git.sesse.net Git - bcachefs-tools-debian/blob - linux/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 <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 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 u8 * 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 int lz4hc_insertandfindbestmatch(struct lz4hc_data *hc4,
  87                 const u8 *ip, const u8 *const matchlimit, const u8 **matchpos)
  88 {
  89         u16 *const chaintable = hc4->chaintable;
  90         HTYPE *const hashtable = hc4->hashtable;
  91         const u8 *ref;
  92 #if LZ4_ARCH64
  93         const u8 * const base = hc4->base;
  94 #else
  95         const int base = 0;
  96 #endif
  97         int nbattempts = MAX_NB_ATTEMPTS;
  98         size_t repl = 0, ml = 0;
  99         u16 delta;
 100
 101         /* HC4 match finder */
 102         lz4hc_insert(hc4, ip);
 103         ref = hashtable[HASH_VALUE(ip)] + base;
 104
 105         /* potential repetition */
 106         if (ref >= ip-4) {
 107                 /* confirmed */
 108                 if (A32(ref) == A32(ip)) {
 109                         delta = (u16)(ip-ref);
 110                         repl = ml  = common_length(ip + MINMATCH,
 111                                         ref + MINMATCH, matchlimit) + MINMATCH;
 112                         *matchpos = ref;
 113                 }
 114                 ref -= (size_t)chaintable[(size_t)(ref) & MAXD_MASK];
 115         }
 116
 117         while ((ref >= ip - MAX_DISTANCE) && nbattempts) {
 118                 nbattempts--;
 119                 if (*(ref + ml) == *(ip + ml)) {
 120                         if (A32(ref) == A32(ip)) {
 121                                 size_t mlt =
 122                                         common_length(ip + MINMATCH,
 123                                         ref + MINMATCH, matchlimit) + MINMATCH;
 124                                 if (mlt > ml) {
 125                                         ml = mlt;
 126                                         *matchpos = ref;
 127                                 }
 128                         }
 129                 }
 130                 ref -= (size_t)chaintable[(size_t)(ref) & MAXD_MASK];
 131         }
 132
 133         /* Complete table */
 134         if (repl) {
 135                 const u8 *ptr = ip;
 136                 const u8 *end;
 137                 end = ip + repl - (MINMATCH-1);
 138                 /* Pre-Load */
 139                 while (ptr < end - delta) {
 140                         chaintable[(size_t)(ptr) & MAXD_MASK] = delta;
 141                         ptr++;
 142                 }
 143                 do {
 144                         chaintable[(size_t)(ptr) & MAXD_MASK] = delta;
 145                         /* Head of chain */
 146                         hashtable[HASH_VALUE(ptr)] = (ptr) - base;
 147                         ptr++;
 148                 } while (ptr < end);
 149                 hc4->nexttoupdate = end;
 150         }
 151
 152         return (int)ml;
 153 }
 154
 155 static inline int lz4hc_insertandgetwidermatch(struct lz4hc_data *hc4,
 156         const u8 *ip, const u8 *startlimit, const u8 *matchlimit, int longest,
 157         const u8 **matchpos, const u8 **startpos)
 158 {
 159         u16 *const chaintable = hc4->chaintable;
 160         HTYPE *const hashtable = hc4->hashtable;
 161 #if LZ4_ARCH64
 162         const u8 * const base = hc4->base;
 163 #else
 164         const int base = 0;
 165 #endif
 166         const u8 *ref;
 167         int nbattempts = MAX_NB_ATTEMPTS;
 168         int delta = (int)(ip - startlimit);
 169
 170         /* First Match */
 171         lz4hc_insert(hc4, ip);
 172         ref = hashtable[HASH_VALUE(ip)] + base;
 173
 174         while ((ref >= ip - MAX_DISTANCE) && (ref >= hc4->base)
 175                 && (nbattempts)) {
 176                 nbattempts--;
 177                 if (*(startlimit + longest) == *(ref - delta + longest)) {
 178                         if (A32(ref) == A32(ip)) {
 179                                 const u8 *reft = ref;
 180                                 const u8 *startt = ip;
 181                                 unsigned length =
 182                                         common_length(ip + MINMATCH,
 183                                                       ref + MINMATCH,
 184                                                       matchlimit);
 185
 186                                 while ((startt > startlimit)
 187                                         && (reft > hc4->base)
 188                                         && (startt[-1] == reft[-1])) {
 189                                         startt--;
 190                                         reft--;
 191                                         length++;
 192                                 }
 193
 194                                 if (length > longest) {
 195                                         longest = length;
 196                                         *matchpos = reft;
 197                                         *startpos = startt;
 198                                 }
 199                         }
 200                 }
 201                 ref -= (size_t)chaintable[(size_t)(ref) & MAXD_MASK];
 202         }
 203         return longest;
 204 }
 205
 206 static inline int lz4_encodesequence(const u8 **ip, u8 **op, const u8 **anchor,
 207                 int ml, const u8 *ref)
 208 {
 209         unsigned length;
 210         u8 *token;
 211
 212         /* Encode Literal length */
 213         length = *ip - *anchor;
 214         token = (*op)++;
 215         *token = encode_length(op, length) << ML_BITS;
 216
 217         /* Copy Literals */
 218         MEMCPY_ADVANCE_CHUNKED(*op, *anchor, length);
 219
 220         /* Encode Offset */
 221         PUT_LE16_ADVANCE(*op, (u16)(*ip - ref));
 222
 223         *token += encode_length(op, ml - MINMATCH);
 224
 225         /* Prepare next loop */
 226         *ip += ml;
 227         *anchor = *ip;
 228
 229         return 0;
 230 }
 231
 232 static int lz4_compresshcctx(struct lz4hc_data *ctx,
 233                 const char *source,
 234                 char *dest,
 235                 int isize)
 236 {
 237         const u8 *ip = (const u8 *)source;
 238         const u8 *anchor = ip;
 239         const u8 *const iend = ip + isize;
 240         const u8 *const mflimit = iend - MFLIMIT;
 241         const u8 *const matchlimit = (iend - LASTLITERALS);
 242
 243         u8 *op = (u8 *)dest;
 244
 245         int ml, ml2, ml3, ml0;
 246         const u8 *ref = NULL;
 247         const u8 *start2 = NULL;
 248         const u8 *ref2 = NULL;
 249         const u8 *start3 = NULL;
 250         const u8 *ref3 = NULL;
 251         const u8 *start0;
 252         const u8 *ref0;
 253         int lastrun;
 254
 255         ip++;
 256
 257         /* Main Loop */
 258         while (ip < mflimit) {
 259                 ml = lz4hc_insertandfindbestmatch(ctx, ip, matchlimit, (&ref));
 260                 if (!ml) {
 261                         ip++;
 262                         continue;
 263                 }
 264
 265                 /* saved, in case we would skip too much */
 266                 start0 = ip;
 267                 ref0 = ref;
 268                 ml0 = ml;
 269 _search2:
 270                 if (ip+ml < mflimit)
 271                         ml2 = lz4hc_insertandgetwidermatch(ctx, ip + ml - 2,
 272                                 ip + 1, matchlimit, ml, &ref2, &start2);
 273                 else
 274                         ml2 = ml;
 275                 /* No better match */
 276                 if (ml2 == ml) {
 277                         lz4_encodesequence(&ip, &op, &anchor, ml, ref);
 278                         continue;
 279                 }
 280
 281                 if (start0 < ip) {
 282                         /* empirical */
 283                         if (start2 < ip + ml0) {
 284                                 ip = start0;
 285                                 ref = ref0;
 286                                 ml = ml0;
 287                         }
 288                 }
 289                 /*
 290                  * Here, start0==ip
 291                  * First Match too small : removed
 292                  */
 293                 if ((start2 - ip) < 3) {
 294                         ml = ml2;
 295                         ip = start2;
 296                         ref = ref2;
 297                         goto _search2;
 298                 }
 299
 300 _search3:
 301                 /*
 302                  * Currently we have :
 303                  * ml2 > ml1, and
 304                  * ip1+3 <= ip2 (usually < ip1+ml1)
 305                  */
 306                 if ((start2 - ip) < OPTIMAL_ML) {
 307                         int correction;
 308                         int new_ml = ml;
 309                         if (new_ml > OPTIMAL_ML)
 310                                 new_ml = OPTIMAL_ML;
 311                         if (ip + new_ml > start2 + ml2 - MINMATCH)
 312                                 new_ml = (int)(start2 - ip) + ml2 - MINMATCH;
 313                         correction = new_ml - (int)(start2 - ip);
 314                         if (correction > 0) {
 315                                 start2 += correction;
 316                                 ref2 += correction;
 317                                 ml2 -= correction;
 318                         }
 319                 }
 320                 /*
 321                  * Now, we have start2 = ip+new_ml,
 322                  * with new_ml=min(ml, OPTIMAL_ML=18)
 323                  */
 324                 if (start2 + ml2 < mflimit)
 325                         ml3 = lz4hc_insertandgetwidermatch(ctx,
 326                                 start2 + ml2 - 3, start2, matchlimit,
 327                                 ml2, &ref3, &start3);
 328                 else
 329                         ml3 = ml2;
 330
 331                 /* No better match : 2 sequences to encode */
 332                 if (ml3 == ml2) {
 333                         /* ip & ref are known; Now for ml */
 334                         if (start2 < ip+ml)
 335                                 ml = (int)(start2 - ip);
 336
 337                         /* Now, encode 2 sequences */
 338                         lz4_encodesequence(&ip, &op, &anchor, ml, ref);
 339                         ip = start2;
 340                         lz4_encodesequence(&ip, &op, &anchor, ml2, ref2);
 341                         continue;
 342                 }
 343
 344                 /* Not enough space for match 2 : remove it */
 345                 if (start3 < ip + ml + 3) {
 346                         /*
 347                          * can write Seq1 immediately ==> Seq2 is removed,
 348                          * so Seq3 becomes Seq1
 349                          */
 350                         if (start3 >= (ip + ml)) {
 351                                 if (start2 < ip + ml) {
 352                                         int correction =
 353                                                 (int)(ip + ml - start2);
 354                                         start2 += correction;
 355                                         ref2 += correction;
 356                                         ml2 -= correction;
 357                                         if (ml2 < MINMATCH) {
 358                                                 start2 = start3;
 359                                                 ref2 = ref3;
 360                                                 ml2 = ml3;
 361                                         }
 362                                 }
 363
 364                                 lz4_encodesequence(&ip, &op, &anchor, ml, ref);
 365                                 ip  = start3;
 366                                 ref = ref3;
 367                                 ml  = ml3;
 368
 369                                 start0 = start2;
 370                                 ref0 = ref2;
 371                                 ml0 = ml2;
 372                                 goto _search2;
 373                         }
 374
 375                         start2 = start3;
 376                         ref2 = ref3;
 377                         ml2 = ml3;
 378                         goto _search3;
 379                 }
 380
 381                 /*
 382                  * OK, now we have 3 ascending matches; let's write at least
 383                  * the first one ip & ref are known; Now for ml
 384                  */
 385                 if (start2 < ip + ml) {
 386                         if ((start2 - ip) < (int)ML_MASK) {
 387                                 int correction;
 388                                 if (ml > OPTIMAL_ML)
 389                                         ml = OPTIMAL_ML;
 390                                 if (ip + ml > start2 + ml2 - MINMATCH)
 391                                         ml = (int)(start2 - ip) + ml2
 392                                                 - MINMATCH;
 393                                 correction = ml - (int)(start2 - ip);
 394                                 if (correction > 0) {
 395                                         start2 += correction;
 396                                         ref2 += correction;
 397                                         ml2 -= correction;
 398                                 }
 399                         } else
 400                                 ml = (int)(start2 - ip);
 401                 }
 402                 lz4_encodesequence(&ip, &op, &anchor, ml, ref);
 403
 404                 ip = start2;
 405                 ref = ref2;
 406                 ml = ml2;
 407
 408                 start2 = start3;
 409                 ref2 = ref3;
 410                 ml2 = ml3;
 411
 412                 goto _search3;
 413         }
 414
 415         /* Encode Last Literals */
 416         lastrun = (int)(iend - anchor);
 417         if (lastrun >= (int)RUN_MASK) {
 418                 *op++ = (RUN_MASK << ML_BITS);
 419                 lastrun -= RUN_MASK;
 420                 for (; lastrun > 254 ; lastrun -= 255)
 421                         *op++ = 255;
 422                 *op++ = (u8) lastrun;
 423         } else
 424                 *op++ = (lastrun << ML_BITS);
 425         memcpy(op, anchor, iend - anchor);
 426         op += iend - anchor;
 427         /* End */
 428         return (int) (((char *)op) - dest);
 429 }
 430
 431 int lz4hc_compress(const unsigned char *src, size_t src_len,
 432                         unsigned char *dst, size_t *dst_len, void *wrkmem)
 433 {
 434         int ret = -1;
 435         int out_len = 0;
 436
 437         struct lz4hc_data *hc4 = (struct lz4hc_data *)wrkmem;
 438         lz4hc_init(hc4, (const u8 *)src);
 439         out_len = lz4_compresshcctx((struct lz4hc_data *)hc4, (const u8 *)src,
 440                 (char *)dst, (int)src_len);
 441
 442         if (out_len < 0)
 443                 goto exit;
 444
 445         *dst_len = out_len;
 446         return 0;
 447
 448 exit:
 449         return ret;
 450 }
 451 EXPORT_SYMBOL(lz4hc_compress);
 452
 453 MODULE_LICENSE("Dual BSD/GPL");
 454 MODULE_DESCRIPTION("LZ4HC compressor");