rle.cpp

// KKO - RLE compressor/decompressor
// Last change: 13.5.2025

#include "rle.h"

// RLE encode a vector of 8bit values, returns a bool (indicating whether RLE was actually used) and the resulting vector
std::pair<bool, std::vector<uint8_t>> rle_encode(const std::vector<uint8_t> &text, uint16_t min_repeat)
{
    std::vector<uint8_t> result; // result to be returned
    uint64_t length = text.size(); // length of the input text
    
    uint64_t i = 0; // input text index
    std::vector<uint8_t> buffer; // buffer storing currect sequence of same chars
    uint64_t buffer_limit = 255; // max buffer size

    // go through the whole text
    while(i < length)
    {
        // no character in buffer OR repeating character found
        if(buffer.empty() || text[i] == buffer.back())
        {
            // buffer is full
            if(buffer.size() == buffer_limit)
            {
                result.push_back(1);
                result.push_back(buffer.size());
                result.push_back(buffer.back());
                buffer.clear();
            }
            buffer.push_back(text[i]);
            i++;
        } 
        // different character found
        else
        {
            // there is enough repeating characters in buffer => rle can be used
            if(buffer.size() >= min_repeat)
            {
                result.push_back(1);
                result.push_back(buffer.size());
                result.push_back(buffer.back());
                buffer.clear();
            }
            // not enough repeating chars, saving as normal 
            else
            {
                for(uint64_t j = 0; j < buffer.size(); j++)
                {
                    result.push_back(0);
                    result.push_back(buffer[j]);
                }
                buffer.clear();
            }
        }
    }

    // finish whatever remained in buffer
    if(!buffer.empty())
    {
        if(buffer.size() >= min_repeat)
        {
            result.push_back(1);
            result.push_back(buffer.size());
            result.push_back(buffer.back());
        } 
        else
        {
            for(uint64_t j = 0; j < buffer.size(); j++)
            {
                result.push_back(0);
                result.push_back(buffer[j]);
            }
        }
    }

    // calculate the total length of encoded text (in bits) to determine if rle is worth it
    uint64_t totalLength = 0;
    i = 0;
    while(i < result.size())
    {
        if(result[i] == 1)
        {
            // 1 bit indicationg rle usage, 8 bits for the number of repetitions, 8 bits for the repeated value
            totalLength += 17;  
            i += 3;
        } 
        else if(result[i] == 0)
        {
            // 1 bit indicationg (not) rle usage, 8 bits for the value
            totalLength += 9;
            i += 2;
        } 
        else 
        {
            std::cerr << "rle_compress: invalid result value - rle will no be used" << std::endl;
            return {false, text};
        }
    }

    // check if rle is worth it
    if(totalLength < text.size() * 8)
    {
        return {true, result};
    }

    // rle is not used
    return {false, text};
}

// RLE decode a vector of 16bit values (only 9 bits are actually used though, first bit is rle flag, 8 bits are actual values), returns a vector of 8bit values
std::vector<uint8_t> rle_decode(const std::vector<uint16_t> &text)
{
    std::vector<uint8_t> result; // final vector of 8bit values

    // decode 9bit values
    uint64_t i = 0;
    while(i < text.size())
    {
        // rle used
        if(text[i] > 255)
        {
            uint16_t repeat = text[i] - 256; // skip first bit, next eight bits - number of repetitions
            uint16_t item = text[i + 1]; // next eight bits - repeated value
            for(uint16_t j = 0; j < repeat; j++)
            {
                result.push_back(item);
            }
            i += 2;
        } 
        // rle was not used
        else
        {
            result.push_back(text[i]); // 8bit char value
            i++;
        } 
    }

    return result;
}