Commit | Line | Data |
---|---|---|
c72ac7a1 CM |
1 | /* |
2 | * LZ4 HC - High Compression Mode of LZ4 | |
4e1a33b1 | 3 | * Copyright (C) 2011-2015, Yann Collet. |
c72ac7a1 | 4 | * |
4e1a33b1 | 5 | * BSD 2 - Clause License (http://www.opensource.org/licenses/bsd - license.php) |
c72ac7a1 CM |
6 | * Redistribution and use in source and binary forms, with or without |
7 | * modification, are permitted provided that the following conditions are | |
8 | * met: | |
4e1a33b1 SS |
9 | * * Redistributions of source code must retain the above copyright |
10 | * notice, this list of conditions and the following disclaimer. | |
11 | * * Redistributions in binary form must reproduce the above | |
c72ac7a1 CM |
12 | * copyright notice, this list of conditions and the following disclaimer |
13 | * in the documentation and/or other materials provided with the | |
14 | * distribution. | |
c72ac7a1 CM |
15 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
16 | * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
17 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
18 | * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
19 | * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
20 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
21 | * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
22 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
23 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
24 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
25 | * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
c72ac7a1 | 26 | * You can contact the author at : |
4e1a33b1 SS |
27 | * - LZ4 homepage : http://www.lz4.org |
28 | * - LZ4 source repository : https://github.com/lz4/lz4 | |
c72ac7a1 | 29 | * |
4e1a33b1 SS |
30 | * Changed for kernel usage by: |
31 | * Sven Schmidt <4sschmid@informatik.uni-hamburg.de> | |
c72ac7a1 CM |
32 | */ |
33 | ||
4e1a33b1 SS |
34 | /*-************************************ |
35 | * Dependencies | |
36 | **************************************/ | |
c72ac7a1 | 37 | #include <linux/lz4.h> |
c72ac7a1 | 38 | #include "lz4defs.h" |
4e1a33b1 SS |
39 | #include <linux/module.h> |
40 | #include <linux/kernel.h> | |
41 | #include <linux/string.h> /* memset */ | |
42 | ||
43 | /* ************************************* | |
44 | * Local Constants and types | |
45 | ***************************************/ | |
c72ac7a1 | 46 | |
4e1a33b1 | 47 | #define OPTIMAL_ML (int)((ML_MASK - 1) + MINMATCH) |
c72ac7a1 | 48 | |
4e1a33b1 SS |
49 | #define HASH_FUNCTION(i) (((i) * 2654435761U) \ |
50 | >> ((MINMATCH*8) - LZ4HC_HASH_LOG)) | |
51 | #define DELTANEXTU16(p) chainTable[(U16)(p)] /* faster */ | |
52 | ||
53 | static U32 LZ4HC_hashPtr(const void *ptr) | |
54 | { | |
55 | return HASH_FUNCTION(LZ4_read32(ptr)); | |
56 | } | |
57 | ||
58 | /************************************** | |
59 | * HC Compression | |
60 | **************************************/ | |
61 | static void LZ4HC_init(LZ4HC_CCtx_internal *hc4, const BYTE *start) | |
c72ac7a1 | 62 | { |
4e1a33b1 SS |
63 | memset((void *)hc4->hashTable, 0, sizeof(hc4->hashTable)); |
64 | memset(hc4->chainTable, 0xFF, sizeof(hc4->chainTable)); | |
65 | hc4->nextToUpdate = 64 * KB; | |
66 | hc4->base = start - 64 * KB; | |
67 | hc4->end = start; | |
68 | hc4->dictBase = start - 64 * KB; | |
69 | hc4->dictLimit = 64 * KB; | |
70 | hc4->lowLimit = 64 * KB; | |
c72ac7a1 CM |
71 | } |
72 | ||
73 | /* Update chains up to ip (excluded) */ | |
4e1a33b1 SS |
74 | static FORCE_INLINE void LZ4HC_Insert(LZ4HC_CCtx_internal *hc4, |
75 | const BYTE *ip) | |
c72ac7a1 | 76 | { |
4e1a33b1 SS |
77 | U16 * const chainTable = hc4->chainTable; |
78 | U32 * const hashTable = hc4->hashTable; | |
c72ac7a1 | 79 | const BYTE * const base = hc4->base; |
4e1a33b1 SS |
80 | U32 const target = (U32)(ip - base); |
81 | U32 idx = hc4->nextToUpdate; | |
82 | ||
83 | while (idx < target) { | |
84 | U32 const h = LZ4HC_hashPtr(base + idx); | |
85 | size_t delta = idx - hashTable[h]; | |
c72ac7a1 | 86 | |
c72ac7a1 CM |
87 | if (delta > MAX_DISTANCE) |
88 | delta = MAX_DISTANCE; | |
c72ac7a1 | 89 | |
4e1a33b1 | 90 | DELTANEXTU16(idx) = (U16)delta; |
c72ac7a1 | 91 | |
4e1a33b1 SS |
92 | hashTable[h] = idx; |
93 | idx++; | |
c72ac7a1 | 94 | } |
4e1a33b1 SS |
95 | |
96 | hc4->nextToUpdate = target; | |
c72ac7a1 CM |
97 | } |
98 | ||
4e1a33b1 SS |
99 | static FORCE_INLINE int LZ4HC_InsertAndFindBestMatch( |
100 | LZ4HC_CCtx_internal *hc4, /* Index table will be updated */ | |
101 | const BYTE *ip, | |
102 | const BYTE * const iLimit, | |
103 | const BYTE **matchpos, | |
104 | const int maxNbAttempts) | |
c72ac7a1 | 105 | { |
4e1a33b1 SS |
106 | U16 * const chainTable = hc4->chainTable; |
107 | U32 * const HashTable = hc4->hashTable; | |
c72ac7a1 | 108 | const BYTE * const base = hc4->base; |
4e1a33b1 SS |
109 | const BYTE * const dictBase = hc4->dictBase; |
110 | const U32 dictLimit = hc4->dictLimit; | |
111 | const U32 lowLimit = (hc4->lowLimit + 64 * KB > (U32)(ip - base)) | |
112 | ? hc4->lowLimit | |
113 | : (U32)(ip - base) - (64 * KB - 1); | |
114 | U32 matchIndex; | |
115 | int nbAttempts = maxNbAttempts; | |
116 | size_t ml = 0; | |
c72ac7a1 CM |
117 | |
118 | /* HC4 match finder */ | |
4e1a33b1 SS |
119 | LZ4HC_Insert(hc4, ip); |
120 | matchIndex = HashTable[LZ4HC_hashPtr(ip)]; | |
121 | ||
122 | while ((matchIndex >= lowLimit) | |
123 | && (nbAttempts)) { | |
124 | nbAttempts--; | |
125 | if (matchIndex >= dictLimit) { | |
126 | const BYTE * const match = base + matchIndex; | |
127 | ||
128 | if (*(match + ml) == *(ip + ml) | |
129 | && (LZ4_read32(match) == LZ4_read32(ip))) { | |
130 | size_t const mlt = LZ4_count(ip + MINMATCH, | |
131 | match + MINMATCH, iLimit) + MINMATCH; | |
c72ac7a1 | 132 | |
c72ac7a1 CM |
133 | if (mlt > ml) { |
134 | ml = mlt; | |
4e1a33b1 SS |
135 | *matchpos = match; |
136 | } | |
137 | } | |
138 | } else { | |
139 | const BYTE * const match = dictBase + matchIndex; | |
140 | ||
141 | if (LZ4_read32(match) == LZ4_read32(ip)) { | |
142 | size_t mlt; | |
143 | const BYTE *vLimit = ip | |
144 | + (dictLimit - matchIndex); | |
145 | ||
146 | if (vLimit > iLimit) | |
147 | vLimit = iLimit; | |
148 | mlt = LZ4_count(ip + MINMATCH, | |
149 | match + MINMATCH, vLimit) + MINMATCH; | |
150 | if ((ip + mlt == vLimit) | |
151 | && (vLimit < iLimit)) | |
152 | mlt += LZ4_count(ip + mlt, | |
153 | base + dictLimit, | |
154 | iLimit); | |
155 | if (mlt > ml) { | |
156 | /* virtual matchpos */ | |
157 | ml = mlt; | |
158 | *matchpos = base + matchIndex; | |
c72ac7a1 CM |
159 | } |
160 | } | |
161 | } | |
4e1a33b1 | 162 | matchIndex -= DELTANEXTU16(matchIndex); |
c72ac7a1 CM |
163 | } |
164 | ||
165 | return (int)ml; | |
166 | } | |
167 | ||
4e1a33b1 SS |
168 | static FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch( |
169 | LZ4HC_CCtx_internal *hc4, | |
170 | const BYTE * const ip, | |
171 | const BYTE * const iLowLimit, | |
172 | const BYTE * const iHighLimit, | |
173 | int longest, | |
174 | const BYTE **matchpos, | |
175 | const BYTE **startpos, | |
176 | const int maxNbAttempts) | |
c72ac7a1 | 177 | { |
4e1a33b1 SS |
178 | U16 * const chainTable = hc4->chainTable; |
179 | U32 * const HashTable = hc4->hashTable; | |
c72ac7a1 | 180 | const BYTE * const base = hc4->base; |
4e1a33b1 SS |
181 | const U32 dictLimit = hc4->dictLimit; |
182 | const BYTE * const lowPrefixPtr = base + dictLimit; | |
183 | const U32 lowLimit = (hc4->lowLimit + 64 * KB > (U32)(ip - base)) | |
184 | ? hc4->lowLimit | |
185 | : (U32)(ip - base) - (64 * KB - 1); | |
186 | const BYTE * const dictBase = hc4->dictBase; | |
187 | U32 matchIndex; | |
188 | int nbAttempts = maxNbAttempts; | |
189 | int delta = (int)(ip - iLowLimit); | |
c72ac7a1 CM |
190 | |
191 | /* First Match */ | |
4e1a33b1 SS |
192 | LZ4HC_Insert(hc4, ip); |
193 | matchIndex = HashTable[LZ4HC_hashPtr(ip)]; | |
194 | ||
195 | while ((matchIndex >= lowLimit) | |
196 | && (nbAttempts)) { | |
197 | nbAttempts--; | |
198 | if (matchIndex >= dictLimit) { | |
199 | const BYTE *matchPtr = base + matchIndex; | |
200 | ||
201 | if (*(iLowLimit + longest) | |
202 | == *(matchPtr - delta + longest)) { | |
203 | if (LZ4_read32(matchPtr) == LZ4_read32(ip)) { | |
204 | int mlt = MINMATCH + LZ4_count( | |
205 | ip + MINMATCH, | |
206 | matchPtr + MINMATCH, | |
207 | iHighLimit); | |
208 | int back = 0; | |
209 | ||
210 | while ((ip + back > iLowLimit) | |
211 | && (matchPtr + back > lowPrefixPtr) | |
212 | && (ip[back - 1] == matchPtr[back - 1])) | |
213 | back--; | |
214 | ||
215 | mlt -= back; | |
216 | ||
217 | if (mlt > longest) { | |
218 | longest = (int)mlt; | |
219 | *matchpos = matchPtr + back; | |
220 | *startpos = ip + back; | |
c72ac7a1 | 221 | } |
c72ac7a1 | 222 | } |
4e1a33b1 SS |
223 | } |
224 | } else { | |
225 | const BYTE * const matchPtr = dictBase + matchIndex; | |
226 | ||
227 | if (LZ4_read32(matchPtr) == LZ4_read32(ip)) { | |
228 | size_t mlt; | |
229 | int back = 0; | |
230 | const BYTE *vLimit = ip + (dictLimit - matchIndex); | |
231 | ||
232 | if (vLimit > iHighLimit) | |
233 | vLimit = iHighLimit; | |
234 | ||
235 | mlt = LZ4_count(ip + MINMATCH, | |
236 | matchPtr + MINMATCH, vLimit) + MINMATCH; | |
237 | ||
238 | if ((ip + mlt == vLimit) && (vLimit < iHighLimit)) | |
239 | mlt += LZ4_count(ip + mlt, base + dictLimit, | |
240 | iHighLimit); | |
241 | while ((ip + back > iLowLimit) | |
242 | && (matchIndex + back > lowLimit) | |
243 | && (ip[back - 1] == matchPtr[back - 1])) | |
244 | back--; | |
245 | ||
246 | mlt -= back; | |
247 | ||
248 | if ((int)mlt > longest) { | |
249 | longest = (int)mlt; | |
250 | *matchpos = base + matchIndex + back; | |
251 | *startpos = ip + back; | |
c72ac7a1 CM |
252 | } |
253 | } | |
254 | } | |
4e1a33b1 SS |
255 | |
256 | matchIndex -= DELTANEXTU16(matchIndex); | |
c72ac7a1 | 257 | } |
4e1a33b1 | 258 | |
c72ac7a1 CM |
259 | return longest; |
260 | } | |
261 | ||
4e1a33b1 SS |
262 | static FORCE_INLINE int LZ4HC_encodeSequence( |
263 | const BYTE **ip, | |
264 | BYTE **op, | |
265 | const BYTE **anchor, | |
266 | int matchLength, | |
267 | const BYTE * const match, | |
268 | limitedOutput_directive limitedOutputBuffer, | |
269 | BYTE *oend) | |
c72ac7a1 | 270 | { |
4e1a33b1 SS |
271 | int length; |
272 | BYTE *token; | |
c72ac7a1 CM |
273 | |
274 | /* Encode Literal length */ | |
275 | length = (int)(*ip - *anchor); | |
276 | token = (*op)++; | |
4e1a33b1 SS |
277 | |
278 | if ((limitedOutputBuffer) | |
279 | && ((*op + (length>>8) | |
280 | + length + (2 + 1 + LASTLITERALS)) > oend)) { | |
281 | /* Check output limit */ | |
282 | return 1; | |
283 | } | |
c72ac7a1 | 284 | if (length >= (int)RUN_MASK) { |
4e1a33b1 SS |
285 | int len; |
286 | ||
287 | *token = (RUN_MASK<<ML_BITS); | |
c72ac7a1 CM |
288 | len = length - RUN_MASK; |
289 | for (; len > 254 ; len -= 255) | |
290 | *(*op)++ = 255; | |
4e1a33b1 | 291 | *(*op)++ = (BYTE)len; |
c72ac7a1 | 292 | } else |
4e1a33b1 | 293 | *token = (BYTE)(length<<ML_BITS); |
c72ac7a1 CM |
294 | |
295 | /* Copy Literals */ | |
4e1a33b1 SS |
296 | LZ4_wildCopy(*op, *anchor, (*op) + length); |
297 | *op += length; | |
c72ac7a1 CM |
298 | |
299 | /* Encode Offset */ | |
4e1a33b1 SS |
300 | LZ4_writeLE16(*op, (U16)(*ip - match)); |
301 | *op += 2; | |
c72ac7a1 CM |
302 | |
303 | /* Encode MatchLength */ | |
4e1a33b1 SS |
304 | length = (int)(matchLength - MINMATCH); |
305 | ||
306 | if ((limitedOutputBuffer) | |
307 | && (*op + (length>>8) | |
308 | + (1 + LASTLITERALS) > oend)) { | |
309 | /* Check output limit */ | |
310 | return 1; | |
311 | } | |
312 | ||
313 | if (length >= (int)ML_MASK) { | |
c72ac7a1 | 314 | *token += ML_MASK; |
4e1a33b1 SS |
315 | length -= ML_MASK; |
316 | ||
317 | for (; length > 509 ; length -= 510) { | |
c72ac7a1 CM |
318 | *(*op)++ = 255; |
319 | *(*op)++ = 255; | |
320 | } | |
4e1a33b1 SS |
321 | |
322 | if (length > 254) { | |
323 | length -= 255; | |
c72ac7a1 CM |
324 | *(*op)++ = 255; |
325 | } | |
4e1a33b1 SS |
326 | |
327 | *(*op)++ = (BYTE)length; | |
c72ac7a1 | 328 | } else |
4e1a33b1 | 329 | *token += (BYTE)(length); |
c72ac7a1 CM |
330 | |
331 | /* Prepare next loop */ | |
4e1a33b1 | 332 | *ip += matchLength; |
c72ac7a1 CM |
333 | *anchor = *ip; |
334 | ||
335 | return 0; | |
336 | } | |
337 | ||
4e1a33b1 SS |
338 | static int LZ4HC_compress_generic( |
339 | LZ4HC_CCtx_internal *const ctx, | |
340 | const char * const source, | |
341 | char * const dest, | |
342 | int const inputSize, | |
343 | int const maxOutputSize, | |
344 | int compressionLevel, | |
345 | limitedOutput_directive limit | |
346 | ) | |
c72ac7a1 | 347 | { |
4e1a33b1 SS |
348 | const BYTE *ip = (const BYTE *) source; |
349 | const BYTE *anchor = ip; | |
350 | const BYTE * const iend = ip + inputSize; | |
351 | const BYTE * const mflimit = iend - MFLIMIT; | |
352 | const BYTE * const matchlimit = (iend - LASTLITERALS); | |
c72ac7a1 | 353 | |
4e1a33b1 SS |
354 | BYTE *op = (BYTE *) dest; |
355 | BYTE * const oend = op + maxOutputSize; | |
c72ac7a1 | 356 | |
4e1a33b1 | 357 | unsigned int maxNbAttempts; |
c72ac7a1 | 358 | int ml, ml2, ml3, ml0; |
4e1a33b1 SS |
359 | const BYTE *ref = NULL; |
360 | const BYTE *start2 = NULL; | |
361 | const BYTE *ref2 = NULL; | |
362 | const BYTE *start3 = NULL; | |
363 | const BYTE *ref3 = NULL; | |
364 | const BYTE *start0; | |
365 | const BYTE *ref0; | |
366 | ||
367 | /* init */ | |
368 | if (compressionLevel > LZ4HC_MAX_CLEVEL) | |
369 | compressionLevel = LZ4HC_MAX_CLEVEL; | |
370 | if (compressionLevel < 1) | |
371 | compressionLevel = LZ4HC_DEFAULT_CLEVEL; | |
372 | maxNbAttempts = 1 << (compressionLevel - 1); | |
373 | ctx->end += inputSize; | |
c72ac7a1 CM |
374 | |
375 | ip++; | |
376 | ||
377 | /* Main Loop */ | |
378 | while (ip < mflimit) { | |
4e1a33b1 SS |
379 | ml = LZ4HC_InsertAndFindBestMatch(ctx, ip, |
380 | matchlimit, (&ref), maxNbAttempts); | |
c72ac7a1 CM |
381 | if (!ml) { |
382 | ip++; | |
383 | continue; | |
384 | } | |
385 | ||
386 | /* saved, in case we would skip too much */ | |
387 | start0 = ip; | |
388 | ref0 = ref; | |
389 | ml0 = ml; | |
4e1a33b1 SS |
390 | |
391 | _Search2: | |
392 | if (ip + ml < mflimit) | |
393 | ml2 = LZ4HC_InsertAndGetWiderMatch(ctx, | |
394 | ip + ml - 2, ip + 0, | |
395 | matchlimit, ml, &ref2, | |
396 | &start2, maxNbAttempts); | |
c72ac7a1 CM |
397 | else |
398 | ml2 = ml; | |
4e1a33b1 | 399 | |
c72ac7a1 | 400 | if (ml2 == ml) { |
4e1a33b1 SS |
401 | /* No better match */ |
402 | if (LZ4HC_encodeSequence(&ip, &op, | |
403 | &anchor, ml, ref, limit, oend)) | |
404 | return 0; | |
c72ac7a1 CM |
405 | continue; |
406 | } | |
407 | ||
408 | if (start0 < ip) { | |
c72ac7a1 | 409 | if (start2 < ip + ml0) { |
4e1a33b1 | 410 | /* empirical */ |
c72ac7a1 CM |
411 | ip = start0; |
412 | ref = ref0; | |
413 | ml = ml0; | |
414 | } | |
415 | } | |
4e1a33b1 SS |
416 | |
417 | /* Here, start0 == ip */ | |
c72ac7a1 | 418 | if ((start2 - ip) < 3) { |
4e1a33b1 | 419 | /* First Match too small : removed */ |
c72ac7a1 CM |
420 | ml = ml2; |
421 | ip = start2; | |
422 | ref = ref2; | |
4e1a33b1 | 423 | goto _Search2; |
c72ac7a1 CM |
424 | } |
425 | ||
4e1a33b1 | 426 | _Search3: |
c72ac7a1 | 427 | /* |
4e1a33b1 SS |
428 | * Currently we have : |
429 | * ml2 > ml1, and | |
430 | * ip1 + 3 <= ip2 (usually < ip1 + ml1) | |
431 | */ | |
c72ac7a1 CM |
432 | if ((start2 - ip) < OPTIMAL_ML) { |
433 | int correction; | |
434 | int new_ml = ml; | |
4e1a33b1 | 435 | |
c72ac7a1 CM |
436 | if (new_ml > OPTIMAL_ML) |
437 | new_ml = OPTIMAL_ML; | |
438 | if (ip + new_ml > start2 + ml2 - MINMATCH) | |
439 | new_ml = (int)(start2 - ip) + ml2 - MINMATCH; | |
4e1a33b1 | 440 | |
c72ac7a1 | 441 | correction = new_ml - (int)(start2 - ip); |
4e1a33b1 | 442 | |
c72ac7a1 CM |
443 | if (correction > 0) { |
444 | start2 += correction; | |
445 | ref2 += correction; | |
446 | ml2 -= correction; | |
447 | } | |
448 | } | |
449 | /* | |
4e1a33b1 SS |
450 | * Now, we have start2 = ip + new_ml, |
451 | * with new_ml = min(ml, OPTIMAL_ML = 18) | |
c72ac7a1 | 452 | */ |
4e1a33b1 | 453 | |
c72ac7a1 | 454 | if (start2 + ml2 < mflimit) |
4e1a33b1 SS |
455 | ml3 = LZ4HC_InsertAndGetWiderMatch(ctx, |
456 | start2 + ml2 - 3, start2, | |
457 | matchlimit, ml2, &ref3, &start3, | |
458 | maxNbAttempts); | |
c72ac7a1 CM |
459 | else |
460 | ml3 = ml2; | |
461 | ||
c72ac7a1 | 462 | if (ml3 == ml2) { |
4e1a33b1 | 463 | /* No better match : 2 sequences to encode */ |
c72ac7a1 | 464 | /* ip & ref are known; Now for ml */ |
4e1a33b1 | 465 | if (start2 < ip + ml) |
c72ac7a1 | 466 | ml = (int)(start2 - ip); |
c72ac7a1 | 467 | /* Now, encode 2 sequences */ |
4e1a33b1 SS |
468 | if (LZ4HC_encodeSequence(&ip, &op, &anchor, |
469 | ml, ref, limit, oend)) | |
470 | return 0; | |
c72ac7a1 | 471 | ip = start2; |
4e1a33b1 SS |
472 | if (LZ4HC_encodeSequence(&ip, &op, &anchor, |
473 | ml2, ref2, limit, oend)) | |
474 | return 0; | |
c72ac7a1 CM |
475 | continue; |
476 | } | |
477 | ||
c72ac7a1 | 478 | if (start3 < ip + ml + 3) { |
4e1a33b1 | 479 | /* Not enough space for match 2 : remove it */ |
c72ac7a1 | 480 | if (start3 >= (ip + ml)) { |
4e1a33b1 SS |
481 | /* can write Seq1 immediately |
482 | * ==> Seq2 is removed, | |
483 | * so Seq3 becomes Seq1 | |
484 | */ | |
c72ac7a1 | 485 | if (start2 < ip + ml) { |
4e1a33b1 SS |
486 | int correction = (int)(ip + ml - start2); |
487 | ||
c72ac7a1 CM |
488 | start2 += correction; |
489 | ref2 += correction; | |
490 | ml2 -= correction; | |
491 | if (ml2 < MINMATCH) { | |
492 | start2 = start3; | |
493 | ref2 = ref3; | |
494 | ml2 = ml3; | |
495 | } | |
496 | } | |
497 | ||
4e1a33b1 SS |
498 | if (LZ4HC_encodeSequence(&ip, &op, &anchor, |
499 | ml, ref, limit, oend)) | |
500 | return 0; | |
501 | ip = start3; | |
c72ac7a1 | 502 | ref = ref3; |
4e1a33b1 | 503 | ml = ml3; |
c72ac7a1 CM |
504 | |
505 | start0 = start2; | |
506 | ref0 = ref2; | |
507 | ml0 = ml2; | |
4e1a33b1 | 508 | goto _Search2; |
c72ac7a1 CM |
509 | } |
510 | ||
511 | start2 = start3; | |
512 | ref2 = ref3; | |
513 | ml2 = ml3; | |
4e1a33b1 | 514 | goto _Search3; |
c72ac7a1 CM |
515 | } |
516 | ||
517 | /* | |
4e1a33b1 SS |
518 | * OK, now we have 3 ascending matches; |
519 | * let's write at least the first one | |
520 | * ip & ref are known; Now for ml | |
521 | */ | |
c72ac7a1 CM |
522 | if (start2 < ip + ml) { |
523 | if ((start2 - ip) < (int)ML_MASK) { | |
524 | int correction; | |
4e1a33b1 | 525 | |
c72ac7a1 CM |
526 | if (ml > OPTIMAL_ML) |
527 | ml = OPTIMAL_ML; | |
528 | if (ip + ml > start2 + ml2 - MINMATCH) | |
4e1a33b1 | 529 | ml = (int)(start2 - ip) + ml2 - MINMATCH; |
c72ac7a1 CM |
530 | correction = ml - (int)(start2 - ip); |
531 | if (correction > 0) { | |
532 | start2 += correction; | |
533 | ref2 += correction; | |
534 | ml2 -= correction; | |
535 | } | |
536 | } else | |
537 | ml = (int)(start2 - ip); | |
538 | } | |
4e1a33b1 SS |
539 | if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, |
540 | ref, limit, oend)) | |
541 | return 0; | |
c72ac7a1 CM |
542 | |
543 | ip = start2; | |
544 | ref = ref2; | |
545 | ml = ml2; | |
546 | ||
547 | start2 = start3; | |
548 | ref2 = ref3; | |
549 | ml2 = ml3; | |
550 | ||
4e1a33b1 | 551 | goto _Search3; |
c72ac7a1 CM |
552 | } |
553 | ||
554 | /* Encode Last Literals */ | |
4e1a33b1 SS |
555 | { |
556 | int lastRun = (int)(iend - anchor); | |
557 | ||
558 | if ((limit) | |
559 | && (((char *)op - dest) + lastRun + 1 | |
560 | + ((lastRun + 255 - RUN_MASK)/255) | |
561 | > (U32)maxOutputSize)) { | |
562 | /* Check output limit */ | |
563 | return 0; | |
564 | } | |
565 | if (lastRun >= (int)RUN_MASK) { | |
566 | *op++ = (RUN_MASK<<ML_BITS); | |
567 | lastRun -= RUN_MASK; | |
568 | for (; lastRun > 254 ; lastRun -= 255) | |
569 | *op++ = 255; | |
570 | *op++ = (BYTE) lastRun; | |
571 | } else | |
572 | *op++ = (BYTE)(lastRun<<ML_BITS); | |
b1a3e75e | 573 | LZ4_memcpy(op, anchor, iend - anchor); |
4e1a33b1 SS |
574 | op += iend - anchor; |
575 | } | |
576 | ||
c72ac7a1 CM |
577 | /* End */ |
578 | return (int) (((char *)op) - dest); | |
579 | } | |
580 | ||
4e1a33b1 SS |
581 | static int LZ4_compress_HC_extStateHC( |
582 | void *state, | |
583 | const char *src, | |
584 | char *dst, | |
585 | int srcSize, | |
586 | int maxDstSize, | |
587 | int compressionLevel) | |
c72ac7a1 | 588 | { |
4e1a33b1 | 589 | LZ4HC_CCtx_internal *ctx = &((LZ4_streamHC_t *)state)->internal_donotuse; |
c72ac7a1 | 590 | |
4e1a33b1 SS |
591 | if (((size_t)(state)&(sizeof(void *) - 1)) != 0) { |
592 | /* Error : state is not aligned | |
593 | * for pointers (32 or 64 bits) | |
594 | */ | |
595 | return 0; | |
596 | } | |
c72ac7a1 | 597 | |
4e1a33b1 | 598 | LZ4HC_init(ctx, (const BYTE *)src); |
c72ac7a1 | 599 | |
4e1a33b1 SS |
600 | if (maxDstSize < LZ4_compressBound(srcSize)) |
601 | return LZ4HC_compress_generic(ctx, src, dst, | |
602 | srcSize, maxDstSize, compressionLevel, limitedOutput); | |
603 | else | |
604 | return LZ4HC_compress_generic(ctx, src, dst, | |
605 | srcSize, maxDstSize, compressionLevel, noLimit); | |
606 | } | |
607 | ||
608 | int LZ4_compress_HC(const char *src, char *dst, int srcSize, | |
609 | int maxDstSize, int compressionLevel, void *wrkmem) | |
610 | { | |
611 | return LZ4_compress_HC_extStateHC(wrkmem, src, dst, | |
612 | srcSize, maxDstSize, compressionLevel); | |
613 | } | |
614 | EXPORT_SYMBOL(LZ4_compress_HC); | |
615 | ||
616 | /************************************** | |
617 | * Streaming Functions | |
618 | **************************************/ | |
619 | void LZ4_resetStreamHC(LZ4_streamHC_t *LZ4_streamHCPtr, int compressionLevel) | |
620 | { | |
621 | LZ4_streamHCPtr->internal_donotuse.base = NULL; | |
622 | LZ4_streamHCPtr->internal_donotuse.compressionLevel = (unsigned int)compressionLevel; | |
623 | } | |
624 | ||
625 | int LZ4_loadDictHC(LZ4_streamHC_t *LZ4_streamHCPtr, | |
626 | const char *dictionary, | |
627 | int dictSize) | |
628 | { | |
629 | LZ4HC_CCtx_internal *ctxPtr = &LZ4_streamHCPtr->internal_donotuse; | |
630 | ||
631 | if (dictSize > 64 * KB) { | |
632 | dictionary += dictSize - 64 * KB; | |
633 | dictSize = 64 * KB; | |
634 | } | |
635 | LZ4HC_init(ctxPtr, (const BYTE *)dictionary); | |
636 | if (dictSize >= 4) | |
637 | LZ4HC_Insert(ctxPtr, (const BYTE *)dictionary + (dictSize - 3)); | |
638 | ctxPtr->end = (const BYTE *)dictionary + dictSize; | |
639 | return dictSize; | |
640 | } | |
641 | EXPORT_SYMBOL(LZ4_loadDictHC); | |
642 | ||
643 | /* compression */ | |
644 | ||
645 | static void LZ4HC_setExternalDict( | |
646 | LZ4HC_CCtx_internal *ctxPtr, | |
647 | const BYTE *newBlock) | |
648 | { | |
649 | if (ctxPtr->end >= ctxPtr->base + 4) { | |
650 | /* Referencing remaining dictionary content */ | |
651 | LZ4HC_Insert(ctxPtr, ctxPtr->end - 3); | |
652 | } | |
653 | ||
654 | /* | |
655 | * Only one memory segment for extDict, | |
656 | * so any previous extDict is lost at this stage | |
657 | */ | |
658 | ctxPtr->lowLimit = ctxPtr->dictLimit; | |
659 | ctxPtr->dictLimit = (U32)(ctxPtr->end - ctxPtr->base); | |
660 | ctxPtr->dictBase = ctxPtr->base; | |
661 | ctxPtr->base = newBlock - ctxPtr->dictLimit; | |
662 | ctxPtr->end = newBlock; | |
663 | /* match referencing will resume from there */ | |
664 | ctxPtr->nextToUpdate = ctxPtr->dictLimit; | |
665 | } | |
4e1a33b1 SS |
666 | |
667 | static int LZ4_compressHC_continue_generic( | |
668 | LZ4_streamHC_t *LZ4_streamHCPtr, | |
669 | const char *source, | |
670 | char *dest, | |
671 | int inputSize, | |
672 | int maxOutputSize, | |
673 | limitedOutput_directive limit) | |
674 | { | |
675 | LZ4HC_CCtx_internal *ctxPtr = &LZ4_streamHCPtr->internal_donotuse; | |
676 | ||
677 | /* auto - init if forgotten */ | |
678 | if (ctxPtr->base == NULL) | |
679 | LZ4HC_init(ctxPtr, (const BYTE *) source); | |
680 | ||
681 | /* Check overflow */ | |
682 | if ((size_t)(ctxPtr->end - ctxPtr->base) > 2 * GB) { | |
683 | size_t dictSize = (size_t)(ctxPtr->end - ctxPtr->base) | |
684 | - ctxPtr->dictLimit; | |
685 | if (dictSize > 64 * KB) | |
686 | dictSize = 64 * KB; | |
687 | LZ4_loadDictHC(LZ4_streamHCPtr, | |
688 | (const char *)(ctxPtr->end) - dictSize, (int)dictSize); | |
689 | } | |
690 | ||
691 | /* Check if blocks follow each other */ | |
692 | if ((const BYTE *)source != ctxPtr->end) | |
693 | LZ4HC_setExternalDict(ctxPtr, (const BYTE *)source); | |
694 | ||
695 | /* Check overlapping input/dictionary space */ | |
696 | { | |
697 | const BYTE *sourceEnd = (const BYTE *) source + inputSize; | |
698 | const BYTE * const dictBegin = ctxPtr->dictBase + ctxPtr->lowLimit; | |
699 | const BYTE * const dictEnd = ctxPtr->dictBase + ctxPtr->dictLimit; | |
700 | ||
701 | if ((sourceEnd > dictBegin) | |
702 | && ((const BYTE *)source < dictEnd)) { | |
703 | if (sourceEnd > dictEnd) | |
704 | sourceEnd = dictEnd; | |
705 | ctxPtr->lowLimit = (U32)(sourceEnd - ctxPtr->dictBase); | |
706 | ||
707 | if (ctxPtr->dictLimit - ctxPtr->lowLimit < 4) | |
708 | ctxPtr->lowLimit = ctxPtr->dictLimit; | |
709 | } | |
710 | } | |
711 | ||
712 | return LZ4HC_compress_generic(ctxPtr, source, dest, | |
713 | inputSize, maxOutputSize, ctxPtr->compressionLevel, limit); | |
714 | } | |
715 | ||
716 | int LZ4_compress_HC_continue( | |
717 | LZ4_streamHC_t *LZ4_streamHCPtr, | |
718 | const char *source, | |
719 | char *dest, | |
720 | int inputSize, | |
721 | int maxOutputSize) | |
722 | { | |
723 | if (maxOutputSize < LZ4_compressBound(inputSize)) | |
724 | return LZ4_compressHC_continue_generic(LZ4_streamHCPtr, | |
725 | source, dest, inputSize, maxOutputSize, limitedOutput); | |
726 | else | |
727 | return LZ4_compressHC_continue_generic(LZ4_streamHCPtr, | |
728 | source, dest, inputSize, maxOutputSize, noLimit); | |
729 | } | |
730 | EXPORT_SYMBOL(LZ4_compress_HC_continue); | |
731 | ||
732 | /* dictionary saving */ | |
733 | ||
734 | int LZ4_saveDictHC( | |
735 | LZ4_streamHC_t *LZ4_streamHCPtr, | |
736 | char *safeBuffer, | |
737 | int dictSize) | |
738 | { | |
739 | LZ4HC_CCtx_internal *const streamPtr = &LZ4_streamHCPtr->internal_donotuse; | |
740 | int const prefixSize = (int)(streamPtr->end | |
741 | - (streamPtr->base + streamPtr->dictLimit)); | |
742 | ||
743 | if (dictSize > 64 * KB) | |
744 | dictSize = 64 * KB; | |
745 | if (dictSize < 4) | |
746 | dictSize = 0; | |
747 | if (dictSize > prefixSize) | |
748 | dictSize = prefixSize; | |
749 | ||
750 | memmove(safeBuffer, streamPtr->end - dictSize, dictSize); | |
c72ac7a1 | 751 | |
4e1a33b1 SS |
752 | { |
753 | U32 const endIndex = (U32)(streamPtr->end - streamPtr->base); | |
754 | ||
755 | streamPtr->end = (const BYTE *)safeBuffer + dictSize; | |
756 | streamPtr->base = streamPtr->end - endIndex; | |
757 | streamPtr->dictLimit = endIndex - dictSize; | |
758 | streamPtr->lowLimit = endIndex - dictSize; | |
759 | ||
760 | if (streamPtr->nextToUpdate < streamPtr->dictLimit) | |
761 | streamPtr->nextToUpdate = streamPtr->dictLimit; | |
762 | } | |
763 | return dictSize; | |
764 | } | |
765 | EXPORT_SYMBOL(LZ4_saveDictHC); | |
766 | ||
ee8a99bd | 767 | MODULE_LICENSE("Dual BSD/GPL"); |
4e1a33b1 | 768 | MODULE_DESCRIPTION("LZ4 HC compressor"); |