home *** CD-ROM | disk | FTP | other *** search
/ Big Green CD 8 / BGCD_8_Dev.iso / NEXTSTEP / Graphics / ToyViewer-2.6a / src / ImageSave.bproj / gifsave.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-09-28  |  13.6 KB  |  527 lines
  1. /*
  2.     gifsave.c
  3.  
  4.     gifsave.c is based on "ppmtogif" of Jef Poskanzer.
  5.     It is modified for ToyViewer.app by T. Ogihara. (1995)
  6. */
  7.  
  8. /* ppmtogif.c - read a portable pixmap and produce a GIF file
  9. **
  10. ** Based on GIFENCOD by David Rowley <mgardi@watdscu.waterloo.edu>.A
  11. ** Lempel-Zim compression based on "compress".
  12. **
  13. ** Copyright (C) 1989 by Jef Poskanzer.
  14. **
  15. ** Permission to use, copy, modify, and distribute this software and its
  16. ** documentation for any purpose and without fee is hereby granted, provided
  17. ** that the above copyright notice appear in all copies and that both that
  18. ** copyright notice and this permission notice appear in supporting
  19. ** documentation.  This software is provided "as is" without express or
  20. ** implied warranty.
  21. **
  22. ** The Graphics Interchange Format(c) is the Copyright property of
  23. ** CompuServe Incorporated.  GIF(sm) is a Service Mark property of
  24. ** CompuServe Incorporated.
  25. */
  26.  
  27. #include "../gif.h"
  28. #include "../common.h"
  29. #include "../strfunc.h"
  30. #include "save.h"
  31.  
  32. #define MAXCOLORS 256
  33.  
  34. /*
  35.  * a code_int must be able to hold 2**BITS values of type int, and also -1
  36.  */
  37. typedef int    code_int;
  38.  
  39. #ifdef SIGNED_COMPARE_SLOW
  40. typedef unsigned long int count_int;
  41. #else /*SIGNED_COMPARE_SLOW*/
  42. typedef long int    count_int;
  43. #endif /*SIGNED_COMPARE_SLOW*/
  44.  
  45. static int GIFNextPixel(void);
  46. static void compress( int init_bits, FILE* outfile );
  47. static void init_output(void);
  48. static void output( code_int code );
  49. static void cl_block( void );
  50. static void cl_hash( count_int hsize );
  51. static void char_out( int c );
  52. static void flush_char( void );
  53.  
  54. /*****************************************************************************
  55.  *
  56.  * GIFENCODE.C    - GIF Image compression interface
  57.  *
  58.  * GIFEncode( FName, commonInfo, colornum, transp, interlace, palette )
  59.  *
  60.  *****************************************************************************/
  61.  
  62. static int Width, Height;
  63. static int BitsPerPixel, alphaindex, isInterlaced;
  64. static int yPtr, yPass;
  65. static const char *comment;
  66. static unsigned char **imageMap;
  67.  
  68. /*
  69.  * Return the next pixel from the image
  70.  */
  71. static int GIFNextPixel(void)
  72. {
  73.     int eol, r, g, b, a;
  74.  
  75.     if (yPtr < 0)
  76.         return EOF;
  77.     if ((eol = getPixel(&r, &g, &b, &a)) < 0) {
  78.         yPtr = -1;
  79.         return EOF;
  80.     }
  81.     if (isInterlaced & eol) {
  82.         yPtr += yPass ? (0x10 >> yPass) : 0x08;
  83.         if (yPtr >= Height) {
  84.             if (++yPass > 3)
  85.                 yPtr = -1;
  86.             else
  87.                 resetPixel(imageMap, (yPtr = 8 >> yPass));
  88.         }else
  89.             resetPixel(imageMap, yPtr);
  90.     }
  91.     if (alphaindex >= 0 && a == AlphaTransp)
  92.         return alphaindex;
  93.     return mapping(r, g, b);
  94. }
  95.  
  96.  
  97. void GIFEncode( FILE *fp, commonInfo *cinf, unsigned char **map,
  98.         int colornum, int transp, int interlace, paltype *palette )
  99. {
  100.     int Resolution, ColorMapSize, InitCodeSize;
  101.     int i, j, power, n, B;
  102.     BOOL gif89;
  103.  
  104.     isInterlaced = interlace;
  105.     resetPixel(imageMap = map, yPtr = 0);
  106.     yPass = 0;
  107.     alphaindex = transp;
  108.     comment = begin_comm(cinf->memo, YES);
  109.     n = colornum;
  110.     if (alphaindex && n < 256) n++;
  111.     for (i = 1, power = 0x02; i < 8; i++, power <<= 1)
  112.         if (power >= n) break;
  113.     BitsPerPixel = i;
  114.     ColorMapSize = 1 << BitsPerPixel;
  115.     Width = cinf->width;
  116.     Height = cinf->height;
  117.     Resolution = BitsPerPixel;
  118.  
  119.     /* The initial code size */
  120.     InitCodeSize = ( BitsPerPixel <= 1 ) ? 2 : BitsPerPixel;
  121.  
  122.     /* Write the Magic header */
  123.     gif89 = (alphaindex >= 0 || comment);
  124.     fprintf(fp, "%s", gif89 ? "GIF89a":"GIF87a");
  125.  
  126.     /* Write out the screen width and height */
  127.     put_short( cinf->width, fp );
  128.     put_short( cinf->height, fp );
  129.  
  130.     /* Indicate that there is a global colour map */
  131.     B = 0x80;            /* Yes, there is a color map */
  132.     B |= (Resolution - 1) << 5;    /* OR in the resolution */
  133.     B |= (BitsPerPixel - 1);    /* OR in the Bits per Pixel */
  134.     fputc( B, fp );
  135.  
  136.     /* Write out the Background colour */
  137.     fputc( 0, fp );
  138.     fputc( 0, fp );    /* Byte of 0's (future expansion) */
  139.  
  140.     /* Write out the Global Colour Map */
  141.     n = (ColorMapSize < colornum) ? ColorMapSize : colornum;
  142.     for(i = 0; i < n; ++i ) {
  143.         unsigned char *p = palette[i];
  144.         for (j = 0; j < 3; j++)
  145.             fputc( p[j], fp );
  146.     }
  147.     for( ; i < ColorMapSize; ++i ) {
  148.         for (j = 0; j < 3; j++)
  149.             fputc( 255, fp );    /* stab */
  150.     }
  151.  
  152.     if (gif89) {
  153.         if (alphaindex >= 0) {
  154.             fputc('!', fp);        /* Extension */
  155.             fputc(0xf9, fp);    /* Graphic Control Extension */
  156.             fputc(4, fp);        /* Block Size */
  157.             fputc(TRANSPARENCY, fp);
  158.             fputc(0, fp);
  159.             fputc(0, fp);        /* Delay Time */
  160.             fputc(alphaindex, fp);    /* Transparent Color Index */
  161.             fputc(0, fp);        /* Block Terminator */
  162.         }
  163.         if (comment == NULL)
  164.             comment = "by ToyViewer";
  165.         i = strlen(comment);
  166.         fputc('!', fp);        /* Extension */
  167.         fputc(0xfe, fp);    /* Comment Extension */
  168.         fputc(i, fp);        /* Block Size */
  169.         fprintf(fp, "%s", comment);
  170.         fputc(0, fp);        /* Block Terminator */
  171.     }
  172.  
  173.     /* Write an Image separator */
  174.     fputc( ',', fp );
  175.  
  176.     /* Write the Image header */
  177.     put_short( 0, fp );    /* LeftOfs */
  178.     put_short( 0, fp );    /* TopOfs */
  179.     put_short( Width, fp );
  180.     put_short( Height, fp );
  181.     /* No Local Color Table & Interlace Mode */
  182.     fputc( interlace ? 0x40 : 0x00, fp );
  183.  
  184.     /* Write out the initial code size */
  185.     fputc( InitCodeSize, fp );
  186.  
  187.     /*
  188.      * Go and actually compress the data
  189.      */
  190.     compress( InitCodeSize+1, fp );
  191.  
  192.     /* Write out a Zero-length packet (to end the series) */
  193.     fputc( 0, fp );
  194.     /* Write the GIF file terminator */
  195.     fputc( ';', fp );
  196. }
  197.  
  198.  
  199. /***************************************************************************
  200.  *
  201.  *  GIFCOMPR.C    - GIF Image compression routines
  202.  *
  203.  *  Lempel-Ziv compression based on 'compress'.  GIF modifications by
  204.  *  David Rowley (mgardi@watdcsu.waterloo.edu)
  205.  *
  206.  ***************************************************************************/
  207.  
  208. /*
  209.  * General DEFINEs
  210.  */
  211.  
  212. #define BITS    12
  213. #define HSIZE    5003    /* 80% occupancy */
  214.  
  215. /*
  216.  *
  217.  * GIF Image compression - modified 'compress'
  218.  *
  219.  * Based on: compress.c - File compression ala IEEE Computer, June 1984.
  220.  *
  221.  * By Authors:  Spencer W. Thomas    (decvax!harpo!utah-cs!utah-gr!thomas)
  222.  *        Jim McKie        (decvax!mcvax!jim)
  223.  *        Steve Davies        (decvax!vax135!petsd!peora!srd)
  224.  *        Ken Turkowski        (decvax!decwrl!turtlevax!ken)
  225.  *        James A. Woods        (decvax!ihnp4!ames!jaw)
  226.  *        Joe Orost        (decvax!vax135!petsd!joe)
  227.  */
  228. #include <ctype.h>
  229.  
  230. static int n_bits;        /* number of bits/code */
  231. static int maxbits = BITS;    /* user settable max # bits/code */
  232. static code_int maxcode;    /* maximum code, given n_bits */
  233. static code_int maxmaxcode = (code_int)1 << BITS;
  234.                 /* should NEVER generate this code */
  235. #ifdef COMPATIBLE        /* But wrong! */
  236. # define MAXCODE(n_bits)    ((code_int) 1 << (n_bits) - 1)
  237. #else /*COMPATIBLE*/
  238. # define MAXCODE(n_bits)    (((code_int) 1 << (n_bits)) - 1)
  239. #endif /*COMPATIBLE*/
  240.  
  241. static count_int htab [HSIZE];
  242. static unsigned short codetab [HSIZE];
  243. #define HashTabOf(i)       htab[i]
  244. #define CodeTabOf(i)    codetab[i]
  245.  
  246. static code_int hsize = HSIZE;    /* for dynamic table sizing */
  247.  
  248. /*
  249.  * To save much memory, we overlay the table used by compress() with those
  250.  * used by decompress().  The tab_prefix table is the same size and type
  251.  * as the codetab.  The tab_suffix table needs 2**BITS characters.  We
  252.  * get this from the beginning of htab.  The output stack uses the rest
  253.  * of htab, and contains characters.  There is plenty of room for any
  254.  * possible stack (stack used to be 8000 characters).
  255.  */
  256.  
  257. #define tab_prefixof(i) CodeTabOf(i)
  258. #define tab_suffixof(i)    ((unsigned char *)(htab))[i]
  259. #define de_stack    ((unsigned char *)&tab_suffixof((code_int)1<<BITS))
  260.  
  261. static code_int free_ent = 0;    /* first unused entry */
  262.  
  263. /*
  264.  * block compression parameters -- after all codes are used up,
  265.  * and compression rate changes, start over.
  266.  */
  267. static int clear_flg = 0;
  268.  
  269. static int offset;
  270. static long int in_count = 1;    /* length of input */
  271. static long int out_count = 0;    /* # of codes output (for debugging) */
  272.  
  273. /*
  274.  * compress stdin to stdout
  275.  *
  276.  * Algorithm:  use open addressing double hashing (no chaining) on the
  277.  * prefix code / next character combination.  We do a variant of Knuth's
  278.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  279.  * secondary probe.  Here, the modular division first probe is gives way
  280.  * to a faster exclusive-or manipulation.  Also do block compression with
  281.  * an adaptive reset, whereby the code table is cleared when the compression
  282.  * ratio decreases, but after the table fills.  The variable-length output
  283.  * codes are re-sized at this point, and a special CLEAR code is generated
  284.  * for the decompressor.  Late addition:  construct the table according to
  285.  * file size for noticeable speed improvement on small files.  Please direct
  286.  * questions about this implementation to ames!jaw.
  287.  */
  288.  
  289. static int g_init_bits;
  290. static FILE* g_outfile;
  291.  
  292. static int ClearCode;
  293. static int EOFCode;
  294.  
  295. static void
  296. compress( int init_bits, FILE *outfile )
  297. {
  298.     long fcode;
  299.     code_int i /* = 0 */;
  300.     int c;
  301.     code_int ent;
  302.     code_int disp;
  303.     code_int hsize_reg;
  304.     int hshift;
  305.  
  306.     /*
  307.      * Set up the globals:    g_init_bits - initial number of bits
  308.      *                g_outfile   - pointer to output file
  309.      */
  310.     g_init_bits = init_bits;
  311.     g_outfile = outfile;
  312.  
  313.     /*
  314.      * Set up the necessary values
  315.      */
  316.     offset = 0;
  317.     out_count = 0;
  318.     clear_flg = 0;
  319.     in_count = 1;
  320.     maxcode = MAXCODE(n_bits = g_init_bits);
  321.  
  322.     ClearCode = (1 << (init_bits - 1));
  323.     EOFCode = ClearCode + 1;
  324.     free_ent = ClearCode + 2;
  325.  
  326.     init_output();    /* Set up the 'byte output' routine */
  327.  
  328.     ent = GIFNextPixel();
  329.  
  330.     hshift = 0;
  331.     for ( fcode = (long) hsize;  fcode < 65536L; fcode *= 2L )
  332.     ++hshift;
  333.     hshift = 8 - hshift;        /* set hash code range bound */
  334.  
  335.     hsize_reg = hsize;
  336.     cl_hash( (count_int) hsize_reg);    /* clear hash table */
  337.  
  338.     output( (code_int)ClearCode );
  339.  
  340.     while ( (c = GIFNextPixel()) != EOF ) {
  341.     ++in_count;
  342.  
  343.     fcode = (long) (((long) c << maxbits) + ent);
  344.     i = (((code_int)c << hshift) ^ ent);    /* xor hashing */
  345.  
  346.     if ( HashTabOf (i) == fcode ) {
  347.         ent = CodeTabOf (i);
  348.         continue;
  349.     } else if ( (long)HashTabOf (i) < 0 )    /* empty slot */
  350.         goto nomatch;
  351.     disp = hsize_reg - i;    /* secondary hash (after G. Knott) */
  352.     if ( i == 0 )
  353.         disp = 1;
  354. probe:
  355.     if ( (i -= disp) < 0 )
  356.         i += hsize_reg;
  357.  
  358.     if ( HashTabOf (i) == fcode ) {
  359.         ent = CodeTabOf (i);
  360.         continue;
  361.     }
  362.     if ( (long)HashTabOf (i) > 0 )
  363.         goto probe;
  364. nomatch:
  365.     output ( (code_int) ent );
  366.     ++out_count;
  367.     ent = c;
  368.     if ( free_ent < maxmaxcode ) {
  369.         CodeTabOf (i) = free_ent++; /* code -> hashtable */
  370.         HashTabOf (i) = fcode;
  371.     } else
  372.         cl_block();
  373.     }
  374.     /*
  375.      * Put out the final code.
  376.      */
  377.     output( (code_int)ent );
  378.     ++out_count;
  379.     output( (code_int) EOFCode );
  380. }
  381.  
  382. /*****************************************************************
  383.  * Output the given code.
  384.  * Inputs:
  385.  *      code:    A n_bits-bit integer.  If == -1, then EOF.
  386.  *        This assumes that n_bits =< (long)wordsize - 1.
  387.  * Outputs:
  388.  *      Outputs code to the file.
  389.  * Assumptions:
  390.  *      Chars are 8 bits long.
  391.  * Algorithm:
  392.  *      Maintain a BITS character long buffer (so that 8 codes will
  393.  * fit in it exactly).  Use the VAX insv instruction to insert each
  394.  * code in turn.  When the buffer fills up empty it and start over.
  395.  */
  396.  
  397. static unsigned long cur_accum = 0;
  398. static int cur_bits = 0;
  399.  
  400. static void output( code_int code )
  401. {
  402.     static unsigned long masks[] = {
  403.         0x0000, 0x0001, 0x0003, 0x0007, 0x000F,
  404.         0x001F, 0x003F, 0x007F, 0x00FF,
  405.         0x01FF, 0x03FF, 0x07FF, 0x0FFF,
  406.         0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
  407.  
  408.     if( cur_bits > 0 ) {
  409.         cur_accum &= masks[ cur_bits ];
  410.         cur_accum |= ((long)code << cur_bits);
  411.     }else
  412.         cur_accum = code;
  413.     cur_bits += n_bits;
  414.     while( cur_bits >= 8 ) {
  415.         char_out( (unsigned int)(cur_accum & 0xff) );
  416.         cur_accum >>= 8;
  417.         cur_bits -= 8;
  418.     }
  419.     /*
  420.      * If the next entry is going to be too big for the code size,
  421.      * then increase it, if possible.
  422.      */
  423.     if ( free_ent > maxcode || clear_flg ) {
  424.         if( clear_flg ) {
  425.             maxcode = MAXCODE (n_bits = g_init_bits);
  426.             clear_flg = 0;
  427.         } else {
  428.             ++n_bits;
  429.             maxcode = ( n_bits == maxbits )
  430.                 ? maxmaxcode : MAXCODE(n_bits);
  431.         }
  432.     }
  433.     if( code == EOFCode ) {
  434.         /* At EOF, write the rest of the buffer. */
  435.         while( cur_bits > 0 ) {
  436.             char_out( (unsigned int)(cur_accum & 0xff) );
  437.             cur_accum >>= 8;
  438.             cur_bits -= 8;
  439.         }
  440.         flush_char();
  441.         fflush( g_outfile );
  442.         /* if( ferror( g_outfile ) ) writeerr(); */
  443.     }
  444. }
  445.  
  446. /*
  447.  * Clear out the hash table
  448.  */
  449. static void cl_block(void)    /* table clear for block compress */
  450. {
  451.     cl_hash ( (count_int) hsize );
  452.     free_ent = ClearCode + 2;
  453.     clear_flg = 1;
  454.     output( (code_int)ClearCode );
  455. }
  456.  
  457. static void cl_hash(count_int hsize)    /* reset code table */
  458. {
  459.  
  460.     count_int *htab_p = htab+hsize;
  461.     long i;
  462.     long m1 = -1;
  463.  
  464.     i = hsize - 16;
  465.     do {        /* might use Sys V memset(3) here */
  466.         *(htab_p-16) = m1;
  467.         *(htab_p-15) = m1;
  468.         *(htab_p-14) = m1;
  469.         *(htab_p-13) = m1;
  470.         *(htab_p-12) = m1;
  471.         *(htab_p-11) = m1;
  472.         *(htab_p-10) = m1;
  473.         *(htab_p-9) = m1;
  474.         *(htab_p-8) = m1;
  475.         *(htab_p-7) = m1;
  476.         *(htab_p-6) = m1;
  477.         *(htab_p-5) = m1;
  478.         *(htab_p-4) = m1;
  479.         *(htab_p-3) = m1;
  480.         *(htab_p-2) = m1;
  481.         *(htab_p-1) = m1;
  482.         htab_p -= 16;
  483.     } while ((i -= 16) >= 0);
  484.  
  485.     for ( i += 16; i > 0; --i )
  486.         *--htab_p = m1;
  487. }
  488.  
  489. /****************************************************************************
  490.  *
  491.  * GIF Specific routines
  492.  *
  493.  ****************************************************************************/
  494.  
  495. static int a_count;    /* Number of characters so far in this 'packet' */
  496. static char accum[256];    /* Define the storage for the packet accumulator */
  497.  
  498. static void init_output(void)
  499. {
  500.     cur_accum = 0;
  501.     cur_bits = 0;
  502.     a_count = 0;
  503. }
  504.  
  505. /*
  506.  * Add a character to the end of the current packet, and if it is 254
  507.  * characters, flush the packet to disk.
  508.  */
  509. static void char_out( int c )
  510. {
  511.     accum[ a_count++ ] = c;
  512.     if( a_count >= 254 )
  513.         flush_char();
  514. }
  515.  
  516. /*
  517.  * Flush the packet to disk, and reset the accumulator
  518.  */
  519. static void flush_char( void )
  520. {
  521.     if( a_count > 0 ) {
  522.         fputc( a_count, g_outfile );
  523.         fwrite( accum, 1, a_count, g_outfile );
  524.         a_count = 0;
  525.     }
  526. }
  527.