diff options
Diffstat (limited to 'libavcodec/huffman.c')
-rw-r--r-- | libavcodec/huffman.c | 114 |
1 files changed, 57 insertions, 57 deletions
diff --git a/libavcodec/huffman.c b/libavcodec/huffman.c index c8d37d78b6..27fed9f022 100644 --- a/libavcodec/huffman.c +++ b/libavcodec/huffman.c @@ -31,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, @@ -117,60 +174,3 @@ int ff_huff_build_tree(AVCodecContext *avctx, VLC *vlc, int nb_codes, } return 0; } - -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_generate_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; - } -} |