ReedSolomon.kt

1package com.peachpasswords.codex23/**4 * Systematic Reed-Solomon erasure codec over GF(2⁸), Backblaze/JavaReedSolomon5 * construction (Vandermonde matrix made systematic). Mirrors the role of the6 * browser's `reed-solomon-erasure` WASM: encode fills parity shards in place;7 * reconstruct repairs any missing shards given an availability mask, tolerating8 * up to `parityShards` losses.9 *10 * Shards are equal-length byte arrays; the code operates byte-column-wise.11 */12object Galois {13    private val EXP = IntArray(512)14    private val LOG = IntArray(256)1516    init {17        var x = 118        for (i in 0 until 255) {19            EXP[i] = x20            LOG[x] = i21            x = x shl 122            if (x and 0x100 != 0) x = x xor 0x11d23        }24        for (i in 255 until 512) EXP[i] = EXP[i - 255]25    }2627    fun mul(a: Int, b: Int): Int =28        if (a == 0 || b == 0) 0 else EXP[LOG[a and 0xff] + LOG[b and 0xff]]2930    fun div(a: Int, b: Int): Int {31        require(b != 0) { "divide by zero" }32        if (a == 0) return 033        return EXP[(LOG[a and 0xff] - LOG[b and 0xff] + 255) % 255]34    }3536    /** Field exponentiation a^n (used to build the Vandermonde matrix). */37    fun exp(a: Int, n: Int): Int {38        if (n == 0) return 139        if (a == 0) return 040        var result = 141        repeat(n) { result = mul(result, a) }42        return result43    }44}4546/** Dense GF(2⁸) matrix with the operations RS needs (multiply, invert). */47private class GfMatrix(val rows: Int, val cols: Int) {48    val data = Array(rows) { IntArray(cols) }4950    fun times(other: GfMatrix): GfMatrix {51        require(cols == other.rows)52        val out = GfMatrix(rows, other.cols)53        for (r in 0 until rows) for (c in 0 until other.cols) {54            var v = 055            for (k in 0 until cols) v = v xor Galois.mul(data[r][k], other.data[k][c])56            out.data[r][c] = v57        }58        return out59    }6061    /** Gaussian-elimination inverse. Throws if singular. */62    fun invert(): GfMatrix {63        require(rows == cols)64        val work = GfMatrix(rows, cols * 2)65        for (r in 0 until rows) {66            System.arraycopy(data[r], 0, work.data[r], 0, cols)67            work.data[r][cols + r] = 168        }69        work.gaussianEliminate()70        val out = GfMatrix(rows, cols)71        for (r in 0 until rows) System.arraycopy(work.data[r], cols, out.data[r], 0, cols)72        return out73    }7475    private fun gaussianEliminate() {76        for (r in 0 until rows) {77            if (data[r][r] == 0) {78                var swap = r + 179                while (swap < rows && data[swap][r] == 0) swap++80                require(swap < rows) { "matrix is singular" }81                val tmp = data[r]; data[r] = data[swap]; data[swap] = tmp82            }83            val pivot = data[r][r]84            if (pivot != 1) for (c in 0 until cols) data[r][c] = Galois.div(data[r][c], pivot)85            for (other in 0 until rows) {86                if (other == r) continue87                val factor = data[other][r]88                if (factor != 0) for (c in 0 until cols) {89                    data[other][c] = data[other][c] xor Galois.mul(factor, data[r][c])90                }91            }92        }93    }9495    companion object {96        /** Encoding matrix: rows 0..dataShards-1 form the identity (systematic). */97        fun buildEncoding(dataShards: Int, totalShards: Int): GfMatrix {98            val vander = GfMatrix(totalShards, dataShards)99            for (r in 0 until totalShards) for (c in 0 until dataShards) {100                vander.data[r][c] = Galois.exp(r, c)101            }102            val top = GfMatrix(dataShards, dataShards)103            for (r in 0 until dataShards) System.arraycopy(vander.data[r], 0, top.data[r], 0, dataShards)104            return vander.times(top.invert())105        }106    }107}108109object ReedSolomon {110111    /** Fill the parity shards (indices dataShards..total-1) in place. */112    fun encode(shards: Array<ByteArray>, dataShards: Int, parityShards: Int) {113        val total = dataShards + parityShards114        require(shards.size == total) { "shard count mismatch" }115        val matrix = GfMatrix.buildEncoding(dataShards, total)116        val shardSize = shards[0].size117        for (parityRow in dataShards until total) {118            val out = shards[parityRow]119            for (b in 0 until shardSize) {120                var v = 0121                for (dataRow in 0 until dataShards) {122                    v = v xor Galois.mul(matrix.data[parityRow][dataRow], shards[dataRow][b].toInt() and 0xff)123                }124                out[b] = v.toByte()125            }126        }127    }128129    /**130     * Reconstruct missing shards in place. [present] marks which shards were131     * recovered intact; at least [dataShards] must be present. Repairs the132     * data shards (and, if asked, parity) by inverting the sub-matrix of133     * present rows.134     */135    fun reconstruct(136        shards: Array<ByteArray>,137        dataShards: Int,138        parityShards: Int,139        present: BooleanArray,140    ) {141        val total = dataShards + parityShards142        val shardSize = shards.first { it.isNotEmpty() }.size143        val presentCount = present.count { it }144        if (presentCount < dataShards) {145            throw CodexException(CodexErrorCode.INSUFFICIENT_CHUNKS, "too few shards present: $presentCount < $dataShards")146        }147148        val matrix = GfMatrix.buildEncoding(dataShards, total)149150        // Build a dataShards×dataShards sub-matrix from the first dataShards151        // present rows, plus the corresponding present shard data.152        val sub = GfMatrix(dataShards, dataShards)153        val subShards = arrayOfNulls<ByteArray>(dataShards)154        var subRow = 0155        var r = 0156        while (subRow < dataShards) {157            if (present[r]) {158                System.arraycopy(matrix.data[r], 0, sub.data[subRow], 0, dataShards)159                subShards[subRow] = shards[r]160                subRow++161            }162            r++163        }164        val decode = sub.invert()165166        // Recover every missing data shard.167        for (missing in 0 until dataShards) {168            if (present[missing]) continue169            val out = ByteArray(shardSize)170            for (b in 0 until shardSize) {171                var v = 0172                for (k in 0 until dataShards) {173                    v = v xor Galois.mul(decode.data[missing][k], subShards[k]!![b].toInt() and 0xff)174                }175                out[b] = v.toByte()176            }177            shards[missing] = out178            present[missing] = true179        }180181        // Recompute any missing parity from the now-complete data shards.182        for (parityRow in dataShards until total) {183            if (present[parityRow]) continue184            val out = ByteArray(shardSize)185            for (b in 0 until shardSize) {186                var v = 0187                for (dataRow in 0 until dataShards) {188                    v = v xor Galois.mul(matrix.data[parityRow][dataRow], shards[dataRow][b].toInt() and 0xff)189                }190                out[b] = v.toByte()191            }192            shards[parityRow] = out193            present[parityRow] = true194        }195    }196}