getbits.c 4.87 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
/*
 * Copyright © 2018, VideoLAN and dav1d authors
 * Copyright © 2018, Two Orioles, LLC
 * All rights reserved.
 *
 * 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.
 */

#include "config.h"

#include <assert.h>

#include "common/intops.h"

#include "src/getbits.h"

36 37
void dav1d_init_get_bits(GetBits *const c, const uint8_t *const data,
                         const size_t sz)
38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
{
    c->ptr = c->ptr_start = data;
    c->ptr_end = &c->ptr_start[sz];
    c->bits_left = 0;
    c->state = 0;
    c->error = 0;
    c->eof = 0;
}

static void refill(GetBits *const c, const unsigned n) {
    assert(c->bits_left <= 56);
    uint64_t state = 0;
    do {
        state <<= 8;
        c->bits_left += 8;
        if (!c->eof)
            state |= *c->ptr++;
        if (c->ptr >= c->ptr_end) {
            c->error = c->eof;
            c->eof = 1;
        }
    } while (n > c->bits_left);
    c->state |= state << (64 - c->bits_left);
}

63
unsigned dav1d_get_bits(GetBits *const c, const unsigned n) {
64
    assert(n <= 32 /* can go up to 57 if we change return type */);
65
    assert(n /* can't shift state by 64 */);
66 67 68 69 70 71 72

    if (n > c->bits_left) refill(c, n);

    const uint64_t state = c->state;
    c->bits_left -= n;
    c->state <<= n;

73
    return (unsigned) (state >> (64 - n));
74 75
}

76
int dav1d_get_sbits(GetBits *const c, const unsigned n) {
77
    const int shift = 31 - n;
78
    const int res = dav1d_get_bits(c, n + 1) << shift;
79 80 81
    return res >> shift;
}

82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
unsigned dav1d_get_uleb128(GetBits *c) {
    unsigned val = 0, more, i = 0;

    do {
        more = dav1d_get_bits(c, 1);
        unsigned bits = dav1d_get_bits(c, 7);
        if (i <= 3 || (i == 4 && bits < (1 << 4)))
            val |= bits << (i * 7);
        else if (bits) {
            c->error = 1;
            return 0;
        }
        if (more && ++i == 8) {
            c->error = 1;
            return 0;
        }
    } while (more);

    return val;
}

103 104 105 106 107 108 109
unsigned dav1d_get_uniform(GetBits *const c, const unsigned max) {
    // Output in range [0..max-1]
    // max must be > 1, or else nothing is read from the bitstream
    assert(max > 1);
    const int l = ulog2(max) + 1;
    assert(l > 1);
    const unsigned m = (1U << l) - max;
skal's avatar
skal committed
110
    const unsigned v = dav1d_get_bits(c, l - 1);
111
    return v < m ? v : (v << 1) - m + dav1d_get_bits(c, 1);
112 113
}

114
unsigned dav1d_get_vlc(GetBits *const c) {
115
    int n_bits = 0;
116
    while (!dav1d_get_bits(c, 1))
117 118
        if (++n_bits == 32)
            return 0xFFFFFFFFU;
119
    return n_bits ? ((1U << n_bits) - 1) + dav1d_get_bits(c, n_bits) : 0;
120 121 122 123 124 125 126 127 128 129 130
}

static unsigned get_bits_subexp_u(GetBits *const c, const unsigned ref,
                                  const unsigned n)
{
    unsigned v = 0;

    for (int i = 0;; i++) {
        const int b = i ? 3 + i - 1 : 3;

        if (n < v + 3 * (1 << b)) {
131
            v += dav1d_get_uniform(c, n - v + 1);
132 133 134
            break;
        }

135 136
        if (!dav1d_get_bits(c, 1)) {
            v += dav1d_get_bits(c, b);
137 138 139 140 141 142 143 144 145
            break;
        }

        v += 1 << b;
    }

    return ref * 2 <= n ? inv_recenter(ref, v) : n - inv_recenter(n - ref, v);
}

146
int dav1d_get_bits_subexp(GetBits *const c, const int ref, const unsigned n) {
147 148 149
    return (int) get_bits_subexp_u(c, ref + (1 << n), 2 << n) - (1 << n);
}

150 151 152 153 154 155 156 157 158 159
void dav1d_bytealign_get_bits(GetBits *c) {
    // bits_left is never more than 7, because it is only incremented
    // by refill(), called by dav1d_get_bits and that never reads more
    // than 7 bits more than it needs.
    //
    // If this wasn't true, we would need to work out how many bits to
    // discard (bits_left % 8), subtract that from bits_left and then
    // shift state right by that amount.
    assert(c->bits_left <= 7);

160 161 162
    c->bits_left = 0;
    c->state = 0;
}