partition.go

Documentation: golang.org/x/image/vp8

     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  }
   130
View as plain text