core/bch.ts

/**
 * BCH (Bose-Chaudhuri-Hocquenghem) Error-Correcting Code
 *
 * Supports configurable BCH(n, k, t) codes over GF(2^m).
 * Uses Berlekamp-Massey decoding with Chien search.
 */

import type { BchParams } from './types.js';

// Primitive polynomials for GF(2^m)
const PRIMITIVE_POLYS: Record<number, number> = {
  6: 0x43,  // x^6 + x + 1
  7: 0x89,  // x^7 + x^3 + 1
  8: 0x11D, // x^8 + x^4 + x^3 + x^2 + 1
};

/**
 * Galois Field GF(2^m) arithmetic
 */
export class GaloisField {
  readonly m: number;
  readonly size: number; // 2^m
  readonly expTable: Int32Array; // alpha^i → element
  readonly logTable: Int32Array; // element → i (log_alpha)

  constructor(m: number) {
    this.m = m;
    this.size = 1 << m;
    const poly = PRIMITIVE_POLYS[m];
    if (!poly) throw new Error(`No primitive polynomial for GF(2^${m})`);

    this.expTable = new Int32Array(this.size * 2);
    this.logTable = new Int32Array(this.size);
    this.logTable[0] = -1; // log(0) undefined

    let val = 1;
    for (let i = 0; i < this.size - 1; i++) {
      this.expTable[i] = val;
      this.logTable[val] = i;
      val <<= 1;
      if (val >= this.size) {
        val ^= poly;
        val &= this.size - 1;
      }
    }
    // Extend exp table for easier modular arithmetic
    for (let i = this.size - 1; i < this.size * 2; i++) {
      this.expTable[i] = this.expTable[i - (this.size - 1)];
    }
  }

  mul(a: number, b: number): number {
    if (a === 0 || b === 0) return 0;
    return this.expTable[this.logTable[a] + this.logTable[b]];
  }

  div(a: number, b: number): number {
    if (b === 0) throw new Error('Division by zero in GF');
    if (a === 0) return 0;
    let exp = this.logTable[a] - this.logTable[b];
    if (exp < 0) exp += this.size - 1;
    return this.expTable[exp];
  }

  pow(a: number, e: number): number {
    if (a === 0) return e === 0 ? 1 : 0;
    let log = (this.logTable[a] * e) % (this.size - 1);
    if (log < 0) log += this.size - 1;
    return this.expTable[log];
  }

  inv(a: number): number {
    if (a === 0) throw new Error('Inverse of zero');
    return this.expTable[this.size - 1 - this.logTable[a]];
  }
}

/**
 * Compute the generator polynomial for a binary BCH code.
 * The generator is the LCM of minimal polynomials of alpha^1 through alpha^(2t).
 * All minimal polynomials over GF(2) have binary (0/1) coefficients.
 */
function computeGeneratorPoly(gf: GaloisField, t: number): Uint8Array {
  // Start with g(x) = 1 as a binary polynomial
  let gen = new Uint8Array([1]);
  const order = gf.size - 1;
  const processed = new Set<number>();

  for (let i = 1; i <= 2 * t; i++) {
    // Normalize i modulo the field order
    const norm = i % order;
    if (processed.has(norm)) continue;

    // Find conjugate class of alpha^i: {i, 2i, 4i, ...} mod order
    const conjugates: number[] = [];
    let r = norm;
    for (let j = 0; j < gf.m; j++) {
      const rNorm = r % order;
      if (conjugates.includes(rNorm)) break;
      conjugates.push(rNorm);
      processed.add(rNorm);
      r = (r * 2) % order;
    }

    // Compute minimal polynomial: product of (x + alpha^c) for c in conjugate class
    // Start with [1] (= 1), then multiply by each (x + alpha^c)
    // Coefficients are in GF(2^m), but we reduce to binary at the end
    let minPoly = [1]; // GF(2^m) coefficients
    for (const c of conjugates) {
      const root = gf.expTable[c];
      const newPoly = new Array(minPoly.length + 1).fill(0);
      for (let k = 0; k < minPoly.length; k++) {
        newPoly[k + 1] ^= minPoly[k];           // x * term
        newPoly[k] ^= gf.mul(minPoly[k], root);  // root * term
      }
      minPoly = newPoly;
    }

    // Convert to binary (all coefficients should be 0 or 1 for minimal polys over GF(2))
    const binaryMinPoly = new Uint8Array(minPoly.length);
    for (let j = 0; j < minPoly.length; j++) {
      binaryMinPoly[j] = minPoly[j] === 0 ? 0 : 1;
    }

    // Multiply gen by binaryMinPoly (binary polynomial multiplication)
    const newGen = new Uint8Array(gen.length + binaryMinPoly.length - 1);
    for (let a = 0; a < gen.length; a++) {
      if (!gen[a]) continue;
      for (let b = 0; b < binaryMinPoly.length; b++) {
        if (binaryMinPoly[b]) {
          newGen[a + b] ^= 1;
        }
      }
    }
    gen = newGen;
  }

  return gen;
}

/**
 * BCH Encoder/Decoder
 */
export class BchCodec {
  readonly params: BchParams;
  readonly gf: GaloisField;
  private readonly genPoly: Uint8Array;
  private readonly genPolyDeg: number;

  constructor(params: BchParams) {
    this.params = params;
    this.gf = new GaloisField(params.m);
    this.genPoly = computeGeneratorPoly(this.gf, params.t);
    this.genPolyDeg = this.genPoly.length - 1;
  }

  /**
   * Encode message bits (length k) into codeword bits (length n)
   * Systematic encoding: message bits appear at the start
   */
  encode(message: Uint8Array): Uint8Array {
    const { n, k } = this.params;
    if (message.length !== k) {
      throw new Error(`Message length ${message.length} !== k=${k}`);
    }

    const nk = n - k;
    const codeword = new Uint8Array(n);
    codeword.set(message);

    // Compute remainder: m(x) * x^(n-k) mod g(x) using binary polynomial long division
    const dividend = new Uint8Array(n);
    // Place message coefficients at positions nk..n-1 (high degree)
    // In our polynomial representation, index i = coefficient of x^i
    // For systematic encoding: codeword(x) = m(x) * x^(n-k) + remainder
    for (let i = 0; i < k; i++) {
      dividend[nk + i] = message[i];
    }

    // Long division
    const rem = new Uint8Array(dividend);
    for (let i = n - 1; i >= nk; i--) {
      if (rem[i]) {
        for (let j = 0; j <= this.genPolyDeg; j++) {
          rem[i - this.genPolyDeg + j] ^= this.genPoly[j];
        }
      }
    }

    // Codeword = message (high positions) + remainder (low positions)
    for (let i = 0; i < nk; i++) {
      codeword[k + i] = message[i]; // Will be overwritten below
    }

    // Actually: codeword[i] for i=0..nk-1 is remainder, for i=nk..n-1 is message
    // Let's use standard ordering: codeword = [message | parity]
    // where c(x) = m(x) * x^(n-k) + (m(x) * x^(n-k) mod g(x))
    for (let i = 0; i < k; i++) {
      codeword[i] = message[i];
    }
    for (let i = 0; i < nk; i++) {
      codeword[k + i] = rem[i];
    }

    return codeword;
  }

  /**
   * Decode a received codeword. Returns corrected message bits or null if uncorrectable.
   */
  decode(received: Uint8Array): Uint8Array | null {
    const { n, k, t } = this.params;
    if (received.length !== n) {
      throw new Error(`Received length ${received.length} !== n=${n}`);
    }

    // Convert to polynomial form matching our encoding
    // received[0..k-1] = message bits, received[k..n-1] = parity bits
    // As polynomial: r(x) = sum r[i] * x^(n-k+i) for i=0..k-1, + sum r[k+i] * x^i for i=0..n-k-1
    const nk = n - k;
    const rPoly = new Uint8Array(n);
    for (let i = 0; i < k; i++) {
      rPoly[nk + i] = received[i];
    }
    for (let i = 0; i < nk; i++) {
      rPoly[i] = received[k + i];
    }

    // Compute syndromes S_1 ... S_{2t}
    // S_j = r(alpha^j) for j = 1..2t
    const syndromes = new Array<number>(2 * t);
    let hasErrors = false;

    for (let j = 0; j < 2 * t; j++) {
      let s = 0;
      let alphaPow = 1; // alpha^((j+1)*0)
      const alphaJ = this.gf.expTable[j + 1]; // alpha^(j+1)
      for (let i = 0; i < n; i++) {
        if (rPoly[i]) {
          s ^= alphaPow;
        }
        alphaPow = this.gf.mul(alphaPow, alphaJ);
      }
      syndromes[j] = s;
      if (s !== 0) hasErrors = true;
    }

    if (!hasErrors) {
      return new Uint8Array(received.subarray(0, k));
    }

    // Berlekamp-Massey to find error locator polynomial
    const sigma = this.berlekampMassey(syndromes, t);
    if (!sigma) return null;

    // Chien search to find error positions in polynomial representation
    const errorPolyPositions = this.chienSearch(sigma, n);
    if (!errorPolyPositions || errorPolyPositions.length !== sigma.length - 1) {
      return null;
    }

    // Correct errors in polynomial representation
    const correctedPoly = new Uint8Array(rPoly);
    for (const pos of errorPolyPositions) {
      if (pos >= n) return null;
      correctedPoly[pos] ^= 1;
    }

    // Verify: recompute syndromes should all be zero
    for (let j = 0; j < 2 * t; j++) {
      let s = 0;
      let alphaPow = 1;
      const alphaJ = this.gf.expTable[j + 1];
      for (let i = 0; i < n; i++) {
        if (correctedPoly[i]) s ^= alphaPow;
        alphaPow = this.gf.mul(alphaPow, alphaJ);
      }
      if (s !== 0) return null;
    }

    // Extract message bits from corrected polynomial
    const message = new Uint8Array(k);
    for (let i = 0; i < k; i++) {
      message[i] = correctedPoly[nk + i];
    }
    return message;
  }

  /**
   * Berlekamp-Massey algorithm
   */
  private berlekampMassey(syndromes: number[], t: number): number[] | null {
    const gf = this.gf;
    const twoT = 2 * t;

    let C = [1];
    let B = [1];
    let L = 0;
    let m = 1;
    let b = 1;

    for (let n = 0; n < twoT; n++) {
      let d = syndromes[n];
      for (let i = 1; i <= L; i++) {
        if (i < C.length && (n - i) >= 0) {
          d ^= gf.mul(C[i], syndromes[n - i]);
        }
      }

      if (d === 0) {
        m++;
      } else if (2 * L <= n) {
        const T = [...C];
        const factor = gf.div(d, b);
        while (C.length < B.length + m) C.push(0);
        for (let i = 0; i < B.length; i++) {
          C[i + m] ^= gf.mul(factor, B[i]);
        }
        L = n + 1 - L;
        B = T;
        b = d;
        m = 1;
      } else {
        const factor = gf.div(d, b);
        while (C.length < B.length + m) C.push(0);
        for (let i = 0; i < B.length; i++) {
          C[i + m] ^= gf.mul(factor, B[i]);
        }
        m++;
      }
    }

    if (L > t) return null;
    return C;
  }

  /**
   * Chien search: find roots of the error locator polynomial.
   *
   * sigma(x) = prod(1 - alpha^(e_j) * x), so roots are at x = alpha^(-e_j).
   * We test x = alpha^(-i) for i = 0..n-1. If sigma(alpha^(-i)) = 0,
   * then error position is i (in polynomial index).
   */
  private chienSearch(sigma: number[], n: number): number[] | null {
    const gf = this.gf;
    const positions: number[] = [];
    const degree = sigma.length - 1;
    const order = gf.size - 1;

    for (let i = 0; i < n; i++) {
      // Evaluate sigma at alpha^(-i)
      let val = sigma[0]; // = 1
      for (let j = 1; j < sigma.length; j++) {
        // alpha^(-i*j) = alpha^(order - i*j mod order)
        let exp = (order - ((i * j) % order)) % order;
        val ^= gf.mul(sigma[j], gf.expTable[exp]);
      }
      if (val === 0) {
        positions.push(i);
      }
    }

    if (positions.length !== degree) return null;
    return positions;
  }

  /**
   * Soft-decode: use soft input values to attempt decoding
   */
  decodeSoft(softBits: Float64Array): { message: Uint8Array | null; reliable: boolean } {
    const hard = new Uint8Array(softBits.length);
    for (let i = 0; i < softBits.length; i++) {
      hard[i] = softBits[i] > 0 ? 1 : 0;
    }

    const decoded = this.decode(hard);
    if (decoded) {
      let reliabilitySum = 0;
      for (let i = 0; i < softBits.length; i++) {
        reliabilitySum += Math.abs(softBits[i]);
      }
      const avgReliability = reliabilitySum / softBits.length;
      return { message: decoded, reliable: avgReliability > 0.15 };
    }

    return { message: null, reliable: false };
  }
}

/**
 * Create BCH codec from standard parameters
 */
export function createBchCodec(params: BchParams): BchCodec {
  return new BchCodec(params);
}