cairo/src/cairo-lzw.c

   1 /* cairo - a vector graphics library with display and print output
   2  *
   3  * Copyright © 2006 Red Hat, Inc.
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it either under the terms of the GNU Lesser General Public
   7  * License version 2.1 as published by the Free Software Foundation
   8  * (the "LGPL") or, at your option, under the terms of the Mozilla
   9  * Public License Version 1.1 (the "MPL"). If you do not alter this
  10  * notice, a recipient may use your version of this file under either
  11  * the MPL or the LGPL.
  12  *
  13  * You should have received a copy of the LGPL along with this library
  14  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  15  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  16  * You should have received a copy of the MPL along with this library
  17  * in the file COPYING-MPL-1.1
  18  *
  19  * The contents of this file are subject to the Mozilla Public License
  20  * Version 1.1 (the "License"); you may not use this file except in
  21  * compliance with the License. You may obtain a copy of the License at
  22  * http://www.mozilla.org/MPL/
  23  *
  24  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  25  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  26  * the specific language governing rights and limitations.
  27  *
  28  * The Original Code is the cairo graphics library.
  29  *
  30  * The Initial Developer of the Original Code is University of Southern
  31  * California.
  32  *
  33  * Contributor(s):
  34  *      Carl D. Worth <cworth@cworth.org>
  35  */
  36
  37 #include "cairoint.h"
  38
  39 typedef struct _lzw_buf {
  40     cairo_status_t status;
  41
  42     unsigned char *data;
  43     int data_size;
  44     int num_data;
  45     uint32_t pending;
  46     unsigned int pending_bits;
  47 } lzw_buf_t;
  48
  49 /* An lzw_buf_t is a simple, growable chunk of memory for holding
  50  * variable-size objects of up to 16 bits each.
  51  *
  52  * Initialize an lzw_buf_t to the given size in bytes.
  53  *
  54  * To store objects into the lzw_buf_t, call _lzw_buf_store_bits and
  55  * when finished, call _lzw_buf_store_pending, (which flushes out the
  56  * last few bits that hadn't yet made a complete byte yet).
  57  *
  58  * Instead of returning failure from any functions, lzw_buf_t provides
  59  * a status value that the caller can query, (and should query at
  60  * least once when done with the object). The status value will be
  61  * either %CAIRO_STATUS_SUCCESS or %CAIRO_STATUS_NO_MEMORY;
  62  */
  63 static void
  64 _lzw_buf_init (lzw_buf_t *buf, int size)
  65 {
  66     if (size == 0)
  67         size = 16;
  68
  69     buf->status = CAIRO_STATUS_SUCCESS;
  70     buf->data_size = size;
  71     buf->num_data = 0;
  72     buf->pending = 0;
  73     buf->pending_bits = 0;
  74
  75     buf->data = malloc (size);
  76     if (buf->data == NULL) {
  77         buf->data_size = 0;
  78         buf->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
  79         return;
  80     }
  81 }
  82
  83 /* Increase the buffer size by doubling.
  84  *
  85  * Returns %CAIRO_STATUS_SUCCESS or %CAIRO_STATUS_NO_MEMORY
  86  */
  87 static cairo_status_t
  88 _lzw_buf_grow (lzw_buf_t *buf)
  89 {
  90     int new_size = buf->data_size * 2;
  91     unsigned char *new_data;
  92
  93     if (buf->status)
  94         return buf->status;
  95
  96     new_data = NULL;
  97     /* check for integer overflow */
  98     if (new_size / 2 == buf->data_size)
  99         new_data = realloc (buf->data, new_size);
 100
 101     if (new_data == NULL) {
 102         free (buf->data);
 103         buf->data_size = 0;
 104         buf->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
 105         return buf->status;
 106     }
 107
 108     buf->data = new_data;
 109     buf->data_size = new_size;
 110
 111     return CAIRO_STATUS_SUCCESS;
 112 }
 113
 114 /* Store the lowest num_bits bits of values into buf.
 115  *
 116  * Note: The bits of value above size_in_bits must be 0, (so don't lie
 117  * about the size).
 118  *
 119  * See also _lzw_buf_store_pending which must be called after the last
 120  * call to _lzw_buf_store_bits.
 121  *
 122  * Sets buf->status to either %CAIRO_STATUS_SUCCESS or %CAIRO_STATUS_NO_MEMORY.
 123  */
 124 static void
 125 _lzw_buf_store_bits (lzw_buf_t *buf, uint16_t value, int num_bits)
 126 {
 127     cairo_status_t status;
 128
 129     assert (value <= (1 << num_bits) - 1);
 130
 131     if (buf->status)
 132         return;
 133
 134     buf->pending = (buf->pending << num_bits) | value;
 135     buf->pending_bits += num_bits;
 136
 137     while (buf->pending_bits >= 8) {
 138         if (buf->num_data >= buf->data_size) {
 139             status = _lzw_buf_grow (buf);
 140             if (status)
 141                 return;
 142         }
 143         buf->data[buf->num_data++] = buf->pending >> (buf->pending_bits - 8);
 144         buf->pending_bits -= 8;
 145     }
 146 }
 147
 148 /* Store the last remaining pending bits into the buffer.
 149  *
 150  * Note: This function must be called after the last call to
 151  * _lzw_buf_store_bits.
 152  *
 153  * Sets buf->status to either %CAIRO_STATUS_SUCCESS or %CAIRO_STATUS_NO_MEMORY.
 154  */
 155 static void
 156 _lzw_buf_store_pending  (lzw_buf_t *buf)
 157 {
 158     cairo_status_t status;
 159
 160     if (buf->status)
 161         return;
 162
 163     if (buf->pending_bits == 0)
 164         return;
 165
 166     assert (buf->pending_bits < 8);
 167
 168     if (buf->num_data >= buf->data_size) {
 169         status = _lzw_buf_grow (buf);
 170         if (status)
 171             return;
 172     }
 173
 174     buf->data[buf->num_data++] = buf->pending << (8 - buf->pending_bits);
 175     buf->pending_bits = 0;
 176 }
 177
 178 /* LZW defines a few magic code values */
 179 #define LZW_CODE_CLEAR_TABLE    256
 180 #define LZW_CODE_EOD            257
 181 #define LZW_CODE_FIRST          258
 182
 183 /* We pack three separate values into a symbol as follows:
 184  *
 185  * 12 bits (31 down to 20):     CODE: code value used to represent this symbol
 186  * 12 bits (19 down to  8):     PREV: previous code value in chain
 187  *  8 bits ( 7 down to  0):     NEXT: next byte value in chain
 188  */
 189 typedef uint32_t lzw_symbol_t;
 190
 191 #define LZW_SYMBOL_SET(sym, prev, next)                 ((sym) = ((prev) << 8)|(next))
 192 #define LZW_SYMBOL_SET_CODE(sym, code, prev, next)      ((sym) = ((code << 20)|(prev) << 8)|(next))
 193 #define LZW_SYMBOL_GET_CODE(sym)                        (((sym) >> 20))
 194 #define LZW_SYMBOL_GET_PREV(sym)                        (((sym) >>  8) & 0x7ff)
 195 #define LZW_SYMBOL_GET_BYTE(sym)                        (((sym) >>  0) & 0x0ff)
 196
 197 /* The PREV+NEXT fields can be seen as the key used to fetch values
 198  * from the hash table, while the code is the value fetched.
 199  */
 200 #define LZW_SYMBOL_KEY_MASK     0x000fffff
 201
 202 /* Since code values are only stored starting with 258 we can safely
 203  * use a zero value to represent free slots in the hash table. */
 204 #define LZW_SYMBOL_FREE         0x00000000
 205
 206 /* These really aren't very free for modifying. First, the PostScript
 207  * specification sets the 9-12 bit range. Second, the encoding of
 208  * lzw_symbol_t above also relies on 2 of LZW_BITS_MAX plus one byte
 209  * fitting within 32 bits.
 210  *
 211  * But other than that, the LZW compression scheme could function with
 212  * more bits per code.
 213  */
 214 #define LZW_BITS_MIN            9
 215 #define LZW_BITS_MAX            12
 216 #define LZW_BITS_BOUNDARY(bits) ((1<<(bits))-1)
 217 #define LZW_MAX_SYMBOLS         (1<<LZW_BITS_MAX)
 218
 219 #define LZW_SYMBOL_TABLE_SIZE   9013
 220 #define LZW_SYMBOL_MOD1         LZW_SYMBOL_TABLE_SIZE
 221 #define LZW_SYMBOL_MOD2         9011
 222
 223 typedef struct _lzw_symbol_table {
 224     lzw_symbol_t table[LZW_SYMBOL_TABLE_SIZE];
 225 } lzw_symbol_table_t;
 226
 227 /* Initialize the hash table to entirely empty */
 228 static void
 229 _lzw_symbol_table_init (lzw_symbol_table_t *table)
 230 {
 231     memset (table->table, 0, LZW_SYMBOL_TABLE_SIZE * sizeof (lzw_symbol_t));
 232 }
 233
 234 /* Lookup a symbol in the symbol table. The PREV and NEXT fields of
 235  * symbol form the key for the lookup.
 236  *
 237  * If successful, then this function returns %TRUE and slot_ret will be
 238  * left pointing at the result that will have the CODE field of
 239  * interest.
 240  *
 241  * If the lookup fails, then this function returns %FALSE and slot_ret
 242  * will be pointing at the location in the table to which a new CODE
 243  * value should be stored along with PREV and NEXT.
 244  */
 245 static cairo_bool_t
 246 _lzw_symbol_table_lookup (lzw_symbol_table_t     *table,
 247                           lzw_symbol_t            symbol,
 248                           lzw_symbol_t          **slot_ret)
 249 {
 250     /* The algorithm here is identical to that in cairo-hash.c. We
 251      * copy it here to allow for a rather more efficient
 252      * implementation due to several circumstances that do not apply
 253      * to the more general case:
 254      *
 255      * 1) We have a known bound on the total number of symbols, so we
 256      *    have a fixed-size table without any copying when growing
 257      *
 258      * 2) We never delete any entries, so we don't need to
 259      *    support/check for DEAD entries during lookup.
 260      *
 261      * 3) The object fits in 32 bits so we store each object in its
 262      *    entirety within the table rather than storing objects
 263      *    externally and putting pointers in the table, (which here
 264      *    would just double the storage requirements and have negative
 265      *    impacts on memory locality).
 266      */
 267     int i, idx, step, hash = symbol & LZW_SYMBOL_KEY_MASK;
 268     lzw_symbol_t candidate;
 269
 270     idx = hash % LZW_SYMBOL_MOD1;
 271     step = 0;
 272
 273     *slot_ret = NULL;
 274     for (i = 0; i < LZW_SYMBOL_TABLE_SIZE; i++)
 275     {
 276         candidate = table->table[idx];
 277         if (candidate == LZW_SYMBOL_FREE)
 278         {
 279             *slot_ret = &table->table[idx];
 280             return FALSE;
 281         }
 282         else /* candidate is LIVE */
 283         {
 284             if ((candidate & LZW_SYMBOL_KEY_MASK) ==
 285                 (symbol & LZW_SYMBOL_KEY_MASK))
 286             {
 287                 *slot_ret = &table->table[idx];
 288                 return TRUE;
 289             }
 290         }
 291
 292         if (step == 0) {
 293             step = hash % LZW_SYMBOL_MOD2;
 294             if (step == 0)
 295                 step = 1;
 296         }
 297
 298         idx += step;
 299         if (idx >= LZW_SYMBOL_TABLE_SIZE)
 300             idx -= LZW_SYMBOL_TABLE_SIZE;
 301     }
 302
 303     return FALSE;
 304 }
 305
 306 /* Compress a bytestream using the LZW algorithm.
 307  *
 308  * This is an original implementation based on reading the
 309  * specification of the LZWDecode filter in the PostScript Language
 310  * Reference. The free parameters in the LZW algorithm are set to the
 311  * values mandated by PostScript, (symbols encoded with widths from 9
 312  * to 12 bits).
 313  *
 314  * This function returns a pointer to a newly allocated buffer holding
 315  * the compressed data, or %NULL if an out-of-memory situation
 316  * occurs.
 317  *
 318  * Notice that any one of the _lzw_buf functions called here could
 319  * trigger an out-of-memory condition. But lzw_buf_t uses cairo's
 320  * shutdown-on-error idiom, so it's safe to continue to call into
 321  * lzw_buf without having to check for errors, (until a final check at
 322  * the end).
 323  */
 324 unsigned char *
 325 _cairo_lzw_compress (unsigned char *data, unsigned long *size_in_out)
 326 {
 327     int bytes_remaining = *size_in_out;
 328     lzw_buf_t buf;
 329     lzw_symbol_table_t table;
 330     lzw_symbol_t symbol, *slot = NULL; /* just to squelch a warning */
 331     int code_next = LZW_CODE_FIRST;
 332     int code_bits = LZW_BITS_MIN;
 333     int prev, next = 0; /* just to squelch a warning */
 334
 335     if (*size_in_out == 0)
 336         return NULL;
 337
 338     _lzw_buf_init (&buf, *size_in_out);
 339
 340     _lzw_symbol_table_init (&table);
 341
 342     /* The LZW header is a clear table code. */
 343     _lzw_buf_store_bits (&buf, LZW_CODE_CLEAR_TABLE, code_bits);
 344
 345     while (1) {
 346
 347         /* Find the longest existing code in the symbol table that
 348          * matches the current input, if any. */
 349         prev = *data++;
 350         bytes_remaining--;
 351         if (bytes_remaining) {
 352             do
 353             {
 354                 next = *data++;
 355                 bytes_remaining--;
 356                 LZW_SYMBOL_SET (symbol, prev, next);
 357                 if (_lzw_symbol_table_lookup (&table, symbol, &slot))
 358                     prev = LZW_SYMBOL_GET_CODE (*slot);
 359             } while (bytes_remaining && *slot != LZW_SYMBOL_FREE);
 360             if (*slot == LZW_SYMBOL_FREE) {
 361                 data--;
 362                 bytes_remaining++;
 363             }
 364         }
 365
 366         /* Write the code into the output. This is either a byte read
 367          * directly from the input, or a code from the last successful
 368          * lookup. */
 369         _lzw_buf_store_bits (&buf, prev, code_bits);
 370
 371         if (bytes_remaining == 0)
 372             break;
 373
 374         LZW_SYMBOL_SET_CODE (*slot, code_next++, prev, next);
 375
 376         if (code_next > LZW_BITS_BOUNDARY(code_bits))
 377         {
 378             code_bits++;
 379             if (code_bits > LZW_BITS_MAX) {
 380                 _lzw_symbol_table_init (&table);
 381                 _lzw_buf_store_bits (&buf, LZW_CODE_CLEAR_TABLE, code_bits - 1);
 382                 code_bits = LZW_BITS_MIN;
 383                 code_next = LZW_CODE_FIRST;
 384             }
 385         }
 386     }
 387
 388     /* The LZW footer is an end-of-data code. */
 389     _lzw_buf_store_bits (&buf, LZW_CODE_EOD, code_bits);
 390
 391     _lzw_buf_store_pending (&buf);
 392
 393     /* See if we ever ran out of memory while writing to buf. */
 394     if (buf.status == CAIRO_STATUS_NO_MEMORY) {
 395         *size_in_out = 0;
 396         return NULL;
 397     }
 398
 399     assert (buf.status == CAIRO_STATUS_SUCCESS);
 400
 401     *size_in_out = buf.num_data;
 402     return buf.data;
 403 }