zstd字典压缩的大数据生产实践 & ctf逆向出题启发_zstd字典训练

zstd实践

首先明确，所有的压缩，和不压缩比，都是cpu换带宽/硬盘。
按我对教科书huffman编码和lzma算法的了解，他们都适合对大文件的压缩，基本原理都是“给高频pattern最短路”。
数据库/数据流压缩，情景不同。操作的对象是许许多多的单行（小文件），而非一个大文件。这导致行与行之间的重复内容无法复用。
zstd可以提前编译字典，字典可以定制化。
在我们的业务数据上，能节省35%的CPU，压缩率提升63%。代价是维护字典，所以适合内网使用（否则需要客户端也参与字典的版本维护），比如我们自己跨AZ的数据搬运。

在一定范围内，字典越大，压缩越慢，压缩率越高，也需要配合更高的压缩等级。字典的体积在100k-500k之间，一般不超过1M。

zstd这个字典也有训练和测试的说法，这个不难理解。构造一个接近实际数据的字典才能有好的压缩效果。好比我们的操作手册，肯定得记录我们自己实际遇到的问题，查询的时候才能较好命中。

gzip比较老，而且是单线程的。pigz是gzip的多线程版。zstd是facebook在2016发布的，自然是支持多线程。spark从3.0开始支持ZSTD，对比默认的snappy，压缩率可以提升30%，降低存储和传输成本。

当然，刚刚提及的所有压缩算法，对hash值这种都没法压缩，因为hash的灵魂就是防碰撞，每个都是低频。hash的压缩需要考虑其它原理的方法。

命题思路

一方面是初次接触rust，一方面是实现一个类似zstd的算法。
命题思路上，我会写两个rust编译后生成的可执行程序，一个用于压缩，一个用于解压缩。
公开放出的是压缩可执行程序，字典，压缩结果。
验题时使用解压缩可执行程序，字典，压缩结果。
题目难点将是，陌生的语言，以及并无现成代码。
给输出求输入的模式，避免了flag在执行过程中在内存里出现。
flag长度准备弄长一点，避免强制破解。

rust背景

Rust 语言可以用于开发：
传统命令行程序 - Rust 编译器可以直接生成目标可执行程序，不需要任何解释程序。
Web 应用 - Rust 可以被编译成 WebAssembly，WebAssembly 是一种 JavaScript 的高效替代品。
网络服务器 - Rust 用极低的资源消耗做到安全高效，且具备很强的大规模并发处理能力。
嵌入式设备 - Rust 同时具有JavaScript的开发速度和 C 语言的执行效率，支持底层平台的开发。

编译器，rustc。
包管理，cargo。

rust的一些特征

导入用的是use，print用的是println!。
函数尾部不带分号，隐式return此表达式。
match关键字作用类似switch。

rust的异常处理

rust函数往往返回一个复合的result类型，它里面的内容可能是好消息，也可能是坏消息。
一句话一般来说以分号结尾，在分号之前加上一个问号，其实是一种match的简写，如果ok就正常返回，如果报错就返回error。
unwrap()也是异常处理，相当于把result解包，如果ok就会返回正常结果，如果出错，就panic崩溃。

具体算法逻辑

本来想自己实现zstd，
发现有点复杂，而且二手资料很少，感觉不值当。
http://www.ezcodesample.com/abs/abs_article.html
上面的链接介绍了ANS，asymmetric numeral system。zstd基于它实现。
这个链接的复杂度更适合出题。

算法理解

出现频率高的，在码表中的行数比较多，输出的bit数就少。
这一点和huffman的思路倒是很像。

精度和码表大小的关系：
码表的构造和frequency高度相关，如果想让frequency很精确的话，码表就要足够大。

妥协

上面的英文链接里有C语言实现，但我肯定不想直接用那个。
自己写的算法，解压时发现不可逆，可以有两种fetch方法。
所以我在想重新设计一下算法，使之更加简化。

每次输出时都加校验码，表示这次输出几bit。恐怕已经不能再称之为“压缩”，不过作为题目没关系。

代码

上面是编码，下面是解码。

use std::fmt::format;
use std::fs;
use std::io::Write;
use fs::File;

fn main() -> Result<(), std::io::Error>{
    let array_a: [usize; 14] = [2,4,7,9,12,13,16,18,19,23,24,27,29,31];
    let array_b: [usize; 10] = [3,6,8,11,14,17,21,22,26,28];
    let array_c: [usize; 6] = [5,10,15,20,25,30];

    let flag_path: &str = "flag.txt";
    let flag = fs::read_to_string(flag_path);
    // println!("Data read: {:?}", flag);

    let mut state: usize= 31;
    let mut binary_string = String::new();
    let mut bit_string: String;
    for c in flag?.chars() {
        println!("before:{}", state);
        let cur_len: usize;
        let outputbit: &str;
        let outputlen: String;
        let head_two: usize = state >> 3;
        let head_three: usize = state >> 2;
        let head_four: usize = state >> 1;
        bit_string = format!("{:b}", state);
        if bit_string.len() < 5 {
            bit_string = format!("{}{}", '0'.to_string().repeat(5-bit_string.len()), bit_string);
            // println!("padding!");
        }
        let bit_str: &str = &bit_string.as_str();
        match c {
            'a' => cur_len = 14,
            'b' => cur_len = 10,
            'c' => cur_len = 6,
            _ => cur_len = 99999
        }
        if state > cur_len {
            if head_four <= cur_len {
                state = head_four;
                outputbit = &bit_str[4..];
                outputlen = format!("01");
            }
            else if head_three <= cur_len {
                state = head_three;
                outputbit = &bit_str[3..];
                outputlen = format!("10");
            }
            else {
                state = head_two;
                outputbit = &bit_str[2..];
                outputlen = format!("11");
            }
            println!("output bits:{}", outputbit);
            binary_string.push_str(outputbit);
            binary_string = format!("{}{}", binary_string, outputlen);
        }
        else {
            outputlen = format!("00");
            binary_string = format!("{}{}", binary_string, outputlen);
        }
        println!("after output:{}", state);
        match c {
            'a' => state = array_a[state - 1],
            'b' => state = array_b[state - 1],
            'c' => state = array_c[state - 1],
            _ => ()
        }
    }
    bit_string = format!("{:b}", state);
    if bit_string.len() < 5 {
        bit_string = format!("{}{}", '0'.to_string().repeat(5-bit_string.len()), bit_string);
        // println!("padding!");
    }
    println!("last state {}", state);
    println!("last state {}", bit_string);
    binary_string = format!("{}{}", binary_string, bit_string);
    println!("{}", binary_string);

    let mut byte_array: Vec<u8> = vec![binary_string.len() as u8];
    let mut content: Vec<u8> = binary_string.as_bytes()
    .chunks(8)
    .map(|chunk| {
        let bit_str = std::str::from_utf8(chunk).unwrap();
        u8::from_str_radix(bit_str, 2).unwrap()
    })
    .collect();
    byte_array.append(&mut content);
    println!("{:?}", byte_array);
    let mut file = File::create("output")?;
    file.write_all(&byte_array)?;
    file.flush()?;

    Ok(())
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

use std::fs;
use std::fs::File;
use std::io::{self, Read};

fn main() -> io::Result<()>{
    let mut file = File::open("output")?;
    let mut buffer: Vec<u8> = Vec::new();
    file.read_to_end(&mut buffer)?;
    // println!("File content as bytes: {:?}", buffer);

    let length: usize = buffer[0] as usize;
    // println!("length of initial bit stream: {}", length);

    let mut binary_string: String = String::new();
    for i in 1..buffer.len() {
        let mut byte_string: String = format!("{:b}", buffer[i]);
        if i < buffer.len() - 1 && byte_string.len() < 8 {
            let pad: String = '0'.to_string().repeat(8-byte_string.len());
            byte_string = format!("{}{}", pad, byte_string);
            // println!("padding!");
        }
        if i == buffer.len() - 1 {
            let pad: String = '0'.to_string().repeat(length - binary_string.len() - byte_string.len());
            byte_string = format!("{}{}", pad, byte_string);
        }
        binary_string.push_str(byte_string.as_str());
    }
    println!("initial binary string: {}", binary_string);

    assert_eq!(binary_string.len(), length, "The decoded binary string does not have the expected length.");

    let array_a: [usize; 14] = [2,4,7,9,12,13,16,18,19,23,24,27,29,31];
    let array_b: [usize; 10] = [3,6,8,11,14,17,21,22,26,28];
    let array_c: [usize; 6] = [5,10,15,20,25,30];
    let mut res: String = String::new();
    let mut state_str: String = binary_string[binary_string.len()-5..binary_string.len()].to_string();
    binary_string = binary_string[0..binary_string.len()-5].to_string();
    let mut state: usize = u8::from_str_radix(state_str.as_str(), 2).unwrap() as usize;

    while binary_string.len() > 0 {
        // println!("state: {}, state_str:{}, binary string: {}", state, state_str, binary_string);
        let mut symbol: char = ' ';
        if let Some(index) = array_a.iter().position(|&x| x == state) {
            symbol = 'a';
            state = index + 1;
        }
        else if let Some(index) = array_b.iter().position(|&x| x == state) {
            symbol = 'b';
            state = index + 1;
        }
        else if let Some(index) = array_c.iter().position(|&x| x == state) {
            symbol = 'c';
            state = index + 1;
        }
        else {
            println!("Error, not found in table, {}", state);
            break;
        }
        state_str = format!("{:b}", state);
        let mut fetch_string: String = String::new();
        if state_str.len() < 5 {
            // fetch几个？
            let fetch_num: usize = u8::from_str_radix(&binary_string[binary_string.len()-2..], 2).unwrap() as usize;
            binary_string = binary_string[0..binary_string.len()-2].to_string();
            fetch_string = binary_string[(binary_string.len()-fetch_num)..binary_string.len()].to_string();
            if fetch_num < 5 - state_str.len() {
                state_str = format!("{}{}{}", '0'.to_string().repeat(5 - state_str.len() - fetch_num), state_str, fetch_string);
            }
            else {
                state_str = format!("{}{}", state_str, fetch_string);
            }
            binary_string = binary_string[0..binary_string.len()-fetch_num].to_string();
        }
        if state_str.len() != 5 {
            println!("state_str {}, fetch_string {}", state_str, fetch_string);
        }
        println!("symbol:{}, state:{}, fetch string:{}", symbol, state, fetch_string);
        state = u8::from_str_radix(state_str.as_str(), 2).unwrap() as usize;
        res.push(symbol as char);
    }

    let reversed_res: String = res.chars().rev().collect();
    println!("{}", reversed_res);
    Ok(())
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85