Any way to work with bits?

[Seymour Clufley]

I've got a structure with one field that is a byte array. The array is so big that the total structure size is over 400mb.

This is annoying because all I need for the byte array is for each index to hold either "1" or "0". There are no other numbers involved. So, I believe a bit array would be sufficient and take up less memory.

Any ideas how/if this can be done?

[eesau]

Hi Seymour,

here's a thread with some asm setbit/getbit functions which should help you get started.

[Seymour Clufley]

Thanks for that, Eesau.

It looks pretty hard. I'll see what I can do with it!

In the meantime does anyone have any ideas how to make an array of bits? And inside a structure? Seems like the structure would include a field that was a pointer to an area of allocated memory big enough to hold X number of bits, X being the size of the array. After that I'm stumped!

[Kaeru Gaman]

you can access any bit with the bitwise operators & (and), | (or), !(xor) and ~(not)
http://www.purebasic.com/documentation/ ... ables.html

get familiar with binary numbers and the values of the 8bit.

the value of the bit, 2^n, can also be expressed as ( 1 << n )
that means you take a ONE, wich is bit0, and shift it to the left until it covers the position of the bit you seek.

you can set a bit using OR.
10010001 | 00000100 = 10010101

you erase a bit using AND NOT, wich means "AND any other than my bit"
10011101 &~ 00001000 =
10011101 & 11110111 = 10010101

you can toggle a bit using XOR
10010101 ! 11000111 = 01010010


just to show you that you don't necessarily need ASM, you can do it with PureBasic alone.
this leads us to these Procedures:

Code: Select all

Procedure.a GetBit ( Value.a, Bit.a )
  ProcedureReturn ( Value & ( 1 << Bit ) )
EndProcedure

Procedure.a SetBit ( Value.a, Bit.a )
  ProcedureReturn ( Value | ( 1 << Bit ) )
EndProcedure

Procedure.a ClrBit ( Value.a, Bit.a )
  ProcedureReturn ( Value &~ ( 1 << Bit ) )
EndProcedure

Procedure.a TglBit ( Value.a, Bit.a )
  ProcedureReturn ( Value ! ( 1 << Bit ) )
EndProcedure

Mind you: using the code directly is faster than procedures and using type Integer (one register) is faster than using unsigned byte.
so, I would access the Memory Long-Value-wise and handle 32bits per Structure Field.

PS: sorry, I was writing this while you wrote your last post.
I will reply to that a bit later.

[Kaeru Gaman]

create a Long-Array within your structure.
you can access the bits within with the following formula:

Code: Select all

; the lower 5bit of the index give us the number of the bit
Bit = Index & 31 
; the higher bits are the number of the Long-Field in the Array
Field = Index >> 5

Index is the Index of the Bit.
the first Long holds Bits 0-31, the second 32-63, third 64-95, etc.

you can retrieve the value of any Long-Field simply by Arrayindex.
access the Bit like shown before.

I got some code ready, thank you for offering this practice.

Code: Select all

; the lower 5bit of the index give us the number of the bit
; Bit = Index & 31 

; the higher bits are the number of the Long-Field in the Array
; Field = Index >> 5

Structure Test
  field1.l
  field2.l
  arry.l [255]
EndStructure

Define myTest.Test

Procedure SetBit ( *StrucVar.Test, Index.l )
  Protected Bit.l
  Protected Field.l
  Bit = Index & 31 
  Field = Index >> 5
  *StrucVar\arry[Field] | ( 1 << Bit )
EndProcedure

; we use bit 4 of field 15 = Bit 484 of the BitArray to test

SetBit( @myTest, 15*32+4 )
Debug myTest\arry[15]

Procedure.l GetBit ( *StrucVar.Test, Index.l )
  Protected Bit.l
  Protected Field.l
  Protected Result.l
  Bit = Index & 31 
  Field = Index >> 5
  Result = ( *StrucVar\arry[Field] & ( 1 << Bit ) ) >> Bit
  ProcedureReturn Result
EndProcedure

Debug GetBit( @myTest, 15*32+4 )

Debug "-----------------------------"

Procedure ClrBit ( *StrucVar.Test, Index.l )
  Protected Bit.l
  Protected Field.l
  Bit = Index & 31 
  Field = Index >> 5
  *StrucVar\arry[Field] &~ ( 1 << Bit )
EndProcedure

myTest\arry[15] = $FFFFFFFF

Debug Bin( myTest\arry[15], #PB_Long )

ClrBit( @myTest, 15*32+4 )

Debug Bin( myTest\arry[15], #PB_Long )

Debug "-----------------------------"

Procedure TglBit ( *StrucVar.Test, Index.l )
  Protected Bit.l
  Protected Field.l
  Bit = Index & 31 
  Field = Index >> 5
  *StrucVar\arry[Field] ! ( 1 << Bit )
EndProcedure

myTest\arry[15] = $FFFFFFFF

Debug Bin( myTest\arry[15], #PB_Long )

For n=0 To 31 Step 3
  TglBit( @myTest, 15*32+n )
Next

Debug Bin( myTest\arry[15], #PB_Long )

[Thorium]

As Kaeru said, you have to use the bitwise operators for that. Something like a bit array is not realy existing. The smalest addressable unit is a byte. So in order to use a byte as a array of 8 bits you have to use some math. Looks complicated at first but if you got it, it's not that hard after all.

[rsts]

Very nice, Mr Gaman.

cheers

[Kaeru Gaman]

Very nice, Mr Gaman.

thank you

[skywalk]

Thank you professor KG!
Your posts are always informative.

[infratec]

Hi,

thanks Kaeru for your nice code
Since I want to use it also for real arrays, I slightly modified it:

Code: Select all

#MaxBits = 1024


Macro BitArraySize(Bits)
 (Bits - 1) / 8 + 1
EndMacro


Structure Test
 arry.a [BitArraySize(#MaxBits)]
EndStructure

Define myTest.Test

Dim NormalArray(BitArraySize(#MaxBits))


Debug "Arraysize: " + Str(ArraySize(NormalArray()))


Procedure InitBits(*A.a, Bits.l, Value) 
 If Value <> 0 : Value = $FF : EndIf
 FillMemory(*A, BitArraySize(Bits), Value)
EndProcedure


Procedure SetBit(*A.a, Index.l)
 *A + (Index >> 3)
  PokeA(*A, PeekA(*A) | (1 << (Index & 7)))
EndProcedure


Procedure ClrBit(*A.a, Index.l)
 *A + (Index >> 3)
 PokeA(*A, PeekA(*A) &~ (1 << (Index & 7)))
EndProcedure


Procedure TglBit(*A.a, Index.l)
 *A + (Index >> 3)
 PokeA(*A, PeekA(*A) ! (1 << (Index & 7)))
EndProcedure


Procedure.a GetBit(*A.a, Index.l)
 *A + (Index >> 3)
 ProcedureReturn (PeekA(*A) & (1 << (Index & 7))) >> (Index & 7)
EndProcedure


InitBits(@myTest\arry, #MaxBits, #False)

SetBit(@myTest\arry, 4)
Debug GetBit(@myTest\arry, 4)

ClrBit(@myTest\arry, 4)
Debug GetBit(@myTest\arry, 4)

TglBit(@myTest\arry, 4)
Debug GetBit(@myTest\arry, 4)


InitBits(@NormalArray, #MaxBits, #True)

SetBit(@NormalArray, 144)
Debug GetBit(@NormalArray, 144)

ClrBit(@NormalArray, 144)
Debug GetBit(@NormalArray, 144)

TglBit(@NormalArray, 144)
Debug GetBit(@NormalArray, 144)

Now we can use it for both cases.

And I added the procedure InitBits().

Bernd

[Kaeru Gaman]

@infratec

nice one!

you should perhaps think about using Long, too. it's not that big difference to code and it may prove more performant.

note, your 'size' parameter is in Byte while the 'index' is in Bit.
what about setting 'size' in Bit, too? you can divide by 8 in your init, resp. by 32 if you use Long.

Code: Select all

Int(( size -1 ) / 32) + 1

will provide the fitting amount of Longs for any odd number of Bits.
perhaps some Shared size value could be used to check index range.

the next idea occuring to me is, change the Init procedure to some DimBits or so,
let it allocate the wanted amount of Mem and add an Element to a LList that holds MemPointer and Size.

... but then again, I don't think a BitArray is some that important tool that tons of Apps would need tons of BitArrays...

[infratec]

Hi Kaeru,

I modified my program according to your suggestion.
Now I use the bit count.

Since I'm coming from the microcontroller side, I'm still thinking in bits and bytes.
When we want to optimize this for speed, we have to use the 'natural' size of the used CPU.

So an additional compilerif is neccessary to detect 32 bits or 64 bits.
But I don't know if this really makes sense.

Maybe I make a small 'performance' test.

Bernd

[Kaeru Gaman]

When we want to optimize this for speed, we have to use the 'natural' size of the used CPU.

that is correct, but if you compile it on x86, you'll get 32bit for .i anyways, and it will run in 32bit compatibility mode when run on a x64 system.
besides, a lot of 32bit OSes nowadays run on machines with x64chips already.

so, I think it's no problem to hardcode it with Long.
you only need to use .i if you want it to be an include.pbi that should be used on an x64 compiler aswell,
so I'd say it's not even worth the effort.

and the other side is, that using Byte for sure is slower on both systems.

[infratec]

Hi Kaeru,

maybe I made a fault, but...
the byte variant is faster than the long variant:

Code: Select all

#MaxBits = 1024

Macro BitArraySize(Bits)
 (Bits - 1) / 8 + 1
EndMacro

Dim NormalArray(BitArraySize(#MaxBits))

Procedure TglBit(*A.a, Index.l)
 *A + (Index >> 3)
 PokeA(*A, PeekA(*A) ! (1 << (Index & 7)))
EndProcedure

Procedure TglBitl(*A.l, Index.l)
 *A + (Index >> 5)
 PokeL(*A, PeekL(*A) ! (1 << (Index & $1F)))
EndProcedure

StartTime = ElapsedMilliseconds()
For i = 0 To 10000000
 TglBitl(@NormalArray, 144)
Next i
Debug ElapsedMilliseconds() - StartTime

StartTime = ElapsedMilliseconds()
For i = 0 To 10000000
 TglBit(@NormalArray, 144)
Next i
Debug ElapsedMilliseconds() - StartTime

On my PC:

Long: 6031ms
Byte: 5781ms

And it is not an IBM XT (8088) with Windows 3.11

Any ideas ?

Bernd

[Kaeru Gaman]

Any ideas ?

yes.

never run a performance check with debugger on