29 year old bug

[webdeck]

Here's a fun story.  Back in 1995, I attempted to write a TI emulator for a Mac.  I almost had the TMS9900 emulation working, but I kept running into weird issues that I couldn't track down.  My Mac back then wasn't powerful enough to run the emulation fast enough, so I gave up on it and moved on to other things...  But from time to time it would nag at me that I couldn't find that bug.

 

This week, I decided to pull out that code and try and find the problem.  Of course, Macs have changed so much that I couldn't even compile it any more because the IDE no longer exists and the frameworks I used have all stopped working.  So I decided to write it from scratch again, this time using Swift, so I could get up to speed on building a modern Mac app.  I tried to write it without referencing what I wrote before, so that I would have a clean start.  This time I focused on building tools to allow me to monitor everything that's going on internally as it is emulating, now that Macs are so much faster.  And this time around, I had the Cyc to refer to.

 

But sure enough, I get it to the point where I can emulate the keyboard and I see that it just keeps scanning one row over and over.  So then I looked at the Cyc's console rom source to see what's going on.  Hmm, it should be a loop that goes through all the rows, so why isn't it...

 

It does a DEC followed by a JOC.  That's not a pattern I remembered using.  I found the key buried in one sentence in the E/A Manual page for DEC: "The carry bit is always set except on transition from zero to minus one."  OMG - the carry bit is the opposite of what I thought!  So that was the bug it took me 29 years to finally find and fix.

[+khanivore]

17 minutes ago, webdeck said:

Here's a fun story.  Back in 1995, I attempted to write a TI emulator for a Mac.  I almost had the TMS9900 emulation working, but I kept running into weird issues that I couldn't track down.  My Mac back then wasn't powerful enough to run the emulation fast enough, so I gave up on it and moved on to other things...  But from time to time it would nag at me that I couldn't find that bug.

 

This week, I decided to pull out that code and try and find the problem.  Of course, Macs have changed so much that I couldn't even compile it any more because the IDE no longer exists and the frameworks I used have all stopped working.  So I decided to write it from scratch again, this time using Swift, so I could get up to speed on building a modern Mac app.  I tried to write it without referencing what I wrote before, so that I would have a clean start.  This time I focused on building tools to allow me to monitor everything that's going on internally as it is emulating, now that Macs are so much faster.  And this time around, I had the Cyc to refer to.

 

But sure enough, I get it to the point where I can emulate the keyboard and I see that it just keeps scanning one row over and over.  So then I looked at the Cyc's console rom source to see what's going on.  Hmm, it should be a loop that goes through all the rows, so why isn't it...

 

It does a DEC followed by a JOC.  That's not a pattern I remembered using.  I found the key buried in one sentence in the E/A Manual page for DEC: "The carry bit is always set except on transition from zero to minus one."  OMG - the carry bit is the opposite of what I thought!  So that was the bug it took me 29 years to finally find and fix.

Heh, I hit the exact same bug writing my emulator for Linux.  Took me weeks to figure out why it would only scan one row.

[+mizapf]

Yes, that's a tricky one which puzzled most of us. But it is easily explained when you keep in mind that DEC is an addition of >FFFF. And the carry bit is a flag of unsigned operations, so the only way to not set is to add FFFF to 0000, or to DEC from 0 to -1.

 

I had a similar experience in MAME when I learned that subtracting 0 from 0 also sets carry. This is because the subtraction is actually done via the one's complement and adding 1. Failing to do so led to the weird effect that almost everything works except for Microsurgeon where you got a Game Over in the moment when you started the game.

[matthew180]

9 hours ago, mizapf said:

Yes, that's a tricky one which puzzled most of us.

 

Without trying to sound pretentious (or be pretentious, as it were), implementing DEC was not puzzling to me when doing the F18A GPU.  Maybe it is just the mindset?  Most people writing emulators are probably doing so from a software perspective, so they implement software solutions that miss what actually happens in real hardware.  Most emulators I have looked at (briefly) are implementing what I call "simulation" rather than emulating what the hardware does.

 

For example, in a case like DEC Rx, there is temptation to have the register value in a variable, say "reg", and do something like: "reg--;"

 

You will get the decrement, but you will miss the nuance of what happened in hardware, and as most people eventually find out, those nuances and side-effects matter.

 

If you have a big switch in your emulator that performs each operation based on the opcode, then you are not doing hardware emulation, IMO.  Hardware does not work like that.

 

9 hours ago, mizapf said:

I had a similar experience in MAME when I learned that subtracting 0 from 0 also sets carry.

 

Yes, because the 9900 does not perform a pre-check (with a few exceptions) on the input values to operations.  The CPU will just perform the operation and set the flags accordingly.  It is the simplest way to do things in hardware.  When it comes to hardware, physical area and the number of transistors matters, and doing special things or making exceptions for certain opcodes is expensive in cost, area, complexity, and testing, so special cases are avoided if at all possible.

 

The 9900 has quite a few places where subtle things happen with instructions and flags, especially around the roll-over events, i.e. >FFFF to >0000, etc..

 

10 hours ago, mizapf said:

This is because the subtraction is actually done via the one's complement and adding 1.

 

I.e. "two's complement".  Standard stuff in pretty much all digital electronics since binary started being used in computers.

 

12 hours ago, webdeck said:

I found the key buried in one sentence in the E/A Manual page for DEC

 

If you are writing an emulator for the 9900, you really want to be looking at the TMS9900 Data Manual, especially pages 21-22 that define and describe how all the flags are set for all instructions.  The Data Manual is the primary source for truth for the 9900, forget the E/A manual (I never used it at all for the F18A GPU).

 

[+mizapf]

13 minutes ago, matthew180 said:

Without trying to sound pretentious (or be pretentious, as it were), implementing DEC was not puzzling to me when doing the F18A GPU.  Maybe it is just the mindset?  Most people writing emulators are probably doing so from a software perspective, so they implement software solutions that miss what actually happens in real hardware.  Most emulators I have looked at (briefly) are implementing what I call "simulation" rather than emulating what the hardware does.

 

There is generally a difference between writing software in C++ and programming an FPGA. If you want to put it like this, software on a typical single-threaded von Neumann machine can never really emulate hardware to that extent.

[matthew180]

Erm, the FPGA is middle ground between hardware and software, but you can still easily get it wrong in an FPGA.  Lots of HDL out there is written from a software perspective; sometimes it works, other times no so well.  Some of my HDL still suffers from a software centric approach as well.

 

3 minutes ago, mizapf said:

If you want to put it like this, software on a typical single-threaded von Neumann machine can never really emulate hardware to that extent.

 

I disagree.  Software emulators can get the digital operation to match the hardware, IMO.  It is just that most emulator writers are probably software people with a software relationship to the CPU.  I was certainly in that situation when I started working with FPGAs, and I had plenty of "holy shit" moments for sure.

 

A software developer sees a CPU as a device that executes instructions in a series of steps.  This is the software-model.  However, hardware is inherently parallel, so there is this strange relationship where a very internally parallel machine presents a completely serialized interface to itself.

 

Emulator writers have to get beneath the software surface and into how the CPU is performing the operations using digital circuits.  The CPU running the emulator is also doing the same thing as the CPU being emulated, which also makes for a strange relationship.  Assembly is probably the best language for writing an emulator since it gives you access to features of the CPU (like direct access to flags, etc.) that are not exposed in high-level languages like C.

 

Of course there are tradeoffs that need to be considered.  Emulation of how the hardware works, using software, means more code and it will be less performant than a simulator that is reproducing hardware "functionality" rather than "hardware emulation".  So, for older emulators running on previous generations of slower PC hardware over the years, where playing games and running software was the goal, simulation was needed.  These days, with multi-GHz CPUs, there is little reason to not have the emulators be more hardware centric (which makes them more accurate).

 

The Vistual6502 project takes this to the extreme with full transistor emulation.  While neat and educational, this does represent a situation of tradeoffs.  Maybe when we have 10GHz+ machines, or machines with hundreds of cores, our emulators can go down to the transistor level and still perform like physical hardware.

 

[webdeck]

11 hours ago, matthew180 said:

 

Most people writing emulators are probably doing so from a software perspective

 

Guilty as charged, since I am a software engineer and not a hardware engineer.  I am completely amazed at the amazing things hardware engineers can do, but it's not my skillset.

 

I took this up for two reasons: 1) to learn more about writing performant Swift applications, and 2) the fact that I had that bug and never figured it out gnawed at me.  I don't expect this to turn into anything that ever get shipped, and it will never match the depth of features that the existing emulators have taken on.  It's just a little fun project for me to learn on.

 

Quote

If you have a big switch in your emulator that performs each operation based on the opcode, then you are not doing hardware emulation, IMO.  Hardware does not work like that.

Fair point.  I am trying to follow the flow diagrams for machine cycles in Appendix A of the TMS9900 Family System Development Manual, as well as cross-referencing the TMS9900 Microprocessor Data Manual, along with the E/A manual and TI-99/4A Console Technical Data, as well as the awesome TI-99/4A Tech Pages.  I didn't have all of those resources back in the day.  I'm trying to count accurate clock cycles for instructions and memory accesses with wait states, etc.  But then macOS doesn't provide nanosecond level accuracy on sleep since it's not a realtime OS, so it winds up being approximate anyway.

 

But at the same time, I am trying to make the emulator be able to provide a lot more visibility into what is going on.  I'm intentionally being less efficient than I could be in how I'm approaching this.  When decoding an instruction, I'm actually parsing it out into a data structure first before executing it, allowing me to audit what is happening.  Swift is a language that enforces bounds checking and type safety at the expense of performance.  But again, this is for fun, so it's fine, and Swift allows me to easily connect up inspectors to visualize what's happening, once I figured out how to do that without completely tanking performance (I manually update them every 1/60 of a second when the emulator is running.)

Quote

If you are writing an emulator for the 9900, you really want to be looking at the TMS9900 Data Manual, especially pages 21-22 that define and describe how all the flags are set for all instructions.  The Data Manual is the primary source for truth for the 9900, forget the E/A manual (I never used it at all for the F18A GPU).

Maybe the Cyc version renumbers the pages, but it's pages 34 and 35 in the version I have, and I used those extensively.  Very helpful in explaining all of the status bits except for Carry.  It just has the sentence "If Carry out = 1" which I guess was too vague for me.  I still don't know what it means.  I understand what two's complement means in terms of how negative numbers are represented in binary, but I still don't get what "carry out" means.  I guess I'm missing something there.

 

 

Here's a short video of what I have so far.  I don't have the VDP rendering implemented yet, so it is just showing ASCII characters in a grid for now.

[apersson850]

6 hours ago, webdeck said:

...but I still don't get what "carry out" means.  I guess I'm missing something there.

It's perhaps easier to grasp if you think about it as a result too big to fit. When it is, you get a "carry over" that ends up in the carry bit.

If you limit yourself to data containers that can hold a single unsigned decimal digit, then you can add 2 and 5 without carry, since the result is 7 and 0 goes to the carry. But you can't add 3 and 7 correctly, since the result is 10. What you get is instead 0 and the 1 goes into the carry. If you add 9 and 9 you get 8 and 1 into the carry. If you add 9 and 1 you also get 0 and 1 into the carry.

 

When you subtract it's counter-intuitive, but that's because adding FFFF to anything will make it a bigger value than FFFF, so there's carry out. Only time it's not bigger than FFFF is if you add FFFF to zero. Now with 16 bits at our disposal, we can either have the range 0 to 65535 (unsigned) or -32768 to 32767. In the latter case, we say that 32767 is 7FFF and -32768 is 8000 in hexadecimal. Thus -1 is FFFF. So adding FFFF is the same as subtracting 1 by adding -1 with this representation. Since the carry out is defined in a way we think is logical when we don't look at the sign, you get the result I described above.

 

The "carry over" nomenclature comes from that if you want to do single digit arithmetic properly, then you add 8 and 6 and get the result 4, with a 1 in the carry. To complete the result you have to handle the next digit now. In the case of adding 08 and 06, the next digit is zero in both numbers, so the sum is zero. But you have a "carry over" of 1, which you must add as a "carry in", to the the correct result of 14.

If you add 28 and 46 on a single digit machine, you still get 4 with carry out when handling the rightmost digits. In the next addition you add the leftmost digits 2 and 4 plus the incoming carry, making the next digit 7. So the result is 74, which is correct.

But eventually you come to the max length of a number you can represent (at least in a CPU you do), and then you end up with a result that's not complete and a carry out, since it should really be bigger than can be represented.

 

In the TMS 9900 (and other binary CPUs), each digit is just 0 or 1, but the 9900 can couple 16 such bits in a row.

 

Some people confuse carry out with overflow. Sometimes they are the same, but not always, since the overflow is computed taking signed numbers into account. With the single digit machine above, an interpretation of 2's complement notation with a single decimal digit would imply that we look at numbers 0 to 4 as they are, but consider the numbers 5 to 9 represent -5 to -1.

 

Now if we add 9 and 1 we still get a carry, since what should have been 10 (unsigned) is only 0, and that carry. But there is no overflow, since then we consider the sign, and -1 added to 1 is just 0. No overflow there. Now on the other hand, if we compute 6 minus 3, there is no carry (the result is 3), but there is an overflow, since with sign you are asking for -4 minus 3. The result -7 is outside our range for signed numbers.

 

When building adders electronically, you can choose from simple ripple carry adders or carry look-ahead adders.

• In a ripple carry adder, each bit is added as A + B + incoming carry.
• Each addition produces an outgoing carry.
• The least significant bit always has incoming carry as zero.

The end result of this design is that you can't compute a correct result until all carry bits have propagated from the least to the most significant bit adder. But each adder is very simple.

 

The other alternative is a look-ahead design. There you handle carries and addition separately in parallel, so you get the full result in one fell swoop, but the complexity of the adder increases quite a lot.

Edited February 9 by apersson850

[+Vorticon]

Well, NOT being a software engineer (or engineer anything for that matter), I can't tell the difference between a Von Neumann machine and a banana. But I can relate to old bugs gnawing at your brain for decades until you solve them. Case in point: One of the first programs I wrote back in 1981 was a loose version of Pacman (of course, what else) in TI Basic as all I had was a console and a cheap tape recorder, and it ran sluggishly great until it eventually crashed for no apparent reason and I could not at the time figure it out for the life of me. So I tossed the handwritten listing in a drawer and forgot about it. Well not quite. As an undergraduate graduation present in 1986, my parents bought me an IBM PC clone and I never looked back, that is until the mid-90's when I got back into the TI scene out of nostalgia. From there on my knowledge of the TI system dramatically improved through a combination of self-teaching with books and the internet groups. Then in 2007 I launched the TI Gameshelf website and I remembered about my Pacman clone. Interestingly, out of the many programs I had written back in the 80's for the TI, it was the only listing that somehow survived. Weird how the subconscious mind works, eh? In any case, I decided to dive back into it and sure enough I discovered that I was jumping out of a subroutine instead of using RETURN in some special situations, which was eventually leading to a stack overflow and a crash! It may sound silly but the moment I figured it all out was akin to when Newton figured out the laws of gravity. Okaaay that's a tiny exaggeration but hey, it's my recall moment and I can do with it what I want! So there. You can find TI PUCK on the https://www.tigameshelf.net/tibasic.htm site if curious. Nothing to brag about, but it's of "historical value"... 😃

[+mizapf]

The interesting thing with our TMS9900 is that you can decide whether you are doing a signed or unsigned operation after you let it perform. Some platforms, like MIPS, have separate addu and add operations for unsigned and signed addition. With the TMS9900, there is only A. You decide at the point where you check the status flags (using some conditional jump, in particular).

 

So the flags are all appropriately set for both cases of signed and unsigned operations. When the operation is a signed one in our intuition, like DEC, the unsigned flags (JH, JOC) don't really make sense, or they act in a possibly surprising way. The same is true for overflow, which only makes sense for signed arithmetics, but is also set/reset for an operation where you actually intended to use unsigned integers.

 

The cool thing about 2s complement is that the signed addition is identical to the unsigned addition. If you add E000 to 1000, you get F000 unsigned. But also, if you interpret E000 as -2000 and F000 as -1000, this is also true.

 

@apersson850Where is overflow and carry the same? I mean, they are often mixed up, in particular when you take the example of E000 + 2000. You get 1000 as a result, with a carry, but people sometimes believe this was an overflow. In German, it's even a bit harder to get it into the students' brains, because carry is called Übertrag ("over-carry"), and overflow is Überlauf ("over-run").

[apersson850]

It's if you consider overflow from an unsigned point of view, which at least student tend to do now and then, then you can get carry and overflow at the same time.

 

But in the TMS 9900 perhaps never, since carry is from an unsigned point of view but overflow from a signed point of view. I haven't considered that in detail. Still, of course, people may mix them up anyway.

[matthew180]

11 hours ago, webdeck said:

Guilty as charged, since I am a software engineer and not a hardware engineer.  I am completely amazed at the amazing things hardware engineers can do, but it's not my skillset.

 

I'm not trying to charge anyone, so please try to read my responses as informational rather than accusatory.  I think most of us here started in the area of software, and some have ventured into the hardware part to various degrees.  However, to write an emulation of hardware, it would be beneficial to do a little venturing into the digital logic part of hardware, IMO.  Understanding the basics of digital circuits like adders and logic, and how computers operate on numbers internally will benefit your emulator greatly.

 

11 hours ago, webdeck said:

I didn't have all of those resources back in the day.

 

For sure!  All the information available today, and especially the ability to talk to people like those in this forum, is amazing!

 

11 hours ago, webdeck said:

It just has the sentence "If Carry out = 1" which I guess was too vague for me.  I still don't know what it means.  I understand what two's complement means in terms of how negative numbers are represented in binary, but I still don't get what "carry out" means.  I guess I'm missing something there.

 

When I find myself in a situation like that, it is my trigger that I need to do some learning.  As you mentioned before, the resources available to you are almost unlimited these days.  A quick Internet search will usually give you more than enough information to self learn the concepts.

 

In this case, carry-out means the last column of bits produced a carry as a result of the addition.  When a computer is out of bit positions (because computers are finite), there are flags that get set so you, the programmer, are aware of any circumstances related to the operation.

 

https://en.wikipedia.org/wiki/Overflow_flag

 

" ... When binary values are interpreted as unsigned numbers, the overflow flag is meaningless and normally ignored. ..."

 

Basically, carry is used when numbers are treated as unsigned, and overflow is used when numbers are treated as signed.  The difference is entirely up to you, the programmer, and what the data represents.  Golden rule of computer software: "know your data!"

 

12 hours ago, mizapf said:

The interesting thing with our TMS9900 is that you can decide whether you are doing a signed or unsigned operation after you let it perform.

 

This is true for pretty much every VLSI CPU since the mid 70s.  The same WikiPedia page above mentions this as well:

 

"... For this reason, most computer instruction sets do not distinguish between signed and unsigned operands, generating both (signed) overflow and (unsigned) carry flags on every operation, and leaving it to following instructions to pay attention to whichever one is of interest. ..."

 

12 hours ago, mizapf said:

Some platforms, like MIPS, have separate addu and add operations for unsigned and signed addition.

 

Actually, this was just poor choice of instruction naming; the addition is performed the same.  The difference is whether the programmer wants a trap to be generated:

 

https://stackoverflow.com/questions/16634110/difference-between-add-and-addu

 

"The instruction names are misleading. Use addu for both signed and unsigned operands, if you do not want a trap on overflow.

Use add if you need a trap on overflow for some reason. Most languages do not want a trap on signed overflow, so add is rarely useful."

 

[apersson850]

9 hours ago, matthew180 said:

Basically, carry is used when numbers are treated as unsigned, and overflow is used when numbers are treated as signed.

Read that again, it's the most important thing to understand. When you run out of bits in a CPU and thus have a spillover, that residue causes a carry out for unsigned or an overflow for signed numbers. Which is why many get confused to begin with, since with unsigned numbers, carry out = 1 indicates an overflow condition as long as we look at the numbers from an unsigned point of view.

 

From the point of view of the TMS 9900, carry is only valid when you use unsigned numbers and overflow when they are signed.

What also sometimes takes some time to grasp is that the rules for binary addition are the same, regardless of if you want the numbers to be signed or unsigned.

[Asmusr]

43 minutes ago, apersson850 said:

Read that again, it's the most important thing to understand. When you run out of bits in a CPU and thus have a spillover, that residue causes a carry out for unsigned or an overflow for signed numbers. Which is why many get confused to begin with, since with unsigned numbers, carry out = 1 indicates an overflow condition as long as we look at the numbers from an unsigned point of view.

I never really understood that before, perhaps because I never needed to add large signed numbers. But it makes a lot of sense.

[matthew180]

6 hours ago, Asmusr said:

I never really understood that before, perhaps because I never needed to add large signed numbers. But it makes a lot of sense.

 

I suspect you have and maybe just did not think about it in this way.  In the case of the retro computers we mess around with we have 8-bit bytes and 16-bit words, so it is easy run out of bits pretty quickly.

 

Any time you let a register "roll over" intentionally (increment or decrement), you are in a situation where you might need to consider the carry or overflow flag.  It can matter a lot with shift instructions as well.

 

Whenever you use any kind of conditional jump instruction, you are having to consider the size of the result value from the previously executed instruction.

[apersson850]

The carry is of course also used to implement double precision arithmetic. If you want to do 32 bit addition, with two values A and B to get the sum in C, split in High and Low words, you add AH and BH to CH, then AL and BL to CL. Now, if you got a carry out of here, you increment CH by one (carry in).

[+FarmerPotato]

On 2/9/2024 at 4:45 AM, apersson850 said:

When building adders electronically, you can choose from simple ripple carry adders or carry look-ahead adders.

• In a ripple carry adder, each bit is added as A + B + incoming carry.
• Each addition produces an outgoing carry.
• The least significant bit always has incoming carry as zero.

The end result of this design is that you can't compute a correct result until all carry bits have propagated from the least to the most significant bit adder. But each adder is very simple.

 

The other alternative is a look-ahead design. There you handle carries and addition separately in parallel, so you get the full result in one fell swoop, but the complexity of the adder increases quite a lot.

 

For those who want to see some silicon, try The Z-80 has a 4-bit ALU.  It has four 1-bit "slices".  Each slice has a Carry In and Carry Out.  Making it a ripple-cary adder. It also does Boolean functions and shifts.

 

Surprise, the Z-80 makes two passes through the 4-bit ALU to compute an 8-bit result. 

 

Reverse engineered by Ken Shirriff, and drawn in logic diagram.  Acknowledgements to Visual 6502 team who supplied the photo: Chris Smith, Ed Spittles, Pavel Zima, Phil Mainwaring, and Julien Oster.  The folks doing this are amazing.  Back when, this was a valuable skill.

 

 

[apersson850]

That was an interesting article. While at university (Lund Institute of Technology in Sweden) I learned to design CPUs built by AMD's then rather new Am2900 chip series. With a couple of ALU and sequencer modules, you could build yourself a processor of any size in 4-bit increments. Did quite a lot of microprogramming with these things.

Among these parts there is ripple carry between the ALU chips but also a carry look-ahead chip. There were many different chips in that serie, but these I remember specifically.

Edited February 11 by apersson850

[Artoj]

Wow, what a enlightening thread!! Thanks for all the insights! I have to reply now, I have been hunkering down on my Ternary hardware sections, Sum, Carry, Any, Half Adders and finally a Full Adder giving me a 3 Trit Addition, to add to my list of Instructions I want to implement. I am currently bashing a diamond nail into the Ternary Multiply circuit, whew it is a hard cracker!, as there is no manual of 'how to' book. I will eventually make the process as transparent and easy to understand. I learned so much from looking at the Bit Sliced version of a 9900 implementation that uses 4x74S481 and a 74S182. So I figured if you want to emulate hardware, make the software look and act like the hardware. So I created a spread sheet that does just that, it could be instructive to even build a small 4 bit binary CPU doing just that. Regards Arto.

 

Here is the bit sliced version of a 9900. Also one of my software versions of a Ternary Full Adder.

Edited March 2 by Artoj

[+DuaneAL]

On 2/9/2024 at 8:05 AM, Vorticon said:

I can't tell the difference between a Von Neumann machine and a banana.

The banana is yellow, other than that they are exactly the same.🙂