ref: 128614f9cd4f97645b9275404a331f1d1fc3db42
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);
}