Friday, 3 January 2014

Fast Z80 Bit Reversal

For years I've been using the following simple code to reverse the bits in the A register by rotating the bits left out of one register and right into another:

; reverse bits in A
; 8 bytes / 206 cycles

  ld b,8
  ld l,a
  rl l
  djnz REVLOOP

Recently I wondered if it's possible to save a few cycles. It turns out the bits are at most 3 rotations away from their position in the reverse:


With this in mind I devised a bit-twiddling hack to reverse the bits in about a third of the time using only 6 rotates and a bit of logic to recombine the rotated bits. Here's the code, which no doubt has been done many times before:

; reverse bits in A
; 17 bytes / 66 cycles

  ld l,a    ; a = 76543210
  rlca      ; a = 54321076
  xor l
  and 0xAA
  xor l     ; a = 56341270
  ld l,a
  rlca      ; a = 41270563
  rrc l     ; l = 05634127
  xor l
  and 0x66
  xor l     ; a = 01234567