我正在尝试对 Y86-64 进行右移
要进行左移，我知道我需要乘以 2^n，其中 n 是我们想要的移位数，例如，如果我们想要移动 4，它是 2^4 = 16 并执行加法循环以执行乘法就可以了，但我不确定该怎么做正确的转变我认为我需要执行除法，但不确定如何处理
pcount_do:
movq $0, %rax
.L2: movq %rdi, %rdx
shrq %rdi
ret
问问题
958 次
2 回答
1
鉴于 Y86 的指令集缺少移位和除法，我会选择与此 C 代码等效的东西：
uint64_t lut[] = {
1,
2,
4,
8,
16,
32,
64,
128,
256,
512,
1024,
2048,
4096,
8192,
16384,
32768,
65536,
131072,
262144,
524288,
1048576,
2097152,
4194304,
8388608,
16777216,
33554432,
67108864,
134217728,
268435456,
536870912,
1073741824,
2147483648,
4294967296,
8589934592,
17179869184,
34359738368,
68719476736,
137438953472,
274877906944,
549755813888,
1099511627776,
2199023255552,
4398046511104,
8796093022208,
17592186044416,
35184372088832,
70368744177664,
140737488355328,
281474976710656,
562949953421312,
1125899906842624,
2251799813685248,
4503599627370496,
9007199254740992,
18014398509481984,
36028797018963968,
72057594037927936,
144115188075855872,
288230376151711744,
576460752303423488,
1152921504606846976,
2305843009213693952,
4611686018427387904,
9223372036854775808};
uint64_t rshift(uint64_t source, int amount) {
uint64_t result = 0;
for(int i = amount; i < 64; ++i) {
if(source & lut[i]) result |= lut[i-amount];
}
return result;
}
只需添加/子/和/或加上一个查找表，这一切都应该是可行的。
如果我们想变得更聪明，正如@PeterCordes 建议的那样，我们可以使用 8 个条目的查找表并处理整个字节，但这需要比循环每个位更多的簿记。
- - 更新 - -
@PeterCordes 正确地指出，查找表实际上是无用的，因为我正在循环比特，因此使用总和计算二的下一个幂是微不足道的：
uint64_t rshift(uint64_t source, int amount) {
uint64_t result = 0;
uint64_t read_bit = 1;
uint64_t write_bit = 1;
for(int i = 0; i < amount; ++i) read_bit = read_bit + read_bit;
for(int i = amount; i < 64; ++i) {
if(source & read_bit) result |= write_bit;
read_bit = read_bit + read_bit;
write_bit = write_bit + write_bit;
}
return result;
}
于 2019-04-08T07:27:55.723 回答
1
就像 Matteo 展示的那样，您可以一次循环一位，在一个位置读取并在另一个位置写入位。
Matteo 的答案通过移动掩码在可变位置读取，并在锁定步长移动的位置写入，从寄存器的底部开始（移动另一个掩码）。
读取输入的 MSB 更容易，然后左移输入左移输入add same,same并重复。所以我们从最高位开始读取位，并从它的 MSB 开始构造结果。（我们一次将 1 位左移到目标位置，使用 ADD 左移，并通过条件加法设置新的位位置。）
我们可以使用 2 的补码符号比较来读取寄存器的最高位。 如果设置了，x < 0，否则不是。
x86 和 y86 有一个名为 SF 的标志，它是根据（ALU 操作的）结果的 MSB 设置的。x86 有js//直接检查条件的指令cmovs。y86 只有/和其他检查的有符号比较条件，所以我们需要对零进行额外的比较以清除 OF（不能溢出）。setsSFjljgeSF!=OFx - 0
或者在语义上，实际上是与零进行比较，而不是仅仅阅读 SF。（除了我们可以将比较零优化为andl %eax,%eaxorandq %rax,%rax，如果您使用的是没有子立即数的 y86 版本，这很有帮助。y86 也缺少 x86 的非破坏性指令test和cmp类似and但sub仅写入标志的指令.)
在https://www.simn.me/js-y86/上测试的 32 位 y86 版本
移植到 y86-64 应该几乎是微不足道的。（更改注册名称，32 变为 64）。
测试用例： 0x12345 >> 1 = 0x000091a2. （我没有看到在该站点上永久链接代码的方法，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-zeroing 是因为 y86 模拟器会组装成像 x86 这样的可变长度机器代码。（所以irmovl 0, %edx效率会降低）。
或者用 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 项 qwords 的 LUT 用于每个字节位置！或者从偏移量加载，然后屏蔽掉“垃圾”字节。
哦，您需要右移以从 qword 中提取字节以提供数组索引。如果 y86 可以进行字节加载，那么您可以将输入整数存储到内存并一次重新加载 1 个字节。或者再次使用未对齐的 qword 加载和 AND 来模拟字节加载，0x00...0FF以隔离寄存器底部的该字节。
事实上，我们可以使用带有字节偏移和掩码的存储/重载来“有效地”在几条指令中“有效地”右移 8 位的倍数。
哦，废话，但是我们在运行时变量计数方面遇到了鸡/蛋问题。我们需要count / 8一个字节偏移量，因为一个字节有 8 位。但是计数很小，所以我们可以使用重复减法循环。（您可能希望AND使用 0x3f 或 0x1f（取决于操作数大小）将计数包装为 64 或 32，就像 x86 硬件移位一样。这将避免在计数太大时索引内存超出正确范围。）
无论如何，然后您可以通过向上舍入（移出太多位）来扩展它以处理不是 8 倍数的右移计数，然后将所需的位一次放回一个，就像第一部分中的循环一样这个问题。（在未对齐的加载后将这些位放在寄存器的顶部。）
或者也许使用 Matteo 的蒙版行走方法，使用 LUT 作为起点。但是，如果我们已经为字节移位进行了存储/未对齐的重新加载，那么另一个重新加载可能会很好。我们可以计算相对于第一次未对齐重新加载的正确偏移量，之前 4 或 8 个字节，因此起始 MSB 是第一次加载的最低位正下方的位。
于 2019-04-08T08:44:26.690 回答