1 | // SPDX-License-Identifier: GPL-2.0-only |
2 | /* |
3 | * LZO1X Decompressor from LZO |
4 | * |
5 | * Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <markus@oberhumer.com> |
6 | * |
7 | * The full LZO package can be found at: |
8 | * http://www.oberhumer.com/opensource/lzo/ |
9 | * |
10 | * Changed for Linux kernel use by: |
11 | * Nitin Gupta <nitingupta910@gmail.com> |
12 | * Richard Purdie <rpurdie@openedhand.com> |
13 | */ |
14 | |
15 | #ifndef STATIC |
16 | #include <linux/module.h> |
17 | #include <linux/kernel.h> |
18 | #endif |
19 | #include <asm/unaligned.h> |
20 | #include <linux/lzo.h> |
21 | #include "lzodefs.h" |
22 | |
23 | #define HAVE_IP(x) ((size_t)(ip_end - ip) >= (size_t)(x)) |
24 | #define HAVE_OP(x) ((size_t)(op_end - op) >= (size_t)(x)) |
25 | #define NEED_IP(x) if (!HAVE_IP(x)) goto input_overrun |
26 | #define NEED_OP(x) if (!HAVE_OP(x)) goto output_overrun |
27 | #define TEST_LB(m_pos) if ((m_pos) < out) goto lookbehind_overrun |
28 | |
29 | /* This MAX_255_COUNT is the maximum number of times we can add 255 to a base |
30 | * count without overflowing an integer. The multiply will overflow when |
31 | * multiplying 255 by more than MAXINT/255. The sum will overflow earlier |
32 | * depending on the base count. Since the base count is taken from a u8 |
33 | * and a few bits, it is safe to assume that it will always be lower than |
34 | * or equal to 2*255, thus we can always prevent any overflow by accepting |
35 | * two less 255 steps. See Documentation/staging/lzo.rst for more information. |
36 | */ |
37 | #define MAX_255_COUNT ((((size_t)~0) / 255) - 2) |
38 | |
39 | int lzo1x_decompress_safe(const unsigned char *in, size_t in_len, |
40 | unsigned char *out, size_t *out_len) |
41 | { |
42 | unsigned char *op; |
43 | const unsigned char *ip; |
44 | size_t t, next; |
45 | size_t state = 0; |
46 | const unsigned char *m_pos; |
47 | const unsigned char * const ip_end = in + in_len; |
48 | unsigned char * const op_end = out + *out_len; |
49 | |
50 | unsigned char bitstream_version; |
51 | |
52 | op = out; |
53 | ip = in; |
54 | |
55 | if (unlikely(in_len < 3)) |
56 | goto input_overrun; |
57 | |
58 | if (likely(in_len >= 5) && likely(*ip == 17)) { |
59 | bitstream_version = ip[1]; |
60 | ip += 2; |
61 | } else { |
62 | bitstream_version = 0; |
63 | } |
64 | |
65 | if (*ip > 17) { |
66 | t = *ip++ - 17; |
67 | if (t < 4) { |
68 | next = t; |
69 | goto match_next; |
70 | } |
71 | goto copy_literal_run; |
72 | } |
73 | |
74 | for (;;) { |
75 | t = *ip++; |
76 | if (t < 16) { |
77 | if (likely(state == 0)) { |
78 | if (unlikely(t == 0)) { |
79 | size_t offset; |
80 | const unsigned char *ip_last = ip; |
81 | |
82 | while (unlikely(*ip == 0)) { |
83 | ip++; |
84 | NEED_IP(1); |
85 | } |
86 | offset = ip - ip_last; |
87 | if (unlikely(offset > MAX_255_COUNT)) |
88 | return LZO_E_ERROR; |
89 | |
90 | offset = (offset << 8) - offset; |
91 | t += offset + 15 + *ip++; |
92 | } |
93 | t += 3; |
94 | copy_literal_run: |
95 | #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) |
96 | if (likely(HAVE_IP(t + 15) && HAVE_OP(t + 15))) { |
97 | const unsigned char *ie = ip + t; |
98 | unsigned char *oe = op + t; |
99 | do { |
100 | COPY8(op, ip); |
101 | op += 8; |
102 | ip += 8; |
103 | COPY8(op, ip); |
104 | op += 8; |
105 | ip += 8; |
106 | } while (ip < ie); |
107 | ip = ie; |
108 | op = oe; |
109 | } else |
110 | #endif |
111 | { |
112 | NEED_OP(t); |
113 | NEED_IP(t + 3); |
114 | do { |
115 | *op++ = *ip++; |
116 | } while (--t > 0); |
117 | } |
118 | state = 4; |
119 | continue; |
120 | } else if (state != 4) { |
121 | next = t & 3; |
122 | m_pos = op - 1; |
123 | m_pos -= t >> 2; |
124 | m_pos -= *ip++ << 2; |
125 | TEST_LB(m_pos); |
126 | NEED_OP(2); |
127 | op[0] = m_pos[0]; |
128 | op[1] = m_pos[1]; |
129 | op += 2; |
130 | goto match_next; |
131 | } else { |
132 | next = t & 3; |
133 | m_pos = op - (1 + M2_MAX_OFFSET); |
134 | m_pos -= t >> 2; |
135 | m_pos -= *ip++ << 2; |
136 | t = 3; |
137 | } |
138 | } else if (t >= 64) { |
139 | next = t & 3; |
140 | m_pos = op - 1; |
141 | m_pos -= (t >> 2) & 7; |
142 | m_pos -= *ip++ << 3; |
143 | t = (t >> 5) - 1 + (3 - 1); |
144 | } else if (t >= 32) { |
145 | t = (t & 31) + (3 - 1); |
146 | if (unlikely(t == 2)) { |
147 | size_t offset; |
148 | const unsigned char *ip_last = ip; |
149 | |
150 | while (unlikely(*ip == 0)) { |
151 | ip++; |
152 | NEED_IP(1); |
153 | } |
154 | offset = ip - ip_last; |
155 | if (unlikely(offset > MAX_255_COUNT)) |
156 | return LZO_E_ERROR; |
157 | |
158 | offset = (offset << 8) - offset; |
159 | t += offset + 31 + *ip++; |
160 | NEED_IP(2); |
161 | } |
162 | m_pos = op - 1; |
163 | next = get_unaligned_le16(p: ip); |
164 | ip += 2; |
165 | m_pos -= next >> 2; |
166 | next &= 3; |
167 | } else { |
168 | NEED_IP(2); |
169 | next = get_unaligned_le16(p: ip); |
170 | if (((next & 0xfffc) == 0xfffc) && |
171 | ((t & 0xf8) == 0x18) && |
172 | likely(bitstream_version)) { |
173 | NEED_IP(3); |
174 | t &= 7; |
175 | t |= ip[2] << 3; |
176 | t += MIN_ZERO_RUN_LENGTH; |
177 | NEED_OP(t); |
178 | memset(op, 0, t); |
179 | op += t; |
180 | next &= 3; |
181 | ip += 3; |
182 | goto match_next; |
183 | } else { |
184 | m_pos = op; |
185 | m_pos -= (t & 8) << 11; |
186 | t = (t & 7) + (3 - 1); |
187 | if (unlikely(t == 2)) { |
188 | size_t offset; |
189 | const unsigned char *ip_last = ip; |
190 | |
191 | while (unlikely(*ip == 0)) { |
192 | ip++; |
193 | NEED_IP(1); |
194 | } |
195 | offset = ip - ip_last; |
196 | if (unlikely(offset > MAX_255_COUNT)) |
197 | return LZO_E_ERROR; |
198 | |
199 | offset = (offset << 8) - offset; |
200 | t += offset + 7 + *ip++; |
201 | NEED_IP(2); |
202 | next = get_unaligned_le16(p: ip); |
203 | } |
204 | ip += 2; |
205 | m_pos -= next >> 2; |
206 | next &= 3; |
207 | if (m_pos == op) |
208 | goto eof_found; |
209 | m_pos -= 0x4000; |
210 | } |
211 | } |
212 | TEST_LB(m_pos); |
213 | #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) |
214 | if (op - m_pos >= 8) { |
215 | unsigned char *oe = op + t; |
216 | if (likely(HAVE_OP(t + 15))) { |
217 | do { |
218 | COPY8(op, m_pos); |
219 | op += 8; |
220 | m_pos += 8; |
221 | COPY8(op, m_pos); |
222 | op += 8; |
223 | m_pos += 8; |
224 | } while (op < oe); |
225 | op = oe; |
226 | if (HAVE_IP(6)) { |
227 | state = next; |
228 | COPY4(op, ip); |
229 | op += next; |
230 | ip += next; |
231 | continue; |
232 | } |
233 | } else { |
234 | NEED_OP(t); |
235 | do { |
236 | *op++ = *m_pos++; |
237 | } while (op < oe); |
238 | } |
239 | } else |
240 | #endif |
241 | { |
242 | unsigned char *oe = op + t; |
243 | NEED_OP(t); |
244 | op[0] = m_pos[0]; |
245 | op[1] = m_pos[1]; |
246 | op += 2; |
247 | m_pos += 2; |
248 | do { |
249 | *op++ = *m_pos++; |
250 | } while (op < oe); |
251 | } |
252 | match_next: |
253 | state = next; |
254 | t = next; |
255 | #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) |
256 | if (likely(HAVE_IP(6) && HAVE_OP(4))) { |
257 | COPY4(op, ip); |
258 | op += t; |
259 | ip += t; |
260 | } else |
261 | #endif |
262 | { |
263 | NEED_IP(t + 3); |
264 | NEED_OP(t); |
265 | while (t > 0) { |
266 | *op++ = *ip++; |
267 | t--; |
268 | } |
269 | } |
270 | } |
271 | |
272 | eof_found: |
273 | *out_len = op - out; |
274 | return (t != 3 ? LZO_E_ERROR : |
275 | ip == ip_end ? LZO_E_OK : |
276 | ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN); |
277 | |
278 | input_overrun: |
279 | *out_len = op - out; |
280 | return LZO_E_INPUT_OVERRUN; |
281 | |
282 | output_overrun: |
283 | *out_len = op - out; |
284 | return LZO_E_OUTPUT_OVERRUN; |
285 | |
286 | lookbehind_overrun: |
287 | *out_len = op - out; |
288 | return LZO_E_LOOKBEHIND_OVERRUN; |
289 | } |
290 | #ifndef STATIC |
291 | EXPORT_SYMBOL_GPL(lzo1x_decompress_safe); |
292 | |
293 | MODULE_LICENSE("GPL" ); |
294 | MODULE_DESCRIPTION("LZO1X Decompressor" ); |
295 | |
296 | #endif |
297 | |