Commit | Line | Data |
---|---|---|
c72ac7a1 CM |
1 | /* |
2 | * LZ4 - Fast LZ compression algorithm | |
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 | /* | |
44 | * LZ4_compressCtx : | |
45 | * ----------------- | |
46 | * Compress 'isize' bytes from 'source' into an output buffer 'dest' of | |
47 | * maximum size 'maxOutputSize'. * If it cannot achieve it, compression | |
48 | * will stop, and result of the function will be zero. | |
49 | * return : the number of bytes written in buffer 'dest', or 0 if the | |
50 | * compression fails | |
51 | */ | |
52 | static inline int lz4_compressctx(void *ctx, | |
53 | const char *source, | |
54 | char *dest, | |
55 | int isize, | |
56 | int maxoutputsize) | |
57 | { | |
58 | HTYPE *hashtable = (HTYPE *)ctx; | |
59 | const u8 *ip = (u8 *)source; | |
60 | #if LZ4_ARCH64 | |
61 | const BYTE * const base = ip; | |
62 | #else | |
63 | const int base = 0; | |
64 | #endif | |
65 | const u8 *anchor = ip; | |
66 | const u8 *const iend = ip + isize; | |
67 | const u8 *const mflimit = iend - MFLIMIT; | |
68 | #define MATCHLIMIT (iend - LASTLITERALS) | |
69 | ||
70 | u8 *op = (u8 *) dest; | |
71 | u8 *const oend = op + maxoutputsize; | |
72 | int length; | |
73 | const int skipstrength = SKIPSTRENGTH; | |
74 | u32 forwardh; | |
75 | int lastrun; | |
76 | ||
77 | /* Init */ | |
78 | if (isize < MINLENGTH) | |
79 | goto _last_literals; | |
80 | ||
81 | memset((void *)hashtable, 0, LZ4_MEM_COMPRESS); | |
82 | ||
83 | /* First Byte */ | |
84 | hashtable[LZ4_HASH_VALUE(ip)] = ip - base; | |
85 | ip++; | |
86 | forwardh = LZ4_HASH_VALUE(ip); | |
87 | ||
88 | /* Main Loop */ | |
89 | for (;;) { | |
90 | int findmatchattempts = (1U << skipstrength) + 3; | |
91 | const u8 *forwardip = ip; | |
92 | const u8 *ref; | |
93 | u8 *token; | |
94 | ||
95 | /* Find a match */ | |
96 | do { | |
97 | u32 h = forwardh; | |
98 | int step = findmatchattempts++ >> skipstrength; | |
99 | ip = forwardip; | |
100 | forwardip = ip + step; | |
101 | ||
102 | if (unlikely(forwardip > mflimit)) | |
103 | goto _last_literals; | |
104 | ||
105 | forwardh = LZ4_HASH_VALUE(forwardip); | |
106 | ref = base + hashtable[h]; | |
107 | hashtable[h] = ip - base; | |
108 | } while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip))); | |
109 | ||
110 | /* Catch up */ | |
111 | while ((ip > anchor) && (ref > (u8 *)source) && | |
112 | unlikely(ip[-1] == ref[-1])) { | |
113 | ip--; | |
114 | ref--; | |
115 | } | |
116 | ||
117 | /* Encode Literal length */ | |
118 | length = (int)(ip - anchor); | |
119 | token = op++; | |
120 | /* check output limit */ | |
121 | if (unlikely(op + length + (2 + 1 + LASTLITERALS) + | |
122 | (length >> 8) > oend)) | |
123 | return 0; | |
124 | ||
125 | if (length >= (int)RUN_MASK) { | |
126 | int len; | |
127 | *token = (RUN_MASK << ML_BITS); | |
128 | len = length - RUN_MASK; | |
129 | for (; len > 254 ; len -= 255) | |
130 | *op++ = 255; | |
131 | *op++ = (u8)len; | |
132 | } else | |
133 | *token = (length << ML_BITS); | |
134 | ||
135 | /* Copy Literals */ | |
136 | LZ4_BLINDCOPY(anchor, op, length); | |
137 | _next_match: | |
138 | /* Encode Offset */ | |
139 | LZ4_WRITE_LITTLEENDIAN_16(op, (u16)(ip - ref)); | |
140 | ||
141 | /* Start Counting */ | |
142 | ip += MINMATCH; | |
143 | /* MinMatch verified */ | |
144 | ref += MINMATCH; | |
145 | anchor = ip; | |
146 | while (likely(ip < MATCHLIMIT - (STEPSIZE - 1))) { | |
147 | #if LZ4_ARCH64 | |
148 | u64 diff = A64(ref) ^ A64(ip); | |
149 | #else | |
150 | u32 diff = A32(ref) ^ A32(ip); | |
151 | #endif | |
152 | if (!diff) { | |
153 | ip += STEPSIZE; | |
154 | ref += STEPSIZE; | |
155 | continue; | |
156 | } | |
157 | ip += LZ4_NBCOMMONBYTES(diff); | |
158 | goto _endcount; | |
159 | } | |
160 | #if LZ4_ARCH64 | |
161 | if ((ip < (MATCHLIMIT - 3)) && (A32(ref) == A32(ip))) { | |
162 | ip += 4; | |
163 | ref += 4; | |
164 | } | |
165 | #endif | |
166 | if ((ip < (MATCHLIMIT - 1)) && (A16(ref) == A16(ip))) { | |
167 | ip += 2; | |
168 | ref += 2; | |
169 | } | |
170 | if ((ip < MATCHLIMIT) && (*ref == *ip)) | |
171 | ip++; | |
172 | _endcount: | |
173 | /* Encode MatchLength */ | |
174 | length = (int)(ip - anchor); | |
175 | /* Check output limit */ | |
176 | if (unlikely(op + (1 + LASTLITERALS) + (length >> 8) > oend)) | |
177 | return 0; | |
178 | if (length >= (int)ML_MASK) { | |
179 | *token += ML_MASK; | |
180 | length -= ML_MASK; | |
181 | for (; length > 509 ; length -= 510) { | |
182 | *op++ = 255; | |
183 | *op++ = 255; | |
184 | } | |
185 | if (length > 254) { | |
186 | length -= 255; | |
187 | *op++ = 255; | |
188 | } | |
189 | *op++ = (u8)length; | |
190 | } else | |
191 | *token += length; | |
192 | ||
193 | /* Test end of chunk */ | |
194 | if (ip > mflimit) { | |
195 | anchor = ip; | |
196 | break; | |
197 | } | |
198 | ||
199 | /* Fill table */ | |
200 | hashtable[LZ4_HASH_VALUE(ip-2)] = ip - 2 - base; | |
201 | ||
202 | /* Test next position */ | |
203 | ref = base + hashtable[LZ4_HASH_VALUE(ip)]; | |
204 | hashtable[LZ4_HASH_VALUE(ip)] = ip - base; | |
205 | if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) { | |
206 | token = op++; | |
207 | *token = 0; | |
208 | goto _next_match; | |
209 | } | |
210 | ||
211 | /* Prepare next loop */ | |
212 | anchor = ip++; | |
213 | forwardh = LZ4_HASH_VALUE(ip); | |
214 | } | |
215 | ||
216 | _last_literals: | |
217 | /* Encode Last Literals */ | |
218 | lastrun = (int)(iend - anchor); | |
219 | if (((char *)op - dest) + lastrun + 1 | |
220 | + ((lastrun + 255 - RUN_MASK) / 255) > (u32)maxoutputsize) | |
221 | return 0; | |
222 | ||
223 | if (lastrun >= (int)RUN_MASK) { | |
224 | *op++ = (RUN_MASK << ML_BITS); | |
225 | lastrun -= RUN_MASK; | |
226 | for (; lastrun > 254 ; lastrun -= 255) | |
227 | *op++ = 255; | |
228 | *op++ = (u8)lastrun; | |
229 | } else | |
230 | *op++ = (lastrun << ML_BITS); | |
231 | memcpy(op, anchor, iend - anchor); | |
232 | op += iend - anchor; | |
233 | ||
234 | /* End */ | |
235 | return (int)(((char *)op) - dest); | |
236 | } | |
237 | ||
238 | static inline int lz4_compress64kctx(void *ctx, | |
239 | const char *source, | |
240 | char *dest, | |
241 | int isize, | |
242 | int maxoutputsize) | |
243 | { | |
244 | u16 *hashtable = (u16 *)ctx; | |
245 | const u8 *ip = (u8 *) source; | |
246 | const u8 *anchor = ip; | |
247 | const u8 *const base = ip; | |
248 | const u8 *const iend = ip + isize; | |
249 | const u8 *const mflimit = iend - MFLIMIT; | |
250 | #define MATCHLIMIT (iend - LASTLITERALS) | |
251 | ||
252 | u8 *op = (u8 *) dest; | |
253 | u8 *const oend = op + maxoutputsize; | |
254 | int len, length; | |
255 | const int skipstrength = SKIPSTRENGTH; | |
256 | u32 forwardh; | |
257 | int lastrun; | |
258 | ||
259 | /* Init */ | |
260 | if (isize < MINLENGTH) | |
261 | goto _last_literals; | |
262 | ||
263 | memset((void *)hashtable, 0, LZ4_MEM_COMPRESS); | |
264 | ||
265 | /* First Byte */ | |
266 | ip++; | |
267 | forwardh = LZ4_HASH64K_VALUE(ip); | |
268 | ||
269 | /* Main Loop */ | |
270 | for (;;) { | |
271 | int findmatchattempts = (1U << skipstrength) + 3; | |
272 | const u8 *forwardip = ip; | |
273 | const u8 *ref; | |
274 | u8 *token; | |
275 | ||
276 | /* Find a match */ | |
277 | do { | |
278 | u32 h = forwardh; | |
279 | int step = findmatchattempts++ >> skipstrength; | |
280 | ip = forwardip; | |
281 | forwardip = ip + step; | |
282 | ||
283 | if (forwardip > mflimit) | |
284 | goto _last_literals; | |
285 | ||
286 | forwardh = LZ4_HASH64K_VALUE(forwardip); | |
287 | ref = base + hashtable[h]; | |
288 | hashtable[h] = (u16)(ip - base); | |
289 | } while (A32(ref) != A32(ip)); | |
290 | ||
291 | /* Catch up */ | |
292 | while ((ip > anchor) && (ref > (u8 *)source) | |
293 | && (ip[-1] == ref[-1])) { | |
294 | ip--; | |
295 | ref--; | |
296 | } | |
297 | ||
298 | /* Encode Literal length */ | |
299 | length = (int)(ip - anchor); | |
300 | token = op++; | |
301 | /* Check output limit */ | |
302 | if (unlikely(op + length + (2 + 1 + LASTLITERALS) | |
303 | + (length >> 8) > oend)) | |
304 | return 0; | |
305 | if (length >= (int)RUN_MASK) { | |
306 | *token = (RUN_MASK << ML_BITS); | |
307 | len = length - RUN_MASK; | |
308 | for (; len > 254 ; len -= 255) | |
309 | *op++ = 255; | |
310 | *op++ = (u8)len; | |
311 | } else | |
312 | *token = (length << ML_BITS); | |
313 | ||
314 | /* Copy Literals */ | |
315 | LZ4_BLINDCOPY(anchor, op, length); | |
316 | ||
317 | _next_match: | |
318 | /* Encode Offset */ | |
319 | LZ4_WRITE_LITTLEENDIAN_16(op, (u16)(ip - ref)); | |
320 | ||
321 | /* Start Counting */ | |
322 | ip += MINMATCH; | |
323 | /* MinMatch verified */ | |
324 | ref += MINMATCH; | |
325 | anchor = ip; | |
326 | ||
327 | while (ip < MATCHLIMIT - (STEPSIZE - 1)) { | |
328 | #if LZ4_ARCH64 | |
329 | u64 diff = A64(ref) ^ A64(ip); | |
330 | #else | |
331 | u32 diff = A32(ref) ^ A32(ip); | |
332 | #endif | |
333 | ||
334 | if (!diff) { | |
335 | ip += STEPSIZE; | |
336 | ref += STEPSIZE; | |
337 | continue; | |
338 | } | |
339 | ip += LZ4_NBCOMMONBYTES(diff); | |
340 | goto _endcount; | |
341 | } | |
342 | #if LZ4_ARCH64 | |
343 | if ((ip < (MATCHLIMIT - 3)) && (A32(ref) == A32(ip))) { | |
344 | ip += 4; | |
345 | ref += 4; | |
346 | } | |
347 | #endif | |
348 | if ((ip < (MATCHLIMIT - 1)) && (A16(ref) == A16(ip))) { | |
349 | ip += 2; | |
350 | ref += 2; | |
351 | } | |
352 | if ((ip < MATCHLIMIT) && (*ref == *ip)) | |
353 | ip++; | |
354 | _endcount: | |
355 | ||
356 | /* Encode MatchLength */ | |
357 | len = (int)(ip - anchor); | |
358 | /* Check output limit */ | |
359 | if (unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend)) | |
360 | return 0; | |
361 | if (len >= (int)ML_MASK) { | |
362 | *token += ML_MASK; | |
363 | len -= ML_MASK; | |
364 | for (; len > 509 ; len -= 510) { | |
365 | *op++ = 255; | |
366 | *op++ = 255; | |
367 | } | |
368 | if (len > 254) { | |
369 | len -= 255; | |
370 | *op++ = 255; | |
371 | } | |
372 | *op++ = (u8)len; | |
373 | } else | |
374 | *token += len; | |
375 | ||
376 | /* Test end of chunk */ | |
377 | if (ip > mflimit) { | |
378 | anchor = ip; | |
379 | break; | |
380 | } | |
381 | ||
382 | /* Fill table */ | |
383 | hashtable[LZ4_HASH64K_VALUE(ip-2)] = (u16)(ip - 2 - base); | |
384 | ||
385 | /* Test next position */ | |
386 | ref = base + hashtable[LZ4_HASH64K_VALUE(ip)]; | |
387 | hashtable[LZ4_HASH64K_VALUE(ip)] = (u16)(ip - base); | |
388 | if (A32(ref) == A32(ip)) { | |
389 | token = op++; | |
390 | *token = 0; | |
391 | goto _next_match; | |
392 | } | |
393 | ||
394 | /* Prepare next loop */ | |
395 | anchor = ip++; | |
396 | forwardh = LZ4_HASH64K_VALUE(ip); | |
397 | } | |
398 | ||
399 | _last_literals: | |
400 | /* Encode Last Literals */ | |
401 | lastrun = (int)(iend - anchor); | |
402 | if (op + lastrun + 1 + (lastrun - RUN_MASK + 255) / 255 > oend) | |
403 | return 0; | |
404 | if (lastrun >= (int)RUN_MASK) { | |
405 | *op++ = (RUN_MASK << ML_BITS); | |
406 | lastrun -= RUN_MASK; | |
407 | for (; lastrun > 254 ; lastrun -= 255) | |
408 | *op++ = 255; | |
409 | *op++ = (u8)lastrun; | |
410 | } else | |
411 | *op++ = (lastrun << ML_BITS); | |
412 | memcpy(op, anchor, iend - anchor); | |
413 | op += iend - anchor; | |
414 | /* End */ | |
415 | return (int)(((char *)op) - dest); | |
416 | } | |
417 | ||
418 | int lz4_compress(const unsigned char *src, size_t src_len, | |
419 | unsigned char *dst, size_t *dst_len, void *wrkmem) | |
420 | { | |
421 | int ret = -1; | |
422 | int out_len = 0; | |
423 | ||
424 | if (src_len < LZ4_64KLIMIT) | |
425 | out_len = lz4_compress64kctx(wrkmem, src, dst, src_len, | |
426 | lz4_compressbound(src_len)); | |
427 | else | |
428 | out_len = lz4_compressctx(wrkmem, src, dst, src_len, | |
429 | lz4_compressbound(src_len)); | |
430 | ||
431 | if (out_len < 0) | |
432 | goto exit; | |
433 | ||
434 | *dst_len = out_len; | |
435 | ||
436 | return 0; | |
437 | exit: | |
438 | return ret; | |
439 | } | |
ee8a99bd | 440 | EXPORT_SYMBOL(lz4_compress); |
c72ac7a1 | 441 | |
ee8a99bd | 442 | MODULE_LICENSE("Dual BSD/GPL"); |
c72ac7a1 | 443 | MODULE_DESCRIPTION("LZ4 compressor"); |