/
esl_huffman.h
52 lines (43 loc) · 1.89 KB
/
esl_huffman.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/* Huffman codes for digitized alphabets
*/
#ifndef eslHUFFMAN_INCLUDED
#define eslHUFFMAN_INCLUDED
#include <esl_config.h>
typedef struct huffman_s {
int *len; // [0..K-1] = codelength 0..127. L[i]=0: symbol i is not coded.
uint32_t *code; // [0..K-1] = Huffman encoding for symbol [i], right flushed.
int K; // total # of symbols in alphabet
/* Canonical Huffman sorting */
int *sorted_at; // [0..Ku-1] = in current sort, rank #i is symidx = sorted_at[i]
int Ku; // how many symbols actually encoded & in sort; 0 < Ku <= K
/* Decoding table. */
int *dt_len; // [0..D-1] = each used codelength [d]
uint32_t *dt_lcode; // [0..D-1] = leftshifted first code for codelength [d]
int *dt_rank; // [0..D-1] = rank (in sorted_at[]) of 1st code for each codelength [d].
int D; // Number of different code lengths; size of decoding table.
int Lmax; // max code length: \max_i L[i]
} ESL_HUFFMAN;
#define eslHUFFMAN_MAXCODE 32 // Maximum <code> length in bits: uint32_t
extern int esl_huffman_Build(const float *fq, int K, ESL_HUFFMAN **ret_hc);
extern void esl_huffman_Destroy(ESL_HUFFMAN *hc);
extern int esl_huffman_Encode(const ESL_HUFFMAN *hc, const char *T, int n, uint32_t **ret_X, int *ret_nb);
extern int esl_huffman_Decode(const ESL_HUFFMAN *hc, const uint32_t *X, int nb, char **ret_T, int *ret_n);
extern int esl_huffman_Dump(FILE *fp, ESL_HUFFMAN *hc);
#endif /*eslHUFFMAN_INCLUDED*/
/* Example canonical code (Ku=7, Lmax=4)
* r L code
* 0 1 0
* 1 3 100
* 2 3 101
* 3 4 1100
* 4 4 1101
* 5 4 1110
* 6 4 1111
*
* Example decoding table (D=3)
* d dt_L dt_lcode dt_rank
* 0 1 0000 0
* 1 3 1000 1
* 2 4 1100 3
*
*/