Root/
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 | |
20 | static 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 = ((size_t)(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 || ((size_t)(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 || ((size_t)(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 | |
63 | try_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 | |
70 | literal: |
71 | dict[dindex] = ip; |
72 | ++ip; |
73 | if (unlikely(ip >= ip_end)) |
74 | break; |
75 | continue; |
76 | |
77 | match: |
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)); |
153 | m3_m4_len: |
154 | while (m_len > 255) { |
155 | m_len -= 255; |
156 | *op++ = 0; |
157 | } |
158 | |
159 | *op++ = (m_len); |
160 | } |
161 | } |
162 | m3_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 | |
176 | int 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 | } |
222 | EXPORT_SYMBOL_GPL(lzo1x_1_compress); |
223 | |
224 | MODULE_LICENSE("GPL"); |
225 | MODULE_DESCRIPTION("LZO1X-1 Compressor"); |
226 | |
227 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9