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