/src/ghostpdl/jbig2dec/jbig2_arith.c

Source
/* Copyright (C) 2001-2023 Artifex Software, Inc.
   All Rights Reserved.

   This software is provided AS-IS with no warranty, either express or
   implied.

   This software is distributed under license and may not be copied,
   modified or distributed except as expressly authorized under the terms
   of the license contained in the file LICENSE in this distribution.

   Refer to licensing information at http://www.artifex.com or contact
   Artifex Software, Inc.,  39 Mesa Street, Suite 108A, San Francisco,
   CA 94129, USA, for further information.
*/

/*
    jbig2dec
*/

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
#include "os_types.h"

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

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

struct _Jbig2ArithState {
    uint32_t C;
    uint32_t A;

    int CT;

    uint32_t next_word;
    size_t next_word_bytes;
    int err;

    Jbig2WordStream *ws;
    size_t offset;
};

/*
  Previous versions of this code had a #define to allow
  us to choose between using the revised arithmetic decoding
  specified in the 'Software Convention' section of the spec.
  Back to back tests showed that the 'Software Convention'
  version was indeed slightly faster. We therefore enable it
  by default. We also strip the option out, because a) it
  makes the code harder to read, and b) such things are an
  invitation to bitrot.
*/

static int
jbig2_arith_bytein(Jbig2Ctx *ctx, Jbig2ArithState *as)
{
    byte B;

    /* Treat both errors and reading beyond end of stream as an error. */
    if (as->err != 0) {
        jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read from underlying stream during arithmetic decoding");
        return -1;
    }
    if (as->next_word_bytes == 0) {
        jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read beyond end of underlying stream during arithmetic decoding");
        return -1;
    }

    /* At this point there is at least one byte in as->next_word. */

    /* This code confused me no end when I first read it, so a quick note
     * to save others (and future me's) from being similarly confused.
     * 'next_word' does indeed contain 'next_word_bytes' of valid data
     * (always starting at the most significant byte). The confusing
     * thing is that the first byte has always already been read.
     * i.e. it serves only as an indication that the last byte we read
     * was FF or not.
     *
     * The jbig2 bytestream uses FF bytes, followed by a byte > 0x8F as
     * marker bytes. These never occur in normal streams of arithmetic
     * encoding, so meeting one terminates the stream (with an infinite
     * series of 1 bits).
     *
     * If we meet an FF byte, we return it as normal. We just 'remember'
     * that fact for the next byte we read.
     */

    /* Figure F.3 */
    B = (byte)((as->next_word >> 24) & 0xFF);
    if (B == 0xFF) {
        byte B1;

        /* next_word_bytes can only be == 1 here, but let's be defensive. */
        if (as->next_word_bytes <= 1) {
            int ret = as->ws->get_next_word(ctx, as->ws, as->offset, &as->next_word);
            if (ret < 0) {
                as->err = 1;
                return jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to check for marker code due to failure in underlying stream during arithmetic decoding");
            }
            as->next_word_bytes = (size_t) ret;

            if (as->next_word_bytes == 0) {
                jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read end of possible terminating marker code, assuming terminating marker code");
                as->next_word = 0xFF900000;
                as->next_word_bytes = 2;
                as->C += 0xFF00;
                as->CT = 8;
                return 0;
            }

            as->offset += as->next_word_bytes;

            B1 = (byte)((as->next_word >> 24) & 0xFF);
            if (B1 > 0x8F) {
#ifdef JBIG2_DEBUG_ARITH
                fprintf(stderr, "read %02x (aa)\n", B);
#endif
                as->CT = 8;
                as->next_word = 0xFF000000 | (as->next_word >> 8);
                as->next_word_bytes = 2;
                as->offset--;
            } else {
#ifdef JBIG2_DEBUG_ARITH
                fprintf(stderr, "read %02x (a)\n", B);
#endif
                as->C += 0xFE00 - (B1 << 9);
                as->CT = 7;
            }
        } else {
            B1 = (byte)((as->next_word >> 16) & 0xFF);
            if (B1 > 0x8F) {
#ifdef JBIG2_DEBUG_ARITH
                fprintf(stderr, "read %02x (ba)\n", B);
#endif
                as->CT = 8;
            } else {
                as->next_word_bytes--;
                as->next_word <<= 8;
#ifdef JBIG2_DEBUG_ARITH
                fprintf(stderr, "read %02x (b)\n", B);
#endif

                as->C += 0xFE00 - (B1 << 9);
                as->CT = 7;
            }
        }
    } else {
#ifdef JBIG2_DEBUG_ARITH
        fprintf(stderr, "read %02x\n", B);
#endif
        as->next_word <<= 8;
        as->next_word_bytes--;

        if (as->next_word_bytes == 0) {
            int ret = as->ws->get_next_word(ctx, as->ws, as->offset, &as->next_word);
            if (ret < 0) {
                as->err = 1;
                return jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read from underlying stream during arithmetic decoding");
            }
            as->next_word_bytes = (size_t) ret;

            if (as->next_word_bytes == 0) {
                jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to find terminating marker code before end of underlying stream, assuming terminating marker code");
                as->next_word = 0xFF900000;
                as->next_word_bytes = 2;
                as->C += 0xFF00;
                as->CT = 8;
                return 0;
            }

            as->offset += as->next_word_bytes;
        }

        B = (byte)((as->next_word >> 24) & 0xFF);
        as->C += 0xFF00 - (B << 8);
        as->CT = 8;
    }

    return 0;
}

/** Allocate and initialize a new arithmetic coding state
 *  the returned pointer can simply be freed; this does
 *  not affect the associated Jbig2WordStream.
 */
Jbig2ArithState *
jbig2_arith_new(Jbig2Ctx *ctx, Jbig2WordStream *ws)
{
    Jbig2ArithState *result;
    int ret;

    result = jbig2_new(ctx, Jbig2ArithState, 1);
    if (result == NULL) {
        jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to allocate arithmetic coding state");
        return NULL;
    }

    result->err = 0;
    result->ws = ws;
    result->offset = 0;

    ret = result->ws->get_next_word(ctx, result->ws, result->offset, &result->next_word);
    if (ret < 0) {
        jbig2_free(ctx->allocator, result);
        jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to initialize underlying stream of arithmetic decoder");
        return NULL;
    }

    result->next_word_bytes = (size_t) ret;
    if (result->next_word_bytes == 0) {
        jbig2_free(ctx->allocator, result);
        jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read first byte from underlying stream when initializing arithmetic decoder");
        return NULL;
    }

    result->offset += result->next_word_bytes;

    /* Figure F.1 */
    result->C = (~(result->next_word >> 8)) & 0xFF0000;

    /* Figure E.20 (2) */
    if (jbig2_arith_bytein(ctx, result) < 0) {
        jbig2_free(ctx->allocator, result);
        jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read second byte from underlying stream when initializing arithmetic decoder");
        return NULL;
    }

    /* Figure E.20 (3) */
    result->C <<= 7;
    result->CT -= 7;
    result->A = 0x8000;

    return result;
}

#define MAX_QE_ARRAY_SIZE 47

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

#define MPS(index, nmps) ((index) ^ (nmps))
#define LPS(index, nlps, swtch) ((index) ^ (nlps) ^ ((swtch) << 7))

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

static int
jbig2_arith_renormd(Jbig2Ctx *ctx, Jbig2ArithState *as)
{
    /* Figure E.18 */
    do {
        if (as->CT == 0 && jbig2_arith_bytein(ctx, as) < 0) {
            return jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read byte from compressed data stream");
        }
        as->A <<= 1;
        as->C <<= 1;
        as->CT--;
    } while ((as->A & 0x8000) == 0);

    return 0;
}

int
jbig2_arith_decode(Jbig2Ctx *ctx, Jbig2ArithState *as, Jbig2ArithCx *pcx)
{
    Jbig2ArithCx cx = *pcx;
    const Jbig2ArithQe *pqe;
    unsigned int index = cx & 0x7f;
    bool D;

    if (index >= MAX_QE_ARRAY_SIZE) {
        return jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to determine probability estimate because index out of range");
    }

    pqe = &jbig2_arith_Qe[index];

    /* Figure F.2 */
    as->A -= pqe->Qe;
    if ((as->C >> 16) < as->A) {
        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;
            }
            if (jbig2_arith_renormd(ctx, as) < 0) {
                return jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to renormalize decoder");
            }

            return D;
        } else {
            return cx >> 7;
        }
    } else {
        as->C -= (as->A) << 16;
        /* 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;
        }
        if (jbig2_arith_renormd(ctx, as) < 0) {
            return jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to renormalize decoder");
        }

        return D;
    }
}

#ifdef TEST

static const byte test_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 defined(JBIG2_DEBUG) || defined(JBIG2_DEBUG_ARITH)
static void
jbig2_arith_trace(Jbig2ArithState *as, Jbig2ArithCx cx)
{
    fprintf(stderr, "I = %2d, MPS = %d, A = %04x, CT = %2d, C = %08x\n", cx & 0x7f, cx >> 7, as->A, as->CT, as->C);
}
#endif

static int
test_get_word(Jbig2Ctx *ctx, Jbig2WordStream *self, size_t offset, uint32_t *word)
{
    uint32_t val = 0;
    int ret = 0;

    if (self == NULL || word == NULL)
        return -1;
    if (offset >= sizeof (test_stream))
        return 0;

    if (offset < sizeof(test_stream)) {
        val |= test_stream[offset] << 24;
        ret++;
    }
    if (offset + 1 < sizeof(test_stream)) {
        val |= test_stream[offset + 1] << 16;
        ret++;
    }
    if (offset + 2 < sizeof(test_stream)) {
        val |= test_stream[offset + 2] << 8;
        ret++;
    }
    if (offset + 3 < sizeof(test_stream)) {
        val |= test_stream[offset + 3];
        ret++;
    }
    *word = val;
    return ret;
}

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

    ctx = jbig2_ctx_new(NULL, 0, NULL, NULL, NULL);

    ws.get_next_word = test_get_word;
    as = jbig2_arith_new(ctx, &ws);
#ifdef JBIG2_DEBUG_ARITH
    jbig2_arith_trace(as, cx);
#endif

    for (i = 0; i < 256; i++) {
#ifdef JBIG2_DEBUG_ARITH
        int D =
#else
        (void)
#endif
            jbig2_arith_decode(ctx, as, &cx);

#ifdef JBIG2_DEBUG_ARITH
        fprintf(stderr, "%3d: D = %d, ", i, D);
        jbig2_arith_trace(as, cx);
#endif
    }

    jbig2_free(ctx->allocator, as);

    jbig2_ctx_free(ctx);

    return 0;
}
#endif

Coverage Report

Created: 2025-12-31 07:31

Line	Count	Source
1		/* Copyright (C) 2001-2023 Artifex Software, Inc.
2		All Rights Reserved.
3
4		This software is provided AS-IS with no warranty, either express or
5		implied.
6
7		This software is distributed under license and may not be copied,
8		modified or distributed except as expressly authorized under the terms
9		of the license contained in the file LICENSE in this distribution.
10
11		Refer to licensing information at http://www.artifex.com or contact
12		Artifex Software, Inc., 39 Mesa Street, Suite 108A, San Francisco,
13		CA 94129, USA, for further information.
14		*/
15
16		/*
17		jbig2dec
18		*/
19
20		#ifdef HAVE_CONFIG_H
21		#include "config.h"
22		#endif
23		#include "os_types.h"
24
25		#include <stdio.h>
26		#include <stdlib.h>
27
28		#include "jbig2.h"
29		#include "jbig2_priv.h"
30		#include "jbig2_arith.h"
31
32		struct _Jbig2ArithState {
33		uint32_t C;
34		uint32_t A;
35
36		int CT;
37
38		uint32_t next_word;
39		size_t next_word_bytes;
40		int err;
41
42		Jbig2WordStream *ws;
43		size_t offset;
44		};
45
46		/*
47		Previous versions of this code had a #define to allow
48		us to choose between using the revised arithmetic decoding
49		specified in the 'Software Convention' section of the spec.
50		Back to back tests showed that the 'Software Convention'
51		version was indeed slightly faster. We therefore enable it
52		by default. We also strip the option out, because a) it
53		makes the code harder to read, and b) such things are an
54		invitation to bitrot.
55		*/
56
57		static int
58		jbig2_arith_bytein(Jbig2Ctx ctx, Jbig2ArithState as)
59	53.6M	{
60	53.6M	byte B;
61
62		/* Treat both errors and reading beyond end of stream as an error. */
63	53.6M	if (as->err != 0) {
64	0	jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read from underlying stream during arithmetic decoding");
65	0	return -1;
66	0	}
67	53.6M	if (as->next_word_bytes == 0) {
68	0	jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read beyond end of underlying stream during arithmetic decoding");
69	0	return -1;
70	0	}
71
72		/* At this point there is at least one byte in as->next_word. */
73
74		/* This code confused me no end when I first read it, so a quick note
75		* to save others (and future me's) from being similarly confused.
76		* 'next_word' does indeed contain 'next_word_bytes' of valid data
77		* (always starting at the most significant byte). The confusing
78		* thing is that the first byte has always already been read.
79		* i.e. it serves only as an indication that the last byte we read
80		* was FF or not.
81		*
82		* The jbig2 bytestream uses FF bytes, followed by a byte > 0x8F as
83		* marker bytes. These never occur in normal streams of arithmetic
84		* encoding, so meeting one terminates the stream (with an infinite
85		* series of 1 bits).
86		*
87		* If we meet an FF byte, we return it as normal. We just 'remember'
88		* that fact for the next byte we read.
89		*/
90
91		/* Figure F.3 */
92	53.6M	B = (byte)((as->next_word >> 24) & 0xFF);
93	53.6M	if (B == 0xFF) {
94	38.5M	byte B1;
95
96		/* next_word_bytes can only be == 1 here, but let's be defensive. */
97	38.5M	if (as->next_word_bytes <= 1) {
98	21.3k	int ret = as->ws->get_next_word(ctx, as->ws, as->offset, &as->next_word);
99	21.3k	if (ret < 0) {
100	0	as->err = 1;
101	0	return jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to check for marker code due to failure in underlying stream during arithmetic decoding");
102	0	}
103	21.3k	as->next_word_bytes = (size_t) ret;
104
105	21.3k	if (as->next_word_bytes == 0) {
106	61	jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read end of possible terminating marker code, assuming terminating marker code");
107	61	as->next_word = 0xFF900000;
108	61	as->next_word_bytes = 2;
109	61	as->C += 0xFF00;
110	61	as->CT = 8;
111	61	return 0;
112	61	}
113
114	21.2k	as->offset += as->next_word_bytes;
115
116	21.2k	B1 = (byte)((as->next_word >> 24) & 0xFF);
117	21.2k	if (B1 > 0x8F) {
118		#ifdef JBIG2_DEBUG_ARITH
119		fprintf(stderr, "read %02x (aa)\n", B);
120		#endif
121	114	as->CT = 8;
122	114	as->next_word = 0xFF000000 \| (as->next_word >> 8);
123	114	as->next_word_bytes = 2;
124	114	as->offset--;
125	21.1k	} else {
126		#ifdef JBIG2_DEBUG_ARITH
127		fprintf(stderr, "read %02x (a)\n", B);
128		#endif
129	21.1k	as->C += 0xFE00 - (B1 << 9);
130	21.1k	as->CT = 7;
131	21.1k	}
132	38.4M	} else {
133	38.4M	B1 = (byte)((as->next_word >> 16) & 0xFF);
134	38.4M	if (B1 > 0x8F) {
135		#ifdef JBIG2_DEBUG_ARITH
136		fprintf(stderr, "read %02x (ba)\n", B);
137		#endif
138	38.4M	as->CT = 8;
139	38.4M	} else {
140	59.4k	as->next_word_bytes--;
141	59.4k	as->next_word <<= 8;
142		#ifdef JBIG2_DEBUG_ARITH
143		fprintf(stderr, "read %02x (b)\n", B);
144		#endif
145
146	59.4k	as->C += 0xFE00 - (B1 << 9);
147	59.4k	as->CT = 7;
148	59.4k	}
149	38.4M	}
150	38.5M	} else {
151		#ifdef JBIG2_DEBUG_ARITH
152		fprintf(stderr, "read %02x\n", B);
153		#endif
154	15.1M	as->next_word <<= 8;
155	15.1M	as->next_word_bytes--;
156
157	15.1M	if (as->next_word_bytes == 0) {
158	3.78M	int ret = as->ws->get_next_word(ctx, as->ws, as->offset, &as->next_word);
159	3.78M	if (ret < 0) {
160	0	as->err = 1;
161	0	return jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read from underlying stream during arithmetic decoding");
162	0	}
163	3.78M	as->next_word_bytes = (size_t) ret;
164
165	3.78M	if (as->next_word_bytes == 0) {
166	256	jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to find terminating marker code before end of underlying stream, assuming terminating marker code");
167	256	as->next_word = 0xFF900000;
168	256	as->next_word_bytes = 2;
169	256	as->C += 0xFF00;
170	256	as->CT = 8;
171	256	return 0;
172	256	}
173
174	3.78M	as->offset += as->next_word_bytes;
175	3.78M	}
176
177	15.1M	B = (byte)((as->next_word >> 24) & 0xFF);
178	15.1M	as->C += 0xFF00 - (B << 8);
179	15.1M	as->CT = 8;
180	15.1M	}
181
182	53.6M	return 0;
183	53.6M	}
184
185		/** Allocate and initialize a new arithmetic coding state
186		* the returned pointer can simply be freed; this does
187		* not affect the associated Jbig2WordStream.
188		*/
189		Jbig2ArithState *
190		jbig2_arith_new(Jbig2Ctx ctx, Jbig2WordStream ws)
191	886	{
192	886	Jbig2ArithState *result;
193	886	int ret;
194
195	886	result = jbig2_new(ctx, Jbig2ArithState, 1);
196	886	if (result == NULL) {
197	0	jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to allocate arithmetic coding state");
198	0	return NULL;
199	0	}
200
201	886	result->err = 0;
202	886	result->ws = ws;
203	886	result->offset = 0;
204
205	886	ret = result->ws->get_next_word(ctx, result->ws, result->offset, &result->next_word);
206	886	if (ret < 0) {
207	0	jbig2_free(ctx->allocator, result);
208	0	jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to initialize underlying stream of arithmetic decoder");
209	0	return NULL;
210	0	}
211
212	886	result->next_word_bytes = (size_t) ret;
213	886	if (result->next_word_bytes == 0) {
214	0	jbig2_free(ctx->allocator, result);
215	0	jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read first byte from underlying stream when initializing arithmetic decoder");
216	0	return NULL;
217	0	}
218
219	886	result->offset += result->next_word_bytes;
220
221		/* Figure F.1 */
222	886	result->C = (~(result->next_word >> 8)) & 0xFF0000;
223
224		/* Figure E.20 (2) */
225	886	if (jbig2_arith_bytein(ctx, result) < 0) {
226	0	jbig2_free(ctx->allocator, result);
227	0	jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read second byte from underlying stream when initializing arithmetic decoder");
228	0	return NULL;
229	0	}
230
231		/* Figure E.20 (3) */
232	886	result->C <<= 7;
233	886	result->CT -= 7;
234	886	result->A = 0x8000;
235
236	886	return result;
237	886	}
238
239	5.82G	#define MAX_QE_ARRAY_SIZE 47
240
241		/* could put bit fields in to minimize memory usage */
242		typedef struct {
243		uint16_t Qe;
244		byte mps_xor; /* mps_xor = index ^ NMPS */
245		byte lps_xor; /* lps_xor = index ^ NLPS ^ (SWITCH << 7) */
246		} Jbig2ArithQe;
247
248		#define MPS(index, nmps) ((index) ^ (nmps))
249		#define LPS(index, nlps, swtch) ((index) ^ (nlps) ^ ((swtch) << 7))
250
251		static const Jbig2ArithQe jbig2_arith_Qe[MAX_QE_ARRAY_SIZE] = {
252		{0x5601, MPS(0, 1), LPS(0, 1, 1)},
253		{0x3401, MPS(1, 2), LPS(1, 6, 0)},
254		{0x1801, MPS(2, 3), LPS(2, 9, 0)},
255		{0x0AC1, MPS(3, 4), LPS(3, 12, 0)},
256		{0x0521, MPS(4, 5), LPS(4, 29, 0)},
257		{0x0221, MPS(5, 38), LPS(5, 33, 0)},
258		{0x5601, MPS(6, 7), LPS(6, 6, 1)},
259		{0x5401, MPS(7, 8), LPS(7, 14, 0)},
260		{0x4801, MPS(8, 9), LPS(8, 14, 0)},
261		{0x3801, MPS(9, 10), LPS(9, 14, 0)},
262		{0x3001, MPS(10, 11), LPS(10, 17, 0)},
263		{0x2401, MPS(11, 12), LPS(11, 18, 0)},
264		{0x1C01, MPS(12, 13), LPS(12, 20, 0)},
265		{0x1601, MPS(13, 29), LPS(13, 21, 0)},
266		{0x5601, MPS(14, 15), LPS(14, 14, 1)},
267		{0x5401, MPS(15, 16), LPS(15, 14, 0)},
268		{0x5101, MPS(16, 17), LPS(16, 15, 0)},
269		{0x4801, MPS(17, 18), LPS(17, 16, 0)},
270		{0x3801, MPS(18, 19), LPS(18, 17, 0)},
271		{0x3401, MPS(19, 20), LPS(19, 18, 0)},
272		{0x3001, MPS(20, 21), LPS(20, 19, 0)},
273		{0x2801, MPS(21, 22), LPS(21, 19, 0)},
274		{0x2401, MPS(22, 23), LPS(22, 20, 0)},
275		{0x2201, MPS(23, 24), LPS(23, 21, 0)},
276		{0x1C01, MPS(24, 25), LPS(24, 22, 0)},
277		{0x1801, MPS(25, 26), LPS(25, 23, 0)},
278		{0x1601, MPS(26, 27), LPS(26, 24, 0)},
279		{0x1401, MPS(27, 28), LPS(27, 25, 0)},
280		{0x1201, MPS(28, 29), LPS(28, 26, 0)},
281		{0x1101, MPS(29, 30), LPS(29, 27, 0)},
282		{0x0AC1, MPS(30, 31), LPS(30, 28, 0)},
283		{0x09C1, MPS(31, 32), LPS(31, 29, 0)},
284		{0x08A1, MPS(32, 33), LPS(32, 30, 0)},
285		{0x0521, MPS(33, 34), LPS(33, 31, 0)},
286		{0x0441, MPS(34, 35), LPS(34, 32, 0)},
287		{0x02A1, MPS(35, 36), LPS(35, 33, 0)},
288		{0x0221, MPS(36, 37), LPS(36, 34, 0)},
289		{0x0141, MPS(37, 38), LPS(37, 35, 0)},
290		{0x0111, MPS(38, 39), LPS(38, 36, 0)},
291		{0x0085, MPS(39, 40), LPS(39, 37, 0)},
292		{0x0049, MPS(40, 41), LPS(40, 38, 0)},
293		{0x0025, MPS(41, 42), LPS(41, 39, 0)},
294		{0x0015, MPS(42, 43), LPS(42, 40, 0)},
295		{0x0009, MPS(43, 44), LPS(43, 41, 0)},
296		{0x0005, MPS(44, 45), LPS(44, 42, 0)},
297		{0x0001, MPS(45, 45), LPS(45, 43, 0)},
298		{0x5601, MPS(46, 46), LPS(46, 46, 0)}
299		};
300
301		static int
302		jbig2_arith_renormd(Jbig2Ctx ctx, Jbig2ArithState as)
303	350M	{
304		/* Figure E.18 */
305	429M	do {
306	429M	if (as->CT == 0 && jbig2_arith_bytein(ctx, as) < 0) {
307	0	return jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read byte from compressed data stream");
308	0	}
309	429M	as->A <<= 1;
310	429M	as->C <<= 1;
311	429M	as->CT--;
312	429M	} while ((as->A & 0x8000) == 0);
313
314	350M	return 0;
315	350M	}
316
317		int
318		jbig2_arith_decode(Jbig2Ctx ctx, Jbig2ArithState as, Jbig2ArithCx *pcx)
319	5.82G	{
320	5.82G	Jbig2ArithCx cx = *pcx;
321	5.82G	const Jbig2ArithQe *pqe;
322	5.82G	unsigned int index = cx & 0x7f;
323	5.82G	bool D;
324
325	5.82G	if (index >= MAX_QE_ARRAY_SIZE) {
326	0	return jbig2_error(ctx, JBIG2_SEVERITY_FATAL, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to determine probability estimate because index out of range");
327	0	}
328
329	5.82G	pqe = &jbig2_arith_Qe[index];
330
331		/* Figure F.2 */
332	5.82G	as->A -= pqe->Qe;
333	5.82G	if ((as->C >> 16) < as->A) {
334	5.76G	if ((as->A & 0x8000) == 0) {
335		/* MPS_EXCHANGE, Figure E.16 */
336	292M	if (as->A < pqe->Qe) {
337	55.2M	D = 1 - (cx >> 7);
338	55.2M	*pcx ^= pqe->lps_xor;
339	237M	} else {
340	237M	D = cx >> 7;
341	237M	*pcx ^= pqe->mps_xor;
342	237M	}
343	292M	if (jbig2_arith_renormd(ctx, as) < 0) {
344	0	return jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to renormalize decoder");
345	0	}
346
347	292M	return D;
348	5.47G	} else {
349	5.47G	return cx >> 7;
350	5.47G	}
351	5.76G	} else {
352	58.6M	as->C -= (as->A) << 16;
353		/* LPS_EXCHANGE, Figure E.17 */
354	58.6M	if (as->A < pqe->Qe) {
355	10.0M	as->A = pqe->Qe;
356	10.0M	D = cx >> 7;
357	10.0M	*pcx ^= pqe->mps_xor;
358	48.5M	} else {
359	48.5M	as->A = pqe->Qe;
360	48.5M	D = 1 - (cx >> 7);
361	48.5M	*pcx ^= pqe->lps_xor;
362	48.5M	}
363	58.6M	if (jbig2_arith_renormd(ctx, as) < 0) {
364	0	return jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to renormalize decoder");
365	0	}
366
367	58.6M	return D;
368	58.6M	}
369	5.82G	}
370
371		#ifdef TEST
372
373		static const byte test_stream[] = {
374		0x84, 0xC7, 0x3B, 0xFC, 0xE1, 0xA1, 0x43, 0x04, 0x02, 0x20, 0x00, 0x00,
375		0x41, 0x0D, 0xBB, 0x86, 0xF4, 0x31, 0x7F, 0xFF, 0x88, 0xFF, 0x37, 0x47,
376		0x1A, 0xDB, 0x6A, 0xDF, 0xFF, 0xAC,
377		0x00, 0x00
378		};
379
380		#if defined(JBIG2_DEBUG) \|\| defined(JBIG2_DEBUG_ARITH)
381		static void
382		jbig2_arith_trace(Jbig2ArithState *as, Jbig2ArithCx cx)
383		{
384		fprintf(stderr, "I = %2d, MPS = %d, A = %04x, CT = %2d, C = %08x\n", cx & 0x7f, cx >> 7, as->A, as->CT, as->C);
385		}
386		#endif
387
388		static int
389		test_get_word(Jbig2Ctx ctx, Jbig2WordStream self, size_t offset, uint32_t *word)
390		{
391		uint32_t val = 0;
392		int ret = 0;
393
394		if (self == NULL \|\| word == NULL)
395		return -1;
396		if (offset >= sizeof (test_stream))
397		return 0;
398
399		if (offset < sizeof(test_stream)) {
400		val \|= test_stream[offset] << 24;
401		ret++;
402		}
403		if (offset + 1 < sizeof(test_stream)) {
404		val \|= test_stream[offset + 1] << 16;
405		ret++;
406		}
407		if (offset + 2 < sizeof(test_stream)) {
408		val \|= test_stream[offset + 2] << 8;
409		ret++;
410		}
411		if (offset + 3 < sizeof(test_stream)) {
412		val \|= test_stream[offset + 3];
413		ret++;
414		}
415		*word = val;
416		return ret;
417		}
418
419		int
420		main(int argc, char **argv)
421		{
422		Jbig2Ctx *ctx;
423		Jbig2WordStream ws;
424		Jbig2ArithState *as;
425		int i;
426		Jbig2ArithCx cx = 0;
427
428		ctx = jbig2_ctx_new(NULL, 0, NULL, NULL, NULL);
429
430		ws.get_next_word = test_get_word;
431		as = jbig2_arith_new(ctx, &ws);
432		#ifdef JBIG2_DEBUG_ARITH
433		jbig2_arith_trace(as, cx);
434		#endif
435
436		for (i = 0; i < 256; i++) {
437		#ifdef JBIG2_DEBUG_ARITH
438		int D =
439		#else
440		(void)
441		#endif
442		jbig2_arith_decode(ctx, as, &cx);
443
444		#ifdef JBIG2_DEBUG_ARITH
445		fprintf(stderr, "%3d: D = %d, ", i, D);
446		jbig2_arith_trace(as, cx);
447		#endif
448		}
449
450		jbig2_free(ctx->allocator, as);
451
452		jbig2_ctx_free(ctx);
453
454		return 0;
455		}
456		#endif