ref: daf2bf42f75488f8675a5556a969ff7681346393
dir: /huffopt/huffopt.c/
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #define WROOT 5 /* fixed width (bits) of root table (MUST also be changed in the decoder C code) */ #define WMAX 7 /* max width of sub-table */ #define LAMBDA 512 /* Lagrange multiplier for MIPS/bytes trade-off: 1 table jump cost == LAMBDA bytes. Table cost = # of bytes + LAMBDA * # of jumps */ #define OPTIMIZE_SIZE 0 /* flag to force LAMBDA==0 (free jumps, table cost == table size) */ #define MIN(a, b) ((a) < (b) ? (a) : (b)) #define MAX(a, b) ((a) > (b) ? (a) : (b)) typedef struct huff_t { struct huff_t *link; struct huff_t *parent; struct huff_t *child[2]; int level; unsigned symbol; unsigned code; struct { int best_width, size; float mips; } dp; int backref; int offset; enum { E_PAIR, E_QUAD } symbol_kind; } huff_t; static int is_leaf(const huff_t *h) { return !h->child[0] && !h->child[1]; } static int imax(int a, int b) { return MAX(a, b); } static char *BIT_str(unsigned x, int bits) { // Print x as bitpattern: 01 (LBS bits) static int idx; static char buf[8][33]; // up to 8 simultaneous numbers char *p = buf[++idx & 7]; while (bits--) { *p++ = "01"[(x >> bits) & 1]; } *p++ = 0; return buf[idx & 7]; } huff_t *huff_create(huff_t *h, unsigned symbol, unsigned code, int code_len, int level, int symbol_kind) { if (!h) { h = (huff_t*)calloc(1, sizeof(huff_t)); h->level = level; h->symbol = code_len ? ~0 : symbol; h->code = code_len ? ~0 : code; h->dp.size = 1; h->dp.mips = 1.f/(1 << level); h->backref = -1; h->symbol_kind = symbol_kind; } if (h && code_len > 0) { int bit = (code >> --code_len) & 1; h->child[bit] = huff_create(h->child[bit], symbol, code, code_len, level + 1, symbol_kind); } return h; } void huff_free(huff_t *h) { if (h) { huff_free(h->child[0]); huff_free(h->child[1]); free(h); } } huff_t *read_codebook(int book) { FILE *f = fopen("HUFFCODE", "rt"); huff_t *tree = NULL; int tab = -1, mx, my, lin; do { if (4 != fscanf(f, "\n.table %d %d %d %d", &tab, &mx, &my, &lin)) { fscanf(f, "%*[^\n]"); } } while(tab != book && !feof(f)); if (tab == book) { int i, j; for (i = 0; i < mx*my; i++) { int x, y, len, icode = 0; char code[30]; if (book < 32) { while (4 != fscanf(f, "\n%d %d %d %s", &x, &y, &len, code)) { fscanf(f, "%*[^\n]"); } } else { x = 0; while (3 != fscanf(f, "\n%d %d %s", &y, &len, code)) { fscanf(f, "%*[^\n]"); } } for (j = 0; j < len; j++) { icode <<= 1; icode |= code[j] - '0'; } tree = huff_create(tree, (x << 16) + y, icode, len, 0, book < 32 ? E_PAIR : E_QUAD); } } fclose(f); return tree; } int huff_symbols_count(const huff_t *h) { return h ? is_leaf(h) + huff_symbols_count(h->child[0]) + huff_symbols_count(h->child[1]) : 0; } int huff_depth(const huff_t *h) { return is_leaf(h) ? 0 : (1 + imax(huff_depth(h->child[0]), huff_depth(h->child[1]))); } int huff_size(const huff_t *h, int depth) { return is_leaf(h) ? 0 : (--depth < 0) ? h->dp.size : huff_size(h->child[0], depth) + huff_size(h->child[1], depth); } float huff_cost(const huff_t *h, int depth) { return is_leaf(h) ? 0 : (--depth < 0) ? h->dp.mips : huff_cost(h->child[0], depth) + huff_cost(h->child[1], depth); } const huff_t *huff_decode(const huff_t *h, unsigned code, int code_len) { return (!code_len || is_leaf(h)) ? h : huff_decode(h->child[(code >> (code_len - 1)) & 1], code, code_len - 1); } void huff_optimize_partition(huff_t *h) { int i, depth, wmin, wmax; if (h && !is_leaf(h)) { // DP call: huff_optimize_partition(h->child[0]); huff_optimize_partition(h->child[1]); depth = huff_depth(h); wmin = h->level ? 1 : WROOT; wmax = wmin > 1 ? wmin : MIN(depth, WMAX); if (h->symbol_kind == E_QUAD && !h->level) { wmax = wmin = 4; } h->dp.size = huff_size(h, h->dp.best_width = wmin) + (1 << wmin); h->dp.mips = huff_cost(h, h->dp.best_width = wmin) + 1.f/(1 << h->level); for (i = wmin + 1; i <= wmax; i++) { int size = huff_size(h, i) + (1 << i); float mips = huff_cost(h, i) + 1.f/(1 << h->level); float cost_i; float cost_have; cost_i = mips*LAMBDA + size; cost_have = h->dp.mips*LAMBDA + h->dp.size; #if OPTIMIZE_SIZE cost_i = (float)size; cost_have = (float)h->dp.size; #endif if (cost_i < cost_have) { h->dp.best_width = i; h->dp.size = size; h->dp.mips = mips; } } } } void huff_print_one(const huff_t *h, FILE *f, int parent_level, int last) { if (h->symbol_kind == E_PAIR) { if (is_leaf(h)) { int x = h->symbol << 16 >> 16; int y = h->symbol << 0 >> 16; fprintf(f, last ? "%d" : "%d,", ((h->level - parent_level)*256 + (x << 4) + (y << 0))); } else { assert(h->offset < (1 << 13)); assert(h->offset); fprintf(f, last ? "%d" : "%d,", (-h->offset << 3) | h->dp.best_width); } } else { if (is_leaf(h)) { fprintf(f, last ? "%d" : "%d,", (h->symbol*16 + 8 + h->level)); } else { fprintf(f, last ? "%d" : "%d,", (h->offset << 3) | h->dp.best_width); } } } void huff_set_links_bfs(huff_t *h, FILE *f) { int print_flag; for (print_flag = 0; print_flag <= 1; print_flag++) { huff_t *q = h; huff_t *queue_head = NULL; huff_t **queue_tail = &queue_head; int offs = 0; while (q) { int i, w = 1 << q->dp.best_width; for (i = 0; i < w; i++) { huff_t *r = (huff_t *)huff_decode(q, i, q->dp.best_width); if (print_flag) { huff_print_one(r, f, q->level, 0); } if (!is_leaf(r)) { r->backref = offs;// + i; *queue_tail = r; queue_tail = &r->link; } } offs += w; q = queue_head; if (q) { if ((queue_head = q->link) != NULL) { queue_tail = &queue_head; } q->offset = offs;// - q->backref; } } } } void huff_set_links_dfs_recursion(huff_t *h, FILE *f, int print_flag, int *off) { int i, w = 1 << h->dp.best_width; h->offset = *off; *off += w; for (i = 0; print_flag && i < w; i++) { huff_print_one(huff_decode(h, i, h->dp.best_width), f, h->level, (i + 1) == w); } for (i = 0; i < w; i++) { huff_t *q = (huff_t *)huff_decode(h, i, h->dp.best_width); if (!is_leaf(q)) { if (print_flag) fprintf(f, ","); huff_set_links_dfs_recursion(q, f, print_flag, off); } } } void huff_set_links_dfs(huff_t *h, FILE *f) { int off = 0; huff_set_links_dfs_recursion(h, f, 0, &off); huff_set_links_dfs_recursion(h, f, 1, &off); }; int main() { int i; const int tabn[] = { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,24,32,33 }; int total_size = 0; int entry_bits[32]; FILE *dst_file = fopen("Huffman_tree.inl", "wt"); for (i = 0; i < sizeof(tabn)/sizeof(tabn[0]); i++) { huff_t *h = read_codebook(tabn[i]); huff_optimize_partition(h); printf("\ntable %2d ", tabn[i]); printf("%3d symbols ", huff_symbols_count(h)); printf("%3d items ", h ? h->dp.size : 0); printf("%1d entry ", h ? h->dp.best_width : 0); printf("%f average memory reads ", h ? h->dp.mips : 0); total_size += h ? h->dp.size : 0; fprintf(dst_file, " static const %s tab%d[] = { ", tabn[i] < 32 ? "int16_t" : "uint8_t", tabn[i]); if (h) { //huff_set_links_bfs(h, dst_file); huff_set_links_dfs(h, dst_file); entry_bits[i] = h->dp.best_width; } else { fprintf(dst_file, "0"); entry_bits[i] = 0; } fprintf(dst_file, " };\n"); huff_free(h); } #if WROOT > 1 fprintf(dst_file, "#define HUFF_ENTRY_BITS %d\n", WROOT); #else fprintf(dst_file, "#define HUFF_ENTRY_BITS 0\n"); fprintf(dst_file, " static const uint8_t g_entry_bits[] = { "); for (i = 0; i < sizeof(tabn)/sizeof(tabn[0]); i++) { fprintf(dst_file, "%d,", entry_bits[i]); } fprintf(dst_file, " };\n", i); #endif fclose(dst_file); printf("\n// Total: %d items\n", total_size); }