1b6bec26cSMarkus F.X.J. Oberhumer /* 28b975bd3SMarkus F.X.J. Oberhumer * LZO1X Decompressor from LZO 3b6bec26cSMarkus F.X.J. Oberhumer * 48b975bd3SMarkus F.X.J. Oberhumer * Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <markus@oberhumer.com> 5b6bec26cSMarkus F.X.J. Oberhumer * 6b6bec26cSMarkus F.X.J. Oberhumer * The full LZO package can be found at: 7b6bec26cSMarkus F.X.J. Oberhumer * http://www.oberhumer.com/opensource/lzo/ 8b6bec26cSMarkus F.X.J. Oberhumer * 98b975bd3SMarkus F.X.J. Oberhumer * Changed for Linux kernel use by: 10b6bec26cSMarkus F.X.J. Oberhumer * Nitin Gupta <nitingupta910@gmail.com> 11b6bec26cSMarkus F.X.J. Oberhumer * Richard Purdie <rpurdie@openedhand.com> 12b6bec26cSMarkus F.X.J. Oberhumer */ 13b6bec26cSMarkus F.X.J. Oberhumer 14b6bec26cSMarkus F.X.J. Oberhumer #ifndef STATIC 15b6bec26cSMarkus F.X.J. Oberhumer #include <linux/module.h> 16b6bec26cSMarkus F.X.J. Oberhumer #include <linux/kernel.h> 17b6bec26cSMarkus F.X.J. Oberhumer #endif 18b6bec26cSMarkus F.X.J. Oberhumer #include <asm/unaligned.h> 19b6bec26cSMarkus F.X.J. Oberhumer #include <linux/lzo.h> 20b6bec26cSMarkus F.X.J. Oberhumer #include "lzodefs.h" 21b6bec26cSMarkus F.X.J. Oberhumer 22af958a38SWilly Tarreau #define HAVE_IP(x) ((size_t)(ip_end - ip) >= (size_t)(x)) 23af958a38SWilly Tarreau #define HAVE_OP(x) ((size_t)(op_end - op) >= (size_t)(x)) 24af958a38SWilly Tarreau #define NEED_IP(x) if (!HAVE_IP(x)) goto input_overrun 25af958a38SWilly Tarreau #define NEED_OP(x) if (!HAVE_OP(x)) goto output_overrun 26af958a38SWilly Tarreau #define TEST_LB(m_pos) if ((m_pos) < out) goto lookbehind_overrun 27b6bec26cSMarkus F.X.J. Oberhumer 2872cf9012SWilly Tarreau /* This MAX_255_COUNT is the maximum number of times we can add 255 to a base 2972cf9012SWilly Tarreau * count without overflowing an integer. The multiply will overflow when 3072cf9012SWilly Tarreau * multiplying 255 by more than MAXINT/255. The sum will overflow earlier 3172cf9012SWilly Tarreau * depending on the base count. Since the base count is taken from a u8 3272cf9012SWilly Tarreau * and a few bits, it is safe to assume that it will always be lower than 3372cf9012SWilly Tarreau * or equal to 2*255, thus we can always prevent any overflow by accepting 3472cf9012SWilly Tarreau * two less 255 steps. See Documentation/lzo.txt for more information. 3572cf9012SWilly Tarreau */ 3672cf9012SWilly Tarreau #define MAX_255_COUNT ((((size_t)~0) / 255) - 2) 3772cf9012SWilly Tarreau 38b6bec26cSMarkus F.X.J. Oberhumer int lzo1x_decompress_safe(const unsigned char *in, size_t in_len, 39b6bec26cSMarkus F.X.J. Oberhumer unsigned char *out, size_t *out_len) 40b6bec26cSMarkus F.X.J. Oberhumer { 418b975bd3SMarkus F.X.J. Oberhumer unsigned char *op; 428b975bd3SMarkus F.X.J. Oberhumer const unsigned char *ip; 438b975bd3SMarkus F.X.J. Oberhumer size_t t, next; 448b975bd3SMarkus F.X.J. Oberhumer size_t state = 0; 458b975bd3SMarkus F.X.J. Oberhumer const unsigned char *m_pos; 46b6bec26cSMarkus F.X.J. Oberhumer const unsigned char * const ip_end = in + in_len; 47b6bec26cSMarkus F.X.J. Oberhumer unsigned char * const op_end = out + *out_len; 48b6bec26cSMarkus F.X.J. Oberhumer 498b975bd3SMarkus F.X.J. Oberhumer op = out; 508b975bd3SMarkus F.X.J. Oberhumer ip = in; 51b6bec26cSMarkus F.X.J. Oberhumer 528b975bd3SMarkus F.X.J. Oberhumer if (unlikely(in_len < 3)) 538b975bd3SMarkus F.X.J. Oberhumer goto input_overrun; 54b6bec26cSMarkus F.X.J. Oberhumer if (*ip > 17) { 55b6bec26cSMarkus F.X.J. Oberhumer t = *ip++ - 17; 568b975bd3SMarkus F.X.J. Oberhumer if (t < 4) { 578b975bd3SMarkus F.X.J. Oberhumer next = t; 58b6bec26cSMarkus F.X.J. Oberhumer goto match_next; 598b975bd3SMarkus F.X.J. Oberhumer } 608b975bd3SMarkus F.X.J. Oberhumer goto copy_literal_run; 61b6bec26cSMarkus F.X.J. Oberhumer } 62b6bec26cSMarkus F.X.J. Oberhumer 638b975bd3SMarkus F.X.J. Oberhumer for (;;) { 64b6bec26cSMarkus F.X.J. Oberhumer t = *ip++; 658b975bd3SMarkus F.X.J. Oberhumer if (t < 16) { 668b975bd3SMarkus F.X.J. Oberhumer if (likely(state == 0)) { 678b975bd3SMarkus F.X.J. Oberhumer if (unlikely(t == 0)) { 6872cf9012SWilly Tarreau size_t offset; 6972cf9012SWilly Tarreau const unsigned char *ip_last = ip; 7072cf9012SWilly Tarreau 718b975bd3SMarkus F.X.J. Oberhumer while (unlikely(*ip == 0)) { 72b6bec26cSMarkus F.X.J. Oberhumer ip++; 73af958a38SWilly Tarreau NEED_IP(1); 74b6bec26cSMarkus F.X.J. Oberhumer } 7572cf9012SWilly Tarreau offset = ip - ip_last; 7672cf9012SWilly Tarreau if (unlikely(offset > MAX_255_COUNT)) 7772cf9012SWilly Tarreau return LZO_E_ERROR; 7872cf9012SWilly Tarreau 7972cf9012SWilly Tarreau offset = (offset << 8) - offset; 8072cf9012SWilly Tarreau t += offset + 15 + *ip++; 81b6bec26cSMarkus F.X.J. Oberhumer } 828b975bd3SMarkus F.X.J. Oberhumer t += 3; 838b975bd3SMarkus F.X.J. Oberhumer copy_literal_run: 848b975bd3SMarkus F.X.J. Oberhumer #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) 85af958a38SWilly Tarreau if (likely(HAVE_IP(t + 15) && HAVE_OP(t + 15))) { 868b975bd3SMarkus F.X.J. Oberhumer const unsigned char *ie = ip + t; 878b975bd3SMarkus F.X.J. Oberhumer unsigned char *oe = op + t; 88b6bec26cSMarkus F.X.J. Oberhumer do { 898b975bd3SMarkus F.X.J. Oberhumer COPY8(op, ip); 908b975bd3SMarkus F.X.J. Oberhumer op += 8; 918b975bd3SMarkus F.X.J. Oberhumer ip += 8; 928b975bd3SMarkus F.X.J. Oberhumer COPY8(op, ip); 938b975bd3SMarkus F.X.J. Oberhumer op += 8; 948b975bd3SMarkus F.X.J. Oberhumer ip += 8; 958b975bd3SMarkus F.X.J. Oberhumer } while (ip < ie); 968b975bd3SMarkus F.X.J. Oberhumer ip = ie; 978b975bd3SMarkus F.X.J. Oberhumer op = oe; 988b975bd3SMarkus F.X.J. Oberhumer } else 998b975bd3SMarkus F.X.J. Oberhumer #endif 1008b975bd3SMarkus F.X.J. Oberhumer { 101af958a38SWilly Tarreau NEED_OP(t); 102af958a38SWilly Tarreau NEED_IP(t + 3); 103b6bec26cSMarkus F.X.J. Oberhumer do { 104b6bec26cSMarkus F.X.J. Oberhumer *op++ = *ip++; 105b6bec26cSMarkus F.X.J. Oberhumer } while (--t > 0); 106b6bec26cSMarkus F.X.J. Oberhumer } 1078b975bd3SMarkus F.X.J. Oberhumer state = 4; 1088b975bd3SMarkus F.X.J. Oberhumer continue; 1098b975bd3SMarkus F.X.J. Oberhumer } else if (state != 4) { 1108b975bd3SMarkus F.X.J. Oberhumer next = t & 3; 1118b975bd3SMarkus F.X.J. Oberhumer m_pos = op - 1; 1128b975bd3SMarkus F.X.J. Oberhumer m_pos -= t >> 2; 1138b975bd3SMarkus F.X.J. Oberhumer m_pos -= *ip++ << 2; 1148b975bd3SMarkus F.X.J. Oberhumer TEST_LB(m_pos); 115af958a38SWilly Tarreau NEED_OP(2); 1168b975bd3SMarkus F.X.J. Oberhumer op[0] = m_pos[0]; 1178b975bd3SMarkus F.X.J. Oberhumer op[1] = m_pos[1]; 1188b975bd3SMarkus F.X.J. Oberhumer op += 2; 1198b975bd3SMarkus F.X.J. Oberhumer goto match_next; 120b6bec26cSMarkus F.X.J. Oberhumer } else { 1218b975bd3SMarkus F.X.J. Oberhumer next = t & 3; 122b6bec26cSMarkus F.X.J. Oberhumer m_pos = op - (1 + M2_MAX_OFFSET); 123b6bec26cSMarkus F.X.J. Oberhumer m_pos -= t >> 2; 124b6bec26cSMarkus F.X.J. Oberhumer m_pos -= *ip++ << 2; 1258b975bd3SMarkus F.X.J. Oberhumer t = 3; 1268b975bd3SMarkus F.X.J. Oberhumer } 1278b975bd3SMarkus F.X.J. Oberhumer } else if (t >= 64) { 1288b975bd3SMarkus F.X.J. Oberhumer next = t & 3; 129b6bec26cSMarkus F.X.J. Oberhumer m_pos = op - 1; 130b6bec26cSMarkus F.X.J. Oberhumer m_pos -= (t >> 2) & 7; 131b6bec26cSMarkus F.X.J. Oberhumer m_pos -= *ip++ << 3; 1328b975bd3SMarkus F.X.J. Oberhumer t = (t >> 5) - 1 + (3 - 1); 133b6bec26cSMarkus F.X.J. Oberhumer } else if (t >= 32) { 1348b975bd3SMarkus F.X.J. Oberhumer t = (t & 31) + (3 - 1); 1358b975bd3SMarkus F.X.J. Oberhumer if (unlikely(t == 2)) { 13672cf9012SWilly Tarreau size_t offset; 13772cf9012SWilly Tarreau const unsigned char *ip_last = ip; 13872cf9012SWilly Tarreau 1398b975bd3SMarkus F.X.J. Oberhumer while (unlikely(*ip == 0)) { 140b6bec26cSMarkus F.X.J. Oberhumer ip++; 141af958a38SWilly Tarreau NEED_IP(1); 142b6bec26cSMarkus F.X.J. Oberhumer } 14372cf9012SWilly Tarreau offset = ip - ip_last; 14472cf9012SWilly Tarreau if (unlikely(offset > MAX_255_COUNT)) 14572cf9012SWilly Tarreau return LZO_E_ERROR; 14672cf9012SWilly Tarreau 14772cf9012SWilly Tarreau offset = (offset << 8) - offset; 14872cf9012SWilly Tarreau t += offset + 31 + *ip++; 149af958a38SWilly Tarreau NEED_IP(2); 150b6bec26cSMarkus F.X.J. Oberhumer } 151b6bec26cSMarkus F.X.J. Oberhumer m_pos = op - 1; 1528b975bd3SMarkus F.X.J. Oberhumer next = get_unaligned_le16(ip); 153b6bec26cSMarkus F.X.J. Oberhumer ip += 2; 1548b975bd3SMarkus F.X.J. Oberhumer m_pos -= next >> 2; 1558b975bd3SMarkus F.X.J. Oberhumer next &= 3; 1568b975bd3SMarkus F.X.J. Oberhumer } else { 157b6bec26cSMarkus F.X.J. Oberhumer m_pos = op; 158b6bec26cSMarkus F.X.J. Oberhumer m_pos -= (t & 8) << 11; 1598b975bd3SMarkus F.X.J. Oberhumer t = (t & 7) + (3 - 1); 1608b975bd3SMarkus F.X.J. Oberhumer if (unlikely(t == 2)) { 16172cf9012SWilly Tarreau size_t offset; 16272cf9012SWilly Tarreau const unsigned char *ip_last = ip; 16372cf9012SWilly Tarreau 1648b975bd3SMarkus F.X.J. Oberhumer while (unlikely(*ip == 0)) { 165b6bec26cSMarkus F.X.J. Oberhumer ip++; 166af958a38SWilly Tarreau NEED_IP(1); 167b6bec26cSMarkus F.X.J. Oberhumer } 16872cf9012SWilly Tarreau offset = ip - ip_last; 16972cf9012SWilly Tarreau if (unlikely(offset > MAX_255_COUNT)) 17072cf9012SWilly Tarreau return LZO_E_ERROR; 17172cf9012SWilly Tarreau 17272cf9012SWilly Tarreau offset = (offset << 8) - offset; 17372cf9012SWilly Tarreau t += offset + 7 + *ip++; 174af958a38SWilly Tarreau NEED_IP(2); 175b6bec26cSMarkus F.X.J. Oberhumer } 1768b975bd3SMarkus F.X.J. Oberhumer next = get_unaligned_le16(ip); 177b6bec26cSMarkus F.X.J. Oberhumer ip += 2; 1788b975bd3SMarkus F.X.J. Oberhumer m_pos -= next >> 2; 1798b975bd3SMarkus F.X.J. Oberhumer next &= 3; 180b6bec26cSMarkus F.X.J. Oberhumer if (m_pos == op) 181b6bec26cSMarkus F.X.J. Oberhumer goto eof_found; 182b6bec26cSMarkus F.X.J. Oberhumer m_pos -= 0x4000; 183b6bec26cSMarkus F.X.J. Oberhumer } 1848b975bd3SMarkus F.X.J. Oberhumer TEST_LB(m_pos); 1858b975bd3SMarkus F.X.J. Oberhumer #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) 1868b975bd3SMarkus F.X.J. Oberhumer if (op - m_pos >= 8) { 1878b975bd3SMarkus F.X.J. Oberhumer unsigned char *oe = op + t; 188af958a38SWilly Tarreau if (likely(HAVE_OP(t + 15))) { 189b6bec26cSMarkus F.X.J. Oberhumer do { 1908b975bd3SMarkus F.X.J. Oberhumer COPY8(op, m_pos); 1918b975bd3SMarkus F.X.J. Oberhumer op += 8; 1928b975bd3SMarkus F.X.J. Oberhumer m_pos += 8; 1938b975bd3SMarkus F.X.J. Oberhumer COPY8(op, m_pos); 1948b975bd3SMarkus F.X.J. Oberhumer op += 8; 1958b975bd3SMarkus F.X.J. Oberhumer m_pos += 8; 1968b975bd3SMarkus F.X.J. Oberhumer } while (op < oe); 1978b975bd3SMarkus F.X.J. Oberhumer op = oe; 198af958a38SWilly Tarreau if (HAVE_IP(6)) { 1998b975bd3SMarkus F.X.J. Oberhumer state = next; 2008b975bd3SMarkus F.X.J. Oberhumer COPY4(op, ip); 2018b975bd3SMarkus F.X.J. Oberhumer op += next; 2028b975bd3SMarkus F.X.J. Oberhumer ip += next; 2038b975bd3SMarkus F.X.J. Oberhumer continue; 204b6bec26cSMarkus F.X.J. Oberhumer } 2058b975bd3SMarkus F.X.J. Oberhumer } else { 206af958a38SWilly Tarreau NEED_OP(t); 2078b975bd3SMarkus F.X.J. Oberhumer do { 2088b975bd3SMarkus F.X.J. Oberhumer *op++ = *m_pos++; 2098b975bd3SMarkus F.X.J. Oberhumer } while (op < oe); 2108b975bd3SMarkus F.X.J. Oberhumer } 2118b975bd3SMarkus F.X.J. Oberhumer } else 2128b975bd3SMarkus F.X.J. Oberhumer #endif 2138b975bd3SMarkus F.X.J. Oberhumer { 2148b975bd3SMarkus F.X.J. Oberhumer unsigned char *oe = op + t; 215af958a38SWilly Tarreau NEED_OP(t); 2168b975bd3SMarkus F.X.J. Oberhumer op[0] = m_pos[0]; 2178b975bd3SMarkus F.X.J. Oberhumer op[1] = m_pos[1]; 2188b975bd3SMarkus F.X.J. Oberhumer op += 2; 2198b975bd3SMarkus F.X.J. Oberhumer m_pos += 2; 2208b975bd3SMarkus F.X.J. Oberhumer do { 2218b975bd3SMarkus F.X.J. Oberhumer *op++ = *m_pos++; 2228b975bd3SMarkus F.X.J. Oberhumer } while (op < oe); 2238b975bd3SMarkus F.X.J. Oberhumer } 224b6bec26cSMarkus F.X.J. Oberhumer match_next: 2258b975bd3SMarkus F.X.J. Oberhumer state = next; 2268b975bd3SMarkus F.X.J. Oberhumer t = next; 2278b975bd3SMarkus F.X.J. Oberhumer #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) 228af958a38SWilly Tarreau if (likely(HAVE_IP(6) && HAVE_OP(4))) { 2298b975bd3SMarkus F.X.J. Oberhumer COPY4(op, ip); 2308b975bd3SMarkus F.X.J. Oberhumer op += t; 2318b975bd3SMarkus F.X.J. Oberhumer ip += t; 2328b975bd3SMarkus F.X.J. Oberhumer } else 2338b975bd3SMarkus F.X.J. Oberhumer #endif 2348b975bd3SMarkus F.X.J. Oberhumer { 235af958a38SWilly Tarreau NEED_IP(t + 3); 236af958a38SWilly Tarreau NEED_OP(t); 2378b975bd3SMarkus F.X.J. Oberhumer while (t > 0) { 238b6bec26cSMarkus F.X.J. Oberhumer *op++ = *ip++; 2398b975bd3SMarkus F.X.J. Oberhumer t--; 240b6bec26cSMarkus F.X.J. Oberhumer } 241b6bec26cSMarkus F.X.J. Oberhumer } 2428b975bd3SMarkus F.X.J. Oberhumer } 243b6bec26cSMarkus F.X.J. Oberhumer 244b6bec26cSMarkus F.X.J. Oberhumer eof_found: 245b6bec26cSMarkus F.X.J. Oberhumer *out_len = op - out; 2468b975bd3SMarkus F.X.J. Oberhumer return (t != 3 ? LZO_E_ERROR : 2478b975bd3SMarkus F.X.J. Oberhumer ip == ip_end ? LZO_E_OK : 2488b975bd3SMarkus F.X.J. Oberhumer ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN); 2498b975bd3SMarkus F.X.J. Oberhumer 250b6bec26cSMarkus F.X.J. Oberhumer input_overrun: 251b6bec26cSMarkus F.X.J. Oberhumer *out_len = op - out; 252b6bec26cSMarkus F.X.J. Oberhumer return LZO_E_INPUT_OVERRUN; 253b6bec26cSMarkus F.X.J. Oberhumer 254b6bec26cSMarkus F.X.J. Oberhumer output_overrun: 255b6bec26cSMarkus F.X.J. Oberhumer *out_len = op - out; 256b6bec26cSMarkus F.X.J. Oberhumer return LZO_E_OUTPUT_OVERRUN; 257b6bec26cSMarkus F.X.J. Oberhumer 258b6bec26cSMarkus F.X.J. Oberhumer lookbehind_overrun: 259b6bec26cSMarkus F.X.J. Oberhumer *out_len = op - out; 260b6bec26cSMarkus F.X.J. Oberhumer return LZO_E_LOOKBEHIND_OVERRUN; 261b6bec26cSMarkus F.X.J. Oberhumer } 262b6bec26cSMarkus F.X.J. Oberhumer #ifndef STATIC 263b6bec26cSMarkus F.X.J. Oberhumer EXPORT_SYMBOL_GPL(lzo1x_decompress_safe); 264b6bec26cSMarkus F.X.J. Oberhumer 265b6bec26cSMarkus F.X.J. Oberhumer MODULE_LICENSE("GPL"); 266b6bec26cSMarkus F.X.J. Oberhumer MODULE_DESCRIPTION("LZO1X Decompressor"); 267b6bec26cSMarkus F.X.J. Oberhumer 268b6bec26cSMarkus F.X.J. Oberhumer #endif 269