Assembly Language Programming - Lesson 2 - Enumeration

[Robert M]

Lesson 2: Enumeration

 

In lesson 1 we introduced the idea of a bit. We learned that a bit is the smallest piece of information in a computer. We learned that a bit can have either the value 1 or 0. We also learned that we as programmers can assign any meaning we wish to individual bits used by our program.

 

In this lesson we will look at the important programming practice of enumeration.

 

e·nu·mer·ate

 

  1. To count off or name one by one; list: A spokesperson enumerated the strikers' demands.

  2. To determine the number of; count.

 

Let's say you want the to write a computer game where the player is picking fruit. There are 4 kinds of fruit in the game: Apples, Oranges, Bananas, and Cherries. All 4 kinds of fruit can be on the screen at the same time. Therefore, your program must keep track of each piece of fruit on the screen, and remember what kind of fruit it is so that it can draw the fruit correctly, and award the correct points to the player when they pick the fruit.

 

The easiest way to track the different kinds of fruit is to enumerate them

Apple = 0

Orange = 1

Banana = 2

Cherries = 3

 

All information in a computer is stored in bits so let's convert that to a bit:

Apple = 0

Orange = 1

Banana = ??

 

Uh oh! We have run out values to enumerate our fruit because a bit can only be 0 or 1. To enumerate the fruit we will have to combine 2 bits together like this:

 

Apple = 00

Orange = 01

Banana = 10

Cherries = 11

 

The 2 bits together have 4 possible combinations so we can enumerate the fruits in our program using 2 bits for each piece of fruit.

 

What if our program needs to have 8 different kinds of fruit, how many bits do we need then?

 

The answer is 3 bits. 3 bits together have 8 value combinations

 

000

001

010

011

100

101

110

111 = 8 combinations.

 

The fomula for the number of combinations possible given N bits is:

 

combinations = 2 ^ N = (2 to the power of N)

 

So an enumeration of W items will require a minimum of:

 

N = log2 (W)

 

Exercises:

------------

Here are some real world examples of enumeration from Atari 2600 games. For each item calculate the minimum bits the program must use to keep track of the particular piece of information.

 

1. The catridge combat has 27 game variations, what is the minimum number of bits the combat program can use to keep track of the current variation?

 

2. The 112 game variations for Space Invaders.

 

3. The Atari 2600 Display is 160 pixels horizontally by 192 pixels vertically (NTSC) To position a player on the screen you must enumerate its horizontal and vertical position. How many bits are needed to store the horizontal and vertical positions of the player?

 

4. In Surround the "arena" is 40 blocks wide by 20 blocks high. Each block in the playfield is either filled or empty. How many bits are needed to remember the status of the playfield? How many bits are needed to remember the horizontal and vertical position of each player?

 

I will post the answers in 24 hours.

[EricBall]

Note: 3 & 4 have two answers depending on whether you are describing width & height independently or not. Bonus marks if you give both answers.

[Rob Mitchell]

1.  The catridge combat has 27 game variations, what is the minimum number of bits the combat program can use to keep track of the current variation?

 

2. The 112 game variations for Space Invaders.

 

1. Five bits.

 

2. Seven bits.

 

Rob Mitchell, Atlanta, GA

[Robert M]

1. The cartridge combat has 27 game variations, what is the minimum number of bits the combat program can use to keep track of the current variation?

 

ANSWER: 2^5 = 32 >= 27, so 5 bits are necessary.

 

 

2. The 112 game variations for Space Invaders.

 

ANSWER: 2^7 = 128 >= 112, so 7 bits are necessary.

 

3. The Atari 2600 Display is 160 pixels horizontally by 192 pixels vertically (NTSC) To position a player on the screen you must enumerate its horizontal and vertical position. How many bits are needed to store the horizontal and vertical positions of the player?

 

ANSWER: 2^8 = 256 >= 192 >= 160, so 8 bits are needed for each horizontal or vertical position. 16 bits total.

 

4. In Surround the "arena" is 40 blocks wide by 20 blocks high. Each block in the playfield is either filled or empty. How many bits are needed to remember the status of the playfield? How many bits are needed to remember the horizontal and vertical position of each player?

 

ANSWER: Since each block of the area has one of 2 states (filled or empty), we need a bit for each block.

 

Number of Blocks = 40 * 20 = 800 bits needed for the arena.

 

2^6 = 64 >= 40 so 6 bits are needed to store each player's horizontal position.

 

2^5 = 32 > = 20 so 5 bits are needed to store each player's vertical position.

 

Note: 3 & 4 have two answers depending on whether you are describing width & height independently or not.  Bonus marks if you give both answers.

 

This is true.

 

For problem 3 we could enumerate all the pixels on the screen (160 x 192 = 30720 possible positions)

 

2^15 = 32767 >= 30720, so you could store the player's position using 15 bits instead of 16 as required for storage of separate X and Y coordinates.

 

For problem 4 we could do the same trick for storing the player positions

 

2^10 = 1024 >= 800, so you could store each player's position using 10 bits instead of the 11 needed to store X and Y positions separately.

 

You may be wondering why then would you not always use the method of storage that uses the fewest bits? The answer is that the code of the program must process the data in the format that you choose, and it is easier to write code for separate X and Y coordinates than it is to write code for single enumerated position. In assembly language programming you will find there are many tricks that can be performed by using exotic data formats. I will provide examples much later in the course.

 

Now it is time to move on to Lesson 3 - Codes

[EricBall]

Just to elaborate on the reasons why more bits than necessary may be used:

 

[*]If the two values are independent (e.g. X & Y positions), so they are typically updated or used/tested separately

[*]Standard word lengths are easier to manipulate (e.g. 1 byte = 8 bits)

[*]Combining/extracting multiple variables requires multiplication/division, which is typically not efficient (e.g. position = Y * 160 + X, or X = position MOD 160)

[*]Room for expansion/enhancement

[Robert M]

Just to elaborate on the reasons why more bits than necessary may be used:

(snip)

 

Well said, thanks!