Merged revisions 282047 via svnmerge from
[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 #include "asterisk.h"
27
28 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
29
30 #include <sys/time.h>
31 #include <sys/resource.h>
32 #include <math.h>
33
34 #include "asterisk/lock.h"
35 #include "asterisk/channel.h"
36 #include "asterisk/translate.h"
37 #include "asterisk/module.h"
38 #include "asterisk/frame.h"
39 #include "asterisk/sched.h"
40 #include "asterisk/cli.h"
41 #include "asterisk/term.h"
42
43 #define MAX_RECALC 1000 /* max sample recalc */
44
45 /*! \brief the list of translators */
46 static AST_RWLIST_HEAD_STATIC(translators, ast_translator);
47
48
49 /*! \brief these values indicate how a translation path will affect the sample rate
50  *
51  *  \note These must stay in this order.  They are ordered by most optimal selection first.
52  */
53 enum path_samp_change {
54         RATE_CHANGE_NONE = 0, /*!< path uses the same sample rate consistently */
55         RATE_CHANGE_UPSAMP = 1, /*!< path will up the sample rate during a translation */
56         RATE_CHANGE_DOWNSAMP = 2, /*!< path will have to down the sample rate during a translation. */
57         RATE_CHANGE_UPSAMP_DOWNSAMP = 3, /*!< path will both up and down the sample rate during translation */
58 };
59
60 struct translator_path {
61         struct ast_translator *step;    /*!< Next step translator */
62         unsigned int cost;              /*!< Complete cost to destination */
63         unsigned int multistep;         /*!< Multiple conversions required for this translation */
64         enum path_samp_change rate_change; /*!< does this path require a sample rate change, if so what kind. */
65 };
66
67 /*! \brief a matrix that, for any pair of supported formats,
68  * indicates the total cost of translation and the first step.
69  * The full path can be reconstricted iterating on the matrix
70  * until step->dstfmt == desired_format.
71  *
72  * Array indexes are 'src' and 'dest', in that order.
73  *
74  * Note: the lock in the 'translators' list is also used to protect
75  * this structure.
76  */
77 static struct translator_path tr_matrix[MAX_FORMAT][MAX_FORMAT];
78
79 /*! \todo
80  * TODO: sample frames for each supported input format.
81  * We build this on the fly, by taking an SLIN frame and using
82  * the existing converter to play with it.
83  */
84
85 /*! \brief returns the index of the lowest bit set */
86 static force_inline int powerof(format_t d)
87 {
88         int x = ffsll(d);
89
90         if (x)
91                 return x - 1;
92
93         ast_log(LOG_WARNING, "No bits set? %llu\n", (unsigned long long) d);
94
95         return -1;
96 }
97
98 /*
99  * wrappers around the translator routines.
100  */
101
102 /*!
103  * \brief Allocate the descriptor, required outbuf space,
104  * and possibly desc.
105  */
106 static void *newpvt(struct ast_translator *t)
107 {
108         struct ast_trans_pvt *pvt;
109         int len;
110         char *ofs;
111
112         /*
113          * compute the required size adding private descriptor,
114          * buffer, AST_FRIENDLY_OFFSET.
115          */
116         len = sizeof(*pvt) + t->desc_size;
117         if (t->buf_size)
118                 len += AST_FRIENDLY_OFFSET + t->buf_size;
119         pvt = ast_calloc(1, len);
120         if (!pvt)
121                 return NULL;
122         pvt->t = t;
123         ofs = (char *)(pvt + 1);        /* pointer to data space */
124         if (t->desc_size) {             /* first comes the descriptor */
125                 pvt->pvt = ofs;
126                 ofs += t->desc_size;
127         }
128         if (t->buf_size)                /* finally buffer and header */
129                 pvt->outbuf.c = ofs + AST_FRIENDLY_OFFSET;
130         /* call local init routine, if present */
131         if (t->newpvt && t->newpvt(pvt)) {
132                 ast_free(pvt);
133                 return NULL;
134         }
135         ast_module_ref(t->module);
136         return pvt;
137 }
138
139 static void destroy(struct ast_trans_pvt *pvt)
140 {
141         struct ast_translator *t = pvt->t;
142
143         if (t->destroy)
144                 t->destroy(pvt);
145         ast_free(pvt);
146         ast_module_unref(t->module);
147 }
148
149 /*! \brief framein wrapper, deals with bound checks.  */
150 static int framein(struct ast_trans_pvt *pvt, struct ast_frame *f)
151 {
152         int ret;
153         int samples = pvt->samples;     /* initial value */
154         
155         /* Copy the last in jb timing info to the pvt */
156         ast_copy_flags(&pvt->f, f, AST_FRFLAG_HAS_TIMING_INFO);
157         pvt->f.ts = f->ts;
158         pvt->f.len = f->len;
159         pvt->f.seqno = f->seqno;
160
161         if (f->samples == 0) {
162                 ast_log(LOG_WARNING, "no samples for %s\n", pvt->t->name);
163         }
164         if (pvt->t->buffer_samples) {   /* do not pass empty frames to callback */
165                 if (f->datalen == 0) { /* perform native PLC if available */
166                         /* If the codec has native PLC, then do that */
167                         if (!pvt->t->native_plc)
168                                 return 0;
169                 }
170                 if (pvt->samples + f->samples > pvt->t->buffer_samples) {
171                         ast_log(LOG_WARNING, "Out of buffer space\n");
172                         return -1;
173                 }
174         }
175         /* we require a framein routine, wouldn't know how to do
176          * it otherwise.
177          */
178         ret = pvt->t->framein(pvt, f);
179         /* diagnostic ... */
180         if (pvt->samples == samples)
181                 ast_log(LOG_WARNING, "%s did not update samples %d\n",
182                         pvt->t->name, pvt->samples);
183         return ret;
184 }
185
186 /*! \brief generic frameout routine.
187  * If samples and datalen are 0, take whatever is in pvt
188  * and reset them, otherwise take the values in the caller and
189  * leave alone the pvt values.
190  */
191 struct ast_frame *ast_trans_frameout(struct ast_trans_pvt *pvt,
192         int datalen, int samples)
193 {
194         struct ast_frame *f = &pvt->f;
195
196         if (samples)
197                 f->samples = samples;
198         else {
199                 if (pvt->samples == 0)
200                         return NULL;
201                 f->samples = pvt->samples;
202                 pvt->samples = 0;
203         }
204         if (datalen)
205                 f->datalen = datalen;
206         else {
207                 f->datalen = pvt->datalen;
208                 pvt->datalen = 0;
209         }
210
211         f->frametype = AST_FRAME_VOICE;
212         f->subclass.codec = 1LL << (pvt->t->dstfmt);
213         f->mallocd = 0;
214         f->offset = AST_FRIENDLY_OFFSET;
215         f->src = pvt->t->name;
216         f->data.ptr = pvt->outbuf.c;
217
218         return ast_frisolate(f);
219 }
220
221 static struct ast_frame *default_frameout(struct ast_trans_pvt *pvt)
222 {
223         return ast_trans_frameout(pvt, 0, 0);
224 }
225
226 /* end of callback wrappers and helpers */
227
228 void ast_translator_free_path(struct ast_trans_pvt *p)
229 {
230         struct ast_trans_pvt *pn = p;
231         while ( (p = pn) ) {
232                 pn = p->next;
233                 destroy(p);
234         }
235 }
236
237 /*! \brief Build a chain of translators based upon the given source and dest formats */
238 struct ast_trans_pvt *ast_translator_build_path(format_t dest, format_t source)
239 {
240         struct ast_trans_pvt *head = NULL, *tail = NULL;
241         
242         source = powerof(source);
243         dest = powerof(dest);
244
245         if (source == -1 || dest == -1) {
246                 ast_log(LOG_WARNING, "No translator path: (%s codec is not valid)\n", source == -1 ? "starting" : "ending");
247                 return NULL;
248         }
249
250         AST_RWLIST_RDLOCK(&translators);
251
252         while (source != dest) {
253                 struct ast_trans_pvt *cur;
254                 struct ast_translator *t = tr_matrix[source][dest].step;
255                 if (!t) {
256                         ast_log(LOG_WARNING, "No translator path from %s to %s\n", 
257                                 ast_getformatname(source), ast_getformatname(dest));
258                         AST_RWLIST_UNLOCK(&translators);
259                         return NULL;
260                 }
261                 if (!(cur = newpvt(t))) {
262                         ast_log(LOG_WARNING, "Failed to build translator step from %s to %s\n",
263                                 ast_getformatname(source), ast_getformatname(dest));
264                         if (head)
265                                 ast_translator_free_path(head); 
266                         AST_RWLIST_UNLOCK(&translators);
267                         return NULL;
268                 }
269                 if (!head)
270                         head = cur;
271                 else
272                         tail->next = cur;
273                 tail = cur;
274                 cur->nextin = cur->nextout = ast_tv(0, 0);
275                 /* Keep going if this isn't the final destination */
276                 source = cur->t->dstfmt;
277         }
278
279         AST_RWLIST_UNLOCK(&translators);
280         return head;
281 }
282
283 /*! \brief do the actual translation */
284 struct ast_frame *ast_translate(struct ast_trans_pvt *path, struct ast_frame *f, int consume)
285 {
286         struct ast_trans_pvt *p = path;
287         struct ast_frame *out = f;
288         struct timeval delivery;
289         int has_timing_info;
290         long ts;
291         long len;
292         int seqno;
293
294         has_timing_info = ast_test_flag(f, AST_FRFLAG_HAS_TIMING_INFO);
295         ts = f->ts;
296         len = f->len;
297         seqno = f->seqno;
298
299         /* XXX hmmm... check this below */
300         if (!ast_tvzero(f->delivery)) {
301                 if (!ast_tvzero(path->nextin)) {
302                         /* Make sure this is in line with what we were expecting */
303                         if (!ast_tveq(path->nextin, f->delivery)) {
304                                 /* The time has changed between what we expected and this
305                                    most recent time on the new packet.  If we have a
306                                    valid prediction adjust our output time appropriately */
307                                 if (!ast_tvzero(path->nextout)) {
308                                         path->nextout = ast_tvadd(path->nextout,
309                                                                   ast_tvsub(f->delivery, path->nextin));
310                                 }
311                                 path->nextin = f->delivery;
312                         }
313                 } else {
314                         /* This is our first pass.  Make sure the timing looks good */
315                         path->nextin = f->delivery;
316                         path->nextout = f->delivery;
317                 }
318                 /* Predict next incoming sample */
319                 path->nextin = ast_tvadd(path->nextin, ast_samp2tv(f->samples, ast_format_rate(f->subclass.codec)));
320         }
321         delivery = f->delivery;
322         for ( ; out && p ; p = p->next) {
323                 framein(p, out);
324                 if (out != f)
325                         ast_frfree(out);
326                 out = p->t->frameout(p);
327         }
328         if (consume)
329                 ast_frfree(f);
330         if (out == NULL)
331                 return NULL;
332         /* we have a frame, play with times */
333         if (!ast_tvzero(delivery)) {
334                 /* Regenerate prediction after a discontinuity */
335                 if (ast_tvzero(path->nextout))
336                         path->nextout = ast_tvnow();
337
338                 /* Use next predicted outgoing timestamp */
339                 out->delivery = path->nextout;
340                 
341                 /* Predict next outgoing timestamp from samples in this
342                    frame. */
343                 path->nextout = ast_tvadd(path->nextout, ast_samp2tv(out->samples, ast_format_rate(out->subclass.codec)));
344         } else {
345                 out->delivery = ast_tv(0, 0);
346                 ast_set2_flag(out, has_timing_info, AST_FRFLAG_HAS_TIMING_INFO);
347                 if (has_timing_info) {
348                         out->ts = ts;
349                         out->len = len;
350                         out->seqno = seqno;
351                 }
352         }
353         /* Invalidate prediction if we're entering a silence period */
354         if (out->frametype == AST_FRAME_CNG)
355                 path->nextout = ast_tv(0, 0);
356         return out;
357 }
358
359 /*! \brief compute the cost of a single translation step */
360 static void calc_cost(struct ast_translator *t, int seconds)
361 {
362         int num_samples = 0;
363         struct ast_trans_pvt *pvt;
364         struct rusage start;
365         struct rusage end;
366         int cost;
367         int out_rate = ast_format_rate(t->dstfmt);
368
369         if (!seconds)
370                 seconds = 1;
371         
372         /* If they don't make samples, give them a terrible score */
373         if (!t->sample) {
374                 ast_log(LOG_WARNING, "Translator '%s' does not produce sample frames.\n", t->name);
375                 t->cost = 999999;
376                 return;
377         }
378
379         pvt = newpvt(t);
380         if (!pvt) {
381                 ast_log(LOG_WARNING, "Translator '%s' appears to be broken and will probably fail.\n", t->name);
382                 t->cost = 999999;
383                 return;
384         }
385
386         getrusage(RUSAGE_SELF, &start);
387
388         /* Call the encoder until we've processed the required number of samples */
389         while (num_samples < seconds * out_rate) {
390                 struct ast_frame *f = t->sample();
391                 if (!f) {
392                         ast_log(LOG_WARNING, "Translator '%s' failed to produce a sample frame.\n", t->name);
393                         destroy(pvt);
394                         t->cost = 999999;
395                         return;
396                 }
397                 framein(pvt, f);
398                 ast_frfree(f);
399                 while ((f = t->frameout(pvt))) {
400                         num_samples += f->samples;
401                         ast_frfree(f);
402                 }
403         }
404
405         getrusage(RUSAGE_SELF, &end);
406
407         cost = ((end.ru_utime.tv_sec - start.ru_utime.tv_sec) * 1000000) + end.ru_utime.tv_usec - start.ru_utime.tv_usec;
408         cost += ((end.ru_stime.tv_sec - start.ru_stime.tv_sec) * 1000000) + end.ru_stime.tv_usec - start.ru_stime.tv_usec;
409
410         destroy(pvt);
411
412         t->cost = cost / seconds;
413
414         if (!t->cost)
415                 t->cost = 1;
416 }
417
418 static enum path_samp_change get_rate_change_result(format_t src, format_t dst)
419 {
420         int src_rate = ast_format_rate(src);
421         int dst_rate = ast_format_rate(dst);
422
423         /* if src rate is less than dst rate, a sample upgrade is required */
424         if (src_rate < dst_rate) {
425                 return RATE_CHANGE_UPSAMP;
426         }
427
428         /* if src rate is larger than dst rate, a downgrade is required */
429         if (src_rate > dst_rate) {
430                 return RATE_CHANGE_DOWNSAMP;
431         }
432
433         return RATE_CHANGE_NONE;
434 }
435
436 /*!
437  * \brief rebuild a translation matrix.
438  * \note This function expects the list of translators to be locked
439 */
440 static void rebuild_matrix(int samples)
441 {
442         struct ast_translator *t;
443         int new_rate_change;
444         int newcost;
445         int x;      /* source format index */
446         int y;      /* intermediate format index */
447         int z;      /* destination format index */
448
449         ast_debug(1, "Resetting translation matrix\n");
450
451         memset(tr_matrix, '\0', sizeof(tr_matrix));
452
453         /* first, compute all direct costs */
454         AST_RWLIST_TRAVERSE(&translators, t, list) {
455                 if (!t->active)
456                         continue;
457
458                 x = t->srcfmt;
459                 z = t->dstfmt;
460
461                 if (samples)
462                         calc_cost(t, samples);
463
464                 new_rate_change = get_rate_change_result(1LL << t->srcfmt, 1LL << t->dstfmt);
465
466                 /* this translator is the best choice if any of the below are true.
467                  * 1. no translation path is set between x and z yet.
468                  * 2. the new translation costs less and sample rate is no worse than old one. 
469                  * 3. the new translation has a better sample rate conversion than the old one.
470                  */
471                 if (!tr_matrix[x][z].step ||
472                         ((t->cost < tr_matrix[x][z].cost) && (new_rate_change <= tr_matrix[x][z].rate_change)) ||
473                         (new_rate_change < tr_matrix[x][z].rate_change)) {
474
475                         tr_matrix[x][z].step = t;
476                         tr_matrix[x][z].cost = t->cost;
477                         tr_matrix[x][z].rate_change = new_rate_change;
478                 }
479         }
480
481         /*
482          * For each triple x, y, z of distinct formats, check if there is
483          * a path from x to z through y which is cheaper than what is
484          * currently known, and in case, update the matrix.
485          * Repeat until the matrix is stable.
486          */
487         for (;;) {
488                 int changed = 0;
489                 int better_choice = 0;
490                 for (x = 0; x < MAX_FORMAT; x++) {      /* source format */
491                         for (y = 0; y < MAX_FORMAT; y++) {    /* intermediate format */
492                                 if (x == y)                     /* skip ourselves */
493                                         continue;
494                                 for (z = 0; z < MAX_FORMAT; z++) {  /* dst format */
495                                         if (z == x || z == y)       /* skip null conversions */
496                                                 continue;
497                                         if (!tr_matrix[x][y].step)  /* no path from x to y */
498                                                 continue;
499                                         if (!tr_matrix[y][z].step)  /* no path from y to z */
500                                                 continue;
501
502                                         /* Does x->y->z result in a less optimal sample rate change?
503                                          * Never downgrade the sample rate conversion quality regardless
504                                          * of any cost improvements */
505                                         if (tr_matrix[x][z].step &&
506                                                 ((tr_matrix[x][z].rate_change < tr_matrix[x][y].rate_change) ||
507                                                 (tr_matrix[x][z].rate_change < tr_matrix[y][z].rate_change))) {
508                                                 continue;
509                                         }
510
511                                         /* is x->y->z a better sample rate confersion that the current x->z? */
512                                         new_rate_change = tr_matrix[x][y].rate_change + tr_matrix[y][z].rate_change;
513
514                                         /* calculate cost from x->y->z */
515                                         newcost = tr_matrix[x][y].cost + tr_matrix[y][z].cost;
516
517                                         /* Is x->y->z a better choice than x->z?
518                                          * There are three conditions for x->y->z to be a better choice than x->z
519                                          * 1. if there is no step directly between x->z then x->y->z is the best and only current option.
520                                          * 2. if x->y->z costs less and the sample rate conversion is no less optimal.
521                                          * 3. if x->y->z results in a more optimal sample rate conversion. */
522                                         if (!tr_matrix[x][z].step) {
523                                                 better_choice = 1;
524                                         } else if ((newcost < tr_matrix[x][z].cost) && (new_rate_change <= tr_matrix[x][z].rate_change)) {
525                                                 better_choice = 1;
526                                         } else if (new_rate_change < tr_matrix[x][z].rate_change) {
527                                                 better_choice = 1;
528                                         } else {
529                                                 better_choice = 0;
530                                         }
531
532                                         if (!better_choice) {
533                                                 continue;
534                                         }
535                                         /* ok, we can get from x to z via y with a cost that
536                                            is the sum of the transition from x to y and from y to z */
537                                         tr_matrix[x][z].step = tr_matrix[x][y].step;
538                                         tr_matrix[x][z].cost = newcost;
539                                         tr_matrix[x][z].multistep = 1;
540
541                                         /* now calculate what kind of sample rate change is required for this multi-step path
542                                          * 
543                                          * if both paths require a change in rate, and they are not in the same direction
544                                          * then this is a up sample down sample conversion scenario. */
545                                         if ((tr_matrix[x][y].rate_change > RATE_CHANGE_NONE) &&
546                                                 (tr_matrix[y][z].rate_change > RATE_CHANGE_NONE) &&
547                                                 (tr_matrix[x][y].rate_change != tr_matrix[y][z].rate_change)) {
548
549                                                 tr_matrix[x][z].rate_change = RATE_CHANGE_UPSAMP_DOWNSAMP;
550                                         } else {
551                                                 /* else just set the rate change to whichever is worse */
552                                                 tr_matrix[x][z].rate_change = tr_matrix[x][y].rate_change > tr_matrix[y][z].rate_change
553                                                         ? tr_matrix[x][y].rate_change : tr_matrix[y][z].rate_change;
554                                         }
555
556                                         ast_debug(3, "Discovered %d cost path from %s to %s, via %s\n", tr_matrix[x][z].cost,
557                                                   ast_getformatname(1LL << x), ast_getformatname(1LL << z), ast_getformatname(1LL << y));
558                                         changed++;
559                                 }
560                         }
561                 }
562                 if (!changed)
563                         break;
564         }
565 }
566
567 const char *ast_translate_path_to_str(struct ast_trans_pvt *p, struct ast_str **str)
568 {
569         struct ast_trans_pvt *pn = p;
570
571         if (!p || !p->t) {
572                 return "";
573         }
574
575         ast_str_set(str, 0, "%s", ast_getformatname(1LL << p->t->srcfmt));
576
577         while ( (p = pn) ) {
578                 pn = p->next;
579                 ast_str_append(str, 0, "->%s", ast_getformatname(1LL << p->t->dstfmt));
580         }
581
582         return ast_str_buffer(*str);
583 }
584
585 static char *complete_trans_path_choice(const char *line, const char *word, int pos, int state)
586 {
587         int which = 0;
588         int wordlen = strlen(word);
589         int i;
590         char *ret = NULL;
591         size_t len = 0;
592         const struct ast_format_list *format_list = ast_get_format_list(&len);
593
594         for (i = 0; i < len; i++) {
595                 if (!(format_list[i].bits & AST_FORMAT_AUDIO_MASK)) {
596                         continue;
597                 }
598                 if (!strncasecmp(word, format_list[i].name, wordlen) && ++which > state) {
599                         ret = ast_strdup(format_list[i].name);
600                         break;
601                 }
602         }
603         return ret;
604 }
605
606 static char *handle_cli_core_show_translation(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
607 {
608 #define SHOW_TRANS 64
609         static const char * const option1[] = { "recalc", "paths", NULL };
610         int x, y, z;
611         int curlen = 0, longest = 0, magnitude[SHOW_TRANS] = { 0, };
612
613         switch (cmd) {
614         case CLI_INIT:
615                 e->command = "core show translation";
616                 e->usage =
617                         "Usage: 'core show translation' can be used in two ways.\n"
618                         "       1. 'core show translation [recalc [<recalc seconds>]]\n"
619                         "          Displays known codec translators and the cost associated\n"
620                         "          with each conversion.  If the argument 'recalc' is supplied along\n"
621                         "          with optional number of seconds to test a new test will be performed\n"
622                         "          as the chart is being displayed.\n"
623                         "       2. 'core show translation paths [codec]'\n"
624                         "           This will display all the translation paths associated with a codec\n";
625                 return NULL;
626         case CLI_GENERATE:
627                 if (a->pos == 3) {
628                         return ast_cli_complete(a->word, option1, a->n);
629                 }
630                 if (a->pos == 4 && !strcasecmp(a->argv[3], option1[1])) {
631                         return complete_trans_path_choice(a->line, a->word, a->pos, a->n);
632                 }
633                 return NULL;
634         }
635
636         if (a->argc > 5)
637                 return CLI_SHOWUSAGE;
638
639         if (a->argv[3] && !strcasecmp(a->argv[3], option1[1]) && a->argc == 5) {
640                 format_t input_src = 0;
641                 format_t src = 0;
642                 size_t len = 0;
643                 int dst;
644                 int i;
645                 const struct ast_format_list *format_list = ast_get_format_list(&len);
646                 struct ast_str *str = ast_str_alloca(256);
647                 struct ast_translator *step;
648
649                 for (i = 0; i < len; i++) {
650                         if (!(format_list[i].bits & AST_FORMAT_AUDIO_MASK)) {
651                                 continue;
652                         }
653                         if (!strncasecmp(format_list[i].name, a->argv[4], strlen(format_list[i].name))) {
654                                 input_src = format_list[i].bits;
655                         }
656                 }
657
658                 if (!input_src) {
659                         ast_cli(a->fd, "Source codec \"%s\" is not found.\n", a->argv[4]);
660                         return CLI_FAILURE;
661                 }
662
663                 AST_RWLIST_RDLOCK(&translators);
664                 ast_cli(a->fd, "--- Translation paths SRC Codec \"%s\" sample rate %d ---\n", a->argv[4], ast_format_rate(input_src));
665                 for (i = 0; i < len; i++) {
666                         if (!(format_list[i].bits & AST_FORMAT_AUDIO_MASK) || (format_list[i].bits == input_src)) {
667                                 continue;
668                         }
669                         dst = powerof(format_list[i].bits);
670                         src = powerof(input_src);
671                         ast_str_reset(str);
672                         if (tr_matrix[src][dst].step) {
673                                 ast_str_append(&str, 0, "%s", ast_getformatname(1LL << tr_matrix[src][dst].step->srcfmt));
674                                 while (src != dst) {
675                                         step = tr_matrix[src][dst].step;
676                                         if (!step) {
677                                                 ast_str_reset(str);
678                                                 break;
679                                         }
680                                         ast_str_append(&str, 0, "->%s", ast_getformatname(1LL << step->dstfmt));
681                                         src = step->dstfmt;
682                                 }
683                         }
684
685                         if (ast_strlen_zero(ast_str_buffer(str))) {
686                                 ast_str_set(&str, 0, "No Translation Path");
687                         }
688
689                         ast_cli(a->fd, "\t%-10.10s To %-10.10s: %-60.60s\n", a->argv[4], format_list[i].name, ast_str_buffer(str));
690                 }
691                 AST_RWLIST_UNLOCK(&translators);
692
693                 return CLI_SUCCESS;
694         } else if (a->argv[3] && !strcasecmp(a->argv[3], "recalc")) {
695                 z = a->argv[4] ? atoi(a->argv[4]) : 1;
696
697                 if (z <= 0) {
698                         ast_cli(a->fd, "         Recalc must be greater than 0.  Defaulting to 1.\n");
699                         z = 1;
700                 }
701
702                 if (z > MAX_RECALC) {
703                         ast_cli(a->fd, "         Maximum limit of recalc exceeded by %d, truncating value to %d\n", z - MAX_RECALC, MAX_RECALC);
704                         z = MAX_RECALC;
705                 }
706                 ast_cli(a->fd, "         Recalculating Codec Translation (number of sample seconds: %d)\n\n", z);
707                 AST_RWLIST_WRLOCK(&translators);
708                 rebuild_matrix(z);
709                 AST_RWLIST_UNLOCK(&translators);
710         } else if (a->argc > 3)
711                 return CLI_SHOWUSAGE;
712
713         AST_RWLIST_RDLOCK(&translators);
714
715         ast_cli(a->fd, "         Translation times between formats (in microseconds) for one second of data\n");
716         ast_cli(a->fd, "          Source Format (Rows) Destination Format (Columns)\n\n");
717         /* Get the length of the longest (usable?) codec name, so we know how wide the left side should be */
718         for (x = 0; x < SHOW_TRANS; x++) {
719                 /* translation only applies to audio right now. */
720                 if (!(AST_FORMAT_AUDIO_MASK & (1LL << (x))))
721                         continue;
722                 curlen = strlen(ast_getformatname(1LL << (x)));
723                 if (curlen > longest)
724                         longest = curlen;
725                 for (y = 0; y < SHOW_TRANS; y++) {
726                         if (!(AST_FORMAT_AUDIO_MASK & (1LL << (y))))
727                                 continue;
728                         if (tr_matrix[x][y].cost > pow(10, magnitude[x])) {
729                                 magnitude[y] = floor(log10(tr_matrix[x][y].cost));
730                         }
731                 }
732         }
733         for (x = -1; x < SHOW_TRANS; x++) {
734                 struct ast_str *out = ast_str_alloca(256);
735                 /* translation only applies to audio right now. */
736                 if (x >= 0 && !(AST_FORMAT_AUDIO_MASK & (1LL << (x))))
737                         continue;
738                 /*Go ahead and move to next iteration if dealing with an unknown codec*/
739                 if(x >= 0 && !strcmp(ast_getformatname(1LL << (x)), "unknown"))
740                         continue;
741                 ast_str_set(&out, -1, " ");
742                 for (y = -1; y < SHOW_TRANS; y++) {
743                         /* translation only applies to audio right now. */
744                         if (y >= 0 && !(AST_FORMAT_AUDIO_MASK & (1LL << (y))))
745                                 continue;
746                         /*Go ahead and move to next iteration if dealing with an unknown codec*/
747                         if (y >= 0 && !strcmp(ast_getformatname(1LL << (y)), "unknown"))
748                                 continue;
749                         if (y >= 0)
750                                 curlen = strlen(ast_getformatname(1LL << (y)));
751                         if (y >= 0 && magnitude[y] + 1 > curlen) {
752                                 curlen = magnitude[y] + 1;
753                         }
754                         if (curlen < 5)
755                                 curlen = 5;
756                         if (x >= 0 && y >= 0 && tr_matrix[x][y].step) {
757                                 /* Actual codec output */
758                                 ast_str_append(&out, -1, "%*d", curlen + 1, tr_matrix[x][y].cost);
759                         } else if (x == -1 && y >= 0) {
760                                 /* Top row - use a dynamic size */
761                                 ast_str_append(&out, -1, "%*s", curlen + 1, ast_getformatname(1LL << (y)) );
762                         } else if (y == -1 && x >= 0) {
763                                 /* Left column - use a static size. */
764                                 ast_str_append(&out, -1, "%*s", longest, ast_getformatname(1LL << (x)) );
765                         } else if (x >= 0 && y >= 0) {
766                                 /* Codec not supported */
767                                 ast_str_append(&out, -1, "%*s", curlen + 1, "-");
768                         } else {
769                                 /* Upper left hand corner */
770                                 ast_str_append(&out, -1, "%*s", longest, "");
771                         }
772                 }
773                 ast_str_append(&out, -1, "\n");
774                 ast_cli(a->fd, "%s", ast_str_buffer(out));
775         }
776         AST_RWLIST_UNLOCK(&translators);
777         return CLI_SUCCESS;
778 }
779
780 static struct ast_cli_entry cli_translate[] = {
781         AST_CLI_DEFINE(handle_cli_core_show_translation, "Display translation matrix")
782 };
783
784 /*! \brief register codec translator */
785 int __ast_register_translator(struct ast_translator *t, struct ast_module *mod)
786 {
787         static int added_cli = 0;
788         struct ast_translator *u;
789         char tmp[80];
790
791         if (!mod) {
792                 ast_log(LOG_WARNING, "Missing module pointer, you need to supply one\n");
793                 return -1;
794         }
795
796         if (!t->buf_size) {
797                 ast_log(LOG_WARNING, "empty buf size, you need to supply one\n");
798                 return -1;
799         }
800
801         t->module = mod;
802
803         t->srcfmt = powerof(t->srcfmt);
804         t->dstfmt = powerof(t->dstfmt);
805         t->active = 1;
806
807         if (t->srcfmt == -1 || t->dstfmt == -1) {
808                 ast_log(LOG_WARNING, "Invalid translator path: (%s codec is not valid)\n", t->srcfmt == -1 ? "starting" : "ending");
809                 return -1;
810         }
811         if (t->srcfmt >= MAX_FORMAT) {
812                 ast_log(LOG_WARNING, "Source format %s is larger than MAX_FORMAT\n", ast_getformatname(t->srcfmt));
813                 return -1;
814         }
815
816         if (t->dstfmt >= MAX_FORMAT) {
817                 ast_log(LOG_WARNING, "Destination format %s is larger than MAX_FORMAT\n", ast_getformatname(t->dstfmt));
818                 return -1;
819         }
820
821         if (t->buf_size) {
822                 /*
823                  * Align buf_size properly, rounding up to the machine-specific
824                  * alignment for pointers.
825                  */
826                 struct _test_align { void *a, *b; } p;
827                 int align = (char *)&p.b - (char *)&p.a;
828
829                 t->buf_size = ((t->buf_size + align - 1) / align) * align;
830         }
831
832         if (t->frameout == NULL)
833                 t->frameout = default_frameout;
834   
835         calc_cost(t, 1);
836
837         ast_verb(2, "Registered translator '%s' from format %s to %s, cost %d\n",
838                             term_color(tmp, t->name, COLOR_MAGENTA, COLOR_BLACK, sizeof(tmp)),
839                             ast_getformatname(1LL << t->srcfmt), ast_getformatname(1LL << t->dstfmt), t->cost);
840
841         if (!added_cli) {
842                 ast_cli_register_multiple(cli_translate, ARRAY_LEN(cli_translate));
843                 added_cli++;
844         }
845
846         AST_RWLIST_WRLOCK(&translators);
847
848         /* find any existing translators that provide this same srcfmt/dstfmt,
849            and put this one in order based on cost */
850         AST_RWLIST_TRAVERSE_SAFE_BEGIN(&translators, u, list) {
851                 if ((u->srcfmt == t->srcfmt) &&
852                     (u->dstfmt == t->dstfmt) &&
853                     (u->cost > t->cost)) {
854                         AST_RWLIST_INSERT_BEFORE_CURRENT(t, list);
855                         t = NULL;
856                         break;
857                 }
858         }
859         AST_RWLIST_TRAVERSE_SAFE_END;
860
861         /* if no existing translator was found for this format combination,
862            add it to the beginning of the list */
863         if (t)
864                 AST_RWLIST_INSERT_HEAD(&translators, t, list);
865
866         rebuild_matrix(0);
867
868         AST_RWLIST_UNLOCK(&translators);
869
870         return 0;
871 }
872
873 /*! \brief unregister codec translator */
874 int ast_unregister_translator(struct ast_translator *t)
875 {
876         char tmp[80];
877         struct ast_translator *u;
878         int found = 0;
879
880         AST_RWLIST_WRLOCK(&translators);
881         AST_RWLIST_TRAVERSE_SAFE_BEGIN(&translators, u, list) {
882                 if (u == t) {
883                         AST_RWLIST_REMOVE_CURRENT(list);
884                         ast_verb(2, "Unregistered translator '%s' from format %s to %s\n", term_color(tmp, t->name, COLOR_MAGENTA, COLOR_BLACK, sizeof(tmp)), ast_getformatname(1LL << t->srcfmt), ast_getformatname(1LL << t->dstfmt));
885                         found = 1;
886                         break;
887                 }
888         }
889         AST_RWLIST_TRAVERSE_SAFE_END;
890
891         if (found)
892                 rebuild_matrix(0);
893
894         AST_RWLIST_UNLOCK(&translators);
895
896         return (u ? 0 : -1);
897 }
898
899 void ast_translator_activate(struct ast_translator *t)
900 {
901         AST_RWLIST_WRLOCK(&translators);
902         t->active = 1;
903         rebuild_matrix(0);
904         AST_RWLIST_UNLOCK(&translators);
905 }
906
907 void ast_translator_deactivate(struct ast_translator *t)
908 {
909         AST_RWLIST_WRLOCK(&translators);
910         t->active = 0;
911         rebuild_matrix(0);
912         AST_RWLIST_UNLOCK(&translators);
913 }
914
915 /*! \brief Calculate our best translator source format, given costs, and a desired destination */
916 format_t ast_translator_best_choice(format_t *dst, format_t *srcs)
917 {
918         int x,y;
919         int better = 0;
920         int besttime = INT_MAX;
921         int beststeps = INT_MAX;
922         unsigned int best_rate_change = INT_MAX;
923         format_t best = -1;
924         format_t bestdst = 0;
925         format_t cur, cursrc;
926         format_t common = ((*dst) & (*srcs)) & AST_FORMAT_AUDIO_MASK;   /* are there common formats ? */
927
928         if (common) { /* yes, pick one and return */
929                 for (cur = 1, y = 0; y <= MAX_AUDIO_FORMAT; cur <<= 1, y++) {
930                         if (!(cur & common)) {
931                                 continue;
932                         }
933
934                         /* We are guaranteed to find one common format. */
935                         if (best == -1) {
936                                 best = cur;
937                                 continue;
938                         }
939                         /* If there are multiple common formats, pick the one with the highest sample rate */
940                         if (ast_format_rate(best) < ast_format_rate(cur)) {
941                                 best = cur;
942                                 continue;
943                         }
944                 }
945                 /* We are done, this is a common format to both. */
946                 *srcs = *dst = best;
947                 return 0;
948         } else {      /* No, we will need to translate */
949                 AST_RWLIST_RDLOCK(&translators);
950                 for (cur = 1, y = 0; y <= MAX_AUDIO_FORMAT; cur <<= 1, y++) {
951                         if (! (cur & *dst)) {
952                                 continue;
953                         }
954                         for (cursrc = 1, x = 0; x <= MAX_AUDIO_FORMAT; cursrc <<= 1, x++) {
955                                 if (!(*srcs & cursrc) || !tr_matrix[x][y].step) {
956                                         continue;
957                                 }
958
959                                 /* This is a better choice if any of the following are true.
960                                  * 1. The sample rate conversion is better than the current pick.
961                                  * 2. the sample rate conversion is no worse than the current pick and the cost or multistep is better
962                                  */
963                                 better = 0;
964                                 if (tr_matrix[x][y].rate_change < best_rate_change) {
965                                         better = 1; /* this match has a better rate conversion */
966                                 }
967                                 if ((tr_matrix[x][y].rate_change <= best_rate_change) &&
968                                         (tr_matrix[x][y].cost < besttime || tr_matrix[x][y].multistep < beststeps)) {
969                                         better = 1; /* this match has no worse rate conversion and the conversion cost is less */
970                                 }
971                                 if (better) {
972                                         /* better than what we have so far */
973                                         best = cursrc;
974                                         bestdst = cur;
975                                         besttime = tr_matrix[x][y].cost;
976                                         beststeps = tr_matrix[x][y].multistep;
977                                         best_rate_change = tr_matrix[x][y].rate_change;
978                                 }
979                         }
980                 }
981                 AST_RWLIST_UNLOCK(&translators);
982                 if (best > -1) {
983                         *srcs = best;
984                         *dst = bestdst;
985                         best = 0;
986                 }
987                 return best;
988         }
989 }
990
991 unsigned int ast_translate_path_steps(format_t dest, format_t src)
992 {
993         unsigned int res = -1;
994
995         /* convert bitwise format numbers into array indices */
996         src = powerof(src);
997         dest = powerof(dest);
998
999         if (src == -1 || dest == -1) {
1000                 ast_log(LOG_WARNING, "No translator path: (%s codec is not valid)\n", src == -1 ? "starting" : "ending");
1001                 return -1;
1002         }
1003         AST_RWLIST_RDLOCK(&translators);
1004
1005         if (tr_matrix[src][dest].step)
1006                 res = tr_matrix[src][dest].multistep + 1;
1007
1008         AST_RWLIST_UNLOCK(&translators);
1009
1010         return res;
1011 }
1012
1013 format_t ast_translate_available_formats(format_t dest, format_t src)
1014 {
1015         format_t res = dest;
1016         format_t x;
1017         format_t src_audio = src & AST_FORMAT_AUDIO_MASK;
1018         format_t src_video = src & AST_FORMAT_VIDEO_MASK;
1019
1020         /* if we don't have a source format, we just have to try all
1021            possible destination formats */
1022         if (!src)
1023                 return dest;
1024
1025         /* If we have a source audio format, get its format index */
1026         if (src_audio)
1027                 src_audio = powerof(src_audio);
1028
1029         /* If we have a source video format, get its format index */
1030         if (src_video)
1031                 src_video = powerof(src_video);
1032
1033         AST_RWLIST_RDLOCK(&translators);
1034
1035         /* For a given source audio format, traverse the list of
1036            known audio formats to determine whether there exists
1037            a translation path from the source format to the
1038            destination format. */
1039         for (x = 1LL; src_audio && x > 0; x <<= 1) {
1040                 if (!(x & AST_FORMAT_AUDIO_MASK)) {
1041                         continue;
1042                 }
1043
1044                 /* if this is not a desired format, nothing to do */
1045                 if (!(dest & x))
1046                         continue;
1047
1048                 /* if the source is supplying this format, then
1049                    we can leave it in the result */
1050                 if (src & x)
1051                         continue;
1052
1053                 /* if we don't have a translation path from the src
1054                    to this format, remove it from the result */
1055                 if (!tr_matrix[src_audio][powerof(x)].step) {
1056                         res &= ~x;
1057                         continue;
1058                 }
1059
1060                 /* now check the opposite direction */
1061                 if (!tr_matrix[powerof(x)][src_audio].step)
1062                         res &= ~x;
1063         }
1064
1065         /* For a given source video format, traverse the list of
1066            known video formats to determine whether there exists
1067            a translation path from the source format to the
1068            destination format. */
1069         for (x = 1LL; src_video && x > 0; x <<= 1) {
1070                 if (!(x & AST_FORMAT_VIDEO_MASK)) {
1071                         continue;
1072                 }
1073
1074                 /* if this is not a desired format, nothing to do */
1075                 if (!(dest & x))
1076                         continue;
1077
1078                 /* if the source is supplying this format, then
1079                    we can leave it in the result */
1080                 if (src & x)
1081                         continue;
1082
1083                 /* if we don't have a translation path from the src
1084                    to this format, remove it from the result */
1085                 if (!tr_matrix[src_video][powerof(x)].step) {
1086                         res &= ~x;
1087                         continue;
1088                 }
1089
1090                 /* now check the opposite direction */
1091                 if (!tr_matrix[powerof(x)][src_video].step)
1092                         res &= ~x;
1093         }
1094
1095         AST_RWLIST_UNLOCK(&translators);
1096
1097         return res;
1098 }