Back to index

moin  1.9.0~rc2
GifEncoder.java
Go to the documentation of this file.
00001 // GifEncoder - write out an image as a GIF
00002 // http://www.acme.com/java/software/Acme.JPM.Encoders.GifEncoder.html
00003 //
00004 // Transparency handling and variable bit size courtesy of Jack Palevich.
00005 //
00006 // Copyright (C)1996,1998 by Jef Poskanzer <jef@acme.com>. All rights reserved.
00007 //
00008 // Redistribution and use in source and binary forms, with or without
00009 // modification, are permitted provided that the following conditions
00010 // are met:
00011 // 1. Redistributions of source code must retain the above copyright
00012 //    notice, this list of conditions and the following disclaimer.
00013 // 2. Redistributions in binary form must reproduce the above copyright
00014 //    notice, this list of conditions and the following disclaimer in the
00015 //    documentation and/or other materials provided with the distribution.
00016 //
00017 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
00018 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00019 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00020 // ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
00021 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00022 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00023 // OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00024 // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00025 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00026 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00027 // SUCH DAMAGE.
00028 //
00029 // Visit the ACME Labs Java page for up-to-date versions of this and other
00030 // fine Java utilities: http://www.acme.com/java/
00031 
00032 package Acme.JPM.Encoders;
00033 
00034 import java.util.*;
00035 import java.io.*;
00036 import java.awt.Image;
00037 import java.awt.image.*;
00038 
00040 // <P>
00041 // <A HREF="/resources/classes/Acme/JPM/Encoders/GifEncoder.java">Fetch the software.</A><BR>
00042 // <A HREF="/resources/classes/Acme.tar.gz">Fetch the entire Acme package.</A>
00043 // <P>
00044 // @see ToGif
00045 
00046 public class GifEncoder extends ImageEncoder
00047     {
00048 
00049     private boolean interlace = false;
00050 
00052     // @param img The image to encode.
00053     // @param out The stream to write the GIF to.
00054     public GifEncoder( Image img, OutputStream out ) throws IOException
00055        {
00056        super( img, out );
00057        }
00058 
00060     // @param img The image to encode.
00061     // @param out The stream to write the GIF to.
00062     // @param interlace Whether to interlace.
00063     public GifEncoder( Image img, OutputStream out, boolean interlace ) throws IOException
00064        {
00065        super( img, out );
00066        this.interlace = interlace;
00067        }
00068 
00070     // @param prod The ImageProducer to encode.
00071     // @param out The stream to write the GIF to.
00072     public GifEncoder( ImageProducer prod, OutputStream out ) throws IOException
00073        {
00074        super( prod, out );
00075        }
00076 
00078     // @param prod The ImageProducer to encode.
00079     // @param out The stream to write the GIF to.
00080     public GifEncoder( ImageProducer prod, OutputStream out, boolean interlace ) throws IOException
00081        {
00082        super( prod, out );
00083        this.interlace = interlace;
00084        }
00085 
00086 
00087     int width, height;
00088     int[][] rgbPixels;
00089 
00090     void encodeStart( int width, int height ) throws IOException
00091        {
00092        this.width = width;
00093        this.height = height;
00094        rgbPixels = new int[height][width];
00095        }
00096 
00097     void encodePixels(
00098        int x, int y, int w, int h, int[] rgbPixels, int off, int scansize )
00099        throws IOException
00100        {
00101        // Save the pixels.
00102        for ( int row = 0; row < h; ++row )
00103            System.arraycopy(
00104               rgbPixels, row * scansize + off,
00105               this.rgbPixels[y + row], x, w );
00106 
00107        }
00108 
00109     Acme.IntHashtable colorHash;
00110 
00111     void encodeDone() throws IOException
00112        {
00113        int transparentIndex = -1;
00114        int transparentRgb = -1;
00115         // Put all the pixels into a hash table.
00116         colorHash = new Acme.IntHashtable();
00117        int index = 0;
00118         for ( int row = 0; row < height; ++row )
00119             {
00120             int rowOffset = row * width;
00121             for ( int col = 0; col < width; ++col )
00122                 {
00123                 int rgb = rgbPixels[row][col];
00124               boolean isTransparent = ( ( rgb >>> 24 ) < 0x80 );
00125               if ( isTransparent )
00126                   {
00127                   if ( transparentIndex < 0 )
00128                      {
00129                      // First transparent color; remember it.
00130                      transparentIndex = index;
00131                      transparentRgb = rgb;
00132                      }
00133                   else if ( rgb != transparentRgb )
00134                      {
00135                      // A second transparent color; replace it with
00136                      // the first one.
00137                      rgbPixels[row][col] = rgb = transparentRgb;
00138                      }
00139                   }
00140                 GifEncoderHashitem item =
00141                   (GifEncoderHashitem) colorHash.get( rgb );
00142                 if ( item == null )
00143                   {
00144                   if ( index >= 256 )
00145                      throw new IOException( "too many colors for a GIF" );
00146                     item = new GifEncoderHashitem(
00147                      rgb, 1, index, isTransparent );
00148                   ++index;
00149                   colorHash.put( rgb, item );
00150                   }
00151                 else
00152                     ++item.count;
00153                 }
00154             }
00155 
00156        // Figure out how many bits to use.
00157        int logColors;
00158        if ( index <= 2 )
00159            logColors = 1;
00160        else if ( index <= 4 )
00161            logColors = 2;
00162        else if ( index <= 16 )
00163            logColors = 4;
00164        else
00165            logColors = 8;
00166 
00167        // Turn colors into colormap entries.
00168        int mapSize = 1 << logColors;
00169        byte[] reds = new byte[mapSize];
00170        byte[] grns = new byte[mapSize];
00171        byte[] blus = new byte[mapSize];
00172        for ( Enumeration e = colorHash.elements(); e.hasMoreElements(); )
00173            {
00174            GifEncoderHashitem item = (GifEncoderHashitem) e.nextElement();
00175            reds[item.index] = (byte) ( ( item.rgb >> 16 ) & 0xff );
00176            grns[item.index] = (byte) ( ( item.rgb >>  8 ) & 0xff );
00177            blus[item.index] = (byte) (   item.rgb         & 0xff );
00178            }
00179 
00180        GIFEncode(
00181            out, width, height, interlace, (byte) 0, transparentIndex,
00182            logColors, reds, grns, blus );
00183        }
00184 
00185     byte GetPixel( int x, int y ) throws IOException
00186        {
00187        GifEncoderHashitem item =
00188            (GifEncoderHashitem) colorHash.get( rgbPixels[y][x] );
00189        if ( item == null )
00190            throw new IOException( "color not found" );
00191        return (byte) item.index;
00192        }
00193 
00194     static void writeString( OutputStream out, String str ) throws IOException
00195         {
00196         byte[] buf = str.getBytes();
00197         out.write( buf );
00198         }
00199 
00200     // Adapted from ppmtogif, which is based on GIFENCOD by David
00201     // Rowley <mgardi@watdscu.waterloo.edu>.  Lempel-Zim compression
00202     // based on "compress".
00203 
00204     int Width, Height;
00205     boolean Interlace;
00206     int curx, cury;
00207     int CountDown;
00208     int Pass = 0;
00209 
00210     void GIFEncode(
00211        OutputStream outs, int Width, int Height, boolean Interlace, byte Background, int Transparent, int BitsPerPixel, byte[] Red, byte[] Green, byte[] Blue )
00212        throws IOException
00213        {
00214        byte B;
00215        int LeftOfs, TopOfs;
00216        int ColorMapSize;
00217        int InitCodeSize;
00218        int i;
00219 
00220        this.Width = Width;
00221        this.Height = Height;
00222        this.Interlace = Interlace;
00223        ColorMapSize = 1 << BitsPerPixel;
00224        LeftOfs = TopOfs = 0;
00225 
00226        // Calculate number of bits we are expecting
00227        CountDown = Width * Height;
00228 
00229        // Indicate which pass we are on (if interlace)
00230        Pass = 0;
00231 
00232        // The initial code size
00233        if ( BitsPerPixel <= 1 )
00234            InitCodeSize = 2;
00235        else
00236            InitCodeSize = BitsPerPixel;
00237 
00238        // Set up the current x and y position
00239        curx = 0;
00240        cury = 0;
00241 
00242        // Write the Magic header
00243        writeString( outs, "GIF89a" );
00244 
00245        // Write out the screen width and height
00246        Putword( Width, outs );
00247        Putword( Height, outs );
00248 
00249        // Indicate that there is a global colour map
00250        B = (byte) 0x80;            // Yes, there is a color map
00251        // OR in the resolution
00252        B |= (byte) ( ( 8 - 1 ) << 4 );
00253        // Not sorted
00254        // OR in the Bits per Pixel
00255        B |= (byte) ( ( BitsPerPixel - 1 ) );
00256 
00257        // Write it out
00258        Putbyte( B, outs );
00259 
00260        // Write out the Background colour
00261        Putbyte( Background, outs );
00262 
00263        // Pixel aspect ratio - 1:1.
00264        //Putbyte( (byte) 49, outs );
00265        // Java's GIF reader currently has a bug, if the aspect ratio byte is
00266        // not zero it throws an ImageFormatException.  It doesn't know that
00267        // 49 means a 1:1 aspect ratio.  Well, whatever, zero works with all
00268        // the other decoders I've tried so it probably doesn't hurt.
00269        Putbyte( (byte) 0, outs );
00270 
00271        // Write out the Global Colour Map
00272        for ( i = 0; i < ColorMapSize; ++i )
00273            {
00274            Putbyte( Red[i], outs );
00275            Putbyte( Green[i], outs );
00276            Putbyte( Blue[i], outs );
00277            }
00278 
00279        // Write out extension for transparent colour index, if necessary.
00280        if ( Transparent != -1 )
00281            {
00282            Putbyte( (byte) '!', outs );
00283            Putbyte( (byte) 0xf9, outs );
00284            Putbyte( (byte) 4, outs );
00285            Putbyte( (byte) 1, outs );
00286            Putbyte( (byte) 0, outs );
00287            Putbyte( (byte) 0, outs );
00288            Putbyte( (byte) Transparent, outs );
00289            Putbyte( (byte) 0, outs );
00290            }
00291 
00292        // Write an Image separator
00293        Putbyte( (byte) ',', outs );
00294 
00295        // Write the Image header
00296        Putword( LeftOfs, outs );
00297        Putword( TopOfs, outs );
00298        Putword( Width, outs );
00299        Putword( Height, outs );
00300 
00301        // Write out whether or not the image is interlaced
00302        if ( Interlace )
00303            Putbyte( (byte) 0x40, outs );
00304        else
00305            Putbyte( (byte) 0x00, outs );
00306 
00307        // Write out the initial code size
00308        Putbyte( (byte) InitCodeSize, outs );
00309 
00310        // Go and actually compress the data
00311        compress( InitCodeSize+1, outs );
00312 
00313        // Write out a Zero-length packet (to end the series)
00314        Putbyte( (byte) 0, outs );
00315 
00316        // Write the GIF file terminator
00317        Putbyte( (byte) ';', outs );
00318        }
00319 
00320     // Bump the 'curx' and 'cury' to point to the next pixel
00321     void BumpPixel()
00322        {
00323        // Bump the current X position
00324        ++curx;
00325 
00326        // If we are at the end of a scan line, set curx back to the beginning
00327        // If we are interlaced, bump the cury to the appropriate spot,
00328        // otherwise, just increment it.
00329        if ( curx == Width )
00330            {
00331            curx = 0;
00332 
00333            if ( ! Interlace )
00334               ++cury;
00335            else
00336               {
00337               switch( Pass )
00338                   {
00339                   case 0:
00340                   cury += 8;
00341                   if ( cury >= Height )
00342                      {
00343                      ++Pass;
00344                      cury = 4;
00345                      }
00346                   break;
00347 
00348                   case 1:
00349                   cury += 8;
00350                   if ( cury >= Height )
00351                      {
00352                      ++Pass;
00353                      cury = 2;
00354                      }
00355                   break;
00356 
00357                   case 2:
00358                   cury += 4;
00359                   if ( cury >= Height )
00360                      {
00361                      ++Pass;
00362                      cury = 1;
00363                      }
00364                   break;
00365 
00366                   case 3:
00367                   cury += 2;
00368                   break;
00369                   }
00370               }
00371            }
00372        }
00373 
00374     static final int EOF = -1;
00375 
00376     // Return the next pixel from the image
00377     int GIFNextPixel() throws IOException
00378        {
00379        byte r;
00380 
00381        if ( CountDown == 0 )
00382            return EOF;
00383 
00384        --CountDown;
00385 
00386        r = GetPixel( curx, cury );
00387 
00388        BumpPixel();
00389 
00390        return r & 0xff;
00391        }
00392 
00393     // Write out a word to the GIF file
00394     void Putword( int w, OutputStream outs ) throws IOException
00395        {
00396        Putbyte( (byte) ( w & 0xff ), outs );
00397        Putbyte( (byte) ( ( w >> 8 ) & 0xff ), outs );
00398        }
00399 
00400     // Write out a byte to the GIF file
00401     void Putbyte( byte b, OutputStream outs ) throws IOException
00402        {
00403        outs.write( b );
00404        }
00405 
00406 
00407     // GIFCOMPR.C       - GIF Image compression routines
00408     //
00409     // Lempel-Ziv compression based on 'compress'.  GIF modifications by
00410     // David Rowley (mgardi@watdcsu.waterloo.edu)
00411 
00412     // General DEFINEs
00413 
00414     static final int BITS = 12;
00415 
00416     static final int HSIZE = 5003;        // 80% occupancy
00417 
00418     // GIF Image compression - modified 'compress'
00419     //
00420     // Based on: compress.c - File compression ala IEEE Computer, June 1984.
00421     //
00422     // By Authors:  Spencer W. Thomas      (decvax!harpo!utah-cs!utah-gr!thomas)
00423     //              Jim McKie              (decvax!mcvax!jim)
00424     //              Steve Davies           (decvax!vax135!petsd!peora!srd)
00425     //              Ken Turkowski          (decvax!decwrl!turtlevax!ken)
00426     //              James A. Woods         (decvax!ihnp4!ames!jaw)
00427     //              Joe Orost              (decvax!vax135!petsd!joe)
00428 
00429     int n_bits;                           // number of bits/code
00430     int maxbits = BITS;                   // user settable max # bits/code
00431     int maxcode;                   // maximum code, given n_bits
00432     int maxmaxcode = 1 << BITS; // should NEVER generate this code
00433 
00434     final int MAXCODE( int n_bits )
00435        {
00436        return ( 1 << n_bits ) - 1;
00437        }
00438 
00439     int[] htab = new int[HSIZE];
00440     int[] codetab = new int[HSIZE];
00441 
00442     int hsize = HSIZE;             // for dynamic table sizing
00443 
00444     int free_ent = 0;                     // first unused entry
00445 
00446     // block compression parameters -- after all codes are used up,
00447     // and compression rate changes, start over.
00448     boolean clear_flg = false;
00449 
00450     // Algorithm:  use open addressing double hashing (no chaining) on the
00451     // prefix code / next character combination.  We do a variant of Knuth's
00452     // algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
00453     // secondary probe.  Here, the modular division first probe is gives way
00454     // to a faster exclusive-or manipulation.  Also do block compression with
00455     // an adaptive reset, whereby the code table is cleared when the compression
00456     // ratio decreases, but after the table fills.  The variable-length output
00457     // codes are re-sized at this point, and a special CLEAR code is generated
00458     // for the decompressor.  Late addition:  construct the table according to
00459     // file size for noticeable speed improvement on small files.  Please direct
00460     // questions about this implementation to ames!jaw.
00461 
00462     int g_init_bits;
00463 
00464     int ClearCode;
00465     int EOFCode;
00466 
00467     void compress( int init_bits, OutputStream outs ) throws IOException
00468        {
00469        int fcode;
00470        int i /* = 0 */;
00471        int c;
00472        int ent;
00473        int disp;
00474        int hsize_reg;
00475        int hshift;
00476 
00477        // Set up the globals:  g_init_bits - initial number of bits
00478        g_init_bits = init_bits;
00479 
00480        // Set up the necessary values
00481        clear_flg = false;
00482        n_bits = g_init_bits;
00483        maxcode = MAXCODE( n_bits );
00484 
00485        ClearCode = 1 << ( init_bits - 1 );
00486        EOFCode = ClearCode + 1;
00487        free_ent = ClearCode + 2;
00488 
00489        char_init();
00490 
00491        ent = GIFNextPixel();
00492 
00493        hshift = 0;
00494        for ( fcode = hsize; fcode < 65536; fcode *= 2 )
00495            ++hshift;
00496        hshift = 8 - hshift;               // set hash code range bound
00497 
00498        hsize_reg = hsize;
00499        cl_hash( hsize_reg );       // clear hash table
00500 
00501        output( ClearCode, outs );
00502 
00503        outer_loop:
00504        while ( (c = GIFNextPixel()) != EOF )
00505            {
00506            fcode = ( c << maxbits ) + ent;
00507            i = ( c << hshift ) ^ ent;            // xor hashing
00508 
00509            if ( htab[i] == fcode )
00510               {
00511               ent = codetab[i];
00512               continue;
00513               }
00514            else if ( htab[i] >= 0 )       // non-empty slot
00515               {
00516               disp = hsize_reg - i;       // secondary hash (after G. Knott)
00517               if ( i == 0 )
00518                   disp = 1;
00519               do
00520                   {
00521                   if ( (i -= disp) < 0 )
00522                      i += hsize_reg;
00523 
00524                   if ( htab[i] == fcode )
00525                      {
00526                      ent = codetab[i];
00527                      continue outer_loop;
00528                      }
00529                   }
00530               while ( htab[i] >= 0 );
00531               }
00532            output( ent, outs );
00533            ent = c;
00534            if ( free_ent < maxmaxcode )
00535               {
00536               codetab[i] = free_ent++;    // code -> hashtable
00537               htab[i] = fcode;
00538               }
00539            else
00540               cl_block( outs );
00541            }
00542        // Put out the final code.
00543        output( ent, outs );
00544        output( EOFCode, outs );
00545        }
00546 
00547     // output
00548     //
00549     // Output the given code.
00550     // Inputs:
00551     //      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
00552     //              that n_bits =< wordsize - 1.
00553     // Outputs:
00554     //      Outputs code to the file.
00555     // Assumptions:
00556     //      Chars are 8 bits long.
00557     // Algorithm:
00558     //      Maintain a BITS character long buffer (so that 8 codes will
00559     // fit in it exactly).  Use the VAX insv instruction to insert each
00560     // code in turn.  When the buffer fills up empty it and start over.
00561 
00562     int cur_accum = 0;
00563     int cur_bits = 0;
00564 
00565     int masks[] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000F,
00566                   0x001F, 0x003F, 0x007F, 0x00FF,
00567                   0x01FF, 0x03FF, 0x07FF, 0x0FFF,
00568                   0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
00569 
00570     void output( int code, OutputStream outs ) throws IOException
00571        {
00572        cur_accum &= masks[cur_bits];
00573 
00574        if ( cur_bits > 0 )
00575            cur_accum |= ( code << cur_bits );
00576        else
00577            cur_accum = code;
00578 
00579        cur_bits += n_bits;
00580 
00581        while ( cur_bits >= 8 )
00582            {
00583            char_out( (byte) ( cur_accum & 0xff ), outs );
00584            cur_accum >>= 8;
00585            cur_bits -= 8;
00586            }
00587 
00588        // If the next entry is going to be too big for the code size,
00589        // then increase it, if possible.
00590        if ( free_ent > maxcode || clear_flg )
00591            {
00592            if ( clear_flg )
00593               {
00594               maxcode = MAXCODE(n_bits = g_init_bits);
00595               clear_flg = false;
00596               }
00597            else
00598               {
00599               ++n_bits;
00600               if ( n_bits == maxbits )
00601                   maxcode = maxmaxcode;
00602               else
00603                   maxcode = MAXCODE(n_bits);
00604               }
00605            }
00606 
00607        if ( code == EOFCode )
00608            {
00609            // At EOF, write the rest of the buffer.
00610            while ( cur_bits > 0 )
00611               {
00612               char_out( (byte) ( cur_accum & 0xff ), outs );
00613               cur_accum >>= 8;
00614               cur_bits -= 8;
00615               }
00616 
00617            flush_char( outs );
00618            }
00619        }
00620 
00621     // Clear out the hash table
00622 
00623     // table clear for block compress
00624     void cl_block( OutputStream outs ) throws IOException
00625        {
00626        cl_hash( hsize );
00627        free_ent = ClearCode + 2;
00628        clear_flg = true;
00629 
00630        output( ClearCode, outs );
00631        }
00632 
00633     // reset code table
00634     void cl_hash( int hsize )
00635        {
00636        for ( int i = 0; i < hsize; ++i )
00637            htab[i] = -1;
00638        }
00639 
00640     // GIF Specific routines
00641 
00642     // Number of characters so far in this 'packet'
00643     int a_count;
00644 
00645     // Set up the 'byte output' routine
00646     void char_init()
00647        {
00648        a_count = 0;
00649        }
00650 
00651     // Define the storage for the packet accumulator
00652     byte[] accum = new byte[256];
00653 
00654     // Add a character to the end of the current packet, and if it is 254
00655     // characters, flush the packet to disk.
00656     void char_out( byte c, OutputStream outs ) throws IOException
00657        {
00658        accum[a_count++] = c;
00659        if ( a_count >= 254 )
00660            flush_char( outs );
00661        }
00662 
00663     // Flush the packet to disk, and reset the accumulator
00664     void flush_char( OutputStream outs ) throws IOException
00665        {
00666        if ( a_count > 0 )
00667            {
00668            outs.write( a_count );
00669            outs.write( accum, 0, a_count );
00670            a_count = 0;
00671            }
00672        }
00673 
00674     }
00675 
00676 class GifEncoderHashitem
00677     {
00678 
00679     public int rgb;
00680     public int count;
00681     public int index;
00682     public boolean isTransparent;
00683 
00684     public GifEncoderHashitem( int rgb, int count, int index, boolean isTransparent )
00685        {
00686        this.rgb = rgb;
00687        this.count = count;
00688        this.index = index;
00689        this.isTransparent = isTransparent;
00690        }
00691 
00692     }