FFmpeg: libavcodec/xface.c Source File

00001 /*
00002  * Copyright (c) 1990 James Ashton - Sydney University
00003  * Copyright (c) 2012 Stefano Sabatini
00004  *
00005  * This file is part of FFmpeg.
00006  *
00007  * FFmpeg is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU Lesser General Public
00009  * License as published by the Free Software Foundation; either
00010  * version 2.1 of the License, or (at your option) any later version.
00011  *
00012  * FFmpeg is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015  * Lesser General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU Lesser General Public
00018  * License along with FFmpeg; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
00020  */
00021 
00027 #include "xface.h"
00028 
00029 void ff_big_add(BigInt *b, uint8_t a)
00030 {
00031     int i;
00032     uint8_t *w;
00033     uint16_t c;
00034 
00035     a &= XFACE_WORDMASK;
00036     if (a == 0)
00037         return;
00038     w = b->words;
00039     c = a;
00040     for (i = 0; i < b->nb_words && c; i++) {
00041         c += *w;
00042         *w++ = c & XFACE_WORDMASK;
00043         c >>= XFACE_BITSPERWORD;
00044     }
00045     if (i == b->nb_words && c) {
00046         b->nb_words++;
00047         *w = c & XFACE_WORDMASK;
00048     }
00049 }
00050 
00051 void ff_big_div(BigInt *b, uint8_t a, uint8_t *r)
00052 {
00053     int i;
00054     uint8_t *w;
00055     uint16_t c, d;
00056 
00057     a &= XFACE_WORDMASK;
00058     if (a == 1 || b->nb_words == 0) {
00059         *r = 0;
00060         return;
00061     }
00062 
00063     /* treat this as a == WORDCARRY and just shift everything right a WORD */
00064     if (a == 0) {
00065         i = --b->nb_words;
00066         w = b->words;
00067         *r = *w;
00068         while (i--) {
00069             *w = *(w + 1);
00070             w++;
00071         }
00072         *w = 0;
00073         return;
00074     }
00075     i = b->nb_words;
00076     w = b->words + i;
00077     c = 0;
00078     while (i--) {
00079         c <<= XFACE_BITSPERWORD;
00080         c += *--w;
00081         d = c / (uint16_t)a;
00082         c = c % (uint16_t)a;
00083         *w = d & XFACE_WORDMASK;
00084     }
00085     *r = c;
00086     if (b->words[b->nb_words - 1] == 0)
00087         b->nb_words--;
00088 }
00089 
00090 void ff_big_mul(BigInt *b, uint8_t a)
00091 {
00092     int i;
00093     uint8_t *w;
00094     uint16_t c;
00095 
00096     a &= XFACE_WORDMASK;
00097     if (a == 1 || b->nb_words == 0)
00098         return;
00099     if (a == 0) {
00100         /* treat this as a == WORDCARRY and just shift everything left a WORD */
00101         i = b->nb_words++;
00102         w = b->words + i;
00103         while (i--) {
00104             *w = *(w - 1);
00105             w--;
00106         }
00107         *w = 0;
00108         return;
00109     }
00110     i = b->nb_words;
00111     w = b->words;
00112     c = 0;
00113     while (i--) {
00114         c += (uint16_t)*w * (uint16_t)a;
00115         *(w++) = c & XFACE_WORDMASK;
00116         c >>= XFACE_BITSPERWORD;
00117     }
00118     if (c) {
00119         b->nb_words++;
00120         *w = c & XFACE_WORDMASK;
00121     }
00122 }
00123 
00124 const ProbRange ff_xface_probranges_per_level[4][3] = {
00125     //  black      grey       white
00126     { {  1, 255}, {251, 0}, {  4, 251} }, /* Top of tree almost always grey */
00127     { {  1, 255}, {200, 0}, { 55, 200} },
00128     { { 33, 223}, {159, 0}, { 64, 159} },
00129     { {131,   0}, {  0, 0}, {125, 131} }, /* Grey disallowed at bottom */
00130 };
00131 
00132 const ProbRange ff_xface_probranges_2x2[16] = {
00133     { 0,   0},  {38,   0}, {38,  38},  {13, 152},
00134     {38,  76},  {13, 165}, {13, 178},  { 6, 230},
00135     {38, 114},  {13, 191}, {13, 204},  { 6, 236},
00136     {13, 217},  { 6, 242}, { 5, 248},  { 3, 253},
00137 };
00138 
00139 /*
00140  * The "guess the next pixel" tables follow. Normally there are 12
00141  * neighbour pixels used to give 1<<12 cases as we get closer to the
00142  * upper left corner lesser numbers of neighbours are available.
00143  *
00144  * Each byte in the tables represents 8 boolean values starting from
00145  * the most significant bit.
00146  */
00147 
00148 static const uint8_t g_00[] = {
00149     0x00, 0x00, 0x01, 0x01, 0x00, 0x00, 0xe3, 0xdf, 0x05, 0x17,
00150     0x05, 0x0f, 0x00, 0x1b, 0x0f, 0xdf, 0x00, 0x04, 0x00, 0x00,
00151     0x0d, 0x0f, 0x03, 0x7f, 0x00, 0x00, 0x00, 0x01, 0x00, 0x1d,
00152     0x45, 0x2f, 0x00, 0x00, 0x00, 0x0d, 0x00, 0x0a, 0xff, 0xff,
00153     0x00, 0x04, 0x00, 0x05, 0x01, 0x3f, 0xcf, 0xff, 0x10, 0x01,
00154     0x80, 0xc9, 0x0f, 0x0f, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00,
00155     0x1b, 0x1f, 0xff, 0xff, 0x4f, 0x54, 0x07, 0x1f, 0x57, 0x47,
00156     0xd7, 0x3d, 0xff, 0xff, 0x5f, 0x1f, 0x7f, 0xff, 0x7f, 0x7f,
00157     0x05, 0x0f, 0x01, 0x0f, 0x0f, 0x5f, 0x9b, 0xdf, 0x7f, 0xff,
00158     0x5f, 0x1d, 0x5f, 0xff, 0x0f, 0x1f, 0x0f, 0x5f, 0x03, 0x1f,
00159     0x4f, 0x5f, 0xf7, 0x7f, 0x7f, 0xff, 0x0d, 0x0f, 0xfb, 0xff,
00160     0xf7, 0xbf, 0x0f, 0x4f, 0xd7, 0x3f, 0x4f, 0x7f, 0xff, 0xff,
00161     0x67, 0xbf, 0x56, 0x25, 0x1f, 0x7f, 0x9f, 0xff, 0x00, 0x00,
00162     0x00, 0x05, 0x5f, 0x7f, 0x01, 0xdf, 0x14, 0x00, 0x05, 0x0f,
00163     0x07, 0xa2, 0x09, 0x0f, 0x00, 0x00, 0x00, 0x00, 0x0f, 0x5f,
00164     0x18, 0xd7, 0x94, 0x71, 0x00, 0x05, 0x1f, 0xb7, 0x0c, 0x07,
00165     0x0f, 0x0f, 0x00, 0x0f, 0x0f, 0x1f, 0x84, 0x8f, 0x05, 0x15,
00166     0x05, 0x0f, 0x4f, 0xff, 0x87, 0xdf, 0x05, 0x01, 0x10, 0x00,
00167     0x0f, 0x0f, 0x00, 0x08, 0x05, 0x04, 0x04, 0x01, 0x4f, 0xff,
00168     0x9f, 0x8f, 0x4a, 0x40, 0x5f, 0x5f, 0xff, 0xfe, 0xdf, 0xff,
00169     0x7f, 0xf7, 0xff, 0x7f, 0xff, 0xff, 0x7b, 0xff, 0x0f, 0xfd,
00170     0xd7, 0x5f, 0x4f, 0x7f, 0x7f, 0xdf, 0xff, 0xff, 0xff, 0xff,
00171     0xff, 0x77, 0xdf, 0x7f, 0x4f, 0xef, 0xff, 0xff, 0x77, 0xff,
00172     0xff, 0xff, 0x6f, 0xff, 0x0f, 0x4f, 0xff, 0xff, 0x9d, 0xff,
00173     0x0f, 0xef, 0xff, 0xdf, 0x6f, 0xff, 0xff, 0xff, 0x4f, 0xff,
00174     0xcd, 0x0f, 0x4f, 0xff, 0xff, 0xdf, 0x00, 0x00, 0x00, 0x0b,
00175     0x05, 0x02, 0x02, 0x0f, 0x04, 0x00, 0x00, 0x0c, 0x01, 0x06,
00176     0x00, 0x0f, 0x20, 0x03, 0x00, 0x00, 0x05, 0x0f, 0x40, 0x08,
00177     0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x0c, 0x0f, 0x01, 0x00,
00178     0x80, 0x00, 0x00, 0x00, 0x80, 0x00, 0x00, 0x14, 0x01, 0x05,
00179     0x01, 0x15, 0xaf, 0x0f, 0x00, 0x01, 0x10, 0x00, 0x08, 0x00,
00180     0x46, 0x0c, 0x20, 0x00, 0x88, 0x00, 0x0f, 0x15, 0xff, 0xdf,
00181     0x02, 0x00, 0x00, 0x0f, 0x7f, 0x5f, 0xdb, 0xff, 0x4f, 0x3e,
00182     0x05, 0x0f, 0x7f, 0xf7, 0x95, 0x4f, 0x0d, 0x0f, 0x01, 0x0f,
00183     0x4f, 0x5f, 0x9f, 0xdf, 0x25, 0x0e, 0x0d, 0x0d, 0x4f, 0x7f,
00184     0x8f, 0x0f, 0x0f, 0xfa, 0x04, 0x4f, 0x4f, 0xff, 0xf7, 0x77,
00185     0x47, 0xed, 0x05, 0x0f, 0xff, 0xff, 0xdf, 0xff, 0x4f, 0x6f,
00186     0xd8, 0x5f, 0x0f, 0x7f, 0xdf, 0x5f, 0x07, 0x0f, 0x94, 0x0d,
00187     0x1f, 0xff, 0xff, 0xff, 0x00, 0x02, 0x00, 0x03, 0x46, 0x57,
00188     0x01, 0x0d, 0x01, 0x08, 0x01, 0x0f, 0x47, 0x6c, 0x0d, 0x0f,
00189     0x02, 0x00, 0x00, 0x00, 0x0b, 0x4f, 0x00, 0x08, 0x05, 0x00,
00190     0x95, 0x01, 0x0f, 0x7f, 0x0c, 0x0f, 0x01, 0x0e, 0x00, 0x00,
00191     0x0f, 0x41, 0x00, 0x00, 0x04, 0x24, 0x0d, 0x0f, 0x0f, 0x7f,
00192     0xcf, 0xdf, 0x00, 0x00, 0x00, 0x00, 0x04, 0x40, 0x00, 0x00,
00193     0x06, 0x26, 0xcf, 0x05, 0xcf, 0x7f, 0xdf, 0xdf, 0x00, 0x00,
00194     0x17, 0x5f, 0xff, 0xfd, 0xff, 0xff, 0x46, 0x09, 0x4f, 0x5f,
00195     0x7f, 0xfd, 0xdf, 0xff, 0x0a, 0x88, 0xa7, 0x7f, 0x7f, 0xff,
00196     0xff, 0xff, 0x0f, 0x04, 0xdf, 0x7f, 0x4f, 0xff, 0x9f, 0xff,
00197     0x0e, 0xe6, 0xdf, 0xff, 0x7f, 0xff, 0xff, 0xff, 0x0f, 0xec,
00198     0x8f, 0x4f, 0x7f, 0xff, 0xdf, 0xff, 0x0f, 0xcf, 0xdf, 0xff,
00199     0x6f, 0x7f, 0xff, 0xff, 0x03, 0x0c, 0x9d, 0x0f, 0x7f, 0xff,
00200     0xff, 0xff,
00201 };
00202 
00203 static const uint8_t g_01[] = {
00204     0x37, 0x73, 0x00, 0x19, 0x57, 0x7f, 0xf5, 0xfb, 0x70, 0x33,
00205     0xf0, 0xf9, 0x7f, 0xff, 0xff, 0xff,
00206 };
00207 
00208 static const uint8_t g_02[] = {
00209     0x50,
00210 };
00211 
00212 static const uint8_t g_10[] = {
00213     0x00, 0x00, 0x00, 0x00, 0x50, 0x00, 0xf3, 0x5f, 0x84, 0x04,
00214     0x17, 0x9f, 0x04, 0x23, 0x05, 0xff, 0x00, 0x00, 0x00, 0x02,
00215     0x03, 0x03, 0x33, 0xd7, 0x05, 0x03, 0x5f, 0x3f, 0x17, 0x33,
00216     0xff, 0xff, 0x00, 0x80, 0x02, 0x04, 0x12, 0x00, 0x11, 0x57,
00217     0x05, 0x25, 0x05, 0x03, 0x35, 0xbf, 0x9f, 0xff, 0x07, 0x6f,
00218     0x20, 0x40, 0x17, 0x06, 0xfa, 0xe8, 0x01, 0x07, 0x1f, 0x9f,
00219     0x1f, 0xff, 0xff, 0xff,
00220 };
00221 
00222 static const uint8_t g_20[] = {
00223     0x04, 0x00, 0x01, 0x01, 0x43, 0x2e, 0xff, 0x3f,
00224 };
00225 
00226 static const uint8_t g_30[] = {
00227     0x11, 0x11, 0x11, 0x11, 0x51, 0x11, 0x13, 0x11, 0x11, 0x11,
00228     0x13, 0x11, 0x11, 0x11, 0x33, 0x11, 0x13, 0x11, 0x13, 0x13,
00229     0x13, 0x13, 0x31, 0x31, 0x11, 0x01, 0x11, 0x11, 0x71, 0x11,
00230     0x11, 0x75,
00231 };
00232 
00233 static const uint8_t g_40[] = {
00234     0x00, 0x0f, 0x00, 0x09, 0x00, 0x0d, 0x00, 0x0d, 0x00, 0x0f,
00235     0x00, 0x4e, 0xe4, 0x0d, 0x10, 0x0f, 0x00, 0x0f, 0x44, 0x4f,
00236     0x00, 0x1e, 0x0f, 0x0f, 0xae, 0xaf, 0x45, 0x7f, 0xef, 0xff,
00237     0x0f, 0xff, 0x00, 0x09, 0x01, 0x11, 0x00, 0x01, 0x1c, 0xdd,
00238     0x00, 0x15, 0x00, 0xff, 0x00, 0x10, 0x00, 0xfd, 0x00, 0x0f,
00239     0x4f, 0x5f, 0x3d, 0xff, 0xff, 0xff, 0x4f, 0xff, 0x1c, 0xff,
00240     0xdf, 0xff, 0x8f, 0xff, 0x00, 0x0d, 0x00, 0x00, 0x00, 0x15,
00241     0x01, 0x07, 0x00, 0x01, 0x02, 0x1f, 0x01, 0x11, 0x05, 0x7f,
00242     0x00, 0x1f, 0x41, 0x57, 0x1f, 0xff, 0x05, 0x77, 0x0d, 0x5f,
00243     0x4d, 0xff, 0x4f, 0xff, 0x0f, 0xff, 0x00, 0x00, 0x02, 0x05,
00244     0x00, 0x11, 0x05, 0x7d, 0x10, 0x15, 0x2f, 0xff, 0x40, 0x50,
00245     0x0d, 0xfd, 0x04, 0x0f, 0x07, 0x1f, 0x07, 0x7f, 0x0f, 0xbf,
00246     0x0d, 0x7f, 0x0f, 0xff, 0x4d, 0x7d, 0x0f, 0xff,
00247 };
00248 
00249 static const uint8_t g_11[] = {
00250     0x01, 0x13, 0x03, 0x7f,
00251 };
00252 
00253 static const uint8_t g_21[] = {
00254     0x17,
00255 };
00256 
00257 static const uint8_t g_31[] = {
00258     0x55, 0x57, 0x57, 0x7f,
00259 };
00260 
00261 static const uint8_t g_41[] = {
00262     0x01, 0x01, 0x01, 0x1f, 0x03, 0x1f, 0x3f, 0xff,
00263 };
00264 
00265 static const uint8_t g_12[] = {
00266     0x40,
00267 };
00268 
00269 static const uint8_t g_22[] = {
00270     0x00,
00271 };
00272 
00273 static const uint8_t g_32[] = {
00274     0x10,
00275 };
00276 
00277 static const uint8_t g_42[] = {
00278     0x10,
00279 };
00280 
00281 void ff_xface_generate_face(uint8_t *dst, uint8_t * const src)
00282 {
00283     int h, i, j, k, l, m;
00284 
00285     for (j = 0; j < XFACE_HEIGHT; j++) {
00286         for (i = 0; i < XFACE_WIDTH; i++) {
00287             h = i + j * XFACE_WIDTH;
00288             k = 0;
00289 
00290             /*
00291                Compute k, encoding the bits *before* the current one, contained in the
00292                image buffer. That is, given the grid:
00293 
00294                 l      i
00295                 |      |
00296                 v      v
00297                +--+--+--+--+--+
00298           m -> | 1| 2| 3| 4| 5|
00299                +--+--+--+--+--+
00300                | 6| 7| 8| 9|10|
00301                +--+--+--+--+--+
00302           j -> |11|12| *|  |  |
00303                +--+--+--+--+--+
00304 
00305                the value k for the pixel marked as "*" will contain the bit encoding of
00306                the values in the matrix marked from "1" to "12". In case the pixel is
00307                near the border of the grid, the number of values contained within the
00308                grid will be lesser than 12.
00309              */
00310 
00311             for (l = i - 2; l <= i + 2; l++) {
00312                 for (m = j - 2; m <= j; m++) {
00313                     if (l >= i && m == j)
00314                         continue;
00315                     if (l > 0 && l <= XFACE_WIDTH && m > 0)
00316                         k = 2*k + src[l + m * XFACE_WIDTH];
00317                 }
00318             }
00319 
00320             /*
00321               Use the guess for the given position and the computed value of k.
00322 
00323               The following table shows the number of digits in k, depending on
00324               the position of the pixel, and shows the corresponding guess table
00325               to use:
00326 
00327                  i=1  i=2  i=3       i=w-1 i=w
00328                +----+----+----+ ... +----+----+
00329            j=1 |  0 |  1 |  2 |     |  2 |  2 |
00330                |g22 |g12 |g02 |     |g42 |g32 |
00331                +----+----+----+ ... +----+----+
00332            j=2 |  3 |  5 |  7 |     |  6 |  5 |
00333                |g21 |g11 |g01 |     |g41 |g31 |
00334                +----+----+----+ ... +----+----+
00335            j=3 |  5 |  9 | 12 |     | 10 |  8 |
00336                |g20 |g10 |g00 |     |g40 |g30 |
00337                +----+----+----+ ... +----+----+
00338             */
00339 
00340 #define GEN(table) dst[h] ^= (table[k>>3]>>(7-(k&7)))&1
00341 
00342             switch (i) {
00343             case 1:
00344                 switch (j) {
00345                 case 1:  GEN(g_22); break;
00346                 case 2:  GEN(g_21); break;
00347                 default: GEN(g_20); break;
00348                 }
00349                 break;
00350             case 2:
00351                 switch (j) {
00352                 case 1:  GEN(g_12); break;
00353                 case 2:  GEN(g_11); break;
00354                 default: GEN(g_10); break;
00355                 }
00356                 break;
00357             case XFACE_WIDTH - 1:
00358                 switch (j) {
00359                 case 1:  GEN(g_42); break;
00360                 case 2:  GEN(g_41); break;
00361                 default: GEN(g_40); break;
00362                 }
00363                 break;
00364             case XFACE_WIDTH:
00365                 switch (j) {
00366                 case 1:  GEN(g_32); break;
00367                 case 2:  GEN(g_31); break;
00368                 default: GEN(g_30); break;
00369                 }
00370                 break;
00371             default:
00372                 switch (j) {
00373                 case 1:  GEN(g_02); break;
00374                 case 2:  GEN(g_01); break;
00375                 default: GEN(g_00); break;
00376                 }
00377                 break;
00378             }
00379         }
00380     }
00381 }