jitterbuf.c

来自网络的iaxclient的协议栈源码

/*
 * jitterbuf: an application-independent jitterbuffer
 *
 * Copyrights:
 * Copyright (C) 2004-2005, Horizon Wimba, Inc.
 *
 * Contributors:
 * Steve Kann <[e-mail]>
 *
 * 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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>

#include "jitterbuf.h"

/* define these here, just for ancient compiler systems */
#define JB_LONGMAX 2147483647L
#define JB_LONGMIN (-JB_LONGMAX - 1L)

/* MS VC can't do __VA_ARGS__ */
#if (defined(WIN32)  ||  defined(_WIN32_WCE))  &&  defined(_MSC_VER)
#define jb_warn if (warnf) warnf
#define jb_err if (errf) errf
#define jb_dbg if (dbgf) dbgf

#ifdef DEEP_DEBUG
  #define jb_dbg2 if (dbgf) dbgf
#else
  #define jb_dbg2 if (0) dbgf
#endif

#else

#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

#endif

static jb_output_function_t warnf, errf, dbgf;

void jb_setoutput(jb_output_function_t err, jb_output_function_t warn, jb_output_function_t dbg)
{
	errf = err;
	warnf = warn;
	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;
}

void jb_reset(jitterbuf *jb)
{
	/* only save settings */
	jb_conf s = jb->info.conf;
	memset(jb, 0, sizeof(*jb));
	jb->info.conf = s;

	/* initialize length, using the configured value */
	jb->info.current = jb->info.target = jb->info.conf.target_extra;
	jb->info.silence_begin_ts = -1;
}

jitterbuf * jb_new()
{
	jitterbuf *jb;

	if (!(jb = (jitterbuf *)malloc(sizeof(*jb))))
		return NULL;

	jb->info.conf.target_extra = JB_TARGET_EXTRA;

	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);
}



#if 0
static int longcmp(const void *a, const void *b)
{
	return *(long *)a - *(long *)b;
}
#endif

/* 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 history_put(jitterbuf *jb, long ts, long now, long ms)
{
	long delay = now - (ts - jb->info.resync_offset);
	long threshold = 2 * jb->info.jitter + jb->info.conf.resync_threshold;
	long kicked;

	/* don't add special/negative times to history */
	if (ts <= 0)
		return 0;

	/* check for drastic change in delay */
	if (jb->info.conf.resync_threshold != -1) {
		if (abs(delay - jb->info.last_delay) > threshold) {
			jb->info.cnt_delay_discont++;
			if (jb->info.cnt_delay_discont > 3) {
				/* resync the jitterbuffer */
				jb->info.cnt_delay_discont = 0;
				jb->hist_ptr = 0;
				jb->hist_maxbuf_valid = 0;

				jb_warn("Resyncing the jb. last_delay %ld, this delay %ld, threshold %ld, new offset %ld\n", jb->info.last_delay, delay, threshold, ts - now);
				jb->info.resync_offset = ts - now;
				jb->info.last_delay = delay = 0; /* after resync, frame is right on time */
			} else {
				return -1;
			}
		} else {
			jb->info.last_delay = delay;
			jb->info.cnt_delay_discont = 0;
		}
	}

	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 0;

	/* 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 0;
	/* end optimization */


invalidate:
	jb->hist_maxbuf_valid = 0;
	return 0;
}

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(jb->hist_maxbuf[0]));
					/* 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(jb->hist_minbuf[0]));
					/* 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;
}

/* returns 1 if frame was inserted into head of queue, 0 otherwise */
static int queue_put(jitterbuf *jb, void *data, const enum jb_frame_type type, long ms, long ts)
{
	jb_frame *frame;
	jb_frame *p;
	int head = 0;
	long resync_ts = ts - jb->info.resync_offset;

	if ((frame = jb->free)) {
		jb->free = frame->next;
	} else if (!(frame = (jb_frame *)malloc(sizeof(*frame)))) {
		jb_err("cannot allocate frame\n");
		return 0;
	}

	jb->info.frames_cur++;

	frame->data = data;
	frame->ts = resync_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;
		head = 1;
	} else if (resync_ts < jb->frames->ts) {
		frame->next = jb->frames;
		frame->prev = jb->frames->prev;

		frame->next->prev = frame;
		frame->prev->next = frame;

		/* frame is out of order */
		jb->info.frames_ooo++;

		jb->frames = frame;
		head = 1;
	} else {
		p = jb->frames;

		/* frame is out of order */
		if (resync_ts < p->prev->ts) jb->info.frames_ooo++;

		while (resync_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;
	}
	return head;
}

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;