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