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