abstract/fixed/adpative jitter buffer: disallow frame re-inserts
[asterisk/asterisk.git] / main / fixedjitterbuf.c
1 /*
2  * Copyright (C) 2005, Attractel OOD
3  *
4  * Contributors:
5  * Slav Klenov <slav@securax.org>
6  *
7  * See http://www.asterisk.org for more information about
8  * the Asterisk project. Please do not directly contact
9  * any of the maintainers of this project for assistance;
10  * the project provides a web site, mailing lists and IRC
11  * channels for your use.
12  *
13  * This program is free software, distributed under the terms of
14  * the GNU General Public License Version 2. See the LICENSE file
15  * at the top of the source tree.
16  *
17  * A license has been granted to Digium (via disclaimer) for the use of
18  * this code.
19  */
20
21 /*! \file
22  *
23  * \brief Jitterbuffering algorithm.
24  *
25  * \author Slav Klenov <slav@securax.org>
26  */
27
28 /*** MODULEINFO
29         <support_level>core</support_level>
30  ***/
31
32 #include "asterisk.h"
33
34 #include <assert.h>
35
36 #include "asterisk/utils.h"
37 #include "fixedjitterbuf.h"
38
39 #undef FIXED_JB_DEBUG
40
41 #ifdef FIXED_JB_DEBUG
42 #define ASSERT(a)
43 #else
44 #define ASSERT(a) assert(a)
45 #endif
46
47 /*! \brief private fixed_jb structure */
48 struct fixed_jb
49 {
50         struct fixed_jb_frame *frames;
51         struct fixed_jb_frame *tail;
52         struct fixed_jb_conf conf;
53         long rxcore;
54         long delay;
55         long next_delivery;
56         int force_resynch;
57 };
58
59
60 static struct fixed_jb_frame *alloc_jb_frame(struct fixed_jb *jb);
61 static void release_jb_frame(struct fixed_jb *jb, struct fixed_jb_frame *frame);
62 static void get_jb_head(struct fixed_jb *jb, struct fixed_jb_frame *frame);
63 static int resynch_jb(struct fixed_jb *jb, void *data, long ms, long ts, long now);
64
65 static inline struct fixed_jb_frame *alloc_jb_frame(struct fixed_jb *jb)
66 {
67         return ast_calloc(1, sizeof(*jb));
68 }
69
70 static inline void release_jb_frame(struct fixed_jb *jb, struct fixed_jb_frame *frame)
71 {
72         ast_free(frame);
73 }
74
75 static void get_jb_head(struct fixed_jb *jb, struct fixed_jb_frame *frame)
76 {
77         struct fixed_jb_frame *fr;
78
79         /* unlink the frame */
80         fr = jb->frames;
81         jb->frames = fr->next;
82         if (jb->frames) {
83                 jb->frames->prev = NULL;
84         } else {
85                 /* the jb is empty - update tail */
86                 jb->tail = NULL;
87         }
88
89         /* update next */
90         jb->next_delivery = fr->delivery + fr->ms;
91
92         /* copy the destination */
93         memcpy(frame, fr, sizeof(struct fixed_jb_frame));
94
95         /* and release the frame */
96         release_jb_frame(jb, fr);
97 }
98
99
100 struct fixed_jb *fixed_jb_new(struct fixed_jb_conf *conf)
101 {
102         struct fixed_jb *jb;
103
104         if (!(jb = ast_calloc(1, sizeof(*jb))))
105                 return NULL;
106
107         /* First copy our config */
108         memcpy(&jb->conf, conf, sizeof(struct fixed_jb_conf));
109
110         /* we don't need the passed config anymore - continue working with the saved one */
111         conf = &jb->conf;
112
113         /* validate the configuration */
114         if (conf->jbsize < 1)
115                 conf->jbsize = FIXED_JB_SIZE_DEFAULT;
116
117         if (conf->resync_threshold < 1)
118                 conf->resync_threshold = FIXED_JB_RESYNCH_THRESHOLD_DEFAULT;
119
120         /* Set the constant delay to the jitterbuf */
121         jb->delay = conf->jbsize;
122
123         return jb;
124 }
125
126
127 void fixed_jb_destroy(struct fixed_jb *jb)
128 {
129         /* jitterbuf MUST be empty before it can be destroyed */
130         ASSERT(jb->frames == NULL);
131
132         ast_free(jb);
133 }
134
135
136 static int resynch_jb(struct fixed_jb *jb, void *data, long ms, long ts, long now)
137 {
138         long diff, offset;
139         struct fixed_jb_frame *frame;
140
141         /* If jb is empty, just reinitialize the jb */
142         if (!jb->frames) {
143                 /* debug check: tail should also be NULL */
144                 ASSERT(jb->tail == NULL);
145
146                 return fixed_jb_put_first(jb, data, ms, ts, now);
147         }
148
149         /* Adjust all jb state just as the new frame is with delivery = the delivery of the last
150            frame (e.g. this one with max delivery) + the length of the last frame. */
151
152         /* Get the diff in timestamps */
153         diff = ts - jb->tail->ts;
154
155         /* Ideally this should be just the length of the last frame. The deviation is the desired
156            offset */
157         offset = diff - jb->tail->ms;
158
159         /* Do we really need to resynch, or this is just a frame for dropping? */
160         if (!jb->force_resynch && (offset < jb->conf.resync_threshold && offset > -jb->conf.resync_threshold))
161                 return FIXED_JB_DROP;
162
163         /* Reset the force resynch flag */
164         jb->force_resynch = 0;
165
166         /* apply the offset to the jb state */
167         jb->rxcore -= offset;
168         frame = jb->frames;
169         while (frame) {
170                 frame->ts += offset;
171                 frame = frame->next;
172         }
173
174         /* now jb_put() should add the frame at a last position */
175         return fixed_jb_put(jb, data, ms, ts, now);
176 }
177
178
179 void fixed_jb_set_force_resynch(struct fixed_jb *jb)
180 {
181         jb->force_resynch = 1;
182 }
183
184
185 int fixed_jb_put_first(struct fixed_jb *jb, void *data, long ms, long ts, long now)
186 {
187         /* this is our first frame - set the base of the receivers time */
188         jb->rxcore = now - ts;
189
190         /* init next for a first time - it should be the time the first frame should be played */
191         jb->next_delivery = now + jb->delay;
192
193         /* put the frame */
194         return fixed_jb_put(jb, data, ms, ts, now);
195 }
196
197 int fixed_jb_put(struct fixed_jb *jb, void *data, long ms, long ts, long now)
198 {
199         struct fixed_jb_frame *frame, *next, *newframe;
200         long delivery;
201
202         /* debug check the validity of the input params */
203         ASSERT(data != NULL);
204         /* do not allow frames shorter than 2 ms */
205         ASSERT(ms >= 2);
206         ASSERT(ts >= 0);
207         ASSERT(now >= 0);
208
209         delivery = jb->rxcore + jb->delay + ts;
210
211         /* check if the new frame is not too late */
212         if (delivery < jb->next_delivery) {
213                 /* should drop the frame, but let first resynch_jb() check if this is not a jump in ts, or
214                    the force resynch flag was not set. */
215                 return resynch_jb(jb, data, ms, ts, now);
216         }
217
218         /* what if the delivery time is bigger than next + delay? Seems like a frame for the future.
219            However, allow more resync_threshold ms in advance */
220         if (delivery > jb->next_delivery + jb->delay + jb->conf.resync_threshold) {
221                 /* should drop the frame, but let first resynch_jb() check if this is not a jump in ts, or
222                    the force resynch flag was not set. */
223                 return resynch_jb(jb, data, ms, ts, now);
224         }
225
226         /* find the right place in the frames list, sorted by delivery time */
227         frame = jb->tail;
228         while (frame && frame->delivery > delivery) {
229                 frame = frame->prev;
230         }
231
232         /* Check if the new delivery time is not covered already by the chosen frame */
233         if (frame && (frame->delivery == delivery ||
234                          delivery < frame->delivery + frame->ms ||
235                          (frame->next && delivery + ms > frame->next->delivery)))
236         {
237                 /* TODO: Should we check for resynch here? Be careful to do not allow threshold smaller than
238                    the size of the jb */
239
240                 /* should drop the frame, but let first resynch_jb() check if this is not a jump in ts, or
241                    the force resynch flag was not set. */
242                 return resynch_jb(jb, data, ms, ts, now);
243         }
244
245         /* Reset the force resynch flag */
246         jb->force_resynch = 0;
247
248         /* Get a new frame */
249         newframe = alloc_jb_frame(jb);
250         newframe->data = data;
251         newframe->ts = ts;
252         newframe->ms = ms;
253         newframe->delivery = delivery;
254
255         /* and insert it right on place */
256         if (frame) {
257                 next = frame->next;
258                 frame->next = newframe;
259                 if (next) {
260                         newframe->next = next;
261                         next->prev = newframe;
262                 } else {
263                         /* insert after the last frame - should update tail */
264                         jb->tail = newframe;
265                         newframe->next = NULL;
266                 }
267                 newframe->prev = frame;
268
269                 return FIXED_JB_OK;
270         } else if (!jb->frames) {
271                 /* the frame list is empty or thats just the first frame ever */
272                 /* tail should also be NULL is that case */
273                 ASSERT(jb->tail == NULL);
274                 jb->frames = jb->tail = newframe;
275                 newframe->next = NULL;
276                 newframe->prev = NULL;
277
278                 return FIXED_JB_OK;
279         } else {
280                 /* insert on a first position - should update frames head */
281                 newframe->next = jb->frames;
282                 newframe->prev = NULL;
283                 jb->frames->prev = newframe;
284                 jb->frames = newframe;
285
286                 return FIXED_JB_OK;
287         }
288 }
289
290
291 int fixed_jb_get(struct fixed_jb *jb, struct fixed_jb_frame *frame, long now, long interpl)
292 {
293         ASSERT(now >= 0);
294         ASSERT(interpl >= 2);
295
296         if (now < jb->next_delivery) {
297                 /* too early for the next frame */
298                 return FIXED_JB_NOFRAME;
299         }
300
301         /* Is the jb empty? */
302         if (!jb->frames) {
303                 /* should interpolate a frame */
304                 /* update next */
305                 jb->next_delivery += interpl;
306
307                 return FIXED_JB_INTERP;
308         }
309
310         /* Isn't it too late for the first frame available in the jb? */
311         if (now > jb->frames->delivery + jb->frames->ms) {
312                 /* yes - should drop this frame and update next to point the next frame (get_jb_head() does it) */
313                 get_jb_head(jb, frame);
314
315                 return FIXED_JB_DROP;
316         }
317
318         /* isn't it too early to play the first frame available? */
319         if (now < jb->frames->delivery) {
320                 /* yes - should interpolate one frame */
321                 /* update next */
322                 jb->next_delivery += interpl;
323
324                 return FIXED_JB_INTERP;
325         }
326
327         /* we have a frame for playing now (get_jb_head() updates next) */
328         get_jb_head(jb, frame);
329
330         return FIXED_JB_OK;
331 }
332
333
334 long fixed_jb_next(struct fixed_jb *jb)
335 {
336         return jb->next_delivery;
337 }
338
339
340 int fixed_jb_remove(struct fixed_jb *jb, struct fixed_jb_frame *frameout)
341 {
342         if (!jb->frames)
343                 return FIXED_JB_NOFRAME;
344
345         get_jb_head(jb, frameout);
346
347         return FIXED_JB_OK;
348 }
349
350 int fixed_jb_is_late(struct fixed_jb *jb, long ts)
351 {
352         return jb->rxcore + jb->delay + ts < jb->next_delivery;
353 }