Assembly Language Programming - Lesson 6 - Binary Logic

[Robert M]

Lesson 6 - Binary Logic

======================



I know I promised to start discussing State Machines in Lesson 6, but now I see that I forgot to talk about binary logical functions.  Since I just covered binary counting, and binary math; I think it would be best to push State Machines off to lesson 7 and cover binary logic now.  



Introduction:

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



What is logic?   I could spend days on that topic, so I need to focus on logic as it applied to programming computers.  Recall our discussion of bits in Lesson 2.  Each bit has one of two possible values 0 or 1.   As the programmer you can apply any meaning you wish to each bit your program uses.   A common use for bits is to indicate  TRUE or FALSE.   TRUE is usually represented by 1, and FALSE is represented by 0.  Such an arrangement is called positive logic.   You can also use negative logic, where TRUE is 0 and FALSE is 1.  For this lesson I will confine the discussion to positive logic for all of the examples, since the instructions in the 650X microprocessors use positive logic.



For this class we are interested in logic functions that we can perform between pairs of bits representing TRUE and FALSE.  Some interesting things can be done with bits using just a few simple logical rules. 



Logic Functions:

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

There are four basic logical functions: AND, OR, XOR, NOT.   You can also combine NOT with the other 3 to form 3 more functions: NAND, NOR, and XNOR.   I will discuss each logical function in detail.  



*****************************

NOTE: For all the experienced programmers reviewing this material, I decided to exclude the logical bit-shift operations from this lesson.  I will cover bit-shifting and rotations when I cover those instructions.

*****************************



The best way to think about binary logical functions is as a special math operator akin to adding and subtracting as we covered in the previous lesson.   For all the logical operations, except NOT, there are 2 arguments and a single result.  So like addition we can write logical operations as A (oper) B = C, where (oper) is the symbol of the logical function to be performed on A and B resulting in C.  





Logical AND:

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

The first function I will present is AND.   The function AND is easy to understand.  Given A and B, C is TRUE only if A and B are TRUE.  Otherwise, C is FALSE.   We can present the AND function as a truth table:



A       B       | C

-----   -----	| -----

FALSE   FALSE   | FALSE

FALSE   TRUE    | FALSE 

TRUE    FALSE   | FALSE

TRUE    TRUE    | TRUE



As a programmer you will use AND to determine if multiple conditions are TRUE at the same time.  



For example:

A = TRUE if the player is carrying the Blue Key.

B = TRUE if the player is touching the Blue Door.

C = TRUE if the player has the Blue key and is touching the blue door.

If C is TRUE, then unlock the Blue Door and play sound effect.



***************** NOTE: ******************************

Above, is an example of what is called pseudocode.  Its a list of instructions similar  to what an actual program section will look like, but it is written in english rather than the programming language.  I will be using psuedocode more and more in these lessons, and you need to get comfortable both reading and writing pseudo code as part of this class.  Expect to see exercises where you will read and write pseudocode.

******************************************************



The symbol for AND is &.  So, C = A AND B = A & B is the same thing.





Logical OR:

-----------

The next logical function is OR.  Given A and B, C is TRUE if either A or B is TRUE, or both A and B are TRUE.   Logical OR in an 'inclusive-OR', not an 'exclusive-OR' as represented by the XOR function to be discussed next.  Here is the truth table for OR.



A       B       | C

-----   -----   | -----

FALSE   FALSE   | FALSE

FALSE   TRUE    | TRUE 

TRUE    FALSE   | TRUE

TRUE    TRUE    | TRUE



The shorthand symbol for OR is '|'.  So, C = A OR B = A | B, is equivalent.





Logical XOR:

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

XOR stands for exclusive OR.  C is TRUE if either A or B is TRUE, but it is FALSE if A and B are both TRUE or both FALSE.  Here is the truth table for XOR:



A       B       | C

-----   -----   | -----

FALSE   FALSE   | FALSE

FALSE   TRUE    | TRUE 

TRUE    FALSE   | TRUE

TRUE    TRUE    | FALSE



The shorthand symbol for XOR is '^'.  So, C = A XOR B = A ^ B is equivalent.



Logical NOT:

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

The function NOT is special in that it takes only 1 argument, not 2.  It is akin to using the negative sign in arithmetic to make a number negative.   C is the opposite state of the input A.  So C is FALSE if A is TRUE.  C is TRUE if A is FALSE.  Here is the truth table for NOT:



A       | C

-----   | -----

FALSE   | TRUE

TRUE    | FALSE



A common way to represent the function NOT is to place a bar over the input like this:

_

A = NOT A



Another way is to use a tilde like this:



~A = NOT A



The second method is easier to implement in the ASCII text of this lesson, but the first method is easier to read (I think).  I will try to use the bar notation in my lessons, but if it gets too annoying to type, I may start using the tilde. 





LOGICAL NAND, NOR, XNOR:

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

The functions NAND, NOR, and XNOR are the logical opposites of AND, OR, and XOR.  Its shorthand:



A NAND B = NOT (A AND B)

A NOR B  = NOT (A OR B)

A XNOR B = NOT (A XOR B)



Here are the truth tables for NAND, NOR, and XNOR:



NAND:

A       B       | C

-----   -----   | -----

FALSE   FALSE   | TRUE

FALSE   TRUE    | TRUE 

TRUE    FALSE   | TRUE

TRUE    TRUE    | FALSE



NOR:

A       B       | C

-----   -----   | -----

FALSE   FALSE   | TRUE

FALSE   TRUE    | FALSE 

TRUE    FALSE   | FALSE

TRUE    TRUE    | FALSE



XNOR:

A       B       | C

-----   -----   | -----

FALSE   FALSE   | TRUE

FALSE   TRUE    | FALSE 

TRUE    FALSE   | FALSE

TRUE    TRUE    | TRUE



For notation, I will simply use the NOT bar or tilda in combination with the exiting notation for AND, OR, or XOR.



                          _____

A NAND B = NOT (A AND B) = A & B = ~(A & B)

                        _____

A NOR B = NOT (A OR B) = A | B = ~(A | B)

                          _____

A XNOR B = NOT (A XOR B) = A ^ B = ~(A ^ B)



FROM BITS TO BYTES:

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

I described the functions above in terms of pairs of bits resulting in a single bit.  In programming 650X assembly language, you will perform these functions on pairs of bytes.  For each input byte you perform the logic function between the corresponding pairs of bits from each input byte, and place the result bit in the corresponding position in the result byte.  Look at the graphic examples below for a picture of the operation.





SOME PRACTICAL LOGIC:

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



As an assembly language programmer you will make frequent use of binary logic functions in your programs.  In this section I provide some practical examples for AND, OR, and XOR.  As a programmer you will often use individual bits within bytes to indicate whether conditions in your game environment are TRUE or FALSE, such bits are often refered to as flags.  You will often group flags together into bytes to save space in the limited memory of your computer.  You will use the AND, OR, XOR logical functions to clear, set, and toggle those flags as events happen in your game. 



------

AND - The function AND is often used in programs to reset one or more bits in a byte to zero, while leaving the other bits unchanged. 



Example:



Given: %11011010



Say you want to be sure that the MSB and LSB of the given byte are clear.  In this example the LSB is already clear, but you don't want to waste time in your code to figure out if the bits are set and then clear them.  With AND you can just clear them.

The first step is to create the necessary bit-mask.  The bit mask is a byte value that will preserve the bits you want unchanged and clear the bits you want cleared.  For each bit to be cleared, reset the bit in the bit mask to 0.  For each bit in the given byte to be unchanged, set the bit in the bit mask to 1.  So to clear the MSB and LSB, but preserve all other bits as is, the bit mask is:  %01111110



C = Given & bitmask = %11011010 & %01111110 = %01011010

                                              ^^^^^^^^

       %11011010                              ||||||||

     & %01111110                              ||||||||

     -----------                              ||||||||

        ||||||||                              ||||||||

        |||||||+--> 0 & 0 = 0 ----------------++++++++

        ||||||+---> 1 & 1 = 1 ----------------+++++++

        |||||+----> 0 & 1 = 0 ----------------++++++

        ||||+-----> 1 & 1 = 1 ----------------+++++

        |||+------> 1 & 1 = 1 ----------------++++

        ||+-------> 0 & 1 = 0 ----------------+++

        |+--------> 1 & 1 = 1 ----------------++

        +---------> 1 & 0 = 0 ----------------+



------

OR - The OR function is often used to set individual bits to 1 within a byte without changing the state of other bits in the byte.  As with using AND to clear bits in a byte, we don't care if the bits are already set will be set by OR'ing the byte with a corresponding bit mask.  Every bit we want set in the byte must be set in the bit mask.  Any bit clear in the bit mask will be unchanged after the OR.



Example:



Given: %11011010 - use OR to set the MSB and LSB.



bitmask = %10000001



C = Given | bitmask = %11011010 | %10000001 = %11011011

                                              ^^^^^^^^

       %11011010                              ||||||||

    or %01111110                              ||||||||

       ---------                              ||||||||

        ||||||||                              ||||||||

        |||||||+--> 0 | 1 = 1 ----------------++++++++

        ||||||+---> 1 | 0 = 1 ----------------+++++++

        |||||+----> 0 | 0 = 0 ----------------++++++

        ||||+-----> 1 | 0 = 1 ----------------+++++

        |||+------> 1 | 0 = 1 ----------------++++

        ||+-------> 0 | 0 = 0 ----------------+++

        |+--------> 1 | 0 = 1 ----------------++

        +---------> 1 | 1 = 1 ----------------+



------

XOR - The XOR function is often used in code to flip/toggle the state of specific bits in a byte without effecting other bits in the byte.   If the bit is 1 it is flipped to 0.  If the bit is 0 it is flipped/toggled to 1.   As with AND to clear bits, and OR to set bits, for XOR you must create a bitmask to indicate which bits are to be toggled and which are to be unchanged.  Each bit set in the bitmask will toggle the bit in the target byte.  Each bit in the bitmask reset to 0 will be unchanged in the target byte.



Example:

Given: %11011010 - use XOR to toggle the MSB and LSB.



bitmask = %10000001



C = Given ^ bitmask = %11011010 ^ %10000001 = %01011011

                                              ^^^^^^^^

       %11011010                              ||||||||

    or %01111110                              ||||||||

       ---------                              ||||||||

        ||||||||                              ||||||||

        |||||||+--> 0 ^ 1 = 1 ----------------++++++++

        ||||||+---> 1 ^ 0 = 1 ----------------+++++++

        |||||+----> 0 ^ 0 = 0 ----------------++++++

        ||||+-----> 1 ^ 0 = 1 ----------------+++++

        |||+------> 1 ^ 0 = 1 ----------------++++

        ||+-------> 0 ^ 0 = 0 ----------------+++

        |+--------> 1 ^ 0 = 1 ----------------++

        +---------> 1 ^ 1 = 0 ----------------+



-------



MORE LOGIC:



There is much more to binary logic, often called Boolean math after its inventor.  This lesson has covered enough for our needs, but there is plently more information and advanced techniques for simplifying complex logical equations, for example:

   ____________________

E = ((A & B) | (C ^ D ))  & A



We aren't interested in such complex logic in a beginners course, but feel free to explore the topic yourself if interested.  Search the internet for "Boolean Math".



===========

Excercises:



1. Given the following bytes (A) and bitmask (B) values calculate the result C, for C = A & B, C = A | B, and C = A ^ B



a. A = %11111111, B=%10101010

b. A = %00000000, B=%01010101

c. A = %11110000, B=%01110111





2.  Given the following bytes (A) and bitmask (B) values calculate the result C, for C = A NAND B, C = A NOR B, and C = A XNOR B



a. A = %10110110, B=%00000000

b. A = %11111111, B=%11111111





3. Fill in the blanks '_____' in this pseudocode example with what you believe is the correct logical function.



SUBROUTINE CheckPlayerStatus

BEGIN

IF (PLAYER.has_green_key = TRUE) ___ (Player.is_touching_door) THEN

 Goto PlayerExitsLevel

ELSE IF (Player.touching_monster = TRUE) ___ (Player.touching_arrow) THEN

 Goto PlayerKilled 

 ELSE IF (Player.touching_gold = TRUE) ___ (Monster.died) THEN

 Goto PlayerGetsPoints

ENDIF

END CheckPlayerStatus





4. BONUS PUZZLER!!!!



You are running low on available memory for your game.  You need to store 2 different counters of events occuring in your game.  The first counter counts up from 0 to 7, when the counter reaches 7 the next time it is added to it resets to zero. The second counter, will count down from 13 to 0, once the counter is at zero it stays at zero even if it is decremented again.  Devise a method for using binary addition and subtration in combination with AND, OR, or NOR logic functions to allow you to store both counters in a single byte.  You must be able to change either counter without affecting the other.  Write the pseudo code to change each counter without affecting the other.  Your solution must not share any bits between the two counters even though such a solution is technically possible, you do not have enough free clock cycles left in your program to use such a technique.

[Nukey Shay]

Is the 13 decimal ($13...%00010011 binary) or hex ($0d...%00001101 binary)?

[Robert M]

Is the 13 decimal ($13...%00010011 binary) or hex ($0d...%00001101 binary)?

 

Ah, good question.

 

13 decimal = %00010011 in BCD (binary coded decimal)

-AND-

13 decimal = %00001101 in binary number format

 

-OR-

 

13 decimal = $13 in Hexadecimal notation of 13 decimal inBCD number format.

-AND-

13 decimal = $0D in Hexadecimal notation of 13 decimal in binary number format

 

I haven't covered hexadecimal notation yet, so other readers should ignore the second half of this reply for now.

 

Did I answer your question?

[Nukey Shay]

Not really a question...just a clarification...

 

I haven't covered hexadecimal notation yet, so other readers should ignore the second half of this reply for now.

 

...and that clears it up

[Robert M]

Is the 13 decimal ($13...%00010011 binary) or hex ($0d...%00001101 binary)?

 

 

If you are asking if the 13 in the PUZZLER is decimal, then yes. I am avoiding teaching Hexadecimal until we start using DASM.

 

 

Please post your solution for the puzzler to the thread. It would be nice to see some different solutions presented. I find I learn this stuff the best by reading work from other people solving the same problem different ways.

 

Cheers!

[Nukey Shay]

Hm...why use logical operators at all?

 

Init $counter=$13 (bcd) or $0d (regular)



      clc

      lda $counter;load all bits

      adc #$20    ;bump up the primary counter (upper 3 bits)

      bcc L_end   ;if no rollover, skip

      beq L_end   ;if secondary counter (rest) already zero, skip

      sec         ;set the carry

      sed         ;set BCD mode

      sbc $01     ;subtract 1

      cld         ;and clear BCD mode

L_end: sta $counter;save for next time

 

Note: omit sed and cld if BCD not needed for secondary counter

[Nukey Shay]

BTW I didn't notice this at first...but EOR is generally the name of the Exclusive-Or function when referring to the 65xx instruction set (EOR/XOR...same thing). Old reference manuals and text won't have XOR listed.

 

Also, in the above routine...I suppose I could have done away with the SEC instruction and used SBC #$00 instead of SBC #$01 to shave off a couple cycles (the carry is already in place from the rollover)

[Thomas Jentzsch]

Also, in the above routine...I suppose I could have done away with the SEC instruction and used SBC #$00 instead of SBC #$01 to shave off a couple cycles (the carry is already in place from the rollover)

Without SEC yes, but it is still SBC #$01 then.

[Nukey Shay]

Really? I got it subtracting by 2 when I just took out the SEC

 

EDIT: yep, you're right...I dunno how I got that the first time

[EricBall]

For some reason (probably having to do with fewer transistors required), the "sense" of the carry bit is reversed for ADC and SBC.

 

So ADC with carry set adds one more, but SBC with carry clear subtracts one more.

 

The following instructions affect the carry bit:

ADC, SBC, CMP, CPX, CPY (compares set the flags just like SBC with carry set), ASL, LSR, ROL, and ROR.

 

The 6502 doesn't have a NOT instruction (or NEG), use EOR #$FF instead.

[Robert M]

Sorry, these lessons of mine sort of fell off a cliff. Is there any interest in me doing more?

 

Cheers!

[Rob Mitchell]

Sorry, these lessons of mine sort of fell off a cliff.  Is there any interest in me doing more?  

 

Yes .. please!

 

Rob Mitchell, Atlanta, GA

[Rob Mitchell]

The Bitmask used in OR and XOR in your original post is copied from the Bitmask of AND. Is this a mistake?

 

Rob Mitchell, Atlanta, GA

[Robert M]

The Bitmask used in OR and XOR in your original post is copied from the Bitmask of AND.  Is this a mistake?

 

Rob Mitchell, Atlanta, GA

 

Yes, you are correct. That is a copy and paste error. Sorry about that.

[Rob Mitchell]

Yes,  you are correct.   That is a copy and paste error.   Sorry about that.

 

Well at least you know that I am paying attention 11 months late!

 

Rob Mitchell, Atlanta, GA

[vdub_bobby]

Sorry, these lessons of mine sort of fell off a cliff.  Is there any interest in me doing more?  

 

Cheers!

I'm interested as well

[kamakazi]

Please keep this tutorial alive. I'm a slow leaner but am finding this information of great value. I know I'm years late but I'm enjoying learning Assembly.

[+Random Terrain]

Were answers posted in this thread? If so, I haven't been able to find them.

 

 

Thanks.