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