From c876d3bbefe0dc00c27ca0c12d29da5874946962 Mon Sep 17 00:00:00 2001 From: Dominik Riebeling Date: Wed, 15 Dec 2021 21:04:28 +0100 Subject: rbutil: Merge rbutil with utils folder. rbutil uses several components from the utils folder, and can be considered part of utils too. Having it in a separate folder is an arbitrary split that doesn't help anymore these days, so merge them. This also allows other utils to easily use libtools.make without the need to navigate to a different folder. Change-Id: I3fc2f4de19e3e776553efb5dea5f779dfec0dc21 --- utils/rbutilqt/mspack/qtmd.c | 490 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 490 insertions(+) create mode 100644 utils/rbutilqt/mspack/qtmd.c (limited to 'utils/rbutilqt/mspack/qtmd.c') diff --git a/utils/rbutilqt/mspack/qtmd.c b/utils/rbutilqt/mspack/qtmd.c new file mode 100644 index 0000000000..58e4787b7f --- /dev/null +++ b/utils/rbutilqt/mspack/qtmd.c @@ -0,0 +1,490 @@ +/* This file is part of libmspack. + * (C) 2003-2004 Stuart Caie. + * + * The Quantum method was created by David Stafford, adapted by Microsoft + * Corporation. + * + * This decompressor is based on an implementation by Matthew Russotto, used + * with permission. + * + * libmspack is free software; you can redistribute it and/or modify it under + * the terms of the GNU Lesser General Public License (LGPL) version 2.1 + * + * For further details, see the file COPYING.LIB distributed with libmspack + */ + +/* Quantum decompression implementation */ + +/* This decompressor was researched and implemented by Matthew Russotto. It + * has since been tidied up by Stuart Caie. More information can be found at + * http://www.speakeasy.org/~russotto/quantumcomp.html + */ + +#include "system-mspack.h" +#include "qtm.h" + +/* import bit-reading macros and code */ +#define BITS_TYPE struct qtmd_stream +#define BITS_VAR qtm +#define BITS_ORDER_MSB +#define READ_BYTES do { \ + unsigned char b0, b1; \ + READ_IF_NEEDED; b0 = *i_ptr++; \ + READ_IF_NEEDED; b1 = *i_ptr++; \ + INJECT_BITS((b0 << 8) | b1, 16); \ +} while (0) +#include "readbits.h" + +/* Quantum static data tables: + * + * Quantum uses 'position slots' to represent match offsets. For every + * match, a small 'position slot' number and a small offset from that slot + * are encoded instead of one large offset. + * + * position_base[] is an index to the position slot bases + * + * extra_bits[] states how many bits of offset-from-base data is needed. + * + * length_base[] and length_extra[] are equivalent in function, but are + * used for encoding selector 6 (variable length match) match lengths, + * instead of match offsets. + * + * They are generated with the following code: + * unsigned int i, offset; + * for (i = 0, offset = 0; i < 42; i++) { + * position_base[i] = offset; + * extra_bits[i] = ((i < 2) ? 0 : (i - 2)) >> 1; + * offset += 1 << extra_bits[i]; + * } + * for (i = 0, offset = 0; i < 26; i++) { + * length_base[i] = offset; + * length_extra[i] = (i < 2 ? 0 : i - 2) >> 2; + * offset += 1 << length_extra[i]; + * } + * length_base[26] = 254; length_extra[26] = 0; + */ +static const unsigned int position_base[42] = { + 0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, + 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576, 32768, 49152, + 65536, 98304, 131072, 196608, 262144, 393216, 524288, 786432, 1048576, 1572864 +}; +static const unsigned char extra_bits[42] = { + 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, + 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19 +}; +static const unsigned char length_base[27] = { + 0, 1, 2, 3, 4, 5, 6, 8, 10, 12, 14, 18, 22, 26, + 30, 38, 46, 54, 62, 78, 94, 110, 126, 158, 190, 222, 254 +}; +static const unsigned char length_extra[27] = { + 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, + 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0 +}; + + +/* Arithmetic decoder: + * + * GET_SYMBOL(model, var) fetches the next symbol from the stated model + * and puts it in var. + * + * If necessary, qtmd_update_model() is called. + */ +#define GET_SYMBOL(model, var) do { \ + range = ((H - L) & 0xFFFF) + 1; \ + symf = ((((C - L + 1) * model.syms[0].cumfreq)-1) / range) & 0xFFFF; \ + \ + for (i = 1; i < model.entries; i++) { \ + if (model.syms[i].cumfreq <= symf) break; \ + } \ + (var) = model.syms[i-1].sym; \ + \ + range = (H - L) + 1; \ + symf = model.syms[0].cumfreq; \ + H = L + ((model.syms[i-1].cumfreq * range) / symf) - 1; \ + L = L + ((model.syms[i].cumfreq * range) / symf); \ + \ + do { model.syms[--i].cumfreq += 8; } while (i > 0); \ + if (model.syms[0].cumfreq > 3800) qtmd_update_model(&model); \ + \ + while (1) { \ + if ((L & 0x8000) != (H & 0x8000)) { \ + if ((L & 0x4000) && !(H & 0x4000)) { \ + /* underflow case */ \ + C ^= 0x4000; L &= 0x3FFF; H |= 0x4000; \ + } \ + else break; \ + } \ + L <<= 1; H = (H << 1) | 1; \ + ENSURE_BITS(1); \ + C = (C << 1) | PEEK_BITS(1); \ + REMOVE_BITS(1); \ + } \ +} while (0) + +static void qtmd_update_model(struct qtmd_model *model) { + struct qtmd_modelsym tmp; + int i, j; + + if (--model->shiftsleft) { + for (i = model->entries - 1; i >= 0; i--) { + /* -1, not -2; the 0 entry saves this */ + model->syms[i].cumfreq >>= 1; + if (model->syms[i].cumfreq <= model->syms[i+1].cumfreq) { + model->syms[i].cumfreq = model->syms[i+1].cumfreq + 1; + } + } + } + else { + model->shiftsleft = 50; + for (i = 0; i < model->entries; i++) { + /* no -1, want to include the 0 entry */ + /* this converts cumfreqs into frequencies, then shifts right */ + model->syms[i].cumfreq -= model->syms[i+1].cumfreq; + model->syms[i].cumfreq++; /* avoid losing things entirely */ + model->syms[i].cumfreq >>= 1; + } + + /* now sort by frequencies, decreasing order -- this must be an + * inplace selection sort, or a sort with the same (in)stability + * characteristics */ + for (i = 0; i < model->entries - 1; i++) { + for (j = i + 1; j < model->entries; j++) { + if (model->syms[i].cumfreq < model->syms[j].cumfreq) { + tmp = model->syms[i]; + model->syms[i] = model->syms[j]; + model->syms[j] = tmp; + } + } + } + + /* then convert frequencies back to cumfreq */ + for (i = model->entries - 1; i >= 0; i--) { + model->syms[i].cumfreq += model->syms[i+1].cumfreq; + } + } +} + +/* Initialises a model to decode symbols from [start] to [start]+[len]-1 */ +static void qtmd_init_model(struct qtmd_model *model, + struct qtmd_modelsym *syms, int start, int len) +{ + int i; + + model->shiftsleft = 4; + model->entries = len; + model->syms = syms; + + for (i = 0; i <= len; i++) { + syms[i].sym = start + i; /* actual symbol */ + syms[i].cumfreq = len - i; /* current frequency of that symbol */ + } +} + + +/*-------- main Quantum code --------*/ + +struct qtmd_stream *qtmd_init(struct mspack_system *system, + struct mspack_file *input, + struct mspack_file *output, + int window_bits, int input_buffer_size) +{ + unsigned int window_size = 1 << window_bits; + struct qtmd_stream *qtm; + int i; + + if (!system) return NULL; + + /* Quantum supports window sizes of 2^10 (1Kb) through 2^21 (2Mb) */ + if (window_bits < 10 || window_bits > 21) return NULL; + + /* round up input buffer size to multiple of two */ + input_buffer_size = (input_buffer_size + 1) & -2; + if (input_buffer_size < 2) return NULL; + + /* allocate decompression state */ + if (!(qtm = (struct qtmd_stream *) system->alloc(system, sizeof(struct qtmd_stream)))) { + return NULL; + } + + /* allocate decompression window and input buffer */ + qtm->window = (unsigned char *) system->alloc(system, (size_t) window_size); + qtm->inbuf = (unsigned char *) system->alloc(system, (size_t) input_buffer_size); + if (!qtm->window || !qtm->inbuf) { + system->free(qtm->window); + system->free(qtm->inbuf); + system->free(qtm); + return NULL; + } + + /* initialise decompression state */ + qtm->sys = system; + qtm->input = input; + qtm->output = output; + qtm->inbuf_size = input_buffer_size; + qtm->window_size = window_size; + qtm->window_posn = 0; + qtm->frame_todo = QTM_FRAME_SIZE; + qtm->header_read = 0; + qtm->error = MSPACK_ERR_OK; + + qtm->i_ptr = qtm->i_end = &qtm->inbuf[0]; + qtm->o_ptr = qtm->o_end = &qtm->window[0]; + qtm->input_end = 0; + qtm->bits_left = 0; + qtm->bit_buffer = 0; + + /* initialise arithmetic coding models + * - model 4 depends on window size, ranges from 20 to 24 + * - model 5 depends on window size, ranges from 20 to 36 + * - model 6pos depends on window size, ranges from 20 to 42 + */ + i = window_bits * 2; + qtmd_init_model(&qtm->model0, &qtm->m0sym[0], 0, 64); + qtmd_init_model(&qtm->model1, &qtm->m1sym[0], 64, 64); + qtmd_init_model(&qtm->model2, &qtm->m2sym[0], 128, 64); + qtmd_init_model(&qtm->model3, &qtm->m3sym[0], 192, 64); + qtmd_init_model(&qtm->model4, &qtm->m4sym[0], 0, (i > 24) ? 24 : i); + qtmd_init_model(&qtm->model5, &qtm->m5sym[0], 0, (i > 36) ? 36 : i); + qtmd_init_model(&qtm->model6, &qtm->m6sym[0], 0, i); + qtmd_init_model(&qtm->model6len, &qtm->m6lsym[0], 0, 27); + qtmd_init_model(&qtm->model7, &qtm->m7sym[0], 0, 7); + + /* all ok */ + return qtm; +} + +int qtmd_decompress(struct qtmd_stream *qtm, off_t out_bytes) { + unsigned int frame_todo, frame_end, window_posn, match_offset, range; + unsigned char *window, *i_ptr, *i_end, *runsrc, *rundest; + int i, j, selector, extra, sym, match_length; + unsigned short H, L, C, symf; + + register unsigned int bit_buffer; + register unsigned char bits_left; + + /* easy answers */ + if (!qtm || (out_bytes < 0)) return MSPACK_ERR_ARGS; + if (qtm->error) return qtm->error; + + /* flush out any stored-up bytes before we begin */ + i = qtm->o_end - qtm->o_ptr; + if ((off_t) i > out_bytes) i = (int) out_bytes; + if (i) { + if (qtm->sys->write(qtm->output, qtm->o_ptr, i) != i) { + return qtm->error = MSPACK_ERR_WRITE; + } + qtm->o_ptr += i; + out_bytes -= i; + } + if (out_bytes == 0) return MSPACK_ERR_OK; + + /* restore local state */ + RESTORE_BITS; + window = qtm->window; + window_posn = qtm->window_posn; + frame_todo = qtm->frame_todo; + H = qtm->H; + L = qtm->L; + C = qtm->C; + + /* while we do not have enough decoded bytes in reserve: */ + while ((qtm->o_end - qtm->o_ptr) < out_bytes) { + /* read header if necessary. Initialises H, L and C */ + if (!qtm->header_read) { + H = 0xFFFF; L = 0; READ_BITS(C, 16); + qtm->header_read = 1; + } + + /* decode more, up to the number of bytes needed, the frame boundary, + * or the window boundary, whichever comes first */ + frame_end = window_posn + (out_bytes - (qtm->o_end - qtm->o_ptr)); + if ((window_posn + frame_todo) < frame_end) { + frame_end = window_posn + frame_todo; + } + if (frame_end > qtm->window_size) { + frame_end = qtm->window_size; + } + + while (window_posn < frame_end) { + GET_SYMBOL(qtm->model7, selector); + if (selector < 4) { + /* literal byte */ + struct qtmd_model *mdl = (selector == 0) ? &qtm->model0 : + ((selector == 1) ? &qtm->model1 : + ((selector == 2) ? &qtm->model2 : + &qtm->model3)); + GET_SYMBOL((*mdl), sym); + window[window_posn++] = sym; + frame_todo--; + } + else { + /* match repeated string */ + switch (selector) { + case 4: /* selector 4 = fixed length match (3 bytes) */ + GET_SYMBOL(qtm->model4, sym); + READ_MANY_BITS(extra, extra_bits[sym]); + match_offset = position_base[sym] + extra + 1; + match_length = 3; + break; + + case 5: /* selector 5 = fixed length match (4 bytes) */ + GET_SYMBOL(qtm->model5, sym); + READ_MANY_BITS(extra, extra_bits[sym]); + match_offset = position_base[sym] + extra + 1; + match_length = 4; + break; + + case 6: /* selector 6 = variable length match */ + GET_SYMBOL(qtm->model6len, sym); + READ_MANY_BITS(extra, length_extra[sym]); + match_length = length_base[sym] + extra + 5; + + GET_SYMBOL(qtm->model6, sym); + READ_MANY_BITS(extra, extra_bits[sym]); + match_offset = position_base[sym] + extra + 1; + break; + + default: + /* should be impossible, model7 can only return 0-6 */ + D(("got %d from selector", selector)) + return qtm->error = MSPACK_ERR_DECRUNCH; + } + + rundest = &window[window_posn]; + frame_todo -= match_length; + + /* does match destination wrap the window? This situation is possible + * where the window size is less than the 32k frame size, but matches + * must not go beyond a frame boundary */ + if ((window_posn + match_length) > qtm->window_size) { + /* copy first part of match, before window end */ + i = qtm->window_size - window_posn; + j = window_posn - match_offset; + while (i--) *rundest++ = window[j++ & (qtm->window_size - 1)]; + + /* flush currently stored data */ + i = (&window[qtm->window_size] - qtm->o_ptr); + + /* this should not happen, but if it does then this code + * can't handle the situation (can't flush up to the end of + * the window, but can't break out either because we haven't + * finished writing the match). bail out in this case */ + if (i > out_bytes) { + D(("during window-wrap match; %d bytes to flush but only need %d", + i, (int) out_bytes)) + return qtm->error = MSPACK_ERR_DECRUNCH; + } + if (qtm->sys->write(qtm->output, qtm->o_ptr, i) != i) { + return qtm->error = MSPACK_ERR_WRITE; + } + out_bytes -= i; + qtm->o_ptr = &window[0]; + qtm->o_end = &window[0]; + + /* copy second part of match, after window wrap */ + rundest = &window[0]; + i = match_length - (qtm->window_size - window_posn); + while (i--) *rundest++ = window[j++ & (qtm->window_size - 1)]; + window_posn = window_posn + match_length - qtm->window_size; + + break; /* because "window_posn < frame_end" has now failed */ + } + else { + /* normal match - output won't wrap window or frame end */ + i = match_length; + + /* does match _offset_ wrap the window? */ + if (match_offset > window_posn) { + /* j = length from match offset to end of window */ + j = match_offset - window_posn; + if (j > (int) qtm->window_size) { + D(("match offset beyond window boundaries")) + return qtm->error = MSPACK_ERR_DECRUNCH; + } + runsrc = &window[qtm->window_size - j]; + if (j < i) { + /* if match goes over the window edge, do two copy runs */ + i -= j; while (j-- > 0) *rundest++ = *runsrc++; + runsrc = window; + } + while (i-- > 0) *rundest++ = *runsrc++; + } + else { + runsrc = rundest - match_offset; + while (i-- > 0) *rundest++ = *runsrc++; + } + window_posn += match_length; + } + } /* if (window_posn+match_length > frame_end) */ + } /* while (window_posn < frame_end) */ + + qtm->o_end = &window[window_posn]; + + /* if we subtracted too much from frame_todo, it will + * wrap around past zero and go above its max value */ + if (frame_todo > QTM_FRAME_SIZE) { + D(("overshot frame alignment")) + return qtm->error = MSPACK_ERR_DECRUNCH; + } + + /* another frame completed? */ + if (frame_todo == 0) { + /* re-align input */ + if (bits_left & 7) REMOVE_BITS(bits_left & 7); + + /* special Quantum hack -- cabd.c injects a trailer byte to allow the + * decompressor to realign itself. CAB Quantum blocks, unlike LZX + * blocks, can have anything from 0 to 4 trailing null bytes. */ + do { READ_BITS(i, 8); } while (i != 0xFF); + + qtm->header_read = 0; + + frame_todo = QTM_FRAME_SIZE; + } + + /* window wrap? */ + if (window_posn == qtm->window_size) { + /* flush all currently stored data */ + i = (qtm->o_end - qtm->o_ptr); + /* break out if we have more than enough to finish this request */ + if (i >= out_bytes) break; + if (qtm->sys->write(qtm->output, qtm->o_ptr, i) != i) { + return qtm->error = MSPACK_ERR_WRITE; + } + out_bytes -= i; + qtm->o_ptr = &window[0]; + qtm->o_end = &window[0]; + window_posn = 0; + } + + } /* while (more bytes needed) */ + + if (out_bytes) { + i = (int) out_bytes; + if (qtm->sys->write(qtm->output, qtm->o_ptr, i) != i) { + return qtm->error = MSPACK_ERR_WRITE; + } + qtm->o_ptr += i; + } + + /* store local state */ + + STORE_BITS; + qtm->window_posn = window_posn; + qtm->frame_todo = frame_todo; + qtm->H = H; + qtm->L = L; + qtm->C = C; + + return MSPACK_ERR_OK; +} + +void qtmd_free(struct qtmd_stream *qtm) { + struct mspack_system *sys; + if (qtm) { + sys = qtm->sys; + sys->free(qtm->window); + sys->free(qtm->inbuf); + sys->free(qtm); + } +} -- cgit v1.2.3