Bit-reverse a byte on 68HC12

Question

I'm in a microprocessors class and we are using assembly language in Freescale CodeWarrior to program a 68HCS12 micro controller. Our assignment this week is to revers a byte, so if the byte was 00000001, the output would be 10000000, or 00101011 to 11010100. We have to use assembly language, and were told we could use rotates and shifts (but not limited to!) to accomplish this task. I'm really at a loss as to where I should start.

Answer 1

Hints: If you do a shift, one bit gets shifted out and a zero (probably) gets shifted in. Where does that shifted out bit go to? You need to shift that in to the other end of the destination register or memory address.

I'm sure that 25 years ago I could do this in Z80 machine code without an assembler :)

Answer 2

Consider two registers as stacks of bits. What happens if you move one bit at a time from one to another?

Answer 3

If you can spare the 256 bytes extra code size, a lookup table is probably the most efficient way to reverse a byte on a 68HCS12. But I am pretty sure this is not what your instructor is expecting.

For the "normal" solution, consider the data bits individually. Rotates and shifts allow you to move bits around. For a first solution, isolate the eight bits (with bitwise "and" operations), move them to their destination positions (shifts, rotates...), then combine them together again (with bitwise "or" operations). This will not be the most efficient or simplest implementation, but you should first concentrate on getting a correct result -- optimization can wait.

Answer 4

When you do a right shift, what was the least significant bit goes into the carry flag.

When you do a rotate, the carry flag is used to fill in the vacated bit of the result (LSB for a ROL, MSB for a ROR).

Answer 5

For example, if you have in al the byte number the easiest way is

mov al, 10101110
mov ecx, 8

we put 8 in ecx for loop

mov ebx, 0 

In bl we will havee the result, we will make ebx, only to see what happens better

loop1:
sal al, 1;           

In carry flag now you have the last bit from left

rcr bl, 1;           

now you add in bl what you have in carry

loop loop1

and that's all

Answer 6

FIrst of all work out the algorithm for doing what you need to do. Express it as pseudo code or C or plain English or diagrams or whatever you are comfortable with. Once you have cleared this conceptual hurdle the actual implementation should be quite simple.

Your CPU probably has instructions which let you shift and/or rotate a register, perhaps including the carry flag as an additional bit. These instructions will be very useful.

Answer 7

This was a comment but I thought WTH!

To save space over the 256 byte table you can have a 16 byte table containing the values for four bits (nibbles) at a time. The algorithm then would be

revval=(revdigit[inval&0x0f]<<4)|
        revdigit[inval>>4];

If I were a prof I'd certainly like the two parts where one shift is in the indexing and the other outside.

Answer 8

I had also to program this bit reverse for the university (for 8 bits). Here is how I did:

MOV AL, 10001011B ;set the value to test
MOV CL, 7
MOV DH, 1
MOV DL, 0

loop1: PUSH AX
AND AL, DH 
PUSH CX
MOV CL, DL
SHR AL, CL
POP CX
MOV BH, AL
SHL BH,CL
OR CH,BH
DEC CL
INC DL
SHL DH, 1
POP AX
CMP DL, 8
JE END
JMP LOOP1

END:

I didn't commented it so here is how it works: DH is a 1 which travels in the byte like first time: 00000001; second time 00000010and so on. When you make an AND with the AL you get 0 or something like 100or 10000 you have to shift that to the right to get it as 0 or 1. Then, put it in BH and shift to the desired position which is 7for byte 0, 6for byte 1and so on. Then OR to our final result and INC and DEC what is necessary. Do not forget the conditional jumps and to pop AX for the next loop :)

Result will be in CH.

Answer 9

The following code make use of rotations and shift. I use Intel x86 syntax, see explanations on the right side:

    mov cx, 8           ; we will reverse the 8 bits contained in one byte
loop:                   ; while loop
    ror di              ; rotate `di` (containing value of the first argument of callee function) to the Right in a non-destructive manner
    adc ax, ax          ; shift `ax` left and add the carry, the carry is equal to 1 if one bit was rotated from 0b1 to MSB from previous operation
    dec cx              ; Decrement cx
    jnz short loop      ; Jump if cx register Not equal to Zero else end loop and return ax

I use dec instruction instead of sub, because it takes one byte only while sub takes 3 bytes. On top of that compilers seem to always optimize by choosing dec over sub.

edit: Also note that rcl ax (3 bytes), while equivalent of adc ax, 0 (2 bytes) followed by shl ax (2 bytes) is less efficient. See comments below, many thanks to Peter Cordes for his insights.