chan_sip: Check sip_pvt pointer in ast_channel_get_t38_state(c)
[asterisk/asterisk.git] / main / translate.c
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 1999 - 2006, Digium, Inc.
5  *
6  * Mark Spencer <markster@digium.com>
7  *
8  * See http://www.asterisk.org for more information about
9  * the Asterisk project. Please do not directly contact
10  * any of the maintainers of this project for assistance;
11  * the project provides a web site, mailing lists and IRC
12  * channels for your use.
13  *
14  * This program is free software, distributed under the terms of
15  * the GNU General Public License Version 2. See the LICENSE file
16  * at the top of the source tree.
17  */
18
19 /*! \file
20  *
21  * \brief Translate via the use of pseudo channels
22  *
23  * \author Mark Spencer <markster@digium.com>
24  */
25
26 /*** MODULEINFO
27         <support_level>core</support_level>
28  ***/
29
30 #include "asterisk.h"
31
32 ASTERISK_REGISTER_FILE()
33
34 #include <sys/time.h>
35 #include <sys/resource.h>
36 #include <math.h>
37
38 #include "asterisk/lock.h"
39 #include "asterisk/channel.h"
40 #include "asterisk/translate.h"
41 #include "asterisk/module.h"
42 #include "asterisk/frame.h"
43 #include "asterisk/sched.h"
44 #include "asterisk/cli.h"
45 #include "asterisk/term.h"
46 #include "asterisk/format.h"
47 #include "asterisk/linkedlists.h"
48
49 /*! \todo
50  * TODO: sample frames for each supported input format.
51  * We build this on the fly, by taking an SLIN frame and using
52  * the existing converter to play with it.
53  */
54
55 /*! max sample recalc */
56 #define MAX_RECALC 1000
57
58 /*! \brief the list of translators */
59 static AST_RWLIST_HEAD_STATIC(translators, ast_translator);
60
61 struct translator_path {
62         struct ast_translator *step;       /*!< Next step translator */
63         uint32_t table_cost;               /*!< Complete table cost to destination */
64         uint8_t multistep;                 /*!< Multiple conversions required for this translation */
65 };
66
67 /*!
68  * \brief a matrix that, for any pair of supported formats,
69  * indicates the total cost of translation and the first step.
70  * The full path can be reconstricted iterating on the matrix
71  * until step->dstfmt == desired_format.
72  *
73  * Array indexes are 'src' and 'dest', in that order.
74  *
75  * Note: the lock in the 'translators' list is also used to protect
76  * this structure.
77  */
78 static struct translator_path **__matrix;
79
80 /*!
81  * \brief table for converting index to format values.
82  *
83  * \note this table is protected by the table_lock.
84  */
85 static unsigned int *__indextable;
86
87 /*! protects the __indextable for resizing */
88 static ast_rwlock_t tablelock;
89
90 /* index size starts at this*/
91 #define INIT_INDEX 32
92 /* index size grows by this as necessary */
93 #define GROW_INDEX 16
94
95 /*! the current largest index used by the __matrix and __indextable arrays*/
96 static int cur_max_index;
97 /*! the largest index that can be used in either the __indextable or __matrix before resize must occur */
98 static int index_size;
99
100 static void matrix_rebuild(int samples);
101
102 /*!
103  * \internal
104  * \brief converts codec id to index value.
105  */
106 static int codec_to_index(unsigned int id)
107 {
108         int x;
109
110         ast_rwlock_rdlock(&tablelock);
111         for (x = 0; x < cur_max_index; x++) {
112                 if (__indextable[x] == id) {
113                         /* format already exists in index2format table */
114                         ast_rwlock_unlock(&tablelock);
115                         return x;
116                 }
117         }
118         ast_rwlock_unlock(&tablelock);
119         return -1; /* not found */
120 }
121
122 /*!
123  * \internal
124  * \brief converts codec to index value.
125  */
126 static int codec2index(struct ast_codec *codec)
127 {
128         return codec_to_index(codec->id);
129 }
130
131 /*!
132  * \internal
133  * \brief converts format to codec index value.
134  */
135 static int format2index(struct ast_format *format)
136 {
137         return codec_to_index(ast_format_get_codec_id(format));
138 }
139
140 /*!
141  * \internal
142  * \brief add a new codec to the matrix and index table structures.
143  *
144  * \note it is perfectly safe to call this on codecs already indexed.
145  *
146  * \retval 0, success
147  * \retval -1, matrix and index table need to be resized
148  */
149 static int add_codec2index(struct ast_codec *codec)
150 {
151         if (codec2index(codec) != -1) {
152                 /* format is already already indexed */
153                 return 0;
154         }
155
156         ast_rwlock_wrlock(&tablelock);
157         if (cur_max_index == (index_size)) {
158                 ast_rwlock_unlock(&tablelock);
159                 return -1; /* hit max length */
160         }
161         __indextable[cur_max_index] = codec->id;
162         cur_max_index++;
163         ast_rwlock_unlock(&tablelock);
164
165         return 0;
166 }
167
168 /*!
169  * \internal
170  * \brief converts index value back to codec
171  */
172 static struct ast_codec *index2codec(int index)
173 {
174         struct ast_codec *codec;
175
176         if (index >= cur_max_index) {
177                 return 0;
178         }
179         ast_rwlock_rdlock(&tablelock);
180         codec = ast_codec_get_by_id(__indextable[index]);
181         ast_rwlock_unlock(&tablelock);
182
183         return codec;
184 }
185
186 /*!
187  * \internal
188  * \brief resize both the matrix and index table so they can represent
189  * more translators
190  *
191  * \note _NO_ locks can be held prior to calling this function
192  *
193  * \retval 0, success
194  * \retval -1, failure.  Old matrix and index table can still be used though
195  */
196 static int matrix_resize(int init)
197 {
198         struct translator_path **tmp_matrix = NULL;
199         unsigned int *tmp_table = NULL;
200         int old_index;
201         int x;
202
203         AST_RWLIST_WRLOCK(&translators);
204         ast_rwlock_wrlock(&tablelock);
205
206         old_index = index_size;
207         if (init) {
208                 index_size += INIT_INDEX;
209         } else {
210                 index_size += GROW_INDEX;
211         }
212
213         /* make new 2d array of translator_path structures */
214         if (!(tmp_matrix = ast_calloc(1, sizeof(struct translator_path *) * (index_size)))) {
215                 goto resize_cleanup;
216         }
217
218         for (x = 0; x < index_size; x++) {
219                 if (!(tmp_matrix[x] = ast_calloc(1, sizeof(struct translator_path) * (index_size)))) {
220                         goto resize_cleanup;
221                 }
222         }
223
224         /* make new index table */
225         if (!(tmp_table = ast_calloc(1, sizeof(unsigned int) * index_size))) {
226                 goto resize_cleanup;
227         }
228
229         /* if everything went well this far, free the old and use the new */
230         if (!init) {
231                 for (x = 0; x < old_index; x++) {
232                         ast_free(__matrix[x]);
233                 }
234                 ast_free(__matrix);
235
236                 memcpy(tmp_table, __indextable, sizeof(unsigned int) * old_index);
237                 ast_free(__indextable);
238         }
239
240         /* now copy them over */
241         __matrix = tmp_matrix;
242         __indextable = tmp_table;
243
244         matrix_rebuild(0);
245         ast_rwlock_unlock(&tablelock);
246         AST_RWLIST_UNLOCK(&translators);
247
248         return 0;
249
250 resize_cleanup:
251         ast_rwlock_unlock(&tablelock);
252         AST_RWLIST_UNLOCK(&translators);
253         if (tmp_matrix) {
254                 for (x = 0; x < index_size; x++) {
255                         ast_free(tmp_matrix[x]);
256                 }
257                 ast_free(tmp_matrix);
258         }
259         ast_free(tmp_table);
260
261         return -1;
262 }
263
264 /*!
265  * \internal
266  * \brief reinitialize the __matrix during matrix rebuild
267  *
268  * \note must be protected by the translators list lock
269  */
270 static void matrix_clear(void)
271 {
272         int x;
273         for (x = 0; x < index_size; x++) {
274                 memset(__matrix[x], '\0', sizeof(struct translator_path) * (index_size));
275         }
276 }
277
278 /*!
279  * \internal
280  * \brief get a matrix entry
281  *
282  * \note This function must be protected by the translators list lock
283  */
284 static struct translator_path *matrix_get(unsigned int x, unsigned int y)
285 {
286         return __matrix[x] + y;
287 }
288
289 /*
290  * wrappers around the translator routines.
291  */
292
293 static void destroy(struct ast_trans_pvt *pvt)
294 {
295         struct ast_translator *t = pvt->t;
296
297         if (t->destroy) {
298                 t->destroy(pvt);
299         }
300         ao2_cleanup(pvt->f.subclass.format);
301         if (pvt->explicit_dst) {
302                 ao2_ref(pvt->explicit_dst, -1);
303                 pvt->explicit_dst = NULL;
304         }
305         ast_free(pvt);
306         ast_module_unref(t->module);
307 }
308
309 /*!
310  * \brief Allocate the descriptor, required outbuf space,
311  * and possibly desc.
312  */
313 static struct ast_trans_pvt *newpvt(struct ast_translator *t, struct ast_format *explicit_dst)
314 {
315         struct ast_trans_pvt *pvt;
316         int len;
317         char *ofs;
318
319         /*
320          * compute the required size adding private descriptor,
321          * buffer, AST_FRIENDLY_OFFSET.
322          */
323         len = sizeof(*pvt) + t->desc_size;
324         if (t->buf_size)
325                 len += AST_FRIENDLY_OFFSET + t->buf_size;
326         pvt = ast_calloc(1, len);
327         if (!pvt) {
328                 return NULL;
329         }
330         pvt->t = t;
331         ofs = (char *)(pvt + 1);        /* pointer to data space */
332         if (t->desc_size) {             /* first comes the descriptor */
333                 pvt->pvt = ofs;
334                 ofs += t->desc_size;
335         }
336         if (t->buf_size) {/* finally buffer and header */
337                 pvt->outbuf.c = ofs + AST_FRIENDLY_OFFSET;
338         }
339         /*
340          * If the format has an attribute module, explicit_dst includes the (joined)
341          * result of the SDP negotiation. For example with the Opus Codec, the format
342          * knows whether both parties want to do forward-error correction (FEC).
343          */
344         pvt->explicit_dst = ao2_bump(explicit_dst);
345
346         ast_module_ref(t->module);
347
348         /* call local init routine, if present */
349         if (t->newpvt && t->newpvt(pvt)) {
350                 ast_free(pvt);
351                 ast_module_unref(t->module);
352                 return NULL;
353         }
354
355         /* Setup normal static translation frame. */
356         pvt->f.frametype = AST_FRAME_VOICE;
357         pvt->f.mallocd = 0;
358         pvt->f.offset = AST_FRIENDLY_OFFSET;
359         pvt->f.src = pvt->t->name;
360         pvt->f.data.ptr = pvt->outbuf.c;
361
362         /*
363          * If the translator has not provided a format
364          * A) use the joined one,
365          * B) use the cached one, or
366          * C) create one.
367          */
368         if (!pvt->f.subclass.format) {
369                 pvt->f.subclass.format = ao2_bump(pvt->explicit_dst);
370
371                 if (!pvt->f.subclass.format && !ast_strlen_zero(pvt->t->format)) {
372                         pvt->f.subclass.format = ast_format_cache_get(pvt->t->format);
373                 }
374
375                 if (!pvt->f.subclass.format) {
376                         struct ast_codec *codec = ast_codec_get(t->dst_codec.name,
377                                 t->dst_codec.type, t->dst_codec.sample_rate);
378                         if (!codec) {
379                                 ast_log(LOG_ERROR, "Unable to get destination codec\n");
380                                 destroy(pvt);
381                                 return NULL;
382                         }
383                         pvt->f.subclass.format = ast_format_create(codec);
384                         ao2_ref(codec, -1);
385                 }
386
387                 if (!pvt->f.subclass.format) {
388                         ast_log(LOG_ERROR, "Unable to create format\n");
389                         destroy(pvt);
390                         return NULL;
391                 }
392         }
393
394         return pvt;
395 }
396
397 /*! \brief framein wrapper, deals with bound checks.  */
398 static int framein(struct ast_trans_pvt *pvt, struct ast_frame *f)
399 {
400         int ret;
401         int samples = pvt->samples;     /* initial value */
402
403         /* Copy the last in jb timing info to the pvt */
404         ast_copy_flags(&pvt->f, f, AST_FRFLAG_HAS_TIMING_INFO);
405         pvt->f.ts = f->ts;
406         pvt->f.len = f->len;
407         pvt->f.seqno = f->seqno;
408
409         if (f->samples == 0) {
410                 ast_log(LOG_WARNING, "no samples for %s\n", pvt->t->name);
411         }
412         if (pvt->t->buffer_samples) {   /* do not pass empty frames to callback */
413                 if (f->datalen == 0) { /* perform native PLC if available */
414                         /* If the codec has native PLC, then do that */
415                         if (!pvt->t->native_plc)
416                                 return 0;
417                 }
418                 if (pvt->samples + f->samples > pvt->t->buffer_samples) {
419                         ast_log(LOG_WARNING, "Out of buffer space\n");
420                         return -1;
421                 }
422         }
423         /* we require a framein routine, wouldn't know how to do
424          * it otherwise.
425          */
426         ret = pvt->t->framein(pvt, f);
427         /* diagnostic ... */
428         if (pvt->samples == samples)
429                 ast_log(LOG_WARNING, "%s did not update samples %d\n",
430                         pvt->t->name, pvt->samples);
431         return ret;
432 }
433
434 /*! \brief generic frameout routine.
435  * If samples and datalen are 0, take whatever is in pvt
436  * and reset them, otherwise take the values in the caller and
437  * leave alone the pvt values.
438  */
439 struct ast_frame *ast_trans_frameout(struct ast_trans_pvt *pvt,
440         int datalen, int samples)
441 {
442         struct ast_frame *f = &pvt->f;
443
444         if (samples) {
445                 f->samples = samples;
446         } else {
447                 if (pvt->samples == 0) {
448                         return NULL;
449                 }
450                 f->samples = pvt->samples;
451                 pvt->samples = 0;
452         }
453         if (datalen) {
454                 f->datalen = datalen;
455         } else {
456                 f->datalen = pvt->datalen;
457                 pvt->datalen = 0;
458         }
459
460         return ast_frisolate(f);
461 }
462
463 static struct ast_frame *default_frameout(struct ast_trans_pvt *pvt)
464 {
465         return ast_trans_frameout(pvt, 0, 0);
466 }
467
468 /* end of callback wrappers and helpers */
469
470 void ast_translator_free_path(struct ast_trans_pvt *p)
471 {
472         struct ast_trans_pvt *pn = p;
473         while ( (p = pn) ) {
474                 pn = p->next;
475                 destroy(p);
476         }
477 }
478
479 /*! \brief Build a chain of translators based upon the given source and dest formats */
480 struct ast_trans_pvt *ast_translator_build_path(struct ast_format *dst, struct ast_format *src)
481 {
482         struct ast_trans_pvt *head = NULL, *tail = NULL;
483         int src_index, dst_index;
484
485         src_index = format2index(src);
486         dst_index = format2index(dst);
487
488         if (src_index < 0 || dst_index < 0) {
489                 ast_log(LOG_WARNING, "No translator path: (%s codec is not valid)\n", src_index < 0 ? "starting" : "ending");
490                 return NULL;
491         }
492
493         AST_RWLIST_RDLOCK(&translators);
494
495         while (src_index != dst_index) {
496                 struct ast_trans_pvt *cur;
497                 struct ast_format *explicit_dst = NULL;
498                 struct ast_translator *t = matrix_get(src_index, dst_index)->step;
499                 if (!t) {
500                         ast_log(LOG_WARNING, "No translator path from %s to %s\n",
501                                 ast_format_get_name(src), ast_format_get_name(dst));
502                         AST_RWLIST_UNLOCK(&translators);
503                         return NULL;
504                 }
505                 if ((t->dst_codec.sample_rate == ast_format_get_sample_rate(dst)) && (t->dst_codec.type == ast_format_get_type(dst)) && (!strcmp(t->dst_codec.name, ast_format_get_name(dst)))) {
506                         explicit_dst = dst;
507                 }
508                 if (!(cur = newpvt(t, explicit_dst))) {
509                         ast_log(LOG_WARNING, "Failed to build translator step from %s to %s\n",
510                                 ast_format_get_name(src), ast_format_get_name(dst));
511                         if (head) {
512                                 ast_translator_free_path(head);
513                         }
514                         AST_RWLIST_UNLOCK(&translators);
515                         return NULL;
516                 }
517                 if (!head) {
518                         head = cur;
519                 } else {
520                         tail->next = cur;
521                 }
522                 tail = cur;
523                 cur->nextin = cur->nextout = ast_tv(0, 0);
524                 /* Keep going if this isn't the final destination */
525                 src_index = cur->t->dst_fmt_index;
526         }
527
528         AST_RWLIST_UNLOCK(&translators);
529         return head;
530 }
531
532 /*! \brief do the actual translation */
533 struct ast_frame *ast_translate(struct ast_trans_pvt *path, struct ast_frame *f, int consume)
534 {
535         struct ast_trans_pvt *p = path;
536         struct ast_frame *out;
537         struct timeval delivery;
538         int has_timing_info;
539         long ts;
540         long len;
541         int seqno;
542
543         has_timing_info = ast_test_flag(f, AST_FRFLAG_HAS_TIMING_INFO);
544         ts = f->ts;
545         len = f->len;
546         seqno = f->seqno;
547
548         if (!ast_tvzero(f->delivery)) {
549                 if (!ast_tvzero(path->nextin)) {
550                         /* Make sure this is in line with what we were expecting */
551                         if (!ast_tveq(path->nextin, f->delivery)) {
552                                 /* The time has changed between what we expected and this
553                                    most recent time on the new packet.  If we have a
554                                    valid prediction adjust our output time appropriately */
555                                 if (!ast_tvzero(path->nextout)) {
556                                         path->nextout = ast_tvadd(path->nextout,
557                                                                   ast_tvsub(f->delivery, path->nextin));
558                                 }
559                                 path->nextin = f->delivery;
560                         }
561                 } else {
562                         /* This is our first pass.  Make sure the timing looks good */
563                         path->nextin = f->delivery;
564                         path->nextout = f->delivery;
565                 }
566                 /* Predict next incoming sample */
567                 path->nextin = ast_tvadd(path->nextin, ast_samp2tv(
568                          f->samples, ast_format_get_sample_rate(f->subclass.format)));
569         }
570         delivery = f->delivery;
571         for (out = f; out && p ; p = p->next) {
572                 struct ast_frame *current = out;
573
574                 do {
575                         framein(p, current);
576                         current = AST_LIST_NEXT(current, frame_list);
577                 } while (current);
578                 if (out != f) {
579                         ast_frfree(out);
580                 }
581                 out = p->t->frameout(p);
582         }
583         if (out) {
584                 /* we have a frame, play with times */
585                 if (!ast_tvzero(delivery)) {
586                         struct ast_frame *current = out;
587
588                         do {
589                                 /* Regenerate prediction after a discontinuity */
590                                 if (ast_tvzero(path->nextout)) {
591                                         path->nextout = ast_tvnow();
592                                 }
593
594                                 /* Use next predicted outgoing timestamp */
595                                 current->delivery = path->nextout;
596
597                                 /* Invalidate prediction if we're entering a silence period */
598                                 if (current->frametype == AST_FRAME_CNG) {
599                                         path->nextout = ast_tv(0, 0);
600                                 /* Predict next outgoing timestamp from samples in this
601                                    frame. */
602                                 } else {
603                                         path->nextout = ast_tvadd(path->nextout, ast_samp2tv(
604                                                 current->samples, ast_format_get_sample_rate(current->subclass.format)));
605                                 }
606
607                                 if (f->samples != current->samples && ast_test_flag(current, AST_FRFLAG_HAS_TIMING_INFO)) {
608                                         ast_debug(4, "Sample size different %d vs %d\n", f->samples, current->samples);
609                                         ast_clear_flag(current, AST_FRFLAG_HAS_TIMING_INFO);
610                                 }
611                                 current = AST_LIST_NEXT(current, frame_list);
612                         } while (current);
613                 } else {
614                         out->delivery = ast_tv(0, 0);
615                         ast_set2_flag(out, has_timing_info, AST_FRFLAG_HAS_TIMING_INFO);
616                         if (has_timing_info) {
617                                 out->ts = ts;
618                                 out->len = len;
619                                 out->seqno = seqno;
620                         }
621                         /* Invalidate prediction if we're entering a silence period */
622                         if (out->frametype == AST_FRAME_CNG) {
623                                 path->nextout = ast_tv(0, 0);
624                         }
625                 }
626         }
627         if (consume) {
628                 ast_frfree(f);
629         }
630         return out;
631 }
632
633 /*!
634  * \internal
635  * \brief Compute the computational cost of a single translation step.
636  *
637  * \note This function is only used to decide which translation path to
638  * use between two translators with identical src and dst formats.  Computational
639  * cost acts only as a tie breaker. This is done so hardware translators
640  * can naturally have precedence over software translators.
641  */
642 static void generate_computational_cost(struct ast_translator *t, int seconds)
643 {
644         int num_samples = 0;
645         struct ast_trans_pvt *pvt;
646         struct rusage start;
647         struct rusage end;
648         int cost;
649         int out_rate = t->dst_codec.sample_rate;
650
651         if (!seconds) {
652                 seconds = 1;
653         }
654
655         /* If they don't make samples, give them a terrible score */
656         if (!t->sample) {
657                 ast_debug(3, "Translator '%s' does not produce sample frames.\n", t->name);
658                 t->comp_cost = 999999;
659                 return;
660         }
661
662         pvt = newpvt(t, NULL);
663         if (!pvt) {
664                 ast_log(LOG_WARNING, "Translator '%s' appears to be broken and will probably fail.\n", t->name);
665                 t->comp_cost = 999999;
666                 return;
667         }
668
669         getrusage(RUSAGE_SELF, &start);
670
671         /* Call the encoder until we've processed the required number of samples */
672         while (num_samples < seconds * out_rate) {
673                 struct ast_frame *f = t->sample();
674                 if (!f) {
675                         ast_log(LOG_WARNING, "Translator '%s' failed to produce a sample frame.\n", t->name);
676                         destroy(pvt);
677                         t->comp_cost = 999999;
678                         return;
679                 }
680                 framein(pvt, f);
681                 ast_frfree(f);
682                 while ((f = t->frameout(pvt))) {
683                         num_samples += f->samples;
684                         ast_frfree(f);
685                 }
686         }
687
688         getrusage(RUSAGE_SELF, &end);
689
690         cost = ((end.ru_utime.tv_sec - start.ru_utime.tv_sec) * 1000000) + end.ru_utime.tv_usec - start.ru_utime.tv_usec;
691         cost += ((end.ru_stime.tv_sec - start.ru_stime.tv_sec) * 1000000) + end.ru_stime.tv_usec - start.ru_stime.tv_usec;
692
693         destroy(pvt);
694
695         t->comp_cost = cost / seconds;
696
697         if (!t->comp_cost) {
698                 t->comp_cost = 1;
699         }
700 }
701
702 /*!
703  * \internal
704  *
705  * \brief If no table cost value was pre set by the translator.  An attempt is made to
706  * automatically generate that cost value from the cost table based on our src and
707  * dst formats.
708  *
709  * \note This function allows older translators built before the translation cost
710  * changed away from using onely computational time to continue to be registered
711  * correctly.  It is expected that translators built after the introduction of this
712  * function will manually assign their own table cost value.
713  *
714  * \note This function is safe to use on any audio formats that used to be defined in the
715  * first 64 bits of the old bit field codec representation.
716  *
717  * \retval Table Cost value greater than 0.
718  * \retval 0 on error.
719  */
720 static int generate_table_cost(struct ast_codec *src, struct ast_codec *dst)
721 {
722         int src_rate = src->sample_rate;
723         int src_ll = 0;
724         int dst_rate = dst->sample_rate;
725         int dst_ll = 0;
726
727         if ((src->type != AST_MEDIA_TYPE_AUDIO) ||
728             (dst->type != AST_MEDIA_TYPE_AUDIO)) {
729                 /* This method of generating table cost is limited to audio.
730                  * Translators for media other than audio must manually set their
731                  * table cost. */
732                 return 0;
733         }
734
735         src_ll = !strcmp(src->name, "slin");
736         dst_ll = !strcmp(dst->name, "slin");
737         if (src_ll) {
738                 if (dst_ll && (src_rate == dst_rate)) {
739                         return AST_TRANS_COST_LL_LL_ORIGSAMP;
740                 } else if (!dst_ll && (src_rate == dst_rate)) {
741                         return AST_TRANS_COST_LL_LY_ORIGSAMP;
742                 } else if (dst_ll && (src_rate < dst_rate)) {
743                         return AST_TRANS_COST_LL_LL_UPSAMP;
744                 } else if (!dst_ll && (src_rate < dst_rate)) {
745                         return AST_TRANS_COST_LL_LY_UPSAMP;
746                 } else if (dst_ll && (src_rate > dst_rate)) {
747                         return AST_TRANS_COST_LL_LL_DOWNSAMP;
748                 } else if (!dst_ll && (src_rate > dst_rate)) {
749                         return AST_TRANS_COST_LL_LY_DOWNSAMP;
750                 } else {
751                         return AST_TRANS_COST_LL_UNKNOWN;
752                 }
753         } else {
754                 if (dst_ll && (src_rate == dst_rate)) {
755                         return AST_TRANS_COST_LY_LL_ORIGSAMP;
756                 } else if (!dst_ll && (src_rate == dst_rate)) {
757                         return AST_TRANS_COST_LY_LY_ORIGSAMP;
758                 } else if (dst_ll && (src_rate < dst_rate)) {
759                         return AST_TRANS_COST_LY_LL_UPSAMP;
760                 } else if (!dst_ll && (src_rate < dst_rate)) {
761                         return AST_TRANS_COST_LY_LY_UPSAMP;
762                 } else if (dst_ll && (src_rate > dst_rate)) {
763                         return AST_TRANS_COST_LY_LL_DOWNSAMP;
764                 } else if (!dst_ll && (src_rate > dst_rate)) {
765                         return AST_TRANS_COST_LY_LY_DOWNSAMP;
766                 } else {
767                         return AST_TRANS_COST_LY_UNKNOWN;
768                 }
769         }
770 }
771
772 /*!
773  * \brief rebuild a translation matrix.
774  * \note This function expects the list of translators to be locked
775 */
776 static void matrix_rebuild(int samples)
777 {
778         struct ast_translator *t;
779         int newtablecost;
780         int x;      /* source format index */
781         int y;      /* intermediate format index */
782         int z;      /* destination format index */
783
784         ast_debug(1, "Resetting translation matrix\n");
785
786         matrix_clear();
787
788         /* first, compute all direct costs */
789         AST_RWLIST_TRAVERSE(&translators, t, list) {
790                 if (!t->active) {
791                         continue;
792                 }
793
794                 x = t->src_fmt_index;
795                 z = t->dst_fmt_index;
796
797                 if (samples) {
798                         generate_computational_cost(t, samples);
799                 }
800
801                 /* This new translator is the best choice if any of the below are true.
802                  * 1. no translation path is set between x and z yet.
803                  * 2. the new table cost is less.
804                  * 3. the new computational cost is less.  Computational cost is only used
805                  *    to break a tie between two identical translation paths.
806                  */
807                 if (!matrix_get(x, z)->step ||
808                         (t->table_cost < matrix_get(x, z)->step->table_cost) ||
809                         (t->comp_cost < matrix_get(x, z)->step->comp_cost)) {
810
811                         matrix_get(x, z)->step = t;
812                         matrix_get(x, z)->table_cost = t->table_cost;
813                 }
814         }
815
816         /*
817          * For each triple x, y, z of distinct formats, check if there is
818          * a path from x to z through y which is cheaper than what is
819          * currently known, and in case, update the matrix.
820          * Repeat until the matrix is stable.
821          */
822         for (;;) {
823                 int changed = 0;
824                 for (x = 0; x < cur_max_index; x++) {      /* source format */
825                         for (y = 0; y < cur_max_index; y++) {  /* intermediate format */
826                                 if (x == y) {                      /* skip ourselves */
827                                         continue;
828                                 }
829                                 for (z = 0; z < cur_max_index; z++) {  /* dst format */
830                                         if ((z == x || z == y) ||        /* skip null conversions */
831                                                 !matrix_get(x, y)->step ||   /* no path from x to y */
832                                                 !matrix_get(y, z)->step) {   /* no path from y to z */
833                                                 continue;
834                                         }
835
836                                         /* calculate table cost from x->y->z */
837                                         newtablecost = matrix_get(x, y)->table_cost + matrix_get(y, z)->table_cost;
838
839                                         /* if no step already exists between x and z OR the new cost of using the intermediate
840                                          * step is cheaper, use this step. */
841                                         if (!matrix_get(x, z)->step || (newtablecost < matrix_get(x, z)->table_cost)) {
842                                                 matrix_get(x, z)->step = matrix_get(x, y)->step;
843                                                 matrix_get(x, z)->table_cost = newtablecost;
844                                                 matrix_get(x, z)->multistep = 1;
845                                                 changed++;
846
847                                                 if (DEBUG_ATLEAST(10)) {
848                                                         struct ast_codec *x_codec = index2codec(x);
849                                                         struct ast_codec *y_codec = index2codec(y);
850                                                         struct ast_codec *z_codec = index2codec(z);
851
852                                                         ast_log(LOG_DEBUG,
853                                                                 "Discovered %u cost path from %s to %s, via %s\n",
854                                                                 matrix_get(x, z)->table_cost, x_codec->name,
855                                                                 y_codec->name, z_codec->name);
856
857                                                         ao2_ref(x_codec, -1);
858                                                         ao2_ref(y_codec, -1);
859                                                         ao2_ref(z_codec, -1);
860                                                 }
861                                         }
862                                 }
863                         }
864                 }
865                 if (!changed) {
866                         break;
867                 }
868         }
869 }
870
871 static void codec_append_name(const struct ast_codec *codec, struct ast_str **buf)
872 {
873         if (codec) {
874                 ast_str_append(buf, 0, "(%s@%u)", codec->name, codec->sample_rate);
875         } else {
876                 ast_str_append(buf, 0, "(nothing)");
877         }
878 }
879
880 const char *ast_translate_path_to_str(struct ast_trans_pvt *p, struct ast_str **str)
881 {
882         if (!p || !p->t) {
883                 return "";
884         }
885
886         ast_str_reset(*str);
887         codec_append_name(&p->t->src_codec, str);
888         while (p) {
889                 ast_str_append(str, 0, "->");
890                 codec_append_name(&p->t->dst_codec, str);
891                 p = p->next;
892         }
893
894         return ast_str_buffer(*str);
895 }
896
897 static char *complete_trans_path_choice(const char *line, const char *word, int pos, int state)
898 {
899         int i = 1, which = 0;
900         int wordlen = strlen(word);
901         struct ast_codec *codec;
902
903         while ((codec = ast_codec_get_by_id(i))) {
904                 ++i;
905                 if (codec->type != AST_MEDIA_TYPE_AUDIO) {
906                         ao2_ref(codec, -1);
907                         continue;
908                 }
909                 if (!strncasecmp(word, codec->name, wordlen) && ++which > state) {
910                         char *res = ast_strdup(codec->name);
911                         ao2_ref(codec, -1);
912                         return res;
913                 }
914                 ao2_ref(codec, -1);
915         }
916         return NULL;
917 }
918
919 static void handle_cli_recalc(struct ast_cli_args *a)
920 {
921         int time = a->argv[4] ? atoi(a->argv[4]) : 1;
922
923         if (time <= 0) {
924                 ast_cli(a->fd, "         Recalc must be greater than 0.  Defaulting to 1.\n");
925                 time = 1;
926         }
927
928         if (time > MAX_RECALC) {
929                 ast_cli(a->fd, "         Maximum limit of recalc exceeded by %d, truncating value to %d\n", time - MAX_RECALC, MAX_RECALC);
930                 time = MAX_RECALC;
931         }
932         ast_cli(a->fd, "         Recalculating Codec Translation (number of sample seconds: %d)\n\n", time);
933         AST_RWLIST_WRLOCK(&translators);
934         matrix_rebuild(time);
935         AST_RWLIST_UNLOCK(&translators);
936 }
937
938 static char *handle_show_translation_table(struct ast_cli_args *a)
939 {
940         int x, y, i, k;
941         int longest = 0, num_codecs = 0, curlen = 0;
942         struct ast_str *out = ast_str_create(1024);
943         struct ast_codec *codec;
944
945         /* Get the length of the longest (usable?) codec name,
946            so we know how wide the left side should be */
947         for (i = 1; (codec = ast_codec_get_by_id(i)); ao2_ref(codec, -1), ++i) {
948                 ++num_codecs;
949                 if (codec->type != AST_MEDIA_TYPE_AUDIO) {
950                         continue;
951                 }
952                 curlen = strlen(codec->name);
953                 if (curlen > longest) {
954                         longest = curlen;
955                 }
956         }
957
958         AST_RWLIST_RDLOCK(&translators);
959         ast_cli(a->fd, "         Translation times between formats (in microseconds) for one second of data\n");
960         ast_cli(a->fd, "          Source Format (Rows) Destination Format (Columns)\n\n");
961
962         for (i = 0; i < num_codecs; i++) {
963                 struct ast_codec *row = i ? ast_codec_get_by_id(i) : NULL;
964
965                 x = -1;
966                 if ((i > 0) && (row->type != AST_MEDIA_TYPE_AUDIO)) {
967                         ao2_ref(row, -1);
968                         continue;
969                 }
970
971                 if ((i > 0) && (x = codec2index(row)) == -1) {
972                         ao2_ref(row, -1);
973                         continue;
974                 }
975
976                 ast_str_set(&out, 0, " ");
977                 for (k = 0; k < num_codecs; k++) {
978                         struct ast_codec *col = k ? ast_codec_get_by_id(k) : NULL;
979
980                         y = -1;
981                         if ((k > 0) && (col->type != AST_MEDIA_TYPE_AUDIO)) {
982                                 ao2_ref(col, -1);
983                                 continue;
984                         }
985
986                         if ((k > 0) && (y = codec2index(col)) == -1) {
987                                 ao2_ref(col, -1);
988                                 continue;
989                         }
990
991                         if (k > 0) {
992                                 curlen = strlen(col->name);
993                         }
994
995                         if (curlen < 5) {
996                                 curlen = 5;
997                         }
998
999                         if (x >= 0 && y >= 0 && matrix_get(x, y)->step) {
1000                                 /* Actual codec output */
1001                                 ast_str_append(&out, 0, "%*u", curlen + 1, (matrix_get(x, y)->table_cost/100));
1002                         } else if (i == 0 && k > 0) {
1003                                 /* Top row - use a dynamic size */
1004                                 ast_str_append(&out, 0, "%*s", curlen + 1, col->name);
1005                         } else if (k == 0 && i > 0) {
1006                                 /* Left column - use a static size. */
1007                                 ast_str_append(&out, 0, "%*s", longest, row->name);
1008                         } else if (x >= 0 && y >= 0) {
1009                                 /* Codec not supported */
1010                                 ast_str_append(&out, 0, "%*s", curlen + 1, "-");
1011                         } else {
1012                                 /* Upper left hand corner */
1013                                 ast_str_append(&out, 0, "%*s", longest, "");
1014                         }
1015                         ao2_cleanup(col);
1016                 }
1017                 ast_str_append(&out, 0, "\n");
1018                 ast_cli(a->fd, "%s", ast_str_buffer(out));
1019                 ao2_cleanup(row);
1020         }
1021         ast_free(out);
1022         AST_RWLIST_UNLOCK(&translators);
1023         return CLI_SUCCESS;
1024 }
1025
1026 static char *handle_show_translation_path(struct ast_cli_args *a, const char *codec_name, unsigned int sample_rate)
1027 {
1028         int i = 1;
1029         struct ast_str *str = ast_str_alloca(1024);
1030         struct ast_translator *step;
1031         struct ast_codec *dst_codec;
1032         struct ast_codec *src_codec = ast_codec_get(codec_name, AST_MEDIA_TYPE_AUDIO, sample_rate);
1033
1034         if (!src_codec) {
1035                 ast_cli(a->fd, "Source codec \"%s\" is not found.\n", codec_name);
1036                 return CLI_FAILURE;
1037         }
1038
1039         AST_RWLIST_RDLOCK(&translators);
1040         ast_cli(a->fd, "--- Translation paths SRC Codec \"%s\" sample rate %u ---\n",
1041                 codec_name, src_codec->sample_rate);
1042
1043         while ((dst_codec = ast_codec_get_by_id(i))) {
1044                 int src, dst;
1045                 char src_buffer[64];
1046                 char dst_buffer[64];
1047
1048                 ++i;
1049                 if (src_codec == dst_codec ||
1050                     dst_codec->type != AST_MEDIA_TYPE_AUDIO) {
1051                         ao2_ref(dst_codec, -1);
1052                         continue;
1053                 }
1054
1055                 dst = codec2index(dst_codec);
1056                 src = codec2index(src_codec);
1057
1058                 if (src < 0 || dst < 0) {
1059                         ast_str_set(&str, 0, "No Translation Path");
1060                 } else {
1061                         step = matrix_get(src, dst)->step;
1062
1063                         if (step) {
1064                                 codec_append_name(&step->src_codec, &str);
1065                                 while (src != dst) {
1066                                         src = step->dst_fmt_index;
1067                                         step = matrix_get(src, dst)->step;
1068                                         if (!step) {
1069                                                 ast_str_append(&str, 0, "->");
1070                                                 codec_append_name(dst_codec, &str);
1071                                                 break;
1072                                         }
1073                                         ast_str_append(&str, 0, "->");
1074                                         codec_append_name(&step->src_codec, &str);
1075                                 }
1076                         }
1077                 }
1078
1079                 snprintf(src_buffer, sizeof(src_buffer), "%s:%u", src_codec->name, src_codec->sample_rate);
1080                 snprintf(dst_buffer, sizeof(dst_buffer), "%s:%u", dst_codec->name, dst_codec->sample_rate);
1081                 ast_cli(a->fd, "\t%-16.16s To %-16.16s: %-60.60s\n",
1082                         src_buffer, dst_buffer, ast_str_buffer(str));
1083                 ast_str_reset(str);
1084                 ao2_ref(dst_codec, -1);
1085         }
1086         AST_RWLIST_UNLOCK(&translators);
1087         ao2_ref(src_codec, -1);
1088         return CLI_SUCCESS;
1089 }
1090
1091 static char *handle_cli_core_show_translation(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
1092 {
1093         static const char * const option[] = { "recalc", "paths", NULL };
1094
1095         switch (cmd) {
1096         case CLI_INIT:
1097                 e->command = "core show translation";
1098                 e->usage =
1099                         "Usage: 'core show translation' can be used in two ways.\n"
1100                         "       1. 'core show translation [recalc [<recalc seconds>]]\n"
1101                         "          Displays known codec translators and the cost associated\n"
1102                         "          with each conversion.  If the argument 'recalc' is supplied along\n"
1103                         "          with optional number of seconds to test a new test will be performed\n"
1104                         "          as the chart is being displayed.\n"
1105                         "       2. 'core show translation paths [codec [sample_rate]]'\n"
1106                         "           This will display all the translation paths associated with a codec.\n"
1107                         "           If a codec has multiple sample rates, the sample rate must be\n"
1108                         "           provided as well.\n";
1109                 return NULL;
1110         case CLI_GENERATE:
1111                 if (a->pos == 3) {
1112                         return ast_cli_complete(a->word, option, a->n);
1113                 }
1114                 if (a->pos == 4 && !strcasecmp(a->argv[3], option[1])) {
1115                         return complete_trans_path_choice(a->line, a->word, a->pos, a->n);
1116                 }
1117                 /* BUGBUG - add tab completion for sample rates */
1118                 return NULL;
1119         }
1120
1121         if (a->argc > 6)
1122                 return CLI_SHOWUSAGE;
1123
1124         if (a->argv[3] && !strcasecmp(a->argv[3], option[1]) && a->argc == 5) { /* show paths */
1125                 return handle_show_translation_path(a, a->argv[4], 0);
1126         } else if (a->argv[3] && !strcasecmp(a->argv[3], option[1]) && a->argc == 6) {
1127                 unsigned int sample_rate;
1128                 if (sscanf(a->argv[5], "%30u", &sample_rate) != 1) {
1129                         ast_cli(a->fd, "Invalid sample rate: %s.\n", a->argv[5]);
1130                         return CLI_FAILURE;
1131                 }
1132                 return handle_show_translation_path(a, a->argv[4], sample_rate);
1133         } else if (a->argv[3] && !strcasecmp(a->argv[3], option[0])) { /* recalc and then fall through to show table */
1134                 handle_cli_recalc(a);
1135         } else if (a->argc > 3) { /* wrong input */
1136                 return CLI_SHOWUSAGE;
1137         }
1138
1139         return handle_show_translation_table(a);
1140 }
1141
1142 static struct ast_cli_entry cli_translate[] = {
1143         AST_CLI_DEFINE(handle_cli_core_show_translation, "Display translation matrix")
1144 };
1145
1146 /*! \brief register codec translator */
1147 int __ast_register_translator(struct ast_translator *t, struct ast_module *mod)
1148 {
1149         struct ast_translator *u;
1150         char tmp[80];
1151         RAII_VAR(struct ast_codec *, src_codec, NULL, ao2_cleanup);
1152         RAII_VAR(struct ast_codec *, dst_codec, NULL, ao2_cleanup);
1153
1154         src_codec = ast_codec_get(t->src_codec.name, t->src_codec.type, t->src_codec.sample_rate);
1155         if (!src_codec) {
1156                 ast_assert(0);
1157                 ast_log(LOG_WARNING, "Failed to register translator: unknown source codec %s\n", t->src_codec.name);
1158                 return -1;
1159         }
1160
1161         dst_codec = ast_codec_get(t->dst_codec.name, t->dst_codec.type, t->dst_codec.sample_rate);
1162         if (!dst_codec) {
1163                 ast_log(LOG_WARNING, "Failed to register translator: unknown destination codec %s\n", t->dst_codec.name);
1164                 return -1;
1165         }
1166
1167         if (add_codec2index(src_codec) || add_codec2index(dst_codec)) {
1168                 if (matrix_resize(0)) {
1169                         ast_log(LOG_WARNING, "Translator matrix can not represent any more translators.  Out of resources.\n");
1170                         return -1;
1171                 }
1172                 add_codec2index(src_codec);
1173                 add_codec2index(dst_codec);
1174         }
1175
1176         if (!mod) {
1177                 ast_log(LOG_WARNING, "Missing module pointer, you need to supply one\n");
1178                 return -1;
1179         }
1180
1181         if (!t->buf_size) {
1182                 ast_log(LOG_WARNING, "empty buf size, you need to supply one\n");
1183                 return -1;
1184         }
1185         if (!t->table_cost && !(t->table_cost = generate_table_cost(src_codec, dst_codec))) {
1186                 ast_log(LOG_WARNING, "Table cost could not be generated for %s, "
1187                         "Please set table_cost variable on translator.\n", t->name);
1188                 return -1;
1189         }
1190
1191         t->module = mod;
1192         t->src_fmt_index = codec2index(src_codec);
1193         t->dst_fmt_index = codec2index(dst_codec);
1194         t->active = 1;
1195
1196         if (t->src_fmt_index < 0 || t->dst_fmt_index < 0) {
1197                 ast_log(LOG_WARNING, "Invalid translator path: (%s codec is not valid)\n", t->src_fmt_index < 0 ? "starting" : "ending");
1198                 return -1;
1199         }
1200         if (t->src_fmt_index >= cur_max_index) {
1201                 ast_log(LOG_WARNING, "Source codec %s is larger than cur_max_index\n", t->src_codec.name);
1202                 return -1;
1203         }
1204
1205         if (t->dst_fmt_index >= cur_max_index) {
1206                 ast_log(LOG_WARNING, "Destination codec %s is larger than cur_max_index\n", t->dst_codec.name);
1207                 return -1;
1208         }
1209
1210         if (t->buf_size) {
1211                 /*
1212                  * Align buf_size properly, rounding up to the machine-specific
1213                  * alignment for pointers.
1214                  */
1215                 struct _test_align { void *a, *b; } p;
1216                 int align = (char *)&p.b - (char *)&p.a;
1217
1218                 t->buf_size = ((t->buf_size + align - 1) / align) * align;
1219         }
1220
1221         if (t->frameout == NULL) {
1222                 t->frameout = default_frameout;
1223         }
1224
1225         generate_computational_cost(t, 1);
1226
1227         ast_verb(2, "Registered translator '%s' from codec %s to %s, table cost, %d, computational cost %d\n",
1228                  term_color(tmp, t->name, COLOR_MAGENTA, COLOR_BLACK, sizeof(tmp)),
1229                  t->src_codec.name, t->dst_codec.name, t->table_cost, t->comp_cost);
1230
1231         AST_RWLIST_WRLOCK(&translators);
1232
1233         /* find any existing translators that provide this same srcfmt/dstfmt,
1234            and put this one in order based on computational cost */
1235         AST_RWLIST_TRAVERSE_SAFE_BEGIN(&translators, u, list) {
1236                 if ((u->src_fmt_index == t->src_fmt_index) &&
1237                     (u->dst_fmt_index == t->dst_fmt_index) &&
1238                     (u->comp_cost > t->comp_cost)) {
1239                         AST_RWLIST_INSERT_BEFORE_CURRENT(t, list);
1240                         t = NULL;
1241                         break;
1242                 }
1243         }
1244         AST_RWLIST_TRAVERSE_SAFE_END;
1245
1246         /* if no existing translator was found for this codec combination,
1247            add it to the beginning of the list */
1248         if (t) {
1249                 AST_RWLIST_INSERT_HEAD(&translators, t, list);
1250         }
1251
1252         matrix_rebuild(0);
1253
1254         AST_RWLIST_UNLOCK(&translators);
1255
1256         return 0;
1257 }
1258
1259 /*! \brief unregister codec translator */
1260 int ast_unregister_translator(struct ast_translator *t)
1261 {
1262         char tmp[80];
1263         struct ast_translator *u;
1264         int found = 0;
1265
1266         AST_RWLIST_WRLOCK(&translators);
1267         AST_RWLIST_TRAVERSE_SAFE_BEGIN(&translators, u, list) {
1268                 if (u == t) {
1269                         AST_RWLIST_REMOVE_CURRENT(list);
1270                         ast_verb(2, "Unregistered translator '%s' from codec %s to %s\n",
1271                                 term_color(tmp, t->name, COLOR_MAGENTA, COLOR_BLACK, sizeof(tmp)),
1272                                 t->src_codec.name, t->dst_codec.name);
1273                         found = 1;
1274                         break;
1275                 }
1276         }
1277         AST_RWLIST_TRAVERSE_SAFE_END;
1278
1279         if (found) {
1280                 matrix_rebuild(0);
1281         }
1282
1283         AST_RWLIST_UNLOCK(&translators);
1284
1285         return (u ? 0 : -1);
1286 }
1287
1288 void ast_translator_activate(struct ast_translator *t)
1289 {
1290         AST_RWLIST_WRLOCK(&translators);
1291         t->active = 1;
1292         matrix_rebuild(0);
1293         AST_RWLIST_UNLOCK(&translators);
1294 }
1295
1296 void ast_translator_deactivate(struct ast_translator *t)
1297 {
1298         AST_RWLIST_WRLOCK(&translators);
1299         t->active = 0;
1300         matrix_rebuild(0);
1301         AST_RWLIST_UNLOCK(&translators);
1302 }
1303
1304 /*! \brief Calculate our best translator source format, given costs, and a desired destination */
1305 int ast_translator_best_choice(struct ast_format_cap *dst_cap,
1306         struct ast_format_cap *src_cap,
1307         struct ast_format **dst_fmt_out,
1308         struct ast_format **src_fmt_out)
1309 {
1310         unsigned int besttablecost = INT_MAX;
1311         unsigned int beststeps = INT_MAX;
1312         struct ast_format *fmt;
1313         struct ast_format *dst;
1314         struct ast_format *src;
1315         RAII_VAR(struct ast_format *, best, NULL, ao2_cleanup);
1316         RAII_VAR(struct ast_format *, bestdst, NULL, ao2_cleanup);
1317         struct ast_format_cap *joint_cap;
1318         int i;
1319         int j;
1320
1321         if (ast_format_cap_empty(dst_cap) || ast_format_cap_empty(src_cap)) {
1322                 ast_log(LOG_ERROR, "Cannot determine best translation path since one capability supports no formats\n");
1323                 return -1;
1324         }
1325
1326         joint_cap = ast_format_cap_alloc(AST_FORMAT_CAP_FLAG_DEFAULT);
1327         if (!joint_cap) {
1328                 return -1;
1329         }
1330         ast_format_cap_get_compatible(dst_cap, src_cap, joint_cap);
1331
1332         for (i = 0; i < ast_format_cap_count(joint_cap); ++i, ao2_cleanup(fmt)) {
1333                 fmt = ast_format_cap_get_format(joint_cap, i);
1334                 if (!fmt
1335                         || ast_format_get_type(fmt) != AST_MEDIA_TYPE_AUDIO) {
1336                         continue;
1337                 }
1338
1339                 if (!best
1340                         || ast_format_get_sample_rate(best) < ast_format_get_sample_rate(fmt)) {
1341                         ao2_replace(best, fmt);
1342                 }
1343         }
1344         ao2_ref(joint_cap, -1);
1345
1346         if (best) {
1347                 ao2_replace(*dst_fmt_out, best);
1348                 ao2_replace(*src_fmt_out, best);
1349                 return 0;
1350         }
1351
1352         /* need to translate */
1353         AST_RWLIST_RDLOCK(&translators);
1354         for (i = 0; i < ast_format_cap_count(dst_cap); ++i, ao2_cleanup(dst)) {
1355                 dst = ast_format_cap_get_format(dst_cap, i);
1356                 if (!dst
1357                         || ast_format_get_type(dst) != AST_MEDIA_TYPE_AUDIO) {
1358                         continue;
1359                 }
1360
1361                 for (j = 0; j < ast_format_cap_count(src_cap); ++j, ao2_cleanup(src)) {
1362                         int x;
1363                         int y;
1364
1365                         src = ast_format_cap_get_format(src_cap, j);
1366                         if (!src
1367                                 || ast_format_get_type(src) != AST_MEDIA_TYPE_AUDIO) {
1368                                 continue;
1369                         }
1370
1371                         x = format2index(src);
1372                         y = format2index(dst);
1373                         if (x < 0 || y < 0) {
1374                                 continue;
1375                         }
1376                         if (!matrix_get(x, y) || !(matrix_get(x, y)->step)) {
1377                                 continue;
1378                         }
1379                         if (matrix_get(x, y)->table_cost < besttablecost
1380                                 || matrix_get(x, y)->multistep < beststeps) {
1381                                 /* better than what we have so far */
1382                                 ao2_replace(best, src);
1383                                 ao2_replace(bestdst, dst);
1384                                 besttablecost = matrix_get(x, y)->table_cost;
1385                                 beststeps = matrix_get(x, y)->multistep;
1386                         }
1387                 }
1388         }
1389         AST_RWLIST_UNLOCK(&translators);
1390
1391         if (!best) {
1392                 return -1;
1393         }
1394         ao2_replace(*dst_fmt_out, bestdst);
1395         ao2_replace(*src_fmt_out, best);
1396         return 0;
1397 }
1398
1399 unsigned int ast_translate_path_steps(struct ast_format *dst_format, struct ast_format *src_format)
1400 {
1401         unsigned int res = -1;
1402         /* convert bitwise format numbers into array indices */
1403         int src = format2index(src_format);
1404         int dest = format2index(dst_format);
1405
1406         if (src < 0 || dest < 0) {
1407                 ast_log(LOG_WARNING, "No translator path: (%s codec is not valid)\n", src < 0 ? "starting" : "ending");
1408                 return -1;
1409         }
1410         AST_RWLIST_RDLOCK(&translators);
1411
1412         if (matrix_get(src, dest)->step) {
1413                 res = matrix_get(src, dest)->multistep + 1;
1414         }
1415
1416         AST_RWLIST_UNLOCK(&translators);
1417
1418         return res;
1419 }
1420
1421 static void check_translation_path(
1422         struct ast_format_cap *dest, struct ast_format_cap *src,
1423         struct ast_format_cap *result, struct ast_format *src_fmt,
1424         enum ast_media_type type)
1425 {
1426         int index, src_index = format2index(src_fmt);
1427         /* For a given source format, traverse the list of
1428            known formats to determine whether there exists
1429            a translation path from the source format to the
1430            destination format. */
1431         for (index = 0; (src_index >= 0) && index < cur_max_index; index++) {
1432                 struct ast_codec *codec = index2codec(index);
1433                 RAII_VAR(struct ast_format *, fmt, ast_format_create(codec), ao2_cleanup);
1434
1435                 ao2_ref(codec, -1);
1436
1437                 if (ast_format_get_type(fmt) != type) {
1438                         continue;
1439                 }
1440
1441                 /* if this is not a desired format, nothing to do */
1442                 if (ast_format_cap_iscompatible_format(dest, fmt) == AST_FORMAT_CMP_NOT_EQUAL) {
1443                         continue;
1444                 }
1445
1446                 /* if the source is supplying this format, then
1447                    we can leave it in the result */
1448                 if (ast_format_cap_iscompatible_format(src, fmt) == AST_FORMAT_CMP_EQUAL) {
1449                         continue;
1450                 }
1451
1452                 /* if we don't have a translation path from the src
1453                    to this format, remove it from the result */
1454                 if (!matrix_get(src_index, index)->step) {
1455                         ast_format_cap_remove(result, fmt);
1456                         continue;
1457                 }
1458
1459                 /* now check the opposite direction */
1460                 if (!matrix_get(index, src_index)->step) {
1461                         ast_format_cap_remove(result, fmt);
1462                 }
1463         }
1464
1465 }
1466
1467 void ast_translate_available_formats(struct ast_format_cap *dest, struct ast_format_cap *src, struct ast_format_cap *result)
1468 {
1469         struct ast_format *cur_dest, *cur_src;
1470         int index;
1471
1472         for (index = 0; index < ast_format_cap_count(dest); ++index) {
1473                 if (!(cur_dest = ast_format_cap_get_format(dest, index))) {
1474                         continue;
1475                 }
1476
1477                 /* We give preference to a joint format structure if possible */
1478                 if ((cur_src = ast_format_cap_get_compatible_format(src, cur_dest))) {
1479                         ast_format_cap_append(result, cur_src, 0);
1480                         ao2_ref(cur_src, -1);
1481                 } else {
1482                         /* Otherwise we just use the destination format */
1483                         ast_format_cap_append(result, cur_dest, 0);
1484                 }
1485                 ao2_ref(cur_dest, -1);
1486         }
1487
1488         /* if we don't have a source format, we just have to try all
1489            possible destination formats */
1490         if (!src) {
1491                 return;
1492         }
1493
1494         for (index = 0; index < ast_format_cap_count(src); ++index) {
1495                 if (!(cur_src = ast_format_cap_get_format(src, index))) {
1496                         continue;
1497                 }
1498
1499                 AST_RWLIST_RDLOCK(&translators);
1500                 check_translation_path(dest, src, result,
1501                                        cur_src, AST_MEDIA_TYPE_AUDIO);
1502                 check_translation_path(dest, src, result,
1503                                        cur_src, AST_MEDIA_TYPE_VIDEO);
1504                 AST_RWLIST_UNLOCK(&translators);
1505                 ao2_ref(cur_src, -1);
1506         }
1507 }
1508
1509 static void translate_shutdown(void)
1510 {
1511         int x;
1512         ast_cli_unregister_multiple(cli_translate, ARRAY_LEN(cli_translate));
1513
1514         ast_rwlock_wrlock(&tablelock);
1515         for (x = 0; x < index_size; x++) {
1516                 ast_free(__matrix[x]);
1517         }
1518         ast_free(__matrix);
1519         __matrix = NULL;
1520         ast_free(__indextable);
1521         __indextable = NULL;
1522         ast_rwlock_unlock(&tablelock);
1523         ast_rwlock_destroy(&tablelock);
1524 }
1525
1526 int ast_translate_init(void)
1527 {
1528         int res = 0;
1529         ast_rwlock_init(&tablelock);
1530         res = matrix_resize(1);
1531         res |= ast_cli_register_multiple(cli_translate, ARRAY_LEN(cli_translate));
1532         ast_register_cleanup(translate_shutdown);
1533         return res;
1534 }