[u-boot.git] / lib / lz4.c

// SPDX-License-Identifier: BSD-2-Clause
/*
   LZ4 - Fast LZ compression algorithm
   Copyright (C) 2011-2015, Yann Collet.

   You can contact the author at :
   - LZ4 source repository : https://github.com/Cyan4973/lz4
   - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c
*/


/**************************************
*  Reading and writing into memory
**************************************/

/* customized version of memcpy, which may overwrite up to 7 bytes beyond dstEnd */
static void LZ4_wildCopy(void* dstPtr, const void* srcPtr, void* dstEnd)
{
    BYTE* d = (BYTE*)dstPtr;
    const BYTE* s = (const BYTE*)srcPtr;
    BYTE* e = (BYTE*)dstEnd;
    do { LZ4_copy8(d,s); d+=8; s+=8; } while (d<e);
}


/**************************************
*  Common Constants
**************************************/
#define MINMATCH 4

#define COPYLENGTH 8
#define LASTLITERALS 5
#define MFLIMIT (COPYLENGTH+MINMATCH)
static const int LZ4_minLength = (MFLIMIT+1);

#define KB *(1 <<10)
#define MB *(1 <<20)
#define GB *(1U<<30)

#define MAXD_LOG 16
#define MAX_DISTANCE ((1 << MAXD_LOG) - 1)

#define ML_BITS  4
#define ML_MASK  ((1U<<ML_BITS)-1)
#define RUN_BITS (8-ML_BITS)
#define RUN_MASK ((1U<<RUN_BITS)-1)


/**************************************
*  Local Structures and types
**************************************/
typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive;
typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;
typedef enum { full = 0, partial = 1 } earlyEnd_directive;


/*******************************
*  Decompression functions
*******************************/
/*
 * This generic decompression function cover all use cases.
 * It shall be instantiated several times, using different sets of directives
 * Note that it is essential this generic function is really inlined,
 * in order to remove useless branches during compilation optimization.
 */
FORCE_INLINE int LZ4_decompress_generic(
                 const char* const source,
                 char* const dest,
                 int inputSize,
                 int outputSize,         /* If endOnInput==endOnInputSize, this value is the max size of Output Buffer. */

                 int endOnInput,         /* endOnOutputSize, endOnInputSize */
                 int partialDecoding,    /* full, partial */
                 int targetOutputSize,   /* only used if partialDecoding==partial */
                 int dict,               /* noDict, withPrefix64k, usingExtDict */
                 const BYTE* const lowPrefix,  /* == dest if dict == noDict */
                 const BYTE* const dictStart,  /* only if dict==usingExtDict */
                 const size_t dictSize         /* note : = 0 if noDict */
                 )
{
    /* Local Variables */
    const BYTE* ip = (const BYTE*) source;
    const BYTE* const iend = ip + inputSize;

    BYTE* op = (BYTE*) dest;
    BYTE* const oend = op + outputSize;
    BYTE* cpy;
    BYTE* oexit = op + targetOutputSize;
    const BYTE* const lowLimit = lowPrefix - dictSize;

    const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize;
    const size_t dec32table[] = {4, 1, 2, 1, 4, 4, 4, 4};
    const size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};

    const int safeDecode = (endOnInput==endOnInputSize);
    const int checkOffset = ((safeDecode) && (dictSize < (int)(64 KB)));


    /* Special cases */
    if ((partialDecoding) && (oexit> oend-MFLIMIT)) oexit = oend-MFLIMIT;                         /* targetOutputSize too high => decode everything */
    if ((endOnInput) && (unlikely(outputSize==0))) return ((inputSize==1) && (*ip==0)) ? 0 : -1;  /* Empty output buffer */
    if ((!endOnInput) && (unlikely(outputSize==0))) return (*ip==0?1:-1);


    /* Main Loop */
    while (1)
    {
        unsigned token;
        size_t length;
        const BYTE* match;

        /* get literal length */
        token = *ip++;
        if ((length=(token>>ML_BITS)) == RUN_MASK)
        {
            unsigned s;
            do
            {
                s = *ip++;
                length += s;
            }
            while (likely((endOnInput)?ip<iend-RUN_MASK:1) && (s==255));
            if ((safeDecode) && unlikely((size_t)(op+length)<(size_t)(op))) goto _output_error;   /* overflow detection */
            if ((safeDecode) && unlikely((size_t)(ip+length)<(size_t)(ip))) goto _output_error;   /* overflow detection */
        }

        /* copy literals */
        cpy = op+length;
        if (((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT)) || (ip+length>iend-(2+1+LASTLITERALS))) )
            || ((!endOnInput) && (cpy>oend-COPYLENGTH)))
        {
            if (partialDecoding)
            {
                if (cpy > oend) goto _output_error;                           /* Error : write attempt beyond end of output buffer */
                if ((endOnInput) && (ip+length > iend)) goto _output_error;   /* Error : read attempt beyond end of input buffer */
            }
            else
            {
                if ((!endOnInput) && (cpy != oend)) goto _output_error;       /* Error : block decoding must stop exactly there */
                if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) goto _output_error;   /* Error : input must be consumed */
            }
            memcpy(op, ip, length);
            ip += length;
            op += length;
            break;     /* Necessarily EOF, due to parsing restrictions */
        }
        LZ4_wildCopy(op, ip, cpy);
        ip += length; op = cpy;

        /* get offset */
        match = cpy - LZ4_readLE16(ip); ip+=2;
        if ((checkOffset) && (unlikely(match < lowLimit))) goto _output_error;   /* Error : offset outside destination buffer */

        /* get matchlength */
        length = token & ML_MASK;
        if (length == ML_MASK)
        {
            unsigned s;
            do
            {
                if ((endOnInput) && (ip > iend-LASTLITERALS)) goto _output_error;
                s = *ip++;
                length += s;
            } while (s==255);
            if ((safeDecode) && unlikely((size_t)(op+length)<(size_t)op)) goto _output_error;   /* overflow detection */
        }
        length += MINMATCH;

        /* check external dictionary */
        if ((dict==usingExtDict) && (match < lowPrefix))
        {
            if (unlikely(op+length > oend-LASTLITERALS)) goto _output_error;   /* doesn't respect parsing restriction */

            if (length <= (size_t)(lowPrefix-match))
            {
                /* match can be copied as a single segment from external dictionary */
                match = dictEnd - (lowPrefix-match);
                memmove(op, match, length); op += length;
            }
            else
            {
                /* match encompass external dictionary and current segment */
                size_t copySize = (size_t)(lowPrefix-match);
                memcpy(op, dictEnd - copySize, copySize);
                op += copySize;
                copySize = length - copySize;
                if (copySize > (size_t)(op-lowPrefix))   /* overlap within current segment */
                {
                    BYTE* const endOfMatch = op + copySize;
                    const BYTE* copyFrom = lowPrefix;
                    while (op < endOfMatch) *op++ = *copyFrom++;
                }
                else
                {
                    memcpy(op, lowPrefix, copySize);
                    op += copySize;
                }
            }
            continue;
        }

        /* copy repeated sequence */
        cpy = op + length;
        if (unlikely((op-match)<8))
        {
            const size_t dec64 = dec64table[op-match];
            op[0] = match[0];
            op[1] = match[1];
            op[2] = match[2];
            op[3] = match[3];
            match += dec32table[op-match];
            LZ4_copy4(op+4, match);
            op += 8; match -= dec64;
        } else { LZ4_copy8(op, match); op+=8; match+=8; }

        if (unlikely(cpy>oend-12))
        {
            if (cpy > oend-LASTLITERALS) goto _output_error;    /* Error : last LASTLITERALS bytes must be literals */
            if (op < oend-8)
            {
                LZ4_wildCopy(op, match, oend-8);
                match += (oend-8) - op;
                op = oend-8;
            }
            while (op<cpy) *op++ = *match++;
        }
        else
            LZ4_wildCopy(op, match, cpy);
        op=cpy;   /* correction */
    }

    /* end of decoding */
    if (endOnInput)
       return (int) (((char*)op)-dest);     /* Nb of output bytes decoded */
    else
       return (int) (((const char*)ip)-source);   /* Nb of input bytes read */

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