我正在用汇编程序编写C子程序,需要在传入的4个值中找到2个最大的值并将它们相乘。我正在努力寻找最大的值,但我有点卡住了。我用这个来求最大值,但我不知道怎么求第二高。如有任何建议,不胜感激。
first:
push bp
mov bp,sp
mov ax,[bp+4]
mov [max1],ax
cmp ax,[bp+6]
jge skip1
mov ax,[bp+6]
mov max1,ax
skip1:
mov ax,max1
cmp ax,[bp+8]
jge skip2
mov ax,[bp+8]
mov max1,ax
skip2:
mov ax,max1
cmp ax,[bp+10]
jge mult
mult:
mul [max1],[max2]
jmp fin
fin:
pop bp
ret
end
想必您不是在寻找SIMD答案,但我认为写起来会很有趣。是的,SSE指令在16位模式下工作。使用AVX编码的指令则没有,因此不能使用AVX的3操作数版本。幸运的是,我能够在没有任何额外的MOVDQA指令的情况下编写它,所以AVX不会有帮助。
我知道如何在不做功课的情况下以你可能想要的方式回答这个问题。如果你真的对高性能的实现感兴趣,而不仅仅是工作,请更新你的问题。
由于您只需要返回两个最大的数的乘积,因此您可以生成所有6个成对乘积并取最大值。(4选2 = 6).
如果暴力破解不起作用,说明你使用得不够:p
update:我刚刚意识到,如果最大的两两乘积来自两个负数,这将给出错误的答案。如果你能排除负输入,它将工作,否则排除输入,这是一个问题。参见下面的SSE4.1版本,分别找到max和2nd-max。
这在没有分支的情况下使用了SSE2。(您可以只使用SSE1在MMX寄存器中做同样的事情,它添加了PMAXSW的MMX寄存器版本)。它只有11条指令(不包括序言/尾声),它们都很快,在大多数cpu上都是单线程的。(参见x86标签wiki获取更多x86链接)
;; untested, but it does assemble (with NASM)
BITS 16
;; We only evaluate 16-bit products, and use signed comparisons on them.
max_product_of_4_args:
push bp
mov bp, sp
; load all 4 args into a SIMD vector
movq xmm0, [bp+4] ;xmm0 = [ 0...0 d c b a ] (word elements)
pshuflw xmm1, xmm0, 0b10010011 ;xmm1 = [ 0.. c b a d ] (rotated left)
pshufd xmm2, xmm0, 0b11110001 ;xmm2 = [ 0.. b a d c ] (swapped)
pmullw xmm1, xmm0 ; [ 0.. cd bc ab ad ] (missing ac and bd)
pmullw xmm2, xmm0 ; [ 0.. bd ac bd ac ]
; then find the max word element between the bottom halves of xmm1 and xmm2
pmaxsw xmm1, xmm2
; now a horizontal max of xmm1
pshuflw xmm0, xmm1, 0b00001110 ; elements[1:0] = elements[3:2], rest don't care
pmaxsw xmm0, xmm1
pshuflw xmm1, xmm0, 0b00000001
pmaxsw xmm0, xmm1
; maximum product result in the low word of xmm0
movd eax, xmm0
; AX = the result. Top half of EAX = garbage. I'm assuming the caller only looks at a 16-bit return value.
; To clear the upper half of EAX, you could use this instead of MOVD:
;pextrw eax, xmm0, 0
; or sign extend AX into EAX with CWDE
fin:
pop bp
ret
end
如果您想要32位产品,PMAXSD是SSE4.1的一部分。也许用零解包(或PMOVZXWD),并使用PMADDWD进行16b * 16b->32b向量乘法。对于奇数元素都为零的情况,PMADDWD的水平加法部分只得到偶数元素的有符号乘法的结果。
有趣的事实:在16位模式下,MOVD和pextrw eax, xmm0, 0
不需要操作数大小的前缀来写入eax。66
前缀已经是所需编码的一部分。pextrw ax, xmm0, 0
不组装(与NASM)。
趣事#2:ndisasm -b16
错误地将MOVQ加载反汇编为movq xmm0, xmm10
:
$ nasm -fbin 16bit-SSE.asm
$ ndisasm -b16 16bit-SSE
...
00000003 F30F7E4604 movq xmm0,xmm10
...
$ objdump -b binary -Mintel -D -mi8086 16bit-SSE
...
3: f3 0f 7e 46 04 movq xmm0,QWORD PTR [bp+0x4]
...
设计音符为2次洗牌,2次乘法。
[ d c b a ] ; orig
[ c b a d ] ; pshuflw
cd bc ab ad : missing ac and bd
[ b a d c ] ; pshuflw. (Using psrldq to shift in zeros would produce zero, but signed products can be < 0)
;; Actually, the max must be > 0, since two odd numbers will make a positive
我试图通过为它创建两个洗牌的输入来只执行一个PMULLW。使用PSHUFB(使用16字节的掩码常量)会很容易。
但我试图将其限制为SSE2(也许代码可以适应MMX)。这是一个没有成功的想法。
[ d d c c b b a a ] ; punpcklwd
[ b a b a b a d c ] ; pshufd
bd ad bc ac bb ab ad ac
: ab ac ad
: bc bd
: cd(missing)
: bb(problem)
我甚至不确定那样会更好。它需要额外的洗牌来获得水平最大值。(如果我们的元素是无符号的,也许我们可以在0 - vec上使用SSE4.1 phminpossuw一次性找到最大值,但OP使用的是有符号比较。)
SSE4.1 PHMINPOSUW
可以给每个元素加32768,然后使用无符号元素
给定一个带符号的16位val: rangeshift = val + 1<<15
将最小值映射为0,最大值映射为65535。(加,减,或异或(加不进位)都是等价的。)
因为我们只有一个找到水平最小值的指令,我们可以用否定来反转这个范围。我们需要先做,因为0保持为0,而0xFFFF变为0x0001,等等。
因此-val + 1<<15
或mapped = 1<<15 - val
将有符号值映射为无符号值,以这样的方式,最小的无符号值是最大的有符号值。val = 1<<15 - mapped
.
然后我们可以使用PHMINPOSUW来查找最低的(无符号)单词元素(最大原始元素),将其掩码为all- 1,然后再使用PHMINPOSUW来查找第二低的
push bp
mov bp, sp
pcmpeqw xmm5, xmm5 ; xmm5 = all-ones (anything compares == itself)
psrlw xmm5, 15 ; _mm_set1_epi16(1<<15)
movq xmm0, [bp+4]
psubw xmm5, xmm0 ; map the signed range to unsigned, in reverse order
phminposuw xmm1, xmm5 ; xmm1 = [ 0... minidx minval ]
movd eax, xmm1 ; ax = minval
psrldq xmm1, 2 ; xmm1 = [ 0... minidx ]
psllw xmm1, 4 ; xmm1 = [ 0... minidx * 16 ]
pcmpeqw xmm2, xmm6
psrlq xmm2, 48 ; xmm2 = _mm_set1_epi64(0xFFFF)
psllq xmm2, xmm1 ; xmm2 = _mm_set1_epi64(0xFFFF << (minidx*16))
; force the min element to 65535, so we can go again and get the 2nd min (which might be 65535, but we don't care what position it was in)
por xmm2, xmm5
phminposuw xmm3, xmm2
movd edx, xmm3 ; dx = 2nd min, upper half of edx=garbage (the index)
mov cx, 1<<15 ; undo the range shift
neg ax
add ax, cx
sub cx, dx
imul cx ; signed multiply dx:ax = ax * cx
pop bp
ret ; return 32-bit result in dx:ax (or caller can look at only the low 16 bits in ax)
这是更多的说明。它可能不会比使用整数寄存器的CMP/CMOV排序网络更好。(请参阅@Terje的评论,以获得使用比较和交换的建议)。
这是我处理四个16位无符号整数输入数字 (80x86+处理器兼容)之间的最大值的第一个解决方案:
Procedure Max4; Assembler;
{ Input: AX, BX, CX, DX
Output: AX= MAX(AX,BX,CX,DX).
Temp: DI}
Asm
{ Input: AX, BX
Output: AX= MAX(AX,BX).
Temp: DI}
Sub AX,BX
CmC
SbB DI,DI
And AX,DI
Add AX,BX
{ Input: CX, DX
Output: CX= MAX(CX,DX).
Temp: DI}
Sub CX,DX
CmC
SbB DI,DI
And CX,DI
Add CX,DX
{ Input: AX, CX
Output: AX= MAX(AX,CX).
Temp: DI}
Sub AX,CX
CmC
SbB DI,DI
And AX,DI
Add AX,CX
End;
我的过程Max4(),相当于AX=Max4(AX,BX,CX,DX),可以工作伟大的一个AX=Max(AX,BX)子例程返回两个数字之间的最大值它用了三次:
AX = Max (Max (AX, BX)、马克斯(CX) DX))
AX = Max (AX, BX) 子路径是遵循:
1) Diff=AX-BX.
2) If Diff>=0 then AX is the greatest number,
Output= Diff+BX= AX-BX+BX= AX.
3) If Diff<0 then BX is the greatest number,
must set Diff to 0,
Output= Diff+BX= 0+BX= BX.
在ASSEMBY: { Input: AX, BX
Output: AX= MAX(AX,BX).
Temp: DI}
Sub AX,BX
{Diff= AX-BX}
CmC
{If Diff>=0 -> FCarry=1 else FCarry=0}
SbB DI,DI
{If Diff>=0 -> DI=DI-DI-1==-1 else DI=DI-DI-0==0}
And AX,DI
{If Diff>=0 -> Diff=(Diff & -1)==Diff else Diff=(Diff & 0)==0}
Add AX,BX
{AX= Diff+BX}
但是这个解决方案只适用于无符号16位数字,并且只处理一个最大的数字(不做乘法)。下一个解决方案在80x86+处理器上正确工作(适用于有符号整数;处理两个最大的数):
Function Max42R(A,B,C,D:Integer):LongInt; Assembler;
Asm
Mov AX,A
Mov BX,B
Mov CX,C
Mov DX,D
{1ø swap (when needed), 1ø scan}
Cmp AX,BX
JLE @01
XChg AX,BX
{2ø swap (when needed), 1ø scan}
@01:Cmp BX,CX
JLE @02
XChg BX,CX
{3ø swap (when needed), 1ø scan}
@02:Cmp CX,DX
JLE @03
XChg CX,DX
{1ø swap (when needed), 2ø scan}
@03:Cmp AX,BX
JLE @04
XChg AX,BX
{2ø swap (when needed), 2ø scan}
@04:Cmp BX,CX
JLE @05
XChg BX,CX
{DX is the first greatest number;
CX is the second greatest number}
@05:Mov AX,DX
Mul CX
End;
是冒泡排序算法的变体。在冒泡排序中,必须比较数组中相邻的每对数字如果第一个比第二个大,交换它们;如果发生了交换,则重复数组扫描,直到对数组进行排序。但是在第一次扫描之后,数组的最后一个值总是最大的。假设四个输入值与虚数组中的相同,仅在需要时,我交换的前三对寄存器,以获得的第一个最大值,
即最后寄存器中的。之后,仅在需要时,我交换前两对寄存器,以获得第二大值,即倒数第二的 .
Max4()程序可以在80386+处理器上编写,如下(支持32位有符号整数;处理一个最大的数字):
Function Max4I(A,B,C,D:Integer):Integer; Assembler;
{ Input: EAX, EBX, ESI, EDI
Output: EAX= MAX(EAX,EBX,ESI,EDI).
Temp: CX.
EAX EDX ECX are 1°, 2° AND 3° PARAMETERs.
Can freely modify the EAX, ECX, AND EDX REGISTERs. }
Asm
Push EBX
Push EDI
Push ESI
{------------------------}
Mov EAX,A
Mov EBX,B
Mov ESI,C
Mov EDI,D
{ Input: EAX, EBX
Output: EAX= MAX(EAX,EBX).
Temp: ECX}
Sub EAX,EBX
Mov ECX,0
SetL CL
Dec ECX
And EAX,ECX
Add EAX,EBX
{ Input: EAX, ESI
Output: EAX= MAX(EAX,ESI).
Temp: ECX}
Sub EAX,ESI
Mov ECX,0
SetL CL
Dec ECX
And EAX,ECX
Add EAX,ESI
{ Input: EAX, EDI
Output: EAX= MAX(EAX,EDI).
Temp: ECX}
Sub EAX,EDI
Mov ECX,0
SetL CL
Dec ECX
And EAX,ECX
Add EAX,EDI
{------------------------}
Pop ESI
Pop EDI
Pop EBX
End;
最后得到两个最大的确定解四个32位有符号整数之间的数字(80386+处理器)。它作为Max42R()函数工作:
Function Max42(A,B,C,D:Integer):Integer; Assembler;
{ Input: EAX, EBX, ESI, EDI
Output: EDI= 1° MAX(EAX,EBX,ESI,EDI).
ESI= 2° MAX(EAX,EBX,ESI,EDI).
Temp: ECX, EDX.
EAX EDX ECX are 1°, 2° AND 3° PARAMETERs.
Can freely modify the EAX, ECX, AND EDX REGISTERs. }
Asm
Push EBX
Push EDI
Push ESI
Mov EAX,A
Mov EBX,B
Mov ESI,C
Mov EDI,D
{ Input: EAX, EBX
Output: EAX= MIN(EAX,EBX).
EBX= MAX(EAX,EBX).
Temp: ECX, EDX}
Sub EAX,EBX
Mov EDX,EAX
Mov ECX,0
SetGE CL
Dec ECX
And EAX,ECX
Add EAX,EBX
Not ECX
And EDX,ECX
Add EBX,EDX
{ Input: EBX, ESI
Output: EBX= MIN(EBX,ESI).
ESI= MAX(EBX,ESI).
Temp: ECX, EDX}
Sub EBX,ESI
Mov EDX,EBX
Mov ECX,0
SetGE CL
Dec ECX
And EBX,ECX
Add EBX,ESI
Not ECX
And EDX,ECX
Add ESI,EDX
{ Input: ESI, EDI
Output: ESI= MIN(ESI,EDI).
EDI= MAX(ESI,EDI).
Temp: ECX, EDX}
Sub ESI,EDI
Mov EDX,ESI
Mov ECX,0
SetGE CL
Dec ECX
And ESI,ECX
Add ESI,EDI
Not ECX
And EDX,ECX
Add EDI,EDX
{ Input: EAX, EBX
Output: EAX= MIN(EAX,EBX).
EBX= MAX(EAX,EBX).
Temp: ECX, EDX}
Sub EAX,EBX
Mov EDX,EAX
Mov ECX,0
SetGE CL
Dec ECX
And EAX,ECX
Add EAX,EBX
Not ECX
And EDX,ECX
Add EBX,EDX
{ Input: EBX, ESI
Output: EBX= MIN(EBX,ESI).
ESI= MAX(EBX,ESI).
Temp: ECX, EDX}
Sub EBX,ESI
Mov EDX,EBX
Mov ECX,0
SetGE CL
Dec ECX
And EBX,ECX
Add EBX,ESI
Not ECX
And EDX,ECX
Add ESI,EDX
{EDI contain the first maximum number;
ESI contain the second maximum number}
Mov EAX,EDI
{------------------------}
Pop ESI
Pop EDI
Pop EBX
End;
如何交换两个寄存器只有当第一个大于第二个 ?
代码这是 ( 80386 + ):
{ Input: EAX, EBX
Output: EAX= MIN(EAX,EBX).
EBX= MAX(EAX,EBX).
Temp: ECX, EDX}
Sub EAX,EBX (* Diff= EAX-EBX; set Overflow flag and Sign flag *)
Mov EDX,EAX (* EDX= Diff; flags not altered *)
Mov ECX,0 (* ECX= 0; flags not altered *)
SetGE CL (* If Sign flag == Overflow flag ECX= 1 else ECX=0 *)
Dec ECX (* If Diff>=0, ECX=0 else ECX=-1 *)
And EAX,ECX (* If Diff>=0, EAX=(EAX & 0)=0 else EAX=(EAX & -1)=EAX *)
Add EAX,EBX (* EAX= Minimum value between input n. *)
Not ECX (* If Diff<0, ECX=0 else ECX=-1 *)
And EDX,ECX (* If Diff<0, EDX=(EDX & 0)=0 else EDX=(EDX & -1)=EDX *)
Add EBX,EDX (* EBX= Maximum value between input n. *)
函数Max42可以写成,也可以作为80686+处理器的下一个代码。只需要20条快速ASM寄存器指令:
Function Max42B(A,B,C,D:Integer):Integer; Assembler;
{ Input: EAX, EBX, ESI, EDI
Output: EDI= 1° MAX(EAX,EBX,ESI,EDI).
ESI= 2° MAX(EAX,EBX,ESI,EDI).
Temp: ECX.
EAX EDX ECX are 1°, 2° AND 3° PARAMETERs.
Can freely modify the EAX, ECX, AND EDX REGISTERs. }
Asm
Push EBX
Push EDI
Push ESI
Mov EAX,A
Mov EBX,B
Mov ESI,C
Mov EDI,D
{ Input: EAX, EBX
Output: EAX= MIN(EAX,EBX).
EBX= MAX(EAX,EBX).
Temp: ECX}
Mov ECX,EAX
Cmp EAX,EBX
CMovGE EAX,EBX
CMovGE EBX,ECX
{ Input: EBX, ESI
Output: EBX= MIN(EBX,ESI).
ESI= MAX(EBX,ESI).
Temp: ECX}
Mov ECX,EBX
Cmp EBX,ESI
CMovGE EBX,ESI
CMovGE ESI,ECX
{ Input: ESI, EDI
Output: ESI= MIN(ESI,EDI).
EDI= MAX(ESI,EDI).
Temp: ECX}
Mov ECX,ESI
Cmp ESI,EDI
CMovGE ESI,EDI
CMovGE EDI,ECX
{ Input: EAX, EBX
Output: EAX= MIN(EAX,EBX).
EBX= MAX(EAX,EBX).
Temp: ECX}
Mov ECX,EAX
Cmp EAX,EBX
CMovGE EAX,EBX
CMovGE EBX,ECX
{ Input: EBX, ESI
Output: EBX= MIN(EBX,ESI).
ESI= MAX(EBX,ESI).
Temp: ECX}
Mov ECX,EBX
Cmp EBX,ESI
CMovGE EBX,ESI
CMovGE ESI,ECX
{EDI contain the first maximum number;
ESI contain the second maximum number}
Mov EAX,EDI
{------------------------}
Pop ESI
Pop EDI
Pop EBX
End;
你好!
一个天真的初学者找到两个最大值的方法(我希望这将让你摆脱推理,如何获得第二高…你只需要搜索第二高,同时搜索最高):
push bp
mov bp,sp
mov ax,[bp+4] ; temporary max1 = first argument
mov bx,8000h ; temporary max2 = INT16_MIN
; max2 <= max1
mov dx,[bp+6]
call updateMax1Max2
mov dx,[bp+8]
call updateMax1Max2
mov dx,[bp+10]
call updateMax1Max2
; ax and bx contains here max1 and max2
imul bx ; signed multiplication, all arguments are signed
; dx:ax = max1 * max2
; "mul" would produce wrong result for input data like -1, -2, -3, -4
pop bp
ret
updateMax1Max2:
; dx is new number, [ax, bx] are current [max1, max2] (max2 <= max1)
cmp bx,dx ; compare new value to lesser max2
jge updateMax1Max2_end
mov bx,dx ; new max2
cmp ax,dx ; compare new value to greater max1
jge updateMax1Max2_end ; new max2 is already <= max1
xchg ax,bx ; new value promoted to new max1, old max1 is now max2
updateMax1Max2_end:
ret
它同时保持两个临时最大值,以换取更复杂的更新(不仅针对单个最大值测试新值,而且针对第二个最大值测试新值)。
然后它通过保持两个临时值以指定的顺序进行某种优化,因此当new值低于max2时,它立即被丢弃,而不是针对max1进行测试。
复杂的"新值是否大于已保存的max1/max2"代码放在单独的子例程中,因此可以多次重用。
最后,[max1,max2]的初始状态被设置为[first_argument, INT16_MIN],这样子例程就可以以简单的方式应用于剩余的三个参数(通过大量重用代码来减少代码复杂性)。
Peter和Terje的建议为高级可能性提供了很好的见解,但他们也很好地展示了性能asm编码是如何棘手的(因为他们都必须在他们的原始想法中添加勘误表)。
当遇到困难或有疑问时,试着用最直接的方法解决问题(就像你会像人一样解决问题)。尽量减少指令的数量(以通用的方式编写,尽可能在子例程中重用任何较大的代码部分),这样易于调试和理解。
然后用几个可能的输入输入,锻炼也角情况([一些示例值],[INT16_MIN, INT16_MIN, INT16_MIN], [INT16_MAX, INT16_MAX, INT16_MAX], [-1, -2, -3, -4], [-2, -1, 0, INT16_MAX],等等…),并验证结果是正确的(理想情况下,在一些代码中也是如此,所以你可以在下次更改例程后重新运行所有测试)。
这是至关重要的一步,它将使您免于最初的错误假设,忽略一些极端情况的结果。在理想的情况下,甚至不要直接运行代码,直接进入调试器并对每个测试用例进行单步执行,不仅要验证结果,还要继续检查计算过程中的内部状态是否如预期的那样工作。
之后,您可以检查一些"代码高尔夫",如何利用情况的所有属性来降低工作量(简化算法)和/或指令数量,以及如何用替代更快的方法替换性能受损的代码。