summaryrefslogtreecommitdiff
path: root/src/cairo-lzw.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/cairo-lzw.c')
-rw-r--r--src/cairo-lzw.c499
1 files changed, 499 insertions, 0 deletions
diff --git a/src/cairo-lzw.c b/src/cairo-lzw.c
new file mode 100644
index 00000000..bb764f3a
--- /dev/null
+++ b/src/cairo-lzw.c
@@ -0,0 +1,499 @@
+/* cairo - a vector graphics library with display and print output
+ *
+ * Copyright © 2006 Red Hat, Inc
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ *
+ * The Original Code is the cairo graphics library.
+ *
+ * Contributor(s):
+ * Alexander Larsson <alexl@redhat.com>
+ *
+ * This code is derived from tif_lzw.c in libtiff 3.8.0.
+ * The original copyright notice appears below in its entirety.
+ */
+
+#include "cairoint.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <stdarg.h>
+#include <assert.h>
+#include <string.h>
+
+/*
+ * Copyright (c) 1988-1997 Sam Leffler
+ * Copyright (c) 1991-1997 Silicon Graphics, Inc.
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and
+ * its documentation for any purpose is hereby granted without fee, provided
+ * that (i) the above copyright notices and this permission notice appear in
+ * all copies of the software and related documentation, and (ii) the names of
+ * Sam Leffler and Silicon Graphics may not be used in any advertising or
+ * publicity relating to the software without the specific, prior written
+ * permission of Sam Leffler and Silicon Graphics.
+ *
+ * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY
+ * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
+ *
+ * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
+ * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
+ * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
+ * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF
+ * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
+ * OF THIS SOFTWARE.
+ */
+
+/*
+ * TIFF Library.
+ * Rev 5.0 Lempel-Ziv & Welch Compression Support
+ *
+ * This code is derived from the compress program whose code is
+ * derived from software contributed to Berkeley by James A. Woods,
+ * derived from original work by Spencer Thomas and Joseph Orost.
+ *
+ * The original Berkeley copyright notice appears below in its entirety.
+ */
+
+#define MAXCODE(n) ((1L<<(n))-1)
+/*
+ * The TIFF spec specifies that encoded bit
+ * strings range from 9 to 12 bits.
+ */
+#define BITS_MIN 9 /* start with 9 bits */
+#define BITS_MAX 12 /* max of 12 bit strings */
+/* predefined codes */
+#define CODE_CLEAR 256 /* code to clear string table */
+#define CODE_EOI 257 /* end-of-information code */
+#define CODE_FIRST 258 /* first free code entry */
+#define CODE_MAX MAXCODE(BITS_MAX)
+#define HSIZE 9001L /* 91% occupancy */
+#define HSHIFT (13-8)
+#ifdef LZW_COMPAT
+/* NB: +1024 is for compatibility with old files */
+#define CSIZE (MAXCODE(BITS_MAX)+1024L)
+#else
+#define CSIZE (MAXCODE(BITS_MAX)+1L)
+#endif
+
+typedef uint16_t hcode_t; /* codes fit in 16 bits */
+typedef struct {
+ long hash;
+ hcode_t code;
+} hash_t;
+
+typedef struct {
+ /* Out buffer */
+ unsigned char *out_buffer; /* compressed out buffer */
+ size_t out_buffer_size; /* # of allocated bytes in out buffer */
+ unsigned char *out_buffer_pos; /* current spot in out buffer */
+ size_t out_buffer_bytes; /* # of data bytes in out buffer */
+ unsigned char *out_buffer_end; /* bound on out_buffer */
+
+ unsigned short nbits; /* # of bits/code */
+ unsigned short maxcode; /* maximum code for lzw_nbits */
+ unsigned short free_ent; /* next free entry in hash table */
+ long nextdata; /* next bits of i/o */
+ long nextbits; /* # of valid bits in lzw_nextdata */
+
+ int enc_oldcode; /* last code encountered */
+ long enc_checkpoint; /* point at which to clear table */
+#define CHECK_GAP 10000 /* enc_ratio check interval */
+ long enc_ratio; /* current compression ratio */
+ long enc_incount; /* (input) data bytes encoded */
+ long enc_outcount; /* encoded (output) bytes */
+ hash_t* enc_hashtab; /* kept separate for small machines */
+} LZWCodecState;
+
+static void cl_hash(LZWCodecState*);
+
+/*
+ * LZW Encoding.
+ */
+
+static unsigned char *
+grow_out_buffer (LZWCodecState *sp, unsigned char *op)
+{
+ size_t cc;
+
+ cc = (size_t)(op - sp->out_buffer);
+
+ sp->out_buffer_size = sp->out_buffer_size * 2;
+ sp->out_buffer = realloc (sp->out_buffer, sp->out_buffer_size);
+ /*
+ * The 4 here insures there is space for 2 max-sized
+ * codes in LZWEncode and LZWPostDecode.
+ */
+ sp->out_buffer_end = sp->out_buffer + sp->out_buffer_size-1 - 4;
+
+ return sp->out_buffer + cc;
+}
+
+static int
+LZWSetupEncode (LZWCodecState* sp)
+{
+ memset (sp, 0, sizeof (LZWCodecState));
+ sp->enc_hashtab = (hash_t*) malloc (HSIZE * sizeof (hash_t));
+ if (sp->enc_hashtab == NULL)
+ return 0;
+ return 1;
+}
+
+static void
+LZWFreeEncode (LZWCodecState* sp)
+{
+ if (sp->enc_hashtab)
+ free (sp->enc_hashtab);
+}
+
+
+/*
+ * Reset encoding state at the start of a strip.
+ */
+static void
+LZWPreEncode (LZWCodecState *sp)
+{
+ sp->nbits = BITS_MIN;
+ sp->maxcode = MAXCODE(BITS_MIN);
+ sp->free_ent = CODE_FIRST;
+ sp->nextbits = 0;
+ sp->nextdata = 0;
+ sp->enc_checkpoint = CHECK_GAP;
+ sp->enc_ratio = 0;
+ sp->enc_incount = 0;
+ sp->enc_outcount = 0;
+ /*
+ * The 4 here insures there is space for 2 max-sized
+ * codes in LZWEncode and LZWPostDecode.
+ */
+ sp->out_buffer_end = sp->out_buffer + sp->out_buffer_size-1 - 4;
+ cl_hash(sp); /* clear hash table */
+ sp->enc_oldcode = (hcode_t) -1; /* generates CODE_CLEAR in LZWEncode */
+}
+
+#define CALCRATIO(sp, rat) { \
+ if (incount > 0x007fffff) { /* NB: shift will overflow */ \
+ rat = outcount >> 8; \
+ rat = (rat == 0 ? 0x7fffffff : incount/rat); \
+ } else \
+ rat = (incount << 8) / outcount; \
+}
+#define PutNextCode(op, c) { \
+ nextdata = (nextdata << nbits) | c; \
+ nextbits += nbits; \
+ *op++ = (unsigned char)(nextdata >> (nextbits-8)); \
+ nextbits -= 8; \
+ if (nextbits >= 8) { \
+ *op++ = (unsigned char)(nextdata >> (nextbits-8)); \
+ nextbits -= 8; \
+ } \
+ outcount += nbits; \
+}
+
+/*
+ * Encode a chunk of pixels.
+ *
+ * Uses an open addressing double hashing (no chaining) on the
+ * prefix code/next character combination. We do a variant of
+ * Knuth's algorithm D (vol. 3, sec. 6.4) along with G. Knott's
+ * relatively-prime secondary probe. Here, the modular division
+ * first probe is gives way to a faster exclusive-or manipulation.
+ * Also do block compression with an adaptive reset, whereby the
+ * code table is cleared when the compression ratio decreases,
+ * but after the table fills. The variable-length output codes
+ * are re-sized at this point, and a CODE_CLEAR is generated
+ * for the decoder.
+ */
+static int
+LZWEncode (LZWCodecState *sp,
+ unsigned char *bp,
+ size_t cc)
+{
+ register long fcode;
+ register hash_t *hp;
+ register int h, c;
+ hcode_t ent;
+ long disp;
+ long incount, outcount, checkpoint;
+ long nextdata, nextbits;
+ int free_ent, maxcode, nbits;
+ unsigned char *op;
+
+ /*
+ * Load local state.
+ */
+ incount = sp->enc_incount;
+ outcount = sp->enc_outcount;
+ checkpoint = sp->enc_checkpoint;
+ nextdata = sp->nextdata;
+ nextbits = sp->nextbits;
+ free_ent = sp->free_ent;
+ maxcode = sp->maxcode;
+ nbits = sp->nbits;
+ op = sp->out_buffer_pos;
+ ent = sp->enc_oldcode;
+
+ if (ent == (hcode_t) -1 && cc > 0) {
+ /*
+ * NB: This is safe because it can only happen
+ * at the start of a strip where we know there
+ * is space in the data buffer.
+ */
+ PutNextCode(op, CODE_CLEAR);
+ ent = *bp++; cc--; incount++;
+ }
+ while (cc > 0) {
+ c = *bp++; cc--; incount++;
+ fcode = ((long)c << BITS_MAX) + ent;
+ h = (c << HSHIFT) ^ ent; /* xor hashing */
+#ifdef _WINDOWS
+ /*
+ * Check hash index for an overflow.
+ */
+ if (h >= HSIZE)
+ h -= HSIZE;
+#endif
+ hp = &sp->enc_hashtab[h];
+ if (hp->hash == fcode) {
+ ent = hp->code;
+ continue;
+ }
+ if (hp->hash >= 0) {
+ /*
+ * Primary hash failed, check secondary hash.
+ */
+ disp = HSIZE - h;
+ if (h == 0)
+ disp = 1;
+ do {
+ /*
+ * Avoid pointer arithmetic 'cuz of
+ * wraparound problems with segments.
+ */
+ if ((h -= disp) < 0)
+ h += HSIZE;
+ hp = &sp->enc_hashtab[h];
+ if (hp->hash == fcode) {
+ ent = hp->code;
+ goto hit;
+ }
+ } while (hp->hash >= 0);
+ }
+ /*
+ * New entry, emit code and add to table.
+ */
+ /*
+ * Verify there is space in the buffer for the code
+ * and any potential Clear code that might be emitted
+ * below. The value of limit is setup so that there
+ * are at least 4 bytes free--room for 2 codes.
+ */
+ if (op > sp->out_buffer_end) {
+ op = grow_out_buffer (sp, op);
+ if (sp->out_buffer == NULL) {
+ return 0;
+ }
+ }
+ PutNextCode(op, ent);
+ ent = c;
+ hp->code = free_ent++;
+ hp->hash = fcode;
+ if (free_ent == CODE_MAX-1) {
+ /* table is full, emit clear code and reset */
+ cl_hash(sp);
+ sp->enc_ratio = 0;
+ incount = 0;
+ outcount = 0;
+ free_ent = CODE_FIRST;
+ PutNextCode(op, CODE_CLEAR);
+ nbits = BITS_MIN;
+ maxcode = MAXCODE(BITS_MIN);
+ } else {
+ /*
+ * If the next entry is going to be too big for
+ * the code size, then increase it, if possible.
+ */
+ if (free_ent > maxcode) {
+ nbits++;
+ assert(nbits <= BITS_MAX);
+ maxcode = (int) MAXCODE(nbits);
+ } else if (incount >= checkpoint) {
+ long rat;
+ /*
+ * Check compression ratio and, if things seem
+ * to be slipping, clear the hash table and
+ * reset state. The compression ratio is a
+ * 24+8-bit fractional number.
+ */
+ checkpoint = incount+CHECK_GAP;
+ CALCRATIO(sp, rat);
+ if (rat <= sp->enc_ratio) {
+ cl_hash(sp);
+ sp->enc_ratio = 0;
+ incount = 0;
+ outcount = 0;
+ free_ent = CODE_FIRST;
+ PutNextCode(op, CODE_CLEAR);
+ nbits = BITS_MIN;
+ maxcode = MAXCODE(BITS_MIN);
+ } else
+ sp->enc_ratio = rat;
+ }
+ }
+ hit:
+ ;
+ }
+
+ /*
+ * Restore global state.
+ */
+ sp->enc_incount = incount;
+ sp->enc_outcount = outcount;
+ sp->enc_checkpoint = checkpoint;
+ sp->enc_oldcode = ent;
+ sp->nextdata = nextdata;
+ sp->nextbits = nextbits;
+ sp->free_ent = free_ent;
+ sp->maxcode = maxcode;
+ sp->nbits = nbits;
+ sp->out_buffer_pos = op;
+ return 1;
+}
+
+/*
+ * Finish off an encoded strip by flushing the last
+ * string and tacking on an End Of Information code.
+ */
+static int
+LZWPostEncode (LZWCodecState *sp)
+{
+ unsigned char *op = sp->out_buffer_pos;
+ long nextbits = sp->nextbits;
+ long nextdata = sp->nextdata;
+ long outcount = sp->enc_outcount;
+ int nbits = sp->nbits;
+
+ if (op > sp->out_buffer_end) {
+ op = grow_out_buffer (sp, op);
+ if (sp->out_buffer == NULL) {
+ return 0;
+ }
+ }
+ if (sp->enc_oldcode != (hcode_t) -1) {
+ PutNextCode(op, sp->enc_oldcode);
+ sp->enc_oldcode = (hcode_t) -1;
+ }
+ PutNextCode(op, CODE_EOI);
+ if (nextbits > 0)
+ *op++ = (unsigned char)(nextdata << (8-nextbits));
+ sp->out_buffer_bytes = (size_t)(op - sp->out_buffer);
+ return 1;
+}
+
+/*
+ * Reset encoding hash table.
+ */
+static void
+cl_hash (LZWCodecState* sp)
+{
+ register hash_t *hp = &sp->enc_hashtab[HSIZE-1];
+ register long i = HSIZE-8;
+
+ do {
+ i -= 8;
+ hp[-7].hash = -1;
+ hp[-6].hash = -1;
+ hp[-5].hash = -1;
+ hp[-4].hash = -1;
+ hp[-3].hash = -1;
+ hp[-2].hash = -1;
+ hp[-1].hash = -1;
+ hp[ 0].hash = -1;
+ hp -= 8;
+ } while (i >= 0);
+ for (i += 8; i > 0; i--, hp--)
+ hp->hash = -1;
+}
+
+/*
+ * Copyright (c) 1985, 1986 The Regents of the University of California.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * James A. Woods, derived from original work by Spencer Thomas
+ * and Joseph Orost.
+ *
+ * Redistribution and use in source and binary forms are permitted
+ * provided that the above copyright notice and this paragraph are
+ * duplicated in all such forms and that any documentation,
+ * advertising materials, and other materials related to such
+ * distribution and use acknowledge that the software was developed
+ * by the University of California, Berkeley. The name of the
+ * University may not be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
+ * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+ */
+
+void *
+_cairo_compress_lzw (void *data, unsigned long data_size, unsigned long *compressed_size)
+{
+ LZWCodecState state;
+
+ if (!LZWSetupEncode (&state))
+ goto bail0;
+
+ state.out_buffer_size = data_size/4;
+ /* We need *some* space at least */
+ if (state.out_buffer_size < 256)
+ state.out_buffer_size = 256;
+ state.out_buffer = malloc (state.out_buffer_size);
+ if (state.out_buffer == NULL)
+ goto bail1;
+
+ state.out_buffer_pos = state.out_buffer;
+ state.out_buffer_bytes = 0;
+
+ LZWPreEncode (&state);
+ if (!LZWEncode (&state, data, data_size))
+ goto bail2;
+ if (!LZWPostEncode(&state))
+ goto bail2;
+
+ LZWFreeEncode(&state);
+
+ *compressed_size = state.out_buffer_bytes;
+ return state.out_buffer;
+
+ bail2:
+ if (state.out_buffer)
+ free (state.out_buffer);
+ bail1:
+ LZWFreeEncode(&state);
+ bail0:
+ return NULL;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-02 01:24:03 +0000