assembly 没有分支或移位的绝对值,只有加/减和布尔值

qybjjes1  于 4个月前  发布在  其他
关注(0)|答案(2)|浏览(58)

我们学校有一个问题,是给那些想测试自己的学生的。我花了很长时间在这个问题上,但还是想不出来。
AX寄存器中有一个16位的数字,这个数字是有符号的。得到它的绝对值,AX中的数字必须保持不变(EDIT:没有限制的寄存器数量,AX寄存器可以改变,但在函数结束时,它需要是原始的数字),答案应该是BX。你只能使用这些指令:
MOV、ADD、XOR、NOT、AND、OR、NEG。
像编译器那样处理SAR是很容易的,但是如果没有它,就不清楚如何在符号位上获得任何行为条件。

qlzsbp2j

qlzsbp2j1#

愚蠢的想法#1:在16位真实的模式下,这是不可能的。即使一个表的整个64 kiB段是不够的;我们需要两倍的时间来查找任何可能的16位值的2字节结果。
我们可以很容易地用32位寻址,比如xor ebx, ebx/mov bx, ax/mov bx, [table + ebx*2],如果你能调整128 kiB的表数据。:P
完全在规则内,你可以用sub esp, 1<<17在32位或64位模式下在堆栈上构造表,并用mov word [esp+0], 0/mov word [esp + 2], 1/etc存储数据。完全展开,没有循环,所以大约有256 kiB的机器代码。但是,这在真实的模式下不起作用,完全是效率的笑话。

我们可以使用x86部分寄存器技巧将符号位隔离为0 / 1整数:

xor  dx, dx           ; DX = 0
    mov  dl, ah           ; DX = AX>>8   (zero extended)
    add  dx, dx           ; DX <<= 1  shifts the sign bit alone into DH

    mov  dl, dh
    mov  dh, 0            ; DX = (AX<0) = sign bit of AX zero extended to 16-bit

    neg  dx               ; DX = 0 or -1

字符串
或者最后3条指令可以优化为2条

neg  dh               ; 0 or -1 according to sign bit of AX
    mov  dl, dh           ; duplicate to the full DX = 0 or -1


头奖;我们有一个sar ax,15cwd值,它的所有位都是0或1,广播AX的符号位,准备与2的补码标识(How to prove that the C statement -x, ~x+1, and ~(x-1) yield the same results?)一起使用,就像编译器使用(https://godbolt.org/z/n3yoUp)一样。
通常,您可以使用xor ax, dx/sub ax, dx来修改原始值。
我之前认为这个挑战要求你避免修改任何 * 其他 * 寄存器,否则保持AX不变的限制是微不足道的,不值得成为挑战的一部分。但是我认为如果没有内存中的额外暂存空间或另一个寄存器,这是不可能的。编辑澄清了没有必要。

mov  bx, ax
    xor  bx, dx           ; ~x      or x
    sub  bx, dx           ; ~x + 1  or x


-1的异或像NOT一样翻转所有位。与0的异或是一个空操作。
-1的整数递增1,带0的整数是空操作(0是加法和异或的单位元素)。
所以这有条件地应用了2的补码-x = ~x + 1恒等式。
附言:我花了几分钟的时间来思考这个问题,排除了任何全寄存器方法,我非常熟悉x86和位操作,例如用x86机器码编写codegolf.SE答案,并用SIMD做一些重要的事情。IMO这是一个有趣的挑战。
此外,在真实的生活中,您永远不会想编写这样的代码; cwdcdq要高效得多,或者对于AX、copy和sar以外的源代码,部分寄存器的东西甚至会导致某些乱序执行CPU(如Intel PPro到Nehalem)的停顿。
例如,在此源的the Godbolt compiler explorer上:

unsigned absval(int x) {
    return x<0 ? 0U - x : x;
}


使用无符号返回值可以避免最负的2的补码整数的有符号整数溢出未定义行为。(-INT_MIN是未定义的行为)。我认为我写它的方式实际上依赖于C实现是2的补码,虽然,因为0U - xx转换为无符号,以匹配另一边 *,然后 * 将其用作二进制-的操作数。或者这就是我们想要的,对于无符号0U-x,从0x8000的输入生成0x8000(对于16位int)。
GCC这样做是为了设置EAX = abs(EDI)(x86-64 System V调用约定)。

mov     eax, edi
    cdq                      ; sign-extend EAX into EDX:EAX
    xor     eax, edx
    sub     eax, edx
    ret


clang针对x86-64执行此操作,使用从NEG读取标志的条件移动:

mov     eax, edi
    neg     eax                 ; 0 - x
    cmovl   eax, edi            ; copy the original if 0 was < x
    ret


在某些CPU上,这样做会更有效:

; shorter critical path on CPUs where mov is not zero latency
    xor     eax, eax
    sub     eax, edi            ; 0 - x
    cmovl   eax, edi            ; copy the original if 0 was < x
    ret


Sandybridge消除了xor-zeroing,但没有mov,对于不执行mov消除的CPU,这缩短了关键路径。mov eax,edi在关键路径上,但xor-zeroing不是。或者我们可以执行mov eax, edi/neg edi/cmovnl eax, edi以再次允许MOV和NEG并行运行。
CMOV是Broadwell之前的Intel CPU上的2-uop指令。(CMOVA和CMOVBE在当前Intel上仍然是2 uop,因为它们读取CF * 和 * ZF,它们在不同的组中分别重命名。其他是1 uop)

apeeds0o

apeeds0o2#

感谢Peter Cordes的回答,代码很简单,问题是SAR指令,但是Peter创建得很好。
号码已加载到AX中

; this is practicaly the SAR instruction, 
; the mask for the absolute value is 
; number >> (sizeof(short)) * CHAR_BIT -1)
; number >>        (2 * 8) - 1 = 15
; so normaly we would do SAR bx, 15 and done

mov bl, ah  ; BX = AX>>8
add bx, bx  ; BX <<= 1
neg bh      ; 0 or -1 
mov bl, bh  ; duplicate the full BX

mov cx, ax  ;
add cx, bx  ; the number + mask 
xor bx, cx  ; (number+mask) ^ mask

字符串
现在答案在BX中,AX没有被更改

相关问题