Module: Omnizip::Algorithms::Zstandard::FSE::TableDescription

Includes:
Constants
Defined in:
lib/omnizip/algorithms/zstandard/fse/table_description.rb

Overview

Reads an FSE table description ("NCount") from the wire and builds an FSE decode Table (RFC 8878 ยง4.1.1, FSE Table Description; mirrors the C reference FSE_readNCount).

The distribution is a forward little-endian bit-packed stream: 4 bits of table log, then per-symbol counts whose bit width shrinks as probability points are spent, with 2-bit repeat codes for runs of zero-count symbols.

Defined Under Namespace

Classes: BitReader

Constant Summary collapse

MAX_SYMBOL_VALUE = 
255

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

Class Method Summary collapse

Methods included from Constants

highbit32

Class Method Details

.read(src) ⇒ Array(Table, Integer)

Read a normalized distribution from the head of src.

Parameters:

  • src (String) —

    bytes holding the table description (plus whatever follows)

Returns:

  • (Array(Table, Integer)) —

    the decode table and the number of bytes consumed

Raises:



50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
# File 'lib/omnizip/algorithms/zstandard/fse/table_description.rb', line 50

def read(src)
  raise Omnizip::DecompressionError, "FSE table description truncated" if src.bytesize < 4

  reader = BitReader.new(src)

  table_log = (reader.peek & 0xF) + FSE_MIN_ACCURACY_LOG
  if table_log > FSE_MAX_ACCURACY_LOG
    raise Omnizip::DecompressionError,
          "FSE tableLog #{table_log} exceeds max #{FSE_MAX_ACCURACY_LOG}"
  end
  reader.skip_bits(4)

  remaining = (1 << table_log) + 1
  threshold = 1 << table_log
  nb_bits = table_log + 1

  counts = Array.new(MAX_SYMBOL_VALUE + 1, 0)
  charnum = 0
  previous0 = false

  loop do
    if previous0
      charnum = skip_zero_run(reader, charnum)
      previous0 = false
      break if charnum > MAX_SYMBOL_VALUE

      next
    end

    max = ((2 * threshold) - 1) - remaining
    masked = reader.peek & (threshold - 1)
    if masked < max
      count = masked
      reader.skip_bits(nb_bits - 1)
    else
      count = reader.peek & ((2 * threshold) - 1)
      count -= max if count >= threshold
      reader.skip_bits(nb_bits)
    end

    actual = count - 1
    actual.negative? ? remaining += actual : remaining -= actual
    counts[charnum] = actual
    charnum += 1
    previous0 = actual.zero?

    if remaining < threshold
      break if remaining <= 1

      high = Constants.highbit32(remaining)
      nb_bits = high + 1
      threshold = 1 << high
    end
    break if charnum > MAX_SYMBOL_VALUE
  end

  if remaining != 1
    raise Omnizip::DecompressionError,
          "FSE distribution does not sum to table size (remaining=#{remaining})"
  end
  if charnum.zero?
    raise Omnizip::DecompressionError, "FSE distribution is empty"
  end

  counts = counts.first(charnum)
  [Table.build(counts, table_log), reader.bytes_consumed]
end

.skip_zero_run(reader, charnum) ⇒ Object

Count 2-bit repeat codes after a zero-count symbol.



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

def skip_zero_run(reader, charnum)
  inverted = (~reader.peek) | 0x80000000
  repeats = trailing_zeros(inverted) >> 1
  while repeats >= 12
    charnum += 36
    charnum = MAX_SYMBOL_VALUE + 1 if charnum > MAX_SYMBOL_VALUE + 1
    reader.skip_bits(24)
    inverted = (~reader.peek) | 0x80000000
    repeats = trailing_zeros(inverted) >> 1
  end
  charnum += 3 * repeats
  charnum = MAX_SYMBOL_VALUE + 1 if charnum > MAX_SYMBOL_VALUE + 1
  reader.skip_bits(2 * repeats)

  tail = reader.peek & 3
  charnum += tail
  charnum = MAX_SYMBOL_VALUE + 1 if charnum > MAX_SYMBOL_VALUE + 1
  reader.skip_bits(2)

  charnum
end

.trailing_zeros(value) ⇒ Object 



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

def trailing_zeros(value)
  count = 0
  while value.nobits?(1) && count < 32
    value >>= 1
    count += 1
  end
  count
end