29

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?

New contributor
user22483 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
5
  • 13
    It saves a byte per string . On x80/x86 it needs additional instructions, so not really to be used everywhere, but ROM is a limited resource. On Motorola type processors (setting flags when loading) it comes free. – Raffzahn Jul 22 at 1:47
  • 2
    This was pretty common on the Apple II, e.g. Applesoft BASIC and DOS used it extensively. The Merlin and LISA assemblers referred to it as Dextral Character Inverted (DCI). I haven't seen it called by any other name, but googling that phrase didn't turn up anything relevant. – fadden Jul 22 at 4:19
  • 2
    FreeDOS Debug version 1.13 and newer use this format in their assembler table. In this older version it is fairly obvious; in later versions a macro automatically adds the flag. (In my fork I changed it to use a 4-bit count in the field prior to the string.) Most other strings in the application are ASCIZ or dollar-terminated. – ecm Jul 22 at 10:41
  • 17
    Pretty much anyone who programmed ASCII-based systems eventually found a memory-saving use for bit 7. (In my case, I had a full-screen PDP-11 display routine in which the high bit meant 'this character needs to be repainted') Thus I would guess the high-bit terminator use would have been independently invented more than once. – another-dave Jul 22 at 12:19
  • 2
    Probably came from the IBM 1620 - a variable-word length BCD machine where each BCD digit also had a flag bit which could be set and tested - a flag on a digit indicated the end of a field. This was a hardware architecture convention - arithmetic on number fields worked this way. See here at wikipedia. (Actually, just kidding: Very few people in that timeframe - or any timeframe for that matter - had ever heard of the 1620 much less knew its architecture/instruction set. Though I did, and had programmed it, in high school.) – davidbak Jul 22 at 20:33
14

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)

17

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.

15

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.

12

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": enter image description here

4
  • 7
    No need for an AND 80h; most 8-bit processors had conditional branches on the sign bit. – DrSheldon Jul 22 at 15:46
  • @DrSheldon: If you need to clear the high bit before storing in video RAM or whatever other use, you would need to AND away the high bit. So you do need an extra AND vs. 0-terminated strings, but it's for recovering the 7-bit ASCII characters, not for testing for termination. – Peter Cordes Jul 22 at 17:47
  • 1
    @PeterCordes: Good point, but then you would need to AND 7fh instead. – DrSheldon Jul 22 at 18:12
  • @DrSheldon: Yes, exactly. Or on a 386, btr ax, 7 to clear bit #7 of AL/AX and set CF according to the old value. Else you need to copy or reload the value from memory at the bottom of the loop, after printing it or whatever. – Peter Cordes Jul 22 at 18:48
10

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

2
  • 1
    It's possible that the same technique was reinvented many times over the early years - in retrospect it seems kind of obvious. – Mark Ransom Jul 23 at 15:42
  • 1
    Oh wow, I have not met many folks who have heard of CADOL. That was my first professional job out of college....in 1998 – StevenPatz Jul 24 at 3:28
4

It was a pretty obvious technique. Even obvious techniques have a first use but you couldn't define 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 disk format. 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.

4

The IBM 1401 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.

New contributor
Terrell E. Koken is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
-3

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!

New contributor
Dave Kanter is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
4
  • 2
    Doesn’t ASCIZ stand for NUL-terminated strings? – user3840170 Jul 24 at 18:02
  • 3
    Absolutely. ASCIZ is 'ASCII zero termination'. Setting the high bit of a character manifestly does NOT apply to DEC PDP-10 assemblers, which used 7 bits for an ASCII character. Perhaps there's some confusion with line numbers, which were a single 36-bit word in which there were 5 numeric ASCII characters, and the 'unused' bit was set. But that has nothing to do with string termination; it's a file-content convention, and the line number word is always at the start of a line. – another-dave Jul 24 at 18:35
  • 1
    The Wiki article is about null terminated strings. The question is not about null terminated strings. – UncleBod 2 days ago
  • 2
    I might have overthought my answer. I was certain the answer would have to do with Telex and once I bought that hammer, everything looked like a nail. Thanks! – Dave Kanter 2 days ago

Your Answer

user22483 is a new contributor. Be nice, and check out our Code of Conduct.

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.