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

   1 /*\r
   2    LZ4 HC - High Compression Mode of LZ4\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 //**************************************\r
  36 // CPU Feature Detection\r
  37 //**************************************\r
  38 // 32 or 64 bits ?\r
  39 #if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) || defined(__amd64) || defined(__ppc64__) || defined(_WIN64) || defined(__LP64__) || defined(_LP64) )   // Detects 64 bits mode\r
  40 #define LZ4_ARCH64 1\r
  41 #else\r
  42 #define LZ4_ARCH64 0\r
  43 #endif\r
  44 \r
  45 // Little Endian or Big Endian ? \r
  46 #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
  47 #define LZ4_BIG_ENDIAN 1\r
  48 #else\r
  49 // Little Endian assumed. PDP Endian and other very rare endian format are unsupported.\r
  50 #endif\r
  51 \r
  52 // Unaligned memory access is automatically enabled for "common" CPU, such as x86.\r
  53 // For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected\r
  54 // If you know your target CPU supports unaligned memory access, you may want to force this option manually to improve performance\r
  55 #if defined(__ARM_FEATURE_UNALIGNED)\r
  56 #define LZ4_FORCE_UNALIGNED_ACCESS 1\r
  57 #endif\r
  58 \r
  59 \r
  60 //**************************************\r
  61 // Compiler Options\r
  62 //**************************************\r
  63 #if __STDC_VERSION__ >= 199901L    // C99\r
  64   /* "restrict" is a known keyword */\r
  65 #else\r
  66 #define restrict  // Disable restrict\r
  67 #endif\r
  68 \r
  69 #ifdef _MSC_VER\r
  70 #define inline __forceinline    // Visual is not C99, but supports some kind of inline\r
  71 #endif\r
  72 \r
  73 #ifdef _MSC_VER  // Visual Studio\r
  74 #define bswap16(x) _byteswap_ushort(x)\r
  75 #else\r
  76 #define bswap16(x)  ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8)))\r
  77 #endif\r
  78 \r
  79 \r
  80 //**************************************\r
  81 // Includes\r
  82 //**************************************\r
  83 #include <stdlib.h>   // calloc, free\r
  84 #include <string.h>   // memset, memcpy\r
  85 #include "lz4hc.h"\r
  86 \r
  87 #define ALLOCATOR(s) calloc(1,s)\r
  88 #define FREEMEM free\r
  89 #define MEM_INIT memset\r
  90 \r
  91 \r
  92 //**************************************\r
  93 // Basic Types\r
  94 //**************************************\r
  95 #if defined(_MSC_VER)    // Visual Studio does not support 'stdint' natively\r
  96 #define BYTE    unsigned __int8\r
  97 #define U16             unsigned __int16\r
  98 #define U32             unsigned __int32\r
  99 #define S32             __int32\r
 100 #define U64             unsigned __int64\r
 101 #else\r
 102 #include <stdint.h>\r
 103 #define BYTE    uint8_t\r
 104 #define U16             uint16_t\r
 105 #define U32             uint32_t\r
 106 #define S32             int32_t\r
 107 #define U64             uint64_t\r
 108 #endif\r
 109 \r
 110 #ifndef LZ4_FORCE_UNALIGNED_ACCESS\r
 111 #pragma pack(push, 1) \r
 112 #endif\r
 113 \r
 114 typedef struct _U16_S { U16 v; } U16_S;\r
 115 typedef struct _U32_S { U32 v; } U32_S;\r
 116 typedef struct _U64_S { U64 v; } U64_S;\r
 117 \r
 118 #ifndef LZ4_FORCE_UNALIGNED_ACCESS\r
 119 #pragma pack(pop) \r
 120 #endif\r
 121 \r
 122 #define A64(x) (((U64_S *)(x))->v)\r
 123 #define A32(x) (((U32_S *)(x))->v)\r
 124 #define A16(x) (((U16_S *)(x))->v)\r
 125 \r
 126 \r
 127 //**************************************\r
 128 // Constants\r
 129 //**************************************\r
 130 #define MINMATCH 4\r
 131 \r
 132 #define DICTIONARY_LOGSIZE 16\r
 133 #define MAXD (1<<DICTIONARY_LOGSIZE)\r
 134 #define MAXD_MASK ((U32)(MAXD - 1))\r
 135 #define MAX_DISTANCE (MAXD - 1)\r
 136 \r
 137 #define HASH_LOG (DICTIONARY_LOGSIZE-1)\r
 138 #define HASHTABLESIZE (1 << HASH_LOG)\r
 139 #define HASH_MASK (HASHTABLESIZE - 1)\r
 140 \r
 141 #define MAX_NB_ATTEMPTS 256\r
 142 \r
 143 #define ML_BITS  4\r
 144 #define ML_MASK  (size_t)((1U<<ML_BITS)-1)\r
 145 #define RUN_BITS (8-ML_BITS)\r
 146 #define RUN_MASK ((1U<<RUN_BITS)-1)\r
 147 \r
 148 #define COPYLENGTH 8\r
 149 #define LASTLITERALS 5\r
 150 #define MFLIMIT (COPYLENGTH+MINMATCH)\r
 151 #define MINLENGTH (MFLIMIT+1)\r
 152 #define OPTIMAL_ML (int)((ML_MASK-1)+MINMATCH)\r
 153 \r
 154 \r
 155 //**************************************\r
 156 // Architecture-specific macros\r
 157 //**************************************\r
 158 #if LZ4_ARCH64  // 64-bit\r
 159 #define STEPSIZE 8\r
 160 #define LZ4_COPYSTEP(s,d)               A64(d) = A64(s); d+=8; s+=8;\r
 161 #define LZ4_COPYPACKET(s,d)             LZ4_COPYSTEP(s,d)\r
 162 #define UARCH U64\r
 163 #define AARCH A64\r
 164 #define HTYPE                                   U32\r
 165 #define INITBASE(b,s)                   const BYTE* const b = s\r
 166 #else           // 32-bit\r
 167 #define STEPSIZE 4\r
 168 #define LZ4_COPYSTEP(s,d)               A32(d) = A32(s); d+=4; s+=4;\r
 169 #define LZ4_COPYPACKET(s,d)             LZ4_COPYSTEP(s,d); LZ4_COPYSTEP(s,d);\r
 170 #define UARCH U32\r
 171 #define AARCH A32\r
 172 #define HTYPE                                   const BYTE*\r
 173 #define INITBASE(b,s)               const int b = 0\r
 174 #endif\r
 175 \r
 176 #if defined(LZ4_BIG_ENDIAN)\r
 177 #define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); v = bswap16(v); d = (s) - v; }\r
 178 #define LZ4_WRITE_LITTLEENDIAN_16(p,i)  { U16 v = (U16)(i); v = bswap16(v); A16(p) = v; p+=2; }\r
 179 #else           // Little Endian\r
 180 #define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); }\r
 181 #define LZ4_WRITE_LITTLEENDIAN_16(p,v)  { A16(p) = v; p+=2; }\r
 182 #endif\r
 183 \r
 184 \r
 185 //************************************************************\r
 186 // Local Types\r
 187 //************************************************************\r
 188 typedef struct \r
 189 {\r
 190         const BYTE* base;\r
 191         HTYPE hashTable[HASHTABLESIZE];\r
 192         U16 chainTable[MAXD];\r
 193         const BYTE* nextToUpdate;\r
 194 } LZ4HC_Data_Structure;\r
 195 \r
 196 \r
 197 //**************************************\r
 198 // Macros\r
 199 //**************************************\r
 200 #define LZ4_WILDCOPY(s,d,e)             do { LZ4_COPYPACKET(s,d) } while (d<e);\r
 201 #define LZ4_BLINDCOPY(s,d,l)    { BYTE* e=d+l; LZ4_WILDCOPY(s,d,e); d=e; }\r
 202 #define HASH_FUNCTION(i)        (((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG))\r
 203 #define HASH_VALUE(p)           HASH_FUNCTION(*(U32*)(p))\r
 204 #define HASH_POINTER(p)         (HashTable[HASH_VALUE(p)] + base)\r
 205 #define DELTANEXT(p)            chainTable[(size_t)(p) & MAXD_MASK] \r
 206 #define GETNEXT(p)                      ((p) - (size_t)DELTANEXT(p))\r
 207 #define ADD_HASH(p)                     { size_t delta = (p) - HASH_POINTER(p); if (delta>MAX_DISTANCE) delta = MAX_DISTANCE; DELTANEXT(p) = (U16)delta; HashTable[HASH_VALUE(p)] = (p) - base; }\r
 208 \r
 209 \r
 210 //**************************************\r
 211 // Private functions\r
 212 //**************************************\r
 213 #if LZ4_ARCH64\r
 214 \r
 215 inline static int LZ4_NbCommonBytes (register U64 val)\r
 216 {\r
 217 #if defined(LZ4_BIG_ENDIAN)\r
 218     #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 219     unsigned long r = 0;\r
 220     _BitScanReverse64( &r, val );\r
 221     return (int)(r>>3);\r
 222     #elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 223     return (__builtin_clzll(val) >> 3); \r
 224     #else\r
 225         int r;\r
 226         if (!(val>>32)) { r=4; } else { r=0; val>>=32; }\r
 227         if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }\r
 228         r += (!val);\r
 229         return r;\r
 230     #endif\r
 231 #else\r
 232     #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 233     unsigned long r = 0;\r
 234     _BitScanForward64( &r, val );\r
 235     return (int)(r>>3);\r
 236     #elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 237     return (__builtin_ctzll(val) >> 3); \r
 238     #else\r
 239         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
 240         return DeBruijnBytePos[((U64)((val & -val) * 0x0218A392CDABBD3F)) >> 58];\r
 241     #endif\r
 242 #endif\r
 243 }\r
 244 \r
 245 #else\r
 246 \r
 247 inline static int LZ4_NbCommonBytes (register U32 val)\r
 248 {\r
 249 #if defined(LZ4_BIG_ENDIAN)\r
 250     #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 251     unsigned long r = 0;\r
 252     _BitScanReverse( &r, val );\r
 253     return (int)(r>>3);\r
 254     #elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 255     return (__builtin_clz(val) >> 3); \r
 256     #else\r
 257         int r;\r
 258         if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }\r
 259         r += (!val);\r
 260         return r;\r
 261     #endif\r
 262 #else\r
 263     #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 264     unsigned long r = 0;\r
 265     _BitScanForward( &r, val );\r
 266     return (int)(r>>3);\r
 267     #elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 268     return (__builtin_ctz(val) >> 3); \r
 269     #else\r
 270         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
 271         return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];\r
 272     #endif\r
 273 #endif\r
 274 }\r
 275 \r
 276 #endif\r
 277 \r
 278 \r
 279 inline static int LZ4HC_Init (LZ4HC_Data_Structure* hc4, const BYTE* base)\r
 280 {\r
 281         MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable));\r
 282         MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable));\r
 283         hc4->nextToUpdate = base + LZ4_ARCH64;\r
 284         hc4->base = base;\r
 285         return 1;\r
 286 }\r
 287 \r
 288 \r
 289 inline static void* LZ4HC_Create (const BYTE* base)\r
 290 {\r
 291         void* hc4 = ALLOCATOR(sizeof(LZ4HC_Data_Structure));\r
 292 \r
 293         LZ4HC_Init (hc4, base);\r
 294         return hc4;\r
 295 }\r
 296 \r
 297 \r
 298 inline static int LZ4HC_Free (void** LZ4HC_Data)\r
 299 {\r
 300         FREEMEM(*LZ4HC_Data);\r
 301         *LZ4HC_Data = NULL;\r
 302         return (1);\r
 303 }\r
 304 \r
 305 \r
 306 inline static void LZ4HC_Insert (LZ4HC_Data_Structure* hc4, const BYTE* ip)\r
 307 {\r
 308         U16*   chainTable = hc4->chainTable;\r
 309         HTYPE* HashTable  = hc4->hashTable;\r
 310         INITBASE(base,hc4->base);\r
 311 \r
 312         while(hc4->nextToUpdate < ip)\r
 313         {\r
 314                 ADD_HASH(hc4->nextToUpdate);\r
 315                 hc4->nextToUpdate++;\r
 316         }\r
 317 }\r
 318 \r
 319 \r
 320 inline static int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure* hc4, const BYTE* ip, const BYTE* const matchlimit, const BYTE** matchpos)\r
 321 {\r
 322         U16* const chainTable = hc4->chainTable;\r
 323         HTYPE* const HashTable = hc4->hashTable;\r
 324         const BYTE* ref;\r
 325         INITBASE(base,hc4->base);\r
 326         int nbAttempts=MAX_NB_ATTEMPTS;\r
 327         int ml=0;\r
 328 \r
 329         // HC4 match finder\r
 330         LZ4HC_Insert(hc4, ip);\r
 331         ref = HASH_POINTER(ip);\r
 332         while ((ref > (ip-MAX_DISTANCE)) && (nbAttempts))\r
 333         {\r
 334                 nbAttempts--;\r
 335                 if (*(ref+ml) == *(ip+ml))\r
 336                 if (*(U32*)ref == *(U32*)ip)\r
 337                 {\r
 338                         const BYTE* reft = ref+MINMATCH;\r
 339                         const BYTE* ipt = ip+MINMATCH;\r
 340 \r
 341                         while (ipt<matchlimit-(STEPSIZE-1))\r
 342                         {\r
 343                                 UARCH diff = AARCH(reft) ^ AARCH(ipt);\r
 344                                 if (!diff) { ipt+=STEPSIZE; reft+=STEPSIZE; continue; }\r
 345                                 ipt += LZ4_NbCommonBytes(diff);\r
 346                                 goto _endCount;\r
 347                         }\r
 348                         if (LZ4_ARCH64) if ((ipt<(matchlimit-3)) && (A32(reft) == A32(ipt))) { ipt+=4; reft+=4; }\r
 349                         if ((ipt<(matchlimit-1)) && (A16(reft) == A16(ipt))) { ipt+=2; reft+=2; }\r
 350                         if ((ipt<matchlimit) && (*reft == *ipt)) ipt++;\r
 351 _endCount:\r
 352 \r
 353                         if (ipt-ip > ml) { ml = ipt-ip; *matchpos = ref; }\r
 354                 }\r
 355                 ref = GETNEXT(ref);\r
 356         }\r
 357 \r
 358         return ml;\r
 359 }\r
 360 \r
 361 \r
 362 inline static int LZ4HC_InsertAndGetWiderMatch (LZ4HC_Data_Structure* hc4, const BYTE* ip, const BYTE* startLimit, const BYTE* matchlimit, int longest, const BYTE** matchpos, const BYTE** startpos)\r
 363 {\r
 364         U16* const  chainTable = hc4->chainTable;\r
 365         HTYPE* const HashTable = hc4->hashTable;\r
 366         INITBASE(base,hc4->base);\r
 367         const BYTE*  ref;\r
 368         int nbAttempts = MAX_NB_ATTEMPTS;\r
 369         int delta = ip-startLimit;\r
 370 \r
 371         // First Match\r
 372         LZ4HC_Insert(hc4, ip);\r
 373         ref = HASH_POINTER(ip);\r
 374 \r
 375         while ((ref > ip-MAX_DISTANCE) && (ref >= hc4->base) && (nbAttempts))\r
 376         {\r
 377                 nbAttempts--;\r
 378                 if (*(startLimit + longest) == *(ref - delta + longest))\r
 379                 if (*(U32*)ref == *(U32*)ip)\r
 380                 {\r
 381                         const BYTE* reft = ref+MINMATCH;\r
 382                         const BYTE* ipt = ip+MINMATCH;\r
 383                         const BYTE* startt = ip;\r
 384 \r
 385                         while (ipt<matchlimit-(STEPSIZE-1))\r
 386                         {\r
 387                                 UARCH diff = AARCH(reft) ^ AARCH(ipt);\r
 388                                 if (!diff) { ipt+=STEPSIZE; reft+=STEPSIZE; continue; }\r
 389                                 ipt += LZ4_NbCommonBytes(diff);\r
 390                                 goto _endCount;\r
 391                         }\r
 392                         if (LZ4_ARCH64) if ((ipt<(matchlimit-3)) && (A32(reft) == A32(ipt))) { ipt+=4; reft+=4; }\r
 393                         if ((ipt<(matchlimit-1)) && (A16(reft) == A16(ipt))) { ipt+=2; reft+=2; }\r
 394                         if ((ipt<matchlimit) && (*reft == *ipt)) ipt++;\r
 395 _endCount:\r
 396 \r
 397                         reft = ref;\r
 398                         while ((startt>startLimit) && (reft > hc4->base) && (startt[-1] == reft[-1])) {startt--; reft--;}\r
 399 \r
 400                         if ((ipt-startt) > longest)\r
 401                         {\r
 402                                 longest = ipt-startt;\r
 403                                 *matchpos = reft;\r
 404                                 *startpos = startt;\r
 405                         }\r
 406                 }\r
 407                 ref = GETNEXT(ref);\r
 408         }\r
 409 \r
 410         return longest;\r
 411 }\r
 412 \r
 413 \r
 414 inline static int LZ4_encodeSequence(const BYTE** ip, BYTE** op, const BYTE** anchor, int ml, const BYTE* ref)\r
 415 {\r
 416         int length, len; \r
 417         BYTE* token;\r
 418 \r
 419         // Encode Literal length\r
 420         length = *ip - *anchor;\r
 421         token = (*op)++;\r
 422         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
 423         else *token = (length<<ML_BITS);\r
 424 \r
 425         // Copy Literals\r
 426         LZ4_BLINDCOPY(*anchor, *op, length);\r
 427 \r
 428         // Encode Offset\r
 429         LZ4_WRITE_LITTLEENDIAN_16(*op,*ip-ref);\r
 430 \r
 431         // Encode MatchLength\r
 432         len = (int)(ml-MINMATCH);\r
 433         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
 434         else *token += len;     \r
 435 \r
 436         // Prepare next loop\r
 437         *ip += ml;\r
 438         *anchor = *ip; \r
 439 \r
 440         return 0;\r
 441 }\r
 442 \r
 443 \r
 444 //****************************\r
 445 // Compression CODE\r
 446 //****************************\r
 447 \r
 448 int LZ4_compressHCCtx(LZ4HC_Data_Structure* ctx,\r
 449                                  const char* source, \r
 450                                  char* dest,\r
 451                                  int isize)\r
 452 {       \r
 453         const BYTE* ip = (const BYTE*) source;\r
 454         const BYTE* anchor = ip;\r
 455         const BYTE* const iend = ip + isize;\r
 456         const BYTE* const mflimit = iend - MFLIMIT;\r
 457         const BYTE* const matchlimit = (iend - LASTLITERALS);\r
 458 \r
 459         BYTE* op = (BYTE*) dest;\r
 460 \r
 461         int     ml, ml2, ml3, ml0;\r
 462         const BYTE* ref=NULL;\r
 463         const BYTE* start2=NULL;\r
 464         const BYTE* ref2=NULL;\r
 465         const BYTE* start3=NULL;\r
 466         const BYTE* ref3=NULL;\r
 467         const BYTE* start0;\r
 468         const BYTE* ref0;\r
 469 \r
 470         ip++;\r
 471 \r
 472         // Main Loop\r
 473         while (ip < mflimit)\r
 474         {\r
 475                 ml = LZ4HC_InsertAndFindBestMatch (ctx, ip, matchlimit, (&ref));\r
 476                 if (!ml) { ip++; continue; }\r
 477 \r
 478                 // saved, in case we would skip too much\r
 479                 start0 = ip;\r
 480                 ref0 = ref;\r
 481                 ml0 = ml;\r
 482 \r
 483 _Search2:\r
 484                 if (ip+ml < mflimit)\r
 485                         ml2 = LZ4HC_InsertAndGetWiderMatch(ctx, ip + ml - 2, ip + 1, matchlimit, ml, &ref2, &start2);\r
 486                 else ml2=ml;\r
 487 \r
 488                 if (ml2 == ml)  // No better match\r
 489                 {\r
 490                         LZ4_encodeSequence(&ip, &op, &anchor, ml, ref);\r
 491                         continue;\r
 492                 }\r
 493 \r
 494                 if (start0 < ip)\r
 495                 {\r
 496                         if (start2 < ip + ml0)   // empirical\r
 497                         {\r
 498                                 ip = start0;\r
 499                                 ref = ref0;\r
 500                                 ml = ml0;\r
 501                         }\r
 502                 }\r
 503 \r
 504                 // Here, start0==ip\r
 505                 if ((start2 - ip) < 3)   // First Match too small : removed\r
 506                 {\r
 507                         ml = ml2;\r
 508                         ip = start2;\r
 509                         ref =ref2;\r
 510                         goto _Search2;\r
 511                 }\r
 512 \r
 513 _Search3:\r
 514                 // Currently we have :\r
 515                 // ml2 > ml1, and\r
 516                 // ip1+3 <= ip2 (usually < ip1+ml1)\r
 517                 if ((start2 - ip) < OPTIMAL_ML)\r
 518                 {\r
 519                         int correction;\r
 520                         int new_ml = ml;\r
 521                         if (new_ml > OPTIMAL_ML) new_ml = OPTIMAL_ML;\r
 522                         if (ip+new_ml > start2 + ml2 - MINMATCH) new_ml = start2 - ip + ml2 - MINMATCH;\r
 523                         correction = new_ml - (start2 - ip);\r
 524                         if (correction > 0)\r
 525                         {\r
 526                                 start2 += correction;\r
 527                                 ref2 += correction;\r
 528                                 ml2 -= correction;\r
 529                         }\r
 530                 }\r
 531                 // Now, we have start2 = ip+new_ml, with new_ml=min(ml, OPTIMAL_ML=18)\r
 532 \r
 533                 if (start2 + ml2 < mflimit)\r
 534                         ml3 = LZ4HC_InsertAndGetWiderMatch(ctx, start2 + ml2 - 3, start2, matchlimit, ml2, &ref3, &start3);\r
 535                 else ml3=ml2;\r
 536 \r
 537                 if (ml3 == ml2) // No better match : 2 sequences to encode\r
 538                 {\r
 539                         // ip & ref are known; Now for ml\r
 540                         if (start2 < ip+ml)\r
 541                         {\r
 542                                 if ((start2 - ip) < OPTIMAL_ML)\r
 543                                 {\r
 544                                         int correction;\r
 545                                         if (ml > OPTIMAL_ML) ml = OPTIMAL_ML;\r
 546                                         if (ip+ml > start2 + ml2 - MINMATCH) ml = start2 - ip + ml2 - MINMATCH;\r
 547                                         correction = ml - (start2 - ip);\r
 548                                         if (correction > 0)\r
 549                                         {\r
 550                                                 start2 += correction;\r
 551                                                 ref2 += correction;\r
 552                                                 ml2 -= correction;\r
 553                                         }\r
 554                                 }\r
 555                                 else\r
 556                                 {\r
 557                                         ml = start2 - ip;\r
 558                                 }\r
 559                         }\r
 560                         // Now, encode 2 sequences\r
 561                         LZ4_encodeSequence(&ip, &op, &anchor, ml, ref);\r
 562                         ip = start2;\r
 563                         LZ4_encodeSequence(&ip, &op, &anchor, ml2, ref2);\r
 564                         continue;\r
 565                 }\r
 566 \r
 567                 if (start3 < ip+ml+3) // Not enough space for match 2 : remove it\r
 568                 {\r
 569                         if (start3 >= (ip+ml)) // can write Seq1 immediately ==> Seq2 is removed, so Seq3 becomes Seq1\r
 570                         {\r
 571                                 if (start2 < ip+ml)\r
 572                                 {\r
 573                                         int correction = (ip+ml) - start2;\r
 574                                         start2 += correction;\r
 575                                         ref2 += correction;\r
 576                                         ml2 -= correction;\r
 577                                         if (ml2 < MINMATCH)\r
 578                                         {\r
 579                                                 start2 = start3;\r
 580                                                 ref2 = ref3;\r
 581                                                 ml2 = ml3;\r
 582                                         }\r
 583                                 }\r
 584 \r
 585                                 LZ4_encodeSequence(&ip, &op, &anchor, ml, ref);\r
 586                                 ip  = start3;\r
 587                                 ref = ref3;\r
 588                                 ml  = ml3;\r
 589 \r
 590                                 start0 = start2;\r
 591                                 ref0 = ref2;\r
 592                                 ml0 = ml2;\r
 593                                 goto _Search2;\r
 594                         }\r
 595 \r
 596                         start2 = start3;\r
 597                         ref2 = ref3;\r
 598                         ml2 = ml3;\r
 599                         goto _Search3;\r
 600                 }\r
 601 \r
 602                 // OK, now we have 3 ascending matches; let's write at least the first one\r
 603                 // ip & ref are known; Now for ml\r
 604                 if (start2 < ip+ml)\r
 605                 {\r
 606                         if ((start2 - ip) < (int)ML_MASK)\r
 607                         {\r
 608                                 int correction;\r
 609                                 if (ml > OPTIMAL_ML) ml = OPTIMAL_ML;\r
 610                                 if (ip + ml > start2 + ml2 - MINMATCH) ml = start2 - ip + ml2 - MINMATCH;\r
 611                                 correction = ml - (start2 - ip);\r
 612                                 if (correction > 0)\r
 613                                 {\r
 614                                         start2 += correction;\r
 615                                         ref2 += correction;\r
 616                                         ml2 -= correction;\r
 617                                 }\r
 618                         }\r
 619                         else\r
 620                         {\r
 621                                 ml = start2 - ip;\r
 622                         }\r
 623                 }\r
 624                 LZ4_encodeSequence(&ip, &op, &anchor, ml, ref);\r
 625 \r
 626                 ip = start2;\r
 627                 ref = ref2;\r
 628                 ml = ml2;\r
 629 \r
 630                 start2 = start3;\r
 631                 ref2 = ref3;\r
 632                 ml2 = ml3;\r
 633 \r
 634                 goto _Search3;\r
 635 \r
 636         }\r
 637 \r
 638         // Encode Last Literals\r
 639         {\r
 640                 int lastRun = iend - anchor;\r
 641                 if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; } \r
 642                 else *op++ = (lastRun<<ML_BITS);\r
 643                 memcpy(op, anchor, iend - anchor);\r
 644                 op += iend-anchor;\r
 645         } \r
 646 \r
 647         // End\r
 648         return (int) (((char*)op)-dest);\r
 649 }\r
 650 \r
 651 \r
 652 int LZ4_compressHC(const char* source, \r
 653                                  char* dest,\r
 654                                  int isize)\r
 655 {\r
 656         void* ctx = LZ4HC_Create((const BYTE*)source);\r
 657         int result = LZ4_compressHCCtx(ctx, source, dest, isize);\r
 658         LZ4HC_Free (&ctx);\r
 659 \r
 660         return result;\r
 661 }\r
 662 \r
 663 \r