Mercurial > projects > dwt-mac

comparison dwt/internal/image/LZWCodec.d @ 0:380af2bdd8e5

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