Search code examples
assemblyy86

Is there a way to perform arithmetic right shift using only xorq, andq, addq, iaddq, & subq?


I'm in a hypothetical architecture that only has those operations (Y86). No arithmetic right shift exists. I'm essentially trying to capture the upmost bit to determine if the number is negative and if so add it to the result register, rax.

Edit:

Sorry all, I forgot to specify, I'm trying to avoid conditional branches to see if it improves the efficiency. No cmov exists in the version I'm in.

The furthest I've gotten is:

andq $0x10000000, elem
subq $0x01111111, elem
addq elem, %rax

However, for a result of 0 this doesn't work.


Solution

  • If Y86 allows MOVQ to access memory that is not QWORD-aligned, then it can be done. But I doubt if it will perform better than a conditional branch.

    The trick is to write the number to memory, then read it again from an address that is slightly 'off'. This effectively shifts bits across a multiple of 8. Combine this with addq to shift the bits 1 position to the left.

    Please note that this highly relies on the endianness of the processor architecture. The following example is based on little endian (Intel-style). On big endian, the offsets will have to be adjusted.

    (If you prefer AT&T syntax, then please reverse the operands and remove the brackets.)

    movq rbx,number         ; sign bit is bit 63 of rbx
    movq [address],rbx      ; sign bit is most significant bit of the byte at [address+7]
    movq rbx,[address+4]    ; sign bit is bit 31 of rbx
    addq rbx,rbx            ; sign bit is bit 32 of rbx
    movq [address],bx       ; sign bit is least significant bit of the byte at [address+4]
    movq rbx,[address+4]    ; sign bit is bit 0 of rbx
    andq rbx,1              ; rbx = 0 for positive number, rbx = 1 for negative number
    addq ax,bx