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