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;
54 void jb_reset(jitterbuf *jb)
56 memset(jb,0,sizeof(jitterbuf));
58 /* initialize length */
59 jb->info.current = jb->info.target = 0;
68 jb = malloc(sizeof(jitterbuf));
74 jb_dbg2("jb_new() = %x\n", jb);
78 void jb_destroy(jitterbuf *jb)
81 jb_dbg2("jb_destroy(%x)\n", jb);
83 /* free all the frames on the "free list" */
85 while (frame != NULL) {
86 jb_frame *next = frame->next;
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
101 static int longcmp(const void *a, const void *b)
103 return *(long *)a - *(long *)b;
106 static void history_put(jitterbuf *jb, long ts, long now)
108 long delay = now - ts;
111 /* don't add special/negative times to history */
115 kicked = jb->history[jb->hist_ptr & JB_HISTORY_SZ];
117 jb->history[(jb->hist_ptr++) % JB_HISTORY_SZ] = delay;
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)
127 /* don't do this until we've filled history
128 * (reduces some edge cases below) */
129 if (jb->hist_ptr < JB_HISTORY_SZ)
132 /* if the new delay would go into min */
133 if (delay < jb->hist_minbuf[JB_HISTORY_MAXBUF_SZ-1])
137 if (delay > jb->hist_maxbuf[JB_HISTORY_MAXBUF_SZ-1])
140 /* or the kicked delay would be in min */
141 if (kicked <= jb->hist_minbuf[JB_HISTORY_MAXBUF_SZ-1])
144 if (kicked >= jb->hist_maxbuf[JB_HISTORY_MAXBUF_SZ-1])
147 /* if we got here, we don't need to invalidate, 'cause this delay didn't
150 /* end optimization */
154 jb->hist_maxbuf_valid = 0;
158 static void history_calc_maxbuf(jitterbuf *jb)
162 if (jb->hist_ptr == 0)
166 /* initialize maxbuf/minbuf to the latest value */
167 for (i=0;i<JB_HISTORY_MAXBUF_SZ;i++) {
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];
172 jb->hist_maxbuf[i] = JB_LONGMIN;
173 jb->hist_minbuf[i] = JB_LONGMAX;
176 /* use insertion sort to populate maxbuf */
177 /* we want it to be the top "n" values, in order */
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;
182 for (;i<jb->hist_ptr;i++) {
183 long toins = jb->history[i % JB_HISTORY_SZ];
185 /* if the maxbuf should get this */
186 if (toins > jb->hist_maxbuf[JB_HISTORY_MAXBUF_SZ-1]) {
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]) {
193 memmove(jb->hist_maxbuf+j+1,jb->hist_maxbuf+j, (JB_HISTORY_MAXBUF_SZ-(j+1)) * sizeof(long));
195 jb->hist_maxbuf[j] = toins;
202 /* if the minbuf should get this */
203 if (toins < jb->hist_minbuf[JB_HISTORY_MAXBUF_SZ-1]) {
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]) {
210 memmove(jb->hist_minbuf+j+1,jb->hist_minbuf+j, (JB_HISTORY_MAXBUF_SZ-(j+1)) * sizeof(long));
212 jb->hist_minbuf[j] = toins;
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");
232 jb->hist_maxbuf_valid = 1;
235 static void history_get(jitterbuf *jb)
237 long max, min, jitter;
241 if (!jb->hist_maxbuf_valid)
242 history_calc_maxbuf(jb);
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;
247 /* index is the "n"ths highest/lowest that we'll look for */
248 index = count * JB_HISTORY_DROPPCT / 100;
250 /* sanity checks for index */
251 if (index > (JB_HISTORY_MAXBUF_SZ - 1))
252 index = JB_HISTORY_MAXBUF_SZ - 1;
261 max = jb->hist_maxbuf[index];
262 min = jb->hist_minbuf[index];
266 /* these debug stmts compare the difference between looking at the absolute jitter, and the
267 * values we get by throwing away the outliers */
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]);
274 jb->info.jitter = jitter;
277 static void queue_put(jitterbuf *jb, void *data, int type, long ms, long ts)
284 jb->free = frame->next;
286 frame = malloc(sizeof(jb_frame));
290 jb_err("cannot allocate frame\n");
294 jb->info.frames_cur++;
302 * frames are a circular list, jb-frames points to to the lowest ts,
303 * jb->frames->prev points to the highest ts
306 if (!jb->frames) { /* queue is empty */
310 frame->prev = jb->frames->prev;
312 frame->next->prev = frame;
313 frame->prev->next = frame;
319 /* frame is out of order */
320 if (ts < p->prev->ts) jb->info.frames_ooo++;
322 while (ts < p->prev->ts && p->prev != jb->frames)
326 frame->prev = p->prev;
328 frame->next->prev = frame;
329 frame->prev->next = frame;
333 static long queue_next(jitterbuf *jb)
336 return jb->frames->ts;
341 static long queue_last(jitterbuf *jb)
344 return jb->frames->prev->ts;
349 static jb_frame *_queue_get(jitterbuf *jb, long ts, int all)
357 /*jb_warn("queue_get: ASK %ld FIRST %ld\n", ts, frame->ts); */
359 if (all || ts > frame->ts) {
360 /* remove this frame */
361 frame->prev->next = frame->next;
362 frame->next->prev = frame->prev;
364 if (frame->next == frame)
367 jb->frames = frame->next;
370 /* insert onto "free" single-linked list */
371 frame->next = jb->free;
374 jb->info.frames_cur--;
376 /* we return the frame pointer, even though it's on free list,
377 * but caller must copy data */
384 static jb_frame *queue_get(jitterbuf *jb, long ts)
386 return _queue_get(jb,ts,0);
389 static jb_frame *queue_getall(jitterbuf *jb)
391 return _queue_get(jb,0,1);
395 /* some diagnostics */
396 static void jb_dbginfo(jitterbuf *jb)
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);
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",
414 jb->info.last_voice_ts,
415 queue_last(jb) - queue_next(jb),
416 jb->info.last_voice_ms);
421 static void jb_chkqueue(jitterbuf *jb)
424 jb_frame *p = jb->frames;
431 if (p->next == NULL) {
432 jb_err("Queue is BROKEN at item [%d]", i);
436 } while (p->next != jb->frames);
439 static void jb_dbgqueue(jitterbuf *jb)
442 jb_frame *p = jb->frames;
452 jb_dbg("[%d]=%ld ", i++, p->ts);
454 } while (p->next != jb->frames);
460 int jb_put(jitterbuf *jb, void *data, int type, long ms, long ts, long now)
462 jb_dbg2("jb_put(%x,%x,%ld,%ld,%ld)\n", jb, data, ms, ts, now);
464 jb->info.frames_in++;
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);
472 queue_put(jb,data,type,ms,ts);
478 static int _jb_get(jitterbuf *jb, jb_frame *frameout, long now)
483 /*if ((now - jb_next(jb)) > 2 * jb->info.last_voice_ms) jb_warn("SCHED: %ld", (now - jb_next(jb))); */
484 /* get jitter info */
489 jb->info.target = jb->info.jitter + jb->info.min + 2 * jb->info.last_voice_ms;
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;
497 diff = jb->info.target - jb->info.current;
499 /* jb_warn("diff = %d lms=%d last = %d now = %d\n", diff, */
500 /* jb->info.last_voice_ms, jb->info.last_adjustment, now); */
502 /* move up last_voice_ts; it is now the expected voice ts */
503 jb->info.last_voice_ts += jb->info.last_voice_ms;
505 /* let's work on non-silent case first */
506 if (!jb->info.silence) {
507 /* we want to grow */
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)) ) ) {
514 jb->info.current += jb->info.last_voice_ms;
515 jb->info.last_adjustment = now;
520 frame = queue_get(jb, jb->info.last_voice_ts - jb->info.current);
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;
527 if (frame->type == JB_TYPE_SILENCE)
528 jb->info.silence = 1;
531 jb->info.frames_out++;
537 /* voice frame is late */
538 if (frame && frame->ts + jb->info.current < jb->info.last_voice_ts - jb->info.last_voice_ms ) {
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--;
547 /*jb_warn("\nlate: wanted=%ld, this=%ld, next=%ld\n", jb->info.last_voice_ts - jb->info.current, frame->ts, queue_next(jb));
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;
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))) {
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;
569 jb->info.frames_out++;
570 decrement_losspct(jb);
571 jb->info.frames_dropped++;
575 increment_losspct(jb);
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;
604 jb->info.frames_lost++;
605 increment_losspct(jb);
610 /* normal case; return the frame, increment stuff */
612 jb->info.frames_out++;
613 decrement_losspct(jb);
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 */
621 /* to disable silent special case altogether, just uncomment this: */
622 /* jb->info.silence = 0; */
624 frame = queue_get(jb, now - jb->info.current);
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;
638 /* normal case; in silent mode, got a non-voice frame */
644 long jb_next(jitterbuf *jb)
646 if (jb->info.silence) {
647 long next = queue_next(jb);
650 return next + jb->info.target;
655 return jb->info.last_voice_ts + jb->info.last_voice_ms;
659 int jb_get(jitterbuf *jb, jb_frame *frameout, long now)
661 int ret = _jb_get(jb,frameout,now);
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");
670 frameout->ms = jb->info.last_voice_ms;
675 int jb_getall(jitterbuf *jb, jb_frame *frameout)
678 frame = queue_getall(jb);
689 int jb_getinfo(jitterbuf *jb, jb_info *stats)
699 int jb_setinfo(jitterbuf *jb, jb_info *settings)
701 /* take selected settings from the struct */
703 jb->info.max_jitterbuf = settings->max_jitterbuf;