3. Memory, Architecture and Assembly

Part of 22C:60, Computer Organization Notes
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Overview

In 1946, Burks Goldstine and Von Neumann published their seminal report Preliminary discussion of the logical design of an electronic computing instrument. While some details of the system they proposed look quite strange from today's perspective, their overall proposal shows what is now the common model for a computer system, and it is well developed. For this reason, it is common to refer to this model as the Von Neumann model of computing. Of course, the technology with which they proposed to implement this model looked primitive even by the standards of the early 1960's; the machine was, after all, proposed before the transistor was even invented, but it was on the cutting edge of what was possible in the late 1940's. Now as then, we think of computers as having the following basic components:

The Von Neumann model of a computer
Central Processing Unit
CPU
 
Registers
 
 
            Interface(s) or Bus(ses)            
 
Memory
 
Input
Output

Central Processing Unit or CPU
Today, as in the original proposal, this component does all of the active computation, directing the movement of data between the other components and doing most of the computations. Since 1960, computers with multiple CPUs have been built, and computers have been built with auxiliary processors, sometimes called coprocessors, but for now, we will ignore these.

Registers
Today, as in the original proposal, the CPU must contain several registers. Some of these hold intermediate results for computations that are currently in progress, and some of them hold information about what computation is to be done next in the sequence of computations that makes up the program being executed. Todays CPU design have more registers and more flexible registers than the computers of the 1940's, but the basic idea has not changed.

Interfaces or Bus
Today, as in the 1940's, the CPU must be connected to additional system components. In early machines, there were no general-purpose interconnection structures, but by the 1960's, it was obvious that standard busses (a term from 19th centur electrical engineering) should be designed to allow any of a number of components to be connected to the CPU using plug-compatable connectors. Some computers have just one bus to which any memory or input-output device may be connected, while others have multiple busses, some for memory, some for fast devices, and others for slow devices.

Memory
Today, as in the 1940's, the single most important component of the computer system, outside the CPU, is the main memory, also referred to as the random-access memory or RAM. Many different technologies have been used for main memory, from vacuum tubes to magnetic drums to magnetic core memory to semiconductor RAM, but from the machine-language programmer's perspective, there has been little change except in memory size and speed. From this perspective, the main memory has always appeared to be a linear array of memory locations, each able to hold the value of one simple variable or one machine instruction.

Input Output Devices
Today, as in the 1940's, computers would be of no use without some way to interact with the outside world. We need keyboard input and some kind of display or printer device, and depending on the application, we may need many other devices. The use of some devices as auxiliary memory was anticipated from the dawn of the computer age in the 1940's, althoug the details of such memories have changed greatly.

Here, 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 addressing.

Memory Resources

Most general purpose computers designed since 1970 have had similar basic memory formats, and since 1980, most general purpose computers have been 32-bit computers, like the Hawk. One big distinction divides these 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 trouble.

Divisions of a Hawk 32-bit word
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 assigns 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. The Hawk memory addressing scheme does not allow individual bits of memory to be given distinct addresses. As with most other computers, if you want to set, reset or test a single bit, you must do this with arithmetic or logical operations, a subject we will discuss at length, later.

The Hawk memory seen as an array of 8-bit 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:

The Hawk memory seen as an array of 16-bit 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.

The Hawk memory seen as an array of 32-bit words
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:

The Hawk memory seen as bytes, halfwords and words
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

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 4,294,967,296 used above is 232 or 1,0000,000016, and the rules of C and C++ for arrays say that the legal range of subscripts for the resulting array runs from 0 to 4,294,967,295 which is 232-1 or FFFF,FFFF16. This is identically the same as the range of legal unsigned integer values that can be represented in a 32-bit word.

There are some 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 Objective C gives 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.

A Hawk memory address

A Hawk memory address
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 two least significant bits, the byte-in-word field, will be ignored and treated as if they were all zero. If the memory address is being used for a half-word operand, the least significant bit will be ignored and treated as zero, so 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 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 force a trap, the hardware term for throwing an exception.

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, as used here, conforms to this model. Read-only memory starts at byte zero of memory and runs up to byte 0000,FFFF16, and read-write memory running from byte 0001,000016 to 0001,FFFF16. In this minimum configuration, locations 0002,000016 to FEFF,FFFF16 are unimplemented. Locations FF00,000016 and up are even stranger; these are reserved for input-output interfaces; while these locations are accessed as if they are memory, accessing them causes side effects such as the output to the display screen; we will ignore this part of memory until later.

 
The minimal Hawk memory address space
                          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? How many bytes are in this region? How many words?

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? How many bytes are in this region? How many words?

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? How many bytes of additional memory would be required to fill this this region? How many words is this?

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? How many bytes are in this region? How many words?

Memory Addresses

Non-aligned data

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.

The SMAL Assembler

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, although there are exceptions. Instead, they are coded in a binary object code or a textual assembly code, ready for processing by later steps on the road to an executable 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, although, again, there are exceptions; instead, it is usually encoded in a binary object code.

A Linker
Linkers take, as input, the object code for the different components of a program. For the simplest programs, there is no need for a linker, but for most interesting 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. Relocation of a file involves deciding where to place the instructions and variables in memory.

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:

A small example of SMAL assembly code
        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:

Partial assembly of the example into memory
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:

Completed assembly of the example into memory
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:

Rewriting the example so it assembles into locations 100 to 107
.       =       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:

Rewriting the example for improved readability
        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:

The assembly listing for the example
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; only the least significant 24 bits of the memory address are shown because single source files that assemble to more than 16 million bytes are extremely unlikely.

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 printing assembly listings, also use a fixed width font!

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.

Named Constants

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 identifiers 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 identifiers is as symbolic names for constants:

An assembly listing using named 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 identifiers inside the assembler. Later, when these identifiers are used as operands on the B, H and W directives, their values are retrieved from inside the assembler and placed in memory. The lines that define these identifiers do not assemble anything into memory; their impact is entirely confined to the assembler itself.

Furthermore, note that the assembler is perfectly happy to perform simple arithmetic operations on these values, as illustrated in lines 12 and 13 above. This arithmetic is done by the assembler itself before the results 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.

Arrays and Structures

Up to this point, we have spoken only of single values, integers and characters. In real programs, we must frequently deal with objects that hold multiple values, either selected by index, as in an array, or selected by name, as in a Java or C++ class, a C structure or a Pascal record. Consider, for example, this C declaration for an array:

A constant array, declared in C
const int a[2][3] = {{00,01,02},{10,11,12}};

The object a declared here is an array containing two elements, a[0] and a[1]. In turn, each of these is an array of three integers. The initial values for each of the integers given in this example are very artificial; they are set up so that for each array element a[i][j], the value is 10i+j. So, for example, a[1][2], has the value 12.

Arrays, in computer's memory, are nothing more than repeating patterns of memory usage in consecutive memory locations. So, where a single integer variable is represnted by one word, an array of 3 integers will be a block of three consecutive words. If we need to create an array of n objects where each object occupies m words, we will simply use a block of n×m consecutive words. Therefore, our constant array of 2 3-word objects will occupy 6 consecutive words of memory, and we could create this in the SMAL assembly language as follows:
A constant array, in SMAL
+000000: 00000000            1  A:      W       00      ; A[0][0]
+000004: 00000001            2          W       01      ; A[0][1]
+000008: 00000002            3          W       02      ; A[0][2]
                             4  
+00000C: 0000000A            5          W       10      ; A[1][0]
+000010: 0000000B            6          W       11      ; A[1][1]
+000014: 0000000C            7          W       12      ; A[1][2]

Note that nothing in the actual assembly language code hints at the fact that the six words of memory used here have any structural relationship to each other. This is only documented in the comments, and it would be perfectly legal to omit these comments and write the code compactly as a single uncommented line of assembly code:
A poorly documented array, in SMAL
+000000: 00000000            1  A:      W       00,01,02,10,11,12
         00000001
         00000002
         0000000A
         0000000B
         0000000C

Any detailed discussion of how array elements are accessed must await a discussion of the instruction set of the computer being used, but it should be easy to see that, in any array, the address of an array element is computed from the address of the first element of the array plus a displacement, where this displacement is the product of the subscript times the element size. For our example array A, composed of 2 elements of 12 bytes each (3 words of 4 bytes each), the address of the start of A[i] is A+12i, assuming that the array A begins at address A.

A programmer is more likely to be interested in finding the address of the integer array element A[i][j]. To find this, we begin with the address of the first element of the row, A[i], and add to this the displacement into the row, j times the size of one row element, which is 4 bytes. Thus, the address of the array element A[i][j] is A+12i+4j.

When an object is composed of a number of fields, as in a C or C++ structure, a Pascal record or a C++ or Java object, these fields are simply stored consecutively in memory. Thus, for example, consider an object consisting of an integer representation of a color associated the coordinates a spot on the display screen. An array of two of these objects might be represented in assembly language as follows:
A constant array of two structures, in SMAL
                             1  RED     =       1
                             2  GREEN   =       2
                             3  BLUE    =       3
                             4
+000000: 00000001            5  A:      W       RED     ; A[0].color
+000004: 0000000A            6          W       10      ; A[0].coord.x
+000008: 00000014            7          W       20      ; A[0].coord.y
                             8  
+00000C: 00000003            9          W       BLUE    ; A[1].color
+000010: 00000019           10          W       25      ; A[1].coord.x
+000014: 0000000C           11          W       12      ; A[1].coord.y

As with the array example, notice that nothing in the assembly language itself explains how these six words of memory are structured. That information is contained in the comments, and it is contained in the code to access the elements of this data structure.

 

Text -- Arrays of Characters

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!

An assembly listing using characters and strings
+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!

From the perspective of the organization of the data into memory, a character string is nothing other than an array of characters, with one byte allocated for each array element. As with all other data structuring, the organization of the data in memory contains no record of which bytes are associated with each other as parts of a structure and which bytes stand alone as independent objects. The code that uses the data must impose this structure, and in well written programs, the organization of the data will be documented with appropriate comments.

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:

An assembly listing demonstrating null-terminated strings
                             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.

Labels

It is always possible to count the bytes in a data structure or program by hand in order to find the memory address of part of that structure or program, or to find its size, but this is very inconvenient. Consider the problem of working with character strings. As mentioned above, one obvious way to record the length of a string is to mark the end with a special character such as null. An obvious alternative to this is to store the length of the string with the string, so that each strings is represented by a memory location containing its length followed by the characters of the string. If the programmer was forced to count the characters in each string constant, as illustrated below, this would be very clumsy:

Hand counted characters in strings
+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 workable, but if one of these string constants must be changed, for example, because it had the wrong value, the programmer must count the characters all over again, and with each change in the size of a string constant, the addresses of all of the following objects in the program will change. This is all clerical work, and if we leave it to the programmer, we expect errors; as with other clerical jobs, what we want to do is automate it.

In assembly languages, we typically do this by providing a way for the assembler to bind the value of the location counter to an identifier, 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, one using the notation we have already been using to bind values to identifiers, and one using a new notation that has the identical effect but allows the identifier definition to be placed on the same line as the data storage directive:

Using the assembler to count the characters
                             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 identifiers within the assembler, S1, S1STX and S1ETX. Each of these identifiers 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 identifier 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. (If you didn't guess this, note that the abbreviations STX and ETX are commonly used for start of text and end of text; these are the names of two of the more obscure ASCII control characters.)

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 identifiers 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 identifier and using the same identifier as a label. Once an identifier has been given a value by use as a label, that value may not be changed. In contrast, identifiers given values by assignment may be redefined elsewhere, which is to say, they are variables whose values are stored within the assembler itself.

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.

Two-pass assembly and the scope of definitions

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 identifiers, and then a second time to use those values, but the story is somewhat more complex, as is illustrated by the example below:

An assembler listing demonstrating some consequences of two-pass assembly
+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
        

Alignment in Assembly Language

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:

An assembler listing demonstrating badly misaligned data
+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:

Assembly of the misaligned data into memory
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:

Assuring proper alignment
                             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:

Assembly of the aligned example into memory
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       5
        

q) 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.