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