Reed–Solomon C++ Playground

My C++ Reed–Solomon code, ported to the browser so you can encode real bytes, corrupt a symbol, and watch the syndromes react — without a compiler. Flip between basic (evaluation encoder) and prod (systematic encoder + syndrome detector); the logic matches the source on the right line-for-line.

Playground

message parity

codeword

stdout

Source (C++)

#include <iostream>
        #include <vector>
        #include <cstdint>
        using namespace std;

        // GF(2^8): addition is XOR.
        uint8_t gf_add(uint8_t a, uint8_t b) { return a ^ b; }

        // multiply by x; reduce x^8 using x^8 = x^4 + x^3 + x + 1  (0x1B)
        uint8_t xtime(uint8_t value) {
            bool overflow = value & 0x80;
            value <<= 1;
            if (overflow) value ^= 0x1B;
            return value;
        }

        // Russian-peasant multiply: XOR shifted copies of x.
        uint8_t gf_mul(uint8_t x, uint8_t y) {
            uint8_t result = 0;
            while (y != 0) {
                if (y & 1) result ^= x;   // include this shifted copy
                x = xtime(x);             // x, 2x, 4x, ...
                y >>= 1;
            }
            return result;
        }

        // evaluate P(x) at a point (ascending coefficients).
        uint8_t evaluate_polynomial(const vector<uint8_t>& poly, uint8_t x) {
            uint8_t result = 0, power = 1;
            for (uint8_t coefficient : poly) {
                result = gf_add(result, gf_mul(coefficient, power));
                power  = gf_mul(power, x);
            }
            return result;
        }

        // codeword[i] = P(i) for i = 0 .. message+parity-1 : every symbol is a point.
        vector<uint8_t> evaluation_encode(const vector<uint8_t>& message, int paritySymbols) {
            int total = message.size() + paritySymbols;
            vector<uint8_t> codeword;
            for (int i = 0; i < total; i++)
                codeword.push_back(evaluate_polynomial(message, i));
            return codeword;
        }

        int main() {
            string text = "Hello";
            vector<uint8_t> message(text.begin(), text.end());
            auto codeword = evaluation_encode(message, 10);   // 5 + 10 = 15 points
        }

#include <iostream>
        #include <vector>
        #include <cstdint>
        #include <stdexcept>
        using namespace std;

        // ── GF(2^8) arithmetic ──
        uint8_t gf_add(uint8_t a, uint8_t b) { return a ^ b; }

        uint8_t xtime(uint8_t value) {
            bool overflow = value & 0x80;
            value <<= 1;
            if (overflow) value ^= 0x1B;          // x^8 = x^4 + x^3 + x + 1
            return value;
        }

        uint8_t gf_mul(uint8_t x, uint8_t y) {
            uint8_t result = 0;
            while (y != 0) {
                if (y & 1) result ^= x;
                x = xtime(x);
                y >>= 1;
            }
            return result;
        }

        uint8_t gf_inverse(uint8_t value) {
            if (value == 0) throw runtime_error("zero has no multiplicative inverse");
            for (int candidate = 1; candidate < 256; candidate++)
                if (gf_mul(value, candidate) == 1) return candidate;
            throw runtime_error("inverse not found");
        }

        uint8_t gf_div(uint8_t a, uint8_t b) { return gf_mul(a, gf_inverse(b)); }

        // ── polynomials, ascending order: {3,5,7} = 3 + 5x + 7x^2 ──
        vector<uint8_t> poly_mul(const vector<uint8_t>& a, const vector<uint8_t>& b) {
            vector<uint8_t> result(a.size() + b.size() - 1, 0);
            for (size_t i = 0; i < a.size(); i++)
                for (size_t j = 0; j < b.size(); j++)            // x^i * x^j = x^(i+j)
                    result[i+j] = gf_add(result[i+j], gf_mul(a[i], b[j]));
            return result;
        }

        vector<uint8_t> poly_mod(vector<uint8_t> dividend, const vector<uint8_t>& divisor) {
            while (dividend.size() >= divisor.size()) {
                uint8_t lead = dividend.back();
                if (lead == 0) { dividend.pop_back(); continue; }
                uint8_t factor = gf_div(lead, divisor.back());   // cancel the top term
                for (size_t i = 0; i < divisor.size(); i++) {
                    int di = dividend.size() - divisor.size() + i;
                    dividend[di] = gf_add(dividend[di], gf_mul(divisor[i], factor));
                }
                while (!dividend.empty() && dividend.back() == 0) dividend.pop_back();
            }
            return dividend;                                      // remainder
        }

        // G(x) = (x + a)(x + a^2) ... (x + a^parity),  a = 2
        vector<uint8_t> generator_polynomial(int paritySymbols) {
            vector<uint8_t> generator = {1};
            uint8_t alpha = 2;
            for (int i = 0; i < paritySymbols; i++) {
                generator = poly_mul(generator, {alpha, 1});
                alpha = gf_mul(alpha, 2);
            }
            return generator;
        }

        vector<uint8_t> systematic_encode(const vector<uint8_t>& message, int paritySymbols) {
            auto generator = generator_polynomial(paritySymbols);

            vector<uint8_t> dividend(paritySymbols, 0);
            dividend.insert(dividend.end(), message.begin(), message.end());   // M(x) * x^parity
            auto parity = poly_mod(dividend, generator);
            parity.resize(paritySymbols, 0);

            // Parity goes in the LOW-order coefficients, message above it, so the
            // codeword stays divisible by G(x). (My first draft did message ‖ parity,
            // which left a clean word with NON-zero syndromes — the bug below.)
            vector<uint8_t> codeword = parity;
            codeword.insert(codeword.end(), message.begin(), message.end());
            return codeword;
        }

        uint8_t evaluate_polynomial(const vector<uint8_t>& poly, uint8_t x) {
            uint8_t result = 0, power = 1;
            for (uint8_t coefficient : poly) {
                result = gf_add(result, gf_mul(coefficient, power));
                power  = gf_mul(power, x);
            }
            return result;
        }

        // syndromes: evaluate the received word at a, a^2, ... a^parity (roots of G).
        vector<uint8_t> syndrome(const vector<uint8_t>& codeword, int paritySymbols) {
            vector<uint8_t> s;
            uint8_t alpha = 2;
            for (int i = 0; i < paritySymbols; i++) {
                s.push_back(evaluate_polynomial(codeword, alpha));
                alpha = gf_mul(alpha, 2);
            }
            return s;
        }

        // roots of the error-locator are the error positions.
        vector<int> chien_search(const vector<uint8_t>& locator) {
            vector<int> positions;
            uint8_t alpha = 1;
            for (int i = 0; i < 255; i++) {
                if (evaluate_polynomial(locator, alpha) == 0) positions.push_back(i);
                alpha = gf_mul(alpha, 2);
            }
            return positions;
        }

        // next stage — find Lambda(x), its roots, then the magnitudes (still stubbed).
        vector<uint8_t> berlekamp_massey(const vector<uint8_t>& syndromes);
        vector<uint8_t> forney(const vector<uint8_t>& s,
                               const vector<uint8_t>& locator,
                               const vector<int>& positions);

        vector<uint8_t> decode(vector<uint8_t> codeword, int paritySymbols) {
            auto s = syndrome(codeword, paritySymbols);

            bool hasError = false;
            for (uint8_t x : s) if (x != 0) { hasError = true; break; }
            if (!hasError) return codeword;            // syndromes all zero -> clean

            // auto locator    = berlekamp_massey(s);
            // auto positions  = chien_search(locator);
            // auto magnitudes = forney(s, locator, positions);
            // for (size_t i = 0; i < positions.size(); i++)
            //     codeword[positions[i]] ^= magnitudes[i];
            return codeword;                            // detection only, for now
        }

        int main() {
            string text = "Hello";
            vector<uint8_t> message(text.begin(), text.end());
            auto codeword = systematic_encode(message, 4);
            auto s = syndrome(codeword, 4);             // {0, 0, 0, 0} when clean
            auto out = decode(codeword, 4);
        }

In prod: encode() a message, hit corrupt a byte (or click any symbol), then decode() to see the syndromes go non-zero. A clean word always gives 0 0 0 0 — that is the codeword still being divisible by G(x).