|
Tips
And Tricks: Binary Manipulation
Author:
Jack Hoxley
Written: 4th
May 2001
Contact: [EMail]
Contents
of This lesson:
1. Introduction
2. Bit fields
3. Flag combining
1.
Introduction
This
tutorial isn't greatly important in the
grand scheme of things, but I wanted to
cover a couple of useful topics that may
well help you out at some point. In
general VB shields us from the low level
binary manipulation (binary is the
010100111010001 stuff!), but there are
times that we may want access to them,
for example, when directly accessing
memory in DirectX we are often required
to directly manipulate the raw data -
where 3 values are stored in 1 (and we
need to get them out)...
2.
Bit Fields
You
should be familiar with the 'Boolean'
datatype - often fundamental to the
operation of many programs, particularly
games. Well, there's one slight problem
with them - they're a bit slow, and they
take up a lot of space. Each 'Boolean'
datatype is a 16 bit (2 byte) signed
number - normally, using an integer of
the same size you have 65536 possible
values, a Boolean of the same space will
only store true/false. Partly because of
this, conversion must take place - you
assign 1645 to a Boolean value and it'll
come back as -1 (true), so there must be
something in there that's converting
them... which will also slow things
down.
Bit
fields are a clever way of reducing the
size that these Booleans take up. One
possible (and often used) method of
collision detection is to store a
true/false value for every
tile/pixel/area in a game world -
100x100 grid = 10000 values, if stored
as a Boolean you're already using up
20,000 bytes of memory (19.5kb),
whereas, if you were clever, you could
fit those 10,000 values into only 1250
bytes (1.2kb) - which is considerably
smaller than the original - expand the
maths a little further, take a 640x480
image, each pixel has a passable
true/false collision flag - that's
307,200 values - stored as booleans
it'll be 600kb, stored in my clever
little method it'll cost you 37.5kb...
So what
is my clever little method then? well,
we're going to be storing each boolean
flag as a single bit (binary digit), a
binary digit is 1 or 0 (on or off),
effectively the same as a boolean - true
or false, on or off. So it makes sense
to use the smallest possible unit. You
may now be thinking that there isn't a
bit datatype (or anything similiar),
thats because there isn't.
We're
going to use the "Byte"
datatype, it is the smallest possible
value, and is unsigned (which means it's
never a negative number); as it's a byte
it's made up of 8 bits, therefore we can
store 8 on/of or true/false values in
each byte - if we then make an array of
these bytes we can store many thousands
very easily - the smaller values that I
demonstrated above were taken by
dividing the total number of values by
8, 8 of them go into a byte, so the
final number is the total number of
bytes...
The
following piece of code is all that is
required to make a simple bit field,
calling SetBool( ) will change the
current value at that point, and GetBool(
) will return the current value at that
point - all you really need.
Private BitField(0 To 99) As Byte '100 bytes = 800 boolean values
Private Function GetBool(N As Long) As Boolean
If (BitField(N \ 8) And 2 ^ (N - ((N \ 8) * 8))) = 2 ^ (N - ((N \ 8) * 8)) Then GetBool = True
End Function
Private Sub SetBool(N As Long, Val As Boolean)
If Val = True Then
BitField(N \ 8) = BitField(N \ 8) Or 2 ^ (N - ((N \ 8) * 8))
Else
BitField(N \ 8) = BitField(N \ 8) Xor 2 ^ (N - ((N \ 8) * 8))
End If
End Sub
|
|
|
|
Looks kind
of scary doesn't it! Lets have a look at
all of this. A byte datatype has a
minimum value of 0, and a maximum value
of 255, described by 8 bits (when all of
them are 0, the result is 0, when all of
them are 1, the result is 255). Each bit
represents a 2^n number, where n is the
bit (0 to 7); to calculate the binary
number 01101101 we just add up all of
the 2^n values for the bits which are
'1', the bit number goes from right to
left, ie, 76543210, so in the previous
number, we have 2^0 + 2^2 + 2^3 + 2^5 +
2^6 = 1 + 4 + 8 + 32 + 64 = 109. Now,
the next part are the logical bitwise
operators (And, Or, Xor) - these all
perform a comparison between two bits
(or when used with numbers, all of the
bits individually), take the following
truth tables:
AND:
| Input
1 |
Input
2 |
Output |
| 0 |
0 |
0 |
| 0 |
1 |
0 |
| 1 |
0 |
0 |
| 1 |
1 |
1 |
OR:
| Input
1 |
Input
2 |
Output |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
1 |
XOR:
| Input
1 |
Input
2 |
Output |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
0 |
We
could now do a quick sum using these,
which is the basis of our code. Notice
that when we are using GetBool it uses
the logical AND operator, well this
basically says that, if the source and
the destination have the same bits, then
the output will have the same as the
destination. Or, for a better example:
01111011
00100000
-------- AND
00100000
What
a surprise, the result is the same as
the second input! so, in VB code we
could say:
If (X And Y) = Y then The_Bit_Is_True
which, if you look up to the top of the
code again, is exactly what I've done.
All the brackets and maths symbols are
just so that we can find which byte to
read from, and which bit within that
byte we are checking.
The
Same goes for the Or'ing and the XOR'ing....
The OR is used to set a bit, which, by
looking at the truth table above should
be fairly obvious. XOR'ing is used to
turn a bit off, which you can see from
the truth table...
One
final thing to do, should you want to
use this method for a 2D array you're
going to need a way of converting an X,Y
coordinate into a single N value. This
can be quite easily done using X+(Y*Width),
where the array would be a 100x100 array
(of 0-99 scale) the formula works out as
99+(99*100) = 9999, the last element in
a (100x100)-1 sized array... Just
remember to make sure that the bit field
array is large enough...
3.
Flag Combining
Even
if your new to the DirectX world you'll
very quickly see that it uses a lot of
functions where you can specify lots of
options in one parameter, for example,
in Direct3D8, to create a Flexible
Vertex Format you use notation like:
Const
FVF =
(D3DFVF_XYZ
or
D3DFVF_DIFFUSE
or
D3DFVF_TEX1)
Const
FVF2 =
(D3DFVF_XYZ
or
D3DFVF_NORMAL
or
D3DFVF_TEX2 |
|
|
|
Both are
stored in a 32bit integer (Long), yet
there are many many different
combinations that can be used. Whilst it
isn't greatly important to understand
how this works, it may be useful if you
come to create your own game engine, or
AI state engine etc... Where you want to
have a number of possibilities, but
don't want to hardcode them all in as
separate functions.
Take
the following example for a generic
graphics engine initialisation:
| InitGraphics(bUseFullscreen,
iModelDetail,
iTextureDetail, 0, 0, 0, 0, 0,
bSpecialFX) |
|
|
|
Not too
pretty really is it... lots of 0's
indicating that we don't want to specify
that parameter etc...
InitGraphics GROPT_STARTFULLSCREEN Or _
GROPT_USEHIDETAILMODELS Or _
GROPT_USEHIGHTDETAILTEXTURES Or _
GROPT_USESPECIALEFFECTS
|
|
|
|
It may
look like more work, but using VB's
intellisense dropdown parameter lists,
it's as easy as selecting them from a
list (really!). And the best part is, we
don't have to specify any parameters
that we don't want to. This method may
not suit your engine perfectly, but it
can be extended in various different
ways...
To
implement the second type of function
calling, we need this code:
Private Enum Options
GROPT_STARTFULLSCREEN = 2 ^ 0
GROPT_STARTWINDOWED = 2 ^ 1
GROPT_USEHWTNL = 2 ^ 2
GROPT_USEPUREDEV = 2 ^ 3
GROPT_USELOWDETAILMODELS = 2 ^ 4
GROPT_USEMEDDETAILMODELS = 2 ^ 5
GROPT_USEHIDETAILMODELS = 2 ^ 6
GROPT_USELOWDETAILTEXTURES = 2 ^ 7
GROPT_USEHIGHTDETAILTEXTURES = 2 ^ 8
GROPT_USESPECIALEFFECTS = 2 ^ 9
GROPT_USEDYNAMICLIGHTS = 2 ^ 10
End Enum
Private Function InitGraphics(ParamList As Options) As Boolean
If ParamList And GROPT_STARTFULLSCREEN = GROPT_STARTFULLSCREEN Then
'initialise fullscreen mode
ElseIf ParamList And GROPT_STARTWINDOWED = GROPT_STARTWINDOWED Then
'initialise in windowed mode
End If
End Function
|
|
|
|
The
enumeration type is used to reference a
bit number to a name, our function can
then split them apart to work out which
values are set; the above example only
does it for the first two enumerations -
but the process is the same for all 10
of them. Note that you can only have up
to 31 enumerations of this type (2^0 to
2^30) due to the maximum value they hold
(32bit long integer).
Look
back at the previous section about bit
fields, remember that X or Y is used to
set a bit and (X and Y)=Y is used to
test a bit for on/off status; these are
used again here.
Hopefully
you've learned something useful here,
nothing particularly ground breaking -
but it's the sort of thing that can be
the perfect solution to that little
problem that you've been working on
recently...
|
