48
# define LZ4HC_HEAPMODE 1
53
#define LZ4_HC_STATIC_LINKING_ONLY
59
#ifndef LZ4_SRC_INCLUDED
61
# pragma GCC diagnostic ignored "-Wunused-function"
63
# if defined (__clang__)
64
# pragma clang diagnostic ignored "-Wunused-function"
66
# define LZ4_COMMONDEFS_ONLY
72
typedef enum { noDictCtx, usingDictCtxHc } dictCtx_directive;
76
#define OPTIMAL_ML (int)((ML_MASK-1)+MINMATCH)
77
#define LZ4_OPT_NUM (1<<12)
81
#define MIN(a,b) ( (a) < (b) ? (a) : (b) )
82
#define MAX(a,b) ( (a) > (b) ? (a) : (b) )
86
typedef enum { lz4mid, lz4hc, lz4opt } lz4hc_strat_e;
92
static const cParams_t k_clTable[LZ4HC_CLEVEL_MAX+1] = {
105
{ lz4opt,16384,LZ4_OPT_NUM },
108
static cParams_t LZ4HC_getCLevelParams(int cLevel)
113
cLevel = LZ4HC_CLEVEL_DEFAULT;
114
cLevel = MIN(LZ4HC_CLEVEL_MAX, cLevel);
115
return k_clTable[cLevel];
120
#define LZ4HC_HASHSIZE 4
121
#define HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-LZ4HC_HASH_LOG))
122
static U32 LZ4HC_hashPtr(const void* ptr) { return HASH_FUNCTION(LZ4_read32(ptr)); }
124
#if defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==2)
126
static U64 LZ4_read64(const void* memPtr) { return *(const U64*) memPtr; }
128
#elif defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==1)
130
LZ4_PACK(typedef struct { U64 u64; }) LZ4_unalign64;
131
static U64 LZ4_read64(const void* ptr) { return ((const LZ4_unalign64*)ptr)->u64; }
134
static U64 LZ4_read64(const void* memPtr)
136
U64 val; LZ4_memcpy(&val, memPtr, sizeof(val)); return val;
141
#define LZ4MID_HASHSIZE 8
142
#define LZ4MID_HASHLOG (LZ4HC_HASH_LOG-1)
143
#define LZ4MID_HASHTABLESIZE (1 << LZ4MID_HASHLOG)
145
static U32 LZ4MID_hash4(U32 v) { return (v * 2654435761U) >> (32-LZ4MID_HASHLOG); }
146
static U32 LZ4MID_hash4Ptr(const void* ptr) { return LZ4MID_hash4(LZ4_read32(ptr)); }
149
static U32 LZ4MID_hash7(U64 v) { return (U32)(((v << (64-56)) * 58295818150454627ULL) >> (64-LZ4MID_HASHLOG)) ; }
150
static U64 LZ4_readLE64(const void* memPtr);
151
static U32 LZ4MID_hash8Ptr(const void* ptr) { return LZ4MID_hash7(LZ4_readLE64(ptr)); }
153
static U64 LZ4_readLE64(const void* memPtr)
155
if (LZ4_isLittleEndian()) {
156
return LZ4_read64(memPtr);
158
const BYTE* p = (const BYTE*)memPtr;
160
return (U64)p[0] | ((U64)p[1]<<8) | ((U64)p[2]<<16) | ((U64)p[3]<<24)
161
| ((U64)p[4]<<32) | ((U64)p[5]<<40) | ((U64)p[6]<<48) | ((U64)p[7]<<56);
168
unsigned LZ4HC_NbCommonBytes32(U32 val)
171
if (LZ4_isLittleEndian()) {
172
# if defined(_MSC_VER) && (_MSC_VER >= 1400) && !defined(LZ4_FORCE_SW_BITCOUNT)
174
_BitScanReverse(&r, val);
175
return (unsigned)((31 - r) >> 3);
176
# elif (defined(__clang__) || (defined(__GNUC__) && ((__GNUC__ > 3) || \
177
((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))))) && \
178
!defined(LZ4_FORCE_SW_BITCOUNT)
179
return (unsigned)__builtin_clz(val) >> 3;
182
val = ((((val + 0x00FFFF00) | 0x00FFFFFF) + val) |
183
(val + 0x00FF0000)) >> 24;
184
return (unsigned)val ^ 3;
187
# if defined(_MSC_VER) && (_MSC_VER >= 1400) && !defined(LZ4_FORCE_SW_BITCOUNT)
189
_BitScanForward(&r, val);
190
return (unsigned)(r >> 3);
191
# elif (defined(__clang__) || (defined(__GNUC__) && ((__GNUC__ > 3) || \
192
((__GNUC__ == 3) && (__GNUC_MINOR__ >= 4))))) && \
193
!defined(LZ4_FORCE_SW_BITCOUNT)
194
return (unsigned)__builtin_ctz(val) >> 3;
196
const U32 m = 0x01010101;
197
return (unsigned)((((val - 1) ^ val) & (m - 1)) * m) >> 24;
205
int LZ4HC_countBack(const BYTE* const ip, const BYTE* const match,
206
const BYTE* const iMin, const BYTE* const mMin)
209
int const min = (int)MAX(iMin - ip, mMin - match);
211
assert(ip >= iMin); assert((size_t)(ip-iMin) < (1U<<31));
212
assert(match >= mMin); assert((size_t)(match - mMin) < (1U<<31));
214
while ((back - min) > 3) {
215
U32 const v = LZ4_read32(ip + back - 4) ^ LZ4_read32(match + back - 4);
217
return (back - (int)LZ4HC_NbCommonBytes32(v));
222
&& (ip[back-1] == match[back-1]) )
228
#define DELTANEXTU16(table, pos) table[(U16)(pos)]
230
#define UPDATABLE(ip, op, anchor) &ip, &op, &anchor
236
static void LZ4HC_clearTables (LZ4HC_CCtx_internal* hc4)
238
MEM_INIT(hc4->hashTable, 0, sizeof(hc4->hashTable));
239
MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable));
242
static void LZ4HC_init_internal (LZ4HC_CCtx_internal* hc4, const BYTE* start)
244
size_t const bufferSize = (size_t)(hc4->end - hc4->prefixStart);
245
size_t newStartingOffset = bufferSize + hc4->dictLimit;
246
DEBUGLOG(5, "LZ4HC_init_internal");
247
assert(newStartingOffset >= bufferSize);
248
if (newStartingOffset > 1 GB) {
249
LZ4HC_clearTables(hc4);
250
newStartingOffset = 0;
252
newStartingOffset += 64 KB;
253
hc4->nextToUpdate = (U32)newStartingOffset;
254
hc4->prefixStart = start;
256
hc4->dictStart = start;
257
hc4->dictLimit = (U32)newStartingOffset;
258
hc4->lowLimit = (U32)newStartingOffset;
268
LZ4_FORCE_INLINE int LZ4HC_encodeSequence (
271
const BYTE** _anchor,
274
limitedOutput_directive limit,
279
#define anchor (*_anchor)
282
BYTE* const token = op++;
284
#if defined(LZ4_DEBUG) && (LZ4_DEBUG >= 6)
285
static const BYTE* start = NULL;
286
static U32 totalCost = 0;
287
U32 const pos = (start==NULL) ? 0 : (U32)(anchor - start);
288
U32 const ll = (U32)(ip - anchor);
289
U32 const llAdd = (ll>=15) ? ((ll-15) / 255) + 1 : 0;
290
U32 const mlAdd = (matchLength>=19) ? ((matchLength-19) / 255) + 1 : 0;
291
U32 const cost = 1 + llAdd + ll + 2 + mlAdd;
292
if (start==NULL) start = anchor;
294
DEBUGLOG(6, "pos:%7u -- literals:%4u, match:%4i, offset:%5i, cost:%4u + %5u",
296
(U32)(ip - anchor), matchLength, offset,
302
length = (size_t)(ip - anchor);
303
LZ4_STATIC_ASSERT(notLimited == 0);
305
if (limit && ((op + (length / 255) + length + (2 + 1 + LASTLITERALS)) > oend)) {
306
DEBUGLOG(6, "Not enough room to write %i literals (%i bytes remaining)",
307
(int)length, (int)(oend - op));
310
if (length >= RUN_MASK) {
311
size_t len = length - RUN_MASK;
312
*token = (RUN_MASK << ML_BITS);
313
for(; len >= 255 ; len -= 255) *op++ = 255;
316
*token = (BYTE)(length << ML_BITS);
320
LZ4_wildCopy8(op, anchor, op + length);
324
assert(offset <= LZ4_DISTANCE_MAX );
326
LZ4_writeLE16(op, (U16)(offset)); op += 2;
329
assert(matchLength >= MINMATCH);
330
length = (size_t)matchLength - MINMATCH;
331
if (limit && (op + (length / 255) + (1 + LASTLITERALS) > oend)) {
332
DEBUGLOG(6, "Not enough room to write match length");
335
if (length >= ML_MASK) {
338
for(; length >= 510 ; length -= 510) { *op++ = 255; *op++ = 255; }
339
if (length >= 255) { length -= 255; *op++ = 255; }
340
*op++ = (BYTE)length;
342
*token += (BYTE)(length);
363
LZ4HC_match_t LZ4HC_searchExtDict(const BYTE* ip, U32 ipIndex,
364
const BYTE* const iLowLimit, const BYTE* const iHighLimit,
365
const LZ4HC_CCtx_internal* dictCtx, U32 gDictEndIndex,
366
int currentBestML, int nbAttempts)
368
size_t const lDictEndIndex = (size_t)(dictCtx->end - dictCtx->prefixStart) + dictCtx->dictLimit;
369
U32 lDictMatchIndex = dictCtx->hashTable[LZ4HC_hashPtr(ip)];
370
U32 matchIndex = lDictMatchIndex + gDictEndIndex - (U32)lDictEndIndex;
371
int offset = 0, sBack = 0;
372
assert(lDictEndIndex <= 1 GB);
373
if (lDictMatchIndex>0)
374
DEBUGLOG(7, "lDictEndIndex = %zu, lDictMatchIndex = %u", lDictEndIndex, lDictMatchIndex);
375
while (ipIndex - matchIndex <= LZ4_DISTANCE_MAX && nbAttempts--) {
376
const BYTE* const matchPtr = dictCtx->prefixStart - dictCtx->dictLimit + lDictMatchIndex;
378
if (LZ4_read32(matchPtr) == LZ4_read32(ip)) {
381
const BYTE* vLimit = ip + (lDictEndIndex - lDictMatchIndex);
382
if (vLimit > iHighLimit) vLimit = iHighLimit;
383
mlt = (int)LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, vLimit) + MINMATCH;
384
back = (ip > iLowLimit) ? LZ4HC_countBack(ip, matchPtr, iLowLimit, dictCtx->prefixStart) : 0;
386
if (mlt > currentBestML) {
388
offset = (int)(ipIndex - matchIndex);
390
DEBUGLOG(7, "found match of length %i within extDictCtx", currentBestML);
393
{ U32 const nextOffset = DELTANEXTU16(dictCtx->chainTable, lDictMatchIndex);
394
lDictMatchIndex -= nextOffset;
395
matchIndex -= nextOffset;
399
md.len = currentBestML;
406
typedef LZ4HC_match_t (*LZ4MID_searchIntoDict_f)(const BYTE* ip, U32 ipIndex,
407
const BYTE* const iHighLimit,
408
const LZ4HC_CCtx_internal* dictCtx, U32 gDictEndIndex);
410
static LZ4HC_match_t LZ4MID_searchHCDict(const BYTE* ip, U32 ipIndex,
411
const BYTE* const iHighLimit,
412
const LZ4HC_CCtx_internal* dictCtx, U32 gDictEndIndex)
414
return LZ4HC_searchExtDict(ip,ipIndex,
416
dictCtx, gDictEndIndex,
420
static LZ4HC_match_t LZ4MID_searchExtDict(const BYTE* ip, U32 ipIndex,
421
const BYTE* const iHighLimit,
422
const LZ4HC_CCtx_internal* dictCtx, U32 gDictEndIndex)
424
size_t const lDictEndIndex = (size_t)(dictCtx->end - dictCtx->prefixStart) + dictCtx->dictLimit;
425
const U32* const hash4Table = dictCtx->hashTable;
426
const U32* const hash8Table = hash4Table + LZ4MID_HASHTABLESIZE;
427
DEBUGLOG(7, "LZ4MID_searchExtDict (ipIdx=%u)", ipIndex);
430
{ U32 l8DictMatchIndex = hash8Table[LZ4MID_hash8Ptr(ip)];
431
U32 m8Index = l8DictMatchIndex + gDictEndIndex - (U32)lDictEndIndex;
432
assert(lDictEndIndex <= 1 GB);
433
if (ipIndex - m8Index <= LZ4_DISTANCE_MAX) {
434
const BYTE* const matchPtr = dictCtx->prefixStart - dictCtx->dictLimit + l8DictMatchIndex;
435
const size_t safeLen = MIN(lDictEndIndex - l8DictMatchIndex, (size_t)(iHighLimit - ip));
436
int mlt = (int)LZ4_count(ip, matchPtr, ip + safeLen);
437
if (mlt >= MINMATCH) {
439
DEBUGLOG(7, "Found long ExtDict match of len=%u", mlt);
441
md.off = (int)(ipIndex - m8Index);
449
{ U32 l4DictMatchIndex = hash4Table[LZ4MID_hash4Ptr(ip)];
450
U32 m4Index = l4DictMatchIndex + gDictEndIndex - (U32)lDictEndIndex;
451
if (ipIndex - m4Index <= LZ4_DISTANCE_MAX) {
452
const BYTE* const matchPtr = dictCtx->prefixStart - dictCtx->dictLimit + l4DictMatchIndex;
453
const size_t safeLen = MIN(lDictEndIndex - l4DictMatchIndex, (size_t)(iHighLimit - ip));
454
int mlt = (int)LZ4_count(ip, matchPtr, ip + safeLen);
455
if (mlt >= MINMATCH) {
457
DEBUGLOG(7, "Found short ExtDict match of len=%u", mlt);
459
md.off = (int)(ipIndex - m4Index);
467
{ LZ4HC_match_t const md = {0, 0, 0 };
477
LZ4MID_addPosition(U32* hTable, U32 hValue, U32 index)
479
hTable[hValue] = index;
482
#define ADDPOS8(_p, _idx) LZ4MID_addPosition(hash8Table, LZ4MID_hash8Ptr(_p), _idx)
483
#define ADDPOS4(_p, _idx) LZ4MID_addPosition(hash4Table, LZ4MID_hash4Ptr(_p), _idx)
488
LZ4MID_fillHTable (LZ4HC_CCtx_internal* cctx, const void* dict, size_t size)
490
U32* const hash4Table = cctx->hashTable;
491
U32* const hash8Table = hash4Table + LZ4MID_HASHTABLESIZE;
492
const BYTE* const prefixPtr = (const BYTE*)dict;
493
U32 const prefixIdx = cctx->dictLimit;
494
U32 const target = prefixIdx + (U32)size - LZ4MID_HASHSIZE;
495
U32 idx = cctx->nextToUpdate;
496
assert(dict == cctx->prefixStart);
497
DEBUGLOG(4, "LZ4MID_fillHTable (size:%zu)", size);
498
if (size <= LZ4MID_HASHSIZE)
501
for (; idx < target; idx += 3) {
502
ADDPOS4(prefixPtr+idx-prefixIdx, idx);
503
ADDPOS8(prefixPtr+idx+1-prefixIdx, idx+1);
506
idx = (size > 32 KB + LZ4MID_HASHSIZE) ? target - 32 KB : cctx->nextToUpdate;
507
for (; idx < target; idx += 1) {
508
ADDPOS8(prefixPtr+idx-prefixIdx, idx);
511
cctx->nextToUpdate = target;
514
static LZ4MID_searchIntoDict_f select_searchDict_function(const LZ4HC_CCtx_internal* dictCtx)
516
if (dictCtx == NULL) return NULL;
517
if (LZ4HC_getCLevelParams(dictCtx->compressionLevel).strat == lz4mid)
518
return LZ4MID_searchExtDict;
519
return LZ4MID_searchHCDict;
522
static int LZ4MID_compress (
523
LZ4HC_CCtx_internal* const ctx,
524
const char* const src,
527
int const maxOutputSize,
528
const limitedOutput_directive limit,
529
const dictCtx_directive dict
532
U32* const hash4Table = ctx->hashTable;
533
U32* const hash8Table = hash4Table + LZ4MID_HASHTABLESIZE;
534
const BYTE* ip = (const BYTE*)src;
535
const BYTE* anchor = ip;
536
const BYTE* const iend = ip + *srcSizePtr;
537
const BYTE* const mflimit = iend - MFLIMIT;
538
const BYTE* const matchlimit = (iend - LASTLITERALS);
539
const BYTE* const ilimit = (iend - LZ4MID_HASHSIZE);
540
BYTE* op = (BYTE*)dst;
541
BYTE* oend = op + maxOutputSize;
543
const BYTE* const prefixPtr = ctx->prefixStart;
544
const U32 prefixIdx = ctx->dictLimit;
545
const U32 ilimitIdx = (U32)(ilimit - prefixPtr) + prefixIdx;
546
const BYTE* const dictStart = ctx->dictStart;
547
const U32 dictIdx = ctx->lowLimit;
548
const U32 gDictEndIndex = ctx->lowLimit;
549
const LZ4MID_searchIntoDict_f searchIntoDict = (dict == usingDictCtxHc) ? select_searchDict_function(ctx->dictCtx) : NULL;
550
unsigned matchLength;
551
unsigned matchDistance;
554
DEBUGLOG(5, "LZ4MID_compress (%i bytes)", *srcSizePtr);
555
if (dict == usingDictCtxHc) DEBUGLOG(5, "usingDictCtxHc");
556
assert(*srcSizePtr >= 0);
557
if (*srcSizePtr) assert(src != NULL);
558
if (maxOutputSize) assert(dst != NULL);
559
if (*srcSizePtr < 0) return 0;
560
if (maxOutputSize < 0) return 0;
561
if (*srcSizePtr > LZ4_MAX_INPUT_SIZE) {
565
if (limit == fillOutput) oend -= LASTLITERALS;
566
if (*srcSizePtr < LZ4_minLength)
567
goto _lz4mid_last_literals;
570
while (ip <= mflimit) {
571
const U32 ipIndex = (U32)(ip - prefixPtr) + prefixIdx;
573
{ U32 const h8 = LZ4MID_hash8Ptr(ip);
574
U32 const pos8 = hash8Table[h8];
575
assert(h8 < LZ4MID_HASHTABLESIZE);
576
assert(pos8 < ipIndex);
577
LZ4MID_addPosition(hash8Table, h8, ipIndex);
578
if (ipIndex - pos8 <= LZ4_DISTANCE_MAX) {
580
if (pos8 >= prefixIdx) {
581
const BYTE* const matchPtr = prefixPtr + pos8 - prefixIdx;
582
assert(matchPtr < ip);
583
matchLength = LZ4_count(ip, matchPtr, matchlimit);
584
if (matchLength >= MINMATCH) {
585
DEBUGLOG(7, "found long match at pos %u (len=%u)", pos8, matchLength);
586
matchDistance = ipIndex - pos8;
587
goto _lz4mid_encode_sequence;
590
if (pos8 >= dictIdx) {
592
const BYTE* const matchPtr = dictStart + (pos8 - dictIdx);
593
const size_t safeLen = MIN(prefixIdx - pos8, (size_t)(matchlimit - ip));
594
matchLength = LZ4_count(ip, matchPtr, ip + safeLen);
595
if (matchLength >= MINMATCH) {
596
DEBUGLOG(7, "found long match at ExtDict pos %u (len=%u)", pos8, matchLength);
597
matchDistance = ipIndex - pos8;
598
goto _lz4mid_encode_sequence;
604
{ U32 const h4 = LZ4MID_hash4Ptr(ip);
605
U32 const pos4 = hash4Table[h4];
606
assert(h4 < LZ4MID_HASHTABLESIZE);
607
assert(pos4 < ipIndex);
608
LZ4MID_addPosition(hash4Table, h4, ipIndex);
609
if (ipIndex - pos4 <= LZ4_DISTANCE_MAX) {
611
if (pos4 >= prefixIdx) {
613
const BYTE* const matchPtr = prefixPtr + (pos4 - prefixIdx);
614
assert(matchPtr < ip);
615
assert(matchPtr >= prefixPtr);
616
matchLength = LZ4_count(ip, matchPtr, matchlimit);
617
if (matchLength >= MINMATCH) {
619
U32 const h8 = LZ4MID_hash8Ptr(ip+1);
620
U32 const pos8 = hash8Table[h8];
621
U32 const m2Distance = ipIndex + 1 - pos8;
622
matchDistance = ipIndex - pos4;
623
if ( m2Distance <= LZ4_DISTANCE_MAX
625
&& likely(ip < mflimit)
627
const BYTE* const m2Ptr = prefixPtr + (pos8 - prefixIdx);
628
unsigned ml2 = LZ4_count(ip+1, m2Ptr, matchlimit);
629
if (ml2 > matchLength) {
630
LZ4MID_addPosition(hash8Table, h8, ipIndex+1);
633
matchDistance = m2Distance;
635
goto _lz4mid_encode_sequence;
638
if (pos4 >= dictIdx) {
640
const BYTE* const matchPtr = dictStart + (pos4 - dictIdx);
641
const size_t safeLen = MIN(prefixIdx - pos4, (size_t)(matchlimit - ip));
642
matchLength = LZ4_count(ip, matchPtr, ip + safeLen);
643
if (matchLength >= MINMATCH) {
644
DEBUGLOG(7, "found match at ExtDict pos %u (len=%u)", pos4, matchLength);
645
matchDistance = ipIndex - pos4;
646
goto _lz4mid_encode_sequence;
652
if ( (dict == usingDictCtxHc)
653
&& (ipIndex - gDictEndIndex < LZ4_DISTANCE_MAX - 8) ) {
655
LZ4HC_match_t dMatch = searchIntoDict(ip, ipIndex,
657
ctx->dictCtx, gDictEndIndex);
658
if (dMatch.len >= MINMATCH) {
659
DEBUGLOG(7, "found Dictionary match (offset=%i)", dMatch.off);
660
assert(dMatch.back == 0);
661
matchLength = (unsigned)dMatch.len;
662
matchDistance = (unsigned)dMatch.off;
663
goto _lz4mid_encode_sequence;
667
ip += 1 + ((ip-anchor) >> 9);
670
_lz4mid_encode_sequence:
672
while (((ip > anchor) & ((U32)(ip-prefixPtr) > matchDistance)) && (unlikely(ip[-1] == ip[-(int)matchDistance-1]))) {
677
ADDPOS8(ip+1, ipIndex+1);
678
ADDPOS8(ip+2, ipIndex+2);
679
ADDPOS4(ip+1, ipIndex+1);
682
{ BYTE* const saved_op = op;
684
if (LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor),
685
(int)matchLength, (int)matchDistance,
688
goto _lz4mid_dest_overflow;
693
{ U32 endMatchIdx = (U32)(ip-prefixPtr) + prefixIdx;
694
U32 pos_m2 = endMatchIdx - 2;
695
if (pos_m2 < ilimitIdx) {
696
if (likely(ip - prefixPtr > 5)) {
697
ADDPOS8(ip-5, endMatchIdx - 5);
699
ADDPOS8(ip-3, endMatchIdx - 3);
700
ADDPOS8(ip-2, endMatchIdx - 2);
701
ADDPOS4(ip-2, endMatchIdx - 2);
702
ADDPOS4(ip-1, endMatchIdx - 1);
707
_lz4mid_last_literals:
709
{ size_t lastRunSize = (size_t)(iend - anchor);
710
size_t llAdd = (lastRunSize + 255 - RUN_MASK) / 255;
711
size_t const totalSize = 1 + llAdd + lastRunSize;
712
if (limit == fillOutput) oend += LASTLITERALS;
713
if (limit && (op + totalSize > oend)) {
714
if (limit == limitedOutput) return 0;
716
lastRunSize = (size_t)(oend - op) - 1 ;
717
llAdd = (lastRunSize + 256 - RUN_MASK) / 256;
718
lastRunSize -= llAdd;
720
DEBUGLOG(6, "Final literal run : %i literals", (int)lastRunSize);
721
ip = anchor + lastRunSize;
723
if (lastRunSize >= RUN_MASK) {
724
size_t accumulator = lastRunSize - RUN_MASK;
725
*op++ = (RUN_MASK << ML_BITS);
726
for(; accumulator >= 255 ; accumulator -= 255)
728
*op++ = (BYTE) accumulator;
730
*op++ = (BYTE)(lastRunSize << ML_BITS);
732
assert(lastRunSize <= (size_t)(oend - op));
733
LZ4_memcpy(op, anchor, lastRunSize);
738
DEBUGLOG(5, "compressed %i bytes into %i bytes", *srcSizePtr, (int)((char*)op - dst));
739
assert(ip >= (const BYTE*)src);
741
*srcSizePtr = (int)(ip - (const BYTE*)src);
742
assert((char*)op >= dst);
744
assert((char*)op - dst < INT_MAX);
745
return (int)((char*)op - dst);
747
_lz4mid_dest_overflow:
748
if (limit == fillOutput) {
750
size_t const ll = (size_t)(ip - anchor);
751
size_t const ll_addbytes = (ll + 240) / 255;
752
size_t const ll_totalCost = 1 + ll_addbytes + ll;
753
BYTE* const maxLitPos = oend - 3;
754
DEBUGLOG(6, "Last sequence is overflowing : %u literals, %u remaining space",
755
(unsigned)ll, (unsigned)(oend-op));
756
if (op + ll_totalCost <= maxLitPos) {
758
size_t const bytesLeftForMl = (size_t)(maxLitPos - (op+ll_totalCost));
759
size_t const maxMlSize = MINMATCH + (ML_MASK-1) + (bytesLeftForMl * 255);
760
assert(maxMlSize < INT_MAX);
761
if ((size_t)matchLength > maxMlSize) matchLength= (unsigned)maxMlSize;
762
if ((oend + LASTLITERALS) - (op + ll_totalCost + 2) - 1 + matchLength >= MFLIMIT) {
763
DEBUGLOG(6, "Let's encode a last sequence (ll=%u, ml=%u)", (unsigned)ll, matchLength);
764
LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor),
765
(int)matchLength, (int)matchDistance,
768
DEBUGLOG(6, "Let's finish with a run of literals (%u bytes left)", (unsigned)(oend-op));
769
goto _lz4mid_last_literals;
781
LZ4_FORCE_INLINE void LZ4HC_Insert (LZ4HC_CCtx_internal* hc4, const BYTE* ip)
783
U16* const chainTable = hc4->chainTable;
784
U32* const hashTable = hc4->hashTable;
785
const BYTE* const prefixPtr = hc4->prefixStart;
786
U32 const prefixIdx = hc4->dictLimit;
787
U32 const target = (U32)(ip - prefixPtr) + prefixIdx;
788
U32 idx = hc4->nextToUpdate;
789
assert(ip >= prefixPtr);
790
assert(target >= prefixIdx);
792
while (idx < target) {
793
U32 const h = LZ4HC_hashPtr(prefixPtr+idx-prefixIdx);
794
size_t delta = idx - hashTable[h];
795
if (delta>LZ4_DISTANCE_MAX) delta = LZ4_DISTANCE_MAX;
796
DELTANEXTU16(chainTable, idx) = (U16)delta;
801
hc4->nextToUpdate = target;
805
# define LZ4HC_rotl32(x,r) _rotl(x,r)
807
# define LZ4HC_rotl32(x,r) ((x << r) | (x >> (32 - r)))
811
static U32 LZ4HC_rotatePattern(size_t const rotate, U32 const pattern)
813
size_t const bitsToRotate = (rotate & (sizeof(pattern) - 1)) << 3;
814
if (bitsToRotate == 0) return pattern;
815
return LZ4HC_rotl32(pattern, (int)bitsToRotate);
821
LZ4HC_countPattern(const BYTE* ip, const BYTE* const iEnd, U32 const pattern32)
823
const BYTE* const iStart = ip;
824
reg_t const pattern = (sizeof(pattern)==8) ?
825
(reg_t)pattern32 + (((reg_t)pattern32) << (sizeof(pattern)*4)) : pattern32;
827
while (likely(ip < iEnd-(sizeof(pattern)-1))) {
828
reg_t const diff = LZ4_read_ARCH(ip) ^ pattern;
829
if (!diff) { ip+=sizeof(pattern); continue; }
830
ip += LZ4_NbCommonBytes(diff);
831
return (unsigned)(ip - iStart);
834
if (LZ4_isLittleEndian()) {
835
reg_t patternByte = pattern;
836
while ((ip<iEnd) && (*ip == (BYTE)patternByte)) {
837
ip++; patternByte >>= 8;
840
U32 bitOffset = (sizeof(pattern)*8) - 8;
842
BYTE const byte = (BYTE)(pattern >> bitOffset);
843
if (*ip != byte) break;
844
ip ++; bitOffset -= 8;
847
return (unsigned)(ip - iStart);
854
LZ4HC_reverseCountPattern(const BYTE* ip, const BYTE* const iLow, U32 pattern)
856
const BYTE* const iStart = ip;
858
while (likely(ip >= iLow+4)) {
859
if (LZ4_read32(ip-4) != pattern) break;
862
{ const BYTE* bytePtr = (const BYTE*)(&pattern) + 3;
863
while (likely(ip>iLow)) {
864
if (ip[-1] != *bytePtr) break;
867
return (unsigned)(iStart - ip);
875
static int LZ4HC_protectDictEnd(U32 const dictLimit, U32 const matchIndex)
877
return ((U32)((dictLimit - 1) - matchIndex) >= 3);
880
typedef enum { rep_untested, rep_not, rep_confirmed } repeat_state_e;
881
typedef enum { favorCompressionRatio=0, favorDecompressionSpeed } HCfavor_e;
884
LZ4_FORCE_INLINE LZ4HC_match_t
885
LZ4HC_InsertAndGetWiderMatch (
886
LZ4HC_CCtx_internal* const hc4,
887
const BYTE* const ip,
888
const BYTE* const iLowLimit, const BYTE* const iHighLimit,
890
const int maxNbAttempts,
891
const int patternAnalysis, const int chainSwap,
892
const dictCtx_directive dict,
893
const HCfavor_e favorDecSpeed)
895
U16* const chainTable = hc4->chainTable;
896
U32* const hashTable = hc4->hashTable;
897
const LZ4HC_CCtx_internal* const dictCtx = hc4->dictCtx;
898
const BYTE* const prefixPtr = hc4->prefixStart;
899
const U32 prefixIdx = hc4->dictLimit;
900
const U32 ipIndex = (U32)(ip - prefixPtr) + prefixIdx;
901
const int withinStartDistance = (hc4->lowLimit + (LZ4_DISTANCE_MAX + 1) > ipIndex);
902
const U32 lowestMatchIndex = (withinStartDistance) ? hc4->lowLimit : ipIndex - LZ4_DISTANCE_MAX;
903
const BYTE* const dictStart = hc4->dictStart;
904
const U32 dictIdx = hc4->lowLimit;
905
const BYTE* const dictEnd = dictStart + prefixIdx - dictIdx;
906
int const lookBackLength = (int)(ip-iLowLimit);
907
int nbAttempts = maxNbAttempts;
908
U32 matchChainPos = 0;
909
U32 const pattern = LZ4_read32(ip);
911
repeat_state_e repeat = rep_untested;
912
size_t srcPatternLength = 0;
913
int offset = 0, sBack = 0;
915
DEBUGLOG(7, "LZ4HC_InsertAndGetWiderMatch");
917
LZ4HC_Insert(hc4, ip);
918
matchIndex = hashTable[LZ4HC_hashPtr(ip)];
919
DEBUGLOG(7, "First candidate match for pos %u found at index %u / %u (lowestMatchIndex)",
920
ipIndex, matchIndex, lowestMatchIndex);
922
while ((matchIndex>=lowestMatchIndex) && (nbAttempts>0)) {
925
assert(matchIndex < ipIndex);
926
if (favorDecSpeed && (ipIndex - matchIndex < 8)) {
929
} else if (matchIndex >= prefixIdx) {
930
const BYTE* const matchPtr = prefixPtr + (matchIndex - prefixIdx);
931
assert(matchPtr < ip);
932
assert(longest >= 1);
933
if (LZ4_read16(iLowLimit + longest - 1) == LZ4_read16(matchPtr - lookBackLength + longest - 1)) {
934
if (LZ4_read32(matchPtr) == pattern) {
935
int const back = lookBackLength ? LZ4HC_countBack(ip, matchPtr, iLowLimit, prefixPtr) : 0;
936
matchLength = MINMATCH + (int)LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, iHighLimit);
938
if (matchLength > longest) {
939
longest = matchLength;
940
offset = (int)(ipIndex - matchIndex);
942
DEBUGLOG(7, "Found match of len=%i within prefix, offset=%i, back=%i", longest, offset, -back);
945
const BYTE* const matchPtr = dictStart + (matchIndex - dictIdx);
946
assert(matchIndex >= dictIdx);
947
if ( likely(matchIndex <= prefixIdx - 4)
948
&& (LZ4_read32(matchPtr) == pattern) ) {
950
const BYTE* vLimit = ip + (prefixIdx - matchIndex);
951
if (vLimit > iHighLimit) vLimit = iHighLimit;
952
matchLength = (int)LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, vLimit) + MINMATCH;
953
if ((ip+matchLength == vLimit) && (vLimit < iHighLimit))
954
matchLength += LZ4_count(ip+matchLength, prefixPtr, iHighLimit);
955
back = lookBackLength ? LZ4HC_countBack(ip, matchPtr, iLowLimit, dictStart) : 0;
957
if (matchLength > longest) {
958
longest = matchLength;
959
offset = (int)(ipIndex - matchIndex);
961
DEBUGLOG(7, "Found match of len=%i within dict, offset=%i, back=%i", longest, offset, -back);
964
if (chainSwap && matchLength==longest) {
965
assert(lookBackLength==0);
966
if (matchIndex + (U32)longest <= ipIndex) {
967
int const kTrigger = 4;
968
U32 distanceToNextMatch = 1;
969
int const end = longest - MINMATCH + 1;
971
int accel = 1 << kTrigger;
973
for (pos = 0; pos < end; pos += step) {
974
U32 const candidateDist = DELTANEXTU16(chainTable, matchIndex + (U32)pos);
975
step = (accel++ >> kTrigger);
976
if (candidateDist > distanceToNextMatch) {
977
distanceToNextMatch = candidateDist;
978
matchChainPos = (U32)pos;
979
accel = 1 << kTrigger;
981
if (distanceToNextMatch > 1) {
982
if (distanceToNextMatch > matchIndex) break;
983
matchIndex -= distanceToNextMatch;
987
{ U32 const distNextMatch = DELTANEXTU16(chainTable, matchIndex);
988
if (patternAnalysis && distNextMatch==1 && matchChainPos==0) {
989
U32 const matchCandidateIdx = matchIndex-1;
991
if (repeat == rep_untested) {
992
if ( ((pattern & 0xFFFF) == (pattern >> 16))
993
& ((pattern & 0xFF) == (pattern >> 24)) ) {
994
DEBUGLOG(7, "Repeat pattern detected, char %02X", pattern >> 24);
995
repeat = rep_confirmed;
996
srcPatternLength = LZ4HC_countPattern(ip+sizeof(pattern), iHighLimit, pattern) + sizeof(pattern);
1000
if ( (repeat == rep_confirmed) && (matchCandidateIdx >= lowestMatchIndex)
1001
&& LZ4HC_protectDictEnd(prefixIdx, matchCandidateIdx) ) {
1002
const int extDict = matchCandidateIdx < prefixIdx;
1003
const BYTE* const matchPtr = extDict ? dictStart + (matchCandidateIdx - dictIdx) : prefixPtr + (matchCandidateIdx - prefixIdx);
1004
if (LZ4_read32(matchPtr) == pattern) {
1005
const BYTE* const iLimit = extDict ? dictEnd : iHighLimit;
1006
size_t forwardPatternLength = LZ4HC_countPattern(matchPtr+sizeof(pattern), iLimit, pattern) + sizeof(pattern);
1007
if (extDict && matchPtr + forwardPatternLength == iLimit) {
1008
U32 const rotatedPattern = LZ4HC_rotatePattern(forwardPatternLength, pattern);
1009
forwardPatternLength += LZ4HC_countPattern(prefixPtr, iHighLimit, rotatedPattern);
1011
{ const BYTE* const lowestMatchPtr = extDict ? dictStart : prefixPtr;
1012
size_t backLength = LZ4HC_reverseCountPattern(matchPtr, lowestMatchPtr, pattern);
1013
size_t currentSegmentLength;
1015
&& matchPtr - backLength == prefixPtr
1016
&& dictIdx < prefixIdx) {
1017
U32 const rotatedPattern = LZ4HC_rotatePattern((U32)(-(int)backLength), pattern);
1018
backLength += LZ4HC_reverseCountPattern(dictEnd, dictStart, rotatedPattern);
1021
backLength = matchCandidateIdx - MAX(matchCandidateIdx - (U32)backLength, lowestMatchIndex);
1022
assert(matchCandidateIdx - backLength >= lowestMatchIndex);
1023
currentSegmentLength = backLength + forwardPatternLength;
1025
if ( (currentSegmentLength >= srcPatternLength)
1026
&& (forwardPatternLength <= srcPatternLength) ) {
1027
U32 const newMatchIndex = matchCandidateIdx + (U32)forwardPatternLength - (U32)srcPatternLength;
1028
if (LZ4HC_protectDictEnd(prefixIdx, newMatchIndex))
1029
matchIndex = newMatchIndex;
1032
assert(newMatchIndex >= prefixIdx - 3 && newMatchIndex < prefixIdx && !extDict);
1033
matchIndex = prefixIdx;
1036
U32 const newMatchIndex = matchCandidateIdx - (U32)backLength;
1037
if (!LZ4HC_protectDictEnd(prefixIdx, newMatchIndex)) {
1038
assert(newMatchIndex >= prefixIdx - 3 && newMatchIndex < prefixIdx && !extDict);
1039
matchIndex = prefixIdx;
1041
matchIndex = newMatchIndex;
1042
if (lookBackLength==0) {
1043
size_t const maxML = MIN(currentSegmentLength, srcPatternLength);
1044
if ((size_t)longest < maxML) {
1045
assert(prefixPtr - prefixIdx + matchIndex != ip);
1046
if ((size_t)(ip - prefixPtr) + prefixIdx - matchIndex > LZ4_DISTANCE_MAX) break;
1047
assert(maxML < 2 GB);
1048
longest = (int)maxML;
1049
offset = (int)(ipIndex - matchIndex);
1051
DEBUGLOG(7, "Found repeat pattern match of len=%i, offset=%i", longest, offset);
1053
{ U32 const distToNextPattern = DELTANEXTU16(chainTable, matchIndex);
1054
if (distToNextPattern > matchIndex) break;
1055
matchIndex -= distToNextPattern;
1062
matchIndex -= DELTANEXTU16(chainTable, matchIndex + matchChainPos);
1066
if ( dict == usingDictCtxHc
1068
&& withinStartDistance) {
1069
size_t const dictEndOffset = (size_t)(dictCtx->end - dictCtx->prefixStart) + dictCtx->dictLimit;
1070
U32 dictMatchIndex = dictCtx->hashTable[LZ4HC_hashPtr(ip)];
1071
assert(dictEndOffset <= 1 GB);
1072
matchIndex = dictMatchIndex + lowestMatchIndex - (U32)dictEndOffset;
1073
if (dictMatchIndex>0) DEBUGLOG(7, "dictEndOffset = %zu, dictMatchIndex = %u => relative matchIndex = %i", dictEndOffset, dictMatchIndex, (int)dictMatchIndex - (int)dictEndOffset);
1074
while (ipIndex - matchIndex <= LZ4_DISTANCE_MAX && nbAttempts--) {
1075
const BYTE* const matchPtr = dictCtx->prefixStart - dictCtx->dictLimit + dictMatchIndex;
1077
if (LZ4_read32(matchPtr) == pattern) {
1080
const BYTE* vLimit = ip + (dictEndOffset - dictMatchIndex);
1081
if (vLimit > iHighLimit) vLimit = iHighLimit;
1082
mlt = (int)LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, vLimit) + MINMATCH;
1083
back = lookBackLength ? LZ4HC_countBack(ip, matchPtr, iLowLimit, dictCtx->prefixStart) : 0;
1085
if (mlt > longest) {
1087
offset = (int)(ipIndex - matchIndex);
1089
DEBUGLOG(7, "found match of length %i within extDictCtx", longest);
1092
{ U32 const nextOffset = DELTANEXTU16(dictCtx->chainTable, dictMatchIndex);
1093
dictMatchIndex -= nextOffset;
1094
matchIndex -= nextOffset;
1098
assert(longest >= 0);
1106
LZ4_FORCE_INLINE LZ4HC_match_t
1107
LZ4HC_InsertAndFindBestMatch(LZ4HC_CCtx_internal* const hc4,
1108
const BYTE* const ip, const BYTE* const iLimit,
1109
const int maxNbAttempts,
1110
const int patternAnalysis,
1111
const dictCtx_directive dict)
1113
DEBUGLOG(7, "LZ4HC_InsertAndFindBestMatch");
1117
return LZ4HC_InsertAndGetWiderMatch(hc4, ip, ip, iLimit, MINMATCH-1, maxNbAttempts, patternAnalysis, 0 , dict, favorCompressionRatio);
1121
LZ4_FORCE_INLINE int LZ4HC_compress_hashChain (
1122
LZ4HC_CCtx_internal* const ctx,
1123
const char* const source,
1126
int const maxOutputSize,
1128
const limitedOutput_directive limit,
1129
const dictCtx_directive dict
1132
const int inputSize = *srcSizePtr;
1133
const int patternAnalysis = (maxNbAttempts > 128);
1135
const BYTE* ip = (const BYTE*) source;
1136
const BYTE* anchor = ip;
1137
const BYTE* const iend = ip + inputSize;
1138
const BYTE* const mflimit = iend - MFLIMIT;
1139
const BYTE* const matchlimit = (iend - LASTLITERALS);
1141
BYTE* optr = (BYTE*) dest;
1142
BYTE* op = (BYTE*) dest;
1143
BYTE* oend = op + maxOutputSize;
1146
const BYTE* start2 = NULL;
1147
const BYTE* start3 = NULL;
1148
LZ4HC_match_t m0, m1, m2, m3;
1149
const LZ4HC_match_t nomatch = {0, 0, 0};
1152
DEBUGLOG(5, "LZ4HC_compress_hashChain (dict?=>%i)", dict);
1154
if (limit == fillOutput) oend -= LASTLITERALS;
1155
if (inputSize < LZ4_minLength) goto _last_literals;
1158
while (ip <= mflimit) {
1159
m1 = LZ4HC_InsertAndFindBestMatch(ctx, ip, matchlimit, maxNbAttempts, patternAnalysis, dict);
1160
if (m1.len<MINMATCH) { ip++; continue; }
1163
start0 = ip; m0 = m1;
1166
DEBUGLOG(7, "_Search2 (currently found match of size %i)", m1.len);
1167
if (ip+m1.len <= mflimit) {
1168
start2 = ip + m1.len - 2;
1169
m2 = LZ4HC_InsertAndGetWiderMatch(ctx,
1170
start2, ip + 0, matchlimit, m1.len,
1171
maxNbAttempts, patternAnalysis, 0, dict, favorCompressionRatio);
1177
if (m2.len <= m1.len) {
1179
if (LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor),
1182
goto _dest_overflow;
1187
if (start2 < ip + m0.len) {
1188
ip = start0; m1 = m0;
1192
if ((start2 - ip) < 3) {
1199
if ((start2 - ip) < OPTIMAL_ML) {
1201
int new_ml = m1.len;
1202
if (new_ml > OPTIMAL_ML) new_ml = OPTIMAL_ML;
1203
if (ip+new_ml > start2 + m2.len - MINMATCH)
1204
new_ml = (int)(start2 - ip) + m2.len - MINMATCH;
1205
correction = new_ml - (int)(start2 - ip);
1206
if (correction > 0) {
1207
start2 += correction;
1208
m2.len -= correction;
1212
if (start2 + m2.len <= mflimit) {
1213
start3 = start2 + m2.len - 3;
1214
m3 = LZ4HC_InsertAndGetWiderMatch(ctx,
1215
start3, start2, matchlimit, m2.len,
1216
maxNbAttempts, patternAnalysis, 0, dict, favorCompressionRatio);
1222
if (m3.len <= m2.len) {
1224
if (start2 < ip+m1.len) m1.len = (int)(start2 - ip);
1227
if (LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor),
1230
goto _dest_overflow;
1233
if (LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor),
1237
goto _dest_overflow;
1242
if (start3 < ip+m1.len+3) {
1243
if (start3 >= (ip+m1.len)) {
1244
if (start2 < ip+m1.len) {
1245
int correction = (int)(ip+m1.len - start2);
1246
start2 += correction;
1247
m2.len -= correction;
1248
if (m2.len < MINMATCH) {
1255
if (LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor),
1258
goto _dest_overflow;
1277
if (start2 < ip+m1.len) {
1278
if ((start2 - ip) < OPTIMAL_ML) {
1280
if (m1.len > OPTIMAL_ML) m1.len = OPTIMAL_ML;
1281
if (ip + m1.len > start2 + m2.len - MINMATCH)
1282
m1.len = (int)(start2 - ip) + m2.len - MINMATCH;
1283
correction = m1.len - (int)(start2 - ip);
1284
if (correction > 0) {
1285
start2 += correction;
1286
m2.len -= correction;
1289
m1.len = (int)(start2 - ip);
1293
if ( LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor),
1296
goto _dest_overflow;
1299
ip = start2; m1 = m2;
1302
start2 = start3; m2 = m3;
1310
{ size_t lastRunSize = (size_t)(iend - anchor);
1311
size_t llAdd = (lastRunSize + 255 - RUN_MASK) / 255;
1312
size_t const totalSize = 1 + llAdd + lastRunSize;
1313
if (limit == fillOutput) oend += LASTLITERALS;
1314
if (limit && (op + totalSize > oend)) {
1315
if (limit == limitedOutput) return 0;
1317
lastRunSize = (size_t)(oend - op) - 1 ;
1318
llAdd = (lastRunSize + 256 - RUN_MASK) / 256;
1319
lastRunSize -= llAdd;
1321
DEBUGLOG(6, "Final literal run : %i literals", (int)lastRunSize);
1322
ip = anchor + lastRunSize;
1324
if (lastRunSize >= RUN_MASK) {
1325
size_t accumulator = lastRunSize - RUN_MASK;
1326
*op++ = (RUN_MASK << ML_BITS);
1327
for(; accumulator >= 255 ; accumulator -= 255) *op++ = 255;
1328
*op++ = (BYTE) accumulator;
1330
*op++ = (BYTE)(lastRunSize << ML_BITS);
1332
LZ4_memcpy(op, anchor, lastRunSize);
1337
*srcSizePtr = (int) (((const char*)ip) - source);
1338
return (int) (((char*)op)-dest);
1341
if (limit == fillOutput) {
1343
size_t const ll = (size_t)(ip - anchor);
1344
size_t const ll_addbytes = (ll + 240) / 255;
1345
size_t const ll_totalCost = 1 + ll_addbytes + ll;
1346
BYTE* const maxLitPos = oend - 3;
1347
DEBUGLOG(6, "Last sequence overflowing");
1349
if (op + ll_totalCost <= maxLitPos) {
1351
size_t const bytesLeftForMl = (size_t)(maxLitPos - (op+ll_totalCost));
1352
size_t const maxMlSize = MINMATCH + (ML_MASK-1) + (bytesLeftForMl * 255);
1353
assert(maxMlSize < INT_MAX); assert(m1.len >= 0);
1354
if ((size_t)m1.len > maxMlSize) m1.len = (int)maxMlSize;
1355
if ((oend + LASTLITERALS) - (op + ll_totalCost + 2) - 1 + m1.len >= MFLIMIT) {
1356
LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor), m1.len, m1.off, notLimited, oend);
1358
goto _last_literals;
1365
static int LZ4HC_compress_optimal( LZ4HC_CCtx_internal* ctx,
1366
const char* const source, char* dst,
1367
int* srcSizePtr, int dstCapacity,
1368
int const nbSearches, size_t sufficient_len,
1369
const limitedOutput_directive limit, int const fullUpdate,
1370
const dictCtx_directive dict,
1371
const HCfavor_e favorDecSpeed);
1374
LZ4HC_compress_generic_internal (
1375
LZ4HC_CCtx_internal* const ctx,
1376
const char* const src,
1378
int* const srcSizePtr,
1379
int const dstCapacity,
1381
const limitedOutput_directive limit,
1382
const dictCtx_directive dict
1385
DEBUGLOG(5, "LZ4HC_compress_generic_internal(src=%p, srcSize=%d)",
1388
if (limit == fillOutput && dstCapacity < 1) return 0;
1389
if ((U32)*srcSizePtr > (U32)LZ4_MAX_INPUT_SIZE) return 0;
1391
ctx->end += *srcSizePtr;
1392
{ cParams_t const cParam = LZ4HC_getCLevelParams(cLevel);
1393
HCfavor_e const favor = ctx->favorDecSpeed ? favorDecompressionSpeed : favorCompressionRatio;
1396
if (cParam.strat == lz4mid) {
1397
result = LZ4MID_compress(ctx,
1398
src, dst, srcSizePtr, dstCapacity,
1400
} else if (cParam.strat == lz4hc) {
1401
result = LZ4HC_compress_hashChain(ctx,
1402
src, dst, srcSizePtr, dstCapacity,
1403
cParam.nbSearches, limit, dict);
1405
assert(cParam.strat == lz4opt);
1406
result = LZ4HC_compress_optimal(ctx,
1407
src, dst, srcSizePtr, dstCapacity,
1408
cParam.nbSearches, cParam.targetLength, limit,
1409
cLevel >= LZ4HC_CLEVEL_MAX,
1412
if (result <= 0) ctx->dirty = 1;
1417
static void LZ4HC_setExternalDict(LZ4HC_CCtx_internal* ctxPtr, const BYTE* newBlock);
1420
LZ4HC_compress_generic_noDictCtx (
1421
LZ4HC_CCtx_internal* const ctx,
1422
const char* const src,
1424
int* const srcSizePtr,
1425
int const dstCapacity,
1427
limitedOutput_directive limit
1430
assert(ctx->dictCtx == NULL);
1431
return LZ4HC_compress_generic_internal(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit, noDictCtx);
1434
static int isStateCompatible(const LZ4HC_CCtx_internal* ctx1, const LZ4HC_CCtx_internal* ctx2)
1436
int const isMid1 = LZ4HC_getCLevelParams(ctx1->compressionLevel).strat == lz4mid;
1437
int const isMid2 = LZ4HC_getCLevelParams(ctx2->compressionLevel).strat == lz4mid;
1438
return !(isMid1 ^ isMid2);
1442
LZ4HC_compress_generic_dictCtx (
1443
LZ4HC_CCtx_internal* const ctx,
1444
const char* const src,
1446
int* const srcSizePtr,
1447
int const dstCapacity,
1449
limitedOutput_directive limit
1452
const size_t position = (size_t)(ctx->end - ctx->prefixStart) + (ctx->dictLimit - ctx->lowLimit);
1453
assert(ctx->dictCtx != NULL);
1454
if (position >= 64 KB) {
1455
ctx->dictCtx = NULL;
1456
return LZ4HC_compress_generic_noDictCtx(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit);
1457
} else if (position == 0 && *srcSizePtr > 4 KB && isStateCompatible(ctx, ctx->dictCtx)) {
1458
LZ4_memcpy(ctx, ctx->dictCtx, sizeof(LZ4HC_CCtx_internal));
1459
LZ4HC_setExternalDict(ctx, (const BYTE *)src);
1460
ctx->compressionLevel = (short)cLevel;
1461
return LZ4HC_compress_generic_noDictCtx(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit);
1463
return LZ4HC_compress_generic_internal(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit, usingDictCtxHc);
1468
LZ4HC_compress_generic (
1469
LZ4HC_CCtx_internal* const ctx,
1470
const char* const src,
1472
int* const srcSizePtr,
1473
int const dstCapacity,
1475
limitedOutput_directive limit
1478
if (ctx->dictCtx == NULL) {
1479
return LZ4HC_compress_generic_noDictCtx(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit);
1481
return LZ4HC_compress_generic_dictCtx(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit);
1486
int LZ4_sizeofStateHC(void) { return (int)sizeof(LZ4_streamHC_t); }
1488
static size_t LZ4_streamHC_t_alignment(void)
1491
typedef struct { char c; LZ4_streamHC_t t; } t_a;
1492
return sizeof(t_a) - sizeof(LZ4_streamHC_t);
1500
int LZ4_compress_HC_extStateHC_fastReset (void* state, const char* src, char* dst, int srcSize, int dstCapacity, int compressionLevel)
1502
LZ4HC_CCtx_internal* const ctx = &((LZ4_streamHC_t*)state)->internal_donotuse;
1503
if (!LZ4_isAligned(state, LZ4_streamHC_t_alignment())) return 0;
1504
LZ4_resetStreamHC_fast((LZ4_streamHC_t*)state, compressionLevel);
1505
LZ4HC_init_internal (ctx, (const BYTE*)src);
1506
if (dstCapacity < LZ4_compressBound(srcSize))
1507
return LZ4HC_compress_generic (ctx, src, dst, &srcSize, dstCapacity, compressionLevel, limitedOutput);
1509
return LZ4HC_compress_generic (ctx, src, dst, &srcSize, dstCapacity, compressionLevel, notLimited);
1512
int LZ4_compress_HC_extStateHC (void* state, const char* src, char* dst, int srcSize, int dstCapacity, int compressionLevel)
1514
LZ4_streamHC_t* const ctx = LZ4_initStreamHC(state, sizeof(*ctx));
1515
if (ctx==NULL) return 0;
1516
return LZ4_compress_HC_extStateHC_fastReset(state, src, dst, srcSize, dstCapacity, compressionLevel);
1519
int LZ4_compress_HC(const char* src, char* dst, int srcSize, int dstCapacity, int compressionLevel)
1522
#if defined(LZ4HC_HEAPMODE) && LZ4HC_HEAPMODE==1
1523
LZ4_streamHC_t* const statePtr = (LZ4_streamHC_t*)ALLOC(sizeof(LZ4_streamHC_t));
1524
if (statePtr==NULL) return 0;
1526
LZ4_streamHC_t state;
1527
LZ4_streamHC_t* const statePtr = &state;
1529
DEBUGLOG(5, "LZ4_compress_HC")
1530
cSize = LZ4_compress_HC_extStateHC(statePtr, src, dst, srcSize, dstCapacity, compressionLevel);
1531
#if defined(LZ4HC_HEAPMODE) && LZ4HC_HEAPMODE==1
1538
int LZ4_compress_HC_destSize(void* state, const char* source, char* dest, int* sourceSizePtr, int targetDestSize, int cLevel)
1540
LZ4_streamHC_t* const ctx = LZ4_initStreamHC(state, sizeof(*ctx));
1541
if (ctx==NULL) return 0;
1542
LZ4HC_init_internal(&ctx->internal_donotuse, (const BYTE*) source);
1543
LZ4_setCompressionLevel(ctx, cLevel);
1544
return LZ4HC_compress_generic(&ctx->internal_donotuse, source, dest, sourceSizePtr, targetDestSize, cLevel, fillOutput);
1553
#if !defined(LZ4_STATIC_LINKING_ONLY_DISABLE_MEMORY_ALLOCATION)
1554
LZ4_streamHC_t* LZ4_createStreamHC(void)
1556
LZ4_streamHC_t* const state =
1557
(LZ4_streamHC_t*)ALLOC_AND_ZERO(sizeof(LZ4_streamHC_t));
1558
if (state == NULL) return NULL;
1559
LZ4_setCompressionLevel(state, LZ4HC_CLEVEL_DEFAULT);
1563
int LZ4_freeStreamHC (LZ4_streamHC_t* LZ4_streamHCPtr)
1565
DEBUGLOG(4, "LZ4_freeStreamHC(%p)", LZ4_streamHCPtr);
1566
if (!LZ4_streamHCPtr) return 0;
1567
FREEMEM(LZ4_streamHCPtr);
1573
LZ4_streamHC_t* LZ4_initStreamHC (void* buffer, size_t size)
1575
LZ4_streamHC_t* const LZ4_streamHCPtr = (LZ4_streamHC_t*)buffer;
1576
DEBUGLOG(4, "LZ4_initStreamHC(%p, %u)", buffer, (unsigned)size);
1578
if (buffer == NULL) return NULL;
1579
if (size < sizeof(LZ4_streamHC_t)) return NULL;
1580
if (!LZ4_isAligned(buffer, LZ4_streamHC_t_alignment())) return NULL;
1582
{ LZ4HC_CCtx_internal* const hcstate = &(LZ4_streamHCPtr->internal_donotuse);
1583
MEM_INIT(hcstate, 0, sizeof(*hcstate)); }
1584
LZ4_setCompressionLevel(LZ4_streamHCPtr, LZ4HC_CLEVEL_DEFAULT);
1585
return LZ4_streamHCPtr;
1589
void LZ4_resetStreamHC (LZ4_streamHC_t* LZ4_streamHCPtr, int compressionLevel)
1591
LZ4_initStreamHC(LZ4_streamHCPtr, sizeof(*LZ4_streamHCPtr));
1592
LZ4_setCompressionLevel(LZ4_streamHCPtr, compressionLevel);
1595
void LZ4_resetStreamHC_fast (LZ4_streamHC_t* LZ4_streamHCPtr, int compressionLevel)
1597
LZ4HC_CCtx_internal* const s = &LZ4_streamHCPtr->internal_donotuse;
1598
DEBUGLOG(5, "LZ4_resetStreamHC_fast(%p, %d)", LZ4_streamHCPtr, compressionLevel);
1600
LZ4_initStreamHC(LZ4_streamHCPtr, sizeof(*LZ4_streamHCPtr));
1602
assert(s->end >= s->prefixStart);
1603
s->dictLimit += (U32)(s->end - s->prefixStart);
1604
s->prefixStart = NULL;
1608
LZ4_setCompressionLevel(LZ4_streamHCPtr, compressionLevel);
1611
void LZ4_setCompressionLevel(LZ4_streamHC_t* LZ4_streamHCPtr, int compressionLevel)
1613
DEBUGLOG(5, "LZ4_setCompressionLevel(%p, %d)", LZ4_streamHCPtr, compressionLevel);
1614
if (compressionLevel < 1) compressionLevel = LZ4HC_CLEVEL_DEFAULT;
1615
if (compressionLevel > LZ4HC_CLEVEL_MAX) compressionLevel = LZ4HC_CLEVEL_MAX;
1616
LZ4_streamHCPtr->internal_donotuse.compressionLevel = (short)compressionLevel;
1619
void LZ4_favorDecompressionSpeed(LZ4_streamHC_t* LZ4_streamHCPtr, int favor)
1621
LZ4_streamHCPtr->internal_donotuse.favorDecSpeed = (favor!=0);
1626
int LZ4_loadDictHC (LZ4_streamHC_t* LZ4_streamHCPtr,
1627
const char* dictionary, int dictSize)
1629
LZ4HC_CCtx_internal* const ctxPtr = &LZ4_streamHCPtr->internal_donotuse;
1631
DEBUGLOG(4, "LZ4_loadDictHC(ctx:%p, dict:%p, dictSize:%d, clevel=%d)", LZ4_streamHCPtr, dictionary, dictSize, ctxPtr->compressionLevel);
1632
assert(dictSize >= 0);
1633
assert(LZ4_streamHCPtr != NULL);
1634
if (dictSize > 64 KB) {
1635
dictionary += (size_t)dictSize - 64 KB;
1639
{ int const cLevel = ctxPtr->compressionLevel;
1640
LZ4_initStreamHC(LZ4_streamHCPtr, sizeof(*LZ4_streamHCPtr));
1641
LZ4_setCompressionLevel(LZ4_streamHCPtr, cLevel);
1642
cp = LZ4HC_getCLevelParams(cLevel);
1644
LZ4HC_init_internal (ctxPtr, (const BYTE*)dictionary);
1645
ctxPtr->end = (const BYTE*)dictionary + dictSize;
1646
if (cp.strat == lz4mid) {
1647
LZ4MID_fillHTable (ctxPtr, dictionary, (size_t)dictSize);
1649
if (dictSize >= LZ4HC_HASHSIZE) LZ4HC_Insert (ctxPtr, ctxPtr->end-3);
1654
void LZ4_attach_HC_dictionary(LZ4_streamHC_t *working_stream, const LZ4_streamHC_t *dictionary_stream) {
1655
working_stream->internal_donotuse.dictCtx = dictionary_stream != NULL ? &(dictionary_stream->internal_donotuse) : NULL;
1660
static void LZ4HC_setExternalDict(LZ4HC_CCtx_internal* ctxPtr, const BYTE* newBlock)
1662
DEBUGLOG(4, "LZ4HC_setExternalDict(%p, %p)", ctxPtr, newBlock);
1663
if ( (ctxPtr->end >= ctxPtr->prefixStart + 4)
1664
&& (LZ4HC_getCLevelParams(ctxPtr->compressionLevel).strat != lz4mid) ) {
1665
LZ4HC_Insert (ctxPtr, ctxPtr->end-3);
1669
ctxPtr->lowLimit = ctxPtr->dictLimit;
1670
ctxPtr->dictStart = ctxPtr->prefixStart;
1671
ctxPtr->dictLimit += (U32)(ctxPtr->end - ctxPtr->prefixStart);
1672
ctxPtr->prefixStart = newBlock;
1673
ctxPtr->end = newBlock;
1674
ctxPtr->nextToUpdate = ctxPtr->dictLimit;
1677
ctxPtr->dictCtx = NULL;
1681
LZ4_compressHC_continue_generic (LZ4_streamHC_t* LZ4_streamHCPtr,
1682
const char* src, char* dst,
1683
int* srcSizePtr, int dstCapacity,
1684
limitedOutput_directive limit)
1686
LZ4HC_CCtx_internal* const ctxPtr = &LZ4_streamHCPtr->internal_donotuse;
1687
DEBUGLOG(5, "LZ4_compressHC_continue_generic(ctx=%p, src=%p, srcSize=%d, limit=%d)",
1688
LZ4_streamHCPtr, src, *srcSizePtr, limit);
1689
assert(ctxPtr != NULL);
1691
if (ctxPtr->prefixStart == NULL)
1692
LZ4HC_init_internal (ctxPtr, (const BYTE*) src);
1695
if ((size_t)(ctxPtr->end - ctxPtr->prefixStart) + ctxPtr->dictLimit > 2 GB) {
1696
size_t dictSize = (size_t)(ctxPtr->end - ctxPtr->prefixStart);
1697
if (dictSize > 64 KB) dictSize = 64 KB;
1698
LZ4_loadDictHC(LZ4_streamHCPtr, (const char*)(ctxPtr->end) - dictSize, (int)dictSize);
1702
if ((const BYTE*)src != ctxPtr->end)
1703
LZ4HC_setExternalDict(ctxPtr, (const BYTE*)src);
1706
{ const BYTE* sourceEnd = (const BYTE*) src + *srcSizePtr;
1707
const BYTE* const dictBegin = ctxPtr->dictStart;
1708
const BYTE* const dictEnd = ctxPtr->dictStart + (ctxPtr->dictLimit - ctxPtr->lowLimit);
1709
if ((sourceEnd > dictBegin) && ((const BYTE*)src < dictEnd)) {
1710
if (sourceEnd > dictEnd) sourceEnd = dictEnd;
1711
ctxPtr->lowLimit += (U32)(sourceEnd - ctxPtr->dictStart);
1712
ctxPtr->dictStart += (U32)(sourceEnd - ctxPtr->dictStart);
1714
if (ctxPtr->dictLimit - ctxPtr->lowLimit < LZ4HC_HASHSIZE) {
1715
ctxPtr->lowLimit = ctxPtr->dictLimit;
1716
ctxPtr->dictStart = ctxPtr->prefixStart;
1719
return LZ4HC_compress_generic (ctxPtr, src, dst, srcSizePtr, dstCapacity, ctxPtr->compressionLevel, limit);
1722
int LZ4_compress_HC_continue (LZ4_streamHC_t* LZ4_streamHCPtr, const char* src, char* dst, int srcSize, int dstCapacity)
1724
DEBUGLOG(5, "LZ4_compress_HC_continue");
1725
if (dstCapacity < LZ4_compressBound(srcSize))
1726
return LZ4_compressHC_continue_generic (LZ4_streamHCPtr, src, dst, &srcSize, dstCapacity, limitedOutput);
1728
return LZ4_compressHC_continue_generic (LZ4_streamHCPtr, src, dst, &srcSize, dstCapacity, notLimited);
1731
int LZ4_compress_HC_continue_destSize (LZ4_streamHC_t* LZ4_streamHCPtr, const char* src, char* dst, int* srcSizePtr, int targetDestSize)
1733
return LZ4_compressHC_continue_generic(LZ4_streamHCPtr, src, dst, srcSizePtr, targetDestSize, fillOutput);
1742
int LZ4_saveDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, char* safeBuffer, int dictSize)
1744
LZ4HC_CCtx_internal* const streamPtr = &LZ4_streamHCPtr->internal_donotuse;
1745
int const prefixSize = (int)(streamPtr->end - streamPtr->prefixStart);
1746
DEBUGLOG(5, "LZ4_saveDictHC(%p, %p, %d)", LZ4_streamHCPtr, safeBuffer, dictSize);
1747
assert(prefixSize >= 0);
1748
if (dictSize > 64 KB) dictSize = 64 KB;
1749
if (dictSize < 4) dictSize = 0;
1750
if (dictSize > prefixSize) dictSize = prefixSize;
1751
if (safeBuffer == NULL) assert(dictSize == 0);
1753
LZ4_memmove(safeBuffer, streamPtr->end - dictSize, (size_t)dictSize);
1754
{ U32 const endIndex = (U32)(streamPtr->end - streamPtr->prefixStart) + streamPtr->dictLimit;
1755
streamPtr->end = (safeBuffer == NULL) ? NULL : (const BYTE*)safeBuffer + dictSize;
1756
streamPtr->prefixStart = (const BYTE*)safeBuffer;
1757
streamPtr->dictLimit = endIndex - (U32)dictSize;
1758
streamPtr->lowLimit = endIndex - (U32)dictSize;
1759
streamPtr->dictStart = streamPtr->prefixStart;
1760
if (streamPtr->nextToUpdate < streamPtr->dictLimit)
1761
streamPtr->nextToUpdate = streamPtr->dictLimit;
1778
LZ4_FORCE_INLINE int LZ4HC_literalsPrice(int const litlen)
1781
assert(litlen >= 0);
1782
if (litlen >= (int)RUN_MASK)
1783
price += 1 + ((litlen-(int)RUN_MASK) / 255);
1788
LZ4_FORCE_INLINE int LZ4HC_sequencePrice(int litlen, int mlen)
1791
assert(litlen >= 0);
1792
assert(mlen >= MINMATCH);
1794
price += LZ4HC_literalsPrice(litlen);
1796
if (mlen >= (int)(ML_MASK+MINMATCH))
1797
price += 1 + ((mlen-(int)(ML_MASK+MINMATCH)) / 255);
1802
LZ4_FORCE_INLINE LZ4HC_match_t
1803
LZ4HC_FindLongerMatch(LZ4HC_CCtx_internal* const ctx,
1804
const BYTE* ip, const BYTE* const iHighLimit,
1805
int minLen, int nbSearches,
1806
const dictCtx_directive dict,
1807
const HCfavor_e favorDecSpeed)
1809
LZ4HC_match_t const match0 = { 0 , 0, 0 };
1813
LZ4HC_match_t md = LZ4HC_InsertAndGetWiderMatch(ctx, ip, ip, iHighLimit, minLen, nbSearches, 1 , 1 , dict, favorDecSpeed);
1814
assert(md.back == 0);
1815
if (md.len <= minLen) return match0;
1816
if (favorDecSpeed) {
1817
if ((md.len>18) & (md.len<=36)) md.len=18;
1823
static int LZ4HC_compress_optimal ( LZ4HC_CCtx_internal* ctx,
1824
const char* const source,
1828
int const nbSearches,
1829
size_t sufficient_len,
1830
const limitedOutput_directive limit,
1831
int const fullUpdate,
1832
const dictCtx_directive dict,
1833
const HCfavor_e favorDecSpeed)
1836
#define TRAILING_LITERALS 3
1837
#if defined(LZ4HC_HEAPMODE) && LZ4HC_HEAPMODE==1
1838
LZ4HC_optimal_t* const opt = (LZ4HC_optimal_t*)ALLOC(sizeof(LZ4HC_optimal_t) * (LZ4_OPT_NUM + TRAILING_LITERALS));
1840
LZ4HC_optimal_t opt[LZ4_OPT_NUM + TRAILING_LITERALS];
1843
const BYTE* ip = (const BYTE*) source;
1844
const BYTE* anchor = ip;
1845
const BYTE* const iend = ip + *srcSizePtr;
1846
const BYTE* const mflimit = iend - MFLIMIT;
1847
const BYTE* const matchlimit = iend - LASTLITERALS;
1848
BYTE* op = (BYTE*) dst;
1849
BYTE* opSaved = (BYTE*) dst;
1850
BYTE* oend = op + dstCapacity;
1851
int ovml = MINMATCH;
1855
#if defined(LZ4HC_HEAPMODE) && LZ4HC_HEAPMODE==1
1856
if (opt == NULL) goto _return_label;
1858
DEBUGLOG(5, "LZ4HC_compress_optimal(dst=%p, dstCapa=%u)", dst, (unsigned)dstCapacity);
1860
if (limit == fillOutput) oend -= LASTLITERALS;
1861
if (sufficient_len >= LZ4_OPT_NUM) sufficient_len = LZ4_OPT_NUM-1;
1864
while (ip <= mflimit) {
1865
int const llen = (int)(ip - anchor);
1866
int best_mlen, best_off;
1867
int cur, last_match_pos = 0;
1869
LZ4HC_match_t const firstMatch = LZ4HC_FindLongerMatch(ctx, ip, matchlimit, MINMATCH-1, nbSearches, dict, favorDecSpeed);
1870
if (firstMatch.len==0) { ip++; continue; }
1872
if ((size_t)firstMatch.len > sufficient_len) {
1874
int const firstML = firstMatch.len;
1876
if ( LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor), firstML, firstMatch.off, limit, oend) ) {
1878
ovoff = firstMatch.off;
1879
goto _dest_overflow;
1886
for (rPos = 0 ; rPos < MINMATCH ; rPos++) {
1887
int const cost = LZ4HC_literalsPrice(llen + rPos);
1890
opt[rPos].litlen = llen + rPos;
1891
opt[rPos].price = cost;
1892
DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i) -- initial setup",
1893
rPos, cost, opt[rPos].litlen);
1896
{ int const matchML = firstMatch.len;
1897
int const offset = firstMatch.off;
1899
assert(matchML < LZ4_OPT_NUM);
1900
for (mlen = MINMATCH ; mlen <= matchML ; mlen++) {
1901
int const cost = LZ4HC_sequencePrice(llen, mlen);
1902
opt[mlen].mlen = mlen;
1903
opt[mlen].off = offset;
1904
opt[mlen].litlen = llen;
1905
opt[mlen].price = cost;
1906
DEBUGLOG(7, "rPos:%3i => price:%3i (matchlen=%i) -- initial setup",
1909
last_match_pos = firstMatch.len;
1911
for (addLit = 1; addLit <= TRAILING_LITERALS; addLit ++) {
1912
opt[last_match_pos+addLit].mlen = 1;
1913
opt[last_match_pos+addLit].off = 0;
1914
opt[last_match_pos+addLit].litlen = addLit;
1915
opt[last_match_pos+addLit].price = opt[last_match_pos].price + LZ4HC_literalsPrice(addLit);
1916
DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i) -- initial setup",
1917
last_match_pos+addLit, opt[last_match_pos+addLit].price, addLit);
1921
for (cur = 1; cur < last_match_pos; cur++) {
1922
const BYTE* const curPtr = ip + cur;
1923
LZ4HC_match_t newMatch;
1925
if (curPtr > mflimit) break;
1926
DEBUGLOG(7, "rPos:%u[%u] vs [%u]%u",
1927
cur, opt[cur].price, opt[cur+1].price, cur+1);
1930
if ( (opt[cur+1].price <= opt[cur].price)
1932
&& (opt[cur+MINMATCH].price < opt[cur].price + 3) )
1936
if (opt[cur+1].price <= opt[cur].price) continue;
1939
DEBUGLOG(7, "search at rPos:%u", cur);
1941
newMatch = LZ4HC_FindLongerMatch(ctx, curPtr, matchlimit, MINMATCH-1, nbSearches, dict, favorDecSpeed);
1944
newMatch = LZ4HC_FindLongerMatch(ctx, curPtr, matchlimit, last_match_pos - cur, nbSearches, dict, favorDecSpeed);
1945
if (!newMatch.len) continue;
1947
if ( ((size_t)newMatch.len > sufficient_len)
1948
|| (newMatch.len + cur >= LZ4_OPT_NUM) ) {
1950
best_mlen = newMatch.len;
1951
best_off = newMatch.off;
1952
last_match_pos = cur + 1;
1957
{ int const baseLitlen = opt[cur].litlen;
1959
for (litlen = 1; litlen < MINMATCH; litlen++) {
1960
int const price = opt[cur].price - LZ4HC_literalsPrice(baseLitlen) + LZ4HC_literalsPrice(baseLitlen+litlen);
1961
int const pos = cur + litlen;
1962
if (price < opt[pos].price) {
1965
opt[pos].litlen = baseLitlen+litlen;
1966
opt[pos].price = price;
1967
DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i)",
1968
pos, price, opt[pos].litlen);
1972
{ int const matchML = newMatch.len;
1975
assert(cur + newMatch.len < LZ4_OPT_NUM);
1976
for ( ; ml <= matchML ; ml++) {
1977
int const pos = cur + ml;
1978
int const offset = newMatch.off;
1981
DEBUGLOG(7, "testing price rPos %i (last_match_pos=%i)",
1982
pos, last_match_pos);
1983
if (opt[cur].mlen == 1) {
1984
ll = opt[cur].litlen;
1985
price = ((cur > ll) ? opt[cur - ll].price : 0)
1986
+ LZ4HC_sequencePrice(ll, ml);
1989
price = opt[cur].price + LZ4HC_sequencePrice(0, ml);
1992
assert((U32)favorDecSpeed <= 1);
1993
if (pos > last_match_pos+TRAILING_LITERALS
1994
|| price <= opt[pos].price - (int)favorDecSpeed) {
1995
DEBUGLOG(7, "rPos:%3i => price:%3i (matchlen=%i)",
1997
assert(pos < LZ4_OPT_NUM);
1998
if ( (ml == matchML)
1999
&& (last_match_pos < pos) )
2000
last_match_pos = pos;
2002
opt[pos].off = offset;
2003
opt[pos].litlen = ll;
2004
opt[pos].price = price;
2008
for (addLit = 1; addLit <= TRAILING_LITERALS; addLit ++) {
2009
opt[last_match_pos+addLit].mlen = 1;
2010
opt[last_match_pos+addLit].off = 0;
2011
opt[last_match_pos+addLit].litlen = addLit;
2012
opt[last_match_pos+addLit].price = opt[last_match_pos].price + LZ4HC_literalsPrice(addLit);
2013
DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i)", last_match_pos+addLit, opt[last_match_pos+addLit].price, addLit);
2017
assert(last_match_pos < LZ4_OPT_NUM + TRAILING_LITERALS);
2018
best_mlen = opt[last_match_pos].mlen;
2019
best_off = opt[last_match_pos].off;
2020
cur = last_match_pos - best_mlen;
2023
assert(cur < LZ4_OPT_NUM);
2024
assert(last_match_pos >= 1);
2025
DEBUGLOG(6, "reverse traversal, looking for shortest path (last_match_pos=%i)", last_match_pos);
2026
{ int candidate_pos = cur;
2027
int selected_matchLength = best_mlen;
2028
int selected_offset = best_off;
2030
int const next_matchLength = opt[candidate_pos].mlen;
2031
int const next_offset = opt[candidate_pos].off;
2032
DEBUGLOG(7, "pos %i: sequence length %i", candidate_pos, selected_matchLength);
2033
opt[candidate_pos].mlen = selected_matchLength;
2034
opt[candidate_pos].off = selected_offset;
2035
selected_matchLength = next_matchLength;
2036
selected_offset = next_offset;
2037
if (next_matchLength > candidate_pos) break;
2038
assert(next_matchLength > 0);
2039
candidate_pos -= next_matchLength;
2044
while (rPos < last_match_pos) {
2045
int const ml = opt[rPos].mlen;
2046
int const offset = opt[rPos].off;
2047
if (ml == 1) { ip++; rPos++; continue; }
2049
assert(ml >= MINMATCH);
2050
assert((offset >= 1) && (offset <= LZ4_DISTANCE_MAX));
2052
if ( LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor), ml, offset, limit, oend) ) {
2055
goto _dest_overflow;
2061
{ size_t lastRunSize = (size_t)(iend - anchor);
2062
size_t llAdd = (lastRunSize + 255 - RUN_MASK) / 255;
2063
size_t const totalSize = 1 + llAdd + lastRunSize;
2064
if (limit == fillOutput) oend += LASTLITERALS;
2065
if (limit && (op + totalSize > oend)) {
2066
if (limit == limitedOutput) {
2071
lastRunSize = (size_t)(oend - op) - 1 ;
2072
llAdd = (lastRunSize + 256 - RUN_MASK) / 256;
2073
lastRunSize -= llAdd;
2075
DEBUGLOG(6, "Final literal run : %i literals", (int)lastRunSize);
2076
ip = anchor + lastRunSize;
2078
if (lastRunSize >= RUN_MASK) {
2079
size_t accumulator = lastRunSize - RUN_MASK;
2080
*op++ = (RUN_MASK << ML_BITS);
2081
for(; accumulator >= 255 ; accumulator -= 255) *op++ = 255;
2082
*op++ = (BYTE) accumulator;
2084
*op++ = (BYTE)(lastRunSize << ML_BITS);
2086
LZ4_memcpy(op, anchor, lastRunSize);
2091
*srcSizePtr = (int) (((const char*)ip) - source);
2092
retval = (int) ((char*)op-dst);
2096
if (limit == fillOutput) {
2098
size_t const ll = (size_t)(ip - anchor);
2099
size_t const ll_addbytes = (ll + 240) / 255;
2100
size_t const ll_totalCost = 1 + ll_addbytes + ll;
2101
BYTE* const maxLitPos = oend - 3;
2102
DEBUGLOG(6, "Last sequence overflowing (only %i bytes remaining)", (int)(oend-1-opSaved));
2104
if (op + ll_totalCost <= maxLitPos) {
2106
size_t const bytesLeftForMl = (size_t)(maxLitPos - (op+ll_totalCost));
2107
size_t const maxMlSize = MINMATCH + (ML_MASK-1) + (bytesLeftForMl * 255);
2108
assert(maxMlSize < INT_MAX); assert(ovml >= 0);
2109
if ((size_t)ovml > maxMlSize) ovml = (int)maxMlSize;
2110
if ((oend + LASTLITERALS) - (op + ll_totalCost + 2) - 1 + ovml >= MFLIMIT) {
2111
DEBUGLOG(6, "Space to end : %i + ml (%i)", (int)((oend + LASTLITERALS) - (op + ll_totalCost + 2) - 1), ovml);
2112
DEBUGLOG(6, "Before : ip = %p, anchor = %p", ip, anchor);
2113
LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor), ovml, ovoff, notLimited, oend);
2114
DEBUGLOG(6, "After : ip = %p, anchor = %p", ip, anchor);
2116
goto _last_literals;
2119
#if defined(LZ4HC_HEAPMODE) && LZ4HC_HEAPMODE==1
2120
if (opt) FREEMEM(opt);
2133
int LZ4_compressHC(const char* src, char* dst, int srcSize) { return LZ4_compress_HC (src, dst, srcSize, LZ4_compressBound(srcSize), 0); }
2134
int LZ4_compressHC_limitedOutput(const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_HC(src, dst, srcSize, maxDstSize, 0); }
2135
int LZ4_compressHC2(const char* src, char* dst, int srcSize, int cLevel) { return LZ4_compress_HC (src, dst, srcSize, LZ4_compressBound(srcSize), cLevel); }
2136
int LZ4_compressHC2_limitedOutput(const char* src, char* dst, int srcSize, int maxDstSize, int cLevel) { return LZ4_compress_HC(src, dst, srcSize, maxDstSize, cLevel); }
2137
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); }
2138
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); }
2139
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); }
2140
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); }
2141
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)); }
2142
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); }
2146
int LZ4_sizeofStreamStateHC(void) { return sizeof(LZ4_streamHC_t); }
2150
int LZ4_resetStreamStateHC(void* state, char* inputBuffer)
2152
LZ4_streamHC_t* const hc4 = LZ4_initStreamHC(state, sizeof(*hc4));
2153
if (hc4 == NULL) return 1;
2154
LZ4HC_init_internal (&hc4->internal_donotuse, (const BYTE*)inputBuffer);
2158
#if !defined(LZ4_STATIC_LINKING_ONLY_DISABLE_MEMORY_ALLOCATION)
2159
void* LZ4_createHC (const char* inputBuffer)
2161
LZ4_streamHC_t* const hc4 = LZ4_createStreamHC();
2162
if (hc4 == NULL) return NULL;
2163
LZ4HC_init_internal (&hc4->internal_donotuse, (const BYTE*)inputBuffer);
2167
int LZ4_freeHC (void* LZ4HC_Data)
2169
if (!LZ4HC_Data) return 0;
2170
FREEMEM(LZ4HC_Data);
2175
int LZ4_compressHC2_continue (void* LZ4HC_Data, const char* src, char* dst, int srcSize, int cLevel)
2177
return LZ4HC_compress_generic (&((LZ4_streamHC_t*)LZ4HC_Data)->internal_donotuse, src, dst, &srcSize, 0, cLevel, notLimited);
2180
int LZ4_compressHC2_limitedOutput_continue (void* LZ4HC_Data, const char* src, char* dst, int srcSize, int dstCapacity, int cLevel)
2182
return LZ4HC_compress_generic (&((LZ4_streamHC_t*)LZ4HC_Data)->internal_donotuse, src, dst, &srcSize, dstCapacity, cLevel, limitedOutput);
2185
char* LZ4_slideInputBufferHC(void* LZ4HC_Data)
2187
LZ4HC_CCtx_internal* const s = &((LZ4_streamHC_t*)LZ4HC_Data)->internal_donotuse;
2188
const BYTE* const bufferStart = s->prefixStart - s->dictLimit + s->lowLimit;
2189
LZ4_resetStreamHC_fast((LZ4_streamHC_t*)LZ4HC_Data, s->compressionLevel);
2191
return (char*)(uptrval)bufferStart;