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