Page 1 of 2
Any way to work with bits?
Posted: Wed Feb 24, 2010 6:18 am
by 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?
Re: Any way to work with bits?
Posted: Wed Feb 24, 2010 7:03 am
by eesau
Hi Seymour,
here's a thread with some asm setbit/getbit functions which should help you get started.
Re: Any way to work with bits?
Posted: Wed Feb 24, 2010 10:20 am
by 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!
Re: Any way to work with bits?
Posted: Wed Feb 24, 2010 10:34 am
by 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.
Re: Any way to work with bits?
Posted: Wed Feb 24, 2010 11:11 am
by 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 )
Re: Any way to work with bits?
Posted: Wed Feb 24, 2010 5:22 pm
by 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.
Re: Any way to work with bits?
Posted: Wed Feb 24, 2010 5:26 pm
by rsts
Very nice, Mr Gaman.
cheers
Re: Any way to work with bits?
Posted: Wed Feb 24, 2010 5:41 pm
by Kaeru Gaman
rsts wrote:Very nice, Mr Gaman.
thank you
Re: Any way to work with bits?
Posted: Wed Feb 24, 2010 5:48 pm
by skywalk
Thank you professor KG!
Your posts are always informative.
Re: Any way to work with bits?
Posted: Thu Feb 25, 2010 10:22 am
by 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
Re: Any way to work with bits?
Posted: Thu Feb 25, 2010 11:09 am
by 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.
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...
Re: Any way to work with bits?
Posted: Thu Feb 25, 2010 11:38 am
by 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
Re: Any way to work with bits?
Posted: Thu Feb 25, 2010 12:53 pm
by Kaeru Gaman
infratec wrote: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.
Re: Any way to work with bits?
Posted: Thu Feb 25, 2010 1:12 pm
by 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
Re: Any way to work with bits?
Posted: Thu Feb 25, 2010 1:24 pm
by Kaeru Gaman
infratec wrote:Any ideas ?
yes.
never run a performance check with debugger on
