bits.go

     1  // Copyright 2023 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 zstd
     6  
     7  import (
     8  	"math/bits"
     9  )
    10  
    11  // block is the data for a single compressed block.
    12  // The data starts immediately after the 3 byte block header,
    13  // and is Block_Size bytes long.
    14  type block []byte
    15  
    16  // bitReader reads a bit stream going forward.
    17  type bitReader struct {
    18  	r    *Reader // for error reporting
    19  	data block   // the bits to read
    20  	off  uint32  // current offset into data
    21  	bits uint32  // bits ready to be returned
    22  	cnt  uint32  // number of valid bits in the bits field
    23  }
    24  
    25  // makeBitReader makes a bit reader starting at off.
    26  func (r *Reader) makeBitReader(data block, off int) bitReader {
    27  	return bitReader{
    28  		r:    r,
    29  		data: data,
    30  		off:  uint32(off),
    31  	}
    32  }
    33  
    34  // moreBits is called to read more bits.
    35  // This ensures that at least 16 bits are available.
    36  func (br *bitReader) moreBits() error {
    37  	for br.cnt < 16 {
    38  		if br.off >= uint32(len(br.data)) {
    39  			return br.r.makeEOFError(int(br.off))
    40  		}
    41  		c := br.data[br.off]
    42  		br.off++
    43  		br.bits |= uint32(c) << br.cnt
    44  		br.cnt += 8
    45  	}
    46  	return nil
    47  }
    48  
    49  // val is called to fetch a value of b bits.
    50  func (br *bitReader) val(b uint8) uint32 {
    51  	r := br.bits & ((1 << b) - 1)
    52  	br.bits >>= b
    53  	br.cnt -= uint32(b)
    54  	return r
    55  }
    56  
    57  // backup steps back to the last byte we used.
    58  func (br *bitReader) backup() {
    59  	for br.cnt >= 8 {
    60  		br.off--
    61  		br.cnt -= 8
    62  	}
    63  }
    64  
    65  // makeError returns an error at the current offset wrapping a string.
    66  func (br *bitReader) makeError(msg string) error {
    67  	return br.r.makeError(int(br.off), msg)
    68  }
    69  
    70  // reverseBitReader reads a bit stream in reverse.
    71  type reverseBitReader struct {
    72  	r     *Reader // for error reporting
    73  	data  block   // the bits to read
    74  	off   uint32  // current offset into data
    75  	start uint32  // start in data; we read backward to start
    76  	bits  uint32  // bits ready to be returned
    77  	cnt   uint32  // number of valid bits in bits field
    78  }
    79  
    80  // makeReverseBitReader makes a reverseBitReader reading backward
    81  // from off to start. The bitstream starts with a 1 bit in the last
    82  // byte, at off.
    83  func (r *Reader) makeReverseBitReader(data block, off, start int) (reverseBitReader, error) {
    84  	streamStart := data[off]
    85  	if streamStart == 0 {
    86  		return reverseBitReader{}, r.makeError(off, "zero byte at reverse bit stream start")
    87  	}
    88  	rbr := reverseBitReader{
    89  		r:     r,
    90  		data:  data,
    91  		off:   uint32(off),
    92  		start: uint32(start),
    93  		bits:  uint32(streamStart),
    94  		cnt:   uint32(7 - bits.LeadingZeros8(streamStart)),
    95  	}
    96  	return rbr, nil
    97  }
    98  
    99  // val is called to fetch a value of b bits.
   100  func (rbr *reverseBitReader) val(b uint8) (uint32, error) {
   101  	if !rbr.fetch(b) {
   102  		return 0, rbr.r.makeEOFError(int(rbr.off))
   103  	}
   104  
   105  	rbr.cnt -= uint32(b)
   106  	v := (rbr.bits >> rbr.cnt) & ((1 << b) - 1)
   107  	return v, nil
   108  }
   109  
   110  // fetch is called to ensure that at least b bits are available.
   111  // It reports false if this can't be done,
   112  // in which case only rbr.cnt bits are available.
   113  func (rbr *reverseBitReader) fetch(b uint8) bool {
   114  	for rbr.cnt < uint32(b) {
   115  		if rbr.off <= rbr.start {
   116  			return false
   117  		}
   118  		rbr.off--
   119  		c := rbr.data[rbr.off]
   120  		rbr.bits <<= 8
   121  		rbr.bits |= uint32(c)
   122  		rbr.cnt += 8
   123  	}
   124  	return true
   125  }
   126  
   127  // makeError returns an error at the current offset wrapping a string.
   128  func (rbr *reverseBitReader) makeError(msg string) error {
   129  	return rbr.r.makeError(int(rbr.off), msg)
   130  }
   131
View as plain text