1 /* Sarien - A Sierra AGI resource interpreter engine
2 * Copyright (C) 1999-2001 Stuart George and Claudio Matsuoka
3 *
4 * $Id: lzw.c,v 1.4 2001/04/26 16:16:33 cmatsuoka Exp $
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; see docs/COPYING for further details.
9 */
10
11 /***************************************************************************
12 ** decomp.c
13 **
14 ** Routines that deal with AGI version 3 specific features.
15 ** The original LZW code is from DJJ, October 1989, p.86.
16 ** It has been modified to handle AGI compression.
17 **
18 ** (c) 1997 Lance Ewing
19 ***************************************************************************/
20
21 #include <stdio.h>
22 #include <string.h>
23
24 #include "sarien.h"
25 #include "lzw.h"
26
27 #define MAXBITS 12
28 #define TABLE_SIZE 18041 /* strange number */
29 #define START_BITS 9
30
31 SINT32 BITS, MAX_VALUE, MAX_CODE;
32 UINT32 *prefix_code;
33 UINT8 *append_character;
34 UINT8 *decode_stack;
35 static SINT32 input_bit_count=0; /* Number of bits in input bit buffer */
36 static UINT32 input_bit_buffer=0L;
37
initLZW()38 void initLZW ()
39 {
40 decode_stack = calloc (1, 8192);
41 prefix_code= malloc (TABLE_SIZE * sizeof(UINT32));
42 append_character= malloc (TABLE_SIZE * sizeof(UINT8));
43 input_bit_count = 0; /* Number of bits in input bit buffer */
44 input_bit_buffer = 0L;
45 }
46
closeLZW()47 void closeLZW ()
48 {
49 free (decode_stack);
50 free (prefix_code);
51 free (append_character);
52 }
53
54 /***************************************************************************
55 ** setBITS
56 **
57 ** Purpose: To adjust the number of bits used to store codes to the value
58 ** passed in.
59 ***************************************************************************/
setBITS(SINT32 value)60 int setBITS (SINT32 value)
61 {
62 if (value == MAXBITS)
63 return TRUE;
64
65 BITS = value;
66 MAX_VALUE = (1 << BITS) - 1;
67 MAX_CODE = MAX_VALUE - 1;
68
69 return FALSE;
70 }
71
72 /***************************************************************************
73 ** decode_string
74 **
75 ** Purpose: To return the string that the code taken from the input buffer
76 ** represents. The string is returned as a stack, i.e. the characters are
77 ** in reverse order.
78 ***************************************************************************/
decode_string(UINT8 * buffer,UINT32 code)79 UINT8 *decode_string(UINT8 *buffer, UINT32 code)
80 {
81 UINT32 i;
82
83 for (i = 0; code > 255; ) {
84 *buffer++ = append_character[code];
85 code=prefix_code[code];
86 if (i++ >= 4000) {
87 fprintf (stderr, "lzw: error in code expansion.\n");
88 abort ();
89 }
90 }
91 *buffer = code;
92
93 return buffer;
94 }
95
96 /***************************************************************************
97 ** input_code
98 **
99 ** Purpose: To return the next code from the input buffer.
100 ***************************************************************************/
input_code(UINT8 ** input)101 UINT32 input_code (UINT8 **input)
102 {
103 UINT32 r;
104
105 while (input_bit_count <= 24) {
106 input_bit_buffer |= (UINT32) *(*input)++ << input_bit_count;
107 input_bit_count += 8;
108 }
109 r = (input_bit_buffer & 0x7FFF) % (1 << BITS);
110 input_bit_buffer >>= BITS;
111 input_bit_count -= BITS;
112
113 return r;
114 }
115
116 /***************************************************************************
117 ** expand
118 **
119 ** Purpose: To uncompress the data contained in the input buffer and store
120 ** the result in the output buffer. The fileLength parameter says how
121 ** many bytes to uncompress. The compression itself is a form of LZW that
122 ** adjusts the number of bits that it represents its codes in as it fills
123 ** up the available codes. Two codes have special meaning:
124 **
125 ** code 256 = start over
126 ** code 257 = end of data
127 ***************************************************************************/
LZW_expand(UINT8 * in,UINT8 * out,SINT32 len)128 void LZW_expand(UINT8 *in, UINT8 *out, SINT32 len)
129 {
130 SINT32 lzwnext, lzwnew, lzwold;
131 SINT32 c, bits;
132 UINT8 *s, *end;
133
134 initLZW();
135
136 bits = setBITS(START_BITS); /* Starts at 9-bits */
137 lzwnext = 257; /* Next available code to define */
138
139 end = (unsigned char *)((long)out + (long)len);
140
141 lzwold = input_code(&in); /* Read in the first code */
142 c = lzwold;
143 lzwnew = input_code(&in);
144
145 while ((out < end) && (lzwnew != 0x101)) {
146 if (lzwnew == 0x100) {
147 /* Code to "start over" */
148 lzwnext = 258;
149 bits = setBITS(START_BITS);
150 lzwold = input_code(&in);
151 c = lzwold;
152 *out++ = (char)c;
153 lzwnew = input_code(&in);
154 } else {
155 if (lzwnew >= lzwnext) {
156 /* Handles special LZW scenario */
157 *decode_stack = c;
158 s = decode_string(decode_stack+1, lzwold);
159 }
160 else
161 s = decode_string(decode_stack, lzwnew);
162
163 /* Reverse order of decoded string and
164 * store in out buffer
165 */
166 c = *s;
167 while (s >= decode_stack)
168 *out++ = *s--;
169
170 if (lzwnext > MAX_CODE)
171 bits = setBITS(BITS + 1);
172
173 prefix_code[lzwnext] = lzwold;
174 append_character[lzwnext] = c;
175 lzwnext++;
176 lzwold = lzwnew;
177
178 lzwnew = input_code(&in);
179 }
180 }
181 closeLZW ();
182 }
183
184