bundles/org.simantics.fastlz/native/lz4.c

   1 /*\r
   2    LZ4 - Fast LZ compression algorithm\r
   3    Copyright (C) 2011-2012, Yann Collet.\r
   4    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)\r
   5 \r
   6    Redistribution and use in source and binary forms, with or without\r
   7    modification, are permitted provided that the following conditions are\r
   8    met:\r
   9 \r
  10        * Redistributions of source code must retain the above copyright\r
  11    notice, this list of conditions and the following disclaimer.\r
  12        * Redistributions in binary form must reproduce the above\r
  13    copyright notice, this list of conditions and the following disclaimer\r
  14    in the documentation and/or other materials provided with the\r
  15    distribution.\r
  16 \r
  17    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS\r
  18    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT\r
  19    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR\r
  20    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT\r
  21    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\r
  22    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT\r
  23    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\r
  24    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\r
  25    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\r
  26    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE\r
  27    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\r
  28 \r
  29    You can contact the author at :\r
  30    - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html\r
  31    - LZ4 source repository : http://code.google.com/p/lz4/\r
  32 */\r
  33 \r
  34 //**************************************\r
  35 // Tuning parameters\r
  36 //**************************************\r
  37 // COMPRESSIONLEVEL :\r
  38 // Increasing this value improves compression ratio\r
  39 // Lowering this value reduces memory usage\r
  40 // Reduced memory usage typically improves speed, due to cache effect (ex : L1 32KB for Intel, L1 64KB for AMD)\r
  41 // Memory usage formula : N->2^(N+2) Bytes (examples : 12 -> 16KB ; 17 -> 512KB)\r
  42 #define COMPRESSIONLEVEL 12\r
  43 \r
  44 // NOTCOMPRESSIBLE_CONFIRMATION :\r
  45 // Decreasing this value will make the algorithm skip faster data segments considered "incompressible"\r
  46 // This may decrease compression ratio dramatically, but will be faster on incompressible data\r
  47 // Increasing this value will make the algorithm search more before declaring a segment "incompressible"\r
  48 // This could improve compression a bit, but will be slower on incompressible data\r
  49 // The default value (6) is recommended\r
  50 #define NOTCOMPRESSIBLE_CONFIRMATION 6\r
  51 \r
  52 // LZ4_COMPRESSMIN :\r
  53 // Compression function will *fail* if it is not successful at compressing input by at least LZ4_COMPRESSMIN bytes\r
  54 // Since the compression function stops working prematurely, it results in a speed gain\r
  55 // The output however is unusable. Compression function result will be zero.\r
  56 // Default : 0 = disabled\r
  57 #define LZ4_COMPRESSMIN 0\r
  58 \r
  59 // BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE :\r
  60 // This will provide a boost to performance for big endian cpu, but the resulting compressed stream will be incompatible with little-endian CPU.\r
  61 // You can set this option to 1 in situations where data will stay within closed environment\r
  62 // This option is useless on Little_Endian CPU (such as x86)\r
  63 //#define BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE 1\r
  64 \r
  65 \r
  66 \r
  67 //**************************************\r
  68 // CPU Feature Detection\r
  69 //**************************************\r
  70 // 32 or 64 bits ?\r
  71 #if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) || defined(__amd64) || defined(__ppc64__) || defined(_WIN64) || defined(__LP64__) || defined(_LP64) )   // Detects 64 bits mode\r
  72 #  define LZ4_ARCH64 1\r
  73 #else\r
  74 #  define LZ4_ARCH64 0\r
  75 #endif\r
  76 \r
  77 // Little Endian or Big Endian ?\r
  78 // Note : overwrite the below #define if you know your architecture endianess\r
  79 #if (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN) || defined(_ARCH_PPC) || defined(__PPC__) || defined(__PPC) || defined(PPC) || defined(__powerpc__) || defined(__powerpc) || defined(powerpc) || ((defined(__BYTE_ORDER__)&&(__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__))) )\r
  80 #  define LZ4_BIG_ENDIAN 1\r
  81 #else\r
  82 // Little Endian assumed. PDP Endian and other very rare endian format are unsupported.\r
  83 #endif\r
  84 \r
  85 // Unaligned memory access is automatically enabled for "common" CPU, such as x86.\r
  86 // For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected\r
  87 // If you know your target CPU supports unaligned memory access, you may want to force this option manually to improve performance\r
  88 #if defined(__ARM_FEATURE_UNALIGNED)\r
  89 #  define LZ4_FORCE_UNALIGNED_ACCESS 1\r
  90 #endif\r
  91 \r
  92 // Define this parameter if your target system or compiler does not support hardware bit count\r
  93 #if defined(_MSC_VER) && defined(_WIN32_WCE)            // Visual Studio for Windows CE does not support Hardware bit count\r
  94 #  define LZ4_FORCE_SW_BITCOUNT\r
  95 #endif\r
  96 \r
  97 \r
  98 //**************************************\r
  99 // Compiler Options\r
 100 //**************************************\r
 101 #if __STDC_VERSION__ >= 199901L // C99\r
 102 /* "restrict" is a known keyword */\r
 103 #else\r
 104 #  define restrict // Disable restrict\r
 105 #endif\r
 106 \r
 107 #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)\r
 108 \r
 109 #ifdef _MSC_VER  // Visual Studio\r
 110 #  define inline __forceinline           // Visual is not C99, but supports some kind of inline\r
 111 #  if LZ4_ARCH64        // 64-bit\r
 112 #    pragma intrinsic(_BitScanForward64) // For Visual 2005\r
 113 #    pragma intrinsic(_BitScanReverse64) // For Visual 2005\r
 114 #  else\r
 115 #    pragma intrinsic(_BitScanForward)   // For Visual 2005\r
 116 #    pragma intrinsic(_BitScanReverse)   // For Visual 2005\r
 117 #  endif\r
 118 #endif\r
 119 \r
 120 #ifdef _MSC_VER\r
 121 #  define lz4_bswap16(x) _byteswap_ushort(x)\r
 122 #else\r
 123 #  define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8)))\r
 124 #endif\r
 125 \r
 126 #if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__)\r
 127 #  define expect(expr,value)    (__builtin_expect ((expr),(value)) )\r
 128 #else\r
 129 #  define expect(expr,value)    (expr)\r
 130 #endif\r
 131 \r
 132 #define likely(expr)     expect((expr) != 0, 1)\r
 133 #define unlikely(expr)   expect((expr) != 0, 0)\r
 134 \r
 135 \r
 136 //**************************************\r
 137 // Includes\r
 138 //**************************************\r
 139 #include <stdlib.h>   // for malloc\r
 140 #include <string.h>   // for memset\r
 141 #include "lz4.h"\r
 142 \r
 143 \r
 144 //**************************************\r
 145 // Basic Types\r
 146 //**************************************\r
 147 #if defined(_MSC_VER)    // Visual Studio does not support 'stdint' natively\r
 148 #  define BYTE  unsigned __int8\r
 149 #  define U16           unsigned __int16\r
 150 #  define U32           unsigned __int32\r
 151 #  define S32           __int32\r
 152 #  define U64           unsigned __int64\r
 153 #else\r
 154 #  include <stdint.h>\r
 155 #  define BYTE  uint8_t\r
 156 #  define U16           uint16_t\r
 157 #  define U32           uint32_t\r
 158 #  define S32           int32_t\r
 159 #  define U64           uint64_t\r
 160 #endif\r
 161 \r
 162 #ifndef LZ4_FORCE_UNALIGNED_ACCESS\r
 163 #  pragma pack(push, 1)\r
 164 #endif\r
 165 \r
 166 typedef struct _U16_S { U16 v; } U16_S;\r
 167 typedef struct _U32_S { U32 v; } U32_S;\r
 168 typedef struct _U64_S { U64 v; } U64_S;\r
 169 \r
 170 #ifndef LZ4_FORCE_UNALIGNED_ACCESS\r
 171 #  pragma pack(pop)\r
 172 #endif\r
 173 \r
 174 #define A64(x) (((U64_S *)(x))->v)\r
 175 #define A32(x) (((U32_S *)(x))->v)\r
 176 #define A16(x) (((U16_S *)(x))->v)\r
 177 \r
 178 \r
 179 //**************************************\r
 180 // Constants\r
 181 //**************************************\r
 182 #define MINMATCH 4\r
 183 \r
 184 #define HASH_LOG COMPRESSIONLEVEL\r
 185 #define HASHTABLESIZE (1 << HASH_LOG)\r
 186 #define HASH_MASK (HASHTABLESIZE - 1)\r
 187 \r
 188 #define SKIPSTRENGTH (NOTCOMPRESSIBLE_CONFIRMATION>2?NOTCOMPRESSIBLE_CONFIRMATION:2)\r
 189 #define STACKLIMIT 13\r
 190 #define HEAPMODE (HASH_LOG>STACKLIMIT)  // Defines if memory is allocated into the stack (local variable), or into the heap (malloc()).\r
 191 #define COPYLENGTH 8\r
 192 #define LASTLITERALS 5\r
 193 #define MFLIMIT (COPYLENGTH+MINMATCH)\r
 194 #define MINLENGTH (MFLIMIT+1)\r
 195 \r
 196 #define MAXD_LOG 16\r
 197 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1)\r
 198 \r
 199 #define ML_BITS 4\r
 200 #define ML_MASK ((1U<<ML_BITS)-1)\r
 201 #define RUN_BITS (8-ML_BITS)\r
 202 #define RUN_MASK ((1U<<RUN_BITS)-1)\r
 203 \r
 204 \r
 205 //**************************************\r
 206 // Architecture-specific macros\r
 207 //**************************************\r
 208 #if LZ4_ARCH64  // 64-bit\r
 209 #  define STEPSIZE 8\r
 210 #  define UARCH U64\r
 211 #  define AARCH A64\r
 212 #  define LZ4_COPYSTEP(s,d)             A64(d) = A64(s); d+=8; s+=8;\r
 213 #  define LZ4_COPYPACKET(s,d)           LZ4_COPYSTEP(s,d)\r
 214 #  define LZ4_SECURECOPY(s,d,e) if (d<e) LZ4_WILDCOPY(s,d,e)\r
 215 #  define HTYPE U32\r
 216 #  define INITBASE(base)                        const BYTE* const base = ip\r
 217 #else           // 32-bit\r
 218 #  define STEPSIZE 4\r
 219 #  define UARCH U32\r
 220 #  define AARCH A32\r
 221 #  define LZ4_COPYSTEP(s,d)             A32(d) = A32(s); d+=4; s+=4;\r
 222 #  define LZ4_COPYPACKET(s,d)           LZ4_COPYSTEP(s,d); LZ4_COPYSTEP(s,d);\r
 223 #  define LZ4_SECURECOPY                        LZ4_WILDCOPY\r
 224 #  define HTYPE const BYTE*\r
 225 #  define INITBASE(base)                        const int base = 0\r
 226 #endif\r
 227 \r
 228 #if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE))\r
 229 #  define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; }\r
 230 #  define LZ4_WRITE_LITTLEENDIAN_16(p,i)  { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p+=2; }\r
 231 #else           // Little Endian\r
 232 #  define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); }\r
 233 #  define LZ4_WRITE_LITTLEENDIAN_16(p,v)  { A16(p) = v; p+=2; }\r
 234 #endif\r
 235 \r
 236 \r
 237 //**************************************\r
 238 // Local structures\r
 239 //**************************************\r
 240 struct refTables\r
 241 {\r
 242         HTYPE hashTable[HASHTABLESIZE];\r
 243 };\r
 244 \r
 245 \r
 246 //**************************************\r
 247 // Macros\r
 248 //**************************************\r
 249 #define LZ4_HASH_FUNCTION(i)    (((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG))\r
 250 #define LZ4_HASH_VALUE(p)               LZ4_HASH_FUNCTION(A32(p))\r
 251 #define LZ4_WILDCOPY(s,d,e)             do { LZ4_COPYPACKET(s,d) } while (d<e);\r
 252 #define LZ4_BLINDCOPY(s,d,l)    { BYTE* e=(d)+l; LZ4_WILDCOPY(s,d,e); d=e; }\r
 253 \r
 254 \r
 255 //****************************\r
 256 // Private functions\r
 257 //****************************\r
 258 #if LZ4_ARCH64\r
 259 \r
 260 inline static int LZ4_NbCommonBytes (register U64 val)\r
 261 {\r
 262 #if defined(LZ4_BIG_ENDIAN)\r
 263     #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 264     unsigned long r = 0;\r
 265     _BitScanReverse64( &r, val );\r
 266     return (int)(r>>3);\r
 267     #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 268     return (__builtin_clzll(val) >> 3);\r
 269     #else\r
 270         int r;\r
 271         if (!(val>>32)) { r=4; } else { r=0; val>>=32; }\r
 272         if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }\r
 273         r += (!val);\r
 274         return r;\r
 275     #endif\r
 276 #else\r
 277     #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 278     unsigned long r = 0;\r
 279     _BitScanForward64( &r, val );\r
 280     return (int)(r>>3);\r
 281     #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 282     return (__builtin_ctzll(val) >> 3);\r
 283     #else\r
 284         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 };\r
 285         return DeBruijnBytePos[((U64)((val & -val) * 0x0218A392CDABBD3F)) >> 58];\r
 286     #endif\r
 287 #endif\r
 288 }\r
 289 \r
 290 #else\r
 291 \r
 292 inline static int LZ4_NbCommonBytes (register U32 val)\r
 293 {\r
 294 #if defined(LZ4_BIG_ENDIAN)\r
 295     #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 296     unsigned long r = 0;\r
 297     _BitScanReverse( &r, val );\r
 298     return (int)(r>>3);\r
 299     #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 300     return (__builtin_clz(val) >> 3);\r
 301     #else\r
 302         int r;\r
 303         if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }\r
 304         r += (!val);\r
 305         return r;\r
 306     #endif\r
 307 #else\r
 308     #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 309     unsigned long r = 0;\r
 310     _BitScanForward( &r, val );\r
 311     return (int)(r>>3);\r
 312     #elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 313     return (__builtin_ctz(val) >> 3);\r
 314     #else\r
 315         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 };\r
 316         return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];\r
 317     #endif\r
 318 #endif\r
 319 }\r
 320 \r
 321 #endif\r
 322 \r
 323 \r
 324 //****************************\r
 325 // Public functions\r
 326 //****************************\r
 327 \r
 328 int LZ4_compressBound(int isize)\r
 329 {\r
 330         return (isize + (isize/255) + 16);\r
 331 }\r
 332 \r
 333 \r
 334 \r
 335 //******************************\r
 336 // Compression functions\r
 337 //******************************\r
 338 \r
 339 int LZ4_compressCtx(void** ctx,\r
 340                                  const char* source,\r
 341                                  char* dest,\r
 342                                  int isize)\r
 343 {\r
 344 #if HEAPMODE\r
 345         struct refTables *srt = (struct refTables *) (*ctx);\r
 346         HTYPE* HashTable;\r
 347 #else\r
 348         HTYPE HashTable[HASHTABLESIZE] = {0};\r
 349 #endif\r
 350 \r
 351         const BYTE* ip = (BYTE*) source;\r
 352         INITBASE(base);\r
 353         const BYTE* anchor = ip;\r
 354         const BYTE* const iend = ip + isize;\r
 355         const BYTE* const mflimit = iend - MFLIMIT;\r
 356 #define matchlimit (iend - LASTLITERALS)\r
 357 \r
 358         BYTE* op = (BYTE*) dest;\r
 359 \r
 360         int len, length;\r
 361         const int skipStrength = SKIPSTRENGTH;\r
 362         U32 forwardH;\r
 363 \r
 364 \r
 365         // Init\r
 366         if (isize<MINLENGTH) goto _last_literals;\r
 367 #if HEAPMODE\r
 368         if (*ctx == NULL)\r
 369         {\r
 370                 srt = (struct refTables *) malloc ( sizeof(struct refTables) );\r
 371                 *ctx = (void*) srt;\r
 372         }\r
 373         HashTable = (HTYPE*)(srt->hashTable);\r
 374         memset((void*)HashTable, 0, sizeof(srt->hashTable));\r
 375 #else\r
 376         (void) ctx;\r
 377 #endif\r
 378 \r
 379 \r
 380         // First Byte\r
 381         HashTable[LZ4_HASH_VALUE(ip)] = ip - base;\r
 382         ip++; forwardH = LZ4_HASH_VALUE(ip);\r
 383 \r
 384         // Main Loop\r
 385     for ( ; ; )\r
 386         {\r
 387                 int findMatchAttempts = (1U << skipStrength) + 3;\r
 388                 const BYTE* forwardIp = ip;\r
 389                 const BYTE* ref;\r
 390                 BYTE* token;\r
 391 \r
 392                 // Find a match\r
 393                 do {\r
 394                         U32 h = forwardH;\r
 395                         int step = findMatchAttempts++ >> skipStrength;\r
 396                         ip = forwardIp;\r
 397                         forwardIp = ip + step;\r
 398 \r
 399                         if unlikely(forwardIp > mflimit) { goto _last_literals; }\r
 400 \r
 401                         forwardH = LZ4_HASH_VALUE(forwardIp);\r
 402                         ref = base + HashTable[h];\r
 403                         HashTable[h] = ip - base;\r
 404 \r
 405                 } while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip)));\r
 406 \r
 407                 // Catch up\r
 408                 while ((ip>anchor) && (ref>(BYTE*)source) && unlikely(ip[-1]==ref[-1])) { ip--; ref--; }\r
 409 \r
 410                 // Encode Literal length\r
 411                 length = ip - anchor;\r
 412                 token = op++;\r
 413                 if (length>=(int)RUN_MASK) { *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *op++ = 255; *op++ = (BYTE)len; }\r
 414                 else *token = (length<<ML_BITS);\r
 415 \r
 416                 // Copy Literals\r
 417                 LZ4_BLINDCOPY(anchor, op, length);\r
 418 \r
 419 _next_match:\r
 420                 // Encode Offset\r
 421                 LZ4_WRITE_LITTLEENDIAN_16(op,ip-ref);\r
 422 \r
 423                 // Start Counting\r
 424                 ip+=MINMATCH; ref+=MINMATCH;   // MinMatch verified\r
 425                 anchor = ip;\r
 426                 while likely(ip<matchlimit-(STEPSIZE-1))\r
 427                 {\r
 428                         UARCH diff = AARCH(ref) ^ AARCH(ip);\r
 429                         if (!diff) { ip+=STEPSIZE; ref+=STEPSIZE; continue; }\r
 430                         ip += LZ4_NbCommonBytes(diff);\r
 431                         goto _endCount;\r
 432                 }\r
 433                 if (LZ4_ARCH64) if ((ip<(matchlimit-3)) && (A32(ref) == A32(ip))) { ip+=4; ref+=4; }\r
 434                 if ((ip<(matchlimit-1)) && (A16(ref) == A16(ip))) { ip+=2; ref+=2; }\r
 435                 if ((ip<matchlimit) && (*ref == *ip)) ip++;\r
 436 _endCount:\r
 437 \r
 438                 // Encode MatchLength\r
 439                 len = (ip - anchor);\r
 440                 if (len>=(int)ML_MASK) { *token+=ML_MASK; len-=ML_MASK; for(; len > 509 ; len-=510) { *op++ = 255; *op++ = 255; } if (len > 254) { len-=255; *op++ = 255; } *op++ = (BYTE)len; }\r
 441                 else *token += len;\r
 442 \r
 443                 // Test end of chunk\r
 444                 if (ip > mflimit) { anchor = ip;  break; }\r
 445 \r
 446                 // Fill table\r
 447                 HashTable[LZ4_HASH_VALUE(ip-2)] = ip - 2 - base;\r
 448 \r
 449                 // Test next position\r
 450                 ref = base + HashTable[LZ4_HASH_VALUE(ip)];\r
 451                 HashTable[LZ4_HASH_VALUE(ip)] = ip - base;\r
 452                 if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) { token = op++; *token=0; goto _next_match; }\r
 453 \r
 454                 // Prepare next loop\r
 455                 anchor = ip++;\r
 456                 forwardH = LZ4_HASH_VALUE(ip);\r
 457         }\r
 458 \r
 459 _last_literals:\r
 460         // Encode Last Literals\r
 461         {\r
 462                 int lastRun = iend - anchor;\r
 463                 if ((LZ4_COMPRESSMIN>0) && (((op - (BYTE*)dest) + lastRun + 1 + ((lastRun-15)/255)) > isize - LZ4_COMPRESSMIN)) return 0;\r
 464                 if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }\r
 465                 else *op++ = (lastRun<<ML_BITS);\r
 466                 memcpy(op, anchor, iend - anchor);\r
 467                 op += iend-anchor;\r
 468         }\r
 469 \r
 470         // End\r
 471         return (int) (((char*)op)-dest);\r
 472 }\r
 473 \r
 474 \r
 475 \r
 476 // Note : this function is valid only if isize < LZ4_64KLIMIT\r
 477 #define LZ4_64KLIMIT ((1<<16) + (MFLIMIT-1))\r
 478 #define HASHLOG64K (HASH_LOG+1)\r
 479 #define HASH64KTABLESIZE (1U<<HASHLOG64K)\r
 480 #define LZ4_HASH64K_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-HASHLOG64K))\r
 481 #define LZ4_HASH64K_VALUE(p)    LZ4_HASH64K_FUNCTION(A32(p))\r
 482 int LZ4_compress64kCtx(void** ctx,\r
 483                                  const char* source,\r
 484                                  char* dest,\r
 485                                  int isize)\r
 486 {\r
 487 #if HEAPMODE\r
 488         struct refTables *srt = (struct refTables *) (*ctx);\r
 489         U16* HashTable;\r
 490 #else\r
 491         U16 HashTable[HASH64KTABLESIZE] = {0};\r
 492 #endif\r
 493 \r
 494         const BYTE* ip = (BYTE*) source;\r
 495         const BYTE* anchor = ip;\r
 496         const BYTE* const base = ip;\r
 497         const BYTE* const iend = ip + isize;\r
 498         const BYTE* const mflimit = iend - MFLIMIT;\r
 499 #define matchlimit (iend - LASTLITERALS)\r
 500 \r
 501         BYTE* op = (BYTE*) dest;\r
 502 \r
 503         int len, length;\r
 504         const int skipStrength = SKIPSTRENGTH;\r
 505         U32 forwardH;\r
 506 \r
 507 \r
 508         // Init\r
 509         if (isize<MINLENGTH) goto _last_literals;\r
 510 #if HEAPMODE\r
 511         if (*ctx == NULL)\r
 512         {\r
 513                 srt = (struct refTables *) malloc ( sizeof(struct refTables) );\r
 514                 *ctx = (void*) srt;\r
 515         }\r
 516         HashTable = (U16*)(srt->hashTable);\r
 517         memset((void*)HashTable, 0, sizeof(srt->hashTable));\r
 518 #else\r
 519         (void) ctx;\r
 520 #endif\r
 521 \r
 522 \r
 523         // First Byte\r
 524         ip++; forwardH = LZ4_HASH64K_VALUE(ip);\r
 525 \r
 526         // Main Loop\r
 527     for ( ; ; )\r
 528         {\r
 529                 int findMatchAttempts = (1U << skipStrength) + 3;\r
 530                 const BYTE* forwardIp = ip;\r
 531                 const BYTE* ref;\r
 532                 BYTE* token;\r
 533 \r
 534                 // Find a match\r
 535                 do {\r
 536                         U32 h = forwardH;\r
 537                         int step = findMatchAttempts++ >> skipStrength;\r
 538                         ip = forwardIp;\r
 539                         forwardIp = ip + step;\r
 540 \r
 541                         if (forwardIp > mflimit) { goto _last_literals; }\r
 542 \r
 543                         forwardH = LZ4_HASH64K_VALUE(forwardIp);\r
 544                         ref = base + HashTable[h];\r
 545                         HashTable[h] = ip - base;\r
 546 \r
 547                 } while (A32(ref) != A32(ip));\r
 548 \r
 549                 // Catch up\r
 550                 while ((ip>anchor) && (ref>(BYTE*)source) && (ip[-1]==ref[-1])) { ip--; ref--; }\r
 551 \r
 552                 // Encode Literal length\r
 553                 length = ip - anchor;\r
 554                 token = op++;\r
 555                 if (length>=(int)RUN_MASK) { *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *op++ = 255; *op++ = (BYTE)len; }\r
 556                 else *token = (length<<ML_BITS);\r
 557 \r
 558                 // Copy Literals\r
 559                 LZ4_BLINDCOPY(anchor, op, length);\r
 560 \r
 561 _next_match:\r
 562                 // Encode Offset\r
 563                 LZ4_WRITE_LITTLEENDIAN_16(op,ip-ref);\r
 564 \r
 565                 // Start Counting\r
 566                 ip+=MINMATCH; ref+=MINMATCH;   // MinMatch verified\r
 567                 anchor = ip;\r
 568                 while (ip<matchlimit-(STEPSIZE-1))\r
 569                 {\r
 570                         UARCH diff = AARCH(ref) ^ AARCH(ip);\r
 571                         if (!diff) { ip+=STEPSIZE; ref+=STEPSIZE; continue; }\r
 572                         ip += LZ4_NbCommonBytes(diff);\r
 573                         goto _endCount;\r
 574                 }\r
 575                 if (LZ4_ARCH64) if ((ip<(matchlimit-3)) && (A32(ref) == A32(ip))) { ip+=4; ref+=4; }\r
 576                 if ((ip<(matchlimit-1)) && (A16(ref) == A16(ip))) { ip+=2; ref+=2; }\r
 577                 if ((ip<matchlimit) && (*ref == *ip)) ip++;\r
 578 _endCount:\r
 579 \r
 580                 // Encode MatchLength\r
 581                 len = (ip - anchor);\r
 582                 if (len>=(int)ML_MASK) { *token+=ML_MASK; len-=ML_MASK; for(; len > 509 ; len-=510) { *op++ = 255; *op++ = 255; } if (len > 254) { len-=255; *op++ = 255; } *op++ = (BYTE)len; }\r
 583                 else *token += len;\r
 584 \r
 585                 // Test end of chunk\r
 586                 if (ip > mflimit) { anchor = ip;  break; }\r
 587 \r
 588                 // Fill table\r
 589                 HashTable[LZ4_HASH64K_VALUE(ip-2)] = ip - 2 - base;\r
 590 \r
 591                 // Test next position\r
 592                 ref = base + HashTable[LZ4_HASH64K_VALUE(ip)];\r
 593                 HashTable[LZ4_HASH64K_VALUE(ip)] = ip - base;\r
 594                 if (A32(ref) == A32(ip)) { token = op++; *token=0; goto _next_match; }\r
 595 \r
 596                 // Prepare next loop\r
 597                 anchor = ip++;\r
 598                 forwardH = LZ4_HASH64K_VALUE(ip);\r
 599         }\r
 600 \r
 601 _last_literals:\r
 602         // Encode Last Literals\r
 603         {\r
 604                 int lastRun = iend - anchor;\r
 605                 if ((LZ4_COMPRESSMIN>0) && (((op - (BYTE*)dest) + lastRun + 1 + ((lastRun-15)/255)) > isize - LZ4_COMPRESSMIN)) return 0;\r
 606                 if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }\r
 607                 else *op++ = (lastRun<<ML_BITS);\r
 608                 memcpy(op, anchor, iend - anchor);\r
 609                 op += iend-anchor;\r
 610         }\r
 611 \r
 612         // End\r
 613         return (int) (((char*)op)-dest);\r
 614 }\r
 615 \r
 616 \r
 617 \r
 618 int LZ4_compress(const char* source,\r
 619                                  char* dest,\r
 620                                  int isize)\r
 621 {\r
 622 #if HEAPMODE\r
 623         void* ctx = malloc(sizeof(struct refTables));\r
 624         int result;\r
 625         if (isize < LZ4_64KLIMIT)\r
 626                 result = LZ4_compress64kCtx(&ctx, source, dest, isize);\r
 627         else result = LZ4_compressCtx(&ctx, source, dest, isize);\r
 628         free(ctx);\r
 629         return result;\r
 630 #else\r
 631         if (isize < (int)LZ4_64KLIMIT) return LZ4_compress64kCtx(NULL, source, dest, isize);\r
 632         return LZ4_compressCtx(NULL, source, dest, isize);\r
 633 #endif\r
 634 }\r
 635 \r
 636 \r
 637 \r
 638 \r
 639 //****************************\r
 640 // Decompression functions\r
 641 //****************************\r
 642 \r
 643 // Note : The decoding functions LZ4_uncompress() and LZ4_uncompress_unknownOutputSize()\r
 644 //              are safe against "buffer overflow" attack type.\r
 645 //              They will never write nor read outside of the provided output buffers.\r
 646 //      LZ4_uncompress_unknownOutputSize() also insures that it will never read outside of the input buffer.\r
 647 //              A corrupted input will produce an error result, a negative int, indicating the position of the error within input stream.\r
 648 \r
 649 int LZ4_uncompress(const char* source,\r
 650                                  char* dest,\r
 651                                  int osize)\r
 652 {\r
 653         // Local Variables\r
 654         const BYTE* restrict ip = (const BYTE*) source;\r
 655         const BYTE* restrict ref;\r
 656 \r
 657         BYTE* restrict op = (BYTE*) dest;\r
 658         BYTE* const oend = op + osize;\r
 659         BYTE* cpy;\r
 660 \r
 661         BYTE token;\r
 662 \r
 663         int     len, length;\r
 664         size_t dec[] ={0, 3, 2, 3, 0, 0, 0, 0};\r
 665 \r
 666 \r
 667         // Main Loop\r
 668         while (1)\r
 669         {\r
 670                 // get runlength\r
 671                 token = *ip++;\r
 672                 if ((length=(token>>ML_BITS)) == RUN_MASK)  { for (;(len=*ip++)==255;length+=255){} length += len; }\r
 673 \r
 674                 // copy literals\r
 675                 cpy = op+length;\r
 676                 if unlikely(cpy>oend-COPYLENGTH)\r
 677                 {\r
 678                         if (cpy > oend) goto _output_error;          // Error : request to write beyond destination buffer\r
 679                         memcpy(op, ip, length);\r
 680                         ip += length;\r
 681                         break;    // Necessarily EOF\r
 682                 }\r
 683                 LZ4_WILDCOPY(ip, op, cpy); ip -= (op-cpy); op = cpy;\r
 684 \r
 685                 // get offset\r
 686                 LZ4_READ_LITTLEENDIAN_16(ref,cpy,ip); ip+=2;\r
 687                 if (ref < (BYTE* const)dest) goto _output_error;   // Error : offset create reference outside destination buffer\r
 688 \r
 689                 // get matchlength\r
 690                 if ((length=(token&ML_MASK)) == ML_MASK) { for (;*ip==255;length+=255) {ip++;} length += *ip++; }\r
 691 \r
 692                 // copy repeated sequence\r
 693                 if unlikely(op-ref<STEPSIZE)\r
 694                 {\r
 695 #if LZ4_ARCH64\r
 696                         size_t dec2table[]={0, 0, 0, -1, 0, 1, 2, 3};\r
 697                         size_t dec2 = dec2table[op-ref];\r
 698 #else\r
 699                         const int dec2 = 0;\r
 700 #endif\r
 701                         *op++ = *ref++;\r
 702                         *op++ = *ref++;\r
 703                         *op++ = *ref++;\r
 704                         *op++ = *ref++;\r
 705                         ref -= dec[op-ref];\r
 706                         A32(op)=A32(ref); op += STEPSIZE-4;\r
 707                         ref -= dec2;\r
 708                 } else { LZ4_COPYSTEP(ref,op); }\r
 709                 cpy = op + length - (STEPSIZE-4);\r
 710                 if (cpy>oend-COPYLENGTH)\r
 711                 {\r
 712                         if (cpy > oend) goto _output_error;             // Error : request to write beyond destination buffer\r
 713                         LZ4_SECURECOPY(ref, op, (oend-COPYLENGTH));\r
 714                         while(op<cpy) *op++=*ref++;\r
 715                         op=cpy;\r
 716                         if (op == oend) break;    // Check EOF (should never happen, since last 5 bytes are supposed to be literals)\r
 717                         continue;\r
 718                 }\r
 719                 LZ4_SECURECOPY(ref, op, cpy);\r
 720                 op=cpy;         // correction\r
 721         }\r
 722 \r
 723         // end of decoding\r
 724         return (int) (((char*)ip)-source);\r
 725 \r
 726         // write overflow error detected\r
 727 _output_error:\r
 728         return (int) (-(((char*)ip)-source));\r
 729 }\r
 730 \r
 731 \r
 732 int LZ4_uncompress_unknownOutputSize(\r
 733                                 const char* source,\r
 734                                 char* dest,\r
 735                                 int isize,\r
 736                                 int maxOutputSize)\r
 737 {\r
 738         // Local Variables\r
 739         const BYTE* restrict ip = (const BYTE*) source;\r
 740         const BYTE* const iend = ip + isize;\r
 741         const BYTE* restrict ref;\r
 742 \r
 743         BYTE* restrict op = (BYTE*) dest;\r
 744         BYTE* const oend = op + maxOutputSize;\r
 745         BYTE* cpy;\r
 746 \r
 747         size_t dec[] ={0, 3, 2, 3, 0, 0, 0, 0};\r
 748 \r
 749 \r
 750         // Main Loop\r
 751         while (ip<iend)\r
 752         {\r
 753                 BYTE token;\r
 754                 int length;\r
 755 \r
 756                 // get runlength\r
 757                 token = *ip++;\r
 758                 if ((length=(token>>ML_BITS)) == RUN_MASK) { int s=255; while ((ip<iend) && (s==255)) { s=*ip++; length += s; } }\r
 759 \r
 760                 // copy literals\r
 761                 cpy = op+length;\r
 762                 if ((cpy>oend-COPYLENGTH) || (ip+length>iend-COPYLENGTH))\r
 763                 {\r
 764                         if (cpy > oend) goto _output_error;          // Error : request to write beyond destination buffer\r
 765                         if (ip+length > iend) goto _output_error;    // Error : request to read beyond source buffer\r
 766                         memcpy(op, ip, length);\r
 767                         op += length;\r
 768                         ip += length;\r
 769                         if (ip<iend) goto _output_error;             // Error : LZ4 format violation\r
 770                         break;    // Necessarily EOF, due to parsing restrictions\r
 771                 }\r
 772                 LZ4_WILDCOPY(ip, op, cpy); ip -= (op-cpy); op = cpy;\r
 773 \r
 774                 // get offset\r
 775                 LZ4_READ_LITTLEENDIAN_16(ref,cpy,ip); ip+=2;\r
 776                 if (ref < (BYTE* const)dest) goto _output_error;   // Error : offset creates reference outside of destination buffer\r
 777 \r
 778                 // get matchlength\r
 779                 if ((length=(token&ML_MASK)) == ML_MASK) { while (ip<iend) { int s = *ip++; length +=s; if (s==255) continue; break; } }\r
 780 \r
 781                 // copy repeated sequence\r
 782                 if unlikely(op-ref<STEPSIZE)\r
 783                 {\r
 784 #if LZ4_ARCH64\r
 785                         size_t dec2table[]={0, 0, 0, -1, 0, 1, 2, 3};\r
 786                         size_t dec2 = dec2table[op-ref];\r
 787 #else\r
 788                         const int dec2 = 0;\r
 789 #endif\r
 790                         *op++ = *ref++;\r
 791                         *op++ = *ref++;\r
 792                         *op++ = *ref++;\r
 793                         *op++ = *ref++;\r
 794                         ref -= dec[op-ref];\r
 795                         A32(op)=A32(ref); op += STEPSIZE-4;\r
 796                         ref -= dec2;\r
 797                 } else { LZ4_COPYSTEP(ref,op); }\r
 798                 cpy = op + length - (STEPSIZE-4);\r
 799                 if (cpy>oend-COPYLENGTH)\r
 800                 {\r
 801                         if (cpy > oend) goto _output_error;           // Error : request to write outside of destination buffer\r
 802                         LZ4_SECURECOPY(ref, op, (oend-COPYLENGTH));\r
 803                         while(op<cpy) *op++=*ref++;\r
 804                         op=cpy;\r
 805                         if (op == oend) break;    // Check EOF (should never happen, since last 5 bytes are supposed to be literals)\r
 806                         continue;\r
 807                 }\r
 808                 LZ4_SECURECOPY(ref, op, cpy);\r
 809                 op=cpy;         // correction\r
 810         }\r
 811 \r
 812         // end of decoding\r
 813         return (int) (((char*)op)-dest);\r
 814 \r
 815         // write overflow error detected\r
 816 _output_error:\r
 817         return (int) (-(((char*)ip)-source));\r
 818 }\r
 819 \r