3. Memory, Architecture and Assembly

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 century electrical engineering) could be designed to allow any of a number of components to be connected to the CPU using plug-compatable connectors. Some computers have been built with just one bus to which all components are connected, while others have separate busses for memory, fast devices, and slow devices.

Memory

Today, as in the 1940's, the main memory is the single most important component of the computer system, outside the CPU. The main memory is also called random-access memory or RAM. Many different technologies have been used for this, from vacuum tubes to magnetic drums, magnetic core memory and semiconductor RAM. Aside from changes in size and speed, all main memory technologies appear to the programmer as a linear array of memory locations, each able to hold the value of one simple variable or (part of) 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. At minimum, we might want a keyboard for input and some kind of display or printer, but the details depend on the application. The use of auxiliary storage devices was anticipated in the 1940's, althoug the devices available have changed greatly over the years.

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

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

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

Whether memory is viewed in terms of bytes, halfwords or words, the memory addresses are always the address of the first byte in the given unit, so word 0 contains halfwords 0 and 2 or bytes 0 to 3. Word 4 contains halfwords 4 and 6 or bytes 4 to 7. Word 8 contains halfwords 8 and 10 or bytes 8 to 11.

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 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 2³² or 1,0000,0000₁₆, 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 2³²-1 or FFFF,FFFF₁₆. 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).

Conceptually, the most significant 30 bits of the address give the word of memory being addressed, while the least significant two bits give the halfword and byte being addressed.

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 32-bit computers are 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.

It is important to understand that an illegal or unimplemented address is still and address. Our computer has exactly 4,294,967,296 distinct addresses, no matter how many of these addresses are associated with working memory or other devices.

The physical memory devices attached to 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. These acronyms are somewhat archaic, since ROM is also a form of random-access memory and these days, it is common to find the ROM replaced by flash memory, which is not really read-only, since blocks of flash memory can be erased and rewritten. 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,FFFF₁₆, and read-write memory running from byte 0001,0000₁₆ to 0001,FFFF₁₆. In this minimum configuration, locations 0002,0000₁₆ to FEFF,FFFF₁₆ are unimplemented. Locations FF00,0000₁₆ and up are even stranger; these are reserved for input-output interfaces; while they 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

Many modern computers have the same address structure as the Hawk. The Power PC and the Pentium also have 32-bit addresses, as does IBM's Enterprise Server architecture. All of these have similar schemes for packing bytes into a word. Other architectures have different address structures. The old DEC PDP-8 had a 12-bit address where each of the 4096 distinct addresses was associated with a 12-bit word in memory. The DEC PDP-11 had a 16-bit address where each of the 65,536 addresses was associated with a byte in memory and consecutive pairs of bytes were used to represent 16-bit words.

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 tries to read from a non-aligned word or halfword, the central processor automatically reads the two words containing the 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 never allocate space for variables that is not properly aligned. Because of this, some computers, including the Hawk, don't even bother supporting non-aligned data.

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?

The SMAL Assembler

So far, we have described the memory of the computer as an array of bytes, where these can be grouped by twos and described as an array of halfwords, or by fours and described as an array of fullwords. Next, we will discuss 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 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 first high-level language to see much use, starting in 1956) or Java (a much younger language, dating to 1995). Each compiler translates its input language to sequencees of macine instructions. These could be put in main memory, ready to execute, but usually, they are saved as 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 the contents of memory in human-readable form. 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 most details of constructing specific binary encodings for the machine instructions and constants to be loaded in memory. The output of the assembler could be placed directly in memory, but again, it is usually saved as a file, 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 ; byte 0 B -1 ; byte 1 H #0F0F ; bytes 2 and 3 W 8#12525252525 ; bytes 4, 5, 6 and 7

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, and comments follow the semicolon on the line. 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:

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. Most assembly code specifies a sequence of data values to be loaded into consecutive locations in memory, without specifying which loctions are to be loaded.

Our assembly language allows specificaiton of the assembly origin, the starting address for assembling the data that follows. For example, if we wanted the code shown above to be stored consecutively starting with byte 100₁₀, we would add one line to the example:

Rewriting the example so it assembles into locations 100 to 107

. = 100 ; set origin to location 100 (decimal!) B 0 B -1 H #0F0F W 8#12525252525

By way of explanation, most of the code in the above example directs 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 a strange name, . (a period). This variable is the assembler's location counter; it tells the assembler where the next byte, halfword or word will be placed in memory. When the assembler assembles a byte, it puts it in the one-byte location referenced by the location counter and then increments the location counter by one. When the assembler assembles a halfword, it puts it in two consecutive bytes, incrementing the location counter by two. Words are assembled into four consecutive bytes, incrementing the location counter by four.

As with any programming language intended for human readers, our assembly language allows comments, blank lines and other features that improve the readability of assembly language documents:

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 document 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 12525252525₈.

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 have been set by the assembly language program so that later parts of the assembly language code, can use these 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. When these identifiers are used as operands on the B, H and W directives, the values assigned to them are retrieved by the assembler and placed in memory. The lines that define these identifiers do not assemble anything into memory; rather, they change values in 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 sequences of objects of the identical size and usually identical type stored in 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 two 3-word objects will occupy 6 consecutive words of memory, and we could create and initialize this array 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 discussion of how array elements are accessed must await discussion of the instruction set of the computer. Accessing an array element begins with computing its memory address. We start with the address of the first array element and add a displacement that is the product of the array subscript and the element size. For the example array A, each element is 3 words or 12 bytes long, so the address of the start of A[i] is A+12i. To find the address of the one word array element A[i][j], 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, 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 associating a color with the coordinates of a spot on the display screen. If we encode colors as integers, 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 will be contained in the code to access the elements of this data structure.

Text -- Arrays of Characters

So far, our examples have all involved assembly of numbers into memory, using several number bases and using 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

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 whether to find the memory address of part of it, or to find its overall size, but this is dull work. Consider the problem of working with character strings. As mentioned above, we can mark mark the end of each string 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, as illustrated below:

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 each begins with a halfword holding the string length 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 works until one of the string constants needs changing. To change a constant, 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 should expect errors.

Computers are good at automating such clerical work. Assembly languages typically do this by providing a way for the assembler to recall the value of the location counter, binding it to an identifier that can be used when needed later. 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), which stands for the location counter. Earlier, we assigned to this symbol to set 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 the same things with regard to the second string, 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 is constant and the value may not be changed. In contrast, identifiers given values by assignment may be redefined elsewhere, which is to say, they are potentially variables within the assembler that may be changed.

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:
 

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 in a typical assembly language program are used as named constants that are defined or redefined before their point of use.

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!

The Hawk assembler itself 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 FFFF₁₆ in locations 1 and 2, and it stores the word holding the value AAAAAAAA₁₆ 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 built-in tools for aligning data, 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, use a macro called ALIGN. This takes an argument giving the alignment constraint, the number by which the address should be divisible. ALIGN is defined in the standard header file hawk.macs used for the Hawk computer. The most common place you will need to use the ALIGN directive is in data between small objects such as bytes or halfwords and larger objects that follow, such as machine instructions, halfwords or words. Always align to the size of the following object, as illustrated below:
 

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

 
The USE directive on line 1 above imports a file of definitions that customizes the SMAL assembler for use with the Hawk architecture. The sequence of byte, halfword and word directives given above is the same as 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 make it divisible by correct power of two, leaving intervening memory locations undefined. In this case, ALIGN 2 advanced the address by one, but at the point where ALIGN 4 was used, the address was already divisible by 4 so the alignment had no effect. The result is that data is packed into 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 with an uninitialized value. There is no guarantee what value you will find there. This means you should never use an align directive between executable machine instructions. Forgotten or misplaced align directives in an assembly language program can be difficult to debug. The basic rule is simple: Worry about alignment whenever smaller objects are followed by larger ones.
 

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 alignment 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 the complete rules that tell whether to insert an ALIGN directive between two successive data storage directives (any of B, W, H and ASCII). Your rules should be given as a table, where rows correspond to the first directive in the sequence and columns correspond to the second; each the table entry should tell what ALIGN directive to use.