LXR linux/lib/lz4/lz4

   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#include <linux/lz4.h>
  45
  46#include <asm/unaligned.h>
  47
  48#include "lz4defs.h"
  49
  50static const int dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
  51#if LZ4_ARCH64
  52static const int dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3};
  53#endif
  54
  55static int lz4_uncompress(const char *source, char *dest, int osize)
  56{
  57        const BYTE *ip = (const BYTE *) source;
  58        const BYTE *ref;
  59        BYTE *op = (BYTE *) dest;
  60        BYTE * const oend = op + osize;
  61        BYTE *cpy;
  62        unsigned token;
  63        size_t length;
  64
  65        while (1) {
  66
  67                /* get runlength */
  68                token = *ip++;
  69                length = (token >> ML_BITS);
  70                if (length == RUN_MASK) {
  71                        size_t len;
  72
  73                        len = *ip++;
  74                        for (; len == 255; length += 255)
  75                                len = *ip++;
  76                        if (unlikely(length > (size_t)(length + len)))
  77                                goto _output_error;
  78                        length += len;
  79                }
  80
  81                /* copy literals */
  82                cpy = op + length;
  83                if (unlikely(cpy > oend - COPYLENGTH)) {
  84                        /*
  85                         * Error: not enough place for another match
  86                         * (min 4) + 5 literals
  87                         */
  88                        if (cpy != oend)
  89                                goto _output_error;
  90
  91                        memcpy(op, ip, length);
  92                        ip += length;
  93                        break; /* EOF */
  94                }
  95                LZ4_WILDCOPY(ip, op, cpy);
  96                ip -= (op - cpy);
  97                op = cpy;
  98
  99                /* get offset */
 100                LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
 101                ip += 2;
 102
 103                /* Error: offset create reference outside destination buffer */
 104                if (unlikely(ref < (BYTE *const) dest))
 105                        goto _output_error;
 106
 107                /* get matchlength */
 108                length = token & ML_MASK;
 109                if (length == ML_MASK) {
 110                        for (; *ip == 255; length += 255)
 111                                ip++;
 112                        if (unlikely(length > (size_t)(length + *ip)))
 113                                goto _output_error;
 114                        length += *ip++;
 115                }
 116
 117                /* copy repeated sequence */
 118                if (unlikely((op - ref) < STEPSIZE)) {
 119#if LZ4_ARCH64
 120                        int dec64 = dec64table[op - ref];
 121#else
 122                        const int dec64 = 0;
 123#endif
 124                        op[0] = ref[0];
 125                        op[1] = ref[1];
 126                        op[2] = ref[2];
 127                        op[3] = ref[3];
 128                        op += 4;
 129                        ref += 4;
 130                        ref -= dec32table[op-ref];
 131                        PUT4(ref, op);
 132                        op += STEPSIZE - 4;
 133                        ref -= dec64;
 134                } else {
 135                        LZ4_COPYSTEP(ref, op);
 136                }
 137                cpy = op + length - (STEPSIZE - 4);
 138                if (cpy > (oend - COPYLENGTH)) {
 139
 140                        /* Error: request to write beyond destination buffer */
 141                        if (cpy > oend)
 142                                goto _output_error;
 143#if LZ4_ARCH64
 144                        if ((ref + COPYLENGTH) > oend)
 145#else
 146                        if ((ref + COPYLENGTH) > oend ||
 147                                        (op + COPYLENGTH) > oend)
 148#endif
 149                                goto _output_error;
 150                        LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
 151                        while (op < cpy)
 152                                *op++ = *ref++;
 153                        op = cpy;
 154                        /*
 155                         * Check EOF (should never happen, since last 5 bytes
 156                         * are supposed to be literals)
 157                         */
 158                        if (op == oend)
 159                                goto _output_error;
 160                        continue;
 161                }
 162                LZ4_SECURECOPY(ref, op, cpy);
 163                op = cpy; /* correction */
 164        }
 165        /* end of decoding */
 166        return (int) (((char *)ip) - source);
 167
 168        /* write overflow error detected */
 169_output_error:
 170        return -1;
 171}
 172
 173static int lz4_uncompress_unknownoutputsize(const char *source, char *dest,
 174                                int isize, size_t maxoutputsize)
 175{
 176        const BYTE *ip = (const BYTE *) source;
 177        const BYTE *const iend = ip + isize;
 178        const BYTE *ref;
 179
 180
 181        BYTE *op = (BYTE *) dest;
 182        BYTE * const oend = op + maxoutputsize;
 183        BYTE *cpy;
 184
 185        /* Main Loop */
 186        while (ip < iend) {
 187
 188                unsigned token;
 189                size_t length;
 190
 191                /* get runlength */
 192                token = *ip++;
 193                length = (token >> ML_BITS);
 194                if (length == RUN_MASK) {
 195                        int s = 255;
 196                        while ((ip < iend) && (s == 255)) {
 197                                s = *ip++;
 198                                if (unlikely(length > (size_t)(length + s)))
 199                                        goto _output_error;
 200                                length += s;
 201                        }
 202                }
 203                /* copy literals */
 204                cpy = op + length;
 205                if ((cpy > oend - COPYLENGTH) ||
 206                        (ip + length > iend - COPYLENGTH)) {
 207
 208                        if (cpy > oend)
 209                                goto _output_error;/* writes beyond buffer */
 210
 211                        if (ip + length != iend)
 212                                goto _output_error;/*
 213                                                    * Error: LZ4 format requires
 214                                                    * to consume all input
 215                                                    * at this stage
 216                                                    */
 217                        memcpy(op, ip, length);
 218                        op += length;
 219                        break;/* Necessarily EOF, due to parsing restrictions */
 220                }
 221                LZ4_WILDCOPY(ip, op, cpy);
 222                ip -= (op - cpy);
 223                op = cpy;
 224
 225                /* get offset */
 226                LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
 227                ip += 2;
 228                if (ref < (BYTE * const) dest)
 229                        goto _output_error;
 230                        /*
 231                         * Error : offset creates reference
 232                         * outside of destination buffer
 233                         */
 234
 235                /* get matchlength */
 236                length = (token & ML_MASK);
 237                if (length == ML_MASK) {
 238                        while (ip < iend) {
 239                                int s = *ip++;
 240                                if (unlikely(length > (size_t)(length + s)))
 241                                        goto _output_error;
 242                                length += s;
 243                                if (s == 255)
 244                                        continue;
 245                                break;
 246                        }
 247                }
 248
 249                /* copy repeated sequence */
 250                if (unlikely((op - ref) < STEPSIZE)) {
 251#if LZ4_ARCH64
 252                        int dec64 = dec64table[op - ref];
 253#else
 254                        const int dec64 = 0;
 255#endif
 256                                op[0] = ref[0];
 257                                op[1] = ref[1];
 258                                op[2] = ref[2];
 259                                op[3] = ref[3];
 260                                op += 4;
 261                                ref += 4;
 262                                ref -= dec32table[op - ref];
 263                                PUT4(ref, op);
 264                                op += STEPSIZE - 4;
 265                                ref -= dec64;
 266                } else {
 267                        LZ4_COPYSTEP(ref, op);
 268                }
 269                cpy = op + length - (STEPSIZE-4);
 270                if (cpy > oend - COPYLENGTH) {
 271                        if (cpy > oend)
 272                                goto _output_error; /* write outside of buf */
 273#if LZ4_ARCH64
 274                        if ((ref + COPYLENGTH) > oend)
 275#else
 276                        if ((ref + COPYLENGTH) > oend ||
 277                                        (op + COPYLENGTH) > oend)
 278#endif
 279                                goto _output_error;
 280                        LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
 281                        while (op < cpy)
 282                                *op++ = *ref++;
 283                        op = cpy;
 284                        /*
 285                         * Check EOF (should never happen, since last 5 bytes
 286                         * are supposed to be literals)
 287                         */
 288                        if (op == oend)
 289                                goto _output_error;
 290                        continue;
 291                }
 292                LZ4_SECURECOPY(ref, op, cpy);
 293                op = cpy; /* correction */
 294        }
 295        /* end of decoding */
 296        return (int) (((char *) op) - dest);
 297
 298        /* write overflow error detected */
 299_output_error:
 300        return -1;
 301}
 302
 303int lz4_decompress(const unsigned char *src, size_t *src_len,
 304                unsigned char *dest, size_t actual_dest_len)
 305{
 306        int ret = -1;
 307        int input_len = 0;
 308
 309        input_len = lz4_uncompress(src, dest, actual_dest_len);
 310        if (input_len < 0)
 311                goto exit_0;
 312        *src_len = input_len;
 313
 314        return 0;
 315exit_0:
 316        return ret;
 317}
 318#ifndef STATIC
 319EXPORT_SYMBOL(lz4_decompress);
 320#endif
 321
 322int lz4_decompress_unknownoutputsize(const unsigned char *src, size_t src_len,
 323                unsigned char *dest, size_t *dest_len)
 324{
 325        int ret = -1;
 326        int out_len = 0;
 327
 328        out_len = lz4_uncompress_unknownoutputsize(src, dest, src_len,
 329                                        *dest_len);
 330        if (out_len < 0)
 331                goto exit_0;
 332        *dest_len = out_len;
 333
 334        return 0;
 335exit_0:
 336        return ret;
 337}
 338#ifndef STATIC
 339EXPORT_SYMBOL(lz4_decompress_unknownoutputsize);
 340
 341MODULE_LICENSE("Dual BSD/GPL");
 342MODULE_DESCRIPTION("LZ4 Decompressor");
 343#endif
 344