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