Mercurial > projects > dwt-mac

comparison dwt/internal/image/PngDeflater.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 1a8b3cb347e0
comparison
equal deleted inserted replaced
-1:000000000000 0:380af2bdd8e5
1 /*******************************************************************************
2 * Copyright (c) 2000, 2006 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 import java.io.ByteArrayOutputStream;
14
15 public class PngDeflater {
16
17 static final int BASE = 65521;
18 static final int WINDOW = 32768;
19 static final int MIN_LENGTH = 3;
20 static final int MAX_MATCHES = 32;
21 static final int HASH = 8209;
22
23 byte[] in;
24 int inLength;
25
26 ByteArrayOutputStream bytes = new ByteArrayOutputStream(1024);
27
28 int adler32 = 1;
29
30 int buffer, bitCount;
31
32 Link[] hashtable = new Link[HASH];
33 Link[] window = new Link[WINDOW];
34 int nextWindow;
35
36 static class Link {
37
38 int hash, value;
39 Link previous, next;
40
41 Link() {
42
43 this.hash = 0;
44 this.value = 0;
45 this.previous = null;
46 this.next = null;
47
48 }
49
50 }
51
52 static class Match {
53
54 int length, distance;
55
56 Match(int length, int distance) {
57
58 this.length = length;
59 this.distance = distance;
60
61 }
62
63 }
64
65 static final short mirrorBytes[] = {
66
67 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
68 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
69 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
70 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
71 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
72 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
73 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
74 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
75 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
76 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
77 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
78 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
79 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
80 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
81 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
82 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
83 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
84 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
85 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
86 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
87 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
88 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
89 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
90 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
91 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
92 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
93 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
94 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
95 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
96 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
97 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
98 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
99
100 };
101
102 static class Code {
103
104 int code, extraBits, min, max;
105
106 Code(int code, int extraBits, int min, int max) {
107
108 this.code = code;
109 this.extraBits = extraBits;
110 this.min = min;
111 this.max = max;
112
113 }
114
115 }
116
117 static final Code lengthCodes[] = {
118
119 new Code(257, 0, 3, 3),
120 new Code(258, 0, 4, 4),
121 new Code(259, 0, 5, 5),
122 new Code(260, 0, 6, 6),
123 new Code(261, 0, 7, 7),
124 new Code(262, 0, 8, 8),
125 new Code(263, 0, 9, 9),
126 new Code(264, 0, 10, 10),
127 new Code(265, 1, 11, 12),
128 new Code(266, 1, 13, 14),
129 new Code(267, 1, 15, 16),
130 new Code(268, 1, 17, 18),
131 new Code(269, 2, 19, 22),
132 new Code(270, 2, 23, 26),
133 new Code(271, 2, 27, 30),
134 new Code(272, 2, 31, 34),
135 new Code(273, 3, 35, 42),
136 new Code(274, 3, 43, 50),
137 new Code(275, 3, 51, 58),
138 new Code(276, 3, 59, 66),
139 new Code(277, 4, 67, 82),
140 new Code(278, 4, 83, 98),
141 new Code(279, 4, 99, 114),
142 new Code(280, 4, 115, 130),
143 new Code(281, 5, 131, 162),
144 new Code(282, 5, 163, 194),
145 new Code(283, 5, 195, 226),
146 new Code(284, 5, 227, 257),
147 new Code(285, 0, 258, 258)
148
149 };
150
151 static final Code distanceCodes[] = {
152
153 new Code(0, 0, 1, 1),
154 new Code(1, 0, 2, 2),
155 new Code(2, 0, 3, 3),
156 new Code(3, 0, 4, 4),
157 new Code(4, 1, 5, 6),
158 new Code(5, 1, 7, 8),
159 new Code(6, 2, 9, 12),
160 new Code(7, 2, 13, 16),
161 new Code(8, 3, 17, 24),
162 new Code(9, 3, 25, 32),
163 new Code(10, 4, 33, 48),
164 new Code(11, 4, 49, 64),
165 new Code(12, 5, 65, 96),
166 new Code(13, 5, 97, 128),
167 new Code(14, 6, 129, 192),
168 new Code(15, 6, 193, 256),
169 new Code(16, 7, 257, 384),
170 new Code(17, 7, 385, 512),
171 new Code(18, 8, 513, 768),
172 new Code(19, 8, 769, 1024),
173 new Code(20, 9, 1025, 1536),
174 new Code(21, 9, 1537, 2048),
175 new Code(22, 10, 2049, 3072),
176 new Code(23, 10, 3073, 4096),
177 new Code(24, 11, 4097, 6144),
178 new Code(25, 11, 6145, 8192),
179 new Code(26, 12, 8193, 12288),
180 new Code(27, 12, 12289, 16384),
181 new Code(28, 13, 16385, 24576),
182 new Code(29, 13, 24577, 32768)
183
184 };
185
186 void writeShortLSB(ByteArrayOutputStream baos, int theShort) {
187
188 byte byte1 = (byte) (theShort & 0xff);
189 byte byte2 = (byte) ((theShort >> 8) & 0xff);
190 byte[] temp = {byte1, byte2};
191 baos.write(temp, 0, 2);
192
193 }
194
195 void writeInt(ByteArrayOutputStream baos, int theInt) {
196
197 byte byte1 = (byte) ((theInt >> 24) & 0xff);
198 byte byte2 = (byte) ((theInt >> 16) & 0xff);
199 byte byte3 = (byte) ((theInt >> 8) & 0xff);
200 byte byte4 = (byte) (theInt & 0xff);
201 byte[] temp = {byte1, byte2, byte3, byte4};
202 baos.write(temp, 0, 4);
203
204 }
205
206 void updateAdler(byte value) {
207
208 int low = adler32 & 0xffff;
209 int high = (adler32 >> 16) & 0xffff;
210 int valueInt = value & 0xff;
211 low = (low + valueInt) % BASE;
212 high = (low + high) % BASE;
213 adler32 = (high << 16) | low;
214
215 }
216
217 int hash(byte[] bytes) {
218
219 int hash = ((bytes[0] & 0xff) << 24 | (bytes[1] & 0xff) << 16 | (bytes[2] & 0xff) << 8) % HASH;
220 if (hash < 0) {
221 hash = hash + HASH;
222 }
223 return hash;
224
225 }
226
227 void writeBits(int value, int count) {
228
229 buffer |= value << bitCount;
230 bitCount += count;
231 if (bitCount >= 16) {
232 bytes.write((byte) buffer);
233 bytes.write((byte) (buffer >>> 8));
234 buffer >>>= 16;
235 bitCount -= 16;
236 }
237
238 }
239
240 void alignToByte() {
241
242 if (bitCount > 0) {
243 bytes.write((byte) buffer);
244 if (bitCount > 8) bytes.write((byte) (buffer >>> 8));
245 }
246 buffer = 0;
247 bitCount = 0;
248
249 }
250
251 void outputLiteral(byte literal) {
252
253 int i = literal & 0xff;
254
255 if (i <= 143) {
256 // 0 through 143 are 8 bits long starting at 00110000
257 writeBits(mirrorBytes[0x30 + i], 8);
258 }
259 else {
260 // 144 through 255 are 9 bits long starting at 110010000
261 writeBits(1 + 2 * mirrorBytes[0x90 - 144 + i], 9);
262 }
263
264 }
265
266 Code findCode(int value, Code[] codes) {
267
268 int i, j, k;
269
270 i = -1;
271 j = codes.length;
272 while (true) {
273 k = (j + i) / 2;
274 if (value < codes[k].min) {
275 j = k;
276 }
277 else if (value > codes[k].max) {
278 i = k;
279 }
280 else {
281 return codes[k];
282 }
283 }
284
285 }
286
287 void outputMatch(int length, int distance) {
288
289 Code d, l;
290 int thisLength;
291
292 while (length > 0) {
293
294 // we can transmit matches of lengths 3 through 258 inclusive
295 // so if length exceeds 258, we must transmit in several steps,
296 // with 258 or less in each step
297
298 if (length > 260) {
299 thisLength = 258;
300 }
301 else if (length <= 258) {
302 thisLength = length;
303 }
304 else {
305 thisLength = length - 3;
306 }
307
308 length = length - thisLength;
309
310 // find length code
311 l = findCode(thisLength, lengthCodes);
312
313 // transmit the length code
314 // 256 through 279 are 7 bits long starting at 0000000
315 // 280 through 287 are 8 bits long starting at 11000000
316 if (l.code <= 279) {
317 writeBits(mirrorBytes[(l.code - 256) * 2], 7);
318 }
319 else {
320 writeBits(mirrorBytes[0xc0 - 280 + l.code], 8);
321 }
322
323 // transmit the extra bits
324 if (l.extraBits !is 0) {
325 writeBits(thisLength - l.min, l.extraBits);
326 }
327
328 // find distance code
329 d = findCode(distance, distanceCodes);
330
331 // transmit the distance code
332 // 5 bits long starting at 00000
333 writeBits(mirrorBytes[d.code * 8], 5);
334
335 // transmit the extra bits
336 if (d.extraBits !is 0) {
337 writeBits(distance - d.min, d.extraBits);
338 }
339
340 }
341
342 }
343
344 Match findLongestMatch(int position, Link firstPosition) {
345
346 Link link = firstPosition;
347 int numberOfMatches = 0;
348 Match bestMatch = new Match(-1, -1);
349
350 while (true) {
351
352 int matchPosition = link.value;
353
354 if (position - matchPosition < WINDOW && matchPosition !is 0) {
355
356 int i;
357
358 for (i = 1; position + i < inLength; i++) {
359 if (in[position + i] !is in[matchPosition + i]) {
360 break;
361 }
362 }
363
364 if (i >= MIN_LENGTH) {
365
366 if (i > bestMatch.length) {
367 bestMatch.length = i;
368 bestMatch.distance = position - matchPosition;
369 }
370
371 numberOfMatches = numberOfMatches + 1;
372
373 if (numberOfMatches is MAX_MATCHES) {
374 break;
375 }
376
377 }
378
379 }
380
381 link = link.next;
382 if (link is null) {
383 break;
384 }
385
386 }
387
388 if (bestMatch.length < MIN_LENGTH || bestMatch.distance < 1 || bestMatch.distance > WINDOW) {
389 return null;
390 }
391
392 return bestMatch;
393
394 }
395
396 void updateHashtable(int to, int from) {
397
398 byte[] data = new byte[3];
399 int hash;
400 Link temp;
401
402 for (int i = to; i < from; i++) {
403
404 if (i + MIN_LENGTH > inLength) {
405 break;
406 }
407
408 data[0] = in[i];
409 data[1] = in[i + 1];
410 data[2] = in[i + 2];
411
412 hash = hash(data);
413
414 if (window[nextWindow].previous !is null) {
415 window[nextWindow].previous.next = null;
416 }
417 else if (window[nextWindow].hash !is 0) {
418 hashtable[window[nextWindow].hash].next = null;
419 }
420
421 window[nextWindow].hash = hash;
422 window[nextWindow].value = i;
423 window[nextWindow].previous = null;
424 temp = window[nextWindow].next = hashtable[hash].next;
425 hashtable[hash].next = window[nextWindow];
426 if (temp !is null) {
427 temp.previous = window[nextWindow];
428 }
429
430 nextWindow = nextWindow + 1;
431 if (nextWindow is WINDOW) {
432 nextWindow = 0;
433 }
434
435 }
436
437 }
438
439 void compress() {
440
441 int position, newPosition;
442 byte[] data = new byte[3];
443 int hash;
444 for (int i = 0; i < HASH; i++) {
445 hashtable[i] = new Link();
446 }
447 for (int i = 0; i < WINDOW; i++) {
448 window[i] = new Link();
449 }
450 nextWindow = 0;
451 Link firstPosition;
452 Match match;
453 int deferredPosition = -1;
454 Match deferredMatch = null;
455
456 writeBits(0x01, 1); // BFINAL = 0x01 (final block)
457 writeBits(0x01, 2); // BTYPE = 0x01 (compression with fixed Huffman codes)
458
459 // just output first byte so we never match at zero
460 outputLiteral(in[0]);
461 position = 1;
462
463 while (position < inLength) {
464
465 if (inLength - position < MIN_LENGTH) {
466 outputLiteral(in[position]);
467 position = position + 1;
468 continue;
469 }
470
471 data[0] = in[position];
472 data[1] = in[position + 1];
473 data[2] = in[position + 2];
474
475 hash = hash(data);
476 firstPosition = hashtable[hash];
477
478 match = findLongestMatch(position, firstPosition);
479
480 updateHashtable(position, position + 1);
481
482 if (match !is null) {
483
484 if (deferredMatch !is null) {
485 if (match.length > deferredMatch.length + 1) {
486 // output literal at deferredPosition
487 outputLiteral(in[deferredPosition]);
488 // defer this match
489 deferredPosition = position;
490 deferredMatch = match;
491 position = position + 1;
492 }
493 else {
494 // output deferredMatch
495 outputMatch(deferredMatch.length, deferredMatch.distance);
496 newPosition = deferredPosition + deferredMatch.length;
497 deferredPosition = -1;
498 deferredMatch = null;
499 updateHashtable(position + 1, newPosition);
500 position = newPosition;
501 }
502 }
503 else {
504 // defer this match
505 deferredPosition = position;
506 deferredMatch = match;
507 position = position + 1;
508 }
509
510 }
511
512 else {
513
514 // no match found
515 if (deferredMatch !is null) {
516 outputMatch(deferredMatch.length, deferredMatch.distance);
517 newPosition = deferredPosition + deferredMatch.length;
518 deferredPosition = -1;
519 deferredMatch = null;
520 updateHashtable(position + 1, newPosition);
521 position = newPosition;
522 }
523 else {
524 outputLiteral(in[position]);
525 position = position + 1;
526 }
527
528 }
529
530 }
531
532 writeBits(0, 7); // end of block code
533 alignToByte();
534
535 }
536
537 void compressHuffmanOnly() {
538
539 int position;
540
541 writeBits(0x01, 1); // BFINAL = 0x01 (final block)
542 writeBits(0x01, 2); // BTYPE = 0x01 (compression with fixed Huffman codes)
543
544 for (position = 0; position < inLength;) {
545
546 outputLiteral(in[position]);
547 position = position + 1;
548
549 }
550
551 writeBits(0, 7); // end of block code
552 alignToByte();
553
554 }
555
556 void store() {
557
558 // stored blocks are limited to 0xffff bytes
559
560 int start = 0;
561 int length = inLength;
562 int blockLength;
563 int BFINAL = 0x00; // BFINAL = 0x00 or 0x01 (if final block), BTYPE = 0x00 (no compression)
564
565 while (length > 0) {
566
567 if (length < 65535) {
568 blockLength = length;
569 BFINAL = 0x01;
570 }
571 else {
572 blockLength = 65535;
573 BFINAL = 0x00;
574 }
575
576 // write data header
577 bytes.write((byte) BFINAL);
578 writeShortLSB(bytes, blockLength); // LEN
579 writeShortLSB(bytes, blockLength ^ 0xffff); // NLEN (one's complement of LEN)
580
581 // write actual data
582 bytes.write(in, start, blockLength);
583
584 length = length - blockLength;
585 start = start + blockLength;
586
587 }
588
589 }
590
591 public byte[] deflate(byte[] input) {
592
593 in = input;
594 inLength = input.length;
595
596 // write zlib header
597 bytes.write((byte) 0x78); // window size = 0x70 (32768), compression method = 0x08
598 bytes.write((byte) 0x9C); // compression level = 0x80 (default), check bits = 0x1C
599
600 // compute checksum
601 for (int i = 0; i < inLength; i++) {
602 updateAdler(in[i]);
603 }
604
605 //store();
606
607 //compressHuffmanOnly();
608
609 compress();
610
611 // write checksum
612 writeInt(bytes, adler32);
613
614 return bytes.toByteArray();
615
616 }
617
618 }