Home | History | Annotate | Download | only in gifencoder
      1 package com.bumptech.glide.gifencoder;
      2 
      3 import java.io.IOException;
      4 import java.io.OutputStream;
      5 
      6 // ==============================================================================
      7 // Adapted from Jef Poskanzer's Java port by way of J. M. G. Elliott.
      8 // K Weiner 12/00
      9 
     10 class LZWEncoder {
     11 
     12     private static final int EOF = -1;
     13 
     14     private int imgW, imgH;
     15 
     16     private byte[] pixAry;
     17 
     18     private int initCodeSize;
     19 
     20     private int remaining;
     21 
     22     private int curPixel;
     23 
     24     // GIFCOMPR.C - GIF Image compression routines
     25     //
     26     // Lempel-Ziv compression based on 'compress'. GIF modifications by
     27     // David Rowley (mgardi (at) watdcsu.waterloo.edu)
     28 
     29     // General DEFINEs
     30 
     31     static final int BITS = 12;
     32 
     33     static final int HSIZE = 5003; // 80% occupancy
     34 
     35     // GIF Image compression - modified 'compress'
     36     //
     37     // Based on: compress.c - File compression ala IEEE Computer, June 1984.
     38     //
     39     // By Authors: Spencer W. Thomas (decvax!harpo!utah-cs!utah-gr!thomas)
     40     // Jim McKie (decvax!mcvax!jim)
     41     // Steve Davies (decvax!vax135!petsd!peora!srd)
     42     // Ken Turkowski (decvax!decwrl!turtlevax!ken)
     43     // James A. Woods (decvax!ihnp4!ames!jaw)
     44     // Joe Orost (decvax!vax135!petsd!joe)
     45 
     46     int n_bits; // number of bits/code
     47 
     48     int maxbits = BITS; // user settable max # bits/code
     49 
     50     int maxcode; // maximum code, given n_bits
     51 
     52     int maxmaxcode = 1 << BITS; // should NEVER generate this code
     53 
     54     int[] htab = new int[HSIZE];
     55 
     56     int[] codetab = new int[HSIZE];
     57 
     58     int hsize = HSIZE; // for dynamic table sizing
     59 
     60     int free_ent = 0; // first unused entry
     61 
     62     // block compression parameters -- after all codes are used up,
     63     // and compression rate changes, start over.
     64     boolean clear_flg = false;
     65 
     66     // Algorithm: use open addressing double hashing (no chaining) on the
     67     // prefix code / next character combination. We do a variant of Knuth's
     68     // algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
     69     // secondary probe. Here, the modular division first probe is gives way
     70     // to a faster exclusive-or manipulation. Also do block compression with
     71     // an adaptive reset, whereby the code table is cleared when the compression
     72     // ratio decreases, but after the table fills. The variable-length output
     73     // codes are re-sized at this point, and a special CLEAR code is generated
     74     // for the decompressor. Late addition: construct the table according to
     75     // file size for noticeable speed improvement on small files. Please direct
     76     // questions about this implementation to ames!jaw.
     77 
     78     int g_init_bits;
     79 
     80     int ClearCode;
     81 
     82     int EOFCode;
     83 
     84     // output
     85     //
     86     // Output the given code.
     87     // Inputs:
     88     // code: A n_bits-bit integer. If == -1, then EOF. This assumes
     89     // that n_bits =< wordsize - 1.
     90     // Outputs:
     91     // Outputs code to the file.
     92     // Assumptions:
     93     // Chars are 8 bits long.
     94     // Algorithm:
     95     // Maintain a BITS character long buffer (so that 8 codes will
     96     // fit in it exactly). Use the VAX insv instruction to insert each
     97     // code in turn. When the buffer fills up empty it and start over.
     98 
     99     int cur_accum = 0;
    100 
    101     int cur_bits = 0;
    102 
    103     int masks[] = {0x0000, 0x0001, 0x0003, 0x0007, 0x000F, 0x001F, 0x003F, 0x007F, 0x00FF, 0x01FF,
    104             0x03FF, 0x07FF, 0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF};
    105 
    106     // Number of characters so far in this 'packet'
    107     int a_count;
    108 
    109     // Define the storage for the packet accumulator
    110     byte[] accum = new byte[256];
    111 
    112     // ----------------------------------------------------------------------------
    113     LZWEncoder(int width, int height, byte[] pixels, int color_depth) {
    114         imgW = width;
    115         imgH = height;
    116         pixAry = pixels;
    117         initCodeSize = Math.max(2, color_depth);
    118     }
    119 
    120     // Add a character to the end of the current packet, and if it is 254
    121     // characters, flush the packet to disk.
    122     void char_out(byte c, OutputStream outs) throws IOException {
    123         accum[a_count++] = c;
    124         if (a_count >= 254)
    125             flush_char(outs);
    126     }
    127 
    128     // Clear out the hash table
    129 
    130     // table clear for block compress
    131     void cl_block(OutputStream outs) throws IOException {
    132         cl_hash(hsize);
    133         free_ent = ClearCode + 2;
    134         clear_flg = true;
    135 
    136         output(ClearCode, outs);
    137     }
    138 
    139     // reset code table
    140     void cl_hash(int hsize) {
    141         for (int i = 0; i < hsize; ++i)
    142             htab[i] = -1;
    143     }
    144 
    145     void compress(int init_bits, OutputStream outs) throws IOException {
    146         int fcode;
    147         int i /* = 0 */;
    148         int c;
    149         int ent;
    150         int disp;
    151         int hsize_reg;
    152         int hshift;
    153 
    154         // Set up the globals: g_init_bits - initial number of bits
    155         g_init_bits = init_bits;
    156 
    157         // Set up the necessary values
    158         clear_flg = false;
    159         n_bits = g_init_bits;
    160         maxcode = MAXCODE(n_bits);
    161 
    162         ClearCode = 1 << (init_bits - 1);
    163         EOFCode = ClearCode + 1;
    164         free_ent = ClearCode + 2;
    165 
    166         a_count = 0; // clear packet
    167 
    168         ent = nextPixel();
    169 
    170         hshift = 0;
    171         for (fcode = hsize; fcode < 65536; fcode *= 2)
    172             ++hshift;
    173         hshift = 8 - hshift; // set hash code range bound
    174 
    175         hsize_reg = hsize;
    176         cl_hash(hsize_reg); // clear hash table
    177 
    178         output(ClearCode, outs);
    179 
    180         outer_loop:
    181         while ((c = nextPixel()) != EOF) {
    182             fcode = (c << maxbits) + ent;
    183             i = (c << hshift) ^ ent; // xor hashing
    184 
    185             if (htab[i] == fcode) {
    186                 ent = codetab[i];
    187                 continue;
    188             } else if (htab[i] >= 0) // non-empty slot
    189             {
    190                 disp = hsize_reg - i; // secondary hash (after G. Knott)
    191                 if (i == 0)
    192                     disp = 1;
    193                 do {
    194                     if ((i -= disp) < 0)
    195                         i += hsize_reg;
    196 
    197                     if (htab[i] == fcode) {
    198                         ent = codetab[i];
    199                         continue outer_loop;
    200                     }
    201                 } while (htab[i] >= 0);
    202             }
    203             output(ent, outs);
    204             ent = c;
    205             if (free_ent < maxmaxcode) {
    206                 codetab[i] = free_ent++; // code -> hashtable
    207                 htab[i] = fcode;
    208             } else
    209                 cl_block(outs);
    210         }
    211         // Put out the final code.
    212         output(ent, outs);
    213         output(EOFCode, outs);
    214     }
    215 
    216     // ----------------------------------------------------------------------------
    217     void encode(OutputStream os) throws IOException {
    218         os.write(initCodeSize); // write "initial code size" byte
    219 
    220         remaining = imgW * imgH; // reset navigation variables
    221         curPixel = 0;
    222 
    223         compress(initCodeSize + 1, os); // compress and write the pixel data
    224 
    225         os.write(0); // write block terminator
    226     }
    227 
    228     // Flush the packet to disk, and reset the accumulator
    229     void flush_char(OutputStream outs) throws IOException {
    230         if (a_count > 0) {
    231             outs.write(a_count);
    232             outs.write(accum, 0, a_count);
    233             a_count = 0;
    234         }
    235     }
    236 
    237     final int MAXCODE(int n_bits) {
    238         return (1 << n_bits) - 1;
    239     }
    240 
    241     // ----------------------------------------------------------------------------
    242     // Return the next pixel from the image
    243     // ----------------------------------------------------------------------------
    244     private int nextPixel() {
    245         if (remaining == 0)
    246             return EOF;
    247 
    248         --remaining;
    249 
    250         byte pix = pixAry[curPixel++];
    251 
    252         return pix & 0xff;
    253     }
    254 
    255     void output(int code, OutputStream outs) throws IOException {
    256         cur_accum &= masks[cur_bits];
    257 
    258         if (cur_bits > 0)
    259             cur_accum |= (code << cur_bits);
    260         else
    261             cur_accum = code;
    262 
    263         cur_bits += n_bits;
    264 
    265         while (cur_bits >= 8) {
    266             char_out((byte) (cur_accum & 0xff), outs);
    267             cur_accum >>= 8;
    268             cur_bits -= 8;
    269         }
    270 
    271         // If the next entry is going to be too big for the code size,
    272         // then increase it, if possible.
    273         if (free_ent > maxcode || clear_flg) {
    274             if (clear_flg) {
    275                 maxcode = MAXCODE(n_bits = g_init_bits);
    276                 clear_flg = false;
    277             } else {
    278                 ++n_bits;
    279                 if (n_bits == maxbits)
    280                     maxcode = maxmaxcode;
    281                 else
    282                     maxcode = MAXCODE(n_bits);
    283             }
    284         }
    285 
    286         if (code == EOFCode) {
    287             // At EOF, write the rest of the buffer.
    288             while (cur_bits > 0) {
    289                 char_out((byte) (cur_accum & 0xff), outs);
    290                 cur_accum >>= 8;
    291                 cur_bits -= 8;
    292             }
    293 
    294             flush_char(outs);
    295         }
    296     }
    297 }
    298