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