3. Memory, Architecture and Assembly
Part of
22C:40, Computer Organization and Hardware Notes
|
In 1946, Burks Goldstine and Von Neumann published their seminal report Preliminary discussion of the logical design of an electronic computing instrument. This report described what is now the common model for a computer system, although the technology with which they proposed to implement this model looked fairly laughable by the standards of the early 1960's, and the details of the system they proposed looked quite strange from today's perspective. The basic elements of their model of computing, however, are as applicable today as they were in the 1940's. Now as then, we think of computers as having the following basic components:
Central Processing Unit CPU
| ||
Interface(s) or Bus(ses) | ||
Memory | Input Output |
In this class, we will focus on one fictional computer architecture, described broadly in Chapter 1 of the Hawk manual. Pay particular attention to the introductory summary with its discussion of the 32 bit word format and how words are broken into halfwords and bytes, and to the memory resources section with its discussion of the memory address format.
Essentially all general purpose computers designed since 1970 have had similar memory formats, and since 1980, most general purpose computers have been 32-bit computers, like the Hawk. Broadly speaking, there has only been one big division that distinguishes two classes of 32-bit computers. Some count bytes within a 32-bit word from left to right; these are described as highbyters or bigendian machines (a reference to Gulliver's Travels), while others count bytes from right to left within a word; these are described as lowbyters or littleendian machines. The Hawk is a lowbyter, as is the Intel Pentium. There are few reasons to claim that one approach is better than the other, but mixing them leads to big difficulties.
31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 | 15 | 14 | 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
byte 3 | byte 2 | byte 1 | byte 0 | ||||||||||||||||||||||||||||
halfword 1 | halfword 0 | ||||||||||||||||||||||||||||||
word |
Like most modern computers, the Hawk memory addressing scheme does not allow individual bits of memory to be given distinct addresses. If you want to set, reset or test a single bit, you have to do this with arithmetic or logical perations, a subject we will discuss at length, later.
Like most modern computers, the Hawk does assign a distinct integer memory address to each byte in memory, and it allows addressing of bytes, halfwords and words, so we may view memory as an array of bytes:
07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
byte 0 | |||||||
byte 1 | |||||||
byte 2 | |||||||
byte 3 | |||||||
byte 4 | |||||||
byte 5 | |||||||
byte 6 | |||||||
. . . |
The Hawk memory can also be viewed as an array of 16-bit halfwords, but because each halfword is composed of two bytes, only the even integers are used as the addresses of halfwords:
15 | 14 | 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
halfword 0 | |||||||||||||||
halfword 2 | |||||||||||||||
halfword 4 | |||||||||||||||
halfword 6 | |||||||||||||||
halfword 8 | |||||||||||||||
. . . |
Finally, the Hawk memory may be viewed as an array of 32-bit words, but again, because each word is composed of two halfwords or 4 bytes, the integers used as addresses of halfwords are all evenly divisible by 4.
31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 | 15 | 14 | 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
word 0 | |||||||||||||||||||||||||||||||
word 4 | |||||||||||||||||||||||||||||||
word 8 | |||||||||||||||||||||||||||||||
. . . |
It is important to remember that word 0 contains halfword 0 and halfword 2 which contain bytes 0 through 3, and word 4 contains halfword 4 and halfword 6 which contain bytes 4 through 7. We are dealing with one memory that may be viewed in many ways! The following diagram emphasizes this:
07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 | ||
word 0 | halfword 0 | byte 0 | |||||||
byte 1 | |||||||||
halfword 2 | byte 2 | ||||||||
byte 3 | |||||||||
word 4 | halfword 4 | byte 4 | |||||||
byte 5 | |||||||||
halfword 6 | byte 6 | ||||||||
byte 7 | |||||||||
. . . |
Exercises
a) Pick a sequence of 4 consecutive memory addresses starting at a randomly chosen address and identify which of them are valid byte addresses, halfword addresses and word addresses. (If this is a homework assignment, use use the due date as your random address, forming the numerical month, day and year in the form MM/DD/YY into a 6-digit decimal number MMDDYY and using that as your starting address).
Memory addresses on the Hawk are also 32-bit words. In this regard, the Hawk is quite comparable to the Pentium, the Power PC, and many previous 32-bit computer architectures. So, if we were declaring the Hawk memory in C or C++, where char variables are 8-bit bytes, we would declare it as:
char memory[4294967296];
The constant 4294967296 used above is 232, and the rules of C and C++ for arrays say that the legal range of subscripts for the resulting array runs from 0 to 4294967295 which is 232-1. This is identically the same as the range of legal unsigned integer values that can be represented in a 32-bit word.
There some little problems with this declaration! First, of course, it does not allow halfword and word addressing, and second, on most computers, if you tried to declare this array in a real program, you would most likely get an error message such as "size of array 'memory' is too large" (that is the message from Objective C under MacOS X).
Nonetheless, the contents of any word of memory on the Hawk computer can be used as a memory address. Conceptually, the most significant 30 bits of the address give the word of memory being addressed, and the least significant two bits give the halfword and byte being addressed.
31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 | 15 | 14 | 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
word in memory | byte in word |
If the memory address is being used for a full-word operand, the byte-in-word field should be all zero. If the memory address is being used for a half-word operand, the byte-in-word field should be either 00 or 10. Only when the memory address is used for a single-byte operand is the byte-in-word field field unconstrained.
The memory addresses described here allow addressing of about 4 gigabytes of memory, or exactly 4,294,967,296 bytes. In fact, few computers are ever configured with this much memory. We say that a 32-bit machine has an address space of 4,294,967,296 bytes because there are that many distinct memory addresses, but within this address space, only some of these addresses are connected to physical memory. The remainder are typically unimplemented, and if they are used by a program, the hardware will typically trap the attempt and raise an exception in the program.
Furthermore, the physical memory devices plugged into different memory addresses are not always identical. Some parts of the memory address space may be populated by read-only memory locations, or ROM, while other parts of the address space may be populated by read-write memory locations, or RAM (this acronym is somewhat archaic, since ROM is also a form of random-access memory). To add to the potential confustion, the physical hardware attached to some memory addresses need not behave like memory at all. For example, on many computers, certain memory addresses are reserved for interfaces to input-output devices.
The minimum configuration for the Hawk machine, for example, is configured with read-only memory starting at byte zero and running up to byte 0000FFFF16, and with read-write memory running from byte 0001000016 to 0001FFFF16. In this minimum configuration, locations 0002000016 to FEFFFFFF16 are unimplemented, and locations FF00000016 and up are reserved for input-output interfaces.
00000000
ROM 0000FFFF |
00010000 RAM 0001FFFF |
00020000 unused FEFFFFFF |
FF000000 I/O FFFFFFFF |
Exercises
b) What are the decimal representations of the first and last addresses of the read-only part of the address space of the minimal Hawk computer?
c) What are the decimal representations of the first and last addresses of the read-write part of the address space of the minimal Hawk computer?
d) What are the decimal representations of the first and last addresses of the unused part of the address space of the minimal Hawk computer?
e) What are the decimal representations of the first and last addresses of the part of the address space of the Hawk computer reserved for input-output device interfaces?
It is possible to store a 32-bit word of data in any 4 consecutive 8-bit bytes of memory, but this is not usually recommended. The problem with such arbitrary alignment of data is that the hardware of most computers is built purely in terms of reading and writing entire words of memory. While programmers may think in terms of 32-bit addresses, the physical connection from the central processor to memory uses only a 30 bit address, that is, the address of an aligned word.
On some computers, when a program attempts to read from a non-aligned word or halfword, the central processor will automatically read the two words that contain the two parts of the non-aligned word. This means that reading a non-aligned word takes twice as long as reading an aligned word, so good programmers and good compilers will never allocate space for variables that is not properly aligned. Because of this, other computers don't even bother supporting non-aligned data. The Hawk takes this approach.
So far, we have described the memory of the computer as an array of bytes, where these can be grouped two at a time and described as an array of halfwords, or four at a time and described as an array of fullwords, but to use these, we need tools to load data into memory. Before we can run a program, we must reduce it to a sequence of machine instructions and then assemble these machine instructions into memory so that they can be run. The following software tools are typically used to do this:
- A Compiler
- Compilers take, as input, the source code for a program written in a higher-level programming language such as FORTRAN (the oldest high-level programming language to achieve widespread use, dating back to 1956) or Java (a relatively young programming language, dating to 1995).
Whatever the source language, compilers translate this to a sequence of macine instructions (or, in the case of Java, a sequence of instructions for the Java virtual machine). These instructions are not generally placed in main memory, ready to execute. Instead, they are coded in a binary object code or a textual assembly code, ready for processing by later steps on the road to actually running the program.
- An Assembler
- Assemblers take, as input, the assembly code for a program, written in an assembly language. This describes, in human-readable form, the intended contents of memory. Many compilers produce output in assembly language, or, thinking in different terms, many compilers include an assembler that performs the last step in the compilation process.
Assemblers take care of many of the details of storage allocation and they generally take care of all of the details of constructing specific binary encodings for machine instructions and constants that are to be loaded in memory. The output of the assembler, however, is generally not placed directly in memory; instead, it is typically encoded in a binary object code.
- A Linker
- Linkers take, as input, the object code for the different components of a program. For all but the simplest of programs, it is common to write the code for the different components in separate source files, compile or assemble these independently, and then combine them with a linker. Some of the separately compiled or assembled components may be organized into libraries, while other parts may be compiled or assembled separately for the sole purpose of modularizing the source code into reasonable-sized and managable parts.
The output of the linker is sometimes referred to as an executable file, and sometimes it is referred to as a loadable object file or a load module.
- A Loader
- Loaders take, as input, a loadable object file and place this in memory, performing the final conversion from object code to machine code, and also, frequently making the final decision about the relocation of the loaded code, that is, what instructions and variables are placed in what memory locations.
The SMAL assembler processes a symbolic macro assembly language, from which it takes its name. The central function of this, and all assembly langages is to describe the placement of values in memory.
The basic tools SMAL offers for packing data into memory are the data storage directive described in Chapter 3 of the SMAL Assembly Language Manual. In summary, each value to be assembled in memory is listed on one line of the assembly language source file, with a statement of whether it is a byte, halfword or word, as illustrated in the following small example:
B 0 B -1 H #0F0F W 8#12525252525 |
This little example asks the assembler to place 2 bytes, 1 halfword and 1 word in memory (a total of 8 bytes), where the first byte contains a zero, specified as a decimal constant, the second byte contains -1, also given as a decimal constant. The SMAL assembly language uses the pound-sign prefix (#) to indicate use of number bases other than 10. In this example, the halfword is given in hexadecimal (base 16) and the final word of the example is given in octal (base 8). Assembling this data into memory produces the following result:
31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 | 15 | 14 | 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
#0F0F | -1 | 0 | |||||||||||||||||||||||||||||
8#12525252525 |
In the above table, the arrangement of bytes, halfwords and words produced by the assembler is shown, but the values are still shown as they appeared in the assembly source code. The data actually lands in memory as shown below:
31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 | 15 | 14 | 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Note in the above example that neither the assembly language source code nor the resulting memory images contained any mention of the addresses into which the data was to be assembled. In our assembly language, as in most others, the source code merely specifies that consecutive data from the assembly source are to be placed into consecutive locations in memory.
Our assembly language does allow specificaiton of the assembly origin, that is, the address into which data is to be assembled. For example, if we wanted the code shown above to be stored in 8 consecutive bytes starting with byte 100 (decimal), we would add one line to the example:
. = 100 B 0 B -1 H #0F0F W 8#12525252525 |
By way of explanation, most of the lines of assembly code in the above example direct the assembler to place values in memory, but the first line, containing the equals sign, instructs the assembler to assign the value 100 to a variable inside the assembler. The variable in queston has the name . (a period) and this strangely named variable is the assembler's location counter. The location counter is the internal variable inside the assembler that it uses to determine where the next byte, halfword or word will be placed in memory.
When the assembler assembles a byte, it places it in the byte referenced by the location counter, and then increments the location counter by one. When the assembler assembles a halfword, it places it in the halfword referenced by the location counter, and then increments the location counter by two. When the assembler assembles a word, it places it in the word referenced by the location counter, and then increments the location counter by four.
Of course, like any programming language intended for human readers, our assembly language allows comments, blank lines and other features that improve its readability to a human reader:
TITLE "A meaningless example" ; The following assembles into 100 to 107 . = 100 B 0 ; 100 B -1 ; 101 H #0F0F ; 102 and 103 W 8#12525252525 ; 104 to 107 END |
By way of explanation, comments in the SMAL assembly language begin with a semicolon and run to the end of the line. Blank lines are allowed, and they are ignored. A line containing just a comment is exactly the same, to the assembler, as a blank line. Finally, in addition to the B, W and H directives that direct the assembler to place bytes, words and halfwords into memory, the assembler also allows many other directives, and one of these is the TITLE directive that is used to give an assembly language program a title.
When you are debugging a machine-language program, it is very convenient to be able to see what the assembler did when it processed that program. To simplify this, most assemblers will, optionally, produce not only an object code output file, ready for loading and possibly execution, but also a listing file formatted for human consumption to indicate what the assembler included the object file. In the case of the SMAL assembler, the above source file, when assembled, will produce the following listing file:
SMAL32, rev 6/98. "A meaningless example" 15:46:51 Page 1 Thu Aug 28 2003 1 TITLE "A meaningless example" 2 3 ; The following assembles into 100 to 107 4 . = 100 5 000064: 00 6 B 0 ; 100 000065: FF 7 B -1 ; 101 000066: 0F0F 8 H #0F0F ; 102 and 103 000068: 55555555 9 W 8#12525252525 ; 104 to 107 10 11 END |
The assembler listing shown above contains, in addition to the original source file, a header on each page giving the page number, time and date of assembly. In additon, each line of the source file is numbered, sequentially, and, most important, on the left-hand side of the line number, and only on those lines of the file that actually put something into memory, the memory location is shown, in hexadecimal, along with the data placed there, also in hexadecimal.
When editing assembly language programs, it is conventional to keep things aligned in neat columns. Conventionally, your editing window should be configured to use a fixed-width font with tabs set every 8 columns and a window 80 columns wide. Use tabs for indenting!
When debugging an assembly language program it is very convenient to keep a listing of that program on hand. In the old days, you would almost always print the listing on paper and have this on your desktop while you were debugging the code. Today, you open a window on your virtual desktop so you can look at the listing while you actually run the code in a second window. When printing assembly listing files, use a fixed-width font, and consider printing in landscape format or in a very small font so that long lines print without wrapping (allow for 80 characters on each assembly source line, plus 32 characters of text added to the left of each line).
Exercises
f) What is the hexadecimal equivalent of the one-word constant 125252525258.
g) Suppose we assemble "B 255" and "B -1" into memory. These two lines of assembly code load exactly the same value into memory, yet one is loading a positive value and the other is loading a negative value. Why are both of these considered correct?
h) Rewrite the running example used above so that it assembles the result into the very last words of the read-only-memory region of the address space of the minimal Hawk.
Assemblers can do much more than merely assemble data into memory and produce pretty listings. One of the most important features of most assemblers is the ability to maintain, inside the assembler, a list of named variables that can be set by assembly language programs and then used, in the assembly language code, in place of explicit values. The simplest use of such variables is as symbolic names for constants:
1 ; Some constants 2 ZERO = 0 3 ONE = 1 4 TEN = 10 5 HUNDRED = 100 6 7 ; Using these constants +000000: 00 8 B ZERO +000001: 01 9 B ONE +000002: 0A 10 B TEN +000003: 64 11 B HUNDRED +000004: 000B 12 H TEN + 1 +000006: 005B 13 H HUNDRED + (ONE - TEN) 14 15 END |
In this assembly listing, note the use of the equals sign to assign values to named variables inside the assembler. Later, when these variables are used as operands on the B, H and W directives, their values are retrieved from inside the assembler and placed in memory.
Furthermore, note that the assembler is perfectly happy to perform simple arithmetic operations on these values. This arithmetic is done by the assembler, and it is the results of these arithmetic operations that are placed in memory.
Finally, note that this example did not set the location counter before starting to assemble values into memory. This means that the assembler does not know where these values should be put in memory, but only that they should be put in consecutive memory locations. This is why the assembler listing contains a plus sign before each memory address in the left-hand column. These plus signs indicate that these addresses will be relocated by adding some as-yet unknown value, the relocation base, when this data is actually loaded in memory.
Exercises
i) Give appropriate definitons, as named constants, for the ASCII control characters BEL, HT, LF, FF and CR. (The binary values of the representations for these characters can be found in Chapter 2.)
j) Give appropriate definitons, as named constants, of the symbols MAXROM, MINRAM and MAXRAM for the minimal Hawk memory address space.
So far, all of our examples have involved assembly of numbers into memory, using either base 10, other bases, or the values of assembly-time variables. We can also assemble characters and strings into memory!
+000000: 61 1 B 'a' +000001: 62 2 B 'b' +000002: 63 3 B 'c' +000003: 64 4 B 'd' +000004: 61 62 63 64 5 ASCII "abcdefgh" 65 66 67 68 6 END |
The first 4 bytes assembled in the above example are given as operands to single B directives. The final 8 bytes are given by the text string that is used as an operand on the ASCII directive. This directive takes a text string as an argument and assembles the consecutive characters of that sting one at a time, as if they had been operands on individual B directives. Note how the assembler lists all of the bytes assembled by ASCII directive, 4 per line, so that you can see the sequence of consecutive values, in hexadecimal, that are used to represent the string.
Note also that the assembler does not impose any convention for indicating the length of the string! In practice, every high level programming language uses such a convention, but the basic idea of data abstraction is that programmers should not need to concern themselves with the details of the representation of abstract data types. Assembly language programmers, though, must always be concerned with these details!
One way to represent the end of a string is to use a special reserved value. The C programming language, for example, uses the value zero for this. An assembly language programmer wishing to use this convention would have to provide an explicit zero at the end of each string, as illustrated in the following example:
1 NULL = 0 +000000: 61 62 63 00 2 ASCII "abc",NULL +000004: 61 3 B 'a' +000005: 62 4 B 'b' +000006: 63 5 B 'c' +000007: 00 6 B 0 |
In the above, note that naming a constant such as NULL offers a way to make the null termination on the string stand out, but it is exactly equivalent to using a numeric zero, so long as we define NULL appropriately. Furthermore, we can include the string terminator on the same line as the string itself, using the ASCII directive, or we can use a separate B directive to assemble this byte on a line by itself. The results that land in memory using these two approaches are identical!
Exercises
k) Give SMAL assembly code to assemble the null-terminated string "Hello World!" into memory.
l) Give SMAL assembly code to assemble the null-terminated string "Hello World!\n" into memory, making appropriate use of named constants for the control characters.
It is always possible to count the bytes in a data structure by hand in order to find the memory address of part of that structure, or in order to record, in that structure, the size of that structure, but this is very inconvenient. Consider, for example, the problem of working with character strings. As mentioned above, one obvious way to deal with strings is to mark the end of each string object with a special character such as null. There is an obvious alternative to this: Store the length of the string with the string, so that string variables are represented by a variable containing the length of the string, followed by the sequence of bytes making up that string. Unfortunately, this is clumsy, because for each string constant in an assembly language program, the programmer is forced to count the characters in that constant, as illustrated below:
+000000: 0006 1 H 6 +000002: 61 62 63 64 2 ASCII "abcdef" 65 66 +000008: 0003 3 H 3 +00000A: 61 62 63 4 ASCII "abc" |
In the above example, there are two string constants, that is, constants representing objects of the class string, where we assume that each string object begins with a halfword holding the length of the string followed by that many characters. One of these string objects is stored in memory locations 0 to 7, while the other is stored in memory locations 8 to 12.
This is perfectly workable, until it comes time to add a character to one of these string constants because, as it turned out, one of them had the wrong value. Once this is done, the characters in that string must be counted and properly recorded in the previous byte, but also, the addresses of each string that follows must be adjusted! This is all clerical work, and naturally, we expect computers to do our clerical work for us.
In assembly languages, we typically do this by providing a way for the assembler to record the value of the location counter in one of the assembler's named variables, and then we can use this recorded value in expressions, as needed, in order to do this clerical work. Two ways of doing this for the above example are given below:
1 S1 = . +000000: 0006 2 H S1ETX - S1STX 3 S1STX = . +000002: 61 62 63 64 4 ASCII "abcdef" 65 66 5 S1ETX = . 6 +000008: 0003 7 S2: H S2ETX - S2STX +00000A: 61 62 63 8 S2STX: ASCII "abc" 9 S2ETX: |
Note that the above example puts exactly the same data in exactly the same memory locations as the previous example, and note that it does it without once requiring the programmer, in the source text, to count the characters in the string.
In the first string, we define the values of 3 variables within the assembler, S1, S1STX and S1ETX. Each of these variables is defined by assigning it the value of the special symbol . (period), and this has exactly the meaning it has when it occurs on the left-hand side of the assignment. That is, it is the name, in our SMAL assembly language, for the location counter. So, the assembly-time variable S1 ends up holding the address of the entire object representing the first string, while S1STX ends up holding the address of the start of the text of the actual string, and S1ETX ends up holding the address immediately after the end of the text of that string. As a result, the difference between S1ETX and S1STX is the length of the string, in bytes, and this is the value we store in the first halfword of the object.
The second string above uses the names S2, S2STX and S2ETX to mean exaclty the same things, but it defines them using a different and more compact syntax. When an identifier in the SMAL assembly language is followed by a colon, we say we are using that identifier as a label. When a label is used this way, the variable inside the assembler associated with the label is given, as its value, the value of the location counter at that point.
There is one important difference between using the equals sign to assign a value to an assembly time variable, and using the same identifier as a label. Once a variable within the assembler has been given a value by use as a label, that value may not be changed. In contrast, variables given values by assignment may be redefined elsewhere, which is to say, they are true variables.
Exercises
m) Give SMAL assembly code to assemble the string object "Hello World!" into memory, using a halfword prefix on the string to hold the string length. Do this making full use of the assembler to do the required clerical work.
n) Give SMAL assembly code to assemble the string object "Hello World!\n" into memory, using a halfword prefix on the string to hold the string length. Do this making full use of the assembler to do the required clerical work.
In looking at the examples above, it is fair to ask, if the assembler reads the source file sequentially, how is it possible to use the value of a symbol such as S1ETX or S2ETX before the point where that symbol is given a value? The answer to this is simple! The SMAL assemlber, like most assemblers, does not read the source file just once, it reads it twice. Conceptually, you can think of it reading the file once to collect the values of all symbols, that is, of all named variables inside the assembler, and then a second time to use those values, but the story is somewhat more complex, as is illustrated by the example below:
+000000:+00000008 1 W XXX 2 XXX = . +000004:+00000004 3 W XXX 4 XXX = . +000008:+00000008 5 W XXX |
In the above example, the uses of XXX on lines 3 and 5 put into memory the values you would expect, that is, the values assigned to XXX most recently, so line 3 uses the value assigned on line 2, and line 5 uses the value assigned on line 4. The puzzling question is, where did the value used on line 1 come from? The answer is, it is the value that was assigned on line 4, which is to say, the final value that was assigned during the first pass through the source file.
This entire issue rarely matters, first because all labels are assigned a value exctly once, and second because most other symbols used by a typical assembly language programmer are really being used as constants, despite the fact that our assembler allows them to be redefined. The example above is very artificial!
Exercises
o) Figure out (by hand) what values should end up in memory when the following very artificial bit of SMAL code is assembled:
B XXX + YYY XXX = 1 B XXX + YYY YYY = 2 B XXX + YYY XXX = 3 B XXX + YYY YYY = 4 B XXX + YYY
In the discussion of words and halfwords at the start of this chapter, we emphasized that the Hawk architecture requires word and halfword values in memory to be properly aligned, so that halfwords must begin at even addresses and words must begin at addresses that are divisible by 4. All of the examples given above have this property, but that is because they were carefully constructed!
In fact, the Hawk assembler does nothing to help assure this, as is illustrated by the following example:
+000000: 00 1 B #00 +000001: FFFF 2 H #FFFF +000003: AAAAAAAA 3 W #AAAAAAAA |
In this example, the assembler stores the halfword holding FFFF16 in locations 1 and 2, and it stores the word holding the value AAAAAAAA16 in locations 3 through 6. The resulting data ends up being put in memory as follows:
31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 | 15 | 14 | 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
In theory, it is possible for an assembly language programmer to count bytes carefully and add extra bytes or halfwords as padding in order to assure that data is correctly aligned in memory, but in practice, this is a tedious clerical job, and clerical work is best left to the computer.
Some assemblers have tools for aligning data built into them, but in the case of the SMAL assembler, this is not built in. Instead, we use a far more powerful tool, a macro, to solve this problem. Macros are directives that are not built-in parts part of a computer language, but rather, they are defined by a program in that language as an extension to the language. Although macros were originally invented as an augmentation to assembly languages, they are now commonly used in many other contexts.
To solve the alignment problem, we define a macro called ALIGN that takes, as an argument, the alignment constraint. Once a macro is defined, we can use ALIGN as if it was a normal directive in our assembly language. The ALIGN macro is defined in the standard header file that all SMAL programs for the Hawk computer will include, and once this header file is properly included, alignment can be properly assured as follows:
1 USE "hawk.macs" +000000: 00 2 B #00 3 ALIGN 2 +000002: FFFF 4 H #FFFF 5 ALIGN 4 +000004: AAAAAAAA 6 W #AAAAAAAA |
Line 1 of the above example imports the complete set of definitions required to customize the SMAL assembler for use with the Hawk computer architecture. The sequence of byte, halfword and word directives given in this code is identical to that in the previous misaligned example, but now, the halfword is preceeded by ALIGN 2 and the word is preceeded by ALIGN 4. The ALIGN macro advances the location counter as needed to assure that it is divisible by correct power of two. In this case, ALIGN 2 had to advance the address by one to force it to be even, but at the point where ALIGN 4 was used, the address was already divisible by 4 so the ALIGN directive had no effect. The above fragment of assembly code ends up packing data in to memory as follows:
31 | 30 | 29 | 28 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 | 15 | 14 | 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 | 00 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||||||||
1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
Beware! When the ALIGN directive causes a byte or two or three of memory to be skipped over, that byte ends up containing an uninitialized value. Later on, if you happen to examine those bytes, there is no guarantee what value you will find there.
Exercises
p) Add the minimum number of ALIGN directives needed to make the following example assemble in a useful way for the Hawk computer:
B 1 W 2 B 3 H 4 W 5q) When the above example is assembled, which lines produce misaligned results.
r) Show the result of assembling the above example into memory, in binary, without any align directives, so that misaligned data is stored in a difficult to use form.
s) Show the result of assembling the above example into memory, after appropriate alignment directives have been added. Show uninitialized bits as blanks.
t) Give a complete set of rules that tells whether to insert an ALIGN directive between two successive data storage directives such as B, W, H and ASCII. Your rules should be expressed as a table, where rows correspond to the first directive in the sequence and columns correspond to the second directive in the sequence, where the table entry tells you whether or not to use an ALIGN.