package org.eclipse.swt.internal.image; | |
/* | |
* (c) Copyright IBM Corp. 2000, 2001. | |
* All Rights Reserved | |
*/ | |
public class PngHuffmanTable { | |
CodeLengthInfo[] codeLengthInfo; | |
int[] codeValues; | |
static final int MAX_CODE_LENGTH = 15; | |
static final int BAD_CODE = 0xFFFFFFF; | |
PngHuffmanTable (int[] lengths) { | |
super(); | |
initialize(lengths); | |
generateTable(lengths); | |
} | |
private void initialize(int[] lengths) { | |
codeValues = new int[lengths.length]; | |
for (int i = 0; i < codeValues.length; i++) { | |
codeValues[i] = i; | |
} | |
// minCodesByLength[n] : The smallest Huffman code of length n + 1. | |
// maxCodesByLength[n] : The largest Huffman code of length n + 1. | |
// indexesByLength[n] : Index into the values array. First value with a code of length n + 1. | |
codeLengthInfo = new CodeLengthInfo[MAX_CODE_LENGTH]; | |
for (int i = 0; i < MAX_CODE_LENGTH; i++) { | |
codeLengthInfo[i] = new CodeLengthInfo(); | |
codeLengthInfo[i].length = i; | |
codeLengthInfo[i].baseIndex = 0; | |
codeLengthInfo[i].min = BAD_CODE; | |
codeLengthInfo[i].max = -1; | |
} | |
} | |
private void generateTable(int[] lengths) { | |
// Sort the values. Primary key is code size. Secondary key is value. | |
for (int i = 0; i < lengths.length - 1; i++) { | |
for (int j = i + 1; j < lengths.length; j++) { | |
if (lengths[j] < lengths[i] | |
|| (lengths[j] == lengths[i] | |
&& codeValues[j] < codeValues[i])) | |
{ | |
int tmp; | |
tmp = lengths[j]; | |
lengths[j] = lengths[i]; | |
lengths[i] = tmp; | |
tmp = codeValues[j]; | |
codeValues[j] = codeValues[i]; | |
codeValues[i] = tmp; | |
} | |
} | |
} | |
// These values in these arrays correspond to the elements of the | |
// "values" array. The Huffman code for codeValues[N] is codes[N] | |
// and the length of the code is lengths[N]. | |
int[] codes = new int[lengths.length]; | |
int lastLength = 0; | |
int code = 0; | |
for (int i = 0; i < lengths.length; i++) { | |
while (lastLength != lengths[i]) { | |
lastLength++; | |
code <<= 1; | |
} | |
if (lastLength != 0) { | |
codes[i] = code; | |
code++; | |
} | |
} | |
int last = 0; | |
for (int i = 0; i < lengths.length; i++) { | |
if (last != lengths[i]) { | |
last = lengths[i]; | |
codeLengthInfo[last - 1].baseIndex = i; | |
codeLengthInfo[last - 1].min = codes[i]; | |
} | |
if (last != 0) codeLengthInfo[last - 1].max = codes[i]; | |
} | |
} | |
int getNextValue(PngDecodingDataStream stream) { | |
int code = stream.getNextIdatBit(); | |
int codelength = 0; | |
// Here we are taking advantage of the fact that 1 bits are used as | |
// a prefix to the longer codeValues. | |
while (code > codeLengthInfo[codelength].max && codelength < MAX_CODE_LENGTH) { | |
code = ((code << 1) | stream.getNextIdatBit()); | |
codelength++; | |
} | |
if (codelength >= MAX_CODE_LENGTH) stream.error(); | |
// Now we have a Huffman code of length (codelength + 1) that | |
// is somewhere in the range | |
// minCodesByLength[codelength]..maxCodesByLength[codelength]. | |
// This code is the (offset + 1)'th code of (codelength + 1); | |
int offset = code - codeLengthInfo[codelength].min; | |
// indexesByLength[codelength] is the first code of length (codelength + 1) | |
// so now we can look up the value for the Huffman code in the table. | |
int index = codeLengthInfo[codelength].baseIndex + offset; | |
return codeValues[index]; | |
} | |
class CodeValuePair { | |
int value; | |
int code; | |
} | |
class CodeLengthInfo { | |
int length; | |
int max; | |
int min; | |
int baseIndex; | |
} | |
} |