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.*;
013:
014: public class PngHuffmanTable {
015: CodeLengthInfo[] codeLengthInfo;
016: int[] codeValues;
017:
018: static final int MAX_CODE_LENGTH = 15;
019: static final int BAD_CODE = 0xFFFFFFF;
020: static final int incs[] = { 1391376, 463792, 198768, 86961, 33936,
021: 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1 };
022:
023: PngHuffmanTable(int[] lengths) {
024: super ();
025: initialize(lengths);
026: generateTable(lengths);
027: }
028:
029: private void initialize(int[] lengths) {
030: codeValues = new int[lengths.length];
031: for (int i = 0; i < codeValues.length; i++) {
032: codeValues[i] = i;
033: }
034:
035: // minCodesByLength[n] : The smallest Huffman code of length n + 1.
036: // maxCodesByLength[n] : The largest Huffman code of length n + 1.
037: // indexesByLength[n] : Index into the values array. First value with a code of length n + 1.
038: codeLengthInfo = new CodeLengthInfo[MAX_CODE_LENGTH];
039: for (int i = 0; i < MAX_CODE_LENGTH; i++) {
040: codeLengthInfo[i] = new CodeLengthInfo();
041: codeLengthInfo[i].length = i;
042: codeLengthInfo[i].baseIndex = 0;
043: codeLengthInfo[i].min = BAD_CODE;
044: codeLengthInfo[i].max = -1;
045: }
046: }
047:
048: private void generateTable(int[] lengths) {
049: // Sort the values using shellsort. Primary key is code size. Secondary key is value.
050: int codeValuesTemp;
051: for (int k = 0; k < 16; k++) {
052: for (int h = incs[k], i = h; i < lengths.length; i++) {
053: int v = lengths[i];
054: codeValuesTemp = codeValues[i];
055: int j = i;
056: while (j >= h
057: && (lengths[j - h] > v || (lengths[j - h] == v && codeValues[j
058: - h] > codeValuesTemp))) {
059: lengths[j] = lengths[j - h];
060: codeValues[j] = codeValues[j - h];
061: j -= h;
062: }
063: lengths[j] = v;
064: codeValues[j] = codeValuesTemp;
065: }
066: }
067:
068: // These values in these arrays correspond to the elements of the
069: // "values" array. The Huffman code for codeValues[N] is codes[N]
070: // and the length of the code is lengths[N].
071: int[] codes = new int[lengths.length];
072: int lastLength = 0;
073: int code = 0;
074: for (int i = 0; i < lengths.length; i++) {
075: while (lastLength != lengths[i]) {
076: lastLength++;
077: code <<= 1;
078: }
079: if (lastLength != 0) {
080: codes[i] = code;
081: code++;
082: }
083: }
084:
085: int last = 0;
086: for (int i = 0; i < lengths.length; i++) {
087: if (last != lengths[i]) {
088: last = lengths[i];
089: codeLengthInfo[last - 1].baseIndex = i;
090: codeLengthInfo[last - 1].min = codes[i];
091: }
092: if (last != 0)
093: codeLengthInfo[last - 1].max = codes[i];
094: }
095: }
096:
097: int getNextValue(PngDecodingDataStream stream) throws IOException {
098: int code = stream.getNextIdatBit();
099: int codelength = 0;
100:
101: // Here we are taking advantage of the fact that 1 bits are used as
102: // a prefix to the longer codeValues.
103: while (codelength < MAX_CODE_LENGTH
104: && code > codeLengthInfo[codelength].max) {
105: code = ((code << 1) | stream.getNextIdatBit());
106: codelength++;
107: }
108: if (codelength >= MAX_CODE_LENGTH)
109: stream.error();
110:
111: // Now we have a Huffman code of length (codelength + 1) that
112: // is somewhere in the range
113: // minCodesByLength[codelength]..maxCodesByLength[codelength].
114: // This code is the (offset + 1)'th code of (codelength + 1);
115: int offset = code - codeLengthInfo[codelength].min;
116:
117: // indexesByLength[codelength] is the first code of length (codelength + 1)
118: // so now we can look up the value for the Huffman code in the table.
119: int index = codeLengthInfo[codelength].baseIndex + offset;
120: return codeValues[index];
121: }
122:
123: class CodeLengthInfo {
124: int length;
125: int max;
126: int min;
127: int baseIndex;
128: }
129:
130: }
|