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.
27 #include "libavutil/avassert.h"
31 void ff_big_add(BigInt
*b
, uint8_t a
)
42 for (i
= 0; i
< b
->nb_words
&& c
; i
++) {
44 *w
++ = c
& XFACE_WORDMASK
;
45 c
>>= XFACE_BITSPERWORD
;
47 if (i
== b
->nb_words
&& c
) {
48 av_assert0(b
->nb_words
< XFACE_MAX_WORDS
);
50 *w
= c
& XFACE_WORDMASK
;
54 void ff_big_div(BigInt
*b
, uint8_t a
, uint8_t *r
)
61 if (a
== 1 || b
->nb_words
== 0) {
66 /* treat this as a == WORDCARRY and just shift everything right a WORD */
82 c
<<= XFACE_BITSPERWORD
;
86 *w
= d
& XFACE_WORDMASK
;
89 if (b
->words
[b
->nb_words
- 1] == 0)
93 void ff_big_mul(BigInt
*b
, uint8_t a
)
100 if (a
== 1 || b
->nb_words
== 0)
103 /* treat this as a == WORDCARRY and just shift everything left a WORD */
104 av_assert0(b
->nb_words
< XFACE_MAX_WORDS
);
118 c
+= (uint16_t)*w
* (uint16_t)a
;
119 *(w
++) = c
& XFACE_WORDMASK
;
120 c
>>= XFACE_BITSPERWORD
;
123 av_assert0(b
->nb_words
< XFACE_MAX_WORDS
);
125 *w
= c
& XFACE_WORDMASK
;
129 const ProbRange ff_xface_probranges_per_level
[4][3] = {
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 */
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},
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.
149 * Each byte in the tables represents 8 boolean values starting from
150 * the most significant bit.
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,
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,
213 static const uint8_t g_02
[] = {
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,
227 static const uint8_t g_20
[] = {
228 0x04, 0x00, 0x01, 0x01, 0x43, 0x2e, 0xff, 0x3f,
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,
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,
254 static const uint8_t g_11
[] = {
255 0x01, 0x13, 0x03, 0x7f,
258 static const uint8_t g_21
[] = {
262 static const uint8_t g_31
[] = {
263 0x55, 0x57, 0x57, 0x7f,
266 static const uint8_t g_41
[] = {
267 0x01, 0x01, 0x01, 0x1f, 0x03, 0x1f, 0x3f, 0xff,
270 static const uint8_t g_12
[] = {
274 static const uint8_t g_22
[] = {
278 static const uint8_t g_32
[] = {
282 static const uint8_t g_42
[] = {
286 void ff_xface_generate_face(uint8_t *dst
, uint8_t * const src
)
288 int h
, i
, j
, k
, l
, m
;
290 for (j
= 0; j
< XFACE_HEIGHT
; j
++) {
291 for (i
= 0; i
< XFACE_WIDTH
; i
++) {
292 h
= i
+ j
* XFACE_WIDTH
;
296 Compute k, encoding the bits *before* the current one, contained in the
297 image buffer. That is, given the grid:
303 m -> | 1| 2| 3| 4| 5|
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.
316 for (l
= i
- 2; l
<= i
+ 2; l
++) {
317 for (m
= j
- 2; m
<= j
; m
++) {
318 if (l
>= i
&& m
== j
)
320 if (l
> 0 && l
<= XFACE_WIDTH
&& m
> 0)
321 k
= 2*k
+ src
[l
+ m
* XFACE_WIDTH
];
326 Use the guess for the given position and the computed value of k.
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
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 +----+----+----+ ... +----+----+
345 #define GEN(table) dst[h] ^= (table[k>>3]>>(7-(k&7)))&1
350 case 1: GEN(g_22
); break;
351 case 2: GEN(g_21
); break;
352 default: GEN(g_20
); break;
357 case 1: GEN(g_12
); break;
358 case 2: GEN(g_11
); break;
359 default: GEN(g_10
); break;
362 case XFACE_WIDTH
- 1:
364 case 1: GEN(g_42
); break;
365 case 2: GEN(g_41
); break;
366 default: GEN(g_40
); break;
371 case 1: GEN(g_32
); break;
372 case 2: GEN(g_31
); break;
373 default: GEN(g_30
); break;
378 case 1: GEN(g_02
); break;
379 case 2: GEN(g_01
); break;
380 default: GEN(g_00
); break;