2
\$\begingroup\$

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.

screenshot program-result

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. :)

\$\endgroup\$
  • \$\begingroup\$ I really hope that the ch register is initially zero. Does the Windows ABI guarantee this? \$\endgroup\$ – Roland Illig Jun 26 '17 at 20:17
  • \$\begingroup\$ @RolandIllig Not sure concerning ch indeed. Thanks for the hint. \$\endgroup\$ – michael.zech Jun 27 '17 at 2:02
3
\$\begingroup\$

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 & 0x55555555) << 1
bits1 = (x >> 1) & 0x55555555
x = bits0 | bits1

Then do the same thing with groups of 2 bits, and then once more with groups of 4 bits.

\$\endgroup\$
2
\$\begingroup\$

Generally looks correct. A certain improvement would be to use a rotate-with-carry instruction:

    process_bit:
        shr eax, 0x01
        rcl ebx, 0x01
        loop process_bit
\$\endgroup\$
1
\$\begingroup\$

Two things caught my eye.

1) Looking at this:

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.

When you want to zero a register, normally you would do that with xor ebx, ebx instead of mov ebx, 0x0 since this is slightly smaller/faster. Also, what about something like this:

process_bit:
    xor     ebx,    ebx     ; Start at zero
    shr     eax,    0x1     ; Kick the right-most bit out ...
    adc     ebx,    0x0     ; Add the shifted bit to ebx
    rol     ebx,    cl      ; The right-most bit has been fresh written. Now move it n-positions to the left.

2) Then there's this:

mov     eax,    edx
call    print_eax_binary

If you know that you are going to need a specific value in eax, why not structure your code such that it ends up there in the first place? If appears that if you swap the usage of eax and edx, you can avoid this move.

PS Regarding Roland's somewhat cryptic remark regarding ch:

If ch isn't zero (for example if it is 7), when you do mov cl, 0x1f, then the ecx register will contain 0x71f. This becomes a problem, since loop uses ecx, not cl.

\$\endgroup\$
1
\$\begingroup\$

As the exercise doesn't require result to be stored, each digit can be displayed immediately.

    mov     ecx, eax      ; Copy dword to be displayed in reverse
@@: mov      al, cl       ; Move low nibble to AL
    and      al, 1        ; Isolate least significant bit
    or       al, '0'      ; Going to be either 0 or 1

   .....  Whatever is required here to display contents of AL

    shr     ecx, 1
    jnz     @b

The only difference with this algorithm is trailing zero's won't be displayed. Just a personal preference of mine, otherwise you could substitute ECX to be a counter of 32 and EDX the copy of EAX if the full 32 bits needs to be shown.

\$\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.