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