#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MIN_MATCH 3
#define MAX_MATCH 258
#define WS_SMALL 511
#define WS_LARGE 16383

#define HASH_SIZE 65536
#define HASH_MASK (HASH_SIZE - 1)

// v1.6: optimal-lazy parsing compativel com formato v1.5 (decoder identico)
// greedy -> lazy com custo real em bits, sem Huffman/range
#define BLOCK_SIZE 65536

// ============================================================================
// INTEGRITY ANCHOR (HONORING MARK ADLER)
// ============================================================================
uint32_t calcular_adler32(const uint8_t *data, size_t len) {
    uint32_t a = 1, b = 0;
    for (size_t i = 0; i < len; i++) {
        a = (a + data[i]) % 65521;
        b = (b + a) % 65521;
    }
    return (b << 16) | a;
}

// ============================================================================
// IN-MEMORY BIT-STREAM (para decidir comprimido vs stored)
// ============================================================================
typedef struct {
    uint8_t *buf;
    size_t cap;
    size_t bit_pos;
} MemBitStream;

void mbs_init(MemBitStream *stream, uint8_t *buffer, size_t capacity) {
    stream->buf = buffer;
    stream->cap = capacity;
    stream->bit_pos = 0;
    memset(buffer, 0, capacity);
}

void mbs_write_bit(MemBitStream *stream, int bit) {
    size_t byte_idx = stream->bit_pos / 8;
    int bit_idx = 7 - (int)(stream->bit_pos % 8);
    if (byte_idx >= stream->cap) return;
    if (bit) stream->buf[byte_idx] |= (uint8_t)(1 << bit_idx);
    else stream->buf[byte_idx] &= (uint8_t)~(1 << bit_idx);
    stream->bit_pos++;
}

void mbs_write_bits(MemBitStream *stream, uint32_t value, int n) {
    for (int i = n - 1; i >= 0; i--)
        mbs_write_bit(stream, (value >> i) & 1);
}

// ============================================================================
// FILE BIT WRITER (sem nested function, compila MSVC + GCC)
// ============================================================================
typedef struct {
    FILE *f;
    uint8_t cur;
    int nbits;
} BitWriter;

void bw_init(BitWriter *w, FILE *f) { w->f = f; w->cur = 0; w->nbits = 0; }

void bw_write_bit(BitWriter *w, int bit) {
    w->cur = (uint8_t)((w->cur << 1) | (bit & 1));
    w->nbits++;
    if (w->nbits == 8) {
        fputc(w->cur, w->f);
        w->cur = 0;
        w->nbits = 0;
    }
}

void bw_write_bits(BitWriter *w, uint32_t v, int n) {
    for (int i = n - 1; i >= 0; i--)
        bw_write_bit(w, (v >> i) & 1);
}

void bw_flush(BitWriter *w) {
    if (w->nbits > 0) {
        w->cur <<= (8 - w->nbits);
        fputc(w->cur, w->f);
        w->cur = 0;
        w->nbits = 0;
    }
}

// ============================================================================
// FILE BIT READER (sem ftell, sem global, sem perder sync)
// ============================================================================
typedef struct {
    FILE *f;
    uint8_t buf;
    int cnt;
    int eof;
} BitReader;

void br_init(BitReader *r, FILE *f) { r->f = f; r->buf = 0; r->cnt = 0; r->eof = 0; }

int br_read_bit(BitReader *r) {
    if (r->cnt == 0) {
        int c = fgetc(r->f);
        if (c == EOF) { r->eof = 1; return 0; }
        r->buf = (uint8_t)c;
        r->cnt = 8;
    }
    r->cnt--;
    return (r->buf >> r->cnt) & 1;
}

uint32_t br_read_bits(BitReader *r, int n) {
    uint32_t v = 0;
    for (int i = 0; i < n; i++) v = (v << 1) | (uint32_t)br_read_bit(r);
    return v;
}

// descarta resto do byte parcial -> usar SOMENTE antes de bloco stored
void br_align(BitReader *r) { r->cnt = 0; }

// ============================================================================
// HASH ENGINE
// ============================================================================
static inline uint32_t quick_hash(const uint8_t *ptr) {
    return ((uint32_t)(ptr[0] << 8) ^ (uint32_t)(ptr[1] << 4) ^ (uint32_t)ptr[2]) & HASH_MASK;
}

// head/prev como int64 para arquivos grandes, -1 = vazio
// retorna match length, preenche *best_off e *use_large
int find_match_v15(uint8_t *in, uint64_t global_pos, uint64_t block_end,
                   int64_t *head, int64_t *prev, int *best_off, int *use_large) {
    int best_len_s = 0, best_off_s = 0;
    int best_len_l = 0, best_off_l = 0;

    if (block_end <= global_pos) return 0;
    uint64_t remain = block_end - global_pos;
    uint64_t max = remain > MAX_MATCH ? MAX_MATCH : remain;
    if (max < MIN_MATCH) return 0;

    uint32_t h = quick_hash(&in[global_pos]);
    int64_t cur = head[h];

    int chain = 0;
    while (cur != -1 && chain++ < 256) {
        uint64_t match_pos = (uint64_t)cur;
        if (match_pos >= global_pos) break; // seguranca
        uint64_t distance = global_pos - match_pos;
        if (distance > (uint64_t)WS_LARGE) break;
        if (distance == 0) break;

        // sem prefetch OOB: calcula direto (seguro: match_pos+l < block_end, global_pos+l < block_end)
        int l = 0;
        // match_pos+l < total garantido se match_pos < global_pos e l <= max
        while ((uint64_t)l < max && in[match_pos + l] == in[global_pos + l]) l++;

        if (distance <= (uint64_t)WS_SMALL && l >= MIN_MATCH && l > best_len_s) {
            best_len_s = l;
            best_off_s = (int)distance;
        }
        if (l >= MIN_MATCH && l > best_len_l) {
            best_len_l = l;
            best_off_l = (int)distance;
        }
        cur = prev[match_pos & (uint64_t)WS_LARGE];
    }

    if (best_len_s < MIN_MATCH && best_len_l < MIN_MATCH) return 0;
    if (best_len_s < MIN_MATCH) { *best_off = best_off_l; *use_large = 1; return best_len_l; }
    if (best_len_l < MIN_MATCH) { *best_off = best_off_s; *use_large = 0; return best_len_s; }

    if (((best_len_l - best_len_s) * 9) > 5) {
        *best_off = best_off_l; *use_large = 1; return best_len_l;
    } else {
        *best_off = best_off_s; *use_large = 0; return best_len_s;
    }
}

static void hash_insert(uint8_t *buf, uint64_t total_len, uint64_t pos,
                        int64_t *head, int64_t *prev) {
    if (pos + MIN_MATCH > total_len) return;
    uint32_t h = quick_hash(&buf[pos]);
    prev[pos & (uint64_t)WS_LARGE] = head[h];
    head[h] = (int64_t)pos;
}

// ============================================================================
// COMPRESSAO COM STORED BLOCK ESCAPE (pulo se nao compressivel)
// Formato v1.5:
//   header 12 bytes: uint64 total_len + uint32 adler
//   por bloco:
//     1 bit tipo
//     se 1 (comprimido): 32 bits decomp_len + tokens (para exatamente decomp_len bytes)
//     se 0 (stored): flush byte + uint32 raw_len LE + raw bytes
// ============================================================================
int executar_compressao(const char* entrada, const char* saida) {
    FILE *fin = fopen(entrada, "rb");
    if (!fin) { printf("Error opening input payload.\n"); return 1; }

    fseek(fin, 0, SEEK_END);
    long ft = ftell(fin);
    uint64_t total_len = ft < 0 ? 0 : (uint64_t)ft;
    fseek(fin, 0, SEEK_SET);

    uint8_t *buf = NULL;
    if (total_len > 0) {
        buf = (uint8_t*)malloc((size_t)total_len);
        if (!buf) { printf("Memory allocation failure.\n"); fclose(fin); return 1; }
        if (fread(buf, 1, (size_t)total_len, fin) != (size_t)total_len) {
            printf("Read fault.\n"); fclose(fin); free(buf); return 1;
        }
    }
    fclose(fin);

    uint32_t checksum = calcular_adler32(buf ? buf : (uint8_t*)"", (size_t)total_len);

    FILE *fout = fopen(saida, "wb");
    if (!fout) { printf("Error creating compressed file.\n"); free(buf); return 1; }

    fwrite(&total_len, sizeof(uint64_t), 1, fout);
    fwrite(&checksum, sizeof(uint32_t), 1, fout);

    if (total_len == 0) { fclose(fout); free(buf); return 0; }

    int64_t *head = (int64_t*)malloc(HASH_SIZE * sizeof(int64_t));
    int64_t *prev = (int64_t*)malloc((WS_LARGE + 1) * sizeof(int64_t));
    uint8_t *comp_block_buf = (uint8_t*)malloc(BLOCK_SIZE * 3);
    if (!head || !prev || !comp_block_buf) {
        printf("Memory allocation failure.\n");
        fclose(fout); free(buf); free(head); free(prev); free(comp_block_buf);
        return 1;
    }
    for (int i = 0; i < HASH_SIZE; i++) head[i] = -1;
    for (int i = 0; i <= WS_LARGE; i++) prev[i] = -1;

    BitWriter bw;
    bw_init(&bw, fout);

    uint64_t global_p = 0;
    while (global_p < total_len) {
        uint64_t block_start = global_p;
        uint64_t block_end = block_start + BLOCK_SIZE;
        if (block_end > total_len) block_end = total_len;
        uint32_t block_raw_len = (uint32_t)(block_end - block_start);

        MemBitStream mbs;
        mbs_init(&mbs, comp_block_buf, BLOCK_SIZE * 3);

        // --- v1.6 lazy parsing: compara economia atual vs proxima ---
        uint64_t internal_p = block_start;
        while (internal_p < block_end) {
            int off = 0, use_large = 0, ml = 0;
            if (internal_p + MIN_MATCH <= block_end)
                ml = find_match_v15(buf, internal_p, block_end, head, prev, &off, &use_large);

            int emit_literal = 1;
            int cur_cost = 0, cur_save = -1000000;
            if (ml >= MIN_MATCH) {
                int bits_offset = use_large ? 14 : 9;
                cur_cost = (ml >= 10) ? (1 + 1 + 3 + bits_offset + 8) : (1 + 1 + 3 + bits_offset);
                cur_save = ml * 9 - cur_cost;
                if (cur_save > 0) {
                    // lookahead em internal_p+1 (com internal_p ja inserido no hash)
                    hash_insert(buf, total_len, internal_p, head, prev);
                    int off2 = 0, use_large2 = 0, ml2 = 0;
                    if (internal_p + 1 + MIN_MATCH <= block_end)
                        ml2 = find_match_v15(buf, internal_p + 1, block_end, head, prev, &off2, &use_large2);
                    if (ml2 >= MIN_MATCH) {
                        int bits2 = use_large2 ? 14 : 9;
                        int cost2 = (ml2 >= 10) ? (1 + 1 + 3 + bits2 + 8) : (1 + 1 + 3 + bits2);
                        int save2 = ml2 * 9 - cost2;
                        if (save2 > cur_save) {
                            // proximo e melhor: emite literal atual (hash ja inserido)
                            mbs_write_bit(&mbs, 0);
                            mbs_write_bits(&mbs, buf[internal_p], 8);
                            internal_p++;
                            continue;
                        }
                    }
                    // remove insercao temporaria? nao: ela faz parte do match; emite match
                    // desfaz contabilmente: internal_p ainda nao avancou, entao re-usa hash atual
                    // (prev/head ja contem internal_p, o que e correto para os proximos k-1 inserts)
                    emit_literal = 0;
                    mbs_write_bit(&mbs, 1);
                    mbs_write_bit(&mbs, use_large);
                    if (ml < 10) mbs_write_bits(&mbs, (uint32_t)(ml - 3), 3);
                    else mbs_write_bits(&mbs, 7, 3);
                    mbs_write_bits(&mbs, (uint32_t)off, bits_offset);
                    if (ml >= 10) mbs_write_bits(&mbs, (uint32_t)(ml - 3), 8);
                    // internal_p ja inserido acima; insere o resto do match
                    internal_p++;
                    for (int k = 1; k < ml; k++) {
                        hash_insert(buf, total_len, internal_p, head, prev);
                        internal_p++;
                    }
                    continue;
                }
            }
            if (emit_literal) {
                mbs_write_bit(&mbs, 0);
                mbs_write_bits(&mbs, buf[internal_p], 8);
                hash_insert(buf, total_len, internal_p, head, prev);
                internal_p++;
            }
        }

        size_t total_bits_used = mbs.bit_pos;
        size_t total_bytes_used = (total_bits_used + 7) / 8;

        if (total_bytes_used < block_raw_len) {
            // bloco comprimido: tipo 1 + decomp_len + bits (sem alinhar, sem ftell)
            bw_write_bit(&bw, 1);
            bw_write_bits(&bw, block_raw_len, 32);
            for (size_t bit_idx = 0; bit_idx < total_bits_used; bit_idx++) {
                size_t byte_pos = bit_idx / 8;
                int bit_pos = 7 - (int)(bit_idx % 8);
                bw_write_bit(&bw, (comp_block_buf[byte_pos] >> bit_pos) & 1);
            }
        } else {
            // pulo: bloco stored, nao expande
            bw_write_bit(&bw, 0);
            bw_flush(&bw);
            fwrite(&block_raw_len, sizeof(uint32_t), 1, fout);
            fwrite(&buf[block_start], 1, block_raw_len, fout);
        }
        global_p = block_end;
    }

    bw_flush(&bw);
    fclose(fout); free(buf); free(head); free(prev); free(comp_block_buf);
    printf("LZSS v1.6 Lazy Optimal Parsing engine complete.\n");
    return 0;
}

// ============================================================================
// DESCOMPRESSAO
// ============================================================================
int executar_descompressao(const char* entrada, const char* saida) {
    FILE *fin = fopen(entrada, "rb");
    if (!fin) { printf("Error opening compressed file.\n"); return 1; }

    uint64_t total_original_len = 0;
    uint32_t checksum_original = 0;
    if (fread(&total_original_len, sizeof(uint64_t), 1, fin) != 1 ||
        fread(&checksum_original, sizeof(uint32_t), 1, fin) != 1) {
        printf("Header processing fault.\n"); fclose(fin); return 1;
    }

    uint8_t *out_buf = NULL;
    if (total_original_len > 0) {
        out_buf = (uint8_t*)malloc((size_t)total_original_len);
        if (!out_buf) { printf("Memory bounds allocation fault.\n"); fclose(fin); return 1; }
    } else {
        // arquivo vazio
        fclose(fin);
        FILE *fout = fopen(saida, "wb");
        if (fout) fclose(fout);
        uint32_t c = calcular_adler32((uint8_t*)"", 0);
        if (c == checksum_original) {
            printf("Decompression Complete. Status: 100%% INTEGRAL (Adler-32 Checked).\n");
            return 0;
        } else {
            printf("CRITICAL VALIDATION ERROR: Output payload is corrupted.\n");
            return 2;
        }
    }

    BitReader br;
    br_init(&br, fin);
    uint64_t global_p = 0;

    while (global_p < total_original_len) {
        if (br.eof) { printf("Truncated block header.\n"); break; }
        int block_type = br_read_bit(&br);

        if (block_type == 1) {
            uint32_t decomp_len = br_read_bits(&br, 32);
            if (br.eof) { printf("Truncated decomp_len.\n"); free(out_buf); fclose(fin); return 1; }
            if (decomp_len == 0 || global_p + decomp_len > total_original_len) {
                printf("Invalid decomp_len.\n"); free(out_buf); fclose(fin); return 1;
            }
            uint64_t block_end_p = global_p + decomp_len;
            while (global_p < block_end_p) {
                int flag = br_read_bit(&br);
                if (br.eof) { printf("Truncated token.\n"); free(out_buf); fclose(fin); return 1; }
                if (flag == 0) {
                    out_buf[global_p++] = (uint8_t)br_read_bits(&br, 8);
                } else {
                    int use_large = br_read_bit(&br);
                    int bits_offset = use_large ? 14 : 9;
                    uint32_t len_code = br_read_bits(&br, 3);
                    uint32_t offset = br_read_bits(&br, bits_offset);
                    if (br.eof) { printf("Truncated match.\n"); free(out_buf); fclose(fin); return 1; }
                    if (offset == 0 || offset > global_p || offset > (uint32_t)(WS_LARGE + 1)) {
                        printf("CRITICAL DECOMPRESSION GUARD: Pointer underflow blocked!\n");
                        free(out_buf); fclose(fin); return 1;
                    }
                    uint32_t ml = (len_code < 7) ? (len_code + 3) : (br_read_bits(&br, 8) + 3);
                    if (ml < MIN_MATCH || ml > MAX_MATCH) {
                        printf("Invalid match length.\n"); free(out_buf); fclose(fin); return 1;
                    }
                    if (global_p + ml > block_end_p) {
                        printf("Match overruns block.\n"); free(out_buf); fclose(fin); return 1;
                    }
                    uint64_t start_pos = global_p - offset;
                    for (uint32_t i = 0; i < ml; i++) {
                        out_buf[global_p] = out_buf[start_pos + i];
                        global_p++;
                    }
                }
            }
            // sem br_align aqui: proximo header comeca imediatamente (bitstream continuo)
        } else {
            // bloco stored: alinha e le bytes crus
            br_align(&br);
            uint32_t raw_len = 0;
            if (fread(&raw_len, sizeof(uint32_t), 1, fin) != 1) {
                printf("Truncated stored header.\n"); free(out_buf); fclose(fin); return 1;
            }
            if (raw_len == 0 || global_p + raw_len > total_original_len) {
                printf("Invalid stored len.\n"); free(out_buf); fclose(fin); return 1;
            }
            if (fread(&out_buf[global_p], 1, raw_len, fin) != raw_len) {
                printf("Truncated stored payload.\n"); free(out_buf); fclose(fin); return 1;
            }
            global_p += raw_len;
            // realinha leitor apos fread (cnt ja 0, mas garante)
            br_align(&br);
        }
    }
    fclose(fin);

    uint32_t checksum_calculado = calcular_adler32(out_buf, (size_t)total_original_len);
    int sucesso = (checksum_original == checksum_calculado) && (global_p == total_original_len);

    if (sucesso) {
        FILE *fout = fopen(saida, "wb");
        if (!fout) { printf("Output execution crash.\n"); free(out_buf); return 1; }
        fwrite(out_buf, 1, (size_t)total_original_len, fout);
        fclose(fout);
        printf("Decompression Complete. Status: 100%% INTEGRAL (Adler-32 Checked).\n");
    } else {
        printf("CRITICAL VALIDATION ERROR: Output payload is corrupted.\n");
    }

    free(out_buf);
    return sucesso ? 0 : 2;
}

int main(int argc, char** argv) {
    if (argc != 4) {
        printf("Usage:\n  Compress:   %s -c <input> <output>\n  Decompress: %s -d <input> <output>\n", argv[0], argv[0]);
        return 1;
    }
    if (strcmp(argv[1], "-c") == 0) return executar_compressao(argv[2], argv[3]);
    if (strcmp(argv[1], "-d") == 0) return executar_descompressao(argv[2], argv[3]);
    printf("Invalid layout mode.\n");
    return 1;
}