Update LZ4 to 1.8.3
[charm.git] / src / arch / util / lz4.c
1 /*
2    LZ4 - Fast LZ compression algorithm
3    Copyright (C) 2011-present, Yann Collet.
4
5    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6
7    Redistribution and use in source and binary forms, with or without
8    modification, are permitted provided that the following conditions are
9    met:
10
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
16    distribution.
17
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.
29
30    You can contact the author at :
31     - LZ4 homepage : http://www.lz4.org
32     - LZ4 source repository : https://github.com/lz4/lz4
33 */
34
35
36 /*-************************************
37 *  Tuning parameters
38 **************************************/
39 /*
40  * LZ4_HEAPMODE :
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()).
43  */
44 #ifndef LZ4_HEAPMODE
45 #  define LZ4_HEAPMODE 0
46 #endif
47
48 /*
49  * ACCELERATION_DEFAULT :
50  * Select "acceleration" for LZ4_compress_fast() when parameter value <= 0
51  */
52 #define ACCELERATION_DEFAULT 1
53
54
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)
70  */
71 #ifndef LZ4_FORCE_MEMORY_ACCESS   /* can be defined externally */
72 #  if defined(__GNUC__) && \
73   ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) \
74   || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) )
75 #    define LZ4_FORCE_MEMORY_ACCESS 2
76 #  elif (defined(__INTEL_COMPILER) && !defined(_WIN32)) || defined(__GNUC__)
77 #    define LZ4_FORCE_MEMORY_ACCESS 1
78 #  endif
79 #endif
80
81 /*
82  * LZ4_FORCE_SW_BITCOUNT
83  * Define this parameter if your target system or compiler does not support hardware bit count
84  */
85 #if defined(_MSC_VER) && defined(_WIN32_WCE)   /* Visual Studio for WinCE doesn't support Hardware bit count */
86 #  define LZ4_FORCE_SW_BITCOUNT
87 #endif
88
89
90
91 /*-************************************
92 *  Dependency
93 **************************************/
94 #define LZ4_STATIC_LINKING_ONLY
95 #define LZ4_DISABLE_DEPRECATE_WARNINGS /* due to LZ4_decompress_safe_withPrefix64k */
96 #include "lz4.h"
97 /* see also "memory routines" below */
98
99
100 /*-************************************
101 *  Compiler Options
102 **************************************/
103 #ifdef _MSC_VER    /* Visual Studio */
104 #  include <intrin.h>
105 #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
106 #  pragma warning(disable : 4293)        /* disable: C4293: too large shift (32-bits) */
107 #endif  /* _MSC_VER */
108
109 #ifndef LZ4_FORCE_INLINE
110 #  ifdef _MSC_VER    /* Visual Studio */
111 #    define LZ4_FORCE_INLINE static __forceinline
112 #  else
113 #    if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L   /* C99 */
114 #      ifdef __GNUC__
115 #        define LZ4_FORCE_INLINE static inline __attribute__((always_inline))
116 #      else
117 #        define LZ4_FORCE_INLINE static inline
118 #      endif
119 #    else
120 #      define LZ4_FORCE_INLINE static
121 #    endif /* __STDC_VERSION__ */
122 #  endif  /* _MSC_VER */
123 #endif /* LZ4_FORCE_INLINE */
124
125 /* LZ4_FORCE_O2_GCC_PPC64LE and LZ4_FORCE_O2_INLINE_GCC_PPC64LE
126  * Gcc on ppc64le generates an unrolled SIMDized loop for LZ4_wildCopy,
127  * together with a simple 8-byte copy loop as a fall-back path.
128  * However, this optimization hurts the decompression speed by >30%,
129  * because the execution does not go to the optimized loop
130  * for typical compressible data, and all of the preamble checks
131  * before going to the fall-back path become useless overhead.
132  * This optimization happens only with the -O3 flag, and -O2 generates
133  * a simple 8-byte copy loop.
134  * With gcc on ppc64le, all of the LZ4_decompress_* and LZ4_wildCopy
135  * functions are annotated with __attribute__((optimize("O2"))),
136  * and also LZ4_wildCopy is forcibly inlined, so that the O2 attribute
137  * of LZ4_wildCopy does not affect the compression speed.
138  */
139 #if defined(__PPC64__) && defined(__LITTLE_ENDIAN__) && defined(__GNUC__)
140 #  define LZ4_FORCE_O2_GCC_PPC64LE __attribute__((optimize("O2")))
141 #  define LZ4_FORCE_O2_INLINE_GCC_PPC64LE __attribute__((optimize("O2"))) LZ4_FORCE_INLINE
142 #else
143 #  define LZ4_FORCE_O2_GCC_PPC64LE
144 #  define LZ4_FORCE_O2_INLINE_GCC_PPC64LE static
145 #endif
146
147 #if (defined(__GNUC__) && (__GNUC__ >= 3)) || (defined(__INTEL_COMPILER) && (__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 #ifndef likely
154 #define likely(expr)     expect((expr) != 0, 1)
155 #endif
156 #ifndef unlikely
157 #define unlikely(expr)   expect((expr) != 0, 0)
158 #endif
159
160
161 /*-************************************
162 *  Memory routines
163 **************************************/
164 #include <stdlib.h>   /* malloc, calloc, free */
165 #define ALLOC(s)          malloc(s)
166 #define ALLOC_AND_ZERO(s) calloc(1,s)
167 #define FREEMEM(p)        free(p)
168 #include <string.h>   /* memset, memcpy */
169 #define MEM_INIT(p,v,s)   memset((p),(v),(s))
170
171
172 /*-************************************
173 *  Basic Types
174 **************************************/
175 #if defined(__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
176 # include <stdint.h>
177   typedef  uint8_t BYTE;
178   typedef uint16_t U16;
179   typedef uint32_t U32;
180   typedef  int32_t S32;
181   typedef uint64_t U64;
182   typedef uintptr_t uptrval;
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   typedef size_t              uptrval;   /* generally true, except OpenVMS-64 */
190 #endif
191
192 #if defined(__x86_64__)
193   typedef U64    reg_t;   /* 64-bits in x32 mode */
194 #else
195   typedef size_t reg_t;   /* 32-bits in x32 mode */
196 #endif
197
198 /*-************************************
199 *  Reading and writing into memory
200 **************************************/
201 static unsigned LZ4_isLittleEndian(void)
202 {
203     const union { U32 u; BYTE c[4]; } one = { 1 };   /* don't use static : performance detrimental */
204     return one.c[0];
205 }
206
207
208 #if defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==2)
209 /* lie to the compiler about data alignment; use with caution */
210
211 static U16 LZ4_read16(const void* memPtr) { return *(const U16*) memPtr; }
212 static U32 LZ4_read32(const void* memPtr) { return *(const U32*) memPtr; }
213 static reg_t LZ4_read_ARCH(const void* memPtr) { return *(const reg_t*) memPtr; }
214
215 static void LZ4_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
216 static void LZ4_write32(void* memPtr, U32 value) { *(U32*)memPtr = value; }
217
218 #elif defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==1)
219
220 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
221 /* currently only defined for gcc and icc */
222 typedef union { U16 u16; U32 u32; reg_t uArch; } __attribute__((packed)) unalign;
223
224 static U16 LZ4_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
225 static U32 LZ4_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
226 static reg_t LZ4_read_ARCH(const void* ptr) { return ((const unalign*)ptr)->uArch; }
227
228 static void LZ4_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }
229 static void LZ4_write32(void* memPtr, U32 value) { ((unalign*)memPtr)->u32 = value; }
230
231 #else  /* safe and portable access through memcpy() */
232
233 static U16 LZ4_read16(const void* memPtr)
234 {
235     U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
236 }
237
238 static U32 LZ4_read32(const void* memPtr)
239 {
240     U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
241 }
242
243 static reg_t LZ4_read_ARCH(const void* memPtr)
244 {
245     reg_t val; memcpy(&val, memPtr, sizeof(val)); return val;
246 }
247
248 static void LZ4_write16(void* memPtr, U16 value)
249 {
250     memcpy(memPtr, &value, sizeof(value));
251 }
252
253 static void LZ4_write32(void* memPtr, U32 value)
254 {
255     memcpy(memPtr, &value, sizeof(value));
256 }
257
258 #endif /* LZ4_FORCE_MEMORY_ACCESS */
259
260
261 static U16 LZ4_readLE16(const void* memPtr)
262 {
263     if (LZ4_isLittleEndian()) {
264         return LZ4_read16(memPtr);
265     } else {
266         const BYTE* p = (const BYTE*)memPtr;
267         return (U16)((U16)p[0] + (p[1]<<8));
268     }
269 }
270
271 static void LZ4_writeLE16(void* memPtr, U16 value)
272 {
273     if (LZ4_isLittleEndian()) {
274         LZ4_write16(memPtr, value);
275     } else {
276         BYTE* p = (BYTE*)memPtr;
277         p[0] = (BYTE) value;
278         p[1] = (BYTE)(value>>8);
279     }
280 }
281
282 /* customized variant of memcpy, which can overwrite up to 8 bytes beyond dstEnd */
283 LZ4_FORCE_O2_INLINE_GCC_PPC64LE
284 void LZ4_wildCopy(void* dstPtr, const void* srcPtr, void* dstEnd)
285 {
286     BYTE* d = (BYTE*)dstPtr;
287     const BYTE* s = (const BYTE*)srcPtr;
288     BYTE* const e = (BYTE*)dstEnd;
289
290     do { memcpy(d,s,8); d+=8; s+=8; } while (d<e);
291 }
292
293
294 /*-************************************
295 *  Common Constants
296 **************************************/
297 #define MINMATCH 4
298
299 #define WILDCOPYLENGTH 8
300 #define LASTLITERALS   5   /* see ../doc/lz4_Block_format.md#parsing-restrictions */
301 #define MFLIMIT       12   /* see ../doc/lz4_Block_format.md#parsing-restrictions */
302 #define MATCH_SAFEGUARD_DISTANCE  ((2*WILDCOPYLENGTH) - MINMATCH)   /* ensure it's possible to write 2 x wildcopyLength without overflowing output buffer */
303 static const int LZ4_minLength = (MFLIMIT+1);
304
305 #define KB *(1 <<10)
306 #define MB *(1 <<20)
307 #define GB *(1U<<30)
308
309 #define MAXD_LOG 16
310 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
311
312 #define ML_BITS  4
313 #define ML_MASK  ((1U<<ML_BITS)-1)
314 #define RUN_BITS (8-ML_BITS)
315 #define RUN_MASK ((1U<<RUN_BITS)-1)
316
317
318 /*-************************************
319 *  Error detection
320 **************************************/
321 #if defined(LZ4_DEBUG) && (LZ4_DEBUG>=1)
322 #  include <assert.h>
323 #else
324 #  ifndef assert
325 #    define assert(condition) ((void)0)
326 #  endif
327 #endif
328
329 #define LZ4_STATIC_ASSERT(c)   { enum { LZ4_static_assert = 1/(int)(!!(c)) }; }   /* use after variable declarations */
330
331 #if defined(LZ4_DEBUG) && (LZ4_DEBUG>=2)
332 #  include <stdio.h>
333 static int g_debuglog_enable = 1;
334 #  define DEBUGLOG(l, ...) {                                  \
335                 if ((g_debuglog_enable) && (l<=LZ4_DEBUG)) {  \
336                     fprintf(stderr, __FILE__ ": ");           \
337                     fprintf(stderr, __VA_ARGS__);             \
338                     fprintf(stderr, " \n");                   \
339             }   }
340 #else
341 #  define DEBUGLOG(l, ...)      {}    /* disabled */
342 #endif
343
344
345 /*-************************************
346 *  Common functions
347 **************************************/
348 static unsigned LZ4_NbCommonBytes (reg_t val)
349 {
350     if (LZ4_isLittleEndian()) {
351         if (sizeof(val)==8) {
352 #       if defined(_MSC_VER) && defined(_WIN64) && !defined(LZ4_FORCE_SW_BITCOUNT)
353             unsigned long r = 0;
354             _BitScanForward64( &r, (U64)val );
355             return (int)(r>>3);
356 #       elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT)
357             return (__builtin_ctzll((U64)val) >> 3);
358 #       else
359             static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
360                                                      0, 3, 1, 3, 1, 4, 2, 7,
361                                                      0, 2, 3, 6, 1, 5, 3, 5,
362                                                      1, 3, 4, 4, 2, 5, 6, 7,
363                                                      7, 0, 1, 2, 3, 3, 4, 6,
364                                                      2, 6, 5, 5, 3, 4, 5, 6,
365                                                      7, 1, 2, 4, 6, 4, 4, 5,
366                                                      7, 2, 6, 5, 7, 6, 7, 7 };
367             return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
368 #       endif
369         } else /* 32 bits */ {
370 #       if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
371             unsigned long r;
372             _BitScanForward( &r, (U32)val );
373             return (int)(r>>3);
374 #       elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT)
375             return (__builtin_ctz((U32)val) >> 3);
376 #       else
377             static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
378                                                      3, 2, 2, 1, 3, 2, 0, 1,
379                                                      3, 3, 1, 2, 2, 2, 2, 0,
380                                                      3, 1, 2, 0, 1, 0, 1, 1 };
381             return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
382 #       endif
383         }
384     } else   /* Big Endian CPU */ {
385         if (sizeof(val)==8) {   /* 64-bits */
386 #       if defined(_MSC_VER) && defined(_WIN64) && !defined(LZ4_FORCE_SW_BITCOUNT)
387             unsigned long r = 0;
388             _BitScanReverse64( &r, val );
389             return (unsigned)(r>>3);
390 #       elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT)
391             return (__builtin_clzll((U64)val) >> 3);
392 #       else
393             static const U32 by32 = sizeof(val)*4;  /* 32 on 64 bits (goal), 16 on 32 bits.
394                 Just to avoid some static analyzer complaining about shift by 32 on 32-bits target.
395                 Note that this code path is never triggered in 32-bits mode. */
396             unsigned r;
397             if (!(val>>by32)) { r=4; } else { r=0; val>>=by32; }
398             if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
399             r += (!val);
400             return r;
401 #       endif
402         } else /* 32 bits */ {
403 #       if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
404             unsigned long r = 0;
405             _BitScanReverse( &r, (unsigned long)val );
406             return (unsigned)(r>>3);
407 #       elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT)
408             return (__builtin_clz((U32)val) >> 3);
409 #       else
410             unsigned r;
411             if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
412             r += (!val);
413             return r;
414 #       endif
415         }
416     }
417 }
418
419 #define STEPSIZE sizeof(reg_t)
420 LZ4_FORCE_INLINE
421 unsigned LZ4_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* pInLimit)
422 {
423     const BYTE* const pStart = pIn;
424
425     if (likely(pIn < pInLimit-(STEPSIZE-1))) {
426         reg_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn);
427         if (!diff) {
428             pIn+=STEPSIZE; pMatch+=STEPSIZE;
429         } else {
430             return LZ4_NbCommonBytes(diff);
431     }   }
432
433     while (likely(pIn < pInLimit-(STEPSIZE-1))) {
434         reg_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn);
435         if (!diff) { pIn+=STEPSIZE; pMatch+=STEPSIZE; continue; }
436         pIn += LZ4_NbCommonBytes(diff);
437         return (unsigned)(pIn - pStart);
438     }
439
440     if ((STEPSIZE==8) && (pIn<(pInLimit-3)) && (LZ4_read32(pMatch) == LZ4_read32(pIn))) { pIn+=4; pMatch+=4; }
441     if ((pIn<(pInLimit-1)) && (LZ4_read16(pMatch) == LZ4_read16(pIn))) { pIn+=2; pMatch+=2; }
442     if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
443     return (unsigned)(pIn - pStart);
444 }
445
446
447 #ifndef LZ4_COMMONDEFS_ONLY
448 /*-************************************
449 *  Local Constants
450 **************************************/
451 static const int LZ4_64Klimit = ((64 KB) + (MFLIMIT-1));
452 static const U32 LZ4_skipTrigger = 6;  /* Increase this value ==> compression run slower on incompressible data */
453
454
455 /*-************************************
456 *  Local Structures and types
457 **************************************/
458 typedef enum { notLimited = 0, limitedOutput = 1, fillOutput = 2 } limitedOutput_directive;
459 typedef enum { clearedTable = 0, byPtr, byU32, byU16 } tableType_t;
460
461 /**
462  * This enum distinguishes several different modes of accessing previous
463  * content in the stream.
464  *
465  * - noDict        : There is no preceding content.
466  * - withPrefix64k : Table entries up to ctx->dictSize before the current blob
467  *                   blob being compressed are valid and refer to the preceding
468  *                   content (of length ctx->dictSize), which is available
469  *                   contiguously preceding in memory the content currently
470  *                   being compressed.
471  * - usingExtDict  : Like withPrefix64k, but the preceding content is somewhere
472  *                   else in memory, starting at ctx->dictionary with length
473  *                   ctx->dictSize.
474  * - usingDictCtx  : Like usingExtDict, but everything concerning the preceding
475  *                   content is in a separate context, pointed to by
476  *                   ctx->dictCtx. ctx->dictionary, ctx->dictSize, and table
477  *                   entries in the current context that refer to positions
478  *                   preceding the beginning of the current compression are
479  *                   ignored. Instead, ctx->dictCtx->dictionary and ctx->dictCtx
480  *                   ->dictSize describe the location and size of the preceding
481  *                   content, and matches are found by looking in the ctx
482  *                   ->dictCtx->hashTable.
483  */
484 typedef enum { noDict = 0, withPrefix64k, usingExtDict, usingDictCtx } dict_directive;
485 typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive;
486
487
488 /*-************************************
489 *  Local Utils
490 **************************************/
491 int LZ4_versionNumber (void) { return LZ4_VERSION_NUMBER; }
492 const char* LZ4_versionString(void) { return LZ4_VERSION_STRING; }
493 int LZ4_compressBound(int isize)  { return LZ4_COMPRESSBOUND(isize); }
494 int LZ4_sizeofState() { return LZ4_STREAMSIZE; }
495
496
497 /*-************************************
498 *  Internal Definitions used in Tests
499 **************************************/
500 #if defined (__cplusplus)
501 extern "C" {
502 #endif
503
504 int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize);
505
506 int LZ4_decompress_safe_forceExtDict(const char* in, char* out, int inSize, int outSize, const void* dict, size_t dictSize);
507
508 #if defined (__cplusplus)
509 }
510 #endif
511
512 /*-******************************
513 *  Compression functions
514 ********************************/
515 static U32 LZ4_hash4(U32 sequence, tableType_t const tableType)
516 {
517     if (tableType == byU16)
518         return ((sequence * 2654435761U) >> ((MINMATCH*8)-(LZ4_HASHLOG+1)));
519     else
520         return ((sequence * 2654435761U) >> ((MINMATCH*8)-LZ4_HASHLOG));
521 }
522
523 static U32 LZ4_hash5(U64 sequence, tableType_t const tableType)
524 {
525     static const U64 prime5bytes = 889523592379ULL;
526     static const U64 prime8bytes = 11400714785074694791ULL;
527     const U32 hashLog = (tableType == byU16) ? LZ4_HASHLOG+1 : LZ4_HASHLOG;
528     if (LZ4_isLittleEndian())
529         return (U32)(((sequence << 24) * prime5bytes) >> (64 - hashLog));
530     else
531         return (U32)(((sequence >> 24) * prime8bytes) >> (64 - hashLog));
532 }
533
534 LZ4_FORCE_INLINE U32 LZ4_hashPosition(const void* const p, tableType_t const tableType)
535 {
536     if ((sizeof(reg_t)==8) && (tableType != byU16)) return LZ4_hash5(LZ4_read_ARCH(p), tableType);
537     return LZ4_hash4(LZ4_read32(p), tableType);
538 }
539
540 static void LZ4_putIndexOnHash(U32 idx, U32 h, void* tableBase, tableType_t const tableType)
541 {
542     switch (tableType)
543     {
544     default: /* fallthrough */
545     case clearedTable: /* fallthrough */
546     case byPtr: { /* illegal! */ assert(0); return; }
547     case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = idx; return; }
548     case byU16: { U16* hashTable = (U16*) tableBase; assert(idx < 65536); hashTable[h] = (U16)idx; return; }
549     }
550 }
551
552 static void LZ4_putPositionOnHash(const BYTE* p, U32 h,
553                                   void* tableBase, tableType_t const tableType,
554                             const BYTE* srcBase)
555 {
556     switch (tableType)
557     {
558     case clearedTable: { /* illegal! */ assert(0); return; }
559     case byPtr: { const BYTE** hashTable = (const BYTE**)tableBase; hashTable[h] = p; return; }
560     case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = (U32)(p-srcBase); return; }
561     case byU16: { U16* hashTable = (U16*) tableBase; hashTable[h] = (U16)(p-srcBase); return; }
562     }
563 }
564
565 LZ4_FORCE_INLINE void LZ4_putPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase)
566 {
567     U32 const h = LZ4_hashPosition(p, tableType);
568     LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase);
569 }
570
571 /* LZ4_getIndexOnHash() :
572  * Index of match position registered in hash table.
573  * hash position must be calculated by using base+index, or dictBase+index.
574  * Assumption 1 : only valid if tableType == byU32 or byU16.
575  * Assumption 2 : h is presumed valid (within limits of hash table)
576  */
577 static U32 LZ4_getIndexOnHash(U32 h, const void* tableBase, tableType_t tableType)
578 {
579     LZ4_STATIC_ASSERT(LZ4_MEMORY_USAGE > 2);
580     if (tableType == byU32) {
581         const U32* const hashTable = (const U32*) tableBase;
582         assert(h < (1U << (LZ4_MEMORY_USAGE-2)));
583         return hashTable[h];
584     }
585     if (tableType == byU16) {
586         const U16* const hashTable = (const U16*) tableBase;
587         assert(h < (1U << (LZ4_MEMORY_USAGE-1)));
588         return hashTable[h];
589     }
590     assert(0); return 0;  /* forbidden case */
591 }
592
593 static const BYTE* LZ4_getPositionOnHash(U32 h, const void* tableBase, tableType_t tableType, const BYTE* srcBase)
594 {
595     if (tableType == byPtr) { const BYTE* const* hashTable = (const BYTE* const*) tableBase; return hashTable[h]; }
596     if (tableType == byU32) { const U32* const hashTable = (const U32*) tableBase; return hashTable[h] + srcBase; }
597     { const U16* const hashTable = (const U16*) tableBase; return hashTable[h] + srcBase; }   /* default, to ensure a return */
598 }
599
600 LZ4_FORCE_INLINE const BYTE* LZ4_getPosition(const BYTE* p,
601                                              const void* tableBase, tableType_t tableType,
602                                              const BYTE* srcBase)
603 {
604     U32 const h = LZ4_hashPosition(p, tableType);
605     return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase);
606 }
607
608 LZ4_FORCE_INLINE void LZ4_prepareTable(
609         LZ4_stream_t_internal* const cctx,
610         const int inputSize,
611         const tableType_t tableType) {
612     /* If the table hasn't been used, it's guaranteed to be zeroed out, and is
613      * therefore safe to use no matter what mode we're in. Otherwise, we figure
614      * out if it's safe to leave as is or whether it needs to be reset.
615      */
616     if (cctx->tableType != clearedTable) {
617         if (cctx->tableType != tableType
618           || (tableType == byU16 && cctx->currentOffset + inputSize >= 0xFFFFU)
619           || (tableType == byU32 && cctx->currentOffset > 1 GB)
620           || tableType == byPtr
621           || inputSize >= 4 KB)
622         {
623             DEBUGLOG(4, "LZ4_prepareTable: Resetting table in %p", cctx);
624             MEM_INIT(cctx->hashTable, 0, LZ4_HASHTABLESIZE);
625             cctx->currentOffset = 0;
626             cctx->tableType = clearedTable;
627         } else {
628             DEBUGLOG(4, "LZ4_prepareTable: Re-use hash table (no reset)");
629         }
630     }
631
632     /* Adding a gap, so all previous entries are > MAX_DISTANCE back, is faster
633      * than compressing without a gap. However, compressing with
634      * currentOffset == 0 is faster still, so we preserve that case.
635      */
636     if (cctx->currentOffset != 0 && tableType == byU32) {
637         DEBUGLOG(5, "LZ4_prepareTable: adding 64KB to currentOffset");
638         cctx->currentOffset += 64 KB;
639     }
640
641     /* Finally, clear history */
642     cctx->dictCtx = NULL;
643     cctx->dictionary = NULL;
644     cctx->dictSize = 0;
645 }
646
647 /** LZ4_compress_generic() :
648     inlined, to ensure branches are decided at compilation time */
649 LZ4_FORCE_INLINE int LZ4_compress_generic(
650                  LZ4_stream_t_internal* const cctx,
651                  const char* const source,
652                  char* const dest,
653                  const int inputSize,
654                  int *inputConsumed, /* only written when outputLimited == fillOutput */
655                  const int maxOutputSize,
656                  const limitedOutput_directive outputLimited,
657                  const tableType_t tableType,
658                  const dict_directive dictDirective,
659                  const dictIssue_directive dictIssue,
660                  const U32 acceleration)
661 {
662     const BYTE* ip = (const BYTE*) source;
663
664     U32 const startIndex = cctx->currentOffset;
665     const BYTE* base = (const BYTE*) source - startIndex;
666     const BYTE* lowLimit;
667
668     const LZ4_stream_t_internal* dictCtx = (const LZ4_stream_t_internal*) cctx->dictCtx;
669     const BYTE* const dictionary =
670         dictDirective == usingDictCtx ? dictCtx->dictionary : cctx->dictionary;
671     const U32 dictSize =
672         dictDirective == usingDictCtx ? dictCtx->dictSize : cctx->dictSize;
673     const U32 dictDelta = (dictDirective == usingDictCtx) ? startIndex - dictCtx->currentOffset : 0;   /* make indexes in dictCtx comparable with index in current context */
674
675     int const maybe_extMem = (dictDirective == usingExtDict) || (dictDirective == usingDictCtx);
676     U32 const prefixIdxLimit = startIndex - dictSize;   /* used when dictDirective == dictSmall */
677     const BYTE* const dictEnd = dictionary + dictSize;
678     const BYTE* anchor = (const BYTE*) source;
679     const BYTE* const iend = ip + inputSize;
680     const BYTE* const mflimitPlusOne = iend - MFLIMIT + 1;
681     const BYTE* const matchlimit = iend - LASTLITERALS;
682
683     /* the dictCtx currentOffset is indexed on the start of the dictionary,
684      * while a dictionary in the current context precedes the currentOffset */
685     const BYTE* dictBase = (dictDirective == usingDictCtx) ?
686                             dictionary + dictSize - dictCtx->currentOffset :
687                             dictionary + dictSize - startIndex;
688
689     BYTE* op = (BYTE*) dest;
690     BYTE* const olimit = op + maxOutputSize;
691
692     U32 offset = 0;
693     U32 forwardH;
694
695     DEBUGLOG(5, "LZ4_compress_generic: srcSize=%i, tableType=%u", inputSize, tableType);
696     /* Init conditions */
697     if (outputLimited == fillOutput && maxOutputSize < 1) return 0; /* Impossible to store anything */
698     if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0;   /* Unsupported inputSize, too large (or negative) */
699     if ((tableType == byU16) && (inputSize>=LZ4_64Klimit)) return 0;  /* Size too large (not within 64K limit) */
700     if (tableType==byPtr) assert(dictDirective==noDict);      /* only supported use case with byPtr */
701     assert(acceleration >= 1);
702
703     lowLimit = (const BYTE*)source - (dictDirective == withPrefix64k ? dictSize : 0);
704
705     /* Update context state */
706     if (dictDirective == usingDictCtx) {
707         /* Subsequent linked blocks can't use the dictionary. */
708         /* Instead, they use the block we just compressed. */
709         cctx->dictCtx = NULL;
710         cctx->dictSize = (U32)inputSize;
711     } else {
712         cctx->dictSize += (U32)inputSize;
713     }
714     cctx->currentOffset += (U32)inputSize;
715     cctx->tableType = (U16)tableType;
716
717     if (inputSize<LZ4_minLength) goto _last_literals;        /* Input too small, no compression (all literals) */
718
719     /* First Byte */
720     LZ4_putPosition(ip, cctx->hashTable, tableType, base);
721     ip++; forwardH = LZ4_hashPosition(ip, tableType);
722
723     /* Main Loop */
724     for ( ; ; ) {
725         const BYTE* match;
726         BYTE* token;
727
728         /* Find a match */
729         if (tableType == byPtr) {
730             const BYTE* forwardIp = ip;
731             unsigned step = 1;
732             unsigned searchMatchNb = acceleration << LZ4_skipTrigger;
733             do {
734                 U32 const h = forwardH;
735                 ip = forwardIp;
736                 forwardIp += step;
737                 step = (searchMatchNb++ >> LZ4_skipTrigger);
738
739                 if (unlikely(forwardIp > mflimitPlusOne)) goto _last_literals;
740                 assert(ip < mflimitPlusOne);
741
742                 match = LZ4_getPositionOnHash(h, cctx->hashTable, tableType, base);
743                 forwardH = LZ4_hashPosition(forwardIp, tableType);
744                 LZ4_putPositionOnHash(ip, h, cctx->hashTable, tableType, base);
745
746             } while ( (match+MAX_DISTANCE < ip)
747                    || (LZ4_read32(match) != LZ4_read32(ip)) );
748
749         } else {   /* byU32, byU16 */
750
751             const BYTE* forwardIp = ip;
752             unsigned step = 1;
753             unsigned searchMatchNb = acceleration << LZ4_skipTrigger;
754             do {
755                 U32 const h = forwardH;
756                 U32 const current = (U32)(forwardIp - base);
757                 U32 matchIndex = LZ4_getIndexOnHash(h, cctx->hashTable, tableType);
758                 assert(matchIndex <= current);
759                 assert(forwardIp - base < (ptrdiff_t)(2 GB - 1));
760                 ip = forwardIp;
761                 forwardIp += step;
762                 step = (searchMatchNb++ >> LZ4_skipTrigger);
763
764                 if (unlikely(forwardIp > mflimitPlusOne)) goto _last_literals;
765                 assert(ip < mflimitPlusOne);
766
767                 if (dictDirective == usingDictCtx) {
768                     if (matchIndex < startIndex) {
769                         /* there was no match, try the dictionary */
770                         assert(tableType == byU32);
771                         matchIndex = LZ4_getIndexOnHash(h, dictCtx->hashTable, byU32);
772                         match = dictBase + matchIndex;
773                         matchIndex += dictDelta;   /* make dictCtx index comparable with current context */
774                         lowLimit = dictionary;
775                     } else {
776                         match = base + matchIndex;
777                         lowLimit = (const BYTE*)source;
778                     }
779                 } else if (dictDirective==usingExtDict) {
780                     if (matchIndex < startIndex) {
781                         DEBUGLOG(7, "extDict candidate: matchIndex=%5u  <  startIndex=%5u", matchIndex, startIndex);
782                         assert(startIndex - matchIndex >= MINMATCH);
783                         match = dictBase + matchIndex;
784                         lowLimit = dictionary;
785                     } else {
786                         match = base + matchIndex;
787                         lowLimit = (const BYTE*)source;
788                     }
789                 } else {   /* single continuous memory segment */
790                     match = base + matchIndex;
791                 }
792                 forwardH = LZ4_hashPosition(forwardIp, tableType);
793                 LZ4_putIndexOnHash(current, h, cctx->hashTable, tableType);
794
795                 if ((dictIssue == dictSmall) && (matchIndex < prefixIdxLimit)) continue;    /* match outside of valid area */
796                 assert(matchIndex < current);
797                 if ((tableType != byU16) && (matchIndex+MAX_DISTANCE < current)) continue;  /* too far */
798                 if (tableType == byU16) assert((current - matchIndex) <= MAX_DISTANCE);     /* too_far presumed impossible with byU16 */
799
800                 if (LZ4_read32(match) == LZ4_read32(ip)) {
801                     if (maybe_extMem) offset = current - matchIndex;
802                     break;   /* match found */
803                 }
804
805             } while(1);
806         }
807
808         /* Catch up */
809         while (((ip>anchor) & (match > lowLimit)) && (unlikely(ip[-1]==match[-1]))) { ip--; match--; }
810
811         /* Encode Literals */
812         {   unsigned const litLength = (unsigned)(ip - anchor);
813             token = op++;
814             if ((outputLimited == limitedOutput) &&  /* Check output buffer overflow */
815                 (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > olimit)))
816                 return 0;
817             if ((outputLimited == fillOutput) &&
818                 (unlikely(op + (litLength+240)/255 /* litlen */ + litLength /* literals */ + 2 /* offset */ + 1 /* token */ + MFLIMIT - MINMATCH /* min last literals so last match is <= end - MFLIMIT */ > olimit))) {
819                 op--;
820                 goto _last_literals;
821             }
822             if (litLength >= RUN_MASK) {
823                 int len = (int)litLength-RUN_MASK;
824                 *token = (RUN_MASK<<ML_BITS);
825                 for(; len >= 255 ; len-=255) *op++ = 255;
826                 *op++ = (BYTE)len;
827             }
828             else *token = (BYTE)(litLength<<ML_BITS);
829
830             /* Copy Literals */
831             LZ4_wildCopy(op, anchor, op+litLength);
832             op+=litLength;
833             DEBUGLOG(6, "seq.start:%i, literals=%u, match.start:%i",
834                         (int)(anchor-(const BYTE*)source), litLength, (int)(ip-(const BYTE*)source));
835         }
836
837 _next_match:
838         /* at this stage, the following variables must be correctly set :
839          * - ip : at start of LZ operation
840          * - match : at start of previous pattern occurence; can be within current prefix, or within extDict
841          * - offset : if maybe_ext_memSegment==1 (constant)
842          * - lowLimit : must be == dictionary to mean "match is within extDict"; must be == source otherwise
843          * - token and *token : position to write 4-bits for match length; higher 4-bits for literal length supposed already written
844          */
845
846         if ((outputLimited == fillOutput) &&
847             (op + 2 /* offset */ + 1 /* token */ + MFLIMIT - MINMATCH /* min last literals so last match is <= end - MFLIMIT */ > olimit)) {
848             /* the match was too close to the end, rewind and go to last literals */
849             op = token;
850             goto _last_literals;
851         }
852
853         /* Encode Offset */
854         if (maybe_extMem) {   /* static test */
855             DEBUGLOG(6, "             with offset=%u  (ext if > %i)", offset, (int)(ip - (const BYTE*)source));
856             assert(offset <= MAX_DISTANCE && offset > 0);
857             LZ4_writeLE16(op, (U16)offset); op+=2;
858         } else  {
859             DEBUGLOG(6, "             with offset=%u  (same segment)", (U32)(ip - match));
860             assert(ip-match <= MAX_DISTANCE);
861             LZ4_writeLE16(op, (U16)(ip - match)); op+=2;
862         }
863
864         /* Encode MatchLength */
865         {   unsigned matchCode;
866
867             if ( (dictDirective==usingExtDict || dictDirective==usingDictCtx)
868               && (lowLimit==dictionary) /* match within extDict */ ) {
869                 const BYTE* limit = ip + (dictEnd-match);
870                 assert(dictEnd > match);
871                 if (limit > matchlimit) limit = matchlimit;
872                 matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, limit);
873                 ip += MINMATCH + matchCode;
874                 if (ip==limit) {
875                     unsigned const more = LZ4_count(limit, (const BYTE*)source, matchlimit);
876                     matchCode += more;
877                     ip += more;
878                 }
879                 DEBUGLOG(6, "             with matchLength=%u starting in extDict", matchCode+MINMATCH);
880             } else {
881                 matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, matchlimit);
882                 ip += MINMATCH + matchCode;
883                 DEBUGLOG(6, "             with matchLength=%u", matchCode+MINMATCH);
884             }
885
886             if ((outputLimited) &&    /* Check output buffer overflow */
887                 (unlikely(op + (1 + LASTLITERALS) + (matchCode>>8) > olimit)) ) {
888                 if (outputLimited == limitedOutput)
889                   return 0;
890                 if (outputLimited == fillOutput) {
891                     /* Match description too long : reduce it */
892                     U32 newMatchCode = 15 /* in token */ - 1 /* to avoid needing a zero byte */ + ((U32)(olimit - op) - 2 - 1 - LASTLITERALS) * 255;
893                     ip -= matchCode - newMatchCode;
894                     matchCode = newMatchCode;
895                 }
896             }
897             if (matchCode >= ML_MASK) {
898                 *token += ML_MASK;
899                 matchCode -= ML_MASK;
900                 LZ4_write32(op, 0xFFFFFFFF);
901                 while (matchCode >= 4*255) {
902                     op+=4;
903                     LZ4_write32(op, 0xFFFFFFFF);
904                     matchCode -= 4*255;
905                 }
906                 op += matchCode / 255;
907                 *op++ = (BYTE)(matchCode % 255);
908             } else
909                 *token += (BYTE)(matchCode);
910         }
911
912         anchor = ip;
913
914         /* Test end of chunk */
915         if (ip >= mflimitPlusOne) break;
916
917         /* Fill table */
918         LZ4_putPosition(ip-2, cctx->hashTable, tableType, base);
919
920         /* Test next position */
921         if (tableType == byPtr) {
922
923             match = LZ4_getPosition(ip, cctx->hashTable, tableType, base);
924             LZ4_putPosition(ip, cctx->hashTable, tableType, base);
925             if ( (match+MAX_DISTANCE >= ip)
926               && (LZ4_read32(match) == LZ4_read32(ip)) )
927             { token=op++; *token=0; goto _next_match; }
928
929         } else {   /* byU32, byU16 */
930
931             U32 const h = LZ4_hashPosition(ip, tableType);
932             U32 const current = (U32)(ip-base);
933             U32 matchIndex = LZ4_getIndexOnHash(h, cctx->hashTable, tableType);
934             assert(matchIndex < current);
935             if (dictDirective == usingDictCtx) {
936                 if (matchIndex < startIndex) {
937                     /* there was no match, try the dictionary */
938                     matchIndex = LZ4_getIndexOnHash(h, dictCtx->hashTable, byU32);
939                     match = dictBase + matchIndex;
940                     lowLimit = dictionary;   /* required for match length counter */
941                     matchIndex += dictDelta;
942                 } else {
943                     match = base + matchIndex;
944                     lowLimit = (const BYTE*)source;  /* required for match length counter */
945                 }
946             } else if (dictDirective==usingExtDict) {
947                 if (matchIndex < startIndex) {
948                     match = dictBase + matchIndex;
949                     lowLimit = dictionary;   /* required for match length counter */
950                 } else {
951                     match = base + matchIndex;
952                     lowLimit = (const BYTE*)source;   /* required for match length counter */
953                 }
954             } else {   /* single memory segment */
955                 match = base + matchIndex;
956             }
957             LZ4_putIndexOnHash(current, h, cctx->hashTable, tableType);
958             assert(matchIndex < current);
959             if ( ((dictIssue==dictSmall) ? (matchIndex >= prefixIdxLimit) : 1)
960               && ((tableType==byU16) ? 1 : (matchIndex+MAX_DISTANCE >= current))
961               && (LZ4_read32(match) == LZ4_read32(ip)) ) {
962                 token=op++;
963                 *token=0;
964                 if (maybe_extMem) offset = current - matchIndex;
965                 DEBUGLOG(6, "seq.start:%i, literals=%u, match.start:%i",
966                             (int)(anchor-(const BYTE*)source), 0, (int)(ip-(const BYTE*)source));
967                 goto _next_match;
968             }
969         }
970
971         /* Prepare next loop */
972         forwardH = LZ4_hashPosition(++ip, tableType);
973
974     }
975
976 _last_literals:
977     /* Encode Last Literals */
978     {   size_t lastRun = (size_t)(iend - anchor);
979         if ( (outputLimited) &&  /* Check output buffer overflow */
980             (op + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > olimit)) {
981             if (outputLimited == fillOutput) {
982                 /* adapt lastRun to fill 'dst' */
983                 lastRun  = (olimit-op) - 1;
984                 lastRun -= (lastRun+240)/255;
985             }
986             if (outputLimited == limitedOutput)
987                 return 0;
988         }
989         if (lastRun >= RUN_MASK) {
990             size_t accumulator = lastRun - RUN_MASK;
991             *op++ = RUN_MASK << ML_BITS;
992             for(; accumulator >= 255 ; accumulator-=255) *op++ = 255;
993             *op++ = (BYTE) accumulator;
994         } else {
995             *op++ = (BYTE)(lastRun<<ML_BITS);
996         }
997         memcpy(op, anchor, lastRun);
998         ip = anchor + lastRun;
999         op += lastRun;
1000     }
1001
1002     if (outputLimited == fillOutput) {
1003         *inputConsumed = (int) (((const char*)ip)-source);
1004     }
1005     DEBUGLOG(5, "LZ4_compress_generic: compressed %i bytes into %i bytes", inputSize, (int)(((char*)op) - dest));
1006     return (int)(((char*)op) - dest);
1007 }
1008
1009
1010 int LZ4_compress_fast_extState(void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
1011 {
1012     LZ4_stream_t_internal* ctx = &((LZ4_stream_t*)state)->internal_donotuse;
1013     if (acceleration < 1) acceleration = ACCELERATION_DEFAULT;
1014     LZ4_resetStream((LZ4_stream_t*)state);
1015     if (maxOutputSize >= LZ4_compressBound(inputSize)) {
1016         if (inputSize < LZ4_64Klimit) {
1017             return LZ4_compress_generic(ctx, source, dest, inputSize, NULL, 0, notLimited, byU16, noDict, noDictIssue, acceleration);
1018         } else {
1019             const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)source > MAX_DISTANCE)) ? byPtr : byU32;
1020             return LZ4_compress_generic(ctx, source, dest, inputSize, NULL, 0, notLimited, tableType, noDict, noDictIssue, acceleration);
1021         }
1022     } else {
1023         if (inputSize < LZ4_64Klimit) {;
1024             return LZ4_compress_generic(ctx, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue, acceleration);
1025         } else {
1026             const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)source > MAX_DISTANCE)) ? byPtr : byU32;
1027             return LZ4_compress_generic(ctx, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, noDict, noDictIssue, acceleration);
1028         }
1029     }
1030 }
1031
1032 /**
1033  * LZ4_compress_fast_extState_fastReset() :
1034  * A variant of LZ4_compress_fast_extState().
1035  *
1036  * Using this variant avoids an expensive initialization step. It is only safe
1037  * to call if the state buffer is known to be correctly initialized already
1038  * (see comment in lz4.h on LZ4_resetStream_fast() for a definition of
1039  * "correctly initialized").
1040  */
1041 int LZ4_compress_fast_extState_fastReset(void* state, const char* src, char* dst, int srcSize, int dstCapacity, int acceleration)
1042 {
1043     LZ4_stream_t_internal* ctx = &((LZ4_stream_t*)state)->internal_donotuse;
1044     if (acceleration < 1) acceleration = ACCELERATION_DEFAULT;
1045
1046     if (dstCapacity >= LZ4_compressBound(srcSize)) {
1047         if (srcSize < LZ4_64Klimit) {
1048             const tableType_t tableType = byU16;
1049             LZ4_prepareTable(ctx, srcSize, tableType);
1050             if (ctx->currentOffset) {
1051                 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, 0, notLimited, tableType, noDict, dictSmall, acceleration);
1052             } else {
1053                 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, 0, notLimited, tableType, noDict, noDictIssue, acceleration);
1054             }
1055         } else {
1056             const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)src > MAX_DISTANCE)) ? byPtr : byU32;
1057             LZ4_prepareTable(ctx, srcSize, tableType);
1058             return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, 0, notLimited, tableType, noDict, noDictIssue, acceleration);
1059         }
1060     } else {
1061         if (srcSize < LZ4_64Klimit) {
1062             const tableType_t tableType = byU16;
1063             LZ4_prepareTable(ctx, srcSize, tableType);
1064             if (ctx->currentOffset) {
1065                 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, dstCapacity, limitedOutput, tableType, noDict, dictSmall, acceleration);
1066             } else {
1067                 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, dstCapacity, limitedOutput, tableType, noDict, noDictIssue, acceleration);
1068             }
1069         } else {
1070             const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)src > MAX_DISTANCE)) ? byPtr : byU32;
1071             LZ4_prepareTable(ctx, srcSize, tableType);
1072             return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, dstCapacity, limitedOutput, tableType, noDict, noDictIssue, acceleration);
1073         }
1074     }
1075 }
1076
1077
1078 int LZ4_compress_fast(const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
1079 {
1080     int result;
1081 #if (LZ4_HEAPMODE)
1082     LZ4_stream_t* ctxPtr = ALLOC(sizeof(LZ4_stream_t));   /* malloc-calloc always properly aligned */
1083     if (ctxPtr == NULL) return 0;
1084 #else
1085     LZ4_stream_t ctx;
1086     LZ4_stream_t* const ctxPtr = &ctx;
1087 #endif
1088     result = LZ4_compress_fast_extState(ctxPtr, source, dest, inputSize, maxOutputSize, acceleration);
1089
1090 #if (LZ4_HEAPMODE)
1091     FREEMEM(ctxPtr);
1092 #endif
1093     return result;
1094 }
1095
1096
1097 int LZ4_compress_default(const char* source, char* dest, int inputSize, int maxOutputSize)
1098 {
1099     return LZ4_compress_fast(source, dest, inputSize, maxOutputSize, 1);
1100 }
1101
1102
1103 /* hidden debug function */
1104 /* strangely enough, gcc generates faster code when this function is uncommented, even if unused */
1105 int LZ4_compress_fast_force(const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
1106 {
1107     LZ4_stream_t ctx;
1108     LZ4_resetStream(&ctx);
1109
1110     if (inputSize < LZ4_64Klimit)
1111         return LZ4_compress_generic(&ctx.internal_donotuse, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, byU16,                        noDict, noDictIssue, acceleration);
1112     else
1113         return LZ4_compress_generic(&ctx.internal_donotuse, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, sizeof(void*)==8 ? byU32 : byPtr, noDict, noDictIssue, acceleration);
1114 }
1115
1116
1117 /* Note!: This function leaves the stream in an unclean/broken state!
1118  * It is not safe to subsequently use the same state with a _fastReset() or
1119  * _continue() call without resetting it. */
1120 static int LZ4_compress_destSize_extState (LZ4_stream_t* state, const char* src, char* dst, int* srcSizePtr, int targetDstSize)
1121 {
1122     LZ4_resetStream(state);
1123
1124     if (targetDstSize >= LZ4_compressBound(*srcSizePtr)) {  /* compression success is guaranteed */
1125         return LZ4_compress_fast_extState(state, src, dst, *srcSizePtr, targetDstSize, 1);
1126     } else {
1127         if (*srcSizePtr < LZ4_64Klimit) {
1128             return LZ4_compress_generic(&state->internal_donotuse, src, dst, *srcSizePtr, srcSizePtr, targetDstSize, fillOutput, byU16, noDict, noDictIssue, 1);
1129         } else {
1130             tableType_t const tableType = ((sizeof(void*)==4) && ((uptrval)src > MAX_DISTANCE)) ? byPtr : byU32;
1131             return LZ4_compress_generic(&state->internal_donotuse, src, dst, *srcSizePtr, srcSizePtr, targetDstSize, fillOutput, tableType, noDict, noDictIssue, 1);
1132     }   }
1133 }
1134
1135
1136 int LZ4_compress_destSize(const char* src, char* dst, int* srcSizePtr, int targetDstSize)
1137 {
1138 #if (LZ4_HEAPMODE)
1139     LZ4_stream_t* ctx = (LZ4_stream_t*)ALLOC(sizeof(LZ4_stream_t));   /* malloc-calloc always properly aligned */
1140     if (ctx == NULL) return 0;
1141 #else
1142     LZ4_stream_t ctxBody;
1143     LZ4_stream_t* ctx = &ctxBody;
1144 #endif
1145
1146     int result = LZ4_compress_destSize_extState(ctx, src, dst, srcSizePtr, targetDstSize);
1147
1148 #if (LZ4_HEAPMODE)
1149     FREEMEM(ctx);
1150 #endif
1151     return result;
1152 }
1153
1154
1155
1156 /*-******************************
1157 *  Streaming functions
1158 ********************************/
1159
1160 LZ4_stream_t* LZ4_createStream(void)
1161 {
1162     LZ4_stream_t* lz4s = (LZ4_stream_t*)ALLOC(sizeof(LZ4_stream_t));
1163     LZ4_STATIC_ASSERT(LZ4_STREAMSIZE >= sizeof(LZ4_stream_t_internal));    /* A compilation error here means LZ4_STREAMSIZE is not large enough */
1164     DEBUGLOG(4, "LZ4_createStream %p", lz4s);
1165     if (lz4s == NULL) return NULL;
1166     LZ4_resetStream(lz4s);
1167     return lz4s;
1168 }
1169
1170 void LZ4_resetStream (LZ4_stream_t* LZ4_stream)
1171 {
1172     DEBUGLOG(5, "LZ4_resetStream (ctx:%p)", LZ4_stream);
1173     MEM_INIT(LZ4_stream, 0, sizeof(LZ4_stream_t));
1174 }
1175
1176 void LZ4_resetStream_fast(LZ4_stream_t* ctx) {
1177     LZ4_prepareTable(&(ctx->internal_donotuse), 0, byU32);
1178 }
1179
1180 int LZ4_freeStream (LZ4_stream_t* LZ4_stream)
1181 {
1182     if (!LZ4_stream) return 0;   /* support free on NULL */
1183     DEBUGLOG(5, "LZ4_freeStream %p", LZ4_stream);
1184     FREEMEM(LZ4_stream);
1185     return (0);
1186 }
1187
1188
1189 #define HASH_UNIT sizeof(reg_t)
1190 int LZ4_loadDict (LZ4_stream_t* LZ4_dict, const char* dictionary, int dictSize)
1191 {
1192     LZ4_stream_t_internal* dict = &LZ4_dict->internal_donotuse;
1193     const tableType_t tableType = byU32;
1194     const BYTE* p = (const BYTE*)dictionary;
1195     const BYTE* const dictEnd = p + dictSize;
1196     const BYTE* base;
1197
1198     DEBUGLOG(4, "LZ4_loadDict (%i bytes from %p into %p)", dictSize, dictionary, LZ4_dict);
1199
1200     /* It's necessary to reset the context,
1201      * and not just continue it with prepareTable()
1202      * to avoid any risk of generating overflowing matchIndex
1203      * when compressing using this dictionary */
1204     LZ4_resetStream(LZ4_dict);
1205
1206     /* We always increment the offset by 64 KB, since, if the dict is longer,
1207      * we truncate it to the last 64k, and if it's shorter, we still want to
1208      * advance by a whole window length so we can provide the guarantee that
1209      * there are only valid offsets in the window, which allows an optimization
1210      * in LZ4_compress_fast_continue() where it uses noDictIssue even when the
1211      * dictionary isn't a full 64k. */
1212
1213     if ((dictEnd - p) > 64 KB) p = dictEnd - 64 KB;
1214     base = dictEnd - 64 KB - dict->currentOffset;
1215     dict->dictionary = p;
1216     dict->dictSize = (U32)(dictEnd - p);
1217     dict->currentOffset += 64 KB;
1218     dict->tableType = tableType;
1219
1220     if (dictSize < (int)HASH_UNIT) {
1221         return 0;
1222     }
1223
1224     while (p <= dictEnd-HASH_UNIT) {
1225         LZ4_putPosition(p, dict->hashTable, tableType, base);
1226         p+=3;
1227     }
1228
1229     return dict->dictSize;
1230 }
1231
1232 void LZ4_attach_dictionary(LZ4_stream_t *working_stream, const LZ4_stream_t *dictionary_stream) {
1233     if (dictionary_stream != NULL) {
1234         /* If the current offset is zero, we will never look in the
1235          * external dictionary context, since there is no value a table
1236          * entry can take that indicate a miss. In that case, we need
1237          * to bump the offset to something non-zero.
1238          */
1239         if (working_stream->internal_donotuse.currentOffset == 0) {
1240             working_stream->internal_donotuse.currentOffset = 64 KB;
1241         }
1242         working_stream->internal_donotuse.dictCtx = &(dictionary_stream->internal_donotuse);
1243     } else {
1244         working_stream->internal_donotuse.dictCtx = NULL;
1245     }
1246 }
1247
1248
1249 static void LZ4_renormDictT(LZ4_stream_t_internal* LZ4_dict, int nextSize)
1250 {
1251     if (LZ4_dict->currentOffset + nextSize > 0x80000000) {   /* potential ptrdiff_t overflow (32-bits mode) */
1252         /* rescale hash table */
1253         U32 const delta = LZ4_dict->currentOffset - 64 KB;
1254         const BYTE* dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize;
1255         int i;
1256         DEBUGLOG(4, "LZ4_renormDictT");
1257         for (i=0; i<LZ4_HASH_SIZE_U32; i++) {
1258             if (LZ4_dict->hashTable[i] < delta) LZ4_dict->hashTable[i]=0;
1259             else LZ4_dict->hashTable[i] -= delta;
1260         }
1261         LZ4_dict->currentOffset = 64 KB;
1262         if (LZ4_dict->dictSize > 64 KB) LZ4_dict->dictSize = 64 KB;
1263         LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize;
1264     }
1265 }
1266
1267
1268 int LZ4_compress_fast_continue (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
1269 {
1270     const tableType_t tableType = byU32;
1271     LZ4_stream_t_internal* streamPtr = &LZ4_stream->internal_donotuse;
1272     const BYTE* dictEnd = streamPtr->dictionary + streamPtr->dictSize;
1273
1274     DEBUGLOG(5, "LZ4_compress_fast_continue (inputSize=%i)", inputSize);
1275
1276     if (streamPtr->initCheck) return 0;   /* Uninitialized structure detected */
1277     LZ4_renormDictT(streamPtr, inputSize);   /* avoid index overflow */
1278     if (acceleration < 1) acceleration = ACCELERATION_DEFAULT;
1279
1280     /* invalidate tiny dictionaries */
1281     if ( (streamPtr->dictSize-1 < 4)   /* intentional underflow */
1282       && (dictEnd != (const BYTE*)source) ) {
1283         DEBUGLOG(5, "LZ4_compress_fast_continue: dictSize(%u) at addr:%p is too small", streamPtr->dictSize, streamPtr->dictionary);
1284         streamPtr->dictSize = 0;
1285         streamPtr->dictionary = (const BYTE*)source;
1286         dictEnd = (const BYTE*)source;
1287     }
1288
1289     /* Check overlapping input/dictionary space */
1290     {   const BYTE* sourceEnd = (const BYTE*) source + inputSize;
1291         if ((sourceEnd > streamPtr->dictionary) && (sourceEnd < dictEnd)) {
1292             streamPtr->dictSize = (U32)(dictEnd - sourceEnd);
1293             if (streamPtr->dictSize > 64 KB) streamPtr->dictSize = 64 KB;
1294             if (streamPtr->dictSize < 4) streamPtr->dictSize = 0;
1295             streamPtr->dictionary = dictEnd - streamPtr->dictSize;
1296         }
1297     }
1298
1299     /* prefix mode : source data follows dictionary */
1300     if (dictEnd == (const BYTE*)source) {
1301         if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset))
1302             return LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, withPrefix64k, dictSmall, acceleration);
1303         else
1304             return LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, withPrefix64k, noDictIssue, acceleration);
1305     }
1306
1307     /* external dictionary mode */
1308     {   int result;
1309         if (streamPtr->dictCtx) {
1310             /* We depend here on the fact that dictCtx'es (produced by
1311              * LZ4_loadDict) guarantee that their tables contain no references
1312              * to offsets between dictCtx->currentOffset - 64 KB and
1313              * dictCtx->currentOffset - dictCtx->dictSize. This makes it safe
1314              * to use noDictIssue even when the dict isn't a full 64 KB.
1315              */
1316             if (inputSize > 4 KB) {
1317                 /* For compressing large blobs, it is faster to pay the setup
1318                  * cost to copy the dictionary's tables into the active context,
1319                  * so that the compression loop is only looking into one table.
1320                  */
1321                 memcpy(streamPtr, streamPtr->dictCtx, sizeof(LZ4_stream_t));
1322                 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, usingExtDict, noDictIssue, acceleration);
1323             } else {
1324                 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, usingDictCtx, noDictIssue, acceleration);
1325             }
1326         } else {
1327             if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) {
1328                 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, usingExtDict, dictSmall, acceleration);
1329             } else {
1330                 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, usingExtDict, noDictIssue, acceleration);
1331             }
1332         }
1333         streamPtr->dictionary = (const BYTE*)source;
1334         streamPtr->dictSize = (U32)inputSize;
1335         return result;
1336     }
1337 }
1338
1339
1340 /* Hidden debug function, to force-test external dictionary mode */
1341 int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int srcSize)
1342 {
1343     LZ4_stream_t_internal* streamPtr = &LZ4_dict->internal_donotuse;
1344     int result;
1345
1346     LZ4_renormDictT(streamPtr, srcSize);
1347
1348     if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) {
1349         result = LZ4_compress_generic(streamPtr, source, dest, srcSize, NULL, 0, notLimited, byU32, usingExtDict, dictSmall, 1);
1350     } else {
1351         result = LZ4_compress_generic(streamPtr, source, dest, srcSize, NULL, 0, notLimited, byU32, usingExtDict, noDictIssue, 1);
1352     }
1353
1354     streamPtr->dictionary = (const BYTE*)source;
1355     streamPtr->dictSize = (U32)srcSize;
1356
1357     return result;
1358 }
1359
1360
1361 /*! LZ4_saveDict() :
1362  *  If previously compressed data block is not guaranteed to remain available at its memory location,
1363  *  save it into a safer place (char* safeBuffer).
1364  *  Note : you don't need to call LZ4_loadDict() afterwards,
1365  *         dictionary is immediately usable, you can therefore call LZ4_compress_fast_continue().
1366  *  Return : saved dictionary size in bytes (necessarily <= dictSize), or 0 if error.
1367  */
1368 int LZ4_saveDict (LZ4_stream_t* LZ4_dict, char* safeBuffer, int dictSize)
1369 {
1370     LZ4_stream_t_internal* const dict = &LZ4_dict->internal_donotuse;
1371     const BYTE* const previousDictEnd = dict->dictionary + dict->dictSize;
1372
1373     if ((U32)dictSize > 64 KB) dictSize = 64 KB;   /* useless to define a dictionary > 64 KB */
1374     if ((U32)dictSize > dict->dictSize) dictSize = dict->dictSize;
1375
1376     memmove(safeBuffer, previousDictEnd - dictSize, dictSize);
1377
1378     dict->dictionary = (const BYTE*)safeBuffer;
1379     dict->dictSize = (U32)dictSize;
1380
1381     return dictSize;
1382 }
1383
1384
1385
1386 /*-*******************************
1387  *  Decompression functions
1388  ********************************/
1389
1390 typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;
1391 typedef enum { decode_full_block = 0, partial_decode = 1 } earlyEnd_directive;
1392
1393 #undef MIN
1394 #define MIN(a,b)    ( (a) < (b) ? (a) : (b) )
1395
1396 /*! LZ4_decompress_generic() :
1397  *  This generic decompression function covers all use cases.
1398  *  It shall be instantiated several times, using different sets of directives.
1399  *  Note that it is important for performance that this function really get inlined,
1400  *  in order to remove useless branches during compilation optimization.
1401  */
1402 LZ4_FORCE_INLINE int
1403 LZ4_decompress_generic(
1404                  const char* const src,
1405                  char* const dst,
1406                  int srcSize,
1407                  int outputSize,         /* If endOnInput==endOnInputSize, this value is `dstCapacity` */
1408
1409                  endCondition_directive endOnInput,   /* endOnOutputSize, endOnInputSize */
1410                  earlyEnd_directive partialDecoding,  /* full, partial */
1411                  dict_directive dict,                 /* noDict, withPrefix64k, usingExtDict */
1412                  const BYTE* const lowPrefix,  /* always <= dst, == dst when no prefix */
1413                  const BYTE* const dictStart,  /* only if dict==usingExtDict */
1414                  const size_t dictSize         /* note : = 0 if noDict */
1415                  )
1416 {
1417     const BYTE* ip = (const BYTE*) src;
1418     const BYTE* const iend = ip + srcSize;
1419
1420     BYTE* op = (BYTE*) dst;
1421     BYTE* const oend = op + outputSize;
1422     BYTE* cpy;
1423
1424     const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize;
1425     const unsigned inc32table[8] = {0, 1, 2,  1,  0,  4, 4, 4};
1426     const int      dec64table[8] = {0, 0, 0, -1, -4,  1, 2, 3};
1427
1428     const int safeDecode = (endOnInput==endOnInputSize);
1429     const int checkOffset = ((safeDecode) && (dictSize < (int)(64 KB)));
1430
1431     /* Set up the "end" pointers for the shortcut. */
1432     const BYTE* const shortiend = iend - (endOnInput ? 14 : 8) /*maxLL*/ - 2 /*offset*/;
1433     const BYTE* const shortoend = oend - (endOnInput ? 14 : 8) /*maxLL*/ - 18 /*maxML*/;
1434
1435     DEBUGLOG(5, "LZ4_decompress_generic (srcSize:%i, dstSize:%i)", srcSize, outputSize);
1436
1437     /* Special cases */
1438     assert(lowPrefix <= op);
1439     assert(src != NULL);
1440     if ((endOnInput) && (unlikely(outputSize==0))) return ((srcSize==1) && (*ip==0)) ? 0 : -1;  /* Empty output buffer */
1441     if ((!endOnInput) && (unlikely(outputSize==0))) return (*ip==0 ? 1 : -1);
1442     if ((endOnInput) && unlikely(srcSize==0)) return -1;
1443
1444     /* Main Loop : decode sequences */
1445     while (1) {
1446         const BYTE* match;
1447         size_t offset;
1448
1449         unsigned const token = *ip++;
1450         size_t length = token >> ML_BITS;  /* literal length */
1451
1452         assert(!endOnInput || ip <= iend); /* ip < iend before the increment */
1453
1454         /* A two-stage shortcut for the most common case:
1455          * 1) If the literal length is 0..14, and there is enough space,
1456          * enter the shortcut and copy 16 bytes on behalf of the literals
1457          * (in the fast mode, only 8 bytes can be safely copied this way).
1458          * 2) Further if the match length is 4..18, copy 18 bytes in a similar
1459          * manner; but we ensure that there's enough space in the output for
1460          * those 18 bytes earlier, upon entering the shortcut (in other words,
1461          * there is a combined check for both stages).
1462          */
1463         if ( (endOnInput ? length != RUN_MASK : length <= 8)
1464             /* strictly "less than" on input, to re-enter the loop with at least one byte */
1465           && likely((endOnInput ? ip < shortiend : 1) & (op <= shortoend)) ) {
1466             /* Copy the literals */
1467             memcpy(op, ip, endOnInput ? 16 : 8);
1468             op += length; ip += length;
1469
1470             /* The second stage: prepare for match copying, decode full info.
1471              * If it doesn't work out, the info won't be wasted. */
1472             length = token & ML_MASK; /* match length */
1473             offset = LZ4_readLE16(ip); ip += 2;
1474             match = op - offset;
1475             assert(match <= op); /* check overflow */
1476
1477             /* Do not deal with overlapping matches. */
1478             if ( (length != ML_MASK)
1479               && (offset >= 8)
1480               && (dict==withPrefix64k || match >= lowPrefix) ) {
1481                 /* Copy the match. */
1482                 memcpy(op + 0, match + 0, 8);
1483                 memcpy(op + 8, match + 8, 8);
1484                 memcpy(op +16, match +16, 2);
1485                 op += length + MINMATCH;
1486                 /* Both stages worked, load the next token. */
1487                 continue;
1488             }
1489
1490             /* The second stage didn't work out, but the info is ready.
1491              * Propel it right to the point of match copying. */
1492             goto _copy_match;
1493         }
1494
1495         /* decode literal length */
1496         if (length == RUN_MASK) {
1497             unsigned s;
1498             if (unlikely(endOnInput ? ip >= iend-RUN_MASK : 0)) goto _output_error;   /* overflow detection */
1499             do {
1500                 s = *ip++;
1501                 length += s;
1502             } while ( likely(endOnInput ? ip<iend-RUN_MASK : 1) & (s==255) );
1503             if ((safeDecode) && unlikely((uptrval)(op)+length<(uptrval)(op))) goto _output_error;   /* overflow detection */
1504             if ((safeDecode) && unlikely((uptrval)(ip)+length<(uptrval)(ip))) goto _output_error;   /* overflow detection */
1505         }
1506
1507         /* copy literals */
1508         cpy = op+length;
1509         LZ4_STATIC_ASSERT(MFLIMIT >= WILDCOPYLENGTH);
1510         if ( ((endOnInput) && ((cpy>oend-MFLIMIT) || (ip+length>iend-(2+1+LASTLITERALS))) )
1511           || ((!endOnInput) && (cpy>oend-WILDCOPYLENGTH)) )
1512         {
1513             if (partialDecoding) {
1514                 if (cpy > oend) { cpy = oend; length = oend-op; }             /* Partial decoding : stop in the middle of literal segment */
1515                 if ((endOnInput) && (ip+length > iend)) goto _output_error;   /* Error : read attempt beyond end of input buffer */
1516             } else {
1517                 if ((!endOnInput) && (cpy != oend)) goto _output_error;       /* Error : block decoding must stop exactly there */
1518                 if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) goto _output_error;   /* Error : input must be consumed */
1519             }
1520             memcpy(op, ip, length);
1521             ip += length;
1522             op += length;
1523             if (!partialDecoding || (cpy == oend)) {
1524                 /* Necessarily EOF, due to parsing restrictions */
1525                 break;
1526             }
1527
1528         } else {
1529             LZ4_wildCopy(op, ip, cpy);   /* may overwrite up to WILDCOPYLENGTH beyond cpy */
1530             ip += length; op = cpy;
1531         }
1532
1533         /* get offset */
1534         offset = LZ4_readLE16(ip); ip+=2;
1535         match = op - offset;
1536
1537         /* get matchlength */
1538         length = token & ML_MASK;
1539
1540 _copy_match:
1541         if ((checkOffset) && (unlikely(match + dictSize < lowPrefix))) goto _output_error;   /* Error : offset outside buffers */
1542         if (!partialDecoding) {
1543             assert(oend > op);
1544             assert(oend - op >= 4);
1545             LZ4_write32(op, 0);   /* silence an msan warning when offset==0; costs <1%; */
1546         }   /* note : when partialDecoding, there is no guarantee that at least 4 bytes remain available in output buffer */
1547
1548         if (length == ML_MASK) {
1549             unsigned s;
1550             do {
1551                 s = *ip++;
1552                 if ((endOnInput) && (ip > iend-LASTLITERALS)) goto _output_error;
1553                 length += s;
1554             } while (s==255);
1555             if ((safeDecode) && unlikely((uptrval)(op)+length<(uptrval)op)) goto _output_error;   /* overflow detection */
1556         }
1557         length += MINMATCH;
1558
1559         /* match starting within external dictionary */
1560         if ((dict==usingExtDict) && (match < lowPrefix)) {
1561             if (unlikely(op+length > oend-LASTLITERALS)) {
1562                 if (partialDecoding) length = MIN(length, (size_t)(oend-op));
1563                 else goto _output_error;   /* doesn't respect parsing restriction */
1564             }
1565
1566             if (length <= (size_t)(lowPrefix-match)) {
1567                 /* match fits entirely within external dictionary : just copy */
1568                 memmove(op, dictEnd - (lowPrefix-match), length);
1569                 op += length;
1570             } else {
1571                 /* match stretches into both external dictionary and current block */
1572                 size_t const copySize = (size_t)(lowPrefix - match);
1573                 size_t const restSize = length - copySize;
1574                 memcpy(op, dictEnd - copySize, copySize);
1575                 op += copySize;
1576                 if (restSize > (size_t)(op - lowPrefix)) {  /* overlap copy */
1577                     BYTE* const endOfMatch = op + restSize;
1578                     const BYTE* copyFrom = lowPrefix;
1579                     while (op < endOfMatch) *op++ = *copyFrom++;
1580                 } else {
1581                     memcpy(op, lowPrefix, restSize);
1582                     op += restSize;
1583             }   }
1584             continue;
1585         }
1586
1587         /* copy match within block */
1588         cpy = op + length;
1589
1590         /* partialDecoding : may not respect endBlock parsing restrictions */
1591         assert(op<=oend);
1592         if (partialDecoding && (cpy > oend-MATCH_SAFEGUARD_DISTANCE)) {
1593             size_t const mlen = MIN(length, (size_t)(oend-op));
1594             const BYTE* const matchEnd = match + mlen;
1595             BYTE* const copyEnd = op + mlen;
1596             if (matchEnd > op) {   /* overlap copy */
1597                 while (op < copyEnd) *op++ = *match++;
1598             } else {
1599                 memcpy(op, match, mlen);
1600             }
1601             op = copyEnd;
1602             if (op==oend) break;
1603             continue;
1604         }
1605
1606         if (unlikely(offset<8)) {
1607             op[0] = match[0];
1608             op[1] = match[1];
1609             op[2] = match[2];
1610             op[3] = match[3];
1611             match += inc32table[offset];
1612             memcpy(op+4, match, 4);
1613             match -= dec64table[offset];
1614         } else {
1615             memcpy(op, match, 8);
1616             match += 8;
1617         }
1618         op += 8;
1619
1620         if (unlikely(cpy > oend-MATCH_SAFEGUARD_DISTANCE)) {
1621             BYTE* const oCopyLimit = oend - (WILDCOPYLENGTH-1);
1622             if (cpy > oend-LASTLITERALS) goto _output_error;    /* Error : last LASTLITERALS bytes must be literals (uncompressed) */
1623             if (op < oCopyLimit) {
1624                 LZ4_wildCopy(op, match, oCopyLimit);
1625                 match += oCopyLimit - op;
1626                 op = oCopyLimit;
1627             }
1628             while (op < cpy) *op++ = *match++;
1629         } else {
1630             memcpy(op, match, 8);
1631             if (length > 16) LZ4_wildCopy(op+8, match+8, cpy);
1632         }
1633         op = cpy;   /* wildcopy correction */
1634     }
1635
1636     /* end of decoding */
1637     if (endOnInput)
1638        return (int) (((char*)op)-dst);     /* Nb of output bytes decoded */
1639     else
1640        return (int) (((const char*)ip)-src);   /* Nb of input bytes read */
1641
1642     /* Overflow error detected */
1643 _output_error:
1644     return (int) (-(((const char*)ip)-src))-1;
1645 }
1646
1647
1648 /*===== Instantiate the API decoding functions. =====*/
1649
1650 LZ4_FORCE_O2_GCC_PPC64LE
1651 int LZ4_decompress_safe(const char* source, char* dest, int compressedSize, int maxDecompressedSize)
1652 {
1653     return LZ4_decompress_generic(source, dest, compressedSize, maxDecompressedSize,
1654                                   endOnInputSize, decode_full_block, noDict,
1655                                   (BYTE*)dest, NULL, 0);
1656 }
1657
1658 LZ4_FORCE_O2_GCC_PPC64LE
1659 int LZ4_decompress_safe_partial(const char* src, char* dst, int compressedSize, int targetOutputSize, int dstCapacity)
1660 {
1661     dstCapacity = MIN(targetOutputSize, dstCapacity);
1662     return LZ4_decompress_generic(src, dst, compressedSize, dstCapacity,
1663                                   endOnInputSize, partial_decode,
1664                                   noDict, (BYTE*)dst, NULL, 0);
1665 }
1666
1667 LZ4_FORCE_O2_GCC_PPC64LE
1668 int LZ4_decompress_fast(const char* source, char* dest, int originalSize)
1669 {
1670     return LZ4_decompress_generic(source, dest, 0, originalSize,
1671                                   endOnOutputSize, decode_full_block, withPrefix64k,
1672                                   (BYTE*)dest - 64 KB, NULL, 0);
1673 }
1674
1675 /*===== Instantiate a few more decoding cases, used more than once. =====*/
1676
1677 LZ4_FORCE_O2_GCC_PPC64LE /* Exported, an obsolete API function. */
1678 int LZ4_decompress_safe_withPrefix64k(const char* source, char* dest, int compressedSize, int maxOutputSize)
1679 {
1680     return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
1681                                   endOnInputSize, decode_full_block, withPrefix64k,
1682                                   (BYTE*)dest - 64 KB, NULL, 0);
1683 }
1684
1685 /* Another obsolete API function, paired with the previous one. */
1686 int LZ4_decompress_fast_withPrefix64k(const char* source, char* dest, int originalSize)
1687 {
1688     /* LZ4_decompress_fast doesn't validate match offsets,
1689      * and thus serves well with any prefixed dictionary. */
1690     return LZ4_decompress_fast(source, dest, originalSize);
1691 }
1692
1693 LZ4_FORCE_O2_GCC_PPC64LE
1694 static int LZ4_decompress_safe_withSmallPrefix(const char* source, char* dest, int compressedSize, int maxOutputSize,
1695                                                size_t prefixSize)
1696 {
1697     return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
1698                                   endOnInputSize, decode_full_block, noDict,
1699                                   (BYTE*)dest-prefixSize, NULL, 0);
1700 }
1701
1702 LZ4_FORCE_O2_GCC_PPC64LE
1703 int LZ4_decompress_safe_forceExtDict(const char* source, char* dest,
1704                                      int compressedSize, int maxOutputSize,
1705                                      const void* dictStart, size_t dictSize)
1706 {
1707     return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
1708                                   endOnInputSize, decode_full_block, usingExtDict,
1709                                   (BYTE*)dest, (const BYTE*)dictStart, dictSize);
1710 }
1711
1712 LZ4_FORCE_O2_GCC_PPC64LE
1713 static int LZ4_decompress_fast_extDict(const char* source, char* dest, int originalSize,
1714                                        const void* dictStart, size_t dictSize)
1715 {
1716     return LZ4_decompress_generic(source, dest, 0, originalSize,
1717                                   endOnOutputSize, decode_full_block, usingExtDict,
1718                                   (BYTE*)dest, (const BYTE*)dictStart, dictSize);
1719 }
1720
1721 /* The "double dictionary" mode, for use with e.g. ring buffers: the first part
1722  * of the dictionary is passed as prefix, and the second via dictStart + dictSize.
1723  * These routines are used only once, in LZ4_decompress_*_continue().
1724  */
1725 LZ4_FORCE_INLINE
1726 int LZ4_decompress_safe_doubleDict(const char* source, char* dest, int compressedSize, int maxOutputSize,
1727                                    size_t prefixSize, const void* dictStart, size_t dictSize)
1728 {
1729     return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
1730                                   endOnInputSize, decode_full_block, usingExtDict,
1731                                   (BYTE*)dest-prefixSize, (const BYTE*)dictStart, dictSize);
1732 }
1733
1734 LZ4_FORCE_INLINE
1735 int LZ4_decompress_fast_doubleDict(const char* source, char* dest, int originalSize,
1736                                    size_t prefixSize, const void* dictStart, size_t dictSize)
1737 {
1738     return LZ4_decompress_generic(source, dest, 0, originalSize,
1739                                   endOnOutputSize, decode_full_block, usingExtDict,
1740                                   (BYTE*)dest-prefixSize, (const BYTE*)dictStart, dictSize);
1741 }
1742
1743 /*===== streaming decompression functions =====*/
1744
1745 LZ4_streamDecode_t* LZ4_createStreamDecode(void)
1746 {
1747     LZ4_streamDecode_t* lz4s = (LZ4_streamDecode_t*) ALLOC_AND_ZERO(sizeof(LZ4_streamDecode_t));
1748     return lz4s;
1749 }
1750
1751 int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream)
1752 {
1753     if (!LZ4_stream) return 0;   /* support free on NULL */
1754     FREEMEM(LZ4_stream);
1755     return 0;
1756 }
1757
1758 /*! LZ4_setStreamDecode() :
1759  *  Use this function to instruct where to find the dictionary.
1760  *  This function is not necessary if previous data is still available where it was decoded.
1761  *  Loading a size of 0 is allowed (same effect as no dictionary).
1762  * @return : 1 if OK, 0 if error
1763  */
1764 int LZ4_setStreamDecode (LZ4_streamDecode_t* LZ4_streamDecode, const char* dictionary, int dictSize)
1765 {
1766     LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse;
1767     lz4sd->prefixSize = (size_t) dictSize;
1768     lz4sd->prefixEnd = (const BYTE*) dictionary + dictSize;
1769     lz4sd->externalDict = NULL;
1770     lz4sd->extDictSize  = 0;
1771     return 1;
1772 }
1773
1774 /*! LZ4_decoderRingBufferSize() :
1775  *  when setting a ring buffer for streaming decompression (optional scenario),
1776  *  provides the minimum size of this ring buffer
1777  *  to be compatible with any source respecting maxBlockSize condition.
1778  *  Note : in a ring buffer scenario,
1779  *  blocks are presumed decompressed next to each other.
1780  *  When not enough space remains for next block (remainingSize < maxBlockSize),
1781  *  decoding resumes from beginning of ring buffer.
1782  * @return : minimum ring buffer size,
1783  *           or 0 if there is an error (invalid maxBlockSize).
1784  */
1785 int LZ4_decoderRingBufferSize(int maxBlockSize)
1786 {
1787     if (maxBlockSize < 0) return 0;
1788     if (maxBlockSize > LZ4_MAX_INPUT_SIZE) return 0;
1789     if (maxBlockSize < 16) maxBlockSize = 16;
1790     return LZ4_DECODER_RING_BUFFER_SIZE(maxBlockSize);
1791 }
1792
1793 /*
1794 *_continue() :
1795     These decoding functions allow decompression of multiple blocks in "streaming" mode.
1796     Previously decoded blocks must still be available at the memory position where they were decoded.
1797     If it's not possible, save the relevant part of decoded data into a safe buffer,
1798     and indicate where it stands using LZ4_setStreamDecode()
1799 */
1800 LZ4_FORCE_O2_GCC_PPC64LE
1801 int LZ4_decompress_safe_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int compressedSize, int maxOutputSize)
1802 {
1803     LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse;
1804     int result;
1805
1806     if (lz4sd->prefixSize == 0) {
1807         /* The first call, no dictionary yet. */
1808         assert(lz4sd->extDictSize == 0);
1809         result = LZ4_decompress_safe(source, dest, compressedSize, maxOutputSize);
1810         if (result <= 0) return result;
1811         lz4sd->prefixSize = result;
1812         lz4sd->prefixEnd = (BYTE*)dest + result;
1813     } else if (lz4sd->prefixEnd == (BYTE*)dest) {
1814         /* They're rolling the current segment. */
1815         if (lz4sd->prefixSize >= 64 KB - 1)
1816             result = LZ4_decompress_safe_withPrefix64k(source, dest, compressedSize, maxOutputSize);
1817         else if (lz4sd->extDictSize == 0)
1818             result = LZ4_decompress_safe_withSmallPrefix(source, dest, compressedSize, maxOutputSize,
1819                                                          lz4sd->prefixSize);
1820         else
1821             result = LZ4_decompress_safe_doubleDict(source, dest, compressedSize, maxOutputSize,
1822                                                     lz4sd->prefixSize, lz4sd->externalDict, lz4sd->extDictSize);
1823         if (result <= 0) return result;
1824         lz4sd->prefixSize += result;
1825         lz4sd->prefixEnd  += result;
1826     } else {
1827         /* The buffer wraps around, or they're switching to another buffer. */
1828         lz4sd->extDictSize = lz4sd->prefixSize;
1829         lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize;
1830         result = LZ4_decompress_safe_forceExtDict(source, dest, compressedSize, maxOutputSize,
1831                                                   lz4sd->externalDict, lz4sd->extDictSize);
1832         if (result <= 0) return result;
1833         lz4sd->prefixSize = result;
1834         lz4sd->prefixEnd  = (BYTE*)dest + result;
1835     }
1836
1837     return result;
1838 }
1839
1840 LZ4_FORCE_O2_GCC_PPC64LE
1841 int LZ4_decompress_fast_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int originalSize)
1842 {
1843     LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse;
1844     int result;
1845
1846     if (lz4sd->prefixSize == 0) {
1847         assert(lz4sd->extDictSize == 0);
1848         result = LZ4_decompress_fast(source, dest, originalSize);
1849         if (result <= 0) return result;
1850         lz4sd->prefixSize = originalSize;
1851         lz4sd->prefixEnd = (BYTE*)dest + originalSize;
1852     } else if (lz4sd->prefixEnd == (BYTE*)dest) {
1853         if (lz4sd->prefixSize >= 64 KB - 1 || lz4sd->extDictSize == 0)
1854             result = LZ4_decompress_fast(source, dest, originalSize);
1855         else
1856             result = LZ4_decompress_fast_doubleDict(source, dest, originalSize,
1857                                                     lz4sd->prefixSize, lz4sd->externalDict, lz4sd->extDictSize);
1858         if (result <= 0) return result;
1859         lz4sd->prefixSize += originalSize;
1860         lz4sd->prefixEnd  += originalSize;
1861     } else {
1862         lz4sd->extDictSize = lz4sd->prefixSize;
1863         lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize;
1864         result = LZ4_decompress_fast_extDict(source, dest, originalSize,
1865                                              lz4sd->externalDict, lz4sd->extDictSize);
1866         if (result <= 0) return result;
1867         lz4sd->prefixSize = originalSize;
1868         lz4sd->prefixEnd  = (BYTE*)dest + originalSize;
1869     }
1870
1871     return result;
1872 }
1873
1874
1875 /*
1876 Advanced decoding functions :
1877 *_usingDict() :
1878     These decoding functions work the same as "_continue" ones,
1879     the dictionary must be explicitly provided within parameters
1880 */
1881
1882 int LZ4_decompress_safe_usingDict(const char* source, char* dest, int compressedSize, int maxOutputSize, const char* dictStart, int dictSize)
1883 {
1884     if (dictSize==0)
1885         return LZ4_decompress_safe(source, dest, compressedSize, maxOutputSize);
1886     if (dictStart+dictSize == dest) {
1887         if (dictSize >= 64 KB - 1)
1888             return LZ4_decompress_safe_withPrefix64k(source, dest, compressedSize, maxOutputSize);
1889         return LZ4_decompress_safe_withSmallPrefix(source, dest, compressedSize, maxOutputSize, dictSize);
1890     }
1891     return LZ4_decompress_safe_forceExtDict(source, dest, compressedSize, maxOutputSize, dictStart, dictSize);
1892 }
1893
1894 int LZ4_decompress_fast_usingDict(const char* source, char* dest, int originalSize, const char* dictStart, int dictSize)
1895 {
1896     if (dictSize==0 || dictStart+dictSize == dest)
1897         return LZ4_decompress_fast(source, dest, originalSize);
1898     return LZ4_decompress_fast_extDict(source, dest, originalSize, dictStart, dictSize);
1899 }
1900
1901
1902 /*=*************************************************
1903 *  Obsolete Functions
1904 ***************************************************/
1905 /* obsolete compression functions */
1906 int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize)
1907 {
1908     return LZ4_compress_default(source, dest, inputSize, maxOutputSize);
1909 }
1910 int LZ4_compress(const char* source, char* dest, int inputSize)
1911 {
1912     return LZ4_compress_default(source, dest, inputSize, LZ4_compressBound(inputSize));
1913 }
1914 int LZ4_compress_limitedOutput_withState (void* state, const char* src, char* dst, int srcSize, int dstSize)
1915 {
1916     return LZ4_compress_fast_extState(state, src, dst, srcSize, dstSize, 1);
1917 }
1918 int LZ4_compress_withState (void* state, const char* src, char* dst, int srcSize)
1919 {
1920     return LZ4_compress_fast_extState(state, src, dst, srcSize, LZ4_compressBound(srcSize), 1);
1921 }
1922 int LZ4_compress_limitedOutput_continue (LZ4_stream_t* LZ4_stream, const char* src, char* dst, int srcSize, int dstCapacity)
1923 {
1924     return LZ4_compress_fast_continue(LZ4_stream, src, dst, srcSize, dstCapacity, 1);
1925 }
1926 int LZ4_compress_continue (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize)
1927 {
1928     return LZ4_compress_fast_continue(LZ4_stream, source, dest, inputSize, LZ4_compressBound(inputSize), 1);
1929 }
1930
1931 /*
1932 These decompression functions are deprecated and should no longer be used.
1933 They are only provided here for compatibility with older user programs.
1934 - LZ4_uncompress is totally equivalent to LZ4_decompress_fast
1935 - LZ4_uncompress_unknownOutputSize is totally equivalent to LZ4_decompress_safe
1936 */
1937 int LZ4_uncompress (const char* source, char* dest, int outputSize)
1938 {
1939     return LZ4_decompress_fast(source, dest, outputSize);
1940 }
1941 int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize)
1942 {
1943     return LZ4_decompress_safe(source, dest, isize, maxOutputSize);
1944 }
1945
1946 /* Obsolete Streaming functions */
1947
1948 int LZ4_sizeofStreamState() { return LZ4_STREAMSIZE; }
1949
1950 int LZ4_resetStreamState(void* state, char* inputBuffer)
1951 {
1952     (void)inputBuffer;
1953     LZ4_resetStream((LZ4_stream_t*)state);
1954     return 0;
1955 }
1956
1957 void* LZ4_create (char* inputBuffer)
1958 {
1959     (void)inputBuffer;
1960     return LZ4_createStream();
1961 }
1962
1963 char* LZ4_slideInputBuffer (void* state)
1964 {
1965     /* avoid const char * -> char * conversion warning */
1966     return (char *)(uptrval)((LZ4_stream_t*)state)->internal_donotuse.dictionary;
1967 }
1968
1969 #endif   /* LZ4_COMMONDEFS_ONLY */