What's the origin of terminating strings by setting the high bit of the last character?

Question

I was looking at a hex dump of the ROM BASIC from the original IBM PC and found some byte strings like this (ASCII dump is on the right):

50 52 49 4e d4 9d 4c 49 53 d4 9e 50 4f d3 1b 45    PRIN..LIS..PO..E

With a closer look, I saw that 50 52 49 4e d4 is "PRINT" but with the highest bit of the last byte set--presumably to indicate the end of the string. We see the same pattern immediately afterward with 4c 49 53 d4 corresponding to "LIST". (Oddly, this convention is not used throughout the ROM; there are some plain old NUL-terminated strings in there as well.)

We even see this in the boot sector from the IBM PC-DOS 1.00 floppy disk:

0a 4e 6f 6e 2d 53 79 73 74 65 6d 20 64 69 73 6b    .Non-System disk
20 6f 72 20 64 69 73 6b 20 65 72 72 6f f2 0d 0a     or disk erro...

Right after "erro" there is the byte 0xf2. If you zero its high-order bit you get 0x72--the expected ASCII "r" to complete the word.

I have never seen this way of terminating a string anywhere else, and the only information I could find about it online was in the Tiny Basic design notes:

Commonly, one uses a special character (NUL = OOH for example) to indicate the end [of a string]. This costs one byte per string but is easy to check. A better way depends upon the fact that ASCII code does not use the high order bit; normally it is used for parity on transmission. We can use it to indicate the end (that is, last character) of a string. When we process the characters we must AND the character with 07FH to scrub off the flag bit.

This still leaves me wondering... Where did this practice come from? Where else was it used? And why use it for some strings in a program and not others?

Answer 1

The method was pretty common for small systems that had to do case-insensitive comparisons to user input or, simply, storage, of a lot of short strings (a standard case in BASIC interpreters).

Alternatives to mark the string end (like a length byte or a trailing zero or "$") would waste a byte per token - With BASIC tokens in the hundreds, some dialects would have wasted a lot of ROM space (and some did, the Sinclair QL, for example, stores its BASIC tokens with a length byte).

Examples for such usages are the Sinclair ZX BASIC interpreters and most of the Microsoft BASIC interpreters. You could argue the method was maybe a bit more common (because "cheaper") on Motorola-derived CPUs, where the load of a value to a register already sets the N flag (Z80 CPUs need an extra instruction to set the flags for this use case)

Answer 2

Commodore BASIC 2.0 (originally from Microsoft), used in the VIC-20 and Commodore 64, stored its table of BASIC tokens this way too. Instead of true ASCII, these machines used PETSCII, where lower-case "a" was (hex) 41 and upper-case "A" was represented as (hex) C1 (or as (hex) 61).

For instance, the token table contained GOSUB as "gosuB" with that last letter being (hex) C2. If the user typed this BASIC line:

1020 gosub 4000

The tokeniser would scan the token table looking for a sequence that matched the typed keyword up to a character that differed only in bit 7.

The code editor took advantage of PETSCII encoding to provide abbreviations. If the user typed this BASIC line:

1030 goS 3000

the "goS" would match up with the entry for "gosuB" using the same algorithm.

Answer 3

WordStar

As noted here, WordStar set the 8th bit of the last character of each word. This was a key difference between Document mode and Non-Document mode. Non-Document mode also did not automatically wrap lines of text. Both of these features of Non-Document mode were key to using WordStar as a programmer's editor, which was quite common in the late 1970s and early 1980s, as it was a powerful full screen editor compatible with any CP/M, CP/M-86, MP/M-86, MS-DOS or PC-DOS system.

Of course, if you forgot and edited a program in Document mode, or created a simple text data file (especially with short lines so that line wrapping wouldn't be an issue) then you would end up with text files that many compilers or other programs would not handle properly.

Answer 4

This practice goes back to at least 1976 with an architecture developed for CADO systems (a small multi-user minicomputer system). The language CADOL stored all strings with the high bit on the last character as a terminator.

The language had special instructions for removing the bit (SPOOL), setting the bit (PACK), and traversing a buffer full of terminated strings (SKIP).

Answer 5

This practice became widespread with small 8bit systems, which had a very limited ROM space. It has some advantages:

• It saves one byte per string.
• Easy detection of string end, just with "AND 80h" or such instruction
• It is OK for 7bit ASCII code (00h - 7Fh)

So it became a de-facto standard. Later, when characters with diacritics (or semigraphics glyphs) were added, were used two other methods: Trailing code (usually 00h, but I have seen FFh, or e.g. ASCII code for "$", as implemented in CP/M OS), or storing the length information (like "HELLO" stored as 5, 'H', 'E', 'L', 'L', 'O'). The last method is called "Pascal-style string" (used e.g. by Turbo Pascal on PC), the trailing zero is called "C-style string" or "ASCIIZ" (Z stands for Zero).

I remember the Sinclair ROM (ZX81, ZX Spectrum, etc.) uses this method to store tokens in the ROM:

DEFB    $35,$37,$2E,$33,$39+$80         ; PRINT

But string variables were stored in RAM as "flagged name + length + string itself":

Answer 6

The IBM 1401, introduced in 1959, used six-data-bit characters, but stored them internally in 8-bit magnetic core stacks. To the six data-bits were appended a parity-check bit and a "word-mark" bit. The word-mark bit was set only on the low-order character of a string (if memory serves me correctly; if not, it was the high-order one) whether that string was an alphanumeric string or a number. This permitted the 1401 to do multiple-precision integer arithmetic, with a precision up to half its memory's size less a few characters for programming. Thus the word-length in the machine was (almost) infinitely variable. This may be the origin of the flag bit.

Sorry if this is a little hazy; it's been nearly sixty years.

Answer 7

It was a pretty obvious technique. Even obvious techniques have a first use but you couldn't define that moment as 'invention' or 'originating'. That suggests that others got the idea by copying an originator and wouldn't have come up with the same idea, independently and quickly. They would and did.

When I first learned to programme in Z80 on a ZX Spectrum, it was a natural step to an idea that squeezed what you could out of every byte. Character codes 128..255 were used for reserved BASIC words and UDGs, which weren't going to be in messages, so it was natural to exploit that spare bit. I'm sure I was tipped off by reading the Spectrum ROM disassembly, which was a wonderful example to learn from, but it had already become the normal way to think after a while of programming on a very limited-speed, limited-memory machine.

The BBC Micro's Advanced Disk Filing System (ADFS) uses a similar idea. In its file descriptors, the 8th bit of the first 4 characters of the 10-character filename store the 4 file attribute bits. But I'd just call that efficient use of data storage.

Answer 8

On Commodore BASIC one neat thing they (Microsoft?) did with the MSB set on the last character of the string/word was that instead of doiing a CMP (6502) to see if the character in the accumulator matched the next character in the string, then checking for a zero result, you'd do an XOR. If you got a zero result then they matched and you could keep on looking through the string, but if not you checked to see if the result was 128/$80/10000000. If it was then you knew you'd got to the end of the string; as someone's pointed out, this was how you could use the goS to match with GOSUB.

So whereas CMP just gave match/no match information, XOR gave match/no match/got to end information.

Answer 9

IBM 1401 and Honeywell 200 family machines had 6 data bits, a word mark and an item mark bit per location; both on were a record mark. Most instructions went down in RAM from the units character to a word mark, but others went up, like I/O, and terminated on a word, an item or a record mark. The character could be BCD or unsigned binary. It was a BCDIC time, pre-ASCII, pre EBCDIC, way pre Unicode, way pre UTF-8!

Answer 10

Back in the early/mid-1970's I worked on IBM/360. For numeric data, the last bit indicated if the number was positive or negative. In hex dumps, the last nibble (a half byte) showed as C or D. Since memory and storage were limited back then. If I knew a number could only be positive, by using Assembler I could use the last bit as part of the number, doubling the value that could be held. This might be a little off, my wet-memory is not so good now, so the details are fuzzy.

Answer 11

All of the above answers are good examples of early use and reasons why, but good old Wikipedia shows that the origin is in the .ASCIZ directive of the assembly and macro languages used to run the PDP-10. The PDP-10 was DEC's workhorse computer of the mid-60's and a precursor to many of the systems listed above. Hope this helps!