LCOV - code coverage report
Current view: top level - libavcodec - elsdec.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 89 109 81.7 %
Date: 2017-12-15 02:19:58 Functions: 5 5 100.0 %

          Line data    Source code
       1             : /*
       2             :  * ELS (Entropy Logarithmic-Scale) decoder
       3             :  *
       4             :  * Copyright (c) 2013 Maxim Poliakovski
       5             :  *
       6             :  * This file is part of FFmpeg.
       7             :  *
       8             :  * FFmpeg is free software; you can redistribute it and/or
       9             :  * modify it under the terms of the GNU Lesser General Public
      10             :  * License as published by the Free Software Foundation; either
      11             :  * version 2.1 of the License, or (at your option) any later version.
      12             :  *
      13             :  * FFmpeg is distributed in the hope that it will be useful,
      14             :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      15             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      16             :  * Lesser General Public License for more details.
      17             :  *
      18             :  * You should have received a copy of the GNU Lesser General Public
      19             :  * License along with FFmpeg; if not, write to the Free Software
      20             :  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
      21             :  */
      22             : 
      23             : /**
      24             :  * @file
      25             :  * Entropy Logarithmic-Scale binary arithmetic decoder
      26             :  */
      27             : 
      28             : #include <math.h>
      29             : #include <stdint.h>
      30             : 
      31             : #include "libavutil/common.h"
      32             : #include "libavutil/intreadwrite.h"
      33             : 
      34             : #include "avcodec.h"
      35             : #include "elsdec.h"
      36             : 
      37             : /* ELS coder constants and structures. */
      38             : #define ELS_JOTS_PER_BYTE   36
      39             : #define ELS_MAX             (1 << 24)
      40             : #define RUNG_SPACE          (64 * sizeof(ElsRungNode))
      41             : 
      42             : /* ELS coder tables. */
      43             : static const struct Ladder {
      44             :     int8_t  AMps;
      45             :     int8_t  ALps;
      46             :     uint8_t next0;
      47             :     uint8_t next1;
      48             : } Ladder[174] = {
      49             :     { -6,   -5,   2,   1 },
      50             :     { -2,  -12,   3,   6 },
      51             :     { -2,  -12,   4,   6 },
      52             :     { -1,  -16,   7,   5 },
      53             :     { -1,  -16,   8,  10 },
      54             :     { -5,   -6,  11,   9 },
      55             :     { -6,   -5,  10,   5 },
      56             :     { -1,  -18,  13,  11 },
      57             :     { -1,  -18,  12,  14 },
      58             :     { -6,   -5,  15,  18 },
      59             :     { -5,   -6,  14,   9 },
      60             :     { -3,   -8,  17,  15 },
      61             :     { -1,  -20,  20,  16 },
      62             :     { -1,  -20,  23,  17 },
      63             :     { -3,   -8,  16,  18 },
      64             :     { -5,   -6,  19,  26 },
      65             :     { -3,   -9,  22,  24 },
      66             :     { -3,   -9,  21,  19 },
      67             :     { -5,   -6,  24,  26 },
      68             :     { -4,   -7,  27,  25 },
      69             :     { -1,  -22,  34,  28 },
      70             :     { -2,  -11,  29,  27 },
      71             :     { -2,  -11,  28,  30 },
      72             :     { -1,  -22,  39,  29 },
      73             :     { -4,   -7,  30,  32 },
      74             :     { -6,   -5,  33,  31 },
      75             :     { -6,   -5,  32,  25 },
      76             :     { -3,   -8,  35,  33 },
      77             :     { -2,  -12,  36,  38 },
      78             :     { -2,  -12,  37,  35 },
      79             :     { -3,   -8,  38,  40 },
      80             :     { -6,   -5,  41,  48 },
      81             :     { -6,   -5,  40,  31 },
      82             :     { -5,   -6,  43,  41 },
      83             :     { -1,  -24,  94,  42 },
      84             :     { -3,   -8,  45,  43 },
      85             :     { -2,  -12,  42,  44 },
      86             :     { -2,  -12,  47,  45 },
      87             :     { -3,   -8,  44,  46 },
      88             :     { -1,  -24, 125,  47 },
      89             :     { -5,   -6,  46,  48 },
      90             :     { -6,   -5,  49,  49 },
      91             :     { -2,  -13, 152, 164 },
      92             :     { -4,   -7,  51,  49 },
      93             :     { -3,   -9, 164, 168 },
      94             :     { -3,   -9,  55,  51 },
      95             :     { -4,   -7, 168, 170 },
      96             :     { -2,  -13,  67,  55 },
      97             :     { -6,   -5, 170,  49 },
      98             :     { -6,   -5,  51, 170 },
      99             :     { -1,  -72,  50,  74 },
     100             :     { -4,   -7,  53,  49 },
     101             :     { -1,  -61,  50,  74 },
     102             :     { -3,   -8,  55,  49 },
     103             :     { -1,  -51,  52,  76 },
     104             :     { -3,   -9,  57,  51 },
     105             :     { -1,  -46,  54,  76 },
     106             :     { -2,  -10,  59,  53 },
     107             :     { -1,  -43,  56,  78 },
     108             :     { -2,  -11,  61,  53 },
     109             :     { -1,  -41,  58,  80 },
     110             :     { -2,  -12,  63,  55 },
     111             :     { -1,  -39,  60,  82 },
     112             :     { -2,  -12,  65,  55 },
     113             :     { -1,  -37,  62,  84 },
     114             :     { -2,  -13,  67,  57 },
     115             :     { -1,  -36,  64,  86 },
     116             :     { -1,  -14,  69,  59 },
     117             :     { -1,  -35,  66,  88 },
     118             :     { -1,  -14,  71,  59 },
     119             :     { -1,  -34,  68,  90 },
     120             :     { -1,  -15,  73,  61 },
     121             :     { -1,  -33,  70,  92 },
     122             :     { -1,  -15,  75,  61 },
     123             :     { -1,  -32,  72,  94 },
     124             :     { -1,  -15,  77,  63 },
     125             :     { -1,  -31,  74,  96 },
     126             :     { -1,  -16,  79,  65 },
     127             :     { -1,  -31,  76,  98 },
     128             :     { -1,  -16,  81,  67 },
     129             :     { -1,  -30,  78, 100 },
     130             :     { -1,  -17,  83,  67 },
     131             :     { -1,  -29,  80, 102 },
     132             :     { -1,  -17,  85,  69 },
     133             :     { -1,  -29,  82, 104 },
     134             :     { -1,  -18,  87,  71 },
     135             :     { -1,  -28,  84, 104 },
     136             :     { -1,  -18,  89,  73 },
     137             :     { -1,  -28,  86, 108 },
     138             :     { -1,  -18,  91,  73 },
     139             :     { -1,  -27,  88, 108 },
     140             :     { -1,  -19,  93,  75 },
     141             :     { -1,  -27,  90, 112 },
     142             :     { -1,  -19,  95,  77 },
     143             :     { -1,  -26,  92, 112 },
     144             :     { -1,  -20,  97,  79 },
     145             :     { -1,  -26,  94, 114 },
     146             :     { -1,  -20,  99,  81 },
     147             :     { -1,  -25,  96, 116 },
     148             :     { -1,  -20, 101,  83 },
     149             :     { -1,  -25,  98, 118 },
     150             :     { -1,  -21, 103,  83 },
     151             :     { -1,  -24, 100, 120 },
     152             :     { -1,  -21, 105,  85 },
     153             :     { -1,  -24, 102, 122 },
     154             :     { -1,  -22, 107,  87 },
     155             :     { -1,  -23, 104, 124 },
     156             :     { -1,  -22, 109,  89 },
     157             :     { -1,  -23, 106, 126 },
     158             :     { -1,  -22, 111,  91 },
     159             :     { -1,  -22, 108, 128 },
     160             :     { -1,  -23, 113,  93 },
     161             :     { -1,  -22, 110, 130 },
     162             :     { -1,  -23, 115,  95 },
     163             :     { -1,  -22, 112, 132 },
     164             :     { -1,  -24, 117,  97 },
     165             :     { -1,  -21, 114, 134 },
     166             :     { -1,  -24, 119,  99 },
     167             :     { -1,  -21, 116, 136 },
     168             :     { -1,  -25, 121, 101 },
     169             :     { -1,  -20, 118, 136 },
     170             :     { -1,  -25, 123, 103 },
     171             :     { -1,  -20, 120, 138 },
     172             :     { -1,  -26, 125, 105 },
     173             :     { -1,  -20, 122, 140 },
     174             :     { -1,  -26, 127, 107 },
     175             :     { -1,  -19, 124, 142 },
     176             :     { -1,  -27, 129, 107 },
     177             :     { -1,  -19, 126, 144 },
     178             :     { -1,  -27, 131, 111 },
     179             :     { -1,  -18, 128, 146 },
     180             :     { -1,  -28, 133, 111 },
     181             :     { -1,  -18, 130, 146 },
     182             :     { -1,  -28, 135, 115 },
     183             :     { -1,  -18, 132, 148 },
     184             :     { -1,  -29, 137, 115 },
     185             :     { -1,  -17, 134, 150 },
     186             :     { -1,  -29, 139, 117 },
     187             :     { -1,  -17, 136, 152 },
     188             :     { -1,  -30, 141, 119 },
     189             :     { -1,  -16, 138, 152 },
     190             :     { -1,  -31, 143, 121 },
     191             :     { -1,  -16, 140, 154 },
     192             :     { -1,  -31, 145, 123 },
     193             :     { -1,  -15, 142, 156 },
     194             :     { -1,  -32, 147, 125 },
     195             :     { -1,  -15, 144, 158 },
     196             :     { -1,  -33, 149, 127 },
     197             :     { -1,  -15, 146, 158 },
     198             :     { -1,  -34, 151, 129 },
     199             :     { -1,  -14, 148, 160 },
     200             :     { -1,  -35, 153, 131 },
     201             :     { -1,  -14, 150, 160 },
     202             :     { -1,  -36, 155, 133 },
     203             :     { -2,  -13, 152, 162 },
     204             :     { -1,  -37, 157, 135 },
     205             :     { -2,  -12, 154, 164 },
     206             :     { -1,  -39, 159, 137 },
     207             :     { -2,  -12, 156, 164 },
     208             :     { -1,  -41, 161, 139 },
     209             :     { -2,  -11, 158, 166 },
     210             :     { -1,  -43, 163, 141 },
     211             :     { -2,  -10, 160, 166 },
     212             :     { -1,  -46, 165, 143 },
     213             :     { -3,   -9, 162, 168 },
     214             :     { -1,  -51, 167, 143 },
     215             :     { -3,   -8, 164, 170 },
     216             :     { -1,  -61, 169, 145 },
     217             :     { -4,   -7, 166, 170 },
     218             :     { -1,  -72, 169, 145 },
     219             :     { -6,   -5, 168,  49 },
     220             :     {  0, -108, 171, 171 },
     221             :     {  0, -108, 172, 172 },
     222             :     { -6,   -5, 173, 173 },
     223             : };
     224             : 
     225             : static const uint32_t els_exp_tab[ELS_JOTS_PER_BYTE * 4 + 1] = {
     226             :            0,        0,       0,       0,       0,       0,         0,        0,
     227             :            0,        0,       0,       0,       0,       0,         0,        0,
     228             :            0,        0,       0,       0,       0,       0,         0,        0,
     229             :            0,        0,       0,       0,       0,       0,         0,        0,
     230             :            0,        0,       0,       0,       1,       1,         1,        1,
     231             :            1,        2,       2,       2,       3,       4,         4,        5,
     232             :            6,        7,       8,      10,      11,      13,        16,       18,
     233             :           21,       25,      29,      34,      40,      47,        54,       64,
     234             :           74,       87,     101,     118,     138,      161,      188,      219,
     235             :          256,      298,     348,     406,     474,      552,      645,      752,
     236             :          877,     1024,    1194,    1393,    1625,     1896,     2211,     2580,
     237             :         3010,     3511,    4096,    4778,    5573,     6501,     7584,     8847,
     238             :        10321,    12040,   14045,   16384,   19112,    22295,    26007,    30339,
     239             :        35391,    41285,   48160,   56180,   65536,    76288,    89088,   103936,
     240             :       121344,   141312,  165120,  192512,  224512,   262144,   305664,   356608,
     241             :       416000,   485376,  566016,  660480,  770560,   898816,  1048576,  1223168,
     242             :      1426688,  1664256, 1941504, 2264832, 2642176,  3082240,  3595520,  4194304,
     243             :      4892672,  5707520, 6657792, 7766784, 9060096, 10568960, 12328960, 14382080,
     244             :     16777216,
     245             : };
     246             : 
     247         136 : void ff_els_decoder_init(ElsDecCtx *ctx, const uint8_t *in, size_t data_size)
     248             : {
     249             :     int nbytes;
     250             : 
     251             :     /* consume up to 3 bytes from the input data */
     252         136 :     if (data_size >= 3) {
     253         136 :         ctx->x = AV_RB24(in);
     254         136 :         nbytes = 3;
     255           0 :     } else if (data_size == 2) {
     256           0 :         ctx->x = AV_RB16(in);
     257           0 :         nbytes = 2;
     258             :     } else {
     259           0 :         ctx->x = *in;
     260           0 :         nbytes = 1;
     261             :     }
     262             : 
     263         136 :     ctx->in_buf    = in + nbytes;
     264         136 :     ctx->data_size = data_size - nbytes;
     265         136 :     ctx->err       = 0;
     266         136 :     ctx->j         = ELS_JOTS_PER_BYTE;
     267         136 :     ctx->t         = ELS_MAX;
     268         136 :     ctx->diff      = FFMIN(ELS_MAX - ctx->x,
     269             :                            ELS_MAX - els_exp_tab[ELS_JOTS_PER_BYTE * 4 - 1]);
     270         136 : }
     271             : 
     272         136 : void ff_els_decoder_uninit(ElsUnsignedRung *rung)
     273             : {
     274         136 :     av_free(rung->rem_rung_list);
     275         136 : }
     276             : 
     277      104553 : static int els_import_byte(ElsDecCtx *ctx)
     278             : {
     279      104553 :     if (!ctx->data_size) {
     280           0 :         ctx->err = AVERROR_EOF;
     281           0 :         return AVERROR_EOF;
     282             :     }
     283      104553 :     ctx->x   = (ctx->x << 8) | *ctx->in_buf++;
     284      104553 :     ctx->data_size--;
     285      104553 :     ctx->j  += ELS_JOTS_PER_BYTE;
     286      104553 :     ctx->t <<= 8;
     287             : 
     288      104553 :     return 0;
     289             : }
     290             : 
     291     1264774 : int ff_els_decode_bit(ElsDecCtx *ctx, uint8_t *rung)
     292             : {
     293             :     int z, bit, ret;
     294     1264774 :     const uint32_t *pAllowable = &els_exp_tab[ELS_JOTS_PER_BYTE * 3];
     295             : 
     296     1264774 :     if (ctx->err)
     297           0 :         return 0;
     298             : 
     299     1264774 :     z          = pAllowable[ctx->j + Ladder[*rung].ALps];
     300     1264774 :     ctx->t    -= z;
     301     1264774 :     ctx->diff -= z;
     302     1264774 :     if (ctx->diff > 0)
     303      382255 :         return *rung & 1;   /* shortcut for x < t > pAllowable[j - 1] */
     304             : 
     305      882519 :     if (ctx->t > ctx->x) {  /* decode most probable symbol (MPS) */
     306      600153 :         ctx->j += Ladder[*rung].AMps;
     307     1725339 :         while (ctx->t > pAllowable[ctx->j])
     308      525033 :             ctx->j++;
     309             : 
     310      600153 :         if (ctx->j <= 0) { /* MPS: import one byte from bytestream. */
     311       34972 :             ret = els_import_byte(ctx);
     312       34972 :             if (ret < 0)
     313           0 :                 return ret;
     314             :         }
     315             : 
     316      600153 :         z     = ctx->t;
     317      600153 :         bit   = *rung & 1;
     318      600153 :         *rung = Ladder[*rung].next0;
     319             :     } else { /* decode less probable symbol (LPS) */
     320      282366 :         ctx->x -= ctx->t;
     321      282366 :         ctx->t  = z;
     322             : 
     323      282366 :         ctx->j += Ladder[*rung].ALps;
     324      282366 :         if (ctx->j <= 0) {
     325             :             /* LPS: import one byte from bytestream. */
     326       69563 :             z <<= 8;
     327       69563 :             ret = els_import_byte(ctx);
     328       69563 :             if (ret < 0)
     329           0 :                 return ret;
     330       69563 :             if (ctx->j <= 0) {
     331             :                 /* LPS: import second byte from bytestream. */
     332          18 :                 z <<= 8;
     333          18 :                 ret = els_import_byte(ctx);
     334          18 :                 if (ret < 0)
     335           0 :                     return ret;
     336          38 :                 while (pAllowable[ctx->j - 1] >= z)
     337           2 :                     ctx->j--;
     338             :             }
     339             :         }
     340             : 
     341      282366 :         bit   = !(*rung & 1);
     342      282366 :         *rung = Ladder[*rung].next1;
     343             :     }
     344             : 
     345      882519 :     ctx->diff = FFMIN(z - ctx->x, z - pAllowable[ctx->j - 1]);
     346             : 
     347      882519 :     return bit;
     348             : }
     349             : 
     350       15033 : unsigned ff_els_decode_unsigned(ElsDecCtx *ctx, ElsUnsignedRung *ur)
     351             : {
     352             :     int i, n, r, bit;
     353             :     ElsRungNode *rung_node;
     354             : 
     355       15033 :     if (ctx->err)
     356           0 :         return 0;
     357             : 
     358             :     /* decode unary prefix */
     359       91011 :     for (n = 0; n < ELS_EXPGOLOMB_LEN + 1; n++)
     360       91011 :         if (ff_els_decode_bit(ctx, &ur->prefix_rung[n]))
     361       15033 :             break;
     362             : 
     363             :     /* handle the error/overflow case */
     364       15033 :     if (ctx->err || n >= ELS_EXPGOLOMB_LEN) {
     365           0 :         ctx->err = AVERROR_INVALIDDATA;
     366           0 :         return 0;
     367             :     }
     368             : 
     369             :     /* handle the zero case */
     370       15033 :     if (!n)
     371        1916 :         return 0;
     372             : 
     373             :     /* initialize probability tree */
     374       13117 :     if (!ur->rem_rung_list) {
     375         136 :         ur->rem_rung_list = av_realloc(NULL, RUNG_SPACE);
     376         136 :         if (!ur->rem_rung_list) {
     377           0 :             ctx->err = AVERROR(ENOMEM);
     378           0 :             return 0;
     379             :         }
     380         136 :         memset(ur->rem_rung_list, 0, RUNG_SPACE);
     381         136 :         ur->rung_list_size = RUNG_SPACE;
     382         136 :         ur->avail_index    = ELS_EXPGOLOMB_LEN;
     383             :     }
     384             : 
     385             :     /* decode the remainder */
     386       89095 :     for (i = 0, r = 0, bit = 0; i < n; i++) {
     387       75978 :         if (!i)
     388       13117 :             rung_node = &ur->rem_rung_list[n];
     389             :         else {
     390       62861 :             if (!rung_node->next_index) {
     391        6906 :                 if (ur->rung_list_size <= (ur->avail_index + 2) * sizeof(ElsRungNode)) {
     392             :                     // remember rung_node position
     393         174 :                     ptrdiff_t pos     = rung_node - ur->rem_rung_list;
     394         174 :                     ur->rem_rung_list = av_realloc(ur->rem_rung_list,
     395         174 :                                                    ur->rung_list_size +
     396             :                                                    RUNG_SPACE);
     397         174 :                     if (!ur->rem_rung_list) {
     398           0 :                         av_free(ur->rem_rung_list);
     399           0 :                         ctx->err = AVERROR(ENOMEM);
     400           0 :                         return 0;
     401             :                     }
     402         174 :                     memset((uint8_t *) ur->rem_rung_list + ur->rung_list_size, 0,
     403             :                            RUNG_SPACE);
     404         174 :                     ur->rung_list_size += RUNG_SPACE;
     405             :                     // restore rung_node position in the new list
     406         174 :                     rung_node = &ur->rem_rung_list[pos];
     407             :                 }
     408        6906 :                 rung_node->next_index = ur->avail_index;
     409        6906 :                 ur->avail_index      += 2;
     410             :             }
     411       62861 :             rung_node = &ur->rem_rung_list[rung_node->next_index + bit];
     412             :         }
     413             : 
     414       75978 :         bit = ff_els_decode_bit(ctx, &rung_node->rung);
     415       75978 :         if (ctx->err)
     416           0 :             return bit;
     417             : 
     418       75978 :         r = (r << 1) + bit;
     419             :     }
     420             : 
     421       13117 :     return (1 << n) - 1 + r; /* make value from exp golomb code */
     422             : }

Generated by: LCOV version 1.13