git.sesse.net Git - ffmpeg/blob - 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 "xface.h"
  28
  29 void 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
  51 void 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
  90 void 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
 124 const 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
 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},
 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
 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,
 200     0xff, 0xff,
 201 };
 202
 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,
 206 };
 207
 208 static const uint8_t g_02[] = {
 209     0x50,
 210 };
 211
 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,
 220 };
 221
 222 static const uint8_t g_20[] = {
 223     0x04, 0x00, 0x01, 0x01, 0x43, 0x2e, 0xff, 0x3f,
 224 };
 225
 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,
 230     0x11, 0x75,
 231 };
 232
 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,
 247 };
 248
 249 static const uint8_t g_11[] = {
 250     0x01, 0x13, 0x03, 0x7f,
 251 };
 252
 253 static const uint8_t g_21[] = {
 254     0x17,
 255 };
 256
 257 static const uint8_t g_31[] = {
 258     0x55, 0x57, 0x57, 0x7f,
 259 };
 260
 261 static const uint8_t g_41[] = {
 262     0x01, 0x01, 0x01, 0x1f, 0x03, 0x1f, 0x3f, 0xff,
 263 };
 264
 265 static const uint8_t g_12[] = {
 266     0x40,
 267 };
 268
 269 static const uint8_t g_22[] = {
 270     0x00,
 271 };
 272
 273 static const uint8_t g_32[] = {
 274     0x10,
 275 };
 276
 277 static const uint8_t g_42[] = {
 278     0x10,
 279 };
 280
 281 void 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 }