summaryrefslogtreecommitdiff
path: root/libavcodec
diff options
context:
space:
mode:
authorMichael Niedermayer <michaelni@gmx.at>2012-08-27 16:00:47 +0200
committerLuca Barbato <lu_zero@gentoo.org>2012-08-28 17:43:25 +0200
commit5a582bd3b500918432996317b704071f462578ca (patch)
tree92e96224e35f662c16e4cca9475ec43195e9459c /libavcodec
parent998f92d680554cbefb4d34c7b3a0a791f94e8f00 (diff)
downloadffmpeg-5a582bd3b500918432996317b704071f462578ca.tar.gz
huffman: add ff_huff_gen_len_table
The function will be used by utvideo as well. Signed-off-by: Luca Barbato <lu_zero@gentoo.org>
Diffstat (limited to 'libavcodec')
-rw-r--r--libavcodec/huffman.c58
-rw-r--r--libavcodec/huffman.h2
-rw-r--r--libavcodec/huffyuv.c65
3 files changed, 63 insertions, 62 deletions
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]);