Mercurial > libavcodec.hg
annotate lzw.c @ 6043:823e6b273ea2 libavcodec
Document Motion_Est_IDs.
author | michael |
---|---|
date | Tue, 18 Dec 2007 19:40:08 +0000 |
parents | 59649ebd5ed8 |
children | dfdff1ca78a7 |
rev | line source |
---|---|
4080 | 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 lzw.c | |
25 * @brief LZW decoding routines | |
26 * @author Fabrice Bellard | |
27 * Modified for use in TIFF by Konstantin Shishkov | |
28 */ | |
29 | |
30 #include "avcodec.h" | |
31 #include "lzw.h" | |
32 | |
33 #define LZW_MAXBITS 12 | |
34 #define LZW_SIZTABLE (1<<LZW_MAXBITS) | |
35 | |
36 static const uint16_t mask[17] = | |
37 { | |
38 0x0000, 0x0001, 0x0003, 0x0007, | |
39 0x000F, 0x001F, 0x003F, 0x007F, | |
40 0x00FF, 0x01FF, 0x03FF, 0x07FF, | |
41 0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF | |
42 }; | |
43 | |
44 struct LZWState { | |
45 uint8_t *pbuf, *ebuf; | |
46 int bbits; | |
47 unsigned int bbuf; | |
48 | |
49 int mode; ///< Decoder mode | |
50 int cursize; ///< The current code size | |
51 int curmask; | |
52 int codesize; | |
53 int clear_code; | |
54 int end_code; | |
55 int newcodes; ///< First available code | |
56 int top_slot; ///< Highest code for current size | |
4725 | 57 int extra_slot; |
4080 | 58 int slot; ///< Last read code |
59 int fc, oc; | |
60 uint8_t *sp; | |
61 uint8_t stack[LZW_SIZTABLE]; | |
62 uint8_t suffix[LZW_SIZTABLE]; | |
63 uint16_t prefix[LZW_SIZTABLE]; | |
64 int bs; ///< current buffer size for GIF | |
65 }; | |
66 | |
67 /* get one code from stream */ | |
68 static int lzw_get_code(struct LZWState * s) | |
69 { | |
4727 | 70 int c; |
4080 | 71 |
72 if(s->mode == FF_LZW_GIF) { | |
73 while (s->bbits < s->cursize) { | |
74 if (!s->bs) { | |
4727 | 75 s->bs = *s->pbuf++; |
4080 | 76 } |
77 s->bbuf |= (*s->pbuf++) << s->bbits; | |
78 s->bbits += 8; | |
79 s->bs--; | |
80 } | |
4736 | 81 c = s->bbuf; |
4716 | 82 s->bbuf >>= s->cursize; |
4080 | 83 } else { // TIFF |
84 while (s->bbits < s->cursize) { | |
85 s->bbuf = (s->bbuf << 8) | (*s->pbuf++); | |
86 s->bbits += 8; | |
87 } | |
4736 | 88 c = s->bbuf >> (s->bbits - s->cursize); |
4080 | 89 } |
90 s->bbits -= s->cursize; | |
4736 | 91 return c & s->curmask; |
4080 | 92 } |
93 | |
94 uint8_t* ff_lzw_cur_ptr(LZWState *p) | |
95 { | |
96 return ((struct LZWState*)p)->pbuf; | |
97 } | |
98 | |
99 void ff_lzw_decode_tail(LZWState *p) | |
100 { | |
101 struct LZWState *s = (struct LZWState *)p; | |
4728
5db8e9e8f71d
move eob_reached logic into ff_lzw_decode_tail() which simplifies the code, avoids some checks in the innermost loop and also gets rid of the controversal break while hopefully retaining the last byte in a valid bytestream, invalid bytestreams still can have very significant overread
michael
parents:
4727
diff
changeset
|
102 |
5db8e9e8f71d
move eob_reached logic into ff_lzw_decode_tail() which simplifies the code, avoids some checks in the innermost loop and also gets rid of the controversal break while hopefully retaining the last byte in a valid bytestream, invalid bytestreams still can have very significant overread
michael
parents:
4727
diff
changeset
|
103 if(s->mode == FF_LZW_GIF) { |
5db8e9e8f71d
move eob_reached logic into ff_lzw_decode_tail() which simplifies the code, avoids some checks in the innermost loop and also gets rid of the controversal break while hopefully retaining the last byte in a valid bytestream, invalid bytestreams still can have very significant overread
michael
parents:
4727
diff
changeset
|
104 while(s->pbuf < s->ebuf && s->bs>0){ |
5db8e9e8f71d
move eob_reached logic into ff_lzw_decode_tail() which simplifies the code, avoids some checks in the innermost loop and also gets rid of the controversal break while hopefully retaining the last byte in a valid bytestream, invalid bytestreams still can have very significant overread
michael
parents:
4727
diff
changeset
|
105 s->pbuf += s->bs; |
5db8e9e8f71d
move eob_reached logic into ff_lzw_decode_tail() which simplifies the code, avoids some checks in the innermost loop and also gets rid of the controversal break while hopefully retaining the last byte in a valid bytestream, invalid bytestreams still can have very significant overread
michael
parents:
4727
diff
changeset
|
106 s->bs = *s->pbuf++; |
5db8e9e8f71d
move eob_reached logic into ff_lzw_decode_tail() which simplifies the code, avoids some checks in the innermost loop and also gets rid of the controversal break while hopefully retaining the last byte in a valid bytestream, invalid bytestreams still can have very significant overread
michael
parents:
4727
diff
changeset
|
107 } |
5db8e9e8f71d
move eob_reached logic into ff_lzw_decode_tail() which simplifies the code, avoids some checks in the innermost loop and also gets rid of the controversal break while hopefully retaining the last byte in a valid bytestream, invalid bytestreams still can have very significant overread
michael
parents:
4727
diff
changeset
|
108 }else |
5db8e9e8f71d
move eob_reached logic into ff_lzw_decode_tail() which simplifies the code, avoids some checks in the innermost loop and also gets rid of the controversal break while hopefully retaining the last byte in a valid bytestream, invalid bytestreams still can have very significant overread
michael
parents:
4727
diff
changeset
|
109 s->pbuf= s->ebuf; |
4080 | 110 } |
111 | |
112 void ff_lzw_decode_open(LZWState **p) | |
113 { | |
114 *p = av_mallocz(sizeof(struct LZWState)); | |
115 } | |
116 | |
117 void ff_lzw_decode_close(LZWState **p) | |
118 { | |
119 av_freep(p); | |
120 } | |
121 | |
122 /** | |
123 * Initialize LZW decoder | |
124 * @param s LZW context | |
125 * @param csize initial code size in bits | |
126 * @param buf input data | |
127 * @param buf_size input data size | |
128 * @param mode decoder working mode - either GIF or TIFF | |
129 */ | |
130 int ff_lzw_decode_init(LZWState *p, int csize, uint8_t *buf, int buf_size, int mode) | |
131 { | |
132 struct LZWState *s = (struct LZWState *)p; | |
133 | |
134 if(csize < 1 || csize > LZW_MAXBITS) | |
135 return -1; | |
136 /* read buffer */ | |
137 s->pbuf = buf; | |
138 s->ebuf = s->pbuf + buf_size; | |
139 s->bbuf = 0; | |
140 s->bbits = 0; | |
141 s->bs = 0; | |
142 | |
143 /* decoder */ | |
144 s->codesize = csize; | |
145 s->cursize = s->codesize + 1; | |
146 s->curmask = mask[s->cursize]; | |
147 s->top_slot = 1 << s->cursize; | |
148 s->clear_code = 1 << s->codesize; | |
149 s->end_code = s->clear_code + 1; | |
150 s->slot = s->newcodes = s->clear_code + 2; | |
4732 | 151 s->oc = s->fc = -1; |
4080 | 152 s->sp = s->stack; |
153 | |
154 s->mode = mode; | |
4735 | 155 s->extra_slot = s->mode == FF_LZW_TIFF; |
4080 | 156 return 0; |
157 } | |
158 | |
159 /** | |
160 * Decode given number of bytes | |
161 * NOTE: the algorithm here is inspired from the LZW GIF decoder | |
162 * written by Steven A. Bennett in 1987. | |
163 * | |
164 * @param s LZW context | |
165 * @param buf output buffer | |
166 * @param len number of bytes to decode | |
167 * @return number of bytes decoded | |
168 */ | |
169 int ff_lzw_decode(LZWState *p, uint8_t *buf, int len){ | |
170 int l, c, code, oc, fc; | |
171 uint8_t *sp; | |
172 struct LZWState *s = (struct LZWState *)p; | |
173 | |
174 if (s->end_code < 0) | |
175 return 0; | |
176 | |
177 l = len; | |
178 sp = s->sp; | |
179 oc = s->oc; | |
180 fc = s->fc; | |
181 | |
182 for (;;) { | |
4726 | 183 while (sp > s->stack) { |
184 *buf++ = *(--sp); | |
185 if ((--l) == 0) | |
186 goto the_end; | |
187 } | |
4080 | 188 c = lzw_get_code(s); |
189 if (c == s->end_code) { | |
190 break; | |
191 } else if (c == s->clear_code) { | |
192 s->cursize = s->codesize + 1; | |
193 s->curmask = mask[s->cursize]; | |
194 s->slot = s->newcodes; | |
195 s->top_slot = 1 << s->cursize; | |
4732 | 196 fc= oc= -1; |
4080 | 197 } else { |
198 code = c; | |
4733
507d08212e36
check input validity, this prevents a few variables from reachin odd values which might have lead to out of array writes and thus might have been exploitable
michael
parents:
4732
diff
changeset
|
199 if (code == s->slot && fc>=0) { |
4080 | 200 *sp++ = fc; |
201 code = oc; | |
4733
507d08212e36
check input validity, this prevents a few variables from reachin odd values which might have lead to out of array writes and thus might have been exploitable
michael
parents:
4732
diff
changeset
|
202 }else if(code >= s->slot) |
507d08212e36
check input validity, this prevents a few variables from reachin odd values which might have lead to out of array writes and thus might have been exploitable
michael
parents:
4732
diff
changeset
|
203 break; |
4080 | 204 while (code >= s->newcodes) { |
205 *sp++ = s->suffix[code]; | |
206 code = s->prefix[code]; | |
207 } | |
208 *sp++ = code; | |
4732 | 209 if (s->slot < s->top_slot && oc>=0) { |
210 s->suffix[s->slot] = code; | |
4080 | 211 s->prefix[s->slot++] = oc; |
212 } | |
4732 | 213 fc = code; |
214 oc = c; | |
4725 | 215 if (s->slot >= s->top_slot - s->extra_slot) { |
4080 | 216 if (s->cursize < LZW_MAXBITS) { |
217 s->top_slot <<= 1; | |
218 s->curmask = mask[++s->cursize]; | |
219 } | |
220 } | |
221 } | |
222 } | |
4733
507d08212e36
check input validity, this prevents a few variables from reachin odd values which might have lead to out of array writes and thus might have been exploitable
michael
parents:
4732
diff
changeset
|
223 s->end_code = -1; |
4080 | 224 the_end: |
225 s->sp = sp; | |
226 s->oc = oc; | |
227 s->fc = fc; | |
228 return len - l; | |
229 } |