home *** CD-ROM | disk | FTP | other *** search
/ Graphics 16,000 / graphics-16000.iso / msdos / fractal / fdesi313 / fdes13s / fdesgif.c < prev    next >
Text File  |  1990-01-23  |  18KB  |  503 lines
  1. /* ENCODER.C
  2. **
  3. ** C source for a simple public domain GIF encoder.
  4. ** By Bert Tyler [73477,433] and Lee Daniel Crocker [73407,2030].
  5. **
  6. ** The program using this encoder must do the following things:
  7. **
  8. **  Call the create_gif() function, passing it parameters for the
  9. **  whole GIF screen such as screen size, global color map, etc.
  10. **  See the description of create_gif() below for more details.
  11. **
  12. **  For each image in the GIF:
  13. **
  14. **      Define a function get_pixel() that returns a color map
  15. **      index for the (x,y) coordinates passed to it.  This can
  16. **      be defined as a macro in GIF.H for speed if desired.
  17. **
  18. **      Call put_image(), passing it parameters for the image
  19. **      such as image size, offsets, local color map, etc.
  20. **
  21. **  Call close_gif().
  22. **
  23. ** This routine uses small string and hash-tables, and "flushes" the
  24. ** GIF entries whenever the hash-table gets two-thirds full or the
  25. ** string table gets full.  It also uses the GIF encoding technique of
  26. ** limiting the encoded string length to a specific size, "adding" a
  27. ** string to the hash table at that point even if a matching string
  28. ** exists ("adding" is in quotes, because if a matching string exists we
  29. ** can increment the code counter but safely throw the duplicate string
  30. ** away, saving both string space and a hash table entry).
  31. **
  32. ** This results in relatively good speed and small data space, but at
  33. ** the expense of compression efficiency (filesize).   These trade-offs
  34. ** could be adjusted by modifying the #DEFINEd variables below.  These
  35. ** numbers (particularly MAXSTRING) should generally be as large as your
  36. ** hardware (or memory model in the case of 8086 machines) will allow.
  37. **
  38. **  > if you want to make the GIF files smaller, make MAXSTRING bigger.
  39. **  > if you need the memory for other things, make MAXSTRING smaller.
  40. **  > if you're on an 80xx6 machine, consider allocating 'strings'
  41. **  >    in a FAR segment (and replacing the 'memcmp/memcpy' calls)
  42. **
  43. ** To save as much space as possible, this routine stores both the encoded
  44. ** string AND its 16-bit GIF code value in the same "string" array (the
  45. ** storage order is arbitrary - we store the code first and then the string).
  46. ** This avoids pre-allocating space for a seperate GIF code table.
  47. */
  48.  
  49. #define MAXTEST   100       /* Maximum encoded string length             */
  50. #define MAXSTRING 24000     /* Array space for all the encoded strings   */
  51.                             /* BIGGER IS BETTER AS FAR AS MAXSTRING GOES */
  52. #define MAXENTRY  6151      /* Maximum encoded entries                   */
  53.                             /* (a prime number is best for hashing)
  54.                                ((and 6151, which is the smallest prime  
  55.                                number greater than (4096*3/2) is dead
  56.                                perfect for our purposes))                */
  57. #include <stdlib.h>
  58. #include <stdio.h>
  59. #include <string.h>
  60. #include <ctype.h>
  61. #include <graphics.h>
  62.  
  63. #include "fdesgif.h"
  64.  
  65. /* Arrays used by the encoder.  These arrays are allocated at the start
  66. ** of the put_image function and freed when it returns.  Currently this
  67. ** is done with malloc() and free(), but a more efficient allocation
  68. ** strategy should not be difficult to implement.  The size of each
  69. ** array is shown here in brackets for clarity.
  70. */
  71.  
  72. static U8 *teststring;  /* [MAXTEST]    String to match against         */
  73. static U8 *strings;     /* [MAXSTRING]  Encoded strings go here         */
  74. static S16 *strlocn;    /* [MAXENTRY]   Location of encoded strings     */
  75.  
  76. static FILE *out;                   /* Destination file for GIF stream  */
  77.  
  78. /* The following arrays are strings that identify various parts of the
  79. ** GIF data stream.  They represent ASCII strings, but are encoded here
  80. ** in hex for portability to non-ASCII systems.
  81. */
  82.  
  83. static char signature[] = { 0x47, 0x49, 0x46, 0x38, 0x37, 0x61 },
  84.             imagestart[] = { 0x2C },
  85.             terminator[] = { 0x3B };
  86.  
  87. static int  lentest,            /* Length of current encoder string     */
  88.             lastentry,          /* Last string found in table           */
  89.             numentries,         /* Number of entries in string table,   */
  90.                                 /* including "fake" entries when full   */
  91.             numrealentries,     /* Number of real entries only          */
  92.             maxnumrealentries,  /* flush the table if < numrealentries  */
  93.             nextentry;          /* Next available entry in string table */
  94.  
  95. static S16  entrynum;           /* Hash value of encoded GIF strings    */
  96.  
  97. static int  clearcode,          /* Code to clear LZW decoder            */
  98.             endcode,            /* LZW end-of-data mark                 */
  99.             gifopen = 0;        /* Flag: is the GIF file open?          */
  100.  
  101. static U8   block[267];         /* Buffer accumulating output bytes     */
  102.  
  103. static int  bytecount,          /* Number of bytes and bits in buffer   */
  104.             bitcount;
  105.  
  106. static int  startbits,          /* Starting code size - 1               */
  107.             gcmapbits,          /* Size in bits of global color map     */
  108.             dcolors,            /* Number of colors in global color map */
  109.             codebits;           /* Current LZW code size                */
  110.  
  111. /* Functions used by the encoder routine.  These are all described in more
  112. ** detail where they are defined, at the end of this souce file.
  113. */
  114.  
  115. static int  log2(register U16);
  116. static void init_bitstream(void);
  117. static void encode_a_value(register U16);
  118. static void init_tables(void);
  119.  
  120. /* Masks used for bitmap function needed to determine color
  121. ** resolution of image.  Byte ordering is unimportant!
  122. */
  123.  
  124. static U16 masks[] = {
  125.     0x0001, 0x0002, 0x0004, 0x0008, 0x0010, 0x0020, 0x0040, 0x0080,
  126.     0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000, 0x8000
  127. };
  128.  
  129. /* create_gif() takes 5 arguments:
  130. **
  131. **  swidth      Width of the GIF virtual screen.
  132. **  sheight     Height of the GIF virtual screen.
  133. **  gcolors     Number of colors in global color map.  This is rounded
  134. **                  up to nearest power of two.
  135. **  palette     Actual color map entries.  Three bytes per color of red,
  136. **                  green, and blue, 0..255.
  137. **  fname       File to write.
  138. **
  139. ** Returns       0 if successful,
  140. **              -1 if a GIF file is already open,
  141. **              -2 if it cannot create the file,
  142. **              -3 if it can create it but cannot write to it.
  143. **
  144. ** The file is closed on any non-zero return.
  145. **
  146. ** NOTE: No apology is made for the unabashed use of "goto" in this
  147. ** function and in put_image.
  148. */
  149.  
  150. int create_gif( int swidth,     /* Global screen width                  */
  151.                 int sheight,    /* "      "      height                 */
  152.                 int gcolors,    /* Global color map size (0 if none)    */
  153.                 U8 *palette,    /* "      "     "   entries             */
  154.                 int crez,       /* Color resolution (1..8), 0 for auto  */
  155.                 char *fname )   /* Filename                             */
  156. {
  157.     int i, c, nbits;
  158.     char openfile[80];
  159.     U8 header[13], *pp;
  160.     U16 bitmap[16], *bp, v;
  161.  
  162.     if (gifopen) {
  163. /*        fprintf(stderr, "Cannot open multiple GIF files.\n");
  164. */
  165.         return -1;
  166.     }
  167.  
  168.     /* Add default file extension of ".GIF"
  169.     */
  170.  
  171.     strcpy(openfile, fname);
  172.     if (strchr(openfile, '.') == NULL) strcat(openfile, ".GIF");
  173.  
  174.     if ((out = fopen(openfile, WRITEMODE)) == NULL) {
  175. /*        fprintf(stderr, "Could not create file %s\n", openfile);
  176. */
  177.         return -2;
  178.     }
  179.  
  180.     memcpy(header, signature, 6);
  181.     PUT16(header[6], swidth);
  182.     PUT16(header[8], sheight);
  183.     
  184.     if (gcolors > 0) header[10] = 0x80; /* Global color map flag        */
  185.     else header[10] = 0x00;
  186.  
  187.     gcmapbits = log2(gcolors);
  188.     dcolors = 1 << gcmapbits;
  189.     if (gcolors <= 2) ++gcmapbits;
  190.     header[10] |= (gcmapbits - 1);      /* Color table size             */
  191.  
  192.     /* The code below tries to determine the color resolution of the
  193.     ** GIF if not given.  It does this by setting a bit in the bitmap
  194.     ** array for every different color value in the color map, then
  195.     ** counting the number of bits set.
  196.     */
  197.     /* &&&DNN this doesn't seem to work */
  198.     if (crez == 0) {
  199.         memset(bitmap, 0, sizeof(bitmap));
  200.         for (pp = palette, i = 3 * gcolors; i > 0; --i) {
  201.             c = *pp++;
  202.             bitmap[c >> 4] |= masks[c & 0x0F];
  203.         }
  204.         nbits = 0;
  205.         for (bp = bitmap, i = 16; i > 0; --i) {
  206.             v = *bp++;
  207.             do {
  208.                 if (v & 0x8000) ++nbits;
  209.                 v = (v & 0x7FFF) << 1;
  210.             } while (v);
  211.         }
  212.         crez = log2(nbits);
  213.     }
  214.     header[10] |= ((crez - 1) << 4);
  215.  
  216.     header[11] = 0;                     /* Background color index       */
  217.     header[12] = 0;                     /* Reserved                     */
  218.  
  219.     if (fwrite(header, 13, 1, out) != 1) goto write_error;
  220.  
  221.     /* Write global color map if there is one.  If gcolors parameter was
  222.     ** not a power of two, random bytes are put into the unused entries.
  223.     */
  224.  
  225.     if (gcolors > 0) {
  226.         if (fwrite(palette, 3 * dcolors, 1, out) != 1) goto write_error;
  227.     }
  228.  
  229.     gifopen = 1;
  230.     return 0;                           /* All's well                   */
  231.  
  232. write_error:
  233.     fclose(out);                        /* Close file and return error  */
  234.     return -3;
  235. }
  236.  
  237. static U16  intstart[] = { 0, 4, 2, 1, 0 },
  238.             intinc[] = { 8, 8, 4, 2, 1 };
  239.  
  240. int put_image(  int iwidth,     /* Image width                          */
  241.                 int iheight,    /* "     height                         */
  242.                 int xoff,       /* "     horizontal offset              */
  243.                 int yoff,       /* "     vertical offset                */
  244.                 int interlace,  /* Interlaced image flag                */
  245.                 int lcolors,    /* Local color map size (0 if none)     */
  246.                 U8 *lcmap )     /* "     "     "   entries              */
  247. {
  248.     int rval, intpass;
  249.     register int hashentry;
  250.     U16 i, y, ydot, xdot, color, colors;
  251.     U8 header[11], cmask;
  252.     static U16 hashcode;
  253.  
  254.     if (!gifopen) {
  255. /*        fprintf(stderr, "No GIF file open.\n");
  256. */
  257.         return -1;
  258.     }
  259.  
  260.     /* Allocate space for arrays.  They are freed at the end of the
  261.     ** function in reverse order of allocation even when an error occurs.
  262.     ** This should make it easy to put in a simple mark/release style
  263.     ** memory allocator to reduce fragmentation.
  264.     */
  265.  
  266.     rval = -2;
  267.     if ((teststring = (U8 *)malloc(MAXTEST)) == NULL) return rval;
  268.     if ((strings = (U8 *)malloc(MAXSTRING)) == NULL) goto memerr3;
  269.     if ((strlocn = (U16 *)malloc(2 * MAXENTRY)) == NULL) goto memerr2;
  270.  
  271.     header[0] = *imagestart;
  272.     PUT16(header[1], xoff);
  273.     PUT16(header[3], yoff);
  274.     PUT16(header[5], iwidth);
  275.     PUT16(header[7], iheight);
  276.  
  277.     if (interlace) {
  278.         header[9] = 0x40;
  279.         intpass = 0;
  280.     } else {
  281.         header[9] = 0x00;   /* We treat non-interlaced images as pass   */
  282.         intpass = 4;        /* 4 to avoid an if() inside the loop.      */
  283.     }
  284.  
  285.     if (lcolors == 0) {         /* If a local color map is given, use   */
  286.         startbits = gcmapbits;  /* it; otherwise, use the global.       */
  287.         colors = dcolors;
  288.     } else {
  289.         header[9] |= 0x80;
  290.         startbits = log2(lcolors);
  291.         colors = 1 << startbits;
  292.         if (lcolors <= 2) ++startbits;
  293.     }
  294.     header[9] |= (U8)(startbits - 1);
  295.     header[10] = (U8)startbits;         /* &&&DNN this should go after local
  296.                                            color map */
  297.  
  298.     if (fwrite(header, 11, 1, out) != 1) goto writeerr;
  299.  
  300.     /* Write local color map if needed.
  301.     */
  302.  
  303.     if (lcolors != 0) {
  304.         if (fwrite(lcmap, 3 * colors, 1, out) != 1) goto writeerr;
  305.     }
  306.  
  307.     clearcode = 1 << startbits;
  308.     endcode = clearcode + 1;
  309.  
  310.     codebits = startbits + 1;       /* Set Initial LZW code size    */
  311.     init_bitstream();               /* Initialize encode_a_value()  */
  312.     init_tables();                  /* "          LZW tables        */
  313.  
  314.     cmask = (U8)(colors - 1);       /* Color value mask             */
  315.  
  316.     ydot = 0;                       /* Ydot holds actual value, y   */
  317.     for (y = iheight; y > 0; --y) { /* is just a count.             */
  318.  
  319.         for (xdot = 0; xdot < iwidth; ++xdot) {
  320.  
  321.             color = get_pixel(xdot, ydot) & cmask;
  322.  
  323.             teststring[0] = (U8)++lentest;
  324.             teststring[lentest] = (U8)color;
  325.  
  326.             if (lentest == 1) {
  327.                 lastentry = color;
  328.                 continue;
  329.             }
  330.  
  331.             if (lentest == 2) hashcode = 301 * (teststring[1] + 1);
  332.             hashcode *= (color + lentest);
  333.             hashentry = ++hashcode % MAXENTRY;
  334.  
  335.             for (i = 0; i < MAXENTRY; ++i) {
  336.                 if (++hashentry >= MAXENTRY) hashentry = 0;
  337.                 if (memcmp(&strings[strlocn[hashentry]+2],
  338.                             teststring, lentest+1) == 0) break;
  339.                 if (strlocn[hashentry] == 0) break;
  340.             }
  341.  
  342.             /* Found and entry and string length is OK.
  343.             */
  344.             if (strlocn[hashentry] != 0 && lentest < MAXTEST-3) {
  345.                 memcpy(&entrynum, &strings[strlocn[hashentry]],2); 
  346.                 lastentry = entrynum;
  347.                 continue;
  348.             }
  349.             encode_a_value(lastentry);
  350.             ++numentries;
  351.  
  352.             if (strlocn[hashentry] == 0) {
  353.                 entrynum = numentries + endcode;
  354.                 strlocn[hashentry] = nextentry;
  355.                 memcpy(&strings[nextentry],   &entrynum,  2);
  356.                 memcpy(&strings[nextentry]+2, teststring, lentest+1);
  357.                 nextentry += lentest+3;
  358.                 ++numrealentries;
  359.             }
  360.  
  361.             teststring[0] = (U8)(lentest = 1);
  362.             teststring[1] = (U8)(lastentry = color);
  363.  
  364.             if ((numentries + endcode) == (1 << codebits)) ++codebits;
  365.  
  366.             /* ensure that we aren't about to exceed either the GIF limit
  367.                of 4096 entries or our artificial efficiency limit of 2/3
  368.                the size of the hash table, or our string table size */
  369.             if (numentries + endcode > (4096-3) ||
  370.                 numrealentries > maxnumrealentries ||
  371.                 nextentry > MAXSTRING-MAXTEST-5) {
  372.                 encode_a_value(lastentry);
  373.                 init_tables();
  374.             }
  375.         }
  376.         putpixel(1,ydot,15);    /* &&&dnn */
  377.         putpixel(2,ydot,15);
  378.         if ((ydot += intinc[intpass]) >= iheight) ydot = intstart[++intpass];
  379.     }
  380.     encode_a_value(lastentry);
  381.     encode_a_value(endcode);
  382.  
  383.     if (fwrite("", 1, 1, out) != 1) rval = -3;  /* Zero-length block    */
  384.     else rval = 0;
  385.     goto nowriteerr;
  386.  
  387. writeerr:               /* This monstrosity assures that all pointers   */
  388.     rval = -3;          /* allocated at the start of the function are   */
  389. nowriteerr:             /* freed in the proper order, even if an error  */
  390.                         /* occurs at some point.                        */
  391. memerr1:
  392.     free(strlocn);
  393. memerr2:
  394.     free(strings);
  395. memerr3:
  396.     free(teststring);
  397.  
  398.     return rval;
  399. }
  400.  
  401. /* Write GIF terminator to file and close.  Only error return is when
  402. ** no file has been opened.
  403. */
  404.  
  405. int close_gif(void)
  406. {
  407.     if (!gifopen) {
  408. /*        fprintf(stderr, "No GIF file open.\n");
  409. */
  410.         return -1;
  411.     }
  412.     fwrite(terminator, 1, 1, out);
  413.     fclose(out);
  414.     return gifopen = 0;
  415. }
  416.  
  417. /* Return base-2 logarithm of its argument (rounded up to the nearest
  418. ** power of two).  Only numbers in the 1..256 range are valid.
  419. */
  420.  
  421. static int log2(register U16 val)
  422. {
  423.     if (--val & 0x80) return 8;
  424.     if (val & 0x40) return 7;
  425.     if (val & 0x20) return 6;
  426.     if (val & 0x10) return 5;
  427.     if (val & 0x08) return 4;
  428.     if (val & 0x04) return 3;
  429.     if (val & 0x02) return 2;
  430.     return 1;
  431. }
  432.  
  433. /* Initialize the output stream.  Bytecount starts at 1 so that the
  434. ** block count can be put in block[0] before writing.
  435. */
  436.  
  437. static void init_bitstream(void)
  438. {
  439.     bytecount = 1;
  440.     bitcount = 0;
  441.     memset(block, 0, sizeof(block));
  442.     return;
  443. }
  444.  
  445. /* Clear LZW tables and reset code size.
  446. */
  447.  
  448. static void init_tables(void)
  449. {
  450.     encode_a_value(clearcode);
  451.     numentries = numrealentries = lentest = 0;
  452.     maxnumrealentries = (MAXENTRY * 2) / 3;
  453.     nextentry = 1;
  454.     codebits = startbits + 1;
  455.  
  456.     *strings = '\0';
  457.     memset(strlocn, 0, 2 * MAXENTRY);
  458.     return;
  459. }
  460.  
  461. /* Write a single code to the output file.  If the outbut buffer
  462. ** is full or an end-of-data code is found, flush output.
  463. */
  464.  
  465. static void encode_a_value(register U16 code)
  466. {
  467.     register U16 icode;
  468.     U8 *bp;
  469.     U16 i;
  470.  
  471.     icode = code << bitcount;
  472.     bp = block + bytecount;
  473.  
  474.     *bp++ |= (U8)icode;
  475.     *bp++ |= (U8)(icode >> 8);
  476.  
  477.     icode = (code >> 8) << bitcount;
  478.     *bp++ |= (U8)(icode >> 8);
  479.  
  480.     bitcount += codebits;
  481.     while (bitcount >= 8) {
  482.         bitcount -= 8;
  483.         ++bytecount;
  484.     }
  485.  
  486.     if (bytecount > 251 || code == endcode) {
  487.         if (code == endcode) {
  488.             while (bitcount > 0) {
  489.                 bitcount -= 8;
  490.                 ++bytecount;
  491.             }
  492.         }
  493.         i = bytecount;
  494.         *block = (U8)(i - 1);
  495.         fwrite(block, bytecount, 1, out);
  496.  
  497.         bytecount = 1;
  498.         memcpy(block+1, block+i, 5);
  499.         memset(block+6, 0, sizeof(block)-6);
  500.     }
  501.     return;
  502. }
  503.