The x86's Decimal Adjust after Addition (DAA) instruction | Hacker News Reader

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

righto.com

96 pointszdw63 comments

> 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

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>

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.

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

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

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

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.

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

(Checking the second one, it's correct as written.)

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.

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.

Advanced enough, or are we brute forcing it?

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.

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

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

That is pure evil. I like it :)

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#L...

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?

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.

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.

The 68000 has the ABCD instruction: 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.

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

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.

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/

1. https://github.com/rvalles/optromloader/blob/master/optromlo...

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.

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.

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

Can you make a post on the ASCII adjust series too? I would have expected both in a single blog post, though.

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.

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?

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

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.

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?

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.

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.

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.

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.

Out of curiosity:

1. What software would you want to run that used 286-style segmentation in a 64 bit space? That model had been abandoned long before AMD wrote the x86_64 spec.

2. What 386 protected mode (or unreal mode too, I guess) software are you needing to run such that you wouldn't buy a 64-bit-only CPU? Again, this has been entirely abandoned (with the sole exception of the SMP boot mechanism, which is defined to start in real mode) on modern systems, even at the firmware level.

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.

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.

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.

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.

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!

Well, they are real numbers, just not always the ones you want.

But we also have, e.g., fairly accurate weather models now, enabled by supercomputers running lots of floating point math.

Wouldn't we have the same if history tilted the way the grandparent post is asking about?

If only humans had 8 or 16 fingers instead of 10 ;)

This reminds me of this: https://news.ycombinator.com/item?id=12719273#12720638

> Fun fact: you can count to hexadecimal on the fingers of one hand.

> The way it works is that each of your four fingers has four well-defined places on them: the three joints, plus the tip. You use your thumb to point at one of these. The first finger represents 1-4, the second 5-8, the third 9-12, the fourth 13-16. You count up and down by moving your thumb.

(...)

> As a special bonus: if you point to the fleshy pads of the fingers instead of the joints, you can use the same system for base 12.

Tough call deciding between this and just using your fingers as a 5 bit binary counter. Incrementing is sure a lot faster with this method at the cost of a bit.

The difficulty with that is that your ring finger is not completely independent of your pinkie due to the way the tendons are connected.

Floats represent real numbers, not "values". (Whatever those are.)

Please teach new programmers the number type stack first.

How do they represent real numbers? If anything, they represent rational numbers.

Also I think your answer is unnecessarily nitpicky. Sentence 'floats can't represent "simple" values like 0.1 (...)' is perfectly clear to everyone on HN, I hope. In fact, I disagree that changing "values" here to a more precise mathematical term would improve anything.

> How do they represent real numbers? If anything, they represent rational numbers.

That's an interesting philosophical question. Does M_PI represent a rational number?

(M_PI isn't mentioned in my copy of the C spec, unless I just can't find it.)

does it not have to represent a rational approximation of Pi? Real numbers in the set theoretic sense are defined as limits of Cauchy sequences[0], and since we can't quite store an infinite sequence, it has to be a finite approximation due to the limitations of the real world.

[0]: https://en.wikipedia.org/wiki/Cauchy_sequence

It does after it's assigned to a variable, but maybe it doesn't before that.

Rationals are a subset of the reals.

No current computing architecture provides primitives for dealing for rational numbers. (Which is why you need to roll your own implementation in software, so nobody bothers.)

But we have great native support for approximating real numbers instead. (Because computing is designed first and foremost to make numerical methods efficient.)

Floats are designed to be computationally and mathematically efficient approximations of the real numbers.

The exist so that trigonometry and logarithms work properly in numerical methods. (A vastly more important problem than getting '0.1' to print pretty on the screen.)

There is no such thing as a 'value' in mathematics, and fixating on 0.1 in particular is pointless.

tldr - everyone should learn the math behind this first.

Responses to this are IMHO unfair. In fact this isn't an inherently terrible or infeasible idea. Transistor costs for 4-bit BCD run just about at the ln(16)/ln(10) level you'd expect, and just a few gates of depth per digit are needed for the carry detect (something that can easily be folded into the carry lookahead optimizations all modern adders need anyway). Hardware multipliers would need more work, you can't make a Dadda/Wallace tree with anything but binary adders, but I'm sure there's a clever generalization.

The one thing you'd lose would be two's complement trickery. Addition and subtraction in BCD actually are fundamentally different algorithms, so that's something to worry about. But then signedness mismatches are themselves a historical footgun, so you could spin this away too, I think.

But... beyond that this could absolutely be done. And it's also true that a lot of traditional bugs with FPU/brain precision mismatch would be fixed in the process.

I don't know that it's an architecture I'd pick, but it's not something to reject out of hand either. It's worth discussing and not downvoting.

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

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

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

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.

You're right. I should have known that, because I know about the Datapoint 2200.

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

Reply on news.ycombinator.com