如何解压缩DEFLATE压缩数据并逆操作PNG的FILTER（C++无库）

一、PNG行过滤器的逆操作实现 #

PNG的IDAT块中，每一行像素数据前会有1字节的过滤器类型（0-4），逆操作需根据类型将过滤后的数据还原为原始像素。以下是每种过滤器的逆运算逻辑（基于C++实现）：

1. 过滤器0（无过滤） #

过滤后的数据即原始数据，直接复制：

// 参数：filtered_data（过滤后的数据指针）、output（原始数据输出缓冲区）、row_length（行数据字节数）
void filter_none(const uint8_t* filtered_data, uint8_t* output, size_t row_length) {
    memcpy(output, filtered_data, row_length);
}

2. 过滤器1（差值过滤） #

每个字节 = 当前过滤字节 + 左侧相邻像素的对应字节（原始值）：

void filter_sub(const uint8_t* filtered_data, uint8_t* output, size_t row_length, int bytes_per_pixel) {
    for (size_t i = 0; i < row_length; ++i) {
        uint8_t left = (i >= bytes_per_pixel) ? output[i - bytes_per_pixel] : 0;
        output[i] = filtered_data[i] + left;
    }
}

注：bytes_per_pixel为单像素字节数，RGB24设为3，RGBA设为4

3. 过滤器2（上值过滤） #

每个字节 = 当前过滤字节 + 上一行对应位置的原始字节：

void filter_up(const uint8_t* filtered_data, uint8_t* output, size_t row_length, const uint8_t* prev_row) {
    for (size_t i = 0; i < row_length; ++i) {
        output[i] = filtered_data[i] + prev_row[i];
    }
}

4. 过滤器3（平均过滤） #

每个字节 = 当前过滤字节 + （左侧原始字节 + 上侧原始字节）/ 2（整数取整）：

void filter_average(const uint8_t* filtered_data, uint8_t* output, size_t row_length, int bytes_per_pixel, const uint8_t* prev_row) {
    for (size_t i = 0; i < row_length; ++i) {
        uint8_t left = (i >= bytes_per_pixel) ? output[i - bytes_per_pixel] : 0;
        uint8_t up = prev_row[i];
        output[i] = filtered_data[i] + ((left + up) / 2);
    }
}

5. 过滤器4（Paeth预测过滤） #

基于左侧、上侧、左上侧三个原始值计算预测值，当前字节 = 过滤字节 + 预测值：

uint8_t paeth_predictor(uint8_t a, uint8_t b, uint8_t c) {
    int p = a + b - c;
    int pa = abs(p - a);
    int pb = abs(p - b);
    int pc = abs(p - c);
    if (pa <= pb && pa <= pc) return a;
    else if (pb <= pc) return b;
    else return c;
}

void filter_paeth(const uint8_t* filtered_data, uint8_t* output, size_t row_length, int bytes_per_pixel, const uint8_t* prev_row) {
    for (size_t i = 0; i < row_length; ++i) {
        uint8_t left = (i >= bytes_per_pixel) ? output[i - bytes_per_pixel] : 0;
        uint8_t up = prev_row[i];
        uint8_t up_left = (i >= bytes_per_pixel) ? prev_row[i - bytes_per_pixel] : 0;
        uint8_t pred = paeth_predictor(left, up, up_left);
        output[i] = filtered_data[i] + pred;
    }
}

注意：所有加法为无符号8位整数运算，自动溢出截断，符合PNG规范

二、DEFLATE压缩数据的解压实现 #

DEFLATE基于LZ77和哈夫曼编码，解压分两步：哈夫曼解码 → LZ77滑动窗口还原。

1. 哈夫曼解码核心要点 #

• 固定哈夫曼树：PNG规范中预定义了字面量/长度树和距离树的码长，可直接硬编码构建映射表，无需解析额外数据。
• 动态哈夫曼树：需先读取码长的编码数据，构建码长哈夫曼树，再解码得到字面量/长度、距离树的码长，最终构建出用于解码LZ77数据的哈夫曼树。
• 实现一个BitReader类，支持从字节流中逐位读取数据（DEFLATE编码为位对齐，非字节对齐）：

class BitReader {
private:
    const uint8_t* data;
    size_t byte_pos;
    uint8_t bit_pos;
public:
    BitReader(const uint8_t* input_data) : data(input_data), byte_pos(0), bit_pos(7) {}

    uint32_t read_bits(int count) {
        uint32_t result = 0;
        for (int i = 0; i < count; ++i) {
            result <<= 1;
            result |= (data[byte_pos] >> bit_pos) & 1;
            if (--bit_pos == -1) {
                byte_pos++;
                bit_pos = 7;
            }
        }
        return result;
    }
};

2. LZ77滑动窗口还原 #

• 滑动窗口固定为32768字节，用std::vector<uint8_t>维护循环缓冲区。
• 解码得到的符号流分为两种：
  • 字面量：直接写入滑动窗口，同时输出到像素数据缓冲区。
  • 长度-距离对：从窗口中距离当前写入位置distance处，复制length个字节到当前位置。

三、BadApple场景优化 #

控制台输出无需全RGB精度，解压后可将RGB转为灰度值，再映射到控制台字符（如@#$%*+=- ）：

// RGB转灰度（ITU-R BT.601标准）
uint8_t rgb_to_gray(uint8_t r, uint8_t g, uint8_t b) {
    return static_cast<uint8_t>(0.299 * r + 0.587 * g + 0.114 * b);
}

// 灰度值转控制台字符
char gray_to_char(uint8_t gray) {
    const char* char_map = " .:-=+*#%@";
    int index = gray * (strlen(char_map) - 1) / 255;
    return char_map[index];
}

内容的提问来源于stack exchange，提问作者masteronin99