Main Site Links Resources Tutorials
News VB Gaming Code Downloads DirectX 7
Contact Webmaster VB Programming Product Reviews DirectX 8
  General Multimedia Articles DirectX 9
      Miscellaneous

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...

DirectX 4 VB 2000 Jack Hoxley. All rights reserved.
Reproduction of this site and it's contents, in whole or in part, is prohibited,
except where explicitly stated otherwise.
Design by Mateo
Contact Webmaster