x86 Is an Octal Machine (1995) | Hacker News Reader

x86 Is an Octal Machine (1995)

gist.github.com

145 pointsa1a106ed549 comments

This is an old article from the early 90s and I believe it may have been the first public mention of this fact about the x86 encoding, although no doubt many have independently "discovered" it before --- especially in the times when microcomputer programming consisted largely of writing down Asm on paper and then hand-assembling the bytes into memory using something like a hex keypad.

All of these are features inherited from the 8080/8085/Z80.

Here are the corresponding opcode tables in octal:

https://dercuano.github.io/notes/8080-opcode-map.html

http://www.righto.com/2013/02/8085-instruction-set-octal-tab...

http://www.z80.info/decoding.htm

Thanks for these links - very interesting.

Astonishing to think that we can see traces of the 8008 still today and that it wasn’t actually an Intel designed ISA (came from CTC / Datapoint).

The Datapoint 2200, the source of the 8008 instruction set, is an interesting machine. The CPU was built from TTL chips. To decode instructions, they used decimal BCD decoder chips, specifically the 7442. But they'd use them as octal decoder chips, only using 8 outputs.

The Datapoint 2200 documentation gave the opcodes in octal, so they were clearly thinking in octal. The 8008 documentation, however, didn't use octal or hexadecimal. The opcodes were given in binary, but grouped in 3 bits, octal style, e.g. 10 111 010. (They didn't specify opcodes in octal or hex!) I think the 8008 was right at the time where octal was on the way out and hexadecimal was taking over. (The 8008 assembler manual uses both octal and hexadecimal, but hexadecimal primarily.)

The Intel 8080 still specified the instruction set in binary, not octal or hexadecimal. The 8085 had opcodes in binary in a 1983 manual, but now split with a line into 4-bit chunks (i.e. hexadecimal-style). And then an appendix gave the opcodes in hexadecimal.

(Just some random history.)

One thing I forgot to mention: the 6502 microprocessor also uses groups of 3 bits in its instructions. However, they group them in the "wrong" way, aaabbbcc, so looking at the instructions in octal doesn't help you at all.

Also, after using the Xerox Alto, which uses 16-bit words, I realized that octal is terrible. The problem is that if you're looking at two bytes in a word, the values make no sense in octal. For example, the characters "AB" form the hex word 0x4142, while "BA" forms 0x4241; the two letters are clear. But in octal, "AB" is 0o40502 and "BA" is 0o41101; the two letters turn into unrecognizable numbers.

With 12-bit, 18-bit, or 36-bit words octal is pretty great. It just sucks with 8-bit bytes being grouped into 16-bit or 32-bit words.

That's just a consequence of us sticking to 8-bit bytes (and derivative word sizes), no? Octal would have made a lot more sense if it was, say, 12-bit.

“Us sticking to 8 bit bytes” is a consequence of having preferred BCD to octal in the past, so the causation is reversed (“12-bit words would have made a lot more sense if it was, say, octal.”) [Edited: actually 12 bit words would make sense in either case, as it's three BCD digits or four octal digits]

The Intel 4004 used four bits to manipulate a single BCD digit. The 8086 had BCD instructions. There were many reasons for preferring BCD when designing computer architectures, though my favourite which was already becoming less relevant at 8086-time was that it meant a full column on a punchcard wouldn’t be “all holes” and reduced the likelihood of the cards tearing.

I'm thinking of earlier times, before microprocessors in general. 6-bit bytes were a thing for a while - fairly logical, too, given that it was just enough bits to encode the entirety of ITA2 without needing any control codes to switch between character banks.

I implemented an 8086 emulator using the 1981 "iAPX 86, 88 USER'S MANUAL". It specifies the opcodes in bit patterns, so add is specified as "0 0 0 0 0 0 d w | mod reg r/m", where d is direction (mem to reg or reg to mem) and w is width (byte or word). Since this kind of pattern is used across many instructions it makes the code fairly easy to comprehend (to me at least).

Extracting the alu function from bits 4-6 means that you can group together the implementation of add, or, adc, sbb, and, sub, xor, to and from memory, for bytes and words into one function.

The code's not as fast as the "one code block per instruction" approach of something like DosBOX but at least it doesn't cause me dread to look at.

In case anyone is curious like I was and wants to look at the documentation, Bitsavers has some[1], including the octal opcode reference[2].

[1] http://bitsavers.org/pdf/datapoint/2200/

[2] http://bitsavers.org/pdf/datapoint/2200/2200_Programmers_Man...

Do you know if Federico Faggin copied the logic design of the 2200 or implemented the ISA using his own design?

The implementation of the 8008 is completely different from the 2200 (as is Texas Instruments' forgotten TMX 1795 implementation). It would be extremely inefficient to copy the TTL implementation, since that depended on what chips were available. But the biggest difference is that the Datapoint 2200 was a serial machine that used serial shift-register memory while the 8008 had a "normal" 8-bit datapath.

Thanks - even in 1972 we had multiple radically different implementations of the same ISA!

His own. There would have been no way to fit the logic design of the 2200 on a chip, both because of lack of metal layers, and because the 2200 was designed to be frugal in how many chips it used, using off-the-shelf chips, which is very different from being frugal in the amount of transistors you use when you have freedom to lay out each one by hand.

I thought the 8008 manuals used hex, but, as kens points out in https://news.ycombinator.com/item?id=30409889, the Datapoint manuals used octal.

My notes on the 8080 are at https://dercuano.github.io/notes/8080-opcode-map.html.

I kind of doubt it was actually the first. It's definitely an interesting/cute thing to notice and write up but I think the weird longevity of this particular piece owes more to the pioneering clickbaity framing (x86 is not really an octal machine, it's not surprising that people 'hadn't noticed' because obviously they had, etc) than the observations themselves.

The sibling comments disagree with you

I’m not seeing any disagreement in sibling or other comments

The comment by kens explains how the Datapoint 2200 both documented the design of the ISA in octal and used collections of three bits to decode at the fairly high TTL chip level.

https://news.ycombinator.com/item?id=30409100#30409889

The fact that instructions have some 'octal' structure doesn't make the thing an 'octal machine' and as importantly, a Datapoint 2200 is not an x86. The x86 is not an octal machine.

> The fact that instructions have some 'octal' structure doesn't make the thing an 'octal machine'

Basic concepts like the 8 GPRs are rooted in it's octal decoding roots. MOD/RM is still octal decoded, SIB is still octal decoded, etc. These fields aren't just three bits long, but also aligned to a three bit boundary within the byte being decoded.

> and as importantly, a Datapoint 2200 is not an x86. The x86 is not an octal machine.

The x86 traces its lineage to that and the points still hit. For instance, even when they added more registers in x86_64, it's still a three bit bank with simply a new prefix to select whether it's referring to the top or bottom 8 register bank out of now 16 total registers. There's some awkward places where you can't address different 8 register banks in the way you'd want to from an encoding perspective because of these continued restrictions going back to the Datapoint 2200.

Having written the HDL for a simple x86_64 decoder, it is very much still an octal machine.

They are still bits, not octdigits or whatever. When 4 bits are used, nobody calls these 'hex machines'. We can definitely spend a lot of time pedanti-digging into the details but at the end of the day, it's just an early example of 'viral title'.

> They are still bits, not octdigits or whatever.

Once again, it's not just that they're just groups of three bits, but the fields are also three bit aligned.

> When 4 bits are used, nobody calls these 'hex machines'.

I mean, most systems aren't aligned nearly as well on clear repeated boundaries the same way. The only other one that I can think of (the SH series) I for one have absolutely called a hex machine because you can read most of the machine instructions directly from the 4-bit nybbles. A four bit opcode and three address RISC instructions out of 16 GPRs means you can read the hex just about as easily as ASM.

The fact that most other machines correctly take a more bit level almost huffman coding route doesn't make x86 any more less octal derived at it's base.

On a machine where opcodes were easily decodeable by just looking at their individual nybbles, calling the machine a “hex machine” would be relatively natural. Obviously the term is to be seen in context, and not (necessarily) the defining characteristic of the machine.

Breaking instructions into 3 bit groups is awfully convenient (and you find it elsewhere, e.g. in portions of the THUMB encoding).

Datapoint did it consistently. And in a way that aligns with octal encoding. And then used octal in their documentation.

In turn, their instruction set basically became the 8008's, which influenced the 8080 and then 8086/8088. In turn, we still have this structure in x86 today: the instructions are prettily readable in octal.

I remember seeing a copy of this Usenet post years ago! It's one of my favorite "secrets" about x86's encoding.

The "core" (non-E/VEX, non-SSE, etc.) x86 encoding is wonderfully clever and terrible by modern standards, and Volume 2 of Intel's SDM is a great reference for how x86 manages to pack remarkably complicated addressing, operand, etc. semantics into just a handful of bytes. The result is a format that's remarkably hard to decode correctly, meaning that just about every software decoder for x86 is saturated with bugs[1] (FD: my project).

[1]: https://github.com/trailofbits/mishegos

Not sure if x86-64 REX prefixes count as "core" by your definition, but REX prefixes are incredibly wasteful and basically throw away all the code size gains that x86 would otherwise get over competing instruction sets. For most instructions, 4 bits are wasted to signal REX, and usually at least 1 more bit is wasted on register extensions not used by the instruction, particularly the SIB index extension. If you limit yourself to 32-bit x86, then yeah, x86 is pretty compact.

Yeah, I was talking about 32-bit x86. REX is indeed very wasteful :-)

(Even then, there's a lot of waste in the "legacy" prefix bytes, and I've always wondered who hacked those into the ISA instead of designing something more compact.)

I've always thought x86-64 was a very weird "not quite 64-bit" extension of x86 that was done awkwardly, unlike the 16- to 32-bit transition. The fact that AMD designed it and not Intel may have been one of the reasons. Then again, "full 64-bit" wasn't really necessary (and even now, a lot of code is fine with 32-bit ints).

Seeing that reminds me of one of the projects I want to do: the "World's Worst x86 Decoder". The basic idea is you toss most of the x86 manual, and just consider all of the prefixes as part of the opcode, so you say that x86 has (numbers are top of head, may be inaccurate) N opcodes, where N = 256 * 4 opcode maps * 4 group 1 prefix possibilities * 7 group 2 prefix * 2 group 3 * 2 group 4 * {REX/VEX/EVEX prefix counting is hard to do). It's the "world's worst" decoder, because not only does it not try to actually give a human-readable name for the opcode, it is also going to give patently wrong results for cases where "we packed 8 different instructions into this opcode, because they each take a memory argument, so the other R field in the ModR/M byte chooses a different instruction".

In my experience it's the "second page" of opcodes (0f xx) where the difficulty lies; the first page has been thoroughly explored and documented by now.

Historical note: the 286 was the first to have the second page.

I haven't seen the FD abbreviation, is it "full disclosure" ?

FD, or 375 octal. :)

Yes, that's "full disclosure."

> ALL 80x86 OPCODES ARE CODED IN OCTAL

That's a backwards way of saying it. I'd rather say, given the hardware structure of the bit fields of the opcode register, the binary opcodes are perhaps better described by octal notation rather than hexadecimal.

I can't interpret the author's intent, but I think they're trying to point out a conflict between how Intel and most other references document the x86 opcode byte (as a byte table, with no clear coordinate relation between bits) versus how the byte is structured internally (around octal values, which would reveal a coordinate relationship if visualized).

Exactly. Then there's no need to scream an odd headline.

I wouldn't say there's any "conflict". Who needs to know the detailed hardware structure? Compiler writers maybe, but they experience and order of magnitude more conflicts then.

> Who needs to know the detailed hardware structure? Compiler writers maybe, but they experience and order of magnitude more conflicts then.

I think this Usenet posting was written in the early 1990s, when a large number of people were probably still using macro assemblers to write large programs, and may have also been writing binary patches for those programs back when that was easier (no relocations to worry about!). It's definitely more of a "cool fact" than something you'd immediately apply, but it's the kind of thing I could see being useful to an assembly programmer of the period.

For my N=1 experience: I've written compact x86 decoders in HDLs before, and this octal mapping of the opcode structure was extremely useful in helping me determine an optimal (in terms of minimal gate counts) decoder structure. But that is indeed a very niche use case.

I was there. I've done my share of programming in assembler and building hardware for embedded systems. I certainly needed to know the hardware details, but I never saw a need to rewrite the opcodes in another notation.

I definitely appreciate the point of your last paragraph.

just throwing this out there, all the Digital/DEC PDP stuff used octal notation, and that equipment was quite popular in universities and labs, so engineers would have been quite used to it in the 70's. But they equally could have been responding to the same constraints the Digital engineers did. Just as there wasn't as much memory back then, there weren't as many registers and they didn't have as many bits.

A more agile way to think of it in your head is not as "octal vs hex vs decimal", but bit patterns. For example, if you decompose a byte into subfields and use a subfield of 3 bits to refer to one of 8 registers, you're going to naturally use octal. chmod on the unix command line is still easiest to use in octal because of the 3 rwx bits for ugo. It's not octal, it's bits and how many do you have.

To put it in the larger historical context, in the 1970s, octal was the preferred number system due to the prevalence of 36-bit, 18-bit and 12-bit architectures. 0xFFFFFFFF is elegant only for a 32-bit machine, for a 36-bit machine, 0o777777777777 is more natural.

A generation of programmers from the 1960s and earlier were trained to use the octal notation. This can be seen in the original Unix assembler - all numbers were assumed to be octal by default, no prefix is needed. It's also why the C programming language uses a single "0" to detonate octal numbers because it was considered convenient.

The IBM S/360 (1964) was the first major computer systems to break this pattern, switching to a 32-bit system with hexadecimal as its preferred notation, all the official documentation was only written in hexadecimal. This extremely successful machine was highly influential, and was likely the first exposure to hexadecimals to many. The standardization of ASCII in the mid-60s also marked the beginning of this transition from a 6-bit byte, which was the previous status quo, to an 8-bit byte. Then in the 1970s, several popular 16-bit and 32-bit minicomputers started to dominate the market. PDP-11, for example, was a 16-bit machine. Although octal was still its officially preferred number system due to habit and the fact that its instruction encoding was designed with 3-bit subfields, but the departure from 36-bit and 18-bit meant the days of octals was numbered (no pun intended), hexadecimals are simply more natural for dealing with integers.

The final death blow of octal was the microcomputer revolution. After 8-bit and 16-bit CPUs started to dominate the computing world in the late 70s and early 80s, the octal notation has gone and mostly fell out of favor. The x86 was a natural product of this era - it's officially documented in hexadecimal (although, like the PDP-11, octal was natural for its instruction encoding).

Because the Intel 8080 instruction set was octal, right?

This is cool: https://dercuano.github.io/notes/8080-opcode-map.html

The x86 is an enhancement of the 8-bit 8080. That also was an octal machine.

At some level this feels like a consequence of a design decision heading to the instruction decode logic. You can map from the Octal groups to the ALU wires and traces and gates in the 8080. They don't have to line up any more, we've moved. beyond that, but if you had the original chip naked and ran it, or ran a simulation, a "mechanistic" relationship between the octal groups might emerge visually?

It also feels like how the 'hidden' instructions get found.

Google tells me "July 5, 1992" about this article, though it doesn't say why, and Google Groups spat me out with a wave of unusability after a few seconds of trying to search there.

Is there currently any good public way to search usenet archives?

> any good public way to search usenet archives

no, you just hope google groups is nice to you (it wasn't the last time you and i had this discussion on hn).

but this time it is:

the posted copy is of the message https://groups.google.com/g/alt.lang.asm/c/bl21J0NYzBY/m/BjP... from "Jan 31, 1995, 7:17:40 AM".

it references an earlier, much shorter post https://groups.google.com/g/alt.lang.asm/c/ZNZp2K-SqhY/m/plK... from "Jul 5, 1992, 8:13:26 PM"

so the (1992) is not wrong, but most precisely it's (1995).

also, a mention on hn that came up whilst looking into this: https://news.ycombinator.com/item?id=12596371

Thanks! I've put 1995 above.

There's also a variant with a 1997 correction, I haven't looked if they are different beyond the notice.

https://web.archive.org/web/20200114164700/http://www.dabo.d...

That one shows up in HN comment search, perhaps for sufficient levels of nerdery this the equivalent of adding 'reddit' at the end of your google search.

> any good public way to search usenet archives

could be a good vanity project for another fts startup like algolia?

the mboxes are all here: https://archive.org/details/usenethistorical

Reply on news.ycombinator.com