1 | /* Copyright (C) 2001-2019 Artifex Software, Inc. |
2 | All Rights Reserved. |
3 | |
4 | This software is provided AS-IS with no warranty, either express or |
5 | implied. |
6 | |
7 | This software is distributed under license and may not be copied, |
8 | modified or distributed except as expressly authorized under the terms |
9 | of the license contained in the file LICENSE in this distribution. |
10 | |
11 | Refer to licensing information at http://www.artifex.com or contact |
12 | Artifex Software, Inc., 1305 Grant Avenue - Suite 200, Novato, |
13 | CA 94945, U.S.A., +1(415)492-9861, for further information. |
14 | */ |
15 | |
16 | /* |
17 | jbig2dec |
18 | */ |
19 | |
20 | #ifdef HAVE_CONFIG_H |
21 | #include "config.h" |
22 | #endif |
23 | #include "os_types.h" |
24 | |
25 | #include <stdio.h> |
26 | #include <stdlib.h> |
27 | |
28 | #include "jbig2.h" |
29 | #include "jbig2_priv.h" |
30 | #include "jbig2_arith.h" |
31 | |
32 | struct _Jbig2ArithState { |
33 | uint32_t C; |
34 | int A; |
35 | |
36 | int CT; |
37 | |
38 | uint32_t next_word; |
39 | int next_word_bytes; |
40 | |
41 | Jbig2WordStream *ws; |
42 | int offset; |
43 | }; |
44 | |
45 | #undef SOFTWARE_CONVENTION |
46 | |
47 | /* |
48 | A note on the "software conventions". |
49 | |
50 | Previously, I had misinterpreted the spec, and had thought that the |
51 | spec's description of the "software convention" was wrong. Now I |
52 | believe that this code is both correct and matches the spec, with |
53 | SOFTWARE_CONVENTION defined or not. Thanks to William Rucklidge for |
54 | the clarification. |
55 | |
56 | In any case, my benchmarking indicates no speed difference at all. |
57 | Therefore, for now we will just use the normative version. |
58 | |
59 | */ |
60 | |
61 | static void |
62 | jbig2_arith_bytein(Jbig2ArithState *as) |
63 | { |
64 | int new_bytes; |
65 | byte B; |
66 | |
67 | /* invariant: as->next_word_bytes > 0 */ |
68 | |
69 | /* Figure G.3 */ |
70 | B = (byte)((as->next_word >> 24) & 0xFF); |
71 | if (B == 0xFF) { |
72 | byte B1; |
73 | |
74 | if (as->next_word_bytes == 1) { |
75 | Jbig2WordStream *ws = as->ws; |
76 | |
77 | new_bytes = ws->get_next_word(ws, as->offset, &as->next_word); |
78 | as->next_word_bytes = new_bytes; |
79 | as->offset += new_bytes; |
80 | |
81 | B1 = (byte)((as->next_word >> 24) & 0xFF); |
82 | if (B1 > 0x8F) { |
83 | #ifdef JBIG2_DEBUG_ARITH |
84 | fprintf(stderr, "read %02x (aa)\n" , B); |
85 | #endif |
86 | #ifndef SOFTWARE_CONVENTION |
87 | as->C += 0xFF00; |
88 | #endif |
89 | as->CT = 8; |
90 | as->next_word = 0xFF000000 | (as->next_word >> 8); |
91 | as->next_word_bytes = 4; |
92 | as->offset--; |
93 | } else { |
94 | #ifdef JBIG2_DEBUG_ARITH |
95 | fprintf(stderr, "read %02x (a)\n" , B); |
96 | #endif |
97 | #ifdef SOFTWARE_CONVENTION |
98 | as->C += 0xFE00 - (B1 << 9); |
99 | #else |
100 | as->C += B1 << 9; |
101 | #endif |
102 | as->CT = 7; |
103 | } |
104 | } else { |
105 | B1 = (byte)((as->next_word >> 16) & 0xFF); |
106 | if (B1 > 0x8F) { |
107 | #ifdef JBIG2_DEBUG_ARITH |
108 | fprintf(stderr, "read %02x (ba)\n" , B); |
109 | #endif |
110 | #ifndef SOFTWARE_CONVENTION |
111 | as->C += 0xFF00; |
112 | #endif |
113 | as->CT = 8; |
114 | } else { |
115 | as->next_word_bytes--; |
116 | as->next_word <<= 8; |
117 | #ifdef JBIG2_DEBUG_ARITH |
118 | fprintf(stderr, "read %02x (b)\n" , B); |
119 | #endif |
120 | |
121 | #ifdef SOFTWARE_CONVENTION |
122 | as->C += 0xFE00 - (B1 << 9); |
123 | #else |
124 | as->C += (B1 << 9); |
125 | #endif |
126 | as->CT = 7; |
127 | } |
128 | } |
129 | } else { |
130 | #ifdef JBIG2_DEBUG_ARITH |
131 | fprintf(stderr, "read %02x\n" , B); |
132 | #endif |
133 | as->CT = 8; |
134 | as->next_word <<= 8; |
135 | as->next_word_bytes--; |
136 | if (as->next_word_bytes == 0) { |
137 | Jbig2WordStream *ws = as->ws; |
138 | |
139 | new_bytes = ws->get_next_word(ws, as->offset, &as->next_word); |
140 | as->offset += new_bytes; |
141 | as->next_word_bytes = new_bytes; |
142 | } |
143 | B = (byte)((as->next_word >> 24) & 0xFF); |
144 | #ifdef SOFTWARE_CONVENTION |
145 | as->C += 0xFF00 - (B << 8); |
146 | #else |
147 | as->C += (B << 8); |
148 | #endif |
149 | } |
150 | } |
151 | |
152 | /** Allocate and initialize a new arithmetic coding state |
153 | * the returned pointer can simply be freed; this does |
154 | * not affect the associated Jbig2WordStream. |
155 | */ |
156 | Jbig2ArithState * |
157 | jbig2_arith_new(Jbig2Ctx *ctx, Jbig2WordStream *ws) |
158 | { |
159 | Jbig2ArithState *result; |
160 | int new_bytes; |
161 | |
162 | result = jbig2_new(ctx, Jbig2ArithState, 1); |
163 | if (result == NULL) { |
164 | jbig2_error(ctx, JBIG2_SEVERITY_FATAL, -1, "failed to allocate arithmetic coding state" ); |
165 | return NULL; |
166 | } |
167 | |
168 | result->ws = ws; |
169 | |
170 | new_bytes = ws->get_next_word(ws, 0, &result->next_word); |
171 | result->next_word_bytes = new_bytes; |
172 | result->offset = new_bytes; |
173 | |
174 | /* Figure E.20 */ |
175 | #ifdef SOFTWARE_CONVENTION |
176 | result->C = (~(result->next_word >> 8)) & 0xFF0000; |
177 | #else |
178 | result->C = (result->next_word >> 8) & 0xFF0000; |
179 | #endif |
180 | |
181 | jbig2_arith_bytein(result); |
182 | result->C <<= 7; |
183 | result->CT -= 7; |
184 | result->A = 0x8000; |
185 | |
186 | return result; |
187 | } |
188 | |
189 | #define MAX_QE_ARRAY_SIZE 47 |
190 | |
191 | /* could put bit fields in to minimize memory usage */ |
192 | typedef struct { |
193 | unsigned short Qe; |
194 | byte mps_xor; /* mps_xor = index ^ NMPS */ |
195 | byte lps_xor; /* lps_xor = index ^ NLPS ^ (SWITCH << 7) */ |
196 | } Jbig2ArithQe; |
197 | |
198 | const Jbig2ArithQe jbig2_arith_Qe[MAX_QE_ARRAY_SIZE] = { |
199 | {0x5601, 1 ^ 0, 1 ^ 0 ^ 0x80}, |
200 | {0x3401, 2 ^ 1, 6 ^ 1}, |
201 | {0x1801, 3 ^ 2, 9 ^ 2}, |
202 | {0x0AC1, 4 ^ 3, 12 ^ 3}, |
203 | {0x0521, 5 ^ 4, 29 ^ 4}, |
204 | {0x0221, 38 ^ 5, 33 ^ 5}, |
205 | {0x5601, 7 ^ 6, 6 ^ 6 ^ 0x80}, |
206 | {0x5401, 8 ^ 7, 14 ^ 7}, |
207 | {0x4801, 9 ^ 8, 14 ^ 8}, |
208 | {0x3801, 10 ^ 9, 14 ^ 9}, |
209 | {0x3001, 11 ^ 10, 17 ^ 10}, |
210 | {0x2401, 12 ^ 11, 18 ^ 11}, |
211 | {0x1C01, 13 ^ 12, 20 ^ 12}, |
212 | {0x1601, 29 ^ 13, 21 ^ 13}, |
213 | {0x5601, 15 ^ 14, 14 ^ 14 ^ 0x80}, |
214 | {0x5401, 16 ^ 15, 14 ^ 15}, |
215 | {0x5101, 17 ^ 16, 15 ^ 16}, |
216 | {0x4801, 18 ^ 17, 16 ^ 17}, |
217 | {0x3801, 19 ^ 18, 17 ^ 18}, |
218 | {0x3401, 20 ^ 19, 18 ^ 19}, |
219 | {0x3001, 21 ^ 20, 19 ^ 20}, |
220 | {0x2801, 22 ^ 21, 19 ^ 21}, |
221 | {0x2401, 23 ^ 22, 20 ^ 22}, |
222 | {0x2201, 24 ^ 23, 21 ^ 23}, |
223 | {0x1C01, 25 ^ 24, 22 ^ 24}, |
224 | {0x1801, 26 ^ 25, 23 ^ 25}, |
225 | {0x1601, 27 ^ 26, 24 ^ 26}, |
226 | {0x1401, 28 ^ 27, 25 ^ 27}, |
227 | {0x1201, 29 ^ 28, 26 ^ 28}, |
228 | {0x1101, 30 ^ 29, 27 ^ 29}, |
229 | {0x0AC1, 31 ^ 30, 28 ^ 30}, |
230 | {0x09C1, 32 ^ 31, 29 ^ 31}, |
231 | {0x08A1, 33 ^ 32, 30 ^ 32}, |
232 | {0x0521, 34 ^ 33, 31 ^ 33}, |
233 | {0x0441, 35 ^ 34, 32 ^ 34}, |
234 | {0x02A1, 36 ^ 35, 33 ^ 35}, |
235 | {0x0221, 37 ^ 36, 34 ^ 36}, |
236 | {0x0141, 38 ^ 37, 35 ^ 37}, |
237 | {0x0111, 39 ^ 38, 36 ^ 38}, |
238 | {0x0085, 40 ^ 39, 37 ^ 39}, |
239 | {0x0049, 41 ^ 40, 38 ^ 40}, |
240 | {0x0025, 42 ^ 41, 39 ^ 41}, |
241 | {0x0015, 43 ^ 42, 40 ^ 42}, |
242 | {0x0009, 44 ^ 43, 41 ^ 43}, |
243 | {0x0005, 45 ^ 44, 42 ^ 44}, |
244 | {0x0001, 45 ^ 45, 43 ^ 45}, |
245 | {0x5601, 46 ^ 46, 46 ^ 46} |
246 | }; |
247 | |
248 | static void |
249 | jbig2_arith_renormd(Jbig2ArithState *as) |
250 | { |
251 | /* Figure E.18 */ |
252 | do { |
253 | if (as->CT == 0) |
254 | jbig2_arith_bytein(as); |
255 | as->A <<= 1; |
256 | as->C <<= 1; |
257 | as->CT--; |
258 | } while ((as->A & 0x8000) == 0); |
259 | } |
260 | |
261 | bool |
262 | jbig2_arith_decode(Jbig2ArithState *as, Jbig2ArithCx *pcx, int *code) |
263 | { |
264 | Jbig2ArithCx cx = *pcx; |
265 | const Jbig2ArithQe *pqe; |
266 | unsigned int index = cx & 0x7f; |
267 | bool D; |
268 | |
269 | if (index >= MAX_QE_ARRAY_SIZE) { |
270 | *code = -1; |
271 | return 0; |
272 | } else { |
273 | pqe = &jbig2_arith_Qe[index]; |
274 | } |
275 | |
276 | /* Figure E.15 */ |
277 | as->A -= pqe->Qe; |
278 | if ( |
279 | #ifdef SOFTWARE_CONVENTION |
280 | /* Note: I do not think this is correct. See above. */ |
281 | (as->C >> 16) < as->A |
282 | #else |
283 | !((as->C >> 16) < pqe->Qe) |
284 | #endif |
285 | ) { |
286 | #ifndef SOFTWARE_CONVENTION |
287 | as->C -= pqe->Qe << 16; |
288 | #endif |
289 | if ((as->A & 0x8000) == 0) { |
290 | /* MPS_EXCHANGE, Figure E.16 */ |
291 | if (as->A < pqe->Qe) { |
292 | D = 1 - (cx >> 7); |
293 | *pcx ^= pqe->lps_xor; |
294 | } else { |
295 | D = cx >> 7; |
296 | *pcx ^= pqe->mps_xor; |
297 | } |
298 | jbig2_arith_renormd(as); |
299 | *code = 0; |
300 | return D; |
301 | } else { |
302 | *code = 0; |
303 | return cx >> 7; |
304 | } |
305 | } else { |
306 | #ifdef SOFTWARE_CONVENTION |
307 | as->C -= (as->A) << 16; |
308 | #endif |
309 | /* LPS_EXCHANGE, Figure E.17 */ |
310 | if (as->A < pqe->Qe) { |
311 | as->A = pqe->Qe; |
312 | D = cx >> 7; |
313 | *pcx ^= pqe->mps_xor; |
314 | } else { |
315 | as->A = pqe->Qe; |
316 | D = 1 - (cx >> 7); |
317 | *pcx ^= pqe->lps_xor; |
318 | } |
319 | jbig2_arith_renormd(as); |
320 | *code = 0; |
321 | return D; |
322 | } |
323 | } |
324 | |
325 | #ifdef TEST |
326 | |
327 | static const byte test_stream[] = { |
328 | 0x84, 0xC7, 0x3B, 0xFC, 0xE1, 0xA1, 0x43, 0x04, 0x02, 0x20, 0x00, 0x00, |
329 | 0x41, 0x0D, 0xBB, 0x86, 0xF4, 0x31, 0x7F, 0xFF, 0x88, 0xFF, 0x37, 0x47, |
330 | 0x1A, 0xDB, 0x6A, 0xDF, 0xFF, 0xAC, |
331 | 0x00, 0x00 |
332 | }; |
333 | |
334 | #if defined(JBIG2_DEBUG) || defined(JBIG2_DEBUG_ARITH) |
335 | static void |
336 | jbig2_arith_trace(Jbig2ArithState *as, Jbig2ArithCx cx) |
337 | { |
338 | fprintf(stderr, "I = %2d, MPS = %d, A = %04x, CT = %2d, C = %08x\n" , cx & 0x7f, cx >> 7, as->A, as->CT, as->C); |
339 | } |
340 | #endif |
341 | |
342 | static int |
343 | test_get_word(Jbig2WordStream *self, size_t offset, uint32_t *word) |
344 | { |
345 | uint32_t val = 0; |
346 | int ret = 0; |
347 | |
348 | if (self == NULL || word == NULL) |
349 | return -1; |
350 | if (offset >= sizeof (test_stream)) |
351 | return 0; |
352 | |
353 | if (offset < sizeof(test_stream)) { |
354 | val |= test_stream[offset] << 24; |
355 | ret++; |
356 | } |
357 | if (offset + 1 < sizeof(test_stream)) { |
358 | val |= test_stream[offset + 1] << 16; |
359 | ret++; |
360 | } |
361 | if (offset + 2 < sizeof(test_stream)) { |
362 | val |= test_stream[offset + 2] << 8; |
363 | ret++; |
364 | } |
365 | if (offset + 3 < sizeof(test_stream)) { |
366 | val |= test_stream[offset + 3]; |
367 | ret++; |
368 | } |
369 | *word = val; |
370 | return ret; |
371 | } |
372 | |
373 | int |
374 | main(int argc, char **argv) |
375 | { |
376 | Jbig2Ctx *ctx; |
377 | Jbig2WordStream ws; |
378 | Jbig2ArithState *as; |
379 | int i; |
380 | Jbig2ArithCx cx = 0; |
381 | int code; |
382 | |
383 | ctx = jbig2_ctx_new(NULL, 0, NULL, NULL, NULL); |
384 | |
385 | ws.get_next_word = test_get_word; |
386 | as = jbig2_arith_new(ctx, &ws); |
387 | #ifdef JBIG2_DEBUG_ARITH |
388 | jbig2_arith_trace(as, cx); |
389 | #endif |
390 | |
391 | for (i = 0; i < 256; i++) { |
392 | #ifdef JBIG2_DEBUG_ARITH |
393 | bool D = |
394 | #else |
395 | (void) |
396 | #endif |
397 | jbig2_arith_decode(as, &cx, &code); |
398 | |
399 | #ifdef JBIG2_DEBUG_ARITH |
400 | fprintf(stderr, "%3d: D = %d, " , i, D); |
401 | jbig2_arith_trace(as, cx); |
402 | #endif |
403 | } |
404 | |
405 | jbig2_free(ctx->allocator, as); |
406 | |
407 | jbig2_ctx_free(ctx); |
408 | |
409 | return 0; |
410 | } |
411 | #endif |
412 | |