home *** CD-ROM | disk | FTP | other *** search
/ Fractal Frenzy 1 / WalnutCreekFractalFrenzy-1.iso / pc / viewers / x11 / xv221.tz / xv221 / xv-2.21 / xvgifwr.c < prev    next >
C/C++ Source or Header  |  1992-04-29  |  15KB  |  595 lines
  1. /*
  2.  * xvgifwr.c  -  handles writing of GIF files.  based on flgife.c and
  3.  *               flgifc.c from the FBM Library, by Michael Maudlin
  4.  *
  5.  * Contains: 
  6.  *   WriteGIF(fp, pic, w, h, rmap, gmap, bmap, numcols, colorstyle)
  7.  *
  8.  * Note: slightly brain-damaged, in that it'll only write non-interlaced 
  9.  *       GIF files (in the interests of speed, or something)
  10.  *
  11.  */
  12.  
  13.  
  14.  
  15. /*****************************************************************
  16.  * Portions of this code Copyright (C) 1989 by Michael Mauldin.
  17.  * Permission is granted to use this file in whole or in
  18.  * part for any purpose, educational, recreational or commercial,
  19.  * provided that this copyright notice is retained unchanged.
  20.  * This software is available to all free of charge by anonymous
  21.  * FTP and in the UUNET archives.
  22.  *
  23.  *
  24.  * Authors:  Michael Mauldin (mlm@cs.cmu.edu)
  25.  *           David Rowley (mgardi@watdcsu.waterloo.edu)
  26.  *
  27.  * Based on: compress.c - File compression ala IEEE Computer, June 1984.
  28.  *
  29.  *    Spencer W. Thomas       (decvax!harpo!utah-cs!utah-gr!thomas)
  30.  *    Jim McKie               (decvax!mcvax!jim)
  31.  *    Steve Davies            (decvax!vax135!petsd!peora!srd)
  32.  *    Ken Turkowski           (decvax!decwrl!turtlevax!ken)
  33.  *    James A. Woods          (decvax!ihnp4!ames!jaw)
  34.  *    Joe Orost               (decvax!vax135!petsd!joe)
  35.  *****************************************************************/
  36.  
  37. /*
  38.  * Copyright 1989, 1990, 1991, 1992 by John Bradley and
  39.  *                       The University of Pennsylvania
  40.  *
  41.  * Permission to use, copy, and distribute for non-commercial purposes,
  42.  * is hereby granted without fee, providing that the above copyright
  43.  * notice appear in all copies and that both the copyright notice and this
  44.  * permission notice appear in supporting documentation.
  45.  *
  46.  * The software may be modified for your own purposes, but modified versions
  47.  * may not be distributed.
  48.  *
  49.  * This software is provided "as is" without any expressed or implied warranty.
  50.  *
  51.  * The author may be contacted via:
  52.  *    US Mail:   John Bradley
  53.  *               GRASP Lab, Room 301C
  54.  *               3401 Walnut St.
  55.  *               Philadelphia, PA  19104
  56.  *
  57.  *    Phone:     (215) 898-8813
  58.  *    EMail:     bradley@cis.upenn.edu
  59.  */
  60.  
  61.  
  62. #include "xv.h"
  63.  
  64. typedef long int        count_int;
  65.  
  66. static int  Width, Height;
  67. static int  curx, cury;
  68. static long CountDown;
  69. static int  Interlace;
  70. static byte bw[2] = {0, 0xff};
  71.  
  72. #ifdef __STDC__
  73. static void putword(int, FILE *);
  74. static void compress(int, FILE *, byte *, int);
  75. static void output(int);
  76. static void cl_block(void);
  77. static void cl_hash(count_int);
  78. static void char_init(void);
  79. static void char_out(int);
  80. static void flush_char(void);
  81. #else
  82. static void putword(), compress(), output(), cl_block(), cl_hash();
  83. static void char_init(), char_out(), flush_char();
  84. #endif
  85.  
  86. static byte pc2nc[256],r1[256],g1[256],b1[256];
  87.  
  88.  
  89. /*************************************************************/
  90. int WriteGIF(fp, pic, w, h, rmap, gmap, bmap, numcols, colorstyle)
  91. FILE *fp;
  92. byte *pic;
  93. int   w,h;
  94. byte *rmap, *gmap, *bmap;
  95. int   numcols, colorstyle;
  96. {
  97.   int RWidth, RHeight;
  98.   int LeftOfs, TopOfs;
  99.   int ColorMapSize, InitCodeSize, Background, BitsPerPixel;
  100.   int i,j,nc;
  101.  
  102.  
  103.   /* if writing B/W stipple... */
  104.   if (colorstyle==2) {
  105.     rmap = gmap = bmap = bw;
  106.     numcols = 2;
  107.   }
  108.  
  109.   Interlace = 0;
  110.   Background = 0;
  111.  
  112.  
  113.   for (i=0; i<256; i++) { pc2nc[i] = r1[i] = g1[i] = b1[i] = 0; }
  114.  
  115.   /* compute number of unique colors */
  116.   nc = 0;
  117.  
  118.   for (i=0; i<numcols; i++) {
  119.     /* see if color #i is already used */
  120.     for (j=0; j<i; j++) {
  121.       if (rmap[i] == rmap[j] && gmap[i] == gmap[j] && 
  122.       bmap[i] == bmap[j]) break;
  123.     }
  124.  
  125.     if (j==i) {  /* wasn't found */
  126.       pc2nc[i] = nc;
  127.       r1[nc] = rmap[i];
  128.       g1[nc] = gmap[i];
  129.       b1[nc] = bmap[i];
  130.       nc++;
  131.     }
  132.     else pc2nc[i] = pc2nc[j];
  133.   }
  134.  
  135.  
  136.   /* figure out 'BitsPerPixel' */
  137.   for (i=1; i<8; i++)
  138.     if ( (1<<i) >= nc) break;
  139.   
  140.   BitsPerPixel = i;
  141.  
  142.   ColorMapSize = 1 << BitsPerPixel;
  143.     
  144.   RWidth  = Width  = w;
  145.   RHeight = Height = h;
  146.   LeftOfs = TopOfs = 0;
  147.     
  148.   CountDown = w * h;    /* # of pixels we'll be doing */
  149.  
  150.   if (BitsPerPixel <= 1) InitCodeSize = 2;
  151.                     else InitCodeSize = BitsPerPixel;
  152.  
  153.   curx = cury = 0;
  154.  
  155.   if (!fp) {
  156.     fprintf(stderr,  "WriteGIF: file not open for writing\n" );
  157.     return (1);
  158.   }
  159.  
  160.   if (DEBUG) 
  161.     fprintf(stderr,"WrGIF: pic=%lx, w,h=%dx%d, numcols=%d, Bits%d,Cmap=%d\n",
  162.         pic, w,h,numcols,BitsPerPixel,ColorMapSize);
  163.  
  164.   fwrite("GIF87a", 1, 6, fp);    /* the GIF magic number */
  165.  
  166.   putword(RWidth, fp);           /* screen descriptor */
  167.   putword(RHeight, fp);
  168.  
  169.   i = 0x80;                     /* Yes, there is a color map */
  170.   i |= (8-1)<<4;                 /* OR in the color resolution (hardwired 8) */
  171.   i |= (BitsPerPixel - 1);       /* OR in the # of bits per pixel */
  172.   fputc(i,fp);          
  173.  
  174.   fputc(Background, fp);         /* background color */
  175.  
  176.   fputc(0, fp);                  /* future expansion byte */
  177.  
  178.  
  179.   if (colorstyle == 1) {         /* greyscale */
  180.     for (i=0; i<ColorMapSize; i++) {
  181.       j = MONO(r1[i], g1[i], b1[i]);
  182.       fputc(j, fp);
  183.       fputc(j, fp);
  184.       fputc(j, fp);
  185.     }
  186.   }
  187.   else {
  188.     for (i=0; i<ColorMapSize; i++) {       /* write out Global colormap */
  189.       fputc(r1[i], fp);
  190.       fputc(g1[i], fp);
  191.       fputc(b1[i], fp);
  192.     }
  193.   }
  194.  
  195.   fputc( ',', fp );              /* image separator */
  196.  
  197.   /* Write the Image header */
  198.   putword(LeftOfs, fp);
  199.   putword(TopOfs,  fp);
  200.   putword(Width,   fp);
  201.   putword(Height,  fp);
  202.   if (Interlace) fputc(0x40, fp);   /* Use Global Colormap, maybe Interlace */
  203.             else fputc(0x00, fp);
  204.  
  205.   fputc(InitCodeSize, fp);
  206.   compress(InitCodeSize+1, fp, pic, w*h);
  207.  
  208.   fputc(0,fp);                      /* Write out a Zero-length packet (EOF) */
  209.   fputc(';',fp);                    /* Write GIF file terminator */
  210.  
  211.   return (0);
  212. }
  213.  
  214.  
  215.  
  216.  
  217. /******************************/
  218. static void putword(w, fp)
  219. int w;
  220. FILE *fp;
  221. {
  222.   /* writes a 16-bit integer in GIF order (LSB first) */
  223.   fputc(w & 0xff, fp);
  224.   fputc((w>>8)&0xff, fp);
  225. }
  226.  
  227.  
  228.  
  229.  
  230. /***********************************************************************/
  231.  
  232.  
  233. static unsigned long cur_accum = 0;
  234. static int           cur_bits = 0;
  235.  
  236.  
  237.  
  238.  
  239. #define min(a,b)        ((a>b) ? b : a)
  240.  
  241. #define XV_BITS    12    /* BITS was already defined on some systems */
  242. #define MSDOS    1
  243.  
  244. #define HSIZE  5003            /* 80% occupancy */
  245.  
  246. typedef unsigned char   char_type;
  247.  
  248.  
  249. static int n_bits;                    /* number of bits/code */
  250. static int maxbits = XV_BITS;         /* user settable max # bits/code */
  251. static int maxcode;                   /* maximum code, given n_bits */
  252. static int maxmaxcode = 1 << XV_BITS; /* NEVER generate this */
  253.  
  254. #define MAXCODE(n_bits)     ( (1 << (n_bits)) - 1)
  255.  
  256. static  count_int      htab [HSIZE];
  257. static  unsigned short codetab [HSIZE];
  258. #define HashTabOf(i)   htab[i]
  259. #define CodeTabOf(i)   codetab[i]
  260.  
  261. static int hsize = HSIZE;            /* for dynamic table sizing */
  262.  
  263. /*
  264.  * To save much memory, we overlay the table used by compress() with those
  265.  * used by decompress().  The tab_prefix table is the same size and type
  266.  * as the codetab.  The tab_suffix table needs 2**BITS characters.  We
  267.  * get this from the beginning of htab.  The output stack uses the rest
  268.  * of htab, and contains characters.  There is plenty of room for any
  269.  * possible stack (stack used to be 8000 characters).
  270.  */
  271.  
  272. #define tab_prefixof(i) CodeTabOf(i)
  273. #define tab_suffixof(i)        ((char_type *)(htab))[i]
  274. #define de_stack               ((char_type *)&tab_suffixof(1<<XV_BITS))
  275.  
  276. static int free_ent = 0;                  /* first unused entry */
  277.  
  278. /*
  279.  * block compression parameters -- after all codes are used up,
  280.  * and compression rate changes, start over.
  281.  */
  282. static int clear_flg = 0;
  283.  
  284. static long int in_count = 1;            /* length of input */
  285. static long int out_count = 0;           /* # of codes output (for debugging) */
  286.  
  287. /*
  288.  * compress stdin to stdout
  289.  *
  290.  * Algorithm:  use open addressing double hashing (no chaining) on the 
  291.  * prefix code / next character combination.  We do a variant of Knuth's
  292.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  293.  * secondary probe.  Here, the modular division first probe is gives way
  294.  * to a faster exclusive-or manipulation.  Also do block compression with
  295.  * an adaptive reset, whereby the code table is cleared when the compression
  296.  * ratio decreases, but after the table fills.  The variable-length output
  297.  * codes are re-sized at this point, and a special CLEAR code is generated
  298.  * for the decompressor.  Late addition:  construct the table according to
  299.  * file size for noticeable speed improvement on small files.  Please direct
  300.  * questions about this implementation to ames!jaw.
  301.  */
  302.  
  303. static int g_init_bits;
  304. static FILE *g_outfile;
  305.  
  306. static int ClearCode;
  307. static int EOFCode;
  308.  
  309.  
  310. /********************************************************/
  311. static void compress(init_bits, outfile, data, len)
  312. int   init_bits;
  313. FILE *outfile;
  314. byte *data;
  315. int   len;
  316. {
  317.   register long fcode;
  318.   register int i = 0;
  319.   register int c;
  320.   register int ent;
  321.   register int disp;
  322.   register int hsize_reg;
  323.   register int hshift;
  324.  
  325.   /*
  326.    * Set up the globals:  g_init_bits - initial number of bits
  327.    *                      g_outfile   - pointer to output file
  328.    */
  329.   g_init_bits = init_bits;
  330.   g_outfile   = outfile;
  331.  
  332.   /* initialize 'compress' globals */
  333.   maxbits = XV_BITS;
  334.   maxmaxcode = 1<<XV_BITS;
  335.   memset((char *) htab, 0, sizeof(htab));
  336.   memset((char *) codetab, 0, sizeof(codetab));
  337.   hsize = HSIZE;
  338.   free_ent = 0;
  339.   clear_flg = 0;
  340.   in_count = 1;
  341.   out_count = 0;
  342.   cur_accum = 0;
  343.   cur_bits = 0;
  344.  
  345.  
  346.   /*
  347.    * Set up the necessary values
  348.    */
  349.   out_count = 0;
  350.   clear_flg = 0;
  351.   in_count = 1;
  352.   maxcode = MAXCODE(n_bits = g_init_bits);
  353.  
  354.   ClearCode = (1 << (init_bits - 1));
  355.   EOFCode = ClearCode + 1;
  356.   free_ent = ClearCode + 2;
  357.  
  358.   char_init();
  359.   ent = pc2nc[*data++];  len--;
  360.  
  361.   hshift = 0;
  362.   for ( fcode = (long) hsize;  fcode < 65536L; fcode *= 2L )
  363.     hshift++;
  364.   hshift = 8 - hshift;                /* set hash code range bound */
  365.  
  366.   hsize_reg = hsize;
  367.   cl_hash( (count_int) hsize_reg);            /* clear hash table */
  368.  
  369.   output(ClearCode);
  370.     
  371.   while (len) {
  372.     c = pc2nc[*data++];  len--;
  373.     in_count++;
  374.  
  375.     fcode = (long) ( ( (long) c << maxbits) + ent);
  376.     i = (((int) c << hshift) ^ ent);    /* xor hashing */
  377.  
  378.     if ( HashTabOf (i) == fcode ) {
  379.       ent = CodeTabOf (i);
  380.       continue;
  381.     }
  382.  
  383.     else if ( (long)HashTabOf (i) < 0 )      /* empty slot */
  384.       goto nomatch;
  385.  
  386.     disp = hsize_reg - i;           /* secondary hash (after G. Knott) */
  387.     if ( i == 0 )
  388.       disp = 1;
  389.  
  390. probe:
  391.     if ( (i -= disp) < 0 )
  392.       i += hsize_reg;
  393.  
  394.     if ( HashTabOf (i) == fcode ) {
  395.       ent = CodeTabOf (i);
  396.       continue;
  397.     }
  398.  
  399.     if ( (long)HashTabOf (i) > 0 ) 
  400.       goto probe;
  401.  
  402. nomatch:
  403.     output(ent);
  404.     out_count++;
  405.     ent = c;
  406.  
  407.     if ( free_ent < maxmaxcode ) {
  408.       CodeTabOf (i) = free_ent++; /* code -> hashtable */
  409.       HashTabOf (i) = fcode;
  410.     }
  411.     else
  412.       cl_block();
  413.   }
  414.  
  415.   /* Put out the final code */
  416.   output(ent);
  417.   out_count++;
  418.   output(EOFCode);
  419. }
  420.  
  421.  
  422. /*****************************************************************
  423.  * TAG( output )
  424.  *
  425.  * Output the given code.
  426.  * Inputs:
  427.  *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
  428.  *              that n_bits =< (long)wordsize - 1.
  429.  * Outputs:
  430.  *      Outputs code to the file.
  431.  * Assumptions:
  432.  *      Chars are 8 bits long.
  433.  * Algorithm:
  434.  *      Maintain a BITS character long buffer (so that 8 codes will
  435.  * fit in it exactly).  Use the VAX insv instruction to insert each
  436.  * code in turn.  When the buffer fills up empty it and start over.
  437.  */
  438.  
  439. static
  440. unsigned long masks[] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000F,
  441.                                   0x001F, 0x003F, 0x007F, 0x00FF,
  442.                                   0x01FF, 0x03FF, 0x07FF, 0x0FFF,
  443.                                   0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
  444.  
  445. static void output(code)
  446. int code;
  447. {
  448.   cur_accum &= masks[cur_bits];
  449.  
  450.   if (cur_bits > 0)
  451.     cur_accum |= ((long)code << cur_bits);
  452.   else
  453.     cur_accum = code;
  454.     
  455.   cur_bits += n_bits;
  456.  
  457.   while( cur_bits >= 8 ) {
  458.     char_out( (unsigned int) (cur_accum & 0xff) );
  459.     cur_accum >>= 8;
  460.     cur_bits -= 8;
  461.   }
  462.  
  463.   /*
  464.    * If the next entry is going to be too big for the code size,
  465.    * then increase it, if possible.
  466.    */
  467.  
  468.   if (free_ent > maxcode || clear_flg) {
  469.  
  470.     if( clear_flg ) {
  471.       maxcode = MAXCODE (n_bits = g_init_bits);
  472.       clear_flg = 0;
  473.     }
  474.     else {
  475.       n_bits++;
  476.       if ( n_bits == maxbits )
  477.     maxcode = maxmaxcode;
  478.       else
  479.     maxcode = MAXCODE(n_bits);
  480.     }
  481.   }
  482.     
  483.   if( code == EOFCode ) {
  484.     /* At EOF, write the rest of the buffer */
  485.     while( cur_bits > 0 ) {
  486.       char_out( (unsigned int)(cur_accum & 0xff) );
  487.       cur_accum >>= 8;
  488.       cur_bits -= 8;
  489.     }
  490.  
  491.     flush_char();
  492.     
  493.     fflush( g_outfile );
  494.  
  495.     if( ferror( g_outfile ) )
  496.       FatalError("unable to write GIF file");
  497.   }
  498. }
  499.  
  500.  
  501. /********************************/
  502. static void cl_block ()             /* table clear for block compress */
  503. {
  504.   /* Clear out the hash table */
  505.  
  506.   cl_hash ( (count_int) hsize );
  507.   free_ent = ClearCode + 2;
  508.   clear_flg = 1;
  509.  
  510.   output(ClearCode);
  511. }
  512.  
  513.  
  514. /********************************/
  515. static void cl_hash(hsize)          /* reset code table */
  516. register count_int hsize;
  517. {
  518.   register count_int *htab_p = htab+hsize;
  519.   register long i;
  520.   register long m1 = -1;
  521.  
  522.   i = hsize - 16;
  523.   do {                            /* might use Sys V memset(3) here */
  524.     *(htab_p-16) = m1;
  525.     *(htab_p-15) = m1;
  526.     *(htab_p-14) = m1;
  527.     *(htab_p-13) = m1;
  528.     *(htab_p-12) = m1;
  529.     *(htab_p-11) = m1;
  530.     *(htab_p-10) = m1;
  531.     *(htab_p-9) = m1;
  532.     *(htab_p-8) = m1;
  533.     *(htab_p-7) = m1;
  534.     *(htab_p-6) = m1;
  535.     *(htab_p-5) = m1;
  536.     *(htab_p-4) = m1;
  537.     *(htab_p-3) = m1;
  538.     *(htab_p-2) = m1;
  539.     *(htab_p-1) = m1;
  540.     htab_p -= 16;
  541.   } while ((i -= 16) >= 0);
  542.  
  543.   for ( i += 16; i > 0; i-- )
  544.     *--htab_p = m1;
  545. }
  546.  
  547.  
  548. /******************************************************************************
  549.  *
  550.  * GIF Specific routines
  551.  *
  552.  ******************************************************************************/
  553.  
  554. /*
  555.  * Number of characters so far in this 'packet'
  556.  */
  557. static int a_count;
  558.  
  559. /*
  560.  * Set up the 'byte output' routine
  561.  */
  562. static void char_init()
  563. {
  564.     a_count = 0;
  565. }
  566.  
  567. /*
  568.  * Define the storage for the packet accumulator
  569.  */
  570. static char accum[ 256 ];
  571.  
  572. /*
  573.  * Add a character to the end of the current packet, and if it is 254
  574.  * characters, flush the packet to disk.
  575.  */
  576. static void char_out(c)
  577. int c;
  578. {
  579.   accum[ a_count++ ] = c;
  580.   if( a_count >= 254 ) 
  581.     flush_char();
  582. }
  583.  
  584. /*
  585.  * Flush the packet to disk, and reset the accumulator
  586.  */
  587. static void flush_char()
  588. {
  589.   if( a_count > 0 ) {
  590.     fputc( a_count, g_outfile );
  591.     fwrite( accum, 1, a_count, g_outfile );
  592.     a_count = 0;
  593.   }
  594. }    
  595.