PngDeflater


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  package org.eclipse.swt.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  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  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 != 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 != 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 != 0) {
355 
356             int i;
357             
358             for (i = 1; position + i < inLength; i++) {
359                 if (in[position + i] != 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 == MAX_MATCHES) {
374                     break;
375                 }
376             
377             }
378                         
379         }
380         
381         link = link.next;
382         if (link == 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 != null) {
415             window[nextWindow].previous.next = null;
416         }
417         else if (window[nextWindow].hash != 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 != null) {
427             temp.previous = window[nextWindow];
428         }
429         
430         nextWindow = nextWindow + 1;
431         if (nextWindow == 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 != null) {
483         
484             if (deferredMatch != 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 != 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 }
619
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags