avcodec/vc1: fix calculation of the last line of a slice
[ffmpeg.git] / libavcodec / ffwavesynth.c
1 /*
2  * Wavesynth pseudo-codec
3  * Copyright (c) 2011 Nicolas George
4  *
5  * This file is part of FFmpeg.
6  *
7  * FFmpeg is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public
9  * License as published by the Free Software Foundation; either
10  * version 2.1 of the License, or (at your option) any later version.
11  *
12  * FFmpeg is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with FFmpeg; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21
22 #include "libavutil/intreadwrite.h"
23 #include "libavutil/log.h"
24 #include "avcodec.h"
25 #include "internal.h"
26
27
28 #define SIN_BITS 14
29 #define WS_MAX_CHANNELS 32
30 #define INF_TS 0x7FFFFFFFFFFFFFFF
31
32 #define PINK_UNIT 128
33
34 /*
35    Format of the extradata and packets
36
37    THIS INFORMATION IS NOT PART OF THE PUBLIC API OR ABI.
38    IT CAN CHANGE WITHOUT NOTIFICATION.
39
40    All numbers are in little endian.
41
42    The codec extradata define a set of intervals with uniform content.
43    Overlapping intervals are added together.
44
45    extradata:
46        uint32      number of intervals
47        ...         intervals
48
49    interval:
50        int64       start timestamp; time_base must be 1/sample_rate;
51                    start timestamps must be in ascending order
52        int64       end timestamp
53        uint32      type
54        uint32      channels mask
55        ...         additional information, depends on type
56
57    sine interval (type fourcc "SINE"):
58        int32       start frequency, in 1/(1<<16) Hz
59        int32       end frequency
60        int32       start amplitude, 1<<16 is the full amplitude
61        int32       end amplitude
62        uint32      start phase, 0 is sin(0), 0x20000000 is sin(pi/2), etc.;
63                    n | (1<<31) means to match the phase of previous channel #n
64
65    pink noise interval (type fourcc "NOIS"):
66        int32       start amplitude
67        int32       end amplitude
68
69    The input packets encode the time and duration of the requested segment.
70
71    packet:
72        int64       start timestamp
73        int32       duration
74
75 */
76
77 enum ws_interval_type {
78     WS_SINE  = MKTAG('S','I','N','E'),
79     WS_NOISE = MKTAG('N','O','I','S'),
80 };
81
82 struct ws_interval {
83     int64_t ts_start, ts_end;
84     uint64_t phi0, dphi0, ddphi;
85     uint64_t amp0, damp;
86     uint64_t phi, dphi, amp;
87     uint32_t channels;
88     enum ws_interval_type type;
89     int next;
90 };
91
92 struct wavesynth_context {
93     int64_t cur_ts;
94     int64_t next_ts;
95     int32_t *sin;
96     struct ws_interval *inter;
97     uint32_t dither_state;
98     uint32_t pink_state;
99     int32_t pink_pool[PINK_UNIT];
100     unsigned pink_need, pink_pos;
101     int nb_inter;
102     int cur_inter;
103     int next_inter;
104 };
105
106 #define LCG_A 1284865837
107 #define LCG_C 4150755663
108 #define LCG_AI 849225893 /* A*AI = 1 [mod 1<<32] */
109
110 static uint32_t lcg_next(uint32_t *s)
111 {
112     *s = *s * LCG_A + LCG_C;
113     return *s;
114 }
115
116 static void lcg_seek(uint32_t *s, int64_t dt)
117 {
118     uint32_t a, c, t = *s;
119
120     if (dt >= 0) {
121         a = LCG_A;
122         c = LCG_C;
123     } else { /* coefficients for a step backward */
124         a = LCG_AI;
125         c = (uint32_t)(LCG_AI * LCG_C);
126         dt = -dt;
127     }
128     while (dt) {
129         if (dt & 1)
130             t = a * t + c;
131         c *= a + 1; /* coefficients for a double step */
132         a *= a;
133         dt >>= 1;
134     }
135     *s = t;
136 }
137
138 /* Emulate pink noise by summing white noise at the sampling frequency,
139  * white noise at half the sampling frequency (each value taken twice),
140  * etc., with a total of 8 octaves.
141  * This is known as the Voss-McCartney algorithm. */
142
143 static void pink_fill(struct wavesynth_context *ws)
144 {
145     int32_t vt[7] = { 0 }, v = 0;
146     int i, j;
147
148     ws->pink_pos = 0;
149     if (!ws->pink_need)
150         return;
151     for (i = 0; i < PINK_UNIT; i++) {
152         for (j = 0; j < 7; j++) {
153             if ((i >> j) & 1)
154                 break;
155             v -= vt[j];
156             vt[j] = (int32_t)lcg_next(&ws->pink_state) >> 3;
157             v += vt[j];
158         }
159         ws->pink_pool[i] = v + ((int32_t)lcg_next(&ws->pink_state) >> 3);
160     }
161     lcg_next(&ws->pink_state); /* so we use exactly 256 steps */
162 }
163
164 /**
165  * @return  (1<<64) * a / b, without overflow, if a < b
166  */
167 static uint64_t frac64(uint64_t a, uint64_t b)
168 {
169     uint64_t r = 0;
170     int i;
171
172     if (b < (uint64_t)1 << 32) { /* b small, use two 32-bits steps */
173         a <<= 32;
174         return ((a / b) << 32) | ((a % b) << 32) / b;
175     }
176     if (b < (uint64_t)1 << 48) { /* b medium, use four 16-bits steps */
177         for (i = 0; i < 4; i++) {
178             a <<= 16;
179             r = (r << 16) | (a / b);
180             a %= b;
181         }
182         return r;
183     }
184     for (i = 63; i >= 0; i--) {
185         if (a >= (uint64_t)1 << 63 || a << 1 >= b) {
186             r |= (uint64_t)1 << i;
187             a = (a << 1) - b;
188         } else {
189             a <<= 1;
190         }
191     }
192     return r;
193 }
194
195 static uint64_t phi_at(struct ws_interval *in, int64_t ts)
196 {
197     uint64_t dt = ts - in->ts_start;
198     uint64_t dt2 = dt & 1 ? /* dt * (dt - 1) / 2 without overflow */
199                    dt * ((dt - 1) >> 1) : (dt >> 1) * (dt - 1);
200     return in->phi0 + dt * in->dphi0 + dt2 * in->ddphi;
201 }
202
203 static void wavesynth_seek(struct wavesynth_context *ws, int64_t ts)
204 {
205     int *last, i;
206     struct ws_interval *in;
207
208     last = &ws->cur_inter;
209     for (i = 0; i < ws->nb_inter; i++) {
210         in = &ws->inter[i];
211         if (ts < in->ts_start)
212             break;
213         if (ts >= in->ts_end)
214             continue;
215         *last = i;
216         last = &in->next;
217         in->phi  = phi_at(in, ts);
218         in->dphi = in->dphi0 + (ts - in->ts_start) * in->ddphi;
219         in->amp  = in->amp0  + (ts - in->ts_start) * in->damp;
220     }
221     ws->next_inter = i;
222     ws->next_ts = i < ws->nb_inter ? ws->inter[i].ts_start : INF_TS;
223     *last = -1;
224     lcg_seek(&ws->dither_state, ts - ws->cur_ts);
225     if (ws->pink_need) {
226         int64_t pink_ts_cur  = (ws->cur_ts + PINK_UNIT - 1) & ~(PINK_UNIT - 1);
227         int64_t pink_ts_next = ts & ~(PINK_UNIT - 1);
228         int pos = ts & (PINK_UNIT - 1);
229         lcg_seek(&ws->pink_state, (pink_ts_next - pink_ts_cur) << 1);
230         if (pos) {
231             pink_fill(ws);
232             ws->pink_pos = pos;
233         } else {
234             ws->pink_pos = PINK_UNIT;
235         }
236     }
237     ws->cur_ts = ts;
238 }
239
240 static int wavesynth_parse_extradata(AVCodecContext *avc)
241 {
242     struct wavesynth_context *ws = avc->priv_data;
243     struct ws_interval *in;
244     uint8_t *edata, *edata_end;
245     int32_t f1, f2, a1, a2;
246     uint32_t phi;
247     int64_t dphi1, dphi2, dt, cur_ts = -0x8000000000000000;
248     int i;
249
250     if (avc->extradata_size < 4)
251         return AVERROR(EINVAL);
252     edata = avc->extradata;
253     edata_end = edata + avc->extradata_size;
254     ws->nb_inter = AV_RL32(edata);
255     edata += 4;
256     if (ws->nb_inter < 0)
257         return AVERROR(EINVAL);
258     ws->inter = av_calloc(ws->nb_inter, sizeof(*ws->inter));
259     if (!ws->inter)
260         return AVERROR(ENOMEM);
261     for (i = 0; i < ws->nb_inter; i++) {
262         in = &ws->inter[i];
263         if (edata_end - edata < 24)
264             return AVERROR(EINVAL);
265         in->ts_start = AV_RL64(edata +  0);
266         in->ts_end   = AV_RL64(edata +  8);
267         in->type     = AV_RL32(edata + 16);
268         in->channels = AV_RL32(edata + 20);
269         edata += 24;
270         if (in->ts_start < cur_ts || in->ts_end <= in->ts_start)
271             return AVERROR(EINVAL);
272         cur_ts = in->ts_start;
273         dt = in->ts_end - in->ts_start;
274         switch (in->type) {
275             case WS_SINE:
276                 if (edata_end - edata < 20)
277                     return AVERROR(EINVAL);
278                 f1  = AV_RL32(edata +  0);
279                 f2  = AV_RL32(edata +  4);
280                 a1  = AV_RL32(edata +  8);
281                 a2  = AV_RL32(edata + 12);
282                 phi = AV_RL32(edata + 16);
283                 edata += 20;
284                 dphi1 = frac64(f1, (int64_t)avc->sample_rate << 16);
285                 dphi2 = frac64(f2, (int64_t)avc->sample_rate << 16);
286                 in->dphi0 = dphi1;
287                 in->ddphi = (dphi2 - dphi1) / dt;
288                 if (phi & 0x80000000) {
289                     phi &= ~0x80000000;
290                     if (phi >= i)
291                         return AVERROR(EINVAL);
292                     in->phi0 = phi_at(&ws->inter[phi], in->ts_start);
293                 } else {
294                     in->phi0 = (uint64_t)phi << 33;
295                 }
296                 break;
297             case WS_NOISE:
298                 if (edata_end - edata < 8)
299                     return AVERROR(EINVAL);
300                 a1  = AV_RL32(edata +  0);
301                 a2  = AV_RL32(edata +  4);
302                 edata += 8;
303                 break;
304             default:
305                 return AVERROR(EINVAL);
306         }
307         in->amp0 = (int64_t)a1 << 32;
308         in->damp = (((int64_t)a2 << 32) - ((int64_t)a1 << 32)) / dt;
309     }
310     if (edata != edata_end)
311         return AVERROR(EINVAL);
312     return 0;
313 }
314
315 static av_cold int wavesynth_init(AVCodecContext *avc)
316 {
317     struct wavesynth_context *ws = avc->priv_data;
318     int i, r;
319
320     if (avc->channels > WS_MAX_CHANNELS) {
321         av_log(avc, AV_LOG_ERROR,
322                "This implementation is limited to %d channels.\n",
323                WS_MAX_CHANNELS);
324         return AVERROR(EINVAL);
325     }
326     r = wavesynth_parse_extradata(avc);
327     if (r < 0) {
328         av_log(avc, AV_LOG_ERROR, "Invalid intervals definitions.\n");
329         goto fail;
330     }
331     ws->sin = av_malloc(sizeof(*ws->sin) << SIN_BITS);
332     if (!ws->sin) {
333         r = AVERROR(ENOMEM);
334         goto fail;
335     }
336     for (i = 0; i < 1 << SIN_BITS; i++)
337         ws->sin[i] = floor(32767 * sin(2 * M_PI * i / (1 << SIN_BITS)));
338     ws->dither_state = MKTAG('D','I','T','H');
339     for (i = 0; i < ws->nb_inter; i++)
340         ws->pink_need += ws->inter[i].type == WS_NOISE;
341     ws->pink_state = MKTAG('P','I','N','K');
342     ws->pink_pos = PINK_UNIT;
343     wavesynth_seek(ws, 0);
344     avc->sample_fmt = AV_SAMPLE_FMT_S16;
345     return 0;
346
347 fail:
348     av_freep(&ws->inter);
349     av_freep(&ws->sin);
350     return r;
351 }
352
353 static void wavesynth_synth_sample(struct wavesynth_context *ws, int64_t ts,
354                                    int32_t *channels)
355 {
356     int32_t amp, val, *cv;
357     struct ws_interval *in;
358     int i, *last, pink;
359     uint32_t c, all_ch = 0;
360
361     i = ws->cur_inter;
362     last = &ws->cur_inter;
363     if (ws->pink_pos == PINK_UNIT)
364         pink_fill(ws);
365     pink = ws->pink_pool[ws->pink_pos++] >> 16;
366     while (i >= 0) {
367         in = &ws->inter[i];
368         i = in->next;
369         if (ts >= in->ts_end) {
370             *last = i;
371             continue;
372         }
373         last = &in->next;
374         amp = in->amp >> 32;
375         in->amp  += in->damp;
376         switch (in->type) {
377             case WS_SINE:
378                 val = amp * ws->sin[in->phi >> (64 - SIN_BITS)];
379                 in->phi  += in->dphi;
380                 in->dphi += in->ddphi;
381                 break;
382             case WS_NOISE:
383                 val = amp * pink;
384                 break;
385             default:
386                 val = 0;
387         }
388         all_ch |= in->channels;
389         for (c = in->channels, cv = channels; c; c >>= 1, cv++)
390             if (c & 1)
391                 *cv += val;
392     }
393     val = (int32_t)lcg_next(&ws->dither_state) >> 16;
394     for (c = all_ch, cv = channels; c; c >>= 1, cv++)
395         if (c & 1)
396             *cv += val;
397 }
398
399 static void wavesynth_enter_intervals(struct wavesynth_context *ws, int64_t ts)
400 {
401     int *last, i;
402     struct ws_interval *in;
403
404     last = &ws->cur_inter;
405     for (i = ws->cur_inter; i >= 0; i = ws->inter[i].next)
406         last = &ws->inter[i].next;
407     for (i = ws->next_inter; i < ws->nb_inter; i++) {
408         in = &ws->inter[i];
409         if (ts < in->ts_start)
410             break;
411         if (ts >= in->ts_end)
412             continue;
413         *last = i;
414         last = &in->next;
415         in->phi = in->phi0;
416         in->dphi = in->dphi0;
417         in->amp = in->amp0;
418     }
419     ws->next_inter = i;
420     ws->next_ts = i < ws->nb_inter ? ws->inter[i].ts_start : INF_TS;
421     *last = -1;
422 }
423
424 static int wavesynth_decode(AVCodecContext *avc, void *rframe, int *rgot_frame,
425                             AVPacket *packet)
426 {
427     struct wavesynth_context *ws = avc->priv_data;
428     AVFrame *frame = rframe;
429     int64_t ts;
430     int duration;
431     int s, c, r;
432     int16_t *pcm;
433     int32_t channels[WS_MAX_CHANNELS];
434
435     *rgot_frame = 0;
436     if (packet->size != 12)
437         return AVERROR_INVALIDDATA;
438     ts = AV_RL64(packet->data);
439     if (ts != ws->cur_ts)
440         wavesynth_seek(ws, ts);
441     duration = AV_RL32(packet->data + 8);
442     if (duration <= 0)
443         return AVERROR(EINVAL);
444     frame->nb_samples = duration;
445     r = ff_get_buffer(avc, frame, 0);
446     if (r < 0)
447         return r;
448     pcm = (int16_t *)frame->data[0];
449     for (s = 0; s < duration; s++, ts++) {
450         memset(channels, 0, avc->channels * sizeof(*channels));
451         if (ts >= ws->next_ts)
452             wavesynth_enter_intervals(ws, ts);
453         wavesynth_synth_sample(ws, ts, channels);
454         for (c = 0; c < avc->channels; c++)
455             *(pcm++) = channels[c] >> 16;
456     }
457     ws->cur_ts += duration;
458     *rgot_frame = 1;
459     return packet->size;
460 }
461
462 static av_cold int wavesynth_close(AVCodecContext *avc)
463 {
464     struct wavesynth_context *ws = avc->priv_data;
465
466     av_freep(&ws->sin);
467     av_freep(&ws->inter);
468     return 0;
469 }
470
471 AVCodec ff_ffwavesynth_decoder = {
472     .name           = "wavesynth",
473     .long_name      = NULL_IF_CONFIG_SMALL("Wave synthesis pseudo-codec"),
474     .type           = AVMEDIA_TYPE_AUDIO,
475     .id             = AV_CODEC_ID_FFWAVESYNTH,
476     .priv_data_size = sizeof(struct wavesynth_context),
477     .init           = wavesynth_init,
478     .close          = wavesynth_close,
479     .decode         = wavesynth_decode,
480     .capabilities   = AV_CODEC_CAP_DR1,
481 };