Chanho Min | c72ac7a | 2013-07-08 16:01:49 -0700 | [diff] [blame] | 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 | } |
| 440 | EXPORT_SYMBOL_GPL(lz4_compress); |
| 441 | |
| 442 | MODULE_LICENSE("GPL"); |
| 443 | MODULE_DESCRIPTION("LZ4 compressor"); |