summaryrefslogtreecommitdiff
path: root/Build/source/libs/pplib/pplib-src/src/util/utillzw.c
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/libs/pplib/pplib-src/src/util/utillzw.c')
-rw-r--r--Build/source/libs/pplib/pplib-src/src/util/utillzw.c705
1 files changed, 705 insertions, 0 deletions
diff --git a/Build/source/libs/pplib/pplib-src/src/util/utillzw.c b/Build/source/libs/pplib/pplib-src/src/util/utillzw.c
new file mode 100644
index 00000000000..e5134e79473
--- /dev/null
+++ b/Build/source/libs/pplib/pplib-src/src/util/utillzw.c
@@ -0,0 +1,705 @@
+/* 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;
+}