2 * Copyright (c) 1990 James Ashton - Sydney University
3 * Copyright (c) 2012 Stefano Sabatini
5 * This file is part of FFmpeg.
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.
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.
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
24 * X-Face common data and utilities definition.
29 void ff_big_add(BigInt *b, uint8_t a)
40 for (i = 0; i < b->nb_words && c; i++) {
42 *w++ = c & XFACE_WORDMASK;
43 c >>= XFACE_BITSPERWORD;
45 if (i == b->nb_words && c) {
47 *w = c & XFACE_WORDMASK;
51 void ff_big_div(BigInt *b, uint8_t a, uint8_t *r)
58 if (a == 1 || b->nb_words == 0) {
63 /* treat this as a == WORDCARRY and just shift everything right a WORD */
79 c <<= XFACE_BITSPERWORD;
83 *w = d & XFACE_WORDMASK;
86 if (b->words[b->nb_words - 1] == 0)
90 void ff_big_mul(BigInt *b, uint8_t a)
97 if (a == 1 || b->nb_words == 0)
100 /* treat this as a == WORDCARRY and just shift everything left a WORD */
114 c += (uint16_t)*w * (uint16_t)a;
115 *(w++) = c & XFACE_WORDMASK;
116 c >>= XFACE_BITSPERWORD;
120 *w = c & XFACE_WORDMASK;
124 const ProbRange ff_xface_probranges_per_level[4][3] = {
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 */
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},
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.
144 * Each byte in the tables represents 8 boolean values starting from
145 * the most significant bit.
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,
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,
208 static const uint8_t g_02[] = {
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,
222 static const uint8_t g_20[] = {
223 0x04, 0x00, 0x01, 0x01, 0x43, 0x2e, 0xff, 0x3f,
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,
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,
249 static const uint8_t g_11[] = {
250 0x01, 0x13, 0x03, 0x7f,
253 static const uint8_t g_21[] = {
257 static const uint8_t g_31[] = {
258 0x55, 0x57, 0x57, 0x7f,
261 static const uint8_t g_41[] = {
262 0x01, 0x01, 0x01, 0x1f, 0x03, 0x1f, 0x3f, 0xff,
265 static const uint8_t g_12[] = {
269 static const uint8_t g_22[] = {
273 static const uint8_t g_32[] = {
277 static const uint8_t g_42[] = {
281 void ff_xface_generate_face(uint8_t *dst, uint8_t * const src)
283 int h, i, j, k, l, m;
285 for (j = 0; j < XFACE_HEIGHT; j++) {
286 for (i = 0; i < XFACE_WIDTH; i++) {
287 h = i + j * XFACE_WIDTH;
291 Compute k, encoding the bits *before* the current one, contained in the
292 image buffer. That is, given the grid:
298 m -> | 1| 2| 3| 4| 5|
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.
311 for (l = i - 2; l <= i + 2; l++) {
312 for (m = j - 2; m <= j; m++) {
313 if (l >= i && m == j)
315 if (l > 0 && l <= XFACE_WIDTH && m > 0)
316 k = 2*k + src[l + m * XFACE_WIDTH];
321 Use the guess for the given position and the computed value of k.
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
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 +----+----+----+ ... +----+----+
340 #define GEN(table) dst[h] ^= (table[k>>3]>>(7-(k&7)))&1
345 case 1: GEN(g_22); break;
346 case 2: GEN(g_21); break;
347 default: GEN(g_20); break;
352 case 1: GEN(g_12); break;
353 case 2: GEN(g_11); break;
354 default: GEN(g_10); break;
357 case XFACE_WIDTH - 1:
359 case 1: GEN(g_42); break;
360 case 2: GEN(g_41); break;
361 default: GEN(g_40); break;
366 case 1: GEN(g_32); break;
367 case 2: GEN(g_31); break;
368 default: GEN(g_30); break;
373 case 1: GEN(g_02); break;
374 case 2: GEN(g_01); break;
375 default: GEN(g_00); break;