FlipBits() but just need a nibble and need to invert bits

[spamiam]

I need to reverse the order of the bits in a nibble. Is there a way to make this faster than flipping bits in an entire byte? What algorithm does FlipBits() use. I found this one:

Code: Select all

unsigned char Bit_Reverse( unsigned char x )
{
    x = &#40;&#40;x >> 1&#41; & 0x55&#41; | &#40;&#40;x << 1&#41; & 0xaa&#41;;
    x = &#40;&#40;x >> 2&#41; & 0x33&#41; | &#40;&#40;x << 2&#41; & 0xcc&#41;;
    x = &#40;&#40;x >> 4&#41; & 0x0f&#41; | &#40;&#40;x << 4&#41; & 0xf0&#41;;
    return x;   
&#125; 

I don't see a way to make this work for just a nibble as it would appear that the ROR and ROL are completely integral to the technique and there is no similar ASM operation for just a nibble.
EDIT: I wrote of ROR/ROL because I saw them in an ASM version. But the shifts work fine too. But shifts are byte wide and there is no way (and no advantage) to limit it to a nibble

In my case I also need to invert the logic of the bits with

Code: Select all

x = NOT x

So, I presume that the most efficient technique would be to use the built-in FlipBits() followed by a bitwise inversion, and shift the bits right or left by 4 to restore the bits to their original nibble.

Code: Select all

Dim x as Byte
'x has some arbitrary value
x = FlipBits(x)
x = NOT x
x = Shr(x,4) 'or x=Shl(x,4)

I wonder how the speed of the above would compare to the code below. I think it is close, but maybe the code below is on average a few clock cycles faster??

Code: Select all

'reverse the order of the low nibble and invert the logic
'use a temporary byte to accumulate the bits
Dim x as Byte
Dim y as Byte
'x has some arbitrary value
y = 0
if (x and &h01) = 0 then y=y or &h08
if (x and &h02) = 0 then y=y or &h04
if (x and &h04) = 0 then y=y or &h02
if (x and &h08) = 0 then y=y or &h01
x = y

-Tony

[dkinzer]

I need to reverse the order of the bits in a nibble. Is there a way to make this faster than flipping bits in an entire byte?

Usually, the fastest way to do a data transformation is to use a lookup table. The tradeoff, however, is usually code size but in this case, it only requires a 16-byte table to implement the transformation.

Code: Select all

Dim dataTable as ByteVectorData ({
    &H0f, &H07, &H0b, &H03
    &H0d, &H05, &H09, &H01
    &H0e, &H06, &H0a, &H02
    &H0c, &H04, &H08, &H00
})

What algorithm does FlipBits() use.

The ZBasic Library uses an iterative approach to reverse the bit order for a 16-bit word. This same code is used to implement the 8-bit reversal by putting the value in the high 8 bits before calling.

[spamiam]

Usually, the fastest way to do a data transformation is to use a lookup table. ....The ZBasic Library uses an iterative approach to reverse the bit order for a 16-bit word. This same code is used to implement the 8-bit reversal by putting the value in the high 8 bits before calling.

Ah, The lookup technique probably only takes a few clock cycles to complete. The bit reversal code, using shifts, I listed probably takes at least 18 clocks. The comparison code I listed probably averages 12 clocks or so.

So, I think the lookup table speed wins by far. I want to have the code work as fast as reasonably possible because the incoming data (on a GPIB bus) could, in principle, be capable of 1MHz. I don't think my code could achieve that throughput, but I'd like it to manage 100KHz if possible. I think it can do so with your suggestion of a look up table.

I suppose the FlipBits algorithm is slower than the 8 bit shift algorithm I showed above by at least a factor of 2, so I should definitely not use the FlipBits code I had shown.

-Tony

[jay]

Ahhh.. now that you mention ByteVectorData.. I have put off a question I have along THAT line.. I'd like to be able to have a sub that could work with a 'pointer' to one of several different '..VectorData' tables. I've played with using addresses, but have not figured out how to do it..

Using your table as and example, I'd like to be able to:

Call MyGeneralSubroutine(dataTable.address)

Where the argument (dataTable.address) could one one of several tables
.
The sub would be something like:

Code: Select all

Sub MyGeneralSubroutine(currTable() as ??)
Dim count As Integer
count = UBount(currTable)
...
End Sub

I've searched the forum and couldn't stumble onto enough to figure out..
Thanks.. jay

[dkinzer]

I'd like to be able to have a sub that could work with a 'pointer' to one of several different '..VectorData' tables.

It can be done but it isn't as simple as one might like. Essentially, you need to pass the address of the table to the subroutine and you also need some means to indicate how many entries are in the table since UBound() is resolved at compile-time.

One way to do it is shown in the example program below. In this case, the receiving subroutine has two parameters: the address of the table and the number of entries. In the subroutine, a ProgMem Byte array is defined that is based at the passed address.

Code: Select all

Dim tbl1 as ByteVectorData ({
   "abc"
})

Dim tbl2 as ByteVectorData ({
   "defghi"
})

Dim tbl3 as ByteVectorData ({
   "jklmnopqrstuv"
})

Sub Main()
   Call foo(tbl1.DataAddress, UBound(tbl1))
   Call foo(tbl2.DataAddress, UBound(tbl2))
   Call foo(tbl3.DataAddress, UBound(tbl3))
End Sub

Sub foo(ByVal tblAddr as Long, ByVal tblLen as Integer)
   Dim tbl() as ProgMem Byte Based tblAddr
   Dim i as Integer
   For i = 1 to tblLen
      Debug.Print Chr(tbl(i));
   Next i
   Debug.Print
End Sub

Another way to do it is to put the number of elements in the table itself and have the receiving routine read the value from the table before processing the remaining entries.

Code: Select all

Dim tbl1 as ByteVectorData ({
   3
   "abc"
})

Dim tbl2 as ByteVectorData ({
   6
   "defghi"
})

Dim tbl3 as ByteVectorData ({
   13
   "jklmnopqrstuv"
})

Sub Main()
   Call foo(tbl1.DataAddress)
   Call foo(tbl2.DataAddress)
   Call foo(tbl3.DataAddress)
End Sub

Sub foo(ByVal tblAddr as Long)
   Dim tbl() as ProgMem Byte Based tblAddr

   ' read the number of entries from the table, adjust the address
   Dim tblLen as Integer
   tblLen = CInt(tbl(1))
   tblAddr = tblAddr + 1

   ' process the table
   Dim i as Integer
   For i = 1 to tblLen
      Debug.Print Chr(tbl(i));
   Next i
   Debug.Print
End Sub

Note that you could use the GetProgMem() subroutine instead of defining the based ProgMem Byte array but I find the latter a bit cleaner.

[jay]

Don, thanks for the note!! Sorry it was a little off topic..
The light came on when you said:

......It can be done but it isn't as simple as one might like. Essentially, you need to pass the address of the table to the subroutine and you also need some means to indicate how many entries are in the table since UBound() is resolved at compile-time.
......

.. I should have 'dumped' the array and figured that out myself.. especially when I looked at the generated "C" files and saw that the results of UBound was set to a fixed value in the "C" source.. I just wasn't thinking..

Regards jay..

[GTBecker]

If I understand your question, Jay, maybe this will work for you, too.

I built a number of tables of character bitmaps, each of potentially different length, using bytevectordata. The first two bytes of each table preface the bitmap itself with the column and row counts. In an initializing sub, I populated a list with the addresses of each character table, indexed by an ASCII value. Two GetProgMem() calls then retrieve the lengths and bitmap data. E.g.:

Code: Select all

Private Char24_HalfSpace as new bytevectordata({
    9, 24,    ' half-space: 9x24, 27 bytes (half the width of a numeric)
        &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00
})

Private Char24_SingleQuote as new bytevectordata({
    4, 24,    ' "'", 12 bytes
        &h00, &h00, &h00, &hfe, &h00, &h00, &hfe, &h01, &h00, &hfe, &h00, &h00
})

Private Char24_Minus as new bytevectordata({
    9, 24,    ' minus: 9x24, 27 bytes (half the width of a numeric)
        &h00, &h0e, &h00, &h00, &h0e, &h00, &h00, &h0e, &h00, &h00, &h0e, &h00, &h00, &h0e, &h00, &h00, &h0e, &h00, &h00, &h0e, &h00, &h00, &h0e, &h00, &h00, &h00, &h00
})

Private Char24_Decimal as new bytevectordata({
    9, 24,    ' decimal point: 9x24, 27 bytes
        &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &he0, &h00, &h00, &he0, &h00, &h00, &he0, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00, &h00
})

' each 18x24 numeric character bitmap below uses 54 bytes
Private Char24_30 as new bytevectordata({
	18, 24,	' 0
		&h00, &h00, &h00, &h80, &hff, &h03, &hf0, &hff, &h1f, &hf8, &hff, &h3f, &hfc, &h00, &h7c, &h1c, &h00, &h70, &h1e, &h00, &hf0, &h0e, &h00, &he0, &h0e, &h00, &he0, &h0e, &h00, &he0, &h0e, &h00, &he0, &h1e, &h00, &hf0, &h3c, &h00, &h70, &hfc, &h00, &h7c, &hf8, &hff, &h3f, &he0, &hff, &h1f, &h80, &hff, &h03, &h00, &h00, &h00
})
... etc...

Code: Select all

Public CharAddrList24px(&h20 to &h39) as long    ' 24px characters " " through "9"

Public Sub InitCharAddrList24()
    CharAddrList24px(&h20) = Char24_HalfSpace.DataAddress
    CharAddrList24px(&h27) = Char24_SingleQuote.DataAddress
    CharAddrList24px(&h2D) = Char24_Minus.DataAddress
    CharAddrList24px(&h2E) = Char24_Decimal.DataAddress
... etc...
End Sub

Code: Select all

dim CharSizes(1 to 2) as byte
    dim Columns as byte Alias CharSizes(1)
    dim Rows as byte Alias CharSizes(2)

    b = asc(ascchr)    ' form character bitmap index

    Call GetProgMem((CharAddrList24px(b)), CharSizes, 2)    ' get character column and row bit counts
    cntCharBytes = cint(Columns) * cint(Rows) \ 8    ' byte count of character bitmap
    Call GetProgMem(CharAddrList24px(b) + 2, OLED_Buffer(2 + ibuff), cntCharBytes)    ' character bitmap to display buffer

[jay]

Tom, thanks for the sample, I'll file it away for future use.. In my current app, it is cleaner for me to use Don's approach and just pass address and UBound as arguments rather than storing size info in each table.

..jay

If I understand your question, Jay, maybe this will work for you, too.
.......