001    /*
002     * GIFCodec
003     *
004     * Copyright (c) 2002, 2003, 2004 Marco Schmidt.
005     * All rights reserved.
006     */
007    
008    package net.sourceforge.jiu.codecs;
009    
010    import java.io.DataOutput;
011    import java.io.IOException;
012    import net.sourceforge.jiu.codecs.ImageCodec;
013    import net.sourceforge.jiu.codecs.UnsupportedTypeException;
014    import net.sourceforge.jiu.data.BilevelImage;
015    import net.sourceforge.jiu.data.Gray8Image;
016    import net.sourceforge.jiu.data.IntegerImage;
017    import net.sourceforge.jiu.data.Paletted8Image;
018    import net.sourceforge.jiu.data.PixelImage;
019    import net.sourceforge.jiu.data.Palette;
020    import net.sourceforge.jiu.data.RGBIndex;
021    import net.sourceforge.jiu.ops.MissingParameterException;
022    import net.sourceforge.jiu.ops.OperationFailedException;
023    import net.sourceforge.jiu.ops.WrongParameterException;
024    
025    /**
026     * A codec to write Compuserve GIF (Graphics Interchange Format) files.
027     * <p>
028     * Only writing GIF files is supported right now.
029     * Reading GIF files with JIU can be done with the {@link net.sourceforge.jiu.gui.awt.ToolkitLoader}
030     * class which uses the image reader built into the Java runtime library ({@link java.awt.Toolkit} class).
031     * That reader has supported GIF since Java 1.0.
032     * <h3>Supported image types</h3>
033     * When saving, classes implementing the following image data interfaces
034     * are supported: 
035     * {@link net.sourceforge.jiu.data.BilevelImage},
036     * {@link net.sourceforge.jiu.data.Gray8Image} and
037     * {@link net.sourceforge.jiu.data.Paletted8Image}.
038     * GIF only supports up to 256 colors in an image, so
039     * you will have to use one of the quantization classes to reduce
040     * a truecolor image to 256 or less colors before you can save it
041     * with this codec.
042     * <h3>Supported I/O classes</h3>
043     * This codec supports {@link java.io.OutputStream}, {@link java.io.DataOutput} 
044     * and  {@link java.io.RandomAccessFile}.
045     * <h3>Bounds</h3>
046     * {@link net.sourceforge.jiu.codecs.ImageCodec}'s bounds concept is supported.
047     * A user of this codec can specify a rectangular part of the input image
048     * that will be saved instead of the complete image.
049     * <h3>Comments</h3>
050     * GIF - at least in its 89a version - allows for the inclusion of textual
051     * comments.
052     * When saving an image to a GIF file, each comment given to a codec
053     * will be stored in a comment extension block of its own.
054     * <h3>Usage example</h3>
055     * Save an image using this codec:
056     * <pre>
057     * GIFCodec codec = new GIFCodec();
058     * codec.appendComment("Bob and Susan at the Munich airport (2002-06-13).");
059     * codec.setImage(image); // BilevelImage, Gray8Image or Paletted8Image
060     * codec.setInterlacing(true);
061     * codec.setFile("output.gif", CodecMode.SAVE);
062     * codec.process();
063     * </pre>
064     * <h3>Interlaced storage</h3>
065     * This codec allows creating interlaced and non-interlaced GIF files.
066     * The default is non-interlaced storage.
067     * Non-interlaced files store the rows top-to-bottom.
068     * <p>
069     * Interlaced files store the image in four passes, progressively adding 
070     * rows until the complete image is stored.
071     * When decoding, the progressive display of interlaced files makes it
072     * supposedly quicker to find out what's displayed in the image.
073     * <p>
074     * On the other hand, transmission typically takes longer, because interlacing
075     * often leads to slightly larger files.
076     * When using interlaced mode, lines that get stored one after another
077     * have some room between them in the image, so there are less similarities
078     * between consecutive lines, which worsens compression ratio (compression
079     * works better with a lot of similarities in the data to be compressed).
080     * <h3>GIF versions</h3>
081     * There are two versions of GIF, 87a and 89a.
082     * In 89a, several things were added to the file format specification.
083     * From the 89a features this codec only uses the possibility of storing textual comments
084     * in GIF files.
085     * Thus, the version used for writing depends on the return value of 
086     * {@link #getNumComments()}.
087     * If there is at least one comment to be written to the file, version 89a
088     * will be used, 87a otherwise.
089     * <h3>Licensing of the LZW algorithm</h3>
090     * Unisys Corp. had a patent in several countries on the LZW algorithm used within GIF.
091     * However, this patent has expired (Japan being the last country 
092     * where the patent expired, on July 7th 2004)  so that LZW can be used freely. 
093     * <h3>Licensing of the file format</h3>
094     * GIF was defined by Compuserve.
095     * In a technical document file called <code>Gif89a.txt</code> that I found 
096     * somewhere on the Net they grant a royalty-free license for use of the
097     * format to anyone - in order to improve the popularity of the format, I guess.
098     * I don't think that it should be possible to put a file format under a copyright,
099     * but all that Compuserve asks for in exchange for freely using the format
100     * is the inclusion of a message.
101     * So, here is that message:
102     * <blockquote>
103     * "The Graphics Interchange Format(c) is the Copyright property of
104     *  CompuServe Incorporated. GIF(sm) is a Service Mark property of
105     *  CompuServe Incorporated."
106     * </blockquote>
107     * <h3>File format background</h3>
108     * I've compiled a web page with  
109     * <a target="_top" href="http://www.geocities.com/marcoschmidt.geo/gif-image-file-format.html">technical
110     * information on GIF </a>.
111     * @author Marco Schmidt
112     */
113    public class GIFCodec extends ImageCodec
114    {
115            private static final int CODE_ARRAY_LENGTH = 5020;
116            private static final int[] INTERLACING_FIRST_ROW = {0, 4, 2, 1};
117            private static final int[] INTERLACING_INCREMENT = {8, 8, 4, 2};
118            private static final int NUM_INTERLACING_PASSES = 4;
119            private static final byte[] MAGIC_GIF87A = {71, 73, 70, 56, 55, (byte)97};
120            private static final byte[] MAGIC_GIF89A = {71, 73, 70, 56, 57, (byte)97};
121            private int backgroundColor;
122            private byte[] block;
123            private int bitOffset;
124            private int bitsPerPixel;
125            private int blockLength;
126            private int clearCode;
127            private int codeSize;
128            private int[] currentCode;
129            private int currentColumn;
130            private int currentInterlacingPass;
131            private int currentRow;
132            private int endOfInformationCode;
133            private boolean notFinished;
134            private int firstFreeCode;
135            private int freeCode;
136            private IntegerImage imageToBeSaved;
137            private int initialCodeSize;
138            private boolean interlaced;
139            private int height;
140            private int maxCode;
141            private int[] newCode;
142            private int[] oldCode;
143            private DataOutput out;
144            private int processedRows;
145            private int width;
146    
147            /**
148             * Returns the index of the background color.
149             * @return int value with the color (index into the palette) of the background color
150             * @see #setBackgroundColor
151             */
152            public int getBackgroundColor()
153            {
154                    return backgroundColor;
155            }
156    
157            public String[] getFileExtensions()
158            {
159                    return new String[] {".gif"};
160            }
161    
162            public String getFormatName()
163            {
164                    return "Compuserve GIF";
165            }
166    
167            public String[] getMimeTypes()
168            {
169                    return new String[] {"image/gif"};
170            }
171    
172            private int getNextSample()
173            {
174                    int result = imageToBeSaved.getSample(currentColumn++, currentRow);
175                    if (currentColumn > getBoundsX2())
176                    {
177                            setProgress(processedRows++, getBoundsHeight());
178                            currentColumn = getBoundsX1();
179                            if (isInterlaced())
180                            {
181                                    currentRow += INTERLACING_INCREMENT[currentInterlacingPass];
182                                    boolean done;
183                                    do
184                                    {
185                                            if (currentRow > getBoundsY2())
186                                            {
187                                                    currentInterlacingPass++;
188                                                    if (currentInterlacingPass < NUM_INTERLACING_PASSES)
189                                                    {
190                                                            currentRow = getBoundsY1() + INTERLACING_FIRST_ROW[currentInterlacingPass];
191                                                    }
192                                            }
193                                            done = currentRow <= getBoundsY2() || currentInterlacingPass > NUM_INTERLACING_PASSES;
194                                    }
195                                    while (!done);
196                            }
197                            else
198                            {
199                                    currentRow++;
200                            }
201                            notFinished = processedRows < getBoundsHeight();
202                    }
203                    return result;
204            }
205    
206            private void initEncoding() throws IOException
207            {
208                    imageToBeSaved = (IntegerImage)getImage();
209                    currentColumn = getBoundsX1();
210                    currentRow = getBoundsY1();
211                    processedRows = 0;
212                    currentInterlacingPass = 0;
213                    notFinished = true;
214                    block = new byte[255];
215                    currentCode = new int[CODE_ARRAY_LENGTH];
216                    newCode = new int[CODE_ARRAY_LENGTH];
217                    oldCode = new int[CODE_ARRAY_LENGTH];
218                    if (bitsPerPixel == 1)
219                    {
220                            initialCodeSize = 2;
221                    }
222                    else
223                    {
224                            initialCodeSize = bitsPerPixel;
225                    }
226            }
227    
228            /**
229             * Returns if the image is or will be stored in interlaced (<code>true</code>) 
230             * or non-interlaced mode (<code>false</code>).
231             * @return interlacing mode
232             * @see #setInterlacing
233             */
234            public boolean isInterlaced()
235            {
236                    return interlaced;
237            }
238    
239            public boolean isLoadingSupported()
240            {
241                    return false;
242            }
243    
244            public boolean isSavingSupported()
245            {
246                    return true;
247            }
248    
249            public void process() throws 
250                    MissingParameterException, 
251                    OperationFailedException
252            {
253                    initModeFromIOObjects();
254                    if (getMode() == CodecMode.LOAD)
255                    {
256                            throw new OperationFailedException("Loading is not supported.");
257                    }
258                    else
259                    {
260                            save();
261                    }
262            }
263    
264            private void resetBlock()
265            {
266                    for (int i = 0; i < block.length; i++)
267                    {
268                            block[i] = 0;
269                    }
270                    blockLength = 0;
271                    bitOffset = 0;
272            }
273    
274            private void resetEncoder()
275            {
276                    codeSize = initialCodeSize + 1;
277                    clearCode = 1 << initialCodeSize;
278                    endOfInformationCode = clearCode + 1;
279                    freeCode = endOfInformationCode + 1;
280                    firstFreeCode = freeCode;
281                    maxCode = (1 << codeSize) - 1;
282                    for (int i = 0; i < currentCode.length; i++)
283                    {
284                            currentCode[i] = 0;
285                    }
286            }
287    
288            private void save() throws
289                    MissingParameterException, 
290                    OperationFailedException, 
291                    UnsupportedTypeException,
292                    WrongParameterException
293            {
294                    PixelImage image = getImage();
295                    if (image == null)
296                    {
297                            throw new MissingParameterException("No image available for saving.");
298                    }
299                    width = image.getWidth();
300                    height = image.getHeight();
301                    setBoundsIfNecessary(width, height);
302                    width = getBoundsWidth();
303                    height = getBoundsHeight();
304                    if (image instanceof Paletted8Image)
305                    {
306                            Palette palette = ((Paletted8Image)image).getPalette();
307                            int numEntries = palette.getNumEntries();
308                            if (numEntries < 1 || numEntries > 256)
309                            {
310                                    throw new WrongParameterException("Palette of image to be saved must have 1..256 entries.");
311                            }
312                            bitsPerPixel = 8;
313                            for (int i = 1; i <= 8; i++)
314                            {
315                                    if ((1 << i) >= numEntries)
316                                    {
317                                            bitsPerPixel = i;
318                                            break;
319                                    }
320                            }
321                    }
322                    else
323                    if (image instanceof Gray8Image)
324                    {
325                            bitsPerPixel = 8;
326                    }
327                    else
328                    if (image instanceof BilevelImage)
329                    {
330                            bitsPerPixel = 1;
331                    }
332                    else
333                    {
334                            throw new UnsupportedTypeException("Unsupported image type: " + image.getClass().getName());
335                    }
336                    out = getOutputAsDataOutput();
337                    if (out == null)
338                    {
339                            throw new MissingParameterException("Output stream / random access file parameter missing.");
340                    }
341                    // now write the output stream
342                    try
343                    {
344                            writeStream();
345                    }
346                    catch (IOException ioe)
347                    {
348                            throw new OperationFailedException("I/O failure: " + ioe.toString());
349                    }
350            }
351    
352            /**
353             * Specify the value of the background color.
354             * Default is <code>0</code>.
355             * @param colorIndex int value with the color (index into the palette) of the background color
356             * @see #getBackgroundColor
357             */
358            public void setBackgroundColor(int colorIndex)
359            {
360                    backgroundColor = colorIndex;
361            }
362    
363            /**
364             * Specifies whether the image will be stored in interlaced mode
365             * (<code>true</code>) or non-interlaced mode (<code>false</code>).
366             * @param useInterlacing boolean, if true interlaced mode, otherwise non-interlaced mode
367             * @see #isInterlaced()
368             */
369            public void setInterlacing(boolean useInterlacing)
370            {
371                    interlaced = useInterlacing;
372            }
373    
374            private void writeBlock() throws IOException
375            {
376                    if (bitOffset > 0)
377                    {
378                            blockLength++;
379                    }
380                    if (blockLength == 0)
381                    {
382                            return;
383                    }
384                    out.write(blockLength);
385                    out.write(block, 0, blockLength);
386                    resetBlock();
387            }
388    
389            private void writeCode(int code) throws IOException
390            {
391                    int remainingBits = codeSize;
392                    do
393                    {
394                            int bitsFree = 8 - bitOffset;
395                            int bits; 
396                            /* bits =>  number of bits to be copied from "code" to 
397                               "block[blockLength]" in this loop iteration */
398                            if (bitsFree < remainingBits)
399                            {
400                                    bits = bitsFree;
401                            }
402                            else
403                            {
404                                    bits = remainingBits;
405                            }
406                            int value = block[blockLength] & 0xff;
407                            value += (code & ((1 << bits) - 1)) << bitOffset;
408                            block[blockLength] = (byte)value;
409                            bitOffset += bits;
410                            if (bitOffset == 8)
411                            {
412                                    blockLength++;
413                                    bitOffset = 0;
414                                    if (blockLength == 255)
415                                    {
416                                            writeBlock();
417                                    }
418                            }
419                            code >>= bits;
420                            remainingBits -= bits;
421                    }
422                    while (remainingBits != 0);
423            }
424    
425            private void writeComments() throws IOException
426            {
427                    if (getNumComments() < 1)
428                    {
429                            return;
430                    }
431                    for (int commentIndex = 0; commentIndex < getNumComments(); commentIndex++)
432                    {
433                            String comment = getComment(commentIndex);
434                            byte[] data = comment.getBytes();
435                            out.write(0x21); // extension introducer
436                            out.write(0xfe); // comment label
437                            int offset = 0;
438                            while (offset < data.length)
439                            {
440                                    int number = Math.min(data.length - offset, 255);
441                                    out.write(number);
442                                    out.write(data, offset, number);
443                                    offset += number;
444                            }
445                            out.write(0); // zero-length block
446                    }
447            }
448    
449            /**
450             * Writes a global header, a global palette and
451             * an image descriptor to output.
452             */
453            private void writeHeader() throws IOException
454            {
455                    // pick a GIF version; stay with 87a if possible (no comments included
456                    // which require 89a)
457                    byte[] magic;
458                    if (getNumComments() > 0)
459                    {
460                            magic = MAGIC_GIF89A;
461                    }
462                    else
463                    {
464                            magic = MAGIC_GIF87A;
465                    }
466                    // global header
467                    out.write(magic);
468                    writeShort(width);
469                    writeShort(height);
470                    int depth = bitsPerPixel - 1;
471                    /* meaning of packed byte
472                       128 => there is a global palette following
473                       (depth << 4) => the number of bits used for encoding
474                       depth - 1 => the number of bits in the global palette (same as for encoding) */
475                    int packed = 128 | (depth << 4) | depth;
476                    out.write(packed);
477                    out.write(backgroundColor);
478                    int pixelAspectRatio = 0;
479                    out.write(pixelAspectRatio);
480    
481                    // global palette
482                    writePalette();
483    
484                    // write textual comments (if any) to file as extension blocks
485                    writeComments();
486    
487                    // image descriptor
488                    out.write(44); // comma
489                    writeShort(0); // x1
490                    writeShort(0); // y1
491                    writeShort(width); // width
492                    writeShort(height); // height
493                    packed = 0;
494                    if (isInterlaced())
495                    {
496                            packed |= 64;
497                    }
498                    out.write(packed); // flags
499            }
500    
501            private void writeImage() throws IOException
502            {
503                    out.write(initialCodeSize);
504                    resetBlock();
505                    resetEncoder();
506                    writeCode(clearCode);
507                    int suffixChar = getNextSample();
508                    int prefixCode = suffixChar;
509                    do
510                    {
511                            suffixChar = getNextSample();
512                            int d = 1;
513                            int hashIndex = (prefixCode ^ (suffixChar << 5)) % 5003;
514                            boolean endInnerLoop;
515                            do
516                            {
517                                    if (currentCode[hashIndex] == 0)
518                                    {
519                                            writeCode(prefixCode);
520                                            d = freeCode;
521                                            if (freeCode <= 4095)
522                                            {
523                                                    oldCode[hashIndex] = prefixCode;
524                                                    newCode[hashIndex] = suffixChar;
525                                                    currentCode[hashIndex] = freeCode;
526                                                    freeCode++;
527                                            }
528                                            if (d > maxCode)
529                                            {
530                                                    if (codeSize < 12)
531                                                    {
532                                                            codeSize++;
533                                                            maxCode = (1 << codeSize) - 1;
534                                                    }
535                                                    else
536                                                    {
537                                                            writeCode(clearCode);
538                                                            resetEncoder();
539                                                    }
540                                            }
541                                            prefixCode = suffixChar;
542                                            break;
543                                    }
544                                    if (oldCode[hashIndex] == prefixCode && newCode[hashIndex] == suffixChar)
545                                    {
546                                            prefixCode= currentCode[hashIndex];
547                                            endInnerLoop = true;
548                                    }
549                                    else
550                                    {
551                                            hashIndex += d;
552                                            d += 2;
553                                            if (hashIndex > 5003)
554                                            {
555                                                    hashIndex -= 5003;
556                                            }
557                                            endInnerLoop = false;
558                                    }
559                            }
560                            while (!endInnerLoop);
561                    }
562                    while (notFinished);
563                    writeCode(prefixCode);
564                    writeCode(endOfInformationCode);
565                    writeBlock();
566            }
567    
568            private void writePalette() throws IOException
569            {
570                    PixelImage image = getImage();
571                    if (image instanceof Paletted8Image)
572                    {
573                            Palette palette = ((Paletted8Image)image).getPalette();
574                            int numEntries = 1 << bitsPerPixel;
575                            for (int i = 0; i < numEntries; i++)
576                            {
577                                    if (i < palette.getNumEntries())
578                                    {
579                                            out.write(palette.getSample(RGBIndex.INDEX_RED, i));
580                                            out.write(palette.getSample(RGBIndex.INDEX_GREEN, i));
581                                            out.write(palette.getSample(RGBIndex.INDEX_BLUE, i));
582                                    }
583                                    else
584                                    {
585                                            out.write(0);
586                                            out.write(0);
587                                            out.write(0);
588                                    }
589                            }
590                    }
591                    else
592                    if (image instanceof Gray8Image)
593                    {
594                            for (int i = 0; i < 256; i++)
595                            {
596                                    out.write(i);
597                                    out.write(i);
598                                    out.write(i);
599                            }
600                    }
601                    else
602                    if (image instanceof BilevelImage)
603                    {
604                            out.write(0);
605                            out.write(0);
606                            out.write(0);
607                            out.write(255);
608                            out.write(255);
609                            out.write(255);
610                    }
611            }
612    
613            private void writeShort(int value) throws IOException
614            {
615                    out.write(value & 0xff);
616                    out.write((value >> 8) & 0xff);
617            }
618    
619            private void writeStream() throws IOException
620            {
621                    initEncoding();
622                    writeHeader();
623                    writeImage();
624                    writeTrailer();
625            }
626    
627            private void writeTrailer() throws IOException
628            {
629                    out.write(0); // zero-length block
630                    out.write(59); // semicolon
631            }
632    }