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

4834 软件学报 2025 年第 36 卷第 10 期

比特在矩阵 M x 中的行列坐标是 (i mod k, i/k), y<<<s 的第 i 比特在矩阵 M y 中的行列坐标是 ((i+s) mod k, (i+s)/k).
为了执行 (i mod k, i/k) 和 ((i+s) mod k, (i+s)/k) 这两个比特位的异或, 行坐标的差异通过改变寄存器的索引抵消, 列
坐标的差异 Δ = (i+s)/k – i/k 通过循环左移抵消.

i
( (⌊ i+ s ⌋ ⌊ ⌋))
(x)
Reg (x ′ ) = Reg ⊕ Reg (y) <<< − , i ∈ [0,k −1] (5)
i i (i+s) mod k
k k
图 4 是其中一种循环移位情况的示例. 假定矩阵 k=8, 循环移位的位数 s=20, 那么移位后序号 i 为 2 的寄存器
Reg (y<<<20) 可通过令移位前序号为 6 的寄存器 Reg (y) 循环左移 2 个单位来计算.
2 6

M y⋘20 : 未知 M y : 已知
Reg (y)
Reg (y⋘20) Y20 Y28 Y4 Y12 0 Y0 Y8 Y16 Y24
0
Reg (y⋘20) ⋮ ⋮ ⋮ ⋮ ⋮
1 Y20 Y29 Y5 Y13
循环左移2个单位
Reg (y)
Reg (y⋘20) Y22 Y30 Y6 Y14 5 Y5 Y13 Y21 Y29
2
Reg (y)
⋮ ⋮ ⋮ ⋮ ⋮ 6 Y6 Y14 Y22 Y30
Reg (y⋘20) Reg (y) Y7 Y15 Y23 Y31
7 Y27 Y3 Y11 Y19 7
图 4 循环移位计算示例

针对循环移位模块间, 当分组比特是 128 比特时, X 0 (和 X 1 ) 是 64 比特长度, 这意味着 X 0 (和 X 1 ) 可以从 64×1
的列向量表示成 32×2 的二维矩阵形式; 当分组比特是 256 比特时, X 0 (和 X 1 ) 是 128 比特长度, 表示 X 0 (和 X 1 ) 可
以从 128×1 的列向量表示成 64×2 或 32×4 的二维矩阵形式. 这从另一角度减少了比特切片所占用的寄存器数量.
uBlock 算法的 PL 和 PR 两个模块都是字节粒度的重排操作, 字节重排会让不同字节比特位的相对位置发生
改变, 所以切片后的一个字节内不应该包含 2 个不同字节的比特位, 让切片后的数据仍然能够以字节为单位进行
重排, 进而使用 SIMD 指令集中的重排指令快速实现.
3.2 比特切片表示法 FBS-uBlock
经过第 3.1 节的分析, 可以得到下面 4 个要点, 用于指导 uBlock 算法比特切片表示法的设计.
(1) 通过考虑迭代过程的数据结构, 说明在减少寄存器占用数量时应分别对 X 0 和 X 1 进行.
(2) 通过考虑非线性的 S 盒部分, 说明当 n=128 时, 寄存器最少是 n/16=8 个. 此时 X 0 和 X 1 恰好各占用 4 个寄
存器, 满足 4 比特 S 盒的计算要求, 再减少则会对 S 盒的计算造成影响.
(3) 通过考虑线性变换 B 部分, 说明将“竖”着的元素“横”着摆放是可行的.
(4) 通过考虑线性变换 PL/PR 部分, 给出了数据比特位在寄存器中存储的约束条件.
图 5 是本文针对 uBlock 算法的比特切片优化思想. 对于 n 比特分组长度的数据 X, 把 X 拆分成 n/2 比特长度
的 X 0 和 X 1 分别进行处理; 以 X 0 为例, 将 n/2 比特的列向量看作是 1×n/2、2×n/4、4×n/8、8×n/16、16×n/32 的表
示; 将“竖”着的元素“横”着摆放, 可以得到 n/2、n/4、n/8、n/16、n/32 行的数据; 每一行表示一个寄存器, 所以 X
得到需要 n、n/2、n/4、n/8 和 n/16 个寄存器的比特切片表示法.
本文提出的比特切片优化方法 FBS-uBlock 是灵活的, 可以从方法和应用这两个层面体现.
(1) 方法层面, 本文提出的 uBlock 算法比特切片优化方法在寄存器的占用数量上是灵活可调的. 本文并没有
提出一种固定的比特切片表示法, 而是以一种减少寄存器占用数量的思想为引子, 构造了多种不同的 uBlock 算法
比特切片表示法. 核心思想是在线性变换 B 中对数据矩阵重新表示, 由一维的列向量转变成二维的矩阵, 由“线”转
变至“面”, 减少行数, 进而减少寄存器数量. 借助这个思想, 在不同的场景需求下, 可以灵活构造出占用不同寄存器
数量的比特切片表示法.
(2) 应用层面, 本文提出的 uBlock 算法比特切片优化方法是一系列针对 uBlock 算法的比特切片表示法, 能够
灵活适用于不同的处理器平台. 以 ARM 架构的处理器平台为例, 低端的处理器只有 16 个供 NEON 指令集操作的