source: abuse/trunk/src/imlib/decoder.cpp @ 112

Last change on this file since 112 was 112, checked in by Sam Hocevar, 11 years ago
  • Fix spelling errors all over the place.
File size: 10.9 KB
Line 
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 */
18
19/*#include "std.h" */
20#include "errs.h"
21#include "image.hpp"
22#include "macs.hpp"
23#include <stdio.h>
24FILE *ufp;
25
26/*IMPORT TEXT *malloc();  */               /* Standard C library allocation */
27
28/* IMPORT INT get_byte()
29 *
30 *   - This external (machine specific) function is expected to return
31 * either the next byte from the GIF file, or a negative number, as
32 * defined in ERRS.H.
33 */
34
35/* IMPORT INT out_line(pixels, linelen)
36 *     UBYTE pixels[];
37 *     INT linelen;
38 *
39 *   - This function takes a full line of pixels (one byte per pixel) and
40 * displays them (or does whatever your program wants with them...).  It
41 * should return zero, or negative if an error or some other event occurs
42 * which would require aborting the decode process...  Note that the length
43 * passed will almost always be equal to the line length passed to the
44 * decoder function, with the sole exception occurring when an ending code
45 * occurs in an odd place in the GIF file...  In any case, linelen will be
46 * equal to the number of pixels passed...
47 */
48/*IMPORT INT out_line(); */
49
50/* IMPORT INT bad_code_count;
51 *
52 * This value is the only other global required by the using program, and
53 * is incremented each time an out of range code is read by the decoder.
54 * When this value is non-zero after a decode, your GIF file is probably
55 * corrupt in some way...
56 */
57int bad_code_count;
58
59#define MAX_CODES   4095
60
61/* Static variables */
62short curr_size;                     /* The current code size */
63short clear;                         /* Value for a clear code */
64short ending;                        /* Value for a ending code */
65short newcodes;                      /* First available code */
66short top_slot;                      /* Highest code for current size */
67short slot;                          /* Last read code */
68
69/* The following static variables are used
70 * for separating out codes
71 */
72short navail_bytes = 0;              /* # bytes left in block */
73short nbits_left = 0;                /* # bits left in current byte */
74  unsigned char b1;                           /* Current byte */
75  unsigned char byte_buff[257];               /* Current block */
76  unsigned char *pbytes;                      /* Pointer to next byte in block */
77
78  long code_mask[13] = {
79     0,
80     0x0001, 0x0003,
81     0x0007, 0x000F,
82     0x001F, 0x003F,
83     0x007F, 0x00FF,
84     0x01FF, 0x03FF,
85     0x07FF, 0x0FFF
86     };
87
88
89/* This function initializes the decoder for reading a new image.
90 */
91short init_exp(short size)
92   {
93   curr_size = size + 1;
94   top_slot = 1 << curr_size;
95   clear = 1 << size;
96   ending = clear + 1;
97   slot = newcodes = ending + 1;
98   navail_bytes = nbits_left = 0;
99   return(0);
100   }
101
102/* get_next_code()
103 * - gets the next code from the GIF file.  Returns the code, or else
104 * a negative number in case of file errors...
105 */
106
107short int get_byte()
108{
109  short int x=0;
110  if (fread(&x,1,1,ufp)!=1)
111    return READ_ERROR;
112  else return x;
113}
114
115short get_next_code()
116   {
117   short i, x;
118   unsigned long ret;
119
120   if (nbits_left == 0)
121      {
122      if (navail_bytes <= 0)
123         {
124
125         /* Out of bytes in current block, so read next block
126          */
127         pbytes = byte_buff;
128         if ((navail_bytes = get_byte()) < 0)
129            return(navail_bytes);
130         else if (navail_bytes)
131            {
132            for (i = 0; i < navail_bytes; ++i)
133               {
134               if ((x = get_byte()) < 0)
135                  return(x);
136               byte_buff[i] = x;
137               }
138            }
139         }
140      b1 = *pbytes++;
141      nbits_left = 8;
142      --navail_bytes;
143      }
144
145   ret = b1 >> (8 - nbits_left);
146   while (curr_size > nbits_left)
147      {
148      if (navail_bytes <= 0)
149         {
150
151         /* Out of bytes in current block, so read next block
152          */
153         pbytes = byte_buff;
154         if ((navail_bytes = get_byte()) < 0)
155            return(navail_bytes);
156         else if (navail_bytes)
157            {
158            for (i = 0; i < navail_bytes; ++i)
159               {
160               if ((x = get_byte()) < 0)
161                  return(x);
162               byte_buff[i] = x;
163               }
164            }
165         }
166      b1 = *pbytes++;
167      ret |= b1 << nbits_left;
168      nbits_left += 8;
169      --navail_bytes;
170      }
171   nbits_left -= curr_size;
172   ret &= code_mask[curr_size];
173   return((short)(ret));
174   }
175
176
177/* The reason we have these separated like this instead of using
178 * a structure like the original Wilhite code did, is because this
179 * stuff generally produces significantly faster code when compiled...
180 * This code is full of similar speedups...  (For a good book on writing
181 * C for speed or for space optomisation, see Efficient C by Tom Plum,
182 * published by Plum-Hall Associates...)
183 */
184  unsigned char stack[MAX_CODES + 1];            /* Stack for storing pixels */
185  unsigned char suffix[MAX_CODES + 1];           /* Suffix table */
186  unsigned short prefix[MAX_CODES + 1];           /* Prefix linked list */
187
188/* short decoder(linewidth)
189 *    short linewidth;               * Pixels per line of image *
190 *
191 * - This function decodes an LZW image, according to the method used
192 * in the GIF spec.  Every *linewidth* "characters" (ie. pixels) decoded
193 * will generate a call to out_line(), which is a user specific function
194 * to display a line of pixels.  The function gets its codes from
195 * get_next_code() which is responsible for reading blocks of data and
196 * separating them into the proper size codes.  Finally, get_byte() is
197 * the global routine to read the next byte from the GIF file.
198 *
199 * It is generally a good idea to have linewidth correspond to the actual
200 * width of a line (as specified in the Image header) to make your own
201 * code a bit simpler, but it isn't absolutely necessary.
202 *
203 * Returns: 0 if successful, else negative.  (See ERRS.H)
204 *
205 */
206
207short decode_gif_data(image *im, FILE *fp)
208
209   {
210   register unsigned char *sp, *bufptr;
211   unsigned char *buf;
212   register short code, fc, oc, bufcnt;
213   short c, size, ret,y;
214   ufp=fp;
215   /* Initialize for decoding a new image...
216    */
217   if ((size = get_byte()) < 0)
218      return(size);
219   if (size < 2 || 9 < size)
220      return(BAD_CODE_SIZE);
221   init_exp(size);
222
223   /* Initialize in case they forgot to put in a clear code.
224    * (This shouldn't happen, but we'll try and decode it anyway...)
225    */
226   oc = fc = 0;
227
228   /* Allocate space for the decode buffer
229    */
230   buf=im->scan_line(0);  y=0;
231/*   if ((buf = (unsigned char *)malloc(linewidth + 1)) == NULL)
232      return(OUT_OF_MEMORY); */
233
234   /* Set up the stack pointer and decode buffer pointer
235    */
236   sp = stack;
237   bufptr = buf;
238   bufcnt = im->height();
239
240   /* This is the main loop.  For each code we get we pass through the
241    * linked list of prefix codes, pushing the corresponding "character" for
242    * each code onto the stack.  When the list reaches a single "character"
243    * we push that on the stack too, and then start unstacking each
244    * character for output in the correct order.  Special handling is
245    * included for the clear code, and the whole thing ends when we get
246    * an ending code.
247    */
248   while ((c = get_next_code()) != ending)
249      {
250
251      /* If we had a file error, return without completing the decode
252       */
253      if (c < 0)
254         {
255//       free(buf);
256         return(0);
257         }
258
259      /* If the code is a clear code, reinitialize all necessary items.
260       */
261      if (c == clear)
262         {
263         curr_size = size + 1;
264         slot = newcodes;
265         top_slot = 1 << curr_size;
266
267         /* Continue reading codes until we get a non-clear code
268          * (Another unlikely, but possible case...)
269          */
270         while ((c = get_next_code()) == clear)
271            ;
272
273         /* If we get an ending code immediately after a clear code
274          * (Yet another unlikely case), then break out of the loop.
275          */
276         if (c == ending)
277            break;
278
279         /* Finally, if the code is beyond the range of already set codes,
280          * (This one had better NOT happen...  I have no idea what will
281          * result from this, but I doubt it will look good...) then set it
282          * to color zero.
283          */
284        CONDITION(c<slot,"Error occurred while reading gif");
285         if (c >= slot)
286            c = 0;
287
288         oc = fc = c;
289
290         /* And let us not forget to put the char into the buffer... And
291          * if, on the off chance, we were exactly one pixel from the end
292          * of the line, we have to send the buffer to the out_line()
293          * routine...
294          */
295         *bufptr++ = c;
296         if (--bufcnt == 0)
297            {
298
299//          if ((ret = out_line(buf, linewidth)) < 0)
300//             {
301//             free(buf);
302//             return(ret);
303//             }
304            y++;
305            if (y<im->height())
306              buf=im->scan_line(y);
307            bufptr = buf;
308            bufcnt = im->width()-1;
309            }
310         }
311      else
312         {
313
314         /* In this case, it's not a clear code or an ending code, so
315          * it must be a code code...  So we can now decode the code into
316          * a stack of character codes. (Clear as mud, right?)
317          */
318         code = c;
319
320         /* Here we go again with one of those off chances...  If, on the
321          * off chance, the code we got is beyond the range of those already
322          * set up (Another thing which had better NOT happen...) we trick
323          * the decoder into thinking it actually got the last code read.
324          * (Hmmn... I'm not sure why this works...  But it does...)
325          */
326
327         if (code >= slot)
328            {
329            if (code > slot)
330               ++bad_code_count;
331            code = oc;
332            *sp++ = fc;
333            }
334
335         /* Here we scan back along the linked list of prefixes, pushing
336          * helpless characters (ie. suffixes) onto the stack as we do so.
337          */
338         while (code >= newcodes)
339            {
340            *sp++ = suffix[code];
341            code = prefix[code];
342            }
343
344         /* Push the last character on the stack, and set up the new
345          * prefix and suffix, and if the required slot number is greater
346          * than that allowed by the current bit size, increase the bit
347          * size.  (NOTE - If we are all full, we *don't* save the new
348          * suffix and prefix...  I'm not certain if this is correct...
349          * it might be more proper to overwrite the last code...
350          */
351         *sp++ = code;
352         if (slot < top_slot)
353            {
354            suffix[slot] = fc = code;
355            prefix[slot++] = oc;
356            oc = c;
357            }
358         if (slot >= top_slot)
359            if (curr_size < 12)
360               {
361               top_slot <<= 1;
362               ++curr_size;
363               }
364
365         /* Now that we've pushed the decoded string (in reverse order)
366          * onto the stack, lets pop it off and put it into our decode
367          * buffer...  And when the decode buffer is full, write another
368          * line...
369          */
370         while (sp > stack)
371            {
372            *bufptr++ = *(--sp);
373            if (--bufcnt == 0)
374               {
375/*             if ((ret = out_line(buf, linewidth)) < 0)
376                  {
377                  free(buf);
378                  return(ret);
379                  } */
380               y++;
381               if (y<im->height())
382                 buf=im->scan_line(y);
383
384               bufptr = buf;
385               bufcnt = im->width()-1;
386               }
387            }
388         }
389      }
390   ret = 0;
391   return(ret);
392   }
393
Note: See TracBrowser for help on using the repository browser.