在汇编编程中,想要从寄存器的低位计算某些东西是相当普遍的,这些位不能保证将其他位置零.在像C这样的高级语言中,你只需将输入转换为小尺寸,让编译器决定是否需要分别将每个输入的高位归零,或者是否可以在输出之后切断结果的高位.事实.
这是为x86-64的(又名AMD64),出于各种原因尤其常见1,其中的一些是存在于其它的ISA.
我将使用64位x86作为示例,但目的是询问/讨论2的补码和无符号二进制算法,因为所有现代CPU都使用它.(注意,C和C++不保证两个补码4,并且有符号溢出是未定义的行为.)
作为示例,考虑一个可以编译为LEA指令2的简单函数.(在X86-64 SysV的(Linux)的ABI 3,前两个函数参数是rdi和rsi,与在返回rax. int是一个32位的类型.)
; int intfunc(int a, int b) { return a + b*4 + 3; }
intfunc:
lea eax, [edi + esi*4 + 3] ; the obvious choice, but gcc can do better
ret
gcc知道即使是负有符号整数,加法也只是从右到左,所以输入的高位不会影响进入的内容eax.因此,它保存了一个指令字节并使用 lea eax, [rdi + rsi*4 + 3]
为什么它有效？
1为什么x86-64频繁出现这种情况:x86-64有可变长度指令,其中额外的前缀字节改变了操作数大小(从32到64或16),因此在指令中通常可以保存一个字节.以相同的速度执行.当写入低8b或16b的寄存器(或稍后读取完整寄存器(Intel pre-IvB)时的失速)时,它也具有错误依赖性(AMD/P4/Silvermont):由于历史原因,只写入32b sub -registers将64b寄存器的其余部分归零.几乎所有的算术和逻辑都可用于低8位,16位或32位,以及通用寄存器的全64位.整数向量指令也是非正交的,某些元素大小的某些操作不可用.
此外,与x86-32不同,ABI在寄存器中传递函数args,而对于窄类型,高位不需要为零.
2 LEA:与其他指令一样, LEA的默认操作数大小为32位,但默认地址大小为64位.操作数大小前缀字节(0x66或REX.W)可以使输出操作数大小为16或64位.地址大小前缀字节(0x67)可以将地址大小减小到32位(64位模式)或16位(32位模式).所以在64位模式下,lea eax, [edx+esi]需要多一个字节lea eax, [rdx+rsi].
这是可能的lea rax, [edx+esi],但地址仍然只用32位计算(进位不设置位32 rax).你得到相同的结果lea eax, [rdx+rsi],这比两个字节短.因此,地址大小前缀永远不会有用LEA,因为Agner Fog的优秀objconv反汇编程序的反汇编输出中的注释警告.
3 x86 ABI:调用者不必将用于传递或返回较小类型的64位寄存器的上部归零(或符号扩展).想要将返回值用作数组索引的调用者必须对其进行符号扩展(使用movzx rax, eax或者特殊情况下的eax指令cdqe.(不要混淆cdq,哪个符号扩展eax到edx:eax例如设置) foridiv.))
这意味着函数返回unsigned int可以计算在临时在64位其返回值rax,并且不需要mov eax, eax 为零高位的rax.在大多数情况下,这个设计决策很有效:通常调用者不需要任何额外的指令来忽略上半部分中的未定义位rax.
C和C++特别指出的是不要求二进制补码有符号整数(除C++ std::atomic类). 也允许一个补码和符号/幅度,因此对于完全可移植的C,这些技巧仅适用于unsigned类型.显然,对于签名操作,符号/幅度表示中的设置符号位意味着例如减去而不是添加其他位.我没有完成一个补码的逻辑
然而,位黑客是只有两个互补的工作是广泛的,因为在实践中没有人关心别的.许多使用二进制补码的东西也应该用一个补码,因为符号位仍然不会改变其他位的解释:它只有 - (2 N -1)(而不是2 N)的值.符号/幅度表示不具有此属性:每个位的位置值为正或负,具体取决于符号位.
另请注意,C编译器可以假定签名溢出永远不会发生,因为它是未定义的行为.因此,例如编译器可以并且确实假设(x+1) < x总是错误的.这使得检测签名溢出在C中相当不方便. 注意无符号环绕(进位)和有符号溢出之间的区别.
按位逻辑
左移(包括*scale中[reg1 + reg2*scale + disp])
加法/减法(以及LEA指令:永远不需要地址大小前缀.如果需要,只需使用所需的操作数大小进行截断.)
乘法的低半部分.例如16b x 16b - > 16b可以用32b x 32b - > 32b完成.您可以imul r16, r/m16, imm16通过使用32位imul r32, r/m32, imm32然后仅读取结果的低16 来避免LCP停顿(和部分寄存器问题).(m32但是,如果使用该版本,请注意更宽的内存引用.)
正如英特尔的insn ref手册所指出的,2和3操作数形式imul可以安全地用于无符号整数.输入的符号位不会以N x N -> N位乘法的形式影响结果的N位.)
2 X(即移通过 x):工作至少在x86,其中所述移位计数被屏蔽,而不是饱和的,向下到操作的宽度,所以高垃圾中ecx,或甚至高位cl,不影响轮班计数.也适用于BMI2无标记移位(shlx等),但不适用于向量移位(pslld xmm, xmm/m128等等,使计数饱和). 智能编译器优化了移位计数的屏蔽,允许在C中旋转的安全习惯用法(没有未定义的行为).
显然,诸如进位/溢出/符号/零之类的标志都会受到更广泛操作的高位垃圾的影响.x86的移位使最后一位移出进位标志,因此这甚至会影响移位.
右转
完全乘法:例如对于16b x 16b - > 32b,确保在执行32b x 32b - > 32b之前,输入的高16位为零或符号扩展imul.或使用16位单操作数mul或imul不方便地将结果放入dx:ax.(有符号与无符号指令的选择将以与32b之前的零或符号扩展相同的方式影响上部16b imul.)
memory addressing([rsi + rax]):根据需要进行符号或零扩展.没有[rsi + eax]寻址模式.
分裂和剩余
log2(即最高设置位的位置)
尾随零计数(除非你知道你想要的部分中有一个设置位,或者只是检查一个大于N的结果,因为你没有找到检查.)
与无符号基数2一样,二进制补码是一种位值系统.无符号base2的MSB 在N比特数(例如,2 31)中具有2 N-1的位值.在2的补码中,MSB的值为-2 N-1(因此用作符号位). 维基百科文章解释了许多其他理解2的补码和否定无符号base2数的方法.
关键点在于设置符号位不会改变其他位的解释.加法和减法的工作方式与unsigned base2完全相同,只是对有符号和无符号的结果进行解释.(例如,当有一个进位但没有超出符号位时发生有符号溢出.)
另外,进位仅从LSB传播到MSB(从右到左).减法是相同的:无论高位中是否有任何东西要借用,低位都借用它.如果这导致溢出或进位,则只会影响高位.例如:
0x801F -0x9123 ------- 0xeefc
低8位,0xFC不依赖于他们借来的东西.他们"环绕"并将借款传递给鞋帮8.
因此加法和减法具有以下特性:结果的低位不依赖于操作数的任何高位.
由于LEA只使用加法(和左移),使用默认的地址大小总是很好.延迟截断直到操作数大小对结果起作用总是很好.
(例外:16位代码可以使用地址大小前缀来进行32位数学运算.在32位或64位代码中,地址大小前缀减小宽度而不是增加.)
乘法可以被认为是重复加法,或者是移位和加法.低半部分不受任何高位的影响.在这个4位示例中,我已经写出了所有位为低2结果位的位乘积.仅涉及任一源的低2位.很明显,这一般起作用:部分乘积在加法之前被移位,因此源中的高位通常不会影响结果中的低位.
有关更详细的说明,请参阅Wikipedia以获取更大版本.有很多好的谷歌点击二进制签名乘法,包括一些教材.
*Warning*: This diagram is probably slightly bogus.
ABCD A has a place value of -2^3 = -8
* abcd a has a place value of -2^3 = -8
------
RRRRrrrr
AAAAABCD * d sign-extended partial products
+ AAAABCD * c
+ AAABCD * b
- AABCD * a (a * A = +2^6, since the negatives cancel)
----------
D*d
^
C*d+D*c
进行有符号乘法而不是无符号乘法仍然在低半部分(本例中为低4位)给出相同的结果.部分产品的符号扩展仅发生在结果的上半部分.
这种解释不是很彻底(甚至可能有错误),但有充分的证据表明在生产代码中使用它是真实和安全的:
gcc用于imul计算unsigned long两个unsigned long输入的乘积. 查看gcc的一个示例,利用LEA获取Godbolt编译器资源管理器上的其他功能.
英特尔的insn ref手册说:
两个和三个操作数形式也可以与无符号操作数一起使用,因为无论操作数是有符号还是无符号,产品的下半部分都是相同的.但是,CF和OF标志不能用于确定结果的上半部分是否为非零.
英特尔的设计决定只引入2和3的操作数形式imul,而不是mul.
显然,按位二进制逻辑运算(和/或/ xor/not)独立地处理每个位:位位置的结果仅取决于该位位置的输入值.比特移位也很明显.
京公网安备 11010802040832号 | 京ICP备19059560号-6 