CSC218 Sequential Programming note.pdf

INTRODUCTION TO MIPS ASSEMBLY LANGUAGE PROGRAMMING 14 What you will learn In this chapter you will learn: 1. binary numbers, and how they relate to computer hardware. 2. to convert to/from binary, decimal, and hexadecimal 3. binary char...

INTRODUCTION TO MIPS ASSEMBLY LANGUAGE PROGRAMMING 14 What you will learn In this chapter you will learn: 1. binary numbers, and how they relate to computer hardware. 2. to convert to/from binary, decimal, and hexadecimal 3. binary character data representation in ASCII 4. integer numbers, which are represented in binary 2's complement format. 5. arithmetic operations for binary numbers 6. binary logic operations 7. the effect of context on data values in a computer. Chapter 1 Introduction One of the major goals of computer science is to use abstraction to insulate the users from how the computer works. For instance, computers can interpret speech and use natural language processing to allow novice users to perform some pretty amazing tasks. Even programming languages are written to enhance the ability of the person writing the code to create and support the program, and a goal of most modern languages is to be hardware agnostic. Abstraction is a very positive goal, but at some level a computer is just a machine. While High Level Languages (HLL) abstract and hide the underlying hardware, they must be translated into assembly language to use the hardware. One of the goals of a computer science education is to strip away these abstraction and make the workings of the computing machine clear. Without an understanding of a computer as a machine, even the best programmer, system administrator, support staff, etc., will have significant gaps in what they are able to accomplish. A basic understanding of hardware is important to any computer professional. Learning assembly language is different than learning a HLL. Assembly language is intended to directly manipulate the hardware that a program is run on. It does not rely on the ability to abstract behavior, instead giving the ability to specify exactly how the hardware is to work to the programmer. Therefore it uses a very different vocabulary than a HLL. That vocabulary is not composed of statements, variables and numbers but of operations, instructions, addresses, and bits. In assembly it is important to remember that the actual hardware to be used only understands binary values 0 and 1. To begin studying assembly, the reader must understand the basics of binary and how it is used in assembly language programming. The chapter is written to help the reader with the concepts of binary numbers. Chapter 1. 1 Binary Numbers Chapter 1.1. 1 Values for Binary Numbers Many students will have had a class covering logic or Boolean algebra, where the binary values are generally true(T) and false(F), and use special symbols such as "^" for AND and "˅" for OR. This 15 INTRODUCTION TO MIPS ASSEMBLY LANGUAGE PROGRAMMING might be fine for mathematics and logic, but is hopelessly inadequate for the engineering task of creating computer machines and languages. To begin, the physical implementation of a binary value in a Central Processing Unit's (CPU) hardware, called a bit, is implemented as a circuit called a flip-flop or latch. A flip-flop has a voltage of either 0 volts or a positive voltage (most computers use +5 volts, but many modern computers use +3.3 volts, and any positive voltage is valid). If a flip-flop has a positive voltage it is called high or on (true), and if it has 0 volts it is low or off (false). In addition hardware is made up of gates that which can either be open (true) or closed (false). Finally the goal of a computer is to be able to work with data that a person can understand. These numbers are always large, and hard to represent as a series of true or false values. When the values become large, people work best with numbers, so the binary number 0 is called false, and 1 is called true. Thus while computers work with binary, there are a number of ways we can talk about that binary. If the discussion is about memory, the value is high, on, or 1. When the purpose is to describe a gate, it is open/closed. If there is a logical operations values can be true/false. The following table summarizes the binary value naming conventions. T/F Number Switch Voltage Gate F 0 Off Low Closed T 1 On High Open Table 1-1: Various names for binary values In addition to the various names, engineers are more comfortable with real operators. This book will follow the convention that "+" is an OR operator, "*" is an AND operator, and "!" (pronounced bang) is a not operator. Some students are uncomfortable with the ambiguity in the names for true and false. They often feel that the way the binary values were presented in their mathematics classes (as true/false) is the "correct" way to represent them. But keep in mind that this class is about implementing a computer in hardware. There is no correct, or even more correct, way to discuss binary values. How they will be referred to will depend on the way in which the value is being used. Understanding a computer requires the individual to be adaptable to all of these ways of referring to binary values. They will all be used in this text, though most of the time the binary values of 0 and 1 will be used. Chapter 1.1. 2 Binary Whole Numbers The numbering system that everyone learns in school is called decimal or base 10. This numbering system is called decimal because it has 10 digits, [0..9]. Thus quantities up to 9 can be easily referenced in this system by a single number. Computers use switches that can be either on (1) or off(0), and so computers use the binary, or base 2, numbering system. In binary, there are only two digits, 0 and 1. So values up to 1 can be easily represented by a single digit. Having only the ability to represent 0 or 1 items is too limiting to be useful. But then so are the 10 values which can be used in the decimal system. The question is how does the decimal handle the problem of numbers greater than 9, and can binary use the same idea? In decimal when 1 is added to 9 the number 10 is created. The number 10 means that there is 1 group of ten numbers, and 0 one number. The number 11 is 1 group of 10 and 1 group of one.  INTRODUCTION TO MIPS ASSEMBLY LANGUAGE PROGRAMMING 16 When 99 is reached, we have 100, which is 1 group of hundred, 0 tens, and 0 ones. So the number 1,245 would be: 1,245 = 1*103 + 2*102 + 4*101+ 5*100 Base 2 can be handled in the same manner. The number 102 (base 2) is 1 group of two and 0 ones, or just 210 (base 10).1 Counting in base 2 is the same. To count in base 2, the numbers are 02, 12, 102, 112, 1002, 1012, 1102 1112, etc. Any number in base 2 can be converted to base 10 using this principal. Consider 1010112, which is: 1*25 + 0*24 + 1*23 + 0 *22 + 1*21 + 1*20 = 32 + 8 + 2 + 1 = 4310 In order to work with base 2 number, it is necessary to know the value of the powers of 2. The following table gives the powers of 2 for the first 16 numbers (to 215). It is highly recommended that students memorize at least the first 11 values of this table (to 210), as these will be used frequently. n 2n n 2n n 2n n 2n 0 1 4 16 8 256 12 4096 1 2 5 32 9 512 13 8192 2 4 6 64 10 1024 14 16348 3 8 7 126 11 2048 15 32768 Table 1-2: Values of 2n for n = 0...15 The first 11 powers of 2 are the most important because the values of 2n are named when n is a decimal number evenly dividable by 10. For example 210 is 1 Kilo, 220 is 1 Meg, etc. The names for these value of 2n are given in the following table. Using these names and the values of 2n from 0-9, it is possible to name all of the binary numbers easily as illustrated below. To find the value of 216, we would write: 216 = 210*26= 1K * 64 = 64K Older programmers will recognize this as the limit to the segment size on older PC's which could only address 16 bits. Younger students will recognize the value of 232, which is: 232 = 230 * 22 = 1G * 4 = 4G 4M was the limit of memory available on more recent PC's with 32 bit addressing, though that limit has been moved with the advent of 64 bit computers. The names for the various values of 2n are given in the following table. 210 Kilo 230 Giga 250 Penta 220 Mega 240 Tera 260 Exa 1 The old joke is that there are 10 types of people in the world, those who know binary and those who do not.  17 INTRODUCTION TO MIPS ASSEMBLY LANGUAGE PROGRAMMING Table 1-3: Names for values of 2n, n = 10, 20, 30, 40, 50, 60 Chapter 1. 2 Converting Binary, Decimal, and Hex Numbers Chapter 1.2. 1 Converting Binary to Decimal Computers think in 0's and 1's, and when dealing with the internal workings of a computer humans must adjust to the computer’s mindset. However, when the computer produces answers, the humans that use them like to think in decimal. So it is often necessary for programmers to be able to convert between what the computer wants to see (binary), and what the human end users want to see (decimal). These next 3 sections will deal with how to convert binary to decimal, and then give 2 ways to convert decimal to binary. Finally, it will give a section on a useful representation for handling large binary numbers called hexadecimal. To convert binary to decimal, it is only necessary to remember that each 0 or 1 in a binary number represents the amount of that binary power of 2. For each binary power of 2, you have either 0 or 1 instance of that number. To see this, consider the binary number 10010102. This number has 1 * 26 + 0 * 25 + 0 * 24 + 1 * 23 + 0 * 22 + 1 * 21 + 0 * 20 = 64 + 8 + 2 = 7410. This can be generalized into an easy way to do this conversion. To convert from binary to decimal put the 2n value of each bit over the bits in the binary number and add the values which are 1, as in the example below: 64 32 16 8 4 2 1 10010102 = 1 0 0 1 0 1 0 = 64 + 8 + 2 = 7410 Chapter 1.2. 2 Converting Decimal to Binary using Binary Powers Two ways to convert decimal number to binary numbers are presented here. The first is easy to explain, but harder to implement. The second is a cleaner algorithm, but why the algorithm works is less intuitive. The first way to convert a number from decimal to binary is to see if a power of 2 is present in the number. For example, consider the number 433. We know that there is no 2 9 (512) value in 433, but there is one value of 28 (or 256). So in the 9th digit of the base 2 number we would put a 1, and subtract that 256 from the value of 433. 433 - 256 = 177 28 27 26 25 24 23 22 21 20 1 - - - - - - - - Next check if there is a 27 (128) value in the number. There is, so add that bit to our string and subtract 128 from the result.  INTRODUCTION TO MIPS ASSEMBLY LANGUAGE PROGRAMMING 18 177 - 128 = 49 28 27 26 25 24 23 22 21 20 1 1 - - - - - - - Now check for values of 26 (64). Since 64 > 49, put a zero in the 26 position and continue. 49 - 0 = 49 28 27 26 25 24 23 22 21 20 1 1 0 - - - - - - Continuing this process for 25 (32), 24(16), 23(8), 22(4), 21(2), and 20(1) results in the final answer. 28 27 26 25 24 23 22 21 20 1 1 0 1 1 0 0 0 1 Thus 43310 = 1101100012. This result can be checked by converting the base 2 number back to base 10. Chapter 1.2. 3 Converting Decimal to Binary using Division While conceptually easy to understand, the method to convert decimal numbers to binary numbers in Chapter 1.2.3 is not easy to implement as the starting and stopping conditions are hard to define. There is a way to implement the conversion which results in a nicer algorithm. The second way to convert a decimal number to binary is to do successive divisions by the number 2. This is because if a number is divided and the remainder taken, the remainder is the value of the 20 bit. Likewise if the result of step 1 is divided again by 2 (so essentially dividing by 2*2 or 4), the reminder is the value of the 21 bit. This process is continued until the result of the division is 0. The example below shows how this works. Start with the number 433. 433 divided by 2 is 216 with a remainder of 1. So in step 1 the result would have the first bit for the power of 2 set to one, as below: 433 / 2 = 216 r 1 28 27 26 25 24 23 22 21 20 - - - - - - - - 1 19 INTRODUCTION TO MIPS ASSEMBLY LANGUAGE PROGRAMMING The number 216 is now divided by 2 to give 108, and the remainder, zero, placed in the second bit. 216 / 2 = 108 r 0 28 27 26 25 24 23 22 21 20 - - - - - - - 0 1 The process continues to divide by 2, filling the remainder in each appropriate bit, until at last the result is 0, as below. 28 27 26 25 24 23 22 21 20 1 1 0 1 1 0 0 0 1 Chapter 1.2. 4 Converting between binary and hexadecimal One of the biggest problems with binary is that the numbers rapidly become very hard to read. This is also true in decimal, where there is often a "," inserted between groupings of 103. So for example 1632134 is often written as 1,632,134, which is easier to read. In binary, something similar is done. Most students are familiar with the term byte, which is 8 bits. But fewer know of a nybble, or 4 bits. 4 bits in binary can represent numbers between 0..15, or 16 values. So values of 4 bits are collected together and create a base 16 number, called a hexadecimal (or simply hex) number. To do this, 16 digits are needed, and arbitrarily the numbers and letters 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F were chosen as the 16 digits. The binary numbers corresponding to these 16 digit hex numbers are given in the table below (note, the normal way to indicate a value is in hex is to write a 0x before it So decimal 10 would be 0xA). Binary Hex Binary Hex Binary Hex Binary Hex Number Digit Number Digit Number Digit Number Digit 0000 0x0 0001 0x 1 0010 0x 2 0011 0x 3 0100 0x 4 0101 0x 5 0110 0x 6 0111 0x 7 1000 0x 8 1001 0x 9 1010 0x A 1011 0x B 1100 0x C 1101 0x D 1110 0x E 1111 0x F Table 1-4: Binary to Hexadecimal Conversion  INTRODUCTION TO MIPS ASSEMBLY LANGUAGE PROGRAMMING 20 The hex numbers can then be arranged in groups of 4 (or 32 bits) to make it easier to translate from a 32 bit computer. Note that hex numbers are normally only used to represent groupings of 4 binary digits. Regardless of what the underlying binary values represent, hex will be used just to show what the binary digits are. So in this text all hex values will be unsigned whole numbers. Most students recognize that a decimal number can be extended by adding a 0 to the left of a decimal number, which does not in any way change that number. For example 0043310 = 043310 = 43310. The same rule applies to binary. So the binary number 1101100012 = 0001101100012. But why would anyone want to add extra zeros to the left of a number? Because to print out the hex representation of a binary number, I need 4 binary digits to do it. The binary number 1101100012 only has 1 binary digit in the high order byte. So to convert this number to binary it is necessary to pad it with left zeros, which have no effect on the number. Thus 1 10011 00012 = 0001 1011 00012= 0x1B1 in hex. Note that even the hex numbers are often paded with zeros, as the hex number 0x1B1 is normally be written 0x01B1, to get groupings of 4 hex numbers (or 32 bits). It is often the case where specific bits of a 32 bit number need to be set. This is most easily done using a hex number. For instance, if a number is required where all of the bits except the right left most (or 1) bit of a number is set, you can write the number in binary as: 111111111111111111111111111111102 A second option is to write the decimal value as: 429496729510 Finally the hex value can be written as 0xFFFFFFFE In almost all cases where specific bits are being set, a hex representation of the number is the easiest to understand and use. Chapter 1. 3 Character Representation All of the numbers used so far in this text have been binary whole numbers. While everything in a computer is binary, and can be represented as a binary value, binary whole numbers do not represent the universe of numbering systems that exists in computers. Two representations that will be covered in the next two sections are character data and integer data. Though computers deal use binary to represent data, humans usually deal with information as symbolic alphabetic and numeric data. So to allow computers to handle user readable alpha/numeric data, a system to encode characters as binary numbers was created. That system is called American Standard Code for Information Interchange (ASCII)2. In ASCII all character are represented by a number from 1 - 127, stored in 8 bits. The ASCII encodings are shown in the following table. 2 ASCII is limited to just 127 characters, and is thus too limited for many applications that deal with internationalization using multiple languages and alphabets. Representations, such as Unicode, have been developed to handle these character sets, but are complex and not needed to understand MIPS Assembly. So this text will limit all character representations to ASCII.  21 INTRODUCTION TO MIPS ASSEMBLY LANGUAGE PROGRAMMING Table 1-5: ASCII Table Using this table, it is possible to encode a string such as "Once" in ASCII characters as the hexadecimal number 0x4F6E63653 (capital O = 0x4F, n = 0x6E, c = 0x53, e = 0x65 ). Numbers as character data are also represented in ASCII. Note the number 13 is 0xD or 11012. However the value of the character string "13" is 0x3133. When dealing with data, it is important to remember what the data represents. Character numbers are represented using binary values, but are very different from their binary numbers. Finally, some of the interesting patterns in ASCII should be noted. All digits start with binary digits 0011 0000. Thus 0 is 0x0011 0000, 1 is 00011 0000, etc. To convert a numeric character digit to a number it is only necessary to subtract the character value of 0. For example, '0' - '0' = 0, '1' - '0' = 1, etc. This is the basis for an easy algorithm to convert numeric strings to numbers which will be discussed in the problems. Also note that all ASCII upper case letters start with the binary string 0010 0000, and are 1 offset for each new character. So A is 0100 0001, B is 0100 0010, etc. Lower case letters start with the binary string 0110 and are offset by 1 for each new character, so a is 0110 0001, b is 0110 0010, 3 By now it is hoped that the reader is convinced that hexadecimal is a generally preferred way to represent data in a computer. The decimal value for this string would be 1,332,634,469 and the binary would be 0100 1111 0110 1110 0110 0011 0010 0101. Having taught for many year, however, I know old habits die hard with many students who will struggle endlessly converting to decimal to avoid learning hex.  INTRODUCTION TO MIPS ASSEMBLY LANGUAGE PROGRAMMING 22 etc. Therefore, all upper case letters differ from their lower case counterpart by a 1 in the digit 0100. This relationship between lower case and capital letters will be use to illustrate logical operations later in this chapter. Chapter 1. 4 Adding Binary Whole Numbers Before moving on to how integer values are stored and used in a computer for calculations, how to do addition of binary whole numbers needs to be covered. When 2 one-bit binary numbers are added, the following results are possible: 02+02 = 02; 02+12 = 12; 12+02 = 12; and 12+12 = 102. This is just like decimal numbers. For example, 3+4=7, and the result is still one digit. A problem occurs, however, when adding two decimal numbers where the result is greater than the base of the number (for decimal, the base is 10). For example, 9+8. The result cannot be represented in one digit, so a carry digit is created. The result of 9+8 is 7 with a carry of 1. The carry of 1 is considered in the next digit, which is actually adding 3 digits (the two addends, and the carry). So 39 + 28 = 67, where the 10's digit (4) is the result of the two addends (3 and 2) and the carry (1). The result of 12+12 = 102 in binary is analogous to the situation in base 10. The addition of 12+12 is 02 with a carry of 12, and there is a carry to the next digit of 12. An illustration of binary addition is shown in the figure below. Figure 1-1: Binary whole number addition Here the first bit adds 12 +12, which yields a 02 in this bit and a carry bit of 12. The next bit now has to add 12 +12 +12 (the extra one is the carry bit), which yields a 12 for this bit and a carry bit of 12. If you follow the arithmetic through, you have 00112 (310) + 01112 (710) = 10102 (1010). Chapter 1. 5 Integer Numbers (2's Complement) Chapter 1.5. 1 What is an Integer Using only positive whole numbers is too limiting for any valid calculation, and so the concept of a binary negative number is needed. When negative values for the set of whole numbers are included with the set of whole number (which are positive), the resulting set is called integer numbers. Integers are non-fractional numbers which have positive and negative values. 23 INTRODUCTION TO MIPS ASSEMBLY LANGUAGE PROGRAMMING When learning mathematics, negative numbers are represented using a sign magnitude format, where a number has a sign (positive or negative), and a magnitude (or value). For example -3 is 3 units (it's magnitude) away from zero in the negative direction (it's sign). Likewise, +5 is 5 units away from zero in a positive direction. Signed magnitude numbers are used in computers, but not for integer values. For now, just realize that it is excessively complex to do arithmetic using signed magnitude numbers. There is a much simpler way to do things called 2's complement. This text will use the term integer and 2's complement number interchangeably. Chapter 1.5. 2 2's complement operation and 2's complement format Many students get confused and somehow believe that a 2's complement has something to do with negative numbers, so this section will try to be as explicit here as possible. Realize that if someone asks, "What is a 2's complement?", they are actually asking two very different questions. There is a 2's complement operation which can be used to negate a number (e.g. translate 2 -> -2 or -5 -> 5). There is also a 2's complement representation (or format) of numbers which can be used to represent integers, and those integers can be positive and negative whole numbers. To reiterate, the 2's complement operation can convert negative numbers to the corresponding positive values, or positive numbers to the corresponding negative values. The 2's complement operation negates the existing number, making positive numbers negative and negative numbers positive. A 2's complement representation (or format) simply represents number, either positive or negative. If you are ever asked if a 2's complement number is positive or negative, the only appropriate answer is yes, a 2's complement number can be positive or negative. The following sections will explain how to do a 2's complement operation, and how to use 2's complement numbers. Being careful to understand the difference between a 2's complement operation and 2's complement number will be a big help to the reader. Chapter 1.5. 3 The 2's Complement Operation A 2's complement operation is simply a way to calculate the negation of a 2's complement number. It is important to realize that creating a 2's complement operation (or negation) is not as simple as putting a minus sign in front of the number. A 2's complement operation requires two steps: 1 - Inverting all of the bits in the number; and 2 - Adding 12 to the number. Consider the number 001011002. The first step is to reverse all of the bits in the number (which will be achieved with a bit-wise ! operation. Note that the ! operator is a unary operation, it only takes one argument, not two. ! (001011002) = 110100112 Note that in the equation above the bits in the number have simply been reversed, with 0's becoming 1's, and 1's becoming 0's. This is also called a 1's complement, though in this text we will never use a 1's complement number. The second step adds a 12 to the number.  INTRODUCTION TO MIPS ASSEMBLY LANGUAGE PROGRAMMING 24 110100112 000000012 110101002. Thus the result of a 2's complement operation on 001011002 is 110101002 , or negative 2's complement value. This process is reversible, as the reader can easily show that the 2's complement value of 110101002 is 001011002. Also note that both the negative and positive values are in 2's complement representation. While positive numbers will begin with a 0 in the left most position, and negative numbers will begin with a 1 in the leftmost position, these are not just sign bits in the same sense as the signed magnitude number, but part of the representation of the number. To understand this difference, consider the case where the positive and negative numbers used above are to be represented in 16 bits, not 8 bits. The first number, which is positive, will extend the sign of the number, which is 0. As we all know, adding 0's to the left of a positive number does not change the number. So 001011002 would become 00000000001011002. However, the negative value cannot extend 0 to the left. If for no other reason, this results in a 0 in the sign bit, and the negative number has been made positive. So to extend the negative number 110101002 to 16 bits requires that the sign bit, in this case 1, be extended. Thus 110101002 becomes 11111111110101002. The left most (or high) bit in the number is normally referred to as a sign bit, a convention this text will continue. But it is important to remember it is not a single bit that determines the sign of the number, but a part of the 2's complement representation. Chapter 1.5. 4 The 2's Complement (or Integer) Type Because the 2's complement operation negates a number, many people believe that a 2's complement number is negative. A better way to think about a 2's complement number is that is a type. A type is an abstraction which has a range of values, and a set of operations. For a 2's complement type, the range of values is all positive and negative whole numbers. For operations, it has the normal arithmetic operations such as addition (+), subtraction (-), multiplication (*) , and division (/). A type also needs an internal representation. In mathematics classes, numbers were always abstract, theoretical entities, and assumed to be infinite. But a computer is not an abstract entity, it is a physical implementation of a computing machine. Therefore, all numbers in a computer must have a physical size for their internal representation. For integers, this size is often 8 (byte), 16(short), 32(integer), or 64(long) bits, though larger numbers of bits can be used to store the numbers. Because the left most bit must be a 0 for positive, and 1 for negative, using a fixed size also helps to identify easily if the number is positive or negative. Because the range of the integer values is constrained to the 2n values (where n is the size of the integer) that can be represented with 2's complement, about half of which are positive and half are negative, roughly 2n-1 values of magnitude are possible. However, one value, zero, must be accounted for, so there are 1 less positive numbers than negative numbers. So while 28 is 256, the 2's complement value of an 8-bit number runs from -128... 127. 25 INTRODUCTION TO MIPS ASSEMBLY LANGUAGE PROGRAMMING Finally, as stated in the previous section, just like zeros can be added to the left of a positive number without effecting its value, in 2's complement ones can be added to the left of a negative number without effecting its value. For example: 00102 = 0000 00102 = 210 11102 = 1111 1110 2= -210 Adding leading zeros to a positive number, and leading ones to a negative number, is called sign extension of a 2's complement number. Chapter 1. 6 Integer Arithmetic Chapter 1.6. 1 Integer Addition Binary whole number addition was covered in chapter 1.4. Integer addition is similar to binary whole number addition except that both positive and negative numbers must be considered. For example, consider adding the two positive numbers 00102 (210) + 00112 (310) = 01012 (510). Figure 1-2: Addition of two positive integers Addition of mixed positive and negative numbers, and two negative numbers also works in the same manner, as the following two examples show. The first adds 00102 (210) + 11012 (-310) = 11112 (-110), and the second adds 11102 (-210) + 11012 (-310) = 10112 (-510). Figure 1-3: Addition of positive and negative integers  INTRODUCTION TO MIPS ASSEMBLY LANGUAGE PROGRAMMING 26 Figure 1-4: Addition of two negative integers Because integers have fixed sizes, addition and subtraction can cause a problem known as integer overflow. This happens which the two numbers which are being added are large positive or negative values, and the combining of the values results in numbers too big to be store in the integer. Chapter 1.6. 2 Overflow of Integer Addition Because integers have fixed sizes, addition and subtraction can cause a problem known as integer overflow. This happens which the two numbers which are being added are large positive or negative values, and the combining of the values results in numbers too big to be store in the integer value. For example, a 4 bit integer can store values from -8...7. So when 01002 (410) + 01012 (5) = 10012 (-7) are added using 4 bit integers the result is too large to store in the integer. When this happens, the number changes sign and gives the wrong answer, as the following figure shows. Figure 1-5: Addition with overflow Attempting to algorithmically figure out if overflow occur is difficult. First if one number is positive and the other is negative, overflow never occurs. If both numbers are positive or negative, then if the sign of the sum is different than the sign of either of the inputs overflow has occurred. 27 INTRODUCTION TO MIPS ASSEMBLY LANGUAGE PROGRAMMING There is a much easier way to figure out if overflow has occurred. If the carry in bit to the last digit is the same as the carry out bit, then no overflow has occurred. If they are different, then overflow has occurred. In figure 1.3 the carry in and carry out for the last bit are both 0, so there is no overflow. Likewise, in figure 1.4 the carry in and carry out are both 1, so there was no overflow. In figure 1.5 the carry in is 1 and the carry out is 0, so overflow has occurred. This method also works for addition of negative numbers. Consider adding 11002 (-410) and 10112 (-510) = 01112 (710), shown in figure 1.6. Here the carry in is 0 and the carry out is 1, so once again overflow has occurred. Figure 1-6: Subtraction with overflow Chapter 1.6. 3 Integer multiplication using bit shift operations Multiplication and division of data values or variables involves hardware components in the Arithmetic Logic Unit (ALU). In assembly these operations will be provided by the various forms mul and div operators, and the hardware to implement them is beyond the scope of this book and will not be covered. However, what is of interest in writing assembly is multiplication and division by a constant. The reason multiplication and division by a constant is covered is that these operations can be provided by bit shift operations, and the bit shift operations are often faster to run than the equivalent mul or div operation. Therefore, bit shift operations are often used in assembly to do multiplication and division, and therefore it is important for assembly language programmers to understand how this works. First consider multiplication of a number by a power of 10 in base 10. In base 10, if a number is multiplied by a power of 10 (10n, where n is the power of 10), it is sufficient to move the number n places to the right filling in with 0's. For example, 15*1000 (or 15 * 103) = 15,000. This same concept holds in binary. To multiply a binary number (e.g. 15, or 000011112) by 2, the number is shifted to the left 1 digit (written as 1111DIVU.W D2,D1 PC=OO0420 SR=2000 SS=00A00000 US=00000000 X=0 A 0 = 0 0 0 0 0 0 0 0 A 1 = 0 0 0 0 0 0 0 0 A2=00000000 A3=00000000 N=0 A 4 = 0 0 0 0 0 0 0 0 A 5 = 0 0 0 0 0 0 0 0 A6=00000000 A7=OOA0OOO0 Z=0 D0=000009C4 D l = 0 0 1 6 0 0 4 5 D2=00000026 D3=00000000 V=0 D 4 = 0 0 0 0 0 0 0 0 D5=00000000 D6=00000000 D7=00000000 C=0 >MOVE.W Dl,$0504 The 68K instruction D I V U D2 , D l divides the 32-bit con- tents of data register D l by the lower-order 16 bits in data register D2. The result is a 16-bit quotient in the lower-order word of D l and a 16-bit remainder in the upper-order word of D l. That is, A54 1 6 /9C4 1 6 = 45 1 6 remainder 1616. The con- tents of D l are $00160045. PC=000426 SR=2000 SS=O0A0OOOO US=00000000 X=0 A 0 = 0 0 0 0 0 0 0 0 A 1 = 0 0 0 0 0 0 0 0 A2=00000000 A 3 = 0 0 0 0 0 0 0 0 N=0 A 4 = 0 0 0 0 0 0 0 0 A 5 = 0 0 0 0 0 0 0 0 A 6 = 0 0 0 0 0 0 0 0 A7=OOA0OO0O Z=0 D0=000009C4 D l = 0 0 1 6 0 0 4 5 D2=00000026 D3=00000000 V=0 D 4 = 0 0 0 0 0 0 0 0 D 5 = 0 0 0 0 0 0 0 0 D6=00000000 D7=00000000 C=0 >STOP #$2700 244 Chapter 6 Assembly language programming The MOVE, w Dl, $ 0 5 0 4 stores the low-order 16-bit result logical operation AND. B # % 0 0 0 0 0111, DO to get OOOOOyyy in Dl in memory location 504If) (i.e. Z). We've used a in DO. wordlength operation and have discarded the remainder in By using the NOT, AND, OR, and EOR instructions, you can the upper-order word of D1. Now we look at the contents of perform any logical operations on a word. Suppose you wish memory location 500 onward. to clear bits 0,1, and 2, set bits 3,4, and 5, and toggle bits 6 and 7 of the byte in DO. You could write 000500 00 32 00 0C 00 45 00 00 00 00 00 00 00 00 00 00. AND.B #%11111000,DO C l e a r b i t s 0, 1, and 2 As you can see, memory location 50416 now contains the OR.B #%00111000,DO S e t b i t s 3 , 4, and 5 EOR.B #%11000000,DO T o g g l e b i t s 6 and 7. integer result of (502 + 122)(50 - 12) = 45, 6 = 69. If [DO] initially contains 01010101, its final contents will be 10111000. We will look at a more practical application of 6.3.3 Using shift and logical operations bit manipulation after we have covered branch operations in We now demonstrate the use of shift and logical operations. a little more detail. Logical shifts enable you to extract specific bits in a word. Consider an 8-bit byte in DO with the format xxyyyzzz, where 6.3.4 Using conditional branches the xs, ys, and zs are three groups of bits that have been You can't write programs without using the conditional packed into a byte. Suppose we wish to extract the three ys branches required to implement loops and other control from this byte. constructs. We now look at the branch again and demonstrate LSR.B #3,DO Shift DO right 3 places to get OOOxxyyy in DO AND.B #%0000011l,D0 Clear bits 3 to 7 of DO to get OOOOOyyy The first instruction LSR. B #3 , DO shifts xxyyyzzz right its use. Consider the following example of an addition fol- to get OOOxxyyy in DO. We remove the xs by means of the lowed by a branch on negative (minus). SHIFT OPERATIONS— A REMINDER The assembly language forms of the 68K's shift instructions are LSL #n,D0 shi ft c o n t e n t s o f DO n p l a c e s left logically LSR #n,D0 s h Lft c o n t e n t s o f DO n p l a c e s right logically ASL #n,D0 sh-Lft c o n t e n t s o f DO n p l a c e s left arithmetically ASR #n,D0 s h Lft c o n t e n t s o f DO n p l a c e s right arithmetically The integer n indicates the number of places to be shifted. These instructions can be applied to bytes, words, and long- words. If you shift a word by more than one place, the end value of the carry bit is determined by the final shift. Consider the following examples: Initial contents of DO Operation Final contents of DO 11001100 LSL.B #1,D0 10011000 11001100 LSR.B #1,D0 01100110 11001100 ASL.B #1,D0 10011000 11001100 ASR.B #1,D0 11100110 1010111100001100 ASR.W #3,DO 1111010111100001 0011100001111101 ASR.W #4,DO 0000001110000111 11001110 ROL.B #1,D0 10011101 11001110 ROR.B #l,DO 01100111 11110000 ROL.B #2,DO 11000011  6.3 Features of the 68K's instruction set 245 SUB D1,D2 Subtract Dl from D2 and branch IF the result in negative BMI ERROR ELSE p a r t Beware Here be bugs THIS C O D E IS W R O N G ! ! ! ERROR THEN p a r t The operation SUB Dl, D2 subtracts the contents of Dl EXIT and skips past the ' ERROR ' clause. Figure 6.10 demon- from D2, deposits the results in D2, and updates the condi- strates the flow of control for this program. tion code register accordingly. Remember we said earlier that not all the 68K's instruc- When the BMI instruction is executed, the branch is taken tions affect die CCR. For example, consider the following two (the THEN part) if the N-bit of the CCR is set because the examples. addition gave a negative result. The branch target is the line labeled by ERROR ADD D 1 , D 2 Add the contents of Dl to the contents of D2 and the intervening code between BMI BMI ERROR If the result is negative, branch to ERROR ERROR and ERROR... is not executed. and If the branch is not taken because the ADD D 1 , D 2 Add t h e c o n t e n t s of Dl t o t h e c o n t e n t s of D2 result of SUB Dl, D2 was positive, the EXG D 3 , A4 Exchange t h e c o n t e n t s of D3 and A4 code immediately following the BMI EXG D 5 , A 6 Exchange the c o n t e n t s of D5 and A6 ERROR is executed. This code corresponds BMI ERROR If t h e r e s u l t of t h e a d d i t i o n was n e g a t i v e , to the ELSE part of the I F THEN ELSE b r a n c h t o ERROR construction. Both these fragments of code have the same effect as far as Unfortunately, there's an error in this example. Suppose the BMI ERROR is concerned. However, the second case might that the subtraction yields a positive result and the ELSE part prove confusing to the reader of the program who may well is executed. Once the ELSE code has been executed, we fall imagine that the state of the CCR prior to the BMI ERROR is through to the THEN part and execute that too, which is not determined by the EXG D3 , DA instruction. what we want to do. After the ELSE part has been executed, it's necessary to skip round the THEN part by means of an BRA Example 1 Suppose you want to write a subroutine to con- instruction. The unconditional branch instruction, BRA vert a 4-bit hexadecimal value into its ASCII equivalent. EXIT forces the computer to execute the next instruction at ASCII character He) Hexadecimal value Binary value SUB D1,D2 0 30 0000 BMI ERROR 1 31 0001 ) ELSE part 2 32 0010 ) BRA EXIT Skip past the THEN part 3 33 0011 ERROR ) 4 34 0100 ) THEN part 35 0101 5 ) 6 36 0110 EXIT 7 37 0111 Start 8 38 1000 39 1001 1 9 1010 A 41 true / x^ false B 42 1011 C 43 1100 [. X ^S^/' D 44 1101 THEN, ELSE E 45 1110 F 46 1111 T Table 6.1 Relationship between ISO/ASCII characters and hexa- Figure 6.10 Flow of control for an IF... THEN... ELSE construct. decimal values. 246 Chapter 6 Assembly language programming Table 6.1 illustrates the relationship between the binary The CMP s o u r c e , d e s t i n a t i o n subtracts the source value of a number (expressed in hexadecimal form) and its operand from the destination operand and sets the flag bits of ASCII equivalent (also expressed in hexadecimal form). For the CCR accordingly; that is, a CMP is the same as a SUB except example, if the internal binary value in a register is that the result is not recorded. 00001010, its hexadecimal equivalent is A16. In order to print the letter 'A' on a terminal, you have to transmit the Example 2 Consider the following algorithm. ASCII code for the letter 'A' (i.e. $41) to it. Once again, please note that there is a difference between the internal binary repre- * IF x = y THEN y = 6 sentation of a number within a com- * IF x < y THEN y = y + 1 puter and the code used represent the * symbol for that number. The number CMP.B D1,D0 Assume that x is in DO and y in :Dl six is expressed in 8 bits by the binary BNE NotEqu IF x = y THEN MOVE.B #6,D1 y = 6 pattern 00000110 and is stored in the BRA exit and leave the algorithm computer's memory in this form. On NotEqu BGE exit IF x < y THEN exit the other hand, the symbol for a six ADD.B #1,D1 ELSE y = y + 1 (i.e. '6') is represented by the binary exit exit point for the algorithm pattern 00110110 in the ASCII code. If we want a printer to make a mark on paper corresponding to '6', we must send the binary number 00110110 to We perform two tests after the comparison CMP.B DO, D l. it. Consequently, numbers held in the computer must One is a BNE and the other a BGE. We can carry out the two be converted to their ASCII forms before they can be tests in succession because there isn't an intervening instruc- printed. tion that modifies the state of the CCR. From Table 6.1 we can derive an algorithm to convert a Although conditional tests performed by high-level 4-bit internal value into its ASCII form. A hexadecimal value languages can be complex (e.g. IF x + Y - z > 3t), the condi- in the range 0 to 9 is converted into ASCII form by adding tional test at the assembly language level is rather more basic hexadecimal 30 to the number. A hexadecimal value in the as this example demonstrates. range $A to $F is converted to ASCII by adding hexadecimal $37. If we represent the number to be converted by HEX and the number to be converted by ASCII, we can write down a Templates for control structures suitable algorithm in the form We now represent some of the control structures of high-level languages as templates in assembly language. A IF HEX < 9 THEN ASCII HEX 30 1 6 template is a pattern or example that can be modified to suit ELSE ASCII HEX 37 1 6 the actual circumstances. In each of the following examples, the high-level construct is provided as a comment to the assembly language template by means of asterisks in the We can rewrite the algorithm as first column. The condition tested is [DO] = [Dl] and the actions to be carried out are A c t i o n l or A c t i o n 2. The ASCII = HEX + $30 templates can be used by providing the appropriate test IF ASCII > $39 THEN ASCII ASCII + 7 instead of CMP D0,D1 and providing the appropriate sequence of assembly language statements instead of This algorithm can be translated into low-level language as A c t i o n l or A c t i o n 2. Note: D0.B holds HEX value on subroutine entry D0.B holds the ASCII character code on return No other register is modified by this subroutine ADD.B #$30,DO ASCII = HEX + $30 CMP.B #$39,DO IF ASCII < $39 THEN EXIT BLE EXIT ADD.B #7, DO ELSE ASCII = ASCII + 7 EXIT RTS  6.3 Features of the 68K's instruction set 247 IF [DO] = [Dl] THEN Actionl CMP D0.D1 Perform test BNE EXIT IF [DO] * [Dl] THEN exit Actionl ELSE execute Actionl EXIT Exit point for construct IF [DO] = [Dl] THEN Actionl ELSE Action2 CMP D0,D1 Compare DO with Dl BNE Action2 IF [DO] * [Dl] perform Action2 Actionl Fall through to actionl if [DO] = [Dl] BRA EXIT Skip round Action2 Action2 Action2 EXIT Exit point for construct FOR K = I TO J ENDFOR MOVE #1,D2 Load loop counter, D2. with I Actionl Perform Actionl ADD #1, D2 Increment loop counter CMP #J+1,D2 Test for end of loop BNE Actionl IF not end THEN go round again EXIT ELSE exit * WHILE [DO] = [Dl] Perform Actionl Repeat CMP DO, Dl Perform test BNE EXIT IF [DO] * [Dl] THEN exit Actionl ELSE carry out Actionl BRA Repeat REPEAT 'loop EXIT Exit from construct REPEAT Actionl UNTIL [DO] = [Dl] Actionl Perform Actionl CMP D0,D1 Carry out test BNE Actionl REPEAT as long as [DO] * [Dl] EXIT Exit from loop CASE OF I 1 = 0 ActionO 1 = 1 Actionl 1 = 2 Action2 1 = 3 Action3 I = N ActionN I > N Exception CMP.B #N,I Test for I out of range BGT EXCEPTION IF I > N THEN exception MOVE.W I, DO Pick up value of I in DO MULU #4,DO Each address is a longword LEA Table,A0 A0 points to table of addresses LEA (A0,D0), AO A0 now points to case I in table MOVEA.L (A0),A0 A0 contains address of case I handler JMP (A0) Execute case I handler 248 Chapter 6 Assembly language programming Table ORG Here is the table of exceptions ActionO DC.L Address of case 0 handler Actionl DC.L Address of case 1 handler Action2 DC.L ) THEN C = 1; E = 0 result is discarded, leaving the contents of DO unaffected by ELSE C = 0; E = 1 flie CMP operation. Only the bits of the CCR are modified. If ENDIF DO contains 00010000, the subtraction yields zero, setting We have to translate this algorithm into 68K code. the Z (zero) flag of the CCR. The following operation, The above action involves the testing of three bits of INPUT BEQ TRUE, results in a branch to the instruction whose address (P, Q, and S), and then setting or clearing two bits of is labeled TRUE. Comparison instructions are of the form OUTPUT (C and E). The bits of OUTPUT not involved in CMP s o u r c e , d e s t i n a t i o n. The difference between CMP the algorithm must not be affected in any way by operations Di, D j and SUB Di, D j is that the former evaluates Di — D; on bits C and E. MOVE.B INPUT,DO Get input status AND.B #%11000000 DO Mask out all bits but P and Q CMP.B #%10000000 DO Test for P = 1, Q = 0 BEQ TRUE Goto action on test true MOVE.B INPUT,DO Get input status again AND.B #%10010000 DO Mask out all bits but P and S CMP.B #%00010000 DO Test for P = 0, S = 1 BEQ TRUE Goto action on test true FALSE MOVE.B OUTPUT,DO Get the output control word AND.B #%11011111 DO Clear bit C OR.B #%00001000 DO Set bit E MOVE.B DO,OUTPUT Set up new output control word BRA EXIT Branch past actions on test true TRUE MOVE.B OUTPUT,DO Get the output control word AND.B #%11110111 DO Clear bit E OR.B #%00100000 DO Set bit C MOVE.B DO,OUTPUT Set up new output control word EXIT Continue  6.4 Addressing modes 249 POINTS TO REMEMBER The assembly language symbol % indicates that the following operand, but the actual operand itself, A N D. B number is interpreted as a binary value and the symbol $ #%11000000, DO means calculate the logical AND means that the following number is interpreted as a between the binary value 11000000 and the contents of DO. hexadecimal value, A N D. B #%11000000, DO tells you much If we had made a mistake in the program and had written more than the hexadecimal and decimal forms of the operand, A N D. B %11000000,DO (ratherthan A N D. B AND.B #$C0,D0andAND.B #192,DO, respectively. #%11000000,DO),the instruction would have AN Ded DO The symbol # informs the assembler that the following with the contents of memory location %11000000 value is not the address of a memory location containing the (i.e. location 192). and throws away the result, whereas the latter evaluates guage programming and introduce a wealth of variations on Di — Dj and puts the result in Dj. address register indirect, addressing. The label FALSE is a dummy label and is not in any way used by the assembly program. It merely serves as a reminder to the programmer of the action to be taken as a result of the 6.4.1 Immediate addressing test being false. At the end of this sequence is an instruction BRA EXIT. A BRA (branch) is equivalent to a GOTO in a high- Application o f i m m e d i a t e addressing level language and causes a branch round the action taken if As an arithmetic constant the result of the test is true. MOVE NUM,D0 [DO] A+B [SP] —» eAQiiOOO A2 = 0 0 0 0 0 0 0 0 A3 = 0 0 0 0 0 0 0 0 N=0 A 4 = 0 0 0 0 0 0 0 0 A 5 = 0 0 0 0 0 0 ? t r f t ^ i a £ 0 0 0 0 0 0 A 7 = 0 0 A 0 0 0 0 0 Z=0 D0 = 0 0 0 0 0 0 0 0 D1 = 0 0 0 0 0 0 0 0 D2 = 0OO0TJtT&«-J2^=0000000O V=n. D4 = 0 0 0 0 0 0 0 0 D 5 = 0 0 0 0 0 0 0 0 D6 = 0 0 0 0 0 0 0 0 D7^ITCrfr9*LCLQ0C= Note the position independent >LEA.L $FE(PCJ AO " code. The value of the PC when ^~i , LEA $FE(PC),AO is executed P C = O O O 4 0 4 S R = 2 0 O O SS=OOAOOOOO us=oooooooo x= '^f402^ Th^°"se*,s°0FEi6/;so ^ the value loaded into AO is an-nnnnnRnn«rn nnnnnnnn in.nnnnnnnn 3Vfl0000000 N= ^2 +FE =500,6 A4 = 0 0 0 0 0 0 0 0 A5 = 0 0 0 0 0 0 0 0 A 6 = 0 0 0 0 0 0 0 0 A7 = 00AOOOO0 Z = L _ _ ! ! _ J _ _ D 0 = 0 0 0 0 0 0 0 0 D 1 = 0 0 0 0 0 0 0 0 D 2 = 0 0 0 0 0 0 0 0 D 3 = 0 0 0 0 0 0 0 0 V=0 D 4 = 0 0 0 0 0 0 0 0 D 5 = 0 0 0 0 0 0 0 0 D 6 = 0 0 0 0 0 0 0 0 D 7 = 0 0 0 0 0 0 0 0 C=0 >BSR.L $0428 We've set A0 to point to the buffer for input data. The next instruction calls the subroutine to input a character. Note the change in the PC to $428. PC=000428 SR=2000 SS=009FFFJC US=00000000 X=0 0 0 9FFFFC:00000408 s A0=00000500 A1=00000000 A2=00TTtn»&e—£3^00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7^CTD?FFFEC_^0 Note the stack pointer D0=00000000 D1=00000000 D2=00000000 D3=00000000 V^0~" has moved up 4 bytes D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 and the return address >MOVE.B #$05,DO is on the stack. PC=00042C SR=2000 SS=009FFFFC US=00000000 X=0 009FFFFC:00000408 s A0=00000500 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=009FFFFC Z=0 D0=00000005 D1=00000000 D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >TRAP #$0F This is the character entered from the keyboard and captured by the TRAP #15. C=00042E SR=2000 SS=009FFFFC US=00000000 X=0 009FFFFC:00000408 s A0=00000500 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=009FFFFC Z=0 D0=00000005 D1=0000005A D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >RTS Having got the input (in this case Z) in Dl, we return from the subroutine. Watch the program counter again. It is currently $42E and will be replaced by $408 (i.e. the address of the instruction after the subroutine call. PC=000408 SR=2000 SS=O0AO0O0O US=00000000 X=0 A0=00000500 A1=00000000 A2-00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=O0A00O00 Z=0 D0=00000005 D1=0000005A D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >MOVE.B D1,(A0)+  6.5 The stack 269 We now store the character in Dl in memory and increment the pointer in AO. PC=00040A SR=2000 SS=00A00000 US=00000000 X=0 A0=00000501 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=00A00000 Z=0 D0=00000005 D1=0000005A D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >CMPI.B #$40,Dl PC=00040E SR=2000 SS=00A00000 US=00000000 X=0 A0=00000501 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=00A00000 Z=0 D0=00000005 D1=0000005A D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 00 >BNE.S $0404 We test the character in D1 for equality with '@' = $40 and then branch back to $0404 if we haven't input an '@'. PO000404 SR=2000 SS=00A00000 US=00000000 X=0 A0=00000501 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=0OAOO0OO Z=0 D0=00000005 D1=0000005A D2=00000000 D3=00000000 v=o D4=00000000 D5=00000000 D6=00000000 D7=00000000 c=o >BSR.L $0428 We haven't, so we continue by reading another character. PC-000428 SR=2000 SS=009FFFFC US=00000000 X=0 009FFFFC:00000408 s A0=00000501 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=009FFFFC Z=0 D0=00000005 D1=0000005A D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >MOVE.B #$05,DO To avoid more tracing, we'll jump ahead to the point at which a '@' has been input in DO. P O 0 0 0 4 2 C SR=2000 SS=009FFFFC US=00000000 X=0 009FFFFC:00000408 s A0=00000501 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=009FFFFC Z=0 D0=00000005 D1=0000005A D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >TRAP #$0F PC=OO^M2X^R^2TTO«--SS^I1£9TFFFC US=00000000 X=0 009FFFFC: 00000408 s A0=00000502 Al=00000000~A2^0lKTTO^e«-Aa£00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=009FFF Here's the '@' that D0=00000005 m=nnnnnn/in.-,n->-n^nnnnnn n^nnnnnnnn V =o D4=00000000 D5=00000000 D6=00000000 D7=0 we entered and its >RTS ASCII value in Dl. PC=000408 SR=2000 SS^OOAOOOOO OS=00000000 X=0 A0=00000502 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=00A00000 Z=0 D0=00000005 Dl=00000040 D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >MOVE.B D1,(A0)+ 270 Chapter 6 Assembly language programming PC=00040A SR=2000 SS=OOAO00O0 US=00000000 X=0 A0=00000503 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=OOAOO0OO Z=0 D0=00000005 Dl=00000040 D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >CMPT.B #540,Dl PC=00040E SR=2004 SS=00A000O0 US=O0OO0000 X=0 A0=00000503 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=0OA0O00O Z=l D0=00000005 Dl=00000040 D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >BNE.S $0404 Because D l contains the ASCII code for'@', the test for equal- ity will yield true and we will not take the branch back to $0404. P O 0 0 0 4 1 0 SR=2004 SS=00A00000 US=00000000 X=0 A0=00000503 A1=00000000 A2=00000000 A3=00000000 N=0 A 4 = 0 0 0 0 0 0 0 0 A 5 = 0 0 0 0 0 0 0 0 A 6 = 0 0 0 0 0 0 0 0 A7=00A00000 Z=l D0=00000005 Dl=00000040 D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >LEA.L $EE(PC),A0 T h e next instructions reset the pointer to the top of the buffer, read a character, a n d compare it to '@'. PC=000414 SR=2004 SS=O0AOO0OO US=00000000 X=0 A0=00000500 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=O0AOO000 Z=l D0=00000005 Dl=00000040 D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >MOVE.B (A0)+,D1 PC=000416 SR=2000 SS=OOA0O0OO US=00000000 X=0 A0=00000501 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=O0AO0OOO Z=0 D0=00000005 D1=0000005A D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >CMPI.B #$40,Dl PC=00041A SR=2000 SS=00A00000 US=00000000 X=0 A0=00000501 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=00A00000 Z=0 D0=00000005 D1=0000005A D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >BEQ.L $0424 If it isn't an '', we will print it by calling the o u t p u t routine. PC=00041E SR=2000 SS=0OAOO00O OS=00000000 X=0 A0=00000501 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=O0AOOO0O Z=0 D0=00000005 D1=0000005A D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >BSR.L $0430  6.5 The stack 271 PC=000430 SR=2000 SS=009FFFFC US=00000000 X=0 009FFFFC:00000422 s A0=00000501 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=009FFFFC Z=0 D0=00000005 D1=0000005A D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >MOVE.B #$06,DO In this case we have branched to address $0430. P O 0 0 0 4 3 4 SR=2000 SS=009FFFFC US=00000000 X=0 009FFFFC:00000422 s A0=00000501 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=009FFFFC Z=0 D0=00000006 D1=0000005A D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >TRAP #$0F We call the operating system with the TRAP. Note that the contents of D1 will be printed as the ASCII character Z. Then we return to the body of the program. © PC=000436 SR=2000 SS=009FFFFC US=00000000 X=0 009FFFFC-.00000422 s A0=00000501 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=009FFFFC Z=0 D0=00000006 D1=0000005A D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >RTS Note the change in the value of the PC following the RTS. PC=000422 SR=2000 SS=O0AO0OOO US=00000000 X=0 A0=00000501 A1=00000000 A2=00000000 A3=00000000 N=0 A4=00000000 A5=00000000 A6=00000000 A7=00A00000 Z=0 D0=00000006 D1=0000005A D2=00000000 D3=00000000 V=0 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 >BRA.S $0414 And so on.. 6.5.3 Subroutines, the stack, and pressed. A return to the calling point is made with the ASCII parameter passing code of the character in data register D1. In order for a subroutine to carry out its function, it is almost You can even use the C-bit in the CCR to pass informa- always necessary to transfer data between the calling program tion from a subroutine to its calling program; for example, and the subroutine. Up to now we have passed data to and from to indicate an error state. Suppose a subroutine has been the subroutine via data registers. In the previous example, we called to read data from a terminal and the terminal is faulty called the subroutine GET_CHAR to input a character from the or not switched on. By setting the carry bit prior to a return keyboard. When this subroutine is invoked by the operation from subroutine, the calling program can be informed that BSR GET_CHAR, a branch is made to the entry point of the sub- an error exists as the following fragment of a program routine. This subroutine reads the keyboard until a key is demonstrates. 272 Chapter 6 Assembly language programming BSR GETDATA Call subroutine and return with data in DO BCS ERROR IF carry flag set THEN something went wrong ELSE deal with the data ERROR Recover from error condition You can't use registers to transfer large quantities of data to above the top of the stack). If an interrupt occurs or you call and from subroutines, due to the limited number of registers. a subroutine, the new return address will be pushed on the You can pass parameters to a subroutine by means of a mail- top of the stack overwriting the old return address. Never box in memory. Consider the following. move the stack pointer below the top of stack. MOVE.W Paraml,Mboxl Put first parameter in mail box 1 MOVE.W Param2,Mbox2 Put second parameter in mail box 2 BSR Sub Now call the subroutine Return here... Sub MOVE.W Mboxl,DO Retrieve the first parameter MOVE.W Mbox2,Dl Retrieve the second parameter RTS Return to the calling program Such a solution is poor, because the subroutine can't be You can avoid using the stack pointer by copying it to interrupted or called by another program. Any data stored in another address register with LEA (A7) , AO. NOW you can explicitly named locations could be corrupted by the inter- use AO to get the parameters; for example, PI can be loaded rupting program (see the box on interrupts). Let's look at into Dl by MOVE.W 6(A0) ,D1. The offset 6 is required how data is transferred between a subroutine and its calling because the parameter PI is buried under the return address program by many high-level languages. (4 bytes) and PI (2 bytes). Similarly, P2 can be loaded into D2 by MOVE.W 4(AO) ,D2. Passing parameters on the stack After returning from the subroutine with RTS, the contents of An ideal way of passing information between the subroutine the stack pointer are [A7] — 4, where A7 is the value of the stack and calling program is via the stack. Suppose two 16-bit pointer before PI and P2 were pushed on the stack. The stack parameters, PI and P2, are needed by the subroutine pointer can be restored to its original value or cleaned up by exe- ABC(P1,P2). The parameters are pushed on the stack cuting LEA 4 (A7) , A7 to move the stack pointer down by two immediately before the subroutine call by the following code: words. Note that LEA 4 (A7) , A7 is the same as ADD. L # 4, A7. PI and P2 are, of course, still in the same locations in memory but they will be over- MOVE.W P 1 , - ( A 7 ) Push the first parameter on t h e s t a c k written as new data is pushed on the stack. MOVE. W P 2 , - ( A 7 ) Push the second parameter BSR ABC Call ABC(P1,P2) By using the stack to pass parameters to a subroutine, the subroutine may be inter- The state of the stack prior to the subroutine call and rupted and then used by the interrupting program without immediately after it is given in Fig. 6.30. Note that the return the parameters being corrupted. As the data is stored on the address is a longword and takes up two words on the stack. stack, it is not overwritten when the subroutine is interrupted On entering the subroutine, you can retrieve the parame- because new data is added at the top of the stack, and then ters from the stack in several ways. However, you must never removed after the interrupt has been serviced. change the stack pointer in such a way that you move it down Let's look at another example of parameter passing in detail. the stack. Consider Fig. 6.30(c) where the stack pointer is In the following program two numbers are loaded into DO and pointing at the return address. If you add 4 to the stack Dl, and then the contents of these registers are pushed on the pointer, it will point to parameter P2 on the stack. You can stack. A subroutine, Addup, is called to add these two numbers now get P2 with, say, MOVE. W (A7) , DO. However, the return together. In this case the result is pushed on the stack. We've used address is no longer on the stack (it's still there in memory blue to highlight code that performs the parameter passing.  6.5 The stack 273 (a) Initial state of the stack. (b) Immediately before BSR. (c) immediately after BSR. Stack Stack Stack Address with respect to the stack pointer return ° / address J>2 Stack pointer Stack pointer PI P2 P1 + +6 y Stack pointer TOS n-4 +8 figure 6.30 Passing parameters on the stack (all values on the stack are words or longwords). THE INTERRUPT An interrupt is a method of diverting the processor from its explicitly named memory locations will be overwritten and intended course of action, and is employed to deal with errors corrupted by the re-use of the subroutine. If the data had been and external events that must be attended to as soon as they stored in registers and the content of the registers pushed on occur. Whenever a processor receives an interrupt request the stack by the interrupt-handling routine, no data in the from a device, the processor finishes its current instruction and subroutine would have been lost by its re-use. After the sub- then jumps to the program that deals with the cause of the routine has been re-used by the interrupt-handling routine, the interrupt. After the interrupt has been serviced, a return is contents of the registers stored on the stack are restored and a made to the point immediately following the last instruction return from interrupt is made with the state of the registers before the interrupt was dealt with. The return mechanism of exactly the same as at the instant the interrupt was serviced. the interrupt is almost identical with that of the subroutine— Interrupts may originate in hardware or software. A the return address is saved on the stack. hardware interrupt may occur when you move the mouse. Suppose a subroutine is interrupted during the course of its A software interrupt may occur when you perform an illegal execution. If the interrupt-handling routine also wishes to use operation or even when you generate one with a TRAP #15 the same subroutine (yes, that's possible), any data stored in instruction. ORG $400 LEA $1000,A7 MOVE W #l,DO Set up the stack pointer MOVE W #2,D1 Set up two parameters in DO and Dl MOVE W D0,-(A7) Push parameter 1 on the stack MOVE w D1,-(A7) Push parameter 2 on the stack BSR AcidUp Call adder routine MOVE w (A7)+,D2 Read the result from the stack LEA 2LEA.L $1000,SP PC=000404 SR=2000 SS=00001000 US=00000000 X=0 00001000:00000000 s A0=00000000 A1=00000000 A2=00000000 A3=00000000 N=0 00001004:00000000 s+4 A4=00000000 A5=00000000 A6=00000000 A7=00001000 Z=0 00001008:00000000 s+8 D0=00000000 D1=00000000 D2=00000000 D3=00000000 V=0 0000100C:00000000 s+12 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 00001010:00000000 s+16 >MOVE.W #$01,DO Note the five new entries to the right of the register display. These lines display the five longwords at the top of the stack. Each line contains the stack address, the longword in that address, and the address with respect to the current stack pointer. Stack Stack P2=2 0FFC P1=1 OFFE OFFE Stack pointer Stack pointer Stack pointer TOS 1000 $1000 $0FF£ 1000 1000 SOFFE (a) Initial state of the stack. (b) After pushing P1 w i t h (c) After pushing P2 with MOVE.W D 0 , - ( A 7 ). MOVE.W D 0 , - ( A 7 ). Stack Stack Stack Return /address Offset f r o m 0FF8 SP r*t»000414 0FF8 OFFE 30000414 0 0FFC 0FFC '*S P2=2 0FFC P2=2 +4 P2=2 OFFE P1=1 OFFE OFFE P1=1 +6 P1=1 1000 Stack pointer Stack pointer Stack pointer 1000 +8 $0FF8 S0FF8 $0FFC Figure 6.31 The state of the (d) After calling the subroutine. (d) Accessing parameters (d) After returning from stack during the execution of a in the subroutine. the subroutine. program.  6.5 The stack 275 PC=000408 SR=2000 SS=00001000 US=00OO0OO0 X=0 00001000:00000000 s A0=00000000 A1=00000000 A2=00000000 A3=00000000 N=0 00001004:00000000 s+4 A4=00000000 A5=00000000 A6=00000000 A7=00001000 Z=0 00001008:00000000 s+8 DO-00000001 Dl=O0O0OO0O D2=00000000 D3=00000000 V=0 0000100C:00000000 s+12 D4=0OO000O0 D5=00000000 D6=00000000 D7=00000000 C=0 00001010:00000000 s+16 >MOVE.W #$02,Dl PC=00040C SR=2000 SS=00001000 US=00000000 X=0 00001000:00000000 s A0=00000000 A1=00000000 A2=00000000 A3=00000000 N=0 00001004:00000000 s+4 A4=00000000 A5=00000000 A6=00000000 A7=00001000 Z=0 00001008:00000000 s+8 D0=00000001 Dl=00000002 D2=00000000 D3=00000000 V=0 0000100C:00000000 s+12 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 00001010:00000000 s+16 >MOVE.W DO,-(SP) PC=00040E SR=2000 SS=O0000FFE US=00000000 X=0 00000FFE:OOO10O00 s A0=00000000 A1=00000000 A2=00000000 A3=00000000 N=0 00001002:00000000 s+4 A 4 = 0 0 0 0 0 0 0 0 A 5 = 0 0 0 0 0 0 0 0 A 6 = 0 0 0 0 0 0 0 0 A7=0OOOOFFE Z=0 00001006:00000000 s+8 D 0 = 0 0 0 0 0 0 0 1 D l = 0 0 0 0 0 0 0 2 D 2 = 0 0 0 0 0 0 0 0 D3=00000000 V=0 0000100A:00000000 s+12 D4=00000000 D 5 = 0 0 0 0 0 0 0 0 D6=00000000 D7=00000000 C=0 0000100E:00000000 s+16 >MOVE.W D1,-(SP) Note how the instruction MOVE. w DO,— (SP) has mod- ified the stack. The top of the stack is no longer $1000, but $0FFE. You can also see that the contents of DO.W (i.e. 0001) has been pushed on the stack. PC=000410 SR=2000 SS=00000FFC US=00000000 X=0 00000FFC:OO020001 s A0=00000000 A1=00000000 A2=00000000 A3=00000000 N=0 00001000:00000000 s+4 A 4 = 0 0 0 0 0 0 0 0 A 5 = 0 0 0 0 0 0 0 0 A 6 = 0 0 0 0 0 0 0 0 A7=00000FFC Z=0 00001004:00000000 s+8 D0=00000001 Dl=00000002 D2=00000000 D3=00000000 V=0 00001008:00000000 s+12 D4=00000000 D 5 = 0 0 0 0 0 0 0 0 D 6 = 0 0 0 0 0 0 0 0 D7=00000000 C=0 0000100C:00000000 s+16 >BSR.L $041E PC=00041E SR=2000 SS=00O0OFF8 US=00000000 X=0 O0000FF8:OOOOO414 s A0=00000000 A1=00000000 A2=00000000 A3=00000000 N=0 00000FFC.-00020001 s + 4 A 4 = 0 0 0 0 0 0 0 0 A 5 = 0 0 0 0 0 0 0 0 A 6 = 0 0 0 0 0 0 0 0 A7-0OOOOFF8 Z=0 0 0 0 0 1 0 0 0 : 0 0 0 0 0 0 0 0 s+8 D0=00000001 Dl=00000002 D2=00000000 D3=00000000 V=0 00001004:00000000 s+12 D4=00000000 D5=00000000 D 6 = 0 0 0 0 0 0 0 0 D7=00000000 C=0 00001008:00000000 s+16 >MOVE.W $04(SP),D2 At this point the return address, $00000414, has been pushed on the stack and the stack pointer is now pointing at $00000FF8. PC=000422 SR=2000 SS=00000FF8 US=00000000 X=0 00000FF8:00000414 s A0=00000000 A1=00000000 A2=00000000 A3=00000000 N=0 00000FFC:00020001 s+4 A4=00000000 A5=00000000 A6=00000000 A7=0000OFF8 Z=0 00001000:00000000 s+8 D0=00000001 Dl=00000002 D2=00000002 D3=00000000 V=0 00001004:00000000 s+12 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 00001008:00000000 s+16 >MOVE.W $06(SP),D3 PC=000426 SR=2000 SS=O0OOOFF8 US=00000000 X=0 OOOOOFF8:00000414 s A0=00000000 A1=00000000 A2=00000000 A3=00000000 N=0 OOOOOFFC:00020001 s+4 A4=00000000 A5=00000000 A6=00000000 A7=00000FF8 Z=0 00001000:00000000 s+8 D0=00000001 Dl=00000002 D2=00000002 D3=00000001 V=0 00001004:00000000 s+12 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 00001008:00000000 s+16 >ADD.W D2,D3 276 Chapter 6 Assembly language programming PC=000428 SR=2000 SS=00000FF8 US=00000000 X=0 OOOOOFF8:00000414 s A0=00000000 A1=00000000 A2=00000000 A3=00000000 N=0 00000FFC:00020001 s+4 A4=00000000 A5=00000000 A6=00000000 A7=00000FF8 Z=0 00001000:00000000 s+8 D0=00000001 Dl=00000002 D2=00000002 D3=00000003 V=0 00001004:00000000 s+12 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 00001008:00000000 s+16 >MOVE.W D3,$04(SP) PC=00042C SR=2000 SS=00000FF8 US=00000000 X=0 OOOOOFF8:00000414 s A0=00000000 A1=00000000 A2=00000000 A3=00000000 N=0 OOOOOFFC:00030001 s+4 A4=00000000 A5=00000000 A6=00000000 A7=00000FF8 Z=0 00001000:00000000 s+8 D0=00000001 Dl=00000002 D2=00000002 D3=00000003 V=0 00001004:00000000 s+12 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 00001008:00000000 s+16 >RTS PO000414 SR=2000 SS=00000FFC US=00000000 X=0 O00O0FFC:0OO3O001 s A0=00000000 A1=00000000 A2=00000000 A3=00000000 N=0 00001000:00000000 s+4 A4=00000000 A5=00000000 A6=00000000 A7=OOO0OFFC Z=0 00001004:00000000 s+8 D0=00000001 Dl=00000002 D2=00000002 D3=00000003 V=0 00001008:00000000 s+12 D4=00000000 D5=00000000 D6=00000000 D7=00000000 C=0 0000100C:00000000 s+16 >MOVE.W (SP)+,D4 PC=000416 SR=2000 SS=0O0OOFFE US=00000000 X=0 OOCOOFFE:00010000 s A0=00000000 A1=00000000 A2=00000000 A3=00000000 N=0 00001002:00000000 s+4 A4=00000000 A5=00000000 A6=00000000 A7=00000FFE Z=0 00001006:00000000 s+8 D0=00000001 Dl=00000002 D2=00000002 D3=00000003 V=0 0000100A:00000000 s+12 D4=00000003 D5=00000000 D6=00000000 D7=00000000 C=0 0000100E:00000000 s+16 >LEA.L $02(SP),SP PC=00041A SR=2000 SS=00001000 US=00000000 X=0 00001000:00000000 s A0=00000000 A1=00000000 A2=00000000 A3=00000000 N=0 00001004:00000000 s+4 A4=00000000 A5=00000000 A6=00000000 A7=00001000 Z=0 00001008:00000000 s+8 D0=00000001 Dl=00000002 D2=00000002 D3=00000003 V=0 0000100C:00000000 s+12 D4=00000003 D5=00000000 D6=00000000 D7=00000000 C=0 00001010:00000000 s+16 >STOP #$2700 Passing parameters by reference The result 1 + 2 = 3 is in data register D3, and the stack We have passed a parameter by value to the subroutine by pointer is the same as its starting value $1000. Passing a para- pushing a copy of its value on the stack. There are two copies meter to a subroutine by value is easy. Getting a result back of the parameter, the original in the calling program and its from the subroutine is trickier, as we'll soon see. copy on the stack. If a parameter is passed by value, changing it within the subroutine doesn't change its value in the calling program—as the next example demonstrates. Program to call a subroutine that swaps two numbers A and B ORG $400 LEA $1000,A7 Set up the stack pointer MOVE. W A,-(A7) Push value of parameter A MOVE..W B,-(A7) Push value of parameter B BSR SWAP Call subroutine to swap A and B LEA 4(A7),A7 Clean up the stack STOP #$2700 Stop SWAP MOVE.W 4(A7),D1 Get first parameter in DO MOVE.W 6(A7),4(A7) Copy second parameter to first parameter MOVE.W D1,6(A7) Copy first parameter to second parameter RTS A DC.W $1234 B DC.W $5678 END $400  6.5 The stack 277 This program calls a subroutine to swap two numbers, In this case, there is only one copy of the parameter. We repeat A and B, which are first pushed on the stack in the main pro- the example in which we added two numbers together, and, this gram. In subroutine SWAP the two parameters are retrieved time, pass the parameters to the subroutine by reference. from their locations on the stack and swapped over. Once a The following program introduces a new instruction, return from subroutine is made and the stack cleaned up, the push effective address PEA, which pushes an address in the parameters on the stack are lost. Parameters A and B in the stack; for example, the operation PEA PQR pushes the address main program were never swapped. PQR on the stack. The instruction PEA PQR is equivalent to MOVE.L #PQR, - (A7). ORG $400 LEA $1000,A7 Set up the stack pointer PEA X Push address of variable X PEA X Push address of variable Y PEA Z Push address of variable 2 (the- result;': BSR AddUp Call adder routine MOVE.W Z,D2 Read the result (a dummy operation) LEA 12(A7),A7 Clean up stack STOP #$2700 Stop * AddUp HOVEA.L 12(A7),A0 Get address of parameter X MOVKA.L S(A7),A1 Get address of parameter Y MOVE. Vi (AD) ,D2 Get value of X MOVE.W (All,D3 Get value of Y ADD D2,D3 Add them MOVEA.L 4(A7),A3 Get address of parameter Z MOVE.W D3, (A3) Put result in variable Z RTS * ORG $500 X DC.W 1 Y