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