tivrfoa · February 20, 2025 09:36 · tivrfoa · Feb 20, 2025 · tivrfoa · Feb 20, 2025
diff --git a/Grok3-hpack.c b/Grok3-hpack.c
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <stdint.h>
 #include <stdbool.h>

 // --- Data Structures ---

 // Header entry structure for static and dynamic tables
 typedef struct {
    char *name;
    char *value;
 } HeaderEntry;

 // Dynamic table structure
 typedef struct {
    HeaderEntry *entries; // entries[0] is most recent
    size_t size;
    size_t capacity;
    size_t current_size; // Total size in octets
    size_t max_size;     // Maximum size in octets
 } DynamicTable;

 // Huffman code entry
 typedef struct {
    uint8_t symbol;
    int length;
    uint32_t code; // Left-aligned code
 } HuffmanCode;

 // HPACK context for encoder and decoder
 typedef struct {
    DynamicTable dynamic_table;
 } HPACKContext;

 // --- Static Table (simplified, full table has 61 entries per RFC 7541) ---
 static const HeaderEntry static_table[] = {
    {":authority", ""},
    {":method", "GET"},
    {":method", "POST"},
    {":path", "/"},
    {":status", "200"}
 };
 static const size_t static_table_size = sizeof(static_table) / sizeof(static_table[0]);

 // --- Huffman Table (simplified, full table has 256 entries per RFC 7541 Appendix B) ---
 static const HuffmanCode huffman_table[] = {
    {'0', 5, 0b00000}, // 0
    {'1', 5, 0b00001}, // 1
    {'a', 5, 0b01010}, // 10
    {'b', 6, 0b111100}, // 60
    // Add remaining entries from RFC 7541 Appendix B
 };
 static const size_t huffman_table_size = sizeof(huffman_table) / sizeof(huffman_table[0]);

 // --- Dynamic Table Functions ---

 void init_dynamic_table(DynamicTable *table, size_t max_size) {
    table->entries = NULL;
    table->size = 0;
    table->capacity = 0;
    table->current_size = 0;
    table->max_size = max_size;
 }

 void free_dynamic_table(DynamicTable *table) {
    for (size_t i = 0; i < table->size; i++) {
        free(table->entries[i].name);
        free(table->entries[i].value);
    }
    free(table->entries);
 }

 void add_to_dynamic_table(DynamicTable *table, const char *name, const char *value) {
    size_t entry_size = 32 + strlen(name) + strlen(value); // 32 octets overhead per RFC 7541
    while (table->current_size + entry_size > table->max_size && table->size > 0) {
        // Evict oldest entry (at size-1)
        HeaderEntry old = table->entries[table->size - 1];
        table->current_size -= 32 + strlen(old.name) + strlen(old.value);
        free(old.name);
        free(old.value);
        table->size--;
    }
    if (table->size == table->capacity) {
        table->capacity = table->capacity ? table->capacity * 2 : 4;
        table->entries = realloc(table->entries, table->capacity * sizeof(HeaderEntry));
    }
    // Shift entries right to insert new entry at index 0
    memmove(&table->entries[1], &table->entries[0], table->size * sizeof(HeaderEntry));
    table->entries[0].name = strdup(name);
    table->entries[0].value = strdup(value);
    table->size++;
    table->current_size += entry_size;
 }

 HeaderEntry get_header_entry(const HPACKContext *ctx, size_t index) {
    HeaderEntry empty = {NULL, NULL};
    if (index < 1) return empty;
    index--; // Convert to 0-based indexing
    if (index < static_table_size) {
        return static_table[index];
    }
    size_t dyn_index = index - static_table_size;
    if (dyn_index < ctx->dynamic_table.size) {
        return ctx->dynamic_table.entries[dyn_index];
    }
    return empty;
 }

 // --- Bit Reader for Huffman Decoding ---

 typedef struct {
    const uint8_t *data;
    size_t pos;
    int bit_pos; // 0 to 7
 } BitReader;

 void bit_reader_init(BitReader *reader, const uint8_t *data) {
    reader->data = data;
    reader->pos = 0;
    reader->bit_pos = 0;
 }

 int read_bit(BitReader *reader) {
    if (reader->pos >= strlen((char *)reader->data)) return -1;
    int bit = (reader->data[reader->pos] >> (7 - reader->bit_pos)) & 1;
    reader->bit_pos++;
    if (reader->bit_pos == 8) {
        reader->pos++;
        reader->bit_pos = 0;
    }
    return bit;
 }

 // --- Bit Writer for Huffman Encoding ---

 typedef struct {
    uint8_t *buffer;
    size_t pos;
    int bit_pos; // 0 to 7
 } BitWriter;

 void bit_writer_init(BitWriter *writer, uint8_t *buffer) {
    writer->buffer = buffer;
    writer->pos = 0;
    writer->bit_pos = 0;
 }

 void write_bit(BitWriter *writer, int bit) {
    if (writer->bit_pos == 0) writer->buffer[writer->pos] = 0;
    writer->buffer[writer->pos] |= (bit << (7 - writer->bit_pos));
    writer->bit_pos++;
    if (writer->bit_pos == 8) {
        writer->pos++;
        writer->bit_pos = 0;
    }
 }

 void write_bits(BitWriter *writer, uint32_t value, int n) {
    for (int i = n - 1; i >= 0; i--) {
        write_bit(writer, (value >> i) & 1);
    }
 }

 // --- Integer Encoding/Decoding ---

 size_t decode_integer(const uint8_t *data, size_t *pos, size_t len, int N) {
    if (*pos >= len) return -1;
    uint8_t first = data[*pos];
    size_t value = first & ((1 << N) - 1);
    (*pos)++;
    if (value < (1 << N) - 1) return value;
    int m = 0;
    while (*pos < len) {
        uint8_t b = data[*pos];
        (*pos)++;
        value += (b & 0x7F) << m;
        if (!(b & 0x80)) return value;
        m += 7;
    }
    return -1; // Incomplete integer
 }

 void encode_integer(BitWriter *writer, size_t value, int N, uint8_t prefix) {
    size_t limit = (1 << N) - 1;
    if (value < limit) {
        write_bits(writer, prefix | value, 8);
    } else {
        write_bits(writer, prefix | limit, 8);
        value -= limit;
        while (value >= 128) {
            write_bits(writer, (value & 0x7F) | 0x80, 8);
            value >>= 7;
        }
        write_bits(writer, value, 8);
    }
 }

 // --- String Literal Encoding/Decoding ---

 char *decode_string(const uint8_t *data, size_t *pos, size_t len) {
    if (*pos >= len) return NULL;
    uint8_t first = data[*pos];
    bool huffman = first & 0x80;
    size_t str_len = decode_integer(data, pos, len, 7);
    if (str_len == -1 || *pos + str_len > len) return NULL;
    char *str = malloc(str_len + 1);
    if (huffman) {
        BitReader reader;
        bit_reader_init(&reader, data + *pos);
        for (size_t i = 0; i < str_len; i++) {
            uint32_t code = 0;
            int bits = 0;
            for (int l = 5; l <= 30; l++) { // Min/max lengths from Huffman table
                if (bits < l) {
                    int bit = read_bit(&reader);
                    if (bit < 0) {
                        free(str);
                        return NULL;
                    }
                    code = (code << 1) | bit;
                    bits++;
                }
                for (size_t j = 0; j < huffman_table_size; j++) {
                    if (huffman_table[j].length == l && huffman_table[j].code == code) {
                        str[i] = huffman_table[j].symbol;
                        goto found;
                    }
                }
            }
            free(str);
            return NULL; // No match
 found:;
        }
        *pos += str_len;
    } else {
        memcpy(str, data + *pos, str_len);
        *pos += str_len;
    }
    str[str_len] = '\0';
    return str;
 }

 void encode_string(BitWriter *writer, const char *str, bool use_huffman) {
    size_t len = strlen(str);
    if (use_huffman) {
        size_t bit_count = 0;
        for (size_t i = 0; i < len; i++) {
            for (size_t j = 0; j < huffman_table_size; j++) {
                if (huffman_table[j].symbol == str[i]) {
                    bit_count += huffman_table[j].length;
                    break;
                }
            }
        }
        size_t byte_count = (bit_count + 7) / 8;
        encode_integer(writer, byte_count, 7, 0x80); // Huffman flag set
        for (size_t i = 0; i < len; i++) {
            for (size_t j = 0; j < huffman_table_size; j++) {
                if (huffman_table[j].symbol == str[i]) {
                    write_bits(writer, huffman_table[j].code, huffman_table[j].length);
                    break;
                }
            }
        }
        while (writer->bit_pos != 0) write_bit(writer, 1); // Pad with 1s
    } else {
        encode_integer(writer, len, 7, 0x00); // No Huffman
        for (size_t i = 0; i < len; i++) {
            write_bits(writer, str[i], 8);
        }
    }
 }

 // --- HPACK Decoder ---

 typedef struct {
    HeaderEntry *headers;
    size_t size;
    size_t capacity;
 } HeaderList;

 void init_header_list(HeaderList *list) {
    list->headers = NULL;
    list->size = 0;
    list->capacity = 0;
 }

 void add_header(HeaderList *list, const char *name, const char *value) {
    if (list->size == list->capacity) {
        list->capacity = list->capacity ? list->capacity * 2 : 4;
        list->headers = realloc(list->headers, list->capacity * sizeof(HeaderEntry));
    }
    list->headers[list->size].name = strdup(name);
    list->headers[list->size].value = strdup(value);
    list->size++;
 }

 void free_header_list(HeaderList *list) {
    for (size_t i = 0; i < list->size; i++) {
        free(list->headers[i].name);
        free(list->headers[i].value);
    }
    free(list->headers);
 }

 void init_hpack_context(HPACKContext *ctx, size_t max_size) {
    init_dynamic_table(&ctx->dynamic_table, max_size);
 }

 void free_hpack_context(HPACKContext *ctx) {
    free_dynamic_table(&ctx->dynamic_table);
 }

 int hpack_decode(HPACKContext *ctx, const uint8_t *data, size_t len, HeaderList *headers) {
    size_t pos = 0;
    while (pos < len) {
        uint8_t first = data[pos];
        if (first & 0x80) { // Indexed
            size_t index = decode_integer(data, &pos, len, 7);
            if (index == -1) return -1;
            HeaderEntry entry = get_header_entry(ctx, index);
            if (!entry.name) return -1;
            add_header(headers, entry.name, entry.value);
        } else if ((first & 0xC0) == 0x40) { // Literal with Incremental Indexing
            size_t index = decode_integer(data, &pos, len, 6);
            if (index == -1) return -1;
            char *name, *value;
            if (index == 0) {
                name = decode_string(data, &pos, len);
                if (!name) return -1;
            } else {
                HeaderEntry entry = get_header_entry(ctx, index);
                if (!entry.name) return -1;
                name = strdup(entry.name);
            }
            value = decode_string(data, &pos, len);
            if (!value) {
                free(name);
                return -1;
            }
            add_header(headers, name, value);
            add_to_dynamic_table(&ctx->dynamic_table, name, value);
            free(name);
            free(value);
        } else if ((first & 0xF0) == 0x00) { // Literal without Indexing
            size_t index = decode_integer(data, &pos, len, 4);
            if (index == -1) return -1;
            char *name, *value;
            if (index == 0) {
                name = decode_string(data, &pos, len);
                if (!name) return -1;
            } else {
                HeaderEntry entry = get_header_entry(ctx, index);
                if (!entry.name) return -1;
                name = strdup(entry.name);
            }
            value = decode_string(data, &pos, len);
            if (!value) {
                free(name);
                return -1;
            }
            add_header(headers, name, value);
            free(name);
            free(value);
        } else if ((first & 0xE0) == 0x20) { // Size Update
            size_t new_size = decode_integer(data, &pos, len, 5);
            if (new_size == -1) return -1;
            ctx->dynamic_table.max_size = new_size;
            while (ctx->dynamic_table.current_size > new_size && ctx->dynamic_table.size > 0) {
                HeaderEntry old = ctx->dynamic_table.entries[ctx->dynamic_table.size - 1];
                ctx->dynamic_table.current_size -= 32 + strlen(old.name) + strlen(old.value);
                free(old.name);
                free(old.value);
                ctx->dynamic_table.size--;
            }
        } else {
            return -1; // Unknown instruction
        }
    }
    return 0;
 }

 // --- HPACK Encoder ---

 int hpack_encode(HPACKContext *ctx, const HeaderList *headers, uint8_t **output, size_t *output_len) {
    size_t buffer_size = 1024; // Initial guess
    *output = malloc(buffer_size);
    BitWriter writer;
    bit_writer_init(&writer, *output);
    for (size_t i = 0; i < headers->size; i++) {
        const char *name = headers->headers[i].name;
        const char *value = headers->headers[i].value;
        bool indexed = false;
        size_t index = 0;
        // Check static table
        for (size_t j = 0; j < static_table_size; j++) {
            if (strcmp(static_table[j].name, name) == 0 && strcmp(static_table[j].value, value) == 0) {
                indexed = true;
                index = j + 1;
                break;
            }
        }
        // Check dynamic table
        if (!indexed) {
            for (size_t j = 0; j < ctx->dynamic_table.size; j++) {
                if (strcmp(ctx->dynamic_table.entries[j].name, name) == 0 &&
                    strcmp(ctx->dynamic_table.entries[j].value, value) == 0) {
                    indexed = true;
                    index = static_table_size + j + 1;
                    break;
                }
            }
        }
        if (indexed) {
            encode_integer(&writer, index, 7, 0x80);
        } else {
            // Use literal with incremental indexing
            encode_integer(&writer, 0, 6, 0x40);
            encode_string(&writer, name, true);  // Use Huffman
            encode_string(&writer, value, true); // Use Huffman
            add_to_dynamic_table(&ctx->dynamic_table, name, value);
        }
        // Resize output buffer if needed
        size_t bytes_used = writer.pos + (writer.bit_pos > 0 ? 1 : 0);
        if (bytes_used >= buffer_size) {
            buffer_size *= 2;
            *output = realloc(*output, buffer_size);
            writer.buffer = *output;
        }
    }
    *output_len = writer.pos + (writer.bit_pos > 0 ? 1 : 0);
    return 0;
 }

 // --- Main Function for Testing ---

 int main() {
    HPACKContext ctx;
    init_hpack_context(&ctx, 4096); // Default max size

    HeaderList headers;
    init_header_list(&headers);
    add_header(&headers, ":method", "GET");
    add_header(&headers, ":path", "/index.html");

    uint8_t *encoded;
    size_t encoded_len;
    if (hpack_encode(&ctx, &headers, &encoded, &encoded_len) != 0) {
        printf("Encoding failed\n");
        return 1;
    }
    printf("Encoded %zu headers into %zu bytes\n", headers.size, encoded_len);

    HPACKContext decode_ctx;
    init_hpack_context(&decode_ctx, 4096);
    HeaderList decoded_headers;
    init_header_list(&decoded_headers);
    if (hpack_decode(&decode_ctx, encoded, encoded_len, &decoded_headers) != 0) {
        printf("Decoding failed\n");
        return 1;
    }
    printf("Decoded headers:\n");
    for (size_t i = 0; i < decoded_headers.size; i++) {
        printf("%s: %s\n", decoded_headers.headers[i].name, decoded_headers.headers[i].value);
    }

    free(encoded);
    free_header_list(&headers);
    free_header_list(&decoded_headers);
    free_hpack_context(&ctx);
    free_hpack_context(&decode_ctx);
    return 0;
 }
diff --git a/Grok3-think-hpack-answer.md b/Grok3-think-hpack-answer.md
diff --git a/Grok3-thought-process-2m55s.txt b/Grok3-thought-process-2m55s.txt
 To view keyboard shortcuts, press question mark
 View keyboard shortcuts
 Write an HPACK implementation in C
 So I have this task: write an HPACK implementation in C. HPACK is the header compression format used in HTTP/2, right? It's designed to reduce the size of HTTP headers, which can be pretty redundant and large, especially with things like cookies and user agents.
 First, I need to understand what HPACK does exactly. From what I recall, HPACK uses a combination of static and dynamic tables to represent common headers and their values. It also employs Huffman coding for string compression. So, my implementation needs to handle these components.
 Let me start by outlining the main parts of HPACK:

    Static Table: This is a predefined table of common header fields and values. It's shared between the encoder and decoder and doesn't change.
    Dynamic Table: This is a table that both the encoder and decoder maintain. It starts empty and gets updated as headers are sent and received. It's essentially a sliding window of recently used headers.
    Header Encoding: Headers can be encoded in different ways:
        Indexed: Referencing an entry in the static or dynamic table.
        Literal with indexing: Adding a new entry to the dynamic table.
        Literal without indexing: Not adding to the dynamic table.
        Literal never indexed: For sensitive headers that shouldn't be stored.
    Huffman Coding: Strings can be compressed using a predefined Huffman code table.

 So, in C, I need to implement both the encoder and the decoder. But since the task is to write an HPACK implementation, I think I need to cover both sides.
 Let me think about the data structures I'll need.
 For the static table, since it's predefined and doesn't change, I can probably hardcode it as an array of structures, where each structure holds the header name and possibly a value.
 For the dynamic table, it needs to be a dynamic data structure since it can grow and shrink. It's typically implemented as a circular buffer with a fixed maximum size. When the table is full, adding a new entry evicts the oldest one.
 I also need to handle the Huffman coding. That means I need the Huffman code table, and functions to encode and decode strings using it.
 Alright, let's start with the static table. I need to know what entries are in it. According to the HPACK specification (RFC 7541), the static table has 61 entries, including common headers like :method, :scheme, :path, and various standard HTTP headers.
 I should define a structure for the table entries. Something like:
 c

 typedef struct {
    const char *name;
    const char *value;
 } HeaderEntry;

 Then, I can define the static table as an array of HeaderEntry.
 Wait, but some entries in the static table have only a name and no value, like :method, while others have both, like :method GET. Actually, looking back at the spec, the static table has entries with both name and value, and some with only name.
 For example:

    Index 1: :authority
    Index 2: :method GET
    Index 3: :method POST
    Index 4: :path /
    And so on.

 So, my HeaderEntry should accommodate both cases. Maybe I can have value as NULL for entries that don't have a value.
 Wait, but in the spec, even the entries like :method have a value, like GET or POST. Wait, actually, looking at the spec, entries 1 to 61 are listed, and some have values, some don't. Wait, actually, upon closer inspection, in the static table, some entries have a value, like index 2 is ":method" "GET", index 3 is ":method" "POST", index 8 is ":status" "200", etc., while others have only a name, like index 1 ":authority", index 4 ":path", but wait, index 4 is ":path" "/", so it does have a value.
 Wait, actually, checking the spec again, all entries in the static table have both a name and a value, but for some, the value is an empty string. Wait, no, for example, index 1 is ":authority" with no value, but in the spec, it's listed as ":authority" "", meaning an empty string.
 Wait, actually, in the wire format, if an entry has an empty value, it means it's just the header name without a value. But in HTTP, headers always have a value, even if it's empty. Wait, actually, in HTTP, headers can have empty values.
 But in HPACK, the static table includes entries with specific values, like ":method" "GET", and also entries like ":path" "/", but also entries like ":authority" with an empty value, meaning it's just the header name.
 Wait, but in the context of HPACK, when you reference an entry with an empty value, it means you're sending the header name with an empty value, I think. But actually, in practice, for headers like :authority, you would send it with a literal value.
 Wait, perhaps it's better to think of the static table as having entries where some have a specific value, and others have an empty value, meaning they are meant to be used with literal values.
 But in any case, for my implementation, I can define the static table with entries that have both name and value, where value can be an empty string.
 So, I'll proceed with:
 c

 typedef struct {
    const char *name;
    const char *value;
 } HeaderEntry;

 static const HeaderEntry static_table[] = {
    { ":authority", "" },
    { ":method", "GET" },
    { ":method", "POST" },
    // ... and so on, up to index 61
 };

 I need to fill in all 61 entries according to the spec.
 Next, for the dynamic table, I need a data structure that can efficiently add and remove entries. Since it's a FIFO queue with a maximum size, I can use a circular buffer.
 But in C, managing a circular buffer with variable-sized entries is a bit tricky because headers can have different lengths. Wait, actually, the dynamic table stores header field representations, which are pairs of strings (name and value).
 So, I need to store pairs of strings. One way is to use a struct with two char pointers, but since the strings can be of varying lengths, I need to manage memory for them.
 Alternatively, I can use a single buffer to store all the strings consecutively, and have the HeaderEntry structs point into that buffer.
 But that might be complicated. Maybe it's simpler to use dynamic memory allocation for each string.
 So, for the dynamic table, I can have an array of HeaderEntry, where each HeaderEntry has dynamically allocated name and value.
 But in C, managing an array of structs with dynamic strings can be error-prone, especially with memory management.
 Another option is to use a linked list, but that might be less efficient for indexing.
 Wait, actually, in HPACK, the dynamic table is indexed, starting from 1, with 1 being the most recently added entry.
 Wait, actually, in the spec, the dynamic table is indexed starting from 1, with 1 being the oldest entry, and the highest index being the most recently added.
 Wait, no, wait: in the spec, the dynamic table is ordered with the newest entry at index 1, and older entries at higher indices.
 Wait, actually, let's check the spec.
 Upon checking, in RFC 7541, section 2.3.2: "The dynamic table is a FIFO queue: entries are added to the end of the table, and removed from the beginning when the table is full."
 Wait, but in terms of indexing, in section 2.3.3: "The header field representation uses a zero-based indexing, with the first entry in the header table being at index 0."
 Wait, actually, in HPACK, the header table is the concatenation of the static table and the dynamic table. The static table has indices 1 to 61, and the dynamic table starts at index 62 onwards.
 Wait, no: actually, the header table is considered as the static table followed by the dynamic table. So index 1 to 61 are static, and index 62 onwards are dynamic.
 But within the dynamic table, the entries are ordered with the most recently added entry at the lowest index among the dynamic table entries.
 Wait, specifically, when a new entry is added to the dynamic table, it is inserted at index 62, and older entries are shifted up, with the oldest entry being at the highest index, and if the table is full, the oldest entry is removed.
 Wait, actually, let's clarify: in the spec, the dynamic table is a list where new entries are added at the beginning (index 1 of the dynamic table), and when the table is full, the oldest entries (at the end) are removed.
 But in the context of the entire header table, the static table is indices 1 to 61, and the dynamic table is indices 62 to 62 + k, where k is the number of entries in the dynamic table.
 Wait, actually, upon checking section 2.3.3: "The header table consists of the static table (see Section 2.3.1) followed by the dynamic table (see Section 2.3.2)."
 So, the header table is static table + dynamic table, with indices starting from 1.
 So, index 1 to 61 are static, and index 62 onwards are dynamic, with index 62 being the most recently added dynamic entry, index 63 the next, and so on, up to the oldest dynamic entry.
 Wait, actually, in the spec, it's the opposite: the dynamic table is ordered with the oldest entry first.
 Wait, let's read carefully.
 In section 2.3.2: "The dynamic table is initially empty. Entries are added to the dynamic table when header fields are encoded with the instructions defined in Section 6."
 And in section 6.1: "Indexed Header Field Representation", it refers to an index in the header table.
 Then, in section 6.2: "Literal Header Field Representation", when encoding with indexing, it says: "The header field is represented as a literal and added into the dynamic table."
 And in the decoding process: "Upon decoding, the header field is added to the dynamic table."
 So, when a literal header with indexing is decoded, it is added to the dynamic table.
 Now, regarding the order: in section 4.1: "Calculating Table Size", it mentions that the dynamic table is a list of header fields, and the size is the sum of the sizes of its entries.
 But it doesn't explicitly say the order. However, in the examples, it shows that new entries are added at the beginning.
 Wait, actually, in Appendix B, there's an example.
 In B.2, it shows the dynamic table after processing some headers, and the indices are such that the most recently added entry is at index 62, then 63, etc.
 Wait, let's see: in B.2.1, after processing the first header, the dynamic table has one entry at index 62.
 Then, after the second header, another entry is added at index 62, and the previous one is now at index 63.
 Wait, actually, in the example, it shows:
 After processing ":method: GET", which is in the static table, no change to dynamic table.
 Then, ":scheme: http", also in static table.
 Then, ":path: /", also in static table.
 Then, ":authority: www.example.com", which is a literal with indexing, so it's added to the dynamic table.
 So, after that, the dynamic table has one entry: ":authority: www.example.com" at index 62.
 Then, in B.2.2, another header set is processed, including "cache-control: private", which is a literal with indexing, so it's added to the dynamic table.
 So, now the dynamic table has "cache-control: private" at index 62, and ":authority: www.example.com" at index 63.
 Wait, actually, in the spec, it says: "The new entry is added to the dynamic table, increasing its size to 2."
 And in the figure, it shows:
 62: cache-control: private
 63: :authority: www.example.com
 Wait, so actually, new entries are added at the beginning of the dynamic table, so at the lowest index among the dynamic table entries.
 So, in the header table, which is static table (1-61) followed by dynamic table (62 onwards), within the dynamic table part, the entries are ordered with the most recently added at index 62, then the next at 63, and so on, with the oldest at the highest index.
 So, when a new entry is added, it's inserted at index 62, and all existing dynamic entries are shifted up by one index, and if the table exceeds its maximum size, the oldest entries are removed from the end.
 Wait, actually, in terms of implementation, it's like a list where new entries are inserted at the front, and old entries are removed from the back when the table is full.
 So, in C, I can implement the dynamic table as a list or an array where index 0 is the most recent entry, index 1 is the next, and so on.
 Then, when referencing an entry in the header table, for indices 1 to 61, it's the static table, and for indices 62 onwards, it's the dynamic table at position index - 62.
 Wait, more precisely, if the dynamic table has k entries, then index 62 corresponds to dynamic table entry 0 (most recent), index 63 to entry 1, up to index 61 + k to entry k-1 (oldest).
 So, in code, to get the entry for a given index:

    If index <= 61, it's static_table[index - 1]
    If index > 61, it's dynamic_table[index - 62]

 Assuming dynamic_table[0] is the most recent entry.
 Yes, that makes sense.
 So, for the dynamic table, I can use a dynamic array or a list that allows efficient insertion at the front and removal from the back.
 In C, I can use a resizable array, like a vector, but since C doesn't have built-in vectors, I'll need to manage it manually.
 Alternatively, I can use a linked list, but accessing by index would be O(n), which might be acceptable since the dynamic table size is typically small.
 But for efficiency, perhaps a resizable array is better.
 I can implement a simple vector of HeaderEntry, where each HeaderEntry has dynamically allocated name and value.
 So, something like:
 c

 typedef struct {
    char *name;
    char *value;
 } HeaderEntry;

 typedef struct {
    HeaderEntry *entries;
    size_t size;
    size_t capacity;
 } DynamicTable;

 Then, I need functions to initialize, add an entry at the front, remove an entry from the back, and access by index.
 Also, I need to keep track of the total size of the dynamic table, which is the sum of the sizes of the entries, where each entry's size is 32 + length of name + length of value.
 Wait, according to the spec, the size of an entry is the number of octets it would require to store in the dynamic table, which is approximately the sum of the lengths of name and value, plus 32 octets of overhead.
 So, in code, I need to maintain the current size, and when adding an entry, check if it exceeds the maximum size, and if so, evict entries from the back until it fits.
 Additionally, the maximum size can be updated by the SETTINGS_HEADER_TABLE_SIZE setting in HTTP/2.
 So, my DynamicTable struct should also have a max_size field, which can be updated.
 Wait, actually, the max_size is part of the decoder context, I think.
 Anyway, I'll need to handle that.
 Now, let's think about the encoder and decoder.
 For the encoder, it takes a list of headers and encodes them into a byte stream using HPACK.
 For the decoder, it takes a byte stream and decodes it into a list of headers.
 So, I need to implement both.
 Perhaps I can start with the decoder, as it's a bit more straightforward.
 For the decoder, I need to read the byte stream, interpret the instructions, and build the list of headers, while updating the dynamic table as necessary.
 The instructions are:

    Indexed Header Field: a single byte with the high bit set, followed by the index.
    Literal Header Field with Incremental Indexing: a byte with the high 2 bits set to 01, followed by the index or 0, then the literal value.
    Literal Header Field without Indexing: a byte with the high 4 bits set to 0000, followed by the literal name and value.
    Literal Header Field Never Indexed: similar, but with high 4 bits set to 0001.
    Dynamic Table Size Update: a byte with the high 3 bits set to 001, followed by the new size.

 So, I need to parse the byte stream according to these formats.
 For each instruction, I need to decode it, possibly add entries to the dynamic table, and output the corresponding header.
 Also, for literal values, they can be Huffman encoded or not, indicated by a bit.
 So, I need to handle Huffman decoding as well.
 Therefore, I need to implement the Huffman decoder.
 Similarly, for the encoder, I need to decide how to encode each header: whether to use indexing, literal with indexing, etc., and possibly use Huffman encoding for literals.
 But perhaps I can start with the decoder.
 First, let's think about the Huffman coding part.
 The HPACK spec defines a specific Huffman code table in Appendix B.
 I need to implement a Huffman decoder that can decode a bitstream using that table.
 In C, I can represent the Huffman tree or use a lookup table for efficiency.
 Since the alphabet is 256 symbols (bytes), and there are also some special symbols like EOS, but in HPACK, it's for encoding strings, so the symbols are bytes.
 Wait, actually, in HPACK, the Huffman code is used for encoding string literals, which are sequences of bytes, so the Huffman codes are for each byte in the string.
 The code table is given in the spec, with codes for each possible byte value 0 to 255, plus an EOS symbol, but in HPACK, the EOS is not used, I think.
 Actually, in section 5.2, it says: "The Huffman code is used to encode string literals in the HPACK format. The code is a canonical Huffman code, with codes assigned in order of increasing code length."
 And it provides the code table.
 So, to decode, I need to read bits from the input stream and traverse the Huffman tree until I reach a leaf, which corresponds to a symbol.
 Since it's a canonical Huffman code, I can implement an efficient decoder using a lookup table or by directly computing the symbol from the bit sequence.
 One common way is to use a table for the shorter codes and a tree for the longer ones.
 But for simplicity, since the maximum code length is 30 bits, I can read up to 30 bits and use a lookup table or a switch statement.
 Alternatively, I can build the Huffman tree and traverse it bit by bit.
 Perhaps building the tree is more straightforward.
 So, I can define a Huffman node structure, with left and right children, and a symbol if it's a leaf.
 Then, I can build the tree according to the code table.
 But actually, since it's a canonical code, I can use a more efficient representation.
 In a canonical Huffman code, the codes are assigned in such a way that for each length, the codes are consecutive integers.
 So, I can group the symbols by their code lengths and assign codes accordingly.
 For decoding, I can use a method where I read a certain number of bits, say L, and check if it corresponds to a code of length L, and if not, read more bits, and so on.
 Specifically, I can have an array of symbols for each code length, and for each length, I can check if the current bits match any code of that length.
 But perhaps the simplest way is to use a single large table where for each possible bit sequence up to the maximum length, I map it to the corresponding symbol and the number of bits consumed.
 But since the maximum length is 30 bits, a table of 2^30 entries is way too large.
 So, that's not feasible.
 Another way is to use multiple tables, one for each possible length, but that's still cumbersome.
 A better way is to use the property of canonical codes: for a given length L, all codes of length L are consecutive, and I can find the range for each length.
 So, I can read L bits, compute the numerical value, and see if it falls within the range for codes of length L, and if so, map it to the corresponding symbol.
 If not, I read more bits, and check for longer lengths.
 To make it efficient, I can precompute for each possible L, the minimum code value for that length, and the symbols in order.
 For example, I can have an array min_code[L] where min_code[L] is the smallest code of length L, and an array symbol[L][i] where i is the offset from min_code[L].
 Then, to decode, I can start with L = min_length, read L bits, compute the value, and check if value >= min_code[L], and if so, compute the offset = value - min_code[L], and if offset < number of symbols at length L, then the symbol is symbol[L][offset], and consume L bits.
 If not, increment L and read more bits, and so on, until I find a match or reach the maximum length.
 This is a standard way to decode canonical Huffman codes.
 So, I can implement that.
 First, I need the code table from the spec.
 The spec provides the codes in Appendix B, with the symbol, the code length, and the code value.
 Actually, in the spec, it's given as a table with symbol, length, and the code in binary.
 For example, symbol 48 ('0') has length 5, code 00000, symbol 49 ('1') has length 5, code 00001, and so on.
 So, I can transcribe that table into my code.
 Perhaps I can define an array of structs, where each struct has the symbol and its code length.
 Then, to build the decoder, I can sort the symbols by code length, and for each length, compute the min_code and the list of symbols.
 But actually, since it's canonical, the codes are assigned in order, so for each length, the symbols are in order, and the codes are consecutive.
 So, I can group the symbols by length, and for each length, have a list of symbols in the order they appear in the table.
 Then, for decoding, I can implement the algorithm I described.
 Alternatively, since the code is fixed, I can hardcode the decoding logic, but that might be error-prone.
 I think implementing the general canonical Huffman decoder is better.
 So, I'll need to:

    Define the code table: an array of {symbol, length} pairs.
    Sort or group them by length.
    For each length, compute the first code and the number of codes.

 But actually, in canonical codes, the first code for each length can be computed based on the number of codes at previous lengths.
 Specifically, I can assign codes starting from 0 for the shortest length, then for longer lengths, the first code is (previous first code + number of codes) << (length difference).
 But since the spec already provides the codes, I can use that.
 Wait, actually, in the spec, the codes are given, so I can use the code values directly.
 Wait, but in the table, the codes are given as binary strings, but for efficiency, I can convert them to integers.
 For example, for length 5, the codes start from 00000 (0) for '0', 00001 (1) for '1', etc.
 So, for length 5, the first code is 0, and there are several symbols with length 5.
 Then, for longer lengths, the codes continue.
 So, in code, I can have an array of symbols sorted by their code, and for each, their length.
 Then, for decoding, I can read bits, compute the value, and find the first symbol whose code <= value and has the corresponding length.
 But perhaps it's easier to use the method with min_code per length.
 Let me try to outline the decoder.
 First, I need to read bits from the input stream. Since the input is a byte stream, I need a way to read bits one by one.
 So, I'll need a bit reader.
 In C, I can implement a bit reader that keeps track of the current byte and the bit position.
 For example:
 c

 typedef struct {
    const uint8_t *data;
    size_t pos; // byte position
    int bit_pos; // bit position within the byte, 0 to 7
 } BitReader;

 void bit_reader_init(BitReader *reader, const uint8_t *data) {
    reader->data = data;
    reader->pos = 0;
    reader->bit_pos = 0;
 }

 int read_bit(BitReader *reader) {
    if (reader->bit_pos == 8) {
        reader->pos++;
        reader->bit_pos = 0;
    }
    int bit = (reader->data[reader->pos] >> (7 - reader->bit_pos)) & 1;
    reader->bit_pos++;
    return bit;
 }

 uint32_t read_bits(BitReader *reader, int n) {
    uint32_t value = 0;
    for (int i = 0; i < n; i++) {
        value = (value << 1) | read_bit(reader);
    }
    return value;
 }

 Something like that.
 Then, for the Huffman decoder, I can do something like:
 First, find the minimum and maximum code lengths.
 From the table, the shortest codes are length 5, and the longest are length 30.
 Wait, actually, checking the spec, the lengths range from 5 to 30 bits.
 So, I can loop from L = 5 to L = 30, read L bits, compute the value, and check if it corresponds to a code of length L.
 To do that, I need to know, for each L, what is the range of codes for that length.
 Since it's canonical, for each L, there is a first code, and then consecutive codes for the symbols of that length.
 So, I can precompute for each L, the first code value, and an array of symbols for that length.
 Then, when decoding, for each L from 5 to 30, read L bits, get value, and see if value - first_code[L] < num_symbols[L], and if so, the symbol is symbols[L][value - first_code[L]], and consume L bits.
 If not, continue to the next L.
 If I reach L = 30 and still no match, it's an error.
 So, to implement this, I need to group the symbols by their code lengths and compute the first_code for each length.
 But how do I get the first_code? In the spec, the codes are given, so I can find the smallest code for each length.
 For example, for length 5, the codes are 00000 for '0', 00001 for '1', etc., so first_code[5] = 0.
 Then, for the next length, say length 6, I need to find the smallest code.
 But actually, in canonical codes, the first code for length L is (first_code[L-1] + num_codes[L-1]) << 1, or something like that.
 Wait, more precisely, since the codes are left-aligned, for each length, the codes are consecutive starting from a certain value.
 Wait, in the HPACK code table, for length 5, codes are from 0 to, say, N5 - 1, then for length 6, from N5 to N5 + N6 - 1, but shifted left by 1, and so on.
 Wait, actually, in binary, for length L, the codes are the integer values from first_code[L] to first_code[L] + num_codes[L] - 1, and when comparing, I need to consider the first L bits.
 So, when I read L bits, the value is the integer represented by those L bits, and if it falls within first_code[L] to first_code[L] + num_codes[L] - 1, then the symbol is the corresponding one.
 Yes, so I can precompute first_code[L] and num_codes[L] and the list of symbols for each L.
 To compute first_code[L], I can sort the codes by length and then by value, and find the smallest code for each length.
 But since the table is already ordered, I can iterate through the table and group them.
 Wait, actually, in the HPACK spec, the code table is given in order of symbol, not in order of code.
 So, I need to collect all the {symbol, length, code} and sort them by length and then by code.
 But perhaps I can assume that for each length, the codes are consecutive.
 Wait, let's check the spec: in Appendix B, the table is given with symbol, length, and the code in binary.
 For example:
 symbol 48: length 5, code 00000
 symbol 49: length 5, code 00001
 /symbol 50: length 5, code 00010
 and so on, up to symbol 57: length 5, code 01001
 Then symbol 97: length 5, code 01010
 and so on.
 So, for length 5, the codes are from 00000 (0) to, say, for symbol 122, length 5, code 11111 (31), but wait, 5 bits can have 32 values, from 0 to 31.
 But in the table, for length 5, there are multiple symbols, like digits, letters, etc.
 Actually, counting, there are many symbols with length 5.
 Then, for longer lengths, there are fewer symbols.
 So, to implement, I can collect all symbols with their lengths, and for each length, find the smallest code value.
 But since the codes are assigned in order, I can assume that for each length, the codes are consecutive starting from a certain value.
 So, I can write a function to build the decoding tables.
 For example, I can have an array of lists, where each list corresponds to a length, and contains the symbols for that length in order.
 Then, I can compute first_code[L] as the code of the first symbol in the list for length L.
 But how do I get the code value? In the spec, the code is given as a binary string, but in code, I need to represent it as an integer.
 For example, for symbol '0', code 00000, which is 0, for '1', 00001, which is 1, etc.
 So, I can include the code value in the table.
 Perhaps I can define a struct:
 c

 typedef struct {
    uint8_t symbol;
    int length;
    uint32_t code; // the code value, left-aligned in 32 bits
 } HuffmanCode;

 Wait, actually, since the maximum length is 30, I can use uint32_t for the code, with the code bits in the most significant bits.
 For example, for length 5, code 00000, I can store it as 00000 << (32 - 5) = 00000 followed by 27 zeros.
 But in C, it's easier to store the code as the integer value of the first length bits.
 For example, for length 5, code 00000 is 0, 00001 is 1, etc.
 Then, when decoding, I can read L bits, get the value, and see if value >= first_code[L] and value < first_code[L] + num_codes[L], and if so, the symbol is symbols[L][value - first_code[L]].
 Yes, so I need to compute first_code[L] as the code of the first symbol with length L.
 So, to do that, I can sort the HuffmanCode array by length, then by code.
 But since the table in the spec is not sorted, I need to sort it in code.
 Alternatively, I can manually group them.
 But perhaps the easiest way is to define the HuffmanCode array in the order given in the spec, then sort it by length and then by code.
 In C, I can use qsort with a custom comparator.
 So, first, I need to define the HuffmanCode array.
 But typing all 256 entries would be tedious, and error-prone.
 Perhaps I can find a way to generate it or copy from somewhere.
 Actually, since it's a standard, maybe there are existing implementations or tables I can use.
 But for this exercise, I'll assume I need to implement it from scratch, so I'll have to type the table.
 Wait, perhaps I can write a script to parse the spec and generate the C code, but that's overkill.
 Alternatively, I can look for existing HPACK implementations in C and see how they handle it.
 But since this is a learning exercise, I'll try to do it myself.
 So, let's say I define:
 c

 static const HuffmanCode huffman_table[] = {
    {48, 5, 0b00000},
    {49, 5, 0b00001},
    {50, 5, 0b00010},
    // and so on
 };

 But in the spec, the code is given as a binary string, like "00000|", but in C, I can write it as an integer.
 For example, for length 5, code "00000" is 0, "00001" is 1, etc.
 But actually, since the codes are left-aligned, for length L, the code is the value shifted to the left.
 But in the decoding algorithm, it's easier to think of the code as the integer value of the first L bits.
 So, for length L, the code value is between 0 and (1<<L) - 1.
 So, I can store the code as a uint32_t, with the value being the code bits.
 Then, when sorting, I can sort by length, then by code value.
 So, I'll define the array with symbol, length, and code value.
 For example:
 c

 static const HuffmanCode huffman_table[] = {
    {48, 5, 0}, // '0'
    {49, 5, 1}, // '1'
    {50, 5, 2}, // '2'
    // ...
    {97, 5, 10}, // 'a', assuming code 01010 is 10 in decimal
    // and so on
 };

 I need to fill in all 256 symbols.
 Once I have that, I can sort the array by length, then by code.
 Then, I can build the decoding tables.
 For example, I can have:
 c

 typedef struct {
    int min_length;
    int max_length;
    uint32_t *first_code; // array of size max_length - min_length + 1
    uint8_t **symbols; // array of arrays, symbols[L - min_length] is the array of symbols for length L
 } HuffmanDecoder;

 Then, to build it, I can:

    Find min_length and max_length from the table.
    Allocate first_code and symbols arrays.
    Sort the huffman_table by length, then by code.
    Then, iterate through the sorted table, and for each length, set first_code[L] to the code of the first symbol with that length, and collect the symbols.

 So, yes, that should work.
 Then, for decoding, I can do:
 c

 uint8_t huffman_decode(BitReader *reader, const HuffmanDecoder *decoder) {
    uint32_t value = 0;
    int bits_read = 0;
    for (int L = decoder->min_length; L <= decoder->max_length; L++) {
        if (bits_read < L) {
            int bit = read_bit(reader);
            value = (value << 1) | bit;
            bits_read++;
        }
        int idx = L - decoder->min_length;
        uint32_t fc = decoder->first_code[idx];
        if (value >= fc && value < fc + decoder->num_codes[idx]) {
            int offset = value - fc;
            return decoder->symbols[idx][offset];
        }
    }
    // error: no symbol found
    return -1;
 }

 Wait, almost, but in the loop, I need to read bits until I have L bits, but since I may need to read more bits for longer codes, I need to accumulate the value.
 Actually, in the code above, it's almost correct, but I need to make sure that for each L, I have exactly L bits in value.
 Wait, actually, since I read one bit at a time, and accumulate value, when L increases, value has more bits.
 So, for example, when L = 5, value has 5 bits, then for L = 6, I read one more bit, so value has 6 bits, and so on.
 Yes, so in the code above, it should work.
 Wait, but in C, when I shift value left, I need to make sure it doesn't overflow, but since max L is 30, and uint32_t can hold 32 bits, it's fine.
 So, yes, that should work.
 So, I need to implement the HuffmanDecoder building function.
 But first, I need the huffman_table.
 Since typing all 256 entries is tedious, perhaps I can find a way to generate it.
 Alternatively, for now, I can assume I have the table, and implement the rest.
 Later, I can fill in the table.
 So, let's say I have static const HuffmanCode huffman_table[256], with the symbols and their lengths and codes.
 Then, I can write a function to build the decoder.
 For example:
 c

 void build_huffman_decoder(HuffmanDecoder *decoder, const HuffmanCode *table, size_t table_size) {
    // First, find min and max lengths
    int min_length = INT_MAX;
    int max_length = 0;
    for (size_t i = 0; i < table_size; i++) {
        if (table[i].length < min_length) min_length = table[i].length;
        if (table[i].length > max_length) max_length = table[i].length;
    }
    decoder->min_length = min_length;
    decoder->max_length = max_length;
    int num_lengths = max_length - min_length + 1;
    decoder->first_code = malloc(num_lengths * sizeof(uint32_t));
    decoder->num_codes = malloc(num_lengths * sizeof(size_t));
    decoder->symbols = malloc(num_lengths * sizeof(uint8_t*));
    // Sort the table by length, then by code
    // For simplicity, asumemos que la tabla ya está ordenada, o puedo copiar y ordenar
    // Actually, let's copy and sort
    HuffmanCode *sorted_table = malloc(table_size * sizeof(HuffmanCode));
    memcpy(sorted_table, table, table_size * sizeof(HuffmanCode));
    qsort(sorted_table, table_size, sizeof(HuffmanCode), compare_huffman_code);
    // where compare_huffman_code is a function that compares first by length, then by code
    // Now, group by length
    size_t index = 0;
    for (int L = min_length; L <= max_length; L++) {
        int idx = L - min_length;
        // Find the number of symbols with length L
        size_t count = 0;
        while (index < table_size && sorted_table[index].length == L) {
            count++;
            index++;
        }
        decoder->num_codes[idx] = count;
        if (count > 0) {
            decoder->first_code[idx] = sorted_table[index - count].code;
            decoder->symbols[idx] = malloc(count * sizeof(uint8_t));
            for (size_t i = 0; i < count; i++) {
                decoder->symbols[idx][i] = sorted_table[index - count + i].symbol;
            }
        } else {
            decoder->first_code[idx] = 0; // or some invalid value
            decoder->symbols[idx] = NULL;
        }
    }
    free(sorted_table);
 }

 Something like that.
 Then, I need to define the compare_huffman_code function:
 c

 int compare_huffman_code(const void *a, const void *b) {
    const HuffmanCode *ha = (const HuffmanCode*)a;
    const HuffmanCode *hb = (const HuffmanCode*)b;
    if (ha->length != hb->length) return ha->length - hb->length;
    return ha->code - hb->code;
 }

 Yes, so that should work.
 So, with this, I can build the HuffmanDecoder, and then use it to decode strings.
 For encoding, similarly, I can have a table for encoding, but since the task is to implement HPACK, I'll need both encoding and decoding.
 But for now, let's focus on the decoder.
 So, back to the HPACK decoder.
 I need to read the byte stream, interpret the instructions, and decode the headers.
 First, I need to handle the different types of instructions.
 Let's recall the formats:

    Indexed Header Field: integer representation with the high bit set, i.e., 1 followed by the index encoded as a 7-bit integer.
    Literal Header Field with Incremental Indexing: 01 followed by 6-bit index or 0, then literal value.

 Wait, more precisely, it's 01 followed by N (where N is the number of bits for the index), and if the index is 0, then it's followed by the literal header name.
 Wait, actually, in the spec, section 6.2.1: "Literal Header Field with Incremental Indexing", it's represented as:

    First byte: 01 followed by 6 bits for the index prefix. If the index is 0, it's followed by the header name as a literal string, then the value as a literal string.
    If the index is not 0, it's the index of the header name in the table, followed by the value as a literal string.

 Similarly for other literal representations.
 Also, there's the dynamic table size update: 001 followed by 5 bits for the size.
 So, to decode, I need to read the first byte, look at the prefix, and decide what to do.
 For example:

    If the first byte has the high bit set (i.e., >= 128), it's an indexed header field, and the index is encoded in the remaining 7 bits, or more if it's a multi-byte integer.
    If the first byte has the high 2 bits set to 01, it's a literal with incremental indexing, and the next 6 bits are the index prefix.
    If the first byte has the high 4 bits set to 0000, it's a literal without indexing.
    If the first byte has the high 4 bits set to 0001, it's a literal never indexed.
    If the first byte has the high 3 bits set to 001, it's a dynamic table size update.

 So, I can write a function to decode one header field representation.
 For that, I need to read bytes from the stream, interpret the instruction, and based on that, decode the header and possibly update the dynamic table.
 Also, for literal strings, they can be Huffman encoded or not, indicated by a bit.
 So, let's outline the decoder.
 First, I need a context for the decoder, which includes the dynamic table and the current max size.
 So, something like:
 c

 typedef struct {
    DynamicTable dynamic_table;
    size_t max_table_size;
    // perhaps other state
 } HPACKDecoder;

 Then, I need a function to initialize it, and a function to decode a header block.
 For decoding, I need to read the byte stream and produce a list of headers.
 So, perhaps:
 c

 int hpack_decode(HPACKDecoder *decoder, const uint8_t *data, size_t len, HeaderList *headers) {
    BitReader reader;
    bit_reader_init(&reader, data);
    // actually, since HPACK is byte-aligned except for Huffman coding, I can use a byte reader mostly
    // but for Huffman, I need bits
    // perhaps I can use a byte reader and switch to bit reader when needed
    // but for simplicity, maybe use a bit reader throughout, but since most operations are byte-aligned, it's inefficient
    // alternatively, I can use a byte reader and handle Huffman separately
    // let's try with a byte reader
    size_t pos = 0;
    while (pos < len) {
        uint8_t first_byte = data[pos];
        if (first_byte & 0x80) { // indexed
            // read index
            size_t index = decode_integer(data, &pos, len, 7);
            if (index == 0) {
                // error
            }
            HeaderEntry entry = get_header_entry(decoder, index);
            add_header(headers, entry.name, entry.value);
        } else if ((first_byte & 0xC0) == 0x40) { // literal with incremental indexing
            size_t index = decode_integer(data, &pos, len, 6);
            char *name;
            if (index == 0) {
                name = decode_literal_string(data, &pos, len);
            } else {
                HeaderEntry entry = get_header_entry(decoder, index);
                name = entry.name;
            }
            char *value = decode_literal_string(data, &pos, len);
            add_header(headers, name, value);
            // add to dynamic table
            add_to_dynamic_table(&<|control513|>

 decoder->dynamic_table, name, value);
        } else if ((first_byte & 0xF0) == 0x00) { // literal without indexing
            // similar to above, but don't add to dynamic table
        } else if ((first_byte & 0xF0) == 0x10) { // literal never indexed
            // similar
        } else if ((first_byte & 0xE0) == 0x20) { // dynamic table size update
            size_t new_size = decode_integer(data, &pos, len, 5);
            set_max_table_size(&decoder->dynamic_table, new_size);
        } else {
            // error
        }
    }
    return 0;
 }

 Wait, this is a rough sketch.
 I need to implement decode_integer, which decodes an integer with a given prefix size.
 In HPACK, integers are encoded with a prefix, where the first byte has the prefix bits, and if the value doesn't fit, there are continuation bytes.
 The decode_integer function can be implemented as per the spec.
 Similarly, decode_literal_string needs to read the string length, which is an integer with prefix 7 bits, and then read that many bytes, and if the Huffman bit is set, decode it using Huffman.
 So, I need to implement those helper functions.
 Let me first implement decode_integer.
 According to the spec, section 5.1, integer representation starts with the N-bit prefix, and if the value is less than 2^N - 1, it's represented in the prefix, else, it's followed by one or more bytes with the high bit set, and the value is encoded in base 128.
 So, in code:
 c

 size_t decode_integer(const uint8_t *data, size_t *pos, size_t len, int N) {
    if (*pos >= len) return -1; // error
    uint8_t first = data[*pos];
    size_t value = first & ((1 << N) - 1);
    (*pos)++;
    if (value < (1 << N) - 1) return value;
    int M = 0;
    while (*pos < len) {
        uint8_t b = data[*pos];
        (*pos)++;
        value += (b & 0x7F) << M;
        if ((b & 0x80) == 0) return value;
        M += 7;
    }
    return -1; // error: incomplete integer
 }

 Something like that.
 Similarly, for literal strings, they are prefixed with an integer representing the length, with N=7, and the high bit of the first byte indicates if Huffman encoding is used.
 So, decode_literal_string can be:
 c

 char *decode_literal_string(const uint8_t *data, size_t *pos, size_t len) {
    if (*pos >= len) return NULL;
    uint8_t first = data[*pos];
    int huffman = first & 0x80;
    size_t str_len = decode_integer(data, pos, len, 7);
    if (str_len == -1 || *pos + str_len > len) return NULL;
    char *str = malloc(str_len + 1);
    if (huffman) {
        // decode Huffman
        BitReader reader;
        bit_reader_init(&reader, data + *pos);
        size_t decoded_len = 0;
        while (decoded_len < str_len) {
            uint8_t symbol = huffman_decode(&reader, &huffman_decoder);
            if (symbol == -1) {
                free(str);
                return NULL;
            }
            str[decoded_len++] = symbol;
        }
        // need to handle padding bits
        // according to spec, the Huffman encoded string must be padded with EOS bits to byte boundary
        // but in decoding, I just need to decode until I have str_len symbols
    } else {
        memcpy(str, data + *pos, str_len);
    }
    *pos += str_len;
    str[str_len] = '\0';
    return str;
 }

 Wait, almost, but for Huffman, since it's bit-aligned, I need to read bits until I have decoded str_len symbols, and then skip to the next byte boundary.
 But in the code above, it's approximate.
 Actually, in HPACK, for Huffman encoded strings, the encoded data is padded with the EOS symbol's code to the next byte boundary, but when decoding, I just need to decode exactly str_len symbols, and the padding should be ignored.
 So, in the decoder, I can decode symbol by symbol until I have str_len symbols, and then the reader should be at the end of the encoded data.
 But since the padding is with EOS, and EOS is not a valid symbol in the string, if I encounter EOS before decoding str_len symbols, it's an error.
 But in practice, since the encoder pads with EOS, the decoder should decode exactly str_len symbols without hitting EOS.
 So, in code, I can decode str_len symbols, and if during decoding I hit EOS or an invalid code, it's an error.
 But in the Huffman code table, EOS is not used, so if I decode a symbol that is not in the table, it's an error.
 Wait, actually, in the HPACK Huffman code, all 256 byte values are represented, so every code corresponds to a valid symbol, except if the code is longer than necessary, but since it's a complete code, every prefix is used.
 Wait, actually, since it's a complete Huffman code, every infinite bit sequence will eventually match a symbol, but in practice, since the encoded data is padded to byte boundary, and the decoder knows str_len, it can stop after decoding str_len symbols.
 So, in the code above, it's basically correct: decode str_len symbols using the Huffman decoder, and then the bit reader should be at the end of the encoded data.
 Then, I need to advance *pos to the next byte boundary.
 Wait, actually, since the bit reader keeps track of the byte position, after decoding str_len symbols, I can set *pos to reader.pos + (reader.bit_pos > 0 ? 1 : 0), or something like that.
 But perhaps it's simpler to calculate the number of bytes consumed by the Huffman encoded string.
 But since the encoding is bit-aligned, it's tricky.
 Alternatively, I can have the huffman_decode function return the number of bits consumed, but since it's variable, it's not straightforward.
 Wait, actually, for each symbol, the number of bits consumed is the length of its code, but since I'm decoding symbol by symbol, I can keep track of the total bits consumed.
 For example, I can modify huffman_decode to return both the symbol and the number of bits consumed.
 But in the standard Huffman decoding algorithm, when I match a symbol, I know how many bits were consumed.
 So, in the loop, I can accumulate the bits consumed.
 Wait, let's say I modify the huffman_decode function to take a pointer to bits_consumed.
 But since it's a loop inside, it's not direct.
 Alternatively, I can have a separate function to decode a string.
 Perhaps it's better to have a function like:
 c

 int huffman_decode_string(const uint8_t *data, size_t encoded_len, char *output, size_t output_len) {
    BitReader reader;
    bit_reader_init(&reader, data);
    size_t decoded = 0;
    while (decoded < output_len) {
        uint8_t symbol = huffman_decode(&reader, &huffman_decoder);
        if (symbol == -1) return -1;
        output[decoded++] = symbol;
    }
    // check if we've consumed exactly the encoded_len bytes
    size_t bytes_consumed = reader.pos;
    if (reader.bit_pos > 0) bytes_consumed++;
    if (bytes_consumed != encoded_len) return -1;
    return 0;
 }

 But actually, since the encoded data may have padding, it's okay if bytes_consumed <= encoded_len, as long as the decoded symbols are exactly output_len.
 But in HPACK, the encoded length is given, and the decoder should consume exactly that many bytes, including padding.
 So, after decoding output_len symbols, the bit reader should have consumed a number of bits that, when rounded up to bytes, equals encoded_len.
 So, I can check that.
 For example:
 c

 size_t bits_consumed = reader.pos * 8 + reader.bit_pos;
 size_t bytes_needed = (bits_consumed + 7) / 8;
 if (bytes_needed != encoded_len) return -1;

 But actually, since the encoder pads to byte boundary, bytes_needed should be equal to encoded_len.
 Wait, more precisely, the encoded data is exactly encoded_len bytes, and the Huffman codes are such that after decoding output_len symbols, the bits consumed should be less than or equal to encoded_len * 8, and the remaining bits should be the padding.
 But in practice, since the padding is with EOS, which is a valid code, but in HPACK, the decoder should not decode beyond the specified length, so it should stop after decoding output_len symbols, and the remaining bits are ignored.
 So, in code, I can decode exactly output_len symbols, and then the bit reader has advanced to some position, and I can set *pos += encoded_len, since the encoded string occupies encoded_len bytes.
 Wait, yes, that's probably the simplest way: decode output_len symbols from the bit stream, and then advance *pos by encoded_len bytes.
 As long as the Huffman decoder doesn't run out of bits before decoding output_len symbols, it's okay.
 If it does, it's an error.
 So, in the decode_literal_string function, I can do:
 c

 char *decode_literal_string(const uint8_t *data, size_t *pos, size_t len) {
    if (*pos >= len) return NULL;
    uint8_t first = data[*pos];
    int huffman = first & 0x80;
    size_t str_len = decode_integer(data, pos, len, 7);
    if (str_len == -1 || *pos + str_len > len) return NULL;
    char *str = malloc(str_len + 1);
    if (huffman) {
        // decode Huffman
        BitReader reader;
        bit_reader_init(&reader, data + *pos);
        for (size_t i = 0; i < str_len; i++) {
            uint8_t symbol = huffman_decode(&reader, &huffman_decoder);
            if (symbol == -1) {
                free(str);
                return NULL;
            }
            str[i] = symbol;
        }
        // advance *pos by str_len bytes
        *pos += str_len;
    } else {
        memcpy(str, data + *pos, str_len);
        *pos += str_len;
    }
    str[str_len] = '\0';
    return str;
 }

 Yes, so in this way, for Huffman encoded strings, I decode exactly str_len symbols from the bit stream starting at data + *pos, and then advance *pos by str_len bytes, since the encoded data is str_len bytes long.
 This assumes that the Huffman encoding of str_len symbols fits exactly within str_len bytes, including padding.
 If during decoding, I can't decode str_len symbols, it's an error.
 Similarly, for the non-Huffman case, it's just copying the bytes.
 So, with this, I can implement the decode_literal_string function.
 Now, back to the main decoder, I need to handle the different instruction types.
 Also, I need to implement the dynamic table management: adding entries, evicting when the size exceeds max_size, etc.
 For that, I need to calculate the size of each entry, which is 32 + length of name + length of value.
 So, when adding an entry, I need to check if the new size would exceed max_size, and if so, evict entries from the back until it fits.
 Also, for the indexed representation, I need to get the entry from the header table, which is either static or dynamic.
 So, I can implement a function like:
 c

 HeaderEntry get_header_entry(const HPACKDecoder *decoder, size_t index) {
    if (index <= 61) {
        return static_table[index - 1];
    } else {
        size_t dyn_index = index - 62;
        if (dyn_index < decoder->dynamic_table.size) {
            return decoder->dynamic_table.entries[decoder->dynamic_table.size - 1 - dyn_index];
            // since dynamic_table[0] is the most recent, which is index 62
            // wait, actually, if dynamic_table[0] is the most recent, then index 62 is dynamic_table[0], index 63 is dynamic_table[1], etc.
            // so return decoder->dynamic_table.entries[dyn_index]
            // assuming dynamic_table.entries[0] is the oldest, entries[size-1] is the most recent
            // wait, earlier I thought of having entries[0] as the most recent
            // let's clarify
            // in the spec, the dynamic table is ordered with the newest entry at the lowest index in the dynamic table part
            // so in the header table, index 62 is the most recent dynamic entry, index 63 is the next, etc.
            // so if I have dynamic_table.entries[0] as the most recent, then for index = 62, dyn_index = 0, so entries[0], for index = 63, dyn_index = 1, entries[1], etc.
            // yes, so return decoder->dynamic_table.entries[dyn_index]
        } else {
            // error: invalid index
            return (HeaderEntry){NULL, NULL};
        }
    }
 }

 Wait, but in my earlierDynamicTable struct, I have entries as an array, with size and capacity, so I need to decide the order.
 Let's say I have entries[0] as the oldest entry, entries[size-1] as the most recent.
 Then, when adding a new entry, I insert it at the end, and when evicting, I remove from the beginning.
 But in that case, for get_header_entry, index 62 would be entries[size-1], index 63 would be entries[size-2], etc.
 So, to access dyn_index, it would be entries[size - 1 - dyn_index], but that might be confusing.
 Alternatively, I can have entries[0] as the most recent, entries[size-1] as the oldest, then when adding, I insert at the beginning, and when evicting, remove from the end.
 In C, inserting at the beginning of an array requires shifting all elements, which is O(n), but since the dynamic table size is typically small, it's acceptable.
 Alternatively, I can use a circular buffer, but that might be more complicated.
 For simplicity, I'll use a resizable array with entries[0] as the most recent.
 So, when adding a new entry, I can shift all existing entries to the right and place the new entry at entries[0], but that's inefficient.
 A better way is to use a vector and prepend the new entry, but in C, vectors are not built-in, so I need to manage it.
 Wait, actually, I can use realloc to grow the array, and then shift the elements.
 But perhaps it's easier to use a linked list, where I can insert at the front efficiently.
 But then accessing by index would be O(n), which is still acceptable for small n.
 Alternatively, I can use an array and keep it in reverse order, but let's say for now, I'll use an array with entries[0] as the most recent.
 So, in get_header_entry, for dynamic table, dyn_index = index - 62, and if dyn_index < size, return entries[dyn_index], where entries[0] is index 62, entries[1] is index 63, etc.
 Yes, so that works.
 Then, when adding a new entry, I need to insert it at entries[0], which means shifting all existing entries to the right.
 In C, I can use memmove to shift the array.
 For example:
 c

 void add_to_dynamic_table(DynamicTable *table, const char *name, const char *value) {
    // first, check if we need to evict entries
    size_t entry_size = 32 + strlen(name) + strlen(value);
    while (table->size > 0 && table->current_size + entry_size > table->max_size) {
        // evict the oldest entry, which is at entries[size-1]
        HeaderEntry old = table->entries[table->size - 1];
        table->current_size -= 32 + strlen(old.name) + strlen(old.value);
        free(old.name);
        free(old.value);
        table->size--;
    }
    // now, make space for the new entry
    if (table->size == table->capacity) {
        table->capacity = table->capacity * 2 + 1;
        table->entries = realloc(table->entries, table->capacity * sizeof(HeaderEntry));
    }
    // shift existing entries to the right
    memmove(&table->entries[1], &table->entries[0], table->size * sizeof(HeaderEntry));
    // add new entry at position 0
    table->entries[0].name = strdup(name);
    table->entries[0].value = strdup(value);
    table->size++;
    table->current_size += entry_size;
 }

 Something like that.
 Wait, but in this code, I need to keep track of current_size, so I should add a field current_size to DynamicTable.
 Also, I need to initialize the dynamic table with max_size, and possibly update it when receiving size update instructions.
 So, yes, that's manageable.
 So, with this, I can implement the decoder.
 Similarly, for the encoder, I need to decide how to encode each header: whether to use indexing, literal with indexing, etc.
 But since the task is to write an HPACK implementation, I think implementing both encoder and decoder is expected.
 However, the encoder is a bit more involved because it needs to make decisions on how to encode each header to optimize compression.
 For example, it can check if the header is already in the table, or if it should be added to the dynamic table, etc.
 But for a basic implementation, I can always use literal with incremental indexing, which would work but not be optimal.
 Alternatively, I can implement a simple strategy, like checking if the header is in the static table or dynamic table, and if so, use indexing, else use literal with indexing.
 But to keep it simple, perhaps I can implement the decoder first, and then the encoder.
 Also, since the question is to write an HPACK implementation, and likely it's expected to be complete, but given the complexity, maybe focusing on the decoder is sufficient for now.
 But to make it complete, I'll outline the encoder as well.
 For the encoder, similarly, I need a context with the dynamic table, and a function to encode a list of headers into a byte stream.
 So, something like:
 c

 int hpack_encode(HPACKEncoder *encoder, const HeaderList *headers, uint8_t **output, size_t *output_len) {
    // implement encoding logic
 }

 Where HPACKEncoder would also have a dynamic table, and possibly other state.
 In the encoding logic, for each header, I can check if it's in the static table or dynamic table, and if so, encode it as indexed, else encode it as literal with incremental indexing, and add it to the dynamic table.
 Also, I need to handle Huffman encoding for literals if it's beneficial.
 But for simplicity, I can always use Huffman encoding, or never use it, but to be correct, I should use it when it reduces the size.
 But since the task is to implement HPACK, I think using Huffman encoding is part of it.
 So, I need to implement the Huffman encoder as well.
 For that, I can have a function to encode a string using Huffman, which takes the string and outputs the bit stream.
 Similarly, I can build an encoding table from the Huffman code table.
 For encoding, since it's a static code, I can have an array of {code, length} for each symbol, and then encode the string by concatenating the codes.
 But since the codes are variable length, I need to output bits.
 So, I can have a bit writer.
 Similar to the bit reader, I can implement a bit writer that accumulates bits and outputs bytes.
 For example:
 c

 typedef struct {
    uint8_t *buffer;
    size_t pos;
    int bit_pos;
 } BitWriter;

 void bit_writer_init(BitWriter *writer, uint8_t *buffer) {
    writer->buffer = buffer;
    writer->pos = 0;
    writer->bit_pos = 0;
 }

 void write_bit(BitWriter *writer, int bit) {
    if (writer->bit_pos == 8) {
        writer->pos++;
        writer->bit_pos = 0;
    }
    writer->buffer[writer->pos] = (writer->buffer[writer->pos] << 1) | bit;
    writer->bit_pos++;
 }

 void write_bits(BitWriter *writer, uint32_t value, int n) {
    for (int i = n - 1; i >= 0; i--) {
        int bit = (value >> i) & 1;
        write_bit(writer, bit);
    }
 }

 Wait, actually, in the code above, it's shifting left, so it's filling from MSB to LSB, but in HPACK, the bits are written from MSB to LSB, so that's correct.
 Then, for Huffman encoding, I can have a table of {code, length} for each symbol, and for each symbol in the string, write the corresponding code.
 For example:
 c

 void huffman_encode_string(const char *str, size_t len, BitWriter *writer) {
    for (size_t i = 0; i < len; i++) {
        uint8_t symbol = str[i];
        uint32_t code = huffman_encode_table[symbol].code;
        int length = huffman_encode_table[symbol].length;
        write_bits(writer, code, length);
    }
    // pad with EOS or with 1s, but in HPACK, it's padded with the EOS symbol's code
    // but since EOS is not used, and the spec says to pad with the code for the EOS symbol, which is 30 bits of 1s, I think
    // actually, in the spec, section 5.2, it says: "To ensure that the Huffman encoded data does not exceed the end of the string, the encoded data is padded with a sequence of bits set to 1 until the end of the last byte is reached."
    // wait, specifically: "The encoded data is padded with the code for the EOS symbol until the end of the last byte is reached."
    // and the EOS symbol has a 30-bit code of all 1s.
    // so, to pad, I can write the EOS code until the bit writer is at a byte boundary.
    // but since the EOS code is 30 bits, it's not straightforward.
    // actually, in practice, I can write bits of 1 until the bit_pos is 0.
    // since writing 1s is equivalent to writing the prefix of the EOS code.
    // so, in code, I can do:
    while (writer->bit_pos != 0) {
        write_bit(writer, 1);
    }
 }

 Yes, so that should work.
 So, with this, I can implement the Huffman encoder.
 Similarly, for the main encoder, I need to encode the instructions: indexed, literal with indexing, etc., and for literals, decide whether to use Huffman or not.
 For simplicity, I can always use Huffman, but to be optimal, I should use it only if it reduces the size.
 But since the task is to implement HPACK, and the spec allows both, I can choose to always use Huffman for literals.
 Alternatively, I can implement a simple heuristic, like if the Huffman encoded length is less than the plain length, use Huffman, else don't.
 But that requires computing the Huffman encoded length, which I can do.
 For example, before encoding a string, I can compute the number of bits required for Huffman encoding, and if it's less than 8 * len, use Huffman, else don't.
 But since Huffman codes are designed to compress, usually it's beneficial, especially for common headers.
 So, perhaps I can always use Huffman for simplicity.
 Now, to summarize, for the HPACK implementation in C, I need:

    Static table: an array of HeaderEntry with the predefined entries.
    Dynamic table: a struct with an array of HeaderEntry, size, capacity, current_size, max_size.
    Functions to manage the dynamic table: add entry, evict entries, get entry by index.
    Huffman coding: the code table, the decoder, the encoder.
    Integer encoding and decoding.
    String literal encoding and decoding, with or without Huffman.
    The main decoder function that reads the byte stream and produces the list of headers, updating the dynamic table.
    The main encoder function that takes the list of headers and produces the byte stream, updating the dynamic table.

 Also, I need to handle the dynamic table size update instructions.
 For the encoder, when encoding, I can include size update instructions if needed, but for simplicity, I can assume the max size is fixed.
 In HTTP/2, the max size can be updated by the SETTINGS frame, but in HPACK, the size update instruction can be used to change it within the header block.
 But for a basic implementation, perhaps I can ignore it.
 Wait, actually, in the spec, the encoder can include size update instructions to reduce the dynamic table size if needed.
 But for a simple implementation, I can omit that.
 So, to wrap up, the key components are:

    Define the static table.
    Implement the dynamic table management.
    Implement the Huffman decoder and encoder.
    Implement integer encoding and decoding.
    Implement string literal encoding and decoding.
    Implement the main decoder and encoder functions.

 Given that, I think I have a plan to implement HPACK in C.
 Of course, the actual implementation would require careful handling of memory, error checking, etc., but the above outlines the main logic.
 So, to answer the question, I would say that writing an HPACK implementation in C involves implementing the static and dynamic tables, Huffman coding, integer and string encoding/decoding, and the main encoder and decoder logic as per the HPACK specification.
	#include <stdio.h>
	#include <stdlib.h>
	#include <string.h>
	#include <stdint.h>
	#include <stdbool.h>

	// --- Data Structures ---

	// Header entry structure for static and dynamic tables
	typedef struct {
	char *name;
	char *value;
	} HeaderEntry;

	// Dynamic table structure
	typedef struct {
	HeaderEntry *entries; // entries[0] is most recent
	size_t size;
	size_t capacity;
	size_t current_size; // Total size in octets
	size_t max_size; // Maximum size in octets
	} DynamicTable;

	// Huffman code entry
	typedef struct {
	uint8_t symbol;
	int length;
	uint32_t code; // Left-aligned code
	} HuffmanCode;

	// HPACK context for encoder and decoder
	typedef struct {
	DynamicTable dynamic_table;
	} HPACKContext;

	// --- Static Table (simplified, full table has 61 entries per RFC 7541) ---
	static const HeaderEntry static_table[] = {
	{":authority", ""},
	{":method", "GET"},
	{":method", "POST"},
	{":path", "/"},
	{":status", "200"}
	};
	static const size_t static_table_size = sizeof(static_table) / sizeof(static_table[0]);

	// --- Huffman Table (simplified, full table has 256 entries per RFC 7541 Appendix B) ---
	static const HuffmanCode huffman_table[] = {
	{'0', 5, 0b00000}, // 0
	{'1', 5, 0b00001}, // 1
	{'a', 5, 0b01010}, // 10
	{'b', 6, 0b111100}, // 60
	// Add remaining entries from RFC 7541 Appendix B
	};
	static const size_t huffman_table_size = sizeof(huffman_table) / sizeof(huffman_table[0]);

	// --- Dynamic Table Functions ---

	void init_dynamic_table(DynamicTable *table, size_t max_size) {
	table->entries = NULL;
	table->size = 0;
	table->capacity = 0;
	table->current_size = 0;
	table->max_size = max_size;
	}

	void free_dynamic_table(DynamicTable *table) {
	for (size_t i = 0; i < table->size; i++) {
	free(table->entries[i].name);
	free(table->entries[i].value);
	}
	free(table->entries);
	}

	void add_to_dynamic_table(DynamicTable table, const char name, const char *value) {
	size_t entry_size = 32 + strlen(name) + strlen(value); // 32 octets overhead per RFC 7541
	while (table->current_size + entry_size > table->max_size && table->size > 0) {
	// Evict oldest entry (at size-1)
	HeaderEntry old = table->entries[table->size - 1];
	table->current_size -= 32 + strlen(old.name) + strlen(old.value);
	free(old.name);
	free(old.value);
	table->size--;
	}
	if (table->size == table->capacity) {
	table->capacity = table->capacity ? table->capacity * 2 : 4;
	table->entries = realloc(table->entries, table->capacity * sizeof(HeaderEntry));
	}
	// Shift entries right to insert new entry at index 0
	memmove(&table->entries[1], &table->entries[0], table->size * sizeof(HeaderEntry));
	table->entries[0].name = strdup(name);
	table->entries[0].value = strdup(value);
	table->size++;
	table->current_size += entry_size;
	}

	HeaderEntry get_header_entry(const HPACKContext *ctx, size_t index) {
	HeaderEntry empty = {NULL, NULL};
	if (index < 1) return empty;
	index--; // Convert to 0-based indexing
	if (index < static_table_size) {
	return static_table[index];
	}
	size_t dyn_index = index - static_table_size;
	if (dyn_index < ctx->dynamic_table.size) {
	return ctx->dynamic_table.entries[dyn_index];
	}
	return empty;
	}

	// --- Bit Reader for Huffman Decoding ---

	typedef struct {
	const uint8_t *data;
	size_t pos;
	int bit_pos; // 0 to 7
	} BitReader;

	void bit_reader_init(BitReader reader, const uint8_t data) {
	reader->data = data;
	reader->pos = 0;
	reader->bit_pos = 0;
	}

	int read_bit(BitReader *reader) {
	if (reader->pos >= strlen((char *)reader->data)) return -1;
	int bit = (reader->data[reader->pos] >> (7 - reader->bit_pos)) & 1;
	reader->bit_pos++;
	if (reader->bit_pos == 8) {
	reader->pos++;
	reader->bit_pos = 0;
	}
	return bit;
	}

	// --- Bit Writer for Huffman Encoding ---

	typedef struct {
	uint8_t *buffer;
	size_t pos;
	int bit_pos; // 0 to 7
	} BitWriter;

	void bit_writer_init(BitWriter writer, uint8_t buffer) {
	writer->buffer = buffer;
	writer->pos = 0;
	writer->bit_pos = 0;
	}

	void write_bit(BitWriter *writer, int bit) {
	if (writer->bit_pos == 0) writer->buffer[writer->pos] = 0;
	writer->buffer[writer->pos] \|= (bit << (7 - writer->bit_pos));
	writer->bit_pos++;
	if (writer->bit_pos == 8) {
	writer->pos++;
	writer->bit_pos = 0;
	}
	}

	void write_bits(BitWriter *writer, uint32_t value, int n) {
	for (int i = n - 1; i >= 0; i--) {
	write_bit(writer, (value >> i) & 1);
	}
	}

	// --- Integer Encoding/Decoding ---

	size_t decode_integer(const uint8_t data, size_t pos, size_t len, int N) {
	if (*pos >= len) return -1;
	uint8_t first = data[*pos];
	size_t value = first & ((1 << N) - 1);
	(*pos)++;
	if (value < (1 << N) - 1) return value;
	int m = 0;
	while (*pos < len) {
	uint8_t b = data[*pos];
	(*pos)++;
	value += (b & 0x7F) << m;
	if (!(b & 0x80)) return value;
	m += 7;
	}
	return -1; // Incomplete integer
	}

	void encode_integer(BitWriter *writer, size_t value, int N, uint8_t prefix) {
	size_t limit = (1 << N) - 1;
	if (value < limit) {
	write_bits(writer, prefix \| value, 8);
	} else {
	write_bits(writer, prefix \| limit, 8);
	value -= limit;
	while (value >= 128) {
	write_bits(writer, (value & 0x7F) \| 0x80, 8);
	value >>= 7;
	}
	write_bits(writer, value, 8);
	}
	}

	// --- String Literal Encoding/Decoding ---

	char decode_string(const uint8_t data, size_t *pos, size_t len) {
	if (*pos >= len) return NULL;
	uint8_t first = data[*pos];
	bool huffman = first & 0x80;
	size_t str_len = decode_integer(data, pos, len, 7);
	if (str_len == -1 \|\| *pos + str_len > len) return NULL;
	char *str = malloc(str_len + 1);
	if (huffman) {
	BitReader reader;
	bit_reader_init(&reader, data + *pos);
	for (size_t i = 0; i < str_len; i++) {
	uint32_t code = 0;
	int bits = 0;
	for (int l = 5; l <= 30; l++) { // Min/max lengths from Huffman table
	if (bits < l) {
	int bit = read_bit(&reader);
	if (bit < 0) {
	free(str);
	return NULL;
	}
	code = (code << 1) \| bit;
	bits++;
	}
	for (size_t j = 0; j < huffman_table_size; j++) {
	if (huffman_table[j].length == l && huffman_table[j].code == code) {
	str[i] = huffman_table[j].symbol;
	goto found;
	}
	}
	}
	free(str);
	return NULL; // No match
	found:;
	}
	*pos += str_len;
	} else {
	memcpy(str, data + *pos, str_len);
	*pos += str_len;
	}
	str[str_len] = '\0';
	return str;
	}

	void encode_string(BitWriter writer, const char str, bool use_huffman) {
	size_t len = strlen(str);
	if (use_huffman) {
	size_t bit_count = 0;
	for (size_t i = 0; i < len; i++) {
	for (size_t j = 0; j < huffman_table_size; j++) {
	if (huffman_table[j].symbol == str[i]) {
	bit_count += huffman_table[j].length;
	break;
	}
	}
	}
	size_t byte_count = (bit_count + 7) / 8;
	encode_integer(writer, byte_count, 7, 0x80); // Huffman flag set
	for (size_t i = 0; i < len; i++) {
	for (size_t j = 0; j < huffman_table_size; j++) {
	if (huffman_table[j].symbol == str[i]) {
	write_bits(writer, huffman_table[j].code, huffman_table[j].length);
	break;
	}
	}
	}
	while (writer->bit_pos != 0) write_bit(writer, 1); // Pad with 1s
	} else {
	encode_integer(writer, len, 7, 0x00); // No Huffman
	for (size_t i = 0; i < len; i++) {
	write_bits(writer, str[i], 8);
	}
	}
	}

	// --- HPACK Decoder ---

	typedef struct {
	HeaderEntry *headers;
	size_t size;
	size_t capacity;
	} HeaderList;

	void init_header_list(HeaderList *list) {
	list->headers = NULL;
	list->size = 0;
	list->capacity = 0;
	}

	void add_header(HeaderList list, const char name, const char *value) {
	if (list->size == list->capacity) {
	list->capacity = list->capacity ? list->capacity * 2 : 4;
	list->headers = realloc(list->headers, list->capacity * sizeof(HeaderEntry));
	}
	list->headers[list->size].name = strdup(name);
	list->headers[list->size].value = strdup(value);
	list->size++;
	}

	void free_header_list(HeaderList *list) {
	for (size_t i = 0; i < list->size; i++) {
	free(list->headers[i].name);
	free(list->headers[i].value);
	}
	free(list->headers);
	}

	void init_hpack_context(HPACKContext *ctx, size_t max_size) {
	init_dynamic_table(&ctx->dynamic_table, max_size);
	}

	void free_hpack_context(HPACKContext *ctx) {
	free_dynamic_table(&ctx->dynamic_table);
	}

	int hpack_decode(HPACKContext ctx, const uint8_t data, size_t len, HeaderList *headers) {
	size_t pos = 0;
	while (pos < len) {
	uint8_t first = data[pos];
	if (first & 0x80) { // Indexed
	size_t index = decode_integer(data, &pos, len, 7);
	if (index == -1) return -1;
	HeaderEntry entry = get_header_entry(ctx, index);
	if (!entry.name) return -1;
	add_header(headers, entry.name, entry.value);
	} else if ((first & 0xC0) == 0x40) { // Literal with Incremental Indexing
	size_t index = decode_integer(data, &pos, len, 6);
	if (index == -1) return -1;
	char name, value;
	if (index == 0) {
	name = decode_string(data, &pos, len);
	if (!name) return -1;
	} else {
	HeaderEntry entry = get_header_entry(ctx, index);
	if (!entry.name) return -1;
	name = strdup(entry.name);
	}
	value = decode_string(data, &pos, len);
	if (!value) {
	free(name);
	return -1;
	}
	add_header(headers, name, value);
	add_to_dynamic_table(&ctx->dynamic_table, name, value);
	free(name);
	free(value);
	} else if ((first & 0xF0) == 0x00) { // Literal without Indexing
	size_t index = decode_integer(data, &pos, len, 4);
	if (index == -1) return -1;
	char name, value;
	if (index == 0) {
	name = decode_string(data, &pos, len);
	if (!name) return -1;
	} else {
	HeaderEntry entry = get_header_entry(ctx, index);
	if (!entry.name) return -1;
	name = strdup(entry.name);
	}
	value = decode_string(data, &pos, len);
	if (!value) {
	free(name);
	return -1;
	}
	add_header(headers, name, value);
	free(name);
	free(value);
	} else if ((first & 0xE0) == 0x20) { // Size Update
	size_t new_size = decode_integer(data, &pos, len, 5);
	if (new_size == -1) return -1;
	ctx->dynamic_table.max_size = new_size;
	while (ctx->dynamic_table.current_size > new_size && ctx->dynamic_table.size > 0) {
	HeaderEntry old = ctx->dynamic_table.entries[ctx->dynamic_table.size - 1];
	ctx->dynamic_table.current_size -= 32 + strlen(old.name) + strlen(old.value);
	free(old.name);
	free(old.value);
	ctx->dynamic_table.size--;
	}
	} else {
	return -1; // Unknown instruction
	}
	}
	return 0;
	}

	// --- HPACK Encoder ---

	int hpack_encode(HPACKContext ctx, const HeaderList headers, uint8_t *output, size_t output_len) {
	size_t buffer_size = 1024; // Initial guess
	*output = malloc(buffer_size);
	BitWriter writer;
	bit_writer_init(&writer, *output);
	for (size_t i = 0; i < headers->size; i++) {
	const char *name = headers->headers[i].name;
	const char *value = headers->headers[i].value;
	bool indexed = false;
	size_t index = 0;
	// Check static table
	for (size_t j = 0; j < static_table_size; j++) {
	if (strcmp(static_table[j].name, name) == 0 && strcmp(static_table[j].value, value) == 0) {
	indexed = true;
	index = j + 1;
	break;
	}
	}
	// Check dynamic table
	if (!indexed) {
	for (size_t j = 0; j < ctx->dynamic_table.size; j++) {
	if (strcmp(ctx->dynamic_table.entries[j].name, name) == 0 &&
	strcmp(ctx->dynamic_table.entries[j].value, value) == 0) {
	indexed = true;
	index = static_table_size + j + 1;
	break;
	}
	}
	}
	if (indexed) {
	encode_integer(&writer, index, 7, 0x80);
	} else {
	// Use literal with incremental indexing
	encode_integer(&writer, 0, 6, 0x40);
	encode_string(&writer, name, true); // Use Huffman
	encode_string(&writer, value, true); // Use Huffman
	add_to_dynamic_table(&ctx->dynamic_table, name, value);
	}
	// Resize output buffer if needed
	size_t bytes_used = writer.pos + (writer.bit_pos > 0 ? 1 : 0);
	if (bytes_used >= buffer_size) {
	buffer_size *= 2;
	output = realloc(output, buffer_size);
	writer.buffer = *output;
	}
	}
	*output_len = writer.pos + (writer.bit_pos > 0 ? 1 : 0);
	return 0;
	}

	// --- Main Function for Testing ---

	int main() {
	HPACKContext ctx;
	init_hpack_context(&ctx, 4096); // Default max size

	HeaderList headers;
	init_header_list(&headers);
	add_header(&headers, ":method", "GET");
	add_header(&headers, ":path", "/index.html");

	uint8_t *encoded;
	size_t encoded_len;
	if (hpack_encode(&ctx, &headers, &encoded, &encoded_len) != 0) {
	printf("Encoding failed\n");
	return 1;
	}
	printf("Encoded %zu headers into %zu bytes\n", headers.size, encoded_len);

	HPACKContext decode_ctx;
	init_hpack_context(&decode_ctx, 4096);
	HeaderList decoded_headers;
	init_header_list(&decoded_headers);
	if (hpack_decode(&decode_ctx, encoded, encoded_len, &decoded_headers) != 0) {
	printf("Decoding failed\n");
	return 1;
	}
	printf("Decoded headers:\n");
	for (size_t i = 0; i < decoded_headers.size; i++) {
	printf("%s: %s\n", decoded_headers.headers[i].name, decoded_headers.headers[i].value);
	}

	free(encoded);
	free_header_list(&headers);
	free_header_list(&decoded_headers);
	free_hpack_context(&ctx);
	free_hpack_context(&decode_ctx);
	return 0;
	}
No results found