FFmpeg coverage

Directory: ../../../ffmpeg/
File: src/libavcodec/lzwenc.c
Date: 2026-01-16 07:34:38
Exec Total Coverage
Lines: 88 94 93.6%
Functions: 11 11 100.0%
Branches: 32 42 76.2%
Line Branch Exec Source
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 */
76 5529882 static inline int hash(int head, const int add)
77 {
78 5529882 head ^= (add << LZW_HASH_SHIFT);
79
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5529882 times.
 5529882 if (head >= LZW_HASH_SIZE)
80 ✗ head -= LZW_HASH_SIZE;
81 av_assert2(head >= 0 && head < LZW_HASH_SIZE);
82 5529882 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 */
91 1410149 static inline int hashNext(int head, const int offset)
92 {
93 1410149 head -= offset;
94
2/2
✓ Branch 0 taken 1118254 times.
✓ Branch 1 taken 291895 times.
 1410149 if(head < 0)
95 1118254 head += LZW_HASH_SIZE;
96 1410149 return head;
97 }
98
99 /**
100 * Hash function calculates hash offset
101 * @param head Actual hash code
102 * @return Hash offset
103 */
104 3541685 static inline int hashOffset(const int head)
105 {
106
2/2
✓ Branch 0 taken 3509155 times.
✓ Branch 1 taken 32530 times.
 3541685 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 */
114 1630008 static inline void writeCode(LZWEncodeState * s, int c)
115 {
116 av_assert2(0 <= c && c < 1 << s->bits);
117
1/2
✓ Branch 0 taken 1630008 times.
✗ Branch 1 not taken.
 1630008 if (s->little_endian)
118 1630008 put_bits_le(&s->pb, s->bits, c);
119 else
120 ✗ put_bits(&s->pb, s->bits, c);
121 1630008 }
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 */
131 3541685 static inline int findCode(LZWEncodeState * s, uint8_t c, int hash_prefix)
132 {
133 3541685 int h = hash(FFMAX(hash_prefix, 0), c);
134 3541685 int hash_offset = hashOffset(h);
135
136
2/2
✓ Branch 0 taken 3325365 times.
✓ Branch 1 taken 1626469 times.
 4951834 while (s->tab[h].hash_prefix != LZW_PREFIX_FREE) {
137
2/2
✓ Branch 0 taken 1966105 times.
✓ Branch 1 taken 1359260 times.
 3325365 if ((s->tab[h].suffix == c)
138
2/2
✓ Branch 0 taken 1915216 times.
✓ Branch 1 taken 50889 times.
 1966105 && (s->tab[h].hash_prefix == hash_prefix))
139 1915216 return h;
140 1410149 h = hashNext(h, hash_offset);
141 }
142
143 1626469 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 */
153 1626469 static inline void addCode(LZWEncodeState * s, uint8_t c, int hash_prefix, int hash_code)
154 {
155 1626469 s->tab[hash_code].code = s->tabsize;
156 1626469 s->tab[hash_code].suffix = c;
157 1626469 s->tab[hash_code].hash_prefix = hash_prefix;
158
159 1626469 s->tabsize++;
160
161
2/2
✓ Branch 0 taken 1324 times.
✓ Branch 1 taken 1625145 times.
 1626469 if (s->tabsize >= (1 << s->bits) + (s->mode == FF_LZW_GIF))
162 1324 s->bits++;
163 1626469 }
164
165 /**
166 * Clear LZW code table
167 * @param s LZW state
168 */
169 1413 static void clearTable(LZWEncodeState * s)
170 {
171 int i, h;
172
173 1413 writeCode(s, s->clear_code);
174 1413 s->bits = 9;
175
2/2
✓ Branch 0 taken 23188743 times.
✓ Branch 1 taken 1413 times.
 23190156 for (i = 0; i < LZW_HASH_SIZE; i++) {
176 23188743 s->tab[i].hash_prefix = LZW_PREFIX_FREE;
177 }
178
2/2
✓ Branch 0 taken 361728 times.
✓ Branch 1 taken 1413 times.
 363141 for (i = 0; i < 256; i++) {
179 361728 h = hash(0, i);
180 361728 s->tab[h].code = i;
181 361728 s->tab[h].suffix = i;
182 361728 s->tab[h].hash_prefix = LZW_PREFIX_EMPTY;
183 }
184 1413 s->tabsize = 258;
185 1413 }
186
187 /**
188 * Calculate number of bytes written
189 * @param s LZW encode state
190 * @return Number of bytes written
191 */
192 35140 static int writtenBytes(LZWEncodeState *s){
193 35140 int ret = put_bytes_count(&s->pb, 0);
194 35140 ret -= s->output_bytes;
195 35140 s->output_bytes += ret;
196 35140 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 */
206 1063 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 1063 s->clear_code = 256;
210 1063 s->end_code = 257;
211 1063 s->maxbits = maxbits;
212 1063 init_put_bits(&s->pb, outbuf, outsize);
213 1063 s->bufsize = outsize;
214
2/4
✓ Branch 0 taken 1063 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 1063 times.
 1063 av_assert0(s->maxbits >= 9 && s->maxbits <= LZW_MAXBITS);
215 1063 s->maxcode = 1 << s->maxbits;
216 1063 s->output_bytes = 0;
217 1063 s->last_code = LZW_PREFIX_EMPTY;
218 1063 s->bits = 9;
219 1063 s->mode = mode;
220 1063 s->little_endian = little_endian;
221 1063 }
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 */
230 34077 int ff_lzw_encode(LZWEncodeState * s, const uint8_t * inbuf, int insize)
231 {
232 int i;
233
234
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 34077 times.
 34077 if(insize * 3 > (s->bufsize - s->output_bytes) * 2){
235 ✗ return -1;
236 }
237
238
2/2
✓ Branch 0 taken 1063 times.
✓ Branch 1 taken 33014 times.
 34077 if (s->last_code == LZW_PREFIX_EMPTY)
239 1063 clearTable(s);
240
241
2/2
✓ Branch 0 taken 3541685 times.
✓ Branch 1 taken 34077 times.
 3575762 for (i = 0; i < insize; i++) {
242 3541685 uint8_t c = *inbuf++;
243 3541685 int code = findCode(s, c, s->last_code);
244
2/2
✓ Branch 0 taken 1626469 times.
✓ Branch 1 taken 1915216 times.
 3541685 if (s->tab[code].hash_prefix == LZW_PREFIX_FREE) {
245 1626469 writeCode(s, s->last_code);
246 1626469 addCode(s, c, s->last_code, code);
247 1626469 code= hash(0, c);
248 }
249 3541685 s->last_code = s->tab[code].code;
250
2/2
✓ Branch 0 taken 350 times.
✓ Branch 1 taken 3541335 times.
 3541685 if (s->tabsize >= s->maxcode - 1) {
251 350 clearTable(s);
252 }
253 }
254
255 34077 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 */
263 1063 int ff_lzw_encode_flush(LZWEncodeState *s)
264 {
265
1/2
✓ Branch 0 taken 1063 times.
✗ Branch 1 not taken.
 1063 if (s->last_code != -1)
266 1063 writeCode(s, s->last_code);
267 1063 writeCode(s, s->end_code);
268
1/2
✓ Branch 0 taken 1063 times.
✗ Branch 1 not taken.
 1063 if (s->little_endian) {
269
1/2
✓ Branch 0 taken 1063 times.
✗ Branch 1 not taken.
 1063 if (s->mode == FF_LZW_GIF)
270 1063 put_bits_le(&s->pb, 1, 0);
271
272 1063 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 1063 s->last_code = -1;
280
281 1063 return writtenBytes(s);
282 }
283