Mercurial > libavcodec.hg

changeset 5732:d6fc148d1a48 libavcodec

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
replace brute force find_optimal_param() with a closed-form solution. overall flac encoding: 4-15% faster. output is not identical to the previous algorithm due to occasional rounding errors, but the differece is less than .0005% bitrate.
author lorenm
date Sat, 29 Sep 2007 05:41:27 +0000
parents 976b4c5e68bb
children c2f88af57c16
files flacenc.c
diffstat 1 files changed, 10 insertions(+), 11 deletions(-) [+]
line wrap: on
line diff
--- a/flacenc.c	Sat Sep 29 01:54:25 2007 +0000
+++ b/flacenc.c	Sat Sep 29 05:41:27 2007 +0000
@@ -447,20 +447,19 @@
 
 #define rice_encode_count(sum, n, k) (((n)*((k)+1))+((sum-(n>>1))>>(k)))
 
+/**
+ * Solve for d/dk(rice_encode_count) = n-((sum-(n>>1))>>(k+1)) = 0
+ */
 static int find_optimal_param(uint32_t sum, int n)
 {
-    int k, k_opt;
-    uint32_t nbits[MAX_RICE_PARAM+1];
+    int k;
+    uint32_t sum2;
 
-    k_opt = 0;
-    nbits[0] = UINT32_MAX;
-    for(k=0; k<=MAX_RICE_PARAM; k++) {
-        nbits[k] = rice_encode_count(sum, n, k);
-        if(nbits[k] < nbits[k_opt]) {
-            k_opt = k;
-        }
-    }
-    return k_opt;
+    if(sum <= n>>1)
+        return 0;
+    sum2 = sum-(n>>1);
+    k = av_log2(n<256 ? FASTDIV(sum2,n) : sum2/n);
+    return FFMIN(k, MAX_RICE_PARAM);
 }
 
 static uint32_t calc_optimal_rice_params(RiceContext *rc, int porder,