/*

 *  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;

}