Mercurial > libavcodec.hg
comparison lzwenc.c @ 4798:c68b9a261f79 libavcodec
LZW encoder by Bartlomiej Wolowiec b.wolowiec students mimuw edu pl
author | michael |
---|---|
date | Sat, 07 Apr 2007 15:10:22 +0000 |
parents | |
children | 4a7e1f5cdc7a |
comparison
equal
deleted
inserted
replaced
4797:12279b61177b | 4798:c68b9a261f79 |
---|---|
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 * LZW encoder | |
24 * @file lzwenc.c | |
25 * @author Bartlomiej Wolowiec | |
26 */ | |
27 | |
28 #include "avcodec.h" | |
29 #include "bitstream.h" | |
30 #include "lzw.h" | |
31 | |
32 #define LZW_MAXBITS 12 | |
33 #define LZW_SIZTABLE (1<<LZW_MAXBITS) | |
34 #define LZW_HASH_SIZE 16411 | |
35 #define LZW_HASH_SHIFT 6 | |
36 | |
37 #define LZW_PREFIX_EMPTY -1 | |
38 #define LZW_PREFIX_FREE -2 | |
39 | |
40 /** One code in hash table */ | |
41 typedef struct Code{ | |
42 /// Hash code of prefix, LZW_PREFIX_EMPTY if empty prefix, or LZW_PREFIX_FREE if no code | |
43 int hash_prefix; | |
44 int code; ///< LZW code | |
45 uint8_t suffix; ///< Last character in code block | |
46 }Code; | |
47 | |
48 /** LZW encode state */ | |
49 typedef struct LZWEncodeState { | |
50 int clear_code; ///< Value of clear code | |
51 int end_code; ///< Value of end code | |
52 Code tab[LZW_HASH_SIZE]; ///< Hash table | |
53 int tabsize; ///< Number of values in hash table | |
54 int bits; ///< Actual bits code | |
55 int bufsize; ///< Size of output buffer | |
56 PutBitContext pb; ///< Put bit context for output | |
57 int maxbits; ///< Max bits code | |
58 int maxcode; ///< Max value of code | |
59 int output_bytes; ///< Number of written bytes | |
60 int last_code; ///< Value of last output code or LZW_PREFIX_EMPTY | |
61 }LZWEncodeState; | |
62 | |
63 | |
64 const int ff_lzw_encode_state_size = sizeof(LZWEncodeState); | |
65 | |
66 /** | |
67 * Hash function adding character | |
68 * @param head LZW code for prefix | |
69 * @param add Character to add | |
70 * @return New hash value | |
71 */ | |
72 static inline int hash(int head, const int add) | |
73 { | |
74 head ^= (add << LZW_HASH_SHIFT); | |
75 if (head >= LZW_HASH_SIZE) | |
76 head -= LZW_HASH_SIZE; | |
77 assert(head >= 0 && head < LZW_HASH_SIZE); | |
78 return head; | |
79 } | |
80 | |
81 /** | |
82 * Hash function calculates next hash value | |
83 * @param head Actual hash code | |
84 * @param offset Offset calculated by hashOffset | |
85 * @return New hash value | |
86 */ | |
87 static inline int hashNext(int head, const int offset) | |
88 { | |
89 head -= offset; | |
90 if(head < 0) | |
91 head += LZW_HASH_SIZE; | |
92 return head; | |
93 } | |
94 | |
95 /** | |
96 * Hash function calculates hash offset | |
97 * @param head Actual hash code | |
98 * @return Hash offset | |
99 */ | |
100 static inline int hashOffset(const int head) | |
101 { | |
102 return head ? LZW_HASH_SIZE - head : 1; | |
103 } | |
104 | |
105 /** | |
106 * Write one code to stream | |
107 * @param s LZW state | |
108 * @param c code to write | |
109 */ | |
110 static inline void writeCode(LZWEncodeState * s, int c) | |
111 { | |
112 assert(0 <= c && c < 1 << s->bits); | |
113 put_bits(&s->pb, s->bits, c); | |
114 } | |
115 | |
116 | |
117 /** | |
118 * Find LZW code for block | |
119 * @param s LZW state | |
120 * @param c Last character in block | |
121 * @param hash_prefix LZW code for prefix | |
122 * @return LZW code for block or -1 if not found in table | |
123 */ | |
124 static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix) | |
125 { | |
126 int h = hash(FFMAX(hash_prefix, 0), c); | |
127 int hash_offset = hashOffset(h); | |
128 | |
129 while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) { | |
130 if ((s->tab[h].suffix == c) | |
131 && (s->tab[h].hash_prefix == hash_prefix)) | |
132 return h; | |
133 h = hashNext(h, hash_offset); | |
134 } | |
135 | |
136 return h; | |
137 } | |
138 | |
139 /** | |
140 * Add block to LZW code table | |
141 * @param s LZW state | |
142 * @param c Last character in block | |
143 * @param hash_prefix LZW code for prefix | |
144 * @param hash_code LZW code for bytes block | |
145 */ | |
146 static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code) | |
147 { | |
148 s->tab[hash_code].code = s->tabsize; | |
149 s->tab[hash_code].suffix = c; | |
150 s->tab[hash_code].hash_prefix = hash_prefix; | |
151 | |
152 s->tabsize++; | |
153 | |
154 if (s->tabsize >= 1 << s->bits) | |
155 s->bits++; | |
156 } | |
157 | |
158 /** | |
159 * Clear LZW code table | |
160 * @param s LZW state | |
161 */ | |
162 static void clearTable(LZWEncodeState * s) | |
163 { | |
164 int i, h; | |
165 | |
166 writeCode(s, s->clear_code); | |
167 s->bits = 9; | |
168 for (i = 0; i < LZW_HASH_SIZE; i++) { | |
169 s->tab[i].hash_prefix = LZW_PREFIX_FREE; | |
170 } | |
171 for (i = 0; i < 256; i++) { | |
172 h = hash(0, i); | |
173 s->tab[h].code = i; | |
174 s->tab[h].suffix = i; | |
175 s->tab[h].hash_prefix = LZW_PREFIX_EMPTY; | |
176 } | |
177 s->tabsize = 258; | |
178 } | |
179 | |
180 /** | |
181 * Calculate number of bytes written | |
182 * @param s LZW encode state | |
183 * @return Number of bytes written | |
184 */ | |
185 static int writtenBytes(LZWEncodeState *s){ | |
186 int ret = (put_bits_count(&s->pb)) >> 3; | |
187 ret -= s->output_bytes; | |
188 s->output_bytes += ret; | |
189 return ret; | |
190 } | |
191 | |
192 /** | |
193 * Initialize LZW encoder. Please set s->clear_code, s->end_code and s->maxbits before run. | |
194 * @param s LZW state | |
195 * @param outbuf Output buffer | |
196 * @param outsize Size of output buffer | |
197 * @param maxbits Maximum length of code | |
198 */ | |
199 void ff_lzw_encode_init(LZWEncodeState * s, uint8_t * outbuf, int outsize, int maxbits) | |
200 { | |
201 s->clear_code = 256; | |
202 s->end_code = 257; | |
203 s->maxbits = maxbits; | |
204 init_put_bits(&s->pb, outbuf, outsize); | |
205 s->bufsize = outsize; | |
206 assert(9 <= s->maxbits && s->maxbits <= s->maxbits); | |
207 s->maxcode = 1 << s->maxbits; | |
208 s->output_bytes = 0; | |
209 s->last_code = LZW_PREFIX_EMPTY; | |
210 s->bits = 9; | |
211 } | |
212 | |
213 /** | |
214 * LZW main compress function | |
215 * @param s LZW state | |
216 * @param inbuf Input buffer | |
217 * @param insize Size of input buffer | |
218 * @return Number of bytes written or -1 on error | |
219 */ | |
220 int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize) | |
221 { | |
222 int i; | |
223 int code_prefix = s->last_code; | |
224 | |
225 if(insize * 3 > (s->bufsize - s->output_bytes) * 2){ | |
226 return -1; | |
227 } | |
228 | |
229 if (code_prefix == LZW_PREFIX_EMPTY) | |
230 clearTable(s); | |
231 | |
232 for (i = 0; i < insize; i++) { | |
233 uint8_t c = *inbuf++; | |
234 int code = findCode(s, c, code_prefix); | |
235 if (s->tab[code].hash_prefix != LZW_PREFIX_FREE) { | |
236 code_prefix = s->tab[code].code; | |
237 } else { | |
238 writeCode(s, code_prefix); | |
239 addCode(s, c, code_prefix, code); | |
240 code_prefix = s->tab[hash(0, c)].code; | |
241 } | |
242 if (s->tabsize >= s->maxcode - 1) { | |
243 clearTable(s); | |
244 } | |
245 } | |
246 s->last_code = code_prefix; | |
247 | |
248 return writtenBytes(s); | |
249 } | |
250 | |
251 /** | |
252 * Write end code and flush bitstream | |
253 * @param s LZW state | |
254 * @return Number of bytes written or -1 on error | |
255 */ | |
256 int ff_lzw_encode_flush(LZWEncodeState * s) | |
257 { | |
258 if (s->last_code != -1) | |
259 writeCode(s, s->last_code); | |
260 writeCode(s, s->end_code); | |
261 flush_put_bits(&s->pb); | |
262 s->last_code = -1; | |
263 | |
264 return writtenBytes(s); | |
265 } |