Contents of /trunk/mkinitrd-magellan/busybox/archival/lzo1x_c.c
Parent Directory | Revision Log
Revision 984 -
(show annotations)
(download)
Sun May 30 11:32:42 2010 UTC (14 years, 4 months ago) by niro
File MIME type: text/plain
File size: 7045 byte(s)
Sun May 30 11:32:42 2010 UTC (14 years, 4 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 | /* 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 | } |