[FFmpeg-cvslog] huffman/huffyuv: move lorens huffman table generation code to huffman.c/h
Michael Niedermayer
git at videolan.org
Wed Aug 22 16:56:09 CEST 2012
ffmpeg | branch: master | Michael Niedermayer <michaelni at gmx.at> | Wed Aug 22 03:57:45 2012 +0200| [3f943fe6815b493741ff65f6c25ca856c38cdafc] | committer: Michael Niedermayer
huffman/huffyuv: move lorens huffman table generation code to huffman.c/h
Reviewed-by: Derek Buitenhuis <derek.buitenhuis at gmail.com>
Signed-off-by: Michael Niedermayer <michaelni at gmx.at>
> http://git.videolan.org/gitweb.cgi/ffmpeg.git/?a=commit;h=3f943fe6815b493741ff65f6c25ca856c38cdafc
---
configure | 1 +
libavcodec/huffman.c | 58 +++++++++++++++++++++++++++++++++++++++++++++
libavcodec/huffman.h | 2 ++
libavcodec/huffyuv.c | 64 +++-----------------------------------------------
4 files changed, 64 insertions(+), 61 deletions(-)
diff --git a/configure b/configure
index 9c0c08f..0b95927 100755
--- a/configure
+++ b/configure
@@ -1557,6 +1557,7 @@ h264_vaapi_hwaccel_select="vaapi h264_decoder"
h264_vda_hwaccel_deps="VideoDecodeAcceleration_VDADecoder_h pthreads"
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 cd1d0d7..8b336dc 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 FFmpeg.
*
@@ -111,3 +112,60 @@ 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;
+ }
+}
diff --git a/libavcodec/huffman.h b/libavcodec/huffman.h
index 5e0787a..956ac1f 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_generate_len_table(uint8_t *dst, const uint64_t *stats);
+
#endif /* AVCODEC_HUFFMAN_H */
diff --git a/libavcodec/huffyuv.c b/libavcodec/huffyuv.c
index da242a9..0dc5c43 100644
--- a/libavcodec/huffyuv.c
+++ b/libavcodec/huffyuv.c
@@ -34,6 +34,7 @@
#include "put_bits.h"
#include "dsputil.h"
#include "thread.h"
+#include "huffman.h"
#define VLC_BITS 11
@@ -245,65 +246,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];
uint16_t bits[1<<VLC_BITS];
@@ -704,7 +646,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_generate_len_table(s->len[i], s->stats[i]);
if(generate_bits_table(s->bits[i], s->len[i])<0){
return -1;
@@ -1290,7 +1232,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_generate_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]);
More information about the ffmpeg-cvslog
mailing list