blocks.cpp

// KKO - block compression/decompression
// Last change: 13.5.2025

#include "blocks.h"

// compress a vector of uint8_t values into a vector of bits
BitBuffer block_compress(struct Params params, const std::vector<uint8_t> &raw_data)
{   
    BitBuffer block_data; // block compressed data

    for(uint64_t block_x = 0; block_x < params.width / BLOCK_SIZE; block_x++)
    {
        for(uint64_t block_y = 0; block_y < params.height / BLOCK_SIZE; block_y++)
        {
            // each block gets an offset for the raw data vector
            uint64_t offset = params.width * BLOCK_SIZE * block_y + BLOCK_SIZE * block_x;

            // horizontal scan
            std::vector<uint8_t> block(BLOCK_SIZE * BLOCK_SIZE);
            for(uint64_t y = 0; y < BLOCK_SIZE; y++)
            {
                for(uint64_t x = 0; x < BLOCK_SIZE; x++)
                {
                    block[y * BLOCK_SIZE + x] = raw_data[offset + params.width * y + x];
                }
            }
            auto b_h_compressed_lzss = compression_pipeline(params, block);

            // vertical scan
            for(uint64_t x = 0; x < BLOCK_SIZE; x++)
            {
                for(uint64_t y = 0; y < BLOCK_SIZE; y++)
                {
                    block[x * BLOCK_SIZE + y] = (raw_data[offset + params.width * y + x]);
                }
            }
            auto b_v_compressed_lzss = compression_pipeline(params, block);

            // find out which scan is the best for the current block (or just use original data)
            uint64_t original_size_bits = BLOCK_SIZE * BLOCK_SIZE * 8;
            uint64_t horizontal_size_bits = b_h_compressed_lzss.size();
            uint64_t vertical_size_bits = b_v_compressed_lzss.size();

            // original data is used, neither horizontal nor vertical scan helped
            if(original_size_bits <= horizontal_size_bits && original_size_bits <= vertical_size_bits)
            {
                // each block starts with gamma encoded data size (size 0 (= 1 gamma encoded) means original data without compression)
                block_data.append(1, 1);
                // original data
                for(uint64_t y = 0; y < BLOCK_SIZE; y++)
                {
                    for(uint64_t x = 0; x < BLOCK_SIZE; x++)
                    {
                        block_data.append(raw_data[offset + params.width * y + x], 8);
                    }
                }
            }
            // horizontal scan had the best results
            else if(horizontal_size_bits <= original_size_bits && horizontal_size_bits <= vertical_size_bits)
            {
                // gamma encoded size
                block_data.append(b_h_compressed_lzss.size()+1, gamma(b_h_compressed_lzss.size()));
                // then a flag indicating whether horizontal or vertical scan was used, 0 means horizontal
                block_data.append(0, 1);

                uint64_t bh_index = 0;
                uint64_t bsize = b_h_compressed_lzss.size();
                while(bh_index + 64 < bsize)
                {
                    block_data.append(b_h_compressed_lzss.read(bh_index, 64), 64);
                    bh_index += 64;
                }
                block_data.append(b_h_compressed_lzss.read(bh_index, bsize - bh_index), bsize - bh_index);
            }
            // vertical scan had the best results
            else
            {
                // gamma encoded size
                block_data.append(b_v_compressed_lzss.size()+1, gamma(b_v_compressed_lzss.size()));
                // then a flag indicating whether horizontal or vertical scan was used, 0 means horizontal
                block_data.append(1, 1);

                uint64_t bv_index = 0;
                uint64_t bsize = b_v_compressed_lzss.size();
                while(bv_index + 64 < bsize)
                {
                    block_data.append(b_v_compressed_lzss.read(bv_index, 64), 64);
                    bv_index += 64;
                }
                block_data.append(b_v_compressed_lzss.read(bv_index, bsize - bv_index), bsize - bv_index);
            }
        }
    }

    return block_data;
}

// decompress a vector of bits into a vector of uint8_t values (each block has its own metadata: block size and scan direction flag)
std::vector<uint8_t> block_decompress(struct Params params, BitBuffer &raw_data)
{
    std::vector<uint8_t> result(params.width * params.height); // decoded data to be returned

    uint64_t bitstream_offset = 0; // offset when indexing raw data (faster the erasing bits from the front)

    for(uint64_t block_x = 0; block_x < params.width / params.blocks; block_x++)
    {
        for(uint64_t block_y = 0; block_y < params.height / params.blocks; block_y++)
        {
            // each block gets its own offset of raw data
            uint64_t offset = params.width * params.blocks * block_y + params.blocks * block_x;

            // get current block size (0 means original uncompressed data)
            uint64_t size = (ungamma_from_bitfield(raw_data, bitstream_offset, false));

            // get number of bits read from the bitfield (to change the offset)
            uint64_t size_copy = size;
            uint64_t bits_used = 0;
            if(size_copy == 0)
                bits_used = 1;
            while(size_copy > 0)
            {
                bits_used++;
                size_copy = size_copy >> 1;
            }
            bits_used = 2 * bits_used - 1;
            bitstream_offset += bits_used;

            // decoded block (still in bits)
            BitBuffer block;

            // block was not compressed
            if(size == 0)
            {
                for(uint64_t y = 0; y < params.blocks; y++)
                {
                    for(uint64_t x = 0; x < params.blocks; x++)
                    {
                        result[offset + params.width * y + x] = raw_data.read(bitstream_offset + params.blocks * y * 8 + x * 8, 8);
                    }
                }
                bitstream_offset += (params.blocks * params.blocks * 8);
            }
            // block was compressed
            else
            {
                // first bit is a flag indicating whether horizontal or vertical scan was used
                bool vertical = raw_data.read(bitstream_offset, 1) ? true : false;

                bitstream_offset += 1;
                // read the block data from raw data
                size_copy = size;
                uint64_t read = 0;
                while(size_copy >= 64)
                {
                    block.append(raw_data.read(bitstream_offset + read, 64), 64);
                    size_copy -= 64;
                    read += 64;
                }
                if(size_copy > 0)
                {
                    block.append(raw_data.read(bitstream_offset + read, size_copy), size_copy);
                    read += size_copy;
                }
                bitstream_offset += size;
                
                // decompress the bits
                std::vector<uint8_t> block_decoded = decompression_pipeline(params, block);
                // save the decompressed values to the right places with horizontal scan
                if(!vertical)
                {
                    for(uint64_t y = 0; y < params.blocks; y++)
                    {
                        for(uint64_t x = 0; x < params.blocks; x++)
                        {
                            result[offset + params.width * y + x] = block_decoded[y * params.blocks + x];
                        }
                    }
                }
                // save the decompressed values to the right places with vertical scan
                else
                {
                    for(uint64_t y = 0; y < params.blocks; y++)
                    {
                        for(uint64_t x = 0; x < params.blocks; x++)
                        {
                            result[offset + params.width * x + y] = block_decoded[y * params.blocks + x];
                        }
                    }
                }
            }
        }
    }

    return result;
}