2 * jitterbuf: an application-independent jitterbuffer
5 * Copyright (C) 2004-2005, Horizon Wimba, Inc.
8 * Steve Kann <stevek@stevek.com>
10 * This program is free software, distributed under the terms of
11 * the GNU Lesser (Library) General Public License
13 * Copyright on this file is disclaimed to Digium for inclusion in Asterisk
16 #include "jitterbuf.h"
21 /* define these here, just for ancient compiler systems */
22 #define JB_LONGMAX 2147483647L
23 #define JB_LONGMIN (-JB_LONGMAX - 1L)
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)
30 #define jb_dbg2(...) (dbgf ? dbgf(__VA_ARGS__) : (void)0)
32 #define jb_dbg2(...) ((void)0)
35 static jb_output_function_t warnf, errf, dbgf;
37 void jb_setoutput(jb_output_function_t warn, jb_output_function_t err, jb_output_function_t dbg)
44 static void increment_losspct(jitterbuf *jb)
46 jb->info.losspct = (100000 + 499 * jb->info.losspct)/500;
49 static void decrement_losspct(jitterbuf *jb)
51 jb->info.losspct = (499 * jb->info.losspct)/500;
55 static void jb_dbginfo(jitterbuf *jb);
58 void jb_reset(jitterbuf *jb)
60 memset(jb,0,sizeof(jitterbuf));
62 /* initialize length */
63 jb->info.current = jb->info.target = 0;
72 jb = malloc(sizeof(jitterbuf));
78 jb_dbg2("jb_new() = %x\n", jb);
82 void jb_destroy(jitterbuf *jb)
85 jb_dbg2("jb_destroy(%x)\n", jb);
87 /* free all the frames on the "free list" */
89 while (frame != NULL) {
90 jb_frame *next = frame->next;
101 /* simple history manipulation */
102 /* maybe later we can make the history buckets variable size, or something? */
103 /* drop parameter determines whether we will drop outliers to minimize
105 static int longcmp(const void *a, const void *b)
107 return *(long *)a - *(long *)b;
110 static void history_put(jitterbuf *jb, long ts, long now)
112 long delay = now - ts;
115 /* don't add special/negative times to history */
119 kicked = jb->history[jb->hist_ptr & JB_HISTORY_SZ];
121 jb->history[(jb->hist_ptr++) % JB_HISTORY_SZ] = delay;
123 /* optimization; the max/min buffers don't need to be recalculated, if this packet's
124 * entry doesn't change them. This happens if this packet is not involved, _and_ any packet
125 * that got kicked out of the history is also not involved
126 * We do a number of comparisons, but it's probably still worthwhile, because it will usually
127 * succeed, and should be a lot faster than going through all 500 packets in history */
128 if (!jb->hist_maxbuf_valid)
131 /* don't do this until we've filled history
132 * (reduces some edge cases below) */
133 if (jb->hist_ptr < JB_HISTORY_SZ)
136 /* if the new delay would go into min */
137 if (delay < jb->hist_minbuf[JB_HISTORY_MAXBUF_SZ-1])
141 if (delay > jb->hist_maxbuf[JB_HISTORY_MAXBUF_SZ-1])
144 /* or the kicked delay would be in min */
145 if (kicked <= jb->hist_minbuf[JB_HISTORY_MAXBUF_SZ-1])
148 if (kicked >= jb->hist_maxbuf[JB_HISTORY_MAXBUF_SZ-1])
151 /* if we got here, we don't need to invalidate, 'cause this delay didn't
154 /* end optimization */
158 jb->hist_maxbuf_valid = 0;
162 static void history_calc_maxbuf(jitterbuf *jb)
166 if (jb->hist_ptr == 0)
170 /* initialize maxbuf/minbuf to the latest value */
171 for (i=0;i<JB_HISTORY_MAXBUF_SZ;i++) {
173 * jb->hist_maxbuf[i] = jb->history[(jb->hist_ptr-1) % JB_HISTORY_SZ];
174 * jb->hist_minbuf[i] = jb->history[(jb->hist_ptr-1) % JB_HISTORY_SZ];
176 jb->hist_maxbuf[i] = JB_LONGMIN;
177 jb->hist_minbuf[i] = JB_LONGMAX;
180 /* use insertion sort to populate maxbuf */
181 /* we want it to be the top "n" values, in order */
183 /* start at the beginning, or JB_HISTORY_SZ frames ago */
184 i = (jb->hist_ptr > JB_HISTORY_SZ) ? (jb->hist_ptr - JB_HISTORY_SZ) : 0;
186 for (;i<jb->hist_ptr;i++) {
187 long toins = jb->history[i % JB_HISTORY_SZ];
189 /* if the maxbuf should get this */
190 if (toins > jb->hist_maxbuf[JB_HISTORY_MAXBUF_SZ-1]) {
192 /* insertion-sort it into the maxbuf */
193 for (j=0;j<JB_HISTORY_MAXBUF_SZ;j++) {
194 /* found where it fits */
195 if (toins > jb->hist_maxbuf[j]) {
197 memmove(jb->hist_maxbuf+j+1,jb->hist_maxbuf+j, (JB_HISTORY_MAXBUF_SZ-(j+1)) * sizeof(long));
199 jb->hist_maxbuf[j] = toins;
206 /* if the minbuf should get this */
207 if (toins < jb->hist_minbuf[JB_HISTORY_MAXBUF_SZ-1]) {
209 /* insertion-sort it into the maxbuf */
210 for (j=0;j<JB_HISTORY_MAXBUF_SZ;j++) {
211 /* found where it fits */
212 if (toins < jb->hist_minbuf[j]) {
214 memmove(jb->hist_minbuf+j+1,jb->hist_minbuf+j, (JB_HISTORY_MAXBUF_SZ-(j+1)) * sizeof(long));
216 jb->hist_minbuf[j] = toins;
225 fprintf(stderr, "toins = %ld\n", toins);
226 fprintf(stderr, "maxbuf =");
227 for (k=0;k<JB_HISTORY_MAXBUF_SZ;k++)
228 fprintf(stderr, "%ld ", jb->hist_maxbuf[k]);
229 fprintf(stderr, "\nminbuf =");
230 for (k=0;k<JB_HISTORY_MAXBUF_SZ;k++)
231 fprintf(stderr, "%ld ", jb->hist_minbuf[k]);
232 fprintf(stderr, "\n");
236 jb->hist_maxbuf_valid = 1;
239 static void history_get(jitterbuf *jb)
241 long max, min, jitter;
245 if (!jb->hist_maxbuf_valid)
246 history_calc_maxbuf(jb);
248 /* count is how many items in history we're examining */
249 count = (jb->hist_ptr < JB_HISTORY_SZ) ? jb->hist_ptr : JB_HISTORY_SZ;
251 /* index is the "n"ths highest/lowest that we'll look for */
252 index = count * JB_HISTORY_DROPPCT / 100;
254 /* sanity checks for index */
255 if (index > (JB_HISTORY_MAXBUF_SZ - 1))
256 index = JB_HISTORY_MAXBUF_SZ - 1;
265 max = jb->hist_maxbuf[index];
266 min = jb->hist_minbuf[index];
270 /* these debug stmts compare the difference between looking at the absolute jitter, and the
271 * values we get by throwing away the outliers */
273 fprintf(stderr, "[%d] min=%d, max=%d, jitter=%d\n", index, min, max, jitter);
274 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]);
278 jb->info.jitter = jitter;
281 static void queue_put(jitterbuf *jb, void *data, int type, long ms, long ts)
288 jb->free = frame->next;
290 frame = malloc(sizeof(jb_frame));
294 jb_err("cannot allocate frame\n");
298 jb->info.frames_cur++;
306 * frames are a circular list, jb-frames points to to the lowest ts,
307 * jb->frames->prev points to the highest ts
310 if (!jb->frames) { /* queue is empty */
314 frame->prev = jb->frames->prev;
316 frame->next->prev = frame;
317 frame->prev->next = frame;
323 /* frame is out of order */
324 if (ts < p->prev->ts) jb->info.frames_ooo++;
326 while (ts < p->prev->ts && p->prev != jb->frames)
330 frame->prev = p->prev;
332 frame->next->prev = frame;
333 frame->prev->next = frame;
337 static long queue_next(jitterbuf *jb)
340 return jb->frames->ts;
345 static long queue_last(jitterbuf *jb)
348 return jb->frames->prev->ts;
353 static jb_frame *_queue_get(jitterbuf *jb, long ts, int all)
361 /*jb_warn("queue_get: ASK %ld FIRST %ld\n", ts, frame->ts); */
363 if (all || ts > frame->ts) {
364 /* remove this frame */
365 frame->prev->next = frame->next;
366 frame->next->prev = frame->prev;
368 if (frame->next == frame)
371 jb->frames = frame->next;
374 /* insert onto "free" single-linked list */
375 frame->next = jb->free;
378 jb->info.frames_cur--;
380 /* we return the frame pointer, even though it's on free list,
381 * but caller must copy data */
388 static jb_frame *queue_get(jitterbuf *jb, long ts)
390 return _queue_get(jb,ts,0);
393 static jb_frame *queue_getall(jitterbuf *jb)
395 return _queue_get(jb,0,1);
398 /* some diagnostics */
399 static void jb_dbginfo(jitterbuf *jb)
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);
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",
417 jb->info.last_voice_ts,
418 queue_last(jb) - queue_next(jb),
419 jb->info.last_voice_ms);
423 static void jb_chkqueue(jitterbuf *jb)
426 jb_frame *p = jb->frames;
433 if (p->next == NULL) {
434 jb_err("Queue is BROKEN at item [%d]", i);
438 } while (p->next != jb->frames);
441 static void jb_dbgqueue(jitterbuf *jb)
444 jb_frame *p = jb->frames;
454 jb_dbg("[%d]=%ld ", i++, p->ts);
456 } while (p->next != jb->frames);
462 int jb_put(jitterbuf *jb, void *data, int type, long ms, long ts, long now)
464 jb_dbg2("jb_put(%x,%x,%ld,%ld,%ld)\n", jb, data, ms, ts, now);
466 jb->info.frames_in++;
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);
474 queue_put(jb,data,type,ms,ts);
480 static int _jb_get(jitterbuf *jb, jb_frame *frameout, long now)
485 /*if ((now - jb_next(jb)) > 2 * jb->info.last_voice_ms) jb_warn("SCHED: %ld", (now - jb_next(jb))); */
486 /* get jitter info */
491 jb->info.target = jb->info.jitter + jb->info.min + 2 * jb->info.last_voice_ms;
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;
499 diff = jb->info.target - jb->info.current;
501 /* jb_warn("diff = %d lms=%d last = %d now = %d\n", diff, */
502 /* jb->info.last_voice_ms, jb->info.last_adjustment, now); */
504 /* move up last_voice_ts; it is now the expected voice ts */
505 jb->info.last_voice_ts += jb->info.last_voice_ms;
507 /* let's work on non-silent case first */
508 if (!jb->info.silence) {
509 /* we want to grow */
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)) ) ) {
516 jb->info.current += jb->info.last_voice_ms;
517 jb->info.last_adjustment = now;
522 frame = queue_get(jb, jb->info.last_voice_ts - jb->info.current);
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;
529 if (frame->type == JB_TYPE_SILENCE)
530 jb->info.silence = 1;
533 jb->info.frames_out++;
539 /* voice frame is late */
540 if (frame && frame->ts + jb->info.current < jb->info.last_voice_ts - jb->info.last_voice_ms ) {
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--;
549 /*jb_warn("\nlate: wanted=%ld, this=%ld, next=%ld\n", jb->info.last_voice_ts - jb->info.current, frame->ts, queue_next(jb));
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;
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))) {
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;
571 jb->info.frames_out++;
572 decrement_losspct(jb);
573 jb->info.frames_dropped++;
577 increment_losspct(jb);
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;
606 jb->info.frames_lost++;
607 increment_losspct(jb);
612 /* normal case; return the frame, increment stuff */
614 jb->info.frames_out++;
615 decrement_losspct(jb);
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 */
623 /* to disable silent special case altogether, just uncomment this: */
624 /* jb->info.silence = 0; */
626 frame = queue_get(jb, now - jb->info.current);
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;
640 /* normal case; in silent mode, got a non-voice frame */
646 long jb_next(jitterbuf *jb)
648 if (jb->info.silence) {
649 long next = queue_next(jb);
652 return next + jb->info.target;
657 return jb->info.last_voice_ts + jb->info.last_voice_ms;
661 int jb_get(jitterbuf *jb, jb_frame *frameout, long now)
663 int ret = _jb_get(jb,frameout,now);
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");
672 frameout->ms = jb->info.last_voice_ms;
677 int jb_getall(jitterbuf *jb, jb_frame *frameout)
680 frame = queue_getall(jb);
691 int jb_getinfo(jitterbuf *jb, jb_info *stats)
701 int jb_setinfo(jitterbuf *jb, jb_info *settings)
703 /* take selected settings from the struct */
705 jb->info.max_jitterbuf = settings->max_jitterbuf;