translate.c

/*
 * Asterisk -- An open source telephony toolkit.
 *
 * Copyright (C) 1999 - 2006, Digium, Inc.
 *
 * Mark Spencer <markster@digium.com>
 *
 * See http://www.asterisk.org for more information about
 * the Asterisk project. Please do not directly contact
 * any of the maintainers of this project for assistance;
 * the project provides a web site, mailing lists and IRC
 * channels for your use.
 *
 * This program is free software, distributed under the terms of
 * the GNU General Public License Version 2. See the LICENSE file
 * at the top of the source tree.
 */

/*! \file
 *
 * \brief Translate via the use of pseudo channels
 *
 * \author Mark Spencer <markster@digium.com>
 */

/*** MODULEINFO
	<support_level>core</support_level>
 ***/

#include "asterisk.h"

#include <sys/time.h>
#include <sys/resource.h>
#include <math.h>
#include <stdlib.h>

#include "asterisk/lock.h"
#include "asterisk/channel.h"
#include "asterisk/translate.h"
#include "asterisk/module.h"
#include "asterisk/frame.h"
#include "asterisk/sched.h"
#include "asterisk/cli.h"
#include "asterisk/term.h"
#include "asterisk/format.h"
#include "asterisk/linkedlists.h"

/*! \todo
 * TODO: sample frames for each supported input format.
 * We build this on the fly, by taking an SLIN frame and using
 * the existing converter to play with it.
 */

/*! max sample recalc */
#define MAX_RECALC 1000

/*! \brief the list of translators */
static AST_RWLIST_HEAD_STATIC(translators, ast_translator);

struct translator_path {
	struct ast_translator *step;       /*!< Next step translator */
	uint32_t table_cost;               /*!< Complete table cost to destination */
	uint8_t multistep;                 /*!< Multiple conversions required for this translation */
};

/*!
 * \brief a matrix that, for any pair of supported formats,
 * indicates the total cost of translation and the first step.
 * The full path can be reconstricted iterating on the matrix
 * until step->dstfmt == desired_format.
 *
 * Array indexes are 'src' and 'dest', in that order.
 *
 * Note: the lock in the 'translators' list is also used to protect
 * this structure.
 */
static struct translator_path **__matrix;

/*!
 * \brief table for converting index to format values.
 *
 * \note this table is protected by the table_lock.
 */
static unsigned int *__indextable;

/*! protects the __indextable for resizing */
static ast_rwlock_t tablelock;

/* index size starts at this*/
#define INIT_INDEX 32
/* index size grows by this as necessary */
#define GROW_INDEX 16

/*! the current largest index used by the __matrix and __indextable arrays*/
static int cur_max_index;
/*! the largest index that can be used in either the __indextable or __matrix before resize must occur */
static int index_size;

static void matrix_rebuild(int samples);

/*!
 * \internal
 * \brief converts codec id to index value.
 */
static int codec_to_index(unsigned int id)
{
	int x;

	ast_rwlock_rdlock(&tablelock);
	for (x = 0; x < cur_max_index; x++) {
		if (__indextable[x] == id) {
			/* format already exists in index2format table */
			ast_rwlock_unlock(&tablelock);
			return x;
		}
	}
	ast_rwlock_unlock(&tablelock);
	return -1; /* not found */
}

/*!
 * \internal
 * \brief converts codec to index value.
 */
static int codec2index(struct ast_codec *codec)
{
	return codec_to_index(codec->id);
}

/*!
 * \internal
 * \brief converts format to codec index value.
 */
static int format2index(struct ast_format *format)
{
	return codec_to_index(ast_format_get_codec_id(format));
}

/*!
 * \internal
 * \brief add a new codec to the matrix and index table structures.
 *
 * \note it is perfectly safe to call this on codecs already indexed.
 *
 * \retval 0, success
 * \retval -1, matrix and index table need to be resized
 */
static int add_codec2index(struct ast_codec *codec)
{
	if (codec2index(codec) != -1) {
		/* format is already already indexed */
		return 0;
	}

	ast_rwlock_wrlock(&tablelock);
	if (cur_max_index == (index_size)) {
		ast_rwlock_unlock(&tablelock);
		return -1; /* hit max length */
	}
	__indextable[cur_max_index] = codec->id;
	cur_max_index++;
	ast_rwlock_unlock(&tablelock);

	return 0;
}

/*!
 * \internal
 * \brief converts index value back to codec
 */
static struct ast_codec *index2codec(int index)
{
	struct ast_codec *codec;

	if (index >= cur_max_index) {
		return 0;
	}
	ast_rwlock_rdlock(&tablelock);
	codec = ast_codec_get_by_id(__indextable[index]);
	ast_rwlock_unlock(&tablelock);

	return codec;
}

/*!
 * \internal
 * \brief resize both the matrix and index table so they can represent
 * more translators
 *
 * \note _NO_ locks can be held prior to calling this function
 *
 * \retval 0, success
 * \retval -1, failure.  Old matrix and index table can still be used though
 */
static int matrix_resize(int init)
{
	struct translator_path **tmp_matrix = NULL;
	unsigned int *tmp_table = NULL;
	int old_index;
	int x;

	AST_RWLIST_WRLOCK(&translators);
	ast_rwlock_wrlock(&tablelock);

	old_index = index_size;
	if (init) {
		index_size += INIT_INDEX;
	} else {
		index_size += GROW_INDEX;
	}

	/* make new 2d array of translator_path structures */
	if (!(tmp_matrix = ast_calloc(1, sizeof(struct translator_path *) * (index_size)))) {
		goto resize_cleanup;
	}

	for (x = 0; x < index_size; x++) {
		if (!(tmp_matrix[x] = ast_calloc(1, sizeof(struct translator_path) * (index_size)))) {
			goto resize_cleanup;
		}
	}

	/* make new index table */
	if (!(tmp_table = ast_calloc(1, sizeof(unsigned int) * index_size))) {
		goto resize_cleanup;
	}

	/* if everything went well this far, free the old and use the new */
	if (!init) {
		for (x = 0; x < old_index; x++) {
			ast_free(__matrix[x]);
		}
		ast_free(__matrix);

		memcpy(tmp_table, __indextable, sizeof(unsigned int) * old_index);
		ast_free(__indextable);
	}

	/* now copy them over */
	__matrix = tmp_matrix;
	__indextable = tmp_table;

	matrix_rebuild(0);
	ast_rwlock_unlock(&tablelock);
	AST_RWLIST_UNLOCK(&translators);

	return 0;

resize_cleanup:
	ast_rwlock_unlock(&tablelock);
	AST_RWLIST_UNLOCK(&translators);
	if (tmp_matrix) {
		for (x = 0; x < index_size; x++) {
			ast_free(tmp_matrix[x]);
		}
		ast_free(tmp_matrix);
	}
	ast_free(tmp_table);

	return -1;
}

/*!
 * \internal
 * \brief reinitialize the __matrix during matrix rebuild
 *
 * \note must be protected by the translators list lock
 */
static void matrix_clear(void)
{
	int x;
	for (x = 0; x < index_size; x++) {
		memset(__matrix[x], '\0', sizeof(struct translator_path) * (index_size));
	}
}

/*!
 * \internal
 * \brief get a matrix entry
 *
 * \note This function must be protected by the translators list lock
 */
static struct translator_path *matrix_get(unsigned int x, unsigned int y)
{
	return __matrix[x] + y;
}

/*
 * wrappers around the translator routines.
 */

static void destroy(struct ast_trans_pvt *pvt)
{
	struct ast_translator *t = pvt->t;

	if (t->destroy) {
		t->destroy(pvt);
	}
	ao2_cleanup(pvt->f.subclass.format);
	if (pvt->explicit_dst) {
		ao2_ref(pvt->explicit_dst, -1);
		pvt->explicit_dst = NULL;
	}
	ast_free(pvt);
	ast_module_unref(t->module);
}

/*!
 * \brief Allocate the descriptor, required outbuf space,
 * and possibly desc.
 */
static struct ast_trans_pvt *newpvt(struct ast_translator *t, struct ast_format *explicit_dst)
{
	struct ast_trans_pvt *pvt;
	int len;
	char *ofs;

	/*
	 * compute the required size adding private descriptor,
	 * buffer, AST_FRIENDLY_OFFSET.
	 */
	len = sizeof(*pvt) + t->desc_size;
	if (t->buf_size)
		len += AST_FRIENDLY_OFFSET + t->buf_size;
	pvt = ast_calloc(1, len);
	if (!pvt) {
		return NULL;
	}
	pvt->t = t;
	ofs = (char *)(pvt + 1);	/* pointer to data space */
	if (t->desc_size) {		/* first comes the descriptor */
		pvt->pvt = ofs;
		ofs += t->desc_size;
	}
	if (t->buf_size) {/* finally buffer and header */
		pvt->outbuf.c = ofs + AST_FRIENDLY_OFFSET;
	}
	/*
	 * If the format has an attribute module, explicit_dst includes the (joined)
	 * result of the SDP negotiation. For example with the Opus Codec, the format
	 * knows whether both parties want to do forward-error correction (FEC).
	 */
	pvt->explicit_dst = ao2_bump(explicit_dst);

	ast_module_ref(t->module);

	/* call local init routine, if present */
	if (t->newpvt && t->newpvt(pvt)) {
		ast_free(pvt);
		ast_module_unref(t->module);
		return NULL;
	}

	/* Setup normal static translation frame. */
	pvt->f.frametype = AST_FRAME_VOICE;
	pvt->f.mallocd = 0;
	pvt->f.offset = AST_FRIENDLY_OFFSET;
	pvt->f.src = pvt->t->name;
	pvt->f.data.ptr = pvt->outbuf.c;

	/*
	 * If the translator has not provided a format
	 * A) use the joined one,
	 * B) use the cached one, or
	 * C) create one.
	 */
	if (!pvt->f.subclass.format) {
		pvt->f.subclass.format = ao2_bump(pvt->explicit_dst);

		if (!pvt->f.subclass.format && !ast_strlen_zero(pvt->t->format)) {
			pvt->f.subclass.format = ast_format_cache_get(pvt->t->format);
		}

		if (!pvt->f.subclass.format) {
			struct ast_codec *codec = ast_codec_get(t->dst_codec.name,
				t->dst_codec.type, t->dst_codec.sample_rate);
			if (!codec) {
				ast_log(LOG_ERROR, "Unable to get destination codec\n");
				destroy(pvt);
				return NULL;
			}
			pvt->f.subclass.format = ast_format_create(codec);
			ao2_ref(codec, -1);
		}

		if (!pvt->f.subclass.format) {
			ast_log(LOG_ERROR, "Unable to create format\n");
			destroy(pvt);
			return NULL;
		}
	}

	return pvt;
}

/*! \brief framein wrapper, deals with bound checks.  */
static int framein(struct ast_trans_pvt *pvt, struct ast_frame *f)
{
	/* Copy the last in jb timing info to the pvt */
	ast_copy_flags(&pvt->f, f, AST_FRFLAG_HAS_TIMING_INFO);
	pvt->f.ts = f->ts;
	pvt->f.len = f->len;
	pvt->f.seqno = f->seqno;

	if (f->samples == 0) {
		ast_log(LOG_WARNING, "no samples for %s\n", pvt->t->name);
	}
	if (pvt->t->buffer_samples) {	/* do not pass empty frames to callback */
		if (f->datalen == 0) { /* perform native PLC if available */
			/* If the codec has native PLC, then do that */
			if (!pvt->t->native_plc)
				return 0;
		}
		if (pvt->samples + f->samples > pvt->t->buffer_samples) {
			ast_log(LOG_WARNING, "Out of buffer space\n");
			return -1;
		}
	}
	/* we require a framein routine, wouldn't know how to do
	 * it otherwise.
	 */
	return pvt->t->framein(pvt, f);
}

/*! \brief generic frameout routine.
 * If samples and datalen are 0, take whatever is in pvt
 * and reset them, otherwise take the values in the caller and
 * leave alone the pvt values.
 */
struct ast_frame *ast_trans_frameout(struct ast_trans_pvt *pvt,
	int datalen, int samples)
{
	struct ast_frame *f = &pvt->f;

	if (samples) {
		f->samples = samples;
	} else {
		if (pvt->samples == 0) {
			return NULL;
		}
		f->samples = pvt->samples;
		pvt->samples = 0;
	}
	if (datalen) {
		f->datalen = datalen;
		f->data.ptr = pvt->outbuf.c;
	} else {
		f->datalen = pvt->datalen;
		if (!f->datalen) {
			f->data.ptr = NULL;
		} else {
			f->data.ptr = pvt->outbuf.c;
		}
		pvt->datalen = 0;
	}

	return ast_frisolate(f);
}

static struct ast_frame *default_frameout(struct ast_trans_pvt *pvt)
{
	return ast_trans_frameout(pvt, 0, 0);
}

/* end of callback wrappers and helpers */

void ast_translator_free_path(struct ast_trans_pvt *p)
{
	struct ast_trans_pvt *pn = p;
	while ( (p = pn) ) {
		pn = p->next;
		destroy(p);
	}
}

/*! \brief Build a chain of translators based upon the given source and dest formats */
struct ast_trans_pvt *ast_translator_build_path(struct ast_format *dst, struct ast_format *src)
{
	struct ast_trans_pvt *head = NULL, *tail = NULL;
	int src_index, dst_index;

	src_index = format2index(src);
	dst_index = format2index(dst);

	if (src_index < 0 || dst_index < 0) {
		ast_log(LOG_WARNING, "No translator path: (%s codec is not valid)\n", src_index < 0 ? "starting" : "ending");
		return NULL;
	}

	AST_RWLIST_RDLOCK(&translators);

	while (src_index != dst_index) {
		struct ast_trans_pvt *cur;
		struct ast_format *explicit_dst = NULL;
		struct ast_translator *t = matrix_get(src_index, dst_index)->step;
		if (!t) {
			ast_log(LOG_WARNING, "No translator path from %s to %s\n",
				ast_format_get_name(src), ast_format_get_name(dst));
			AST_RWLIST_UNLOCK(&translators);
			return NULL;
		}
		if ((t->dst_codec.sample_rate == ast_format_get_sample_rate(dst)) && (t->dst_codec.type == ast_format_get_type(dst))) {
			explicit_dst = dst;
		}
		if (!(cur = newpvt(t, explicit_dst))) {
			ast_log(LOG_WARNING, "Failed to build translator step from %s to %s\n",
				ast_format_get_name(src), ast_format_get_name(dst));
			if (head) {
				ast_translator_free_path(head);
			}
			AST_RWLIST_UNLOCK(&translators);
			return NULL;
		}
		if (!head) {
			head = cur;
		} else {
			tail->next = cur;
		}
		tail = cur;
		cur->nextin = cur->nextout = ast_tv(0, 0);
		/* Keep going if this isn't the final destination */
		src_index = cur->t->dst_fmt_index;
	}

	AST_RWLIST_UNLOCK(&translators);
	return head;
}

/*! \brief do the actual translation */
struct ast_frame *ast_translate(struct ast_trans_pvt *path, struct ast_frame *f, int consume)
{
	struct ast_trans_pvt *p = path;
	struct ast_frame *out;
	struct timeval delivery;
	int has_timing_info;
	long ts;
	long len;
	int seqno;

	if (f->frametype == AST_FRAME_RTCP) {
		/* Just pass the feedback to the right callback, if it exists.
		 * This "translation" does nothing so return a null frame. */
		struct ast_trans_pvt *tp;
		for (tp = p; tp; tp = tp->next) {
			if (tp->t->feedback)
				tp->t->feedback(tp, f);
		}
		return &ast_null_frame;
	}

	has_timing_info = ast_test_flag(f, AST_FRFLAG_HAS_TIMING_INFO);
	ts = f->ts;
	len = f->len;
	seqno = f->seqno;

	if (!ast_tvzero(f->delivery)) {
		if (!ast_tvzero(path->nextin)) {
			/* Make sure this is in line with what we were expecting */
			if (!ast_tveq(path->nextin, f->delivery)) {
				/* The time has changed between what we expected and this
				   most recent time on the new packet.  If we have a
				   valid prediction adjust our output time appropriately */
				if (!ast_tvzero(path->nextout)) {
					path->nextout = ast_tvadd(path->nextout,
								  ast_tvsub(f->delivery, path->nextin));
				}
				path->nextin = f->delivery;
			}
		} else {
			/* This is our first pass.  Make sure the timing looks good */
			path->nextin = f->delivery;
			path->nextout = f->delivery;
		}
		/* Predict next incoming sample */
		path->nextin = ast_tvadd(path->nextin, ast_samp2tv(
			 f->samples, ast_format_get_sample_rate(f->subclass.format)));
	}
	delivery = f->delivery;
	for (out = f; out && p ; p = p->next) {
		struct ast_frame *current = out;

		do {
			framein(p, current);
			current = AST_LIST_NEXT(current, frame_list);
		} while (current);
		if (out != f) {
			ast_frfree(out);
		}
		out = p->t->frameout(p);
	}
	if (out) {
		/* we have a frame, play with times */
		if (!ast_tvzero(delivery)) {
			struct ast_frame *current = out;

			do {
				/* Regenerate prediction after a discontinuity */
				if (ast_tvzero(path->nextout)) {
					path->nextout = ast_tvnow();
				}

				/* Use next predicted outgoing timestamp */
				current->delivery = path->nextout;

				/* Invalidate prediction if we're entering a silence period */
				if (current->frametype == AST_FRAME_CNG) {
					path->nextout = ast_tv(0, 0);
				/* Predict next outgoing timestamp from samples in this
				   frame. */
				} else {
					path->nextout = ast_tvadd(path->nextout, ast_samp2tv(
						current->samples, ast_format_get_sample_rate(current->subclass.format)));
				}

				if (f->samples != current->samples && ast_test_flag(current, AST_FRFLAG_HAS_TIMING_INFO)) {
					ast_debug(4, "Sample size different %d vs %d\n", f->samples, current->samples);
					ast_clear_flag(current, AST_FRFLAG_HAS_TIMING_INFO);
				}
				current = AST_LIST_NEXT(current, frame_list);
			} while (current);
		} else {
			out->delivery = ast_tv(0, 0);
			ast_set2_flag(out, has_timing_info, AST_FRFLAG_HAS_TIMING_INFO);
			if (has_timing_info) {
				out->ts = ts;
				out->len = len;
				out->seqno = seqno;
			}
			/* Invalidate prediction if we're entering a silence period */
			if (out->frametype == AST_FRAME_CNG) {
				path->nextout = ast_tv(0, 0);
			}
		}
	}
	if (consume) {
		ast_frfree(f);
	}
	return out;
}

/*!
 * \internal
 * \brief Compute the computational cost of a single translation step.
 *
 * \note This function is only used to decide which translation path to
 * use between two translators with identical src and dst formats.  Computational
 * cost acts only as a tie breaker. This is done so hardware translators
 * can naturally have precedence over software translators.
 */
static void generate_computational_cost(struct ast_translator *t, int seconds)
{
	int num_samples = 0;
	struct ast_trans_pvt *pvt;
	struct rusage start;
	struct rusage end;
	int cost;
	int out_rate = t->dst_codec.sample_rate;

	if (!seconds) {
		seconds = 1;
	}

	/* If they don't make samples, give them a terrible score */
	if (!t->sample) {
		ast_debug(3, "Translator '%s' does not produce sample frames.\n", t->name);
		t->comp_cost = 999999;
		return;
	}

	pvt = newpvt(t, NULL);
	if (!pvt) {
		ast_log(LOG_WARNING, "Translator '%s' appears to be broken and will probably fail.\n", t->name);
		t->comp_cost = 999999;
		return;
	}

	getrusage(RUSAGE_SELF, &start);

	/* Call the encoder until we've processed the required number of samples */
	while (num_samples < seconds * out_rate) {
		struct ast_frame *f = t->sample();
		if (!f) {
			ast_log(LOG_WARNING, "Translator '%s' failed to produce a sample frame.\n", t->name);
			destroy(pvt);
			t->comp_cost = 999999;
			return;
		}
		framein(pvt, f);
		ast_frfree(f);
		while ((f = t->frameout(pvt))) {
			num_samples += f->samples;
			ast_frfree(f);
		}
	}

	getrusage(RUSAGE_SELF, &end);

	cost = ((end.ru_utime.tv_sec - start.ru_utime.tv_sec) * 1000000) + end.ru_utime.tv_usec - start.ru_utime.tv_usec;
	cost += ((end.ru_stime.tv_sec - start.ru_stime.tv_sec) * 1000000) + end.ru_stime.tv_usec - start.ru_stime.tv_usec;

	destroy(pvt);

	t->comp_cost = cost / seconds;

	if (!t->comp_cost) {
		t->comp_cost = 1;
	}
}

/*!
 * \internal
 *
 * \brief If no table cost value was pre set by the translator.  An attempt is made to
 * automatically generate that cost value from the cost table based on our src and
 * dst formats.
 *
 * \note This function allows older translators built before the translation cost
 * changed away from using onely computational time to continue to be registered
 * correctly.  It is expected that translators built after the introduction of this
 * function will manually assign their own table cost value.
 *
 * \note This function is safe to use on any audio formats that used to be defined in the
 * first 64 bits of the old bit field codec representation.
 *
 * \retval Table Cost value greater than 0.
 * \retval 0 on error.
 */
static int generate_table_cost(struct ast_codec *src, struct ast_codec *dst)
{
	int src_rate = src->sample_rate;
	int src_ll = 0;
	int dst_rate = dst->sample_rate;
	int dst_ll = 0;

	if ((src->type != AST_MEDIA_TYPE_AUDIO) ||
	    (dst->type != AST_MEDIA_TYPE_AUDIO)) {
		/* This method of generating table cost is limited to audio.
		 * Translators for media other than audio must manually set their
		 * table cost. */
		return 0;
	}

	src_ll = !strcmp(src->name, "slin");
	dst_ll = !strcmp(dst->name, "slin");
	if (src_ll) {
		if (dst_ll && (src_rate == dst_rate)) {
			return AST_TRANS_COST_LL_LL_ORIGSAMP;
		} else if (!dst_ll && (src_rate == dst_rate)) {
			return AST_TRANS_COST_LL_LY_ORIGSAMP;
		} else if (dst_ll && (src_rate < dst_rate)) {
			return AST_TRANS_COST_LL_LL_UPSAMP;
		} else if (!dst_ll && (src_rate < dst_rate)) {
			return AST_TRANS_COST_LL_LY_UPSAMP;
		} else if (dst_ll && (src_rate > dst_rate)) {
			return AST_TRANS_COST_LL_LL_DOWNSAMP;
		} else if (!dst_ll && (src_rate > dst_rate)) {
			return AST_TRANS_COST_LL_LY_DOWNSAMP;
		} else {
			return AST_TRANS_COST_LL_UNKNOWN;
		}
	} else {
		if (dst_ll && (src_rate == dst_rate)) {
			return AST_TRANS_COST_LY_LL_ORIGSAMP;
		} else if (!dst_ll && (src_rate == dst_rate)) {
			return AST_TRANS_COST_LY_LY_ORIGSAMP;
		} else if (dst_ll && (src_rate < dst_rate)) {
			return AST_TRANS_COST_LY_LL_UPSAMP;
		} else if (!dst_ll && (src_rate < dst_rate)) {
			return AST_TRANS_COST_LY_LY_UPSAMP;
		} else if (dst_ll && (src_rate > dst_rate)) {
			return AST_TRANS_COST_LY_LL_DOWNSAMP;
		} else if (!dst_ll && (src_rate > dst_rate)) {
			return AST_TRANS_COST_LY_LY_DOWNSAMP;
		} else {
			return AST_TRANS_COST_LY_UNKNOWN;
		}
	}
}

/*!
 * \brief rebuild a translation matrix.
 * \note This function expects the list of translators to be locked
*/
static void matrix_rebuild(int samples)
{
	struct ast_translator *t;
	int newtablecost;
	int x;      /* source format index */
	int y;      /* intermediate format index */
	int z;      /* destination format index */

	ast_debug(1, "Resetting translation matrix\n");

	matrix_clear();

	/* first, compute all direct costs */
	AST_RWLIST_TRAVERSE(&translators, t, list) {
		if (!t->active) {
			continue;
		}

		x = t->src_fmt_index;
		z = t->dst_fmt_index;

		if (samples) {
			generate_computational_cost(t, samples);
		}

		/* This new translator is the best choice if any of the below are true.
		 * 1. no translation path is set between x and z yet.
		 * 2. the new table cost is less.
		 * 3. the new computational cost is less.  Computational cost is only used
		 *    to break a tie between two identical translation paths.
		 */
		if (!matrix_get(x, z)->step ||
			(t->table_cost < matrix_get(x, z)->step->table_cost) ||
			(t->comp_cost < matrix_get(x, z)->step->comp_cost)) {

			matrix_get(x, z)->step = t;
			matrix_get(x, z)->table_cost = t->table_cost;
		}
	}

	/*
	 * For each triple x, y, z of distinct formats, check if there is
	 * a path from x to z through y which is cheaper than what is
	 * currently known, and in case, update the matrix.
	 * Repeat until the matrix is stable.
	 */
	for (;;) {
		int changed = 0;
		for (x = 0; x < cur_max_index; x++) {      /* source format */
			for (y = 0; y < cur_max_index; y++) {  /* intermediate format */
				if (x == y) {                      /* skip ourselves */
					continue;
				}
				for (z = 0; z < cur_max_index; z++) {  /* dst format */
					if ((z == x || z == y) ||        /* skip null conversions */
						!matrix_get(x, y)->step ||   /* no path from x to y */
						!matrix_get(y, z)->step) {   /* no path from y to z */
						continue;
					}

					/* calculate table cost from x->y->z */
					newtablecost = matrix_get(x, y)->table_cost + matrix_get(y, z)->table_cost;

					/* if no step already exists between x and z OR the new cost of using the intermediate
					 * step is cheaper, use this step. */
					if (!matrix_get(x, z)->step || (newtablecost < matrix_get(x, z)->table_cost)) {
						matrix_get(x, z)->step = matrix_get(x, y)->step;
						matrix_get(x, z)->table_cost = newtablecost;
						matrix_get(x, z)->multistep = 1;
						changed++;

						if (DEBUG_ATLEAST(10)) {
							struct ast_codec *x_codec = index2codec(x);
							struct ast_codec *y_codec = index2codec(y);
							struct ast_codec *z_codec = index2codec(z);

							ast_log(LOG_DEBUG,
								"Discovered %u cost path from %s to %s, via %s\n",
								matrix_get(x, z)->table_cost, x_codec->name,
								y_codec->name, z_codec->name);

							ao2_ref(x_codec, -1);
							ao2_ref(y_codec, -1);
							ao2_ref(z_codec, -1);
						}
					}
				}
			}
		}
		if (!changed) {
			break;
		}
	}
}

static void codec_append_name(const struct ast_codec *codec, struct ast_str **buf)
{
	if (codec) {
		ast_str_append(buf, 0, "(%s@%u)", codec->name, codec->sample_rate);
	} else {
		ast_str_append(buf, 0, "(nothing)");
	}
}

const char *ast_translate_path_to_str(struct ast_trans_pvt *p, struct ast_str **str)
{
	if (!p || !p->t) {
		return "";
	}

	ast_str_reset(*str);
	codec_append_name(&p->t->src_codec, str);
	while (p) {
		ast_str_append(str, 0, "->");
		codec_append_name(&p->t->dst_codec, str);
		p = p->next;
	}

	return ast_str_buffer(*str);
}

static char *complete_trans_path_choice(const char *line, const char *word, int pos, int state)
{
	int i = 1, which = 0;
	int wordlen = strlen(word);
	struct ast_codec *codec;

	while ((codec = ast_codec_get_by_id(i))) {
		++i;
		if (codec->type != AST_MEDIA_TYPE_AUDIO) {
			ao2_ref(codec, -1);
			continue;
		}
		if (!strncasecmp(word, codec->name, wordlen) && ++which > state) {
			char *res = ast_strdup(codec->name);
			ao2_ref(codec, -1);
			return res;
		}
		ao2_ref(codec, -1);
	}
	return NULL;
}

static void handle_cli_recalc(struct ast_cli_args *a)
{
	int time = a->argv[4] ? atoi(a->argv[4]) : 1;

	if (time <= 0) {
		ast_cli(a->fd, "         Recalc must be greater than 0.  Defaulting to 1.\n");
		time = 1;
	}

	if (time > MAX_RECALC) {
		ast_cli(a->fd, "         Maximum limit of recalc exceeded by %d, truncating value to %d\n", time - MAX_RECALC, MAX_RECALC);
		time = MAX_RECALC;
	}
	ast_cli(a->fd, "         Recalculating Codec Translation (number of sample seconds: %d)\n\n", time);
	AST_RWLIST_WRLOCK(&translators);
	matrix_rebuild(time);
	AST_RWLIST_UNLOCK(&translators);
}

static char *handle_show_translation_table(struct ast_cli_args *a)
{
	int x, y, i, k;
	int longest = 7; /* slin192 */
	int num_codecs = 0, curlen = 0;
	struct ast_str *out = ast_str_create(1024);
	struct ast_codec *codec;

	/* Get the length of the longest (usable?) codec name,
	   so we know how wide the left side should be */
	for (i = 1; (codec = ast_codec_get_by_id(i)); ao2_ref(codec, -1), ++i) {
		++num_codecs;
		if (codec->type != AST_MEDIA_TYPE_AUDIO) {
			continue;
		}
		curlen = strlen(codec->name);
		if (curlen > longest) {
			longest = curlen;
		}
	}

	AST_RWLIST_RDLOCK(&translators);
	ast_cli(a->fd, "         Translation times between formats (in microseconds) for one second of data\n");
	ast_cli(a->fd, "          Source Format (Rows) Destination Format (Columns)\n\n");

	for (i = 0; i < num_codecs; i++) {
		struct ast_codec *row = i ? ast_codec_get_by_id(i) : NULL;

		x = -1;
		if ((i > 0) && (row->type != AST_MEDIA_TYPE_AUDIO)) {
			ao2_ref(row, -1);
			continue;
		}

		if ((i > 0) && (x = codec2index(row)) == -1) {
			ao2_ref(row, -1);
			continue;
		}

		ast_str_set(&out, 0, " ");
		for (k = 0; k < num_codecs; k++) {
			int adjust = 0;
			struct ast_codec *col = k ? ast_codec_get_by_id(k) : NULL;

			y = -1;
			if ((k > 0) && (col->type != AST_MEDIA_TYPE_AUDIO)) {
				ao2_ref(col, -1);
				continue;
			}

			if ((k > 0) && (y = codec2index(col)) == -1) {
				ao2_ref(col, -1);
				continue;
			}