Rizin
unix-like reverse engineering framework and cli tools
Macros | Functions
readhuff.h File Reference

Go to the source code of this file.

Macros

#define HUFF_MAXBITS   16
 
#define READ_HUFFSYM(tbl, var)
 
#define HUFF_TRAVERSE(tbl)
 

Functions

static int make_decode_table (unsigned int nsyms, unsigned int nbits, unsigned char *length, unsigned short *table)
 

Macro Definition Documentation

◆ HUFF_MAXBITS

#define HUFF_MAXBITS   16

Definition at line 28 of file readhuff.h.

◆ HUFF_TRAVERSE

#define HUFF_TRAVERSE (   tbl)
Value:
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)
i
lzma_index ** i
Definition: index.h:629
HUFF_TABLE
#define HUFF_TABLE(tbl, idx)
Definition: lzxd.c:97
MAXSYMBOLS
#define MAXSYMBOLS(tbl)
Definition: lzxd.c:96
HUFF_ERROR
#define HUFF_ERROR
Definition: lzxd.c:99
TABLEBITS
#define TABLEBITS(tbl)
Definition: lzxd.c:95
BITBUF_WIDTH
#define BITBUF_WIDTH
Definition: readbits.h:101
while
while(len< limit &&buf1[len]==buf2[len])++len

Definition at line 53 of file readhuff.h.

◆ READ_HUFFSYM

#define READ_HUFFSYM (   tbl,
  var 
)
Value:
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)
HUFF_LEN
#define HUFF_LEN(tbl, idx)
Definition: lzxd.c:98
PEEK_BITS
#define PEEK_BITS(nbits)
Definition: readbits.h:153
HUFF_TRAVERSE
#define HUFF_TRAVERSE(tbl)
Definition: readhuff.h:53
HUFF_MAXBITS
#define HUFF_MAXBITS
Definition: readhuff.h:28

Definition at line 34 of file readhuff.h.

Function Documentation

◆ make_decode_table()

static int make_decode_table ( unsigned int  nsyms,
unsigned int  nbits,
unsigned char *  length,
unsigned short *  table 
)
static

Definition at line 78 of file readhuff.h.

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 }
bit_mask
#define bit_mask
Definition: analysis_8051.c:392
length
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
make_dist_html.reverse
reverse
Definition: make_dist_html.py:119
pos
int pos
Definition: main.c:11

References bit_mask, HUFF_MAXBITS, length, pos, and make_dist_html::reverse.

Referenced by inflate(), and zip_read_lens().