pico-8 suckless

rust 数据处理

start at 2023/07/25.

数据

最近想重写一下之前写的屎山代码，本来想写一个 TUI 的，但是写 TUI 的话要写一个文件管理器，工程量太大了，所以干脆改成命令行程序得了，后面考虑封装成 wasm 也是可以的，但是就 js 那显示速度真可以吗？

我之前写的一坨东西的原理是用 ffmpeg 把视频拆掉，每帧都转换为 ascii 画，存在一个 Vec 里，后面经过一通乱优化，变为只存储改变像素点的信息，为了不用每次都加工一遍就把数据存储成二进制文件，下次想要观看的时候再载入即可，然而是有一个问题的，视频的音频信息是我手动用 ffmpeg 拆的，要想写的像样点是需要集成到程序里去的，同时直接序列化的二进制文件也挺大的，都超过原视频了(废话)，但是这一堆代码实在是太乱了，我不知道从何下手，而且 main 函数里都像是在测试函数功能一样乱，所以直接简单重构一下吧

这篇文章可不是用来记录重构过程的，主要是记载一下以下几个库的使用方法:

• binrw
• flate2
• bit-set

binrw

顾名思义，binr(ead)w(rite) 是用来把数据二进制序列化和反序列化的工具，主流的序列化是serde，之前的代码序列化就是用这个实现的，但是我用的似懂非懂，秉持一个能用就行的原则就冲了，但是用法还是不是很明白，为什么这次不再好好学习一下 serde 呢

不知道，想用这个就用这个，又不是什么生产环境 ~

binrw 给一个结构体序列化的前提是结构体里的所有元素都能够被序列化（废话

如果我们知道结构体里某个属性的数据是定长的，那么我们只需要知道这个数据是什么类型的，查阅一下数据类型对应的信息即可推理出它需要占多少字节，那么如果结构体里所有数据都是定长的，并且按照这个顺序来排列，那么序列化完成之后，我们也能按照这个规则反序列化出这个数据原来的样子，这就是序列化的大致原理，本质上就是需要一套规则，这个规则有约定俗成的，比如说 serde 的本质上是要转换为一个中间模型，再把中间模型进行序列化，也有编码者自己规定的，不过知道了这套原理，我们自己也可以造轮子了！（你这个人怎么老是喜欢造轮子）

我们只解决了不定长的数据，那么定长的数据怎么解决？答案是告诉它有多长，把序列化想象成时间冻结，你难道再冻结的时候还要完成什么操作吗，为什么不等着冻结结束后再行动呢，不过 binrw 不支持 char，可能是多国语言问题吧，不过 binrw 提供了 NullString，我还没仔细研究过。但是理论上来说什么东西都可以转换成字节，什么东西也都能转变为0和1组成的二进制，而多维数组也可以用映射的方式转换为一维数组，所以应该所有东西都是可以被序列化的，只不过有些结构体需要转换一下形态

规则是 无序 通往 有序 的大门

屁话一堆，还是来看怎么使用 binrw 吧

我们有这么一个结构体

struct Map {
    width: u16,
    height: u16,
    col: Vec<u8>,
    name: String
}

现在对它进行装修，只需要用属性即可

#[binrw]
#[brw(big, magic = b"mmap")]
struct Map {
    width: u16,
    height: u16,
    col: Vec<u8>,
    name: String
}

第一行的 #[binrw] 等效于 #[derive(BinRead, BinWrite)] 相当于告诉编译器，这玩意需要序列化和反序列化

噢，别忘了

use binrw::{BinRead, BinWrite, binrw};

第二行的 brw 括号里的就是同时适用于读和写时的配置了，当然有 br 和 bw，把读写分开来

big 对应 little，分别代表大端字节序 (Big-Endian) 和 小端字节序(Little-Endian)

大端序（Big-Endian）将数据的低位字节存放在内存的高位地址，高位字节存放在低位地址。这种排列方式与数据用字节表示时的书写顺序一致，符合人类的阅读习惯。

小端序（Little-Endian），将一个多位数的低位放在较小的地址处，高位放在较大的地址处，则称小端序。小端序与人类的阅读习惯相反，但更符合计算机读取内存的方式，因为CPU读取内存中的数据时，是从低地址向高地址方向进行读取的。

后面的 magic 就是 魔法句柄（前缀，就相当于是一个标识符，具体有什么用可以参考：

#[binrw]
#[brw(little)]
struct Point(i16, i16);

#[derive(BinRead)]
#[br(big, magic = b"SHAP")]
enum Shape {
    #[br(magic(0u8))] Rect {
        left: i16, top: i16, right: i16, bottom: i16
    },
    #[br(magic(1u8))] Oval { origin: Point, rx: u8, ry: u8 }
}

let oval = Shape::read(&mut Cursor::new(b"SHAP\x01\x80\x02\xe0\x01\x2a\x15")).unwrap();
assert_eq!(oval, Shape::Oval { origin: Point(640, 480), rx: 42, ry: 21 });

[SHAP] [\x01] [\x80\x02\xe0\x01] [\x2a] [\x15]，惊奇的发现居然可以同时嵌套其他实现了 BinRead 的结构体

如果我们的 Map 只有 width 和 height，那么我们的工作就已经做完了，可惜我们还有两个非定长的数据类型，需要我们做一些改变，col 是一个动态数组，如果我们能告诉序列化它的长度就行了，我们加一个元素用来告诉它有多少长度，然后加一个属性指定，不能用 usize 噢，因为 usize 的大小取决于系统，不定就是无序，这里是br，不是brw，只有在读取的时候才要使用

{
    ...
    col_count: u8,
    #[br(count = col_count)]
    col: Vec<u8>,
    ...
}

剩下一个 name 字符串，我们需要怎么做呢？binrw库里有一个 NullString 类型，可以直接解决

struct Map {
    width: u16,
    height: u16,
    col_count: u8,
    #[br(count = col_count)]
    col: Vec<u8>,
    name: NullString
}

NullString 的 hover 有写 A null-terminated 8-bit string.

也就是把每个字符变成 u8，这样的话我们可以用动态数组来表示字符串就行了（mdzz

#[binrw]
#[brw(big, magic = b"mmap")]
#[derive(Debug)]
struct Map {
    width: u16,
    height: u16,
    col_count: u8,
    #[br(count = col_count)]
    col: Vec<u8>,
    name_count: u8,
    #[br(count = name_count * 2)]
    name: Vec<u8>
}

我还特意让每个字符有两个字节

接下来是序列化和反序列化了，虽然这个名字是 read 和 write，但是我可没打算直接读写这玩意，直接写也太大了！

encode

// encode
fn encode() -> Cursor<Vec<u8>>{
    let tmp = Map{
        width: 255,
        height: 255,
        col_count: 2,
        col: vec![24, 29],
        name_count: 3,
        name: vec![6, 5, 4, 3, 2, 1]
    };
    let mut cur = Cursor::new(Vec::new());
    tmp.write(&mut cur).unwrap();
    println!("{:?}\n{:?}", tmp, cur.clone().into_inner());
    cur
}

我们中规中矩写一个结构体实例，然后把它写进 std::io::Cursor 里，write 写入对象的条件是实现 Read 和 Seek 两个特性，一般有 Cursor 和 std::fs::File 是同时实现这两个的，可以直接拿来用，binrw 自带了一个 io，里面有 Cursor，不过我还是喜欢用 std 的东西

decode

// decode
fn decode(cur: Cursor<Vec<u8>>) {
    let mut cur = cur.clone();
    cur.set_position(0);
    let tmp = Map::read(&mut cur).unwrap();
    println!("{:?}", tmp);
    let tmp = Map::read(&mut Cursor::new(b"mmap\x00\x10\x00\x10\x01\x21\x02\x01\x02\x03\x04")).unwrap();
    println!("--------------------------\n{:?}", tmp);
}

这个比较简单粗暴好理解

fn main() {
    let tmp = encode();
    decode(tmp);
}

最后串起来，完美执行

不过我是不是应该用 test 来写这种东西，老喜欢把这种东西写进 main 里

binrw 只能转为二进制文件，听名字就知道不能转为 json 那种有可读性的文件，所以有空还是要仔细学一下 serde

flate2

无损压缩，这个世界上无损压缩就那么几种算法，这个使用的是 DEFLATE 算法

具体原理大概是

是同时使用了LZ77算法与哈夫曼编码（Huffman Coding）的一个无损数据压缩算法。它最初是由美国程序员菲尔·卡茨（Phil Katz）为他的PKZIP软件第二版所定义的，后来被RFC 1951标准化

LZ77算法通过使用编码器或者解码器中已经出现过的相应匹配数据信息，替换当前数据从而实现压缩功能。这个匹配信息使用称为长度-距离对的一对数据进行编码，它等同于“每个给定长度个字符都等于后面特定距离字符位置上的未压缩数据流。”

在计算机资料处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现概率的方法得到的，出现概率高的字母使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

看上去感觉像算法复杂度蛮高的字符串题，我倒还没闲工夫去搞懂实现，之前看《硅谷》倒是有压缩算法，不过那个太虚构了，还是现实一点来看看怎么用吧

encode

现在我们手头上有这么一个文件 hello.bin （不要在意，python 随机生成的

72680631482092620292718750846970204021485234748435774041517442472626814666931994800891063031012107590392007700270477119190001397713259074394119884542568536691887563856179875906777442729307397216697965839016015982898586024802120372763575304436546803800343346110119155624139745996012937203406759252383312099212054595065493485133122242778699921849319092190189617215935844086880421389732609937526009152962736214786376085037305079631634016433474591688150666785609537224143490014517577206720316213313834220577937085406

现在我们需要对它压缩，那么我们第一步应该先把他都进来再说，因为文件都包含一个类似指针的东西会移动，所以一般都是申明为可变变量，然而编译器告诉我不用 mut

let mut file = std::fs::File::open("hello.bin").unwrap();

然后我们对这个文件的字节进行读取，一般来说压缩的话是整体压缩吧，分开压缩也不是不行，因为都是无损的，本质上也只是对一堆0和1进行修改，能完美还原的话中间步骤是什么样都无所谓，这里我们用 std::io::BufReader 把文件内容读为字节流

let buffer = BufReader::new(file);

然后我们开始压缩，创建一个压缩器，他应该实在 new 的时候就压缩好了

let mut encoder = bufread::DeflateEncoder::new(
    buffer, flate2::Compression::best());

第一个参数是要压缩的字节流，第二个参数是使用的压缩类型，当然要选择效果最好的！

其实不止这一种压缩器，还有其他的，我比较喜欢这个

接下来让压缩器把读到的东西吐出来，不用多想，吐出来的东西也肯定是字节流

let mut buf = Vec::new();
encoder.read_to_end(&mut buf).unwrap();

干脆写进文件吧

let mut file2 = std::fs::File::create("zipp").unwrap();
file2.write(buf.as_slice()).unwrap();

因为涉及到了读和写，所以不要忘记 use std::io::{Read, Write}

来看效果

$ ls -l
-rw-r--r-- 1 paradoxskin paradoxskin 514 Jul 26 23:53 hello.bin
-rw-r--r-- 1 paradoxskin paradoxskin 264 Jul 27 23:59 zipp

直接压缩了一半，相当的给力

decode

都压缩了一个文件，所以解压就直接解压这个文件吧

let file = std::fs::File::open("zipp").unwrap();
let buf = BufReader::new(file);

let mut decoder = bufread::DeflateDecoder::new(buf);
let mut v = Vec::new();
decoder.read_to_end(&mut v);
println!("{:?}", v);

输出了一堆

[55, 50, 54, 56, 48, 54, 51, 49, 52, 56, 50, 48, 57, 50, 54, 50, 48, 50, 57, 50, 55, 49, 56, 55, 53, 48, 56, 52, 54, 57, 55, 48, 50, 48, 52, 48, 50, 49, 52, 56, 53, 50, 51, 52, 55, 52, 56, 52, 51, 53, 55, 55, 52, 48, 52, 49, 53, 49, 55, 52, 52, 50, 52, 55, 50, 54, 50, 54, 56, 49, 52, 54, 54, 54, 57, 51, 49, 57, 57, 52, 56, 48, 48, 56, 57, 49, 48, 54, 51, 48, 51, 49, 48, 49, 50, 49, 48, 55, 53, 57, 48, 51, 57, 50, 48, 48, 55, 55, 48, 48, 50, 55, 48, 52, 55, 55, 49, 49, 57, 49, 57, 48, 48, 48, 49, 51, 57, 55, 55, 49, 51, 50, 53, 57, 48, 55, 52, 51, 57, 52, 49, 49, 57, 56, 56, 52, 53, 52, 50, 53, 54, 56, 53, 51, 54, 54, 57, 49, 56, 56, 55, 53, 54, 51, 56, 53, 54, 49, 55, 57, 56, 55, 53, 57, 48, 54, 55, 55, 55, 52, 52, 50, 55, 50, 57, 51, 48, 55, 51, 57, 55, 50, 49, 54, 54, 57, 55, 57, 54, 53, 56, 51, 57, 48, 49, 54, 48, 49, 53, 57, 56, 50, 56, 57, 56, 53, 56, 54, 48, 50, 52, 56, 48, 50, 49, 50, 48, 51, 55, 50, 55, 54, 51, 53, 55, 53, 51, 48, 52, 52, 51, 54, 53, 52, 54, 56, 48, 51, 56, 48, 48, 51, 52, 51, 51, 52, 54, 49, 49, 48, 49, 49, 57, 49, 53, 53, 54, 50, 52, 49, 51, 57, 55, 52, 53, 57, 57, 54, 48, 49, 50, 57, 51, 55, 50, 48, 51, 52, 48, 54, 55, 53, 57, 50, 53, 50, 51, 56, 51, 51, 49, 50, 48, 57, 57, 50, 49, 50, 48, 53, 52, 53, 57, 53, 48, 54, 53, 52, 57, 51, 52, 56, 53, 49, 51, 51, 49, 50, 50, 50, 52, 50, 55, 55, 56, 54, 57, 57, 57, 50, 49, 56, 52, 57, 51, 49, 57, 48, 57, 50, 49, 57, 48, 49, 56, 57, 54, 49, 55, 50, 49, 53, 57, 51, 53, 56, 52, 52, 48, 56, 54, 56, 56, 48, 52, 50, 49, 51, 56, 57, 55, 51, 50, 54, 48, 57, 57, 51, 55, 53, 50, 54, 48, 48, 57, 49, 53, 50, 57, 54, 50, 55, 51, 54, 50, 49, 52, 55, 56, 54, 51, 55, 54, 48, 56, 53, 48, 51, 55, 51, 48, 53, 48, 55, 57, 54, 51, 49, 54, 51, 52, 48, 49, 54, 52, 51, 51, 52, 55, 52, 53, 57, 49, 54, 56, 56, 49, 53, 48, 54, 54, 54, 55, 56, 53, 54, 48, 57, 53, 51, 55, 50, 50, 52, 49, 52, 51, 52, 57, 48, 48, 49, 52, 53, 49, 55, 53, 55, 55, 50, 48, 54, 55, 50, 48, 51, 49, 54, 50, 49, 51, 51, 49, 51, 56, 51, 52, 50, 50, 48, 53, 55, 55, 57, 51, 55, 48, 56, 53, 52, 48, 54, 13, 10]

因为是字符的字节，所以

for tmp in v {
    print!("{}", tmp as char);
}

输出为

72680631482092620292718750846970204021485234748435774041517442472626814666931994800891063031012107590392007700270477119190001397713259074394119884542568536691887563856179875906777442729307397216697965839016015982898586024802120372763575304436546803800343346110119155624139745996012937203406759252383312099212054595065493485133122242778699921849319092190189617215935844086880421389732609937526009152962736214786376085037305079631634016433474591688150666785609537224143490014517577206720316213313834220577937085406

nice！

bit-set

因为这东西太多了，所以这片小小的空地写不下我的学习日志（有空再学

QED

2023/07/27