File: common\decoder.c
1 /* DECODE.C - An LZW decoder for GIF
2 * Copyright (C) 1987, by Steven A. Bennett
3 *
4 * Permission is given by the author to freely redistribute and include
5 * this code in any program as long as this credit is given where due.
6 *
7 * In accordance with the above, I want to credit Steve Wilhite who wrote
8 * the code which this is heavily inspired by...
9 *
10 * GIF and 'Graphics Interchange Format' are trademarks (tm) of
11 * Compuserve, Incorporated, an H&R Block Company.
12 *
13 * Release Notes: This file contains a decoder routine for GIF images
14 * which is similar, structurally, to the original routine by Steve Wilhite.
15 * It is, however, somewhat noticably faster in most cases.
16 *
17 == This routine was modified for use in FRACTINT in two ways.
18 ==
19 == 1) The original #includes were folded into the routine strictly to hold
20 == down the number of files we were dealing with.
21 ==
22 == 2) The 'stack', 'suffix', 'prefix', and 'decoderline' arrays were
23 == changed from static and 'malloc()'ed to external only so that
24 == the assembler program could use the same array space for several
25 == independent chunks of code. Also, 'stack' was renamed to 'dstack'
26 == for TASM compatibility.
27 ==
28 == 3) The 'out_line()' external function has been changed to reference
29 == '*outln()' for flexibility (in particular, 3D transformations)
30 ==
31 == 4) A call to 'keypressed()' has been added after the 'outln()' calls
32 == to check for the presenc of a key-press as a bail-out signal
33 ==
34 == (Bert Tyler and Timothy Wegner)
35 */
36
37 /* Rev 01/02/91 - Revised by Mike Gelvin
38 * altered logic to allow newcode to input a line at a time
39 * altered logic to allow decoder to place characters
40 * directly into the output buffer if they fit
41 */
42
43
44 /***** Application Includes *********************************************/
45 /* see Fractint.c for a description of the "include" hierarchy */
46 #include "port.h"
47 #include "prototyp.h"
48
49 /***** Application Function Prototypes **********************************/
50 static short get_next_code(void);
51
52 /* extern short out_line(pixels, linelen)
53 * UBYTE pixels[];
54 * short linelen;
55 *
56 * - This function takes a full line of pixels (one byte per pixel) and
57 * displays them (or does whatever your program wants with them...). It
58 * should return zero, or negative if an error or some other event occurs
59 * which would require aborting the decode process... Note that the length
60 * passed will almost always be equal to the line length passed to the
61 * decoder function, with the sole exception occurring when an ending code
62 * occurs in an odd place in the GIF file... In any case, linelen will be
63 * equal to the number of pixels passed...
64 */
65 int (*outln) (BYTE *, int) = out_line;
66
67 /***** Local Static Variables *******************************************/
68 /* Various error codes used by decoder
69 * and my own routines... It's okay
70 * for you to define whatever you want,
71 * as long as it's negative... It will be
72 * returned intact up the various subroutine
73 * levels...
74 */
75 #define OUT_OF_MEMORY -10
76 #define BAD_CODE_SIZE -20
77 #define READ_ERROR -1
78 #define WRITE_ERROR -2
79 #define OPEN_ERROR -3
80 #define CREATE_ERROR -4
81
82 #define MAX_CODES 4095
83
84 #define NOPE 0
85 #define YUP -1
86
87 static short curr_size; /* The current code size */
88
89 /* The following static variables are used
90 * for seperating out codes
91 */
92 static short navail_bytes; /* # bytes left in block */
93 static short nbits_left; /* # bits left in current byte */
94 static BYTE *byte_buff; /* Current block, reuse shared mem */
95 static BYTE *pbytes; /* Pointer to next byte in block */
96
97 static short code_mask[13] =
98 {
99 0,
100 0x0001, 0x0003,
101 0x0007, 0x000F,
102 0x001F, 0x003F,
103 0x007F, 0x00FF,
104 0x01FF, 0x03FF,
105 0x07FF, 0x0FFF
106 };
107
108 /***** External Variables ***********************************************/
109 /* extern short bad_code_count;
110 *
111 * This value is the only other global required by the using program, and
112 * is incremented each time an out of range code is read by the decoder.
113 * When this value is non-zero after a decode, your GIF file is probably
114 * corrupt in some way...
115 *
116 * whups, here are more globals, added by PB:
117 * extern short skipxdots; 0 to get every dot, 1 for every 2nd, 2 every 3rd, ...
118 * extern short skipydots;
119 *
120 * All external declarations now in PROTOTYPE.H
121 */
122
123
124 /*
125 I removed the LOCAL identifiers in the arrays below and replaced them
126 with 'extern's so as to declare (and re-use) the space elsewhere.
127 The arrays are actually declared in the assembler source.
128 Bert Tyler
129 */
130
131 #if 0
137 #endif
138
139 /* avoid using fixed near arrays by enabling next */
140 #if 0
143 #endif
144
145 #if 0 /* remove this when suffix no longer used in diskvid.c */
148 #endif
149
150 #if 0
153 #endif
154
155 /* for the time being, use a pointer to a buffer in the gifview stack */
156 extern BYTE *decoderline1;
157 #define decoderline decoderline1
158
159 /* The reason we have these separated like this instead of using
160 * a structure like the original Wilhite code did, is because this
161 * stuff generally produces significantly faster code when compiled...
162 * This code is full of similar speedups... (For a good book on writing
163 * C for speed or for space optimization, see Efficient C by Tom Plum,
164 * published by Plum-Hall Associates...)
165 */
166
167
168 /***** Program **********************************************************/
169 /* short decoder(linewidth)
170 * short linewidth; * Pixels per line of image *
171 *
172 * - This function decodes an LZW image, according to the method used
173 * in the GIF spec. Every *linewidth* "characters" (ie. pixels) decoded
174 * will generate a call to out_line(), which is a user specific function
175 * to display a line of pixels. The function gets its codes from
176 * get_next_code() which is responsible for reading blocks of data and
177 * seperating them into the proper size codes. Finally, get_byte() is
178 * the global routine to read the next byte from the GIF file.
179 *
180 * It is generally a good idea to have linewidth correspond to the actual
181 * width of a line (as specified in the Image header) to make your own
182 * code a bit simpler, but it isn't absolutely necessary.
183 *
184 * Returns: 0 if successful, else negative. (See ERRS.H)
185 *
186 */
187
188 /* moved sizeofstring here for possible re-use elsewhere */
189 short far sizeofstring[MAX_CODES + 1]; /* size of string list */
190
191 short decoder(short linewidth)
192 {
193 #ifdef XFRACT
195 #endif
196 BYTE far *sp;
197 short code;
198 short old_code;
199 short ret;
200 short c;
201 short size;
202 short i;
203 short j;
204 short fastloop;
205 short bufcnt; /* how many empty spaces left in buffer */
206 short xskip;
207 short slot; /* Last read code */
208 short newcodes; /* First available code */
209 BYTE *bufptr;
210 short yskip;
211 short top_slot; /* Highest code for current size */
212 short clear; /* Value for a clear code */
213 short ending; /* Value for a ending code */
214 BYTE out_value;
215
216 /* Initialize for decoding a new image... */
217
218 if ((size = (short) get_byte()) < 0)
219 return (size);
220 if (size < 2 || 9 < size)
221 return (BAD_CODE_SIZE);
222
223 curr_size = (short) (size + 1);
224 top_slot = (short) (1 << curr_size);
225 clear = (short) (1 << size);
226 ending = (short) (clear + 1);
227 slot = newcodes = (short) (ending + 1);
228 navail_bytes = nbits_left = sizeofstring[slot] = xskip = yskip
229 = old_code = 0;
230 out_value = 0;
231 for (i = 0; i < slot; i++)
232 {
233 sizeofstring[i] = 0;
234 }
235
236 /* Initialize in case they forgot to put in a clear code. (This shouldn't
237 * happen, but we'll try and decode it anyway...) */
238
239 /* Set up the stack pointer and decode buffer pointer */
240 sp = dstack;
241 bufptr = decoderline;
242 bufcnt = linewidth;
243
244 /* This is the main loop. For each code we get we pass through the linked
245 * list of prefix codes, pushing the corresponding "character" for each
246 * code onto the stack. When the list reaches a single "character" we
247 * push that on the stack too, and then start unstacking each character
248 * for output in the correct order. Special handling is included for the
249 * clear code, and the whole thing ends when we get an ending code. */
250 while ((c = get_next_code()) != ending)
251 {
252
253 /* If we had a file error, return without completing the decode */
254 if (c < 0)
255 return (0);
256
257 /* If the code is a clear code, reinitialize all necessary items. */
258 if (c == clear)
259 {
260 curr_size = (short) (size + 1);
261 slot = newcodes;
262 sizeofstring[slot] = 0;
263 top_slot = (short) (1 << curr_size);
264
265 /* Continue reading codes until we get a non-clear code (Another
266 * unlikely, but possible case...) */
267 while ((c = get_next_code()) == clear)
268 ;
269
270 /* If we get an ending code immediately after a clear code (Yet
271 * another unlikely case), then break out of the loop. */
272 if (c == ending)
273 break;
274
275 /* Finally, if the code is beyond the range of already set codes,
276 * (This one had better NOT happen... I have no idea what will
277 * result from this, but I doubt it will look good...) then set it
278 * to color zero. */
279 if (c >= slot)
280 c = 0;
281
282 out_value = (BYTE) (old_code = c);
283
284 /* And let us not forget to put the char into the buffer... */
285 *sp++ = (BYTE) c;
286 }
287 else
288 {
289 /* In this case, it's not a clear code or an ending code, so it must
290 * be a code code... So we can now decode the code into a stack of
291 * character codes. (Clear as mud, right?) */
292 code = c;
293
294 /* Here we go again with one of those off chances... If, on the off
295 * chance, the code we got is beyond the range of those already set
296 * up (Another thing which had better NOT happen...) we trick the
297 * decoder into thinking it actually got the next slot avail. */
298
299 if (code >= slot)
300 {
301 if (code > slot)
302 {
303 ++bad_code_count;
304 c = slot;
305 }
306 code = old_code;
307 *sp++ = out_value;
308 }
309
310 /* Here we scan back along the linked list of prefixes. If they can
311 * fit into the output buffer then transfer them direct. ELSE push
312 * them into the stack until we are down to enough characters that
313 * they do fit. Output the line then fall through to unstack the
314 * ones that would not fit. */
315 fastloop = NOPE;
316 while (code >= newcodes)
317 {
318 j = i = sizeofstring[code];
319 if (i > 0 && bufcnt - i > 0 && skipxdots == 0)
320 {
321 fastloop = YUP;
322
323 do
324 {
325 *(bufptr + j) = suffix[code];
326 code = prefix[code];
327 } while (--j > 0);
328 *bufptr = (BYTE) code;
329 bufptr += ++i;
330 bufcnt -= i;
331 if (bufcnt == 0) /* finished an input row? */
332 {
333 if (--yskip < 0)
334 {
335 if ((ret = (short) ((*outln) (decoderline, bufptr - decoderline))) < 0)
336 return (ret);
337 yskip = skipydots;
338 }
339 if (keypressed())
340 return (-1);
341 bufptr = decoderline;
342 bufcnt = linewidth;
343 xskip = 0;
344 }
345 }
346 else
347 {
348 *sp++ = suffix[code];
349 code = prefix[code];
350 }
351 }
352
353 /* Push the last character on the stack, and set up the new prefix
354 * and suffix, and if the required slot number is greater than that
355 * allowed by the current bit size, increase the bit size. (NOTE -
356 * If we are all full, we *don't* save the new suffix and prefix...
357 * I'm not certain if this is correct... it might be more proper to
358 * overwrite the last code... */
359 if (fastloop == NOPE)
360 *sp++ = (BYTE) code;
361
362 if (slot < top_slot)
363 {
364 sizeofstring[slot] = (short) (sizeofstring[old_code] + 1);
365 suffix[slot] = out_value = (BYTE) code;
366 prefix[slot++] = old_code;
367 old_code = c;
368 }
369 if (slot >= top_slot)
370 if (curr_size < 12)
371 {
372 top_slot <<= 1;
373 ++curr_size;
374 }
375 }
376 while (sp > dstack)
377 {
378 --sp;
379 if (--xskip < 0)
380 {
381 xskip = skipxdots;
382 *bufptr++ = *sp;
383 }
384 if (--bufcnt == 0) /* finished an input row? */
385 {
386 if (--yskip < 0)
387 {
388 if ((ret = (short) ((*outln) (decoderline, bufptr - decoderline))) < 0)
389 return (ret);
390 yskip = skipydots;
391 }
392 if (keypressed())
393 return (-1);
394 bufptr = decoderline;
395 bufcnt = linewidth;
396 xskip = 0;
397 }
398 }
399 }
400 /* PB note that if last line is incomplete, we're not going to try to emit
401 * it; original code did, but did so via out_line and therefore couldn't
402 * have worked well in all cases... */
403 return (0);
404 }
405
406 /***** Program **********************************************************/
407 /* get_next_code()
408 * - gets the next code from the GIF file. Returns the code, or else
409 * a negative number in case of file errors...
410 */
411 static short get_next_code()
412 {
413 static BYTE b1; /* Current byte */
414 static unsigned short ret_code;
415
416 if (nbits_left == 0)
417 {
418 if (navail_bytes <= 0)
419 {
420
421 /* Out of bytes in current block, so read next block */
422 pbytes = byte_buff;
423 if ((navail_bytes = (short) get_byte()) < 0)
424 return (navail_bytes);
425 else if (navail_bytes)
426 get_bytes(byte_buff, navail_bytes);
427 }
428 b1 = *pbytes++;
429 nbits_left = 8;
430 --navail_bytes;
431 }
432
433 ret_code = (short) (b1 >> (8 - nbits_left));
434 while (curr_size > nbits_left)
435 {
436 if (navail_bytes <= 0)
437 {
438
439 /* Out of bytes in current block, so read next block */
440 pbytes = byte_buff;
441 if ((navail_bytes = (short) get_byte()) < 0)
442 return (navail_bytes);
443 else if (navail_bytes)
444 get_bytes(byte_buff, navail_bytes);
445 }
446 b1 = *pbytes++;
447 ret_code |= b1 << nbits_left;
448 nbits_left += 8;
449 --navail_bytes;
450 }
451 nbits_left -= curr_size;
452 return ((short) (ret_code & code_mask[curr_size]));
453 }
454
455 /* called in parent reoutine to set byte_buff */
456 void set_byte_buff(BYTE * ptr)
457 {
458 byte_buff = ptr;
459 }
460