Class: Omnizip::Algorithms::Zstandard::FSE::BitStream

Inherits:
Object
  • Object
show all
Defined in:
lib/omnizip/algorithms/zstandard/fse/bitstream.rb

Overview

Reverse-direction bit reader matching the zstd C reference BIT_DStream (lib/common/bitstream.h).

The bitstream is written forward by the encoder but read BACKWARDS: bytes are consumed from the last toward the first, and within each byte bits are consumed MSB-first. The reader keeps a 64-bit container (little-endian window onto 8 bytes) and takes bits from the high end after bits_consumed.

The last byte holds a 1 end-mark bit with 0-7 padding zero bits above it; the last byte can therefore never be 0x00.

Constant Summary collapse

MASK64 = 
0xFFFFFFFFFFFFFFFF
UNFINISHED =

Reload statuses mirroring C's BIT_DStream_status.

:unfinished
END_OF_BUFFER = 
:end_of_buffer
COMPLETED = 
:completed
OVERFLOW = 
:overflow

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(data) ⇒ BitStream

Returns a new instance of BitStream.

Parameters:

  • data (String) —

    the full bitstream bytes (binary)



50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/omnizip/algorithms/zstandard/fse/bitstream.rb', line 50

def initialize(data)
  @data = data
  n = data.bytesize
  last = n.positive? ? data.getbyte(n - 1) : 0
  end_mark = last.positive? ? 8 - Constants.highbit32(last) : 0

  if n >= 8
    @ptr = n - 8
    @container = read_le64(@ptr)
    @bits_consumed = end_mark
  else
    @ptr = 0
    @container = 0
    n.times { |i| @container |= data.getbyte(i) << (i * 8) }
    @bits_consumed = end_mark + ((8 - n) * 8)
  end
end

Instance Attribute Details

#data ⇒ Object (readonly)

Returns the value of attribute data.



47
48
49
 
# File 'lib/omnizip/algorithms/zstandard/fse/bitstream.rb', line 47

def data
  @data
end

Instance Method Details

#align_to_byte ⇒ Object

Skip to the next byte boundary (toward the stream start).



143
144
145
146
147
148
149
 
# File 'lib/omnizip/algorithms/zstandard/fse/bitstream.rb', line 143

def align_to_byte
  remainder = @bits_consumed % 8
  return if remainder.zero?

  @bits_consumed += 8 - remainder
  reload if @bits_consumed >= 8
end

#exhausted? ⇒ Boolean

Returns:

  • (Boolean) 


158
159
160
 
# File 'lib/omnizip/algorithms/zstandard/fse/bitstream.rb', line 158

def exhausted?
  remaining_bits.zero?
end

#peek_bits(count) ⇒ Object

Peek count bits without consuming.



84
85
86
87
88
89
90
91
92
93
 
# File 'lib/omnizip/algorithms/zstandard/fse/bitstream.rb', line 84

def peek_bits(count)
  saved_ptr = @ptr
  saved_container = @container
  saved_consumed = @bits_consumed
  result = read_bits(count)
  @ptr = saved_ptr
  @container = saved_container
  @bits_consumed = saved_consumed
  result
end

#read_bits(count) ⇒ Integer

Read count bits, first-read bit becoming the value's MSB (little-endian value semantics per RFC 8878 §4.1).

Parameters:

  • count (Integer) —

    0..32

Returns:

  • (Integer) 


73
74
75
76
77
78
79
80
81
 
# File 'lib/omnizip/algorithms/zstandard/fse/bitstream.rb', line 73

def read_bits(count)
  return 0 if count.zero?

  shift_left = @bits_consumed & 63
  shift_right = (64 - count) & 63
  result = ((@container << shift_left) & MASK64) >> shift_right
  @bits_consumed += count
  result & ((1 << count) - 1)
end

#reload ⇒ Object

Reload the container after enough bits have been consumed, mirroring C's BIT_reloadDStream.



97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
# File 'lib/omnizip/algorithms/zstandard/fse/bitstream.rb', line 97

def reload
  return if @bits_consumed < 8

  if @ptr >= 8
    bytes_consumed = @bits_consumed >> 3
    @ptr -= bytes_consumed
    @ptr = 0 if @ptr.negative?
    @bits_consumed &= 7
    load_container
  elsif @ptr.zero?
    # No earlier bytes to load; leave the container as is.
  else
    nb_bytes = @bits_consumed >> 3
    actual_bytes = [nb_bytes, @ptr].min
    @ptr -= actual_bytes
    @bits_consumed -= actual_bytes * 8
    load_container
  end
end

#reload_status ⇒ Symbol

Full reload that also reports the C reload status.

Returns:

  • (Symbol) —

    one of UNFINISHED, END_OF_BUFFER, COMPLETED, OVERFLOW



121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
 
# File 'lib/omnizip/algorithms/zstandard/fse/bitstream.rb', line 121

def reload_status
  return OVERFLOW if @bits_consumed > 64

  if @ptr >= 8
    bytes_consumed = @bits_consumed >> 3
    @ptr -= bytes_consumed
    @ptr = 0 if @ptr.negative?
    @bits_consumed &= 7
    load_container
    return UNFINISHED
  end
  return END_OF_BUFFER if @ptr.zero?

  nb_bytes = @bits_consumed >> 3
  actual_bytes = [nb_bytes, @ptr].min
  @ptr -= actual_bytes
  @bits_consumed -= actual_bytes * 8
  load_container
  actual_bytes < nb_bytes ? END_OF_BUFFER : UNFINISHED
end

#remaining_bits ⇒ Object

Bits not yet consumed, counting from the end of the data.



152
153
154
155
156
 
# File 'lib/omnizip/algorithms/zstandard/fse/bitstream.rb', line 152

def remaining_bits
  total = @data.bytesize * 8
  consumed = bits_consumed_so_far
  total >= consumed ? total - consumed : 0
end