Class: Omnizip::Algorithms::Zstandard::LiteralsDecoder

Inherits:
Object
  • Object
show all
Includes:
Constants
Defined in:
lib/omnizip/algorithms/zstandard/literals.rb

Overview

Literals section decoder (RFC 8878 §3.1.1.3.1).

Header byte 0 layout (bits numbered from the LSB, matching the C reference litEncType = istart[0] & 3):

bits 0-1  Literals_Block_Type (0=Raw, 1=RLE, 2=Compressed,
        3=Treeless)
bits 2-3  Size_Format selector

Raw / RLE size formats:

00, 10 -> 1-byte header, regen = byte0 >> 3
01     -> 2-byte header, regen = LE16 >> 4
11     -> 3-byte header, regen = LE24 >> 4

Compressed / Treeless size formats:

00 -> 3-byte header, single stream, 10-bit sizes
01 -> 3-byte header, 4 streams, 10-bit sizes
10 -> 4-byte header, 4 streams, 14-bit sizes
11 -> 5-byte header, 4 streams, 18-bit sizes

Constant Summary

Constants included from Constants

Constants::BLOCK_HEADER_SIZE, Constants::BLOCK_MAX_SIZE, Constants::BLOCK_TYPE_COMPRESSED, Constants::BLOCK_TYPE_RAW, Constants::BLOCK_TYPE_RESERVED, Constants::BLOCK_TYPE_RLE, Constants::BUFFER_SIZE, Constants::DEFAULT_LEVEL, Constants::DEFAULT_REPEAT_OFFSETS, Constants::FSE_DEFAULT_TABLELOG, Constants::FSE_MAX_ACCURACY_LOG, Constants::FSE_MIN_ACCURACY_LOG, Constants::HUFFMAN_MAX_BITS, Constants::HUFFMAN_MAX_CODE_LENGTH, Constants::HUFFMAN_MAX_LOG, Constants::HUFFMAN_STANDARD_TABLE_SIZE, Constants::HUF_SYMBOLVALUE_MAX, Constants::LDM_MIN_LEVEL, Constants::LITERALS_BLOCK_COMPRESSED, Constants::LITERALS_BLOCK_RAW, Constants::LITERALS_BLOCK_RLE, Constants::LITERALS_BLOCK_TREELESS, Constants::LITERALS_LENGTH_ACCURACY_LOG, Constants::LITERAL_LENGTH_TABLE, Constants::MAGIC_BYTES, Constants::MAGIC_NUMBER, Constants::MATCH_LENGTH_ACCURACY_LOG, Constants::MATCH_LENGTH_TABLE, Constants::MAX_LEVEL, Constants::MIN_LEVEL, Constants::MODE_FSE, Constants::MODE_PREDEFINED, Constants::MODE_REPEAT, Constants::MODE_RLE, Constants::OFFSET_ACCURACY_LOG, Constants::OF_BASE, Constants::OF_BITS, Constants::PREDEFINED_LL_DISTRIBUTION, Constants::PREDEFINED_ML_DISTRIBUTION, Constants::PREDEFINED_OFFSET_DISTRIBUTION, Constants::REPEAT_OFFSET_1, Constants::REPEAT_OFFSET_2, Constants::REPEAT_OFFSET_3, Constants::SKIPPABLE_MAGIC_BASE, Constants::SKIPPABLE_MAGIC_MASK, Constants::WINDOW_LOG_MAX, Constants::WINDOW_LOG_MIN

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Constants

highbit32

Constructor Details

#initialize(literals, huffman_table, consumed) ⇒ LiteralsDecoder

Returns a new instance of LiteralsDecoder.



233
234
235
236
237
 
# File 'lib/omnizip/algorithms/zstandard/literals.rb', line 233

def initialize(literals, huffman_table, consumed)
  @literals = literals
  @huffman_table = huffman_table
  @consumed = consumed
end

Instance Attribute Details

#consumed ⇒ Integer (readonly)

Returns bytes consumed from the input.

Returns:

  • (Integer) —

    bytes consumed from the input



56
57
58
 
# File 'lib/omnizip/algorithms/zstandard/literals.rb', line 56

def consumed
  @consumed
end

#huffman_table ⇒ Huffman? (readonly)

Returns table from a Compressed block, for the next Treeless block in the same frame.

Returns:

  • (Huffman, nil) —

    table from a Compressed block, for the next Treeless block in the same frame



53
54
55
 
# File 'lib/omnizip/algorithms/zstandard/literals.rb', line 53

def huffman_table
  @huffman_table
end

#literals ⇒ String (readonly)

Returns decoded literal bytes.

Returns:

  • (String) —

    decoded literal bytes



49
50
51
 
# File 'lib/omnizip/algorithms/zstandard/literals.rb', line 49

def literals
  @literals
end

Class Method Details

.decode(input, previous_table = nil) ⇒ LiteralsDecoder

Decode the literals section at the head of input.

Parameters:

  • input (String)
  • previous_table (Huffman, nil) (defaults to: nil) —

    table from the previous compressed literals block (required for Treeless)

Returns:

Raises:



64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/omnizip/algorithms/zstandard/literals.rb', line 64

def self.decode(input, previous_table = nil)
  raise Omnizip::DecompressionError, "empty literals section" if input.empty?

  block_type = input.getbyte(0) & 0x03

  case block_type
  when LITERALS_BLOCK_RAW then decode_raw(input)
  when LITERALS_BLOCK_RLE then decode_rle(input)
  when LITERALS_BLOCK_COMPRESSED
    decode_compressed(input, previous_table, false)
  when LITERALS_BLOCK_TREELESS
    decode_compressed(input, previous_table, true)
  end
end

.decode_compressed(input, previous_table, is_repeat) ⇒ Object

rubocop:disable Metrics/AbcSize rubocop:disable-next Metrics/MethodLength



103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
 
# File 'lib/omnizip/algorithms/zstandard/literals.rb', line 103

def self.decode_compressed(input, previous_table, is_repeat)
  if is_repeat && previous_table.nil?
    raise Omnizip::DecompressionError,
          "treeless literals block requires a previous compressed " \
          "block in the same frame"
  end

  lhl_code = (input.getbyte(0) >> 2) & 0x03

  min_header = [3, 3, 4, 5][lhl_code]
  if input.bytesize < min_header
    raise Omnizip::DecompressionError,
          "truncated compressed literals header: need #{min_header} bytes"
  end

  lit_size, lit_c_size, lh_size, single_stream =
    case lhl_code
    when 0, 1
      lhc = input.getbyte(0) |
        (input.getbyte(1) << 8) | (input.getbyte(2) << 16)
      [(lhc >> 4) & 0x3FF, (lhc >> 14) & 0x3FF, 3, lhl_code.zero?]
    when 2
      lhc = input.unpack1("V") & 0xFFFFFFFF
      [(lhc >> 4) & 0x3FFF, lhc >> 18, 4, false]
    else
      low = input.byteslice(0, 4).unpack1("V")
      high = input.getbyte(4)
      lhc = low | (high << 32)
      [(lhc >> 4) & 0x3FFFF, lhc >> 22, 5, false]
    end

  needed = lh_size + lit_c_size
  if input.bytesize < needed
    raise Omnizip::DecompressionError,
          "truncated compressed literals: need #{needed} bytes"
  end
  compressed = input.byteslice(lh_size, lit_c_size)

  table_bytes = 0
  table = previous_table
  unless is_repeat
    table, table_bytes = HuffmanTableReader.read(compressed)
  end

  literal_data = compressed.byteslice(table_bytes..)
  literals = if single_stream
               decode_single_stream(table, literal_data, lit_size)
             else
               decode_four_stream(table, literal_data, lit_size)
             end

  new(literals, is_repeat ? nil : table, needed)
end

.decode_four_stream(table, src, lit_size) ⇒ Object

Jump table + four independent reverse bitstreams, each decoding ~1/4 of the literals (RFC 8878 §3.1.1.3.1.4). rubocop:disable Metrics/AbcSize



193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
 
# File 'lib/omnizip/algorithms/zstandard/literals.rb', line 193

def self.decode_four_stream(table, src, lit_size)
  if src.bytesize < 10
    raise Omnizip::DecompressionError,
          "4-stream literals too short (need at least 10 bytes)"
  end
  # rubocop:enable Metrics/AbcSize

  length1 = src.unpack1("v")
  length2 = src.byteslice(2, 2).unpack1("v")
  length3 = src.byteslice(4, 2).unpack1("v")
  total = src.bytesize - 6
  if length1 + length2 + length3 > total
    raise Omnizip::DecompressionError,
          "4-stream jump table sizes exceed total stream size"
  end

  streams = src.byteslice(6..)
  seg1 = streams.byteslice(0, length1)
  seg2 = streams.byteslice(length1, length2)
  seg3 = streams.byteslice(length1 + length2, length3)
  seg4 = streams.byteslice((length1 + length2 + length3)..)

  segment_size = (lit_size + 3) / 4
  bounds = [0,
            segment_size,
            segment_size * 2,
            segment_size * 3,
            lit_size]

  out = String.new(encoding: Encoding::BINARY)
  [seg1, seg2, seg3, seg4].each_with_index do |seg, i|
    bs = FSE::BitStream.new(seg)
    (bounds[i]...bounds[i + 1]).each do
      out << table.decode(bs).chr
      bs.reload
    end
  end
  out
end

.decode_raw(input) ⇒ Object 



79
80
81
82
83
84
85
86
87
88
 
# File 'lib/omnizip/algorithms/zstandard/literals.rb', line 79

def self.decode_raw(input)
  regen_size, header_size = size_format_raw_rle(input)
  end_pos = header_size + regen_size
  if input.bytesize < end_pos
    raise Omnizip::DecompressionError,
          "truncated raw literals: need #{end_pos} bytes"
  end

  new(input.byteslice(header_size, regen_size), nil, end_pos)
end

.decode_rle(input) ⇒ Object 



90
91
92
93
94
95
96
97
98
99
 
# File 'lib/omnizip/algorithms/zstandard/literals.rb', line 90

def self.decode_rle(input)
  regen_size, header_size = size_format_raw_rle(input)
  if input.bytesize < header_size + 1
    raise Omnizip::DecompressionError,
          "truncated RLE literals: missing repeated byte"
  end

  byte = input.getbyte(header_size)
  new(byte.chr * regen_size, nil, header_size + 1)
end

.decode_single_stream(table, src, lit_size) ⇒ Object

One reverse bitstream decoded into lit_size symbols.



180
181
182
183
184
185
186
187
188
 
# File 'lib/omnizip/algorithms/zstandard/literals.rb', line 180

def self.decode_single_stream(table, src, lit_size)
  bs = FSE::BitStream.new(src)
  out = String.new(encoding: Encoding::BINARY)
  lit_size.times do
    out << table.decode(bs).chr
    bs.reload
  end
  out
end

.size_format_raw_rle(input) ⇒ Object

rubocop:disable-next Metrics/AbcSize



159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
 
# File 'lib/omnizip/algorithms/zstandard/literals.rb', line 159

def self.size_format_raw_rle(input)
  lhl_code = (input.getbyte(0) >> 2) & 0x03
  header_size = [1, 2, 1, 3][lhl_code]
  if input.bytesize < header_size
    raise Omnizip::DecompressionError,
          "truncated Raw/RLE literals header: need #{header_size} bytes"
  end

  case lhl_code
  when 0, 2
    [input.getbyte(0) >> 3, 1]
  when 1
    [input.unpack1("v") >> 4, 2]
  else
    lhc = input.getbyte(0) | (input.getbyte(1) << 8) |
      (input.getbyte(2) << 16)
    [lhc >> 4, 3]
  end
end