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