bitreader.go

Documentation: github.com/klauspost/compress/huff0

     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 huff0
     7  
     8  import (
     9  	"encoding/binary"
    10  	"errors"
    11  	"fmt"
    12  	"io"
    13  )
    14  
    15  // bitReader reads a bitstream in reverse.
    16  // The last set bit indicates the start of the stream and is used
    17  // for aligning the input.
    18  type bitReaderBytes struct {
    19  	in       []byte
    20  	off      uint // next byte to read is at in[off - 1]
    21  	value    uint64
    22  	bitsRead uint8
    23  }
    24  
    25  // init initializes and resets the bit reader.
    26  func (b *bitReaderBytes) init(in []byte) error {
    27  	if len(in) < 1 {
    28  		return errors.New("corrupt stream: too short")
    29  	}
    30  	b.in = in
    31  	b.off = uint(len(in))
    32  	// The highest bit of the last byte indicates where to start
    33  	v := in[len(in)-1]
    34  	if v == 0 {
    35  		return errors.New("corrupt stream, did not find end of stream")
    36  	}
    37  	b.bitsRead = 64
    38  	b.value = 0
    39  	if len(in) >= 8 {
    40  		b.fillFastStart()
    41  	} else {
    42  		b.fill()
    43  		b.fill()
    44  	}
    45  	b.advance(8 - uint8(highBit32(uint32(v))))
    46  	return nil
    47  }
    48  
    49  // peekBitsFast requires that at least one bit is requested every time.
    50  // There are no checks if the buffer is filled.
    51  func (b *bitReaderBytes) peekByteFast() uint8 {
    52  	got := uint8(b.value >> 56)
    53  	return got
    54  }
    55  
    56  func (b *bitReaderBytes) advance(n uint8) {
    57  	b.bitsRead += n
    58  	b.value <<= n & 63
    59  }
    60  
    61  // fillFast() will make sure at least 32 bits are available.
    62  // There must be at least 4 bytes available.
    63  func (b *bitReaderBytes) fillFast() {
    64  	if b.bitsRead < 32 {
    65  		return
    66  	}
    67  
    68  	// 2 bounds checks.
    69  	v := b.in[b.off-4 : b.off]
    70  	low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
    71  	b.value |= uint64(low) << (b.bitsRead - 32)
    72  	b.bitsRead -= 32
    73  	b.off -= 4
    74  }
    75  
    76  // fillFastStart() assumes the bitReaderBytes is empty and there is at least 8 bytes to read.
    77  func (b *bitReaderBytes) fillFastStart() {
    78  	// Do single re-slice to avoid bounds checks.
    79  	b.value = binary.LittleEndian.Uint64(b.in[b.off-8:])
    80  	b.bitsRead = 0
    81  	b.off -= 8
    82  }
    83  
    84  // fill() will make sure at least 32 bits are available.
    85  func (b *bitReaderBytes) fill() {
    86  	if b.bitsRead < 32 {
    87  		return
    88  	}
    89  	if b.off > 4 {
    90  		v := b.in[b.off-4 : b.off]
    91  		low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
    92  		b.value |= uint64(low) << (b.bitsRead - 32)
    93  		b.bitsRead -= 32
    94  		b.off -= 4
    95  		return
    96  	}
    97  	for b.off > 0 {
    98  		b.value |= uint64(b.in[b.off-1]) << (b.bitsRead - 8)
    99  		b.bitsRead -= 8
   100  		b.off--
   101  	}
   102  }
   103  
   104  // finished returns true if all bits have been read from the bit stream.
   105  func (b *bitReaderBytes) finished() bool {
   106  	return b.off == 0 && b.bitsRead >= 64
   107  }
   108  
   109  func (b *bitReaderBytes) remaining() uint {
   110  	return b.off*8 + uint(64-b.bitsRead)
   111  }
   112  
   113  // close the bitstream and returns an error if out-of-buffer reads occurred.
   114  func (b *bitReaderBytes) close() error {
   115  	// Release reference.
   116  	b.in = nil
   117  	if b.remaining() > 0 {
   118  		return fmt.Errorf("corrupt input: %d bits remain on stream", b.remaining())
   119  	}
   120  	if b.bitsRead > 64 {
   121  		return io.ErrUnexpectedEOF
   122  	}
   123  	return nil
   124  }
   125  
   126  // bitReaderShifted reads a bitstream in reverse.
   127  // The last set bit indicates the start of the stream and is used
   128  // for aligning the input.
   129  type bitReaderShifted struct {
   130  	in       []byte
   131  	off      uint // next byte to read is at in[off - 1]
   132  	value    uint64
   133  	bitsRead uint8
   134  }
   135  
   136  // init initializes and resets the bit reader.
   137  func (b *bitReaderShifted) init(in []byte) error {
   138  	if len(in) < 1 {
   139  		return errors.New("corrupt stream: too short")
   140  	}
   141  	b.in = in
   142  	b.off = uint(len(in))
   143  	// The highest bit of the last byte indicates where to start
   144  	v := in[len(in)-1]
   145  	if v == 0 {
   146  		return errors.New("corrupt stream, did not find end of stream")
   147  	}
   148  	b.bitsRead = 64
   149  	b.value = 0
   150  	if len(in) >= 8 {
   151  		b.fillFastStart()
   152  	} else {
   153  		b.fill()
   154  		b.fill()
   155  	}
   156  	b.advance(8 - uint8(highBit32(uint32(v))))
   157  	return nil
   158  }
   159  
   160  // peekBitsFast requires that at least one bit is requested every time.
   161  // There are no checks if the buffer is filled.
   162  func (b *bitReaderShifted) peekBitsFast(n uint8) uint16 {
   163  	return uint16(b.value >> ((64 - n) & 63))
   164  }
   165  
   166  func (b *bitReaderShifted) advance(n uint8) {
   167  	b.bitsRead += n
   168  	b.value <<= n & 63
   169  }
   170  
   171  // fillFast() will make sure at least 32 bits are available.
   172  // There must be at least 4 bytes available.
   173  func (b *bitReaderShifted) fillFast() {
   174  	if b.bitsRead < 32 {
   175  		return
   176  	}
   177  
   178  	// 2 bounds checks.
   179  	v := b.in[b.off-4 : b.off]
   180  	low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
   181  	b.value |= uint64(low) << ((b.bitsRead - 32) & 63)
   182  	b.bitsRead -= 32
   183  	b.off -= 4
   184  }
   185  
   186  // fillFastStart() assumes the bitReaderShifted is empty and there is at least 8 bytes to read.
   187  func (b *bitReaderShifted) fillFastStart() {
   188  	// Do single re-slice to avoid bounds checks.
   189  	b.value = binary.LittleEndian.Uint64(b.in[b.off-8:])
   190  	b.bitsRead = 0
   191  	b.off -= 8
   192  }
   193  
   194  // fill() will make sure at least 32 bits are available.
   195  func (b *bitReaderShifted) fill() {
   196  	if b.bitsRead < 32 {
   197  		return
   198  	}
   199  	if b.off > 4 {
   200  		v := b.in[b.off-4 : b.off]
   201  		low := (uint32(v[0])) | (uint32(v[1]) << 8) | (uint32(v[2]) << 16) | (uint32(v[3]) << 24)
   202  		b.value |= uint64(low) << ((b.bitsRead - 32) & 63)
   203  		b.bitsRead -= 32
   204  		b.off -= 4
   205  		return
   206  	}
   207  	for b.off > 0 {
   208  		b.value |= uint64(b.in[b.off-1]) << ((b.bitsRead - 8) & 63)
   209  		b.bitsRead -= 8
   210  		b.off--
   211  	}
   212  }
   213  
   214  func (b *bitReaderShifted) remaining() uint {
   215  	return b.off*8 + uint(64-b.bitsRead)
   216  }
   217  
   218  // close the bitstream and returns an error if out-of-buffer reads occurred.
   219  func (b *bitReaderShifted) close() error {
   220  	// Release reference.
   221  	b.in = nil
   222  	if b.remaining() > 0 {
   223  		return fmt.Errorf("corrupt input: %d bits remain on stream", b.remaining())
   224  	}
   225  	if b.bitsRead > 64 {
   226  		return io.ErrUnexpectedEOF
   227  	}
   228  	return nil
   229  }
   230
View as plain text