[FFmpeg-soc] [soc]: r3715 - in eac3: checkout.sh ffmpeg.patch grng.c grng.h znrng.c znrng.h
jbr
subversion at mplayerhq.hu
Sun Sep 7 03:18:04 CEST 2008
Author: jbr
Date: Sun Sep 7 03:18:04 2008
New Revision: 3715
Log:
use the faster ziggurat algorithm instead of polar for the normal PRNG
Added:
eac3/znrng.c
eac3/znrng.h
Removed:
eac3/grng.c
eac3/grng.h
Modified:
eac3/checkout.sh
eac3/ffmpeg.patch
Modified: eac3/checkout.sh
==============================================================================
--- eac3/checkout.sh (original)
+++ eac3/checkout.sh Sun Sep 7 03:18:04 2008
@@ -1,5 +1,5 @@
LAVC_FILES="eac3dec.c ac3dec.c"
-LAVU_FILES="grng.c grng.h"
+LAVU_FILES="znrng.c znrng.h"
echo "checking out ffmpeg svn"
for i in $LAVC_FILES ac3dec.h ac3dec_data.c ac3dec_data.h; do
@@ -17,7 +17,7 @@ for i in $LAVC_FILES; do
rm -f libavcodec/$i
ln -s ../../$i libavcodec/$i
done
-echo "copying the GRNG files to ffmpeg/libavutil"
+echo "copying the ZNRNG files to ffmpeg/libavutil"
for i in $LAVU_FILES; do
rm -f libavutil/$i
ln -s ../../$i libavutil/$i
Modified: eac3/ffmpeg.patch
==============================================================================
--- eac3/ffmpeg.patch (original)
+++ eac3/ffmpeg.patch Sun Sep 7 03:18:04 2008
@@ -2,20 +2,20 @@ Index: libavutil/Makefile
===================================================================
--- libavutil/Makefile (revision 15141)
+++ libavutil/Makefile (working copy)
-@@ -8,6 +8,7 @@
- crc.o \
- des.o \
- fifo.o \
-+ grng.o \
- intfloat_readwrite.o \
- lfg.o \
- lls.o \
+@@ -23,6 +23,7 @@
+ string.o \
+ tree.o \
+ utils.o \
++ znrng.o \
+
+ HEADERS = adler32.h \
+ avstring.h \
@@ -41,7 +42,7 @@
rational.h \
sha1.h
-TESTS = $(addsuffix -test$(EXESUF), adler32 aes crc des lls md5 pca random sha1 softfloat tree)
-+TESTS = $(addsuffix -test$(EXESUF), adler32 aes crc des grng lls md5 pca random sha1 softfloat tree)
++TESTS = $(addsuffix -test$(EXESUF), adler32 aes crc des lls md5 pca random sha1 softfloat tree znrng)
include $(SUBDIR)../subdir.mak
Added: eac3/znrng.c
==============================================================================
--- (empty file)
+++ eac3/znrng.c Sun Sep 7 03:18:04 2008
@@ -0,0 +1,174 @@
+/*
+ * Normal distribution PRNG following Marsaglia and Tang's Ziggurat algorithm
+ * Copyright (c) 2004 David Bateman
+ *
+ * The algorithm is described the article:
+ * Marsaglia, George and Tsang, Wai Wan (2000), The Ziggurat Method for
+ * Generating Random Variables, Journal of Statistical Software, Vol. 5,
+ * Issue 8, Oct 2000.
+ * http://www.jstatsoft.org/v05/i08/
+ *
+ * The original version written by David Bateman has been modified here to
+ * only include the normal distribution, use floats instead of doubles, and
+ * return signed 4.24-bit fixed-point integers.
+ *
+ * This file is part of FFmpeg.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The names of its contributors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+ * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "common.h"
+
+#include "znrng.h"
+
+#define NMANTISSA 0x80000000
+
+#define TAIL_CUTOFF 3.6541528853610088
+#define SLICE_AREA 0.00492867323399
+
+static int cutoff_area_ratio[256];
+static float slice_width[256];
+static float slice_y_min[256];
+
+/** get a uniformly-distributed point between 0.0 and 1.0 */
+static inline float random_float(AVRandomState *c)
+{
+ return ((av_random(c) + 0.5) / 4294967296.0);
+}
+
+/** Gaussian probabilty function */
+static inline float gpf(float x)
+{
+ return expf(-0.5*x*x);
+}
+
+/** inverse Gaussian probabilty function */
+static inline float igpf(float x)
+{
+ return sqrtf(-2.0*logf(x));
+}
+
+void av_znrng_init(AVRandomState *c, unsigned int seed)
+{
+ int i;
+ float w, w0;
+
+ av_init_random(seed, c);
+
+ w0 = TAIL_CUTOFF;
+ slice_width[255] = w0 / NMANTISSA;
+ slice_y_min[255] = gpf(w0);
+ cutoff_area_ratio[0] = w0 * slice_y_min[255] / SLICE_AREA * NMANTISSA;
+ slice_width[0] = SLICE_AREA / slice_y_min[255] / NMANTISSA;
+ slice_y_min[0] = 1.0;
+
+ for (i = 254; i > 0; i--) {
+ w = igpf(SLICE_AREA / w0 + slice_y_min[i+1]);
+ cutoff_area_ratio[i+1] = (int)(w / w0 * NMANTISSA);
+ slice_width[i] = w / NMANTISSA;
+ slice_y_min[i] = gpf(w);
+ w0 = w;
+ }
+ cutoff_area_ratio[1] = 0;
+}
+
+int av_znrng_get(AVRandomState *c)
+{
+ float x;
+ do {
+ for (;;) {
+ int ux = av_random(c);
+ int slice = ux & 0xFF;
+ x = ux * slice_width[slice];
+ if (abs(ux) < cutoff_area_ratio[slice]) {
+ break;
+ } else if (slice == 0) {
+ /* tail */
+ float y;
+ do {
+ x = -logf(random_float(c)) / TAIL_CUTOFF;
+ y = -logf(random_float(c));
+ } while (y+y <= x*x);
+ x = (ux < 0) ? -TAIL_CUTOFF-x : TAIL_CUTOFF+x;
+ break;
+ } else if ((slice_y_min[slice-1]-slice_y_min[slice])*
+ random_float(c)+slice_y_min[slice] < gpf(x)) {
+ break;
+ }
+ /* if the point is above the curve, try again */
+ }
+ } while (x < -15.0 || x > 15.0);
+ return lrintf(x * 0x8000000);
+}
+
+
+#ifdef TEST
+#include "log.h"
+
+#define TEST_COUNT 10000
+
+int main(void)
+{
+ AVRandomState c;
+ int x=0;
+ int i, j;
+ float mean, stddev;
+ float data[TEST_COUNT]={0,};
+
+ av_znrng_init(&c, 0xDEADBEEF);
+
+ for (j = 0; j < TEST_COUNT; j++) {
+ START_TIMER
+ for (i = 0; i < 624; i++) {
+ x+=av_znrng_get(&c);
+ }
+ STOP_TIMER("624 calls of av_znrng_get");
+ }
+ av_log(NULL, AV_LOG_ERROR, "final value:%X\n", x);
+
+ for (j = 0; j < 16; j++) {
+ mean = 0;
+ for(i=0; i<TEST_COUNT; i++) {
+ data[i] = (float)av_znrng_get(&c);
+ mean += data[i];
+ }
+ mean /= TEST_COUNT;
+ stddev = 0;
+ for(i=0; i<TEST_COUNT; i++) {
+ float diff = data[i] - mean;
+ stddev += (diff * diff);
+ }
+ stddev /= TEST_COUNT;
+ stddev = sqrtf(stddev);
+ av_log(NULL, AV_LOG_ERROR, "mean:%+f stddev:%f\n", mean / 0x8000000,
+ stddev / 0x8000000);
+ }
+
+ return 0;
+}
+#endif
Added: eac3/znrng.h
==============================================================================
--- (empty file)
+++ eac3/znrng.h Sun Sep 7 03:18:04 2008
@@ -0,0 +1,61 @@
+/*
+ * Normal distribution PRNG following Marsaglia and Tang's Ziggurat algorithm
+ * Copyright (c) 2004 David Bateman
+ *
+ * The algorithm is described the article:
+ * Marsaglia, George and Tsang, Wai Wan (2000), The Ziggurat Method for
+ * Generating Random Variables, Journal of Statistical Software, Vol. 5,
+ * Issue 8, Oct 2000.
+ * http://www.jstatsoft.org/v05/i08/
+ *
+ * The original version written by David Bateman has been modified here to
+ * only include the normal distribution, use floats instead of doubles, and
+ * return signed 4.24-bit fixed-point integers.
+ *
+ * This file is part of FFmpeg.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * 3. The names of its contributors may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
+ * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef AVUTIL_ZNRNG_H
+#define AVUTIL_ZNRNG_H
+
+#include "random.h"
+
+typedef struct {
+ AVRandomState rc;
+} AVZNRNG;
+
+void av_znrng_init(AVRandomState *c, unsigned int seed);
+
+/**
+ * Gets the next random signed 4.28-bit fixed-point number
+ */
+int av_znrng_get(AVRandomState *c);
+
+#endif /* AVUTIL_ZNRNG_H */
More information about the FFmpeg-soc
mailing list