6507 Graphing Calculator: Update

After a few months of progress, a demo version of this project is on my website. You can try out all the functionality of the calculator in your browser since it runs on my 6502 emulator. Below are some updates since the last post.

Software The functionality of the calculator is close to complete. The Forth system is basically done and supports these new structures: IF/ELSE/THEN, DO/LOOP, BEGIN/AGAIN, and BEGIN/UNTIL. The only part missing from the Forth system is a way to look at the words and variables. Most Forths have a word called WORDS for this. My plan is to have a very simple list-based browser that will let the user delete words and will handle garbage collection. Logical operations like AND and OR have been implemented as well as CORDIC-based functions like SIN, COS, and TAN.

The firmware running in simulation is now a little more than 9KB, which is too big to fit on the calculator's 8KB EEPROM. The CORDIC routines especially take up a lot of room. I'll need to shave at least 2KB off of the firmware to get everything to fit and have room to implement the last few remaining features. My previous plan was to rewrite parts of the firmware in Forth. Now, I plan to also implement a byte-based virtual machine for floating point registers which should make the firmware much smaller and hopefully not sacrifice much speed. 

Features I plan to add to the firmware:

• Word browser with garbage collection
• Simple graphing
• Improved numerical output on the stack display
• New words: ATAN, ACOS, ASIN, MOD, ^, E^, LN

Hardware
There haven't been many updates to the hardware part of this project. The voltage regulator is a switching boost converter that generates 5v from three lithium AA batteries. These have good battery life for high current drain applications like this and also don't leak and damage the device the way alkaline batteries can. The boost converter will let me use the batteries down to a fairly low voltage, whereas a buck converter with four AAs would stop working when the batteries hit 1.3v and still have a lot of charge left. Picking the right capacitors and inductors for the regulator was a little tough since the exact ones listed in the datasheet have been discontinued. The few I picked to try seem to work but the voltage is too high when I run the regulator on a breadboard, so I'll have to wait until I solder it down to the circuit board to be sure.

Website The new page on my website for the project has the firmware running in my 6502 emulator with documentation for the project below it. Some of the documentation sections, like the word list, took quite a bit of HTML and CSS to arrange, so I made a simple markup system to generate the pages. The information for the pages is stored in a markup text file that is easy to read and edit. A Python script reads the file and generates all the HTML files which would have taken a very long time to write by hand. I'm not sure what tools people generally use for this type of job. The system I made was a fun sub-project and really saved a considerable amount of time.

There were also a few small updates to the 6502 emulator that the calculator firmware is running on. One is a check for indirect jumps where the low byte of the address is 0xFF. There is a well known bug in the original NMOS 6502 where those addresses are calculated incorrectly. It turns out that the new check I added to the emulator is not really necessary since assemblers do their own check, but I'll leave it in for now. The HTML layout of the emulator pages is also more modular and cleaned up so it's easier to add new projects that use the emulator.

Conclusion

Now that this project is at a stopping point, I'm going to shift my attention to a new project that I'm working on for my resume. This won't take as long to build as a calculator, so hopefully I can shift back to this project when that was is finished.

Tiny Calculator: Hardware

Tiny Calculator is business card size.

The hardware for this project is finally done! The first step was getting the LCD running. This time I went with a 128x32 LCD from Newhaven, which is a little pricey at $11. A simple HD44780 compatible LCD like I used for my RPN Scientific Calculator project would give me the same 20x4 character resolution for $3-4, but all the ones I have seen are way too big. Another option would be a small OLED screen, which are very cheap but would drain the CR2032 battery a lot faster.

The LCD has 17 pins with 1.5mm spacing, which is smaller than a breadboard or protoboard but still big enough to solder by hand. The majority of the pins are for capacitors, so I soldered a small adapter board to hold them and route the data pins to a breadboard. This was tedious and more difficult than I imagine when I bought the LCD but the hardware worked on the first try. After I got it running, I epoxied the LCD to the board. Next time, I think I will go with something easier to solder like an OLED screen even if it takes more current.

The datasheet for the LCD has some initialization code, which I could not get to work. A search turned up some working C code from another forum that was easy to get running with GCC for the MSP430. Translating the C code to assembly was a little tricky since some of the variables for initializing the SPI module on the MSP430 are not plain constants as you might expect from looking at the C code. It took some searching in the header files to figure out that what appears to be a constant is actually something cleverly defined to load a configuration value from the MSP430. After I got that working, everything else went smooth. Rather than try to design my own 5x7 font, I reused a character set I found on a German forum, which came in handy on another project I have been working on but haven't posted about yet.

The main board of the calculator is pretty simple. It just holds the microcontroller, CR2032 battery, and some pins for programming. All the wires are 30 gauge wire wrap I got from Mouser, which I really like using. The power lines are thicker gauge, but they are there more for color coding than because I need them to be that thick. 30 gauge copper is supposed to be able to carry more than the few mA I am using without dropping a lot of voltage.

The keypad has 35 keys, which is more than the 25 I was planning on originally. The main reason I did this is because it looked strange to have a square keypad. Also, there were two leftover pins since Xin and Xout can be reused as GPIO if there is no crystal.

 Each key takes up one 3x3 block on the protoboard, which is smaller than the 4x3 spacing of the keypad on my Pocket Calculator project. It turns out, it's not too difficult to bend the legs under the button a little to make them fit the tighter spacing. The LCD and the keypad both plug into the main board with headers.

Since the calculator runs on a battery, it's important to keep the calculator in low power mode as much as possible. This turned out to be surprisingly painless in assembly! Setting up interrupts is very straightforward too. The calculator scans the keypad a few dozen times a second and goes back to sleep if there is no work to be done. Each key has a byte of memory allocated to it to implement a counter for debouncing the keys and showing which keys have been read. My very cheap multimeter shows that the calculator uses a lot less current than the datasheet for the MSP430 and LCD suggest. Hopefully I can borrow better equipment and get a more accurate reading to try to better estimate how long the calculator should run before it needs a new battery.

The interface code is already mostly done and will be the topic of the next post on this project. After that, the only step left is adding the key labels.

Tiny Calculator: Improved CORDIC

Since my last post I have made a lot of changes to the CORDIC routines I was working on. As you can see in the chart above, the new version fits in less than the 4.1k of the last version even after adding in logarithms. The change came after I found an article about how the HP-35 did CORDIC calculations. Unlike the other descriptions of the method I have used, this version uses an atan table of powers of 10 instead of powers of 2. This lets you shift the arguments by whole decimal places, which is much faster with BCD numbers than powers of 2 . Before, I had wondered if this would be more efficient, but I don't understand the math behind it well enough to modify the routine myself. My implementation of the method the HP-35 uses only takes 90k cycles, compared to the 1.18 million of the last version. The X and Y that the calculation produces, however, cannot be scaled to produce sine and cosine directly. The scale factor depends on the number of rotations, which is easy to precalculate when the angle is halved every iteration, but not possible to know in advance when you use powers of 10 since each iteration requires up to 9 calculations with each affecting the scale factor. As a result, the ratio of X and Y provides the tangent and the HP-35 used identities involving multiplication, division, and square root to generate sine and cosine from tangent. In addition to the 90k cycles for the CORDIC calculation, I would need at least another 140k cycles for these identities. This is 5 times faster than how I was doing it before, although I'm afraid the accuracy would suffer from the added calculations.

The next thing I tried was posting on the HP museum forum, where Thomas Klemm showed me how to do CORDIC calculations in base 10 without resorting to identities. This was a huge help and a much better way to do things than anything I have tried before. The newest routine I have calculates tangent in only 186k cycles and provides sine and cosine without additional calculations! Like in Thomas' version, I tried to make this CORDIC routine more generic so that I can reuse it for inverse trig functions too. Logarithms and powers of e turned out to be much simpler than trig functions using the method described on the same page about the HP-35.

There are still a lot of things to learn about MSP430 assembly. One thing that tripped me up was thinking that RRA automatically shifts a 0 in from the left when rotating when it actually reproduces the leftmost bit instead. Another surprise was that shifting packed BCD by two decimal places is just as fast loading a word from memory, swapping and combining bytes, then writing the result back to memory as it is to just copy bytes directly. I thought the byte copies would be faster, but I was actually able to shave one cycle off by loading and writing words. I rewrote this short section of code five different times trying to save a cycle or two and eventually realized that this is not a useful way to spend my time. This improvement is too tiny to ever be noticeable, and I want to finish this project soon. There are a few other small improvements I have not spent time on since they would provide only a negligible speed up.

The next step is to start working on hardware and the interface code.

Tiny Calculator: Sine, Cosine, and Tangent

For the trig functions, I started building the same angle table that I used for the CORDIC routines in my RPN Scientific Calculator. Comparing my table to an example calculation I found of how CORDIC works, I noticed that the values are all pi times bigger than the ones in the example. Could I have made the same mistake in my RPN Scientific Calculator? When I get back home from the holidays, I should check to make sure that this does not throw off some of the calculations. Another thing I found out from the same page was that the K value to multiply by after the CORDIC calculation is calculated for a particular number of iterations. In my RPN Scientific Calculator, I included a K value for the maximum number of iterations and truncated it when less precision was used. On second thought, I should have done some testing to make sure truncating the K value to the precision of the argument always yields the best results for a particular level of precision. At the moment I don't plan to redo anything on my older calculators unless something is majorly wrong. It is good, though, to recognize this type of mistake, so I can look out for it in future projects that use CORDIC.

To generate the angle table I used the bc command line calculator. It has a very simple programming language that can run from a script. Interestingly, bc does not seem to do any type of rounding, so the tables I have are unrounded. Maybe I will experiment with a rounded table to see how much of an effect it has. For some of the other tables (including a couple I ended up not needing) I used Python, which has been really helpful. The table itself contains angles descending in size, so I only sto

The first step to implementing the trig functions was replicating the CORDIC calculations in a spreadsheet. This works for about 30 iterations until the numbers become too small for the spreadsheet to handle. Rather than doing bit shift operations like I would on the microcontroller, I multiplied by inverse powers of two, which accomplishes the same goal. When I had that working, I tried generating those multipliers on the MSP430 and multiplying, rather than bit shifts. I thought this might be fairly fast since the multiplier could be left in binary, which makes it quicker to use with the Russian Peasant algorithm, and the amount of zeroes in the multiplier would mean relatively few multiplies altogether. Consider this shortened table of successive inverse powers of two:

New project: Tiny Calculator

My Pocket Calculator project has been on the back burner for a few months while I finish my master's thesis. In the mean time, I got interested in doing a much simpler project to make a very small calculator that will hopefully be about 2.5 inches long. This is the size of a 5x5 keypad and the small 128x32 LCD I want to use. Like my first first calculator, it will use a through hole MSP430. The first calculator needed two MSP430s to contain all the firmware, but I think I can fit everything on one chip for this project. It should also be possible to do what I want with the 512 bytes of internal RAM the chip has, so I won't need any external SRAM, and with 25 keys, I also won't need external shift registers. Other than the microcontroller and some capacitors, the only other thing on the board will be a CR2032 battery. The MSP430 needs 2.7v to run at 16MHz, so I plan to run at 8MHz in order to use the battery down to 2.4v. It might be possible to monitor the battery and run at 16MHz as long as the voltage is high enough, but I don't think I will need the extra speed like I did on the last calculator.

One of the main things that got me interested in this project was finding out that the MSP430 has a decimal add instruction that works on packed BCD words. This is really convenient and should be many times faster than doing BCD manually in C like I did for my first calculator. One possibility would be mixing C and assembly to take advantage of features like this, but I am going to try to do the whole thing in assembly to make it as small and fast as possible. Another speed up should come from switching to a 16 byte floating point format. This will let me calculate logarithms and trig functions to the same precision as my first calculator but fit everything in the 512 bytes of internal RAM. Eliminating the bottleneck of transferring data over SPI one bit at a time will probably be the main speed up. For multiplication, I want to try some of the algorithms I tested for the 6502, and for division, I will try out some based on Netwon's Method. For logarithms and trig functions, I'll probably use CORDIC routines again, but I want to see if Taylor polynomials will be much smaller, even if they are slower. With 25 keys, I can fit in just about everything from my first calculator. It should be able to do a little more than an HP-35. The main drawback compared to my first calculator will be less precision with large numbers and less stack space, although neither should be a problem, since there won't be a programmable mode. Also, I plan to keep track of exponents by the byte, rather than the nibble like a did on the first calculator. This will mean losing precision by a factor of 10 in some cases, but it will make aligning numbers during calculation much simpler.

RPN Scientific Calculator: Tweaks

Recently I was able to get some new components and took the chance to make a few tweaks to the calculator. First of all, I hooked up a new 20x4 character LCD to replace the 16x2 version I was using before. It is gray with black letters and I like how it looks. With this I will be able to make the bottom row of the screen a menu like the kind some of the later HP calculators use. The LCD itself came with male headers so it can be plugged into a breadboard, but there was no convenient place to put it so I decided to run wires from the headers to the breadboard instead. The LCD worked fine at first but quickly became corrupted after I wound the wires into a loop to make them neater. This was causing crosstalk and the problem disappeared when I separated the wires.

I also added a CMOS 555 timer to generate the negative voltage for the LCD. This frees up a microcontroller pin that I am now using to independently drive the input shift register of the RAM. Now I can read the external RAM and the keyboard at the same time without worrying about coordinating interrupts. In order to save energy I decided to use the smallest capacitor and the largest value resistors I could for the timer. Unfortunately, none of the resistor values I had on hand would give me the 30 Hz or so the microcontroller was generating. 48 Hz was the closest I could get using a 0.1 uF capacitor and 100k ohm resistors for R1 and R2. Adding a 470 ohm resistor to the output of the 555 gave a good contrast and should also keep the contrast constant if I try to run everything from a battery later.

The last thing I did was to expand the CORDIC tables to 32 bits wide instead of 16. Using a 16 bit wide table gives around 14 decimal places of accuracy which is sufficient for calculating logarithms. A problem arises, however, when that logarithm is used to calculate things like exponents because those 14 places of accuracy also include the whole part of the answer. A simple calculation like 8^9 only offers 5 decimal places of accuracy after the decimal since the whole part is 9 digits long. The new version takes about 6 seconds to calculate "atan(tan(37))" This is very slow so I will let the user set the precision in settings.

RPN Scientific Calculator: More CORDIC Routines

After finishing the CORDIC routine for logarithms I started on the CORDIC routine for trig functions. For this I needed a different look up table and a different function, but it didn't take up much room in the flash. The table for pre-computed logarithms is stored compactly in flash and the same routine that unpacks it into the external memory is also used to unpack the trig table. With this I can calculate sine, cosine, tangent, and arctangent. It should also be possible to calculate arcsine as well but I haven't tried yet.

To test these new function I tried calculating atan(tan(37)). When using 16 decimal places for the calculations this gives the answer 36.9999999999999781, which is pretty accurate. Unfortunately, this took over two seconds, which is just too slow. The logarithm and powers of e functions were at least twice as fast. In order to speed things up I tried to eliminate as many reads and writes to the external memory as I could. One thing I didn't notice when I wrote the original functions is that the loop condition for a for loop is recalculated each iteration. When the condition depends on a variable in external memory, the variable is fetched on every iteration, which is wasteful if the variable hasn't changed. After changing the code to use local copies of external variables whenever possible, I was able to cut down external memory access by almost 25%.

25% wasn't quite enough so I looked at the code I was using to right shift. This allows me to divide numbers by 2 quickly but takes some extra coding since shifting in BCD is a little more complicated than a normal binary shift. Because of the extra work involved in keeping everything straight during BCD shifting, I was doing shifts one bit at a time. This means a 58 bit shift, for example, would simply do 58 shifts of 1 bit each. As you can imagine this is not efficient and was a big part of the slow down in the code. My solution was to use as many 4-bit shifts as needed, then a few 1 bit shifts at the end to finish it off.

Shifting by 4 bits in BCD is fairly easy. As you probably know, shifting by 4 bits is the same as dividing by 16, and dividing by a number (16 in this case) is the same as summing the results of dividing each decimal place by that number. Since there are only 10 possibilities (0-9) for each decimal place, I stored the results of dividing each possibility by 16 in a look up table and used that to sum the results. Here is an example:

789 ÷ 16 = 700/16 =   4375
                  80/16 =     5000
             +     9/16 =      5625
                               49.3125

The values 4375, 5000, 5625, etc are stored in the look up table. The sum of these results are stored in local RAM since 6 bytes is enough to keep track of the summing long enough to deal with any carries before finally writing the last byte to the external RAM. Doing it like this I only need to read and write every decimal place once per 4-bit shift. This cuts down the number of external memory accesses down to almost one third of what it was at the beginning and allowed me to calculate atan(tan(37)) in a little over a second. All of this fits in 8.1K of Flash meaning I just broke the halfway mark of what the MSP430G2553 chip I am using can hold. If there is any space left over at the end, I would like to implement a similar 8-bit shift routine as well to speed things up even more.

RPN Scientific Calculator: Division and Logarithms

After rewriting the multiplication function I started on the division routine. There are several ways to do this. I used the subtract and shift method. It takes up a little more than 150 lines of code which makes it about twice as big as the multiplication routine. Unlike with the other operations, with division a maximum number of decimal places has to be specified. It seems unlikely that I would ever need more than 16 places, which makes me think a fixed place format might have worked too. This is still possible if I need to shrink the program size.

The next step is to implement logarithms and powers of e. This will be useful on its own but will also let me calculate powers and roots. One way I found to calculate logarithms is with a Taylor series like this: 

ln[(1+x)/(1-x)]=2(x+x³/3+x⁵/5+x⁷/7+....)

This seems ideal since it only requires one loop and several multiply and divide operations which shouldn't take up much room in Flash. Even with the the MSP430 running at 16MHz, it rook over 3 seconds to calculate ln(7). In an effort to speed things up I examined the code for multiplying and dividing but didn't find much to improve. One thing I did change was the addition routine. I was adding a 0 to the beginning of every result so that there would be room for a 1 if I needed to carry. However, in most cases the 0 wasn't needed and when doing repeated additions during multiplication, the 0s accumulated at the beginning of the result wasting memory. Removing these 0s wasted time so I changed the addition code to only add the 0 when necessary. This still didn't make it much faster, though.

Next, I ran the code on my PC and noticed that it needed to access the external memory over 2 million times to calculate the logarithm to 16 decimal places. Clearly this was the bottleneck. The next idea I tried was the CORDIC method which is ideal for small microcontrollers like the MSP430. This uses a precomputed table and only needs adds and bit shifts, two things that microcontrollers can do much more efficiently than multiplying and dividing. Using this method I can calculate e^x and ln(x) for a wide range of values in less than one second because it only needs about 50,000 accesses to the external memory.

After I finished the ln function but before I started on the e^x function, I noticed that the program was already 6.5k. This is a little concerning since 16k is the max size for the program and there are still many more features to add. One thing that can reduce size is the static keyword. Making all my functions static shrunk the program size down to only 3.7k. After adding some more entries to the CORDIC table, improving the ln function, and adding the e^x function, the program size was back up to almost 6.5k again. This seems very strange since the program is now almost 1,000 lines and the ln functions only takes 50 lines. In fact commenting out the ln function reduces the program down to only 4.4k. Why this one small function should suddenly add more than 2k to my code is not clear but I hope to figure it out soon.