Imported Debian version 2.5.3~trusty1
[deb_ffmpeg.git] / ffmpeg / libavcodec / lzwenc.c
CommitLineData
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 */
42typedef 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 */
50typedef 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
67const 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 */
75static 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 */
90static 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 */
103static 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 */
113static 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 */
127static 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 */
149static 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 */
165static 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 */
188static 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 */
202void 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 */
227int 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 */
260int 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}