297 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*3 * LZO1X Decompressor from LZO4 *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 STATIC16#include <linux/module.h>17#include <linux/kernel.h>18#endif19#include <linux/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_overrun26#define NEED_OP(x) if (!HAVE_OP(x)) goto output_overrun27#define TEST_LB(m_pos) if ((m_pos) < out) goto lookbehind_overrun28 29/* This MAX_255_COUNT is the maximum number of times we can add 255 to a base30 * count without overflowing an integer. The multiply will overflow when31 * multiplying 255 by more than MAXINT/255. The sum will overflow earlier32 * depending on the base count. Since the base count is taken from a u833 * and a few bits, it is safe to assume that it will always be lower than34 * or equal to 2*255, thus we can always prevent any overflow by accepting35 * two less 255 steps. See Documentation/staging/lzo.rst for more information.36 */37#define MAX_255_COUNT ((((size_t)~0) / 255) - 2)38 39int 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;94copy_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 } else110#endif111 {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 } else240#endif241 {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 }252match_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 } else261#endif262 {263 NEED_IP(t + 3);264 NEED_OP(t);265 while (t > 0) {266 *op++ = *ip++;267 t--;268 }269 }270 }271 272eof_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 278input_overrun:279 *out_len = op - out;280 return LZO_E_INPUT_OVERRUN;281 282output_overrun:283 *out_len = op - out;284 return LZO_E_OUTPUT_OVERRUN;285 286lookbehind_overrun:287 *out_len = op - out;288 return LZO_E_LOOKBEHIND_OVERRUN;289}290#ifndef STATIC291EXPORT_SYMBOL_GPL(lzo1x_decompress_safe);292 293MODULE_LICENSE("GPL");294MODULE_DESCRIPTION("LZO1X Decompressor");295 296#endif297