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)
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are
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
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.
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/
33 * Changed for kernel use by:
34 * Chanho Min <chanho.min@lge.com>
37 #include <linux/module.h>
38 #include <linux/kernel.h>
39 #include <linux/lz4.h>
40 #include <asm/unaligned.h>
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
52 static inline int lz4_compressctx(void *ctx
,
58 HTYPE
*hashtable
= (HTYPE
*)ctx
;
59 const u8
*ip
= (u8
*)source
;
61 const BYTE
* const base
= ip
;
65 const u8
*anchor
= ip
;
66 const u8
*const iend
= ip
+ isize
;
67 const u8
*const mflimit
= iend
- MFLIMIT
;
68 #define MATCHLIMIT (iend - LASTLITERALS)
71 u8
*const oend
= op
+ maxoutputsize
;
73 const int skipstrength
= SKIPSTRENGTH
;
78 if (isize
< MINLENGTH
)
81 memset((void *)hashtable
, 0, LZ4_MEM_COMPRESS
);
84 hashtable
[LZ4_HASH_VALUE(ip
)] = ip
- base
;
86 forwardh
= LZ4_HASH_VALUE(ip
);
90 int findmatchattempts
= (1U << skipstrength
) + 3;
91 const u8
*forwardip
= ip
;
98 int step
= findmatchattempts
++ >> skipstrength
;
100 forwardip
= ip
+ step
;
102 if (unlikely(forwardip
> mflimit
))
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
)));
111 while ((ip
> anchor
) && (ref
> (u8
*)source
) &&
112 unlikely(ip
[-1] == ref
[-1])) {
117 /* Encode Literal length */
118 length
= (int)(ip
- anchor
);
120 /* check output limit */
121 if (unlikely(op
+ length
+ (2 + 1 + LASTLITERALS
) +
122 (length
>> 8) > oend
))
125 if (length
>= (int)RUN_MASK
) {
127 *token
= (RUN_MASK
<< ML_BITS
);
128 len
= length
- RUN_MASK
;
129 for (; len
> 254 ; len
-= 255)
133 *token
= (length
<< ML_BITS
);
136 LZ4_BLINDCOPY(anchor
, op
, length
);
139 LZ4_WRITE_LITTLEENDIAN_16(op
, (u16
)(ip
- ref
));
143 /* MinMatch verified */
146 while (likely(ip
< MATCHLIMIT
- (STEPSIZE
- 1))) {
148 u64 diff
= A64(ref
) ^ A64(ip
);
150 u32 diff
= A32(ref
) ^ A32(ip
);
157 ip
+= LZ4_NBCOMMONBYTES(diff
);
161 if ((ip
< (MATCHLIMIT
- 3)) && (A32(ref
) == A32(ip
))) {
166 if ((ip
< (MATCHLIMIT
- 1)) && (A16(ref
) == A16(ip
))) {
170 if ((ip
< MATCHLIMIT
) && (*ref
== *ip
))
173 /* Encode MatchLength */
174 length
= (int)(ip
- anchor
);
175 /* Check output limit */
176 if (unlikely(op
+ (1 + LASTLITERALS
) + (length
>> 8) > oend
))
178 if (length
>= (int)ML_MASK
) {
181 for (; length
> 509 ; length
-= 510) {
193 /* Test end of chunk */
200 hashtable
[LZ4_HASH_VALUE(ip
-2)] = ip
- 2 - base
;
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
))) {
211 /* Prepare next loop */
213 forwardh
= LZ4_HASH_VALUE(ip
);
217 /* Encode Last Literals */
218 lastrun
= (int)(iend
- anchor
);
219 if (((char *)op
- dest
) + lastrun
+ 1
220 + ((lastrun
+ 255 - RUN_MASK
) / 255) > (u32
)maxoutputsize
)
223 if (lastrun
>= (int)RUN_MASK
) {
224 *op
++ = (RUN_MASK
<< ML_BITS
);
226 for (; lastrun
> 254 ; lastrun
-= 255)
230 *op
++ = (lastrun
<< ML_BITS
);
231 memcpy(op
, anchor
, iend
- anchor
);
235 return (int)(((char *)op
) - dest
);
238 static inline int lz4_compress64kctx(void *ctx
,
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)
252 u8
*op
= (u8
*) dest
;
253 u8
*const oend
= op
+ maxoutputsize
;
255 const int skipstrength
= SKIPSTRENGTH
;
260 if (isize
< MINLENGTH
)
263 memset((void *)hashtable
, 0, LZ4_MEM_COMPRESS
);
267 forwardh
= LZ4_HASH64K_VALUE(ip
);
271 int findmatchattempts
= (1U << skipstrength
) + 3;
272 const u8
*forwardip
= ip
;
279 int step
= findmatchattempts
++ >> skipstrength
;
281 forwardip
= ip
+ step
;
283 if (forwardip
> mflimit
)
286 forwardh
= LZ4_HASH64K_VALUE(forwardip
);
287 ref
= base
+ hashtable
[h
];
288 hashtable
[h
] = (u16
)(ip
- base
);
289 } while (A32(ref
) != A32(ip
));
292 while ((ip
> anchor
) && (ref
> (u8
*)source
)
293 && (ip
[-1] == ref
[-1])) {
298 /* Encode Literal length */
299 length
= (int)(ip
- anchor
);
301 /* Check output limit */
302 if (unlikely(op
+ length
+ (2 + 1 + LASTLITERALS
)
303 + (length
>> 8) > oend
))
305 if (length
>= (int)RUN_MASK
) {
306 *token
= (RUN_MASK
<< ML_BITS
);
307 len
= length
- RUN_MASK
;
308 for (; len
> 254 ; len
-= 255)
312 *token
= (length
<< ML_BITS
);
315 LZ4_BLINDCOPY(anchor
, op
, length
);
319 LZ4_WRITE_LITTLEENDIAN_16(op
, (u16
)(ip
- ref
));
323 /* MinMatch verified */
327 while (ip
< MATCHLIMIT
- (STEPSIZE
- 1)) {
329 u64 diff
= A64(ref
) ^ A64(ip
);
331 u32 diff
= A32(ref
) ^ A32(ip
);
339 ip
+= LZ4_NBCOMMONBYTES(diff
);
343 if ((ip
< (MATCHLIMIT
- 3)) && (A32(ref
) == A32(ip
))) {
348 if ((ip
< (MATCHLIMIT
- 1)) && (A16(ref
) == A16(ip
))) {
352 if ((ip
< MATCHLIMIT
) && (*ref
== *ip
))
356 /* Encode MatchLength */
357 len
= (int)(ip
- anchor
);
358 /* Check output limit */
359 if (unlikely(op
+ (1 + LASTLITERALS
) + (len
>> 8) > oend
))
361 if (len
>= (int)ML_MASK
) {
364 for (; len
> 509 ; len
-= 510) {
376 /* Test end of chunk */
383 hashtable
[LZ4_HASH64K_VALUE(ip
-2)] = (u16
)(ip
- 2 - base
);
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
)) {
394 /* Prepare next loop */
396 forwardh
= LZ4_HASH64K_VALUE(ip
);
400 /* Encode Last Literals */
401 lastrun
= (int)(iend
- anchor
);
402 if (op
+ lastrun
+ 1 + (lastrun
- RUN_MASK
+ 255) / 255 > oend
)
404 if (lastrun
>= (int)RUN_MASK
) {
405 *op
++ = (RUN_MASK
<< ML_BITS
);
407 for (; lastrun
> 254 ; lastrun
-= 255)
411 *op
++ = (lastrun
<< ML_BITS
);
412 memcpy(op
, anchor
, iend
- anchor
);
415 return (int)(((char *)op
) - dest
);
418 int lz4_compress(const unsigned char *src
, size_t src_len
,
419 unsigned char *dst
, size_t *dst_len
, void *wrkmem
)
424 if (src_len
< LZ4_64KLIMIT
)
425 out_len
= lz4_compress64kctx(wrkmem
, src
, dst
, src_len
,
426 lz4_compressbound(src_len
));
428 out_len
= lz4_compressctx(wrkmem
, src
, dst
, src_len
,
429 lz4_compressbound(src_len
));
440 EXPORT_SYMBOL(lz4_compress
);
442 MODULE_LICENSE("Dual BSD/GPL");
443 MODULE_DESCRIPTION("LZ4 compressor");
This page took 0.038591 seconds and 5 git commands to generate.