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