Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4349 | Serge | 1 | /* |
2 | * LZW decoder |
||
3 | * Copyright (c) 2003 Fabrice Bellard |
||
4 | * Copyright (c) 2006 Konstantin Shishkov |
||
5 | * |
||
6 | * This file is part of FFmpeg. |
||
7 | * |
||
8 | * FFmpeg is free software; you can redistribute it and/or |
||
9 | * modify it under the terms of the GNU Lesser General Public |
||
10 | * License as published by the Free Software Foundation; either |
||
11 | * version 2.1 of the License, or (at your option) any later version. |
||
12 | * |
||
13 | * FFmpeg is distributed in the hope that it will be useful, |
||
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
||
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
||
16 | * Lesser General Public License for more details. |
||
17 | * |
||
18 | * You should have received a copy of the GNU Lesser General Public |
||
19 | * License along with FFmpeg; if not, write to the Free Software |
||
20 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
||
21 | */ |
||
22 | |||
23 | /** |
||
24 | * @file |
||
25 | * @brief LZW decoding routines |
||
26 | * @author Fabrice Bellard |
||
27 | * @author modified for use in TIFF by Konstantin Shishkov |
||
28 | */ |
||
29 | |||
30 | #include "avcodec.h" |
||
31 | #include "lzw.h" |
||
32 | #include "libavutil/mem.h" |
||
33 | |||
34 | #define LZW_MAXBITS 12 |
||
35 | #define LZW_SIZTABLE (1< |
||
36 | |||
37 | static const uint16_t mask[17] = |
||
38 | { |
||
39 | 0x0000, 0x0001, 0x0003, 0x0007, |
||
40 | 0x000F, 0x001F, 0x003F, 0x007F, |
||
41 | 0x00FF, 0x01FF, 0x03FF, 0x07FF, |
||
42 | 0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF |
||
43 | }; |
||
44 | |||
45 | struct LZWState { |
||
46 | const uint8_t *pbuf, *ebuf; |
||
47 | int bbits; |
||
48 | unsigned int bbuf; |
||
49 | |||
50 | int mode; ///< Decoder mode |
||
51 | int cursize; ///< The current code size |
||
52 | int curmask; |
||
53 | int codesize; |
||
54 | int clear_code; |
||
55 | int end_code; |
||
56 | int newcodes; ///< First available code |
||
57 | int top_slot; ///< Highest code for current size |
||
58 | int extra_slot; |
||
59 | int slot; ///< Last read code |
||
60 | int fc, oc; |
||
61 | uint8_t *sp; |
||
62 | uint8_t stack[LZW_SIZTABLE]; |
||
63 | uint8_t suffix[LZW_SIZTABLE]; |
||
64 | uint16_t prefix[LZW_SIZTABLE]; |
||
65 | int bs; ///< current buffer size for GIF |
||
66 | }; |
||
67 | |||
68 | /* get one code from stream */ |
||
69 | static int lzw_get_code(struct LZWState * s) |
||
70 | { |
||
71 | int c; |
||
72 | |||
73 | if(s->mode == FF_LZW_GIF) { |
||
74 | while (s->bbits < s->cursize) { |
||
75 | if (!s->bs) { |
||
76 | s->bs = *s->pbuf++; |
||
77 | } |
||
78 | s->bbuf |= (*s->pbuf++) << s->bbits; |
||
79 | s->bbits += 8; |
||
80 | s->bs--; |
||
81 | } |
||
82 | c = s->bbuf; |
||
83 | s->bbuf >>= s->cursize; |
||
84 | } else { // TIFF |
||
85 | while (s->bbits < s->cursize) { |
||
86 | s->bbuf = (s->bbuf << 8) | (*s->pbuf++); |
||
87 | s->bbits += 8; |
||
88 | } |
||
89 | c = s->bbuf >> (s->bbits - s->cursize); |
||
90 | } |
||
91 | s->bbits -= s->cursize; |
||
92 | return c & s->curmask; |
||
93 | } |
||
94 | |||
95 | void ff_lzw_decode_tail(LZWState *p) |
||
96 | { |
||
97 | struct LZWState *s = (struct LZWState *)p; |
||
98 | |||
99 | if(s->mode == FF_LZW_GIF) { |
||
100 | while (s->bs > 0) { |
||
101 | if (s->bs >= s->ebuf - s->pbuf) { |
||
102 | s->pbuf = s->ebuf; |
||
103 | break; |
||
104 | } else { |
||
105 | s->pbuf += s->bs; |
||
106 | s->bs = *s->pbuf++; |
||
107 | } |
||
108 | } |
||
109 | }else |
||
110 | s->pbuf= s->ebuf; |
||
111 | } |
||
112 | |||
113 | av_cold void ff_lzw_decode_open(LZWState **p) |
||
114 | { |
||
115 | *p = av_mallocz(sizeof(struct LZWState)); |
||
116 | } |
||
117 | |||
118 | av_cold void ff_lzw_decode_close(LZWState **p) |
||
119 | { |
||
120 | av_freep(p); |
||
121 | } |
||
122 | |||
123 | /** |
||
124 | * Initialize LZW decoder |
||
125 | * @param p LZW context |
||
126 | * @param csize initial code size in bits |
||
127 | * @param buf input data |
||
128 | * @param buf_size input data size |
||
129 | * @param mode decoder working mode - either GIF or TIFF |
||
130 | */ |
||
131 | int ff_lzw_decode_init(LZWState *p, int csize, const uint8_t *buf, int buf_size, int mode) |
||
132 | { |
||
133 | struct LZWState *s = (struct LZWState *)p; |
||
134 | |||
135 | if(csize < 1 || csize >= LZW_MAXBITS) |
||
136 | return -1; |
||
137 | /* read buffer */ |
||
138 | s->pbuf = buf; |
||
139 | s->ebuf = s->pbuf + buf_size; |
||
140 | s->bbuf = 0; |
||
141 | s->bbits = 0; |
||
142 | s->bs = 0; |
||
143 | |||
144 | /* decoder */ |
||
145 | s->codesize = csize; |
||
146 | s->cursize = s->codesize + 1; |
||
147 | s->curmask = mask[s->cursize]; |
||
148 | s->top_slot = 1 << s->cursize; |
||
149 | s->clear_code = 1 << s->codesize; |
||
150 | s->end_code = s->clear_code + 1; |
||
151 | s->slot = s->newcodes = s->clear_code + 2; |
||
152 | s->oc = s->fc = -1; |
||
153 | s->sp = s->stack; |
||
154 | |||
155 | s->mode = mode; |
||
156 | s->extra_slot = s->mode == FF_LZW_TIFF; |
||
157 | return 0; |
||
158 | } |
||
159 | |||
160 | /** |
||
161 | * Decode given number of bytes |
||
162 | * NOTE: the algorithm here is inspired from the LZW GIF decoder |
||
163 | * written by Steven A. Bennett in 1987. |
||
164 | * |
||
165 | * @param p LZW context |
||
166 | * @param buf output buffer |
||
167 | * @param len number of bytes to decode |
||
168 | * @return number of bytes decoded |
||
169 | */ |
||
170 | int ff_lzw_decode(LZWState *p, uint8_t *buf, int len){ |
||
171 | int l, c, code, oc, fc; |
||
172 | uint8_t *sp; |
||
173 | struct LZWState *s = (struct LZWState *)p; |
||
174 | |||
175 | if (s->end_code < 0) |
||
176 | return 0; |
||
177 | |||
178 | l = len; |
||
179 | sp = s->sp; |
||
180 | oc = s->oc; |
||
181 | fc = s->fc; |
||
182 | |||
183 | for (;;) { |
||
184 | while (sp > s->stack) { |
||
185 | *buf++ = *(--sp); |
||
186 | if ((--l) == 0) |
||
187 | goto the_end; |
||
188 | } |
||
189 | if (s->ebuf < s->pbuf) { |
||
190 | av_log(NULL, AV_LOG_ERROR, "lzw overread\n"); |
||
191 | goto the_end; |
||
192 | } |
||
193 | c = lzw_get_code(s); |
||
194 | if (c == s->end_code) { |
||
195 | break; |
||
196 | } else if (c == s->clear_code) { |
||
197 | s->cursize = s->codesize + 1; |
||
198 | s->curmask = mask[s->cursize]; |
||
199 | s->slot = s->newcodes; |
||
200 | s->top_slot = 1 << s->cursize; |
||
201 | fc= oc= -1; |
||
202 | } else { |
||
203 | code = c; |
||
204 | if (code == s->slot && fc>=0) { |
||
205 | *sp++ = fc; |
||
206 | code = oc; |
||
207 | }else if(code >= s->slot) |
||
208 | break; |
||
209 | while (code >= s->newcodes) { |
||
210 | *sp++ = s->suffix[code]; |
||
211 | code = s->prefix[code]; |
||
212 | } |
||
213 | *sp++ = code; |
||
214 | if (s->slot < s->top_slot && oc>=0) { |
||
215 | s->suffix[s->slot] = code; |
||
216 | s->prefix[s->slot++] = oc; |
||
217 | } |
||
218 | fc = code; |
||
219 | oc = c; |
||
220 | if (s->slot >= s->top_slot - s->extra_slot) { |
||
221 | if (s->cursize < LZW_MAXBITS) { |
||
222 | s->top_slot <<= 1; |
||
223 | s->curmask = mask[++s->cursize]; |
||
224 | } |
||
225 | } |
||
226 | } |
||
227 | } |
||
228 | s->end_code = -1; |
||
229 | the_end: |
||
230 | s->sp = sp; |
||
231 | s->oc = oc; |
||
232 | s->fc = fc; |
||
233 | return len - l; |
||
234 | }=><=>>>><>>>><>><>>><>>><>>>>>>>> |