《老子到此一游系列》之 老子带你看懂这些风景—— 多维探秘通用无损压缩 第七章 OpenHarmony 内核子系统（转发）
第七章 OpenHarmony内核子系统
OpenHarmony的Linux内核基于开源Linux内核LTS 4.19.y / 5.10.y 分支演进，在此基线基础上，回合CVE补丁及OpenHarmony特性，作为OpenHarmony Common Kernel基线。针对不同的芯片，各厂商合入对应的板级驱动补丁，完成对OpenHarmony的基线适配。
7.1 EROFS文件系统
EROFS 文件系统代表增强型只读文件系统。与其他只读文件系统不同，它旨在为灵活性、可扩展性而设计，但要保持简单和高性能。EROFS由华为于2018年开源，现已合入Linux内核主线，在4.19版本发布：
EROFS 实现了 LZ4 固定大小算法的输出压缩，与其他现有的固定大小的输入解决方案相比，它从可变大小的输入生成固定大小的压缩数据块。使用固定大小的输出压缩可以获得相对更高的压缩率，因为现在流行的数据压缩算法大多基于 LZ77，这种固定大小的输出方法可以从历史字典中受益。
具体来说，原始数据被转换成几个可变大小的范围，同时被压缩成物理集群。为了记录每个可变大小的范围，引入逻辑簇作为压缩索引的基本单元，以指示是否在范围内生成新的范围。
由此可见，操作系统性能的提升能力一定程度上取决于其所采用的文件系统，压缩算法是文件系统设计上尤其重要同时又是不可或缺的一环。按照以上思路，我们得到了具体实例，代码较多，我们对其进行整理，得到如下参考表格：
| 目录/设备 | 挂载点 | 文件系统 | 键值 | 备注 |
| /dev/block/dm-6 | / | erofs | ro,seclabel,relatime,user_xattr,lz4asm | 系统盘采用华为自研开源EROFS文件系统 面向终端场景 减小了元数据 随机读取性能有明显提高 |
| tmpfs | /storage | tmpfs | rw,seclabel,nosuid,nodev,noexec,relatime,size=3827176k,nr_inodes=956794,mode=755,gid=1000 | 内部存储目录 采用tmpfs临时文件系统 对应于/tmp或swap 在内存利用上有很大价值 |
| /dev/block/sdd72 | /data | f2fs | rw,seclabel,nosuid,nodev,noatime,background_gc=on,discard,no_heap,user_xattr,inline_xattr,acl,inline_data,inline_dentry,extent_cache,mode=adaptive,inline_encrypt,sdp_encrypt,active_logs=6,alloc_mode=default,fsync_mode=posix | 应用核心数据目录 采用18个月不卡的F2FS格式 减轻了存储器内部处理负担 |
| /dev/block/sdd66 | /metadata | ext4 | rw,seclabel,nosuid,nodev,noatime,discard,data=ordered | 各种元数据及缓存目录 采用常规第四代扩展格式 门槛相对较低 优化后可显著提高运行性能 |
| /dev/block/sdd7 | /sec_storage | ext4 | rw,context=u:object_r:teecd_data_file:s0,nosuid,nodev,noatime,discard,nodelalloc,data=journal | |
| /dev/block/sdd23 | /cache | ext4 | rw,seclabel,nosuid,nodev,noatime,data=ordered | |
| /data/media/0 | /mnt/mdfs/sdcard | hmdfs | rw,relatime,insensitive,merge_disable,ra_pages=128,account=10143583112313917499,recv_uid=1023,cache_dir=/data/misc_ce/0/kdfs/cache/16448759910518911873,real_dst=/mnt/mdfs/sdcard,offline_stash,dentry_cache | 数据媒体存取目录 采用鸿蒙全自研跨设备HMDFS 支持多设备数据融合 4倍Samba性能 |
| /mnt/media_rw | /mnt/mdfs/external_storage | hmdfs | rw,relatime,insensitive,merge_disable,ra_pages=128,account=10143583112313917499,recv_uid=1023,cache_dir=/data/misc_ce/0/kdfs/cache/14998924782874330279,real_dst=/mnt/mdfs/external_storage,no_offline_stash,dentry_cache,external_storage | |
| /data/media | /mnt/runtime/default/emulated | sdcardfs | rw,nosuid,nodev,noexec,noatime,fsuid=1023,fsgid=1023,gid=1015,multiuser,mask=6,derive_gid,default_normal,reserved=20MB,unshared_obb | 数据媒体运行时存取目录 sdcardfs管理被作为外部存储的/sdcard目录 若对其进行优化 外存性能的提高极其有助于系统整体性能的提高 |
7.2 L74固定大小输出算法
块格式
LZ4 是 LZ77 型压缩器，具有固定的、面向字节的编码。没有熵编码器后端，也没有成帧层。假设后者由系统的其他部分处理，这种设计有利于简易及速度，有助于以后进行优化、紧凑及增强功能。
压缩块格式
LZ4 压缩块由序列组成。序列是一组文字（未压缩的字节），后跟一个匹配副本。每个序列都从一个标记开始。标记是一个字节值，分为两个 4 位字段。因此，每个字段的范围从 0 到 15。第一个字段使用了标记的 4 个高比特位，它提供了要遵循的文字的长度。
如果字段值为 0，则没有文字。如果是15，那么需要多加一些字节来表示全长，然后每个额外的字节代表一个从 0 到 255 的值，该值被添加到前一个值以产生总长度。当字节值为 255 时，必须读取并添加另一个字节，以此类推。标记后面可以有任意数量的值为“255”的字节，无大小限制：
在标记和可选长度字节之后，是文字本身。它们的数量与之前解码的一样多（字面量长度），字面量可能为零。文字之后是匹配复制操作。它从偏移量开始，是一个 2 字节的值，采用小端格式（第一个字节是“低”字节，第二个是“高”字节），偏移量表示要复制的匹配的位置。例如，1 表示“当前位置 – 1 个字节”。最大偏移值为 65535，65536 及以上无法编码。0 是无效的偏移值。这种值的存在表示无效（损坏）块。
然后可以提取匹配长度。为此，我们使用第二个标记字段，即低 4 位。显然，这个值的范围是 0 到 15。但是在这里，0 意味着复制操作是最小的。匹配的最小长度称为 minmatch，为 4。因此，0 值表示 4 个字节，15 值表示 19+ 个字节。与文字长度类似，在达到可能的最高值 (15) 时，必须读取额外的字节，一次一个，值范围从 0 到 255。它们被添加到总数中以提供最终匹配长度。255 值意味着还有另一个字节要读取和添加。可以存在的可选“255”字节的数量没有限制。（注意：这指向大约 250 的最大可实现压缩比）。
解码匹配长度到达当前序列的末尾。下一个字节是另一个序列的开始。但在移动到下一个序列之前，这时需要使用解码的匹配位置和长度了。解码器将 matchlength 字节从匹配位置复制到当前位置。
在某些情况下，matchlength 可以大于 offset。因此，由于 match_pos + matchlength > current_pos，稍后要复制的字节尚未解码，这称为“重叠匹配”，需要特别小心处理。常见的情况是偏移量为 1，这意味着最后一个字节重复 matchlength 次。
区块限制终止
终止 LZ4 块需要特定的限制：
- 最后一个序列只包含文字，块在他们之后结束
- 输入的最后 5 个字节始终是文字。因此，最后一个序列至少包含 5 个字节
- 特别的，如果输入小于 5 个字节，则只有一个序列，它包含整个输入作为文字。空输入可以用零字节表示，解释为没有文字和匹配的最终标记
- 最后一个匹配必须在块结束前至少 12 个字节开始，紧随其后的是最后一个序列，它只包含文字
- 需要注意，不能压缩 < 13 字节的独立块，因为匹配必须复制“某些东西”，因此至少需要一个前字节
- 但是，当一个块可以引用另一个块的数据时，它可以立即以匹配方式而非文字开始，因此可以压缩正好为 12 个字节的块。
当某一个块不符合以上这些终止条件时，允许一致的解码器将会视该块为错误从而拒绝；这些条件是为了确保与各种历史解码器之间的兼容性，解码器在面向速度的设计中依赖它们。
参考文献
[1] Deorowicz S . Universal Lossless Data Compression Algorithms[J]. Philosophy Dissertation Thesis, 2003.
https://www.researchgate.net/publication/2910531_Universal_Lossless_Data_Compression_Algorithms
[2] Burrows M , Wheeler D J . A Block-Sorting Lossless Data Compression Algorithm[J]. technical report digital src research report, 1995.
https://www.researchgate.net/publication/2702058_A_Block-Sorting_Lossless_Data_Compression_Algorithm
[3] Gao X , Dong M , Miao X , et al. EROFS: a compression-friendly readonly file system for resource-scarce devices. 2019.
https://dl.acm.org/doi/abs/10.5555/3358807.3358821
[4] Ni G . Research on BWT and Classical Compression Algorithms[J]. Computer & Digital Engineering, 2010.
http://en.cnki.com.cn/Article_en/CJFDTOTAL-JSSG201011009.htm
[5] Farruggia A , Ferragina P , Frangioni A , et al. Bicriteria data compression[J]. Society for Industrial and Applied Mathematics, 2013.
https://xueshu.baidu.com/usercenter/paper/show?paperid=27a6024fe31d2cda63a5e79b34be6cfd
[6] Alakuijala J , Farruggia A , Ferragina P , et al. Brotli: A General-Purpose Data Compressor[J]. ACM Transactions on Information Systems, 2018, 37(1):1-30.
[7] Overview – The Hitchhiker’s Guide to Compression (go-compression.github.io)
https://go-compression.github.io/
[8] Wavelet Tutorial – Part 1
https://users.rowan.edu/~polikar/WTpart1.html
[9] Wavlet Tutorial – Part 2
https://users.rowan.edu/~polikar/WTpart2.html
[10] Wavelet Tutorial – Part 3
https://users.rowan.edu/~polikar/WTpart3.html
缩略语列表
| 缩写 | 英文 | 中文 |
| ANS | Asymmetric numeral systems | 非对称数字系统 |
| BSLDCA | The Block Sorting Lossless Data Compression Algorithm | 块排序无损数据压缩算法 |
| BTW | Burrows–Wheeler Transform | Burrows–Wheeler转换 |
| BWCA | Burrows-Wheeler Compression Algorithm | Burrows-Wheeler压缩算法 |
| CTW | Context Tree Weighting | 上下文树加权 |
| CWT | Continue Wavelet Transform | 连续小波变换 |
| DMC | Dynamic Markov Coding | 动态马可夫压缩 |
| DWT | Discrete Wavelet Transform | 离散小波变换 |
| EC | Entropy Coder | 熵编码器 |
| MCO | Multi-Criteria Optimisation | 多标准优化 |
| MTF | Move To Front Transform | 前移变换 |
| PPM | Prediction by Partial Matching | 通过部分匹配进行预测 |
| RLE-0 | Zero Run Length Encoding | 零游程编码 |
| STFT | Short-time Fourier transform | 短时傅里叶变换 |
| EROFS | Enhanced Read-Only File System | 增强只读文件系统 |
| CVE | Common Vulnerabilities and Exposures | 通用漏洞披露 |
ELT.ZIP是谁？
ELT<=>Elite(精英)，.ZIP为压缩格式，ELT.ZIP即压缩精英。
成员：
上海工程技术大学大二在校生 闫旭
合肥师范学院大二在校生 楚一凡
清华大学大二在校生 赵宏博
成都信息工程大学大一在校生 高云帆
黑龙江大学大一在校生 高鸿萱
山东大学大三在校生 张智腾
ELT.ZIP是来自6个地方的同学，在OpenHarmony成长计划啃论文俱乐部里，与来自华为、软通动力、润和软件、拓维信息、深开鸿等公司的高手一起，学习、研究、切磋操作系统技术…
写在最后：
OpenHarmony 成长计划—“啃论文俱乐部”（以下简称“啃论文俱乐部”）是在 2022年 1 月 11 日的一次日常活动中诞生的。截至 3 月 31 日，啃论文俱乐部已有 87 名师生和企业导师参与，目前共有十二个技术方向并行探索，每个方向都有专业的技术老师带领同学们通过啃综述论文制定技术地图，按“降龙十八掌”的学习方法编排技术开发内容，并通过专业推广培养高校开发者成为软件技术学术级人才。
啃论文俱乐部的宗旨是希望同学们在开源活动中得到软件技术能力提升、得到技术写作能力提升、得到讲解技术能力提升。大学一年级新生〇门槛参与，已有俱乐部来自多所高校的大一同学写出高居榜首的技术文章。
如今，搜索“啃论文”，人们不禁想到、而且看到的都是我们——OpenHarmony 成长计划—“啃论文俱乐部”的产出。
OpenHarmony开源与开发者成长计划—“啃论文俱乐部”学习资料合集
1）入门资料：啃论文可以有怎样的体验
https://docs.qq.com/slide/DY0RXWElBTVlHaXhi?u=4e311e072cbf4f93968e09c44294987d
2）操作办法：怎么从啃论文到开源提交以及深度技术文章输出https://docs.qq.com/slide/DY05kbGtsYVFmcUhU
3）企业/学校/老师/学生为什么要参与 & 啃论文俱乐部的运营办法https://docs.qq.com/slide/DY2JkS2ZEb2FWckhq
4）往期啃论文俱乐部同学分享会精彩回顾：
同学分享会No1.成长计划啃论文分享会纪要（2022/02/18） https://docs.qq.com/doc/DY2RZZmVNU2hTQlFY
同学分享会No.2 成长计划啃论文分享会纪要（2022/03/11） https://docs.qq.com/doc/DUkJ5c2NRd2FRZkhF
同学们分享会No.3 成长计划啃论文分享会纪要（2022/03/25）
https://docs.qq.com/doc/DUm5pUEF3ck1VcG92?u=4e311e072cbf4f93968e09c44294987d
现在，你是不是也热血沸腾，摩拳擦掌地准备加入这个俱乐部呢？当然欢迎啦！啃论文俱乐部向任何对开源技术感兴趣的大学生开发者敞开大门。
后续，我们会在服务中心公众号陆续分享一些 OpenHarmony 开源与开发者成长计划—“啃论文俱乐部”学习心得体会和总结资料。记得呼朋引伴来看哦。
扫码添加 OpenHarmony 高校小助手，加入“啃论文俱乐部”微信群