home *** CD-ROM | disk | FTP | other *** search
/ Photo CD Demo 1 / Demo.bin / fractint / fras1611.zip / DECODER.C < prev    next >
Text File  |  1990-10-18  |  13KB  |  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)(UTINY *,INT) = 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. /* whups, here are more globals, added by PB: */
  102. IMPORT INT skipxdots; /* 0 to get every dot, 1 for every 2nd, 2 every 3rd, ... */
  103. IMPORT INT skipydots; /* ditto for rows */
  104.  
  105. #define NULL   0L
  106. #define MAX_CODES   4095
  107.  
  108. /* Static variables */
  109. LOCAL WORD curr_size;              /* The current code size */
  110. LOCAL WORD clear;              /* Value for a clear code */
  111. LOCAL WORD ending;              /* Value for a ending code */
  112. LOCAL WORD newcodes;              /* First available code */
  113. LOCAL WORD top_slot;              /* Highest code for current size */
  114. LOCAL WORD slot;              /* Last read code */
  115.  
  116. /* The following static variables are used
  117.  * for seperating out codes
  118.  */
  119. LOCAL WORD navail_bytes = 0;          /* # bytes left in block */
  120. LOCAL WORD nbits_left = 0;          /* # bits left in current byte */
  121. LOCAL UTINY b1;               /* Current byte */
  122. LOCAL UTINY byte_buff[257];          /* Current block, reuse shared mem */
  123. LOCAL UTINY *pbytes;              /* Pointer to next byte in block */
  124.  
  125. LOCAL LONG code_mask[13] = {
  126.      0,
  127.      0x0001, 0x0003,
  128.      0x0007, 0x000F,
  129.      0x001F, 0x003F,
  130.      0x007F, 0x00FF,
  131.      0x01FF, 0x03FF,
  132.      0x07FF, 0x0FFF
  133.      };
  134.  
  135.  
  136. /* This function initializes the decoder for reading a new image.
  137.  */
  138. LOCAL WORD init_exp(size)
  139.    WORD size;
  140.    {
  141.    curr_size = size + 1;
  142.    top_slot = 1 << curr_size;
  143.    clear = 1 << size;
  144.    ending = clear + 1;
  145.    slot = newcodes = ending + 1;
  146.    navail_bytes = nbits_left = 0;
  147.    return(0);
  148.    }
  149.  
  150. /* get_next_code()
  151.  * - gets the next code from the GIF file.  Returns the code, or else
  152.  * a negative number in case of file errors...
  153.  */
  154. LOCAL WORD get_next_code()
  155.    {
  156.    WORD i, x;
  157.    ULONG ret;
  158.  
  159.    if (nbits_left == 0)
  160.       {
  161.       if (navail_bytes <= 0)
  162.      {
  163.  
  164.      /* Out of bytes in current block, so read next block
  165.       */
  166.      pbytes = byte_buff;
  167.      if ((navail_bytes = get_byte()) < 0)
  168.         return(navail_bytes);
  169.      else if (navail_bytes)
  170.         {
  171.         for (i = 0; i < navail_bytes; ++i)
  172.            {
  173.            if ((x = get_byte()) < 0)
  174.           return(x);
  175.            byte_buff[i] = x;
  176.            }
  177.         }
  178.      }
  179.       b1 = *pbytes++;
  180.       nbits_left = 8;
  181.       --navail_bytes;
  182.       }
  183.  
  184.    ret = b1 >> (8 - nbits_left);
  185.    while (curr_size > nbits_left)
  186.       {
  187.       if (navail_bytes <= 0)
  188.      {
  189.  
  190.      /* Out of bytes in current block, so read next block
  191.       */
  192.      pbytes = byte_buff;
  193.      if ((navail_bytes = get_byte()) < 0)
  194.         return(navail_bytes);
  195.      else if (navail_bytes)
  196.         {
  197.         for (i = 0; i < navail_bytes; ++i)
  198.            {
  199.            if ((x = get_byte()) < 0)
  200.           return(x);
  201.            byte_buff[i] = x;
  202.            }
  203.         }
  204.      }
  205.       b1 = *pbytes++;
  206.       ret |= b1 << nbits_left;
  207.       nbits_left += 8;
  208.       --navail_bytes;
  209.       }
  210.    nbits_left -= curr_size;
  211.    ret &= code_mask[curr_size];
  212.    return((WORD)(ret));
  213.    }
  214.  
  215.  
  216. /* The reason we have these seperated like this instead of using
  217.  * a structure like the original Wilhite code did, is because this
  218.  * stuff generally produces significantly faster code when compiled...
  219.  * This code is full of similar speedups...  (For a good book on writing
  220.  * C for speed or for space optomisation, see Efficient C by Tom Plum,
  221.  * published by Plum-Hall Associates...)
  222.  */
  223.  
  224. /*
  225. I removed the LOCAL identifiers in the arrays below and replaced them
  226. with 'extern's so as to declare (and re-use) the space elsewhere.
  227. The arrays are actually declared in the assembler source.
  228.                         Bert Tyler
  229. */
  230.  
  231. extern UTINY dstack[MAX_CODES + 1];          /* Stack for storing pixels */
  232. extern UTINY suffix[MAX_CODES + 1];          /* Suffix table */
  233. extern UWORD prefix[MAX_CODES + 1];          /* Prefix linked list */
  234. extern UTINY decoderline[2];              /* decoded line goes here */
  235.  
  236. /* WORD decoder(linewidth)
  237.  *    WORD linewidth;            * Pixels per line of image *
  238.  *
  239.  * - This function decodes an LZW image, according to the method used
  240.  * in the GIF spec.  Every *linewidth* "characters" (ie. pixels) decoded
  241.  * will generate a call to out_line(), which is a user specific function
  242.  * to display a line of pixels.  The function gets its codes from
  243.  * get_next_code() which is responsible for reading blocks of data and
  244.  * seperating them into the proper size codes.    Finally, get_byte() is
  245.  * the global routine to read the next byte from the GIF file.
  246.  *
  247.  * It is generally a good idea to have linewidth correspond to the actual
  248.  * width of a line (as specified in the Image header) to make your own
  249.  * code a bit simpler, but it isn't absolutely necessary.
  250.  *
  251.  * Returns: 0 if successful, else negative.  (See ERRS.H)
  252.  *
  253.  */
  254.  
  255. WORD decoder(linewidth)
  256.    WORD linewidth;
  257.    {
  258.    FAST UTINY *sp, *bufptr;
  259.    UTINY *buf;
  260.    FAST WORD code, fc, oc, bufcnt;
  261.    WORD c, size, ret;
  262.    WORD xskip,yskip;
  263.  
  264.    /* Initialize for decoding a new image...
  265.     */
  266.    if ((size = get_byte()) < 0)
  267.       return(size);
  268.    if (size < 2 || 9 < size)
  269.       return(BAD_CODE_SIZE);
  270.    init_exp(size);
  271.    xskip = yskip = 0;
  272.  
  273.    /* Initialize in case they forgot to put in a clear code.
  274.     * (This shouldn't happen, but we'll try and decode it anyway...)
  275.     */
  276.    oc = fc = 0;
  277.  
  278.    buf = decoderline;
  279.  
  280.    /* Set up the stack pointer and decode buffer pointer
  281.     */
  282.    sp = dstack;
  283.    bufptr = buf;
  284.    bufcnt = linewidth;
  285.  
  286.    /* This is the main loop.  For each code we get we pass through the
  287.     * linked list of prefix codes, pushing the corresponding "character" for
  288.     * each code onto the stack.  When the list reaches a single "character"
  289.     * we push that on the stack too, and then start unstacking each
  290.     * character for output in the correct order.  Special handling is
  291.     * included for the clear code, and the whole thing ends when we get
  292.     * an ending code.
  293.     */
  294.    while ((c = get_next_code()) != ending)
  295.       {
  296.  
  297.       /* If we had a file error, return without completing the decode
  298.        */
  299.       if (c < 0)
  300.      return(0);
  301.  
  302.       /* If the code is a clear code, reinitialize all necessary items.
  303.        */
  304.       if (c == clear)
  305.      {
  306.      curr_size = size + 1;
  307.      slot = newcodes;
  308.      top_slot = 1 << curr_size;
  309.  
  310.      /* Continue reading codes until we get a non-clear code
  311.       * (Another unlikely, but possible case...)
  312.       */
  313.      while ((c = get_next_code()) == clear)
  314.         ;
  315.  
  316.      /* If we get an ending code immediately after a clear code
  317.       * (Yet another unlikely case), then break out of the loop.
  318.       */
  319.      if (c == ending)
  320.         break;
  321.  
  322.      /* Finally, if the code is beyond the range of already set codes,
  323.       * (This one had better NOT happen...    I have no idea what will
  324.       * result from this, but I doubt it will look good...) then set it
  325.       * to color zero.
  326.       */
  327.      if (c >= slot)
  328.         c = 0;
  329.  
  330.      oc = fc = c;
  331.  
  332.      /* And let us not forget to put the char into the buffer... */
  333.      *sp++ = c; /* let the common code outside the if else stuff it */
  334.      }
  335.       else
  336.      {
  337.  
  338.      /* In this case, it's not a clear code or an ending code, so
  339.       * it must be a code code...  So we can now decode the code into
  340.       * a stack of character codes. (Clear as mud, right?)
  341.       */
  342.      code = c;
  343.  
  344.      /* Here we go again with one of those off chances...  If, on the
  345.       * off chance, the code we got is beyond the range of those already
  346.       * set up (Another thing which had better NOT happen...) we trick
  347.       * the decoder into thinking it actually got the last code read.
  348.       * (Hmmn... I'm not sure why this works...  But it does...)
  349.       */
  350.      if (code >= slot)
  351.         {
  352.         if (code > slot)
  353.            ++bad_code_count;
  354.         code = oc;
  355.         *sp++ = fc;
  356.         }
  357.  
  358.      /* Here we scan back along the linked list of prefixes, pushing
  359.       * helpless characters (ie. suffixes) onto the stack as we do so.
  360.       */
  361.      while (code >= newcodes)
  362.         {
  363.         *sp++ = suffix[code];
  364.         code = prefix[code];
  365.         }
  366.  
  367.      /* Push the last character on the stack, and set up the new
  368.       * prefix and suffix, and if the required slot number is greater
  369.       * than that allowed by the current bit size, increase the bit
  370.       * size.  (NOTE - If we are all full, we *don't* save the new
  371.       * suffix and prefix...  I'm not certain if this is correct...
  372.       * it might be more proper to overwrite the last code...
  373.       */
  374.      *sp++ = code;
  375.      if (slot < top_slot)
  376.         {
  377.         suffix[slot] = fc = code;
  378.         prefix[slot++] = oc;
  379.         oc = c;
  380.         }
  381.      if (slot >= top_slot)
  382.         if (curr_size < 12)
  383.            {
  384.            top_slot <<= 1;
  385.            ++curr_size;
  386.            }
  387.      }
  388.  
  389.       /* Now that we've pushed the decoded string (in reverse order)
  390.        * onto the stack, lets pop it off and put it into our decode
  391.        * buffer...  And when the decode buffer is full, write another
  392.        * line...
  393.        */
  394.       while (sp > dstack)
  395.      {
  396.      --sp;
  397.      if (--xskip < 0)
  398.         {
  399.         xskip = skipxdots;
  400.         *bufptr++ = *sp;
  401.         }
  402.      if (--bufcnt == 0) /* finished an input row? */
  403.         {
  404.         if (--yskip < 0)
  405.            {
  406.            if ((ret = (*outln)(buf, bufptr - buf)) < 0)
  407.           return(ret);
  408.            yskip = skipydots;
  409.            }
  410.         if (keypressed())
  411.            return(-1);
  412.         bufptr = buf;
  413.         bufcnt = linewidth;
  414.         xskip = 0;
  415.         }
  416.      }
  417.       }
  418.    /* PB note that if last line is incomplete, we're not going to try
  419.       to emit it;  original code did, but did so via out_line and therefore
  420.       couldn't have worked well in all cases... */
  421.    return(0);
  422.    }
  423.  
  424.