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 op = out; 50 ip = in; 51 52 if (unlikely(in_len < 3)) 53 goto input_overrun; 54 if (*ip > 17) { 55 t = *ip++ - 17; 56 if (t < 4) { 57 next = t; 58 goto match_next; 59 } 60 goto copy_literal_run; 61 } 62 63 for (;;) { 64 t = *ip++; 65 if (t < 16) { 66 if (likely(state == 0)) { 67 if (unlikely(t == 0)) { 68 size_t offset; 69 const unsigned char *ip_last = ip; 70 71 while (unlikely(*ip == 0)) { 72 ip++; 73 NEED_IP(1); 74 } 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++; 81 } 82 t += 3; 83 copy_literal_run: 84 #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) 85 if (likely(HAVE_IP(t + 15) && HAVE_OP(t + 15))) { 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 { 101 NEED_OP(t); 102 NEED_IP(t + 3); 103 do { 104 *op++ = *ip++; 105 } while (--t > 0); 106 } 107 state = 4; 108 continue; 109 } else if (state != 4) { 110 next = t & 3; 111 m_pos = op - 1; 112 m_pos -= t >> 2; 113 m_pos -= *ip++ << 2; 114 TEST_LB(m_pos); 115 NEED_OP(2); 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; 126 } 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)) { 136 size_t offset; 137 const unsigned char *ip_last = ip; 138 139 while (unlikely(*ip == 0)) { 140 ip++; 141 NEED_IP(1); 142 } 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++; 149 NEED_IP(2); 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)) { 161 size_t offset; 162 const unsigned char *ip_last = ip; 163 164 while (unlikely(*ip == 0)) { 165 ip++; 166 NEED_IP(1); 167 } 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++; 174 NEED_IP(2); 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; 188 if (likely(HAVE_OP(t + 15))) { 189 do { 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; 198 if (HAVE_IP(6)) { 199 state = next; 200 COPY4(op, ip); 201 op += next; 202 ip += next; 203 continue; 204 } 205 } else { 206 NEED_OP(t); 207 do { 208 *op++ = *m_pos++; 209 } while (op < oe); 210 } 211 } else 212 #endif 213 { 214 unsigned char *oe = op + t; 215 NEED_OP(t); 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 } 224 match_next: 225 state = next; 226 t = next; 227 #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) 228 if (likely(HAVE_IP(6) && HAVE_OP(4))) { 229 COPY4(op, ip); 230 op += t; 231 ip += t; 232 } else 233 #endif 234 { 235 NEED_IP(t + 3); 236 NEED_OP(t); 237 while (t > 0) { 238 *op++ = *ip++; 239 t--; 240 } 241 } 242 } 243 244 eof_found: 245 *out_len = op - out; 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 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 } 262 #ifndef STATIC 263 EXPORT_SYMBOL_GPL(lzo1x_decompress_safe); 264 265 MODULE_LICENSE("GPL"); 266 MODULE_DESCRIPTION("LZO1X Decompressor"); 267 268 #endif 269