mfbt/lz4.c

   1 /*
   2    LZ4 - Fast LZ compression algorithm
   3    Copyright (C) 2011-2014, Yann Collet.
   4    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
   5
   6    Redistribution and use in source and binary forms, with or without
   7    modification, are permitted provided that the following conditions are
   8    met:
   9
  10        * Redistributions of source code must retain the above copyright
  11    notice, this list of conditions and the following disclaimer.
  12        * Redistributions in binary form must reproduce the above
  13    copyright notice, this list of conditions and the following disclaimer
  14    in the documentation and/or other materials provided with the
  15    distribution.
  16
  17    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  20    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  21    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  22    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  23    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  27    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28
  29    You can contact the author at :
  30    - LZ4 source repository : http://code.google.com/p/lz4/
  31    - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c
  32 */
  33
  34 /**************************************
  35    Tuning parameters
  36 **************************************/
  37 /*
  38  * HEAPMODE :
  39  * Select how default compression functions will allocate memory for their hash table,
  40  * in memory stack (0:default, fastest), or in memory heap (1:requires memory allocation (malloc)).
  41  */
  42 #define HEAPMODE 0
  43
  44
  45 /**************************************
  46    CPU Feature Detection
  47 **************************************/
  48 /* 32 or 64 bits ? */
  49 #if (defined(__x86_64__) || defined(_M_X64) || defined(_WIN64) \
  50   || defined(__powerpc64__) || defined(__powerpc64le__) \
  51   || defined(__ppc64__) || defined(__ppc64le__) \
  52   || defined(__PPC64__) || defined(__PPC64LE__) \
  53   || defined(__ia64) || defined(__itanium__) || defined(_M_IA64) \
  54   || (defined(__mips64) && defined(_ABI64)))   /* Detects 64 bits mode */
  55 #  define LZ4_ARCH64 1
  56 #else
  57 #  define LZ4_ARCH64 0
  58 #endif
  59
  60 /*
  61  * Little Endian or Big Endian ?
  62  * Overwrite the #define below if you know your architecture endianess
  63  */
  64 #include <stdlib.h>   /* Apparently required to detect endianess */
  65 #if defined (__GLIBC__)
  66 #  include <endian.h>
  67 #  if (__BYTE_ORDER == __BIG_ENDIAN)
  68 #     define LZ4_BIG_ENDIAN 1
  69 #  endif
  70 #elif (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN)) && !(defined(__LITTLE_ENDIAN__) || defined(__LITTLE_ENDIAN) || defined(_LITTLE_ENDIAN))
  71 #  define LZ4_BIG_ENDIAN 1
  72 #elif defined(__sparc) || defined(__sparc__) \
  73    || defined(__powerpc__) || defined(__ppc__) || defined(__PPC__) \
  74    || defined(__hpux)  || defined(__hppa) \
  75    || defined(_MIPSEB) || defined(__s390__)
  76 #  define LZ4_BIG_ENDIAN 1
  77 #else
  78 /* Little Endian assumed. PDP Endian and other very rare endian format are unsupported. */
  79 #endif
  80
  81 /*
  82  * Unaligned memory access is automatically enabled for "common" CPU, such as x86.
  83  * For others CPU, such as ARM, the compiler may be more cautious, inserting unnecessary extra code to ensure aligned access property
  84  * If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance
  85  */
  86 #if defined(__ARM_FEATURE_UNALIGNED)
  87 #  define LZ4_FORCE_UNALIGNED_ACCESS 1
  88 #endif
  89
  90 /* Define this parameter if your target system or compiler does not support hardware bit count */
  91 #if defined(_MSC_VER) && defined(_WIN32_WCE)   /* Visual Studio for Windows CE does not support Hardware bit count */
  92 #  define LZ4_FORCE_SW_BITCOUNT
  93 #endif
  94
  95 /*
  96  * BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE :
  97  * This option may provide a small boost to performance for some big endian cpu, although probably modest.
  98  * You may set this option to 1 if data will remain within closed environment.
  99  * This option is useless on Little_Endian CPU (such as x86)
 100  */
 101
 102 /* #define BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE 1 */
 103
 104
 105 /**************************************
 106  Compiler Options
 107 **************************************/
 108 #if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)   /* C99 */
 109 /* "restrict" is a known keyword */
 110 #else
 111 #  define restrict /* Disable restrict */
 112 #endif
 113
 114 #ifdef _MSC_VER    /* Visual Studio */
 115 #  define FORCE_INLINE static __forceinline
 116 #  include <intrin.h>                    /* For Visual 2005 */
 117 #  if LZ4_ARCH64   /* 64-bits */
 118 #    pragma intrinsic(_BitScanForward64) /* For Visual 2005 */
 119 #    pragma intrinsic(_BitScanReverse64) /* For Visual 2005 */
 120 #  else            /* 32-bits */
 121 #    pragma intrinsic(_BitScanForward)   /* For Visual 2005 */
 122 #    pragma intrinsic(_BitScanReverse)   /* For Visual 2005 */
 123 #  endif
 124 #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
 125 #else
 126 #  ifdef __GNUC__
 127 #    define FORCE_INLINE static inline __attribute__((always_inline))
 128 #  else
 129 #    define FORCE_INLINE static inline
 130 #  endif
 131 #endif
 132
 133 #ifdef _MSC_VER  /* Visual Studio */
 134 #  define lz4_bswap16(x) _byteswap_ushort(x)
 135 #else
 136 #  define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8)))
 137 #endif
 138
 139 #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
 140
 141 #if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__)
 142 #  define expect(expr,value)    (__builtin_expect ((expr),(value)) )
 143 #else
 144 #  define expect(expr,value)    (expr)
 145 #endif
 146
 147 #define likely(expr)     expect((expr) != 0, 1)
 148 #define unlikely(expr)   expect((expr) != 0, 0)
 149
 150
 151 /**************************************
 152    Memory routines
 153 **************************************/
 154 #include <stdlib.h>   /* malloc, calloc, free */
 155 #define ALLOCATOR(n,s) calloc(n,s)
 156 #define FREEMEM        free
 157 #include <string.h>   /* memset, memcpy */
 158 #define MEM_INIT       memset
 159
 160
 161 /**************************************
 162    Includes
 163 **************************************/
 164 #include "lz4.h"
 165
 166
 167 /**************************************
 168    Basic Types
 169 **************************************/
 170 #if defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)   /* C99 */
 171 # include <stdint.h>
 172   typedef  uint8_t BYTE;
 173   typedef uint16_t U16;
 174   typedef uint32_t U32;
 175   typedef  int32_t S32;
 176   typedef uint64_t U64;
 177 #else
 178   typedef unsigned char       BYTE;
 179   typedef unsigned short      U16;
 180   typedef unsigned int        U32;
 181   typedef   signed int        S32;
 182   typedef unsigned long long  U64;
 183 #endif
 184
 185 #if defined(__GNUC__)  && !defined(LZ4_FORCE_UNALIGNED_ACCESS)
 186 #  define _PACKED __attribute__ ((packed))
 187 #else
 188 #  define _PACKED
 189 #endif
 190
 191 #if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__)
 192 #  if defined(__IBMC__) || defined(__SUNPRO_C) || defined(__SUNPRO_CC)
 193 #    pragma pack(1)
 194 #  else
 195 #    pragma pack(push, 1)
 196 #  endif
 197 #endif
 198
 199 typedef struct { U16 v; }  _PACKED U16_S;
 200 typedef struct { U32 v; }  _PACKED U32_S;
 201 typedef struct { U64 v; }  _PACKED U64_S;
 202 typedef struct {size_t v;} _PACKED size_t_S;
 203
 204 #if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__)
 205 #  if defined(__SUNPRO_C) || defined(__SUNPRO_CC)
 206 #    pragma pack(0)
 207 #  else
 208 #    pragma pack(pop)
 209 #  endif
 210 #endif
 211
 212 #define A16(x)   (((U16_S *)(x))->v)
 213 #define A32(x)   (((U32_S *)(x))->v)
 214 #define A64(x)   (((U64_S *)(x))->v)
 215 #define AARCH(x) (((size_t_S *)(x))->v)
 216
 217
 218 /**************************************
 219    Constants
 220 **************************************/
 221 #define LZ4_HASHLOG   (LZ4_MEMORY_USAGE-2)
 222 #define HASHTABLESIZE (1 << LZ4_MEMORY_USAGE)
 223 #define HASH_SIZE_U32 (1 << LZ4_HASHLOG)
 224
 225 #define MINMATCH 4
 226
 227 #define COPYLENGTH 8
 228 #define LASTLITERALS 5
 229 #define MFLIMIT (COPYLENGTH+MINMATCH)
 230 static const int LZ4_minLength = (MFLIMIT+1);
 231
 232 #define KB *(1U<<10)
 233 #define MB *(1U<<20)
 234 #define GB *(1U<<30)
 235
 236 #define LZ4_64KLIMIT ((64 KB) + (MFLIMIT-1))
 237 #define SKIPSTRENGTH 6   /* Increasing this value will make the compression run slower on incompressible data */
 238
 239 #define MAXD_LOG 16
 240 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
 241
 242 #define ML_BITS  4
 243 #define ML_MASK  ((1U<<ML_BITS)-1)
 244 #define RUN_BITS (8-ML_BITS)
 245 #define RUN_MASK ((1U<<RUN_BITS)-1)
 246
 247
 248 /**************************************
 249    Structures and local types
 250 **************************************/
 251 typedef struct {
 252     U32  hashTable[HASH_SIZE_U32];
 253     U32  currentOffset;
 254     U32  initCheck;
 255     const BYTE* dictionary;
 256     const BYTE* bufferStart;
 257     U32  dictSize;
 258 } LZ4_stream_t_internal;
 259
 260 typedef enum { notLimited = 0, limitedOutput = 1 } limitedOutput_directive;
 261 typedef enum { byPtr, byU32, byU16 } tableType_t;
 262
 263 typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive;
 264 typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive;
 265
 266 typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;
 267 typedef enum { full = 0, partial = 1 } earlyEnd_directive;
 268
 269
 270 /**************************************
 271    Architecture-specific macros
 272 **************************************/
 273 #define STEPSIZE                  sizeof(size_t)
 274 #define LZ4_COPYSTEP(d,s)         { AARCH(d) = AARCH(s); d+=STEPSIZE; s+=STEPSIZE; }
 275 #define LZ4_COPY8(d,s)            { LZ4_COPYSTEP(d,s); if (STEPSIZE<8) LZ4_COPYSTEP(d,s); }
 276
 277 #if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE))
 278 #  define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; }
 279 #  define LZ4_WRITE_LITTLEENDIAN_16(p,i)  { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p+=2; }
 280 #else      /* Little Endian */
 281 #  define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); }
 282 #  define LZ4_WRITE_LITTLEENDIAN_16(p,v)  { A16(p) = v; p+=2; }
 283 #endif
 284
 285
 286 /**************************************
 287    Macros
 288 **************************************/
 289 #define LZ4_STATIC_ASSERT(c)    { enum { LZ4_static_assert = 1/(!!(c)) }; }   /* use only *after* variable declarations */
 290 #if LZ4_ARCH64 || !defined(__GNUC__)
 291 #  define LZ4_WILDCOPY(d,s,e)   { do { LZ4_COPY8(d,s) } while (d<e); }        /* at the end, d>=e; */
 292 #else
 293 #  define LZ4_WILDCOPY(d,s,e)   { if (likely(e-d <= 8)) LZ4_COPY8(d,s) else do { LZ4_COPY8(d,s) } while (d<e); }
 294 #endif
 295
 296
 297 /****************************
 298    Private local functions
 299 ****************************/
 300 #if LZ4_ARCH64
 301
 302 int LZ4_NbCommonBytes (register U64 val)
 303 {
 304 # if defined(LZ4_BIG_ENDIAN)
 305 #   if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
 306     unsigned long r = 0;
 307     _BitScanReverse64( &r, val );
 308     return (int)(r>>3);
 309 #   elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
 310     return (__builtin_clzll(val) >> 3);
 311 #   else
 312     int r;
 313     if (!(val>>32)) { r=4; } else { r=0; val>>=32; }
 314     if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
 315     r += (!val);
 316     return r;
 317 #   endif
 318 # else
 319 #   if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
 320     unsigned long r = 0;
 321     _BitScanForward64( &r, val );
 322     return (int)(r>>3);
 323 #   elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
 324     return (__builtin_ctzll(val) >> 3);
 325 #   else
 326     static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5, 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 4, 5, 7, 2, 6, 5, 7, 6, 7, 7 };
 327     return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
 328 #   endif
 329 # endif
 330 }
 331
 332 #else
 333
 334 int LZ4_NbCommonBytes (register U32 val)
 335 {
 336 # if defined(LZ4_BIG_ENDIAN)
 337 #   if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
 338     unsigned long r = 0;
 339     _BitScanReverse( &r, val );
 340     return (int)(r>>3);
 341 #   elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
 342     return (__builtin_clz(val) >> 3);
 343 #   else
 344     int r;
 345     if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
 346     r += (!val);
 347     return r;
 348 #   endif
 349 # else
 350 #   if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
 351     unsigned long r;
 352     _BitScanForward( &r, val );
 353     return (int)(r>>3);
 354 #   elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
 355     return (__builtin_ctz(val) >> 3);
 356 #   else
 357     static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 };
 358     return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
 359 #   endif
 360 # endif
 361 }
 362
 363 #endif
 364
 365
 366 /********************************
 367    Compression functions
 368 ********************************/
 369 int LZ4_compressBound(int isize)  { return LZ4_COMPRESSBOUND(isize); }
 370
 371 static int LZ4_hashSequence(U32 sequence, tableType_t tableType)
 372 {
 373     if (tableType == byU16)
 374         return (((sequence) * 2654435761U) >> ((MINMATCH*8)-(LZ4_HASHLOG+1)));
 375     else
 376         return (((sequence) * 2654435761U) >> ((MINMATCH*8)-LZ4_HASHLOG));
 377 }
 378
 379 static int LZ4_hashPosition(const BYTE* p, tableType_t tableType) { return LZ4_hashSequence(A32(p), tableType); }
 380
 381 static void LZ4_putPositionOnHash(const BYTE* p, U32 h, void* tableBase, tableType_t tableType, const BYTE* srcBase)
 382 {
 383     switch (tableType)
 384     {
 385     case byPtr: { const BYTE** hashTable = (const BYTE**) tableBase; hashTable[h] = p; break; }
 386     case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = (U32)(p-srcBase); break; }
 387     case byU16: { U16* hashTable = (U16*) tableBase; hashTable[h] = (U16)(p-srcBase); break; }
 388     }
 389 }
 390
 391 static void LZ4_putPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase)
 392 {
 393     U32 h = LZ4_hashPosition(p, tableType);
 394     LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase);
 395 }
 396
 397 static const BYTE* LZ4_getPositionOnHash(U32 h, void* tableBase, tableType_t tableType, const BYTE* srcBase)
 398 {
 399     if (tableType == byPtr) { const BYTE** hashTable = (const BYTE**) tableBase; return hashTable[h]; }
 400     if (tableType == byU32) { U32* hashTable = (U32*) tableBase; return hashTable[h] + srcBase; }
 401     { U16* hashTable = (U16*) tableBase; return hashTable[h] + srcBase; }   /* default, to ensure a return */
 402 }
 403
 404 static const BYTE* LZ4_getPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase)
 405 {
 406     U32 h = LZ4_hashPosition(p, tableType);
 407     return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase);
 408 }
 409
 410 static unsigned LZ4_count(const BYTE* pIn, const BYTE* pRef, const BYTE* pInLimit)
 411 {
 412     const BYTE* const pStart = pIn;
 413
 414     while (likely(pIn<pInLimit-(STEPSIZE-1)))
 415     {
 416         size_t diff = AARCH(pRef) ^ AARCH(pIn);
 417         if (!diff) { pIn+=STEPSIZE; pRef+=STEPSIZE; continue; }
 418         pIn += LZ4_NbCommonBytes(diff);
 419         return (unsigned)(pIn - pStart);
 420     }
 421     if (sizeof(void*)==8) if ((pIn<(pInLimit-3)) && (A32(pRef) == A32(pIn))) { pIn+=4; pRef+=4; }
 422     if ((pIn<(pInLimit-1)) && (A16(pRef) == A16(pIn))) { pIn+=2; pRef+=2; }
 423     if ((pIn<pInLimit) && (*pRef == *pIn)) pIn++;
 424
 425     return (unsigned)(pIn - pStart);
 426 }
 427
 428
 429 static int LZ4_compress_generic(
 430                  void* ctx,
 431                  const char* source,
 432                  char* dest,
 433                  int inputSize,
 434                  int maxOutputSize,
 435
 436                  limitedOutput_directive outputLimited,
 437                  tableType_t tableType,
 438                  dict_directive dict,
 439                  dictIssue_directive dictIssue)
 440 {
 441     LZ4_stream_t_internal* const dictPtr = (LZ4_stream_t_internal*)ctx;
 442
 443     const BYTE* ip = (const BYTE*) source;
 444     const BYTE* base;
 445     const BYTE* lowLimit;
 446     const BYTE* const lowRefLimit = ip - dictPtr->dictSize;
 447     const BYTE* const dictionary = dictPtr->dictionary;
 448     const BYTE* const dictEnd = dictionary + dictPtr->dictSize;
 449     const size_t dictDelta = dictEnd - (const BYTE*)source;
 450     const BYTE* anchor = (const BYTE*) source;
 451     const BYTE* const iend = ip + inputSize;
 452     const BYTE* const mflimit = iend - MFLIMIT;
 453     const BYTE* const matchlimit = iend - LASTLITERALS;
 454
 455     BYTE* op = (BYTE*) dest;
 456     BYTE* const olimit = op + maxOutputSize;
 457
 458     const int skipStrength = SKIPSTRENGTH;
 459     U32 forwardH;
 460     size_t refDelta=0;
 461
 462     /* Init conditions */
 463     if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0;          /* Unsupported input size, too large (or negative) */
 464     switch(dict)
 465     {
 466     case noDict:
 467     default:
 468         base = (const BYTE*)source;
 469         lowLimit = (const BYTE*)source;
 470         break;
 471     case withPrefix64k:
 472         base = (const BYTE*)source - dictPtr->currentOffset;
 473         lowLimit = (const BYTE*)source - dictPtr->dictSize;
 474         break;
 475     case usingExtDict:
 476         base = (const BYTE*)source - dictPtr->currentOffset;
 477         lowLimit = (const BYTE*)source;
 478         break;
 479     }
 480     if ((tableType == byU16) && (inputSize>=(int)LZ4_64KLIMIT)) return 0;   /* Size too large (not within 64K limit) */
 481     if (inputSize<LZ4_minLength) goto _last_literals;                       /* Input too small, no compression (all literals) */
 482
 483     /* First Byte */
 484     LZ4_putPosition(ip, ctx, tableType, base);
 485     ip++; forwardH = LZ4_hashPosition(ip, tableType);
 486
 487     /* Main Loop */
 488     for ( ; ; )
 489     {
 490         const BYTE* ref;
 491         BYTE* token;
 492         {
 493             const BYTE* forwardIp = ip;
 494             unsigned step=1;
 495             unsigned searchMatchNb = (1U << skipStrength);
 496
 497             /* Find a match */
 498             do {
 499                 U32 h = forwardH;
 500                 ip = forwardIp;
 501                 forwardIp += step;
 502                 step = searchMatchNb++ >> skipStrength;
 503                 //if (step>8) step=8;   // required for valid forwardIp ; slows down uncompressible data a bit
 504
 505                 if (unlikely(forwardIp > mflimit)) goto _last_literals;
 506
 507                 ref = LZ4_getPositionOnHash(h, ctx, tableType, base);
 508                 if (dict==usingExtDict)
 509                 {
 510                     if (ref<(const BYTE*)source)
 511                     {
 512                         refDelta = dictDelta;
 513                         lowLimit = dictionary;
 514                     }
 515                     else
 516                     {
 517                         refDelta = 0;
 518                         lowLimit = (const BYTE*)source;
 519                     }
 520                 }
 521                 forwardH = LZ4_hashPosition(forwardIp, tableType);
 522                 LZ4_putPositionOnHash(ip, h, ctx, tableType, base);
 523
 524             } while ( ((dictIssue==dictSmall) ? (ref < lowRefLimit) : 0)
 525                 || ((tableType==byU16) ? 0 : (ref + MAX_DISTANCE < ip))
 526                 || (A32(ref+refDelta) != A32(ip)) );
 527         }
 528
 529         /* Catch up */
 530         while ((ip>anchor) && (ref+refDelta > lowLimit) && (unlikely(ip[-1]==ref[refDelta-1]))) { ip--; ref--; }
 531
 532         {
 533             /* Encode Literal length */
 534             unsigned litLength = (unsigned)(ip - anchor);
 535             token = op++;
 536             if ((outputLimited) && (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > olimit)))
 537                 return 0;   /* Check output limit */
 538             if (litLength>=RUN_MASK)
 539             {
 540                 int len = (int)litLength-RUN_MASK;
 541                 *token=(RUN_MASK<<ML_BITS);
 542                 for(; len >= 255 ; len-=255) *op++ = 255;
 543                 *op++ = (BYTE)len;
 544             }
 545             else *token = (BYTE)(litLength<<ML_BITS);
 546
 547             /* Copy Literals */
 548             { BYTE* end = op+litLength; LZ4_WILDCOPY(op,anchor,end); op=end; }
 549         }
 550
 551 _next_match:
 552         /* Encode Offset */
 553         LZ4_WRITE_LITTLEENDIAN_16(op, (U16)(ip-ref));
 554
 555         /* Encode MatchLength */
 556         {
 557             unsigned matchLength;
 558
 559             if ((dict==usingExtDict) && (lowLimit==dictionary))
 560             {
 561                 const BYTE* limit;
 562                 ref += refDelta;
 563                 limit = ip + (dictEnd-ref);
 564                 if (limit > matchlimit) limit = matchlimit;
 565                 matchLength = LZ4_count(ip+MINMATCH, ref+MINMATCH, limit);
 566                 ip += MINMATCH + matchLength;
 567                 if (ip==limit)
 568                 {
 569                     unsigned more = LZ4_count(ip, (const BYTE*)source, matchlimit);
 570                     matchLength += more;
 571                     ip += more;
 572                 }
 573             }
 574             else
 575             {
 576                 matchLength = LZ4_count(ip+MINMATCH, ref+MINMATCH, matchlimit);
 577                 ip += MINMATCH + matchLength;
 578             }
 579
 580             if (matchLength>=ML_MASK)
 581             {
 582                 if ((outputLimited) && (unlikely(op + (1 + LASTLITERALS) + (matchLength>>8) > olimit)))
 583                     return 0;    /* Check output limit */
 584                 *token += ML_MASK;
 585                 matchLength -= ML_MASK;
 586                 for (; matchLength >= 510 ; matchLength-=510) { *op++ = 255; *op++ = 255; }
 587                 if (matchLength >= 255) { matchLength-=255; *op++ = 255; }
 588                 *op++ = (BYTE)matchLength;
 589             }
 590             else *token += (BYTE)(matchLength);
 591         }
 592
 593         anchor = ip;
 594
 595         /* Test end of chunk */
 596         if (ip > mflimit) break;
 597
 598         /* Fill table */
 599         LZ4_putPosition(ip-2, ctx, tableType, base);
 600
 601         /* Test next position */
 602         ref = LZ4_getPosition(ip, ctx, tableType, base);
 603         if (dict==usingExtDict)
 604         {
 605             if (ref<(const BYTE*)source)
 606             {
 607                 refDelta = dictDelta;
 608                 lowLimit = dictionary;
 609             }
 610             else
 611             {
 612                 refDelta = 0;
 613                 lowLimit = (const BYTE*)source;
 614             }
 615         }
 616         LZ4_putPosition(ip, ctx, tableType, base);
 617         if ( ((dictIssue==dictSmall) ? (ref>=lowRefLimit) : 1)
 618             && (ref+MAX_DISTANCE>=ip)
 619             && (A32(ref+refDelta)==A32(ip)) )
 620         { token=op++; *token=0; goto _next_match; }
 621
 622         /* Prepare next loop */
 623         forwardH = LZ4_hashPosition(++ip, tableType);
 624     }
 625
 626 _last_literals:
 627     /* Encode Last Literals */
 628     {
 629         int lastRun = (int)(iend - anchor);
 630         if ((outputLimited) && (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize))
 631             return 0;   /* Check output limit */
 632         if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun >= 255 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }
 633         else *op++ = (BYTE)(lastRun<<ML_BITS);
 634         memcpy(op, anchor, iend - anchor);
 635         op += iend-anchor;
 636     }
 637
 638     /* End */
 639     return (int) (((char*)op)-dest);
 640 }
 641
 642
 643 int LZ4_compress(const char* source, char* dest, int inputSize)
 644 {
 645 #if (HEAPMODE)
 646     void* ctx = ALLOCATOR(LZ4_STREAMSIZE_U32, 4);   /* Aligned on 4-bytes boundaries */
 647 #else
 648     U32 ctx[LZ4_STREAMSIZE_U32] = {0};      /* Ensure data is aligned on 4-bytes boundaries */
 649 #endif
 650     int result;
 651
 652     if (inputSize < (int)LZ4_64KLIMIT)
 653         result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, 0, notLimited, byU16, noDict, noDictIssue);
 654     else
 655         result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, 0, notLimited, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue);
 656
 657 #if (HEAPMODE)
 658     FREEMEM(ctx);
 659 #endif
 660     return result;
 661 }
 662
 663 int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize)
 664 {
 665 #if (HEAPMODE)
 666     void* ctx = ALLOCATOR(LZ4_STREAMSIZE_U32, 4);   /* Aligned on 4-bytes boundaries */
 667 #else
 668     U32 ctx[LZ4_STREAMSIZE_U32] = {0};      /* Ensure data is aligned on 4-bytes boundaries */
 669 #endif
 670     int result;
 671
 672     if (inputSize < (int)LZ4_64KLIMIT)
 673         result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue);
 674     else
 675         result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, maxOutputSize, limitedOutput, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue);
 676
 677 #if (HEAPMODE)
 678     FREEMEM(ctx);
 679 #endif
 680     return result;
 681 }
 682
 683
 684 /*****************************************
 685    Experimental : Streaming functions
 686 *****************************************/
 687
 688 void* LZ4_createStream()
 689 {
 690     void* lz4s = ALLOCATOR(4, LZ4_STREAMSIZE_U32);
 691     MEM_INIT(lz4s, 0, LZ4_STREAMSIZE);
 692     return lz4s;
 693 }
 694
 695 int LZ4_free (void* LZ4_stream)
 696 {
 697     FREEMEM(LZ4_stream);
 698     return (0);
 699 }
 700
 701
 702 int LZ4_loadDict (void* LZ4_dict, const char* dictionary, int dictSize)
 703 {
 704     LZ4_stream_t_internal* dict = (LZ4_stream_t_internal*) LZ4_dict;
 705     const BYTE* p = (const BYTE*)dictionary;
 706     const BYTE* const dictEnd = p + dictSize;
 707     const BYTE* base;
 708
 709     LZ4_STATIC_ASSERT(LZ4_STREAMSIZE >= sizeof(LZ4_stream_t_internal));      /* A compilation error here means LZ4_STREAMSIZE is not large enough */
 710     if (dict->initCheck) MEM_INIT(dict, 0, sizeof(LZ4_stream_t_internal));   /* Uninitialized structure detected */
 711
 712     if (dictSize < MINMATCH)
 713     {
 714         dict->dictionary = NULL;
 715         dict->dictSize = 0;
 716         return 1;
 717     }
 718
 719     if (p <= dictEnd - 64 KB) p = dictEnd - 64 KB;
 720     base = p - dict->currentOffset;
 721     dict->dictionary = p;
 722     dict->dictSize = (U32)(dictEnd - p);
 723     dict->currentOffset += dict->dictSize;
 724
 725     while (p <= dictEnd-MINMATCH)
 726     {
 727         LZ4_putPosition(p, dict, byU32, base);
 728         p+=3;
 729     }
 730
 731     return 1;
 732 }
 733
 734
 735 void LZ4_renormDictT(LZ4_stream_t_internal* LZ4_dict, const BYTE* src)
 736 {
 737     if ((LZ4_dict->currentOffset > 0x80000000) ||
 738         ((size_t)LZ4_dict->currentOffset > (size_t)src))   /* address space overflow */
 739     {
 740         /* rescale hash table */
 741         U32 delta = LZ4_dict->currentOffset - 64 KB;
 742         const BYTE* dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize;
 743         int i;
 744         for (i=0; i<HASH_SIZE_U32; i++)
 745         {
 746             if (LZ4_dict->hashTable[i] < delta) LZ4_dict->hashTable[i]=0;
 747             else LZ4_dict->hashTable[i] -= delta;
 748         }
 749         LZ4_dict->currentOffset = 64 KB;
 750         if (LZ4_dict->dictSize > 64 KB) LZ4_dict->dictSize = 64 KB;
 751         LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize;
 752     }
 753 }
 754
 755
 756 FORCE_INLINE int LZ4_compress_continue_generic (void* LZ4_stream, const char* source, char* dest, int inputSize,
 757                                                 int maxOutputSize, limitedOutput_directive limit)
 758 {
 759     LZ4_stream_t_internal* streamPtr = (LZ4_stream_t_internal*)LZ4_stream;
 760     const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize;
 761
 762     const BYTE* smallest = (const BYTE*) source;
 763     if (streamPtr->initCheck) return 0;   /* Uninitialized structure detected */
 764     if ((streamPtr->dictSize>0) && (smallest>dictEnd)) smallest = dictEnd;
 765     LZ4_renormDictT(streamPtr, smallest);
 766
 767     /* Check overlapping input/dictionary space */
 768     {
 769         const BYTE* sourceEnd = (const BYTE*) source + inputSize;
 770         if ((sourceEnd > streamPtr->dictionary) && (sourceEnd < dictEnd))
 771         {
 772             streamPtr->dictSize = (U32)(dictEnd - sourceEnd);
 773             if (streamPtr->dictSize > 64 KB) streamPtr->dictSize = 64 KB;
 774             if (streamPtr->dictSize < 4) streamPtr->dictSize = 0;
 775             streamPtr->dictionary = dictEnd - streamPtr->dictSize;
 776         }
 777     }
 778
 779     /* prefix mode : source data follows dictionary */
 780     if (dictEnd == (const BYTE*)source)
 781     {
 782         int result;
 783         if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset))
 784             result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, withPrefix64k, dictSmall);
 785         else
 786             result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, withPrefix64k, noDictIssue);
 787         streamPtr->dictSize += (U32)inputSize;
 788         streamPtr->currentOffset += (U32)inputSize;
 789         return result;
 790     }
 791
 792     /* external dictionary mode */
 793     {
 794         int result;
 795         if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset))
 796             result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, usingExtDict, dictSmall);
 797         else
 798             result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, usingExtDict, noDictIssue);
 799         streamPtr->dictionary = (const BYTE*)source;
 800         streamPtr->dictSize = (U32)inputSize;
 801         streamPtr->currentOffset += (U32)inputSize;
 802         return result;
 803     }
 804 }
 805
 806
 807 int LZ4_compress_continue (void* LZ4_stream, const char* source, char* dest, int inputSize)
 808 {
 809     return LZ4_compress_continue_generic(LZ4_stream, source, dest, inputSize, 0, notLimited);
 810 }
 811
 812 int LZ4_compress_limitedOutput_continue (void* LZ4_stream, const char* source, char* dest, int inputSize, int maxOutputSize)
 813 {
 814     return LZ4_compress_continue_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limitedOutput);
 815 }
 816
 817
 818 // Hidden debug function, to force separate dictionary mode
 819 int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int inputSize)
 820 {
 821     LZ4_stream_t_internal* streamPtr = (LZ4_stream_t_internal*)LZ4_dict;
 822     int result;
 823     const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize;
 824
 825     const BYTE* smallest = dictEnd;
 826     if (smallest > (const BYTE*) source) smallest = (const BYTE*) source;
 827     LZ4_renormDictT((LZ4_stream_t_internal*)LZ4_dict, smallest);
 828
 829     result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, usingExtDict, noDictIssue);
 830
 831     streamPtr->dictionary = (const BYTE*)source;
 832     streamPtr->dictSize = (U32)inputSize;
 833     streamPtr->currentOffset += (U32)inputSize;
 834
 835     return result;
 836 }
 837
 838
 839 int LZ4_saveDict (void* LZ4_dict, char* safeBuffer, int dictSize)
 840 {
 841     LZ4_stream_t_internal* dict = (LZ4_stream_t_internal*) LZ4_dict;
 842     const BYTE* previousDictEnd = dict->dictionary + dict->dictSize;
 843
 844     if ((U32)dictSize > 64 KB) dictSize = 64 KB;   /* useless to define a dictionary > 64 KB */
 845     if ((U32)dictSize > dict->dictSize) dictSize = dict->dictSize;
 846
 847     memcpy(safeBuffer, previousDictEnd - dictSize, dictSize);
 848
 849     dict->dictionary = (const BYTE*)safeBuffer;
 850     dict->dictSize = (U32)dictSize;
 851
 852     return 1;
 853 }
 854
 855
 856
 857 /****************************
 858    Decompression functions
 859 ****************************/
 860 /*
 861  * This generic decompression function cover all use cases.
 862  * It shall be instanciated several times, using different sets of directives
 863  * Note that it is essential this generic function is really inlined,
 864  * in order to remove useless branches during compilation optimisation.
 865  */
 866 FORCE_INLINE int LZ4_decompress_generic(
 867                  const char* source,
 868                  char* dest,
 869                  int inputSize,
 870                  int outputSize,         /* If endOnInput==endOnInputSize, this value is the max size of Output Buffer. */
 871
 872                  int endOnInput,         /* endOnOutputSize, endOnInputSize */
 873                  int partialDecoding,    /* full, partial */
 874                  int targetOutputSize,   /* only used if partialDecoding==partial */
 875                  int dict,               /* noDict, withPrefix64k, usingExtDict */
 876                  const char* dictStart,  /* only if dict==usingExtDict */
 877                  int dictSize            /* note : = 0 if noDict */
 878                  )
 879 {
 880     /* Local Variables */
 881     const BYTE* restrict ip = (const BYTE*) source;
 882     const BYTE* ref;
 883     const BYTE* const iend = ip + inputSize;
 884
 885     BYTE* op = (BYTE*) dest;
 886     BYTE* const oend = op + outputSize;
 887     BYTE* cpy;
 888     BYTE* oexit = op + targetOutputSize;
 889     const BYTE* const lowLimit = (const BYTE*)dest - dictSize;
 890
 891     const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize;
 892 //#define OLD
 893 #ifdef OLD
 894     const size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};   /* static reduces speed for LZ4_decompress_safe() on GCC64 */
 895 #else
 896     const size_t dec32table[] = {4-0, 4-3, 4-2, 4-3, 4-0, 4-0, 4-0, 4-0};   /* static reduces speed for LZ4_decompress_safe() on GCC64 */
 897 #endif
 898     static const size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};
 899
 900     const int checkOffset = (endOnInput) && (dictSize < (int)(64 KB));
 901
 902
 903     /* Special cases */
 904     if ((partialDecoding) && (oexit> oend-MFLIMIT)) oexit = oend-MFLIMIT;                        /* targetOutputSize too high => decode everything */
 905     if ((endOnInput) && (unlikely(outputSize==0))) return ((inputSize==1) && (*ip==0)) ? 0 : -1;   /* Empty output buffer */
 906     if ((!endOnInput) && (unlikely(outputSize==0))) return (*ip==0?1:-1);
 907
 908
 909     /* Main Loop */
 910     while (1)
 911     {
 912         unsigned token;
 913         size_t length;
 914
 915         /* get runlength */
 916         token = *ip++;
 917         if ((length=(token>>ML_BITS)) == RUN_MASK)
 918         {
 919             unsigned s;
 920             do
 921             {
 922                 s = *ip++;
 923                 length += s;
 924             }
 925             while (likely((endOnInput)?ip<iend-RUN_MASK:1) && (s==255));
 926             //if ((sizeof(void*)==4) && unlikely(length>LZ4_MAX_INPUT_SIZE)) goto _output_error;   /* overflow detection */
 927             if ((sizeof(void*)==4) && unlikely((size_t)(op+length)<(size_t)(op))) goto _output_error;   /* quickfix issue 134 */
 928             if ((endOnInput) && (sizeof(void*)==4) && unlikely((size_t)(ip+length)<(size_t)(ip))) goto _output_error;   /* quickfix issue 134 */
 929         }
 930
 931         /* copy literals */
 932         cpy = op+length;
 933         if (((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT)) || (ip+length>iend-(2+1+LASTLITERALS))) )
 934             || ((!endOnInput) && (cpy>oend-COPYLENGTH)))
 935         {
 936             if (partialDecoding)
 937             {
 938                 if (cpy > oend) goto _output_error;                           /* Error : write attempt beyond end of output buffer */
 939                 if ((endOnInput) && (ip+length > iend)) goto _output_error;   /* Error : read attempt beyond end of input buffer */
 940             }
 941             else
 942             {
 943                 if ((!endOnInput) && (cpy != oend)) goto _output_error;       /* Error : block decoding must stop exactly there */
 944                 if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) goto _output_error;   /* Error : input must be consumed */
 945             }
 946             memcpy(op, ip, length);
 947             ip += length;
 948             op += length;
 949             break;                                       /* Necessarily EOF, due to parsing restrictions */
 950         }
 951         LZ4_WILDCOPY(op, ip, cpy); ip -= (op-cpy); op = cpy;
 952
 953         /* get offset */
 954         LZ4_READ_LITTLEENDIAN_16(ref,cpy,ip); ip+=2;
 955         if ((checkOffset) && (unlikely(ref < lowLimit))) goto _output_error;   /* Error : offset outside destination buffer */
 956
 957         /* get matchlength */
 958         if ((length=(token&ML_MASK)) == ML_MASK)
 959         {
 960             unsigned s;
 961             do
 962             {
 963                 if ((endOnInput) && (ip > iend-LASTLITERALS)) goto _output_error;
 964                 s = *ip++;
 965                 length += s;
 966             } while (s==255);
 967             //if ((sizeof(void*)==4) && unlikely(length>LZ4_MAX_INPUT_SIZE)) goto _output_error;   /* overflow detection */
 968             if ((sizeof(void*)==4) && unlikely((size_t)(op+length)<(size_t)op)) goto _output_error;   /* quickfix issue 134 */
 969         }
 970
 971         /* check external dictionary */
 972         if ((dict==usingExtDict) && (ref < (BYTE* const)dest))
 973         {
 974             if (unlikely(op+length+MINMATCH > oend-LASTLITERALS)) goto _output_error;
 975
 976             if (length+MINMATCH <= (size_t)(dest-(char*)ref))
 977             {
 978                 ref = dictEnd - (dest-(char*)ref);
 979                 memcpy(op, ref, length+MINMATCH);
 980                 op += length+MINMATCH;
 981             }
 982             else
 983             {
 984                 size_t copySize = (size_t)(dest-(char*)ref);
 985                 memcpy(op, dictEnd - copySize, copySize);
 986                 op += copySize;
 987                 copySize = length+MINMATCH - copySize;
 988                 if (copySize > (size_t)((char*)op-dest))   /* overlap */
 989                 {
 990                     BYTE* const cpy = op + copySize;
 991                     const BYTE* ref = (BYTE*)dest;
 992                     while (op < cpy) *op++ = *ref++;
 993                 }
 994                 else
 995                 {
 996                     memcpy(op, dest, copySize);
 997                     op += copySize;
 998                 }
 999             }
1000             continue;
1001         }
1002
1003         /* copy repeated sequence */
1004         if (unlikely((op-ref)<(int)STEPSIZE))
1005         {
1006             const size_t dec64 = dec64table[(sizeof(void*)==4) ? 0 : op-ref];
1007             op[0] = ref[0];
1008             op[1] = ref[1];
1009             op[2] = ref[2];
1010             op[3] = ref[3];
1011 #ifdef OLD
1012             op += 4, ref += 4; ref -= dec32table[op-ref];
1013             A32(op) = A32(ref);
1014             op += STEPSIZE-4; ref -= dec64;
1015 #else
1016             ref += dec32table[op-ref];
1017             A32(op+4) = A32(ref);
1018             op += STEPSIZE; ref -= dec64;
1019 #endif
1020         } else { LZ4_COPYSTEP(op,ref); }
1021         cpy = op + length - (STEPSIZE-4);
1022
1023         if (unlikely(cpy>oend-COPYLENGTH-(STEPSIZE-4)))
1024         {
1025             if (cpy > oend-LASTLITERALS) goto _output_error;    /* Error : last 5 bytes must be literals */
1026             if (op<oend-COPYLENGTH) LZ4_WILDCOPY(op, ref, (oend-COPYLENGTH));
1027             while(op<cpy) *op++=*ref++;
1028             op=cpy;
1029             continue;
1030         }
1031         LZ4_WILDCOPY(op, ref, cpy);
1032         op=cpy;   /* correction */
1033     }
1034
1035     /* end of decoding */
1036     if (endOnInput)
1037        return (int) (((char*)op)-dest);     /* Nb of output bytes decoded */
1038     else
1039        return (int) (((char*)ip)-source);   /* Nb of input bytes read */
1040
1041     /* Overflow error detected */
1042 _output_error:
1043     return (int) (-(((char*)ip)-source))-1;
1044 }
1045
1046
1047 int LZ4_decompress_safe(const char* source, char* dest, int compressedSize, int maxOutputSize)
1048 {
1049     return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, noDict, NULL, 0);
1050 }
1051
1052 int LZ4_decompress_safe_partial(const char* source, char* dest, int compressedSize, int targetOutputSize, int maxOutputSize)
1053 {
1054     return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, partial, targetOutputSize, noDict, NULL, 0);
1055 }
1056
1057 int LZ4_decompress_fast(const char* source, char* dest, int originalSize)
1058 {
1059     return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, withPrefix64k, NULL, 0);
1060 }
1061
1062 /* streaming decompression functions */
1063
1064 //#define LZ4_STREAMDECODESIZE_U32 4
1065 //#define LZ4_STREAMDECODESIZE     (LZ4_STREAMDECODESIZE_U32 * sizeof(unsigned int))
1066 //typedef struct { unsigned int table[LZ4_STREAMDECODESIZE_U32]; } LZ4_streamDecode_t;
1067 typedef struct
1068 {
1069     const char* dictionary;
1070     int dictSize;
1071 } LZ4_streamDecode_t_internal;
1072
1073 /*
1074  * If you prefer dynamic allocation methods,
1075  * LZ4_createStreamDecode()
1076  * provides a pointer (void*) towards an initialized LZ4_streamDecode_t structure.
1077  */
1078 void* LZ4_createStreamDecode()
1079 {
1080     void* lz4s = ALLOCATOR(sizeof(U32), LZ4_STREAMDECODESIZE_U32);
1081     MEM_INIT(lz4s, 0, LZ4_STREAMDECODESIZE);
1082     return lz4s;
1083 }
1084
1085 /*
1086  * LZ4_setDictDecode
1087  * Use this function to instruct where to find the dictionary
1088  * This function is not necessary if previous data is still available where it was decoded.
1089  * Loading a size of 0 is allowed (same effect as no dictionary).
1090  * Return : 1 if OK, 0 if error
1091  */
1092 int LZ4_setDictDecode (void* LZ4_streamDecode, const char* dictionary, int dictSize)
1093 {
1094     LZ4_streamDecode_t_internal* lz4sd = (LZ4_streamDecode_t_internal*) LZ4_streamDecode;
1095     lz4sd->dictionary = dictionary;
1096     lz4sd->dictSize = dictSize;
1097     return 1;
1098 }
1099
1100 /*
1101 *_continue() :
1102     These decoding functions allow decompression of multiple blocks in "streaming" mode.
1103     Previously decoded blocks must still be available at the memory position where they were decoded.
1104     If it's not possible, save the relevant part of decoded data into a safe buffer,
1105     and indicate where it stands using LZ4_setDictDecode()
1106 */
1107 int LZ4_decompress_safe_continue (void* LZ4_streamDecode, const char* source, char* dest, int compressedSize, int maxOutputSize)
1108 {
1109     LZ4_streamDecode_t_internal* lz4sd = (LZ4_streamDecode_t_internal*) LZ4_streamDecode;
1110     int result;
1111
1112     result = LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, usingExtDict, lz4sd->dictionary, lz4sd->dictSize);
1113     if (result <= 0) return result;
1114     if (lz4sd->dictionary + lz4sd->dictSize == dest)
1115     {
1116         lz4sd->dictSize += result;
1117     }
1118     else
1119     {
1120         lz4sd->dictionary = dest;
1121         lz4sd->dictSize = result;
1122     }
1123
1124     return result;
1125 }
1126
1127 int LZ4_decompress_fast_continue (void* LZ4_streamDecode, const char* source, char* dest, int originalSize)
1128 {
1129     LZ4_streamDecode_t_internal* lz4sd = (LZ4_streamDecode_t_internal*) LZ4_streamDecode;
1130     int result;
1131
1132     result = LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, usingExtDict, lz4sd->dictionary, lz4sd->dictSize);
1133     if (result <= 0) return result;
1134     if (lz4sd->dictionary + lz4sd->dictSize == dest)
1135     {
1136         lz4sd->dictSize += result;
1137     }
1138     else
1139     {
1140         lz4sd->dictionary = dest;
1141         lz4sd->dictSize = result;
1142     }
1143
1144     return result;
1145 }
1146
1147
1148 /*
1149 Advanced decoding functions :
1150 *_usingDict() :
1151     These decoding functions work the same as "_continue" ones,
1152     the dictionary must be explicitly provided within parameters
1153 */
1154
1155 int LZ4_decompress_safe_usingDict(const char* source, char* dest, int compressedSize, int maxOutputSize, const char* dictStart, int dictSize)
1156 {
1157     return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, usingExtDict, dictStart, dictSize);
1158 }
1159
1160 int LZ4_decompress_fast_usingDict(const char* source, char* dest, int originalSize, const char* dictStart, int dictSize)
1161 {
1162     return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, usingExtDict, dictStart, dictSize);
1163 }