Which 2's complement integer operations can be used without zeroing high bits in the inputs, if only the low part of the result is wanted?
Solution 1:
Wide operations that can be used with garbage in upper bits:
- bitwise logicals
- left shift (including the
*scale
in[reg1 + reg2*scale + disp]
) - addition/subtraction (and thus
LEA
instructions: the address-size prefix is never needed. Just use the desired operand-size to truncate if needed.) -
The low half of a multiply. e.g. 16b x 16b -> 16b can be done with a 32b x 32b -> 32b. You can avoid LCP stalls (and partial-register problems) from
imul r16, r/m16, imm16
by using a 32bitimul r32, r/m32, imm32
and then reading only the low 16 of the result. (Be careful with wider memory refs if using them32
version, though.)As pointed out by Intel's insn ref manual, the 2 and 3 operand forms of
imul
are safe for use on unsigned integers. The sign bits of the inputs don't affect the N bits of the result in aN x N -> N
bit multiply.) - 2x (i.e. shift by
x
): Works at least on x86, where the shift count is masked, rather than saturated, down to the width of the operation, so high garbage inecx
, or even the high bits ofcl
, don't affect the shift count. Also applies to BMI2 flagless shifts (shlx
etc), but not to vector shifts (pslld xmm, xmm/m128
etc, which saturate the count). Smart compilers optimize away masking of the shift count, allowing for a safe idiom for rotates in C (no undefined behaviour).
Obviously flags like carry/overflow / sign / zero will all be affected by garbage in high bits of a wider operation. x86's shifts put the last bit shifted out into the carry flag, so this even affects shifts.
Operations that can't be used with garbage in upper bits:
- right shift
full multiplication: e.g. for 16b x 16b -> 32b, ensure the upper 16 of the inputs are zero- or sign-extended before doing a 32b x 32b -> 32b
imul
. Or use a 16bit one-operandmul
orimul
to inconveniently put the result indx:ax
. (The choice of signed vs. unsigned instruction will affect the upper 16b in the same way as zero- or sign-extending before a 32bimul
.)memory addressing (
[rsi + rax]
): sign or zero-extend as needed. There is no[rsi + eax]
addressing mode.division and remainder
- log2 (i.e. position of highest set bit)
- trailing zero count (unless you know there is a set bit somewhere in the part you want, or just check for a result larger than N as you not-found check.)
Two's complement, like unsigned base 2, is a place-value system. The MSB for unsigned base2 has a place value of 2N-1 in an N bit number (e.g. 231). In 2's complement, the MSB has a value of -2N-1 (and thus works as a sign bit). The wikipedia article explains many other ways of understanding 2's complement and negating an unsigned base2 number.
The key point is that having the sign bit set doesn't change the interpretation of the other bits. Addition and subtraction work exactly the same as for unsigned base2, and it's only the interpretation of the result that differs between signed and unsigned. (E.g. signed overflow happens when there's a carry into but not out of the sign bit.)
In addition, carry propagates from LSB to MSB (right to left) only. Subtraction is the same: regardless of whether there is anything in the high bits to borrow, the low bits borrow it. If that causes an overflow or carry, only the high bits will be affected. E.g.:
0x801F
-0x9123
-------
0xeefc
The low 8 bits, 0xFC
, don't depend on what they borrowed from. They "wrap around" and pass on the borrow to the upper 8 bits.
So addition and subtraction have the property that the low bits of the result don't depend on any upper bits of the operands.
Since LEA
only uses addition (and left-shift), using the default address-size is always fine. Delaying truncation until the operand-size comes into play for the result is always fine.
(Exception: 16bit code can use an address-size prefix to do 32bit math. In 32bit or 64bit code, the address-size prefix reduces the width instead of increasing.)
Multiplication can be thought of as repeated addition, or as shifting and addition. The low half isn't affected by any upper bits. In this 4-bit example, I've written out all the bit-products that are summed into the low 2 result bits. Only the low 2 bits of either source are involved. It's clear that this works in general: Partial products are shifted before addition, so high bits in the source never affect lower bits in the result in general.
See Wikipedia for a larger version of this with much more detailed explanation. There are many good google hits for binary signed multiplication, including some teaching material.
*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
Doing a signed multiply instead of an unsigned multiply still gives the same result in the low half (the low 4 bits in this example). Sign-extension of the partial products only happens into the upper half of the result.
This explanation is not very thorough (and maybe even has mistakes), but there is good evidence that it is true and safe to use in production code:
gcc uses
imul
to compute theunsigned long
product of twounsigned long
inputs. See an example of this of gcc taking advantage of LEA for other functions on the Godbolt compiler explorer.Intel's insn ref manual says:
The two- and three-operand forms may also be used with unsigned operands because the lower half of the product is the same regardless if the operands are signed or unsigned. The CF and OF flags, however, cannot be used to determine if the upper half of the result is non-zero.
- Intel's design decision to only introduce 2 and 3 operand forms of
imul
, notmul
.
Obviously the bitwise binary logical operations (and/or/xor/not) treat each bit independently: the result for a bit position depends only on the inputs value at that bit position. Bit-shifts are also rather obvious.