Class: Omnizip::Parity::Galois16

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

Overview

Pure implementation of Galois Field GF(2^16) arithmetic Uses generator polynomial 0x1100B (69643) as per PAR2 specification

This is pure algorithm code with no I/O dependencies. All operations are exact (no floating point) and work in GF(2^16).

Constant Summary collapse

BITS = 
16
GENERATOR =

69643 in decimal

0x1100B
FIELD_SIZE =

65536

1 << BITS
LIMIT =

65535

FIELD_SIZE - 1

Class Method Summary collapse

Class Method Details

.add(a, b) ⇒ Object Also known as: subtract

Addition in GF(2^16) - same as subtraction (XOR)



54
55
56
 
# File 'lib/omnizip/parity/galois16.rb', line 54

def add(a, b)
  (a ^ b) & 0xFFFF
end

.antilog(value) ⇒ Object

Get antilog value (inverse of log)



49
50
51
 
# File 'lib/omnizip/parity/galois16.rb', line 49

def antilog(value)
  @antilog_table[value % FIELD_SIZE]
end

.build_tables ⇒ Object

Build log and antilog tables This is called once when the class is loaded



23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
# File 'lib/omnizip/parity/galois16.rb', line 23

def build_tables
  return if @log_table && @antilog_table

  @log_table = Array.new(FIELD_SIZE)
  @antilog_table = Array.new(FIELD_SIZE)

  b = 1
  LIMIT.times do |l|
    @log_table[b] = l
    @antilog_table[l] = b

    b <<= 1
    b ^= GENERATOR if b.anybits?(FIELD_SIZE)
  end

  # Special cases for zero
  @log_table[0] = LIMIT
  @antilog_table[LIMIT] = 0
end

.divide(a, b) ⇒ Object

Division in GF(2^16)

Raises:

  • (ArgumentError) 


74
75
76
77
78
79
80
81
82
83
84
 
# File 'lib/omnizip/parity/galois16.rb', line 74

def divide(a, b)
  a &= 0xFFFF
  b &= 0xFFFF

  return 0 if a.zero?
  raise ArgumentError, "Division by zero in GF(2^16)" if b.zero?

  diff = @log_table[a] - @log_table[b]
  diff += LIMIT if diff.negative?
  @antilog_table[diff]
end

.gcd(a, b) ⇒ Object

Compute GCD using Euclidean algorithm



104
105
106
107
108
109
110
111
112
113
 
# File 'lib/omnizip/parity/galois16.rb', line 104

def gcd(a, b)
  while a != 0 && b != 0
    if a > b
      a %= b
    else
      b %= a
    end
  end
  a + b
end

.log(value) ⇒ Object

Get log value (discrete logarithm)



44
45
46
 
# File 'lib/omnizip/parity/galois16.rb', line 44

def log(value)
  @log_table[value & 0xFFFF]
end

.multiply(a, b) ⇒ Object

Multiplication in GF(2^16)



62
63
64
65
66
67
68
69
70
71
 
# File 'lib/omnizip/parity/galois16.rb', line 62

def multiply(a, b)
  a &= 0xFFFF
  b &= 0xFFFF

  return 0 if a.zero? || b.zero?

  sum = @log_table[a] + @log_table[b]
  sum -= LIMIT if sum >= LIMIT
  @antilog_table[sum]
end

.power(a, n) ⇒ Object

Power in GF(2^16): compute a^n



87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/omnizip/parity/galois16.rb', line 87

def power(a, n)
  a &= 0xFFFF

  return 1 if n.zero?
  return 0 if a.zero?

  product = @log_table[a] * n

  # Reduce modulo LIMIT using the identity:
  # product mod LIMIT = (product >> BITS) + (product & LIMIT)
  product = (product >> BITS) + (product & LIMIT)
  product -= LIMIT if product >= LIMIT

  @antilog_table[product]
end

.select_bases(count) ⇒ Object

Select base values for Reed-Solomon matrix Par2cmdline uses sequential logbases: base = antilog base = antilog = 1, base = antilog = 2, etc.

Raises:

  • (ArgumentError) 


118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
# File 'lib/omnizip/parity/galois16.rb', line 118

def select_bases(count)
  raise ArgumentError, "Too many bases requested" if count >= LIMIT

  bases = []

  count.times do |i|
    # Par2cmdline uses logbase = i (NOT i+1!)
    # This gives: base[0]=1, base[1]=2, base[2]=4, etc.
    logbase = i

    if logbase >= LIMIT
      raise ArgumentError,
            "Too many input blocks for Reed Solomon matrix"
    end

    # Convert log to actual value
    bases << @antilog_table[logbase]
  end

  bases
end