001 package railo.runtime.img; 002 003 import java.io.IOException; 004 import java.io.OutputStream; 005 006 //============================================================================== 007 // Adapted from Jef Poskanzer's Java port by way of J. M. G. Elliott. 008 // K Weiner 12/00 009 010 public class LZWEncoder { 011 012 private static final int EOF = -1; 013 014 private int imgW, imgH; 015 private byte[] pixAry; 016 private int initCodeSize; 017 private int remaining; 018 private int curPixel; 019 020 // GIFCOMPR.C - GIF Image compression routines 021 // 022 // Lempel-Ziv compression based on 'compress'. GIF modifications by 023 // David Rowley (mgardi@watdcsu.waterloo.edu) 024 025 // General DEFINEs 026 027 static final int BITS = 12; 028 029 static final int HSIZE = 5003; // 80% occupancy 030 031 // GIF Image compression - modified 'compress' 032 // 033 // Based on: compress.c - File compression ala IEEE Computer, June 1984. 034 // 035 // By Authors: Spencer W. Thomas (decvax!harpo!utah-cs!utah-gr!thomas) 036 // Jim McKie (decvax!mcvax!jim) 037 // Steve Davies (decvax!vax135!petsd!peora!srd) 038 // Ken Turkowski (decvax!decwrl!turtlevax!ken) 039 // James A. Woods (decvax!ihnp4!ames!jaw) 040 // Joe Orost (decvax!vax135!petsd!joe) 041 042 int n_bits; // number of bits/code 043 int maxbits = BITS; // user settable max # bits/code 044 int maxcode; // maximum code, given n_bits 045 int maxmaxcode = 1 << BITS; // should NEVER generate this code 046 047 int[] htab = new int[HSIZE]; 048 int[] codetab = new int[HSIZE]; 049 050 int hsize = HSIZE; // for dynamic table sizing 051 052 int free_ent = 0; // first unused entry 053 054 // block compression parameters -- after all codes are used up, 055 // and compression rate changes, start over. 056 boolean clear_flg = false; 057 058 // Algorithm: use open addressing double hashing (no chaining) on the 059 // prefix code / next character combination. We do a variant of Knuth's 060 // algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime 061 // secondary probe. Here, the modular division first probe is gives way 062 // to a faster exclusive-or manipulation. Also do block compression with 063 // an adaptive reset, whereby the code table is cleared when the compression 064 // ratio decreases, but after the table fills. The variable-length output 065 // codes are re-sized at this point, and a special CLEAR code is generated 066 // for the decompressor. Late addition: construct the table according to 067 // file size for noticeable speed improvement on small files. Please direct 068 // questions about this implementation to ames!jaw. 069 070 int g_init_bits; 071 072 int ClearCode; 073 int EOFCode; 074 075 // output 076 // 077 // Output the given code. 078 // Inputs: 079 // code: A n_bits-bit integer. If == -1, then EOF. This assumes 080 // that n_bits =< wordsize - 1. 081 // Outputs: 082 // Outputs code to the file. 083 // Assumptions: 084 // Chars are 8 bits long. 085 // Algorithm: 086 // Maintain a BITS character long buffer (so that 8 codes will 087 // fit in it exactly). Use the VAX insv instruction to insert each 088 // code in turn. When the buffer fills up empty it and start over. 089 090 int cur_accum = 0; 091 int cur_bits = 0; 092 093 int masks[] = 094 { 095 0x0000, 096 0x0001, 097 0x0003, 098 0x0007, 099 0x000F, 100 0x001F, 101 0x003F, 102 0x007F, 103 0x00FF, 104 0x01FF, 105 0x03FF, 106 0x07FF, 107 0x0FFF, 108 0x1FFF, 109 0x3FFF, 110 0x7FFF, 111 0xFFFF }; 112 113 // Number of characters so far in this 'packet' 114 int a_count; 115 116 // Define the storage for the packet accumulator 117 byte[] accum = new byte[256]; 118 119 //---------------------------------------------------------------------------- 120 public LZWEncoder(int width, int height, byte[] pixels, int color_depth) { 121 imgW = width; 122 imgH = height; 123 pixAry = pixels; 124 initCodeSize = Math.max(2, color_depth); 125 } 126 127 // Add a character to the end of the current packet, and if it is 254 128 // characters, flush the packet to disk. 129 void char_out(byte c, OutputStream outs) throws IOException { 130 accum[a_count++] = c; 131 if (a_count >= 254) 132 flush_char(outs); 133 } 134 135 // Clear out the hash table 136 137 // table clear for block compress 138 void cl_block(OutputStream outs) throws IOException { 139 cl_hash(hsize); 140 free_ent = ClearCode + 2; 141 clear_flg = true; 142 143 output(ClearCode, outs); 144 } 145 146 // reset code table 147 void cl_hash(int hsize) { 148 for (int i = 0; i < hsize; ++i) 149 htab[i] = -1; 150 } 151 152 void compress(int init_bits, OutputStream outs) throws IOException { 153 int fcode; 154 int i /* = 0 */; 155 int c; 156 int ent; 157 int disp; 158 int hsize_reg; 159 int hshift; 160 161 // Set up the globals: g_init_bits - initial number of bits 162 g_init_bits = init_bits; 163 164 // Set up the necessary values 165 clear_flg = false; 166 n_bits = g_init_bits; 167 maxcode = MAXCODE(n_bits); 168 169 ClearCode = 1 << (init_bits - 1); 170 EOFCode = ClearCode + 1; 171 free_ent = ClearCode + 2; 172 173 a_count = 0; // clear packet 174 175 ent = nextPixel(); 176 177 hshift = 0; 178 for (fcode = hsize; fcode < 65536; fcode *= 2) 179 ++hshift; 180 hshift = 8 - hshift; // set hash code range bound 181 182 hsize_reg = hsize; 183 cl_hash(hsize_reg); // clear hash table 184 185 output(ClearCode, outs); 186 187 outer_loop : while ((c = nextPixel()) != EOF) { 188 fcode = (c << maxbits) + ent; 189 i = (c << hshift) ^ ent; // xor hashing 190 191 if (htab[i] == fcode) { 192 ent = codetab[i]; 193 continue; 194 } else if (htab[i] >= 0) // non-empty slot 195 { 196 disp = hsize_reg - i; // secondary hash (after G. Knott) 197 if (i == 0) 198 disp = 1; 199 do { 200 if ((i -= disp) < 0) 201 i += hsize_reg; 202 203 if (htab[i] == fcode) { 204 ent = codetab[i]; 205 continue outer_loop; 206 } 207 } while (htab[i] >= 0); 208 } 209 output(ent, outs); 210 ent = c; 211 if (free_ent < maxmaxcode) { 212 codetab[i] = free_ent++; // code -> hashtable 213 htab[i] = fcode; 214 } else 215 cl_block(outs); 216 } 217 // Put out the final code. 218 output(ent, outs); 219 output(EOFCode, outs); 220 } 221 222 //---------------------------------------------------------------------------- 223 public void encode(OutputStream os) throws IOException { 224 os.write(initCodeSize); // write "initial code size" byte 225 226 remaining = imgW * imgH; // reset navigation variables 227 curPixel = 0; 228 229 compress(initCodeSize + 1, os); // compress and write the pixel data 230 231 os.write(0); // write block terminator 232 } 233 234 // Flush the packet to disk, and reset the accumulator 235 void flush_char(OutputStream outs) throws IOException { 236 if (a_count > 0) { 237 outs.write(a_count); 238 outs.write(accum, 0, a_count); 239 a_count = 0; 240 } 241 } 242 243 final int MAXCODE(int n_bits) { 244 return (1 << n_bits) - 1; 245 } 246 247 //---------------------------------------------------------------------------- 248 // Return the next pixel from the image 249 //---------------------------------------------------------------------------- 250 private int nextPixel() { 251 if (remaining == 0) 252 return EOF; 253 254 --remaining; 255 256 byte pix = pixAry[curPixel++]; 257 258 return pix & 0xff; 259 } 260 261 void output(int code, OutputStream outs) throws IOException { 262 cur_accum &= masks[cur_bits]; 263 264 if (cur_bits > 0) 265 cur_accum |= (code << cur_bits); 266 else 267 cur_accum = code; 268 269 cur_bits += n_bits; 270 271 while (cur_bits >= 8) { 272 char_out((byte) (cur_accum & 0xff), outs); 273 cur_accum >>= 8; 274 cur_bits -= 8; 275 } 276 277 // If the next entry is going to be too big for the code size, 278 // then increase it, if possible. 279 if (free_ent > maxcode || clear_flg) { 280 if (clear_flg) { 281 maxcode = MAXCODE(n_bits = g_init_bits); 282 clear_flg = false; 283 } else { 284 ++n_bits; 285 if (n_bits == maxbits) 286 maxcode = maxmaxcode; 287 else 288 maxcode = MAXCODE(n_bits); 289 } 290 } 291 292 if (code == EOFCode) { 293 // At EOF, write the rest of the buffer. 294 while (cur_bits > 0) { 295 char_out((byte) (cur_accum & 0xff), outs); 296 cur_accum >>= 8; 297 cur_bits -= 8; 298 } 299 300 flush_char(outs); 301 } 302 } 303 }