diff options
Diffstat (limited to 'libavcodec/huffman.c')
-rw-r--r-- | libavcodec/huffman.c | 58 |
1 files changed, 58 insertions, 0 deletions
diff --git a/libavcodec/huffman.c b/libavcodec/huffman.c index 676fffe..aef4929 100644 --- a/libavcodec/huffman.c +++ b/libavcodec/huffman.c @@ -1,5 +1,6 @@ /* * Copyright (c) 2006 Konstantin Shishkov + * Copyright (c) 2007 Loren Merritt * * This file is part of Libav. * @@ -30,6 +31,63 @@ /* symbol for Huffman tree node */ #define HNODE -1 +typedef struct { + uint64_t val; + int name; +} HeapElem; + +static void heap_sift(HeapElem *h, int root, int size) +{ + while (root * 2 + 1 < size) { + int child = root * 2 + 1; + if (child < size - 1 && h[child].val > h[child+1].val) + child++; + if (h[root].val > h[child].val) { + FFSWAP(HeapElem, h[root], h[child]); + root = child; + } else + break; + } +} + +void ff_huff_gen_len_table(uint8_t *dst, const uint64_t *stats) +{ + HeapElem h[256]; + int up[2*256]; + int len[2*256]; + int offset, i, next; + int size = 256; + + for (offset = 1; ; offset <<= 1) { + for (i=0; i < size; i++) { + h[i].name = i; + h[i].val = (stats[i] << 8) + offset; + } + for (i = size / 2 - 1; i >= 0; i--) + heap_sift(h, i, size); + + for (next = size; next < size * 2 - 1; next++) { + // merge the two smallest entries, and put it back in the heap + uint64_t min1v = h[0].val; + up[h[0].name] = next; + h[0].val = INT64_MAX; + heap_sift(h, 0, size); + up[h[0].name] = next; + h[0].name = next; + h[0].val += min1v; + heap_sift(h, 0, size); + } + + len[2 * size - 2] = 0; + for (i = 2 * size - 3; i >= size; i--) + len[i] = len[up[i]] + 1; + for (i = 0; i < size; i++) { + dst[i] = len[up[i]] + 1; + if (dst[i] >= 32) break; + } + if (i==size) break; + } +} static void get_tree_codes(uint32_t *bits, int16_t *lens, uint8_t *xlat, Node *nodes, int node, |