6502 BCD Multiplication

In preparation for the 6502-based calculator I am planning on building, I started thinking about the best way to do BCD multiplication. One of the reasons I was interested in working with the 6502 is its built in BCD mode. This works great for add and subtract but the chip does not have any sort of multiply or divide, BCD or otherwise. (Some of the 6800 family I was researching before do have hardware multiply, as does the 8051.) There are several routines that can make BCD multiplication faster, so I tried some of them on the 6502 to see which one works best.

To test these I used the Kowalski 6502 Simulator, which is neat because you can assemble in the simulator and then single step or run the program and see which line is being executed. Another convenient thing is that an input/output window is mapped into memory starting at at $E000. I also like the help window which automatically gives you information on op codes when you type them. On the other hand, the included macro system is extremely primitive and you can't do much with it, especially compared to the excellent macro system in CA65. It has a lot of other shortcomings and is fairly buggy, but I don't want to complain since it is free software. After I got frustrated at the lack of basic macro functionality, I tried assembling with CA65 and loading the binary into the simulator. The diassembler seems to work well but of course there is no way for the simulator to know label or function names. For these multiplication tests I decided to just make do with the simulator since I don't need much macro functionality. In the future, though, I will go back to using the 6502 trainer I made before.

To run the tests I made a loop that multiplies all combinations of BCD numbers $00 x $00 to $99 x $99. The Kowalski simulator has a function to count cycles, so I used that to find the time of an empty loop. For each test I recorded the cycles it took, subtracted the loop overhead time, and divided by 10,000 to get average cycles per calculation. After I was done, I went back and used look up tables for operations like shifting by 4 and halving numbers to speed things up a little. I also tried checking for 0 and 1 as arguments to skip the rest of the calculation, but this was not faster. In the table below, the table size column takes into account all the space the tables take up, including unused padding bytes inside the table. Here are the results in the order I did the tests:

	Method	Cycle average	Code size	Table size
1	Repeated additions	1,596.23	34	0
2	Repeated additions, minimize loops	1,236.66	48	0
3	Shift/add	284.80	67	0
4	4x8 lookup table	101.00	65	10k
5	4x8 lookup table, byte aligned	97.00	61	14.8k
6	Russian peasant algorithm	267.79	66	0
7	Quarter square table (half table)	115.33	85	816
8	Quarter square table (full table)	118.00	78	1,632
9	Quarter square table (BCD to bin to BCD)	86.00	51	1,816
10	Quarter square table (BCD to bin only)	60.00	34	792
11	Half squares	113.60	126	200
12	Simulated ROM lookup	31.00	20	46k

Descriptions of methods below:

6502 Address Decoding

For the 6502 graphing calculator I started working on two years ago I wanted to use an ATF1508 CPLD to do the address decoding. In another post, I wrote about how difficult it was to get this chip going. For one, the program I found to generate SVF files for it is 16-bit only. At the time I was running it in a virtual machine, but I don't have my Windows XP disk any more. If I keep using the homemade setup for it I had before, instead of buying a programmer (which is expensive), I think I might be able to run the program in a DOS emulator without Windows.

6502 address decoder with SRAM

Another way I was thinking about doing the decoding is with a 32k 12ns SRAM. For each address, the SRAM would act as a lookup table for the chip selects and other signals that the CPLD normaly does. This would not be as fast as the 7.5ns of the ATF1508, but it would still be very fast. One way would be to hold the 6502 in reset and cycle a counter through all 16-bits of the address space copying information from an EEPROM to the SRAM. After a certain amount of time, a timer would fire to disable that EEPROM and the counter and enable the SRAM, EEPROM, and 6502 of the main system. I'm not sure I got all of the signals exactly right but I made this schematic to illustrate approximately what I was thinking. The disadvantages of this setup is that the extra SRAM consumes 160ma, which would be a lot for the battery-based calculator I want to build, and the extra space the counters and second EEPROM would take.



Another way I thought about was disabling the main SRAM on startup but directing all reads to the EEPROM and all writes to the address decoding SRAM. This would let me write the whole lookup table into that SRAM with the 6502 . A transparent buffer would separate that SRAM from the data bus and prevent it from being written to further after a timer fires. If I got everything right, this would require more glue logic, but it would get rid of the counters and extra EEPROM of the last design.

A third way I thought of is to skip writing the memory decoder SRAM and use an EEPROM. Unfortunately, that would need 45ns or so to do the decoding, which is a lot slower than a CPLD. One alternative I found is 8k 25ns NVRAM, which stores its value permanently in an EEPROM but loads its content into SRAM when it turns on. This would give me 8 byte resolution, so I would probably lose less than 200 bytes of address space for peripherals. Also, if I drive the SPI clock with the NVRAM then I could set it low for one 8 byte stretch and fill that stretch with NOP instructions. Then to pull the clock low for a given number of cycles, I would just have to jump to the corresponding NOP in that stretch of memory.

On the 6502 forum I found a really great page on 6502 bus timing. If I understand the timing correctly, the 6502 needs up to 30ns to output its address and then the address decoding logic can go to work (either 12 or 25ns in this case). After that, the 74HC670 I have in the diagram will need 16ns up to nearly 40ns in the worst case to drive the high bits of the 512k SRAM. If I can get away with only two windows into the SRAM then it would only be about 6ns max if I replace the 74HC670 with a buffer and 74AS244. In order to avoid accidentally writing to wrong addresses, those delays will have to propagate before the clock goes high and the glue logic brings the WE\ of the SRAM low. This would allow me to run between 5 and 10MHz, depending on the combination. This is a lot less than the 14 MHz maximum the W65C02 I am using is rated for but it might work until I get the kinks out of working with the ATF1508.

6800 Family Tree

After about two years away from electronics, I have some time for my projects now that I am almost finished with my degree. Lately, I've been thinking about a lot of things and I want to start some new calculator projects and pick up where I left off on some other projects. One thing I have been thinking about is working on a simpler 6502 based calculator than I was working on before to get more experience working with the chip. I think the 6502 graphing calculator I was working on did not turn out very well because I rushed through everything too fast trying to get ready for Makevention in 2015.

Along those lines I recently got curious about other chips I could use to make a calculator. The last time I was curious about that I compared some of the microcontrollers I was interested in to see how fast they compute. One of my plans now is to do some other comparisons, which I think will be more useful. This time I want to compare processors like the 6502 as well, so I looked at other chips that would be fun to use. One group that I have been interested in for a while is the 6800 family like the 6809 and 6309. I could not find a family tree on the internet, so I started making one myself. When I was almost done, I found this tree in a document about the 6804:

Makevention 2015

Makevention went really well! I was able to show everything I have been working on, although I didn't have time to finish everything. I made a poster board explaining some concepts related to calculators like RPN, BCD, and CORDIC on the left side with information about my RPN Scientific Calculator on the right. I also had a print out of how my external RAM preprocessor works. A few of the people who came by my table were programmers and understood the solution.

On the table itself I had different calculators and projects laid out in roughly chronological order. The first was an MK-61 RPN calculator I added to my collection over 10 years ago. Of course I didn't make it but I wanted to show an example of an RPN calculator and what inspired me to first make calculators. When I first got the calculator out to test it, it didn't show anything on the screen and I was afraid it was broken. I took it completely apart and looked for burst capacitors. I also brushed off the battery contacts since they didn't look very clean. When I turned it on, it still didn't show anything but when I pressed a number it showed up! It seems the calculator just doesn't display anything when first turned on, instead of the zero I was expecting. Somehow I had forgotten that in the 10 years its been since I last used it.

The Casio Algebra FX 2.0 was included to show the RPN stack program I wrote for it in 2002 or so. That program was designed to make the calculator function more like the HP-48GX I had at the time which I admired so much. First, I had to buy a calculator to replace the Algebra FX 2.0+ I sold in college. Loading the program onto the calculator took quite a while to figure out! In 2002 I used a serial cable, which I think was an SB-87, to load programs without any trouble. Nowadays I don't have a serial port, so I bought an FA-124 USB cable. It turns out that this cable doesn't work on Windows 7. I also couldn't get it to work correctly under Windows XP running in an emulator. Next I tried a lot of different third-party software and finally got the program to load using FlashCOM 1.4v and an FTDI cable. For the link port I bought a 2.5mm plug that I could easily wire to the FTDI cable. After that, the program I loaded kept crashing and I thought the transfer was corrupt. After more fiddling I got Turbo C up and running in an emulator and compiled the program source myself, which produced a fairly stable program that was good enough for exhibiting, although it did crash a couple times during Makevention. Someday I would like to fix the program up and make it more stable.

The next thing I showed was a launchpad hooked up to a breadboard with a button and blinking LED to show how easy it is to get started with electronics. The next step was my binary LED calculator. I soldered a coin battery holder on to the board. After that I showed the RPN Scientific Calculator and explained that it was not too difficult to move to this stage after I managed to finish the binary LED calculator. The Programmable RPN Scientific Calculator was next. I printed temporary a colored keypad on poster paper which I taped to it, but it did not work very well. Unexpectedly, the calculator showed random keypresses when I put my hand near it. All the keys were in the same column on the keyboard, which makes me thing there is a bad connection in that row of the key matrix.

Next I showed the Improved 6502 Virtual Trainer up and running on my laptop, along with the first 6502 Virtual Trainer. I also showed what I had accomplished with the 6502 graphing calculator. So far, I have most of the hardware for it installed but I am having problems keeping the buffer chips for driving the LCD at the appropriate voltage level. Maybe the pins joining the sections of the calculator together aren't making a good connection. In any case, I showed the calculator taken apart into its sections. I also showed the Logic Tool I have been using to debug the graphing calculator and the EEPROM programmer I built. The last thing I showed was the TI-86 I bought to hook up to an ESP8266. My plan was to relay text from the calculator over WiFi to a computer running Matlab or similar software to allow the calculator to solve more complex equations. I still haven't gotten the ESP8266 voltage levels to work right, but I want to finish this project when I have time.

All in all it was a great day and I really enjoyed showing the public all the things I have been working
on.

Summer Hackathon: Conclusion

The Summer Hackathon I started on in May came to an end in August when I displayed a lot of what I had been working on at Makevention. I finished some projects and abandoned some others. Here is the outcome of the projects I set out to work on.

EEPROM Computer	Progress:	Abandoned
As I mentioned in the last update, a 4-bit version of this kind of computer has already been made by someone else. In the future I may make a 32-bit version, but for the time being I am done working on this.

8-bit Homebrew Computer	Progress:	20%
For this project, I designed a lot of the opcodes and most of how I want the computer to work. The chips I want to use don't seem to be simulated anywhere, so I will have to breadboard everything to test it out. So far I have one chip working just to test how it works.

Brainfuck Microcontroller	Progress:	55%
Apart from a few counters and status LEDs on a breadboard, I started soldering some boards with double row headers to hold everything.

Juggalo Robot	Progress:	70%
During the summer I didn't make much real progress on this project. I spent most of my time working on projects for Makevention instead.

ESP8266	Progress:	50%
I got an ESP8266 up and running. At first I had problems with the power supply but the chip seems to run alright with those problems solved. It also lists and connects to networks. Next, I need to connect to a server and transfer data, which will be used for a calculator project.

Wireless Breadboard	Progress:	Failed
This project was a failure. First of all I made a mistake with the spacing of the headers and it wouldn't fit the breadboard I was using. When I was working with it later I broke the entire header in half. The project wouldn't work anyway because the breadboard drops so much voltage. Unless I can find a breadboard that is much better, I don't intend to work on this project.

ATF1508 CPLD	Progress:	Done
After a lot of trouble and replacing a bricked chip, I eventually found a way to reliably program this chip. I also soldered a board to use for testing. This should be everything I need for the project I will use it in.

BASIC Interpreter	Progress:	30%
I also didn't make any progress on this project either. It would have been used with the Wireless Breadboard project if I had finished it. I will keep it for a later project I might need BASIC for.

LCD Programming	Progress:	50%
I got an LCD working for the 6502 Graphing Calculator project, as well as a VFD (technically not an LCD) for the Improved RPN Calculator. I did not get the LCD on the STM32F429 Discovery board working because I didn't need it for the Improved 6502 Trainer. I also haven't gotten the monochrome 5.5 inch LCD that requires -27v working yet. It will probably be easier to get a color LCD of that size instead.

Improved 6502 Trainer	Progress:	Done
I finished just about everything I wanted to for this project. It is much faster than the first 6502 Trainer. I will use it to develop for the 6502 Graphing Calculator.

Improved RPN Calculator	Progress:	95%
I finished almost everything for this project except a permanent keypad. I also renamed the project "Programmable RPN Calculator." The keystroke programming can repeat keystrokes, but it can't do any testing or branching. I will add those features eventually, but not in this version of the hardware. I shrank the size of numbers from 255 bytes down to 140. This lets me store all the temporary registers used during calculations on the chip, which makes calculations about five times faster. When I make a keypad I will be finished.

RPN Scientific Calculator on Hackaday

In August my RPN Scientific Calculator was featured on Hackaday in Hacklet 70 - Calculator Projects. It was really great to see my project on Hackaday! There was also a small scientific calculator running a 6502 emulator, a KIM-1 replica with a calculator form factor, and a project called CalcHack that adds functionality to TI graphing calculators. CalcHack is an awesome idea and one thing it adds is a 2.4GHz radio. One of my ideas for Makevention was adding an ESP8266 to the inside of a TI-86, but this solution is much better! Hackaday also created a page for calculator projects where I added my RPN Scientific Calculator, Improved RPN Scientific Calculator, and 6502 Graphing Calculator.

Progress Update

The past few months I have not had enough time to update this blog because I had so much to do in school this semester. My laptop also stopped working properly and I haven't had time to fix it, so I have not done anything with my projects. The only thing I have done related to programming is a few problems on Project Euler, which I recommend to anyone who enjoys programming. In August, a lot of things happened leading up to Makevention. Now that I have some time during the holidays, I am going to try to catch up on some posts. Hopefully I will have more time this semester to work on projects.