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
29void 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
51void 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
90void 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
124const 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
132const 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
148static 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
203static 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
208static const uint8_t g_02[] = {
209    0x50,
210};
211
212static 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
222static const uint8_t g_20[] = {
223    0x04, 0x00, 0x01, 0x01, 0x43, 0x2e, 0xff, 0x3f,
224};
225
226static 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
233static 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
249static const uint8_t g_11[] = {
250    0x01, 0x13, 0x03, 0x7f,
251};
252
253static const uint8_t g_21[] = {
254    0x17,
255};
256
257static const uint8_t g_31[] = {
258    0x55, 0x57, 0x57, 0x7f,
259};
260
261static const uint8_t g_41[] = {
262    0x01, 0x01, 0x01, 0x1f, 0x03, 0x1f, 0x3f, 0xff,
263};
264
265static const uint8_t g_12[] = {
266    0x40,
267};
268
269static const uint8_t g_22[] = {
270    0x00,
271};
272
273static const uint8_t g_32[] = {
274    0x10,
275};
276
277static const uint8_t g_42[] = {
278    0x10,
279};
280
281void 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}
382