diff options
| -rwxr-xr-x | configure | 2 | ||||
| -rw-r--r-- | libavcodec/huffman.c | 58 | ||||
| -rw-r--r-- | libavcodec/huffman.h | 2 | ||||
| -rw-r--r-- | libavcodec/huffyuv.c | 65 |
4 files changed, 65 insertions, 62 deletions
@@ -1376,6 +1376,7 @@ eatgq_decoder_select="aandcttables" eatqi_decoder_select="aandcttables error_resilience mpegvideo" ffv1_decoder_select="golomb rangecoder" ffv1_encoder_select="rangecoder" +ffvhuff_encoder_select="huffman" flac_decoder_select="golomb" flac_encoder_select="golomb lpc" flashsv_decoder_select="zlib" @@ -1397,6 +1398,7 @@ h264_dxva2_hwaccel_select="dxva2 h264_decoder" h264_vaapi_hwaccel_select="vaapi h264_decoder" h264_vda_hwaccel_select="vda h264_decoder" h264_vdpau_decoder_select="vdpau h264_decoder" +huffyuv_encoder_select="huffman" iac_decoder_select="fft mdct sinewin" imc_decoder_select="fft mdct sinewin" jpegls_decoder_select="golomb" diff --git a/libavcodec/huffman.c b/libavcodec/huffman.c index 676fffe0f5..aef4929b1c 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, diff --git a/libavcodec/huffman.h b/libavcodec/huffman.h index 5625313ac7..881c30db47 100644 --- a/libavcodec/huffman.h +++ b/libavcodec/huffman.h @@ -42,4 +42,6 @@ typedef int (*HuffCmp)(const void *va, const void *vb); int ff_huff_build_tree(AVCodecContext *avctx, VLC *vlc, int nb_codes, Node *nodes, HuffCmp cmp, int flags); +void ff_huff_gen_len_table(uint8_t *dst, const uint64_t *stats); + #endif /* AVCODEC_HUFFMAN_H */ diff --git a/libavcodec/huffyuv.c b/libavcodec/huffyuv.c index cd7a87600e..e5200e01cb 100644 --- a/libavcodec/huffyuv.c +++ b/libavcodec/huffyuv.c @@ -33,6 +33,7 @@ #include "put_bits.h" #include "dsputil.h" #include "thread.h" +#include "huffman.h" #define VLC_BITS 11 @@ -223,66 +224,6 @@ static int generate_bits_table(uint32_t *dst, const uint8_t *len_table) return 0; } -#if CONFIG_HUFFYUV_ENCODER || CONFIG_FFVHUFF_ENCODER -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; - } -} - -static void 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; - } -} -#endif /* CONFIG_HUFFYUV_ENCODER || CONFIG_FFVHUFF_ENCODER */ - static void generate_joint_tables(HYuvContext *s) { uint16_t symbols[1 << VLC_BITS]; @@ -697,7 +638,7 @@ static av_cold int encode_init(AVCodecContext *avctx) } for (i = 0; i < 3; i++) { - generate_len_table(s->len[i], s->stats[i]); + ff_huff_gen_len_table(s->len[i], s->stats[i]); if (generate_bits_table(s->bits[i], s->len[i]) < 0) { return -1; @@ -1307,7 +1248,7 @@ static int encode_frame(AVCodecContext *avctx, AVPacket *pkt, if (s->context) { for (i = 0; i < 3; i++) { - generate_len_table(s->len[i], s->stats[i]); + ff_huff_gen_len_table(s->len[i], s->stats[i]); if (generate_bits_table(s->bits[i], s->len[i]) < 0) return -1; size += store_table(s, s->len[i], &pkt->data[size]); |