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