lib/lz4/lz4_compress.c

   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");