1
/* This file is part of libmspack.
2
* (C) 2003-2004 Stuart Caie.
4
* The Quantum method was created by David Stafford, adapted by Microsoft
7
* This decompressor is based on an implementation by Matthew Russotto, used
10
* libmspack is free software; you can redistribute it and/or modify it under
11
* the terms of the GNU Lesser General Public License (LGPL) version 2.1
13
* For further details, see the file COPYING.LIB distributed with libmspack
16
/* Quantum decompression implementation */
18
/* This decompressor was researched and implemented by Matthew Russotto. It
19
* has since been tidied up by Stuart Caie. More information can be found at
20
* http://www.speakeasy.org/~russotto/quantumcomp.html
24
#include "clamav-config.h"
31
/* Quantum decompressor bitstream reading macros
33
* STORE_BITS stores bitstream state in qtmd_stream structure
34
* RESTORE_BITS restores bitstream state from qtmd_stream structure
35
* READ_BITS(var,n) takes N bits from the buffer and puts them in var
36
* FILL_BUFFER if there is room for another 16 bits, reads another
37
* 16 bits from the input stream.
38
* PEEK_BITS(n) extracts without removing N bits from the bit buffer
39
* REMOVE_BITS(n) removes N bits from the bit buffer
41
* These bit access routines work by using the area beyond the MSB and the
42
* LSB as a free source of zeroes. This avoids having to mask any bits.
43
* So we have to know the bit width of the bitbuffer variable.
52
#define BITBUF_WIDTH (sizeof(unsigned int) * CHAR_BIT)
54
#define STORE_BITS do { \
57
qtm->bit_buffer = bit_buffer; \
58
qtm->bits_left = bits_left; \
61
#define RESTORE_BITS do { \
64
bit_buffer = qtm->bit_buffer; \
65
bits_left = qtm->bits_left; \
68
/* adds 16 bits to bit buffer, if there's space for the new bits */
69
#define FILL_BUFFER do { \
70
if (bits_left <= (BITBUF_WIDTH - 16)) { \
71
if (i_ptr >= i_end) { \
72
if (qtmd_read_input(qtm)) return qtm->error; \
76
bit_buffer |= ((i_ptr[0] << 8) | i_ptr[1]) \
77
<< (BITBUF_WIDTH - 16 - bits_left); \
83
#define PEEK_BITS(n) (bit_buffer >> (BITBUF_WIDTH - (n)))
84
#define REMOVE_BITS(n) ((bit_buffer <<= (n)), (bits_left -= (n)))
86
#define READ_BITS(val, bits) do { \
88
for (bits_needed = (bits); bits_needed > 0; bits_needed -= bit_run) { \
90
bit_run = (bits_left < bits_needed) ? bits_left : bits_needed; \
91
(val) = ((val) << bit_run) | PEEK_BITS(bit_run); \
92
REMOVE_BITS(bit_run); \
96
static int qtmd_read_input(struct qtmd_stream *qtm) {
97
int read = qtm->sys->read(qtm->input, &qtm->inbuf[0], (int)qtm->inbuf_size);
98
if (read < 0) return qtm->error = MSPACK_ERR_READ;
100
qtm->i_ptr = &qtm->inbuf[0];
101
qtm->i_end = &qtm->inbuf[read];
102
return MSPACK_ERR_OK;
105
/* Quantum static data tables:
107
* Quantum uses 'position slots' to represent match offsets. For every
108
* match, a small 'position slot' number and a small offset from that slot
109
* are encoded instead of one large offset.
111
* position_base[] is an index to the position slot bases
113
* extra_bits[] states how many bits of offset-from-base data is needed.
115
* length_base[] and length_extra[] are equivalent in function, but are
116
* used for encoding selector 6 (variable length match) match lengths,
117
* instead of match offsets.
119
static unsigned int position_base[42];
120
static unsigned char extra_bits[42], length_base[27], length_extra[27];
122
static void qtmd_static_init() {
123
unsigned int i, offset;
125
for (i = 0, offset = 0; i < 42; i++) {
126
position_base[i] = offset;
127
extra_bits[i] = ((i < 2) ? 0 : (i - 2)) >> 1;
128
offset += 1 << extra_bits[i];
131
for (i = 0, offset = 0; i < 26; i++) {
132
length_base[i] = offset;
133
length_extra[i] = (i < 2 ? 0 : i - 2) >> 2;
134
offset += 1 << length_extra[i];
136
length_base[26] = 254; length_extra[26] = 0;
140
/* Arithmetic decoder:
142
* GET_SYMBOL(model, var) fetches the next symbol from the stated model
143
* and puts it in var.
145
* If necessary, qtmd_update_model() is called.
147
#define GET_SYMBOL(model, var) do { \
148
range = ((H - L) & 0xFFFF) + 1; \
149
symf = ((((C - L + 1) * model.syms[0].cumfreq)-1) / range) & 0xFFFF; \
151
for (i = 1; i < model.entries; i++) { \
152
if (model.syms[i].cumfreq <= symf) break; \
154
(var) = model.syms[i-1].sym; \
156
range = (H - L) + 1; \
157
symf = model.syms[0].cumfreq; \
158
H = L + ((model.syms[i-1].cumfreq * range) / symf) - 1; \
159
L = L + ((model.syms[i].cumfreq * range) / symf); \
161
do { model.syms[--i].cumfreq += 8; } while (i > 0); \
162
if (model.syms[0].cumfreq > 3800) qtmd_update_model(&model); \
165
if ((L & 0x8000) != (H & 0x8000)) { \
166
if ((L & 0x4000) && !(H & 0x4000)) { \
167
/* underflow case */ \
168
C ^= 0x4000; L &= 0x3FFF; H |= 0x4000; \
172
L <<= 1; H = (H << 1) | 1; \
174
C = (C << 1) | PEEK_BITS(1); \
179
static void qtmd_update_model(struct qtmd_model *model) {
180
struct qtmd_modelsym tmp;
183
if (--model->shiftsleft) {
184
for (i = model->entries - 1; i >= 0; i--) {
185
/* -1, not -2; the 0 entry saves this */
186
model->syms[i].cumfreq >>= 1;
187
if (model->syms[i].cumfreq <= model->syms[i+1].cumfreq) {
188
model->syms[i].cumfreq = model->syms[i+1].cumfreq + 1;
193
model->shiftsleft = 50;
194
for (i = 0; i < model->entries; i++) {
195
/* no -1, want to include the 0 entry */
196
/* this converts cumfreqs into frequencies, then shifts right */
197
model->syms[i].cumfreq -= model->syms[i+1].cumfreq;
198
model->syms[i].cumfreq++; /* avoid losing things entirely */
199
model->syms[i].cumfreq >>= 1;
202
/* now sort by frequencies, decreasing order -- this must be an
203
* inplace selection sort, or a sort with the same (in)stability
205
for (i = 0; i < model->entries - 1; i++) {
206
for (j = i + 1; j < model->entries; j++) {
207
if (model->syms[i].cumfreq < model->syms[j].cumfreq) {
208
tmp = model->syms[i];
209
model->syms[i] = model->syms[j];
210
model->syms[j] = tmp;
215
/* then convert frequencies back to cumfreq */
216
for (i = model->entries - 1; i >= 0; i--) {
217
model->syms[i].cumfreq += model->syms[i+1].cumfreq;
222
/* Initialises a model to decode symbols from [start] to [start]+[len]-1 */
223
static void qtmd_init_model(struct qtmd_model *model,
224
struct qtmd_modelsym *syms, int start, int len)
228
model->shiftsleft = 4;
229
model->entries = len;
232
for (i = 0; i <= len; i++) {
233
syms[i].sym = start + i; /* actual symbol */
234
syms[i].cumfreq = len - i; /* current frequency of that symbol */
239
/*-------- main Quantum code --------*/
241
struct qtmd_stream *qtmd_init(struct mspack_system *system,
242
struct mspack_file *input,
243
struct mspack_file *output,
244
int window_bits, int input_buffer_size)
246
unsigned int window_size = 1 << window_bits;
247
struct qtmd_stream *qtm;
250
if (!system) return NULL;
252
/* Quantum supports window sizes of 2^10 (1Kb) through 2^21 (2Mb) */
254
/* tk: temporary fix: only process 32KB+ window sizes */
255
if (window_bits < 15 || window_bits > 21) return NULL;
257
input_buffer_size = (input_buffer_size + 1) & -2;
258
if (input_buffer_size < 2) return NULL;
260
/* initialise static data */
263
/* allocate decompression state */
264
if (!(qtm = system->alloc(system, sizeof(struct qtmd_stream)))) {
268
/* allocate decompression window and input buffer */
269
qtm->window = system->alloc(system, (size_t) window_size);
270
qtm->inbuf = system->alloc(system, (size_t) input_buffer_size);
271
if (!qtm->window || !qtm->inbuf) {
272
system->free(qtm->window);
273
system->free(qtm->inbuf);
278
/* initialise decompression state */
281
qtm->output = output;
282
qtm->inbuf_size = input_buffer_size;
283
qtm->window_size = window_size;
284
qtm->window_posn = 0;
285
qtm->frame_start = 0;
286
qtm->header_read = 0;
287
qtm->error = MSPACK_ERR_OK;
289
qtm->i_ptr = qtm->i_end = &qtm->inbuf[0];
290
qtm->o_ptr = qtm->o_end = &qtm->window[0];
294
/* initialise arithmetic coding models
295
* - model 4 depends on window size, ranges from 20 to 24
296
* - model 5 depends on window size, ranges from 20 to 36
297
* - model 6pos depends on window size, ranges from 20 to 42
300
qtmd_init_model(&qtm->model0, &qtm->m0sym[0], 0, 64);
301
qtmd_init_model(&qtm->model1, &qtm->m1sym[0], 64, 64);
302
qtmd_init_model(&qtm->model2, &qtm->m2sym[0], 128, 64);
303
qtmd_init_model(&qtm->model3, &qtm->m3sym[0], 192, 64);
304
qtmd_init_model(&qtm->model4, &qtm->m4sym[0], 0, (i > 24) ? 24 : i);
305
qtmd_init_model(&qtm->model5, &qtm->m5sym[0], 0, (i > 36) ? 36 : i);
306
qtmd_init_model(&qtm->model6, &qtm->m6sym[0], 0, i);
307
qtmd_init_model(&qtm->model6len, &qtm->m6lsym[0], 0, 27);
308
qtmd_init_model(&qtm->model7, &qtm->m7sym[0], 0, 7);
314
int qtmd_decompress(struct qtmd_stream *qtm, off_t out_bytes) {
315
unsigned int frame_start, frame_end, window_posn, match_offset, range;
316
unsigned char *window, *i_ptr, *i_end, *runsrc, *rundest;
317
int i, j, selector, extra, sym, match_length;
318
unsigned short H, L, C, symf;
320
register unsigned int bit_buffer;
321
register unsigned char bits_left;
322
unsigned char bits_needed, bit_run;
325
if (!qtm || (out_bytes < 0)) return MSPACK_ERR_ARGS;
326
if (qtm->error) return qtm->error;
328
/* flush out any stored-up bytes before we begin */
329
i = qtm->o_end - qtm->o_ptr;
330
if ((off_t) i > out_bytes) i = (int) out_bytes;
332
if (qtm->sys->write(qtm->output, qtm->o_ptr, i) != i) {
333
return qtm->error = MSPACK_ERR_WRITE;
338
if (out_bytes == 0) return MSPACK_ERR_OK;
340
/* restore local state */
342
window = qtm->window;
343
window_posn = qtm->window_posn;
344
frame_start = qtm->frame_start;
349
/* while we do not have enough decoded bytes in reserve: */
350
while ((qtm->o_end - qtm->o_ptr) < out_bytes) {
352
/* read header if necessary. Initialises H, L and C */
353
if (!qtm->header_read) {
354
H = 0xFFFF; L = 0; READ_BITS(C, 16);
355
qtm->header_read = 1;
358
/* decode more, at most up to to frame boundary */
359
frame_end = window_posn + (out_bytes - (qtm->o_end - qtm->o_ptr));
360
if ((frame_start + QTM_FRAME_SIZE) < frame_end) {
361
frame_end = frame_start + QTM_FRAME_SIZE;
364
while (window_posn < frame_end) {
365
GET_SYMBOL(qtm->model7, selector);
367
struct qtmd_model *mdl = (selector == 0) ? &qtm->model0 :
368
((selector == 1) ? &qtm->model1 :
369
((selector == 2) ? &qtm->model2 :
371
GET_SYMBOL((*mdl), sym);
372
window[window_posn++] = sym;
376
case 4: /* selector 4 = fixed length match (3 bytes) */
377
GET_SYMBOL(qtm->model4, sym);
378
READ_BITS(extra, extra_bits[sym]);
379
match_offset = position_base[sym] + extra + 1;
383
case 5: /* selector 5 = fixed length match (4 bytes) */
384
GET_SYMBOL(qtm->model5, sym);
385
READ_BITS(extra, extra_bits[sym]);
386
match_offset = position_base[sym] + extra + 1;
390
case 6: /* selector 6 = variable length match */
391
GET_SYMBOL(qtm->model6len, sym);
392
READ_BITS(extra, length_extra[sym]);
393
match_length = length_base[sym] + extra + 5;
395
GET_SYMBOL(qtm->model6, sym);
396
READ_BITS(extra, extra_bits[sym]);
397
match_offset = position_base[sym] + extra + 1;
401
/* should be impossible, model7 can only return 0-6 */
402
return qtm->error = MSPACK_ERR_DECRUNCH;
405
rundest = &window[window_posn];
407
/* does match offset wrap the window? */
408
if (match_offset > window_posn) {
409
/* j = length from match offset to end of window */
410
j = match_offset - window_posn;
411
if (j > (int) qtm->window_size) {
412
D(("match offset beyond window boundaries"))
413
return qtm->error = MSPACK_ERR_DECRUNCH;
415
runsrc = &window[qtm->window_size - j];
417
/* if match goes over the window edge, do two copy runs */
418
i -= j; while (j-- > 0) *rundest++ = *runsrc++;
421
while (i-- > 0) *rundest++ = *runsrc++;
424
runsrc = rundest - match_offset;
425
while (i-- > 0) *rundest++ = *runsrc++;
427
window_posn += match_length;
429
} /* while (window_posn < frame_end) */
431
qtm->o_end = &window[window_posn];
433
/* another frame completed? */
434
if ((window_posn - frame_start) >= QTM_FRAME_SIZE) {
435
if ((window_posn - frame_start) != QTM_FRAME_SIZE) {
436
D(("overshot frame alignment"))
437
return qtm->error = MSPACK_ERR_DECRUNCH;
441
if (bits_left & 7) REMOVE_BITS(bits_left & 7);
442
do { READ_BITS(i, 8); } while (i != 0xFF);
443
qtm->header_read = 0;
446
if (window_posn == qtm->window_size) {
447
/* flush all currently stored data */
448
i = (qtm->o_end - qtm->o_ptr);
449
if (qtm->sys->write(qtm->output, qtm->o_ptr, i) != i) {
450
return qtm->error = MSPACK_ERR_WRITE;
453
qtm->o_ptr = &window[0];
454
qtm->o_end = &window[0];
458
frame_start = window_posn;
461
} /* while (more bytes needed) */
465
if (qtm->sys->write(qtm->output, qtm->o_ptr, i) != i) {
466
return qtm->error = MSPACK_ERR_WRITE;
471
/* store local state */
473
qtm->window_posn = window_posn;
474
qtm->frame_start = frame_start;
479
return MSPACK_ERR_OK;
482
void qtmd_free(struct qtmd_stream *qtm) {
483
struct mspack_system *sys;
486
sys->free(qtm->window);
487
sys->free(qtm->inbuf);
added
removed
libclamav/mspack/qtmd.c
