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