Commit | Line | Data |
---|---|---|
c72ac7a1 CM |
1 | /* |
2 | * LZ4 HC - High Compression Mode of LZ4 | |
3 | * Copyright (C) 2011-2012, Yann Collet. | |
4 | * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) | |
5 | * | |
6 | * Redistribution and use in source and binary forms, with or without | |
7 | * modification, are permitted provided that the following conditions are | |
8 | * met: | |
9 | * | |
10 | * * Redistributions of source code must retain the above copyright | |
11 | * notice, this list of conditions and the following disclaimer. | |
12 | * * Redistributions in binary form must reproduce the above | |
13 | * copyright notice, this list of conditions and the following disclaimer | |
14 | * in the documentation and/or other materials provided with the | |
15 | * distribution. | |
16 | * | |
17 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
18 | * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
19 | * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
20 | * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
21 | * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
22 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
23 | * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
24 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
25 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
26 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
27 | * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
28 | * | |
29 | * You can contact the author at : | |
30 | * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html | |
31 | * - LZ4 source repository : http://code.google.com/p/lz4/ | |
32 | * | |
33 | * Changed for kernel use by: | |
34 | * Chanho Min <chanho.min@lge.com> | |
35 | */ | |
36 | ||
37 | #include <linux/module.h> | |
38 | #include <linux/kernel.h> | |
39 | #include <linux/lz4.h> | |
40 | #include <asm/unaligned.h> | |
41 | #include "lz4defs.h" | |
42 | ||
43 | struct lz4hc_data { | |
44 | const u8 *base; | |
45 | HTYPE hashtable[HASHTABLESIZE]; | |
46 | u16 chaintable[MAXD]; | |
47 | const u8 *nexttoupdate; | |
48 | } __attribute__((__packed__)); | |
49 | ||
50 | static inline int lz4hc_init(struct lz4hc_data *hc4, const u8 *base) | |
51 | { | |
52 | memset((void *)hc4->hashtable, 0, sizeof(hc4->hashtable)); | |
53 | memset(hc4->chaintable, 0xFF, sizeof(hc4->chaintable)); | |
54 | ||
55 | #if LZ4_ARCH64 | |
56 | hc4->nexttoupdate = base + 1; | |
57 | #else | |
58 | hc4->nexttoupdate = base; | |
59 | #endif | |
60 | hc4->base = base; | |
61 | return 1; | |
62 | } | |
63 | ||
64 | /* Update chains up to ip (excluded) */ | |
65 | static inline void lz4hc_insert(struct lz4hc_data *hc4, const u8 *ip) | |
66 | { | |
67 | u16 *chaintable = hc4->chaintable; | |
68 | HTYPE *hashtable = hc4->hashtable; | |
69 | #if LZ4_ARCH64 | |
70 | const BYTE * const base = hc4->base; | |
71 | #else | |
72 | const int base = 0; | |
73 | #endif | |
74 | ||
75 | while (hc4->nexttoupdate < ip) { | |
76 | const u8 *p = hc4->nexttoupdate; | |
77 | size_t delta = p - (hashtable[HASH_VALUE(p)] + base); | |
78 | if (delta > MAX_DISTANCE) | |
79 | delta = MAX_DISTANCE; | |
80 | chaintable[(size_t)(p) & MAXD_MASK] = (u16)delta; | |
81 | hashtable[HASH_VALUE(p)] = (p) - base; | |
82 | hc4->nexttoupdate++; | |
83 | } | |
84 | } | |
85 | ||
86 | static inline size_t lz4hc_commonlength(const u8 *p1, const u8 *p2, | |
87 | const u8 *const matchlimit) | |
88 | { | |
89 | const u8 *p1t = p1; | |
90 | ||
91 | while (p1t < matchlimit - (STEPSIZE - 1)) { | |
92 | #if LZ4_ARCH64 | |
93 | u64 diff = A64(p2) ^ A64(p1t); | |
94 | #else | |
95 | u32 diff = A32(p2) ^ A32(p1t); | |
96 | #endif | |
97 | if (!diff) { | |
98 | p1t += STEPSIZE; | |
99 | p2 += STEPSIZE; | |
100 | continue; | |
101 | } | |
102 | p1t += LZ4_NBCOMMONBYTES(diff); | |
103 | return p1t - p1; | |
104 | } | |
105 | #if LZ4_ARCH64 | |
106 | if ((p1t < (matchlimit-3)) && (A32(p2) == A32(p1t))) { | |
107 | p1t += 4; | |
108 | p2 += 4; | |
109 | } | |
110 | #endif | |
111 | ||
112 | if ((p1t < (matchlimit - 1)) && (A16(p2) == A16(p1t))) { | |
113 | p1t += 2; | |
114 | p2 += 2; | |
115 | } | |
116 | if ((p1t < matchlimit) && (*p2 == *p1t)) | |
117 | p1t++; | |
118 | return p1t - p1; | |
119 | } | |
120 | ||
121 | static inline int lz4hc_insertandfindbestmatch(struct lz4hc_data *hc4, | |
122 | const u8 *ip, const u8 *const matchlimit, const u8 **matchpos) | |
123 | { | |
124 | u16 *const chaintable = hc4->chaintable; | |
125 | HTYPE *const hashtable = hc4->hashtable; | |
126 | const u8 *ref; | |
127 | #if LZ4_ARCH64 | |
128 | const BYTE * const base = hc4->base; | |
129 | #else | |
130 | const int base = 0; | |
131 | #endif | |
132 | int nbattempts = MAX_NB_ATTEMPTS; | |
133 | size_t repl = 0, ml = 0; | |
134 | u16 delta; | |
135 | ||
136 | /* HC4 match finder */ | |
137 | lz4hc_insert(hc4, ip); | |
138 | ref = hashtable[HASH_VALUE(ip)] + base; | |
139 | ||
140 | /* potential repetition */ | |
141 | if (ref >= ip-4) { | |
142 | /* confirmed */ | |
143 | if (A32(ref) == A32(ip)) { | |
144 | delta = (u16)(ip-ref); | |
145 | repl = ml = lz4hc_commonlength(ip + MINMATCH, | |
146 | ref + MINMATCH, matchlimit) + MINMATCH; | |
147 | *matchpos = ref; | |
148 | } | |
149 | ref -= (size_t)chaintable[(size_t)(ref) & MAXD_MASK]; | |
150 | } | |
151 | ||
152 | while ((ref >= ip - MAX_DISTANCE) && nbattempts) { | |
153 | nbattempts--; | |
154 | if (*(ref + ml) == *(ip + ml)) { | |
155 | if (A32(ref) == A32(ip)) { | |
156 | size_t mlt = | |
157 | lz4hc_commonlength(ip + MINMATCH, | |
158 | ref + MINMATCH, matchlimit) + MINMATCH; | |
159 | if (mlt > ml) { | |
160 | ml = mlt; | |
161 | *matchpos = ref; | |
162 | } | |
163 | } | |
164 | } | |
165 | ref -= (size_t)chaintable[(size_t)(ref) & MAXD_MASK]; | |
166 | } | |
167 | ||
168 | /* Complete table */ | |
169 | if (repl) { | |
170 | const BYTE *ptr = ip; | |
171 | const BYTE *end; | |
172 | end = ip + repl - (MINMATCH-1); | |
173 | /* Pre-Load */ | |
174 | while (ptr < end - delta) { | |
175 | chaintable[(size_t)(ptr) & MAXD_MASK] = delta; | |
176 | ptr++; | |
177 | } | |
178 | do { | |
179 | chaintable[(size_t)(ptr) & MAXD_MASK] = delta; | |
180 | /* Head of chain */ | |
181 | hashtable[HASH_VALUE(ptr)] = (ptr) - base; | |
182 | ptr++; | |
183 | } while (ptr < end); | |
184 | hc4->nexttoupdate = end; | |
185 | } | |
186 | ||
187 | return (int)ml; | |
188 | } | |
189 | ||
190 | static inline int lz4hc_insertandgetwidermatch(struct lz4hc_data *hc4, | |
191 | const u8 *ip, const u8 *startlimit, const u8 *matchlimit, int longest, | |
192 | const u8 **matchpos, const u8 **startpos) | |
193 | { | |
194 | u16 *const chaintable = hc4->chaintable; | |
195 | HTYPE *const hashtable = hc4->hashtable; | |
196 | #if LZ4_ARCH64 | |
197 | const BYTE * const base = hc4->base; | |
198 | #else | |
199 | const int base = 0; | |
200 | #endif | |
201 | const u8 *ref; | |
202 | int nbattempts = MAX_NB_ATTEMPTS; | |
203 | int delta = (int)(ip - startlimit); | |
204 | ||
205 | /* First Match */ | |
206 | lz4hc_insert(hc4, ip); | |
207 | ref = hashtable[HASH_VALUE(ip)] + base; | |
208 | ||
209 | while ((ref >= ip - MAX_DISTANCE) && (ref >= hc4->base) | |
210 | && (nbattempts)) { | |
211 | nbattempts--; | |
212 | if (*(startlimit + longest) == *(ref - delta + longest)) { | |
213 | if (A32(ref) == A32(ip)) { | |
214 | const u8 *reft = ref + MINMATCH; | |
215 | const u8 *ipt = ip + MINMATCH; | |
216 | const u8 *startt = ip; | |
217 | ||
218 | while (ipt < matchlimit-(STEPSIZE - 1)) { | |
219 | #if LZ4_ARCH64 | |
220 | u64 diff = A64(reft) ^ A64(ipt); | |
221 | #else | |
222 | u32 diff = A32(reft) ^ A32(ipt); | |
223 | #endif | |
224 | ||
225 | if (!diff) { | |
226 | ipt += STEPSIZE; | |
227 | reft += STEPSIZE; | |
228 | continue; | |
229 | } | |
230 | ipt += LZ4_NBCOMMONBYTES(diff); | |
231 | goto _endcount; | |
232 | } | |
233 | #if LZ4_ARCH64 | |
234 | if ((ipt < (matchlimit - 3)) | |
235 | && (A32(reft) == A32(ipt))) { | |
236 | ipt += 4; | |
237 | reft += 4; | |
238 | } | |
239 | ipt += 2; | |
240 | #endif | |
241 | if ((ipt < (matchlimit - 1)) | |
242 | && (A16(reft) == A16(ipt))) { | |
243 | reft += 2; | |
244 | } | |
245 | if ((ipt < matchlimit) && (*reft == *ipt)) | |
246 | ipt++; | |
247 | _endcount: | |
248 | reft = ref; | |
249 | ||
250 | while ((startt > startlimit) | |
251 | && (reft > hc4->base) | |
252 | && (startt[-1] == reft[-1])) { | |
253 | startt--; | |
254 | reft--; | |
255 | } | |
256 | ||
257 | if ((ipt - startt) > longest) { | |
258 | longest = (int)(ipt - startt); | |
259 | *matchpos = reft; | |
260 | *startpos = startt; | |
261 | } | |
262 | } | |
263 | } | |
264 | ref -= (size_t)chaintable[(size_t)(ref) & MAXD_MASK]; | |
265 | } | |
266 | return longest; | |
267 | } | |
268 | ||
269 | static inline int lz4_encodesequence(const u8 **ip, u8 **op, const u8 **anchor, | |
270 | int ml, const u8 *ref) | |
271 | { | |
272 | int length, len; | |
273 | u8 *token; | |
274 | ||
275 | /* Encode Literal length */ | |
276 | length = (int)(*ip - *anchor); | |
277 | token = (*op)++; | |
278 | if (length >= (int)RUN_MASK) { | |
279 | *token = (RUN_MASK << ML_BITS); | |
280 | len = length - RUN_MASK; | |
281 | for (; len > 254 ; len -= 255) | |
282 | *(*op)++ = 255; | |
283 | *(*op)++ = (u8)len; | |
284 | } else | |
285 | *token = (length << ML_BITS); | |
286 | ||
287 | /* Copy Literals */ | |
288 | LZ4_BLINDCOPY(*anchor, *op, length); | |
289 | ||
290 | /* Encode Offset */ | |
291 | LZ4_WRITE_LITTLEENDIAN_16(*op, (u16)(*ip - ref)); | |
292 | ||
293 | /* Encode MatchLength */ | |
294 | len = (int)(ml - MINMATCH); | |
295 | if (len >= (int)ML_MASK) { | |
296 | *token += ML_MASK; | |
297 | len -= ML_MASK; | |
298 | for (; len > 509 ; len -= 510) { | |
299 | *(*op)++ = 255; | |
300 | *(*op)++ = 255; | |
301 | } | |
302 | if (len > 254) { | |
303 | len -= 255; | |
304 | *(*op)++ = 255; | |
305 | } | |
306 | *(*op)++ = (u8)len; | |
307 | } else | |
308 | *token += len; | |
309 | ||
310 | /* Prepare next loop */ | |
311 | *ip += ml; | |
312 | *anchor = *ip; | |
313 | ||
314 | return 0; | |
315 | } | |
316 | ||
317 | static int lz4_compresshcctx(struct lz4hc_data *ctx, | |
318 | const char *source, | |
319 | char *dest, | |
320 | int isize) | |
321 | { | |
322 | const u8 *ip = (const u8 *)source; | |
323 | const u8 *anchor = ip; | |
324 | const u8 *const iend = ip + isize; | |
325 | const u8 *const mflimit = iend - MFLIMIT; | |
326 | const u8 *const matchlimit = (iend - LASTLITERALS); | |
327 | ||
328 | u8 *op = (u8 *)dest; | |
329 | ||
330 | int ml, ml2, ml3, ml0; | |
331 | const u8 *ref = NULL; | |
332 | const u8 *start2 = NULL; | |
333 | const u8 *ref2 = NULL; | |
334 | const u8 *start3 = NULL; | |
335 | const u8 *ref3 = NULL; | |
336 | const u8 *start0; | |
337 | const u8 *ref0; | |
338 | int lastrun; | |
339 | ||
340 | ip++; | |
341 | ||
342 | /* Main Loop */ | |
343 | while (ip < mflimit) { | |
344 | ml = lz4hc_insertandfindbestmatch(ctx, ip, matchlimit, (&ref)); | |
345 | if (!ml) { | |
346 | ip++; | |
347 | continue; | |
348 | } | |
349 | ||
350 | /* saved, in case we would skip too much */ | |
351 | start0 = ip; | |
352 | ref0 = ref; | |
353 | ml0 = ml; | |
354 | _search2: | |
355 | if (ip+ml < mflimit) | |
356 | ml2 = lz4hc_insertandgetwidermatch(ctx, ip + ml - 2, | |
357 | ip + 1, matchlimit, ml, &ref2, &start2); | |
358 | else | |
359 | ml2 = ml; | |
360 | /* No better match */ | |
361 | if (ml2 == ml) { | |
362 | lz4_encodesequence(&ip, &op, &anchor, ml, ref); | |
363 | continue; | |
364 | } | |
365 | ||
366 | if (start0 < ip) { | |
367 | /* empirical */ | |
368 | if (start2 < ip + ml0) { | |
369 | ip = start0; | |
370 | ref = ref0; | |
371 | ml = ml0; | |
372 | } | |
373 | } | |
374 | /* | |
375 | * Here, start0==ip | |
376 | * First Match too small : removed | |
377 | */ | |
378 | if ((start2 - ip) < 3) { | |
379 | ml = ml2; | |
380 | ip = start2; | |
381 | ref = ref2; | |
382 | goto _search2; | |
383 | } | |
384 | ||
385 | _search3: | |
386 | /* | |
387 | * Currently we have : | |
388 | * ml2 > ml1, and | |
389 | * ip1+3 <= ip2 (usually < ip1+ml1) | |
390 | */ | |
391 | if ((start2 - ip) < OPTIMAL_ML) { | |
392 | int correction; | |
393 | int new_ml = ml; | |
394 | if (new_ml > OPTIMAL_ML) | |
395 | new_ml = OPTIMAL_ML; | |
396 | if (ip + new_ml > start2 + ml2 - MINMATCH) | |
397 | new_ml = (int)(start2 - ip) + ml2 - MINMATCH; | |
398 | correction = new_ml - (int)(start2 - ip); | |
399 | if (correction > 0) { | |
400 | start2 += correction; | |
401 | ref2 += correction; | |
402 | ml2 -= correction; | |
403 | } | |
404 | } | |
405 | /* | |
406 | * Now, we have start2 = ip+new_ml, | |
407 | * with new_ml=min(ml, OPTIMAL_ML=18) | |
408 | */ | |
409 | if (start2 + ml2 < mflimit) | |
410 | ml3 = lz4hc_insertandgetwidermatch(ctx, | |
411 | start2 + ml2 - 3, start2, matchlimit, | |
412 | ml2, &ref3, &start3); | |
413 | else | |
414 | ml3 = ml2; | |
415 | ||
416 | /* No better match : 2 sequences to encode */ | |
417 | if (ml3 == ml2) { | |
418 | /* ip & ref are known; Now for ml */ | |
419 | if (start2 < ip+ml) | |
420 | ml = (int)(start2 - ip); | |
421 | ||
422 | /* Now, encode 2 sequences */ | |
423 | lz4_encodesequence(&ip, &op, &anchor, ml, ref); | |
424 | ip = start2; | |
425 | lz4_encodesequence(&ip, &op, &anchor, ml2, ref2); | |
426 | continue; | |
427 | } | |
428 | ||
429 | /* Not enough space for match 2 : remove it */ | |
430 | if (start3 < ip + ml + 3) { | |
431 | /* | |
432 | * can write Seq1 immediately ==> Seq2 is removed, | |
433 | * so Seq3 becomes Seq1 | |
434 | */ | |
435 | if (start3 >= (ip + ml)) { | |
436 | if (start2 < ip + ml) { | |
437 | int correction = | |
438 | (int)(ip + ml - start2); | |
439 | start2 += correction; | |
440 | ref2 += correction; | |
441 | ml2 -= correction; | |
442 | if (ml2 < MINMATCH) { | |
443 | start2 = start3; | |
444 | ref2 = ref3; | |
445 | ml2 = ml3; | |
446 | } | |
447 | } | |
448 | ||
449 | lz4_encodesequence(&ip, &op, &anchor, ml, ref); | |
450 | ip = start3; | |
451 | ref = ref3; | |
452 | ml = ml3; | |
453 | ||
454 | start0 = start2; | |
455 | ref0 = ref2; | |
456 | ml0 = ml2; | |
457 | goto _search2; | |
458 | } | |
459 | ||
460 | start2 = start3; | |
461 | ref2 = ref3; | |
462 | ml2 = ml3; | |
463 | goto _search3; | |
464 | } | |
465 | ||
466 | /* | |
467 | * OK, now we have 3 ascending matches; let's write at least | |
468 | * the first one ip & ref are known; Now for ml | |
469 | */ | |
470 | if (start2 < ip + ml) { | |
471 | if ((start2 - ip) < (int)ML_MASK) { | |
472 | int correction; | |
473 | if (ml > OPTIMAL_ML) | |
474 | ml = OPTIMAL_ML; | |
475 | if (ip + ml > start2 + ml2 - MINMATCH) | |
476 | ml = (int)(start2 - ip) + ml2 | |
477 | - MINMATCH; | |
478 | correction = ml - (int)(start2 - ip); | |
479 | if (correction > 0) { | |
480 | start2 += correction; | |
481 | ref2 += correction; | |
482 | ml2 -= correction; | |
483 | } | |
484 | } else | |
485 | ml = (int)(start2 - ip); | |
486 | } | |
487 | lz4_encodesequence(&ip, &op, &anchor, ml, ref); | |
488 | ||
489 | ip = start2; | |
490 | ref = ref2; | |
491 | ml = ml2; | |
492 | ||
493 | start2 = start3; | |
494 | ref2 = ref3; | |
495 | ml2 = ml3; | |
496 | ||
497 | goto _search3; | |
498 | } | |
499 | ||
500 | /* Encode Last Literals */ | |
501 | lastrun = (int)(iend - anchor); | |
502 | if (lastrun >= (int)RUN_MASK) { | |
503 | *op++ = (RUN_MASK << ML_BITS); | |
504 | lastrun -= RUN_MASK; | |
505 | for (; lastrun > 254 ; lastrun -= 255) | |
506 | *op++ = 255; | |
507 | *op++ = (u8) lastrun; | |
508 | } else | |
509 | *op++ = (lastrun << ML_BITS); | |
510 | memcpy(op, anchor, iend - anchor); | |
511 | op += iend - anchor; | |
512 | /* End */ | |
513 | return (int) (((char *)op) - dest); | |
514 | } | |
515 | ||
516 | int lz4hc_compress(const unsigned char *src, size_t src_len, | |
517 | unsigned char *dst, size_t *dst_len, void *wrkmem) | |
518 | { | |
519 | int ret = -1; | |
520 | int out_len = 0; | |
521 | ||
522 | struct lz4hc_data *hc4 = (struct lz4hc_data *)wrkmem; | |
523 | lz4hc_init(hc4, (const u8 *)src); | |
524 | out_len = lz4_compresshcctx((struct lz4hc_data *)hc4, (const u8 *)src, | |
525 | (char *)dst, (int)src_len); | |
526 | ||
527 | if (out_len < 0) | |
528 | goto exit; | |
529 | ||
530 | *dst_len = out_len; | |
531 | return 0; | |
532 | ||
533 | exit: | |
534 | return ret; | |
535 | } | |
ee8a99bd | 536 | EXPORT_SYMBOL(lz4hc_compress); |
c72ac7a1 | 537 | |
ee8a99bd | 538 | MODULE_LICENSE("Dual BSD/GPL"); |
c72ac7a1 | 539 | MODULE_DESCRIPTION("LZ4HC compressor"); |