file_compressor.cpp

// backend_full_compressor.cpp
// Full backend-style C++ implementation:
//  - LZ77 (simple sliding-window) compressor/decompressor
//  - Huffman compressor/decompressor (bit-level, tree serialized)
//  - Pipeline: LZ77 -> Huffman (and reverse)
//  - CLI for backend usage
// Compile: g++ -std=c++17 -O2 -o backend_full_compressor backend_full_compressor.cpp

#include <bits/stdc++.h>
using namespace std;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;

// ---------------------- File I/O ----------------------
class FileIO {
public:
    static vector<u8> readAll(const string &path) {
        ifstream in(path, ios::binary);
        if(!in) throw runtime_error("Cannot open input file: " + path);
        return vector<u8>((istreambuf_iterator<char>(in)), istreambuf_iterator<char>());
    }
    static void writeAll(const string &path, const vector<u8>& data) {
        ofstream out(path, ios::binary);
        if(!out) throw runtime_error("Cannot open output file: " + path);
        out.write(reinterpret_cast<const char*>(data.data()), data.size());
    }
};

// ---------------------- Bit writer / reader ----------------------
struct BitWriter {
    vector<u8> out;
    u8 cur = 0;
    int bits_filled = 0;
    u64 total_bits = 0;

    void writeBit(int b) {
        if(b) cur |= (1u << (7 - bits_filled));
        bits_filled++;
        total_bits++;
        if(bits_filled == 8) {
            out.push_back(cur);
            cur = 0; bits_filled = 0;
        }
    }
    // write 'count' bits from the most-significant side of val
    void writeBits(u32 val, int count) {
        for(int i = count - 1; i >= 0; --i) writeBit((val >> i) & 1u);
    }
    void writeByte(u8 byte) {
        writeBits(byte, 8);
    }
    void flush() {
        if(bits_filled) {
            out.push_back(cur);
            cur = 0; bits_filled = 0;
        }
    }
};

struct BitReader {
    const vector<u8>& in;
    size_t pos = 0;
    u8 cur = 0;
    int bits_left = 0;
    BitReader(const vector<u8>& data): in(data) {}
    // returns -1 on EOF
    int readBit() {
        if(bits_left == 0) {
            if(pos >= in.size()) return -1;
            cur = in[pos++];
            bits_left = 8;
        }
        int b = (cur >> (bits_left - 1)) & 1;
        bits_left--;
        return b;
    }
    int readBits(int count) {
        int v = 0;
        for(int i=0;i<count;i++) {
            int b = readBit();
            if(b < 0) return -1;
            v = (v << 1) | b;
        }
        return v;
    }
    // remaining bytes (unused bits in current byte are considered consumed)
    size_t remainingBytes() const {
        return (in.size() >= pos) ? (in.size() - pos) : 0;
    }
};

// ---------------------- LZ77 ----------------------
// Token format for LZ77 token stream (simple):
// Literal:  0x00 <byte>
// Match:    0x01 <dist_hi> <dist_lo> <len>
// dist: 16-bit, len: 8-bit. Emit matches only when len >= 3.

class LZ77 {
public:
    struct Config { int window_size = 1<<15; int lookahead = 255; };

    static vector<u8> compress(const vector<u8>& input, Config cfg = {}) {
        vector<u8> out;
        size_t n = input.size();
        size_t pos = 0;
        while(pos < n) {
            int best_len = 0;
            int best_dist = 0;
            size_t start = (pos > (size_t)cfg.window_size) ? pos - cfg.window_size : 0;
            size_t max_len = min((size_t)cfg.lookahead, n - pos);
            // naive search for simplicity - O(window * lookahead)
            for(size_t j = start; j < pos; ++j) {
                int len = 0;
                while(len < (int)max_len && input[j + len] == input[pos + len]) ++len;
                if(len > best_len) {
                    best_len = len;
                    best_dist = (int)(pos - j);
                    if(best_len == (int)max_len) break;
                }
            }
            if(best_len >= 3) {
                out.push_back(0x01);
                u16 dist = (u16)best_dist;
                out.push_back((u8)(dist >> 8));
                out.push_back((u8)(dist & 0xFF));
                out.push_back((u8)best_len);
                pos += best_len;
            } else {
                out.push_back(0x00);
                out.push_back(input[pos++]);
            }
        }
        return out;
    }

    static vector<u8> decompress(const vector<u8>& tokens) {
        vector<u8> out;
        size_t pos = 0;
        while(pos < tokens.size()) {
            u8 t = tokens[pos++];
            if(t == 0x00) {
                if(pos >= tokens.size()) throw runtime_error("LZ77: malformed literal");
                out.push_back(tokens[pos++]);
            } else if(t == 0x01) {
                if(pos + 2 >= tokens.size()) throw runtime_error("LZ77: malformed match");
                u16 dist = ((u16)tokens[pos] << 8) | tokens[pos+1];
                u8 len = tokens[pos+2];
                pos += 3;
                if(dist == 0 || dist > out.size()) throw runtime_error("LZ77: invalid distance");
                size_t start = out.size() - dist;
                for(int i=0;i<len;i++) out.push_back(out[start + i]);
            } else {
                throw runtime_error("LZ77: unknown token");
            }
        }
        return out;
    }
};

// ---------------------- Huffman ----------------------
class Huffman {
private:
    struct Node {
        u8 byte;
        u64 freq;
        Node *l, *r;
        Node(u8 b, u64 f): byte(b), freq(f), l(nullptr), r(nullptr) {}
        Node(Node* L, Node* R): byte(0), freq(L->freq + R->freq), l(L), r(R) {}
        bool isLeaf() const { return l == nullptr && r == nullptr; }
    };

    struct Cmp {
        bool operator()(const Node* a, const Node* b) const {
            if(a->freq != b->freq) return a->freq > b->freq;
            return a->byte > b->byte;
        }
    };

    static void deleteTree(Node* n) {
        if(!n) return;
        deleteTree(n->l);
        deleteTree(n->r);
        delete n;
    }

    static void buildCodes(Node* node, vector<string>& codes, string cur = "") {
        if(!node) return;
        if(node->isLeaf()) {
            codes[node->byte] = cur.empty() ? "0" : cur; // single-symbol edge case
            return;
        }
        buildCodes(node->l, codes, cur + "0");
        buildCodes(node->r, codes, cur + "1");
    }

    // Serialize tree to bitwriter (preorder):
    // leaf: write 1 then 8 bits of byte
    // internal: write 0 then recurse
    static void serializeTree(Node* node, BitWriter& bw) {
        if(!node) return;
        if(node->isLeaf()) {
            bw.writeBit(1);
            bw.writeBits(node->byte, 8);
        } else {
            bw.writeBit(0);
            serializeTree(node->l, bw);
            serializeTree(node->r, bw);
        }
    }
    static Node* deserializeTree(BitReader& br) {
        int b = br.readBit();
        if(b < 0) throw runtime_error("Huffman: tree truncated");
        if(b == 1) {
            int val = br.readBits(8);
            if(val < 0) throw runtime_error("Huffman: tree leaf truncated");
            return new Node((u8)val, 0);
        } else {
            Node* left = deserializeTree(br);
            Node* right = deserializeTree(br);
            return new Node(left, right);
        }
    }

public:
    // Compress raw bytes -> packed bytes containing:
    // [4 bytes tree_bitlen][tree_bytes][4 bytes data_bitlen][data_bytes]
    static vector<u8> compress(const vector<u8>& data) {
        // handle empty
        if(data.empty()) {
            vector<u8> empty_out(8, 0); // tree_bits=0, data_bits=0
            return empty_out;
        }

        u64 freq[256] = {0};
        for(u8 b : data) freq[b]++;

        priority_queue<Node*, vector<Node*>, Cmp> pq;
        for(int i=0;i<256;i++) if(freq[i]) pq.push(new Node((u8)i, freq[i]));
        if(pq.size() == 1) {
            // create a second node to avoid degenerate tree
            Node* only = pq.top(); pq.pop();
            Node* fake = new Node((u8)((only->byte + 1) & 0xFF), 0);
            pq.push(new Node(only, fake));
        }
        while(pq.size() > 1) {
            Node* a = pq.top(); pq.pop();
            Node* b = pq.top(); pq.pop();
            pq.push(new Node(a,b));
        }
        Node* root = pq.top();

        vector<string> codes(256);
        buildCodes(root, codes);

        // serialize tree
        BitWriter treeBW;
        serializeTree(root, treeBW);
        treeBW.flush();
        u32 tree_bits = (u32)treeBW.total_bits;
        vector<u8> tree_bytes = treeBW.out;

        // encode data bits
        BitWriter dataBW;
        for(u8 b : data) {
            const string &c = codes[b];
            for(char ch : c) dataBW.writeBit(ch == '1');
        }
        dataBW.flush();
        u32 data_bits = (u32)dataBW.total_bits;
        vector<u8> data_bytes = dataBW.out;

        // compose output
        vector<u8> out;
        auto push_u32 = [&](u32 x){
            out.push_back((u8)((x >> 24) & 0xFF));
            out.push_back((u8)((x >> 16) & 0xFF));
            out.push_back((u8)((x >> 8) & 0xFF));
            out.push_back((u8)(x & 0xFF));
        };
        push_u32(tree_bits);
        out.insert(out.end(), tree_bytes.begin(), tree_bytes.end());
        push_u32(data_bits);
        out.insert(out.end(), data_bytes.begin(), data_bytes.end());

        deleteTree(root);
        return out;
    }

    // Decompress from packed format back to original bytes
    static vector<u8> decompress(const vector<u8>& packed) {
        if(packed.size() < 8) throw runtime_error("Huffman: packed too small");
        auto read_u32 = [&](size_t off)->u32{
            if(off + 4 > packed.size()) throw runtime_error("Huffman: header truncated");
            return ((u32)packed[off] << 24) | ((u32)packed[off+1] << 16) | ((u32)packed[off+2] << 8) | (u32)packed[off+3];
        };
        u32 tree_bits = read_u32(0);
        size_t tree_byte_len = (tree_bits + 7) / 8;
        if(4 + tree_byte_len + 4 > packed.size()) throw runtime_error("Huffman: bad header sizes");
        vector<u8> tree_bytes(packed.begin() + 4, packed.begin() + 4 + tree_byte_len);
        u32 data_bits = read_u32(4 + tree_byte_len);
        size_t data_start = 4 + tree_byte_len + 4;
        vector<u8> data_bytes;
        if(data_start <= packed.size()) data_bytes.assign(packed.begin() + data_start, packed.end());

        if(tree_bits == 0 && data_bits == 0) return {}; // empty original

        // rebuild tree
        BitReader treeBR(tree_bytes);
        Node* root = deserializeTree(treeBR);

        // decode data bits by walking tree
        BitReader dataBR(data_bytes);
        vector<u8> out;
        Node* node = root;
        for(u32 i=0;i<data_bits;i++) {
            int b = dataBR.readBit();
            if(b < 0) throw runtime_error("Huffman: data bitstream truncated");
            node = (b == 0) ? node->l : node->r;
            if(!node) throw runtime_error("Huffman: traversal error");
            if(node->isLeaf()) {
                out.push_back(node->byte);
                node = root;
            }
        }

        deleteTree(root);
        return out;
    }
};

// ---------------------- Combined Pipeline & File Format ----------------------
// Final file format for pipeline:
// [4 bytes magic 'FZ01'] [HuffmanPacked (tree+data) covering LZ77 token stream]
// To decompress: read magic, send rest to Huffman::decompress -> get token stream -> LZ77::decompress

static const array<u8,4> MAGIC = {'F','Z','0','1'};

class CompressorService {
public:
    // full pipeline: input -> LZ77 tokens -> Huffman packed -> write with magic header
    static void compressFile(const string &infile, const string &outfile) {
        auto input = FileIO::readAll(infile);
        cerr << "[Service] Read input: " << input.size() << " bytes\n";

        auto tokens = LZ77::compress(input);
        cerr << "[Service] LZ77 tokens: " << tokens.size() << " bytes\n";

        auto huff = Huffman::compress(tokens);
        cerr << "[Service] Huffman packed size: " << huff.size() << " bytes\n";

        vector<u8> out;
        out.insert(out.end(), MAGIC.begin(), MAGIC.end());
        out.insert(out.end(), huff.begin(), huff.end());
        FileIO::writeAll(outfile, out);
        cerr << "[Service] Compressed file written: " << outfile << " (" << out.size() << " bytes)\n";
    }

    // read file, check magic, strip header, Huffman-decompress -> tokens -> LZ77-decompress -> write original
    static void decompressFile(const string &infile, const string &outfile) {
        auto data = FileIO::readAll(infile);
        if(data.size() < 4) throw runtime_error("Input too small");
        if(!equal(MAGIC.begin(), MAGIC.end(), data.begin())) throw runtime_error("Bad magic header - not recognized format");
        vector<u8> huff_part(data.begin() + 4, data.end());
        auto tokens = Huffman::decompress(huff_part);
        cerr << "[Service] Huffman -> tokens: " << tokens.size() << " bytes\n";
        auto original = LZ77::decompress(tokens);
        cerr << "[Service] LZ77 -> original: " << original.size() << " bytes\n";
        FileIO::writeAll(outfile, original);
        cerr << "[Service] Decompressed file written: " << outfile << "\n";
    }

    // convenience single-stage helpers (for testing)
    static void lz77CompressFile(const string& in, const string& out) {
        auto input = FileIO::readAll(in);
        auto tokens = LZ77::compress(input);
        FileIO::writeAll(out, tokens);
        cerr << "[Service] Wrote LZ77 token stream to " << out << "\n";
    }
    static void lz77DecompressFile(const string& in, const string& out) {
        auto tokens = FileIO::readAll(in);
        auto orig = LZ77::decompress(tokens);
        FileIO::writeAll(out, orig);
        cerr << "[Service] Wrote LZ77-decompressed to " << out << "\n";
    }
    static void huffCompressFile(const string& in, const string& out) {
        auto input = FileIO::readAll(in);
        auto packed = Huffman::compress(input);
        FileIO::writeAll(out, packed);
        cerr << "[Service] Wrote Huffman-packed to " << out << "\n";
    }
    static void huffDecompressFile(const string& in, const string& out) {
        auto packed = FileIO::readAll(in);
        auto orig = Huffman::decompress(packed);
        FileIO::writeAll(out, orig);
        cerr << "[Service] Wrote Huffman-decompressed to " << out << "\n";
    }
};

// ---------------------- CLI Entrypoint ----------------------
int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    try {
        if(argc < 4) {
            cerr << "Usage:\n"
                 << "  " << argv[0] << " compress <input> <output>\n"
                 << "  " << argv[0] << " decompress <input> <output>\n"
                 << "  " << argv[0] << " lz77-compress <input> <output>\n"
                 << "  " << argv[0] << " lz77-decompress <input> <output>\n"
                 << "  " << argv[0] << " huff-compress <input> <output>\n"
                 << "  " << argv[0] << " huff-decompress <input> <output>\n";
            return 1;
        }
        string cmd = argv[1];
        string in = argv[2];
        string out = argv[3];

        if(cmd == "compress") CompressorService::compressFile(in, out);
        else if(cmd == "decompress") CompressorService::decompressFile(in, out);
        else if(cmd == "lz77-compress") CompressorService::lz77CompressFile(in, out);
        else if(cmd == "lz77-decompress") CompressorService::lz77DecompressFile(in, out);
        else if(cmd == "huff-compress") CompressorService::huffCompressFile(in, out);
        else if(cmd == "huff-decompress") CompressorService::huffDecompressFile(in, out);
        else {
            cerr << "Unknown command: " << cmd << "\n";
            return 1;
        }
    } catch(const exception &e) {
        cerr << "Error: " << e.what() << "\n";
        return 1;
    }
    return 0;
}