scheduler/filter.c

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