Mercurial > projects > dwt-win
view dwt/internal/image/PngDeflater.d @ 213:36f5cb12e1a2
Update to SWT 3.4M7
author | Frank Benoit <benoit@tionex.de> |
---|---|
date | Sat, 17 May 2008 17:34:28 +0200 |
parents | 1801ddeb8f32 |
children | fd9c62a2998e |
line wrap: on
line source
/******************************************************************************* * Copyright (c) 2000, 2006 IBM Corporation and others. * All rights reserved. This program and the accompanying materials * are made available under the terms of the Eclipse Public License v1.0 * which accompanies this distribution, and is available at * http://www.eclipse.org/legal/epl-v10.html * * Contributors: * IBM Corporation - initial API and implementation * Port to the D programming language: * Frank Benoit <benoit@tionex.de> *******************************************************************************/ module dwt.internal.image.PngDeflater; import dwt.dwthelper.ByteArrayOutputStream; public class PngDeflater { static const int BASE = 65521; static const int WINDOW = 32768; static const int MIN_LENGTH = 3; static const int MAX_MATCHES = 32; static const int HASH = 8209; byte[] istr; int inLength; ByteArrayOutputStream bytes; int adler32 = 1; int buffer, bitCount; Link[HASH] hashtable;// = new Link[HASH]; Link[WINDOW] window;// = new Link[WINDOW]; int nextWindow; public this(){ bytes = new ByteArrayOutputStream(1024); } class Link { int hash, value; Link previous, next; this() { this.hash = 0; this.value = 0; this.previous = null; this.next = null; } } static class Match { int length, distance; this(int length, int distance) { this.length = length; this.distance = distance; } } static const short mirrorBytes[] = [ cast(short) 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0, 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8, 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8, 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4, 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4, 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec, 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc, 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2, 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2, 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea, 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa, 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6, 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6, 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee, 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe, 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1, 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1, 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9, 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9, 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5, 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5, 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed, 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd, 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3, 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3, 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb, 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb, 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7, 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7, 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef, 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff, ]; static class Code { int code, extraBits, min, max; this(int code, int extraBits, int min, int max) { this.code = code; this.extraBits = extraBits; this.min = min; this.max = max; } } static const Code lengthCodes[]; static const Code distanceCodes[]; static this() { lengthCodes = [ new Code(257, 0, 3, 3), new Code(258, 0, 4, 4), new Code(259, 0, 5, 5), new Code(260, 0, 6, 6), new Code(261, 0, 7, 7), new Code(262, 0, 8, 8), new Code(263, 0, 9, 9), new Code(264, 0, 10, 10), new Code(265, 1, 11, 12), new Code(266, 1, 13, 14), new Code(267, 1, 15, 16), new Code(268, 1, 17, 18), new Code(269, 2, 19, 22), new Code(270, 2, 23, 26), new Code(271, 2, 27, 30), new Code(272, 2, 31, 34), new Code(273, 3, 35, 42), new Code(274, 3, 43, 50), new Code(275, 3, 51, 58), new Code(276, 3, 59, 66), new Code(277, 4, 67, 82), new Code(278, 4, 83, 98), new Code(279, 4, 99, 114), new Code(280, 4, 115, 130), new Code(281, 5, 131, 162), new Code(282, 5, 163, 194), new Code(283, 5, 195, 226), new Code(284, 5, 227, 257), new Code(285, 0, 258, 258)]; distanceCodes = [ new Code(0, 0, 1, 1), new Code(1, 0, 2, 2), new Code(2, 0, 3, 3), new Code(3, 0, 4, 4), new Code(4, 1, 5, 6), new Code(5, 1, 7, 8), new Code(6, 2, 9, 12), new Code(7, 2, 13, 16), new Code(8, 3, 17, 24), new Code(9, 3, 25, 32), new Code(10, 4, 33, 48), new Code(11, 4, 49, 64), new Code(12, 5, 65, 96), new Code(13, 5, 97, 128), new Code(14, 6, 129, 192), new Code(15, 6, 193, 256), new Code(16, 7, 257, 384), new Code(17, 7, 385, 512), new Code(18, 8, 513, 768), new Code(19, 8, 769, 1024), new Code(20, 9, 1025, 1536), new Code(21, 9, 1537, 2048), new Code(22, 10, 2049, 3072), new Code(23, 10, 3073, 4096), new Code(24, 11, 4097, 6144), new Code(25, 11, 6145, 8192), new Code(26, 12, 8193, 12288), new Code(27, 12, 12289, 16384), new Code(28, 13, 16385, 24576), new Code(29, 13, 24577, 32768)]; } void writeShortLSB(ByteArrayOutputStream baos, int theShort) { byte byte1 = cast(byte) (theShort & 0xff); byte byte2 = cast(byte) ((theShort >> 8) & 0xff); byte[] temp = [byte1, byte2]; baos.write(temp, 0, 2); } void writeInt(ByteArrayOutputStream baos, int theInt) { byte byte1 = cast(byte) ((theInt >> 24) & 0xff); byte byte2 = cast(byte) ((theInt >> 16) & 0xff); byte byte3 = cast(byte) ((theInt >> 8) & 0xff); byte byte4 = cast(byte) (theInt & 0xff); byte[] temp = [byte1, byte2, byte3, byte4]; baos.write(temp, 0, 4); } void updateAdler(byte value) { int low = adler32 & 0xffff; int high = (adler32 >> 16) & 0xffff; int valueInt = value & 0xff; low = (low + valueInt) % BASE; high = (low + high) % BASE; adler32 = (high << 16) | low; } int hash(byte[] bytes) { int hash = ((bytes[0] & 0xff) << 24 | (bytes[1] & 0xff) << 16 | (bytes[2] & 0xff) << 8) % HASH; if (hash < 0) { hash = hash + HASH; } return hash; } void writeBits(int value, int count) { buffer |= value << bitCount; bitCount += count; if (bitCount >= 16) { bytes.write(cast(byte) buffer); bytes.write(cast(byte) (buffer >>> 8)); buffer >>>= 16; bitCount -= 16; } } void alignToByte() { if (bitCount > 0) { bytes.write(cast(byte) buffer); if (bitCount > 8) bytes.write(cast(byte) (buffer >>> 8)); } buffer = 0; bitCount = 0; } void outputLiteral(byte literal) { int i = literal & 0xff; if (i <= 143) { // 0 through 143 are 8 bits long starting at 00110000 writeBits(mirrorBytes[0x30 + i], 8); } else { // 144 through 255 are 9 bits long starting at 110010000 writeBits(1 + 2 * mirrorBytes[0x90 - 144 + i], 9); } } Code findCode(int value, Code[] codes) { int i, j, k; i = -1; j = codes.length; while (true) { k = (j + i) / 2; if (value < codes[k].min) { j = k; } else if (value > codes[k].max) { i = k; } else { return codes[k]; } } } void outputMatch(int length, int distance) { Code d, l; int thisLength; while (length > 0) { // we can transmit matches of lengths 3 through 258 inclusive // so if length exceeds 258, we must transmit in several steps, // with 258 or less in each step if (length > 260) { thisLength = 258; } else if (length <= 258) { thisLength = length; } else { thisLength = length - 3; } length = length - thisLength; // find length code l = findCode(thisLength, lengthCodes); // transmit the length code // 256 through 279 are 7 bits long starting at 0000000 // 280 through 287 are 8 bits long starting at 11000000 if (l.code <= 279) { writeBits(mirrorBytes[(l.code - 256) * 2], 7); } else { writeBits(mirrorBytes[0xc0 - 280 + l.code], 8); } // transmit the extra bits if (l.extraBits !is 0) { writeBits(thisLength - l.min, l.extraBits); } // find distance code d = findCode(distance, distanceCodes); // transmit the distance code // 5 bits long starting at 00000 writeBits(mirrorBytes[d.code * 8], 5); // transmit the extra bits if (d.extraBits !is 0) { writeBits(distance - d.min, d.extraBits); } } } Match findLongestMatch(int position, Link firstPosition) { Link link = firstPosition; int numberOfMatches = 0; Match bestMatch = new Match(-1, -1); while (true) { int matchPosition = link.value; if (position - matchPosition < WINDOW && matchPosition !is 0) { int i; for (i = 1; position + i < inLength; i++) { if (istr[position + i] !is istr[matchPosition + i]) { break; } } if (i >= MIN_LENGTH) { if (i > bestMatch.length) { bestMatch.length = i; bestMatch.distance = position - matchPosition; } numberOfMatches = numberOfMatches + 1; if (numberOfMatches is MAX_MATCHES) { break; } } } link = link.next; if (link is null) { break; } } if (bestMatch.length < MIN_LENGTH || bestMatch.distance < 1 || bestMatch.distance > WINDOW) { return null; } return bestMatch; } void updateHashtable(int to, int from) { byte[] data = new byte[3]; int hashval; Link temp; for (int i = to; i < from; i++) { if (i + MIN_LENGTH > inLength) { break; } data[0] = istr[i]; data[1] = istr[i + 1]; data[2] = istr[i + 2]; hashval = hash(data); if (window[nextWindow].previous !is null) { window[nextWindow].previous.next = null; } else if (window[nextWindow].hash !is 0) { hashtable[window[nextWindow].hash].next = null; } window[nextWindow].hash = hashval; window[nextWindow].value = i; window[nextWindow].previous = null; temp = window[nextWindow].next = hashtable[hashval].next; hashtable[hashval].next = window[nextWindow]; if (temp !is null) { temp.previous = window[nextWindow]; } nextWindow = nextWindow + 1; if (nextWindow is WINDOW) { nextWindow = 0; } } } void compress() { int position, newPosition; byte[] data = new byte[3]; int hashval; for (int i = 0; i < HASH; i++) { hashtable[i] = new Link(); } for (int i = 0; i < WINDOW; i++) { window[i] = new Link(); } nextWindow = 0; Link firstPosition; Match match; int deferredPosition = -1; Match deferredMatch = null; writeBits(0x01, 1); // BFINAL = 0x01 (final block) writeBits(0x01, 2); // BTYPE = 0x01 (compression with fixed Huffman codes) // just output first byte so we never match at zero outputLiteral(istr[0]); position = 1; while (position < inLength) { if (inLength - position < MIN_LENGTH) { outputLiteral(istr[position]); position = position + 1; continue; } data[0] = istr[position]; data[1] = istr[position + 1]; data[2] = istr[position + 2]; hashval = hash(data); firstPosition = hashtable[hashval]; match = findLongestMatch(position, firstPosition); updateHashtable(position, position + 1); if (match !is null) { if (deferredMatch !is null) { if (match.length > deferredMatch.length + 1) { // output literal at deferredPosition outputLiteral(istr[deferredPosition]); // defer this match deferredPosition = position; deferredMatch = match; position = position + 1; } else { // output deferredMatch outputMatch(deferredMatch.length, deferredMatch.distance); newPosition = deferredPosition + deferredMatch.length; deferredPosition = -1; deferredMatch = null; updateHashtable(position + 1, newPosition); position = newPosition; } } else { // defer this match deferredPosition = position; deferredMatch = match; position = position + 1; } } else { // no match found if (deferredMatch !is null) { outputMatch(deferredMatch.length, deferredMatch.distance); newPosition = deferredPosition + deferredMatch.length; deferredPosition = -1; deferredMatch = null; updateHashtable(position + 1, newPosition); position = newPosition; } else { outputLiteral(istr[position]); position = position + 1; } } } writeBits(0, 7); // end of block code alignToByte(); } void compressHuffmanOnly() { int position; writeBits(0x01, 1); // BFINAL = 0x01 (final block) writeBits(0x01, 2); // BTYPE = 0x01 (compression with fixed Huffman codes) for (position = 0; position < inLength;) { outputLiteral(istr[position]); position = position + 1; } writeBits(0, 7); // end of block code alignToByte(); } void store() { // stored blocks are limited to 0xffff bytes int start = 0; int length = inLength; int blockLength; int BFINAL = 0x00; // BFINAL = 0x00 or 0x01 (if final block), BTYPE = 0x00 (no compression) while (length > 0) { if (length < 65535) { blockLength = length; BFINAL = 0x01; } else { blockLength = 65535; BFINAL = 0x00; } // write data header bytes.write(cast(byte) BFINAL); writeShortLSB(bytes, blockLength); // LEN writeShortLSB(bytes, blockLength ^ 0xffff); // NLEN (one's complement of LEN) // write actual data bytes.write(istr, start, blockLength); length = length - blockLength; start = start + blockLength; } } public byte[] deflate(byte[] input) { istr = input; inLength = input.length; // write zlib header bytes.write(cast(byte) 0x78); // window size = 0x70 (32768), compression method = 0x08 bytes.write(cast(byte) 0x9C); // compression level = 0x80 (default), check bits = 0x1C // compute checksum for (int i = 0; i < inLength; i++) { updateAdler(istr[i]); } //store(); //compressHuffmanOnly(); compress(); // write checksum writeInt(bytes, adler32); return bytes.toByteArray(); } }