bitreader.go

Documentation: github.com/klauspost/compress/fse

     1  // Copyright 2018 Klaus Post. 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  // Based on work Copyright (c) 2013, Yann Collet, released under BSD License.
     5  
     6  package fse
     7  
     8  import (
     9  	"encoding/binary"
    10  	"errors"
    11  	"io"
    12  )
    13  
    14  // bitReader reads a bitstream in reverse.
    15  // The last set bit indicates the start of the stream and is used
    16  // for aligning the input.
    17  type bitReader struct {
    18  	in       []byte
    19  	off      uint // next byte to read is at in[off - 1]
    20  	value    uint64
    21  	bitsRead uint8
    22  }
    23  
    24  // init initializes and resets the bit reader.
    25  func (b *bitReader) init(in []byte) error {
    26  	if len(in) < 1 {
    27  		return errors.New("corrupt stream: too short")
    28  	}
    29  	b.in = in
    30  	b.off = uint(len(in))
    31  	// The highest bit of the last byte indicates where to start
    32  	v := in[len(in)-1]
    33  	if v == 0 {
    34  		return errors.New("corrupt stream, did not find end of stream")
    35  	}
    36  	b.bitsRead = 64
    37  	b.value = 0
    38  	if len(in) >= 8 {
    39  		b.fillFastStart()
    40  	} else {
    41  		b.fill()
    42  		b.fill()
    43  	}
    44  	b.bitsRead += 8 - uint8(highBits(uint32(v)))
    45  	return nil
    46  }
    47  
    48  // getBits will return n bits. n can be 0.
    49  func (b *bitReader) getBits(n uint8) uint16 {
    50  	if n == 0 || b.bitsRead >= 64 {
    51  		return 0
    52  	}
    53  	return b.getBitsFast(n)
    54  }
    55  
    56  // getBitsFast requires that at least one bit is requested every time.
    57  // There are no checks if the buffer is filled.
    58  func (b *bitReader) getBitsFast(n uint8) uint16 {
    59  	const regMask = 64 - 1
    60  	v := uint16((b.value << (b.bitsRead & regMask)) >> ((regMask + 1 - n) & regMask))
    61  	b.bitsRead += n
    62  	return v
    63  }
    64  
    65  // fillFast() will make sure at least 32 bits are available.
    66  // There must be at least 4 bytes available.
    67  func (b *bitReader) fillFast() {
    68  	if b.bitsRead < 32 {
    69  		return
    70  	}
    71  	// 2 bounds checks.
    72  	v := b.in[b.off-4:]
    73  	v = v[:4]
    74  	low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
    75  	b.value = (b.value << 32) | uint64(low)
    76  	b.bitsRead -= 32
    77  	b.off -= 4
    78  }
    79  
    80  // fill() will make sure at least 32 bits are available.
    81  func (b *bitReader) fill() {
    82  	if b.bitsRead < 32 {
    83  		return
    84  	}
    85  	if b.off > 4 {
    86  		v := b.in[b.off-4:]
    87  		v = v[:4]
    88  		low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
    89  		b.value = (b.value << 32) | uint64(low)
    90  		b.bitsRead -= 32
    91  		b.off -= 4
    92  		return
    93  	}
    94  	for b.off > 0 {
    95  		b.value = (b.value << 8) | uint64(b.in[b.off-1])
    96  		b.bitsRead -= 8
    97  		b.off--
    98  	}
    99  }
   100  
   101  // fillFastStart() assumes the bitreader is empty and there is at least 8 bytes to read.
   102  func (b *bitReader) fillFastStart() {
   103  	// Do single re-slice to avoid bounds checks.
   104  	b.value = binary.LittleEndian.Uint64(b.in[b.off-8:])
   105  	b.bitsRead = 0
   106  	b.off -= 8
   107  }
   108  
   109  // finished returns true if all bits have been read from the bit stream.
   110  func (b *bitReader) finished() bool {
   111  	return b.bitsRead >= 64 && b.off == 0
   112  }
   113  
   114  // close the bitstream and returns an error if out-of-buffer reads occurred.
   115  func (b *bitReader) close() error {
   116  	// Release reference.
   117  	b.in = nil
   118  	if b.bitsRead > 64 {
   119  		return io.ErrUnexpectedEOF
   120  	}
   121  	return nil
   122  }
   123
View as plain text