Rice-Golomb Encoder and Decoder Copyright (c) Thursday, April 3, 2025, to Sunday, April 6, 2025, by James Pate Williams, Jr. BA, BS, Master of Software Engineering, Doctor of Philosophy Computer Science

// Rice-Golomb Encoder and Decoder
// Copyright (c) Thursday, April 3, 2025
// by James Pate Williams, Jr.
// BA, BS, Master of Software Engineering
// Doctor of Philosophy Computer Science
// Online references:
// https://en.wikipedia.org/wiki/Golomb_coding
// https://ntrs.nasa.gov/api/citations/19790014634/downloads/19790014634.pdf

#include <iostream>
#include <string>
#include <vector>
//#include <stdlib.h>

bool Encode(const char* NChars, size_t NCharsCount,
    long M, long long& N, std::vector<char>& qBits,
    std::vector<char>& rBits, unsigned int& qSize, unsigned int& rSize,
    long long& q, long long& r, unsigned int& NSize) {
    N = NChars[0] - (long long)'0';
    for (unsigned int i = 1; i < NCharsCount; i++) {
        N = 10 * N + (long long)NChars[i] - (long long)'0';
    }
    q = N / M;
    r = N % M;
    qSize = 0;
    while (qSize < q) {
        qBits.push_back('1');
        qSize++;
    }
    qBits.push_back('0');
    qSize++;
    rSize = 0;
    unsigned int b = (unsigned int)floor(log2(M));
    if (b > 62) {
        return false;
    }
    long long p = (long long)pow(2, b + 1);
    if (r < p - M) {
        long long rr = r;
        while (rr > 0) {
            long long digit = (rr & 1) == 1 ? 1 : 0;
            rBits.push_back((char)digit + '0');
            rSize++;
            rr >>= 1;
        }
        rBits.push_back('0');
        rSize++;
    }
    else {
        long long rr = r + p - M;
        while (rSize < b + 1) {
            long long digit = rr & 1 ? 1 : 0;
            rBits.push_back((char)digit + '0');
            rSize++;
            rr >>= 1;
        }
    }
    long long rValue = rBits[0];
    for (size_t i = 1; i < rSize; i++) {
        rValue = rValue * 2 + rBits[i];
    }
    long long NBitCount = 0;
    while (N > 0) {
        N >>= 1;
        NBitCount++;
    }
    std::cout << "q-bits size = " << qSize << std::endl;
    std::cout << "r-bits size = " << rSize << std::endl;
    std::cout << "N-bits size = " << qSize + rSize << std::endl;
    std::cout << "N-Chars * 8-Bits per Char = " << NCharsCount * 8 << std::endl;
    std::cout << "% Compression = " << 100.0 * (1.0 - (qSize + rSize) /
        (NCharsCount * 8.0)) << std::endl;
    return true;
}

void Decode(long long M, long long& N,
    std::vector<char> qBits, std::vector<char> rBits,
    unsigned int& qSize, unsigned int& rSize,
    long long& q, long long& r) {
    int count = 0;
    while (qBits[count] != '0') {
        count++;
    }
    q = count;
    int c = (int)rSize - 1;
    unsigned int b = (unsigned int)floor(log2(M));
    long long p = (long long)pow(2, b + 1);
    long long s = 0;
    r = rBits[c--] - (long long)'0';
    do {
        r = 2 * r + rBits[c] - (long long)'0';
        c--;
    } while (c >= 0);
    if (r < p - M) {
        s = r;
    }
    else {
        s = r + p - M;
        c = 1;
        r = rBits[0] - (long long)'0';
        while (c < (int)(b + 1)) {
            r = 2 * r + rBits[c] - (long long)'0';
            c++;
        }
        s = r;
    }
    r = s;
    N = q * M + r;
}

int main() {
    char line[128] = { };
    size_t NSize = 0, qSize = 0, rSize = 0;
    long long M = 10, N = 42, q = -1, r = -1;
    std::vector<char> qBits, rBits;
    std::cout << "M = ";
    std::cin.getline(line, 127);
    std::string str1(line);
    M = std::stoi(str1);
    std::cout << "N = ";
    std::cin.getline(line, 127);
    std::string str2(line);
    Encode(str2.c_str(), strlen(str2.c_str()), M, N,
        qBits, rBits, qSize, rSize, q, r, NSize);
    std::cout << "q = " << q << std::endl;
    std::cout << "r = " << r << std::endl;
    std::cout << "q-size = " << qSize << std::endl;
    std::cout << "r-size = " << rSize << std::endl;
    std::cout << "q ";
    for (unsigned int i = 0; i < qSize; i++) {
        std::cout << qBits[i] << ' ';
    }
    std::cout << std::endl;
    std::cout << "r ";
    for (int i = (int)rSize - 1; i >= 0; i--) {
        std::cout << rBits[i] << ' ';
    }
    std::cout << std::endl;
    Decode(M, N, qBits, rBits, qSize, rSize, q, r);
    std::cout << "q = " << q << std::endl;
    std::cout << "r = " << r << std::endl;
    std::cout << "q-size = " << qSize << std::endl;
    std::cout << "r-size = " << rSize << std::endl;
    std::cout << "q ";
    for (unsigned int i = 0; i < qSize; i++) {
        std::cout << qBits[i] << ' ';
    }
    std::cout << std::endl;
    std::cout << "r ";
    for (int i = rSize - 1; i >= 0; i--) {
        std::cout << rBits[i] << ' ';
    }
    std::cout << std::endl;
    std::cout << "N = " << N << std::endl;
    return 0;
}

M = 64
N = 1027
q-bits size = 17
r-bits size = 3
N-bits size = 20
N-Chars * 8-Bits per Char = 32
% Compression = 37.5
q = 16
r = 3
q-size = 17
r-size = 3
q 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
r 0 1 1
q = 16
r = 3
q-size = 17
r-size = 3
q 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
r 0 1 1
N = 1027