summaryrefslogtreecommitdiff
path: root/Build/source/texk/web2c/luatexdir/luapplib/src/util/utillzw.c
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/texk/web2c/luatexdir/luapplib/src/util/utillzw.c')
-rw-r--r--Build/source/texk/web2c/luatexdir/luapplib/src/util/utillzw.c705
1 files changed, 0 insertions, 705 deletions
diff --git a/Build/source/texk/web2c/luatexdir/luapplib/src/util/utillzw.c b/Build/source/texk/web2c/luatexdir/luapplib/src/util/utillzw.c
deleted file mode 100644
index e5134e79473..00000000000
--- a/Build/source/texk/web2c/luatexdir/luapplib/src/util/utillzw.c
+++ /dev/null
@@ -1,705 +0,0 @@
-/* lzw implementation for postscript/pdf filters
-# Notes on LZW
-
-# Encoder
-
-Initially the table contains 256 entires for single bytes. Encoder consumes
-input bytes trying to find the longest sequence stored so far in the table.
-Once it finds a sequence that is not present in the table, it outputs the table
-index of the longest sequence found (accumulated bytes except the last
-consumed) and pushes the new sequence (accumulated bytes including the last
-one) on the top of the table. The last taken byte is not yet written to the
-output, it becomes the beginning of the new sequence to accumulate. Initially,
-encoder outputs 9-bit codes. While the table grows, the number of bits for each
-code increases up to 12. In example, after adding a table entry of index 511 it
-is high time to switch to 10-bit bytes. /EarlyChange=true parameter in stream
-dictionary (both postscript and pdf) informs to increase the number of bits one
-code earlier then necessary. Looks pretty much like an early days bug that
-became a specification :) I have never found a PDF having /EarlyChange key
-specified anyway.
-
-Once the table becomes full (or when encoder decides it is worthy),
-a clear-table marker (code 256) purges the table and restores codes length to
-9. End-of-data marker (code 257) ends the stream. Conventionally, the beginning
-of the stream starts with clear-table marker.
-
-Postscript allows to provide a /UnitLength which determines the bit length of
-codes. The above description assumes UnitLength=8 (default). Allowed values are
-from 3 to 8. Different UnitLength also affects markers; clear-table is then
-2^UnitLength and end-of-data marker is 2^UnitLenth+1.
-
-Encoder outputs 9-12bit codes that are packed into bytes using high-bits-first
-scheme (default) or low-bits-scheme.
-
-PDF spec p. 73 (PS spec p. 135 gives an mistaken output sequence and so
-mistaken output bytes)
-
-Input character sequence (decimal)
-45 45 45 45 45 65 45 45 45 66
-
-Output 9bit codes (decimal)
-256 45 258 258 65 259 66 257
-
-Output 9bit codes (binary)
-100000000 000101101 100000010 100000010 001000001 100000011 001000010 100000001
-
-Output bytes (LowBitsFirst=false); eight high-order bits of code becomes
-the first byte, remaining low-order bit of code becomes the high-order bit of the
-next byte;
-10000000 00001011 01100000 01010000 00100010 00001100 00001100 10000101 00000001
--> 80 0B 60 50 22 0C 0C 85 01
-
-Output bytes (binary, LowBitsFirst=true); eight low-order bits of code becomes
-the first byte, remaining high-order bit of code becomes low-order bit of the
-next byte;
-00000000 01011011 00001000 00010100 00011000 01100100 10100000 10000000 10010000
--> 00 5B 08 14 18 64 A0 80 90
-
-# Decoder
-
-Decoder consumes input bytes transforming them to 9 to 12 bit codes. Initially
-it starts with 9bit codes and the table of 258 fixed codes (same as encoder).
-Basically, it interprets incoming codes as table indices (except 256 and 257
-markers) and it outputs byte sequences stored at given indices. It also
-upbuilds the table and changes the number of bits of codes when necessary. The
-key point on lzw is that both encoder and decoder builds the table
-synchronously.
-
-However, decoder needs some "knowledge" about how encoder works to be able to
-interpret a table index that it doesn't have so far. Look that the output from
-encoder in the example above. The first output code is conventional clear-table
-(256). Then comes a code 45. So far so good, decoder interprets code 45 as
-a (fixed) entry of the table, emitting byte 45. The next code is 258, which is
-should be interpreted as an index in the table. Oops, encoder doesn't have one
-yet. If that occurs, it means that encoder was able to output the new entry
-code just after adding it to a table. It means that
-
- sequence_before + next_byte == next_byte + sequence_after
-
-This may happen not only for sequences like 45 45 45, but also symmetric series
-such as abcbabcba; abcb + a == a + bcba. Decoder must be aware of that and if
-it gets a code one larger than the top table index, it should create one on-fly
-by appending last entry sequence by the first by of the last entry.
-
-# UnitLength
-
-Postscript specification mentions about UnitLength parameter that can be used
-in LZW decoder (not allowed in encoder), with possible values from 3 to 8. This
-parameter determines the number of bits per code; form UnitLength + 1 to 12. It
-also determines which codes are used for clear-table marker (2^UnitLength) and
-end-of-data marker ((2^UnitLength)+1). Postscript specification says (page 134):
-
-"Initially, the code length is (UnitLength + 1) bits and the table contains only
-entries for the (2^UnitLength + 2) fixed codes. As encoding proceeds, entries are
-appended to the table, associating new codes with longer and longer input character
-sequences. The encoding and decoding filters maintain identical copies of
-this table."
-
-Later on page 136 Postscript specification says:
-
-"Data that has been LZW-encoded with a UnitLength less than 8 consists only of
-codes in the range 0 to 2^UnitLength - 1; consequently, the LZWDecode filter produces
-only codes in that range when read. UnitLength also affects the encoded
-representation, as described above."
-
-UnitLength (Postscript only) and LowBitsFirst are used only by decoder.
-EarlyChange should obviously be respected by both encoder and decoder. When
-table index reaches current bit length boundary (511, 1023, ...) it must react
-by increasing the number of bits of input code. But if the index reaches it
-maximum value (when the table is full), decoder is NOT supposed to clear the
-table. When the table is full, encoder must emit clear-table marker and it
-emits this code using 12 bits and reinitialize code bits after that. It means
-that, when the table is full, decoder should get one more 12-bit code (which
-should be clear-table marker) and actually clear the table and reinitialize
-code bits after that.
-
-# Clear-table vs last entry track (after tries and checks)
-
-It is also not quite clear what should actually happen when encoder gets a full
-table and it is supposed to emit clear-table marker. When it gets full, it
-means that it has just appended another entry to the table. And that happens
-only the input sequence collected so far plus the last byte is not present in
-the table. Encoder is supposed to output the table index of the present
-sequence and set the recent byte as a starting index of the new sequence to be
-collected. Even if it is time to clear the table, encoder is still supposed to
-keep the track of the last table entry. Decoder, however, must drop the track of the
-last code on clear-table.
-
-# Decoder table vs encoder table
-
-While decoding we need query lzw table by (subsequent) numeric codes and output
-character sequences stored in the table. While encoding we need to query the
-table on every input byte and fetch indices pointing to character sequences.
-Note that we never need to query the entire table for the longest sequence
-found so far. The encoder table do not need to access the longest character
-sequence at one piece. It is enough to keep the track of the current table
-index and the very next byte. We organize an encoder table into a search tree,
-where every node contains its table index (value) and last byte (key). Except
-initial tree content, every node is created on the base of the previous node
-and it conceptually point the sequence represented by that nodo consists of the
-previous node sequence plus the next byte.
-
-Every new node is a descendant of the node it has been derived from. Every node
-has a map (a search subtree) indexed by suffix byte value, pointing to
-descendants nodes. Every node also has binary tentackles (left/right fields)
-necessary to search the map (except initials, every node lives in a map of some
-ancestor node). The key point is that on every input byte we don't search the
-entire tree, but only the map of the current node children. The map tree is
-a simple binary tree with no balancing mechanism (not worthy to optimize an
-ephemeric structure that may be upbuilt more often then queried).
-
-In our implementation, decoder table requires 4069 entries (topmost index 4095).
-Encoder table, however, needs 4097 entries to handle the case when EarlyIndex
-parameter is 0 (I have never a chance to test that in practise). The node of index
-4096 might be added to a search tree, but its code is never emitted; the lookup
-is purged just after adding that node.
-
-todo:
-- support for LowBitsFirst encoding
-*/
-
-#include "utilmem.h"
-#include "utillzw.h"
-
-/* filter state struct */
-
-typedef struct lzw_entry {
- union {
- const char *rdata; // to be able to init with string literal
- char *data;
- };
- int size;
-} lzw_entry;
-
-#define lzw_index short
-
-typedef struct lzw_node lzw_node;
-
-struct lzw_node {
- lzw_index index;
- unsigned char suffix;
- lzw_node *left;
- lzw_node *right;
- lzw_node *map;
-};
-
-struct lzw_state {
- union {
- lzw_node *lookup; /* encoder table */
- lzw_entry *table; /* decoder table */
- };
- lzw_index index; /* table index */
- union {
- lzw_node *lastnode; /* previous encoder table node */
- struct {
- lzw_entry *lastentry; /* previous decoder table entry */
- int tailbytes; /* num of bytes of lastentry not yet written out */
- };
- };
- int basebits; /* /UnitLength parameter (8) */
- int codebits; /* current code bits */
- int lastbyte; /* previosly read byte */
- int tailbits; /* lastbyte bits not yet consumed */
- int flush; /* encoder */
- int flags; /* options */
-};
-
-typedef union { lzw_state *lzwstate; void *voidstate; } lzw_state_pointer; // to avoid 'dereferencing type-puned ...' warnings
-
-#define LZW_INIT_STATE { { 0 }, 0, { 0 }, 0, 0, 0, 0, 0, 0 }
-
-/* macros */
-
-#define LZW_MIN_BITS 3
-#define LZW_MAX_BITS 12
-#define LZW_TABLE_SIZE (1 << LZW_MAX_BITS)
-#define LZW_LOOKUP_SIZE (LZW_TABLE_SIZE + 1)
-
-#define lzw_bit_range(bits) (bits >= LZW_MIN_BITS && bits <= LZW_BASE_BITS)
-#define lzw_base_bits(flags) (flags & ((1 << 4) - 1)) // 4 low bits of flags is basebits (UnitLength)
-
-#define lzw_initial_codes(state) (1 << state->basebits)
-#define lzw_clear_code(state) lzw_initial_codes(state)
-#define lzw_eod_code(state) (lzw_initial_codes(state) + 1)
-#define lzw_initial_index(state) (lzw_initial_codes(state) + 2)
-
-#define lzw_max_index(state) ((1 << state->codebits) - ((state->flags & LZW_EARLY_INDEX) ? 1 : 0))
-#define lzw_check_bits(state) ((void)(state->index == lzw_max_index(state) && state->codebits < LZW_MAX_BITS && ++state->codebits))
-
-#define lzw_malloc util_malloc
-#define lzw_free util_free
-
-/* decoder */
-
-static struct lzw_entry lzw_initial_table[] = {
- {{"\x00"}, 1}, {{"\x01"}, 1}, {{"\x02"}, 1}, {{"\x03"}, 1}, {{"\x04"}, 1}, {{"\x05"}, 1}, {{"\x06"}, 1}, {{"\x07"}, 1}, {{"\x08"}, 1}, {{"\x09"}, 1}, {{"\x0A"}, 1}, {{"\x0B"}, 1}, {{"\x0C"}, 1}, {{"\x0D"}, 1}, {{"\x0E"}, 1}, {{"\x0F"}, 1},
- {{"\x10"}, 1}, {{"\x11"}, 1}, {{"\x12"}, 1}, {{"\x13"}, 1}, {{"\x14"}, 1}, {{"\x15"}, 1}, {{"\x16"}, 1}, {{"\x17"}, 1}, {{"\x18"}, 1}, {{"\x19"}, 1}, {{"\x1A"}, 1}, {{"\x1B"}, 1}, {{"\x1C"}, 1}, {{"\x1D"}, 1}, {{"\x1E"}, 1}, {{"\x1F"}, 1},
- {{"\x20"}, 1}, {{"\x21"}, 1}, {{"\x22"}, 1}, {{"\x23"}, 1}, {{"\x24"}, 1}, {{"\x25"}, 1}, {{"\x26"}, 1}, {{"\x27"}, 1}, {{"\x28"}, 1}, {{"\x29"}, 1}, {{"\x2A"}, 1}, {{"\x2B"}, 1}, {{"\x2C"}, 1}, {{"\x2D"}, 1}, {{"\x2E"}, 1}, {{"\x2F"}, 1},
- {{"\x30"}, 1}, {{"\x31"}, 1}, {{"\x32"}, 1}, {{"\x33"}, 1}, {{"\x34"}, 1}, {{"\x35"}, 1}, {{"\x36"}, 1}, {{"\x37"}, 1}, {{"\x38"}, 1}, {{"\x39"}, 1}, {{"\x3A"}, 1}, {{"\x3B"}, 1}, {{"\x3C"}, 1}, {{"\x3D"}, 1}, {{"\x3E"}, 1}, {{"\x3F"}, 1},
- {{"\x40"}, 1}, {{"\x41"}, 1}, {{"\x42"}, 1}, {{"\x43"}, 1}, {{"\x44"}, 1}, {{"\x45"}, 1}, {{"\x46"}, 1}, {{"\x47"}, 1}, {{"\x48"}, 1}, {{"\x49"}, 1}, {{"\x4A"}, 1}, {{"\x4B"}, 1}, {{"\x4C"}, 1}, {{"\x4D"}, 1}, {{"\x4E"}, 1}, {{"\x4F"}, 1},
- {{"\x50"}, 1}, {{"\x51"}, 1}, {{"\x52"}, 1}, {{"\x53"}, 1}, {{"\x54"}, 1}, {{"\x55"}, 1}, {{"\x56"}, 1}, {{"\x57"}, 1}, {{"\x58"}, 1}, {{"\x59"}, 1}, {{"\x5A"}, 1}, {{"\x5B"}, 1}, {{"\x5C"}, 1}, {{"\x5D"}, 1}, {{"\x5E"}, 1}, {{"\x5F"}, 1},
- {{"\x60"}, 1}, {{"\x61"}, 1}, {{"\x62"}, 1}, {{"\x63"}, 1}, {{"\x64"}, 1}, {{"\x65"}, 1}, {{"\x66"}, 1}, {{"\x67"}, 1}, {{"\x68"}, 1}, {{"\x69"}, 1}, {{"\x6A"}, 1}, {{"\x6B"}, 1}, {{"\x6C"}, 1}, {{"\x6D"}, 1}, {{"\x6E"}, 1}, {{"\x6F"}, 1},
- {{"\x70"}, 1}, {{"\x71"}, 1}, {{"\x72"}, 1}, {{"\x73"}, 1}, {{"\x74"}, 1}, {{"\x75"}, 1}, {{"\x76"}, 1}, {{"\x77"}, 1}, {{"\x78"}, 1}, {{"\x79"}, 1}, {{"\x7A"}, 1}, {{"\x7B"}, 1}, {{"\x7C"}, 1}, {{"\x7D"}, 1}, {{"\x7E"}, 1}, {{"\x7F"}, 1},
- {{"\x80"}, 1}, {{"\x81"}, 1}, {{"\x82"}, 1}, {{"\x83"}, 1}, {{"\x84"}, 1}, {{"\x85"}, 1}, {{"\x86"}, 1}, {{"\x87"}, 1}, {{"\x88"}, 1}, {{"\x89"}, 1}, {{"\x8A"}, 1}, {{"\x8B"}, 1}, {{"\x8C"}, 1}, {{"\x8D"}, 1}, {{"\x8E"}, 1}, {{"\x8F"}, 1},
- {{"\x90"}, 1}, {{"\x91"}, 1}, {{"\x92"}, 1}, {{"\x93"}, 1}, {{"\x94"}, 1}, {{"\x95"}, 1}, {{"\x96"}, 1}, {{"\x97"}, 1}, {{"\x98"}, 1}, {{"\x99"}, 1}, {{"\x9A"}, 1}, {{"\x9B"}, 1}, {{"\x9C"}, 1}, {{"\x9D"}, 1}, {{"\x9E"}, 1}, {{"\x9F"}, 1},
- {{"\xA0"}, 1}, {{"\xA1"}, 1}, {{"\xA2"}, 1}, {{"\xA3"}, 1}, {{"\xA4"}, 1}, {{"\xA5"}, 1}, {{"\xA6"}, 1}, {{"\xA7"}, 1}, {{"\xA8"}, 1}, {{"\xA9"}, 1}, {{"\xAA"}, 1}, {{"\xAB"}, 1}, {{"\xAC"}, 1}, {{"\xAD"}, 1}, {{"\xAE"}, 1}, {{"\xAF"}, 1},
- {{"\xB0"}, 1}, {{"\xB1"}, 1}, {{"\xB2"}, 1}, {{"\xB3"}, 1}, {{"\xB4"}, 1}, {{"\xB5"}, 1}, {{"\xB6"}, 1}, {{"\xB7"}, 1}, {{"\xB8"}, 1}, {{"\xB9"}, 1}, {{"\xBA"}, 1}, {{"\xBB"}, 1}, {{"\xBC"}, 1}, {{"\xBD"}, 1}, {{"\xBE"}, 1}, {{"\xBF"}, 1},
- {{"\xC0"}, 1}, {{"\xC1"}, 1}, {{"\xC2"}, 1}, {{"\xC3"}, 1}, {{"\xC4"}, 1}, {{"\xC5"}, 1}, {{"\xC6"}, 1}, {{"\xC7"}, 1}, {{"\xC8"}, 1}, {{"\xC9"}, 1}, {{"\xCA"}, 1}, {{"\xCB"}, 1}, {{"\xCC"}, 1}, {{"\xCD"}, 1}, {{"\xCE"}, 1}, {{"\xCF"}, 1},
- {{"\xD0"}, 1}, {{"\xD1"}, 1}, {{"\xD2"}, 1}, {{"\xD3"}, 1}, {{"\xD4"}, 1}, {{"\xD5"}, 1}, {{"\xD6"}, 1}, {{"\xD7"}, 1}, {{"\xD8"}, 1}, {{"\xD9"}, 1}, {{"\xDA"}, 1}, {{"\xDB"}, 1}, {{"\xDC"}, 1}, {{"\xDD"}, 1}, {{"\xDE"}, 1}, {{"\xDF"}, 1},
- {{"\xE0"}, 1}, {{"\xE1"}, 1}, {{"\xE2"}, 1}, {{"\xE3"}, 1}, {{"\xE4"}, 1}, {{"\xE5"}, 1}, {{"\xE6"}, 1}, {{"\xE7"}, 1}, {{"\xE8"}, 1}, {{"\xE9"}, 1}, {{"\xEA"}, 1}, {{"\xEB"}, 1}, {{"\xEC"}, 1}, {{"\xED"}, 1}, {{"\xEE"}, 1}, {{"\xEF"}, 1},
- {{"\xF0"}, 1}, {{"\xF1"}, 1}, {{"\xF2"}, 1}, {{"\xF3"}, 1}, {{"\xF4"}, 1}, {{"\xF5"}, 1}, {{"\xF6"}, 1}, {{"\xF7"}, 1}, {{"\xF8"}, 1}, {{"\xF9"}, 1}, {{"\xFA"}, 1}, {{"\xFB"}, 1}, {{"\xFC"}, 1}, {{"\xFD"}, 1}, {{"\xFE"}, 1}, {{"\xFF"}, 1}
-};
-
-#define lzw_entry_at(state, index) (&state->table[index])
-
-static lzw_state * lzw_decoder_init_table (lzw_state *state, lzw_entry *table, int flags)
-{
- state->basebits = lzw_base_bits(flags); // first four bits or flags
- if (!lzw_bit_range(state->basebits))
- return NULL;
- state->flags = flags;
- if ((state->table = table) == NULL)
- {
- state->table = (lzw_entry *)lzw_malloc(LZW_TABLE_SIZE * sizeof(lzw_entry));
- state->flags |= LZW_TABLE_ALLOC;
- }
- memcpy(state->table, lzw_initial_table, (size_t)lzw_initial_codes(state)*sizeof(lzw_entry));
- // memset(&state->table[lzw_initial_codes(state)], 0, 2*sizeof(lzw_entry)); // eod and clear entries never accessed
- state->codebits = state->basebits + 1;
- state->index = lzw_initial_index(state);
- state->lastentry = NULL;
- state->tailbytes = 0;
- state->lastbyte = 0;
- state->tailbits = 0;
- return state;
-}
-
-lzw_state * lzw_decoder_init (lzw_state *state, int flags)
-{
- return lzw_decoder_init_table(state, NULL, flags);
-}
-
-static void lzw_decoder_clear (lzw_state *state)
-{
- lzw_entry *entry;
- lzw_index initindex = lzw_initial_index(state);
- while (state->index > initindex)
- {
- entry = lzw_entry_at(state, --state->index);
- lzw_free(entry->data);
- // entry->data = NULL;
- // entry->size = 0;
- }
- state->lastentry = NULL;
- state->tailbytes = 0;
- state->codebits = state->basebits + 1;
-}
-
-void lzw_decoder_close (lzw_state *state)
-{
- lzw_decoder_clear(state);
- if (state->flags & LZW_TABLE_ALLOC)
- lzw_free(state->table);
-}
-
-static int lzw_next_entry (lzw_state *state, lzw_entry *nextentry)
-{
- lzw_entry *lastentry, *newentry;
- if ((lastentry = state->lastentry) == NULL)
- return 1; /* its ok */
- if (state->index == LZW_TABLE_SIZE)
- return 0; /* invalid input; eod marker expected earlier */
- /* put the new entry on the top of the table */
- newentry = lzw_entry_at(state, state->index++);
- /* its size is the last entrtyy size plus 1 */
- newentry->size = lastentry->size + 1;
- /* its content is the content of the last entry, */
- newentry->data = (char *)lzw_malloc((size_t)newentry->size);
- memcpy(newentry->data, lastentry->data, lastentry->size);
- /* plus the first byte of the new entry (usually fixed code entry) */
- newentry->data[newentry->size - 1] = nextentry->data[0];
- return 1;
-}
-
-#define lzw_write_bytes(O, state) ((state->tailbytes -= (int)iof_write(O, state->lastentry->data, (size_t)state->tailbytes)) == 0)
-
-iof_status lzw_decode_state (iof *I, iof *O, lzw_state *state)
-{
- const lzw_index clear = lzw_clear_code(state), eod = lzw_eod_code(state);
- lzw_index code;
- lzw_entry *entry;
- if (state->lastentry != NULL)
- { /* write out the tail from the last call */
- if (state->tailbytes > 0 && !lzw_write_bytes(O, state))
- return IOFFULL;
- /* do what we normally do at the end of the loop body below */
- lzw_check_bits(state);
- }
- // if (state->flags & LZW_LOW_BITS_FIRST)
- // return IOFERR;
- while (1)
- {
- /* get input code of length state->codebits */
- code = (state->lastbyte & ((1 << state->tailbits) - 1)) << (state->codebits - state->tailbits);
- for (state->tailbits -= state->codebits; state->tailbits < 0; )
- {
- get_code:
- if ((state->lastbyte = iof_get(I)) < 0)
- return state->flush ? IOFEOF : state->lastbyte;
- state->tailbits += 8;
- if (state->tailbits < 0)
- {
- code |= (state->lastbyte << (-state->tailbits));
- goto get_code;
- }
- else
- {
- code |= (state->lastbyte >> state->tailbits);
- break;
- }
- }
- /* interpret the code */
- if (code < state->index)
- { /* single byte code or special marker */
- if (code == clear)
- {
- lzw_decoder_clear(state);
- continue;
- }
- if (code == eod)
- return IOFEOF;
- entry = lzw_entry_at(state, code);
- if (!lzw_next_entry(state, entry))
- return IOFERR;
- }
- else if (code == state->index)
- { /* apparently encoder has emitted the code of the key just created (see notes) */
- if (!lzw_next_entry(state, state->lastentry))
- return IOFERR;
- entry = lzw_entry_at(state, state->index - 1);
- }
- else
- { /* invalid input code */
- return IOFERR;
- }
- /* record the entry found */
- state->lastentry = entry;
- /* emit the sequence pointed by that entry */
- state->tailbytes = entry->size;
- if (!lzw_write_bytes(O, state))
- return IOFFULL;
- /* check and update code bits */
- lzw_check_bits(state);
- }
- return state->lastbyte; // never reached
-}
-
-/* encoder */
-
-#define lzw_node_at(state, index) (&state->lookup[index])
-
-#define lzw_node_init(node, i, c) (node->index = i, node->suffix = c, node->left = NULL, node->right = NULL, node->map = NULL)
-
-static lzw_state * lzw_encoder_init_table (lzw_state *state, lzw_node *lookup, int flags)
-{
- lzw_index index;
- lzw_node *node;
- state->basebits = lzw_base_bits(flags); // first four bits of flags is base bits of code (default 8)
- if (!lzw_bit_range(state->basebits))
- return NULL;
- state->flags = flags;
- if ((state->lookup = lookup) == NULL)
- {
- state->lookup = lzw_malloc(LZW_LOOKUP_SIZE*sizeof(lzw_node));
- state->flags |= LZW_TABLE_ALLOC;
- }
- state->index = lzw_initial_index(state);
- for (index = 0; index < lzw_initial_codes(state); ++index)
- {
- node = lzw_node_at(state, index);
- lzw_node_init(node, index, (unsigned char)index);
- }
- state->codebits = state->basebits + 1;
- state->lastnode = NULL;
- state->lastbyte = 0;
- state->tailbits = 0;
- return state;
-}
-
-lzw_state * lzw_encoder_init (lzw_state *state, int flags)
-{
- return lzw_encoder_init_table(state, NULL, flags);
-}
-
-void lzw_encoder_close (lzw_state *state)
-{
- if (state->flags & LZW_TABLE_ALLOC)
- lzw_free(state->lookup);
-}
-
-static void lzw_encoder_clear (lzw_state *state)
-{
- lzw_node *node;
- lzw_index index;
- /* clear fixed nodes */
- for (index = 0; index < lzw_initial_codes(state); ++index)
- {
- node = lzw_node_at(state, index);
- lzw_node_init(node, index, (unsigned char)index);
- }
- /* reset table index */
- state->index = lzw_initial_index(state);
- /* reset code bits */
- state->codebits = state->basebits + 1;
-}
-
-static void lzw_put_code (iof *O, lzw_state *state, lzw_index code, int todobits)
-{
- int leftbits, rightbits;
- do
- {
- leftbits = 8 - state->tailbits;
- rightbits = todobits - leftbits;
- if (rightbits >= 0)
- {
- state->lastbyte |= (code >> rightbits);
- iof_put(O, state->lastbyte);
- code = code & ((1 << rightbits) - 1);
- todobits -= leftbits;
- state->lastbyte = 0;
- state->tailbits = 0;
- }
- else
- {
- state->lastbyte |= (code << (-rightbits));
- state->tailbits += todobits;
- return;
- }
- } while (1);
-}
-
-static iof_status lzw_encode_last (iof *O, lzw_state *state)
-{
- if (state->flush)
- {
- /* put the last code if any */
- if (state->lastnode != NULL)
- lzw_put_code(O, state, state->lastnode->index, state->codebits);
- /* put eod marker, */
- lzw_put_code(O, state, lzw_eod_code(state), state->codebits);
- /* with tail bits set to 0 */
- if (state->tailbits > 0)
- lzw_put_code(O, state, 0, 8 - state->tailbits);
- return IOFEOF;
- }
- return IOFEMPTY;
-}
-
-static lzw_node * lzw_node_push (lzw_state *state, unsigned char suffix)
-{
- lzw_node *node;
- node = lzw_node_at(state, state->index);
- lzw_node_init(node, state->index, suffix);
- ++state->index;
- return node;
-}
-
-static int lzw_next_node (lzw_state *state, unsigned char suffix)
-{
- lzw_node *node;
- if ((node = state->lastnode->map) == NULL)
- {
- state->lastnode->map = lzw_node_push(state, suffix);
- return 0;
- }
- while (1)
- {
- if (suffix < node->suffix)
- {
- if (node->left == NULL)
- {
- node->left = lzw_node_push(state, suffix);
- return 0;
- }
- node = node->left;
- }
- else if (suffix > node->suffix)
- {
- if (node->right == NULL)
- {
- node->right = lzw_node_push(state, suffix);
- return 0;
- }
- node = node->right;
- }
- else
- {
- state->lastnode = node;
- return 1;
- }
- }
- return 0; // never reached
-}
-
-iof_status lzw_encode_state (iof *I, iof *O, lzw_state *state)
-{
- int byte;
- if (state->lastnode == NULL)
- { /* first call only; following convention, put clear-table marker */
- if (!iof_ensure(O, 2))
- return IOFFULL;
- lzw_put_code(O, state, lzw_clear_code(state), state->codebits);
- /* get the first input byte and initialize the current table entry */
- if ((byte = iof_get(I)) < 0)
- return lzw_encode_last(O, state);
- state->lastnode = lzw_node_at(state, byte);
- }
- while (iof_ensure(O, 2))
- { /* we need to write at most 2 bytes on each iteration */
- if ((byte = iof_get(I)) < 0)
- return lzw_encode_last(O, state);
- if (lzw_next_node(state, (unsigned char)byte) == 0)
- { /* means that the key hasn't been found and the new entry has just been created */
- /* output the code pointing the longest sequence so far */
- lzw_put_code(O, state, state->lastnode->index, state->codebits);
- /* update code bits */
- if (state->index == lzw_max_index(state) + 1)
- {
- if (state->codebits < LZW_MAX_BITS)
- ++state->codebits;
- else
- {
- /* put clear-table marker */
- lzw_put_code(O, state, lzw_clear_code(state), state->codebits);
- /* reset the table */
- lzw_encoder_clear(state);
- }
- }
- /* in any case, recent byte becomes the current table code */
- state->lastnode = lzw_node_at(state, byte);
- }
- /* otherwise no new entry is appended and state->lastnode points the longer sequence just found */
- }
- return IOFFULL;
-}
-
-/* single call codecs */
-
-iof_status lzw_decode (iof *I, iof *O, int flags)
-{
- lzw_state state = LZW_INIT_STATE;
- lzw_entry table[LZW_TABLE_SIZE];
- int ret;
- lzw_decoder_init_table(&state, table, flags);
- state.flush = 1;
- ret = lzw_decode_state(I, O, &state);
- // iof_flush(O); // ?
- lzw_decoder_close(&state);
- return ret;
-}
-
-iof_status lzw_encode (iof *I, iof *O, int flags)
-{
- lzw_state state = LZW_INIT_STATE;
- lzw_node lookup[LZW_LOOKUP_SIZE];
- int ret;
- lzw_encoder_init_table(&state, lookup, flags);
- state.flush = 1;
- ret = lzw_encode_state(I, O, &state);
- // iof_flush(O); // ?
- lzw_encoder_close(&state);
- return ret;
-}
-
-/* filters */
-
-// lzw decoder function
-
-static size_t lzw_decoder (iof *F, iof_mode mode)
-{
- lzw_state *state;
- iof_status status;
- size_t tail;
-
- state = iof_filter_state(lzw_state *, F);
- switch(mode)
- {
- case IOFLOAD:
- case IOFREAD:
- if (F->flags & IOF_STOPPED)
- return 0;
- tail = iof_tail(F);
- F->pos = F->buf + tail;
- F->end = F->buf + F->space;
- do {
- status = lzw_decode_state(F->next, F, state);
- } while (mode == IOFLOAD && status == IOFFULL && iof_resize_buffer(F));
- return iof_decoder_retval(F, "lzw", status);
- case IOFCLOSE:
- lzw_decoder_close(state);
- iof_free(F);
- return 0;
- default:
- break;
- }
- return 0;
-}
-
-// lzw encoder function
-
-static size_t lzw_encoder (iof *F, iof_mode mode)
-{
- lzw_state *state;
- iof_status status;
-
- state = iof_filter_state(lzw_state *, F);
- switch (mode)
- {
- case IOFFLUSH:
- state->flush = 1;
- FALLTHRU // fall through
- case IOFWRITE:
- F->end = F->pos;
- F->pos = F->buf;
- status = lzw_encode_state(F, F->next, state);
- return iof_encoder_retval(F, "lzw", status);
- case IOFCLOSE:
- if (!state->flush)
- lzw_encoder(F, IOFFLUSH);
- lzw_encoder_close(state);
- iof_free(F);
- return 0;
- default:
- break;
- }
- return 0;
-}
-
-iof * iof_filter_lzw_decoder (iof *N, int flags)
-{
- iof *I;
- lzw_state_pointer P;
- I = iof_filter_reader(lzw_decoder, sizeof(lzw_state), &P.voidstate);
- iof_setup_next(I, N);
- if (lzw_decoder_init(P.lzwstate, flags) == NULL)
- {
- iof_discard(I);
- return NULL;
- }
- P.lzwstate->flush = 1;
- return I;
-}
-
-iof * iof_filter_lzw_encoder (iof *N, int flags)
-{
- iof *O;
- lzw_state_pointer P;
- O = iof_filter_writer(lzw_encoder, sizeof(lzw_state), &P.voidstate);
- iof_setup_next(O, N);
- if (lzw_encoder_init(P.lzwstate, flags) == NULL)
- {
- iof_discard(O);
- return NULL;
- }
- return O;
-}