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