/src/ghostpdl/jbig2dec/jbig2_arith.c

Source (jump to first uncovered line)
/* 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-08-28 07:06

Line	Count	Source (jump to first uncovered line)
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	44.9M	{
60	44.9M	byte B;
61
62		/* Treat both errors and reading beyond end of stream as an error. */
63	44.9M	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	44.9M	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	44.9M	B = (byte)((as->next_word >> 24) & 0xFF);
93	44.9M	if (B == 0xFF) {
94	32.3M	byte B1;
95
96		/* next_word_bytes can only be == 1 here, but let's be defensive. */
97	32.3M	if (as->next_word_bytes <= 1) {
98	17.6k	int ret = as->ws->get_next_word(ctx, as->ws, as->offset, &as->next_word);
99	17.6k	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	17.6k	as->next_word_bytes = (size_t) ret;
104
105	17.6k	if (as->next_word_bytes == 0) {
106	20	jbig2_error(ctx, JBIG2_SEVERITY_WARNING, JBIG2_UNKNOWN_SEGMENT_NUMBER, "failed to read end of possible terminating marker code, assuming terminating marker code");
107	20	as->next_word = 0xFF900000;
108	20	as->next_word_bytes = 2;
109	20	as->C += 0xFF00;
110	20	as->CT = 8;
111	20	return 0;
112	20	}
113
114	17.6k	as->offset += as->next_word_bytes;
115
116	17.6k	B1 = (byte)((as->next_word >> 24) & 0xFF);
117	17.6k	if (B1 > 0x8F) {
118		#ifdef JBIG2_DEBUG_ARITH
119		fprintf(stderr, "read %02x (aa)\n", B);
120		#endif
121	96	as->CT = 8;
122	96	as->next_word = 0xFF000000 \| (as->next_word >> 8);
123	96	as->next_word_bytes = 2;
124	96	as->offset--;
125	17.5k	} else {
126		#ifdef JBIG2_DEBUG_ARITH
127		fprintf(stderr, "read %02x (a)\n", B);
128		#endif
129	17.5k	as->C += 0xFE00 - (B1 << 9);
130	17.5k	as->CT = 7;
131	17.5k	}
132	32.3M	} else {
133	32.3M	B1 = (byte)((as->next_word >> 16) & 0xFF);
134	32.3M	if (B1 > 0x8F) {
135		#ifdef JBIG2_DEBUG_ARITH
136		fprintf(stderr, "read %02x (ba)\n", B);
137		#endif
138	32.2M	as->CT = 8;
139	32.2M	} else {
140	49.0k	as->next_word_bytes--;
141	49.0k	as->next_word <<= 8;
142		#ifdef JBIG2_DEBUG_ARITH
143		fprintf(stderr, "read %02x (b)\n", B);
144		#endif
145
146	49.0k	as->C += 0xFE00 - (B1 << 9);
147	49.0k	as->CT = 7;
148	49.0k	}
149	32.3M	}
150	32.3M	} else {
151		#ifdef JBIG2_DEBUG_ARITH
152		fprintf(stderr, "read %02x\n", B);
153		#endif
154	12.5M	as->next_word <<= 8;
155	12.5M	as->next_word_bytes--;
156
157	12.5M	if (as->next_word_bytes == 0) {
158	3.14M	int ret = as->ws->get_next_word(ctx, as->ws, as->offset, &as->next_word);
159	3.14M	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.14M	as->next_word_bytes = (size_t) ret;
164
165	3.14M	if (as->next_word_bytes == 0) {
166	204	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	204	as->next_word = 0xFF900000;
168	204	as->next_word_bytes = 2;
169	204	as->C += 0xFF00;
170	204	as->CT = 8;
171	204	return 0;
172	204	}
173
174	3.14M	as->offset += as->next_word_bytes;
175	3.14M	}
176
177	12.5M	B = (byte)((as->next_word >> 24) & 0xFF);
178	12.5M	as->C += 0xFF00 - (B << 8);
179	12.5M	as->CT = 8;
180	12.5M	}
181
182	44.9M	return 0;
183	44.9M	}
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	654	{
192	654	Jbig2ArithState *result;
193	654	int ret;
194
195	654	result = jbig2_new(ctx, Jbig2ArithState, 1);
196	654	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	654	result->err = 0;
202	654	result->ws = ws;
203	654	result->offset = 0;
204
205	654	ret = result->ws->get_next_word(ctx, result->ws, result->offset, &result->next_word);
206	654	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	654	result->next_word_bytes = (size_t) ret;
213	654	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	654	result->offset += result->next_word_bytes;
220
221		/* Figure F.1 */
222	654	result->C = (~(result->next_word >> 8)) & 0xFF0000;
223
224		/* Figure E.20 (2) */
225	654	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	654	result->C <<= 7;
233	654	result->CT -= 7;
234	654	result->A = 0x8000;
235
236	654	return result;
237	654	}
238
239	4.78G	#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	293M	{
304		/* Figure E.18 */
305	359M	do {
306	359M	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	359M	as->A <<= 1;
310	359M	as->C <<= 1;
311	359M	as->CT--;
312	359M	} while ((as->A & 0x8000) == 0);
313
314	293M	return 0;
315	293M	}
316
317		int
318		jbig2_arith_decode(Jbig2Ctx ctx, Jbig2ArithState as, Jbig2ArithCx *pcx)
319	4.78G	{
320	4.78G	Jbig2ArithCx cx = *pcx;
321	4.78G	const Jbig2ArithQe *pqe;
322	4.78G	unsigned int index = cx & 0x7f;
323	4.78G	bool D;
324
325	4.78G	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	4.78G	pqe = &jbig2_arith_Qe[index];
330
331		/* Figure F.2 */
332	4.78G	as->A -= pqe->Qe;
333	4.78G	if ((as->C >> 16) < as->A) {
334	4.73G	if ((as->A & 0x8000) == 0) {
335		/* MPS_EXCHANGE, Figure E.16 */
336	245M	if (as->A < pqe->Qe) {
337	46.7M	D = 1 - (cx >> 7);
338	46.7M	*pcx ^= pqe->lps_xor;
339	198M	} else {
340	198M	D = cx >> 7;
341	198M	*pcx ^= pqe->mps_xor;
342	198M	}
343	245M	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	245M	return D;
348	4.49G	} else {
349	4.49G	return cx >> 7;
350	4.49G	}
351	4.73G	} else {
352	48.8M	as->C -= (as->A) << 16;
353		/* LPS_EXCHANGE, Figure E.17 */
354	48.8M	if (as->A < pqe->Qe) {
355	8.39M	as->A = pqe->Qe;
356	8.39M	D = cx >> 7;
357	8.39M	*pcx ^= pqe->mps_xor;
358	40.4M	} else {
359	40.4M	as->A = pqe->Qe;
360	40.4M	D = 1 - (cx >> 7);
361	40.4M	*pcx ^= pqe->lps_xor;
362	40.4M	}
363	48.8M	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	48.8M	return D;
368	48.8M	}
369	4.78G	}
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