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