9

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?

  • 1
    You might need to specify which system you mean since there are many ways it could be done. For example, OS/8 filenames will be different from WPS-8 spellcheck files. – Wilson Mar 1 '18 at 13:40
  • @Wilson On the 8 and 16-bit computers with which I am familiar, while there are of course many ways text could be handled, in practice there's only one way it ever was handled. If more than one way was actually in common use on the PDP-8, that in itself is very interesting, and I'd like to know all the common ways. – rwallace Mar 1 '18 at 13:48
  • 1
    Heh - when you've mastered character encodings on a 12-bit machine with word addressing ... try the PDP-10 (DECSystem-10): 5 7-bit characters in 36 bit words (with one left over to play bit-diddling tricks with!) (But the PDP-10 had arbitrary bitfield addressing as well as word addressing ...) (Also you could use SIXBIT encoding if you wanted.) – davidbak Mar 1 '18 at 23:57
  • 1
    PDP-10 byte pointers were derived from the ones on the PDP-6, which precedes the PDP-8. But the PDP-8 may follow the pattern of the PDP-5 which is even earlier. – Walter Mitty Mar 24 '18 at 20:38
15

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.

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.

8

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 :)

  • 3
    "Word processing was the application the PDP-8 was designed for" -- I assume, given the context of the rest of your answer, that you mean wasn't rather than was. – Jules Mar 1 '18 at 15:29
  • 4
    Using the -8 for text processing was not all that unheard-of. A whole lot of PDP-8's were used by newspapers for typesetting, using the 6-bit TTS (TeleTypeSetting) code. DEC had a software package for this and sold a bundled -8 configuration. WPS-8 came later when Diablo printers and floppy disks became cheap enough, and was very popular. I would also comment that the "real number crunching" ability of a PDP-8 was pretty darn limited, even for its day. – Jamie Hanrahan Mar 1 '18 at 19:29
  • 2
    @JamieHanrahan Word Processing: While the machine wasn't realy designed for it, it's still a computer and can be programmed to do much it wasn't optimal for. I once did real time sound/voice procesing on a /370. Also not exactly the machine designed for such, stillm, ge got it working :). For the 'number crunching', did you note the little remark about that? – Raffzahn Mar 1 '18 at 20:26
  • 3
    Even if text processing wasn't its primary use, it had a text editor and compilers for a number of languages. String processing was certainly necessary in them. – Barmar Mar 1 '18 at 21:42
  • 2
    What CDC machine was 36-bit? The 6600 thru Cybers were 60-bit until the 64-bit 180/200/205 series. They also made 48, 24, 16 and 12 bit machines. The Cyber PPUs were 12-bit. Cybers packed 10 6-bit chars to the word as 'display code' (CDCs almost-ASCII-with-crazy-warts) on NOS. There was a 12-bit encoding that allowed lower case that Plato used. Cybers had a dedicated shift unit that helped access characters. You could also push a lot of user interface out to the PPUs, so for some programs the PPU offloaded character handling (like block mode 3270 terminals, but with more smarts). – KJ Seefried Mar 2 '18 at 1:42
7

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.

  • 4
    "The PDP-8's magnetic core memory required write after read since the read operation was destructive and zeroed the read memory location." Very true; I believe this was true of all practical core memory, since writing a bit to a known state was the only practical way to read it. – Jamie Hanrahan Mar 1 '18 at 19:31
  • @JamieHanrahan But on most machines, the fact that the data needed to be written after a read was completely transparent to assembly language programmers. – JeremyP Mar 13 '18 at 10:24
  • +1 for mentioning the autoincrement locations which definitely must be considered as part of the ISA. – davidbak May 18 '18 at 4:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.