ref: b536be35e4f10d15b973800351e9e5e1dc17e79d
author: giles <giles@ded80894-8fb9-0310-811b-c03f3676ab4d>
date: Wed May 30 16:58:04 EDT 2001
Initial revision git-svn-id: http://svn.ghostscript.com/jbig2dec/trunk@12 ded80894-8fb9-0310-811b-c03f3676ab4d
--- /dev/null
+++ b/jbig2.c
@@ -1,0 +1,242 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "jbig2.h"
+
+typedef struct _Jbig2SegmentHeader Jbig2SegmentHeader;
+typedef struct _Jbig2SymbolDictionary Jbig2SymbolDictionary;
+
+struct _Jbig2Ctx {+ FILE *f;
+ int offset;
+
+ byte flags;
+ int32 n_pages;
+};
+
+struct _Jbig2SegmentHeader {+ int32 segment_number;
+ byte flags;
+ int referred_to_segment_count;
+ int32 page_association;
+ int data_length;
+};
+
+struct _Jbig2SymbolDictionary {+ int16 flags;
+ int8 SDAT_flags[8];
+ byte SDRAT_flags[4];
+ int32 SDNUMEXSYMS;
+ int32 SDNUMNEWSYMS;
+};
+
+int32
+get_bytes (Jbig2Ctx *ctx, byte *buf, int size, int off)
+{+ fseek (ctx->f, off, SEEK_SET);
+ return fread (buf, 1, size, ctx->f);
+}
+
+int16
+get_int16 (Jbig2Ctx *ctx, int off)
+{+ byte buf[2];
+
+ get_bytes (ctx, buf, 2, off);
+ return (buf[0] << 8) | buf[1];
+}
+
+int32
+get_int32 (Jbig2Ctx *ctx, int off)
+{+ byte buf[4];
+
+ get_bytes (ctx, buf, 4, off);
+ return (buf[0] << 24) | (buf[1] << 16) | (buf[2] << 8) | buf[3];
+}
+
+static Jbig2Ctx *
+jbig2_open (FILE *f)
+{+ byte buf[9];
+ const byte header[8] = { 0x97, 0x4a, 0x42, 0x32, 0x0d, 0x0a, 0x1a, 0x0a };+ Jbig2Ctx *ctx;
+
+ /* Annex D.4 */
+ ctx = (Jbig2Ctx *)malloc (sizeof(Jbig2Ctx));
+ ctx->f = f;
+ get_bytes (ctx, buf, 9, 0);
+ if (memcmp (buf, header, 8))
+ {+ printf ("not a JBIG2 file\n");+ return NULL;
+ }
+ ctx->flags = buf[8];
+ if (ctx->flags & 2)
+ {+ ctx->offset = 9;
+ }
+ else
+ {+ ctx->offset = 13;
+ ctx->n_pages = get_int32 (ctx, 9);
+ }
+ return ctx;
+}
+
+static Jbig2SegmentHeader *
+jbig2_read_segment_header (Jbig2Ctx *ctx)
+{+ Jbig2SegmentHeader *result = (Jbig2SegmentHeader *)malloc(sizeof(Jbig2SegmentHeader));
+ int32 offset = ctx->offset;
+ byte rtscarf;
+ int referred_to_segment_count;
+ byte spa;
+
+ /* 7.2.2 */
+ result->segment_number = get_int32 (ctx, offset);
+
+ /* 7.2.3 */
+ get_bytes (ctx, &result->flags, 1, offset + 4);
+
+ /* 7.2.4 */
+ get_bytes (ctx, &rtscarf, 1, offset + 5);
+ if ((rtscarf & 0xe0) == 0xe0)
+ {+ printf ("long form of rtscarf, can't handle!\n");+ }
+ else
+ {+ referred_to_segment_count = (rtscarf >> 5);
+ offset += 6 + referred_to_segment_count;
+ }
+ result->referred_to_segment_count = referred_to_segment_count;
+ /* todo: read referred to segment numbers */
+
+ /* 7.2.6 */
+ get_bytes (ctx, &spa, 1, offset);
+ if (result->flags & 64)
+ {+ printf ("long form of spa, can't handle!\n");+ }
+ result->page_association = spa;
+
+ /* 7.2.7 */
+ result->data_length = get_int32 (ctx, offset + 1);
+ ctx->offset = offset + 5;
+
+ return result;
+}
+
+static Jbig2SymbolDictionary *
+jbig2_read_symbol_dictionary (Jbig2Ctx *ctx)
+{+ Jbig2SymbolDictionary *result = (Jbig2SymbolDictionary *)malloc(sizeof(Jbig2SymbolDictionary));
+ int32 offset = ctx->offset;
+ bool SDHUFF, SDREFAGG, SDRTEMPLATE;
+ int sdat_bytes;
+
+ /* 7.4.2.1.1 */
+ result->flags = get_int16 (ctx, offset);
+ offset += 2;
+
+ SDHUFF = result->flags & 1;
+ SDREFAGG = (result->flags >> 1) & 1;
+ SDRTEMPLATE = (result->flags >> 12) & 1;
+
+ /* 7.4.2.1.2 */
+ if (!SDHUFF)
+ {+ int SDTEMPLATE = (result->flags >> 10) & 3;
+ if (SDTEMPLATE == 0)
+ sdat_bytes = 8;
+ else
+ sdat_bytes = 2;
+ }
+ else
+ sdat_bytes = 0;
+ get_bytes (ctx, result->SDAT_flags, sdat_bytes, offset);
+ memset (&result->SDAT_flags + sdat_bytes, 0, 8 - sdat_bytes);
+ offset += sdat_bytes;
+
+ /* 7.4.2.1.3 */
+ if (SDREFAGG && !SDRTEMPLATE)
+ {+ get_bytes (ctx, result->SDRAT_flags, 4, offset);
+ offset += 4;
+ }
+
+ /* 7.4.2.1.4 */
+ result->SDNUMEXSYMS = get_int32 (ctx, offset);
+
+ /* 7.4.2.1.5 */
+ result->SDNUMNEWSYMS = get_int32 (ctx, offset + 4);
+ offset += 8;
+
+ return result;
+}
+
+static void
+dump_symbol_dictionary (Jbig2SymbolDictionary *sd)
+{+ printf ("segment type = symbol dictionary, flags = %04x, numexsyms = %d, numnewsyms = %d\n",+ sd->flags, sd->SDNUMEXSYMS, sd->SDNUMNEWSYMS);
+}
+
+static bool
+dump_segment (Jbig2Ctx *ctx)
+{+ Jbig2SegmentHeader *sh;
+ int32 offset;
+ Jbig2SymbolDictionary *sd;
+
+ sh = jbig2_read_segment_header (ctx);
+ offset = ctx->offset;
+ printf ("segment number = %d, flags = %02x, page %d, %d bytes\n",+ sh->segment_number, sh->flags, sh->page_association, sh->data_length);
+ switch (sh->flags & 63)
+ {+ case 0:
+ sd = jbig2_read_symbol_dictionary (ctx);
+ dump_symbol_dictionary (sd);
+ break;
+ case 51:
+ printf ("segment type = end of file\n");+ return TRUE;
+ }
+ ctx->offset = offset + sh->data_length;
+ return FALSE;
+}
+
+static void
+dump_jbig2 (FILE *f)
+{+ Jbig2Ctx *ctx;
+ bool last;
+
+ ctx = jbig2_open (f);
+ printf ("Number of pages = %d\n", ctx->n_pages);+ for (;;)
+ {+ last = dump_segment (ctx);
+ if (last)
+ break;
+ }
+}
+
+int
+main (int argc, char **argv)
+{+ FILE *f;
+
+ if (argc < 2)
+ return -1;
+ f = fopen (argv[1], "rb");
+ if (f == NULL)
+ return -1;
+
+ dump_jbig2 (f);
+ fclose (f);
+ return 0;
+}
--- /dev/null
+++ b/jbig2.h
@@ -1,0 +1,31 @@
+typedef unsigned char byte;
+typedef int bool;
+typedef unsigned int uint32;
+typedef int int32;
+typedef short int16;
+typedef signed char int8;
+
+#define TRUE 1
+#define FALSE 0
+
+typedef struct _Jbig2Ctx Jbig2Ctx;
+
+int32
+get_bytes (Jbig2Ctx *ctx, byte *buf, int size, int off);
+
+int16
+get_int16 (Jbig2Ctx *ctx, int off);
+
+int32
+get_int32 (Jbig2Ctx *ctx, int off);
+
+/* The word stream design is a compromise between simplicity and
+ trying to amortize the number of method calls. Each ::get_next_word
+ invocation pulls 4 bytes from the stream, packed big-endian into a
+ 32 bit word. The offset argument is provided as a convenience. It
+ begins at 0 and increments by 4 for each successive invocation. */
+typedef struct _Jbig2WordStream Jbig2WordStream;
+
+struct _Jbig2WordStream {+ int32 (*get_next_word) (Jbig2WordStream *self, int offset);
+};
--- /dev/null
+++ b/jbig2_arith.c
@@ -1,0 +1,327 @@
+#include <stdlib.h>
+
+#include "jbig2.h"
+#include "jbig2_arith.h"
+
+struct _Jbig2ArithState {+ uint32 C;
+ int A;
+ int I_CX;
+ int MPS_CX;
+
+ int CT;
+
+ uint32 next_word;
+ int next_word_bytes;
+
+ Jbig2WordStream *ws;
+ int offset;
+};
+
+#define SOFTWARE_CONVENTION
+
+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 F.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)
+ {+ printf ("read %02x (aa)\n", B);+#ifndef SOFTWARE_CONVENTION
+ as->C += 0xFF00;
+#endif
+ as->CT = 8;
+ as->next_word = (0xFF00 | B1) << 16;
+ as->next_word_bytes = 2;
+ }
+ else
+ {+ printf ("read %02x (a)\n", B);+#ifdef SOFTWARE_CONVENTION
+ as->C += 0xFE00 - (B << 8);
+#else
+ as->C += 0xFF00;
+#endif
+ as->CT = 7;
+ as->next_word_bytes = 4;
+ }
+ }
+ else
+ {+ B1 = (as->next_word >> 16) & 0xFF;
+ if (B1 > 0x8F)
+ {+ printf ("read %02x (ba)\n", B);+#ifndef SOFTWARE_CONVENTION
+ as->C += 0xFF00;
+#endif
+ as->CT = 8;
+ }
+ else
+ {+ as->next_word_bytes--;
+ as->next_word <<= 8;
+ printf ("read %02x (b)\n", B);+#ifdef SOFTWARE_CONVENTION
+ as->C += 0xFE00 - (B << 8);
+#else
+ as->C += 0xFF00;
+#endif
+ as->CT = 7;
+ }
+ }
+ }
+ else
+ {+ printf ("read %02x\n", B);+#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)
+{+ printf ("I = %2d, A = %04x, CT = %2d, C = %08x\n",+ as->I_CX, as->A, as->CT, as->C);
+}
+#endif
+
+Jbig2ArithState *
+jbig2_arith_new (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 F.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;
+
+ /* note: these are merely defaults; it may be necessary to provide
+ additional arguments to initialize these to non-default values. */
+ result->I_CX = 0;
+ result->MPS_CX = 0;
+
+ return result;
+};
+
+/* could put bit fields in to minimize memory usage */
+typedef struct {+ int Qe;
+ int NMPS;
+ int NLPS;
+ bool SWITCH;
+} Jbig2ArithQe;
+
+const Jbig2ArithQe jbig2_arith_Qe[] = {+ { 0x5601, 1, 1, 1 },+ { 0x3401, 2, 6, 0 },+ { 0x1801, 3, 9, 0 },+ { 0x0AC1, 4, 12, 0 },+ { 0x0521, 5, 29, 0 },+ { 0x0221, 38, 33, 0 },+ { 0x5601, 7, 6, 1 },+ { 0x5401, 8, 14, 0 },+ { 0x4801, 9, 14, 0 },+ { 0x3801, 10, 14, 0 },+ { 0x3001, 11, 17, 0 },+ { 0x2401, 12, 18, 0 },+ { 0x1C01, 13, 20, 0 },+ { 0x1601, 29, 21, 0 },+ { 0x5601, 15, 14, 1 },+ { 0x5401, 16, 14, 0 },+ { 0x5101, 17, 15, 0 },+ { 0x4801, 18, 16, 0 },+ { 0x3801, 19, 17, 0 },+ { 0x3401, 20, 18, 0 },+ { 0x3001, 21, 19, 0 },+ { 0x2801, 22, 19, 0 },+ { 0x2401, 23, 20, 0 },+ { 0x2201, 24, 21, 0 },+ { 0x1C01, 25, 22, 0 },+ { 0x1801, 26, 23, 0 },+ { 0x1601, 27, 24, 0 },+ { 0x1401, 28, 25, 0 },+ { 0x1201, 29, 26, 0 },+ { 0x1101, 30, 27, 0 },+ { 0x0AC1, 31, 28, 0 },+ { 0x09C1, 32, 29, 0 },+ { 0x08A1, 33, 30, 0 },+ { 0x0521, 34, 31, 0 },+ { 0x0441, 35, 32, 0 },+ { 0x02A1, 36, 33, 0 },+ { 0x0221, 37, 34, 0 },+ { 0x0141, 38, 35, 0 },+ { 0x0111, 39, 36, 0 },+ { 0x0085, 40, 37, 0 },+ { 0x0049, 41, 38, 0 },+ { 0x0025, 42, 39, 0 },+ { 0x0015, 43, 40, 0 },+ { 0x0009, 44, 41, 0 },+ { 0x0005, 45, 42, 0 },+ { 0x0001, 45, 43, 0 },+ { 0x5601, 46, 46, 0 }+};
+
+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)
+{+ const Jbig2ArithQe *pqe = &jbig2_arith_Qe[as->I_CX];
+ bool D;
+
+ /* Figure F.2 */
+ as->A -= pqe->Qe;
+ if (
+#ifdef SOFTWARE_CONVENTION
+ (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 - as->MPS_CX;
+ as->MPS_CX ^= pqe->SWITCH;
+ as->I_CX = pqe->NLPS;
+ }
+ else
+ {+ D = as->MPS_CX;
+ as->I_CX = pqe->NMPS;
+ }
+ jbig2_arith_renormd (as);
+ return D;
+ }
+ else
+ return as->MPS_CX;
+ }
+ 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 = as->MPS_CX;
+ as->I_CX = pqe->NMPS;
+ }
+ else
+ {+ as->A = pqe->Qe;
+ D = 1 - as->MPS_CX;
+ as->MPS_CX ^= pqe->SWITCH;
+ as->I_CX = pqe->NLPS;
+ }
+ jbig2_arith_renormd (as);
+ return D;
+ }
+}
+
+#ifdef TEST
+
+static int32
+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;
+
+ ws.get_next_word = test_get_word;
+ as = jbig2_arith_new (&ws);
+ jbig2_arith_trace (as);
+
+ for (i = 0; i < 256; i++)
+ {+ bool D;
+
+ D = jbig2_arith_decode (as);
+ printf ("%3d: D = %d, ", i, D);+ jbig2_arith_trace (as);
+
+ }
+ return 0;
+}
+#endif
--- /dev/null
+++ b/jbig2_arith.h
@@ -1,0 +1,4 @@
+typedef struct _Jbig2ArithState Jbig2ArithState;
+
+Jbig2ArithState *
+jbig2_arith_new (Jbig2WordStream *ws);
--- /dev/null
+++ b/jbig2_huffman.c
@@ -1,0 +1,371 @@
+/* Huffman table decoding procedures */
+
+#include <stdlib.h>
+
+#include "jbig2.h"
+#include "jbig2_huffman.h"
+
+#define JBIG2_HUFFMAN_FLAGS_ISOOB 1
+#define JBIG2_HUFFMAN_FLAGS_ISLOW 2
+#define JBIG2_HUFFMAN_FLAGS_ISEXT 4
+
+typedef struct _Jbig2HuffmanEntry Jbig2HuffmanEntry;
+
+struct _Jbig2HuffmanEntry {+ union {+ int32 RANGELOW;
+ Jbig2HuffmanTable *ext_table;
+ } u;
+ byte PREFLEN;
+ byte RANGELEN;
+ byte flags;
+};
+
+struct _Jbig2HuffmanTable {+ int log_table_size;
+ Jbig2HuffmanEntry *entries;
+};
+
+struct _Jbig2HuffmanState {+ /* The current bit offset is equal to (offset * 8) + offset_bits.
+ The MSB of this_word is the current bit offset. The MSB of next_word
+ is (offset + 4) * 8. */
+ uint32 this_word;
+ uint32 next_word;
+ int offset_bits;
+ int offset;
+
+ Jbig2WordStream *ws;
+};
+
+
+Jbig2HuffmanState *
+jbig2_huffman_new (Jbig2WordStream *ws)
+{+ Jbig2HuffmanState *result = (Jbig2HuffmanState *)malloc (sizeof(Jbig2HuffmanState));
+
+ result->offset = 0;
+ result->offset_bits = 0;
+ result->this_word = ws->get_next_word (ws, 0);
+ result->next_word = ws->get_next_word (ws, 4);
+
+ result->ws = ws;
+
+ return result;
+}
+
+int32
+jbig2_huffman_get (Jbig2HuffmanState *hs,
+ const Jbig2HuffmanTable *table, bool *oob)
+{+ Jbig2HuffmanEntry *entry;
+ byte flags;
+ int offset_bits = hs->offset_bits;
+ uint32 this_word = hs->this_word;
+ uint32 next_word;
+ int RANGELEN;
+ int32 result;
+
+ for (;;)
+ { + int log_table_size = table->log_table_size;
+ int PREFLEN;
+
+ entry = &table->entries[this_word >> (32 - log_table_size)];
+ flags = entry->flags;
+ PREFLEN = entry->PREFLEN;
+
+ next_word = hs->next_word;
+ offset_bits += PREFLEN;
+ if (offset_bits >= 32)
+ {+ Jbig2WordStream *ws = hs->ws;
+ this_word = next_word;
+ hs->offset += 4;
+ next_word = ws->get_next_word (ws, hs->offset + 4);
+ offset_bits -= 32;
+ hs->next_word = next_word;
+ PREFLEN = offset_bits;
+ }
+ this_word = (this_word << PREFLEN) |
+ (next_word >> (32 - offset_bits));
+ if (flags & JBIG2_HUFFMAN_FLAGS_ISEXT)
+ {+ table = entry->u.ext_table;
+ }
+ else
+ break;
+ }
+ result = entry->u.RANGELOW;
+ RANGELEN = entry->RANGELEN;
+ if (RANGELEN > 0)
+ {+ int32 HTOFFSET;
+
+ HTOFFSET = this_word >> (32 - RANGELEN);
+ if (flags & JBIG2_HUFFMAN_FLAGS_ISLOW)
+ result -= HTOFFSET;
+ else
+ result += HTOFFSET;
+
+ offset_bits += RANGELEN;
+ if (offset_bits >= 32)
+ {+ Jbig2WordStream *ws = hs->ws;
+ this_word = next_word;
+ hs->offset += 4;
+ next_word = ws->get_next_word (ws, hs->offset + 4);
+ offset_bits -= 32;
+ hs->next_word = next_word;
+ RANGELEN = offset_bits;
+ }
+ this_word = (this_word << RANGELEN) |
+ (next_word >> (32 - offset_bits));
+ }
+
+ hs->this_word = this_word;
+ hs->offset_bits = offset_bits;
+
+ if (oob != NULL)
+ *oob = (flags & JBIG2_HUFFMAN_FLAGS_ISOOB);
+
+ return result;
+}
+
+typedef struct _Jbig2HuffmanLine Jbig2HuffmanLine;
+
+struct _Jbig2HuffmanLine {+ int PREFLEN;
+ int RANGELEN;
+ int RANGELOW;
+};
+
+struct _Jbig2HuffmanParams {+ bool HTOOB;
+ int n_lines;
+ const Jbig2HuffmanLine *lines;
+};
+
+/* Table B.1 */
+const Jbig2HuffmanLine
+jbig_huffman_lines_A[] = {+ { 1, 4, 0 },+ { 2, 8, 16 },+ { 3, 16, 272 },+ { 0, 32, -1 }, /* low */+ { 3, 32, 65808 } /* high */+};
+
+const Jbig2HuffmanParams
+jbig_huffman_params_A = { FALSE, 5, jbig_huffman_lines_A };+
+/* Table B.2 */
+const Jbig2HuffmanLine
+jbig_huffman_lines_B[] = {+ { 1, 0, 0 },+ { 2, 0, 1 },+ { 3, 0, 2 },+ { 4, 3, 3 },+ { 5, 6, 11 },+ { 0, 32, -1 }, /* low */+ { 6, 32, 75 }, /* high */+ { 6, 0, 0 }+};
+
+const Jbig2HuffmanParams
+jbig_huffman_params_B = { TRUE, 8, jbig_huffman_lines_B };+
+/* Table B.3 */
+const Jbig2HuffmanLine
+jbig_huffman_lines_C[] = {+ { 8, 8, -256 },+ { 1, 0, 0 },+ { 2, 0, 1 },+ { 3, 0, 2 },+ { 4, 3, 3 },+ { 5, 6, 11 },+ { 8, 32, -257 }, /* low */+ { 7, 32, 75 }, /* high */+ { 6, 0, 0 } /* OOB */+};
+
+const Jbig2HuffmanParams
+jbig_huffman_params_C = { TRUE, 9, jbig_huffman_lines_C };+
+/* Table B.4 */
+const Jbig2HuffmanLine
+jbig_huffman_lines_D[] = {+ { 1, 0, 1 },+ { 2, 0, 2 },+ { 3, 0, 3 },+ { 4, 3, 4 },+ { 5, 6, 12 },+ { 0, 32, -1 }, /* low */+ { 5, 32, 76 }, /* high */+};
+
+const Jbig2HuffmanParams
+jbig_huffman_params_D = { FALSE, 7, jbig_huffman_lines_D };+
+/* Table B.14 */
+const Jbig2HuffmanLine
+jbig_huffman_lines_N[] = {+ { 3, 0, -2 },+ { 3, 0, -1 },+ { 1, 0, 0 },+ { 3, 3, 1 },+ { 3, 6, 2 },+ { 0, 32, -1 }, /* low */+ { 0, 32, 3 }, /* high */+};
+
+const Jbig2HuffmanParams
+jbig_huffman_params_N = { FALSE, 7, jbig_huffman_lines_N };+
+#define LOG_TABLE_SIZE_MAX 8
+
+Jbig2HuffmanTable *
+jbig2_build_huffman_table (const Jbig2HuffmanParams *params)
+{+ int LENCOUNT[256];
+ int LENMAX = -1;
+ const Jbig2HuffmanLine *lines = params->lines;
+ int n_lines = params->n_lines;
+ int i, j;
+ int log_table_size = 0;
+ Jbig2HuffmanTable *result;
+ Jbig2HuffmanEntry *entries;
+ int CURLEN;
+ int firstcode = 0;
+ int CURCODE;
+ int CURTEMP;
+
+ /* B.3, 1. */
+ for (i = 0; i < params->n_lines; i++)
+ {+ int PREFLEN = lines[i].PREFLEN;
+ int lts;
+
+ if (PREFLEN > LENMAX)
+ {+ for (j = LENMAX + 1; j < PREFLEN + 1; j++)
+ LENCOUNT[j] = 0;
+ LENMAX = PREFLEN;
+ }
+ LENCOUNT[PREFLEN]++;
+
+ lts = PREFLEN + lines[i].RANGELEN;
+ if (lts > LOG_TABLE_SIZE_MAX)
+ lts = PREFLEN;
+ if (lts <= LOG_TABLE_SIZE_MAX && log_table_size < lts)
+ log_table_size = lts;
+ }
+ result = (Jbig2HuffmanTable *)malloc (sizeof(Jbig2HuffmanTable));
+ result->log_table_size = log_table_size;
+ entries = (Jbig2HuffmanEntry *)malloc (sizeof(Jbig2HuffmanEntry) << log_table_size);
+ result->entries = entries;
+
+ LENCOUNT[0] = 0;
+
+ for (CURLEN = 1; CURLEN <= LENMAX; CURLEN++)
+ {+ int shift = log_table_size - CURLEN;
+
+ /* B.3 3.(a) */
+ firstcode = (firstcode + LENCOUNT[CURLEN - 1]) << 1;
+ CURCODE = firstcode;
+ /* B.3 3.(b) */
+ for (CURTEMP = 0; CURTEMP < n_lines; CURTEMP++)
+ {+ int PREFLEN = lines[CURTEMP].PREFLEN;
+ if (PREFLEN == CURLEN)
+ {+ int RANGELEN = lines[CURTEMP].RANGELEN;
+ int start_j = CURCODE << shift;
+ int end_j = (CURCODE + 1) << shift;
+ byte eflags = 0;
+
+ /* todo: build extension tables */
+ if (params->HTOOB && CURTEMP == n_lines - 1)
+ eflags |= JBIG2_HUFFMAN_FLAGS_ISOOB;
+ if (CURTEMP == n_lines - (params->HTOOB ? 3 : 2))
+ eflags |= JBIG2_HUFFMAN_FLAGS_ISLOW;
+ if (PREFLEN + RANGELEN > LOG_TABLE_SIZE_MAX)
+ {+ for (j = start_j; j < end_j; j++)
+ {+ entries[j].u.RANGELOW = lines[CURTEMP].RANGELOW;
+ entries[j].PREFLEN = PREFLEN;
+ entries[j].RANGELEN = RANGELEN;
+ entries[j].flags = eflags;
+ }
+ }
+ else
+ {+ for (j = start_j; j < end_j; j++)
+ {+ int32 HTOFFSET = (j >> (shift - RANGELEN)) &
+ ((1 << RANGELEN) - 1);
+ if (eflags & JBIG2_HUFFMAN_FLAGS_ISLOW)
+ entries[j].u.RANGELOW = lines[CURTEMP].RANGELOW -
+ HTOFFSET;
+ else
+ entries[j].u.RANGELOW = lines[CURTEMP].RANGELOW +
+ HTOFFSET;
+ entries[j].PREFLEN = PREFLEN + RANGELEN;
+ entries[j].RANGELEN = 0;
+ entries[j].flags = eflags;
+ }
+ }
+ CURCODE++;
+ }
+ }
+ }
+
+ return result;
+}
+
+#ifdef TEST
+#include <stdio.h>
+
+static int32
+test_get_word (Jbig2WordStream *self, int offset)
+{+ if (offset == 0)
+ return 0xe9cbf400;
+ else
+ return 0;
+}
+
+int
+main (int argc, char **argv)
+{+ Jbig2HuffmanTable *b1;
+ Jbig2HuffmanTable *b2;
+ Jbig2HuffmanTable *b4;
+ Jbig2HuffmanState *hs;
+ Jbig2WordStream ws;
+ bool oob;
+ int32 code;
+
+ b1 = jbig2_build_huffman_table (&jbig_huffman_params_A);
+ b2 = jbig2_build_huffman_table (&jbig_huffman_params_B);
+ b4 = jbig2_build_huffman_table (&jbig_huffman_params_D);
+ ws.get_next_word = test_get_word;
+ hs = jbig2_huffman_new (&ws);
+
+ code = jbig2_huffman_get (hs, b4, &oob);
+ printf ("%d %s\n", code, oob ? "OOB" : "");+
+ code = jbig2_huffman_get (hs, b2, &oob);
+ printf ("%d %s\n", code, oob ? "OOB" : "");+
+ code = jbig2_huffman_get (hs, b2, &oob);
+ printf ("%d %s\n", code, oob ? "OOB" : "");+
+ code = jbig2_huffman_get (hs, b1, &oob);
+ printf ("%d %s\n", code, oob ? "OOB" : "");+
+ return 0;
+}
+#endif
--- /dev/null
+++ b/jbig2_huffman.h
@@ -1,0 +1,13 @@
+typedef struct _Jbig2HuffmanState Jbig2HuffmanState;
+typedef struct _Jbig2HuffmanTable Jbig2HuffmanTable;
+typedef struct _Jbig2HuffmanParams Jbig2HuffmanParams;
+
+Jbig2HuffmanState *
+jbig2_huffman_new (Jbig2WordStream *ws);
+
+int32
+jbig2_huffman_get (Jbig2HuffmanState *hs,
+ const Jbig2HuffmanTable *table, bool *oob);
+
+Jbig2HuffmanTable *
+jbig2_build_huffman_table (const Jbig2HuffmanParams *params);
--- /dev/null
+++ b/makefile
@@ -1,0 +1,12 @@
+CFLAGS=-Wall -g
+
+all: jbig2
+
+jbig2: jbig2.o jbig2_huffman.o jbig2_arith.o
+
+test_huffman: jbig2_huffman.c
+ gcc $(CFLAGS) -DTEST jbig2_huffman.c -o test_huffman
+
+test_arith: jbig2_arith.c
+ gcc $(CFLAGS) -DTEST -DDEBUG jbig2_arith.c -o test_arith
+