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