1 /* 2 * LZO1X Decompressor from LZO 3 * 4 * Copyright (C) 1996-2012 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 Linux kernel use by: 10 * Nitin Gupta <nitingupta910@gmail.com> 11 * Richard Purdie <rpurdie@openedhand.com> 12 */ 13 14 #ifndef STATIC 15 #include <linux/module.h> 16 #include <linux/kernel.h> 17 #endif 18 #include <asm/unaligned.h> 19 #include <linux/lzo.h> 20 #include "lzodefs.h" 21 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 27 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 38 int lzo1x_decompress_safe(const unsigned char *in, size_t in_len, 39 unsigned char *out, size_t *out_len) 40 { 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; 46 const unsigned char * const ip_end = in + in_len; 47 unsigned char * const op_end = out + *out_len; 48 49 unsigned char bitstream_version; 50 51 op = out; 52 ip = in; 53 54 if (unlikely(in_len < 3)) 55 goto input_overrun; 56 57 if (likely(in_len >= 5) && likely(*ip == 17)) { 58 bitstream_version = ip[1]; 59 ip += 2; 60 } else { 61 bitstream_version = 0; 62 } 63 64 if (*ip > 17) { 65 t = *ip++ - 17; 66 if (t < 4) { 67 next = t; 68 goto match_next; 69 } 70 goto copy_literal_run; 71 } 72 73 for (;;) { 74 t = *ip++; 75 if (t < 16) { 76 if (likely(state == 0)) { 77 if (unlikely(t == 0)) { 78 size_t offset; 79 const unsigned char *ip_last = ip; 80 81 while (unlikely(*ip == 0)) { 82 ip++; 83 NEED_IP(1); 84 } 85 offset = ip - ip_last; 86 if (unlikely(offset > MAX_255_COUNT)) 87 return LZO_E_ERROR; 88 89 offset = (offset << 8) - offset; 90 t += offset + 15 + *ip++; 91 } 92 t += 3; 93 copy_literal_run: 94 #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) 95 if (likely(HAVE_IP(t + 15) && HAVE_OP(t + 15))) { 96 const unsigned char *ie = ip + t; 97 unsigned char *oe = op + t; 98 do { 99 COPY8(op, ip); 100 op += 8; 101 ip += 8; 102 COPY8(op, ip); 103 op += 8; 104 ip += 8; 105 } while (ip < ie); 106 ip = ie; 107 op = oe; 108 } else 109 #endif 110 { 111 NEED_OP(t); 112 NEED_IP(t + 3); 113 do { 114 *op++ = *ip++; 115 } while (--t > 0); 116 } 117 state = 4; 118 continue; 119 } else if (state != 4) { 120 next = t & 3; 121 m_pos = op - 1; 122 m_pos -= t >> 2; 123 m_pos -= *ip++ << 2; 124 TEST_LB(m_pos); 125 NEED_OP(2); 126 op[0] = m_pos[0]; 127 op[1] = m_pos[1]; 128 op += 2; 129 goto match_next; 130 } else { 131 next = t & 3; 132 m_pos = op - (1 + M2_MAX_OFFSET); 133 m_pos -= t >> 2; 134 m_pos -= *ip++ << 2; 135 t = 3; 136 } 137 } else if (t >= 64) { 138 next = t & 3; 139 m_pos = op - 1; 140 m_pos -= (t >> 2) & 7; 141 m_pos -= *ip++ << 3; 142 t = (t >> 5) - 1 + (3 - 1); 143 } else if (t >= 32) { 144 t = (t & 31) + (3 - 1); 145 if (unlikely(t == 2)) { 146 size_t offset; 147 const unsigned char *ip_last = ip; 148 149 while (unlikely(*ip == 0)) { 150 ip++; 151 NEED_IP(1); 152 } 153 offset = ip - ip_last; 154 if (unlikely(offset > MAX_255_COUNT)) 155 return LZO_E_ERROR; 156 157 offset = (offset << 8) - offset; 158 t += offset + 31 + *ip++; 159 NEED_IP(2); 160 } 161 m_pos = op - 1; 162 next = get_unaligned_le16(ip); 163 ip += 2; 164 m_pos -= next >> 2; 165 next &= 3; 166 } else { 167 NEED_IP(2); 168 next = get_unaligned_le16(ip); 169 if (((next & 0xfffc) == 0xfffc) && 170 ((t & 0xf8) == 0x18) && 171 likely(bitstream_version)) { 172 NEED_IP(3); 173 t &= 7; 174 t |= ip[2] << 3; 175 t += MIN_ZERO_RUN_LENGTH; 176 NEED_OP(t); 177 memset(op, 0, t); 178 op += t; 179 next &= 3; 180 ip += 3; 181 goto match_next; 182 } else { 183 m_pos = op; 184 m_pos -= (t & 8) << 11; 185 t = (t & 7) + (3 - 1); 186 if (unlikely(t == 2)) { 187 size_t offset; 188 const unsigned char *ip_last = ip; 189 190 while (unlikely(*ip == 0)) { 191 ip++; 192 NEED_IP(1); 193 } 194 offset = ip - ip_last; 195 if (unlikely(offset > MAX_255_COUNT)) 196 return LZO_E_ERROR; 197 198 offset = (offset << 8) - offset; 199 t += offset + 7 + *ip++; 200 NEED_IP(2); 201 next = get_unaligned_le16(ip); 202 } 203 ip += 2; 204 m_pos -= next >> 2; 205 next &= 3; 206 if (m_pos == op) 207 goto eof_found; 208 m_pos -= 0x4000; 209 } 210 } 211 TEST_LB(m_pos); 212 #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) 213 if (op - m_pos >= 8) { 214 unsigned char *oe = op + t; 215 if (likely(HAVE_OP(t + 15))) { 216 do { 217 COPY8(op, m_pos); 218 op += 8; 219 m_pos += 8; 220 COPY8(op, m_pos); 221 op += 8; 222 m_pos += 8; 223 } while (op < oe); 224 op = oe; 225 if (HAVE_IP(6)) { 226 state = next; 227 COPY4(op, ip); 228 op += next; 229 ip += next; 230 continue; 231 } 232 } else { 233 NEED_OP(t); 234 do { 235 *op++ = *m_pos++; 236 } while (op < oe); 237 } 238 } else 239 #endif 240 { 241 unsigned char *oe = op + t; 242 NEED_OP(t); 243 op[0] = m_pos[0]; 244 op[1] = m_pos[1]; 245 op += 2; 246 m_pos += 2; 247 do { 248 *op++ = *m_pos++; 249 } while (op < oe); 250 } 251 match_next: 252 state = next; 253 t = next; 254 #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) 255 if (likely(HAVE_IP(6) && HAVE_OP(4))) { 256 COPY4(op, ip); 257 op += t; 258 ip += t; 259 } else 260 #endif 261 { 262 NEED_IP(t + 3); 263 NEED_OP(t); 264 while (t > 0) { 265 *op++ = *ip++; 266 t--; 267 } 268 } 269 } 270 271 eof_found: 272 *out_len = op - out; 273 return (t != 3 ? LZO_E_ERROR : 274 ip == ip_end ? LZO_E_OK : 275 ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN); 276 277 input_overrun: 278 *out_len = op - out; 279 return LZO_E_INPUT_OVERRUN; 280 281 output_overrun: 282 *out_len = op - out; 283 return LZO_E_OUTPUT_OVERRUN; 284 285 lookbehind_overrun: 286 *out_len = op - out; 287 return LZO_E_LOOKBEHIND_OVERRUN; 288 } 289 #ifndef STATIC 290 EXPORT_SYMBOL_GPL(lzo1x_decompress_safe); 291 292 MODULE_LICENSE("GPL"); 293 MODULE_DESCRIPTION("LZO1X Decompressor"); 294 295 #endif 296