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
