Generating Hamming codec C++ classes

main.cpp

/*
 * Developer : Naveen Rohilla
 * Objective : Hamming code
 */

#include <iostream>
#include "main.hpp"

using namespace std;

//  calculating no. of parity bits
//  using formula (2 ^ r) >= r + m + 1
int calculateParityBits(int m) {
    m ++;
    int r = 0;
    while (((1 << r) - r) < m) {
        r++;
    }
    return r;
}

//  calculating no. of parity bits in the given hamming code
int calculateParityBits2(int m) {
    int r = 0;
    while ((1 << r) < m) {
        r++;
    }
    return r;
}

//  inserting parity bits in data
void insertParityBits(string & data, const int & r, int & m) {
    for (int i = 0; i < r; i++) {
        data.insert(m + 1 - (1 << i), "p");
        m++;
    }
}


//  generating hamming code
void hamming(string & data, int parity) {
    int m = data.size();

    int r = calculateParityBits(m);
    cout << "Parity bits = " << r << endl;
    insertParityBits(data, r, m);
    cout << "\nData is = " << data << endl;

    //calculating value of parity bits
    for (int i = 0, j, counter, skip, count1; i < r; i++) {
        counter = 1 << i;
        skip = counter;
        count1 = 0;
        for (j = m - skip; j >= 0; j--) {
            if (data[j] == '1') {
                count1++;
            }
            skip--;
            if (skip == 0) {
                skip = counter;
                j = j - skip;
            }
        }

        if (parity) {
            if (count1 & 1) {
                data.replace(m - counter, 1, "0");
            }
            else {
                data.replace(m - counter, 1, "1");
            }
        }
        else {
            if (count1 & 1) {
                data.replace(m - counter, 1, "1");
            }
            else {
                data.replace(m - counter, 1, "0");
            }
        }
    }
}


//  detection and correction of received hamming code
void detection(string & data, int parity) {
    bool flag = true;
    int errorBit = 0;
    int m = data.size();

    int r = calculateParityBits2(m);

    //verifying value of parity bits
    for (int i = 0, j, counter, skip, count1; i < r; i++) {
        counter = 1 << i;
        skip = counter;
        count1 = 0;
        for (j = m - skip; j >= 0; j--) {
            if (data[j] == '1') {
                count1++;
            }
            skip--;
            if (skip == 0) {
                skip = counter;
                j = j - skip;
            }
        }

        if (parity) {
            if (count1 & 1);
            else {
                flag = false;
                errorBit += counter;
            }
        }
        else {
            if (count1 & 1) {
                flag = false;
                errorBit += counter;
            }
            else;
        }
    }

    if (! flag) {
        cout << "Error occurd in the received data, in bit(from right side) " << errorBit << endl;
        if (data[m - errorBit] == '1') {
            data.replace(m - errorBit, 1, "0");
        }
        else {
            data.replace(m - errorBit, 1, "1");
        }
        cout << "Correct code should be = " << data << endl;
    }
    else {
        cout << "Code is correct";
    }

    for (int i = 0; i < r; i++) {
        data.erase(m - (1 << i), 1);
    }
}

int main() {
    string data;
    int parity;
    int option;
    bool flag = true;

    do {
        cout << "\n\n1.Generate Hamming code";
        cout << "\n2.Detection and Correction of Received Hamming code";
        cout << "\n3.Generate and error detection and correction of a hamming code";
        cout << "\n4.Generate Hamming codec C++ class";
        cout << "\n0.Exit";
        cout << "\nEnter option...";
        cin >> option;

        switch (option) {

            case 1: {
                cout << "\nEnter Data :";
                cin >> data;
                cout << "Enter parity  0--even , 1--odd :";
                cin >> parity;
                hamming(data, parity);
                cout << "\nHamming code generated = " << data << endl;
                break;
            }

            case 2: {
                cout << "\nEnter Data :";
                cin >> data;
                cout << "Enter parity  0--even , 1--odd :";
                cin >> parity;
                detection(data, parity);
                cout << "\n original data received = " << data << endl;
                break;
            }

            case 3: {
                cout << "\nEnter Data :";
                cin >> data;
                cout << "Enter parity  0--even , 1--odd :";
                cin >> parity;
                hamming(data, parity);
                cout << "\nHamming code generated = " << data << endl;
                detection(data, parity);
                cout << "\nOriginal data received = " << data << endl;
                break;
            }

            case 4: {
                cout << "\nEnter number of data bits (1~57) :";
                int data_bits;
                cin >> data_bits;
                cout << "Enter parity  0--even , 1--odd :";
                cin >> parity;

                cout << "Enter file name :";
                string file_name;
                cin >> file_name;
                file_name += ".hpp";

                ofstream ofs(file_name, ofstream::out);
                hamming_gen_sec_t gs(data_bits, parity);
                gs.print_code(ofs, "", "");
                ofs.close();
                cout << "\nFile " << file_name << " generated." << endl;
                break;
            }

            case 0: {
                flag = false;
                break;
            }
        }
    } while (flag);

    return 0;
}

main.hpp

/*
 * Generate Hamming codec C++ classes with straight forward calculations. (data width 1 ~ 57)
 * The produced codes match the results Naveen Rohilla method generated. (See main.cpp and:
 * https://gist.github.com/RNaveen99/4d5851e9195a3189418dd4bb56bebd1d)
 *
 * Author: BD1ES
 * Date created: 01 APR 2020
 */

#ifndef __main_hpp
#define __main_hpp

#include <cstdint>
#include <cstdarg>
#include <vector>
#include <iostream>
#include <sstream>
#include <fstream>
#include <thread>
#include <chrono>

// Single error correction generator type.
class hamming_gen_sec_t {
public:

    hamming_gen_sec_t(uint8_t data_bits_in, bool odd_in = false) {
        data_bits = data_bits_in > 57 ? 57 : data_bits_in < 1 ? 1 : data_bits_in;
        odd_parity = odd_in;

        calc_parity_bits();
        calc_interlacing();
        calc_matrix();
    }

    void print_code(std::ostream &os, const char *indent, const char *class_prefix) {
        print_lines(os, indent, gen_class(class_prefix));
    }

    std::vector <std::string> gen_class(const char *class_prefix) {
        std::stringstream ss;

        ss << vsform("\n"
                     "class %shamming%d_%d_t {\n"
                     "public:\n\n"
                     , class_prefix
                     , data_bits+parity_bits
                     , data_bits);

        std::vector <std::string> v = gen_encoder();
        for(size_t i = 0; i < v.size(); i++){
            ss << "    " << v[i] << "\n";
        }

        v = gen_decoder();
        for(size_t i = 0; i < v.size(); i++){
            ss << "    " << v[i] << "\n";
        }

        v = gen_constants();
        for(size_t i = 0; i < v.size()-1; i++){
            ss << "    " << v[i] << "\n";
        }

        ss << "};\n";

        return get_lines(ss);
    }

    // generating encoder
    std::vector <std::string> gen_encoder() {
        std::stringstream ss;

        // header
        ss << vsform("// [%d,%d] Hamming encoder using %s parity matrix.\n"
                     "uint%d_t encode(uint%d_t data_in) {\n"
                     , data_bits+parity_bits
                     , data_bits
                     , sodd(odd_parity)
                     , int_bits(data_bits+parity_bits)
                     , int_bits(data_bits));

        // data serialization
        ss << vsform("    uint%d_t d[%d];\n"
                     , int_bits(data_bits+parity_bits)
                     , data_bits);
        for(uint8_t i = 0; i < data_bits; i++){
            ss << vsform("    d[%s%d] = (data_in>>%s%d)&1;\n"
                         , sfill(data_bits, i), i
                         , sfill(data_bits, i), i);
        }

        // parity bits
        std::vector <std::string> v = gen_parity_bits();
        for(size_t i = 0; i < v.size(); i++){
            ss << "    " << v[i] << "\n";
        }

        // interlacing
        ss << vsform("\n"
                     "    uint%d_t code;\n"
                     "    code = "
                     , int_bits(data_bits+parity_bits));
        for(uint8_t i = 0; i < (data_bits+parity_bits); i++){
            if(i != 0){
                if((i%5) == 0){
                    ss << "\n        ";
                }
                ss << " | ";
            }
            if(i < parity_bits){
                ss << vsform("(p[%d]%s<<%s%d)"
                             , i, sfill(data_bits, i)
                             , sfill(data_bits+parity_bits, interlacing[i]), interlacing[i]);
            }else{
                ss << vsform("(d[%s%d]<<%s%d)"
                             , sfill(data_bits, i-parity_bits), i-parity_bits
                             , sfill(data_bits+parity_bits, interlacing[i]), interlacing[i]);
            }
        }
        ss << ";\n";

        // eof
        ss << "\n"
              "    return code;\n"
              "}\n";

        return get_lines(ss);
    }

    // generating decoder
    std::vector <std::string> gen_decoder() {
        std::stringstream ss;

        // header
        ss << vsform("// [%d,%d] Hamming decoder using %s parity matrix.\n"
                     "uint8_t decode(uint%d_t &data, uint%d_t code_in) {\n"
                     , data_bits+parity_bits
                     , data_bits
                     , sodd(odd_parity)
                     , int_bits(data_bits)
                     , int_bits(data_bits+parity_bits));

        // deinterlacing
        ss << vsform("    uint8_t q[%d];\n"
                     "    uint%d_t d[%d];\n"
                     , parity_bits
                     , int_bits(data_bits)
                     , data_bits);
        for(uint8_t i = 0; i < (data_bits+parity_bits); i++){
            if(i < parity_bits){
                ss << vsform("    q[%d]%s = (code_in>>%s%d)&1;\n"
                             , i, sfill(data_bits, i)
                             , sfill(data_bits+parity_bits, interlacing[i]), interlacing[i]);
            }else{
                ss << vsform("    d[%s%d] = (code_in>>%s%d)&1;\n"
                             , sfill(data_bits, i-parity_bits), i-parity_bits
                             , sfill(data_bits+parity_bits, interlacing[i]), interlacing[i]);
            }
        }

        // parity bits
        std::vector <std::string> v = gen_parity_bits();
        for(size_t i = 0; i < v.size(); i++){
            ss << "    " << v[i] << "\n";
        }

        // syndrome
        ss << "\n"
              "    uint8_t syn;\n"
              "    syn = ";
        for(uint8_t i = 0; i < parity_bits; i++){
            if(i != 0){
                if((i%3) == 0){
                    ss << "\n       ";
                }
                ss << " | ";
            }
            ss << vsform("((p[%d]^q[%d])<<%d)", i, i, i);
        }
        ss << ";\n";

        // data bits correction
        ss << "\n"
              "    switch(syn){\n";
        for(uint8_t i = 0; i < data_bits; i++){
            uint8_t dbit = parity_bits + i;
            uint8_t synd = interlacing[dbit] + 1;
            ss << vsform("    case %s%d:\n"
                         , sfill(interlacing.back()+1, synd), synd);
            ss << vsform("        d[%s%d] ^= 1; break;\n"
                         , sfill(data_bits, i), i);
        }
        ss << "    default:\n"
              "        break;\n"
              "    };\n";

        ss << "\n"
              "    data = ";
        for(uint8_t i = 0; i < data_bits; i++){
            if(i != 0){
                if((i%5) == 0){
                    ss << "\n        ";
                }
                ss << " | ";
            }
            ss << vsform("(d[%s%d]<<%s%d)"
                         , sfill(data_bits, i), i
                         , sfill(data_bits, i), i);
        }
        ss << ";\n";

        // eof
        ss << "\n"
              "    return syn;\n"
              "}\n";

        return get_lines(ss);
    }

    // generating parity bits
    std::vector <std::string> gen_parity_bits() {
        std::stringstream ss;

        ss << vsform("\n"
                     "uint8_t p[%d] = {"
                     , parity_bits);
        for(uint8_t i = 0; i < parity_bits; i++){
            if(i != 0){
                ss << ", ";
            }
            if(odd_parity){
                ss << "1";
            }else{
                ss << "0";
            }
        }
        ss << "};\n";

        for(uint8_t i = 0; i < matrix.size(); i++){
            ss << vsform("p[%d] ^= ", i);
            for(uint8_t j = 0; j < matrix[i].size(); j++){
                if(j != 0){
                    if((j%8) == 0){
                        ss << "\n     ";
                    }
                    ss << " ^ ";
                }
                ss << vsform("d[%s%d]"
                             , sfill(data_bits, matrix[i][j]), matrix[i][j]);
            }
            ss << ";\n";
        }

        return get_lines(ss);
    }

    // generating constants
    std::vector <std::string> gen_constants() {
        std::stringstream ss;

        ss << vsform("inline uint8_t data_bits() {\n"
                     "    return %d;\n"
                     "}\n"
                     , data_bits);

        ss << vsform("\n"
                     "inline uint8_t parity_bits() {\n"
                     "    return %d;\n"
                     "}\n"
                     , parity_bits);

        return get_lines(ss);
    }

protected:
    typedef std::vector <uint8_t> byte_vector_t;

    bool odd_parity;
    uint8_t data_bits, parity_bits;
    byte_vector_t interlacing;
    std::vector <byte_vector_t> matrix;

    void calc_parity_bits() {
        // using formula (2 ^ p) >= p + d + 1
        parity_bits = 0;
        while ((1 << parity_bits) < (data_bits+parity_bits+1)) parity_bits++;
    }

    void calc_interlacing() {
        // looking for parity bits
        for(uint8_t i = 0; i < parity_bits; i++){
            interlacing.push_back((1<<i) - 1);
        }

        // looking for data bits
        for(uint8_t i = 1; i <= (data_bits+parity_bits); i++){
            if(!is_po2(i)){
                interlacing.push_back(i-1);
            }
        }
    }

    void calc_matrix() {
        for(uint8_t i = 0; i < parity_bits; i++){
            byte_vector_t xors;
            xors.clear();
            uint8_t dbit = 0;
            for(uint8_t j = 1; j <= (data_bits+parity_bits); j++){
                if(!is_po2(j)){
                    // if bit number is 2**i
                    if(j & (1<<i)){
                        xors.push_back(dbit);
                    }
                    dbit++;
                }
            }
            matrix.push_back(xors);
        }
    }

    template <class T>
    bool is_po2(T v) {
        return (v > 0) && ((v & (v - 1)) == 0);
    }

    uint8_t int_bits(uint8_t bits) {
        if(bits <= 8){
            return 8;
        }else if(bits <= 16){
            return 16;
        }else if(bits <= 32){
            return 32;
        }else if(bits <= 64){
            return 64;
        }else{
            throw std::runtime_error(vsform("%s: uint%d_t is too long to make.", __func__, bits));
        }
    }

    const char *sfill(uint8_t a, uint8_t b) {
        if((a>=10) && (b<10)){
            return " ";
        }else{
            return "";
        }
    }

    const char *sodd(bool odd) {
        if(odd){
            return "odd";
        }else{
            return "even";
        }
    }

    static std::string vsform(const char* fmt, ...) {
        va_list vl;
        va_start(vl, fmt);
        auto size = vsnprintf(nullptr, 0, fmt, vl) + 1; // The size needs '\0' contained.
        va_end(vl);

        // If thrown, a coding issue may exist.
        if(size > 4096){
            throw std::runtime_error(vsform("%s: %s is too long to make.", __func__, fmt));
        }

        char *buf = new char[size_t(size)];

        va_start(vl, fmt);
        size = vsnprintf(buf, size_t(size), fmt, vl);
        va_end(vl);

        std::string res = std::string(buf, size_t(size));
        delete[] buf;

        return res;
    }

    std::vector <std::string> get_lines(std::stringstream &ss) {
        std::vector <std::string> v;

        while(!ss.eof()){
            std::string line;
            getline(ss, line);
            v.push_back(line);
        }

        return v;
    }

    void print_lines(std::ostream &os, const char *indents, const std::vector <std::string> &v) {
        for(size_t i = 0; i < v.size(); i++){
            os << indents << v[i] << "\n";
        }
    }
};

#endif