GCC Code Coverage Report
Directory: ../../../ffmpeg/ Exec Total Coverage
File: src/libavcodec/xface.c Lines: 97 102 95.1 %
Date: 2020-10-23 17:01:47 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
454976
    if (a == 0)
39
9315
        return;
40
445661
    w = b->words;
41
445661
    c = a;
42

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

445661
    if (i == b->nb_words && c) {
48
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

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
454155
    if (a == 0) {
68
194000
        i = --b->nb_words;
69
194000
        w = b->words;
70
194000
        *r = *w;
71
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
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
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

454976
    if (a == 1 || b->nb_words == 0)
101
1098
        return;
102
453878
    if (a == 0) {
103
        /* treat this as a == WORDCARRY and just shift everything left a WORD */
104
192927
        av_assert0(b->nb_words < XFACE_MAX_WORDS);
105
192927
        i = b->nb_words++;
106
192927
        w = b->words + i;
107
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
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
260951
    if (c) {
123
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
19649
    for (j = 0; j < XFACE_HEIGHT; j++) {
291
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
5543424
            for (l = i - 2; l <= i + 2; l++) {
317
18478080
                for (m = j - 2; m <= j; m++) {
318

13858560
                    if (l <= 0 || l >= i && m == j)
319
3098928
                        continue;
320

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

923904
            switch (i) {
348
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
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
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
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
}