blob: f751ff7c1affe3fba4891d6403e8c663ceecd712 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
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;
}
}
|
