1 /* 2 LZ4 HC - High Compression Mode of LZ4 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 source repository : https://github.com/lz4/lz4 32 - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c 33 */ 34 /* note : lz4hc is not an independent module, it requires lz4.h/lz4.c for proper compilation */ 35 36 37 /* ************************************* 38 * Tuning Parameter 39 ***************************************/ 40 41 /*! HEAPMODE : 42 * Select how default compression function will allocate workplace memory, 43 * in stack (0:fastest), or in heap (1:requires malloc()). 44 * Since workplace is rather large, heap mode is recommended. 45 */ 46 #ifndef LZ4HC_HEAPMODE 47 # define LZ4HC_HEAPMODE 1 48 #endif 49 50 51 /*=== Dependency ===*/ 52 #define LZ4_HC_STATIC_LINKING_ONLY 53 #include "lz4hc.h" 54 55 56 /*=== Common LZ4 definitions ===*/ 57 #if defined(__GNUC__) 58 # pragma GCC diagnostic ignored "-Wunused-function" 59 #endif 60 #if defined (__clang__) 61 # pragma clang diagnostic ignored "-Wunused-function" 62 #endif 63 64 #define LZ4_COMMONDEFS_ONLY 65 #include "lz4.c" /* LZ4_count, constants, mem */ 66 67 68 /*=== Constants ===*/ 69 #define OPTIMAL_ML (int)((ML_MASK-1)+MINMATCH) 70 #define LZ4_OPT_NUM (1<<12) 71 72 73 /*=== Macros ===*/ 74 #define MIN(a,b) ( (a) < (b) ? (a) : (b) ) 75 #define MAX(a,b) ( (a) > (b) ? (a) : (b) ) 76 #define HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-LZ4HC_HASH_LOG)) 77 #define DELTANEXTMAXD(p) chainTable[(p) & LZ4HC_MAXD_MASK] /* flexible, LZ4HC_MAXD dependent */ 78 #define DELTANEXTU16(table, pos) table[(U16)(pos)] /* faster */ 79 80 static U32 LZ4HC_hashPtr(const void* ptr) { return HASH_FUNCTION(LZ4_read32(ptr)); } 81 82 /*=== Enums ===*/ 83 typedef enum { noDictCtx, usingDictCtx } dictCtx_directive; 84 85 86 /************************************** 87 * HC Compression 88 **************************************/ 89 static void LZ4HC_clearTables (LZ4HC_CCtx_internal* hc4) 90 { 91 MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable)); 92 MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable)); 93 } 94 95 static void LZ4HC_init (LZ4HC_CCtx_internal* hc4, const BYTE* start) 96 { 97 uptrval startingOffset = hc4->end - hc4->base; 98 if (startingOffset > 1 GB) { 99 LZ4HC_clearTables(hc4); 100 startingOffset = 0; 101 } 102 startingOffset += 64 KB; 103 hc4->nextToUpdate = (U32) startingOffset; 104 hc4->base = start - startingOffset; 105 hc4->end = start; 106 hc4->dictBase = start - startingOffset; 107 hc4->dictLimit = (U32) startingOffset; 108 hc4->lowLimit = (U32) startingOffset; 109 } 110 111 112 /* Update chains up to ip (excluded) */ 113 LZ4_FORCE_INLINE void LZ4HC_Insert (LZ4HC_CCtx_internal* hc4, const BYTE* ip) 114 { 115 U16* const chainTable = hc4->chainTable; 116 U32* const hashTable = hc4->hashTable; 117 const BYTE* const base = hc4->base; 118 U32 const target = (U32)(ip - base); 119 U32 idx = hc4->nextToUpdate; 120 121 while (idx < target) { 122 U32 const h = LZ4HC_hashPtr(base+idx); 123 size_t delta = idx - hashTable[h]; 124 if (delta>MAX_DISTANCE) delta = MAX_DISTANCE; 125 DELTANEXTU16(chainTable, idx) = (U16)delta; 126 hashTable[h] = idx; 127 idx++; 128 } 129 130 hc4->nextToUpdate = target; 131 } 132 133 /** LZ4HC_countBack() : 134 * @return : negative value, nb of common bytes before ip/match */ 135 LZ4_FORCE_INLINE 136 int LZ4HC_countBack(const BYTE* const ip, const BYTE* const match, 137 const BYTE* const iMin, const BYTE* const mMin) 138 { 139 int back = 0; 140 int const min = (int)MAX(iMin - ip, mMin - match); 141 assert(min <= 0); 142 assert(ip >= iMin); assert((size_t)(ip-iMin) < (1U<<31)); 143 assert(match >= mMin); assert((size_t)(match - mMin) < (1U<<31)); 144 while ( (back > min) 145 && (ip[back-1] == match[back-1]) ) 146 back--; 147 return back; 148 } 149 150 /* LZ4HC_countPattern() : 151 * pattern32 must be a sample of repetitive pattern of length 1, 2 or 4 (but not 3!) */ 152 static unsigned 153 LZ4HC_countPattern(const BYTE* ip, const BYTE* const iEnd, U32 const pattern32) 154 { 155 const BYTE* const iStart = ip; 156 reg_t const pattern = (sizeof(pattern)==8) ? (reg_t)pattern32 + (((reg_t)pattern32) << 32) : pattern32; 157 158 while (likely(ip < iEnd-(sizeof(pattern)-1))) { 159 reg_t const diff = LZ4_read_ARCH(ip) ^ pattern; 160 if (!diff) { ip+=sizeof(pattern); continue; } 161 ip += LZ4_NbCommonBytes(diff); 162 return (unsigned)(ip - iStart); 163 } 164 165 if (LZ4_isLittleEndian()) { 166 reg_t patternByte = pattern; 167 while ((ip<iEnd) && (*ip == (BYTE)patternByte)) { 168 ip++; patternByte >>= 8; 169 } 170 } else { /* big endian */ 171 U32 bitOffset = (sizeof(pattern)*8) - 8; 172 while (ip < iEnd) { 173 BYTE const byte = (BYTE)(pattern >> bitOffset); 174 if (*ip != byte) break; 175 ip ++; bitOffset -= 8; 176 } 177 } 178 179 return (unsigned)(ip - iStart); 180 } 181 182 /* LZ4HC_reverseCountPattern() : 183 * pattern must be a sample of repetitive pattern of length 1, 2 or 4 (but not 3!) 184 * read using natural platform endianess */ 185 static unsigned 186 LZ4HC_reverseCountPattern(const BYTE* ip, const BYTE* const iLow, U32 pattern) 187 { 188 const BYTE* const iStart = ip; 189 190 while (likely(ip >= iLow+4)) { 191 if (LZ4_read32(ip-4) != pattern) break; 192 ip -= 4; 193 } 194 { const BYTE* bytePtr = (const BYTE*)(&pattern) + 3; /* works for any endianess */ 195 while (likely(ip>iLow)) { 196 if (ip[-1] != *bytePtr) break; 197 ip--; bytePtr--; 198 } } 199 return (unsigned)(iStart - ip); 200 } 201 202 typedef enum { rep_untested, rep_not, rep_confirmed } repeat_state_e; 203 typedef enum { favorCompressionRatio=0, favorDecompressionSpeed } HCfavor_e; 204 205 LZ4_FORCE_INLINE int 206 LZ4HC_InsertAndGetWiderMatch ( 207 LZ4HC_CCtx_internal* hc4, 208 const BYTE* const ip, 209 const BYTE* const iLowLimit, 210 const BYTE* const iHighLimit, 211 int longest, 212 const BYTE** matchpos, 213 const BYTE** startpos, 214 const int maxNbAttempts, 215 const int patternAnalysis, 216 const int chainSwap, 217 const dictCtx_directive dict, 218 const HCfavor_e favorDecSpeed) 219 { 220 U16* const chainTable = hc4->chainTable; 221 U32* const HashTable = hc4->hashTable; 222 const LZ4HC_CCtx_internal * const dictCtx = hc4->dictCtx; 223 const BYTE* const base = hc4->base; 224 const U32 dictLimit = hc4->dictLimit; 225 const BYTE* const lowPrefixPtr = base + dictLimit; 226 const U32 ipIndex = (U32)(ip - base); 227 const U32 lowestMatchIndex = (hc4->lowLimit + 64 KB > ipIndex) ? hc4->lowLimit : ipIndex - MAX_DISTANCE; 228 const BYTE* const dictBase = hc4->dictBase; 229 int const lookBackLength = (int)(ip-iLowLimit); 230 int nbAttempts = maxNbAttempts; 231 int matchChainPos = 0; 232 U32 const pattern = LZ4_read32(ip); 233 U32 matchIndex; 234 U32 dictMatchIndex; 235 repeat_state_e repeat = rep_untested; 236 size_t srcPatternLength = 0; 237 238 DEBUGLOG(7, "LZ4HC_InsertAndGetWiderMatch"); 239 /* First Match */ 240 LZ4HC_Insert(hc4, ip); 241 matchIndex = HashTable[LZ4HC_hashPtr(ip)]; 242 DEBUGLOG(7, "First match at index %u / %u (lowestMatchIndex)", 243 matchIndex, lowestMatchIndex); 244 245 while ((matchIndex>=lowestMatchIndex) && (nbAttempts)) { 246 int matchLength=0; 247 nbAttempts--; 248 assert(matchIndex < ipIndex); 249 if (favorDecSpeed && (ipIndex - matchIndex < 8)) { 250 /* do nothing */ 251 } else if (matchIndex >= dictLimit) { /* within current Prefix */ 252 const BYTE* const matchPtr = base + matchIndex; 253 assert(matchPtr >= lowPrefixPtr); 254 assert(matchPtr < ip); 255 assert(longest >= 1); 256 if (LZ4_read16(iLowLimit + longest - 1) == LZ4_read16(matchPtr - lookBackLength + longest - 1)) { 257 if (LZ4_read32(matchPtr) == pattern) { 258 int const back = lookBackLength ? LZ4HC_countBack(ip, matchPtr, iLowLimit, lowPrefixPtr) : 0; 259 matchLength = MINMATCH + LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, iHighLimit); 260 matchLength -= back; 261 if (matchLength > longest) { 262 longest = matchLength; 263 *matchpos = matchPtr + back; 264 *startpos = ip + back; 265 } } } 266 } else { /* lowestMatchIndex <= matchIndex < dictLimit */ 267 const BYTE* const matchPtr = dictBase + matchIndex; 268 if (LZ4_read32(matchPtr) == pattern) { 269 const BYTE* const dictStart = dictBase + hc4->lowLimit; 270 int back = 0; 271 const BYTE* vLimit = ip + (dictLimit - matchIndex); 272 if (vLimit > iHighLimit) vLimit = iHighLimit; 273 matchLength = LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, vLimit) + MINMATCH; 274 if ((ip+matchLength == vLimit) && (vLimit < iHighLimit)) 275 matchLength += LZ4_count(ip+matchLength, lowPrefixPtr, iHighLimit); 276 back = lookBackLength ? LZ4HC_countBack(ip, matchPtr, iLowLimit, dictStart) : 0; 277 matchLength -= back; 278 if (matchLength > longest) { 279 longest = matchLength; 280 *matchpos = base + matchIndex + back; /* virtual pos, relative to ip, to retrieve offset */ 281 *startpos = ip + back; 282 } } } 283 284 if (chainSwap && matchLength==longest) { /* better match => select a better chain */ 285 assert(lookBackLength==0); /* search forward only */ 286 if (matchIndex + longest <= ipIndex) { 287 U32 distanceToNextMatch = 1; 288 int pos; 289 for (pos = 0; pos <= longest - MINMATCH; pos++) { 290 U32 const candidateDist = DELTANEXTU16(chainTable, matchIndex + pos); 291 if (candidateDist > distanceToNextMatch) { 292 distanceToNextMatch = candidateDist; 293 matchChainPos = pos; 294 } } 295 if (distanceToNextMatch > 1) { 296 if (distanceToNextMatch > matchIndex) break; /* avoid overflow */ 297 matchIndex -= distanceToNextMatch; 298 continue; 299 } } } 300 301 { U32 const distNextMatch = DELTANEXTU16(chainTable, matchIndex); 302 if (patternAnalysis && distNextMatch==1 && matchChainPos==0) { 303 U32 const matchCandidateIdx = matchIndex-1; 304 /* may be a repeated pattern */ 305 if (repeat == rep_untested) { 306 if ( ((pattern & 0xFFFF) == (pattern >> 16)) 307 & ((pattern & 0xFF) == (pattern >> 24)) ) { 308 repeat = rep_confirmed; 309 srcPatternLength = LZ4HC_countPattern(ip+sizeof(pattern), iHighLimit, pattern) + sizeof(pattern); 310 } else { 311 repeat = rep_not; 312 } } 313 if ( (repeat == rep_confirmed) 314 && (matchCandidateIdx >= dictLimit) ) { /* same segment only */ 315 const BYTE* const matchPtr = base + matchCandidateIdx; 316 if (LZ4_read32(matchPtr) == pattern) { /* good candidate */ 317 size_t const forwardPatternLength = LZ4HC_countPattern(matchPtr+sizeof(pattern), iHighLimit, pattern) + sizeof(pattern); 318 const BYTE* const lowestMatchPtr = (lowPrefixPtr + MAX_DISTANCE >= ip) ? lowPrefixPtr : ip - MAX_DISTANCE; 319 size_t const backLength = LZ4HC_reverseCountPattern(matchPtr, lowestMatchPtr, pattern); 320 size_t const currentSegmentLength = backLength + forwardPatternLength; 321 322 if ( (currentSegmentLength >= srcPatternLength) /* current pattern segment large enough to contain full srcPatternLength */ 323 && (forwardPatternLength <= srcPatternLength) ) { /* haven't reached this position yet */ 324 matchIndex = matchCandidateIdx + (U32)forwardPatternLength - (U32)srcPatternLength; /* best position, full pattern, might be followed by more match */ 325 } else { 326 matchIndex = matchCandidateIdx - (U32)backLength; /* farthest position in current segment, will find a match of length currentSegmentLength + maybe some back */ 327 if (lookBackLength==0) { /* no back possible */ 328 size_t const maxML = MIN(currentSegmentLength, srcPatternLength); 329 if ((size_t)longest < maxML) { 330 assert(base + matchIndex < ip); 331 if (ip - (base+matchIndex) > MAX_DISTANCE) break; 332 assert(maxML < 2 GB); 333 longest = (int)maxML; 334 *matchpos = base + matchIndex; /* virtual pos, relative to ip, to retrieve offset */ 335 *startpos = ip; 336 } 337 { U32 const distToNextPattern = DELTANEXTU16(chainTable, matchIndex); 338 if (distToNextPattern > matchIndex) break; /* avoid overflow */ 339 matchIndex -= distToNextPattern; 340 } } } 341 continue; 342 } } 343 } } /* PA optimization */ 344 345 /* follow current chain */ 346 matchIndex -= DELTANEXTU16(chainTable, matchIndex+matchChainPos); 347 348 } /* while ((matchIndex>=lowestMatchIndex) && (nbAttempts)) */ 349 350 if (dict == usingDictCtx && nbAttempts && ipIndex - lowestMatchIndex < MAX_DISTANCE) { 351 size_t const dictEndOffset = dictCtx->end - dictCtx->base; 352 assert(dictEndOffset <= 1 GB); 353 dictMatchIndex = dictCtx->hashTable[LZ4HC_hashPtr(ip)]; 354 matchIndex = dictMatchIndex + lowestMatchIndex - (U32)dictEndOffset; 355 while (ipIndex - matchIndex <= MAX_DISTANCE && nbAttempts--) { 356 const BYTE* const matchPtr = dictCtx->base + dictMatchIndex; 357 358 if (LZ4_read32(matchPtr) == pattern) { 359 int mlt; 360 int back = 0; 361 const BYTE* vLimit = ip + (dictEndOffset - dictMatchIndex); 362 if (vLimit > iHighLimit) vLimit = iHighLimit; 363 mlt = LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, vLimit) + MINMATCH; 364 back = lookBackLength ? LZ4HC_countBack(ip, matchPtr, iLowLimit, dictCtx->base + dictCtx->dictLimit) : 0; 365 mlt -= back; 366 if (mlt > longest) { 367 longest = mlt; 368 *matchpos = base + matchIndex + back; 369 *startpos = ip + back; 370 } 371 } 372 373 { U32 const nextOffset = DELTANEXTU16(dictCtx->chainTable, dictMatchIndex); 374 dictMatchIndex -= nextOffset; 375 matchIndex -= nextOffset; 376 } 377 } 378 } 379 380 return longest; 381 } 382 383 LZ4_FORCE_INLINE 384 int LZ4HC_InsertAndFindBestMatch(LZ4HC_CCtx_internal* const hc4, /* Index table will be updated */ 385 const BYTE* const ip, const BYTE* const iLimit, 386 const BYTE** matchpos, 387 const int maxNbAttempts, 388 const int patternAnalysis, 389 const dictCtx_directive dict) 390 { 391 const BYTE* uselessPtr = ip; 392 /* note : LZ4HC_InsertAndGetWiderMatch() is able to modify the starting position of a match (*startpos), 393 * but this won't be the case here, as we define iLowLimit==ip, 394 * so LZ4HC_InsertAndGetWiderMatch() won't be allowed to search past ip */ 395 return LZ4HC_InsertAndGetWiderMatch(hc4, ip, ip, iLimit, MINMATCH-1, matchpos, &uselessPtr, maxNbAttempts, patternAnalysis, 0 /*chainSwap*/, dict, favorCompressionRatio); 396 } 397 398 399 400 typedef enum { 401 noLimit = 0, 402 limitedOutput = 1, 403 limitedDestSize = 2, 404 } limitedOutput_directive; 405 406 /* LZ4HC_encodeSequence() : 407 * @return : 0 if ok, 408 * 1 if buffer issue detected */ 409 LZ4_FORCE_INLINE int LZ4HC_encodeSequence ( 410 const BYTE** ip, 411 BYTE** op, 412 const BYTE** anchor, 413 int matchLength, 414 const BYTE* const match, 415 limitedOutput_directive limit, 416 BYTE* oend) 417 { 418 size_t length; 419 BYTE* const token = (*op)++; 420 421 #if defined(LZ4_DEBUG) && (LZ4_DEBUG >= 6) 422 static const BYTE* start = NULL; 423 static U32 totalCost = 0; 424 U32 const pos = (start==NULL) ? 0 : (U32)(*anchor - start); 425 U32 const ll = (U32)(*ip - *anchor); 426 U32 const llAdd = (ll>=15) ? ((ll-15) / 255) + 1 : 0; 427 U32 const mlAdd = (matchLength>=19) ? ((matchLength-19) / 255) + 1 : 0; 428 U32 const cost = 1 + llAdd + ll + 2 + mlAdd; 429 if (start==NULL) start = *anchor; /* only works for single segment */ 430 /* g_debuglog_enable = (pos >= 2228) & (pos <= 2262); */ 431 DEBUGLOG(6, "pos:%7u -- literals:%3u, match:%4i, offset:%5u, cost:%3u + %u", 432 pos, 433 (U32)(*ip - *anchor), matchLength, (U32)(*ip-match), 434 cost, totalCost); 435 totalCost += cost; 436 #endif 437 438 /* Encode Literal length */ 439 length = (size_t)(*ip - *anchor); 440 if ((limit) && ((*op + (length >> 8) + length + (2 + 1 + LASTLITERALS)) > oend)) return 1; /* Check output limit */ 441 if (length >= RUN_MASK) { 442 size_t len = length - RUN_MASK; 443 *token = (RUN_MASK << ML_BITS); 444 for(; len >= 255 ; len -= 255) *(*op)++ = 255; 445 *(*op)++ = (BYTE)len; 446 } else { 447 *token = (BYTE)(length << ML_BITS); 448 } 449 450 /* Copy Literals */ 451 LZ4_wildCopy(*op, *anchor, (*op) + length); 452 *op += length; 453 454 /* Encode Offset */ 455 assert( (*ip - match) <= MAX_DISTANCE ); /* note : consider providing offset as a value, rather than as a pointer difference */ 456 LZ4_writeLE16(*op, (U16)(*ip-match)); *op += 2; 457 458 /* Encode MatchLength */ 459 assert(matchLength >= MINMATCH); 460 length = (size_t)(matchLength - MINMATCH); 461 if ((limit) && (*op + (length >> 8) + (1 + LASTLITERALS) > oend)) return 1; /* Check output limit */ 462 if (length >= ML_MASK) { 463 *token += ML_MASK; 464 length -= ML_MASK; 465 for(; length >= 510 ; length -= 510) { *(*op)++ = 255; *(*op)++ = 255; } 466 if (length >= 255) { length -= 255; *(*op)++ = 255; } 467 *(*op)++ = (BYTE)length; 468 } else { 469 *token += (BYTE)(length); 470 } 471 472 /* Prepare next loop */ 473 *ip += matchLength; 474 *anchor = *ip; 475 476 return 0; 477 } 478 479 LZ4_FORCE_INLINE int LZ4HC_compress_hashChain ( 480 LZ4HC_CCtx_internal* const ctx, 481 const char* const source, 482 char* const dest, 483 int* srcSizePtr, 484 int const maxOutputSize, 485 unsigned maxNbAttempts, 486 const limitedOutput_directive limit, 487 const dictCtx_directive dict 488 ) 489 { 490 const int inputSize = *srcSizePtr; 491 const int patternAnalysis = (maxNbAttempts > 128); /* levels 9+ */ 492 493 const BYTE* ip = (const BYTE*) source; 494 const BYTE* anchor = ip; 495 const BYTE* const iend = ip + inputSize; 496 const BYTE* const mflimit = iend - MFLIMIT; 497 const BYTE* const matchlimit = (iend - LASTLITERALS); 498 499 BYTE* optr = (BYTE*) dest; 500 BYTE* op = (BYTE*) dest; 501 BYTE* oend = op + maxOutputSize; 502 503 int ml0, ml, ml2, ml3; 504 const BYTE* start0; 505 const BYTE* ref0; 506 const BYTE* ref = NULL; 507 const BYTE* start2 = NULL; 508 const BYTE* ref2 = NULL; 509 const BYTE* start3 = NULL; 510 const BYTE* ref3 = NULL; 511 512 /* init */ 513 *srcSizePtr = 0; 514 if (limit == limitedDestSize) oend -= LASTLITERALS; /* Hack for support LZ4 format restriction */ 515 if (inputSize < LZ4_minLength) goto _last_literals; /* Input too small, no compression (all literals) */ 516 517 /* Main Loop */ 518 while (ip <= mflimit) { 519 ml = LZ4HC_InsertAndFindBestMatch (ctx, ip, matchlimit, &ref, maxNbAttempts, patternAnalysis, dict); 520 if (ml<MINMATCH) { ip++; continue; } 521 522 /* saved, in case we would skip too much */ 523 start0 = ip; ref0 = ref; ml0 = ml; 524 525 _Search2: 526 if (ip+ml <= mflimit) { 527 ml2 = LZ4HC_InsertAndGetWiderMatch(ctx, 528 ip + ml - 2, ip + 0, matchlimit, ml, &ref2, &start2, 529 maxNbAttempts, patternAnalysis, 0, dict, favorCompressionRatio); 530 } else { 531 ml2 = ml; 532 } 533 534 if (ml2 == ml) { /* No better match => encode ML1 */ 535 optr = op; 536 if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) goto _dest_overflow; 537 continue; 538 } 539 540 if (start0 < ip) { /* first match was skipped at least once */ 541 if (start2 < ip + ml0) { /* squeezing ML1 between ML0(original ML1) and ML2 */ 542 ip = start0; ref = ref0; ml = ml0; /* restore initial ML1 */ 543 } } 544 545 /* Here, start0==ip */ 546 if ((start2 - ip) < 3) { /* First Match too small : removed */ 547 ml = ml2; 548 ip = start2; 549 ref =ref2; 550 goto _Search2; 551 } 552 553 _Search3: 554 /* At this stage, we have : 555 * ml2 > ml1, and 556 * ip1+3 <= ip2 (usually < ip1+ml1) */ 557 if ((start2 - ip) < OPTIMAL_ML) { 558 int correction; 559 int new_ml = ml; 560 if (new_ml > OPTIMAL_ML) new_ml = OPTIMAL_ML; 561 if (ip+new_ml > start2 + ml2 - MINMATCH) new_ml = (int)(start2 - ip) + ml2 - MINMATCH; 562 correction = new_ml - (int)(start2 - ip); 563 if (correction > 0) { 564 start2 += correction; 565 ref2 += correction; 566 ml2 -= correction; 567 } 568 } 569 /* Now, we have start2 = ip+new_ml, with new_ml = min(ml, OPTIMAL_ML=18) */ 570 571 if (start2 + ml2 <= mflimit) { 572 ml3 = LZ4HC_InsertAndGetWiderMatch(ctx, 573 start2 + ml2 - 3, start2, matchlimit, ml2, &ref3, &start3, 574 maxNbAttempts, patternAnalysis, 0, dict, favorCompressionRatio); 575 } else { 576 ml3 = ml2; 577 } 578 579 if (ml3 == ml2) { /* No better match => encode ML1 and ML2 */ 580 /* ip & ref are known; Now for ml */ 581 if (start2 < ip+ml) ml = (int)(start2 - ip); 582 /* Now, encode 2 sequences */ 583 optr = op; 584 if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) goto _dest_overflow; 585 ip = start2; 586 optr = op; 587 if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml2, ref2, limit, oend)) goto _dest_overflow; 588 continue; 589 } 590 591 if (start3 < ip+ml+3) { /* Not enough space for match 2 : remove it */ 592 if (start3 >= (ip+ml)) { /* can write Seq1 immediately ==> Seq2 is removed, so Seq3 becomes Seq1 */ 593 if (start2 < ip+ml) { 594 int correction = (int)(ip+ml - start2); 595 start2 += correction; 596 ref2 += correction; 597 ml2 -= correction; 598 if (ml2 < MINMATCH) { 599 start2 = start3; 600 ref2 = ref3; 601 ml2 = ml3; 602 } 603 } 604 605 optr = op; 606 if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) goto _dest_overflow; 607 ip = start3; 608 ref = ref3; 609 ml = ml3; 610 611 start0 = start2; 612 ref0 = ref2; 613 ml0 = ml2; 614 goto _Search2; 615 } 616 617 start2 = start3; 618 ref2 = ref3; 619 ml2 = ml3; 620 goto _Search3; 621 } 622 623 /* 624 * OK, now we have 3 ascending matches; 625 * let's write the first one ML1. 626 * ip & ref are known; Now decide ml. 627 */ 628 if (start2 < ip+ml) { 629 if ((start2 - ip) < OPTIMAL_ML) { 630 int correction; 631 if (ml > OPTIMAL_ML) ml = OPTIMAL_ML; 632 if (ip + ml > start2 + ml2 - MINMATCH) ml = (int)(start2 - ip) + ml2 - MINMATCH; 633 correction = ml - (int)(start2 - ip); 634 if (correction > 0) { 635 start2 += correction; 636 ref2 += correction; 637 ml2 -= correction; 638 } 639 } else { 640 ml = (int)(start2 - ip); 641 } 642 } 643 optr = op; 644 if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) goto _dest_overflow; 645 646 /* ML2 becomes ML1 */ 647 ip = start2; ref = ref2; ml = ml2; 648 649 /* ML3 becomes ML2 */ 650 start2 = start3; ref2 = ref3; ml2 = ml3; 651 652 /* let's find a new ML3 */ 653 goto _Search3; 654 } 655 656 _last_literals: 657 /* Encode Last Literals */ 658 { size_t lastRunSize = (size_t)(iend - anchor); /* literals */ 659 size_t litLength = (lastRunSize + 255 - RUN_MASK) / 255; 660 size_t const totalSize = 1 + litLength + lastRunSize; 661 if (limit == limitedDestSize) oend += LASTLITERALS; /* restore correct value */ 662 if (limit && (op + totalSize > oend)) { 663 if (limit == limitedOutput) return 0; /* Check output limit */ 664 /* adapt lastRunSize to fill 'dest' */ 665 lastRunSize = (size_t)(oend - op) - 1; 666 litLength = (lastRunSize + 255 - RUN_MASK) / 255; 667 lastRunSize -= litLength; 668 } 669 ip = anchor + lastRunSize; 670 671 if (lastRunSize >= RUN_MASK) { 672 size_t accumulator = lastRunSize - RUN_MASK; 673 *op++ = (RUN_MASK << ML_BITS); 674 for(; accumulator >= 255 ; accumulator -= 255) *op++ = 255; 675 *op++ = (BYTE) accumulator; 676 } else { 677 *op++ = (BYTE)(lastRunSize << ML_BITS); 678 } 679 memcpy(op, anchor, lastRunSize); 680 op += lastRunSize; 681 } 682 683 /* End */ 684 *srcSizePtr = (int) (((const char*)ip) - source); 685 return (int) (((char*)op)-dest); 686 687 _dest_overflow: 688 if (limit == limitedDestSize) { 689 op = optr; /* restore correct out pointer */ 690 goto _last_literals; 691 } 692 return 0; 693 } 694 695 696 static int LZ4HC_compress_optimal( LZ4HC_CCtx_internal* ctx, 697 const char* const source, char* dst, 698 int* srcSizePtr, int dstCapacity, 699 int const nbSearches, size_t sufficient_len, 700 const limitedOutput_directive limit, int const fullUpdate, 701 const dictCtx_directive dict, 702 HCfavor_e favorDecSpeed); 703 704 705 LZ4_FORCE_INLINE int LZ4HC_compress_generic_internal ( 706 LZ4HC_CCtx_internal* const ctx, 707 const char* const src, 708 char* const dst, 709 int* const srcSizePtr, 710 int const dstCapacity, 711 int cLevel, 712 const limitedOutput_directive limit, 713 const dictCtx_directive dict 714 ) 715 { 716 typedef enum { lz4hc, lz4opt } lz4hc_strat_e; 717 typedef struct { 718 lz4hc_strat_e strat; 719 U32 nbSearches; 720 U32 targetLength; 721 } cParams_t; 722 static const cParams_t clTable[LZ4HC_CLEVEL_MAX+1] = { 723 { lz4hc, 2, 16 }, /* 0, unused */ 724 { lz4hc, 2, 16 }, /* 1, unused */ 725 { lz4hc, 2, 16 }, /* 2, unused */ 726 { lz4hc, 4, 16 }, /* 3 */ 727 { lz4hc, 8, 16 }, /* 4 */ 728 { lz4hc, 16, 16 }, /* 5 */ 729 { lz4hc, 32, 16 }, /* 6 */ 730 { lz4hc, 64, 16 }, /* 7 */ 731 { lz4hc, 128, 16 }, /* 8 */ 732 { lz4hc, 256, 16 }, /* 9 */ 733 { lz4opt, 96, 64 }, /*10==LZ4HC_CLEVEL_OPT_MIN*/ 734 { lz4opt, 512,128 }, /*11 */ 735 { lz4opt,16384,LZ4_OPT_NUM }, /* 12==LZ4HC_CLEVEL_MAX */ 736 }; 737 738 DEBUGLOG(4, "LZ4HC_compress_generic(%p, %p, %d)", ctx, src, *srcSizePtr); 739 740 if (limit == limitedDestSize && dstCapacity < 1) return 0; /* Impossible to store anything */ 741 if ((U32)*srcSizePtr > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported input size (too large or negative) */ 742 743 ctx->end += *srcSizePtr; 744 if (cLevel < 1) cLevel = LZ4HC_CLEVEL_DEFAULT; /* note : convention is different from lz4frame, maybe something to review */ 745 cLevel = MIN(LZ4HC_CLEVEL_MAX, cLevel); 746 { cParams_t const cParam = clTable[cLevel]; 747 HCfavor_e const favor = ctx->favorDecSpeed ? favorDecompressionSpeed : favorCompressionRatio; 748 if (cParam.strat == lz4hc) 749 return LZ4HC_compress_hashChain(ctx, 750 src, dst, srcSizePtr, dstCapacity, 751 cParam.nbSearches, limit, dict); 752 assert(cParam.strat == lz4opt); 753 return LZ4HC_compress_optimal(ctx, 754 src, dst, srcSizePtr, dstCapacity, 755 cParam.nbSearches, cParam.targetLength, limit, 756 cLevel == LZ4HC_CLEVEL_MAX, /* ultra mode */ 757 dict, favor); 758 } 759 } 760 761 static void LZ4HC_setExternalDict(LZ4HC_CCtx_internal* ctxPtr, const BYTE* newBlock); 762 763 static int LZ4HC_compress_generic_noDictCtx ( 764 LZ4HC_CCtx_internal* const ctx, 765 const char* const src, 766 char* const dst, 767 int* const srcSizePtr, 768 int const dstCapacity, 769 int cLevel, 770 limitedOutput_directive limit 771 ) 772 { 773 assert(ctx->dictCtx == NULL); 774 return LZ4HC_compress_generic_internal(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit, noDictCtx); 775 } 776 777 static int LZ4HC_compress_generic_dictCtx ( 778 LZ4HC_CCtx_internal* const ctx, 779 const char* const src, 780 char* const dst, 781 int* const srcSizePtr, 782 int const dstCapacity, 783 int cLevel, 784 limitedOutput_directive limit 785 ) 786 { 787 const size_t position = ctx->end - ctx->base - ctx->lowLimit; 788 assert(ctx->dictCtx != NULL); 789 if (position >= 64 KB) { 790 ctx->dictCtx = NULL; 791 return LZ4HC_compress_generic_noDictCtx(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit); 792 } else if (position == 0 && *srcSizePtr > 4 KB) { 793 memcpy(ctx, ctx->dictCtx, sizeof(LZ4HC_CCtx_internal)); 794 LZ4HC_setExternalDict(ctx, (const BYTE *)src); 795 ctx->compressionLevel = (short)cLevel; 796 return LZ4HC_compress_generic_noDictCtx(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit); 797 } else { 798 return LZ4HC_compress_generic_internal(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit, usingDictCtx); 799 } 800 } 801 802 static int LZ4HC_compress_generic ( 803 LZ4HC_CCtx_internal* const ctx, 804 const char* const src, 805 char* const dst, 806 int* const srcSizePtr, 807 int const dstCapacity, 808 int cLevel, 809 limitedOutput_directive limit 810 ) 811 { 812 if (ctx->dictCtx == NULL) { 813 return LZ4HC_compress_generic_noDictCtx(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit); 814 } else { 815 return LZ4HC_compress_generic_dictCtx(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit); 816 } 817 } 818 819 820 int LZ4_sizeofStateHC(void) { return sizeof(LZ4_streamHC_t); } 821 822 int LZ4_compress_HC_extStateHC_fastReset (void* state, const char* src, char* dst, int srcSize, int dstCapacity, int compressionLevel) 823 { 824 LZ4HC_CCtx_internal* const ctx = &((LZ4_streamHC_t*)state)->internal_donotuse; 825 if (((size_t)(state)&(sizeof(void*)-1)) != 0) return 0; /* Error : state is not aligned for pointers (32 or 64 bits) */ 826 LZ4_resetStreamHC_fast((LZ4_streamHC_t*)state, compressionLevel); 827 LZ4HC_init (ctx, (const BYTE*)src); 828 if (dstCapacity < LZ4_compressBound(srcSize)) 829 return LZ4HC_compress_generic (ctx, src, dst, &srcSize, dstCapacity, compressionLevel, limitedOutput); 830 else 831 return LZ4HC_compress_generic (ctx, src, dst, &srcSize, dstCapacity, compressionLevel, noLimit); 832 } 833 834 int LZ4_compress_HC_extStateHC (void* state, const char* src, char* dst, int srcSize, int dstCapacity, int compressionLevel) 835 { 836 if (((size_t)(state)&(sizeof(void*)-1)) != 0) return 0; /* Error : state is not aligned for pointers (32 or 64 bits) */ 837 LZ4_resetStreamHC ((LZ4_streamHC_t*)state, compressionLevel); 838 return LZ4_compress_HC_extStateHC_fastReset(state, src, dst, srcSize, dstCapacity, compressionLevel); 839 } 840 841 int LZ4_compress_HC(const char* src, char* dst, int srcSize, int dstCapacity, int compressionLevel) 842 { 843 #if defined(LZ4HC_HEAPMODE) && LZ4HC_HEAPMODE==1 844 LZ4_streamHC_t* const statePtr = (LZ4_streamHC_t*)ALLOC(sizeof(LZ4_streamHC_t)); 845 #else 846 LZ4_streamHC_t state; 847 LZ4_streamHC_t* const statePtr = &state; 848 #endif 849 int const cSize = LZ4_compress_HC_extStateHC(statePtr, src, dst, srcSize, dstCapacity, compressionLevel); 850 #if defined(LZ4HC_HEAPMODE) && LZ4HC_HEAPMODE==1 851 free(statePtr); 852 #endif 853 return cSize; 854 } 855 856 /* LZ4_compress_HC_destSize() : 857 * only compatible with regular HC parser */ 858 int LZ4_compress_HC_destSize(void* LZ4HC_Data, const char* source, char* dest, int* sourceSizePtr, int targetDestSize, int cLevel) 859 { 860 LZ4HC_CCtx_internal* const ctx = &((LZ4_streamHC_t*)LZ4HC_Data)->internal_donotuse; 861 LZ4_resetStreamHC((LZ4_streamHC_t*)LZ4HC_Data, cLevel); 862 LZ4HC_init(ctx, (const BYTE*) source); 863 return LZ4HC_compress_generic(ctx, source, dest, sourceSizePtr, targetDestSize, cLevel, limitedDestSize); 864 } 865 866 867 868 /************************************** 869 * Streaming Functions 870 **************************************/ 871 /* allocation */ 872 LZ4_streamHC_t* LZ4_createStreamHC(void) { 873 LZ4_streamHC_t* const LZ4_streamHCPtr = (LZ4_streamHC_t*)ALLOC(sizeof(LZ4_streamHC_t)); 874 if (LZ4_streamHCPtr==NULL) return NULL; 875 LZ4_resetStreamHC(LZ4_streamHCPtr, LZ4HC_CLEVEL_DEFAULT); 876 return LZ4_streamHCPtr; 877 } 878 879 int LZ4_freeStreamHC (LZ4_streamHC_t* LZ4_streamHCPtr) { 880 DEBUGLOG(4, "LZ4_freeStreamHC(%p)", LZ4_streamHCPtr); 881 if (!LZ4_streamHCPtr) return 0; /* support free on NULL */ 882 free(LZ4_streamHCPtr); 883 return 0; 884 } 885 886 887 /* initialization */ 888 void LZ4_resetStreamHC (LZ4_streamHC_t* LZ4_streamHCPtr, int compressionLevel) 889 { 890 LZ4_STATIC_ASSERT(sizeof(LZ4HC_CCtx_internal) <= sizeof(size_t) * LZ4_STREAMHCSIZE_SIZET); /* if compilation fails here, LZ4_STREAMHCSIZE must be increased */ 891 DEBUGLOG(4, "LZ4_resetStreamHC(%p, %d)", LZ4_streamHCPtr, compressionLevel); 892 LZ4_streamHCPtr->internal_donotuse.end = (const BYTE *)(ptrdiff_t)-1; 893 LZ4_streamHCPtr->internal_donotuse.base = NULL; 894 LZ4_streamHCPtr->internal_donotuse.dictCtx = NULL; 895 LZ4_streamHCPtr->internal_donotuse.favorDecSpeed = 0; 896 LZ4_setCompressionLevel(LZ4_streamHCPtr, compressionLevel); 897 } 898 899 void LZ4_resetStreamHC_fast (LZ4_streamHC_t* LZ4_streamHCPtr, int compressionLevel) 900 { 901 DEBUGLOG(4, "LZ4_resetStreamHC_fast(%p, %d)", LZ4_streamHCPtr, compressionLevel); 902 LZ4_streamHCPtr->internal_donotuse.end -= (uptrval)LZ4_streamHCPtr->internal_donotuse.base; 903 LZ4_streamHCPtr->internal_donotuse.base = NULL; 904 LZ4_streamHCPtr->internal_donotuse.dictCtx = NULL; 905 LZ4_setCompressionLevel(LZ4_streamHCPtr, compressionLevel); 906 } 907 908 void LZ4_setCompressionLevel(LZ4_streamHC_t* LZ4_streamHCPtr, int compressionLevel) 909 { 910 if (compressionLevel < 1) compressionLevel = LZ4HC_CLEVEL_DEFAULT; 911 if (compressionLevel > LZ4HC_CLEVEL_MAX) compressionLevel = LZ4HC_CLEVEL_MAX; 912 LZ4_streamHCPtr->internal_donotuse.compressionLevel = (short)compressionLevel; 913 } 914 915 void LZ4_favorDecompressionSpeed(LZ4_streamHC_t* LZ4_streamHCPtr, int favor) 916 { 917 LZ4_streamHCPtr->internal_donotuse.favorDecSpeed = (favor!=0); 918 } 919 920 int LZ4_loadDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, const char* dictionary, int dictSize) 921 { 922 LZ4HC_CCtx_internal* const ctxPtr = &LZ4_streamHCPtr->internal_donotuse; 923 DEBUGLOG(4, "LZ4_loadDictHC(%p, %p, %d)", LZ4_streamHCPtr, dictionary, dictSize); 924 if (dictSize > 64 KB) { 925 dictionary += dictSize - 64 KB; 926 dictSize = 64 KB; 927 } 928 LZ4_resetStreamHC(LZ4_streamHCPtr, ctxPtr->compressionLevel); 929 LZ4HC_init (ctxPtr, (const BYTE*)dictionary); 930 ctxPtr->end = (const BYTE*)dictionary + dictSize; 931 if (dictSize >= 4) LZ4HC_Insert (ctxPtr, ctxPtr->end-3); 932 return dictSize; 933 } 934 935 void LZ4_attach_HC_dictionary(LZ4_streamHC_t *working_stream, const LZ4_streamHC_t *dictionary_stream) { 936 working_stream->internal_donotuse.dictCtx = dictionary_stream != NULL ? &(dictionary_stream->internal_donotuse) : NULL; 937 } 938 939 /* compression */ 940 941 static void LZ4HC_setExternalDict(LZ4HC_CCtx_internal* ctxPtr, const BYTE* newBlock) 942 { 943 DEBUGLOG(4, "LZ4HC_setExternalDict(%p, %p)", ctxPtr, newBlock); 944 if (ctxPtr->end >= ctxPtr->base + ctxPtr->dictLimit + 4) 945 LZ4HC_Insert (ctxPtr, ctxPtr->end-3); /* Referencing remaining dictionary content */ 946 947 /* Only one memory segment for extDict, so any previous extDict is lost at this stage */ 948 ctxPtr->lowLimit = ctxPtr->dictLimit; 949 ctxPtr->dictLimit = (U32)(ctxPtr->end - ctxPtr->base); 950 ctxPtr->dictBase = ctxPtr->base; 951 ctxPtr->base = newBlock - ctxPtr->dictLimit; 952 ctxPtr->end = newBlock; 953 ctxPtr->nextToUpdate = ctxPtr->dictLimit; /* match referencing will resume from there */ 954 } 955 956 static int LZ4_compressHC_continue_generic (LZ4_streamHC_t* LZ4_streamHCPtr, 957 const char* src, char* dst, 958 int* srcSizePtr, int dstCapacity, 959 limitedOutput_directive limit) 960 { 961 LZ4HC_CCtx_internal* const ctxPtr = &LZ4_streamHCPtr->internal_donotuse; 962 DEBUGLOG(4, "LZ4_compressHC_continue_generic(%p, %p, %d)", LZ4_streamHCPtr, src, *srcSizePtr); 963 /* auto-init if forgotten */ 964 if (ctxPtr->base == NULL) LZ4HC_init (ctxPtr, (const BYTE*) src); 965 966 /* Check overflow */ 967 if ((size_t)(ctxPtr->end - ctxPtr->base) > 2 GB) { 968 size_t dictSize = (size_t)(ctxPtr->end - ctxPtr->base) - ctxPtr->dictLimit; 969 if (dictSize > 64 KB) dictSize = 64 KB; 970 LZ4_loadDictHC(LZ4_streamHCPtr, (const char*)(ctxPtr->end) - dictSize, (int)dictSize); 971 } 972 973 /* Check if blocks follow each other */ 974 if ((const BYTE*)src != ctxPtr->end) LZ4HC_setExternalDict(ctxPtr, (const BYTE*)src); 975 976 /* Check overlapping input/dictionary space */ 977 { const BYTE* sourceEnd = (const BYTE*) src + *srcSizePtr; 978 const BYTE* const dictBegin = ctxPtr->dictBase + ctxPtr->lowLimit; 979 const BYTE* const dictEnd = ctxPtr->dictBase + ctxPtr->dictLimit; 980 if ((sourceEnd > dictBegin) && ((const BYTE*)src < dictEnd)) { 981 if (sourceEnd > dictEnd) sourceEnd = dictEnd; 982 ctxPtr->lowLimit = (U32)(sourceEnd - ctxPtr->dictBase); 983 if (ctxPtr->dictLimit - ctxPtr->lowLimit < 4) ctxPtr->lowLimit = ctxPtr->dictLimit; 984 } 985 } 986 987 return LZ4HC_compress_generic (ctxPtr, src, dst, srcSizePtr, dstCapacity, ctxPtr->compressionLevel, limit); 988 } 989 990 int LZ4_compress_HC_continue (LZ4_streamHC_t* LZ4_streamHCPtr, const char* src, char* dst, int srcSize, int dstCapacity) 991 { 992 if (dstCapacity < LZ4_compressBound(srcSize)) 993 return LZ4_compressHC_continue_generic (LZ4_streamHCPtr, src, dst, &srcSize, dstCapacity, limitedOutput); 994 else 995 return LZ4_compressHC_continue_generic (LZ4_streamHCPtr, src, dst, &srcSize, dstCapacity, noLimit); 996 } 997 998 int LZ4_compress_HC_continue_destSize (LZ4_streamHC_t* LZ4_streamHCPtr, const char* src, char* dst, int* srcSizePtr, int targetDestSize) 999 { 1000 return LZ4_compressHC_continue_generic(LZ4_streamHCPtr, src, dst, srcSizePtr, targetDestSize, limitedDestSize); 1001 } 1002 1003 1004 1005 /* dictionary saving */ 1006 1007 int LZ4_saveDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, char* safeBuffer, int dictSize) 1008 { 1009 LZ4HC_CCtx_internal* const streamPtr = &LZ4_streamHCPtr->internal_donotuse; 1010 int const prefixSize = (int)(streamPtr->end - (streamPtr->base + streamPtr->dictLimit)); 1011 DEBUGLOG(4, "LZ4_saveDictHC(%p, %p, %d)", LZ4_streamHCPtr, safeBuffer, dictSize); 1012 if (dictSize > 64 KB) dictSize = 64 KB; 1013 if (dictSize < 4) dictSize = 0; 1014 if (dictSize > prefixSize) dictSize = prefixSize; 1015 memmove(safeBuffer, streamPtr->end - dictSize, dictSize); 1016 { U32 const endIndex = (U32)(streamPtr->end - streamPtr->base); 1017 streamPtr->end = (const BYTE*)safeBuffer + dictSize; 1018 streamPtr->base = streamPtr->end - endIndex; 1019 streamPtr->dictLimit = endIndex - dictSize; 1020 streamPtr->lowLimit = endIndex - dictSize; 1021 if (streamPtr->nextToUpdate < streamPtr->dictLimit) streamPtr->nextToUpdate = streamPtr->dictLimit; 1022 } 1023 return dictSize; 1024 } 1025 1026 1027 /*********************************** 1028 * Deprecated Functions 1029 ***********************************/ 1030 /* These functions currently generate deprecation warnings */ 1031 /* Deprecated compression functions */ 1032 int LZ4_compressHC(const char* src, char* dst, int srcSize) { return LZ4_compress_HC (src, dst, srcSize, LZ4_compressBound(srcSize), 0); } 1033 int LZ4_compressHC_limitedOutput(const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_HC(src, dst, srcSize, maxDstSize, 0); } 1034 int LZ4_compressHC2(const char* src, char* dst, int srcSize, int cLevel) { return LZ4_compress_HC (src, dst, srcSize, LZ4_compressBound(srcSize), cLevel); } 1035 int LZ4_compressHC2_limitedOutput(const char* src, char* dst, int srcSize, int maxDstSize, int cLevel) { return LZ4_compress_HC(src, dst, srcSize, maxDstSize, cLevel); } 1036 int LZ4_compressHC_withStateHC (void* state, const char* src, char* dst, int srcSize) { return LZ4_compress_HC_extStateHC (state, src, dst, srcSize, LZ4_compressBound(srcSize), 0); } 1037 int LZ4_compressHC_limitedOutput_withStateHC (void* state, const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_HC_extStateHC (state, src, dst, srcSize, maxDstSize, 0); } 1038 int LZ4_compressHC2_withStateHC (void* state, const char* src, char* dst, int srcSize, int cLevel) { return LZ4_compress_HC_extStateHC(state, src, dst, srcSize, LZ4_compressBound(srcSize), cLevel); } 1039 int LZ4_compressHC2_limitedOutput_withStateHC (void* state, const char* src, char* dst, int srcSize, int maxDstSize, int cLevel) { return LZ4_compress_HC_extStateHC(state, src, dst, srcSize, maxDstSize, cLevel); } 1040 int LZ4_compressHC_continue (LZ4_streamHC_t* ctx, const char* src, char* dst, int srcSize) { return LZ4_compress_HC_continue (ctx, src, dst, srcSize, LZ4_compressBound(srcSize)); } 1041 int LZ4_compressHC_limitedOutput_continue (LZ4_streamHC_t* ctx, const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_HC_continue (ctx, src, dst, srcSize, maxDstSize); } 1042 1043 1044 /* Deprecated streaming functions */ 1045 int LZ4_sizeofStreamStateHC(void) { return LZ4_STREAMHCSIZE; } 1046 1047 int LZ4_resetStreamStateHC(void* state, char* inputBuffer) 1048 { 1049 LZ4HC_CCtx_internal *ctx = &((LZ4_streamHC_t*)state)->internal_donotuse; 1050 if ((((size_t)state) & (sizeof(void*)-1)) != 0) return 1; /* Error : pointer is not aligned for pointer (32 or 64 bits) */ 1051 LZ4_resetStreamHC((LZ4_streamHC_t*)state, ((LZ4_streamHC_t*)state)->internal_donotuse.compressionLevel); 1052 LZ4HC_init(ctx, (const BYTE*)inputBuffer); 1053 return 0; 1054 } 1055 1056 void* LZ4_createHC (const char* inputBuffer) 1057 { 1058 LZ4_streamHC_t* hc4 = (LZ4_streamHC_t*)ALLOC(sizeof(LZ4_streamHC_t)); 1059 if (hc4 == NULL) return NULL; /* not enough memory */ 1060 LZ4_resetStreamHC(hc4, 0 /* compressionLevel */); 1061 LZ4HC_init (&hc4->internal_donotuse, (const BYTE*)inputBuffer); 1062 return hc4; 1063 } 1064 1065 int LZ4_freeHC (void* LZ4HC_Data) { 1066 if (!LZ4HC_Data) return 0; /* support free on NULL */ 1067 FREEMEM(LZ4HC_Data); 1068 return 0; 1069 } 1070 1071 int LZ4_compressHC2_continue (void* LZ4HC_Data, const char* src, char* dst, int srcSize, int cLevel) 1072 { 1073 return LZ4HC_compress_generic (&((LZ4_streamHC_t*)LZ4HC_Data)->internal_donotuse, src, dst, &srcSize, 0, cLevel, noLimit); 1074 } 1075 1076 int LZ4_compressHC2_limitedOutput_continue (void* LZ4HC_Data, const char* src, char* dst, int srcSize, int dstCapacity, int cLevel) 1077 { 1078 return LZ4HC_compress_generic (&((LZ4_streamHC_t*)LZ4HC_Data)->internal_donotuse, src, dst, &srcSize, dstCapacity, cLevel, limitedOutput); 1079 } 1080 1081 char* LZ4_slideInputBufferHC(void* LZ4HC_Data) 1082 { 1083 LZ4_streamHC_t *ctx = (LZ4_streamHC_t*)LZ4HC_Data; 1084 const BYTE *bufferStart = ctx->internal_donotuse.base + ctx->internal_donotuse.lowLimit; 1085 LZ4_resetStreamHC_fast(ctx, ctx->internal_donotuse.compressionLevel); 1086 /* avoid const char * -> char * conversion warning :( */ 1087 return (char *)(uptrval)bufferStart; 1088 } 1089 1090 1091 /* ================================================ 1092 * LZ4 Optimal parser (levels 10-12) 1093 * ===============================================*/ 1094 typedef struct { 1095 int price; 1096 int off; 1097 int mlen; 1098 int litlen; 1099 } LZ4HC_optimal_t; 1100 1101 /* price in bytes */ 1102 LZ4_FORCE_INLINE int LZ4HC_literalsPrice(int const litlen) 1103 { 1104 int price = litlen; 1105 if (litlen >= (int)RUN_MASK) 1106 price += 1 + (litlen-RUN_MASK)/255; 1107 return price; 1108 } 1109 1110 1111 /* requires mlen >= MINMATCH */ 1112 LZ4_FORCE_INLINE int LZ4HC_sequencePrice(int litlen, int mlen) 1113 { 1114 int price = 1 + 2 ; /* token + 16-bit offset */ 1115 1116 price += LZ4HC_literalsPrice(litlen); 1117 1118 if (mlen >= (int)(ML_MASK+MINMATCH)) 1119 price += 1 + (mlen-(ML_MASK+MINMATCH))/255; 1120 1121 return price; 1122 } 1123 1124 1125 typedef struct { 1126 int off; 1127 int len; 1128 } LZ4HC_match_t; 1129 1130 LZ4_FORCE_INLINE LZ4HC_match_t 1131 LZ4HC_FindLongerMatch(LZ4HC_CCtx_internal* const ctx, 1132 const BYTE* ip, const BYTE* const iHighLimit, 1133 int minLen, int nbSearches, 1134 const dictCtx_directive dict, 1135 const HCfavor_e favorDecSpeed) 1136 { 1137 LZ4HC_match_t match = { 0 , 0 }; 1138 const BYTE* matchPtr = NULL; 1139 /* note : LZ4HC_InsertAndGetWiderMatch() is able to modify the starting position of a match (*startpos), 1140 * but this won't be the case here, as we define iLowLimit==ip, 1141 * so LZ4HC_InsertAndGetWiderMatch() won't be allowed to search past ip */ 1142 int matchLength = LZ4HC_InsertAndGetWiderMatch(ctx, ip, ip, iHighLimit, minLen, &matchPtr, &ip, nbSearches, 1 /*patternAnalysis*/, 1 /*chainSwap*/, dict, favorDecSpeed); 1143 if (matchLength <= minLen) return match; 1144 if (favorDecSpeed) { 1145 if ((matchLength>18) & (matchLength<=36)) matchLength=18; /* favor shortcut */ 1146 } 1147 match.len = matchLength; 1148 match.off = (int)(ip-matchPtr); 1149 return match; 1150 } 1151 1152 1153 static int LZ4HC_compress_optimal ( LZ4HC_CCtx_internal* ctx, 1154 const char* const source, 1155 char* dst, 1156 int* srcSizePtr, 1157 int dstCapacity, 1158 int const nbSearches, 1159 size_t sufficient_len, 1160 const limitedOutput_directive limit, 1161 int const fullUpdate, 1162 const dictCtx_directive dict, 1163 const HCfavor_e favorDecSpeed) 1164 { 1165 #define TRAILING_LITERALS 3 1166 LZ4HC_optimal_t opt[LZ4_OPT_NUM + TRAILING_LITERALS]; /* ~64 KB, which is a bit large for stack... */ 1167 1168 const BYTE* ip = (const BYTE*) source; 1169 const BYTE* anchor = ip; 1170 const BYTE* const iend = ip + *srcSizePtr; 1171 const BYTE* const mflimit = iend - MFLIMIT; 1172 const BYTE* const matchlimit = iend - LASTLITERALS; 1173 BYTE* op = (BYTE*) dst; 1174 BYTE* opSaved = (BYTE*) dst; 1175 BYTE* oend = op + dstCapacity; 1176 1177 /* init */ 1178 DEBUGLOG(5, "LZ4HC_compress_optimal"); 1179 *srcSizePtr = 0; 1180 if (limit == limitedDestSize) oend -= LASTLITERALS; /* Hack for support LZ4 format restriction */ 1181 if (sufficient_len >= LZ4_OPT_NUM) sufficient_len = LZ4_OPT_NUM-1; 1182 1183 /* Main Loop */ 1184 assert(ip - anchor < LZ4_MAX_INPUT_SIZE); 1185 while (ip <= mflimit) { 1186 int const llen = (int)(ip - anchor); 1187 int best_mlen, best_off; 1188 int cur, last_match_pos = 0; 1189 1190 LZ4HC_match_t const firstMatch = LZ4HC_FindLongerMatch(ctx, ip, matchlimit, MINMATCH-1, nbSearches, dict, favorDecSpeed); 1191 if (firstMatch.len==0) { ip++; continue; } 1192 1193 if ((size_t)firstMatch.len > sufficient_len) { 1194 /* good enough solution : immediate encoding */ 1195 int const firstML = firstMatch.len; 1196 const BYTE* const matchPos = ip - firstMatch.off; 1197 opSaved = op; 1198 if ( LZ4HC_encodeSequence(&ip, &op, &anchor, firstML, matchPos, limit, oend) ) /* updates ip, op and anchor */ 1199 goto _dest_overflow; 1200 continue; 1201 } 1202 1203 /* set prices for first positions (literals) */ 1204 { int rPos; 1205 for (rPos = 0 ; rPos < MINMATCH ; rPos++) { 1206 int const cost = LZ4HC_literalsPrice(llen + rPos); 1207 opt[rPos].mlen = 1; 1208 opt[rPos].off = 0; 1209 opt[rPos].litlen = llen + rPos; 1210 opt[rPos].price = cost; 1211 DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i) -- initial setup", 1212 rPos, cost, opt[rPos].litlen); 1213 } } 1214 /* set prices using initial match */ 1215 { int mlen = MINMATCH; 1216 int const matchML = firstMatch.len; /* necessarily < sufficient_len < LZ4_OPT_NUM */ 1217 int const offset = firstMatch.off; 1218 assert(matchML < LZ4_OPT_NUM); 1219 for ( ; mlen <= matchML ; mlen++) { 1220 int const cost = LZ4HC_sequencePrice(llen, mlen); 1221 opt[mlen].mlen = mlen; 1222 opt[mlen].off = offset; 1223 opt[mlen].litlen = llen; 1224 opt[mlen].price = cost; 1225 DEBUGLOG(7, "rPos:%3i => price:%3i (matchlen=%i) -- initial setup", 1226 mlen, cost, mlen); 1227 } } 1228 last_match_pos = firstMatch.len; 1229 { int addLit; 1230 for (addLit = 1; addLit <= TRAILING_LITERALS; addLit ++) { 1231 opt[last_match_pos+addLit].mlen = 1; /* literal */ 1232 opt[last_match_pos+addLit].off = 0; 1233 opt[last_match_pos+addLit].litlen = addLit; 1234 opt[last_match_pos+addLit].price = opt[last_match_pos].price + LZ4HC_literalsPrice(addLit); 1235 DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i) -- initial setup", 1236 last_match_pos+addLit, opt[last_match_pos+addLit].price, addLit); 1237 } } 1238 1239 /* check further positions */ 1240 for (cur = 1; cur < last_match_pos; cur++) { 1241 const BYTE* const curPtr = ip + cur; 1242 LZ4HC_match_t newMatch; 1243 1244 if (curPtr > mflimit) break; 1245 DEBUGLOG(7, "rPos:%u[%u] vs [%u]%u", 1246 cur, opt[cur].price, opt[cur+1].price, cur+1); 1247 if (fullUpdate) { 1248 /* not useful to search here if next position has same (or lower) cost */ 1249 if ( (opt[cur+1].price <= opt[cur].price) 1250 /* in some cases, next position has same cost, but cost rises sharply after, so a small match would still be beneficial */ 1251 && (opt[cur+MINMATCH].price < opt[cur].price + 3/*min seq price*/) ) 1252 continue; 1253 } else { 1254 /* not useful to search here if next position has same (or lower) cost */ 1255 if (opt[cur+1].price <= opt[cur].price) continue; 1256 } 1257 1258 DEBUGLOG(7, "search at rPos:%u", cur); 1259 if (fullUpdate) 1260 newMatch = LZ4HC_FindLongerMatch(ctx, curPtr, matchlimit, MINMATCH-1, nbSearches, dict, favorDecSpeed); 1261 else 1262 /* only test matches of minimum length; slightly faster, but misses a few bytes */ 1263 newMatch = LZ4HC_FindLongerMatch(ctx, curPtr, matchlimit, last_match_pos - cur, nbSearches, dict, favorDecSpeed); 1264 if (!newMatch.len) continue; 1265 1266 if ( ((size_t)newMatch.len > sufficient_len) 1267 || (newMatch.len + cur >= LZ4_OPT_NUM) ) { 1268 /* immediate encoding */ 1269 best_mlen = newMatch.len; 1270 best_off = newMatch.off; 1271 last_match_pos = cur + 1; 1272 goto encode; 1273 } 1274 1275 /* before match : set price with literals at beginning */ 1276 { int const baseLitlen = opt[cur].litlen; 1277 int litlen; 1278 for (litlen = 1; litlen < MINMATCH; litlen++) { 1279 int const price = opt[cur].price - LZ4HC_literalsPrice(baseLitlen) + LZ4HC_literalsPrice(baseLitlen+litlen); 1280 int const pos = cur + litlen; 1281 if (price < opt[pos].price) { 1282 opt[pos].mlen = 1; /* literal */ 1283 opt[pos].off = 0; 1284 opt[pos].litlen = baseLitlen+litlen; 1285 opt[pos].price = price; 1286 DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i)", 1287 pos, price, opt[pos].litlen); 1288 } } } 1289 1290 /* set prices using match at position = cur */ 1291 { int const matchML = newMatch.len; 1292 int ml = MINMATCH; 1293 1294 assert(cur + newMatch.len < LZ4_OPT_NUM); 1295 for ( ; ml <= matchML ; ml++) { 1296 int const pos = cur + ml; 1297 int const offset = newMatch.off; 1298 int price; 1299 int ll; 1300 DEBUGLOG(7, "testing price rPos %i (last_match_pos=%i)", 1301 pos, last_match_pos); 1302 if (opt[cur].mlen == 1) { 1303 ll = opt[cur].litlen; 1304 price = ((cur > ll) ? opt[cur - ll].price : 0) 1305 + LZ4HC_sequencePrice(ll, ml); 1306 } else { 1307 ll = 0; 1308 price = opt[cur].price + LZ4HC_sequencePrice(0, ml); 1309 } 1310 1311 assert((U32)favorDecSpeed <= 1); 1312 if (pos > last_match_pos+TRAILING_LITERALS 1313 || price <= opt[pos].price - (int)favorDecSpeed) { 1314 DEBUGLOG(7, "rPos:%3i => price:%3i (matchlen=%i)", 1315 pos, price, ml); 1316 assert(pos < LZ4_OPT_NUM); 1317 if ( (ml == matchML) /* last pos of last match */ 1318 && (last_match_pos < pos) ) 1319 last_match_pos = pos; 1320 opt[pos].mlen = ml; 1321 opt[pos].off = offset; 1322 opt[pos].litlen = ll; 1323 opt[pos].price = price; 1324 } } } 1325 /* complete following positions with literals */ 1326 { int addLit; 1327 for (addLit = 1; addLit <= TRAILING_LITERALS; addLit ++) { 1328 opt[last_match_pos+addLit].mlen = 1; /* literal */ 1329 opt[last_match_pos+addLit].off = 0; 1330 opt[last_match_pos+addLit].litlen = addLit; 1331 opt[last_match_pos+addLit].price = opt[last_match_pos].price + LZ4HC_literalsPrice(addLit); 1332 DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i)", last_match_pos+addLit, opt[last_match_pos+addLit].price, addLit); 1333 } } 1334 } /* for (cur = 1; cur <= last_match_pos; cur++) */ 1335 1336 best_mlen = opt[last_match_pos].mlen; 1337 best_off = opt[last_match_pos].off; 1338 cur = last_match_pos - best_mlen; 1339 1340 encode: /* cur, last_match_pos, best_mlen, best_off must be set */ 1341 assert(cur < LZ4_OPT_NUM); 1342 assert(last_match_pos >= 1); /* == 1 when only one candidate */ 1343 DEBUGLOG(6, "reverse traversal, looking for shortest path (last_match_pos=%i)", last_match_pos); 1344 { int candidate_pos = cur; 1345 int selected_matchLength = best_mlen; 1346 int selected_offset = best_off; 1347 while (1) { /* from end to beginning */ 1348 int const next_matchLength = opt[candidate_pos].mlen; /* can be 1, means literal */ 1349 int const next_offset = opt[candidate_pos].off; 1350 DEBUGLOG(7, "pos %i: sequence length %i", candidate_pos, selected_matchLength); 1351 opt[candidate_pos].mlen = selected_matchLength; 1352 opt[candidate_pos].off = selected_offset; 1353 selected_matchLength = next_matchLength; 1354 selected_offset = next_offset; 1355 if (next_matchLength > candidate_pos) break; /* last match elected, first match to encode */ 1356 assert(next_matchLength > 0); /* can be 1, means literal */ 1357 candidate_pos -= next_matchLength; 1358 } } 1359 1360 /* encode all recorded sequences in order */ 1361 { int rPos = 0; /* relative position (to ip) */ 1362 while (rPos < last_match_pos) { 1363 int const ml = opt[rPos].mlen; 1364 int const offset = opt[rPos].off; 1365 if (ml == 1) { ip++; rPos++; continue; } /* literal; note: can end up with several literals, in which case, skip them */ 1366 rPos += ml; 1367 assert(ml >= MINMATCH); 1368 assert((offset >= 1) && (offset <= MAX_DISTANCE)); 1369 opSaved = op; 1370 if ( LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ip - offset, limit, oend) ) /* updates ip, op and anchor */ 1371 goto _dest_overflow; 1372 } } 1373 } /* while (ip <= mflimit) */ 1374 1375 _last_literals: 1376 /* Encode Last Literals */ 1377 { size_t lastRunSize = (size_t)(iend - anchor); /* literals */ 1378 size_t litLength = (lastRunSize + 255 - RUN_MASK) / 255; 1379 size_t const totalSize = 1 + litLength + lastRunSize; 1380 if (limit == limitedDestSize) oend += LASTLITERALS; /* restore correct value */ 1381 if (limit && (op + totalSize > oend)) { 1382 if (limit == limitedOutput) return 0; /* Check output limit */ 1383 /* adapt lastRunSize to fill 'dst' */ 1384 lastRunSize = (size_t)(oend - op) - 1; 1385 litLength = (lastRunSize + 255 - RUN_MASK) / 255; 1386 lastRunSize -= litLength; 1387 } 1388 ip = anchor + lastRunSize; 1389 1390 if (lastRunSize >= RUN_MASK) { 1391 size_t accumulator = lastRunSize - RUN_MASK; 1392 *op++ = (RUN_MASK << ML_BITS); 1393 for(; accumulator >= 255 ; accumulator -= 255) *op++ = 255; 1394 *op++ = (BYTE) accumulator; 1395 } else { 1396 *op++ = (BYTE)(lastRunSize << ML_BITS); 1397 } 1398 memcpy(op, anchor, lastRunSize); 1399 op += lastRunSize; 1400 } 1401 1402 /* End */ 1403 *srcSizePtr = (int) (((const char*)ip) - source); 1404 return (int) ((char*)op-dst); 1405 1406 _dest_overflow: 1407 if (limit == limitedDestSize) { 1408 op = opSaved; /* restore correct out pointer */ 1409 goto _last_literals; 1410 } 1411 return 0; 1412 } 1413
