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

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