0001: // ImageEncoder - abstract class for writing out an image
0002: // http://www.acme.com/java/software/Acme.JPM.Encoders.ImageEncoder.html
0003: //
0004: // Copyright (C) 1996 by Jef Poskanzer <jef@acme.com>. All rights reserved.
0005: //
0006: // Redistribution and use in source and binary forms, with or without
0007: // modification, are permitted provided that the following conditions
0008: // are met:
0009: // 1. Redistributions of source code must retain the above copyright
0010: // notice, this list of conditions and the following disclaimer.
0011: // 2. Redistributions in binary form must reproduce the above copyright
0012: // notice, this list of conditions and the following disclaimer in the
0013: // documentation and/or other materials provided with the distribution.
0014: //
0015: // THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
0016: // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
0017: // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
0018: // ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
0019: // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
0020: // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
0021: // OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
0022: // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
0023: // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
0024: // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
0025: // SUCH DAMAGE.
0026: //
0027: // Visit the ACME Labs Java page for up-to-date versions of this and other
0028: // fine Java utilities: http://www.acme.com/java/
0029:
0030: package com.jgraph.pad.util;
0031:
0032: import java.awt.Image;
0033: import java.awt.image.ColorModel;
0034: import java.awt.image.ImageConsumer;
0035: import java.awt.image.ImageProducer;
0036: import java.io.IOException;
0037: import java.io.OutputStream;
0038: import java.util.Dictionary;
0039: import java.util.Enumeration;
0040: import java.util.Hashtable;
0041: import java.util.NoSuchElementException;
0042:
0043: /// Abstract class for writing out an image.
0044: // <P>
0045: // A framework for classes that encode and write out an image in
0046: // a particular file format.
0047: // <P>
0048: // This provides a simplified rendition of the ImageConsumer interface.
0049: // It always delivers the pixels as ints in the RGBdefault color model.
0050: // It always provides them in top-down left-right order.
0051: // If you want more flexibility you can always implement ImageConsumer
0052: // directly.
0053: // <P>
0054: // <A HREF="/resources/classes/Acme/JPM/Encoders/ImageEncoder.java">Fetch the software.</A><BR>
0055: // <A HREF="/resources/classes/Acme.tar.gz">Fetch the entire Acme package.</A>
0056: // <P>
0057: // @see GifEncoder
0058: // @see PpmEncoder
0059: // @see Acme.JPM.Decoders.ImageDecoder
0060:
0061: public abstract class JGraphpadImageEncoder implements ImageConsumer {
0062:
0063: protected OutputStream out;
0064:
0065: private ImageProducer producer;
0066:
0067: private int width = -1;
0068:
0069: private int height = -1;
0070:
0071: private int hintflags = 0;
0072:
0073: private boolean started = false;
0074:
0075: private boolean encoding;
0076:
0077: private IOException iox;
0078:
0079: private static final ColorModel rgbModel = ColorModel
0080: .getRGBdefault();
0081:
0082: private Hashtable props = null;
0083:
0084: // / Constructor.
0085: // @param img The image to encode.
0086: // @param out The stream to write the bytes to.
0087: public JGraphpadImageEncoder(Image img, OutputStream out)
0088: throws IOException {
0089: this (img.getSource(), out);
0090: }
0091:
0092: // / Constructor.
0093: // @param producer The ImageProducer to encode.
0094: // @param out The stream to write the bytes to.
0095: public JGraphpadImageEncoder(ImageProducer producer,
0096: OutputStream out) throws IOException {
0097: this .producer = producer;
0098: this .out = out;
0099: }
0100:
0101: /**
0102: * Public GIF Encoding method. Use this method for GIF encoding in JGraph
0103: * editors.
0104: *
0105: * @throws IOException
0106: */
0107: public static void writeGIF(Image image, OutputStream out)
0108: throws IOException {
0109: new GifEncoder(image, out).encode();
0110: }
0111:
0112: // Methods that subclasses implement.
0113:
0114: // / Subclasses implement this to initialize an encoding.
0115: abstract void encodeStart(int w, int h) throws IOException;
0116:
0117: // / Subclasses implement this to actually write out some bits. They
0118: // are guaranteed to be delivered in top-down-left-right order.
0119: // One int per pixel, index is row * scansize + off + col,
0120: // RGBdefault (AARRGGBB) color model.
0121: abstract void encodePixels(int x, int y, int w, int h,
0122: int[] rgbPixels, int off, int scansize) throws IOException;
0123:
0124: // / Subclasses implement this to finish an encoding.
0125: abstract void encodeDone() throws IOException;
0126:
0127: // Our own methods.
0128:
0129: // / Call this after initialization to get things going.
0130: public synchronized void encode() throws IOException {
0131: encoding = true;
0132: iox = null;
0133: producer.startProduction(this );
0134: while (encoding)
0135: try {
0136: wait();
0137: } catch (InterruptedException e) {
0138: }
0139: if (iox != null)
0140: throw iox;
0141: }
0142:
0143: private boolean accumulate = false;
0144:
0145: private int[] accumulator;
0146:
0147: private void encodePixelsWrapper(int x, int y, int w, int h,
0148: int[] rgbPixels, int off, int scansize) throws IOException {
0149: if (!started) {
0150: started = true;
0151: encodeStart(width, height);
0152: if ((hintflags & TOPDOWNLEFTRIGHT) == 0) {
0153: accumulate = true;
0154: accumulator = new int[width * height];
0155: }
0156: }
0157: if (accumulate)
0158: for (int row = 0; row < h; ++row)
0159: System.arraycopy(rgbPixels, row * scansize + off,
0160: accumulator, (y + row) * width + x, w);
0161: else
0162: encodePixels(x, y, w, h, rgbPixels, off, scansize);
0163: }
0164:
0165: private void encodeFinish() throws IOException {
0166: if (accumulate) {
0167: encodePixels(0, 0, width, height, accumulator, 0, width);
0168: accumulator = null;
0169: accumulate = false;
0170: }
0171: }
0172:
0173: private synchronized void stop() {
0174: encoding = false;
0175: notifyAll();
0176: }
0177:
0178: // Methods from ImageConsumer.
0179:
0180: public void setDimensions(int width, int height) {
0181: this .width = width;
0182: this .height = height;
0183: }
0184:
0185: public void setProperties(Hashtable props) {
0186: this .props = props;
0187: }
0188:
0189: public void setColorModel(ColorModel model) {
0190: // Ignore.
0191: }
0192:
0193: public void setHints(int hintflags) {
0194: this .hintflags = hintflags;
0195: }
0196:
0197: public void setPixels(int x, int y, int w, int h, ColorModel model,
0198: byte[] pixels, int off, int scansize) {
0199: int[] rgbPixels = new int[w];
0200: for (int row = 0; row < h; ++row) {
0201: int rowOff = off + row * scansize;
0202: for (int col = 0; col < w; ++col)
0203: rgbPixels[col] = model
0204: .getRGB(pixels[rowOff + col] & 0xff);
0205: try {
0206: encodePixelsWrapper(x, y + row, w, 1, rgbPixels, 0, w);
0207: } catch (IOException e) {
0208: iox = e;
0209: stop();
0210: return;
0211: }
0212: }
0213: }
0214:
0215: public void setPixels(int x, int y, int w, int h, ColorModel model,
0216: int[] pixels, int off, int scansize) {
0217: if (model == rgbModel) {
0218: try {
0219: encodePixelsWrapper(x, y, w, h, pixels, off, scansize);
0220: } catch (IOException e) {
0221: iox = e;
0222: stop();
0223: return;
0224: }
0225: } else {
0226: int[] rgbPixels = new int[w];
0227: for (int row = 0; row < h; ++row) {
0228: int rowOff = off + row * scansize;
0229: for (int col = 0; col < w; ++col)
0230: rgbPixels[col] = model.getRGB(pixels[rowOff + col]);
0231: try {
0232: encodePixelsWrapper(x, y + row, w, 1, rgbPixels, 0,
0233: w);
0234: } catch (IOException e) {
0235: iox = e;
0236: stop();
0237: return;
0238: }
0239: }
0240: }
0241: }
0242:
0243: public void imageComplete(int status) {
0244: producer.removeConsumer(this );
0245: if (status == ImageConsumer.IMAGEABORTED)
0246: iox = new IOException("image aborted");
0247: else {
0248: try {
0249: encodeFinish();
0250: encodeDone();
0251: } catch (IOException e) {
0252: iox = e;
0253: }
0254: }
0255: stop();
0256: }
0257:
0258: public static class GifEncoder extends JGraphpadImageEncoder {
0259:
0260: private boolean interlace = false;
0261:
0262: // / Constructor from Image.
0263: // @param img The image to encode.
0264: // @param out The stream to write the GIF to.
0265: public GifEncoder(Image img, OutputStream out)
0266: throws IOException {
0267: super (img, out);
0268: }
0269:
0270: // / Constructor from Image with interlace setting.
0271: // @param img The image to encode.
0272: // @param out The stream to write the GIF to.
0273: // @param interlace Whether to interlace.
0274: public GifEncoder(Image img, OutputStream out, boolean interlace)
0275: throws IOException {
0276: super (img, out);
0277: this .interlace = interlace;
0278: }
0279:
0280: // / Constructor from ImageProducer.
0281: // @param prod The ImageProducer to encode.
0282: // @param out The stream to write the GIF to.
0283: public GifEncoder(ImageProducer prod, OutputStream out)
0284: throws IOException {
0285: super (prod, out);
0286: }
0287:
0288: // / Constructor from ImageProducer with interlace setting.
0289: // @param prod The ImageProducer to encode.
0290: // @param out The stream to write the GIF to.
0291: public GifEncoder(ImageProducer prod, OutputStream out,
0292: boolean interlace) throws IOException {
0293: super (prod, out);
0294: this .interlace = interlace;
0295: }
0296:
0297: int width, height;
0298:
0299: int[][] rgbPixels;
0300:
0301: void encodeStart(int width, int height) throws IOException {
0302: this .width = width;
0303: this .height = height;
0304: rgbPixels = new int[height][width];
0305: }
0306:
0307: void encodePixels(int x, int y, int w, int h, int[] rgbPixels,
0308: int off, int scansize) throws IOException {
0309: // Save the pixels.
0310: for (int row = 0; row < h; ++row)
0311: System.arraycopy(rgbPixels, row * scansize + off,
0312: this .rgbPixels[y + row], x, w);
0313:
0314: }
0315:
0316: IntHashtable colorHash;
0317:
0318: void encodeDone() throws IOException {
0319: int transparentIndex = -1;
0320: int transparentRgb = -1;
0321: // Put all the pixels into a hash table.
0322: colorHash = new IntHashtable();
0323: int index = 0;
0324: for (int row = 0; row < height; ++row) {
0325: for (int col = 0; col < width; ++col) {
0326: int rgb = rgbPixels[row][col];
0327: boolean isTransparent = ((rgb >>> 24) < 0x80);
0328: if (isTransparent) {
0329: if (transparentIndex < 0) {
0330: // First transparent color; remember it.
0331: transparentIndex = index;
0332: transparentRgb = rgb;
0333: } else if (rgb != transparentRgb) {
0334: // A second transparent color; replace it with
0335: // the first one.
0336: rgbPixels[row][col] = rgb = transparentRgb;
0337: }
0338: }
0339: GifEncoderHashitem item = (GifEncoderHashitem) colorHash
0340: .get(rgb);
0341: if (item == null) {
0342: if (index >= 256)
0343: throw new IOException(
0344: "too many colors for a GIF");
0345: item = new GifEncoderHashitem(rgb, 1, index,
0346: isTransparent);
0347: ++index;
0348: colorHash.put(rgb, item);
0349: } else
0350: ++item.count;
0351: }
0352: }
0353:
0354: // Figure out how many bits to use.
0355: int logColors;
0356: if (index <= 2)
0357: logColors = 1;
0358: else if (index <= 4)
0359: logColors = 2;
0360: else if (index <= 16)
0361: logColors = 4;
0362: else
0363: logColors = 8;
0364:
0365: // Turn colors into colormap entries.
0366: int mapSize = 1 << logColors;
0367: byte[] reds = new byte[mapSize];
0368: byte[] grns = new byte[mapSize];
0369: byte[] blus = new byte[mapSize];
0370: for (Enumeration e = colorHash.elements(); e
0371: .hasMoreElements();) {
0372: GifEncoderHashitem item = (GifEncoderHashitem) e
0373: .nextElement();
0374: reds[item.index] = (byte) ((item.rgb >> 16) & 0xff);
0375: grns[item.index] = (byte) ((item.rgb >> 8) & 0xff);
0376: blus[item.index] = (byte) (item.rgb & 0xff);
0377: }
0378:
0379: GIFEncode(out, width, height, interlace, (byte) 0,
0380: transparentIndex, logColors, reds, grns, blus);
0381: }
0382:
0383: byte GetPixel(int x, int y) throws IOException {
0384: GifEncoderHashitem item = (GifEncoderHashitem) colorHash
0385: .get(rgbPixels[y][x]);
0386: if (item == null)
0387: throw new IOException("color not found");
0388: return (byte) item.index;
0389: }
0390:
0391: static void writeString(OutputStream out, String str)
0392: throws IOException {
0393: byte[] buf = str.getBytes();
0394: out.write(buf);
0395: }
0396:
0397: // Adapted from ppmtogif, which is based on GIFENCOD by David
0398: // Rowley <mgardi@watdscu.waterloo.edu>. Lempel-Zim compression
0399: // based on "compress".
0400:
0401: int Width, Height;
0402:
0403: boolean Interlace;
0404:
0405: int curx, cury;
0406:
0407: int CountDown;
0408:
0409: int Pass = 0;
0410:
0411: void GIFEncode(OutputStream outs, int Width, int Height,
0412: boolean Interlace, byte Background, int Transparent,
0413: int BitsPerPixel, byte[] Red, byte[] Green, byte[] Blue)
0414: throws IOException {
0415: byte B;
0416: int LeftOfs, TopOfs;
0417: int ColorMapSize;
0418: int InitCodeSize;
0419: int i;
0420:
0421: this .Width = Width;
0422: this .Height = Height;
0423: this .Interlace = Interlace;
0424: ColorMapSize = 1 << BitsPerPixel;
0425: LeftOfs = TopOfs = 0;
0426:
0427: // Calculate number of bits we are expecting
0428: CountDown = Width * Height;
0429:
0430: // Indicate which pass we are on (if interlace)
0431: Pass = 0;
0432:
0433: // The initial code size
0434: if (BitsPerPixel <= 1)
0435: InitCodeSize = 2;
0436: else
0437: InitCodeSize = BitsPerPixel;
0438:
0439: // Set up the current x and y position
0440: curx = 0;
0441: cury = 0;
0442:
0443: // Write the Magic header
0444: writeString(outs, "GIF89a");
0445:
0446: // Write out the screen width and height
0447: Putword(Width, outs);
0448: Putword(Height, outs);
0449:
0450: // Indicate that there is a global colour map
0451: B = (byte) 0x80; // Yes, there is a color map
0452: // OR in the resolution
0453: B |= (byte) ((8 - 1) << 4);
0454: // Not sorted
0455: // OR in the Bits per Pixel
0456: B |= (byte) ((BitsPerPixel - 1));
0457:
0458: // Write it out
0459: Putbyte(B, outs);
0460:
0461: // Write out the Background colour
0462: Putbyte(Background, outs);
0463:
0464: // Pixel aspect ratio - 1:1.
0465: // Putbyte( (byte) 49, outs );
0466: // Java's GIF reader currently has a bug, if the aspect ratio byte
0467: // is
0468: // not zero it throws an ImageFormatException. It doesn't know that
0469: // 49 means a 1:1 aspect ratio. Well, whatever, zero works with all
0470: // the other decoders I've tried so it probably doesn't hurt.
0471: Putbyte((byte) 0, outs);
0472:
0473: // Write out the Global Colour Map
0474: for (i = 0; i < ColorMapSize; ++i) {
0475: Putbyte(Red[i], outs);
0476: Putbyte(Green[i], outs);
0477: Putbyte(Blue[i], outs);
0478: }
0479:
0480: // Write out extension for transparent colour index, if necessary.
0481: if (Transparent != -1) {
0482: Putbyte((byte) '!', outs);
0483: Putbyte((byte) 0xf9, outs);
0484: Putbyte((byte) 4, outs);
0485: Putbyte((byte) 1, outs);
0486: Putbyte((byte) 0, outs);
0487: Putbyte((byte) 0, outs);
0488: Putbyte((byte) Transparent, outs);
0489: Putbyte((byte) 0, outs);
0490: }
0491:
0492: // Write an Image separator
0493: Putbyte((byte) ',', outs);
0494:
0495: // Write the Image header
0496: Putword(LeftOfs, outs);
0497: Putword(TopOfs, outs);
0498: Putword(Width, outs);
0499: Putword(Height, outs);
0500:
0501: // Write out whether or not the image is interlaced
0502: if (Interlace)
0503: Putbyte((byte) 0x40, outs);
0504: else
0505: Putbyte((byte) 0x00, outs);
0506:
0507: // Write out the initial code size
0508: Putbyte((byte) InitCodeSize, outs);
0509:
0510: // Go and actually compress the data
0511: compress(InitCodeSize + 1, outs);
0512:
0513: // Write out a Zero-length packet (to end the series)
0514: Putbyte((byte) 0, outs);
0515:
0516: // Write the GIF file terminator
0517: Putbyte((byte) ';', outs);
0518: }
0519:
0520: // Bump the 'curx' and 'cury' to point to the next pixel
0521: void BumpPixel() {
0522: // Bump the current X position
0523: ++curx;
0524:
0525: // If we are at the end of a scan line, set curx back to the
0526: // beginning
0527: // If we are interlaced, bump the cury to the appropriate spot,
0528: // otherwise, just increment it.
0529: if (curx == Width) {
0530: curx = 0;
0531:
0532: if (!Interlace)
0533: ++cury;
0534: else {
0535: switch (Pass) {
0536: case 0:
0537: cury += 8;
0538: if (cury >= Height) {
0539: ++Pass;
0540: cury = 4;
0541: }
0542: break;
0543:
0544: case 1:
0545: cury += 8;
0546: if (cury >= Height) {
0547: ++Pass;
0548: cury = 2;
0549: }
0550: break;
0551:
0552: case 2:
0553: cury += 4;
0554: if (cury >= Height) {
0555: ++Pass;
0556: cury = 1;
0557: }
0558: break;
0559:
0560: case 3:
0561: cury += 2;
0562: break;
0563: }
0564: }
0565: }
0566: }
0567:
0568: static final int EOF = -1;
0569:
0570: // Return the next pixel from the image
0571: int GIFNextPixel() throws IOException {
0572: byte r;
0573:
0574: if (CountDown == 0)
0575: return EOF;
0576:
0577: --CountDown;
0578:
0579: r = GetPixel(curx, cury);
0580:
0581: BumpPixel();
0582:
0583: return r & 0xff;
0584: }
0585:
0586: // Write out a word to the GIF file
0587: void Putword(int w, OutputStream outs) throws IOException {
0588: Putbyte((byte) (w & 0xff), outs);
0589: Putbyte((byte) ((w >> 8) & 0xff), outs);
0590: }
0591:
0592: // Write out a byte to the GIF file
0593: void Putbyte(byte b, OutputStream outs) throws IOException {
0594: outs.write(b);
0595: }
0596:
0597: // GIFCOMPR.C - GIF Image compression routines
0598: //
0599: // Lempel-Ziv compression based on 'compress'. GIF modifications by
0600: // David Rowley (mgardi@watdcsu.waterloo.edu)
0601:
0602: // General DEFINEs
0603:
0604: static final int BITS = 12;
0605:
0606: static final int HSIZE = 5003; // 80% occupancy
0607:
0608: // GIF Image compression - modified 'compress'
0609: //
0610: // Based on: compress.c - File compression ala IEEE Computer, June 1984.
0611: //
0612: // By Authors: Spencer W. Thomas (decvax!harpo!utah-cs!utah-gr!thomas)
0613: // Jim McKie (decvax!mcvax!jim)
0614: // Steve Davies (decvax!vax135!petsd!peora!srd)
0615: // Ken Turkowski (decvax!decwrl!turtlevax!ken)
0616: // James A. Woods (decvax!ihnp4!ames!jaw)
0617: // Joe Orost (decvax!vax135!petsd!joe)
0618:
0619: int n_bits; // number of bits/code
0620:
0621: int maxbits = BITS; // user settable max # bits/code
0622:
0623: int maxcode; // maximum code, given n_bits
0624:
0625: int maxmaxcode = 1 << BITS; // should NEVER generate this code
0626:
0627: final int MAXCODE(int n_bits) {
0628: return (1 << n_bits) - 1;
0629: }
0630:
0631: int[] htab = new int[HSIZE];
0632:
0633: int[] codetab = new int[HSIZE];
0634:
0635: int hsize = HSIZE; // for dynamic table sizing
0636:
0637: int free_ent = 0; // first unused entry
0638:
0639: // block compression parameters -- after all codes are used up,
0640: // and compression rate changes, start over.
0641: boolean clear_flg = false;
0642:
0643: // Algorithm: use open addressing double hashing (no chaining) on the
0644: // prefix code / next character combination. We do a variant of Knuth's
0645: // algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
0646: // secondary probe. Here, the modular division first probe is gives way
0647: // to a faster exclusive-or manipulation. Also do block compression with
0648: // an adaptive reset, whereby the code table is cleared when the
0649: // compression
0650: // ratio decreases, but after the table fills. The variable-length
0651: // output
0652: // codes are re-sized at this point, and a special CLEAR code is
0653: // generated
0654: // for the decompressor. Late addition: construct the table according to
0655: // file size for noticeable speed improvement on small files. Please
0656: // direct
0657: // questions about this implementation to ames!jaw.
0658:
0659: int g_init_bits;
0660:
0661: int ClearCode;
0662:
0663: int EOFCode;
0664:
0665: void compress(int init_bits, OutputStream outs)
0666: throws IOException {
0667: int fcode;
0668: int i /* = 0 */;
0669: int c;
0670: int ent;
0671: int disp;
0672: int hsize_reg;
0673: int hshift;
0674:
0675: // Set up the globals: g_init_bits - initial number of bits
0676: g_init_bits = init_bits;
0677:
0678: // Set up the necessary values
0679: clear_flg = false;
0680: n_bits = g_init_bits;
0681: maxcode = MAXCODE(n_bits);
0682:
0683: ClearCode = 1 << (init_bits - 1);
0684: EOFCode = ClearCode + 1;
0685: free_ent = ClearCode + 2;
0686:
0687: char_init();
0688:
0689: ent = GIFNextPixel();
0690:
0691: hshift = 0;
0692: for (fcode = hsize; fcode < 65536; fcode *= 2)
0693: ++hshift;
0694: hshift = 8 - hshift; // set hash code range bound
0695:
0696: hsize_reg = hsize;
0697: cl_hash(hsize_reg); // clear hash table
0698:
0699: output(ClearCode, outs);
0700:
0701: outer_loop: while ((c = GIFNextPixel()) != EOF) {
0702: fcode = (c << maxbits) + ent;
0703: i = (c << hshift) ^ ent; // xor hashing
0704:
0705: if (htab[i] == fcode) {
0706: ent = codetab[i];
0707: continue;
0708: } else if (htab[i] >= 0) // non-empty slot
0709: {
0710: disp = hsize_reg - i; // secondary hash (after G. Knott)
0711: if (i == 0)
0712: disp = 1;
0713: do {
0714: if ((i -= disp) < 0)
0715: i += hsize_reg;
0716:
0717: if (htab[i] == fcode) {
0718: ent = codetab[i];
0719: continue outer_loop;
0720: }
0721: } while (htab[i] >= 0);
0722: }
0723: output(ent, outs);
0724: ent = c;
0725: if (free_ent < maxmaxcode) {
0726: codetab[i] = free_ent++; // code -> hashtable
0727: htab[i] = fcode;
0728: } else
0729: cl_block(outs);
0730: }
0731: // Put out the final code.
0732: output(ent, outs);
0733: output(EOFCode, outs);
0734: }
0735:
0736: // output
0737: //
0738: // Output the given code.
0739: // Inputs:
0740: // code: A n_bits-bit integer. If == -1, then EOF. This assumes
0741: // that n_bits =< wordsize - 1.
0742: // Outputs:
0743: // Outputs code to the file.
0744: // Assumptions:
0745: // Chars are 8 bits long.
0746: // Algorithm:
0747: // Maintain a BITS character long buffer (so that 8 codes will
0748: // fit in it exactly). Use the VAX insv instruction to insert each
0749: // code in turn. When the buffer fills up empty it and start over.
0750:
0751: int cur_accum = 0;
0752:
0753: int cur_bits = 0;
0754:
0755: int masks[] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000F, 0x001F,
0756: 0x003F, 0x007F, 0x00FF, 0x01FF, 0x03FF, 0x07FF, 0x0FFF,
0757: 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
0758:
0759: void output(int code, OutputStream outs) throws IOException {
0760: cur_accum &= masks[cur_bits];
0761:
0762: if (cur_bits > 0)
0763: cur_accum |= (code << cur_bits);
0764: else
0765: cur_accum = code;
0766:
0767: cur_bits += n_bits;
0768:
0769: while (cur_bits >= 8) {
0770: char_out((byte) (cur_accum & 0xff), outs);
0771: cur_accum >>= 8;
0772: cur_bits -= 8;
0773: }
0774:
0775: // If the next entry is going to be too big for the code size,
0776: // then increase it, if possible.
0777: if (free_ent > maxcode || clear_flg) {
0778: if (clear_flg) {
0779: maxcode = MAXCODE(n_bits = g_init_bits);
0780: clear_flg = false;
0781: } else {
0782: ++n_bits;
0783: if (n_bits == maxbits)
0784: maxcode = maxmaxcode;
0785: else
0786: maxcode = MAXCODE(n_bits);
0787: }
0788: }
0789:
0790: if (code == EOFCode) {
0791: // At EOF, write the rest of the buffer.
0792: while (cur_bits > 0) {
0793: char_out((byte) (cur_accum & 0xff), outs);
0794: cur_accum >>= 8;
0795: cur_bits -= 8;
0796: }
0797:
0798: flush_char(outs);
0799: }
0800: }
0801:
0802: // Clear out the hash table
0803:
0804: // table clear for block compress
0805: void cl_block(OutputStream outs) throws IOException {
0806: cl_hash(hsize);
0807: free_ent = ClearCode + 2;
0808: clear_flg = true;
0809:
0810: output(ClearCode, outs);
0811: }
0812:
0813: // reset code table
0814: void cl_hash(int hsize) {
0815: for (int i = 0; i < hsize; ++i)
0816: htab[i] = -1;
0817: }
0818:
0819: // GIF Specific routines
0820:
0821: // Number of characters so far in this 'packet'
0822: int a_count;
0823:
0824: // Set up the 'byte output' routine
0825: void char_init() {
0826: a_count = 0;
0827: }
0828:
0829: // Define the storage for the packet accumulator
0830: byte[] accum = new byte[256];
0831:
0832: // Add a character to the end of the current packet, and if it is 254
0833: // characters, flush the packet to disk.
0834: void char_out(byte c, OutputStream outs) throws IOException {
0835: accum[a_count++] = c;
0836: if (a_count >= 254)
0837: flush_char(outs);
0838: }
0839:
0840: // Flush the packet to disk, and reset the accumulator
0841: void flush_char(OutputStream outs) throws IOException {
0842: if (a_count > 0) {
0843: outs.write(a_count);
0844: outs.write(accum, 0, a_count);
0845: a_count = 0;
0846: }
0847: }
0848:
0849: }
0850:
0851: static class GifEncoderHashitem {
0852:
0853: public int rgb;
0854:
0855: public int count;
0856:
0857: public int index;
0858:
0859: public boolean isTransparent;
0860:
0861: public GifEncoderHashitem(int rgb, int count, int index,
0862: boolean isTransparent) {
0863: this .rgb = rgb;
0864: this .count = count;
0865: this .index = index;
0866: this .isTransparent = isTransparent;
0867: }
0868:
0869: }
0870:
0871: // / A Hashtable that uses ints as the keys.
0872: // <P>
0873: // Use just like java.util.Hashtable, except that the keys must be ints.
0874: // This is much faster than creating a new Integer for each access.
0875: // <P>
0876: // <A HREF="/resources/classes/Acme/IntHashtable.java">Fetch the
0877: // software.</A><BR>
0878: // <A HREF="/resources/classes/Acme.tar.gz">Fetch the entire Acme
0879: // package.</A>
0880: // <P>
0881: // @see java.util.Hashtable
0882:
0883: public static class IntHashtable extends Dictionary implements
0884: Cloneable {
0885: // / The hash table data.
0886: private IntHashtableEntry table[];
0887:
0888: // / The total number of entries in the hash table.
0889: private int count;
0890:
0891: // / Rehashes the table when count exceeds this threshold.
0892: private int threshold;
0893:
0894: // / The load factor for the hashtable.
0895: private float loadFactor;
0896:
0897: // / Constructs a new, empty hashtable with the specified initial
0898: // capacity and the specified load factor.
0899: // @param initialCapacity the initial number of buckets
0900: // @param loadFactor a number between 0.0 and 1.0, it defines
0901: // the threshold for rehashing the hashtable into
0902: // a bigger one.
0903: // @exception IllegalArgumentException If the initial capacity
0904: // is less than or equal to zero.
0905: // @exception IllegalArgumentException If the load factor is
0906: // less than or equal to zero.
0907: public IntHashtable(int initialCapacity, float loadFactor) {
0908: if (initialCapacity <= 0 || loadFactor <= 0.0)
0909: throw new IllegalArgumentException();
0910: this .loadFactor = loadFactor;
0911: table = new IntHashtableEntry[initialCapacity];
0912: threshold = (int) (initialCapacity * loadFactor);
0913: }
0914:
0915: // / Constructs a new, empty hashtable with the specified initial
0916: // capacity.
0917: // @param initialCapacity the initial number of buckets
0918: public IntHashtable(int initialCapacity) {
0919: this (initialCapacity, 0.75f);
0920: }
0921:
0922: // / Constructs a new, empty hashtable. A default capacity and load
0923: // factor
0924: // is used. Note that the hashtable will automatically grow when it gets
0925: // full.
0926: public IntHashtable() {
0927: this (101, 0.75f);
0928: }
0929:
0930: // / Returns the number of elements contained in the hashtable.
0931: public int size() {
0932: return count;
0933: }
0934:
0935: // / Returns true if the hashtable contains no elements.
0936: public boolean isEmpty() {
0937: return count == 0;
0938: }
0939:
0940: // / Returns an enumeration of the hashtable's keys.
0941: // @see IntHashtable#elements
0942: public synchronized Enumeration keys() {
0943: return new IntHashtableEnumerator(table, true);
0944: }
0945:
0946: // / Returns an enumeration of the elements. Use the Enumeration methods
0947: // on the returned object to fetch the elements sequentially.
0948: // @see IntHashtable#keys
0949: public synchronized Enumeration elements() {
0950: return new IntHashtableEnumerator(table, false);
0951: }
0952:
0953: // / Returns true if the specified object is an element of the
0954: // hashtable.
0955: // This operation is more expensive than the containsKey() method.
0956: // @param value the value that we are looking for
0957: // @exception NullPointerException If the value being searched
0958: // for is equal to null.
0959: // @see IntHashtable#containsKey
0960: public synchronized boolean contains(Object value) {
0961: if (value == null)
0962: throw new NullPointerException();
0963: IntHashtableEntry tab[] = table;
0964: for (int i = tab.length; i-- > 0;) {
0965: for (IntHashtableEntry e = tab[i]; e != null; e = e.next) {
0966: if (e.value.equals(value))
0967: return true;
0968: }
0969: }
0970: return false;
0971: }
0972:
0973: // / Returns true if the collection contains an element for the key.
0974: // @param key the key that we are looking for
0975: // @see IntHashtable#contains
0976: public synchronized boolean containsKey(int key) {
0977: IntHashtableEntry tab[] = table;
0978: int hash = key;
0979: int index = (hash & 0x7FFFFFFF) % tab.length;
0980: for (IntHashtableEntry e = tab[index]; e != null; e = e.next) {
0981: if (e.hash == hash && e.key == key)
0982: return true;
0983: }
0984: return false;
0985: }
0986:
0987: // / Gets the object associated with the specified key in the
0988: // hashtable.
0989: // @param key the specified key
0990: // @returns the element for the key or null if the key
0991: // is not defined in the hash table.
0992: // @see IntHashtable#put
0993: public synchronized Object get(int key) {
0994: IntHashtableEntry tab[] = table;
0995: int hash = key;
0996: int index = (hash & 0x7FFFFFFF) % tab.length;
0997: for (IntHashtableEntry e = tab[index]; e != null; e = e.next) {
0998: if (e.hash == hash && e.key == key)
0999: return e.value;
1000: }
1001: return null;
1002: }
1003:
1004: // / A get method that takes an Object, for compatibility with
1005: // java.util.Dictionary. The Object must be an Integer.
1006: public Object get(Object okey) {
1007: if (!(okey instanceof Integer))
1008: throw new InternalError("key is not an Integer");
1009: Integer ikey = (Integer) okey;
1010: int key = ikey.intValue();
1011: return get(key);
1012: }
1013:
1014: // / Rehashes the content of the table into a bigger table.
1015: // This method is called automatically when the hashtable's
1016: // size exceeds the threshold.
1017: protected void rehash() {
1018: int oldCapacity = table.length;
1019: IntHashtableEntry oldTable[] = table;
1020:
1021: int newCapacity = oldCapacity * 2 + 1;
1022: IntHashtableEntry newTable[] = new IntHashtableEntry[newCapacity];
1023:
1024: threshold = (int) (newCapacity * loadFactor);
1025: table = newTable;
1026:
1027: for (int i = oldCapacity; i-- > 0;) {
1028: for (IntHashtableEntry old = oldTable[i]; old != null;) {
1029: IntHashtableEntry e = old;
1030: old = old.next;
1031:
1032: int index = (e.hash & 0x7FFFFFFF) % newCapacity;
1033: e.next = newTable[index];
1034: newTable[index] = e;
1035: }
1036: }
1037: }
1038:
1039: // / Puts the specified element into the hashtable, using the specified
1040: // key. The element may be retrieved by doing a get() with the same key.
1041: // The key and the element cannot be null.
1042: // @param key the specified key in the hashtable
1043: // @param value the specified element
1044: // @exception NullPointerException If the value of the element
1045: // is equal to null.
1046: // @see IntHashtable#get
1047: // @return the old value of the key, or null if it did not have one.
1048: public synchronized Object put(int key, Object value) {
1049: // Make sure the value is not null.
1050: if (value == null)
1051: throw new NullPointerException();
1052:
1053: // Makes sure the key is not already in the hashtable.
1054: IntHashtableEntry tab[] = table;
1055: int hash = key;
1056: int index = (hash & 0x7FFFFFFF) % tab.length;
1057: for (IntHashtableEntry e = tab[index]; e != null; e = e.next) {
1058: if (e.hash == hash && e.key == key) {
1059: Object old = e.value;
1060: e.value = value;
1061: return old;
1062: }
1063: }
1064:
1065: if (count >= threshold) {
1066: // Rehash the table if the threshold is exceeded.
1067: rehash();
1068: return put(key, value);
1069: }
1070:
1071: // Creates the new entry.
1072: IntHashtableEntry e = new IntHashtableEntry();
1073: e.hash = hash;
1074: e.key = key;
1075: e.value = value;
1076: e.next = tab[index];
1077: tab[index] = e;
1078: ++count;
1079: return null;
1080: }
1081:
1082: // / A put method that takes an Object, for compatibility with
1083: // java.util.Dictionary. The Object must be an Integer.
1084: public Object put(Object okey, Object value) {
1085: if (!(okey instanceof Integer))
1086: throw new InternalError("key is not an Integer");
1087: Integer ikey = (Integer) okey;
1088: int key = ikey.intValue();
1089: return put(key, value);
1090: }
1091:
1092: // / Removes the element corresponding to the key. Does nothing if the
1093: // key is not present.
1094: // @param key the key that needs to be removed
1095: // @return the value of key, or null if the key was not found.
1096: public synchronized Object remove(int key) {
1097: IntHashtableEntry tab[] = table;
1098: int hash = key;
1099: int index = (hash & 0x7FFFFFFF) % tab.length;
1100: for (IntHashtableEntry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
1101: if (e.hash == hash && e.key == key) {
1102: if (prev != null)
1103: prev.next = e.next;
1104: else
1105: tab[index] = e.next;
1106: --count;
1107: return e.value;
1108: }
1109: }
1110: return null;
1111: }
1112:
1113: // / A remove method that takes an Object, for compatibility with
1114: // java.util.Dictionary. The Object must be an Integer.
1115: public Object remove(Object okey) {
1116: if (!(okey instanceof Integer))
1117: throw new InternalError("key is not an Integer");
1118: Integer ikey = (Integer) okey;
1119: int key = ikey.intValue();
1120: return remove(key);
1121: }
1122:
1123: // / Clears the hash table so that it has no more elements in it.
1124: public synchronized void clear() {
1125: IntHashtableEntry tab[] = table;
1126: for (int index = tab.length; --index >= 0;)
1127: tab[index] = null;
1128: count = 0;
1129: }
1130:
1131: // / Creates a clone of the hashtable. A shallow copy is made,
1132: // the keys and elements themselves are NOT cloned. This is a
1133: // relatively expensive operation.
1134: public synchronized Object clone() {
1135: try {
1136: IntHashtable t = (IntHashtable) super .clone();
1137: t.table = new IntHashtableEntry[table.length];
1138: for (int i = table.length; i-- > 0;)
1139: t.table[i] = (table[i] != null) ? (IntHashtableEntry) table[i]
1140: .clone()
1141: : null;
1142: return t;
1143: } catch (CloneNotSupportedException e) {
1144: // This shouldn't happen, since we are Cloneable.
1145: throw new InternalError();
1146: }
1147: }
1148:
1149: // / Converts to a rather lengthy String.
1150: public synchronized String toString() {
1151: int max = size() - 1;
1152: StringBuffer buf = new StringBuffer();
1153: Enumeration k = keys();
1154: Enumeration e = elements();
1155: buf.append("{");
1156:
1157: for (int i = 0; i <= max; ++i) {
1158: String s1 = k.nextElement().toString();
1159: String s2 = e.nextElement().toString();
1160: buf.append(s1 + "=" + s2);
1161: if (i < max)
1162: buf.append(", ");
1163: }
1164: buf.append("}");
1165: return buf.toString();
1166: }
1167: }
1168:
1169: static class IntHashtableEntry {
1170: int hash;
1171:
1172: int key;
1173:
1174: Object value;
1175:
1176: IntHashtableEntry next;
1177:
1178: protected Object clone() {
1179: IntHashtableEntry entry = new IntHashtableEntry();
1180: entry.hash = hash;
1181: entry.key = key;
1182: entry.value = value;
1183: entry.next = (next != null) ? (IntHashtableEntry) next
1184: .clone() : null;
1185: return entry;
1186: }
1187: }
1188:
1189: static class IntHashtableEnumerator implements Enumeration {
1190: boolean keys;
1191:
1192: int index;
1193:
1194: IntHashtableEntry table[];
1195:
1196: IntHashtableEntry entry;
1197:
1198: IntHashtableEnumerator(IntHashtableEntry table[], boolean keys) {
1199: this .table = table;
1200: this .keys = keys;
1201: this .index = table.length;
1202: }
1203:
1204: public boolean hasMoreElements() {
1205: if (entry != null)
1206: return true;
1207: while (index-- > 0)
1208: if ((entry = table[index]) != null)
1209: return true;
1210: return false;
1211: }
1212:
1213: public Object nextElement() {
1214: if (entry == null)
1215: while ((index-- > 0)
1216: && ((entry = table[index]) == null))
1217: ;
1218: if (entry != null) {
1219: IntHashtableEntry e = entry;
1220: entry = e.next;
1221: return keys ? new Integer(e.key) : e.value;
1222: }
1223: throw new NoSuchElementException("IntHashtableEnumerator");
1224: }
1225: }
1226:
1227: }
|