1 /* $Id: libdynamite.c 1274 2003-09-16 07:27:34Z twogood $ */
2 #include "libdynamite.h"
3 #include <stdint.h>
4 #include <stdlib.h>
5 #include <string.h>
6 #include <assert.h>
7
8 /*
9 This code probably looks really bad to anyone that is experienced with
10 (de)compression algorithms. But it works.
11 */
12
13 #define DEBUG 0
14
15 #if DEBUG
16 #include <stdio.h>
17 #endif
18
19 #define BUFFER_SIZE 0x8000
20 #define MAX_DICTIONARY_SIZE 0x1000
21
22 #define BIT_0 1
23 #define BIT_8 0x100
24
25 #define FREE(ptr) { if (ptr) { free(ptr); ptr = NULL; } }
26
27 typedef struct _Dynamite
28 {
29 DynamiteResult status;
30
31 /* external connections */
32 dynamite_reader reader;
33 dynamite_writer writer;
34 void* cookie;
35
36 /* bit reader */
37 uint8_t* buffer;
38 uint8_t byte;
39 int bit;
40
41
42 /* dictionary */
43 uint8_t* dictionary;
44 int dictionary_bits;
45 int dictionary_size;
46 int window_offset;
47
48 /* debug */
49 size_t bytes_written;
50 } Dynamite;
51
dynamite_read(Dynamite * dynamite,void * buffer,size_t size)52 static size_t dynamite_read(Dynamite* dynamite, void* buffer, size_t size)/*{{{*/
53 {
54 return dynamite->reader(buffer, size, dynamite->cookie);
55 }/*}}}*/
56
dynamite_write(Dynamite * dynamite,void * buffer,size_t size)57 static size_t dynamite_write(Dynamite* dynamite, void* buffer, size_t size)/*{{{*/
58 {
59 return dynamite->writer(buffer, size, dynamite->cookie);
60 }/*}}}*/
61
dynamite_read_header(Dynamite * dynamite)62 static bool dynamite_read_header(Dynamite* dynamite)/*{{{*/
63 {
64 bool success = false;
65 uint8_t header[2];
66
67 if (sizeof(header) != dynamite_read(dynamite, header, sizeof(header)))
68 goto exit;
69
70 dynamite->dictionary_bits = header[1];
71
72 switch (header[0])
73 {
74 case 0:
75 /* ok! */
76 break;
77
78 case 1:
79 /* encoded literal representation, not (yet) supported, fall through */
80 dynamite->status = DYNAMITE_NOT_IMPLEMENTED;
81 goto exit;
82
83 default:
84 /* not compressed with this algorithm! */
85 dynamite->status = DYNAMITE_BAD_FORMAT;
86 goto exit;
87 }
88
89 switch (dynamite->dictionary_bits)
90 {
91 case 4:
92 dynamite->dictionary_size = 0x400;
93 break;
94 case 5:
95 dynamite->dictionary_size = 0x800;
96 break;
97 case 6:
98 dynamite->dictionary_size = 0x1000;
99 break;
100 default:
101 /* not compressed with this algorithm! */
102 dynamite->status = DYNAMITE_BAD_FORMAT;
103 goto exit;
104 }
105
106 success = true;
107
108 exit:
109 return success;
110 }/*}}}*/
111
dynamite_read_bit(Dynamite * dynamite)112 static unsigned dynamite_read_bit(Dynamite* dynamite)/*{{{*/
113 {
114 /* XXX: this could probably be optimized */
115 unsigned result;
116
117 if (8 == dynamite->bit)
118 {
119 dynamite_read(dynamite, &dynamite->byte, 1);
120 dynamite->bit = 0;
121 }
122
123 result = dynamite->byte & 1;
124 dynamite->byte >>= 1;
125 dynamite->bit++;
126
127 return result;
128 }/*}}}*/
129
dynamite_read_bits_little_endian(Dynamite * dynamite,int count)130 static unsigned dynamite_read_bits_little_endian(Dynamite* dynamite, int count)/*{{{*/
131 {
132 /* XXX: this could probably be optimized */
133 int i;
134 unsigned result = 0;
135 unsigned bit = 1;
136
137 for (i = 0; i < count; i++)
138 {
139 if (dynamite_read_bit(dynamite))
140 result |= bit;
141 bit <<= 1;
142 }
143
144 return result;
145 }/*}}}*/
146
dynamite_read_bits_big_endian(Dynamite * dynamite,int count)147 static unsigned dynamite_read_bits_big_endian(Dynamite* dynamite, int count)/*{{{*/
148 {
149 /* XXX: this could probably be optimized */
150 int i;
151 unsigned result = 0;
152
153 for (i = 0; i < count; i++)
154 {
155 result <<= 1;
156 result |= dynamite_read_bit(dynamite);
157 }
158
159 return result;
160 }/*}}}*/
161
dynamite_get_copy_length(Dynamite * dynamite)162 static int dynamite_get_copy_length(Dynamite* dynamite)/*{{{*/
163 {
164 unsigned bits;
165 bits = dynamite_read_bits_big_endian(dynamite, 2);
166
167 switch (bits)
168 {
169 case 0: /* 00 */
170 bits = dynamite_read_bits_big_endian(dynamite, 2);
171
172 switch (bits)/*{{{*/
173 {
174 case 0: /* 0000 */
175 bits = dynamite_read_bits_big_endian(dynamite, 2);
176 switch (bits)
177 {
178 case 0: /* 000000 */
179 if (dynamite_read_bit(dynamite)) /* 0000001 */
180 {
181 return 136 + dynamite_read_bits_little_endian(dynamite, 7);
182 }
183 else /* 0000000 */
184 {
185 return 264 + dynamite_read_bits_little_endian(dynamite, 8);
186 }
187 case 1: /* 000001 */
188 return 72 + dynamite_read_bits_little_endian(dynamite, 6);
189 case 2: /* 000010 */
190 return 40 + dynamite_read_bits_little_endian(dynamite, 5);
191 case 3: /* 000011 */
192 return 24 + dynamite_read_bits_little_endian(dynamite, 4);
193 default:
194 abort();
195 }
196
197 case 1: /* 0001 */
198 if (dynamite_read_bit(dynamite))
199 return 12 + dynamite_read_bits_little_endian(dynamite, 2);
200 else
201 return 16 + dynamite_read_bits_little_endian(dynamite, 3);
202
203 case 2: /* 0010 */
204 if (dynamite_read_bit(dynamite)) /* 00101 */
205 return 9;
206 else /* 00100 */
207 return 10 + dynamite_read_bit(dynamite);
208
209 case 3: /* 0011 */
210 return 8;
211 default:
212 abort();
213 }/*}}}*/
214
215 case 1: /* 01 */
216 if (dynamite_read_bit(dynamite))
217 return 5; /* 011 */
218 else /* 010 */
219 {
220 if (dynamite_read_bit(dynamite))
221 return 6; /* 0101 */
222 else
223 return 7; /* 0100 */
224 }
225
226 case 2: /* 10 */
227 if (dynamite_read_bit(dynamite))
228 return 2; /* 101 */
229 else
230 return 4; /* 100 */
231
232 case 3:
233 return 3;
234
235 default:
236 abort();
237 }
238 }/*}}}*/
239
dynamite_get_upper_offset_bits(Dynamite * dynamite)240 static unsigned dynamite_get_upper_offset_bits(Dynamite* dynamite)/*{{{*/
241 {
242 unsigned bits;
243
244 bits = dynamite_read_bits_big_endian(dynamite, 2);
245
246 switch (bits)
247 {
248 case 0: /* 00 */
249 if (dynamite_read_bit(dynamite)) /* 001 */
250 {
251 bits = dynamite_read_bits_big_endian(dynamite, 4);
252 return 0x27 - bits;
253 }
254 else /* 000 */
255 {
256 if (dynamite_read_bit(dynamite)) /* 0001 */
257 {
258 bits = dynamite_read_bits_big_endian(dynamite, 3);
259 return 0x2f - bits;
260 }
261 else /* 0000 */
262 {
263 bits = dynamite_read_bits_big_endian(dynamite, 4);
264 return 0x3f - bits;
265 }
266 }
267
268 case 1: /* 01 */
269 bits = dynamite_read_bits_big_endian(dynamite, 4);
270 if (bits)
271 return 0x16 - bits;
272 else
273 return 0x17 - dynamite_read_bit(dynamite);
274
275 case 2: /* 10 */
276 bits = dynamite_read_bit(dynamite) << 1;
277 bits |= dynamite_read_bit(dynamite);
278 switch (bits)
279 {
280 case 0: /* 1000 */
281 if (dynamite_read_bit(dynamite))
282 return 5;
283 else
284 return 6;
285
286 case 1: /* 1001 */
287 if (dynamite_read_bit(dynamite))
288 return 3;
289 else
290 return 4;
291
292 case 2: /* 1010 */
293 return 2;
294 case 3: /* 1011 */
295 return 1;
296
297 default:
298 abort();
299 }
300
301 case 3: /* 11 */
302 return 0;
303
304 default:
305 abort();
306 }
307 }/*}}}*/
308
dynamite_get_offset(Dynamite * dynamite,int length)309 static int dynamite_get_offset(Dynamite* dynamite, int length)/*{{{*/
310 {
311 unsigned lower_bit_count;
312 int result = 0;
313
314 if (2 == length)
315 lower_bit_count = 2;
316 else
317 lower_bit_count = dynamite->dictionary_bits;
318
319 result = dynamite_get_upper_offset_bits(dynamite) << lower_bit_count;
320 result |= dynamite_read_bits_little_endian(dynamite, lower_bit_count);
321
322 return result;
323 }/*}}}*/
324
dynamite_add_to_dictionary(Dynamite * dynamite,uint8_t byte)325 static void dynamite_add_to_dictionary(Dynamite* dynamite, uint8_t byte)/*{{{*/
326 {
327 dynamite->window_offset = (dynamite->window_offset + 1) % dynamite->dictionary_size;
328 dynamite->dictionary[dynamite->window_offset] = byte;
329 }/*}}}*/
330
dynamite_get_from_dictionary(Dynamite * dynamite,unsigned offset)331 static uint8_t dynamite_get_from_dictionary(Dynamite* dynamite, unsigned offset)/*{{{*/
332 {
333 size_t window_offset = dynamite->window_offset;
334 if (offset > window_offset)
335 {
336 window_offset += dynamite->dictionary_size;
337 }
338
339 return dynamite->dictionary[window_offset - offset];
340 }/*}}}*/
341
dynamite_write_byte(Dynamite * dynamite,uint8_t byte)342 static bool dynamite_write_byte(Dynamite* dynamite, uint8_t byte)/*{{{*/
343 {
344 #if DEBUG
345 fprintf(stderr, "%02x ", byte);
346 #endif
347 dynamite_add_to_dictionary(dynamite, byte);
348 if (1 == dynamite_write(dynamite, &byte, 1))
349 {
350 dynamite->bytes_written++;
351 return true;
352 }
353 else
354 {
355 dynamite->status = DYNAMITE_WRITE_ERROR;
356 return false;
357 }
358 }/*}}}*/
359
dynamite_explode(dynamite_reader reader,dynamite_writer writer,void * cookie)360 DynamiteResult dynamite_explode(dynamite_reader reader, dynamite_writer writer, void* cookie)
361 {
362 Dynamite dynamite;
363
364 memset(&dynamite, 0, sizeof(Dynamite));
365
366 dynamite.status = DYNAMITE_UNEXPECTED_ERROR;
367 dynamite.reader = reader;
368 dynamite.writer = writer;
369 dynamite.cookie = cookie;
370 dynamite.buffer = malloc(BUFFER_SIZE);
371
372 if (!dynamite_read_header(&dynamite))
373 goto exit;
374
375 dynamite.bit = 8; /* causes update of byte */
376 dynamite.status = DYNAMITE_SUCCESS;
377 dynamite.dictionary = malloc(dynamite.dictionary_size);
378 memset(dynamite.dictionary, 0, dynamite.dictionary_size);
379
380 while (DYNAMITE_SUCCESS == dynamite.status)
381 {
382 #if DEBUG
383 fprintf(stderr, "%08x: ", dynamite.bytes_written);
384 #endif
385
386 if (dynamite_read_bit(&dynamite))
387 {
388 /* Control token */
389 int length = dynamite_get_copy_length(&dynamite);
390
391 assert(length <= 519);
392
393 if (519 == length)
394 {
395 /* finished */
396 break;
397 }
398 else
399 {
400 int offset = dynamite_get_offset(&dynamite, length);
401
402 #if DEBUG
403 fprintf(stderr, "Copying %i bytes from offset %i\n", length, offset);
404 #endif
405
406 while (length)
407 {
408 dynamite_write_byte(&dynamite, dynamite_get_from_dictionary(&dynamite, offset));
409 length--;
410 }
411 }
412 }
413 else
414 {
415 /*
416 Literal token
417 */
418
419 /* TODO: handle encoded representation too */
420 uint8_t byte = dynamite_read_bits_little_endian(&dynamite, 8) /*& 0xff*/;
421 dynamite_write_byte(&dynamite, byte);
422 }
423
424 #if DEBUG
425 if (dynamite.bytes_written > 0x20)
426 abort();
427 #endif
428
429 #if DEBUG
430 fprintf(stderr, "\n");
431 #endif
432 }
433
434 exit:
435 FREE(dynamite.buffer);
436 FREE(dynamite.dictionary);
437 return dynamite.status;
438 }
439
440