嵌入式图形界面的图片压缩：几种平衡压缩率与解码速度的算法选择

// RLE (Run-Length Encoding) Implementation
int rle_encode(const unsigned char *input, int input_len, unsigned char *output) {
    int output_len = 0;
    int i = 0;

    while (i < input_len) {
        unsigned char current = input[i];
        int count = 1;

        while (i + count < input_len && input[i + count] == current && count < 255) {
            count++;
        }

        output[output_len++] = count;
        output[output_len++] = current;
        i += count;
    }

    return output_len;
}

int rle_decode(const unsigned char *input, int input_len, unsigned char *output) {
    int output_len = 0;
    int i = 0;

    while (i < input_len) {
        int count = input[i++];
        unsigned char value = input[i++];

        for (int j = 0; j < count; j++) {
            output[output_len++] = value;
        }
    }

    return output_len;
}

// SRLE (Simplified RLE) Implementation
int srle_encode(const unsigned char *input, int input_len, unsigned char *output) {
    int output_len = 0;
    int i = 0;

    while (i < input_len) {
        // Find runs of same value
        unsigned char current = input[i];
        int run_length = 1;

        while (i + run_length < input_len && input[i + run_length] == current) {
            run_length++;
        }

        if (run_length >= 4) {
            // Encode run
            output[output_len++] = 0;  // Special marker
            output[output_len++] = run_length;
            output[output_len++] = current;
            i += run_length;
        } else {
            // Copy literal
            output[output_len++] = input[i++];
        }
    }

    return output_len;
}

int srle_decode(const unsigned char *input, int input_len, unsigned char *output) {
    int output_len = 0;
    int i = 0;

    while (i < input_len) {
        if (input[i] == 0) {
            // Decode run
            int run_length = input[i + 1];
            unsigned char value = input[i + 2];
            for (int j = 0; j < run_length; j++) {
                output[output_len++] = value;
            }
            i += 3;
        } else {
            // Copy literal
            output[output_len++] = input[i++];
        }
    }

    return output_len;
}

// Mini LZO-style Implementation
#define HASH_BITS 14
#define HASH_SIZE (1 << HASH_BITS)
#define HASH_MASK (HASH_SIZE - 1)
#define MIN_MATCH 3
#define MAX_MATCH 128

int mini_lzo_encode(const unsigned char *input, int input_len, unsigned char *output) {
    int output_len = 0;
    unsigned short hash_table[HASH_SIZE] = {0};

    int i = 0;
    while (i < input_len) {
        // Look for a match
        int hash = ((input[i] << 8) | input[i + 1]) & HASH_MASK;
        int match_pos = hash_table[hash];
        int match_len = 0;

        if (match_pos < i) {
            // Check match length
            while (match_len < MAX_MATCH &&
                   i + match_len < input_len &&
                   input[match_pos + match_len] == input[i + match_len]) {
                match_len++;
            }
        }

        if (match_len >= MIN_MATCH) {
            // Encode match
            int match_dist = i - match_pos;
            output[output_len++] = ((match_len - MIN_MATCH) << 4) | ((match_dist >> 8) & 0x0F);
            output[output_len++] = match_dist & 0xFF;
            i += match_len;
        } else {
            // Encode literal
            output[output_len++] = input[i++];
        }

        // Update hash table
        hash_table[hash] = i;
    }

    return output_len;
}

int mini_lzo_decode(const unsigned char *input, int input_len, unsigned char *output) {
    int output_len = 0;
    int i = 0;

    unsigned short hash_table[HASH_SIZE] = {0};

    while (i < input_len) {
        unsigned char byte = input[i++];

        if (byte < 0x80) {  // literal byte
            output[output_len++] = byte;
        } else {  // compressed match
            int len = (byte >> 4) + MIN_MATCH;
            int dist = ((byte & 0x0F) << 8) | input[i++];

            int match_pos = output_len - dist;
            for (int j = 0; j < len; j++) {
                output[output_len++] = output[match_pos + j];
            }
        }
    }

    return output_len;
}

// FastLZ-style Implementation
#define FASTLZ_HASH_LOG  13
#define FASTLZ_HASH_SIZE (1 << FASTLZ_HASH_LOG)
#define FASTLZ_HASH_MASK  (FASTLZ_HASH_SIZE - 1)

int fastlz_encode(const unsigned char *input, int input_len, unsigned char *output) {
    int output_len = 0;
    int hash_table[FASTLZ_HASH_SIZE] = {0};

    int i = 0;
    while (i < input_len) {
        // Compute hash
        int hash = (input[i] + (input[i + 1] << 4) + (input[i + 2] << 8)) & FASTLZ_HASH_MASK;
        int match_pos = hash_table[hash];
        int match_len = 0;

        if (match_pos < i) {
            // Check match length
            while (match_len < 264 && i + match_len < input_len &&
                   input[match_pos + match_len] == input[i + match_len]) {
                match_len++;
            }
        }

        if (match_len >= 3) {
            // Encode match
            int match_dist = i - match_pos;

            if (match_len < 7) {
                output[output_len++] = ((match_len - 2) << 5) | ((match_dist >> 8) & 0x1F);
            } else {
                output[output_len++] = (7 << 5) | ((match_dist >> 8) & 0x1F);
                output[output_len++] = match_len - 7;
            }

            output[output_len++] = match_dist & 0xFF;
            i += match_len;
        } else {
            // Encode literal
            output[output_len++] = input[i++];
        }

        // Update hash table
        hash_table[hash] = i;
    }

    return output_len;
}

int fastlz_decode(const unsigned char *input, int input_len, unsigned char *output) {
    int output_len = 0;
    int i = 0;

    int hash_table[FASTLZ_HASH_SIZE] = {0};

    while (i < input_len) {
        unsigned char byte = input[i++];

        if (byte < 0x80) {  // literal byte
            output[output_len++] = byte;
        } else {  // compressed match
            int len = (byte >> 5) + 3;
            int dist = ((byte & 0x1F) << 8) | input[i++];

            int match_pos = output_len - dist;
            for (int j = 0; j < len; j++) {
                output[output_len++] = output[match_pos + j];
            }
        }
    }

    return output_len;
}

// QOI (Quite OK Image Format) style Implementation
typedef struct {
    unsigned char r, g, b, a;
} QOIPixel;

#define QOI_HASH(p) (((p).r * 3 + (p).g * 5 + (p).b * 7 + (p).a * 11) & 63)

int qoi_encode(const QOIPixel *input, int pixel_count, unsigned char *output) {
    int output_len = 0;
    QOIPixel index[64] = {0};
    QOIPixel prev = {0, 0, 0, 255};
    int run = 0;

    for (int i = 0; i < pixel_count; i++) {
        QOIPixel pixel = input[i];

        if (memcmp(&pixel, &prev, sizeof(QOIPixel)) == 0) {
            run++;
            if (run == 62 || i == pixel_count - 1) {
                output[output_len++] = 0xC0 | (run - 1);
                run = 0;
            }
        } else {
            if (run > 0) {
                output[output_len++] = 0xC0 | (run - 1);
                run = 0;
            }

            int index_pos = QOI_HASH(pixel);
            if (memcmp(&pixel, &index[index_pos], sizeof(QOIPixel)) == 0) {
                output[output_len++] = 0x00 | index_pos;
            } else {
                index[index_pos] = pixel;

                if (pixel.a == prev.a) {
                    int vr = pixel.r - prev.r;
                    int vg = pixel.g - prev.g;
                    int vb = pixel.b - prev.b;

                    if (vr > -3 && vr < 2 && vg > -3 && vg < 2 && vb > -3 && vb < 2) {
                        output[output_len++] = 0x40 | ((vr + 2) << 4) | ((vg + 2) << 2) | (vb + 2);
                    } else {
                        output[output_len++] = 0xFE;
                        output[output_len++] = pixel.r;
                        output[output_len++] = pixel.g;
                        output[output_len++] = pixel.b;
                    }
                } else {
                    output[output_len++] = 0xFF;
                    output[output_len++] = pixel.r;
                    output[output_len++] = pixel.g;
                    output[output_len++] = pixel.b;
                    output[output_len++] = pixel.a;
                }
            }
        }

        prev = pixel;
    }

    return output_len;
}

int qoi_decode(const unsigned char *input, int input_len, QOIPixel *output) {
    int output_len = 0;
    QOIPixel index[64] = {0};
    QOIPixel prev = {0, 0, 0, 255};

    int i = 0;
    while (i < input_len) {
        unsigned char byte = input[i++];

        if (byte == 0xC0) {  // run-length encoding
            int run_len = (byte & 0x3F) + 1;
            for (int j = 0; j < run_len; j++) {
                output[output_len++] = prev;
            }
        } else {
            prev.r = byte;
            prev.g = input[i++];
            prev.b = input[i++];
            prev.a = input[i++];
            output[output_len++] = prev;
        }
    }

    return output_len;
}

#define MAX_TREE_NODES 512

typedef struct {
    int frequency;
    int left;
    int right;
    unsigned char value;
} HuffmanNode;

typedef struct {
    unsigned int code;
    int bits;
} HuffmanCode;

void build_huffman_tree(const int *frequencies, HuffmanNode *nodes, int *node_count) {
    // Initialize leaf nodes
    *node_count = 0;
    for (int i = 0; i < 256; i++) {
        if (frequencies[i] > 0) {
            nodes[*node_count].frequency = frequencies[i];
            nodes[*node_count].value = (unsigned char)i;
            nodes[*node_count].left = -1;
            nodes[*node_count].right = -1;
            (*node_count)++;
        }
    }

    // Build tree
    while (*node_count > 1) {
        // Find two nodes with lowest frequencies
        int min1 = 0, min2 = 1;
        if (nodes[min1].frequency > nodes[min2].frequency) {
            int temp = min1;
            min1 = min2;
            min2 = temp;
        }

        for (int i = 2; i < *node_count; i++) {
            if (nodes[i].frequency < nodes[min1].frequency) {
                min2 = min1;
                min1 = i;
            } else if (nodes[i].frequency < nodes[min2].frequency) {
                min2 = i;
            }
        }

        // Create new internal node
        HuffmanNode new_node;
        new_node.frequency = nodes[min1].frequency + nodes[min2].frequency;
        new_node.left = min1;
        new_node.right = min2;

        // Replace first minimum with new node and remove second minimum
        nodes[min1] = new_node;
        nodes[min2] = nodes[--(*node_count)];
    }
}

void generate_huffman_codes(const HuffmanNode *nodes, int node_count, HuffmanCode *codes,
                          int node_index, unsigned int code, int bits) {
    if (nodes[node_index].left == -1 && nodes[node_index].right == -1) {
        // Leaf node
        codes[nodes[node_index].value].code = code;
        codes[nodes[node_index].value].bits = bits;
    } else {
        // Internal node - traverse left and right
        generate_huffman_codes(nodes, node_count, codes, nodes[node_index].left,
                             (code << 1), bits + 1);
        generate_huffman_codes(nodes, node_count, codes, nodes[node_index].right,
                             (code << 1) | 1, bits + 1);
    }
}

// Combined RLE + Huffman Implementation
int rle_huffman_encode(const unsigned char *input, int input_len, unsigned char *output) {
    // First perform RLE
    unsigned char *rle_buffer = (unsigned char *)malloc(input_len * 2);
    int rle_len = rle_encode(input, input_len, rle_buffer);

    // Calculate frequencies
    int frequencies[256] = {0};
    for (int i = 0; i < rle_len; i++) {
        frequencies[rle_buffer[i]]++;
    }

    // Build Huffman tree and generate codes
    HuffmanNode nodes[MAX_TREE_NODES];
    int node_count;
    build_huffman_tree(frequencies, nodes, &node_count);

    HuffmanCode codes[256];
    generate_huffman_codes(nodes, node_count, codes, 0, 0, 0);

    // Write header (frequencies)
    int output_len = 0;
    memcpy(output, frequencies, sizeof(frequencies));
    output_len += sizeof(frequencies);

    // Encode data
    unsigned int bit_buffer = 0;
    int bits_in_buffer = 0;

    for (int i = 0; i < rle_len; i++) {
        unsigned char symbol = rle_buffer[i];
        HuffmanCode code = codes[symbol];

        bit_buffer = (bit_buffer << code.bits) | code.code;
        bits_in_buffer += code.bits;

        while (bits_in_buffer >= 8) {
            output[output_len++] = (bit_buffer >> (bits_in_buffer - 8)) & 0xFF;
            bits_in_buffer -= 8;
        }
    }

    // Flush remaining bits
    if (bits_in_buffer > 0) {
        output[output_len++] = (bit_buffer << (8 - bits_in_buffer)) & 0xFF;
    }

    free(rle_buffer);
    return output_len;
}

int rle_huffman_decode(const unsigned char *input, int input_len, unsigned char *output) {

    int frequencies[256];
    memcpy(frequencies, input, sizeof(frequencies));
    input += sizeof(frequencies);

    HuffmanNode nodes[MAX_TREE_NODES];
    int node_count;
    build_huffman_tree(frequencies, nodes, &node_count);

    HuffmanCode codes[256];
    generate_huffman_codes(nodes, node_count, codes, 0, 0, 0);

    int output_len = 0;
    unsigned int bit_buffer = 0;
    int bits_in_buffer = 0;
    int rle_len = 0;

    unsigned char *rle_buffer = (unsigned char *)malloc(input_len * 2);
    int rle_output_len = 0;

    while (rle_len < input_len) {
        bit_buffer = (bit_buffer << 8) | input[rle_len++];
        bits_in_buffer += 8;

        while (bits_in_buffer >= 8) {
            unsigned char symbol = 0;
            for (symbol = 0; symbol < 256; symbol++) {
                if (codes[symbol].bits <= bits_in_buffer &&
                    (bit_buffer >> (bits_in_buffer - codes[symbol].bits)) == codes[symbol].code) {
                    rle_buffer[rle_output_len++] = symbol;
                    bits_in_buffer -= codes[symbol].bits;
                    bit_buffer &= (1 << bits_in_buffer) - 1;
                    break;
                }
            }
        }
    }

    int i = 0;
    while (i < rle_output_len) {
        int count = rle_buffer[i++];
        unsigned char value = rle_buffer[i++];

        for (int j = 0; j < count; j++) {
            output[output_len++] = value;
        }
    }

    free(rle_buffer);
    return output_len;
}