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 */
hash(int head,const int add)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 */
hashNext(int head,const int offset)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 */
hashOffset(const int head)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 */
writeCode(LZWEncodeState * s,int c)113 static inline void writeCode(LZWEncodeState * s, int c)
114 {
115 av_assert2(0 <= c && c < 1 << s->bits);
116 if (s->little_endian)
117 put_bits_le(&s->pb, s->bits, c);
118 else
119 put_bits(&s->pb, s->bits, c);
120 }
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 */
findCode(LZWEncodeState * s,uint8_t c,int hash_prefix)130 static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix)
131 {
132 int h = hash(FFMAX(hash_prefix, 0), c);
133 int hash_offset = hashOffset(h);
134
135 while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) {
136 if ((s->tab[h].suffix == c)
137 && (s->tab[h].hash_prefix == hash_prefix))
138 return h;
139 h = hashNext(h, hash_offset);
140 }
141
142 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 */
addCode(LZWEncodeState * s,uint8_t c,int hash_prefix,int hash_code)152 static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code)
153 {
154 s->tab[hash_code].code = s->tabsize;
155 s->tab[hash_code].suffix = c;
156 s->tab[hash_code].hash_prefix = hash_prefix;
157
158 s->tabsize++;
159
160 if (s->tabsize >= (1 << s->bits) + (s->mode == FF_LZW_GIF))
161 s->bits++;
162 }
163
164 /**
165 * Clear LZW code table
166 * @param s LZW state
167 */
clearTable(LZWEncodeState * s)168 static void clearTable(LZWEncodeState * s)
169 {
170 int i, h;
171
172 writeCode(s, s->clear_code);
173 s->bits = 9;
174 for (i = 0; i < LZW_HASH_SIZE; i++) {
175 s->tab[i].hash_prefix = LZW_PREFIX_FREE;
176 }
177 for (i = 0; i < 256; i++) {
178 h = hash(0, i);
179 s->tab[h].code = i;
180 s->tab[h].suffix = i;
181 s->tab[h].hash_prefix = LZW_PREFIX_EMPTY;
182 }
183 s->tabsize = 258;
184 }
185
186 /**
187 * Calculate number of bytes written
188 * @param s LZW encode state
189 * @return Number of bytes written
190 */
writtenBytes(LZWEncodeState * s)191 static int writtenBytes(LZWEncodeState *s){
192 int ret = put_bits_count(&s->pb) >> 3;
193 ret -= s->output_bytes;
194 s->output_bytes += ret;
195 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 */
ff_lzw_encode_init(LZWEncodeState * s,uint8_t * outbuf,int outsize,int maxbits,enum FF_LZW_MODES mode,int little_endian)205 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 s->clear_code = 256;
209 s->end_code = 257;
210 s->maxbits = maxbits;
211 init_put_bits(&s->pb, outbuf, outsize);
212 s->bufsize = outsize;
213 av_assert0(s->maxbits >= 9 && s->maxbits <= LZW_MAXBITS);
214 s->maxcode = 1 << s->maxbits;
215 s->output_bytes = 0;
216 s->last_code = LZW_PREFIX_EMPTY;
217 s->bits = 9;
218 s->mode = mode;
219 s->little_endian = little_endian;
220 }
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 */
ff_lzw_encode(LZWEncodeState * s,const uint8_t * inbuf,int insize)229 int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize)
230 {
231 int i;
232
233 if(insize * 3 > (s->bufsize - s->output_bytes) * 2){
234 return -1;
235 }
236
237 if (s->last_code == LZW_PREFIX_EMPTY)
238 clearTable(s);
239
240 for (i = 0; i < insize; i++) {
241 uint8_t c = *inbuf++;
242 int code = findCode(s, c, s->last_code);
243 if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {
244 writeCode(s, s->last_code);
245 addCode(s, c, s->last_code, code);
246 code= hash(0, c);
247 }
248 s->last_code = s->tab[code].code;
249 if (s->tabsize >= s->maxcode - 1) {
250 clearTable(s);
251 }
252 }
253
254 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 */
ff_lzw_encode_flush(LZWEncodeState * s)262 int ff_lzw_encode_flush(LZWEncodeState *s)
263 {
264 if (s->last_code != -1)
265 writeCode(s, s->last_code);
266 writeCode(s, s->end_code);
267 if (s->little_endian) {
268 if (s->mode == FF_LZW_GIF)
269 put_bits_le(&s->pb, 1, 0);
270
271 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 s->last_code = -1;
279
280 return writtenBytes(s);
281 }
282