Skip to content

Commit

Permalink
utvideoenc: use ff_generate_len()
Browse files Browse the repository at this point in the history 
19% faster
smaller files
this may also fix possible integer overflows due to previous 32bit useage

Tested with libutvideo and our utvideo decoder, this patch does not change
decoder output in the test

Reviewed-by: Derek Buitenhuis <derek.buitenhuis@gmail.com>
Signed-off-by: Michael Niedermayer <michaelni@gmx.at>
  • Loading branch information
@michaelni
michaelni committed Aug 22, 2012
1 parent 52820bc commit f92f493
Show file tree
Hide file tree
Showing 13 changed files with 587 additions and 699 deletions.
120 changes: 4 additions & 116 deletions libavcodec/utvideoenc.c
View file
Expand Up @@ -32,6 +32,7 @@
#include "dsputil.h"
#include "mathops.h"
#include "utvideo.h"
#include "huffman.h"

/* Compare huffentry symbols */
static int huff_cmp_sym(const void *a, const void *b)
Expand Down Expand Up @@ -289,7 +290,7 @@ static void median_predict(uint8_t *src, uint8_t *dst, int step, int stride,

/* Count the usage of values in a plane */
static void count_usage(uint8_t *src, int width,
int height, uint32_t *counts)
int height, uint64_t *counts)
{
int i, j;

Expand All @@ -301,119 +302,6 @@ static void count_usage(uint8_t *src, int width,
}
}

static uint32_t add_weights(uint32_t w1, uint32_t w2)
{
uint32_t max = (w1 & 0xFF) > (w2 & 0xFF) ? (w1 & 0xFF) : (w2 & 0xFF);

return ((w1 & 0xFFFFFF00) + (w2 & 0xFFFFFF00)) | (1 + max);
}

static void up_heap(uint32_t val, uint32_t *heap, uint32_t *weights)
{
uint32_t initial_val = heap[val];

while (weights[initial_val] < weights[heap[val >> 1]]) {
heap[val] = heap[val >> 1];
val >>= 1;
}

heap[val] = initial_val;
}

static void down_heap(uint32_t nr_heap, uint32_t *heap, uint32_t *weights)
{
uint32_t val = 1;
uint32_t val2;
uint32_t initial_val = heap[val];

while (1) {
val2 = val << 1;

if (val2 > nr_heap)
break;

if (val2 < nr_heap && weights[heap[val2 + 1]] < weights[heap[val2]])
val2++;

if (weights[initial_val] < weights[heap[val2]])
break;

heap[val] = heap[val2];

val = val2;
}

heap[val] = initial_val;
}

/* Calculate the huffman code lengths from value counts */
static void calculate_code_lengths(uint8_t *lengths, uint32_t *counts)
{
uint32_t nr_nodes, nr_heap, node1, node2;
int i, j;
int32_t k;

/* Heap and node entries start from 1 */
uint32_t weights[512];
uint32_t heap[512];
int32_t parents[512];

/* Set initial weights */
for (i = 0; i < 256; i++)
weights[i + 1] = (counts[i] ? counts[i] : 1) << 8;

nr_nodes = 256;
nr_heap = 0;

heap[0] = 0;
weights[0] = 0;
parents[0] = -2;

/* Create initial nodes */
for (i = 1; i <= 256; i++) {
parents[i] = -1;

heap[++nr_heap] = i;
up_heap(nr_heap, heap, weights);
}

/* Build the tree */
while (nr_heap > 1) {
node1 = heap[1];
heap[1] = heap[nr_heap--];

down_heap(nr_heap, heap, weights);

node2 = heap[1];
heap[1] = heap[nr_heap--];

down_heap(nr_heap, heap, weights);

nr_nodes++;

parents[node1] = parents[node2] = nr_nodes;
weights[nr_nodes] = add_weights(weights[node1], weights[node2]);
parents[nr_nodes] = -1;

heap[++nr_heap] = nr_nodes;

up_heap(nr_heap, heap, weights);
}

/* Generate lengths */
for (i = 1; i <= 256; i++) {
j = 0;
k = i;

while (parents[k] >= 0) {
k = parents[k];
j++;
}

lengths[i - 1] = j;
}
}

/* Calculate the actual huffman codes from the code lengths */
static void calculate_codes(HuffEntry *he)
{
Expand Down Expand Up @@ -474,7 +362,7 @@ static int encode_plane(AVCodecContext *avctx, uint8_t *src,
{
UtvideoContext *c = avctx->priv_data;
uint8_t lengths[256];
uint32_t counts[256] = { 0 };
uint64_t counts[256] = { 0 };

HuffEntry he[256];

Expand Down Expand Up @@ -546,7 +434,7 @@ static int encode_plane(AVCodecContext *avctx, uint8_t *src,
}

/* Calculate huffman lengths */
calculate_code_lengths(lengths, counts);
ff_generate_len_table(lengths, counts);

/*
* Write the plane's header into the output packet:
Expand Down
86 changes: 43 additions & 43 deletions tests/ref/fate/utvideoenc_rgb_left
View file
@@ -1,51 +1,51 @@
#tb 0: 1/25
0, 0, 0, 1, 182328, 928d49b37c9918a1a8674a5ebf20e05a
0, 1, 1, 1, 182336, c662168526d8fcaa2d8fea224eac8814
0, 2, 2, 1, 182956, 04dd499aea666d39e6e3579441f694a5
0, 3, 3, 1, 182384, 230828b8a0eabf61a61f53009639ba4d
0, 0, 0, 1, 182328, cd084b244939d7e0008d8e5ab3429dc1
0, 1, 1, 1, 182336, c9c40672750f372134185901147fb776
0, 2, 2, 1, 182956, c728911ca73225f2dc7453533c9be95e
0, 3, 3, 1, 182384, 54521f709b461a25198db755bce582fa
0, 4, 4, 1, 181704, 5e03ab58b4480a6613f54857f10c39e5
0, 5, 5, 1, 182136, 6ee23e8eba131ae876d0e0ea7c5f40bb
0, 6, 6, 1, 181552, a930b6040ac40209da63ae14aad00169
0, 7, 7, 1, 182292, f504d5207bcd7f06064d81e438063b83
0, 8, 8, 1, 181424, b91cad343cfccdaddacbe7de21dfea76
0, 9, 9, 1, 182316, 53ed29545ff5aadc232d0fa147612d31
0, 10, 10, 1, 182064, 393d810a2838b1a997c73c485a6f7114
0, 11, 11, 1, 182596, af0c838f2268ef5a6f071cd3af4213b1
0, 12, 12, 1, 180900, 3eef962799e950342d36d069c6d16c72
0, 5, 5, 1, 182136, c623fb06b90fdd7a5ba0b4f217b6a388
0, 6, 6, 1, 181552, 5d03be9dfc01ad99364fc3cc8378af72
0, 7, 7, 1, 182292, fc90878278c82b2f835151dc6d43dd47
0, 8, 8, 1, 181424, 9b6339a0d3af2d3034162183cd4d79e4
0, 9, 9, 1, 182316, 7e45bb5ffe57f98a433420abaffe78cc
0, 10, 10, 1, 182064, d9525605a7d7d75a8e33502f61733af1
0, 11, 11, 1, 182596, 62e87fa5c33a8d208deaa8719682b9a5
0, 12, 12, 1, 180900, 149059d3d56c55358c7044c7d569730f
0, 13, 13, 1, 181920, 0d20f588c27471a038e159a131e9c8ea
0, 14, 14, 1, 182824, 7a15ecc62b8f1e127887ce1a4f27888e
0, 15, 15, 1, 182452, b5dd047a2c6ff876334511962ba3de22
0, 16, 16, 1, 182312, c974923e3d99157667410bd8185b98d2
0, 17, 17, 1, 181856, e2e836553f3bb1049a462410686ebd37
0, 18, 18, 1, 181108, 3b6d955727c6bb1c83e10783d5e322ca
0, 19, 19, 1, 181388, 19bb766c008267a87ff2bf17233bcd24
0, 20, 20, 1, 180936, c48c9f308e1d58cd227cade9f40d644d
0, 21, 21, 1, 180900, a4b5e482edd1ab63bcd107e448889b6f
0, 22, 22, 1, 181936, 43a88f8818a761ad0774e93cec6e8e34
0, 23, 23, 1, 182304, 1f75b25b6f3944cea81842d74b44ba15
0, 14, 14, 1, 182824, a301a411ff11042ecb583e1e3b12dbda
0, 15, 15, 1, 182452, 0ee2a9ed39fb8569a8d6c2b3afb8f80a
0, 16, 16, 1, 182312, 68dd3b820adf2cbc6686a7d48fa22c6e
0, 17, 17, 1, 181856, 1897926cfe9b7acaf9c21714c449ce41
0, 18, 18, 1, 181108, 15d2af460733fdd896078632cdfef9fd
0, 19, 19, 1, 181388, 8b8e7a4b7d355f41f7e836120c4792ac
0, 20, 20, 1, 180936, e18e27aa027f2470bfa95c536a0a89af
0, 21, 21, 1, 180900, eb663ae3c5ffa8e751280e0dbb260e02
0, 22, 22, 1, 181936, 7514bbe06cee027f54710dc900297863
0, 23, 23, 1, 182304, 8cb2dcdbd4c919b4c977f45bee46c54c
0, 24, 24, 1, 182580, 9185ed53b7e8339b61d3abe230bbab71
0, 25, 25, 1, 182572, f4ece21bb56548d7df0333ccf5c5cf44
0, 26, 26, 1, 182356, 281975b0138e5e3eeb2f9832b5e56bf1
0, 27, 27, 1, 181532, ce685ee2c76c3b17a63918e967371f91
0, 28, 28, 1, 179580, 331569af5ce83bd08ed631b66f3abba4
0, 25, 25, 1, 182572, 81f8bdd3255b91d6621e9ebd3c9d7679
0, 26, 26, 1, 182356, 1f9ff40700881054c62e33acde06910d
0, 27, 27, 1, 181532, 10d2477aa1e319a61e517d25fd6c95d0
0, 28, 28, 1, 179580, 3012480c43d15866ccc4a81d56650ee2
0, 29, 29, 1, 179528, 5e0fbd62a164dc72cf511023da792175
0, 30, 30, 1, 180760, 5b30e7182136e59a5da4a345f22bcb6c
0, 31, 31, 1, 181564, 53919baccc7eedc83f8a242581f0dc83
0, 32, 32, 1, 181428, 94221b58afd266a92d763b32a5c7ee8d
0, 33, 33, 1, 182980, 202c771f9d1056f8e0000028c716f134
0, 34, 34, 1, 182624, a0a1466f85870adf5fae0c922aeba348
0, 35, 35, 1, 182352, a0d790951e4f2c0e80aa94f88456d9ca
0, 30, 30, 1, 180760, 679f430c86dca203456f532e978dffc2
0, 31, 31, 1, 181564, 64d31faf01cb7b52d7d7e20280e6652b
0, 32, 32, 1, 181428, 04961d71aa3c81b33d28b39ead20ee1d
0, 33, 33, 1, 182980, 51361c802005721002f5f4924f081708
0, 34, 34, 1, 182624, 67c5582c45e3ee7e6aca49fdc0a980b8
0, 35, 35, 1, 182352, 4fade9db12f2d6ce633556fdb8914971
0, 36, 36, 1, 181336, ac8fbab67b36d58c4e8374bfb07458e7
0, 37, 37, 1, 181528, 91150acfb9da0656d52dab68b4b526df
0, 38, 38, 1, 179776, 0d91b14f5e87671583db9adbc5306247
0, 37, 37, 1, 181528, f798157b6d4d04c767ecb76346922ddc
0, 38, 38, 1, 179776, 01d407ed0b86eeb2c3ee3c24dd452d8d
0, 39, 39, 1, 180100, 062e4af150100d7accf86a907a4b99b5
0, 40, 40, 1, 180228, 23c617b76ef8f274bd089016fb8516c7
0, 41, 41, 1, 180592, 72e3aaa7131e2385845600f0793022c6
0, 42, 42, 1, 181188, 3e50bceb61a1a880f21e6f1b713c4ee3
0, 43, 43, 1, 181300, c001028d3481dc5be1c694cb4693c879
0, 44, 44, 1, 180812, bb0cabd09e9c0d4717c936a6d6532cce
0, 45, 45, 1, 178816, cae14eb93a455bd8210ab7f2f8ef31f7
0, 46, 46, 1, 178196, 5d8bb486d7b6e241e2cbd3702a97dba2
0, 47, 47, 1, 178772, 63a30c640a7aed626e4bcc749e7e594a
0, 48, 48, 1, 178652, db9f7c1968896659c00dc50cf7070184
0, 49, 49, 1, 178512, 28ce86e70639638a6da209a3e9d63eb5
0, 41, 41, 1, 180592, 55f538ae5e44b60209138b7536d5c199
0, 42, 42, 1, 181188, d39d52f5b690661434b1abd8717b3e30
0, 43, 43, 1, 181300, 9e202444287234bafd103fab83b1a974
0, 44, 44, 1, 180812, 602165271de71594132cce98af56a7b2
0, 45, 45, 1, 178816, c427d67196f43ece6bf3855e1256d7bb
0, 46, 46, 1, 178196, 0d05902e2870a85333a216c723077e98
0, 47, 47, 1, 178772, 57f528eb984b5b7181c89b48b58271f3
0, 48, 48, 1, 178652, 5cd1031b0ada3ba9c2d4c2f2b7c8e277
0, 49, 49, 1, 178512, d3c0c84fc63f1e32a4a026e2cd39b161
80 changes: 40 additions & 40 deletions tests/ref/fate/utvideoenc_rgb_median
View file
@@ -1,51 +1,51 @@
#tb 0: 1/25
0, 0, 0, 1, 182160, 927bd48282b1545ce73bf9c68670a9b4
0, 1, 1, 1, 182104, d60b5eb10ff0a5cfd928ca00c215d344
0, 2, 2, 1, 183108, eab7279cfaf1cdde8a6c874f8fd83c49
0, 0, 0, 1, 182160, abcf4f477f74b696faca2fcff1f62aa9
0, 1, 1, 1, 182104, 7cbcf339fa40c24522067295b39d637f
0, 2, 2, 1, 183108, dfc2c418f4379a89654c16b34ff19446
0, 3, 3, 1, 182320, 62a4647b05709d86c51a18be16877e98
0, 4, 4, 1, 181920, 33cef2cf9df3293153192c2d71b3e04f
0, 5, 5, 1, 182424, ca198cc391d762fce8a0d1b52bf20f4e
0, 6, 6, 1, 182248, 37666d2ea0c2c78e158b0f2eac6d367e
0, 4, 4, 1, 181920, 61d63520703503f6e17fad67cbc08794
0, 5, 5, 1, 182424, f467638396feabe613b3c851289452d8
0, 6, 6, 1, 182248, 8a0cba950d6c5d63ba9603212ca95b0e
0, 7, 7, 1, 181876, 91432f472cf373d5d4036bd100950f3e
0, 8, 8, 1, 182104, f78415ac9304c2ff0ef903debf9148bd
0, 9, 9, 1, 182540, c98da552ec452e2b6877fed05ecd7fee
0, 8, 8, 1, 182104, 1c8852d82a48c1b01911ffbedf0ac1f4
0, 9, 9, 1, 182540, f36b9d48123b55f2141ae10dd26e1ca0
0, 10, 10, 1, 182120, e6ecdb9af6591916153ca9aeba76b9d0
0, 11, 11, 1, 182136, 6367ca0d64b63303c2292b788dba0e60
0, 12, 12, 1, 181296, 59cec61dd7efc242939233b06ea683f3
0, 13, 13, 1, 182136, fc906cc12493c70f3f8fcbf640a7ffe8
0, 14, 14, 1, 182412, 571b1171b74de32801be9bd02a773eaa
0, 11, 11, 1, 182136, 7dc7b828a5b7c652df612474fad66f6b
0, 12, 12, 1, 181296, 347eac6563435a62f75298cefe13d3a6
0, 13, 13, 1, 182136, 3bbcd8afacdf9549da9ebd736df548a7
0, 14, 14, 1, 182412, 17f8c6ef692b4085624ce1ef7efbc963
0, 15, 15, 1, 182732, 9212760fa11fe4fa193ba1aa259e9765
0, 16, 16, 1, 181944, c8779690e7935000d38eba9889a40056
0, 17, 17, 1, 182232, e531631c1f9b273dd476bba14c2e36e1
0, 18, 18, 1, 181512, 012dec9becd805ded4452e9479edaa52
0, 16, 16, 1, 181944, 7dd6d6a7084f97a77ec09ec6c62f0ab8
0, 17, 17, 1, 182232, 518552687d47ae93726679f0ed962ef4
0, 18, 18, 1, 181512, 29a66924742add13a0cae65d93d38ea9
0, 19, 19, 1, 181424, 67c965637248333f92da9d493bf7546e
0, 20, 20, 1, 180764, 6139b448310c9c31f8fb6563a7fa194c
0, 20, 20, 1, 180764, 298457c6c2b3f4ebcda87a12579f094d
0, 21, 21, 1, 181072, 493ea592b7d59eebf01c002e7e22fc43
0, 22, 22, 1, 181160, 850adac4246bdf1fb1ada47e7886cb77
0, 22, 22, 1, 181160, e30195fcc16ecfbb9348943cff01623f
0, 23, 23, 1, 182156, d26cfac33e19b4ca11210c9e6cb91955
0, 24, 24, 1, 182260, 9554fd3b74b753135d298d788aae7c8d
0, 25, 25, 1, 181976, 5b94e7cd232949746691a94ebcc44fbe
0, 26, 26, 1, 181832, a0f9c815cb53396cec2164d32a900d46
0, 27, 27, 1, 181424, d2469bf8274936e282e78cb8f7f84859
0, 28, 28, 1, 180632, f1862cea94f752a8a104076ddee2f19f
0, 29, 29, 1, 180624, 01a084f93f7e58320a6972ddfba6d15d
0, 30, 30, 1, 181024, a744315a8357da7d85d23b107562270e
0, 31, 31, 1, 181844, 11d1feaef20b793f1c474014e0eccd75
0, 24, 24, 1, 182260, 963c157d3f0023b49d23099d53d60c8b
0, 25, 25, 1, 181976, 2494d481bf2be97692eaeda95f279b0d
0, 26, 26, 1, 181832, f1be95c840d4fcb0c8d4b7aed5b197c5
0, 27, 27, 1, 181424, 03d92e89358a8b9b9e7cf302edde307e
0, 28, 28, 1, 180632, 09f9e162fdaf28342c442172179a75c9
0, 29, 29, 1, 180624, 481e7f7730ab3ba67c06faa620a8bd5e
0, 30, 30, 1, 181024, 7a1d1b06b73d2bf41563eb749805780c
0, 31, 31, 1, 181844, 8a6ce6dd6f79e423a3bb6c2b163adc55
0, 32, 32, 1, 181712, a68007bbdf0169c9ed2dffae3dc63221
0, 33, 33, 1, 182008, 4880e81cfd06ae1ee7016e292f2c8a0b
0, 34, 34, 1, 181800, c40bd225be33ad95c2757d6204d83212
0, 35, 35, 1, 181840, 655275b71e3ce4999ef7b54bfd4ab7d1
0, 36, 36, 1, 181848, 072f45397965a649c3dcd42737a81381
0, 37, 37, 1, 181976, 624d00b654dec2ebb13a43a2eed726ed
0, 38, 38, 1, 181216, 9d52bb427c7d82e74aa00839f4093173
0, 39, 39, 1, 181236, 873d7aa5b7e7a6e1a64044e35891ab69
0, 40, 40, 1, 180672, f584290b2b0384f7c86ce0aa07a2c0f1
0, 41, 41, 1, 181324, 87eda71b74f8033e5a142d17beb0bccc
0, 42, 42, 1, 180980, c6a41621433317f6cce5bbc90e9b11d2
0, 43, 43, 1, 181204, df15a287bfc1dbda81be966046c0982e
0, 33, 33, 1, 182008, f37dd0635de369761e2de979ee799c3a
0, 34, 34, 1, 181800, 14029ba1c364eca476559ce553919e99
0, 35, 35, 1, 181840, ee227d15f15c3cd564dcad2160453fb7
0, 36, 36, 1, 181848, 13b5d0892cc76a25b4914f2d706a0ad5
0, 37, 37, 1, 181976, 1a0be9f2cefe0d867c5c03d6b3987ad8
0, 38, 38, 1, 181216, 79795d735f9e0f92091203bf8b9eb9ed
0, 39, 39, 1, 181236, 2d006c8c4ba448ca7841df76e44ffa88
0, 40, 40, 1, 180672, ed5210abdae49042fcae9bde2f65a057
0, 41, 41, 1, 181324, fbbc7839c595cd0f0efc0917edfed2c3
0, 42, 42, 1, 180980, c6120b5a9440f4a0d83731627eb96d98
0, 43, 43, 1, 181204, ac4371912d16f657c90e8a00cfafdfd2
0, 44, 44, 1, 180720, d392d95c67349296d922dbf53ec3f832
0, 45, 45, 1, 180028, 8bded0918eae1e10073a40df3b6f0f39
0, 46, 46, 1, 179704, d23b2c0b47d81b60b64c05303bc163eb
0, 47, 47, 1, 179648, 2a178bb890bff21a27eec2342aeecb7f
0, 48, 48, 1, 179424, 31e54f174861aa95b52ba65fdbef6af8
0, 45, 45, 1, 180028, 37a2717fbd5aaeb128812298484f8267
0, 46, 46, 1, 179704, e8716f4856e4ccdc541632a218894f62
0, 47, 47, 1, 179648, e99cbe5d1bbd7bce241ae500b4de06c2
0, 48, 48, 1, 179424, 6f8a5e356fb77b61d9dfcabdf97340b9
0, 49, 49, 1, 178980, 75a7700b822236b0ecb169fd692910f1

0 comments on commit f92f493

Please sign in to comment.