1ebbc1ff67d8d2640a229ab7e1687042c51765a5
[asterisk/asterisk.git] / 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 <sys/types.h>
27 #include <sys/socket.h>
28 #include <sys/time.h>
29 #include <unistd.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include <stdio.h>
33
34 #include "asterisk.h"
35
36 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
37
38 #include "asterisk/lock.h"
39 #include "asterisk/channel.h"
40 #include "asterisk/logger.h"
41 #include "asterisk/translate.h"
42 #include "asterisk/options.h"
43 #include "asterisk/frame.h"
44 #include "asterisk/sched.h"
45 #include "asterisk/cli.h"
46 #include "asterisk/term.h"
47
48 #define MAX_RECALC 200 /* max sample recalc */
49
50 /*! \note
51    This could all be done more efficiently *IF* we chained packets together
52    by default, but it would also complicate virtually every application. */
53    
54 static AST_LIST_HEAD_STATIC(translators, ast_translator);
55
56 struct ast_translator_dir {
57         struct ast_translator *step;    /*!< Next step translator */
58         unsigned int cost;              /*!< Complete cost to destination */
59         unsigned int multistep;         /*!< Multiple conversions required for this translation */
60 };
61
62 struct ast_frame_delivery {
63         struct ast_frame *f;
64         struct ast_channel *chan;
65         int fd;
66         struct translator_pvt *owner;
67         struct ast_frame_delivery *prev;
68         struct ast_frame_delivery *next;
69 };
70
71 static struct ast_translator_dir tr_matrix[MAX_FORMAT][MAX_FORMAT];
72
73 struct ast_trans_pvt {
74         struct ast_translator *step;
75         struct ast_translator_pvt *state;
76         struct ast_trans_pvt *next;
77         struct timeval nextin;
78         struct timeval nextout;
79 };
80
81
82 static int powerof(int d)
83 {
84         int x;
85         for (x = 0; x < 32; x++)
86                 if ((1 << x) & d)
87                         return x;
88         ast_log(LOG_WARNING, "Powerof %d: No power??\n", d);
89         return -1;
90 }
91
92 void ast_translator_free_path(struct ast_trans_pvt *p)
93 {
94         struct ast_trans_pvt *pl, *pn;
95         pn = p;
96         while(pn) {
97                 pl = pn;
98                 pn = pn->next;
99                 if (pl->state && pl->step->destroy)
100                         pl->step->destroy(pl->state);
101                 free(pl);
102         }
103 }
104
105 /*! Build a set of translators based upon the given source and destination formats */
106 struct ast_trans_pvt *ast_translator_build_path(int dest, int source)
107 {
108         struct ast_trans_pvt *tmpr = NULL, *tmp = NULL;
109         
110         source = powerof(source);
111         dest = powerof(dest);
112         
113         while(source != dest) {
114                 if (!tr_matrix[source][dest].step) {
115                         /* We shouldn't have allocated any memory */
116                         ast_log(LOG_WARNING, "No translator path from %s to %s\n", 
117                                 ast_getformatname(source), ast_getformatname(dest));
118                         return NULL;
119                 }
120
121                 if (tmp) {
122                         tmp->next = malloc(sizeof(*tmp));
123                         tmp = tmp->next;
124                 } else
125                         tmp = malloc(sizeof(*tmp));
126                         
127                 if (!tmp) {
128                         ast_log(LOG_WARNING, "Out of memory\n");
129                         if (tmpr)
130                                 ast_translator_free_path(tmpr); 
131                         return NULL;
132                 }
133
134                 /* Set the root, if it doesn't exist yet... */
135                 if (!tmpr)
136                         tmpr = tmp;
137
138                 tmp->next = NULL;
139                 tmp->nextin = tmp->nextout = ast_tv(0, 0);
140                 tmp->step = tr_matrix[source][dest].step;
141                 tmp->state = tmp->step->newpvt();
142                 
143                 if (!tmp->state) {
144                         ast_log(LOG_WARNING, "Failed to build translator step from %d to %d\n", source, dest);
145                         ast_translator_free_path(tmpr); 
146                         return NULL;
147                 }
148                 
149                 /* Keep going if this isn't the final destination */
150                 source = tmp->step->dstfmt;
151         }
152         return tmpr;
153 }
154
155 struct ast_frame *ast_translate(struct ast_trans_pvt *path, struct ast_frame *f, int consume)
156 {
157         struct ast_trans_pvt *p;
158         struct ast_frame *out;
159         struct timeval delivery;
160         p = path;
161         /* Feed the first frame into the first translator */
162         p->step->framein(p->state, f);
163         if (!ast_tvzero(f->delivery)) {
164                 if (!ast_tvzero(path->nextin)) {
165                         /* Make sure this is in line with what we were expecting */
166                         if (!ast_tveq(path->nextin, f->delivery)) {
167                                 /* The time has changed between what we expected and this
168                                    most recent time on the new packet.  If we have a
169                                    valid prediction adjust our output time appropriately */
170                                 if (!ast_tvzero(path->nextout)) {
171                                         path->nextout = ast_tvadd(path->nextout,
172                                                                   ast_tvsub(f->delivery, path->nextin));
173                                 }
174                                 path->nextin = f->delivery;
175                         }
176                 } else {
177                         /* This is our first pass.  Make sure the timing looks good */
178                         path->nextin = f->delivery;
179                         path->nextout = f->delivery;
180                 }
181                 /* Predict next incoming sample */
182                 path->nextin = ast_tvadd(path->nextin, ast_samp2tv(f->samples, 8000));
183         }
184         delivery = f->delivery;
185         if (consume)
186                 ast_frfree(f);
187         while(p) {
188                 out = p->step->frameout(p->state);
189                 /* If we get nothing out, return NULL */
190                 if (!out)
191                         return NULL;
192                 /* If there is a next state, feed it in there.  If not,
193                    return this frame  */
194                 if (p->next) 
195                         p->next->step->framein(p->next->state, out);
196                 else {
197                         if (!ast_tvzero(delivery)) {
198                                 /* Regenerate prediction after a discontinuity */
199                                 if (ast_tvzero(path->nextout))
200                                         path->nextout = ast_tvnow();
201
202                                 /* Use next predicted outgoing timestamp */
203                                 out->delivery = path->nextout;
204                                 
205                                 /* Predict next outgoing timestamp from samples in this
206                                    frame. */
207                                 path->nextout = ast_tvadd(path->nextout, ast_samp2tv( out->samples, 8000));
208                         } else {
209                                 out->delivery = ast_tv(0, 0);
210                         }
211                         /* Invalidate prediction if we're entering a silence period */
212                         if (out->frametype == AST_FRAME_CNG)
213                                 path->nextout = ast_tv(0, 0);
214                         return out;
215                 }
216                 p = p->next;
217         }
218         ast_log(LOG_WARNING, "I should never get here...\n");
219         return NULL;
220 }
221
222
223 static void calc_cost(struct ast_translator *t, int samples)
224 {
225         int sofar=0;
226         struct ast_translator_pvt *pvt;
227         struct ast_frame *f, *out;
228         struct timeval start;
229         int cost;
230
231         if(!samples)
232                 samples = 1;
233         
234         /* If they don't make samples, give them a terrible score */
235         if (!t->sample) {
236                 ast_log(LOG_WARNING, "Translator '%s' does not produce sample frames.\n", t->name);
237                 t->cost = 99999;
238                 return;
239         }
240         pvt = t->newpvt();
241         if (!pvt) {
242                 ast_log(LOG_WARNING, "Translator '%s' appears to be broken and will probably fail.\n", t->name);
243                 t->cost = 99999;
244                 return;
245         }
246         start = ast_tvnow();
247         /* Call the encoder until we've processed one second of time */
248         while(sofar < samples * 8000) {
249                 f = t->sample();
250                 if (!f) {
251                         ast_log(LOG_WARNING, "Translator '%s' failed to produce a sample frame.\n", t->name);
252                         t->destroy(pvt);
253                         t->cost = 99999;
254                         return;
255                 }
256                 t->framein(pvt, f);
257                 ast_frfree(f);
258                 while((out = t->frameout(pvt))) {
259                         sofar += out->samples;
260                         ast_frfree(out);
261                 }
262         }
263         cost = ast_tvdiff_ms(ast_tvnow(), start);
264         t->destroy(pvt);
265         t->cost = cost / samples;
266         if (!t->cost)
267                 t->cost = 1;
268 }
269
270 /*! 
271   \brief Use the list of translators to build a translation matrix
272
273   \note This function expects the list of translators to be locked
274 */
275 static void rebuild_matrix(int samples)
276 {
277         struct ast_translator *t;
278         int changed;
279         int x, y, z;
280
281         if (option_debug)
282                 ast_log(LOG_DEBUG, "Resetting translation matrix\n");
283
284         bzero(tr_matrix, sizeof(tr_matrix));
285
286         AST_LIST_TRAVERSE(&translators, t, list) {
287                 if (samples)
288                         calc_cost(t, samples);
289           
290                 if (!tr_matrix[t->srcfmt][t->dstfmt].step ||
291                     tr_matrix[t->srcfmt][t->dstfmt].cost > t->cost) {
292                         tr_matrix[t->srcfmt][t->dstfmt].step = t;
293                         tr_matrix[t->srcfmt][t->dstfmt].cost = t->cost;
294                 }
295         }
296
297         do {
298                 changed = 0;
299
300                 /* Don't you just love O(N^3) operations? */
301                 for (x = 0; x< MAX_FORMAT; x++) {                       /* For each source format */
302                         for (y = 0; y < MAX_FORMAT; y++) {              /* And each destination format */
303                                 if (x == y)                             /* Except ourselves, of course */
304                                         continue;
305
306                                 for (z=0; z < MAX_FORMAT; z++) {        /* And each format it might convert to */
307                                         if ((x == z) || (y == z))       /* Don't ever convert back to us */
308                                                 continue;
309
310                                         if (tr_matrix[x][y].step &&     /* We can convert from x to y */
311                                             tr_matrix[y][z].step &&     /* And from y to z and... */
312                                             (!tr_matrix[x][z].step ||   /* Either there isn't an x->z conversion */
313                                              (tr_matrix[x][y].cost + 
314                                               tr_matrix[y][z].cost <    /* Or we're cheaper than the existing */
315                                               tr_matrix[x][z].cost)     /* solution */
316                                                     )) {
317                                                 /* We can get from x to z via y with a cost that
318                                                    is the sum of the transition from x to y and
319                                                    from y to z */
320                                                 
321                                                 tr_matrix[x][z].step = tr_matrix[x][y].step;
322                                                 tr_matrix[x][z].cost = tr_matrix[x][y].cost + 
323                                                         tr_matrix[y][z].cost;
324                                                 tr_matrix[x][z].multistep = 1;
325                                                 if (option_debug)
326                                                         ast_log(LOG_DEBUG, "Discovered %d cost path from %s to %s, via %d\n", tr_matrix[x][z].cost, ast_getformatname(x), ast_getformatname(z), y);
327                                                 changed++;
328                                         }
329                                 }
330                         }
331                 }
332         } while (changed);
333 }
334
335
336 /*! \brief CLI "show translation" command handler */
337 static int show_translation(int fd, int argc, char *argv[])
338 {
339 #define SHOW_TRANS 11
340         int x, y, z;
341         char line[80];
342         if (argc > 4) 
343                 return RESULT_SHOWUSAGE;
344
345         AST_LIST_LOCK(&translators);    
346         
347         if (argv[2] && !strcasecmp(argv[2],"recalc")) {
348                 z = argv[3] ? atoi(argv[3]) : 1;
349
350                 if (z <= 0) {
351                         ast_cli(fd,"         C'mon let's be serious here... defaulting to 1.\n");
352                         z = 1;
353                 }
354
355                 if (z > MAX_RECALC) {
356                         ast_cli(fd,"         Maximum limit of recalc exceeded by %d, truncating value to %d\n",z-MAX_RECALC,MAX_RECALC);
357                         z = MAX_RECALC;
358                 }
359                 ast_cli(fd,"         Recalculating Codec Translation (number of sample seconds: %d)\n\n",z);
360                 rebuild_matrix(z);
361         }
362
363         ast_cli(fd, "         Translation times between formats (in milliseconds)\n");
364         ast_cli(fd, "          Source Format (Rows) Destination Format(Columns)\n\n");
365         for (x = -1; x < SHOW_TRANS; x++) {
366                 /* next 2 lines run faster than using strcpy() */
367                 line[0] = ' ';
368                 line[1] = '\0';
369                 for (y=-1;y<SHOW_TRANS;y++) {
370                         if (x >= 0 && y >= 0 && tr_matrix[x][y].step)
371                                 snprintf(line + strlen(line), sizeof(line) - strlen(line), " %5d", tr_matrix[x][y].cost >= 99999 ? tr_matrix[x][y].cost-99999 : tr_matrix[x][y].cost);
372                         else
373                                 if (((x == -1 && y >= 0) || (y == -1 && x >= 0))) {
374                                         snprintf(line + strlen(line), sizeof(line) - strlen(line), 
375                                                 " %5s", ast_getformatname(1<<(x+y+1)) );
376                                 } else if (x != -1 && y != -1) {
377                                         snprintf(line + strlen(line), sizeof(line) - strlen(line), "     -");
378                                 } else {
379                                         snprintf(line + strlen(line), sizeof(line) - strlen(line), "      ");
380                                 }
381                 }
382                 snprintf(line + strlen(line), sizeof(line) - strlen(line), "\n");
383                 ast_cli(fd, line);                      
384         }
385         AST_LIST_UNLOCK(&translators);
386         return RESULT_SUCCESS;
387 }
388
389 static int added_cli = 0;
390
391 static char show_trans_usage[] =
392 "Usage: show translation [recalc] [<recalc seconds>]\n"
393 "       Displays known codec translators and the cost associated\n"
394 "with each conversion.  If the argument 'recalc' is supplied along\n"
395 "with optional number of seconds to test a new test will be performed\n"
396 "as the chart is being displayed.\n";
397
398 static struct ast_cli_entry show_trans =
399 { { "show", "translation", NULL }, show_translation, "Display translation matrix", show_trans_usage };
400
401 int ast_register_translator(struct ast_translator *t)
402 {
403         char tmp[80];
404         t->srcfmt = powerof(t->srcfmt);
405         t->dstfmt = powerof(t->dstfmt);
406         if (t->srcfmt >= MAX_FORMAT) {
407                 ast_log(LOG_WARNING, "Source format %s is larger than MAX_FORMAT\n", ast_getformatname(t->srcfmt));
408                 return -1;
409         }
410         if (t->dstfmt >= MAX_FORMAT) {
411                 ast_log(LOG_WARNING, "Destination format %s is larger than MAX_FORMAT\n", ast_getformatname(t->dstfmt));
412                 return -1;
413         }
414         calc_cost(t,1);
415         if (option_verbose > 1)
416                 ast_verbose(VERBOSE_PREFIX_2 "Registered translator '%s' from format %s to %s, cost %d\n", term_color(tmp, t->name, COLOR_MAGENTA, COLOR_BLACK, sizeof(tmp)), ast_getformatname(1 << t->srcfmt), ast_getformatname(1 << t->dstfmt), t->cost);
417         AST_LIST_LOCK(&translators);
418         if (!added_cli) {
419                 ast_cli_register(&show_trans);
420                 added_cli++;
421         }
422         AST_LIST_INSERT_HEAD(&translators, t, list);
423         rebuild_matrix(0);
424         AST_LIST_UNLOCK(&translators);
425         return 0;
426 }
427
428 /*! \brief unregister codec translator */
429 int ast_unregister_translator(struct ast_translator *t)
430 {
431         char tmp[80];
432         struct ast_translator *u;
433         AST_LIST_LOCK(&translators);
434         AST_LIST_TRAVERSE_SAFE_BEGIN(&translators, u, list) {
435                 if (u == t) {
436                         AST_LIST_REMOVE_CURRENT(&translators, list);
437                         if (option_verbose > 1)
438                                 ast_verbose(VERBOSE_PREFIX_2 "Unregistered translator '%s' from format %s to %s\n", term_color(tmp, t->name, COLOR_MAGENTA, COLOR_BLACK, sizeof(tmp)), ast_getformatname(1 << t->srcfmt), ast_getformatname(1 << t->dstfmt));
439                         break;
440                 }
441         }
442         AST_LIST_TRAVERSE_SAFE_END
443         rebuild_matrix(0);
444         AST_LIST_UNLOCK(&translators);
445         return (u ? 0 : -1);
446 }
447
448 /*! \brief Calculate our best translator source format, given costs, and a desired destination */
449 int ast_translator_best_choice(int *dst, int *srcs)
450 {
451         int x,y;
452         int best = -1;
453         int bestdst = 0;
454         int cur = 1;
455         int besttime = INT_MAX;
456         int beststeps = INT_MAX;
457         int common;
458
459         if ((common = (*dst) & (*srcs))) {
460                 /* We have a format in common */
461                 for (y = 0; y < MAX_FORMAT; y++) {
462                         if (cur & common) {
463                                 /* This is a common format to both.  Pick it if we don't have one already */
464                                 bestdst = cur;
465                                 best = cur;
466                         }
467                         cur = cur << 1;
468                 }
469         } else {
470                 /* We will need to translate */
471                 AST_LIST_LOCK(&translators);
472                 for (y = 0; y < MAX_FORMAT; y++) {
473                         if (!(cur & *dst)) {
474                                 cur = cur << 1;
475                                 continue;
476                         }
477
478                         for (x = 0; x < MAX_FORMAT; x++) {
479                                 if ((*srcs & (1 << x)) &&                       /* x is a valid source format */
480                                     tr_matrix[x][y].step) {                     /* There's a step */
481                                         if (tr_matrix[x][y].cost > besttime)
482                                                 continue;                       /* It's more expensive, skip it */
483                                         
484                                         if (tr_matrix[x][y].cost == besttime &&
485                                             tr_matrix[x][y].multistep >= beststeps)
486                                                 continue;                       /* It requires the same (or more) steps,
487                                                                                    skip it */
488
489                                         /* It's better than what we have so far */
490                                         best = 1 << x;
491                                         bestdst = cur;
492                                         besttime = tr_matrix[x][y].cost;
493                                         beststeps = tr_matrix[x][y].multistep;
494                                 }
495                         }
496                         cur = cur << 1;
497                 }
498                 AST_LIST_UNLOCK(&translators);
499         }
500
501         if (best > -1) {
502                 *srcs = best;
503                 *dst = bestdst;
504                 best = 0;
505         }
506
507         return best;
508 }