2 LZ4 - Fast LZ compression algorithm
3 Copyright (C) 2011-2017, Yann Collet.
5 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions are
11 * Redistributions of source code must retain the above copyright
12 notice, this list of conditions and the following disclaimer.
13 * Redistributions in binary form must reproduce the above
14 copyright notice, this list of conditions and the following disclaimer
15 in the documentation and/or other materials provided with the
18 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 You can contact the author at :
31 - LZ4 homepage : http://www.lz4.org
32 - LZ4 source repository : https://github.com/lz4/lz4
36 /*-************************************
38 **************************************/
41 * Select how default compression functions will allocate memory for their hash table,
42 * in memory stack (0:default, fastest), or in memory heap (1:requires malloc()).
45 # define LZ4_HEAPMODE 0
49 * ACCELERATION_DEFAULT :
50 * Select "acceleration" for LZ4_compress_fast() when parameter value <= 0
52 #define ACCELERATION_DEFAULT 1
55 /*-************************************
56 * CPU Feature Detection
57 **************************************/
58 /* LZ4_FORCE_MEMORY_ACCESS
59 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
60 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
61 * The below switch allow to select different access method for improved performance.
62 * Method 0 (default) : use `memcpy()`. Safe and portable.
63 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
64 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
65 * Method 2 : direct access. This method is portable but violate C standard.
66 * It can generate buggy code on targets which assembly generation depends on alignment.
67 * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
68 * See https://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
69 * Prefer these methods in priority order (0 > 1 > 2)
71 #ifndef LZ4_FORCE_MEMORY_ACCESS /* can be defined externally */
72 # if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) )
73 # define LZ4_FORCE_MEMORY_ACCESS 2
74 # elif defined(__INTEL_COMPILER) || defined(__GNUC__)
75 # define LZ4_FORCE_MEMORY_ACCESS 1
80 * LZ4_FORCE_SW_BITCOUNT
81 * Define this parameter if your target system or compiler does not support hardware bit count
83 #if defined(_MSC_VER) && defined(_WIN32_WCE) /* Visual Studio for Windows CE does not support Hardware bit count */
84 # define LZ4_FORCE_SW_BITCOUNT
88 /*-************************************
90 **************************************/
92 /* see also "memory routines" below */
95 /*-************************************
97 **************************************/
98 #ifdef _MSC_VER /* Visual Studio */
100 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
101 # pragma warning(disable : 4293) /* disable: C4293: too large shift (32-bits) */
102 #endif /* _MSC_VER */
104 #ifndef LZ4_FORCE_INLINE
105 # ifdef _MSC_VER /* Visual Studio */
106 # define LZ4_FORCE_INLINE static __forceinline
108 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
110 # define LZ4_FORCE_INLINE static inline __attribute__((always_inline))
112 # define LZ4_FORCE_INLINE static inline
115 # define LZ4_FORCE_INLINE static
116 # endif /* __STDC_VERSION__ */
117 # endif /* _MSC_VER */
118 #endif /* LZ4_FORCE_INLINE */
120 #if (defined(__GNUC__) && (__GNUC__ >= 3)) || (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 800)) || defined(__clang__)
121 # define expect(expr,value) (__builtin_expect ((expr),(value)) )
123 # define expect(expr,value) (expr)
126 #define likely(expr) expect((expr) != 0, 1)
127 #define unlikely(expr) expect((expr) != 0, 0)
130 /*-************************************
132 **************************************/
133 #include <stdlib.h> /* malloc, calloc, free */
134 #define ALLOCATOR(n,s) calloc(n,s)
136 #include <string.h> /* memset, memcpy */
137 #define MEM_INIT memset
140 /*-************************************
142 **************************************/
143 #if defined(__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
145 typedef uint8_t BYTE;
146 typedef uint16_t U16;
147 typedef uint32_t U32;
149 typedef uint64_t U64;
150 typedef uintptr_t uptrval;
152 typedef unsigned char BYTE;
153 typedef unsigned short U16;
154 typedef unsigned int U32;
155 typedef signed int S32;
156 typedef unsigned long long U64;
157 typedef size_t uptrval; /* generally true, except OpenVMS-64 */
160 #if defined(__x86_64__)
161 typedef U64 reg_t; /* 64-bits in x32 mode */
163 typedef size_t reg_t; /* 32-bits in x32 mode */
166 /*-************************************
167 * Reading and writing into memory
168 **************************************/
169 static unsigned LZ4_isLittleEndian(void)
171 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
176 #if defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==2)
177 /* lie to the compiler about data alignment; use with caution */
179 static U16 LZ4_read16(const void* memPtr) { return *(const U16*) memPtr; }
180 static U32 LZ4_read32(const void* memPtr) { return *(const U32*) memPtr; }
181 static reg_t LZ4_read_ARCH(const void* memPtr) { return *(const reg_t*) memPtr; }
183 static void LZ4_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
184 static void LZ4_write32(void* memPtr, U32 value) { *(U32*)memPtr = value; }
186 #elif defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==1)
188 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
189 /* currently only defined for gcc and icc */
190 typedef union { U16 u16; U32 u32; reg_t uArch; } __attribute__((packed)) unalign;
192 static U16 LZ4_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
193 static U32 LZ4_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
194 static reg_t LZ4_read_ARCH(const void* ptr) { return ((const unalign*)ptr)->uArch; }
196 static void LZ4_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }
197 static void LZ4_write32(void* memPtr, U32 value) { ((unalign*)memPtr)->u32 = value; }
199 #else /* safe and portable access through memcpy() */
201 static U16 LZ4_read16(const void* memPtr)
203 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
206 static U32 LZ4_read32(const void* memPtr)
208 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
211 static reg_t LZ4_read_ARCH(const void* memPtr)
213 reg_t val; memcpy(&val, memPtr, sizeof(val)); return val;
216 static void LZ4_write16(void* memPtr, U16 value)
218 memcpy(memPtr, &value, sizeof(value));
221 static void LZ4_write32(void* memPtr, U32 value)
223 memcpy(memPtr, &value, sizeof(value));
226 #endif /* LZ4_FORCE_MEMORY_ACCESS */
229 static U16 LZ4_readLE16(const void* memPtr)
231 if (LZ4_isLittleEndian()) {
232 return LZ4_read16(memPtr);
234 const BYTE* p = (const BYTE*)memPtr;
235 return (U16)((U16)p[0] + (p[1]<<8));
239 static void LZ4_writeLE16(void* memPtr, U16 value)
241 if (LZ4_isLittleEndian()) {
242 LZ4_write16(memPtr, value);
244 BYTE* p = (BYTE*)memPtr;
246 p[1] = (BYTE)(value>>8);
250 static void LZ4_copy8(void* dst, const void* src)
255 /* customized variant of memcpy, which can overwrite up to 8 bytes beyond dstEnd */
256 static void LZ4_wildCopy(void* dstPtr, const void* srcPtr, void* dstEnd)
258 BYTE* d = (BYTE*)dstPtr;
259 const BYTE* s = (const BYTE*)srcPtr;
260 BYTE* const e = (BYTE*)dstEnd;
262 do { LZ4_copy8(d,s); d+=8; s+=8; } while (d<e);
266 /*-************************************
268 **************************************/
271 #define WILDCOPYLENGTH 8
272 #define LASTLITERALS 5
273 #define MFLIMIT (WILDCOPYLENGTH+MINMATCH)
274 static const int LZ4_minLength = (MFLIMIT+1);
281 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
284 #define ML_MASK ((1U<<ML_BITS)-1)
285 #define RUN_BITS (8-ML_BITS)
286 #define RUN_MASK ((1U<<RUN_BITS)-1)
289 /*-************************************
291 **************************************/
292 #define LZ4_STATIC_ASSERT(c) { enum { LZ4_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
294 #if defined(LZ4_DEBUG) && (LZ4_DEBUG>=2)
296 # define DEBUGLOG(l, ...) { \
297 if (l<=LZ4_DEBUG) { \
298 fprintf(stderr, __FILE__ ": "); \
299 fprintf(stderr, __VA_ARGS__); \
300 fprintf(stderr, " \n"); \
303 # define DEBUGLOG(l, ...) {} /* disabled */
307 /*-************************************
309 **************************************/
310 static unsigned LZ4_NbCommonBytes (register reg_t val)
312 if (LZ4_isLittleEndian()) {
313 if (sizeof(val)==8) {
314 # if defined(_MSC_VER) && defined(_WIN64) && !defined(LZ4_FORCE_SW_BITCOUNT)
316 _BitScanForward64( &r, (U64)val );
318 # elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT)
319 return (__builtin_ctzll((U64)val) >> 3);
321 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 };
322 return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
324 } else /* 32 bits */ {
325 # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
327 _BitScanForward( &r, (U32)val );
329 # elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT)
330 return (__builtin_ctz((U32)val) >> 3);
332 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 };
333 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
336 } else /* Big Endian CPU */ {
337 if (sizeof(val)==8) {
338 # if defined(_MSC_VER) && defined(_WIN64) && !defined(LZ4_FORCE_SW_BITCOUNT)
340 _BitScanReverse64( &r, val );
341 return (unsigned)(r>>3);
342 # elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT)
343 return (__builtin_clzll((U64)val) >> 3);
346 if (!(val>>32)) { r=4; } else { r=0; val>>=32; }
347 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
351 } else /* 32 bits */ {
352 # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
354 _BitScanReverse( &r, (unsigned long)val );
355 return (unsigned)(r>>3);
356 # elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT)
357 return (__builtin_clz((U32)val) >> 3);
360 if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
368 #define STEPSIZE sizeof(reg_t)
369 static unsigned LZ4_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* pInLimit)
371 const BYTE* const pStart = pIn;
373 while (likely(pIn<pInLimit-(STEPSIZE-1))) {
374 reg_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn);
375 if (!diff) { pIn+=STEPSIZE; pMatch+=STEPSIZE; continue; }
376 pIn += LZ4_NbCommonBytes(diff);
377 return (unsigned)(pIn - pStart);
380 if ((STEPSIZE==8) && (pIn<(pInLimit-3)) && (LZ4_read32(pMatch) == LZ4_read32(pIn))) { pIn+=4; pMatch+=4; }
381 if ((pIn<(pInLimit-1)) && (LZ4_read16(pMatch) == LZ4_read16(pIn))) { pIn+=2; pMatch+=2; }
382 if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
383 return (unsigned)(pIn - pStart);
387 #ifndef LZ4_COMMONDEFS_ONLY
388 /*-************************************
390 **************************************/
391 static const int LZ4_64Klimit = ((64 KB) + (MFLIMIT-1));
392 static const U32 LZ4_skipTrigger = 6; /* Increase this value ==> compression run slower on incompressible data */
395 /*-************************************
396 * Local Structures and types
397 **************************************/
398 typedef enum { notLimited = 0, limitedOutput = 1 } limitedOutput_directive;
399 typedef enum { byPtr, byU32, byU16 } tableType_t;
401 typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive;
402 typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive;
404 typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;
405 typedef enum { full = 0, partial = 1 } earlyEnd_directive;
408 /*-************************************
410 **************************************/
411 int LZ4_versionNumber (void) { return LZ4_VERSION_NUMBER; }
412 const char* LZ4_versionString(void) { return LZ4_VERSION_STRING; }
413 int LZ4_compressBound(int isize) { return LZ4_COMPRESSBOUND(isize); }
414 int LZ4_sizeofState() { return LZ4_STREAMSIZE; }
417 /*-******************************
418 * Compression functions
419 ********************************/
420 static U32 LZ4_hash4(U32 sequence, tableType_t const tableType)
422 if (tableType == byU16)
423 return ((sequence * 2654435761U) >> ((MINMATCH*8)-(LZ4_HASHLOG+1)));
425 return ((sequence * 2654435761U) >> ((MINMATCH*8)-LZ4_HASHLOG));
428 static U32 LZ4_hash5(U64 sequence, tableType_t const tableType)
430 static const U64 prime5bytes = 889523592379ULL;
431 static const U64 prime8bytes = 11400714785074694791ULL;
432 const U32 hashLog = (tableType == byU16) ? LZ4_HASHLOG+1 : LZ4_HASHLOG;
433 if (LZ4_isLittleEndian())
434 return (U32)(((sequence << 24) * prime5bytes) >> (64 - hashLog));
436 return (U32)(((sequence >> 24) * prime8bytes) >> (64 - hashLog));
439 LZ4_FORCE_INLINE U32 LZ4_hashPosition(const void* const p, tableType_t const tableType)
441 if ((sizeof(reg_t)==8) && (tableType != byU16)) return LZ4_hash5(LZ4_read_ARCH(p), tableType);
442 return LZ4_hash4(LZ4_read32(p), tableType);
445 static void LZ4_putPositionOnHash(const BYTE* p, U32 h, void* tableBase, tableType_t const tableType, const BYTE* srcBase)
449 case byPtr: { const BYTE** hashTable = (const BYTE**)tableBase; hashTable[h] = p; return; }
450 case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = (U32)(p-srcBase); return; }
451 case byU16: { U16* hashTable = (U16*) tableBase; hashTable[h] = (U16)(p-srcBase); return; }
455 LZ4_FORCE_INLINE void LZ4_putPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase)
457 U32 const h = LZ4_hashPosition(p, tableType);
458 LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase);
461 static const BYTE* LZ4_getPositionOnHash(U32 h, void* tableBase, tableType_t tableType, const BYTE* srcBase)
463 if (tableType == byPtr) { const BYTE** hashTable = (const BYTE**) tableBase; return hashTable[h]; }
464 if (tableType == byU32) { const U32* const hashTable = (U32*) tableBase; return hashTable[h] + srcBase; }
465 { const U16* const hashTable = (U16*) tableBase; return hashTable[h] + srcBase; } /* default, to ensure a return */
468 LZ4_FORCE_INLINE const BYTE* LZ4_getPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase)
470 U32 const h = LZ4_hashPosition(p, tableType);
471 return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase);
475 /** LZ4_compress_generic() :
476 inlined, to ensure branches are decided at compilation time */
477 LZ4_FORCE_INLINE int LZ4_compress_generic(
478 LZ4_stream_t_internal* const cctx,
479 const char* const source,
482 const int maxOutputSize,
483 const limitedOutput_directive outputLimited,
484 const tableType_t tableType,
485 const dict_directive dict,
486 const dictIssue_directive dictIssue,
487 const U32 acceleration)
489 const BYTE* ip = (const BYTE*) source;
491 const BYTE* lowLimit;
492 const BYTE* const lowRefLimit = ip - cctx->dictSize;
493 const BYTE* const dictionary = cctx->dictionary;
494 const BYTE* const dictEnd = dictionary + cctx->dictSize;
495 const ptrdiff_t dictDelta = dictEnd - (const BYTE*)source;
496 const BYTE* anchor = (const BYTE*) source;
497 const BYTE* const iend = ip + inputSize;
498 const BYTE* const mflimit = iend - MFLIMIT;
499 const BYTE* const matchlimit = iend - LASTLITERALS;
501 BYTE* op = (BYTE*) dest;
502 BYTE* const olimit = op + maxOutputSize;
506 /* Init conditions */
507 if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported inputSize, too large (or negative) */
512 base = (const BYTE*)source;
513 lowLimit = (const BYTE*)source;
516 base = (const BYTE*)source - cctx->currentOffset;
517 lowLimit = (const BYTE*)source - cctx->dictSize;
520 base = (const BYTE*)source - cctx->currentOffset;
521 lowLimit = (const BYTE*)source;
524 if ((tableType == byU16) && (inputSize>=LZ4_64Klimit)) return 0; /* Size too large (not within 64K limit) */
525 if (inputSize<LZ4_minLength) goto _last_literals; /* Input too small, no compression (all literals) */
528 LZ4_putPosition(ip, cctx->hashTable, tableType, base);
529 ip++; forwardH = LZ4_hashPosition(ip, tableType);
533 ptrdiff_t refDelta = 0;
538 { const BYTE* forwardIp = ip;
540 unsigned searchMatchNb = acceleration << LZ4_skipTrigger;
542 U32 const h = forwardH;
545 step = (searchMatchNb++ >> LZ4_skipTrigger);
547 if (unlikely(forwardIp > mflimit)) goto _last_literals;
549 match = LZ4_getPositionOnHash(h, cctx->hashTable, tableType, base);
550 if (dict==usingExtDict) {
551 if (match < (const BYTE*)source) {
552 refDelta = dictDelta;
553 lowLimit = dictionary;
556 lowLimit = (const BYTE*)source;
558 forwardH = LZ4_hashPosition(forwardIp, tableType);
559 LZ4_putPositionOnHash(ip, h, cctx->hashTable, tableType, base);
561 } while ( ((dictIssue==dictSmall) ? (match < lowRefLimit) : 0)
562 || ((tableType==byU16) ? 0 : (match + MAX_DISTANCE < ip))
563 || (LZ4_read32(match+refDelta) != LZ4_read32(ip)) );
567 while (((ip>anchor) & (match+refDelta > lowLimit)) && (unlikely(ip[-1]==match[refDelta-1]))) { ip--; match--; }
569 /* Encode Literals */
570 { unsigned const litLength = (unsigned)(ip - anchor);
572 if ((outputLimited) && /* Check output buffer overflow */
573 (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > olimit)))
575 if (litLength >= RUN_MASK) {
576 int len = (int)litLength-RUN_MASK;
577 *token = (RUN_MASK<<ML_BITS);
578 for(; len >= 255 ; len-=255) *op++ = 255;
581 else *token = (BYTE)(litLength<<ML_BITS);
584 LZ4_wildCopy(op, anchor, op+litLength);
590 LZ4_writeLE16(op, (U16)(ip-match)); op+=2;
592 /* Encode MatchLength */
593 { unsigned matchCode;
595 if ((dict==usingExtDict) && (lowLimit==dictionary)) {
598 limit = ip + (dictEnd-match);
599 if (limit > matchlimit) limit = matchlimit;
600 matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, limit);
601 ip += MINMATCH + matchCode;
603 unsigned const more = LZ4_count(ip, (const BYTE*)source, matchlimit);
608 matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, matchlimit);
609 ip += MINMATCH + matchCode;
612 if ( outputLimited && /* Check output buffer overflow */
613 (unlikely(op + (1 + LASTLITERALS) + (matchCode>>8) > olimit)) )
615 if (matchCode >= ML_MASK) {
617 matchCode -= ML_MASK;
618 LZ4_write32(op, 0xFFFFFFFF);
619 while (matchCode >= 4*255) op+=4, LZ4_write32(op, 0xFFFFFFFF), matchCode -= 4*255;
620 op += matchCode / 255;
621 *op++ = (BYTE)(matchCode % 255);
623 *token += (BYTE)(matchCode);
628 /* Test end of chunk */
629 if (ip > mflimit) break;
632 LZ4_putPosition(ip-2, cctx->hashTable, tableType, base);
634 /* Test next position */
635 match = LZ4_getPosition(ip, cctx->hashTable, tableType, base);
636 if (dict==usingExtDict) {
637 if (match < (const BYTE*)source) {
638 refDelta = dictDelta;
639 lowLimit = dictionary;
642 lowLimit = (const BYTE*)source;
644 LZ4_putPosition(ip, cctx->hashTable, tableType, base);
645 if ( ((dictIssue==dictSmall) ? (match>=lowRefLimit) : 1)
646 && (match+MAX_DISTANCE>=ip)
647 && (LZ4_read32(match+refDelta)==LZ4_read32(ip)) )
648 { token=op++; *token=0; goto _next_match; }
650 /* Prepare next loop */
651 forwardH = LZ4_hashPosition(++ip, tableType);
655 /* Encode Last Literals */
656 { size_t const lastRun = (size_t)(iend - anchor);
657 if ( (outputLimited) && /* Check output buffer overflow */
658 ((op - (BYTE*)dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize) )
660 if (lastRun >= RUN_MASK) {
661 size_t accumulator = lastRun - RUN_MASK;
662 *op++ = RUN_MASK << ML_BITS;
663 for(; accumulator >= 255 ; accumulator-=255) *op++ = 255;
664 *op++ = (BYTE) accumulator;
666 *op++ = (BYTE)(lastRun<<ML_BITS);
668 memcpy(op, anchor, lastRun);
673 return (int) (((char*)op)-dest);
677 int LZ4_compress_fast_extState(void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
679 LZ4_stream_t_internal* ctx = &((LZ4_stream_t*)state)->internal_donotuse;
680 LZ4_resetStream((LZ4_stream_t*)state);
681 if (acceleration < 1) acceleration = ACCELERATION_DEFAULT;
683 if (maxOutputSize >= LZ4_compressBound(inputSize)) {
684 if (inputSize < LZ4_64Klimit)
685 return LZ4_compress_generic(ctx, source, dest, inputSize, 0, notLimited, byU16, noDict, noDictIssue, acceleration);
687 return LZ4_compress_generic(ctx, source, dest, inputSize, 0, notLimited, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue, acceleration);
689 if (inputSize < LZ4_64Klimit)
690 return LZ4_compress_generic(ctx, source, dest, inputSize, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue, acceleration);
692 return LZ4_compress_generic(ctx, source, dest, inputSize, maxOutputSize, limitedOutput, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue, acceleration);
697 int LZ4_compress_fast(const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
700 void* ctxPtr = ALLOCATOR(1, sizeof(LZ4_stream_t)); /* malloc-calloc always properly aligned */
703 void* const ctxPtr = &ctx;
706 int const result = LZ4_compress_fast_extState(ctxPtr, source, dest, inputSize, maxOutputSize, acceleration);
715 int LZ4_compress_default(const char* source, char* dest, int inputSize, int maxOutputSize)
717 return LZ4_compress_fast(source, dest, inputSize, maxOutputSize, 1);
721 /* hidden debug function */
722 /* strangely enough, gcc generates faster code when this function is uncommented, even if unused */
723 int LZ4_compress_fast_force(const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
726 LZ4_resetStream(&ctx);
728 if (inputSize < LZ4_64Klimit)
729 return LZ4_compress_generic(&ctx.internal_donotuse, source, dest, inputSize, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue, acceleration);
731 return LZ4_compress_generic(&ctx.internal_donotuse, source, dest, inputSize, maxOutputSize, limitedOutput, sizeof(void*)==8 ? byU32 : byPtr, noDict, noDictIssue, acceleration);
735 /*-******************************
736 * *_destSize() variant
737 ********************************/
739 static int LZ4_compress_destSize_generic(
740 LZ4_stream_t_internal* const ctx,
741 const char* const src,
743 int* const srcSizePtr,
744 const int targetDstSize,
745 const tableType_t tableType)
747 const BYTE* ip = (const BYTE*) src;
748 const BYTE* base = (const BYTE*) src;
749 const BYTE* lowLimit = (const BYTE*) src;
750 const BYTE* anchor = ip;
751 const BYTE* const iend = ip + *srcSizePtr;
752 const BYTE* const mflimit = iend - MFLIMIT;
753 const BYTE* const matchlimit = iend - LASTLITERALS;
755 BYTE* op = (BYTE*) dst;
756 BYTE* const oend = op + targetDstSize;
757 BYTE* const oMaxLit = op + targetDstSize - 2 /* offset */ - 8 /* because 8+MINMATCH==MFLIMIT */ - 1 /* token */;
758 BYTE* const oMaxMatch = op + targetDstSize - (LASTLITERALS + 1 /* token */);
759 BYTE* const oMaxSeq = oMaxLit - 1 /* token */;
764 /* Init conditions */
765 if (targetDstSize < 1) return 0; /* Impossible to store anything */
766 if ((U32)*srcSizePtr > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported input size, too large (or negative) */
767 if ((tableType == byU16) && (*srcSizePtr>=LZ4_64Klimit)) return 0; /* Size too large (not within 64K limit) */
768 if (*srcSizePtr<LZ4_minLength) goto _last_literals; /* Input too small, no compression (all literals) */
772 LZ4_putPosition(ip, ctx->hashTable, tableType, base);
773 ip++; forwardH = LZ4_hashPosition(ip, tableType);
781 { const BYTE* forwardIp = ip;
783 unsigned searchMatchNb = 1 << LZ4_skipTrigger;
789 step = (searchMatchNb++ >> LZ4_skipTrigger);
791 if (unlikely(forwardIp > mflimit)) goto _last_literals;
793 match = LZ4_getPositionOnHash(h, ctx->hashTable, tableType, base);
794 forwardH = LZ4_hashPosition(forwardIp, tableType);
795 LZ4_putPositionOnHash(ip, h, ctx->hashTable, tableType, base);
797 } while ( ((tableType==byU16) ? 0 : (match + MAX_DISTANCE < ip))
798 || (LZ4_read32(match) != LZ4_read32(ip)) );
802 while ((ip>anchor) && (match > lowLimit) && (unlikely(ip[-1]==match[-1]))) { ip--; match--; }
804 /* Encode Literal length */
805 { unsigned litLength = (unsigned)(ip - anchor);
807 if (op + ((litLength+240)/255) + litLength > oMaxLit) {
808 /* Not enough space for a last match */
812 if (litLength>=RUN_MASK) {
813 unsigned len = litLength - RUN_MASK;
814 *token=(RUN_MASK<<ML_BITS);
815 for(; len >= 255 ; len-=255) *op++ = 255;
818 else *token = (BYTE)(litLength<<ML_BITS);
821 LZ4_wildCopy(op, anchor, op+litLength);
827 LZ4_writeLE16(op, (U16)(ip-match)); op+=2;
829 /* Encode MatchLength */
830 { size_t matchLength = LZ4_count(ip+MINMATCH, match+MINMATCH, matchlimit);
832 if (op + ((matchLength+240)/255) > oMaxMatch) {
833 /* Match description too long : reduce it */
834 matchLength = (15-1) + (oMaxMatch-op) * 255;
836 ip += MINMATCH + matchLength;
838 if (matchLength>=ML_MASK) {
840 matchLength -= ML_MASK;
841 while (matchLength >= 255) { matchLength-=255; *op++ = 255; }
842 *op++ = (BYTE)matchLength;
844 else *token += (BYTE)(matchLength);
849 /* Test end of block */
850 if (ip > mflimit) break;
851 if (op > oMaxSeq) break;
854 LZ4_putPosition(ip-2, ctx->hashTable, tableType, base);
856 /* Test next position */
857 match = LZ4_getPosition(ip, ctx->hashTable, tableType, base);
858 LZ4_putPosition(ip, ctx->hashTable, tableType, base);
859 if ( (match+MAX_DISTANCE>=ip)
860 && (LZ4_read32(match)==LZ4_read32(ip)) )
861 { token=op++; *token=0; goto _next_match; }
863 /* Prepare next loop */
864 forwardH = LZ4_hashPosition(++ip, tableType);
868 /* Encode Last Literals */
869 { size_t lastRunSize = (size_t)(iend - anchor);
870 if (op + 1 /* token */ + ((lastRunSize+240)/255) /* litLength */ + lastRunSize /* literals */ > oend) {
871 /* adapt lastRunSize to fill 'dst' */
872 lastRunSize = (oend-op) - 1;
873 lastRunSize -= (lastRunSize+240)/255;
875 ip = anchor + lastRunSize;
877 if (lastRunSize >= RUN_MASK) {
878 size_t accumulator = lastRunSize - RUN_MASK;
879 *op++ = RUN_MASK << ML_BITS;
880 for(; accumulator >= 255 ; accumulator-=255) *op++ = 255;
881 *op++ = (BYTE) accumulator;
883 *op++ = (BYTE)(lastRunSize<<ML_BITS);
885 memcpy(op, anchor, lastRunSize);
890 *srcSizePtr = (int) (((const char*)ip)-src);
891 return (int) (((char*)op)-dst);
895 static int LZ4_compress_destSize_extState (LZ4_stream_t* state, const char* src, char* dst, int* srcSizePtr, int targetDstSize)
897 LZ4_resetStream(state);
899 if (targetDstSize >= LZ4_compressBound(*srcSizePtr)) { /* compression success is guaranteed */
900 return LZ4_compress_fast_extState(state, src, dst, *srcSizePtr, targetDstSize, 1);
902 if (*srcSizePtr < LZ4_64Klimit)
903 return LZ4_compress_destSize_generic(&state->internal_donotuse, src, dst, srcSizePtr, targetDstSize, byU16);
905 return LZ4_compress_destSize_generic(&state->internal_donotuse, src, dst, srcSizePtr, targetDstSize, sizeof(void*)==8 ? byU32 : byPtr);
910 int LZ4_compress_destSize(const char* src, char* dst, int* srcSizePtr, int targetDstSize)
913 LZ4_stream_t* ctx = (LZ4_stream_t*)ALLOCATOR(1, sizeof(LZ4_stream_t)); /* malloc-calloc always properly aligned */
915 LZ4_stream_t ctxBody;
916 LZ4_stream_t* ctx = &ctxBody;
919 int result = LZ4_compress_destSize_extState(ctx, src, dst, srcSizePtr, targetDstSize);
929 /*-******************************
930 * Streaming functions
931 ********************************/
933 LZ4_stream_t* LZ4_createStream(void)
935 LZ4_stream_t* lz4s = (LZ4_stream_t*)ALLOCATOR(8, LZ4_STREAMSIZE_U64);
936 LZ4_STATIC_ASSERT(LZ4_STREAMSIZE >= sizeof(LZ4_stream_t_internal)); /* A compilation error here means LZ4_STREAMSIZE is not large enough */
937 LZ4_resetStream(lz4s);
941 void LZ4_resetStream (LZ4_stream_t* LZ4_stream)
943 MEM_INIT(LZ4_stream, 0, sizeof(LZ4_stream_t));
946 int LZ4_freeStream (LZ4_stream_t* LZ4_stream)
948 if (!LZ4_stream) return 0; /* support free on NULL */
954 #define HASH_UNIT sizeof(reg_t)
955 int LZ4_loadDict (LZ4_stream_t* LZ4_dict, const char* dictionary, int dictSize)
957 LZ4_stream_t_internal* dict = &LZ4_dict->internal_donotuse;
958 const BYTE* p = (const BYTE*)dictionary;
959 const BYTE* const dictEnd = p + dictSize;
962 if ((dict->initCheck) || (dict->currentOffset > 1 GB)) /* Uninitialized structure, or reuse overflow */
963 LZ4_resetStream(LZ4_dict);
965 if (dictSize < (int)HASH_UNIT) {
966 dict->dictionary = NULL;
971 if ((dictEnd - p) > 64 KB) p = dictEnd - 64 KB;
972 dict->currentOffset += 64 KB;
973 base = p - dict->currentOffset;
974 dict->dictionary = p;
975 dict->dictSize = (U32)(dictEnd - p);
976 dict->currentOffset += dict->dictSize;
978 while (p <= dictEnd-HASH_UNIT) {
979 LZ4_putPosition(p, dict->hashTable, byU32, base);
983 return dict->dictSize;
987 static void LZ4_renormDictT(LZ4_stream_t_internal* LZ4_dict, const BYTE* src)
989 if ((LZ4_dict->currentOffset > 0x80000000) ||
990 ((uptrval)LZ4_dict->currentOffset > (uptrval)src)) { /* address space overflow */
991 /* rescale hash table */
992 U32 const delta = LZ4_dict->currentOffset - 64 KB;
993 const BYTE* dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize;
995 for (i=0; i<LZ4_HASH_SIZE_U32; i++) {
996 if (LZ4_dict->hashTable[i] < delta) LZ4_dict->hashTable[i]=0;
997 else LZ4_dict->hashTable[i] -= delta;
999 LZ4_dict->currentOffset = 64 KB;
1000 if (LZ4_dict->dictSize > 64 KB) LZ4_dict->dictSize = 64 KB;
1001 LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize;
1006 int LZ4_compress_fast_continue (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
1008 LZ4_stream_t_internal* streamPtr = &LZ4_stream->internal_donotuse;
1009 const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize;
1011 const BYTE* smallest = (const BYTE*) source;
1012 if (streamPtr->initCheck) return 0; /* Uninitialized structure detected */
1013 if ((streamPtr->dictSize>0) && (smallest>dictEnd)) smallest = dictEnd;
1014 LZ4_renormDictT(streamPtr, smallest);
1015 if (acceleration < 1) acceleration = ACCELERATION_DEFAULT;
1017 /* Check overlapping input/dictionary space */
1018 { const BYTE* sourceEnd = (const BYTE*) source + inputSize;
1019 if ((sourceEnd > streamPtr->dictionary) && (sourceEnd < dictEnd)) {
1020 streamPtr->dictSize = (U32)(dictEnd - sourceEnd);
1021 if (streamPtr->dictSize > 64 KB) streamPtr->dictSize = 64 KB;
1022 if (streamPtr->dictSize < 4) streamPtr->dictSize = 0;
1023 streamPtr->dictionary = dictEnd - streamPtr->dictSize;
1027 /* prefix mode : source data follows dictionary */
1028 if (dictEnd == (const BYTE*)source) {
1030 if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset))
1031 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, withPrefix64k, dictSmall, acceleration);
1033 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, withPrefix64k, noDictIssue, acceleration);
1034 streamPtr->dictSize += (U32)inputSize;
1035 streamPtr->currentOffset += (U32)inputSize;
1039 /* external dictionary mode */
1041 if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset))
1042 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, usingExtDict, dictSmall, acceleration);
1044 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, usingExtDict, noDictIssue, acceleration);
1045 streamPtr->dictionary = (const BYTE*)source;
1046 streamPtr->dictSize = (U32)inputSize;
1047 streamPtr->currentOffset += (U32)inputSize;
1053 /* Hidden debug function, to force external dictionary mode */
1054 int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int inputSize)
1056 LZ4_stream_t_internal* streamPtr = &LZ4_dict->internal_donotuse;
1058 const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize;
1060 const BYTE* smallest = dictEnd;
1061 if (smallest > (const BYTE*) source) smallest = (const BYTE*) source;
1062 LZ4_renormDictT(streamPtr, smallest);
1064 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, 0, notLimited, byU32, usingExtDict, noDictIssue, 1);
1066 streamPtr->dictionary = (const BYTE*)source;
1067 streamPtr->dictSize = (U32)inputSize;
1068 streamPtr->currentOffset += (U32)inputSize;
1074 /*! LZ4_saveDict() :
1075 * If previously compressed data block is not guaranteed to remain available at its memory location,
1076 * save it into a safer place (char* safeBuffer).
1077 * Note : you don't need to call LZ4_loadDict() afterwards,
1078 * dictionary is immediately usable, you can therefore call LZ4_compress_fast_continue().
1079 * Return : saved dictionary size in bytes (necessarily <= dictSize), or 0 if error.
1081 int LZ4_saveDict (LZ4_stream_t* LZ4_dict, char* safeBuffer, int dictSize)
1083 LZ4_stream_t_internal* const dict = &LZ4_dict->internal_donotuse;
1084 const BYTE* const previousDictEnd = dict->dictionary + dict->dictSize;
1086 if ((U32)dictSize > 64 KB) dictSize = 64 KB; /* useless to define a dictionary > 64 KB */
1087 if ((U32)dictSize > dict->dictSize) dictSize = dict->dictSize;
1089 memmove(safeBuffer, previousDictEnd - dictSize, dictSize);
1091 dict->dictionary = (const BYTE*)safeBuffer;
1092 dict->dictSize = (U32)dictSize;
1099 /*-*****************************
1100 * Decompression functions
1101 *******************************/
1102 /*! LZ4_decompress_generic() :
1103 * This generic decompression function cover all use cases.
1104 * It shall be instantiated several times, using different sets of directives
1105 * Note that it is important this generic function is really inlined,
1106 * in order to remove useless branches during compilation optimization.
1108 LZ4_FORCE_INLINE int LZ4_decompress_generic(
1109 const char* const source,
1112 int outputSize, /* If endOnInput==endOnInputSize, this value is the max size of Output Buffer. */
1114 int endOnInput, /* endOnOutputSize, endOnInputSize */
1115 int partialDecoding, /* full, partial */
1116 int targetOutputSize, /* only used if partialDecoding==partial */
1117 int dict, /* noDict, withPrefix64k, usingExtDict */
1118 const BYTE* const lowPrefix, /* == dest when no prefix */
1119 const BYTE* const dictStart, /* only if dict==usingExtDict */
1120 const size_t dictSize /* note : = 0 if noDict */
1123 /* Local Variables */
1124 const BYTE* ip = (const BYTE*) source;
1125 const BYTE* const iend = ip + inputSize;
1127 BYTE* op = (BYTE*) dest;
1128 BYTE* const oend = op + outputSize;
1130 BYTE* oexit = op + targetOutputSize;
1131 const BYTE* const lowLimit = lowPrefix - dictSize;
1133 const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize;
1134 const unsigned dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4};
1135 const int dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3};
1137 const int safeDecode = (endOnInput==endOnInputSize);
1138 const int checkOffset = ((safeDecode) && (dictSize < (int)(64 KB)));
1142 if ((partialDecoding) && (oexit > oend-MFLIMIT)) oexit = oend-MFLIMIT; /* targetOutputSize too high => decode everything */
1143 if ((endOnInput) && (unlikely(outputSize==0))) return ((inputSize==1) && (*ip==0)) ? 0 : -1; /* Empty output buffer */
1144 if ((!endOnInput) && (unlikely(outputSize==0))) return (*ip==0?1:-1);
1146 /* Main Loop : decode sequences */
1152 /* get literal length */
1153 unsigned const token = *ip++;
1154 if ((length=(token>>ML_BITS)) == RUN_MASK) {
1159 } while ( likely(endOnInput ? ip<iend-RUN_MASK : 1) & (s==255) );
1160 if ((safeDecode) && unlikely((uptrval)(op)+length<(uptrval)(op))) goto _output_error; /* overflow detection */
1161 if ((safeDecode) && unlikely((uptrval)(ip)+length<(uptrval)(ip))) goto _output_error; /* overflow detection */
1166 if ( ((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT)) || (ip+length>iend-(2+1+LASTLITERALS))) )
1167 || ((!endOnInput) && (cpy>oend-WILDCOPYLENGTH)) )
1169 if (partialDecoding) {
1170 if (cpy > oend) goto _output_error; /* Error : write attempt beyond end of output buffer */
1171 if ((endOnInput) && (ip+length > iend)) goto _output_error; /* Error : read attempt beyond end of input buffer */
1173 if ((!endOnInput) && (cpy != oend)) goto _output_error; /* Error : block decoding must stop exactly there */
1174 if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) goto _output_error; /* Error : input must be consumed */
1176 memcpy(op, ip, length);
1179 break; /* Necessarily EOF, due to parsing restrictions */
1181 LZ4_wildCopy(op, ip, cpy);
1182 ip += length; op = cpy;
1185 offset = LZ4_readLE16(ip); ip+=2;
1186 match = op - offset;
1187 if ((checkOffset) && (unlikely(match < lowLimit))) goto _output_error; /* Error : offset outside buffers */
1188 LZ4_write32(op, (U32)offset); /* costs ~1%; silence an msan warning when offset==0 */
1190 /* get matchlength */
1191 length = token & ML_MASK;
1192 if (length == ML_MASK) {
1196 if ((endOnInput) && (ip > iend-LASTLITERALS)) goto _output_error;
1199 if ((safeDecode) && unlikely((uptrval)(op)+length<(uptrval)op)) goto _output_error; /* overflow detection */
1203 /* check external dictionary */
1204 if ((dict==usingExtDict) && (match < lowPrefix)) {
1205 if (unlikely(op+length > oend-LASTLITERALS)) goto _output_error; /* doesn't respect parsing restriction */
1207 if (length <= (size_t)(lowPrefix-match)) {
1208 /* match can be copied as a single segment from external dictionary */
1209 memmove(op, dictEnd - (lowPrefix-match), length);
1212 /* match encompass external dictionary and current block */
1213 size_t const copySize = (size_t)(lowPrefix-match);
1214 size_t const restSize = length - copySize;
1215 memcpy(op, dictEnd - copySize, copySize);
1217 if (restSize > (size_t)(op-lowPrefix)) { /* overlap copy */
1218 BYTE* const endOfMatch = op + restSize;
1219 const BYTE* copyFrom = lowPrefix;
1220 while (op < endOfMatch) *op++ = *copyFrom++;
1222 memcpy(op, lowPrefix, restSize);
1228 /* copy match within block */
1230 if (unlikely(offset<8)) {
1231 const int dec64 = dec64table[offset];
1236 match += dec32table[offset];
1237 memcpy(op+4, match, 4);
1239 } else { LZ4_copy8(op, match); match+=8; }
1242 if (unlikely(cpy>oend-12)) {
1243 BYTE* const oCopyLimit = oend-(WILDCOPYLENGTH-1);
1244 if (cpy > oend-LASTLITERALS) goto _output_error; /* Error : last LASTLITERALS bytes must be literals (uncompressed) */
1245 if (op < oCopyLimit) {
1246 LZ4_wildCopy(op, match, oCopyLimit);
1247 match += oCopyLimit - op;
1250 while (op<cpy) *op++ = *match++;
1252 LZ4_copy8(op, match);
1253 if (length>16) LZ4_wildCopy(op+8, match+8, cpy);
1255 op=cpy; /* correction */
1258 /* end of decoding */
1260 return (int) (((char*)op)-dest); /* Nb of output bytes decoded */
1262 return (int) (((const char*)ip)-source); /* Nb of input bytes read */
1264 /* Overflow error detected */
1266 return (int) (-(((const char*)ip)-source))-1;
1270 int LZ4_decompress_safe(const char* source, char* dest, int compressedSize, int maxDecompressedSize)
1272 return LZ4_decompress_generic(source, dest, compressedSize, maxDecompressedSize, endOnInputSize, full, 0, noDict, (BYTE*)dest, NULL, 0);
1275 int LZ4_decompress_safe_partial(const char* source, char* dest, int compressedSize, int targetOutputSize, int maxDecompressedSize)
1277 return LZ4_decompress_generic(source, dest, compressedSize, maxDecompressedSize, endOnInputSize, partial, targetOutputSize, noDict, (BYTE*)dest, NULL, 0);
1280 int LZ4_decompress_fast(const char* source, char* dest, int originalSize)
1282 return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, withPrefix64k, (BYTE*)(dest - 64 KB), NULL, 64 KB);
1286 /*===== streaming decompression functions =====*/
1288 LZ4_streamDecode_t* LZ4_createStreamDecode(void)
1290 LZ4_streamDecode_t* lz4s = (LZ4_streamDecode_t*) ALLOCATOR(1, sizeof(LZ4_streamDecode_t));
1294 int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream)
1296 if (!LZ4_stream) return 0; /* support free on NULL */
1297 FREEMEM(LZ4_stream);
1302 * LZ4_setStreamDecode() :
1303 * Use this function to instruct where to find the dictionary.
1304 * This function is not necessary if previous data is still available where it was decoded.
1305 * Loading a size of 0 is allowed (same effect as no dictionary).
1306 * Return : 1 if OK, 0 if error
1308 int LZ4_setStreamDecode (LZ4_streamDecode_t* LZ4_streamDecode, const char* dictionary, int dictSize)
1310 LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse;
1311 lz4sd->prefixSize = (size_t) dictSize;
1312 lz4sd->prefixEnd = (const BYTE*) dictionary + dictSize;
1313 lz4sd->externalDict = NULL;
1314 lz4sd->extDictSize = 0;
1320 These decoding functions allow decompression of multiple blocks in "streaming" mode.
1321 Previously decoded blocks must still be available at the memory position where they were decoded.
1322 If it's not possible, save the relevant part of decoded data into a safe buffer,
1323 and indicate where it stands using LZ4_setStreamDecode()
1325 int LZ4_decompress_safe_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int compressedSize, int maxOutputSize)
1327 LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse;
1330 if (lz4sd->prefixEnd == (BYTE*)dest) {
1331 result = LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
1332 endOnInputSize, full, 0,
1333 usingExtDict, lz4sd->prefixEnd - lz4sd->prefixSize, lz4sd->externalDict, lz4sd->extDictSize);
1334 if (result <= 0) return result;
1335 lz4sd->prefixSize += result;
1336 lz4sd->prefixEnd += result;
1338 lz4sd->extDictSize = lz4sd->prefixSize;
1339 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize;
1340 result = LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
1341 endOnInputSize, full, 0,
1342 usingExtDict, (BYTE*)dest, lz4sd->externalDict, lz4sd->extDictSize);
1343 if (result <= 0) return result;
1344 lz4sd->prefixSize = result;
1345 lz4sd->prefixEnd = (BYTE*)dest + result;
1351 int LZ4_decompress_fast_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int originalSize)
1353 LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse;
1356 if (lz4sd->prefixEnd == (BYTE*)dest) {
1357 result = LZ4_decompress_generic(source, dest, 0, originalSize,
1358 endOnOutputSize, full, 0,
1359 usingExtDict, lz4sd->prefixEnd - lz4sd->prefixSize, lz4sd->externalDict, lz4sd->extDictSize);
1360 if (result <= 0) return result;
1361 lz4sd->prefixSize += originalSize;
1362 lz4sd->prefixEnd += originalSize;
1364 lz4sd->extDictSize = lz4sd->prefixSize;
1365 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize;
1366 result = LZ4_decompress_generic(source, dest, 0, originalSize,
1367 endOnOutputSize, full, 0,
1368 usingExtDict, (BYTE*)dest, lz4sd->externalDict, lz4sd->extDictSize);
1369 if (result <= 0) return result;
1370 lz4sd->prefixSize = originalSize;
1371 lz4sd->prefixEnd = (BYTE*)dest + originalSize;
1379 Advanced decoding functions :
1381 These decoding functions work the same as "_continue" ones,
1382 the dictionary must be explicitly provided within parameters
1385 LZ4_FORCE_INLINE int LZ4_decompress_usingDict_generic(const char* source, char* dest, int compressedSize, int maxOutputSize, int safe, const char* dictStart, int dictSize)
1388 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, noDict, (BYTE*)dest, NULL, 0);
1389 if (dictStart+dictSize == dest) {
1390 if (dictSize >= (int)(64 KB - 1))
1391 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, withPrefix64k, (BYTE*)dest-64 KB, NULL, 0);
1392 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, noDict, (BYTE*)dest-dictSize, NULL, 0);
1394 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, usingExtDict, (BYTE*)dest, (const BYTE*)dictStart, dictSize);
1397 int LZ4_decompress_safe_usingDict(const char* source, char* dest, int compressedSize, int maxOutputSize, const char* dictStart, int dictSize)
1399 return LZ4_decompress_usingDict_generic(source, dest, compressedSize, maxOutputSize, 1, dictStart, dictSize);
1402 int LZ4_decompress_fast_usingDict(const char* source, char* dest, int originalSize, const char* dictStart, int dictSize)
1404 return LZ4_decompress_usingDict_generic(source, dest, 0, originalSize, 0, dictStart, dictSize);
1407 /* debug function */
1408 int LZ4_decompress_safe_forceExtDict(const char* source, char* dest, int compressedSize, int maxOutputSize, const char* dictStart, int dictSize)
1410 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, usingExtDict, (BYTE*)dest, (const BYTE*)dictStart, dictSize);
1414 /*=*************************************************
1415 * Obsolete Functions
1416 ***************************************************/
1417 /* obsolete compression functions */
1418 int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize) { return LZ4_compress_default(source, dest, inputSize, maxOutputSize); }
1419 int LZ4_compress(const char* source, char* dest, int inputSize) { return LZ4_compress_default(source, dest, inputSize, LZ4_compressBound(inputSize)); }
1420 int LZ4_compress_limitedOutput_withState (void* state, const char* src, char* dst, int srcSize, int dstSize) { return LZ4_compress_fast_extState(state, src, dst, srcSize, dstSize, 1); }
1421 int LZ4_compress_withState (void* state, const char* src, char* dst, int srcSize) { return LZ4_compress_fast_extState(state, src, dst, srcSize, LZ4_compressBound(srcSize), 1); }
1422 int LZ4_compress_limitedOutput_continue (LZ4_stream_t* LZ4_stream, const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_fast_continue(LZ4_stream, src, dst, srcSize, maxDstSize, 1); }
1423 int LZ4_compress_continue (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize) { return LZ4_compress_fast_continue(LZ4_stream, source, dest, inputSize, LZ4_compressBound(inputSize), 1); }
1426 These function names are deprecated and should no longer be used.
1427 They are only provided here for compatibility with older user programs.
1428 - LZ4_uncompress is totally equivalent to LZ4_decompress_fast
1429 - LZ4_uncompress_unknownOutputSize is totally equivalent to LZ4_decompress_safe
1431 int LZ4_uncompress (const char* source, char* dest, int outputSize) { return LZ4_decompress_fast(source, dest, outputSize); }
1432 int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize) { return LZ4_decompress_safe(source, dest, isize, maxOutputSize); }
1435 /* Obsolete Streaming functions */
1437 int LZ4_sizeofStreamState() { return LZ4_STREAMSIZE; }
1439 static void LZ4_init(LZ4_stream_t* lz4ds, BYTE* base)
1441 MEM_INIT(lz4ds, 0, sizeof(LZ4_stream_t));
1442 lz4ds->internal_donotuse.bufferStart = base;
1445 int LZ4_resetStreamState(void* state, char* inputBuffer)
1447 if ((((uptrval)state) & 3) != 0) return 1; /* Error : pointer is not aligned on 4-bytes boundary */
1448 LZ4_init((LZ4_stream_t*)state, (BYTE*)inputBuffer);
1452 void* LZ4_create (char* inputBuffer)
1454 LZ4_stream_t* lz4ds = (LZ4_stream_t*)ALLOCATOR(8, sizeof(LZ4_stream_t));
1455 LZ4_init (lz4ds, (BYTE*)inputBuffer);
1459 char* LZ4_slideInputBuffer (void* LZ4_Data)
1461 LZ4_stream_t_internal* ctx = &((LZ4_stream_t*)LZ4_Data)->internal_donotuse;
1462 int dictSize = LZ4_saveDict((LZ4_stream_t*)LZ4_Data, (char*)ctx->bufferStart, 64 KB);
1463 return (char*)(ctx->bufferStart + dictSize);
1466 /* Obsolete streaming decompression functions */
1468 int LZ4_decompress_safe_withPrefix64k(const char* source, char* dest, int compressedSize, int maxOutputSize)
1470 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, withPrefix64k, (BYTE*)dest - 64 KB, NULL, 64 KB);
1473 int LZ4_decompress_fast_withPrefix64k(const char* source, char* dest, int originalSize)
1475 return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, withPrefix64k, (BYTE*)dest - 64 KB, NULL, 64 KB);
1478 #endif /* LZ4_COMMONDEFS_ONLY */