Module: Omnizip::Parity::Par2cmdlineAlgorithm

Defined in:
lib/omnizip/parity/par2cmdline_algorithm.rb

Overview

Par2cmdline-compatible Reed-Solomon algorithm

This implements the EXACT algorithm from par2cmdline reedsolomon.cpp Lines 230-262 show the base value computation for encoding.

Key algorithm from par2cmdline:

unsigned int logbase = 0;
for (unsigned int index=0; index<count; index++)
{
while (gcd(G::Limit, logbase) != 1)
{
  logbase++;
}
G::ValueType base = G(logbase++).ALog();
database[index] = base;
}

Then for matrix: coefficient = base ^ exponent

Class Method Summary collapse

Class Method Details

.build_encoding_matrix(data_count, recovery_count) ⇒ Array<Array<Integer>>

Build encoding matrix using par2cmdline algorithm

Parameters:

  • data_count (Integer) —

    Number of data blocks

  • recovery_count (Integer) —

    Number of recovery blocks

Returns:

  • (Array<Array<Integer>>) —

    Encoding matrix



55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
# File 'lib/omnizip/parity/par2cmdline_algorithm.rb', line 55

def self.build_encoding_matrix(data_count, recovery_count)
  bases = compute_bases(data_count)

  matrix = Array.new(recovery_count) { Array.new(data_count) }

  recovery_count.times do |exponent|
    data_count.times do |col|
      # Matrix coefficient = base[col] ^ exponent
      matrix[exponent][col] = Galois16.power(bases[col], exponent)
    end
  end

  matrix
end

.compute_bases(data_count) ⇒ Array<Integer>

Compute base values exactly as par2cmdline does

Parameters:

  • data_count (Integer) —

    Number of data blocks

Returns:

  • (Array<Integer>) —

    Base values for each data block



29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
# File 'lib/omnizip/parity/par2cmdline_algorithm.rb', line 29

def self.compute_bases(data_count)
  bases = []
  logbase = 0
  limit = 65535 # GF(2^16) limit

  data_count.times do
    # Find next logbase where gcd(65535, logbase) == 1
    logbase += 1 while gcd(limit, logbase) != 1

    raise "Too many input blocks" if logbase >= limit

    # Use antilog to convert logbase to base value
    # This is the key: base = antilog[logbase]
    base = Galois16.antilog(logbase)
    bases << base
    logbase += 1
  end

  bases
end

.gcd(a, b) ⇒ Integer

Compute greatest common divisor

Parameters:

  • a (Integer)
  • b (Integer)

Returns:

  • (Integer) —

    GCD of a and b



75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/omnizip/parity/par2cmdline_algorithm.rb', line 75

def self.gcd(a, b)
  return 0 if a.zero? && b.zero?
  return a + b if a.zero? || b.zero?

  while a.positive? && b.positive?
    if a > b
      a %= b
    else
      b %= a
    end
  end

  a + b
end

.generate_coefficient_table(max_exponent = 100) ⇒ Hash<Integer, Integer>

Verify algorithm by generating expected coefficients

Parameters:

  • max_exponent (Integer) (defaults to: 100) —

    Maximum exponent to test

Returns:

  • (Hash<Integer, Integer>) —

    Coefficient for each exponent



94
95
96
97
98
99
100
101
102
103
104
105
 
# File 'lib/omnizip/parity/par2cmdline_algorithm.rb', line 94

def self.generate_coefficient_table(max_exponent = 100)
  bases = compute_bases(10) # Test with 10 data blocks
  coefficients = {}

  (0..max_exponent).each do |exponent|
    # For par2cmdline, ALL data blocks use the same coefficient
    # which is base[0] ^ exponent
    coefficients[exponent] = Galois16.power(bases[0], exponent)
  end

  coefficients
end