1// Copyright 2011 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package vp8
6
7// Each VP8 frame consists of between 2 and 9 bitstream partitions.
8// Each partition is byte-aligned and is independently arithmetic-encoded.
9//
10// This file implements decoding a partition's bitstream, as specified in
11// chapter 7. The implementation follows libwebp's approach instead of the
12// specification's reference C implementation. For example, we use a look-up
13// table instead of a for loop to recalibrate the encoded range.
14
15var (
16 lutShift = [127]uint8{
17 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
18 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
19 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
20 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
21 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
22 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
23 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
24 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
25 }
26 lutRangeM1 = [127]uint8{
27 127,
28 127, 191,
29 127, 159, 191, 223,
30 127, 143, 159, 175, 191, 207, 223, 239,
31 127, 135, 143, 151, 159, 167, 175, 183, 191, 199, 207, 215, 223, 231, 239, 247,
32 127, 131, 135, 139, 143, 147, 151, 155, 159, 163, 167, 171, 175, 179, 183, 187,
33 191, 195, 199, 203, 207, 211, 215, 219, 223, 227, 231, 235, 239, 243, 247, 251,
34 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149, 151, 153, 155, 157,
35 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179, 181, 183, 185, 187, 189,
36 191, 193, 195, 197, 199, 201, 203, 205, 207, 209, 211, 213, 215, 217, 219, 221,
37 223, 225, 227, 229, 231, 233, 235, 237, 239, 241, 243, 245, 247, 249, 251, 253,
38 }
39)
40
41// uniformProb represents a 50% probability that the next bit is 0.
42const uniformProb = 128
43
44// partition holds arithmetic-coded bits.
45type partition struct {
46 // buf is the input bytes.
47 buf []byte
48 // r is how many of buf's bytes have been consumed.
49 r int
50 // rangeM1 is range minus 1, where range is in the arithmetic coding sense,
51 // not the Go language sense.
52 rangeM1 uint32
53 // bits and nBits hold those bits shifted out of buf but not yet consumed.
54 bits uint32
55 nBits uint8
56 // unexpectedEOF tells whether we tried to read past buf.
57 unexpectedEOF bool
58}
59
60// init initializes the partition.
61func (p *partition) init(buf []byte) {
62 p.buf = buf
63 p.r = 0
64 p.rangeM1 = 254
65 p.bits = 0
66 p.nBits = 0
67 p.unexpectedEOF = false
68}
69
70// readBit returns the next bit.
71func (p *partition) readBit(prob uint8) bool {
72 if p.nBits < 8 {
73 if p.r >= len(p.buf) {
74 p.unexpectedEOF = true
75 return false
76 }
77 // Expression split for 386 compiler.
78 x := uint32(p.buf[p.r])
79 p.bits |= x << (8 - p.nBits)
80 p.r++
81 p.nBits += 8
82 }
83 split := (p.rangeM1*uint32(prob))>>8 + 1
84 bit := p.bits >= split<<8
85 if bit {
86 p.rangeM1 -= split
87 p.bits -= split << 8
88 } else {
89 p.rangeM1 = split - 1
90 }
91 if p.rangeM1 < 127 {
92 shift := lutShift[p.rangeM1]
93 p.rangeM1 = uint32(lutRangeM1[p.rangeM1])
94 p.bits <<= shift
95 p.nBits -= shift
96 }
97 return bit
98}
99
100// readUint returns the next n-bit unsigned integer.
101func (p *partition) readUint(prob, n uint8) uint32 {
102 var u uint32
103 for n > 0 {
104 n--
105 if p.readBit(prob) {
106 u |= 1 << n
107 }
108 }
109 return u
110}
111
112// readInt returns the next n-bit signed integer.
113func (p *partition) readInt(prob, n uint8) int32 {
114 u := p.readUint(prob, n)
115 b := p.readBit(prob)
116 if b {
117 return -int32(u)
118 }
119 return int32(u)
120}
121
122// readOptionalInt returns the next n-bit signed integer in an encoding
123// where the likely result is zero.
124func (p *partition) readOptionalInt(prob, n uint8) int32 {
125 if !p.readBit(prob) {
126 return 0
127 }
128 return p.readInt(prob, n)
129}