xref: /openbmc/u-boot/lib/lz4.c (revision 35546f6f2014282cc4f9772324b5588bd44a2938)
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 */
18  static 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)
35  static 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  **************************************/
53  typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive;
54  typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;
55  typedef 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   */
68  FORCE_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