// Author:  cirakg & claude ai
// Summary: Reed-Solomon error-correction codewords over GF(2^m) for QR (and later Data Matrix and Aztec).
//
// A Field is GF(2^m) with a primitive polynomial and the exponent the
// generator's roots start at (QR: 0x11D, base 0; Data Matrix: 0x12D,
// base 1). Generator polynomials are cached per field and length. ecc()
// is the remainder of data * x^n divided by the generator: the standard
// systematic encoding, one multiply-accumulate per data symbol and EC
// symbol, so a caller budgets blocks per job step.

import Toybox.Lang;

module ReedSolomon {

    class Field {
        var size as Number;
        var exp as Array<Number>;
        var log as Array<Number>;
        var base as Number;
        private var _generators as Dictionary<Number, Array<Number>> = {} as Dictionary<Number, Array<Number>>;

        // primitive: the field polynomial including x^m (0x11D for GF(256)).
        function initialize(primitive as Number, fieldSize as Number, generatorBase as Number) {
            size = fieldSize;
            base = generatorBase;
            exp = new [2 * fieldSize] as Array<Number>;
            log = new [fieldSize] as Array<Number>;
            var x = 1;
            for (var i = 0; i < fieldSize - 1; i++) {
                exp[i] = x;
                log[x] = i;
                x <<= 1;
                if (x >= fieldSize) {
                    x ^= primitive;
                }
            }
            // Doubled table: exp[a + b] needs no modulo.
            for (var i = fieldSize - 1; i < 2 * fieldSize; i++) {
                exp[i] = exp[i - (fieldSize - 1)];
            }
            log[0] = 0;
        }

        function multiply(a as Number, b as Number) as Number {
            if (a == 0 || b == 0) {
                return 0;
            }
            return exp[log[a] + log[b]];
        }

        // Coefficients of the generator with n roots, highest degree first,
        // without the leading 1.
        function generator(n as Number) as Array<Number> {
            var cached = _generators[n];
            if (cached != null) {
                return cached;
            }
            var g = [1] as Array<Number>;
            for (var i = 0; i < n; i++) {
                // Multiply by (x - a^(base + i)); in GF(2^m) minus is plus.
                var root = exp[(base + i) % (size - 1)];
                var next = new [g.size() + 1] as Array<Number>;
                for (var k = 0; k < next.size(); k++) {
                    next[k] = 0;
                }
                for (var k = 0; k < g.size(); k++) {
                    next[k] = next[k] ^ g[k];
                    next[k + 1] = next[k + 1] ^ multiply(g[k], root);
                }
                g = next;
            }
            var coefficients = g.slice(1, null) as Array<Number>;
            _generators[n] = coefficients;
            return coefficients;
        }
    }

    // The n error-correction symbols of data (both as symbol values).
    function ecc(field as Field, data as Array<Number>, n as Number) as Array<Number> {
        var g = field.generator(n);
        var rem = new [n] as Array<Number>;
        for (var k = 0; k < n; k++) {
            rem[k] = 0;
        }
        var exp = field.exp;
        var log = field.log;
        var logG = new [n] as Array<Number>;
        for (var k = 0; k < n; k++) {
            logG[k] = g[k] == 0 ? -1 : log[g[k]];
        }
        for (var i = 0; i < data.size(); i++) {
            var factor = data[i] ^ rem[0];
            // Shift the remainder left by one symbol.
            for (var k = 0; k < n - 1; k++) {
                rem[k] = rem[k + 1];
            }
            rem[n - 1] = 0;
            if (factor != 0) {
                var lf = log[factor];
                for (var k = 0; k < n; k++) {
                    var lg = logG[k];
                    if (lg >= 0) {
                        rem[k] = rem[k] ^ exp[lf + lg];
                    }
                }
            }
        }
        return rem;
    }
}