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