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