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 1960's; 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 1940's, but the basic idea has not changed.

Interfaces or Bus

Today, as in the 1940's, the CPU must be connected to other system components. At first, 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 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 1940's, computers store running programs and their variables in main memory, also known as random-access memory or RAM. A variety of memory technologies have been used: Williams tubes, accoustic delay lines, magnetic drums, core memory and semiconductor RAM. Aside from issues of size and speed, all main memory technologies implement a linear array of memory locations.

Input Output Devices

Today, as in the 1940's, computers would be of no use without a way to interact with the outside world, for example, a keyboard and some kind of display or printer. The details depend on the application. The use of auxiliary storage devices such as disks was anticipated in the 1940's, althoug the devices available 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 memory models, and since 1980, most have used 32-bit words, 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 – 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 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, 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 . . .

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. It does not allow halfword and word addressing, and on most computers, if you tried to declare this array in a real program, you might 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 are associated with working memory or other devices.

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

Exercises

b) Give the decimal representations of the first and last address in the read-only part of the address space of the minimal Hawk computer. How many bytes are in this region? How many words?

c) Give the decimal representations of the first and last address in the read-write part of the address space of the minimal Hawk computer. How many bytes are in this region? How many words?

d) Give the decimal representations of the first and last address in the unused part of the address space of the minimal Hawk computer? How many bytes of memory could you add to fill this region? How many words?

e) Give 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

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 widely used high-level language, starting in 1956) or Java (a younger language, dating to 1995). Compilers translate this input to sequencees of macine instructions. Some put these directly into main memory, ready to execute, but most save the result as binary object code or 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 may be called an executable file, 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 #F0F0 ; 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
#F0F0																–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 #F0F0 W 8#12525252525

Most of the above code tells the assembler to put 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 is the assembler's location counter; it tells the assembler where to put the next byte, halfword or word in memory. When the assembler assembles a byte, it puts it in the location referenced by the location counter and then increments the location counter by one. When the it assembles 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

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 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 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 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 shown above contains, in addition to the original source file, a header on each page giving the file title, the page number and the time and date of assembly. In additon, each line of the source file is numbered, sequentially, and, most important, on the left-hand side of the line number, and only on those lines of the file that actually put something into memory, the memory location is shown, in hexadecimal, along with the data placed there, also in hexadecimal.

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

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

Exercises

f) What is the hexadecimal equivalent of the one-word constant 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 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 variables that have been set by the assembly language program for use later in the assembly language code. 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 +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 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.

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.

Exercises

i) Give appropriate definitons, as named constants, for the ASCII control characters BEL, HT, LF, FF and CR. (The binary 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

+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]

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

+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 begin with the 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.

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 stored consecutively in memory. 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 can 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 +00000000: 00000001 5 A: W RED ; A[0].color +00000004: 0000000A 6 W 10 ; A[0].coord.x +00000008: 00000014 7 W 20 ; A[0].coord.y 8 +0000000C: 00000003 9 W BLUE ; A[1].color +00000010: 00000019 10 W 25 ; A[1].coord.x +00000014: 0000000C 11 W 12 ; A[1].coord.y

As with the array example, nothing (aside from the comments) in this code explains how these six words of memory are structured. Data structure is imposed only by the code that uses that data.

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

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

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. Assembly language programmers, though, must always be concerned with such details.

From the perspective of the organization of the data into memory, a character string is just an array of characters, with one byte per 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 are independent objects. The code that uses the data must impose this structure, and in well written programs, the organization should also 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 +00000000: 61 62 63 00 2 ASCII "abc",NULL +00000004: 61 3 B 'a' +00000005: 62 4 B 'b' +00000006: 63 5 B 'c' +00000007: 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 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 string is represented by a memory location containing its length followed by the characters of the string, as illustrated below:

Hand counted characters in strings

+00000000: 0006 1 H 6 +00000002: 61 62 63 64 2 ASCII "abcdef" +00000006: 65 66 3 +00000008: 0003 4 H 3 +0000000A: 61 62 63 5 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 such string is stored in memory locations 0 to 7, while the other is 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 = . +00000000: 0006 2 H S1ETX - S1STX 3 S1STX = . +00000002: 61 62 63 64 4 ASCII "abcdef" +00000006: 65 66 5 6 S1ETX = . 7 +00000008: 0003 8 S2: H S2ETX - S2STX +0000000A: 61 62 63 9 S2STX: ASCII "abc" 10 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 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.) 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 S1ETX and S1STX 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 we are using that identifier 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.

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 many assemblers, reads the source file 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

+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 through the source file.

This issue rarely matters because all labels are assigned a value exctly once, and because most other symbols used in a typical assembly language program are defined before the 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

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

To solve the alignment problem, 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. The most common place you will need to use the ALIGN macro 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.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. 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.