[FFmpeg-devel] [PATCH 3/5] lavu: add noise generator.

Nicolas George nicolas.george at normalesup.org
Sat Dec 3 11:21:31 CET 2011


Signed-off-by: Nicolas George <nicolas.george at normalesup.org>
---
 doc/APIchanges     |    3 +
 libavutil/Makefile |    2 +
 libavutil/avutil.h |    2 +-
 libavutil/noise.c  |  273 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 libavutil/noise.h  |   90 +++++++++++++++++
 5 files changed, 369 insertions(+), 1 deletions(-)
 create mode 100644 libavutil/noise.c
 create mode 100644 libavutil/noise.h

diff --git a/doc/APIchanges b/doc/APIchanges
index 6f7d46d..8d297a7 100644
--- a/doc/APIchanges
+++ b/doc/APIchanges
@@ -13,6 +13,9 @@ libavutil:   2011-04-18
 
 API changes, most recent first:
 
+2011-12-03 - xxxxxxx - lavu 51.31.0
+  Add noise generator.
+
 2011-12-03 - xxxxxxx - lavu 51.30.0
   Add AVERROR_BUG.
 
diff --git a/libavutil/Makefile b/libavutil/Makefile
index 3a5ceba..1896c07 100644
--- a/libavutil/Makefile
+++ b/libavutil/Makefile
@@ -27,6 +27,7 @@ HEADERS = adler32.h                                                     \
           mathematics.h                                                 \
           md5.h                                                         \
           mem.h                                                         \
+          noise.h                                                       \
           dict.h                                                        \
           opt.h                                                         \
           parseutils.h                                                  \
@@ -61,6 +62,7 @@ OBJS = adler32.o                                                        \
        mathematics.o                                                    \
        md5.o                                                            \
        mem.o                                                            \
+       noise.o                                                          \
        dict.o                                                           \
        opt.o                                                            \
        parseutils.o                                                     \
diff --git a/libavutil/avutil.h b/libavutil/avutil.h
index af43cc5..acc4c22 100644
--- a/libavutil/avutil.h
+++ b/libavutil/avutil.h
@@ -153,7 +153,7 @@
  */
 
 #define LIBAVUTIL_VERSION_MAJOR 51
-#define LIBAVUTIL_VERSION_MINOR 30
+#define LIBAVUTIL_VERSION_MINOR 31
 #define LIBAVUTIL_VERSION_MICRO  0
 
 #define LIBAVUTIL_VERSION_INT   AV_VERSION_INT(LIBAVUTIL_VERSION_MAJOR, \
diff --git a/libavutil/noise.c b/libavutil/noise.c
new file mode 100644
index 0000000..d24377a
--- /dev/null
+++ b/libavutil/noise.c
@@ -0,0 +1,273 @@
+/*
+ * Seekable noise generator
+ * Copyright (c) 2011 Nicolas George
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include "noise.h"
+
+/*
+ * Threehalffish cipher
+ *
+ * Threehalffish is a simple and fast cipher working on blocks of four
+ * 32-bits integers, using a key of the same size.
+ *
+ * Threehalffish is based on the Threefish cipher, designed as part of the
+ * Skein hash function proposal for SHA-3. As such, some of the
+ * cryptanalysis done on Threefish applies to Threehalffish. The significant
+ * differences are that Threefish works with bytes seen as little-endian
+ * integers while Threehalffish works directly with integers, and Threefish
+ * works with 64-bits integers, while all sizes and constants have been
+ * halved for Threehalffish.
+ *
+ * The design of Threehalffish makes it especially useful as a
+ * multidimensional seekable pseudo-random number generator (PRNG):
+ * just encode the coordinates (up to four) of the requested point and use
+ * some of the output integers.
+ *
+ * The name Threehalffish has no official meaning outside this project.
+ *
+ * This code is based on a Threefish implementation by Gaëtan Leurent,
+ * itself based on the reference implementation.
+ */
+
+struct threehalffish_ctx {
+    uint32_t k[5];
+};
+
+/* Threefish rotation constants halved */
+static const unsigned rot[8][2] = {
+    { 7,  8}, {26, 28}, {11, 20}, { 2, 18},
+    {12, 16}, {23,  6}, {29, 11}, {16, 16},
+};
+
+/* Threefish C240 (0x1BD11BDAA9FC1A22) taking one hex digit out of two */
+#define C240HALF 0xB1BA9CA2U
+
+/* Threefish default is 9, gcc will unroll up to 4. */
+#define N_8_ROUNDS 4
+
+static inline uint32_t uint32_rot_l(uint32_t x, unsigned n)
+{
+    return (x << n) | (x >> (32 - n));
+}
+
+static inline void step_forward(uint32_t x[4], unsigned n)
+{
+    unsigned a = ((n & 1) << 1) | 1;
+    unsigned b = a ^ 2;
+
+    x[0] += x[a];
+    x[a] = uint32_rot_l(x[a], rot[n][0]);
+    x[a] ^= x[0];
+    x[2] += x[b];
+    x[b] = uint32_rot_l(x[b], rot[n][1]);
+    x[b] ^= x[2];
+}
+
+static inline void inject_key(uint32_t x[4], const uint32_t k[5], unsigned n)
+{
+    unsigned i;
+
+    for(i = 0; i < 4; i++)
+        x[i] += k[(n + i) % 5];
+    x[3] += n;
+}
+
+static void threehalffish_init(struct threehalffish_ctx *th, uint32_t k[4])
+{
+    unsigned i;
+
+    th->k[4] = C240HALF;
+    for(i = 0; i < 4; i++)
+        th->k[4] ^= th->k[i] = k[i];
+}
+
+static void threehalffish_encrypt(const struct threehalffish_ctx *th,
+                                  uint32_t x[4])
+{
+    unsigned i;
+
+    inject_key(x, th->k, 0);
+    for(i = 0; i < N_8_ROUNDS; i++) {
+        step_forward(x, 0);
+        step_forward(x, 1);
+        step_forward(x, 2);
+        step_forward(x, 3);
+        inject_key(x, th->k, 2 * i + 1);
+        step_forward(x, 4);
+        step_forward(x, 5);
+        step_forward(x, 6);
+        step_forward(x, 7);
+        inject_key(x, th->k, 2 * i + 2);
+    }
+}
+
+/*
+ * White noise
+ */
+
+#define WHITE_NOISE_UNIT 256 /* must be a power of two */
+
+struct AVNoiseContextWhite {
+    AVNoiseContext noise;
+    struct threehalffish_ctx th;
+    unsigned shift;
+    int rand[WHITE_NOISE_UNIT];
+};
+
+static void av_noise_white_seek(AVNoiseContext *noisegen, int64_t ts)
+{
+    struct AVNoiseContextWhite *noise = (struct AVNoiseContextWhite *)noisegen;
+    int64_t ts0 = ts & ~(WHITE_NOISE_UNIT - 1);
+    uint32_t c[4];
+    int i, j;
+
+    for (i = 0; i < WHITE_NOISE_UNIT; i += 4) {
+        c[0] = ts0 >> 32;
+        c[1] = ts0;
+        c[2] = 0;
+        c[3] = i;
+        threehalffish_encrypt(&noise->th, c);
+        for (j = 0; j < 4; j++)
+            noise->rand[i + j] = (int32_t)c[j] >> noise->shift;
+    }
+    noise->noise.next = noise->rand + (ts & (WHITE_NOISE_UNIT - 1));
+    noise->noise.end_ts = ts0 + WHITE_NOISE_UNIT;
+}
+
+static int av_noise_white_init(AVNoiseContext **rnoise, unsigned bits,
+                               unsigned major, unsigned minor)
+{
+    struct AVNoiseContextWhite *noise = av_malloc(sizeof(*noise));
+    uint32_t key[4] = { MKTAG('F','F','N','G'), MKTAG('W','H','I','T'),
+                        major, minor };
+
+    if (!noise)
+        return AVERROR(ENOMEM);
+    noise->noise.next = noise->noise.end = noise->rand + WHITE_NOISE_UNIT;
+    noise->noise.end_ts = 0;
+    noise->noise.seek = av_noise_white_seek;
+    threehalffish_init(&noise->th, key);
+    noise->shift = 32 - bits;
+    *rnoise = &noise->noise;
+    return 0;
+}
+
+/*
+ * Pink noise
+ *
+ * This implementation emulate pink noise by summing white noise at the
+ * sampling frequency, white noise at half the sampling frequency (each
+ * value taken twice), etc., with a total of 8 octaves.
+ * This is known as the Voss-McCartney algorithm.
+ */
+
+struct AVNoiseContextPink {
+    AVNoiseContext noise;
+    struct threehalffish_ctx th;
+    unsigned shift;
+    int rand[128];
+};
+
+static void av_noise_pink_seek(AVNoiseContext *noisegen, int64_t ts)
+{
+    struct AVNoiseContextPink *noise = (struct AVNoiseContextPink *)noisegen;
+    int64_t ts0 = ts & ~127;
+    int32_t pool[128], *pc, *r;
+    int32_t vt[4] = { 0, 0, 0, 0 }, v;
+    int i, j, d;
+
+    pc = pool;
+    for (i = 0; i < 32; i++) {
+        int32_t c[4] = { ts0 >> 32, ts0, 0, i };
+        threehalffish_encrypt(&noise->th, c);
+        for (j = 0; j < 4; j++)
+            *(pc++) = c[j] >> noise->shift;
+    }
+    pc = pool;
+    r = noise->rand;
+    v = *(pc++); // comp 1/128
+    for (i = 0; i < 32; i++) {
+        int32_t c[4] = { ts0 >> 32, ts0, 1, i };
+        threehalffish_encrypt(&noise->th, c);
+        d = (i - 1) ^ i;
+        for (j = 0; j < 4; j++, d <<= 1) {
+            if (d & 16) {
+                v -= vt[j];
+                v += vt[j] = *(pc++); // comp 1/64-1/8
+            }
+        }
+        for (j = 0; j < 4; j++)
+            *(r++) = v + pc[2] + pc[j >> 1] + (c[j] >> noise->shift);
+            //            1/4     1/2          1/1
+        pc += 3;
+    }
+    noise->noise.next = noise->rand + (ts & 127);
+    noise->noise.end_ts = ts0 + 128;
+}
+
+static int av_noise_pink_init(AVNoiseContext **rnoise, unsigned bits,
+                              unsigned major, unsigned minor)
+{
+    struct AVNoiseContextPink *noise = av_malloc(sizeof(*noise));
+    uint32_t key[4] = { MKTAG('F','F','N','G'), MKTAG('P','I','N','K'),
+                        major, minor };
+
+    if (!noise)
+        return AVERROR(ENOMEM);
+    noise->noise.next = noise->noise.end = noise->rand + 128;
+    noise->noise.end_ts = 0;
+    noise->noise.seek = av_noise_pink_seek;
+    threehalffish_init(&noise->th, key);
+    noise->shift = 35 - bits;
+    *rnoise = &noise->noise;
+    return 0;
+}
+
+/*
+ * Pilot functions
+ */
+
+int av_noise_init(AVNoiseContext **noise,
+                  enum AVNoiseType type,
+                  unsigned bits,
+                  unsigned sample_rate,
+                  unsigned major,
+                  unsigned minor)
+{
+    switch (type) {
+        case AV_NOISE_WHITE:
+            return av_noise_white_init(noise, bits, major, minor);
+        case AV_NOISE_PINK_8O:
+            return av_noise_pink_init(noise, bits, major, minor);
+        default:
+            return AVERROR(EINVAL);
+    }
+}
+
+void av_noise_freep(AVNoiseContext **noise)
+{
+    av_free(*noise);
+    *noise = NULL;
+}
+
+void av_noise_seek(AVNoiseContext *noise, int64_t ts)
+{
+    noise->seek(noise, ts);
+}
diff --git a/libavutil/noise.h b/libavutil/noise.h
new file mode 100644
index 0000000..f5a8eb6
--- /dev/null
+++ b/libavutil/noise.h
@@ -0,0 +1,90 @@
+/*
+ * Seekable noise generator
+ * Copyright (c) 2011 Nicolas George
+ *
+ * This file is part of FFmpeg.
+ *
+ * FFmpeg is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * FFmpeg is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with FFmpeg; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef AVUTIL_NOISE_H
+#define AVUTIL_NOISE_H
+
+#include "common.h"
+
+/**
+ * Context to generate seekable noise
+ * This API allows to generate signed pseudo-random numbers
+ * as a seekable stream indexed by a 64-bits integer.
+ * Access to any part of the stream is made in constant time,
+ * and reading twice the same part of the stream yields the same result.
+ */
+typedef struct AVNoiseContext AVNoiseContext;
+
+struct AVNoiseContext {
+    int32_t *next, *end;
+    int64_t end_ts;
+    void (*seek)(AVNoiseContext *, int64_t);
+};
+
+enum AVNoiseType {
+    /** white noise, exactly what it says on the tin;
+     *  root mean square amplitude: 1/sqrt(3) */
+    AV_NOISE_WHITE,
+    /** pseudo-pink noise using 8 octaves of white noise;
+     *  root mean square amplitude: 1/sqrt(24) */
+    AV_NOISE_PINK_8O,
+};
+
+/**
+ * Allocate and init a noise context
+ * @param noise        used to return the allocated context
+ * @param type         type of noise desired
+ * @param bits         number of significant bits of the noise, <= 32
+ * @param sample_rate  sample rate, in Hz, may be used to tune parameters
+ * @param major        used as part of the seed for the PRNG
+ * @param minor        used as part of the seed for the PRNG
+ * @return  0 on success, <0 error code on failure
+ */
+int av_noise_init(AVNoiseContext **noise,
+                  enum AVNoiseType type,
+                  unsigned bits,
+                  unsigned sample_rate,
+                  unsigned major,
+                  unsigned minor);
+
+/**
+ * Free a noise context and set the given pointer to NULL
+ * Harmless it the pointer is already NULL.
+ */
+void av_noise_freep(AVNoiseContext **noise);
+
+/**
+ * Get the next number in the stream
+ */
+static inline int av_noise_next(AVNoiseContext *noise)
+{
+    if (noise->next == noise->end)
+        noise->seek(noise, noise->end_ts);
+    return *(noise->next++);
+}
+
+/**
+ * Seek the stream
+ * After this call, av_noise_next returns the number at index ts.
+ */
+void av_noise_seek(AVNoiseContext *noise, int64_t ts);
+
+#endif
-- 
1.7.7.3



More information about the ffmpeg-devel mailing list