]>
git.ipfire.org Git - people/ms/u-boot.git/blob - lib/lz4.c
2 LZ4 - Fast LZ compression algorithm
3 Copyright (C) 2011-2015, Yann Collet.
5 SPDX-License-Identifier: BSD-2-Clause
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
13 /**************************************
14 * Reading and writing into memory
15 **************************************/
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
)
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
);
27 /**************************************
29 **************************************/
33 #define LASTLITERALS 5
34 #define MFLIMIT (COPYLENGTH+MINMATCH)
35 static const int LZ4_minLength
= (MFLIMIT
+1);
42 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
45 #define ML_MASK ((1U<<ML_BITS)-1)
46 #define RUN_BITS (8-ML_BITS)
47 #define RUN_MASK ((1U<<RUN_BITS)-1)
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
;
59 /*******************************
60 * Decompression functions
61 *******************************/
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.
68 FORCE_INLINE
int LZ4_decompress_generic(
69 const char* const source
,
72 int outputSize
, /* If endOnInput==endOnInputSize, this value is the max size of Output Buffer. */
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 */
84 const BYTE
* ip
= (const BYTE
*) source
;
85 const BYTE
* const iend
= ip
+ inputSize
;
87 BYTE
* op
= (BYTE
*) dest
;
88 BYTE
* const oend
= op
+ outputSize
;
90 BYTE
* oexit
= op
+ targetOutputSize
;
91 const BYTE
* const lowLimit
= lowPrefix
- dictSize
;
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};
97 const int safeDecode
= (endOnInput
==endOnInputSize
);
98 const int checkOffset
= ((safeDecode
) && (dictSize
< (int)(64 KB
)));
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);
114 /* get literal length */
116 if ((length
=(token
>>ML_BITS
)) == RUN_MASK
)
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 */
131 if (((endOnInput
) && ((cpy
>(partialDecoding
?oexit
:oend
-MFLIMIT
)) || (ip
+length
>iend
-(2+1+LASTLITERALS
))) )
132 || ((!endOnInput
) && (cpy
>oend
-COPYLENGTH
)))
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 */
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 */
144 memcpy(op
, ip
, length
);
147 break; /* Necessarily EOF, due to parsing restrictions */
149 LZ4_wildCopy(op
, ip
, cpy
);
150 ip
+= length
; op
= cpy
;
153 match
= cpy
- LZ4_readLE16(ip
); ip
+=2;
154 if ((checkOffset
) && (unlikely(match
< lowLimit
))) goto _output_error
; /* Error : offset outside destination buffer */
156 /* get matchlength */
157 length
= token
& ML_MASK
;
158 if (length
== ML_MASK
)
163 if ((endOnInput
) && (ip
> iend
-LASTLITERALS
)) goto _output_error
;
167 if ((safeDecode
) && unlikely((size_t)(op
+length
)<(size_t)op
)) goto _output_error
; /* overflow detection */
171 /* check external dictionary */
172 if ((dict
==usingExtDict
) && (match
< lowPrefix
))
174 if (unlikely(op
+length
> oend
-LASTLITERALS
)) goto _output_error
; /* doesn't respect parsing restriction */
176 if (length
<= (size_t)(lowPrefix
-match
))
178 /* match can be copied as a single segment from external dictionary */
179 match
= dictEnd
- (lowPrefix
-match
);
180 memmove(op
, match
, length
); op
+= length
;
184 /* match encompass external dictionary and current segment */
185 size_t copySize
= (size_t)(lowPrefix
-match
);
186 memcpy(op
, dictEnd
- copySize
, copySize
);
188 copySize
= length
- copySize
;
189 if (copySize
> (size_t)(op
-lowPrefix
)) /* overlap within current segment */
191 BYTE
* const endOfMatch
= op
+ copySize
;
192 const BYTE
* copyFrom
= lowPrefix
;
193 while (op
< endOfMatch
) *op
++ = *copyFrom
++;
197 memcpy(op
, lowPrefix
, copySize
);
204 /* copy repeated sequence */
206 if (unlikely((op
-match
)<8))
208 const size_t dec64
= dec64table
[op
-match
];
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; }
218 if (unlikely(cpy
>oend
-12))
220 if (cpy
> oend
-LASTLITERALS
) goto _output_error
; /* Error : last LASTLITERALS bytes must be literals */
223 LZ4_wildCopy(op
, match
, oend
-8);
224 match
+= (oend
-8) - op
;
227 while (op
<cpy
) *op
++ = *match
++;
230 LZ4_wildCopy(op
, match
, cpy
);
231 op
=cpy
; /* correction */
234 /* end of decoding */
236 return (int) (((char*)op
)-dest
); /* Nb of output bytes decoded */
238 return (int) (((const char*)ip
)-source
); /* Nb of input bytes read */
240 /* Overflow error detected */
242 return (int) (-(((const char*)ip
)-source
))-1;