Rename --enable-swscaler --> enable-swscale to be consistent with the
[ffmpeg.git] / libavcodec / lzwenc.c
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
224     if(insize * 3 > (s->bufsize - s->output_bytes) * 2){
225         return -1;
226     }
227
228     if (s->last_code == LZW_PREFIX_EMPTY)
229         clearTable(s);
230
231     for (i = 0; i < insize; i++) {
232         uint8_t c = *inbuf++;
233         int code = findCode(s, c, s->last_code);
234         if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {
235             writeCode(s, s->last_code);
236             addCode(s, c, s->last_code, code);
237             code= hash(0, c);
238         }
239         s->last_code = s->tab[code].code;
240         if (s->tabsize >= s->maxcode - 1) {
241             clearTable(s);
242         }
243     }
244
245     return writtenBytes(s);
246 }
247
248 /**
249  * Write end code and flush bitstream
250  * @param s LZW state
251  * @return Number of bytes written or -1 on error
252  */
253 int ff_lzw_encode_flush(LZWEncodeState * s)
254 {
255     if (s->last_code != -1)
256         writeCode(s, s->last_code);
257     writeCode(s, s->end_code);
258     flush_put_bits(&s->pb);
259     s->last_code = -1;
260
261     return writtenBytes(s);
262 }