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 | ||
206a81c1 GKH |
22 | #define HAVE_IP(t, x) \ |
23 | (((size_t)(ip_end - ip) >= (size_t)(t + x)) && \ | |
24 | (((t + x) >= t) && ((t + x) >= x))) | |
25 | ||
26 | #define HAVE_OP(t, x) \ | |
27 | (((size_t)(op_end - op) >= (size_t)(t + x)) && \ | |
28 | (((t + x) >= t) && ((t + x) >= x))) | |
29 | ||
30 | #define NEED_IP(t, x) \ | |
31 | do { \ | |
32 | if (!HAVE_IP(t, x)) \ | |
33 | goto input_overrun; \ | |
34 | } while (0) | |
35 | ||
36 | #define NEED_OP(t, x) \ | |
37 | do { \ | |
38 | if (!HAVE_OP(t, x)) \ | |
39 | goto output_overrun; \ | |
40 | } while (0) | |
41 | ||
42 | #define TEST_LB(m_pos) \ | |
43 | do { \ | |
44 | if ((m_pos) < out) \ | |
45 | goto lookbehind_overrun; \ | |
46 | } while (0) | |
64c70b1c RP |
47 | |
48 | int lzo1x_decompress_safe(const unsigned char *in, size_t in_len, | |
8b975bd3 | 49 | unsigned char *out, size_t *out_len) |
64c70b1c | 50 | { |
8b975bd3 MO |
51 | unsigned char *op; |
52 | const unsigned char *ip; | |
53 | size_t t, next; | |
54 | size_t state = 0; | |
55 | const unsigned char *m_pos; | |
64c70b1c RP |
56 | const unsigned char * const ip_end = in + in_len; |
57 | unsigned char * const op_end = out + *out_len; | |
64c70b1c | 58 | |
8b975bd3 MO |
59 | op = out; |
60 | ip = in; | |
64c70b1c | 61 | |
8b975bd3 MO |
62 | if (unlikely(in_len < 3)) |
63 | goto input_overrun; | |
64c70b1c RP |
64 | if (*ip > 17) { |
65 | t = *ip++ - 17; | |
8b975bd3 MO |
66 | if (t < 4) { |
67 | next = t; | |
64c70b1c | 68 | goto match_next; |
64c70b1c | 69 | } |
8b975bd3 MO |
70 | goto copy_literal_run; |
71 | } | |
64c70b1c | 72 | |
8b975bd3 | 73 | for (;;) { |
64c70b1c | 74 | t = *ip++; |
8b975bd3 MO |
75 | if (t < 16) { |
76 | if (likely(state == 0)) { | |
77 | if (unlikely(t == 0)) { | |
78 | while (unlikely(*ip == 0)) { | |
64c70b1c RP |
79 | t += 255; |
80 | ip++; | |
206a81c1 | 81 | NEED_IP(1, 0); |
64c70b1c | 82 | } |
8b975bd3 | 83 | t += 15 + *ip++; |
64c70b1c | 84 | } |
8b975bd3 MO |
85 | t += 3; |
86 | copy_literal_run: | |
87 | #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) | |
206a81c1 | 88 | if (likely(HAVE_IP(t, 15) && HAVE_OP(t, 15))) { |
8b975bd3 MO |
89 | const unsigned char *ie = ip + t; |
90 | unsigned char *oe = op + t; | |
91 | do { | |
92 | COPY8(op, ip); | |
93 | op += 8; | |
94 | ip += 8; | |
95 | COPY8(op, ip); | |
96 | op += 8; | |
97 | ip += 8; | |
98 | } while (ip < ie); | |
99 | ip = ie; | |
100 | op = oe; | |
101 | } else | |
102 | #endif | |
103 | { | |
206a81c1 GKH |
104 | NEED_OP(t, 0); |
105 | NEED_IP(t, 3); | |
8b975bd3 MO |
106 | do { |
107 | *op++ = *ip++; | |
108 | } while (--t > 0); | |
64c70b1c | 109 | } |
8b975bd3 MO |
110 | state = 4; |
111 | continue; | |
112 | } else if (state != 4) { | |
113 | next = t & 3; | |
64c70b1c RP |
114 | m_pos = op - 1; |
115 | m_pos -= t >> 2; | |
116 | m_pos -= *ip++ << 2; | |
8b975bd3 | 117 | TEST_LB(m_pos); |
206a81c1 | 118 | NEED_OP(2, 0); |
8b975bd3 MO |
119 | op[0] = m_pos[0]; |
120 | op[1] = m_pos[1]; | |
121 | op += 2; | |
122 | goto match_next; | |
123 | } else { | |
124 | next = t & 3; | |
125 | m_pos = op - (1 + M2_MAX_OFFSET); | |
126 | m_pos -= t >> 2; | |
127 | m_pos -= *ip++ << 2; | |
128 | t = 3; | |
64c70b1c | 129 | } |
8b975bd3 MO |
130 | } else if (t >= 64) { |
131 | next = t & 3; | |
132 | m_pos = op - 1; | |
133 | m_pos -= (t >> 2) & 7; | |
134 | m_pos -= *ip++ << 3; | |
135 | t = (t >> 5) - 1 + (3 - 1); | |
136 | } else if (t >= 32) { | |
137 | t = (t & 31) + (3 - 1); | |
138 | if (unlikely(t == 2)) { | |
139 | while (unlikely(*ip == 0)) { | |
140 | t += 255; | |
141 | ip++; | |
206a81c1 | 142 | NEED_IP(1, 0); |
8b975bd3 MO |
143 | } |
144 | t += 31 + *ip++; | |
206a81c1 | 145 | NEED_IP(2, 0); |
8b975bd3 MO |
146 | } |
147 | m_pos = op - 1; | |
148 | next = get_unaligned_le16(ip); | |
149 | ip += 2; | |
150 | m_pos -= next >> 2; | |
151 | next &= 3; | |
152 | } else { | |
153 | m_pos = op; | |
154 | m_pos -= (t & 8) << 11; | |
155 | t = (t & 7) + (3 - 1); | |
156 | if (unlikely(t == 2)) { | |
157 | while (unlikely(*ip == 0)) { | |
158 | t += 255; | |
159 | ip++; | |
206a81c1 | 160 | NEED_IP(1, 0); |
8b975bd3 MO |
161 | } |
162 | t += 7 + *ip++; | |
206a81c1 | 163 | NEED_IP(2, 0); |
8b975bd3 MO |
164 | } |
165 | next = get_unaligned_le16(ip); | |
166 | ip += 2; | |
167 | m_pos -= next >> 2; | |
168 | next &= 3; | |
169 | if (m_pos == op) | |
170 | goto eof_found; | |
171 | m_pos -= 0x4000; | |
172 | } | |
173 | TEST_LB(m_pos); | |
174 | #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) | |
175 | if (op - m_pos >= 8) { | |
176 | unsigned char *oe = op + t; | |
206a81c1 | 177 | if (likely(HAVE_OP(t, 15))) { |
64c70b1c | 178 | do { |
8b975bd3 MO |
179 | COPY8(op, m_pos); |
180 | op += 8; | |
181 | m_pos += 8; | |
182 | COPY8(op, m_pos); | |
183 | op += 8; | |
184 | m_pos += 8; | |
185 | } while (op < oe); | |
186 | op = oe; | |
206a81c1 | 187 | if (HAVE_IP(6, 0)) { |
8b975bd3 MO |
188 | state = next; |
189 | COPY4(op, ip); | |
190 | op += next; | |
191 | ip += next; | |
192 | continue; | |
193 | } | |
64c70b1c | 194 | } else { |
206a81c1 | 195 | NEED_OP(t, 0); |
64c70b1c RP |
196 | do { |
197 | *op++ = *m_pos++; | |
8b975bd3 | 198 | } while (op < oe); |
64c70b1c | 199 | } |
8b975bd3 MO |
200 | } else |
201 | #endif | |
202 | { | |
203 | unsigned char *oe = op + t; | |
206a81c1 | 204 | NEED_OP(t, 0); |
8b975bd3 MO |
205 | op[0] = m_pos[0]; |
206 | op[1] = m_pos[1]; | |
207 | op += 2; | |
208 | m_pos += 2; | |
209 | do { | |
210 | *op++ = *m_pos++; | |
211 | } while (op < oe); | |
212 | } | |
64c70b1c | 213 | match_next: |
8b975bd3 MO |
214 | state = next; |
215 | t = next; | |
216 | #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) | |
206a81c1 | 217 | if (likely(HAVE_IP(6, 0) && HAVE_OP(4, 0))) { |
8b975bd3 MO |
218 | COPY4(op, ip); |
219 | op += t; | |
220 | ip += t; | |
221 | } else | |
222 | #endif | |
223 | { | |
206a81c1 GKH |
224 | NEED_IP(t, 3); |
225 | NEED_OP(t, 0); | |
8b975bd3 | 226 | while (t > 0) { |
64c70b1c | 227 | *op++ = *ip++; |
8b975bd3 | 228 | t--; |
64c70b1c | 229 | } |
8b975bd3 | 230 | } |
64c70b1c RP |
231 | } |
232 | ||
64c70b1c RP |
233 | eof_found: |
234 | *out_len = op - out; | |
8b975bd3 MO |
235 | return (t != 3 ? LZO_E_ERROR : |
236 | ip == ip_end ? LZO_E_OK : | |
237 | ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN); | |
238 | ||
64c70b1c RP |
239 | input_overrun: |
240 | *out_len = op - out; | |
241 | return LZO_E_INPUT_OVERRUN; | |
242 | ||
243 | output_overrun: | |
244 | *out_len = op - out; | |
245 | return LZO_E_OUTPUT_OVERRUN; | |
246 | ||
247 | lookbehind_overrun: | |
248 | *out_len = op - out; | |
249 | return LZO_E_LOOKBEHIND_OVERRUN; | |
250 | } | |
7dd65feb | 251 | #ifndef STATIC |
64c70b1c RP |
252 | EXPORT_SYMBOL_GPL(lzo1x_decompress_safe); |
253 | ||
254 | MODULE_LICENSE("GPL"); | |
255 | MODULE_DESCRIPTION("LZO1X Decompressor"); | |
256 | ||
7dd65feb | 257 | #endif |