summaryrefslogtreecommitdiff
path: root/Build/source/texk/web2c/luatexdir/luapplib/src/util/utillzw.c
blob: e5134e79473a91051b7c060383f419c80d95a038 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
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;
}