Go to most recent revision | Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 4680 | right-hear | 1 | #include "fitz.h" |
| 2 | |||
| 3 | /* TODO: error checking */ |
||
| 4 | |||
| 5 | enum |
||
| 6 | { |
||
| 7 | MIN_BITS = 9, |
||
| 8 | MAX_BITS = 12, |
||
| 9 | NUM_CODES = (1 << MAX_BITS), |
||
| 10 | LZW_CLEAR = 256, |
||
| 11 | LZW_EOD = 257, |
||
| 12 | LZW_FIRST = 258, |
||
| 13 | MAX_LENGTH = 4097 |
||
| 14 | }; |
||
| 15 | |||
| 16 | typedef struct lzw_code_s lzw_code; |
||
| 17 | |||
| 18 | struct lzw_code_s |
||
| 19 | { |
||
| 20 | int prev; /* prev code (in string) */ |
||
| 21 | unsigned short length; /* string len, including this token */ |
||
| 22 | unsigned char value; /* data value */ |
||
| 23 | unsigned char first_char; /* first token of string */ |
||
| 24 | }; |
||
| 25 | |||
| 26 | typedef struct fz_lzwd_s fz_lzwd; |
||
| 27 | |||
| 28 | struct fz_lzwd_s |
||
| 29 | { |
||
| 30 | fz_stream *chain; |
||
| 31 | int eod; |
||
| 32 | |||
| 33 | int early_change; |
||
| 34 | |||
| 35 | int code_bits; /* num bits/code */ |
||
| 36 | int code; /* current code */ |
||
| 37 | int old_code; /* previously recognized code */ |
||
| 38 | int next_code; /* next free entry */ |
||
| 39 | |||
| 40 | lzw_code table[NUM_CODES]; |
||
| 41 | |||
| 42 | unsigned char bp[MAX_LENGTH]; |
||
| 43 | unsigned char *rp, *wp; |
||
| 44 | }; |
||
| 45 | |||
| 46 | static int |
||
| 47 | read_lzwd(fz_stream *stm, unsigned char *buf, int len) |
||
| 48 | { |
||
| 49 | fz_lzwd *lzw = stm->state; |
||
| 50 | lzw_code *table = lzw->table; |
||
| 51 | unsigned char *p = buf; |
||
| 52 | unsigned char *ep = buf + len; |
||
| 53 | unsigned char *s; |
||
| 54 | int codelen; |
||
| 55 | |||
| 56 | int code_bits = lzw->code_bits; |
||
| 57 | int code = lzw->code; |
||
| 58 | int old_code = lzw->old_code; |
||
| 59 | int next_code = lzw->next_code; |
||
| 60 | |||
| 61 | while (lzw->rp < lzw->wp && p < ep) |
||
| 62 | *p++ = *lzw->rp++; |
||
| 63 | |||
| 64 | while (p < ep) |
||
| 65 | { |
||
| 66 | if (lzw->eod) |
||
| 67 | return 0; |
||
| 68 | |||
| 69 | code = fz_read_bits(lzw->chain, code_bits); |
||
| 70 | |||
| 71 | if (fz_is_eof_bits(lzw->chain)) |
||
| 72 | { |
||
| 73 | lzw->eod = 1; |
||
| 74 | break; |
||
| 75 | } |
||
| 76 | |||
| 77 | if (code == LZW_EOD) |
||
| 78 | { |
||
| 79 | lzw->eod = 1; |
||
| 80 | break; |
||
| 81 | } |
||
| 82 | |||
| 83 | if (code == LZW_CLEAR) |
||
| 84 | { |
||
| 85 | code_bits = MIN_BITS; |
||
| 86 | next_code = LZW_FIRST; |
||
| 87 | old_code = -1; |
||
| 88 | continue; |
||
| 89 | } |
||
| 90 | |||
| 91 | /* if stream starts without a clear code, old_code is undefined... */ |
||
| 92 | if (old_code == -1) |
||
| 93 | { |
||
| 94 | old_code = code; |
||
| 95 | } |
||
| 96 | else |
||
| 97 | { |
||
| 98 | /* add new entry to the code table */ |
||
| 99 | table[next_code].prev = old_code; |
||
| 100 | table[next_code].first_char = table[old_code].first_char; |
||
| 101 | table[next_code].length = table[old_code].length + 1; |
||
| 102 | if (code < next_code) |
||
| 103 | table[next_code].value = table[code].first_char; |
||
| 104 | else if (code == next_code) |
||
| 105 | table[next_code].value = table[next_code].first_char; |
||
| 106 | else |
||
| 107 | fz_warn("out of range code encountered in lzw decode"); |
||
| 108 | |||
| 109 | next_code ++; |
||
| 110 | |||
| 111 | if (next_code > (1 << code_bits) - lzw->early_change - 1) |
||
| 112 | { |
||
| 113 | code_bits ++; |
||
| 114 | if (code_bits > MAX_BITS) |
||
| 115 | code_bits = MAX_BITS; /* FIXME */ |
||
| 116 | } |
||
| 117 | |||
| 118 | old_code = code; |
||
| 119 | } |
||
| 120 | |||
| 121 | /* code maps to a string, copy to output (in reverse...) */ |
||
| 122 | if (code > 255) |
||
| 123 | { |
||
| 124 | codelen = table[code].length; |
||
| 125 | lzw->rp = lzw->bp; |
||
| 126 | lzw->wp = lzw->bp + codelen; |
||
| 127 | |||
| 128 | assert(codelen < MAX_LENGTH); |
||
| 129 | |||
| 130 | s = lzw->wp; |
||
| 131 | do { |
||
| 132 | *(--s) = table[code].value; |
||
| 133 | code = table[code].prev; |
||
| 134 | } while (code >= 0 && s > lzw->bp); |
||
| 135 | } |
||
| 136 | |||
| 137 | /* ... or just a single character */ |
||
| 138 | else |
||
| 139 | { |
||
| 140 | lzw->bp[0] = code; |
||
| 141 | lzw->rp = lzw->bp; |
||
| 142 | lzw->wp = lzw->bp + 1; |
||
| 143 | } |
||
| 144 | |||
| 145 | /* copy to output */ |
||
| 146 | while (lzw->rp < lzw->wp && p < ep) |
||
| 147 | *p++ = *lzw->rp++; |
||
| 148 | } |
||
| 149 | |||
| 150 | lzw->code_bits = code_bits; |
||
| 151 | lzw->code = code; |
||
| 152 | lzw->old_code = old_code; |
||
| 153 | lzw->next_code = next_code; |
||
| 154 | |||
| 155 | return p - buf; |
||
| 156 | } |
||
| 157 | |||
| 158 | static void |
||
| 159 | close_lzwd(fz_stream *stm) |
||
| 160 | { |
||
| 161 | fz_lzwd *lzw = stm->state; |
||
| 162 | fz_close(lzw->chain); |
||
| 163 | fz_free(lzw); |
||
| 164 | } |
||
| 165 | |||
| 166 | fz_stream * |
||
| 167 | fz_open_lzwd(fz_stream *chain, fz_obj *params) |
||
| 168 | { |
||
| 169 | fz_lzwd *lzw; |
||
| 170 | fz_obj *obj; |
||
| 171 | int i; |
||
| 172 | |||
| 173 | lzw = fz_malloc(sizeof(fz_lzwd)); |
||
| 174 | lzw->chain = chain; |
||
| 175 | lzw->eod = 0; |
||
| 176 | lzw->early_change = 1; |
||
| 177 | |||
| 178 | obj = fz_dict_gets(params, "EarlyChange"); |
||
| 179 | if (obj) |
||
| 180 | lzw->early_change = !!fz_to_int(obj); |
||
| 181 | |||
| 182 | for (i = 0; i < 256; i++) |
||
| 183 | { |
||
| 184 | lzw->table[i].value = i; |
||
| 185 | lzw->table[i].first_char = i; |
||
| 186 | lzw->table[i].length = 1; |
||
| 187 | lzw->table[i].prev = -1; |
||
| 188 | } |
||
| 189 | |||
| 190 | for (i = 256; i < NUM_CODES; i++) |
||
| 191 | { |
||
| 192 | lzw->table[i].value = 0; |
||
| 193 | lzw->table[i].first_char = 0; |
||
| 194 | lzw->table[i].length = 0; |
||
| 195 | lzw->table[i].prev = -1; |
||
| 196 | } |
||
| 197 | |||
| 198 | lzw->code_bits = MIN_BITS; |
||
| 199 | lzw->code = -1; |
||
| 200 | lzw->next_code = LZW_FIRST; |
||
| 201 | lzw->old_code = -1; |
||
| 202 | lzw->rp = lzw->bp; |
||
| 203 | lzw->wp = lzw->bp; |
||
| 204 | |||
| 205 | return fz_new_stream(lzw, read_lzwd, close_lzwd); |
||
| 206 | } |