LCOV - code coverage report
Current view: top level - libavcodec - xface.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 101 107 94.4 %
Date: 2017-12-14 01:15:32 Functions: 4 4 100.0 %

          Line data    Source code
       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      454976 : void ff_big_add(BigInt *b, uint8_t a)
      32             : {
      33             :     int i;
      34             :     uint8_t *w;
      35             :     uint16_t c;
      36             : 
      37      454976 :     a &= XFACE_WORDMASK;
      38      454976 :     if (a == 0)
      39        9315 :         return;
      40      445661 :     w = b->words;
      41      445661 :     c = a;
      42      937128 :     for (i = 0; i < b->nb_words && c; i++) {
      43      491467 :         c += *w;
      44      491467 :         *w++ = c & XFACE_WORDMASK;
      45      491467 :         c >>= XFACE_BITSPERWORD;
      46             :     }
      47      445661 :     if (i == b->nb_words && c) {
      48         546 :         av_assert0(b->nb_words < XFACE_MAX_WORDS);
      49         546 :         b->nb_words++;
      50         546 :         *w = c & XFACE_WORDMASK;
      51             :     }
      52             : }
      53             : 
      54      454735 : 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      454735 :     a &= XFACE_WORDMASK;
      61      454735 :     if (a == 1 || b->nb_words == 0) {
      62         580 :         *r = 0;
      63         580 :         return;
      64             :     }
      65             : 
      66             :     /* treat this as a == WORDCARRY and just shift everything right a WORD */
      67      454155 :     if (a == 0) {
      68      194000 :         i = --b->nb_words;
      69      194000 :         w = b->words;
      70      194000 :         *r = *w;
      71    26526272 :         while (i--) {
      72    26138272 :             *w = *(w + 1);
      73    26138272 :             w++;
      74             :         }
      75      194000 :         *w = 0;
      76      194000 :         return;
      77             :     }
      78      260155 :     i = b->nb_words;
      79      260155 :     w = b->words + i;
      80      260155 :     c = 0;
      81    36107031 :     while (i--) {
      82    35586721 :         c <<= XFACE_BITSPERWORD;
      83    35586721 :         c += *--w;
      84    35586721 :         d = c / (uint16_t)a;
      85    35586721 :         c = c % (uint16_t)a;
      86    35586721 :         *w = d & XFACE_WORDMASK;
      87             :     }
      88      260155 :     *r = c;
      89      260155 :     if (b->words[b->nb_words - 1] == 0)
      90      193185 :         b->nb_words--;
      91             : }
      92             : 
      93      454976 : void ff_big_mul(BigInt *b, uint8_t a)
      94             : {
      95             :     int i;
      96             :     uint8_t *w;
      97             :     uint16_t c;
      98             : 
      99      454976 :     a &= XFACE_WORDMASK;
     100      454976 :     if (a == 1 || b->nb_words == 0)
     101        1098 :         return;
     102      453878 :     if (a == 0) {
     103             :         /* treat this as a == WORDCARRY and just shift everything left a WORD */
     104      192927 :         av_assert0(b->nb_words < XFACE_MAX_WORDS);
     105      192927 :         i = b->nb_words++;
     106      192927 :         w = b->words + i;
     107    26443035 :         while (i--) {
     108    26057181 :             *w = *(w - 1);
     109    26057181 :             w--;
     110             :         }
     111      192927 :         *w = 0;
     112      192927 :         return;
     113             :     }
     114      260951 :     i = b->nb_words;
     115      260951 :     w = b->words;
     116      260951 :     c = 0;
     117    36020301 :     while (i--) {
     118    35498399 :         c += (uint16_t)*w * (uint16_t)a;
     119    35498399 :         *(w++) = c & XFACE_WORDMASK;
     120    35498399 :         c >>= XFACE_BITSPERWORD;
     121             :     }
     122      260951 :     if (c) {
     123      193712 :         av_assert0(b->nb_words < XFACE_MAX_WORDS);
     124      193712 :         b->nb_words++;
     125      193712 :         *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         401 : void ff_xface_generate_face(uint8_t *dst, uint8_t * const src)
     287             : {
     288             :     int h, i, j, k, l, m;
     289             : 
     290       19649 :     for (j = 0; j < XFACE_HEIGHT; j++) {
     291      943152 :         for (i = 0; i < XFACE_WIDTH; i++) {
     292      923904 :             h = i + j * XFACE_WIDTH;
     293      923904 :             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     5543424 :             for (l = i - 2; l <= i + 2; l++) {
     317    18478080 :                 for (m = j - 2; m <= j; m++) {
     318    13858560 :                     if (l <= 0 || l >= i && m == j)
     319     3098928 :                         continue;
     320    10759632 :                     if (l <= XFACE_WIDTH && m > 0)
     321    10217480 :                         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      923904 :             switch (i) {
     348       19248 :             case 1:
     349       19248 :                 switch (j) {
     350         401 :                 case 1:  GEN(g_22); break;
     351         401 :                 case 2:  GEN(g_21); break;
     352       18446 :                 default: GEN(g_20); break;
     353             :                 }
     354       19248 :                 break;
     355       19248 :             case 2:
     356       19248 :                 switch (j) {
     357         401 :                 case 1:  GEN(g_12); break;
     358         401 :                 case 2:  GEN(g_11); break;
     359       18446 :                 default: GEN(g_10); break;
     360             :                 }
     361       19248 :                 break;
     362       19248 :             case XFACE_WIDTH - 1:
     363       19248 :                 switch (j) {
     364         401 :                 case 1:  GEN(g_42); break;
     365         401 :                 case 2:  GEN(g_41); break;
     366       18446 :                 default: GEN(g_40); break;
     367             :                 }
     368       19248 :                 break;
     369           0 :             case XFACE_WIDTH:
     370           0 :                 switch (j) {
     371           0 :                 case 1:  GEN(g_32); break;
     372           0 :                 case 2:  GEN(g_31); break;
     373           0 :                 default: GEN(g_30); break;
     374             :                 }
     375           0 :                 break;
     376      866160 :             default:
     377      866160 :                 switch (j) {
     378       18045 :                 case 1:  GEN(g_02); break;
     379       18045 :                 case 2:  GEN(g_01); break;
     380      830070 :                 default: GEN(g_00); break;
     381             :                 }
     382      866160 :                 break;
     383             :             }
     384             :         }
     385             :     }
     386         401 : }

Generated by: LCOV version 1.13