]> git.sesse.net Git - ffmpeg/blob - libavcodec/lzwenc.c
options_table: Add some missing #includes to fix "make checkheaders".
[ffmpeg] / libavcodec / lzwenc.c
1 /*
2  * LZW encoder
3  * Copyright (c) 2007 Bartlomiej Wolowiec
4  *
5  * This file is part of Libav.
6  *
7  * Libav 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  * Libav 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 Libav; 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 "put_bits.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     enum FF_LZW_MODES mode;  ///< TIFF or GIF
62     void (*put_bits)(PutBitContext *, int, unsigned); ///< GIF is LE while TIFF is BE
63 }LZWEncodeState;
64
65
66 const int ff_lzw_encode_state_size = sizeof(LZWEncodeState);
67
68 /**
69  * Hash function adding character
70  * @param head LZW code for prefix
71  * @param add Character to add
72  * @return New hash value
73  */
74 static inline int hash(int head, const int add)
75 {
76     head ^= (add << LZW_HASH_SHIFT);
77     if (head >= LZW_HASH_SIZE)
78         head -= LZW_HASH_SIZE;
79     assert(head >= 0 && head < LZW_HASH_SIZE);
80     return head;
81 }
82
83 /**
84  * Hash function calculates next hash value
85  * @param head Actual hash code
86  * @param offset Offset calculated by hashOffset
87  * @return New hash value
88  */
89 static inline int hashNext(int head, const int offset)
90 {
91     head -= offset;
92     if(head < 0)
93         head += LZW_HASH_SIZE;
94     return head;
95 }
96
97 /**
98  * Hash function calculates hash offset
99  * @param head Actual hash code
100  * @return Hash offset
101  */
102 static inline int hashOffset(const int head)
103 {
104     return head ? LZW_HASH_SIZE - head : 1;
105 }
106
107 /**
108  * Write one code to stream
109  * @param s LZW state
110  * @param c code to write
111  */
112 static inline void writeCode(LZWEncodeState * s, int c)
113 {
114     assert(0 <= c && c < 1 << s->bits);
115     s->put_bits(&s->pb, s->bits, c);
116 }
117
118
119 /**
120  * Find LZW code for block
121  * @param s LZW state
122  * @param c Last character in block
123  * @param hash_prefix LZW code for prefix
124  * @return LZW code for block or -1 if not found in table
125  */
126 static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix)
127 {
128     int h = hash(FFMAX(hash_prefix, 0), c);
129     int hash_offset = hashOffset(h);
130
131     while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) {
132         if ((s->tab[h].suffix == c)
133             && (s->tab[h].hash_prefix == hash_prefix))
134             return h;
135         h = hashNext(h, hash_offset);
136     }
137
138     return h;
139 }
140
141 /**
142  * Add block to LZW code table
143  * @param s LZW state
144  * @param c Last character in block
145  * @param hash_prefix LZW code for prefix
146  * @param hash_code LZW code for bytes block
147  */
148 static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code)
149 {
150     s->tab[hash_code].code = s->tabsize;
151     s->tab[hash_code].suffix = c;
152     s->tab[hash_code].hash_prefix = hash_prefix;
153
154     s->tabsize++;
155
156     if (s->tabsize >= (1 << s->bits) + (s->mode == FF_LZW_GIF))
157         s->bits++;
158 }
159
160 /**
161  * Clear LZW code table
162  * @param s LZW state
163  */
164 static void clearTable(LZWEncodeState * s)
165 {
166     int i, h;
167
168     writeCode(s, s->clear_code);
169     s->bits = 9;
170     for (i = 0; i < LZW_HASH_SIZE; i++) {
171         s->tab[i].hash_prefix = LZW_PREFIX_FREE;
172     }
173     for (i = 0; i < 256; i++) {
174         h = hash(0, i);
175         s->tab[h].code = i;
176         s->tab[h].suffix = i;
177         s->tab[h].hash_prefix = LZW_PREFIX_EMPTY;
178     }
179     s->tabsize = 258;
180 }
181
182 /**
183  * Calculate number of bytes written
184  * @param s LZW encode state
185  * @return Number of bytes written
186  */
187 static int writtenBytes(LZWEncodeState *s){
188     int ret = put_bits_count(&s->pb) >> 3;
189     ret -= s->output_bytes;
190     s->output_bytes += ret;
191     return ret;
192 }
193
194 /**
195  * Initialize LZW encoder. Please set s->clear_code, s->end_code and s->maxbits before run.
196  * @param s LZW state
197  * @param outbuf Output buffer
198  * @param outsize Size of output buffer
199  * @param maxbits Maximum length of code
200  */
201 void ff_lzw_encode_init(LZWEncodeState *s, uint8_t *outbuf, int outsize,
202                         int maxbits, enum FF_LZW_MODES mode,
203                         void (*lzw_put_bits)(PutBitContext *, int, unsigned))
204 {
205     s->clear_code = 256;
206     s->end_code = 257;
207     s->maxbits = maxbits;
208     init_put_bits(&s->pb, outbuf, outsize);
209     s->bufsize = outsize;
210     assert(s->maxbits >= 9 && s->maxbits <= LZW_MAXBITS);
211     s->maxcode = 1 << s->maxbits;
212     s->output_bytes = 0;
213     s->last_code = LZW_PREFIX_EMPTY;
214     s->bits = 9;
215     s->mode = mode;
216     s->put_bits = lzw_put_bits;
217 }
218
219 /**
220  * LZW main compress function
221  * @param s LZW state
222  * @param inbuf Input buffer
223  * @param insize Size of input buffer
224  * @return Number of bytes written or -1 on error
225  */
226 int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize)
227 {
228     int i;
229
230     if(insize * 3 > (s->bufsize - s->output_bytes) * 2){
231         return -1;
232     }
233
234     if (s->last_code == LZW_PREFIX_EMPTY)
235         clearTable(s);
236
237     for (i = 0; i < insize; i++) {
238         uint8_t c = *inbuf++;
239         int code = findCode(s, c, s->last_code);
240         if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {
241             writeCode(s, s->last_code);
242             addCode(s, c, s->last_code, code);
243             code= hash(0, c);
244         }
245         s->last_code = s->tab[code].code;
246         if (s->tabsize >= s->maxcode - 1) {
247             clearTable(s);
248         }
249     }
250
251     return writtenBytes(s);
252 }
253
254 /**
255  * Write end code and flush bitstream
256  * @param s LZW state
257  * @return Number of bytes written or -1 on error
258  */
259 int ff_lzw_encode_flush(LZWEncodeState *s,
260                         void (*lzw_flush_put_bits)(PutBitContext *))
261 {
262     if (s->last_code != -1)
263         writeCode(s, s->last_code);
264     writeCode(s, s->end_code);
265     lzw_flush_put_bits(&s->pb);
266     s->last_code = -1;
267
268     return writtenBytes(s);
269 }