utils.cpp

// KKO - utils
// Last change: 13.5.2025

#include "utils.h"
#include "rle.h"
#include "lzss.h"


// append N bits to the buffer
void BitBuffer::append(uint64_t value, uint64_t bit_count)
{
    // max 64 bits can be read at the same time
    if(bit_count > 64)
    {
        std::cerr << "bitbuffer: wrong append" << std::endl;
        exit(1);
    }

    total_bits += bit_count;
    uint64_t remaining = bit_count;

    while(remaining > 0)
    {
        // start a new byte if there is none or the last one is full
        if(data.empty() || (total_bits - remaining + start_offset) % 8 == 0)
            data.push_back(0);

        uint64_t current_index = data.size() - 1;
        uint64_t used_bits = (total_bits - remaining + start_offset) % 8;
        uint64_t free_bits = 8 - used_bits;
        uint64_t bits_to_write = std::min(free_bits, remaining);

        uint8_t bits = (value >> (remaining - bits_to_write)) & ((1 << bits_to_write) - 1);
        bits = bits << (8 - used_bits - bits_to_write);

        data[current_index] |= bits;
        remaining -= bits_to_write;
    }
}

// remove N bits from the start of the buffer
void BitBuffer::remove(uint64_t bit_count)
{
    total_bits -= bit_count;
    start_offset += bit_count;

    // at least 8 bits skipped, the whole byte can be removed
    while(start_offset > 7 && !data.empty())
    {
        data.pop_front();
        start_offset -= 8;
    }
}

// read N bits from index
uint64_t BitBuffer::read(uint64_t index, uint64_t bit_count) const
{
    // max 64 bits can be read at the same time
    if(bit_count > 64)
    {
        std::cerr << "bitbuffer: wrong read" << std::endl;
        exit(1);
    }

    uint64_t result = 0;
    uint64_t offset = (start_offset + index) / 8; // targeted byte offset
    uint64_t used_bits = (start_offset + index) % 8; // number of used bits in targeted byte

    uint64_t read = 0; // number of already read bits
    while(read < bit_count)
    {
        uint8_t byte = data[offset];
        uint64_t remaining_bits = 8 - used_bits;
        uint64_t unread = std::min(bit_count - read, remaining_bits);
        uint8_t bits = (byte >> (8 - used_bits - unread)) & ((1 << unread) - 1);
        result = (result << unread) | bits;

        read += unread;
        used_bits = 0;
        offset++;
    }

    return result;
}

// convert bitbuffer to vector of uint8_t
std::vector<uint8_t> BitBuffer::to_byte_vector() const
{
    std::vector<uint8_t> res(data.begin(), data.end());
    return res;
}

// convert vector of uint8_t to bitbuffer
void BitBuffer::load_from_byte_vector(const std::vector<uint8_t> &input)
{
    data.insert(data.end(), input.begin(), input.end());
    total_bits += 8 * input.size();
}

// returns total_bits
uint64_t BitBuffer::size() const
{
    return total_bits;
}

// adjust padding bits in the last byte
void BitBuffer::adjust_padding(uint16_t padding_bits)
{
    total_bits -= padding_bits;
}

// get length of number converted into elias gamma encoding
std::uint64_t gamma(uint64_t number)
{
    // elias gamma encoding is shifted by one, because of zero representation
    number++;

    uint64_t length = 0;
    while(number > 0)
    {
        length++;
        number = number >> 1;
    }

    // prepend len-1 zeroes
    length = (2 * length) - 1;
    return length;
}

// given a sequence of bits, return the first elias gamma decoded integer from the start (also remove the used bits, exception is if erase = false)
uint64_t ungamma_from_bitfield(BitBuffer &bits, uint64_t offset, bool erase)
{
    int64_t zeroes = 0; // leading zero count
    uint64_t index = 0; // current index in bitfield

    // count leading zeroes
    while(bits.read(offset + index, 1) == 0)
    {
        zeroes++;
        index++;
    }

    // get the gamma encoded binary without leading zeroes
    uint64_t value = 0;
    while(zeroes >= 0)
    {
        value = value << 1;
        value = value | (bits.read(offset + index, 1));
        index++;
        zeroes--;
    }

    value--; // decrease by one since gamma encoding is shifted

    if(erase)
    {
        // remove first n bits from the data, since it was read already
        bits.remove(index);
    }

    return value;
}

// delta encode a vector of unsigned 8bit integers (store differences between values, not the values themselves)
std::vector<uint8_t> delta_encode(const std::vector<uint8_t> &input)
{
    std::vector<uint8_t> result;
    // first value stays the same
    result.push_back(input[0]);

    for(uint64_t i = 1; i < input.size(); i++)
    {
        // difference between current and previous vale (as 32bit int)
        uint16_t diff = static_cast<int>(input[i]) - static_cast<int>(input[i - 1]);
        // calculate difference on 8bits
        result.push_back(static_cast<uint8_t>((diff + 256) % 256));
    }

    return result;
}

// delta decode a vector of unsigned 8bit integers
std::vector<uint8_t> delta_decode(const std::vector<uint8_t> &input)
{
    std::vector<uint8_t> result;
    // first value stays the same
    result.push_back(input[0]);

    for(uint64_t i = 1; i < input.size(); i++)
    {
        // current value is calculated as stored difference + previous value (as 32bit int)
        uint16_t curr = static_cast<int>(result[i - 1]) + static_cast<int>(input[i]);
        // calculate value on 8bits
        result.push_back(static_cast<uint8_t>(curr % 256));
    }

    return result;
}


// given a vector of uint8_t values, compress them into bits (delta encode -> rle -> lzss)
BitBuffer compression_pipeline(struct Params params, std::vector<uint8_t> &input)
{
    // delta encoding
    if(params.model)
        input = delta_encode(input);

    // compress
    auto [rle_used, compressed_rle] = rle_encode(input);
    BitBuffer compressed_lzss = lzss_encode(rle_used ? compressed_rle : input, rle_used);

    return compressed_lzss;
}

// given a vector of bits, decompress them into uint8_t values (lzss -> rle -> delta decode)
std::vector<uint8_t> decompression_pipeline(struct Params params, const BitBuffer &input)
{
    // decompress
    auto decompressed_lzss = lzss_decode(input);
    auto decompressed_rle = rle_decode(decompressed_lzss);

    // delta encoding
    if(params.model)
        decompressed_rle = delta_decode(decompressed_rle);

    return decompressed_rle;
}