unused/javajs/img/GifEncoder.java

   1 /* $RCSfile$
   2  * $Author: hansonr $
   3  * $Date: 2007-06-02 12:14:13 -0500 (Sat, 02 Jun 2007) $
   4  * $Revision: 7831 $
   5  *
   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.
   8  *
   9  * Copyright (C) 2000-2005  The Jmol Development Team
  10  *
  11  * Contact: jmol-developers@lists.sf.net
  12  *
  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.
  17  *
  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.
  22  *
  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.
  26  */
  27
  28 //  Final encoding code from http://acme.com/resources/classes/Acme/JPM/Encoders/GifEncoder.java
  29 //
  30 //  GifEncoder - write out an image as a GIF
  31 //
  32 //
  33 //  Transparency handling and variable bit size courtesy of Jack Palevich.
  34 //
  35 //  Copyright (C)1996,1998 by Jef Poskanzer <jef@mail.acme.com>. All rights reserved.
  36 //
  37 //  Redistribution and use in source and binary forms, with or without
  38 //  modification, are permitted provided that the following conditions
  39 //  are met:
  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.
  45 //
  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
  56 //  SUCH DAMAGE.
  57 //
  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/
  60 //
  61 /// Write out an image as a GIF.
  62 // <P>
  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>
  65 // <P>
  66 // @see ToGif
  67
  68 package javajs.img;
  69
  70 import javajs.util.CU;
  71 import javajs.util.Lst;
  72 import javajs.util.M3;
  73 import javajs.util.P3;
  74
  75 import java.util.Hashtable;
  76 import java.util.Map;
  77 import java.io.IOException;
  78
  79 /**
  80  *
  81  * GifEncoder extensively adapted for Jmol by Bob Hanson
  82  *
  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.)
  86  *
  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.
  89  *
  90  * -- commented code allows visualization of the color space using Jmol. Very
  91  * enlightening!
  92  *
  93  * -- much simplified interface with ImageEncoder
  94  *
  95  * -- uses simple Hashtable with Integer() to catalog colors
  96  *
  97  * -- allows progressive production of animated GIF via Jmol CAPTURE command
  98  *
  99  * -- uses general purpose javajs.util.OutputChannel for byte-handling options
 100  * such as posting to a server, writing to disk, and retrieving bytes.
 101  *
 102  * -- allows JavaScript port
 103  *
 104  * -- Bob Hanson, first try: 24 Sep 2013; final coding: 9 Nov 2014
 105  *
 106  *
 107  * @author Bob Hanson hansonr@stolaf.edu
 108  */
 109
 110 public class GifEncoder extends ImageEncoder {
 111
 112   private Map<String, Object> params;
 113   private P3[] palette;
 114   private int backgroundColor;
 115
 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;
 124
 125   private int delayTime100ths = -1;
 126   private int bitsPerPixel = 1;
 127
 128   private int byteCount;
 129
 130   /**
 131    * we allow for animated GIF by being able to re-enter the code with different
 132    * parameters held in params
 133    *
 134    *
 135    */
 136   @Override
 137   protected void setParams(Map<String, Object> params) {
 138     this.params = params;
 139     Integer ic = (Integer) params.get("transparentColor");
 140     if (ic == null) {
 141       ic = (Integer) params.get("backgroundColor");
 142       if (ic != null)
 143         backgroundColor = ic.intValue();
 144     } else {
 145       backgroundColor = ic.intValue();
 146       isTransparent = true;
 147     }
 148
 149     interlaced = (Boolean.TRUE == params.get("interlaced"));
 150     if (params.containsKey("captureRootExt") // file0000.gif
 151         || !params.containsKey("captureMode")) // animated gif
 152       return;
 153     interlaced = false;
 154     capturing = true;
 155     try {
 156       byteCount = ((Integer) params.get("captureByteCount")).intValue();
 157     } catch (Exception e) {
 158       // ignore
 159     }
 160     switch ("maec"
 161         .indexOf(((String) params.get("captureMode")).substring(0, 1))) {
 162     case 0: //"movie"
 163       params.put("captureMode", "add");
 164       addImage = false;
 165       addTrailer = false;
 166       break;
 167     case 1: // add
 168       addHeader = false;
 169       addTrailer = false;
 170       int fps = Math.abs(((Integer) params.get("captureFps")).intValue());
 171       delayTime100ths = (fps == 0 ? 0 : 100 / fps);
 172       looping = (Boolean.FALSE != params.get("captureLooping"));
 173       break;
 174     case 2: // end
 175       addHeader = false;
 176       addImage = false;
 177       break;
 178     case 3: // cancel
 179       addHeader = false;
 180       addImage = false;
 181       out.cancel();
 182       break;
 183     }
 184   }
 185
 186   @Override
 187   protected void generate() throws IOException {
 188     if (addHeader)
 189       writeHeader();
 190     addHeader = false; // only one header
 191     if (addImage) {
 192       createPalette();
 193       writeGraphicControlExtension();
 194       if (delayTime100ths >= 0 && looping)
 195         writeNetscapeLoopExtension();
 196       writeImage();
 197     }
 198   }
 199
 200   @Override
 201   protected void close() {
 202     if (addTrailer) {
 203       writeTrailer();
 204     } else {
 205       doClose = false;
 206     }
 207     if (capturing)
 208       params.put("captureByteCount", Integer.valueOf(byteCount));
 209   }
 210
 211   //////////////  256-color quantization  //////////////
 212
 213   /**
 214    * a color point in normalized L*a*b space with a flag indicating whether it
 215    * is the background color
 216    */
 217   private class ColorItem extends P3 {
 218     /**
 219          *
 220          */
 221         protected boolean isBackground;
 222
 223     ColorItem(int rgb, boolean isBackground) {
 224       this.isBackground = isBackground;
 225       setT(toLABnorm(rgb));
 226     }
 227   }
 228
 229   /**
 230    * A list of normalized L*a*b points with an index and a center and volume
 231    *
 232    */
 233   private class ColorCell extends Lst<P3> {
 234
 235     /**
 236          *
 237          */
 238         private static final long serialVersionUID = 1L;
 239         protected int index;
 240     protected P3 center;
 241
 242     private float volume;
 243
 244     ColorCell(int index) {
 245       this.index = index;
 246     }
 247
 248     /**
 249      * @param doVisualize
 250      *        debugging only
 251      * @return volume in normalized L*a*b space
 252      */
 253     public float getVolume(boolean doVisualize) {
 254       if (volume != 0)
 255         return volume;
 256       if (size() < 2)
 257         return -1;
 258       //if (true)
 259       //return lst.size();
 260       //float d;
 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;
 267       int n = size();
 268       for (int i = n; --i >= 0;) {
 269         P3 xyz = get(i);
 270         if (xyz.x < minx)
 271           minx = xyz.x;
 272         if (xyz.y < miny)
 273           miny = xyz.y;
 274         if (xyz.z < minz)
 275           minz = xyz.z;
 276         if (xyz.x > maxx)
 277           maxx = xyz.x;
 278         if (xyz.y > maxy)
 279           maxy = xyz.y;
 280         if (xyz.z > maxz)
 281           maxz = xyz.z;
 282       }
 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");
 303       //      }
 304       return volume = dx * dx + dy * dy + dz * dz;
 305     }
 306
 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 + "'" : ""));
 315     //      }
 316
 317     /**
 318      * Set the average normalized L*a*b value for this cell and return its RGB point
 319      *
 320      * @return RGB point
 321      *
 322      */
 323     protected P3 setColor() {
 324       int count = size();
 325       center = new P3();
 326       for (int i = count; --i >= 0;)
 327         center.add(get(i));
 328       center.scale(1f / count);
 329       // Jmol visualization only
 330       //volume = 0;
 331       //getVolume(true);
 332       return toRGB(center);
 333     }
 334
 335     /**
 336      * use median_cut algorithm to split the cell, creating a doubly linked
 337      * list.
 338      *
 339      * Paul Heckbert, MIT thesis COLOR IMAGE QUANTIZATION FOR FRAME BUFFER
 340      * DISPLAY https://www.cs.cmu.edu/~ph/ciq_thesis
 341      *
 342      * except, as in GIMP, we use center (not median) here.
 343      *
 344      * @param cells
 345      * @return true if split
 346      */
 347     protected boolean splitCell(Lst<ColorCell> cells) {
 348       int n = size();
 349       if (n < 2)
 350         return false;
 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;) {
 359           P3 lab = get(i);
 360           float v = (ic == 0 ? lab.x : ic == 1 ? lab.y : lab.z);
 361           if (low > v)
 362             low = v;
 363           if (high < v)
 364             high = v;
 365         }
 366         ranges[0][ic] = low;
 367         ranges[1][ic] = high;
 368         ranges[2][ic] = high - low;
 369       }
 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
 374       switch (mode) {
 375       case 0:
 376         for (int i = n; --i >= 0;)
 377           if (get(i).x >= val)
 378             newCell.addLast(removeItemAt(i));
 379         break;
 380       case 1:
 381         for (int i = n; --i >= 0;)
 382           if (get(i).y >= val)
 383             newCell.addLast(removeItemAt(i));
 384         break;
 385       case 2:
 386         for (int i = size(); --i >= 0;)
 387           if (get(i).z >= val)
 388             newCell.addLast(removeItemAt(i));
 389         break;
 390       }
 391       return true;
 392     }
 393   }
 394
 395   /**
 396    * Quantize all colors and create the final palette;
 397    * replace pixels[] with an array of color indices.
 398    *
 399    */
 400   private void createPalette() {
 401
 402     // catalog all pixel colors
 403
 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++) {
 407       int rgb = pixels[i];
 408       Integer key = Integer.valueOf(rgb);
 409       ColorItem item = ciHash.get(key);
 410       if (item == null) {
 411         item = new ColorItem(rgb, rgb == backgroundColor);
 412         ciHash.put(key, item);
 413         tempColors.addLast(item);
 414       }
 415     }
 416     int nColors = tempColors.size();
 417     System.out.println("GIF total image colors: " + nColors);
 418     ciHash = null;
 419
 420     // create a set of <= 256 color cells
 421
 422     Lst<ColorCell> cells = quantizeColors(tempColors);
 423     nColors = cells.size();
 424     System.out.println("GIF final color count: " + nColors);
 425
 426     // generate the palette and map each cell's rgb color to itself
 427
 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);
 433       colorMap.put(
 434           Integer.valueOf(CU.colorPtToFFRGB(palette[i] = c.setColor())), c);
 435     }
 436
 437     // index all pixels to a pallete color
 438
 439     pixels = indexPixels(cells, colorMap);
 440   }
 441
 442   /**
 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.
 447    *
 448    * It is possible that we will end up with fewer than 256 colors.
 449    *
 450    * @param tempColors
 451    * @return final list of colors
 452    */
 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));
 458     cells.addLast(cc);
 459     cc = new ColorCell(1);
 460     if (n > 256)
 461       cells.addLast(cc);
 462     for (int i = 0; i < n; i++) {
 463       ColorItem c = tempColors.get(i);
 464       if (c.isBackground)
 465         continue;
 466       cc.addLast(c);
 467       if (n <= 256) {
 468         cells.addLast(cc);
 469         cc = new ColorCell(cells.size());
 470       }
 471     }
 472     tempColors.clear();
 473     if (n > 256)
 474       while ((n = cells.size()) < 256) {
 475         float maxVol = 0;
 476         ColorCell maxCell = null;
 477         for (int i = n; --i >= 1;) {
 478           ColorCell c = cells.get(i);
 479           float v = c.getVolume(false);
 480           if (v > maxVol) {
 481             maxVol = v;
 482             maxCell = c;
 483           }
 484         }
 485         if (maxCell == null || !maxCell.splitCell(cells))
 486           break;
 487       }
 488     return cells;
 489   }
 490
 491   /**
 492    *
 493    * Assign all colors to their closest approximation and return an array of
 494    * color indexes.
 495    *
 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.
 499    *
 500    * @param cells
 501    *        quantized color cells
 502    * @param colorMap
 503    *        map of quantized rgb to its cell
 504    * @return array of color indexes, one for each pixel
 505    *
 506    */
 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:
 512     //         p  +1
 513     //   +w-1 +w  +w+1
 514     // so including p as well, we need a total of width + 2 errors.
 515     //
 516     // as p moves through the pixels, we just use mod to cycle through
 517     // this strip.
 518     //
 519     int w2 = width + 2;
 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];
 524     P3 err = new P3();
 525     P3 lab;
 526     int rgb;
 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) {
 532           // leave as 0
 533           continue;
 534         }
 535         P3 pe = errors[p % w2];
 536         if (pe == null || pe.x == Float.MAX_VALUE) {
 537           lab = null;
 538           rgb = pixels[p];
 539         } else {
 540           lab = toLABnorm(pixels[p]);
 541           err = pe;
 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);
 546           lab.add(err);
 547           rgb = CU.colorPtToFFRGB(toRGB(lab));
 548         }
 549         Integer key = Integer.valueOf(rgb);
 550         ColorCell cell = colorMap.get(key);
 551         if (cell == null) {
 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);
 556           if (cell == null) {
 557             // find nearest cell
 558             float maxerr = Float.MAX_VALUE;
 559             // skip 0 0 0
 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();
 564               if (d < maxerr) {
 565                 maxerr = d;
 566                 cell = c;
 567               }
 568             }
 569             nearestCell.put(key, cell);
 570           }
 571           if (floydSteinberg) {
 572             // dither
 573             err.sub2(lab, cell.center);
 574             boolean notLastCol = (j < width - 1);
 575             if (notLastCol)
 576               addError(err, 7, errors, p + 1, w2);
 577             if (notLastRow) {
 578               if (j > 0)
 579                 addError(err, 3, errors, p + width - 1, w2);
 580               addError(err, 5, errors, p + width, w2);
 581               if (notLastCol)
 582                 addError(err, 1, errors, p + width + 1, w2);
 583             }
 584           }
 585           err.x = Float.MAX_VALUE; // used; flag for resetting to 0
 586         }
 587         newPixels[p] = cell.index;
 588       }
 589     }
 590     return newPixels;
 591   }
 592
 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)
 596       return;
 597     p %= w2;
 598     P3 errp = errors[p];
 599     if (errp == null)
 600       errp = errors[p] = new P3();
 601     else if (errp.x == Float.MAX_VALUE) // reuse
 602       errp.set(0, 0, 0);
 603     errp.scaleAdd2(f / 16f, err, errp);
 604   }
 605
 606   ///////////////////////// CIE L*a*b / XYZ / sRGB conversion methods /////////
 607
 608   // these could be static, but that just makes for more JavaScript code
 609
 610   protected P3 toLABnorm(int rgb) {
 611     P3 lab = CU.colorPtFromInt(rgb, null);
 612     rgbToXyz(lab, lab);
 613     xyzToLab(lab, lab);
 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;
 617     return lab;
 618   }
 619
 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;
 625     labToXyz(xyz, xyz);
 626     return xyzToRgb(xyz, xyz);
 627   }
 628
 629   private static M3 xyz2rgb;
 630   private static M3 rgb2xyz;
 631
 632   static {
 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 });
 635
 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 });
 638   }
 639
 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
 643     if (xyz == null)
 644       xyz = new P3();
 645     xyz.x = sxyz(rgb.x);
 646     xyz.y = sxyz(rgb.y);
 647     xyz.z = sxyz(rgb.z);
 648     rgb2xyz.rotate(xyz);
 649     return xyz;
 650   }
 651
 652   private float sxyz(float x) {
 653     x /= 255;
 654     return (float) (x <= 0.04045 ? x / 12.92 : Math.pow(((x + 0.055) / 1.055),
 655         2.4)) * 100;
 656   }
 657
 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
 661     if (rgb == null)
 662       rgb = new P3();
 663     rgb.setT(xyz);
 664     rgb.scale(0.01f);
 665     xyz2rgb.rotate(rgb);
 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);
 669     return rgb;
 670   }
 671
 672   private float srgb(float x) {
 673     return (float) (x > 0.0031308f ? (1.055 * Math.pow(x, 1.0 / 2.4)) - 0.055
 674         : x * 12.92) * 255;
 675   }
 676
 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};
 682     if (lab == null)
 683       lab = new P3();
 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);
 690     return lab;
 691   }
 692
 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 */
 696     );
 697   }
 698
 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};
 703     if (xyz == null)
 704       xyz = new P3();
 705
 706     xyz.setT(lab);
 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;
 713
 714     return xyz;
 715   }
 716
 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 */));
 720   }
 721
 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);
 725   }
 726
 727   ///////////////////////// GifEncoder writing methods ////////////////////////
 728
 729   /**
 730    * includes logical screen descriptor
 731    *
 732    * @throws IOException
 733    */
 734   private void writeHeader() throws IOException {
 735     putString("GIF89a");
 736     putWord(width);
 737     putWord(height);
 738     putByte(0); // no global color table -- using local instead
 739     putByte(0); // no background
 740     putByte(0); // no pixel aspect ratio given
 741   }
 742
 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
 752     }
 753   }
 754
 755   // see  http://www.vurdalakov.net/misc/gif/netscape-looping-application-extension
 756   //      +---------------+
 757   //   0  |     0x21      |  Extension Label
 758   //      +---------------+
 759   //   1  |     0xFF      |  Application Extension Label
 760   //      +---------------+
 761   //   2  |     0x0B      |  Block Size
 762   //      +---------------+
 763   //   3  |               |
 764   //      +-             -+
 765   //   4  |               |
 766   //      +-             -+
 767   //   5  |               |
 768   //      +-             -+
 769   //   6  |               |
 770   //      +-  NETSCAPE   -+  Application Identifier (8 bytes)
 771   //   7  |               |
 772   //      +-             -+
 773   //   8  |               |
 774   //      +-             -+
 775   //   9  |               |
 776   //      +-             -+
 777   //  10  |               |
 778   //      +---------------+
 779   //  11  |               |
 780   //      +-             -+
 781   //  12  |      2.0      |  Application Authentication Code (3 bytes)
 782   //      +-             -+
 783   //  13  |               |
 784   //      +===============+                      --+
 785   //  14  |     0x03      |  Sub-block Data Size   |
 786   //      +---------------+                        |
 787   //  15  |     0x01      |  Sub-block ID          |
 788   //      +---------------+                        | Application Data Sub-block
 789   //  16  |               |                        |
 790   //      +-             -+  Loop Count (2 bytes)  |
 791   //  17  |               |                        |
 792   //      +===============+                      --+
 793   //  18  |     0x00      |  Block Terminator
 794   //      +---------------+
 795
 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");
 801     putByte(3);
 802     putByte(1);
 803     putWord(0); // loop indefinitely
 804     putByte(0); // end-of-block
 805
 806   }
 807
 808   private int initCodeSize;
 809   private int curpt;
 810
 811   private void writeImage() {
 812     putByte(0x2C);
 813     putWord(0); //left
 814     putWord(0); //top
 815     putWord(width);
 816     putWord(height);
 817
 818     //    <Packed Fields>  =      LISx xZZZ
 819
 820     //    L Local Color Table Flag
 821     //    I Interlace Flag
 822     //    S Sort Flag
 823     //    x Reserved
 824     //    ZZZ Size of Local Color Table
 825
 826     int packedFields = 0x80 | (interlaced ? 0x40 : 0) | (bitsPerPixel - 1);
 827     putByte(packedFields);
 828     int colorMapSize = 1 << bitsPerPixel;
 829     P3 p = new P3();
 830     for (int i = 0; i < colorMapSize; i++) {
 831       if (palette[i] != null)
 832         p = palette[i];
 833       putByte((int) p.x);
 834       putByte((int) p.y);
 835       putByte((int) p.z);
 836     }
 837     putByte(initCodeSize = (bitsPerPixel <= 1 ? 2 : bitsPerPixel));
 838     compress();
 839     putByte(0);
 840   }
 841
 842   private void writeTrailer() {
 843     // Write the GIF file terminator
 844     putByte(0x3B);
 845   }
 846
 847   ///// compression routines /////
 848
 849   private static final int EOF = -1;
 850
 851   // Return the next pixel from the image
 852   private int nextPixel() {
 853     if (countDown-- == 0)
 854       return EOF;
 855     int colorIndex = pixels[curpt];
 856     // Bump the current X position
 857     ++curx;
 858     if (curx == width) {
 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.
 862       curx = 0;
 863       if (interlaced)
 864         updateY(INTERLACE_PARAMS[pass], INTERLACE_PARAMS[pass + 4]);
 865       else
 866         ++cury;
 867     }
 868     curpt = cury * width + curx;
 869     return colorIndex & 0xff;
 870   }
 871
 872   private static final int[] INTERLACE_PARAMS = { 8, 8, 4, 2, 4, 2, 1, 0 };
 873
 874   /**
 875    *
 876    * Group 1 : Every 8th. row, starting with row 0. (Pass 1)
 877    *
 878    * Group 2 : Every 8th. row, starting with row 4. (Pass 2)
 879    *
 880    * Group 3 : Every 4th. row, starting with row 2. (Pass 3)
 881    *
 882    * Group 4 : Every 2nd. row, starting with row 1. (Pass 4)
 883    *
 884    * @param yNext
 885    * @param yNew
 886    */
 887   private void updateY(int yNext, int yNew) {
 888     cury += yNext;
 889     if (yNew >= 0 && cury >= height) {
 890       cury = yNew;
 891       ++pass;
 892     }
 893   }
 894
 895   // Write out a word to the GIF file
 896   private void putWord(int w) {
 897     putByte(w);
 898     putByte(w >> 8);
 899   }
 900
 901   // GIFCOMPR.C       - GIF Image compression routines
 902   //
 903   // Lempel-Ziv compression based on 'compress'.  GIF modifications by
 904   // David Rowley (mgardi@watdcsu.waterloo.edu)
 905
 906   // General DEFINEs
 907
 908   private static final int BITS = 12;
 909
 910   private static final int HSIZE = 5003; // 80% occupancy
 911
 912   // GIF Image compression - modified 'compress'
 913   //
 914   // Based on: compress.c - File compression ala IEEE Computer, June 1984.
 915   //
 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)
 922
 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
 927
 928   private final static int MAXCODE(int nBits) {
 929     return (1 << nBits) - 1;
 930   }
 931
 932   private int[] htab = new int[HSIZE];
 933   private int[] codetab = new int[HSIZE];
 934
 935   private int hsize = HSIZE; // for dynamic table sizing
 936
 937   private int freeEnt = 0; // first unused entry
 938
 939   // block compression parameters -- after all codes are used up,
 940   // and compression rate changes, start over.
 941   private boolean clearFlag = false;
 942
 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.
 954
 955   private int clearCode;
 956   private int EOFCode;
 957
 958   private int countDown;
 959   private int pass = 0;
 960   private int curx, cury;
 961
 962   private void compress() {
 963
 964     // Calculate number of bits we are expecting
 965     countDown = width * height;
 966
 967     // Indicate which pass we are on (if interlace)
 968     pass = 0;
 969     // Set up the current x and y position
 970     curx = 0;
 971     cury = 0;
 972
 973     // Set up the necessary values
 974     clearFlag = false;
 975     nBits = initCodeSize + 1;
 976     maxcode = MAXCODE(nBits);
 977
 978     clearCode = 1 << initCodeSize;
 979     EOFCode = clearCode + 1;
 980     freeEnt = clearCode + 2;
 981
 982     // Set up the 'byte output' routine
 983     bufPt = 0;
 984
 985     int ent = nextPixel();
 986
 987     int hshift = 0;
 988     int fcode;
 989     for (fcode = hsize; fcode < 65536; fcode *= 2)
 990       ++hshift;
 991     hshift = 8 - hshift; // set hash code range bound
 992
 993     int hsizeReg = hsize;
 994     clearHash(hsizeReg); // clear hash table
 995
 996     output(clearCode);
 997
 998     int c;
 999     outer_loop: while ((c = nextPixel()) != EOF) {
1000       fcode = (c << maxbits) + ent;
1001       int i = (c << hshift) ^ ent; // xor hashing
1002
1003       if (htab[i] == fcode) {
1004         ent = codetab[i];
1005         continue;
1006       } else if (htab[i] >= 0) // non-empty slot
1007       {
1008         int disp = hsizeReg - i; // secondary hash (after G. Knott)
1009         if (i == 0)
1010           disp = 1;
1011         do {
1012           if ((i -= disp) < 0)
1013             i += hsizeReg;
1014
1015           if (htab[i] == fcode) {
1016             ent = codetab[i];
1017             continue outer_loop;
1018           }
1019         } while (htab[i] >= 0);
1020       }
1021       output(ent);
1022       ent = c;
1023       if (freeEnt < maxmaxcode) {
1024         codetab[i] = freeEnt++; // code -> hashtable
1025         htab[i] = fcode;
1026       } else {
1027         clearBlock();
1028       }
1029     }
1030     // Put out the final code.
1031     output(ent);
1032     output(EOFCode);
1033   }
1034
1035   // output
1036   //
1037   // Output the given code.
1038   // Inputs:
1039   //      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
1040   //              that n_bits =< wordsize - 1.
1041   // Outputs:
1042   //      Outputs code to the file.
1043   // Assumptions:
1044   //      Chars are 8 bits long.
1045   // Algorithm:
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.
1049
1050   private int curAccum = 0;
1051   private int curBits = 0;
1052
1053   private int masks[] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000F, 0x001F,
1054       0x003F, 0x007F, 0x00FF, 0x01FF, 0x03FF, 0x07FF, 0x0FFF, 0x1FFF, 0x3FFF,
1055       0x7FFF, 0xFFFF };
1056
1057   private void output(int code) {
1058     curAccum &= masks[curBits];
1059
1060     if (curBits > 0)
1061       curAccum |= (code << curBits);
1062     else
1063       curAccum = code;
1064
1065     curBits += nBits;
1066
1067     while (curBits >= 8) {
1068       byteOut((byte) (curAccum & 0xff));
1069       curAccum >>= 8;
1070       curBits -= 8;
1071     }
1072
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) {
1076       if (clearFlag) {
1077         maxcode = MAXCODE(nBits = initCodeSize + 1);
1078         clearFlag = false;
1079       } else {
1080         ++nBits;
1081         if (nBits == maxbits)
1082           maxcode = maxmaxcode;
1083         else
1084           maxcode = MAXCODE(nBits);
1085       }
1086     }
1087
1088     if (code == EOFCode) {
1089       // At EOF, write the rest of the buffer.
1090       while (curBits > 0) {
1091         byteOut((byte) (curAccum & 0xff));
1092         curAccum >>= 8;
1093         curBits -= 8;
1094       }
1095       flushBytes();
1096     }
1097   }
1098
1099   // Clear out the hash table
1100
1101   // table clear for block compress
1102   private void clearBlock() {
1103     clearHash(hsize);
1104     freeEnt = clearCode + 2;
1105     clearFlag = true;
1106
1107     output(clearCode);
1108   }
1109
1110   // reset code table
1111   private void clearHash(int hsize) {
1112     for (int i = 0; i < hsize; ++i)
1113       htab[i] = -1;
1114   }
1115
1116   // GIF-specific routines (byte array buffer)
1117
1118   // Number of bytes so far in this 'packet'
1119   private int bufPt;
1120
1121   // Define the storage for the packet accumulator
1122   final private byte[] buf = new byte[256];
1123
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) {
1127     buf[bufPt++] = c;
1128     if (bufPt >= 254)
1129       flushBytes();
1130   }
1131
1132   // Flush the packet to disk, and reset the accumulator
1133   protected void flushBytes() {
1134     if (bufPt > 0) {
1135       putByte(bufPt);
1136       out.write(buf, 0, bufPt);
1137       byteCount += bufPt;
1138       bufPt = 0;
1139     }
1140   }
1141
1142 }