Dr. Dobb's Z80 Toolbook

Contents

PREFACE to the online text

Twenty-five years later, it seems there are still a few CP/M programmers in the world. For their sakes I am putting the book online. A few typos have been corrected and the figures have been redrawn and are somewhat clearer than the original. Otherwise it is the same. Look nearby for access a ZIP archive with the files distributed with the book.

PREFACE to the print edition

This is a book of programs, and a book about programming. It contains a variety of software, all written in assembly language for a computer equipped with CP/M and a Z80 processor. The software is useful, but the book is about the process of constructing programs: how they are conceived, designed, and coded.

The book is in two parts. Part I contains complete programs, each worked out from an initial specification, through a design in a high-level pseudo-code, to working assembly language.

These programs are built from a kit of simpler parts: a comprehensive set of subroutines for manipulating integers, strings, and especially files. It brings to assembly language much of the convenience of the standard C runtime library, and it makes writing assembly language utilities a lot easier. Part II describes how that toolkit was designed and how it works.

What The Software Requires

The software in this book requires the CP/M-80 operating system (either CP/M 2.2 or CP/M Plus). It also requires a Zilog Z80 processor chip. I found that certain Z80 features were absolutely necessary to doing the file-handling modules right. While unavoidable, this is a pity; it means that such excellent dual-processor machines as the CompuPro and the Zenith Z-100, which use an Intel 8085 on their 8-bit side, cannot use these programs.

If you obtain the software in machine-readable form, you can execute the programs of Part I immediately. To modify them, however, you will need the RMAC assembler. To link the toolkit modules with programs of your own you must have the LINK-80 linker and the LIB library manager. RMAC, LINK-80, and LIB are products of Digital Research, Inc. (and trademarks as well). They are distributed free with CP/M Plus and are available separately for CP/M 2.2. There may be other assemblers and linkers that will work, but none have been tested.

Why Assembly Language?

Assembly language a bad reputation. Most books on programming tell you to use a simple language like BASIC, a clear one like Pascal, or an efficient one like C. I echo that advice: in many cases you should write programs in a higher-level language. This is especially true if you are new to programming. Until you are thoroughly at home with the fundamentals of programming -- until you know the loop, the subroutine, the array and the file in all their varieties, and have practiced breaking a problem down and composing a program from its pieces -- you should avoid assembly language. Once you have mastered those things, you are free to choose a language to suit the task at hand.

As compared to BASIC, Pascal, or C, assembly language is inherently more tedious and difficult to use. Worse, it is not portable; assembly-language programs can only run in the combination of processor and operating system for which they are written. However, assembly language code is normally much smaller and faster than the code generated by the simple compilers available for CP/M. And assembly language gives you access to all the features of the machine and operating system, including many that aren't available in higher languages. Sometimes speed and access to the hardware is crucial to the success of an application.

Commercial programmers avoid assembly language because its extra difficulty raises the cost of a project, while its lack of portability cuts down the size of the market. Still, I heard Mitch Kapor, president of Lotus Development, say that Lotus 1-2-3^ had to be written in assembly language because a prototype written in C was too big and slow to be saleable. And though Apple's MacIntosh owes some of the speed of its graphics to brilliant algorithms, its designers credit a well-honed assembly language toolbox for most of its speed.

Once you decide to use assembly language, your first concern should be to minimize the inevitable extra cost in effort. That's best done through a disciplined approach to design and coding, and by making full use of a library of subroutines. This book aims to demonstrate both those things.

The Genesis of This Book

I started out to do a simple update of an earlier book (A Programmer's Notebook: Utilities for CP/M-80, Reston, 1983; now out of print) to make it work under CP/M Plus. But the longer I looked, the less I liked the older book, especially its library of subroutines which was incomplete and had many inconsistencies.

For this book I began by designing and building a comprehensive toolkit of subroutines. I packaged them as functional modules and gave them macro interfaces that were as simple and as consistent as I could make them. (For example, all of the CP/M file operations, even to the testing and setting of file attributes, can be done with simple macro calls and no use whatever of the CP/M File Control Block.) Only then did I write the programs that would use the subroutines.

Half way through, I heard of a comparable package, called SYSLIB, that was in the public domain. I was careful to avoid seeing SYSLIB or any other subroutine package, so as to avoid even a hint of plagairism.

The work was finished in September 1984, just as the market for computer books in general, and books on CP/M in particular, collapsed like a pricked balloon. The publisher that had contracted for the book had, like much of the software industry, become fixated on the IBM Personal Computer. They decided the book wouldn't sell and gave it back to me.

Fortunately the present publisher realizes that there are more than a million CP/M machines in daily, productive use. The people who own them have been using computers longer than the typical PC owner, and since their abandonment by an industry they have become more knowledgeable and self-reliant. A lot of them, we hope, are getting ready to write their own software. Those are the people this book is for.

D. E. Cortesi

Palo Alto, 8/84 and 9/85

1 RAW MATERIALS

In Figure 1-1 you see a simple program. It's about as trivial as it can be; it writes one ASCII character, the control character BEL, to the console. I call it beep.

I hope you have composed assembly programs as complicated as beep before now. If so, you know that what you see in Figure 1-1 is the source text of a program, which would be prepared with an editor program and stored as a file on disk. The file would, very likely, be named beep.asm.

The Assembly Process

The program could be assembled with the CP/M command

The assembler, a program named asm, is called; it reads the source file and performs the translation from readable symbols to binary machine language. The translated program is called an object program. It is recorded as another file, beep.hex in this case.

That file is still not executable. In fact, although all the symbolic names have been stripped from it and replaced with their binary equivalents, beep.hex is still in a symbolic form. A hex file represents the machine-language program as a series of ASCII characters, one for each hex digit (group of four bits). This hex-file format was originally designed for storing object programs on paper tape, but it still has its uses.

CP/M includes a program that will convert the hex form of an object program to true, binary, machine language. It is called load in CP/M 2.2 and hexcom in CP/M Plus. The command

in CP/M 2.2, or

in CP/M Plus will read the file beep.hex. The assembler's output will be converted to binary and written as a new file, beep.com. This file is an exact copy of the machine language program as it must appear in storage before the CPU can execute it. Once beep.com exists, the operator may give the command

In response, CP/M will copy beep.com into storage and apply the CPU to it. The result will be a single "beep" from the terminal.

All assemblies go through these two translation steps. First the assembler converts symbols to binary values and records them in an intermediate file. Then a second program converts the intermediate file into an exact, binary image of the program. The operating system can load this image as a command, and run it.

In a simple assembly, the assembler is asm, the intermediate file is a hex file, and the second program is load (or hexcom). In the rest of this book, however, we'll use a relocating assembler, rmac, and a program linker, link, as the second program.

THE INSTRUCTION SET

In order to construct a program of machine instructions, we have to know what instructions are available for use. A CPU's repertoire, the vocabulary of its machine language, is called its instruction set. These instructions, and the machine resources they can manipulate, are the raw materials of assembly language programming.

In this book we will use the instruction set of the Zilog Z80 CPU. However, the assembler we will use was originally designed to handle the simpler instruction set of the Intel 8080 CPU, and that causes some problems.

The 8080 Instruction Set

Intel's 8080 CPU was the first microprocessor to have an instruction set with enough power to be useful for general data processing. Its successor, the very similar 8085, is still a useful machine.

The 8080 offers us a very small set of hardware resources with which to work. The first one is an address space of 65,536 bytes of RAM, or "memory," or (as I prefer to call it) working storage. The CP/M operating system preempts two portions of this. It reserves the first 256 bytes, and its code occupies the highest addresses -- typically the top 8 or 12 kilobytes. The remaining addresses are available for our programs and their data.

A second resource is an 8-bit accumulator called register A. Except for loading and storing data, almost everything that the machine does, it does in register A. Only in register A, for instance, may we perform decimal arithmetic or manipulate the bits of a byte.

A third resource is a group of four 8-bit registers known as B, C, D, and E. These may be used to hold single bytes, or they may be paired as BC and DE to hold 16-bit words. In that guise they can be used as addresses for loading and storing a byte from register A. These registers may be incremented or decremented, but they can't receive the result of any other arithmetic operation.

A fourth resource is another pair of byte registers, H and L. Paired as the HL register, these can be used as a 16-bit accumulator. That is, the unsigned 16-bit word in HL may be added to itself, or the BC or DE word may be added into it. The contents of DE and HL may be swapped in a single instruction (but not the contents of BC and HL).

An important feature of the 8080 is that the storage byte whose address is in HL can be used as if it were another 8-bit register on a par with B, C, D or E. In the assemblers used here, that byte is referred to as register M.

A fifth resource is a pushdown stack of words in working storage. The CPU contains a 16-bit register, the stack pointer, which points to the last byte pushed onto the stack. Any of the register pairs may be pushed on the stack, which grows downward (from larger to smaller addresses). A useful oddity of the instruction set is that the word in HL may be swapped with the top word on the stack in one instruction.

The Intel Assembler Syntax

The Intel company specified an assembly syntax for the 8080's instructions. Now, remember that there is no necessary relation between the binary bytes that the CPU reads on one hand, and the syntax rules of the assembler that prepares those bytes on the other. The assembly language is merely some engineer's idea of a concise, readable way to write down instructions.

The syntax Intel chose was simple. We might quarrel with some of the choices for operation code symbols -- the use of mov (move) where most other assemblers use "load" can be confusing, and if they had to use it, why couldn't they have spelt it out in full? -- but it is much too late to quibble.

The CP/M operating system was designed to support the 8080, and asm, the assembler that was part of it, naturally supported the Intel syntax for instructions.

The Z80 Instruction Set

Zilog designed the Z80 CPU as a faster, more powerful replacement for the 8080, and it was a quick success. In order to be a true replacement, the Z80 had to be compatible with the 8080; that is, it had to process the same instructions the same way, so that programs written for the 8080 could run on a Z80 without significant changes. Zilog succeeded in this. The machines differ in certain very subtle points about the way the flags are set after certain operations, but it's a rare 8080 program that won't run on a Z80.

The Z80 provides us with more resources. The most important ones are the IX and IY registers. These two 16-bit registers are used to address storage, just as the HL register can address a byte as "register" M. However, while we can reach only one byte through HL, we can reach any of 128 bytes on either side of the address in IX or IY.

The best use of an index register is to hold the base address of a block of related data. Then any byte of the block is just as accessible as any other, and any of them may be used as an operand in an arithmetic or logical instruction. If you persevere into Part II of this book, you'll find that the file-handling subroutines make extensive use of IX to access a block of information about the present state of some file.

The Z80 added yet more features to those of the 8080. It can test, set to 1, or set to 0 any single bit in any byte register. And while the 8080 can shift and rotate the bits of register A, the Z80 extends these operations to all registers. The Z80 can also subtract, as well as add, unsigned words into register HL. That makes it a lot easier to write subroutines for general binary arithmetic.

The repeating instruction was another Z80 innovation. It has six of them, each amounting to a short subroutine wrapped up in a single operation code. The ldir instruction is the best-known; it allows us to copy a block of storage from one place to another in a single operation. In the discussion of string operations in chapter 14 you will find an analysis of the use of Z80 operations like ldir versus the comparable 8080 loops.

The 8080 gives us a set of conditional jump instructions. The Z80 supplements these with a group of "relative" jumps. While an 8080 jump always specifies the full, 16-bit address of the place to jump to, a relative jump contains only an 8-bit number from -128 through +127. When the jump is taken, this offset is added to the present instruction address.

Relative jumps have three advantages. The first is that they are "position independent"; that is, a block of code that contains only relative jumps may be moved to a different place in storage and still work, whereas if an 8080 jump is moved, the address in it has to be modified. The programs in this book don't move around in storage, so position independence doesn't mean much to us.

The second advantage is that a relative jump is one byte shorter than an 8080 jump. That can be important in some rare applications, but if every jump in this book were relative, the programs wouldn't shrink by as much as ten percent.

The final advantage is an esoteric one. As the Z80 does it, an 8080-style jump always takes the same amount of time (ten clock cycles) whether or not the jump condition is satisfied. A relative jump, however, takes less time (seven cycles) if it is not taken, and more time (twelve cycles) if it is taken. So, in code that is fine-tuned for speed, we might write a relative jump whenever we expect the branch to be taken rarely, and an 8080-style jump when we expect it to be taken more often than not.

One relative jump, the djnz (decrement and jump if not zero), is especially useful. This instruction decrements the contents of register B and performs a jump if the result is nonzero. It is just the ticket for controlling small loops, and we'll use it a lot.

The Zilog Assembly Syntax

After designing a CPU that was so closely compatible with Intel's, the engineers at Zilog went on to specify an assembly syntax that was utterly different. It may have been that the engineers came from different backgrounds, with the Intel people following a DEC tradition while the Zilog folks worked to an IBM model. Whatever the reason, Zilog's official assembly syntax for the Z80 bears no resemblance to Intel's, even where the machine instructions are identical in binary value and operational effect.

Good things may be said of the Zilog assembly syntax. It is consistent; that is, similar operations have similar syntax. The Intel engineers, for example, seemed to think that there was something fundamentally different between loading register A from the byte addressed by HL, which they coded as

and loading it from the byte addressed by BC, represented as

At Zilog, they saw these as the same fundamental operation and encoded them as

respectively. Either scheme works, since in any case we programmers soon learn the instructions by heart and think of them by their effects, not their encodings. But two incompatible traditions were established.

That created a problem for the companies that built computers and software based on the Z80. Those that already had an investment in 8080-style software often chose to ignore the Zilog syntax. Instead, they extended the Intel assembly format to cover the additional registers and operations of the Z80. One such company, now defunct, was Technical Design Labs; you will still sometimes see references to "TDL syntax" or to their "TDL assembler," an assembler that was distributed by several companies.

Companies that started out with the Z80 adopted the Zilog style from the start. Software for Tandy Corporation's TRS-80 line, for example, has always used Zilog syntax.

The Digital Research Solution

Digital Research Inc., the publisher of CP/M, chose neither course. It didn't supply a Z80 assembler in any form. Even today, the three 8-bit assemblers from Digital Research will accept only 8080 instructions. However, two of these assemblers, mac and rmac, are macro assemblers. We'll consider macro assembly in the next chapter; for now it is enough to say that one advantage of a macro assembler is that you may design your own instruction set. That's what Digital Research did; they supply a library of Z80 instruction macros as a standard part of the assembler package. You include that library in an assembly; then you may write Z80 instructions in extended-Intel syntax.

This is the form of Z80 instructions that you will find in this book: the form established by the Digital Research macro library. Except for the relative jumps, such instructions are rare in the programs of Part I. The 8080 instructions were adequate for almost everything done there. In the toolkit presented in Part II, however, the Z80 facilities are used a great deal.

Tabulating the Instructions

If you are not as familiar with the Z80's instructions as you'd like to be, join me in an exercise. When I am confronted with a new CPU, I get a handle on it by cross-tabulating its instructions in different ways, looking for relationships between them. If you'll do that for the Z80 instructions I guarantee you'll uncover a few surprises.

In the first table, document all the possible ways of copying a single byte from a source to a destination. The possible sources and destinations include

• register A
• B, C, D, E, H and L, the other byte registers
• M, the storage byte addressed by register HL
• the byte addressed by register BC or DE
• any of the 256 bytes around the address in register IX or IY
• a storage byte specified by some symbolic address

Table 1-1 is a start at such a tabulation. Its columns represent sources and its rows, destinations. The single instructions that copy a byte have been filled it. Omitting the entries on the diagonal, how many of the missing squares can you fill in with sequences of instructions, and how short can you make the sequences?

If your patience has held up through that exercise, make a similar table for the instructions that will copy a 16-bit word between

• register HL
• register BC or DE
• register IX or IY
• the stack pointer, SP
• a word in storage at a symbolic address

Table 1-2 is a start at this 25-entry table. Note how few one-instruction entries there are, and how many are unique to the Z80. Can you find short sequences to fill in the empty entries? Spending a few hours constructing such tables is one of the best ways I know of to feel at home with the resources of a CPU.

THE CP/M BDOS

There is one one other resource on which our programs may draw. The CP/M Basic Disk Operating System, or BDOS, is present in the machine along with our program. It can perform a number of services, and will if we invoke it correctly. The beep program of Figure 1-1 calls on the BDOS.

The BDOS is located at some address in high storage; that is, it begins at an address higher than the end of our program. We don't know what that address is. It varies from system to system, and it can vary from one command to the next in a single system, although it normally doesn't. However, there is always a jump instruction at location 5 (address 0005h) which is aimed at the lowest instruction in the BDOS. To call upon the BDOS, we need only place the correct arguments in registers and call location 5.

One BDOS argument is a service number that specifies what we want done. It is always passed in register C. The other argument depends on the service being requested, but if it's a byte, it is passed in register E, and if a word, in DE. In beep, the service is to type a byte at the system console. The second argument is the byte to be typed; it's passed in register E.

In Part I of this book, the programs interact with the BDOS only at second hand, through the subroutines of the toolkit. In Part II we will employ many BDOS services in designing the toolkit itself

2 TOOLS

We use abstract types in any program. Look at the beep program again (Figure 2-1). Even in this trivial exercise I can identify three abstractions. There is "the set of valid BDOS service request numbers." One of those is 2, the request to display one character on the screen. There is "the set of ASCII control characters." One of those is 7, the BEL character. Finally, there is the BDOS itself, the abstraction of a program that will perform a function given certain parameters. This last is not an abstract data type but rather a functional abstraction, the concept of a particular action.

Symbolic Names

Abstractions are purely human constructions. We may decide that a set of bytes is an English sentence, but that decision is in no way part of a machine-language program. The CPU will not object if we tell it to multiply two sentences, look for a verb in a floating-point number. The assembler will not complain if we give it a program like this.

High-level languages help us avoid mistakes like that. They do it with a variety of mechanisms for isolating one data type from another. Assembly language doesn't; it permits us to mix data types in any way we like, including nonsensical ones. However, it also gives us the means to construct our own type-handling mechanisms. The first of these is the symbolic name. We use symbolic names to make clear the distinction between one kind of data and another.

We don't do it for the computer's benefit. Look again at Figure 2-1. When it is translated to machine language, it is compressed by a factor of 40, from more than 360 bytes to just eight. This compression is the result of stripping out every bit of symbolic information. Names of operations translate to one byte; symbolic constants translate to one or two; and all comments are deleted.

Ninety percent of the beep source file is redundant -- to the CPU. But these things are not in the source file to serve the CPU; they are there to serve human purposes. In Figure 2-2 you can see a version of beep that contains the absolute minimum of symbolic information. In translation it compresses by a factor of only five. Since it is eight times less redundant, it is in some sense a more efficient representation of a computer program. However, it is a total failure as a message between humans.

Every program source file is a message with three destinations. One destination is the processor, which has no ability to process symbolic information. The second is yourself; you record your decisions about the abstractions being used in the program as comments and symbolic names, for quick reference as you work. The third is a future person, either the programmer that will follow you or yourself at a later time.

Since two of the three recipients of a program are human, and since the other is mindlessly unaware of the program's symbolic content, it follows that the symbolic components of the source text deserve as much attention as the purely mechanical elements.

It also follows that the best assembler is the one with the best support for symbolic information, and that we should exploit that support as thoroughly as we exploit the machine. The CP/M assemblers all allow symbolic names to be as much as 16 characters long and can handle hundreds of names in a single assembly. I've made good use of those features in these programs.

Standard Names

Some things and locations are such constant features of CP/M programs that we might as well have standard names for them, and we might as well find a way to avoid having to type them into every program. The assembler's maclib command gives a way to include a file of equated names.

All the programs in this book use a single macro library, environ.lib. It contains, among other things, about 50 names for common things, notably the standard CP/M storage locations and the ASCII control characters. A separate macro library, services.lib, contains names for the BDOS service requests and a service macro that encapsulates the calling mechanism. If we like, we can rewrite Figure 2-1 using these two libraries and standard names (Figure 2-3).

ABSTRACT TYPES

Neither the CPU nor the assembler have any support for abstract data types, but we programmers use them constantly. Four types are so common and so useful that they crop up in every program. This book features a toolkit of subroutines that deal with these four data types: the character, the integer, the string, and the file.

Characters

We use use the ASCII code to relate numbers (which is all that a byte can contain) to letters. Once we've decided that a certain byte will contain a character, we tend to talk as if we really could store a letter in it. We can't, of course; even when we write a sequence like this

what we have accomplished is to store the number 120 in the byte -- a quantity that has no necessary relationship to the letter x whatsoever. That's the virtue of abstractions. Having decided on the treatment of LetterByte and having accepted the ASCII code, we can write a program in terms of these abstractions. It relieves our mental burdens considerably, as anyone will attest who has entered a program, in binary, to a primitive development system through its toggle switches.

Sometimes we have to switch between one abstraction and another on the fly. For instance, if we want to make a letter uppercase, we have to alternate between thinking of it as a letter, as a number, and as a bit-pattern. In Figure 2-4 you see a subroutine that returns the letter addressed by register HL as uppercase. There are two point-of-view switches in it.

The first five instructions do a range-check on the letter and exit if it isn't a lowercase letter. The second and third compare the letter to the constant a and return if it's less. The alphabet, as we usually think of it, doesn't recognize the concept of "less"; even so, up to this point most people would agree that the program is dealing with alphabetic letters.

In the fourth instruction we shift to another view of the letter. Here we want to test the letter against z but, in order to set the Carry flag for all cases when the letter is less than or equal to z, we has to test against a value greater than z. The expression 'z'+1 only makes sense if we think of z as a number, not a letter.

The subroutine finally makes the letter uppercase by setting its bit 5 to zero. That operation only makes sense if we think of the letter as a pattern of bits. After long experience with assembly language, I find such shifts in point of view very natural, but they do give newcomers a lot of trouble.

Abstract Functions

It is a mental strain to work with materials whose shape depends on our angle of view, and every increment of mental stress adds to the time-cost of making a program. But the strain is only present while we are designing and coding the operation. If we code it once in a subroutine like Figure 2-4, we may then forget all its internal details. The symbolic name of the subroutine becomes the abstract function "make an uppercase letter." Thereafter we need only write

without regard to the details of the process. Naive writers on programming will tell you to use subroutines because they make the program smaller (the instructions don't have to be repeated at each place they are used). That's true. However, the true economy of a subroutine is that it reduces the mental load on the programmer. From that point of view, it can be economical to create a subroutine that is used only once.

The toolkit used in this book contains a number of functions that, like Figure 2-4, modify or classify single characters.

Strings

A lone character has limited uses. Often we need strings of them. A string can be a message, or part of one; it can represent one line of a file; and tables of strings are helpful for decoding complicated user input. Most high-level languages recognize the string as a fundamental data type. Assembly language does not; it supports only independent bytes. However, it gives us the tools we need to define our own string data type. We only have to decide how a string should be represented in storage.

There are two common ways of representing strings. In both, a string is a sequence of letters in adjacent bytes. In one method, the string is preceded by a count of the bytes in the string. For instance, a 6-byte string that could be as long as 10 bytes would be defined this way.

This representation of a string is used by several Pascal compilers, but hardly ever in assembly language. You can spot the languages that use it; they restrict strings to a maximum length of 255 bytes because they have to fit the count into the leading byte. This string form has the advantages that it is easy to discover the string's length (just pick up the count) and it's easy to find the end of the string (add the string's length to its address). But nothing else you might do with a string is easy because you are forever patching up the length-bytes.

The other method leaves the length of the string implicit, marking its end with a special delimiter that can't otherwise appear in a string. A variety of delimiters have been used. The CP/M BDOS marks the end of a string with the ASCII currency symbol in some of its functions. Some programmers, when space is at a premium, will mark the end of a string by setting on the high bit of the last character. But the most common delimiter is the null byte, a byte with a numeric value of zero.

The same constant string (six bytes in a 10-byte string space) would be defined this way, using a null delimiter.

With this convention, it takes time to find the end of a string or to learn its length (you have to inspect each byte in turn until you find the null byte). But it is easy to copy a string (just copy bytes until you have copied the null) and to append one string to another (find the null in the first, then copy the second through the null that ends it).

It is particularly easy to compare two strings in this format. A subroutine that does it appears in Figure 2-5. One nice feature of this string format is that when one string is a leading substring of the other, the shorter one will automatically appear as "less."

Null-terminated strings have the nice property that every trailing substring of a string is also a string. The string abcd0 (using 0 to stand for the terminating null) is a string, but so are bcd0, cd0, and d0. So indeed is the terminal null byte; it's the null string. This property means that, for example, if we are pointing to a string that has leading blanks, we can increment the pointer past the blanks and still be pointing to a string. It might now be the null string, but otherwise it needs no special handling.

This string type is a very useful abstraction. The subroutines in this book include a comprehensive set of tools for creating and manipulating strings in assembly language.

Integers

Only two numeric data types are native to the Z80 CPU: the unsigned 8-bit integer and the unsigned 16-bit integer -- in other words, the binary byte and the binary word. The only arithmetic it can do on them is to to add or subtract them, or increment and decrement them by one. A lot can be done with only these abilities, but sometimes we need more.

Sometimes we need other kinds of numeric data. One useful type is the signed integer, a number that can record negative as well as positive values. Occasionally we need the operations of multiplication and division. Multiplication and division of unsigned values can be done with subroutines, and all four arithmetic operations on signed values require subroutines. Subroutines to multiply and divide unsigned integers, and to add, subtract, compare, multiply, and divide signed integers, are part of the toolkit developed in this book.

When two 16-bit integers are multiplied together, the result may be as much as 32 bits long. An integer of this size is an awkward thing for the Z80 to handle. It takes more than half of the CPU's registers just to hold it! Nevertheless, the data type of the 32-bit (4-byte) integer turns out to be useful, especially in file operations.

Under CP/M 2.2, a disk file may be as long as eight megabytes: 8,388,608 bytes, to be exact. Under CP/M Plus, it may be four times as large, or 33 million bytes. If we want to note our position in a file exactly to the byte -- and we do -- we must be able to note a number that may occupy 25 bits. If we want to convert a byte-address within a file to a record count, we have to be able to divide such a number by an integer.

Accordingly, our toolkit must contain at least some support for working with 32-bit unsigned integers, or "longwords" as we will call them. The toolkit routines for 16-bit multiplication return longwords; there is a routine to divide a longword by a word; and there are routines to add, subtract, and compare longwords.

These numeric types -- bytes, signed and unsigned words, and longwords -- are all binary numbers. We must have a means to convert between the binary representation of a number and the ASCII digits that we can display, print, or type on a keyboard. This is where the numeric data types and the string data type come together. The toolkit contains a set of functions to convert strings of ASCII digits into binary values, and vice versa. If we have a string of digits (either decimal or hexadecimal), we can convert those characters into the binary number they represent. If we have developed a binary number, we can convert it to digit characters and append them to a string.

Files

The file is another abstract data type. The bulk CP/M itself is concerned with supporting this abstraction. To a CP/M program, a file is a sequence of bytes that it can create, write, read, rename or erase by calling on the BDOS with appropriate arguments.

This a great convenience. The operating system's file services shield us from a world of messy details -- we needn't worry about disk space allocation, or sector and track numbers, or sector sizes, or I/O interfaces. All we have to do is point to a CP/M file control block and say, "do it, please," and it will be done. Furthermore, the same "do it" request will work correctly in another system with different disk hardware, and under other versions of the operating system such as MP/M.

Problems With the File System

Useful though it is, the CP/M file system has some shortcomings. Although it claims to present a file as a sequence of bytes, it really stores it as a sequence of 128-byte records. There are too many places where we have shift points of view, thinking of a file at one time as a sequence of bytes and at another as a sequence of 128-byte blocks.

Another problem is the lack of device independence. Under CP/M, there is one set of service requests for dealing with files and a completely different set for dealing with the console, printer, and auxiliary devices. That's too bad, because with few exceptions these character devices could be treated just like files, and there are many advantages to doing so.

Another failing is that there is no connection between the file abstraction and the other abstract data types, especially integers and strings. We'd like to be able to read or write data in units that are strings, or words, or longwords, but the only data unit that CP/M can transfer is the 128-byte record.

There is also the problem of filespecs, the command tokens that the user enters to name a file. The user names a file as "d:filename.typ," but the program must parse that string into the file control block before CP/M can use it. Not only is this a tedious bit of processing, but the program must also check the string for validity (CP/M won't), and must check to see if it is ambiguous.

A related problem is the sticky one of file passwords. CP/M Plus supports them while CP/M 2.2 does not. Under CP/M Plus, a complete filespec is "d:filename.typ;password." The program must recognize the password and take special steps to present it to CP/M when the file is opened, or to assign it when a file is created. Furthermore, a good program should be able to tell when a file password is needed and prompt the user to enter it -- but only if it was omitted. All these filespec problems make it a major operation to get a file opened for processing.

Solving the File Problems

All of these problems can be solved, and their solution is a major feature of the toolkit presented in this book. It contains a set of functional abstractions for dealing with files, abstractions that make of a CP/M file a true abstract data type that interacts smoothly with the other abstract types. The design details are complicated, and we'll defer them to the second part of the book. In the first part we will concentrate on using files.

In order to use an abstract file, you have to use assembler macros. But macros and relocation are separate topics. Let's turn to them now. We will return to files in the the next chapter.

MACROS

Every assembler gives us two tools for abstraction, symbolic names and subroutines. A macro assembler gives us a third: the macro. In essence, a macro is a packet of assembler statements that we can invoke with a single line. We define the macro just once. Wherever we want that packet of lines inserted in a program, we write only the name of the macro. The assembler replaces it with the lines we defined for it.

Macro Replacement

Let's demonstrate this with an example. Recall Figure 2-4, the subroutine named uppit. Suppose that, for some reason, we expected to have to make the byte Letter uppercase at several places in a program. Furthermore, uppit doesn't affect the byte in storage; it returns the altered byte in register A. Therefore at several places in the program we are going to have to write this sequence of lines

Besides, at some of those places, we won't want the previous contents of registers A and HL destroyed when this is done.

Very well, we will write a macro and name it letterup (Figure 2-6). That done, we can write the single line letterup wherever we intend to make the value of Letter uppercase. The assembler will replace the one line with the seven lines defined for the macro. This is called "macro expansion"; the assembler "expands" our one-line macro call by replacing it with the body of the macro definition.

There are several ways to think about what we have accomplished with Figure 2-6. The simplest is to say that we have used the assembler to save ourselves time at the keyboard, and we have.

Another way is to say that we have used the assembler to create a new machine instruction, the letterup instruction. It's a special-purpose instruction which happens to be composite, comprising seven ordinary instructions.

The most general way to think about it is to say that we have used the macro feature to create a new abstract function. As a result of our coding the macro, the name, letterup, has come to stand for the function, make-the-byte-Letter-be-uppercase. Wherever in a program we need that function, we need only code the name.

Notice that the letterup abstraction has been built upon another abstraction, the one implemented by the subroutine uppit. The macro provides the function of the subroutine plus saving and restoring registers. We will often build one abstraction on another until we have produced a whole heirarchy of them.

Macro Parameters

If that were all there was to macros, they would still be useful, but there is more. A macro can be written to take parameters (or "arguments" or "operands" -- the words should have different meanings, but they've been so abused that they mean almost the same thing).

A macro parameter is a portion of the macro that is to be supplied at the time the macro is processed. When we define the macro, we refer to the parameter by a symbolic name. When we use the macro, we supply data to be substituted for the parameter-name wherever it appears in the macro expansion.

Parameters let us make a macro general rather than specific. We can demonstrate this by rewriting Figure 2-6. A macro that operates only on a byte name Letter is specific to that label. We should define instead the macro upany (Figure 2-7). This macro takes as its only parameter the address of the byte to be made uppercase.

Compare Figure 2-6 and Figure 2-7. They differ in only two lines. In Figure 2-7, the first line notifies the assembler that this macro takes a single parameter whose name is "which." In the fourth line there is a reference to which; when the assembler expands the macro it will replace the characters "which" with whatever characters the programmer wrote following the name of the macro. At one point in the program we might write

with the result that the assembler will produce the line

At another point we might code

and the assembler will dutifully produce

as one of the lines of the macro expansion. In this way a macro can become a general functional abstraction.

Parameter Tests

The Digital Research assemblers support conditional assembly, a means of controlling the assembler so that different code is produced depending on the contents of the source program. This finds its greatest use within macros. One common use is in checking the parameters of macros. As shown in Figure 2-7, the upany macro doesn't check its parameter in any way. If we thoughtlessly omit the parameter,

the assembler will replace the parameter name "which" with the null string, producing the line

Then it will discover that it can't assemble such an instruction and flag that line as an error. But the cause of the error won't be obvious. We can trap the error and issue a diagnostic message if we rewrite the macro as shown in Figure 2-8.

The assembler will expand all of the lines of the macro, replacing every occurrence of which with the given parameter, just as before. After expanding all eleven lines, it will process them just as if they had been written into the program at that point.

Now, however, the lines comprise a conditional assembly -- one bounded by if, else, and endif lines. The assembler will process the if line, which instructs it to test a condition. The condition in this case is "not nul" followed by whatever parameter was given. That condition is satisfied if any nonblank characters follow the word nul. If a parameter was given, the condition is true, and the assembler continues working up to the point at which it finds the else line; then it skips lines until it finds endif. The effect of the macro expansion will be exactly the same as if we had used the macro of Figure 2-7.

If we omit the parameter, however, something different will happen. The assembler will still expand all eleven lines of the macro body and begin to process them. But the condition of the if line will not be satisfied. After expansion, it will consist of only

because no parameter was given and so which was replaced with the null string.

Since the condition is not satisfied, the assembler will begin skipping; it will not assemble anything until it has seen the else line. When it begins assembling again, it will find the line

That is not a valid assembly statement. It's a deliberate error. The assembler will display it with an error flag. The line doesn't say anything to the assembler or the CPU, but it gives the programmer a better handle on the source of the problem.

Conditional Assembly

The conditional assembly feature can be used within macros to make them more useful or more flexible. To see how, let's rewrite the upany macro once more.

As written in Figure 2-8, the macro abstracts the idea of "make a named byte in storage uppercase." That might be handy, but there are times when we want to make a byte uppercase when we can't refer to it by a symbolic expression. Perhaps we have computed its address by adding together a base address and some other factor. Now its address is in register HL, but we can't give a symbolic name for it, and therefore can't use the macro. We could just write the subroutine call instead:

Besides being tedious, that might confuse a later reader who would waste time figuring out why we didn't use the macro here.

We'd like the macro to handle this case. We need a way to tell it that the address has already been loaded into HL and therefore it needn't generate the instructions to save and load HL. The only way to do that (with the Digital Research assemblers; others have better methods) is to define a special symbolic name, and to test for that name in the macro. Suppose that, early in the program, we had defined the name +H to the assembler:

If we can assume that's been done, we can rewrite the macro as shown in Figure 2-9.

If we give this macro a parameter that is any expression other than +H, it will produce exactly the same lines as the one in Figure 2-8. But if we invoke it with the line

the assembler will find the conditions of the two inner if statements to be false. As a result, it will skip assembling the lines that save, load, and restore register HL. The special parameter +H serves to tell the macro, "don't bother saving and loading the address, I've done it for you."

(This technique works with the assembler named mac, but it does not work as shown with rmac. A more involved method, described in Part II, is really required.)

Toolkit Macros

All of these macro techniques, and some that haven't been mentioned, have been put to use in building the tools in this book. To begin with, every function in the toolkit is accessed by way of a macro. These macros validate their parameters as fully as they can, and produce specific messages when necessary parameters are omitted. Most of them use the technique of special names for registers.

The contents of the macros are explained at length in Part II of the book. However, you don't have to know their contents in order to use them as we will be doing here in Part I; you only need to know how they are employed.

The toolkit macros are defined in a single macro library named environ.lib. It is made part of an assembly with the single statement

The assembler primes itself with the toolkit macros before continuing with the assembly. The environ maclib contains

• standard names for common locations and for ASCII control characters
• an abbreviated set of Z80 instructions (omitting I/O instructions and those that use the IY register)
• macros for testing single characters
• macros for manipulating strings
• macros for integer arithmetic
• macros for file operations
• macros for allocating storage, and for filling and copying blocks of storage

The macros, their functions, and their parameters are listed in an appendix and are summarized for quick reference on the end-papers of the volume.

MODULARITY, RELOCATION, AND LINKING

Simple assemblers like asm provide symbolic names and conditional assembly. Macro assemblers like mac add the ability to define and use macros. There is a third level of capability and it, too, enhances our ability to create abstractions. This is the ability to construct independent modules, and to create a final program by linking an assortment of modules together. An assembler that supports this is commonly called a relocating assembler -- although relocation is the least important part of it.

External and Public Symbols

To a simple assembler, a program is a single source file and it is assembled in a single run of the assembler. There is no relation between the code produced in one assembly and that produced in another. As a result, the output of an assembly has to be a complete, self-contained program. Every function required by that program has to be part of its source text, because there is no way (or at least, no easy way) to combine the output of two different assemblies into a single program.

A relocating assembler does not force this assumption on us. The input to a relocating assembler does not have to define a self-contained program. It may be the source of a module: a portion of a program that is logically separable from other parts, but not complete in itself. The assembler provides three features that, together, make it possible to link together the output of many assembly runs into a single program.

The first two features have to do with symbolic names. We may tell the assembler that a particular name is external, that is, not defined by any statement in the current source file. The assembler takes it on faith that the given name will be defined somewhere, sometime, in another assembly. It includes in its output a note to the effect that name so-and-so is required to complete this module. It also writes notes to designate all the places in the object code where the address of name so-and-so is used in an instruction.

The complement to an external name is a public name. A name that is defined within the current source file may be be designated as public. This tells the assembler that access to the name will be required by other modules. The assembler does nothing special with the name except to place in its output a note to the effect that name such-and-such is defined at a certain offset in this module.

Linking

These special name-handling features are almost enough to allow modularity. Already you can imagine a program that would read the object code of two or more modules and splice together their name-references. It could see what names were defined as public, and what names were required as external references; then it could supply to the external references the addresses that correspond to their definitions.

Let's illustrate this with a simple example. We will begin by converting our uppercase subroutine, Figure 2-4, into a complete assembly source file (Figure 2-10). This requires only the addition of a public statement to make the entry-point label of the subroutine available to other modules.

Two other, optional, lines have been added in Figure 2-10: a name statement causes the module's name to be part of its object file, and an end statement tells the assembler the source is complete. The assembler doesn't require the end line; the physical end of the file would serve. The name statement names the module within an object library.

If it were placed in a file uppit.asm, the source text shown in Figure 2-10 could be assembled by rmac. The output would be another file, uppit.rel, which defines the object code of the subroutine. It isn't a complete program; it doesn't do anything that would be useful as a CP/M command. It is, however, a logically-separable part of a program, one that realizes the functional abstraction of converting a letter to uppercase.

Now we need a way to combine this module with another program. Suppose we were writing a program in which we had need of uppit. Here is part of it:

The extern statement tells the assembler that the name uppit is not defined anywhere in the current source file. Instead we promise, cross our hearts and hope to die, that the name uppit will be defined as public in some other source file. The assembler believes us. When it assembles the call uppit statement, it doesn't try to put an address in the call instruction. It puts only zeros there, and inserts a note in its output saying "this call instruction won't work until it has been patched to point to something called uppit."

The program that weaves together these interlocking name-references is called link; it is part of the rmac software package. It processes the output of one or more assemblies to produce a runnable program. We could finish our program with the command

The link program would read program.rel and uppit.rel and combine them. It would note the public name uppit in one and the external reference to the same name in the other, and it would patch the call instruction so that it pointed to the code of the uppit subroutine. Its output would be the file program.com, ready to execute.

Modularity

Notice what this gives us. The subroutine uppit only needs to be written once; in it, we put our idea of how a certain abstract function is to be implemented. It needs to be assembled only once, also. After all, once we have defined how to do this task, how often will we need to change it? The tiny file uppit.rel is all we need. In any program where we need the function, we can write an extrn statement for uppit, and include uppit when we link the program. Even that can be simplified, as we'll see.

But we have left a loose end. We actually use uppit by way of the macro upany (Figure 2-9). It's the macro name that represents the function to us, not the subroutine name. It's all too likely that we'll employ the macro without remembering to declare the subroutine as external. If we do, the call statement in the macro expansion will produce an assembly error type "U" because the name uppit will be undefined.

This is easily fixed. All we have to do is to add the extrn statement to the macro body (Figure 2-11). When the macro expands, the statement will be processed. The assembler will note the need for uppit in the object file, the linker will add it to the finished program, and all will be well. If we use the macro several times, several extrn statements will be generated. That causes no problems with the Digital Research assembler and linker, although other products might prohibit it.

Relocation

I have glossed over the linker's other task, relocation. Consider: at the time it is processing a source file, the assembler cannot possibly know where the object code is going to be located in storage. Nor can we know it. Oh, if the source file represents the main part of a CP/M command, we know that it will have to be located at 0100h, the base of the CP/M transient program area. But when we are assembling a subroutine like the one in Figure 2-10, neither we nor the assembler can tell where the code will finally reside. It depends on the size of the program to which the subroutine will be appended. By the same token, the assembler can't predict where an external name will be when the program is finished.

Many Z80 instructions, especially jumps and calls, contain operands that are 16-bit address values. These addresses depend on the final location of the code that they refer to. Yet the assembler cannot know where the code will be! How can it finish these instructions?

The answer, of course, is that it doesn't finish them. It leaves room in the object code for the addresses, but it doesn't try to put values in them. It does include notes in the object file that say, in effect, "this word refers to an offset of x bytes within this module." Everything else is up to the linker.

The linker is the program that knows the final location of each piece of code. It puts the first .rel file at address 0100h; all the rest follow it. As it prepares each module, link updates all the addresses so they refer to the location of their final targets.

OBJECT LIBRARIES

The rmac product is composed of three programs. We've already discussed the assembler, rmac, and the linker, link. The third program is a library manager, lib.

Its purpose is to build and maintain libraries of object modules like uppit.rel. It is easy to accumulate a collection of dozens, even hundreds, of useful little modules. It is awkward and inefficient to keep each one as a separate .rel file and to name it in the link command. Instead we collect them in related groups as object libraries ("relocatable libraries" in the Digital Research documentation). The lib command is used to build an object library, to list its contents, or to replace a module within a library.

The lib program will build either of two types of library files. Both have the same contents, a collection of modules. The simplest is just a concatenation of the modules that go into it. Such a library has the filetype .rel.

The second type is called an "indexed relocatable library" and has the filetype .irl. A file of this type commences with a table of module-names and the file offsets at which they commence. Both the lib and the link program can use this tabular index to locate a module quickly.

Suppose that we already had an object library named misc.irl. We could add the file uppit.rel to the library with this command.

The lib program's peculiar syntax becomes more understandable if you keep in mind that it always builds a new file from one or more old files. The new file is named on the left of the equals sign. The old files that go into it are named in a list to the right of the equals sign. The command above can be read as "Lib: create misc.irl (which is to be an indexed relocatable library) from the contents of misc.irl plus uppit.rel."

Notice that giving a filetype of irl to the new file is not sufficient. You have to include the option [i], or lib will build an ordinary library.

Should we alter uppit and reassemble it, we could update it in the library with this command.

Read that as "Lib: create misc.irl (which is to be an indexed relocatable library) from the contents of misc.irl, replacing the module whose name is uppit with the file named uppit.rel." (We put name statements in module source files, as in Figure 2-10, so we can refer to them in such commands.)

When we have uppit in an object library, we can link a program that uses it with this command.

The option [s] after the library name means "selective search"; it tells link to include only the modules from this library that are specifically required. Lacking the option, link will include everything in the library whether it is referenced or not.

The toolkit used in this book is kept in one object library, environ.irl.

SUMMARY

We have achieved the acme of abstraction allowed by the Digital Research assembly products. We have defined an abstract function, that of making a byte uppercase. We implemented the simplest, most general case of the abstraction as assembly source, then stored its object code in an object library.

We defined a macro as an interface to the abstract function. The macro builds on the simple subroutine by saving, loading, and restoring registers. The macro also declares the subroutine as external so that link will include it.

When these steps have been done, all we need to do in order to use the abstract function is to include the macro library that defines it in our programs. Well, we do have to remember the name of the macro and what it wants in the way of parameters. However, all that's needed to invoke the function is to write of the macro name and its parameter. The macro will take care of setting up the registers that the subroutine needs. The assembler will note that the subroutine is needed. The linker will search for it and append it to the linked program.

In the next chapter we will experiment with these tools by writing some simple file-copy programs, and we will study some of the features of the file abstract data type

3 DRAFTING AIDS

The preceding paragraph is a plan of sorts, but it has to be formalized. In Figure 3-1 you will see a first pass at a formal plan for the typist program.

That plan is rendered in pseudo-code, a notation for planning programs. A pseudo-code is any notation that mixes the few, rigid, control structures allowed by good programming practice with free-form words whenever we want to defer thinking about irrelevant details.

Interlude: Pseudo-Code

A pseudo-code plan is for use by people, not by programs, so it may use any notational conventions you like. My personal pseudo-code style mixes English with forms taken from real programming languages. You are free to develop your own pseudo-code style, one that suits you taste and the way you think. The style should force you to state the shape of the problem in the formal, explicit manner of a programming language while not impeding your thinking with excess detail.

There are four reasons to write a plan in pseudo-code. The first is that it forces discipline on a verbal specification, giving it structure. That structure reveals much more precisely what the program will entail. Often a problem that sounds simple in English turns out to be very difficult to do. It's better to find that out while planning than while coding.

The second reason is that we make discoveries as we labor to translate fuzzy words into the strict forms of a program. We discover which things in the program will be hard to do and which easy. We discover that down here we will need to use something that we could have stored back up there. We discover that we will have to do the same procedure at three different places, and therefore it should be a subroutine. Or we discover that we have to do in this program something that we already worked out while planning an earlier one.

The third reason is that we can experiment with a pseudo-code plan. It's close enough to a program that we can make initial judgements about the algorithm we will use. We can write two versions of a procedure and decide quite accurately which version will run faster or use more working storage. We can erase, cross out, revise in every way; and we can do it with much faster "turnaround time" than if we were doing the same experiments in a real programming language. The flexibility and power of the pseudo-code "editor" and "compiler" are really amazing when you consider that they consist of nothing more than a yellow pad and a felt-tip pen.

The last reason is that the actual program is much easier to write when we can work from a good pseudo-code plan. One reason assembly language is hard to use is the number of niggling details that we have to keep track of: the contents of the registers, the correct jump condition to use, and so on. But these matters are local problems that can be worked out while looking at a span of code no larger than one screenful. They aren't difficult to solve, provided we are not at the same time trying to solve global, algorithmic problems. It's just not possible to work out the correct use of the stack and the shape of the main loop at the same time. But if you have made all the big decisions and recorded them as pseudo-code, the coding details are easy to cope with.

Designing Typist

Let's return to the design of the typist program. The first draft of a plan appears in Figure 3-1, and it is nearly enough to code from. (I can say that because I know there are toolkit macros that correspond to each of the major lines in Figure 3-1.) There's only one change that should be made in it. The loop condition, "until done," is vague. When is "done"? The answer requires a digression on the nature of the file abstract type.

One of my objectives in designing the file-handling tools was that all files were to be handled alike, whether they were disk files or CP/M character devices. As much as possible, an input file was to be an input file regardless of whether its contents came from a disk, or the keyboard, or a modem. And it worked out that that could be done (the details are in Part II).

Another principle was there were two types of files, ASCII and binary. An ASCII file contains ASCII characters grouped in lines, and its end is marked by the Control-Z byte or by physical end of file, whichever comes first. A binary file contains any sort of bytes; has no internal structure except as the program imposes one; and it ends only at physical end of file. The difference between these two types of file lies entirely in how the program treats them. If it reads a file with ASCII-type macros, the file will be given ASCII-type treatment; if not, not.

Now, it is my plan in typist to treat both the console and the printer as ASCII files. That means that the end of the input file will be marked by receipt of a Control-Z byte. (It can't be marked by physical end of file, because there is no such thing as the "end" of a device.) The functions that read ASCII data return a signal when they find a Control-Z byte.

That is what "until done" amounts to, then: the appearance of logical end of file on the input, as signaled by the function that reads a line. We can express this in the plan by rewriting it as shown in Figure 3-2. In it, the pseudo-keyword break means "exit the loop right now."

Coding Typist

Since it doesn't do any processing of the data, the typist program consists almost entirely of calls on toolkit functions. As a result, its assembly code (Figure 3-3) is almost a line-for-line translation of the plan. Read it now, then let's examine it together.

Many of the lines of the program are calls on toolkit macros. In a minute we will talk about these in the order they are used. Remember, however, that all of these macros are documented in the Appendix to this book.

Figure 3-3 is, of course, an assembly source file. It is written for assembly by rmac, a relocating assembler. That explains the two statements dseg and cseg, which you may not have seen before. Relocating assemblers distinguish between a "data segment" and a "code segment." These portionss of the program are kept separate. At any point in the program the assembler is producing object code for one segment or the other, and these statements switch between them.

The program begins in the data segment by defining two files with the statements

The words confile and lstfile are the names of macros. They are declarative macros; that is, macros that expand to lists of static data. Declarative macros are normally placed in the data segment, although they don't have to be.

Each of these declarations expands into a "file control record," an assemblage of bytes and words that will represent the file to the toolkit functions. There is a general-purpose macro for declaring a file; it is named filedef and we will use it later. The macros used here are special cases of filedef that make it easy to define files that specifically represent the console and the printer.

The line

calls on another declarative macro. The strspace macro declares space for a string of some length -- in this case a length of linesize, or 128 bytes. The macro assembles to a single null byte plus the requested amount of undefined space. In other words, it reserves room for a string of that size, and initializes the space to the null string.

Declarations done, the program switches to the code segment, where executable instructions are always assembled. It invokes the prolog macro because a call on prolog must be the first executable statement in any program that uses the toolkit. This macro expands into a few instructions that

• learn the size of working storage
• set up a stack
• initialized the dynamic storage allocation functions

and then call the instructions that follow prolog as a subroutine. Everything that follows prolog is a subroutine of it; therefore the main program may end with a simple return instruction. When it does, the remaining instructions in the prolog expansion return to the operating system. Under CP/M Plus, they also set the Program Return Code to a value of "success."

The formalities complete, Figure 3-3 gets down to the business of the program, which takes exactly four lines to conduct. Here they are:

Two of these are macro calls. The fgetstr macro gets a string from a file. It requires three parameters: the address of the file, the address of a space to receive the string, and the maximum length of the space. In this macro the keyboard file is passed as the file, the line string space will receive the data, and the constant linesize is used to specify its maximum length. (In Figure 3-3, find the three places where linesize is named. Do you see its purpose?)

Reading a string is an ASCII-type operation. The fgetstr function takes bytes from a file and stores them in a string until it sees a Return byte, or a Control-Z byte, or until the string space fills up. If it stops on a Control-Z byte, it returns the Zero flag true; otherwise it returns it false. As a result, our pseudo-code statement "if end of file, break," can be implemented as the instruction rz, meaning "if fgetstr saw a control-Z byte, quit."

As you can probably guess, the fputline macro writes a string to a file. It also writes a terminating Return and Linefeed pair. (There is a function fputstr that writes the string but not the Return and Linefeed. These macros are related in the same way as the write and writeln procedures of Pascal, or like BASIC's PRINT statement with and without a terminating semicolon.)

Assembling and Linking

The source file of Figure 3-3 can be assembled with a command such as

You may not be used to assembler options. Their meanings are

• lb: find macro libraries on drive B
• px: write the listing to the console (only)
• sz: don't write a symbol table file
• -m: don't list macro expansions

The last option simplifies the listing; without it the tedious and uninformative macro expansions obscure the listing. (I'm not trying to hide anything; feel free to display the macro expansions if you want to. You'll soon find that they clutter your neatly-typed logic without adding any information.)

You can see the result of that assembly command in Figure 3-4. It doesn't add a great deal to the source file; so little, in fact, that I almost never keep an assembly listing. A listing of the source file is sufficient as a record of the program.

As soon as the assembly is complete, the program can be linked. The resulting console display appears in Figure 3-5, and it deserves comment.

The bulk of Figure 3-5 consists of a display of all the public labels that link handled while linking the program. You might wonder what all these names signify. The answer is, very little. Most of them are the names of toolkit functions. The toolkit modules call one another with abandon; for example, FSPST, which implements the put-string function, calls FSPAC (put an ASCII character), which calls FSPBY (put a byte), which would call FBOUT if it needed to write a buffer-load to disk, and so forth.

All this has next to nothing to do with the logic of typist, the program we are interested in. There are two things worth noting. First, all the public names used in the toolkit code begin with the at-sign character. That's a device to isolate these public names, avoiding conflicts with public names you might devise.

The second thing to note is the aggregate size of this, a very simple program. According to the messages at the end of Figure 3-5, the final code segment contains 553h bytes (1,363 decimal), and the data segment contains 3ACh (940 decimal). There is a common segment (a separate, named, data segment) of 128 bytes, so the total size of the program is 2,431 bytes.

That seems like a lot for a trivial program, and it is. The typist program could be written in a tenth the space if we were willing to hand-code its file operations. Because of the way the toolkit functions cross-link with each other, there is a minimum size of about 2,500 bytes for any program that uses only device files and about 4,100 bytes in the more typical programs that write to disk. Two things make that acceptable. First, it is still small when compared to the minimum size of a program in a high-level language (compile the comparable program in Pascal or C and check its final size). Second, after this first lump, programs grow very slowly as they become more complex. The increase in size after 4,100 bytes is all in the processing code, not in the support.

Using Typist

Now that it exists as typist.com, we can try out the typist command. There isn't much to it (see Figure 3-6). Each time the Return key is pressed, that line is written to the printer. When the user enters a Control-Z signal, the program quits. An impatient user could also kill this program by entering Control-C; CP/M would then cancel it. We shouldn't encourage our users to do that, however. For one thing, it doesn't work with all programs. For another, Control-C cancellation takes place instantly, without giving the program a chance to clean up after itself.

Console Input: Lines or Bytes?

It's an important feature of typist that it permits the operator to use CP/M line editing. It only does so as a result of a special feature of the toolkit input functions. In most cases, the support for fgetstr simply copies one byte at a time from the file to the string space, stopping at the first Return character. That's what it does for a file and for the AUX character device (called the RDR device in CP/M 2.2).

The toolkit functions make a special case of reading a string from the keyboard. In this one case, they call on the BDOS for its service of reading a whole line. It is that BDOS service that supports line editing. Since the system handles it, our programs don't have to. On the other hand, the length of such a line is limited. The BDOS won't read a line longer than 255 bytes, while the toolkit function won't ask it to read a line longer than the buffer associated with the file. In the case of the confile macro, that buffer is only 128 bytes long.

Longer lines, indeed lines of any length at all, can be read from other kinds of files. Longer lines can be read from the keyboard as well, but only by requesting them one byte at a time with a different macro, fgetchar. The disadvantage is that when the keyboard is read one byte at a time, CP/M doesn't supply any line-editing features.

THE Keyfile PROGRAM

The typist program is a file-copy program written for the special case of copying from keyboard to printer. It has its uses, but the same abilities could be had from a more general program, one that copies from the keyboard to any destination: the printer, the AUX (or PUN) device, or to a disk file. Let's make such a program, and call it keyfile.

The purpose of keyfile is to take lines from the keyboard and write them to some destination. The destination will be named as an operand of the command; it will either be a file or one of the keywords AUX:, PUN:, or LST:.

The keyfile program will serve the same purposes as typist, but may also be used to construct a short disk file or to send a line or two to whatever is connected to the AUX device. Like typist, it will allow line-editing of the input lines. However, it should also display a prompt; that is, some signal that it is ready for a line to be entered.

Designing Keyfile

Once more we prepare a plan in pseudo-code. It resembles the plan for typist but there is more to be said (Figure 3-7).

The main loop of Figure 3-7 is much the same as the main loop of Figure 3-3, except for the addition of displaying the prompt. The differences occur outside the main loop, in preparing the files beforehand and closing the output file after the loop ends.

Command Operands

One of the most convenient, and at the same time most awkward, features of the CP/M programming environment is the way that command-line operands are presented to a command program. It is convenient, in that whatever operands the operator may have typed are placed in a known location in storage. The program may parse them and use them in any way desired.

It is awkward because the characters of the command line are simply left, exactly as they were typed, and the program has to parse them into tokens before they can be used. That is not a simple task; for a program the size of keyfile, the code to isolate an operand and assign it as the name of a file can be larger than the code of the main loop. The problem becomes harder as the number of operands increases.

CP/M will have formatted the first two operands into CP/M File Control Blocks (provided they were delimited by spaces, not by tabs), but CP/M doesn't recognize the names of devices for this use; and it doesn't handle operands after the second; and anyway the first two may not have been meant for file names.

The toolkit addresses these problems through two functions. One parses the operand string into tokens, each token a separate string, and reports the number of tokens it found. The other returns the address of a token-string given its number.

With these services in mind, we can expand on the plan line, "verify the operand." What must be verified is, first, that exactly one operand was given. With no operands, the program wouldn't know where to put its output. If there are two or more, the operator has confused this program with another one.

When one operand was given, its format must be validated; that is, we have to make sure that it is a valid file specification, or filespec. That can be done by calling on the toolkit function that assigns a filespec (as a string) to a file. It reports back if the string was not valid, or if it was ambiguous. We mustn't try to use an ambiguous filespec (one like "*.doc" or "abc???.sub") for output.

If we assume the presence of these services, we can expand the plan as follows.

Preparing Files for Use

The input and output files will be specified as abstract files using the general macro filedef. Such files must be opened before they can be used. Anywhere in data processing, to open a file is to do whatever is necessary to make it ready for use. In the specific context of this book's toolkit, opening a file entails several steps:

• discovering if the file represents a device or a disk file
• finding out if the file can support its intended use
• allocating a buffer for the file
• for a disk file, finding or creating the file in the disk directory

In the typist program, we used the confile and lstfile macros. Since these are specific to the console and printer devices, they are "opened" statically at the time the macros are expanded.

The Input file in Figure 3-7 will be prepared by application of the freset macro, which prepares a file for input. The file will be dedicated to the console device, so we know beforehand that freset will discover that it represents a device and that it can support its intended use, which (freset assumes) is that of sequential input.

The Output file will be prepared using the frewrite macro, which prepares a file for output. We won't know what the real destination of the file will be; it will depend on what the the operator gave as a command operand. The frewrite support might find it to be a device like LST: or a disk file. It might find that the destination can't support the implied use of sequential output. That would be the case if the command operand was a read-only device like RDR, or (under CP/M Plus) if it specified a read-only disk file. In such cases, the open function will abort the program for us.

Coding Keyfile

With an expanded plan in hand we can code the program (Figure 3-8). Read it now to see how much of it you can understand or guess at. In a moment we will study each line, but try to get the big picture first.

Once more the source file follows the pseudo-code closely, since again there are toolkit macros for almost everything that has to be done. The lines

are the first appearances of filedef. This declarative macro expands to a block of 64 bytes which represents a file. Half of that contains a CP/M file control block (FCB), the normal input to the BDOS for file-oriented service requests. The remainder is used by the toolkit functions that support files; it allows them to extend the CP/M idea of a file into a more general, flexible abstract data type.

The filedef macro allows five parameters. The first one is required; it specifies the size this file's buffer is to have. The buffer is a block of storage where file data can be held on its way to or from the file. The buffer space is allocated dynamically when the file is opened; it does not take up space in the program as stored on disk.

This buffer-size parameter is required, and it must be a multiple of 128 bytes. In both cases here, the buffer size is given as Linelen, that is, 256, bytes. For the Input file, that permits receiving a line of up to 254 bytes from the operator. The buffer size for the Output file didn't have to be the same size; it could have been specified larger or smaller. With the single exception of reading whole lines from the keyboard, all toolkit file functions work with any size of buffer. Generally they go faster with larger buffers, but speed isn't a concern in this program, which is limited by the operator's typing speed.

As many as four parameters may follow the buffer-size. When given, these parameters represent the file specification for this file. In full, the parameters of filedef are

In the declaration of the Input file, only the name parameter is specified. When a file is given a filespec with the only the filename CON:, having no drive-letter, no filetype, and no password, the toolkit functions will recognize the file as referring to the console. This is how we dedicate the Input file's definition to the console device. (We might better have coded the name KBD:, which the toolkit recognizes as meaning the console device for input only.)

No filespec parameters are given for the Output file. That is because the filespec will be assigned to it later, when the program executes, from the first operand of the command.

String Constants

The two lines

declare constant strings. The strconst macro assembles the given constant in the form of a string, that is, terminated by a null byte so that the string functions will handle it correctly.

The Abort Macro

The code of Figure 3-8 follows the pseudo-code of Figure 3-7 very closely. Indeed, the assembly code was made from the pseudo-code: I edited the pseudo-code file, converting its lines to assembly comments, then wrote the assembly statements between them.

Before we follow the flow of logic in the code, let's consider the abort macro that appears several times. It frequently happens that, in the initialization sections of a program, we want to terminate it with a message. We don't expect the program to abort very often, and aborting is not a detail on which we want to spend a lot of time, but still we have to think about it. The abort macro makes it easy to code these cases.

The macro takes two parameters; its syntax is

The jump-condition is a one- or two-letter condition that you might code as part of a jump instruction in the case where an abort is desired. The message-label is the address of a message that is to be displayed as the program quits.

Unlike the rest of the toolkit macros -- in which I tried hard to avoid optional macro parameters -- both parameters of abort are optional. If the jump condition is omitted, the abort is unconditional; it will always take place if control reaches it. And if the message label is omitted, the macro assumes that register DE addresses the message.

The message issued by an abort is written with a BDOS service request that expects the data to be terminated with a dollar sign, $. (Notice that that was true of the string constant, Ughhh.)

When an abort takes place, its effect is to jump directly to a short piece of code that is produced in the expansion of the prolog macro. This code calls on the BDOS to display the message and then terminates the program. (Under CP/M Plus, it also sets the Program Return Code to a "failure" value.)

All of the aborts in keyfile use the same message, a very unhelpful statement that "I have a problem." In later chapters we will improve on this behavior.

Using the Toolkit

With that background, we can follow the logic of keyfile. The savetail function scans the command tail that CP/M left, and breaks it into tokens wherever it is delimited by spaces or tabs. Each token becomes a string, and all the strings are put away for safekeeping in a block of storage that is allocated dynamically. The count of tokens found is returned in register A. Here, the program tests that count and aborts if it isn't equal to 1.

The tailtokn macro returns a token given its number (counting from 1). It returns the address of the token in register DE, which is the usual way of addressing strings for the string functions. However, the file functions, when taking a string as input, take its address in register HL (they reserve DE to address the file block). Accordingly, the code here puts the token address in HL and invokes the fassign macro. This function accepts a file (here Output) and a string, and assigns the string as the filespec of that file. At this point we have the address of the string in a register, and have no other way of naming it. The macro call specifies that the address of the string is already in register HL.

The fassign function reports two conditions. If the string it receives is not a valid CP/M filespec, it returns the Zero flag true. If the name was valid but ambiguous, it returns a question-mark in register A. The code here checks these two cases and aborts if either is true. The remainder of the program is a straightforward translation of the pseudo-code, and quite similar to typist.

SUMMARY

We have built two versions of a simple, but useful, program; we have practiced using pseudo-code; and we have gone over the use of some common toolkit macros in detail. These three chapters have been a lengthy (and perhaps tedious) introduction to the fundamental tools of assembly language programming. We can list them now. The chief one is the mental tool of abstraction in all its forms. The physical tools are used to implement heirarchies of abstractions. We define some common data types and the operations on them; we implement those operations as subroutines; we hide the subroutine interfaces in macros. We use the assembler's naming and macro abilities to do this, and we use the linker and library manager to store the subroutines conveniently and efficiently.

In the rest of Part I we will write ever more complicated programs and create ever-higher levels of abstraction. In the text, I will pay less attention to the details of the tools because they are documented in the appendix. It's not the tools we are concerned with here, but what we can build with them

4 EMIT

That's a very pretty specification; now we have to implement it. We begin, of course, with a draft pseudo-code plan (Figure 4-1).

There are two basic strategies we could use here: we could write each byte to the device as soon as we decode it, or we could decode them all, then write them all at once. The second strategy is shown in Figure 4-1. The first strategy is simpler, but it has the defect that, should the program find a byte it can't decipher, it may have already sent some bytes to the device. Under the second strategy, either all bytes will be sent or none of them will.

SELF-DOCUMENTATION

Before we go further with the design of emit, let's turn aside to investigate a general problem that is raised by the first line of Figure 4-1, "validate the number of command-tokens." It describes a step that will be part of nearly every program we write. Every program expects a certain number of command operands, perhaps zero, or exactly two, or sometimes the count of operands must fall in a certain range. Their count is the first thing the program can learn about its operands. What should it do when it gets the wrong number of operands?

The typist program of chapter 3 expected no command operands. The keyfile program expected exactly one, and aborted with an unhelpful message if it was given more or less than one operand. Now we have emit: it wants a device name and some number of bytes to emit. The minimum number of operands it can accept is 1 (when no byte operands are given), while the maximum is the maximum that the user can squeeze onto the line.

What should a program do when the number of command operands doesn't meet its expectations? Some CP/M commands take the approach that if they are given no operands, they report on the system; if they have operands then they change the state of the system. The user command is an example of this policy.

Prompting for Missing Operands

Another policy is to take the absence of operands as a cue to prompt the user to enter the missing operands. In CP/M Plus, the rename and date commands work this way, and the pip command has always followed that policy. We might visualize emit carrying out a dialogue like this one.

There are things to be said for such a policy; it looks "friendly" as all get-out. Unfortunately, it is difficult to do it well. Once a program undertakes to be interactive, it vastly increases its opportunities for looking stupid. To see what I mean, consider this dialogue.

Substitute any conceivable user mistake for "frummage"; the point is, a program has to validate every response as it gets it to avoid looking stupid. But then it must also have the logic to report an error in that response and re-prompt. That goes for every prompted input, and it adds up to a significant amount of programming - often more programming than is involved in the function the program is meant to do in the first place.

Another problem arises from the fact that command operands are positional in nature; that is, the only thing that distinguishes one operand from another is its position in the command line. That makes it impossible to tell for certain which operands have been omitted unless they all are. In the case of emit, for example, if there are any operands, the program must assume that the first one is meant as a device-name. If it gets just one operand, emit can't tell the difference between these two cases:

In the first case, the user names a device but omits to say what bytes should be sent to it; in the second, the user has named a byte to send (the byte that puts an Epson MX-80 into condensed mode) but not the device. If the user has been deluded into expecting the program to prompt for a sequence of bytes in the first case and for a device-name in the second, he or she is going to be disappointed; the program doesn't have the information it needs to be that clever.

The Usage Message

Finally, we should ask if the effort of prompting for missing operands is really worth all the programming it takes. Its only use is to help the user who doesn't know the usage of the command. The user who knows it wouldn't bother with prompting; it's a lot quicker just to type the operands and be done with it.

If we design our commands to take only a few operands, and if we make those operands flow in a natural sequence, then the only problem we have is how to help the user who has not learned them, or who has temporarily forgotten them. That can be done with a brief usage message - a few lines that summarize the proper use of the program.

Let's establish the rule that, if a program is given no operands, or the wrong number of operands, or if its very first operand is a single question-mark, it will respond by displaying a usage message. Here's how that might look with emit.

A display like that is enough to jog the memory of someone who has used the command before but who has forgotten, perhaps, how the program wants hex numbers written. It also summarizes the command for someone who has never used it, but who simply wondered what it was good for. It omits some details, but that's why we write documentation, isn't it?

We could, of course, write the complete program specification into the usage message. I know people who would argue that we should, or rather, who would argue that all systems should have complete documentation of all commands on-line at all times. Those peoples' machines have larger disks and faster processors than mine. Documentation is bulky; and the documentation for a command is used many, many times fewer than the command itself is used.

The Chkops Module

In every program we do from here on, we will want to save the command operands, check their count, and check the first operand for a question mark. The function is stereotyped and easy to make into a parameterized subroutine. Let's do that, creating a module chkops that we can include in any program. Its pseudo-code appears in Figure 4-2.

The plan outlines a subroutine that takes three parameters: the minimum and maximum counts of tokens that the program will accept, and the address of a usage message. Since chkops will use the message in an abort macro if it uses it at all, we must be sure that the message ends in a dollar sign.

The plan in Figure 4-2 includes the first use of my personal pseudo-code notation for a subroutine that returns a value. In this case, the returned value is the count of command operand tokens.

The plan is a simple one and not difficult to convert to assembly language. The result is in Figure 4-3. There are a few things worth noting in that listing.

The name Statement

The first is the name statement with which it begins. Its only effect is to make the the assembler include that name as one of its notes in the object file. The linker will make no use of the name. Only the lib program notices the name of a module; it keeps a name for each module in an object library. The lib command is easier to use if every module has an explicit name that is the same as its filename.

The Entersub Macro

The code in Figure 4-3 defines only a module, not a complete program. We code the prolog macro as the first statement of a complete program, but that would not be appropriate in a module. That macro generates the code to set up a stack and initialize storage. A module should depend for such matters on the program with which it is linked. However, the prolog macro defines two public labels that a module may need: +BDOS, the gateway to the operating system.

The entersub macro is used to get access to those two names. All it contains is a pair of extern statements to define them as external, but it has a nice, official look to it.

Saving Registers

As you read Figure 4-3, you might have noted how the code goes to some trouble to return all registers to its caller just as the caller passed them. The only exception is register A, in which the module returns its result, the count of tokens.

This is a general rule that we will apply to all subroutines: a subroutine will preserve all of its caller's registers, except for the registers in which it returns a result. In chkops we might reasonably suppose that the caller doesn't care if registers B, C, and DE are preserved or not; nevertheless we still preserve them.

It costs us something to apply that rule. It takes time to push and pop registers, and the stack-size requirement goes up. Neither cost is very large. The registers are pushed and popped only once for each call on a module. If the module contains any kind of loop, its real processing time will completely overshadow the time taken to save them. The prolog macro reserves a generous, 256-byte stack when the program starts up. That allows for pushing 128 registers, or for 32 nested subroutine calls each of which saved four registers.

The benefit of applying the rule is that abstract functions keep their abstract nature. When we know that the rule will be applied consistently, then at the moment we code a call to a subroutine we need think only about the subroutine's defined result. We don't have to clutter our minds with exceptions, dangers, special cases. All we have to remember is which registers the subroutine takes as input and which it returns as output. That reduces the number of things we have to keep in mind, and that speeds programming and reduces bugs.

The Greater-Than Condition

The code in Figure 4-3 illustrates one peculiarity of the Z80 instruction set. The Z80 (and the 8080) have processor flags that are set during a comparison. A comparison is essentially an unsigned subtract; the flags are set as if the instruction operand had been subtracted from the contents of register A.

The processor flags are so defined that, after a comparison, we can detect equality with a jz jump, and we can detect that A was less than the operand with a jc jump. Furthermore, we can detect that A was greater than or equal to the operand with a jnc jump. But there is no single jump that will be taken if A was greater than but not equal to the operand.

That is the condition that must be detected in Figure 4-3 when comparing the count of operands to the contents of register C, the maximum number allowed. There are three ways to handle the situation. The simplest would be to code two jumps in sequence,

so that the first jump eliminates the equal-to condition from consideration. Besides being confusing to read, that solution offends my sensibilities; it uses six whole bytes (gad!) to detect a simple condition.

A second solution is to reverse the order of the operands. Instead of comparing to see if count is greater than max, we could arrange things so we could compare to see if max was less than count. It's the same test but its result is revealed unambiguously by the processor flags.

That's not easy to read, and it destroys the contents of register B.

A third solution is to reduce the first comparand by one or to increase the second comparand by one. Either strategem merges the case of equality (of the original comparands) with the case of less-than. Thus if we want to test a letter to see if it is less than or equal to "z" we can code the test

If register A is less than or equal to "z," it will be simply less than a value one more than "z."

In Figure 4-3 we dare not increment the second comparand, since the caller might have passed 255 in register C (meaning, essentially, "I don't care how many"). Incrementing C in that case would cause it to overflow to zero, resulting in a false detection of an error. The method actually used is to reduce the first comparand; if the count less one is less than register C, then the original count must have been less than or equal to C. That trick, also, is subject to error. If the original count was zero, decrementing it would make it underflow to 255. But at that point in Figure 4-3, the case of a zero count has been eliminated.

THE BODY OF EMIT

Now we have taken care of chkops, we can turn to the rest of the plan for emit.

Checking the Device Operand

The second item in Figure 4-1 is "validate device name and assign to dest." I first thought to do this with the fassign macro. That macro lets the program know if the token represented a valid, unambiguous filespec. Unfortunately, it does not let the program know if the filespec named a device (that's not usually a consideration when setting up a file).

There is a toolkit macro that inquires whether a file is a disk file or a device, and another that tests to see if a file is read-only or writable. The two in combination would tell the program whether or not it had been given the name of a writable device. Unfortunately, neither of those macros will work until the file has been opened, and we don't want to open the file unless the operand is valid.

There is another way. Part of the toolkit's support for strings is support for searching a table of strings. A table of strings is a collection of string constants. There is a macro, strlook, which accepts the address of a table of strings and the address of single string, and searches for a match to the string in the table. We will build a table of strings, each an acceptable device name, and search it for a match to the first-operand token. If there is a match, the operand is valid.

Decoding Bytes

The rest of Figure 4-1 is concerned with decoding the operands that represent bytes to be emitted, and it is written at very high level (in other words, it's vague). This part is repeated in Figure 4-4.

The way we defined the byte-operands, we can tell the type of each one from its initial character. If it is an alphabetic, the operand must be a name like ESC or COMMA. If a quote, the operand is a literal; if a decimal digit, it's a number - although whether decimal or hexadecimal we can't tell. These realizations, plus some details concerning how the decoded bytes might be stored, are expressed in Figure 4-5.

The effect of Figure 4-5 is to organize what we know about initial letters and to defer the decision on what to do about them. Procrastination is an important tool in program design. Here we have decided that there ought to be a separate subroutine for each kind of token, decided what parameters each routine will take, and finally we've put off any decisions on how those routines will do their work. Now each can be considered in isolation.

One other decision is visible in Figure 4-5: there will be a subroutine badbyte to handle the case of an indecipherable operand. It will be given the bad token; it will presumably issue an enlightening error message and abort the program.

Name Operands

Ok, let's tackle those deferred decisions, starting with the case of a token that is initially alphabetic. Such operands ought to name ASCII control characters. They can be decoded with a table of strings. We will set up a table of valid control character names and search in it for the token we got. If it appears, it's a valid operand. If the operand doesn't appear in the table, we will call on badbyte to issue a diagnostic message.

A table of strings can also translate a string. To see how, you must understand how a table is laid out in storage. The heart of a table of strings is an array of addresses. Each address-word points to a constant string. Space for this array is reserved by the strtable macro. Each constant string is assembled by the strentry macro, which also sends the assembler back to fill in the string's address in the array of addresses.

When we apply strlook to search the table, we pass it the address of the array of addresses. The function compares the input string to each table entry in turn, getting their addresses from the array.

Although we will usually define the table-entry strings together, they don't have to be adjacent in storage. Other data can be sandwiched between the strings; it will not affect the way the table is searched. The strlook function gets the strings' addresses from the array; it has no way of telling whether or not they are adjacent, nor does it care.

Used in its simplest form, strlook merely returns the processor's Zero flag true if the input string appears in the table. However, it can be used in such a way that it also returns register HL pointing to the null byte at the end of the table entry that matched the string. That's the key; if we leave the translation of each name following the table-entry that describes it, we will be able to validate a name and translate it in a single step. The plan for names comes out looking like Figure 4-6.

Numeric Operands

The numeric operands are easier to handle. There are toolkit macros that, given the address of a numeric string, will convert it to binary and return the binary result. The only problem is to decide whether the operand was written in decimal or hexadecimal so that the right toolkit function can be applied. That is indicated by its last character, which should be either a digit or the letter "H." If it is neither, or if the conversion routine returns a binary value greater than 255, we will abort through badbyte. The resulting plan is shown in Figure 4-7.

Literal Operands

Operands that represent literal characters commence with a quote, either an ASCII apostrophe or a double-quote character. This may be discarded. If the user is a nitpicker and closed the operand with the same character, the closing quote should be eliminated as well. The characters that remain in the string should be counted and copied to the holding array. The only error that I can think of is the case where, after dropping the leading and trailing quote, nothing remains. That should be diagnosed through badbyte. The plan falls out as Figure 4-8.

In decoding both numeric and literal operands, we need to get at the ending byte of a string. There is a toolkit macro, strend, that will advance a register from the front of a string to the null at its end. From the null, backing up one byte gives the address of the end character. That might, of course, be the first character as well; we'll have to watch out for such one-letter strings.

CODING EMIT

The emit program comes out quite a bit larger than the ones we've dealt with thus far, so let's examine it in sections, starting with its prologue.

The Prologue

The opening sections of the source of emit appear in Figure 4-9. Like all the programs in this book, the source lines are limited to 64 characters. That's because the assembler adds sixteen bytes of information to the head of each line as it lists it. The longest lines in the listing are limited to 80 characters, and will fit on the screen of the terminal.

The first section is a descriptive prologue. Its purpose is to summarize the main features of the program for another programmer (or for myself at a later time). Professional software shops apply strict, elaborate standards to the layout of such a prologue. We can be more casual, but some things really should be present: a synopsis of the program's function and command syntax, a list of the abort messages it may display, notes on the external modules it requires, and a modification history.

The modification history is especially important. One of the most vexing problems you can face is to find two versions of a program's source, and to be unable to tell which one contains the fix for a certain bug. If you record all fixes and enhancements under the "History" heading in the prologue, you can tell one version of the source from another.

The Global Data

It's my habit to begin the code of a program in the data segment, with the definition of all the constants, files, work areas, and messages. The usage message, if it is first among these, is handy for reference from the prologue.

In Figure 4-9, the usage message is labelled usage; it runs for several lines. Every screen-line of the message must end with a return-linefeed pair, and the message as a whole must end with dollar-sign character. This is because the usage message (and any other message used in an abort) is displayed using the BDOS's type-a-message function, and it always types up to a dollar sign. If the dollar sign is missing, it will type, and type, and type, throwing any sort of garbage to the screen, until finally, somewhere in storage, it finds a random dollar sign.

The variables used in the main body of the program are defined in this section as well. There are three of these in Figure 4-9 - ntoken, ctoken, and cbyte. They are used in the main section of the program.

The Main Loop

Every program has a main loop, a top level of the program that determines what things will be done, in what order, and when the program is finished. The source of the main loop of emit appears in Figure 4-10. In a simple program, the main loop might be the only loop, but in emit, much of the processing has been pushed out into subroutines that are called from the main loop.

The code in Figure 4-10 follows the pseudo-code of Figure 4-5 closely. In fact, I used the lines of Figure 4-5 as a skeleton for it. I concatenated those lines to the first draft of Figure 4-9 and inserted the assembly language code between them, paging back to the global definitions to add variables as needed.

There are some assembly language tricks worth noting in Figure 4-10. The statement

could have been written just as well as two statements,

and might be better so. The effect of the two sequences is identical, but the first is one byte shorter and microscopically faster. One byte is a trivial space and, since this statement is executed precisely once in a run of the program, the time saved is meaningless. The same trick could be justified if it occurred in the heart of a loop that was executed thousands of times.

The bytes ntoken and ctoken are used to regulate the main loop. The first holds the count of command operands, while the second holds the number of the operand that will be processed on the next pass. When the second exceeds the first, processing is complete.

The bytes are compared following the label for. Follow the way that register HL is used to address the pair of bytes. The code sequence

could as well have been written

and perhaps ought to have been. Once more we are saving one byte of code and a few microseconds of time. This section of code is executed as many times as there are command operands, so in a typical run it will save less than a hundred microseconds. That is an insignificant optimization, and it is obtained at a steep price. If the ntoken and ctoken variables were not defined adjacently and in that order, the code wouldn't work! That is, incrementing HL from ntoken would not bring it to point at ctoken. Again this is code that can only be justified in a section of a program that will be executed many thousands of times per run. I have a bad habit of making these useless optimizations at inappropriate points; I'll try to do better as we go on.

The program might discover that the first byte operand, operand number two, doesn't exist. In that case, the main loop will end as soon as it starts, and the program will arrive at label donefor with its count of decoded bytes equal to zero. That's fine; every program should "do nothing gracefully"; if this one has nothing to emit, it emits nothing, and ends.

Normally it will have decoded some bytes. The count of them will be in register B - which plays the role of the pseudo-code variable "j" - and their values will be in the array stuff. The body of emit ends with a short loop that picks up each byte and writes it to the file dest.

The line that does the writing,

deserves a look. All of the file and string macros in the toolkit allow register notation in this form. The first parameter of a file macro is always the designation of a file definition. In this case, it's the file dest, so the line could have been written

However, if it had been, the macro would have generated the code to save the contents of register DE, load it with the address of dest, and restore it after the operation. In Figure 4-10, register DE is loaded with the file's address outside the loop and the +D parameter tells the macro it needn't bother.

The parameter +A is essential, not optional. If we wanted to write a specific byte to the file - the ASCII tab code, for example - we could do it with the line

specifying a constant value. But in Figure 4-10, the byte value to be written is unknown; it is whatever happens to have been decoded and stored in stuff. That value has been loaded into register A, and the parameter +A tells the macro where to find it.

There are two toolkit macros that will write a single byte to a file: fputchar and fputbyte. As their names suggest, one is specifically for writing ASCII character values, while the other is for writing nondescript bytes of any sort. They make different assumptions about the use of the file that is being written. The fputchar macro assumes a CP/M text file is being created; if we give it a return character, it obligingly writes a linefeed character as well. That way, a program can end a text line with a single operation.

The macro being used here, fputbyte, makes no such assumptions. That is just what emit wants. It is supposed to write exactly and only the bytes that are requested by its command operands.

Setting Up the Device

The skeleton of emit is visible in Figure 4-10, but the program's flesh is in the subroutines it calls. The first of these subroutines, checkdev, is called only once. It is a subroutine only to get it out of sight so as to clarify the flow of the body. Its text appears in Figure 4-11. It contains our first uses of table lookup and of string copying.

As we decided earlier, checkdev verifies the first command operand by looking it up in a table of valid operands. The table is defined in a short data segment at the head of the subroutine. A string table is defined in two steps. The strtable macro defines space for the array of entry-addresses. Its operand is the number of entries the table will have.

Each entry is defined with the strentry macro. Its parameter, like that of strconst, is a string constant which it defines in storage. But strentry has an additional job: it moves the assembler back to the next slot of the array defined by strtable and assembles there the address of the string constant. Thus a table is defined by a call of strtable followed by a series of calls on strentry.

A table is searched by the executable macro strlook. In Figure 4-11, the program gets the address of the first command operand as a string, and uses strlook to look for that string in the table. If it is not found, the Zero flag is false afterward. Here, if the operand string matches an entry of the table, it specifies a writable CP/M device. The code assigns the string as the name of a file and opens the file for output.

If the operand isn't valid, checkdev must abort the program with an informative message. It does that following label baddev. The informative message will be

where FRUMMAGE is whatever the operand consisted of. It takes a bit more trouble to echo a bad input within a message, but it makes the message a great deal more helpful, since it is immediately apparent how the program interpreted the operand.

The abort message is constructed from two parts - the incorrect operand and a constant string - and both are strings. The code at baddev builds the message in the stuff array's space, since stuff won't be of any use now. The strcopy function copies a string to a space. Here it is used to copy the operand string to the stuff space.

The constant part of the message is appended to the operand string using strappnd. That macro takes two strings and appends the second to the first, making a single, longer, string. In this case, the second string is the string constant abdev, defined in Figure 4-9. That constant ended in a dollar sign, as is required of any message used in an abort.

Handling Bad Operands

It's especially important to repeat the incorrect operand when we report an invalid byte-token (Figure 4-12). Imagine the frustration of a user who types emit with twenty operands, only to be told "Invalid operand." "Which operand, dummy?" he or she would shriek. This is how programmers accumulate bad karma. A programmer who doesn't want to be reincarnated as a cockroach will take care to echo the offending operand as part of the message. It would be even better if emit checked every operand and issued a message for each bad one. It doesn't; it aborts on the first one it can't handle, so the user will have to discover his or her mistakes one at a time.

The badbyte code in Figure 4-12 is called as a subroutine, but that's a sham. It always aborts, ending the program, so it can never return to its caller. However, when it aborts, the address of its caller is on the stack. If we were debugging emit with a program like sid, we could set a trap at the entry to badbyte (or at the public label +ERROR where all aborts go to happen). Then we could examine the stack to see where the abort was initiated.

Handling Numbers

There are three types of operands, and the processing of each has been pushed into a subroutine. The code for handling numeric operands is shown in Figure 4-13.

The operand that begins with a digit should end in another digit if it is decimal, or in the letter "H" if it is written in hexadecimal. The code in Figure 4-13 checks this first. It uses the strend macro to advance the string address in register DE until it is pointing at the null byte that ends any string. Decrementing DE yields the address of the byte preceding the null, the last byte of the string.

If that byte is "H," the code invokes function straxbw. This one of a number of toolkit functions for converting between binary values and numeric characters. The names of these macros encode their functions according to this scheme:

• ax means "ASCII hex digits"
• ad means "ASCII decimal digits"
• bw means "binary (unsigned) word"
• sw means "signed (binary) word"
• bb means "binary byte"
• lw means "long (4-byte) unsigned word"

The source of the conversion comes first, the destination second, in the macro's name. Thus straxbw converts ASCII hex digits to an unsigned binary word; stradbw converts decimal digits to an unsigned word; strswad converts a signed word into ASCII digits; and so forth. Not all combinations are implemented, since not all are meaningful.

The code in Figure 4-13 uses one of two of these macros to convert the numeric operand to binary in register HL (the destination by default). The result must be tested to see if it can be accomodated in a byte. After all, there's nothing to prevent the user from entering

The test is to check the most significant byte of the result; if it is zero, the value fits in a byte.

When it does, the decoded byte must be saved in array stuff and counted. In the pseudo-code, we indicated that with lines like

That's how we would do it in a high-level language like Pascal. Subscripting an array is more difficult in assembly language. It could be done by loading the address of stuff and adding the count of bytes to it. That comes to only a handful of instructions, which could have been put into a subroutine for use from several places.

What I chose to do (almost without thinking) was to carry the address of the next slot in stuff in a separate variable, cbyte. That address has to be incremented each time a byte is stored, when the count is incremented. You can see it being done at the end of Figure 4-13.

Handling Literals

The second type of operand is the quoted literal. The code to handle that type is shown in Figure 4-14. It begins much like the numeric code, finding the last byte of the operand, but it has a different purpose. We decided that the user could, but didn't have to, close a literal with a quote. Here the code is checking to see if there is a closing quote, and obliterating it if so. That shortens the operand string by one byte, and reduces the two cases to one case, that of the unclosed quote.

Having done this, the code in Figure 4-14 checks to see if anything is left. If there is, all of the one or more bytes must be copied to the stuff array. The process is much like that of storing a numeric byte, but is repeated in a loop.

Handling Names

The final operand type is the named character. These, we planned, were to be decoded using a lookup table. The code that does it appears in Figure 4-15. It is dominated by a large data segment, in which a 36-entry table of names is defined.

Each table entry is followed by a single byte, the value of that name. The code takes advantage of these bytes when it invokes the strlook with the lines

The second operand of strlook is the address of the table to be searched. If it is given as a label, or merely as +H meaning "the address is in HL, use it," the only result of the lookup is to set the Zero flag true or false.

Giving the operand as +Hupdate tells the macro, "the table's address is in HL, use it, but don't save HL for me - give it back the way the lookup code leaves it."

The lookup support module leaves HL pointing to the null at the end of the last table entry it examined in its search. If the search was successful, that entry is the one that matches the search string. And, because of the way the table entries are defined, that address is just one less than the byte that contains the matching value of the name. It can be picked up and saved in stuff.

SUMMARY

Building the emit program has exercised our design methods and many of the more interesting toolbox functions. If you are still new to assembly language, emit is a good program on which to practice your code-reading skills. Work through it line by line, referring to a manual or book that explains the use of each instruction, until you feel confident that you understand what the program is doing. In succeeding chapters we will discuss the program code in less detail

5 DISPLAYING FILES

These considerations lead us to the plan shown in Figure 5-1. It expresses the idea that we can make two lines -- twice 64, or 128 bytes -- before we have to check for end of file. But it could use some elaboration. Displaying a line is no problem; fputline user,line will do it nicely. But preparing a line for display is the heart of the program, and the problem of discovering end of file needs consideration.

A plan for displaying a line is shown in Figure 5-2. It expresses the idea that a line is formed by reading and translating exactly 64 bytes from the file, and appending the printable characters to the display line.

The only characters that need translation are the control characters. They are easily identified; their byte values are less than that of the space character. Well, perhaps it isn't quite that easy! The DEL character, byte value 127, is also a control character. It has no printable representation, so it, too, should be translated.

Furthermore, certain word processors have the unfortunate habit of sprinkling text files with what should be ordinary ASCII characters, but which have their high bits set. What should cdump do with these? It could treat them as control characters, displaying them as dots. That's reasonable, since a byte with a value greater than DEL's 127 has no printable representation. (No standard representation, anyway. Lots of devices will print or display different symbols when sent bytes greater than 127, but no two agree on what symbols to use for what bytes.) On the other hand, the user might get more information about the file if such characters were reduced to ordinary ASCII and then translated. That would reveal more meaning in some files, at the cost, in others, of displaying characters where no character was intended. The plan in Figure 5-2 adopts this latter course.

Opening an Input File

One line of Figure 5-1 needs attention. It says, "validate filespec, assign it to input, and open it." There are several steps that have to be taken to do this. And from here on, most of our programs will have to read from a file named by a command operand, so this is going to be a problem we will face again and again. It's a good application for a separate module that we can use over and over.

What does it take to prepare an input file for use? The first step is to assign the command operand string to a file definition with the fassign macro. Its return tells us whether or not the operand is a valid filespec. If the operand was invalid the program should abort, but the ending message should echo the invalid operand.

The operand might be valid by the generous rules of CP/M, but it might still be ambiguous; that is, it might contain a question mark or asterisk so that it refers to more than one file. Such a filespec is of no use for input. Under CP/M Plus, an attempt to open such a file is illegal and will terminate the program with a CP/M error message. Under CP/M 2.2, we can open an ambiguously-named file, but we can't predict what file we will end up reading; it will be the first file in the disk directory that happened to match the name.

The fassign macro reports whether the filespec was ambiguous. If it does the program should abort with an informative message -- again, a message that echos the operand the way the user typed it.

When neither of these conditions interferes, the file may be opened for input with the freset macro. The code that supports this macro reports back whether or not there is any data to be had from the file. There is data to be had if the file is a disk file that has data in it, or if it is a device that is capable of input. The file can produce no data if it doesn't exist at all; or if it is a device that can't do input, such as PUN:; or if it is a disk file with no data in it.

All of these last three conditions are lumped into the single flag returned by freset. In most cases, they all mean the same thing: that there is nothing for the program to do. The usual response to such an empty-file report is to terminate, once more with an message. However in this case the message has to be worded more vaguely.

It doesn't take a great deal of code to perform these steps, but it it's better to do it once for all and put the results in a separate module, one we might call openin. The code for the module appears in Figure 5-3.

The code in Figure 5-3 demonstrates two new things. The first is a common trick, that of anticipating a possible outcome in order to avoid writing extra jump instructions. Consider the lines that go

The point of them is that, if fassign reports an error, we are to transfer to error with the address of message inval in register BC. The lines could have been written this way,

with the business of loading the address of the error message being deferred until we know that it is needed. That is just how most compilers would code the equivalent "if" statement. But the second version requires us to invent a label to name the good case, and to write two jumps. We avoid that by loading BC in anticipation of having to jump, then jumping only if necessary. The trick is used in two other places.

The second thing is the construction of a string from pieces. The abort message is built up from four parts -- the operand string, a constant, whatever string is addressed by register BC, and another constant. This requires four macro calls. The register operand +Dupdate operand says, "DE has the address, and don't save it -- let the function update it for me."

The string functions usually update the destination pointer so that it points to the null byte at the end of the string. The strappnd operation has to advance to the end of the destination string before it can begin appending to it. By allowing the string address in DE to be updated each time, we keep it pointing at the current end-byte of the string, reducing the amount of work the support functions have to do. This gains a meaningless savings of time -- meaningless because the speed with which a program goes to abnormal termination doesn't matter a bit!

Detecting End of File

Thus far we have planned cdump as if the input file would go on forever. That's the easy way to think about it. Things proceed in a nice, regular way as we go along through the file, and the plans reflect that regularity.

End of file is a discontinuity, an abrupt break. The program must stop what it has been doing and do something else (in this case, terminate). We simplified things by having the openin module abort if the file was empty. That eliminated the case in which end-of-file turns up immediately; since CP/M stores files in units of 128 bytes, we can be confident that there will be at least enough data for the first pair of lines. However, once that pair has been processed, we have to find out if there is data to make the next pair.

Programming languages vary in the way they present end of file. Some treat it as a surprise, an error condition that might crop up during an attempt at input, and supply a mechanism for jumping elsewhere in the program when it arises. PL/I and COBOL take this approach. In those languages, you write code that says, "I don't believe end of file will happen, but if it does, go there."

Other languages treat end of file as an expected condition or state of a file. These languages provide a means of checking for the end-of-file condition before a read is attempted. Pascal is one such language; in it you are required to write the equivalent of "Is end of file true? If not, read."

The toolkit functions that read files do not anticipate end of file. If there is another byte in the file, fgetbyte will return it. Nothing special will happen even if that is the very last byte in the file. Only when it finds that no more data is to be had will an input function report end of file by returning the Zero flag true. This approach made the toolkit easier to write and more efficient in execution (and in fact no other approach is possible with files that are really devices), but it causes problems for a plan like the one in Figure 5-1 and Figure 5-2.

In Figure 5-1, we are assuming that we can test for end of file after reading the 128th byte and before trying to read the 129th byte. This is Pascal-style programming; it assumes that there is a way to look ahead and see the end of file looming without actually attempting a read. Fortunately, there is; but imagine the consequences if there wasn't. If the only way to detect end of file was to attempt a read, then our whole plan would have to be turned inside out. The makeline routine (Figure 5-2) would detect end of file when it tried to read a byte; it would have to end early and return a signal; then the main loop (Figure 5-1) would have to notice the signal and break off its loop early. As an exercise, work out a plan that would work under these conditions. There are a number of dodges you can work, but the result will always be more convoluted than what we have now.

The feof? macro (the Digital Research assemblers permit question-marks in macro names) will test for impending end of file. It reports back with the Zero flag true if the next input request will fail because of physical end of file; that is, if there are no more bytes to be had at all. This function gives us just what we need to implement the "until" test in Figure 5-1.

The feof? function can be used with text files as well as binary ones. When the file is not at its physical end, it returns a copy of the next byte in register A so that the program can detect an impending logical end of file -- the control-Z character.

This function can only work correctly only on disk files. Think about it: what meaning could "end of file" have when applied to a device like CON:? On one hand, a device is always at end of file, since there is no next character ready until the device produces one, and it might not. On the other hand, it is never at end of file because it is capable of producing another byte. This is one area in which disk files and devices can't be treated alike. The feof? macro always reports end of file on device files, while input functions never do (they just wait for a byte to arrive).

Detecting User Impatience

There is yet another factor that our cdump plan ought to take into account (gee, it looked like such a simple program!). As the plan stands, cdump is going to finish the display of any file it starts on. Suppose the user sets it going on a large file, and then decides that the display is useless. Maybe the first few lines of the display answer the user's question, or maybe the wrong file was named. Whatever the reason, the program has started and now the user wants to cancel it and get on to something else.

The usual way to cancel a CP/M program is to press control-C, but that is only effective when the system is paying attention to the keyboard. The BDOS only monitors the keyboard for control-C during an input request (cdump makes none) or while the display is frozen by control-S. Our user could cancel cdump by pressing control-S and then control-C. But the user can cancel system commands like type and dir by pressing control-C alone, and a display program like cdump should be just as accomodating, if only for consistency.

We can incorporate this need in the plan of Figure 5-1 by adding another "until" condition:

There is a toolkit macro, testcon, which tests for pending keyboard input, much as the BASIC function INKEY$ does. It will allow us to implement the additional test.

Coding Cdump

Once all the planning has been done and the openin module has been coded, the rest of cdump is easy to implement. Its code appears in Figure 5-4.

As will often be the case, the assembly source follows the pseudo-code plan very closely; so closely, in fact, that it was created by editing the pseudo-code file and filling in the necessary assembly statements between each line. (I don't mean to say that they were filled in quickly or thoughtlessly! I worked back and forth over the file many times, reading and revising. But the pseudo-code lines supplied the skeleton.)

Observe the use of registers HL and DE in the subroutine makeline. This routine has two objects to keep track of: the file input and the developing display string in line. It takes bytes from the file with fgetbyte, which returns the next byte in register A, and it appends translated bytes to the string with strput.

Both of these macros could have been given the names of their objects as parameters, as in

But the code of makeline goes to the trouble of carrying the addresses of file and string in registers. Having set up the registers, it could have appended it to the string with

That would have saved the macro's generation of code to load the string's address in register DE. But what the code uses is the operand +Dupdate operand causes the macro to not preserve the starting value of DE, leaving it instead as the support function returned it. Thus the register traces the end of the line as it develops, saving 64 scans from the front of the line to its end in the course of the loop. This time the extra complexity really does save some time.

THE BDUMP PROGRAM

The cdump command is useful for checking the contents of files which we expect to contain only text. But there are times when we want to look into files that aren't supposed to contain text, files that we expect will consist of binary data. Cdump doesn't tell us enough about such files; they are full of binary values that it renders only as dots.

Specifying Bdump

We need a binary-dump program, bdump, which will show us the precise contents of a file in all their hexadecimal glory. Binary files don't have any internal markers to divide them into convenient sections, as text files are divided into lines, so bdump may as well divide them into the 128-byte chunks that CP/M calls "records." These don't usually correspond to the records of the file as they are defined by the programs that create or use such a file, but they are the only divisions that are common to all binary files.

The bdump program, then, will display a file in 128-byte groups, each group identified by its relative record number -- the number of the record within the file, counting from zero. The contents of the file will be shown in hexadecimal and in ASCII.

There is more than one way to display data in hexadecimal. The most common way is to spread it out on a line, with a space between each byte and with the ASCII values following:

That format uses one line to display just 16 bytes of data. Another way is to invert the format, showing the hexadecimal digits in columns below their ASCII translation:

This vertical format allows us to put 64 bytes across the screen. However, it takes three lines to show those bytes, and requires a blank line between each 64-byte display to avoid confusion. The final result is the same; both formats use up eight screen lines in displaying 128 bytes of data. The horizontal format is slightly easier to create using the toolkit macros, so we'll use it.

Bdump is much like cdump in its outline. It must open a file, read it, and display it. A draft plan expressing this appears in Figure 5-5.

That plan merely repeats the obvious, but there is virtue in writing it down anyway. I have often made the mistake of wading into the details of a program I thought would be just like some other, only to discover that it wasn't; that something in the specification mandated a different plan. Now that we have examined Figure 5-5 and decided that, yes, it is just like cdump's plan and so should present no problems, we can set it aside. What we have accomplished is to eliminate all of the problem except the line "get 128 bytes and display it," and now we can focus on that.

It's no problem to get 128 (or any other number) of binary bytes from a file; there is a toolkit macro, fgetblok, for just that purpose. Having gotten the data, we must display it in eight lines with a record number at the end of the first one. That leads to the plan in Figure 5-6.

The first line has to be treated differently because only it will contain the record number. The remaining lines can be handled in a loop. However, the parallel construction of "process 1st 16 bytes" and "process next 16 bytes" is no accident. Most of the first line will be created by the same actions that create the whole of the other lines, and those actions can be a subroutine. Thus we reduce the problem "get 128 bytes and display it" to one of "process 16 bytes into line."

Each display line has two parts, a display of hex numbers and a display of ASCII text. The hex numbers will reflect the exact values of the bytes from the file, while the text display will show them in the way that cdump does -- with characters for the printable bytes and dots for the ones that aren't.

I can think of two ways of building such a display. The first way is to build a single display line by going over the file data twice. This method is outlined in Figure 5-7.

The second way is to process each file byte once, putting it into each of two strings, and then to concatenate the strings. This method is outlined in Figure 5-8. In both figures, the notation "translate(x)" refers to the same subroutine that we used in cdump.

In this program, it doesn't much matter which of the methods we use. In a higher language like C or Pascal, we'd probably favor the second plan because it has one less for-loop. When I look ahead to the assembly language encoding of each plan, however, I can see that in the first plan there is one less thing to keep track of at any one time. That is, in the first plan the program will only have to keep track of its position in the file bytes and in one string, while in the second it has two string-addresses to juggle.

Coding Bdump

The assembly code of bdump appears in Figure 5-9. As usual, it follows the pseudo-code plan. However, I made a change as I wrote it. The structure of bdump is nested deeply enough to be confusing. The structure could be summarized this way.

In such a structure, it ought to be possible to understand any one level independent of the others. That's the only way to keep the program understandable and maintainable. It is always necessary to understand the abstract function of the lower routines that are called, but that is the only interlevel information that should be required. It's an important principle of software design that if you can't read a routine at one level without referring to the code in levels above or below it, the structure of the program is faulty.

The levels of a program are most independent when the only flow of data between levels is through subroutine arguments downward and subroutine results upward. Any other method of exchanging data between levels confuses the relationship between levels, and can cause a change in the code at one level to propogate up or down to another level. There are several kinds of inter-level relationship that can confuse a program's structure, and some of them are very subtle. But the worst is the sharing of named variables.

Until now we have been casual about this principle, but the structure of bdump is elaborate enough that we should pay attention to it. There are two key tests for level independence. The first is, "Could this subroutine be completely rewritten without causing a change in any program that calls it?" The second is the reciprocal query, "Could the program that calls this subroutine be completely rewritten without causing a change in the subroutine?" The chkops and openin modules satisfy both; they depend only on the arguments passed to them in registers. So does the translate subroutine from cdump.

The show128 routine planned in Figure 5-6 and the show16 routines in Figure 5-7 and Figure 5-8 do not. Each depends on a variable that is defined at a higher level. Show128 assumes the existence of a file named input; show16 relies on a string-space named line. In both cases, the second test fails -- the calling program couldn't be completely rewritten without changing at least the names used in those subroutines.

Is this merely a philosophical quibble? In a program as small as bdump, perhaps so. But no; the show128 and show16 routines are potentially useful in other programs. Someday we might want to extract them, make modules of them, and use them with some other program. We would not be able to because of those cross-level name references. They would have to become external names in a module; if the code were copied bodily into another program, that program would have to define a file and string-space with the identical names and use them in the identical way. Or suppose you worked in a group of programmers and wanted to make these routines available to the others: imagine what the documentation for these little modules would look like. (In fact, over-complicated technical documentation is as often the fault of poor structure in the thing documented as it is the fault of the writer.)

It's usually easy to fix a modularity problem at the design stages. I fixed the problems in show128 and show16 as I wrote the assembly code. I made sure that all the resources they needed were either private to them, or handed to them in registers. It didn't cost anything in program size or speed.

SUMMARY

We've designed and coded two simple file-display programs, but they turned out not to be quite as simple as expected. Designing them led us to consider how to: open an input file named as a command operand, detect end of file, and cancel a program when the user tires of it. And even a small program proved to have a structure complex enough to motivate some attention to proper modular design. In the next chapter we'll apply these principles to a more complicated display task

6 TABBIT AND UNTAB

That leaves two cases: x either contains an ASCII CR, indicating end of line, or it does not. If it does not, the blanks summarized in count are necessary white space and must be written. If it does, they are redundant and may be skipped. If we put all these things together, we arrive at the plan shown in Figure 6-1.

Column Position and Tab Stops

Just one problem remains: how can we know how many columns remain to the next tab stop, regardless of the current position in the line? Well, suppose that we know what the current position is, as a count of columns beginning at 1 in the left margin. Now enumerate all the answers for the first dozen columns:

It's like a question from a sophisticated IQ test: "What expression, applied to the numbers of the top line, will yield the numbers on the bottom line?" The answer jumps out at you if you number the column positions, not from one, but from zero:

The expression we want is

where column is the current column position counting from zero.

The modulo, or mod, function crops up often in programming. Provided that we deal only with positive integers, x modulo y is simply the remainder after dividing x by y, and is always an integer between zero and y-1 inclusive. Provided we number things starting from zero, the expression number mod y has the effect of folding all possible numbers back onto the first y numbers; as here the expression column mod 8 will fold any value of column back onto the first eight column numbers, 0 to 7.

This "folding" effect of modulo works neatly only when things are numbered starting with zero, and that explains why programmers so often use origin-zero numbering schemes. Thanks to modulo, we need consider only the first eight column numbers, and the expression 8-number yields the count of positions up to the next tab stop.

Modulo is particularly easy to implement when working with binary numbers and y is an integral power of two. Eight is such a power of two; as a result, column mod 8 amounts to nothing more than extracting the three least-significant bits of column. In other words,

have exactly the same result. No doubt that's why the CP/M tab increment is eight, not ten.

We are squeezing the unknown parts out of the plan. Now we have an expression that will set up our tab-producing loop, but it requires column as input. That variable must contain a running count of the current output column position. We could think of it as an analogue of the physical position of a print-head or cursor as it displays the file. Every character that we write to the output file must have the same effect on column that it would have on the position of a cursor or print-head.

An ordinary character should make column increase by one. A CR should reset it to zero. A tab character should advance it to the next tab stop, and a backspace character should decrease it by one. The first of these are obvious, but backspace is a bit tricky. A real printer won't backspace out of column 1, so when writing a backspace code we mustn't decrement column lower than zero. (Of course, backspace is an unlikely character to find in a disk file, but if we disregard it, some user will apply tabbit to a file that contains one and report a bug. Besides, who says tabbit's input file has to be a disk? It might be CON:.)

Advancing column to the next tab stop amounts to rounding it up to an even multiple of eight. Since eight is a power of two, we can do that with the expression

When we augment Figure 6-1 with statements to maintain and use column, the result is Figure 6-2, and the plan for the body of tabbit is complete.

Initialization

The plan in Figure 6-2 is complete for the body of the program, but it omits the initialization and termination steps. What needs to be done? The first step, as in previous programs, will be to check the number of operands and terminate with a usage message if necessary. The chkops module will handle that. Then the input file must be assigned and opened. That process will be similar to the same step in the cdump and bdump programs. The openin module would suffice for it.

The third step of initialization will be to open the output file. This will be a new process for us. We will want to assign the second command operand to a file, but we will want to include in the assignment a default file -- the assigned, opened input file. After the assignment, the file must be opened with the frewrite macro to prepare it for output.

How shall we handle this step? It should be generalized and isolated in a module for use with other utilities. However, the assignment of an operand string to the output file is subject to the same two errors that can afflict the input file; that is, the operand could turn out to be an invalid filespec, or it could turn out to be ambiguous.

The openin module that we created in chapter 5 already contains apparatus to construct error messages for these situations. With its code, string constants, and working space, this apparatus occupies a couple of hundred bytes. It would be a shame to duplicate all that in another module, causing all utilities to contain two copies of those error messages. Instead, let's create a module that performs both kinds of opens that a utility needs.

The code of this module, openut, appears in Figure 6-3. I created it by editing openin. The openin module is still useful; it contains the minimum function needed by a program that only reads a file. Many such programs can be written.

The openut module in Figure 6-3 is a superset of openin. It contains a public function named openin that does exactly what the simpler module does -- assign an operand to a file and open it for input, aborting if the file is empty or not found. It contains an additional function, openou (public names are limited to six characters, unfortunately). This function assigns an operand to a file with a default, and opens the file for output.

The operand-assignment operation is common to both of these functions; it has been extracted into a small subroutine. The business of building an error message has been disentangled from the rest of the code as well; in fact, the structure of openin has been cleaned up generally to make openut.

CODING TABBIT

The plan for tabbit was so thorough that the assembly-language source fell into place quickly and easily (it appears in Figure 6-4). It opens with calls on chkops, openin, and the new openou, and closes with an fclose of the output file. The code to implement Figure 6-2 falls between these, but I chose to make that a subroutine so as to make the main line of initialization and termination clearer.

That subroutine, process, is another direct translation from the pseudo-code plan to assembly language, but a bit more complicated than previous efforts. The architecture of the Z80 CPU complicated matters at three points.

A pseudo-code loop or if statement must be implemented with conditional jumps. The program must prepare the CPU's flag registers properly before taking a conditional jump. And almost the only way of setting the flags is to perform some operation in register A. For instance, the pseudo-code

might, if "count" is being carried in registers HL, become the assembly statements

That's fine, so long as there was nothing of interest in register A beforehand. In tabbit, however, I was carrying the all-important variable x, the current nonblank input byte, in register A. At three points it had to be set aside temporarily while register A was used to set up for conditional jumps. In one case, the variable x was set aside over a long stretch of code by pushing it onto the stack; in two others it was tucked away in another register that was unused at that point. Find these points in Figure 6-4 and then ask yourself what they imply for the maintainability of the code. Imagine someone a year from now wanting to add a new function to tabbit, a function that needs another register. Might these temporary saves of x be missed, or fouled up somehow, so as to cause a bug? What could be done to make things easier for that person?

Performance

The main reason for using assembly language is efficiency; that is, getting a smaller, faster program. It might occur to you that Figure 6-2 is so detailed that it is almost ready for compiling in C or Pascal as it stands. What is gained by translating it into assembly language?

In order to find out, I translated Figure 6-2 into the C language and compiled it with a popular 8-bit implementation of C. The translation was straightforward, although not as simple as I thought it would be. You can read it in Figure 6-5. Here are the results.

The C source file is considerably shorter at 1.4 kilobytes (Kb) versus 4.25 Kb. The difference would be less if the C file had a proper prologue and more comments (as it should); even so, the assembly language will always be at least twice as large (and will presumably take twice as long to compose, all else being equal).

The programs took about the same length of time to compile (assemble) and link -- the assembly version was ready to run after 60 seconds, the C version after 73 seconds. This relationship would vary with the C compiler used; some are faster and some slower than the one I used. In any case, the cycle of edit, compile, and test takes about the same length of time for either language.

The assembly program was smaller, as it should be. Tabbit in assembly language, linked with all the toolkit modules it uses, comes to 4.0 Kb. The C version, linked with this compiler's run-time library, came to 9.8 Kb, more than twice as large. This ratio would have been much larger in favor of assembly language had I not been careful to avoid the printf() function of C which requires elaborate library support.

In execution the assembly program was much the faster. It processed a 5.3 Kb input file (its own source with all tabs converted to blanks) in 5.8 seconds; the C program took 9.8 seconds to process the same file.

SPECIFYING UNTAB

We've done tabbit; now let's address the opposite problem. Suppose that we have an ASCII file the contains tabs, and we don't want the tabs. Perhaps we ran tabbit on a file and then realized that its contents would be rearranged at output, making the tabs invalid. Or perhaps we have downloaded this file from a mainframe system that defines a different tab-increment than CP/M's eight. We want the tabs replaced by the blanks that they stand for. Now in fact, the pip program will do exactly that, so it isn't really necessary to write a special program for the purpose. However, it is an interesting problem. In particular, it gives us an excuse to write a utility that takes an option.

The untab utility will processes an ASCII file to remove all tabs and replace them with the blanks that they represent. It will assume that the tabs in the file are based on some regular increment. Unless the increment is specified otherwise, an increment of 8 (the customary CP/M increment) will be used. However, a different increment between 1 and 255 may be specified as an option in the command line.

The syntax of untab is

A>untab infile outfile [increment]

The file references are given as for other utilities. Omitted parts of the output reference are supplied from the input reference. If the output reference is omitted entirely, the input file will be replaced.

The option [increment] may be omitted. If it is, the command will assume a tab increment of 8. A different increment may be specified as a decimal number enclosed in square brackets. For example,

will produce "thatfile" from "thisfile" using a tab increment of 10.

The Syntax of Options

It is only recently that Digital Research has attempted to standardize the syntax of options in commands. Think of the variety of ways of coding options. The asm assembler takes parameters as single letters in the filetype position. The mac and rmac assemblers take two-letter parameters following a dollar sign. The use of a hyphen is becoming popular in some circles. Other writers have used the slash as a delimiter for parameters. Indeed, almost every ASCII punctuation character has been used to distinguish an option from a filespec by some program or other. Which one ought we to use? After some thought, it seemed best to me to use the square brackets.

If you are using CP/M 2.2, you are used to giving options within square brackets, but only to pip, as for instance when you enter

However, the newer Digital Research operating systems -- MP/M 2, CP/M Plus, and Concurrent CP/M -- use these square brackets in many commands. The link and lib programs that we use with the rmac relocating assembler follow this custom as well.

The toolkit functions were designed with the square-bracket usage in mind. In particular, fassign takes the left and right square-bracket characters to be filespec delimiters. Either one stops its scan over a filespec; the contents of a string preceding the bracket are part of the filespec but the bracket itself is not.

This fits in well with the utility convention for filespec operands. If the outfile operand is omitted, the option will appear as the second command operand. We needn't make a special test for this case; we can pass the operand string (of, say, [10]) to fassign and it, finding nothing to the left of the filespec delimiter "[," will treat the operand as a null string for file-assignment purposes.

DESIGNING UNTAB

As we did with tabbit, let's defer planning the initialization steps and go to work on the processing loop. Unlike tabbit's processing loop, that of untab can follow the simplest utility model:

In this case, "doing something" with an input byte comes down to two cases: the input byte is a tab, or it isn't. If it is a tab, we want to write one or more blanks in its place. We can formalize the idea this way.

The code is simpler than tabbit's because no look-ahead is needed. In tabbit, the appearance of a space marked a point at which the program might be able to substitute a tab. The uncertainty could only be resolved by reading further in the file. In untab, the appearance of a tab signals a point at which spaces will be substituted.

Ah, but how many spaces? Two factors determine the answer -- the tab increment, and the current position within the file. The latter is a column count, just like the one we maintain throughout tabbit. The tab increment will be either eight, or the number given as an option in the command.

If we assumed a fixed tab increment of 8, the answer would be simple to obtain. It would be

the same expression that we used in tabbit to compute how many positions remained to a tab stop. But that expression is just a special case of

where tabincr is any regular tab increment. In tabbit we used a fixed increment of 8, and that made modulo an easy function to implement. Here we must take column mod tabincr when tabincr may be any number from 1 to 255. Since both are positive integers, "modulo" and "remainder" are identical (remainder and modulo are not the same function when either argument is negative, a point that is often overlooked). We have will have to perform a division of a 16-bit column value by an 8-bit tab increment. The toolkit functions contain such a divide routine.

With these things in mind, we can lay out a fairly detailed plan for untab (Figure 6-6). Two lines are still fuzzy in that plan. One of them is "adjust column for the effect of x." That's just shorthand for the same set of ifs and elses that appear at the end of tabbit; there are no surprises in it.

Processing the Option

The other fuzzy area is expressed by the line "extract tab-increment from option." That problem breaks down immediately into two problems: (1) locate the option operand-string, and (2) if there was one, extract a number from it. At first glance, neither of these steps looks too hard.

Finding the option operand isn't too hard. As we have specified the command's syntax, the option must be the last operand. We wrote the chkops module so that it returns in register A the number of operands that appeared in the command. If there were three operands, the option operand is the third; if two, it's the second. So a call on the toolkit function tailtokn, passing the same number that chkops returned, will yield the address of the last operand-string.

Of course, if the user enters only the two filespecs, the last operand string will be the outfile operand, not an option. We can eliminate that case by looking for a left-bracket character as the first byte of the string.

Once we have the option-operand as a string, it is not difficult to extract a number from it. We must step over the opening bracket character, then use stradbw to convert ASCII digits to a binary word. Then we should check the result to see if it is in the specified range of 1-255.

Problems With Options

All this is not hard to do, but it doesn't add up to a sophisticated user interface, either. Consider what the user might try, and how the program would react to it. For instance, the user might omit both file operands.

In this case, the program would ask openin to assign and open a file based on the first operand, [11]. But the bracket is a filespec delimiter to fassign, so the input filedef would be assigned a filename and filetype of all blanks; that file would not be found, and the program's response would be to abort with the message

That doesn't match the conventional idea of "user friendly," but at least it would alert the user that something is wrong.

Another possibility is that the user would run the option up against the output filespec, as pip requires.

In this case, the two files would be opened correctly, but our scheme for locating the option would fail. The toolkit macros split the command "tail" into operand strings only at blanks or commas, so this command has but two operands: thisfile and thatfile[16]. The program would check the second operand for a leading bracket, fail to find it, and continue with the default increment of eight instead of the desired 16.

A third glitch appears if the user inserts any spaces into the option.

Now there are not three, not four, but five operands, and chkops will abort the program with the usage message.

Other erroneous combinations are possible, and it would take a very sophisticated program to analyze for all possible errors. Such analysis might be easier if the toolkit function savetail were designed to treat the square brackets in special ways. It could, for example, force any left- or right-bracket to become an isolated, one-character, operand. Then a program would receive all possible cases of bracketed options as if they had been entered as space, bracket, option, space, bracket. (But consider the effect of such a rule on a program like emit!)

This is the not case, however; and although under the existing scheme it is possible for a utility to look fairly stupid, I don't feel disposed to fix it. Perhaps you would like to put a more intelligent option-analyzer into it.

CODING UNTAB

The assembly code of UNTAB appears in Figure 6-7. Like tabbit, it consists of a main-line routine that performs initialization and termination, and a subroutine process that implements the pseudo-code plan. Another, smaller subroutine locates and extracts the tab-increment option.

For the most part, translating pseudo-code to assembly source is a straightforward business, very easy to do with a good full-screen editor. Begin with a unit, like a repeat-loop, and make assembly comments of it.

Insert a label at the top of the loop, and add the code that will implement the loop condition.

Then pick the next-innermost statement and implement it. Each form of pseudo-code statement has an arrangement of necessary labels and segments of assembly code that you can apply almost mechanically (just as a compiler would do). An if statement, for example, needs a false-label and (if it has an else part) an end-if label. Take this one, for example.

Before doing anything else, insert the necessary labels.

Then implement the condition of the if and the escape at the end of the then part.

The statements within the then- and else-parts may then be implemented.

This almost-mechanical scheme works, but isn't always desirable. Simple compilers for high-level languages do the same sort of mechanical translation, and they produce awful code. One example shows up in the process subroutine of Figure 6-7. Its repeat-loop contains only an if statement. The then-part of that statement is executed only when x is a tab, while the loop condition is x=CpmEof. Only the most intelligent of optimizing compilers would recognize what is obvious to a human programmer: if the then-part of the if is executed, the loop condition cannot possibly be true (and there are no true optimizing compilers available for microcomputers).

A mechanical translation of the if, such as the one outlined above, would have the then-part of the statement end with a branch to the end of the if, and thus to the loop-test which couldn't possibly be satisfied. In Figure 6-7 you will see that this redundant test has been short-circuited by a jump back to the top of the loop.

SUMMARY

We have built a matched pair of utilities and in the process have done battle with several issues in program design: handling defaults in command operands, opening files for sequential output, processing a stream of bytes with and without lookahead, and a less-than-perfect method of handling command options.

File-transforming utilities like these ("filters," they are sometimes called) are among the best candidates for assembly-language implementations. They are usually based on simple algorithms that aren't hard to code in assembly language, and when that is done, they usually reward us by being much smaller and faster than they would be in a high-level language. We will build several more in following chapters, but there are an endless number you could construct to the same pattern to suit your own needs

7 PACK AND UNPACK

I wrote a program (in a high-level language, since it would only be used a few times) that would read a text file and take a census of every digraph that began with one of (space, etaoinshrdlu). I ran it against files amounting to 250,000 bytes (the text of a book), and found the results that are summarized in Table 7-1. In that table, each row lists the eight letters that most often followed the letter that heads the row, in descending order of frequency.

This table is not to be taken as definitive for English text in general. It can't be; it is based on letter frequencies as they appear in one book by one author. Furthermore, only the first few letters in each row had distinct frequencies of occurrence. Once past the fourth follower-letter, frequencies were small and similar. This suggests that, given a different sample, while the first three or four follower-letters would almost certainly appear in roughly the same positions, the rest might be different. In the first row, followers of the space, the true second-place follower was "other"; that is, uppercase letters and nonalphabetics. Despite these shortcomings, the information in u is good enough to be the basis of an effective compression method.

This method searches a file for letters in the common set. It copies ones that are not to its output. When it finds one of the thirteen common characters, it tests the following byte against the appropriate row of u. If the second character is found, the pair of letters can be compressed into a single byte. The byte is formed from the number at the head of the row and the number at the head of the column.

SPECIFYING PACK AND UNPACK

The pack and unpack programs form a complementary pair. The purpose of pack is to compress a file of text, while unpack will restore a compressed file to its original form. A compressed file takes less disk space, so more files can be gotten onto a small diskette. However, a compressed file is useless for anything but storage; it contains many unprintable bytes and must be restored by unpack before being printed or processed by other programs.

The compression method of pack works correctly only for files of text in English (or another European language), expressed as ASCII bytes. While packing and unpacking a non-ASCII file will not harm it (no information will be lost), the result of packing such a file will not be smaller (and might be larger) than the original file.

Both programs are utilities and have no options. That is, their syntax is

For pack, infile is the text file to be compressed and outfile receives the packed data. For unpack, infile is a packed file produced by pack, and outfile is the destination of the restored text. Both programs use the "utility convention"; that is, omitted parts of the outfile filespec will be copied from the infile filespec, and if outfile is omitted, infile will be replaced.

DESIGNING PACK

The pack program is essentially a file-copy utility, but it cannot decide what to do with every byte based only on the byte's value. When the current byte is one of the common letters, it must look ahead one more byte to see if it has a compressible pair. This is a simpler problem than that presented by tabbit, where, when we found a blank, we had to look ahead as many as eight bytes before we could be sure whether a blank or a tab should be written.

Since pack looks at only two bytes at a time, it may as well carry two current bytes at all times. In other words, pack can look at its input through a window two bytes wide. When compression is not possible, it will deal only with the byte at the left of the window, then shift the window to the right. When it can compress the byte, it will deal with both bytes, then shift the window to the right twice. We can formalize this notion as a simple plan (Figure 7-1).

The Compression Code

Before going any further, let's establish the encoding scheme for compressible pairs. We are assuming ASCII input, and that implies that all, or anyway most, input bytes will be less than 128 decimal. Therefore we will reserve all output byte values from 128 to 255 for compression codes. That gives us 128 values to play with.

its high bit set on will represent a compression code.

Now we'll perform one of those shifts of view so common in systems programming. We'll stop thinking of these as numbers, and start thinking of them as the binary values stored in bytes, and specifically as patterns of eight bits. The numbers from 0 to 127 are stored as bit patterns from 0000$0000b through 0111$1111b, while the range we are claiming, 128 to 255, is stored as 1000$0000b through 1111$1111b. (The Digital Research assemblers permit us to scatter dollar-signs freely in numeric constants. Here we are using them to make the groups of bits easier to read.) In other words, the reserved values all have their high (most significant) bit set on. In a byte whose high bit is set, we have seven more bits to use for encoded values.

There are thirteen common characters to look for; it takes four bits to represent thirteen values; therefore four of the seven bits will have to be dedicated to encoding the first letter of the pair. The remaining three bits can represent eight numbers (from zero to seven), and will be used to encode one of eight following characters. A compression code can be described as a binary constant of 1$aaaa$bbb.

The four bits aaaa could be used to encode as many as sixteen first letters. However, once the most common thirteen characters are eliminated, the remaining characters found in English text show a distribution that is nearly flat and that varies significantly from document to document. In other words, the farther down the list we go, the less reliable our predictions about character rank become and therefore the less likely we are to achieve useful compression.

Furthermore, when we restrict the values of the bits aaaa to the range of 0-12, we leave some possible compression codes free for other uses. As things stand, a compression code might range from binary 1$0000$000 to 1$1100$111; that is, from 80h to E7h. The byte values E8h through EFh and F0h to FFh are free, and we can make good use of them for other things.

Allowing for Non-Ascii Data

The output of pack is to consist of uncompressed ASCII bytes (with high bits of zero) and compression codes (with high bits of one). But what shall we do if we find an input byte whose high bit is one? Such bytes are frequent in binary files, and they occur in the document files written by some word processors. They can't be compressed, but if we copy them unchanged unpack will take them to be compression codes.

The solution is to "escape" an offending byte; that is, to prefix it with a special code that says "take the following byte literally." Let's set aside the first of our unused codes, E8h, as a flag for non-ASCII data. When we incorporate that idea into Figure 7-1 we get the plan in Figure 7-2.

Take a close look at Figure 7-2. It seems quite redundant. Two branches of the if sequence end in identical statements, and all three end in the same action, c := next byte. That line at least can be factored out and moved to the bottom of the loop. And if the middle branch were to set things up so that b:=c was a proper action, that line could be factored out as well. If we do these things we get the tighter plan shown in Figure 7-3.

Input, Output, and End of File

The plan in Figure 7-3 is well advanced; we had better consider how the I/O actions of "write" and "next byte" will be implemented. When we specified these programs, we promised that they would be able to handle binary files without losing any information. That promise may cause problems. It means that "next byte" will have to be implemented with the non-ASCII input function, fgetbyte. There are several implications.

When we deal only with text data, we can use the ASCII function fgetchar and so receive two benefits. That function swallows a linefeed that follows a return, so that end of line is marked by a single byte rather than the return-linefeed pair that actually end a line of text. Pack, however, will be seeing both characters when it reads a text file.

Detection of end of file is more complicated with fgetbyte. The logical end of a text file is marked by a special character, control-Z (equated to CpmEof in the listings). There is no such convenient marker in a binary file; any byte value is possible, so none of them can be reserved to mark end of file. When fgetbyte finds there is no more data in the file, it reports back with the Zero flag true and a byte value of zero, but zero is also possible as data.

Consider Figure 7-3 in the light of these facts. How will we be able to implement the loop test, "until all bytes processed"? End of file could be discovered at any of the places where the program reads the next byte. There are two of these at the moment. If the last two bytes of a file form a compressible pair, end of file will be seen in the middle of the loop and again at the bottom, and all bytes will have been processed. If not, end of file will be seen first at the bottom of the loop, at which time the byte in b will remain to be processed. It would be decidedly awkward to figure out which condition obtains and to clean up the remaining byte in the second case. It could be done (for instance, by making "next byte" into a subroutine and in it, counting the number of times end of file is reported) but the resulting plan is not pretty.

Things would be ever so much simpler if there was a data value that meant end of file, as there is in text files. Then, so long as we made sure that that data value wouldn't participate in any compressions, the loop condition could be stated as until (b = end of file value). In other words, the loop could be allowed to run until that value had worked its way across the two-byte window, at which time all the preceding data bytes would have been dealt with.

It can be done. In the C programming language, it is done by treating byte values as integer values, and by using an integer value greater than 255 to mean end of file. Doing this will complicate the implementation (it will mean devoting a register pair to the variables b and c), but it will simplify our design work a good deal. (I know that because I've already gone through several abortive designs that didn't use this dodge.)

The pack program will find end of file at the physical end of its input file. But it will write less data than it reads, so its output file may not end exactly on a CP/M record boundary. The toolkit functions will fill out the last record with meaningless bytes, and we won't want unpack to process these. So pack will have to flag the end of the meaningful data with something that unpack can recognize. Let's assign the unused compression code EFh for that purpose -- its hex value looks like an acronym for End File -- and make sure that pack writes that as the last byte of compressed data.

Ad-Hoc Compressions

The plan so far will compress certain pairs of lowercase letters, but other common pairs occur in CP/M text files. If we can identify them, we have the compression codes E9h to EEh to represent them.

One such pair is the CR-LF combination -- the carriage return and linefeed bytes that end every line of a text file. Pack will be seeing these and it could recognize them and translate them to a single compression code.

I can think of only one other combination that is likely to be generally useful. That's the combination CR-LF-TAB, which begins so many lines of program source files in almost any language. Many other combinations could be cited as common, but only in specific kinds of files: the CR-LF-semicolon that is common in assembly-language files; the zero-zero, comma-zero and space-zero pairs often found in data files; and so on. But all such compressions are specific to one kind of data and would have little effect on any other kind of file.

When we insert these two ad-hoc compressions into the plan, and extend it to account for the fact that bytes will be handled as integers, we get the plan shown in Figure 7-4.

Run-Length Encoding

Runs of identical characters aren't common in document files, but they do occur; and they are often found in program source files. It won't hurt the effectiveness of pack to attempt run-length encoding and it might help it. We have the sixteen compression codes F0h-FFh; let's use them. We shall specify that a run of identical characters is represented by a two-byte code Fnh, cch, where the hex digit n is the number of times that the byte cch should be repeated. The shortest possible run is two bytes long, so let us say that the compression code Fnh means that the following byte should be repeated n+2 times. F0h means a run of 2, F2h a run of 4, and so on to FFh, signifying a run of 17 bytes.

In order to recognize a run longer than two bytes we will have to look further ahead in the file than our two-byte window allows. We won't even try unless all other compressions have failed and b=c; that is, when we have a run of at least two bytes that are otherwise incompressible.

Once we see that condition, we will enter a loop in which we will suck up as many more identical bytes as possible, just as in tabbit we vacumed up as many blanks as we could find before writing any tabs. Having counted the identical characters we will be able to write as many run codes as the count allows. If the count is odd, we'll have to write a solo byte to make up the final tally. The plan for this is in Figure 7-5. Imagine that code inserted into Figure 7-4 just preceding the final else.

There is a new pseudo-code structure in Figure 7-5, the loop structure. No common programming languages support the loop structure, yet it is often useful, especially in assembly language programming. It signifies a middle-exit loop. In general form it is

Here is the sense of it: do the first act; test the condition; if it is true then do the second act and repeat the loop; otherwise exit the loop. There is an alternative way of writing the same thing:

In Figure 7-5, first act is c := readone() and second act is n := n+1. Write the loop from Figure 7-5 in while form and compare the two. Do you agree that they describe the same sequence of actions? The loop structure rotates the while ninety degrees, so to speak, and thus does away with the redundant statement of first act.

Finding Compressible Pairs

There's still a vague line in Figure 7-5. We have been putting off a decision on how to implement the test and action

Making the test will involve making separate tests on b and c. Is b one of the thirteen common characters? If so, is c one of its common followers? If so, the numbers that will be combined in the pair-code should be produced as a byproduct of making the tests.

Therefore let's specify a subroutine that will ask the questions, form a compression code if it can, or form something harmless if it can't. Then we can test its output. In other words, we will be able to write

This trick of having a function serve two purposes -- returning a usable value when a condition is true and returning a harmless signal when it isn't -- is often useful at the pseudo-code level. As we will discover, it sometimes doesn't work out so well at the level of assembly language statements.

How shall makepair do its work? It should look up the first character in a list of common characters, quitting with a non-code if it isn't there or saving the character's rank-number if it is. Then it can select a list of possible followers based on the rank-number, and search for the second character in that list. (These follower-lists are the rows of u.) A plan along these lines is shown in Figure 7-6.

As displayed, makepair depends on lookup, a subroutine that will search for a character within a string and return its index counting from zero. Strangely enough, there is no such function in the toolkit. It isn't hard to write such a function; we can defer it until we code the program.

CODING PACK

Initializing Pack

The outer portions of pack.asm are shown in Figure 7-7. Much of this material should be familiar from the utilities we've done before. I thought it all would be, and so prepared no specific plan for for it. However, a new consideration cropped up.

It occurred to me that if unpack tried to restore a file that hadn't been packed in the first place it could produce rubbish. It shouldn't accept any that hadn't been prepared by pack. In order that it would be able to recognize such files, I made pack start its output file with a two-byte "version code" that unpack can check for.

The first byte of the version code is FFh, a value that is not likely to be the first byte of an unpacked file. It certainly isn't likely in a text file, nor in a program object file (where it would represent a reset instruction as the first statement of a program). The second byte is an arbitrary choice.

The Main Loop

I prepared the first version of pack in the same way that I did previous programs -- by editing the pseudo-code file and inserting assembly statements to implement the pseudo-code actions. The program worked, but it wasn't fast enough to suit me.

We can judge the performance of a utility by the rate at which it consumes input data. I tested pack on a file of 62,000 bytes (performance timings should always be made with large files in order to swamp the time taken to load the program and open its files). It took 47 seconds to process the file. That's an input rate of only 1300 bytes per second, or a processing time of about 760 microseconds per byte. That would be a respectable data rate if the program had been written in a high-level language, but speed is the whole point of using assembly language.

Since the test was made on a machine with large, fast disks, I knew it would be even slower in a system with 5-inch diskette drives, and those are just the machines where pack should be most useful. So I went looking for the place where too much time was being spent.

The first question was, how fast should the program be? To find out, I modified it so that it did almost no processing at all. It was compressing data in a 3:2 ratio; that is, it was writing two bytes for every three it read. I edited the main repeat-until loop so that it did nothing but read three bytes and write two. This gutted version of the program processed (so to speak) at a rate of 1880 bytes per second or 530 microseconds/byte -- a 30% improvement in speed, if not in function.

The next questions were, what part of the main loop was eating up more than 200 microseconds for every input byte, and could it be streamlined? Z80 instructions take from one to three microseconds each. Roughly speaking, that 200 microsecond bulge represented 100 instructions on each trip 'round the repeat loop. Most of the loop consisted of tests and branches. The special cases of carriage returns and of bytes greater than 127, for example, were dealt with in a couple of dozen instructions. Nor could the problem be related to run-length encoding, since the test file had few if any runs.

That left only the implementation of makepair. Its logic and use followed closely after Figure 7-5. It was called for every ASCII byte except a CR; it used lookup to find out if the byte was in the common set; if so, it used lookup once more to check the following letter.

It was clearly inefficient to look up every byte in the list of common letters. Many of them wouldn't be there, and the search took the longest time to return a negative result.

I inserted code so that makepair was called only when the current byte was a space or a lowercase letter between a and u inclusive. In pseudo-code terms, I changed the test

to the more involved test

This change improved the program; it now processed at 1450 bytes/second (690 microseconds/byte). But that amounted to a change of only 10% and I wanted something closer to 25%. To get it, I would have to depart further from the pseudo-code.

It occurred to me that the current byte could be classified through a table look-up rather than a sequential search of a list. I prepared a table having 128 entries. All of the entries contained FFh except the ones that corresponded to the common thirteen; those contained the numbers 0-12 that would encode them. It takes only a few instructions to index the table; the number extracted from it is supplies both the signal that the byte is or is not one of the common ones and its code value when it is.

This version of the main loop appears in Figure 7-8. It consumed input data at 1690 bytes/second, 20% faster than the original implementation of the pseudo-code. However, the pseudo-code plan served an essential function. It made the first implementation of pack easy to build, and that version verified the algorithm. The performance improvements followed, each a small change on a program that was known to be working. This is an application of the motto, "first make it right, then make it fast."

Byte values are easy to manipulate in assembly language, word values less so. Still, the need to carry the pseudo-code variables b and c as words, not bytes, caused less trouble than I'd expected. One fact helped. If you study Figure 7-4 you will see that, throughout the body of the loop, the value in b must be a data byte; it cannot be the end of file value. All input goes to c; only at the bottom of the loop is c copied to b. Immediately afterward the loop condition is evaluated, and execution can continue only if b is still a data value.

That fact made it possible to treat the variable b as a byte at most points; only the variable c had to be handled as if it might contain the end of file signal at any time.

Implementing Makepair

The efficiency changes in the main loop caused changes in makepair as well. It would only be called when b was known to be one of the common letters, and it could be passed the number that encoded that letter. Its remaining job was to check the c byte to see if it was a common follower of b, and to prepare the pair-code if so.

I prepared thirteen strings of follower characters -- the rows of u -- and a separate table of their addresses. Twice the first letter's code value, plus the address of the table, yielded the address of the proper list of followers. Since the pseudo-code function lookup was now used in only one place, I made it in-line code. The final code appears in Figure 7-9.

Implementing Run-Length Encoding

The implementation of run-length encoding followed very closely on the pseudo-code of Figure 7-5; it appears in Figure 7-10. The only complication came from my realization that it was just barely possible that pack might encounter a run of more than 256 identical bytes. That meant that the count of identical bytes had to be handled as a word, not a byte. This caused no problem while counting up, but it meant that a 16-bit subtract would have to be used while counting down by 17. Once the count has been reduced below 17, however, it may be handled as a byte.

DESIGNING UNPACK

The pack program reduces the size of most text files by a third, rendering them useless as it does so. It is time to design the program that will restore a packed file to its original form.

The input to unpack is the sequence of bytes that pack wrote. We can list them all; they include

• ordinary ASCII bytes
• pair-codes
• E8h followed by a non-ASCII byte
• E9h meaning CR-LF
• EAh meaning CR-LF-TAB
• EFh to signal physical end of file
• run-codes, each followed by the byte to be repeated

The program can decide what to do next on the basis of a single byte's value. When a program is to select one of several possible actions based on a single value, we can express its shape with a pseudo-code case structure, as shown in Figure 7-11.

If you know the Pascal language, you'll recognize the case structure. Even if you don't, its meaning should be clear. The line "case (next) of" means "based on the value of next, select one of the following actions." The action-groups follow, each prefixed by the value or range of values to which it applies.

We can implement a case with a mechanism very much like the character-class table used in pack. The program can classify the current byte by indexing a table; the class-value produced is an index of some sort to the action that should be performed on that byte.

The only thing that isn't detailed in Figure 7-11 is the action for a pair-code, "decode the pair as b, c." It shouldn't be hard to implement, however. Each pair-code consists of two binary numbers, one of four bits and one of three. The first, four-bit, number stands for the first character of the pair. It also stands for the row of u (thirteen times eight) are laid out in row order in storage, the seven-bit concatenation of the two numbers will lead us directly to the correct second character!

CODING UNPACK

The only complicated part of implementing unpack was the implementation of the case statement. It is possible to do this in assembly language in a way that is very fast, but it requires subtle uses of the assembler.

Look back at Figure 7-11. Each action within the case structure is independent; when it completes, control should pass to the end of the entire structure. The obvious way to implement it is to write a label at the head of each action, put a label at the end of the structure, and end each action with a jump to the end.

The only remaining problem is how to select, and jump to, the correct label.

There are several ways to do it. Here's the way I chose to do it for unpack, where the case label is to be selected based on the value of an input byte. I placed a label at the top of the structure. The difference between a case label and the top label, that is, the result of an assembler expression like

is the byte offset of that case label within the case structure. If we construct a table with one entry for each possible input byte, and place in that entry the offset to the case that handles that byte, we can select the case very quickly. All we need to do is use the input byte as an index to the table, add the resulting offset to the label of the case structure as a whole, and we have the address of the needed case. The pchl instruction lets us jump directly to that address.

In unpack, all the cases fit within 256 bytes, so each case's offset fit in a byte. Input bytes might have any of 256 values, so the case-table had to have 256 entries, each containing the offset to the relevant case.

It would be incredibly tedious to type 256 table entries of the form

There are only six different cases, and three of them account for most of the entries. These three cover ranges of consecutive input values. Most of the table can be described as 128 repetitions of the ASCII case, 104 repetitions of the pair-code case, and 16 repetitions of the run-code case.

The mac and rmac assemblers contain a command that is just what we need. The sequence

produces count repetitions of the statements. The expression

yields the count of possible pair-codes, so the sequence

will generate all those entries of the table. The rest of the table can be produced in the same way, as you can see in Figure 7-12.

This use of rept turned up a bug in rmac version 1.1. When I tested unpack, it crashed my system. I ran it under the sid debugging tool several times and finally determined that it crashed while trying to handle the CR-LF code. By stepping it through the case loop I found it was loading an invalid case-offset from the table. I supposed that I must have written one of the repeat-count expressions incorrectly, so I displayed the table and counted its entries. There were too few entries for pair-codes. That made the whole table too short, so that what should have been the entry for the CR-LF code actually fell into a table of ASCII characters. That accidental byte, treated as a case-offset, sent the program off to who-knows-where.

Yet on inspection all the count expressions proved correct. It turned out that the rept command itself was at fault; it repeated 32 times too few for a certain range of counts. What to do? I didn't want to code the table by hand; yet if I stuck in an extra rept to make up the difference, the table would come out too big when assembled by an assembler that lacked the bug. I finally repaired the damage by adding an assembler if statement. It checks to see if the right number of bytes were generated and, if they weren't, executes another rept to make up the difference.

SUMMARY

Utility programs, because they're usually simple, used a lot, and need to run fast, are ideal places to apply assembly language. Pack and unpack are good examples. They compress text files at least as well as the (more complicated and slower) public domain squeeze programs, and they run with pleasant speed. But notice that the speed didn't come automatically, just because we used assembly language. The first version of pack was slower than desirable, and it took changes in both the algorithm and the way the algorithm was implemented to speed it up.

With the programs of these two chapters for models, you should be able to construct a variety of utility programs. In the next chapter we will start work on a project of a higher order of difficulty

8 THE ANTHOLOGY PACKAGE: DESIGN

You might enjoy implementing a pip-based anthology system; if you do, you'll learn a lot about the design of anthologies and about the CP/M commands. The submit files in Figure 8-1 are a beginning. The first one (shown in two versions) adds a file to an anthology. It prefixes the file with a delimiting line composed of %%% and the filespec, then puts that line and the file at the head of the anthology.

The second submit file uses the start and quit options of pip to retrieve one file. It presumes that every member of the anthology is followed by a delimiter line. That will be true of every member except the last one (the first one added). For it to be true of that member as well, the initial anthology file must be created with a single delimiter line. A submit file that will create an anthology is easy to write.

The pip command isn't sophisticated enough to allow deleting members from an anthology, nor can it be made to list the members in one. However, the CP/M editor ed can be driven from a submit file. It is possible to a build a fairly complete set of anthology commands using ed, pip, and submit. I made one, but I wasn't able to find a way to make it detect errors. It would add duplicate members, crash when asked to retrieve a nonexistent member, and try to add the anthology to itself if I told it to. And it was painfully slow.

Anthology programs can be found in collections of public-domain software. Why, then are we going to build our own? For two reasons: because I didn't care for the existing ones I tried (in particular, I thought they didn't pay enough attention to data integrity); and because the project is a good vehicle for demonstrating the tools and techniques developed in this book at the full stretch of their capacities.

As usual, our first step in building a program is to specify its external appearance. The specification that follows is result of several days' intensive mulling. If some of its features seem odd, trust me; they will be justified later.

SPECIFYING THE ANTHOLOGY PACKAGE

An anthology is a special file into which many small files can be collected with a resultant savings in disk and directory space. The anthology commands specified here make it possible to create anthologies, add and delete files in them, list their contents, and retrieve files from them.

Anthologies and Files

You may collect many files in a single anthology. Usually, more files can be kept in an anthology than would fit on a disk as independent files. For example, a disk that can't hold more than 64 files could hold an anthology that contained more than 100 files, so long as their aggregate size fit the disk.

An anthologized file is not as accessible as one that stands by itself. The anthology as a whole can be copied, but the files within it are not visible to the rest of the system. They must be retrieved from the anthology, that is, copied out to become independent files, before anything else can be done with them.

You may compress text files with pack before putting them into an anthology; this will conserve even more disk space. If you do that, it will take two steps to gain access to an anthologized file: it must be extracted from the anthology; then it must be unpacked. The anthology as a whole must never be packed.

An anthology may be copied with pip, renamed with ren, erased with era, or have its file attributes set with stat (set in CP/M Plus). These are the only things that may safely done to an anthology; all other manipulations are done with one of the anthology commands.

Creating an Anthology

An anthology must be created before anything else can be done with it. This is done with the antnew command,

The operand antname names the anthology to be created. It is a filespec, except that the filetype is not needed and will be ignored if given. The antnew program will not create an anthology that already exists. To recreate an anthology, you must first erase it.

The new anthology consists of more than one file. The primary file is antname.ant; it will contain the data of anthologized files. Two other files are part of the same anthology; their names are antname.anx and antname.any. They contain duplicate copies of the directory information for the anthology. The first, antname.anx, is the primary directory. The second is a spare copy for use in case the first becomes unreadable. Whenever an anthology is copied, all three files should be copied, as in

Adding Files

Files are added to, or replaced in, an anthology with the antput command,

The command first locates the anthology antname. Then it locates the file filespec on disk, reporting an error if it doesn't exist. The file is copied into the anthology. If a file with the same filename and filetype already exists in the anthology, this file replaces it.

The filespec may be ambiguous (contain asterisks or question marks). When it is, all files that match that filespec will be added to the anthology, one at a time. The name of each file is displayed as it is copied.

The copied files are not erased; they still remain on disk. If a file has a password (CP/M Plus only), the password will not be recorded in the anthology. When later the file is retrieved from the anthology, it will not be protected.

Retrieving Files

A copy of an anthologized file is retrieved for use with the antget command,

The command first locates the anthology antname. Then it searches the anthology for a file with the same filename and filetype as filespec. If none is found, an error is reported. Otherwise, that file's data is copied to disk as filespec, replacing any existing file of that name.

The filespec operand may be ambiguous. If it is, the command will retrieve every anthologized file with a matching name and type, one at a time.

Listing Files

You can display the names of files in an anthology with the antdir command,

The command searches the anthology for all files whose filenames and filetypes match filespec. The filespec operand may be ambiguous. It may also be omitted, in which case it is taken to be *.*, that is, all files.

The command displays one line for each matching file. The line contains a number, which is the size of the file in 128-byte records, and the filespec. After displaying the matching files, antdir displays a total line showing the aggregate size of the listed files, the size of the anthology, and the amount of unused space in it.

Deleting Files

You can delete members of an anthology with the antera command,

The command locates the anthology and searches it for a file whose filename and filetype match filespec; when found, the command deletes it. The anthology space occupied by the file remains allocated to the anthology (the anthology files will be no smaller on disk) but it is available for reuse by the antput command.

When filespec is ambiguous, antera behaves differently. It searches the anthology for matching files and, as it finds each one, displays its name on the screen and awaits keyboard input. If you want that file deleted, you must enter the letter y and press return. If the file is not to be deleted, type any other letter or merely press return; the file will be left alone.

Data Integrity

Since an anthology may be entrusted with files that don't exist anywhere else, it's important to preserve the integrity of the anthology. Although the anthology commands are designed with this in mind, there are failures that they cannot guard against. For example, a disk read error (a "bad sector") in the CP/M disk directory makes all files on that disk inaccessible. A program can't be designed to protect against such a failure. Therefore you should always keep at least one, preferably two, backup copies of any anthology.

A disk read error that falls within a file makes some data irretrievable, but the rest of the file may be recoverable. However, the usual CP/M commands either read all of a file or none of it. The pip command, for instance, will not copy a file that contains a bad sector; it aborts when it sees the error and the data it copied preceding the error is lost.

The anthology commands, however, can usually recover at least part of a damaged anthology. The recovery method depends on whether the error affects the anthology data file antname.ant or the directory file antname.anx.

Directory Failures

When an anthology command starts, it displays the note loading directory. When it has finished reading the directory, it displays the word done on the same line. If the program is aborted by a disk read error before the word done appears, you will know that the bad sector lies in the directory file antname.anx. To recover, rename the directory file to have a filetype of .bad (do not erase it; that would just free the bad sector for use by another file). Then rename the duplicate directory file, antname.any to have the filetype .anx, and try the command again. If the command works, immediately copy the .ant and .anx files to another disk. (Copy the .anx file twice, the second time giving the copy the type .any, so as to complete the set.)

The integrity of the anthology directory file is crucial; if it were to be corrupted so that it was no longer a true description of the anthology, all of the anthologized files could be lost or scrambled. All of the commands take great care to prevent this. They are designed so that, with the exception of a few critical seconds at the end of a command, program termination for any cause whatever -- a CP/M error message, a power failure, a disk error or a full disk -- will not harm the anthology on disk.

Furthermore, antera and antput, the commands that update the directory, apply several consistency checks to the directory before writing it to disk. If a test fails, the commands terminate with the message Integrity check, leaving the original anthology unharmed.

Because of this design, the general method for recovering from any anthology error is to analyze the cause of the crash and then to run the failed command again.

Failures In Antput

While antput is reading a file and copying it to the anthology, it displays the file's name and type. If it crashes due a disk read error (a "bad sector") at this time, the problem lies in the file being copied, not in the anthology. If antput crashes because the disk is full, it simply means that the anthology has gotten too big for the disk. In either case the anthology should be unharmed, although the files added by antput will not be found in it.

After copying the file, antput displays the word checking and reads back the copied data. A disk error at this point indicates a bad sector in the anthology data file, a sector that was used by the file just added. Files that were already in the anthology should be unharmed; use antget to retrieve them to another disk.

Failures In Antget

Antget displays the name and type of each file as it is retrieved, and done after closing the retrieved file. If antget is terminated for a full disk during this time, it simply means that there wasn't room for the retrieved file; the anthology is all right.

A disk read error during retrieval indicates a bad sector in the anthology data file. Note the name of the file that caused the error. That anthology member, at least, is ruined; further attempts to copy it will also abort. Use antdir to list all the files. Then use antget to retrieve all files except the one with the bad sector. Other files may also cause antget to crash, but most of them should prove recoverable. Retrieve all the files you can to other disks; discard the bad disk; and rebuild the anthology.

Data Security

CP/M Plus supports file passwords. The password system interacts with anthology use in several ways.

When you use antput to add a password-protected file to an anthology, you may give the file's password as part of the filespec operand, or as the system default password, or you may wait for the program to prompt you for it. In any case, the file's password is not recorded in the anthology. The only security protection for anthologized files is the password of the anthology as a whole.

When you retrieve a file with antget, you may include a password as part of the filespec operand. The password will be applied at the read level to the file or files that are retrieved.

An anthology may be protected with a password. Remember that while an anthology consists of three files, the commands receive only one operand to name them. Therefore all the files of an anthology must have the same password. If they had different passwords, the commands wouldn't be able to work.

If you include a password in the antnew command as part of antname, it will be applied to all files at the read level. Alternatively, you may later apply a password to the data file, the directory files, or both, at any of the three levels read, write, or delete. The number and level of the passwords interacts with the commands' actions in a complex way.

• Antdir only reads the directory file. It is affected only by a read-level password on the directory.
• Antera reads and updates the directory file. It is affected by a read- or write- level password on the directory file.
• Antget reads directory and data files; it must be given a password when either file is protected at the read level.
• Antput reads and updates the data and directory files. It is affected by read- or write-level passwords on any file.

These varied effects allow you to control the actions of a person who doesn't know the password:

• To secure the anthology from all commands, give all files a read-level password.
• To permit the use of antdir only, apply a read-level password to the data file and the same password at the write level to the directory file.
• To permit antdir or antget while blocking antput and antera, apply a password at the write level to both files.
• To permit anthology commands while blocking the CP/M commands era and ren, apply a password to all files at the delete level.

Keep in mind that if you copy a protected file with pip, giving the password in the pip command, pip applies the password at the read level to its output.

DESIGNING THE ANTHOLOGY SYSTEM

My goodness, what a complicated specification. Fortunately, most of the material on passwords simply recapitulates functions that are already built into the toolkit. And we may safely defer all considerations of ambiguous filespecs until later. If we design a good mechanism to add, retrieve, or erase one file at a time, it won't be hard to extend it several files.

System Objectives

We had better start by defining a list of design objectives, or policies. We didn't do that for earlier programs. Because they were simple, they could be designed under the implicit policy of finding the cleanest, fastest algorithm that would accomplish the specified task. In the present task we will have many choices to make, and explicit objectives will help make them.

I believe that data integrity ought to be an anthology system's first objective. An anthology should be, so far as we can make it, proof against loss of data. Its design should be such that, if damage occurs, whether by hardware error or program failure, the loss will be confined to the smallest possible area. Such a design is said to be "robust."

It takes a lot of care to create a robust design. For example, we must keep in mind that our programs can be aborted by a disk error on any input, and design them so that no such failure will cause them to leave the anthology in an unusable state. We should also bear in mind that a program can be cancelled at any instant by a power failure or a press of a reset button. So far as possible, no failure of any kind should be allowed to damage the anthology.

Next come some design constraints. The design should not be based on recopying the anthology. The lib library manager, for example, makes a new copy of an object library every time it is run. Recopying is a simple management algorithm, but it has two major problems. First, processing time varies with the size of the anthology, not with the size of the files being added or retrieved. Second, it limits the size of an anthology to one-half the size of a disk. Our anthologies should be able to expand to nearly the capacity of one disk, and that implies that we will have to update or extend them in place.

Another constraint is that the design should reclaim data space automatically. In some library systems, the space occupied by a deleted member is simply lost; the user is expected to rebuild the anthology with a special "pack" or "reclaim" program when the waste space becomes excessive. I don't think that's tolerable. Space allocation can be easy for the program; it is always a major irritation for the user.

A final policy decision is, how large may an anthology become? The choice will affect the design at many points; a design that works well for half a megabyte may not be suitable for handling ten megabytes. There are only a few common disk sizes: there are many around 128 kilobytes (Kb); some around 500 Kb; some around 1000 Kb; and hard disks range upward from five Megabytes (5 Mb or 5,000 Kb).

The smallest disks need anthologies the most. Disks of 500 Kb and up usually have directories with 128 entries or more. Furthermore, an anthology larger than 500 Kb must contain either very large files (which don't benefit from anthologizing) or so many small files that keeping track of them would be very difficult. I think it is safe to set the maximum size of an anthology at 512 Kb; if the disk has greater capacity, the user has the option of creating more anthologies.

Implications of the Objectives

These objectives have several implications for our design. The first I saw was that control information -- the directory that shows which data belongs to what file -- must be stored redundantly, and apart from the data. The redundancy is necessary for robustness. While damage to file data affects at most one file, damage to the control information can affect several files or all files. If the directory is stored in duplicate in different places on the disk, the chances of recovering from a disk error are much better.

Some library systems maintain only a single file, interspersing control information among the data of the stored members. We can't do that. If we did, we'd have to read the anthology sequentially to find the control information. Then a disk read error would make inaccessible all the control information following the bad sector, violating our first design objective. Besides, if we are to store the directory data twice, at least one copy will have to be a separate file; so both copies may as well be separate files.

The objectives of not recopying and automatic reclamation will mandate the use of direct access disk I/O. In earlier programs we always processed files sequentially from start to end. The anthology commands will have to read and write "at random" (as it is commonly said); that is, they will need to skip around in the file, reading or writing at any point in any order.

The CP/M file system permits direct access to disk files, and the toolkit contains functions that support it. The fseek function can be used to position a file at any byte, so that subsequent input or output will begin at that byte. The frecseek function has the same effect, but it positions the file in terms of records of some fixed size, not in terms of bytes. The frewind function returns a file to its first byte so that it can be overwritten in place. We don't want to consider the details just yet, but we must know that these abilities exist.

The Data File

We can design the data file knowing only that much, and knowing that CP/M files consist of a sequence of 128-byte records. We will treat the data file as an expanse of these records. Some of them will be occupied by the data of anthology members, while others may be free. When we add a file to the anthology, we will copy it into such free records are available, and append new records to the end of the data file as required.

DESIGNING THE DIRECTORY

The directory file will contain the control information that lets us know what members the anthology contains, what data records are free, and which records of the data file are owned by which members. When we retrieve a member, we will use the directory information to retrieve the data records in their correct sequence, writing each to an ordinary sequential file. When we erase a member, we will mark each of the data records it occupied as being available for use.

We must now choose a design for that directory information. There is any number of ways to structure the directory; however, we want a design that will be as simple and as robust as possible. A simple structure will make the programs easier to write and less prone to bugs. For a robust system, we must have a directory organization such that, if a few bits or bytes should be corrupted, only a limited amount of file data will be lost. Some directory structures, as we will see, collapse catastrophically if they are corrupted in the smallest way.

This is a real fear, by the way. There are three causes of data corruption. One is disk failure. In four years of personal computing, I've seen at least two errors that could only have been due to the disk controller mis-writing a byte and not detecting its own error. A second is a failure in RAM. Eight-bit machines lack the parity-check circuits that would detect failures in the RAM chips, and there is a small but genuine chance that what a program writes into RAM is not what it will read back. The most likely cause of data corruption, of course, is program error.

Directory Alternatives

The anthology directory has nearly the same purpose as an operating system's directory of files on disk. Let's compare two of these to see what we can learn.

CP/M divides a disk into blocks of one or two kilobytes each and numbers the blocks. Each directory entry contains a filespec, an extent number, and a list of eight or sixteen block numbers. To process a file sequentially, CP/M finds the directory entry with the lowest extent number and reads out the block numbers from it. After processing those blocks, it looks for the directory entry with the next higher extent number. In order to know which blocks are in use, CP/M keeps a bit-map for each disk drive. When it first accesses a drive, it reads all directory entries. For each block number it finds, it sets the corresponding map bit to 1; afterward, free blocks are represented by 0-bits.

The CP/M scheme is fairly robust. If one directory entry is corrupted, it will affect only one or a few blocks of one file and at most one other file (two files might end up owning the same block number). However, the CP/M directory contains a lot of redundant information for large files (the repeated filespecs in each extent's entry), and it wastes space on small ones (the unused block-number positions in their entries).

The MS-DOS operating system is quite different. It, too, divides a disk into blocks (of 512 bytes) and numbers the blocks. However, it records the state of all blocks in a single table called the File Allocation Table (FAT). The FAT is an array of binary numbers, each corresponding to one disk block; that is, the nth entry of the FAT is related to disk block n. If a FAT entry contains zero, the related block is free.

An MS-DOS file is given just one directory entry, no matter its size. In the entry there is a single block number, that of the first block owned by the file. The rest of the file's space is recorded as a chain of numbers running through the FAT. To read a file sequentially, MS-DOS proceeds this way:

Thus the FAT entry corresponding to each block of a file contains the number of the next block of the file.

The MS-DOS scheme avoids the redundancy of CP/M's directory, but it also avoids CP/M's robustness. Its fragility stems from the fact that the numbers in the FAT have no independent meaning. Every number's interpretation depends on the numbers that precede it in its chain. If a single bit in the FAT is altered, the corruption affects all of the blocks that used to follow that entry in the chain. Some blocks will be lost; others will end up being owned by two files. The block numbers in a CP/M directory don't have this interdependence; if one is corrupted, the others are still correct and usable.

MS-DOS compounds the danger by keeping the FAT in storage continually, refreshing it from disk as little as possible but writing it back to disk often. This ensures that when the in-storage copy is corrupted -- and it does happen, as many owners of IBM PCs will attest -- the error will quickly be made permanent.

In our directory, we will emulate the economy of MS-DOS by keeping a single array of record numbers. We will not, however, track a file's records by threading a chain through the table. Each entry in the table must stand alone, so that one corrupt entry won't cause other entries to be misinterpreted.

We can learn something else from the unfortunate example of MS-DOS: we must try to avoid committing a mistake to disk. It's bad enough to corrupt the directory in storage, but so long as we don't make the error permanent by writing it to disk its effects will be limited to a single program's run.

We can achieve this with two rules. First, we must never modify the data file in such a way that the old directory on disk is made invalid. If we stick to that, unexpected program terminations will cause no loss of data. The old directory will be a valid description of the data even after a crash, although it may not describe the changes the program attempted to create. This rule alone makes our system proof against crashes of all sorts -- disk read errors, disk full errors, the user pressing the reset button -- and furthermore we will be free to end the programs with the abort macro at any time.

The second rule is that, after modifying the directory in storage, we must try to verify its correctness before writing it back to disk. It won't be possible to detect all errors, but we can detect most of them. If we can catch a corrupt directory and abort, the first rule will ensure that we've done no permanent harm.

A HIGH-LEVEL DESIGN

Of course, I wouldn't be saying all these things if I hadn't already prepared a design that met the objectives. We will examine it first at a very high level, deferring all questions of assembly-language implementation.

The Data Structures

There will be a data file which we will view as an expanse of 128-byte records. We will number these records from 1 to MaxR, where MaxR is at least 4096 (4096 times 128 makes 512 Kb). There will be an array of integers called R indexed by record numbers, so that the value of R[r] tells the state of record r.

At this high level, we may pretend that there are two I/O functions, copyin(r) and copyout(r). The first will represent reading 128 bytes from the current input file and writing it to record r of the data file; copyout(r) will stand for getting record r from the data file and writing it to the current output file. These pseudo-functions translate directly into toolkit function calls.

We will also suppose that the directory can account for as many as MaxF files, MaxF being some useful number like 500 -- how many doesn't matter. We will number the files from 1 to MaxF and keep track of them in two arrays. The first, F, is an array of strings, the names of the files in filename.typ form. (If we were working in BASIC, we'd write DIM F$(MAXF).) The second, S, is an array of integers, the sizes of the files. Thus F[f] is the name of file f, while S[f] is its size as a count of 128-byte records. If there is no file f, F[f] will be a null string.

When R[r] is zero, record r is free. Otherwise the value of R[r] will be the number f of the file that owns record r. We will always allocate data records starting with the lowest number available. As a result, we could copy a file out of the anthology with this simple loop.

That's the basic structure. It is certainly simple. We can make it quite robust with consistency checks. We can verify, for instance, that every entry of R contains either zero or a file number between 1 and MaxF, and that a file of that number exists (F[R[r]] is not a null string). We can also verify that every existing file owns exactly as many records as the array S says it should. If we add two two more variables -- AlFiles as a count of active files and Frecs as a count of free records -- we can make a complete set of tests. We can verify that there are exactly Frecs entries of zero in R and exactly AlFiles filename strings in F.

If we make these checks just before writing the directory back to disk, we will come close to ensuring that we never create an inconsistent directory. It is remotely possible that a directory could be corrupted in such a way that it would be inaccurate yet self-consistent, but the chances of that are so small that we can ignore them.

Support Functions

Let's design some support functions to make the use of these data structures simpler. (This isn't just a pedagogical dodge; I really did begin my design efforts by working out this set of support functions.) We can begin with functions to manage the filename arrays. The find function (Figure 8-2) searches for a filename string in the array F, returning its file number if it appears and zero otherwise.

The add function (Figure 8-3) is used to add a new filename to the directory. It looks for an unused entry in F and sets it to the new filename string. If none exist, the directory must be full.

When retrieving a file we have to read out its records in order. We don't know where the records of a given file fall within the array R, but we have decided that they will appear in ascending order; that is, the next record has a higher number r than the current one. The nextdat function (Figure 8-4) finds the next record of a file, given the file number and the number of the current record. It expects that it won't be called unless there is a next record; hence it aborts with an integrity failure if it can't find one. Note the use of a while loop in Figure 8-4. Why do you suppose nextdat doesn't use a repeat loop as the prior functions did?

With nextdat we can write pseudo-code for the heart of antget, a loop that copies a file f from the anthology.

Again we have used a while loop. Here it is because we will allow an anthology member to have a size of zero. If the user wants to anthologize an empty file, we will allow it.

When we copy in a new or replacement file we will have to allocate record numbers to hold its data. One way to do this is to scan the array R from beginning to end, looking for an entry that contains zero. But more often than not, when we want one free record we will shortly want another. If we scan from the beginning each time, the program will waste progressively more time on fruitless comparisons on each call. Let's borrow a trick from nextdat and search for the next free record after the last one found. This is shown in nextfree in Figure 8-5.

With nextfree we can sketch the heart of the antput command.

This simple formulation ignores the problem of replacing a file that already exists in the anthology.

When erasing files we have to free record numbers. We may as well have a support function for this purpose. The free function (Figure 8-6) releases all the records owned by a file, performing a consistency check as it goes.

We could use free as it stands to erase a file, but not to replace one. Replacement will occur when antput is asked to copy in a file that already exists in the anthology. The simple way to do the replacement is to apply free to that file, releasing all its existing records, then to execute the simple loop shown above. But that loop calls nextfree, which might choose one of the records that was just freed. The new file data would overwrite some or all of the old version of the file.

For robustness we must not alter the data file in such a way as to make the old directory on disk invalid. But this replacement procedure would do just that. After freeing the old file's records and reusing some of them, the old directory wouldn't describe that file correctly. If the program crashed before it could rewrite the updated directory, the anthology would be ruined.

The only solution is to have two kinds of "free" records: records that are really free, and those that will be free when the directory is updated on disk. We might use a value of -1 in R to signify a record that is conditionally free. That will signify that it belongs to no file, but will prevent nextfree from selecting it for use. When we are ready to commit the directory to disk we will convert these marks to zeros, probably as part of performing the consistency checks.

Only antput and antera will use free; antput needs to free records conditionally while antera won't care. Therefore the statement R[r]:=0 in Figure 8-6 may as well be R[r]:=-1 for all cases.

Just as a check on the design, let's sketch the process of committing a directory to disk. This will be done at the end of the antput and antera commands. The logic is shown in Figure 8-7. It depends on an additional array of integers T, in which the true count of records owned by each file is accumulated.

IMPLEMENTING THE DIRECTORY

This scheme seems to work smoothly enough, at least as pseudo-code. But how can it be implemented in assembly language? A literal translation of the pseudo-code design would use the arrays R, F and S, each of a fixed size both on disk and in storage. There are disadvantages to this. Arrays are tedious to manipulate in assembly language; for example, it would be quicker if, where the pseudo-code indexes the array of filenames as F[f], we could actually use the address of that filename string without going the process of computing it from the index and the base address of the array.

A more important problem is that arrays of fixed size are both bulky and inflexible. Consider the storage requirements. We must allow at least 4,096 record numbers, each a two-byte integer. That's 8,192 bytes. We should allow at least 100 filenames. It takes 13 bytes to record the string "filename.typ," plus two bytes for the size of the file -- say 16 bytes for each file. That's another 1,600 bytes. A directory composed of fixed-size, preinitialized arrays would take nearly 10 Kb of disk space regardless of the amount of data in the anthology it describes. Furthermore, its fixed size would hamper the user who needs to store exactly 101 files, or the one who needs to store just 4,097 data records.

The directory may take up a fixed amount of space in storage, but its size on disk should be proportional to the amount of data in the anthology. This is especially important for small disks. Furthermore, it should allow a flexible upper limit on both the number of files and the amount of data. The array R should be able to expand at the expense of arrays F and S, and vice versa.

The Directory In Storage

This can be done in assembly language. The first step is to merge the arrays F and S. The merged array -- let's call it FS -- is an array of data structures, each entry containing a filename string, a size integer, and a spare byte to make up 16 bytes (Figure 8-8).

Figure 8-8. The layout of array FS in storage.

Now imagine a block of storage set aside to hold the arrays. The array R, the list of integers that describes the data records, may occupy the low-address end of the area. The array of file structures can be packed into the high-address end of the area. The space between the end of R and the start of FS is available for the expansion of either.

This situation is diagrammed in Figure 8-9. It shows a block of storage that starts at some address Base. Base is also the address of the first entry of array R; the address TopR points to the first unused word following R.

Figure 8-9. Arrays R and FS can share a block of storage.

Some distance beyond the end of R, the array FS begins. Address BotF points to the first entry of FS. The address TopF points to the byte after the end of FS -- the end of the block of storage.

Under this arrangement, both arrays are open-ended. If we need space to record a new file, we get it by subtracting 16 from BotF. If a new data record must be allocated and none of the existing ones are free, we can create space in R by adding 2 to TopR. In either case, the directory becomes full only if TopR becomes greater than BotF.

Under this scheme the contents of the file entries are no longer indexes to an array F; instead they are addresses of FS records.

Notice that these changes in the representation of the data are not fundamental. They don't affect the logic that we laid out in the last section; the pseudo-code functions displayed there are still accurate statements. There is still an array R; its entries still reflect the state of data records; the contents of arrays F and S still exist and have their planned meanings.

The Directory on Disk

When the directory arrays are laid out in storage this way, it becomes easy to read and write only the relevant parts to disk. The relevant part of the array R extends from Base to TopR; that of FS from BotF to TopF. Define

Now suppose that when a directory is written to disk, we write only this information:

• The word SizeR
• The word SizeF
• SizeR bytes starting at Base
• SizeF bytes starting at BotF

In a new anthology, SizeR and SizeF are both zero, so the directory of a new anthology would consist of nothing but two words of zero. Once files have been put into an anthology, its directory files on disk will be larger, but their size will always be proportional to the amount of data in the anthology.

Reading a directory into storage is the reverse process. We would allocate an area of storage and set its start and end addresses in Base and TopF. Then we would read a word to SizeR and a word to SizeF. If the sum of those words was greater than the size of our area, we'd have found an integrity failure; otherwise we would

• Set BotF := TopF - SizeF
• Set TopR := Base + SizeR
• Read SizeR bytes to Base
• Read SizeF bytes to BotF

Relative Addresses

A directory written to disk by one program will be read to storage in other programs. There is no guarantee that the value of Base will be the same in different programs, yet the record entries in R are supposed to be addresses. These addresses won't be accurate if they are loaded to a different Base point.

One more change will fix this problem. After the directory is loaded, R[r] will be the address of the FS entry that owns that record. However, just before writing the directory to disk we will go through R and modify each nonzero entry this way:

That converts what was an address into an offset, the distance in bytes from that file entry to the top of the storage area.

After reading a directory we will perform the reverse conversion,

(yes, the same expression), to convert an offset back into an absolute address. This peculiar conversion handles two kinds of difference between one program and another. The second program might read the directory to a different area of storage, and it might use a larger or smaller block of storage to hold the directory. The only thing we will depend upon is that all programs will place the array FS at the top of the storage block.

Writing the Directory

There are two ways in which we could update the directory files. One way is to open them with frewrite and write them sequentially. That replaces the old files with new ones; while the writing is going on both old and new files exist.

The other way is to use the direct-access functions to write the directory data back into the existing files. That could be done by applying frewind to seek back to the head of the files and then writing them sequentially. The new data would be written over the old data in the same disk sectors.

There are reasons for preferring the second method. The first is integrity. Once the directory data have successfully been read from a certain part of the disk, that expanse of magnetic oxide is known to be readable, and we ought to stick with it. If we make new files, they'll go to a new, unproven part of the disk's surface. Another reason has to do with passwords under CP/M Plus. The directory file may have a password at the write or delete level. When the toolkit functions make a new or replacement file, they must install a password at the more stringent read level, so rewriting the directory would have the effect of forcing the password level up. On the other hand, the directory might have only a delete-level password, which normally needn't be given when a file is updated in place. But when a file is rewritten, the old file must be erased, so the password would be required (or would cause a program abort if it wasn't given).

Yet another reason is that while a file is being replaced, two copies exist. On a nearly-full disk, that might force a needless disk-full error. So all in all, it seems best to use direct-access functions to rewrite the directory in place.

Ah, but that last point brings up a new worry. Imagine this scenario: Several files are added to an anthology on a nearly-full disk. The files' data fits, but the new filenames and record numbers cause the directory to expand across a kilobyte boundary. CP/M must allocate a new disk block to each directory file -- and runs out of disk space. If the files are updated from first record to last, the program will be aborted before it finishes writing the directory, but after it has updated that part of the directory that fit in the old directory's allocation. The directories (or perhaps only one of them) are no longer a true description of the anthology. This violates one of our integrity rules.

It took hard thought to arrive at the obvious solution to this danger: use the direct-access services to update the directories from last record to first. The only thing that will make CP/M abort a program during file output is running out of disk space, but that will happen only when the program is writing to a new sector of the file. But if we are writing to a new sector, we can't be overwriting old directory data. Therefore we must write those records of the directory that might be new sectors first. If that causes CP/M to abort us, we can't have overwritten the old directory data; it will still be there, a true description of the anthology.

The routine that updates the directory files on disk will have to write them backwards, from their last 128-byte record back to their first. In order to do so conveniently, the values of SizeR and SizeF will have to be stated in units of 128 bytes; that is, they will have to be counts of 128-byte records.

Wait, there is one more hazard. The directory files antname.anx and antname.any are supposed to be identical. But what if the .anx file is written correctly and then we encounter disk-full while writing .any. The files will be out of step; one will be updated while the other is back-level.

The solution is to write the files alternately by record, from last record to first. Write the last record of .anx; write the last record of .any; write the next-to-last record to .anx and then to .any. This will force CP/M to allocate the new disk blocks that are needed by both files before we write over the old data of either file. If disk-full occurs, neither file's original contents will be changed; if not, both will be changed.

SUMMARY

Whew! This is where an integrity policy can lead one. Is it worthwhile? Well, for this application, perhaps not. But the software market is being flooded with so-called "database managers" to which people entrust data of immense value. How many of them take even this amount of care for data integrity and security? Most ignore all such considerations, simply dumping the whole responsibility onto the user with many platitudes about "make lots of backup copies." You have seen the issues and at least a few of the solutions. Should you set out to build a small database manager using the direct-access services of this book's toolkit, you'll have some idea of what to do.

In the next chapter we will attempt to implement this monster we've conceived

9 THE ANTHOLOGY SYSTEM: SUPPORT MODULES

In retrospect that would have been the best solution, but I chose another: the common block. A common block is a named segment of storage. Each module that needs access to its contents includes a definition of the common block; the link program makes sure that each module's definition references the same area of storage. The common block for the anthology system is shown in Figure 9-1.

This section of code has to be included in every module of the system. Therein lies one danger of common blocks. The link program guarantees that every definition of the block will refer to the same area of storage, but it cannot check on the use of the storage. There will be no error indication if one module's definition of the contents of the common block differs from another module's definition. If one module stored, say, TopR in the eighth word of the common area while another module retrieved it from the sixth word, a very tricky bug would result. The modules would look correct in isolation but wouldn't work together.

The common block's definition must be identical in every module or catastrophe will follow. I made that happen by writing Figure 9-1 as a separate file and pulling it into each file as it was edited. But sure enough, around the fourth module I discovered that another word was needed in the common definition. Then I had to go back and correct the previous modules.

Assume that the code of Figure 9-1 is part of all the remaining figures in this chapter.

IMPLEMENTING THE MODULES

Let's look at the code of the most useful modules. In truth, I wrote the modules needed by antnew first, then wrote and tested antnew, then the modules needed by antput, then antput itself, and proceeded in that fashion until all the programs were done. But I had the structure of the whole system in my head in more detail than could be shown in the last chapter. That gave me confidence that it would all come together. You may not have the same sense of the design's solidity, and seeing the modules first may reassure you.

The Find function

Glance back to figure 8-2, the pseudo-code of a function that finds a name in the directory. Its implementation appears in Figure 9-2.

Study Figure 9-2 carefully, for it illustrates a method of scanning an array that is used throughout these routines. The array of filename-and-size entries begins at the top (the high-address end) of the in-storage copy of the directory. Its oldest, highest entry ends in the last byte of that area, and common word TopF contains the address of the following byte. Its latest entry is at the lowest address; that address is in common word BotF. In a new anthology the array is empty and BotF = TopF.

The array can be scanned in either direction. In Figure 9-2 it is scanned from highest to lowest address. Before the loop, register HL is set from TopF. At the top of the loop, the dsbc instruction is used to back HL up by the length of one entry. That instruction has to be used with care; it subtracts from HL the contents of a register pair plus the value of the carry flag. That is useful in certain arithmetic routines, but most often the carry flag is irrelevant and we must be sure that it is zero before doing the subtract. The easiest way to clear it is the instruction ora a. That changes no registers, but like all logical instructions it sets carry to zero.

After the subtract, HL points to the next lower array entry -- or does it? If its contents have become numerically less than BotF, it points only to unknown, useless space. To find out if this is the case, HL must be compared to BotF. There is no word-compare in the Z80 instruction set, but binary comparison is nothing more than binary subtraction. In Figure 9-2, BotF is subtracted from HL. If that sets the carry flag, BotF was greater -- there was a "borrow" out of the high bit of HL -- and the loop must end in failure. If not, HL points to a valid array entry. Well, it used to; it no longer does because BotF has been subtracted from it. Its contents must be restored by adding BotF back into it. Then the input string may be compared to the filename string in the array.

The Add Function

When find fails, the new filename may be added to the directory with function add. Its pseudo-code is shown in figure 8-3; its implementation appears in Figure 9-3.

The pseudo-code plan for add was based on the implicit assumption that the array of filenames had a fixed size. It showed a simple scan for the first unused entry. The real situation is more complicated since the array has a flexible size. It may contain an unused entry (if a file had been erased), but if it does not, it can be extended downward to create a new, unused, entry.

The code in Figure 9-3 starts with a scan down the file array much like that in Figure 9-2. The loop has, however, two exits. If it locates an empty entry (one containing a null string), the new filename may be inserted there. If it reaches the end of the array, however, it attempts to create a new entry. When this succeeds, the case of "add a new entry" has been made identical to the case of "reuse an old entry"; that is, the outcome of "add a new entry" is identical to that of "find an unused entry" -- both end up with HL addressing an available entry. This trick of reducing one case to another is a useful one.

The dsbc instruction is used for word comparisons twice in Figure 9-3, and both times the original value in HL is preserved by pushing and popping HL, whereas in Figure 9-2 it was done by adding back the compared value. The difference is that in Figure 9-2 the contents of HL mattered only in one case and were irrelevant in the other. In Figure 9-3, HL's original contents are needed on both legs of the branch. The branch is taken on the state of the carry flag, but if HL were restored with an add, the restoration would wipe out the state of carry that determines the branch. Accordingly HL must be restored with the slower stack operations.

The Nextdat Function

The nextdat function, planned in figure 8-4, was specified to return the number of the next record owned by a file. It amounts to a simple scan upward through the array of record numbers, R, looking for the next entry that contains the index of the given file.

As implemented in Figure 9-4 the simplicity is rather swamped by the necessary switch in mental levels between indexing an array -- checking the value of R[r] -- and addressing a sequence of two-byte words in storage. The arithmetic involved in the indexing is discussed in the comments at the head of Figure 9-4. The fact that the Z80 cannot treat stored words as units complicates things further. Follow the progress of HL through the loop carefully. It is used to look at first one byte of a word, then the next; but when the loop ends HL is pointing, not at the start of a word, but at its middle.

This routine can encounter an impossible situation. If nextdat is called, its caller must expect that a "next" data record exists. But one might not; what should nextdat do if it can't find one? Either the calling program has a bug or the directory has been corrupted; whichever, the integrity of the system is in doubt and the only safe course is to abort the program. The routine quits with the first of what eventually became nine "integrity checks." The message it issues isn't very informative, but then it is never supposed to be seen anyway. If the situation ever does arise, there isn't much more that can be said about it than "aghhhh!"

The Nextfree Function

The function nextfree, whose plan appeared in figure 8-5 and whose code is shown in Figure 9-5, has some of the characteristics of both add and nextdat. Like nextdat, it scans upward through the array R. Like add, it is looking for an unused entry and, if its search fails, it tries to create a new entry by extending the array.

Both the add and nextfree functions could be frustrated by finding no room to expand their arrays, and both abort when this happens. They display different messages, but in fact both are reporting the same condition -- that the two arrays have met in the middle of the in-storage directory. Fortunately, neither message is likely to be seen. The in-storage directory is 16 Kb long, allowing for a megabyte of data, a thousand filenames, or a generous mixture of the two.

The Free Function

The function free, whose plan was shown in figure 8-6, was specified as releasing the ownership of all records owned by a particular file. In order to ensure that antput would not reuse the freed records during a single run (and thus make the old directory invalid), free was to mark each record slot with a -1.

The implementation of free appears in Figure 9-6. It differs from the pseudo-code plan in that it doesn't count the records it releases in Frecs. Since they aren't really free yet, they shouldn't be counted as such. During the commit procedure (the validity checks prior to saving the directory) the marked records will be set to zero and counted.

As often happens, the body of the loop needed one more variable than I had registers to hold. The Z80's architecture, however, makes the top word of the stack almost as accessible as a register pair. I elected to keep the count of freed records on top of the stack, switching it into HL when it needed incrementing.

The Copyin and Copyout Functions

The anthology design assumed the existence of two functions for I/O between the data file and a sequential file: copyin to read a file's record and store it in the anthology; copyout to copy an anthology record to a sequential file.

I said that these routines would translate to a series of toolkit macros, and indeed they do. The copyin function's code is shown in Figure 9-7. It requires only a record number (as it would be returned by nextfree), Figure 9-5) and the use of the files defined in the common area. Part of its simplicity stems from its assumption that the sequential file is not at its end; its caller is supposed to assure that.

The copyout code appears in Figure 9-8. It has to check for one impossible condition. The frecseek function that it uses to position the data file at the required record returns a signal in the Zero flag. If it returns Zero true, it is because CP/M reported that no data existed at that file position (similar to the way in which the sequential-input functions return Zero true at end of file). This should never occur; the record number given to copyout ought to have come from nextdat and, if it is owned by this file, there ought to be data in it. If it does occur, the directory or the copyout's caller has lost all credibility.

The Setup Function

Each anthology command will need to fetch its first command operand and use it to set up the filedefs of the three anthology files. In addition, each command ought to follow our convention of displaying a usage message when called with no operands or an operand of only a question-mark. These essential formalities are perfect for a module their own. I put them in a module named ANTSET (Figure 9-9). Much of what this setup routine was patterned after the chkops module we used in earlier programs. Two of its features are new.

The first new feature is the definition of the anthology files. Every module's source file contains the identical definition of the common block as shown in Figure 9-1. That definition reserves space for the three filedef macros which will represent the parts of the anthology, but it doesn't contain the macro calls themselves.

Here in the ANTSET source file the assembler is made to reopen the common block, move back to each of these names, and assemble the filedef macros. When constant values are to be assembled into a common area, it is best to do it this way. When link processes constant data in a common area, it simply overlays each module's constants on the prior one's. If two modules assemble constants in the same byte, the one that link happens to process second will prevail. It's best to make sure that only one module actually assembles anything in a common area.

When rmac is made to reopen a common area this way, however, it also produces an "E" error flag on one statement in the common definition. This appears to be a bug, but it seems to cause no harm.

The second new thing in Figure 9-9 is the use of a partial assignment of a name to a file. The fassign function is familiar; it assigns a filespec, contained in a character string, to a file definition. Normally it assigns all the parts of a filespec: drivecode, filename, filetype, and password (the password is accepted, but has no effect, under CP/M 2.2). However, fassign may also be used to assign only one of those parts, or any combination of parts, while leaving the others unchanged.

The setup function applies fassign this way. It first assigns the entire first operand to each file. That establishes all four parts, or all of them that were given in the command, in the file definitions. Then it uses the optional fourth operand of fassign to assign a fixed filetype to each file. That filetype replaces any filetype that might have been given in the command operand. This is how the anthology commands apply a single "antname" operand to the three-file suite of an anthology.

Opening the Files

All of the anthology commands except antnew will expect that all three anthology files exist and contain data and will have to open them. These additional formalities I placed in another module, ANTOPE (Figure 9-10).

Any CP/M disk file may be used for direct access. As far as CP/M is concerned, there is no difference between a sequential file and a direct one; they are handled using the same data structures, and direct operations may be mixed with sequential ones. As a result, it is permissible to open a file with freset even though it will be used for direct access. That's what ANTOPE does.

The toolkit contains a function specifically designed for opening direct-access files, fupdate. It does what freset does, but in addition it checks for device files and read-only files and aborts in these cases. The check for a device file (a file assigned a device name like CON: for a filespec) is useful, but not necessary in the anthology programs. They assign a filetype to each anthology file, and by the rules of the toolkit functions, a filespec that includes a filetype (like con:.ant) must be a disk file. Of course, no such file would be found, so that case is trapped without the help of fupdate.

As to the check for a read-only file, some of the anthology commands will attempt to modify the files and some will not. The use of fupdate would have required the files to be read-write, even for the antdir or antget commands. It seemed better to ignore the possibility of a read-only anthology, allowing CP/M to terminate the program if the user attempted to antput to a read-only anthology. Our design is such that doing so can't hurt anything.

IMPLEMENTING ANTNEW

The setup function is the only module required to make the antnew command work, and that simple program was the first one implemented (Figure 9-11). It uses setup to set up the files, makes sure that none of them exist, then creates them. The frewrite function creates a file that doesn't already exist.

After making the a file, antnew writes a block of 128 bytes of binary zero to it. The contents don't matter in the data file, but it must contain at least one record or ANTOPE will reject it. In the directory files, the first six words of the first record will be read to the first six words defined in Figure 9-1. Since they will be zero, they will properly define a directory that contains no information. The other commands will have to be written so that this is an acceptable state for a directory -- as the supporting modules have been.

LOADING THE DIRECTORY

All the other commands will have to load the anthology's directory from disk. That operation clearly deserved a module of its own, and it got one (Figure 9-12). The job of this load routine is to retrieve the directory from disk and set it up in storage in the form that the supporting functions expect. Four steps are involved. I worked them out in pseudocode, and some of the pseudocode can still be seen in the module.

The first step is to read the first twelve bytes from the .anx file into the first words of the common block. Four of these words -- SizeR, SpanR, SizeF and SpanF -- define the remainder of the directory. The Size words give the lengths of the two arrays, R and FS, in bytes. The Span words give their lengths as a count of 128-byte records. When these lengths are known, their sum should be checked against the predefined constant SizeDir, the size the directory is to have in storage. The sum ought to be no greater (if it were greater it would indicate either corruption of the file or an immense directory written by a program with a larger SizeDir than this program's).

After verifying that the directory will fit, load can allocate the storage to hold it. The toolkit function dslow allocates a block of storage of a given size at the low-address end of storage (just past the end of the program) and returns its address. That address becomes Base, the base address of the directory.

Only the first twelve bytes are significant in the first record of the directory. The following SpanR records contain the array R; the SpanF records after that contain the array FS. The next step is to read these two spans of records into the allocated storage. In Figure 9-12 this is done with fgetblok, a toolkit function that reads any number of bytes from a file into storage and returns the count of bytes read -- which will be the same as requested, unless early end of file is encountered.

The first span is read to the address in Base; the second is read to an address SpanF*128 bytes below TopF. If the directory were very full, these two blocks of data might overlap, but that would cause no harm since they would also have overlapped when they were written.

The array of filenames and sizes is now complete, but the array R is not. It should contain addresses of entries in FS; instead it contains relocatable offsets. A single scan over the array corrects this.

The load function does only a little integrity checking, validating only the gross sizes of the arrays and guarding against early end of file. It could do a thorough check of the arrays' contents, but doing so would make the system less, not more, robust. Suppose the directory were corrupted in some minor way that affected only a file or two. A thorough consistency check at this point would find the error, but then the program's only response could be to terminate. That would make all files inaccessible for an error that affects only a few. It's better to be permissive at this stage, applying the rigorous checks only when the directory is to be updated on disk.

SAVING THE DIRECTORY

After antput or antera has modified the directory, it must be saved on disk. Saving the directory is a larger job than loading it. Its contents must be subjected to stringent integrity checks, and then it must be written to disk in reverse order by records as discussed in the last chapter. The implementation of this elaborate procedure is shown in Figure 9-13. It consists of two independent routines, commit to do the checking and update for the disk output. These routines, although lengthy, are straightforward implementations of their pseudo-code (which is included in the source file as comments).

SUMMARY

The anthology system is becoming real. Here we have seen the implementation of nearly all the support modules, especially the critical routines that load and save the directory, and the antnew command that initializes an anthology. In the next chapter we will implement the rest of the anthology commands

10 THE ANTHOLOGY SYSTEM: COMMANDS

The implementation of this top-level logic of antput is shown in Figure 10-1. Aside from details like declaring a usage message, it is a simple implementation of the preceding list of tasks. The job of making a list of files has been pushed out into a subroutine listall; it is supposed to return a count of the matching files. The job of installing one file in the anthology has been encapsulated as a subroutine doput.

Listing Files That Match an Operand

Very well, we are faced with the task of implementing a subroutine which, given a command operand, will somehow build a list of all the filespecs that match that operand.

There are BDOS services to perform a directory search. They take a CP/M File Control Block (FCB) and return a disk directory entry for the next file that matches the (possibly ambiguous) filespec in the FCB. There are two toolkit services that pass these BDOS services along in terms of the toolkit's abstract type, the file.

The first of these, fdirbegn, takes two files, a source file and a target file. The source filedef must have been initialized by fassign. The fdirbegn function uses the BDOS to locate the first disk file that matches the source filedef. If there is one, it sets up the target filedef with that filespec, just as fassign would do.

The second toolkit function, fdircont (for continue), does the same job for the next matching file. Here, "first" and "next" refer to directory order, the accidental sequence of files in the disk directory.

The only restriction on these functions is that, by CP/M's rules, we may do no disk file operations between fdirbegn and fdircont, nor between one fdircont and the next. We are not allowed to find a first file, open and process it, then find the next. We must make a list of all the matching files, then process the list.

In what form shall we list the files, and where is the list to be kept? The directory-search functions return an initialized filedef, but a filedef is 64 bytes long. It would be more economical to make a list containing only the filespecs as strings. There is a toolkit function, fgetspec, that retrieves a filespec (or parts of one) from an initialized filedef. It's the inverse of fassign. We can use it to extract the filespec from the target file after fdirbegn or fdircont has initialized it.

We should allow for a generous number of files. After all, the user might enter a command like

and that could result in a long list. I chose 100 as an arbitrary but generous limit. A filename and a filetype, as a string, can't exceed 13 bytes, so 1,300 bytes is needed to store the list. If that space were reserved in the program's data segment, it would become part of the antput.com file. A better solution is to acquire the space at run time with dynamic allocation. Read Figure 10-2 with these considerations in mind.

The crux of the algorithm is in the statements

The fgetspec function extracts any combination of drivecode, filename, and filetype from an initialized file, makes a string of them, and appends that string to the string addressed by its second parameter. Here, the initialized filedef is workfile, which has been set up with a matching file by fdirbegn or fdircont. The third operand, the bit-mask 0110b, specifies that the filename and filetype (but not the drivecode) are wanted. The resulting string is laid out where register HL points, and HL is updated to point to its end.

Before the call to fgetspec, a null is stored where HL points. That creates a null string to which fgetspec may append its result. Afterward, HL points to the null at the end of the result; stepping past that points HL at uninitialized space where the next string, if any, may be built. The result of the loop is to build a compact sequence of strings, each adjacent to the next, each divided from the next by its null-byte delimiter.

Once the list of files has been built, the program needs some way to retrieve them one at a time and set them up in the AntSeq filedef for use. The subroutine setnext does this job (Figure 10-3).