首页
社区
课程
招聘
未解决 [求助] 求教此压缩算法的解压方法 [算术编码] 100.00雪花
发表于: 2023-9-26 21:10 3254

未解决 [求助] 求教此压缩算法的解压方法 [算术编码] 100.00雪花

2023-9-26 21:10
3254

这应该是算术编码,我对这种算法只了解了一些皮毛,无法写出解压代码,还请指导!

鉴于一些原因,这里就不直接贴出原代码了,我尽量描述精楚一点。

//--------------------//
首先,产生一个表,初始大小是 256 + 2 头尾2字节为空格,中间的 256字节 对应数值 0 - 255

即,这个表初始是这样的: 空格(20h), 0, 1, 2, 3 .... 254, 255, 空格(20h),所以它的初始大小是 258字节, 这个应该是所谓的[概率表]?

初始化 2个 重要的 double值, A = 1, B = 0 //即[初始区间]为 0 - 1 ?

//--------------------//

循环开始(压缩开始), 对 [原数据 - SrcData] 进行 "逐字节" 地处理。

假设, SrcData[0] 是 74h, 那么:

X = 74h 在[表]中的偏移值。(如, 由于是第0字节, [表]还是初始状态, 所以 X = 75h, 注意 [表] 在后面还会变动! 下面会描述)

Y = (74h + 1) 在[表]中的偏移值。(接上例, Y = 76h)

//--------------------//

计算那2个 double值: //计算 区间值 ?

double dbVal = (A - B) / 表的当前长度; (注意表是变动的, 长度也会变动, 下面会描述)
A = B + (dbVal * Y); //接上例, A = 0.45736434108527130
B = B + (dbVal * X); //接上例, B = 0.45348837209302323
//也就是说,对 X 定义的区间值为 [A - B] ???

将这2个double值转换到 '二进制' 的表示形式,则:

A = 0.011101010001010111010100010101110101000101011101010001

B = 0.011101000001011111010000010111110100000101111101000001

截取出 A B 的 [小数部分] 的 "头部相同部分" //那么这个值一定落在这个区间

A = 0.011101010 ...
B = 0.011101000 ...

这里可以看到, 相同部分的长度(设为 Z ) = 7, 即为:0111010

那么,这个 0111010 就是最终结果! 即 74h 最终变成了 0111010

注:这里有个需要特别注意的情况, 就是 '相同部分' 的长度为 0, 此时, 直接就是没有结果, 不记录!

例如(只是假设), 原数据: 58 69 05, 58 = 000 69 = 没有结果 05 = 110, 那么这3字节的压缩后会是 000110

//--------------------//

A B 值 步进: //调整 区间值?

A = A * (1 << Z); //如 A = 0.45736434108527130, Z = 7, 则处结果为 58.54263565891472609
A = A - 整数部分; //也就是说, 只取 [小数部分], 那么 A 最终结果是 0.54263565891472609

而 B 值也是同样的计算:

B = B * (1 << Z);
B = B - 整数部分; //接上例, 此时 B 值为 0.046511627906973274
//--------------------//

在最后, 对 [表] 进行变动! //有点像智能调整概率分布?

取 Y 值; (注: Y = (原数据 + 1) 在[表]中的偏移值)

在 "表[Y]" 处, 插入(增加) 14个 0, 注意表的长度也增加 14 //注, 14 这个值是可以通过输入参数来配置的, 比如, 可以设为 27, 那么压缩结果会不同(这个有点像压缩级别?)

//--------------------//

至此, 循环结束; 将继续处理下一个字节: 即 SrcData[1], SrcData[2], ... 直至处理完;

在处理完之后, 记录 B 的 "最后值":

假设 SrcData 只有 1个字节, 即, 74h, 处理后为 0111010

处理完后 B 值为: 0.046511627906973274, 其二进值为: 0.00001011111010000010111110100000101111101000001 (只取 [小数部分])

那么最终得到的, 压缩后的数据是: 0111010 + 00001011111010000010111110100000101111101000001, 即: 011101000001011111010000010111110100000101111101000001

然后, 还会将 "原数据的原始长度"(即 解压后长度), 通知给 <解压方>

//--------------------//
经实测, "test12345", 压缩后的最终结果为: 011101000111011101111110111100001101111101110110110001010110111101001101100100001110110101011011101101101111001

然后将二进制转换到十六进制(每次取8bit为1字节): 74 77 7e f0 df 76 c5 6f 4d 90 ed 5b b6 f2 //此转换只是方便存储与转输, 与压缩算法没有实质性的关联

经实测, 一段长度为 256字节的数据, 压缩后可达到 100多字节; 一段 500多的字节的数据, 可以压缩到 400字节左右。

//--------------------//

它的代码并不复杂,我已经用 C语言 自己写了一个函数, 然后对原程序进行多次反复调试, 对不同的数据进行压缩, 然后对比结果, 都是一样的。

但是自己根本无法理解这种算法,无法写出解压代码,还请指导!如果能有类似的代码,就最好了。


[招生]科锐逆向工程师培训(2024年11月15日实地,远程教学同时开班, 第51期)

收藏
免费 0
支持
分享
最新回复 (1)
雪    币: 483
活跃值: (133)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
2

发你一段代码,也不知道有没有用。你参考参考吧

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

// 表的大小
#define TABLE_SIZE 258

// 表
unsigned char table[TABLE_SIZE];

// 当前区间值
double A = 0.0;
double B = 1.0;

// 输出缓冲区
unsigned char *output_buffer;
size_t output_buffer_size = 0;

// 读入压缩数据
unsigned char *read_compressed_data(size_t *data_size) {
    // 从文件中读入压缩数据
    FILE *fp = fopen("compressed_data.bin", "rb");
    if (fp == NULL) {
        perror("Error opening compressed data file");
        return NULL;
    }

    // 获取压缩数据的大小
    fseek(fp, 0, SEEK_END);
    *data_size = ftell(fp);
    fseek(fp, 0, SEEK_SET);

    // 分配内存存储压缩数据
    unsigned char *data = malloc(*data_size);
    if (data == NULL) {
        perror("Error allocating memory for compressed data");
        fclose(fp);
        return NULL;
    }

    // 读入压缩数据
    fread(data, 1, *data_size, fp);
    fclose(fp);

    return data;
}

// 读入原始数据的长度
size_t read_original_data_length() {
    // 从文件中读入原始数据的长度
    FILE *fp = fopen("original_data_length.txt", "r");
    if (fp == NULL) {
        perror("Error opening original data length file");
        return 0;
    }

    // 读入原始数据的长度
    size_t length;
    fscanf(fp, "%zu", &length);
    fclose(fp);

    return length;
}

// 初始化表
void initialize_table() {
    // 初始化表中的值
    for (int i = 0; i < TABLE_SIZE; i++) {
        table[i] = i;
    }
}

// 更新表
void update_table(unsigned char symbol) {
    // 找到 symbol 在表中的下标
    int index = symbol;

    // 将 symbol 之后的 14 个值都减去 1
    for (int i = index + 1; i < TABLE_SIZE; i++) {
        table[i]--;
    }
}

// 解压数据
void decompress_data(unsigned char *compressed_data, size_t compressed_data_size, size_t original_data_length) {
    // 分配内存存储解压后的数据
    output_buffer = malloc(original_data_length);
    if (output_buffer == NULL) {
        perror("Error allocating memory for output buffer");
        return;
    }

    // 初始化输出缓冲区
    memset(output_buffer, 0, original_data_length);

    // 初始化表
    initialize_table();

    // 循环读取压缩数据
    for (size_t i = 0; i < compressed_data_size; i++) {
        // 从压缩数据中读取 8 位二进制数据
        unsigned char byte = compressed_data[i];

        // 将二进制数据转换为 double 值
        double X = (double)byte / 256.0;

        // 计算 X 在表中的下标
        int Y = 0;
        while (X > (double)table[Y] / TABLE_SIZE) {
            Y++;
        }

        // 计算区间值
        double dbVal = (A - B) / TABLE_SIZE;
        A = B + (dbVal * Y);
        B = B + (dbVal * X);

        // 将 A 和 B 转换为二进制表示
        char A_binary[64];
        char B_binary[64];
        sprintf(A_binary, "%.63f", A);
        sprintf(B_binary, "%.63f", B);

        // 提取 A 和 B 的公共前缀部分
        char *common_prefix = A_binary;
        while (*common_prefix && *common_prefix == *B_binary) {
            common_prefix++;
        }

        // 如果公共前缀部分的长度大于 0,则将公共前缀部分对应的值添加到输出缓冲区
        if (strlen(common_prefix) > 0) {
            int symbol = Y;
            output_buffer[output_buffer_size++] = symbol;

            // 更新表
            update_table(symbol);
        }

        // 将 A 和 B 的小数部分乘以 2,并去除整数部分
        A = A * 2.0 - floor(A * 2.0);
        B = B * 2.0 - floor(B * 2.0);
    }

    // 将输出缓冲区中的数据还原为原始


2023-12-26 21:03
0
游客
登录 | 注册 方可回帖
返回
//