我正在尝试用ARM汇编语言实现布斯乘法算法。
Algorithm 2: Booth’s Algorithm to multiply two 32-bit numbers to produce a 64-bit result
Data: Multiplier in V , U = 0, Multiplicand in N
Result: The lower 64 bits of UV contain the result
1 i←0
2 prevBit ← 0
3 fori<32do
4 i←i+1
5 currBit ← LSB of V
6 if (currBit,prevBit) = (1,0) then
7 U←U−N
8 end
9 else if (currBit,prevBit) = (0,1) then
10 U←U+N
11 end
12 prevBit ← currBit
13 UV ← UV ≫ 1 (arithmetic right shift)
14 end
字符串
如何执行算法的第13步?如何对两个寄存器中存储为32位部分的64位数执行asr?
我已经尝试在两个寄存器上执行asr,然后对于低32位,我用高32位的LSB替换MSB(在执行asr之前存储)。
1条答案
按热度按时间2ul0zpep1#
询问编译器:
int64_t asr_1(int64_t a){ return a>>1; }
。Godbolt编译器资源管理器,带GCC和clang for ARM
在标准调用约定中,第一个arg和返回值都在R1:R 0中,因此编译器将使asm就地操作。对于移位计数为1,Clang使用Carry标志从高半部分的底部到低半部分的顶部获取位。
字符串
GCC不使用进位标志,它和clang使用相同的策略来处理2到31之间的移位计数。**
int64_t
的低半部分是无符号的;**逻辑移位会留下零,您可以从高半部分的某些位进行OR。对于1
的计数,这种策略比rrx
技巧效率低,除非rrx
在某些CPU上很慢。型
Clang with
-mthumb
奇怪地在rrx
之前使用asrs.w
,但对于return a>>(32+5);
仍然使用普通的asrs
(16位),这很容易:asrs r0, r1, #5
;asrs r1, r1, #31
(返回瓦尔的高半部分是全0或全1,根据符号位)。使用
asrs.w
没有任何正确的理由。asrs
可以编码为16位Thumb指令,尽管rrx
只适用于Thumb 2。这不需要ARMv 8或任何东西,事实上clang -march=armv4t
仍然使用它;我只是倾向于使用-mcpu=cortex-a77
或a53
,因为它是最近的,很容易想到,我想知道是否有任何新的技巧,以及适合现代ARM内核的调优选择。cortex-m3
或m0
也与某些项目相关。M0明显缺乏大多数Thumb 2编码:型
变量计数移位比较困难,但编译器仍然可以使用 predicate 执行向您展示如何实现。
型
ARM移位计数>= 32时,移位所有位,产生逻辑移位的零。因此,如果它实际上是我们需要的其他位,则
r1, lsl r3
源操作数为零。而asr r1, r1, r2
设置高半部分的工作原理与r2==32或更高时的asr r1, #31
类似;它仍然是原始输入移位计数。