Assembler-program which reverses the content of EAX Following exercise:


  Write a program that takes a number (of size 4 bytes) x as input, and then
      reverses all the bits of x, and outputs the result. By reversing all bits we
      mean that the bit with original location i will move to location 31-i.
      Small example (for the 8 bit case):
        if x == {01001111}_2, then the output is {11110010}_2.
        In this example we reversed only 8 bits. Your program will be able to
        reverse 32 bits.


Full exercise-description can be seen here: XORPD GitHub

I tinkered out the following idea. Please take into account my comments too.

format PE console
entry start

include 'win32a.inc' 

; ===============================================
section '.text' code readable executable

start:
    mov     eax,    0x4f    ; 0x4f is equal to 01001111 (from the exercise-description example).
    mov     cl,     0x1f    ; cl becomes the control variable. 0x1f == 31 decimal
    xor     edx,    edx     ; edx will accumulate the different states of ebx during the runtime.
process_bit:
    shr     eax,    0x1     ; Kick the right-most bit out ...
    jc      add_one         ; If it was a 1 jump to 'add_one' ... 
    mov     ebx,    0x0     ;  ... otherwise write a 0 ...
    jmp     now_rotate      
add_one:
    mov     ebx,    0x1
now_rotate:
    rol     ebx,    cl      ; The right-most bit has been fresh written. Now move it n-positions to the left.
    or      edx,    ebx     ; "Save" or "Add" the current positive bits (1-bits) of ebx to edx.
    loop    process_bit

    mov     eax,    edx
    call    print_eax_binary

    ; Exit the process:
    push    0
    call    [ExitProcess]


include 'training.inc'


I guess it works right.



Please compare the result on the screenshot with the example-value from the exercise-description.

What to think about my solution?

Is it valid? Or does it have to be improved?

Is there a better way to solve the described task?

Looking forward to read your hints and comments.
In assembler it is often possible to avoid jmp instructions. This is done to improve branch prediction and thereby performance.

Your code can be written without the jump to add_one:

xor ebx, ebx
shr eax, 1
adc ebx, 0


These three instructions replace the whole jumping. The adc (add with carry) instruction's original purpose is to support chained addition, but it can be used creatively for many other purposes. Note that I had to move the xor ebx, ebx to the top since it updates the carry flag.

There are also the rcr and rcl instructions that efficiently use the carry flag as a one-bit register. You can just repeat 32 times:

rcr eax, 1
rcl ebx, 1


And you're done. When you inline this loop, you have a constant-time operation that finishes in 64 instructions. Each of them probably takes a single cycle, therefore 64 cycles. That's already acceptable, but there are probably better ways.

On the electrical, hardware level, the bitswap operation can be implemented by just swapping the wires, therefore chances are high that there is some machine instruction that makes this task more efficient. Just read through the whole processor manual to see if there is anything related. Have a look for the keywords "swap", "shift", "mask".

If you want to get a really fast program, you should use the bswap eax instruction, followed by code that reverses the bit order. This can probably be found in the excellent book Hacker's Delight.

The basic idea is to take every second bit and shift it to the left. At the same time, take the remaining bits and shift them to the right. Like this:

bits0 = (x &amp; 0x55555555) &lt;&lt; 1
bits1 = (x &gt;&gt; 1) &amp; 0x55555555
x = bits0 | bits1


Then do the same thing with groups of 2 bits, and then once more with groups of 4 bits. The groups of 8 and 16 bits are done by the bswap instruction, you don't need to implement them on your own.