diff options
author | Jens Arnold <amiconn@rockbox.org> | 2005-11-27 23:41:55 +0000 |
---|---|---|
committer | Jens Arnold <amiconn@rockbox.org> | 2005-11-27 23:41:55 +0000 |
commit | 7c21a96e9afa3408ca0b459a392275aa0ae77608 (patch) | |
tree | 9933c4012631b53e72478b14db6315dfcaba5c32 /tools/ucl/src/ucl_mchw.ch | |
parent | f04577377d879d040ef046c38f6ab18b84a51341 (diff) | |
download | rockbox-7c21a96e9afa3408ca0b459a392275aa0ae77608.tar.gz rockbox-7c21a96e9afa3408ca0b459a392275aa0ae77608.zip |
Initial check-in of (stripped-down) UCL data compression library v 1.01
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@8087 a1c6a512-1295-4272-9138-f99709370657
Diffstat (limited to 'tools/ucl/src/ucl_mchw.ch')
-rwxr-xr-x | tools/ucl/src/ucl_mchw.ch | 313 |
1 files changed, 313 insertions, 0 deletions
diff --git a/tools/ucl/src/ucl_mchw.ch b/tools/ucl/src/ucl_mchw.ch new file mode 100755 index 0000000000..f2bcc9506f --- /dev/null +++ b/tools/ucl/src/ucl_mchw.ch | |||
@@ -0,0 +1,313 @@ | |||
1 | /* ucl_mchw.ch -- matching functions using a window | ||
2 | |||
3 | This file is part of the UCL data compression library. | ||
4 | |||
5 | Copyright (C) 1996-2002 Markus Franz Xaver Johannes Oberhumer | ||
6 | All Rights Reserved. | ||
7 | |||
8 | The UCL library is free software; you can redistribute it and/or | ||
9 | modify it under the terms of the GNU General Public License as | ||
10 | published by the Free Software Foundation; either version 2 of | ||
11 | the License, or (at your option) any later version. | ||
12 | |||
13 | The UCL library is distributed in the hope that it will be useful, | ||
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
16 | GNU General Public License for more details. | ||
17 | |||
18 | You should have received a copy of the GNU General Public License | ||
19 | along with the UCL library; see the file COPYING. | ||
20 | If not, write to the Free Software Foundation, Inc., | ||
21 | 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. | ||
22 | |||
23 | Markus F.X.J. Oberhumer | ||
24 | <markus@oberhumer.com> | ||
25 | */ | ||
26 | |||
27 | |||
28 | |||
29 | |||
30 | /*********************************************************************** | ||
31 | // | ||
32 | ************************************************************************/ | ||
33 | |||
34 | typedef struct | ||
35 | { | ||
36 | int init; | ||
37 | |||
38 | ucl_uint look; /* bytes in lookahead buffer */ | ||
39 | |||
40 | ucl_uint m_len; | ||
41 | ucl_uint m_off; | ||
42 | |||
43 | ucl_uint last_m_len; | ||
44 | ucl_uint last_m_off; | ||
45 | |||
46 | const ucl_byte *bp; | ||
47 | const ucl_byte *ip; | ||
48 | const ucl_byte *in; | ||
49 | const ucl_byte *in_end; | ||
50 | ucl_byte *out; | ||
51 | |||
52 | ucl_uint32 bb_b; | ||
53 | unsigned bb_k; | ||
54 | unsigned bb_c_endian; | ||
55 | unsigned bb_c_s; | ||
56 | unsigned bb_c_s8; | ||
57 | ucl_byte *bb_p; | ||
58 | ucl_byte *bb_op; | ||
59 | |||
60 | struct ucl_compress_config_t conf; | ||
61 | ucl_uintp result; | ||
62 | |||
63 | ucl_progress_callback_p cb; | ||
64 | |||
65 | ucl_uint textsize; /* text size counter */ | ||
66 | ucl_uint codesize; /* code size counter */ | ||
67 | ucl_uint printcount; /* counter for reporting progress every 1K bytes */ | ||
68 | |||
69 | /* some stats */ | ||
70 | unsigned long lit_bytes; | ||
71 | unsigned long match_bytes; | ||
72 | unsigned long rep_bytes; | ||
73 | unsigned long lazy; | ||
74 | } | ||
75 | UCL_COMPRESS_T; | ||
76 | |||
77 | |||
78 | |||
79 | #if defined(__PUREC__) && defined(__UCL_TOS16) | ||
80 | /* the cast is needed to work around a bug in Pure C */ | ||
81 | #define getbyte(c) ((c).ip < (c).in_end ? (unsigned) *((c).ip)++ : (-1)) | ||
82 | #else | ||
83 | #define getbyte(c) ((c).ip < (c).in_end ? *((c).ip)++ : (-1)) | ||
84 | #endif | ||
85 | |||
86 | #include "ucl_swd.ch" | ||
87 | |||
88 | |||
89 | |||
90 | /*********************************************************************** | ||
91 | // | ||
92 | ************************************************************************/ | ||
93 | |||
94 | static int | ||
95 | init_match ( UCL_COMPRESS_T *c, ucl_swd_t *s, | ||
96 | const ucl_byte *dict, ucl_uint dict_len, | ||
97 | ucl_uint32 flags ) | ||
98 | { | ||
99 | int r; | ||
100 | |||
101 | assert(!c->init); | ||
102 | c->init = 1; | ||
103 | |||
104 | s->c = c; | ||
105 | |||
106 | c->last_m_len = c->last_m_off = 0; | ||
107 | |||
108 | c->textsize = c->codesize = c->printcount = 0; | ||
109 | c->lit_bytes = c->match_bytes = c->rep_bytes = 0; | ||
110 | c->lazy = 0; | ||
111 | |||
112 | r = swd_init(s,dict,dict_len); | ||
113 | if (r != UCL_E_OK) | ||
114 | { | ||
115 | swd_exit(s); | ||
116 | return r; | ||
117 | } | ||
118 | |||
119 | s->use_best_off = (flags & 1) ? 1 : 0; | ||
120 | return UCL_E_OK; | ||
121 | } | ||
122 | |||
123 | |||
124 | /*********************************************************************** | ||
125 | // | ||
126 | ************************************************************************/ | ||
127 | |||
128 | static int | ||
129 | find_match ( UCL_COMPRESS_T *c, ucl_swd_t *s, | ||
130 | ucl_uint this_len, ucl_uint skip ) | ||
131 | { | ||
132 | assert(c->init); | ||
133 | |||
134 | if (skip > 0) | ||
135 | { | ||
136 | assert(this_len >= skip); | ||
137 | swd_accept(s, this_len - skip); | ||
138 | c->textsize += this_len - skip + 1; | ||
139 | } | ||
140 | else | ||
141 | { | ||
142 | assert(this_len <= 1); | ||
143 | c->textsize += this_len - skip; | ||
144 | } | ||
145 | |||
146 | s->m_len = THRESHOLD; | ||
147 | #ifdef SWD_BEST_OFF | ||
148 | if (s->use_best_off) | ||
149 | memset(s->best_pos,0,sizeof(s->best_pos)); | ||
150 | #endif | ||
151 | swd_findbest(s); | ||
152 | c->m_len = s->m_len; | ||
153 | #if defined(__UCL_CHECKER) | ||
154 | /* s->m_off may be uninitialized if we didn't find a match, | ||
155 | * but then its value will never be used. | ||
156 | */ | ||
157 | c->m_off = (s->m_len == THRESHOLD) ? 0 : s->m_off; | ||
158 | #else | ||
159 | c->m_off = s->m_off; | ||
160 | #endif | ||
161 | |||
162 | swd_getbyte(s); | ||
163 | |||
164 | if (s->b_char < 0) | ||
165 | { | ||
166 | c->look = 0; | ||
167 | c->m_len = 0; | ||
168 | swd_exit(s); | ||
169 | } | ||
170 | else | ||
171 | { | ||
172 | c->look = s->look + 1; | ||
173 | } | ||
174 | c->bp = c->ip - c->look; | ||
175 | |||
176 | #if 0 | ||
177 | /* brute force match search */ | ||
178 | if (c->m_len > THRESHOLD && c->m_len + 1 <= c->look) | ||
179 | { | ||
180 | const ucl_byte *ip = c->bp; | ||
181 | const ucl_byte *m = c->bp - c->m_off; | ||
182 | const ucl_byte *in = c->in; | ||
183 | |||
184 | if (ip - in > N) | ||
185 | in = ip - N; | ||
186 | for (;;) | ||
187 | { | ||
188 | while (*in != *ip) | ||
189 | in++; | ||
190 | if (in == ip) | ||
191 | break; | ||
192 | if (in != m) | ||
193 | if (memcmp(in,ip,c->m_len+1) == 0) | ||
194 | printf("%p %p %p %5d\n",in,ip,m,c->m_len); | ||
195 | in++; | ||
196 | } | ||
197 | } | ||
198 | #endif | ||
199 | |||
200 | if (c->cb && c->textsize > c->printcount) | ||
201 | { | ||
202 | (*c->cb->callback)(c->textsize,c->codesize,3,c->cb->user); | ||
203 | c->printcount += 1024; | ||
204 | } | ||
205 | |||
206 | return UCL_E_OK; | ||
207 | } | ||
208 | |||
209 | |||
210 | /*********************************************************************** | ||
211 | // bit buffer | ||
212 | ************************************************************************/ | ||
213 | |||
214 | static int bbConfig(UCL_COMPRESS_T *c, int endian, int bitsize) | ||
215 | { | ||
216 | if (endian != -1) | ||
217 | { | ||
218 | if (endian != 0) | ||
219 | return UCL_E_ERROR; | ||
220 | c->bb_c_endian = endian; | ||
221 | } | ||
222 | if (bitsize != -1) | ||
223 | { | ||
224 | if (bitsize != 8 && bitsize != 16 && bitsize != 32) | ||
225 | return UCL_E_ERROR; | ||
226 | c->bb_c_s = bitsize; | ||
227 | c->bb_c_s8 = bitsize / 8; | ||
228 | } | ||
229 | c->bb_b = 0; c->bb_k = 0; | ||
230 | c->bb_p = NULL; | ||
231 | c->bb_op = NULL; | ||
232 | return UCL_E_OK; | ||
233 | } | ||
234 | |||
235 | |||
236 | static void bbWriteBits(UCL_COMPRESS_T *c) | ||
237 | { | ||
238 | ucl_byte *p = c->bb_p; | ||
239 | ucl_uint32 b = c->bb_b; | ||
240 | |||
241 | p[0] = UCL_BYTE(b >> 0); | ||
242 | if (c->bb_c_s >= 16) | ||
243 | { | ||
244 | p[1] = UCL_BYTE(b >> 8); | ||
245 | if (c->bb_c_s == 32) | ||
246 | { | ||
247 | p[2] = UCL_BYTE(b >> 16); | ||
248 | p[3] = UCL_BYTE(b >> 24); | ||
249 | } | ||
250 | } | ||
251 | } | ||
252 | |||
253 | |||
254 | static void bbPutBit(UCL_COMPRESS_T *c, unsigned bit) | ||
255 | { | ||
256 | assert(bit == 0 || bit == 1); | ||
257 | assert(c->bb_k <= c->bb_c_s); | ||
258 | |||
259 | if (c->bb_k < c->bb_c_s) | ||
260 | { | ||
261 | if (c->bb_k == 0) | ||
262 | { | ||
263 | assert(c->bb_p == NULL); | ||
264 | c->bb_p = c->bb_op; | ||
265 | c->bb_op += c->bb_c_s8; | ||
266 | } | ||
267 | assert(c->bb_p != NULL); | ||
268 | assert(c->bb_p + c->bb_c_s8 <= c->bb_op); | ||
269 | |||
270 | c->bb_b = (c->bb_b << 1) + bit; | ||
271 | c->bb_k++; | ||
272 | } | ||
273 | else | ||
274 | { | ||
275 | assert(c->bb_p != NULL); | ||
276 | assert(c->bb_p + c->bb_c_s8 <= c->bb_op); | ||
277 | |||
278 | bbWriteBits(c); | ||
279 | c->bb_p = c->bb_op; | ||
280 | c->bb_op += c->bb_c_s8; | ||
281 | c->bb_b = bit; | ||
282 | c->bb_k = 1; | ||
283 | } | ||
284 | } | ||
285 | |||
286 | |||
287 | static void bbPutByte(UCL_COMPRESS_T *c, unsigned b) | ||
288 | { | ||
289 | /**printf("putbyte %p %p %x (%d)\n", op, bb_p, x, bb_k);*/ | ||
290 | assert(c->bb_p == NULL || c->bb_p + c->bb_c_s8 <= c->bb_op); | ||
291 | *c->bb_op++ = UCL_BYTE(b); | ||
292 | } | ||
293 | |||
294 | |||
295 | static void bbFlushBits(UCL_COMPRESS_T *c, unsigned filler_bit) | ||
296 | { | ||
297 | if (c->bb_k > 0) | ||
298 | { | ||
299 | assert(c->bb_k <= c->bb_c_s); | ||
300 | while (c->bb_k != c->bb_c_s) | ||
301 | bbPutBit(c, filler_bit); | ||
302 | bbWriteBits(c); | ||
303 | c->bb_k = 0; | ||
304 | } | ||
305 | c->bb_p = NULL; | ||
306 | } | ||
307 | |||
308 | |||
309 | |||
310 | /* | ||
311 | vi:ts=4:et | ||
312 | */ | ||
313 | |||