Shifting bits in assembly (nasm)

Question

I wrote a function which takes a byte and shifts the bits around. That is, there shall be the same number of 1 bits and 0 bits in the output but the bits will be shifted in position:

global _main
default rel

section .text

_main:
    ; Given 1 byte, shift the positions of the bits in the form 74652103
    mov bl, 0x5A
    ; 0101 1010

    shift_bits:
    ; 1. bit 7 stays same
    ; 2. bit 4 (0x10) gets shifted left by 2 - and with 0001 0000, shift left by 2, or with result
    ; 3. bit 6 (0x40) gets shifted right by 1
    ; 4. bit 5 (0x20) gets shifted right by 1
    ; 5. bit 2 (0x4) gets shifted left by 1
    ; 6. bit 1 (0x2) gets shifted left by 1
    ; 7. bit 0 (0x1) gets shifted left by 1
    ; 8. bit 3 (0x8) gets shifted right by 3
    ; begin 0101 1010
    ; expect: 0110 0101
    ; end 0110 0101
        mov al, bl
        mov cl, 0
        and al, 0x80
        or cl, al
        mov al, bl
        and al, 0x10
        shl al, 2
        or cl, al
        mov al, bl
        and al, 0x4
        shl al, 1
        or cl, al
        mov al, bl
        and al, 0x2
        shl al, 1
        or cl, al
        mov al, bl
        and al, 0x1
        shl al, 1
        or cl, al
        mov al, bl
        and al, 0x8
        shr al, 3
        or cl, al
        mov al, bl
        and al, 0x2
        shl al, 1
        mov al, bl
        and al, 0x40
        shr al, 1
        or cl, al
        mov byte [A], cl ; Store result in A

    go_out:
    mov     rax, 0x2000001 ; exit - macOS specific!
    mov     rdi, 0
    syscall


section .data
A: db 0

Is there a more efficient way to do this with fewer instructions or more performant ones?

Answer 1

The operation count can be reduced, by using that some bits are moved by the same distance. Bits 0, 1 and 2 can be shifted left in one go. 5 and 6 can be shifted right in one go.

Some shift/bitwise-OR combinations can be written as lea, that would be bad for Pentium 4 but very good on Ryzen and Ice Lake and fine on Haswell/Skylake. Since this is 64bit code it is best to use lea with a 64bit address and then implicitly discard the top half of the result by writing it to a 32bit destination, explicitly using a 32bit address would generate a useless address size override prefix.

The 8 bit operations have a disadvantage on several CPUs that limits their efficiency, they're usually not inherently slow per-se but the problem is that writing to the "low" 8 bit register may have a dependency on the whole register (the "high" registers are an other story and have their own issues), something like mov al, bl doesn't "decouple" the new al from the old al on such CPUs because the write is merged into rax. So unless there is a good reason for writing to an 8 bit register, I would recommend avoiding it, to avoid such odd edge cases of the microarchitecture.

Here is a possible implementation:

    ; keep bit 7 at bit 7
    mov     eax, ebx
    and     eax, 128
    ; shift bits 0, 1, 2 left by 1 and combine
    mov     ecx, ebx
    and     ecx, 7
    lea     eax, [rax + 2*rcx]
    ; shift bit 4 left by 2 and combine
    mov     ecx, ebx
    and     ecx, 0x10
    lea     eax, [rax + 4*rcx]
    ; shift bit 3 right by 3 and combine
    mov     ecx, ebx
    and     ecx, 8
    shr     ecx, 3
    or      eax, ecx
    ; shift bits 5 and 6 right by 1 and combine
    shr     ebx
    and     ebx, 0x30
    or      eax, ebx
    ; store result
    mov [A], al