Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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_free(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.                     ur->rem_rung_list = av_realloc(ur->rem_rung_list,
  395.                                                    ur->rung_list_size +
  396.                                                    RUNG_SPACE);
  397.                     if (!ur->rem_rung_list) {
  398.                         av_free(ur->rem_rung_list);
  399.                         ctx->err = AVERROR(ENOMEM);
  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. }
  423.