FFmpeg  4.0
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 
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) {
49  b->nb_words++;
50  *w = c & XFACE_WORDMASK;
51  }
52 }
53 
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 
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 */
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) {
124  b->nb_words++;
125  *w = c & XFACE_WORDMASK;
126  }
127 }
128 
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 
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 
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 }
const char * b
Definition: vf_curves.c:113
#define XFACE_WIDTH
Definition: xface.h:33
uint8_t words[XFACE_MAX_WORDS]
Definition: xface.h:63
const ProbRange ff_xface_probranges_per_level[4][3]
Definition: xface.c:129
static const uint8_t g_11[]
Definition: xface.c:254
#define src
Definition: vp8dsp.c:254
X-Face common definitions.
void ff_xface_generate_face(uint8_t *dst, uint8_t *const src)
Definition: xface.c:286
#define av_assert0(cond)
assert() equivalent, that is always enabled.
Definition: avassert.h:37
uint8_t
static const uint8_t g_41[]
Definition: xface.c:266
static const uint8_t g_22[]
Definition: xface.c:274
Definition: xface.h:61
static const uint8_t g_21[]
Definition: xface.c:258
void ff_big_mul(BigInt *b, uint8_t a)
Multiply a by b storing the result in b.
Definition: xface.c:93
static const uint8_t g_40[]
Definition: xface.c:238
static const uint8_t g_30[]
Definition: xface.c:231
#define XFACE_MAX_WORDS
Definition: xface.h:57
#define XFACE_BITSPERWORD
Definition: xface.h:52
const char * r
Definition: vf_curves.c:111
void ff_big_add(BigInt *b, uint8_t a)
Add a to b storing the result in b.
Definition: xface.c:31
simple assert() macros that are a bit more flexible than ISO C assert().
const ProbRange ff_xface_probranges_2x2[16]
Definition: xface.c:137
#define XFACE_WORDMASK
Definition: xface.h:54
uint8_t w
Definition: llviddspenc.c:38
#define XFACE_HEIGHT
Definition: xface.h:34
static const uint8_t g_00[]
Definition: xface.c:153
static const uint8_t g_12[]
Definition: xface.c:270
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
#define GEN(table)
static const uint8_t g_20[]
Definition: xface.c:227
static const uint8_t g_01[]
Definition: xface.c:208
static const uint8_t g_42[]
Definition: xface.c:282
static const uint8_t g_32[]
Definition: xface.c:278
static const uint8_t g_10[]
Definition: xface.c:217
static double c[64]
static const uint8_t g_02[]
Definition: xface.c:213
int nb_words
Definition: xface.h:62
static const uint8_t g_31[]
Definition: xface.c:262