RAID 7 test

raid.cpp

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

class RAID7 {
private:
    static const uint16_t GF_POLY = 0x11D;  // x^8 + x^4 + x^3 + x^2 + 1
    
    vector<uint8_t> gf_exp;
    vector<uint8_t> gf_log;
    
public:
    RAID7() {
        init_gf_tables();
    }
    
    void init_gf_tables() {
        gf_exp.resize(512, 0);
        gf_log.resize(256, 0);
        
        uint16_t x = 1;
        for (int i = 0; i < 255; i++) {
            gf_exp[i] = x;
            gf_log[x] = i;
            x <<= 1;
            if (x & 0x100) x ^= GF_POLY;
        }
        
        for (int i = 255; i < 512; i++) {
            gf_exp[i] = gf_exp[i - 255];
        }
    }
    
    uint8_t gf_mul(uint8_t a, uint8_t b) {
        if (a == 0 || b == 0) return 0;
        return gf_exp[gf_log[a] + gf_log[b]];
    }
    
    uint8_t gf_div(uint8_t a, uint8_t b) {
        if (a == 0) return 0;
        if (b == 0) throw runtime_error("Division by zero in GF");
        return gf_exp[gf_log[a] + 255 - gf_log[b]];
    }
    
    uint8_t gf_pow(uint8_t base, int exp) {
        if (base == 0) return 0;
        if (exp == 0) return 1;
        return gf_exp[(gf_log[base] * exp) % 255];
    }
    
    // Matrix operations for solving 3x3 systems in GF(2^8)
    struct Matrix3x3 {
        uint8_t m[3][3];
        uint8_t det;
        
        Matrix3x3(uint8_t a00, uint8_t a01, uint8_t a02,
                  uint8_t a10, uint8_t a11, uint8_t a12,
                  uint8_t a20, uint8_t a21, uint8_t a22) {
            m[0][0] = a00; m[0][1] = a01; m[0][2] = a02;
            m[1][0] = a10; m[1][1] = a11; m[1][2] = a12;
            m[2][0] = a20; m[2][1] = a21; m[2][2] = a22;
        }
    };
    
    uint8_t gf_det3x3(const Matrix3x3& mat, RAID7& raid) {
        // Calculate 3x3 determinant in GF(2^8)
        uint8_t term1 = raid.gf_mul(mat.m[0][0], raid.gf_mul(mat.m[1][1], mat.m[2][2]));
        uint8_t term2 = raid.gf_mul(mat.m[0][1], raid.gf_mul(mat.m[1][2], mat.m[2][0]));
        uint8_t term3 = raid.gf_mul(mat.m[0][2], raid.gf_mul(mat.m[1][0], mat.m[2][1]));
        uint8_t term4 = raid.gf_mul(mat.m[0][2], raid.gf_mul(mat.m[1][1], mat.m[2][0]));
        uint8_t term5 = raid.gf_mul(mat.m[0][1], raid.gf_mul(mat.m[1][0], mat.m[2][2]));
        uint8_t term6 = raid.gf_mul(mat.m[0][0], raid.gf_mul(mat.m[1][2], mat.m[2][1]));
        
        return (term1 ^ term2 ^ term3) ^ (term4 ^ term5 ^ term6);
    }
    
    // Generate triple parity for RAID 7
    struct TripleParity {
        vector<uint8_t> P;  // XOR parity
        vector<uint8_t> Q;  // Reed-Solomon parity 1
        vector<uint8_t> R;  // Reed-Solomon parity 2
    };
    
    TripleParity generate_parity(const vector<vector<uint8_t>>& data_disks) {
        if (data_disks.empty()) return {{}, {}, {}};
        
        size_t block_size = data_disks[0].size();
        size_t num_data_disks = data_disks.size();
        
        TripleParity parity;
        parity.P.resize(block_size, 0);
        parity.Q.resize(block_size, 0);
        parity.R.resize(block_size, 0);
        
        for (size_t i = 0; i < block_size; i++) {
            // P parity: simple XOR
            for (size_t disk = 0; disk < num_data_disks; disk++) {
                parity.P[i] ^= data_disks[disk][i];
            }
            
            // Q parity: Reed-Solomon using powers of 2
            for (size_t disk = 0; disk < num_data_disks; disk++) {
                parity.Q[i] ^= gf_mul(gf_pow(2, disk), data_disks[disk][i]);
            }
            
            // R parity: Reed-Solomon using powers of 3
            for (size_t disk = 0; disk < num_data_disks; disk++) {
                parity.R[i] ^= gf_mul(gf_pow(3, disk), data_disks[disk][i]);
            }
        }
        
        return parity;
    }
    
    // Recover from single disk failure
    vector<uint8_t> recover_single_disk(const vector<vector<uint8_t>>& available_disks, 
                                       const vector<uint8_t>& P_parity) {
        if (available_disks.empty()) return {};
        
        size_t block_size = available_disks[0].size();
        vector<uint8_t> recovered(block_size, 0);
        
        for (size_t i = 0; i < block_size; i++) {
            recovered[i] = P_parity[i];
            for (const auto& disk : available_disks) {
                recovered[i] ^= disk[i];
            }
        }
        
        return recovered;
    }
    
    // Recover from dual disk failure
    pair<vector<uint8_t>, vector<uint8_t>> recover_dual_disk(
        const vector<vector<uint8_t>>& available_disks,
        const TripleParity& parity,
        int failed_disk1, int failed_disk2,
        int total_data_disks) {
        
        if (available_disks.empty()) return {{}, {}};
        
        size_t block_size = available_disks[0].size();
        vector<uint8_t> recovered1(block_size);
        vector<uint8_t> recovered2(block_size);
        
        for (size_t i = 0; i < block_size; i++) {
            uint8_t known_P = 0, known_Q = 0;
            int disk_index = 0;
            
            for (const auto& disk : available_disks) {
                while (disk_index == failed_disk1 || disk_index == failed_disk2) {
                    disk_index++;
                }
                
                known_P ^= disk[i];
                known_Q ^= gf_mul(gf_pow(2, disk_index), disk[i]);
                disk_index++;
            }
            
            uint8_t target_P = parity.P[i] ^ known_P;
            uint8_t target_Q = parity.Q[i] ^ known_Q;
            
            uint8_t g1 = gf_pow(2, failed_disk1);
            uint8_t g2 = gf_pow(2, failed_disk2);
            
            uint8_t denominator = g1 ^ g2;
            if (denominator == 0) {
                throw runtime_error("Cannot recover: identical generator powers");
            }
            
            uint8_t B_value = gf_div(target_Q ^ gf_mul(g1, target_P), denominator);
            uint8_t A_value = target_P ^ B_value;
            
            recovered1[i] = A_value;
            recovered2[i] = B_value;
        }
        
        return {recovered1, recovered2};
    }
    
    // Recover from TRIPLE disk failure (RAID 7 specialty!)
    tuple<vector<uint8_t>, vector<uint8_t>, vector<uint8_t>> recover_triple_disk(
        const vector<vector<uint8_t>>& available_disks,
        const TripleParity& parity,
        int failed_disk1, int failed_disk2, int failed_disk3,
        int total_data_disks) {
        
        if (available_disks.empty()) return {{}, {}, {}};
        
        size_t block_size = available_disks[0].size();
        vector<uint8_t> recovered1(block_size);
        vector<uint8_t> recovered2(block_size);
        vector<uint8_t> recovered3(block_size);
        
        for (size_t i = 0; i < block_size; i++) {
            // Calculate known contributions
            uint8_t known_P = 0, known_Q = 0, known_R = 0;
            int disk_index = 0;
            
            for (const auto& disk : available_disks) {
                while (disk_index == failed_disk1 || disk_index == failed_disk2 || disk_index == failed_disk3) {
                    disk_index++;
                }
                
                known_P ^= disk[i];
                known_Q ^= gf_mul(gf_pow(2, disk_index), disk[i]);
                known_R ^= gf_mul(gf_pow(3, disk_index), disk[i]);
                disk_index++;
            }
            
            // Set up 3x3 system:
            // A ⊕ B ⊕ C = target_P
            // g1*A ⊕ g2*B ⊕ g3*C = target_Q  
            // h1*A ⊕ h2*B ⊕ h3*C = target_R
            
            uint8_t target_P = parity.P[i] ^ known_P;
            uint8_t target_Q = parity.Q[i] ^ known_Q;
            uint8_t target_R = parity.R[i] ^ known_R;
            
            uint8_t g1 = gf_pow(2, failed_disk1);
            uint8_t g2 = gf_pow(2, failed_disk2);
            uint8_t g3 = gf_pow(2, failed_disk3);
            
            uint8_t h1 = gf_pow(3, failed_disk1);
            uint8_t h2 = gf_pow(3, failed_disk2);
            uint8_t h3 = gf_pow(3, failed_disk3);
            
            // Solve 3x3 system using Cramer's rule in GF(2^8)
            Matrix3x3 main_matrix(1, 1, 1, g1, g2, g3, h1, h2, h3);
            uint8_t det_main = gf_det3x3(main_matrix, *this);
            
            if (det_main == 0) {
                throw runtime_error("Cannot recover: singular matrix");
            }
            
            // Solve for A (replace first column with targets)
            Matrix3x3 matrix_A(target_P, 1, 1, target_Q, g2, g3, target_R, h2, h3);
            uint8_t det_A = gf_det3x3(matrix_A, *this);
            recovered1[i] = gf_div(det_A, det_main);
            
            // Solve for B (replace second column with targets)
            Matrix3x3 matrix_B(1, target_P, 1, g1, target_Q, g3, h1, target_R, h3);
            uint8_t det_B = gf_det3x3(matrix_B, *this);
            recovered2[i] = gf_div(det_B, det_main);
            
            // Solve for C (replace third column with targets)
            Matrix3x3 matrix_C(1, 1, target_P, g1, g2, target_Q, h1, h2, target_R);
            uint8_t det_C = gf_det3x3(matrix_C, *this);
            recovered3[i] = gf_div(det_C, det_main);
        }
        
        return {recovered1, recovered2, recovered3};
    }
    
    void print_disk(const string& name, const vector<uint8_t>& disk) {
        cout << name << ": ";
        for (uint8_t byte : disk) {
            cout << setw(3) << int(byte) << " ";
        }
        cout << "\n";
    }
};

void raid7_comprehensive_demo() {
    RAID7 raid;
    
    cout << "=== RAID 7: Triple Parity Demo ===\n\n";
    
    // Create 5 data disks
    vector<vector<uint8_t>> data_disks = {
        {10, 20, 30},     // Disk 0
        {40, 50, 60},     // Disk 1  
        {70, 80, 90},     // Disk 2
        {100, 110, 121},  // Disk 3
        {130, 140, 157}   // Disk 4
    };
    
    cout << "Original Data Disks:\n";
    for (size_t i = 0; i < data_disks.size(); i++) {
        raid.print_disk("Disk " + to_string(i), data_disks[i]);
    }
    
    // Generate triple parity
    auto parity = raid.generate_parity(data_disks);
    cout << "\nGenerated Triple Parity:\n";
    raid.print_disk("P Parity (XOR)", parity.P);
    raid.print_disk("Q Parity (2^i)", parity.Q);
    raid.print_disk("R Parity (3^i)", parity.R);
    
    // Test 1: Single disk failure
    cout << "\n=== Test 1: Single Disk Failure (Disk 2) ===\n";
    vector<vector<uint8_t>> available_single = {data_disks[0], data_disks[1], data_disks[3], data_disks[4]};
    auto recovered_single = raid.recover_single_disk(available_single, parity.P);
    
    raid.print_disk("Original Disk 2", data_disks[2]);
    raid.print_disk("Recovered Disk 2", recovered_single);
    cout << "Single recovery: " << (data_disks[2] == recovered_single ? "SUCCESS" : "FAILED") << "\n";
    
    // Test 2: Dual disk failure
    cout << "\n=== Test 2: Dual Disk Failure (Disks 1 and 3) ===\n";
    vector<vector<uint8_t>> available_dual = {data_disks[0], data_disks[2], data_disks[4]};
    auto [recovered_1, recovered_3] = raid.recover_dual_disk(available_dual, parity, 1, 3, 5);
    
    raid.print_disk("Original Disk 1", data_disks[1]);
    raid.print_disk("Recovered Disk 1", recovered_1);
    raid.print_disk("Original Disk 3", data_disks[3]);
    raid.print_disk("Recovered Disk 3", recovered_3);
    
    bool dual_success = (data_disks[1] == recovered_1) && (data_disks[3] == recovered_3);
    cout << "Dual recovery: " << (dual_success ? "SUCCESS" : "FAILED") << "\n";
    
    // Test 3: TRIPLE disk failure (RAID 7 specialty!)
    cout << "\n=== Test 3: TRIPLE Disk Failure (Disks 0, 2, and 4) ===\n";
    vector<vector<uint8_t>> available_triple = {data_disks[1], data_disks[3]};
    auto [recovered_0, recovered_2, recovered_4] = raid.recover_triple_disk(available_triple, parity, 0, 2, 4, 5);
    
    raid.print_disk("Original Disk 0", data_disks[0]);
    raid.print_disk("Recovered Disk 0", recovered_0);
    raid.print_disk("Original Disk 2", data_disks[2]);
    raid.print_disk("Recovered Disk 2", recovered_2);
    raid.print_disk("Original Disk 4", data_disks[4]);
    raid.print_disk("Recovered Disk 4", recovered_4);
    
    bool triple_success = (data_disks[0] == recovered_0) && 
                         (data_disks[2] == recovered_2) && 
                         (data_disks[4] == recovered_4);
    cout << "TRIPLE recovery: " << (triple_success ? "SUCCESS" : "FAILED") << "\n";
    
    // Explain the mathematics
    cout << "\n=== RAID 7 Mathematical Foundation ===\n";
    cout << "RAID 7 uses THREE parity schemes:\n";
    cout << "1. P = D0 ⊕ D1 ⊕ D2 ⊕ D3 ⊕ D4 (XOR parity)\n";
    cout << "2. Q = 2^0×D0 ⊕ 2^1×D1 ⊕ 2^2×D2 ⊕ 2^3×D3 ⊕ 2^4×D4 (Reed-Solomon base 2)\n";
    cout << "3. R = 3^0×D0 ⊕ 3^1×D1 ⊕ 3^2×D2 ⊕ 3^3×D3 ⊕ 3^4×D4 (Reed-Solomon base 3)\n\n";
    cout << "Triple failure recovery solves 3×3 linear system in GF(2^8)\n";
    cout << "Can survive ANY 3 simultaneous disk failures!\n";
    cout << "Storage efficiency: n/(n+3) where n = data disks\n";
}

int main() {
    try {
        raid7_comprehensive_demo();
    } catch (const exception& e) {
        cerr << "Error: " << e.what() << endl;
        return 1;
    }
    return 0;
}