FFmpeg
xface.c
Go to the documentation of this file.
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 void ff_big_add(BigInt *b, uint8_t a)
32 {
33  int i;
34  uint8_t *w;
35  uint16_t c;
36 
37  a &= XFACE_WORDMASK;
38  if (a == 0)
39  return;
40  w = b->words;
41  c = a;
42  for (i = 0; i < b->nb_words && c; i++) {
43  c += *w;
44  *w++ = c & XFACE_WORDMASK;
45  c >>= XFACE_BITSPERWORD;
46  }
47  if (i == b->nb_words && c) {
48  av_assert0(b->nb_words < XFACE_MAX_WORDS);
49  b->nb_words++;
50  *w = c & XFACE_WORDMASK;
51  }
52 }
53 
54 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  a &= XFACE_WORDMASK;
61  if (a == 1 || b->nb_words == 0) {
62  *r = 0;
63  return;
64  }
65 
66  /* treat this as a == WORDCARRY and just shift everything right a WORD */
67  if (a == 0) {
68  i = --b->nb_words;
69  w = b->words;
70  *r = *w;
71  while (i--) {
72  *w = *(w + 1);
73  w++;
74  }
75  *w = 0;
76  return;
77  }
78  i = b->nb_words;
79  w = b->words + i;
80  c = 0;
81  while (i--) {
82  c <<= XFACE_BITSPERWORD;
83  c += *--w;
84  d = c / (uint16_t)a;
85  c = c % (uint16_t)a;
86  *w = d & XFACE_WORDMASK;
87  }
88  *r = c;
89  if (b->words[b->nb_words - 1] == 0)
90  b->nb_words--;
91 }
92 
93 void ff_big_mul(BigInt *b, uint8_t a)
94 {
95  int i;
96  uint8_t *w;
97  uint16_t c;
98 
99  a &= XFACE_WORDMASK;
100  if (a == 1 || b->nb_words == 0)
101  return;
102  if (a == 0) {
103  /* treat this as a == WORDCARRY and just shift everything left a WORD */
104  av_assert0(b->nb_words < XFACE_MAX_WORDS);
105  i = b->nb_words++;
106  w = b->words + i;
107  while (i--) {
108  *w = *(w - 1);
109  w--;
110  }
111  *w = 0;
112  return;
113  }
114  i = b->nb_words;
115  w = b->words;
116  c = 0;
117  while (i--) {
118  c += (uint16_t)*w * (uint16_t)a;
119  *(w++) = c & XFACE_WORDMASK;
120  c >>= XFACE_BITSPERWORD;
121  }
122  if (c) {
123  av_assert0(b->nb_words < XFACE_MAX_WORDS);
124  b->nb_words++;
125  *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 void ff_xface_generate_face(uint8_t *dst, uint8_t * const src)
287 {
288  int h, i, j, k, l, m;
289 
290  for (j = 0; j < XFACE_HEIGHT; j++) {
291  for (i = 0; i < XFACE_WIDTH; i++) {
292  h = i + j * XFACE_WIDTH;
293  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  for (l = i - 2; l <= i + 2; l++) {
317  for (m = j - 2; m <= j; m++) {
318  if (l <= 0 || l >= i && m == j)
319  continue;
320  if (l <= XFACE_WIDTH && m > 0)
321  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  switch (i) {
348  case 1:
349  switch (j) {
350  case 1: GEN(g_22); break;
351  case 2: GEN(g_21); break;
352  default: GEN(g_20); break;
353  }
354  break;
355  case 2:
356  switch (j) {
357  case 1: GEN(g_12); break;
358  case 2: GEN(g_11); break;
359  default: GEN(g_10); break;
360  }
361  break;
362  case XFACE_WIDTH - 1:
363  switch (j) {
364  case 1: GEN(g_42); break;
365  case 2: GEN(g_41); break;
366  default: GEN(g_40); break;
367  }
368  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  default:
377  switch (j) {
378  case 1: GEN(g_02); break;
379  case 2: GEN(g_01); break;
380  default: GEN(g_00); break;
381  }
382  break;
383  }
384  }
385  }
386 }
g_20
static const uint8_t g_20[]
Definition: xface.c:227
r
const char * r
Definition: vf_curves.c:116
XFACE_HEIGHT
#define XFACE_HEIGHT
Definition: xface.h:34
ff_big_div
void ff_big_div(BigInt *b, uint8_t a, uint8_t *r)
Divide b by a storing the result in b and the remainder in the word pointed to by r.
Definition: xface.c:54
w
uint8_t w
Definition: llviddspenc.c:39
b
#define b
Definition: input.c:41
g_22
static const uint8_t g_22[]
Definition: xface.c:274
g_00
static const uint8_t g_00[]
Definition: xface.c:153
g_40
static const uint8_t g_40[]
Definition: xface.c:238
g_30
static const uint8_t g_30[]
Definition: xface.c:231
ProbRange
Definition: xface.h:90
avassert.h
ff_big_add
void ff_big_add(BigInt *b, uint8_t a)
Add a to b storing the result in b.
Definition: xface.c:31
xface.h
g_31
static const uint8_t g_31[]
Definition: xface.c:262
BigInt
Definition: xface.h:61
av_assert0
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
g_21
static const uint8_t g_21[]
Definition: xface.c:258
g_41
static const uint8_t g_41[]
Definition: xface.c:266
XFACE_WIDTH
#define XFACE_WIDTH
Definition: xface.h:33
src
#define src
Definition: vp8dsp.c:255
g_11
static const uint8_t g_11[]
Definition: xface.c:254
c
Undefined Behavior In the C some operations are like signed integer dereferencing freed accessing outside allocated Undefined Behavior must not occur in a C it is not safe even if the output of undefined operations is unused The unsafety may seem nit picking but Optimizing compilers have in fact optimized code on the assumption that no undefined Behavior occurs Optimizing code based on wrong assumptions can and has in some cases lead to effects beyond the output of computations The signed integer overflow problem in speed critical code Code which is highly optimized and works with signed integers sometimes has the problem that often the output of the computation does not c
Definition: undefined.txt:32
g_02
static const uint8_t g_02[]
Definition: xface.c:213
XFACE_WORDMASK
#define XFACE_WORDMASK
Definition: xface.h:54
a
The reader does not expect b to be semantically here and if the code is changed by maybe adding a a division or other the signedness will almost certainly be mistaken To avoid this confusion a new type was SUINT is the C unsigned type but it holds a signed int to use the same example SUINT a
Definition: undefined.txt:41
g_01
static const uint8_t g_01[]
Definition: xface.c:208
g_32
static const uint8_t g_32[]
Definition: xface.c:278
i
int i
Definition: input.c:407
g_10
static const uint8_t g_10[]
Definition: xface.c:217
XFACE_MAX_WORDS
#define XFACE_MAX_WORDS
Definition: xface.h:57
XFACE_BITSPERWORD
#define XFACE_BITSPERWORD
Definition: xface.h:52
ff_xface_probranges_2x2
const ProbRange ff_xface_probranges_2x2[16]
Definition: xface.c:137
ff_xface_probranges_per_level
const ProbRange ff_xface_probranges_per_level[4][3]
Definition: xface.c:129
g_42
static const uint8_t g_42[]
Definition: xface.c:282
d
d
Definition: ffmpeg_filter.c:156
ff_xface_generate_face
void ff_xface_generate_face(uint8_t *dst, uint8_t *const src)
Definition: xface.c:286
h
h
Definition: vp9dsp_template.c:2038
g_12
static const uint8_t g_12[]
Definition: xface.c:270
ff_big_mul
void ff_big_mul(BigInt *b, uint8_t a)
Multiply a by b storing the result in b.
Definition: xface.c:93
GEN
#define GEN(table)
Generated on Thu May 6 2021 19:21:46 for FFmpeg by   doxygen 1.8.17