1 |
|
|
/* |
2 |
|
|
* LZW encoder |
3 |
|
|
* Copyright (c) 2007 Bartlomiej Wolowiec |
4 |
|
|
* |
5 |
|
|
* This file is part of FFmpeg. |
6 |
|
|
* |
7 |
|
|
* FFmpeg is free software; you can redistribute it and/or |
8 |
|
|
* modify it under the terms of the GNU Lesser General Public |
9 |
|
|
* License as published by the Free Software Foundation; either |
10 |
|
|
* version 2.1 of the License, or (at your option) any later version. |
11 |
|
|
* |
12 |
|
|
* FFmpeg is distributed in the hope that it will be useful, |
13 |
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of |
14 |
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
15 |
|
|
* Lesser General Public License for more details. |
16 |
|
|
* |
17 |
|
|
* You should have received a copy of the GNU Lesser General Public |
18 |
|
|
* License along with FFmpeg; if not, write to the Free Software |
19 |
|
|
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
20 |
|
|
*/ |
21 |
|
|
|
22 |
|
|
/** |
23 |
|
|
* @file |
24 |
|
|
* LZW encoder |
25 |
|
|
* @author Bartlomiej Wolowiec |
26 |
|
|
*/ |
27 |
|
|
|
28 |
|
|
#include "avcodec.h" |
29 |
|
|
#include "lzw.h" |
30 |
|
|
#include "mathops.h" |
31 |
|
|
#include "put_bits.h" |
32 |
|
|
|
33 |
|
|
#define LZW_MAXBITS 12 |
34 |
|
|
#define LZW_SIZTABLE (1<<LZW_MAXBITS) |
35 |
|
|
#define LZW_HASH_SIZE 16411 |
36 |
|
|
#define LZW_HASH_SHIFT 6 |
37 |
|
|
|
38 |
|
|
#define LZW_PREFIX_EMPTY -1 |
39 |
|
|
#define LZW_PREFIX_FREE -2 |
40 |
|
|
|
41 |
|
|
/** One code in hash table */ |
42 |
|
|
typedef struct Code{ |
43 |
|
|
/// Hash code of prefix, LZW_PREFIX_EMPTY if empty prefix, or LZW_PREFIX_FREE if no code |
44 |
|
|
int hash_prefix; |
45 |
|
|
int code; ///< LZW code |
46 |
|
|
uint8_t suffix; ///< Last character in code block |
47 |
|
|
}Code; |
48 |
|
|
|
49 |
|
|
/** LZW encode state */ |
50 |
|
|
typedef struct LZWEncodeState { |
51 |
|
|
int clear_code; ///< Value of clear code |
52 |
|
|
int end_code; ///< Value of end code |
53 |
|
|
Code tab[LZW_HASH_SIZE]; ///< Hash table |
54 |
|
|
int tabsize; ///< Number of values in hash table |
55 |
|
|
int bits; ///< Actual bits code |
56 |
|
|
int bufsize; ///< Size of output buffer |
57 |
|
|
PutBitContext pb; ///< Put bit context for output |
58 |
|
|
int maxbits; ///< Max bits code |
59 |
|
|
int maxcode; ///< Max value of code |
60 |
|
|
int output_bytes; ///< Number of written bytes |
61 |
|
|
int last_code; ///< Value of last output code or LZW_PREFIX_EMPTY |
62 |
|
|
enum FF_LZW_MODES mode; ///< TIFF or GIF |
63 |
|
|
int little_endian; ///< GIF is LE while TIFF is BE |
64 |
|
|
}LZWEncodeState; |
65 |
|
|
|
66 |
|
|
|
67 |
|
|
const int ff_lzw_encode_state_size = sizeof(LZWEncodeState); |
68 |
|
|
|
69 |
|
|
/** |
70 |
|
|
* Hash function adding character |
71 |
|
|
* @param head LZW code for prefix |
72 |
|
|
* @param add Character to add |
73 |
|
|
* @return New hash value |
74 |
|
|
*/ |
75 |
|
5529886 |
static inline int hash(int head, const int add) |
76 |
|
|
{ |
77 |
|
5529886 |
head ^= (add << LZW_HASH_SHIFT); |
78 |
✗✓ |
5529886 |
if (head >= LZW_HASH_SIZE) |
79 |
|
|
head -= LZW_HASH_SIZE; |
80 |
|
|
av_assert2(head >= 0 && head < LZW_HASH_SIZE); |
81 |
|
5529886 |
return head; |
82 |
|
|
} |
83 |
|
|
|
84 |
|
|
/** |
85 |
|
|
* Hash function calculates next hash value |
86 |
|
|
* @param head Actual hash code |
87 |
|
|
* @param offset Offset calculated by hashOffset |
88 |
|
|
* @return New hash value |
89 |
|
|
*/ |
90 |
|
1409932 |
static inline int hashNext(int head, const int offset) |
91 |
|
|
{ |
92 |
|
1409932 |
head -= offset; |
93 |
✓✓ |
1409932 |
if(head < 0) |
94 |
|
1118268 |
head += LZW_HASH_SIZE; |
95 |
|
1409932 |
return head; |
96 |
|
|
} |
97 |
|
|
|
98 |
|
|
/** |
99 |
|
|
* Hash function calculates hash offset |
100 |
|
|
* @param head Actual hash code |
101 |
|
|
* @return Hash offset |
102 |
|
|
*/ |
103 |
|
3541685 |
static inline int hashOffset(const int head) |
104 |
|
|
{ |
105 |
✓✓ |
3541685 |
return head ? LZW_HASH_SIZE - head : 1; |
106 |
|
|
} |
107 |
|
|
|
108 |
|
|
/** |
109 |
|
|
* Write one code to stream |
110 |
|
|
* @param s LZW state |
111 |
|
|
* @param c code to write |
112 |
|
|
*/ |
113 |
|
1630012 |
static inline void writeCode(LZWEncodeState * s, int c) |
114 |
|
|
{ |
115 |
|
|
av_assert2(0 <= c && c < 1 << s->bits); |
116 |
✓✗ |
1630012 |
if (s->little_endian) |
117 |
|
1630012 |
put_bits_le(&s->pb, s->bits, c); |
118 |
|
|
else |
119 |
|
|
put_bits(&s->pb, s->bits, c); |
120 |
|
1630012 |
} |
121 |
|
|
|
122 |
|
|
|
123 |
|
|
/** |
124 |
|
|
* Find LZW code for block |
125 |
|
|
* @param s LZW state |
126 |
|
|
* @param c Last character in block |
127 |
|
|
* @param hash_prefix LZW code for prefix |
128 |
|
|
* @return LZW code for block or -1 if not found in table |
129 |
|
|
*/ |
130 |
|
3541685 |
static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix) |
131 |
|
|
{ |
132 |
|
3541685 |
int h = hash(FFMAX(hash_prefix, 0), c); |
133 |
|
3541685 |
int hash_offset = hashOffset(h); |
134 |
|
|
|
135 |
✓✓ |
4951617 |
while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) { |
136 |
✓✓ |
3325144 |
if ((s->tab[h].suffix == c) |
137 |
✓✓ |
1965850 |
&& (s->tab[h].hash_prefix == hash_prefix)) |
138 |
|
1915212 |
return h; |
139 |
|
1409932 |
h = hashNext(h, hash_offset); |
140 |
|
|
} |
141 |
|
|
|
142 |
|
1626473 |
return h; |
143 |
|
|
} |
144 |
|
|
|
145 |
|
|
/** |
146 |
|
|
* Add block to LZW code table |
147 |
|
|
* @param s LZW state |
148 |
|
|
* @param c Last character in block |
149 |
|
|
* @param hash_prefix LZW code for prefix |
150 |
|
|
* @param hash_code LZW code for bytes block |
151 |
|
|
*/ |
152 |
|
1626473 |
static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code) |
153 |
|
|
{ |
154 |
|
1626473 |
s->tab[hash_code].code = s->tabsize; |
155 |
|
1626473 |
s->tab[hash_code].suffix = c; |
156 |
|
1626473 |
s->tab[hash_code].hash_prefix = hash_prefix; |
157 |
|
|
|
158 |
|
1626473 |
s->tabsize++; |
159 |
|
|
|
160 |
✓✓ |
1626473 |
if (s->tabsize >= (1 << s->bits) + (s->mode == FF_LZW_GIF)) |
161 |
|
1324 |
s->bits++; |
162 |
|
1626473 |
} |
163 |
|
|
|
164 |
|
|
/** |
165 |
|
|
* Clear LZW code table |
166 |
|
|
* @param s LZW state |
167 |
|
|
*/ |
168 |
|
1413 |
static void clearTable(LZWEncodeState * s) |
169 |
|
|
{ |
170 |
|
|
int i, h; |
171 |
|
|
|
172 |
|
1413 |
writeCode(s, s->clear_code); |
173 |
|
1413 |
s->bits = 9; |
174 |
✓✓ |
23190156 |
for (i = 0; i < LZW_HASH_SIZE; i++) { |
175 |
|
23188743 |
s->tab[i].hash_prefix = LZW_PREFIX_FREE; |
176 |
|
|
} |
177 |
✓✓ |
363141 |
for (i = 0; i < 256; i++) { |
178 |
|
361728 |
h = hash(0, i); |
179 |
|
361728 |
s->tab[h].code = i; |
180 |
|
361728 |
s->tab[h].suffix = i; |
181 |
|
361728 |
s->tab[h].hash_prefix = LZW_PREFIX_EMPTY; |
182 |
|
|
} |
183 |
|
1413 |
s->tabsize = 258; |
184 |
|
1413 |
} |
185 |
|
|
|
186 |
|
|
/** |
187 |
|
|
* Calculate number of bytes written |
188 |
|
|
* @param s LZW encode state |
189 |
|
|
* @return Number of bytes written |
190 |
|
|
*/ |
191 |
|
35140 |
static int writtenBytes(LZWEncodeState *s){ |
192 |
|
35140 |
int ret = put_bits_count(&s->pb) >> 3; |
193 |
|
35140 |
ret -= s->output_bytes; |
194 |
|
35140 |
s->output_bytes += ret; |
195 |
|
35140 |
return ret; |
196 |
|
|
} |
197 |
|
|
|
198 |
|
|
/** |
199 |
|
|
* Initialize LZW encoder. Please set s->clear_code, s->end_code and s->maxbits before run. |
200 |
|
|
* @param s LZW state |
201 |
|
|
* @param outbuf Output buffer |
202 |
|
|
* @param outsize Size of output buffer |
203 |
|
|
* @param maxbits Maximum length of code |
204 |
|
|
*/ |
205 |
|
1063 |
void ff_lzw_encode_init(LZWEncodeState *s, uint8_t *outbuf, int outsize, |
206 |
|
|
int maxbits, enum FF_LZW_MODES mode, int little_endian) |
207 |
|
|
{ |
208 |
|
1063 |
s->clear_code = 256; |
209 |
|
1063 |
s->end_code = 257; |
210 |
|
1063 |
s->maxbits = maxbits; |
211 |
|
1063 |
init_put_bits(&s->pb, outbuf, outsize); |
212 |
|
1063 |
s->bufsize = outsize; |
213 |
✓✗✗✓
|
1063 |
av_assert0(s->maxbits >= 9 && s->maxbits <= LZW_MAXBITS); |
214 |
|
1063 |
s->maxcode = 1 << s->maxbits; |
215 |
|
1063 |
s->output_bytes = 0; |
216 |
|
1063 |
s->last_code = LZW_PREFIX_EMPTY; |
217 |
|
1063 |
s->bits = 9; |
218 |
|
1063 |
s->mode = mode; |
219 |
|
1063 |
s->little_endian = little_endian; |
220 |
|
1063 |
} |
221 |
|
|
|
222 |
|
|
/** |
223 |
|
|
* LZW main compress function |
224 |
|
|
* @param s LZW state |
225 |
|
|
* @param inbuf Input buffer |
226 |
|
|
* @param insize Size of input buffer |
227 |
|
|
* @return Number of bytes written or -1 on error |
228 |
|
|
*/ |
229 |
|
34077 |
int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize) |
230 |
|
|
{ |
231 |
|
|
int i; |
232 |
|
|
|
233 |
✗✓ |
34077 |
if(insize * 3 > (s->bufsize - s->output_bytes) * 2){ |
234 |
|
|
return -1; |
235 |
|
|
} |
236 |
|
|
|
237 |
✓✓ |
34077 |
if (s->last_code == LZW_PREFIX_EMPTY) |
238 |
|
1063 |
clearTable(s); |
239 |
|
|
|
240 |
✓✓ |
3575762 |
for (i = 0; i < insize; i++) { |
241 |
|
3541685 |
uint8_t c = *inbuf++; |
242 |
|
3541685 |
int code = findCode(s, c, s->last_code); |
243 |
✓✓ |
3541685 |
if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) { |
244 |
|
1626473 |
writeCode(s, s->last_code); |
245 |
|
1626473 |
addCode(s, c, s->last_code, code); |
246 |
|
1626473 |
code= hash(0, c); |
247 |
|
|
} |
248 |
|
3541685 |
s->last_code = s->tab[code].code; |
249 |
✓✓ |
3541685 |
if (s->tabsize >= s->maxcode - 1) { |
250 |
|
350 |
clearTable(s); |
251 |
|
|
} |
252 |
|
|
} |
253 |
|
|
|
254 |
|
34077 |
return writtenBytes(s); |
255 |
|
|
} |
256 |
|
|
|
257 |
|
|
/** |
258 |
|
|
* Write end code and flush bitstream |
259 |
|
|
* @param s LZW state |
260 |
|
|
* @return Number of bytes written or -1 on error |
261 |
|
|
*/ |
262 |
|
1063 |
int ff_lzw_encode_flush(LZWEncodeState *s) |
263 |
|
|
{ |
264 |
✓✗ |
1063 |
if (s->last_code != -1) |
265 |
|
1063 |
writeCode(s, s->last_code); |
266 |
|
1063 |
writeCode(s, s->end_code); |
267 |
✓✗ |
1063 |
if (s->little_endian) { |
268 |
✓✗ |
1063 |
if (s->mode == FF_LZW_GIF) |
269 |
|
1063 |
put_bits_le(&s->pb, 1, 0); |
270 |
|
|
|
271 |
|
1063 |
flush_put_bits_le(&s->pb); |
272 |
|
|
} else { |
273 |
|
|
if (s->mode == FF_LZW_GIF) |
274 |
|
|
put_bits(&s->pb, 1, 0); |
275 |
|
|
|
276 |
|
|
flush_put_bits(&s->pb); |
277 |
|
|
} |
278 |
|
1063 |
s->last_code = -1; |
279 |
|
|
|
280 |
|
1063 |
return writtenBytes(s); |
281 |
|
|
} |