avcodec/gsmdec_template: Fix runtime error: signed integer overflow: -22527 * 99113...
[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  * @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     void (*put_bits)(PutBitContext *, int, unsigned); ///< 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  */
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  */
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  */
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  */
113 static 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  */
127 static 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  */
149 static 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  */
165 static 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  */
188 static 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  */
202 void 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  */
227 int 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  */
260 int 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 }