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