blob: 03080ee58729325d5defca45ea37b5ac79cc236e
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 | void (*put_bits)(PutBitContext *, int, unsigned); ///< 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 | static inline int hash(int head, const int add) |
76 | { |
77 | head ^= (add << LZW_HASH_SHIFT); |
78 | if (head >= LZW_HASH_SIZE) |
79 | head -= LZW_HASH_SIZE; |
80 | av_assert2(head >= 0 && head < LZW_HASH_SIZE); |
81 | 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 | static inline int hashNext(int head, const int offset) |
91 | { |
92 | head -= offset; |
93 | if(head < 0) |
94 | head += LZW_HASH_SIZE; |
95 | return head; |
96 | } |
97 | |
98 | /** |
99 | * Hash function calculates hash offset |
100 | * @param head Actual hash code |
101 | * @return Hash offset |
102 | */ |
103 | static inline int hashOffset(const int head) |
104 | { |
105 | 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 | static inline void writeCode(LZWEncodeState * s, int c) |
114 | { |
115 | av_assert2(0 <= c && c < 1 << s->bits); |
116 | s->put_bits(&s->pb, s->bits, c); |
117 | } |
118 | |
119 | |
120 | /** |
121 | * Find LZW code for block |
122 | * @param s LZW state |
123 | * @param c Last character in block |
124 | * @param hash_prefix LZW code for prefix |
125 | * @return LZW code for block or -1 if not found in table |
126 | */ |
127 | static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix) |
128 | { |
129 | int h = hash(FFMAX(hash_prefix, 0), c); |
130 | int hash_offset = hashOffset(h); |
131 | |
132 | while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) { |
133 | if ((s->tab[h].suffix == c) |
134 | && (s->tab[h].hash_prefix == hash_prefix)) |
135 | return h; |
136 | h = hashNext(h, hash_offset); |
137 | } |
138 | |
139 | return h; |
140 | } |
141 | |
142 | /** |
143 | * Add block to LZW code table |
144 | * @param s LZW state |
145 | * @param c Last character in block |
146 | * @param hash_prefix LZW code for prefix |
147 | * @param hash_code LZW code for bytes block |
148 | */ |
149 | static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code) |
150 | { |
151 | s->tab[hash_code].code = s->tabsize; |
152 | s->tab[hash_code].suffix = c; |
153 | s->tab[hash_code].hash_prefix = hash_prefix; |
154 | |
155 | s->tabsize++; |
156 | |
157 | if (s->tabsize >= (1 << s->bits) + (s->mode == FF_LZW_GIF)) |
158 | s->bits++; |
159 | } |
160 | |
161 | /** |
162 | * Clear LZW code table |
163 | * @param s LZW state |
164 | */ |
165 | static void clearTable(LZWEncodeState * s) |
166 | { |
167 | int i, h; |
168 | |
169 | writeCode(s, s->clear_code); |
170 | s->bits = 9; |
171 | for (i = 0; i < LZW_HASH_SIZE; i++) { |
172 | s->tab[i].hash_prefix = LZW_PREFIX_FREE; |
173 | } |
174 | for (i = 0; i < 256; i++) { |
175 | h = hash(0, i); |
176 | s->tab[h].code = i; |
177 | s->tab[h].suffix = i; |
178 | s->tab[h].hash_prefix = LZW_PREFIX_EMPTY; |
179 | } |
180 | s->tabsize = 258; |
181 | } |
182 | |
183 | /** |
184 | * Calculate number of bytes written |
185 | * @param s LZW encode state |
186 | * @return Number of bytes written |
187 | */ |
188 | static int writtenBytes(LZWEncodeState *s){ |
189 | int ret = put_bits_count(&s->pb) >> 3; |
190 | ret -= s->output_bytes; |
191 | s->output_bytes += ret; |
192 | return ret; |
193 | } |
194 | |
195 | /** |
196 | * Initialize LZW encoder. Please set s->clear_code, s->end_code and s->maxbits before run. |
197 | * @param s LZW state |
198 | * @param outbuf Output buffer |
199 | * @param outsize Size of output buffer |
200 | * @param maxbits Maximum length of code |
201 | */ |
202 | void ff_lzw_encode_init(LZWEncodeState *s, uint8_t *outbuf, int outsize, |
203 | int maxbits, enum FF_LZW_MODES mode, |
204 | void (*lzw_put_bits)(PutBitContext *, int, unsigned)) |
205 | { |
206 | s->clear_code = 256; |
207 | s->end_code = 257; |
208 | s->maxbits = maxbits; |
209 | init_put_bits(&s->pb, outbuf, outsize); |
210 | s->bufsize = outsize; |
211 | av_assert0(s->maxbits >= 9 && s->maxbits <= LZW_MAXBITS); |
212 | s->maxcode = 1 << s->maxbits; |
213 | s->output_bytes = 0; |
214 | s->last_code = LZW_PREFIX_EMPTY; |
215 | s->bits = 9; |
216 | s->mode = mode; |
217 | s->put_bits = lzw_put_bits; |
218 | } |
219 | |
220 | /** |
221 | * LZW main compress function |
222 | * @param s LZW state |
223 | * @param inbuf Input buffer |
224 | * @param insize Size of input buffer |
225 | * @return Number of bytes written or -1 on error |
226 | */ |
227 | int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize) |
228 | { |
229 | int i; |
230 | |
231 | if(insize * 3 > (s->bufsize - s->output_bytes) * 2){ |
232 | return -1; |
233 | } |
234 | |
235 | if (s->last_code == LZW_PREFIX_EMPTY) |
236 | clearTable(s); |
237 | |
238 | for (i = 0; i < insize; i++) { |
239 | uint8_t c = *inbuf++; |
240 | int code = findCode(s, c, s->last_code); |
241 | if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) { |
242 | writeCode(s, s->last_code); |
243 | addCode(s, c, s->last_code, code); |
244 | code= hash(0, c); |
245 | } |
246 | s->last_code = s->tab[code].code; |
247 | if (s->tabsize >= s->maxcode - 1) { |
248 | clearTable(s); |
249 | } |
250 | } |
251 | |
252 | return writtenBytes(s); |
253 | } |
254 | |
255 | /** |
256 | * Write end code and flush bitstream |
257 | * @param s LZW state |
258 | * @return Number of bytes written or -1 on error |
259 | */ |
260 | int ff_lzw_encode_flush(LZWEncodeState *s, |
261 | void (*lzw_flush_put_bits)(PutBitContext *)) |
262 | { |
263 | if (s->last_code != -1) |
264 | writeCode(s, s->last_code); |
265 | writeCode(s, s->end_code); |
266 | if (s->mode == FF_LZW_GIF) |
267 | s->put_bits(&s->pb, 1, 0); |
268 | |
269 | lzw_flush_put_bits(&s->pb); |
270 | s->last_code = -1; |
271 | |
272 | return writtenBytes(s); |
273 | } |
274 |