Rizin
unix-like reverse engineering framework and cli tools
readhuff.h
Go to the documentation of this file.
1 /* This file is part of libmspack.
2  * (C) 2003-2014 Stuart Caie.
3  *
4  * libmspack is free software; you can redistribute it and/or modify it under
5  * the terms of the GNU Lesser General Public License (LGPL) version 2.1
6  *
7  * For further details, see the file COPYING.LIB distributed with libmspack
8  */
9 
10 #ifndef MSPACK_READHUFF_H
11 #define MSPACK_READHUFF_H 1
12 
13 /* This implements a fast Huffman tree decoding system. */
14 
15 #if !(defined(BITS_ORDER_MSB) || defined(BITS_ORDER_LSB))
16 # error "readhuff.h is used in conjunction with readbits.h, include that first"
17 #endif
18 #if !(defined(TABLEBITS) && defined(MAXSYMBOLS))
19 # error "define TABLEBITS(tbl) and MAXSYMBOLS(tbl) before using readhuff.h"
20 #endif
21 #if !(defined(HUFF_TABLE) && defined(HUFF_LEN))
22 # error "define HUFF_TABLE(tbl) and HUFF_LEN(tbl) before using readhuff.h"
23 #endif
24 #ifndef HUFF_ERROR
25 # error "define HUFF_ERROR before using readhuff.h"
26 #endif
27 #ifndef HUFF_MAXBITS
28 # define HUFF_MAXBITS 16
29 #endif
30 
31 /* Decodes the next huffman symbol from the input bitstream into var.
32  * Do not use this macro on a table unless build_decode_table() succeeded.
33  */
34 #define READ_HUFFSYM(tbl, var) do { \
35  ENSURE_BITS(HUFF_MAXBITS); \
36  sym = HUFF_TABLE(tbl, PEEK_BITS(TABLEBITS(tbl))); \
37  if (sym >= MAXSYMBOLS(tbl)) HUFF_TRAVERSE(tbl); \
38  (var) = sym; \
39  i = HUFF_LEN(tbl, sym); \
40  REMOVE_BITS(i); \
41 } while (0)
42 
43 #ifdef BITS_ORDER_LSB
44 # define HUFF_TRAVERSE(tbl) do { \
45  i = TABLEBITS(tbl) - 1; \
46  do { \
47  if (i++ > HUFF_MAXBITS) HUFF_ERROR; \
48  sym = HUFF_TABLE(tbl, \
49  (sym << 1) | ((bit_buffer >> i) & 1)); \
50  } while (sym >= MAXSYMBOLS(tbl)); \
51 } while (0)
52 #else
53 #define HUFF_TRAVERSE(tbl) do { \
54  i = 1 << (BITBUF_WIDTH - TABLEBITS(tbl)); \
55  do { \
56  if ((i >>= 1) == 0) HUFF_ERROR; \
57  sym = HUFF_TABLE(tbl, \
58  (sym << 1) | ((bit_buffer & i) ? 1 : 0)); \
59  } while (sym >= MAXSYMBOLS(tbl)); \
60 } while (0)
61 #endif
62 
63 /* make_decode_table(nsyms, nbits, length[], table[])
64  *
65  * This function was originally coded by David Tritscher.
66  * It builds a fast huffman decoding table from
67  * a canonical huffman code lengths table.
68  *
69  * nsyms = total number of symbols in this huffman tree.
70  * nbits = any symbols with a code length of nbits or less can be decoded
71  * in one lookup of the table.
72  * length = A table to get code lengths from [0 to nsyms-1]
73  * table = The table to fill up with decoded symbols and pointers.
74  * Should be ((1<<nbits) + (nsyms*2)) in length.
75  *
76  * Returns 0 for OK or 1 for error
77  */
78 static int make_decode_table(unsigned int nsyms, unsigned int nbits,
79  unsigned char *length, unsigned short *table)
80 {
81  register unsigned short sym, next_symbol;
82  register unsigned int leaf, fill;
83 #ifdef BITS_ORDER_LSB
84  register unsigned int reverse;
85 #endif
86  register unsigned char bit_num;
87  unsigned int pos = 0; /* the current position in the decode table */
88  unsigned int table_mask = 1 << nbits;
89  unsigned int bit_mask = table_mask >> 1; /* don't do 0 length codes */
90 
91  /* fill entries for codes short enough for a direct mapping */
92  for (bit_num = 1; bit_num <= nbits; bit_num++) {
93  for (sym = 0; sym < nsyms; sym++) {
94  if (length[sym] != bit_num) continue;
95 #ifdef BITS_ORDER_MSB
96  leaf = pos;
97 #else
98  /* reverse the significant bits */
99  fill = length[sym]; reverse = pos >> (nbits - fill); leaf = 0;
100  do {leaf <<= 1; leaf |= reverse & 1; reverse >>= 1;} while (--fill);
101 #endif
102 
103  if((pos += bit_mask) > table_mask) return 1; /* table overrun */
104 
105  /* fill all possible lookups of this symbol with the symbol itself */
106 #ifdef BITS_ORDER_MSB
107  for (fill = bit_mask; fill-- > 0;) table[leaf++] = sym;
108 #else
109  fill = bit_mask; next_symbol = 1 << bit_num;
110  do { table[leaf] = sym; leaf += next_symbol; } while (--fill);
111 #endif
112  }
113  bit_mask >>= 1;
114  }
115 
116  /* exit with success if table is now complete */
117  if (pos == table_mask) return 0;
118 
119  /* mark all remaining table entries as unused */
120  for (sym = pos; sym < table_mask; sym++) {
121 #ifdef BITS_ORDER_MSB
122  table[sym] = 0xFFFF;
123 #else
124  reverse = sym; leaf = 0; fill = nbits;
125  do { leaf <<= 1; leaf |= reverse & 1; reverse >>= 1; } while (--fill);
126  table[leaf] = 0xFFFF;
127 #endif
128  }
129 
130  /* next_symbol = base of allocation for long codes */
131  next_symbol = ((table_mask >> 1) < nsyms) ? nsyms : (table_mask >> 1);
132 
133  /* give ourselves room for codes to grow by up to 16 more bits.
134  * codes now start at bit nbits+16 and end at (nbits+16-codelength) */
135  pos <<= 16;
136  table_mask <<= 16;
137  bit_mask = 1 << 15;
138 
139  for (bit_num = nbits+1; bit_num <= HUFF_MAXBITS; bit_num++) {
140  for (sym = 0; sym < nsyms; sym++) {
141  if (length[sym] != bit_num) continue;
142  if (pos >= table_mask) return 1; /* table overflow */
143 
144 #ifdef BITS_ORDER_MSB
145  leaf = pos >> 16;
146 #else
147  /* leaf = the first nbits of the code, reversed */
148  reverse = pos >> 16; leaf = 0; fill = nbits;
149  do {leaf <<= 1; leaf |= reverse & 1; reverse >>= 1;} while (--fill);
150 #endif
151  for (fill = 0; fill < (bit_num - nbits); fill++) {
152  /* if this path hasn't been taken yet, 'allocate' two entries */
153  if (table[leaf] == 0xFFFF) {
154  table[(next_symbol << 1) ] = 0xFFFF;
155  table[(next_symbol << 1) + 1 ] = 0xFFFF;
156  table[leaf] = next_symbol++;
157  }
158 
159  /* follow the path and select either left or right for next bit */
160  leaf = table[leaf] << 1;
161  if ((pos >> (15-fill)) & 1) leaf++;
162  }
163  table[leaf] = sym;
164  pos += bit_mask;
165  }
166  bit_mask >>= 1;
167  }
168 
169  /* full table? */
170  return (pos == table_mask) ? 0 : 1;
171 }
172 #endif
#define bit_mask
#define HUFF_MAXBITS
Definition: readhuff.h:28
static int make_decode_table(unsigned int nsyms, unsigned int nbits, unsigned char *length, unsigned short *table)
Definition: readhuff.h:78
static static sync static getppid static getegid const char static filename char static len const char char static bufsiz static mask static vfork const void static prot static getpgrp const char static swapflags static arg static fd static protocol static who struct sockaddr static addrlen static backlog struct timeval struct timezone static tz const struct iovec static count static mode const void const struct sockaddr static tolen const char static pathname void static offset struct stat static buf void long static basep static whence static length const void static len static semflg const void static shmflg const struct timespec struct timespec static rem const char static group const void length
Definition: sflib.h:133
int pos
Definition: main.c:11