home *** CD-ROM | disk | FTP | other *** search
/ Resource Library: Graphics / graphics-16000.iso / general / convrtrs / pbmplus / ntpbmsrc.lha / netpbm / ppm / ppmtogif.c < prev    next >
C/C++ Source or Header  |  1993-11-12  |  24KB  |  958 lines
  1. /* ppmtogif.c - read a portable pixmap and produce a GIF file
  2. **
  3. ** Based on GIFENCOD by David Rowley <mgardi@watdscu.waterloo.edu>.A
  4. ** Lempel-Zim compression based on "compress".
  5. **
  6. ** Modified by Marcel Wijkstra <wijkstra@fwi.uva.nl>
  7. **
  8. **
  9. ** Copyright (C) 1989 by Jef Poskanzer.
  10. **
  11. ** Permission to use, copy, modify, and distribute this software and its
  12. ** documentation for any purpose and without fee is hereby granted, provided
  13. ** that the above copyright notice appear in all copies and that both that
  14. ** copyright notice and this permission notice appear in supporting
  15. ** documentation.  This software is provided "as is" without express or
  16. ** implied warranty.
  17. **
  18. ** The Graphics Interchange Format(c) is the Copyright property of
  19. ** CompuServe Incorporated.  GIF(sm) is a Service Mark property of
  20. ** CompuServe Incorporated.
  21. */
  22.  
  23. #include "ppm.h"
  24. #include "ppmcmap.h"
  25.  
  26. #define MAXCOLORS 256
  27.  
  28. /*
  29.  * Pointer to function returning an int
  30.  */
  31. typedef int (* ifunptr) ARGS((int, int));
  32.  
  33. /*
  34.  * a code_int must be able to hold 2**BITS values of type int, and also -1
  35.  */
  36. typedef int             code_int;
  37.  
  38. #ifdef SIGNED_COMPARE_SLOW
  39. typedef unsigned long int count_int;
  40. typedef unsigned short int count_short;
  41. #else /*SIGNED_COMPARE_SLOW*/
  42. typedef long int          count_int;
  43. #endif /*SIGNED_COMPARE_SLOW*/
  44.  
  45. static int colorstobpp ARGS(( int colors ));
  46. static int GetPixel ARGS(( int x, int y ));
  47. static void BumpPixel ARGS(( void ));
  48. static int GIFNextPixel ARGS(( ifunptr getpixel ));
  49. static void GIFEncode ARGS(( FILE* fp, int GWidth, int GHeight, int GInterlace, int Background, int Transparent, int BitsPerPixel, int* Red, int* Green, int* Blue, ifunptr GetPixel ));
  50. int Red[MAXCOLORS],Green[MAXCOLORS],Blue[MAXCOLORS],perm[MAXCOLORS],permi[MAXCOLORS];
  51. int colors;
  52. pixval maxtmp;
  53. static void Putword ARGS(( int w, FILE* fp ));
  54. static void compress ARGS(( int init_bits, FILE* outfile, ifunptr ReadValue ));
  55. static void output ARGS(( code_int code ));
  56. static void cl_block ARGS(( void ));
  57. static void cl_hash ARGS(( count_int hsize ));
  58. static void writeerr ARGS(( void ));
  59. static void char_init ARGS(( void ));
  60. static void char_out ARGS(( int c ));
  61. static void flush_char ARGS(( void ));
  62. static int sqr ARGS((int x));
  63. static int closestcolor ARGS((pixel color));
  64.  
  65. static pixel** pixels;
  66. static colorhash_table cht;
  67.  
  68. int
  69. main( argc, argv )
  70.     int argc;
  71.     char* argv[];
  72.     {
  73.     FILE* ifp;
  74.     int argn, rows, cols, i,j,k, BitsPerPixel;
  75.     int interlace, sort, map, transparent;
  76.     pixel transcolor;
  77.     char *mapfile;
  78.     pixval maxval;
  79.     colorhist_vector chv;
  80.     char* usage = "[-interlace] [-sort] [-map mapfile] [-transparent color] [ppmfile]";
  81.  
  82.     ppm_init( &argc, argv );
  83.  
  84.     argn = 1;
  85.     interlace = 0;
  86.     sort = 0;
  87.     map = 0;
  88.     transparent = -1;
  89.  
  90.     while ( argn < argc && argv[argn][0] == '-' && argv[argn][1] != '\0' )
  91.         {
  92.         if ( pm_keymatch( argv[argn], "-interlace", 2 ) )
  93.             interlace = 1;
  94.         else if ( pm_keymatch( argv[argn], "-nointerlace", 2 ) )
  95.             interlace = 0;
  96.         else if ( pm_keymatch( argv[argn], "-sort", 2 ) )
  97.             sort = 1;
  98.         else if ( pm_keymatch( argv[argn], "-map", 2 ) ) {
  99.             map = 1;
  100.             if (++argn < argc)
  101.               mapfile = argv[argn];
  102.             else pm_usage(usage); }
  103.     else if ( pm_keymatch( argv[argn], "-transparent", 2 ) ) {
  104.         transparent = 1;
  105.         if (++argn < argc)
  106.         transcolor = ppm_parsecolor( argv[argn], PPM_MAXMAXVAL );
  107.         else
  108.         pm_usage(usage);
  109.     }
  110.         else
  111.             pm_usage( usage );
  112.         ++argn;
  113.         }
  114.  
  115.     /* Read the colormap from another file. */
  116.     if (map) {
  117.       ifp = pm_openr(mapfile);
  118.       pixels = ppm_readppm( ifp, &cols, &rows, &maxval );
  119.       pm_close( ifp );
  120.  
  121.       /* Figure out the colormap from the <mapfile>. */
  122.       pm_message( "computing other colormap..." );
  123.       chv = ppm_computecolorhist( pixels, cols, rows, MAXCOLORS, &colors );
  124.  
  125.       ppm_freearray(pixels,rows); }
  126.  
  127.     if ( argn < argc )
  128.         {
  129.         ifp = pm_openr( argv[argn] );
  130.         ++argn;
  131.         }
  132.     else
  133.         ifp = stdin;
  134.  
  135.     if ( argn != argc )
  136.         pm_usage( usage );
  137.  
  138.     pixels = ppm_readppm( ifp, &cols, &rows, &maxtmp );
  139.     if (!map)
  140.       maxval=maxtmp;
  141.  
  142.     pm_close( ifp );
  143.  
  144.     /* Figure out the colormap. */
  145.     if (!map) {
  146.       pm_message( "computing colormap..." );
  147.       chv = ppm_computecolorhist( pixels, cols, rows, MAXCOLORS, &colors ); }
  148.  
  149.     if ( chv == (colorhist_vector) 0 )
  150.         pm_error(
  151.             "too many colors - try doing a 'ppmquant %d'", MAXCOLORS );
  152.     pm_message( "%d colors found", colors );
  153.  
  154.     /* Now turn the ppm colormap into the appropriate GIF colormap. */
  155.     if ( maxval > 255 )
  156.         pm_message(
  157.             "maxval is not 255 - automatically rescaling colors" );
  158.     for ( i = 0; i < colors; ++i )
  159.         {
  160.         if ( maxval == 255 )
  161.             {
  162.             Red[i] = PPM_GETR( chv[i].color );
  163.             Green[i] = PPM_GETG( chv[i].color );
  164.             Blue[i] = PPM_GETB( chv[i].color );
  165.             }
  166.         else
  167.             {
  168.             Red[i] = (int) PPM_GETR( chv[i].color ) * 255 / maxval;
  169.             Green[i] = (int) PPM_GETG( chv[i].color ) * 255 / maxval;
  170.             Blue[i] = (int) PPM_GETB( chv[i].color ) * 255 / maxval;
  171.             }
  172.         }
  173.  
  174.     /* Sort the colormap */
  175.     for (i=0;i<colors;i++)
  176.       permi[i]=i;
  177.     if (sort) {
  178.       pm_message("sorting colormap");
  179.       for (i=0;i<colors;i++)
  180.         for (j=i+1;j<colors;j++)
  181.           if (((Red[i]*MAXCOLORS)+Green[i])*MAXCOLORS+Blue[i] >
  182.               ((Red[j]*MAXCOLORS)+Green[j])*MAXCOLORS+Blue[j]) {
  183.             k=permi[i]; permi[i]=permi[j]; permi[j]=k;
  184.             k=Red[i]; Red[i]=Red[j]; Red[j]=k;
  185.             k=Green[i]; Green[i]=Green[j]; Green[j]=k;
  186.             k=Blue[i]; Blue[i]=Blue[j]; Blue[j]=k; } }
  187.     for (i=0;i<colors;i++)
  188.       perm[permi[i]]=i;
  189.  
  190.     BitsPerPixel = colorstobpp( colors );
  191.  
  192.     /* And make a hash table for fast lookup. */
  193.     cht = ppm_colorhisttocolorhash( chv, colors );
  194.     ppm_freecolorhist( chv );
  195.  
  196.     /* figure out the transparent colour index */
  197.     if (transparent > 0) {
  198.         transparent = ppm_lookupcolor( cht, &transcolor );
  199.     if (transparent == -1)
  200.         transparent = closestcolor( transcolor );
  201.         else
  202.             transparent = perm[transparent];
  203.     }
  204.  
  205.     /* All set, let's do it. */
  206.     GIFEncode(
  207.         stdout, cols, rows, interlace, 0, transparent, BitsPerPixel,
  208.         Red, Green, Blue, GetPixel );
  209.  
  210.     exit( 0 );
  211.     }
  212.  
  213. static int
  214. colorstobpp( colors )
  215. int colors;
  216.     {
  217.     int bpp;
  218.  
  219.     if ( colors <= 2 )
  220.         bpp = 1;
  221.     else if ( colors <= 4 )
  222.         bpp = 2;
  223.     else if ( colors <= 8 )
  224.         bpp = 3;
  225.     else if ( colors <= 16 )
  226.         bpp = 4;
  227.     else if ( colors <= 32 )
  228.         bpp = 5;
  229.     else if ( colors <= 64 )
  230.         bpp = 6;
  231.     else if ( colors <= 128 )
  232.         bpp = 7;
  233.     else if ( colors <= 256 )
  234.         bpp = 8;
  235.     else
  236.         pm_error( "can't happen" );
  237.  
  238.     return bpp;
  239.     }
  240.  
  241.  
  242. static int
  243. sqr(x)
  244. int x;
  245.   {
  246.   return x*x;
  247.   }
  248.  
  249.  
  250. static int
  251. closestcolor(color)
  252. pixel color;
  253.   {
  254.   int i,r,g,b,d,
  255.       imin,dmin;
  256.  
  257.   r=(int)PPM_GETR(color)*255/maxtmp;
  258.   g=(int)PPM_GETG(color)*255/maxtmp;
  259.   b=(int)PPM_GETB(color)*255/maxtmp;
  260.  
  261.   dmin=1000000;
  262.   for (i=0;i<colors;i++) {
  263.     d=sqr(r-Red[i])+sqr(g-Green[i])+sqr(b-Blue[i]);
  264.     if (d<dmin) {
  265.       dmin=d;
  266.       imin=i; } }
  267.   ppm_addtocolorhash(cht,&color,permi[imin]);
  268.   return imin;
  269.   }
  270.  
  271.  
  272. static int
  273. GetPixel( x, y )
  274. int x, y;
  275.     {
  276.     int color;
  277.  
  278.     color = ppm_lookupcolor( cht, &pixels[y][x] );
  279.     if (color == -1)
  280.       color = closestcolor(pixels[y][x]);
  281.     else
  282.       color=perm[color];
  283.     return color;
  284.     }
  285.  
  286.  
  287. /*****************************************************************************
  288.  *
  289.  * GIFENCODE.C    - GIF Image compression interface
  290.  *
  291.  * GIFEncode( FName, GHeight, GWidth, GInterlace, Background, Transparent,
  292.  *            BitsPerPixel, Red, Green, Blue, GetPixel )
  293.  *
  294.  *****************************************************************************/
  295.  
  296. #define TRUE 1
  297. #define FALSE 0
  298.  
  299. static int Width, Height;
  300. static int curx, cury;
  301. static long CountDown;
  302. static int Pass = 0;
  303. static int Interlace;
  304.  
  305. /*
  306.  * Bump the 'curx' and 'cury' to point to the next pixel
  307.  */
  308. static void
  309. BumpPixel()
  310. {
  311.         /*
  312.          * Bump the current X position
  313.          */
  314.         ++curx;
  315.  
  316.         /*
  317.          * If we are at the end of a scan line, set curx back to the beginning
  318.          * If we are interlaced, bump the cury to the appropriate spot,
  319.          * otherwise, just increment it.
  320.          */
  321.         if( curx == Width ) {
  322.                 curx = 0;
  323.  
  324.                 if( !Interlace )
  325.                         ++cury;
  326.                 else {
  327.                      switch( Pass ) {
  328.  
  329.                        case 0:
  330.                           cury += 8;
  331.                           if( cury >= Height ) {
  332.                                 ++Pass;
  333.                                 cury = 4;
  334.                           }
  335.                           break;
  336.  
  337.                        case 1:
  338.                           cury += 8;
  339.                           if( cury >= Height ) {
  340.                                 ++Pass;
  341.                                 cury = 2;
  342.                           }
  343.                           break;
  344.  
  345.                        case 2:
  346.                           cury += 4;
  347.                           if( cury >= Height ) {
  348.                              ++Pass;
  349.                              cury = 1;
  350.                           }
  351.                           break;
  352.  
  353.                        case 3:
  354.                           cury += 2;
  355.                           break;
  356.                         }
  357.                 }
  358.         }
  359. }
  360.  
  361. /*
  362.  * Return the next pixel from the image
  363.  */
  364. static int
  365. GIFNextPixel( getpixel )
  366. ifunptr getpixel;
  367. {
  368.         int r;
  369.  
  370.         if( CountDown == 0 )
  371.                 return EOF;
  372.  
  373.         --CountDown;
  374.  
  375.         r = ( * getpixel )( curx, cury );
  376.  
  377.         BumpPixel();
  378.  
  379.         return r;
  380. }
  381.  
  382. /* public */
  383.  
  384. static void
  385. GIFEncode( fp, GWidth, GHeight, GInterlace, Background, Transparent,
  386.            BitsPerPixel, Red, Green, Blue, GetPixel )
  387.  
  388. FILE* fp;
  389. int GWidth, GHeight;
  390. int GInterlace;
  391. int Background;
  392. int Transparent;
  393. int BitsPerPixel;
  394. int Red[], Green[], Blue[];
  395. ifunptr GetPixel;
  396. {
  397.         int B;
  398.         int RWidth, RHeight;
  399.         int LeftOfs, TopOfs;
  400.         int Resolution;
  401.         int ColorMapSize;
  402.         int InitCodeSize;
  403.         int i;
  404.  
  405.         Interlace = GInterlace;
  406.  
  407.         ColorMapSize = 1 << BitsPerPixel;
  408.  
  409.         RWidth = Width = GWidth;
  410.         RHeight = Height = GHeight;
  411.         LeftOfs = TopOfs = 0;
  412.  
  413.         Resolution = BitsPerPixel;
  414.  
  415.         /*
  416.          * Calculate number of bits we are expecting
  417.          */
  418.         CountDown = (long)Width * (long)Height;
  419.  
  420.         /*
  421.          * Indicate which pass we are on (if interlace)
  422.          */
  423.         Pass = 0;
  424.  
  425.         /*
  426.          * The initial code size
  427.          */
  428.         if( BitsPerPixel <= 1 )
  429.                 InitCodeSize = 2;
  430.         else
  431.                 InitCodeSize = BitsPerPixel;
  432.  
  433.         /*
  434.          * Set up the current x and y position
  435.          */
  436.         curx = cury = 0;
  437.  
  438.         /*
  439.          * Write the Magic header
  440.          */
  441.         fwrite( Transparent < 0 ? "GIF87a" : "GIF89a", 1, 6, fp );
  442.  
  443.         /*
  444.          * Write out the screen width and height
  445.          */
  446.         Putword( RWidth, fp );
  447.         Putword( RHeight, fp );
  448.  
  449.         /*
  450.          * Indicate that there is a global colour map
  451.          */
  452.         B = 0x80;       /* Yes, there is a color map */
  453.  
  454.         /*
  455.          * OR in the resolution
  456.          */
  457.         B |= (Resolution - 1) << 5;
  458.  
  459.         /*
  460.          * OR in the Bits per Pixel
  461.          */
  462.         B |= (BitsPerPixel - 1);
  463.  
  464.         /*
  465.          * Write it out
  466.          */
  467.         fputc( B, fp );
  468.  
  469.         /*
  470.          * Write out the Background colour
  471.          */
  472.         fputc( Background, fp );
  473.  
  474.         /*
  475.          * Byte of 0's (future expansion)
  476.          */
  477.         fputc( 0, fp );
  478.  
  479.         /*
  480.          * Write out the Global Colour Map
  481.          */
  482.         for( i=0; i<ColorMapSize; ++i ) {
  483.                 fputc( Red[i], fp );
  484.                 fputc( Green[i], fp );
  485.                 fputc( Blue[i], fp );
  486.         }
  487.  
  488.     /*
  489.      * Write out extension for transparent colour index, if necessary.
  490.      */
  491.     if ( Transparent >= 0 ) {
  492.         fputc( '!', fp );
  493.         fputc( 0xf9, fp );
  494.         fputc( 4, fp );
  495.         fputc( 1, fp );
  496.         fputc( 0, fp );
  497.         fputc( 0, fp );
  498.         fputc( Transparent, fp );
  499.         fputc( 0, fp );
  500.     }
  501.  
  502.         /*
  503.          * Write an Image separator
  504.          */
  505.         fputc( ',', fp );
  506.  
  507.         /*
  508.          * Write the Image header
  509.          */
  510.  
  511.         Putword( LeftOfs, fp );
  512.         Putword( TopOfs, fp );
  513.         Putword( Width, fp );
  514.         Putword( Height, fp );
  515.  
  516.         /*
  517.          * Write out whether or not the image is interlaced
  518.          */
  519.         if( Interlace )
  520.                 fputc( 0x40, fp );
  521.         else
  522.                 fputc( 0x00, fp );
  523.  
  524.         /*
  525.          * Write out the initial code size
  526.          */
  527.         fputc( InitCodeSize, fp );
  528.  
  529.         /*
  530.          * Go and actually compress the data
  531.          */
  532.         compress( InitCodeSize+1, fp, GetPixel );
  533.  
  534.         /*
  535.          * Write out a Zero-length packet (to end the series)
  536.          */
  537.         fputc( 0, fp );
  538.  
  539.         /*
  540.          * Write the GIF file terminator
  541.          */
  542.         fputc( ';', fp );
  543.  
  544.         /*
  545.          * And close the file
  546.          */
  547.         fclose( fp );
  548. }
  549.  
  550. /*
  551.  * Write out a word to the GIF file
  552.  */
  553. static void
  554. Putword( w, fp )
  555. int w;
  556. FILE* fp;
  557. {
  558.         fputc( w & 0xff, fp );
  559.         fputc( (w / 256) & 0xff, fp );
  560. }
  561.  
  562.  
  563. /***************************************************************************
  564.  *
  565.  *  GIFCOMPR.C       - GIF Image compression routines
  566.  *
  567.  *  Lempel-Ziv compression based on 'compress'.  GIF modifications by
  568.  *  David Rowley (mgardi@watdcsu.waterloo.edu)
  569.  *
  570.  ***************************************************************************/
  571.  
  572. /*
  573.  * General DEFINEs
  574.  */
  575.  
  576. #define BITS    12
  577.  
  578. #define HSIZE  5003            /* 80% occupancy */
  579.  
  580. #ifdef NO_UCHAR
  581.  typedef char   char_type;
  582. #else /*NO_UCHAR*/
  583.  typedef        unsigned char   char_type;
  584. #endif /*NO_UCHAR*/
  585.  
  586. /*
  587.  *
  588.  * GIF Image compression - modified 'compress'
  589.  *
  590.  * Based on: compress.c - File compression ala IEEE Computer, June 1984.
  591.  *
  592.  * By Authors:  Spencer W. Thomas       (decvax!harpo!utah-cs!utah-gr!thomas)
  593.  *              Jim McKie               (decvax!mcvax!jim)
  594.  *              Steve Davies            (decvax!vax135!petsd!peora!srd)
  595.  *              Ken Turkowski           (decvax!decwrl!turtlevax!ken)
  596.  *              James A. Woods          (decvax!ihnp4!ames!jaw)
  597.  *              Joe Orost               (decvax!vax135!petsd!joe)
  598.  *
  599.  */
  600. #include <ctype.h>
  601.  
  602. #define ARGVAL() (*++(*argv) || (--argc && *++argv))
  603.  
  604. static int n_bits;                        /* number of bits/code */
  605. static int maxbits = BITS;                /* user settable max # bits/code */
  606. static code_int maxcode;                  /* maximum code, given n_bits */
  607. static code_int maxmaxcode = (code_int)1 << BITS; /* should NEVER generate this code */
  608. #ifdef COMPATIBLE               /* But wrong! */
  609. # define MAXCODE(n_bits)        ((code_int) 1 << (n_bits) - 1)
  610. #else /*COMPATIBLE*/
  611. # define MAXCODE(n_bits)        (((code_int) 1 << (n_bits)) - 1)
  612. #endif /*COMPATIBLE*/
  613.  
  614. static count_int htab [HSIZE];
  615. static unsigned short codetab [HSIZE];
  616. #define HashTabOf(i)       htab[i]
  617. #define CodeTabOf(i)    codetab[i]
  618.  
  619. static code_int hsize = HSIZE;                 /* for dynamic table sizing */
  620.  
  621. /*
  622.  * To save much memory, we overlay the table used by compress() with those
  623.  * used by decompress().  The tab_prefix table is the same size and type
  624.  * as the codetab.  The tab_suffix table needs 2**BITS characters.  We
  625.  * get this from the beginning of htab.  The output stack uses the rest
  626.  * of htab, and contains characters.  There is plenty of room for any
  627.  * possible stack (stack used to be 8000 characters).
  628.  */
  629.  
  630. #define tab_prefixof(i) CodeTabOf(i)
  631. #define tab_suffixof(i)        ((char_type*)(htab))[i]
  632. #define de_stack               ((char_type*)&tab_suffixof((code_int)1<<BITS))
  633.  
  634. static code_int free_ent = 0;                  /* first unused entry */
  635.  
  636. /*
  637.  * block compression parameters -- after all codes are used up,
  638.  * and compression rate changes, start over.
  639.  */
  640. static int clear_flg = 0;
  641.  
  642. static int offset;
  643. static long int in_count = 1;            /* length of input */
  644. static long int out_count = 0;           /* # of codes output (for debugging) */
  645.  
  646. /*
  647.  * compress stdin to stdout
  648.  *
  649.  * Algorithm:  use open addressing double hashing (no chaining) on the
  650.  * prefix code / next character combination.  We do a variant of Knuth's
  651.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  652.  * secondary probe.  Here, the modular division first probe is gives way
  653.  * to a faster exclusive-or manipulation.  Also do block compression with
  654.  * an adaptive reset, whereby the code table is cleared when the compression
  655.  * ratio decreases, but after the table fills.  The variable-length output
  656.  * codes are re-sized at this point, and a special CLEAR code is generated
  657.  * for the decompressor.  Late addition:  construct the table according to
  658.  * file size for noticeable speed improvement on small files.  Please direct
  659.  * questions about this implementation to ames!jaw.
  660.  */
  661.  
  662. static int g_init_bits;
  663. static FILE* g_outfile;
  664.  
  665. static int ClearCode;
  666. static int EOFCode;
  667.  
  668. static void
  669. compress( init_bits, outfile, ReadValue )
  670. int init_bits;
  671. FILE* outfile;
  672. ifunptr ReadValue;
  673. {
  674.     register long fcode;
  675.     register code_int i /* = 0 */;
  676.     register int c;
  677.     register code_int ent;
  678.     register code_int disp;
  679.     register code_int hsize_reg;
  680.     register int hshift;
  681.  
  682.     /*
  683.      * Set up the globals:  g_init_bits - initial number of bits
  684.      *                      g_outfile   - pointer to output file
  685.      */
  686.     g_init_bits = init_bits;
  687.     g_outfile = outfile;
  688.  
  689.     /*
  690.      * Set up the necessary values
  691.      */
  692.     offset = 0;
  693.     out_count = 0;
  694.     clear_flg = 0;
  695.     in_count = 1;
  696.     maxcode = MAXCODE(n_bits = g_init_bits);
  697.  
  698.     ClearCode = (1 << (init_bits - 1));
  699.     EOFCode = ClearCode + 1;
  700.     free_ent = ClearCode + 2;
  701.  
  702.     char_init();
  703.  
  704.     ent = GIFNextPixel( ReadValue );
  705.  
  706.     hshift = 0;
  707.     for ( fcode = (long) hsize;  fcode < 65536L; fcode *= 2L )
  708.         ++hshift;
  709.     hshift = 8 - hshift;                /* set hash code range bound */
  710.  
  711.     hsize_reg = hsize;
  712.     cl_hash( (count_int) hsize_reg);            /* clear hash table */
  713.  
  714.     output( (code_int)ClearCode );
  715.  
  716. #ifdef SIGNED_COMPARE_SLOW
  717.     while ( (c = GIFNextPixel( ReadValue )) != (unsigned) EOF ) {
  718. #else /*SIGNED_COMPARE_SLOW*/
  719.     while ( (c = GIFNextPixel( ReadValue )) != EOF ) {  /* } */
  720. #endif /*SIGNED_COMPARE_SLOW*/
  721.  
  722.         ++in_count;
  723.  
  724.         fcode = (long) (((long) c << maxbits) + ent);
  725.         i = (((code_int)c << hshift) ^ ent);    /* xor hashing */
  726.  
  727.         if ( HashTabOf (i) == fcode ) {
  728.             ent = CodeTabOf (i);
  729.             continue;
  730.         } else if ( (long)HashTabOf (i) < 0 )      /* empty slot */
  731.             goto nomatch;
  732.         disp = hsize_reg - i;           /* secondary hash (after G. Knott) */
  733.         if ( i == 0 )
  734.             disp = 1;
  735. probe:
  736.         if ( (i -= disp) < 0 )
  737.             i += hsize_reg;
  738.  
  739.         if ( HashTabOf (i) == fcode ) {
  740.             ent = CodeTabOf (i);
  741.             continue;
  742.         }
  743.         if ( (long)HashTabOf (i) > 0 )
  744.             goto probe;
  745. nomatch:
  746.         output ( (code_int) ent );
  747.         ++out_count;
  748.         ent = c;
  749. #ifdef SIGNED_COMPARE_SLOW
  750.         if ( (unsigned) free_ent < (unsigned) maxmaxcode) {
  751. #else /*SIGNED_COMPARE_SLOW*/
  752.         if ( free_ent < maxmaxcode ) {  /* } */
  753. #endif /*SIGNED_COMPARE_SLOW*/
  754.             CodeTabOf (i) = free_ent++; /* code -> hashtable */
  755.             HashTabOf (i) = fcode;
  756.         } else
  757.                 cl_block();
  758.     }
  759.     /*
  760.      * Put out the final code.
  761.      */
  762.     output( (code_int)ent );
  763.     ++out_count;
  764.     output( (code_int) EOFCode );
  765. }
  766.  
  767. /*****************************************************************
  768.  * TAG( output )
  769.  *
  770.  * Output the given code.
  771.  * Inputs:
  772.  *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
  773.  *              that n_bits =< (long)wordsize - 1.
  774.  * Outputs:
  775.  *      Outputs code to the file.
  776.  * Assumptions:
  777.  *      Chars are 8 bits long.
  778.  * Algorithm:
  779.  *      Maintain a BITS character long buffer (so that 8 codes will
  780.  * fit in it exactly).  Use the VAX insv instruction to insert each
  781.  * code in turn.  When the buffer fills up empty it and start over.
  782.  */
  783.  
  784. static unsigned long cur_accum = 0;
  785. static int cur_bits = 0;
  786.  
  787. static unsigned long masks[] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000F,
  788.                                   0x001F, 0x003F, 0x007F, 0x00FF,
  789.                                   0x01FF, 0x03FF, 0x07FF, 0x0FFF,
  790.                                   0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
  791.  
  792. static void
  793. output( code )
  794. code_int  code;
  795. {
  796.     cur_accum &= masks[ cur_bits ];
  797.  
  798.     if( cur_bits > 0 )
  799.         cur_accum |= ((long)code << cur_bits);
  800.     else
  801.         cur_accum = code;
  802.  
  803.     cur_bits += n_bits;
  804.  
  805.     while( cur_bits >= 8 ) {
  806.         char_out( (unsigned int)(cur_accum & 0xff) );
  807.         cur_accum >>= 8;
  808.         cur_bits -= 8;
  809.     }
  810.  
  811.     /*
  812.      * If the next entry is going to be too big for the code size,
  813.      * then increase it, if possible.
  814.      */
  815.    if ( free_ent > maxcode || clear_flg ) {
  816.  
  817.             if( clear_flg ) {
  818.  
  819.                 maxcode = MAXCODE (n_bits = g_init_bits);
  820.                 clear_flg = 0;
  821.  
  822.             } else {
  823.  
  824.                 ++n_bits;
  825.                 if ( n_bits == maxbits )
  826.                     maxcode = maxmaxcode;
  827.                 else
  828.                     maxcode = MAXCODE(n_bits);
  829.             }
  830.         }
  831.  
  832.     if( code == EOFCode ) {
  833.         /*
  834.          * At EOF, write the rest of the buffer.
  835.          */
  836.         while( cur_bits > 0 ) {
  837.                 char_out( (unsigned int)(cur_accum & 0xff) );
  838.                 cur_accum >>= 8;
  839.                 cur_bits -= 8;
  840.         }
  841.  
  842.         flush_char();
  843.  
  844.         fflush( g_outfile );
  845.  
  846.         if( ferror( g_outfile ) )
  847.                 writeerr();
  848.     }
  849. }
  850.  
  851. /*
  852.  * Clear out the hash table
  853.  */
  854. static void
  855. cl_block ()             /* table clear for block compress */
  856. {
  857.  
  858.         cl_hash ( (count_int) hsize );
  859.         free_ent = ClearCode + 2;
  860.         clear_flg = 1;
  861.  
  862.         output( (code_int)ClearCode );
  863. }
  864.  
  865. static void
  866. cl_hash(hsize)          /* reset code table */
  867. register count_int hsize;
  868. {
  869.  
  870.         register count_int *htab_p = htab+hsize;
  871.  
  872.         register long i;
  873.         register long m1 = -1;
  874.  
  875.         i = hsize - 16;
  876.         do {                            /* might use Sys V memset(3) here */
  877.                 *(htab_p-16) = m1;
  878.                 *(htab_p-15) = m1;
  879.                 *(htab_p-14) = m1;
  880.                 *(htab_p-13) = m1;
  881.                 *(htab_p-12) = m1;
  882.                 *(htab_p-11) = m1;
  883.                 *(htab_p-10) = m1;
  884.                 *(htab_p-9) = m1;
  885.                 *(htab_p-8) = m1;
  886.                 *(htab_p-7) = m1;
  887.                 *(htab_p-6) = m1;
  888.                 *(htab_p-5) = m1;
  889.                 *(htab_p-4) = m1;
  890.                 *(htab_p-3) = m1;
  891.                 *(htab_p-2) = m1;
  892.                 *(htab_p-1) = m1;
  893.                 htab_p -= 16;
  894.         } while ((i -= 16) >= 0);
  895.  
  896.         for ( i += 16; i > 0; --i )
  897.                 *--htab_p = m1;
  898. }
  899.  
  900. static void
  901. writeerr()
  902. {
  903.         pm_error( "error writing output file" );
  904. }
  905.  
  906. /******************************************************************************
  907.  *
  908.  * GIF Specific routines
  909.  *
  910.  ******************************************************************************/
  911.  
  912. /*
  913.  * Number of characters so far in this 'packet'
  914.  */
  915. static int a_count;
  916.  
  917. /*
  918.  * Set up the 'byte output' routine
  919.  */
  920. static void
  921. char_init()
  922. {
  923.         a_count = 0;
  924. }
  925.  
  926. /*
  927.  * Define the storage for the packet accumulator
  928.  */
  929. static char accum[ 256 ];
  930.  
  931. /*
  932.  * Add a character to the end of the current packet, and if it is 254
  933.  * characters, flush the packet to disk.
  934.  */
  935. static void
  936. char_out( c )
  937. int c;
  938. {
  939.         accum[ a_count++ ] = c;
  940.         if( a_count >= 254 )
  941.                 flush_char();
  942. }
  943.  
  944. /*
  945.  * Flush the packet to disk, and reset the accumulator
  946.  */
  947. static void
  948. flush_char()
  949. {
  950.         if( a_count > 0 ) {
  951.                 fputc( a_count, g_outfile );
  952.                 fwrite( accum, 1, a_count, g_outfile );
  953.                 a_count = 0;
  954.         }
  955. }
  956.  
  957. /* The End */
  958.