Annotation of /trunk/mkinitrd-magellan/busybox/archival/lzo1x_c.c
Parent Directory | Revision Log
Revision 984 -
(hide annotations)
(download)
Sun May 30 11:32:42 2010 UTC (13 years, 11 months ago) by niro
File MIME type: text/plain
File size: 7045 byte(s)
Sun May 30 11:32:42 2010 UTC (13 years, 11 months ago) by niro
File MIME type: text/plain
File size: 7045 byte(s)
-updated to busybox-1.16.1 and enabled blkid/uuid support in default config
1 | niro | 984 | /* implementation of the LZO1[XY]-1 compression algorithm |
2 | |||
3 | This file is part of the LZO real-time data compression library. | ||
4 | |||
5 | Copyright (C) 1996..2008 Markus Franz Xaver Johannes Oberhumer | ||
6 | All Rights Reserved. | ||
7 | |||
8 | Markus F.X.J. Oberhumer <markus@oberhumer.com> | ||
9 | http://www.oberhumer.com/opensource/lzo/ | ||
10 | |||
11 | The LZO library is free software; you can redistribute it and/or | ||
12 | modify it under the terms of the GNU General Public License as | ||
13 | published by the Free Software Foundation; either version 2 of | ||
14 | the License, or (at your option) any later version. | ||
15 | |||
16 | The LZO library is distributed in the hope that it will be useful, | ||
17 | but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
18 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
19 | GNU General Public License for more details. | ||
20 | |||
21 | You should have received a copy of the GNU General Public License | ||
22 | along with the LZO library; see the file COPYING. | ||
23 | If not, write to the Free Software Foundation, Inc., | ||
24 | 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. | ||
25 | */ | ||
26 | |||
27 | /*********************************************************************** | ||
28 | // compress a block of data. | ||
29 | ************************************************************************/ | ||
30 | static NOINLINE unsigned | ||
31 | do_compress(const uint8_t* in, unsigned in_len, | ||
32 | uint8_t* out, unsigned* out_len, | ||
33 | void* wrkmem) | ||
34 | { | ||
35 | register const uint8_t* ip; | ||
36 | uint8_t* op; | ||
37 | const uint8_t* const in_end = in + in_len; | ||
38 | const uint8_t* const ip_end = in + in_len - M2_MAX_LEN - 5; | ||
39 | const uint8_t* ii; | ||
40 | const void* *const dict = (const void**) wrkmem; | ||
41 | |||
42 | op = out; | ||
43 | ip = in; | ||
44 | ii = ip; | ||
45 | |||
46 | ip += 4; | ||
47 | for (;;) { | ||
48 | register const uint8_t* m_pos; | ||
49 | unsigned m_off; | ||
50 | unsigned m_len; | ||
51 | unsigned dindex; | ||
52 | |||
53 | D_INDEX1(dindex,ip); | ||
54 | GINDEX(m_pos,m_off,dict,dindex,in); | ||
55 | if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET)) | ||
56 | goto literal; | ||
57 | #if 1 | ||
58 | if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3]) | ||
59 | goto try_match; | ||
60 | D_INDEX2(dindex,ip); | ||
61 | #endif | ||
62 | GINDEX(m_pos,m_off,dict,dindex,in); | ||
63 | if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET)) | ||
64 | goto literal; | ||
65 | if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3]) | ||
66 | goto try_match; | ||
67 | goto literal; | ||
68 | |||
69 | try_match: | ||
70 | #if 1 && defined(LZO_UNALIGNED_OK_2) | ||
71 | if (* (const lzo_ushortp) m_pos != * (const lzo_ushortp) ip) | ||
72 | #else | ||
73 | if (m_pos[0] != ip[0] || m_pos[1] != ip[1]) | ||
74 | #endif | ||
75 | { | ||
76 | } else { | ||
77 | if (m_pos[2] == ip[2]) { | ||
78 | #if 0 | ||
79 | if (m_off <= M2_MAX_OFFSET) | ||
80 | goto match; | ||
81 | if (lit <= 3) | ||
82 | goto match; | ||
83 | if (lit == 3) { /* better compression, but slower */ | ||
84 | assert(op - 2 > out); op[-2] |= (uint8_t)(3); | ||
85 | *op++ = *ii++; *op++ = *ii++; *op++ = *ii++; | ||
86 | goto code_match; | ||
87 | } | ||
88 | if (m_pos[3] == ip[3]) | ||
89 | #endif | ||
90 | goto match; | ||
91 | } | ||
92 | else { | ||
93 | /* still need a better way for finding M1 matches */ | ||
94 | #if 0 | ||
95 | /* a M1 match */ | ||
96 | #if 0 | ||
97 | if (m_off <= M1_MAX_OFFSET && lit > 0 && lit <= 3) | ||
98 | #else | ||
99 | if (m_off <= M1_MAX_OFFSET && lit == 3) | ||
100 | #endif | ||
101 | { | ||
102 | register unsigned t; | ||
103 | |||
104 | t = lit; | ||
105 | assert(op - 2 > out); op[-2] |= (uint8_t)(t); | ||
106 | do *op++ = *ii++; while (--t > 0); | ||
107 | assert(ii == ip); | ||
108 | m_off -= 1; | ||
109 | *op++ = (uint8_t)(M1_MARKER | ((m_off & 3) << 2)); | ||
110 | *op++ = (uint8_t)(m_off >> 2); | ||
111 | ip += 2; | ||
112 | goto match_done; | ||
113 | } | ||
114 | #endif | ||
115 | } | ||
116 | } | ||
117 | |||
118 | /* a literal */ | ||
119 | literal: | ||
120 | UPDATE_I(dict, 0, dindex, ip, in); | ||
121 | ++ip; | ||
122 | if (ip >= ip_end) | ||
123 | break; | ||
124 | continue; | ||
125 | |||
126 | /* a match */ | ||
127 | match: | ||
128 | UPDATE_I(dict, 0, dindex, ip, in); | ||
129 | /* store current literal run */ | ||
130 | if (pd(ip, ii) > 0) { | ||
131 | register unsigned t = pd(ip, ii); | ||
132 | |||
133 | if (t <= 3) { | ||
134 | assert(op - 2 > out); | ||
135 | op[-2] |= (uint8_t)(t); | ||
136 | } | ||
137 | else if (t <= 18) | ||
138 | *op++ = (uint8_t)(t - 3); | ||
139 | else { | ||
140 | register unsigned tt = t - 18; | ||
141 | |||
142 | *op++ = 0; | ||
143 | while (tt > 255) { | ||
144 | tt -= 255; | ||
145 | *op++ = 0; | ||
146 | } | ||
147 | assert(tt > 0); | ||
148 | *op++ = (uint8_t)(tt); | ||
149 | } | ||
150 | do *op++ = *ii++; while (--t > 0); | ||
151 | } | ||
152 | |||
153 | /* code the match */ | ||
154 | assert(ii == ip); | ||
155 | ip += 3; | ||
156 | if (m_pos[3] != *ip++ || m_pos[4] != *ip++ || m_pos[5] != *ip++ | ||
157 | || m_pos[6] != *ip++ || m_pos[7] != *ip++ || m_pos[8] != *ip++ | ||
158 | #ifdef LZO1Y | ||
159 | || m_pos[ 9] != *ip++ || m_pos[10] != *ip++ || m_pos[11] != *ip++ | ||
160 | || m_pos[12] != *ip++ || m_pos[13] != *ip++ || m_pos[14] != *ip++ | ||
161 | #endif | ||
162 | ) { | ||
163 | --ip; | ||
164 | m_len = pd(ip, ii); | ||
165 | assert(m_len >= 3); | ||
166 | assert(m_len <= M2_MAX_LEN); | ||
167 | |||
168 | if (m_off <= M2_MAX_OFFSET) { | ||
169 | m_off -= 1; | ||
170 | #if defined(LZO1X) | ||
171 | *op++ = (uint8_t)(((m_len - 1) << 5) | ((m_off & 7) << 2)); | ||
172 | *op++ = (uint8_t)(m_off >> 3); | ||
173 | #elif defined(LZO1Y) | ||
174 | *op++ = (uint8_t)(((m_len + 1) << 4) | ((m_off & 3) << 2)); | ||
175 | *op++ = (uint8_t)(m_off >> 2); | ||
176 | #endif | ||
177 | } | ||
178 | else if (m_off <= M3_MAX_OFFSET) { | ||
179 | m_off -= 1; | ||
180 | *op++ = (uint8_t)(M3_MARKER | (m_len - 2)); | ||
181 | goto m3_m4_offset; | ||
182 | } else { | ||
183 | #if defined(LZO1X) | ||
184 | m_off -= 0x4000; | ||
185 | assert(m_off > 0); | ||
186 | assert(m_off <= 0x7fff); | ||
187 | *op++ = (uint8_t)(M4_MARKER | ((m_off & 0x4000) >> 11) | (m_len - 2)); | ||
188 | goto m3_m4_offset; | ||
189 | #elif defined(LZO1Y) | ||
190 | goto m4_match; | ||
191 | #endif | ||
192 | } | ||
193 | } | ||
194 | else { | ||
195 | { | ||
196 | const uint8_t* end = in_end; | ||
197 | const uint8_t* m = m_pos + M2_MAX_LEN + 1; | ||
198 | while (ip < end && *m == *ip) | ||
199 | m++, ip++; | ||
200 | m_len = pd(ip, ii); | ||
201 | } | ||
202 | assert(m_len > M2_MAX_LEN); | ||
203 | |||
204 | if (m_off <= M3_MAX_OFFSET) { | ||
205 | m_off -= 1; | ||
206 | if (m_len <= 33) | ||
207 | *op++ = (uint8_t)(M3_MARKER | (m_len - 2)); | ||
208 | else { | ||
209 | m_len -= 33; | ||
210 | *op++ = M3_MARKER | 0; | ||
211 | goto m3_m4_len; | ||
212 | } | ||
213 | } else { | ||
214 | #if defined(LZO1Y) | ||
215 | m4_match: | ||
216 | #endif | ||
217 | m_off -= 0x4000; | ||
218 | assert(m_off > 0); | ||
219 | assert(m_off <= 0x7fff); | ||
220 | if (m_len <= M4_MAX_LEN) | ||
221 | *op++ = (uint8_t)(M4_MARKER | ((m_off & 0x4000) >> 11) | (m_len - 2)); | ||
222 | else { | ||
223 | m_len -= M4_MAX_LEN; | ||
224 | *op++ = (uint8_t)(M4_MARKER | ((m_off & 0x4000) >> 11)); | ||
225 | m3_m4_len: | ||
226 | while (m_len > 255) { | ||
227 | m_len -= 255; | ||
228 | *op++ = 0; | ||
229 | } | ||
230 | assert(m_len > 0); | ||
231 | *op++ = (uint8_t)(m_len); | ||
232 | } | ||
233 | } | ||
234 | m3_m4_offset: | ||
235 | *op++ = (uint8_t)((m_off & 63) << 2); | ||
236 | *op++ = (uint8_t)(m_off >> 6); | ||
237 | } | ||
238 | #if 0 | ||
239 | match_done: | ||
240 | #endif | ||
241 | ii = ip; | ||
242 | if (ip >= ip_end) | ||
243 | break; | ||
244 | } | ||
245 | |||
246 | *out_len = pd(op, out); | ||
247 | return pd(in_end, ii); | ||
248 | } | ||
249 | |||
250 | /*********************************************************************** | ||
251 | // public entry point | ||
252 | ************************************************************************/ | ||
253 | int DO_COMPRESS(const uint8_t* in, unsigned in_len, | ||
254 | uint8_t* out, unsigned* out_len, | ||
255 | void* wrkmem) | ||
256 | { | ||
257 | uint8_t* op = out; | ||
258 | unsigned t; | ||
259 | |||
260 | if (in_len <= M2_MAX_LEN + 5) | ||
261 | t = in_len; | ||
262 | else { | ||
263 | t = do_compress(in,in_len,op,out_len,wrkmem); | ||
264 | op += *out_len; | ||
265 | } | ||
266 | |||
267 | if (t > 0) { | ||
268 | const uint8_t* ii = in + in_len - t; | ||
269 | |||
270 | if (op == out && t <= 238) | ||
271 | *op++ = (uint8_t)(17 + t); | ||
272 | else if (t <= 3) | ||
273 | op[-2] |= (uint8_t)(t); | ||
274 | else if (t <= 18) | ||
275 | *op++ = (uint8_t)(t - 3); | ||
276 | else { | ||
277 | unsigned tt = t - 18; | ||
278 | |||
279 | *op++ = 0; | ||
280 | while (tt > 255) { | ||
281 | tt -= 255; | ||
282 | *op++ = 0; | ||
283 | } | ||
284 | assert(tt > 0); | ||
285 | *op++ = (uint8_t)(tt); | ||
286 | } | ||
287 | do *op++ = *ii++; while (--t > 0); | ||
288 | } | ||
289 | |||
290 | *op++ = M4_MARKER | 1; | ||
291 | *op++ = 0; | ||
292 | *op++ = 0; | ||
293 | |||
294 | *out_len = pd(op, out); | ||
295 | return 0; /*LZO_E_OK*/ | ||
296 | } |