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