silo/third-party/lz4/lz4hc.c

   1 /*\r
   2    LZ4 HC - High Compression Mode of LZ4\r
   3    Copyright (C) 2011-2013, 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 Note : this source file requires "lz4hc_encoder.h"\r
  36 */\r
  37 \r
  38 \r
  39 //**************************************\r
  40 // Memory routines\r
  41 //**************************************\r
  42 #include <stdlib.h>   // calloc, free\r
  43 #define ALLOCATOR(s)  calloc(1,s)\r
  44 #define FREEMEM       free\r
  45 #include <string.h>   // memset, memcpy\r
  46 #define MEM_INIT      memset\r
  47 \r
  48 \r
  49 //**************************************\r
  50 // CPU Feature Detection\r
  51 //**************************************\r
  52 // 32 or 64 bits ?\r
  53 #if (defined(__x86_64__) || defined(_M_X64) || defined(_WIN64) \\r
  54   || defined(__powerpc64__) || defined(__ppc64__) || defined(__PPC64__) \\r
  55   || defined(__64BIT__) || defined(_LP64) || defined(__LP64__) \\r
  56   || defined(__ia64) || defined(__itanium__) || defined(_M_IA64) )   // Detects 64 bits mode\r
  57 #  define LZ4_ARCH64 1\r
  58 #else\r
  59 #  define LZ4_ARCH64 0\r
  60 #endif\r
  61 \r
  62 // Little Endian or Big Endian ?\r
  63 // Overwrite the #define below if you know your architecture endianess\r
  64 #if defined (__GLIBC__)\r
  65 #  include <endian.h>\r
  66 #  if (__BYTE_ORDER == __BIG_ENDIAN)\r
  67 #     define LZ4_BIG_ENDIAN 1\r
  68 #  endif\r
  69 #elif (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN)) && !(defined(__LITTLE_ENDIAN__) || defined(__LITTLE_ENDIAN) || defined(_LITTLE_ENDIAN))\r
  70 #  define LZ4_BIG_ENDIAN 1\r
  71 #elif defined(__sparc) || defined(__sparc__) \\r
  72    || defined(__powerpc__) || defined(__ppc__) || defined(__PPC__) \\r
  73    || defined(__hpux)  || defined(__hppa) \\r
  74    || defined(_MIPSEB) || defined(__s390__)\r
  75 #  define LZ4_BIG_ENDIAN 1\r
  76 #else\r
  77 // Little Endian assumed. PDP Endian and other very rare endian format are unsupported.\r
  78 #endif\r
  79 \r
  80 // Unaligned memory access is automatically enabled for "common" CPU, such as x86.\r
  81 // For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected\r
  82 // If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance\r
  83 #if defined(__ARM_FEATURE_UNALIGNED)\r
  84 #  define LZ4_FORCE_UNALIGNED_ACCESS 1\r
  85 #endif\r
  86 \r
  87 // Define this parameter if your target system or compiler does not support hardware bit count\r
  88 #if defined(_MSC_VER) && defined(_WIN32_WCE)            // Visual Studio for Windows CE does not support Hardware bit count\r
  89 #  define LZ4_FORCE_SW_BITCOUNT\r
  90 #endif\r
  91 \r
  92 \r
  93 //**************************************\r
  94 // Compiler Options\r
  95 //**************************************\r
  96 #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L   // C99\r
  97   /* "restrict" is a known keyword */\r
  98 #else\r
  99 #  define restrict  // Disable restrict\r
 100 #endif\r
 101 \r
 102 #ifdef _MSC_VER\r
 103 #  define forceinline __forceinline\r
 104 #  include <intrin.h>                 // For Visual 2005\r
 105 #  if LZ4_ARCH64     // 64-bits\r
 106 #    pragma intrinsic(_BitScanForward64) // For Visual 2005\r
 107 #    pragma intrinsic(_BitScanReverse64) // For Visual 2005\r
 108 #  else              // 32-bits\r
 109 #    pragma intrinsic(_BitScanForward)   // For Visual 2005\r
 110 #    pragma intrinsic(_BitScanReverse)   // For Visual 2005\r
 111 #  endif\r
 112 #  pragma warning(disable : 4127)        // disable: C4127: conditional expression is constant\r
 113 #  pragma warning(disable : 4701)        // disable: C4701: potentially uninitialized local variable used\r
 114 #else \r
 115 #  ifdef __GNUC__\r
 116 #    define forceinline inline __attribute__((always_inline))\r
 117 #  else\r
 118 #    define forceinline inline\r
 119 #  endif\r
 120 #endif\r
 121 \r
 122 #ifdef _MSC_VER  // Visual Studio\r
 123 #define lz4_bswap16(x) _byteswap_ushort(x)\r
 124 #else\r
 125 #define lz4_bswap16(x)  ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8)))\r
 126 #endif\r
 127 \r
 128 \r
 129 //**************************************\r
 130 // Includes\r
 131 //**************************************\r
 132 #include "lz4hc.h"\r
 133 #include "lz4.h"\r
 134 \r
 135 \r
 136 //**************************************\r
 137 // Basic Types\r
 138 //**************************************\r
 139 #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L   // C99\r
 140 # include <stdint.h>\r
 141   typedef uint8_t  BYTE;\r
 142   typedef uint16_t U16;\r
 143   typedef uint32_t U32;\r
 144   typedef  int32_t S32;\r
 145   typedef uint64_t U64;\r
 146 #else\r
 147   typedef unsigned char       BYTE;\r
 148   typedef unsigned short      U16;\r
 149   typedef unsigned int        U32;\r
 150   typedef   signed int        S32;\r
 151   typedef unsigned long long  U64;\r
 152 #endif\r
 153 \r
 154 #if defined(__GNUC__)  && !defined(LZ4_FORCE_UNALIGNED_ACCESS)\r
 155 #  define _PACKED __attribute__ ((packed))\r
 156 #else\r
 157 #  define _PACKED\r
 158 #endif\r
 159 \r
 160 #if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__)\r
 161 #  ifdef __IBMC__\r
 162 #    pragma pack(1)\r
 163 #  else\r
 164 #    pragma pack(push, 1)\r
 165 #  endif\r
 166 #endif\r
 167 \r
 168 typedef struct _U16_S { U16 v; } _PACKED U16_S;\r
 169 typedef struct _U32_S { U32 v; } _PACKED U32_S;\r
 170 typedef struct _U64_S { U64 v; } _PACKED U64_S;\r
 171 \r
 172 #if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__)\r
 173 #  pragma pack(pop)\r
 174 #endif\r
 175 \r
 176 #define A64(x) (((U64_S *)(x))->v)\r
 177 #define A32(x) (((U32_S *)(x))->v)\r
 178 #define A16(x) (((U16_S *)(x))->v)\r
 179 \r
 180 \r
 181 //**************************************\r
 182 // Constants\r
 183 //**************************************\r
 184 #define MINMATCH 4\r
 185 \r
 186 #define DICTIONARY_LOGSIZE 16\r
 187 #define MAXD (1<<DICTIONARY_LOGSIZE)\r
 188 #define MAXD_MASK ((U32)(MAXD - 1))\r
 189 #define MAX_DISTANCE (MAXD - 1)\r
 190 \r
 191 #define HASH_LOG (DICTIONARY_LOGSIZE-1)\r
 192 #define HASHTABLESIZE (1 << HASH_LOG)\r
 193 #define HASH_MASK (HASHTABLESIZE - 1)\r
 194 \r
 195 #define MAX_NB_ATTEMPTS 256\r
 196 \r
 197 #define ML_BITS  4\r
 198 #define ML_MASK  (size_t)((1U<<ML_BITS)-1)\r
 199 #define RUN_BITS (8-ML_BITS)\r
 200 #define RUN_MASK ((1U<<RUN_BITS)-1)\r
 201 \r
 202 #define COPYLENGTH 8\r
 203 #define LASTLITERALS 5\r
 204 #define MFLIMIT (COPYLENGTH+MINMATCH)\r
 205 #define MINLENGTH (MFLIMIT+1)\r
 206 #define OPTIMAL_ML (int)((ML_MASK-1)+MINMATCH)\r
 207 \r
 208 #define KB *(1U<<10)\r
 209 #define MB *(1U<<20)\r
 210 #define GB *(1U<<30)\r
 211 \r
 212 \r
 213 //**************************************\r
 214 // Architecture-specific macros\r
 215 //**************************************\r
 216 #if LZ4_ARCH64   // 64-bit\r
 217 #  define STEPSIZE 8\r
 218 #  define LZ4_COPYSTEP(s,d)     A64(d) = A64(s); d+=8; s+=8;\r
 219 #  define LZ4_COPYPACKET(s,d)   LZ4_COPYSTEP(s,d)\r
 220 #  define UARCH U64\r
 221 #  define AARCH A64\r
 222 #  define HTYPE                 U32\r
 223 #  define INITBASE(b,s)         const BYTE* const b = s\r
 224 #else   // 32-bit\r
 225 #  define STEPSIZE 4\r
 226 #  define LZ4_COPYSTEP(s,d)     A32(d) = A32(s); d+=4; s+=4;\r
 227 #  define LZ4_COPYPACKET(s,d)   LZ4_COPYSTEP(s,d); LZ4_COPYSTEP(s,d);\r
 228 #  define UARCH U32\r
 229 #  define AARCH A32\r
 230 //#  define HTYPE                 const BYTE*\r
 231 //#  define INITBASE(b,s)         const int b = 0\r
 232 #  define HTYPE                 U32\r
 233 #  define INITBASE(b,s)         const BYTE* const b = s\r
 234 #endif\r
 235 \r
 236 #if defined(LZ4_BIG_ENDIAN)\r
 237 #  define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; }\r
 238 #  define LZ4_WRITE_LITTLEENDIAN_16(p,i)  { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p+=2; }\r
 239 #else   // Little Endian\r
 240 #  define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); }\r
 241 #  define LZ4_WRITE_LITTLEENDIAN_16(p,v)  { A16(p) = v; p+=2; }\r
 242 #endif\r
 243 \r
 244 \r
 245 //************************************************************\r
 246 // Local Types\r
 247 //************************************************************\r
 248 typedef struct \r
 249 {\r
 250     const BYTE* inputBuffer;\r
 251     const BYTE* base;\r
 252     const BYTE* end;\r
 253     HTYPE hashTable[HASHTABLESIZE];\r
 254     U16 chainTable[MAXD];\r
 255     const BYTE* nextToUpdate;\r
 256 } LZ4HC_Data_Structure;\r
 257 \r
 258 \r
 259 //**************************************\r
 260 // Macros\r
 261 //**************************************\r
 262 #define LZ4_WILDCOPY(s,d,e)    do { LZ4_COPYPACKET(s,d) } while (d<e);\r
 263 #define LZ4_BLINDCOPY(s,d,l)   { BYTE* e=d+l; LZ4_WILDCOPY(s,d,e); d=e; }\r
 264 #define HASH_FUNCTION(i)       (((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG))\r
 265 #define HASH_VALUE(p)          HASH_FUNCTION(A32(p))\r
 266 #define HASH_POINTER(p)        (HashTable[HASH_VALUE(p)] + base)\r
 267 #define DELTANEXT(p)           chainTable[(size_t)(p) & MAXD_MASK] \r
 268 #define GETNEXT(p)             ((p) - (size_t)DELTANEXT(p))\r
 269 \r
 270 \r
 271 //**************************************\r
 272 // Private functions\r
 273 //**************************************\r
 274 #if LZ4_ARCH64\r
 275 \r
 276 inline static int LZ4_NbCommonBytes (register U64 val)\r
 277 {\r
 278 #if defined(LZ4_BIG_ENDIAN)\r
 279 #  if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 280     unsigned long r = 0;\r
 281     _BitScanReverse64( &r, val );\r
 282     return (int)(r>>3);\r
 283 #  elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 284     return (__builtin_clzll(val) >> 3); \r
 285 #  else\r
 286     int r;\r
 287     if (!(val>>32)) { r=4; } else { r=0; val>>=32; }\r
 288     if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }\r
 289     r += (!val);\r
 290     return r;\r
 291 #  endif\r
 292 #else\r
 293 #  if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 294     unsigned long r = 0;\r
 295     _BitScanForward64( &r, val );\r
 296     return (int)(r>>3);\r
 297 #  elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 298     return (__builtin_ctzll(val) >> 3); \r
 299 #  else\r
 300     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
 301     return DeBruijnBytePos[((U64)((val & -val) * 0x0218A392CDABBD3F)) >> 58];\r
 302 #  endif\r
 303 #endif\r
 304 }\r
 305 \r
 306 #else\r
 307 \r
 308 inline static int LZ4_NbCommonBytes (register U32 val)\r
 309 {\r
 310 #if defined(LZ4_BIG_ENDIAN)\r
 311 #  if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 312     unsigned long r;\r
 313     _BitScanReverse( &r, val );\r
 314     return (int)(r>>3);\r
 315 #  elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 316     return (__builtin_clz(val) >> 3); \r
 317 #  else\r
 318     int r;\r
 319     if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }\r
 320     r += (!val);\r
 321     return r;\r
 322 #  endif\r
 323 #else\r
 324 #  if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 325     unsigned long r;\r
 326     _BitScanForward( &r, val );\r
 327     return (int)(r>>3);\r
 328 #  elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)\r
 329     return (__builtin_ctz(val) >> 3); \r
 330 #  else\r
 331     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
 332     return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];\r
 333 #  endif\r
 334 #endif\r
 335 }\r
 336 \r
 337 #endif\r
 338 \r
 339 \r
 340 static inline int LZ4_InitHC (LZ4HC_Data_Structure* hc4, const BYTE* base)\r
 341 {\r
 342     MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable));\r
 343     MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable));\r
 344     hc4->nextToUpdate = base + 1;\r
 345     hc4->base = base;\r
 346     hc4->inputBuffer = base;\r
 347     hc4->end = base;\r
 348     return 1;\r
 349 }\r
 350 \r
 351 \r
 352 void* LZ4_createHC (const char* slidingInputBuffer)\r
 353 {\r
 354     void* hc4 = ALLOCATOR(sizeof(LZ4HC_Data_Structure));\r
 355     LZ4_InitHC ((LZ4HC_Data_Structure*)hc4, (const BYTE*)slidingInputBuffer);\r
 356     return hc4;\r
 357 }\r
 358 \r
 359 \r
 360 int LZ4_freeHC (void* LZ4HC_Data)\r
 361 {\r
 362     FREEMEM(LZ4HC_Data);\r
 363     return (0);\r
 364 }\r
 365 \r
 366 \r
 367 // Update chains up to ip (excluded)\r
 368 static forceinline void LZ4HC_Insert (LZ4HC_Data_Structure* hc4, const BYTE* ip)\r
 369 {\r
 370     U16*   chainTable = hc4->chainTable;\r
 371     HTYPE* HashTable  = hc4->hashTable;\r
 372     INITBASE(base,hc4->base);\r
 373 \r
 374     while(hc4->nextToUpdate < ip)\r
 375     {\r
 376         const BYTE* const p = hc4->nextToUpdate;\r
 377         size_t delta = (p) - HASH_POINTER(p); \r
 378         if (delta>MAX_DISTANCE) delta = MAX_DISTANCE; \r
 379         DELTANEXT(p) = (U16)delta; \r
 380         HashTable[HASH_VALUE(p)] = (HTYPE)((p) - base);\r
 381         hc4->nextToUpdate++;\r
 382     }\r
 383 }\r
 384 \r
 385 \r
 386 char* LZ4_slideInputBufferHC(void* LZ4HC_Data)\r
 387 {\r
 388     LZ4HC_Data_Structure* hc4 = (LZ4HC_Data_Structure*)LZ4HC_Data;\r
 389     U32 distance = (U32)(hc4->end - hc4->inputBuffer) - 64 KB;\r
 390     distance = (distance >> 16) << 16;   // Must be a multiple of 64 KB\r
 391     LZ4HC_Insert(hc4, hc4->end - MINMATCH);\r
 392     memcpy((void*)(hc4->end - 64 KB - distance), (const void*)(hc4->end - 64 KB), 64 KB);\r
 393     hc4->nextToUpdate -= distance;\r
 394     hc4->base -= distance;\r
 395     if ((U32)(hc4->inputBuffer - hc4->base) > 1 GB + 64 KB)   // Avoid overflow\r
 396     {\r
 397         int i;\r
 398         hc4->base += 1 GB;\r
 399         for (i=0; i<HASHTABLESIZE; i++) hc4->hashTable[i] -= 1 GB;\r
 400     }\r
 401     hc4->end -= distance;\r
 402     return (char*)(hc4->end);\r
 403 }\r
 404 \r
 405 \r
 406 static forceinline size_t LZ4HC_CommonLength (const BYTE* p1, const BYTE* p2, const BYTE* const matchlimit)\r
 407 {\r
 408     const BYTE* p1t = p1;\r
 409 \r
 410     while (p1t<matchlimit-(STEPSIZE-1))\r
 411     {\r
 412         UARCH diff = AARCH(p2) ^ AARCH(p1t);\r
 413         if (!diff) { p1t+=STEPSIZE; p2+=STEPSIZE; continue; }\r
 414         p1t += LZ4_NbCommonBytes(diff);\r
 415         return (p1t - p1);\r
 416     }\r
 417     if (LZ4_ARCH64) if ((p1t<(matchlimit-3)) && (A32(p2) == A32(p1t))) { p1t+=4; p2+=4; }\r
 418     if ((p1t<(matchlimit-1)) && (A16(p2) == A16(p1t))) { p1t+=2; p2+=2; }\r
 419     if ((p1t<matchlimit) && (*p2 == *p1t)) p1t++;\r
 420     return (p1t - p1);\r
 421 }\r
 422 \r
 423 \r
 424 static forceinline int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure* hc4, const BYTE* ip, const BYTE* const matchlimit, const BYTE** matchpos)\r
 425 {\r
 426     U16* const chainTable = hc4->chainTable;\r
 427     HTYPE* const HashTable = hc4->hashTable;\r
 428     const BYTE* ref;\r
 429     INITBASE(base,hc4->base);\r
 430     int nbAttempts=MAX_NB_ATTEMPTS;\r
 431     size_t repl=0, ml=0;\r
 432     U16 delta=0;  // useless assignment, to remove an uninitialization warning\r
 433 \r
 434     // HC4 match finder\r
 435     LZ4HC_Insert(hc4, ip);\r
 436     ref = HASH_POINTER(ip);\r
 437 \r
 438 #define REPEAT_OPTIMIZATION\r
 439 #ifdef REPEAT_OPTIMIZATION\r
 440     // Detect repetitive sequences of length <= 4\r
 441     if ((U32)(ip-ref) <= 4)        // potential repetition\r
 442     {\r
 443         if (A32(ref) == A32(ip))   // confirmed\r
 444         {\r
 445             delta = (U16)(ip-ref);\r
 446             repl = ml  = LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit) + MINMATCH;\r
 447             *matchpos = ref;\r
 448         }\r
 449         ref = GETNEXT(ref);\r
 450     }\r
 451 #endif\r
 452 \r
 453     while (((U32)(ip-ref) <= MAX_DISTANCE) && (nbAttempts))\r
 454     {\r
 455         nbAttempts--;\r
 456         if (*(ref+ml) == *(ip+ml))\r
 457         if (A32(ref) == A32(ip))\r
 458         {\r
 459             size_t mlt = LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit) + MINMATCH;\r
 460             if (mlt > ml) { ml = mlt; *matchpos = ref; }\r
 461         }\r
 462         ref = GETNEXT(ref);\r
 463     }\r
 464 \r
 465 #ifdef REPEAT_OPTIMIZATION\r
 466     // Complete table\r
 467     if (repl)\r
 468     {\r
 469         const BYTE* ptr = ip;\r
 470         const BYTE* end;\r
 471 \r
 472         end = ip + repl - (MINMATCH-1);\r
 473         while(ptr < end-delta)\r
 474         {\r
 475             DELTANEXT(ptr) = delta;    // Pre-Load\r
 476             ptr++;\r
 477         }\r
 478         do\r
 479         {\r
 480             DELTANEXT(ptr) = delta;    \r
 481             HashTable[HASH_VALUE(ptr)] = (HTYPE)((ptr) - base);     // Head of chain\r
 482             ptr++;\r
 483         } while(ptr < end);\r
 484         hc4->nextToUpdate = end;\r
 485     }\r
 486 #endif \r
 487 \r
 488     return (int)ml;\r
 489 }\r
 490 \r
 491 \r
 492 static forceinline 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
 493 {\r
 494     U16* const  chainTable = hc4->chainTable;\r
 495     HTYPE* const HashTable = hc4->hashTable;\r
 496     INITBASE(base,hc4->base);\r
 497     const BYTE*  ref;\r
 498     int nbAttempts = MAX_NB_ATTEMPTS;\r
 499     int delta = (int)(ip-startLimit);\r
 500 \r
 501     // First Match\r
 502     LZ4HC_Insert(hc4, ip);\r
 503     ref = HASH_POINTER(ip);\r
 504 \r
 505     while (((U32)(ip-ref) <= MAX_DISTANCE) && (nbAttempts))\r
 506     {\r
 507         nbAttempts--;\r
 508         if (*(startLimit + longest) == *(ref - delta + longest))\r
 509         if (A32(ref) == A32(ip))\r
 510         {\r
 511 #if 1\r
 512             const BYTE* reft = ref+MINMATCH;\r
 513             const BYTE* ipt = ip+MINMATCH;\r
 514             const BYTE* startt = ip;\r
 515 \r
 516             while (ipt<matchlimit-(STEPSIZE-1))\r
 517             {\r
 518                 UARCH diff = AARCH(reft) ^ AARCH(ipt);\r
 519                 if (!diff) { ipt+=STEPSIZE; reft+=STEPSIZE; continue; }\r
 520                 ipt += LZ4_NbCommonBytes(diff);\r
 521                 goto _endCount;\r
 522             }\r
 523             if (LZ4_ARCH64) if ((ipt<(matchlimit-3)) && (A32(reft) == A32(ipt))) { ipt+=4; reft+=4; }\r
 524             if ((ipt<(matchlimit-1)) && (A16(reft) == A16(ipt))) { ipt+=2; reft+=2; }\r
 525             if ((ipt<matchlimit) && (*reft == *ipt)) ipt++;\r
 526 _endCount:\r
 527             reft = ref;\r
 528 #else\r
 529             // Easier for code maintenance, but unfortunately slower too\r
 530             const BYTE* startt = ip;\r
 531             const BYTE* reft = ref;\r
 532             const BYTE* ipt = ip + MINMATCH + LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit);\r
 533 #endif\r
 534 \r
 535             while ((startt>startLimit) && (reft > hc4->inputBuffer) && (startt[-1] == reft[-1])) {startt--; reft--;}\r
 536 \r
 537             if ((ipt-startt) > longest)\r
 538             {\r
 539                 longest = (int)(ipt-startt);\r
 540                 *matchpos = reft;\r
 541                 *startpos = startt;\r
 542             }\r
 543         }\r
 544         ref = GETNEXT(ref);\r
 545     }\r
 546 \r
 547     return longest;\r
 548 }\r
 549 \r
 550 \r
 551 \r
 552 //**************************************\r
 553 // Compression functions\r
 554 //**************************************\r
 555 \r
 556 /*\r
 557 int LZ4_compressHC(\r
 558                  const char* source,\r
 559                  char* dest,\r
 560                  int inputSize)\r
 561 \r
 562 Compress 'inputSize' bytes from 'source' into an output buffer 'dest'.\r
 563 Destination buffer must be already allocated, and sized at a minimum of LZ4_compressBound(inputSize).\r
 564 return : the number of bytes written in buffer 'dest'\r
 565 */\r
 566 #define FUNCTION_NAME LZ4_compressHC\r
 567 #include "lz4hc_encoder.h"\r
 568 \r
 569 \r
 570 /*\r
 571 int LZ4_compressHC_limitedOutput(\r
 572                  const char* source,\r
 573                  char* dest,\r
 574                  int inputSize,\r
 575                  int maxOutputSize)\r
 576 \r
 577 Compress 'inputSize' bytes from 'source' into an output buffer 'dest' of maximum size 'maxOutputSize'.\r
 578 If it cannot achieve it, compression will stop, and result of the function will be zero.\r
 579 return : the number of bytes written in buffer 'dest', or 0 if the compression fails\r
 580 */\r
 581 #define FUNCTION_NAME LZ4_compressHC_limitedOutput\r
 582 #define LIMITED_OUTPUT\r
 583 #include "lz4hc_encoder.h"\r
 584 \r