Return to Answer

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.

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 the symbol type in the remaining 2 bits.

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

I don't know how PAL8 uses the hi bit of word 2 and word 3. They are carefully ignored when looking up a symbol in the table, so I assume they are not simply set to zero.

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.

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 was willing to entertain the complications of doing so on packed text.

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

For some storage devices, the characters were packed 3 chars to 2 words, but this was more a function of the storage device driver than of the application software.

The standard 3/2 packing method was somewhat strange -- byte 1 was 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 would produce the text with every 3rd char deleted.

        +---+---+---+---+---+---+---+---+---+---+---+---+
word 1  | byte 3 hi 4b  |          byte 1               |
        +---+---+---+---+---+---+---+---+---+---+---+---+
word 2  | byte 3 lo 4b  |          byte 2               |
        +---+---+---+---+---+---+---+---+---+---+---+---+

This format was introduced by the author of the RX01 floppy disk handler and subsequent developers never found a reason to break compatibility.

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

Odd char count with null padding:

    TEXT    @ERROR@

        +-+-+-+-+-+-+-+-+-+-+-+-+
word 1  |     E     |     R     |
        +-+-+-+-+-+-+-+-+-+-+-+-+
word 2  |     R     |     O     |
        +-+-+-+-+-+-+-+-+-+-+-+-+
word 3  |     R     |0 0 0 0 0 0|
        +-+-+-+-+-+-+-+-+-+-+-+-+

Even char count and no padding:

    TEXT    @STRING@

        +-+-+-+-+-+-+-+-+-+-+-+-+
word 1  |     S     |     T     |
        +-+-+-+-+-+-+-+-+-+-+-+-+
word 2  |     R     |     I     |
        +-+-+-+-+-+-+-+-+-+-+-+-+
word 3  |     N     |     G     |
        +-+-+-+-+-+-+-+-+-+-+-+-+

Odd char count with zero terminator and no padding:

    TEXTZ   @ERROR@

        +-+-+-+-+-+-+-+-+-+-+-+-+
word 1  |     E     |     R     |
        +-+-+-+-+-+-+-+-+-+-+-+-+
word 2  |     R     |     O     |
        +-+-+-+-+-+-+-+-+-+-+-+-+
word 3  |     R     |0 0 0 0 0 0|
        +-+-+-+-+-+-+-+-+-+-+-+-+

Even char count with zero terminator and null padding:

    TEXTZ   @STRING@

        +-+-+-+-+-+-+-+-+-+-+-+-+
word 1  |     S     |     T     |
        +-+-+-+-+-+-+-+-+-+-+-+-+
word 2  |     R     |     I     |
        +-+-+-+-+-+-+-+-+-+-+-+-+
word 3  |     N     |     G     |
        +-+-+-+-+-+-+-+-+-+-+-+-+
word 4  |0 0 0 0 0 0|0 0 0 0 0 0|
        +-+-+-+-+-+-+-+-+-+-+-+-+

/ 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

An interesting exception

The authors of the PAL8 assembler managed to cram a 6-char symbol, a 2-bit type, two 1-bit 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.

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.

        +---+---+---+---+---+---+---+---+---+---+---+---+
word 1  | type  |    char1*37+char2 (octal 0..1746)     |
        +---+---+---+---+---+---+---+---+---+---+---+---+
word 2  | ? |      char3*37+char4 (octal 0..2530)       |
        +---+---+---+---+---+---+---+---+---+---+---+---+
word 3  | ? |      char5*37+char6 (octal 0..2530)       |
        +---+---+---+---+---+---+---+---+---+---+---+---+
word 4  |            12-bit dependent value             |
        +---+---+---+---+---+---+---+---+---+---+---+---+

Recovery of the two characters from a radix-37 pair is slow, but this is done only once, when printing out the symbol table, and the code is fast enough.

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.

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.

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.

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         │
        └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

/ 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

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.

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.

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

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.