lib/lz4/lz4hc_compress.c

   1 /*
   2  * LZ4 HC - High Compression Mode of LZ4
   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 <[email protected]>
  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 struct lz4hc_data {
  44         const u8 *base;
  45         HTYPE hashtable[HASHTABLESIZE];
  46         u16 chaintable[MAXD];
  47         const u8 *nexttoupdate;
  48 } __attribute__((__packed__));
  49
  50 static inline int lz4hc_init(struct lz4hc_data *hc4, const u8 *base)
  51 {
  52         memset((void *)hc4->hashtable, 0, sizeof(hc4->hashtable));
  53         memset(hc4->chaintable, 0xFF, sizeof(hc4->chaintable));
  54
  55 #if LZ4_ARCH64
  56         hc4->nexttoupdate = base + 1;
  57 #else
  58         hc4->nexttoupdate = base;
  59 #endif
  60         hc4->base = base;
  61         return 1;
  62 }
  63
  64 /* Update chains up to ip (excluded) */
  65 static inline void lz4hc_insert(struct lz4hc_data *hc4, const u8 *ip)
  66 {
  67         u16 *chaintable = hc4->chaintable;
  68         HTYPE *hashtable  = hc4->hashtable;
  69 #if LZ4_ARCH64
  70         const BYTE * const base = hc4->base;
  71 #else
  72         const int base = 0;
  73 #endif
  74
  75         while (hc4->nexttoupdate < ip) {
  76                 const u8 *p = hc4->nexttoupdate;
  77                 size_t delta = p - (hashtable[HASH_VALUE(p)] + base);
  78                 if (delta > MAX_DISTANCE)
  79                         delta = MAX_DISTANCE;
  80                 chaintable[(size_t)(p) & MAXD_MASK] = (u16)delta;
  81                 hashtable[HASH_VALUE(p)] = (p) - base;
  82                 hc4->nexttoupdate++;
  83         }
  84 }
  85
  86 static inline size_t lz4hc_commonlength(const u8 *p1, const u8 *p2,
  87                 const u8 *const matchlimit)
  88 {
  89         const u8 *p1t = p1;
  90
  91         while (p1t < matchlimit - (STEPSIZE - 1)) {
  92 #if LZ4_ARCH64
  93                 u64 diff = A64(p2) ^ A64(p1t);
  94 #else
  95                 u32 diff = A32(p2) ^ A32(p1t);
  96 #endif
  97                 if (!diff) {
  98                         p1t += STEPSIZE;
  99                         p2 += STEPSIZE;
 100                         continue;
 101                 }
 102                 p1t += LZ4_NBCOMMONBYTES(diff);
 103                 return p1t - p1;
 104         }
 105 #if LZ4_ARCH64
 106         if ((p1t < (matchlimit-3)) && (A32(p2) == A32(p1t))) {
 107                 p1t += 4;
 108                 p2 += 4;
 109         }
 110 #endif
 111
 112         if ((p1t < (matchlimit - 1)) && (A16(p2) == A16(p1t))) {
 113                 p1t += 2;
 114                 p2 += 2;
 115         }
 116         if ((p1t < matchlimit) && (*p2 == *p1t))
 117                 p1t++;
 118         return p1t - p1;
 119 }
 120
 121 static inline int lz4hc_insertandfindbestmatch(struct lz4hc_data *hc4,
 122                 const u8 *ip, const u8 *const matchlimit, const u8 **matchpos)
 123 {
 124         u16 *const chaintable = hc4->chaintable;
 125         HTYPE *const hashtable = hc4->hashtable;
 126         const u8 *ref;
 127 #if LZ4_ARCH64
 128         const BYTE * const base = hc4->base;
 129 #else
 130         const int base = 0;
 131 #endif
 132         int nbattempts = MAX_NB_ATTEMPTS;
 133         size_t repl = 0, ml = 0;
 134         u16 delta;
 135
 136         /* HC4 match finder */
 137         lz4hc_insert(hc4, ip);
 138         ref = hashtable[HASH_VALUE(ip)] + base;
 139
 140         /* potential repetition */
 141         if (ref >= ip-4) {
 142                 /* confirmed */
 143                 if (A32(ref) == A32(ip)) {
 144                         delta = (u16)(ip-ref);
 145                         repl = ml  = lz4hc_commonlength(ip + MINMATCH,
 146                                         ref + MINMATCH, matchlimit) + MINMATCH;
 147                         *matchpos = ref;
 148                 }
 149                 ref -= (size_t)chaintable[(size_t)(ref) & MAXD_MASK];
 150         }
 151
 152         while ((ref >= ip - MAX_DISTANCE) && nbattempts) {
 153                 nbattempts--;
 154                 if (*(ref + ml) == *(ip + ml)) {
 155                         if (A32(ref) == A32(ip)) {
 156                                 size_t mlt =
 157                                         lz4hc_commonlength(ip + MINMATCH,
 158                                         ref + MINMATCH, matchlimit) + MINMATCH;
 159                                 if (mlt > ml) {
 160                                         ml = mlt;
 161                                         *matchpos = ref;
 162                                 }
 163                         }
 164                 }
 165                 ref -= (size_t)chaintable[(size_t)(ref) & MAXD_MASK];
 166         }
 167
 168         /* Complete table */
 169         if (repl) {
 170                 const BYTE *ptr = ip;
 171                 const BYTE *end;
 172                 end = ip + repl - (MINMATCH-1);
 173                 /* Pre-Load */
 174                 while (ptr < end - delta) {
 175                         chaintable[(size_t)(ptr) & MAXD_MASK] = delta;
 176                         ptr++;
 177                 }
 178                 do {
 179                         chaintable[(size_t)(ptr) & MAXD_MASK] = delta;
 180                         /* Head of chain */
 181                         hashtable[HASH_VALUE(ptr)] = (ptr) - base;
 182                         ptr++;
 183                 } while (ptr < end);
 184                 hc4->nexttoupdate = end;
 185         }
 186
 187         return (int)ml;
 188 }
 189
 190 static inline int lz4hc_insertandgetwidermatch(struct lz4hc_data *hc4,
 191         const u8 *ip, const u8 *startlimit, const u8 *matchlimit, int longest,
 192         const u8 **matchpos, const u8 **startpos)
 193 {
 194         u16 *const chaintable = hc4->chaintable;
 195         HTYPE *const hashtable = hc4->hashtable;
 196 #if LZ4_ARCH64
 197         const BYTE * const base = hc4->base;
 198 #else
 199         const int base = 0;
 200 #endif
 201         const u8 *ref;
 202         int nbattempts = MAX_NB_ATTEMPTS;
 203         int delta = (int)(ip - startlimit);
 204
 205         /* First Match */
 206         lz4hc_insert(hc4, ip);
 207         ref = hashtable[HASH_VALUE(ip)] + base;
 208
 209         while ((ref >= ip - MAX_DISTANCE) && (ref >= hc4->base)
 210                 && (nbattempts)) {
 211                 nbattempts--;
 212                 if (*(startlimit + longest) == *(ref - delta + longest)) {
 213                         if (A32(ref) == A32(ip)) {
 214                                 const u8 *reft = ref + MINMATCH;
 215                                 const u8 *ipt = ip + MINMATCH;
 216                                 const u8 *startt = ip;
 217
 218                                 while (ipt < matchlimit-(STEPSIZE - 1)) {
 219                                         #if LZ4_ARCH64
 220                                         u64 diff = A64(reft) ^ A64(ipt);
 221                                         #else
 222                                         u32 diff = A32(reft) ^ A32(ipt);
 223                                         #endif
 224
 225                                         if (!diff) {
 226                                                 ipt += STEPSIZE;
 227                                                 reft += STEPSIZE;
 228                                                 continue;
 229                                         }
 230                                         ipt += LZ4_NBCOMMONBYTES(diff);
 231                                         goto _endcount;
 232                                 }
 233                                 #if LZ4_ARCH64
 234                                 if ((ipt < (matchlimit - 3))
 235                                         && (A32(reft) == A32(ipt))) {
 236                                         ipt += 4;
 237                                         reft += 4;
 238                                 }
 239                                 ipt += 2;
 240                                 #endif
 241                                 if ((ipt < (matchlimit - 1))
 242                                         && (A16(reft) == A16(ipt))) {
 243                                         reft += 2;
 244                                 }
 245                                 if ((ipt < matchlimit) && (*reft == *ipt))
 246                                         ipt++;
 247 _endcount:
 248                                 reft = ref;
 249
 250                                 while ((startt > startlimit)
 251                                         && (reft > hc4->base)
 252                                         && (startt[-1] == reft[-1])) {
 253                                         startt--;
 254                                         reft--;
 255                                 }
 256
 257                                 if ((ipt - startt) > longest) {
 258                                         longest = (int)(ipt - startt);
 259                                         *matchpos = reft;
 260                                         *startpos = startt;
 261                                 }
 262                         }
 263                 }
 264                 ref -= (size_t)chaintable[(size_t)(ref) & MAXD_MASK];
 265         }
 266         return longest;
 267 }
 268
 269 static inline int lz4_encodesequence(const u8 **ip, u8 **op, const u8 **anchor,
 270                 int ml, const u8 *ref)
 271 {
 272         int length, len;
 273         u8 *token;
 274
 275         /* Encode Literal length */
 276         length = (int)(*ip - *anchor);
 277         token = (*op)++;
 278         if (length >= (int)RUN_MASK) {
 279                 *token = (RUN_MASK << ML_BITS);
 280                 len = length - RUN_MASK;
 281                 for (; len > 254 ; len -= 255)
 282                         *(*op)++ = 255;
 283                 *(*op)++ = (u8)len;
 284         } else
 285                 *token = (length << ML_BITS);
 286
 287         /* Copy Literals */
 288         LZ4_BLINDCOPY(*anchor, *op, length);
 289
 290         /* Encode Offset */
 291         LZ4_WRITE_LITTLEENDIAN_16(*op, (u16)(*ip - ref));
 292
 293         /* Encode MatchLength */
 294         len = (int)(ml - MINMATCH);
 295         if (len >= (int)ML_MASK) {
 296                 *token += ML_MASK;
 297                 len -= ML_MASK;
 298                 for (; len > 509 ; len -= 510) {
 299                         *(*op)++ = 255;
 300                         *(*op)++ = 255;
 301                 }
 302                 if (len > 254) {
 303                         len -= 255;
 304                         *(*op)++ = 255;
 305                 }
 306                 *(*op)++ = (u8)len;
 307         } else
 308                 *token += len;
 309
 310         /* Prepare next loop */
 311         *ip += ml;
 312         *anchor = *ip;
 313
 314         return 0;
 315 }
 316
 317 static int lz4_compresshcctx(struct lz4hc_data *ctx,
 318                 const char *source,
 319                 char *dest,
 320                 int isize)
 321 {
 322         const u8 *ip = (const u8 *)source;
 323         const u8 *anchor = ip;
 324         const u8 *const iend = ip + isize;
 325         const u8 *const mflimit = iend - MFLIMIT;
 326         const u8 *const matchlimit = (iend - LASTLITERALS);
 327
 328         u8 *op = (u8 *)dest;
 329
 330         int ml, ml2, ml3, ml0;
 331         const u8 *ref = NULL;
 332         const u8 *start2 = NULL;
 333         const u8 *ref2 = NULL;
 334         const u8 *start3 = NULL;
 335         const u8 *ref3 = NULL;
 336         const u8 *start0;
 337         const u8 *ref0;
 338         int lastrun;
 339
 340         ip++;
 341
 342         /* Main Loop */
 343         while (ip < mflimit) {
 344                 ml = lz4hc_insertandfindbestmatch(ctx, ip, matchlimit, (&ref));
 345                 if (!ml) {
 346                         ip++;
 347                         continue;
 348                 }
 349
 350                 /* saved, in case we would skip too much */
 351                 start0 = ip;
 352                 ref0 = ref;
 353                 ml0 = ml;
 354 _search2:
 355                 if (ip+ml < mflimit)
 356                         ml2 = lz4hc_insertandgetwidermatch(ctx, ip + ml - 2,
 357                                 ip + 1, matchlimit, ml, &ref2, &start2);
 358                 else
 359                         ml2 = ml;
 360                 /* No better match */
 361                 if (ml2 == ml) {
 362                         lz4_encodesequence(&ip, &op, &anchor, ml, ref);
 363                         continue;
 364                 }
 365
 366                 if (start0 < ip) {
 367                         /* empirical */
 368                         if (start2 < ip + ml0) {
 369                                 ip = start0;
 370                                 ref = ref0;
 371                                 ml = ml0;
 372                         }
 373                 }
 374                 /*
 375                  * Here, start0==ip
 376                  * First Match too small : removed
 377                  */
 378                 if ((start2 - ip) < 3) {
 379                         ml = ml2;
 380                         ip = start2;
 381                         ref = ref2;
 382                         goto _search2;
 383                 }
 384
 385 _search3:
 386                 /*
 387                  * Currently we have :
 388                  * ml2 > ml1, and
 389                  * ip1+3 <= ip2 (usually < ip1+ml1)
 390                  */
 391                 if ((start2 - ip) < OPTIMAL_ML) {
 392                         int correction;
 393                         int new_ml = ml;
 394                         if (new_ml > OPTIMAL_ML)
 395                                 new_ml = OPTIMAL_ML;
 396                         if (ip + new_ml > start2 + ml2 - MINMATCH)
 397                                 new_ml = (int)(start2 - ip) + ml2 - MINMATCH;
 398                         correction = new_ml - (int)(start2 - ip);
 399                         if (correction > 0) {
 400                                 start2 += correction;
 401                                 ref2 += correction;
 402                                 ml2 -= correction;
 403                         }
 404                 }
 405                 /*
 406                  * Now, we have start2 = ip+new_ml,
 407                  * with new_ml=min(ml, OPTIMAL_ML=18)
 408                  */
 409                 if (start2 + ml2 < mflimit)
 410                         ml3 = lz4hc_insertandgetwidermatch(ctx,
 411                                 start2 + ml2 - 3, start2, matchlimit,
 412                                 ml2, &ref3, &start3);
 413                 else
 414                         ml3 = ml2;
 415
 416                 /* No better match : 2 sequences to encode */
 417                 if (ml3 == ml2) {
 418                         /* ip & ref are known; Now for ml */
 419                         if (start2 < ip+ml)
 420                                 ml = (int)(start2 - ip);
 421
 422                         /* Now, encode 2 sequences */
 423                         lz4_encodesequence(&ip, &op, &anchor, ml, ref);
 424                         ip = start2;
 425                         lz4_encodesequence(&ip, &op, &anchor, ml2, ref2);
 426                         continue;
 427                 }
 428
 429                 /* Not enough space for match 2 : remove it */
 430                 if (start3 < ip + ml + 3) {
 431                         /*
 432                          * can write Seq1 immediately ==> Seq2 is removed,
 433                          * so Seq3 becomes Seq1
 434                          */
 435                         if (start3 >= (ip + ml)) {
 436                                 if (start2 < ip + ml) {
 437                                         int correction =
 438                                                 (int)(ip + ml - start2);
 439                                         start2 += correction;
 440                                         ref2 += correction;
 441                                         ml2 -= correction;
 442                                         if (ml2 < MINMATCH) {
 443                                                 start2 = start3;
 444                                                 ref2 = ref3;
 445                                                 ml2 = ml3;
 446                                         }
 447                                 }
 448
 449                                 lz4_encodesequence(&ip, &op, &anchor, ml, ref);
 450                                 ip  = start3;
 451                                 ref = ref3;
 452                                 ml  = ml3;
 453
 454                                 start0 = start2;
 455                                 ref0 = ref2;
 456                                 ml0 = ml2;
 457                                 goto _search2;
 458                         }
 459
 460                         start2 = start3;
 461                         ref2 = ref3;
 462                         ml2 = ml3;
 463                         goto _search3;
 464                 }
 465
 466                 /*
 467                  * OK, now we have 3 ascending matches; let's write at least
 468                  * the first one ip & ref are known; Now for ml
 469                  */
 470                 if (start2 < ip + ml) {
 471                         if ((start2 - ip) < (int)ML_MASK) {
 472                                 int correction;
 473                                 if (ml > OPTIMAL_ML)
 474                                         ml = OPTIMAL_ML;
 475                                 if (ip + ml > start2 + ml2 - MINMATCH)
 476                                         ml = (int)(start2 - ip) + ml2
 477                                                 - MINMATCH;
 478                                 correction = ml - (int)(start2 - ip);
 479                                 if (correction > 0) {
 480                                         start2 += correction;
 481                                         ref2 += correction;
 482                                         ml2 -= correction;
 483                                 }
 484                         } else
 485                                 ml = (int)(start2 - ip);
 486                 }
 487                 lz4_encodesequence(&ip, &op, &anchor, ml, ref);
 488
 489                 ip = start2;
 490                 ref = ref2;
 491                 ml = ml2;
 492
 493                 start2 = start3;
 494                 ref2 = ref3;
 495                 ml2 = ml3;
 496
 497                 goto _search3;
 498         }
 499
 500         /* Encode Last Literals */
 501         lastrun = (int)(iend - anchor);
 502         if (lastrun >= (int)RUN_MASK) {
 503                 *op++ = (RUN_MASK << ML_BITS);
 504                 lastrun -= RUN_MASK;
 505                 for (; lastrun > 254 ; lastrun -= 255)
 506                         *op++ = 255;
 507                 *op++ = (u8) lastrun;
 508         } else
 509                 *op++ = (lastrun << ML_BITS);
 510         memcpy(op, anchor, iend - anchor);
 511         op += iend - anchor;
 512         /* End */
 513         return (int) (((char *)op) - dest);
 514 }
 515
 516 int lz4hc_compress(const unsigned char *src, size_t src_len,
 517                         unsigned char *dst, size_t *dst_len, void *wrkmem)
 518 {
 519         int ret = -1;
 520         int out_len = 0;
 521
 522         struct lz4hc_data *hc4 = (struct lz4hc_data *)wrkmem;
 523         lz4hc_init(hc4, (const u8 *)src);
 524         out_len = lz4_compresshcctx((struct lz4hc_data *)hc4, (const u8 *)src,
 525                 (char *)dst, (int)src_len);
 526
 527         if (out_len < 0)
 528                 goto exit;
 529
 530         *dst_len = out_len;
 531         return 0;
 532
 533 exit:
 534         return ret;
 535 }
 536 EXPORT_SYMBOL(lz4hc_compress);
 537
 538 MODULE_LICENSE("Dual BSD/GPL");
 539 MODULE_DESCRIPTION("LZ4HC compressor");