016714021c053283033bbf402bfea296ee70339a
[libav.git] / libavcodec / lzw.c
1 /*
2 * LZW decoder
3 * Copyright (c) 2003 Fabrice Bellard
4 * Copyright (c) 2006 Konstantin Shishkov
5 *
6 * This file is part of Libav.
7 *
8 * Libav 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 * Libav 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 Libav; 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<<LZW_MAXBITS)
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 *buf_start, *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 int ff_lzw_size_read(LZWState *p)
96 {
97 struct LZWState *s = p;
98 return s->pbuf - s->buf_start;
99 }
100
101 void ff_lzw_decode_tail(LZWState *p)
102 {
103 struct LZWState *s = (struct LZWState *)p;
104
105 if(s->mode == FF_LZW_GIF) {
106 while (s->bs > 0) {
107 if (s->bs >= s->ebuf - s->pbuf) {
108 s->pbuf = s->ebuf;
109 break;
110 } else {
111 s->pbuf += s->bs;
112 s->bs = *s->pbuf++;
113 }
114 }
115 }else
116 s->pbuf= s->ebuf;
117 }
118
119 av_cold void ff_lzw_decode_open(LZWState **p)
120 {
121 *p = av_mallocz(sizeof(struct LZWState));
122 }
123
124 av_cold void ff_lzw_decode_close(LZWState **p)
125 {
126 av_freep(p);
127 }
128
129 /**
130 * Initialize LZW decoder
131 * @param p LZW context
132 * @param csize initial code size in bits
133 * @param buf input data
134 * @param buf_size input data size
135 * @param mode decoder working mode - either GIF or TIFF
136 */
137 int ff_lzw_decode_init(LZWState *p, int csize, const uint8_t *buf, int buf_size, int mode)
138 {
139 struct LZWState *s = (struct LZWState *)p;
140
141 if(csize < 1 || csize >= LZW_MAXBITS)
142 return -1;
143 /* read buffer */
144 s->pbuf = buf;
145 s->ebuf = s->pbuf + buf_size;
146 s->bbuf = 0;
147 s->bbits = 0;
148 s->bs = 0;
149
150 /* decoder */
151 s->codesize = csize;
152 s->cursize = s->codesize + 1;
153 s->curmask = mask[s->cursize];
154 s->top_slot = 1 << s->cursize;
155 s->clear_code = 1 << s->codesize;
156 s->end_code = s->clear_code + 1;
157 s->slot = s->newcodes = s->clear_code + 2;
158 s->oc = s->fc = -1;
159 s->sp = s->stack;
160
161 s->mode = mode;
162 s->extra_slot = s->mode == FF_LZW_TIFF;
163 return 0;
164 }
165
166 /**
167 * Decode given number of bytes
168 * NOTE: the algorithm here is inspired from the LZW GIF decoder
169 * written by Steven A. Bennett in 1987.
170 *
171 * @param p LZW context
172 * @param buf output buffer
173 * @param len number of bytes to decode
174 * @return number of bytes decoded
175 */
176 int ff_lzw_decode(LZWState *p, uint8_t *buf, int len){
177 int l, c, code, oc, fc;
178 uint8_t *sp;
179 struct LZWState *s = (struct LZWState *)p;
180
181 if (s->end_code < 0)
182 return 0;
183
184 l = len;
185 sp = s->sp;
186 oc = s->oc;
187 fc = s->fc;
188
189 for (;;) {
190 while (sp > s->stack) {
191 *buf++ = *(--sp);
192 if ((--l) == 0)
193 goto the_end;
194 }
195 c = lzw_get_code(s);
196 if (c == s->end_code) {
197 break;
198 } else if (c == s->clear_code) {
199 s->cursize = s->codesize + 1;
200 s->curmask = mask[s->cursize];
201 s->slot = s->newcodes;
202 s->top_slot = 1 << s->cursize;
203 fc= oc= -1;
204 } else {
205 code = c;
206 if (code == s->slot && fc>=0) {
207 *sp++ = fc;
208 code = oc;
209 }else if(code >= s->slot)
210 break;
211 while (code >= s->newcodes) {
212 *sp++ = s->suffix[code];
213 code = s->prefix[code];
214 }
215 *sp++ = code;
216 if (s->slot < s->top_slot && oc>=0) {
217 s->suffix[s->slot] = code;
218 s->prefix[s->slot++] = oc;
219 }
220 fc = code;
221 oc = c;
222 if (s->slot >= s->top_slot - s->extra_slot) {
223 if (s->cursize < LZW_MAXBITS) {
224 s->top_slot <<= 1;
225 s->curmask = mask[++s->cursize];
226 }
227 }
228 }
229 }
230 s->end_code = -1;
231 the_end:
232 s->sp = sp;
233 s->oc = oc;
234 s->fc = fc;
235 return len - l;
236 }