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/readhuff.h | 172 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 172 insertions(+) create mode 100644 utils/rbutilqt/mspack/readhuff.h (limited to 'utils/rbutilqt/mspack/readhuff.h') diff --git a/utils/rbutilqt/mspack/readhuff.h b/utils/rbutilqt/mspack/readhuff.h new file mode 100644 index 0000000000..4d94225789 --- /dev/null +++ b/utils/rbutilqt/mspack/readhuff.h @@ -0,0 +1,172 @@ +/* This file is part of libmspack. + * (C) 2003-2014 Stuart Caie. + * + * 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 + */ + +#ifndef MSPACK_READHUFF_H +#define MSPACK_READHUFF_H 1 + +/* This implements a fast Huffman tree decoding system. */ + +#if !(defined(BITS_ORDER_MSB) || defined(BITS_ORDER_LSB)) +# error "readhuff.h is used in conjunction with readbits.h, include that first" +#endif +#if !(defined(TABLEBITS) && defined(MAXSYMBOLS)) +# error "define TABLEBITS(tbl) and MAXSYMBOLS(tbl) before using readhuff.h" +#endif +#if !(defined(HUFF_TABLE) && defined(HUFF_LEN)) +# error "define HUFF_TABLE(tbl) and HUFF_LEN(tbl) before using readhuff.h" +#endif +#ifndef HUFF_ERROR +# error "define HUFF_ERROR before using readhuff.h" +#endif +#ifndef HUFF_MAXBITS +# define HUFF_MAXBITS 16 +#endif + +/* Decodes the next huffman symbol from the input bitstream into var. + * Do not use this macro on a table unless build_decode_table() succeeded. + */ +#define READ_HUFFSYM(tbl, var) do { \ + ENSURE_BITS(HUFF_MAXBITS); \ + sym = HUFF_TABLE(tbl, PEEK_BITS(TABLEBITS(tbl))); \ + if (sym >= MAXSYMBOLS(tbl)) HUFF_TRAVERSE(tbl); \ + (var) = sym; \ + i = HUFF_LEN(tbl, sym); \ + REMOVE_BITS(i); \ +} while (0) + +#ifdef BITS_ORDER_LSB +# define HUFF_TRAVERSE(tbl) do { \ + i = TABLEBITS(tbl) - 1; \ + do { \ + if (i++ > HUFF_MAXBITS) HUFF_ERROR; \ + sym = HUFF_TABLE(tbl, \ + (sym << 1) | ((bit_buffer >> i) & 1)); \ + } while (sym >= MAXSYMBOLS(tbl)); \ +} while (0) +#else +#define HUFF_TRAVERSE(tbl) do { \ + i = 1 << (BITBUF_WIDTH - TABLEBITS(tbl)); \ + do { \ + if ((i >>= 1) == 0) HUFF_ERROR; \ + sym = HUFF_TABLE(tbl, \ + (sym << 1) | ((bit_buffer & i) ? 1 : 0)); \ + } while (sym >= MAXSYMBOLS(tbl)); \ +} while (0) +#endif + +/* make_decode_table(nsyms, nbits, length[], table[]) + * + * This function was originally coded by David Tritscher. + * It builds a fast huffman decoding table from + * a canonical huffman code lengths table. + * + * nsyms = total number of symbols in this huffman tree. + * nbits = any symbols with a code length of nbits or less can be decoded + * in one lookup of the table. + * length = A table to get code lengths from [0 to nsyms-1] + * table = The table to fill up with decoded symbols and pointers. + * Should be ((1<> 1; /* don't do 0 length codes */ + + /* fill entries for codes short enough for a direct mapping */ + for (bit_num = 1; bit_num <= nbits; bit_num++) { + for (sym = 0; sym < nsyms; sym++) { + if (length[sym] != bit_num) continue; +#ifdef BITS_ORDER_MSB + leaf = pos; +#else + /* reverse the significant bits */ + fill = length[sym]; reverse = pos >> (nbits - fill); leaf = 0; + do {leaf <<= 1; leaf |= reverse & 1; reverse >>= 1;} while (--fill); +#endif + + if((pos += bit_mask) > table_mask) return 1; /* table overrun */ + + /* fill all possible lookups of this symbol with the symbol itself */ +#ifdef BITS_ORDER_MSB + for (fill = bit_mask; fill-- > 0;) table[leaf++] = sym; +#else + fill = bit_mask; next_symbol = 1 << bit_num; + do { table[leaf] = sym; leaf += next_symbol; } while (--fill); +#endif + } + bit_mask >>= 1; + } + + /* exit with success if table is now complete */ + if (pos == table_mask) return 0; + + /* mark all remaining table entries as unused */ + for (sym = pos; sym < table_mask; sym++) { +#ifdef BITS_ORDER_MSB + table[sym] = 0xFFFF; +#else + reverse = sym; leaf = 0; fill = nbits; + do { leaf <<= 1; leaf |= reverse & 1; reverse >>= 1; } while (--fill); + table[leaf] = 0xFFFF; +#endif + } + + /* next_symbol = base of allocation for long codes */ + next_symbol = ((table_mask >> 1) < nsyms) ? nsyms : (table_mask >> 1); + + /* give ourselves room for codes to grow by up to 16 more bits. + * codes now start at bit nbits+16 and end at (nbits+16-codelength) */ + pos <<= 16; + table_mask <<= 16; + bit_mask = 1 << 15; + + for (bit_num = nbits+1; bit_num <= HUFF_MAXBITS; bit_num++) { + for (sym = 0; sym < nsyms; sym++) { + if (length[sym] != bit_num) continue; + if (pos >= table_mask) return 1; /* table overflow */ + +#ifdef BITS_ORDER_MSB + leaf = pos >> 16; +#else + /* leaf = the first nbits of the code, reversed */ + reverse = pos >> 16; leaf = 0; fill = nbits; + do {leaf <<= 1; leaf |= reverse & 1; reverse >>= 1;} while (--fill); +#endif + for (fill = 0; fill < (bit_num - nbits); fill++) { + /* if this path hasn't been taken yet, 'allocate' two entries */ + if (table[leaf] == 0xFFFF) { + table[(next_symbol << 1) ] = 0xFFFF; + table[(next_symbol << 1) + 1 ] = 0xFFFF; + table[leaf] = next_symbol++; + } + + /* follow the path and select either left or right for next bit */ + leaf = table[leaf] << 1; + if ((pos >> (15-fill)) & 1) leaf++; + } + table[leaf] = sym; + pos += bit_mask; + } + bit_mask >>= 1; + } + + /* full table? */ + return (pos == table_mask) ? 0 : 1; +} +#endif -- cgit v1.2.3