LXR uboot/lib/lz4.c

   1/*
   2   LZ4 - Fast LZ compression algorithm
   3   Copyright (C) 2011-2015, Yann Collet.
   4
   5   SPDX-License-Identifier: BSD-2-Clause
   6
   7   You can contact the author at :
   8   - LZ4 source repository : https://github.com/Cyan4973/lz4
   9   - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c
  10*/
  11
  12
  13/**************************************
  14*  Reading and writing into memory
  15**************************************/
  16
  17/* customized version of memcpy, which may overwrite up to 7 bytes beyond dstEnd */
  18static void LZ4_wildCopy(void* dstPtr, const void* srcPtr, void* dstEnd)
  19{
  20    BYTE* d = (BYTE*)dstPtr;
  21    const BYTE* s = (const BYTE*)srcPtr;
  22    BYTE* e = (BYTE*)dstEnd;
  23    do { LZ4_copy8(d,s); d+=8; s+=8; } while (d<e);
  24}
  25
  26
  27/**************************************
  28*  Common Constants
  29**************************************/
  30#define MINMATCH 4
  31
  32#define COPYLENGTH 8
  33#define LASTLITERALS 5
  34#define MFLIMIT (COPYLENGTH+MINMATCH)
  35static const int LZ4_minLength = (MFLIMIT+1);
  36
  37#define KB *(1 <<10)
  38#define MB *(1 <<20)
  39#define GB *(1U<<30)
  40
  41#define MAXD_LOG 16
  42#define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
  43
  44#define ML_BITS  4
  45#define ML_MASK  ((1U<<ML_BITS)-1)
  46#define RUN_BITS (8-ML_BITS)
  47#define RUN_MASK ((1U<<RUN_BITS)-1)
  48
  49
  50/**************************************
  51*  Local Structures and types
  52**************************************/
  53typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive;
  54typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;
  55typedef enum { full = 0, partial = 1 } earlyEnd_directive;
  56
  57
  58
  59/*******************************
  60*  Decompression functions
  61*******************************/
  62/*
  63 * This generic decompression function cover all use cases.
  64 * It shall be instantiated several times, using different sets of directives
  65 * Note that it is essential this generic function is really inlined,
  66 * in order to remove useless branches during compilation optimization.
  67 */
  68FORCE_INLINE int LZ4_decompress_generic(
  69                 const char* const source,
  70                 char* const dest,
  71                 int inputSize,
  72                 int outputSize,         /* If endOnInput==endOnInputSize, this value is the max size of Output Buffer. */
  73
  74                 int endOnInput,         /* endOnOutputSize, endOnInputSize */
  75                 int partialDecoding,    /* full, partial */
  76                 int targetOutputSize,   /* only used if partialDecoding==partial */
  77                 int dict,               /* noDict, withPrefix64k, usingExtDict */
  78                 const BYTE* const lowPrefix,  /* == dest if dict == noDict */
  79                 const BYTE* const dictStart,  /* only if dict==usingExtDict */
  80                 const size_t dictSize         /* note : = 0 if noDict */
  81                 )
  82{
  83    /* Local Variables */
  84    const BYTE* ip = (const BYTE*) source;
  85    const BYTE* const iend = ip + inputSize;
  86
  87    BYTE* op = (BYTE*) dest;
  88    BYTE* const oend = op + outputSize;
  89    BYTE* cpy;
  90    BYTE* oexit = op + targetOutputSize;
  91    const BYTE* const lowLimit = lowPrefix - dictSize;
  92
  93    const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize;
  94    const size_t dec32table[] = {4, 1, 2, 1, 4, 4, 4, 4};
  95    const size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};
  96
  97    const int safeDecode = (endOnInput==endOnInputSize);
  98    const int checkOffset = ((safeDecode) && (dictSize < (int)(64 KB)));
  99
 100
 101    /* Special cases */
 102    if ((partialDecoding) && (oexit> oend-MFLIMIT)) oexit = oend-MFLIMIT;                         /* targetOutputSize too high => decode everything */
 103    if ((endOnInput) && (unlikely(outputSize==0))) return ((inputSize==1) && (*ip==0)) ? 0 : -1;  /* Empty output buffer */
 104    if ((!endOnInput) && (unlikely(outputSize==0))) return (*ip==0?1:-1);
 105
 106
 107    /* Main Loop */
 108    while (1)
 109    {
 110        unsigned token;
 111        size_t length;
 112        const BYTE* match;
 113
 114        /* get literal length */
 115        token = *ip++;
 116        if ((length=(token>>ML_BITS)) == RUN_MASK)
 117        {
 118            unsigned s;
 119            do
 120            {
 121                s = *ip++;
 122                length += s;
 123            }
 124            while (likely((endOnInput)?ip<iend-RUN_MASK:1) && (s==255));
 125            if ((safeDecode) && unlikely((size_t)(op+length)<(size_t)(op))) goto _output_error;   /* overflow detection */
 126            if ((safeDecode) && unlikely((size_t)(ip+length)<(size_t)(ip))) goto _output_error;   /* overflow detection */
 127        }
 128
 129        /* copy literals */
 130        cpy = op+length;
 131        if (((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT)) || (ip+length>iend-(2+1+LASTLITERALS))) )
 132            || ((!endOnInput) && (cpy>oend-COPYLENGTH)))
 133        {
 134            if (partialDecoding)
 135            {
 136                if (cpy > oend) goto _output_error;                           /* Error : write attempt beyond end of output buffer */
 137                if ((endOnInput) && (ip+length > iend)) goto _output_error;   /* Error : read attempt beyond end of input buffer */
 138            }
 139            else
 140            {
 141                if ((!endOnInput) && (cpy != oend)) goto _output_error;       /* Error : block decoding must stop exactly there */
 142                if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) goto _output_error;   /* Error : input must be consumed */
 143            }
 144            memcpy(op, ip, length);
 145            ip += length;
 146            op += length;
 147            break;     /* Necessarily EOF, due to parsing restrictions */
 148        }
 149        LZ4_wildCopy(op, ip, cpy);
 150        ip += length; op = cpy;
 151
 152        /* get offset */
 153        match = cpy - LZ4_readLE16(ip); ip+=2;
 154        if ((checkOffset) && (unlikely(match < lowLimit))) goto _output_error;   /* Error : offset outside destination buffer */
 155
 156        /* get matchlength */
 157        length = token & ML_MASK;
 158        if (length == ML_MASK)
 159        {
 160            unsigned s;
 161            do
 162            {
 163                if ((endOnInput) && (ip > iend-LASTLITERALS)) goto _output_error;
 164                s = *ip++;
 165                length += s;
 166            } while (s==255);
 167            if ((safeDecode) && unlikely((size_t)(op+length)<(size_t)op)) goto _output_error;   /* overflow detection */
 168        }
 169        length += MINMATCH;
 170
 171        /* check external dictionary */
 172        if ((dict==usingExtDict) && (match < lowPrefix))
 173        {
 174            if (unlikely(op+length > oend-LASTLITERALS)) goto _output_error;   /* doesn't respect parsing restriction */
 175
 176            if (length <= (size_t)(lowPrefix-match))
 177            {
 178                /* match can be copied as a single segment from external dictionary */
 179                match = dictEnd - (lowPrefix-match);
 180                memmove(op, match, length); op += length;
 181            }
 182            else
 183            {
 184                /* match encompass external dictionary and current segment */
 185                size_t copySize = (size_t)(lowPrefix-match);
 186                memcpy(op, dictEnd - copySize, copySize);
 187                op += copySize;
 188                copySize = length - copySize;
 189                if (copySize > (size_t)(op-lowPrefix))   /* overlap within current segment */
 190                {
 191                    BYTE* const endOfMatch = op + copySize;
 192                    const BYTE* copyFrom = lowPrefix;
 193                    while (op < endOfMatch) *op++ = *copyFrom++;
 194                }
 195                else
 196                {
 197                    memcpy(op, lowPrefix, copySize);
 198                    op += copySize;
 199                }
 200            }
 201            continue;
 202        }
 203
 204        /* copy repeated sequence */
 205        cpy = op + length;
 206        if (unlikely((op-match)<8))
 207        {
 208            const size_t dec64 = dec64table[op-match];
 209            op[0] = match[0];
 210            op[1] = match[1];
 211            op[2] = match[2];
 212            op[3] = match[3];
 213            match += dec32table[op-match];
 214            LZ4_copy4(op+4, match);
 215            op += 8; match -= dec64;
 216        } else { LZ4_copy8(op, match); op+=8; match+=8; }
 217
 218        if (unlikely(cpy>oend-12))
 219        {
 220            if (cpy > oend-LASTLITERALS) goto _output_error;    /* Error : last LASTLITERALS bytes must be literals */
 221            if (op < oend-8)
 222            {
 223                LZ4_wildCopy(op, match, oend-8);
 224                match += (oend-8) - op;
 225                op = oend-8;
 226            }
 227            while (op<cpy) *op++ = *match++;
 228        }
 229        else
 230            LZ4_wildCopy(op, match, cpy);
 231        op=cpy;   /* correction */
 232    }
 233
 234    /* end of decoding */
 235    if (endOnInput)
 236       return (int) (((char*)op)-dest);     /* Nb of output bytes decoded */
 237    else
 238       return (int) (((const char*)ip)-source);   /* Nb of input bytes read */
 239
 240    /* Overflow error detected */
 241_output_error:
 242    return (int) (-(((const char*)ip)-source))-1;
 243}
 244