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