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
ff_big_add(BigInt * b,uint8_t a)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
ff_big_div(BigInt * b,uint8_t a,uint8_t * r)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
ff_big_mul(BigInt * b,uint8_t a)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
ff_xface_generate_face(uint8_t * dst,uint8_t * const src)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 }
387