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