How did the PDP-8 handle strings?

Question

The PDP-8 was a popular 12-bit minicomputer of the late sixties. It used word addressing, so that it always dealt in 12-bit words, of which it could address 4096 with a full bank of core memory.

In practice, a typical minicomputer would spend a great deal of its time dealing with text one way or another. In those days, the market didn't demand the ability to use lowercase, which meant the PDP could fit a character in 6 bits, so it could fit two of them in a word.

But since it couldn't address individual characters, what was the idiomatic way to handle strings? Clearly you could open code the necessary instructions for reading a word from memory and handling each component character separately, but on the face of it, that would be rather inefficient in time and (more important in those days) code size. The instruction set is very small (only eight opcodes!) and unless I'm missing something, doesn't seem to contain any special instructions for the purpose.

I found a 'hello world' program in PDP-8 assembly, but it doesn't use the contemporary encoding, it stores the string in ASCII, one character per word, which would surely have been unacceptably inefficient at the time: https://bigdanzblog.wordpress.com/2014/05/31/hello-world-program-for-pdp-8-using-pal-assembly-language/

So how were strings normally handled in contemporary code?

Answer 1

Technically, the three common methods for storing text in a PDP-8 memory were:

• two 6-bit chars per word, using the 64 glyph TTY character set
• padded to 8-bit bytes, packed three bytes per two words
• one char per word, accepting the overhead of four or five unused bits per char

With a few rare exceptions, programs handle text for two reasons:

• the program is intended to handle text as data
• the program must emit predefined messages to the console, or as part of its output

One char per one word

PDP-8 programs that manipulate text (e.g. TECO, WPS8, EDIT) use 7-bit ASCII encoding, storing one char per word and accepting the overhead of five unused bits per char. Scanning and searching text is difficult enough on any minicomputer; no one is willing to entertain the complications of doing so on packed text.

At least one program (WPS8) uses the extra bits to encode character attributes such as bold, underline, etc.

Three chars per two words

This information on 3/2 packing is taken from Doug Jones's excellent archive.

Files under the widely used OS/8 system consist of sequences of 256 word blocks. When used for text or other 8-bit data streams, each block holds 384 bytes. The standard 3/2 packing method is somewhat strange -- byte 1 is stored in the lo 8 bits of word 1, byte 2 in the lo 8 bits of word 2, and byte 3 in the high 4 bits of word 1 and the hi 4 bits of word 2. Failure to unpack correctly can produce text with every 3rd char deleted.

        ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
word 1  │ byte 3 hi 4b  │            byte 1             │
        ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
word 2  │ byte 3 lo 4b  │            byte 2             │
        └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

Because most of the PDP-8 system software was originally developed for paper tape, the binary object code in *.BN files is stored in paper-tape image form using the above packing scheme.

This format was introduced by the authors of OS/8 utilities such as ABSLDR, and subsequent developers never found a reason to break compatibility.

Two chars per one word

PDP-8 programs that emit predefined messages almost always use the upper-case only 64 char TTY set, and store them as two 6-bit chars per word.

The DEC PDP-8 assembler (PAL) (except the earliest editions) includes directives to pack literal strings. TEXT and TEXTZ both pack literal strings into two 6-bit chars per word; TEXTZ in addition appends a 6-bit zero terminator to the string before packing.

TEXT with odd char count appends one halfword of null padding:

    TEXT    @ERROR@

        ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
word 1  │           E           │           R           │
        ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
word 2  │           R           │           O           │
        ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
word 3  │           R           │        000000         │
        └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

TEXT with even char count appends no padding:

    TEXT    @STRING@

        ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
word 1  │           S           │           T           │
        ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
word 2  │           R           │           I           │
        ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
word 3  │           N           │           G           │
        └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

TEXTZ with odd char count appends a halfword zero terminator and no padding:

    TEXTZ   @ERROR@

        ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
word 1  │           E           │           R           │
        ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
word 2  │           R           │           O           │
        ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
word 3  │           R           │        000000         │
        └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

TEXTZ with even char count appends a zero terminator and null padding:

    TEXTZ   @STRING@

        ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
word 1  │           S           │           T           │
        ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
word 2  │           R           │           I           │
        ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
word 3  │           N           │           G           │
        ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
word 4  │        000000         │        000000         │
        └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

A routine to write 7b ASCII messages to the console might occupy 20 words, while the corresponding routine to write 6b packed TTY messages would require 34 words. This means that unpacking 6b text consumes less total storage if you have more than about 28 characters of message in all.

Here are a couple of "Hello, world!" programs using typical message dump subroutines:

/ 7-BIT HELLO PROGRAM

        *       200
        JMS     WRMSG
                "H
                "e
                "l
                "l
                "o
                ",
                " 
                "w
                "o
                "r
                "l
                "d
                "!
                0
        HLT
        JMP     200

/ WRITE MESSAGE TO CONSOLE
WRMSG,  0
WRLP,   TAD I   WRMSG   / MESSAGE TEXT FOLLOWS CALL
        ISZ     WRMSG   / BUMP RETURN ADDRESS
        SNA             / ZERO MARKS END OF MESSAGE
         JMP    WREX
        JMS     WRCHR
        JMP     WRLP
/
WREX,   TAD     K15     / CR
        JMS     WRCHR
        TAD     K12     / LF
        JMS     WRCHR
        JMP I   WRMSG
/
K15,    15
K12,    12

/ WRITE CHARACTER TO CONSOLE
WRCHR,  0
        SKCFL   TTY     / SEND 7B CHAR TO CONSOLE
         JMP    .-1
        WRSEQ   TTY
        CLA             / SOME CONSOLES DO NOT CLEAR AC
        JMP I   WRCHR

.

/ 6-BIT HELLO PROGRAM

        *       200
        JMS     WRMSG
                TEXTZ   @HELLO, WORLD!@
        HLT
        JMP     200

/ WRITE MESSAGE TO CONSOLE
/ CALLING SEQUENCE
/        ... AC MUST BE ZERO
/        JMS    WRMSG
/               TEXTZ   @MESSAGE@
/        ... NORMAL RETURN, AC == 0
/
WRMSG,  0
WRLP,   TAD I   WRMSG   / MESSAGE TEXT FOLLOWS CALL
        MQL             / SAVE NEXT MESSAGE WORD IN MQ
        ISZ     WRMSG   / BUMP RETURN ADDRESS
        CLA MQA         / EMIT HI 6B OF WORD
        BSW
        JMS     WRHF
        CLA MQA         / EMIT LO 6B OF WORD
        JMS     WRHF
        JMP     WRLP
/
WRHF,   0
        AND     K77     / EXTRACT 6B PAL CHAR
        SNA             / ZERO MARKS END OF MESSAGE
         JMP    WREX
        TAD     K40     / CONVERT 6B PAL TO 7B ASCII
        AND     K77
        TAD     K40
        JMS     WRCHR
        JMP I   WRHF
/
WREX,   TAD     K15     / CR
        JMS     WRCHR
        TAD     K12     / LF
        JMS     WRCHR
        JMP I   WRMSG
/
K77,    77
K40,    40
K15,    15
K12,    12

/ WRITE CHARACTER TO CONSOLE
/ CALLING SEQUENCE
/         ... AC MUST CONTAIN 7B ASCII CHAR
/        JMS     WRCHR
/        ... NORMAL RETURN, AC == 0
/        
WRCHR,  0
        SKCFL   TTY     / SEND 7B CHAR TO CONSOLE
         JMP    .-1
        WRSEQ   TTY
        CLA             / SOME CONSOLES DO NOT CLEAR AC
        JMP I   WRCHR

One interesting exception

No discussion of string handling on the PDP-8 would be complete without a description of the insanely compact format of the PAL8 assembler symbol table.

The authors of PAL8 managed to cram a 6-char symbol, a 2-bit type, two boolean flags, and a 12-bit defined value into each 4-word symbol table entry. They did this by restricting the symbol character set to 36 chars plus a null terminator, and using radix encoding instead of concatenation.

A PAL8 symbol can contain only A..Z and 0..9, must begin with A..Z, and is truncated at 6 chars. To construct a symbol table entry, the chars are first mapped to these char codes:

     0  terminator or null padding
 1..26  A..Z
27..36  0..9

Then the mapped values are stored 2 per word in radix-37 format, that is, hi-char * 37 + lo-char. Since the greatest char code is 36, the greatest value of a radix-37 pair is 36 * 37 + 36 = 1368 (octal 2530) which occupies only 11 bits. This leaves one bit available to store a boolean flag.

The maximum value of the first char pair is even smaller. A symbol must begin with A..Z, so the code for char 1 can only be 1..26. This means the greatest value for word 1 is 26 * 37 + 36 = 998 (octal 1746) which occupies only 10 bits. PAL8 stores symbol type information in the remaining 2 bits.

        ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
word 1  │ type  │    char1*37+char2 (octal 45..1746)    │
        ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
word 2  │flg│      char3*37+char4 (octal 0..2530)       │
        ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
word 3  │flg│      char5*37+char6 (octal 0..2530)       │
        ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
word 4  │            12-bit dependent value             │
        └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

PAL8 uses the hi bit of word 2 and word 3 to store additional symbol type information.

Also, the first word of a valid entry can not be zero. The minimum value is 37 (octal 45) for the single-character symbol "A". This allows the entire symbol table table to be null-terminated.

Recovery of the two characters from a radix-37 pair is slow, but this is done only once, when printing out the symbol table. Originally the program had only to keep up with a printer or teletype console.

I don't know if earlier editions of PAL used a looser packing. I have the source code for only the OS/8 PAL8 assembler.

Radix text packing was also used on other machines; for example PDP-11 software often used radix-40 to store three chars per 16-bit word.

Answer 2

When I used the PDP-8, 7-bit ascii was in use. Strings would start on an word boundary, and be packed 1.5 8-bit bytes per word, and the last nibble might be unused.

You'd use a subroutine to output them somewhere (e.g. teletype), and that subroutine would unpack them for sending as individual 8-bit characters. The subroutine would have code for each case: (1) byte left justified in 12-bit word, (2) byte straddling 12-bit words, and (3) byte right justified in 12-bit word. The subroutine would handle each case in succession, after the last case, start over.

Also, don't forget that the PDP-8 has indirect load/store through a pointer in memory, and 8 locations (on the base page at octal addresses 10-17) are special in having auto-increment operations. (They're used almost like registers.)

This means even with only one accumulator register, that you can do movmem and strcpy-like operations pretty easily. You put your source & target into the auto-incrementing memory locations, then put a (negative) count in another memory location.

Loop:   TAD I 10      ; source in auto-incrementing pointer at word address 10
        DCA I 11      ; target in auto-incrementing pointer at word address 11
        ISZ 20        ; counter in memory location 20, increments & skips on zero
        JMP Loop      ; backward branch to loop start; skipped to end the loop

---

The PDP-8's magnetic core memory required write after read since the read operation was destructive and zeroed the read memory location. This meant that any read had to be automatically followed by a write of the read value. By adding an increment operation to the re-write, they achieved both auto increment for loads/stores, and, increment and skip on zero (which also operates on memory location), virtually for free since it has to re-write anyway.

Answer 3

In practice, a typical minicomputer would spend a great deal of its time dealing with text one way or another.

Not really. PDPs where mainly used to automate machinery and related number crunching (only small numbers and little pebbles from today's view). Text wasn't among high priority.

In those days, the market didn't demand the ability to use lowercase, which meant the PDP could fit a character in 6 bits, so it could fit two of them in a word.

Jup. A 6 bit encoding was perfect to cover all characters of the back then common 5 bit ITA2 encoding without the need of switching sequences (*1). This was a quite common practice. For example IBM's701 and follow up used 36 bit words and packed always 3 characters into a half word.Similar CDC's 6000 series used 60 bit words with 10 bytes each (*2).

But since it couldn't address individual characters, what was the idiomatic way to handle strings? Clearly you could open code the necessary instructions for reading a word from memory and handling each component character separately, but on the face of it, that would be rather inefficient in time and (more important in those days) code size.

Exactly that has been done. Just think of the way 8 bit CPUs handle 8 bit words as two hex digits. It involves some shifting and masking. And eventually buffers with unpacked characters to do overlapping operations. Remember, memory space was even more scarce than processing time.

With the PDP 8/E (IIRC) a new opcode got introduced: BSW or ByteSWap switched the upper and lower byte (*3), simplifying the handling of packed byte strings.

The instruction set is very small (only eight opcodes!)

It's a matter of definition, as one could also define the PDP as having more than 42 opcodes, as 'opcode' 7 was used to define 34 subcodes.

and unless I'm missing something, doesn't seem to contain any special instructions for the purpose.

The missing point would be the missing need for text manipulation. Word processing wasn't the application the PDP-8 was designed for. Texts where usually only output as fixed strings for like labels and headers. Everything else where numbers, which needed conversation from binary anyway.

I found a 'hello world' program in PDP-8 assembly, but it doesn't use the contemporary encoding, it stores the string in ASCII, one character per word, which would surely have been unacceptably inefficient at the time

Not really, as such character by character manipulation was only needed for very special situations.

So how were strings normally handled in contemporary code?

99% was unpacking strings and printing them. Works fine with a limited instruction set. The rest was done in line buffers with one character per word and results (if there where any at all) again packed before storing.

---

*1 - To some degree it's like Unicode half a century later - an extended code to cover multiple pages without switching.

*2 - Again, these machines weren't so much about text as real number crunchers.

*3 - Jup, bytes, as they where 6 bit bytes :)