/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-06-10 07:27

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