blob: 569985d522d518a8992929d5924b6a5062ff9e93 [file] [log] [blame]
Richard Purdie64c70b12007-07-10 17:22:24 -07001/*
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +02002 * LZO1X Decompressor from LZO
Richard Purdie64c70b12007-07-10 17:22:24 -07003 *
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +02004 * Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <markus@oberhumer.com>
Richard Purdie64c70b12007-07-10 17:22:24 -07005 *
6 * The full LZO package can be found at:
7 * http://www.oberhumer.com/opensource/lzo/
8 *
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +02009 * Changed for Linux kernel use by:
Richard Purdie64c70b12007-07-10 17:22:24 -070010 * Nitin Gupta <nitingupta910@gmail.com>
11 * Richard Purdie <rpurdie@openedhand.com>
12 */
13
Albin Tonnerre7dd65fe2010-01-08 14:42:42 -080014#ifndef STATIC
Richard Purdie64c70b12007-07-10 17:22:24 -070015#include <linux/module.h>
16#include <linux/kernel.h>
Albin Tonnerre7dd65fe2010-01-08 14:42:42 -080017#endif
Richard Purdie64c70b12007-07-10 17:22:24 -070018#include <asm/unaligned.h>
Albin Tonnerre7dd65fe2010-01-08 14:42:42 -080019#include <linux/lzo.h>
Richard Purdie64c70b12007-07-10 17:22:24 -070020#include "lzodefs.h"
21
Willy Tarreauaf958a32014-09-27 12:31:36 +020022#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
Richard Purdie64c70b12007-07-10 17:22:24 -070027
28int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +020029 unsigned char *out, size_t *out_len)
Richard Purdie64c70b12007-07-10 17:22:24 -070030{
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +020031 unsigned char *op;
32 const unsigned char *ip;
33 size_t t, next;
34 size_t state = 0;
35 const unsigned char *m_pos;
Richard Purdie64c70b12007-07-10 17:22:24 -070036 const unsigned char * const ip_end = in + in_len;
37 unsigned char * const op_end = out + *out_len;
Richard Purdie64c70b12007-07-10 17:22:24 -070038
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +020039 op = out;
40 ip = in;
Richard Purdie64c70b12007-07-10 17:22:24 -070041
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +020042 if (unlikely(in_len < 3))
43 goto input_overrun;
Richard Purdie64c70b12007-07-10 17:22:24 -070044 if (*ip > 17) {
45 t = *ip++ - 17;
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +020046 if (t < 4) {
47 next = t;
Richard Purdie64c70b12007-07-10 17:22:24 -070048 goto match_next;
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +020049 }
50 goto copy_literal_run;
Richard Purdie64c70b12007-07-10 17:22:24 -070051 }
52
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +020053 for (;;) {
Richard Purdie64c70b12007-07-10 17:22:24 -070054 t = *ip++;
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +020055 if (t < 16) {
56 if (likely(state == 0)) {
57 if (unlikely(t == 0)) {
58 while (unlikely(*ip == 0)) {
59 t += 255;
60 ip++;
Willy Tarreauaf958a32014-09-27 12:31:36 +020061 NEED_IP(1);
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +020062 }
63 t += 15 + *ip++;
64 }
65 t += 3;
66copy_literal_run:
67#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
Willy Tarreauaf958a32014-09-27 12:31:36 +020068 if (likely(HAVE_IP(t + 15) && HAVE_OP(t + 15))) {
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +020069 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 {
Willy Tarreauaf958a32014-09-27 12:31:36 +020084 NEED_OP(t);
85 NEED_IP(t + 3);
Richard Purdie64c70b12007-07-10 17:22:24 -070086 do {
87 *op++ = *ip++;
88 } while (--t > 0);
89 }
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +020090 state = 4;
91 continue;
92 } else if (state != 4) {
93 next = t & 3;
Richard Purdie64c70b12007-07-10 17:22:24 -070094 m_pos = op - 1;
95 m_pos -= t >> 2;
96 m_pos -= *ip++ << 2;
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +020097 TEST_LB(m_pos);
Willy Tarreauaf958a32014-09-27 12:31:36 +020098 NEED_OP(2);
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +020099 op[0] = m_pos[0];
100 op[1] = m_pos[1];
101 op += 2;
102 goto match_next;
Richard Purdie64c70b12007-07-10 17:22:24 -0700103 } else {
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +0200104 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++;
Willy Tarreauaf958a32014-09-27 12:31:36 +0200122 NEED_IP(1);
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +0200123 }
124 t += 31 + *ip++;
Willy Tarreauaf958a32014-09-27 12:31:36 +0200125 NEED_IP(2);
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +0200126 }
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++;
Willy Tarreauaf958a32014-09-27 12:31:36 +0200140 NEED_IP(1);
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +0200141 }
142 t += 7 + *ip++;
Willy Tarreauaf958a32014-09-27 12:31:36 +0200143 NEED_IP(2);
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +0200144 }
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;
Willy Tarreauaf958a32014-09-27 12:31:36 +0200157 if (likely(HAVE_OP(t + 15))) {
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +0200158 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;
Willy Tarreauaf958a32014-09-27 12:31:36 +0200167 if (HAVE_IP(6)) {
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +0200168 state = next;
169 COPY4(op, ip);
170 op += next;
171 ip += next;
172 continue;
173 }
174 } else {
Willy Tarreauaf958a32014-09-27 12:31:36 +0200175 NEED_OP(t);
Richard Purdie64c70b12007-07-10 17:22:24 -0700176 do {
177 *op++ = *m_pos++;
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +0200178 } while (op < oe);
Richard Purdie64c70b12007-07-10 17:22:24 -0700179 }
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +0200180 } else
181#endif
182 {
183 unsigned char *oe = op + t;
Willy Tarreauaf958a32014-09-27 12:31:36 +0200184 NEED_OP(t);
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +0200185 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 }
Richard Purdie64c70b12007-07-10 17:22:24 -0700193match_next:
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +0200194 state = next;
195 t = next;
196#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
Willy Tarreauaf958a32014-09-27 12:31:36 +0200197 if (likely(HAVE_IP(6) && HAVE_OP(4))) {
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +0200198 COPY4(op, ip);
199 op += t;
200 ip += t;
201 } else
202#endif
203 {
Willy Tarreauaf958a32014-09-27 12:31:36 +0200204 NEED_IP(t + 3);
205 NEED_OP(t);
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +0200206 while (t > 0) {
Richard Purdie64c70b12007-07-10 17:22:24 -0700207 *op++ = *ip++;
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +0200208 t--;
Richard Purdie64c70b12007-07-10 17:22:24 -0700209 }
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +0200210 }
Richard Purdie64c70b12007-07-10 17:22:24 -0700211 }
212
Richard Purdie64c70b12007-07-10 17:22:24 -0700213eof_found:
214 *out_len = op - out;
Markus F.X.J. Oberhumer8b975bd2012-08-13 17:25:44 +0200215 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
Richard Purdie64c70b12007-07-10 17:22:24 -0700219input_overrun:
220 *out_len = op - out;
221 return LZO_E_INPUT_OVERRUN;
222
223output_overrun:
224 *out_len = op - out;
225 return LZO_E_OUTPUT_OVERRUN;
226
227lookbehind_overrun:
228 *out_len = op - out;
229 return LZO_E_LOOKBEHIND_OVERRUN;
230}
Albin Tonnerre7dd65fe2010-01-08 14:42:42 -0800231#ifndef STATIC
Richard Purdie64c70b12007-07-10 17:22:24 -0700232EXPORT_SYMBOL_GPL(lzo1x_decompress_safe);
233
234MODULE_LICENSE("GPL");
235MODULE_DESCRIPTION("LZO1X Decompressor");
236
Albin Tonnerre7dd65fe2010-01-08 14:42:42 -0800237#endif