Tag: data-compression

// 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