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