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

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

uBlock 算法的线性变换 B 中主要的运算是 32 比特循环移位, X 0 和 X 1 在进行循环移位时会被分成数段 32 比
特数据, 每段独立执行循环移位. 因此, 在线性变换 B 中可以从两个角度减少占用的寄存器数量, 一个角度是针对
32 比特循环移位模块的内部, 在表示 32 比特的数据时减少寄存器的占用; 另一个角度是针对并行的多个 32 比特
循环移位模块之间, 通过按行并置多个模块来减少寄存器占用. 因为“针对模块内”增加了循环移位指令的代价, 而
“针对模块间”没有额外代价, 故在减少寄存器占用数量时首先采用“针对模块间”的方式.
针对循环移位模块内, 如果将 32 比特数据写成列向量的形式, 异或运算变成模 2 加法, 循环移位转变成矩阵
乘法 M ROL ×x 的形式, 那么 x′ = x ⊕(y<<<4) 可以表示成公式 (1) 的形式. 通过观察公式 (1) 中矩阵 M RO 的值可以
L
发现, 矩阵 M RO 恰好是每一行循环右移 4 位的单位矩阵.
L

 ′       
 x  x 0   00010000...   y 0 
 0        
       
       
       
 x ′         

 
   x 1   00001000...   y 1 
 
 1        
       
       
       
 x ′         

 
 2   x 2   00000100...   y 2 

 
       
       
     .   
 .    .   .   .  


 
 
′
x = x⊕ M ROL ×y ⇔  .    .  +  .   .  (1)

 .  =  .  
 ×  . 
 
 
         
       
       
       
 x ′         

 

 
   x 29   01000000...   y 29 
 29       
       
       
       
 x ′         

 
 
   x 30   00100000...   y 30 

 30       
       
       
       
x ′ x 31 00010000... y 31
31
进一步观察可以发现, 矩阵 M RO 是一个循环矩阵, 如果把 M RO 写成 2×2、4×4、8×8 或 16×16 的分块矩阵
L
L
后, 分块矩阵也是循环矩阵. 因此, 如果将数据写成一个二维的矩阵, 将循环移位运算对应的矩阵 M RO 写成分块
L
矩阵的形式, 那么公式 (1) 将转变成公式 (2)–(4) 的形式. 为了简化表达式, 在公式 (2)–(4) 中使用符号 x i– 代表由
j
x i , x i+1 , ..., x j 组成的列向量.

[ ] [ ] [ ] [ ]
x ′ 0−15 x 0−15 A B y 0−15 [ ′ ′ ]
x ′ = x 16−31 + B A × y 16−31 ⇔ x 0−15 x 16−31
16−31
[ ] [ ] [ ]
= x 0−15 x 16−31 +[A]× y 0−15 y 16−31 +[B]× y 16−31 y 0−15 (2)

 ′       
 x  x 0−7   A B C D   y 0−7 
 0−7        
       
 x ′    x 8−15   D A B     [ ]

 

 
 8−15   C   y 8−15  ′ ′ ′ ′
 
         ⇔ x x x x
  =   +   × 
 x ′    x 16−23   C D A     0−7 8−15 16−23 24−31


 
 
   B   y 16−23 
 
 16−23       
       
x ′ x 24−31 B C D A y 24−31
24−31
[ ] [ ]
= x 0−7 x 8−15 x 16−23 x 24−31 +[A]× y 0−7 y 8−15 y 16−23 y 24−31
[ ] [ ]
+[B]× y 8−15 y 16−23 y 24−31 y 0−7 +[C]× y 16−23 y 24−31 y 0−7 y 8−15
[ ]
(3)
+[D]× y 24−31 y 0−7 y 8−15 y 16−23

 ′       
 x  x 0−3   A B ... H   y 0−3 
 0−3        
       
 x ′    x 4−7   H A ...    

 

 
 
 4−7   G   y 4−7  [ ]
       
        ′ ′ ′

 + 
 .  =  .   . . . ×  .  ⇔ x x ... x
   .   0−3 4−7 28−31
 
 .   .   . . .   . 
     . . .   
 .   . . .   . 
       
       
       
x ′ 28−31 x 28−31 B C ... A y 28−31
[ ] [ ]
= x 0−3 x 4−7 ... x 28−31 +[A]× y 0−3 y 4−7 ... y 28−31
[ ] [ ]
... ...
(4)
+[B]× y 4−7 y 28−31 y 0−3 +...+[H]× y 28−31 y 0−3 y 24−27
观察公式 (2)–(4) 等号右侧数据 y 的表示, 可以发现公式对数据进行了循环的变换, 按照列的单位进行了循环
左移. 可以验证, 对于 32 比特数的循环 4、8、20 移位运算, 都可以有类似的表示方式. 上述理论分析表明, 可以通
过引入一些循环移位运算来降低列向量的行数. 在比特切片的表示中, 数据每一行代表一个寄存器, 行数的降低意
味着寄存器占用数量的减少, 从而能够达到减少访存开销的目的.
对于线性变换 B 的运算 x′ = x ⊕(y<<<s), s∈{0, 4, 8, 20}, 将数据 x 和 y 都表示成 k×(32/k) 的矩阵 M x 和 M y , 用
符号 Reg (x) 表示 x 的比特切片表示下的第 i 个寄存器, 所有表示形式的计算方式可通过公式 (5) 概括. 数据 x 第 i
i