selph
selph
发布于 2022-04-02 / 393 阅读
0
0

《xchg rax,rax》片段分析0x21--多项式乘法

前言

本次是该系列的的第0x21篇,是个数学相关的示例


实验环境:

  • Windows10 + VS2022 + masm

0x21

代码片段链接:xorpd | xchg rax,rax 0x21

mov      rsi,rax
add      rax,rbx
mov      rdi,rdx
sub      rdx,rcx
add      rdi,rcx

imul     rax,rcx
imul     rsi,rdx
imul     rdi,rbx

add      rsi,rax
mov      rbx,rsi
sub      rax,rdi

代码分析

测试代码:

.code
main proc
    mov      rax, 001h
	mov		 rbx, 002h
	mov		 rcx, 003h
	mov		 rdx, 004h

	mov      rsi,rax	;rsi = rax		 
	add      rax,rbx	;rax = rax + rbx 
	mov      rdi,rdx	;rdi = rdx		 
	sub      rdx,rcx	;rdx = rdx - rcx 
	add      rdi,rcx	;rdi = rdi + rcx

	imul     rax,rcx	;rax = rax * rcx ; (rax + rbx) * rcx
	imul     rsi,rdx	;rsi = rsi * rdx ; rax * (rdx - rcx) 
	imul     rdi,rbx	;rdi = rdi * rbx ; rbx * (rdx + rcx)

	add      rsi,rax	;rsi = rsi + rax ; (rax + rbx) * rcx + rax * (rdx - rcx) = rbx * rcx + rax * rdx
	mov      rbx,rsi	;rbx = rsi		 
	sub      rax,rdi	;rax = rax - rdi ; (rax + rbx) * rcx - rbx * (rdx + rcx) = rax * rcx - rbx * rdx

	ret
main ENDP
END

这里最后的输出和最初的输入的关系:

rax = rax * rcx - rbx * rdx
rbx = rax * rdx + rbx * rcx

(参考资料[1])这对应于两个复数的乘法:(a + bi) * (c + di) = (ac - bd) + (ad + bc)i。

注意,它只使用了三次乘法来计算结果中的四种不同的乘积。这就是多项式乘法的Karatsuba算法的精髓。

参考资料


评论