lzw cpp

#include <algorithm>
#include <bitset>
#include <byteswap.h>
#include <cstddef>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <ostream>
#include <vector>

#include "x86intrin.h"

extern "C" size_t lol(const uint8_t * in, size_t in_size, uint8_t * out, size_t out_size);

#ifndef NDEBUG
#define Log(strm) std::cout << strm
#else
#define Log(strm)
#endif

struct StrView
{
    uint32_t data = 0;
    uint32_t size = 0;
};

class StrViewPrinter
{
public:
    StrViewPrinter(const uint8_t * data, StrView view)
        : data(data + view.data)
        , size(view.size)
    {}

    friend std::ostream & operator<<(std::ostream & out, StrViewPrinter printer)
    {
        out << std::hex;
        auto * it = printer.data;
        auto * end = it + printer.size;
        while (it != end) {
            out << uint32_t(*it++) << ' ';
        }
        return out;
    }

private:
    const uint8_t * const data = nullptr;
    const size_t size = 0;
};

volatile uint64_t rdtscp()
{
    unsigned dummy;
    return __rdtscp(&dummy);
}

constexpr uint32_t bits(uint32_t &) { return 32; }
constexpr uint32_t half_bits(uint32_t &) { return 16; }

constexpr uint32_t ClearCode = 256;
constexpr uint32_t EOI = 257;
constexpr uint32_t FirstInTable = 258;

constexpr uint32_t SwitchTo10 = 510;
constexpr uint32_t SwitchTo11 = 1022;
constexpr uint32_t SwitchTo12 = 2046;

constexpr size_t TableSize = 4096;


uint32_t read_num(const uint8_t *& in, uint32_t & buff, uint8_t & bit_idx, uint8_t num_size)
{
    Log("read_num:\n");
    Log(" buff:" << std::bitset<sizeof(buff)>(buff));
    Log(std::dec);
    Log(" bit_idx: " << int(bit_idx));
    Log(" num_size: " << int(num_size));

    uint32_t res = (buff) << bit_idx;
    res = res >> (bits(buff) - num_size);
    Log(std::hex << " res: " << res << std::endl);

    bit_idx += num_size;
    if (bit_idx > half_bits(buff)) {
        bit_idx -= half_bits(buff);
        buff = (buff << 8) | *in++;
        buff = (buff << 8) | *in++;
    }
    return res;

}

void clear_table(StrView * table)
{
    auto * end = table + TableSize;
    table += FirstInTable;
    while (table != end) {
        *table++ = {0, 0};
    }
}

void write_string(uint32_t code, StrView * table, const uint8_t * strings, uint8_t *& out)
{
    if (code < FirstInTable) {
        Log("writech: " << code << '\n');
        *out++ = code;
    } else {
        StrView view = table[code];
        const uint8_t * str = strings + view.data;
        const uint8_t * end = str + view.size;
        Log("writestr: " << StrViewPrinter(strings, view) << '\n');
        while (str != end) {
            *out++ = *str++;
        }
    }
}

size_t lzw_dec(const uint8_t * in, size_t in_size, uint8_t * out, size_t out_size)
{
    uint32_t buff = *in++;
    buff = (buff << 8) | *in++;
    buff = (buff << 8) | *in++;
    buff = (buff << 8) | *in++;

    uint8_t bit_idx = 0;
    uint8_t num_size = 9;

    uint32_t num = 0;
    uint32_t old_num = 0;

    StrView table[TableSize];
    for (auto it = table, end = it + FirstInTable; it != end; ++it) {
        it->size = 1;
    }
    const uint8_t * strings = out;
    uint32_t free_code;

    Log(std::hex);

    while ((num = read_num(in, buff, bit_idx, num_size)) != EOI) {
        Log("num: " << num << '\n');
        if (num == ClearCode) {
            Log("cleaning up" << std::endl);
            clear_table(table);
            num_size = 9;
            free_code = FirstInTable;
            num = read_num(in, buff, bit_idx, num_size);
            Log(num << '\n');
            if (num == EOI) {
                break;
            }
            write_string(num, table, strings, out);
            old_num = num;
        } else {
            StrView new_entry;
            new_entry.data = (out - strings) - table[old_num].size; // old_num is what we've just written
            new_entry.size = table[old_num].size + 1;
            if (num < FirstInTable || table[num].size != 0) { // is in table
                write_string(num, table, strings, out);
            } else {
                write_string(old_num, table, strings, out);
                uint8_t cycled = strings[new_entry.data];
                *out++ = cycled;
                Log("writeafter: " << int(cycled) << '\n');
            }
            Log("written: " << (out - strings) << '\n');
            old_num = num;

            table[free_code] = new_entry;
                Log("code: " << free_code << " "
                    "string: " << StrViewPrinter(strings, new_entry) << '\n');
            switch (free_code) {
                case SwitchTo10:
                case SwitchTo11:
                case SwitchTo12:
                    num_size++;
                    Log("new_free_code: " << std::dec << free_code << std::endl);
                    Log("new_num_size: " << int(num_size) << std::hex << std::endl);
                    break;
            }
            free_code++;
        }
    }
    return out - strings;
}

uint8_t in[30000];
uint8_t out[40000];

int main()
{
    auto input = fopen("in", "rb");
    fread(in, 22118, 1, input);
    fclose(input);

    volatile auto start = rdtscp();
    auto decoded = lzw_dec(in, 22118, out, 40000);
    volatile auto end = rdtscp();

    std::cout << "decode time: " << (end - start) << '\n';

    auto output = fopen("my_out", "wb");
    fwrite(out, decoded, 1, output);
    fclose(output);

}