git.sesse.net Git - bcachefs-tools-debian/blob - linux/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/log2.h>
  38 #include <linux/module.h>
  39 #include <linux/kernel.h>
  40 #include <linux/lz4.h>
  41 #include <asm/unaligned.h>
  42 #include "lz4defs.h"
  43
  44 #define LZ4_HASH_VALUE(p, _table)                               \
  45         __HASH_VALUE(p, MEMORY_USAGE - ilog2(sizeof(_table[0])))
  46
  47 struct lz4_hash_table {
  48         const u8        *(*add)(const struct lz4_hash_table, const u8 *);
  49         void            *ctx;
  50         const u8        *base;
  51 };
  52
  53 #if __SIZEOF_POINTER__ == 4
  54 static inline const u8 *hash_table_add32(const struct lz4_hash_table hash,
  55                                          const u8 *ip)
  56 {
  57         const u8 **table = hash.ctx;
  58
  59         swap(table[LZ4_HASH_VALUE(ip, table)], ip);
  60         return ip;
  61 }
  62 #else
  63 static inline const u8 *hash_table_add32(const struct lz4_hash_table hash,
  64                                          const u8 *ip)
  65 {
  66         u32 *table = hash.ctx;
  67         size_t offset = ip - hash.base;
  68
  69         swap(table[LZ4_HASH_VALUE(ip, table)], offset);
  70         return hash.base + offset;
  71 }
  72 #endif
  73
  74 static inline const u8 *hash_table_add16(const struct lz4_hash_table hash,
  75                                          const u8 *ip)
  76 {
  77         u16 *table = hash.ctx;
  78         size_t offset = ip - hash.base;
  79
  80         swap(table[LZ4_HASH_VALUE(ip, table)], offset);
  81         return hash.base + offset;
  82 }
  83
  84 static inline const u8 *try_match(const struct lz4_hash_table hash,
  85                                   const u8 *ip)
  86 {
  87         const u8 *ref = hash.add(hash, ip);
  88
  89         return ref >= ip - MAX_DISTANCE &&
  90                 A32(ref) == A32(ip) ? ref : NULL;
  91 }
  92
  93 static inline const u8 *find_match(const struct lz4_hash_table hash,
  94                                    const u8 **ip, const u8 *anchor,
  95                                    const u8 *start, const u8 *end)
  96 {
  97
  98         int findmatchattempts = (1U << SKIPSTRENGTH) + 3;
  99         const u8 *next_ip = *ip, *ref;
 100
 101         do {
 102                 *ip = next_ip;
 103                 next_ip += findmatchattempts++ >> SKIPSTRENGTH;
 104
 105                 if (unlikely(next_ip > end))
 106                         return NULL;
 107         } while (!(ref = try_match(hash, *ip)));
 108
 109         /* Catch up */
 110         while (*ip > anchor &&
 111                ref > start &&
 112                unlikely((*ip)[-1] == ref[-1])) {
 113                 (*ip)--;
 114                 ref--;
 115         }
 116
 117         return ref;
 118 }
 119
 120 /*
 121  * LZ4_compressCtx :
 122  * -----------------
 123  * Compress 'isize' bytes from 'source' into an output buffer 'dest' of
 124  * maximum size 'maxOutputSize'.  * If it cannot achieve it, compression
 125  * will stop, and result of the function will be zero.
 126  * return : the number of bytes written in buffer 'dest', or 0 if the
 127  * compression fails
 128  */
 129 static inline int lz4_compressctx(const struct lz4_hash_table hash,
 130                                   const u8 *src, size_t src_len,
 131                                   u8 *dst, size_t *dst_len)
 132 {
 133         const u8 *ip = src;
 134         const u8 *anchor = ip, *ref;
 135         const u8 *const iend = ip + src_len;
 136         const u8 *const mflimit = iend - MFLIMIT;
 137         const u8 *const matchlimit = iend - LASTLITERALS;
 138         size_t maxoutputsize = *dst_len;
 139         u8 *op = dst;
 140         u8 *const oend = op + maxoutputsize;
 141         int length;
 142         u8 *token;
 143
 144         /* Init */
 145         if (src_len < MINLENGTH)
 146                 goto _last_literals;
 147
 148         memset(hash.ctx, 0, LZ4_MEM_COMPRESS);
 149         hash.add(hash, ip);
 150
 151         /* Main Loop */
 152         while (1) {
 153                 /* Starting a literal: */
 154                 anchor = ip++;
 155                 ref = find_match(hash, &ip, anchor, src, mflimit);
 156                 if (!ref)
 157                         goto _last_literals;
 158
 159                 /*
 160                  * We found a match; @ip now points to the match and @ref points
 161                  * to the prior part of the input we matched with. Everything up
 162                  * to @anchor has been encoded; the range from @anchor to @ip
 163                  * didn't match and now has to be encoded as a literal:
 164                  */
 165                 length = ip - anchor;
 166                 token = op++;
 167
 168                 /* check output limit */
 169                 if (unlikely(op + length + (2 + 1 + LASTLITERALS) +
 170                              (length >> 8) > oend))
 171                         return -(ip - src);
 172
 173                 *token = encode_length(&op, length) << ML_BITS;
 174
 175                 /* Copy Literals */
 176                 MEMCPY_ADVANCE_CHUNKED(op, anchor, length);
 177
 178                 /* Encode matches: */
 179                 while (1) {
 180                         /* Match offset: */
 181                         PUT_LE16_ADVANCE(op, ip - ref);
 182
 183                         /* MINMATCH bytes already matched from find_match(): */
 184                         ip += MINMATCH;
 185                         ref += MINMATCH;
 186
 187                         length = common_length(ip, ref, matchlimit);
 188
 189                         /* Check output limit */
 190                         if (unlikely(op + (1 + LASTLITERALS) +
 191                                      (length >> 8) > oend))
 192                                 return -(ip - src);
 193
 194                         ip += length;
 195
 196                         *token += encode_length(&op, length);
 197
 198                         /* Test end of chunk */
 199                         if (ip > mflimit) {
 200                                 anchor = ip;
 201                                 break;
 202                         }
 203
 204                         /* Fill table */
 205                         hash.add(hash, ip - 2);
 206
 207                         /* Test next position */
 208                         ref = try_match(hash, ip);
 209                         if (!ref)
 210                                 break;
 211
 212                         token = op++;
 213                         *token = 0;
 214                 }
 215         }
 216
 217 _last_literals:
 218         /* Encode Last Literals */
 219         length = iend - anchor;
 220         if ((op - dst) + length + 1 +
 221             ((length + 255 - RUN_MASK) / 255) > (u32)maxoutputsize)
 222                 return -(ip - src);
 223
 224         token = op++;
 225         *token = encode_length(&op, length) << ML_BITS;
 226         MEMCPY_ADVANCE(op, anchor, iend - anchor);
 227
 228         /* End */
 229         *dst_len = op - dst;
 230         return 0;
 231 }
 232
 233 __attribute__((flatten))
 234 int lz4_compress(const unsigned char *src, size_t src_len,
 235                  unsigned char *dst, size_t *dst_len, void *wrkmem)
 236 {
 237         if (src_len < LZ4_64KLIMIT) {
 238                 const struct lz4_hash_table hash = {
 239                         .add    = hash_table_add16,
 240                         .ctx    = wrkmem,
 241                         .base   = src,
 242                 };
 243
 244                 return lz4_compressctx(hash, src, src_len, dst, dst_len);
 245         } else {
 246                 const struct lz4_hash_table hash = {
 247                         .add    = hash_table_add32,
 248                         .ctx    = wrkmem,
 249                         .base   = src,
 250                 };
 251
 252                 return lz4_compressctx(hash, src, src_len, dst, dst_len);
 253         }
 254 }
 255 EXPORT_SYMBOL(lz4_compress);
 256
 257 MODULE_LICENSE("Dual BSD/GPL");
 258 MODULE_DESCRIPTION("LZ4 compressor");