search:

General



Rooms & Areas



Presence



Systems



Wiki Help



pmwiki.org



edit menu
Edit Page Upload Security

Binary Numbers And Math

December 2nd, 2005

A bug had been discovered that caused items purchased in the V'Rung Armory to seem to vanish when a player placed the items inside any container. However, the items were being put ON the containers, instead of inside them. For reference, the V'Rung Armory has all buyable wares ON furniture items, instead of lying on the ground like with most stores. Below is an explanation of how this problem was fixed, along with a lesson in binary counting systems and binary math and logic.

The problem was that when the items were being duplicated in the purchasing process, the flagging for in/on/under/behind was not being reset. So when you bought an item ON a counter, etc., the first time you put it away the ON flag would still be set and then when you removed it from the container the flags were removed properly. Those flags are stored as part of an object's Data1 row of data, in field #4. In EaxiaSEL, we refer to this as $object:data1:4. On, under, and behind use a combination of bitwise flags that weren't being filtered out in the purchase process and to fix this, programmatically, we need to understand how binary numbers work and how to perform binary math.

The Binary Counting System

Everything on a computer is stored as a series of zero's and one's because electronically a computer can only determine if an electronic signal is on (voltage/currant) or off (memory) as well as magnetically (hard drives/disks use positive and negative fields). A single bit of data uses either a 0 or a 1.

In our decimal system, each digit ranges from 0-9. For example, 394 is a 3 in the 100's place, a 9 in the 10's place, and a 4 in the 1's place. However, the binary system uses digits ranging from only 0-1, so when you would otherwise roll over to a 2, you would have to increment the size of the number.

For example, in binary, you would count like this:

	Decimal 0 = Binary    0
	Decimal 1 = Binary    1
	Decimal 2 = Binary   10
	Decimal 3 = Binary   11
	Decimal 4 = Binary  100
	Decimal 5 = Binary  101
	Decimal 6 = Binary  110
	Decimal 7 = Binary  111
	Decimal 8 = Binary 1000
	Decimal 9 = Binary 1001
        etc.

Bits And Bytes

A single byte of data is comprised of eight bits. An eight-digit number in decimal would store numbers from 0 to 99,999,999. But an eight-digit number in binary can only store numbers from 0 to 1111 1111. (We don't group binary numbers with commas, and we don't separate them every third digit, so the formatting of binary numbers may look odd at first.)

The binary number 1111 1111 means, in English: a 1 in the 1's place, a 1 in the 2's place, a 1 in the 4's place, a 1 in the 8's place, a 1 in the 16's place, a 1 in the 32's place, a 1 in the 64's place, and a 1 in the 128's place. The sum of which is 255. So a single byte of data stores numbers from 0-255 (in decimal).

On all Windows 32-bit systems, the largest size of data is typically 32-bit. (There are methods around that restriction to get bigger numbers, but that's beyond the scope of this lecture.) This includes operating systems such as Windows 95, 98, Me, 2000, XP and 2003.

A thirty-two-bit number is made up of four bytes, holding a range of values from 0 to 1111 1111 1111 1111 1111 1111 1111 1111 (0 to 4,294,967,295 in decimal).

How Binary Numbers Are Used In Eaxia

Treating these numbers as their natural binary state gives us an advantage, even if it seems confusing to do at first because of our natural consideration for the decimal system. Since each digit is either a 0 or a 1, we can relate this to yes/no or on/off settings, like a row of 32 light switches turned either on or off.

A bit that's used like an on/off setting is called a 'flag.' Most of the data used on objects, players, etc. uses a 32-bit value to store data. For $object:data1:4, the variable is treated as binary so we can flag on/off specific settings about the object. If you look at the Object OLC-Helper, under the 'Other Flags' tab, you'll see a list of 'Object Type Flags' numbered #00 through #17. These flags correspond to the placement of bits numbered #00 through #32 in $object:data1:4.

So, if $object:data1:4 for a backpack was 0000 0000 0000 0000 0000 0000 0000 0001, then only one flag would be turned on, the 'is this item a container' flag (flag #00, the right-most digit).

Let's treat this as a 16-bit number for now (flags for 00-15) just to make it easier to read (less digits to think about)...

Our backpack's $object:data1:4 being 0000 0000 0000 0001 means that flag #00 (right-most digit) is ON/1 and flags #01 through #15 (the rest of the digits, starting with #01 and moving up until #15) are OFF/0. Looking at the Object OLC-Helper for reference, we know exactly what flags #00 through #15 mean. Some aren't labeled, but in general, we can pick apart what we need to in order to understand what settings are used for this object. Thankfully, the OLC-Helper does the dirty work of converting checkboxes into bits and stringing them all together to fit in $object:data1:4 so we don't have to do any nasty calculations ourselves.

Now, if the item was 'cursed' and a 'container', then $object:data1:4 would be 0000 0000 0010 0001 (if we still treat it as a 16-bit number), which means: an ON/1 flag in #05 and an ON/1 flag in #00.

Similarly, if the item was 'cursed' and 'invisible' then $object:data1:4 would be 0000 0000 0010 1000, which means: an ON/1 flag in #05 and an ON/1 flag in #03. Since it is a 32-bit field, it'd technically be 0000 0000 0000 0000 0000 0000 0010 1000.

Checking the object data (SHOW_OBJECT_DATA) for our sample backpack, we see...

	Object data for a leather backpack:
	Object ID: 133210
	Ar/Ds/Nm:  'a' 'leather' 'backpack'
	Script:    0
	There are no items inside of it.
	Data1:     1 0 17 131073 14 0 32769 0
	Data2:     200 0 0 0 0 0 0 0
	Data3:     0 0 0 0 0 0 0 0
	Data4:     0 0 0 0 0 0 0 0 0 0
	Data5:     0 0 0 0 0 0 0 0 0 0
	LOOK: ''
	READ: ''

The fourth number in the object's 'Data1' line ($object:data1:4) is 131073. This is the decimal conversion of a 32-bit binary number corresponding to the flags/bits we've been talking about, so let's convert this to binary to look at the individual flags...

To convert, start your Calculator program (go to Start -> Run and type CALC, or go to Start -> Programs -> Accessories -> Calculator) and go to View -> Scientific. Now enter 131,073 into the calculator and click on 'Bin' to convert it to a binary number (it will trim the left-most 0's).

You should get 10 0000 0000 0000 0001 (0000 0000 0000 0010 0000 0000 0000 0001 if Calculator would have kept it as a 32-bit number). This number means that flags #17 and #00 are turned ON/1, and the rest are OFF/0. In Object OLC-Helper, we know what those flags mean: 'GameMaster only' and 'Container'.

Binary Math In EaxiaSEL

When an item is inside of another item, we can check its relationship to its container item. We have the following relationships: IN (inside of), ON (on top of), UNDER (underneath), and BEHIND (behind something), which is a list of four possible relationships. It seems a waste to dedicate a whole variable, that can hold a range of up to 4 billion when we only need space for up to 4. The best way to get space for a list of 4 outcomes is to use two bits, joined together. The possible combination of two bits together are 00, 01, 10, and 11, so we use them to identify the four relationships of an item to its container item:

	00 = IN
	01 = ON
	10 = UNDER
	11 = BEHIND

Items use two bits, flags #15 and #16, for exactly this purpose. Since we read the places of numbers starting right to left (1's, then 10's, then 100's, then 1,000's, etc. in decimal and the same for binary), that means that if an item is ON another item, that flag #15 is turned ON/1 and flag #16 is turned OFF/0. Object OLC-Helper should be updated to show meanings for flags #15 and #16, but the combination of using them both to mean something new when they're *both* on could be confusing.

So, let's put this into an example: let's say we have an arrow for a bow. This arrow is inside someone's backpack right now. There should be no reason ANY of the flags in object:data1:4 should be turned on, therefore object:data1:4 = 0 (thirty-two bits of 0's). If the player were to go to his house, take out the arrow, and then put it ON a table, then now the object:data1:4 of the arrow should be: 0000 0000 0000 0000 1000 0000 0000 0000 (0 in bit #16 and 1 in bit #15). Remember: the RIGHT-most bit is #00, not #01... count starting with #00.

If the player took the arrow and put it...

	in the backpack:     0000 0000 0000 0000 0000 0000 0000 0000
	on the table:        0000 0000 0000 0000 1000 0000 0000 0000
	or under the rug:    0000 0000 0000 0001 0000 0000 0000 0000
	behind the dresser:  0000 0000 0000 0001 1000 0000 0000 0000

Notice how flags/bits #15 and #16 indicate the four possible relationships of an item to its container item.

The problem with the script that buys items from the shop is that it was built with the idea that all items would be directly on the ground for purchase; therefore, not IN, ON, UNDER, or BEHIND other objects/containers/furniture. And therefore, it does not modify the duplicated (purchased) object to have bits #16 and #15 set to 0.

So now, the problem should be rather clear. Because when those flags are left on and the player goes to put the item away, the flag moves it funny. The solution may also be clear, but not the process -- how do we change part of the data in a field of bits through EaxiaSEL?

This is where bitwise operations come into play. There are logical operators and bitwise operators. There are also mathematical operators. We've seen logical operators: && (logical AND), || (logical OR). Bitwise operators: & (bitwise AND), | (bitwise OR), ~ (bitwise inverse), << (bitwise shift left), and >> (bitwise shift right). We use bitwise operators to perform operations on numbers on a bit-by-bit basis.

The easiest to understand is bitwise OR, so we'll start there. Bitwise OR adds the results of two bitfields together, comparing each bit place together. If EITHER number is ON/1 in that place, the result will be ON/1 in that place (from one number or the other), but if both numbers have OFF/0 in that place, the result will be OFF/0 in that place. For example: 0001 0011 | 0011 0100 = 0011 0111. We aren't adding the two numbers together, we're making a comparison of each bit.

Simple Examples of OR:

	0001 | 0001 = 0001
	0001 | 0000 = 0001
	0010 | 0110 = 0110
	1101 | 1001 = 1101
	1111 | 1111 = 1111

AND works similarly, but both bits must be ON/1.

So, examples of AND:

	0001 & 0011 = 0001
	1011 & 1111 = 1011
	1110 & 1101 = 1100

Bitwise inverse (~) simply takes all of the 1's and makes them 0's. Likewise, all of the 0's and makes them 1's. There are practical applications for this, and we will have to use it for our fix.

In most programming languages, this would look like: ~0010 = 1101. However, I wrote EaxiaSEL to be fast, which means its less flexible towards syntax. So ALL expressions must have two conditions/parts. ~0010 is 1 operator and 1 condition. So, in EaxiaSEL we use a 'dummy' number: a condition/number/part that has NO significance and the value is ignored, just for the sake of syntax. We'll use the number 0, just for fun (since it doesn't matter). In EaxiaSEL, we would write the expression ~0010 as: 0010 ~ 0. So if we: SET A0 TO (0010 ~ 0), it would set A0 to 1101 (technically, since A0 is a 32-bit value, it would set A0 to 1111 1111 1111 1111 1111 1111 1111 1101). That's how bitwise inverse works.

Shifting is fun. << and >> take all the digits and move them X spaces over in one direction or another. If we have 0001 0000 and shift it RIGHT 2 spaces, it would be 0000 0100, which is written like 0001 0000 >> 2. Bits are not 'wrapped' around to the other side. They are dropped/lost and new digits become 0's automatically. So since all binary values are 32 bits, doing this: A0 << 32 - would wipe out EVERY digit, leaving you with 32 zeros. There is some practical use for this.

If we wanted to easily check if the GameMaster flag (flag #17) was on an item, that would be: 1 << 17. This is easier than going into the calculator, typing 0010 0000 0000 0000 0000 in, and changing it to 131,072. Which seems clearer? SET A0 TO (1 << 17) or SET A0 TO (131072) when working with flag #17?

Now, with our example, if we wanted to check flag #17, we would: IF ($object:data1:4 & (1 << 17)). Bitwise AND comparison of the bits in object:data1:4 with the bitwise representation of flag #17. That just checks to see IF the flag is on or off. To turn off a flag, we want to bitwise AND it with the INVERSE of the flag.

Say that we have an item that we want to programmatically remove flag #17 from, but we don't want to disturb any of the others. That's where inverse comes into play. We can: SET A0 to ($object:data:4 & ((1 << 17) ~ 0)).

Why? Because... 1 << 17 = 0000 0000 0000 0010 0000 0000 0000 0000.

Then, the inverse: 0000 0000 0000 0010 0000 0000 0000 0000 ~ 0 = 1111 1111 1111 1101 1111 1111 1111 1111.

And if this were our backpack from the earlier example (which has 0000 0000 0000 0010 0000 0000 0000 0001, container and GM-only flags on), then the logical AND: 0000 0000 0000 0000 0010 0000 0000 0000 0001 & 1111 1111 1111 1101 1111 1111 1111 1111 = 0000 0000 0000 0000 0000 0000 0000 0001

(Because we're bitwise-AND'ing against every single bit being ON except the one we're after).

From right-to-left, bit #0 in both places is on. The rest of the bits are missing the on/off in one of the other numbers. That is how we programmatically turn OFF bits without disturbing the rest.

Here's an easier example, we'll just use 8 bits with 0100 1110 for our value with the intention to turn off bits #02 and #03.

We use the inverse of bits #02 and #03: 0000 1100 ~ 0 = 1111 0011

And then use our original number to AND with: 0100 1110 & 1111 0011 = 0100 0010

Comparing our original number of 0100 1110 and our result number of 0100 0010, we see that we programmatically turned off flags #02 and #03 without affecting the other bits that were on/off.

We're getting closer, because we just turned off two bits, which is what we need to do with our problem here (bits #15 and #16). How do we write that easily? Let's go back to our last problem. How do we write bits #02 and #03 easily? We know that the binary number for bits #02 and #03 being ON/1 is written as 1100 in binary (12 in decimal). So we could technically have written our expression as: (x & (12 ~ 0)).

(Note: EaxiaSEL understands expressions that perform binary operations on decimal values, but we can't write numbers in their binary equivelants, we *must* write them as decimal numbers).

However, bits #15 and #16 will be expressed by a much bigger number, so how do we write 'bits #15 and #16' without writing it as 98,304 (which is 0000 0000 0000 0001 1000 0000 0000 0000 in binary)? We COULD just: SET A0 TO ($object:data1:4 & (98304 ~ 0)) and be done with it, because that is perfectly legal and the correct solution, but that's not a friendly number to consider if anyone had to come back and figure out what we're doing.

The easiest to understand version would be:

SET A0 TO ($object:data1:4 & (((1 << 15) | (1 << 16)) ~ 0))

This is the:

combination of flags #15 and #16
inverted
AND'ed against our bitfield

A smaller equation would be:

SET A0 TO ($object:data1:4 & ((3 << 15) ~ 0))

It means: 3 (0011 in binary), shifted to the left 15 spots, which yields the same as the first equation (0001 shifted over 15 and 0001 shifted over 16). 3 is probably easier to cope with because it is a smaller equation, but it is more cryptic because it doesn't clearly identify the individual bits. Either is correct, and technically I would go with the former equation, since we're trying to be nice to the would-be reader (which is why we didn't give up with 98,304)..

So what we needed to do, in the BUY section of the room script for generic stores (Script #1264), is modify the object in this way:

        SET A1 TO ($object:data1:4 & (((1 << 15) | (1 << 16)) ~ 0))
        CHANGE_OBJECT_DATA1 $object:data1:1 $object:data1:2 $object:data1:3 $A1 $object:data1:5 $object:data1:6 $object:data1:7 $object:data1:8

After uploading the fix, and reloading the script, we tested it by purchasing an dagger from the store and did SHOW_OBJECT_DATA DAGGER:

	Object data for a bone-handled dagger:
	Object ID: 156193
	Ar/Ds/Nm:  'a' 'bone-handled' 'dagger'
	Script:    0
	There are no items inside of it.
	Data1:     0 0 0 0 1 3000 1 2
	Data2:     1 3 2 0 0 1 2 4
	Data3:     0 0 0 0 0 0 0 0
	Data4:     0 0 0 0 0 0 0 0 0 0
	Data5:     0 0 0 0 0 0 0 0 0 0
	LOOK: ''
	READ: ''

Originally, the item would have flag #15 on $object:data1:4 (#16=0/#15=1 means the item is ON its container). Now it has 0, so we don't have to throw it into Calculator to see what each bit is, individually, we know that all the flags are off so the fix worked. We could test it by putting it in a container, for example if we were purchasing an item that had other flags like a backpack from previous examples. We will see that the item is put IN the backpack, not ON. Before the fix, if you had done a SHOW_OBJECT_DATA for the store items, you would see flag #15 on and if you loaded it in the OLC helper, you'd see that the grayed-out checkbox for #15 would be checked which would have given away part of the problem at the beginning if you knew what the significance of those flags meant.

So, this bug is fixed, permanently, for any other store that uses the generic store script. And now we all know a little more about binary math.

Recent Changes - Page History - Printable View
Page last modified on January 12, 2006, at 10:55 AM EST
PmWiki 2.20-beta16 - www.PmWiki.org