git.sesse.net Git - ffmpeg/blob - libavcodec/elsdec.c

   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 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     if (data_size >= 3) {
 253         ctx->x = AV_RB24(in);
 254         nbytes = 3;
 255     } else if (data_size == 2) {
 256         ctx->x = AV_RB16(in);
 257         nbytes = 2;
 258     } else {
 259         ctx->x = *in;
 260         nbytes = 1;
 261     }
 262
 263     ctx->in_buf    = in + nbytes;
 264     ctx->data_size = data_size - nbytes;
 265     ctx->err       = 0;
 266     ctx->j         = ELS_JOTS_PER_BYTE;
 267     ctx->t         = ELS_MAX;
 268     ctx->diff      = FFMIN(ELS_MAX - ctx->x,
 269                            ELS_MAX - els_exp_tab[ELS_JOTS_PER_BYTE * 4 - 1]);
 270 }
 271
 272 void ff_els_decoder_uninit(ElsUnsignedRung *rung)
 273 {
 274     av_freep(&rung->rem_rung_list);
 275 }
 276
 277 static int els_import_byte(ElsDecCtx *ctx)
 278 {
 279     if (!ctx->data_size) {
 280         ctx->err = AVERROR_EOF;
 281         return AVERROR_EOF;
 282     }
 283     ctx->x   = (ctx->x << 8) | *ctx->in_buf++;
 284     ctx->data_size--;
 285     ctx->j  += ELS_JOTS_PER_BYTE;
 286     ctx->t <<= 8;
 287
 288     return 0;
 289 }
 290
 291 int ff_els_decode_bit(ElsDecCtx *ctx, uint8_t *rung)
 292 {
 293     int z, bit, ret;
 294     const uint32_t *pAllowable = &els_exp_tab[ELS_JOTS_PER_BYTE * 3];
 295
 296     if (ctx->err)
 297         return 0;
 298
 299     z          = pAllowable[ctx->j + Ladder[*rung].ALps];
 300     ctx->t    -= z;
 301     ctx->diff -= z;
 302     if (ctx->diff > 0)
 303         return *rung & 1;   /* shortcut for x < t > pAllowable[j - 1] */
 304
 305     if (ctx->t > ctx->x) {  /* decode most probable symbol (MPS) */
 306         ctx->j += Ladder[*rung].AMps;
 307         while (ctx->t > pAllowable[ctx->j])
 308             ctx->j++;
 309
 310         if (ctx->j <= 0) { /* MPS: import one byte from bytestream. */
 311             ret = els_import_byte(ctx);
 312             if (ret < 0)
 313                 return ret;
 314         }
 315
 316         z     = ctx->t;
 317         bit   = *rung & 1;
 318         *rung = Ladder[*rung].next0;
 319     } else { /* decode less probable symbol (LPS) */
 320         ctx->x -= ctx->t;
 321         ctx->t  = z;
 322
 323         ctx->j += Ladder[*rung].ALps;
 324         if (ctx->j <= 0) {
 325             /* LPS: import one byte from bytestream. */
 326             z <<= 8;
 327             ret = els_import_byte(ctx);
 328             if (ret < 0)
 329                 return ret;
 330             if (ctx->j <= 0) {
 331                 /* LPS: import second byte from bytestream. */
 332                 z <<= 8;
 333                 ret = els_import_byte(ctx);
 334                 if (ret < 0)
 335                     return ret;
 336                 while (pAllowable[ctx->j - 1] >= z)
 337                     ctx->j--;
 338             }
 339         }
 340
 341         bit   = !(*rung & 1);
 342         *rung = Ladder[*rung].next1;
 343     }
 344
 345     ctx->diff = FFMIN(z - ctx->x, z - pAllowable[ctx->j - 1]);
 346
 347     return bit;
 348 }
 349
 350 unsigned ff_els_decode_unsigned(ElsDecCtx *ctx, ElsUnsignedRung *ur)
 351 {
 352     int i, n, r, bit;
 353     ElsRungNode *rung_node;
 354
 355     if (ctx->err)
 356         return 0;
 357
 358     /* decode unary prefix */
 359     for (n = 0; n < ELS_EXPGOLOMB_LEN + 1; n++)
 360         if (ff_els_decode_bit(ctx, &ur->prefix_rung[n]))
 361             break;
 362
 363     /* handle the error/overflow case */
 364     if (ctx->err || n >= ELS_EXPGOLOMB_LEN) {
 365         ctx->err = AVERROR_INVALIDDATA;
 366         return 0;
 367     }
 368
 369     /* handle the zero case */
 370     if (!n)
 371         return 0;
 372
 373     /* initialize probability tree */
 374     if (!ur->rem_rung_list) {
 375         ur->rem_rung_list = av_realloc(NULL, RUNG_SPACE);
 376         if (!ur->rem_rung_list) {
 377             ctx->err = AVERROR(ENOMEM);
 378             return 0;
 379         }
 380         memset(ur->rem_rung_list, 0, RUNG_SPACE);
 381         ur->rung_list_size = RUNG_SPACE;
 382         ur->avail_index    = ELS_EXPGOLOMB_LEN;
 383     }
 384
 385     /* decode the remainder */
 386     for (i = 0, r = 0, bit = 0; i < n; i++) {
 387         if (!i)
 388             rung_node = &ur->rem_rung_list[n];
 389         else {
 390             if (!rung_node->next_index) {
 391                 if (ur->rung_list_size <= (ur->avail_index + 2) * sizeof(ElsRungNode)) {
 392                     // remember rung_node position
 393                     ptrdiff_t pos     = rung_node - ur->rem_rung_list;
 394                     ctx->err = av_reallocp(&ur->rem_rung_list,
 395                                                    ur->rung_list_size +
 396                                                    RUNG_SPACE);
 397                     if (ctx->err < 0) {
 398                         return 0;
 399                     }
 400                     memset((uint8_t *) ur->rem_rung_list + ur->rung_list_size, 0,
 401                            RUNG_SPACE);
 402                     ur->rung_list_size += RUNG_SPACE;
 403                     // restore rung_node position in the new list
 404                     rung_node = &ur->rem_rung_list[pos];
 405                 }
 406                 rung_node->next_index = ur->avail_index;
 407                 ur->avail_index      += 2;
 408             }
 409             rung_node = &ur->rem_rung_list[rung_node->next_index + bit];
 410         }
 411
 412         bit = ff_els_decode_bit(ctx, &rung_node->rung);
 413         if (ctx->err)
 414             return bit;
 415
 416         r = (r << 1) + bit;
 417     }
 418
 419     return (1 << n) - 1 + r; /* make value from exp golomb code */
 420 }