mfbt/lz4.c

   1 /*
   2    LZ4 - Fast LZ compression algorithm
   3    Copyright (C) 2011-2017, Yann Collet.
   4
   5    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
   6
   7    Redistribution and use in source and binary forms, with or without
   8    modification, are permitted provided that the following conditions are
   9    met:
  10
  11        * Redistributions of source code must retain the above copyright
  12    notice, this list of conditions and the following disclaimer.
  13        * Redistributions in binary form must reproduce the above
  14    copyright notice, this list of conditions and the following disclaimer
  15    in the documentation and/or other materials provided with the
  16    distribution.
  17
  18    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29
  30    You can contact the author at :
  31     - LZ4 homepage : http://www.lz4.org
  32     - LZ4 source repository : https://github.com/lz4/lz4
  33 */
  34
  35
  36 /*-************************************
  37 *  Tuning parameters
  38 **************************************/
  39 /*
  40  * LZ4_HEAPMODE :
  41  * Select how default compression functions will allocate memory for their hash table,
  42  * in memory stack (0:default, fastest), or in memory heap (1:requires malloc()).
  43  */
  44 #ifndef LZ4_HEAPMODE
  45 #  define LZ4_HEAPMODE 0
  46 #endif
  47
  48 /*
  49  * ACCELERATION_DEFAULT :
  50  * Select "acceleration" for LZ4_compress_fast() when parameter value <= 0
  51  */
  52 #define ACCELERATION_DEFAULT 1
  53
  54
  55 /*-************************************
  56 *  CPU Feature Detection
  57 **************************************/
  58 /* LZ4_FORCE_MEMORY_ACCESS
  59  * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
  60  * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
  61  * The below switch allow to select different access method for improved performance.
  62  * Method 0 (default) : use `memcpy()`. Safe and portable.
  63  * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
  64  *            This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
  65  * Method 2 : direct access. This method is portable but violate C standard.
  66  *            It can generate buggy code on targets which assembly generation depends on alignment.
  67  *            But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
  68  * See https://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
  69  * Prefer these methods in priority order (0 > 1 > 2)
  70  */
  71 #ifndef LZ4_FORCE_MEMORY_ACCESS   /* can be defined externally */
  72 #  if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) )
  73 #    define LZ4_FORCE_MEMORY_ACCESS 2
  74 #  elif defined(__INTEL_COMPILER) || defined(__GNUC__)
  75 #    define LZ4_FORCE_MEMORY_ACCESS 1
  76 #  endif
  77 #endif
  78
  79 /*
  80  * LZ4_FORCE_SW_BITCOUNT
  81  * Define this parameter if your target system or compiler does not support hardware bit count
  82  */
  83 #if defined(_MSC_VER) && defined(_WIN32_WCE)   /* Visual Studio for Windows CE does not support Hardware bit count */
  84 #  define LZ4_FORCE_SW_BITCOUNT
  85 #endif
  86
  87
  88 /*-************************************
  89 *  Dependency
  90 **************************************/
  91 #include "lz4.h"
  92 /* see also "memory routines" below */
  93
  94
  95 /*-************************************
  96 *  Compiler Options
  97 **************************************/
  98 #ifdef _MSC_VER    /* Visual Studio */
  99 #  include <intrin.h>
 100 #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
 101 #  pragma warning(disable : 4293)        /* disable: C4293: too large shift (32-bits) */
 102 #endif  /* _MSC_VER */
 103
 104 #ifndef FORCE_INLINE
 105 #  ifdef _MSC_VER    /* Visual Studio */
 106 #    define FORCE_INLINE static __forceinline
 107 #  else
 108 #    if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L   /* C99 */
 109 #      ifdef __GNUC__
 110 #        define FORCE_INLINE static inline __attribute__((always_inline))
 111 #      else
 112 #        define FORCE_INLINE static inline
 113 #      endif
 114 #    else
 115 #      define FORCE_INLINE static
 116 #    endif /* __STDC_VERSION__ */
 117 #  endif  /* _MSC_VER */
 118 #endif /* FORCE_INLINE */
 119
 120 #if (defined(__GNUC__) && (__GNUC__ >= 3)) || (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 800)) || defined(__clang__)
 121 #  define expect(expr,value)    (__builtin_expect ((expr),(value)) )
 122 #else
 123 #  define expect(expr,value)    (expr)
 124 #endif
 125
 126 #define likely(expr)     expect((expr) != 0, 1)
 127 #define unlikely(expr)   expect((expr) != 0, 0)
 128
 129
 130 /*-************************************
 131 *  Memory routines
 132 **************************************/
 133 #include <stdlib.h>   /* malloc, calloc, free */
 134 #define ALLOCATOR(n,s) calloc(n,s)
 135 #define FREEMEM        free
 136 #include <string.h>   /* memset, memcpy */
 137 #define MEM_INIT       memset
 138
 139
 140 /*-************************************
 141 *  Basic Types
 142 **************************************/
 143 #if defined(__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
 144 # include <stdint.h>
 145   typedef  uint8_t BYTE;
 146   typedef uint16_t U16;
 147   typedef uint32_t U32;
 148   typedef  int32_t S32;
 149   typedef uint64_t U64;
 150   typedef uintptr_t uptrval;
 151 #else
 152   typedef unsigned char       BYTE;
 153   typedef unsigned short      U16;
 154   typedef unsigned int        U32;
 155   typedef   signed int        S32;
 156   typedef unsigned long long  U64;
 157   typedef size_t              uptrval;   /* generally true, except OpenVMS-64 */
 158 #endif
 159
 160 #if defined(__x86_64__)
 161   typedef U64    reg_t;   /* 64-bits in x32 mode */
 162 #else
 163   typedef size_t reg_t;   /* 32-bits in x32 mode */
 164 #endif
 165
 166 /*-************************************
 167 *  Reading and writing into memory
 168 **************************************/
 169 static unsigned LZ4_isLittleEndian(void)
 170 {
 171     const union { U32 u; BYTE c[4]; } one = { 1 };   /* don't use static : performance detrimental */
 172     return one.c[0];
 173 }
 174
 175
 176 #if defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==2)
 177 /* lie to the compiler about data alignment; use with caution */
 178
 179 static U16 LZ4_read16(const void* memPtr) { return *(const U16*) memPtr; }
 180 static U32 LZ4_read32(const void* memPtr) { return *(const U32*) memPtr; }
 181 static reg_t LZ4_read_ARCH(const void* memPtr) { return *(const reg_t*) memPtr; }
 182
 183 static void LZ4_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
 184 static void LZ4_write32(void* memPtr, U32 value) { *(U32*)memPtr = value; }
 185
 186 #elif defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==1)
 187
 188 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
 189 /* currently only defined for gcc and icc */
 190 typedef union { U16 u16; U32 u32; reg_t uArch; } __attribute__((packed)) unalign;
 191
 192 static U16 LZ4_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
 193 static U32 LZ4_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
 194 static reg_t LZ4_read_ARCH(const void* ptr) { return ((const unalign*)ptr)->uArch; }
 195
 196 static void LZ4_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }
 197 static void LZ4_write32(void* memPtr, U32 value) { ((unalign*)memPtr)->u32 = value; }
 198
 199 #else  /* safe and portable access through memcpy() */
 200
 201 static U16 LZ4_read16(const void* memPtr)
 202 {
 203     U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
 204 }
 205
 206 static U32 LZ4_read32(const void* memPtr)
 207 {
 208     U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
 209 }
 210
 211 static reg_t LZ4_read_ARCH(const void* memPtr)
 212 {
 213     reg_t val; memcpy(&val, memPtr, sizeof(val)); return val;
 214 }
 215
 216 static void LZ4_write16(void* memPtr, U16 value)
 217 {
 218     memcpy(memPtr, &value, sizeof(value));
 219 }
 220
 221 static void LZ4_write32(void* memPtr, U32 value)
 222 {
 223     memcpy(memPtr, &value, sizeof(value));
 224 }
 225
 226 #endif /* LZ4_FORCE_MEMORY_ACCESS */
 227
 228
 229 static U16 LZ4_readLE16(const void* memPtr)
 230 {
 231     if (LZ4_isLittleEndian()) {
 232         return LZ4_read16(memPtr);
 233     } else {
 234         const BYTE* p = (const BYTE*)memPtr;
 235         return (U16)((U16)p[0] + (p[1]<<8));
 236     }
 237 }
 238
 239 static void LZ4_writeLE16(void* memPtr, U16 value)
 240 {
 241     if (LZ4_isLittleEndian()) {
 242         LZ4_write16(memPtr, value);
 243     } else {
 244         BYTE* p = (BYTE*)memPtr;
 245         p[0] = (BYTE) value;
 246         p[1] = (BYTE)(value>>8);
 247     }
 248 }
 249
 250 static void LZ4_copy8(void* dst, const void* src)
 251 {
 252     memcpy(dst,src,8);
 253 }
 254
 255 /* customized variant of memcpy, which can overwrite up to 8 bytes beyond dstEnd */
 256 static void LZ4_wildCopy(void* dstPtr, const void* srcPtr, void* dstEnd)
 257 {
 258     BYTE* d = (BYTE*)dstPtr;
 259     const BYTE* s = (const BYTE*)srcPtr;
 260     BYTE* const e = (BYTE*)dstEnd;
 261
 262     do { LZ4_copy8(d,s); d+=8; s+=8; } while (d<e);
 263 }
 264
 265
 266 /*-************************************
 267 *  Common Constants
 268 **************************************/
 269 #define MINMATCH 4
 270
 271 #define WILDCOPYLENGTH 8
 272 #define LASTLITERALS 5
 273 #define MFLIMIT (WILDCOPYLENGTH+MINMATCH)
 274 static const int LZ4_minLength = (MFLIMIT+1);
 275
 276 #define KB *(1 <<10)
 277 #define MB *(1 <<20)
 278 #define GB *(1U<<30)
 279
 280 #define MAXD_LOG 16
 281 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
 282
 283 #define ML_BITS  4
 284 #define ML_MASK  ((1U<<ML_BITS)-1)
 285 #define RUN_BITS (8-ML_BITS)
 286 #define RUN_MASK ((1U<<RUN_BITS)-1)
 287
 288
 289 /*-************************************
 290 *  Error detection
 291 **************************************/
 292 #define LZ4_STATIC_ASSERT(c)    { enum { LZ4_static_assert = 1/(int)(!!(c)) }; }   /* use only *after* variable declarations */
 293
 294 #if defined(LZ4_DEBUG) && (LZ4_DEBUG>=2)
 295 #  include <stdio.h>
 296 #  define DEBUGLOG(l, ...) {                          \
 297                 if (l<=LZ4_DEBUG) {                   \
 298                     fprintf(stderr, __FILE__ ": ");   \
 299                     fprintf(stderr, __VA_ARGS__);     \
 300                     fprintf(stderr, " \n");           \
 301             }   }
 302 #else
 303 #  define DEBUGLOG(l, ...)      {}    /* disabled */
 304 #endif
 305
 306
 307 /*-************************************
 308 *  Common functions
 309 **************************************/
 310 static unsigned LZ4_NbCommonBytes (register reg_t val)
 311 {
 312     if (LZ4_isLittleEndian()) {
 313         if (sizeof(val)==8) {
 314 #       if defined(_MSC_VER) && defined(_WIN64) && !defined(LZ4_FORCE_SW_BITCOUNT)
 315             unsigned long r = 0;
 316             _BitScanForward64( &r, (U64)val );
 317             return (int)(r>>3);
 318 #       elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT)
 319             return (__builtin_ctzll((U64)val) >> 3);
 320 #       else
 321             static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5, 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 4, 5, 7, 2, 6, 5, 7, 6, 7, 7 };
 322             return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
 323 #       endif
 324         } else /* 32 bits */ {
 325 #       if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
 326             unsigned long r;
 327             _BitScanForward( &r, (U32)val );
 328             return (int)(r>>3);
 329 #       elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT)
 330             return (__builtin_ctz((U32)val) >> 3);
 331 #       else
 332             static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 };
 333             return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
 334 #       endif
 335         }
 336     } else   /* Big Endian CPU */ {
 337         if (sizeof(val)==8) {
 338 #       if defined(_MSC_VER) && defined(_WIN64) && !defined(LZ4_FORCE_SW_BITCOUNT)
 339             unsigned long r = 0;
 340             _BitScanReverse64( &r, val );
 341             return (unsigned)(r>>3);
 342 #       elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT)
 343             return (__builtin_clzll((U64)val) >> 3);
 344 #       else
 345             unsigned r;
 346             if (!(val>>32)) { r=4; } else { r=0; val>>=32; }
 347             if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
 348             r += (!val);
 349             return r;
 350 #       endif
 351         } else /* 32 bits */ {
 352 #       if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
 353             unsigned long r = 0;
 354             _BitScanReverse( &r, (unsigned long)val );
 355             return (unsigned)(r>>3);
 356 #       elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT)
 357             return (__builtin_clz((U32)val) >> 3);
 358 #       else
 359             unsigned r;
 360             if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
 361             r += (!val);
 362             return r;
 363 #       endif
 364         }
 365     }
 366 }
 367
 368 #define STEPSIZE sizeof(reg_t)
 369 static unsigned LZ4_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* pInLimit)
 370 {
 371     const BYTE* const pStart = pIn;
 372
 373     while (likely(pIn<pInLimit-(STEPSIZE-1))) {
 374         reg_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn);
 375         if (!diff) { pIn+=STEPSIZE; pMatch+=STEPSIZE; continue; }
 376         pIn += LZ4_NbCommonBytes(diff);
 377         return (unsigned)(pIn - pStart);
 378     }
 379
 380     if ((STEPSIZE==8) && (pIn<(pInLimit-3)) && (LZ4_read32(pMatch) == LZ4_read32(pIn))) { pIn+=4; pMatch+=4; }
 381     if ((pIn<(pInLimit-1)) && (LZ4_read16(pMatch) == LZ4_read16(pIn))) { pIn+=2; pMatch+=2; }
 382     if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
 383     return (unsigned)(pIn - pStart);
 384 }
 385
 386
 387 #ifndef LZ4_COMMONDEFS_ONLY
 388 /*-************************************
 389 *  Local Constants
 390 **************************************/
 391 static const int LZ4_64Klimit = ((64 KB) + (MFLIMIT-1));
 392 static const U32 LZ4_skipTrigger = 6;  /* Increase this value ==> compression run slower on incompressible data */
 393
 394
 395 /*-************************************
 396 *  Local Structures and types
 397 **************************************/
 398 typedef enum { notLimited = 0, limitedOutput = 1 } limitedOutput_directive;
 399 typedef enum { byPtr, byU32, byU16 } tableType_t;
 400
 401 typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive;
 402 typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive;
 403
 404 typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;
 405 typedef enum { full = 0, partial = 1 } earlyEnd_directive;
 406
 407
 408 /*-************************************
 409 *  Local Utils
 410 **************************************/
 411 int LZ4_versionNumber (void) { return LZ4_VERSION_NUMBER; }
 412 const char* LZ4_versionString(void) { return LZ4_VERSION_STRING; }
 413 int LZ4_compressBound(int isize)  { return LZ4_COMPRESSBOUND(isize); }
 414 int LZ4_sizeofState() { return LZ4_STREAMSIZE; }
 415
 416
 417 /*-******************************
 418 *  Compression functions
 419 ********************************/
 420 static U32 LZ4_hash4(U32 sequence, tableType_t const tableType)
 421 {
 422     if (tableType == byU16)
 423         return ((sequence * 2654435761U) >> ((MINMATCH*8)-(LZ4_HASHLOG+1)));
 424     else
 425         return ((sequence * 2654435761U) >> ((MINMATCH*8)-LZ4_HASHLOG));
 426 }
 427
 428 static U32 LZ4_hash5(U64 sequence, tableType_t const tableType)
 429 {
 430     static const U64 prime5bytes = 889523592379ULL;
 431     static const U64 prime8bytes = 11400714785074694791ULL;
 432     const U32 hashLog = (tableType == byU16) ? LZ4_HASHLOG+1 : LZ4_HASHLOG;
 433     if (LZ4_isLittleEndian())
 434         return (U32)(((sequence << 24) * prime5bytes) >> (64 - hashLog));
 435     else
 436         return (U32)(((sequence >> 24) * prime8bytes) >> (64 - hashLog));
 437 }
 438
 439 FORCE_INLINE U32 LZ4_hashPosition(const void* const p, tableType_t const tableType)
 440 {
 441     if ((sizeof(reg_t)==8) && (tableType != byU16)) return LZ4_hash5(LZ4_read_ARCH(p), tableType);
 442     return LZ4_hash4(LZ4_read32(p), tableType);
 443 }
 444
 445 static void LZ4_putPositionOnHash(const BYTE* p, U32 h, void* tableBase, tableType_t const tableType, const BYTE* srcBase)
 446 {
 447     switch (tableType)
 448     {
 449     case byPtr: { const BYTE** hashTable = (const BYTE**)tableBase; hashTable[h] = p; return; }
 450     case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = (U32)(p-srcBase); return; }
 451     case byU16: { U16* hashTable = (U16*) tableBase; hashTable[h] = (U16)(p-srcBase); return; }
 452     }
 453 }
 454
 455 FORCE_INLINE void LZ4_putPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase)
 456 {
 457     U32 const h = LZ4_hashPosition(p, tableType);
 458     LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase);
 459 }
 460
 461 static const BYTE* LZ4_getPositionOnHash(U32 h, void* tableBase, tableType_t tableType, const BYTE* srcBase)
 462 {
 463     if (tableType == byPtr) { const BYTE** hashTable = (const BYTE**) tableBase; return hashTable[h]; }
 464     if (tableType == byU32) { const U32* const hashTable = (U32*) tableBase; return hashTable[h] + srcBase; }
 465     { const U16* const hashTable = (U16*) tableBase; return hashTable[h] + srcBase; }   /* default, to ensure a return */
 466 }
 467
 468 FORCE_INLINE const BYTE* LZ4_getPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase)
 469 {
 470     U32 const h = LZ4_hashPosition(p, tableType);
 471     return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase);
 472 }
 473
 474
 475 /** LZ4_compress_generic() :
 476     inlined, to ensure branches are decided at compilation time */
 477 FORCE_INLINE int LZ4_compress_generic(
 478                  LZ4_stream_t_internal* const cctx,
 479                  const char* const source,
 480                  char* const dest,
 481                  const int inputSize,
 482                  const int maxOutputSize,
 483                  const limitedOutput_directive outputLimited,
 484                  const tableType_t tableType,
 485                  const dict_directive dict,
 486                  const dictIssue_directive dictIssue,
 487                  const U32 acceleration)
 488 {
 489     const BYTE* ip = (const BYTE*) source;
 490     const BYTE* base;
 491     const BYTE* lowLimit;
 492     const BYTE* const lowRefLimit = ip - cctx->dictSize;
 493     const BYTE* const dictionary = cctx->dictionary;
 494     const BYTE* const dictEnd = dictionary + cctx->dictSize;
 495     const ptrdiff_t dictDelta = dictEnd - (const BYTE*)source;
 496     const BYTE* anchor = (const BYTE*) source;
 497     const BYTE* const iend = ip + inputSize;
 498     const BYTE* const mflimit = iend - MFLIMIT;
 499     const BYTE* const matchlimit = iend - LASTLITERALS;
 500
 501     BYTE* op = (BYTE*) dest;
 502     BYTE* const olimit = op + maxOutputSize;
 503
 504     U32 forwardH;
 505
 506     /* Init conditions */
 507     if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0;   /* Unsupported inputSize, too large (or negative) */
 508     switch(dict)
 509     {
 510     case noDict:
 511     default:
 512         base = (const BYTE*)source;
 513         lowLimit = (const BYTE*)source;
 514         break;
 515     case withPrefix64k:
 516         base = (const BYTE*)source - cctx->currentOffset;
 517         lowLimit = (const BYTE*)source - cctx->dictSize;
 518         break;
 519     case usingExtDict:
 520         base = (const BYTE*)source - cctx->currentOffset;
 521         lowLimit = (const BYTE*)source;
 522         break;
 523     }
 524     if ((tableType == byU16) && (inputSize>=LZ4_64Klimit)) return 0;   /* Size too large (not within 64K limit) */
 525     if (inputSize<LZ4_minLength) goto _last_literals;                  /* Input too small, no compression (all literals) */
 526
 527     /* First Byte */
 528     LZ4_putPosition(ip, cctx->hashTable, tableType, base);
 529     ip++; forwardH = LZ4_hashPosition(ip, tableType);
 530
 531     /* Main Loop */
 532     for ( ; ; ) {
 533         ptrdiff_t refDelta = 0;
 534         const BYTE* match;
 535         BYTE* token;
 536
 537         /* Find a match */
 538         {   const BYTE* forwardIp = ip;
 539             unsigned step = 1;
 540             unsigned searchMatchNb = acceleration << LZ4_skipTrigger;
 541             do {
 542                 U32 const h = forwardH;
 543                 ip = forwardIp;
 544                 forwardIp += step;
 545                 step = (searchMatchNb++ >> LZ4_skipTrigger);
 546
 547                 if (unlikely(forwardIp > mflimit)) goto _last_literals;
 548
 549                 match = LZ4_getPositionOnHash(h, cctx->hashTable, tableType, base);
 550                 if (dict==usingExtDict) {
 551                     if (match < (const BYTE*)source) {
 552                         refDelta = dictDelta;
 553                         lowLimit = dictionary;
 554                     } else {
 555                         refDelta = 0;
 556                         lowLimit = (const BYTE*)source;
 557                 }   }
 558                 forwardH = LZ4_hashPosition(forwardIp, tableType);
 559                 LZ4_putPositionOnHash(ip, h, cctx->hashTable, tableType, base);
 560
 561             } while ( ((dictIssue==dictSmall) ? (match < lowRefLimit) : 0)
 562                 || ((tableType==byU16) ? 0 : (match + MAX_DISTANCE < ip))
 563                 || (LZ4_read32(match+refDelta) != LZ4_read32(ip)) );
 564         }
 565
 566         /* Catch up */
 567         while (((ip>anchor) & (match+refDelta > lowLimit)) && (unlikely(ip[-1]==match[refDelta-1]))) { ip--; match--; }
 568
 569         /* Encode Literals */
 570         {   unsigned const litLength = (unsigned)(ip - anchor);
 571             token = op++;
 572             if ((outputLimited) &&  /* Check output buffer overflow */
 573                 (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > olimit)))
 574                 return 0;
 575             if (litLength >= RUN_MASK) {
 576                 int len = (int)litLength-RUN_MASK;
 577                 *token = (RUN_MASK<<ML_BITS);
 578                 for(; len >= 255 ; len-=255) *op++ = 255;
 579                 *op++ = (BYTE)len;
 580             }
 581             else *token = (BYTE)(litLength<<ML_BITS);
 582
 583             /* Copy Literals */
 584             LZ4_wildCopy(op, anchor, op+litLength);
 585             op+=litLength;
 586         }
 587
 588 _next_match:
 589         /* Encode Offset */
 590         LZ4_writeLE16(op, (U16)(ip-match)); op+=2;
 591
 592         /* Encode MatchLength */
 593         {   unsigned matchCode;
 594
 595             if ((dict==usingExtDict) && (lowLimit==dictionary)) {
 596                 const BYTE* limit;
 597                 match += refDelta;
 598                 limit = ip + (dictEnd-match);
 599                 if (limit > matchlimit) limit = matchlimit;
 600                 matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, limit);
 601                 ip += MINMATCH + matchCode;
 602                 if (ip==limit) {
 603                     unsigned const more = LZ4_count(ip, (const BYTE*)source, matchlimit);
 604                     matchCode += more;
 605                     ip += more;
 606                 }
 607             } else {
 608                 matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, matchlimit);
 609                 ip += MINMATCH + matchCode;
 610             }
 611
 612             if ( outputLimited &&    /* Check output buffer overflow */
 613                 (unlikely(op + (1 + LASTLITERALS) + (matchCode>>8) > olimit)) )
 614                 return 0;
 615             if (matchCode >= ML_MASK) {
 616                 *token += ML_MASK;
 617                 matchCode -= ML_MASK;
 618                 LZ4_write32(op, 0xFFFFFFFF);
 619                 while (matchCode >= 4*255) {
 620                     op+=4;
 621                     LZ4_write32(op, 0xFFFFFFFF);
 622                     matchCode -= 4*255;
 623                 }
 624                 op += matchCode / 255;
 625                 *op++ = (BYTE)(matchCode % 255);
 626             } else
 627                 *token += (BYTE)(matchCode);
 628         }
 629
 630         anchor = ip;
 631
 632         /* Test end of chunk */
 633         if (ip > mflimit) break;
 634
 635         /* Fill table */
 636         LZ4_putPosition(ip-2, cctx->hashTable, tableType, base);
 637
 638         /* Test next position */
 639         match = LZ4_getPosition(ip, cctx->hashTable, tableType, base);
 640         if (dict==usingExtDict) {
 641             if (match < (const BYTE*)source) {
 642                 refDelta = dictDelta;
 643                 lowLimit = dictionary;
 644             } else {
 645                 refDelta = 0;
 646                 lowLimit = (const BYTE*)source;
 647         }   }
 648         LZ4_putPosition(ip, cctx->hashTable, tableType, base);
 649         if ( ((dictIssue==dictSmall) ? (match>=lowRefLimit) : 1)
 650             && (match+MAX_DISTANCE>=ip)
 651             && (LZ4_read32(match+refDelta)==LZ4_read32(ip)) )
 652         { token=op++; *token=0; goto _next_match; }
 653
 654         /* Prepare next loop */
 655         forwardH = LZ4_hashPosition(++ip, tableType);
 656     }
 657
 658 _last_literals:
 659     /* Encode Last Literals */
 660     {   size_t const lastRun = (size_t)(iend - anchor);
 661         if ( (outputLimited) &&  /* Check output buffer overflow */
 662             ((op - (BYTE*)dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize) )
 663             return 0;
 664         if (lastRun >= RUN_MASK) {
 665             size_t accumulator = lastRun - RUN_MASK;
 666             *op++ = RUN_MASK << ML_BITS;
 667             for(; accumulator >= 255 ; accumulator-=255) *op++ = 255;
 668             *op++ = (BYTE) accumulator;
 669         } else {
 670             *op++ = (BYTE)(lastRun<<ML_BITS);
 671         }
 672         memcpy(op, anchor, lastRun);
 673         op += lastRun;
 674     }
 675
 676     /* End */
 677     return (int) (((char*)op)-dest);
 678 }
 679
 680
 681 int LZ4_compress_fast_extState(void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
 682 {
 683     LZ4_stream_t_internal* ctx = &((LZ4_stream_t*)state)->internal_donotuse;
 684     LZ4_resetStream((LZ4_stream_t*)state);
 685     if (acceleration < 1) acceleration = ACCELERATION_DEFAULT;
 686
 687     if (maxOutputSize >= LZ4_compressBound(inputSize)) {
 688         if (inputSize < LZ4_64Klimit)
 689             return LZ4_compress_generic(ctx, source, dest, inputSize,             0,    notLimited,                        byU16, noDict, noDictIssue, acceleration);
 690         else
 691             return LZ4_compress_generic(ctx, source, dest, inputSize,             0,    notLimited, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue, acceleration);
 692     } else {
 693         if (inputSize < LZ4_64Klimit)
 694             return LZ4_compress_generic(ctx, source, dest, inputSize, maxOutputSize, limitedOutput,                        byU16, noDict, noDictIssue, acceleration);
 695         else
 696             return LZ4_compress_generic(ctx, source, dest, inputSize, maxOutputSize, limitedOutput, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue, acceleration);
 697     }
 698 }
 699
 700
 701 int LZ4_compress_fast(const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
 702 {
 703 #if (LZ4_HEAPMODE)
 704     void* ctxPtr = ALLOCATOR(1, sizeof(LZ4_stream_t));   /* malloc-calloc always properly aligned */
 705 #else
 706     LZ4_stream_t ctx;
 707     void* const ctxPtr = &ctx;
 708 #endif
 709
 710     int const result = LZ4_compress_fast_extState(ctxPtr, source, dest, inputSize, maxOutputSize, acceleration);
 711
 712 #if (LZ4_HEAPMODE)
 713     FREEMEM(ctxPtr);
 714 #endif
 715     return result;
 716 }
 717
 718
 719 int LZ4_compress_default(const char* source, char* dest, int inputSize, int maxOutputSize)
 720 {
 721     return LZ4_compress_fast(source, dest, inputSize, maxOutputSize, 1);
 722 }
 723
 724
 725 /* hidden debug function */
 726 /* strangely enough, gcc generates faster code when this function is uncommented, even if unused */
 727 int LZ4_compress_fast_force(const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
 728 {
 729     LZ4_stream_t ctx;
 730     LZ4_resetStream(&ctx);
 731
 732     if (inputSize < LZ4_64Klimit)
 733         return LZ4_compress_generic(&ctx.internal_donotuse, source, dest, inputSize, maxOutputSize, limitedOutput, byU16,                        noDict, noDictIssue, acceleration);
 734     else
 735         return LZ4_compress_generic(&ctx.internal_donotuse, source, dest, inputSize, maxOutputSize, limitedOutput, sizeof(void*)==8 ? byU32 : byPtr, noDict, noDictIssue, acceleration);
 736 }
 737
 738
 739 /*-******************************
 740 *  *_destSize() variant
 741 ********************************/
 742
 743 static int LZ4_compress_destSize_generic(
 744                        LZ4_stream_t_internal* const ctx,
 745                  const char* const src,
 746                        char* const dst,
 747                        int*  const srcSizePtr,
 748                  const int targetDstSize,
 749                  const tableType_t tableType)
 750 {
 751     const BYTE* ip = (const BYTE*) src;
 752     const BYTE* base = (const BYTE*) src;
 753     const BYTE* lowLimit = (const BYTE*) src;
 754     const BYTE* anchor = ip;
 755     const BYTE* const iend = ip + *srcSizePtr;
 756     const BYTE* const mflimit = iend - MFLIMIT;
 757     const BYTE* const matchlimit = iend - LASTLITERALS;
 758
 759     BYTE* op = (BYTE*) dst;
 760     BYTE* const oend = op + targetDstSize;
 761     BYTE* const oMaxLit = op + targetDstSize - 2 /* offset */ - 8 /* because 8+MINMATCH==MFLIMIT */ - 1 /* token */;
 762     BYTE* const oMaxMatch = op + targetDstSize - (LASTLITERALS + 1 /* token */);
 763     BYTE* const oMaxSeq = oMaxLit - 1 /* token */;
 764
 765     U32 forwardH;
 766
 767
 768     /* Init conditions */
 769     if (targetDstSize < 1) return 0;                                     /* Impossible to store anything */
 770     if ((U32)*srcSizePtr > (U32)LZ4_MAX_INPUT_SIZE) return 0;            /* Unsupported input size, too large (or negative) */
 771     if ((tableType == byU16) && (*srcSizePtr>=LZ4_64Klimit)) return 0;   /* Size too large (not within 64K limit) */
 772     if (*srcSizePtr<LZ4_minLength) goto _last_literals;                  /* Input too small, no compression (all literals) */
 773
 774     /* First Byte */
 775     *srcSizePtr = 0;
 776     LZ4_putPosition(ip, ctx->hashTable, tableType, base);
 777     ip++; forwardH = LZ4_hashPosition(ip, tableType);
 778
 779     /* Main Loop */
 780     for ( ; ; ) {
 781         const BYTE* match;
 782         BYTE* token;
 783
 784         /* Find a match */
 785         {   const BYTE* forwardIp = ip;
 786             unsigned step = 1;
 787             unsigned searchMatchNb = 1 << LZ4_skipTrigger;
 788
 789             do {
 790                 U32 h = forwardH;
 791                 ip = forwardIp;
 792                 forwardIp += step;
 793                 step = (searchMatchNb++ >> LZ4_skipTrigger);
 794
 795                 if (unlikely(forwardIp > mflimit)) goto _last_literals;
 796
 797                 match = LZ4_getPositionOnHash(h, ctx->hashTable, tableType, base);
 798                 forwardH = LZ4_hashPosition(forwardIp, tableType);
 799                 LZ4_putPositionOnHash(ip, h, ctx->hashTable, tableType, base);
 800
 801             } while ( ((tableType==byU16) ? 0 : (match + MAX_DISTANCE < ip))
 802                 || (LZ4_read32(match) != LZ4_read32(ip)) );
 803         }
 804
 805         /* Catch up */
 806         while ((ip>anchor) && (match > lowLimit) && (unlikely(ip[-1]==match[-1]))) { ip--; match--; }
 807
 808         /* Encode Literal length */
 809         {   unsigned litLength = (unsigned)(ip - anchor);
 810             token = op++;
 811             if (op + ((litLength+240)/255) + litLength > oMaxLit) {
 812                 /* Not enough space for a last match */
 813                 op--;
 814                 goto _last_literals;
 815             }
 816             if (litLength>=RUN_MASK) {
 817                 unsigned len = litLength - RUN_MASK;
 818                 *token=(RUN_MASK<<ML_BITS);
 819                 for(; len >= 255 ; len-=255) *op++ = 255;
 820                 *op++ = (BYTE)len;
 821             }
 822             else *token = (BYTE)(litLength<<ML_BITS);
 823
 824             /* Copy Literals */
 825             LZ4_wildCopy(op, anchor, op+litLength);
 826             op += litLength;
 827         }
 828
 829 _next_match:
 830         /* Encode Offset */
 831         LZ4_writeLE16(op, (U16)(ip-match)); op+=2;
 832
 833         /* Encode MatchLength */
 834         {   size_t matchLength = LZ4_count(ip+MINMATCH, match+MINMATCH, matchlimit);
 835
 836             if (op + ((matchLength+240)/255) > oMaxMatch) {
 837                 /* Match description too long : reduce it */
 838                 matchLength = (15-1) + (oMaxMatch-op) * 255;
 839             }
 840             ip += MINMATCH + matchLength;
 841
 842             if (matchLength>=ML_MASK) {
 843                 *token += ML_MASK;
 844                 matchLength -= ML_MASK;
 845                 while (matchLength >= 255) { matchLength-=255; *op++ = 255; }
 846                 *op++ = (BYTE)matchLength;
 847             }
 848             else *token += (BYTE)(matchLength);
 849         }
 850
 851         anchor = ip;
 852
 853         /* Test end of block */
 854         if (ip > mflimit) break;
 855         if (op > oMaxSeq) break;
 856
 857         /* Fill table */
 858         LZ4_putPosition(ip-2, ctx->hashTable, tableType, base);
 859
 860         /* Test next position */
 861         match = LZ4_getPosition(ip, ctx->hashTable, tableType, base);
 862         LZ4_putPosition(ip, ctx->hashTable, tableType, base);
 863         if ( (match+MAX_DISTANCE>=ip)
 864             && (LZ4_read32(match)==LZ4_read32(ip)) )
 865         { token=op++; *token=0; goto _next_match; }
 866
 867         /* Prepare next loop */
 868         forwardH = LZ4_hashPosition(++ip, tableType);
 869     }
 870
 871 _last_literals:
 872     /* Encode Last Literals */
 873     {   size_t lastRunSize = (size_t)(iend - anchor);
 874         if (op + 1 /* token */ + ((lastRunSize+240)/255) /* litLength */ + lastRunSize /* literals */ > oend) {
 875             /* adapt lastRunSize to fill 'dst' */
 876             lastRunSize  = (oend-op) - 1;
 877             lastRunSize -= (lastRunSize+240)/255;
 878         }
 879         ip = anchor + lastRunSize;
 880
 881         if (lastRunSize >= RUN_MASK) {
 882             size_t accumulator = lastRunSize - RUN_MASK;
 883             *op++ = RUN_MASK << ML_BITS;
 884             for(; accumulator >= 255 ; accumulator-=255) *op++ = 255;
 885             *op++ = (BYTE) accumulator;
 886         } else {
 887             *op++ = (BYTE)(lastRunSize<<ML_BITS);
 888         }
 889         memcpy(op, anchor, lastRunSize);
 890         op += lastRunSize;
 891     }
 892
 893     /* End */
 894     *srcSizePtr = (int) (((const char*)ip)-src);
 895     return (int) (((char*)op)-dst);
 896 }
 897
 898
 899 static int LZ4_compress_destSize_extState (LZ4_stream_t* state, const char* src, char* dst, int* srcSizePtr, int targetDstSize)
 900 {
 901     LZ4_resetStream(state);
 902
 903     if (targetDstSize >= LZ4_compressBound(*srcSizePtr)) {  /* compression success is guaranteed */
 904         return LZ4_compress_fast_extState(state, src, dst, *srcSizePtr, targetDstSize, 1);
 905     } else {
 906         if (*srcSizePtr < LZ4_64Klimit)
 907             return LZ4_compress_destSize_generic(&state->internal_donotuse, src, dst, srcSizePtr, targetDstSize, byU16);
 908         else
 909             return LZ4_compress_destSize_generic(&state->internal_donotuse, src, dst, srcSizePtr, targetDstSize, sizeof(void*)==8 ? byU32 : byPtr);
 910     }
 911 }
 912
 913
 914 int LZ4_compress_destSize(const char* src, char* dst, int* srcSizePtr, int targetDstSize)
 915 {
 916 #if (LZ4_HEAPMODE)
 917     LZ4_stream_t* ctx = (LZ4_stream_t*)ALLOCATOR(1, sizeof(LZ4_stream_t));   /* malloc-calloc always properly aligned */
 918 #else
 919     LZ4_stream_t ctxBody;
 920     LZ4_stream_t* ctx = &ctxBody;
 921 #endif
 922
 923     int result = LZ4_compress_destSize_extState(ctx, src, dst, srcSizePtr, targetDstSize);
 924
 925 #if (LZ4_HEAPMODE)
 926     FREEMEM(ctx);
 927 #endif
 928     return result;
 929 }
 930
 931
 932
 933 /*-******************************
 934 *  Streaming functions
 935 ********************************/
 936
 937 LZ4_stream_t* LZ4_createStream(void)
 938 {
 939     LZ4_stream_t* lz4s = (LZ4_stream_t*)ALLOCATOR(8, LZ4_STREAMSIZE_U64);
 940     LZ4_STATIC_ASSERT(LZ4_STREAMSIZE >= sizeof(LZ4_stream_t_internal));    /* A compilation error here means LZ4_STREAMSIZE is not large enough */
 941     LZ4_resetStream(lz4s);
 942     return lz4s;
 943 }
 944
 945 void LZ4_resetStream (LZ4_stream_t* LZ4_stream)
 946 {
 947     MEM_INIT(LZ4_stream, 0, sizeof(LZ4_stream_t));
 948 }
 949
 950 int LZ4_freeStream (LZ4_stream_t* LZ4_stream)
 951 {
 952     if (!LZ4_stream) return 0;   /* support free on NULL */
 953     FREEMEM(LZ4_stream);
 954     return (0);
 955 }
 956
 957
 958 #define HASH_UNIT sizeof(reg_t)
 959 int LZ4_loadDict (LZ4_stream_t* LZ4_dict, const char* dictionary, int dictSize)
 960 {
 961     LZ4_stream_t_internal* dict = &LZ4_dict->internal_donotuse;
 962     const BYTE* p = (const BYTE*)dictionary;
 963     const BYTE* const dictEnd = p + dictSize;
 964     const BYTE* base;
 965
 966     if ((dict->initCheck) || (dict->currentOffset > 1 GB))  /* Uninitialized structure, or reuse overflow */
 967         LZ4_resetStream(LZ4_dict);
 968
 969     if (dictSize < (int)HASH_UNIT) {
 970         dict->dictionary = NULL;
 971         dict->dictSize = 0;
 972         return 0;
 973     }
 974
 975     if ((dictEnd - p) > 64 KB) p = dictEnd - 64 KB;
 976     dict->currentOffset += 64 KB;
 977     base = p - dict->currentOffset;
 978     dict->dictionary = p;
 979     dict->dictSize = (U32)(dictEnd - p);
 980     dict->currentOffset += dict->dictSize;
 981
 982     while (p <= dictEnd-HASH_UNIT) {
 983         LZ4_putPosition(p, dict->hashTable, byU32, base);
 984         p+=3;
 985     }
 986
 987     return dict->dictSize;
 988 }
 989
 990
 991 static void LZ4_renormDictT(LZ4_stream_t_internal* LZ4_dict, const BYTE* src)
 992 {
 993     if ((LZ4_dict->currentOffset > 0x80000000) ||
 994         ((uptrval)LZ4_dict->currentOffset > (uptrval)src)) {   /* address space overflow */
 995         /* rescale hash table */
 996         U32 const delta = LZ4_dict->currentOffset - 64 KB;
 997         const BYTE* dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize;
 998         int i;
 999         for (i=0; i<LZ4_HASH_SIZE_U32; i++) {
1000             if (LZ4_dict->hashTable[i] < delta) LZ4_dict->hashTable[i]=0;
1001             else LZ4_dict->hashTable[i] -= delta;
1002         }
1003         LZ4_dict->currentOffset = 64 KB;
1004         if (LZ4_dict->dictSize > 64 KB) LZ4_dict->dictSize = 64 KB;
1005         LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize;
1006     }
1007 }
1008
1009
1010 int LZ4_compress_fast_continue (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
1011 {
1012     LZ4_stream_t_internal* streamPtr = &LZ4_stream->internal_donotuse;
1013     const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize;
1014
1015     const BYTE* smallest = (const BYTE*) source;
1016     if (streamPtr->initCheck) return 0;   /* Uninitialized structure detected */
1017     if ((streamPtr->dictSize>0) && (smallest>dictEnd)) smallest = dictEnd;
1018     LZ4_renormDictT(streamPtr, smallest);
1019     if (acceleration < 1) acceleration = ACCELERATION_DEFAULT;
1020
1021     /* Check overlapping input/dictionary space */
1022     {   const BYTE* sourceEnd = (const BYTE*) source + inputSize;
1023         if ((sourceEnd > streamPtr->dictionary) && (sourceEnd < dictEnd)) {
1024             streamPtr->dictSize = (U32)(dictEnd - sourceEnd);
1025             if (streamPtr->dictSize > 64 KB) streamPtr->dictSize = 64 KB;
1026             if (streamPtr->dictSize < 4) streamPtr->dictSize = 0;
1027             streamPtr->dictionary = dictEnd - streamPtr->dictSize;
1028         }
1029     }
1030
1031     /* prefix mode : source data follows dictionary */
1032     if (dictEnd == (const BYTE*)source) {
1033         int result;
1034         if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset))
1035             result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, withPrefix64k, dictSmall, acceleration);
1036         else
1037             result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, withPrefix64k, noDictIssue, acceleration);
1038         streamPtr->dictSize += (U32)inputSize;
1039         streamPtr->currentOffset += (U32)inputSize;
1040         return result;
1041     }
1042
1043     /* external dictionary mode */
1044     {   int result;
1045         if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset))
1046             result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, usingExtDict, dictSmall, acceleration);
1047         else
1048             result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, usingExtDict, noDictIssue, acceleration);
1049         streamPtr->dictionary = (const BYTE*)source;
1050         streamPtr->dictSize = (U32)inputSize;
1051         streamPtr->currentOffset += (U32)inputSize;
1052         return result;
1053     }
1054 }
1055
1056
1057 /* Hidden debug function, to force external dictionary mode */
1058 int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int inputSize)
1059 {
1060     LZ4_stream_t_internal* streamPtr = &LZ4_dict->internal_donotuse;
1061     int result;
1062     const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize;
1063
1064     const BYTE* smallest = dictEnd;
1065     if (smallest > (const BYTE*) source) smallest = (const BYTE*) source;
1066     LZ4_renormDictT(streamPtr, smallest);
1067
1068     result = LZ4_compress_generic(streamPtr, source, dest, inputSize, 0, notLimited, byU32, usingExtDict, noDictIssue, 1);
1069
1070     streamPtr->dictionary = (const BYTE*)source;
1071     streamPtr->dictSize = (U32)inputSize;
1072     streamPtr->currentOffset += (U32)inputSize;
1073
1074     return result;
1075 }
1076
1077
1078 /*! LZ4_saveDict() :
1079  *  If previously compressed data block is not guaranteed to remain available at its memory location,
1080  *  save it into a safer place (char* safeBuffer).
1081  *  Note : you don't need to call LZ4_loadDict() afterwards,
1082  *         dictionary is immediately usable, you can therefore call LZ4_compress_fast_continue().
1083  *  Return : saved dictionary size in bytes (necessarily <= dictSize), or 0 if error.
1084  */
1085 int LZ4_saveDict (LZ4_stream_t* LZ4_dict, char* safeBuffer, int dictSize)
1086 {
1087     LZ4_stream_t_internal* const dict = &LZ4_dict->internal_donotuse;
1088     const BYTE* const previousDictEnd = dict->dictionary + dict->dictSize;
1089
1090     if ((U32)dictSize > 64 KB) dictSize = 64 KB;   /* useless to define a dictionary > 64 KB */
1091     if ((U32)dictSize > dict->dictSize) dictSize = dict->dictSize;
1092
1093     memmove(safeBuffer, previousDictEnd - dictSize, dictSize);
1094
1095     dict->dictionary = (const BYTE*)safeBuffer;
1096     dict->dictSize = (U32)dictSize;
1097
1098     return dictSize;
1099 }
1100
1101
1102
1103 /*-*****************************
1104 *  Decompression functions
1105 *******************************/
1106 /*! LZ4_decompress_generic() :
1107  *  This generic decompression function cover all use cases.
1108  *  It shall be instantiated several times, using different sets of directives
1109  *  Note that it is important this generic function is really inlined,
1110  *  in order to remove useless branches during compilation optimization.
1111  */
1112 FORCE_INLINE int LZ4_decompress_generic(
1113                  const char* const source,
1114                  char* const dest,
1115                  int inputSize,
1116                  int outputSize,         /* If endOnInput==endOnInputSize, this value is the max size of Output Buffer. */
1117
1118                  int endOnInput,         /* endOnOutputSize, endOnInputSize */
1119                  int partialDecoding,    /* full, partial */
1120                  int targetOutputSize,   /* only used if partialDecoding==partial */
1121                  int dict,               /* noDict, withPrefix64k, usingExtDict */
1122                  const BYTE* const lowPrefix,  /* == dest when no prefix */
1123                  const BYTE* const dictStart,  /* only if dict==usingExtDict */
1124                  const size_t dictSize         /* note : = 0 if noDict */
1125                  )
1126 {
1127     /* Local Variables */
1128     const BYTE* ip = (const BYTE*) source;
1129     const BYTE* const iend = ip + inputSize;
1130
1131     BYTE* op = (BYTE*) dest;
1132     BYTE* const oend = op + outputSize;
1133     BYTE* cpy;
1134     BYTE* oexit = op + targetOutputSize;
1135     const BYTE* const lowLimit = lowPrefix - dictSize;
1136
1137     const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize;
1138     const unsigned dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4};
1139     const int dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3};
1140
1141     const int safeDecode = (endOnInput==endOnInputSize);
1142     const int checkOffset = ((safeDecode) && (dictSize < (int)(64 KB)));
1143
1144
1145     /* Special cases */
1146     if ((partialDecoding) && (oexit > oend-MFLIMIT)) oexit = oend-MFLIMIT;                        /* targetOutputSize too high => decode everything */
1147     if ((endOnInput) && (unlikely(outputSize==0))) return ((inputSize==1) && (*ip==0)) ? 0 : -1;  /* Empty output buffer */
1148     if ((!endOnInput) && (unlikely(outputSize==0))) return (*ip==0?1:-1);
1149
1150     /* Main Loop : decode sequences */
1151     while (1) {
1152         size_t length;
1153         const BYTE* match;
1154         size_t offset;
1155
1156         /* get literal length */
1157         unsigned const token = *ip++;
1158         if ((length=(token>>ML_BITS)) == RUN_MASK) {
1159             unsigned s;
1160             do {
1161                 s = *ip++;
1162                 length += s;
1163             } while ( likely(endOnInput ? ip<iend-RUN_MASK : 1) & (s==255) );
1164             if ((safeDecode) && unlikely((uptrval)(op)+length<(uptrval)(op))) goto _output_error;   /* overflow detection */
1165             if ((safeDecode) && unlikely((uptrval)(ip)+length<(uptrval)(ip))) goto _output_error;   /* overflow detection */
1166         }
1167
1168         /* copy literals */
1169         cpy = op+length;
1170         if ( ((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT)) || (ip+length>iend-(2+1+LASTLITERALS))) )
1171             || ((!endOnInput) && (cpy>oend-WILDCOPYLENGTH)) )
1172         {
1173             if (partialDecoding) {
1174                 if (cpy > oend) goto _output_error;                           /* Error : write attempt beyond end of output buffer */
1175                 if ((endOnInput) && (ip+length > iend)) goto _output_error;   /* Error : read attempt beyond end of input buffer */
1176             } else {
1177                 if ((!endOnInput) && (cpy != oend)) goto _output_error;       /* Error : block decoding must stop exactly there */
1178                 if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) goto _output_error;   /* Error : input must be consumed */
1179             }
1180             memcpy(op, ip, length);
1181             ip += length;
1182             op += length;
1183             break;     /* Necessarily EOF, due to parsing restrictions */
1184         }
1185         LZ4_wildCopy(op, ip, cpy);
1186         ip += length; op = cpy;
1187
1188         /* get offset */
1189         offset = LZ4_readLE16(ip); ip+=2;
1190         match = op - offset;
1191         if ((checkOffset) && (unlikely(match < lowLimit))) goto _output_error;   /* Error : offset outside buffers */
1192         LZ4_write32(op, (U32)offset);   /* costs ~1%; silence an msan warning when offset==0 */
1193
1194         /* get matchlength */
1195         length = token & ML_MASK;
1196         if (length == ML_MASK) {
1197             unsigned s;
1198             do {
1199                 s = *ip++;
1200                 if ((endOnInput) && (ip > iend-LASTLITERALS)) goto _output_error;
1201                 length += s;
1202             } while (s==255);
1203             if ((safeDecode) && unlikely((uptrval)(op)+length<(uptrval)op)) goto _output_error;   /* overflow detection */
1204         }
1205         length += MINMATCH;
1206
1207         /* check external dictionary */
1208         if ((dict==usingExtDict) && (match < lowPrefix)) {
1209             if (unlikely(op+length > oend-LASTLITERALS)) goto _output_error;   /* doesn't respect parsing restriction */
1210
1211             if (length <= (size_t)(lowPrefix-match)) {
1212                 /* match can be copied as a single segment from external dictionary */
1213                 memmove(op, dictEnd - (lowPrefix-match), length);
1214                 op += length;
1215             } else {
1216                 /* match encompass external dictionary and current block */
1217                 size_t const copySize = (size_t)(lowPrefix-match);
1218                 size_t const restSize = length - copySize;
1219                 memcpy(op, dictEnd - copySize, copySize);
1220                 op += copySize;
1221                 if (restSize > (size_t)(op-lowPrefix)) {  /* overlap copy */
1222                     BYTE* const endOfMatch = op + restSize;
1223                     const BYTE* copyFrom = lowPrefix;
1224                     while (op < endOfMatch) *op++ = *copyFrom++;
1225                 } else {
1226                     memcpy(op, lowPrefix, restSize);
1227                     op += restSize;
1228             }   }
1229             continue;
1230         }
1231
1232         /* copy match within block */
1233         cpy = op + length;
1234         if (unlikely(offset<8)) {
1235             const int dec64 = dec64table[offset];
1236             op[0] = match[0];
1237             op[1] = match[1];
1238             op[2] = match[2];
1239             op[3] = match[3];
1240             match += dec32table[offset];
1241             memcpy(op+4, match, 4);
1242             match -= dec64;
1243         } else { LZ4_copy8(op, match); match+=8; }
1244         op += 8;
1245
1246         if (unlikely(cpy>oend-12)) {
1247             BYTE* const oCopyLimit = oend-(WILDCOPYLENGTH-1);
1248             if (cpy > oend-LASTLITERALS) goto _output_error;    /* Error : last LASTLITERALS bytes must be literals (uncompressed) */
1249             if (op < oCopyLimit) {
1250                 LZ4_wildCopy(op, match, oCopyLimit);
1251                 match += oCopyLimit - op;
1252                 op = oCopyLimit;
1253             }
1254             while (op<cpy) *op++ = *match++;
1255         } else {
1256             LZ4_copy8(op, match);
1257             if (length>16) LZ4_wildCopy(op+8, match+8, cpy);
1258         }
1259         op=cpy;   /* correction */
1260     }
1261
1262     /* end of decoding */
1263     if (endOnInput)
1264        return (int) (((char*)op)-dest);     /* Nb of output bytes decoded */
1265     else
1266        return (int) (((const char*)ip)-source);   /* Nb of input bytes read */
1267
1268     /* Overflow error detected */
1269 _output_error:
1270     return (int) (-(((const char*)ip)-source))-1;
1271 }
1272
1273
1274 int LZ4_decompress_safe(const char* source, char* dest, int compressedSize, int maxDecompressedSize)
1275 {
1276     return LZ4_decompress_generic(source, dest, compressedSize, maxDecompressedSize, endOnInputSize, full, 0, noDict, (BYTE*)dest, NULL, 0);
1277 }
1278
1279 int LZ4_decompress_safe_partial(const char* source, char* dest, int compressedSize, int targetOutputSize, int maxDecompressedSize)
1280 {
1281     return LZ4_decompress_generic(source, dest, compressedSize, maxDecompressedSize, endOnInputSize, partial, targetOutputSize, noDict, (BYTE*)dest, NULL, 0);
1282 }
1283
1284 int LZ4_decompress_fast(const char* source, char* dest, int originalSize)
1285 {
1286     return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, withPrefix64k, (BYTE*)(dest - 64 KB), NULL, 64 KB);
1287 }
1288
1289
1290 /*===== streaming decompression functions =====*/
1291
1292 LZ4_streamDecode_t* LZ4_createStreamDecode(void)
1293 {
1294     LZ4_streamDecode_t* lz4s = (LZ4_streamDecode_t*) ALLOCATOR(1, sizeof(LZ4_streamDecode_t));
1295     return lz4s;
1296 }
1297
1298 int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream)
1299 {
1300     if (!LZ4_stream) return 0;   /* support free on NULL */
1301     FREEMEM(LZ4_stream);
1302     return 0;
1303 }
1304
1305 /*!
1306  * LZ4_setStreamDecode() :
1307  * Use this function to instruct where to find the dictionary.
1308  * This function is not necessary if previous data is still available where it was decoded.
1309  * Loading a size of 0 is allowed (same effect as no dictionary).
1310  * Return : 1 if OK, 0 if error
1311  */
1312 int LZ4_setStreamDecode (LZ4_streamDecode_t* LZ4_streamDecode, const char* dictionary, int dictSize)
1313 {
1314     LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse;
1315     lz4sd->prefixSize = (size_t) dictSize;
1316     lz4sd->prefixEnd = (const BYTE*) dictionary + dictSize;
1317     lz4sd->externalDict = NULL;
1318     lz4sd->extDictSize  = 0;
1319     return 1;
1320 }
1321
1322 /*
1323 *_continue() :
1324     These decoding functions allow decompression of multiple blocks in "streaming" mode.
1325     Previously decoded blocks must still be available at the memory position where they were decoded.
1326     If it's not possible, save the relevant part of decoded data into a safe buffer,
1327     and indicate where it stands using LZ4_setStreamDecode()
1328 */
1329 int LZ4_decompress_safe_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int compressedSize, int maxOutputSize)
1330 {
1331     LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse;
1332     int result;
1333
1334     if (lz4sd->prefixEnd == (BYTE*)dest) {
1335         result = LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
1336                                         endOnInputSize, full, 0,
1337                                         usingExtDict, lz4sd->prefixEnd - lz4sd->prefixSize, lz4sd->externalDict, lz4sd->extDictSize);
1338         if (result <= 0) return result;
1339         lz4sd->prefixSize += result;
1340         lz4sd->prefixEnd  += result;
1341     } else {
1342         lz4sd->extDictSize = lz4sd->prefixSize;
1343         lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize;
1344         result = LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
1345                                         endOnInputSize, full, 0,
1346                                         usingExtDict, (BYTE*)dest, lz4sd->externalDict, lz4sd->extDictSize);
1347         if (result <= 0) return result;
1348         lz4sd->prefixSize = result;
1349         lz4sd->prefixEnd  = (BYTE*)dest + result;
1350     }
1351
1352     return result;
1353 }
1354
1355 int LZ4_decompress_fast_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int originalSize)
1356 {
1357     LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse;
1358     int result;
1359
1360     if (lz4sd->prefixEnd == (BYTE*)dest) {
1361         result = LZ4_decompress_generic(source, dest, 0, originalSize,
1362                                         endOnOutputSize, full, 0,
1363                                         usingExtDict, lz4sd->prefixEnd - lz4sd->prefixSize, lz4sd->externalDict, lz4sd->extDictSize);
1364         if (result <= 0) return result;
1365         lz4sd->prefixSize += originalSize;
1366         lz4sd->prefixEnd  += originalSize;
1367     } else {
1368         lz4sd->extDictSize = lz4sd->prefixSize;
1369         lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize;
1370         result = LZ4_decompress_generic(source, dest, 0, originalSize,
1371                                         endOnOutputSize, full, 0,
1372                                         usingExtDict, (BYTE*)dest, lz4sd->externalDict, lz4sd->extDictSize);
1373         if (result <= 0) return result;
1374         lz4sd->prefixSize = originalSize;
1375         lz4sd->prefixEnd  = (BYTE*)dest + originalSize;
1376     }
1377
1378     return result;
1379 }
1380
1381
1382 /*
1383 Advanced decoding functions :
1384 *_usingDict() :
1385     These decoding functions work the same as "_continue" ones,
1386     the dictionary must be explicitly provided within parameters
1387 */
1388
1389 FORCE_INLINE int LZ4_decompress_usingDict_generic(const char* source, char* dest, int compressedSize, int maxOutputSize, int safe, const char* dictStart, int dictSize)
1390 {
1391     if (dictSize==0)
1392         return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, noDict, (BYTE*)dest, NULL, 0);
1393     if (dictStart+dictSize == dest) {
1394         if (dictSize >= (int)(64 KB - 1))
1395             return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, withPrefix64k, (BYTE*)dest-64 KB, NULL, 0);
1396         return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, noDict, (BYTE*)dest-dictSize, NULL, 0);
1397     }
1398     return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, usingExtDict, (BYTE*)dest, (const BYTE*)dictStart, dictSize);
1399 }
1400
1401 int LZ4_decompress_safe_usingDict(const char* source, char* dest, int compressedSize, int maxOutputSize, const char* dictStart, int dictSize)
1402 {
1403     return LZ4_decompress_usingDict_generic(source, dest, compressedSize, maxOutputSize, 1, dictStart, dictSize);
1404 }
1405
1406 int LZ4_decompress_fast_usingDict(const char* source, char* dest, int originalSize, const char* dictStart, int dictSize)
1407 {
1408     return LZ4_decompress_usingDict_generic(source, dest, 0, originalSize, 0, dictStart, dictSize);
1409 }
1410
1411 /* debug function */
1412 int LZ4_decompress_safe_forceExtDict(const char* source, char* dest, int compressedSize, int maxOutputSize, const char* dictStart, int dictSize)
1413 {
1414     return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, usingExtDict, (BYTE*)dest, (const BYTE*)dictStart, dictSize);
1415 }
1416
1417
1418 /*=*************************************************
1419 *  Obsolete Functions
1420 ***************************************************/
1421 /* obsolete compression functions */
1422 int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize) { return LZ4_compress_default(source, dest, inputSize, maxOutputSize); }
1423 int LZ4_compress(const char* source, char* dest, int inputSize) { return LZ4_compress_default(source, dest, inputSize, LZ4_compressBound(inputSize)); }
1424 int LZ4_compress_limitedOutput_withState (void* state, const char* src, char* dst, int srcSize, int dstSize) { return LZ4_compress_fast_extState(state, src, dst, srcSize, dstSize, 1); }
1425 int LZ4_compress_withState (void* state, const char* src, char* dst, int srcSize) { return LZ4_compress_fast_extState(state, src, dst, srcSize, LZ4_compressBound(srcSize), 1); }
1426 int LZ4_compress_limitedOutput_continue (LZ4_stream_t* LZ4_stream, const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_fast_continue(LZ4_stream, src, dst, srcSize, maxDstSize, 1); }
1427 int LZ4_compress_continue (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize) { return LZ4_compress_fast_continue(LZ4_stream, source, dest, inputSize, LZ4_compressBound(inputSize), 1); }
1428
1429 /*
1430 These function names are deprecated and should no longer be used.
1431 They are only provided here for compatibility with older user programs.
1432 - LZ4_uncompress is totally equivalent to LZ4_decompress_fast
1433 - LZ4_uncompress_unknownOutputSize is totally equivalent to LZ4_decompress_safe
1434 */
1435 int LZ4_uncompress (const char* source, char* dest, int outputSize) { return LZ4_decompress_fast(source, dest, outputSize); }
1436 int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize) { return LZ4_decompress_safe(source, dest, isize, maxOutputSize); }
1437
1438
1439 /* Obsolete Streaming functions */
1440
1441 int LZ4_sizeofStreamState() { return LZ4_STREAMSIZE; }
1442
1443 static void LZ4_init(LZ4_stream_t* lz4ds, BYTE* base)
1444 {
1445     MEM_INIT(lz4ds, 0, sizeof(LZ4_stream_t));
1446     lz4ds->internal_donotuse.bufferStart = base;
1447 }
1448
1449 int LZ4_resetStreamState(void* state, char* inputBuffer)
1450 {
1451     if ((((uptrval)state) & 3) != 0) return 1;   /* Error : pointer is not aligned on 4-bytes boundary */
1452     LZ4_init((LZ4_stream_t*)state, (BYTE*)inputBuffer);
1453     return 0;
1454 }
1455
1456 void* LZ4_create (char* inputBuffer)
1457 {
1458     LZ4_stream_t* lz4ds = (LZ4_stream_t*)ALLOCATOR(8, sizeof(LZ4_stream_t));
1459     LZ4_init (lz4ds, (BYTE*)inputBuffer);
1460     return lz4ds;
1461 }
1462
1463 char* LZ4_slideInputBuffer (void* LZ4_Data)
1464 {
1465     LZ4_stream_t_internal* ctx = &((LZ4_stream_t*)LZ4_Data)->internal_donotuse;
1466     int dictSize = LZ4_saveDict((LZ4_stream_t*)LZ4_Data, (char*)ctx->bufferStart, 64 KB);
1467     return (char*)(ctx->bufferStart + dictSize);
1468 }
1469
1470 /* Obsolete streaming decompression functions */
1471
1472 int LZ4_decompress_safe_withPrefix64k(const char* source, char* dest, int compressedSize, int maxOutputSize)
1473 {
1474     return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, withPrefix64k, (BYTE*)dest - 64 KB, NULL, 64 KB);
1475 }
1476
1477 int LZ4_decompress_fast_withPrefix64k(const char* source, char* dest, int originalSize)
1478 {
1479     return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, withPrefix64k, (BYTE*)dest - 64 KB, NULL, 64 KB);
1480 }
1481
1482 #endif   /* LZ4_COMMONDEFS_ONLY */