1 /*******************************************************************************
2 * Copyright (c) 2000, 2011 IBM Corporation and others.
3 *
4 * This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License 2.0
6 * which accompanies this distribution, and is available at
7 * https://www.eclipse.org/legal/epl-2.0/
8 *
9 * SPDX-License-Identifier: EPL-2.0
10 *
11 * Contributors:
12 * IBM Corporation - initial API and implementation
13 *******************************************************************************/
14 package org.eclipse.swt.internal.image;
15
16
17 import org.eclipse.swt.*;
18 import org.eclipse.swt.graphics.*;
19
20 final class LZWCodec {
21 int bitsPerPixel, blockSize, blockIndex, currentByte, bitsLeft,
22 codeSize, clearCode, endCode, newCodes, topSlot, currentSlot,
23 imageWidth, imageHeight, imageX, imageY, pass, line, codeMask;
24 byte[] block, lineArray;
25 int[] stack, suffix, prefix;
26 LZWNode[] nodeStack;
27 LEDataInputStream inputStream;
28 LEDataOutputStream outputStream;
29 ImageData image;
30 ImageLoader loader;
31 boolean interlaced;
32 static final int[] MASK_TABLE = new int[] {
33 0x1, 0x3, 0x7, 0xF, 0x1F, 0x3F, 0x7F,
34 0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF
35 };
36
37 /**
38 * Decode the input.
39 */
decode()40 void decode() {
41 int code;
42 int oc = 0;
43 int fc = 0;
44 byte[] buf = new byte[imageWidth];
45 int stackIndex = 0;
46 int bufIndex = 0;
47 int c;
48 while ((c = nextCode()) != endCode) {
49 if (c == clearCode) {
50 codeSize = bitsPerPixel + 1;
51 codeMask = MASK_TABLE[bitsPerPixel];
52 currentSlot = newCodes;
53 topSlot = 1 << codeSize;
54 while ((c = nextCode()) == clearCode) {}
55 if (c != endCode) {
56 oc = fc = c;
57 buf[bufIndex] = (byte)c;
58 bufIndex++;
59 if (bufIndex == imageWidth) {
60 nextPutPixels(buf);
61 bufIndex = 0;
62 }
63 }
64 } else {
65 code = c;
66 if (code >= currentSlot) {
67 code = oc;
68 stack[stackIndex] = fc;
69 stackIndex++;
70 }
71 while (code >= newCodes) {
72 stack[stackIndex] = suffix[code];
73 stackIndex++;
74 code = prefix[code];
75 }
76 stack[stackIndex] = code;
77 stackIndex++;
78 if (currentSlot < topSlot) {
79 fc = code;
80 suffix[currentSlot] = fc;
81 prefix[currentSlot] = oc;
82 currentSlot++;
83 oc = c;
84 }
85 if (currentSlot >= topSlot) {
86 if (codeSize < 12) {
87 codeMask = MASK_TABLE[codeSize];
88 codeSize++;
89 topSlot = topSlot + topSlot;
90 }
91 }
92 while (stackIndex > 0) {
93 stackIndex--;
94 buf[bufIndex] = (byte)stack[stackIndex];
95 bufIndex++;
96 if (bufIndex == imageWidth) {
97 nextPutPixels(buf);
98 bufIndex = 0;
99 }
100 }
101 }
102 }
103 if (bufIndex != 0 && line < imageHeight) {
104 nextPutPixels(buf);
105 }
106 }
107 /**
108 * Decode the LZW-encoded bytes in the given byte stream
109 * into the given DeviceIndependentImage.
110 */
decode(LEDataInputStream inputStream, ImageLoader loader, ImageData image, boolean interlaced, int depth)111 public void decode(LEDataInputStream inputStream, ImageLoader loader, ImageData image, boolean interlaced, int depth) {
112 this.inputStream = inputStream;
113 this.loader = loader;
114 this.image = image;
115 this.interlaced = interlaced;
116 this.bitsPerPixel = depth;
117 initializeForDecoding();
118 decode();
119 }
120 /**
121 * Encode the image.
122 */
encode()123 void encode() {
124 nextPutCode(clearCode);
125 int lastPrefix = encodeLoop();
126 nextPutCode(lastPrefix);
127 nextPutCode(endCode);
128
129 // Write out last partial block
130 if (bitsLeft == 8) {
131 block[0] = (byte)(blockIndex - 1); // Nothing in last byte
132 } else {
133 block[0] = (byte)(blockIndex); // Last byte has data
134 }
135 writeBlock();
136
137 // Write out empty block to indicate the end (if needed)
138 if (block[0] != 0) {
139 block[0] = 0;
140 writeBlock();
141 }
142 }
143 /**
144 * Encode the bytes into the given byte stream
145 * from the given DeviceIndependentImage.
146 */
encode(LEDataOutputStream byteStream, ImageData image)147 public void encode(LEDataOutputStream byteStream, ImageData image) {
148 this.outputStream = byteStream;
149 this.image = image;
150 initializeForEncoding();
151 encode();
152 }
153 /**
154 * Encoding loop broken out to allow early return.
155 */
encodeLoop()156 int encodeLoop() {
157 int pixel = nextPixel();
158 boolean found;
159 LZWNode node;
160 while (true) {
161 int currentPrefix = pixel;
162 node = nodeStack[currentPrefix];
163 found = true;
164 pixel = nextPixel();
165 if (pixel < 0)
166 return currentPrefix;
167 while (found && (node.children != null)) {
168 node = node.children;
169 while (found && (node.suffix != pixel)) {
170 if (pixel < node.suffix) {
171 if (node.left == null) {
172 node.left = new LZWNode();
173 found = false;
174 }
175 node = node.left;
176 } else {
177 if (node.right == null) {
178 node.right = new LZWNode();
179 found = false;
180 }
181 node = node.right;
182 }
183 }
184 if (found) {
185 currentPrefix = node.code;
186 pixel = nextPixel();
187 if (pixel < 0)
188 return currentPrefix;
189 }
190 }
191 if (found) {
192 node.children = new LZWNode();
193 node = node.children;
194 }
195 node.children = null;
196 node.left = null;
197 node.right = null;
198 node.code = currentSlot;
199 node.prefix = currentPrefix;
200 node.suffix = pixel;
201 nextPutCode(currentPrefix);
202 currentSlot++;
203 // Off by one?
204 if (currentSlot < 4096) {
205 if (currentSlot > topSlot) {
206 codeSize++;
207 codeMask = MASK_TABLE[codeSize - 1];
208 topSlot *= 2;
209 }
210 } else {
211 nextPutCode(clearCode);
212 for (int i = 0; i < nodeStack.length; i++)
213 nodeStack[i].children = null;
214 codeSize = bitsPerPixel + 1;
215 codeMask = MASK_TABLE[codeSize - 1];
216 currentSlot = newCodes;
217 topSlot = 1 << codeSize;
218 }
219 }
220 }
221 /**
222 * Initialize the receiver for decoding the given
223 * byte array.
224 */
initializeForDecoding()225 void initializeForDecoding() {
226 pass = 1;
227 line = 0;
228 codeSize = bitsPerPixel + 1;
229 topSlot = 1 << codeSize;
230 clearCode = 1 << bitsPerPixel;
231 endCode = clearCode + 1;
232 newCodes = currentSlot = endCode + 1;
233 currentByte = -1;
234 blockSize = bitsLeft = 0;
235 blockIndex = 0;
236 codeMask = MASK_TABLE[codeSize - 1];
237 stack = new int[4096];
238 suffix = new int[4096];
239 prefix = new int[4096];
240 block = new byte[256];
241 imageWidth = image.width;
242 imageHeight = image.height;
243 }
244 /**
245 * Initialize the receiver for encoding the given
246 * byte array.
247 */
initializeForEncoding()248 void initializeForEncoding() {
249 interlaced = false;
250 bitsPerPixel = image.depth;
251 codeSize = bitsPerPixel + 1;
252 topSlot = 1 << codeSize;
253 clearCode = 1 << bitsPerPixel;
254 endCode = clearCode + 1;
255 newCodes = currentSlot = endCode + 1;
256 bitsLeft = 8;
257 currentByte = 0;
258 blockIndex = 1;
259 blockSize = 255;
260 block = new byte[blockSize];
261 block[0] = (byte)(blockSize - 1);
262 nodeStack = new LZWNode[1 << bitsPerPixel];
263 for (int i = 0; i < nodeStack.length; i++) {
264 LZWNode node = new LZWNode();
265 node.code = i + 1;
266 node.prefix = -1;
267 node.suffix = i + 1;
268 nodeStack[i] = node;
269 }
270 imageWidth = image.width;
271 imageHeight = image.height;
272 imageY = -1;
273 lineArray = new byte[imageWidth];
274 imageX = imageWidth + 1; // Force a read
275 }
276 /**
277 * Answer the next code from the input byte array.
278 */
nextCode()279 int nextCode() {
280 int code;
281 if (bitsLeft == 0) {
282 if (blockIndex >= blockSize) {
283 blockSize = readBlock();
284 blockIndex = 0;
285 if (blockSize == 0) return endCode;
286 }
287 blockIndex++;
288 currentByte = block[blockIndex] & 0xFF;
289 bitsLeft = 8;
290 code = currentByte;
291 } else {
292 int shift = bitsLeft - 8;
293 if (shift < 0)
294 code = currentByte >> (0 - shift);
295 else
296 code = currentByte << shift;
297 }
298 while (codeSize > bitsLeft) {
299 if (blockIndex >= blockSize) {
300 blockSize = readBlock();
301 blockIndex = 0;
302 if (blockSize == 0) return endCode;
303 }
304 blockIndex++;
305 currentByte = block[blockIndex] & 0xFF;
306 code += currentByte << bitsLeft;
307 bitsLeft += 8;
308 }
309 bitsLeft -= codeSize;
310 return code & codeMask;
311 }
312 /**
313 * Answer the next pixel to encode in the image
314 */
nextPixel()315 int nextPixel() {
316 imageX++;
317 if (imageX > imageWidth) {
318 imageY++;
319 if (imageY >= imageHeight) {
320 return -1;
321 } else {
322 nextPixels(lineArray, imageWidth);
323 }
324 imageX = 1;
325 }
326 return this.lineArray[imageX - 1] & 0xFF;
327 }
328 /**
329 * Copy a row of pixel values from the image.
330 */
nextPixels(byte[] buf, int lineWidth)331 void nextPixels(byte[] buf, int lineWidth) {
332 if (image.depth == 8) {
333 System.arraycopy(image.data, imageY * image.bytesPerLine, buf, 0, lineWidth);
334 } else {
335 image.getPixels(0, imageY, lineWidth, buf, 0);
336 }
337 }
338 /**
339 * Output aCode to the output stream.
340 */
nextPutCode(int aCode)341 void nextPutCode(int aCode) {
342 int codeToDo = aCode;
343 int codeBitsToDo = codeSize;
344 // Fill in the remainder of the current byte with the
345 // *high-order* bits of the code.
346 int c = codeToDo & MASK_TABLE[bitsLeft - 1];
347 currentByte = currentByte | (c << (8 - bitsLeft));
348 block[blockIndex] = (byte)currentByte;
349 codeBitsToDo -= bitsLeft;
350 if (codeBitsToDo < 1) {
351 // The whole code fit in the first byte, so we are done.
352 bitsLeft -= codeSize;
353 if (bitsLeft == 0) {
354 // We used the whole last byte, so get ready
355 // for the next one.
356 bitsLeft = 8;
357 blockIndex++;
358 if (blockIndex >= blockSize) {
359 writeBlock();
360 blockIndex = 1;
361 }
362 currentByte = 0;
363 }
364 return;
365 }
366 codeToDo = codeToDo >> bitsLeft;
367
368 // Fill in any remaining whole bytes (i.e. not the last one!)
369 blockIndex++;
370 if (blockIndex >= blockSize) {
371 writeBlock();
372 blockIndex = 1;
373 }
374 while (codeBitsToDo >= 8) {
375 currentByte = codeToDo & 0xFF;
376 block[blockIndex] = (byte)currentByte;
377 codeToDo = codeToDo >> 8;
378 codeBitsToDo -= 8;
379 blockIndex++;
380 if (blockIndex >= blockSize) {
381 writeBlock();
382 blockIndex = 1;
383 }
384 }
385 // Fill the *low-order* bits of the last byte with the remainder
386 bitsLeft = 8 - codeBitsToDo;
387 currentByte = codeToDo;
388 block[blockIndex] = (byte)currentByte;
389 }
390 /**
391 * Copy a row of pixel values to the image.
392 */
nextPutPixels(byte[] buf)393 void nextPutPixels(byte[] buf) {
394 if (image.depth == 8) {
395 // Slight optimization for depth = 8.
396 int start = line * image.bytesPerLine;
397 System.arraycopy(buf, 0, image.data, start, imageWidth);
398 } else {
399 image.setPixels(0, line, imageWidth, buf, 0);
400 }
401 if (interlaced) {
402 if (pass == 1) {
403 copyRow(buf, 7);
404 line += 8;
405 } else if (pass == 2) {
406 copyRow(buf, 3);
407 line += 8;
408 } else if (pass == 3) {
409 copyRow(buf, 1);
410 line += 4;
411 } else if (pass == 4) {
412 line += 2;
413 } else if (pass == 5) {
414 line += 0;
415 }
416 if (line >= imageHeight) {
417 pass++;
418 if (pass == 2) line = 4;
419 else if (pass == 3) line = 2;
420 else if (pass == 4) line = 1;
421 else if (pass == 5) line = 0;
422 if (pass < 5) {
423 if (loader.hasListeners()) {
424 ImageData imageCopy = (ImageData) image.clone();
425 loader.notifyListeners(
426 new ImageLoaderEvent(loader, imageCopy, pass - 2, false));
427 }
428 }
429 }
430 if (line >= imageHeight) line = 0;
431 } else {
432 line++;
433 }
434 }
435 /**
436 * Copy duplicate rows of pixel values to the image.
437 * This is to fill in rows if the image is interlaced.
438 */
copyRow(byte[] buf, int copies)439 void copyRow(byte[] buf, int copies) {
440 for (int i = 1; i <= copies; i++) {
441 if (line + i < imageHeight) {
442 image.setPixels(0, line + i, imageWidth, buf, 0);
443 }
444 }
445 }
446 /**
447 * Read a block from the byte stream.
448 * Return the number of bytes read.
449 * Throw an exception if the block could not be read.
450 */
readBlock()451 int readBlock() {
452 int size = -1;
453 try {
454 size = inputStream.read();
455 if (size == -1) {
456 SWT.error(SWT.ERROR_INVALID_IMAGE);
457 }
458 block[0] = (byte)size;
459 size = inputStream.read(block, 1, size);
460 if (size == -1) {
461 SWT.error(SWT.ERROR_INVALID_IMAGE);
462 }
463 } catch (Exception e) {
464 SWT.error(SWT.ERROR_IO, e);
465 }
466 return size;
467 }
468 /**
469 * Write a block to the byte stream.
470 * Throw an exception if the block could not be written.
471 */
writeBlock()472 void writeBlock() {
473 try {
474 outputStream.write(block, 0, (block[0] & 0xFF) + 1);
475 } catch (Exception e) {
476 SWT.error(SWT.ERROR_IO, e);
477 }
478 }
479 }
480