scheduler/filter.c

   1 /*
   2  * File type conversion routines for CUPS.
   3  *
   4  * Copyright 2007-2011 by Apple Inc.
   5  * Copyright 1997-2007 by Easy Software Products, all rights reserved.
   6  *
   7  * These coded instructions, statements, and computer programs are the
   8  * property of Apple Inc. and are protected by Federal copyright
   9  * law.  Distribution and use rights are outlined in the file "LICENSE.txt"
  10  * which should have been included with this file.  If this file is
  11  * missing or damaged, see the license at "http://www.cups.org/".
  12  */
  13
  14 /*
  15  * Include necessary headers...
  16  */
  17
  18 #include <cups/string-private.h>
  19 #include <cups/debug-private.h>
  20 #include "mime.h"
  21
  22
  23 /*
  24  * Local types...
  25  */
  26
  27 typedef struct _mime_typelist_s         /**** List of source types ****/
  28 {
  29   struct _mime_typelist_s *next;        /* Next source type */
  30   mime_type_t           *src;           /* Source type */
  31 } _mime_typelist_t;
  32
  33
  34 /*
  35  * Local functions...
  36  */
  37
  38 static int              mime_compare_filters(mime_filter_t *, mime_filter_t *);
  39 static int              mime_compare_srcs(mime_filter_t *, mime_filter_t *);
  40 static cups_array_t     *mime_find_filters(mime_t *mime, mime_type_t *src,
  41                                       size_t srcsize, mime_type_t *dst,
  42                                       int *cost, _mime_typelist_t *visited);
  43
  44
  45 /*
  46  * 'mimeAddFilter()' - Add a filter to the current MIME database.
  47  */
  48
  49 mime_filter_t *                         /* O - New filter */
  50 mimeAddFilter(mime_t      *mime,        /* I - MIME database */
  51               mime_type_t *src,         /* I - Source type */
  52               mime_type_t *dst,         /* I - Destination type */
  53               int         cost,         /* I - Relative time/resource cost */
  54               const char  *filter)      /* I - Filter program to run */
  55 {
  56   mime_filter_t *temp;                  /* New filter */
  57
  58
  59   DEBUG_printf(("mimeAddFilter(mime=%p, src=%p(%s/%s), dst=%p(%s/%s), cost=%d, "
  60                 "filter=\"%s\")", mime,
  61                 src, src ? src->super : "???", src ? src->type : "???",
  62                 dst, dst ? dst->super : "???", dst ? dst->type : "???",
  63                 cost, filter));
  64
  65  /*
  66   * Range-check the input...
  67   */
  68
  69   if (!mime || !src || !dst || !filter)
  70   {
  71     DEBUG_puts("1mimeAddFilter: Returning NULL.");
  72     return (NULL);
  73   }
  74
  75  /*
  76   * See if we already have an existing filter for the given source and
  77   * destination...
  78   */
  79
  80   if ((temp = mimeFilterLookup(mime, src, dst)) != NULL)
  81   {
  82    /*
  83     * Yup, does the existing filter have a higher cost?  If so, copy the
  84     * filter and cost to the existing filter entry and return it...
  85     */
  86
  87     if (temp->cost > cost)
  88     {
  89       DEBUG_printf(("1mimeAddFilter: Replacing filter \"%s\", cost %d.",
  90                     temp->filter, temp->cost));
  91       temp->cost = cost;
  92       strlcpy(temp->filter, filter, sizeof(temp->filter));
  93     }
  94   }
  95   else
  96   {
  97    /*
  98     * Nope, add a new one...
  99     */
 100
 101     if (!mime->filters)
 102       mime->filters = cupsArrayNew((cups_array_func_t)mime_compare_filters, NULL);
 103
 104     if (!mime->filters)
 105       return (NULL);
 106
 107     if ((temp = calloc(1, sizeof(mime_filter_t))) == NULL)
 108       return (NULL);
 109
 110    /*
 111     * Copy the information over and sort if necessary...
 112     */
 113
 114     temp->src  = src;
 115     temp->dst  = dst;
 116     temp->cost = cost;
 117     strlcpy(temp->filter, filter, sizeof(temp->filter));
 118
 119     DEBUG_puts("1mimeAddFilter: Adding new filter.");
 120     cupsArrayAdd(mime->filters, temp);
 121     cupsArrayAdd(mime->srcs, temp);
 122   }
 123
 124  /*
 125   * Return the new/updated filter...
 126   */
 127
 128   DEBUG_printf(("1mimeAddFilter: Returning %p.", temp));
 129
 130   return (temp);
 131 }
 132
 133
 134 /*
 135  * 'mimeFilter()' - Find the fastest way to convert from one type to another.
 136  */
 137
 138 cups_array_t *                          /* O - Array of filters to run */
 139 mimeFilter(mime_t      *mime,           /* I - MIME database */
 140            mime_type_t *src,            /* I - Source file type */
 141            mime_type_t *dst,            /* I - Destination file type */
 142            int         *cost)           /* O - Cost of filters */
 143 {
 144   DEBUG_printf(("mimeFilter(mime=%p, src=%p(%s/%s), dst=%p(%s/%s), "
 145                 "cost=%p(%d))", mime,
 146                 src, src ? src->super : "???", src ? src->type : "???",
 147                 dst, dst ? dst->super : "???", dst ? dst->type : "???",
 148                 cost, cost ? *cost : 0));
 149
 150   return (mimeFilter2(mime, src, 0, dst, cost));
 151 }
 152
 153
 154 /*
 155  * 'mimeFilter2()' - Find the fastest way to convert from one type to another,
 156  *                   including file size.
 157  */
 158
 159 cups_array_t *                          /* O - Array of filters to run */
 160 mimeFilter2(mime_t      *mime,          /* I - MIME database */
 161             mime_type_t *src,           /* I - Source file type */
 162             size_t      srcsize,        /* I - Size of source file */
 163             mime_type_t *dst,           /* I - Destination file type */
 164             int         *cost)          /* O - Cost of filters */
 165 {
 166   cups_array_t  *filters;               /* Array of filters to run */
 167
 168
 169  /*
 170   * Range-check the input...
 171   */
 172
 173   DEBUG_printf(("mimeFilter2(mime=%p, src=%p(%s/%s), srcsize=" CUPS_LLFMT
 174                 ", dst=%p(%s/%s), cost=%p(%d))", mime,
 175                 src, src ? src->super : "???", src ? src->type : "???",
 176                 CUPS_LLCAST srcsize,
 177                 dst, dst ? dst->super : "???", dst ? dst->type : "???",
 178                 cost, cost ? *cost : 0));
 179
 180   if (cost)
 181     *cost = 0;
 182
 183   if (!mime || !src || !dst)
 184     return (NULL);
 185
 186  /*
 187   * (Re)build the source lookup array as needed...
 188   */
 189
 190   if (!mime->srcs)
 191   {
 192     mime_filter_t       *current;       /* Current filter */
 193
 194     mime->srcs = cupsArrayNew((cups_array_func_t)mime_compare_srcs, NULL);
 195
 196     for (current = mimeFirstFilter(mime);
 197          current;
 198          current = mimeNextFilter(mime))
 199       cupsArrayAdd(mime->srcs, current);
 200   }
 201
 202  /*
 203   * Find the filters...
 204   */
 205
 206   filters = mime_find_filters(mime, src, srcsize, dst, cost, NULL);
 207
 208   DEBUG_printf(("1mimeFilter2: Returning %d filter(s), cost %d:",
 209                 cupsArrayCount(filters), cost ? *cost : -1));
 210 #ifdef DEBUG
 211   {
 212     mime_filter_t       *filter;        /* Current filter */
 213
 214     for (filter = (mime_filter_t *)cupsArrayFirst(filters);
 215          filter;
 216          filter = (mime_filter_t *)cupsArrayNext(filters))
 217       DEBUG_printf(("1mimeFilter2: %s/%s %s/%s %d %s", filter->src->super,
 218                     filter->src->type, filter->dst->super, filter->dst->type,
 219                     filter->cost, filter->filter));
 220   }
 221 #endif /* DEBUG */
 222
 223   return (filters);
 224 }
 225
 226
 227 /*
 228  * 'mimeFilterLookup()' - Lookup a filter.
 229  */
 230
 231 mime_filter_t *                         /* O - Filter for src->dst */
 232 mimeFilterLookup(mime_t      *mime,     /* I - MIME database */
 233                  mime_type_t *src,      /* I - Source type */
 234                  mime_type_t *dst)      /* I - Destination type */
 235 {
 236   mime_filter_t key,                    /* Key record for filter search */
 237                 *filter;                /* Matching filter */
 238
 239
 240   DEBUG_printf(("2mimeFilterLookup(mime=%p, src=%p(%s/%s), dst=%p(%s/%s))", mime,
 241                 src, src ? src->super : "???", src ? src->type : "???",
 242                 dst, dst ? dst->super : "???", dst ? dst->type : "???"));
 243
 244   key.src = src;
 245   key.dst = dst;
 246
 247   filter = (mime_filter_t *)cupsArrayFind(mime->filters, &key);
 248   DEBUG_printf(("3mimeFilterLookup: Returning %p(%s).", filter,
 249                 filter ? filter->filter : "???"));
 250   return (filter);
 251 }
 252
 253
 254 /*
 255  * 'mime_compare_filters()' - Compare two filters.
 256  */
 257
 258 static int                              /* O - Comparison result */
 259 mime_compare_filters(mime_filter_t *f0, /* I - First filter */
 260                      mime_filter_t *f1) /* I - Second filter */
 261 {
 262   int   i;                              /* Result of comparison */
 263
 264
 265   if ((i = strcmp(f0->src->super, f1->src->super)) == 0)
 266     if ((i = strcmp(f0->src->type, f1->src->type)) == 0)
 267       if ((i = strcmp(f0->dst->super, f1->dst->super)) == 0)
 268         i = strcmp(f0->dst->type, f1->dst->type);
 269
 270   return (i);
 271 }
 272
 273
 274 /*
 275  * 'mime_compare_srcs()' - Compare two filter source types.
 276  */
 277
 278 static int                              /* O - Comparison result */
 279 mime_compare_srcs(mime_filter_t *f0,    /* I - First filter */
 280                   mime_filter_t *f1)    /* I - Second filter */
 281 {
 282   int   i;                              /* Result of comparison */
 283
 284
 285   if ((i = strcmp(f0->src->super, f1->src->super)) == 0)
 286     i = strcmp(f0->src->type, f1->src->type);
 287
 288   return (i);
 289 }
 290
 291
 292 /*
 293  * 'mime_find_filters()' - Find the filters to convert from one type to another.
 294  */
 295
 296 static cups_array_t *                   /* O - Array of filters to run */
 297 mime_find_filters(
 298     mime_t           *mime,             /* I - MIME database */
 299     mime_type_t      *src,              /* I - Source file type */
 300     size_t           srcsize,           /* I - Size of source file */
 301     mime_type_t      *dst,              /* I - Destination file type */
 302     int              *cost,             /* O - Cost of filters */
 303     _mime_typelist_t *list)             /* I - Source types we've used */
 304 {
 305   int                   tempcost,       /* Temporary cost */
 306                         mincost;        /* Current minimum */
 307   cups_array_t          *temp,          /* Temporary filter */
 308                         *mintemp;       /* Current minimum */
 309   mime_filter_t         *current,       /* Current filter */
 310                         srckey;         /* Source type key */
 311   _mime_typelist_t      listnode,       /* New list node */
 312                         *listptr;       /* Pointer in list */
 313
 314
 315   DEBUG_printf(("2mime_find_filters(mime=%p, src=%p(%s/%s), srcsize=" CUPS_LLFMT
 316                 ", dst=%p(%s/%s), cost=%p, list=%p)", mime, src, src->super,
 317                 src->type, CUPS_LLCAST srcsize, dst, dst->super, dst->type,
 318                 cost, list));
 319
 320  /*
 321   * See if there is a filter that can convert the files directly...
 322   */
 323
 324   if ((current = mimeFilterLookup(mime, src, dst)) != NULL &&
 325       (current->maxsize == 0 || srcsize <= current->maxsize))
 326   {
 327    /*
 328     * Got a direct filter!
 329     */
 330
 331     DEBUG_puts("3mime_find_filters: Direct filter found.");
 332
 333     if ((mintemp = cupsArrayNew(NULL, NULL)) == NULL)
 334     {
 335       DEBUG_puts("3mime_find_filters: Returning NULL (out of memory).");
 336       return (NULL);
 337     }
 338
 339     cupsArrayAdd(mintemp, current);
 340
 341     mincost = current->cost;
 342
 343     if (!cost)
 344     {
 345       DEBUG_printf(("3mime_find_filters: Returning 1 filter, cost %d:",
 346                     mincost));
 347       DEBUG_printf(("3mime_find_filters: %s/%s %s/%s %d %s",
 348                     current->src->super, current->src->type,
 349                     current->dst->super, current->dst->type,
 350                     current->cost, current->filter));
 351       return (mintemp);
 352     }
 353   }
 354   else
 355   {
 356    /*
 357     * No direct filter...
 358     */
 359
 360     mintemp = NULL;
 361     mincost = 9999999;
 362   }
 363
 364  /*
 365   * Initialize this node in the type list...
 366   */
 367
 368   listnode.next = list;
 369
 370  /*
 371   * OK, now look for filters from the source type to any other type...
 372   */
 373
 374   srckey.src = src;
 375
 376   for (current = (mime_filter_t *)cupsArrayFind(mime->srcs, &srckey);
 377        current && current->src == src;
 378        current = (mime_filter_t *)cupsArrayNext(mime->srcs))
 379   {
 380    /*
 381     * See if we have already tried the destination type as a source
 382     * type (this avoids extra filter looping...)
 383     */
 384
 385     mime_type_t *current_dst;           /* Current destination type */
 386
 387     if (current->maxsize > 0 && srcsize > current->maxsize)
 388       continue;
 389
 390     for (listptr = list, current_dst = current->dst;
 391          listptr;
 392          listptr = listptr->next)
 393       if (current_dst == listptr->src)
 394         break;
 395
 396     if (listptr)
 397       continue;
 398
 399    /*
 400     * See if we have any filters that can convert from the destination type
 401     * of this filter to the final type...
 402     */
 403
 404     listnode.src = current->src;
 405
 406     cupsArraySave(mime->srcs);
 407     temp = mime_find_filters(mime, current->dst, srcsize, dst, &tempcost,
 408                              &listnode);
 409     cupsArrayRestore(mime->srcs);
 410
 411     if (!temp)
 412       continue;
 413
 414     if (!cost)
 415     {
 416       DEBUG_printf(("3mime_find_filters: Returning %d filter(s), cost %d:",
 417                     cupsArrayCount(temp), tempcost));
 418
 419 #ifdef DEBUG
 420       for (current = (mime_filter_t *)cupsArrayFirst(temp);
 421            current;
 422            current = (mime_filter_t *)cupsArrayNext(temp))
 423         DEBUG_printf(("3mime_find_filters: %s/%s %s/%s %d %s",
 424                       current->src->super, current->src->type,
 425                       current->dst->super, current->dst->type,
 426                       current->cost, current->filter));
 427 #endif /* DEBUG */
 428
 429       return (temp);
 430     }
 431
 432    /*
 433     * Found a match; see if this one is less costly than the last (if
 434     * any...)
 435     */
 436
 437     tempcost += current->cost;
 438
 439     if (tempcost < mincost)
 440     {
 441       cupsArrayDelete(mintemp);
 442
 443      /*
 444       * Hey, we got a match!  Add the current filter to the beginning of the
 445       * filter list...
 446       */
 447
 448       mintemp = temp;
 449       mincost = tempcost;
 450       cupsArrayInsert(mintemp, current);
 451     }
 452     else
 453       cupsArrayDelete(temp);
 454   }
 455
 456   if (mintemp)
 457   {
 458    /*
 459     * Hey, we got a match!
 460     */
 461
 462     DEBUG_printf(("3mime_find_filters: Returning %d filter(s), cost %d:",
 463                   cupsArrayCount(mintemp), mincost));
 464
 465 #ifdef DEBUG
 466     for (current = (mime_filter_t *)cupsArrayFirst(mintemp);
 467          current;
 468          current = (mime_filter_t *)cupsArrayNext(mintemp))
 469       DEBUG_printf(("3mime_find_filters: %s/%s %s/%s %d %s",
 470                     current->src->super, current->src->type,
 471                     current->dst->super, current->dst->type,
 472                     current->cost, current->filter));
 473 #endif /* DEBUG */
 474
 475     if (cost)
 476       *cost = mincost;
 477
 478     return (mintemp);
 479   }
 480
 481   DEBUG_puts("3mime_find_filters: Returning NULL (no matches).");
 482
 483   return (NULL);
 484 }