diff options
Diffstat (limited to 'converter/other/jbig/libjbig/jbig_ar.c')
| -rw-r--r-- | converter/other/jbig/libjbig/jbig_ar.c | 417 |
1 files changed, 417 insertions, 0 deletions
diff --git a/converter/other/jbig/libjbig/jbig_ar.c b/converter/other/jbig/libjbig/jbig_ar.c new file mode 100644 index 00000000..d23a317d --- /dev/null +++ b/converter/other/jbig/libjbig/jbig_ar.c @@ -0,0 +1,417 @@ +/* + * Arithmetic encoder and decoder of the portable JBIG + * compression library + * + * Markus Kuhn -- http://www.cl.cam.ac.uk/~mgk25/jbigkit/ + * + * This module implements a portable standard C arithmetic encoder + * and decoder used by the JBIG lossless bi-level image compression + * algorithm as specified in International Standard ISO 11544:1993 + * and ITU-T Recommendation T.82. + * + * 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 + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + * + * If you want to use this program under different license conditions, + * then contact the author for an arrangement. + */ + +#include <assert.h> +#include "jbig_ar.h" + +/* + * Probability estimation tables for the arithmetic encoder/decoder + * given by ITU T.82 Table 24. + */ + +static short lsztab[113] = { + 0x5a1d, 0x2586, 0x1114, 0x080b, 0x03d8, 0x01da, 0x00e5, 0x006f, + 0x0036, 0x001a, 0x000d, 0x0006, 0x0003, 0x0001, 0x5a7f, 0x3f25, + 0x2cf2, 0x207c, 0x17b9, 0x1182, 0x0cef, 0x09a1, 0x072f, 0x055c, + 0x0406, 0x0303, 0x0240, 0x01b1, 0x0144, 0x00f5, 0x00b7, 0x008a, + 0x0068, 0x004e, 0x003b, 0x002c, 0x5ae1, 0x484c, 0x3a0d, 0x2ef1, + 0x261f, 0x1f33, 0x19a8, 0x1518, 0x1177, 0x0e74, 0x0bfb, 0x09f8, + 0x0861, 0x0706, 0x05cd, 0x04de, 0x040f, 0x0363, 0x02d4, 0x025c, + 0x01f8, 0x01a4, 0x0160, 0x0125, 0x00f6, 0x00cb, 0x00ab, 0x008f, + 0x5b12, 0x4d04, 0x412c, 0x37d8, 0x2fe8, 0x293c, 0x2379, 0x1edf, + 0x1aa9, 0x174e, 0x1424, 0x119c, 0x0f6b, 0x0d51, 0x0bb6, 0x0a40, + 0x5832, 0x4d1c, 0x438e, 0x3bdd, 0x34ee, 0x2eae, 0x299a, 0x2516, + 0x5570, 0x4ca9, 0x44d9, 0x3e22, 0x3824, 0x32b4, 0x2e17, 0x56a8, + 0x4f46, 0x47e5, 0x41cf, 0x3c3d, 0x375e, 0x5231, 0x4c0f, 0x4639, + 0x415e, 0x5627, 0x50e7, 0x4b85, 0x5597, 0x504f, 0x5a10, 0x5522, + 0x59eb +}; + +static unsigned char nmpstab[113] = { + 1, 2, 3, 4, 5, 6, 7, 8, + 9, 10, 11, 12, 13, 13, 15, 16, + 17, 18, 19, 20, 21, 22, 23, 24, + 25, 26, 27, 28, 29, 30, 31, 32, + 33, 34, 35, 9, 37, 38, 39, 40, + 41, 42, 43, 44, 45, 46, 47, 48, + 49, 50, 51, 52, 53, 54, 55, 56, + 57, 58, 59, 60, 61, 62, 63, 32, + 65, 66, 67, 68, 69, 70, 71, 72, + 73, 74, 75, 76, 77, 78, 79, 48, + 81, 82, 83, 84, 85, 86, 87, 71, + 89, 90, 91, 92, 93, 94, 86, 96, + 97, 98, 99, 100, 93, 102, 103, 104, + 99, 106, 107, 103, 109, 107, 111, 109, + 111 +}; + +/* + * least significant 7 bits (mask 0x7f) of nlpstab[] contain NLPS value, + * most significant bit (mask 0x80) contains SWTCH bit + */ +static unsigned char nlpstab[113] = { + 129, 14, 16, 18, 20, 23, 25, 28, + 30, 33, 35, 9, 10, 12, 143, 36, + 38, 39, 40, 42, 43, 45, 46, 48, + 49, 51, 52, 54, 56, 57, 59, 60, + 62, 63, 32, 33, 165, 64, 65, 67, + 68, 69, 70, 72, 73, 74, 75, 77, + 78, 79, 48, 50, 50, 51, 52, 53, + 54, 55, 56, 57, 58, 59, 61, 61, + 193, 80, 81, 82, 83, 84, 86, 87, + 87, 72, 72, 74, 74, 75, 77, 77, + 208, 88, 89, 90, 91, 92, 93, 86, + 216, 95, 96, 97, 99, 99, 93, 223, + 101, 102, 103, 104, 99, 105, 106, 107, + 103, 233, 108, 109, 110, 111, 238, 112, + 240 +}; + +/* + * The next functions implement the arithmedic encoder and decoder + * required for JBIG. The same algorithm is also used in the arithmetic + * variant of JPEG. + */ + +/* marker codes */ +#define MARKER_STUFF 0x00 +#define MARKER_ESC 0xff + +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; +} + + +void arith_encode_flush(struct jbg_arenc_state *s) +{ + unsigned long temp; + + /* 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; +} + + +void arith_encode(struct jbg_arenc_state *s, int cx, int pix) +{ + register unsigned lsz, ss; + register unsigned char *st; + long temp; + + assert(cx >= 0 && cx < 4096); + st = s->st + cx; + ss = *st & 0x7f; + assert(ss < 113); + lsz = lsztab[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 ^= nlpstab[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 |= nmpstab[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; +} + + +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->startup = 1; + s->nopadding = 0; + return; +} + +/* + * Decode and return one symbol from the provided PSCD byte stream + * that starts in s->pscd_ptr and ends in the byte before s->pscd_end. + * The context cx is a 12-bit integer in the range 0..4095. This + * function will advance s->pscd_ptr each time it has consumed all + * information from that PSCD byte. + * + * If a symbol has been decoded successfully, the return value will be + * 0 or 1 (depending on the symbol). + * + * If the decoder was not able to decode a symbol from the provided + * PSCD, then the return value will be -1, and two cases can be + * distinguished: + * + * s->pscd_ptr == s->pscd_end: + * + * The decoder has used up all information in the provided PSCD + * bytes. Further PSCD bytes have to be provided (via new values of + * s->pscd_ptr and/or s->pscd_end) before another symbol can be + * decoded. + * + * s->pscd_ptr == s->pscd_end - 1: + * + * The decoder has used up all provided PSCD bytes except for the + * very last byte, because that has the value 0xff. The decoder can + * at this point not yet tell whether this 0xff belongs to a + * MARKER_STUFF sequence or marks the end of the PSCD. Further PSCD + * bytes have to be provided (via new values of s->pscd_ptr and/or + * s->pscd_end), including the not yet processed 0xff byte, before + * another symbol can be decoded successfully. + * + * If s->nopadding != 0, the decoder will return -2 when it reaches + * the first two bytes of the marker segment that follows (and + * terminates) the PSCD, but before decoding the first symbol that + * depends on a bit in the input data that could have been the result + * of zero padding, and might, therefore, never have been encoded. + * This gives the caller the opportunity to lookahead early enough + * beyond a terminating SDNORM/SDRST for a trailing NEWLEN (as + * required by T.85) before decoding remaining symbols. Call the + * decoder again afterwards as often as necessary (leaving s->pscd_ptr + * pointing to the start of the marker segment) to retrieve any + * required remaining symbols that might depend on padding. + * + * [Note that each PSCD can be decoded into an infinitely long + * sequence of symbols, because the encoder might have truncated away + * an arbitrarily long sequence of trailing 0x00 bytes, which the + * decoder will append automatically as needed when it reaches the end + * of the PSCD. Therefore, the decoder cannot report any end of the + * symbol sequence and other means (external to the PSCD and + * arithmetic decoding process) are needed to determine that.] + */ + +int arith_decode(struct jbg_ardec_state *s, int cx) +{ + register unsigned lsz, ss; + register unsigned char *st; + int pix; + + /* renormalization */ + while (s->a < 0x8000 || s->startup) { + while (s->ct <= 8 && s->ct >= 0) { + /* first we can move a new byte into s->c */ + if (s->pscd_ptr >= s->pscd_end) { + return -1; /* more bytes needed */ + } + if (*s->pscd_ptr == 0xff) + if (s->pscd_ptr + 1 >= s->pscd_end) { + return -1; /* final 0xff byte not processed */ + } else { + if (*(s->pscd_ptr + 1) == MARKER_STUFF) { + s->c |= 0xffL << (8 - s->ct); + s->ct += 8; + s->pscd_ptr += 2; + } else { + s->ct = -1; /* start padding with zero bytes */ + if (s->nopadding) { + s->nopadding = 0; + return -2; /* subsequent symbols might depend on zero padding */ + } + } + } + else { + s->c |= (long)*(s->pscd_ptr++) << (8 - s->ct); + s->ct += 8; + } + } + s->c <<= 1; + s->a <<= 1; + if (s->ct >= 0) s->ct--; + if (s->a == 0x10000L) + s->startup = 0; + } + + st = s->st + cx; + ss = *st & 0x7f; + assert(ss < 113); + lsz = lsztab[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 ^= nlpstab[ss]; + } else { + pix = *st >> 7; + *st &= 0x80; + *st |= nmpstab[ss]; + } + } + else { + /* LPS_EXCHANGE */ + if (s->a < lsz) { + s->c -= s->a << 16; + s->a = lsz; + pix = *st >> 7; + *st &= 0x80; + *st |= nmpstab[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 ^= nlpstab[ss]; + } + } + + return pix; +} |