Commit | Line | Data |
---|---|---|
2ba45a60 DM |
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 | } |