shithub: jbig2

ref: 2d6d6e0c7b2c97e52a3363eae09841a17fe8e272
dir: /jbig2_arith.c/

View raw version
/*
    jbig2dec
    
    Copyright (c) 2001 artofcode LLC.
    
    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.

    $Id: jbig2_arith.c,v 1.7 2002/02/16 07:25:36 raph Exp $
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#include "jbig2.h"
#include "jbig2_priv.h"
#include "jbig2_arith.h"

#ifdef DEBUG
#include <stdio.h>
#endif

struct _Jbig2ArithState {
  uint32_t C;
  int A;

  int CT;

  uint32_t next_word;
  int next_word_bytes;

  Jbig2WordStream *ws;
  int offset;
};

#undef SOFTWARE_CONVENTION

/*
  A note on the "software conventions".

  The spec (in both draft and final versions) gives a "software
  conventions" version of the arithmetic decoding procedure. It is not
  normative, which is good, because it's wrong.

  The value of C in the "software conventions" is nominally equal to
  -C + (0x10000 >> CT) + (A << 16). However, the leftmost branch of
  Figure G.3 gives a very wrong value for C, based on this equation.
  Changing the (B << 9) to (B << 8) restores the invariant, and gives
  correct decoding of the H.2 test sequence. However, the decoding of
  the 042_4.jb2 test bitstream is incorrect, even with this change.
  Changing the "Chigh < A?" predicate in Figure G.2 to "C < (A << 16)"
  restores correct decoding for bitstream, but I'm not sure this is
  100% correct.

  In any case, my benchmarking indicates no speed difference at all.
  Therefore, for now we will just use the normative version. If
  somebody wants to figure out how to do the software conventions
  version correctly, and can establish that it really does improve
  performance, it might be worthwhile to revisit.

 */

static void
jbig2_arith_bytein (Jbig2ArithState *as)
{
  byte B;

  if (as->next_word_bytes == 0)
    {
      Jbig2WordStream *ws = as->ws;
      as->next_word = ws->get_next_word (ws, as->offset);
      as->offset += 4;
      as->next_word_bytes = 4;
    }
  /* Figure G.3 */
  B = (as->next_word >> 24) & 0xFF;
  if (B == 0xFF)
    {
      byte B1;
      if (as->next_word_bytes == 1)
	{
	  Jbig2WordStream *ws = as->ws;
	  as->next_word = ws->get_next_word (ws, as->offset);
	  as->offset += 4;
	  B1 = (as->next_word >> 24) & 0xFF;
	  if (B1 > 0x8F)
	    {
#ifdef DEBUG
	      printf ("read %02x (aa)\n", B);
#endif
#ifndef SOFTWARE_CONVENTION
	      as->C += 0xFF00;
#endif
	      as->CT = 8;
	      as->next_word = (0xFF00 | B1) << 16;
	      as->next_word_bytes = 2;
	    }
	  else
	    {
#ifdef DEBUG
	      printf ("read %02x (a)\n", B);
#endif
#ifdef SOFTWARE_CONVENTION
	      /* Note: this is what the spec says. The spec is wrong. */
	      as->C += 0xFE00 - (B << 9);
#else
	      as->C += 0xFF00;
#endif
	      as->CT = 7;
	      as->next_word_bytes = 4;
	    }
	}
      else
	{
	  B1 = (as->next_word >> 16) & 0xFF;
	  if (B1 > 0x8F)
	    {
#ifdef DEBUG
	      printf ("read %02x (ba)\n", B);
#endif
#ifndef SOFTWARE_CONVENTION
	      as->C += 0xFF00;
#endif
	      as->CT = 8;
	    }
	  else
	    {
	      as->next_word_bytes--;
	      as->next_word <<= 8;
#ifdef DEBUG
	      printf ("read %02x (b)\n", B);
#endif

#ifdef SOFTWARE_CONVENTION
	      /* Note: this is what the spec says. The spec is wrong. */
	      as->C += 0xFE00 - (B << 9);
#else
	      as->C += 0xFF00;
#endif
	      as->CT = 7;
	    }
	}
    }
  else
    {
#ifdef DEBUG
      printf ("read %02x\n", B);
#endif
#ifdef SOFTWARE_CONVENTION
      as->C += 0xFF00 - (B << 8);
#else
      as->C += (B << 8);
#endif
      as->CT = 8;
      as->next_word <<= 8;
      as->next_word_bytes--;
    }
}

#ifdef DEBUG
#include <stdio.h>

static void
jbig2_arith_trace (Jbig2ArithState *as, Jbig2ArithCx cx)
{
  printf ("I = %2d, MPS = %d, A = %04x, CT = %2d, C = %08x\n",
	  cx & 0x7f, cx >> 7, as->A, as->CT, as->C);
}
#endif

Jbig2ArithState *
jbig2_arith_new (Jbig2Ctx *ctx, Jbig2WordStream *ws)
{
  Jbig2ArithState *result = (Jbig2ArithState *)malloc (sizeof(Jbig2ArithState));

  result->ws = ws;

  result->next_word = ws->get_next_word (ws, 0);
  result->next_word_bytes = 4;
  result->offset = 4;

  /* Figure G.1 */
#ifdef SOFTWARE_CONVENTION
  result->C = (~(result->next_word >> 8)) & 0xFF0000;
#else
  result->C = (result->next_word >> 8) & 0xFF0000;
#endif
  result->next_word <<= 8;
  result->next_word_bytes--;

  jbig2_arith_bytein (result);
  result->C <<= 7;
  result->CT -= 7;
  result->A = 0x8000;

  return result;
};

/* could put bit fields in to minimize memory usage */
typedef struct {
  unsigned short Qe;
  byte mps_xor; /* mps_xor = index ^ NMPS */
  byte lps_xor; /* lps_xor = index ^ NLPS ^ (SWITCH << 7) */
} Jbig2ArithQe;

const Jbig2ArithQe jbig2_arith_Qe[] = {
  { 0x5601,  1 ^  0,  1 ^  0 ^ 0x80 },
  { 0x3401,  2 ^  1,  6 ^  1 },
  { 0x1801,  3 ^  2,  9 ^  2 },
  { 0x0AC1,  4 ^  3, 12 ^  3 },
  { 0x0521,  5 ^  4, 29 ^  4 },
  { 0x0221, 38 ^  5, 33 ^  5 },
  { 0x5601,  7 ^  6,  6 ^  6 ^ 0x80 },
  { 0x5401,  8 ^  7, 14 ^  7 },
  { 0x4801,  9 ^  8, 14 ^  8 },
  { 0x3801, 10 ^  9, 14 ^  9 },
  { 0x3001, 11 ^ 10, 17 ^ 10 },
  { 0x2401, 12 ^ 11, 18 ^ 11 },
  { 0x1C01, 13 ^ 12, 20 ^ 12 },
  { 0x1601, 29 ^ 13, 21 ^ 13 },
  { 0x5601, 15 ^ 14, 14 ^ 14 ^ 0x80 },
  { 0x5401, 16 ^ 15, 14 ^ 15 },
  { 0x5101, 17 ^ 16, 15 ^ 16 },
  { 0x4801, 18 ^ 17, 16 ^ 17 },
  { 0x3801, 19 ^ 18, 17 ^ 18 },
  { 0x3401, 20 ^ 19, 18 ^ 19 },
  { 0x3001, 21 ^ 20, 19 ^ 20 },
  { 0x2801, 22 ^ 21, 19 ^ 21 },
  { 0x2401, 23 ^ 22, 20 ^ 22 },
  { 0x2201, 24 ^ 23, 21 ^ 23 },
  { 0x1C01, 25 ^ 24, 22 ^ 24 },
  { 0x1801, 26 ^ 25, 23 ^ 25 },
  { 0x1601, 27 ^ 26, 24 ^ 26 },
  { 0x1401, 28 ^ 27, 25 ^ 27 },
  { 0x1201, 29 ^ 28, 26 ^ 28 },
  { 0x1101, 30 ^ 29, 27 ^ 29 },
  { 0x0AC1, 31 ^ 30, 28 ^ 30 },
  { 0x09C1, 32 ^ 31, 29 ^ 31 },
  { 0x08A1, 33 ^ 32, 30 ^ 32 },
  { 0x0521, 34 ^ 33, 31 ^ 33 },
  { 0x0441, 35 ^ 34, 32 ^ 34 },
  { 0x02A1, 36 ^ 35, 33 ^ 35 },
  { 0x0221, 37 ^ 36, 34 ^ 36 },
  { 0x0141, 38 ^ 37, 35 ^ 37 },
  { 0x0111, 39 ^ 38, 36 ^ 38 },
  { 0x0085, 40 ^ 39, 37 ^ 39 },
  { 0x0049, 41 ^ 40, 38 ^ 40 },
  { 0x0025, 42 ^ 41, 39 ^ 41 },
  { 0x0015, 43 ^ 42, 40 ^ 42 },
  { 0x0009, 44 ^ 43, 41 ^ 43 },
  { 0x0005, 45 ^ 44, 42 ^ 44 },
  { 0x0001, 45 ^ 45, 43 ^ 45 },
  { 0x5601, 46 ^ 46, 46 ^ 46 }
};

static void
jbig2_arith_renormd (Jbig2ArithState *as)
{
  /* Figure E.18 */
  do
    {
      if (as->CT == 0)
	jbig2_arith_bytein (as);
      as->A <<= 1;
      as->C <<= 1;
      as->CT--;
    }
  while ((as->A & 0x8000) == 0);
}

bool
jbig2_arith_decode (Jbig2ArithState *as, Jbig2ArithCx *pcx)
{
  Jbig2ArithCx cx = *pcx;
  const Jbig2ArithQe *pqe = &jbig2_arith_Qe[cx & 0x7f];
  bool D;

  /* Figure G.2 */
  as->A -= pqe->Qe;
  if (
#ifdef SOFTWARE_CONVENTION
      /* Note: I do not think this is correct. See above. */
      (as->C >> 16) < as->A
#else
      !((as->C >> 16) < pqe->Qe)
#endif
      )
    {
#ifndef SOFTWARE_CONVENTION
      as->C -= pqe->Qe << 16;
#endif
      if ((as->A & 0x8000) == 0)
	{
	  /* MPS_EXCHANGE, Figure E.16 */
	  if (as->A < pqe->Qe)
	    {
	      D = 1 - (cx >> 7);
	      *pcx ^= pqe->lps_xor;
	    }
	  else
	    {
	      D = cx >> 7;
	      *pcx ^= pqe->mps_xor;
	    }
	  jbig2_arith_renormd (as);
	  return D;
	}
      else
	return cx >> 7;
    }
  else
    {
#ifdef SOFTWARE_CONVENTION
      as->C -= (as->A) << 16;
#endif
      /* LPS_EXCHANGE, Figure E.17 */
      if (as->A < pqe->Qe)
	{
	  as->A = pqe->Qe;
	  D = cx >> 7;
	  *pcx ^= pqe->mps_xor;
	}
      else
	{
	  as->A = pqe->Qe;
	  D = 1 - (cx >> 7);
	  *pcx ^= pqe->lps_xor;
	}
      jbig2_arith_renormd (as);
      return D;
    }
}

#ifdef TEST

static int32_t
test_get_word (Jbig2WordStream *self, int offset)
{
  byte stream[] = {
    0x84, 0xC7, 0x3B, 0xFC, 0xE1, 0xA1, 0x43, 0x04, 0x02, 0x20, 0x00, 0x00,
    0x41, 0x0D, 0xBB, 0x86, 0xF4, 0x31, 0x7F, 0xFF, 0x88, 0xFF, 0x37, 0x47,
    0x1A, 0xDB, 0x6A, 0xDF, 0xFF, 0xAC,
    0x00, 0x00
  };
  if (offset >= sizeof(stream))
    return 0;
  else
    return (stream[offset] << 24) | (stream[offset + 1] << 16) |
      (stream[offset + 2] << 8) | stream[offset + 3];
}

int
main (int argc, char **argv)
{
  Jbig2WordStream ws;
  Jbig2ArithState *as;
  int i;
  Jbig2ArithCx cx = 0;

  ws.get_next_word = test_get_word;
  as = jbig2_arith_new (NULL, &ws);
  jbig2_arith_trace (as, cx);

  for (i = 0; i < 256; i++)
    {
      bool D;

      D = jbig2_arith_decode (as, &cx);
      printf ("%3d: D = %d, ", i, D);
      jbig2_arith_trace (as, cx);
      
    }
  return 0;
}
#endif