home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / grafik / gif / gif.c next >
Encoding:
C/C++ Source or Header  |  1990-11-12  |  15.0 KB  |  477 lines
  1. Path: ukma!tut.cis.ohio-state.edu!rutgers!bellcore!texbell!merch!cpe!hal6000!trsvax!johnm
  2. From: johnm@trsvax.UUCP
  3. Newsgroups: comp.graphics
  4. Subject: GIF decoder (shar-ed)
  5. Message-ID: <194300057@trsvax>
  6. Date: 14 Mar 89 22:58:00 GMT
  7. Lines: 466
  8. Nf-ID: #N:trsvax:194300057:000:14585
  9. Nf-From: trsvax.UUCP!johnm    Mar 14 16:58:00 1989
  10.  
  11.  
  12. Everybody seems to want source code for a good GIF decoder.  Here is one of my
  13. favorites.  It was written by Steve Bennett in C and it has the advantage of 
  14. not only being one of the easiest to use decoders but also being one of the 
  15. fastest (of those not written in assembly).
  16.  
  17. The routines only cover the actual decompression and the disposal of the data
  18. (whether it goes to the screen, a buffer, or whatever).  You will need to
  19. write the routines to handle reading the header of a GIF file yourself.  If you
  20. have the spec. this should be a fairly trivial operation as most of the
  21. header info can be described in terms of structures that you can read in.
  22. All the hard stuff is already done for us by Mr. Bennett.
  23.  
  24. John Munsch
  25.  
  26. =============================== Cut Here ================================
  27. #!/bin/sh
  28. # This is a shell archive, meaning:
  29. # 1. Remove everything above the #!/bin/sh line.
  30. # 2. Save the resulting text in a file.
  31. # 3. Execute the file with /bin/sh (not csh) to create the files:
  32. #    decoder.c
  33. #    errs.h
  34. #    std.h
  35. # This archive created: Tue Mar 14 16:47:55 1989
  36. PATH=/bin:$PATH; export PATH
  37. echo shar: extracting "'decoder.c'" '(11918 characters)'
  38. if test -f 'decoder.c'
  39. then
  40.     echo shar: over-writing existing file "'decoder.c'"
  41. fi
  42. cat << \SHAR_EOF > 'decoder.c'
  43. /* DECODE.C - An LZW decoder for GIF
  44.  * Copyright (C) 1987, by Steven A. Bennett
  45.  *
  46.  * Permission is given by the author to freely redistribute and include
  47.  * this code in any program as long as this credit is given where due.
  48.  *
  49.  * In accordance with the above, I want to credit Steve Wilhite who wrote
  50.  * the code which this is heavily inspired by...
  51.  *
  52.  * GIF and 'Graphics Interchange Format' are trademarks (tm) of
  53.  * Compuserve, Incorporated, an H&R Block Company.
  54.  *
  55.  * Release Notes: This file contains a decoder routine for GIF images
  56.  * which is similar, structurally, to the original routine by Steve Wilhite.
  57.  * It is, however, somewhat noticably faster in most cases.
  58.  *
  59.  */
  60.  
  61. #include "std.h"
  62. #include "errs.h"
  63.  
  64. IMPORT TEXT *malloc();                 /* Standard C library allocation */
  65.  
  66. /* IMPORT INT get_byte()
  67.  *
  68.  *   - This external (machine specific) function is expected to return
  69.  * either the next byte from the GIF file, or a negative number, as
  70.  * defined in ERRS.H.
  71.  */
  72. IMPORT INT get_byte();
  73.  
  74. /* IMPORT INT out_line(pixels, linelen)
  75.  *     UBYTE pixels[];
  76.  *     INT linelen;
  77.  *
  78.  *   - This function takes a full line of pixels (one byte per pixel) and
  79.  * displays them (or does whatever your program wants with them...).  It
  80.  * should return zero, or negative if an error or some other event occurs
  81.  * which would require aborting the decode process...  Note that the length
  82.  * passed will almost always be equal to the line length passed to the
  83.  * decoder function, with the sole exception occurring when an ending code
  84.  * occurs in an odd place in the GIF file...  In any case, linelen will be
  85.  * equal to the number of pixels passed...
  86.  */
  87. IMPORT INT out_line();
  88.  
  89. /* IMPORT INT bad_code_count;
  90.  *
  91.  * This value is the only other global required by the using program, and
  92.  * is incremented each time an out of range code is read by the decoder.
  93.  * When this value is non-zero after a decode, your GIF file is probably
  94.  * corrupt in some way...
  95.  */
  96. IMPORT INT bad_code_count;
  97.  
  98. #define NULL   0L
  99. #define MAX_CODES   4095
  100.  
  101. /* Static variables */
  102. LOCAL WORD curr_size;                     /* The current code size */
  103. LOCAL WORD clear;                         /* Value for a clear code */
  104. LOCAL WORD ending;                        /* Value for a ending code */
  105. LOCAL WORD newcodes;                      /* First available code */
  106. LOCAL WORD top_slot;                      /* Highest code for current size */
  107. LOCAL WORD slot;                          /* Last read code */
  108.  
  109. /* The following static variables are used
  110.  * for seperating out codes
  111.  */
  112. LOCAL WORD navail_bytes = 0;              /* # bytes left in block */
  113. LOCAL WORD nbits_left = 0;                /* # bits left in current byte */
  114. LOCAL UTINY b1;                           /* Current byte */
  115. LOCAL UTINY byte_buff[257];               /* Current block */
  116. LOCAL UTINY *pbytes;                      /* Pointer to next byte in block */
  117.  
  118. LOCAL LONG code_mask[13] = {
  119.      0,
  120.      0x0001, 0x0003,
  121.      0x0007, 0x000F,
  122.      0x001F, 0x003F,
  123.      0x007F, 0x00FF,
  124.      0x01FF, 0x03FF,
  125.      0x07FF, 0x0FFF
  126.      };
  127.  
  128.  
  129. /* This function initializes the decoder for reading a new image.
  130.  */
  131. LOCAL WORD init_exp(size)
  132.    WORD size;
  133.    {
  134.    curr_size = size + 1;
  135.    top_slot = 1 << curr_size;
  136.    clear = 1 << size;
  137.    ending = clear + 1;
  138.    slot = newcodes = ending + 1;
  139.    navail_bytes = nbits_left = 0;
  140.    return(0);
  141.    }
  142.  
  143. /* get_next_code()
  144.  * - gets the next code from the GIF file.  Returns the code, or else
  145.  * a negative number in case of file errors...
  146.  */
  147. LOCAL WORD get_next_code()
  148.    {
  149.    WORD i, x;
  150.    ULONG ret;
  151.  
  152.    if (nbits_left == 0)
  153.       {
  154.       if (navail_bytes <= 0)
  155.          {
  156.  
  157.          /* Out of bytes in current block, so read next block
  158.           */
  159.          pbytes = byte_buff;
  160.          if ((navail_bytes = get_byte()) < 0)
  161.             return(navail_bytes);
  162.          else if (navail_bytes)
  163.             {
  164.             for (i = 0; i < navail_bytes; ++i)
  165.                {
  166.                if ((x = get_byte()) < 0)
  167.                   return(x);
  168.                byte_buff[i] = x;
  169.                }
  170.             }
  171.          }
  172.       b1 = *pbytes++;
  173.       nbits_left = 8;
  174.       --navail_bytes;
  175.       }
  176.  
  177.    ret = b1 >> (8 - nbits_left);
  178.    while (curr_size > nbits_left)
  179.       {
  180.       if (navail_bytes <= 0)
  181.          {
  182.  
  183.          /* Out of bytes in current block, so read next block
  184.           */
  185.          pbytes = byte_buff;
  186.          if ((navail_bytes = get_byte()) < 0)
  187.             return(navail_bytes);
  188.          else if (navail_bytes)
  189.             {
  190.             for (i = 0; i < navail_bytes; ++i)
  191.                {
  192.                if ((x = get_byte()) < 0)
  193.                   return(x);
  194.                byte_buff[i] = x;
  195.                }
  196.             }
  197.          }
  198.       b1 = *pbytes++;
  199.       ret |= b1 << nbits_left;
  200.       nbits_left += 8;
  201.       --navail_bytes;
  202.       }
  203.    nbits_left -= curr_size;
  204.    ret &= code_mask[curr_size];
  205.    return((WORD)(ret));
  206.    }
  207.  
  208.  
  209. /* The reason we have these seperated like this instead of using
  210.  * a structure like the original Wilhite code did, is because this
  211.  * stuff generally produces significantly faster code when compiled...
  212.  * This code is full of similar speedups...  (For a good book on writing
  213.  * C for speed or for space optomisation, see Efficient C by Tom Plum,
  214.  * published by Plum-Hall Associates...)
  215.  */
  216. LOCAL UTINY stack[MAX_CODES + 1];            /* Stack for storing pixels */
  217. LOCAL UTINY suffix[MAX_CODES + 1];           /* Suffix table */
  218. LOCAL UWORD prefix[MAX_CODES + 1];           /* Prefix linked list */
  219.  
  220. /* WORD decoder(linewidth)
  221.  *    WORD linewidth;               * Pixels per line of image *
  222.  *
  223.  * - This function decodes an LZW image, according to the method used
  224.  * in the GIF spec.  Every *linewidth* "characters" (ie. pixels) decoded
  225.  * will generate a call to out_line(), which is a user specific function
  226.  * to display a line of pixels.  The function gets it's codes from
  227.  * get_next_code() which is responsible for reading blocks of data and
  228.  * seperating them into the proper size codes.  Finally, get_byte() is
  229.  * the global routine to read the next byte from the GIF file.
  230.  *
  231.  * It is generally a good idea to have linewidth correspond to the actual
  232.  * width of a line (as specified in the Image header) to make your own
  233.  * code a bit simpler, but it isn't absolutely necessary.
  234.  *
  235.  * Returns: 0 if successful, else negative.  (See ERRS.H)
  236.  *
  237.  */
  238.  
  239. WORD decoder(linewidth)
  240.    WORD linewidth;
  241.    {
  242.    FAST UTINY *sp, *bufptr;
  243.    UTINY *buf;
  244.    FAST WORD code, fc, oc, bufcnt;
  245.    WORD c, size, ret;
  246.  
  247.    /* Initialize for decoding a new image...
  248.     */
  249.    if ((size = get_byte()) < 0)
  250.       return(size);
  251.    if (size < 2 || 9 < size)
  252.       return(BAD_CODE_SIZE);
  253.    init_exp(size);
  254.  
  255.    /* Initialize in case they forgot to put in a clear code.
  256.     * (This shouldn't happen, but we'll try and decode it anyway...)
  257.     */
  258.    oc = fc = 0;
  259.  
  260.    /* Allocate space for the decode buffer
  261.     */
  262.    if ((buf = (UTINY *)malloc(linewidth + 1)) == NULL)
  263.       return(OUT_OF_MEMORY);
  264.  
  265.    /* Set up the stack pointer and decode buffer pointer
  266.     */
  267.    sp = stack;
  268.    bufptr = buf;
  269.    bufcnt = linewidth;
  270.  
  271.    /* This is the main loop.  For each code we get we pass through the
  272.     * linked list of prefix codes, pushing the corresponding "character" for
  273.     * each code onto the stack.  When the list reaches a single "character"
  274.     * we push that on the stack too, and then start unstacking each
  275.     * character for output in the correct order.  Special handling is
  276.     * included for the clear code, and the whole thing ends when we get
  277.     * an ending code.
  278.     */
  279.    while ((c = get_next_code()) != ending)
  280.       {
  281.  
  282.       /* If we had a file error, return without completing the decode
  283.        */
  284.       if (c < 0)
  285.          {
  286.          free(buf);
  287.          return(0);
  288.          }
  289.  
  290.       /* If the code is a clear code, reinitialize all necessary items.
  291.        */
  292.       if (c == clear)
  293.          {
  294.          curr_size = size + 1;
  295.          slot = newcodes;
  296.          top_slot = 1 << curr_size;
  297.  
  298.          /* Continue reading codes until we get a non-clear code
  299.           * (Another unlikely, but possible case...)
  300.           */
  301.          while ((c = get_next_code()) == clear)
  302.             ;
  303.  
  304.          /* If we get an ending code immediately after a clear code
  305.           * (Yet another unlikely case), then break out of the loop.
  306.           */
  307.          if (c == ending)
  308.             break;
  309.  
  310.          /* Finally, if the code is beyond the range of already set codes,
  311.           * (This one had better NOT happen...  I have no idea what will
  312.           * result from this, but I doubt it will look good...) then set it
  313.           * to color zero.
  314.           */
  315.          if (c >= slot)
  316.             c = 0;
  317.  
  318.          oc = fc = c;
  319.  
  320.          /* And let us not forget to put the char into the buffer... And
  321.           * if, on the off chance, we were exactly one pixel from the end
  322.           * of the line, we have to send the buffer to the out_line()
  323.           * routine...
  324.           */
  325.          *bufptr++ = c;
  326.          if (--bufcnt == 0)
  327.             {
  328.             if ((ret = out_line(buf, linewidth)) < 0)
  329.                {
  330.                free(buf);
  331.                return(ret);
  332.                }
  333.             bufptr = buf;
  334.             bufcnt = linewidth;
  335.             }
  336.          }
  337.       else
  338.          {
  339.  
  340.          /* In this case, it's not a clear code or an ending code, so
  341.           * it must be a code code...  So we can now decode the code into
  342.           * a stack of character codes. (Clear as mud, right?)
  343.           */
  344.          code = c;
  345.  
  346.          /* Here we go again with one of those off chances...  If, on the
  347.           * off chance, the code we got is beyond the range of those already
  348.           * set up (Another thing which had better NOT happen...) we trick
  349.           * the decoder into thinking it actually got the last code read.
  350.           * (Hmmn... I'm not sure why this works...  But it does...)
  351.           */
  352.          if (code >= slot)
  353.             {
  354.             if (code > slot)
  355.                ++bad_code_count;
  356.             code = oc;
  357.             *sp++ = fc;
  358.             }
  359.  
  360.          /* Here we scan back along the linked list of prefixes, pushing
  361.           * helpless characters (ie. suffixes) onto the stack as we do so.
  362.           */
  363.          while (code >= newcodes)
  364.             {
  365.             *sp++ = suffix[code];
  366.             code = prefix[code];
  367.             }
  368.  
  369.          /* Push the last character on the stack, and set up the new
  370.           * prefix and suffix, and if the required slot number is greater
  371.           * than that allowed by the current bit size, increase the bit
  372.           * size.  (NOTE - If we are all full, we *don't* save the new
  373.           * suffix and prefix...  I'm not certain if this is correct...
  374.           * it might be more proper to overwrite the last code...
  375.           */
  376.          *sp++ = code;
  377.          if (slot < top_slot)
  378.             {
  379.             suffix[slot] = fc = code;
  380.             prefix[slot++] = oc;
  381.             oc = c;
  382.             }
  383.          if (slot >= top_slot)
  384.             if (curr_size < 12)
  385.                {
  386.                top_slot <<= 1;
  387.                ++curr_size;
  388.                } 
  389.  
  390.          /* Now that we've pushed the decoded string (in reverse order)
  391.           * onto the stack, lets pop it off and put it into our decode
  392.           * buffer...  And when the decode buffer is full, write another
  393.           * line...
  394.           */
  395.          while (sp > stack)
  396.             {
  397.             *bufptr++ = *(--sp);
  398.             if (--bufcnt == 0)
  399.                {
  400.                if ((ret = out_line(buf, linewidth)) < 0)
  401.                   {
  402.                   free(buf);
  403.                   return(ret);
  404.                   }
  405.                bufptr = buf;
  406.                bufcnt = linewidth;
  407.                }
  408.             }
  409.          }
  410.       }
  411.    ret = 0;
  412.    if (bufcnt != linewidth)
  413.       ret = out_line(buf, (linewidth - bufcnt));
  414.    free(buf);
  415.    return(ret);
  416.    }
  417.  
  418. SHAR_EOF
  419. if test 11918 -ne "`wc -c 'decoder.c'`"
  420. then
  421.     echo shar: error transmitting "'decoder.c'" '(should have been 11918 characters)'
  422. fi
  423. echo shar: extracting "'errs.h'" '(366 characters)'
  424. if test -f 'errs.h'
  425. then
  426.     echo shar: over-writing existing file "'errs.h'"
  427. fi
  428. cat << \SHAR_EOF > 'errs.h'
  429. /* Various error codes used by decoder
  430.  * and my own routines...   It's okay
  431.  * for you to define whatever you want,
  432.  * as long as it's negative...  It will be
  433.  * returned intact up the various subroutine
  434.  * levels...
  435.  */
  436. #define OUT_OF_MEMORY -10
  437. #define BAD_CODE_SIZE -20
  438. #define READ_ERROR -1
  439. #define WRITE_ERROR -2
  440. #define OPEN_ERROR -3
  441. #define CREATE_ERROR -4
  442.  
  443. SHAR_EOF
  444. if test 366 -ne "`wc -c 'errs.h'`"
  445. then
  446.     echo shar: error transmitting "'errs.h'" '(should have been 366 characters)'
  447. fi
  448. echo shar: extracting "'std.h'" '(278 characters)'
  449. if test -f 'std.h'
  450. then
  451.     echo shar: over-writing existing file "'std.h'"
  452. fi
  453. cat << \SHAR_EOF > 'std.h'
  454. /* STD.H - My own standard header file...
  455.  */
  456.  
  457. #define LOCAL static
  458. #define IMPORT extern
  459.  
  460. #define FAST register
  461.  
  462. typedef short WORD;
  463. typedef unsigned short UWORD;
  464. typedef char TEXT;
  465. typedef unsigned char UTINY;
  466. typedef long LONG;
  467. typedef unsigned long ULONG;
  468. typedef int INT;
  469.  
  470. SHAR_EOF
  471. if test 278 -ne "`wc -c 'std.h'`"
  472. then
  473.     echo shar: error transmitting "'std.h'" '(should have been 278 characters)'
  474. fi
  475. #    End of shell archive
  476. exit 0
  477.