7 ms·

The x86's Decimal Adjust after Addition (DAA) instruction

96 points by zdw 4y ago

kens 4y ago
Anyone have questions on the DAA instruction? This is a bit of a niche post, I have to admit.
- jamesfinlayson 4y ago
  If BCD is the only thing it's applicable for I don't think it has much use - I can't imagine any modern compilers generating BCD instructions nor any hand-rolled assembly making use of it these days. > Even Intel's x86 processors are moving away from the DAA instruction; it generates an invalid opcode exception in x86-64 mode. That's the first I've heard of that so I'm guessing no one complained.
  - rvalles 4y ago
    I have used DAA recently, in my "load option ROM in RAM floppy tool"[0]. Specifically, I use it for printing numbers as hexadecimal[1], as unfortunately the ASCII standard is not arranged in a way as to facilitate this. 0. https://github.com/rvalles/optromloader/ https://github.com/rvalles/optromloader/ 1. https://github.com/rvalles/optromloader/blob/master/optromloader.asm#L182 https://github.com/rvalles/optromloader/blob/master/optromlo...
- gfaure 4y ago
  I only remember the DAA instruction because it was the last instruction I implemented in my Game Boy emulator. Since it's mainly used for end-user display of game scores, for most games it doesn't lead to any behaviour problems apart from messed up numeric strings, even if not implemented.
  - MBCook 4y ago
    Ditto! I fished the CPU emulation on the emulator I’m writing around Christmas and I purposefully pushed DAA to the end of my instruction TODO list. It’s not that bad conceptually but in practice making sure all the flags are set right by the other instructions so DAA would work is a bit of a pain.
  - dezgeg 4y ago
    Another GB emulator hobbyist here :) My dim recollection is that Pokemon uses BCD for in-game cash, so there you might be able to 'cheat' or either never buy anything if BCD stuff is left unimplemented :)
- anticensor 4y ago
  Can you make a post on the ASCII adjust series too? I would have expected both in a single blog post, though.
  - kens 4y ago
    There's not a lot to say about the ASCII adjust instructions. I mention them in footnote 2. They are the same idea except they act on a single BCD digit. They aren't specifically for ASCII, but if you ignore the upper nybble, ASCII digit characters match the BCD values.
- atq2119 4y ago
  Since reverse engineering the 8086 is your thing, I was really hoping for this blog post to go into how the instruction is actually implemented. Is it all fixed function in the ALU? Is it micro-coded and if so, how?
  - userbinator 4y ago
    Given that it's a 4-cycle instruction (and a reg-reg add is 3), it seems rather quick to be microcoded. (As an aside, Google gives absolutely horrible results if you search for "8086 DAA instruction timing". At least half the ones on the first page seem to be for the 8085, there's also this article itself and the discussion on HN, neither of which have the information.)
  - kens 4y ago
    This article is sort of a prelude to looking at the 8086's hardware. (I was looking at the Intel documentation and realized it was confusing and slightly wrong, so needed to figure out what is really happening.) The 8086 implements the instruction in microcode, but like all the arithmetic operations, the interesting stuff happens in the ALU. In particular, the ALU hardware has a DAA instruction that figures out what correction value is needed and adjusts the flags appropriately. Another microcode instruction performs the addition. So the microcode is just four instructions long.
deleted 4y ago
[deleted]
tasty_freeze 4y ago
This instruction is lifted pretty directly from the 8080 behavior. One of they improvements the Z80 made over the 8080 was that DAA worked after either ADD or SUB, whereas the original DAA worked only for add.
userbinator 4y ago
More than one person noticed the addition of 6, and the significance that has to conversions between ASCII hex and binary, and came up with short (branchless) sequences for doing so using these and the other BCD instructions. This 6-byte sequence featuring DAA is apparently known as "Allison's Algorithm" online, although neither my references nor those I could find online lead me to the actual person of that name: add al, 90h daa add al, 40h daa I believe it faded into obscurity once the shorter 5-byte sequence using DAS instead was discovered: cmp al, 0ah sbb al, 69h das
- kens 4y ago
  The algorithm was published by Dennis Allison in "A design philosophy for microcomputer architectures", Computer (Volume: 10, Issue: 2, February 1977), https://doi.org/10.1109/C-M.1977.217645 https://doi.org/10.1109/C-M.1977.217645 Curiously, the article discusses design goals for microcomputers at a high level. The hex to ASCII algorithm was a random example of the gap between compilers and machine code. Allison had done a bunch of work with Knuth on decimal arithmetic, so he probably had this example at his fingertips.
- Sniffnoy 4y ago
  Note that in Allison's Algorithm, that second ADD should actually be an ADC. (I say this both because that's what's in the original paper and because checking it myself that's what works -- it's needed to add the 1 for A through F, so you don't get @ through E instead. Didn't check the second one.)
  - Sniffnoy 4y ago
    (Checking the second one, it's correct as written.)
monocasa 4y ago
> RISC processors, with their reduced instruction sets, cast aside less-important instructions such as decimal arithmetic Interestingly, the John Mashey at MIPS defended the use of BCD instructions in what I think is PA-RISC (which does have a DCOR - Decimal Correct instruction). That's because they looked at their instruction traces, saw lots of use of BCD arithmetic as the processor was targeting COBOL among other languages, and implemented that hardware support as single cycle register to register ops, and kept the overall arch of a normal RISC. That sort of diffusion test where you actually go look at instruction traces to come up with single cycle accelerators for your expected use case, but architecturally don't comingle your load store pathway with your ALU ops is sort of the heart of RISC. HP simply had different goals for their RISC chip than MIPS. https://yarchive.net/comp/bcd_instructions.html https://yarchive.net/comp/bcd_instructions.html That argument still pops up, for instance the "javascript instruction" in ARM. There's a lot about ARM that isn't pure RISC, but I argue that instruction is. They looked at instruction traces and found a single cycle (dispatch at least, it might be pipelined) ALU op that could accelerate the workloads that were important to them. In this case converting float to integer using x86 rounding modes rather than whatever modes are in the config register because Javascript expects x86 rounding which is different than default ARM rounding and switching back and forth is expensive. That instruction and the process used to come up with it are about as RISC as you can get, IMO. </semi_unrelated_rant>
- kps 4y ago
  One little line in there — “Machines are faster now, and the British use boring decimal currency like everyone else”. There were once machines with support for LSD mixed-base arithmetic (10, …, 10, 20, 12) in hardware and languages.
  - KMag 4y ago
    ... and most stock markets are also decimalized now. I remember reading the newspaper for my 7th grade investment club run by my math teacher. Prices were in 1/8ths of a dollar, as I remember, and maybe the penny stocks were in 1/6ths. In an alternate universe where the IEEE-754r decimal formats were in the original IEEE-754 spec, presumably most of these decimal integer operations would be performed in the FPU. If they're common enough, a handful of specialized fast-path instructions could be implemented for cases where it's known a priori that the exponents of the arguments match. Though, as sad is it is that we still use gallons in the US, it is handy that all of the subdivisions of a gallon down to the ounce are powers of two. Alternatively, the Babylonians were more advanced than we generally give them credit, as their base-60 number system isn't intuitive, and yet has lots of small factors for handy fractions. Any fraction storable in a finite number of digits in base-2, base-10, or base-12 (including any integer power of 1/3) is storable in a finite number of digits in base-60. So, a base-60 calculation would result in fewer display issues due to rounding for common calculations in people's everyday lives. Storing one base-60 digit in 6 bits isn't terribly wasteful, though more wasteful than storing 3 base-10 digits in 10 bits.
zvrba 4y ago
Since DAA generates #UB in 64-bit mode, I assume all such "adjust" instructions do (haven't bothered to check). In that case, is the auxiliary flag (AF) in the flags register used for anything at all in 64-bit mode?
- kens 4y ago
  Yes, the other adjust instructions are invalid in 64-bit mode. The Auxiliary Flag can get set in 64-bit mode, but I don't think anything uses it. You could access it through the EFLAGS register but I think it's otherwise useless.
- userbinator 4y ago
  One of the most puzzling things about 64-bit mode. There's no reason why they wouldn't work, and they didn't find anything else to reuse those valuable 1-byte opcodes for either.
  - ajross 4y ago
    This is true for a lot of historical cruft (c.f. segment registers wired to zero in 64 bit mode, likewise there's no reason that calculation shouldn't work since you have to have it present in 32 bit protected mode anyway). Presumably AMD wanted to specify only the future-useful subset of the architecture to be usable in long mode so that in the future when people started shipping long mode only CPUs[1] they wouldn't have to bother with the junk. [1] Which never happened, presumably because the transistor overhead of supporting real and 32 bit mode on the monster cores of the modern world was negligible. But you could totally ship a successful processor today that booted in long mode and lacked the ability to transition to real mode.
    - userbinator 4y ago
      64-bit mode could've just been an extension of regular protected mode, using double-wide descriptors of the reserved types that may even have been reserved for that purpose. That would've been the ultimate in backwards compatibility and a logical step. But you could totally ship a successful processor today that booted in long mode and lacked the ability to transition to real mode I don't think so. I certainly wouldn't want one, and neither would a lot of other people. Intel learned that lesson twice --- once with the 80376, and again when it started making x86 smartphone SoCs. No one really wants x86 without the rest of the PC architecture, since then they might as well use something like ARM or even RISC-V instead.
larusso 4y ago
I honestly had no idea what this instruction is just by reading the title. While reading I had the „aha“ moment of: „wait a minute that sounds like decimal mode on the 6502“. I had to wrap my had around this once I tried to write an emulator for it (I didn’t end the project but I wasn‘t far off). I wondered about the use-cases but was too far down the well on how to implement it correctly to check for the history. Interesting to know that Intel etc had to keep a two step solution unlike the 6502 with its decimal mode flag. The posts example code makes more sense then the 6502 docs did back then. But it could also be cause I have an understanding about the problem it solves. Decimal mode didn’t click for me in the beginning because my brain tried to overcomplicate the idea of decimal mode :)
- cesaref 4y ago
  Back in the 80s, writing 6502 with some other peeps one of the fun windups was when someone was away from their desk was to slip a SED instruction into their source in an obscure function that wasn't called that often. If you get it right, they spend quite some time trying to track down why their code is misbehaving. A bit of misdirection (e.g 'oh, that target machine was giving problems yesterday, maybe the hardware is failing') can really help :)
  - larusso 4y ago
    That is pure evil. I like it :)
Animats 4y ago
x86 is descended from the Intel 4004, which was for desk calculators. That's why it has explicit decimal math hardware.
- kens 4y ago
  No. It's often believed that the 8008 came from the 4004, but they have completely different architectures. They are essentially unrelated except many of the same people worked on both. The 8008 came from the Datapoint 2200, a desktop computer built from a board of TTL chips. Datapoint asked Intel and Texas Instruments if they could replace this TTL processor with a single chip. Texas Instruments created the TMX 1795, the first 8-bit microprocessor. Intel created the 8008 shortly after. Both chips copied the instruction set and architecture of the 2200. Datapoint didn't like either chip and stuck with TTL. Texas Instruments couldn't find a customer for the TMX 1795 and abandoned it. Intel, on the other hand, marketed the 8008 as a general-purpose microprocessor, essentially creating the microprocessor industry. The 8008 was cleaned up to create the popular 8080. Intel started the iAPX 432 as their flagship "micromainframe" processor, but it was extremely ambitious and fell behind the schedule. Intel created a stopgap 16-bit processor so they'd have something to sell until the iAPX 432 was ready: this was the 8086. They designed the 8086 to be able to run 8080 assembly after translation, so it inherited a lot from the 8080. As for the iAPX 432, it was late, a failure, and is mostly forgotten. The point of this is that the x86 is descended from the Datapoint 2200 and has no connection to the Intel 4004.
  - Animats 4y ago
    You're right. I should have known that, because I know about the Datapoint 2200.
Sniffnoy 4y ago
Hm, so the post mentions two approaches to BCD addition -- using a DAA instruction, and using a decimal mode like the 6502. It's funny because neither of these are what I would have thought of as the obvious way, namely, having an "add as BCD" instruction (equivalent to an ADD followed by a DAA, or on the 6502 to an ADD in decimal mode). Did any processors take that approach?
- kens 4y ago
  IBM System/360 (1964) had separate instructions for decimal arithmetic. The Z80 had a DAA instruction, but a separate status bit tracked if the previous operation was addition or subtraction.
- flohofwoe 4y ago
  I guess the reason is better composability and fewer wasted opcode "slots". E.g. arithmetic instructions output their result and status flags, and the DAA instruction takes that as input. Separate BCD instruction would require to duplicate all instructions that are "compatible" with DAA, and there might not have been enough room in the instruction set for those.
- tom_ 4y ago
  The 68000 has the ABCD instruction: http://68k.hax.com/ABCD http://68k.hax.com/ABCD (and SBCD, and NBCD) The ABCD -(An),-(An) form is presumably for big-endian multi-byte BCD values, as the X flag participates.
wheybags 4y ago
Part of me wonders if binary floating point was a mistake. If we had invested the same effort into hardware optimising some kind of BCD based floating point format, where would we be now? The amount of confusion caused for new programmers by the way floats can't represent "simple" values like 0.1 perfectly is immense. Would also make round tripping through text formats like json "just work", as opposed to the mess we have now.
- TazeTSchnitzel 4y ago
  The confusion around 0.1 might be a good thing, it makes you learn early on that floats approximate a number to its significant digits and are not real numbers.
  - wheybags 4y ago
    People are used to approximations, but they are used to decimal approximations. "I can't represent 1/3 as a decimal" is expected, "I can't represent 1/10 as a decimal" is surprising.
    - DerekL 4y ago
      Making computers use more memory, use larger chips, and consume more power just to make one thing easier for novice programmers is a bad trade-off. Decimal floating-point types could be implemented in software for those who really want it.
      - bcrl 4y ago
        By that reasoning we shouldn't be using higher level languages like Python and Java that use more memory, and consume more power for the same workload as code written in assembly. 6502 assembly FTW!
  - CamperBob2 4y ago
    Well, they are real numbers, just not always the ones you want.
guerrilla 4y ago
Keep going Ken! Thanks a million for all of this :)
pygy_ 4y ago
I wonder when Google is going to pull the plug on Blogger/Blogspot. I wouldn't feel safe about my posts having them hosted there...
segfaultbuserr 4y ago
On these early CPUs, conversion from binary to decimal could be very expensive. It required an integer division by 10, and the division must be done in software. Replacing it with shift-and-add calculations is not a solution, since fast bitshifts was only possible with a barrel shifter, which was also nonexistent on an early 8-bit CPU. If the integer is a fixed-width data type, say a 16-bit integer, a common algorithm was repeatedly subtracting 10000, 1000, 100, 10, etc., from the number. Not very efficient in terms of algorithm, but it can be implemented in a few lines of fast assembly. Still, if the number is frequently updated (perhaps a spreadsheet, or an on-screen score in a game), the fastest solution was storing it in BCD and avoiding the conversion. So native support of BCD arithmetic was not just a legacy due to desk calculators or compatibility, but also necessity. Earlier discrete logic circuits and calculators used BCD for the same reason. Conversion from BCD to readable formats like a 7-segment display or ASCII output was simple and only requires simple combinational logic. It's fortunate that computers are advanced enough today that we usually don't need to worry about the overhead of printf("%d", integer) anymore.
- awesomedad 4y ago
  Advanced enough, or are we brute forcing it?
  - segfaultbuserr 4y ago
    Excellent question. I'd say it's "advanced enough" in terms of semiconductor process node, "brute-force enough" in terms of circuit logic. A barrel shifter is definitely one of the most "brute-force" kind of logic circuits - you want to shift many bits in a word, but at the same time in a single cycle? Just use a large matrix to connect every possible input bits to every possible output bits. Early chips simply couldn't afford the die area on this non-essential but nice-to-have feature.
pcwalton 4y ago
I suspect that the most popular software using DAA that folks here have used would be emulators of old systems that had BCD mode, such as the SNES. For example, ZSNES uses it: https://github.com/xyproto/zsnes/blob/main/cpu/s65816d.inc#L253 https://github.com/xyproto/zsnes/blob/main/cpu/s65816d.inc#L...
advisedwang 4y ago
I enjoy the name "DAA" is clearly a play on "ADD", complete with incredibly contrived backronym

96 points by zdw 4y ago

kens 4y ago

Anyone have questions on the DAA instruction? This is a bit of a niche post, I have to admit.

jamesfinlayson 4y ago
If BCD is the only thing it's applicable for I don't think it has much use - I can't imagine any modern compilers generating BCD instructions nor any hand-rolled assembly making use of it these days. > Even Intel's x86 processors are moving away from the DAA instruction; it generates an invalid opcode exception in x86-64 mode. That's the first I've heard of that so I'm guessing no one complained.
- rvalles 4y ago
  I have used DAA recently, in my "load option ROM in RAM floppy tool"[0]. Specifically, I use it for printing numbers as hexadecimal[1], as unfortunately the ASCII standard is not arranged in a way as to facilitate this. 0. https://github.com/rvalles/optromloader/ https://github.com/rvalles/optromloader/ 1. https://github.com/rvalles/optromloader/blob/master/optromloader.asm#L182 https://github.com/rvalles/optromloader/blob/master/optromlo...
gfaure 4y ago
I only remember the DAA instruction because it was the last instruction I implemented in my Game Boy emulator. Since it's mainly used for end-user display of game scores, for most games it doesn't lead to any behaviour problems apart from messed up numeric strings, even if not implemented.
- MBCook 4y ago
  Ditto! I fished the CPU emulation on the emulator I’m writing around Christmas and I purposefully pushed DAA to the end of my instruction TODO list. It’s not that bad conceptually but in practice making sure all the flags are set right by the other instructions so DAA would work is a bit of a pain.
- dezgeg 4y ago
  Another GB emulator hobbyist here :) My dim recollection is that Pokemon uses BCD for in-game cash, so there you might be able to 'cheat' or either never buy anything if BCD stuff is left unimplemented :)
anticensor 4y ago
Can you make a post on the ASCII adjust series too? I would have expected both in a single blog post, though.
- kens 4y ago
  There's not a lot to say about the ASCII adjust instructions. I mention them in footnote 2. They are the same idea except they act on a single BCD digit. They aren't specifically for ASCII, but if you ignore the upper nybble, ASCII digit characters match the BCD values.
atq2119 4y ago
Since reverse engineering the 8086 is your thing, I was really hoping for this blog post to go into how the instruction is actually implemented. Is it all fixed function in the ALU? Is it micro-coded and if so, how?
- userbinator 4y ago
  Given that it's a 4-cycle instruction (and a reg-reg add is 3), it seems rather quick to be microcoded. (As an aside, Google gives absolutely horrible results if you search for "8086 DAA instruction timing". At least half the ones on the first page seem to be for the 8085, there's also this article itself and the discussion on HN, neither of which have the information.)
- kens 4y ago
  This article is sort of a prelude to looking at the 8086's hardware. (I was looking at the Intel documentation and realized it was confusing and slightly wrong, so needed to figure out what is really happening.) The 8086 implements the instruction in microcode, but like all the arithmetic operations, the interesting stuff happens in the ALU. In particular, the ALU hardware has a DAA instruction that figures out what correction value is needed and adjusts the flags appropriately. Another microcode instruction performs the addition. So the microcode is just four instructions long.

deleted 4y ago

[deleted]

tasty_freeze 4y ago

This instruction is lifted pretty directly from the 8080 behavior. One of they improvements the Z80 made over the 8080 was that DAA worked after either ADD or SUB, whereas the original DAA worked only for add.

userbinator 4y ago

More than one person noticed the addition of 6, and the significance that has to conversions between ASCII hex and binary, and came up with short (branchless) sequences for doing so using these and the other BCD instructions. This 6-byte sequence featuring DAA is apparently known as "Allison's Algorithm" online, although neither my references nor those I could find online lead me to the actual person of that name: add al, 90h daa add al, 40h daa I believe it faded into obscurity once the shorter 5-byte sequence using DAS instead was discovered: cmp al, 0ah sbb al, 69h das

kens 4y ago
The algorithm was published by Dennis Allison in "A design philosophy for microcomputer architectures", Computer (Volume: 10, Issue: 2, February 1977), https://doi.org/10.1109/C-M.1977.217645 https://doi.org/10.1109/C-M.1977.217645 Curiously, the article discusses design goals for microcomputers at a high level. The hex to ASCII algorithm was a random example of the gap between compilers and machine code. Allison had done a bunch of work with Knuth on decimal arithmetic, so he probably had this example at his fingertips.
Sniffnoy 4y ago
Note that in Allison's Algorithm, that second ADD should actually be an ADC. (I say this both because that's what's in the original paper and because checking it myself that's what works -- it's needed to add the 1 for A through F, so you don't get @ through E instead. Didn't check the second one.)
- Sniffnoy 4y ago
  (Checking the second one, it's correct as written.)

monocasa 4y ago

> RISC processors, with their reduced instruction sets, cast aside less-important instructions such as decimal arithmetic Interestingly, the John Mashey at MIPS defended the use of BCD instructions in what I think is PA-RISC (which does have a DCOR - Decimal Correct instruction). That's because they looked at their instruction traces, saw lots of use of BCD arithmetic as the processor was targeting COBOL among other languages, and implemented that hardware support as single cycle register to register ops, and kept the overall arch of a normal RISC. That sort of diffusion test where you actually go look at instruction traces to come up with single cycle accelerators for your expected use case, but architecturally don't comingle your load store pathway with your ALU ops is sort of the heart of RISC. HP simply had different goals for their RISC chip than MIPS. https://yarchive.net/comp/bcd_instructions.html https://yarchive.net/comp/bcd_instructions.html That argument still pops up, for instance the "javascript instruction" in ARM. There's a lot about ARM that isn't pure RISC, but I argue that instruction is. They looked at instruction traces and found a single cycle (dispatch at least, it might be pipelined) ALU op that could accelerate the workloads that were important to them. In this case converting float to integer using x86 rounding modes rather than whatever modes are in the config register because Javascript expects x86 rounding which is different than default ARM rounding and switching back and forth is expensive. That instruction and the process used to come up with it are about as RISC as you can get, IMO. </semi_unrelated_rant>

kps 4y ago
One little line in there — “Machines are faster now, and the British use boring decimal currency like everyone else”. There were once machines with support for LSD mixed-base arithmetic (10, …, 10, 20, 12) in hardware and languages.
- KMag 4y ago
  ... and most stock markets are also decimalized now. I remember reading the newspaper for my 7th grade investment club run by my math teacher. Prices were in 1/8ths of a dollar, as I remember, and maybe the penny stocks were in 1/6ths. In an alternate universe where the IEEE-754r decimal formats were in the original IEEE-754 spec, presumably most of these decimal integer operations would be performed in the FPU. If they're common enough, a handful of specialized fast-path instructions could be implemented for cases where it's known a priori that the exponents of the arguments match. Though, as sad is it is that we still use gallons in the US, it is handy that all of the subdivisions of a gallon down to the ounce are powers of two. Alternatively, the Babylonians were more advanced than we generally give them credit, as their base-60 number system isn't intuitive, and yet has lots of small factors for handy fractions. Any fraction storable in a finite number of digits in base-2, base-10, or base-12 (including any integer power of 1/3) is storable in a finite number of digits in base-60. So, a base-60 calculation would result in fewer display issues due to rounding for common calculations in people's everyday lives. Storing one base-60 digit in 6 bits isn't terribly wasteful, though more wasteful than storing 3 base-10 digits in 10 bits.

zvrba 4y ago

Since DAA generates #UB in 64-bit mode, I assume all such "adjust" instructions do (haven't bothered to check). In that case, is the auxiliary flag (AF) in the flags register used for anything at all in 64-bit mode?

kens 4y ago
Yes, the other adjust instructions are invalid in 64-bit mode. The Auxiliary Flag can get set in 64-bit mode, but I don't think anything uses it. You could access it through the EFLAGS register but I think it's otherwise useless.
userbinator 4y ago
One of the most puzzling things about 64-bit mode. There's no reason why they wouldn't work, and they didn't find anything else to reuse those valuable 1-byte opcodes for either.
- ajross 4y ago
  This is true for a lot of historical cruft (c.f. segment registers wired to zero in 64 bit mode, likewise there's no reason that calculation shouldn't work since you have to have it present in 32 bit protected mode anyway). Presumably AMD wanted to specify only the future-useful subset of the architecture to be usable in long mode so that in the future when people started shipping long mode only CPUs[1] they wouldn't have to bother with the junk. [1] Which never happened, presumably because the transistor overhead of supporting real and 32 bit mode on the monster cores of the modern world was negligible. But you could totally ship a successful processor today that booted in long mode and lacked the ability to transition to real mode.
  - userbinator 4y ago
    64-bit mode could've just been an extension of regular protected mode, using double-wide descriptors of the reserved types that may even have been reserved for that purpose. That would've been the ultimate in backwards compatibility and a logical step. But you could totally ship a successful processor today that booted in long mode and lacked the ability to transition to real mode I don't think so. I certainly wouldn't want one, and neither would a lot of other people. Intel learned that lesson twice --- once with the 80376, and again when it started making x86 smartphone SoCs. No one really wants x86 without the rest of the PC architecture, since then they might as well use something like ARM or even RISC-V instead.

larusso 4y ago

I honestly had no idea what this instruction is just by reading the title. While reading I had the „aha“ moment of: „wait a minute that sounds like decimal mode on the 6502“. I had to wrap my had around this once I tried to write an emulator for it (I didn’t end the project but I wasn‘t far off). I wondered about the use-cases but was too far down the well on how to implement it correctly to check for the history. Interesting to know that Intel etc had to keep a two step solution unlike the 6502 with its decimal mode flag. The posts example code makes more sense then the 6502 docs did back then. But it could also be cause I have an understanding about the problem it solves. Decimal mode didn’t click for me in the beginning because my brain tried to overcomplicate the idea of decimal mode :)

cesaref 4y ago
Back in the 80s, writing 6502 with some other peeps one of the fun windups was when someone was away from their desk was to slip a SED instruction into their source in an obscure function that wasn't called that often. If you get it right, they spend quite some time trying to track down why their code is misbehaving. A bit of misdirection (e.g 'oh, that target machine was giving problems yesterday, maybe the hardware is failing') can really help :)
- larusso 4y ago
  That is pure evil. I like it :)

Animats 4y ago

x86 is descended from the Intel 4004, which was for desk calculators. That's why it has explicit decimal math hardware.

kens 4y ago
No. It's often believed that the 8008 came from the 4004, but they have completely different architectures. They are essentially unrelated except many of the same people worked on both. The 8008 came from the Datapoint 2200, a desktop computer built from a board of TTL chips. Datapoint asked Intel and Texas Instruments if they could replace this TTL processor with a single chip. Texas Instruments created the TMX 1795, the first 8-bit microprocessor. Intel created the 8008 shortly after. Both chips copied the instruction set and architecture of the 2200. Datapoint didn't like either chip and stuck with TTL. Texas Instruments couldn't find a customer for the TMX 1795 and abandoned it. Intel, on the other hand, marketed the 8008 as a general-purpose microprocessor, essentially creating the microprocessor industry. The 8008 was cleaned up to create the popular 8080. Intel started the iAPX 432 as their flagship "micromainframe" processor, but it was extremely ambitious and fell behind the schedule. Intel created a stopgap 16-bit processor so they'd have something to sell until the iAPX 432 was ready: this was the 8086. They designed the 8086 to be able to run 8080 assembly after translation, so it inherited a lot from the 8080. As for the iAPX 432, it was late, a failure, and is mostly forgotten. The point of this is that the x86 is descended from the Datapoint 2200 and has no connection to the Intel 4004.
- Animats 4y ago
  You're right. I should have known that, because I know about the Datapoint 2200.

Sniffnoy 4y ago

Hm, so the post mentions two approaches to BCD addition -- using a DAA instruction, and using a decimal mode like the 6502. It's funny because neither of these are what I would have thought of as the obvious way, namely, having an "add as BCD" instruction (equivalent to an ADD followed by a DAA, or on the 6502 to an ADD in decimal mode). Did any processors take that approach?

kens 4y ago
IBM System/360 (1964) had separate instructions for decimal arithmetic. The Z80 had a DAA instruction, but a separate status bit tracked if the previous operation was addition or subtraction.
flohofwoe 4y ago
I guess the reason is better composability and fewer wasted opcode "slots". E.g. arithmetic instructions output their result and status flags, and the DAA instruction takes that as input. Separate BCD instruction would require to duplicate all instructions that are "compatible" with DAA, and there might not have been enough room in the instruction set for those.
tom_ 4y ago
The 68000 has the ABCD instruction: http://68k.hax.com/ABCD http://68k.hax.com/ABCD (and SBCD, and NBCD) The ABCD -(An),-(An) form is presumably for big-endian multi-byte BCD values, as the X flag participates.

wheybags 4y ago

Part of me wonders if binary floating point was a mistake. If we had invested the same effort into hardware optimising some kind of BCD based floating point format, where would we be now? The amount of confusion caused for new programmers by the way floats can't represent "simple" values like 0.1 perfectly is immense. Would also make round tripping through text formats like json "just work", as opposed to the mess we have now.

TazeTSchnitzel 4y ago
The confusion around 0.1 might be a good thing, it makes you learn early on that floats approximate a number to its significant digits and are not real numbers.
- wheybags 4y ago
  People are used to approximations, but they are used to decimal approximations. "I can't represent 1/3 as a decimal" is expected, "I can't represent 1/10 as a decimal" is surprising.
  - DerekL 4y ago
    Making computers use more memory, use larger chips, and consume more power just to make one thing easier for novice programmers is a bad trade-off. Decimal floating-point types could be implemented in software for those who really want it.
    - bcrl 4y ago
      By that reasoning we shouldn't be using higher level languages like Python and Java that use more memory, and consume more power for the same workload as code written in assembly. 6502 assembly FTW!
- CamperBob2 4y ago
  Well, they are real numbers, just not always the ones you want.

guerrilla 4y ago

Keep going Ken! Thanks a million for all of this :)

pygy_ 4y ago

I wonder when Google is going to pull the plug on Blogger/Blogspot. I wouldn't feel safe about my posts having them hosted there...

segfaultbuserr 4y ago

On these early CPUs, conversion from binary to decimal could be very expensive. It required an integer division by 10, and the division must be done in software. Replacing it with shift-and-add calculations is not a solution, since fast bitshifts was only possible with a barrel shifter, which was also nonexistent on an early 8-bit CPU. If the integer is a fixed-width data type, say a 16-bit integer, a common algorithm was repeatedly subtracting 10000, 1000, 100, 10, etc., from the number. Not very efficient in terms of algorithm, but it can be implemented in a few lines of fast assembly. Still, if the number is frequently updated (perhaps a spreadsheet, or an on-screen score in a game), the fastest solution was storing it in BCD and avoiding the conversion. So native support of BCD arithmetic was not just a legacy due to desk calculators or compatibility, but also necessity. Earlier discrete logic circuits and calculators used BCD for the same reason. Conversion from BCD to readable formats like a 7-segment display or ASCII output was simple and only requires simple combinational logic. It's fortunate that computers are advanced enough today that we usually don't need to worry about the overhead of printf("%d", integer) anymore.

awesomedad 4y ago
Advanced enough, or are we brute forcing it?
- segfaultbuserr 4y ago
  Excellent question. I'd say it's "advanced enough" in terms of semiconductor process node, "brute-force enough" in terms of circuit logic. A barrel shifter is definitely one of the most "brute-force" kind of logic circuits - you want to shift many bits in a word, but at the same time in a single cycle? Just use a large matrix to connect every possible input bits to every possible output bits. Early chips simply couldn't afford the die area on this non-essential but nice-to-have feature.

pcwalton 4y ago

I suspect that the most popular software using DAA that folks here have used would be emulators of old systems that had BCD mode, such as the SNES. For example, ZSNES uses it: https://github.com/xyproto/zsnes/blob/main/cpu/s65816d.inc#L253 https://github.com/xyproto/zsnes/blob/main/cpu/s65816d.inc#L...

advisedwang 4y ago

I enjoy the name "DAA" is clearly a play on "ADD", complete with incredibly contrived backronym