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(lz4_compress); 441 442 MODULE_LICENSE("Dual BSD/GPL"); 443 MODULE_DESCRIPTION("LZ4 compressor"); 444