在我的80x86汇编程序中,我试图计算(((((2 ^ 0 + 2 ^ 1)*2 ^ 2)+ 2 ^ 3)*2 ^ 4)+ 2 ^ 5)的等式... (2 ^ n),其中每个偶数指数前面都有一个乘法,每个奇数指数前面都有一个加号.我有代码,但我的结果不断取决于所需的结果.当n为5时,结果应该是354,但是我得到330.
任何和所有的建议将不胜感激.
.586
.model flat
include io.h
.stack 4096
.data
number dword ?
prompt byte "enter the power", 0
string byte 40 dup (?), 0
result byte 11 dup (?), 0
lbl_msg byte "answer", 0
bool dword ?
runtot dword ?
.code
_MainProc proc
input prompt, string, 40
atod string
push eax
call power
add esp, 4
dtoa result, eax
output lbl_msg, result
mov eax, 0
ret
_MainProc endp
power proc
push ebp
mov ebp, esp
push ecx
mov bool, 1 ;initial boolean value
mov eax, 1
mov runtot, 2 ;to keep a running total
mov ecx, [ebp + 8]
jecxz done
loop1:
add eax, eax ;power of 2
test bool, ecx ;test case for whether exp is odd/even
jnz oddexp ;if boolean is 1
add runtot, eax ;if boolean is 0
loop loop1
oddexp:
mov ebx, eax ;move eax to seperate register for multiplication
mov eax, runtot ;move existing total for multiplication
mul ebx ;multiplication of old eax to new eax/running total
loop loop1
done:
mov eax, runtot ;move final runtotal for print
pop ecx
pop ebp
ret
power endp
end
您使用静态变量和分支过度复杂化代码.
这些是2的幂,你可以(而且应该)只是左移n而不是实际构造2^n和使用mul指令.
add eax,eax是乘以2的最佳方法(又称左移1),但不清楚为什么你在这一点上对EAX中的值这样做.它可以是乘法结果(您可能应该将其存储回runtot之后mul),或者是偶数迭代后左移1.
如果你试图创建一个2^i变量(强度降低优化每次迭代移1而不是移位i),那么你的错误就是你mul在oddexp块中破坏了EAX 及其设置.
正如杰斯特所指出的那样,如果第一次loop loop1失败,它将会陷入oddexp:.当你进行循环尾部复制时,如果循环在那里结束,请确保考虑每个尾部的落入点.
有一个静态变量被称为bool持有a 1,你只能用它作为操作数test.这意味着人类读者有时需要改变面具; test ecx,1作为检查零/非零的低位的方法更清楚.
您也不需要静态存储runtot,只需使用寄存器(如最终您想要结果的EAX).32位x86有7个寄存器(不包括堆栈指针).
我就是这样做的.未经测试,但我通过展开2简化了很多.然后奇数/偶数的测试消失了,因为交替模式被硬编码到循环结构中.
我们在循环中递增和比较/分支两次,因此展开没有摆脱循环开销,只是将其中一个循环分支更改为if() break可以从中间离开循环的a.
这不是写这个的最有效方式; 循环中间的增量和早退出检查可以通过计算另一个计数器来优化n,如果剩下少于2个步骤则离开循环.(然后在结语中排序)
;; UNTESTED
power proc ; fastcall calling convention: arg: ECX = unsigned int n
; clobbers: ECX, EDX
; returns: EAX
push ebx ; save a call-preserved register for scratch space
mov eax, 1 ; EAX = 2^0 running total / return value
test ecx,ecx
jz done
mov edx, ecx ; EDX = n
mov ecx, 1 ; ECX = i=1..n loop counter and shift count
loop1: ; do{ // unrolled by 2
; add 2^odd power
mov ebx, 1
shl ebx, cl ; 2^i ; xor ebx, ebx; bts ebx, ecx
add eax, ebx ; total += 2^i
inc ecx
cmp ecx, edx
jae done ; if (++i >= n) break;
; multiply by 2^even power
shl eax, cl ; total <<= i; // same as total *= (1<<i)
inc ecx ; ++i
cmp ecx, edx
jb loop1 ; }while(i<n);
done:
pop ebx
ret
我没有检查加 - 奇 - 功率步是否会产生进位到另一位.我认为它没有,因此将其实现为bts eax, ecx(设置位i)可能是安全的.实际上是OR而不是ADD,但只要该位先前被清除,它们就是等效的.
为了让asm看起来更像源代码并避免模糊指令,我实现1<<i了shl生成2^ifor total += 2^i,而不是更高效的Intel xor ebx,ebx/ bts ebx, ecx.(英特尔Sandybridge系列的可变计数转换为3 uop,因为x86标志处理传统行李:如果count = 0,则标志必须不受影响).但是AMD Ryzen的情况更糟糕,其中bts reg,reg2 uops但是shl reg,cl1.
更新:在添加时i=3 确实产生进位,因此我们不能对该情况进行OR或BTS.但是通过更多分支可以实现优化.
; define shiftadd_power(n) { local res=1; local i; for(i=1;i<=n;i++){ res+=1<<i; i++; if(i>n)break; res<<=i;} return res;}
shiftadd_power(n) defined
; base2(2)
; shiftadd_power(0)
1 /* 1 */
...
前几个产出是:
n shiftadd(n) (base2)
0 1
1 11
2 1100
3 10100 ; 1100 + 1000 carries
4 101000000
5 101100000 ; 101000000 + 100000 set a bit that was previously 0
6 101100000000000
7 101100010000000 ; increasing amounts of trailing zero around the bit being flipped by ADD
剥离前3次迭代将启用BTS优化,您只需设置该位而不是实际创建2^n和添加.
取而代之的只是剥他们,我们就可以硬编码的起点,i=3对于更大的n,和优化计算出的返回值的代码n<3的情况.我想出了一个无分支的公式,基于将0b1100位模式右移3或2或0.
另请注意,对于n> = 18,最后一次移位计数严格大于寄存器宽度的一半,而奇数中的2 ^ i i没有低位.因此,只有最后的1或2次迭代才会影响结果.归结1<<n为奇数n或0偶数n.这简化为(n&1) << n.
因为n=14..17,最多设置2位.从result = 0开始,进行最后3或4次迭代应足以获得正确的总数.事实上,对于任何一个n,我们只需要进行最后的k迭代,其中k足够的偶数的总移位计数i> = 32.由早期迭代设置的任何位都被移出.(我没有为这个特例增加一个分支.)
;; UNTESTED
;; special cases for n<3, and for n>=18
;; enabling an optimization in the main loop (BTS instead of add)
;; funky overflow behaviour for n>31: large odd n gives 1<<(n%32) instead of 0
power_optimized proc
; fastcall calling convention: arg: ECX = unsigned int n <= 31
; clobbers: ECX, EDX
; returns: EAX
mov eax, 14h ; 0b10100 = power(3)
cmp ecx, 3
ja n_gt_3 ; goto main loop or fall through to hard-coded low n
je early_ret
;; n=0, 1, or 2 => 1, 3, 12 (0b1, 0b11, 0b1100)
mov eax, 0ch ; 0b1100 to be right-shifted by 3, 2, or 0
cmp ecx, 1 ; count=0,1,2 => CF,ZF,neither flag set
setbe cl ; count=0,1,2 => cl=1,1,0
adc cl, cl ; 3,2,0 (cl = cl+cl + (count<1) )
shr eax, cl
early_ret:
ret
large_n: ; odd n: result = 1<<n. even n: result = 0
mov eax, ecx
and eax, 1 ; n&1
shl eax, cl ; n>31 will wrap the shift count so this "fails"
ret ; if you need to return 0 for all n>31, add another check
n_gt_3:
;; eax = running total for i=3 already
cmp ecx, 18
jae large_n
mov edx, ecx ; EDX = n
mov ecx, 4 ; ECX = i=4..n loop counter and shift count
loop1: ; do{ // unrolled by 2
; multiply by 2^even power
shl eax, cl ; total <<= i; // same as total *= (1<<i)
inc edx
cmp ecx, edx
jae done ; if (++i >= n) break;
; add 2^odd power. i>3 so it won't already be set (thus no carry)
bts eax, edx ; total |= 1<<i;
inc ecx ; ++i
cmp ecx, edx
jb loop1 ; }while(i<n);
done:
ret
通过使用BTS在EAX中设置一个位,避免了需要额外的临时寄存器来构造1<<i,因此我们不必保存/恢复EBX.所以这是一个小额奖励.
请注意,这次输入的主循环i=4是偶数,而不是i=1.所以我交换了添加与转移.
我仍然没有得到解决,以拉动cmp/ jae圈外的中间.喜欢的东西lea edx, [ecx-2],而不是mov将设置循环退出条件,但需要检查不运行循环在所有的I = 4或5.对于大数量的吞吐量,许多CPU可以维持1 +取1不采取分支的每个2个时钟,没有产生比循环携带的dep链(通过eax和ecx)更糟糕的瓶颈.但是分支预测会有所不同,它使用更多的分支顺序缓冲区条目来记录更多可能的回滚/快速恢复点.
| 归档时间： |
|
| 查看次数： |
102 次 |
| 最近记录： |