home *** CD-ROM | disk | FTP | other *** search
- /* Copyright (C) 1994 Aladdin Enterprises. All rights reserved.
-
- This file is part of Aladdin Ghostscript.
-
- Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND. No author
- or distributor accepts any responsibility for the consequences of using it,
- or for whether it serves any particular purpose or works at all, unless he
- or she says so in writing. Refer to the Aladdin Ghostscript Free Public
- License (the "License") for full details.
-
- Every copy of Aladdin Ghostscript must include a copy of the License,
- normally in a plain ASCII text file named PUBLIC. The License grants you
- the right to copy, modify and redistribute Aladdin Ghostscript, but only
- under certain conditions described in the License. Among other things, the
- License requires that the copyright notice and this notice be preserved on
- all copies.
- */
-
- /* sbhc.c */
- /* Bounded Huffman code filters */
- #include "stdio_.h"
- #include "gdebug.h"
- #include "strimpl.h"
- #include "sbhc.h"
-
- /*#define TEST*/
-
- /* ------ Huffman coding support ------ */
-
- /* Generate the encoding table from the definition. */
- /* The size of the encode array is def->num_values. */
- void
- bhc_make_encoding(hce_code *encode, const hc_definition *def)
- { uint next = 0;
- const ushort *pvalue = def->values;
- uint i, k;
- for ( i = 1; i <= def->num_counts; i++ )
- { for ( k = 0; k < def->counts[i]; k++, pvalue++, next++ )
- { hce_code *pce = encode + *pvalue;
- pce->code = next;
- pce->code_length = i;
- }
- next <<= 1;
- }
- }
-
- /* We decode in two steps, first indexing into a table with */
- /* a fixed number of bits from the source, and then indexing into */
- /* an auxiliary table if necessary. (See shc.h for details.) */
-
- /* Calculate the size of the decoding table. */
- uint
- bhc_sizeof_decoding(const hc_definition *def, int initial_bits)
- { uint size = 1 << initial_bits;
- uint carry = 0, mask = ~1;
- uint i;
- for ( i = initial_bits + 1; i <= def->num_counts;
- i++, carry <<= 1, mask <<= 1
- )
- { carry += def->counts[i];
- size += carry & mask;
- carry &= ~mask;
- }
- return size;
- }
-
- /* Generate the decoding tables. */
- void
- bhc_make_decoding(hcd_code *decode, const hc_definition *def,
- int initial_bits)
- { /* Make entries for single-dispatch codes. */
- { hcd_code *pcd = decode;
- const ushort *pvalue = def->values;
- uint i, k, d;
- for ( i = 0; i <= initial_bits; i++ )
- { for ( k = 0; k < def->counts[i]; k++, pvalue++ )
- { for ( d = 1 << (initial_bits - i); d > 0;
- d--, pcd++
- )
- pcd->value = *pvalue,
- pcd->code_length = i;
- }
- }
- }
- /* Make entries for two-dispatch codes. */
- /* By working backward, we can do this more easily */
- /* in a single pass. */
- { uint dsize = bhc_sizeof_decoding(def, initial_bits);
- hcd_code *pcd = decode + (1 << initial_bits);
- hcd_code *pcd2 = decode + dsize;
- const ushort *pvalue = def->values + def->num_values;
- uint entries_left = 0, slots_left = 0, mult_shift = 0;
- uint i = def->num_counts + 1, j;
- for ( ; ; )
- { if ( slots_left == 0 )
- { if ( entries_left != 0 )
- { slots_left = 1 << (i - initial_bits);
- mult_shift = 0;
- continue;
- }
- if ( --i <= initial_bits )
- break;
- entries_left = def->counts[i];
- continue;
- }
- if ( entries_left == 0 )
- { entries_left = def->counts[--i];
- mult_shift++;
- continue;
- }
- --entries_left, --pvalue;
- for ( j = 1 << mult_shift; j > 0; j-- )
- { --pcd2;
- pcd2->value = *pvalue;
- pcd2->code_length = i - initial_bits;
- }
- if ( (slots_left -= 1 << mult_shift) == 0 )
- { --pcd;
- pcd->value = pcd2 - decode;
- pcd->code_length = i + mult_shift;
- }
- }
- }
- }
-
- /* Test program */
- #ifdef TEST
- int
- main(int argc, const char *argv[])
- { static uint counts[5] = { 0, 0, 1, 5, 2 };
- static uint values[8] = { 0, 1, 4, 5, 6, 7, 2, 3 };
- static const hc_definition def = {
- counts, countof(counts) - 1,
- values, countof(values)
- };
- hce_code encode[8];
- hcd_code decode[99];
- uint i;
- uint dsize;
- bhc_make_encoding(encode, &def);
- for ( i = 0; i < countof(values); i++ )
- printf("encode[%d] size=%d code=%d\n",
- i, (int)encode[i].code_length, (int)encode[i].code);
- dsize = bhc_sizeof_decoding(&def, 2);
- printf("Decoding size = %d\n", dsize);
- bhc_make_decoding(decode, &def, 2);
- for ( i = 0; i < dsize; i++ )
- printf("decode[%d] size=%d code=%d\n",
- i, (int)decode[i].code_length, (int)decode[i].value);
- return 0;
- }
- #endif
-
- /* ------ BoundedHuffmanEncode ------ */
-
- private_st_BHCE_state();
-
- #define ss ((stream_BHCE_state *)st)
-
- /* Initialize BoundedHuffmanEncode filter. */
- private int
- s_BHCE_init(register stream_state *st)
- { uint count = ss->encode.count = ss->definition.num_values;
- hce_code *encode = ss->encode.codes =
- (hce_code *)gs_alloc_byte_array(st->memory, count,
- sizeof(hce_code), "BHCE encode");
- if ( encode == 0 )
- return ERRC; /****** WRONG ******/
- bhc_make_encoding(encode, &ss->definition);
- s_hce_init_inline(ss);
- return 0;
- }
-
- /* Release the filter. */
- private void
- s_BHCE_release(stream_state *st)
- { gs_free_object(st->memory, ss->encode.codes, "BHCE encode");
- }
-
- /* Process a buffer. */
- private int
- s_BHCE_process(stream_state *st, stream_cursor_read *pr,
- stream_cursor_write *pw, bool last)
- { const byte *p = pr->ptr;
- const byte *rlimit = pr->limit;
- byte *q = pw->ptr;
- byte *wlimit = pw->limit - (hc_bits_size >> 3);
- const hce_code *encode = ss->encode.codes;
- uint num_values = ss->definition.num_values;
- int status = 0;
- while ( p < rlimit && q < wlimit )
- { uint value = *++p;
- const hce_code *cp = &encode[value];
- if ( value >= num_values )
- { status = ERRC;
- break;
- }
- hc_put_code((stream_hc_state *)ss, q, cp);
- }
- if ( last && status == 0 )
- { if ( q >= wlimit )
- status = 1;
- else
- q = hc_put_last_bits((stream_hc_state *)ss, q);
- }
- pr->ptr = p;
- pw->ptr = q;
- return (p == rlimit ? 0 : 1);
- }
-
- #undef ss
-
- /* Stream template */
- const stream_template s_BHCE_template =
- { &st_BHCE_state, s_BHCE_init, s_BHCE_process,
- 1, hc_bits_size >> 3, s_BHCE_release
- };
-
- /* ------ BoundedHuffmanDecode ------ */
-
- private_st_BHCD_state();
-
- #define ss ((stream_BHCD_state *)st)
-
- #define hcd_initial_bits 7 /* arbitrary, >= 1 and <= 8 */
-
- /* Initialize BoundedHuffmanDecode filter. */
- private int
- s_BHCD_init(register stream_state *st)
- { uint initial_bits = ss->decode.initial_bits =
- min(hcd_initial_bits, ss->definition.num_counts);
- uint dsize = bhc_sizeof_decoding(&ss->definition, initial_bits);
- hcd_code *decode = ss->decode.codes =
- (hcd_code *)gs_alloc_byte_array(st->memory, dsize,
- sizeof(hcd_code), "BHCD decode");
- if ( decode == 0 )
- return ERRC; /****** WRONG ******/
- bhc_make_decoding(decode, &ss->definition, initial_bits);
- ss->decode.count = ss->definition.num_values;
- s_hcd_init_inline(ss);
- return 0;
- }
-
- /* Release the filter. */
- private void
- s_BHCD_release(stream_state *st)
- { gs_free_object(st->memory, ss->decode.codes, "BHCD decode");
- }
-
- /* Process a buffer. */
- private int
- s_BHCD_process(stream_state *st, stream_cursor_read *pr,
- stream_cursor_write *pw, bool last)
- { hcd_declare_state;
- byte *q = pw->ptr;
- byte *wlimit = pw->limit;
- const hcd_code *decode = ss->decode.codes;
- uint initial_bits = ss->decode.initial_bits;
- int status = 0;
- hcd_load_state();
- for ( ; ; )
- { const hcd_code *cp;
- int clen;
- hcd_ensure_bits(initial_bits, x1);
- cp = &decode[hcd_peek_var_bits(initial_bits)];
- w1: if ( q >= wlimit )
- { status = 1;
- break;
- }
- if ( (clen = cp->code_length) > initial_bits )
- { if ( !hcd_bits_available(clen) )
- { /* We don't have enough bits for */
- /* all possible codes that begin this way, */
- /* but we might have enough for */
- /* the next code. */
- /****** NOT IMPLEMENTED YET ******/
- break;
- }
- clen -= initial_bits;
- hcd_skip_bits(initial_bits);
- hcd_ensure_bits(clen, out); /* can't exit */
- cp = &decode[cp->value + hcd_peek_var_bits(clen)];
- hcd_skip_bits(cp->code_length);
- }
- else
- { hcd_skip_bits(clen);
- }
- *++q = cp->value;
- continue;
- /* We don't have enough bits for all possible */
- /* codes, but we might have enough for */
- /* the next code. */
- x1: cp = &decode[(bits & ((1 << bits_left) - 1)) <<
- (initial_bits - bits_left)];
- if ( (clen = cp->code_length) <= bits_left )
- goto w1;
- break;
- }
- out: hcd_store_state();
- pw->ptr = q;
- return status;
- }
-
- #undef ss
-
- /* Stream template */
- const stream_template s_BHCD_template =
- { &st_BHCD_state, s_BHCD_init, s_BHCD_process, 1, 1, s_BHCD_release
- };
-