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. Some details of their proposed design look strange from today's perspective, but their overall proposal includes all of the essential parts of a modern computer. For this reason, we say that modern computers follow the Von Neumann model of computing. Of course, the technology they proposed to use looked primitive even by the standards of the early 1960s; the machine was, after all, proposed before the transistor had been invented, but it was implementable using technologies known during World War II. 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, the CPU does most of the computation and directs the movement of data between the other components. Multi-CPUs computers were first made in the 1960s and are now common; coprocessors also originated in the 1960s. We will ignore these extras until later.

Registers

Today, as in the original proposal, the CPU must contain several registers. Some registers hold intermediate results, others hold information needed to control the sequence of computations in the program being executed. Todays CPU design have more registers and more flexible registers than the computers of the 1940s, but the basic idea has not changed.

Interfaces or Bus

Today, as in the 1940s, the CPU must be connected to other system components. At first, there were no general-purpose interconnection structures, but by the 1960s, it was obvious that standard busses (a term from 19^th century electrical engineering) could be designed to allow the CPU to communicate with multiple components. Some computers have been built with just one bus connecting all components; others have multiple busses, for example, one for memory and one for input-output.

Memory

Today, as in the 1940s, computers store running programs and their variables in main memory, also known as random-access memory or RAM. Many technologies have been used: Williams tubes, accoustic delay lines, magnetic drums, core memory and semiconductor RAM. Whatever their size or speed, all main memory technologies implement an array of memory locations indexed by integer memory addresses.

Input Output Devices

Today, as in the 1940s, computers would be useless without a way to interact with the outside world. Depending on the application, a keyboard and display might be the bare minimum. Auxiliary storage devices such as disks were anticipated from the start, and the variety of devices has grown immensely.

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 memory models, and since 1980, most have used 32-bit words, like the Hawk, or even 64-bit words. 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 – these are described as lowbyters or littleendian machines. The Hawk is a lowbyter, as is the Intel Pentium. There is little reason 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 operations on larger chunks such as bytes or words, we will discuss at length later.
 

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

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

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, 1, 2 and 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 . . .

Memory Addresses in C

C (and C++) allow you to declare variables that hold a memory address. These are called pointer variables or just pointers. The most common use of pointers in C is as handles on objects, but they have other (and more dangerous) uses. Because memory may be viewed as an array of bytes, an array of halfwords, an array of words, or other data types, C requires you to declare the type of the object you are referecing with a pointer.

Declaring pointers in C

void* a; /* points to an object of unspecified type */ char* b; /* points to a character (a byte?) */ short int* c; /* points to a short integer (a halfword?)*/ int* d; /* points to an integer (a word?)*/ long int* e; /* points to a long integer (a double word?)*/ #include <inttypes.h> uint8_t* f /* points to an unsigned byte */ int16_t* g /* points to a signed halfword */ uint32_t* h /* points to an unsigned word */

Notice the special data type void. Many programmers are familiar with the concept of a void function or void method in languages such as Java. That is just a way of declaring a subroutine that returns nothing in languages such as C and Java where all routines must have a declared return type. In C (and C++), void is also a data type. A variable of type void is useless because it can't hold a value. Void pointers are useful because they carry a memory address without offering a clue about the data stored at that address.

Of course, pointers wouldn't be very useful without some way to initialize them. The simplest tool for this is the C address of operator & (ampersand). If i is an integer variable, for example, &i is the address of i, a value of type int*. Beware, here we are using & as a prefix operator. If you write i&j, it has a completely different meaning.

We have already used pointers of type char* as handles on strings, and we have noted that if b is of type char*, it is legal to write b[i], where pointer b points to the first character in a string and b[i] selects a character from the string. Now, consider an example using integers and integer pointers:

Exploring memory with integer pointers

/* intpoint.c -- a program to explore memory with integer pointers */ #include <stdio.h> int a[3] = {1, 2, 3}; int main( void ) { int* p = &a[1]; /* pointer to the middle integer */ printf( "p[0] = %d\n", p[0] ); printf( "p[1] = %d\n", p[1] ); printf( "p[2] = %d\n", p[2] ); return 0; }

Here, we created a global array a of three integers, initialized to the 3 consecutive integers 1, 2 and 3. Inside our main function, we have a local variable, the integer pointer p that is initialized to point to the middle array element — in C, all arrays begin at element zero. The program then uses p as a pointer to an array of integers and prints its first 3 elements.

If you run this program, you should not be surprised to find that p[0] is the same as a[1] and p[1] is the same as a[2]. The puzzle is, what is p[2]? Nothing in this program determines a value for p[2]. It is simply the value stored in the next int sized chunk of RAM after the array a. C (and C++) let you do this, while languages like Java and Python do not permit anything like this kind of unsafe programming.

Note that instead of p[0], we could also have written *p, which means, simply, get the int from the RAM location pointed to by p. This is called dereferencing the pointer. The asterisk, as a prefix operator, is C's dereferencing operator.

C allows us to do things that are even stranger. In C, the type of a pointer can be changed by casting. So, if you have a pointer pi that points to an integer, you can treat it as a character pointer by using (char*)pi. The following program illustrates this:
 

Exploring integers seen as characters

/* intcast.c -- a program to explore casting integers as characters */ #include <stdio.h> int main( void ) { int a = 0x41424344; char* p = (char*)&a; printf( "p[0] = 0x%02X = '%c'\n", p[0], p[0] ); printf( "p[1] = 0x%02X = '%c'\n", p[1], p[1] ); printf( "p[2] = 0x%02X = '%c'\n", p[2], p[2] ); printf( "p[3] = 0x%02X = '%c'\n", p[3], p[3] ); return 0; }

Here, because p is a character pointer, p[0] (which could have been written *p refers to just one byte, and p[1] refers to the next consecutive byte in memory. Each call to printf in this program prints one element of the array of characters pointed to by p. Each element is printed twice, so the format string contains two format specifiers. The %02X format specifier asks the character to be printed as two hexadecimal digits, using upper-case letters, and with no suppression of leading zeros, and %c asks for it to be printed as a character.

This program could produce two possible results when you run it, depending on whether the computer you run it on is a highbyter or lowbyter. The program also demonstrates how using hexadecimal neatly aligns the data with the four bytes of the word.

Memory Addresses on the Hawk

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. It does not allow halfword and word addressing, and with many compilers, if you tried to declare this array in a real program, you would get an error message such as "size of array 'memory' is too large" (that is the message Objective C gave 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, many 32-bit computers are configured with less 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 may be connected to physical memory. We say that the remaining addresses are unimplemented; if they are used by a program, the hardware will typically force a trap, the hardware term for throwing an exception.

Note 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 are associated with working memory or other devices.

To address more than 4 gigabytes of memory, a computer must either have a larger word size, or it must use special hardware called a memory management unit (MMU) that can translate 32-bit addresses to something larger. Almost all modern computers have MMUs, not only because of the support they offer for larger memory address spaces, but because they can be configured to protect memory against misuse by faulty or rogue applications. See Chapter 14.

The actual memory devices attached to different memory addresses need not be identical. Some parts of the memory address space may be populated by read-only memory, or ROM, while other parts of the address space may be populated by read-write memory, or RAM. These acronyms are somewhat archaic: ROM is also a form of random-access memory, and sometimes, ROM is replaced by by electrically erasable programmable ROM or EEPROM, where the computer can change the contents. Flash memory is a kind of very fast EEPROM. To add to the confustion, some memory addresses may be used for input-output device interfaces that do not behave anything like memory.

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 runs 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 the input-output addresses 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, the Intel Pentium and IBM's Enterprise Server architecture all follow this model, with similar schemes for packing bytes into words. Other machines have used other models. For example, the DEC PDP-8 had a 12-bit address and each of the 4096 distinct addresses could hold one 12-bit word. The DEC PDP-11 had a 16-bit address where each of the 65,536 addresses could hold a byte; pairs of consecutive bytes could hold 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 reads and writes memory in terms of entire words. While programmers may think in terms of 32-bit addresses, the physical connection between the central processor and memory may use just 30 bits of address – the address of an aligned word.

On some computers, when a program reads from a non-aligned word or halfword, the central processor automatically reads the two words holding the parts of the non-aligned word. As a result, reading a non-aligned word takes twice as long as reading an aligned word. 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.

The SMAL Assembler

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 parts of the tool chain used to do this:

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 #F0F0 ; bytes 2 and 3 W 8#12525252525 ; bytes 4, 5, 6 and 7

This example tells the assembler to put 2 bytes, 1 halfword and 1 word in consecutive memory locations (a total of 8 bytes). The first byte holds a zero, given in decimal, the second byte contains –1, also given in decimal. SMAL 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 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
#F0F0																–1								0
8#12525252525

In the above, 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 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 where that sequence begins.

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 #F0F0 W 8#12525252525

The line only change from the previous example is one new line, the first line. This tells the assembler to assign the value 100 to a variable inside the assembler called the location counter, referenced by the strange name . (a period). The location counter tells the assembler where to put the next byte, halfword or word in memory. To assemble a byte, the assembler puts it in the location referenced by the location counter and then increments the location counter by one. To assemble a halfword, it puts it in two consecutive bytes, incrementing the location counter by two. Words go in 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 to improve readability:

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 #F0F0 ; 102 and 103 W 8#12525252525 ; 104 to 107 END

As already mentioned, 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, H and W directives that tell the assembler to put bytes, words and halfwords in memory, the assembler allows many other directives; 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 meet this need, most assemblers optionally produce not only an object code output file, ready for loading in memory, but also a listing file formatted to show what the assembler put in memory. When the SMAL assembler processes the above source file, it produces the following listing file:

The assembly listing for the example

SMAL32 (rev 8/11) A meaningless example 14:18:38 Page 1 Mon Aug 15 2011 1 TITLE "A meaningless example" 2 3 ; The following assembles into 100 to 107 4 . = 100 5 00000064: 00 6 B 0 ; 100 00000065: FF 7 B -1 ; 101 00000066: F0F0 8 H #F0F0 ; 102 and 103 00000068: 55555555 9 W 8#12525252525 ; 104 to 107 10 11 END

The assembler listing above contains the original source file on the right side of each page, with page headers giving the file title, page number and time and date of assembly. A column of source line numbers runs down the center of the listing. On the right, the listing shows what the assembler put in memory, with memory addresses given in hex, followed by a colon, followed by the data assembled into that address, also in hex.

The information on the left side of the listing contains much of the same information as the object code, so sometimes, people refer to it as object code. The real object code, however, is even less readable than the left side of the listing.

When editing assembly language programs, it is conventional to keep things aligned in neat columns. Conventionally, your editing window should be configured to use a fixed-width font with tabs set every 8 columns and a window 80 columns wide. Use tabs for indenting.

When debugging an assembly language program it is very convenient to keep a listing of that program on hand. In the old days, you would almost always print the listing on paper and have this on your desktop while you were debugging the code. Today, you open a window on your virtual desktop so you can look at the listing while you actually run the code in a second window. When printing assembly listing files, use a fixed-width font, and consider printing in landscape format or in a very small font so that long lines print without wrapping (allow for 80 characters on each assembly source line, plus 32 characters of text added to the left of each line).

Named Constants

In a C program, variables must be declared and given a type before they are used. Constant declarations are very similar, with the keyword const added. Initial values of variables are optional, but for constants, a value must be provided. Consider this example:

Constant declarations in C

const int five = 5; const char blank = ' ';

One of the most important features of most assemblers is the ability to maintain, inside the assembler, a set of itentifiers (symbols) and their values. The data structure inside the assembler that holds these values is called the symbol table, and in most assemblers, including SMAL, the values are one-word quantities that are usually interpreted as integers. Assembly language code may set the values of these identifers and later use those values. There are many uses for these identifiers, including building control structures, but the most elementary use for 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 +00000000: 00 8 B ZERO +00000001: 01 9 B ONE +00000002: 0A 10 B TEN +00000003: 64 11 B HUNDRED +00000004: 000B 12 H TEN + 1 +00000006: 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 later, for example, as operands on the B, H and W directives, the values assigned to them are retrieved by the assembler and used. The lines that define these identifiers do not produce any object code. Rather, they change values inside the assembler itself.

Note that the assembler can do simple arithmetic operations, as illustrated in lines 12 and 13 above. This arithmetic is done by the assembler before the results are put 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.

Arrays

To this point, we have focused primarily on single integer or character values, integers and characters. In real programs, we frequently deal with objects that hold multiple values. Fields of an array are selected by their numeric array index. Consider this example declaration of a constant array in C;

A constant array, declared in C

const int a[2][3] = {{00,01,02},{10,11,12}};

The object a declared here is a constant array containing two elements, a[0] and a[1]. Each of these is an array of three integers. The values for the array elements are very artificial. Each array element a[i][j], has the value is 10i + j, for example, a[1][2] has the value 12.

Arrays, in computer memory, are nothing more than sequences of objects of the identical size and compatible 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 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

+00000000: 00000000 1 A: W 00 ; A[0][0] +00000004: 00000001 2 W 01 ; A[0][1] +00000008: 00000002 3 W 02 ; A[0][2] 4 +0000000C: 0000000A 5 W 10 ; A[1][0] +00000010: 0000000B 6 W 11 ; A[1][1] +00000014: 0000000C 7 W 12 ; A[1][2]

Nothing in the assembly language code above hints at the fact that the six words of memory have any structural relationship. 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 code:

A poorly documented array, in SMAL

+00000000: 00000000 1 A: W 00,01,02,10,11,12 +00000004: 00000001 +00000008: 00000002 +0000000C: 0000000A +00000010: 0000000B +00000014: 0000000C

We cannot discuss how array elements are accessed until we introduce the instruction set of the computer, but accessing an array element begins with computing its memory address. To find the address of A[i][j], we start with the address of the first array element A and add a displacement that is the product of the array subscript and the element size. In this example, each element of A is 3 words or 12 bytes long, so the address of A[i] is A + 12i. To get the address of the word at A[i][j], we begin with the address of A[i], which is the start of an array of 4 byte words, so the address of the array element A[i][j] is A + 12i + 4j.

Text — Arrays of Characters

In both C and SMAL, character strings are just arrays of characters stored in consecutive memory locations. As a result, we can make two changes to the classic first C program given in the previous chapter. First, we can replace the string literal "Hello World\n" with a named string constant, and second, we can replace the string literal used to give the value of that constant with an array constant that gives each character of the string as a separate character constant. The result is as follows:

A first C program, rewritten

/* hello.c -- a variant on the classic hello world program */ #include <stdio.h> const char hello[13] = { 'H', 'e', 'l', 'l', 'o', ' ', 'W', 'o', 'r', 'l', 'd', '\n' ,'\0' }; int main( void ) { printf( hello ); return 0; }

This program means exactly the same thing as the original hello world program. Naming the string constant instead of including it as a string literal causes no change, and giving the text of the string as an explicit array also changes nothing.

As in C, string constants in the SMAL assembly language can be constructed by any mechanism that places consecutive characters in consecutive bytes of memory. We can do this with one B directive per byte, one H directive per pair of bytes, or one W directive per 4-byte sequence, but the most convenient way to form character strings is the ASCII directive, as illustrated here:

An assembly listing using characters and strings

+00000000: 61 1 B 'a' +00000001: 62 2 B 'b' +00000002: 63 3 B 'c' +00000003: 64 4 B 'd' +00000004: 61 62 63 64 5 ASCII "abcdefgh" +00000008: 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 that nothing in the text of the above example indicates the end of one string or the start of another.

The SMAL assembler does not impose any convention for indicating the lengths of strings. High level programming languages always impose such conventions, but they are frequently hidden, since the basic idea of data abstraction is to hide implementation details. In C, as we have seen, the convention is to terminate strings with an ASCII NUL character, that is, a zero byte. In Java and Python, in contrast, the mechanisms used to encode the lengths of charachter strings are hidden from the programmer.

When the language does not impose a convention for indicating the length of a string, it is up to the programmer to adopt one. If a SMAL programmer wants to use C's null-terminated string convention, the NUL or zero at the end of each string must be provided explicitly. The following example illustrates this:

An assembly listing demonstrating null-terminated strings

1 NUL = 0 +00000000: 61 62 63 00 2 ASCII "abc",NUL +00000004: 61 3 B 'a' +00000005: 62 4 B 'b' +00000006: 63 5 B 'c' +00000007: 00 6 B 0

 
In the above, we used the named constant NUL to make the null termination on the string stand out, but it is exactly equivalent to using a numeric zero. 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.

Labels

An alternative way to represent the length of a string is to store the length explicitly as a prefix on the memory area occupied by the text. Because the standard library used with Hawk programs is partially patterned on the C standard library, we will not use this convention, but supposing we did. If we just stored the string length in a single unsigned byte, the maximum length would be 255 characters. If we reserved two bytes or one halfword to hold the length, the maximum length would be 65535 characters.

It is always possible to count the bytes in a data structure or program by hand, but this is dull work. Consider the problem of working with character strings where the length is stored as a prefix, as suggested above. If we hand-cound the bytes, we might write the code as follows in SMAL:

Hand counted characters in strings

+00000000: 0006 1 H 6 ; length +00000002: 61 62 63 64 2 ASCII "abcdef" +00000006: 65 66 3 +00000008: 0003 4 H 3 ; length +0000000A: 61 62 63 5 ASCII "abc"

In the above, we used two bytes, one halfword, to hold the length of each string. The string starting at memory location 0 has a length of 6, while the string starting at location 8 has a length of 3. If we want to change one of the strings, we must count the characters all over again, an unpleasant and error-prone clerical task.

Computers are good at automating clerical work, so it should be no surprise that most assemblers provide tools that can be used to automate this one. Assembly languages typically do this by allowing a symbol to be bound to the value of the location counter at some point and then used elsewhere when that value is needed. 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 much the same effect but in more compact form:

Using the assembler to count the characters

1 S1 = . +00000000: 0006 2 H S1ETX - S1STX 3 S1STX = . +00000002: 61 62 63 64 4 ASCII "abcdef" +00000006: 65 66 5 S1ETX = . 6 +00000008: 0003 7 S2: H S2ETX - S2STX +0000000A: 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 to count characters in the source text.

In the first string, the values of 3 identifiers within the assembler, S1, S1STX and S1ETX, are defined by assigning the value of the special symbol . (period), which stands for the location counter. In earlier examples, we assigned to this symbol to set the location counter. Here, S1 ends up holding the address of the entire object representing the first string, while S1STX holds the address of the start of the text and S1ETX ends up holds the address immediately after the end of the text. As a result, the difference between S1STX and S1ETX is the length of the string, and this value is stored in the first halfword of the object. (The abbreviations STX and ETX are commonly used for start of text and end of text, the names of two somewhat obscure ASCII control characters.)

The second string above uses the names S2, S2STX and S2ETX to hold similar attributes of the second string. These are defined using a different and more compact syntax. When an identifier in the SMAL assembly language is followed by a colon, we say that it is used as a label. Defining an identifier as a lable sets its value to the current value of the location counter.

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, the value is constant and 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.

Two-pass assembly and the scope of definitions

In looking at the examples above, it is fair to ask, if the assembler processes 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 many assemblers, reads the source file twice. It is a two pass assembler. Conceptually, a two pass assembler operates as follows:

• The first pass reads and processes the entire source file to collect the values of all identifiers.

• The second pass reads and processes the entire file to produce the object code.

This view of two-pass assembly is an oversimplification because both passes must track the value of the location counter from line to line, and both passes must handle assignments of values to identifiers. The following example illustrates some of the consequences of two pass assembly:

Some consequences of two-pass assembly

+00000000:+00000008 1 W XXX 2 XXX = . +00000004:+00000004 3 W XXX 4 XXX = . +00000008:+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 most recent values assigned to XXX. 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.

This issue rarely matters because all labels are assigned a value exctly once, and because most symbols used in a typical assembly language program are defined before use. The fact that an assembler uses two passes is frequently only apparent when you forget to define something.

                        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. If any of the examples given above have this property, it is the result of accident or careful construction.

The SMAL assembler does not enforce any alignment, as is illustrated by the following example:
 

Some badly misaligned data

+00000000: 00 1 B #00 +00000001: FFFF 2 H #FFFF +00000003: 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, including C and C++ programs, word processors and spreadsheets.

To solve the alignment problem in SMAL, we 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.h used for the Hawk computer. Generally, you should use the ALIGN macro in 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.h" +00000000: 00 2 B #00 3 ALIGN 2 +00000002: FFFF 4 H #FFFF 5 ALIGN 4 +00000004: 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. USE in SMAL does much the same thing as #include in C. 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.

                        B       1
                        W       2
                        B       3
                        H       4
                        W       5