/src/u-boot/lib/lzo/lzo1x_decompress.c

Source
/*
 *  LZO1X Decompressor from MiniLZO
 *
 *  Copyright (C) 1996-2005 Markus F.X.J. Oberhumer <markus@oberhumer.com>
 *
 *  The full LZO package can be found at:
 *  http://www.oberhumer.com/opensource/lzo/
 *
 *  Changed for kernel use by:
 *  Nitin Gupta <nitingupta910@gmail.com>
 *  Richard Purdie <rpurdie@openedhand.com>
 */

#include <linux/kernel.h>
#include <linux/lzo.h>
#include <linux/string.h>
#include <asm/byteorder.h>
#include <asm/unaligned.h>
#include "lzodefs.h"

#define HAVE_IP(x, ip_end, ip) ((size_t)(ip_end - ip) < (x))
#define HAVE_OP(x, op_end, op) ((size_t)(op_end - op) < (x))
#define HAVE_LB(m_pos, out, op) (m_pos < out || m_pos >= op)

#define COPY4(dst, src) \
    put_unaligned(get_unaligned((const u32 *)(src)), (u32 *)(dst))

static const unsigned char lzop_magic[] = {
  0x89, 0x4c, 0x5a, 0x4f, 0x00, 0x0d, 0x0a, 0x1a, 0x0a
};

#define HEADER_HAS_FILTER 0x00000800L

bool lzop_is_valid_header(const unsigned char *src)
{
  int i;
  /* read magic: 9 first bytes */
  for (i = 0; i < ARRAY_SIZE(lzop_magic); i++) {
    if (*src++ != lzop_magic[i])
      return false;
  }
  return true;
}

static inline const unsigned char *parse_header(const unsigned char *src)
{
  u16 version;
  int i;

  if (!lzop_is_valid_header(src))
    return NULL;

  /* skip header */
  src += 9;

  /* get version (2bytes), skip library version (2),
   * 'need to be extracted' version (2) and
   * method (1) */
  version = get_unaligned_be16(src);
  src += 7;
  if (version >= 0x0940)
    src++;
  if (get_unaligned_be32(src) & HEADER_HAS_FILTER)
    src += 4; /* filter info */

  /* skip flags, mode and mtime_low */
  src += 12;
  if (version >= 0x0940)
    src += 4; /* skip mtime_high */

  i = *src++;
  /* don't care about the file name, and skip checksum */
  src += i + 4;

  return src;
}

int lzop_decompress(const unsigned char *src, size_t src_len,
        unsigned char *dst, size_t *dst_len)
{
  unsigned char *start = dst;
  const unsigned char *send = src + src_len;
  u32 slen, dlen;
  size_t tmp, remaining;
  int r;

  src = parse_header(src);
  if (!src)
    return LZO_E_ERROR;

  remaining = *dst_len;
  while (src < send) {
    /* read uncompressed block size */
    dlen = get_unaligned_be32(src);
    src += 4;

    /* exit if last block */
    if (dlen == 0) {
      *dst_len = dst - start;
      return LZO_E_OK;
    }

    /* read compressed block size, and skip block checksum info */
    slen = get_unaligned_be32(src);
    src += 8;

    if (slen <= 0 || slen > dlen)
      return LZO_E_ERROR;

    /* abort if buffer ran out of room */
    if (dlen > remaining)
      return LZO_E_OUTPUT_OVERRUN;

    /* When the input data is not compressed at all,
     * lzo1x_decompress_safe will fail, so call memcpy()
     * instead */
    if (dlen == slen) {
      memcpy(dst, src, slen);
    } else {
      /* decompress */
      tmp = dlen;
      r = lzo1x_decompress_safe((u8 *)src, slen, dst, &tmp);

      if (r != LZO_E_OK) {
        *dst_len = dst - start;
        return r;
      }

      if (dlen != tmp)
        return LZO_E_ERROR;
    }

    src += slen;
    dst += dlen;
    remaining -= dlen;
  }

  return LZO_E_INPUT_OVERRUN;
}

int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
      unsigned char *out, size_t *out_len)
{
  const unsigned char * const ip_end = in + in_len;
  unsigned char * const op_end = out + *out_len;
  const unsigned char *ip = in, *m_pos;
  unsigned char *op = out;
  size_t t;

  *out_len = 0;

  if (*ip > 17) {
    t = *ip++ - 17;
    if (t < 4)
      goto match_next;
    if (HAVE_OP(t, op_end, op))
      goto output_overrun;
    if (HAVE_IP(t + 1, ip_end, ip))
      goto input_overrun;
    do {
      *op++ = *ip++;
    } while (--t > 0);
    goto first_literal_run;
  }

  while ((ip < ip_end)) {
    t = *ip++;
    if (t >= 16)
      goto match;
    if (t == 0) {
      if (HAVE_IP(1, ip_end, ip))
        goto input_overrun;
      while (*ip == 0) {
        t += 255;
        ip++;
        if (HAVE_IP(1, ip_end, ip))
          goto input_overrun;
      }
      t += 15 + *ip++;
    }
    if (HAVE_OP(t + 3, op_end, op))
      goto output_overrun;
    if (HAVE_IP(t + 4, ip_end, ip))
      goto input_overrun;

    COPY4(op, ip);
    op += 4;
    ip += 4;
    if (--t > 0) {
      if (t >= 4) {
        do {
          COPY4(op, ip);
          op += 4;
          ip += 4;
          t -= 4;
        } while (t >= 4);
        if (t > 0) {
          do {
            *op++ = *ip++;
          } while (--t > 0);
        }
      } else {
        do {
          *op++ = *ip++;
        } while (--t > 0);
      }
    }

first_literal_run:
    t = *ip++;
    if (t >= 16)
      goto match;
    m_pos = op - (1 + M2_MAX_OFFSET);
    m_pos -= t >> 2;
    m_pos -= *ip++ << 2;

    if (HAVE_LB(m_pos, out, op))
      goto lookbehind_overrun;

    if (HAVE_OP(3, op_end, op))
      goto output_overrun;
    *op++ = *m_pos++;
    *op++ = *m_pos++;
    *op++ = *m_pos;

    goto match_done;

    do {
match:
      if (t >= 64) {
        m_pos = op - 1;
        m_pos -= (t >> 2) & 7;
        m_pos -= *ip++ << 3;
        t = (t >> 5) - 1;
        if (HAVE_LB(m_pos, out, op))
          goto lookbehind_overrun;
        if (HAVE_OP(t + 3 - 1, op_end, op))
          goto output_overrun;
        goto copy_match;
      } else if (t >= 32) {
        t &= 31;
        if (t == 0) {
          if (HAVE_IP(1, ip_end, ip))
            goto input_overrun;
          while (*ip == 0) {
            t += 255;
            ip++;
            if (HAVE_IP(1, ip_end, ip))
              goto input_overrun;
          }
          t += 31 + *ip++;
        }
        m_pos = op - 1;
        m_pos -= get_unaligned_le16(ip) >> 2;
        ip += 2;
      } else if (t >= 16) {
        m_pos = op;
        m_pos -= (t & 8) << 11;

        t &= 7;
        if (t == 0) {
          if (HAVE_IP(1, ip_end, ip))
            goto input_overrun;
          while (*ip == 0) {
            t += 255;
            ip++;
            if (HAVE_IP(1, ip_end, ip))
              goto input_overrun;
          }
          t += 7 + *ip++;
        }
        m_pos -= get_unaligned_le16(ip) >> 2;
        ip += 2;
        if (m_pos == op)
          goto eof_found;
        m_pos -= 0x4000;
      } else {
        m_pos = op - 1;
        m_pos -= t >> 2;
        m_pos -= *ip++ << 2;

        if (HAVE_LB(m_pos, out, op))
          goto lookbehind_overrun;
        if (HAVE_OP(2, op_end, op))
          goto output_overrun;

        *op++ = *m_pos++;
        *op++ = *m_pos;
        goto match_done;
      }

      if (HAVE_LB(m_pos, out, op))
        goto lookbehind_overrun;
      if (HAVE_OP(t + 3 - 1, op_end, op))
        goto output_overrun;

      if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
        COPY4(op, m_pos);
        op += 4;
        m_pos += 4;
        t -= 4 - (3 - 1);
        do {
          COPY4(op, m_pos);
          op += 4;
          m_pos += 4;
          t -= 4;
        } while (t >= 4);
        if (t > 0)
          do {
            *op++ = *m_pos++;
          } while (--t > 0);
      } else {
copy_match:
        *op++ = *m_pos++;
        *op++ = *m_pos++;
        do {
          *op++ = *m_pos++;
        } while (--t > 0);
      }
match_done:
      t = ip[-2] & 3;
      if (t == 0)
        break;
match_next:
      if (HAVE_OP(t, op_end, op))
        goto output_overrun;
      if (HAVE_IP(t + 1, ip_end, ip))
        goto input_overrun;

      *op++ = *ip++;
      if (t > 1) {
        *op++ = *ip++;
        if (t > 2)
          *op++ = *ip++;
      }

      t = *ip++;
    } while (ip < ip_end);
  }

  *out_len = op - out;
  return LZO_E_EOF_NOT_FOUND;

eof_found:
  *out_len = op - out;
  return (ip == ip_end ? LZO_E_OK :
    (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
input_overrun:
  *out_len = op - out;
  return LZO_E_INPUT_OVERRUN;

output_overrun:
  *out_len = op - out;
  return LZO_E_OUTPUT_OVERRUN;

lookbehind_overrun:
  *out_len = op - out;
  return LZO_E_LOOKBEHIND_OVERRUN;
}

Coverage Report

Created: 2026-03-11 06:21

Line	Count	Source
1		/*
2		* LZO1X Decompressor from MiniLZO
3		*
4		* Copyright (C) 1996-2005 Markus F.X.J. Oberhumer <markus@oberhumer.com>
5		*
6		* The full LZO package can be found at:
7		* http://www.oberhumer.com/opensource/lzo/
8		*
9		* Changed for kernel use by:
10		* Nitin Gupta <nitingupta910@gmail.com>
11		* Richard Purdie <rpurdie@openedhand.com>
12		*/
13
14		#include <linux/kernel.h>
15		#include <linux/lzo.h>
16		#include <linux/string.h>
17		#include <asm/byteorder.h>
18		#include <asm/unaligned.h>
19		#include "lzodefs.h"
20
21	0	#define HAVE_IP(x, ip_end, ip) ((size_t)(ip_end - ip) < (x))
22	0	#define HAVE_OP(x, op_end, op) ((size_t)(op_end - op) < (x))
23	0	#define HAVE_LB(m_pos, out, op) (m_pos < out \|\| m_pos >= op)
24
25		#define COPY4(dst, src) \
26	0	put_unaligned(get_unaligned((const u32 )(src)), (u32 )(dst))
27
28		static const unsigned char lzop_magic[] = {
29		0x89, 0x4c, 0x5a, 0x4f, 0x00, 0x0d, 0x0a, 0x1a, 0x0a
30		};
31
32	0	#define HEADER_HAS_FILTER 0x00000800L
33
34		bool lzop_is_valid_header(const unsigned char *src)
35	0	{
36	0	int i;
37		/* read magic: 9 first bytes */
38	0	for (i = 0; i < ARRAY_SIZE(lzop_magic); i++) {
39	0	if (*src++ != lzop_magic[i])
40	0	return false;
41	0	}
42	0	return true;
43	0	}
44
45		static inline const unsigned char parse_header(const unsigned char src)
46	0	{
47	0	u16 version;
48	0	int i;
49
50	0	if (!lzop_is_valid_header(src))
51	0	return NULL;
52
53		/* skip header */
54	0	src += 9;
55
56		/* get version (2bytes), skip library version (2),
57		* 'need to be extracted' version (2) and
58		* method (1) */
59	0	version = get_unaligned_be16(src);
60	0	src += 7;
61	0	if (version >= 0x0940)
62	0	src++;
63	0	if (get_unaligned_be32(src) & HEADER_HAS_FILTER)
64	0	src += 4; /* filter info */
65
66		/* skip flags, mode and mtime_low */
67	0	src += 12;
68	0	if (version >= 0x0940)
69	0	src += 4; /* skip mtime_high */
70
71	0	i = *src++;
72		/* don't care about the file name, and skip checksum */
73	0	src += i + 4;
74
75	0	return src;
76	0	}
77
78		int lzop_decompress(const unsigned char *src, size_t src_len,
79		unsigned char dst, size_t dst_len)
80	0	{
81	0	unsigned char *start = dst;
82	0	const unsigned char *send = src + src_len;
83	0	u32 slen, dlen;
84	0	size_t tmp, remaining;
85	0	int r;
86
87	0	src = parse_header(src);
88	0	if (!src)
89	0	return LZO_E_ERROR;
90
91	0	remaining = *dst_len;
92	0	while (src < send) {
93		/* read uncompressed block size */
94	0	dlen = get_unaligned_be32(src);
95	0	src += 4;
96
97		/* exit if last block */
98	0	if (dlen == 0) {
99	0	*dst_len = dst - start;
100	0	return LZO_E_OK;
101	0	}
102
103		/* read compressed block size, and skip block checksum info */
104	0	slen = get_unaligned_be32(src);
105	0	src += 8;
106
107	0	if (slen <= 0 \|\| slen > dlen)
108	0	return LZO_E_ERROR;
109
110		/* abort if buffer ran out of room */
111	0	if (dlen > remaining)
112	0	return LZO_E_OUTPUT_OVERRUN;
113
114		/* When the input data is not compressed at all,
115		* lzo1x_decompress_safe will fail, so call memcpy()
116		* instead */
117	0	if (dlen == slen) {
118	0	memcpy(dst, src, slen);
119	0	} else {
120		/* decompress */
121	0	tmp = dlen;
122	0	r = lzo1x_decompress_safe((u8 *)src, slen, dst, &tmp);
123
124	0	if (r != LZO_E_OK) {
125	0	*dst_len = dst - start;
126	0	return r;
127	0	}
128
129	0	if (dlen != tmp)
130	0	return LZO_E_ERROR;
131	0	}
132
133	0	src += slen;
134	0	dst += dlen;
135	0	remaining -= dlen;
136	0	}
137
138	0	return LZO_E_INPUT_OVERRUN;
139	0	}
140
141		int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
142		unsigned char out, size_t out_len)
143	0	{
144	0	const unsigned char * const ip_end = in + in_len;
145	0	unsigned char * const op_end = out + *out_len;
146	0	const unsigned char ip = in, m_pos;
147	0	unsigned char *op = out;
148	0	size_t t;
149
150	0	*out_len = 0;
151
152	0	if (*ip > 17) {
153	0	t = *ip++ - 17;
154	0	if (t < 4)
155	0	goto match_next;
156	0	if (HAVE_OP(t, op_end, op))
157	0	goto output_overrun;
158	0	if (HAVE_IP(t + 1, ip_end, ip))
159	0	goto input_overrun;
160	0	do {
161	0	op++ = ip++;
162	0	} while (--t > 0);
163	0	goto first_literal_run;
164	0	}
165
166	0	while ((ip < ip_end)) {
167	0	t = *ip++;
168	0	if (t >= 16)
169	0	goto match;
170	0	if (t == 0) {
171	0	if (HAVE_IP(1, ip_end, ip))
172	0	goto input_overrun;
173	0	while (*ip == 0) {
174	0	t += 255;
175	0	ip++;
176	0	if (HAVE_IP(1, ip_end, ip))
177	0	goto input_overrun;
178	0	}
179	0	t += 15 + *ip++;
180	0	}
181	0	if (HAVE_OP(t + 3, op_end, op))
182	0	goto output_overrun;
183	0	if (HAVE_IP(t + 4, ip_end, ip))
184	0	goto input_overrun;
185
186	0	COPY4(op, ip);
187	0	op += 4;
188	0	ip += 4;
189	0	if (--t > 0) {
190	0	if (t >= 4) {
191	0	do {
192	0	COPY4(op, ip);
193	0	op += 4;
194	0	ip += 4;
195	0	t -= 4;
196	0	} while (t >= 4);
197	0	if (t > 0) {
198	0	do {
199	0	op++ = ip++;
200	0	} while (--t > 0);
201	0	}
202	0	} else {
203	0	do {
204	0	op++ = ip++;
205	0	} while (--t > 0);
206	0	}
207	0	}
208
209	0	first_literal_run:
210	0	t = *ip++;
211	0	if (t >= 16)
212	0	goto match;
213	0	m_pos = op - (1 + M2_MAX_OFFSET);
214	0	m_pos -= t >> 2;
215	0	m_pos -= *ip++ << 2;
216
217	0	if (HAVE_LB(m_pos, out, op))
218	0	goto lookbehind_overrun;
219
220	0	if (HAVE_OP(3, op_end, op))
221	0	goto output_overrun;
222	0	op++ = m_pos++;
223	0	op++ = m_pos++;
224	0	op++ = m_pos;
225
226	0	goto match_done;
227
228	0	do {
229	0	match:
230	0	if (t >= 64) {
231	0	m_pos = op - 1;
232	0	m_pos -= (t >> 2) & 7;
233	0	m_pos -= *ip++ << 3;
234	0	t = (t >> 5) - 1;
235	0	if (HAVE_LB(m_pos, out, op))
236	0	goto lookbehind_overrun;
237	0	if (HAVE_OP(t + 3 - 1, op_end, op))
238	0	goto output_overrun;
239	0	goto copy_match;
240	0	} else if (t >= 32) {
241	0	t &= 31;
242	0	if (t == 0) {
243	0	if (HAVE_IP(1, ip_end, ip))
244	0	goto input_overrun;
245	0	while (*ip == 0) {
246	0	t += 255;
247	0	ip++;
248	0	if (HAVE_IP(1, ip_end, ip))
249	0	goto input_overrun;
250	0	}
251	0	t += 31 + *ip++;
252	0	}
253	0	m_pos = op - 1;
254	0	m_pos -= get_unaligned_le16(ip) >> 2;
255	0	ip += 2;
256	0	} else if (t >= 16) {
257	0	m_pos = op;
258	0	m_pos -= (t & 8) << 11;
259
260	0	t &= 7;
261	0	if (t == 0) {
262	0	if (HAVE_IP(1, ip_end, ip))
263	0	goto input_overrun;
264	0	while (*ip == 0) {
265	0	t += 255;
266	0	ip++;
267	0	if (HAVE_IP(1, ip_end, ip))
268	0	goto input_overrun;
269	0	}
270	0	t += 7 + *ip++;
271	0	}
272	0	m_pos -= get_unaligned_le16(ip) >> 2;
273	0	ip += 2;
274	0	if (m_pos == op)
275	0	goto eof_found;
276	0	m_pos -= 0x4000;
277	0	} else {
278	0	m_pos = op - 1;
279	0	m_pos -= t >> 2;
280	0	m_pos -= *ip++ << 2;
281
282	0	if (HAVE_LB(m_pos, out, op))
283	0	goto lookbehind_overrun;
284	0	if (HAVE_OP(2, op_end, op))
285	0	goto output_overrun;
286
287	0	op++ = m_pos++;
288	0	op++ = m_pos;
289	0	goto match_done;
290	0	}
291
292	0	if (HAVE_LB(m_pos, out, op))
293	0	goto lookbehind_overrun;
294	0	if (HAVE_OP(t + 3 - 1, op_end, op))
295	0	goto output_overrun;
296
297	0	if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
298	0	COPY4(op, m_pos);
299	0	op += 4;
300	0	m_pos += 4;
301	0	t -= 4 - (3 - 1);
302	0	do {
303	0	COPY4(op, m_pos);
304	0	op += 4;
305	0	m_pos += 4;
306	0	t -= 4;
307	0	} while (t >= 4);
308	0	if (t > 0)
309	0	do {
310	0	op++ = m_pos++;
311	0	} while (--t > 0);
312	0	} else {
313	0	copy_match:
314	0	op++ = m_pos++;
315	0	op++ = m_pos++;
316	0	do {
317	0	op++ = m_pos++;
318	0	} while (--t > 0);
319	0	}
320	0	match_done:
321	0	t = ip[-2] & 3;
322	0	if (t == 0)
323	0	break;
324	0	match_next:
325	0	if (HAVE_OP(t, op_end, op))
326	0	goto output_overrun;
327	0	if (HAVE_IP(t + 1, ip_end, ip))
328	0	goto input_overrun;
329
330	0	op++ = ip++;
331	0	if (t > 1) {
332	0	op++ = ip++;
333	0	if (t > 2)
334	0	op++ = ip++;
335	0	}
336
337	0	t = *ip++;
338	0	} while (ip < ip_end);
339	0	}
340
341	0	*out_len = op - out;
342	0	return LZO_E_EOF_NOT_FOUND;
343
344	0	eof_found:
345	0	*out_len = op - out;
346	0	return (ip == ip_end ? LZO_E_OK :
347	0	(ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
348	0	input_overrun:
349	0	*out_len = op - out;
350	0	return LZO_E_INPUT_OVERRUN;
351
352	0	output_overrun:
353	0	*out_len = op - out;
354	0	return LZO_E_OUTPUT_OVERRUN;
355
356	0	lookbehind_overrun:
357	0	*out_len = op - out;
358	0	return LZO_E_LOOKBEHIND_OVERRUN;
359	0	}