FB II COMPILER

What would be the fastest way to swap eight bits, so that e.g. 64 becomes 2 (01000000 <> 00000010) and 192 becomes 3 (11000000 <> 00000011)?

Instead of special-purpose 8-bit reversal code, consider a general purpose FN, able to reverse 16- or 32-bit variables as well. FN BitRev in the program below illustrates a powerful programming technique for such tasks: recursion. BitRev splits the original number into two halves, bit-reverses each half (by calling itself recursively), and re-assembles the halves in reverse order.

Then, for speed, consider another powerful technique: a look-up table. This is useful when some function is expensive to compute but has a manageable number of possible input values. For 8-bit reversals, there are only 256 possible inputs, whose "outputs" can conveniently be pre-computed and kept in gReversedByteArray(). The program shows a huge speed increase (at least 50X) from this technique, by timing a million calculations and a million look-ups. Times are reported in ticks (=1/60s).

'---------------A complete FB2 or FB^3 program----------------
DIM gReversedByteArray(255)
END GLOBALS

' register on' uncomment for FB^3

LOCAL FN BitRev(num&, nBits) ' nBits should be 2,4,8,16 or 32
  DIM left&, right&, mask&
  nBits = (nBits>>1)
  mask& = BIT(nBits)-1
  right& = num& AND mask&
  left& = (num& >> nBits) AND mask&
  LONG IF nBits>1' recursion limit
    right& = FN BitRev(right&, nBits)
    left& = FN BitRev(left&, nBits)
  END IF
END FN = (right& << nBits) OR left&

LOCAL FN InitReverseByteArray
  DIM j
  FOR j=0 TO 255
    gReversedByteArray(j) = FN BitRev(j,8)
  NEXT
END FN

DIM b&, rb&, j&, ticks&, nBits
WINDOW 1,"",(0,0)-(620,300)
DEFSTR LONG
' test 8-byte reversal
b&=123: rb& = FN BitRev(b&, 8)
PRINT "8-bit " RIGHT$(BIN$(b&),8) " --> " RIGHT$(BIN$(rb&),8)

' test 16-bit reversal
b&=12301: rb&=FN BitRev(b&, 16)
PRINT "16-bit "RIGHT$(BIN$(b&),16) " --> " RIGHT$(BIN$(rb&),16)

' test 32-bit reversal
b&=-1230000101: rb&=FN BitRev(b&, 32)
PRINT "32-bit " RIGHT$(BIN$(b&),32) " --> " RIGHT$(BIN$(rb&),32)

_numTotest=1000000
PRINT "Speed test " _numTotest " 8-bit reversals..."
ticks& = FN TICKCOUNT
FOR j&=1 TO _numTotest
  rb& = FN BitRev(123, 8) ' calculate
NEXT
ticks& = FN TICKCOUNT - ticks&
PRINT RIGHT$(BIN$(123),8) " --> " RIGHT$(BIN$(rb&),8)
PRINT "Calculation ticks =" ticks&

FN InitReverseByteArray ' pre-compute table

ticks& = FN TICKCOUNT
FOR j&=1 TO _numTotest
  rb& = gReversedByteArray(123) ' look-up
NEXT
ticks& = FN TICKCOUNT - ticks&
PRINT RIGHT$(BIN$(123),8) " --> " RIGHT$(BIN$(rb&),8)
PRINT "Look-up table ticks =" ticks&

DO: HANDLEEVENTS: UNTIL FN BUTTON
'----------------------------------------------------

I remember asking...

What would be the fastest way to swap eight bits, so that e.g. 64 becomes 2 (01000000 <> 00000010) and 192 becomes 3 (11000000 <> 00000011)?

... and then I thought:

'Split the byte in half, and make a lookup-table of inverted
'4-bit numbers, e.g. f(7) = 14, because 0111 <> 1110

DIM f(15)
DATA 0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15
FOR i = 0 TO 15
  READ f(i)
NEXT

'Then twiddle the bits of the two halves of the byte, e.g. if our byte is a = 26 = &1A

  a  = &1A
  b1 = a  /  16               'b1 = &1
  b2 = a MOD 16               'b2 = &A
  c  = 16 * f(b2) + f(b1)              ' c = 16 * 5 + 8 = &58

'Which gives the reversed byte in c.

How's that? It seems about midway between the two beautiful suggestions Robert Purves made, doesn't it?
Now, there should be a way to find the reverses without recourse to a lookup-table...

Now, there should be a way to find the reverses without recourse to a lookup-table...

But why? Your table only needs 16 entries--just 16 bytes if you use a BYTE array. If you don't want the minimal overhead of an array, just use a 16-byte var and do this:

DIM swapList;16
'set values

then

swappedNybble% = PEEK (@swapList + nybbleVal)

Doing anything else will use more mem than that for code, and be slower.

BTW, I think bitshifts would be faster for the calcs you showed:

  a  = &1A
  b1 = a >> 4              'b1 = &1
  b2 = a AND 15            'b2 = &A
  c  = f(b2) << 4 + f(b1)              ' c = 16 * 5 + 8 = &58

Now, there should be a way to find the reverses without recourse to a lookup-table...

try this:

LOCAL FN swapNybble%(nybble%)
 select nybble%
  case 0,6,9,15    '= no change
  case 1,8: nybble% = nybble% XOR 9
  case 2,4: nybble% = nybble% XOR 6
  case else:nybble% = nybble% XOR 15
 end select
END FN = nybble% AND 15

  a  = &1A
  swappedVal% = FN swapNybble%(a>>4) OR FN swapNybble%(a AND 15) << 4

At least it's a different approach.

And then I, too, thought: "What about BetterBitRev?"

'---------------A complete FB2 or FB^3 program----------------
END GLOBALS

' register on' uncomment for FB^3

LOCAL FN BetterBitRev(num&, nBits)
DIM out&,j
out& = 0
FOR j = 1 TO nBits
out& = (out&<<1) OR (num& AND 1)
num& = num&>>1
NEXT
END FN = out&

DIM b&, rb&
WINDOW 1,"",(0,0)-(620,300)

DEFSTR LONG
' test 8-byte reversal
b&=123: rb& = FN BetterBitRev(b&, 8)
PRINT "8-bit " RIGHT$(BIN$(b&),8) " --> " RIGHT$(BIN$(rb&),8)

' test 16-bit reversal
b&=12301: rb&=FN BetterBitRev(b&, 16)
PRINT "16-bit "RIGHT$(BIN$(b&),16) " --> " RIGHT$(BIN$(rb&),16)

' test 32-bit reversal
b&=-1230000101: rb&=FN BetterBitRev(b&, 32)
PRINT "32-bit " RIGHT$(BIN$(b&),32) " --> " RIGHT$(BIN$(rb&),32)

DO: HANDLEEVENTS: UNTIL FN BUTTON