Bitmap Font encoding prototype 2

#include <boost/algorithm/string/classification.hpp>
#include <boost/algorithm/string/split.hpp>

#include <array>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>


struct glyph
{
    uint8_t code;
    std::array<uint16_t, 16> rows;
};

struct font
{
    std::string header;
    std::vector<glyph> glyphs;

    void sort()
    {
        std::sort(glyphs.begin(), glyphs.end()
            , [](glyph const& l, glyph const& r) -> bool {
                return l.code < r.code;
            });

    }
};

font load_font_txt(std::string const& file_name)
{
    font f;

    std::ifstream input(file_name);
    getline(input, f.header);
    for (std::string line; getline(input, line);) {
        std::vector<std::string> parts;
        boost::split(parts, line, boost::is_any_of("|"));
        std::vector<std::string> rows;
        boost::split(rows, parts[1], boost::is_any_of(" "));

        glyph g;
        g.code = static_cast<uint8_t>(std::stoul(parts[0]));
        for (uint32_t i(0); i < 16; ++i) {
            g.rows[i] = static_cast<uint16_t>(std::stoul(rows[i], nullptr, 16));
        }

        f.glyphs.push_back(g);
    }

    return f;
}

void encode_v0(font const& f, std::vector<uint8_t>& buffer)
{
    std::copy(f.header.begin(), f.header.end(), std::back_inserter(buffer));
    buffer.push_back('\r');
    buffer.push_back('\n');
    for (glyph const& g : f.glyphs) {
        std::ostringstream s;
        s << int(g.code) << "|";
        for (uint32_t i(0); i < 16; ++i) {
            s << (i ? " " : "") << std::uppercase
                << std::setfill('0') << std::setw(3) << std::hex
                << g.rows[i];
        }
        s << "\r\n";
        std::string temp(s.str());
        std::copy(temp.begin(), temp.end(), std::back_inserter(buffer));
    }
}

void encode_header(font const& f, std::vector<uint8_t>& buffer)
{
    // Store header directly
    std::copy(f.header.begin(), f.header.end(), std::back_inserter(buffer));
    // and terminate with null
    buffer.push_back(0);
}


struct simple_bitstream
{
    simple_bitstream(std::vector<uint8_t>& buffer)
        : buf_(buffer)
        , temp_(0)
        , temp_size_(0)
    {
    }

    void write_bits(uint32_t v, uint8_t bits)
    {
        if (bits) {
            write_bits(v >> 1, bits - 1);
            write_bit(v & 1);
        }
    }

    void write_bit(uint8_t v)
    {
        temp_ = (temp_ << 1) | (v & 1);
        ++temp_size_;
        if (temp_size_ == 8) {
            buf_.push_back(temp_);
            temp_size_ = 0;
            temp_ = 0;
        }
    }

    void flush()
    {
        for (; temp_size_;) {
            write_bit(0);
        }
    }

    std::vector<uint8_t>& buf_;
    uint8_t temp_;
    uint8_t temp_size_;
};

void encode_v1(font const& f, std::vector<uint8_t>& buffer)
{
    encode_header(f, buffer);
    simple_bitstream b(buffer);
    for (glyph const& g : f.glyphs) {
        // Code using 1 byte
        b.write_bits(g.code, 8);
        for (uint32_t i(0); i < 16; ++i) {
            // Pixel using 2 bytes, most significant bits first, prefixed by 4 bit padding
            b.write_bits(g.rows[i], 16);
        }
    }
}

void encode_v2(font const& f, std::vector<uint8_t>& buffer)
{
    encode_header(f, buffer);
    simple_bitstream b(buffer);
    for (glyph const& g : f.glyphs) {
        // Code using 1 byte
        b.write_bits(g.code, 8);
        for (uint32_t i(0); i < 16; i += 2) {
            // 2 pixels using 3 bytes, most significant bits first
            b.write_bits(g.rows[i], 12);
            b.write_bits(g.rows[i + 1], 12);
        }
    }
}

void encode_v3(font const& f, std::vector<uint8_t>& buffer)
{
    encode_header(f, buffer);
    simple_bitstream b(buffer);
    for (glyph const& g : f.glyphs) {
        // Code using 1 byte
        b.write_bits(g.code, 8);

        for (uint32_t i(0); i < 16; ++i) {
            uint16_t row(g.rows[i]);
            if (row == 0) {
                // An empty row
                b.write_bit(1);
            } else {
                // Verbatim row
                b.write_bit(0);
                b.write_bits(row, 12);
            }
        }
    }
}

// Find nearest identical preceding row in this glyph
uint8_t find_nearest_copy(glyph const& g, uint32_t i)
{
    uint8_t offset(0);
    uint16_t row(g.rows[i]);
    for (uint8_t j(1); j < i; ++j) {
        if (row == g.rows[i - j]) {
            offset = j;
            break;
        }
    }
    return offset;
}

void encode_v4(font const& f, std::vector<uint8_t>& buffer)
{
    uint32_t OP_VERBATIM(0), OP_COPY(1);

    encode_header(f, buffer);
    simple_bitstream b(buffer);
    for (glyph const& g : f.glyphs) {
        // Code using 1 byte
        b.write_bits(g.code, 8);

        for (uint32_t i(0); i < 16; ++i) {
            uint16_t row(g.rows[i]);
            if (row == 0) {
                // Empty row, copy with offset 0
                b.write_bit(OP_COPY);
                b.write_bits(0, 4);
                continue;
            }

            // Find nearest identical preceding row in this glyph
            uint8_t offset(find_nearest_copy(g, i));
            if (offset) {
                // Copy with non-zero offset
                b.write_bit(OP_COPY);
                b.write_bits(offset, 4);
            } else {
                // Verbatim row
                b.write_bit(OP_VERBATIM);
                b.write_bits(row, 12);
            }
        }
    }
}

void encode_v5(font const& f, std::vector<uint8_t>& buffer)
{
    uint32_t OP_VERBATIM(0), OP_COPY(1), OP_EMPTY(2);

    encode_header(f, buffer);
    simple_bitstream b(buffer);
    for (glyph const& g : f.glyphs) {
        // Code using 1 byte
        b.write_bits(g.code, 8);

        for (uint32_t i(0); i < 16; ++i) {
            uint16_t row(g.rows[i]);
            if (row == 0) {
                // Empty row
                b.write_bits(OP_EMPTY, 2);
                continue;
            }

            // Find nearest identical preceding row in this glyph
            uint8_t offset(find_nearest_copy(g, i));
            if (offset) {
                // Copy with non-zero offset
                b.write_bits(OP_COPY, 2);
                b.write_bits(offset, 4);
            } else {
                // Verbatim row
                b.write_bits(OP_VERBATIM, 2);
                b.write_bits(row, 12);
            }
        }
    }
}

uint32_t find_end_row(glyph const& g)
{
    uint32_t end_row(16);
    for (uint32_t i(0); i < 16; ++i) {
        if (g.rows[15 - i] > 0) {
            break;
        }
        --end_row;
    }
    return end_row;
}


void encode_v6(font const& f, std::vector<uint8_t>& buffer)
{
    uint32_t OP_VERBATIM(0), OP_COPY(1), OP_EMPTY(2), OP_END(3);

    encode_header(f, buffer);
    simple_bitstream b(buffer);
    for (glyph const& g : f.glyphs) {
        // Code using 1 byte
        b.write_bits(g.code, 8);

        uint32_t end_row(find_end_row(g));
        for (uint32_t i(0); i < end_row; ++i) {
            uint16_t row(g.rows[i]);
            if (row == 0) {
                // Empty row
                b.write_bits(OP_EMPTY, 2);
                continue;
            }

            // Find nearest identical preceding row in this glyph
            uint8_t offset(find_nearest_copy(g, i));
            if (offset) {
                // Copy with non-zero offset
                b.write_bits(OP_COPY, 2);
                b.write_bits(offset - 1, 4);
            } else {
                // Verbatim row
                b.write_bits(OP_VERBATIM, 2);
                b.write_bits(row, 12);
            }
        }
        if (end_row < 16) {
            // End the glyph (any remaining rows are empty)
            b.write_bits(OP_END, 2);
        }
    }
}

void find_max_glyph_size(font const& f, uint32_t& max_end_row, uint32_t& column_count)
{
    uint16_t column_mask(0);
    max_end_row = 0;
    for (glyph const& g : f.glyphs) {
        max_end_row = std::max(max_end_row, find_end_row(g));

        for (uint32_t i(0); i < 16; ++i) {
            column_mask |= g.rows[i];
        }
    }

    column_count = 12;
    for (; column_count > 0; --column_count) {
        if (column_mask >> (column_count - 1)) {
            break;
        }
    }
}


void encode_v7(font const& f, std::vector<uint8_t>& buffer)
{
    uint32_t OP_VERBATIM(0), OP_COPY(1), OP_EMPTY(2), OP_END(3);

    encode_header(f, buffer);

    uint32_t max_end_row, column_count;
    find_max_glyph_size(f, max_end_row, column_count);

    simple_bitstream b(buffer);

    b.write_bits(column_count - 1, 4);
    b.write_bits(max_end_row - 1, 4);

    for (glyph const& g : f.glyphs) {
        // Code using 1 byte
        b.write_bits(g.code, 8);

        uint32_t end_row(find_end_row(g));
        for (uint32_t i(0); i < end_row; ++i) {
            uint16_t row(g.rows[i]);
            if (row == 0) {
                // Empty row
                b.write_bits(OP_EMPTY, 2);
                continue;
            }

            // Find nearest identical preceding row in this glyph
            uint8_t offset(find_nearest_copy(g, i));
            if (offset) {
                // Copy with non-zero offset
                b.write_bits(OP_COPY, 2);
                b.write_bits(offset - 1, 4);
            } else {
                // Verbatim row
                b.write_bits(OP_VERBATIM, 2);
                b.write_bits(row, column_count);
            }
        }
        if (end_row < max_end_row) {
            // End the glyph (any remaining rows are empty)
            b.write_bits(OP_END, 2);
        }
    }
}

#include "arithmetic_codec.h"

void encode_v8(font const& f, std::vector<uint8_t>& buffer)
{
    uint32_t OP_VERBATIM(0), OP_COPY(1), OP_EMPTY(2), OP_END(3);

    uint32_t max_end_row, column_count;
    find_max_glyph_size(f, max_end_row, column_count);

    Arithmetic_Codec codec(1 << 18);
    Adaptive_Bit_Model pixel_model;
    Adaptive_Data_Model opcode_model(4);
    Adaptive_Data_Model offset_model(15);
    Static_Data_Model ascii_model;
    ascii_model.set_distribution(256);
    Static_Data_Model column_model;
    column_model.set_distribution(12);
    Static_Data_Model row_model;
    row_model.set_distribution(16);

    codec.start_encoder();

    for (uint8_t c : f.header) {
        codec.encode(c, ascii_model);
    }
    codec.encode(0, ascii_model);

    codec.encode(column_count - 1, column_model);
    codec.encode(max_end_row - 1, row_model);

    for (glyph const& g : f.glyphs) {
        // Code using 1 byte
        codec.encode(g.code, ascii_model);

        uint32_t end_row(find_end_row(g));
        for (uint32_t i(0); i < end_row; ++i) {
            uint16_t row(g.rows[i]);
            if (row == 0) {
                // Empty row
                codec.encode(OP_EMPTY, opcode_model);
                continue;
            }

            // Find nearest identical preceding row in this glyph
            uint8_t offset(find_nearest_copy(g, i));
            if (offset) {
                // Copy with non-zero offset
                codec.encode(OP_COPY, opcode_model);
                codec.encode(offset - 1, offset_model);
            } else {
                // Verbatim row
                codec.encode(OP_VERBATIM, opcode_model);
                for (uint32_t c(column_count); c > 0; --c) {
                    codec.encode((row >> (c - 1)) & 1, pixel_model);
                }
            }
        }
        if (end_row < max_end_row) {
            // End the glyph (any remaining rows are empty)
            codec.encode(OP_END, opcode_model);
        }
    }

    uint32_t payload_size(codec.stop_encoder());
    uint8_t* payload_buffer(codec.buffer());

    buffer.resize(payload_size);
    std::copy(payload_buffer, payload_buffer + payload_size, buffer.begin());
}

void encode_v9(font const& f, std::vector<uint8_t>& buffer)
{
    uint32_t OP_VERBATIM(0), OP_COPY(1), OP_EMPTY(2), OP_END(3);

    uint32_t max_end_row, column_count;
    find_max_glyph_size(f, max_end_row, column_count);

    Arithmetic_Codec codec(1 << 18);
    Adaptive_Bit_Model pixel_model[2];
    Adaptive_Data_Model opcode_model(4);
    Adaptive_Data_Model offset_model(15);
    Static_Data_Model ascii_model;
    ascii_model.set_distribution(256);
    Static_Data_Model column_model;
    column_model.set_distribution(12);
    Static_Data_Model row_model;
    row_model.set_distribution(16);

    codec.start_encoder();

    for (uint8_t c : f.header) {
        codec.encode(c, ascii_model);
    }
    codec.encode(0, ascii_model);

    codec.encode(column_count - 1, column_model);
    codec.encode(max_end_row - 1, row_model);

    for (glyph const& g : f.glyphs) {
        // Code using 1 byte
        codec.encode(g.code, ascii_model);

        uint32_t end_row(find_end_row(g));
        for (uint32_t i(0); i < end_row; ++i) {
            uint16_t row(g.rows[i]);
            if (row == 0) {
                // Empty row
                codec.encode(OP_EMPTY, opcode_model);
                continue;
            }

            // Find nearest identical preceding row in this glyph
            uint8_t offset(find_nearest_copy(g, i));
            if (offset) {
                // Copy with non-zero offset
                codec.encode(OP_COPY, opcode_model);
                codec.encode(offset - 1, offset_model);
            } else {
                // Verbatim row
                codec.encode(OP_VERBATIM, opcode_model);
                uint8_t prev_pixel(0);
                for (uint32_t c(column_count); c > 0; --c) {
                    uint8_t pixel((row >> (c - 1)) & 1);
                    codec.encode(pixel, pixel_model[prev_pixel]);
                    prev_pixel = pixel;
                }
            }
        }
        if (end_row < max_end_row) {
            // End the glyph (any remaining rows are empty)
            codec.encode(OP_END, opcode_model);
        }
    }

    uint32_t payload_size(codec.stop_encoder());
    uint8_t* payload_buffer(codec.buffer());

    buffer.resize(payload_size);
    std::copy(payload_buffer, payload_buffer + payload_size, buffer.begin());
}


void encode_v10(font const& f, std::vector<uint8_t>& buffer)
{
    uint32_t OP_VERBATIM(0), OP_COPY(1), OP_EMPTY(2), OP_END(3);

    uint32_t max_end_row, column_count;
    find_max_glyph_size(f, max_end_row, column_count);

    Arithmetic_Codec codec(1 << 18);
    Adaptive_Bit_Model pixel_model[2];
    Adaptive_Data_Model opcode_model[3];
    for (uint32_t i(0); i < 3; ++i) {
        opcode_model[i].set_alphabet(4);
    }
    Adaptive_Data_Model offset_model(15);
    Static_Data_Model ascii_model;
    ascii_model.set_distribution(256);
    Static_Data_Model column_model;
    column_model.set_distribution(12);
    Static_Data_Model row_model;
    row_model.set_distribution(16);

    codec.start_encoder();

    for (uint8_t c : f.header) {
        codec.encode(c, ascii_model);
    }
    codec.encode(0, ascii_model);

    codec.encode(column_count - 1, column_model);
    codec.encode(max_end_row - 1, row_model);

    for (glyph const& g : f.glyphs) {
        // Code using 1 byte
        codec.encode(g.code, ascii_model);

        uint32_t end_row(find_end_row(g));
        uint8_t prev_opcode(OP_VERBATIM), curr_opcode;
        for (uint32_t i(0); i < end_row; ++i) {
            uint16_t row(g.rows[i]);
            if (row == 0) {
                // Empty row
                curr_opcode = OP_EMPTY;
                codec.encode(curr_opcode, opcode_model[prev_opcode]);
            } else {
                // Find nearest identical preceding row in this glyph
                uint8_t offset(find_nearest_copy(g, i));
                if (offset) {
                    // Copy with non-zero offset
                    curr_opcode = OP_COPY;
                    codec.encode(curr_opcode, opcode_model[prev_opcode]);
                    codec.encode(offset - 1, offset_model);
                } else {
                    // Verbatim row
                    curr_opcode = OP_COPY;
                    codec.encode(curr_opcode, opcode_model[prev_opcode]);
                    uint8_t prev_pixel(0);
                    for (uint32_t c(column_count); c > 0; --c) {
                        uint8_t pixel((row >> (c - 1)) & 1);
                        codec.encode(pixel, pixel_model[prev_pixel]);
                        prev_pixel = pixel;
                    }
                }
            }
            prev_opcode = curr_opcode;
        }
        if (end_row < max_end_row) {
            // End the glyph (any remaining rows are empty)
            codec.encode(OP_END, opcode_model[prev_opcode]);
        }
    }

    uint32_t payload_size(codec.stop_encoder());
    uint8_t* payload_buffer(codec.buffer());

    buffer.resize(payload_size);
    std::copy(payload_buffer, payload_buffer + payload_size, buffer.begin());
}


void encode_v11(font const& f, std::vector<uint8_t>& buffer)
{
    uint32_t OP_VERBATIM(0), OP_COPY(1), OP_EMPTY(2), OP_END(3);

    uint32_t max_end_row, column_count;
    find_max_glyph_size(f, max_end_row, column_count);

    Arithmetic_Codec codec(1 << 18);
    Adaptive_Bit_Model presence_model;
    Adaptive_Bit_Model pixel_model[2];
    Adaptive_Data_Model opcode_model[3];
    for (uint32_t i(0); i < 3; ++i) {
        opcode_model[i].set_alphabet(4);
    }
    Adaptive_Data_Model offset_model(15);
    Static_Data_Model ascii_model;
    ascii_model.set_distribution(256);
    Static_Data_Model column_model;
    column_model.set_distribution(12);
    Static_Data_Model row_model;
    row_model.set_distribution(16);

    codec.start_encoder();

    for (uint8_t c : f.header) {
        codec.encode(c, ascii_model);
    }
    codec.encode(0, ascii_model);

    uint8_t first_code(f.glyphs.front().code);
    uint8_t last_code(f.glyphs.back().code);

    codec.encode(first_code, ascii_model);
    codec.encode(last_code, ascii_model);

    std::vector<bool> glyph_available(256);
    for (glyph const& g : f.glyphs) {
        glyph_available[g.code] = true;
    }
    for (uint32_t i(first_code); i <= last_code; ++i) {
        if (glyph_available[i]) {
            codec.encode(1, presence_model);
        } else {
            codec.encode(0, presence_model);
        }
    }

    codec.encode(column_count - 1, column_model);
    codec.encode(max_end_row - 1, row_model);

    for (glyph const& g : f.glyphs) {
        uint32_t end_row(find_end_row(g));
        uint8_t prev_opcode(OP_VERBATIM), curr_opcode;
        for (uint32_t i(0); i < end_row; ++i) {
            uint16_t row(g.rows[i]);
            if (row == 0) {
                // Empty row
                curr_opcode = OP_EMPTY;
                codec.encode(curr_opcode, opcode_model[prev_opcode]);
            } else {
                // Find nearest identical preceding row in this glyph
                uint8_t offset(find_nearest_copy(g, i));
                if (offset) {
                    // Copy with non-zero offset
                    curr_opcode = OP_COPY;
                    codec.encode(curr_opcode, opcode_model[prev_opcode]);
                    codec.encode(offset - 1, offset_model);
                } else {
                    // Verbatim row
                    curr_opcode = OP_COPY;
                    codec.encode(curr_opcode, opcode_model[prev_opcode]);
                    uint8_t prev_pixel(0);
                    for (uint32_t c(column_count); c > 0; --c) {
                        uint8_t pixel((row >> (c - 1)) & 1);
                        codec.encode(pixel, pixel_model[prev_pixel]);
                        prev_pixel = pixel;
                    }
                }
            }
            prev_opcode = curr_opcode;
        }
        if (end_row < max_end_row) {
            // End the glyph (any remaining rows are empty)
            codec.encode(OP_END, opcode_model[prev_opcode]);
        }
    }

    uint32_t payload_size(codec.stop_encoder());
    uint8_t* payload_buffer(codec.buffer());

    buffer.resize(payload_size);
    std::copy(payload_buffer, payload_buffer + payload_size, buffer.begin());
}


int main()
{
    font f(load_font_txt("font_full.txt"));
    f.sort();

    std::vector<std::vector<uint8_t>> buf(12);

    encode_v0(f, buf[0]);
    encode_v1(f, buf[1]);
    encode_v2(f, buf[2]);
    encode_v3(f, buf[3]);
    encode_v4(f, buf[4]);
    encode_v5(f, buf[5]);
    encode_v6(f, buf[6]);
    encode_v7(f, buf[7]);
    encode_v8(f, buf[8]);
    encode_v9(f, buf[9]);
    encode_v10(f, buf[10]);
    encode_v11(f, buf[11]);

    for (uint32_t i(0); i < buf.size(); ++i) {
        std::cout << "Variant " << i << ": " << buf[i].size() << " bytes\n";
    }

    return 0;
}