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