365ec44f09e28edfb78753506444ef8903d84b42
[asterisk/asterisk.git] / jitterbuf.c
1 /*
2  * jitterbuf: an application-independent jitterbuffer
3  *
4  * Copyrights:
5  * Copyright (C) 2004-2005, Horizon Wimba, Inc.
6  *
7  * Contributors:
8  * Steve Kann <stevek@stevek.com>
9  *
10  * This program is free software, distributed under the terms of
11  * the GNU Lesser (Library) General Public License
12  *
13  * Copyright on this file is disclaimed to Digium for inclusion in Asterisk
14  */
15
16 #include <stdio.h>
17 #include <stdlib.h>
18 #include <string.h>
19
20 #include "jitterbuf.h"
21
22 /* define these here, just for ancient compiler systems */
23 #define JB_LONGMAX 2147483647L
24 #define JB_LONGMIN (-JB_LONGMAX - 1L)
25
26 #define jb_warn(...) (warnf ? warnf(__VA_ARGS__) : (void)0)
27 #define jb_err(...) (errf ? errf(__VA_ARGS__) : (void)0)
28 #define jb_dbg(...) (dbgf ? dbgf(__VA_ARGS__) : (void)0)
29
30 #ifdef DEEP_DEBUG
31 #define jb_dbg2(...) (dbgf ? dbgf(__VA_ARGS__) : (void)0)
32 #else
33 #define jb_dbg2(...) ((void)0)
34 #endif
35
36 static jb_output_function_t warnf, errf, dbgf;
37
38 void jb_setoutput(jb_output_function_t warn, jb_output_function_t err, jb_output_function_t dbg) 
39 {
40         warnf = warn;
41         errf = err;
42         dbgf = dbg;
43 }
44
45 static void increment_losspct(jitterbuf *jb) 
46 {
47         jb->info.losspct = (100000 + 499 * jb->info.losspct)/500;    
48 }
49
50 static void decrement_losspct(jitterbuf *jb) 
51 {
52         jb->info.losspct = (499 * jb->info.losspct)/500;    
53 }
54
55 void jb_reset(jitterbuf *jb) 
56 {
57         memset(jb,0,sizeof(jitterbuf));
58
59         /* initialize length */
60         jb->info.current = jb->info.target = 0; 
61         jb->info.silence = 1; 
62 }
63
64 jitterbuf * jb_new() 
65 {
66         jitterbuf *jb;
67
68
69         jb = malloc(sizeof(jitterbuf));
70         if (!jb) 
71                 return NULL;
72
73         jb_reset(jb);
74
75         jb_dbg2("jb_new() = %x\n", jb);
76         return jb;
77 }
78
79 void jb_destroy(jitterbuf *jb) 
80 {
81         jb_frame *frame; 
82         jb_dbg2("jb_destroy(%x)\n", jb);
83
84         /* free all the frames on the "free list" */
85         frame = jb->free;
86         while (frame != NULL) {
87                 jb_frame *next = frame->next;
88                 free(frame);
89                 frame = next;
90         }
91
92         /* free ourselves! */ 
93         free(jb);
94 }
95
96
97
98 /* simple history manipulation */
99 /* maybe later we can make the history buckets variable size, or something? */
100 /* drop parameter determines whether we will drop outliers to minimize
101  * delay */
102 #if 0
103 static int longcmp(const void *a, const void *b) 
104 {
105         return *(long *)a - *(long *)b;
106 }
107 #endif
108
109 static void history_put(jitterbuf *jb, long ts, long now) 
110 {
111         long delay = now - ts;
112         long kicked;
113
114         /* don't add special/negative times to history */
115         if (ts <= 0) 
116                 return;
117
118         kicked = jb->history[jb->hist_ptr & JB_HISTORY_SZ];
119
120         jb->history[(jb->hist_ptr++) % JB_HISTORY_SZ] = delay;
121
122         /* optimization; the max/min buffers don't need to be recalculated, if this packet's
123          * entry doesn't change them.  This happens if this packet is not involved, _and_ any packet
124          * that got kicked out of the history is also not involved 
125          * We do a number of comparisons, but it's probably still worthwhile, because it will usually
126          * succeed, and should be a lot faster than going through all 500 packets in history */
127         if (!jb->hist_maxbuf_valid)
128                 return;
129
130         /* don't do this until we've filled history 
131          * (reduces some edge cases below) */
132         if (jb->hist_ptr < JB_HISTORY_SZ)
133                 goto invalidate;
134
135         /* if the new delay would go into min */
136         if (delay < jb->hist_minbuf[JB_HISTORY_MAXBUF_SZ-1])
137                 goto invalidate;
138     
139         /* or max.. */
140         if (delay > jb->hist_maxbuf[JB_HISTORY_MAXBUF_SZ-1])
141                 goto invalidate;
142
143         /* or the kicked delay would be in min */
144         if (kicked <= jb->hist_minbuf[JB_HISTORY_MAXBUF_SZ-1]) 
145                 goto invalidate;
146
147         if (kicked >= jb->hist_maxbuf[JB_HISTORY_MAXBUF_SZ-1]) 
148                 goto invalidate;
149
150         /* if we got here, we don't need to invalidate, 'cause this delay didn't 
151          * affect things */
152         return;
153         /* end optimization */
154
155
156 invalidate:
157         jb->hist_maxbuf_valid = 0;
158         return;
159 }
160
161 static void history_calc_maxbuf(jitterbuf *jb) 
162 {
163         int i,j;
164
165         if (jb->hist_ptr == 0) 
166                 return;
167
168
169         /* initialize maxbuf/minbuf to the latest value */
170         for (i=0;i<JB_HISTORY_MAXBUF_SZ;i++) {
171 /*
172  * jb->hist_maxbuf[i] = jb->history[(jb->hist_ptr-1) % JB_HISTORY_SZ];
173  * jb->hist_minbuf[i] = jb->history[(jb->hist_ptr-1) % JB_HISTORY_SZ];
174  */
175                 jb->hist_maxbuf[i] = JB_LONGMIN;
176                 jb->hist_minbuf[i] = JB_LONGMAX;
177         }
178
179         /* use insertion sort to populate maxbuf */
180         /* we want it to be the top "n" values, in order */
181
182         /* start at the beginning, or JB_HISTORY_SZ frames ago */
183         i = (jb->hist_ptr > JB_HISTORY_SZ) ? (jb->hist_ptr - JB_HISTORY_SZ) : 0; 
184
185         for (;i<jb->hist_ptr;i++) {
186                 long toins = jb->history[i % JB_HISTORY_SZ];
187
188                 /* if the maxbuf should get this */
189                 if (toins > jb->hist_maxbuf[JB_HISTORY_MAXBUF_SZ-1])  {
190
191                         /* insertion-sort it into the maxbuf */
192                         for (j=0;j<JB_HISTORY_MAXBUF_SZ;j++) {
193                                 /* found where it fits */
194                                 if (toins > jb->hist_maxbuf[j]) {
195                                         /* move over */
196                                         memmove(jb->hist_maxbuf+j+1,jb->hist_maxbuf+j, (JB_HISTORY_MAXBUF_SZ-(j+1)) * sizeof(long));
197                                         /* insert */
198                                         jb->hist_maxbuf[j] = toins;
199
200                                         break;
201                                 }
202                         }
203                 }
204
205                 /* if the minbuf should get this */
206                 if (toins < jb->hist_minbuf[JB_HISTORY_MAXBUF_SZ-1])  {
207
208                         /* insertion-sort it into the maxbuf */
209                         for (j=0;j<JB_HISTORY_MAXBUF_SZ;j++) {
210                                 /* found where it fits */
211                                 if (toins < jb->hist_minbuf[j]) {
212                                         /* move over */
213                                         memmove(jb->hist_minbuf+j+1,jb->hist_minbuf+j, (JB_HISTORY_MAXBUF_SZ-(j+1)) * sizeof(long));
214                                         /* insert */
215                                         jb->hist_minbuf[j] = toins;
216
217                                         break;
218                                 }
219                         }
220                 }
221
222                 if (0) { 
223                         int k;
224                         fprintf(stderr, "toins = %ld\n", toins);
225                         fprintf(stderr, "maxbuf =");
226                         for (k=0;k<JB_HISTORY_MAXBUF_SZ;k++) 
227                                 fprintf(stderr, "%ld ", jb->hist_maxbuf[k]);
228                         fprintf(stderr, "\nminbuf =");
229                         for (k=0;k<JB_HISTORY_MAXBUF_SZ;k++) 
230                                 fprintf(stderr, "%ld ", jb->hist_minbuf[k]);
231                         fprintf(stderr, "\n");
232                 }
233         }
234
235         jb->hist_maxbuf_valid = 1;
236 }
237
238 static void history_get(jitterbuf *jb) 
239 {
240         long max, min, jitter;
241         int index;
242         int count;
243
244         if (!jb->hist_maxbuf_valid) 
245                 history_calc_maxbuf(jb);
246
247         /* count is how many items in history we're examining */
248         count = (jb->hist_ptr < JB_HISTORY_SZ) ? jb->hist_ptr : JB_HISTORY_SZ;
249
250         /* index is the "n"ths highest/lowest that we'll look for */
251         index = count * JB_HISTORY_DROPPCT / 100;
252
253         /* sanity checks for index */
254         if (index > (JB_HISTORY_MAXBUF_SZ - 1)) 
255                 index = JB_HISTORY_MAXBUF_SZ - 1;
256
257
258         if (index < 0) {
259                 jb->info.min = 0;
260                 jb->info.jitter = 0;
261                 return;
262         }
263
264         max = jb->hist_maxbuf[index];
265         min = jb->hist_minbuf[index];
266
267         jitter = max - min;
268
269         /* these debug stmts compare the difference between looking at the absolute jitter, and the
270          * values we get by throwing away the outliers */
271         /*
272         fprintf(stderr, "[%d] min=%d, max=%d, jitter=%d\n", index, min, max, jitter);
273         fprintf(stderr, "[%d] min=%d, max=%d, jitter=%d\n", 0, jb->hist_minbuf[0], jb->hist_maxbuf[0], jb->hist_maxbuf[0]-jb->hist_minbuf[0]);
274         */
275
276         jb->info.min = min;
277         jb->info.jitter = jitter;
278 }
279
280 static void queue_put(jitterbuf *jb, void *data, int type, long ms, long ts) 
281 {
282         jb_frame *frame;
283         jb_frame *p;
284
285         frame = jb->free;
286         if (frame) {
287                 jb->free = frame->next;
288         } else {
289                 frame = malloc(sizeof(jb_frame));
290         }
291
292         if (!frame) {
293                 jb_err("cannot allocate frame\n");
294                 return;
295         }
296
297         jb->info.frames_cur++;
298
299         frame->data = data;
300         frame->ts = ts;
301         frame->ms = ms;
302         frame->type = type;
303
304         /* 
305          * frames are a circular list, jb-frames points to to the lowest ts, 
306          * jb->frames->prev points to the highest ts
307          */
308
309         if (!jb->frames) {  /* queue is empty */
310                 jb->frames = frame;
311                 frame->next = frame;
312                 frame->prev = frame;
313                 frame->prev = jb->frames->prev;
314
315                 frame->next->prev = frame;
316                 frame->prev->next = frame;
317
318                 jb->frames = frame;
319         } else { 
320                 p = jb->frames;
321
322                 /* frame is out of order */
323                 if (ts < p->prev->ts) jb->info.frames_ooo++;
324
325                 while (ts < p->prev->ts && p->prev != jb->frames) 
326                         p = p->prev;
327
328                 frame->next = p;
329                 frame->prev = p->prev;
330
331                 frame->next->prev = frame;
332                 frame->prev->next = frame;
333         }
334 }
335
336 static long queue_next(jitterbuf *jb) 
337 {
338         if (jb->frames) 
339                 return jb->frames->ts;
340         else 
341                 return -1;
342 }
343
344 static long queue_last(jitterbuf *jb) 
345 {
346         if (jb->frames) 
347                 return jb->frames->prev->ts;
348         else 
349                 return -1;
350 }
351
352 static jb_frame *_queue_get(jitterbuf *jb, long ts, int all) 
353 {
354         jb_frame *frame;
355         frame = jb->frames;
356
357         if (!frame)
358                 return NULL;
359
360         /*jb_warn("queue_get: ASK %ld FIRST %ld\n", ts, frame->ts); */
361
362         if (all || ts > frame->ts) {
363                 /* remove this frame */
364                 frame->prev->next = frame->next;
365                 frame->next->prev = frame->prev;
366
367                 if (frame->next == frame)
368                         jb->frames = NULL;
369                 else
370                         jb->frames = frame->next;
371
372
373                 /* insert onto "free" single-linked list */
374                 frame->next = jb->free;
375                 jb->free = frame;
376
377                 jb->info.frames_cur--;
378
379                 /* we return the frame pointer, even though it's on free list, 
380                  * but caller must copy data */
381                 return frame;
382         } 
383
384         return NULL;
385 }
386
387 static jb_frame *queue_get(jitterbuf *jb, long ts) 
388 {
389         return _queue_get(jb,ts,0);
390 }
391
392 static jb_frame *queue_getall(jitterbuf *jb) 
393 {
394         return _queue_get(jb,0,1);
395 }
396
397 #if 0
398 /* some diagnostics */
399 static void jb_dbginfo(jitterbuf *jb) 
400 {
401         if (dbgf == NULL) 
402                 return;
403
404         jb_dbg("\njb info: fin=%ld fout=%ld flate=%ld flost=%ld fdrop=%ld fcur=%ld\n",
405                 jb->info.frames_in, jb->info.frames_out, jb->info.frames_late, jb->info.frames_lost, jb->info.frames_dropped, jb->info.frames_cur);
406         
407         jb_dbg("jitter=%ld current=%ld target=%ld min=%ld sil=%d len=%d len/fcur=%ld\n",
408                 jb->info.jitter, jb->info.current, jb->info.target, jb->info.min, jb->info.silence, jb->info.current - jb->info.min, 
409                 jb->info.frames_cur ? (jb->info.current - jb->info.min)/jb->info.frames_cur : -8);
410         if (jb->info.frames_in > 0) 
411                 jb_dbg("jb info: Loss PCT = %ld%%, Late PCT = %ld%%\n",
412                         jb->info.frames_lost * 100/(jb->info.frames_in + jb->info.frames_lost), 
413                         jb->info.frames_late * 100/jb->info.frames_in);
414         jb_dbg("jb info: queue %d -> %d.  last_ts %d (queue len: %d) last_ms %d\n",
415                 queue_next(jb), 
416                 queue_last(jb),
417                 jb->info.last_voice_ts, 
418                 queue_last(jb) - queue_next(jb),
419                 jb->info.last_voice_ms);
420 }
421 #endif
422
423 #ifdef DEEP_DEBUG
424 static void jb_chkqueue(jitterbuf *jb) 
425 {
426         int i=0;
427         jb_frame *p = jb->frames;
428
429         if (!p) {
430                 return;
431         }
432
433         do {
434                 if (p->next == NULL)  {
435                         jb_err("Queue is BROKEN at item [%d]", i);      
436                 }
437                 i++;
438                 p=p->next;
439         } while (p->next != jb->frames);
440 }
441
442 static void jb_dbgqueue(jitterbuf *jb) 
443 {
444         int i=0;
445         jb_frame *p = jb->frames;
446
447         jb_dbg("queue: ");
448
449         if (!p) {
450                 jb_dbg("EMPTY\n");
451                 return;
452         }
453
454         do {
455                 jb_dbg("[%d]=%ld ", i++, p->ts);
456                 p=p->next;
457         } while (p->next != jb->frames);
458
459         jb_dbg("\n");
460 }
461 #endif
462
463 int jb_put(jitterbuf *jb, void *data, int type, long ms, long ts, long now) 
464 {
465         jb_dbg2("jb_put(%x,%x,%ld,%ld,%ld)\n", jb, data, ms, ts, now);
466
467         jb->info.frames_in++;
468
469         if (type == JB_TYPE_VOICE) {
470                 /* presently, I'm only adding VOICE frames to history and drift calculations; mostly because with the
471                  * IAX integrations, I'm sending retransmitted control frames with their awkward timestamps through */
472                 history_put(jb,ts,now);
473         }
474
475         queue_put(jb,data,type,ms,ts);
476
477         return JB_OK;
478 }
479
480
481 static int _jb_get(jitterbuf *jb, jb_frame *frameout, long now) 
482 {
483         jb_frame *frame;
484         long diff;
485
486         /*if ((now - jb_next(jb)) > 2 * jb->info.last_voice_ms) jb_warn("SCHED: %ld", (now - jb_next(jb))); */
487         /* get jitter info */
488         history_get(jb);
489
490
491         /* target */
492         jb->info.target = jb->info.jitter + jb->info.min + 2 * jb->info.last_voice_ms; 
493
494         /* if a hard clamp was requested, use it */
495         if ((jb->info.max_jitterbuf) && ((jb->info.target - jb->info.min) > jb->info.max_jitterbuf)) {
496                 jb_dbg("clamping target from %d to %d\n", (jb->info.target - jb->info.min), jb->info.max_jitterbuf);
497                         jb->info.target = jb->info.min + jb->info.max_jitterbuf;
498         }
499
500         diff = jb->info.target - jb->info.current;
501
502         /* jb_warn("diff = %d lms=%d last = %d now = %d\n", diff,  */
503         /*      jb->info.last_voice_ms, jb->info.last_adjustment, now); */
504
505         /* move up last_voice_ts; it is now the expected voice ts */
506         jb->info.last_voice_ts += jb->info.last_voice_ms;
507
508         /* let's work on non-silent case first */
509         if (!jb->info.silence) { 
510                 /* we want to grow */
511                 if ((diff > 0) && 
512                         /* we haven't grown in 2 frames' length */
513                         (((jb->info.last_adjustment + 2 * jb->info.last_voice_ms ) < now) || 
514                         /* we need to grow more than the "length" we have left */
515                         (diff > queue_last(jb)  - queue_next(jb)) ) ) {
516                         
517                         jb->info.current += jb->info.last_voice_ms;
518                         jb->info.last_adjustment = now;
519                         jb_dbg("G");
520                         return JB_INTERP;
521                 }
522
523                 frame = queue_get(jb, jb->info.last_voice_ts - jb->info.current);
524
525                 /* not a voice frame; just return it. */
526                 if (frame && frame->type != JB_TYPE_VOICE) {
527                         /* rewind last_voice_ts, since this isn't voice */
528                         jb->info.last_voice_ts -= jb->info.last_voice_ms;
529
530                         if (frame->type == JB_TYPE_SILENCE) 
531                                 jb->info.silence = 1;
532
533                         *frameout = *frame;
534                         jb->info.frames_out++;
535                         jb_dbg("o");
536                         return JB_OK;
537                 }
538
539
540                 /* voice frame is late */
541                 if (frame && frame->ts + jb->info.current < jb->info.last_voice_ts - jb->info.last_voice_ms ) {
542                         *frameout = *frame;
543                         /* rewind last_voice, since we're just dumping */
544                         jb->info.last_voice_ts -= jb->info.last_voice_ms;
545                         jb->info.frames_out++;
546                         decrement_losspct(jb);
547                         jb->info.frames_late++;
548                         jb->info.frames_lost--;
549                         jb_dbg("l");
550                         /*jb_warn("\nlate: wanted=%ld, this=%ld, next=%ld\n", jb->info.last_voice_ts - jb->info.current, frame->ts, queue_next(jb));
551                         jb_warninfo(jb); */
552                         return JB_DROP;
553                 }
554
555                 /* keep track of frame sizes, to allow for variable sized-frames */
556                 if (frame && frame->ms > 0) {
557                         jb->info.last_voice_ms = frame->ms;
558                 }
559
560                 /* we want to shrink; shrink at 1 frame / 500ms */
561                 if (diff < -2 * jb->info.last_voice_ms && 
562                 ((!frame && jb->info.last_adjustment + 80 < now) || 
563                         (jb->info.last_adjustment + 500 < now))) {
564
565                         /* don't increment last_ts ?? */
566                         jb->info.last_voice_ts -= jb->info.last_voice_ms;
567                         jb->info.current -= jb->info.last_voice_ms;
568                         jb->info.last_adjustment = now;
569
570                         if (frame) {
571                                 *frameout = *frame;
572                                 jb->info.frames_out++;
573                                 decrement_losspct(jb);
574                                 jb->info.frames_dropped++;
575                                 jb_dbg("s");
576                                 return JB_DROP;
577                         } else {
578                                 increment_losspct(jb);
579                                 jb_dbg("S");
580                                 return JB_NOFRAME;
581                         }
582                 }
583
584                 /* lost frame */
585                 if (!frame) {
586                         /* this is a bit of a hack for now, but if we're close to
587                          * target, and we find a missing frame, it makes sense to
588                          * grow, because the frame might just be a bit late;
589                          * otherwise, we presently get into a pattern where we return
590                          * INTERP for the lost frame, then it shows up next, and we
591                          * throw it away because it's late */
592                         /* I've recently only been able to replicate this using
593                          * iaxclient talking to app_echo on asterisk.  In this case,
594                          * my outgoing packets go through asterisk's (old)
595                          * jitterbuffer, and then might get an unusual increasing delay 
596                          * there if it decides to grow?? */
597                         /* Update: that might have been a different bug, that has been fixed..
598                          * But, this still seemed like a good idea, except that it ended up making a single actual
599                          * lost frame get interpolated two or more times, when there was "room" to grow, so it might
600                          * be a bit of a bad idea overall */
601                         /*if (diff > -1 * jb->info.last_voice_ms) { 
602                                 jb->info.current += jb->info.last_voice_ms;
603                                 jb->info.last_adjustment = now;
604                                 jb_warn("g");
605                                 return JB_INTERP;
606                         } */
607                         jb->info.frames_lost++;
608                         increment_losspct(jb);
609                         jb_dbg("L");
610                         return JB_INTERP;
611                 }
612
613                 /* normal case; return the frame, increment stuff */
614                 *frameout = *frame;
615                 jb->info.frames_out++;
616                 decrement_losspct(jb);
617                 jb_dbg("v");
618                 return JB_OK;
619         } else {     
620                 /* TODO: after we get the non-silent case down, we'll make the
621                  * silent case -- basically, we'll just grow and shrink faster
622                  * here, plus handle last_voice_ts a bit differently */
623       
624                 /* to disable silent special case altogether, just uncomment this: */
625                 /* jb->info.silence = 0; */
626
627                 frame = queue_get(jb, now - jb->info.current);
628                 if (!frame) {
629                         return JB_NOFRAME;
630                 }
631                 if (frame && frame->type == JB_TYPE_VOICE) {
632                         /* try setting current to target right away here */
633                         jb->info.current = jb->info.target;
634                         jb->info.silence = 0;
635                         jb->info.last_voice_ts = frame->ts + jb->info.current + frame->ms;
636                         jb->info.last_voice_ms = frame->ms;
637                         *frameout = *frame;
638                         jb_dbg("V");
639                         return JB_OK;
640                 }
641                 /* normal case; in silent mode, got a non-voice frame */
642                 *frameout = *frame;
643                 return JB_OK;
644         }
645 }
646
647 long jb_next(jitterbuf *jb) 
648 {
649         if (jb->info.silence) {
650                 long next = queue_next(jb);
651                 if (next > 0) { 
652                         history_get(jb);
653                         return next + jb->info.target;
654                 }
655                 else 
656                         return JB_LONGMAX;
657         } else {
658                 return jb->info.last_voice_ts + jb->info.last_voice_ms;
659         }
660 }
661
662 int jb_get(jitterbuf *jb, jb_frame *frameout, long now) 
663 {
664         int ret = _jb_get(jb,frameout,now);
665 #if 0
666         static int lastts=0;
667         int thists = ((ret == JB_OK) || (ret == JB_DROP)) ? frameout->ts : 0;
668         jb_warn("jb_get(%x,%x,%ld) = %d (%d)\n", jb, frameout, now, ret, thists);
669         if (thists && thists < lastts) jb_warn("XXXX timestamp roll-back!!!\n");
670         lastts = thists;
671 #endif
672         if(ret == JB_INTERP) 
673                 frameout->ms = jb->info.last_voice_ms;
674         
675         return ret;
676 }
677
678 int jb_getall(jitterbuf *jb, jb_frame *frameout) 
679 {
680         jb_frame *frame;
681         frame = queue_getall(jb);
682
683         if (!frame) {
684                 return JB_NOFRAME;
685         }
686
687         *frameout = *frame;
688         return JB_OK;
689 }
690
691
692 int jb_getinfo(jitterbuf *jb, jb_info *stats) 
693 {
694
695         history_get(jb);
696
697         *stats = jb->info;
698
699         return JB_OK;
700 }
701
702 int jb_setinfo(jitterbuf *jb, jb_info *settings) 
703 {
704         /* take selected settings from the struct */
705
706         jb->info.max_jitterbuf = settings->max_jitterbuf;
707
708         return JB_OK;
709 }
710
711