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
32struct _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
61static void
62jbig2_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 */
156Jbig2ArithState *
157jbig2_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 */
192typedef 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
198const 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
248static void
249jbig2_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
261bool
262jbig2_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
327static 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)
335static void
336jbig2_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
342static int
343test_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
373int
374main(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