lkml.org 
[lkml]   [2012]   [Feb]   [13]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    SubjectRe: [PATCH 1/3] Add the snappy-c compressor to lib v2
    From
    On Thu, Jan 12, 2012 at 6:28 PM, Andi Kleen <andi@firstfloor.org> wrote:
    > From: Andi Kleen <ak@linux.intel.com>
    >
    > This is a C port of the google snappy compressor. It has roughly
    > comparable compression to LZO, but is significantly faster on many file
    > types. For example it beats all other compressors on already
    > compressed data.
    >
    > I ported the original C++ code over to C and did some changes
    > to make it better fit into the kernel. It preallocates the worst
    > case memory consumption now. While the code being larger
    > than lzo it is still reasonable (about 5K on x86).
    >
    > Decompression needs very little memory, Compression
    > currently 192K on 64bit and 128K on 32bit. For comparison
    > LZO compression needs 128K on 64bit and 64K on 32bit.
    >
    > [This could be lowered significantly by not preallocating
    > for most use cases, typically the footprint is much lower.
    > The original C++ version only allocated most of this
    > when (rarely) needed, but this is more problematic in the kernel]
    >
    > There are some minor divergences from the Linux coding standards:
    > in particular I kept the C++/C99 style mixed statement/declarations.
    > This was mainly to not diverge too much from the reference C++
    > source, so that improvements from there can be easily ported.
    > There are some other left overs from the google style, but very
    > little now.
    >
    > Performance:
    >
    > The compressor performs best on 64bit-LE systems,
    > but is also quite good on 32bit. I haven't tested BE, but
    > I don't expect that to add a lot of overhead.
    >
    > Here is some performance data (32bit, Nehalem):
    > c/b = cycles/byte; lower numbers are better.
    >
    > x86-64 executable: (compression minimally slower than qlz, but
    > much better at decompression, lzo is left in the dust):
    >
    > snappy: emacs-gtk: 11007968 b: ratio 0.38: comp 8.13 uncomp 2.65 c/b
    > lzo   : emacs-gtk: 11007968 b: ratio 0.33: comp 12.74 uncomp 4.70 c/b
    > zlib1 : emacs-gtk: 11007968 b: ratio 0.27: comp 49.96 uncomp 13.14 c/b
    > zlib3 : emacs-gtk: 11007968 b: ratio 0.26: comp 64.17 uncomp 12.33 c/b
    > lzf   : emacs-gtk: 11007968 b: ratio 0.37: comp 9.85 uncomp 4.33 c/b
    > qlz   : emacs-gtk: 11007968 b: ratio 0.34: comp 7.51 uncomp 6.28 c/b
    > fastlz: emacs-gtk: 11007968 b: ratio 0.37: comp 10.73 uncomp 4.97 c/b
    >
    > Compressed data (beats everything else):
    >
    > snappy: udev-151.tar.gz: 634842 b: ratio 1.00: comp 0.99 uncomp 0.33 c/b
    > lzo   : udev-151.tar.gz: 634842 b: ratio 1.00: comp 41.44 uncomp 0.66 c/b
    > zlib1 : udev-151.tar.gz: 634842 b: ratio 1.00: comp 116.99 uncomp 3.94 c/b
    > zlib3 : udev-151.tar.gz: 634842 b: ratio 1.00: comp 117.68 uncomp 3.94 c/b
    > lzf   : udev-151.tar.gz: 634842 b: ratio 1.03: comp 16.32 uncomp 1.14 c/b
    > qlz   : udev-151.tar.gz: 634842 b: ratio 1.00: comp 10.42 uncomp 0.42 c/b
    > fastlz: udev-151.tar.gz: 634842 b: ratio 1.03: comp 19.35 uncomp 2.07 c/b
    >
    > Text file (compression somewhat slower than qlz, but decompression
    > much better, lzo is much worse):
    >
    > snappy: manual.txt: 445343 b: ratio 0.47: comp 12.01 uncomp 3.12 c/b
    > lzo   : manual.txt: 445343 b: ratio 0.44: comp 16.32 uncomp 7.53 c/b
    > zlib1 : manual.txt: 445343 b: ratio 0.35: comp 56.37 uncomp 15.59 c/b
    > zlib3 : manual.txt: 445343 b: ratio 0.31: comp 73.45 uncomp 13.99 c/b
    > lzf   : manual.txt: 445343 b: ratio 0.46: comp 13.43 uncomp 5.47 c/b
    > qlz   : manual.txt: 445343 b: ratio 0.44: comp 9.16 uncomp 8.19 c/b
    > fastlz: manual.txt: 445343 b: ratio 0.46: comp 14.22 uncomp 7.28 c/b
    >
    > As you can see snappy is a good all-around compressor.
    >
    > On 64bit the compression is even faster and beats everything else easily:
    >
    > snappy: emacs-gtk: 11007968 b: ratio 0.38: comp 4.90 uncomp 2.65 c/b
    > lzo   : emacs-gtk: 11007968 b: ratio 0.33: comp 11.24 uncomp 4.46 c/b
    > zlib1 : emacs-gtk: 11007968 b: ratio 0.27: comp 41.67 uncomp 11.13 c/b
    > zlib3 : emacs-gtk: 11007968 b: ratio 0.26: comp 51.80 uncomp 10.54 c/b
    > lzf   : emacs-gtk: 11007968 b: ratio 0.37: comp 8.79 uncomp 4.05 c/b
    > qlz   : emacs-gtk: 11007968 b: ratio 0.34: comp 5.44 uncomp 5.46 c/b
    > fastlz: emacs-gtk: 11007968 b: ratio 0.37: comp 9.91 uncomp 4.77 c/b
    >
    > On 64bit it's now nearly as fast as qlz on the text file too:
    >
    > snappy: manual.txt: 445343 b: ratio 0.47: comp 7.79 uncomp 3.47 c/b
    > lzo   : manual.txt: 445343 b: ratio 0.44: comp 15.46 uncomp 7.27 c/b
    > zlib1 : manual.txt: 445343 b: ratio 0.35: comp 45.79 uncomp 12.78 c/b
    > zlib3 : manual.txt: 445343 b: ratio 0.31: comp 60.52 uncomp 11.72 c/b
    > lzf   : manual.txt: 445343 b: ratio 0.46: comp 12.62 uncomp 5.30 c/b
    > qlz   : manual.txt: 445343 b: ratio 0.44: comp 6.81 uncomp 7.65 c/b
    > fastlz: manual.txt: 445343 b: ratio 0.46: comp 13.75 uncomp 6.52 c/b
    >
    > Overall it's a good alternative to lzo, with the only
    > drawback being the somewhat higher memory use.
    >
    > v2: Some minor performance improvements and cleanups.
    > 32bit compression should be a few percent faster now.
    > Signed-off-by: Andi Kleen <ak@linux.intel.com>
    > ---
    >  include/linux/snappy.h |   26 +
    >  lib/Kconfig            |    6 +
    >  lib/Makefile           |    4 +
    >  lib/snappy.c           | 1300 ++++++++++++++++++++++++++++++++++++++++++++++++
    >  4 files changed, 1336 insertions(+), 0 deletions(-)
    >  create mode 100644 include/linux/snappy.h
    >  create mode 100644 lib/snappy.c
    >
    > diff --git a/include/linux/snappy.h b/include/linux/snappy.h
    > new file mode 100644
    > index 0000000..4119803
    > --- /dev/null
    > +++ b/include/linux/snappy.h
    > @@ -0,0 +1,26 @@
    > +#ifndef _LINUX_SNAPPY_H
    > +#define _LINUX_SNAPPY_H 1
    > +
    > +#include <linux/types.h>
    > +
    > +/* Only needed for compression. This preallocates the worst case */
    > +struct snappy_env {
    > +       u16 *hash_table;
    > +       void *scratch;
    > +       void *scratch_output;
    > +};
    > +
    > +int snappy_init_env(struct snappy_env *env);
    > +void snappy_free_env(struct snappy_env *env);
    > +bool snappy_uncompress(const char *compressed, size_t n, char *uncompressed);
    > +int snappy_compress(struct snappy_env *env,
    > +                   const char *input,
    > +                   size_t input_length,
    > +                   char *compressed,
    > +                   size_t *compressed_length);
    > +bool snappy_uncompressed_length(const char *buf, size_t len, size_t *result);
    > +size_t snappy_max_compressed_length(size_t source_len);
    > +
    > +
    > +
    > +#endif
    > diff --git a/lib/Kconfig b/lib/Kconfig
    > index 201e1b3..719e4f2 100644
    > --- a/lib/Kconfig
    > +++ b/lib/Kconfig
    > @@ -310,4 +310,10 @@ config DIGSIG
    >          Digital signature verification. Currently only RSA is supported.
    >          Implementation is done using GnuPG MPI library
    >
    > +config SNAPPY
    > +       tristate "Snappy compressor"
    > +       help
    > +          Add the snappy compressor. This is a reasonable compressor that
    > +         compresses and decompresses extremly fast.
    > +
    >  endmenu
    > diff --git a/lib/Makefile b/lib/Makefile
    > index dace162..2f5f86a 100644
    > --- a/lib/Makefile
    > +++ b/lib/Makefile
    > @@ -121,6 +121,10 @@ obj-$(CONFIG_DQL) += dynamic_queue_limits.o
    >  obj-$(CONFIG_MPILIB) += mpi/
    >  obj-$(CONFIG_DIGSIG) += digsig.o
    >
    > +CFLAGS_snappy.o += $(call cc-disable-warning, declaration-after-statement) \
    > +                  -DNDEBUG=1
    > +obj-$(CONFIG_SNAPPY) += snappy.o
    > +
    >  hostprogs-y    := gen_crc32table
    >  clean-files    := crc32table.h
    >
    > diff --git a/lib/snappy.c b/lib/snappy.c
    > new file mode 100644
    > index 0000000..0b39e07
    > --- /dev/null
    > +++ b/lib/snappy.c
    > @@ -0,0 +1,1300 @@
    > +/*
    > + * C port of the snappy compressor from Google.
    > + * This is a very fast compressor with comparable compression to lzo.
    > + * Works best on 64bit little-endian, but should be good on others too.
    > + * Ported by Andi Kleen.
    > + * Based on snappy 1.0.3 plus some selected changes from SVN.
    > + */
    > +
    > +/*
    > + * Copyright 2005 Google Inc. All Rights Reserved.
    > + *
    > + * Redistribution and use in source and binary forms, with or without
    > + * modification, are permitted provided that the following conditions are
    > + * met:
    > + *
    > + *     * Redistributions of source code must retain the above copyright
    > + * notice, this list of conditions and the following disclaimer.
    > + *     * Redistributions in binary form must reproduce the above
    > + * copyright notice, this list of conditions and the following disclaimer
    > + * in the documentation and/or other materials provided with the
    > + * distribution.
    > + *     * Neither the name of Google Inc. nor the names of its
    > + * contributors may be used to endorse or promote products derived from
    > + * this software without specific prior written permission.
    > + *
    > + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
    > + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
    > + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
    > + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
    > + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    > + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
    > + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    > + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
    > + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    > + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
    > + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    > + */
    > +
    > +#include <linux/kernel.h>
    > +#include <linux/module.h>
    > +#include <linux/slab.h>
    > +#include <linux/string.h>
    > +#include <linux/snappy.h>
    > +#include <asm/unaligned.h>
    > +
    > +#define CRASH_UNLESS(x) BUG_ON(!(x))
    > +#define CHECK(cond) CRASH_UNLESS(cond)
    > +#define CHECK_LE(a, b) CRASH_UNLESS((a) <= (b))
    > +#define CHECK_GE(a, b) CRASH_UNLESS((a) >= (b))
    > +#define CHECK_EQ(a, b) CRASH_UNLESS((a) == (b))
    > +#define CHECK_NE(a, b) CRASH_UNLESS((a) != (b))
    > +#define CHECK_LT(a, b) CRASH_UNLESS((a) < (b))
    > +#define CHECK_GT(a, b) CRASH_UNLESS((a) > (b))
    > +
    > +#define UNALIGNED_LOAD16(_p) get_unaligned((u16 *)(_p))
    > +#define UNALIGNED_LOAD32(_p) get_unaligned((u32 *)(_p))
    > +#define UNALIGNED_LOAD64(_p) get_unaligned((u64 *)(_p))
    > +
    > +#define UNALIGNED_STORE16(_p, _val) put_unaligned(_val, (u16 *)(_p))
    > +#define UNALIGNED_STORE32(_p, _val) put_unaligned(_val, (u32 *)(_p))
    > +#define UNALIGNED_STORE64(_p, _val) put_unaligned(_val, (u64 *)(_p))
    > +
    > +#ifdef NDEBUG
    > +
    > +#define DCHECK(cond) do {} while(0)
    > +#define DCHECK_LE(a, b) do {} while(0)
    > +#define DCHECK_GE(a, b) do {} while(0)
    > +#define DCHECK_EQ(a, b) do {} while(0)
    > +#define DCHECK_NE(a, b) do {} while(0)
    > +#define DCHECK_LT(a, b) do {} while(0)
    > +#define DCHECK_GT(a, b) do {} while(0)
    > +
    > +#else
    > +
    > +#define DCHECK(cond) CHECK(cond)
    > +#define DCHECK_LE(a, b) CHECK_LE(a, b)
    > +#define DCHECK_GE(a, b) CHECK_GE(a, b)
    > +#define DCHECK_EQ(a, b) CHECK_EQ(a, b)
    > +#define DCHECK_NE(a, b) CHECK_NE(a, b)
    > +#define DCHECK_LT(a, b) CHECK_LT(a, b)
    > +#define DCHECK_GT(a, b) CHECK_GT(a, b)
    > +
    > +#endif
    > +
    > +static inline bool is_little_endian(void)
    > +{
    > +#ifdef __LITTLE_ENDIAN__
    > +       return true;
    > +#endif
    > +       return false;
    > +}
    > +
    > +static inline int log2_floor(u32 n)
    > +{
    > +       return n == 0 ? -1 : 31 ^ __builtin_clz(n);
    > +}
    > +
    > +static inline int find_lsb_set_non_zero(u32 n)
    > +{
    > +       return __builtin_ctz(n);
    > +}
    > +
    > +static inline int find_lsb_set_non_zero64(u64 n)
    > +{
    > +       if (sizeof(long) == 4) {
    > +               if (n & 0xffffffff)
    > +                       return __builtin_ctz(n & 0xffffffff);
    > +               return 32 + __builtin_ctz(n >> 32);
    > +       }
    > +       return __builtin_ctzll(n);
    > +}
    > +
    > +#define kmax32 5
    > +
    > +/*
    > + * Attempts to parse a varint32 from a prefix of the bytes in [ptr,limit-1].
    > + *  Never reads a character at or beyond limit.  If a valid/terminated varint32
    > + * was found in the range, stores it in *OUTPUT and returns a pointer just
    > + * past the last byte of the varint32. Else returns NULL.  On success,
    > + * "result <= limit".
    > + */
    > +static inline const char *varint_parse32_with_limit(const char *p,
    > +                                                   const char *l,
    > +                                                   u32 * OUTPUT)
    > +{
    > +       const unsigned char *ptr = (const unsigned char *)(p);
    > +       const unsigned char *limit = (const unsigned char *)(l);
    > +       u32 b, result;
    > +
    > +       if (ptr >= limit)
    > +               return NULL;
    > +       b = *(ptr++);
    > +       result = b & 127;
    > +       if (b < 128)
    > +               goto done;
    > +       if (ptr >= limit)
    > +               return NULL;
    > +       b = *(ptr++);
    > +       result |= (b & 127) << 7;
    > +       if (b < 128)
    > +               goto done;
    > +       if (ptr >= limit)
    > +               return NULL;
    > +       b = *(ptr++);
    > +       result |= (b & 127) << 14;
    > +       if (b < 128)
    > +               goto done;
    > +       if (ptr >= limit)
    > +               return NULL;
    > +       b = *(ptr++);
    > +       result |= (b & 127) << 21;
    > +       if (b < 128)
    > +               goto done;
    > +       if (ptr >= limit)
    > +               return NULL;
    > +       b = *(ptr++);
    > +       result |= (b & 127) << 28;
    > +       if (b < 16)
    > +               goto done;
    > +       return NULL;            /* Value is too long to be a varint32 */
    > +done:
    > +       *OUTPUT = result;
    > +       return (const char *)(ptr);
    > +}
    > +
    > +/*
    > + * REQUIRES   "ptr" points to a buffer of length sufficient to hold "v".
    > + *  EFFECTS    Encodes "v" into "ptr" and returns a pointer to the
    > + *            byte just past the last encoded byte.
    > + */
    > +static inline char *varint_encode32(char *sptr, u32 v)
    > +{
    > +       /* Operate on characters as unsigneds */
    > +       unsigned char *ptr = (unsigned char *)(sptr);
    > +       static const int B = 128;
    > +
    > +       if (v < (1 << 7)) {
    > +               *(ptr++) = v;
    > +       } else if (v < (1 << 14)) {
    > +               *(ptr++) = v | B;
    > +               *(ptr++) = v >> 7;
    > +       } else if (v < (1 << 21)) {
    > +               *(ptr++) = v | B;
    > +               *(ptr++) = (v >> 7) | B;
    > +               *(ptr++) = v >> 14;
    > +       } else if (v < (1 << 28)) {
    > +               *(ptr++) = v | B;
    > +               *(ptr++) = (v >> 7) | B;
    > +               *(ptr++) = (v >> 14) | B;
    > +               *(ptr++) = v >> 21;
    > +       } else {
    > +               *(ptr++) = v | B;
    > +               *(ptr++) = (v >> 7) | B;
    > +               *(ptr++) = (v >> 14) | B;
    > +               *(ptr++) = (v >> 21) | B;
    > +               *(ptr++) = v >> 28;
    > +       }
    > +       return (char *)(ptr);
    > +}
    > +
    > +struct source {
    > +       const char *ptr;
    > +       size_t left;
    > +};
    > +
    > +static inline int available(struct source *s)
    > +{
    > +       return s->left;
    > +}
    > +
    > +static inline const char *peek(struct source *s, size_t * len)
    > +{
    > +       *len = s->left;
    > +       return s->ptr;
    > +}
    > +
    > +static inline void skip(struct source *s, size_t n)
    > +{
    > +       s->left -= n;
    > +       s->ptr += n;
    > +}
    > +
    > +struct sink {
    > +       char *dest;
    > +};
    > +
    > +static inline void append(struct sink *s, const char *data, size_t n)
    > +{
    > +       if (data != s->dest)
    > +               memcpy(s->dest, data, n);
    > +       s->dest += n;
    > +}
    > +
    > +static inline void *sink_peek(struct sink *s, size_t n)
    > +{
    > +       return s->dest;
    > +}
    > +
    > +struct writer {
    > +       char *base;
    > +       char *op;
    > +       char *op_limit;
    > +};
    > +
    > +/* Called before decompression */
    > +static inline void writer_set_expected_length(struct writer *w, size_t len)
    > +{
    > +       w->op_limit = w->op + len;
    > +}
    > +
    > +/* Called after decompression */
    > +static inline bool writer_check_length(struct writer *w)
    > +{
    > +       return w->op == w->op_limit;
    > +}
    > +
    > +/*
    > + * Copy "len" bytes from "src" to "op", one byte at a time.  Used for
    > + *  handling COPY operations where the input and output regions may
    > + * overlap.  For example, suppose:
    > + *    src    == "ab"
    > + *    op     == src + 2
    > + *    len    == 20
    > + * After IncrementalCopy(src, op, len), the result will have
    > + * eleven copies of "ab"
    > + *    ababababababababababab
    > + * Note that this does not match the semantics of either memcpy()
    > + * or memmove().
    > + */
    > +static inline void incremental_copy(const char *src, char *op, int len)
    > +{
    > +       DCHECK_GT(len, 0);
    > +       do {
    > +               *op++ = *src++;
    > +       } while (--len > 0);
    > +}
    > +
    > +/*
    > + * Equivalent to IncrementalCopy except that it can write up to ten extra
    > + *  bytes after the end of the copy, and that it is faster.
    > + *
    > + * The main part of this loop is a simple copy of eight bytes at a time until
    > + * we've copied (at least) the requested amount of bytes.  However, if op and
    > + * src are less than eight bytes apart (indicating a repeating pattern of
    > + * length < 8), we first need to expand the pattern in order to get the correct
    > + * results. For instance, if the buffer looks like this, with the eight-byte
    > + * <src> and <op> patterns marked as intervals:
    > + *
    > + *    abxxxxxxxxxxxx
    > + *    [------]           src
    > + *      [------]         op
    > + *
    > + * a single eight-byte copy from <src> to <op> will repeat the pattern once,
    > + * after which we can move <op> two bytes without moving <src>:
    > + *
    > + *    ababxxxxxxxxxx
    > + *    [------]           src
    > + *        [------]       op
    > + *
    > + * and repeat the exercise until the two no longer overlap.
    > + *
    > + * This allows us to do very well in the special case of one single byte
    > + * repeated many times, without taking a big hit for more general cases.
    > + *
    > + * The worst case of extra writing past the end of the match occurs when
    > + * op - src == 1 and len == 1; the last copy will read from byte positions
    > + * [0..7] and write to [4..11], whereas it was only supposed to write to
    > + * position 1. Thus, ten excess bytes.
    > + */
    > +
    > +#define kmax_increment_copy_overflow  10
    > +
    > +static inline void incremental_copy_fast_path(const char *src, char *op,
    > +                                             int len)
    > +{
    > +       while (op - src < 8) {
    > +               UNALIGNED_STORE64(op, UNALIGNED_LOAD64(src));
    > +               len -= op - src;
    > +               op += op - src;
    > +       }
    > +       while (len > 0) {
    > +               UNALIGNED_STORE64(op, UNALIGNED_LOAD64(src));
    > +               src += 8;
    > +               op += 8;
    > +               len -= 8;
    > +       }
    > +}
    > +
    > +static inline bool writer_append_from_self(struct writer *w, u32 offset,
    > +                                          u32 len)
    > +{
    > +       char *op = w->op;
    > +       const int space_left = w->op_limit - op;
    > +
    > +       if (op - w->base <= offset - 1u)        /* -1u catches offset==0 */
    > +               return false;
    > +       if (len <= 16 && offset >= 8 && space_left >= 16) {
    > +               /* Fast path, used for the majority (70-80%) of dynamic
    > +                * invocations. */
    > +               UNALIGNED_STORE64(op, UNALIGNED_LOAD64(op - offset));
    > +               UNALIGNED_STORE64(op + 8, UNALIGNED_LOAD64(op - offset + 8));
    > +       } else {
    > +               if (space_left >= len + kmax_increment_copy_overflow) {
    > +                       incremental_copy_fast_path(op - offset, op, len);
    > +               } else {
    > +                       if (space_left < len) {
    > +                               return false;
    > +                       }
    > +                       incremental_copy(op - offset, op, len);
    > +               }
    > +       }
    > +
    > +       w->op = op + len;
    > +       return true;
    > +}
    > +
    > +static inline bool writer_append(struct writer *w, const char *ip, u32 len,
    > +                                bool allow_fast_path)
    > +{
    > +       char *op = w->op;
    > +       const int space_left = w->op_limit - op;
    > +       if (allow_fast_path && len <= 16 && space_left >= 16) {
    > +               /* Fast path, used for the majority (about 90%) of dynamic
    > +                * invocations. */
    > +               UNALIGNED_STORE64(op, UNALIGNED_LOAD64(ip));
    > +               UNALIGNED_STORE64(op + 8, UNALIGNED_LOAD64(ip + 8));
    > +       } else {
    > +               if (space_left < len)
    > +                       return false;
    > +               memcpy(op, ip, len);
    > +       }
    > +       w->op = op + len;
    > +       return true;
    > +}
    > +
    > +/*
    > + * Any hash function will produce a valid compressed bitstream, but a good
    > + * hash function reduces the number of collisions and thus yields better
    > + * compression for compressible input, and more speed for incompressible
    > + * input. Of course, it doesn't hurt if the hash function is reasonably fast
    > + * either, as it gets called a lot.
    > + */
    > +static inline u32 hash_bytes(u32 bytes, int shift)
    > +{
    > +       u32 kmul = 0x1e35a7bd;
    > +       return (bytes * kmul) >> shift;
    > +}
    > +
    > +static inline u32 hash(const char *p, int shift)
    > +{
    > +       return hash_bytes(UNALIGNED_LOAD32(p), shift);
    > +}
    > +
    > +/*
    > + * Compressed data can be defined as:
    > + *    compressed := item* literal*
    > + *    item       := literal* copy
    > + *
    > + * The trailing literal sequence has a space blowup of at most 62/60
    > + * since a literal of length 60 needs one tag byte + one extra byte
    > + * for length information.
    > + *
    > + * Item blowup is trickier to measure.  Suppose the "copy" op copies
    > + * 4 bytes of data.  Because of a special check in the encoding code,
    > + * we produce a 4-byte copy only if the offset is < 65536.  Therefore
    > + * the copy op takes 3 bytes to encode, and this type of item leads
    > + * to at most the 62/60 blowup for representing literals.
    > + *
    > + * Suppose the "copy" op copies 5 bytes of data.  If the offset is big
    > + * enough, it will take 5 bytes to encode the copy op.  Therefore the
    > + * worst case here is a one-byte literal followed by a five-byte copy.
    > + * I.e., 6 bytes of input turn into 7 bytes of "compressed" data.
    > + *
    > + * This last factor dominates the blowup, so the final estimate is:
    > + */
    > +size_t snappy_max_compressed_length(size_t source_len)
    > +{
    > +       return 32 + source_len + source_len / 6;
    > +}
    > +EXPORT_SYMBOL(snappy_max_compressed_length);
    > +
    > +enum {
    > +       LITERAL = 0,
    > +       COPY_1_BYTE_OFFSET = 1, /* 3 bit length + 3 bits of offset in opcode */
    > +       COPY_2_BYTE_OFFSET = 2,
    > +       COPY_4_BYTE_OFFSET = 3
    > +};
    > +
    > +static inline char *emit_literal(char *op,
    > +                                const char *literal,
    > +                                int len, bool allow_fast_path)
    > +{
    > +       int n = len - 1;        /* Zero-length literals are disallowed */
    > +
    > +       if (n < 60) {
    > +               /* Fits in tag byte */
    > +               *op++ = LITERAL | (n << 2);
    > +
    > +/*
    > + * The vast majority of copies are below 16 bytes, for which a
    > + * call to memcpy is overkill. This fast path can sometimes
    > + * copy up to 15 bytes too much, but that is okay in the
    > + * main loop, since we have a bit to go on for both sides:
    > + *
    > + *   - The input will always have kInputMarginBytes = 15 extra
    > + *     available bytes, as long as we're in the main loop, and
    > + *     if not, allow_fast_path = false.
    > + *   - The output will always have 32 spare bytes (see
    > + *     MaxCompressedLength).
    > + */
    > +               if (allow_fast_path && len <= 16) {
    > +                       UNALIGNED_STORE64(op, UNALIGNED_LOAD64(literal));
    > +                       UNALIGNED_STORE64(op + 8,
    > +                                         UNALIGNED_LOAD64(literal + 8));
    > +                       return op + len;
    > +               }
    > +       } else {
    > +               /* Encode in upcoming bytes */
    > +               char *base = op;
    > +               int count = 0;
    > +               op++;
    > +               while (n > 0) {
    > +                       *op++ = n & 0xff;
    > +                       n >>= 8;
    > +                       count++;
    > +               }
    > +               DCHECK(count >= 1);
    > +               DCHECK(count <= 4);
    > +               *base = LITERAL | ((59 + count) << 2);
    > +       }
    > +       memcpy(op, literal, len);
    > +       return op + len;
    > +}
    > +
    > +static inline char *emit_copy_less_than64(char *op, int offset, int len)
    > +{
    > +       DCHECK_LE(len, 64);
    > +       DCHECK_GE(len, 4);
    > +       DCHECK_LT(offset, 65536);
    > +
    > +       if ((len < 12) && (offset < 2048)) {
    > +               int len_minus_4 = len - 4;
    > +               DCHECK(len_minus_4 < 8);        /* Must fit in 3 bits */
    > +               *op++ =
    > +                   COPY_1_BYTE_OFFSET | ((len_minus_4) << 2) | ((offset >> 8)
    > +                                                                << 5);
    > +               *op++ = offset & 0xff;
    > +       } else {
    > +               *op++ = COPY_2_BYTE_OFFSET | ((len - 1) << 2);
    > +               put_unaligned_le16(offset, op);
    > +               op += 2;
    > +       }
    > +       return op;
    > +}
    > +
    > +static inline char *emit_copy(char *op, int offset, int len)
    > +{
    > +       /*
    > +        * Emit 64 byte copies but make sure to keep at least four bytes
    > +        * reserved
    > +        */
    > +       while (len >= 68) {
    > +               op = emit_copy_less_than64(op, offset, 64);
    > +               len -= 64;
    > +       }
    > +
    > +       /*
    > +        * Emit an extra 60 byte copy if have too much data to fit in
    > +        * one copy
    > +        */
    > +       if (len > 64) {
    > +               op = emit_copy_less_than64(op, offset, 60);
    > +               len -= 60;
    > +       }
    > +
    > +       /* Emit remainder */
    > +       op = emit_copy_less_than64(op, offset, len);
    > +       return op;
    > +}
    > +
    > +/**
    > + * snappy_uncompressed_length - return length of uncompressed output.
    > + * @start: compressed buffer
    > + * @n: length of compressed buffer.
    > + * @result: Write the length of the uncompressed output here.
    > + *
    > + * Returns true when successfull, otherwise false.
    > + */
    > +bool snappy_uncompressed_length(const char *start, size_t n, size_t * result)
    > +{
    > +       u32 v = 0;
    > +       const char *limit = start + n;
    > +       if (varint_parse32_with_limit(start, limit, &v) != NULL) {
    > +               *result = v;
    > +               return true;
    > +       } else {
    > +               return false;
    > +       }
    > +}
    > +EXPORT_SYMBOL(snappy_uncompressed_length);
    > +
    > +#define kblock_log 15
    > +#define kblock_size (1 << kblock_log)
    > +
    > +#define kmax_hash_table_bits 14
    > +#define kmax_hash_table_size (1 << kmax_hash_table_bits)
    > +
    > +/*
    > + * Use smaller hash table when input.size() is smaller, since we
    > + * fill the table, incurring O(hash table size) overhead for
    > + * compression, and if the input is short, we won't need that
    > + * many hash table entries anyway.
    > + */
    > +static u16 *get_hash_table(struct snappy_env *env, size_t input_size,
    > +                             int *table_size)
    > +{
    > +       int htsize = 256;
    > +
    > +       DCHECK(kmax_hash_table_size >= 256);
    > +       while (htsize < kmax_hash_table_size && htsize < input_size)
    > +               htsize <<= 1;
    > +       CHECK_EQ(0, htsize & (htsize - 1));
    > +       CHECK_LE(htsize, kmax_hash_table_size);
    > +
    > +       u16 *table;
    > +       table = env->hash_table;
    > +
    > +       *table_size = htsize;
    > +       memset(table, 0, htsize * sizeof(*table));
    > +       return table;
    > +}
    > +
    > +/*
    > + * Return the largest n such that
    > + *
    > + *   s1[0,n-1] == s2[0,n-1]
    > + *   and n <= (s2_limit - s2).
    > + *
    > + * Does not read *s2_limit or beyond.
    > + * Does not read *(s1 + (s2_limit - s2)) or beyond.
    > + * Requires that s2_limit >= s2.
    > + *
    > + * Separate implementation for x86_64, for speed.  Uses the fact that
    > + * x86_64 is little endian.
    > + */
    > +#if defined(__LITTLE_ENDIAN__)
    > +static inline int find_match_length(const char *s1,
    > +                                   const char *s2, const char *s2_limit)
    > +{
    > +       int matched = 0;
    > +
    > +       DCHECK_GE(s2_limit, s2);
    > +       /*
    > +        * Find out how long the match is. We loop over the data 64 bits at a
    > +        * time until we find a 64-bit block that doesn't match; then we find
    > +        * the first non-matching bit and use that to calculate the total
    > +        * length of the match.
    > +        */
    > +       while (likely(s2 <= s2_limit - 8)) {
    > +               if (unlikely
    > +                   (UNALIGNED_LOAD64(s2) == UNALIGNED_LOAD64(s1 + matched))) {
    > +                       s2 += 8;
    > +                       matched += 8;
    > +               } else {
    > +                       /*
    > +                        * On current (mid-2008) Opteron models there
    > +                        * is a 3% more efficient code sequence to
    > +                        * find the first non-matching byte.  However,
    > +                        * what follows is ~10% better on Intel Core 2
    > +                        * and newer, and we expect AMD's bsf
    > +                        * instruction to improve.
    > +                        */
    > +                       u64 x =
    > +                           UNALIGNED_LOAD64(s2) ^ UNALIGNED_LOAD64(s1 +
    > +                                                                   matched);
    > +                       int matching_bits = find_lsb_set_non_zero64(x);
    > +                       matched += matching_bits >> 3;
    > +                       return matched;
    > +               }
    > +       }
    > +       while (likely(s2 < s2_limit)) {
    > +               if (likely(s1[matched] == *s2)) {
    > +                       ++s2;
    > +                       ++matched;
    > +               } else {
    > +                       return matched;
    > +               }
    > +       }
    > +       return matched;
    > +}
    > +#else
    > +static inline int find_match_length(const char *s1,
    > +                                   const char *s2, const char *s2_limit)
    > +{
    > +       /* Implementation based on the x86-64 version, above. */
    > +       DCHECK_GE(s2_limit, s2);
    > +       int matched = 0;
    > +
    > +       while (s2 <= s2_limit - 4 &&
    > +              UNALIGNED_LOAD32(s2) == UNALIGNED_LOAD32(s1 + matched)) {
    > +               s2 += 4;
    > +               matched += 4;
    > +       }
    > +       if (is_little_endian() && s2 <= s2_limit - 4) {
    > +               u32 x =
    > +                   UNALIGNED_LOAD32(s2) ^ UNALIGNED_LOAD32(s1 + matched);
    > +               int matching_bits = find_lsb_set_non_zero(x);
    > +               matched += matching_bits >> 3;
    > +       } else {
    > +               while ((s2 < s2_limit) && (s1[matched] == *s2)) {
    > +                       ++s2;
    > +                       ++matched;
    > +               }
    > +       }
    > +       return matched;
    > +}
    > +#endif
    > +
    > +/*
    > + * For 0 <= offset <= 4, GetU32AtOffset(UNALIGNED_LOAD64(p), offset) will
    > + *  equal UNALIGNED_LOAD32(p + offset).  Motivation: On x86-64 hardware we have
    > + * empirically found that overlapping loads such as
    > + *  UNALIGNED_LOAD32(p) ... UNALIGNED_LOAD32(p+1) ... UNALIGNED_LOAD32(p+2)
    > + * are slower than UNALIGNED_LOAD64(p) followed by shifts and casts to u32.
    > + */
    > +static inline u32 get_u32_at_offset(u64 v, int offset)
    > +{
    > +       DCHECK(0 <= offset && offset <= 4);
    > +       return v >> (is_little_endian()? 8 * offset : 32 - 8 * offset);
    > +}
    > +
    > +/*
    > + * Flat array compression that does not emit the "uncompressed length"
    > + *  prefix. Compresses "input" string to the "*op" buffer.
    > + *
    > + * REQUIRES: "input" is at most "kBlockSize" bytes long.
    > + * REQUIRES: "op" points to an array of memory that is at least
    > + * "MaxCompressedLength(input.size())" in size.
    > + * REQUIRES: All elements in "table[0..table_size-1]" are initialized to zero.
    > + * REQUIRES: "table_size" is a power of two
    > + *
    > + * Returns an "end" pointer into "op" buffer.
    > + * "end - op" is the compressed size of "input".
    > + */
    > +
    > +static char *compress_fragment(const char *const input,
    > +                              const size_t input_size,
    > +                              char *op, u16 * table, const int table_size)
    > +{
    > +       /* "ip" is the input pointer, and "op" is the output pointer. */
    > +       const char *ip = input;
    > +       CHECK_LE(input_size, kblock_size);
    > +       CHECK_EQ(table_size & (table_size - 1), 0);
    > +       const int shift = 32 - log2_floor(table_size);
    > +       DCHECK_EQ(UINT_MAX >> shift, table_size - 1);
    > +       const char *ip_end = input + input_size;
    > +       const char *baseip = ip;
    > +       /*
    > +        * Bytes in [next_emit, ip) will be emitted as literal bytes.  Or
    > +        *  [next_emit, ip_end) after the main loop.
    > +        */
    > +       const char *next_emit = ip;
    > +
    > +       const int kinput_margin_bytes = 15;
    > +
    > +       if (likely(input_size >= kinput_margin_bytes)) {
    > +               const char *ip_limit = input + input_size -
    > +                       kinput_margin_bytes;
    > +
    > +               u32 next_hash;
    > +               for (next_hash = hash(++ip, shift);;) {
    > +                       DCHECK_LT(next_emit, ip);
    > +/*
    > + * The body of this loop calls EmitLiteral once and then EmitCopy one or
    > + * more times.  (The exception is that when we're close to exhausting
    > + * the input we goto emit_remainder.)
    > + *
    > + * In the first iteration of this loop we're just starting, so
    > + * there's nothing to copy, so calling EmitLiteral once is
    > + * necessary.  And we only start a new iteration when the
    > + * current iteration has determined that a call to EmitLiteral will
    > + * precede the next call to EmitCopy (if any).
    > + *
    > + * Step 1: Scan forward in the input looking for a 4-byte-long match.
    > + * If we get close to exhausting the input then goto emit_remainder.
    > + *
    > + * Heuristic match skipping: If 32 bytes are scanned with no matches
    > + * found, start looking only at every other byte. If 32 more bytes are
    > + * scanned, look at every third byte, etc.. When a match is found,
    > + * immediately go back to looking at every byte. This is a small loss
    > + * (~5% performance, ~0.1% density) for lcompressible data due to more
    > + * bookkeeping, but for non-compressible data (such as JPEG) it's a huge
    > + * win since the compressor quickly "realizes" the data is incompressible
    > + * and doesn't bother looking for matches everywhere.
    > + *
    > + * The "skip" variable keeps track of how many bytes there are since the
    > + * last match; dividing it by 32 (ie. right-shifting by five) gives the
    > + * number of bytes to move ahead for each iteration.
    > + */
    > +                       u32 skip = 32;
    > +
    > +                       const char *next_ip = ip;
    > +                       const char *candidate;
    > +                       do {
    > +                               ip = next_ip;
    > +                               u32 hval = next_hash;
    > +                               DCHECK_EQ(hval, hash(ip, shift));
    > +                               u32 bytes_between_hash_lookups = skip++ >> 5;
    > +                               next_ip = ip + bytes_between_hash_lookups;
    > +                               if (unlikely(next_ip > ip_limit)) {
    > +                                       goto emit_remainder;
    > +                               }
    > +                               next_hash = hash(next_ip, shift);
    > +                               candidate = baseip + table[hval];
    > +                               DCHECK_GE(candidate, baseip);
    > +                               DCHECK_LT(candidate, ip);
    > +
    > +                               table[hval] = ip - baseip;
    > +                       } while (likely(UNALIGNED_LOAD32(ip) !=
    > +                                       UNALIGNED_LOAD32(candidate)));
    > +
    > +/*
    > + * Step 2: A 4-byte match has been found.  We'll later see if more
    > + * than 4 bytes match.  But, prior to the match, input
    > + * bytes [next_emit, ip) are unmatched.  Emit them as "literal bytes."
    > + */
    > +                       DCHECK_LE(next_emit + 16, ip_end);
    > +                       op = emit_literal(op, next_emit, ip - next_emit, true);
    > +
    > +/*
    > + * Step 3: Call EmitCopy, and then see if another EmitCopy could
    > + * be our next move.  Repeat until we find no match for the
    > + * input immediately after what was consumed by the last EmitCopy call.
    > + *
    > + * If we exit this loop normally then we need to call EmitLiteral next,
    > + * though we don't yet know how big the literal will be.  We handle that
    > + * by proceeding to the next iteration of the main loop.  We also can exit
    > + * this loop via goto if we get close to exhausting the input.
    > + */
    > +                       u64 input_bytes = 0;
    > +                       u32 candidate_bytes = 0;
    > +
    > +                       do {
    > +/*
    > + * We have a 4-byte match at ip, and no need to emit any
    > + *  "literal bytes" prior to ip.
    > + */
    > +                               const char *base = ip;
    > +                               int matched = 4 +
    > +                                   find_match_length(candidate + 4, ip + 4,
    > +                                                     ip_end);
    > +                               ip += matched;
    > +                               int offset = base - candidate;
    > +                               DCHECK_EQ(0, memcmp(base, candidate, matched));
    > +                               op = emit_copy(op, offset, matched);
    > +/*
    > + * We could immediately start working at ip now, but to improve
    > + * compression we first update table[Hash(ip - 1, ...)].
    > + */
    > +                               const char *insert_tail = ip - 1;
    > +                               next_emit = ip;
    > +                               if (unlikely(ip >= ip_limit)) {
    > +                                       goto emit_remainder;
    > +                               }
    > +                               input_bytes = UNALIGNED_LOAD64(insert_tail);
    > +                               u32 prev_hash =
    > +                                   hash_bytes(get_u32_at_offset
    > +                                              (input_bytes, 0), shift);
    > +                               table[prev_hash] = ip - baseip - 1;
    > +                               u32 cur_hash =
    > +                                   hash_bytes(get_u32_at_offset
    > +                                              (input_bytes, 1), shift);
    > +                               candidate = baseip + table[cur_hash];
    > +                               candidate_bytes = UNALIGNED_LOAD32(candidate);
    > +                               table[cur_hash] = ip - baseip;
    > +                       } while (get_u32_at_offset(input_bytes, 1) ==
    > +                                candidate_bytes);
    > +
    > +                       next_hash =
    > +                           hash_bytes(get_u32_at_offset(input_bytes, 2),
    > +                                      shift);
    > +                       ++ip;
    > +               }
    > +       }
    > +
    > +emit_remainder:
    > +       /* Emit the remaining bytes as a literal */
    > +       if (next_emit < ip_end)
    > +               op = emit_literal(op, next_emit, ip_end - next_emit, false);
    > +
    > +       return op;
    > +}
    > +
    > +/*
    > + * -----------------------------------------------------------------------
    > + *  Lookup table for decompression code.  Generated by ComputeTable() below.
    > + * -----------------------------------------------------------------------
    > + */
    > +
    > +/* Mapping from i in range [0,4] to a mask to extract the bottom 8*i bits */
    > +static const u32 wordmask[] = {
    > +       0u, 0xffu, 0xffffu, 0xffffffu, 0xffffffffu
    > +};
    > +
    > +/*
    > + * Data stored per entry in lookup table:
    > + *       Range   Bits-used       Description
    > + *      ------------------------------------
    > + *      1..64   0..7            Literal/copy length encoded in opcode byte
    > + *      0..7    8..10           Copy offset encoded in opcode byte / 256
    > + *      0..4    11..13          Extra bytes after opcode
    > + *
    > + * We use eight bits for the length even though 7 would have sufficed
    > + * because of efficiency reasons:
    > + *      (1) Extracting a byte is faster than a bit-field
    > + *      (2) It properly aligns copy offset so we do not need a <<8
    > + */
    > +static const u16 char_table[256] = {
    > +       0x0001, 0x0804, 0x1001, 0x2001, 0x0002, 0x0805, 0x1002, 0x2002,
    > +       0x0003, 0x0806, 0x1003, 0x2003, 0x0004, 0x0807, 0x1004, 0x2004,
    > +       0x0005, 0x0808, 0x1005, 0x2005, 0x0006, 0x0809, 0x1006, 0x2006,
    > +       0x0007, 0x080a, 0x1007, 0x2007, 0x0008, 0x080b, 0x1008, 0x2008,
    > +       0x0009, 0x0904, 0x1009, 0x2009, 0x000a, 0x0905, 0x100a, 0x200a,
    > +       0x000b, 0x0906, 0x100b, 0x200b, 0x000c, 0x0907, 0x100c, 0x200c,
    > +       0x000d, 0x0908, 0x100d, 0x200d, 0x000e, 0x0909, 0x100e, 0x200e,
    > +       0x000f, 0x090a, 0x100f, 0x200f, 0x0010, 0x090b, 0x1010, 0x2010,
    > +       0x0011, 0x0a04, 0x1011, 0x2011, 0x0012, 0x0a05, 0x1012, 0x2012,
    > +       0x0013, 0x0a06, 0x1013, 0x2013, 0x0014, 0x0a07, 0x1014, 0x2014,
    > +       0x0015, 0x0a08, 0x1015, 0x2015, 0x0016, 0x0a09, 0x1016, 0x2016,
    > +       0x0017, 0x0a0a, 0x1017, 0x2017, 0x0018, 0x0a0b, 0x1018, 0x2018,
    > +       0x0019, 0x0b04, 0x1019, 0x2019, 0x001a, 0x0b05, 0x101a, 0x201a,
    > +       0x001b, 0x0b06, 0x101b, 0x201b, 0x001c, 0x0b07, 0x101c, 0x201c,
    > +       0x001d, 0x0b08, 0x101d, 0x201d, 0x001e, 0x0b09, 0x101e, 0x201e,
    > +       0x001f, 0x0b0a, 0x101f, 0x201f, 0x0020, 0x0b0b, 0x1020, 0x2020,
    > +       0x0021, 0x0c04, 0x1021, 0x2021, 0x0022, 0x0c05, 0x1022, 0x2022,
    > +       0x0023, 0x0c06, 0x1023, 0x2023, 0x0024, 0x0c07, 0x1024, 0x2024,
    > +       0x0025, 0x0c08, 0x1025, 0x2025, 0x0026, 0x0c09, 0x1026, 0x2026,
    > +       0x0027, 0x0c0a, 0x1027, 0x2027, 0x0028, 0x0c0b, 0x1028, 0x2028,
    > +       0x0029, 0x0d04, 0x1029, 0x2029, 0x002a, 0x0d05, 0x102a, 0x202a,
    > +       0x002b, 0x0d06, 0x102b, 0x202b, 0x002c, 0x0d07, 0x102c, 0x202c,
    > +       0x002d, 0x0d08, 0x102d, 0x202d, 0x002e, 0x0d09, 0x102e, 0x202e,
    > +       0x002f, 0x0d0a, 0x102f, 0x202f, 0x0030, 0x0d0b, 0x1030, 0x2030,
    > +       0x0031, 0x0e04, 0x1031, 0x2031, 0x0032, 0x0e05, 0x1032, 0x2032,
    > +       0x0033, 0x0e06, 0x1033, 0x2033, 0x0034, 0x0e07, 0x1034, 0x2034,
    > +       0x0035, 0x0e08, 0x1035, 0x2035, 0x0036, 0x0e09, 0x1036, 0x2036,
    > +       0x0037, 0x0e0a, 0x1037, 0x2037, 0x0038, 0x0e0b, 0x1038, 0x2038,
    > +       0x0039, 0x0f04, 0x1039, 0x2039, 0x003a, 0x0f05, 0x103a, 0x203a,
    > +       0x003b, 0x0f06, 0x103b, 0x203b, 0x003c, 0x0f07, 0x103c, 0x203c,
    > +       0x0801, 0x0f08, 0x103d, 0x203d, 0x1001, 0x0f09, 0x103e, 0x203e,
    > +       0x1801, 0x0f0a, 0x103f, 0x203f, 0x2001, 0x0f0b, 0x1040, 0x2040
    > +};
    > +
    > +struct snappy_decompressor {
    > +       struct source *reader;  /* Underlying source of bytes to decompress */
    > +       const char *ip;         /* Points to next buffered byte */
    > +       const char *ip_limit;   /* Points just past buffered bytes */
    > +       u32 peeked;             /* Bytes peeked from reader (need to skip) */
    > +       bool eof;               /* Hit end of input without an error? */
    > +       char scratch[5];        /* Temporary buffer for peekfast boundaries */
    > +};
    > +
    > +static void
    > +init_snappy_decompressor(struct snappy_decompressor *d, struct source *reader)
    > +{
    > +       d->reader = reader;
    > +       d->ip = NULL;
    > +       d->ip_limit = NULL;
    > +       d->peeked = 0;
    > +       d->eof = false;
    > +}
    > +
    > +static void exit_snappy_decompressor(struct snappy_decompressor *d)
    > +{
    > +       skip(d->reader, d->peeked);
    > +}
    > +
    > +/*
    > + * Read the uncompressed length stored at the start of the compressed data.
    > + * On succcess, stores the length in *result and returns true.
    > + * On failure, returns false.
    > + */
    > +static bool read_uncompressed_length(struct snappy_decompressor *d,
    > +                                    u32 * result)
    > +{
    > +       DCHECK(d->ip == NULL);  /*
    > +                                * Must not have read anything yet
    > +                                * Length is encoded in 1..5 bytes
    > +                                */
    > +       *result = 0;
    > +       u32 shift = 0;
    > +       while (true) {
    > +               if (shift >= 32)
    > +                       return false;
    > +               size_t n;
    > +               const char *ip = peek(d->reader, &n);
    > +               if (n == 0)
    > +                       return false;
    > +               const unsigned char c = *(const unsigned char *)(ip);
    > +               skip(d->reader, 1);
    > +               *result |= (u32) (c & 0x7f) << shift;
    > +               if (c < 128) {
    > +                       break;
    > +               }
    > +               shift += 7;
    > +       }
    > +       return true;
    > +}
    > +
    > +static bool refill_tag(struct snappy_decompressor *d);
    > +
    > +/*
    > + * Process the next item found in the input.
    > + * Returns true if successful, false on error or end of input.
    > + */
    > +static void decompress_all_tags(struct snappy_decompressor *d,
    > +                               struct writer *writer)
    > +{
    > +       const char *ip = d->ip;
    > +
    > +       for (;;) {
    > +               if (d->ip_limit - ip < 5) {
    > +                       d->ip = ip;
    > +                       if (!refill_tag(d))
    > +                               return;
    > +                       ip = d->ip;
    > +               }
    > +
    > +               const unsigned char c = *(const unsigned char *)(ip++);
    > +
    > +               if ((c & 0x3) == LITERAL) {
    > +                       u32 literal_length = c >> 2;
    > +                       if (unlikely(literal_length >= 60)) {
    > +                               /* Long literal */
    > +                               const u32 literal_ll = literal_length - 59;
    > +                               literal_length = get_unaligned_le32(ip) &
    > +                                       wordmask[literal_ll];
    > +                               ip += literal_ll;
    > +                       }
    > +                       ++literal_length;
    > +
    > +                       u32 avail = d->ip_limit - ip;
    > +                       while (avail < literal_length) {
    > +                               if (!writer_append(writer, ip, avail, false))
    > +                                       return;
    > +                               literal_length -= avail;
    > +                               skip(d->reader, d->peeked);
    > +                               size_t n;
    > +                               ip = peek(d->reader, &n);
    > +                               avail = n;
    > +                               d->peeked = avail;
    > +                               if (avail == 0)
    > +                                       return; /* Premature end of input */
    > +                               d->ip_limit = ip + avail;
    > +                       }
    > +                       bool allow_fast_path = (avail >= 16);
    > +                       if (!writer_append(writer, ip, literal_length,
    > +                                          allow_fast_path))
    > +                               return;
    > +                       ip += literal_length;
    > +               } else {
    > +                       const u32 entry = char_table[c];
    > +                       const u32 trailer = get_unaligned_le32(ip) &
    > +                               wordmask[entry >> 11];
    > +                       const u32 length = entry & 0xff;
    > +                       ip += entry >> 11;
    > +
    > +                       /*
    > +                        * copy_offset/256 is encoded in bits 8..10.
    > +                        * By just fetching those bits, we get
    > +                        * copy_offset (since the bit-field starts at
    > +                        * bit 8).
    > +                        */
    > +                       const u32 copy_offset = entry & 0x700;
    > +                       if (!writer_append_from_self(writer,
    > +                                                    copy_offset + trailer,
    > +                                                    length))
    > +                               return;
    > +               }
    > +       }
    > +}
    > +
    > +static bool refill_tag(struct snappy_decompressor *d)
    > +{
    > +       const char *ip = d->ip;
    > +
    > +       if (ip == d->ip_limit) {
    > +               size_t n;
    > +               /* Fetch a new fragment from the reader */
    > +               skip(d->reader, d->peeked); /* All peeked bytes are used up */
    > +               ip = peek(d->reader, &n);
    > +               d->peeked = n;
    > +               if (n == 0) {
    > +                       d->eof = true;
    > +                       return false;
    > +               }
    > +               d->ip_limit = ip + n;
    > +       }
    > +
    > +       /* Read the tag character */
    > +       DCHECK_LT(ip, d->ip_limit);
    > +       const unsigned char c = *(const unsigned char *)(ip);
    > +       const u32 entry = char_table[c];
    > +       const u32 needed = (entry >> 11) + 1;   /* +1 byte for 'c' */
    > +       DCHECK_LE(needed, sizeof(d->scratch));
    > +
    > +       /* Read more bytes from reader if needed */
    > +       u32 nbuf = d->ip_limit - ip;
    > +
    > +       if (nbuf < needed) {
    > +               /*
    > +                * Stitch together bytes from ip and reader to form the word
    > +                * contents.  We store the needed bytes in "scratch".  They
    > +                * will be consumed immediately by the caller since we do not
    > +                * read more than we need.
    > +                */
    > +               memmove(d->scratch, ip, nbuf);
    > +               skip(d->reader, d->peeked); /* All peeked bytes are used up */
    > +               d->peeked = 0;
    > +               while (nbuf < needed) {
    > +                       size_t length;
    > +                       const char *src = peek(d->reader, &length);
    > +                       if (length == 0)
    > +                               return false;
    > +                       u32 to_add = min_t(u32, needed - nbuf, length);
    > +                       memcpy(d->scratch + nbuf, src, to_add);
    > +                       nbuf += to_add;
    > +                       skip(d->reader, to_add);
    > +               }
    > +               DCHECK_EQ(nbuf, needed);
    > +               d->ip = d->scratch;
    > +               d->ip_limit = d->scratch + needed;
    > +       } else if (nbuf < 5) {
    > +               /*
    > +                * Have enough bytes, but move into scratch so that we do not
    > +                * read past end of input
    > +                */
    > +               memmove(d->scratch, ip, nbuf);
    > +               skip(d->reader, d->peeked); /* All peeked bytes are used up */
    > +               d->peeked = 0;
    > +               d->ip = d->scratch;
    > +               d->ip_limit = d->scratch + nbuf;
    > +       } else {
    > +               /* Pass pointer to buffer returned by reader. */
    > +               d->ip = ip;
    > +       }
    > +       return true;
    > +}
    > +
    > +static int internal_uncompress(struct source *r,
    > +                              struct writer *writer, u32 max_len)
    > +{
    > +       struct snappy_decompressor decompressor;
    > +       u32 uncompressed_len = 0;
    > +
    > +       init_snappy_decompressor(&decompressor, r);
    > +
    > +       if (!read_uncompressed_length(&decompressor, &uncompressed_len))
    > +               return -EIO;
    > +       /* Protect against possible DoS attack */
    > +       if ((u64) (uncompressed_len) > max_len)
    > +               return -EIO;
    > +
    > +       writer_set_expected_length(writer, uncompressed_len);
    > +
    > +       /* Process the entire input */
    > +       decompress_all_tags(&decompressor, writer);
    > +
    > +       exit_snappy_decompressor(&decompressor);
    > +       return (decompressor.eof && writer_check_length(writer)) ? 0 : -EIO;
    > +}
    > +
    > +static inline int compress(struct snappy_env *env, struct source *reader,
    > +                          struct sink *writer)
    > +{
    > +       int err;
    > +       size_t written = 0;
    > +       int N = available(reader);
    > +       char ulength[kmax32];
    > +       char *p = varint_encode32(ulength, N);
    > +
    > +       append(writer, ulength, p - ulength);
    > +       written += (p - ulength);
    > +
    > +       while (N > 0) {
    > +               /* Get next block to compress (without copying if possible) */
    > +               size_t fragment_size;
    > +               const char *fragment = peek(reader, &fragment_size);
    > +               if (fragment_size == 0) {
    > +                       err = -EIO;
    > +                       goto out;
    > +               }
    > +               const int num_to_read = min_t(int, N, kblock_size);
    > +               size_t bytes_read = fragment_size;
    > +
    > +               int pending_advance = 0;
    > +               if (bytes_read >= num_to_read) {
    > +                       /* Buffer returned by reader is large enough */
    > +                       pending_advance = num_to_read;
    > +                       fragment_size = num_to_read;
    > +               }
    > +#ifdef SCATHER_GATHER
    > +               else {
    > +                       memcpy(env->scratch, fragment, bytes_read);
    > +                       skip(reader, bytes_read);
    > +
    > +                       while (bytes_read < num_to_read) {
    > +                               fragment = peek(reader, &fragment_size);
    > +                               size_t n =
    > +                                   min_t(size_t, fragment_size,
    > +                                         num_to_read - bytes_read);
    > +                               memcpy(env->scratch + bytes_read, fragment, n);
    > +                               bytes_read += n;
    > +                               skip(reader, n);
    > +                       }
    > +                       DCHECK_EQ(bytes_read, num_to_read);
    > +                       fragment = env->scratch;
    > +                       fragment_size = num_to_read;
    > +               }
    > +#endif
    > +               if (fragment_size < num_to_read)
    > +                       return -EIO;
    > +
    > +               /* Get encoding table for compression */
    > +               int table_size;
    > +               u16 *table = get_hash_table(env, num_to_read, &table_size);
    > +
    > +               /* Compress input_fragment and append to dest */
    > +               const int max_output =
    > +                   snappy_max_compressed_length(num_to_read);
    > +
    > +               char *dest;
    > +               dest = sink_peek(writer, max_output);
    > +#ifdef SCATHER_GATHER
    > +               if (!dest) {
    > +                       /*
    > +                        * Need a scratch buffer for the output,
    > +                        * because the byte sink doesn't have enough
    > +                        * in one piece.
    > +                        */
    > +                       dest = env->scratch_output;
    > +               }
    > +#endif
    > +               char *end = compress_fragment(fragment, fragment_size,
    > +                                             dest, table, table_size);
    > +               append(writer, dest, end - dest);
    > +               written += (end - dest);
    > +
    > +               N -= num_to_read;
    > +               skip(reader, pending_advance);
    > +       }
    > +
    > +       err = 0;
    > +out:
    > +       return err;
    > +}
    > +
    > +/**
    > + * snappy_compress - Compress a buffer using the snappy compressor.
    > + * @env: Preallocated environment
    > + * @input: Input buffer
    > + * @input_length: Length of input_buffer
    > + * @compressed: Output buffer for compressed data
    > + * @compressed_length: The real length of the output written here.
    > + *
    > + * Return 0 on success, otherwise an negative error code.
    > + *
    > + * The output buffer must be at least
    > + * snappy_max_compressed_length(input_length) bytes long.
    > + *
    > + * Requires a preallocated environment from snappy_init_env.
    > + * The environment does not keep state over individual calls
    > + * of this function, just preallocates the memory.
    > + */
    > +int snappy_compress(struct snappy_env *env,
    > +                   const char *input,
    > +                   size_t input_length,
    > +                   char *compressed, size_t *compressed_length)
    > +{
    > +       struct source reader = {
    > +               .ptr = input,
    > +               .left = input_length
    > +       };
    > +       struct sink writer = {
    > +               .dest = compressed,
    > +       };
    > +       int err = compress(env, &reader, &writer);
    > +
    > +       /* Compute how many bytes were added */
    > +       *compressed_length = (writer.dest - compressed);
    > +       return err;
    > +}
    > +EXPORT_SYMBOL(snappy_compress);
    > +
    > +/**
    > + * snappy_uncompress - Uncompress a snappy compressed buffer
    > + * @compressed: Input buffer with compressed data
    > + * @n: length of compressed buffer
    > + * @uncompressed: buffer for uncompressed data
    > + *
    > + * The uncompressed data buffer must be at least
    > + * snappy_uncompressed_length(compressed) bytes long.
    > + *
    > + * Returns true when successfull, otherwise false.
    > + */
    > +bool snappy_uncompress(const char *compressed, size_t n, char *uncompressed)
    > +{
    > +       struct source reader = {
    > +               .ptr = compressed,
    > +               .left = n
    > +       };
    > +       struct writer output = {
    > +               .base = uncompressed,
    > +               .op = uncompressed
    > +       };
    > +       return internal_uncompress(&reader, &output, 0xffffffff);
    > +}
    > +EXPORT_SYMBOL(snappy_uncompress);
    > +
    > +/**
    > + * snappy_init_env - Allocate snappy compression environment
    > + * @env: Environment to preallocate
    > + *
    > + * Returns 0 on success, otherwise negative errno.
    > + * Must run in process context.
    > + */
    > +int snappy_init_env(struct snappy_env *env)
    > +{
    > +       env->hash_table = vmalloc(sizeof(u16) * kmax_hash_table_size);
    > +       if (!env->hash_table)
    > +               goto error;
    > +#ifdef SCATHER_GATHER
    > +       env->scratch = vmalloc(kblock_size);
    > +       env->scratch_output =
    > +               vmalloc(snappy_max_compressed_length(kblock_size));
    > +       if (!env->scratch || !env->scratch_output)
    > +               goto error;
    > +#endif
    > +       return 0;
    > +error:
    > +       snappy_free_env(env);
    > +       return -ENOMEM;
    > +}
    > +EXPORT_SYMBOL(snappy_init_env);
    > +
    > +/**
    > + * snappy_free_env - Free an snappy compression environment
    > + * @env: Environment to free.
    > + *
    > + * Must run in process context.
    > + */
    > +void snappy_free_env(struct snappy_env *env)
    > +{
    > +       vfree(env->hash_table);
    > +#ifdef SCATHER_GATHER
    > +       vfree(env->scratch);
    > +       vfree(env->scratch_output);
    > +#endif
    > +       memset(env, 0, sizeof(struct snappy_env));
    > +}
    > +EXPORT_SYMBOL(snappy_free_env);
    > --
    > 1.7.7.4

    I've run into one of those x86_64/x86 errors (I think x86_64 has
    different implicit includes).

    (BTW: If you're ever reworking this patch set, I'd like to make an ad
    hoc request for slightly different names for fs/btrfs/snappy.c and
    lib/snappy.c)

    When building a x86 kernel, I get the following errors:
    CC [M] lib/snappy.o
    lib/snappy.c: In function 'snappy_init_env':
    lib/snappy.c:1268:2: error: implicit declaration of function 'vmalloc'
    CC [M] fs/btrfs/free-space-cache.o
    lib/snappy.c:1268:18: warning: assignment makes pointer from integer
    without a cast
    lib/snappy.c: In function 'snappy_free_env':
    lib/snappy.c:1293:2: error: implicit declaration of function 'vfree'
    make[1]: *** [lib/snappy.o] Error 1
    make: *** [lib] Error 2

    The error clears with this patch:

    diff --git a/lib/snappy.c b/lib/snappy.c
    index 3848c6c..a25b2a4 100644
    --- a/lib/snappy.c
    +++ b/lib/snappy.c
    @@ -41,6 +41,7 @@
    #include <linux/slab.h>
    #include <linux/string.h>
    #include <linux/snappy.h>
    +#include <linux/vmalloc.h>
    #include <asm/unaligned.h>

    #define CRASH_UNLESS(x) BUG_ON(!(x))
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/
    \
     
     \ /
      Last update: 2012-02-14 05:33    [W:4.124 / U:0.060 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site