ref: 8f2d8d661e4230e61e095e336f1b14c739b62ba0
dir: /jbig2_huffman.c/
/*
jbig2dec
Copyright (c) 2001 artofcode LLC.
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.
For information on commercial licensing, go to
http://www.artifex.com/licensing/ or contact
Artifex Software, Inc., 101 Lucas Valley Road #110,
San Rafael, CA 94903, U.S.A., +1(415)492-9861.
$Id: jbig2_huffman.c,v 1.11 2002/07/20 17:23:15 giles Exp $
*/
/* Huffman table decoding procedures
-- See Annex B of the JBIG2 draft spec */
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
#include "os_types.h"
#include <stdlib.h>
#include "jbig2.h"
#include "jbig2_priv.h"
#include "jbig2_huffman.h"
#define JBIG2_HUFFMAN_FLAGS_ISOOB 1
#define JBIG2_HUFFMAN_FLAGS_ISLOW 2
#define JBIG2_HUFFMAN_FLAGS_ISEXT 4
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_t this_word;
uint32_t 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_t
jbig2_huffman_get (Jbig2HuffmanState *hs,
const Jbig2HuffmanTable *table, bool *oob)
{
Jbig2HuffmanEntry *entry;
byte flags;
int offset_bits = hs->offset_bits;
uint32_t this_word = hs->this_word;
uint32_t next_word;
int RANGELEN;
int32_t 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_t 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;
}
#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_t 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>
/* a test bitstream, and a list of the table indicies
to use in decoding it. 1 = table B.1 (A), 2 = table B.2 (B), and so on */
/* this test stream should decode to { 8, 5, oob, 8 } */
const byte test_stream[] = { 0xe9, 0xcb, 0xf4, 0x00 };
const byte test_tabindex[] = { 4, 2, 2, 1 };
static uint32_t
test_get_word (Jbig2WordStream *self, int offset)
{
/* assume test_stream[] is at least 4 bytes */
if (offset+3 > sizeof(test_stream))
return 0;
else
return ( (test_stream[offset] << 24) |
(test_stream[offset+1] << 16) |
(test_stream[offset+2] << 8) |
(test_stream[offset+3]) );
}
int
main (int argc, char **argv)
{
Jbig2HuffmanTable *tables[5];
Jbig2HuffmanState *hs;
Jbig2WordStream ws;
bool oob;
int32_t code;
tables[0] = NULL;
tables[1] = jbig2_build_huffman_table (&jbig_huffman_params_A);
tables[2] = jbig2_build_huffman_table (&jbig_huffman_params_B);
tables[3] = NULL;
tables[4] = jbig2_build_huffman_table (&jbig_huffman_params_D);
ws.get_next_word = test_get_word;
hs = jbig2_huffman_new (&ws);
printf("testing jbig2 huffmann decoding...");
printf("\t(should be 8 5 (oob) 8)\n");
{
int i;
int sequence_length = sizeof(test_tabindex);
for (i = 0; i < sequence_length; i++) {
code = jbig2_huffman_get (hs, tables[test_tabindex[i]], &oob);
if (oob) printf("(oob) ");
else printf("%d ", code);
}
}
printf("\n");
return 0;
}
#endif