1afc2ba1Toomas Soome/*
2afc2ba1Toomas Soome * LZ4 - Fast LZ compression algorithm
3afc2ba1Toomas Soome * Header File
4afc2ba1Toomas Soome * Copyright (C) 2011-2013, Yann Collet.
5afc2ba1Toomas Soome * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6afc2ba1Toomas Soome *
7afc2ba1Toomas Soome * Redistribution and use in source and binary forms, with or without
8afc2ba1Toomas Soome * modification, are permitted provided that the following conditions are
9afc2ba1Toomas Soome * met:
10afc2ba1Toomas Soome *
11afc2ba1Toomas Soome *     * Redistributions of source code must retain the above copyright
12afc2ba1Toomas Soome * notice, this list of conditions and the following disclaimer.
13afc2ba1Toomas Soome *     * Redistributions in binary form must reproduce the above
14afc2ba1Toomas Soome * copyright notice, this list of conditions and the following disclaimer
15afc2ba1Toomas Soome * in the documentation and/or other materials provided with the
16afc2ba1Toomas Soome * distribution.
17afc2ba1Toomas Soome *
18afc2ba1Toomas Soome * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19afc2ba1Toomas Soome * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20afc2ba1Toomas Soome * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21afc2ba1Toomas Soome * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22afc2ba1Toomas Soome * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23afc2ba1Toomas Soome * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24afc2ba1Toomas Soome * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25afc2ba1Toomas Soome * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26afc2ba1Toomas Soome * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27afc2ba1Toomas Soome * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28afc2ba1Toomas Soome * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29afc2ba1Toomas Soome *
30afc2ba1Toomas Soome * You can contact the author at :
31afc2ba1Toomas Soome * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html
32afc2ba1Toomas Soome * - LZ4 source repository : http://code.google.com/p/lz4/
33afc2ba1Toomas Soome */
3410ae99eToomas Soome/*
3510ae99eToomas Soome * Copyright (c) 2016 by Delphix. All rights reserved.
36cab7c30Andy Fiddaman * Copyright 2020 OmniOS Community Edition (OmniOSce) Association.
3710ae99eToomas Soome */
38afc2ba1Toomas Soome
3910ae99eToomas Soome#if defined(_KERNEL) || defined(_FAKE_KERNEL)
4010ae99eToomas Soome#include <sys/zfs_context.h>
4110ae99eToomas Soome#elif defined(_STANDALONE)
4210ae99eToomas Soome#include <sys/cdefs.h>
4310ae99eToomas Soome#include <stand.h>
44afc2ba1Toomas Soome#include <sys/types.h>
4510ae99eToomas Soome#include <sys/endian.h>
46afc2ba1Toomas Soome#include <assert.h>
4710ae99eToomas Soome
4810ae99eToomas Soome#define	ASSERT	assert
4910ae99eToomas Soome#else
50afc2ba1Toomas Soome#include <string.h>
5110ae99eToomas Soome#include <stdlib.h>
5210ae99eToomas Soome#include <sys/types.h>
5310ae99eToomas Soome#include <sys/sysmacros.h>
5410ae99eToomas Soome#include <netinet/in.h>
5510ae99eToomas Soome#include <assert.h>
5610ae99eToomas Soome
5710ae99eToomas Soome#define	ASSERT	assert
5810ae99eToomas Soome#endif
5910ae99eToomas Soome#include <lz4.h>
60afc2ba1Toomas Soome
61afc2ba1Toomas Soomestatic int real_LZ4_compress(const char *source, char *dest, int isize,
62afc2ba1Toomas Soome    int osize);
63afc2ba1Toomas Soomestatic int LZ4_uncompress_unknownOutputSize(const char *source, char *dest,
64afc2ba1Toomas Soome    int isize, int maxOutputSize);
65afc2ba1Toomas Soomestatic int LZ4_compressCtx(void *ctx, const char *source, char *dest,
66afc2ba1Toomas Soome    int isize, int osize);
67afc2ba1Toomas Soomestatic int LZ4_compress64kCtx(void *ctx, const char *source, char *dest,
68afc2ba1Toomas Soome    int isize, int osize);
69afc2ba1Toomas Soome
70afc2ba1Toomas Soomesize_t
7110ae99eToomas Soomelz4_compress(void *s_start, void *d_start, size_t s_len, size_t d_len,
7210ae99eToomas Soome    int n __unused)
73afc2ba1Toomas Soome{
74afc2ba1Toomas Soome	uint32_t bufsiz;
75afc2ba1Toomas Soome	char *dest = d_start;
76afc2ba1Toomas Soome
7710ae99eToomas Soome	ASSERT(d_len >= sizeof (bufsiz));
78afc2ba1Toomas Soome
79afc2ba1Toomas Soome	bufsiz = real_LZ4_compress(s_start, &dest[sizeof (bufsiz)], s_len,
80afc2ba1Toomas Soome	    d_len - sizeof (bufsiz));
81afc2ba1Toomas Soome
82afc2ba1Toomas Soome	/* Signal an error if the compression routine returned zero. */
83afc2ba1Toomas Soome	if (bufsiz == 0)
84afc2ba1Toomas Soome		return (s_len);
85afc2ba1Toomas Soome
86afc2ba1Toomas Soome	/*
87afc2ba1Toomas Soome	 * Encode the compresed buffer size at the start. We'll need this in
88afc2ba1Toomas Soome	 * decompression to counter the effects of padding which might be
89afc2ba1Toomas Soome	 * added to the compressed buffer and which, if unhandled, would
90afc2ba1Toomas Soome	 * confuse the hell out of our decompression function.
91afc2ba1Toomas Soome	 */
9210ae99eToomas Soome#if defined(_KERNEL) || defined(_FAKE_KERNEL)
9310ae99eToomas Soome	*(uint32_t *)(void *)dest = BE_32(bufsiz);
9410ae99eToomas Soome#else
9510ae99eToomas Soome	*(uint32_t *)(void *)dest = htonl(bufsiz);
9610ae99eToomas Soome#endif
97afc2ba1Toomas Soome
98afc2ba1Toomas Soome	return (bufsiz + sizeof (bufsiz));
99afc2ba1Toomas Soome}
100afc2ba1Toomas Soome
101afc2ba1Toomas Soomeint
10210ae99eToomas Soomelz4_decompress(void *s_start, void *d_start, size_t s_len, size_t d_len,
10310ae99eToomas Soome    int n __unused)
104afc2ba1Toomas Soome{
105afc2ba1Toomas Soome	const char *src = s_start;
10610ae99eToomas Soome#if defined(_KERNEL) || defined(_FAKE_KERNEL)
10710ae99eToomas Soome	uint32_t bufsiz = BE_IN32(s_start);
10810ae99eToomas Soome#else
10910ae99eToomas Soome	uint32_t bufsiz = htonl(*(uint32_t *)s_start);
11010ae99eToomas Soome#endif
111afc2ba1Toomas Soome
112afc2ba1Toomas Soome	/* invalid compressed buffer size encoded at start */
113afc2ba1Toomas Soome	if (bufsiz + sizeof (bufsiz) > s_len)
114afc2ba1Toomas Soome		return (1);
115afc2ba1Toomas Soome
116afc2ba1Toomas Soome	/*
117afc2ba1Toomas Soome	 * Returns 0 on success (decompression function returned non-negative)
11810ae99eToomas Soome	 * and non-zero on failure (decompression function returned negative).
119afc2ba1Toomas Soome	 */
120afc2ba1Toomas Soome	return (LZ4_uncompress_unknownOutputSize(&src[sizeof (bufsiz)],
121afc2ba1Toomas Soome	    d_start, bufsiz, d_len) < 0);
122afc2ba1Toomas Soome}
123afc2ba1Toomas Soome
124afc2ba1Toomas Soome/*
125afc2ba1Toomas Soome * LZ4 API Description:
126afc2ba1Toomas Soome *
127afc2ba1Toomas Soome * Simple Functions:
128afc2ba1Toomas Soome * real_LZ4_compress() :
129afc2ba1Toomas Soome *	isize  : is the input size. Max supported value is ~1.9GB
130afc2ba1Toomas Soome *	return : the number of bytes written in buffer dest
13110ae99eToomas Soome *		 or 0 if the compression fails (if LZ4_COMPRESSMIN is set).
132afc2ba1Toomas Soome *	note : destination buffer must be already allocated.
133afc2ba1Toomas Soome *		destination buffer must be sized to handle worst cases
13410ae99eToomas Soome *		situations (input data not compressible).
135afc2ba1Toomas Soome *
136afc2ba1Toomas Soome * Advanced Functions
137afc2ba1Toomas Soome *
13810ae99eToomas Soome * LZ4_compressBound() :
13910ae99eToomas Soome *	Provides the maximum size that LZ4 may output in a "worst case"
14010ae99eToomas Soome *	scenario (input data not compressible) primarily useful for memory
14110ae99eToomas Soome *	allocation of output buffer.
14210ae99eToomas Soome *
14310ae99eToomas Soome *	isize  : is the input size. Max supported value is ~1.9GB
14410ae99eToomas Soome *	return : maximum output size in a "worst case" scenario
14510ae99eToomas Soome *	note : this function is limited by "int" range (2^31-1)
14610ae99eToomas Soome *
147afc2ba1Toomas Soome * LZ4_uncompress_unknownOutputSize() :
148afc2ba1Toomas Soome *	isize  : is the input size, therefore the compressed size
149afc2ba1Toomas Soome *	maxOutputSize : is the size of the destination buffer (which must be
150afc2ba1Toomas Soome *		already allocated)
151afc2ba1Toomas Soome *	return : the number of bytes decoded in the destination buffer
152afc2ba1Toomas Soome *		(necessarily <= maxOutputSize). If the source stream is
153afc2ba1Toomas Soome *		malformed, the function will stop decoding and return a
154afc2ba1Toomas Soome *		negative result, indicating the byte position of the faulty
155afc2ba1Toomas Soome *		instruction. This function never writes beyond dest +
156afc2ba1Toomas Soome *		maxOutputSize, and is therefore protected against malicious
157afc2ba1Toomas Soome *		data packets.
158afc2ba1Toomas Soome *	note   : Destination buffer must be already allocated.
159afc2ba1Toomas Soome *
160afc2ba1Toomas Soome * LZ4_compressCtx() :
161afc2ba1Toomas Soome *	This function explicitly handles the CTX memory structure.
162afc2ba1Toomas Soome *
163afc2ba1Toomas Soome *	ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated
164afc2ba1Toomas Soome *	by the caller (either on the stack or using kmem_zalloc). Passing NULL
165afc2ba1Toomas Soome *	isn't valid.
166afc2ba1Toomas Soome *
167afc2ba1Toomas Soome * LZ4_compress64kCtx() :
168afc2ba1Toomas Soome *	Same as LZ4_compressCtx(), but specific to small inputs (<64KB).
169afc2ba1Toomas Soome *	isize *Must* be <64KB, otherwise the output will be corrupted.
170afc2ba1Toomas Soome *
171afc2ba1Toomas Soome *	ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated
172afc2ba1Toomas Soome *	by the caller (either on the stack or using kmem_zalloc). Passing NULL
173afc2ba1Toomas Soome *	isn't valid.
174afc2ba1Toomas Soome */
175afc2ba1Toomas Soome
176afc2ba1Toomas Soome/*
177afc2ba1Toomas Soome * Tuning parameters
178afc2ba1Toomas Soome */
179afc2ba1Toomas Soome
180afc2ba1Toomas Soome/*
181afc2ba1Toomas Soome * COMPRESSIONLEVEL: Increasing this value improves compression ratio
182afc2ba1Toomas Soome *	 Lowering this value reduces memory usage. Reduced memory usage
183afc2ba1Toomas Soome *	typically improves speed, due to cache effect (ex: L1 32KB for Intel,
184afc2ba1Toomas Soome *	L1 64KB for AMD). Memory usage formula : N->2^(N+2) Bytes
185afc2ba1Toomas Soome *	(examples : 12 -> 16KB ; 17 -> 512KB)
186afc2ba1Toomas Soome */
187afc2ba1Toomas Soome#define	COMPRESSIONLEVEL 12
188afc2ba1Toomas Soome
189afc2ba1Toomas Soome/*
190afc2ba1Toomas Soome * NOTCOMPRESSIBLE_CONFIRMATION: Decreasing this value will make the
191afc2ba1Toomas Soome *	algorithm skip faster data segments considered "incompressible".
192afc2ba1Toomas Soome *	This may decrease compression ratio dramatically, but will be
193afc2ba1Toomas Soome *	faster on incompressible data. Increasing this value will make
194afc2ba1Toomas Soome *	the algorithm search more before declaring a segment "incompressible".
195afc2ba1Toomas Soome *	This could improve compression a bit, but will be slower on
196afc2ba1Toomas Soome *	incompressible data. The default value (6) is recommended.
197afc2ba1Toomas Soome */
198afc2ba1Toomas Soome#define	NOTCOMPRESSIBLE_CONFIRMATION 6
199afc2ba1Toomas Soome
200afc2ba1Toomas Soome/*
201afc2ba1Toomas Soome * BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE: This will provide a boost to
202afc2ba1Toomas Soome * performance for big endian cpu, but the resulting compressed stream
203afc2ba1Toomas Soome * will be incompatible with little-endian CPU. You can set this option
204afc2ba1Toomas Soome * to 1 in situations where data will stay within closed environment.
205afc2ba1Toomas Soome * This option is useless on Little_Endian CPU (such as x86).
206afc2ba1Toomas Soome */
207afc2ba1Toomas Soome/* #define	BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE 1 */
208afc2ba1Toomas Soome
209afc2ba1Toomas Soome/*
210afc2ba1Toomas Soome * CPU Feature Detection
211afc2ba1Toomas Soome */
212afc2ba1Toomas Soome
213afc2ba1Toomas Soome/* 32 or 64 bits ? */
214afc2ba1Toomas Soome#if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) || \
215afc2ba1Toomas Soome    defined(__amd64) || defined(__ppc64__) || defined(_WIN64) || \
216afc2ba1Toomas Soome    defined(__LP64__) || defined(_LP64))
217afc2ba1Toomas Soome#define	LZ4_ARCH64 1
218afc2ba1Toomas Soome#else
219afc2ba1Toomas Soome#define	LZ4_ARCH64 0
220afc2ba1Toomas Soome#endif
221afc2ba1Toomas Soome
222afc2ba1Toomas Soome/*
223afc2ba1Toomas Soome * Limits the amount of stack space that the algorithm may consume to hold
224afc2ba1Toomas Soome * the compression lookup table. The value `9' here means we'll never use
225afc2ba1Toomas Soome * more than 2k of stack (see above for a description of COMPRESSIONLEVEL).
226afc2ba1Toomas Soome * If more memory is needed, it is allocated from the heap.
227afc2ba1Toomas Soome */
228afc2ba1Toomas Soome#define	STACKLIMIT 9
229afc2ba1Toomas Soome
230afc2ba1Toomas Soome/*
231afc2ba1Toomas Soome * Little Endian or Big Endian?
232afc2ba1Toomas Soome * Note: overwrite the below #define if you know your architecture endianess.
233afc2ba1Toomas Soome */
23410ae99eToomas Soome#if defined(BYTE_ORDER)
23510ae99eToomas Soome#if BYTE_ORDER == BIG_ENDIAN	/* This is sys/endian.h API */
23610ae99eToomas Soome#define	LZ4_BIG_ENDIAN 1
23710ae99eToomas Soome#else
23810ae99eToomas Soome/*
23910ae99eToomas Soome * Little Endian assumed. PDP Endian and other very rare endian format
24010ae99eToomas Soome * are unsupported.
24110ae99eToomas Soome */
24210ae99eToomas Soome#endif
24310ae99eToomas Soome#else /* !defined(BYTE_ORDER) */
244afc2ba1Toomas Soome#if (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || \
245afc2ba1Toomas Soome	defined(_BIG_ENDIAN) || defined(_ARCH_PPC) || defined(__PPC__) || \
246afc2ba1Toomas Soome	defined(__PPC) || defined(PPC) || defined(__powerpc__) || \
247afc2ba1Toomas Soome	defined(__powerpc) || defined(powerpc) || \
248afc2ba1Toomas Soome	((defined(__BYTE_ORDER__)&&(__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__))))
249afc2ba1Toomas Soome#define	LZ4_BIG_ENDIAN 1
250afc2ba1Toomas Soome#else
251afc2ba1Toomas Soome/*
252afc2ba1Toomas Soome * Little Endian assumed. PDP Endian and other very rare endian format
253afc2ba1Toomas Soome * are unsupported.
254afc2ba1Toomas Soome */
255afc2ba1Toomas Soome#endif
25610ae99eToomas Soome#endif /* defined(BYTE_ORDER) */
257afc2ba1Toomas Soome
258afc2ba1Toomas Soome/*
259afc2ba1Toomas Soome * Unaligned memory access is automatically enabled for "common" CPU,
260afc2ba1Toomas Soome * such as x86. For others CPU, the compiler will be more cautious, and
261afc2ba1Toomas Soome * insert extra code to ensure aligned access is respected. If you know
262afc2ba1Toomas Soome * your target CPU supports unaligned memory access, you may want to
263afc2ba1Toomas Soome * force this option manually to improve performance
264afc2ba1Toomas Soome */
265afc2ba1Toomas Soome#if defined(__ARM_FEATURE_UNALIGNED)
266afc2ba1Toomas Soome#define	LZ4_FORCE_UNALIGNED_ACCESS 1
267afc2ba1Toomas Soome#endif
268afc2ba1Toomas Soome
269afc2ba1Toomas Soome#ifdef __sparc
270afc2ba1Toomas Soome#define	LZ4_FORCE_SW_BITCOUNT
271afc2ba1Toomas Soome#endif
272afc2ba1Toomas Soome
273afc2ba1Toomas Soome/*
274afc2ba1Toomas Soome * Compiler Options
275afc2ba1Toomas Soome */
276afc2ba1Toomas Soome#if __STDC_VERSION__ >= 199901L	/* C99 */
277afc2ba1Toomas Soome/* "restrict" is a known keyword */
278afc2ba1Toomas Soome#else
279afc2ba1Toomas Soome/* Disable restrict */
280afc2ba1Toomas Soome#define	restrict
281afc2ba1Toomas Soome#endif
282afc2ba1Toomas Soome
283afc2ba1Toomas Soome#define	GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
284afc2ba1Toomas Soome
285afc2ba1Toomas Soome#ifdef _MSC_VER
286afc2ba1Toomas Soome/* Visual Studio */
287afc2ba1Toomas Soome/* Visual is not C99, but supports some kind of inline */
288afc2ba1Toomas Soome#define	inline __forceinline
289afc2ba1Toomas Soome#if LZ4_ARCH64
290afc2ba1Toomas Soome/* For Visual 2005 */
291afc2ba1Toomas Soome#pragma intrinsic(_BitScanForward64)
292afc2ba1Toomas Soome#pragma intrinsic(_BitScanReverse64)
293afc2ba1Toomas Soome#else /* !LZ4_ARCH64 */
294afc2ba1Toomas Soome/* For Visual 2005 */
295afc2ba1Toomas Soome#pragma intrinsic(_BitScanForward)
296afc2ba1Toomas Soome#pragma intrinsic(_BitScanReverse)
297afc2ba1Toomas Soome#endif /* !LZ4_ARCH64 */
298afc2ba1Toomas Soome#endif /* _MSC_VER */
299afc2ba1Toomas Soome
300afc2ba1Toomas Soome#ifdef _MSC_VER
301afc2ba1Toomas Soome#define	lz4_bswap16(x) _byteswap_ushort(x)
302afc2ba1Toomas Soome#else /* !_MSC_VER */
303afc2ba1Toomas Soome#define	lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | \
304afc2ba1Toomas Soome	(((x) & 0xffu) << 8)))
305afc2ba1Toomas Soome#endif /* !_MSC_VER */
306afc2ba1Toomas Soome
307afc2ba1Toomas Soome#if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__)
308afc2ba1Toomas Soome#define	expect(expr, value)    (__builtin_expect((expr), (value)))
309afc2ba1Toomas Soome#else
310afc2ba1Toomas Soome#define	expect(expr, value)    (expr)
311afc2ba1Toomas Soome#endif
312afc2ba1Toomas Soome
31310ae99eToomas Soome#ifndef likely
314afc2ba1Toomas Soome#define	likely(expr)	expect((expr) != 0, 1)
31510ae99eToomas Soome#endif
31610ae99eToomas Soome
31710ae99eToomas Soome#ifndef unlikely
318afc2ba1Toomas Soome#define	unlikely(expr)	expect((expr) != 0, 0)
31910ae99eToomas Soome#endif
320afc2ba1Toomas Soome
321afc2ba1Toomas Soome/* Basic types */
322afc2ba1Toomas Soome#if defined(_MSC_VER)
323afc2ba1Toomas Soome/* Visual Studio does not support 'stdint' natively */
324afc2ba1Toomas Soome#define	BYTE	unsigned __int8
325afc2ba1Toomas Soome#define	U16	unsigned __int16
326afc2ba1Toomas Soome#define	U32	unsigned __int32
327afc2ba1Toomas Soome#define	S32	__int32
328afc2ba1Toomas Soome#define	U64	unsigned __int64
329afc2ba1Toomas Soome#else /* !defined(_MSC_VER) */
330afc2ba1Toomas Soome#define	BYTE	uint8_t
331afc2ba1Toomas Soome#define	U16	uint16_t
332afc2ba1Toomas Soome#define	U32	uint32_t
333afc2ba1Toomas Soome#define	S32	int32_t
334afc2ba1Toomas Soome#define	U64	uint64_t
335afc2ba1Toomas Soome#endif /* !defined(_MSC_VER) */
336afc2ba1Toomas Soome
337afc2ba1Toomas Soome#ifndef LZ4_FORCE_UNALIGNED_ACCESS
338afc2ba1Toomas Soome#pragma pack(1)
339afc2ba1Toomas Soome#endif
340afc2ba1Toomas Soome
341afc2ba1Toomas Soometypedef struct _U16_S {
342afc2ba1Toomas Soome	U16 v;
343afc2ba1Toomas Soome} U16_S;
344afc2ba1Toomas Soometypedef struct _U32_S {
345afc2ba1Toomas Soome	U32 v;
346afc2ba1Toomas Soome} U32_S;
347afc2ba1Toomas Soometypedef struct _U64_S {
348afc2ba1Toomas Soome	U64 v;
349afc2ba1Toomas Soome} U64_S;
350afc2ba1Toomas Soome
351afc2ba1Toomas Soome#ifndef LZ4_FORCE_UNALIGNED_ACCESS
352afc2ba1Toomas Soome#pragma pack()
353afc2ba1Toomas Soome#endif
354afc2ba1Toomas Soome
35510ae99eToomas Soome#define	A64(x) (((U64_S *)(__DECONST(void *, x)))->v)
35610ae99eToomas Soome#define	A32(x) (((U32_S *)(__DECONST(void *, x)))->v)
35710ae99eToomas Soome#define	A16(x) (((U16_S *)(__DECONST(void *, x)))->v)
358afc2ba1Toomas Soome
359afc2ba1Toomas Soome/*
360afc2ba1Toomas Soome * Constants
361afc2ba1Toomas Soome */
362afc2ba1Toomas Soome#define	MINMATCH 4
363afc2ba1Toomas Soome
364afc2ba1Toomas Soome#define	HASH_LOG COMPRESSIONLEVEL
365afc2ba1Toomas Soome#define	HASHTABLESIZE (1 << HASH_LOG)
366afc2ba1Toomas Soome#define	HASH_MASK (HASHTABLESIZE - 1)
367afc2ba1Toomas Soome
368afc2ba1Toomas Soome#define	SKIPSTRENGTH (NOTCOMPRESSIBLE_CONFIRMATION > 2 ? \
369afc2ba1Toomas Soome	NOTCOMPRESSIBLE_CONFIRMATION : 2)
370afc2ba1Toomas Soome
371afc2ba1Toomas Soome/*
372afc2ba1Toomas Soome * Defines if memory is allocated into the stack (local variable),
373afc2ba1Toomas Soome * or into the heap (kmem_alloc()).
374afc2ba1Toomas Soome */
375afc2ba1Toomas Soome#define	HEAPMODE (HASH_LOG > STACKLIMIT)
376afc2ba1Toomas Soome#define	COPYLENGTH 8
377afc2ba1Toomas Soome#define	LASTLITERALS 5
378afc2ba1Toomas Soome#define	MFLIMIT (COPYLENGTH + MINMATCH)
379afc2ba1Toomas Soome#define	MINLENGTH (MFLIMIT + 1)
380afc2ba1Toomas Soome
381afc2ba1Toomas Soome#define	MAXD_LOG 16
382afc2ba1Toomas Soome#define	MAX_DISTANCE ((1 << MAXD_LOG) - 1)
383afc2ba1Toomas Soome
384afc2ba1Toomas Soome#define	ML_BITS 4
385afc2ba1Toomas Soome#define	ML_MASK ((1U<<ML_BITS)-1)
386afc2ba1Toomas Soome#define	RUN_BITS (8-ML_BITS)
387afc2ba1Toomas Soome#define	RUN_MASK ((1U<<RUN_BITS)-1)
388afc2ba1Toomas Soome
389afc2ba1Toomas Soome
390afc2ba1Toomas Soome/*
391afc2ba1Toomas Soome * Architecture-specific macros
392afc2ba1Toomas Soome */
393afc2ba1Toomas Soome#if LZ4_ARCH64
394afc2ba1Toomas Soome#define	STEPSIZE 8
395afc2ba1Toomas Soome#define	UARCH U64
396afc2ba1Toomas Soome#define	AARCH A64
397afc2ba1Toomas Soome#define	LZ4_COPYSTEP(s, d)	A64(d) = A64(s); d += 8; s += 8;
398afc2ba1Toomas Soome#define	LZ4_COPYPACKET(s, d)	LZ4_COPYSTEP(s, d)
399afc2ba1Toomas Soome#define	LZ4_SECURECOPY(s, d, e)	if (d < e) LZ4_WILDCOPY(s, d, e)
400afc2ba1Toomas Soome#define	HTYPE U32
401afc2ba1Toomas Soome#define	INITBASE(base)		const BYTE* const base = ip
402afc2ba1Toomas Soome#else /* !LZ4_ARCH64 */
403afc2ba1Toomas Soome#define	STEPSIZE 4
404afc2ba1Toomas Soome#define	UARCH U32
405afc2ba1Toomas Soome#define	AARCH A32
406afc2ba1Toomas Soome#define	LZ4_COPYSTEP(s, d)	A32(d) = A32(s); d += 4; s += 4;
407afc2ba1Toomas Soome#define	LZ4_COPYPACKET(s, d)	LZ4_COPYSTEP(s, d); LZ4_COPYSTEP(s, d);
408afc2ba1Toomas Soome#define	LZ4_SECURECOPY		LZ4_WILDCOPY
409afc2ba1Toomas Soome#define	HTYPE const BYTE *
410afc2ba1Toomas Soome#define	INITBASE(base)		const int base = 0
411afc2ba1Toomas Soome#endif /* !LZ4_ARCH64 */
412afc2ba1Toomas Soome
413afc2ba1Toomas Soome#if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE))
414afc2ba1Toomas Soome#define	LZ4_READ_LITTLEENDIAN_16(d, s, p) \
415afc2ba1Toomas Soome	{ U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; }
416afc2ba1Toomas Soome#define	LZ4_WRITE_LITTLEENDIAN_16(p, i) \
417afc2ba1Toomas Soome	{ U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p += 2; }
418afc2ba1Toomas Soome#else
419afc2ba1Toomas Soome#define	LZ4_READ_LITTLEENDIAN_16(d, s, p) { d = (s) - A16(p); }
420afc2ba1Toomas Soome#define	LZ4_WRITE_LITTLEENDIAN_16(p, v)  { A16(p) = v; p += 2; }
421afc2ba1Toomas Soome#endif
422afc2ba1Toomas Soome
423afc2ba1Toomas Soome
424afc2ba1Toomas Soome/* Local structures */
425afc2ba1Toomas Soomestruct refTables {
426afc2ba1Toomas Soome	HTYPE hashTable[HASHTABLESIZE];
427afc2ba1Toomas Soome};
428afc2ba1Toomas Soome
429afc2ba1Toomas Soome
430afc2ba1Toomas Soome/* Macros */
431afc2ba1Toomas Soome#define	LZ4_HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH * 8) - \
432afc2ba1Toomas Soome	HASH_LOG))
433afc2ba1Toomas Soome#define	LZ4_HASH_VALUE(p) LZ4_HASH_FUNCTION(A32(p))
434afc2ba1Toomas Soome#define	LZ4_WILDCOPY(s, d, e) do { LZ4_COPYPACKET(s, d) } while (d < e);
435afc2ba1Toomas Soome#define	LZ4_BLINDCOPY(s, d, l) { BYTE* e = (d) + l; LZ4_WILDCOPY(s, d, e); \
436afc2ba1Toomas Soome	d = e; }
437afc2ba1Toomas Soome
438afc2ba1Toomas Soome
439afc2ba1Toomas Soome/* Private functions */
440afc2ba1Toomas Soome#if LZ4_ARCH64
441afc2ba1Toomas Soome
44210ae99eToomas Soomestatic inline int
443afc2ba1Toomas SoomeLZ4_NbCommonBytes(register U64 val)
444afc2ba1Toomas Soome{
445afc2ba1Toomas Soome#if defined(LZ4_BIG_ENDIAN)
446afc2ba1Toomas Soome#if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
447afc2ba1Toomas Soome	unsigned long r = 0;
448afc2ba1Toomas Soome	_BitScanReverse64(&r, val);
449afc2ba1Toomas Soome	return (int)(r >> 3);
450afc2ba1Toomas Soome#elif defined(__GNUC__) && (GCC_VERSION >= 304) && \
451afc2ba1Toomas Soome	!defined(LZ4_FORCE_SW_BITCOUNT)
452afc2ba1Toomas Soome	return (__builtin_clzll(val) >> 3);
453afc2ba1Toomas Soome#else
454afc2ba1Toomas Soome	int r;
455afc2ba1Toomas Soome	if (!(val >> 32)) {
456afc2ba1Toomas Soome		r = 4;
457afc2ba1Toomas Soome	} else {
458afc2ba1Toomas Soome		r = 0;
459afc2ba1Toomas Soome		val >>= 32;
460afc2ba1Toomas Soome	}
461afc2ba1Toomas Soome	if (!(val >> 16)) {
462afc2ba1Toomas Soome		r += 2;
463afc2ba1Toomas Soome		val >>= 8;
464afc2ba1Toomas Soome	} else {
465afc2ba1Toomas Soome		val >>= 24;
466afc2ba1Toomas Soome	}
467afc2ba1Toomas Soome	r += (!val);
468afc2ba1Toomas Soome	return (r);
469afc2ba1Toomas Soome#endif
470afc2ba1Toomas Soome#else
471afc2ba1Toomas Soome#if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
472afc2ba1Toomas Soome	unsigned long r = 0;
473afc2ba1Toomas Soome	_BitScanForward64(&r, val);
474afc2ba1Toomas Soome	return (int)(r >> 3);
475afc2ba1Toomas Soome#elif defined(__GNUC__) && (GCC_VERSION >= 304) && \
476afc2ba1Toomas Soome	!defined(LZ4_FORCE_SW_BITCOUNT)
477afc2ba1Toomas Soome	return (__builtin_ctzll(val) >> 3);
478afc2ba1Toomas Soome#else
479afc2ba1Toomas Soome	static const int DeBruijnBytePos[64] =
480afc2ba1Toomas Soome	    { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5,
481afc2ba1Toomas Soome		3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5,
482afc2ba1Toomas Soome		5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4,
483afc2ba1Toomas Soome		4, 5, 7, 2, 6, 5, 7, 6, 7, 7
484afc2ba1Toomas Soome	};
485afc2ba1Toomas Soome	return DeBruijnBytePos[((U64) ((val & -val) * 0x0218A392CDABBD3F)) >>
486afc2ba1Toomas Soome	    58];
487afc2ba1Toomas Soome#endif
488afc2ba1Toomas Soome#endif
489afc2ba1Toomas Soome}
490afc2ba1Toomas Soome
491afc2ba1Toomas Soome#else
492afc2ba1Toomas Soome
49310ae99eToomas Soomestatic inline int
494afc2ba1Toomas SoomeLZ4_NbCommonBytes(register U32 val)
495afc2ba1Toomas Soome{
496afc2ba1Toomas Soome#if defined(LZ4_BIG_ENDIAN)
497afc2ba1Toomas Soome#if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
498afc2ba1Toomas Soome	unsigned long r = 0;
499afc2ba1Toomas Soome	_BitScanReverse(&r, val);
500afc2ba1Toomas Soome	return (int)(r >> 3);
501afc2ba1Toomas Soome#elif defined(__GNUC__) && (GCC_VERSION >= 304) && \
502afc2ba1Toomas Soome	!defined(LZ4_FORCE_SW_BITCOUNT)
503afc2ba1Toomas Soome	return (__builtin_clz(val) >> 3);
504afc2ba1Toomas Soome#else
505afc2ba1Toomas Soome	int r;
506afc2ba1Toomas Soome	if (!(val >> 16)) {
507afc2ba1Toomas Soome		r = 2;
508afc2ba1Toomas Soome		val >>= 8;
509afc2ba1Toomas Soome	} else {
510afc2ba1Toomas Soome		r = 0;
511afc2ba1Toomas Soome		val >>= 24;
512afc2ba1Toomas Soome	}
513afc2ba1Toomas Soome	r += (!val);
514afc2ba1Toomas Soome	return (r);
515afc2ba1Toomas Soome#endif
516afc2ba1Toomas Soome#else
517afc2ba1Toomas Soome#if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
518afc2ba1Toomas Soome	unsigned long r = 0;
519afc2ba1Toomas Soome	_BitScanForward(&r, val);
520afc2ba1Toomas Soome	return (int)(r >> 3);
521afc2ba1Toomas Soome#elif defined(__GNUC__) && (GCC_VERSION >= 304) && \
522afc2ba1Toomas Soome	!defined(LZ4_FORCE_SW_BITCOUNT)
523afc2ba1Toomas Soome	return (__builtin_ctz(val) >> 3);
524afc2ba1Toomas Soome#else
525afc2ba1Toomas Soome	static const int DeBruijnBytePos[32] = {
526afc2ba1Toomas Soome		0, 0, 3, 0, 3, 1, 3, 0,
527afc2ba1Toomas Soome		3, 2, 2, 1, 3, 2, 0, 1,
528afc2ba1Toomas Soome		3, 3, 1, 2, 2, 2, 2, 0,
529afc2ba1Toomas Soome		3, 1, 2, 0, 1, 0, 1, 1
530afc2ba1Toomas Soome	};
531afc2ba1Toomas Soome	return DeBruijnBytePos[((U32) ((val & -(S32) val) * 0x077CB531U)) >>
532afc2ba1Toomas Soome	    27];
533afc2ba1Toomas Soome#endif
534afc2ba1Toomas Soome#endif
535afc2ba1Toomas Soome}
536afc2ba1Toomas Soome
537afc2ba1Toomas Soome#endif
538afc2ba1Toomas Soome
539afc2ba1Toomas Soome/* Compression functions */
540afc2ba1Toomas Soome
541afc2ba1Toomas Soome/*ARGSUSED*/
542afc2ba1Toomas Soomestatic int
543afc2ba1Toomas SoomeLZ4_compressCtx(void *ctx, const char *source, char *dest, int isize,
544afc2ba1Toomas Soome    int osize)
545afc2ba1Toomas Soome{
546afc2ba1Toomas Soome#if HEAPMODE
547afc2ba1Toomas Soome	struct refTables *srt = (struct refTables *)ctx;
548afc2ba1Toomas Soome	HTYPE *HashTable = (HTYPE *) (srt->hashTable);
549afc2ba1Toomas Soome#else
550afc2ba1Toomas Soome	HTYPE HashTable[HASHTABLESIZE] = { 0 };
551afc2ba1Toomas Soome#endif
552afc2ba1Toomas Soome
55310ae99eToomas Soome	const BYTE *ip = (const BYTE *) source;
554afc2ba1Toomas Soome	INITBASE(base);
555afc2ba1Toomas Soome	const BYTE *anchor = ip;
556afc2ba1Toomas Soome	const BYTE *const iend = ip + isize;
557afc2ba1Toomas Soome	const BYTE *const oend = (BYTE *) dest + osize;
558afc2ba1Toomas Soome	const BYTE *const mflimit = iend - MFLIMIT;
559afc2ba1Toomas Soome#define	matchlimit (iend - LASTLITERALS)
560afc2ba1Toomas Soome
561afc2ba1Toomas Soome	BYTE *op = (BYTE *) dest;
562afc2ba1Toomas Soome
563afc2ba1Toomas Soome	int len, length;
564afc2ba1Toomas Soome	const int skipStrength = SKIPSTRENGTH;
565afc2ba1Toomas Soome	U32 forwardH;
566afc2ba1Toomas Soome
567afc2ba1Toomas Soome
568afc2ba1Toomas Soome	/* Init */
569afc2ba1Toomas Soome	if (isize < MINLENGTH)
570afc2ba1Toomas Soome		goto _last_literals;
571afc2ba1Toomas Soome
572afc2ba1Toomas Soome	/* First Byte */
573afc2ba1Toomas Soome	HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
574afc2ba1Toomas Soome	ip++;
575afc2ba1Toomas Soome	forwardH = LZ4_HASH_VALUE(ip);
576afc2ba1Toomas Soome
577afc2ba1Toomas Soome	/* Main Loop */
578afc2ba1Toomas Soome	for (;;) {
579afc2ba1Toomas Soome		int findMatchAttempts = (1U << skipStrength) + 3;
580afc2ba1Toomas Soome		const BYTE *forwardIp = ip;
581afc2ba1Toomas Soome		const BYTE *ref;
582afc2ba1Toomas Soome		BYTE *token;
583afc2ba1Toomas Soome
584afc2ba1Toomas Soome		/* Find a match */
585afc2ba1Toomas Soome		do {
586afc2ba1Toomas Soome			U32 h = forwardH;
587afc2ba1Toomas Soome			int step = findMatchAttempts++ >> skipStrength;
588afc2ba1Toomas Soome			ip = forwardIp;
589afc2ba1Toomas Soome			forwardIp = ip + step;
590afc2ba1Toomas Soome
591afc2ba1Toomas Soome			if unlikely(forwardIp > mflimit) {
592afc2ba1Toomas Soome				goto _last_literals;
593afc2ba1Toomas Soome			}
594afc2ba1Toomas Soome
595afc2ba1Toomas Soome			forwardH = LZ4_HASH_VALUE(forwardIp);
596afc2ba1Toomas Soome			ref = base + HashTable[h];
597afc2ba1Toomas Soome			HashTable[h] = ip - base;
598afc2ba1Toomas Soome
599afc2ba1Toomas Soome		} while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip)));
600afc2ba1Toomas Soome
601afc2ba1Toomas Soome		/* Catch up */
60210ae99eToomas Soome		while ((ip > anchor) && (ref > (const BYTE *) source) &&
603afc2ba1Toomas Soome		    unlikely(ip[-1] == ref[-1])) {
604afc2ba1Toomas Soome			ip--;
605afc2ba1Toomas Soome			ref--;
606afc2ba1Toomas Soome		}
607afc2ba1Toomas Soome
608afc2ba1Toomas Soome		/* Encode Literal length */
609afc2ba1Toomas Soome		length = ip - anchor;
610afc2ba1Toomas Soome		token = op++;
611afc2ba1Toomas Soome
612afc2ba1Toomas Soome		/* Check output limit */
613afc2ba1Toomas Soome		if unlikely(op + length + (2 + 1 + LASTLITERALS) +
614afc2ba1Toomas Soome		    (length >> 8) > oend)
615afc2ba1Toomas Soome			return (0);
616afc2ba1Toomas Soome
617afc2ba1Toomas Soome		if (length >= (int)RUN_MASK) {
618afc2ba1Toomas Soome			*token = (RUN_MASK << ML_BITS);
619afc2ba1Toomas Soome			len = length - RUN_MASK;
620afc2ba1Toomas Soome			for (; len > 254; len -= 255)
621afc2ba1Toomas Soome				*op++ = 255;
622afc2ba1Toomas Soome			*op++ = (BYTE)len;
623afc2ba1Toomas Soome		} else
624afc2ba1Toomas Soome			*token = (length << ML_BITS);
625afc2ba1Toomas Soome
626afc2ba1Toomas Soome		/* Copy Literals */
627afc2ba1Toomas Soome		LZ4_BLINDCOPY(anchor, op, length);
628afc2ba1Toomas Soome
629afc2ba1Toomas Soome		_next_match:
630afc2ba1Toomas Soome		/* Encode Offset */
631afc2ba1Toomas Soome		LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref);
632afc2ba1Toomas Soome
633afc2ba1Toomas Soome		/* Start Counting */
634afc2ba1Toomas Soome		ip += MINMATCH;
635afc2ba1Toomas Soome		ref += MINMATCH;	/* MinMatch verified */
636afc2ba1Toomas Soome		anchor = ip;
637afc2ba1Toomas Soome		while likely(ip < matchlimit - (STEPSIZE - 1)) {
638afc2ba1Toomas Soome			UARCH diff = AARCH(ref) ^ AARCH(ip);
639afc2ba1Toomas Soome			if (!diff) {
640afc2ba1Toomas Soome				ip += STEPSIZE;
641afc2ba1Toomas Soome				ref += STEPSIZE;
642afc2ba1Toomas Soome				continue;
643afc2ba1Toomas Soome			}
644afc2ba1Toomas Soome			ip += LZ4_NbCommonBytes(diff);
645afc2ba1Toomas Soome			goto _endCount;
646afc2ba1Toomas Soome		}
647afc2ba1Toomas Soome#if LZ4_ARCH64
648afc2ba1Toomas Soome		if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) {
649afc2ba1Toomas Soome			ip += 4;
650afc2ba1Toomas Soome			ref += 4;
651afc2ba1Toomas Soome		}
652afc2ba1Toomas Soome#endif
653afc2ba1Toomas Soome		if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) {
654afc2ba1Toomas Soome			ip += 2;
655afc2ba1Toomas Soome			ref += 2;
656afc2ba1Toomas Soome		}
657afc2ba1Toomas Soome		if ((ip < matchlimit) && (*ref == *ip))
658afc2ba1Toomas Soome			ip++;
659afc2ba1Toomas Soome		_endCount:
660afc2ba1Toomas Soome
661afc2ba1Toomas Soome		/* Encode MatchLength */
662afc2ba1Toomas Soome		len = (ip - anchor);
663afc2ba1Toomas Soome		/* Check output limit */
664afc2ba1Toomas Soome		if unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend)
665afc2ba1Toomas Soome			return (0);
666afc2ba1Toomas Soome		if (len >= (int)ML_MASK) {
667afc2ba1Toomas Soome			*token += ML_MASK;
668afc2ba1Toomas Soome			len -= ML_MASK;
669afc2ba1Toomas Soome			for (; len > 509; len -= 510) {
670afc2ba1Toomas Soome				*op++ = 255;
671afc2ba1Toomas Soome				*op++ = 255;
672afc2ba1Toomas Soome			}
673afc2ba1Toomas Soome			if (len > 254) {
674afc2ba1Toomas Soome				len -= 255;
675afc2ba1Toomas Soome				*op++ = 255;
676afc2ba1Toomas Soome			}
677afc2ba1Toomas Soome			*op++ = (BYTE)len;
678afc2ba1Toomas Soome		} else
679afc2ba1Toomas Soome			*token += len;
680afc2ba1Toomas Soome
681afc2ba1Toomas Soome		/* Test end of chunk */
682afc2ba1Toomas Soome		if (ip > mflimit) {
683afc2ba1Toomas Soome			anchor = ip;
684afc2ba1Toomas Soome			break;
685afc2ba1Toomas Soome		}
686afc2ba1Toomas Soome		/* Fill table */
687afc2ba1Toomas Soome		HashTable[LZ4_HASH_VALUE(ip - 2)] = ip - 2 - base;
688afc2ba1Toomas Soome
689afc2ba1Toomas Soome		/* Test next position */
690afc2ba1Toomas Soome		ref = base + HashTable[LZ4_HASH_VALUE(ip)];
691afc2ba1Toomas Soome		HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
692afc2ba1Toomas Soome		if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) {
693afc2ba1Toomas Soome			token = op++;
694afc2ba1Toomas Soome			*token = 0;
695afc2ba1Toomas Soome			goto _next_match;
696afc2ba1Toomas Soome		}
697afc2ba1Toomas Soome		/* Prepare next loop */
698afc2ba1Toomas Soome		anchor = ip++;
699afc2ba1Toomas Soome		forwardH = LZ4_HASH_VALUE(ip);
700afc2ba1Toomas Soome	}
701afc2ba1Toomas Soome
702afc2ba1Toomas Soome	_last_literals:
703afc2ba1Toomas Soome	/* Encode Last Literals */
704afc2ba1Toomas Soome	{
705afc2ba1Toomas Soome		int lastRun = iend - anchor;
706afc2ba1Toomas Soome		if (op + lastRun + 1 + ((lastRun + 255 - RUN_MASK) / 255) >
707afc2ba1Toomas Soome		    oend)
708afc2ba1Toomas Soome			return (0);
709afc2ba1Toomas Soome		if (lastRun >= (int)RUN_MASK) {
710afc2ba1Toomas Soome			*op++ = (RUN_MASK << ML_BITS);
711afc2ba1Toomas Soome			lastRun -= RUN_MASK;
712afc2ba1Toomas Soome			for (; lastRun > 254; lastRun -= 255) {
713afc2ba1Toomas Soome				*op++ = 255;
714afc2ba1Toomas Soome			}
715afc2ba1Toomas Soome			*op++ = (BYTE)lastRun;
716afc2ba1Toomas Soome		} else
717afc2ba1Toomas Soome			*op++ = (lastRun << ML_BITS);
718afc2ba1Toomas Soome		(void) memcpy(op, anchor, iend - anchor);
719afc2ba1Toomas Soome		op += iend - anchor;
720afc2ba1Toomas Soome	}
721afc2ba1Toomas Soome
722afc2ba1Toomas Soome	/* End */
723afc2ba1Toomas Soome	return (int)(((char *)op) - dest);
724afc2ba1Toomas Soome}
725afc2ba1Toomas Soome
726afc2ba1Toomas Soome
727afc2ba1Toomas Soome
728afc2ba1Toomas Soome/* Note : this function is valid only if isize < LZ4_64KLIMIT */
729afc2ba1Toomas Soome#define	LZ4_64KLIMIT ((1 << 16) + (MFLIMIT - 1))
730afc2ba1Toomas Soome#define	HASHLOG64K (HASH_LOG + 1)
731afc2ba1Toomas Soome#define	HASH64KTABLESIZE (1U << HASHLOG64K)
732afc2ba1Toomas Soome#define	LZ4_HASH64K_FUNCTION(i)	(((i) * 2654435761U) >> ((MINMATCH*8) - \
733afc2ba1Toomas Soome	HASHLOG64K))
734afc2ba1Toomas Soome#define	LZ4_HASH64K_VALUE(p)	LZ4_HASH64K_FUNCTION(A32(p))
735afc2ba1Toomas Soome
736afc2ba1Toomas Soome/*ARGSUSED*/
737afc2ba1Toomas Soomestatic int
738afc2ba1Toomas SoomeLZ4_compress64kCtx(void *ctx, const char *source, char *dest, int isize,
739afc2ba1Toomas Soome    int osize)
740afc2ba1Toomas Soome{
741afc2ba1Toomas Soome#if HEAPMODE
742afc2ba1Toomas Soome	struct refTables *srt = (struct refTables *)ctx;
743afc2ba1Toomas Soome	U16 *HashTable = (U16 *) (srt->hashTable);
744afc2ba1Toomas Soome#else
745afc2ba1Toomas Soome	U16 HashTable[HASH64KTABLESIZE] = { 0 };
746afc2ba1Toomas Soome#endif
747afc2ba1Toomas Soome
74810ae99eToomas Soome	const BYTE *ip = (const BYTE *) source;
749afc2ba1Toomas Soome	const BYTE *anchor = ip;
750afc2ba1Toomas Soome	const BYTE *const base = ip;
751afc2ba1Toomas Soome	const BYTE *const iend = ip + isize;
752afc2ba1Toomas Soome	const BYTE *const oend = (BYTE *) dest + osize;
753afc2ba1Toomas Soome	const BYTE *const mflimit = iend - MFLIMIT;
754afc2ba1Toomas Soome#define	matchlimit (iend - LASTLITERALS)
755afc2ba1Toomas Soome
756afc2ba1Toomas Soome	BYTE *op = (BYTE *) dest;
757afc2ba1Toomas Soome
758afc2ba1Toomas Soome	int len, length;
759afc2ba1Toomas Soome	const int skipStrength = SKIPSTRENGTH;
760afc2ba1Toomas Soome	U32 forwardH;
761afc2ba1Toomas Soome
762afc2ba1Toomas Soome	/* Init */
763afc2ba1Toomas Soome	if (isize < MINLENGTH)
764afc2ba1Toomas Soome		goto _last_literals;
765afc2ba1Toomas Soome
766afc2ba1Toomas Soome	/* First Byte */
767afc2ba1Toomas Soome	ip++;
768afc2ba1Toomas Soome	forwardH = LZ4_HASH64K_VALUE(ip);
769afc2ba1Toomas Soome
770afc2ba1Toomas Soome	/* Main Loop */
771afc2ba1Toomas Soome	for (;;) {
772afc2ba1Toomas Soome		int findMatchAttempts = (1U << skipStrength) + 3;
773afc2ba1Toomas Soome		const BYTE *forwardIp = ip;
774afc2ba1Toomas Soome		const BYTE *ref;
775afc2ba1Toomas Soome		BYTE *token;
776afc2ba1Toomas Soome
777afc2ba1Toomas Soome		/* Find a match */
778afc2ba1Toomas Soome		do {
779afc2ba1Toomas Soome			U32 h = forwardH;
780afc2ba1Toomas Soome			int step = findMatchAttempts++ >> skipStrength;
781afc2ba1Toomas Soome			ip = forwardIp;
782afc2ba1Toomas Soome			forwardIp = ip + step;
783afc2ba1Toomas Soome
784afc2ba1Toomas Soome			if (forwardIp > mflimit) {
785afc2ba1Toomas Soome				goto _last_literals;
786afc2ba1Toomas Soome			}
787afc2ba1Toomas Soome
788afc2ba1Toomas Soome			forwardH = LZ4_HASH64K_VALUE(forwardIp);
789afc2ba1Toomas Soome			ref = base + HashTable[h];
790afc2ba1Toomas Soome			HashTable[h] = ip - base;
791afc2ba1Toomas Soome
792afc2ba1Toomas Soome		} while (A32(ref) != A32(ip));
793afc2ba1Toomas Soome
794afc2ba1Toomas Soome		/* Catch up */
79510ae99eToomas Soome		while ((ip > anchor) && (ref > (const BYTE *) source) &&
796afc2ba1Toomas Soome		    (ip[-1] == ref[-1])) {
797afc2ba1Toomas Soome			ip--;
798afc2ba1Toomas Soome			ref--;
799afc2ba1Toomas Soome		}
800afc2ba1Toomas Soome
801afc2ba1Toomas Soome		/* Encode Literal length */
802afc2ba1Toomas Soome		length = ip - anchor;
803afc2ba1Toomas Soome		token = op++;
804afc2ba1Toomas Soome
805afc2ba1Toomas Soome		/* Check output limit */
806afc2ba1Toomas Soome		if unlikely(op + length + (2 + 1 + LASTLITERALS) +
807afc2ba1Toomas Soome		    (length >> 8) > oend)
808afc2ba1Toomas Soome			return (0);
809afc2ba1Toomas Soome
810afc2ba1Toomas Soome		if (length >= (int)RUN_MASK) {
811afc2ba1Toomas Soome			*token = (RUN_MASK << ML_BITS);
812afc2ba1Toomas Soome			len = length - RUN_MASK;
813afc2ba1Toomas Soome			for (; len > 254; len -= 255)
814afc2ba1Toomas Soome				*op++ = 255;
815afc2ba1Toomas Soome			*op++ = (BYTE)len;
816afc2ba1Toomas Soome		} else
817afc2ba1Toomas Soome			*token = (length << ML_BITS);
818afc2ba1Toomas Soome
819afc2ba1Toomas Soome		/* Copy Literals */
820afc2ba1Toomas Soome		LZ4_BLINDCOPY(anchor, op, length);
821afc2ba1Toomas Soome
822afc2ba1Toomas Soome		_next_match:
823afc2ba1Toomas Soome		/* Encode Offset */
824afc2ba1Toomas Soome		LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref);
825afc2ba1Toomas Soome
826afc2ba1Toomas Soome		/* Start Counting */
827afc2ba1Toomas Soome		ip += MINMATCH;
828afc2ba1Toomas Soome		ref += MINMATCH;	/* MinMatch verified */
829afc2ba1Toomas Soome		anchor = ip;
830afc2ba1Toomas Soome		while (ip < matchlimit - (STEPSIZE - 1)) {
831afc2ba1Toomas Soome			UARCH diff = AARCH(ref) ^ AARCH(ip);
832afc2ba1Toomas Soome			if (!diff) {
833afc2ba1Toomas Soome				ip += STEPSIZE;
834afc2ba1Toomas Soome				ref += STEPSIZE;
835afc2ba1Toomas Soome				continue;
836afc2ba1Toomas Soome			}
837afc2ba1Toomas Soome			ip += LZ4_NbCommonBytes(diff);
838afc2ba1Toomas Soome			goto _endCount;
839afc2ba1Toomas Soome		}
840afc2ba1Toomas Soome#if LZ4_ARCH64
841afc2ba1Toomas Soome		if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) {
842afc2ba1Toomas Soome			ip += 4;
843afc2ba1Toomas Soome			ref += 4;
844afc2ba1Toomas Soome		}
845afc2ba1Toomas Soome#endif
846afc2ba1Toomas Soome		if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) {
847afc2ba1Toomas Soome			ip += 2;
848afc2ba1Toomas Soome			ref += 2;
849afc2ba1Toomas Soome		}
850afc2ba1Toomas Soome		if ((ip < matchlimit) && (*ref == *ip))
851afc2ba1Toomas Soome			ip++;
852afc2ba1Toomas Soome		_endCount:
853afc2ba1Toomas Soome
854afc2ba1Toomas Soome		/* Encode MatchLength */
855afc2ba1Toomas Soome		len = (ip - anchor);
856afc2ba1Toomas Soome		/* Check output limit */
857afc2ba1Toomas Soome		if unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend)
858afc2ba1Toomas Soome			return (0);
859afc2ba1Toomas Soome		if (len >= (int)ML_MASK) {
860afc2ba1Toomas Soome			*token += ML_MASK;
861afc2ba1Toomas Soome			len -= ML_MASK;
862afc2ba1Toomas Soome			for (; len > 509; len -= 510) {
863afc2ba1Toomas Soome				*op++ = 255;
864afc2ba1Toomas Soome				*op++ = 255;
865afc2ba1Toomas Soome			}
866afc2ba1Toomas Soome			if (len > 254) {
867afc2ba1Toomas Soome				len -= 255;
868afc2ba1Toomas Soome				*op++ = 255;
869afc2ba1Toomas Soome			}
870afc2ba1Toomas Soome			*op++ = (BYTE)len;
871afc2ba1Toomas Soome		} else
872afc2ba1Toomas Soome			*token += len;
873afc2ba1Toomas Soome
874afc2ba1Toomas Soome		/* Test end of chunk */
875afc2ba1Toomas Soome		if (ip > mflimit) {
876afc2ba1Toomas Soome			anchor = ip;
877afc2ba1Toomas Soome			break;
878afc2ba1Toomas Soome		}
879afc2ba1Toomas Soome		/* Fill table */
880afc2ba1Toomas Soome		HashTable[LZ4_HASH64K_VALUE(ip - 2)] = ip - 2 - base;
881afc2ba1Toomas Soome
882afc2ba1Toomas Soome		/* Test next position */
883afc2ba1Toomas Soome		ref = base + HashTable[LZ4_HASH64K_VALUE(ip)];
884afc2ba1Toomas Soome		HashTable[LZ4_HASH64K_VALUE(ip)] = ip - base;
885afc2ba1Toomas Soome		if (A32(ref) == A32(ip)) {
886afc2ba1Toomas Soome			token = op++;
887afc2ba1Toomas Soome			*token = 0;
888afc2ba1Toomas Soome			goto _next_match;
889afc2ba1Toomas Soome		}
890afc2ba1Toomas Soome		/* Prepare next loop */
891afc2ba1Toomas Soome		anchor = ip++;
892afc2ba1Toomas Soome		forwardH = LZ4_HASH64K_VALUE(ip);
893afc2ba1Toomas Soome	}
894afc2ba1Toomas Soome
895afc2ba1Toomas Soome	_last_literals:
896afc2ba1Toomas Soome	/* Encode Last Literals */
897afc2ba1Toomas Soome	{
898afc2ba1Toomas Soome		int lastRun = iend - anchor;
899afc2ba1Toomas Soome		if (op + lastRun + 1 + ((lastRun + 255 - RUN_MASK) / 255) >
900afc2ba1Toomas Soome		    oend)
901afc2ba1Toomas Soome			return (0);
902afc2ba1Toomas Soome		if (lastRun >= (int)RUN_MASK) {
903afc2ba1Toomas Soome			*op++ = (RUN_MASK << ML_BITS);
904afc2ba1Toomas Soome			lastRun -= RUN_MASK;
905afc2ba1Toomas Soome			for (; lastRun > 254; lastRun -= 255)
906afc2ba1Toomas Soome				*op++ = 255;
907afc2ba1Toomas Soome			*op++ = (BYTE)lastRun;
908afc2ba1Toomas Soome		} else
909afc2ba1Toomas Soome			*op++ = (lastRun << ML_BITS);
910afc2ba1Toomas Soome		(void) memcpy(op, anchor, iend - anchor);
911afc2ba1Toomas Soome		op += iend - anchor;
912afc2ba1Toomas Soome	}
913afc2ba1Toomas Soome
914afc2ba1Toomas Soome	/* End */
915afc2ba1Toomas Soome	return (int)(((char *)op) - dest);
916afc2ba1Toomas Soome}
917afc2ba1Toomas Soome
918afc2ba1Toomas Soomestatic int
919afc2ba1Toomas Soomereal_LZ4_compress(const char *source, char *dest, int isize, int osize)
920afc2ba1Toomas Soome{
921afc2ba1Toomas Soome#if HEAPMODE
92210ae99eToomas Soome#if defined(_KERNEL) || defined(_FAKE_KERNEL)
92310ae99eToomas Soome	void *ctx = kmem_zalloc(sizeof (struct refTables), KM_NOSLEEP);
92410ae99eToomas Soome#else
925cab7c30Andy Fiddaman	void *ctx = calloc(1, sizeof (struct refTables));
92610ae99eToomas Soome#endif
927afc2ba1Toomas Soome	int result;
928afc2ba1Toomas Soome
929afc2ba1Toomas Soome	/*
930afc2ba1Toomas Soome	 * out of kernel memory, gently fall through - this will disable
931afc2ba1Toomas Soome	 * compression in zio_compress_data
932afc2ba1Toomas Soome	 */
933afc2ba1Toomas Soome	if (ctx == NULL)
934afc2ba1Toomas Soome		return (0);
935afc2ba1Toomas Soome
936afc2ba1Toomas Soome	if (isize < LZ4_64KLIMIT)
937afc2ba1Toomas Soome		result = LZ4_compress64kCtx(ctx, source, dest, isize, osize);
938afc2ba1Toomas Soome	else
939afc2ba1Toomas Soome		result = LZ4_compressCtx(ctx, source, dest, isize, osize);
940afc2ba1Toomas Soome
94110ae99eToomas Soome#if defined(_KERNEL) || defined(_FAKE_KERNEL)
94210ae99eToomas Soome	kmem_free(ctx, sizeof (struct refTables));
94310ae99eToomas Soome#else
94410ae99eToomas Soome	free(ctx);
94510ae99eToomas Soome#endif
946afc2ba1Toomas Soome	return (result);
947afc2ba1Toomas Soome#else
948afc2ba1Toomas Soome	if (isize < (int)LZ4_64KLIMIT)
949afc2ba1Toomas Soome		return (LZ4_compress64kCtx(NULL, source, dest, isize, osize));
950afc2ba1Toomas Soome	return (LZ4_compressCtx(NULL, source, dest, isize, osize));
951afc2ba1Toomas Soome#endif
952afc2ba1Toomas Soome}
953afc2ba1Toomas Soome
954afc2ba1Toomas Soome/* Decompression functions */
955afc2ba1Toomas Soome
956afc2ba1Toomas Soome/*
957afc2ba1Toomas Soome * Note: The decoding function LZ4_uncompress_unknownOutputSize() is safe
95810ae99eToomas Soome *	against "buffer overflow" attack type. It will never write nor
95910ae99eToomas Soome *	read outside of the provided output buffers.
96010ae99eToomas Soome *	LZ4_uncompress_unknownOutputSize() also insures that
96110ae99eToomas Soome *	it will never read outside of the input buffer. A corrupted input
96210ae99eToomas Soome *	will produce an error result, a negative int, indicating the position
96310ae99eToomas Soome *	of the error within input stream.
964afc2ba1Toomas Soome */
965afc2ba1Toomas Soome
966afc2ba1Toomas Soomestatic int
967afc2ba1Toomas SoomeLZ4_uncompress_unknownOutputSize(const char *source, char *dest, int isize,
968afc2ba1Toomas Soome    int maxOutputSize)
969afc2ba1Toomas Soome{
970afc2ba1Toomas Soome	/* Local Variables */
971afc2ba1Toomas Soome	const BYTE *restrict ip = (const BYTE *) source;
972afc2ba1Toomas Soome	const BYTE *const iend = ip + isize;
973afc2ba1Toomas Soome	const BYTE *ref;
974afc2ba1Toomas Soome
975afc2ba1Toomas Soome	BYTE *op = (BYTE *) dest;
976afc2ba1Toomas Soome	BYTE *const oend = op + maxOutputSize;
977afc2ba1Toomas Soome	BYTE *cpy;
978afc2ba1Toomas Soome
979afc2ba1Toomas Soome	size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
980afc2ba1Toomas Soome#if LZ4_ARCH64
981afc2ba1Toomas Soome	size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};
982afc2ba1Toomas Soome#endif
983afc2ba1Toomas Soome
984afc2ba1Toomas Soome	/* Main Loop */
985afc2ba1Toomas Soome	while (ip < iend) {
986afc2ba1Toomas Soome		unsigned token;
987afc2ba1Toomas Soome		size_t length;
988afc2ba1Toomas Soome
989afc2ba1Toomas Soome		/* get runlength */
990afc2ba1Toomas Soome		token = *ip++;
991afc2ba1Toomas Soome		if ((length = (token >> ML_BITS)) == RUN_MASK) {
992afc2ba1Toomas Soome			int s = 255;
993afc2ba1Toomas Soome			while ((ip < iend) && (s == 255)) {
994afc2ba1Toomas Soome				s = *ip++;
995afc2ba1Toomas Soome				length += s;
996afc2ba1Toomas Soome			}
997afc2ba1Toomas Soome		}
998afc2ba1Toomas Soome		/* copy literals */
999afc2ba1Toomas Soome		cpy = op + length;
1000afc2ba1Toomas Soome		/* CORNER-CASE: cpy might overflow. */
1001afc2ba1Toomas Soome		if (cpy < op)
1002afc2ba1Toomas Soome			goto _output_error;	/* cpy was overflowed, bail! */
1003afc2ba1Toomas Soome		if ((cpy > oend - COPYLENGTH) ||
1004afc2ba1Toomas Soome		    (ip + length > iend - COPYLENGTH)) {
1005afc2ba1Toomas Soome			if (cpy > oend)
1006afc2ba1Toomas Soome				/* Error: writes beyond output buffer */
1007afc2ba1Toomas Soome				goto _output_error;
1008afc2ba1Toomas Soome			if (ip + length != iend)
1009afc2ba1Toomas Soome				/*
1010afc2ba1Toomas Soome				 * Error: LZ4 format requires to consume all
1011afc2ba1Toomas Soome				 * input at this stage
1012afc2ba1Toomas Soome				 */
1013afc2ba1Toomas Soome				goto _output_error;
1014afc2ba1Toomas Soome			(void) memcpy(op, ip, length);
1015afc2ba1Toomas Soome			op += length;
1016afc2ba1Toomas Soome			/* Necessarily EOF, due to parsing restrictions */
1017afc2ba1Toomas Soome			break;
1018afc2ba1Toomas Soome		}
1019afc2ba1Toomas Soome		LZ4_WILDCOPY(ip, op, cpy);
1020afc2ba1Toomas Soome		ip -= (op - cpy);
1021afc2ba1Toomas Soome		op = cpy;
1022afc2ba1Toomas Soome
1023afc2ba1Toomas Soome		/* get offset */
1024afc2ba1Toomas Soome		LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
1025afc2ba1Toomas Soome		ip += 2;
1026afc2ba1Toomas Soome		if (ref < (BYTE * const) dest)
1027afc2ba1Toomas Soome			/*
1028afc2ba1Toomas Soome			 * Error: offset creates reference outside of
1029afc2ba1Toomas Soome			 * destination buffer
1030afc2ba1Toomas Soome			 */
1031afc2ba1Toomas Soome			goto _output_error;
1032afc2ba1Toomas Soome
1033afc2ba1Toomas Soome		/* get matchlength */
1034afc2ba1Toomas Soome		if ((length = (token & ML_MASK)) == ML_MASK) {
1035afc2ba1Toomas Soome			while (ip < iend) {
1036afc2ba1Toomas Soome				int s = *ip++;
1037afc2ba1Toomas Soome				length += s;
1038afc2ba1Toomas Soome				if (s == 255)
1039afc2ba1Toomas Soome					continue;
1040afc2ba1Toomas Soome				break;
1041afc2ba1Toomas Soome			}
1042afc2ba1Toomas Soome		}
1043afc2ba1Toomas Soome		/* copy repeated sequence */
1044afc2ba1Toomas Soome		if unlikely(op - ref < STEPSIZE) {
1045afc2ba1Toomas Soome#if LZ4_ARCH64
1046afc2ba1Toomas Soome			size_t dec64 = dec64table[op-ref];
1047afc2ba1Toomas Soome#else
1048afc2ba1Toomas Soome			const int dec64 = 0;
1049afc2ba1Toomas Soome#endif
1050afc2ba1Toomas Soome			op[0] = ref[0];
1051afc2ba1Toomas Soome			op[1] = ref[1];
1052afc2ba1Toomas Soome			op[2] = ref[2];
1053afc2ba1Toomas Soome			op[3] = ref[3];
1054afc2ba1Toomas Soome			op += 4;
1055afc2ba1Toomas Soome			ref += 4;
1056afc2ba1Toomas Soome			ref -= dec32table[op-ref];
1057afc2ba1Toomas Soome			A32(op) = A32(ref);
1058afc2ba1Toomas Soome			op += STEPSIZE - 4;
1059afc2ba1Toomas Soome			ref -= dec64;
1060afc2ba1Toomas Soome		} else {
1061afc2ba1Toomas Soome			LZ4_COPYSTEP(ref, op);
1062afc2ba1Toomas Soome		}
1063afc2ba1Toomas Soome		cpy = op + length - (STEPSIZE - 4);
1064afc2ba1Toomas Soome		if (cpy > oend - COPYLENGTH) {
1065afc2ba1Toomas Soome			if (cpy > oend)
1066afc2ba1Toomas Soome				/*
1067afc2ba1Toomas Soome				 * Error: request to write outside of
1068afc2ba1Toomas Soome				 * destination buffer
1069afc2ba1Toomas Soome				 */
1070afc2ba1Toomas Soome				goto _output_error;
1071afc2ba1Toomas Soome			LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
1072afc2ba1Toomas Soome			while (op < cpy)
1073afc2ba1Toomas Soome				*op++ = *ref++;
1074afc2ba1Toomas Soome			op = cpy;
1075afc2ba1Toomas Soome			if (op == oend)
1076afc2ba1Toomas Soome				/*
1077afc2ba1Toomas Soome				 * Check EOF (should never happen, since
1078afc2ba1Toomas Soome				 * last 5 bytes are supposed to be literals)
1079afc2ba1Toomas Soome				 */
1080afc2ba1Toomas Soome				goto _output_error;
1081afc2ba1Toomas Soome			continue;
1082afc2ba1Toomas Soome		}
1083afc2ba1Toomas Soome		LZ4_SECURECOPY(ref, op, cpy);
1084afc2ba1Toomas Soome		op = cpy;	/* correction */
1085afc2ba1Toomas Soome	}
1086afc2ba1Toomas Soome
1087afc2ba1Toomas Soome	/* end of decoding */
1088afc2ba1Toomas Soome	return (int)(((char *)op) - dest);
1089afc2ba1Toomas Soome
1090afc2ba1Toomas Soome	/* write overflow error detected */
1091afc2ba1Toomas Soome	_output_error:
109210ae99eToomas Soome	return (int)(-(((const char *)ip) - source));
1093afc2ba1Toomas Soome}
1094