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