3 * $Date: 2007-06-02 12:14:13 -0500 (Sat, 02 Jun 2007) $
6 * Some portions of this file have been modified by Robert Hanson hansonr.at.stolaf.edu 2012-2017
7 * for use in SwingJS via transpilation into JavaScript using Java2Script.
9 * Copyright (C) 2000-2005 The Jmol Development Team
11 * Contact: jmol-developers@lists.sf.net
13 * This library is free software; you can redistribute it and/or
14 * modify it under the terms of the GNU Lesser General Public
15 * License as published by the Free Software Foundation; either
16 * version 2.1 of the License, or (at your option) any later version.
18 * This library is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 * Lesser General Public License for more details.
23 * You should have received a copy of the GNU Lesser General Public
24 * License along with this library; if not, write to the Free Software
25 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
28 // Final encoding code from http://acme.com/resources/classes/Acme/JPM/Encoders/GifEncoder.java
30 // GifEncoder - write out an image as a GIF
33 // Transparency handling and variable bit size courtesy of Jack Palevich.
35 // Copyright (C)1996,1998 by Jef Poskanzer <jef@mail.acme.com>. All rights reserved.
37 // Redistribution and use in source and binary forms, with or without
38 // modification, are permitted provided that the following conditions
40 // 1. Redistributions of source code must retain the above copyright
41 // notice, this list of conditions and the following disclaimer.
42 // 2. Redistributions in binary form must reproduce the above copyright
43 // notice, this list of conditions and the following disclaimer in the
44 // documentation and/or other materials provided with the distribution.
46 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
47 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
48 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
49 // ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
50 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
51 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
52 // OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
53 // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
54 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
55 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
58 // Visit the ACME Labs Java page for up-to-date versions of this and other
59 // fine Java utilities: http://www.acme.com/java/
61 /// Write out an image as a GIF.
63 // <A HREF="/resources/classes/Acme/JPM/Encoders/GifEncoder.java">Fetch the software.</A><BR>
64 // <A HREF="/resources/classes/Acme.tar.gz">Fetch the entire Acme package.</A>
70 import javajs.util.CU;
71 import javajs.util.Lst;
72 import javajs.util.M3;
73 import javajs.util.P3;
75 import java.util.Hashtable;
77 import java.io.IOException;
81 * GifEncoder extensively adapted for Jmol by Bob Hanson
83 * Color quantization roughly follows the GIMP method
84 * "dither Floyd-Steinberg (normal)" but with some twists. (For example, we
85 * exclude the background color.)
87 * Note that although GIMP code annotation refers to "median-cut", it is really
88 * using MEAN-cut. That is what I use here as well.
90 * -- commented code allows visualization of the color space using Jmol. Very
93 * -- much simplified interface with ImageEncoder
95 * -- uses simple Hashtable with Integer() to catalog colors
97 * -- allows progressive production of animated GIF via Jmol CAPTURE command
99 * -- uses general purpose javajs.util.OutputChannel for byte-handling options
100 * such as posting to a server, writing to disk, and retrieving bytes.
102 * -- allows JavaScript port
104 * -- Bob Hanson, first try: 24 Sep 2013; final coding: 9 Nov 2014
107 * @author Bob Hanson hansonr@stolaf.edu
110 public class GifEncoder extends ImageEncoder {
112 private Map<String, Object> params;
113 private P3[] palette;
114 private int backgroundColor;
116 private boolean interlaced;
117 private boolean addHeader = true;
118 private boolean addImage = true;
119 private boolean addTrailer = true;
120 private boolean isTransparent;
121 private boolean floydSteinberg = true;
122 private boolean capturing;
123 private boolean looping;
125 private int delayTime100ths = -1;
126 private int bitsPerPixel = 1;
128 private int byteCount;
131 * we allow for animated GIF by being able to re-enter the code with different
132 * parameters held in params
137 protected void setParams(Map<String, Object> params) {
138 this.params = params;
139 Integer ic = (Integer) params.get("transparentColor");
141 ic = (Integer) params.get("backgroundColor");
143 backgroundColor = ic.intValue();
145 backgroundColor = ic.intValue();
146 isTransparent = true;
149 interlaced = (Boolean.TRUE == params.get("interlaced"));
150 if (params.containsKey("captureRootExt") // file0000.gif
151 || !params.containsKey("captureMode")) // animated gif
156 byteCount = ((Integer) params.get("captureByteCount")).intValue();
157 } catch (Exception e) {
161 .indexOf(((String) params.get("captureMode")).substring(0, 1))) {
163 params.put("captureMode", "add");
170 int fps = Math.abs(((Integer) params.get("captureFps")).intValue());
171 delayTime100ths = (fps == 0 ? 0 : 100 / fps);
172 looping = (Boolean.FALSE != params.get("captureLooping"));
187 protected void generate() throws IOException {
190 addHeader = false; // only one header
193 writeGraphicControlExtension();
194 if (delayTime100ths >= 0 && looping)
195 writeNetscapeLoopExtension();
201 protected void close() {
208 params.put("captureByteCount", Integer.valueOf(byteCount));
211 ////////////// 256-color quantization //////////////
214 * a color point in normalized L*a*b space with a flag indicating whether it
215 * is the background color
217 private class ColorItem extends P3 {
221 protected boolean isBackground;
223 ColorItem(int rgb, boolean isBackground) {
224 this.isBackground = isBackground;
225 setT(toLABnorm(rgb));
230 * A list of normalized L*a*b points with an index and a center and volume
233 private class ColorCell extends Lst<P3> {
238 private static final long serialVersionUID = 1L;
242 private float volume;
244 ColorCell(int index) {
251 * @return volume in normalized L*a*b space
253 public float getVolume(boolean doVisualize) {
261 float maxx = -Integer.MAX_VALUE;
262 float minx = Integer.MAX_VALUE;
263 float maxy = -Integer.MAX_VALUE;
264 float miny = Integer.MAX_VALUE;
265 float maxz = -Integer.MAX_VALUE;
266 float minz = Integer.MAX_VALUE;
268 for (int i = n; --i >= 0;) {
283 float dx = (maxx - minx);
284 float dy = (maxy - miny);
285 float dz = (maxz - minz);
286 // Jmol visualization only
287 // if (doVisualize) {
288 // P3 ptRGB = toRGB(center);
289 // drawPt(index, -size(), ptRGB);
290 // //for (int i = n; --i >= 0;)
291 // //drawPt(index, i, toRGB(get(i)));
292 // P3 pt0 = toRGB(P3.new3(Math.max(minx, 0), Math.max(miny, 0),
293 // Math.max(minz, 0)));
294 // P3 pt1 = toRGB(P3.new3(Math.min(maxx, 100), Math.min(maxy, 100),
295 // Math.min(maxz, 100)));
296 // rgbToXyz(pt0, pt0);
297 // xyzToLab(pt0, pt0);
298 // rgbToXyz(pt1, pt1);
299 // xyzToLab(pt1, pt1);
300 // System.out.println("boundbox corners " + pt0 + " " + pt1);
301 // System.out.println("draw d" + index + " boundbox color " + ptRGB
302 // + " mesh nofill");
304 return volume = dx * dx + dy * dy + dz * dz;
307 // // Jmol visualization only
308 // private void drawPt(int index, int i, P3 rgb) {
309 // boolean isMain = (i < 0);
310 // P3 lab = rgbToXyz(rgb, null);
311 // xyzToLab(lab, lab);
312 // System.out.println("draw d" + index + (isMain ? "_" : "_" + i) + " width "
313 // + (isMain ? 1.0 : 0.2) + " " + lab
314 // + " color " + rgb + (isMain ? " '" + -i + "'" : ""));
318 * Set the average normalized L*a*b value for this cell and return its RGB point
323 protected P3 setColor() {
326 for (int i = count; --i >= 0;)
328 center.scale(1f / count);
329 // Jmol visualization only
332 return toRGB(center);
336 * use median_cut algorithm to split the cell, creating a doubly linked
339 * Paul Heckbert, MIT thesis COLOR IMAGE QUANTIZATION FOR FRAME BUFFER
340 * DISPLAY https://www.cs.cmu.edu/~ph/ciq_thesis
342 * except, as in GIMP, we use center (not median) here.
345 * @return true if split
347 protected boolean splitCell(Lst<ColorCell> cells) {
351 int newIndex = cells.size();
352 ColorCell newCell = new ColorCell(newIndex);
353 cells.addLast(newCell);
354 float[][] ranges = new float[3][3];
355 for (int ic = 0; ic < 3; ic++) {
356 float low = Float.MAX_VALUE;
357 float high = -Float.MAX_VALUE;
358 for (int i = n; --i >= 0;) {
360 float v = (ic == 0 ? lab.x : ic == 1 ? lab.y : lab.z);
367 ranges[1][ic] = high;
368 ranges[2][ic] = high - low;
370 float[] r = ranges[2];
371 int mode = (r[0] >= r[1] ? (r[0] >= r[2] ? 0 : 2) : r[1] >= r[2] ? 1 : 2);
372 float val = ranges[0][mode] + ranges[2][mode] / 2;
373 volume = 0; // recalculate volume if needed
376 for (int i = n; --i >= 0;)
378 newCell.addLast(removeItemAt(i));
381 for (int i = n; --i >= 0;)
383 newCell.addLast(removeItemAt(i));
386 for (int i = size(); --i >= 0;)
388 newCell.addLast(removeItemAt(i));
396 * Quantize all colors and create the final palette;
397 * replace pixels[] with an array of color indices.
400 private void createPalette() {
402 // catalog all pixel colors
404 Lst<ColorItem> tempColors = new Lst<ColorItem>();
405 Map<Integer, ColorItem> ciHash = new Hashtable<Integer, ColorItem>();
406 for (int i = 0, n = pixels.length; i < n; i++) {
408 Integer key = Integer.valueOf(rgb);
409 ColorItem item = ciHash.get(key);
411 item = new ColorItem(rgb, rgb == backgroundColor);
412 ciHash.put(key, item);
413 tempColors.addLast(item);
416 int nColors = tempColors.size();
417 System.out.println("GIF total image colors: " + nColors);
420 // create a set of <= 256 color cells
422 Lst<ColorCell> cells = quantizeColors(tempColors);
423 nColors = cells.size();
424 System.out.println("GIF final color count: " + nColors);
426 // generate the palette and map each cell's rgb color to itself
428 Map<Integer, ColorCell> colorMap = new Hashtable<Integer, ColorCell>();
429 bitsPerPixel = (nColors <= 2 ? 1 : nColors <= 4 ? 2 : nColors <= 16 ? 4 : 8);
430 palette = new P3[1 << bitsPerPixel];
431 for (int i = 0; i < nColors; i++) {
432 ColorCell c = cells.get(i);
434 Integer.valueOf(CU.colorPtToFFRGB(palette[i] = c.setColor())), c);
437 // index all pixels to a pallete color
439 pixels = indexPixels(cells, colorMap);
443 * Quantize colors by generating a set of cells in normalized L*a*b space
444 * containing all colors. Start with just two cells -- fixed background color
445 * and all others. Keep splitting cells while there are fewer than 256 and
446 * some with multiple colors in them.
448 * It is possible that we will end up with fewer than 256 colors.
451 * @return final list of colors
453 private Lst<ColorCell> quantizeColors(Lst<ColorItem> tempColors) {
454 int n = tempColors.size();
455 Lst<ColorCell> cells = new Lst<ColorCell>();
456 ColorCell cc = new ColorCell(0);
457 cc.addLast(new ColorItem(backgroundColor, true));
459 cc = new ColorCell(1);
462 for (int i = 0; i < n; i++) {
463 ColorItem c = tempColors.get(i);
469 cc = new ColorCell(cells.size());
474 while ((n = cells.size()) < 256) {
476 ColorCell maxCell = null;
477 for (int i = n; --i >= 1;) {
478 ColorCell c = cells.get(i);
479 float v = c.getVolume(false);
485 if (maxCell == null || !maxCell.splitCell(cells))
493 * Assign all colors to their closest approximation and return an array of
496 * Uses Floyd-Steinberg dithering, finding the closest known color and then
497 * spreading out the error over four leading pixels. Limits error to +/- 75
498 * percent in normalized L*a*b space.
501 * quantized color cells
503 * map of quantized rgb to its cell
504 * @return array of color indexes, one for each pixel
507 private int[] indexPixels(Lst<ColorCell> cells,
508 Map<Integer, ColorCell> colorMap) {
509 // We need a strip only width+2 wide to process all the errors.
510 // Errors are added to the next pixel and the next row's pixels
511 // only through p + width + 1:
514 // so including p as well, we need a total of width + 2 errors.
516 // as p moves through the pixels, we just use mod to cycle through
520 P3[] errors = new P3[w2];
521 // We should replace, not overwrite, pixels
522 // as this may be the raw canvas.buf32.
523 int[] newPixels = new int[pixels.length];
527 Map<Integer, ColorCell> nearestCell = new Hashtable<Integer, ColorCell>();
528 for (int i = 0, p = 0; i < height; ++i) {
529 boolean notLastRow = (i != height - 1);
530 for (int j = 0; j < width; ++j, p++) {
531 if (pixels[p] == backgroundColor) {
535 P3 pe = errors[p % w2];
536 if (pe == null || pe.x == Float.MAX_VALUE) {
540 lab = toLABnorm(pixels[p]);
542 // important not to round the clamp here -- full floating precision
543 err.x = clamp(err.x, -75, 75);
544 err.y = clamp(err.y, -75, 75);
545 err.z = clamp(err.z, -75, 75);
547 rgb = CU.colorPtToFFRGB(toRGB(lab));
549 Integer key = Integer.valueOf(rgb);
550 ColorCell cell = colorMap.get(key);
552 // critical to generate normalized L*a*b from RGB here for nearestCell mapping.
553 // otherwise future RGB keys may match the wrong cell
554 lab = toLABnorm(rgb);
555 cell = nearestCell.get(key);
558 float maxerr = Float.MAX_VALUE;
560 for (int ib = cells.size(); --ib >= 1;) {
561 ColorCell c = cells.get(ib);
562 err.sub2(lab, c.center);
563 float d = err.lengthSquared();
569 nearestCell.put(key, cell);
571 if (floydSteinberg) {
573 err.sub2(lab, cell.center);
574 boolean notLastCol = (j < width - 1);
576 addError(err, 7, errors, p + 1, w2);
579 addError(err, 3, errors, p + width - 1, w2);
580 addError(err, 5, errors, p + width, w2);
582 addError(err, 1, errors, p + width + 1, w2);
585 err.x = Float.MAX_VALUE; // used; flag for resetting to 0
587 newPixels[p] = cell.index;
593 private void addError(P3 err, int f, P3[] errors, int p, int w2) {
594 // GIMP will allow changing the background color.
595 if (pixels[p] == backgroundColor)
600 errp = errors[p] = new P3();
601 else if (errp.x == Float.MAX_VALUE) // reuse
603 errp.scaleAdd2(f / 16f, err, errp);
606 ///////////////////////// CIE L*a*b / XYZ / sRGB conversion methods /////////
608 // these could be static, but that just makes for more JavaScript code
610 protected P3 toLABnorm(int rgb) {
611 P3 lab = CU.colorPtFromInt(rgb, null);
614 // normalize to 0-100
615 lab.y = (lab.y + 86.185f) / (98.254f + 86.185f) * 100f;
616 lab.z = (lab.z + 107.863f) / (94.482f + 107.863f) * 100f;
620 protected P3 toRGB(P3 lab) {
621 P3 xyz = P3.newP(lab);
622 // normalized to 0-100
623 xyz.y = xyz.y / 100f * (98.254f + 86.185f) - 86.185f;
624 xyz.z = xyz.z / 100f * (94.482f + 107.863f) - 107.863f;
626 return xyzToRgb(xyz, xyz);
629 private static M3 xyz2rgb;
630 private static M3 rgb2xyz;
633 rgb2xyz = M3.newA9(new float[] { 0.4124f, 0.3576f, 0.1805f, 0.2126f,
634 0.7152f, 0.0722f, 0.0193f, 0.1192f, 0.9505f });
636 xyz2rgb = M3.newA9(new float[] { 3.2406f, -1.5372f, -0.4986f, -0.9689f,
637 1.8758f, 0.0415f, 0.0557f, -0.2040f, 1.0570f });
640 public P3 rgbToXyz(P3 rgb, P3 xyz) {
641 // http://en.wikipedia.org/wiki/CIE_1931_color_space
642 // http://rsb.info.nih.gov/ij/plugins/download/Color_Space_Converter.java
652 private float sxyz(float x) {
654 return (float) (x <= 0.04045 ? x / 12.92 : Math.pow(((x + 0.055) / 1.055),
658 public P3 xyzToRgb(P3 xyz, P3 rgb) {
659 // http://en.wikipedia.org/wiki/CIE_1931_color_space
660 // http://rsb.info.nih.gov/ij/plugins/download/Color_Space_Converter.java
666 rgb.x = clamp(srgb(rgb.x), 0, 255);
667 rgb.y = clamp(srgb(rgb.y), 0, 255);
668 rgb.z = clamp(srgb(rgb.z), 0, 255);
672 private float srgb(float x) {
673 return (float) (x > 0.0031308f ? (1.055 * Math.pow(x, 1.0 / 2.4)) - 0.055
677 public P3 xyzToLab(P3 xyz, P3 lab) {
678 // http://en.wikipedia.org/wiki/Lab_color_space
679 // http://rsb.info.nih.gov/ij/plugins/download/Color_Space_Converter.java
680 // Lab([0..100], [-86.185..98.254], [-107.863..94.482])
681 // XYZn = D65 = {95.0429, 100.0, 108.8900};
684 float x = flab(xyz.x / 95.0429f);
685 float y = flab(xyz.y / 100);
686 float z = flab(xyz.z / 108.89f);
687 lab.x = (116 * y) - 16;
688 lab.y = 500 * (x - y);
689 lab.z = 200 * (y - z);
693 private float flab(float t) {
694 return (float) (t > 8.85645168E-3 /* (24/116)^3 */? Math.pow(t,
695 0.333333333) : 7.78703704 /* 1/3*116/24*116/24 */* t + 0.137931034 /* 16/116 */
699 public P3 labToXyz(P3 lab, P3 xyz) {
700 // http://en.wikipedia.org/wiki/Lab_color_space
701 // http://rsb.info.nih.gov/ij/plugins/download/Color_Space_Converter.java
702 // XYZn = D65 = {95.0429, 100.0, 108.8900};
707 float y = (xyz.x + 16) / 116;
708 float x = xyz.y / 500 + y;
709 float z = y - xyz.z / 200;
710 xyz.x = fxyz(x) * 95.0429f;
711 xyz.y = fxyz(y) * 100;
712 xyz.z = fxyz(z) * 108.89f;
717 private float fxyz(float t) {
718 return (float) (t > 0.206896552 /* (24/116) */? t * t * t
719 : 0.128418549 /* 3*24/116*24/116 */* (t - 0.137931034 /* 16/116 */));
722 private float clamp(float c, float min, float max) {
723 c = (c < min ? min : c > max ? max : c);
724 return (min == 0 ? Math.round(c) : c);
727 ///////////////////////// GifEncoder writing methods ////////////////////////
730 * includes logical screen descriptor
732 * @throws IOException
734 private void writeHeader() throws IOException {
738 putByte(0); // no global color table -- using local instead
739 putByte(0); // no background
740 putByte(0); // no pixel aspect ratio given
743 private void writeGraphicControlExtension() {
744 if (isTransparent || delayTime100ths >= 0) {
745 putByte(0x21); // graphic control extension
746 putByte(0xf9); // graphic control label
747 putByte(4); // block size
748 putByte((isTransparent ? 9 : 0) | (delayTime100ths > 0 ? 2 : 0)); // packed bytes
749 putWord(delayTime100ths > 0 ? delayTime100ths : 0);
750 putByte(0); // transparent index
751 putByte(0); // end-of-block
755 // see http://www.vurdalakov.net/misc/gif/netscape-looping-application-extension
757 // 0 | 0x21 | Extension Label
759 // 1 | 0xFF | Application Extension Label
761 // 2 | 0x0B | Block Size
770 // +- NETSCAPE -+ Application Identifier (8 bytes)
781 // 12 | 2.0 | Application Authentication Code (3 bytes)
784 // +===============+ --+
785 // 14 | 0x03 | Sub-block Data Size |
786 // +---------------+ |
787 // 15 | 0x01 | Sub-block ID |
788 // +---------------+ | Application Data Sub-block
790 // +- -+ Loop Count (2 bytes) |
792 // +===============+ --+
793 // 18 | 0x00 | Block Terminator
796 private void writeNetscapeLoopExtension() {
797 putByte(0x21); // graphic control extension
798 putByte(0xff); // netscape loop extension
799 putByte(0x0B); // block size
800 putString("NETSCAPE2.0");
803 putWord(0); // loop indefinitely
804 putByte(0); // end-of-block
808 private int initCodeSize;
811 private void writeImage() {
818 // <Packed Fields> = LISx xZZZ
820 // L Local Color Table Flag
824 // ZZZ Size of Local Color Table
826 int packedFields = 0x80 | (interlaced ? 0x40 : 0) | (bitsPerPixel - 1);
827 putByte(packedFields);
828 int colorMapSize = 1 << bitsPerPixel;
830 for (int i = 0; i < colorMapSize; i++) {
831 if (palette[i] != null)
837 putByte(initCodeSize = (bitsPerPixel <= 1 ? 2 : bitsPerPixel));
842 private void writeTrailer() {
843 // Write the GIF file terminator
847 ///// compression routines /////
849 private static final int EOF = -1;
851 // Return the next pixel from the image
852 private int nextPixel() {
853 if (countDown-- == 0)
855 int colorIndex = pixels[curpt];
856 // Bump the current X position
859 // If we are at the end of a scan line, set curx back to the beginning
860 // If we are interlaced, bump the cury to the appropriate spot,
861 // otherwise, just increment it.
864 updateY(INTERLACE_PARAMS[pass], INTERLACE_PARAMS[pass + 4]);
868 curpt = cury * width + curx;
869 return colorIndex & 0xff;
872 private static final int[] INTERLACE_PARAMS = { 8, 8, 4, 2, 4, 2, 1, 0 };
876 * Group 1 : Every 8th. row, starting with row 0. (Pass 1)
878 * Group 2 : Every 8th. row, starting with row 4. (Pass 2)
880 * Group 3 : Every 4th. row, starting with row 2. (Pass 3)
882 * Group 4 : Every 2nd. row, starting with row 1. (Pass 4)
887 private void updateY(int yNext, int yNew) {
889 if (yNew >= 0 && cury >= height) {
895 // Write out a word to the GIF file
896 private void putWord(int w) {
901 // GIFCOMPR.C - GIF Image compression routines
903 // Lempel-Ziv compression based on 'compress'. GIF modifications by
904 // David Rowley (mgardi@watdcsu.waterloo.edu)
908 private static final int BITS = 12;
910 private static final int HSIZE = 5003; // 80% occupancy
912 // GIF Image compression - modified 'compress'
914 // Based on: compress.c - File compression ala IEEE Computer, June 1984.
916 // By Authors: Spencer W. Thomas (decvax!harpo!utah-cs!utah-gr!thomas)
917 // Jim McKie (decvax!mcvax!jim)
918 // Steve Davies (decvax!vax135!petsd!peora!srd)
919 // Ken Turkowski (decvax!decwrl!turtlevax!ken)
920 // James A. Woods (decvax!ihnp4!ames!jaw)
921 // Joe Orost (decvax!vax135!petsd!joe)
923 private int nBits; // number of bits/code
924 private int maxbits = BITS; // user settable max # bits/code
925 private int maxcode; // maximum code, given n_bits
926 private int maxmaxcode = 1 << BITS; // should NEVER generate this code
928 private final static int MAXCODE(int nBits) {
929 return (1 << nBits) - 1;
932 private int[] htab = new int[HSIZE];
933 private int[] codetab = new int[HSIZE];
935 private int hsize = HSIZE; // for dynamic table sizing
937 private int freeEnt = 0; // first unused entry
939 // block compression parameters -- after all codes are used up,
940 // and compression rate changes, start over.
941 private boolean clearFlag = false;
943 // Algorithm: use open addressing double hashing (no chaining) on the
944 // prefix code / next character combination. We do a variant of Knuth's
945 // algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
946 // secondary probe. Here, the modular division first probe is gives way
947 // to a faster exclusive-or manipulation. Also do block compression with
948 // an adaptive reset, whereby the code table is cleared when the compression
949 // ratio decreases, but after the table fills. The variable-length output
950 // codes are re-sized at this point, and a special CLEAR code is generated
951 // for the decompressor. Late addition: construct the table according to
952 // file size for noticeable speed improvement on small files. Please direct
953 // questions about this implementation to ames!jaw.
955 private int clearCode;
958 private int countDown;
959 private int pass = 0;
960 private int curx, cury;
962 private void compress() {
964 // Calculate number of bits we are expecting
965 countDown = width * height;
967 // Indicate which pass we are on (if interlace)
969 // Set up the current x and y position
973 // Set up the necessary values
975 nBits = initCodeSize + 1;
976 maxcode = MAXCODE(nBits);
978 clearCode = 1 << initCodeSize;
979 EOFCode = clearCode + 1;
980 freeEnt = clearCode + 2;
982 // Set up the 'byte output' routine
985 int ent = nextPixel();
989 for (fcode = hsize; fcode < 65536; fcode *= 2)
991 hshift = 8 - hshift; // set hash code range bound
993 int hsizeReg = hsize;
994 clearHash(hsizeReg); // clear hash table
999 outer_loop: while ((c = nextPixel()) != EOF) {
1000 fcode = (c << maxbits) + ent;
1001 int i = (c << hshift) ^ ent; // xor hashing
1003 if (htab[i] == fcode) {
1006 } else if (htab[i] >= 0) // non-empty slot
1008 int disp = hsizeReg - i; // secondary hash (after G. Knott)
1012 if ((i -= disp) < 0)
1015 if (htab[i] == fcode) {
1017 continue outer_loop;
1019 } while (htab[i] >= 0);
1023 if (freeEnt < maxmaxcode) {
1024 codetab[i] = freeEnt++; // code -> hashtable
1030 // Put out the final code.
1037 // Output the given code.
1039 // code: A n_bits-bit integer. If == -1, then EOF. This assumes
1040 // that n_bits =< wordsize - 1.
1042 // Outputs code to the file.
1044 // Chars are 8 bits long.
1046 // Maintain a BITS character long buffer (so that 8 codes will
1047 // fit in it exactly). Use the VAX insv instruction to insert each
1048 // code in turn. When the buffer fills up empty it and start over.
1050 private int curAccum = 0;
1051 private int curBits = 0;
1053 private int masks[] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000F, 0x001F,
1054 0x003F, 0x007F, 0x00FF, 0x01FF, 0x03FF, 0x07FF, 0x0FFF, 0x1FFF, 0x3FFF,
1057 private void output(int code) {
1058 curAccum &= masks[curBits];
1061 curAccum |= (code << curBits);
1067 while (curBits >= 8) {
1068 byteOut((byte) (curAccum & 0xff));
1073 // If the next entry is going to be too big for the code size,
1074 // then increase it, if possible.
1075 if (freeEnt > maxcode || clearFlag) {
1077 maxcode = MAXCODE(nBits = initCodeSize + 1);
1081 if (nBits == maxbits)
1082 maxcode = maxmaxcode;
1084 maxcode = MAXCODE(nBits);
1088 if (code == EOFCode) {
1089 // At EOF, write the rest of the buffer.
1090 while (curBits > 0) {
1091 byteOut((byte) (curAccum & 0xff));
1099 // Clear out the hash table
1101 // table clear for block compress
1102 private void clearBlock() {
1104 freeEnt = clearCode + 2;
1111 private void clearHash(int hsize) {
1112 for (int i = 0; i < hsize; ++i)
1116 // GIF-specific routines (byte array buffer)
1118 // Number of bytes so far in this 'packet'
1121 // Define the storage for the packet accumulator
1122 final private byte[] buf = new byte[256];
1124 // Add a byte to the end of the current packet, and if it is 254
1125 // byte, flush the packet to disk.
1126 private void byteOut(byte c) {
1132 // Flush the packet to disk, and reset the accumulator
1133 protected void flushBytes() {
1136 out.write(buf, 0, bufPt);