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.

Calculator Processors

Most of the microcontrollers and processors I have looked into using have been for my calculator projects. That's one of the main reasons I did my microcontroller comparison a few years ago. Recently, I have gotten interested in other chips I could use for calculator projects, in addition to the 6502, 6800 family, and 8051 chips I was interested in before.

The main two criteria I have are an external memory bus and through-hole package. Right away, this eliminates most modern microcontrollers, since almost all of them with an external memory bus are SMD only. In theory, I could use a chip without an external bus if it had a few hundred KB of RAM for data and a few hundred more KB of RAM or flash for program space, but I haven't found that in a through-hole package. Another point is that I would like the ability to load programs from an SD card, which is impractical if I need to have the chip reflash itself every time I load a program. Through-hole parts are more convenient to solder, and I would like to do a few more projects with them before I try to start making surface mount boards.

Modern microcontrollers

• AVR - None of the ATmega series has an external bus. Some of the ATxmega series do, but they don't come in through-hole packages.
• PIC - For a through-hole part, the PIC32 series is very impressive at 50mhz with 64KB RAM and 256KB of flash, but even this is not enough for what I am planning. The chip requires a separate programmer, and the compiler offers limited optimizations unless you pay, which is absurd in 2018 compared to its competition. It does have something called PMP, which offers a sort of data bus, but it can only address 12 bits, since the DIP part only has 28 pins. 
• MSP430 - This chip worked well for my RPN Scientific Calculator, but it also lacks an external bus.
• Propeller - This is an interesting chip but like the others, it lacks an external bus and does not have enough flash or RAM. The one interesting possibility is doing several calculations in parallel, although I don't know how I would use that for a calculator.
• Zilog - They have some nice chips, including some processors with external buses, but I would like to use something different than what the TI-83 and similar models use.
• LPC1114 - I really like this chip, and I am using it in my Pocket Calculator, but it also lacks an external bus, and it seems that it is no longer manufactured.

Pocket Calculator: Hardware

In the last two weeks I have made a lot of progress on my Pocket Calculator. Normally, I like to breadboard everything and have it working 100% before I solder anything, but I had to speed things up since I was leaving home where all my electronics stuff is. So far, the project has turned out reasonably well with only a few hiccups.

Microcontroller: LPC1114
First of all, I had to get out my old LPC1114s and figure out how to program them again, since I haven't worked with them in over 2 years. Like before, it was really easy to do so with an FT232 cable. After frying an MSP430 Launchpad a few years ago by accidentally giving it 5v from the cable, I was really careful about hooking it up this time. One thing I do is leave the cable unconnected from USB until I recheck all the connections, which saved me this time since I had accidentally plugged into the 5v line again.

Looking on the internet I was surprised to see that no one seems to sell the LPC1114 in DIP28 any more. That means the three that I have left might be the last ones I have to play with. There was some sort of announcement a few years ago that NXP would stop producing the chip then they changed their mind after someone pointed out that the company had promised to keep its chips in production. It looks like they might have decided to stop producing them after all, although they are listed as in production until at least 2022 on the NXP longevity page. One interesting thing I found was a listing for the chip in PLCC44 package with 8KB of RAM instead of the 4 the DIP version has. I'm not sure if those ever made it into production but it would be cool to have one to play with.

Pocket Calculator: Stack

For this calculator, I am working on a more sophisticated stack system than I had for my RPN Scientific Calculator. Instead of stack items being fixed at the maximum length, which wastes a lot of memory, item length varies. With only 4k to work with on the LPC1114, it will be very important to conserve memory wherever possible. As I have it now, each item has a header that indicates its position on the RPN stack, its name, and an ID number for variables in functions. RPN stack positions start at one so that variables marked zero will not appear on the RPN stack. This is useful for named variables, so that they can use the same stack system internally. The ID numbers will allow me to keep track of variables local to functions, so I can easily clear them when the function exits.

The system I have now writes the result of an operation directly to the top of the stack then marks the two consumed items as free memory. This has the advantage of allowing the result to be larger than the operands, which can be useful for things like string concatenation. The screenshot above shows how I was testing the system in C# with a simple calculator that can only add. Freeing items like this will make the stack grow fairly quickly and eventually require garbage collection. The advantage, however, is that calculations should be very fast until garbage collection is required. A slower method would be to scan the stack for a free section that is large enough for the result before adding to the stack, but this will eventually require garbage collection as well. My suspicion is that just adding to the top of the stack will be faster overall, even if garbage collection happens more often.

To keep track of the memory, I decided to implement my own garbage collection system, since malloc in C would lead to unrecoverable fragmentation. On IRC one day I made the mistake of asking about how to implement garbage collected stacks like these internally and ended up wasting over an hour arguing with someone who was convinced I was going about everything totally wrong. In the end, one of the suggestions was to have the calculator user push a 0 onto the stack manually before entering values to be operated on so that the system can overwrite the 0 with the result. This recommendation (and a few of the others given) were just laughably horrible and would seriously cripple the functionality of the calculator. Sometimes people on IRC can give good suggestions, but I also have to remind myself not to argue with people who don't really know what they are talking about but won't admit it.

One of the useful suggestions given by a different person was to use two stacks for calculations. The result goes on the second stack and is then copied back to the main stack overwriting the consumed operands. In theory this system will never need garbage collection, although it seems to me that it will take the same amount of time on average. It may be simpler since calculating free memory, for example, is comparing just one pointer, rather than crawling the stack adding up free chunks. This system assumes, however, that operations always work on the top of the stack, which is not the case when named variables share the same internal stack as the RPN stack. It might make more sense in that case to use the second stack only for named variables and do garbage collection on that stack, while keeping the first stack RPN only to prevent garbage collection.

New project: Pocket Calculator

Recently I got interested in building a very small calculator I can carry around with me. The other calculator projects I worked on are neat, but I don't carry them around because they are too big and fragile. This time I want to make something really practical but also small enough to fit in my pocket. The smallest way I know how to do this with the chips I'm familiar with is using the same LPC1114 in DIP28 package I used for my Programmable RPN Calculator. There are a few changes I would like to make for this calculator, though. First, I want to be able to manipulate all kinds of data on the calculator's stack, such as strings, instead of just floating point BCD numbers. Second, I plan to redo the BCD format I used in the other calculators to store the least significant digits first, which should make them a little easier to deal with. Third, I plan to make all items on the stack variable length, rather than fixed length like on my other calculators. This will be necessary for this calculator since I plan to store the whole stack in the 4k RAM the microcontroller has, instead of on an external SPI RAM chip.

The main new feature I want this calculator to have is a BASIC interpreter. My experience with the first RPN calculator I worked on showed how much of the microcontroller's flash can be eaten up by interface code, so I really don't think I could fit all the calculator functions and interpreter in the LPC1114's 32k of flash. Instead, I plan to store a virtual machine on the chip that can interpret code stored on a large capacity flash or FRAM chip. Retrieving the code over SPI and interpreting it will be much slower than executing code natively on the chip, but I think it will be fast enough for the UI, BASIC editor, and maybe even the tokenizing part of the BASIC editor. On one hand I could switch to a chip with bigger flash, which I am not anxious to do, but I will need some kind of virtual machine anyway to interpret the code generated by the BASIC editor, so it is no loss to use the same virtual machine for the UI. The BASIC programs and editor data will be stored on an SPI SRAM chip, which should work fast enough to edit and tokenize programs, while all the stack and program variables will be stored on the microcontroller.

BCD Addition Speed Test: 6502 vs 8051

12345.6789 + 9999.99999 packed BCD on 8051

A few years ago I decided to revisit the microcontroller comparison I had done to see how much of a speed up I could get recoding my BCD addition routine in 8051 assembly. At the time I was surprised that it was 3-4 times faster than the C version. That original BCD routine, which I used for my RPN Scientific Calculator, uses unpacked BCD characters arranged with the most significant bytes first. For the calculator I want to build with a 6502, I wrote a new routine that stores the least significant bytes first in packed BCD. This takes advantage of the 6502's decimal mode to quickly add packed BCD bytes and avoids having to shift all the bytes when an extra byte has to be added for the final carry. It turns out that the 8051 has an instruction, DA, to correct the result of BCD additions from their binary result back into BCD, so it is easy to do packed BCD for it as well. To compare the speed of the two chips for use in a calculator, I translated the 6502 packed BCD routine to 8051 assembly and ran both versions in their respective simulators.

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: