[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