git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/lz4_decompress.c

   1 /*
   2  * LZ4 Decompressor for Linux kernel
   3  *
   4  * Copyright (C) 2013, LG Electronics, Kyungsik Lee <kyungsik.lee@lge.com>
   5  *
   6  * Based on LZ4 implementation by Yann Collet.
   7  *
   8  * LZ4 - Fast LZ compression algorithm
   9  * Copyright (C) 2011-2012, Yann Collet.
  10  * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
  11  *
  12  * Redistribution and use in source and binary forms, with or without
  13  * modification, are permitted provided that the following conditions are
  14  * met:
  15  *
  16  *     * Redistributions of source code must retain the above copyright
  17  * notice, this list of conditions and the following disclaimer.
  18  *     * Redistributions in binary form must reproduce the above
  19  * copyright notice, this list of conditions and the following disclaimer
  20  * in the documentation and/or other materials provided with the
  21  * distribution.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  29  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  30  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  31  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  32  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  33  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34  *
  35  *  You can contact the author at :
  36  *  - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html
  37  *  - LZ4 source repository : http://code.google.com/p/lz4/
  38  */
  39
  40 #ifndef STATIC
  41 #include <linux/module.h>
  42 #include <linux/kernel.h>
  43 #endif
  44
  45 #include "lz4.h"
  46
  47 /*
  48  * Detects 64 bits mode
  49  */
  50 #if defined(CONFIG_64BIT)
  51 #define LZ4_ARCH64 1
  52 #else
  53 #define LZ4_ARCH64 0
  54 #endif
  55
  56 #include <asm/unaligned.h>
  57 #include <linux/log2.h>
  58 #include <linux/string.h>
  59
  60 #define A32(_p) get_unaligned((u32 *) (_p))
  61 #define A16(_p) get_unaligned((u16 *) (_p))
  62
  63 #define GET_LE16_ADVANCE(_src)                          \
  64 ({                                                      \
  65         u16 _r = get_unaligned_le16(_src);              \
  66         (_src) += 2;                                    \
  67         _r;                                             \
  68 })
  69
  70 #define PUT_LE16_ADVANCE(_dst, _v)                      \
  71 do {                                                    \
  72         put_unaligned_le16((_v), (_dst));               \
  73         (_dst) += 2;                                    \
  74 } while (0)
  75
  76 #define LENGTH_LONG             15
  77 #define COPYLENGTH              8
  78 #define ML_BITS                 4
  79 #define ML_MASK                 ((1U << ML_BITS) - 1)
  80 #define RUN_BITS                (8 - ML_BITS)
  81 #define RUN_MASK                ((1U << RUN_BITS) - 1)
  82 #define MEMORY_USAGE            14
  83 #define MINMATCH                4
  84 #define SKIPSTRENGTH            6
  85 #define LASTLITERALS            5
  86 #define MFLIMIT                 (COPYLENGTH + MINMATCH)
  87 #define MINLENGTH               (MFLIMIT + 1)
  88 #define MAXD_LOG                16
  89 #define MAXD                    (1 << MAXD_LOG)
  90 #define MAXD_MASK               (u32)(MAXD - 1)
  91 #define MAX_DISTANCE            (MAXD - 1)
  92 #define HASH_LOG                (MAXD_LOG - 1)
  93 #define HASHTABLESIZE           (1 << HASH_LOG)
  94 #define MAX_NB_ATTEMPTS         256
  95 #define OPTIMAL_ML              (int)((ML_MASK-1)+MINMATCH)
  96 #define LZ4_64KLIMIT            ((1<<16) + (MFLIMIT - 1))
  97
  98 #define __HASH_VALUE(p, bits)                           \
  99         (((A32(p)) * 2654435761U) >> (32 - (bits)))
 100
 101 #define HASH_VALUE(p)           __HASH_VALUE(p, HASH_LOG)
 102
 103 #define MEMCPY_ADVANCE(_dst, _src, length)              \
 104 do {                                                    \
 105         typeof(length) _length = (length);              \
 106         memcpy(_dst, _src, _length);                    \
 107         _src += _length;                                \
 108         _dst += _length;                                \
 109 } while (0)
 110
 111 #define MEMCPY_ADVANCE_BYTES(_dst, _src, _length)       \
 112 do {                                                    \
 113         const u8 *_end = (_src) + (_length);            \
 114         while ((_src) < _end)                           \
 115                 *_dst++ = *_src++;                      \
 116 } while (0)
 117
 118 #define STEPSIZE                __SIZEOF_LONG__
 119
 120 #define LZ4_COPYPACKET(_src, _dst)                      \
 121 do {                                                    \
 122         MEMCPY_ADVANCE(_dst, _src, STEPSIZE);           \
 123         MEMCPY_ADVANCE(_dst, _src, COPYLENGTH - STEPSIZE);\
 124 } while (0)
 125
 126 /*
 127  * Equivalent to MEMCPY_ADVANCE - except may overrun @_dst and @_src by
 128  * COPYLENGTH:
 129  *
 130  * Note: src and dst may overlap (with src < dst) - we must do the copy in
 131  * STEPSIZE chunks for correctness
 132  *
 133  * Note also: length may be negative - we must not call memcpy if length is
 134  * negative, but still adjust dst and src by length
 135  */
 136 #define MEMCPY_ADVANCE_CHUNKED(_dst, _src, _length)     \
 137 do {                                                    \
 138         u8 *_end = (_dst) + (_length);                  \
 139         while ((_dst) < _end)                           \
 140                 LZ4_COPYPACKET(_src, _dst);             \
 141         _src -= (_dst) - _end;                          \
 142         _dst = _end;                                    \
 143 } while (0)
 144
 145 #define MEMCPY_ADVANCE_CHUNKED_NOFIXUP(_dst, _src, _end)\
 146 do {                                                    \
 147         while ((_dst) < (_end))                         \
 148                 LZ4_COPYPACKET((_src), (_dst));         \
 149 } while (0)
 150
 151 static const int dec32table[8] = {0, 3, 2, 3, 0, 0, 0, 0};
 152 #if LZ4_ARCH64
 153 static const int dec64table[8] = {0, 0, 0, -1, 0, 1, 2, 3};
 154 #else
 155 static const int dec64table[8] = {0, 0, 0, 0, 0, 0, 0, 0};
 156 #endif
 157
 158 static inline size_t get_length(const u8 **ip, size_t length)
 159 {
 160         if (length == LENGTH_LONG) {
 161                 size_t len;
 162
 163                 do {
 164                         length += (len = *(*ip)++);
 165                 } while (len == 255);
 166         }
 167
 168         return length;
 169 }
 170
 171 static int lz4_uncompress(const u8 *source, u8 *dest, int osize)
 172 {
 173         const u8 *ip = source;
 174         const u8 *ref;
 175         u8 *op = dest;
 176         u8 * const oend = op + osize;
 177         u8 *cpy;
 178         unsigned token, offset;
 179         ssize_t length;
 180
 181         while (1) {
 182                 /* get runlength */
 183                 token = *ip++;
 184                 length = get_length(&ip, token >> ML_BITS);
 185
 186                 /* copy literals */
 187                 if (unlikely(op + length > oend - COPYLENGTH)) {
 188                         /*
 189                          * Error: not enough place for another match
 190                          * (min 4) + 5 literals
 191                          */
 192                         if (op + length != oend)
 193                                 goto _output_error;
 194
 195                         MEMCPY_ADVANCE(op, ip, length);
 196                         break; /* EOF */
 197                 }
 198                 MEMCPY_ADVANCE_CHUNKED(op, ip, length);
 199
 200                 /* get match offset */
 201                 offset = GET_LE16_ADVANCE(ip);
 202                 ref = op - offset;
 203
 204                 /* Error: offset create reference outside destination buffer */
 205                 if (unlikely(ref < (u8 *const) dest))
 206                         goto _output_error;
 207
 208                 /* get match length */
 209                 length = get_length(&ip, token & ML_MASK);
 210                 length += MINMATCH;
 211
 212                 /* copy first STEPSIZE bytes of match: */
 213                 if (unlikely(offset < STEPSIZE)) {
 214                         MEMCPY_ADVANCE_BYTES(op, ref, 4);
 215                         ref -= dec32table[offset];
 216
 217                         memcpy(op, ref, 4);
 218                         op += STEPSIZE - 4;
 219                         ref -= dec64table[offset];
 220                 } else {
 221                         MEMCPY_ADVANCE(op, ref, STEPSIZE);
 222                 }
 223                 length -= STEPSIZE;
 224                 /*
 225                  * Note - length could have been < STEPSIZE; that's ok, length
 226                  * will now be negative and we'll just end up rewinding op:
 227                  */
 228
 229                 /* copy rest of match: */
 230                 cpy = op + length;
 231                 if (cpy > oend - COPYLENGTH) {
 232                         /* Error: request to write beyond destination buffer */
 233                         if (cpy              > oend ||
 234                             ref + COPYLENGTH > oend)
 235                                 goto _output_error;
 236 #if !LZ4_ARCH64
 237                         if (op  + COPYLENGTH > oend)
 238                                 goto _output_error;
 239 #endif
 240                         MEMCPY_ADVANCE_CHUNKED_NOFIXUP(op, ref, oend - COPYLENGTH);
 241                         /* op could be > cpy here */
 242                         while (op < cpy)
 243                                 *op++ = *ref++;
 244                         op = cpy;
 245                         /*
 246                          * Check EOF (should never happen, since last 5 bytes
 247                          * are supposed to be literals)
 248                          */
 249                         if (op == oend)
 250                                 goto _output_error;
 251                 } else {
 252                         MEMCPY_ADVANCE_CHUNKED(op, ref, length);
 253                 }
 254         }
 255         /* end of decoding */
 256         return ip - source;
 257
 258         /* write overflow error detected */
 259 _output_error:
 260         return -1;
 261 }
 262
 263 int bch2_lz4_decompress(const unsigned char *src, size_t *src_len,
 264                         unsigned char *dest, size_t actual_dest_len)
 265 {
 266         int ret = -1;
 267         int input_len = 0;
 268
 269         input_len = lz4_uncompress(src, dest, actual_dest_len);
 270         if (input_len < 0)
 271                 goto exit_0;
 272         *src_len = input_len;
 273
 274         return 0;
 275 exit_0:
 276         return ret;
 277 }