aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorRichard Purdie <rpurdie@openedhand.com>2007-07-10 20:22:24 -0400
committerLinus Torvalds <torvalds@woody.linux-foundation.org>2007-07-10 20:51:13 -0400
commit64c70b1cf43de158282bc1675918d503e5b15cc1 (patch)
treee7797ee372de94bb9129300e55d23034a7d05f9a
parent4c75f7416f51b0c6855952467a5db04f9c598f09 (diff)
Add LZO1X algorithm to the kernel
This is a hybrid version of the patch to add the LZO1X compression algorithm to the kernel. Nitin and myself have merged the best parts of the various patches to form this version which we're both happy with (and are jointly signing off). The performance of this version is equivalent to the original minilzo code it was based on. Bytecode comparisons have also been made on ARM, i386 and x86_64 with favourable results. There are several users of LZO lined up including jffs2, crypto and reiser4 since its much faster than zlib. Signed-off-by: Nitin Gupta <nitingupta910@gmail.com> Signed-off-by: Richard Purdie <rpurdie@openedhand.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat
-rw-r--r--include/linux/lzo.h44
-rw-r--r--lib/Kconfig6
-rw-r--r--lib/Makefile2
-rw-r--r--lib/lzo/Makefile5
-rw-r--r--lib/lzo/lzo1x_compress.c226
-rw-r--r--lib/lzo/lzo1x_decompress.c254
-rw-r--r--lib/lzo/lzodefs.h43
7 files changed, 580 insertions, 0 deletions
diff --git a/include/linux/lzo.h b/include/linux/lzo.h
new file mode 100644
index 000000000000..582d8b711a13
--- /dev/null
+++ b/include/linux/lzo.h
@@ -0,0 +1,44 @@
1#ifndef __LZO_H__
2#define __LZO_H__
3/*
4 * LZO Public Kernel Interface
5 * A mini subset of the LZO real-time data compression library
6 *
7 * Copyright (C) 1996-2005 Markus F.X.J. Oberhumer <markus@oberhumer.com>
8 *
9 * The full LZO package can be found at:
10 * http://www.oberhumer.com/opensource/lzo/
11 *
12 * Changed for kernel use by:
13 * Nitin Gupta <nitingupta910@gmail.com>
14 * Richard Purdie <rpurdie@openedhand.com>
15 */
16
17#define LZO1X_MEM_COMPRESS (16384 * sizeof(unsigned char *))
18#define LZO1X_1_MEM_COMPRESS LZO1X_MEM_COMPRESS
19
20#define lzo1x_worst_compress(x) (x + (x / 64) + 16 + 3)
21
22/* This requires 'workmem' of size LZO1X_1_MEM_COMPRESS */
23int lzo1x_1_compress(const unsigned char *src, size_t src_len,
24 unsigned char *dst, size_t *dst_len, void *wrkmem);
25
26/* safe decompression with overrun testing */
27int lzo1x_decompress_safe(const unsigned char *src, size_t src_len,
28 unsigned char *dst, size_t *dst_len);
29
30/*
31 * Return values (< 0 = Error)
32 */
33#define LZO_E_OK 0
34#define LZO_E_ERROR (-1)
35#define LZO_E_OUT_OF_MEMORY (-2)
36#define LZO_E_NOT_COMPRESSIBLE (-3)
37#define LZO_E_INPUT_OVERRUN (-4)
38#define LZO_E_OUTPUT_OVERRUN (-5)
39#define LZO_E_LOOKBEHIND_OVERRUN (-6)
40#define LZO_E_EOF_NOT_FOUND (-7)
41#define LZO_E_INPUT_NOT_CONSUMED (-8)
42#define LZO_E_NOT_YET_IMPLEMENTED (-9)
43
44#endif
diff --git a/lib/Kconfig b/lib/Kconfig
index 2e7ae6b9215b..3eb29d5dc4f5 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -64,6 +64,12 @@ config ZLIB_INFLATE
64config ZLIB_DEFLATE 64config ZLIB_DEFLATE
65 tristate 65 tristate
66 66
67config LZO_COMPRESS
68 tristate
69
70config LZO_DECOMPRESS
71 tristate
72
67# 73#
68# Generic allocator support is selected if needed 74# Generic allocator support is selected if needed
69# 75#
diff --git a/lib/Makefile b/lib/Makefile
index c8c8e20784ce..d1b366bdf86e 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -49,6 +49,8 @@ obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o
49obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/ 49obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
50obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/ 50obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/
51obj-$(CONFIG_REED_SOLOMON) += reed_solomon/ 51obj-$(CONFIG_REED_SOLOMON) += reed_solomon/
52obj-$(CONFIG_LZO_COMPRESS) += lzo/
53obj-$(CONFIG_LZO_DECOMPRESS) += lzo/
52 54
53obj-$(CONFIG_TEXTSEARCH) += textsearch.o 55obj-$(CONFIG_TEXTSEARCH) += textsearch.o
54obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o 56obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.o
diff --git a/lib/lzo/Makefile b/lib/lzo/Makefile
new file mode 100644
index 000000000000..e764116ea12d
--- /dev/null
+++ b/lib/lzo/Makefile
@@ -0,0 +1,5 @@
1lzo_compress-objs := lzo1x_compress.o
2lzo_decompress-objs := lzo1x_decompress.o
3
4obj-$(CONFIG_LZO_COMPRESS) += lzo_compress.o
5obj-$(CONFIG_LZO_DECOMPRESS) += lzo_decompress.o
diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
new file mode 100644
index 000000000000..c935f00073e9
--- /dev/null
+++ b/lib/lzo/lzo1x_compress.c
@@ -0,0 +1,226 @@
1/*
2 * LZO1X Compressor from MiniLZO
3 *
4 * Copyright (C) 1996-2005 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 kernel use by:
10 * Nitin Gupta <nitingupta910@gmail.com>
11 * Richard Purdie <rpurdie@openedhand.com>
12 */
13
14#include <linux/module.h>
15#include <linux/kernel.h>
16#include <linux/lzo.h>
17#include <asm/unaligned.h>
18#include "lzodefs.h"
19
20static noinline size_t
21_lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
22 unsigned char *out, size_t *out_len, void *wrkmem)
23{
24 const unsigned char * const in_end = in + in_len;
25 const unsigned char * const ip_end = in + in_len - M2_MAX_LEN - 5;
26 const unsigned char ** const dict = wrkmem;
27 const unsigned char *ip = in, *ii = ip;
28 const unsigned char *end, *m, *m_pos;
29 size_t m_off, m_len, dindex;
30 unsigned char *op = out;
31
32 ip += 4;
33
34 for (;;) {
35 dindex = ((0x21 * DX3(ip, 5, 5, 6)) >> 5) & D_MASK;
36 m_pos = dict[dindex];
37
38 if (m_pos < in)
39 goto literal;
40
41 if (ip == m_pos || (ip - m_pos) > M4_MAX_OFFSET)
42 goto literal;
43
44 m_off = ip - m_pos;
45 if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
46 goto try_match;
47
48 dindex = (dindex & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f);
49 m_pos = dict[dindex];
50
51 if (m_pos < in)
52 goto literal;
53
54 if (ip == m_pos || (ip - m_pos) > M4_MAX_OFFSET)
55 goto literal;
56
57 m_off = ip - m_pos;
58 if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
59 goto try_match;
60
61 goto literal;
62
63try_match:
64 if (get_unaligned((const unsigned short *)m_pos)
65 == get_unaligned((const unsigned short *)ip)) {
66 if (likely(m_pos[2] == ip[2]))
67 goto match;
68 }
69
70literal:
71 dict[dindex] = ip;
72 ++ip;
73 if (unlikely(ip >= ip_end))
74 break;
75 continue;
76
77match:
78 dict[dindex] = ip;
79 if (ip != ii) {
80 size_t t = ip - ii;
81
82 if (t <= 3) {
83 op[-2] |= t;
84 } else if (t <= 18) {
85 *op++ = (t - 3);
86 } else {
87 size_t tt = t - 18;
88
89 *op++ = 0;
90 while (tt > 255) {
91 tt -= 255;
92 *op++ = 0;
93 }
94 *op++ = tt;
95 }
96 do {
97 *op++ = *ii++;
98 } while (--t > 0);
99 }
100
101 ip += 3;
102 if (m_pos[3] != *ip++ || m_pos[4] != *ip++
103 || m_pos[5] != *ip++ || m_pos[6] != *ip++
104 || m_pos[7] != *ip++ || m_pos[8] != *ip++) {
105 --ip;
106 m_len = ip - ii;
107
108 if (m_off <= M2_MAX_OFFSET) {
109 m_off -= 1;
110 *op++ = (((m_len - 1) << 5)
111 | ((m_off & 7) << 2));
112 *op++ = (m_off >> 3);
113 } else if (m_off <= M3_MAX_OFFSET) {
114 m_off -= 1;
115 *op++ = (M3_MARKER | (m_len - 2));
116 goto m3_m4_offset;
117 } else {
118 m_off -= 0x4000;
119
120 *op++ = (M4_MARKER | ((m_off & 0x4000) >> 11)
121 | (m_len - 2));
122 goto m3_m4_offset;
123 }
124 } else {
125 end = in_end;
126 m = m_pos + M2_MAX_LEN + 1;
127
128 while (ip < end && *m == *ip) {
129 m++;
130 ip++;
131 }
132 m_len = ip - ii;
133
134 if (m_off <= M3_MAX_OFFSET) {
135 m_off -= 1;
136 if (m_len <= 33) {
137 *op++ = (M3_MARKER | (m_len - 2));
138 } else {
139 m_len -= 33;
140 *op++ = M3_MARKER | 0;
141 goto m3_m4_len;
142 }
143 } else {
144 m_off -= 0x4000;
145 if (m_len <= M4_MAX_LEN) {
146 *op++ = (M4_MARKER
147 | ((m_off & 0x4000) >> 11)
148 | (m_len - 2));
149 } else {
150 m_len -= M4_MAX_LEN;
151 *op++ = (M4_MARKER
152 | ((m_off & 0x4000) >> 11));
153m3_m4_len:
154 while (m_len > 255) {
155 m_len -= 255;
156 *op++ = 0;
157 }
158
159 *op++ = (m_len);
160 }
161 }
162m3_m4_offset:
163 *op++ = ((m_off & 63) << 2);
164 *op++ = (m_off >> 6);
165 }
166
167 ii = ip;
168 if (unlikely(ip >= ip_end))
169 break;
170 }
171
172 *out_len = op - out;
173 return in_end - ii;
174}
175
176int lzo1x_1_compress(const unsigned char *in, size_t in_len, unsigned char *out,
177 size_t *out_len, void *wrkmem)
178{
179 const unsigned char *ii;
180 unsigned char *op = out;
181 size_t t;
182
183 if (unlikely(in_len <= M2_MAX_LEN + 5)) {
184 t = in_len;
185 } else {
186 t = _lzo1x_1_do_compress(in, in_len, op, out_len, wrkmem);
187 op += *out_len;
188 }
189
190 if (t > 0) {
191 ii = in + in_len - t;
192
193 if (op == out && t <= 238) {
194 *op++ = (17 + t);
195 } else if (t <= 3) {
196 op[-2] |= t;
197 } else if (t <= 18) {
198 *op++ = (t - 3);
199 } else {
200 size_t tt = t - 18;
201
202 *op++ = 0;
203 while (tt > 255) {
204 tt -= 255;
205 *op++ = 0;
206 }
207
208 *op++ = tt;
209 }
210 do {
211 *op++ = *ii++;
212 } while (--t > 0);
213 }
214
215 *op++ = M4_MARKER | 1;
216 *op++ = 0;
217 *op++ = 0;
218
219 *out_len = op - out;
220 return LZO_E_OK;
221}
222EXPORT_SYMBOL_GPL(lzo1x_1_compress);
223
224MODULE_LICENSE("GPL");
225MODULE_DESCRIPTION("LZO1X-1 Compressor");
226
diff --git a/lib/lzo/lzo1x_decompress.c b/lib/lzo/lzo1x_decompress.c
new file mode 100644
index 000000000000..9dc7056e5520
--- /dev/null
+++ b/lib/lzo/lzo1x_decompress.c
@@ -0,0 +1,254 @@
1/*
2 * LZO1X Decompressor from MiniLZO
3 *
4 * Copyright (C) 1996-2005 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 kernel use by:
10 * Nitin Gupta <nitingupta910@gmail.com>
11 * Richard Purdie <rpurdie@openedhand.com>
12 */
13
14#include <linux/module.h>
15#include <linux/kernel.h>
16#include <linux/lzo.h>
17#include <asm/byteorder.h>
18#include <asm/unaligned.h>
19#include "lzodefs.h"
20
21#define HAVE_IP(x, ip_end, ip) ((size_t)(ip_end - ip) < (x))
22#define HAVE_OP(x, op_end, op) ((size_t)(op_end - op) < (x))
23#define HAVE_LB(m_pos, out, op) (m_pos < out || m_pos >= op)
24
25#define COPY4(dst, src) \
26 put_unaligned(get_unaligned((const u32 *)(src)), (u32 *)(dst))
27
28int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
29 unsigned char *out, size_t *out_len)
30{
31 const unsigned char * const ip_end = in + in_len;
32 unsigned char * const op_end = out + *out_len;
33 const unsigned char *ip = in, *m_pos;
34 unsigned char *op = out;
35 size_t t;
36
37 *out_len = 0;
38
39 if (*ip > 17) {
40 t = *ip++ - 17;
41 if (t < 4)
42 goto match_next;
43 if (HAVE_OP(t, op_end, op))
44 goto output_overrun;
45 if (HAVE_IP(t + 1, ip_end, ip))
46 goto input_overrun;
47 do {
48 *op++ = *ip++;
49 } while (--t > 0);
50 goto first_literal_run;
51 }
52
53 while ((ip < ip_end)) {
54 t = *ip++;
55 if (t >= 16)
56 goto match;
57 if (t == 0) {
58 if (HAVE_IP(1, ip_end, ip))
59 goto input_overrun;
60 while (*ip == 0) {
61 t += 255;
62 ip++;
63 if (HAVE_IP(1, ip_end, ip))
64 goto input_overrun;
65 }
66 t += 15 + *ip++;
67 }
68 if (HAVE_OP(t + 3, op_end, op))
69 goto output_overrun;
70 if (HAVE_IP(t + 4, ip_end, ip))
71 goto input_overrun;
72
73 COPY4(op, ip);
74 op += 4;
75 ip += 4;
76 if (--t > 0) {
77 if (t >= 4) {
78 do {
79 COPY4(op, ip);
80 op += 4;
81 ip += 4;
82 t -= 4;
83 } while (t >= 4);
84 if (t > 0) {
85 do {
86 *op++ = *ip++;
87 } while (--t > 0);
88 }
89 } else {
90 do {
91 *op++ = *ip++;
92 } while (--t > 0);
93 }
94 }
95
96first_literal_run:
97 t = *ip++;
98 if (t >= 16)
99 goto match;
100 m_pos = op - (1 + M2_MAX_OFFSET);
101 m_pos -= t >> 2;
102 m_pos -= *ip++ << 2;
103
104 if (HAVE_LB(m_pos, out, op))
105 goto lookbehind_overrun;
106
107 if (HAVE_OP(3, op_end, op))
108 goto output_overrun;
109 *op++ = *m_pos++;
110 *op++ = *m_pos++;
111 *op++ = *m_pos;
112
113 goto match_done;
114
115 do {
116match:
117 if (t >= 64) {
118 m_pos = op - 1;
119 m_pos -= (t >> 2) & 7;
120 m_pos -= *ip++ << 3;
121 t = (t >> 5) - 1;
122 if (HAVE_LB(m_pos, out, op))
123 goto lookbehind_overrun;
124 if (HAVE_OP(t + 3 - 1, op_end, op))
125 goto output_overrun;
126 goto copy_match;
127 } else if (t >= 32) {
128 t &= 31;
129 if (t == 0) {
130 if (HAVE_IP(1, ip_end, ip))
131 goto input_overrun;
132 while (*ip == 0) {
133 t += 255;
134 ip++;
135 if (HAVE_IP(1, ip_end, ip))
136 goto input_overrun;
137 }
138 t += 31 + *ip++;
139 }
140 m_pos = op - 1;
141 m_pos -= le16_to_cpu(get_unaligned(
142 (const unsigned short *)ip)) >> 2;
143 ip += 2;
144 } else if (t >= 16) {
145 m_pos = op;
146 m_pos -= (t & 8) << 11;
147
148 t &= 7;
149 if (t == 0) {
150 if (HAVE_IP(1, ip_end, ip))
151 goto input_overrun;
152 while (*ip == 0) {
153 t += 255;
154 ip++;
155 if (HAVE_IP(1, ip_end, ip))
156 goto input_overrun;
157 }
158 t += 7 + *ip++;
159 }
160 m_pos -= le16_to_cpu(get_unaligned(
161 (const unsigned short *)ip) >> 2);
162 ip += 2;
163 if (m_pos == op)
164 goto eof_found;
165 m_pos -= 0x4000;
166 } else {
167 m_pos = op - 1;
168 m_pos -= t >> 2;
169 m_pos -= *ip++ << 2;
170
171 if (HAVE_LB(m_pos, out, op))
172 goto lookbehind_overrun;
173 if (HAVE_OP(2, op_end, op))
174 goto output_overrun;
175
176 *op++ = *m_pos++;
177 *op++ = *m_pos;
178 goto match_done;
179 }
180
181 if (HAVE_LB(m_pos, out, op))
182 goto lookbehind_overrun;
183 if (HAVE_OP(t + 3 - 1, op_end, op))
184 goto output_overrun;
185
186 if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
187 COPY4(op, m_pos);
188 op += 4;
189 m_pos += 4;
190 t -= 4 - (3 - 1);
191 do {
192 COPY4(op, m_pos);
193 op += 4;
194 m_pos += 4;
195 t -= 4;
196 } while (t >= 4);
197 if (t > 0)
198 do {
199 *op++ = *m_pos++;
200 } while (--t > 0);
201 } else {
202copy_match:
203 *op++ = *m_pos++;
204 *op++ = *m_pos++;
205 do {
206 *op++ = *m_pos++;
207 } while (--t > 0);
208 }
209match_done:
210 t = ip[-2] & 3;
211 if (t == 0)
212 break;
213match_next:
214 if (HAVE_OP(t, op_end, op))
215 goto output_overrun;
216 if (HAVE_IP(t + 1, ip_end, ip))
217 goto input_overrun;
218
219 *op++ = *ip++;
220 if (t > 1) {
221 *op++ = *ip++;
222 if (t > 2)
223 *op++ = *ip++;
224 }
225
226 t = *ip++;
227 } while (ip < ip_end);
228 }
229
230 *out_len = op - out;
231 return LZO_E_EOF_NOT_FOUND;
232
233eof_found:
234 *out_len = op - out;
235 return (ip == ip_end ? LZO_E_OK :
236 (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
237input_overrun:
238 *out_len = op - out;
239 return LZO_E_INPUT_OVERRUN;
240
241output_overrun:
242 *out_len = op - out;
243 return LZO_E_OUTPUT_OVERRUN;
244
245lookbehind_overrun:
246 *out_len = op - out;
247 return LZO_E_LOOKBEHIND_OVERRUN;
248}
249
250EXPORT_SYMBOL_GPL(lzo1x_decompress_safe);
251
252MODULE_LICENSE("GPL");
253MODULE_DESCRIPTION("LZO1X Decompressor");
254
diff --git a/lib/lzo/lzodefs.h b/lib/lzo/lzodefs.h
new file mode 100644
index 000000000000..b6d482c492ef
--- /dev/null
+++ b/lib/lzo/lzodefs.h
@@ -0,0 +1,43 @@
1/*
2 * lzodefs.h -- architecture, OS and compiler specific defines
3 *
4 * Copyright (C) 1996-2005 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 kernel use by:
10 * Nitin Gupta <nitingupta910@gmail.com>
11 * Richard Purdie <rpurdie@openedhand.com>
12 */
13
14#define LZO_VERSION 0x2020
15#define LZO_VERSION_STRING "2.02"
16#define LZO_VERSION_DATE "Oct 17 2005"
17
18#define M1_MAX_OFFSET 0x0400
19#define M2_MAX_OFFSET 0x0800
20#define M3_MAX_OFFSET 0x4000
21#define M4_MAX_OFFSET 0xbfff
22
23#define M1_MIN_LEN 2
24#define M1_MAX_LEN 2
25#define M2_MIN_LEN 3
26#define M2_MAX_LEN 8
27#define M3_MIN_LEN 3
28#define M3_MAX_LEN 33
29#define M4_MIN_LEN 3
30#define M4_MAX_LEN 9
31
32#define M1_MARKER 0
33#define M2_MARKER 64
34#define M3_MARKER 32
35#define M4_MARKER 16
36
37#define D_BITS 14
38#define D_MASK ((1u << D_BITS) - 1)
39#define D_HIGH ((D_MASK >> 1) + 1)
40
41#define DX2(p, s1, s2) (((((size_t)((p)[2]) << (s2)) ^ (p)[1]) \
42 << (s1)) ^ (p)[0])
43#define DX3(p, s1, s2, s3) ((DX2((p)+1, s2, s3) << (s1)) ^ (p)[0])
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-14 20:59:56 -0500