Avoid warnings from -fsanitize=integer in the hash functions.
[tinc] / src / lib / lz4 / lz4.c
1 /*
2    LZ4 - Fast LZ compression algorithm
3    Copyright (C) 2011-2020, 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 *  Tuning parameters
37 **************************************/
38 /*
39  * LZ4_HEAPMODE :
40  * Select how default compression functions will allocate memory for their hash table,
41  * in memory stack (0:default, fastest), or in memory heap (1:requires malloc()).
42  */
43 #ifndef LZ4_HEAPMODE
44 #  define LZ4_HEAPMODE 0
45 #endif
46
47 /*
48  * LZ4_ACCELERATION_DEFAULT :
49  * Select "acceleration" for LZ4_compress_fast() when parameter value <= 0
50  */
51 #define LZ4_ACCELERATION_DEFAULT 1
52 /*
53  * LZ4_ACCELERATION_MAX :
54  * Any "acceleration" value higher than this threshold
55  * get treated as LZ4_ACCELERATION_MAX instead (fix #876)
56  */
57 #define LZ4_ACCELERATION_MAX 65537
58
59
60 /*-************************************
61 *  CPU Feature Detection
62 **************************************/
63 /* LZ4_FORCE_MEMORY_ACCESS
64  * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
65  * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
66  * The below switch allow to select different access method for improved performance.
67  * Method 0 (default) : use `memcpy()`. Safe and portable.
68  * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
69  *            This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
70  * Method 2 : direct access. This method is portable but violate C standard.
71  *            It can generate buggy code on targets which assembly generation depends on alignment.
72  *            But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
73  * See https://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
74  * Prefer these methods in priority order (0 > 1 > 2)
75  */
76 #ifndef LZ4_FORCE_MEMORY_ACCESS   /* can be defined externally */
77 #  if defined(__GNUC__) && \
78   ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) \
79   || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) )
80 #    define LZ4_FORCE_MEMORY_ACCESS 2
81 #  elif (defined(__INTEL_COMPILER) && !defined(_WIN32)) || defined(__GNUC__)
82 #    define LZ4_FORCE_MEMORY_ACCESS 1
83 #  endif
84 #endif
85
86 /*
87  * LZ4_FORCE_SW_BITCOUNT
88  * Define this parameter if your target system or compiler does not support hardware bit count
89  */
90 #if defined(_MSC_VER) && defined(_WIN32_WCE)   /* Visual Studio for WinCE doesn't support Hardware bit count */
91 #  undef  LZ4_FORCE_SW_BITCOUNT  /* avoid double def */
92 #  define LZ4_FORCE_SW_BITCOUNT
93 #endif
94
95
96
97 /*-************************************
98 *  Dependency
99 **************************************/
100 /*
101  * LZ4_SRC_INCLUDED:
102  * Amalgamation flag, whether lz4.c is included
103  */
104 #ifndef LZ4_SRC_INCLUDED
105 #  define LZ4_SRC_INCLUDED 1
106 #endif
107
108 #ifndef LZ4_STATIC_LINKING_ONLY
109 #define LZ4_STATIC_LINKING_ONLY
110 #endif
111
112 #ifndef LZ4_DISABLE_DEPRECATE_WARNINGS
113 #define LZ4_DISABLE_DEPRECATE_WARNINGS /* due to LZ4_decompress_safe_withPrefix64k */
114 #endif
115
116 #define LZ4_STATIC_LINKING_ONLY  /* LZ4_DISTANCE_MAX */
117 #include "lz4.h"
118 /* see also "memory routines" below */
119
120
121 /*-************************************
122 *  Compiler Options
123 **************************************/
124 #if defined(_MSC_VER) && (_MSC_VER >= 1400)  /* Visual Studio 2005+ */
125 #  include <intrin.h>               /* only present in VS2005+ */
126 #  pragma warning(disable : 4127)   /* disable: C4127: conditional expression is constant */
127 #endif  /* _MSC_VER */
128
129 #ifndef LZ4_FORCE_INLINE
130 #  ifdef _MSC_VER    /* Visual Studio */
131 #    define LZ4_FORCE_INLINE static __forceinline
132 #  else
133 #    if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L   /* C99 */
134 #      ifdef __GNUC__
135 #        define LZ4_FORCE_INLINE static inline __attribute__((always_inline))
136 #      else
137 #        define LZ4_FORCE_INLINE static inline
138 #      endif
139 #    else
140 #      define LZ4_FORCE_INLINE static
141 #    endif /* __STDC_VERSION__ */
142 #  endif  /* _MSC_VER */
143 #endif /* LZ4_FORCE_INLINE */
144
145 /* LZ4_FORCE_O2 and LZ4_FORCE_INLINE
146  * gcc on ppc64le generates an unrolled SIMDized loop for LZ4_wildCopy8,
147  * together with a simple 8-byte copy loop as a fall-back path.
148  * However, this optimization hurts the decompression speed by >30%,
149  * because the execution does not go to the optimized loop
150  * for typical compressible data, and all of the preamble checks
151  * before going to the fall-back path become useless overhead.
152  * This optimization happens only with the -O3 flag, and -O2 generates
153  * a simple 8-byte copy loop.
154  * With gcc on ppc64le, all of the LZ4_decompress_* and LZ4_wildCopy8
155  * functions are annotated with __attribute__((optimize("O2"))),
156  * and also LZ4_wildCopy8 is forcibly inlined, so that the O2 attribute
157  * of LZ4_wildCopy8 does not affect the compression speed.
158  */
159 #if defined(__PPC64__) && defined(__LITTLE_ENDIAN__) && defined(__GNUC__) && !defined(__clang__)
160 #  define LZ4_FORCE_O2  __attribute__((optimize("O2")))
161 #  undef LZ4_FORCE_INLINE
162 #  define LZ4_FORCE_INLINE  static __inline __attribute__((optimize("O2"),always_inline))
163 #else
164 #  define LZ4_FORCE_O2
165 #endif
166
167 #if (defined(__GNUC__) && (__GNUC__ >= 3)) || (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 800)) || defined(__clang__)
168 #  define expect(expr,value)    (__builtin_expect ((expr),(value)) )
169 #else
170 #  define expect(expr,value)    (expr)
171 #endif
172
173 #ifndef likely
174 #define likely(expr)     expect((expr) != 0, 1)
175 #endif
176 #ifndef unlikely
177 #define unlikely(expr)   expect((expr) != 0, 0)
178 #endif
179
180 /* Should the alignment test prove unreliable, for some reason,
181  * it can be disabled by setting LZ4_ALIGN_TEST to 0 */
182 #ifndef LZ4_ALIGN_TEST  /* can be externally provided */
183 # define LZ4_ALIGN_TEST 1
184 #endif
185
186
187 /*-************************************
188 *  Memory routines
189 **************************************/
190 #ifdef LZ4_USER_MEMORY_FUNCTIONS
191 /* memory management functions can be customized by user project.
192  * Below functions must exist somewhere in the Project
193  * and be available at link time */
194 void* LZ4_malloc(size_t s);
195 void* LZ4_calloc(size_t n, size_t s);
196 void  LZ4_free(void* p);
197 # define ALLOC(s)          LZ4_malloc(s)
198 # define ALLOC_AND_ZERO(s) LZ4_calloc(1,s)
199 # define FREEMEM(p)        LZ4_free(p)
200 #else
201 # include <stdlib.h>   /* malloc, calloc, free */
202 # define ALLOC(s)          malloc(s)
203 # define ALLOC_AND_ZERO(s) calloc(1,s)
204 # define FREEMEM(p)        free(p)
205 #endif
206
207 #include <string.h>   /* memset, memcpy */
208 #define MEM_INIT(p,v,s)   memset((p),(v),(s))
209
210
211 /*-************************************
212 *  Common Constants
213 **************************************/
214 #define MINMATCH 4
215
216 #define WILDCOPYLENGTH 8
217 #define LASTLITERALS   5   /* see ../doc/lz4_Block_format.md#parsing-restrictions */
218 #define MFLIMIT       12   /* see ../doc/lz4_Block_format.md#parsing-restrictions */
219 #define MATCH_SAFEGUARD_DISTANCE  ((2*WILDCOPYLENGTH) - MINMATCH)   /* ensure it's possible to write 2 x wildcopyLength without overflowing output buffer */
220 #define FASTLOOP_SAFE_DISTANCE 64
221 static const int LZ4_minLength = (MFLIMIT+1);
222
223 #define KB *(1 <<10)
224 #define MB *(1 <<20)
225 #define GB *(1U<<30)
226
227 #define LZ4_DISTANCE_ABSOLUTE_MAX 65535
228 #if (LZ4_DISTANCE_MAX > LZ4_DISTANCE_ABSOLUTE_MAX)   /* max supported by LZ4 format */
229 #  error "LZ4_DISTANCE_MAX is too big : must be <= 65535"
230 #endif
231
232 #define ML_BITS  4
233 #define ML_MASK  ((1U<<ML_BITS)-1)
234 #define RUN_BITS (8-ML_BITS)
235 #define RUN_MASK ((1U<<RUN_BITS)-1)
236
237
238 /*-************************************
239 *  Error detection
240 **************************************/
241 #if defined(LZ4_DEBUG) && (LZ4_DEBUG>=1)
242 #  include <assert.h>
243 #else
244 #  ifndef assert
245 #    define assert(condition) ((void)0)
246 #  endif
247 #endif
248
249 #define LZ4_STATIC_ASSERT(c)   { enum { LZ4_static_assert = 1/(int)(!!(c)) }; }   /* use after variable declarations */
250
251 #if defined(LZ4_DEBUG) && (LZ4_DEBUG>=2)
252 #  include <stdio.h>
253    static int g_debuglog_enable = 1;
254 #  define DEBUGLOG(l, ...) {                          \
255         if ((g_debuglog_enable) && (l<=LZ4_DEBUG)) {  \
256             fprintf(stderr, __FILE__ ": ");           \
257             fprintf(stderr, __VA_ARGS__);             \
258             fprintf(stderr, " \n");                   \
259     }   }
260 #else
261 #  define DEBUGLOG(l, ...) {}    /* disabled */
262 #endif
263
264 static int LZ4_isAligned(const void* ptr, size_t alignment)
265 {
266     return ((size_t)ptr & (alignment -1)) == 0;
267 }
268
269
270 /*-************************************
271 *  Types
272 **************************************/
273 #include <limits.h>
274 #if defined(__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
275 # include <stdint.h>
276   typedef  uint8_t BYTE;
277   typedef uint16_t U16;
278   typedef uint32_t U32;
279   typedef  int32_t S32;
280   typedef uint64_t U64;
281   typedef uintptr_t uptrval;
282 #else
283 # if UINT_MAX != 4294967295UL
284 #   error "LZ4 code (when not C++ or C99) assumes that sizeof(int) == 4"
285 # endif
286   typedef unsigned char       BYTE;
287   typedef unsigned short      U16;
288   typedef unsigned int        U32;
289   typedef   signed int        S32;
290   typedef unsigned long long  U64;
291   typedef size_t              uptrval;   /* generally true, except OpenVMS-64 */
292 #endif
293
294 #if defined(__x86_64__)
295   typedef U64    reg_t;   /* 64-bits in x32 mode */
296 #else
297   typedef size_t reg_t;   /* 32-bits in x32 mode */
298 #endif
299
300 typedef enum {
301     notLimited = 0,
302     limitedOutput = 1,
303     fillOutput = 2
304 } limitedOutput_directive;
305
306
307 /*-************************************
308 *  Reading and writing into memory
309 **************************************/
310
311 /**
312  * LZ4 relies on memcpy with a constant size being inlined. In freestanding
313  * environments, the compiler can't assume the implementation of memcpy() is
314  * standard compliant, so it can't apply its specialized memcpy() inlining
315  * logic. When possible, use __builtin_memcpy() to tell the compiler to analyze
316  * memcpy() as if it were standard compliant, so it can inline it in freestanding
317  * environments. This is needed when decompressing the Linux Kernel, for example.
318  */
319 #if defined(__GNUC__) && (__GNUC__ >= 4)
320 #define LZ4_memcpy(dst, src, size) __builtin_memcpy(dst, src, size)
321 #else
322 #define LZ4_memcpy(dst, src, size) memcpy(dst, src, size)
323 #endif
324
325 static unsigned LZ4_isLittleEndian(void)
326 {
327     const union { U32 u; BYTE c[4]; } one = { 1 };   /* don't use static : performance detrimental */
328     return one.c[0];
329 }
330
331
332 #if defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==2)
333 /* lie to the compiler about data alignment; use with caution */
334
335 static U16 LZ4_read16(const void* memPtr) { return *(const U16*) memPtr; }
336 static U32 LZ4_read32(const void* memPtr) { return *(const U32*) memPtr; }
337 static reg_t LZ4_read_ARCH(const void* memPtr) { return *(const reg_t*) memPtr; }
338
339 static void LZ4_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
340 static void LZ4_write32(void* memPtr, U32 value) { *(U32*)memPtr = value; }
341
342 #elif defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==1)
343
344 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
345 /* currently only defined for gcc and icc */
346 typedef union { U16 u16; U32 u32; reg_t uArch; } __attribute__((packed)) unalign;
347
348 static U16 LZ4_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
349 static U32 LZ4_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
350 static reg_t LZ4_read_ARCH(const void* ptr) { return ((const unalign*)ptr)->uArch; }
351
352 static void LZ4_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }
353 static void LZ4_write32(void* memPtr, U32 value) { ((unalign*)memPtr)->u32 = value; }
354
355 #else  /* safe and portable access using memcpy() */
356
357 static U16 LZ4_read16(const void* memPtr)
358 {
359     U16 val; LZ4_memcpy(&val, memPtr, sizeof(val)); return val;
360 }
361
362 static U32 LZ4_read32(const void* memPtr)
363 {
364     U32 val; LZ4_memcpy(&val, memPtr, sizeof(val)); return val;
365 }
366
367 static reg_t LZ4_read_ARCH(const void* memPtr)
368 {
369     reg_t val; LZ4_memcpy(&val, memPtr, sizeof(val)); return val;
370 }
371
372 static void LZ4_write16(void* memPtr, U16 value)
373 {
374     LZ4_memcpy(memPtr, &value, sizeof(value));
375 }
376
377 static void LZ4_write32(void* memPtr, U32 value)
378 {
379     LZ4_memcpy(memPtr, &value, sizeof(value));
380 }
381
382 #endif /* LZ4_FORCE_MEMORY_ACCESS */
383
384
385 static U16 LZ4_readLE16(const void* memPtr)
386 {
387     if (LZ4_isLittleEndian()) {
388         return LZ4_read16(memPtr);
389     } else {
390         const BYTE* p = (const BYTE*)memPtr;
391         return (U16)((U16)p[0] + (p[1]<<8));
392     }
393 }
394
395 static void LZ4_writeLE16(void* memPtr, U16 value)
396 {
397     if (LZ4_isLittleEndian()) {
398         LZ4_write16(memPtr, value);
399     } else {
400         BYTE* p = (BYTE*)memPtr;
401         p[0] = (BYTE) value;
402         p[1] = (BYTE)(value>>8);
403     }
404 }
405
406 /* customized variant of memcpy, which can overwrite up to 8 bytes beyond dstEnd */
407 LZ4_FORCE_INLINE
408 void LZ4_wildCopy8(void* dstPtr, const void* srcPtr, void* dstEnd)
409 {
410     BYTE* d = (BYTE*)dstPtr;
411     const BYTE* s = (const BYTE*)srcPtr;
412     BYTE* const e = (BYTE*)dstEnd;
413
414     do { LZ4_memcpy(d,s,8); d+=8; s+=8; } while (d<e);
415 }
416
417 static const unsigned inc32table[8] = {0, 1, 2,  1,  0,  4, 4, 4};
418 static const int      dec64table[8] = {0, 0, 0, -1, -4,  1, 2, 3};
419
420
421 #ifndef LZ4_FAST_DEC_LOOP
422 #  if defined __i386__ || defined _M_IX86 || defined __x86_64__ || defined _M_X64
423 #    define LZ4_FAST_DEC_LOOP 1
424 #  elif defined(__aarch64__) && !defined(__clang__)
425      /* On aarch64, we disable this optimization for clang because on certain
426       * mobile chipsets, performance is reduced with clang. For information
427       * refer to https://github.com/lz4/lz4/pull/707 */
428 #    define LZ4_FAST_DEC_LOOP 1
429 #  else
430 #    define LZ4_FAST_DEC_LOOP 0
431 #  endif
432 #endif
433
434 #if LZ4_FAST_DEC_LOOP
435
436 LZ4_FORCE_INLINE void
437 LZ4_memcpy_using_offset_base(BYTE* dstPtr, const BYTE* srcPtr, BYTE* dstEnd, const size_t offset)
438 {
439     assert(srcPtr + offset == dstPtr);
440     if (offset < 8) {
441         LZ4_write32(dstPtr, 0);   /* silence an msan warning when offset==0 */
442         dstPtr[0] = srcPtr[0];
443         dstPtr[1] = srcPtr[1];
444         dstPtr[2] = srcPtr[2];
445         dstPtr[3] = srcPtr[3];
446         srcPtr += inc32table[offset];
447         LZ4_memcpy(dstPtr+4, srcPtr, 4);
448         srcPtr -= dec64table[offset];
449         dstPtr += 8;
450     } else {
451         LZ4_memcpy(dstPtr, srcPtr, 8);
452         dstPtr += 8;
453         srcPtr += 8;
454     }
455
456     LZ4_wildCopy8(dstPtr, srcPtr, dstEnd);
457 }
458
459 /* customized variant of memcpy, which can overwrite up to 32 bytes beyond dstEnd
460  * this version copies two times 16 bytes (instead of one time 32 bytes)
461  * because it must be compatible with offsets >= 16. */
462 LZ4_FORCE_INLINE void
463 LZ4_wildCopy32(void* dstPtr, const void* srcPtr, void* dstEnd)
464 {
465     BYTE* d = (BYTE*)dstPtr;
466     const BYTE* s = (const BYTE*)srcPtr;
467     BYTE* const e = (BYTE*)dstEnd;
468
469     do { LZ4_memcpy(d,s,16); LZ4_memcpy(d+16,s+16,16); d+=32; s+=32; } while (d<e);
470 }
471
472 /* LZ4_memcpy_using_offset()  presumes :
473  * - dstEnd >= dstPtr + MINMATCH
474  * - there is at least 8 bytes available to write after dstEnd */
475 LZ4_FORCE_INLINE void
476 LZ4_memcpy_using_offset(BYTE* dstPtr, const BYTE* srcPtr, BYTE* dstEnd, const size_t offset)
477 {
478     BYTE v[8];
479
480     assert(dstEnd >= dstPtr + MINMATCH);
481
482     switch(offset) {
483     case 1:
484         MEM_INIT(v, *srcPtr, 8);
485         break;
486     case 2:
487         LZ4_memcpy(v, srcPtr, 2);
488         LZ4_memcpy(&v[2], srcPtr, 2);
489         LZ4_memcpy(&v[4], v, 4);
490         break;
491     case 4:
492         LZ4_memcpy(v, srcPtr, 4);
493         LZ4_memcpy(&v[4], srcPtr, 4);
494         break;
495     default:
496         LZ4_memcpy_using_offset_base(dstPtr, srcPtr, dstEnd, offset);
497         return;
498     }
499
500     LZ4_memcpy(dstPtr, v, 8);
501     dstPtr += 8;
502     while (dstPtr < dstEnd) {
503         LZ4_memcpy(dstPtr, v, 8);
504         dstPtr += 8;
505     }
506 }
507 #endif
508
509
510 /*-************************************
511 *  Common functions
512 **************************************/
513 static unsigned LZ4_NbCommonBytes (reg_t val)
514 {
515     assert(val != 0);
516     if (LZ4_isLittleEndian()) {
517         if (sizeof(val) == 8) {
518 #       if defined(_MSC_VER) && (_MSC_VER >= 1800) && defined(_M_AMD64) && !defined(LZ4_FORCE_SW_BITCOUNT)
519             /* x64 CPUS without BMI support interpret `TZCNT` as `REP BSF` */
520             return (unsigned)_tzcnt_u64(val) >> 3;
521 #       elif defined(_MSC_VER) && defined(_WIN64) && !defined(LZ4_FORCE_SW_BITCOUNT)
522             unsigned long r = 0;
523             _BitScanForward64(&r, (U64)val);
524             return (unsigned)r >> 3;
525 #       elif (defined(__clang__) || (defined(__GNUC__) && ((__GNUC__ > 3) || \
526                             ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))))) && \
527                                         !defined(LZ4_FORCE_SW_BITCOUNT)
528             return (unsigned)__builtin_ctzll((U64)val) >> 3;
529 #       else
530             const U64 m = 0x0101010101010101ULL;
531             val ^= val - 1;
532             return (unsigned)(((U64)((val & (m - 1)) * m)) >> 56);
533 #       endif
534         } else /* 32 bits */ {
535 #       if defined(_MSC_VER) && (_MSC_VER >= 1400) && !defined(LZ4_FORCE_SW_BITCOUNT)
536             unsigned long r;
537             _BitScanForward(&r, (U32)val);
538             return (unsigned)r >> 3;
539 #       elif (defined(__clang__) || (defined(__GNUC__) && ((__GNUC__ > 3) || \
540                             ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))))) && \
541                         !defined(__TINYC__) && !defined(LZ4_FORCE_SW_BITCOUNT)
542             return (unsigned)__builtin_ctz((U32)val) >> 3;
543 #       else
544             const U32 m = 0x01010101;
545             return (unsigned)((((val - 1) ^ val) & (m - 1)) * m) >> 24;
546 #       endif
547         }
548     } else   /* Big Endian CPU */ {
549         if (sizeof(val)==8) {
550 #       if (defined(__clang__) || (defined(__GNUC__) && ((__GNUC__ > 3) || \
551                             ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))))) && \
552                         !defined(__TINYC__) && !defined(LZ4_FORCE_SW_BITCOUNT)
553             return (unsigned)__builtin_clzll((U64)val) >> 3;
554 #       else
555 #if 1
556             /* this method is probably faster,
557              * but adds a 128 bytes lookup table */
558             static const unsigned char ctz7_tab[128] = {
559                 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
560                 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
561                 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
562                 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
563                 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
564                 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
565                 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
566                 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
567             };
568             U64 const mask = 0x0101010101010101ULL;
569             U64 const t = (((val >> 8) - mask) | val) & mask;
570             return ctz7_tab[(t * 0x0080402010080402ULL) >> 57];
571 #else
572             /* this method doesn't consume memory space like the previous one,
573              * but it contains several branches,
574              * that may end up slowing execution */
575             static const U32 by32 = sizeof(val)*4;  /* 32 on 64 bits (goal), 16 on 32 bits.
576             Just to avoid some static analyzer complaining about shift by 32 on 32-bits target.
577             Note that this code path is never triggered in 32-bits mode. */
578             unsigned r;
579             if (!(val>>by32)) { r=4; } else { r=0; val>>=by32; }
580             if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
581             r += (!val);
582             return r;
583 #endif
584 #       endif
585         } else /* 32 bits */ {
586 #       if (defined(__clang__) || (defined(__GNUC__) && ((__GNUC__ > 3) || \
587                             ((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))))) && \
588                                         !defined(LZ4_FORCE_SW_BITCOUNT)
589             return (unsigned)__builtin_clz((U32)val) >> 3;
590 #       else
591             val >>= 8;
592             val = ((((val + 0x00FFFF00) | 0x00FFFFFF) + val) |
593               (val + 0x00FF0000)) >> 24;
594             return (unsigned)val ^ 3;
595 #       endif
596         }
597     }
598 }
599
600
601 #define STEPSIZE sizeof(reg_t)
602 LZ4_FORCE_INLINE
603 unsigned LZ4_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* pInLimit)
604 {
605     const BYTE* const pStart = pIn;
606
607     if (likely(pIn < pInLimit-(STEPSIZE-1))) {
608         reg_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn);
609         if (!diff) {
610             pIn+=STEPSIZE; pMatch+=STEPSIZE;
611         } else {
612             return LZ4_NbCommonBytes(diff);
613     }   }
614
615     while (likely(pIn < pInLimit-(STEPSIZE-1))) {
616         reg_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn);
617         if (!diff) { pIn+=STEPSIZE; pMatch+=STEPSIZE; continue; }
618         pIn += LZ4_NbCommonBytes(diff);
619         return (unsigned)(pIn - pStart);
620     }
621
622     if ((STEPSIZE==8) && (pIn<(pInLimit-3)) && (LZ4_read32(pMatch) == LZ4_read32(pIn))) { pIn+=4; pMatch+=4; }
623     if ((pIn<(pInLimit-1)) && (LZ4_read16(pMatch) == LZ4_read16(pIn))) { pIn+=2; pMatch+=2; }
624     if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
625     return (unsigned)(pIn - pStart);
626 }
627
628
629 #ifndef LZ4_COMMONDEFS_ONLY
630 /*-************************************
631 *  Local Constants
632 **************************************/
633 static const int LZ4_64Klimit = ((64 KB) + (MFLIMIT-1));
634 static const U32 LZ4_skipTrigger = 6;  /* Increase this value ==> compression run slower on incompressible data */
635
636
637 /*-************************************
638 *  Local Structures and types
639 **************************************/
640 typedef enum { clearedTable = 0, byPtr, byU32, byU16 } tableType_t;
641
642 /**
643  * This enum distinguishes several different modes of accessing previous
644  * content in the stream.
645  *
646  * - noDict        : There is no preceding content.
647  * - withPrefix64k : Table entries up to ctx->dictSize before the current blob
648  *                   blob being compressed are valid and refer to the preceding
649  *                   content (of length ctx->dictSize), which is available
650  *                   contiguously preceding in memory the content currently
651  *                   being compressed.
652  * - usingExtDict  : Like withPrefix64k, but the preceding content is somewhere
653  *                   else in memory, starting at ctx->dictionary with length
654  *                   ctx->dictSize.
655  * - usingDictCtx  : Everything concerning the preceding content is
656  *                   in a separate context, pointed to by ctx->dictCtx.
657  *                   ctx->dictionary, ctx->dictSize, and table entries
658  *                   in the current context that refer to positions
659  *                   preceding the beginning of the current compression are
660  *                   ignored. Instead, ctx->dictCtx->dictionary and ctx->dictCtx
661  *                   ->dictSize describe the location and size of the preceding
662  *                   content, and matches are found by looking in the ctx
663  *                   ->dictCtx->hashTable.
664  */
665 typedef enum { noDict = 0, withPrefix64k, usingExtDict, usingDictCtx } dict_directive;
666 typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive;
667
668
669 /*-************************************
670 *  Local Utils
671 **************************************/
672 int LZ4_versionNumber (void) { return LZ4_VERSION_NUMBER; }
673 const char* LZ4_versionString(void) { return LZ4_VERSION_STRING; }
674 int LZ4_compressBound(int isize)  { return LZ4_COMPRESSBOUND(isize); }
675 int LZ4_sizeofState(void) { return LZ4_STREAMSIZE; }
676
677
678 /*-****************************************
679 *  Internal Definitions, used only in Tests
680 *******************************************/
681 #if defined (__cplusplus)
682 extern "C" {
683 #endif
684
685 int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int srcSize);
686
687 int LZ4_decompress_safe_forceExtDict(const char* source, char* dest,
688                                      int compressedSize, int maxOutputSize,
689                                      const void* dictStart, size_t dictSize);
690
691 #if defined (__cplusplus)
692 }
693 #endif
694
695 /*-******************************
696 *  Compression functions
697 ********************************/
698 LZ4_FORCE_INLINE U32 LZ4_hash4(U32 sequence, tableType_t const tableType)
699 {
700     if (tableType == byU16)
701         return ((sequence * 2654435761U) >> ((MINMATCH*8)-(LZ4_HASHLOG+1)));
702     else
703         return ((sequence * 2654435761U) >> ((MINMATCH*8)-LZ4_HASHLOG));
704 }
705
706 LZ4_FORCE_INLINE U32 LZ4_hash5(U64 sequence, tableType_t const tableType)
707 {
708     const U32 hashLog = (tableType == byU16) ? LZ4_HASHLOG+1 : LZ4_HASHLOG;
709     if (LZ4_isLittleEndian()) {
710         const U64 prime5bytes = 889523592379ULL;
711         return (U32)(((sequence << 24) * prime5bytes) >> (64 - hashLog));
712     } else {
713         const U64 prime8bytes = 11400714785074694791ULL;
714         return (U32)(((sequence >> 24) * prime8bytes) >> (64 - hashLog));
715     }
716 }
717
718 LZ4_FORCE_INLINE U32 LZ4_hashPosition(const void* const p, tableType_t const tableType)
719 {
720     if ((sizeof(reg_t)==8) && (tableType != byU16)) return LZ4_hash5(LZ4_read_ARCH(p), tableType);
721     return LZ4_hash4(LZ4_read32(p), tableType);
722 }
723
724 LZ4_FORCE_INLINE void LZ4_clearHash(U32 h, void* tableBase, tableType_t const tableType)
725 {
726     switch (tableType)
727     {
728     default: /* fallthrough */
729     case clearedTable: { /* illegal! */ assert(0); return; }
730     case byPtr: { const BYTE** hashTable = (const BYTE**)tableBase; hashTable[h] = NULL; return; }
731     case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = 0; return; }
732     case byU16: { U16* hashTable = (U16*) tableBase; hashTable[h] = 0; return; }
733     }
734 }
735
736 LZ4_FORCE_INLINE void LZ4_putIndexOnHash(U32 idx, U32 h, void* tableBase, tableType_t const tableType)
737 {
738     switch (tableType)
739     {
740     default: /* fallthrough */
741     case clearedTable: /* fallthrough */
742     case byPtr: { /* illegal! */ assert(0); return; }
743     case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = idx; return; }
744     case byU16: { U16* hashTable = (U16*) tableBase; assert(idx < 65536); hashTable[h] = (U16)idx; return; }
745     }
746 }
747
748 LZ4_FORCE_INLINE void LZ4_putPositionOnHash(const BYTE* p, U32 h,
749                                   void* tableBase, tableType_t const tableType,
750                             const BYTE* srcBase)
751 {
752     switch (tableType)
753     {
754     case clearedTable: { /* illegal! */ assert(0); return; }
755     case byPtr: { const BYTE** hashTable = (const BYTE**)tableBase; hashTable[h] = p; return; }
756     case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = (U32)(p-srcBase); return; }
757     case byU16: { U16* hashTable = (U16*) tableBase; hashTable[h] = (U16)(p-srcBase); return; }
758     }
759 }
760
761 LZ4_FORCE_INLINE void LZ4_putPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase)
762 {
763     U32 const h = LZ4_hashPosition(p, tableType);
764     LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase);
765 }
766
767 /* LZ4_getIndexOnHash() :
768  * Index of match position registered in hash table.
769  * hash position must be calculated by using base+index, or dictBase+index.
770  * Assumption 1 : only valid if tableType == byU32 or byU16.
771  * Assumption 2 : h is presumed valid (within limits of hash table)
772  */
773 LZ4_FORCE_INLINE U32 LZ4_getIndexOnHash(U32 h, const void* tableBase, tableType_t tableType)
774 {
775     LZ4_STATIC_ASSERT(LZ4_MEMORY_USAGE > 2);
776     if (tableType == byU32) {
777         const U32* const hashTable = (const U32*) tableBase;
778         assert(h < (1U << (LZ4_MEMORY_USAGE-2)));
779         return hashTable[h];
780     }
781     if (tableType == byU16) {
782         const U16* const hashTable = (const U16*) tableBase;
783         assert(h < (1U << (LZ4_MEMORY_USAGE-1)));
784         return hashTable[h];
785     }
786     assert(0); return 0;  /* forbidden case */
787 }
788
789 static const BYTE* LZ4_getPositionOnHash(U32 h, const void* tableBase, tableType_t tableType, const BYTE* srcBase)
790 {
791     if (tableType == byPtr) { const BYTE* const* hashTable = (const BYTE* const*) tableBase; return hashTable[h]; }
792     if (tableType == byU32) { const U32* const hashTable = (const U32*) tableBase; return hashTable[h] + srcBase; }
793     { const U16* const hashTable = (const U16*) tableBase; return hashTable[h] + srcBase; }   /* default, to ensure a return */
794 }
795
796 LZ4_FORCE_INLINE const BYTE*
797 LZ4_getPosition(const BYTE* p,
798                 const void* tableBase, tableType_t tableType,
799                 const BYTE* srcBase)
800 {
801     U32 const h = LZ4_hashPosition(p, tableType);
802     return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase);
803 }
804
805 LZ4_FORCE_INLINE void
806 LZ4_prepareTable(LZ4_stream_t_internal* const cctx,
807            const int inputSize,
808            const tableType_t tableType) {
809     /* If the table hasn't been used, it's guaranteed to be zeroed out, and is
810      * therefore safe to use no matter what mode we're in. Otherwise, we figure
811      * out if it's safe to leave as is or whether it needs to be reset.
812      */
813     if ((tableType_t)cctx->tableType != clearedTable) {
814         assert(inputSize >= 0);
815         if ((tableType_t)cctx->tableType != tableType
816           || ((tableType == byU16) && cctx->currentOffset + (unsigned)inputSize >= 0xFFFFU)
817           || ((tableType == byU32) && cctx->currentOffset > 1 GB)
818           || tableType == byPtr
819           || inputSize >= 4 KB)
820         {
821             DEBUGLOG(4, "LZ4_prepareTable: Resetting table in %p", cctx);
822             MEM_INIT(cctx->hashTable, 0, LZ4_HASHTABLESIZE);
823             cctx->currentOffset = 0;
824             cctx->tableType = (U32)clearedTable;
825         } else {
826             DEBUGLOG(4, "LZ4_prepareTable: Re-use hash table (no reset)");
827         }
828     }
829
830     /* Adding a gap, so all previous entries are > LZ4_DISTANCE_MAX back,
831      * is faster than compressing without a gap.
832      * However, compressing with currentOffset == 0 is faster still,
833      * so we preserve that case.
834      */
835     if (cctx->currentOffset != 0 && tableType == byU32) {
836         DEBUGLOG(5, "LZ4_prepareTable: adding 64KB to currentOffset");
837         cctx->currentOffset += 64 KB;
838     }
839
840     /* Finally, clear history */
841     cctx->dictCtx = NULL;
842     cctx->dictionary = NULL;
843     cctx->dictSize = 0;
844 }
845
846 /** LZ4_compress_generic() :
847  *  inlined, to ensure branches are decided at compilation time.
848  *  Presumed already validated at this stage:
849  *  - source != NULL
850  *  - inputSize > 0
851  */
852 LZ4_FORCE_INLINE int LZ4_compress_generic_validated(
853                  LZ4_stream_t_internal* const cctx,
854                  const char* const source,
855                  char* const dest,
856                  const int inputSize,
857                  int *inputConsumed, /* only written when outputDirective == fillOutput */
858                  const int maxOutputSize,
859                  const limitedOutput_directive outputDirective,
860                  const tableType_t tableType,
861                  const dict_directive dictDirective,
862                  const dictIssue_directive dictIssue,
863                  const int acceleration)
864 {
865     int result;
866     const BYTE* ip = (const BYTE*) source;
867
868     U32 const startIndex = cctx->currentOffset;
869     const BYTE* base = (const BYTE*) source - startIndex;
870     const BYTE* lowLimit;
871
872     const LZ4_stream_t_internal* dictCtx = (const LZ4_stream_t_internal*) cctx->dictCtx;
873     const BYTE* const dictionary =
874         dictDirective == usingDictCtx ? dictCtx->dictionary : cctx->dictionary;
875     const U32 dictSize =
876         dictDirective == usingDictCtx ? dictCtx->dictSize : cctx->dictSize;
877     const U32 dictDelta = (dictDirective == usingDictCtx) ? startIndex - dictCtx->currentOffset : 0;   /* make indexes in dictCtx comparable with index in current context */
878
879     int const maybe_extMem = (dictDirective == usingExtDict) || (dictDirective == usingDictCtx);
880     U32 const prefixIdxLimit = startIndex - dictSize;   /* used when dictDirective == dictSmall */
881     const BYTE* const dictEnd = dictionary ? dictionary + dictSize : dictionary;
882     const BYTE* anchor = (const BYTE*) source;
883     const BYTE* const iend = ip + inputSize;
884     const BYTE* const mflimitPlusOne = iend - MFLIMIT + 1;
885     const BYTE* const matchlimit = iend - LASTLITERALS;
886
887     /* the dictCtx currentOffset is indexed on the start of the dictionary,
888      * while a dictionary in the current context precedes the currentOffset */
889     const BYTE* dictBase = (dictionary == NULL) ? NULL :
890                            (dictDirective == usingDictCtx) ?
891                             dictionary + dictSize - dictCtx->currentOffset :
892                             dictionary + dictSize - startIndex;
893
894     BYTE* op = (BYTE*) dest;
895     BYTE* const olimit = op + maxOutputSize;
896
897     U32 offset = 0;
898     U32 forwardH;
899
900     DEBUGLOG(5, "LZ4_compress_generic_validated: srcSize=%i, tableType=%u", inputSize, tableType);
901     assert(ip != NULL);
902     /* If init conditions are not met, we don't have to mark stream
903      * as having dirty context, since no action was taken yet */
904     if (outputDirective == fillOutput && maxOutputSize < 1) { return 0; } /* Impossible to store anything */
905     if ((tableType == byU16) && (inputSize>=LZ4_64Klimit)) { return 0; }  /* Size too large (not within 64K limit) */
906     if (tableType==byPtr) assert(dictDirective==noDict);      /* only supported use case with byPtr */
907     assert(acceleration >= 1);
908
909     lowLimit = (const BYTE*)source - (dictDirective == withPrefix64k ? dictSize : 0);
910
911     /* Update context state */
912     if (dictDirective == usingDictCtx) {
913         /* Subsequent linked blocks can't use the dictionary. */
914         /* Instead, they use the block we just compressed. */
915         cctx->dictCtx = NULL;
916         cctx->dictSize = (U32)inputSize;
917     } else {
918         cctx->dictSize += (U32)inputSize;
919     }
920     cctx->currentOffset += (U32)inputSize;
921     cctx->tableType = (U32)tableType;
922
923     if (inputSize<LZ4_minLength) goto _last_literals;        /* Input too small, no compression (all literals) */
924
925     /* First Byte */
926     LZ4_putPosition(ip, cctx->hashTable, tableType, base);
927     ip++; forwardH = LZ4_hashPosition(ip, tableType);
928
929     /* Main Loop */
930     for ( ; ; ) {
931         const BYTE* match;
932         BYTE* token;
933         const BYTE* filledIp;
934
935         /* Find a match */
936         if (tableType == byPtr) {
937             const BYTE* forwardIp = ip;
938             int step = 1;
939             int searchMatchNb = acceleration << LZ4_skipTrigger;
940             do {
941                 U32 const h = forwardH;
942                 ip = forwardIp;
943                 forwardIp += step;
944                 step = (searchMatchNb++ >> LZ4_skipTrigger);
945
946                 if (unlikely(forwardIp > mflimitPlusOne)) goto _last_literals;
947                 assert(ip < mflimitPlusOne);
948
949                 match = LZ4_getPositionOnHash(h, cctx->hashTable, tableType, base);
950                 forwardH = LZ4_hashPosition(forwardIp, tableType);
951                 LZ4_putPositionOnHash(ip, h, cctx->hashTable, tableType, base);
952
953             } while ( (match+LZ4_DISTANCE_MAX < ip)
954                    || (LZ4_read32(match) != LZ4_read32(ip)) );
955
956         } else {   /* byU32, byU16 */
957
958             const BYTE* forwardIp = ip;
959             int step = 1;
960             int searchMatchNb = acceleration << LZ4_skipTrigger;
961             do {
962                 U32 const h = forwardH;
963                 U32 const current = (U32)(forwardIp - base);
964                 U32 matchIndex = LZ4_getIndexOnHash(h, cctx->hashTable, tableType);
965                 assert(matchIndex <= current);
966                 assert(forwardIp - base < (ptrdiff_t)(2 GB - 1));
967                 ip = forwardIp;
968                 forwardIp += step;
969                 step = (searchMatchNb++ >> LZ4_skipTrigger);
970
971                 if (unlikely(forwardIp > mflimitPlusOne)) goto _last_literals;
972                 assert(ip < mflimitPlusOne);
973
974                 if (dictDirective == usingDictCtx) {
975                     if (matchIndex < startIndex) {
976                         /* there was no match, try the dictionary */
977                         assert(tableType == byU32);
978                         matchIndex = LZ4_getIndexOnHash(h, dictCtx->hashTable, byU32);
979                         match = dictBase + matchIndex;
980                         matchIndex += dictDelta;   /* make dictCtx index comparable with current context */
981                         lowLimit = dictionary;
982                     } else {
983                         match = base + matchIndex;
984                         lowLimit = (const BYTE*)source;
985                     }
986                 } else if (dictDirective == usingExtDict) {
987                     if (matchIndex < startIndex) {
988                         DEBUGLOG(7, "extDict candidate: matchIndex=%5u  <  startIndex=%5u", matchIndex, startIndex);
989                         assert(startIndex - matchIndex >= MINMATCH);
990                         assert(dictBase);
991                         match = dictBase + matchIndex;
992                         lowLimit = dictionary;
993                     } else {
994                         match = base + matchIndex;
995                         lowLimit = (const BYTE*)source;
996                     }
997                 } else {   /* single continuous memory segment */
998                     match = base + matchIndex;
999                 }
1000                 forwardH = LZ4_hashPosition(forwardIp, tableType);
1001                 LZ4_putIndexOnHash(current, h, cctx->hashTable, tableType);
1002
1003                 DEBUGLOG(7, "candidate at pos=%u  (offset=%u \n", matchIndex, current - matchIndex);
1004                 if ((dictIssue == dictSmall) && (matchIndex < prefixIdxLimit)) { continue; }    /* match outside of valid area */
1005                 assert(matchIndex < current);
1006                 if ( ((tableType != byU16) || (LZ4_DISTANCE_MAX < LZ4_DISTANCE_ABSOLUTE_MAX))
1007                   && (matchIndex+LZ4_DISTANCE_MAX < current)) {
1008                     continue;
1009                 } /* too far */
1010                 assert((current - matchIndex) <= LZ4_DISTANCE_MAX);  /* match now expected within distance */
1011
1012                 if (LZ4_read32(match) == LZ4_read32(ip)) {
1013                     if (maybe_extMem) offset = current - matchIndex;
1014                     break;   /* match found */
1015                 }
1016
1017             } while(1);
1018         }
1019
1020         /* Catch up */
1021         filledIp = ip;
1022         while (((ip>anchor) & (match > lowLimit)) && (unlikely(ip[-1]==match[-1]))) { ip--; match--; }
1023
1024         /* Encode Literals */
1025         {   unsigned const litLength = (unsigned)(ip - anchor);
1026             token = op++;
1027             if ((outputDirective == limitedOutput) &&  /* Check output buffer overflow */
1028                 (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > olimit)) ) {
1029                 return 0;   /* cannot compress within `dst` budget. Stored indexes in hash table are nonetheless fine */
1030             }
1031             if ((outputDirective == fillOutput) &&
1032                 (unlikely(op + (litLength+240)/255 /* litlen */ + litLength /* literals */ + 2 /* offset */ + 1 /* token */ + MFLIMIT - MINMATCH /* min last literals so last match is <= end - MFLIMIT */ > olimit))) {
1033                 op--;
1034                 goto _last_literals;
1035             }
1036             if (litLength >= RUN_MASK) {
1037                 int len = (int)(litLength - RUN_MASK);
1038                 *token = (RUN_MASK<<ML_BITS);
1039                 for(; len >= 255 ; len-=255) *op++ = 255;
1040                 *op++ = (BYTE)len;
1041             }
1042             else *token = (BYTE)(litLength<<ML_BITS);
1043
1044             /* Copy Literals */
1045             LZ4_wildCopy8(op, anchor, op+litLength);
1046             op+=litLength;
1047             DEBUGLOG(6, "seq.start:%i, literals=%u, match.start:%i",
1048                         (int)(anchor-(const BYTE*)source), litLength, (int)(ip-(const BYTE*)source));
1049         }
1050
1051 _next_match:
1052         /* at this stage, the following variables must be correctly set :
1053          * - ip : at start of LZ operation
1054          * - match : at start of previous pattern occurrence; can be within current prefix, or within extDict
1055          * - offset : if maybe_ext_memSegment==1 (constant)
1056          * - lowLimit : must be == dictionary to mean "match is within extDict"; must be == source otherwise
1057          * - token and *token : position to write 4-bits for match length; higher 4-bits for literal length supposed already written
1058          */
1059
1060         if ((outputDirective == fillOutput) &&
1061             (op + 2 /* offset */ + 1 /* token */ + MFLIMIT - MINMATCH /* min last literals so last match is <= end - MFLIMIT */ > olimit)) {
1062             /* the match was too close to the end, rewind and go to last literals */
1063             op = token;
1064             goto _last_literals;
1065         }
1066
1067         /* Encode Offset */
1068         if (maybe_extMem) {   /* static test */
1069             DEBUGLOG(6, "             with offset=%u  (ext if > %i)", offset, (int)(ip - (const BYTE*)source));
1070             assert(offset <= LZ4_DISTANCE_MAX && offset > 0);
1071             LZ4_writeLE16(op, (U16)offset); op+=2;
1072         } else  {
1073             DEBUGLOG(6, "             with offset=%u  (same segment)", (U32)(ip - match));
1074             assert(ip-match <= LZ4_DISTANCE_MAX);
1075             LZ4_writeLE16(op, (U16)(ip - match)); op+=2;
1076         }
1077
1078         /* Encode MatchLength */
1079         {   unsigned matchCode;
1080
1081             if ( (dictDirective==usingExtDict || dictDirective==usingDictCtx)
1082               && (lowLimit==dictionary) /* match within extDict */ ) {
1083                 const BYTE* limit = ip + (dictEnd-match);
1084                 assert(dictEnd > match);
1085                 if (limit > matchlimit) limit = matchlimit;
1086                 matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, limit);
1087                 ip += (size_t)matchCode + MINMATCH;
1088                 if (ip==limit) {
1089                     unsigned const more = LZ4_count(limit, (const BYTE*)source, matchlimit);
1090                     matchCode += more;
1091                     ip += more;
1092                 }
1093                 DEBUGLOG(6, "             with matchLength=%u starting in extDict", matchCode+MINMATCH);
1094             } else {
1095                 matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, matchlimit);
1096                 ip += (size_t)matchCode + MINMATCH;
1097                 DEBUGLOG(6, "             with matchLength=%u", matchCode+MINMATCH);
1098             }
1099
1100             if ((outputDirective) &&    /* Check output buffer overflow */
1101                 (unlikely(op + (1 + LASTLITERALS) + (matchCode+240)/255 > olimit)) ) {
1102                 if (outputDirective == fillOutput) {
1103                     /* Match description too long : reduce it */
1104                     U32 newMatchCode = 15 /* in token */ - 1 /* to avoid needing a zero byte */ + ((U32)(olimit - op) - 1 - LASTLITERALS) * 255;
1105                     ip -= matchCode - newMatchCode;
1106                     assert(newMatchCode < matchCode);
1107                     matchCode = newMatchCode;
1108                     if (unlikely(ip <= filledIp)) {
1109                         /* We have already filled up to filledIp so if ip ends up less than filledIp
1110                          * we have positions in the hash table beyond the current position. This is
1111                          * a problem if we reuse the hash table. So we have to remove these positions
1112                          * from the hash table.
1113                          */
1114                         const BYTE* ptr;
1115                         DEBUGLOG(5, "Clearing %u positions", (U32)(filledIp - ip));
1116                         for (ptr = ip; ptr <= filledIp; ++ptr) {
1117                             U32 const h = LZ4_hashPosition(ptr, tableType);
1118                             LZ4_clearHash(h, cctx->hashTable, tableType);
1119                         }
1120                     }
1121                 } else {
1122                     assert(outputDirective == limitedOutput);
1123                     return 0;   /* cannot compress within `dst` budget. Stored indexes in hash table are nonetheless fine */
1124                 }
1125             }
1126             if (matchCode >= ML_MASK) {
1127                 *token += ML_MASK;
1128                 matchCode -= ML_MASK;
1129                 LZ4_write32(op, 0xFFFFFFFF);
1130                 while (matchCode >= 4*255) {
1131                     op+=4;
1132                     LZ4_write32(op, 0xFFFFFFFF);
1133                     matchCode -= 4*255;
1134                 }
1135                 op += matchCode / 255;
1136                 *op++ = (BYTE)(matchCode % 255);
1137             } else
1138                 *token += (BYTE)(matchCode);
1139         }
1140         /* Ensure we have enough space for the last literals. */
1141         assert(!(outputDirective == fillOutput && op + 1 + LASTLITERALS > olimit));
1142
1143         anchor = ip;
1144
1145         /* Test end of chunk */
1146         if (ip >= mflimitPlusOne) break;
1147
1148         /* Fill table */
1149         LZ4_putPosition(ip-2, cctx->hashTable, tableType, base);
1150
1151         /* Test next position */
1152         if (tableType == byPtr) {
1153
1154             match = LZ4_getPosition(ip, cctx->hashTable, tableType, base);
1155             LZ4_putPosition(ip, cctx->hashTable, tableType, base);
1156             if ( (match+LZ4_DISTANCE_MAX >= ip)
1157               && (LZ4_read32(match) == LZ4_read32(ip)) )
1158             { token=op++; *token=0; goto _next_match; }
1159
1160         } else {   /* byU32, byU16 */
1161
1162             U32 const h = LZ4_hashPosition(ip, tableType);
1163             U32 const current = (U32)(ip-base);
1164             U32 matchIndex = LZ4_getIndexOnHash(h, cctx->hashTable, tableType);
1165             assert(matchIndex < current);
1166             if (dictDirective == usingDictCtx) {
1167                 if (matchIndex < startIndex) {
1168                     /* there was no match, try the dictionary */
1169                     matchIndex = LZ4_getIndexOnHash(h, dictCtx->hashTable, byU32);
1170                     match = dictBase + matchIndex;
1171                     lowLimit = dictionary;   /* required for match length counter */
1172                     matchIndex += dictDelta;
1173                 } else {
1174                     match = base + matchIndex;
1175                     lowLimit = (const BYTE*)source;  /* required for match length counter */
1176                 }
1177             } else if (dictDirective==usingExtDict) {
1178                 if (matchIndex < startIndex) {
1179                     assert(dictBase);
1180                     match = dictBase + matchIndex;
1181                     lowLimit = dictionary;   /* required for match length counter */
1182                 } else {
1183                     match = base + matchIndex;
1184                     lowLimit = (const BYTE*)source;   /* required for match length counter */
1185                 }
1186             } else {   /* single memory segment */
1187                 match = base + matchIndex;
1188             }
1189             LZ4_putIndexOnHash(current, h, cctx->hashTable, tableType);
1190             assert(matchIndex < current);
1191             if ( ((dictIssue==dictSmall) ? (matchIndex >= prefixIdxLimit) : 1)
1192               && (((tableType==byU16) && (LZ4_DISTANCE_MAX == LZ4_DISTANCE_ABSOLUTE_MAX)) ? 1 : (matchIndex+LZ4_DISTANCE_MAX >= current))
1193               && (LZ4_read32(match) == LZ4_read32(ip)) ) {
1194                 token=op++;
1195                 *token=0;
1196                 if (maybe_extMem) offset = current - matchIndex;
1197                 DEBUGLOG(6, "seq.start:%i, literals=%u, match.start:%i",
1198                             (int)(anchor-(const BYTE*)source), 0, (int)(ip-(const BYTE*)source));
1199                 goto _next_match;
1200             }
1201         }
1202
1203         /* Prepare next loop */
1204         forwardH = LZ4_hashPosition(++ip, tableType);
1205
1206     }
1207
1208 _last_literals:
1209     /* Encode Last Literals */
1210     {   size_t lastRun = (size_t)(iend - anchor);
1211         if ( (outputDirective) &&  /* Check output buffer overflow */
1212             (op + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > olimit)) {
1213             if (outputDirective == fillOutput) {
1214                 /* adapt lastRun to fill 'dst' */
1215                 assert(olimit >= op);
1216                 lastRun  = (size_t)(olimit-op) - 1/*token*/;
1217                 lastRun -= (lastRun + 256 - RUN_MASK) / 256;  /*additional length tokens*/
1218             } else {
1219                 assert(outputDirective == limitedOutput);
1220                 return 0;   /* cannot compress within `dst` budget. Stored indexes in hash table are nonetheless fine */
1221             }
1222         }
1223         DEBUGLOG(6, "Final literal run : %i literals", (int)lastRun);
1224         if (lastRun >= RUN_MASK) {
1225             size_t accumulator = lastRun - RUN_MASK;
1226             *op++ = RUN_MASK << ML_BITS;
1227             for(; accumulator >= 255 ; accumulator-=255) *op++ = 255;
1228             *op++ = (BYTE) accumulator;
1229         } else {
1230             *op++ = (BYTE)(lastRun<<ML_BITS);
1231         }
1232         LZ4_memcpy(op, anchor, lastRun);
1233         ip = anchor + lastRun;
1234         op += lastRun;
1235     }
1236
1237     if (outputDirective == fillOutput) {
1238         *inputConsumed = (int) (((const char*)ip)-source);
1239     }
1240     result = (int)(((char*)op) - dest);
1241     assert(result > 0);
1242     DEBUGLOG(5, "LZ4_compress_generic: compressed %i bytes into %i bytes", inputSize, result);
1243     return result;
1244 }
1245
1246 /** LZ4_compress_generic() :
1247  *  inlined, to ensure branches are decided at compilation time;
1248  *  takes care of src == (NULL, 0)
1249  *  and forward the rest to LZ4_compress_generic_validated */
1250 LZ4_FORCE_INLINE int LZ4_compress_generic(
1251                  LZ4_stream_t_internal* const cctx,
1252                  const char* const src,
1253                  char* const dst,
1254                  const int srcSize,
1255                  int *inputConsumed, /* only written when outputDirective == fillOutput */
1256                  const int dstCapacity,
1257                  const limitedOutput_directive outputDirective,
1258                  const tableType_t tableType,
1259                  const dict_directive dictDirective,
1260                  const dictIssue_directive dictIssue,
1261                  const int acceleration)
1262 {
1263     DEBUGLOG(5, "LZ4_compress_generic: srcSize=%i, dstCapacity=%i",
1264                 srcSize, dstCapacity);
1265
1266     if ((U32)srcSize > (U32)LZ4_MAX_INPUT_SIZE) { return 0; }  /* Unsupported srcSize, too large (or negative) */
1267     if (srcSize == 0) {   /* src == NULL supported if srcSize == 0 */
1268         if (outputDirective != notLimited && dstCapacity <= 0) return 0;  /* no output, can't write anything */
1269         DEBUGLOG(5, "Generating an empty block");
1270         assert(outputDirective == notLimited || dstCapacity >= 1);
1271         assert(dst != NULL);
1272         dst[0] = 0;
1273         if (outputDirective == fillOutput) {
1274             assert (inputConsumed != NULL);
1275             *inputConsumed = 0;
1276         }
1277         return 1;
1278     }
1279     assert(src != NULL);
1280
1281     return LZ4_compress_generic_validated(cctx, src, dst, srcSize,
1282                 inputConsumed, /* only written into if outputDirective == fillOutput */
1283                 dstCapacity, outputDirective,
1284                 tableType, dictDirective, dictIssue, acceleration);
1285 }
1286
1287
1288 int LZ4_compress_fast_extState(void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
1289 {
1290     LZ4_stream_t_internal* const ctx = & LZ4_initStream(state, sizeof(LZ4_stream_t)) -> internal_donotuse;
1291     assert(ctx != NULL);
1292     if (acceleration < 1) acceleration = LZ4_ACCELERATION_DEFAULT;
1293     if (acceleration > LZ4_ACCELERATION_MAX) acceleration = LZ4_ACCELERATION_MAX;
1294     if (maxOutputSize >= LZ4_compressBound(inputSize)) {
1295         if (inputSize < LZ4_64Klimit) {
1296             return LZ4_compress_generic(ctx, source, dest, inputSize, NULL, 0, notLimited, byU16, noDict, noDictIssue, acceleration);
1297         } else {
1298             const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)source > LZ4_DISTANCE_MAX)) ? byPtr : byU32;
1299             return LZ4_compress_generic(ctx, source, dest, inputSize, NULL, 0, notLimited, tableType, noDict, noDictIssue, acceleration);
1300         }
1301     } else {
1302         if (inputSize < LZ4_64Klimit) {
1303             return LZ4_compress_generic(ctx, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue, acceleration);
1304         } else {
1305             const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)source > LZ4_DISTANCE_MAX)) ? byPtr : byU32;
1306             return LZ4_compress_generic(ctx, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, noDict, noDictIssue, acceleration);
1307         }
1308     }
1309 }
1310
1311 /**
1312  * LZ4_compress_fast_extState_fastReset() :
1313  * A variant of LZ4_compress_fast_extState().
1314  *
1315  * Using this variant avoids an expensive initialization step. It is only safe
1316  * to call if the state buffer is known to be correctly initialized already
1317  * (see comment in lz4.h on LZ4_resetStream_fast() for a definition of
1318  * "correctly initialized").
1319  */
1320 int LZ4_compress_fast_extState_fastReset(void* state, const char* src, char* dst, int srcSize, int dstCapacity, int acceleration)
1321 {
1322     LZ4_stream_t_internal* ctx = &((LZ4_stream_t*)state)->internal_donotuse;
1323     if (acceleration < 1) acceleration = LZ4_ACCELERATION_DEFAULT;
1324     if (acceleration > LZ4_ACCELERATION_MAX) acceleration = LZ4_ACCELERATION_MAX;
1325
1326     if (dstCapacity >= LZ4_compressBound(srcSize)) {
1327         if (srcSize < LZ4_64Klimit) {
1328             const tableType_t tableType = byU16;
1329             LZ4_prepareTable(ctx, srcSize, tableType);
1330             if (ctx->currentOffset) {
1331                 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, 0, notLimited, tableType, noDict, dictSmall, acceleration);
1332             } else {
1333                 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, 0, notLimited, tableType, noDict, noDictIssue, acceleration);
1334             }
1335         } else {
1336             const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)src > LZ4_DISTANCE_MAX)) ? byPtr : byU32;
1337             LZ4_prepareTable(ctx, srcSize, tableType);
1338             return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, 0, notLimited, tableType, noDict, noDictIssue, acceleration);
1339         }
1340     } else {
1341         if (srcSize < LZ4_64Klimit) {
1342             const tableType_t tableType = byU16;
1343             LZ4_prepareTable(ctx, srcSize, tableType);
1344             if (ctx->currentOffset) {
1345                 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, dstCapacity, limitedOutput, tableType, noDict, dictSmall, acceleration);
1346             } else {
1347                 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, dstCapacity, limitedOutput, tableType, noDict, noDictIssue, acceleration);
1348             }
1349         } else {
1350             const tableType_t tableType = ((sizeof(void*)==4) && ((uptrval)src > LZ4_DISTANCE_MAX)) ? byPtr : byU32;
1351             LZ4_prepareTable(ctx, srcSize, tableType);
1352             return LZ4_compress_generic(ctx, src, dst, srcSize, NULL, dstCapacity, limitedOutput, tableType, noDict, noDictIssue, acceleration);
1353         }
1354     }
1355 }
1356
1357
1358 int LZ4_compress_fast(const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
1359 {
1360     int result;
1361 #if (LZ4_HEAPMODE)
1362     LZ4_stream_t* ctxPtr = (LZ4_stream_t*)ALLOC(sizeof(LZ4_stream_t));   /* malloc-calloc always properly aligned */
1363     if (ctxPtr == NULL) return 0;
1364 #else
1365     LZ4_stream_t ctx;
1366     LZ4_stream_t* const ctxPtr = &ctx;
1367 #endif
1368     result = LZ4_compress_fast_extState(ctxPtr, source, dest, inputSize, maxOutputSize, acceleration);
1369
1370 #if (LZ4_HEAPMODE)
1371     FREEMEM(ctxPtr);
1372 #endif
1373     return result;
1374 }
1375
1376
1377 int LZ4_compress_default(const char* src, char* dst, int srcSize, int maxOutputSize)
1378 {
1379     return LZ4_compress_fast(src, dst, srcSize, maxOutputSize, 1);
1380 }
1381
1382
1383 /* Note!: This function leaves the stream in an unclean/broken state!
1384  * It is not safe to subsequently use the same state with a _fastReset() or
1385  * _continue() call without resetting it. */
1386 static int LZ4_compress_destSize_extState (LZ4_stream_t* state, const char* src, char* dst, int* srcSizePtr, int targetDstSize)
1387 {
1388     void* const s = LZ4_initStream(state, sizeof (*state));
1389     assert(s != NULL); (void)s;
1390
1391     if (targetDstSize >= LZ4_compressBound(*srcSizePtr)) {  /* compression success is guaranteed */
1392         return LZ4_compress_fast_extState(state, src, dst, *srcSizePtr, targetDstSize, 1);
1393     } else {
1394         if (*srcSizePtr < LZ4_64Klimit) {
1395             return LZ4_compress_generic(&state->internal_donotuse, src, dst, *srcSizePtr, srcSizePtr, targetDstSize, fillOutput, byU16, noDict, noDictIssue, 1);
1396         } else {
1397             tableType_t const addrMode = ((sizeof(void*)==4) && ((uptrval)src > LZ4_DISTANCE_MAX)) ? byPtr : byU32;
1398             return LZ4_compress_generic(&state->internal_donotuse, src, dst, *srcSizePtr, srcSizePtr, targetDstSize, fillOutput, addrMode, noDict, noDictIssue, 1);
1399     }   }
1400 }
1401
1402
1403 int LZ4_compress_destSize(const char* src, char* dst, int* srcSizePtr, int targetDstSize)
1404 {
1405 #if (LZ4_HEAPMODE)
1406     LZ4_stream_t* ctx = (LZ4_stream_t*)ALLOC(sizeof(LZ4_stream_t));   /* malloc-calloc always properly aligned */
1407     if (ctx == NULL) return 0;
1408 #else
1409     LZ4_stream_t ctxBody;
1410     LZ4_stream_t* ctx = &ctxBody;
1411 #endif
1412
1413     int result = LZ4_compress_destSize_extState(ctx, src, dst, srcSizePtr, targetDstSize);
1414
1415 #if (LZ4_HEAPMODE)
1416     FREEMEM(ctx);
1417 #endif
1418     return result;
1419 }
1420
1421
1422
1423 /*-******************************
1424 *  Streaming functions
1425 ********************************/
1426
1427 LZ4_stream_t* LZ4_createStream(void)
1428 {
1429     LZ4_stream_t* const lz4s = (LZ4_stream_t*)ALLOC(sizeof(LZ4_stream_t));
1430     LZ4_STATIC_ASSERT(LZ4_STREAMSIZE >= sizeof(LZ4_stream_t_internal));    /* A compilation error here means LZ4_STREAMSIZE is not large enough */
1431     DEBUGLOG(4, "LZ4_createStream %p", lz4s);
1432     if (lz4s == NULL) return NULL;
1433     LZ4_initStream(lz4s, sizeof(*lz4s));
1434     return lz4s;
1435 }
1436
1437 static size_t LZ4_stream_t_alignment(void)
1438 {
1439 #if LZ4_ALIGN_TEST
1440     typedef struct { char c; LZ4_stream_t t; } t_a;
1441     return sizeof(t_a) - sizeof(LZ4_stream_t);
1442 #else
1443     return 1;  /* effectively disabled */
1444 #endif
1445 }
1446
1447 LZ4_stream_t* LZ4_initStream (void* buffer, size_t size)
1448 {
1449     DEBUGLOG(5, "LZ4_initStream");
1450     if (buffer == NULL) { return NULL; }
1451     if (size < sizeof(LZ4_stream_t)) { return NULL; }
1452     if (!LZ4_isAligned(buffer, LZ4_stream_t_alignment())) return NULL;
1453     MEM_INIT(buffer, 0, sizeof(LZ4_stream_t_internal));
1454     return (LZ4_stream_t*)buffer;
1455 }
1456
1457 /* resetStream is now deprecated,
1458  * prefer initStream() which is more general */
1459 void LZ4_resetStream (LZ4_stream_t* LZ4_stream)
1460 {
1461     DEBUGLOG(5, "LZ4_resetStream (ctx:%p)", LZ4_stream);
1462     MEM_INIT(LZ4_stream, 0, sizeof(LZ4_stream_t_internal));
1463 }
1464
1465 void LZ4_resetStream_fast(LZ4_stream_t* ctx) {
1466     LZ4_prepareTable(&(ctx->internal_donotuse), 0, byU32);
1467 }
1468
1469 int LZ4_freeStream (LZ4_stream_t* LZ4_stream)
1470 {
1471     if (!LZ4_stream) return 0;   /* support free on NULL */
1472     DEBUGLOG(5, "LZ4_freeStream %p", LZ4_stream);
1473     FREEMEM(LZ4_stream);
1474     return (0);
1475 }
1476
1477
1478 #define HASH_UNIT sizeof(reg_t)
1479 int LZ4_loadDict (LZ4_stream_t* LZ4_dict, const char* dictionary, int dictSize)
1480 {
1481     LZ4_stream_t_internal* dict = &LZ4_dict->internal_donotuse;
1482     const tableType_t tableType = byU32;
1483     const BYTE* p = (const BYTE*)dictionary;
1484     const BYTE* const dictEnd = p + dictSize;
1485     const BYTE* base;
1486
1487     DEBUGLOG(4, "LZ4_loadDict (%i bytes from %p into %p)", dictSize, dictionary, LZ4_dict);
1488
1489     /* It's necessary to reset the context,
1490      * and not just continue it with prepareTable()
1491      * to avoid any risk of generating overflowing matchIndex
1492      * when compressing using this dictionary */
1493     LZ4_resetStream(LZ4_dict);
1494
1495     /* We always increment the offset by 64 KB, since, if the dict is longer,
1496      * we truncate it to the last 64k, and if it's shorter, we still want to
1497      * advance by a whole window length so we can provide the guarantee that
1498      * there are only valid offsets in the window, which allows an optimization
1499      * in LZ4_compress_fast_continue() where it uses noDictIssue even when the
1500      * dictionary isn't a full 64k. */
1501     dict->currentOffset += 64 KB;
1502
1503     if (dictSize < (int)HASH_UNIT) {
1504         return 0;
1505     }
1506
1507     if ((dictEnd - p) > 64 KB) p = dictEnd - 64 KB;
1508     base = dictEnd - dict->currentOffset;
1509     dict->dictionary = p;
1510     dict->dictSize = (U32)(dictEnd - p);
1511     dict->tableType = (U32)tableType;
1512
1513     while (p <= dictEnd-HASH_UNIT) {
1514         LZ4_putPosition(p, dict->hashTable, tableType, base);
1515         p+=3;
1516     }
1517
1518     return (int)dict->dictSize;
1519 }
1520
1521 void LZ4_attach_dictionary(LZ4_stream_t* workingStream, const LZ4_stream_t* dictionaryStream)
1522 {
1523     const LZ4_stream_t_internal* dictCtx = (dictionaryStream == NULL) ? NULL :
1524         &(dictionaryStream->internal_donotuse);
1525
1526     DEBUGLOG(4, "LZ4_attach_dictionary (%p, %p, size %u)",
1527              workingStream, dictionaryStream,
1528              dictCtx != NULL ? dictCtx->dictSize : 0);
1529
1530     if (dictCtx != NULL) {
1531         /* If the current offset is zero, we will never look in the
1532          * external dictionary context, since there is no value a table
1533          * entry can take that indicate a miss. In that case, we need
1534          * to bump the offset to something non-zero.
1535          */
1536         if (workingStream->internal_donotuse.currentOffset == 0) {
1537             workingStream->internal_donotuse.currentOffset = 64 KB;
1538         }
1539
1540         /* Don't actually attach an empty dictionary.
1541          */
1542         if (dictCtx->dictSize == 0) {
1543             dictCtx = NULL;
1544         }
1545     }
1546     workingStream->internal_donotuse.dictCtx = dictCtx;
1547 }
1548
1549
1550 static void LZ4_renormDictT(LZ4_stream_t_internal* LZ4_dict, int nextSize)
1551 {
1552     assert(nextSize >= 0);
1553     if (LZ4_dict->currentOffset + (unsigned)nextSize > 0x80000000) {   /* potential ptrdiff_t overflow (32-bits mode) */
1554         /* rescale hash table */
1555         U32 const delta = LZ4_dict->currentOffset - 64 KB;
1556         const BYTE* dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize;
1557         int i;
1558         DEBUGLOG(4, "LZ4_renormDictT");
1559         for (i=0; i<LZ4_HASH_SIZE_U32; i++) {
1560             if (LZ4_dict->hashTable[i] < delta) LZ4_dict->hashTable[i]=0;
1561             else LZ4_dict->hashTable[i] -= delta;
1562         }
1563         LZ4_dict->currentOffset = 64 KB;
1564         if (LZ4_dict->dictSize > 64 KB) LZ4_dict->dictSize = 64 KB;
1565         LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize;
1566     }
1567 }
1568
1569
1570 int LZ4_compress_fast_continue (LZ4_stream_t* LZ4_stream,
1571                                 const char* source, char* dest,
1572                                 int inputSize, int maxOutputSize,
1573                                 int acceleration)
1574 {
1575     const tableType_t tableType = byU32;
1576     LZ4_stream_t_internal* const streamPtr = &LZ4_stream->internal_donotuse;
1577     const char* dictEnd = streamPtr->dictSize ? (const char*)streamPtr->dictionary + streamPtr->dictSize : NULL;
1578
1579     DEBUGLOG(5, "LZ4_compress_fast_continue (inputSize=%i, dictSize=%u)", inputSize, streamPtr->dictSize);
1580
1581     LZ4_renormDictT(streamPtr, inputSize);   /* fix index overflow */
1582     if (acceleration < 1) acceleration = LZ4_ACCELERATION_DEFAULT;
1583     if (acceleration > LZ4_ACCELERATION_MAX) acceleration = LZ4_ACCELERATION_MAX;
1584
1585     /* invalidate tiny dictionaries */
1586     if ( (streamPtr->dictSize < 4)     /* tiny dictionary : not enough for a hash */
1587       && (dictEnd != source)           /* prefix mode */
1588       && (inputSize > 0)               /* tolerance : don't lose history, in case next invocation would use prefix mode */
1589       && (streamPtr->dictCtx == NULL)  /* usingDictCtx */
1590       ) {
1591         DEBUGLOG(5, "LZ4_compress_fast_continue: dictSize(%u) at addr:%p is too small", streamPtr->dictSize, streamPtr->dictionary);
1592         /* remove dictionary existence from history, to employ faster prefix mode */
1593         streamPtr->dictSize = 0;
1594         streamPtr->dictionary = (const BYTE*)source;
1595         dictEnd = source;
1596     }
1597
1598     /* Check overlapping input/dictionary space */
1599     {   const char* const sourceEnd = source + inputSize;
1600         if ((sourceEnd > (const char*)streamPtr->dictionary) && (sourceEnd < dictEnd)) {
1601             streamPtr->dictSize = (U32)(dictEnd - sourceEnd);
1602             if (streamPtr->dictSize > 64 KB) streamPtr->dictSize = 64 KB;
1603             if (streamPtr->dictSize < 4) streamPtr->dictSize = 0;
1604             streamPtr->dictionary = (const BYTE*)dictEnd - streamPtr->dictSize;
1605         }
1606     }
1607
1608     /* prefix mode : source data follows dictionary */
1609     if (dictEnd == source) {
1610         if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset))
1611             return LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, withPrefix64k, dictSmall, acceleration);
1612         else
1613             return LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, withPrefix64k, noDictIssue, acceleration);
1614     }
1615
1616     /* external dictionary mode */
1617     {   int result;
1618         if (streamPtr->dictCtx) {
1619             /* We depend here on the fact that dictCtx'es (produced by
1620              * LZ4_loadDict) guarantee that their tables contain no references
1621              * to offsets between dictCtx->currentOffset - 64 KB and
1622              * dictCtx->currentOffset - dictCtx->dictSize. This makes it safe
1623              * to use noDictIssue even when the dict isn't a full 64 KB.
1624              */
1625             if (inputSize > 4 KB) {
1626                 /* For compressing large blobs, it is faster to pay the setup
1627                  * cost to copy the dictionary's tables into the active context,
1628                  * so that the compression loop is only looking into one table.
1629                  */
1630                 LZ4_memcpy(streamPtr, streamPtr->dictCtx, sizeof(*streamPtr));
1631                 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, usingExtDict, noDictIssue, acceleration);
1632             } else {
1633                 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, usingDictCtx, noDictIssue, acceleration);
1634             }
1635         } else {  /* small data <= 4 KB */
1636             if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) {
1637                 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, usingExtDict, dictSmall, acceleration);
1638             } else {
1639                 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL, maxOutputSize, limitedOutput, tableType, usingExtDict, noDictIssue, acceleration);
1640             }
1641         }
1642         streamPtr->dictionary = (const BYTE*)source;
1643         streamPtr->dictSize = (U32)inputSize;
1644         return result;
1645     }
1646 }
1647
1648
1649 /* Hidden debug function, to force-test external dictionary mode */
1650 int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int srcSize)
1651 {
1652     LZ4_stream_t_internal* streamPtr = &LZ4_dict->internal_donotuse;
1653     int result;
1654
1655     LZ4_renormDictT(streamPtr, srcSize);
1656
1657     if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) {
1658         result = LZ4_compress_generic(streamPtr, source, dest, srcSize, NULL, 0, notLimited, byU32, usingExtDict, dictSmall, 1);
1659     } else {
1660         result = LZ4_compress_generic(streamPtr, source, dest, srcSize, NULL, 0, notLimited, byU32, usingExtDict, noDictIssue, 1);
1661     }
1662
1663     streamPtr->dictionary = (const BYTE*)source;
1664     streamPtr->dictSize = (U32)srcSize;
1665
1666     return result;
1667 }
1668
1669
1670 /*! LZ4_saveDict() :
1671  *  If previously compressed data block is not guaranteed to remain available at its memory location,
1672  *  save it into a safer place (char* safeBuffer).
1673  *  Note : no need to call LZ4_loadDict() afterwards, dictionary is immediately usable,
1674  *         one can therefore call LZ4_compress_fast_continue() right after.
1675  * @return : saved dictionary size in bytes (necessarily <= dictSize), or 0 if error.
1676  */
1677 int LZ4_saveDict (LZ4_stream_t* LZ4_dict, char* safeBuffer, int dictSize)
1678 {
1679     LZ4_stream_t_internal* const dict = &LZ4_dict->internal_donotuse;
1680
1681     DEBUGLOG(5, "LZ4_saveDict : dictSize=%i, safeBuffer=%p", dictSize, safeBuffer);
1682
1683     if ((U32)dictSize > 64 KB) { dictSize = 64 KB; } /* useless to define a dictionary > 64 KB */
1684     if ((U32)dictSize > dict->dictSize) { dictSize = (int)dict->dictSize; }
1685
1686     if (safeBuffer == NULL) assert(dictSize == 0);
1687     if (dictSize > 0) {
1688         const BYTE* const previousDictEnd = dict->dictionary + dict->dictSize;
1689         assert(dict->dictionary);
1690         memmove(safeBuffer, previousDictEnd - dictSize, dictSize);
1691     }
1692
1693     dict->dictionary = (const BYTE*)safeBuffer;
1694     dict->dictSize = (U32)dictSize;
1695
1696     return dictSize;
1697 }
1698
1699
1700
1701 /*-*******************************
1702  *  Decompression functions
1703  ********************************/
1704
1705 typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;
1706 typedef enum { decode_full_block = 0, partial_decode = 1 } earlyEnd_directive;
1707
1708 #undef MIN
1709 #define MIN(a,b)    ( (a) < (b) ? (a) : (b) )
1710
1711 /* Read the variable-length literal or match length.
1712  *
1713  * ip - pointer to use as input.
1714  * lencheck - end ip.  Return an error if ip advances >= lencheck.
1715  * loop_check - check ip >= lencheck in body of loop.  Returns loop_error if so.
1716  * initial_check - check ip >= lencheck before start of loop.  Returns initial_error if so.
1717  * error (output) - error code.  Should be set to 0 before call.
1718  */
1719 typedef enum { loop_error = -2, initial_error = -1, ok = 0 } variable_length_error;
1720 LZ4_FORCE_INLINE unsigned
1721 read_variable_length(const BYTE**ip, const BYTE* lencheck,
1722                      int loop_check, int initial_check,
1723                      variable_length_error* error)
1724 {
1725     U32 length = 0;
1726     U32 s;
1727     if (initial_check && unlikely((*ip) >= lencheck)) {    /* overflow detection */
1728         *error = initial_error;
1729         return length;
1730     }
1731     do {
1732         s = **ip;
1733         (*ip)++;
1734         length += s;
1735         if (loop_check && unlikely((*ip) >= lencheck)) {    /* overflow detection */
1736             *error = loop_error;
1737             return length;
1738         }
1739     } while (s==255);
1740
1741     return length;
1742 }
1743
1744 /*! LZ4_decompress_generic() :
1745  *  This generic decompression function covers all use cases.
1746  *  It shall be instantiated several times, using different sets of directives.
1747  *  Note that it is important for performance that this function really get inlined,
1748  *  in order to remove useless branches during compilation optimization.
1749  */
1750 LZ4_FORCE_INLINE int
1751 LZ4_decompress_generic(
1752                  const char* const src,
1753                  char* const dst,
1754                  int srcSize,
1755                  int outputSize,         /* If endOnInput==endOnInputSize, this value is `dstCapacity` */
1756
1757                  endCondition_directive endOnInput,   /* endOnOutputSize, endOnInputSize */
1758                  earlyEnd_directive partialDecoding,  /* full, partial */
1759                  dict_directive dict,                 /* noDict, withPrefix64k, usingExtDict */
1760                  const BYTE* const lowPrefix,  /* always <= dst, == dst when no prefix */
1761                  const BYTE* const dictStart,  /* only if dict==usingExtDict */
1762                  const size_t dictSize         /* note : = 0 if noDict */
1763                  )
1764 {
1765     if ((src == NULL) || (outputSize < 0)) { return -1; }
1766
1767     {   const BYTE* ip = (const BYTE*) src;
1768         const BYTE* const iend = ip + srcSize;
1769
1770         BYTE* op = (BYTE*) dst;
1771         BYTE* const oend = op + outputSize;
1772         BYTE* cpy;
1773
1774         const BYTE* const dictEnd = (dictStart == NULL) ? NULL : dictStart + dictSize;
1775
1776         const int safeDecode = (endOnInput==endOnInputSize);
1777         const int checkOffset = ((safeDecode) && (dictSize < (int)(64 KB)));
1778
1779
1780         /* Set up the "end" pointers for the shortcut. */
1781         const BYTE* const shortiend = iend - (endOnInput ? 14 : 8) /*maxLL*/ - 2 /*offset*/;
1782         const BYTE* const shortoend = oend - (endOnInput ? 14 : 8) /*maxLL*/ - 18 /*maxML*/;
1783
1784         const BYTE* match;
1785         size_t offset;
1786         unsigned token;
1787         size_t length;
1788
1789
1790         DEBUGLOG(5, "LZ4_decompress_generic (srcSize:%i, dstSize:%i)", srcSize, outputSize);
1791
1792         /* Special cases */
1793         assert(lowPrefix <= op);
1794         if ((endOnInput) && (unlikely(outputSize==0))) {
1795             /* Empty output buffer */
1796             if (partialDecoding) return 0;
1797             return ((srcSize==1) && (*ip==0)) ? 0 : -1;
1798         }
1799         if ((!endOnInput) && (unlikely(outputSize==0))) { return (*ip==0 ? 1 : -1); }
1800         if ((endOnInput) && unlikely(srcSize==0)) { return -1; }
1801
1802         /* Currently the fast loop shows a regression on qualcomm arm chips. */
1803 #if LZ4_FAST_DEC_LOOP
1804         if ((oend - op) < FASTLOOP_SAFE_DISTANCE) {
1805             DEBUGLOG(6, "skip fast decode loop");
1806             goto safe_decode;
1807         }
1808
1809         /* Fast loop : decode sequences as long as output < iend-FASTLOOP_SAFE_DISTANCE */
1810         while (1) {
1811             /* Main fastloop assertion: We can always wildcopy FASTLOOP_SAFE_DISTANCE */
1812             assert(oend - op >= FASTLOOP_SAFE_DISTANCE);
1813             if (endOnInput) { assert(ip < iend); }
1814             token = *ip++;
1815             length = token >> ML_BITS;  /* literal length */
1816
1817             assert(!endOnInput || ip <= iend); /* ip < iend before the increment */
1818
1819             /* decode literal length */
1820             if (length == RUN_MASK) {
1821                 variable_length_error error = ok;
1822                 length += read_variable_length(&ip, iend-RUN_MASK, (int)endOnInput, (int)endOnInput, &error);
1823                 if (error == initial_error) { goto _output_error; }
1824                 if ((safeDecode) && unlikely((uptrval)(op)+length<(uptrval)(op))) { goto _output_error; } /* overflow detection */
1825                 if ((safeDecode) && unlikely((uptrval)(ip)+length<(uptrval)(ip))) { goto _output_error; } /* overflow detection */
1826
1827                 /* copy literals */
1828                 cpy = op+length;
1829                 LZ4_STATIC_ASSERT(MFLIMIT >= WILDCOPYLENGTH);
1830                 if (endOnInput) {  /* LZ4_decompress_safe() */
1831                     if ((cpy>oend-32) || (ip+length>iend-32)) { goto safe_literal_copy; }
1832                     LZ4_wildCopy32(op, ip, cpy);
1833                 } else {   /* LZ4_decompress_fast() */
1834                     if (cpy>oend-8) { goto safe_literal_copy; }
1835                     LZ4_wildCopy8(op, ip, cpy); /* LZ4_decompress_fast() cannot copy more than 8 bytes at a time :
1836                                                  * it doesn't know input length, and only relies on end-of-block properties */
1837                 }
1838                 ip += length; op = cpy;
1839             } else {
1840                 cpy = op+length;
1841                 if (endOnInput) {  /* LZ4_decompress_safe() */
1842                     DEBUGLOG(7, "copy %u bytes in a 16-bytes stripe", (unsigned)length);
1843                     /* We don't need to check oend, since we check it once for each loop below */
1844                     if (ip > iend-(16 + 1/*max lit + offset + nextToken*/)) { goto safe_literal_copy; }
1845                     /* Literals can only be 14, but hope compilers optimize if we copy by a register size */
1846                     LZ4_memcpy(op, ip, 16);
1847                 } else {  /* LZ4_decompress_fast() */
1848                     /* LZ4_decompress_fast() cannot copy more than 8 bytes at a time :
1849                      * it doesn't know input length, and relies on end-of-block properties */
1850                     LZ4_memcpy(op, ip, 8);
1851                     if (length > 8) { LZ4_memcpy(op+8, ip+8, 8); }
1852                 }
1853                 ip += length; op = cpy;
1854             }
1855
1856             /* get offset */
1857             offset = LZ4_readLE16(ip); ip+=2;
1858             match = op - offset;
1859             assert(match <= op);
1860
1861             /* get matchlength */
1862             length = token & ML_MASK;
1863
1864             if (length == ML_MASK) {
1865                 variable_length_error error = ok;
1866                 if ((checkOffset) && (unlikely(match + dictSize < lowPrefix))) { goto _output_error; } /* Error : offset outside buffers */
1867                 length += read_variable_length(&ip, iend - LASTLITERALS + 1, (int)endOnInput, 0, &error);
1868                 if (error != ok) { goto _output_error; }
1869                 if ((safeDecode) && unlikely((uptrval)(op)+length<(uptrval)op)) { goto _output_error; } /* overflow detection */
1870                 length += MINMATCH;
1871                 if (op + length >= oend - FASTLOOP_SAFE_DISTANCE) {
1872                     goto safe_match_copy;
1873                 }
1874             } else {
1875                 length += MINMATCH;
1876                 if (op + length >= oend - FASTLOOP_SAFE_DISTANCE) {
1877                     goto safe_match_copy;
1878                 }
1879
1880                 /* Fastpath check: Avoids a branch in LZ4_wildCopy32 if true */
1881                 if ((dict == withPrefix64k) || (match >= lowPrefix)) {
1882                     if (offset >= 8) {
1883                         assert(match >= lowPrefix);
1884                         assert(match <= op);
1885                         assert(op + 18 <= oend);
1886
1887                         LZ4_memcpy(op, match, 8);
1888                         LZ4_memcpy(op+8, match+8, 8);
1889                         LZ4_memcpy(op+16, match+16, 2);
1890                         op += length;
1891                         continue;
1892             }   }   }
1893
1894             if (checkOffset && (unlikely(match + dictSize < lowPrefix))) { goto _output_error; } /* Error : offset outside buffers */
1895             /* match starting within external dictionary */
1896             if ((dict==usingExtDict) && (match < lowPrefix)) {
1897                 if (unlikely(op+length > oend-LASTLITERALS)) {
1898                     if (partialDecoding) {
1899                         DEBUGLOG(7, "partialDecoding: dictionary match, close to dstEnd");
1900                         length = MIN(length, (size_t)(oend-op));
1901                     } else {
1902                         goto _output_error;  /* end-of-block condition violated */
1903                 }   }
1904
1905                 if (length <= (size_t)(lowPrefix-match)) {
1906                     /* match fits entirely within external dictionary : just copy */
1907                     memmove(op, dictEnd - (lowPrefix-match), length);
1908                     op += length;
1909                 } else {
1910                     /* match stretches into both external dictionary and current block */
1911                     size_t const copySize = (size_t)(lowPrefix - match);
1912                     size_t const restSize = length - copySize;
1913                     LZ4_memcpy(op, dictEnd - copySize, copySize);
1914                     op += copySize;
1915                     if (restSize > (size_t)(op - lowPrefix)) {  /* overlap copy */
1916                         BYTE* const endOfMatch = op + restSize;
1917                         const BYTE* copyFrom = lowPrefix;
1918                         while (op < endOfMatch) { *op++ = *copyFrom++; }
1919                     } else {
1920                         LZ4_memcpy(op, lowPrefix, restSize);
1921                         op += restSize;
1922                 }   }
1923                 continue;
1924             }
1925
1926             /* copy match within block */
1927             cpy = op + length;
1928
1929             assert((op <= oend) && (oend-op >= 32));
1930             if (unlikely(offset<16)) {
1931                 LZ4_memcpy_using_offset(op, match, cpy, offset);
1932             } else {
1933                 LZ4_wildCopy32(op, match, cpy);
1934             }
1935
1936             op = cpy;   /* wildcopy correction */
1937         }
1938     safe_decode:
1939 #endif
1940
1941         /* Main Loop : decode remaining sequences where output < FASTLOOP_SAFE_DISTANCE */
1942         while (1) {
1943             token = *ip++;
1944             length = token >> ML_BITS;  /* literal length */
1945
1946             assert(!endOnInput || ip <= iend); /* ip < iend before the increment */
1947
1948             /* A two-stage shortcut for the most common case:
1949              * 1) If the literal length is 0..14, and there is enough space,
1950              * enter the shortcut and copy 16 bytes on behalf of the literals
1951              * (in the fast mode, only 8 bytes can be safely copied this way).
1952              * 2) Further if the match length is 4..18, copy 18 bytes in a similar
1953              * manner; but we ensure that there's enough space in the output for
1954              * those 18 bytes earlier, upon entering the shortcut (in other words,
1955              * there is a combined check for both stages).
1956              */
1957             if ( (endOnInput ? length != RUN_MASK : length <= 8)
1958                 /* strictly "less than" on input, to re-enter the loop with at least one byte */
1959               && likely((endOnInput ? ip < shortiend : 1) & (op <= shortoend)) ) {
1960                 /* Copy the literals */
1961                 LZ4_memcpy(op, ip, endOnInput ? 16 : 8);
1962                 op += length; ip += length;
1963
1964                 /* The second stage: prepare for match copying, decode full info.
1965                  * If it doesn't work out, the info won't be wasted. */
1966                 length = token & ML_MASK; /* match length */
1967                 offset = LZ4_readLE16(ip); ip += 2;
1968                 match = op - offset;
1969                 assert(match <= op); /* check overflow */
1970
1971                 /* Do not deal with overlapping matches. */
1972                 if ( (length != ML_MASK)
1973                   && (offset >= 8)
1974                   && (dict==withPrefix64k || match >= lowPrefix) ) {
1975                     /* Copy the match. */
1976                     LZ4_memcpy(op + 0, match + 0, 8);
1977                     LZ4_memcpy(op + 8, match + 8, 8);
1978                     LZ4_memcpy(op +16, match +16, 2);
1979                     op += length + MINMATCH;
1980                     /* Both stages worked, load the next token. */
1981                     continue;
1982                 }
1983
1984                 /* The second stage didn't work out, but the info is ready.
1985                  * Propel it right to the point of match copying. */
1986                 goto _copy_match;
1987             }
1988
1989             /* decode literal length */
1990             if (length == RUN_MASK) {
1991                 variable_length_error error = ok;
1992                 length += read_variable_length(&ip, iend-RUN_MASK, (int)endOnInput, (int)endOnInput, &error);
1993                 if (error == initial_error) { goto _output_error; }
1994                 if ((safeDecode) && unlikely((uptrval)(op)+length<(uptrval)(op))) { goto _output_error; } /* overflow detection */
1995                 if ((safeDecode) && unlikely((uptrval)(ip)+length<(uptrval)(ip))) { goto _output_error; } /* overflow detection */
1996             }
1997
1998             /* copy literals */
1999             cpy = op+length;
2000 #if LZ4_FAST_DEC_LOOP
2001         safe_literal_copy:
2002 #endif
2003             LZ4_STATIC_ASSERT(MFLIMIT >= WILDCOPYLENGTH);
2004             if ( ((endOnInput) && ((cpy>oend-MFLIMIT) || (ip+length>iend-(2+1+LASTLITERALS))) )
2005               || ((!endOnInput) && (cpy>oend-WILDCOPYLENGTH)) )
2006             {
2007                 /* We've either hit the input parsing restriction or the output parsing restriction.
2008                  * In the normal scenario, decoding a full block, it must be the last sequence,
2009                  * otherwise it's an error (invalid input or dimensions).
2010                  * In partialDecoding scenario, it's necessary to ensure there is no buffer overflow.
2011                  */
2012                 if (partialDecoding) {
2013                     /* Since we are partial decoding we may be in this block because of the output parsing
2014                      * restriction, which is not valid since the output buffer is allowed to be undersized.
2015                      */
2016                     assert(endOnInput);
2017                     DEBUGLOG(7, "partialDecoding: copying literals, close to input or output end")
2018                     DEBUGLOG(7, "partialDecoding: literal length = %u", (unsigned)length);
2019                     DEBUGLOG(7, "partialDecoding: remaining space in dstBuffer : %i", (int)(oend - op));
2020                     DEBUGLOG(7, "partialDecoding: remaining space in srcBuffer : %i", (int)(iend - ip));
2021                     /* Finishing in the middle of a literals segment,
2022                      * due to lack of input.
2023                      */
2024                     if (ip+length > iend) {
2025                         length = (size_t)(iend-ip);
2026                         cpy = op + length;
2027                     }
2028                     /* Finishing in the middle of a literals segment,
2029                      * due to lack of output space.
2030                      */
2031                     if (cpy > oend) {
2032                         cpy = oend;
2033                         assert(op<=oend);
2034                         length = (size_t)(oend-op);
2035                     }
2036                 } else {
2037                     /* We must be on the last sequence because of the parsing limitations so check
2038                      * that we exactly regenerate the original size (must be exact when !endOnInput).
2039                      */
2040                     if ((!endOnInput) && (cpy != oend)) { goto _output_error; }
2041                      /* We must be on the last sequence (or invalid) because of the parsing limitations
2042                       * so check that we exactly consume the input and don't overrun the output buffer.
2043                       */
2044                     if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) {
2045                         DEBUGLOG(6, "should have been last run of literals")
2046                         DEBUGLOG(6, "ip(%p) + length(%i) = %p != iend (%p)", ip, (int)length, ip+length, iend);
2047                         DEBUGLOG(6, "or cpy(%p) > oend(%p)", cpy, oend);
2048                         goto _output_error;
2049                     }
2050                 }
2051                 memmove(op, ip, length);  /* supports overlapping memory regions; only matters for in-place decompression scenarios */
2052                 ip += length;
2053                 op += length;
2054                 /* Necessarily EOF when !partialDecoding.
2055                  * When partialDecoding, it is EOF if we've either
2056                  * filled the output buffer or
2057                  * can't proceed with reading an offset for following match.
2058                  */
2059                 if (!partialDecoding || (cpy == oend) || (ip >= (iend-2))) {
2060                     break;
2061                 }
2062             } else {
2063                 LZ4_wildCopy8(op, ip, cpy);   /* may overwrite up to WILDCOPYLENGTH beyond cpy */
2064                 ip += length; op = cpy;
2065             }
2066
2067             /* get offset */
2068             offset = LZ4_readLE16(ip); ip+=2;
2069             match = op - offset;
2070
2071             /* get matchlength */
2072             length = token & ML_MASK;
2073
2074     _copy_match:
2075             if (length == ML_MASK) {
2076               variable_length_error error = ok;
2077               length += read_variable_length(&ip, iend - LASTLITERALS + 1, (int)endOnInput, 0, &error);
2078               if (error != ok) goto _output_error;
2079                 if ((safeDecode) && unlikely((uptrval)(op)+length<(uptrval)op)) goto _output_error;   /* overflow detection */
2080             }
2081             length += MINMATCH;
2082
2083 #if LZ4_FAST_DEC_LOOP
2084         safe_match_copy:
2085 #endif
2086             if ((checkOffset) && (unlikely(match + dictSize < lowPrefix))) goto _output_error;   /* Error : offset outside buffers */
2087             /* match starting within external dictionary */
2088             if ((dict==usingExtDict) && (match < lowPrefix)) {
2089                 if (unlikely(op+length > oend-LASTLITERALS)) {
2090                     if (partialDecoding) length = MIN(length, (size_t)(oend-op));
2091                     else goto _output_error;   /* doesn't respect parsing restriction */
2092                 }
2093
2094                 if (length <= (size_t)(lowPrefix-match)) {
2095                     /* match fits entirely within external dictionary : just copy */
2096                     memmove(op, dictEnd - (lowPrefix-match), length);
2097                     op += length;
2098                 } else {
2099                     /* match stretches into both external dictionary and current block */
2100                     size_t const copySize = (size_t)(lowPrefix - match);
2101                     size_t const restSize = length - copySize;
2102                     LZ4_memcpy(op, dictEnd - copySize, copySize);
2103                     op += copySize;
2104                     if (restSize > (size_t)(op - lowPrefix)) {  /* overlap copy */
2105                         BYTE* const endOfMatch = op + restSize;
2106                         const BYTE* copyFrom = lowPrefix;
2107                         while (op < endOfMatch) *op++ = *copyFrom++;
2108                     } else {
2109                         LZ4_memcpy(op, lowPrefix, restSize);
2110                         op += restSize;
2111                 }   }
2112                 continue;
2113             }
2114             assert(match >= lowPrefix);
2115
2116             /* copy match within block */
2117             cpy = op + length;
2118
2119             /* partialDecoding : may end anywhere within the block */
2120             assert(op<=oend);
2121             if (partialDecoding && (cpy > oend-MATCH_SAFEGUARD_DISTANCE)) {
2122                 size_t const mlen = MIN(length, (size_t)(oend-op));
2123                 const BYTE* const matchEnd = match + mlen;
2124                 BYTE* const copyEnd = op + mlen;
2125                 if (matchEnd > op) {   /* overlap copy */
2126                     while (op < copyEnd) { *op++ = *match++; }
2127                 } else {
2128                     LZ4_memcpy(op, match, mlen);
2129                 }
2130                 op = copyEnd;
2131                 if (op == oend) { break; }
2132                 continue;
2133             }
2134
2135             if (unlikely(offset<8)) {
2136                 LZ4_write32(op, 0);   /* silence msan warning when offset==0 */
2137                 op[0] = match[0];
2138                 op[1] = match[1];
2139                 op[2] = match[2];
2140                 op[3] = match[3];
2141                 match += inc32table[offset];
2142                 LZ4_memcpy(op+4, match, 4);
2143                 match -= dec64table[offset];
2144             } else {
2145                 LZ4_memcpy(op, match, 8);
2146                 match += 8;
2147             }
2148             op += 8;
2149
2150             if (unlikely(cpy > oend-MATCH_SAFEGUARD_DISTANCE)) {
2151                 BYTE* const oCopyLimit = oend - (WILDCOPYLENGTH-1);
2152                 if (cpy > oend-LASTLITERALS) { goto _output_error; } /* Error : last LASTLITERALS bytes must be literals (uncompressed) */
2153                 if (op < oCopyLimit) {
2154                     LZ4_wildCopy8(op, match, oCopyLimit);
2155                     match += oCopyLimit - op;
2156                     op = oCopyLimit;
2157                 }
2158                 while (op < cpy) { *op++ = *match++; }
2159             } else {
2160                 LZ4_memcpy(op, match, 8);
2161                 if (length > 16)  { LZ4_wildCopy8(op+8, match+8, cpy); }
2162             }
2163             op = cpy;   /* wildcopy correction */
2164         }
2165
2166         /* end of decoding */
2167         if (endOnInput) {
2168             DEBUGLOG(5, "decoded %i bytes", (int) (((char*)op)-dst));
2169            return (int) (((char*)op)-dst);     /* Nb of output bytes decoded */
2170        } else {
2171            return (int) (((const char*)ip)-src);   /* Nb of input bytes read */
2172        }
2173
2174         /* Overflow error detected */
2175     _output_error:
2176         return (int) (-(((const char*)ip)-src))-1;
2177     }
2178 }
2179
2180
2181 /*===== Instantiate the API decoding functions. =====*/
2182
2183 LZ4_FORCE_O2
2184 int LZ4_decompress_safe(const char* source, char* dest, int compressedSize, int maxDecompressedSize)
2185 {
2186     return LZ4_decompress_generic(source, dest, compressedSize, maxDecompressedSize,
2187                                   endOnInputSize, decode_full_block, noDict,
2188                                   (BYTE*)dest, NULL, 0);
2189 }
2190
2191 LZ4_FORCE_O2
2192 int LZ4_decompress_safe_partial(const char* src, char* dst, int compressedSize, int targetOutputSize, int dstCapacity)
2193 {
2194     dstCapacity = MIN(targetOutputSize, dstCapacity);
2195     return LZ4_decompress_generic(src, dst, compressedSize, dstCapacity,
2196                                   endOnInputSize, partial_decode,
2197                                   noDict, (BYTE*)dst, NULL, 0);
2198 }
2199
2200 LZ4_FORCE_O2
2201 int LZ4_decompress_fast(const char* source, char* dest, int originalSize)
2202 {
2203     return LZ4_decompress_generic(source, dest, 0, originalSize,
2204                                   endOnOutputSize, decode_full_block, withPrefix64k,
2205                                   (BYTE*)dest - 64 KB, NULL, 0);
2206 }
2207
2208 /*===== Instantiate a few more decoding cases, used more than once. =====*/
2209
2210 LZ4_FORCE_O2 /* Exported, an obsolete API function. */
2211 int LZ4_decompress_safe_withPrefix64k(const char* source, char* dest, int compressedSize, int maxOutputSize)
2212 {
2213     return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
2214                                   endOnInputSize, decode_full_block, withPrefix64k,
2215                                   (BYTE*)dest - 64 KB, NULL, 0);
2216 }
2217
2218 /* Another obsolete API function, paired with the previous one. */
2219 int LZ4_decompress_fast_withPrefix64k(const char* source, char* dest, int originalSize)
2220 {
2221     /* LZ4_decompress_fast doesn't validate match offsets,
2222      * and thus serves well with any prefixed dictionary. */
2223     return LZ4_decompress_fast(source, dest, originalSize);
2224 }
2225
2226 LZ4_FORCE_O2
2227 static int LZ4_decompress_safe_withSmallPrefix(const char* source, char* dest, int compressedSize, int maxOutputSize,
2228                                                size_t prefixSize)
2229 {
2230     return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
2231                                   endOnInputSize, decode_full_block, noDict,
2232                                   (BYTE*)dest-prefixSize, NULL, 0);
2233 }
2234
2235 LZ4_FORCE_O2
2236 int LZ4_decompress_safe_forceExtDict(const char* source, char* dest,
2237                                      int compressedSize, int maxOutputSize,
2238                                      const void* dictStart, size_t dictSize)
2239 {
2240     return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
2241                                   endOnInputSize, decode_full_block, usingExtDict,
2242                                   (BYTE*)dest, (const BYTE*)dictStart, dictSize);
2243 }
2244
2245 LZ4_FORCE_O2
2246 static int LZ4_decompress_fast_extDict(const char* source, char* dest, int originalSize,
2247                                        const void* dictStart, size_t dictSize)
2248 {
2249     return LZ4_decompress_generic(source, dest, 0, originalSize,
2250                                   endOnOutputSize, decode_full_block, usingExtDict,
2251                                   (BYTE*)dest, (const BYTE*)dictStart, dictSize);
2252 }
2253
2254 /* The "double dictionary" mode, for use with e.g. ring buffers: the first part
2255  * of the dictionary is passed as prefix, and the second via dictStart + dictSize.
2256  * These routines are used only once, in LZ4_decompress_*_continue().
2257  */
2258 LZ4_FORCE_INLINE
2259 int LZ4_decompress_safe_doubleDict(const char* source, char* dest, int compressedSize, int maxOutputSize,
2260                                    size_t prefixSize, const void* dictStart, size_t dictSize)
2261 {
2262     return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
2263                                   endOnInputSize, decode_full_block, usingExtDict,
2264                                   (BYTE*)dest-prefixSize, (const BYTE*)dictStart, dictSize);
2265 }
2266
2267 LZ4_FORCE_INLINE
2268 int LZ4_decompress_fast_doubleDict(const char* source, char* dest, int originalSize,
2269                                    size_t prefixSize, const void* dictStart, size_t dictSize)
2270 {
2271     return LZ4_decompress_generic(source, dest, 0, originalSize,
2272                                   endOnOutputSize, decode_full_block, usingExtDict,
2273                                   (BYTE*)dest-prefixSize, (const BYTE*)dictStart, dictSize);
2274 }
2275
2276 /*===== streaming decompression functions =====*/
2277
2278 LZ4_streamDecode_t* LZ4_createStreamDecode(void)
2279 {
2280     LZ4_streamDecode_t* lz4s = (LZ4_streamDecode_t*) ALLOC_AND_ZERO(sizeof(LZ4_streamDecode_t));
2281     LZ4_STATIC_ASSERT(LZ4_STREAMDECODESIZE >= sizeof(LZ4_streamDecode_t_internal));    /* A compilation error here means LZ4_STREAMDECODESIZE is not large enough */
2282     return lz4s;
2283 }
2284
2285 int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream)
2286 {
2287     if (LZ4_stream == NULL) { return 0; }  /* support free on NULL */
2288     FREEMEM(LZ4_stream);
2289     return 0;
2290 }
2291
2292 /*! LZ4_setStreamDecode() :
2293  *  Use this function to instruct where to find the dictionary.
2294  *  This function is not necessary if previous data is still available where it was decoded.
2295  *  Loading a size of 0 is allowed (same effect as no dictionary).
2296  * @return : 1 if OK, 0 if error
2297  */
2298 int LZ4_setStreamDecode (LZ4_streamDecode_t* LZ4_streamDecode, const char* dictionary, int dictSize)
2299 {
2300     LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse;
2301     lz4sd->prefixSize = (size_t)dictSize;
2302     if (dictSize) {
2303         assert(dictionary != NULL);
2304         lz4sd->prefixEnd = (const BYTE*) dictionary + dictSize;
2305     } else {
2306         lz4sd->prefixEnd = (const BYTE*) dictionary;
2307     }
2308     lz4sd->externalDict = NULL;
2309     lz4sd->extDictSize  = 0;
2310     return 1;
2311 }
2312
2313 /*! LZ4_decoderRingBufferSize() :
2314  *  when setting a ring buffer for streaming decompression (optional scenario),
2315  *  provides the minimum size of this ring buffer
2316  *  to be compatible with any source respecting maxBlockSize condition.
2317  *  Note : in a ring buffer scenario,
2318  *  blocks are presumed decompressed next to each other.
2319  *  When not enough space remains for next block (remainingSize < maxBlockSize),
2320  *  decoding resumes from beginning of ring buffer.
2321  * @return : minimum ring buffer size,
2322  *           or 0 if there is an error (invalid maxBlockSize).
2323  */
2324 int LZ4_decoderRingBufferSize(int maxBlockSize)
2325 {
2326     if (maxBlockSize < 0) return 0;
2327     if (maxBlockSize > LZ4_MAX_INPUT_SIZE) return 0;
2328     if (maxBlockSize < 16) maxBlockSize = 16;
2329     return LZ4_DECODER_RING_BUFFER_SIZE(maxBlockSize);
2330 }
2331
2332 /*
2333 *_continue() :
2334     These decoding functions allow decompression of multiple blocks in "streaming" mode.
2335     Previously decoded blocks must still be available at the memory position where they were decoded.
2336     If it's not possible, save the relevant part of decoded data into a safe buffer,
2337     and indicate where it stands using LZ4_setStreamDecode()
2338 */
2339 LZ4_FORCE_O2
2340 int LZ4_decompress_safe_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int compressedSize, int maxOutputSize)
2341 {
2342     LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse;
2343     int result;
2344
2345     if (lz4sd->prefixSize == 0) {
2346         /* The first call, no dictionary yet. */
2347         assert(lz4sd->extDictSize == 0);
2348         result = LZ4_decompress_safe(source, dest, compressedSize, maxOutputSize);
2349         if (result <= 0) return result;
2350         lz4sd->prefixSize = (size_t)result;
2351         lz4sd->prefixEnd = (BYTE*)dest + result;
2352     } else if (lz4sd->prefixEnd == (BYTE*)dest) {
2353         /* They're rolling the current segment. */
2354         if (lz4sd->prefixSize >= 64 KB - 1)
2355             result = LZ4_decompress_safe_withPrefix64k(source, dest, compressedSize, maxOutputSize);
2356         else if (lz4sd->extDictSize == 0)
2357             result = LZ4_decompress_safe_withSmallPrefix(source, dest, compressedSize, maxOutputSize,
2358                                                          lz4sd->prefixSize);
2359         else
2360             result = LZ4_decompress_safe_doubleDict(source, dest, compressedSize, maxOutputSize,
2361                                                     lz4sd->prefixSize, lz4sd->externalDict, lz4sd->extDictSize);
2362         if (result <= 0) return result;
2363         lz4sd->prefixSize += (size_t)result;
2364         lz4sd->prefixEnd  += result;
2365     } else {
2366         /* The buffer wraps around, or they're switching to another buffer. */
2367         lz4sd->extDictSize = lz4sd->prefixSize;
2368         lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize;
2369         result = LZ4_decompress_safe_forceExtDict(source, dest, compressedSize, maxOutputSize,
2370                                                   lz4sd->externalDict, lz4sd->extDictSize);
2371         if (result <= 0) return result;
2372         lz4sd->prefixSize = (size_t)result;
2373         lz4sd->prefixEnd  = (BYTE*)dest + result;
2374     }
2375
2376     return result;
2377 }
2378
2379 LZ4_FORCE_O2
2380 int LZ4_decompress_fast_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int originalSize)
2381 {
2382     LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse;
2383     int result;
2384     assert(originalSize >= 0);
2385
2386     if (lz4sd->prefixSize == 0) {
2387         assert(lz4sd->extDictSize == 0);
2388         result = LZ4_decompress_fast(source, dest, originalSize);
2389         if (result <= 0) return result;
2390         lz4sd->prefixSize = (size_t)originalSize;
2391         lz4sd->prefixEnd = (BYTE*)dest + originalSize;
2392     } else if (lz4sd->prefixEnd == (BYTE*)dest) {
2393         if (lz4sd->prefixSize >= 64 KB - 1 || lz4sd->extDictSize == 0)
2394             result = LZ4_decompress_fast(source, dest, originalSize);
2395         else
2396             result = LZ4_decompress_fast_doubleDict(source, dest, originalSize,
2397                                                     lz4sd->prefixSize, lz4sd->externalDict, lz4sd->extDictSize);
2398         if (result <= 0) return result;
2399         lz4sd->prefixSize += (size_t)originalSize;
2400         lz4sd->prefixEnd  += originalSize;
2401     } else {
2402         lz4sd->extDictSize = lz4sd->prefixSize;
2403         lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize;
2404         result = LZ4_decompress_fast_extDict(source, dest, originalSize,
2405                                              lz4sd->externalDict, lz4sd->extDictSize);
2406         if (result <= 0) return result;
2407         lz4sd->prefixSize = (size_t)originalSize;
2408         lz4sd->prefixEnd  = (BYTE*)dest + originalSize;
2409     }
2410
2411     return result;
2412 }
2413
2414
2415 /*
2416 Advanced decoding functions :
2417 *_usingDict() :
2418     These decoding functions work the same as "_continue" ones,
2419     the dictionary must be explicitly provided within parameters
2420 */
2421
2422 int LZ4_decompress_safe_usingDict(const char* source, char* dest, int compressedSize, int maxOutputSize, const char* dictStart, int dictSize)
2423 {
2424     if (dictSize==0)
2425         return LZ4_decompress_safe(source, dest, compressedSize, maxOutputSize);
2426     if (dictStart+dictSize == dest) {
2427         if (dictSize >= 64 KB - 1) {
2428             return LZ4_decompress_safe_withPrefix64k(source, dest, compressedSize, maxOutputSize);
2429         }
2430         assert(dictSize >= 0);
2431         return LZ4_decompress_safe_withSmallPrefix(source, dest, compressedSize, maxOutputSize, (size_t)dictSize);
2432     }
2433     assert(dictSize >= 0);
2434     return LZ4_decompress_safe_forceExtDict(source, dest, compressedSize, maxOutputSize, dictStart, (size_t)dictSize);
2435 }
2436
2437 int LZ4_decompress_fast_usingDict(const char* source, char* dest, int originalSize, const char* dictStart, int dictSize)
2438 {
2439     if (dictSize==0 || dictStart+dictSize == dest)
2440         return LZ4_decompress_fast(source, dest, originalSize);
2441     assert(dictSize >= 0);
2442     return LZ4_decompress_fast_extDict(source, dest, originalSize, dictStart, (size_t)dictSize);
2443 }
2444
2445
2446 /*=*************************************************
2447 *  Obsolete Functions
2448 ***************************************************/
2449 /* obsolete compression functions */
2450 int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize)
2451 {
2452     return LZ4_compress_default(source, dest, inputSize, maxOutputSize);
2453 }
2454 int LZ4_compress(const char* src, char* dest, int srcSize)
2455 {
2456     return LZ4_compress_default(src, dest, srcSize, LZ4_compressBound(srcSize));
2457 }
2458 int LZ4_compress_limitedOutput_withState (void* state, const char* src, char* dst, int srcSize, int dstSize)
2459 {
2460     return LZ4_compress_fast_extState(state, src, dst, srcSize, dstSize, 1);
2461 }
2462 int LZ4_compress_withState (void* state, const char* src, char* dst, int srcSize)
2463 {
2464     return LZ4_compress_fast_extState(state, src, dst, srcSize, LZ4_compressBound(srcSize), 1);
2465 }
2466 int LZ4_compress_limitedOutput_continue (LZ4_stream_t* LZ4_stream, const char* src, char* dst, int srcSize, int dstCapacity)
2467 {
2468     return LZ4_compress_fast_continue(LZ4_stream, src, dst, srcSize, dstCapacity, 1);
2469 }
2470 int LZ4_compress_continue (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize)
2471 {
2472     return LZ4_compress_fast_continue(LZ4_stream, source, dest, inputSize, LZ4_compressBound(inputSize), 1);
2473 }
2474
2475 /*
2476 These decompression functions are deprecated and should no longer be used.
2477 They are only provided here for compatibility with older user programs.
2478 - LZ4_uncompress is totally equivalent to LZ4_decompress_fast
2479 - LZ4_uncompress_unknownOutputSize is totally equivalent to LZ4_decompress_safe
2480 */
2481 int LZ4_uncompress (const char* source, char* dest, int outputSize)
2482 {
2483     return LZ4_decompress_fast(source, dest, outputSize);
2484 }
2485 int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize)
2486 {
2487     return LZ4_decompress_safe(source, dest, isize, maxOutputSize);
2488 }
2489
2490 /* Obsolete Streaming functions */
2491
2492 int LZ4_sizeofStreamState(void) { return LZ4_STREAMSIZE; }
2493
2494 int LZ4_resetStreamState(void* state, char* inputBuffer)
2495 {
2496     (void)inputBuffer;
2497     LZ4_resetStream((LZ4_stream_t*)state);
2498     return 0;
2499 }
2500
2501 void* LZ4_create (char* inputBuffer)
2502 {
2503     (void)inputBuffer;
2504     return LZ4_createStream();
2505 }
2506
2507 char* LZ4_slideInputBuffer (void* state)
2508 {
2509     /* avoid const char * -> char * conversion warning */
2510     return (char *)(uptrval)((LZ4_stream_t*)state)->internal_donotuse.dictionary;
2511 }
2512
2513 #endif   /* LZ4_COMMONDEFS_ONLY */