diff options
author | giraffedata <giraffedata@9d0c8265-081b-0410-96cb-a4ca84ce46f8> | 2014-06-22 00:57:10 +0000 |
---|---|---|
committer | giraffedata <giraffedata@9d0c8265-081b-0410-96cb-a4ca84ce46f8> | 2014-06-22 00:57:10 +0000 |
commit | 0ac1e193cb0c0b9ed6e6a8601cbb293218bededd (patch) | |
tree | 42b9153272c0fd2a2d815d3999f726fafe807d7a /converter/other/jbig/libjbig/jbig.c | |
parent | 482bb9cede2d7b8b83c81c3bc7fbecf90cf10dba (diff) | |
download | netpbm-mirror-0ac1e193cb0c0b9ed6e6a8601cbb293218bededd.tar.gz netpbm-mirror-0ac1e193cb0c0b9ed6e6a8601cbb293218bededd.tar.xz netpbm-mirror-0ac1e193cb0c0b9ed6e6a8601cbb293218bededd.zip |
Update to JBIG-KIT 2.1
git-svn-id: http://svn.code.sf.net/p/netpbm/code/trunk@2206 9d0c8265-081b-0410-96cb-a4ca84ce46f8
Diffstat (limited to 'converter/other/jbig/libjbig/jbig.c')
-rw-r--r-- | converter/other/jbig/libjbig/jbig.c | 1840 |
1 files changed, 1110 insertions, 730 deletions
diff --git a/converter/other/jbig/libjbig/jbig.c b/converter/other/jbig/libjbig/jbig.c index 90295d8b..ed0a9d08 100644 --- a/converter/other/jbig/libjbig/jbig.c +++ b/converter/other/jbig/libjbig/jbig.c @@ -1,15 +1,13 @@ /* - * Portable Free JBIG image compression library + * Portable JBIG image compression library * - * Markus Kuhn -- mkuhn@acm.org - * - * $Id: jbig.c,v 1.12 2000-04-08 11:42:18+01 mgk25 Rel $ + * Copyright 1995-2014 -- Markus Kuhn -- http://www.cl.cam.ac.uk/~mgk25/ * * This module implements a portable standard C encoder and decoder - * using the JBIG lossless bi-level image compression algorithm as - * specified in International Standard ISO 11544:1993 or equivalently - * as specified in ITU-T Recommendation T.82. See the file jbig.doc - * for usage instructions and application examples. + * using the JBIG1 lossless bi-level image compression algorithm + * specified in International Standard ISO 11544:1993 and + * ITU-T Recommendation T.82. See the file jbig.txt for usage + * instructions and application examples. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -27,41 +25,21 @@ * * If you want to use this program under different license conditions, * then contact the author for an arrangement. - * - * It is possible that certain products which can be built using this - * software module might form inventions protected by patent rights in - * some countries (e.g., by patents about arithmetic coding algorithms - * owned by IBM and AT&T in the USA). Provision of this software by the - * author does NOT include any licences for any patents. In those - * countries where a patent licence is required for certain applications - * of this software module, you will have to obtain such a licence - * yourself. */ #ifdef DEBUG #include <stdio.h> +#else +#define NDEBUG #endif #include <stdlib.h> +#include <string.h> #include <assert.h> #include "jbig.h" - -/* optional export of arithmetic coder functions for test purposes */ -#ifdef TEST_CODEC -#define ARITH -#define ARITH_INL -#else -#define ARITH static -#ifdef __GNUC__ -#define ARITH_INL static __inline__ -#else -#define ARITH_INL static -#endif -#endif - -#define MX_MAX 23 /* maximal supported mx offset for +#define MX_MAX 127 /* maximal supported mx offset for * adaptive template in the encoder */ #define TPB2CX 0x195 /* contexts for TP special pixels */ @@ -91,15 +69,15 @@ /* object code version id */ const char jbg_version[] = -" JBIG-KIT " JBG_VERSION " -- Markus Kuhn -- " -"$Id: jbig.c,v 1.12 2000-04-08 11:42:18+01 mgk25 Rel $ "; + "JBIG-KIT " JBG_VERSION " -- (c) 1995-2014 Markus Kuhn -- " + "Licence: " JBG_LICENCE "\n"; /* - * the following array specifies for each combination of the 3 + * The following array specifies for each combination of the 3 * ordering bits, which ii[] variable represents which dimension * of s->sde. */ -static const int index[8][3] = { +static const int iindex[8][3] = { { 2, 1, 0 }, /* no ordering bit set */ { -1, -1, -1}, /* SMID -> illegal combination */ { 2, 0, 1 }, /* ILEAVE */ @@ -110,96 +88,90 @@ static const int index[8][3] = { { -1, -1, -1 } /* SEQ + SMID + ILEAVE -> illegal combination */ }; +#define _(String) String /* to mark translatable string for GNU gettext */ /* - * Array [language][message] with text string error messages that correspond + * Array with English ASCII error messages that correspond * to return values from public functions in this library. */ -#define NEMSG 9 /* number of error codes */ -#define NEMSG_LANG 3 /* number of supported languages */ -static const char *errmsg[NEMSG_LANG][NEMSG] = { - /* English (JBG_EN) */ - { - "Everything is ok", /* JBG_EOK */ - "Reached specified maximum size", /* JBG_EOK_INTR */ - "Unexpected end of data", /* JBG_EAGAIN */ - "Not enough memory available", /* JBG_ENOMEM */ - "ABORT marker found", /* JBG_EABORT */ - "Unknown marker segment encountered", /* JBG_EMARKER */ - "Incremental BIE does not fit to previous one", /* JBG_ENOCONT */ - "Invalid data encountered", /* JBG_EINVAL */ - "Unimplemented features used" /* JBG_EIMPL */ - }, - /* German (JBG_DE_8859_1) */ - { - "Kein Problem aufgetreten", /* JBG_EOK */ - "Angegebene maximale Bildgr\366\337e erreicht", /* JBG_EOK_INTR */ - "Unerwartetes Ende der Daten", /* JBG_EAGAIN */ - "Nicht gen\374gend Speicher vorhanden", /* JBG_ENOMEM */ - "Es wurde eine Abbruch-Sequenz gefunden", /* JBG_EABORT */ - "Eine unbekannte Markierungssequenz wurde gefunden", /* JBG_EMARKER */ - "Neue Daten passen nicht zu vorangegangenen Daten", /* JBG_ENOCONT */ - "Es wurden ung\374ltige Daten gefunden", /* JBG_EINVAL */ - "Noch nicht implementierte Optionen wurden benutzt" /* JBG_EIMPL */ - }, - /* German (JBG_DE_UTF_8) */ - { - "Kein Problem aufgetreten", /* JBG_EOK */ - "Angegebene maximale Bildgr\303\266\303\237e erreicht", /* JBG_EOK_INTR */ - "Unerwartetes Ende der Daten", /* JBG_EAGAIN */ - "Nicht gen\303\274gend Speicher vorhanden", /* JBG_ENOMEM */ - "Es wurde eine Abbruch-Sequenz gefunden", /* JBG_EABORT */ - "Eine unbekannte Markierungssequenz wurde gefunden", /* JBG_EMARKER */ - "Neue Daten passen nicht zu vorangegangenen Daten", /* JBG_ENOCONT */ - "Es wurden ung\303\274ltige Daten gefunden", /* JBG_EINVAL */ - "Noch nicht implementierte Optionen wurden benutzt" /* JBG_EIMPL */ - } +static const char *errmsg[] = { + _("All OK"), /* JBG_EOK */ + _("Reached specified image size"), /* JBG_EOK_INTR */ + _("Unexpected end of input data stream"), /* JBG_EAGAIN */ + _("Not enough memory available"), /* JBG_ENOMEM */ + _("ABORT marker segment encountered"), /* JBG_EABORT */ + _("Unknown marker segment encountered"), /* JBG_EMARKER */ + _("Input data stream contains invalid data"), /* JBG_EINVAL */ + _("Input data stream uses unimplemented JBIG features"), /* JBG_EIMPL */ + _("Incremental BIE does not continue previous one") /* JBG_ENOCONT */ }; - /* * The following three functions are the only places in this code, were * C library memory management functions are called. The whole JBIG * library has been designed in order to allow multi-threaded - * execution. no static or global variables are used, so all fuctions + * execution. No static or global variables are used, so all fuctions * are fully reentrant. However if you want to use this multi-thread * capability and your malloc, realloc and free are not reentrant, * then simply add the necessary semaphores or mutex primitives below. + * In contrast to C's malloc() and realloc(), but like C's calloc(), + * these functions take two parameters nmemb and size that are multiplied + * before being passed on to the corresponding C function. + * This we can catch all overflows during a size_t multiplication a + * a single place. */ -static void *checked_malloc(size_t size) +#ifndef SIZE_MAX +#define SIZE_MAX ((size_t) -1) /* largest value of size_t */ +#endif + +static void *checked_malloc(size_t nmemb, size_t size) { void *p; - - p = malloc(size); + /* Full manual exception handling is ugly here for performance * reasons. If an adequate handling of lack of memory is required, - * then use C++ and throw a C++ exception here. */ + * then use C++ and throw a C++ exception instead of abort(). */ + + /* assert that nmemb * size <= SIZE_MAX */ + if (size > SIZE_MAX / nmemb) + abort(); + + p = malloc(nmemb * size); + if (!p) abort(); #if 0 - fprintf(stderr, "%p = malloc(%ld)\n", p, (long) size); + fprintf(stderr, "%p = malloc(%lu * %lu)\n", p, + (unsigned long) nmemb, (unsigned long) size); #endif return p; } -static void *checked_realloc(void *ptr, size_t size) +static void *checked_realloc(void *ptr, size_t nmemb, size_t size) { void *p; - p = realloc(ptr, size); /* Full manual exception handling is ugly here for performance * reasons. If an adequate handling of lack of memory is required, - * then use C++ and throw a C++ exception here. */ + * then use C++ and throw a C++ exception here instead of abort(). */ + + /* assert that nmemb * size <= SIZE_MAX */ + if (size > SIZE_MAX / nmemb) + abort(); + + p = realloc(ptr, nmemb * size); + if (!p) abort(); #if 0 - fprintf(stderr, "%p = realloc(%p, %ld)\n", p, ptr, (long) size); + fprintf(stderr, "%p = realloc(%p, %lu * %lu)\n", p, ptr, + (unsigned long) nmemb, (unsigned long) size); #endif return p; @@ -218,291 +190,6 @@ static void checked_free(void *ptr) -/* - * The next functions implement the arithmedic encoder and decoder - * required for JBIG. The same algorithm is also used in the arithmetic - * variant of JPEG. - */ - -#ifdef DEBUG -static long encoded_pixels = 0; -#endif - -ARITH void arith_encode_init(struct jbg_arenc_state *s, int reuse_st) -{ - int i; - - if (!reuse_st) - for (i = 0; i < 4096; s->st[i++] = 0); - s->c = 0; - s->a = 0x10000L; - s->sc = 0; - s->ct = 11; - s->buffer = -1; /* empty */ - - return; -} - - -ARITH void arith_encode_flush(struct jbg_arenc_state *s) -{ - unsigned long temp; - -#ifdef DEBUG - fprintf(stderr, " encoded pixels = %ld, a = %05lx, c = %08lx\n", - encoded_pixels, s->a, s->c); -#endif - - /* find the s->c in the coding interval with the largest - * number of trailing zero bits */ - if ((temp = (s->a - 1 + s->c) & 0xffff0000L) < s->c) - s->c = temp + 0x8000; - else - s->c = temp; - /* send remaining bytes to output */ - s->c <<= s->ct; - if (s->c & 0xf8000000L) { - /* one final overflow has to be handled */ - if (s->buffer >= 0) { - s->byte_out(s->buffer + 1, s->file); - if (s->buffer + 1 == MARKER_ESC) - s->byte_out(MARKER_STUFF, s->file); - } - /* output 0x00 bytes only when more non-0x00 will follow */ - if (s->c & 0x7fff800L) - for (; s->sc; --s->sc) - s->byte_out(0x00, s->file); - } else { - if (s->buffer >= 0) - s->byte_out(s->buffer, s->file); - /* T.82 figure 30 says buffer+1 for the above line! Typo? */ - for (; s->sc; --s->sc) { - s->byte_out(0xff, s->file); - s->byte_out(MARKER_STUFF, s->file); - } - } - /* output final bytes only if they are not 0x00 */ - if (s->c & 0x7fff800L) { - s->byte_out((s->c >> 19) & 0xff, s->file); - if (((s->c >> 19) & 0xff) == MARKER_ESC) - s->byte_out(MARKER_STUFF, s->file); - if (s->c & 0x7f800L) { - s->byte_out((s->c >> 11) & 0xff, s->file); - if (((s->c >> 11) & 0xff) == MARKER_ESC) - s->byte_out(MARKER_STUFF, s->file); - } - } - - return; -} - - -ARITH_INL void arith_encode(struct jbg_arenc_state *s, int cx, int pix) -{ - extern short jbg_lsz[]; - extern unsigned char jbg_nmps[], jbg_nlps[]; - register unsigned lsz, ss; - register unsigned char *st; - long temp; - -#ifdef DEBUG - ++encoded_pixels; -#endif - - assert(cx >= 0 && cx < 4096); - st = s->st + cx; - ss = *st & 0x7f; - assert(ss < 113); - lsz = jbg_lsz[ss]; - -#if 0 - fprintf(stderr, "pix = %d, cx = %d, mps = %d, st = %3d, lsz = 0x%04x, " - "a = 0x%05lx, c = 0x%08lx, ct = %2d, buf = 0x%02x\n", - pix, cx, !!(s->st[cx] & 0x80), ss, lsz, s->a, s->c, s->ct, - s->buffer); -#endif - - if (((pix << 7) ^ s->st[cx]) & 0x80) { - /* encode the less probable symbol */ - if ((s->a -= lsz) >= lsz) { - /* If the interval size (lsz) for the less probable symbol (LPS) - * is larger than the interval size for the MPS, then exchange - * the two symbols for coding efficiency, otherwise code the LPS - * as usual: */ - s->c += s->a; - s->a = lsz; - } - /* Check whether MPS/LPS exchange is necessary - * and chose next probability estimator status */ - *st &= 0x80; - *st ^= jbg_nlps[ss]; - } else { - /* encode the more probable symbol */ - if ((s->a -= lsz) & 0xffff8000L) - return; /* A >= 0x8000 -> ready, no renormalization required */ - if (s->a < lsz) { - /* If the interval size (lsz) for the less probable symbol (LPS) - * is larger than the interval size for the MPS, then exchange - * the two symbols for coding efficiency: */ - s->c += s->a; - s->a = lsz; - } - /* chose next probability estimator status */ - *st &= 0x80; - *st |= jbg_nmps[ss]; - } - - /* renormalization of coding interval */ - do { - s->a <<= 1; - s->c <<= 1; - --s->ct; - if (s->ct == 0) { - /* another byte is ready for output */ - temp = s->c >> 19; - if (temp & 0xffffff00L) { - /* handle overflow over all buffered 0xff bytes */ - if (s->buffer >= 0) { - ++s->buffer; - s->byte_out(s->buffer, s->file); - if (s->buffer == MARKER_ESC) - s->byte_out(MARKER_STUFF, s->file); - } - for (; s->sc; --s->sc) - s->byte_out(0x00, s->file); - s->buffer = temp & 0xff; /* new output byte, might overflow later */ - assert(s->buffer != 0xff); - /* can s->buffer really never become 0xff here? */ - } else if (temp == 0xff) { - /* buffer 0xff byte (which might overflow later) */ - ++s->sc; - } else { - /* output all buffered 0xff bytes, they will not overflow any more */ - if (s->buffer >= 0) - s->byte_out(s->buffer, s->file); - for (; s->sc; --s->sc) { - s->byte_out(0xff, s->file); - s->byte_out(MARKER_STUFF, s->file); - } - s->buffer = temp; /* buffer new output byte (can still overflow) */ - } - s->c &= 0x7ffffL; - s->ct = 8; - } - } while (s->a < 0x8000); - - return; -} - - -ARITH void arith_decode_init(struct jbg_ardec_state *s, int reuse_st) -{ - int i; - - if (!reuse_st) - for (i = 0; i < 4096; s->st[i++] = 0); - s->c = 0; - s->a = 1; - s->ct = 0; - s->result = JBG_OK; - s->startup = 1; - return; -} - - -ARITH_INL int arith_decode(struct jbg_ardec_state *s, int cx) -{ - extern short jbg_lsz[]; - extern unsigned char jbg_nmps[], jbg_nlps[]; - register unsigned lsz, ss; - register unsigned char *st; - int pix; - - /* renormalization */ - while (s->a < 0x8000 || s->startup) { - if (s->ct < 1 && s->result != JBG_READY) { - /* first we have to move a new byte into s->c */ - if (s->pscd_ptr >= s->pscd_end) { - s->result = JBG_MORE; - return -1; - } - if (*s->pscd_ptr == 0xff) - if (s->pscd_ptr + 1 >= s->pscd_end) { - s->result = JBG_MARKER; - return -1; - } else { - if (*(s->pscd_ptr + 1) == MARKER_STUFF) { - s->c |= 0xffL << (8 - s->ct); - s->ct += 8; - s->pscd_ptr += 2; - s->result = JBG_OK; - } else - s->result = JBG_READY; - } - else { - s->c |= (long)*(s->pscd_ptr++) << (8 - s->ct); - s->ct += 8; - s->result = JBG_OK; - } - } - s->c <<= 1; - s->a <<= 1; - --s->ct; - if (s->a == 0x10000L) - s->startup = 0; - } - - st = s->st + cx; - ss = *st & 0x7f; - assert(ss < 113); - lsz = jbg_lsz[ss]; - -#if 0 - fprintf(stderr, "cx = %d, mps = %d, st = %3d, lsz = 0x%04x, a = 0x%05lx, " - "c = 0x%08lx, ct = %2d\n", - cx, !!(s->st[cx] & 0x80), ss, lsz, s->a, s->c, s->ct); -#endif - - if ((s->c >> 16) < (s->a -= lsz)) - if (s->a & 0xffff8000L) - return *st >> 7; - else { - /* MPS_EXCHANGE */ - if (s->a < lsz) { - pix = 1 - (*st >> 7); - /* Check whether MPS/LPS exchange is necessary - * and chose next probability estimator status */ - *st &= 0x80; - *st ^= jbg_nlps[ss]; - } else { - pix = *st >> 7; - *st &= 0x80; - *st |= jbg_nmps[ss]; - } - } - else { - /* LPS_EXCHANGE */ - if (s->a < lsz) { - s->c -= s->a << 16; - s->a = lsz; - pix = *st >> 7; - *st &= 0x80; - *st |= jbg_nmps[ss]; - } else { - s->c -= s->a << 16; - s->a = lsz; - pix = 1 - (*st >> 7); - /* Check whether MPS/LPS exchange is necessary - * and chose next probability estimator status */ - *st &= 0x80; - *st ^= jbg_nlps[ss]; - } - } - - return pix; -} - - /* * Memory management for buffers which are used for temporarily @@ -532,7 +219,7 @@ static struct jbg_buf *jbg_buf_init(struct jbg_buf **free_list) *free_list = new_block->next; } else { /* request a new memory block */ - new_block = (struct jbg_buf *) checked_malloc(sizeof(struct jbg_buf)); + new_block = (struct jbg_buf *) checked_malloc(1, sizeof(struct jbg_buf)); } new_block->len = 0; new_block->next = NULL; @@ -668,7 +355,8 @@ static void jbg_buf_output(struct jbg_buf **head, /* - * Calculate y = ceil(x/2) applied n times. This function is used to + * Calculate y = ceil(x/2) applied n times, which is equivalent to + * y = ceil(x/(2^n)). This function is used to * determine the number of pixels per row or column after n resolution * reductions. E.g. X[d-1] = jbg_ceil_half(X[d], 1) and X[0] = * jbg_ceil_half(X[d], d) as defined in clause 6.2.3 of T.82. @@ -677,12 +365,405 @@ unsigned long jbg_ceil_half(unsigned long x, int n) { unsigned long mask; + assert(n >= 0 && n < 32); mask = (1UL << n) - 1; /* the lowest n bits are 1 here */ return (x >> n) + ((mask & x) != 0); } /* + * Set L0 (the number of lines in a stripe at lowest resolution) + * to a default value, such that there are about 35 stripes, as + * suggested in Annex C of ITU-T T.82, without exceeding the + * limit 128/2^D suggested in Annex A. + */ +static void jbg_set_default_l0(struct jbg_enc_state *s) +{ + s->l0 = jbg_ceil_half(s->yd, s->d) / 35; /* 35 stripes/image */ + while ((s->l0 << s->d) > 128) /* but <= 128 lines/stripe */ + --s->l0; + if (s->l0 < 2) s->l0 = 2; +} + + +/* + * Calculate the number of stripes, as defined in clause 6.2.3 of T.82. + */ +static unsigned long jbg_stripes(unsigned long l0, unsigned long yd, + unsigned long d) +{ + unsigned long y0 = jbg_ceil_half(yd, d); + + return y0 / l0 + (y0 % l0 != 0); +} + + +/* + * Resolution reduction table given by ITU-T T.82 Table 17 + */ + +static char jbg_resred[4096] = { + 0,0,0,1,0,0,0,1,0,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1, + 0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1, + 0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1, + 1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0,0,0,0,1,0,1,0,0,1,1,1,0,1,1, + 0,0,0,1,0,0,0,1,0,0,1,0,0,0,1,1,0,1,1,1,0,0,0,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,1,1,1,0,1,0,1,0,0,1,1,1,0,1,1,0,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,1,0,0,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1, + 1,0,0,1,0,0,1,1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1, + 0,0,1,1,0,0,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,0,1,1,0,1,1,1,1,1,1,0,1,1,1,0, + 0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1, + 0,0,0,1,0,0,0,1,0,1,1,0,1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1, + 1,1,1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1, + 1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,1, + 0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,1,1,1,0,1,0,1,0,1,1,0,1,0,1,1,0,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,1,1,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,1,0,1,0,0,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,1,0,0,1,1,1,1,1,1,0,1,1,1,1,0,1,1, + 1,0,0,1,0,0,1,0,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0, + 0,0,1,0,1,1,1,1,0,0,0,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,0, + 0,0,0,0,1,0,0,1,0,0,1,1,0,1,1,1,0,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,1,1,0,1,0,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,1,1,0,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1, + 0,0,1,0,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,0,1,1,0,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,1, + 0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,1,0,0,1,0,0,1,1, + 0,0,0,0,0,0,0,1,0,1,1,1,0,1,0,1,0,0,1,0,0,0,0,1,0,1,0,1,0,1,0,1, + 0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,1,0,0,0,0,0,0,0,1,1,1,1,0,1,1,1, + 0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,1,0,1,0,1,1,0,0,0,1,0,0,1,1, + 0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1,1,1,0,0,1,1, + 0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,1,0,0,0,0,0,0,1, + 0,0,1,0,0,1,1,1,0,0,0,0,1,0,0,1,0,0,0,1,1,1,1,0,1,0,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,1,0, + 0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,1,1,1,0,1,1,1, + 0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,1,1,0,1,0,0,0,1,1,0,1,0,0,0,0,1,1,1,1,0,0,1,1,1,0,1,1,0,0,1,1, + 0,0,0,0,0,0,0,0,1,1,0,1,0,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1, + 0,0,1,1,0,0,1,1,0,0,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,1,0,0,0,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1, + 0,0,0,1,0,0,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,0,0,1,0,0,1,0,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1, + 0,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1, + 0,0,1,1,1,1,1,1,0,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1, + 0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,1,1,0,1,1, + 0,0,0,1,0,0,0,1,0,0,1,0,0,0,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,1,1,1,0,1,0,1,0,0,1,0,1,0,1,1,0,1,1,1,0,1,1,1, + 0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,1,0,1,0,1,1,0,1,1,0,1,1,1,1,1,1,1, + 0,0,0,0,1,0,0,1,0,0,1,1,0,0,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,1,1,1,1,1,0,1,1, + 1,0,1,0,1,0,0,1,1,0,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,1,0,1,1,0,1,1,1, + 0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,1,1,0,1,1,0,1,1,1,1, + 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,1,0,1,0,1,0,1,1,0,1,0,1,0,0,0,1,1,1,1,1,1,1,1,1, + 1,1,1,0,1,0,0,0,1,1,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1, + 1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,1,1,0,1,1, + 0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,0,1,1,0,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,1,1,1,0,1,0,1,0,0,1,0,1,0,0,1,0,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,1,0,1,1,0,1,1,0,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,1,0,1,0,0,0,1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1, + 1,0,0,0,1,0,0,0,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,1,1,1,1,0,1,1,0, + 0,0,1,1,1,1,1,1,0,0,0,0,1,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,1,1,0,1,1,1,1,1,1,1, + 0,0,0,0,1,0,0,0,0,0,0,1,0,0,1,1,0,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1, + 0,0,1,0,1,0,1,1,0,0,1,0,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1, + 0,0,1,0,1,0,1,1,0,1,1,1,1,1,1,1,0,0,1,1,1,0,1,1,0,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,1, + 0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1, + 0,0,0,0,0,0,0,1,0,1,1,1,0,1,0,1,0,0,1,0,0,0,0,1,0,1,0,1,0,1,0,1, + 0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0,1,0,1,0,0,1,1, + 0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,1, + 0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,1,1, + 0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,1, + 1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,1,1,0,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,1,0,0,0,0,0,0,0, + 0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,1,1, + 0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0, + 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1, + 0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1, + 0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,1,1,1,1,1,1, + 0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,1, + 0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,0,1,1,0,0,0,1,0,1,1,1,0,1,1,1 +}; + +/* + * Deterministic prediction tables given by ITU-T T.82 tables + * 19 to 22. The table below is organized differently, the + * index bits are permutated for higher efficiency. + */ + +static char jbg_dptable[256 + 512 + 2048 + 4096] = { + /* phase 0: offset=0 */ + 0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2, + 0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,0,2,2,2,2,2,2,0,2,2,2,2,2,2,2, + 0,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2,0,0,2,2,2,2,2,2,0,2,0,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + /* phase 1: offset=256 */ + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2, + 0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,0,2,2,2,2,2,0,2,0,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2, + 0,2,2,2,2,1,2,1,2,2,2,2,1,1,1,1,2,0,2,0,2,2,2,2,0,2,0,2,2,2,2,2, + 0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,0,0,2,2,2,2,0,2,2,2,2,2,2,2, + 0,2,0,2,2,2,2,2,2,2,2,2,2,0,2,0,2,2,0,0,2,2,2,2,2,0,0,2,2,2,2,2, + 0,2,2,2,2,1,2,1,2,2,2,2,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1, + 1,2,1,2,2,2,2,2,2,2,2,2,2,1,2,2,2,2,1,1,2,2,2,2,2,0,2,2,2,2,2,2, + 2,2,2,2,2,0,2,0,2,2,2,2,0,0,0,0,0,2,0,2,2,2,2,2,0,2,2,2,2,2,2,2, + 0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,0,2,2,2,2,0,2,0,2,2,2,2,2, + 2,2,2,2,2,1,1,1,2,2,2,2,1,1,1,1,1,2,1,2,2,2,2,2,2,2,2,2,2,2,2,1, + 2,2,2,2,2,2,2,2,2,2,2,2,2,0,1,2,0,2,0,2,2,2,2,2,0,2,0,2,2,2,2,1, + 0,2,0,2,2,1,2,1,2,2,2,2,1,1,1,1,0,0,0,0,2,2,2,2,0,2,0,2,2,2,2,1, + 2,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,2,2,0,0,0,2,2,2,2,2, + 2,2,2,2,2,1,2,1,2,2,2,2,2,2,2,1,2,2,2,2,2,2,2,2,1,2,1,2,2,2,2,1, + 2,2,2,2,2,2,2,2,0,2,0,2,2,1,2,2,2,2,2,2,2,2,2,2,0,0,0,2,2,2,2,2, + /* phase 2: offset=768 */ + 2,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,2,2,2,2,1,1,1,1, + 0,2,2,2,2,1,2,1,2,2,2,2,1,2,1,2,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1, + 2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,0,2,2,1,2,1,2,2,2,2,2,1,1,1, + 2,0,2,2,2,1,2,1,0,2,2,2,1,2,1,2,2,2,2,0,2,2,2,2,0,2,0,2,2,2,2,2, + 0,2,0,0,1,1,1,1,2,2,2,2,1,1,1,1,0,2,0,2,1,1,1,1,2,2,2,2,1,1,1,1, + 2,2,0,2,2,2,1,2,2,2,2,2,1,2,1,2,2,2,0,2,2,1,2,1,0,2,0,2,1,1,1,1, + 2,0,0,2,2,2,2,2,0,2,0,2,2,0,2,0,2,0,2,0,2,2,2,1,2,2,0,2,1,1,2,1, + 2,2,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,1, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,2,2,2,2,1,1,1,1, + 0,0,0,0,2,2,2,2,0,0,0,0,2,2,2,2,0,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,0,2,2,2,2,1,0,2,2,2,1,1,1,1,2,0,2,2,2,2,2,2,0,2,0,2,2,1,2,1, + 2,0,2,0,2,2,2,2,0,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,2,2, + 0,2,2,2,1,2,1,2,2,2,2,2,2,2,2,2,0,2,2,2,2,2,1,2,2,2,2,2,2,2,2,2, + 2,2,0,2,2,2,2,2,2,2,2,2,2,2,0,2,2,0,0,2,2,1,2,1,0,2,2,2,1,1,1,1, + 2,2,2,0,2,2,2,2,2,2,0,2,2,0,2,0,2,1,2,2,2,2,2,2,1,2,1,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,0,2,2,2,1, + 0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,2,1,1,1,2,2,2,2,1,1,1,1, + 2,2,2,1,2,2,2,2,2,2,1,2,0,0,0,0,2,2,0,2,2,1,2,2,2,2,2,2,1,1,1,1, + 2,0,0,0,2,2,2,2,0,2,2,2,2,2,2,0,2,2,2,0,2,2,2,2,2,0,0,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,0,2,2,1,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,1, + 0,2,0,2,2,1,1,2,2,2,2,2,2,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,1,2,2, + 2,0,2,0,2,1,2,1,0,2,0,2,2,2,1,2,2,0,2,0,2,2,2,2,0,2,0,2,2,2,1,2, + 2,2,2,0,2,2,2,2,2,2,0,2,2,2,2,2,2,2,1,2,2,2,2,2,2,0,1,2,2,2,2,1, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1, + 0,2,2,2,1,2,1,2,2,2,2,2,2,2,2,2,0,2,2,2,2,2,1,2,2,2,2,2,2,2,2,2, + 2,0,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2,0,0,2,2,1,2,1,0,2,2,2,1,1,1,1, + 2,0,2,0,2,1,2,2,0,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,0,2,2,1,2,2, + 2,0,2,2,2,2,2,2,2,0,2,2,2,2,2,2,2,0,2,0,2,2,2,2,0,0,0,0,2,1,2,1, + 2,2,2,2,2,2,2,0,2,2,2,2,2,2,2,0,2,2,2,2,2,1,2,0,0,2,2,2,1,2,2,2, + 0,0,2,0,2,2,2,2,0,2,0,2,2,0,2,0,1,1,1,2,2,2,2,2,2,2,2,2,2,1,1,1, + 2,2,2,2,2,2,2,2,2,0,2,2,2,2,2,1,2,2,2,2,2,2,2,2,2,0,2,0,2,2,2,1, + 2,2,0,0,2,2,2,2,2,2,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,2,2,2,2,1,1,1,1, + 0,2,2,2,1,2,1,2,2,2,2,2,2,2,2,2,0,2,2,2,2,2,1,2,2,2,2,2,2,2,2,2, + 2,0,0,2,2,2,2,2,0,2,0,2,2,2,2,2,1,0,1,2,2,2,2,1,0,2,2,2,1,1,1,1, + 2,2,2,2,2,2,2,2,2,2,0,2,2,0,2,0,2,1,2,2,2,2,2,2,2,2,0,2,2,1,2,2, + 0,2,0,0,1,1,1,1,0,2,2,2,1,1,1,1,2,2,2,2,2,2,2,2,2,0,2,2,1,2,1,1, + 2,2,0,2,2,1,2,2,2,2,2,2,1,2,2,2,2,0,2,2,2,2,2,2,0,2,0,2,1,2,1,1, + 2,0,2,0,2,2,2,2,0,2,0,2,2,1,2,2,2,2,2,2,2,2,2,2,2,1,2,2,2,2,2,1, + 2,2,2,2,2,2,2,2,2,0,2,2,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1, + 0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 0,2,2,2,2,0,2,0,2,2,2,2,0,0,0,0,2,2,2,2,2,1,1,2,2,2,2,2,1,2,2,2, + 2,0,2,2,2,1,2,1,0,2,2,2,2,2,1,2,2,0,2,0,2,2,2,2,0,2,0,2,2,1,2,2, + 0,2,0,0,2,2,2,2,1,2,2,2,2,2,2,0,2,1,2,2,2,2,2,2,1,2,2,2,2,2,2,2, + 0,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,2,1,0,2,2, + 0,0,0,2,2,1,1,1,2,2,2,2,1,2,2,2,2,0,2,0,2,2,2,1,2,2,2,2,1,2,1,2, + 0,0,0,0,2,2,2,2,2,2,0,2,2,1,2,2,2,1,2,1,2,2,2,2,1,2,1,2,0,2,2,2, + 2,0,2,0,2,2,2,2,2,0,2,2,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1, + 0,2,2,2,1,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,1,2,2,2,2,2,0,2,2,1,2,2,0,0,0,2,2,2,2,2,1,2,2,0,2,2,2,1,2,1,2, + 2,0,2,0,2,2,2,2,0,2,0,2,2,1,2,2,0,2,0,0,2,2,2,2,2,2,2,2,2,1,2,2, + 2,2,2,2,2,2,2,2,2,0,2,2,2,2,2,1,2,2,2,2,2,2,2,2,2,0,2,0,2,2,2,1, + 1,2,0,2,2,1,2,1,2,2,2,2,1,2,2,2,2,0,2,0,2,2,2,2,2,0,2,2,1,1,1,1, + 0,2,2,2,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,0,2,2,1,2,1, + 2,2,0,0,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1, + 2,2,2,0,2,2,2,2,2,2,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,1,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,0,2, + 2,0,2,0,2,2,2,2,2,1,1,2,2,2,2,2,2,2,2,2,2,2,2,1,0,2,0,2,2,2,1,2, + 2,0,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2, + 2,0,2,0,2,2,2,2,2,0,2,0,2,2,2,2,2,0,2,0,2,2,2,2,0,0,0,0,2,1,2,1, + 2,2,2,2,2,1,2,1,0,2,0,2,2,2,2,2,2,0,2,0,2,2,2,2,0,2,0,2,2,2,2,1, + 2,0,2,0,2,2,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,0, + 2,0,2,0,2,2,2,1,2,2,2,0,2,2,2,1,2,0,2,0,2,2,2,2,0,0,0,2,2,2,2,1, + 2,0,2,0,2,2,2,2,2,2,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,2, + /* phase 3: offset=2816 */ + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1, + 0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,1,2,1,2,0,2,0,1,2,1,2,0,2,0,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,0,2,2,2,1,2,0,2,2,2,1,2,2,2,2,0,2,0,2,1,2,1,0,0,0,0,1,1,1,1, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,0,2,2,2,1,2, + 2,2,2,1,2,2,2,0,1,1,1,1,0,0,0,0,2,2,2,2,2,2,2,2,2,0,2,0,2,1,2,1, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,0,0,0,0,1,1,1,1, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,0,2,1,2,1,0,0,0,0,1,1,1,1, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,2,1,2,0,2,0,2, + 2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,0,2,0,2,1,2,1,2,0,2,0,2,1,2,1, + 2,0,0,0,2,1,1,1,0,0,0,0,1,1,1,1,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2, + 2,0,2,2,2,1,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,0,0,2,0,1,1,2,1, + 2,2,2,0,2,2,2,1,2,1,2,2,2,0,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1, + 0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,2,0,2,0,2,1,2,1,0,0,0,0,1,1,1,1, + 2,0,0,2,2,1,1,2,2,2,2,2,2,2,2,2,2,1,2,1,2,0,2,0,2,1,1,1,2,0,0,0, + 2,1,2,1,2,0,2,0,1,2,1,2,0,2,0,2,2,2,2,0,2,2,2,1,2,0,2,0,2,1,2,1, + 2,0,2,0,2,1,2,1,0,0,0,0,1,1,1,1,2,2,2,2,2,2,2,2,2,0,2,0,2,1,2,1, + 2,2,2,2,2,2,2,2,2,0,0,0,2,1,1,1,2,2,2,2,2,2,2,2,2,0,2,0,2,1,2,1, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2, + 0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2, + 2,0,0,0,2,1,1,1,0,0,0,0,1,1,1,1,2,0,2,0,2,1,2,1,0,0,2,0,1,1,2,1, + 2,2,1,2,2,2,0,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,0,0,0,2,1,1,1, + 2,2,2,1,2,2,2,0,2,1,1,1,2,0,0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,1,2,1,2,0,2,0,1,2,1,2,0,2,0,2, + 2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1, + 2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,0,0,0,2,1,1,1,0,0,0,0,1,1,1,1, + 2,0,2,2,2,1,2,2,0,0,2,0,1,1,2,1,2,1,2,1,2,0,2,0,2,2,2,2,2,2,2,2, + 2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,0,0,0,0,1,1,1,1, + 2,0,0,0,2,1,1,1,0,0,0,0,1,1,1,1,2,2,2,2,2,2,2,2,2,1,0,2,2,0,1,2, + 2,2,2,1,2,2,2,0,2,1,1,1,2,0,0,0,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1, + 2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1, + 0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,1,2,2,2,0,2,2,2,2,2,2,2,2,2,2, + 2,1,2,1,2,0,2,0,1,2,1,1,0,2,0,0,0,0,2,1,1,1,2,0,0,0,0,0,1,1,1,1, + 2,2,2,2,2,2,2,2,1,2,2,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,0,2,1,2,1,2,0,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,0,2,2,2,1,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,1,2,2,2,0,2,2,2,2,0,2,2,2,1,2,2,2,0,0,2,2,1,1, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2, + 0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,1,2,2,2,0,2,2,2,2,2,2,2,2,2, + 2,0,2,0,2,1,2,1,0,0,0,0,1,1,1,1,2,2,2,2,2,2,2,2,0,0,0,0,1,1,1,1, + 2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,0,0,0,2,1,1,1, + 2,2,2,0,2,2,2,1,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2, + 2,0,2,2,2,1,2,2,2,0,2,0,2,1,2,1,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1, + 2,1,2,1,2,0,2,0,1,2,1,2,0,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,1,2,1,2,0,2,0,1,2,1,1,0,2,0,0,2,0,2,2,2,1,2,2,0,2,1,2,1,2,0,2, + 2,2,2,1,2,2,2,0,2,2,1,2,2,2,0,2,2,1,2,2,2,0,2,2,2,2,0,2,2,2,1,2, + 0,0,2,0,1,1,2,1,0,0,1,0,1,1,0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,0,2,2,2,1,1,2,2,2,0,2,2,2,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1, + 2,2,2,2,2,2,2,2,2,1,2,2,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1, + 2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,0,0,2,2,1,1,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2, + 0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,1,2,2,2,0,2,2,2,2,2,2,2,2,2, + 2,0,0,0,2,1,1,1,0,0,0,0,1,1,1,1,2,2,2,1,2,2,2,0,2,1,2,1,2,0,2,0, + 2,1,2,2,2,0,2,2,2,2,2,2,2,2,2,2,0,2,0,0,1,2,1,1,2,0,0,0,2,1,1,1, + 2,2,2,2,2,2,2,2,2,1,1,1,2,0,0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,0,2,2,2,1,2,2,0,2,2,2,1,2,2,1,2,1,2,0,2,0,2,0,2,2,2,1,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,2,2,2,0,2,2,2,1,1,1,2,0,0,0, + 2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,0,2,0,0,1,2,1,1, + 2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,0,2,2,2,1,2,2,2, + 2,1,2,1,2,0,2,0,2,1,2,2,2,0,2,2,2,2,2,0,2,2,2,1,2,0,2,0,2,1,2,1, + 2,0,2,0,2,1,2,1,0,2,0,2,1,2,1,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2, + 2,2,2,2,2,2,2,2,0,2,0,2,1,2,1,2,2,2,2,2,2,2,2,2,0,1,0,0,1,0,1,1, + 2,2,2,2,2,2,2,2,2,1,2,2,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,2,2,1,2,2,2,0,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,1,2,2,1,0,2,0,2,2,2,1,2,2,2, + 2,2,2,2,2,2,2,2,1,2,2,2,0,2,2,2,2,2,2,0,2,2,2,1,2,2,0,2,2,2,1,2, + 2,0,2,0,2,1,2,1,0,2,0,2,1,2,1,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2, + 0,2,0,0,1,2,1,1,2,0,0,0,2,1,1,1,2,2,2,2,2,2,2,2,1,0,1,2,0,1,0,2, + 2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,1,2,2,2,0,2,2,1,1,2,2,0,0,2,2, + 0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,1,2,1,2,0,2,0,2,1,2,2,2,0,2,2,2,0,2,2,2,1,2,2,0,2,2,2,1,2,2,2, + 0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,1,2,2,2,0,2,2,2, + 2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,0,2,1,2,1,2, + 0,0,0,0,1,1,1,1,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,2,1,2,0,2,0,2,2,0,2,2,2,1,2, + 2,0,2,0,2,1,2,1,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2, + 0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,1,2,2,2,0,1,1,2,1,0,0,2,0,2,0,2,2,2,1,2,2,0,2,2,2,1,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,2,2,2,0,2,2,2,2,0,2,2,2,1,2, + 2,0,2,0,2,1,2,1,0,2,0,2,1,2,1,2,2,2,2,2,2,2,2,2,2,1,2,2,2,0,2,2, + 0,2,0,0,1,2,1,1,0,2,0,2,1,2,1,2,2,2,2,2,2,2,2,2,0,0,0,2,1,1,1,2, + 2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1, + 2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,0,0,2,1,1,1,2,0,0,2,2,2,1,2,2,2, + 2,1,2,1,2,0,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,0,0,1,2,1,1, + 0,0,2,2,1,1,2,2,0,2,1,2,1,2,0,2,2,1,2,1,2,0,2,0,1,2,1,2,0,2,0,2, + 2,2,2,2,2,2,2,2,1,2,1,2,0,2,0,2,2,2,2,2,2,2,2,2,2,0,2,0,2,1,2,1, + 2,2,0,0,2,2,1,1,2,2,0,0,2,2,1,1,2,2,2,2,2,2,2,2,2,2,0,0,2,2,1,1, + 2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,0,2,0,0,1,2,1,1, + 2,2,2,0,2,2,2,1,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,1,1,1,2,0,0,0,2, + 2,2,2,2,2,2,2,2,1,1,1,2,0,0,0,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2, + 2,0,2,0,2,1,2,1,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,0,0,0,2,1,1,1, + 2,0,2,2,2,1,2,2,0,2,2,2,1,2,2,2,2,0,2,0,2,1,2,1,2,2,2,2,2,2,2,2, + 2,0,2,0,2,1,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,0,2,0,2,1,2,1,2,1,2,0,2,0,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,0,2,0,2,1,2,1,1,2,1,2,0,2,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,1,2,1,2,0,2,0,2,2,1,2,1,2,0,2,0,2,2,2,2,2,2,2,2, + 2,0,2,1,2,1,2,0,0,2,1,2,1,2,0,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1, + 2,0,2,0,2,1,2,1,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,0,2,0,2,1,2,1, + 2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,1,2,1,2,0,2,0,1,1,1,2,0,0,0,2,2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1, + 2,0,2,0,2,1,2,1,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, + 2,2,2,2,2,2,2,2,2,2,2,0,2,2,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, +}; + + +/* * Initialize the status struct for the encoder. */ void jbg_enc_init(struct jbg_enc_state *s, unsigned long x, unsigned long y, @@ -693,12 +774,13 @@ void jbg_enc_init(struct jbg_enc_state *s, unsigned long x, unsigned long y, { unsigned long l, lx; int i; - size_t bufsize; - - extern char jbg_resred[], jbg_dptable[]; + assert(x > 0 && y > 0 && planes > 0 && planes < 256); s->xd = x; s->yd = y; + s->yd1 = y; /* This is the hight initially announced in BIH. To provoke + generation of NEWLEN for T.85 compatibility tests, + overwrite with new value s->yd1 > s->yd */ s->planes = planes; s->data_out = data_out; s->file = file; @@ -706,33 +788,32 @@ void jbg_enc_init(struct jbg_enc_state *s, unsigned long x, unsigned long y, s->d = 0; s->dl = 0; s->dh = s->d; - s->l0 = jbg_ceil_half(s->yd, s->d) / 35; /* 35 stripes/image */ - while ((s->l0 << s->d) > 128) /* but <= 128 lines/stripe */ - --s->l0; - if (s->l0 < 2) s->l0 = 2; + jbg_set_default_l0(s); s->mx = 8; s->my = 0; s->order = JBG_ILEAVE | JBG_SMID; s->options = JBG_TPBON | JBG_TPDON | JBG_DPON; + s->comment = NULL; s->dppriv = jbg_dptable; s->res_tab = jbg_resred; - s->highres = checked_malloc(planes * sizeof(int)); + s->highres = (int *) checked_malloc(planes, sizeof(int)); s->lhp[0] = p; - s->lhp[1] = checked_malloc(planes * sizeof(unsigned char *)); - bufsize = ((jbg_ceil_half(x, 1) + 7) / 8) * jbg_ceil_half(y, 1); + s->lhp[1] = (unsigned char **) + checked_malloc(planes, sizeof(unsigned char *)); for (i = 0; i < planes; i++) { s->highres[i] = 0; - s->lhp[1][i] = checked_malloc(sizeof(unsigned char) * bufsize); + s->lhp[1][i] = (unsigned char *) + checked_malloc(jbg_ceil_half(y, 1), jbg_ceil_half(x, 1+3)); } s->free_list = NULL; s->s = (struct jbg_arenc_state *) - checked_malloc(s->planes * sizeof(struct jbg_arenc_state)); - s->tx = (int *) checked_malloc(s->planes * sizeof(int)); + checked_malloc(s->planes, sizeof(struct jbg_arenc_state)); + s->tx = (int *) checked_malloc(s->planes, sizeof(int)); lx = jbg_ceil_half(x, 1); - s->tp = (char *) checked_malloc(lx * sizeof(char)); - for (l = 0; l < lx; s->tp[l++] = 2); + s->tp = (char *) checked_malloc(lx, sizeof(char)); + for (l = 0; l < lx; s->tp[l++] = 2) ; s->sde = NULL; return; @@ -759,12 +840,7 @@ int jbg_enc_lrlmax(struct jbg_enc_state *s, unsigned long x, break; s->dl = 0; s->dh = s->d; - - s->l0 = jbg_ceil_half(s->yd, s->d) / 35; /* 35 stripes/image */ - while ((s->l0 << s->d) > 128) /* but <= 128 lines/stripe */ - --s->l0; - if (s->l0 < 2) s->l0 = 2; - + jbg_set_default_l0(s); return s->d; } @@ -776,17 +852,12 @@ int jbg_enc_lrlmax(struct jbg_enc_state *s, unsigned long x, */ void jbg_enc_layers(struct jbg_enc_state *s, int d) { - if (d < 0 || d > 255) + if (d < 0 || d > 31) return; s->d = d; s->dl = 0; s->dh = s->d; - - s->l0 = jbg_ceil_half(s->yd, s->d) / 35; /* 35 stripes/image */ - while ((s->l0 << s->d) > 128) /* but <= 128 lines/stripe */ - --s->l0; - if (s->l0 < 2) s->l0 = 2; - + jbg_set_default_l0(s); return; } @@ -813,11 +884,11 @@ int jbg_enc_lrange(struct jbg_enc_state *s, int dl, int dh) * the number of layer 0 lines per stripes. */ void jbg_enc_options(struct jbg_enc_state *s, int order, int options, - long l0, int mx, int my) + unsigned long l0, int mx, int my) { if (order >= 0 && order <= 0x0f) s->order = order; if (options >= 0) s->options = options; - if (l0 >= 0) s->l0 = l0; + if (l0 > 0) s->l0 = l0; if (mx >= 0 && my < 128) s->mx = mx; if (my >= 0 && my < 256) s->my = my; @@ -838,13 +909,17 @@ static void encode_sde(struct jbg_enc_state *s, unsigned long line_h0 = 0, line_h1 = 0; unsigned long line_h2, line_h3, line_l1, line_l2, line_l3; struct jbg_arenc_state *se; - unsigned long i, j, y; - unsigned t; + unsigned long y; /* current line number in highres image */ + unsigned long i; /* current line number within highres stripe */ + unsigned long j; /* current column number in highres image */ + long o; + unsigned a, p, t; int ltp, ltp_old, cx; unsigned long c_all, c[MX_MAX + 1], cmin, cmax, clmin, clmax; int tmax, at_determined; int new_tx; long new_tx_line = -1; + int reset; struct jbg_buf *new_jbg_buf; #ifdef DEBUG @@ -876,16 +951,19 @@ static void encode_sde(struct jbg_enc_state *s, lx = jbg_ceil_half(hx, 1); ly = jbg_ceil_half(hy, 1); /* bytes per line in highres and lowres image */ - hbpl = (hx + 7) / 8; - lbpl = (lx + 7) / 8; + hbpl = jbg_ceil_half(hx, 3); + lbpl = jbg_ceil_half(lx, 3); /* pointer to first image byte of highres stripe */ hp = s->lhp[s->highres[plane]][plane] + stripe * hl * hbpl; lp2 = s->lhp[1 - s->highres[plane]][plane] + stripe * ll * lbpl; lp1 = lp2 + lbpl; + /* check whether we can refer to any state of a previous stripe */ + reset = (stripe == 0) || (s->options & JBG_SDRST); + /* initialize arithmetic encoder */ se = s->s + plane; - arith_encode_init(se, stripe != 0); + arith_encode_init(se, !reset); s->sde[stripe][layer][plane] = jbg_buf_init(&s->free_list); se->byte_out = jbg_buf_write; se->file = s->sde[stripe][layer][plane]; @@ -894,7 +972,7 @@ static void encode_sde(struct jbg_enc_state *s, c_all = 0; for (t = 0; t <= s->mx; t++) c[t] = 0; - if (stripe == 0) + if (stripe == 0) /* the SDRST case is handled at the end */ s->tx[plane] = 0; new_tx = -1; at_determined = 0; /* we haven't yet decided the template move */ @@ -903,16 +981,16 @@ static void encode_sde(struct jbg_enc_state *s, /* initialize typical prediction */ ltp = 0; - if (stripe == 0) + if (reset) ltp_old = 0; else { ltp_old = 1; p1 = hp - hbpl; if (y > 1) { q1 = p1 - hbpl; - while (p1 < hp && (ltp_old = (*p1++ == *q1++)) != 0); + while (p1 < hp && (ltp_old = (*p1++ == *q1++)) != 0) ; } else - while (p1 < hp && (ltp_old = (*p1++ == 0)) != 0); + while (p1 < hp && (ltp_old = (*p1++ == 0)) != 0) ; } if (layer == 0) { @@ -938,7 +1016,7 @@ static void encode_sde(struct jbg_enc_state *s, if (c_all - cmax < (c_all >> 3) && cmax - c[s->tx[plane]] > c_all - cmax && cmax - c[s->tx[plane]] > (c_all >> 4) && - /* ^ T.82 says here < !!! Typo ? */ + /* ^ T.82 said < here, fixed in Cor.1/25 */ cmax - (c_all - c[s->tx[plane]]) > c_all - cmax && cmax - (c_all - c[s->tx[plane]]) > (c_all >> 4) && cmax - cmin > (c_all >> 2) && @@ -949,19 +1027,24 @@ static void encode_sde(struct jbg_enc_state *s, new_tx_line = i; s->tx[plane] = new_tx; } +#ifdef DEBUG + fprintf(stderr, "ATMOVE: line=%ld, tx=%d, c_all=%ld\n", + i, new_tx, c_all); +#endif } at_determined = 1; } + assert(s->tx[plane] >= 0); /* i.e., tx can safely be cast to unsigned */ /* typical prediction */ if (s->options & JBG_TPBON) { ltp = 1; p1 = hp; - if (y > 0) { + if (i > 0 || !reset) { q1 = hp - hbpl; - while (q1 < hp && (ltp = (*p1++ == *q1++)) != 0); + while (q1 < hp && (ltp = (*p1++ == *q1++)) != 0) ; } else - while (p1 < hp + hbpl && (ltp = (*p1++ == 0)) != 0); + while (p1 < hp + hbpl && (ltp = (*p1++ == 0)) != 0) ; arith_encode(se, (s->options & JBG_LRLTWO) ? TPB2CX : TPB3CX, ltp == ltp_old); #ifdef DEBUG @@ -985,26 +1068,35 @@ static void encode_sde(struct jbg_enc_state *s, */ line_h1 = line_h2 = line_h3 = 0; - if (y > 0) line_h2 = (long)*(hp - hbpl) << 8; - if (y > 1) line_h3 = (long)*(hp - hbpl - hbpl) << 8; + if (i > 0 || !reset) line_h2 = (long)*(hp - hbpl) << 8; + if (i > 1 || !reset) line_h3 = (long)*(hp - hbpl - hbpl) << 8; /* encode line */ for (j = 0; j < hx; hp++) { line_h1 |= *hp; - if (j < hbpl * 8 - 8 && y > 0) { + if (j < hbpl * 8 - 8 && (i > 0 || !reset)) { line_h2 |= *(hp - hbpl + 1); - if (y > 1) + if (i > 1 || !reset) line_h3 |= *(hp - hbpl - hbpl + 1); } if (s->options & JBG_LRLTWO) { /* two line template */ do { line_h1 <<= 1; line_h2 <<= 1; line_h3 <<= 1; - if (s->tx[plane]) - arith_encode(se, (((line_h2 >> 10) & 0x3e0) | - ((line_h1 >> (4 + s->tx[plane])) & 0x010) | + if (s->tx[plane]) { + if ((unsigned) s->tx[plane] > j) + a = 0; + else { + o = (j - s->tx[plane]) - (j & ~7L); + a = (hp[o >> 3] >> (7 - (o & 7))) & 1; + a <<= 4; + } + assert(s->tx[plane] > 23 || + a == ((line_h1 >> (4 + s->tx[plane])) & 0x010)); + arith_encode(se, (((line_h2 >> 10) & 0x3e0) | a | ((line_h1 >> 9) & 0x00f)), (line_h1 >> 8) & 1); + } else arith_encode(se, (((line_h2 >> 10) & 0x3f0) | ((line_h1 >> 9) & 0x00f)), @@ -1014,9 +1106,20 @@ static void encode_sde(struct jbg_enc_state *s, #endif /* statistics for adaptive template changes */ if (!at_determined && j >= s->mx && j < hx-2) { - c[0] += !(((line_h2 >> 6) ^ line_h1) & 0x100); - for (t = 5; t <= s->mx; t++) - c[t] += !(((line_h1 >> t) ^ line_h1) & 0x100); + p = (line_h1 & 0x100) != 0; /* current pixel value */ + c[0] += ((line_h2 & 0x4000) != 0) == p; /* default position */ + assert(!(((line_h2 >> 6) ^ line_h1) & 0x100) == + (((line_h2 & 0x4000) != 0) == p)); + for (t = 5; t <= s->mx && t <= j; t++) { + o = (j - t) - (j & ~7L); + a = (hp[o >> 3] >> (7 - (o & 7))) & 1; + assert(t > 23 || + (a == p) == !(((line_h1 >> t) ^ line_h1) & 0x100)); + c[t] += a == p; + } + for (; t <= s->mx; t++) { + c[t] += 0 == p; + } ++c_all; } } while (++j & 7 && j < hx); @@ -1024,13 +1127,21 @@ static void encode_sde(struct jbg_enc_state *s, /* three line template */ do { line_h1 <<= 1; line_h2 <<= 1; line_h3 <<= 1; - if (s->tx[plane]) + if (s->tx[plane]) { + if ((unsigned) s->tx[plane] > j) + a = 0; + else { + o = (j - s->tx[plane]) - (j & ~7L); + a = (hp[o >> 3] >> (7 - (o & 7))) & 1; + a <<= 2; + } + assert(s->tx[plane] > 23 || + a == ((line_h1 >> (6 + s->tx[plane])) & 0x004)); arith_encode(se, (((line_h3 >> 8) & 0x380) | - ((line_h2 >> 12) & 0x078) | - ((line_h1 >> (6 + s->tx[plane])) & 0x004) | + ((line_h2 >> 12) & 0x078) | a | ((line_h1 >> 9) & 0x003)), (line_h1 >> 8) & 1); - else + } else arith_encode(se, (((line_h3 >> 8) & 0x380) | ((line_h2 >> 12) & 0x07c) | ((line_h1 >> 9) & 0x003)), @@ -1040,9 +1151,20 @@ static void encode_sde(struct jbg_enc_state *s, #endif /* statistics for adaptive template changes */ if (!at_determined && j >= s->mx && j < hx-2) { - c[0] += !(((line_h2 >> 6) ^ line_h1) & 0x100); - for (t = 3; t <= s->mx; t++) - c[t] += !(((line_h1 >> t) ^ line_h1) & 0x100); + p = (line_h1 & 0x100) != 0; /* current pixel value */ + c[0] += ((line_h2 & 0x4000) != 0) == p; /* default position */ + assert(!(((line_h2 >> 6) ^ line_h1) & 0x100) == + (((line_h2 & 0x4000) != 0) == p)); + for (t = 3; t <= s->mx && t <= j; t++) { + o = (j - t) - (j & ~7L); + a = (hp[o >> 3] >> (7 - (o & 7))) & 1; + assert(t > 23 || + (a == p) == !(((line_h1 >> t) ^ line_h1) & 0x100)); + c[t] += a == p; + } + for (; t <= s->mx; t++) { + c[t] += 0 == p; + } ++c_all; } } while (++j & 7 && j < hx); @@ -1073,7 +1195,7 @@ static void encode_sde(struct jbg_enc_state *s, if (c_all - cmax < (c_all >> 3) && cmax - c[s->tx[plane]] > c_all - cmax && cmax - c[s->tx[plane]] > (c_all >> 4) && - /* ^ T.82 says here < !!! Typo ? */ + /* ^ T.82 said < here, fixed in Cor.1/25 */ cmax - (c_all - c[s->tx[plane]]) > c_all - cmax && cmax - (c_all - c[s->tx[plane]]) > (c_all >> 4) && cmax - cmin > (c_all >> 2) && @@ -1101,7 +1223,7 @@ static void encode_sde(struct jbg_enc_state *s, p0 = p1 = hp; if (i < hl - 1 && y < hy - 1) p0 = hp + hbpl; - if (y > 1) + if (i > 1 || !reset) line_l3 = (long)*(q2 - lbpl) << 8; else line_l3 = 0; @@ -1110,7 +1232,7 @@ static void encode_sde(struct jbg_enc_state *s, ltp = 1; for (j = 0; j < lx && ltp; q1++, q2++) { if (j < lbpl * 8 - 8) { - if (y > 1) + if (i > 1 || !reset) line_l3 |= *(q2 - lbpl + 1); line_l2 |= *(q2 + 1); line_l1 |= *(q1 + 1); @@ -1180,8 +1302,8 @@ static void encode_sde(struct jbg_enc_state *s, line_h1 = line_h2 = line_h3 = line_l1 = line_l2 = line_l3 = 0; - if (y > 0) line_h2 = (long)*(hp - hbpl) << 8; - if (y > 1) { + if (i > 0 || !reset) line_h2 = (long)*(hp - hbpl) << 8; + if (i > 1 || !reset) { line_h3 = (long)*(hp - hbpl - hbpl) << 8; line_l3 = (long)*(lp2 - lbpl) << 8; } @@ -1191,12 +1313,12 @@ static void encode_sde(struct jbg_enc_state *s, /* encode line */ for (j = 0; j < hx; lp1++, lp2++) { if ((j >> 1) < lbpl * 8 - 8) { - if (y > 1) + if (i > 1 || !reset) line_l3 |= *(lp2 - lbpl + 1); line_l2 |= *(lp2 + 1); line_l1 |= *(lp1 + 1); } - do { + do { /* ... while (j & 15 && j < hx) */ assert(hp - (s->lhp[s->highres[plane]][plane] + (stripe * hl + i) * hbpl) @@ -1206,15 +1328,15 @@ static void encode_sde(struct jbg_enc_state *s, (stripe * ll + (i>>1)) * lbpl) == (ptrdiff_t) j >> 4); - line_h1 |= *(hp++); + line_h1 |= *hp; if (j < hbpl * 8 - 8) { - if (y > 0) { - line_h2 |= *(hp - hbpl); - if (y > 1) - line_h3 |= *(hp - hbpl - hbpl); + if (i > 0 || !reset) { + line_h2 |= *(hp - hbpl + 1); + if (i > 1 || !reset) + line_h3 |= *(hp - hbpl - hbpl + 1); } } - do { + do { /* ... while (j & 7 && j < hx) */ line_l1 <<= 1; line_l2 <<= 1; line_l3 <<= 1; if (ltp && s->tp[j >> 1] < 2) { /* pixel are typical and have not to be encoded */ @@ -1227,7 +1349,7 @@ static void encode_sde(struct jbg_enc_state *s, j += 2; #endif } else - do { + do { /* ... while (++j & 1 && j < hx) */ line_h1 <<= 1; line_h2 <<= 1; line_h3 <<= 1; /* deterministic prediction */ @@ -1286,12 +1408,20 @@ static void encode_sde(struct jbg_enc_state *s, } /* determine context */ - if (s->tx[plane]) - cx = (((line_h1 >> 9) & 0x003) | - ((line_h1 >> (4 + s->tx[plane])) & 0x010) | + if (s->tx[plane]) { + if ((unsigned) s->tx[plane] > j) + a = 0; + else { + o = (j - s->tx[plane]) - (j & ~7L); + a = (hp[o >> 3] >> (7 - (o & 7))) & 1; + a <<= 4; + } + assert(s->tx[plane] > 23 || + a == ((line_h1 >> (4 + s->tx[plane])) & 0x010)); + cx = (((line_h1 >> 9) & 0x003) | a | ((line_h2 >> 13) & 0x00c) | ((line_h3 >> 11) & 0x020)); - else + } else cx = (((line_h1 >> 9) & 0x003) | ((line_h2 >> 13) & 0x01c) | ((line_h3 >> 11) & 0x020)); @@ -1318,6 +1448,7 @@ static void encode_sde(struct jbg_enc_state *s, } while (++j & 1 && j < hx); } while (j & 7 && j < hx); + hp++; } while (j & 15 && j < hx); } /* for (j = ...) */ @@ -1333,7 +1464,10 @@ static void encode_sde(struct jbg_enc_state *s, arith_encode_flush(se); jbg_buf_remove_zeros(s->sde[stripe][layer][plane]); jbg_buf_write(MARKER_ESC, s->sde[stripe][layer][plane]); - jbg_buf_write(MARKER_SDNORM, s->sde[stripe][layer][plane]); + jbg_buf_write((s->options & JBG_SDRST) ? MARKER_SDRST : MARKER_SDNORM, + s->sde[stripe][layer][plane]); + if (s->options & JBG_SDRST) + s->tx[plane] = 0; /* add ATMOVE */ if (new_tx != -1) { @@ -1381,12 +1515,18 @@ static void encode_sde(struct jbg_enc_state *s, static void resolution_reduction(struct jbg_enc_state *s, int plane, int higher_layer) { - unsigned long hx, hy, lx, ly, hbpl, lbpl; + unsigned long hl, ll, hx, hy, lx, ly, hbpl, lbpl; unsigned char *hp1, *hp2, *hp3, *lp; unsigned long line_h1, line_h2, line_h3, line_l2; - unsigned long i, j; + unsigned long y; /* current line number in lowres image */ + unsigned long i; /* current line number within lowres stripe */ + unsigned long j; /* current column number in lowres image */ int pix, k, l; + /* number of lines per stripe in highres image */ + hl = s->l0 << higher_layer; + /* number of lines per stripe in lowres image */ + ll = hl >> 1; /* number of pixels in highres image */ hx = jbg_ceil_half(s->xd, s->d - higher_layer); hy = jbg_ceil_half(s->yd, s->d - higher_layer); @@ -1394,8 +1534,8 @@ static void resolution_reduction(struct jbg_enc_state *s, int plane, lx = jbg_ceil_half(hx, 1); ly = jbg_ceil_half(hy, 1); /* bytes per line in highres and lowres image */ - hbpl = (hx + 7) / 8; - lbpl = (lx + 7) / 8; + hbpl = jbg_ceil_half(hx, 3); + lbpl = jbg_ceil_half(lx, 3); /* pointers to first image bytes */ hp2 = s->lhp[s->highres[plane]][plane]; hp1 = hp2 + hbpl; @@ -1424,40 +1564,44 @@ static void resolution_reduction(struct jbg_enc_state *s, int plane, * 76543210 76543210 76543210 76543210 line_l2 * X */ - - for (i = 0; i < ly; i++) { - if (2*i + 1 >= hy) - hp1 = hp2; - pix = 0; - line_h1 = line_h2 = line_h3 = line_l2 = 0; - for (j = 0; j < lbpl * 8; j += 8) { - *lp = 0; - line_l2 |= i ? lp[-lbpl] : 0; - for (k = 0; k < 8 && j + k < lx; k += 4) { - if (((j + k) >> 2) < hbpl) { - line_h3 |= i ? *hp3 : 0; - ++hp3; - line_h2 |= *(hp2++); - line_h1 |= *(hp1++); - } - for (l = 0; l < 4 && j + k + l < lx; l++) { - line_h3 <<= 2; - line_h2 <<= 2; - line_h1 <<= 2; - line_l2 <<= 1; - pix = s->res_tab[((line_h1 >> 8) & 0x007) | - ((line_h2 >> 5) & 0x038) | - ((line_h3 >> 2) & 0x1c0) | - (pix << 9) | ((line_l2 << 2) & 0xc00)]; - *lp = (*lp << 1) | pix; + + for (y = 0; y < ly;) { + for (i = 0; i < ll && y < ly; i++, y++) { + if (2*y + 1 >= hy) + hp1 = hp2; + pix = 0; + line_h1 = line_h2 = line_h3 = line_l2 = 0; + for (j = 0; j < lbpl * 8; j += 8) { + *lp = 0; + if (i > 0 || (y > 0 && !(s->options & JBG_SDRST))) + line_l2 |= *(lp-lbpl); + for (k = 0; k < 8 && j + k < lx; k += 4) { + if (((j + k) >> 2) < hbpl) { + if (i > 0 || (y > 0 && !(s->options & JBG_SDRST))) + line_h3 |= *hp3; + ++hp3; + line_h2 |= *(hp2++); + line_h1 |= *(hp1++); + } + for (l = 0; l < 4 && j + k + l < lx; l++) { + line_h3 <<= 2; + line_h2 <<= 2; + line_h1 <<= 2; + line_l2 <<= 1; + pix = s->res_tab[((line_h1 >> 8) & 0x007) | + ((line_h2 >> 5) & 0x038) | + ((line_h3 >> 2) & 0x1c0) | + (pix << 9) | ((line_l2 << 2) & 0xc00)]; + *lp = (*lp << 1) | pix; + } } + ++lp; } - ++lp; + *(lp - 1) <<= lbpl * 8 - lx; + hp1 += hbpl; + hp2 += hbpl; + hp3 += hbpl; } - *(lp - 1) <<= lbpl * 8 - lx; - hp1 += hbpl; - hp2 += hbpl; - hp3 += hbpl; } #ifdef DEBUG @@ -1482,16 +1626,15 @@ static void resolution_reduction(struct jbg_enc_state *s, int plane, * order to write the next SDE. It has first to generate the required * SDE and all SDEs which have to be encoded before this SDE can be * created. The problem here is that if we want to output a lower - * resolution layer, we have to allpy the resolution reduction - * algorithm in order to get it. As we try to safe as much memory as + * resolution layer, we have to apply the resolution reduction + * algorithm first to get it. As we try to safe as much memory as * possible, the resolution reduction will overwrite previous higher * resolution bitmaps. Consequently, we have to encode and buffer SDEs * which depend on higher resolution layers before we can start the - * resolution reduction. All this logic about which SDE has to be - * encoded before resolution reduction is allowed is handled here. - * This approach might be a little bit more complex than alternative - * ways to do it, but it allows us to do the encoding with the minimal - * possible amount of temporary memory. + * resolution reduction. All the logic about which SDE has to be + * encoded before resolution reduction is allowed is handled + * here. This approach may be a bit more complex than alternative ways + * of doing it, but it minimizes the amount of temporary memory used. */ static void output_sde(struct jbg_enc_state *s, unsigned long stripe, int layer, int plane) @@ -1587,12 +1730,12 @@ void jbg_int2dppriv(unsigned char *dptable, const char *internal) int trans2[11] = { 1, 0, 3, 2, 10, 9, 8, 7, 6, 5, 4 }; int trans3[12] = { 1, 0, 3, 2, 11, 10, 9, 8, 7, 6, 5, 4 }; - for (i = 0; i < 1728; dptable[i++] = 0); + for (i = 0; i < 1728; dptable[i++] = 0) ; #define FILL_TABLE1(offset, len, trans) \ for (i = 0; i < len; i++) { \ k = 0; \ - for (j = 0; j < 8; j++) \ + for (j = 0; i >> j; j++) \ k |= ((i >> j) & 1) << trans[j]; \ dptable[(i + offset) >> 2] |= \ (internal[k + offset] & 3) << ((3 - (i&3)) << 1); \ @@ -1623,7 +1766,7 @@ void jbg_dppriv2int(char *internal, const unsigned char *dptable) #define FILL_TABLE2(offset, len, trans) \ for (i = 0; i < len; i++) { \ k = 0; \ - for (j = 0; j < 8; j++) \ + for (j = 0; i >> j; j++) \ k |= ((i >> j) & 1) << trans[j]; \ internal[k + offset] = \ (dptable[(i + offset) >> 2] >> ((3 - (i & 3)) << 1)) & 3; \ @@ -1644,20 +1787,19 @@ void jbg_dppriv2int(char *internal, const unsigned char *dptable) */ void jbg_enc_out(struct jbg_enc_state *s) { - long bpl; - unsigned char bih[20]; + unsigned long bpl; + unsigned char buf[20]; unsigned long xd, yd, y; long ii[3], is[3], ie[3]; /* generic variables for the 3 nested loops */ unsigned long stripe; int layer, plane; int order; unsigned char dpbuf[1728]; - extern char jbg_dptable[]; /* some sanity checks */ s->order &= JBG_HITOLO | JBG_SEQ | JBG_ILEAVE | JBG_SMID; order = s->order & (JBG_SEQ | JBG_ILEAVE | JBG_SMID); - if (index[order][0] < 0) + if (iindex[order][0] < 0) s->order = order = JBG_SMID | JBG_ILEAVE; if (s->options & JBG_DPON && s->dppriv != jbg_dptable) s->options |= JBG_DPPRIV; @@ -1669,29 +1811,65 @@ void jbg_enc_out(struct jbg_enc_state *s) if (s->d > 255 || s->d < 0 || s->dh > s->d || s->dh < 0 || s->dl < 0 || s->dl > s->dh || s->planes < 0 || s->planes > 255) return; + /* prevent uint32 overflow: s->l0 * 2 ^ s->d < 2 ^ 32 */ + if (s->d > 31 || (s->d != 0 && s->l0 >= (1UL << (32 - s->d)))) + return; + if (s->yd1 < s->yd) + s->yd1 = s->yd; + if (s->yd1 > s->yd) + s->options |= JBG_VLENGTH; /* ensure correct zero padding of bitmap at the final byte of each line */ if (s->xd & 7) { - bpl = (s->xd + 7) / 8; /* bytes per line */ + bpl = jbg_ceil_half(s->xd, 3); /* bytes per line */ for (plane = 0; plane < s->planes; plane++) for (y = 0; y < s->yd; y++) s->lhp[0][plane][y * bpl + bpl - 1] &= ~((1 << (8 - (s->xd & 7))) - 1); } + /* prepare BIH */ + buf[0] = s->dl; + buf[1] = s->dh; + buf[2] = s->planes; + buf[3] = 0; + xd = jbg_ceil_half(s->xd, s->d - s->dh); + yd = jbg_ceil_half(s->yd1, s->d - s->dh); + buf[4] = xd >> 24; + buf[5] = (xd >> 16) & 0xff; + buf[6] = (xd >> 8) & 0xff; + buf[7] = xd & 0xff; + buf[8] = yd >> 24; + buf[9] = (yd >> 16) & 0xff; + buf[10] = (yd >> 8) & 0xff; + buf[11] = yd & 0xff; + buf[12] = s->l0 >> 24; + buf[13] = (s->l0 >> 16) & 0xff; + buf[14] = (s->l0 >> 8) & 0xff; + buf[15] = s->l0 & 0xff; + buf[16] = s->mx; + buf[17] = s->my; + buf[18] = s->order; + buf[19] = s->options & 0x7f; + +#if 0 + /* sanitize L0 (if it was set to 0xffffffff for T.85-style NEWLEN tests) */ + if (s->l0 > (s->yd >> s->d)) + s->l0 = s->yd >> s->d; +#endif + /* calculate number of stripes that will be required */ - s->stripes = ((s->yd >> s->d) + - ((((1UL << s->d) - 1) & s->xd) != 0) + s->l0 - 1) / s->l0; + s->stripes = jbg_stripes(s->l0, s->yd, s->d); /* allocate buffers for SDE pointers */ if (s->sde == NULL) { s->sde = (struct jbg_buf ****) - checked_malloc(s->stripes * sizeof(struct jbg_buf ***)); + checked_malloc(s->stripes, sizeof(struct jbg_buf ***)); for (stripe = 0; stripe < s->stripes; stripe++) { s->sde[stripe] = (struct jbg_buf ***) - checked_malloc((s->d + 1) * sizeof(struct jbg_buf **)); + checked_malloc(s->d + 1, sizeof(struct jbg_buf **)); for (layer = 0; layer < s->d + 1; layer++) { s->sde[stripe][layer] = (struct jbg_buf **) - checked_malloc(s->planes * sizeof(struct jbg_buf *)); + checked_malloc(s->planes, sizeof(struct jbg_buf *)); for (plane = 0; plane < s->planes; plane++) s->sde[stripe][layer][plane] = SDE_TODO; } @@ -1699,29 +1877,7 @@ void jbg_enc_out(struct jbg_enc_state *s) } /* output BIH */ - bih[0] = s->dl; - bih[1] = s->dh; - bih[2] = s->planes; - bih[3] = 0; - xd = jbg_ceil_half(s->xd, s->d - s->dh); - yd = jbg_ceil_half(s->yd, s->d - s->dh); - bih[4] = xd >> 24; - bih[5] = (xd >> 16) & 0xff; - bih[6] = (xd >> 8) & 0xff; - bih[7] = xd & 0xff; - bih[8] = yd >> 24; - bih[9] = (yd >> 16) & 0xff; - bih[10] = (yd >> 8) & 0xff; - bih[11] = yd & 0xff; - bih[12] = s->l0 >> 24; - bih[13] = (s->l0 >> 16) & 0xff; - bih[14] = (s->l0 >> 8) & 0xff; - bih[15] = s->l0 & 0xff; - bih[16] = s->mx; - bih[17] = s->my; - bih[18] = s->order; - bih[19] = s->options & 0x7f; - s->data_out(bih, 20, s->file); + s->data_out(buf, 20, s->file); if ((s->options & (JBG_DPON | JBG_DPPRIV | JBG_DPLAST)) == (JBG_DPON | JBG_DPPRIV)) { /* write private table */ @@ -1751,27 +1907,68 @@ void jbg_enc_out(struct jbg_enc_state *s) * stripe depends on the option flags. */ - /* start and end value vor each loop */ - is[index[order][STRIPE]] = 0; - ie[index[order][STRIPE]] = s->stripes - 1; - is[index[order][LAYER]] = s->dl; - ie[index[order][LAYER]] = s->dh; - is[index[order][PLANE]] = 0; - ie[index[order][PLANE]] = s->planes - 1; + /* start and end value for each loop */ + is[iindex[order][STRIPE]] = 0; + ie[iindex[order][STRIPE]] = s->stripes - 1; + is[iindex[order][LAYER]] = s->dl; + ie[iindex[order][LAYER]] = s->dh; + is[iindex[order][PLANE]] = 0; + ie[iindex[order][PLANE]] = s->planes - 1; for (ii[0] = is[0]; ii[0] <= ie[0]; ii[0]++) for (ii[1] = is[1]; ii[1] <= ie[1]; ii[1]++) for (ii[2] = is[2]; ii[2] <= ie[2]; ii[2]++) { - stripe = ii[index[order][STRIPE]]; + stripe = ii[iindex[order][STRIPE]]; if (s->order & JBG_HITOLO) - layer = s->dh - (ii[index[order][LAYER]] - s->dl); + layer = s->dh - (ii[iindex[order][LAYER]] - s->dl); else - layer = ii[index[order][LAYER]]; - plane = ii[index[order][PLANE]]; + layer = ii[iindex[order][LAYER]]; + plane = ii[iindex[order][PLANE]]; + + /* output comment marker segment if there is any pending */ + if (s->comment) { + buf[0] = MARKER_ESC; + buf[1] = MARKER_COMMENT; + buf[2] = s->comment_len >> 24; + buf[3] = (s->comment_len >> 16) & 0xff; + buf[4] = (s->comment_len >> 8) & 0xff; + buf[5] = s->comment_len & 0xff; + s->data_out(buf, 6, s->file); + s->data_out(s->comment, s->comment_len, s->file); + s->comment = NULL; + } output_sde(s, stripe, layer, plane); + /* + * When we generate a NEWLEN test case (s->yd1 > s->yd), output + * NEWLEN after last stripe if we have only a single + * resolution layer or plane (see ITU-T T.85 profile), otherwise + * output NEWLEN before last stripe. + */ + if (s->yd1 > s->yd && + (stripe == s->stripes - 1 || + (stripe == s->stripes - 2 && + (s->dl != s->dh || s->planes > 1)))) { + s->yd1 = s->yd; + yd = jbg_ceil_half(s->yd, s->d - s->dh); + buf[0] = MARKER_ESC; + buf[1] = MARKER_NEWLEN; + buf[2] = yd >> 24; + buf[3] = (yd >> 16) & 0xff; + buf[4] = (yd >> 8) & 0xff; + buf[5] = yd & 0xff; + s->data_out(buf, 6, s->file); +#ifdef DEBUG + fprintf(stderr, "NEWLEN: yd=%lu\n", yd); +#endif + if (stripe == s->stripes - 1) { + buf[1] = MARKER_SDNORM; + s->data_out(buf, 2, s->file); + } + } + } return; @@ -1784,7 +1981,7 @@ void jbg_enc_free(struct jbg_enc_state *s) int layer, plane; #ifdef DEBUG - fprintf(stderr, "jbg_enc_free(%p)\n", s); + fprintf(stderr, "jbg_enc_free(%p)\n", (void *) s); #endif /* clear buffers for SDEs */ @@ -1820,23 +2017,24 @@ void jbg_enc_free(struct jbg_enc_state *s) checked_free(s->lhp[1][plane]); checked_free(s->lhp[1]); } - + + /* clear buffer for index of highres image in lhp */ + checked_free(s->highres); + return; } /* - * Convert the error codes used by jbg_dec_in() into a string - * written in the selected language and character set. + * Convert the error codes used by jbg_dec_in() into an English ASCII string */ -const char *jbg_strerror(int errnum, int language) +const char *jbg_strerror(int errnum) { - if (errnum < 0 || errnum >= NEMSG) + errnum >>= 4; + if (errnum < 0 || (unsigned) errnum >= sizeof(errmsg)/sizeof(errmsg[0])) return "Unknown error code passed to jbg_strerror()"; - if (language < 0 || language >= NEMSG_LANG) - return "Unknown language code passed to jbg_strerror()"; - return errmsg[language][errnum]; + return errmsg[errnum]; } @@ -1880,8 +2078,8 @@ void jbg_dec_maxsize(struct jbg_dec_state *s, unsigned long xmax, * Decode the new len PSDC bytes to which data points and add them to * the current stripe. Return the number of bytes which have actually * been read (this will be less than len if a marker segment was - * part of the data or if the final byte was 0xff were this code - * can not determine, whether we have a marker segment. + * part of the data or if the final byte was 0xff, in which case + * this code cannot determine whether we have a marker segment). */ static size_t decode_pscd(struct jbg_dec_state *s, unsigned char *data, size_t len) @@ -1894,13 +2092,15 @@ static size_t decode_pscd(struct jbg_dec_state *s, unsigned char *data, register unsigned long line_l1, line_l2, line_l3; struct jbg_ardec_state *se; unsigned long x; + long o; + unsigned a; int n; - int pix, cx = 0, slntp, shift, tx; + int pix, cx = 0, slntp, tx; /* SDE loop variables */ - stripe = s->ii[index[s->order & 7][STRIPE]]; - layer = s->ii[index[s->order & 7][LAYER]]; - plane = s->ii[index[s->order & 7][PLANE]]; + stripe = s->ii[iindex[s->order & 7][STRIPE]]; + layer = s->ii[iindex[s->order & 7][LAYER]]; + plane = s->ii[iindex[s->order & 7][PLANE]]; /* forward data to arithmetic decoder */ se = s->s[plane] + layer - s->dl; @@ -1920,8 +2120,8 @@ static size_t decode_pscd(struct jbg_dec_state *s, unsigned char *data, lx = jbg_ceil_half(hx, 1); ly = jbg_ceil_half(hy, 1); /* bytes per line in highres and lowres image */ - hbpl = (hx + 7) / 8; - lbpl = (lx + 7) / 8; + hbpl = jbg_ceil_half(hx, 3); + lbpl = jbg_ceil_half(lx, 3); /* pointer to highres and lowres image bytes */ hp = s->lhp[ layer & 1][plane] + (stripe * hl + s->i) * hbpl + (s->x >> 3); @@ -1938,19 +2138,18 @@ static size_t decode_pscd(struct jbg_dec_state *s, unsigned char *data, line_l3 = s->line_l3; x = s->x; - if (s->x == 0 && s->i == 0 && - (stripe == 0 || s->reset[plane][layer - s->dl])) { - s->tx[plane][layer - s->dl] = s->ty[plane][layer - s->dl] = 0; - if (s->pseudo) - s->lntp[plane][layer - s->dl] = 1; - } - #ifdef DEBUG if (s->x == 0 && s->i == 0 && s->pseudo) fprintf(stderr, "decode_pscd(%p, %p, %ld): s/d/p = %2lu/%2u/%2u\n", - s, data, (long) len, stripe, layer, plane); + (void *) s, (void *) data, (long) len, stripe, layer, plane); #endif + if (s->x == 0 && s->i == 0 && + (stripe == 0 || s->reset[plane][layer - s->dl]) && s->pseudo) { + s->tx[plane][layer - s->dl] = s->ty[plane][layer - s->dl] = 0; + s->lntp[plane][layer - s->dl] = 1; + } + if (layer == 0) { /* @@ -1960,7 +2159,7 @@ static size_t decode_pscd(struct jbg_dec_state *s, unsigned char *data, for (; s->i < hl && y < hy; s->i++, y++) { /* adaptive template changes */ - if (x == 0) + if (x == 0 && s->pseudo) for (n = 0; n < s->at_moves; n++) if (s->at_line[n] == s->i) { s->tx[plane][layer - s->dl] = s->at_tx[n]; @@ -1971,19 +2170,16 @@ static size_t decode_pscd(struct jbg_dec_state *s, unsigned char *data, #endif } tx = s->tx[plane][layer - s->dl]; - shift = tx - ((s->options & JBG_LRLTWO) ? 5 : 3); + assert(tx >= 0); /* i.e., tx can safely be cast to unsigned */ /* typical prediction */ if (s->options & JBG_TPBON && s->pseudo) { slntp = arith_decode(se, (s->options & JBG_LRLTWO) ? TPB2CX : TPB3CX); - if (se->result == JBG_MORE || se->result == JBG_MARKER) + if (slntp < 0) goto leave; s->lntp[plane][layer - s->dl] = !(slntp ^ s->lntp[plane][layer - s->dl]); - if (s->lntp[plane][layer - s->dl]) { - /* this line is 'not typical' and has to be coded completely */ - s->pseudo = 0; - } else { + if (!s->lntp[plane][layer - s->dl]) { /* this line is 'typical' (i.e. identical to the previous one) */ p1 = hp; if (s->i == 0 && (stripe == 0 || s->reset[plane][layer - s->dl])) @@ -1995,7 +2191,9 @@ static size_t decode_pscd(struct jbg_dec_state *s, unsigned char *data, hp += hbpl; continue; } + /* this line is 'not typical' and has to be coded completely */ } + s->pseudo = 0; /* * Layout of the variables line_h1, line_h2, line_h3, which contain @@ -2071,14 +2269,24 @@ static size_t decode_pscd(struct jbg_dec_state *s, unsigned char *data, if (s->options & JBG_LRLTWO) { /* two line template */ do { - if (tx) - pix = arith_decode(se, (((line_h2 >> 9) & 0x3e0) | - ((line_h1 >> shift) & 0x010) | + if (tx) { + if ((unsigned) tx > x) + a = 0; + else if (tx < 8) + a = ((line_h1 >> (tx - 5)) & 0x010); + else { + o = (x - tx) - (x & ~7L); + a = (hp[o >> 3] >> (7 - (o & 7))) & 1; + a <<= 4; + } + assert(tx > 31 || + a == ((line_h1 >> (tx - 5)) & 0x010)); + pix = arith_decode(se, (((line_h2 >> 9) & 0x3e0) | a | (line_h1 & 0x00f))); - else + } else pix = arith_decode(se, (((line_h2 >> 9) & 0x3f0) | (line_h1 & 0x00f))); - if (se->result == JBG_MORE || se->result == JBG_MARKER) + if (pix < 0) goto leave; line_h1 = (line_h1 << 1) | pix; line_h2 <<= 1; @@ -2086,16 +2294,26 @@ static size_t decode_pscd(struct jbg_dec_state *s, unsigned char *data, } else { /* three line template */ do { - if (tx) + if (tx) { + if ((unsigned) tx > x) + a = 0; + else if (tx < 8) + a = ((line_h1 >> (tx - 3)) & 0x004); + else { + o = (x - tx) - (x & ~7L); + a = (hp[o >> 3] >> (7 - (o & 7))) & 1; + a <<= 2; + } + assert(tx > 31 || + a == ((line_h1 >> (tx - 3)) & 0x004)); pix = arith_decode(se, (((line_h3 >> 7) & 0x380) | - ((line_h2 >> 11) & 0x078) | - ((line_h1 >> shift) & 0x004) | + ((line_h2 >> 11) & 0x078) | a | (line_h1 & 0x003))); - else + } else pix = arith_decode(se, (((line_h3 >> 7) & 0x380) | ((line_h2 >> 11) & 0x07c) | (line_h1 & 0x003))); - if (se->result == JBG_MORE || se->result == JBG_MARKER) + if (pix < 0) goto leave; line_h1 = (line_h1 << 1) | pix; @@ -2130,20 +2348,17 @@ static size_t decode_pscd(struct jbg_dec_state *s, unsigned char *data, #endif } tx = s->tx[plane][layer - s->dl]; - shift = tx - 3; /* handle lower border of low-resolution image */ if ((s->i >> 1) >= ll - 1 || (y >> 1) >= ly - 1) lp1 = lp2; /* typical prediction */ - if (s->options & JBG_TPDON && s->pseudo) { - s->lntp[plane][layer - s->dl] = arith_decode(se, TPDCX); - if (se->result == JBG_MORE || se->result == JBG_MARKER) + if ((s->options & JBG_TPDON) && s->pseudo) { + if ((s->lntp[plane][layer - s->dl] = arith_decode(se, TPDCX)) < 0) goto leave; - s->pseudo = 0; } - + s->pseudo = 0; /* * Layout of the variables line_h1, line_h2, line_h3, which contain @@ -2254,7 +2469,7 @@ static size_t decode_pscd(struct jbg_dec_state *s, unsigned char *data, if (pix & 2) { if (tx) cx = ((line_h1 & 0x003) | - (((line_h1 << 2) >> shift) & 0x010) | + (((line_h1 << 2) >> (tx - 3)) & 0x010) | ((line_h2 >> 12) & 0x00c) | ((line_h3 >> 10) & 0x020)); else @@ -2270,7 +2485,7 @@ static size_t decode_pscd(struct jbg_dec_state *s, unsigned char *data, cx |= (y & 1) << 11; pix = arith_decode(se, cx); - if (se->result == JBG_MORE || se->result == JBG_MARKER) + if (pix < 0) goto leave; } @@ -2316,23 +2531,38 @@ static size_t decode_pscd(struct jbg_dec_state *s, unsigned char *data, /* - * Provide a new BIE fragment to the decoder. + * Provide to the decoder a new BIE fragment of len bytes starting at data. + * + * Unless cnt is NULL, *cnt will contain the number of actually read bytes + * on return. + * + * Normal return values: + * + * JBG_EAGAIN All data bytes provided so far have been processed + * (*cnt == len) but the end of the data stream has + * not yet been recognized. Call the function again + * with additional BIE bytes. + * JBG_EOK The function has reached the end of a and + * a full image has been decoded. The function can + * be called again with data from the next BIE, if + * there exists one, in order to get to a higher + * resolution layer. The remaining len - *cnt bytes + * of the previous data block will then have to passed + * to this function again if len > *cnt. + * JBG_EOK_INTR Parsing the BIE has been interrupted as had been + * requested by a jbg_dec_maxsize() specification. + * This function can be called again with the + * rest of the BIE to continue the decoding process. + * The remaining len - *cnt bytes of the previous + * data block will then have to be passed to this + * function again if len > *cnt. * - * If cnt is not NULL, then *cnt will contain after the call the - * number of actually read bytes. If the data was not complete, then - * the return value will be JBG_EAGAIN and *cnt == len. In case this - * function has returned with JBG_EOK, then it has reached the end of - * a BIE but it can be called again with data from the next BIE if - * there exists one in order to get to a higher resolution layer. In - * case the return value was JBG_EOK_INTR then this function can be - * called again with the rest of the BIE, because parsing the BIE has - * been interrupted by a jbg_dec_maxsize() specification. In both - * cases the remaining len - *cnt bytes of the previous block will - * have to passed to this function again (if len > *cnt). In case of - * any other return value than JBG_EOK, JBG_EOK_INTR or JBG_EAGAIN, a - * serious problem has occurred and the only function you should call - * is jbg_dec_free() in order to remove the mess (and probably - * jbg_strerror() in order to find out what to tell the user). + * Any other return value indicates that the decoding process was + * aborted by a serious problem and the only function you can then + * still call is jbg_dec_free() in order to remove the mess, and + * jbg85_strerror() to find out what to tell the user. (Looking at the + * least significant bits of the return value will provide additional + * information by identifying which test exactly has failed.) */ int jbg_dec_in(struct jbg_dec_state *s, unsigned char *data, size_t len, size_t *cnt) @@ -2340,9 +2570,8 @@ int jbg_dec_in(struct jbg_dec_state *s, unsigned char *data, size_t len, int i, j, required_length; unsigned long x, y; unsigned long is[3], ie[3]; - long hsize, lsize; - extern char jbg_dptable[]; size_t dummy_cnt; + unsigned char *dppriv; if (!cnt) cnt = &dummy_cnt; *cnt = 0; @@ -2354,92 +2583,112 @@ int jbg_dec_in(struct jbg_dec_state *s, unsigned char *data, size_t len, s->buffer[s->bie_len++] = data[(*cnt)++]; if (s->bie_len < 20) return JBG_EAGAIN; - if (s->buffer[1] < s->buffer[0]) - return JBG_EINVAL; /* test whether this looks like a valid JBIG header at all */ - if (s->buffer[3] != 0 || (s->buffer[18] & 0xf0) != 0 || - (s->buffer[19] & 0x80) != 0) - return JBG_EINVAL; + if (s->buffer[1] < s->buffer[0]) + return JBG_EINVAL | 1; + if (s->buffer[3] != 0) return JBG_EINVAL | 2; /* padding != 0 */ + if ((s->buffer[18] & 0xf0) != 0) return JBG_EINVAL | 3; /* padding != 0 */ + if ((s->buffer[19] & 0x80) != 0) return JBG_EINVAL | 4; /* padding != 0 */ if (s->buffer[0] != s->d + 1) - return JBG_ENOCONT; + return JBG_ENOCONT | 1; s->dl = s->buffer[0]; s->d = s->buffer[1]; if (s->dl == 0) s->planes = s->buffer[2]; else if (s->planes != s->buffer[2]) - return JBG_ENOCONT; + return JBG_ENOCONT | 2; x = (((long) s->buffer[ 4] << 24) | ((long) s->buffer[ 5] << 16) | ((long) s->buffer[ 6] << 8) | (long) s->buffer[ 7]); y = (((long) s->buffer[ 8] << 24) | ((long) s->buffer[ 9] << 16) | ((long) s->buffer[10] << 8) | (long) s->buffer[11]); if (s->dl != 0 && ((s->xd << (s->d - s->dl + 1)) != x && (s->yd << (s->d - s->dl + 1)) != y)) - return JBG_ENOCONT; + return JBG_ENOCONT | 3; s->xd = x; s->yd = y; s->l0 = (((long) s->buffer[12] << 24) | ((long) s->buffer[13] << 16) | ((long) s->buffer[14] << 8) | (long) s->buffer[15]); - if (!s->planes || !s->xd || !s->yd || !s->l0) - return JBG_EINVAL; + /* ITU-T T.85 trick not directly supported by decoder; for full + * T.85 compatibility with respect to all NEWLEN marker scenarios, + * preprocess BIE with jbg_newlen() before passing it to the decoder, + * or consider using the decoder found in jbig85.c instead. */ + if (s->yd == 0xffffffff) + return JBG_EIMPL | 1; + if (!s->planes) return JBG_EINVAL | 5; + if (!s->xd) return JBG_EINVAL | 6; + if (!s->yd) return JBG_EINVAL | 7; + if (!s->l0) return JBG_EINVAL | 8; + /* prevent uint32 overflow: s->l0 * 2 ^ s->d < 2 ^ 32 */ + if (s->d > 31) + return JBG_EIMPL | 2; + if ((s->d != 0 && s->l0 >= (1UL << (32 - s->d)))) + return JBG_EIMPL | 3; s->mx = s->buffer[16]; if (s->mx > 127) - return JBG_EINVAL; + return JBG_EINVAL | 9; s->my = s->buffer[17]; - if (s->mx > 32 || s->my > 0) - return JBG_EIMPL; +#if 0 + if (s->my > 0) + return JBG_EIMPL | 4; +#endif s->order = s->buffer[18]; - if (index[s->order & 7][0] < 0) - return JBG_EINVAL; + if (iindex[s->order & 7][0] < 0) + return JBG_EINVAL | 10; /* HITOLO and SEQ currently not yet implemented */ if (s->dl != s->d && (s->order & JBG_HITOLO || s->order & JBG_SEQ)) - return JBG_EIMPL; + return JBG_EIMPL | 5; s->options = s->buffer[19]; /* calculate number of stripes that will be required */ - s->stripes = ((s->yd >> s->d) + - ((((1UL << s->d) - 1) & s->xd) != 0) + s->l0 - 1) / s->l0; - + s->stripes = jbg_stripes(s->l0, s->yd, s->d); + /* some initialization */ - s->ii[index[s->order & 7][STRIPE]] = 0; - s->ii[index[s->order & 7][LAYER]] = s->dl; - s->ii[index[s->order & 7][PLANE]] = 0; - /* bytes required for resolution layer D and D-1 */ - hsize = ((s->xd + 7) / 8) * s->yd; - lsize = ((jbg_ceil_half(s->xd, 1) + 7) / 8) * - jbg_ceil_half(s->yd, 1); + s->ii[iindex[s->order & 7][STRIPE]] = 0; + s->ii[iindex[s->order & 7][LAYER]] = s->dl; + s->ii[iindex[s->order & 7][PLANE]] = 0; if (s->dl == 0) { - s->s = checked_malloc(s->planes * sizeof(struct jbg_ardec_state *)); - s->tx = checked_malloc(s->planes * sizeof(int *)); - s->ty = checked_malloc(s->planes * sizeof(int *)); - s->reset = checked_malloc(s->planes * sizeof(int *)); - s->lntp = checked_malloc(s->planes * sizeof(int *)); - s->lhp[0] = checked_malloc(s->planes * sizeof(unsigned char *)); - s->lhp[1] = checked_malloc(s->planes * sizeof(unsigned char *)); + s->s = (struct jbg_ardec_state **) + checked_malloc(s->planes, sizeof(struct jbg_ardec_state *)); + s->tx = (int **) checked_malloc(s->planes, sizeof(int *)); + s->ty = (int **) checked_malloc(s->planes, sizeof(int *)); + s->reset = (int **) checked_malloc(s->planes, sizeof(int *)); + s->lntp = (int **) checked_malloc(s->planes, sizeof(int *)); + s->lhp[0] = (unsigned char **) + checked_malloc(s->planes, sizeof(unsigned char *)); + s->lhp[1] = (unsigned char **) + checked_malloc(s->planes, sizeof(unsigned char *)); for (i = 0; i < s->planes; i++) { - s->s[i] = checked_malloc((s->d - s->dl + 1) * - sizeof(struct jbg_ardec_state)); - s->tx[i] = checked_malloc((s->d - s->dl + 1) * sizeof(int)); - s->ty[i] = checked_malloc((s->d - s->dl + 1) * sizeof(int)); - s->reset[i] = checked_malloc((s->d - s->dl + 1) * sizeof(int)); - s->lntp[i] = checked_malloc((s->d - s->dl + 1) * sizeof(int)); - s->lhp[s->d &1][i] = checked_malloc(sizeof(unsigned char) * hsize); - s->lhp[(s->d-1)&1][i] = checked_malloc(sizeof(unsigned char) * lsize); + s->s[i] = (struct jbg_ardec_state *) + checked_malloc(s->d - s->dl + 1, sizeof(struct jbg_ardec_state)); + s->tx[i] = (int *) checked_malloc(s->d - s->dl + 1, sizeof(int)); + s->ty[i] = (int *) checked_malloc(s->d - s->dl + 1, sizeof(int)); + s->reset[i] = (int *) checked_malloc(s->d - s->dl + 1, sizeof(int)); + s->lntp[i] = (int *) checked_malloc(s->d - s->dl + 1, sizeof(int)); + s->lhp[ s->d & 1][i] = (unsigned char *) + checked_malloc(s->yd, jbg_ceil_half(s->xd, 3)); + s->lhp[(s->d-1) & 1][i] = (unsigned char *) + checked_malloc(jbg_ceil_half(s->yd, 1), jbg_ceil_half(s->xd, 1+3)); } } else { for (i = 0; i < s->planes; i++) { - s->s[i] = checked_realloc(s->s[i], (s->d - s->dl + 1) * - sizeof(struct jbg_ardec_state)); - s->tx[i] = checked_realloc(s->tx[i], (s->d - s->dl + 1) * sizeof(int)); - s->ty[i] = checked_realloc(s->ty[i], (s->d - s->dl + 1) * sizeof(int)); - s->reset[i] = checked_realloc(s->reset[i], - (s->d - s->dl +1) * sizeof(int)); - s->lntp[i] = checked_realloc(s->lntp[i], - (s->d - s->dl +1) * sizeof(int)); - s->lhp[s->d &1][i] = checked_realloc(s->lhp[s->d & 1][i], - sizeof(unsigned char) * hsize); - s->lhp[(s->d-1)&1][i] = checked_realloc(s->lhp[(s->d-1)&1][i], - sizeof(unsigned char) * lsize); + s->s[i] = (struct jbg_ardec_state *) + checked_realloc(s->s[i], s->d - s->dl + 1, + sizeof(struct jbg_ardec_state)); + s->tx[i] = (int *) checked_realloc(s->tx[i], + s->d - s->dl + 1, sizeof(int)); + s->ty[i] = (int *) checked_realloc(s->ty[i], + s->d - s->dl + 1, sizeof(int)); + s->reset[i] = (int *) checked_realloc(s->reset[i], + s->d - s->dl + 1, sizeof(int)); + s->lntp[i] = (int *) checked_realloc(s->lntp[i], + s->d - s->dl + 1, sizeof(int)); + s->lhp[ s->d & 1][i] = (unsigned char *) + checked_realloc(s->lhp[ s->d & 1][i], + s->yd, jbg_ceil_half(s->xd, 3)); + s->lhp[(s->d-1) & 1][i] = (unsigned char *) + checked_realloc(s->lhp[(s->d-1) & 1][i], + jbg_ceil_half(s->yd, 1), jbg_ceil_half(s->xd, 1+3)); } } for (i = 0; i < s->planes; i++) @@ -2460,13 +2709,16 @@ int jbg_dec_in(struct jbg_dec_state *s, unsigned char *data, size_t len, (s->options & (JBG_DPON | JBG_DPPRIV | JBG_DPLAST)) == (JBG_DPON | JBG_DPPRIV)) { assert(s->bie_len >= 20); + if (!s->dppriv || s->dppriv == jbg_dptable) + s->dppriv = (char *) checked_malloc(1728, sizeof(char)); while (s->bie_len < 20 + 1728 && *cnt < len) - s->buffer[s->bie_len++ - 20] = data[(*cnt)++]; + s->dppriv[s->bie_len++ - 20] = data[(*cnt)++]; if (s->bie_len < 20 + 1728) return JBG_EAGAIN; - if (!s->dppriv || s->dppriv == jbg_dptable) - s->dppriv = checked_malloc(sizeof(char) * 1728); - jbg_dppriv2int(s->dppriv, s->buffer); + dppriv = (unsigned char *) s->dppriv; + s->dppriv = (char *) checked_malloc(6912, sizeof(char)); + jbg_dppriv2int(s->dppriv, dppriv); + checked_free(dppriv); } /* @@ -2516,7 +2768,7 @@ int jbg_dec_in(struct jbg_dec_state *s, unsigned char *data, size_t len, /* now the buffer is filled with exactly one marker segment */ switch (s->buffer[1]) { case MARKER_COMMENT: - s->comment_skip = + s->comment_skip = (((long) s->buffer[2] << 24) | ((long) s->buffer[3] << 16) | ((long) s->buffer[4] << 8) | (long) s->buffer[5]); break; @@ -2531,21 +2783,21 @@ int jbg_dec_in(struct jbg_dec_state *s, unsigned char *data, size_t len, s->at_tx[s->at_moves] > (int) s->mx || s->at_ty[s->at_moves] > (int) s->my || (s->at_ty[s->at_moves] == 0 && s->at_tx[s->at_moves] < 0)) - return JBG_EINVAL; + return JBG_EINVAL | 11; + if (s->at_ty[s->at_moves] != 0) + return JBG_EIMPL | 6; s->at_moves++; } else - return JBG_EINVAL; + return JBG_EIMPL | 7; /* more than JBG_ATMOVES_MAX ATMOVES */ break; case MARKER_NEWLEN: y = (((long) s->buffer[2] << 24) | ((long) s->buffer[3] << 16) | ((long) s->buffer[4] << 8) | (long) s->buffer[5]); - if (y > s->yd || !(s->options & JBG_VLENGTH)) - return JBG_EINVAL; + if (y > s->yd) return JBG_EINVAL | 12; + if (!(s->options & JBG_VLENGTH)) return JBG_EINVAL | 13; s->yd = y; /* calculate again number of stripes that will be required */ - s->stripes = - ((s->yd >> s->d) + - ((((1UL << s->d) - 1) & s->xd) != 0) + s->l0 - 1) / s->l0; + s->stripes = jbg_stripes(s->l0, s->yd, s->d); break; case MARKER_ABORT: return JBG_EABORT; @@ -2555,13 +2807,13 @@ int jbg_dec_in(struct jbg_dec_state *s, unsigned char *data, size_t len, /* decode final pixels based on trailing zero bytes */ decode_pscd(s, s->buffer, 2); - arith_decode_init(s->s[s->ii[index[s->order & 7][PLANE]]] + - s->ii[index[s->order & 7][LAYER]] - s->dl, - s->ii[index[s->order & 7][STRIPE]] != s->stripes - 1 + arith_decode_init(s->s[s->ii[iindex[s->order & 7][PLANE]]] + + s->ii[iindex[s->order & 7][LAYER]] - s->dl, + s->ii[iindex[s->order & 7][STRIPE]] != s->stripes - 1 && s->buffer[1] != MARKER_SDRST); - s->reset[s->ii[index[s->order & 7][PLANE]]] - [s->ii[index[s->order & 7][LAYER]] - s->dl] = + s->reset[s->ii[iindex[s->order & 7][PLANE]]] + [s->ii[iindex[s->order & 7][LAYER]] - s->dl] = (s->buffer[1] == MARKER_SDRST); /* prepare for next SDE */ @@ -2572,12 +2824,12 @@ int jbg_dec_in(struct jbg_dec_state *s, unsigned char *data, size_t len, /* increment layer/stripe/plane loop variables */ /* start and end value for each loop: */ - is[index[s->order & 7][STRIPE]] = 0; - ie[index[s->order & 7][STRIPE]] = s->stripes - 1; - is[index[s->order & 7][LAYER]] = s->dl; - ie[index[s->order & 7][LAYER]] = s->d; - is[index[s->order & 7][PLANE]] = 0; - ie[index[s->order & 7][PLANE]] = s->planes - 1; + is[iindex[s->order & 7][STRIPE]] = 0; + ie[iindex[s->order & 7][STRIPE]] = s->stripes - 1; + is[iindex[s->order & 7][LAYER]] = s->dl; + ie[iindex[s->order & 7][LAYER]] = s->d; + is[iindex[s->order & 7][PLANE]] = 0; + ie[iindex[s->order & 7][PLANE]] = s->planes - 1; i = 2; /* index to innermost loop */ do { j = 0; /* carry flag */ @@ -2593,12 +2845,16 @@ int jbg_dec_in(struct jbg_dec_state *s, unsigned char *data, size_t len, /* check whether this have been all SDEs */ if (j) { +#ifdef DEBUG + fprintf(stderr, "This was the final SDE in this BIE, " + "%ld bytes left.\n", (long) (len - *cnt)); +#endif s->bie_len = 0; return JBG_EOK; } /* check whether we have to abort because of xmax/ymax */ - if (index[s->order & 7][LAYER] == 0 && i < 0) { + if (iindex[s->order & 7][LAYER] == 0 && i < 0) { /* LAYER is the outermost loop and we have just gone to next layer */ if (jbg_ceil_half(s->xd, s->d - s->ii[0]) > s->xmax || jbg_ceil_half(s->yd, s->d - s->ii[0]) > s->ymax) { @@ -2629,7 +2885,7 @@ int jbg_dec_in(struct jbg_dec_state *s, unsigned char *data, size_t len, "%02x %02x %02x %02x ...\n", data[*cnt], data[*cnt+1], data[*cnt+2], data[*cnt+3]); #endif - return JBG_EINVAL; + return JBG_EINVAL | 14; } } @@ -2641,15 +2897,16 @@ int jbg_dec_in(struct jbg_dec_state *s, unsigned char *data, size_t len, /* * After jbg_dec_in() returned JBG_EOK or JBG_EOK_INTR, you can call this - * function in order to find out the width of the image. + * function in order to find out the width of the image. Returns 0 if + * there is no image available yet. */ -long jbg_dec_getwidth(const struct jbg_dec_state *s) +unsigned long jbg_dec_getwidth(const struct jbg_dec_state *s) { if (s->d < 0) - return -1; - if (index[s->order & 7][LAYER] == 0) { + return 0; + if (iindex[s->order & 7][LAYER] == 0) { if (s->ii[0] < 1) - return -1; + return 0; else return jbg_ceil_half(s->xd, s->d - (s->ii[0] - 1)); } @@ -2660,15 +2917,16 @@ long jbg_dec_getwidth(const struct jbg_dec_state *s) /* * After jbg_dec_in() returned JBG_EOK or JBG_EOK_INTR, you can call this - * function in order to find out the height of the image. + * function in order to find out the height of the image. Returns 0 if + * there is no image available yet. */ -long jbg_dec_getheight(const struct jbg_dec_state *s) +unsigned long jbg_dec_getheight(const struct jbg_dec_state *s) { if (s->d < 0) - return -1; - if (index[s->order & 7][LAYER] == 0) { + return 0; + if (iindex[s->order & 7][LAYER] == 0) { if (s->ii[0] < 1) - return -1; + return 0; else return jbg_ceil_half(s->yd, s->d - (s->ii[0] - 1)); } @@ -2679,13 +2937,14 @@ long jbg_dec_getheight(const struct jbg_dec_state *s) /* * After jbg_dec_in() returned JBG_EOK or JBG_EOK_INTR, you can call this - * function in order to get a pointer to the image. + * function in order to get a pointer to the image. Returns NULL if + * there is no image available yet. */ unsigned char *jbg_dec_getimage(const struct jbg_dec_state *s, int plane) { if (s->d < 0) return NULL; - if (index[s->order & 7][LAYER] == 0) { + if (iindex[s->order & 7][LAYER] == 0) { if (s->ii[0] < 1) return NULL; else @@ -2701,20 +2960,20 @@ unsigned char *jbg_dec_getimage(const struct jbg_dec_state *s, int plane) * this function in order to find out the size in bytes of one * bitplane of the image. */ -long jbg_dec_getsize(const struct jbg_dec_state *s) +unsigned long jbg_dec_getsize(const struct jbg_dec_state *s) { if (s->d < 0) - return -1; - if (index[s->order & 7][LAYER] == 0) { + return 0; + if (iindex[s->order & 7][LAYER] == 0) { if (s->ii[0] < 1) - return -1; + return 0; else return - ((jbg_ceil_half(s->xd, s->d - (s->ii[0] - 1)) + 7) / 8) * + jbg_ceil_half(s->xd, s->d - (s->ii[0] - 1) + 3) * /* overflow risk? */ jbg_ceil_half(s->yd, s->d - (s->ii[0] - 1)); } - return ((s->xd + 7) / 8) * s->yd; + return jbg_ceil_half(s->xd, 3) * s->yd; } @@ -2723,16 +2982,16 @@ long jbg_dec_getsize(const struct jbg_dec_state *s) * this function in order to find out the size of the image that you * can retrieve with jbg_merge_planes(). */ -long jbg_dec_getsize_merged(const struct jbg_dec_state *s) +unsigned long jbg_dec_getsize_merged(const struct jbg_dec_state *s) { if (s->d < 0) - return -1; - if (index[s->order & 7][LAYER] == 0) { + return 0; + if (iindex[s->order & 7][LAYER] == 0) { if (s->ii[0] < 1) - return -1; + return 0; else return - jbg_ceil_half(s->xd, s->d - (s->ii[0] - 1)) * + jbg_ceil_half(s->xd, s->d - (s->ii[0] - 1)) * /* overflow risk? */ jbg_ceil_half(s->yd, s->d - (s->ii[0] - 1)) * ((s->planes + 7) / 8); } @@ -2770,6 +3029,8 @@ void jbg_dec_free(struct jbg_dec_state *s) checked_free(s->lntp); checked_free(s->lhp[0]); checked_free(s->lhp[1]); + if (s->dppriv && s->dppriv != jbg_dptable) + checked_free(s->dppriv); s->s = NULL; @@ -2790,11 +3051,10 @@ void jbg_split_planes(unsigned long x, unsigned long y, int has_planes, const unsigned char *src, unsigned char **dest, int use_graycode) { - unsigned bpl = (x + 7) / 8; /* bytes per line in dest plane */ - unsigned i, k = 8; + unsigned long bpl = jbg_ceil_half(x, 3); /* bytes per line in dest plane */ + unsigned long line, i; + unsigned k = 8; int p; - unsigned long line; - extern void *memset(void *s, int c, size_t n); unsigned prev; /* previous *src byte shifted by 8 bit to the left */ register int bits, msb = has_planes - 1; int bitno; @@ -2818,7 +3078,7 @@ void jbg_split_planes(unsigned long x, unsigned long y, int has_planes, bits = (prev | *src) >> bitno; /* go to next *src byte, but keep old */ if (bitno == 0) - prev = *src++; + prev = *src++ << 8; /* make space for inserting new bit */ dest[p][bpl * line + i] <<= 1; /* insert bit, if requested apply Gray encoding */ @@ -2831,7 +3091,7 @@ void jbg_split_planes(unsigned long x, unsigned long y, int has_planes, } /* skip unused *src bytes */ for (;p < has_planes; p++) - if (((has_planes - 1 - p) & 7) == 0) + if (((msb - p) & 7) == 0) src++; } } @@ -2845,16 +3105,16 @@ void jbg_split_planes(unsigned long x, unsigned long y, int has_planes, /* * Merge the separate bit planes decoded by the JBIG decoder into an * integer pixel field. This is essentially the counterpart to - * jbg_split_planes(). */ + * jbg_split_planes(). + */ void jbg_dec_merge_planes(const struct jbg_dec_state *s, int use_graycode, void (*data_out)(unsigned char *start, size_t len, void *file), void *file) { #define BUFLEN 4096 - int bpp, bpl; - unsigned long line; - unsigned i, k = 8; - int p, q; + unsigned long bpl, line, i; + unsigned k = 8; + int p; unsigned char buf[BUFLEN]; unsigned char *bp = buf; unsigned char **src; @@ -2866,12 +3126,11 @@ void jbg_dec_merge_planes(const struct jbg_dec_state *s, int use_graycode, x = jbg_dec_getwidth(s); y = jbg_dec_getheight(s); - if (x <= 0 || y <= 0) + if (x == 0 || y == 0) return; - bpp = (s->planes + 7) / 8; /* bytes per pixel in dest image */ - bpl = (x + 7) / 8; /* bytes per line in src plane */ + bpl = jbg_ceil_half(x, 3); /* bytes per line in src plane */ - if (index[s->order & 7][LAYER] == 0) + if (iindex[s->order & 7][LAYER] == 0) if (s->ii[0] < 1) return; else @@ -2882,12 +3141,13 @@ void jbg_dec_merge_planes(const struct jbg_dec_state *s, int use_graycode, for (line = 0; line < y; line++) { /* lines loop */ for (i = 0; i * 8 < x; i++) { /* src bytes loop */ for (k = 0; k < 8 && i * 8 + k < x; k++) { /* pixel loop */ - for (p = (s->planes-1) & ~7; p >= 0; p -= 8) { /* dest bytes loop */ - v = 0; - for (q = 0; q < 8 && p+q < s->planes; q++) /* pixel bit loop */ + v = 0; + for (p = 0; p < s->planes;) { /* dest bytes loop */ + do { v = (v << 1) | - (((src[p+q][bpl * line + i] >> (7 - k)) & 1) ^ + (((src[p][bpl * line + i] >> (7 - k)) & 1) ^ (use_graycode & v)); + } while ((s->planes - ++p) & 7); *bp++ = v; if (bp - buf == BUFLEN) { data_out(buf, BUFLEN, file); @@ -2903,3 +3163,123 @@ void jbg_dec_merge_planes(const struct jbg_dec_state *s, int use_graycode, return; } + + +/* + * Given a pointer p to the first byte of either a marker segment or a + * PSCD, as well as the length len of the remaining data, return + * either the pointer to the first byte of the next marker segment or + * PSCD, or p+len if this was the last one, or NULL if some error was + * encountered. Possible errors are: + * + * - not enough bytes left for complete marker segment + * - no marker segment terminates the PSCD + * - unknown marker code encountered + * + */ +static unsigned char *jbg_next_pscdms(unsigned char *p, size_t len) +{ + unsigned char *pp; + unsigned long l; + + if (len < 2) + return NULL; /* not enough bytes left for complete marker segment */ + + if (p[0] != MARKER_ESC || p[1] == MARKER_STUFF) { + do { + while (p[0] == MARKER_ESC && p[1] == MARKER_STUFF) { + p += 2; + len -= 2; + if (len < 2) + return NULL; /* not enough bytes left for complete marker segment */ + } + assert(len >= 2); + pp = (unsigned char *) memchr(p, MARKER_ESC, len - 1); + if (!pp) + return NULL; /* no marker segment terminates the PSCD */ + l = pp - p; + assert(l < len); + p += l; + len -= l; + } while (p[1] == MARKER_STUFF); + } else { + switch (p[1]) { + case MARKER_SDNORM: + case MARKER_SDRST: + case MARKER_ABORT: + return p + 2; + case MARKER_NEWLEN: + if (len < 6) + return NULL; /* not enough bytes left for complete marker segment */ + return p + 6; + case MARKER_ATMOVE: + if (len < 8) + return NULL; /* not enough bytes left for complete marker segment */ + return p + 8; + case MARKER_COMMENT: + if (len < 6) + return NULL; /* not enough bytes left for complete marker segment */ + l = (((long) p[2] << 24) | ((long) p[3] << 16) | + ((long) p[4] << 8) | (long) p[5]); + if (len - 6 < l) + return NULL; /* not enough bytes left for complete marker segment */ + return p + 6 + l; + default: + /* unknown marker sequence encountered */ + return NULL; + } + } + + return p; +} + + +/* + * Scan a complete BIE for a NEWLEN marker segment, then read the new + * YD value found in it and use it to overwrite the one in the BIE + * header. Use this procedure if a BIE initially declares an + * unreasonably high provisional YD value (e.g., 0xffffffff) or + * depends on the fact that section 6.2.6.2 of ITU-T T.82 says that a + * NEWLEN marker segment "could refer to a line in the immediately + * preceding stripe due to an unexpected termination of the image or + * the use of only such stripe". ITU-T.85 explicitely suggests the + * use of this for fax machines that start transmission before having + * encountered the end of the page. None of this is necessary for + * BIEs produced by JBIG-KIT, which normally does not use NEWLEN. + */ +int jbg_newlen(unsigned char *bie, size_t len) +{ + unsigned char *p = bie + 20; + int i; + unsigned long y, yn; + + if (len < 20) + return JBG_EAGAIN; + if ((bie[19] & (JBG_DPON | JBG_DPPRIV | JBG_DPLAST)) + == (JBG_DPON | JBG_DPPRIV)) + p += 1728; /* skip DPTABLE */ + if (p >= bie + len) + return JBG_EAGAIN; + + while ((p = jbg_next_pscdms(p, len - (p - bie)))) { + if (p == bie + len) + return JBG_EOK; + else if (p[0] == MARKER_ESC) + switch (p[1]) { + case MARKER_NEWLEN: + y = (((long) bie[ 8] << 24) | ((long) bie[ 9] << 16) | + ((long) bie[10] << 8) | (long) bie[11]); + yn = (((long) p[2] << 24) | ((long) p[3] << 16) | + ((long) p[4] << 8) | (long) p[5]); + if (yn > y) return JBG_EINVAL | 12; + /* overwrite YD in BIH with YD from NEWLEN */ + for (i = 0; i < 4; i++) { + bie[8+i] = p[2+i]; + } + return JBG_EOK; + case MARKER_ABORT: + return JBG_EABORT; + } + } + return JBG_EINVAL | 0; +} |