FFmpeg coverage

Directory: ../../../ffmpeg/
File: src/libavcodec/xface.c
Date: 2024-04-19 17:50:32
Exec Total Coverage
Lines: 97 102 95.1%
Functions: 4 4 100.0%
Branches: 71 78 91.0%
Line Branch Exec Source
1 /*
2 * Copyright (c) 1990 James Ashton - Sydney University
3 * Copyright (c) 2012 Stefano Sabatini
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 * X-Face common data and utilities definition.
25 */
26
27 #include "libavutil/avassert.h"
28
29 #include "xface.h"
30
31 454976 void ff_big_add(BigInt *b, uint8_t a)
32 {
33 int i;
34 uint8_t *w;
35 uint16_t c;
36
37 454976 a &= XFACE_WORDMASK;
38
2/2
✓ Branch 0 taken 9315 times.
✓ Branch 1 taken 445661 times.
 454976 if (a == 0)
39 9315 return;
40 445661 w = b->words;
41 445661 c = a;
42
4/4
✓ Branch 0 taken 936195 times.
✓ Branch 1 taken 933 times.
✓ Branch 2 taken 491467 times.
✓ Branch 3 taken 444728 times.
 937128 for (i = 0; i < b->nb_words && c; i++) {
43 491467 c += *w;
44 491467 *w++ = c & XFACE_WORDMASK;
45 491467 c >>= XFACE_BITSPERWORD;
46 }
47
4/4
✓ Branch 0 taken 933 times.
✓ Branch 1 taken 444728 times.
✓ Branch 2 taken 546 times.
✓ Branch 3 taken 387 times.
 445661 if (i == b->nb_words && c) {
48
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 546 times.
 546 av_assert0(b->nb_words < XFACE_MAX_WORDS);
49 546 b->nb_words++;
50 546 *w = c & XFACE_WORDMASK;
51 }
52 }
53
54 454735 void ff_big_div(BigInt *b, uint8_t a, uint8_t *r)
55 {
56 int i;
57 uint8_t *w;
58 uint16_t c, d;
59
60 454735 a &= XFACE_WORDMASK;
61
4/4
✓ Branch 0 taken 454395 times.
✓ Branch 1 taken 340 times.
✓ Branch 2 taken 240 times.
✓ Branch 3 taken 454155 times.
 454735 if (a == 1 || b->nb_words == 0) {
62 580 *r = 0;
63 580 return;
64 }
65
66 /* treat this as a == WORDCARRY and just shift everything right a WORD */
67
2/2
✓ Branch 0 taken 194000 times.
✓ Branch 1 taken 260155 times.
 454155 if (a == 0) {
68 194000 i = --b->nb_words;
69 194000 w = b->words;
70 194000 *r = *w;
71
2/2
✓ Branch 0 taken 26138272 times.
✓ Branch 1 taken 194000 times.
 26332272 while (i--) {
72 26138272 *w = *(w + 1);
73 26138272 w++;
74 }
75 194000 *w = 0;
76 194000 return;
77 }
78 260155 i = b->nb_words;
79 260155 w = b->words + i;
80 260155 c = 0;
81
2/2
✓ Branch 0 taken 35586721 times.
✓ Branch 1 taken 260155 times.
 35846876 while (i--) {
82 35586721 c <<= XFACE_BITSPERWORD;
83 35586721 c += *--w;
84 35586721 d = c / (uint16_t)a;
85 35586721 c = c % (uint16_t)a;
86 35586721 *w = d & XFACE_WORDMASK;
87 }
88 260155 *r = c;
89
2/2
✓ Branch 0 taken 193185 times.
✓ Branch 1 taken 66970 times.
 260155 if (b->words[b->nb_words - 1] == 0)
90 193185 b->nb_words--;
91 }
92
93 454976 void ff_big_mul(BigInt *b, uint8_t a)
94 {
95 int i;
96 uint8_t *w;
97 uint16_t c;
98
99 454976 a &= XFACE_WORDMASK;
100
4/4
✓ Branch 0 taken 454636 times.
✓ Branch 1 taken 340 times.
✓ Branch 2 taken 758 times.
✓ Branch 3 taken 453878 times.
 454976 if (a == 1 || b->nb_words == 0)
101 1098 return;
102
2/2
✓ Branch 0 taken 192927 times.
✓ Branch 1 taken 260951 times.
 453878 if (a == 0) {
103 /* treat this as a == WORDCARRY and just shift everything left a WORD */
104
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 192927 times.
 192927 av_assert0(b->nb_words < XFACE_MAX_WORDS);
105 192927 i = b->nb_words++;
106 192927 w = b->words + i;
107
2/2
✓ Branch 0 taken 26057181 times.
✓ Branch 1 taken 192927 times.
 26250108 while (i--) {
108 26057181 *w = *(w - 1);
109 26057181 w--;
110 }
111 192927 *w = 0;
112 192927 return;
113 }
114 260951 i = b->nb_words;
115 260951 w = b->words;
116 260951 c = 0;
117
2/2
✓ Branch 0 taken 35498399 times.
✓ Branch 1 taken 260951 times.
 35759350 while (i--) {
118 35498399 c += (uint16_t)*w * (uint16_t)a;
119 35498399 *(w++) = c & XFACE_WORDMASK;
120 35498399 c >>= XFACE_BITSPERWORD;
121 }
122
2/2
✓ Branch 0 taken 193712 times.
✓ Branch 1 taken 67239 times.
 260951 if (c) {
123
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 193712 times.
 193712 av_assert0(b->nb_words < XFACE_MAX_WORDS);
124 193712 b->nb_words++;
125 193712 *w = c & XFACE_WORDMASK;
126 }
127 }
128
129 const ProbRange ff_xface_probranges_per_level[4][3] = {
130 // black grey white
131 { { 1, 255}, {251, 0}, { 4, 251} }, /* Top of tree almost always grey */
132 { { 1, 255}, {200, 0}, { 55, 200} },
133 { { 33, 223}, {159, 0}, { 64, 159} },
134 { {131, 0}, { 0, 0}, {125, 131} }, /* Grey disallowed at bottom */
135 };
136
137 const ProbRange ff_xface_probranges_2x2[16] = {
138 { 0, 0}, {38, 0}, {38, 38}, {13, 152},
139 {38, 76}, {13, 165}, {13, 178}, { 6, 230},
140 {38, 114}, {13, 191}, {13, 204}, { 6, 236},
141 {13, 217}, { 6, 242}, { 5, 248}, { 3, 253},
142 };
143
144 /*
145 * The "guess the next pixel" tables follow. Normally there are 12
146 * neighbour pixels used to give 1<<12 cases as we get closer to the
147 * upper left corner lesser numbers of neighbours are available.
148 *
149 * Each byte in the tables represents 8 boolean values starting from
150 * the most significant bit.
151 */
152
153 static const uint8_t g_00[] = {
154 0x00, 0x00, 0x01, 0x01, 0x00, 0x00, 0xe3, 0xdf, 0x05, 0x17,
155 0x05, 0x0f, 0x00, 0x1b, 0x0f, 0xdf, 0x00, 0x04, 0x00, 0x00,
156 0x0d, 0x0f, 0x03, 0x7f, 0x00, 0x00, 0x00, 0x01, 0x00, 0x1d,
157 0x45, 0x2f, 0x00, 0x00, 0x00, 0x0d, 0x00, 0x0a, 0xff, 0xff,
158 0x00, 0x04, 0x00, 0x05, 0x01, 0x3f, 0xcf, 0xff, 0x10, 0x01,
159 0x80, 0xc9, 0x0f, 0x0f, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
160 0x1b, 0x1f, 0xff, 0xff, 0x4f, 0x54, 0x07, 0x1f, 0x57, 0x47,
161 0xd7, 0x3d, 0xff, 0xff, 0x5f, 0x1f, 0x7f, 0xff, 0x7f, 0x7f,
162 0x05, 0x0f, 0x01, 0x0f, 0x0f, 0x5f, 0x9b, 0xdf, 0x7f, 0xff,
163 0x5f, 0x1d, 0x5f, 0xff, 0x0f, 0x1f, 0x0f, 0x5f, 0x03, 0x1f,
164 0x4f, 0x5f, 0xf7, 0x7f, 0x7f, 0xff, 0x0d, 0x0f, 0xfb, 0xff,
165 0xf7, 0xbf, 0x0f, 0x4f, 0xd7, 0x3f, 0x4f, 0x7f, 0xff, 0xff,
166 0x67, 0xbf, 0x56, 0x25, 0x1f, 0x7f, 0x9f, 0xff, 0x00, 0x00,
167 0x00, 0x05, 0x5f, 0x7f, 0x01, 0xdf, 0x14, 0x00, 0x05, 0x0f,
168 0x07, 0xa2, 0x09, 0x0f, 0x00, 0x00, 0x00, 0x00, 0x0f, 0x5f,
169 0x18, 0xd7, 0x94, 0x71, 0x00, 0x05, 0x1f, 0xb7, 0x0c, 0x07,
170 0x0f, 0x0f, 0x00, 0x0f, 0x0f, 0x1f, 0x84, 0x8f, 0x05, 0x15,
171 0x05, 0x0f, 0x4f, 0xff, 0x87, 0xdf, 0x05, 0x01, 0x10, 0x00,
172 0x0f, 0x0f, 0x00, 0x08, 0x05, 0x04, 0x04, 0x01, 0x4f, 0xff,
173 0x9f, 0x8f, 0x4a, 0x40, 0x5f, 0x5f, 0xff, 0xfe, 0xdf, 0xff,
174 0x7f, 0xf7, 0xff, 0x7f, 0xff, 0xff, 0x7b, 0xff, 0x0f, 0xfd,
175 0xd7, 0x5f, 0x4f, 0x7f, 0x7f, 0xdf, 0xff, 0xff, 0xff, 0xff,
176 0xff, 0x77, 0xdf, 0x7f, 0x4f, 0xef, 0xff, 0xff, 0x77, 0xff,
177 0xff, 0xff, 0x6f, 0xff, 0x0f, 0x4f, 0xff, 0xff, 0x9d, 0xff,
178 0x0f, 0xef, 0xff, 0xdf, 0x6f, 0xff, 0xff, 0xff, 0x4f, 0xff,
179 0xcd, 0x0f, 0x4f, 0xff, 0xff, 0xdf, 0x00, 0x00, 0x00, 0x0b,
180 0x05, 0x02, 0x02, 0x0f, 0x04, 0x00, 0x00, 0x0c, 0x01, 0x06,
181 0x00, 0x0f, 0x20, 0x03, 0x00, 0x00, 0x05, 0x0f, 0x40, 0x08,
182 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x0c, 0x0f, 0x01, 0x00,
183 0x80, 0x00, 0x00, 0x00, 0x80, 0x00, 0x00, 0x14, 0x01, 0x05,
184 0x01, 0x15, 0xaf, 0x0f, 0x00, 0x01, 0x10, 0x00, 0x08, 0x00,
185 0x46, 0x0c, 0x20, 0x00, 0x88, 0x00, 0x0f, 0x15, 0xff, 0xdf,
186 0x02, 0x00, 0x00, 0x0f, 0x7f, 0x5f, 0xdb, 0xff, 0x4f, 0x3e,
187 0x05, 0x0f, 0x7f, 0xf7, 0x95, 0x4f, 0x0d, 0x0f, 0x01, 0x0f,
188 0x4f, 0x5f, 0x9f, 0xdf, 0x25, 0x0e, 0x0d, 0x0d, 0x4f, 0x7f,
189 0x8f, 0x0f, 0x0f, 0xfa, 0x04, 0x4f, 0x4f, 0xff, 0xf7, 0x77,
190 0x47, 0xed, 0x05, 0x0f, 0xff, 0xff, 0xdf, 0xff, 0x4f, 0x6f,
191 0xd8, 0x5f, 0x0f, 0x7f, 0xdf, 0x5f, 0x07, 0x0f, 0x94, 0x0d,
192 0x1f, 0xff, 0xff, 0xff, 0x00, 0x02, 0x00, 0x03, 0x46, 0x57,
193 0x01, 0x0d, 0x01, 0x08, 0x01, 0x0f, 0x47, 0x6c, 0x0d, 0x0f,
194 0x02, 0x00, 0x00, 0x00, 0x0b, 0x4f, 0x00, 0x08, 0x05, 0x00,
195 0x95, 0x01, 0x0f, 0x7f, 0x0c, 0x0f, 0x01, 0x0e, 0x00, 0x00,
196 0x0f, 0x41, 0x00, 0x00, 0x04, 0x24, 0x0d, 0x0f, 0x0f, 0x7f,
197 0xcf, 0xdf, 0x00, 0x00, 0x00, 0x00, 0x04, 0x40, 0x00, 0x00,
198 0x06, 0x26, 0xcf, 0x05, 0xcf, 0x7f, 0xdf, 0xdf, 0x00, 0x00,
199 0x17, 0x5f, 0xff, 0xfd, 0xff, 0xff, 0x46, 0x09, 0x4f, 0x5f,
200 0x7f, 0xfd, 0xdf, 0xff, 0x0a, 0x88, 0xa7, 0x7f, 0x7f, 0xff,
201 0xff, 0xff, 0x0f, 0x04, 0xdf, 0x7f, 0x4f, 0xff, 0x9f, 0xff,
202 0x0e, 0xe6, 0xdf, 0xff, 0x7f, 0xff, 0xff, 0xff, 0x0f, 0xec,
203 0x8f, 0x4f, 0x7f, 0xff, 0xdf, 0xff, 0x0f, 0xcf, 0xdf, 0xff,
204 0x6f, 0x7f, 0xff, 0xff, 0x03, 0x0c, 0x9d, 0x0f, 0x7f, 0xff,
205 0xff, 0xff,
206 };
207
208 static const uint8_t g_01[] = {
209 0x37, 0x73, 0x00, 0x19, 0x57, 0x7f, 0xf5, 0xfb, 0x70, 0x33,
210 0xf0, 0xf9, 0x7f, 0xff, 0xff, 0xff,
211 };
212
213 static const uint8_t g_02[] = {
214 0x50,
215 };
216
217 static const uint8_t g_10[] = {
218 0x00, 0x00, 0x00, 0x00, 0x50, 0x00, 0xf3, 0x5f, 0x84, 0x04,
219 0x17, 0x9f, 0x04, 0x23, 0x05, 0xff, 0x00, 0x00, 0x00, 0x02,
220 0x03, 0x03, 0x33, 0xd7, 0x05, 0x03, 0x5f, 0x3f, 0x17, 0x33,
221 0xff, 0xff, 0x00, 0x80, 0x02, 0x04, 0x12, 0x00, 0x11, 0x57,
222 0x05, 0x25, 0x05, 0x03, 0x35, 0xbf, 0x9f, 0xff, 0x07, 0x6f,
223 0x20, 0x40, 0x17, 0x06, 0xfa, 0xe8, 0x01, 0x07, 0x1f, 0x9f,
224 0x1f, 0xff, 0xff, 0xff,
225 };
226
227 static const uint8_t g_20[] = {
228 0x04, 0x00, 0x01, 0x01, 0x43, 0x2e, 0xff, 0x3f,
229 };
230
231 static const uint8_t g_30[] = {
232 0x11, 0x11, 0x11, 0x11, 0x51, 0x11, 0x13, 0x11, 0x11, 0x11,
233 0x13, 0x11, 0x11, 0x11, 0x33, 0x11, 0x13, 0x11, 0x13, 0x13,
234 0x13, 0x13, 0x31, 0x31, 0x11, 0x01, 0x11, 0x11, 0x71, 0x11,
235 0x11, 0x75,
236 };
237
238 static const uint8_t g_40[] = {
239 0x00, 0x0f, 0x00, 0x09, 0x00, 0x0d, 0x00, 0x0d, 0x00, 0x0f,
240 0x00, 0x4e, 0xe4, 0x0d, 0x10, 0x0f, 0x00, 0x0f, 0x44, 0x4f,
241 0x00, 0x1e, 0x0f, 0x0f, 0xae, 0xaf, 0x45, 0x7f, 0xef, 0xff,
242 0x0f, 0xff, 0x00, 0x09, 0x01, 0x11, 0x00, 0x01, 0x1c, 0xdd,
243 0x00, 0x15, 0x00, 0xff, 0x00, 0x10, 0x00, 0xfd, 0x00, 0x0f,
244 0x4f, 0x5f, 0x3d, 0xff, 0xff, 0xff, 0x4f, 0xff, 0x1c, 0xff,
245 0xdf, 0xff, 0x8f, 0xff, 0x00, 0x0d, 0x00, 0x00, 0x00, 0x15,
246 0x01, 0x07, 0x00, 0x01, 0x02, 0x1f, 0x01, 0x11, 0x05, 0x7f,
247 0x00, 0x1f, 0x41, 0x57, 0x1f, 0xff, 0x05, 0x77, 0x0d, 0x5f,
248 0x4d, 0xff, 0x4f, 0xff, 0x0f, 0xff, 0x00, 0x00, 0x02, 0x05,
249 0x00, 0x11, 0x05, 0x7d, 0x10, 0x15, 0x2f, 0xff, 0x40, 0x50,
250 0x0d, 0xfd, 0x04, 0x0f, 0x07, 0x1f, 0x07, 0x7f, 0x0f, 0xbf,
251 0x0d, 0x7f, 0x0f, 0xff, 0x4d, 0x7d, 0x0f, 0xff,
252 };
253
254 static const uint8_t g_11[] = {
255 0x01, 0x13, 0x03, 0x7f,
256 };
257
258 static const uint8_t g_21[] = {
259 0x17,
260 };
261
262 static const uint8_t g_31[] = {
263 0x55, 0x57, 0x57, 0x7f,
264 };
265
266 static const uint8_t g_41[] = {
267 0x01, 0x01, 0x01, 0x1f, 0x03, 0x1f, 0x3f, 0xff,
268 };
269
270 static const uint8_t g_12[] = {
271 0x40,
272 };
273
274 static const uint8_t g_22[] = {
275 0x00,
276 };
277
278 static const uint8_t g_32[] = {
279 0x10,
280 };
281
282 static const uint8_t g_42[] = {
283 0x10,
284 };
285
286 401 void ff_xface_generate_face(uint8_t *dst, uint8_t * const src)
287 {
288 int h, i, j, k, l, m;
289
290
2/2
✓ Branch 0 taken 19248 times.
✓ Branch 1 taken 401 times.
 19649 for (j = 0; j < XFACE_HEIGHT; j++) {
291
2/2
✓ Branch 0 taken 923904 times.
✓ Branch 1 taken 19248 times.
 943152 for (i = 0; i < XFACE_WIDTH; i++) {
292 923904 h = i + j * XFACE_WIDTH;
293 923904 k = 0;
294
295 /*
296 Compute k, encoding the bits *before* the current one, contained in the
297 image buffer. That is, given the grid:
298
299 l i
300 | |
301 v v
302 +--+--+--+--+--+
303 m -> | 1| 2| 3| 4| 5|
304 +--+--+--+--+--+
305 | 6| 7| 8| 9|10|
306 +--+--+--+--+--+
307 j -> |11|12| *| | |
308 +--+--+--+--+--+
309
310 the value k for the pixel marked as "*" will contain the bit encoding of
311 the values in the matrix marked from "1" to "12". In case the pixel is
312 near the border of the grid, the number of values contained within the
313 grid will be lesser than 12.
314 */
315
316
2/2
✓ Branch 0 taken 4619520 times.
✓ Branch 1 taken 923904 times.
 5543424 for (l = i - 2; l <= i + 2; l++) {
317
2/2
✓ Branch 0 taken 13858560 times.
✓ Branch 1 taken 4619520 times.
 18478080 for (m = j - 2; m <= j; m++) {
318
6/6
✓ Branch 0 taken 13512096 times.
✓ Branch 1 taken 346464 times.
✓ Branch 2 taken 8257392 times.
✓ Branch 3 taken 5254704 times.
✓ Branch 4 taken 2752464 times.
✓ Branch 5 taken 5504928 times.
 13858560 if (l <= 0 || l >= i && m == j)
319 3098928 continue;
320
4/4
✓ Branch 0 taken 10721136 times.
✓ Branch 1 taken 38496 times.
✓ Branch 2 taken 10217480 times.
✓ Branch 3 taken 503656 times.
 10759632 if (l <= XFACE_WIDTH && m > 0)
321 10217480 k = 2*k + src[l + m * XFACE_WIDTH];
322 }
323 }
324
325 /*
326 Use the guess for the given position and the computed value of k.
327
328 The following table shows the number of digits in k, depending on
329 the position of the pixel, and shows the corresponding guess table
330 to use:
331
332 i=1 i=2 i=3 i=w-1 i=w
333 +----+----+----+ ... +----+----+
334 j=1 | 0 | 1 | 2 | | 2 | 2 |
335 |g22 |g12 |g02 | |g42 |g32 |
336 +----+----+----+ ... +----+----+
337 j=2 | 3 | 5 | 7 | | 6 | 5 |
338 |g21 |g11 |g01 | |g41 |g31 |
339 +----+----+----+ ... +----+----+
340 j=3 | 5 | 9 | 12 | | 10 | 8 |
341 |g20 |g10 |g00 | |g40 |g30 |
342 +----+----+----+ ... +----+----+
343 */
344
345 #define GEN(table) dst[h] ^= (table[k>>3]>>(7-(k&7)))&1
346
347
4/5
✓ Branch 0 taken 19248 times.
✓ Branch 1 taken 19248 times.
✓ Branch 2 taken 19248 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 866160 times.
 923904 switch (i) {
348
3/3
✓ Branch 0 taken 401 times.
✓ Branch 1 taken 401 times.
✓ Branch 2 taken 18446 times.
 19248 case 1:
349 switch (j) {
350 401 case 1: GEN(g_22); break;
351 401 case 2: GEN(g_21); break;
352 18446 default: GEN(g_20); break;
353 }
354 19248 break;
355
3/3
✓ Branch 0 taken 401 times.
✓ Branch 1 taken 401 times.
✓ Branch 2 taken 18446 times.
 19248 case 2:
356 switch (j) {
357 401 case 1: GEN(g_12); break;
358 401 case 2: GEN(g_11); break;
359 18446 default: GEN(g_10); break;
360 }
361 19248 break;
362
3/3
✓ Branch 0 taken 401 times.
✓ Branch 1 taken 401 times.
✓ Branch 2 taken 18446 times.
 19248 case XFACE_WIDTH - 1:
363 switch (j) {
364 401 case 1: GEN(g_42); break;
365 401 case 2: GEN(g_41); break;
366 18446 default: GEN(g_40); break;
367 }
368 19248 break;
369 ✗ case XFACE_WIDTH:
370 switch (j) {
371 ✗ case 1: GEN(g_32); break;
372 ✗ case 2: GEN(g_31); break;
373 ✗ default: GEN(g_30); break;
374 }
375 ✗ break;
376
3/3
✓ Branch 0 taken 18045 times.
✓ Branch 1 taken 18045 times.
✓ Branch 2 taken 830070 times.
 866160 default:
377 switch (j) {
378 18045 case 1: GEN(g_02); break;
379 18045 case 2: GEN(g_01); break;
380 830070 default: GEN(g_00); break;
381 }
382 866160 break;
383 }
384 }
385 }
386 401 }
387