]> git.sur5r.net Git - u-boot/blob - lib/lz4.c
efi_loader: use correct format string for unsigned long
[u-boot] / 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 */
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 }