1 /*
2 LZ4 - Fast LZ compression algorithm
3 Copyright (C) 2011-2014, Yann Collet.
4 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
5
6 Redistribution and use in source and binary forms, with or without
7 modification, are permitted provided that the following conditions are
8 met:
9
10 * Redistributions of source code must retain the above copyright
11 notice, this list of conditions and the following disclaimer.
12 * Redistributions in binary form must reproduce the above
13 copyright notice, this list of conditions and the following disclaimer
14 in the documentation and/or other materials provided with the
15 distribution.
16
17 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28
29 You can contact the author at :
30 - LZ4 source repository : http://code.google.com/p/lz4/
31 - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c
32 */
33
34 /**************************************
35 Tuning parameters
36 **************************************/
37 /*
38 * MEMORY_USAGE :
39 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
40 * Increasing memory usage improves compression ratio
41 * Reduced memory usage can improve speed, due to cache effect
42 * Default value is 14, for 16KB, which nicely fits into Intel x86 L1 cache
43 */
44 #define MEMORY_USAGE 14
45
46 /*
47 * HEAPMODE :
48 * Select how default compression functions will allocate memory for their hash table,
49 * in memory stack (0:default, fastest), or in memory heap (1:requires memory allocation (malloc)).
50 */
51 #define HEAPMODE 0
52
53
54 /**************************************
55 CPU Feature Detection
56 **************************************/
57 /* 32 or 64 bits ? */
58 #if (defined(__x86_64__) || defined(_M_X64) || defined(_WIN64) \
59 || defined(__powerpc64__) || defined(__ppc64__) || defined(__PPC64__) \
60 || defined(__64BIT__) || defined(_LP64) || defined(__LP64__) \
61 || defined(__ia64) || defined(__itanium__) || defined(_M_IA64) ) /* Detects 64 bits mode */
62 # define LZ4_ARCH64 1
63 #else
64 # define LZ4_ARCH64 0
65 #endif
66
67 /*
68 * Little Endian or Big Endian ?
69 * Overwrite the #define below if you know your architecture endianess
70 */
71 #if defined (__GLIBC__)
72 # include <endian.h>
73 # if (__BYTE_ORDER == __BIG_ENDIAN)
74 # define LZ4_BIG_ENDIAN 1
75 # endif
76 #elif (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN)) && !(defined(__LITTLE_ENDIAN__) || defined(__LITTLE_ENDIAN) || defined(_LITTLE_ENDIAN))
77 # define LZ4_BIG_ENDIAN 1
78 #elif defined(__sparc) || defined(__sparc__) \
79 || defined(__powerpc__) || defined(__ppc__) || defined(__PPC__) \
80 || defined(__hpux) || defined(__hppa) \
81 || defined(_MIPSEB) || defined(__s390__)
82 # define LZ4_BIG_ENDIAN 1
83 #else
84 /* Little Endian assumed. PDP Endian and other very rare endian format are unsupported. */
85 #endif
86
87 /*
88 * Unaligned memory access is automatically enabled for "common" CPU, such as x86.
89 * For others CPU, such as ARM, the compiler may be more cautious, inserting unnecessary extra code to ensure aligned access property
90 * If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance
91 */
92 #if defined(__ARM_FEATURE_UNALIGNED)
93 # define LZ4_FORCE_UNALIGNED_ACCESS 1
94 #endif
95
96 /* Define this parameter if your target system or compiler does not support hardware bit count */
97 #if defined(_MSC_VER) && defined(_WIN32_WCE) /* Visual Studio for Windows CE does not support Hardware bit count */
98 # define LZ4_FORCE_SW_BITCOUNT
99 #endif
100
101 /*
102 * BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE :
103 * This option may provide a small boost to performance for some big endian cpu, although probably modest.
104 * You may set this option to 1 if data will remain within closed environment.
105 * This option is useless on Little_Endian CPU (such as x86)
106 */
107
108 /* #define BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE 1 */
109
110
111 /**************************************
112 Compiler Options
113 **************************************/
114 #if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */
115 /* "restrict" is a known keyword */
116 #else
117 # define restrict /* Disable restrict */
118 #endif
119
120 #ifdef _MSC_VER /* Visual Studio */
121 # define FORCE_INLINE static __forceinline
122 # include <intrin.h> /* For Visual 2005 */
123 # if LZ4_ARCH64 /* 64-bits */
124 # pragma intrinsic(_BitScanForward64) /* For Visual 2005 */
125 # pragma intrinsic(_BitScanReverse64) /* For Visual 2005 */
126 # else /* 32-bits */
127 # pragma intrinsic(_BitScanForward) /* For Visual 2005 */
128 # pragma intrinsic(_BitScanReverse) /* For Visual 2005 */
129 # endif
130 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
131 #else
132 # ifdef __GNUC__
133 # define FORCE_INLINE static inline __attribute__((always_inline))
134 # else
135 # define FORCE_INLINE static inline
136 # endif
137 #endif
138
139 #ifdef _MSC_VER /* Visual Studio */
140 # define lz4_bswap16(x) _byteswap_ushort(x)
141 #else
142 # define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8)))
143 #endif
144
145 #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
146
147 #if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__)
148 # define expect(expr,value) (__builtin_expect ((expr),(value)) )
149 #else
150 # define expect(expr,value) (expr)
151 #endif
152
153 #define likely(expr) expect((expr) != 0, 1)
154 #define unlikely(expr) expect((expr) != 0, 0)
155
156
157 /**************************************
158 Memory routines
159 **************************************/
160 #include <stdlib.h> /* malloc, calloc, free */
161 #define ALLOCATOR(n,s) calloc(n,s)
162 #define FREEMEM free
163 #include <string.h> /* memset, memcpy */
164 #define MEM_INIT memset
165
166
167 /**************************************
168 Includes
169 **************************************/
170 #include "lz4.h"
171
172
173 /**************************************
174 Basic Types
175 **************************************/
176 #if defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */
177 # include <stdint.h>
178 typedef uint8_t BYTE;
179 typedef uint16_t U16;
180 typedef uint32_t U32;
181 typedef int32_t S32;
182 typedef uint64_t U64;
183 #else
184 typedef unsigned char BYTE;
185 typedef unsigned short U16;
186 typedef unsigned int U32;
187 typedef signed int S32;
188 typedef unsigned long long U64;
189 #endif
190
191 #if defined(__GNUC__) && !defined(LZ4_FORCE_UNALIGNED_ACCESS)
192 # define _PACKED __attribute__ ((packed))
193 #else
194 # define _PACKED
195 #endif
196
197 #if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__)
198 # if defined(__IBMC__) || defined(__SUNPRO_C) || defined(__SUNPRO_CC)
199 # pragma pack(1)
200 # else
201 # pragma pack(push, 1)
202 # endif
203 #endif
204
205 typedef struct { U16 v; } _PACKED U16_S;
206 typedef struct { U32 v; } _PACKED U32_S;
207 typedef struct { U64 v; } _PACKED U64_S;
208 typedef struct {size_t v;} _PACKED size_t_S;
209
210 #if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__)
211 # if defined(__SUNPRO_C) || defined(__SUNPRO_CC)
212 # pragma pack(0)
213 # else
214 # pragma pack(pop)
215 # endif
216 #endif
217
218 #define A16(x) (((U16_S *)(x))->v)
219 #define A32(x) (((U32_S *)(x))->v)
220 #define A64(x) (((U64_S *)(x))->v)
221 #define AARCH(x) (((size_t_S *)(x))->v)
222
223
224 /**************************************
225 Constants
226 **************************************/
227 #define LZ4_HASHLOG (MEMORY_USAGE-2)
228 #define HASHTABLESIZE (1 << MEMORY_USAGE)
229 #define HASHNBCELLS4 (1 << LZ4_HASHLOG)
230
231 #define MINMATCH 4
232
233 #define COPYLENGTH 8
234 #define LASTLITERALS 5
235 #define MFLIMIT (COPYLENGTH+MINMATCH)
236 static const int LZ4_minLength = (MFLIMIT+1);
237
238 #define KB *(1U<<10)
239 #define MB *(1U<<20)
240 #define GB *(1U<<30)
241
242 #define LZ4_64KLIMIT ((64 KB) + (MFLIMIT-1))
243 #define SKIPSTRENGTH 6 /* Increasing this value will make the compression run slower on incompressible data */
244
245 #define MAXD_LOG 16
246 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
247
248 #define ML_BITS 4
249 #define ML_MASK ((1U<<ML_BITS)-1)
250 #define RUN_BITS (8-ML_BITS)
251 #define RUN_MASK ((1U<<RUN_BITS)-1)
252
253
254 /**************************************
255 Structures and local types
256 **************************************/
257 typedef struct {
258 U32 hashTable[HASHNBCELLS4];
259 const BYTE* bufferStart;
260 const BYTE* base;
261 const BYTE* nextBlock;
262 } LZ4_Data_Structure;
263
264 typedef enum { notLimited = 0, limited = 1 } limitedOutput_directive;
265 typedef enum { byPtr, byU32, byU16 } tableType_t;
266
267 typedef enum { noPrefix = 0, withPrefix = 1 } prefix64k_directive;
268
269 typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;
270 typedef enum { full = 0, partial = 1 } earlyEnd_directive;
271
272
273 /**************************************
274 Architecture-specific macros
275 **************************************/
276 #define STEPSIZE sizeof(size_t)
277 #define LZ4_COPYSTEP(d,s) { AARCH(d) = AARCH(s); d+=STEPSIZE; s+=STEPSIZE; }
278 #define LZ4_COPY8(d,s) { LZ4_COPYSTEP(d,s); if (STEPSIZE<8) LZ4_COPYSTEP(d,s); }
279
280 #if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE))
281 # define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; }
282 # define LZ4_WRITE_LITTLEENDIAN_16(p,i) { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p+=2; }
283 #else /* Little Endian */
284 # define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); }
285 # define LZ4_WRITE_LITTLEENDIAN_16(p,v) { A16(p) = v; p+=2; }
286 #endif
287
288
289 /**************************************
290 Macros
291 **************************************/
292 #if LZ4_ARCH64 || !defined(__GNUC__)
293 # define LZ4_WILDCOPY(d,s,e) { do { LZ4_COPY8(d,s) } while (d<e); } /* at the end, d>=e; */
294 #else
295 # define LZ4_WILDCOPY(d,s,e) { if (likely(e-d <= 8)) LZ4_COPY8(d,s) else do { LZ4_COPY8(d,s) } while (d<e); }
296 #endif
297 #define LZ4_SECURECOPY(d,s,e) { if (d<e) LZ4_WILDCOPY(d,s,e); }
298
299
300 /****************************
301 Private local functions
302 ****************************/
303 #if LZ4_ARCH64
304
LZ4_NbCommonBytes(register U64 val)305 FORCE_INLINE int LZ4_NbCommonBytes (register U64 val)
306 {
307 # if defined(LZ4_BIG_ENDIAN)
308 # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
309 unsigned long r = 0;
310 _BitScanReverse64( &r, val );
311 return (int)(r>>3);
312 # elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
313 return (__builtin_clzll(val) >> 3);
314 # else
315 int r;
316 if (!(val>>32)) { r=4; } else { r=0; val>>=32; }
317 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
318 r += (!val);
319 return r;
320 # endif
321 # else
322 # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
323 unsigned long r = 0;
324 _BitScanForward64( &r, val );
325 return (int)(r>>3);
326 # elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
327 return (__builtin_ctzll(val) >> 3);
328 # else
329 static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5, 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 4, 5, 7, 2, 6, 5, 7, 6, 7, 7 };
330 return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
331 # endif
332 # endif
333 }
334
335 #else
336
LZ4_NbCommonBytes(register U32 val)337 FORCE_INLINE int LZ4_NbCommonBytes (register U32 val)
338 {
339 # if defined(LZ4_BIG_ENDIAN)
340 # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
341 unsigned long r = 0;
342 _BitScanReverse( &r, val );
343 return (int)(r>>3);
344 # elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
345 return (__builtin_clz(val) >> 3);
346 # else
347 int r;
348 if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
349 r += (!val);
350 return r;
351 # endif
352 # else
353 # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
354 unsigned long r;
355 _BitScanForward( &r, val );
356 return (int)(r>>3);
357 # elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
358 return (__builtin_ctz(val) >> 3);
359 # else
360 static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 };
361 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
362 # endif
363 # endif
364 }
365
366 #endif
367
368
369 /****************************
370 Compression functions
371 ****************************/
LZ4_compressBound(int isize)372 int LZ4_compressBound(int isize) { return LZ4_COMPRESSBOUND(isize); }
373
LZ4_hashSequence(U32 sequence,tableType_t tableType)374 FORCE_INLINE int LZ4_hashSequence(U32 sequence, tableType_t tableType)
375 {
376 if (tableType == byU16)
377 return (((sequence) * 2654435761U) >> ((MINMATCH*8)-(LZ4_HASHLOG+1)));
378 else
379 return (((sequence) * 2654435761U) >> ((MINMATCH*8)-LZ4_HASHLOG));
380 }
381
LZ4_hashPosition(const BYTE * p,tableType_t tableType)382 FORCE_INLINE int LZ4_hashPosition(const BYTE* p, tableType_t tableType) { return LZ4_hashSequence(A32(p), tableType); }
383
LZ4_putPositionOnHash(const BYTE * p,U32 h,void * tableBase,tableType_t tableType,const BYTE * srcBase)384 FORCE_INLINE void LZ4_putPositionOnHash(const BYTE* p, U32 h, void* tableBase, tableType_t tableType, const BYTE* srcBase)
385 {
386 switch (tableType)
387 {
388 case byPtr: { const BYTE** hashTable = (const BYTE**) tableBase; hashTable[h] = p; break; }
389 case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = (U32)(p-srcBase); break; }
390 case byU16: { U16* hashTable = (U16*) tableBase; hashTable[h] = (U16)(p-srcBase); break; }
391 }
392 }
393
LZ4_putPosition(const BYTE * p,void * tableBase,tableType_t tableType,const BYTE * srcBase)394 FORCE_INLINE void LZ4_putPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase)
395 {
396 U32 h = LZ4_hashPosition(p, tableType);
397 LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase);
398 }
399
LZ4_getPositionOnHash(U32 h,void * tableBase,tableType_t tableType,const BYTE * srcBase)400 FORCE_INLINE const BYTE* LZ4_getPositionOnHash(U32 h, void* tableBase, tableType_t tableType, const BYTE* srcBase)
401 {
402 if (tableType == byPtr) { const BYTE** hashTable = (const BYTE**) tableBase; return hashTable[h]; }
403 if (tableType == byU32) { U32* hashTable = (U32*) tableBase; return hashTable[h] + srcBase; }
404 { U16* hashTable = (U16*) tableBase; return hashTable[h] + srcBase; } /* default, to ensure a return */
405 }
406
LZ4_getPosition(const BYTE * p,void * tableBase,tableType_t tableType,const BYTE * srcBase)407 FORCE_INLINE const BYTE* LZ4_getPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase)
408 {
409 U32 h = LZ4_hashPosition(p, tableType);
410 return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase);
411 }
412
413
LZ4_compress_generic(void * ctx,const char * source,char * dest,int inputSize,int maxOutputSize,limitedOutput_directive limitedOutput,tableType_t tableType,prefix64k_directive prefix)414 FORCE_INLINE int LZ4_compress_generic(
415 void* ctx,
416 const char* source,
417 char* dest,
418 int inputSize,
419 int maxOutputSize,
420
421 limitedOutput_directive limitedOutput,
422 tableType_t tableType,
423 prefix64k_directive prefix)
424 {
425 const BYTE* ip = (const BYTE*) source;
426 const BYTE* const base = (prefix==withPrefix) ? ((LZ4_Data_Structure*)ctx)->base : (const BYTE*) source;
427 const BYTE* const lowLimit = ((prefix==withPrefix) ? ((LZ4_Data_Structure*)ctx)->bufferStart : (const BYTE*)source);
428 const BYTE* anchor = (const BYTE*) source;
429 const BYTE* const iend = ip + inputSize;
430 const BYTE* const mflimit = iend - MFLIMIT;
431 const BYTE* const matchlimit = iend - LASTLITERALS;
432
433 BYTE* op = (BYTE*) dest;
434 BYTE* const oend = op + maxOutputSize;
435
436 int length;
437 const int skipStrength = SKIPSTRENGTH;
438 U32 forwardH;
439
440 /* Init conditions */
441 if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported input size, too large (or negative) */
442 if ((prefix==withPrefix) && (ip != ((LZ4_Data_Structure*)ctx)->nextBlock)) return 0; /* must continue from end of previous block */
443 if (prefix==withPrefix) ((LZ4_Data_Structure*)ctx)->nextBlock=iend; /* do it now, due to potential early exit */
444 if ((tableType == byU16) && (inputSize>=(int)LZ4_64KLIMIT)) return 0; /* Size too large (not within 64K limit) */
445 if (inputSize<LZ4_minLength) goto _last_literals; /* Input too small, no compression (all literals) */
446
447 /* First Byte */
448 LZ4_putPosition(ip, ctx, tableType, base);
449 ip++; forwardH = LZ4_hashPosition(ip, tableType);
450
451 /* Main Loop */
452 for ( ; ; )
453 {
454 int findMatchAttempts = (1U << skipStrength) + 3;
455 const BYTE* forwardIp = ip;
456 const BYTE* ref;
457 BYTE* token;
458
459 /* Find a match */
460 do {
461 U32 h = forwardH;
462 int step = findMatchAttempts++ >> skipStrength;
463 ip = forwardIp;
464 forwardIp = ip + step;
465
466 if (unlikely(forwardIp > mflimit)) { goto _last_literals; }
467
468 forwardH = LZ4_hashPosition(forwardIp, tableType);
469 ref = LZ4_getPositionOnHash(h, ctx, tableType, base);
470 LZ4_putPositionOnHash(ip, h, ctx, tableType, base);
471
472 } while ((ref + MAX_DISTANCE < ip) || (A32(ref) != A32(ip)));
473
474 /* Catch up */
475 while ((ip>anchor) && (ref > lowLimit) && (unlikely(ip[-1]==ref[-1]))) { ip--; ref--; }
476
477 /* Encode Literal length */
478 length = (int)(ip - anchor);
479 token = op++;
480 if ((limitedOutput) && (unlikely(op + length + (2 + 1 + LASTLITERALS) + (length/255) > oend))) return 0; /* Check output limit */
481 if (length>=(int)RUN_MASK)
482 {
483 int len = length-RUN_MASK;
484 *token=(RUN_MASK<<ML_BITS);
485 for(; len >= 255 ; len-=255) *op++ = 255;
486 *op++ = (BYTE)len;
487 }
488 else *token = (BYTE)(length<<ML_BITS);
489
490 /* Copy Literals */
491 { BYTE* end=(op)+(length); LZ4_WILDCOPY(op,anchor,end); op=end; }
492
493 _next_match:
494 /* Encode Offset */
495 LZ4_WRITE_LITTLEENDIAN_16(op,(U16)(ip-ref));
496
497 /* Start Counting */
498 ip+=MINMATCH; ref+=MINMATCH; /* MinMatch already verified */
499 anchor = ip;
500 while (likely(ip<matchlimit-(STEPSIZE-1)))
501 {
502 size_t diff = AARCH(ref) ^ AARCH(ip);
503 if (!diff) { ip+=STEPSIZE; ref+=STEPSIZE; continue; }
504 ip += LZ4_NbCommonBytes(diff);
505 goto _endCount;
506 }
507 if (LZ4_ARCH64) if ((ip<(matchlimit-3)) && (A32(ref) == A32(ip))) { ip+=4; ref+=4; }
508 if ((ip<(matchlimit-1)) && (A16(ref) == A16(ip))) { ip+=2; ref+=2; }
509 if ((ip<matchlimit) && (*ref == *ip)) ip++;
510 _endCount:
511
512 /* Encode MatchLength */
513 length = (int)(ip - anchor);
514 if ((limitedOutput) && (unlikely(op + (1 + LASTLITERALS) + (length>>8) > oend))) return 0; /* Check output limit */
515 if (length>=(int)ML_MASK)
516 {
517 *token += ML_MASK;
518 length -= ML_MASK;
519 for (; length > 509 ; length-=510) { *op++ = 255; *op++ = 255; }
520 if (length >= 255) { length-=255; *op++ = 255; }
521 *op++ = (BYTE)length;
522 }
523 else *token += (BYTE)(length);
524
525 /* Test end of chunk */
526 if (ip > mflimit) { anchor = ip; break; }
527
528 /* Fill table */
529 LZ4_putPosition(ip-2, ctx, tableType, base);
530
531 /* Test next position */
532 ref = LZ4_getPosition(ip, ctx, tableType, base);
533 LZ4_putPosition(ip, ctx, tableType, base);
534 if ((ref + MAX_DISTANCE >= ip) && (A32(ref) == A32(ip))) { token = op++; *token=0; goto _next_match; }
535
536 /* Prepare next loop */
537 anchor = ip++;
538 forwardH = LZ4_hashPosition(ip, tableType);
539 }
540
541 _last_literals:
542 /* Encode Last Literals */
543 {
544 int lastRun = (int)(iend - anchor);
545 if ((limitedOutput) && (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize)) return 0; /* Check output limit */
546 if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun >= 255 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }
547 else *op++ = (BYTE)(lastRun<<ML_BITS);
548 memcpy(op, anchor, iend - anchor);
549 op += iend-anchor;
550 }
551
552 /* End */
553 return (int) (((char*)op)-dest);
554 }
555
556
LZ4_compress(const char * source,char * dest,int inputSize)557 int LZ4_compress(const char* source, char* dest, int inputSize)
558 {
559 #if (HEAPMODE)
560 void* ctx = ALLOCATOR(HASHNBCELLS4, 4); /* Aligned on 4-bytes boundaries */
561 #else
562 U32 ctx[1U<<(MEMORY_USAGE-2)] = {0}; /* Ensure data is aligned on 4-bytes boundaries */
563 #endif
564 int result;
565
566 if (inputSize < (int)LZ4_64KLIMIT)
567 result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, 0, notLimited, byU16, noPrefix);
568 else
569 result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, 0, notLimited, (sizeof(void*)==8) ? byU32 : byPtr, noPrefix);
570
571 #if (HEAPMODE)
572 FREEMEM(ctx);
573 #endif
574 return result;
575 }
576
LZ4_compress_limitedOutput(const char * source,char * dest,int inputSize,int maxOutputSize)577 int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize)
578 {
579 #if (HEAPMODE)
580 void* ctx = ALLOCATOR(HASHNBCELLS4, 4); /* Aligned on 4-bytes boundaries */
581 #else
582 U32 ctx[1U<<(MEMORY_USAGE-2)] = {0}; /* Ensure data is aligned on 4-bytes boundaries */
583 #endif
584 int result;
585
586 if (inputSize < (int)LZ4_64KLIMIT)
587 result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, maxOutputSize, limited, byU16, noPrefix);
588 else
589 result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, maxOutputSize, limited, (sizeof(void*)==8) ? byU32 : byPtr, noPrefix);
590
591 #if (HEAPMODE)
592 FREEMEM(ctx);
593 #endif
594 return result;
595 }
596
597
598 /*****************************
599 Using external allocation
600 *****************************/
601
LZ4_sizeofState()602 int LZ4_sizeofState() { return 1 << MEMORY_USAGE; }
603
604
LZ4_compress_withState(void * state,const char * source,char * dest,int inputSize)605 int LZ4_compress_withState (void* state, const char* source, char* dest, int inputSize)
606 {
607 if (((size_t)(state)&3) != 0) return 0; /* Error : state is not aligned on 4-bytes boundary */
608 MEM_INIT(state, 0, LZ4_sizeofState());
609
610 if (inputSize < (int)LZ4_64KLIMIT)
611 return LZ4_compress_generic(state, source, dest, inputSize, 0, notLimited, byU16, noPrefix);
612 else
613 return LZ4_compress_generic(state, source, dest, inputSize, 0, notLimited, (sizeof(void*)==8) ? byU32 : byPtr, noPrefix);
614 }
615
616
LZ4_compress_limitedOutput_withState(void * state,const char * source,char * dest,int inputSize,int maxOutputSize)617 int LZ4_compress_limitedOutput_withState (void* state, const char* source, char* dest, int inputSize, int maxOutputSize)
618 {
619 if (((size_t)(state)&3) != 0) return 0; /* Error : state is not aligned on 4-bytes boundary */
620 MEM_INIT(state, 0, LZ4_sizeofState());
621
622 if (inputSize < (int)LZ4_64KLIMIT)
623 return LZ4_compress_generic(state, source, dest, inputSize, maxOutputSize, limited, byU16, noPrefix);
624 else
625 return LZ4_compress_generic(state, source, dest, inputSize, maxOutputSize, limited, (sizeof(void*)==8) ? byU32 : byPtr, noPrefix);
626 }
627
628
629 /****************************
630 Stream functions
631 ****************************/
632
LZ4_sizeofStreamState()633 int LZ4_sizeofStreamState()
634 {
635 return sizeof(LZ4_Data_Structure);
636 }
637
LZ4_init(LZ4_Data_Structure * lz4ds,const BYTE * base)638 FORCE_INLINE void LZ4_init(LZ4_Data_Structure* lz4ds, const BYTE* base)
639 {
640 MEM_INIT(lz4ds->hashTable, 0, sizeof(lz4ds->hashTable));
641 lz4ds->bufferStart = base;
642 lz4ds->base = base;
643 lz4ds->nextBlock = base;
644 }
645
LZ4_resetStreamState(void * state,const char * inputBuffer)646 int LZ4_resetStreamState(void* state, const char* inputBuffer)
647 {
648 if ((((size_t)state) & 3) != 0) return 1; /* Error : pointer is not aligned on 4-bytes boundary */
649 LZ4_init((LZ4_Data_Structure*)state, (const BYTE*)inputBuffer);
650 return 0;
651 }
652
LZ4_create(const char * inputBuffer)653 void* LZ4_create (const char* inputBuffer)
654 {
655 void* lz4ds = ALLOCATOR(1, sizeof(LZ4_Data_Structure));
656 LZ4_init ((LZ4_Data_Structure*)lz4ds, (const BYTE*)inputBuffer);
657 return lz4ds;
658 }
659
660
LZ4_free(void * LZ4_Data)661 int LZ4_free (void* LZ4_Data)
662 {
663 FREEMEM(LZ4_Data);
664 return (0);
665 }
666
667
LZ4_slideInputBuffer(void * LZ4_Data)668 char* LZ4_slideInputBuffer (void* LZ4_Data)
669 {
670 LZ4_Data_Structure* lz4ds = (LZ4_Data_Structure*)LZ4_Data;
671 size_t delta = lz4ds->nextBlock - (lz4ds->bufferStart + 64 KB);
672
673 if ( (lz4ds->base - delta > lz4ds->base) /* underflow control */
674 || ((size_t)(lz4ds->nextBlock - lz4ds->base) > 0xE0000000) ) /* close to 32-bits limit */
675 {
676 size_t deltaLimit = (lz4ds->nextBlock - 64 KB) - lz4ds->base;
677 int nH;
678
679 for (nH=0; nH < HASHNBCELLS4; nH++)
680 {
681 if ((size_t)(lz4ds->hashTable[nH]) < deltaLimit) lz4ds->hashTable[nH] = 0;
682 else lz4ds->hashTable[nH] -= (U32)deltaLimit;
683 }
684 memcpy((void*)(lz4ds->bufferStart), (const void*)(lz4ds->nextBlock - 64 KB), 64 KB);
685 lz4ds->base = lz4ds->bufferStart;
686 lz4ds->nextBlock = lz4ds->base + 64 KB;
687 }
688 else
689 {
690 memcpy((void*)(lz4ds->bufferStart), (const void*)(lz4ds->nextBlock - 64 KB), 64 KB);
691 lz4ds->nextBlock -= delta;
692 lz4ds->base -= delta;
693 }
694
695 return (char*)(lz4ds->nextBlock);
696 }
697
698
LZ4_compress_continue(void * LZ4_Data,const char * source,char * dest,int inputSize)699 int LZ4_compress_continue (void* LZ4_Data, const char* source, char* dest, int inputSize)
700 {
701 return LZ4_compress_generic(LZ4_Data, source, dest, inputSize, 0, notLimited, byU32, withPrefix);
702 }
703
704
LZ4_compress_limitedOutput_continue(void * LZ4_Data,const char * source,char * dest,int inputSize,int maxOutputSize)705 int LZ4_compress_limitedOutput_continue (void* LZ4_Data, const char* source, char* dest, int inputSize, int maxOutputSize)
706 {
707 return LZ4_compress_generic(LZ4_Data, source, dest, inputSize, maxOutputSize, limited, byU32, withPrefix);
708 }
709
710
711 /****************************
712 Decompression functions
713 ****************************/
714 /*
715 * This generic decompression function cover all use cases.
716 * It shall be instanciated several times, using different sets of directives
717 * Note that it is essential this generic function is really inlined,
718 * in order to remove useless branches during compilation optimisation.
719 */
LZ4_decompress_generic(const char * source,char * dest,int inputSize,int outputSize,int endOnInput,int prefix64k,int partialDecoding,int targetOutputSize)720 FORCE_INLINE int LZ4_decompress_generic(
721 const char* source,
722 char* dest,
723 int inputSize,
724 int outputSize, /* If endOnInput==endOnInputSize, this value is the max size of Output Buffer. */
725
726 int endOnInput, /* endOnOutputSize, endOnInputSize */
727 int prefix64k, /* noPrefix, withPrefix */
728 int partialDecoding, /* full, partial */
729 int targetOutputSize /* only used if partialDecoding==partial */
730 )
731 {
732 /* Local Variables */
733 const BYTE* restrict ip = (const BYTE*) source;
734 const BYTE* ref;
735 const BYTE* const iend = ip + inputSize;
736
737 BYTE* op = (BYTE*) dest;
738 BYTE* const oend = op + outputSize;
739 BYTE* cpy;
740 BYTE* oexit = op + targetOutputSize;
741
742 /*const size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0}; / static reduces speed for LZ4_decompress_safe() on GCC64 */
743 const size_t dec32table[] = {4-0, 4-3, 4-2, 4-3, 4-0, 4-0, 4-0, 4-0}; /* static reduces speed for LZ4_decompress_safe() on GCC64 */
744 static const size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};
745
746
747 /* Special cases */
748 if ((partialDecoding) && (oexit> oend-MFLIMIT)) oexit = oend-MFLIMIT; /* targetOutputSize too high => decode everything */
749 if ((endOnInput) && (unlikely(outputSize==0))) return ((inputSize==1) && (*ip==0)) ? 0 : -1; /* Empty output buffer */
750 if ((!endOnInput) && (unlikely(outputSize==0))) return (*ip==0?1:-1);
751
752
753 /* Main Loop */
754 while (1)
755 {
756 unsigned token;
757 size_t length;
758
759 /* get runlength */
760 token = *ip++;
761 if ((length=(token>>ML_BITS)) == RUN_MASK)
762 {
763 unsigned s=255;
764 while (((endOnInput)?ip<iend:1) && (s==255))
765 {
766 s = *ip++;
767 length += s;
768 }
769 }
770
771 /* copy literals */
772 cpy = op+length;
773 if (((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT)) || (ip+length>iend-(2+1+LASTLITERALS))) )
774 || ((!endOnInput) && (cpy>oend-COPYLENGTH)))
775 {
776 if (partialDecoding)
777 {
778 if (cpy > oend) goto _output_error; /* Error : write attempt beyond end of output buffer */
779 if ((endOnInput) && (ip+length > iend)) goto _output_error; /* Error : read attempt beyond end of input buffer */
780 }
781 else
782 {
783 if ((!endOnInput) && (cpy != oend)) goto _output_error; /* Error : block decoding must stop exactly there */
784 if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) goto _output_error; /* Error : input must be consumed */
785 }
786 memcpy(op, ip, length);
787 ip += length;
788 op += length;
789 break; /* Necessarily EOF, due to parsing restrictions */
790 }
791 LZ4_WILDCOPY(op, ip, cpy); ip -= (op-cpy); op = cpy;
792
793 /* get offset */
794 LZ4_READ_LITTLEENDIAN_16(ref,cpy,ip); ip+=2;
795 if ((prefix64k==noPrefix) && (unlikely(ref < (BYTE* const)dest))) goto _output_error; /* Error : offset outside destination buffer */
796
797 /* get matchlength */
798 if ((length=(token&ML_MASK)) == ML_MASK)
799 {
800 while ((!endOnInput) || (ip<iend-(LASTLITERALS+1))) /* Ensure enough bytes remain for LASTLITERALS + token */
801 {
802 unsigned s = *ip++;
803 length += s;
804 if (s==255) continue;
805 break;
806 }
807 }
808
809 /* copy repeated sequence */
810 if (unlikely((op-ref)<(int)STEPSIZE))
811 {
812 const size_t dec64 = dec64table[(sizeof(void*)==4) ? 0 : op-ref];
813 op[0] = ref[0];
814 op[1] = ref[1];
815 op[2] = ref[2];
816 op[3] = ref[3];
817 /*op += 4, ref += 4; ref -= dec32table[op-ref];
818 A32(op) = A32(ref);
819 op += STEPSIZE-4; ref -= dec64;*/
820 ref += dec32table[op-ref];
821 A32(op+4) = A32(ref);
822 op += STEPSIZE; ref -= dec64;
823 } else { LZ4_COPYSTEP(op,ref); }
824 cpy = op + length - (STEPSIZE-4);
825
826 if (unlikely(cpy>oend-COPYLENGTH-(STEPSIZE-4)))
827 {
828 if (cpy > oend-LASTLITERALS) goto _output_error; /* Error : last 5 bytes must be literals */
829 LZ4_SECURECOPY(op, ref, (oend-COPYLENGTH));
830 while(op<cpy) *op++=*ref++;
831 op=cpy;
832 continue;
833 }
834 LZ4_WILDCOPY(op, ref, cpy);
835 op=cpy; /* correction */
836 }
837
838 /* end of decoding */
839 if (endOnInput)
840 return (int) (((char*)op)-dest); /* Nb of output bytes decoded */
841 else
842 return (int) (((char*)ip)-source); /* Nb of input bytes read */
843
844 /* Overflow error detected */
845 _output_error:
846 return (int) (-(((char*)ip)-source))-1;
847 }
848
849
LZ4_decompress_safe(const char * source,char * dest,int inputSize,int maxOutputSize)850 int LZ4_decompress_safe(const char* source, char* dest, int inputSize, int maxOutputSize)
851 {
852 return LZ4_decompress_generic(source, dest, inputSize, maxOutputSize, endOnInputSize, noPrefix, full, 0);
853 }
854
LZ4_decompress_safe_withPrefix64k(const char * source,char * dest,int inputSize,int maxOutputSize)855 int LZ4_decompress_safe_withPrefix64k(const char* source, char* dest, int inputSize, int maxOutputSize)
856 {
857 return LZ4_decompress_generic(source, dest, inputSize, maxOutputSize, endOnInputSize, withPrefix, full, 0);
858 }
859
LZ4_decompress_safe_partial(const char * source,char * dest,int inputSize,int targetOutputSize,int maxOutputSize)860 int LZ4_decompress_safe_partial(const char* source, char* dest, int inputSize, int targetOutputSize, int maxOutputSize)
861 {
862 return LZ4_decompress_generic(source, dest, inputSize, maxOutputSize, endOnInputSize, noPrefix, partial, targetOutputSize);
863 }
864
LZ4_decompress_fast_withPrefix64k(const char * source,char * dest,int outputSize)865 int LZ4_decompress_fast_withPrefix64k(const char* source, char* dest, int outputSize)
866 {
867 return LZ4_decompress_generic(source, dest, 0, outputSize, endOnOutputSize, withPrefix, full, 0);
868 }
869
LZ4_decompress_fast(const char * source,char * dest,int outputSize)870 int LZ4_decompress_fast(const char* source, char* dest, int outputSize)
871 {
872 #ifdef _MSC_VER /* This version is faster with Visual */
873 return LZ4_decompress_generic(source, dest, 0, outputSize, endOnOutputSize, noPrefix, full, 0);
874 #else
875 return LZ4_decompress_generic(source, dest, 0, outputSize, endOnOutputSize, withPrefix, full, 0);
876 #endif
877 }
878
LZ4_uncompress(const char * source,char * dest,int outputSize)879 int LZ4_uncompress (const char* source, char* dest, int outputSize) { return LZ4_decompress_fast(source, dest, outputSize); }
LZ4_uncompress_unknownOutputSize(const char * source,char * dest,int isize,int maxOutputSize)880 int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize) { return LZ4_decompress_safe(source, dest, isize, maxOutputSize); }
881