3 * Copyright (c) 2003 Fabrice Bellard
4 * Copyright (c) 2006 Konstantin Shishkov
6 * This file is part of FFmpeg.
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.
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.
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
25 * @brief LZW decoding routines
26 * @author Fabrice Bellard
27 * @author modified for use in TIFF by Konstantin Shishkov
31 #include "bytestream.h"
33 #include "libavutil/mem.h"
35 #define LZW_MAXBITS 12
36 #define LZW_SIZTABLE (1<<LZW_MAXBITS)
38 static const uint16_t mask
[17] =
40 0x0000, 0x0001, 0x0003, 0x0007,
41 0x000F, 0x001F, 0x003F, 0x007F,
42 0x00FF, 0x01FF, 0x03FF, 0x07FF,
43 0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF
51 int mode
; ///< Decoder mode
52 int cursize
; ///< The current code size
57 int newcodes
; ///< First available code
58 int top_slot
; ///< Highest code for current size
60 int slot
; ///< Last read code
63 uint8_t stack
[LZW_SIZTABLE
];
64 uint8_t suffix
[LZW_SIZTABLE
];
65 uint16_t prefix
[LZW_SIZTABLE
];
66 int bs
; ///< current buffer size for GIF
69 /* get one code from stream */
70 static int lzw_get_code(struct LZWState
* s
)
74 if(s
->mode
== FF_LZW_GIF
) {
75 while (s
->bbits
< s
->cursize
) {
77 s
->bs
= bytestream2_get_byte(&s
->gb
);
79 s
->bbuf
|= bytestream2_get_byte(&s
->gb
) << s
->bbits
;
84 s
->bbuf
>>= s
->cursize
;
86 while (s
->bbits
< s
->cursize
) {
87 s
->bbuf
= (s
->bbuf
<< 8) | bytestream2_get_byte(&s
->gb
);
90 c
= s
->bbuf
>> (s
->bbits
- s
->cursize
);
92 s
->bbits
-= s
->cursize
;
93 return c
& s
->curmask
;
96 void ff_lzw_decode_tail(LZWState
*p
)
98 struct LZWState
*s
= (struct LZWState
*)p
;
100 if(s
->mode
== FF_LZW_GIF
) {
101 while (s
->bs
> 0 && bytestream2_get_bytes_left(&s
->gb
)) {
102 bytestream2_skip(&s
->gb
, s
->bs
);
103 s
->bs
= bytestream2_get_byte(&s
->gb
);
106 bytestream2_skip(&s
->gb
, bytestream2_get_bytes_left(&s
->gb
));
109 av_cold
void ff_lzw_decode_open(LZWState
**p
)
111 *p
= av_mallocz(sizeof(struct LZWState
));
114 av_cold
void ff_lzw_decode_close(LZWState
**p
)
120 * Initialize LZW decoder
121 * @param p LZW context
122 * @param csize initial code size in bits
123 * @param buf input data
124 * @param buf_size input data size
125 * @param mode decoder working mode - either GIF or TIFF
127 int ff_lzw_decode_init(LZWState
*p
, int csize
, const uint8_t *buf
, int buf_size
, int mode
)
129 struct LZWState
*s
= (struct LZWState
*)p
;
131 if(csize
< 1 || csize
>= LZW_MAXBITS
)
134 bytestream2_init(&s
->gb
, buf
, buf_size
);
141 s
->cursize
= s
->codesize
+ 1;
142 s
->curmask
= mask
[s
->cursize
];
143 s
->top_slot
= 1 << s
->cursize
;
144 s
->clear_code
= 1 << s
->codesize
;
145 s
->end_code
= s
->clear_code
+ 1;
146 s
->slot
= s
->newcodes
= s
->clear_code
+ 2;
151 s
->extra_slot
= s
->mode
== FF_LZW_TIFF
;
156 * Decode given number of bytes
157 * NOTE: the algorithm here is inspired from the LZW GIF decoder
158 * written by Steven A. Bennett in 1987.
160 * @param p LZW context
161 * @param buf output buffer
162 * @param len number of bytes to decode
163 * @return number of bytes decoded
165 int ff_lzw_decode(LZWState
*p
, uint8_t *buf
, int len
){
166 int l
, c
, code
, oc
, fc
;
168 struct LZWState
*s
= (struct LZWState
*)p
;
179 while (sp
> s
->stack
) {
185 if (c
== s
->end_code
) {
187 } else if (c
== s
->clear_code
) {
188 s
->cursize
= s
->codesize
+ 1;
189 s
->curmask
= mask
[s
->cursize
];
190 s
->slot
= s
->newcodes
;
191 s
->top_slot
= 1 << s
->cursize
;
195 if (code
== s
->slot
&& fc
>=0) {
198 }else if(code
>= s
->slot
)
200 while (code
>= s
->newcodes
) {
201 *sp
++ = s
->suffix
[code
];
202 code
= s
->prefix
[code
];
205 if (s
->slot
< s
->top_slot
&& oc
>=0) {
206 s
->suffix
[s
->slot
] = code
;
207 s
->prefix
[s
->slot
++] = oc
;
211 if (s
->slot
>= s
->top_slot
- s
->extra_slot
) {
212 if (s
->cursize
< LZW_MAXBITS
) {
214 s
->curmask
= mask
[++s
->cursize
];