Page 438 - 《软件学报》2025年第10期

龚子睿 等: FBS-uBlock: 灵活的 uBlock 算法比特切片优化方法 4835

向量寄存器, 高端的有 32 个向量寄存器, 未来说不定会产生具有 64 个向量寄存器的处理器, 开发者可以根据处理
器平台的寄存器资源灵活选取最适合的比特切片表示法, 便利了 uBlock 算法的工程应用.

n
part-1 -bit
2r
part-2
n n
-bit r× -bit n
X 0 X 0 2r -bit part-1 part-2 ... part-r
2 ... 2r
part-r
r-part
n-bit
n
part-1 -bit n
2r -bit part-1 part-2 ... part-r
2r
part-2
n -bit n
X 1 2 X 1 r× 2r -bit ... r-part
part-r
图 5 FBS-uBlock 核心思想

uBlock 算法的比特切片表示法 FBS-uBlock 的详细描述如图 6 所示, 图 6 涉及的符号定义如表 4 所示. 图 6 展
示了 n 比特数据 X 在不同缩减比率 r 下的比特切片表示法, 占用的寄存器数量为 n/r 个, 需要一次性读入 n/(2r) 组
数据 X. 对于 uBlock-128/128 算法和 uBlock-128/256 算法, r 的取值为 1、2、4、8、16; 对于 uBlock-256/256 算法,
r 还可以取到 32.

图 6 uBlock 算法比特切片表示法

图 6 中, n/(2r) 组 n 比特数据 X 被转换成 n/r×n/2 大小的矩阵, 矩阵上半部分代表 X 的高 n/2 比特, 下半部分代
表 X 的低 n/2 比特. 矩阵的上半或下半部分可以看成 n/(2r)×r 的分块矩阵, 每个分块元素代表 X 的某个比特位. X
的比特位将按照列的顺序放置, 从左上角开始, 由上至下, 由左至右. 每个分块元素 b[i] 代表 n/(2r) 组数据 X 的第
i 比特位, 长度恰好是 n/(2r) 比特.