partition.go (3698B)
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 5 package 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 15 var ( 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. 42 const uniformProb = 128 43 44 // partition holds arithmetic-coded bits. 45 type 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. 61 func (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. 71 func (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. 101 func (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. 113 func (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. 124 func (p *partition) readOptionalInt(prob, n uint8) int32 { 125 if !p.readBit(prob) { 126 return 0 127 } 128 return p.readInt(prob, n) 129 }