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/kernel.h>
  39 #include <linux/lz4.h>
  40 #include <asm/unaligned.h>
  41 #include "lz4defs.h"
  42
  43 #define LZ4_HASH_VALUE(p, _table)                               \
  44         __HASH_VALUE(p, MEMORY_USAGE - ilog2(sizeof(_table[0])))
  45
  46 struct lz4_hash_table {
  47         const u8        *(*add)(const struct lz4_hash_table, const u8 *);
  48         void            *ctx;
  49         const u8        *base;
  50 };
  51
  52 #if __SIZEOF_POINTER__ == 4
  53 static inline const u8 *hash_table_add32(const struct lz4_hash_table hash,
  54                                          const u8 *ip)
  55 {
  56         const u8 **table = hash.ctx;
  57
  58         swap(table[LZ4_HASH_VALUE(ip, table)], ip);
  59         return ip;
  60 }
  61 #else
  62 static inline const u8 *hash_table_add32(const struct lz4_hash_table hash,
  63                                          const u8 *ip)
  64 {
  65         u32 *table = hash.ctx;
  66         size_t offset = ip - hash.base;
  67
  68         swap(table[LZ4_HASH_VALUE(ip, table)], offset);
  69         return hash.base + offset;
  70 }
  71 #endif
  72
  73 static inline const u8 *hash_table_add16(const struct lz4_hash_table hash,
  74                                          const u8 *ip)
  75 {
  76         u16 *table = hash.ctx;
  77         size_t offset = ip - hash.base;
  78
  79         swap(table[LZ4_HASH_VALUE(ip, table)], offset);
  80         return hash.base + offset;
  81 }
  82
  83 static inline const u8 *find_match(const struct lz4_hash_table hash,
  84                                    const u8 **ip, const u8 *anchor,
  85                                    const u8 *start, const u8 *mflimit)
  86 {
  87         int findmatchattempts = (1U << SKIPSTRENGTH) + 3;
  88
  89         while (*ip <= mflimit) {
  90                 const u8 *ref = hash.add(hash, *ip);
  91
  92                 if (ref >= *ip - MAX_DISTANCE && A32(ref) == A32(*ip)) {
  93                         /* found match: */
  94                         while (*ip > anchor &&
  95                                ref > start &&
  96                                unlikely((*ip)[-1] == ref[-1])) {
  97                                 (*ip)--;
  98                                 ref--;
  99                         }
 100
 101                         return ref;
 102                 }
 103
 104                 *ip += findmatchattempts++ >> SKIPSTRENGTH;
 105         }
 106
 107         return NULL;
 108 }
 109
 110 static inline int length_len(unsigned length)
 111 {
 112         return length / 255 + 1;
 113 }
 114
 115 /*
 116  * LZ4_compressCtx :
 117  * -----------------
 118  * Compress 'isize' bytes from 'source' into an output buffer 'dest' of
 119  * maximum size 'maxOutputSize'.  * If it cannot achieve it, compression
 120  * will stop, and result of the function will be zero.
 121  * return : the number of bytes written in buffer 'dest', or 0 if the
 122  * compression fails
 123  */
 124 static inline int lz4_compressctx(const struct lz4_hash_table hash,
 125                                   const u8 *src, size_t src_len,
 126                                   u8 *dst, size_t *dst_len)
 127 {
 128         const u8 *ip = src, *anchor = ip, *ref;
 129         const u8 *const iend = ip + src_len;
 130         const u8 *const mflimit = iend - MFLIMIT;
 131         const u8 *const matchlimit = iend - LASTLITERALS;
 132         u8 *op = dst, *token;
 133         u8 *const oend = op + *dst_len;
 134         size_t literal_len, match_len, match_offset;
 135
 136         /* Init */
 137         memset(hash.ctx, 0, LZ4_MEM_COMPRESS);
 138         hash.add(hash, ip);
 139
 140         /* Always start with a literal: */
 141         ip++;
 142
 143         while ((ref = find_match(hash, &ip, anchor, src, mflimit))) {
 144                 /*
 145                  * We found a match; @ip now points to the match and @ref points
 146                  * to the prior part of the input we matched with. Everything up
 147                  * to @anchor has been encoded; the range from @anchor to @ip
 148                  * didn't match and now has to be encoded as a literal:
 149                  */
 150                 literal_len = ip - anchor;
 151                 match_offset = ip - ref;
 152
 153                 /* MINMATCH bytes already matched from find_match(): */
 154                 ip += MINMATCH;
 155                 ref += MINMATCH;
 156                 match_len = common_length(ip, ref, matchlimit);
 157                 ip += match_len;
 158
 159                 /* check output limit */
 160                 if (unlikely(op +
 161                              1 + /* token */
 162                              2 + /* match ofset */
 163                              literal_len +
 164                              length_len(literal_len) +
 165                              length_len(match_len) +
 166                              LASTLITERALS > oend))
 167                         break;
 168
 169                 token = op++;
 170                 *token = encode_length(&op, literal_len) << ML_BITS;
 171                 MEMCPY_ADVANCE_CHUNKED(op, anchor, literal_len);
 172                 PUT_LE16_ADVANCE(op, match_offset);
 173                 *token += encode_length(&op, match_len);
 174
 175                 anchor = ip;
 176         }
 177
 178         /* Encode remaining input as literal: */
 179         literal_len = iend - anchor;
 180         if (unlikely(op +
 181                      1 +
 182                      literal_len +
 183                      length_len(literal_len) > oend)) {
 184                 /* Return how much would be able to fit: */
 185                 ssize_t remaining = oend - op;
 186                 ssize_t encoded = anchor - src;
 187
 188                 remaining -= length_len(remaining) + 1;
 189
 190                 return -max(encoded + remaining, 1L);
 191         }
 192
 193         token = op++;
 194         *token = encode_length(&op, literal_len) << ML_BITS;
 195         MEMCPY_ADVANCE(op, anchor, literal_len);
 196
 197         /* End */
 198         BUG_ON(op > oend);
 199         *dst_len = op - dst;
 200         return 0;
 201 }
 202
 203 __attribute__((flatten))
 204 int lz4_compress(const unsigned char *src, size_t src_len,
 205                  unsigned char *dst, size_t *dst_len, void *wrkmem)
 206 {
 207         if (src_len < LZ4_64KLIMIT) {
 208                 const struct lz4_hash_table hash = {
 209                         .add    = hash_table_add16,
 210                         .ctx    = wrkmem,
 211                         .base   = src,
 212                 };
 213
 214                 return lz4_compressctx(hash, src, src_len, dst, dst_len);
 215         } else {
 216                 const struct lz4_hash_table hash = {
 217                         .add    = hash_table_add32,
 218                         .ctx    = wrkmem,
 219                         .base   = src,
 220                 };
 221
 222                 return lz4_compressctx(hash, src, src_len, dst, dst_len);
 223         }
 224 }