/
exr_huffman.dart
344 lines (273 loc) · 9.17 KB
/
exr_huffman.dart
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
import 'dart:typed_data';
import '../../image_exception.dart';
import '../../util/input_buffer.dart';
class ExrHuffman {
static void uncompress(
InputBuffer compressed, int nCompressed, Uint16List raw, int nRaw) {
if (nCompressed == 0) {
if (nRaw != 0) {
throw ImageException('Incomplete huffman data');
}
return;
}
var start = compressed.offset;
var im = compressed.readUint32();
var iM = compressed.readUint32();
compressed.skip(4); // tableLength
var nBits = compressed.readUint32();
if (im < 0 || im >= HUF_ENCSIZE || iM < 0 || iM >= HUF_ENCSIZE) {
throw ImageException('Invalid huffman table size');
}
compressed.skip(4);
var freq = List<int>(HUF_ENCSIZE);
freq.fillRange(0, HUF_ENCSIZE, 0);
var hdec = List<ExrHufDec>(HUF_DECSIZE);
for (var i = 0; i < HUF_DECSIZE; ++i) {
hdec[i] = ExrHufDec();
}
unpackEncTable(compressed, nCompressed - 20, im, iM, freq);
if (nBits > 8 * (nCompressed - (compressed.offset - start))) {
throw ImageException('Error in header for Huffman-encoded data '
'(invalid number of bits).');
}
buildDecTable(freq, im, iM, hdec);
decode(freq, hdec, compressed, nBits, iM, nRaw, raw);
}
static void decode(List<int> hcode, List<ExrHufDec> hdecod, InputBuffer input,
int ni, int rlc, int no, Uint16List out) {
var c_lc = [0, 0];
var ie = input.offset + (ni + 7) ~/ 8; // input byte size
var oi = 0;
// Loop on input bytes
while (input.offset < ie) {
getChar(c_lc, input);
// Access decoding table
while (c_lc[1] >= HUF_DECBITS) {
var pl = hdecod[(c_lc[0] >> (c_lc[1] - HUF_DECBITS)) & HUF_DECMASK];
if (pl.len != 0) {
// Get short code
c_lc[1] -= pl.len;
oi = getCode(pl.lit, rlc, c_lc, input, out, oi, no);
} else {
if (pl.p == null) {
throw ImageException('Error in Huffman-encoded data '
'(invalid code).');
}
// Search long code
int j;
for (j = 0; j < pl.lit; j++) {
var l = hufLength(hcode[pl.p[j]]);
while (c_lc[1] < l && input.offset < ie) {
// get more bits
getChar(c_lc, input);
}
if (c_lc[1] >= l) {
if (hufCode(hcode[pl.p[j]]) ==
((c_lc[0] >> (c_lc[1] - l)) & ((1 << l) - 1))) {
// Found : get long code
c_lc[1] -= l;
oi = getCode(pl.p[j], rlc, c_lc, input, out, oi, no);
break;
}
}
}
if (j == pl.lit) {
throw ImageException('Error in Huffman-encoded data '
'(invalid code).');
}
}
}
}
// Get remaining (short) codes
var i = (8 - ni) & 7;
c_lc[0] >>= i;
c_lc[1] -= i;
while (c_lc[1] > 0) {
var pl = hdecod[(c_lc[0] << (HUF_DECBITS - c_lc[1])) & HUF_DECMASK];
if (pl.len != 0) {
c_lc[1] -= pl.len;
oi = getCode(pl.lit, rlc, c_lc, input, out, oi, no);
} else {
throw ImageException('Error in Huffman-encoded data '
'(invalid code).');
}
}
if (oi != no) {
throw ImageException('Error in Huffman-encoded data '
'(decoded data are shorter than expected).');
}
}
static int getCode(int po, int rlc, List<int> c_lc, InputBuffer input,
Uint16List out, int oi, int oe) {
if (po == rlc) {
if (c_lc[1] < 8) {
getChar(c_lc, input);
}
c_lc[1] -= 8;
var cs = (c_lc[0] >> c_lc[1]) & 0xff;
if (oi + cs > oe) {
throw ImageException('Error in Huffman-encoded data '
'(decoded data are longer than expected).');
}
var s = out[oi - 1];
while (cs-- > 0) {
out[oi++] = s;
}
} else if (oi < oe) {
out[oi++] = po;
} else {
throw ImageException('Error in Huffman-encoded data '
'(decoded data are longer than expected).');
}
return oi;
}
static void buildDecTable(
List<int> hcode, int im, int iM, List<ExrHufDec> hdecod) {
// Init hashtable & loop on all codes.
// Assumes that hufClearDecTable(hdecod) has already been called.
for (; im <= iM; im++) {
var c = hufCode(hcode[im]);
var l = hufLength(hcode[im]);
if (c >> l != 0) {
// Error: c is supposed to be an l-bit code,
// but c contains a value that is greater
// than the largest l-bit number.
throw ImageException('Error in Huffman-encoded data '
'(invalid code table entry).');
}
if (l > HUF_DECBITS) {
// Long code: add a secondary entry
var pl = hdecod[(c >> (l - HUF_DECBITS))];
if (pl.len != 0) {
// Error: a short code has already
// been stored in table entry *pl.
throw ImageException('Error in Huffman-encoded data '
'(invalid code table entry).');
}
pl.lit++;
if (pl.p != null) {
var p = pl.p;
pl.p = List<int>(pl.lit);
for (var i = 0; i < pl.lit - 1; ++i) {
pl.p[i] = p[i];
}
} else {
pl.p = [0];
}
pl.p[pl.lit - 1] = im;
} else if (l != 0) {
// Short code: init all primary entries
var pi = (c << (HUF_DECBITS - l));
var pl = hdecod[pi];
for (var i = 1 << (HUF_DECBITS - l); i > 0; i--, pi++) {
pl = hdecod[pi];
if (pl.len != 0 || pl.p != null) {
// Error: a short code or a long code has
// already been stored in table entry *pl.
throw ImageException('Error in Huffman-encoded data '
'(invalid code table entry).');
}
pl.len = l;
pl.lit = im;
}
}
}
}
static void unpackEncTable(
InputBuffer p, int ni, int im, int iM, List<int> hcode) {
var pcode = p.offset;
var c_lc = [0, 0];
for (; im <= iM; im++) {
if (p.offset - pcode > ni) {
throw ImageException('Error in Huffman-encoded data '
'(unexpected end of code table data).');
}
var l = hcode[im] = getBits(6, c_lc, p); // code length
if (l == LONG_ZEROCODE_RUN) {
if (p.offset - pcode > ni) {
throw ImageException('Error in Huffman-encoded data '
'(unexpected end of code table data).');
}
var zerun = getBits(8, c_lc, p) + SHORTEST_LONG_RUN;
if (im + zerun > iM + 1) {
throw ImageException('Error in Huffman-encoded data '
'(code table is longer than expected).');
}
while (zerun-- != 0) {
hcode[im++] = 0;
}
im--;
} else if (l >= SHORT_ZEROCODE_RUN) {
var zerun = l - SHORT_ZEROCODE_RUN + 2;
if (im + zerun > iM + 1) {
throw ImageException('Error in Huffman-encoded data '
'(code table is longer than expected).');
}
while (zerun-- != 0) {
hcode[im++] = 0;
}
im--;
}
}
canonicalCodeTable(hcode);
}
static int hufLength(int code) => code & 63;
static int hufCode(int code) => code >> 6;
static void canonicalCodeTable(List<int> hcode) {
var n = List<int>(59);
n.fillRange(0, 59, 0);
// For each i from 0 through 58, count the
// number of different codes of length i, and
// store the count in n[i].
for (var i = 0; i < HUF_ENCSIZE; ++i) {
n[hcode[i]] += 1;
}
// For each i from 58 through 1, compute the
// numerically lowest code with length i, and
// store that code in n[i].
var c = 0;
for (var i = 58; i > 0; --i) {
var nc = ((c + n[i]) >> 1);
n[i] = c;
c = nc;
}
// hcode[i] contains the length, l, of the
// code for symbol i. Assign the next available
// code of length l to the symbol and store both
// l and the code in hcode[i].
for (var i = 0; i < HUF_ENCSIZE; ++i) {
var l = hcode[i];
if (l > 0) {
hcode[i] = l | (n[l]++ << 6);
}
}
}
static void getChar(List<int> c_lc, InputBuffer input) {
c_lc[0] = ((c_lc[0] << 8) | input.readByte()) & MASK_64;
c_lc[1] = (c_lc[1] + 8) & MASK_32;
}
static int getBits(int nBits, List<int> c_lc, InputBuffer input) {
while (c_lc[1] < nBits) {
c_lc[0] = ((c_lc[0] << 8) | input.readByte()) & MASK_64;
c_lc[1] = (c_lc[1] + 8) & MASK_32;
}
c_lc[1] -= nBits;
return (c_lc[0] >> c_lc[1]) & ((1 << nBits) - 1);
}
static const MASK_32 = (1 << 32) - 1;
static const MASK_64 = (1 << 64) - 1;
static const HUF_ENCBITS = 16; // literal (value) bit length
static const HUF_DECBITS = 14; // decoding bit size (>= 8)
static const HUF_ENCSIZE = (1 << HUF_ENCBITS) + 1; // encoding table size
static const HUF_DECSIZE = 1 << HUF_DECBITS; // decoding table size
static const HUF_DECMASK = HUF_DECSIZE - 1;
static const SHORT_ZEROCODE_RUN = 59;
static const LONG_ZEROCODE_RUN = 63;
static const SHORTEST_LONG_RUN = 2 + LONG_ZEROCODE_RUN - SHORT_ZEROCODE_RUN;
static const LONGEST_LONG_RUN = 255 + SHORTEST_LONG_RUN;
}
class ExrHufDec {
int len = 0;
int lit = 0;
List<int> p;
}