Reverse bit order of a byte

Go To Last Post
56 posts / 0 new

Pages

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

danni wrote:
The AA-55 method was better in size and time.

What du you mean by space and time? I guess most methods are smaller in flash than a 256 byte table lookup. But is there one that's faster? I browsed the thread clawson linked to and I couldn't find one faster than a 256 byte table lookup. Maybe it's just my benchmarking skills that sucks.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:

// Reverses the order of bits in a byte. 
// I.e. MSB is swapped with LSB, etc. 
unsigned char Bit_Reverse( unsigned char x ) 
{ 
  94:	98 2f       	mov	r25, r24
  96:	99 0f       	add	r25, r25
  98:	9a 7a       	andi	r25, 0xAA	; 170
  9a:	86 95       	lsr	r24
  9c:	85 75       	andi	r24, 0x55	; 85
  9e:	98 2b       	or	r25, r24
    x = ((x >> 1) & 0x55) | ((x << 1) & 0xaa); 
    x = ((x >> 2) & 0x33) | ((x << 2) & 0xcc); 
  a0:	89 2f       	mov	r24, r25
  a2:	88 0f       	add	r24, r24
  a4:	88 0f       	add	r24, r24
  a6:	8c 7c       	andi	r24, 0xCC	; 204
  a8:	96 95       	lsr	r25
  aa:	96 95       	lsr	r25
  ac:	93 73       	andi	r25, 0x33	; 51
  ae:	89 2b       	or	r24, r25
    x = ((x >> 4) & 0x0f) | ((x << 4) & 0xf0); 
  b0:	98 2f       	mov	r25, r24
  b2:	92 95       	swap	r25
  b4:	9f 70       	andi	r25, 0x0F	; 15
  b6:	82 95       	swap	r24
  b8:	80 7f       	andi	r24, 0xF0	; 240
    return x;    
}
  ba:	89 2b       	or	r24, r25
  bc:	08 95       	ret

(20 cyles from entry point until ret - but not including call/ret overhead)

If the C compiler could be taught that

Quote:
x = ((x >> 4) & 0x0f) | ((x << 4) & 0xf0)

can compile to a single swap instruction.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I needed a very small routine to achieve reversing bits in a byte. The smallest routine I could come up with takes 14 bytes in assembly and reverses a byte in 38 cycles.

.global reverseByte
.func   reverseByte
reverseByte:
clc
ldi        r25, 0x80
rotate_bit:
rol        r24
ror        r25
brcc       rotate_bit
mov        r24, r25
ret
.endfunc

I did a full analysis of a couple of functions to reverse a byte at http://omarfrancisco.com/reversing-bits-in-a-byte/

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thelandlord wrote:
The smallest routine I could come up with takes 14 bytes in assembly and reverses a byte in 38 cycles.
You don't need the clc. Since you overwrite the content of r24 just before returning it matters not what gets shifted in. Note, too, that the routine would work just as well using lsl r24 instead of rol 24. That change would not affect the size or speed.

Don Kinzer
ZBasic Microcontrollers
http://www.zbasic.net

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You are correct!. The clc is not needed. This cuts the size of the routine to 12 bytes and 37 cycles.

Pages