File size: 3,568 Bytes
bdfb884 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 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 | """
Step 2: Reed-Solomon erasure coding over the verified GF(256) field.
Split data into k systematic shards + m parity shards (n = k+m). ANY k of the n
shards reconstruct the original -- so up to m shards can be lost or corrupted and
the data still survives. This is the honest sense of "small pieces that together
rebuild the whole": redundancy, not shrinkage (n shards total n/k x the data).
All coefficients come from a Cauchy matrix over GF(256) (every square submatrix
invertible => any-k-of-n recovery). Every multiply is the GF(256) multiply that
the neural LOG/EXP units were verified bit-exact against (65536/65536), so the
fast table path here is the proven-equivalent of the neural coding core.
"""
from __future__ import annotations
from .gf256 import EXP, LOG, gf_mul
MUL = [[gf_mul(a, b) for b in range(256)] for a in range(256)] # full product table
def gf_inv(a: int) -> int:
return EXP[255 - LOG[a]] if a else 0
def cauchy(k: int, m: int):
return [[gf_inv((k + i) ^ j) for j in range(k)] for i in range(m)]
def _gen_row(r: int, k: int, C):
if r < k:
row = [0] * k
row[r] = 1
return row
return C[r - k]
def encode(data: bytes, k: int, m: int):
"""-> (shards[n], shard_len, orig_len). shards[:k] are systematic data."""
orig = len(data)
L = (orig + k - 1) // k
d = data + bytes(L * k - orig)
shards = [bytearray(d[j * L:(j + 1) * L]) for j in range(k)]
C = cauchy(k, m)
for i in range(m):
P = bytearray(L)
Ci = C[i]
for j in range(k):
MC = MUL[Ci[j]]
Dj = shards[j]
for b in range(L):
P[b] ^= MC[Dj[b]]
shards.append(P)
return shards, L, orig
def _invert(M, k):
A = [list(M[i]) + [1 if j == i else 0 for j in range(k)] for i in range(k)]
for col in range(k):
piv = col
while A[piv][col] == 0:
piv += 1
A[col], A[piv] = A[piv], A[col]
inv = gf_inv(A[col][col])
A[col] = [MUL[inv][x] for x in A[col]]
for r in range(k):
if r != col and A[r][col]:
f = A[r][col]
A[r] = [A[r][x] ^ MUL[f][A[col][x]] for x in range(2 * k)]
return [A[i][k:] for i in range(k)]
def decode(present: dict, k: int, m: int, L: int, orig: int) -> bytes:
"""present: {shard_index: bytes}; needs >= k entries."""
idxs = sorted(present.keys())[:k]
C = cauchy(k, m)
Minv = _invert([_gen_row(r, k, C) for r in idxs], k)
data_shards = [bytearray(L) for _ in range(k)]
for j in range(k):
row = Minv[j]
Dj = data_shards[j]
for t, r in enumerate(idxs):
c = row[t]
if not c:
continue
MC = MUL[c]
src = present[r]
for b in range(L):
Dj[b] ^= MC[src[b]]
return b"".join(bytes(s) for s in data_shards)[:orig]
def neural_parity_equiv(net_log, net_exp, k=4, m=2, L=16) -> bool:
"""Compute one parity shard with the NEURAL gf_mul and confirm it matches the
golden coding -- i.e. the verified units drive the erasure code bit-exactly."""
import os
from .gf256 import gf_mul_neural
data = os.urandom(L * k)
shards, _, _ = encode(data, k, m)
C = cauchy(k, m)
Dsh = [data[j * L:(j + 1) * L] for j in range(k)]
P = bytearray(L)
for j in range(k):
for b in range(L):
P[b] ^= gf_mul_neural(C[0][j], Dsh[j][b], net_log, net_exp)
return bytes(P) == bytes(shards[k]) # neural parity == golden parity
|