blob: fd94058bd7f9496fe69699b85177e1c18e4af2e7 [file] [log] [blame]
Chanho Minc72ac7a2013-07-08 16:01:49 -07001/*
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 */
52static 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
238static 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
418int 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;
437exit:
438 return ret;
439}
440EXPORT_SYMBOL_GPL(lz4_compress);
441
442MODULE_LICENSE("GPL");
443MODULE_DESCRIPTION("LZ4 compressor");