Class: Omnizip::Parity::ReedSolomonMatrix

Inherits:
Object
  • Object
show all
Defined in:
lib/omnizip/parity/reed_solomon_matrix.rb

Overview

Reed-Solomon matrix for incremental chunk processing

This class computes the RS matrix coefficients ONCE using Gaussian elimination, then provides methods to apply those coefficients incrementally to data chunks.

Based on par2cmdline's approach (reedsolomon.h, par2repairer.cpp)

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(present_indices, missing_indices, recovery_exponents, total_inputs, block_size) ⇒ ReedSolomonMatrix

Initialize matrix

Parameters:

  • present_indices (Array<Integer>) —

    Indices of available data blocks

  • missing_indices (Array<Integer>) —

    Indices of blocks to recover

  • recovery_exponents (Array<Integer>) —

    Exponents of recovery blocks to use

  • total_inputs (Integer) —

    Total number of input blocks (present + missing)

  • block_size (Integer) —

    Block size in bytes



44
45
46
47
48
49
50
51
52
53
54
 
# File 'lib/omnizip/parity/reed_solomon_matrix.rb', line 44

def initialize(present_indices, missing_indices, recovery_exponents,
total_inputs, block_size)
  @present_indices = present_indices.sort
  @missing_indices = missing_indices.sort
  @recovery_exponents = recovery_exponents.sort
  @total_inputs = total_inputs
  @block_size = block_size
  @matrix = nil # Computed by compute!
  @bases = nil  # Computed by compute!
  @used_recovery_exponents = nil # Computed by compute!
end

Instance Attribute Details

#bases ⇒ Array<Integer> (readonly)

Returns Selected bases for Galois field.

Returns:

  • (Array<Integer>) —

    Selected bases for Galois field



35
36
37
 
# File 'lib/omnizip/parity/reed_solomon_matrix.rb', line 35

def bases
  @bases
end

#block_size ⇒ Integer (readonly)

Returns Block size in bytes.

Returns:

  • (Integer) —

    Block size in bytes



29
30
31
 
# File 'lib/omnizip/parity/reed_solomon_matrix.rb', line 29

def block_size
  @block_size
end

#matrix ⇒ Array<Array<Integer>> (readonly)

Returns Solved matrix coefficients (num_missing x num_missing).

Returns:

  • (Array<Array<Integer>>) —

    Solved matrix coefficients (num_missing x num_missing)



32
33
34
 
# File 'lib/omnizip/parity/reed_solomon_matrix.rb', line 32

def matrix
  @matrix
end

#missing_indices ⇒ Array<Integer> (readonly)

Returns Indices of missing input blocks.

Returns:

  • (Array<Integer>) —

    Indices of missing input blocks



17
18
19
 
# File 'lib/omnizip/parity/reed_solomon_matrix.rb', line 17

def missing_indices
  @missing_indices
end

#present_indices ⇒ Array<Integer> (readonly)

Returns Indices of present input blocks.

Returns:

  • (Array<Integer>) —

    Indices of present input blocks



14
15
16
 
# File 'lib/omnizip/parity/reed_solomon_matrix.rb', line 14

def present_indices
  @present_indices
end

#recovery_exponents ⇒ Array<Integer> (readonly)

Returns All available recovery exponents.

Returns:

  • (Array<Integer>) —

    All available recovery exponents



20
21
22
 
# File 'lib/omnizip/parity/reed_solomon_matrix.rb', line 20

def recovery_exponents
  @recovery_exponents
end

#total_inputs ⇒ Integer (readonly)

Returns Total number of input blocks.

Returns:

  • (Integer) —

    Total number of input blocks



26
27
28
 
# File 'lib/omnizip/parity/reed_solomon_matrix.rb', line 26

def total_inputs
  @total_inputs
end

#used_recovery_exponents ⇒ Array<Integer> (readonly)

Returns Recovery exponents actually used (first num_missing).

Returns:

  • (Array<Integer>) —

    Recovery exponents actually used (first num_missing)



23
24
25
 
# File 'lib/omnizip/parity/reed_solomon_matrix.rb', line 23

def used_recovery_exponents
  @used_recovery_exponents
end

Instance Method Details

#coefficient(output_idx, recovery_idx) ⇒ Integer

Get matrix coefficient for computing missing blocks

This returns the coefficient from A^-1 matrix that tells us how much each recovery block contributes to each missing block.

After transposition, matrix structure is:

  • matrix[output_idx] (rows=recovery, cols=missing)

For x = A^-1 * b:

x[output_idx] = sum over recovery_idx of A^-1[output_idx][recovery_idx] * b[recovery_idx]

Due to transpose, we access as: matrix[output_idx]

Parameters:

  • output_idx (Integer) —

    Output block index (0..missing_count-1)

  • recovery_idx (Integer) —

    Recovery block index (0..recovery_count-1)

Returns:

  • (Integer) —

    Galois field coefficient



119
120
121
122
123
124
 
# File 'lib/omnizip/parity/reed_solomon_matrix.rb', line 119

def coefficient(output_idx, recovery_idx)
  raise "Matrix not computed - call compute! first" unless @matrix

  # After transpose, indices are swapped: @matrix[recovery_idx][output_idx]
  @matrix[recovery_idx][output_idx]
end

#compute! ⇒ void

This method returns an undefined value.

Compute matrix coefficients using Gaussian elimination

CORRECT FORMULATION: We solve: A * x = b where:

This method computes A^-1, so we can later compute: x = A^-1 * b



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
 
# File 'lib/omnizip/parity/reed_solomon_matrix.rb', line 69

def compute!
  @bases = Par2cmdlineAlgorithm.compute_bases(total_inputs)

  num_missing = missing_indices.size

  # Select which recovery exponents to use (first num_missing)
  @used_recovery_exponents = recovery_exponents.first(num_missing)

  # Build A matrix: A[i,j] = base[missing[j]]^exponent[i]
  # This is num_missing x num_missing (SQUARE)
  a_matrix = Array.new(num_missing) { Array.new(num_missing, 0) }

  @used_recovery_exponents.each_with_index do |exponent, row|
    missing_indices.each_with_index do |idx, col|
      a_matrix[row][col] = Galois16.power(@bases[idx], exponent)
    end
  end

  # Invert A matrix using Gaussian elimination
  # Create augmented matrix [A | I]
  identity = Array.new(num_missing) do |i|
    Array.new(num_missing) do |j|
      i == j ? 1 : 0
    end
  end

  gaussian_elimination!(a_matrix, identity)

  # Store inverted matrix (now in identity position)
  # IMPORTANT: Transpose it so rows=missing_indices, cols=recovery_indices
  # This allows direct indexing: matrix[output_idx][recovery_idx]
  @matrix = identity.transpose
end

#output_count ⇒ Integer

Get number of output blocks (missing)

Returns:

  • (Integer) —

    Output count



185
186
187
 
# File 'lib/omnizip/parity/reed_solomon_matrix.rb', line 185

def output_count
  missing_indices.size
end

#present_contribution_coefficient(present_idx, recovery_exponent) ⇒ Integer

Get coefficient for present block contribution to b vector

Returns how much a present block contributes when building b vector. This is: -base^exponent

Parameters:

  • present_idx (Integer) —

    Index of present data block

  • recovery_exponent (Integer) —

    Recovery block exponent

Returns:

  • (Integer) —

    Galois field coefficient



134
135
136
 
# File 'lib/omnizip/parity/reed_solomon_matrix.rb', line 134

def present_contribution_coefficient(present_idx, recovery_exponent)
  Galois16.power(@bases[present_idx], recovery_exponent)
end

#process_chunk(factor, input_chunk, output_block, chunk_size, output_offset: 0) ⇒ Object

Process a chunk of data: output_chunk ^= input_chunk * factor

This is called thousands of times during repair to incrementally build up each recovered block chunk by chunk.

Parameters:

  • factor (Integer) —

    Galois field multiplier (from matrix)

  • input_chunk (String) —

    Input chunk data

  • output_block (String) —

    Full output block (modified in place)

  • chunk_size (Integer) —

    Chunk size in bytes (must be even)

  • output_offset (Integer) (defaults to: 0) —

    Offset within output block where to write



148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
 
# File 'lib/omnizip/parity/reed_solomon_matrix.rb', line 148

def process_chunk(factor, input_chunk, output_block, chunk_size,
output_offset: 0)
  return if factor.zero? # Optimization

  num_words = chunk_size / 2

  num_words.times do |i|
    input_offset = i * 2
    block_offset = output_offset + (i * 2)

    # Read 16-bit words (little-endian)
    input_word = input_chunk.getbyte(input_offset) |
      (input_chunk.getbyte(input_offset + 1) << 8)

    output_word = output_block.getbyte(block_offset) |
      (output_block.getbyte(block_offset + 1) << 8)

    # Galois multiplication and addition (XOR)
    result = Galois16.add(output_word,
                          Galois16.multiply(input_word, factor))

    # Write back as bytes (little-endian)
    output_block.setbyte(block_offset, result & 0xFF)
    output_block.setbyte(block_offset + 1, (result >> 8) & 0xFF)
  end
end

#recovery_count ⇒ Integer

Get number of recovery blocks used

Returns:

  • (Integer) —

    Recovery count



178
179
180
 
# File 'lib/omnizip/parity/reed_solomon_matrix.rb', line 178

def recovery_count
  recovery_exponents.size
end