64-bit HC08 integer math routines here

[CurtThompson]

I needed to do some 64-bit integer math for a project I'm doing.  I looked around and found a paper that describes a method sort of like long division and has some source in Pascal.  The paper is "Multiple-length Division Revisited: a Tour of the Minefield" by Brinch Hansen, June 1994.  Here is a link to the paper: http://brinch-hansen.net/papers/1994b.pdf.  The problem is, the calcs I need to make took about 500ms.

Next I took to assembly code from AN1219, "M68HC08 Integer Math Routines" (http://www.freescale.com/files/microcontrollers/doc/app_note/AN1219.pdf?fsrch=1).  This has a 32-bit by 16-bit divide that I ported to inline assembly.  I extrapolated that code to produce a 64-bit by 32-bit divide.  There are some multiply and right shift routines there as well.  With this version of code, I was able to do the same calcs in 16.9ms (better).

It's not the pretties code but I hope others might find the attached code useful.

Curt

[bigmac]

Hello Curt,

While the AN1219 code is relatively efficient, I notice that the Pack() and Unpack() function are certainly not.  In fact, the four calls seem to require a total of about 9000 cycles, compared with 3500+ cycles for the 32 x 16 division function.

Note that the latter figure could be improved somewhat with the allocation of zero page RAM, and further improvement with the use of instructions applicable to zero page RAM, probably a total saving of about 500 cycles.

However, the situation is simplified if a structure is created, to hold the results during the calculation.  The quantities can then be directly written to the required locations within the structure, and directly read back at the completion of the calculation.  The inline assembly code portion extensively uses indexed addressing. As a result, the code that previously required a total of about 12k cycles, now requires about 3500.

When this code is extended to 64 x 32 division, the number of cycles required is about 11k.

Regards,

Mac

[CurtThompson]

Thanks Mac.  I admit that I am a lacky when it comes to assembly.  I'm sure others will find what you supplied useful too.

Curt