main.cpp

/*
 * ZIP File Compression System
 * Design and Analysis of Algorithms - JIIT Sector-62
 * Team: Metereya, Piyush, Raman, Shivang, Shaurya
 *
 * Algorithms: LZ77 (dictionary) + Huffman Coding (entropy)
 * Compile: g++ -std=c++17 -O2 -o zipper main.cpp
 * Usage:   ./zipper compress input.txt output.zc
 *          ./zipper decompress output.zc restored.txt
 */

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <unordered_map>
#include <map>
#include <queue>
#include <bitset>
#include <iomanip>
#include <chrono>
#include <cassert>
#include <functional>
#include <algorithm>

using namespace std;

// ============================================================
//  SECTION 1: LZ77 — Sliding Window Compression
// ============================================================

struct LZ77Token {
    int  offset;   // how far back in the window
    int  length;   // how many chars to copy
    char next;     // next literal char after the match
};

// Encode: produce a list of (offset, length, char) tokens
vector<LZ77Token> lz77_encode(const string& data,
                               int window_size   = 255,
                               int lookahead_max = 15) {
    vector<LZ77Token> tokens;
    int i = 0;
    int n = (int)data.size();

    while (i < n) {
        int best_offset = 0, best_length = 0;
        int win_start   = max(0, i - window_size);

        // Search the sliding window for the longest match
        for (int len = min(lookahead_max, n - i); len >= 1; --len) {
            string substr = data.substr(i, len);
            string window = data.substr(win_start, i - win_start);
            size_t pos    = window.rfind(substr);
            if (pos != string::npos) {
                best_offset = (int)(window.size() - pos);
                best_length = len;
                break;
            }
        }

        char next_char = (i + best_length < n) ? data[i + best_length] : '\0';
        tokens.push_back({best_offset, best_length, next_char});
        i += best_length + 1;
    }
    return tokens;
}

// Decode: reconstruct original string from tokens
string lz77_decode(const vector<LZ77Token>& tokens) {
    string result;
    for (auto& tok : tokens) {
        if (tok.length > 0) {
            int start = (int)result.size() - tok.offset;
            for (int j = 0; j < tok.length; ++j)
                result += result[start + j];
        }
        if (tok.next != '\0')
            result += tok.next;
    }
    return result;
}

// Serialize tokens to a flat string for Huffman input
string tokens_to_string(const vector<LZ77Token>& tokens) {
    string s;
    for (auto& t : tokens) {
        // Pack as fixed-width fields: 3 bytes offset, 2 bytes length, 1 byte char
        s += (char)(t.offset & 0xFF);
        s += (char)(t.length & 0xFF);
        s += (char)(t.next);
    }
    return s;
}

vector<LZ77Token> string_to_tokens(const string& s) {
    vector<LZ77Token> tokens;
    for (size_t i = 0; i + 2 < s.size(); i += 3) {
        LZ77Token t;
        t.offset = (unsigned char)s[i];
        t.length = (unsigned char)s[i+1];
        t.next   = s[i+2];
        tokens.push_back(t);
    }
    return tokens;
}

// ============================================================
//  SECTION 2: Huffman Coding — Entropy Compression
// ============================================================

struct HuffNode {
    unsigned char ch;
    int freq;
    HuffNode* left;
    HuffNode* right;
    HuffNode(unsigned char c, int f)
        : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(HuffNode* a, HuffNode* b) {
        return a->freq > b->freq;   // min-heap by frequency
    }
};

// Build Huffman tree from frequency map
HuffNode* build_huffman_tree(const unordered_map<unsigned char, int>& freq) {
    priority_queue<HuffNode*, vector<HuffNode*>, Compare> minHeap;
    for (auto& p : freq) {
    unsigned char ch = p.first;
    int f = p.second;
    minHeap.push(new HuffNode(ch, f));
}

    // Edge case: single unique character
    if (minHeap.size() == 1) {
        HuffNode* only = minHeap.top(); minHeap.pop();
        HuffNode* root = new HuffNode(0, only->freq);
        root->left = only;
        return root;
    }

    while (minHeap.size() > 1) {
        HuffNode* l = minHeap.top(); minHeap.pop();
        HuffNode* r = minHeap.top(); minHeap.pop();
        HuffNode* merged = new HuffNode(0, l->freq + r->freq);
        merged->left  = l;
        merged->right = r;
        minHeap.push(merged);
    }
    return minHeap.top();
}

// Generate code table by DFS traversal
void gen_codes(HuffNode* node, const string& code,
               unordered_map<unsigned char, string>& table) {
    if (!node) return;
    if (!node->left && !node->right) {
        table[node->ch] = code.empty() ? "0" : code;
        return;
    }
    gen_codes(node->left,  code + "0", table);
    gen_codes(node->right, code + "1", table);
}

// Encode bytes → bit-string using code table
string huffman_encode(const string& data,
                      const unordered_map<unsigned char, string>& table) {
    string bits;
    bits.reserve(data.size() * 4);
    for (unsigned char c : data)
        bits += table.at(c);
    return bits;
}

// Decode bit-string → bytes using tree
string huffman_decode(const string& bits, HuffNode* root) {
    string result;
    HuffNode* cur = root;
    for (char b : bits) {
        cur = (b == '0') ? cur->left : cur->right;
        if (!cur->left && !cur->right) {
            result += (char)cur->ch;
            cur = root;
        }
    }
    return result;
}

// Free tree memory
void free_tree(HuffNode* node) {
    if (!node) return;
    free_tree(node->left);
    free_tree(node->right);
    delete node;
}

// ============================================================
//  SECTION 3: Bit Packing (compact binary output)
// ============================================================

// Pack bit-string into bytes (pad with zeros to byte boundary)
string pack_bits(const string& bits) {
    string packed;
    int pad = (8 - (int)(bits.size() % 8)) % 8;
    packed += (char)pad;  // first byte = number of padding bits
    string padded = bits + string(pad, '0');
    for (size_t i = 0; i < padded.size(); i += 8) {
        bitset<8> byte(padded.substr(i, 8));
        packed += (char)byte.to_ulong();
    }
    return packed;
}

// Unpack bytes → bit-string (strip padding)
string unpack_bits(const string& packed) {
    if (packed.empty()) return "";
    int pad = (unsigned char)packed[0];
    string bits;
    for (size_t i = 1; i < packed.size(); ++i) {
        bitset<8> byte((unsigned char)packed[i]);
        bits += byte.to_string();
    }
    // Remove trailing padding
    if (pad > 0) bits = bits.substr(0, bits.size() - pad);
    return bits;
}

// ============================================================
//  SECTION 4: Serialise / Deserialise Huffman Code Table
//  (needed to store the table inside the compressed file)
// ============================================================

string serialize_table(const unordered_map<unsigned char, string>& table) {
    ostringstream oss;
    oss << table.size() << "\n";
    for (auto& p : table) {
    unsigned char ch = p.first;
    string code = p.second;
    oss << (int)(unsigned char)ch << " " << code << "\n";
}
    return oss.str();
}

unordered_map<unsigned char, string> deserialize_table(istream& in) {
    unordered_map<unsigned char, string> table;
    int n; in >> n;
    for (int i = 0; i < n; ++i) {
        int ch_int; string code;
        in >> ch_int >> code;
        table[(unsigned char)ch_int] = code;
    }
    return table;
}

// ============================================================
//  SECTION 5: Compress / Decompress API
// ============================================================

bool compress_file(const string& inpath, const string& outpath) {
    // --- Read input ---
    ifstream fin(inpath, ios::binary);
    if (!fin) { cerr << "Cannot open: " << inpath << "\n"; return false; }
    string data((istreambuf_iterator<char>(fin)), {});
    fin.close();

    if (data.empty()) { cerr << "Input file is empty.\n"; return false; }

    cout << "Original size     : " << data.size() << " bytes\n";

    // --- LZ77 ---
    auto t0 = chrono::high_resolution_clock::now();
    auto tokens  = lz77_encode(data);
    string serial = tokens_to_string(tokens);
    cout << "After LZ77        : " << serial.size() << " bytes ("
         << tokens.size() << " tokens)\n";

    // --- Build Huffman table ---
    unordered_map<unsigned char, int> freq;
    for (unsigned char c : serial) freq[c]++;
    HuffNode* root = build_huffman_tree(freq);
    unordered_map<unsigned char, string> table;
    gen_codes(root, "", table);
    free_tree(root);

    // --- Huffman encode ---
    string bits   = huffman_encode(serial, table);
    string packed = pack_bits(bits);

    // --- Write output file ---
    // Format:
    //   Line 1: original size
    //   Line 2: token count
    //   Lines 3..N: code table (serialized)
    //   "---DATA---\n"
    //   raw packed bytes
    ofstream fout(outpath, ios::binary);
    if (!fout) { cerr << "Cannot write: " << outpath << "\n"; return false; }

    string header;
    header += to_string(data.size())   + "\n";
    header += to_string(tokens.size()) + "\n";
    header += serialize_table(table);
    header += "---DATA---\n";

    fout.write(header.data(), header.size());
    fout.write(packed.data(), packed.size());
    fout.close();

    auto t1 = chrono::high_resolution_clock::now();
    double ms = chrono::duration<double,milli>(t1-t0).count();

    // --- Stats ---
    ifstream fs(outpath, ios::binary | ios::ate);
    size_t comp_size = fs.tellg();
    double ratio = 100.0 * (1.0 - (double)comp_size / data.size());

    cout << "Compressed size   : " << comp_size   << " bytes\n";
    cout << "Compression ratio : " << fixed << setprecision(1) << ratio << "% saved\n";
    cout << "Time taken        : " << fixed << setprecision(2) << ms << " ms\n";
    cout << "Output written to : " << outpath << "\n";
    return true;
}

bool decompress_file(const string& inpath, const string& outpath) {
    ifstream fin(inpath, ios::binary);
    if (!fin) { cerr << "Cannot open: " << inpath << "\n"; return false; }

    // --- Read header ---
    size_t orig_size, token_count;
    fin >> orig_size >> token_count;
    fin.ignore();   // consume newline after token_count

    auto table    = deserialize_table(fin);
    fin.ignore();   // newline after table

    string marker;
    getline(fin, marker);   // "---DATA---"

    // --- Read packed bytes ---
    string packed((istreambuf_iterator<char>(fin)), {});
    fin.close();

    // --- Huffman decode ---
    string bits   = unpack_bits(packed);

    // Rebuild tree from table for decoding
    // (We reconstruct it from the code table — same tree structure)
    // Simple approach: use code table directly for decode via trie
    // Build a decode trie from the stored table
    struct TrieNode {
        TrieNode* ch[2] = {nullptr, nullptr};
        int symbol = -1;
    };
    TrieNode* troot = new TrieNode();
    for (auto& p : table) {
    unsigned char c = p.first;
    string code = p.second;

    TrieNode* cur = troot;
    for (char b : code) {
        int idx = b - '0';
        if (!cur->ch[idx]) cur->ch[idx] = new TrieNode();
        cur = cur->ch[idx];
    }
    cur->symbol = (int)(unsigned char)c;
}

    string serial;
    serial.reserve(token_count * 3);
    TrieNode* cur = troot;
    for (char b : bits) {
        int idx = b - '0';
        cur = cur->ch[idx];
        if (!cur) break;
        if (cur->symbol != -1) {
            serial += (char)cur->symbol;
            cur = troot;
        }
    }

    // Free trie
    function<void(TrieNode*)> free_trie = [&](TrieNode* n){
        if (!n) return;
        free_trie(n->ch[0]); free_trie(n->ch[1]); delete n;
    };
    free_trie(troot);

    // --- LZ77 decode ---
    auto tokens = string_to_tokens(serial);
    string result = lz77_decode(tokens);

    // Trim to original size (handles padding edge cases)
    if (result.size() > orig_size) result = result.substr(0, orig_size);

    // --- Write output ---
    ofstream fout(outpath, ios::binary);
    if (!fout) { cerr << "Cannot write: " << outpath << "\n"; return false; }
    fout.write(result.data(), result.size());
    fout.close();

    cout << "Decompressed size : " << result.size() << " bytes\n";
    cout << "Output written to : " << outpath << "\n";
    return true;
}

// ============================================================
//  SECTION 6: CLI Entry Point
// ============================================================

void print_usage() {
    cout << "\n╔══════════════════════════════════════════════════╗\n";
    cout << "║   ZIP Compression System — JIIT DAA Project      ║\n";
    cout << "║   Algorithms: LZ77 + Huffman Coding               ║\n";
    cout << "╚══════════════════════════════════════════════════╝\n\n";
    cout << "Usage:\n";
    cout << "  ./zipper compress   <input.txt>  <output.zc>\n";
    cout << "  ./zipper decompress <input.zc>   <output.txt>\n";
    cout << "  ./zipper demo                    (run built-in test)\n\n";
}

void run_demo() {
    cout << "\n=== BUILT-IN DEMO ===\n\n";

    // --- LZ77 demo ---
    string sample = "abracadabra abracadabra is a magic word";
    cout << "Input string : \"" << sample << "\"\n";
    auto tokens = lz77_encode(sample);
    cout << "LZ77 tokens  : " << tokens.size() << "\n";
    cout << "  First 5 tokens (offset, length, next_char):\n";
    for (int i = 0; i < min(5,(int)tokens.size()); ++i)
        cout << "    (" << tokens[i].offset << ", " << tokens[i].length
             << ", '" << (tokens[i].next ? tokens[i].next : ' ') << "')\n";
    string decoded = lz77_decode(tokens);
    cout << "LZ77 decoded : \"" << decoded << "\"\n";
    cout << "Match        : " << (decoded == sample ? "PASS " : "FAIL ") << "\n\n";

    // --- Huffman demo ---
    string htext = "this is a huffman coding demonstration";
    unordered_map<unsigned char, int> freq;
    for (unsigned char c : htext) freq[c]++;
    HuffNode* root = build_huffman_tree(freq);
    unordered_map<unsigned char, string> table;
    gen_codes(root, "", table);

    cout << "Huffman code table for: \"" << htext << "\"\n";
    // Sort by code length for display
    vector<pair<unsigned char,string>> sorted_table(table.begin(), table.end());
    sort(sorted_table.begin(), sorted_table.end(),
         [](auto& a, auto& b){ return a.second.size() < b.second.size(); });
    for (auto& p : sorted_table) {
    unsigned char ch = p.first;
    string code = p.second;

    cout << "  '" << ch << "'  (freq=" << freq[ch] << ")  ->  " << code << "\n";
}

    string bits = huffman_encode(htext, table);
    string hdec = huffman_decode(bits, root);
    cout << "\nOriginal bits  : " << htext.size()*8 << "\n";
    cout << "Huffman bits   : " << bits.size() << "\n";
    cout << "Savings        : " << fixed << setprecision(1)
         << 100.0*(1.0 - (double)bits.size()/(htext.size()*8)) << "%\n";
    cout << "Decoded match  : " << (hdec == htext ? "PASS " : "FAIL ") << "\n";
    free_tree(root);

    // --- Full pipeline demo ---
    cout << "\n=== FULL PIPELINE TEST ===\n";
    string testfile = "zipper_test_input.txt";
    string compfile = "zipper_test.zc";
    string restfile = "zipper_test_restored.txt";

    string testdata = "The quick brown fox jumps over the lazy dog. "
                      "The quick brown fox jumps over the lazy dog. "
                      "Pack my box with five dozen liquor jugs. "
                      "Huffman and LZ77 together make DEFLATE compression!";
    ofstream tf(testfile); tf << testdata; tf.close();

    cout << "\n-- Compression --\n";
    compress_file(testfile, compfile);
    cout << "\n-- Decompression --\n";
    decompress_file(compfile, restfile);

    ifstream rf(restfile);
    string restored((istreambuf_iterator<char>(rf)), {});
    cout << "\nIntegrity check  : "
         << (restored == testdata ? "PASS - files match perfectly" : "FAIL ") << "\n";
}

int main(int argc, char* argv[]) {
    if (argc < 2) { print_usage(); return 1; }

    string mode = argv[1];

    if (mode == "demo") {
        run_demo();
    } else if (mode == "compress" && argc == 4) {
        cout << "\n=== COMPRESSING ===\n";
        return compress_file(argv[2], argv[3]) ? 0 : 1;
    } else if (mode == "decompress" && argc == 4) {
        cout << "\n=== DECOMPRESSING ===\n";
        return decompress_file(argv[2], argv[3]) ? 0 : 1;
    } else {
        print_usage();
        return 1;
    }
    return 0;
}