Previous Contents Next

CHAPTER 4: TABBIT AND UNTAB

In this chapter we develop another pair of utilities. These programs tackle the problem of inserting and removing tabs from a file of ASCII text. The problem is interesting, and a simple one to state. Because of that, it is becoming a standard exercise for systems programmers. At the end of the chapter we'll compare my solution to one from another book.

THE TAB PROBLEM

CP/M has a convention for the use of tab characters. Every serial I/O device is assumed to have tab stops set at every eighth column. If columns were numbered from zero, the stops would be at columns 8, 16, 24, and so on. It is conventional to number columns from one, so the usual way of stating the tab convention is to say, "tab stops are assumed in columns 9, 17, 25, etc."

Because of that assumption every tab has a consistent interpretation, no matter where in a file it appears. A tab always stands for the number of spaces needed to move to the next eighth column. As we noted in the last chapter, the effect is to provide automatic data compression. The convention almost eliminates the presence of strings of blank characters in files.

Of course, not all programs put tabs into their output files. Some should not! If the data in a record occupies a different column than it will in its eventual output, tabs should not appear in it. Let's look at an example. Imagine a BASIC program like this,

... 3000 FOR I=1 TO J 3010 WRITE#1,DESC$(I),PRICE(I) 3020 NEXT I ...

which prepares an output file like this:

... " Widget",0.45 "Midget Widget",0.85 "Bigger Widget",1.49 ...

The programmer has put leading blanks in the description field for some good reason. They should not be replaced with tabs. The fields of the records bear no necessary relation to the columns in which they begin. They might become input to a program like this,

... 7200 FOR I=1 TO J 7210 READ#1,WHAT$,COST 7220 PRINT "Description: ";WHAT$,COST 7230 NEXT I ...

which, given tabs in the input file, will not produce the output expected. The tab that made sense in column 1 of a record will not be correct in column 14 of a print line. If the data file was edited, and if the editor program replaced blanks in its output with tabs, the second program would produce the wrong output.

On the other hand, some programs produce files that don't contain tabs when tabs would be perfectly alright. Files brought to CP/M from some other operating system often don't contain tabs. Worse, files from some other operating system might contain tabs that are based on some other tab increment than eight.

If we had a utility that compressed a file by replacing blanks with tabs wherever possible, and another one that replaced tabs with the spaces they stood for, then we could solve any of these problems. We want to be able to take a file without tabs and TABBIT, and to take a file containing tabs based on any regular increment and UNTAB it.

SPECIFYING TABBIT

The TABBIT command reads an input file of ASCII text, and writes an output file in which strings of blanks have been replaced by tabs wherever that can be done without changing the appearance of the file as printed. TABBIT may be applied to any file. However, it is not recommended for use on files that will receive other processing before they are printed (or else such files should be UNTABbed before processing).

The syntax of TABBIT is:

TABBIT inputref outputref

TABBIT uses the utility convention for its input and output filerefs. An omitted input drivecode will be replaced with the default drivecode. If a part of the output fileref is omitted, the corresponding part of the input fileref will be used. The output file may replace the input file.

DESIGNING TABBIT

We established a general pattern for any utility in Chapter 3. The initialization, input, and output routines developed for PACK will serve nicely for both TABBIT and UNTAB. All that needs to be designed is the main loop. I sat down with a fresh cup of coffee one morning and sketched out Figure 4-1.

It seemed obvious that there should be a column counter. When a blank appeared, the column number would tell how many blanks had to follow the first one in order for a tab to be possible. The column count would represent the motion of a real output device—a terminal, for example—when driven from the input file. It would be based on a zero origin. Then when the column count modulo eight was zero, we would be at a tabstop. Taking an integer modulo eight is easy in binary arithmetic, and that is doubtless the reason that CP/M uses a tab increment of eight.

Maintaining the Column Count

It occurred to me that there was more to keeping the column count accurate than I had thought at first. It had to be reset on each line. And what about control characters? I expanded the important parts of Figure 4-1 into Figure 4-2. When the current character is a printable one (other than blank), the column count must be incremented. If it is a carrier return, the count goes to 0. That's true whether or not we are at an official CP/M end of line (return followed by linefeed).

What if the character is a tab? After all, we can't prevent the user from running TABBIT against a file that already contains tabs. The count has to be moved on to the next tabstop. I devised the expression

Column := 1+(Column or 0111b)

as an easy way of bumping Column to the next multiple of eight.

I blush to admit that it was only as I was writing the first draft of this chapter that I remembered the backspace character. The line

elif (B is AsciiBS) then Column := max(Column-1,0)

was a very late addition to all the figures in this chapter. Note the use of max to ensure that Column doesn't go below zero. A real output device can't backspace beyond the left end of its carriage, and therefore Column must not become negative.

The other control characters have no effect on the column. A linefeed, for instance, causes vertical motion but not horizontal motion. (Some printers, whose designers apparently never troubled to read the ASCII standards documents, return the print head on receipt of a linefeed. If you are unfortunate enough to own such a non-standard device you have my sympathy, but don't expect me to write a non-standard program to compensate.)

A Mistaken Optimization

On the second or third pass over the design, it occurred to me that Column didn't need to be a full count of the current column. All that mattered was Column modulo eight, the column number relative to the most recent tabstop. I blithely changed everything to reflect this insight. For instance, the effect of a tab on Column could be expressed as "Column:=0."

Then I remembered the backspace. There is a difference between backspacing from column 8 to column 7 on one hand, and backspacing from column 0 to column -1 on the other. The only way to distinguish between the two cases is to keep a complete count of the actual column. I had to remove all my clever optimizations.

Could Column still be kept in a single byte? Absolutely not! A line of a CP/M file can have any length. I find it very irritating when a program refuses to work with lines longer than 255 bytes. Column has to be a 16-bit counter, not just a byte.

Substituting Tabs For Blanks

The purpose of TABBIT is to replace strings of blanks with single tab characters. If there are eight blanks beginning in column 0, they can be replaced with a single tab. If there are seven blanks starting in column 1, they can be replaced, and so on.

The program structure (borrowed from PACK) provides a two-character window on the file. We can look just one character beyond the current one. If there is a blank in column 0, how can the program tell whether or not seven more blanks follow it?

Table 4-1 summarizes the relationship between the numbers. A tab at some Column must stand for a number of blanks that depends on the value of Column modulo 8. Given a blank in some column, the number of blanks that must follow it before a tab can be used is expressed by 7-(Column mod 8). Table 4-2 shows this requirement in terms of the state of the program variables and the input file.

What can the program do when it finds itself in a situation like that shown in the last line of Table 4-2? It can only find out that the file contains the right number of blanks by reading the file. If there are enough blanks, then after reading them the program can write a single tab. Suppose that there are not enough blanks to allow a tab? By the time that is known, some blanks have been read. They must then be recreated in the output file.

The Recursive Test

I fiddled with the problem, producing abortive efforts like that in Figure 4-3, until the coffee cup was empty. Then I went out for a walk.

In the middle of a stride the word "recursion" popped into my mind. Of course! What Figure 4-3 contains is an unrolled account of a recursive procedure. On the way back to my office, I worked it out.

When B contains a blank, set

T := 7-(Column mod 8)

If T=0, then a tab can replace the blank in B. Otherwise, read one byte and decrement T; if B still contains a blank, start over from the last sentence. But if B turns up nonblank, there weren't enough blanks to permit replacing them with a tab, so stop with T>0.

That expresses the test in a way that could be coded as a loop. But when the test fails, the problem remains of recreating the blanks that were swallowed while testing. Coding the test as a recursive procedure makes that problem easy to solve. The code I arrived at appears in Figure 4-4, which expands the lower half of Figure 4-2. Three points are indicated by letters in braces.

The code begins by discarding the case of a single blank occurring just before a tabstop (i.e. the case of T=0). After all, there is no effective difference between a blank in column seven and a tab in column seven. Replacing one with the other doesn't compress the output. The same test discards any case of a single blank (the case of C<>B). A single blank that is not just before a tabstop can't be compressed. Single blanks are common in files of text, so it may save some time to avoid looking at them.

Once the program knows there are at least two consecutive blanks and at least two columns to a tabstop, it calls the recursive procedure TesTab. At point {A} TesTab has reduced the situation one step toward T=0. If it has reached that point, it exits (the test is successful).

If it has not reached the case of T=0, the test must continue. If C contains a blank, TesTab calls itself to continue the test. At point {B}, if T hasn't been reduced to 0, the test has failed. Either it failed because C held a nonblank at this level, or because C turned up nonblank at some lower level of TesTab. Either way this level of TesTab must replace the blank that it swallowed prior to point {A}. Table 4-3 shows the course of the important variables in three different cases.

The complete pseudo-code of TABBIT appears in Figure 4-5. Half a pad of notepaper was sacrificed to get it right. The basic notions never changed, but it took me a number of tries to work out all the details of managing the B, C, and Column variables so that they came out right in every case. It took even longer to satisfy myself that they did come out right.

Often when I thought I had everything arranged perfectly, I would think of a way to simplify things (or would discover an oversight like the missing backspace). Then it would have to be rewritten and checked out out again. Had I gone to the machine to begin coding assembly language, the first version that worked would have been the final version. I'm glad I did not, for the result has an elegance that I find satisfying. In the end, coding the assembly language took just over 30 minutes. The program worked correctly the first time, and that was even more satisfying.

THE TABBIT PROGRAM

The assembler version of TABBIT appears in Listing 4-1. The logic is not a simple translation of Figure 4-5. I couldn't resist the temptation to take advantage of machine language optimizations. That distorted the shape of the program, although Figure 4-5 is still a faithful portrayal of the logic.

The first coding trick is the use of a three-way branch (Listing 4-1, lines 63-68). After a comparison, the 8080's flags distinguish three cases—less, equal, and greater (the original FORTRAN language was built for a machine with similar flags, and its original IF statement reflected that design by providing for three targets). Once DEL has been disposed of, the ASCII code breaks neatly into the Blank, the control characters less than Blank, and the printable characters greater than Blank. The 8080 has the irritating quirk that the jumps after a comparison have to be coded in a certain order. If the test were coded as

CPI AsciiBlank JNC IsPrintable JZ IsBlank

the second branch would never be taken. The carry flag is false in both the equal and the greater-than case. The designers at Intel did a better job with the machine flags in the 8086.

I found that I had a free register. B and C are the text window, and D and E compose the Column count. The variable T fit nicely into register H. That left register L unused. An unused register is a rare and precious thing in a machine as limited as the 8080. In looking over the code I noticed that there were several uses of an immediate constant of 07h. Putting the constant in the spare register yielded a net saving of exactly two bytes of code and an insignificant number of machine cycles. Still, it was a pleasure to see a line of one-byte instructions in the IsBlank routine. As is often the case, the optimization was one of the programmer's morale, not of the program.

SPECIFYING UNTAB

The UNTAB command processes an ASCII file to remove all tabs and replace them with the blanks that they represent. It assumes 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) is used. However, a different increment between 1 and 255 may be specified in the command line.

The syntax of UNTAB is

UNTAB inputref outputref /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 parameter /increment may be omitted. If it is, the command assumes a tab increment of 8. A different increment may be specified by coding a slash followed immediately by the increment number. For example,

untab thisfile thatfile /10

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

DESIGNING UNTAB

Parameter Syntax

It is only recently that Digital Research has attempted to standardize the syntax of CP/M and MP/M commands. Think of the variety of ways of coding parameters. The ASM assembler takes parameters as single letters in the filetype position. MAC takes two-letter parameters following a dollar sign. PIP looks for its options inside brackets. Other software publishers have used the slash as a delimiter for parameters.

The preliminary documents for MP/M 2 state that the preferred method is to enclose options in brackets. That is what the new MP/M commands require. But those documents also authorize the slash as a delimiter and as a marker for optional parameters.

I elected to use the slash because there was no need to surround increment with delimiters. It is much simpler to scan the command line for a slash, then take decimal digits until a nondigit is found. If the command required two or more parameters, something more elaborate would be needed.

Getting the Parameter

UNTAB was easy to design once the ground had been prepared by work on TABBIT. The only notable feature of the initial sketch (Figure 4-6) is the line "get tab increment from command line." That should be done before the files are initialized. Otherwise, some early file activity might alter CpmBuffer, where the command tail is found.

When I expanded the sketch into a pseudo-code design (Figure 4-7) I had to give more thought to the parameter. I turned aside at that point to code the library routines that would be used. The program had to be able to distinguish four different cases:

1. The parameter was omitted
2. The parameter was given correctly
3. The parameter was not numeric
4. The parameter was numeric but too high or low

It turned out to be fairly easy to detect the first three cases in the included subroutines (see routines CmdNumOpt and DecToBinary in Appendix C). But the valid range of an option is the concern of the specific program. The library routines can tell if an option was given and if it was numeric, but the detection of an number that is too high or low has to be left to the main program.

The routine (DecToBinary) that converts the digits to a binary number is not very sophisticated. It will accept leading zeros (so that "/0009" is a valid parameter) but any nondigit ends its conversion. Thus "/1-", with a simple typographical error for the zero digit, will be taken as "/1". That is adequate for this application, but it might be a problem another program.

The Main Loop

The main loop of UNTAB (Figure 4-7) is very similar to that of TABBIT. Most of the code is concerned with keeping track of the current column. A blank can be treated as just another printable character.

The code is simpler than TABBIT because no look-ahead is needed. In TABBIT, the appearance of a blank 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 blanks will be substituted. Only B, the left edge of the text window, is needed.

Ah, but how many blanks? If we assumed a fixed tab increment of 8, the answer would be simple to obtain. It would be 8-(Column mod 8), as shown in Table 4-1. But that expression is just a special case of

TabInc - (Column mod TabInc)

where TabInc is the regular tab increment. In TABBIT we used a fixed increment of 8, and modulo was an easy function to implement. Here we must find Column mod TabInc when TabInc may be any number from 1 to 255. Since both are positive integers, "modulo" and "remainder" are identical (remainder and modulo are different functions when either argument is negative). We have to perform a division of the 16-bit Column by the 8-bit TabInc. Such division is not difficult to do, and I added an 8-bit-into-16-bit divide to the library of included routines.

THE UNTAB PROGRAM

The assembly code of UNTAB appears in Listing 4-2. It contains no techniques that haven't been used in earlier chapters. Beginners might like to examine the command-line subroutines that it includes. They are woven together with a fairly complicated set of conventions for the use of the Zero and Carry flags. I am not especially fond of those. They caused the only two bugs that turned up in UNTAB. Now that the details have been worked out and sealed away in library routines where I won't have to think about them again, I find them tolerable. They can be justified in small, general purpose routines, but to tie together the main part of a program with flag settings is to ask for trouble.

Both UNTAB and TABBIT are built around a tall heap of if...elif...else statements. These represent the general form of a Case statement and they could have been coded that way. The table-driven Case structure of program UNPACK would work in either of these programs.

An Initialization Problem

The original version of the file initialization code tested for an omitted filename by comparing its first character to a blank character. That was valid as long as the input and output filerefs were the only permitted operands. However, UNTAB accepts the /increment parameter as well. If the output fileref is omitted, the CCP will put the /increment parameter into the default FCB in its place. If both filerefs are omitted, the parameter will turn up in the default FCB as the first command operand. In either case, the slash, not a blank, will appear as the first character of the omitted fileref.

As a result, the first time I ran UNTAB with an omitted output fileref and a specific increment, it produced an output file named "A:/10." It took a while to discover where the output had gone! The solution was to make the initialization code test for an omitted fileref by calling the included routine Delimiter. Delimiter returns "true" if a character is any of the standard command delimiters, including the space and the slash.

ANOTHER SOLUTION

Programming is a human activity, not a mechanical one. There are psychological and moral lessons to be learned, as well as logical and mathematical ones, if we are to work at our best. One such lesson is the Fallacy of the Best Solution.

I spent several hours working out the logic of TABBIT. The result was correct and, although it is not especially easy to read, it has a certain elegance. It is not surprising, then, that I fell into the trap of thinking that I had found the Best Solution. Kernighan and Plauger's book, Software Tools [1], administered a needed corrective.

Software Tools had been on my bookshelf for several years. I bought a copy of its successor [2] not long before beginning work on TABBIT, anticipating a pleasant time rereading an old friend. When I saw that Chapter 2 opened with a program "entab" to replace blanks with tabs, I set the book aside until TABBIT was finished.

Then I compared my solution to that of Kernigan and Plauger. I have translated the algorithm of "entab" into the pseudo-code used in this book so that you can make the same comparison (Figure 4-8 versus Figure 4-5). It was, for a moment, quite unpleasant to find that their solution is simpler and more elegant than mine. That is the penalty for falling into the fallacy of the Best Solution: the nasty ego-shock of finding that someone else has worked the same problem and arrived at a Better Solution.

This, of course, was not the first time I had fallen into the trap of the Best Solution and paid the penalty for it. Many times in the course of a software career I have had my complacency about a piece of code shattered by someone's innocent question, "But why didn't you just..." There is a simple way to avoid this punishment. It is to practice what Weinberg [3] named "egoless programming" as a normal part of your work. In egoless programming, one gets the input of other people at all stages of design and coding. It is my experience that, in programming, two heads are always better than one. Not only does egoless programming spare one the shock that comes when one's Best Solution is revealed as sub-optimal, but the cooperation of a team nearly always converges on the genuine Better Solution.

One disadvantage of personal machines is that they make it harder to practice egoless programming. There you are, alone at the keyboard of your CP/M system, possibly the only programmer for blocks around. How can you avoid the trap of the Best Solution?

There are some things you can do. The first is, at every stage of your work, to remind yourself that your solutions are almost certainly not the best possible. Become a stern critic of your own code; examine it for the oversights that (you tell yourself) are sure to exist in it. Another thing is to read other people's programs. You can learn a great deal just from seeing how another person's mind deals with programming problems. It's always a healthy surprise to discover that other people's minds work differently from your own!

But there is really no substitute for interaction with others. In 1971, when time-sharing systems were still a novelty, Weinberg wrote "...if there is a common room next to the place where computer output is returned, useful mixing can take place there. Personalized delivery services, however, tend to isolate the programmer from this type of interaction, and terminal systems for remote-job-entry and exit may make his isolation worse. This aspect of terminal operations is probably going to be a curse, not a blessing." [4] The same aspect of personal computers allows programming to become an activity so intensely private as to be nearly autistic. Whatever you can do to expose your work to the inspection of others—friends, colleagues, the local computer club—will improve its quality, and will increase the satisfaction you take in it.