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
REVLOOP:
  rl l
  rra
  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:

76543210
⇐1⇐33⇒1⇒⇐1⇐33⇒1⇒
01234567

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
  rlca      ; a = 54321076
  xor l
  and 0xAA
  xor l     ; a = 56341270
  ld l,a
  rlca
  rlca
  rlca      ; a = 41270563
  rrc l     ; l = 05634127
  xor l
  and 0x66
  xor l     ; a = 01234567

4 comments:

  1. ld l,a : ld a,(hl) :)
    save space or save tacts

    ReplyDelete
    Replies
    1. Thanks for the hint. I asked some fiends of mine who work with web application development company to help me with the code and they showed me this site.

      Delete
  2. how to save B:
    ld l,#01 : rra : rl l : jr nc,$-3 : ld a,l

    s.

    ReplyDelete
  3. If speed is the real issue, the (usually) fastest way to deal with bits in a byte (reverse bits, count bits set/clear, determine the first bit set/clear) is to pre-load a table with all 256 possible values and then use the byte in question to index into the table for the result.

    ReplyDelete