Add PLC and jitter buffer and iax2 meta trunk with timestamps (bug #2532, #3400)

git-svn-id: http://svn.digium.com/svn/asterisk/trunk@5192 f38db490-d61c-443f-a65b-d21fe96a405b

1 files changed, 698 insertions, 0 deletions

diff --git a/jitterbuf.c b/jitterbuf.c
new file mode 100755
index 000000000..1a315b5f1
--- /dev/null
+++ b/jitterbuf.c
@@ -0,0 +1,698 @@
+/*
+ * jitterbuf: an application-independent jitterbuffer
+ *
+ * Copyrights:
+ * Copyright (C) 2004-2005, Horizon Wimba, Inc.
+ *
+ * Contributors:
+ * Steve Kann <stevek@stevek.com>
+ *
+ * This program is free software, distributed under the terms of
+ * the GNU Lesser (Library) General Public License
+ *
+ * Copyright on this file is disclaimed to Digium for inclusion in Asterisk
+ */
+
+#include "jitterbuf.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+/* define these here, just for ancient compiler systems */
+#define JB_LONGMAX 2147483647L
+#define JB_LONGMIN (-JB_LONGMAX - 1L)
+
+#define jb_warn(...) (warnf ? warnf(__VA_ARGS__) : (void)0)
+#define jb_err(...) (errf ? errf(__VA_ARGS__) : (void)0)
+#define jb_dbg(...) (dbgf ? dbgf(__VA_ARGS__) : (void)0)
+
+#ifdef DEEP_DEBUG
+#define jb_dbg2(...) (dbgf ? dbgf(__VA_ARGS__) : (void)0)
+#else
+#define jb_dbg2(...) ((void)0)
+#endif
+
+static jb_output_function_t warnf, errf, dbgf;
+
+void jb_setoutput(jb_output_function_t warn, jb_output_function_t err, jb_output_function_t dbg) 
+{
+    warnf = warn;
+    errf = err;
+    dbgf = dbg;
+}
+
+static void increment_losspct(jitterbuf *jb) 
+{
+    jb->info.losspct = (100000 + 499 * jb->info.losspct)/500;    
+}
+
+static void decrement_losspct(jitterbuf *jb) 
+{
+    jb->info.losspct = (499 * jb->info.losspct)/500;    
+}
+
+
+static void jb_dbginfo(jitterbuf *jb);
+
+
+void jb_reset(jitterbuf *jb) 
+{
+    memset(jb,0,sizeof(jitterbuf));
+
+    /* initialize length */
+    jb->info.current = jb->info.target = 0; 
+    jb->info.silence = 1; 
+}
+
+jitterbuf * jb_new() 
+{
+    jitterbuf *jb;
+
+
+    jb = malloc(sizeof(jitterbuf));
+    if(!jb) return NULL;
+
+    jb_reset(jb);
+
+    jb_dbg2("jb_new() = %x\n", jb);
+    return jb;
+}
+
+void jb_destroy(jitterbuf *jb) 
+{
+    jb_frame *frame; 
+    jb_dbg2("jb_destroy(%x)\n", jb);
+
+    /* free all the frames on the "free list" */
+    frame = jb->free;
+    while(frame != NULL) {
+      jb_frame *next = frame->next;
+      free(frame);
+      frame = next;
+    }
+
+    /* free ourselves! */ 
+    free(jb);
+}
+
+
+
+/* simple history manipulation */
+/* maybe later we can make the history buckets variable size, or something? */
+/* drop parameter determines whether we will drop outliers to minimize
+ * delay */
+static int longcmp(const void *a, const void *b) 
+{
+    return *(long *)a - *(long *)b;
+}
+
+static void history_put(jitterbuf *jb, long ts, long now) 
+{
+    long delay = now - ts;
+    long kicked;
+
+    /* don't add special/negative times to history */
+    if(ts <= 0) return;
+
+    kicked = jb->history[jb->hist_ptr & JB_HISTORY_SZ];
+
+    jb->history[(jb->hist_ptr++) % JB_HISTORY_SZ] = delay;
+
+    /* optimization; the max/min buffers don't need to be recalculated, if this packet's
+     * entry doesn't change them.  This happens if this packet is not involved, _and_ any packet
+     * that got kicked out of the history is also not involved 
+     * We do a number of comparisons, but it's probably still worthwhile, because it will usually
+     * succeed, and should be a lot faster than going through all 500 packets in history */
+    if(!jb->hist_maxbuf_valid)
+      return;
+
+    /* don't do this until we've filled history 
+     * (reduces some edge cases below) */
+    if(jb->hist_ptr < JB_HISTORY_SZ)
+      goto invalidate;
+
+    /* if the new delay would go into min */
+    if(delay < jb->hist_minbuf[JB_HISTORY_MAXBUF_SZ-1])
+      goto invalidate;
+    
+    /* or max.. */
+    if(delay > jb->hist_maxbuf[JB_HISTORY_MAXBUF_SZ-1])
+      goto invalidate;
+
+    /* or the kicked delay would be in min */
+    if(kicked <= jb->hist_minbuf[JB_HISTORY_MAXBUF_SZ-1]) 
+      goto invalidate;
+
+    if(kicked >= jb->hist_maxbuf[JB_HISTORY_MAXBUF_SZ-1]) 
+      goto invalidate;
+
+    /* if we got here, we don't need to invalidate, 'cause this delay didn't 
+     * affect things */
+    return;
+    /* end optimization */
+
+
+invalidate:
+    jb->hist_maxbuf_valid = 0;
+    return;
+}
+
+static void history_calc_maxbuf(jitterbuf *jb) 
+{
+    int i,j;
+
+    if(jb->hist_ptr == 0) return;
+
+
+    /* initialize maxbuf/minbuf to the latest value */
+    for(i=0;i<JB_HISTORY_MAXBUF_SZ;i++) {
+/*
+ * jb->hist_maxbuf[i] = jb->history[(jb->hist_ptr-1) % JB_HISTORY_SZ];
+ * jb->hist_minbuf[i] = jb->history[(jb->hist_ptr-1) % JB_HISTORY_SZ];
+ */
+      jb->hist_maxbuf[i] = JB_LONGMIN;
+      jb->hist_minbuf[i] = JB_LONGMAX;
+    }
+
+    /* use insertion sort to populate maxbuf */
+    /* we want it to be the top "n" values, in order */
+
+    /* start at the beginning, or JB_HISTORY_SZ frames ago */
+    i = (jb->hist_ptr > JB_HISTORY_SZ) ? (jb->hist_ptr - JB_HISTORY_SZ) : 0; 
+
+    for(;i<jb->hist_ptr;i++) {
+	long toins = jb->history[i % JB_HISTORY_SZ];
+
+	/* if the maxbuf should get this */
+	if(toins > jb->hist_maxbuf[JB_HISTORY_MAXBUF_SZ-1])  {
+
+	    /* insertion-sort it into the maxbuf */
+	    for(j=0;j<JB_HISTORY_MAXBUF_SZ;j++) {
+		/* found where it fits */
+		if(toins > jb->hist_maxbuf[j]) {
+		    /* move over */
+		    memmove(jb->hist_maxbuf+j+1,jb->hist_maxbuf+j, (JB_HISTORY_MAXBUF_SZ-(j+1)) * sizeof(long));
+		    /* insert */
+		    jb->hist_maxbuf[j] = toins;
+
+		    break;
+		}
+	    }
+	}
+
+	/* if the minbuf should get this */
+	if(toins < jb->hist_minbuf[JB_HISTORY_MAXBUF_SZ-1])  {
+
+	    /* insertion-sort it into the maxbuf */
+	    for(j=0;j<JB_HISTORY_MAXBUF_SZ;j++) {
+		/* found where it fits */
+		if(toins < jb->hist_minbuf[j]) {
+		    /* move over */
+		    memmove(jb->hist_minbuf+j+1,jb->hist_minbuf+j, (JB_HISTORY_MAXBUF_SZ-(j+1)) * sizeof(long));
+		    /* insert */
+		    jb->hist_minbuf[j] = toins;
+
+		    break;
+		}
+	    }
+	}
+
+	if(0) { 
+	  int k;
+	  fprintf(stderr, "toins = %ld\n", toins);
+	  fprintf(stderr, "maxbuf =");
+	  for(k=0;k<JB_HISTORY_MAXBUF_SZ;k++) 
+	      fprintf(stderr, "%ld ", jb->hist_maxbuf[k]);
+	  fprintf(stderr, "\nminbuf =");
+	  for(k=0;k<JB_HISTORY_MAXBUF_SZ;k++) 
+	      fprintf(stderr, "%ld ", jb->hist_minbuf[k]);
+	  fprintf(stderr, "\n");
+	}
+    }
+
+    jb->hist_maxbuf_valid = 1;
+}
+
+static void history_get(jitterbuf *jb) 
+{
+    long max, min, jitter;
+    int index;
+    int count;
+
+    if(!jb->hist_maxbuf_valid) 
+      history_calc_maxbuf(jb);
+
+    /* count is how many items in history we're examining */
+    count = (jb->hist_ptr < JB_HISTORY_SZ) ? jb->hist_ptr : JB_HISTORY_SZ;
+
+    /* index is the "n"ths highest/lowest that we'll look for */
+    index = count * JB_HISTORY_DROPPCT / 100;
+
+    /* sanity checks for index */
+    if(index > (JB_HISTORY_MAXBUF_SZ - 1)) index = JB_HISTORY_MAXBUF_SZ - 1;
+
+
+    if(index < 0) {
+      jb->info.min = 0;
+      jb->info.jitter = 0;
+      return;
+    }
+
+    max = jb->hist_maxbuf[index];
+    min = jb->hist_minbuf[index];
+
+    jitter = max - min;
+
+    /* these debug stmts compare the difference between looking at the absolute jitter, and the
+     * values we get by throwing away the outliers */
+    /*
+    fprintf(stderr, "[%d] min=%d, max=%d, jitter=%d\n", index, min, max, jitter);
+    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]);
+    */
+
+    jb->info.min = min;
+    jb->info.jitter = jitter;
+}
+
+static void queue_put(jitterbuf *jb, void *data, int type, long ms, long ts) 
+{
+    jb_frame *frame;
+    jb_frame *p;
+
+    frame = jb->free;
+    if(frame) {
+	jb->free = frame->next;
+    } else {
+	frame = malloc(sizeof(jb_frame));
+    }
+
+    if(!frame) {
+	jb_err("cannot allocate frame\n");
+	return;
+    }
+
+    jb->info.frames_cur++;
+
+    frame->data = data;
+    frame->ts = ts;
+    frame->ms = ms;
+    frame->type = type;
+
+    /* 
+     * frames are a circular list, jb-frames points to to the lowest ts, 
+     * jb->frames->prev points to the highest ts
+     */
+
+    if(!jb->frames) {  /* queue is empty */
+	jb->frames = frame;
+	frame->next = frame;
+	frame->prev = frame;
+    } else if(ts < jb->frames->ts) { 
+	frame->next = jb->frames;
+	frame->prev = jb->frames->prev;
+
+	frame->next->prev = frame;
+	frame->prev->next = frame;
+
+	jb->frames = frame;
+    } else { 
+	p = jb->frames;
+
+	/* frame is out of order */
+	if(ts < p->prev->ts) jb->info.frames_ooo++;
+
+	while(ts < p->prev->ts && p->prev != jb->frames) 
+	    p = p->prev;
+
+	frame->next = p;
+	frame->prev = p->prev;
+
+	frame->next->prev = frame;
+	frame->prev->next = frame;
+    }
+}
+
+static long queue_next(jitterbuf *jb) 
+{
+    if(jb->frames) return jb->frames->ts;
+    else return -1;
+}
+
+static long queue_last(jitterbuf *jb) 
+{
+    if(jb->frames) return jb->frames->prev->ts;
+    else return -1;
+}
+
+static jb_frame *_queue_get(jitterbuf *jb, long ts, int all) 
+{
+    jb_frame *frame;
+    frame = jb->frames;
+
+    if(!frame)
+	return NULL;
+
+    /*jb_warn("queue_get: ASK %ld FIRST %ld\n", ts, frame->ts); */
+
+    if(all || ts > frame->ts) {
+	/* remove this frame */
+	frame->prev->next = frame->next;
+	frame->next->prev = frame->prev;
+
+	if(frame->next == frame)
+	  jb->frames = NULL;
+	else
+	  jb->frames = frame->next;
+
+
+	/* insert onto "free" single-linked list */
+	frame->next = jb->free;
+	jb->free = frame;
+
+	jb->info.frames_cur--;
+
+	/* we return the frame pointer, even though it's on free list, 
+	 * but caller must copy data */
+	return frame;
+    } 
+
+    return NULL;
+}
+
+static jb_frame *queue_get(jitterbuf *jb, long ts) 
+{
+    return _queue_get(jb,ts,0);
+}
+
+static jb_frame *queue_getall(jitterbuf *jb) 
+{
+    return _queue_get(jb,0,1);
+}
+
+/* some diagnostics */
+static void jb_dbginfo(jitterbuf *jb) 
+{
+    if(dbgf == NULL) return;
+
+    jb_dbg("\njb info: fin=%ld fout=%ld flate=%ld flost=%ld fdrop=%ld fcur=%ld\n",
+	    jb->info.frames_in, jb->info.frames_out, jb->info.frames_late, jb->info.frames_lost, jb->info.frames_dropped, jb->info.frames_cur);
+	
+    jb_dbg("	jitter=%ld current=%ld target=%ld min=%ld sil=%d len=%d len/fcur=%ld\n",
+	    jb->info.jitter, jb->info.current, jb->info.target, jb->info.min, jb->info.silence, jb->info.current - jb->info.min, 
+	    jb->info.frames_cur ? (jb->info.current - jb->info.min)/jb->info.frames_cur : -8);
+    if(jb->info.frames_in > 0) 
+	jb_dbg("jb info: Loss PCT = %ld%%, Late PCT = %ld%%\n",
+	    jb->info.frames_lost * 100/(jb->info.frames_in + jb->info.frames_lost), 
+	    jb->info.frames_late * 100/jb->info.frames_in);
+	jb_dbg("jb info: queue %d -> %d.  last_ts %d (queue len: %d) last_ms %d\n",
+	    queue_next(jb), 
+	    queue_last(jb),
+	    jb->info.last_voice_ts, 
+	    queue_last(jb) - queue_next(jb),
+	    jb->info.last_voice_ms);
+}
+
+#ifdef DEEP_DEBUG
+static void jb_chkqueue(jitterbuf *jb) 
+{
+    int i=0;
+    jb_frame *p = jb->frames;
+
+    if(!p) {
+      return;
+    }
+
+    do {
+	if(p->next == NULL)  {
+	  jb_err("Queue is BROKEN at item [%d]", i);	
+	}
+	i++;
+	p=p->next;
+    } while (p->next != jb->frames);
+}
+
+static void jb_dbgqueue(jitterbuf *jb) 
+{
+    int i=0;
+    jb_frame *p = jb->frames;
+
+    jb_dbg("queue: ");
+
+    if(!p) {
+      jb_dbg("EMPTY\n");
+      return;
+    }
+
+    do {
+	jb_dbg("[%d]=%ld ", i++, p->ts);
+	p=p->next;
+    } while (p->next != jb->frames);
+
+    jb_dbg("\n");
+}
+#endif
+
+int jb_put(jitterbuf *jb, void *data, int type, long ms, long ts, long now) 
+{
+    jb_dbg2("jb_put(%x,%x,%ld,%ld,%ld)\n", jb, data, ms, ts, now);
+
+    jb->info.frames_in++;
+
+    if(type == JB_TYPE_VOICE) {
+      /* presently, I'm only adding VOICE frames to history and drift calculations; mostly because with the
+       * IAX integrations, I'm sending retransmitted control frames with their awkward timestamps through */
+      history_put(jb,ts,now);
+    }
+
+    queue_put(jb,data,type,ms,ts);
+
+    return JB_OK;
+}
+
+
+static int _jb_get(jitterbuf *jb, jb_frame *frameout, long now) 
+{
+    jb_frame *frame;
+    long diff;
+
+    /*if((now - jb_next(jb)) > 2 * jb->info.last_voice_ms) jb_warn("SCHED: %ld", (now - jb_next(jb))); */
+    /* get jitter info */
+    history_get(jb);
+
+
+    /* target */
+    jb->info.target = jb->info.jitter + jb->info.min + 2 * jb->info.last_voice_ms; 
+
+    /* if a hard clamp was requested, use it */
+    if((jb->info.max_jitterbuf) && ((jb->info.target - jb->info.min) > jb->info.max_jitterbuf)) {
+	jb_dbg("clamping target from %d to %d\n", (jb->info.target - jb->info.min), jb->info.max_jitterbuf);
+	jb->info.target = jb->info.min + jb->info.max_jitterbuf;
+    }
+
+    diff = jb->info.target - jb->info.current;
+
+    /*    jb_warn("diff = %d lms=%d last = %d now = %d\n", diff,  */
+    /*	jb->info.last_voice_ms, jb->info.last_adjustment, now); */
+
+    /* move up last_voice_ts; it is now the expected voice ts */
+    jb->info.last_voice_ts += jb->info.last_voice_ms;
+
+    /* let's work on non-silent case first */
+    if(!jb->info.silence) { 
+	  /* we want to grow */
+      if( (diff > 0) && 
+	  /* we haven't grown in 2 frames' length */
+	  (((jb->info.last_adjustment + 2 * jb->info.last_voice_ms ) < now) || 
+	   /* we need to grow more than the "length" we have left */
+	   (diff > queue_last(jb)  - queue_next(jb)) ) ) {
+	      jb->info.current += jb->info.last_voice_ms;
+	      jb->info.last_adjustment = now;
+	      jb_dbg("G");
+	      return JB_INTERP;
+      }
+
+      frame = queue_get(jb, jb->info.last_voice_ts - jb->info.current);
+
+      /* not a voice frame; just return it. */
+      if(frame && frame->type != JB_TYPE_VOICE) {
+	/* rewind last_voice_ts, since this isn't voice */
+	jb->info.last_voice_ts -= jb->info.last_voice_ms;
+
+	if(frame->type == JB_TYPE_SILENCE) 
+	  jb->info.silence = 1;
+
+	*frameout = *frame;
+	jb->info.frames_out++;
+	jb_dbg("o");
+	return JB_OK;
+      }
+
+
+      /* voice frame is late */
+      if(frame && frame->ts + jb->info.current < jb->info.last_voice_ts - jb->info.last_voice_ms ) {
+	*frameout = *frame;
+	/* rewind last_voice, since we're just dumping */
+	jb->info.last_voice_ts -= jb->info.last_voice_ms;
+	jb->info.frames_out++;
+	decrement_losspct(jb);
+	jb->info.frames_late++;
+	jb->info.frames_lost--;
+	jb_dbg("l");
+	/*jb_warn("\nlate: wanted=%ld, this=%ld, next=%ld\n", jb->info.last_voice_ts - jb->info.current, frame->ts, queue_next(jb));
+	jb_warninfo(jb); */
+	return JB_DROP;
+      }
+
+      /* keep track of frame sizes, to allow for variable sized-frames */
+      if(frame && frame->ms > 0) {
+	jb->info.last_voice_ms = frame->ms;
+      }
+
+      /* we want to shrink; shrink at 1 frame / 500ms */
+      if(diff < -2 * jb->info.last_voice_ms && 
+		((!frame && jb->info.last_adjustment + 80 < now) || 
+		 (jb->info.last_adjustment + 500 < now))) {
+
+	/* don't increment last_ts ?? */
+	jb->info.last_voice_ts -= jb->info.last_voice_ms;
+	jb->info.current -= jb->info.last_voice_ms;
+	jb->info.last_adjustment = now;
+
+	if(frame)  {
+	  *frameout = *frame;
+	  jb->info.frames_out++;
+	  decrement_losspct(jb);
+	  jb->info.frames_dropped++;
+	  jb_dbg("s");
+	  return JB_DROP;
+	} else {
+	  increment_losspct(jb);
+	  jb_dbg("S");
+	  return JB_NOFRAME;
+	}
+      }
+
+      /* lost frame */
+      if(!frame) {
+	  /* this is a bit of a hack for now, but if we're close to
+	   * target, and we find a missing frame, it makes sense to
+	   * grow, because the frame might just be a bit late;
+	   * otherwise, we presently get into a pattern where we return
+	   * INTERP for the lost frame, then it shows up next, and we
+	   * throw it away because it's late */
+	  /* I've recently only been able to replicate this using
+	   * iaxclient talking to app_echo on asterisk.  In this case,
+	   * my outgoing packets go through asterisk's (old)
+	   * jitterbuffer, and then might get an unusual increasing delay 
+	   * there if it decides to grow?? */
+	  /* Update: that might have been a different bug, that has been fixed..
+	   * But, this still seemed like a good idea, except that it ended up making a single actual
+	   * lost frame get interpolated two or more times, when there was "room" to grow, so it might
+	   * be a bit of a bad idea overall */
+	  /*if(diff > -1 * jb->info.last_voice_ms) { 
+	      jb->info.current += jb->info.last_voice_ms;
+	      jb->info.last_adjustment = now;
+	      jb_warn("g");
+	      return JB_INTERP;
+	  } */
+	  jb->info.frames_lost++;
+	  increment_losspct(jb);
+	  jb_dbg("L");
+	  return JB_INTERP;
+      }
+
+      /* normal case; return the frame, increment stuff */
+      *frameout = *frame;
+      jb->info.frames_out++;
+      decrement_losspct(jb);
+      jb_dbg("v");
+      return JB_OK;
+  } else {     
+      /* TODO: after we get the non-silent case down, we'll make the
+       * silent case -- basically, we'll just grow and shrink faster
+       * here, plus handle last_voice_ts a bit differently */
+      
+      /* to disable silent special case altogether, just uncomment this: */
+       /* jb->info.silence = 0; */
+
+       frame = queue_get(jb, now - jb->info.current);
+       if(!frame) {
+	  return JB_NOFRAME;
+       }
+       if(frame && frame->type == JB_TYPE_VOICE) {
+	  /* try setting current to target right away here */
+	  jb->info.current = jb->info.target;
+	  jb->info.silence = 0;
+	  jb->info.last_voice_ts = frame->ts + jb->info.current + frame->ms;
+	  jb->info.last_voice_ms = frame->ms;
+	  *frameout = *frame;
+	  jb_dbg("V");
+	  return JB_OK;
+       }
+       /* normal case; in silent mode, got a non-voice frame */
+       *frameout = *frame;
+       return JB_OK;
+  }
+}
+
+long jb_next(jitterbuf *jb) 
+{
+    if(jb->info.silence) {
+      long next = queue_next(jb);
+      if(next > 0) { 
+	history_get(jb);
+	return next + jb->info.target;
+      }
+      else return JB_LONGMAX;
+    } else {
+      return jb->info.last_voice_ts + jb->info.last_voice_ms;
+    }
+}
+
+int jb_get(jitterbuf *jb, jb_frame *frameout, long now) 
+{
+    int ret = _jb_get(jb,frameout,now);
+#if 0
+    static int lastts=0;
+    int thists = ((ret == JB_OK) || (ret == JB_DROP)) ? frameout->ts : 0;
+    jb_warn("jb_get(%x,%x,%ld) = %d (%d)\n", jb, frameout, now, ret, thists);
+    if(thists && thists < lastts) jb_warn("XXXX timestamp roll-back!!!\n");
+    lastts = thists;
+#endif
+    return ret;
+}
+
+int jb_getall(jitterbuf *jb, jb_frame *frameout) 
+{
+    jb_frame *frame;
+    frame = queue_getall(jb);
+
+    if(!frame) {
+      return JB_NOFRAME;
+    }
+
+    *frameout = *frame;
+    return JB_OK;
+}
+
+
+int jb_getinfo(jitterbuf *jb, jb_info *stats) 
+{
+
+    history_get(jb);
+
+    *stats = jb->info;
+
+  return JB_OK;
+}
+
+int jb_setinfo(jitterbuf *jb, jb_info *settings) 
+{
+  /* take selected settings from the struct */
+
+  jb->info.max_jitterbuf = settings->max_jitterbuf;
+
+  return JB_OK;
+}
+
+