64-bit integer implementation for 8-bit microcontroller

views:

117

answers:

+1 Q:

64-bit integer implementation for 8-bit microcontroller

I'm working on OKI 431 microcontroller. This is 8-bit microcontroller. We don't like to have any floating point operation to be performed in our project so we've eliminated all floating point operations and converted them into integer operations in some way. But we cannot eliminate one floating point operation because optimizing the calculation for integer operation requires 64-bit integer which the micro doesn't natively support. It has C compiler that supports upto 32-bit integer operation. The calculation takes too long time which is noticeable in a way to user.

I'm wondering if there is any 64-bit integer library that can be easily used in C for microcontoller coding. Or what is the easiest way to write such thing efficiently? Here efficiently implies minimize amount of time required.

Thanks in advanced.

+2 A:

Wikipedia has a list of libraries.

Matt Kane 2010-09-24 14:55:14

all of these libraries are large enough for code memory i believe. oki 431 has only 64K code memory.

Donotalo 2010-09-24 15:13:49

You can at least investigate the open source ones and take the parts that interest you (depending on your target license, I suppose)

Matt Kane 2010-09-24 15:37:48

+1: Agreed. This is as good as it can get without doing assembly.

blizpasta 2010-09-24 15:54:54

+1 A:

You may have to go into assembly to do this. The obvious things you need are:

addition
2s complement (invert and increment)
left and right arithmetic shift by 1

From those you can build subtraction, multiplication, long division, and longer shifts. Keep in mind that multiplying two 64-bit numbers gives you a 128-bit number, and long division may need to be able to take a 128-bit dividend.

It will seem painfully slow, but the assumption in such a machine is that you need a small footprint, not speed. I assume you are doing these calculations at the lowest frequency you can.

An open-source library may have a slightly faster way to do it, but it could also be even slower.

Mike Dunlavey 2010-09-24 16:10:24

about calculation frequency: the calculation has to be done periodically. minimum period is 10 seconds.

Donotalo 2010-09-24 16:13:13

@Donotalo: If the basic clock were 1mhz I would guess a multiplication or division to be on the order of a millisecond, so that should be OK.

Mike Dunlavey 2010-09-24 16:21:24

@Donotalo: Of course, a basic IEEE floating-point software library would also be in the same range, and wouldn't be home-grown. Your compiler probably comes with one.

Mike Dunlavey 2010-09-24 16:23:45

@Donotalo: Once I stepped through an IEEE floating point addition on an 8088 (16-bit registers). It took around 300 instructions, of which only a few were actually adding. The rest were unpacking, packing, normalizing, checking for special values, etc. But if you don't need it at high frequency, it works just fine.

Mike Dunlavey 2010-09-24 16:36:37

we can use two clock speeds: 32K and 500K. 32K is preferred.

Donotalo 2010-09-24 16:45:17

@Donotalo: So maybe 30-60 ms for a basic operation.

Mike Dunlavey 2010-09-24 17:34:34

+2 A:

Since this is a micro-controller you will probably want to use a simple assembly library. The fewer operations it has to support the simpler and smaller it can be. You may also find that you can get away with smaller than 64 bit numbers (48 bit, perhaps) and reduce the run time and register requirements.

nategoose 2010-09-24 16:20:33

Whenever speed is a problem with floating point math in small embedded systems, and when integer math is not enough, fixed point math is a fast replacement.

http://forum.e-lab.de/topic.php?t=2387

http://en.wikipedia.org/wiki/Fixed-point_arithmetic

http://www.eetimes.com/discussion/other/4024639/Fixed-point-math-in-C

http://en.wikibooks.org/wiki/Embedded_Systems/Floating_Point_Unit

avra 2010-09-27 10:14:46