ffmpeg/libavcodec/xface.c

   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
  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
  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
  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
 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 >= i && m == j)
 319                         continue;
 320                     if (l > 0 && 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 }