assembly - 如何在Y86-64(或其他具有ADD + AND但没有 native 右移的玩具ISA)中执行右移

Question

我正在尝试在Y86-64上执行右移

要进行左移，我知道我需要乘以2 ^ n，其中n是我们想要的位数，例如，如果我们想移4，则为2 ^ 4 = 16并执行加法循环以执行乘法对此，但我不确定该如何做正确的调整，我想我需要进行除法，但不确定如何处理

pcount_do:
     movq $0, %rax
.L2: movq %rdi, %rdx
     shrq %rdi
     ret

Answer 1

就像Matteo展示的那样，您可以一次循环一位，在一个位置读取，而在另一位置写入。

Matteo的答案通过移动掩码来在可变位置读取，并从寄存器的底部开始（在另一个掩码上移动）以锁定步长移动的位置进行写入。

读取输入的MSB比较容易，然后使用add same,same将输入左移并重复输入。因此，我们从最高位开始读取位，并从其MSB开始构造结果。 （我们一次向目标位置左移了1位，而ADD向左移，并且有条件加法设置是否设置新的位。）

我们可以使用2的补码符号比较来读取寄存器的高位。如果已设置，则为x < 0，否则未设置。

x86和y86具有一个称为SF的标志，该标志根据结果（ALU操作）的MSB设置。 x86具有js / cmovs / sets指令，这些指令直接检查SF条件。 y86仅具有jl / jge和其他检查SF!=OF的带符号比较条件，因此我们需要对零进行额外的比较以清除OF（x - 0不能溢出）。

或者从语义上讲，实际上是与零进行比较，而不仅仅是读取SF。 （除了我们can optimize compare-against-zero into andl %eax,%eax or andq %rax,%rax，如果您使用的是不具有次立即性的y86版本，这会很有帮助。y86还会丢失x86的无损test和cmp指令，例如and和< cc>，但只写标志。）

在https://www.simn.me/js-y86/上测试的32位y86版本

移植到y86-64应该很简单。 （更改注册表名称，并且32变为64）。
测试案例：sub。 （我没有找到一种方法来永久链接该站点上的代码，就像Godbolt编译器浏览器所允许的那样。）

   # constant input test case
    irmovl  0x12345, %eax
    #  irmovl  3, %ecx           # this could trivial handle variable counts, but doesn't.

# start of right-shift block:
# input: EAX = number to be shifted
# output: EDX =  number >> 1
# clobbers: EAX, ECX, EDI.   (EDI=1 to work around lack of add-immediate)

    xorl    %edx, %edx      # dst = 0.   like # irmovl  $0, %edx
    irmovl  1, %edi         # y86 is missing immediate add?

# shift 32-n bits from EAX into the bottom of EDX
# one at a time using SF to read them from the MSB
    irmovl  31, %ecx        # hard code count = 32 - 31
                            # or calculate this as 32 - count with neg / add or equivalent
rshift:                    # do {
    addl   %edx, %edx       # dst <<= 1

    andl   %eax, %eax       # compare against zero because y86 is missing js / cmovs that tests just SF
    jge   MSB_zero          # jge = jnl = not lower
    xorl    %edi,  %edx      # edx ^= 1.   y86 is missing OR?  low bit = 0 so we can ADD or XOR to set it
  MSB_zero:

    addl   %eax, %eax       # src <<= 1

    subl   %edi, %ecx
    jne   rshift            # }while(--ecx);  # semantically jnz


    halt # result in EDX
    #shr    $1, %eax

我使用了Xor调零功能，因为y86仿真器可组装成可变长度的机器代码，例如x86。 （因此 0x12345 >> 1 = 0x000091a2效率较低）。



或使用CMOVL从EAX的MSB到EDX的LSB进行无分支转移

# loop body:
    addl       %edx, %edx      # dst <<= 1

    xorl       %esi, %esi      # esi = 0
    sub        %esi, %eax      # src -= 0  to set flags
    cmovl      %edi, %esi      # esi = (src<0) ? 1 : 0  = MSB of EAX
    addl       %esi, %edx      # copy the bit into EDX  (can't carry to higher bits)

    addl       %eax, %eax      # src <<= 1

如果您的y86模拟器模拟了分支错误预测的性能损失，请使用此功能。否则分支是更少的指令。



或者，如果您关心性能，则应该可以一次对整个字节使用查找表，并且跨字节边界进行修复。

但是，由于没有左移可以有效地组合各个字节，因此对于每个字节位置，您都需要一个单独的256项qword LUT！或从偏移量加载，然后屏蔽掉“垃圾”字节。

哦，您需要右移以从qword中提取字节以提供数组索引。如果y86可以进行字节加载，则可以将输入整数存储到内存中，然后一次将其重新加载1个字节。或者再次使用未对齐的qword负载模拟字节负载，并使用 irmovl 0, %edx与AND进行模拟，以在寄存器底部隔离该字节。



实际上，我们可以使用带字节偏移量和掩码的存储/重新加载功能，仅用几条指令就可以“有效地”进行8位的倍数右移。

糟糕，但是对于运行时变量计数，我们遇到了鸡/蛋问题。我们需要 0x00...0FF作为字节偏移量，因为一个字节中有8位。但是数量很少，因此我们可以使用重复减法循环。 （您可能希望使用0x3f或0x1f（取决于操作数大小） count / 8将计数换行为64或32，就像x86硬件移位一样。这将避免索引过大而超出正确范围的索引存储方式。）

无论如何，您可以通过四舍五入（移出太多位）来扩展它以处理不是8的倍数的右移计数，然后一次将所需的位放回一个，就像循环的第一部分中那样。问题。 （在未对齐的加载之后，将那些位放在寄存器的顶部。）

或者也许使用Matteo的走面具的方法，使用LUT作为起点。但是，如果我们已经在进行存储/未对齐的重装以进行字节移位，则另一个重装可能很好。我们可以计算出相对于第一次未对齐重载的正确偏移量，即之前的4或8个字节，因此起始MSB恰好在第一次加载的最低位之下。