msac.c 6.83 KB
Newer Older
1
/*
Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
2 3 4
 * Copyright © 2018, VideoLAN and dav1d authors
 * Copyright © 2018, Two Orioles, LLC
 * All rights reserved.
5
 *
Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice, this
 *    list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 27 28 29 30 31 32 33 34 35 36
 */

#include "config.h"

#include <assert.h>
#include <limits.h>

#include "common/intops.h"

#include "src/msac.h"

37
#define EC_PROB_SHIFT 6
38 39
#define EC_MIN_PROB 4  // must be <= (1<<EC_PROB_SHIFT)/16

Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
40
#define EC_WIN_SIZE (sizeof(ec_win) << 3)
41

Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
42 43 44 45 46 47 48 49 50 51 52 53
static inline void ctx_refill(MsacContext *s) {
    const uint8_t *buf_pos = s->buf_pos;
    const uint8_t *buf_end = s->buf_end;
    int c = EC_WIN_SIZE - s->cnt - 24;
    ec_win dif = s->dif;
    while (c >= 0 && buf_pos < buf_end) {
        dif ^= ((ec_win)*buf_pos++) << c;
        c -= 8;
    }
    s->dif = dif;
    s->cnt = EC_WIN_SIZE - c - 24;
    s->buf_pos = buf_pos;
54 55
}

Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
56 57 58 59 60 61 62 63 64 65 66 67 68
/* Takes updated dif and range values, renormalizes them so that
 * 32768 <= rng < 65536 (reading more bytes from the stream into dif if
 * necessary), and stores them back in the decoder context.
 * dif: The new value of dif.
 * rng: The new value of the range. */
static inline void ctx_norm(MsacContext *s, ec_win dif, uint32_t rng) {
    const uint16_t d = 15 - (31 ^ clz(rng));
    assert(rng <= 65535U);
    s->cnt -= d;
    s->dif = ((dif + 1) << d) - 1; /* Shift in 1s in the LSBs */
    s->rng = rng << d;
    if (s->cnt < 0)
        ctx_refill(s);
69 70
}

71
unsigned dav1d_msac_decode_bool_equi(MsacContext *const s) {
72 73 74 75 76 77 78 79 80 81 82
    ec_win v, vw, dif = s->dif;
    uint16_t r = s->rng;
    unsigned ret;
    assert((dif >> (EC_WIN_SIZE - 16)) < r);
    // When the probability is 1/2, f = 16384 >> EC_PROB_SHIFT = 256 and we can
    // replace the multiply with a simple shift.
    v = ((r >> 8) << 7) + EC_MIN_PROB;
    vw   = v << (EC_WIN_SIZE - 16);
    ret  = dif >= vw;
    dif -= ret*vw;
    v   += ret*(r - 2*v);
83
    ctx_norm(s, dif, (unsigned) v);
84 85 86
    return !ret;
}

Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
87 88 89
/* Decode a single binary value.
 * f: The probability that the bit is one
 * Return: The value decoded (0 or 1). */
90
unsigned dav1d_msac_decode_bool(MsacContext *const s, const unsigned f) {
Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
91 92 93 94
    ec_win v, vw, dif = s->dif;
    uint16_t r = s->rng;
    unsigned ret;
    assert((dif >> (EC_WIN_SIZE - 16)) < r);
95
    v = ((r >> 8) * (f >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT)) + EC_MIN_PROB;
Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
96 97 98 99
    vw   = v << (EC_WIN_SIZE - 16);
    ret  = dif >= vw;
    dif -= ret*vw;
    v   += ret*(r - 2*v);
100
    ctx_norm(s, dif, (unsigned) v);
Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
101
    return !ret;
102 103
}

104
unsigned dav1d_msac_decode_bools(MsacContext *const c, const unsigned l) {
105 106
    int v = 0;
    for (int n = (int) l - 1; n >= 0; n--)
107
        v = (v << 1) | dav1d_msac_decode_bool_equi(c);
108 109 110
    return v;
}

111 112
int dav1d_msac_decode_subexp(MsacContext *const c, const int ref,
                             const int n, const unsigned k)
113 114 115 116
{
    int i = 0;
    int a = 0;
    int b = k;
Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
117
    while ((2 << b) < n) {
118
        if (!dav1d_msac_decode_bool_equi(c)) break;
119 120 121
        b = k + i++;
        a = (1 << b);
    }
122
    const unsigned v = dav1d_msac_decode_bools(c, b) + a;
Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
123 124
    return ref * 2 <= n ? inv_recenter(ref, v) :
                          n - 1 - inv_recenter(n - 1 - ref, v);
125 126
}

127
int dav1d_msac_decode_uniform(MsacContext *const c, const unsigned n) {
128 129 130
    assert(n > 0);
    const int l = ulog2(n) + 1;
    assert(l > 1);
Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
131
    const unsigned m = (1 << l) - n;
132 133
    const unsigned v = dav1d_msac_decode_bools(c, l - 1);
    return v < m ? v : (v << 1) - m + dav1d_msac_decode_bool_equi(c);
134 135
}

136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
/* Decodes a symbol given an inverse cumulative distribution function (CDF)
 * table in Q15. */
static unsigned decode_symbol(MsacContext *const s, const uint16_t *const cdf,
                              const unsigned n_symbols)
{
    ec_win u, v = s->rng, r = s->rng >> 8;
    const ec_win c = s->dif >> (EC_WIN_SIZE - 16);
    unsigned ret = 0;

    assert(!cdf[n_symbols - 1]);

    do {
        u = v;
        v = r * (cdf[ret++] >> EC_PROB_SHIFT);
        v >>= 7 - EC_PROB_SHIFT;
        v += EC_MIN_PROB * (n_symbols - ret);
    } while (c < v);

    assert(u <= s->rng);

    ctx_norm(s, s->dif - (v << (EC_WIN_SIZE - 16)), (unsigned) (u - v));
    return ret - 1;
}

160 161
static void update_cdf(uint16_t *const cdf, const unsigned val,
                       const unsigned n_symbols)
162
{
163 164
    const unsigned count = cdf[n_symbols];
    const int rate = ((count >> 4) | 4) + (n_symbols > 3);
Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
165
    unsigned i;
166
    for (i = 0; i < val; i++)
Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
167
        cdf[i] += (32768 - cdf[i]) >> rate;
168
    for (; i < n_symbols - 1; i++)
Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
169
        cdf[i] -= cdf[i] >> rate;
170
    cdf[n_symbols] = count + (count < 32);
171
}
Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
172

173 174 175
unsigned dav1d_msac_decode_symbol_adapt(MsacContext *const c,
                                        uint16_t *const cdf,
                                        const unsigned n_symbols)
176
{
177
    const unsigned val = decode_symbol(c, cdf, n_symbols);
178 179
    if(c->allow_update_cdf)
        update_cdf(cdf, val, n_symbols);
180 181 182
    return val;
}

183 184 185 186
unsigned dav1d_msac_decode_bool_adapt(MsacContext *const c,
                                      uint16_t *const cdf)
{
    const unsigned bit = dav1d_msac_decode_bool(c, *cdf);
187

188 189 190 191 192 193 194 195 196 197
    if(c->allow_update_cdf){
        // update_cdf() specialized for boolean CDFs
        const unsigned count = cdf[1];
        const int rate = (count >> 4) | 4;
        if (bit) {
            cdf[0] += (32768 - cdf[0]) >> rate;
        } else {
            cdf[0] -= cdf[0] >> rate;
        }
        cdf[1] = count + (count < 32);
198 199 200 201 202
    }

    return bit;
}

203 204
void dav1d_msac_init(MsacContext *const s, const uint8_t *const data,
                     const size_t sz, const int disable_cdf_update_flag)
Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
205 206 207 208 209 210
{
    s->buf_pos = data;
    s->buf_end = data + sz;
    s->dif = ((ec_win)1 << (EC_WIN_SIZE - 1)) - 1;
    s->rng = 0x8000;
    s->cnt = -15;
211
    s->allow_update_cdf = !disable_cdf_update_flag;
Rostislav Pehlivanov's avatar
Rostislav Pehlivanov committed
212 213
    ctx_refill(s);
}