1
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ as long as only 8 bit values are involved, you can also use look-up-table (LUT) with size 256B, then the conversion is basically single mov from memory, but I guess you are for some reason trying to avoid this (kinda "cheat", but often used in 8b/16b CPU emulators, etc.. to make the processing speed predictable across different types of calculations and also the LUTs are often 10..20 bits to account not only for the source 8b value, but also the "flag" register and calculating in single mov results of both together). \$\endgroup\$ – Ped7g Dec 13 '19 at 14:07
  • \$\begingroup\$ and about actually doing the calculation with instructions, which instructions you are willing to accept? The example seems to be x86_64, so you would accept also shrx and similar? (didn't really try, but I would guess it may be favourable for certain intermediate steps, not affecting flags and specifying both source + destination registers saving a copy instruction). \$\endgroup\$ – Ped7g Dec 13 '19 at 14:12
3
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.