Need C source for 64 bit integer math (have 32bit limit on my compiler)
Andrew
CodeVision has 32bit limitation for integers.
I need to do 64bit integer math (32bx32b, 32b+32b).
I could reinvent the wheel,
but figure this has to be out there
in multiple places for free.
Any suggestions for free
C source for 64bit integer math?
D Yuniskis
> I'm using CodeVision C compiler on an AVR.
> CodeVision has 32bit limitation for integers.
> I need to do 64bit integer math (32bx32b, 32b+32b).
>
> I could reinvent the wheel,
> but figure this has to be out there
> in multiple places for free.
This is a "freshman" homework assignment (i.e., crank
it out in a day). Think of how you perform *decimal*
arithmetic (i.e., one "digit" at a time). Now, think of
a 64 bit operand as just a set of two 32 bit "digits".
You *learn* by doing (and discover issues that you might
never be aware of when you just inherit someone else's
work)
Arlet
This is usually easier done in assembler, where you have access to the
carry flag. You could look at the generated assembler code for 32 bit
math, and extend it for 64 bit.
Or you could use a compiler that supports the "long long" type, such
as gcc.
Nils
For these kind of questions I'd like to recommend to buy the book
"Hackers Delight" (if you can still find a copy of it).
http://www.hackersdelight.org/
The source-code archive from the website it is a nice reference as well.
It does not contain super trivial things like multi-byte additions, but
you can find multi-byte multiplication routines for any purpose (e.g.
32*32 = 64 bits, or high 32 bits of a 64 bit product ect.)
link:
http://www.hackersdelight.org/HDcode.htm
Btw - the code-archive is worth bookmarking and checking once per
quater. The author still adds new stuff every couple of month.
Jon Kirwan
wrote:
Looks like you already posted this up on avrfreaks and got some
replies. I didn't really understand your 32b+32b request, as that
requires only 33 bits -- only one bit is valid in the upper 32-bit
word of a 64-bit result for unsigned, if that's what you wanted. It's
not hard to generate for unsigned, but slightly more trouble for
signed. Also, you didn't specify signed vs unsigned or whether you'd
like to mix the two types, which compounds the problem of providing
any useful answer. And you didn't address speed or code size. I
gather you want this entirely in c, though, and don't want anything
more than multiplication and addition operations?
Tell us where you are now and fill in some more details, if you don't
already have a solution from posting elsewhere. Might be a better
shot at an answer here, then.
Jon
P.S. If you are looking for generalized code in c, there is a book I
might point you towards which gets right down into the details of a
fairly general purpose, expandable set of routines entirely in c.
Nobody
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
static void add64(uint32_t a, uint32_t b, uint32_t *prh, uint32_t *prl)
{
uint32_t rl = a + b;
uint32_t rh = rl < a;
*prl = rl;
*prh = rh;
}
/*
(k*ah + al) * (k*bh + bl)
= k*k*ah*bh + k*(ah*bl + al*bh) + al*bl
*/
static void mul64(uint32_t a, uint32_t b, uint32_t *prh, uint32_t *prl)
{
uint32_t ah = a >> 16, al = a & 0xFFFFU;
uint32_t bh = b >> 16, bl = b & 0xFFFFU;
uint32_t rl = al * bl;
uint32_t rm1 = ah * bl;
uint32_t rm2 = al * bh;
uint32_t rh = ah * bh;
uint32_t rm1h = rm1 >> 16, rm1l = rm1 & 0xFFFFU;
uint32_t rm2h = rm2 >> 16, rm2l = rm2 & 0xFFFFU;
uint32_t rml = rm1l + rm2l;
uint32_t rmh = rm1h + rm2h;
rl += rml << 16;
if (rml & 0xFFFF0000U)
rmh++;
rh += rmh;
*prl = rl;
*prh = rh;
}
int main(int argc, char **argv)
{
uint32_t a, b, rl, rh;
uint64_t r;
if (argc != 3)
return 1;
a = (uint32_t) strtoul(argv[1], NULL, 0);
b = (uint32_t) strtoul(argv[2], NULL, 0);
mul64(a, b, &rh, &rl);
r = ((uint64_t) rh << 32) + rl;
printf("%08x * %08x = %16llx\n", (unsigned) a, (unsigned) b, (unsigned long long) r);
printf("%08x * %08x = %16llx\n", (unsigned) a, (unsigned) b, (unsigned long long) a * b);
add64(a, b, &rh, &rl);
r = ((uint64_t) rh << 32) + rl;
printf("%08x + %08x = %16llx\n", (unsigned) a, (unsigned) b, (unsigned long long) r);
printf("%08x + %08x = %16llx\n", (unsigned) a, (unsigned) b, (unsigned long long) a + b);
return 0;
}
Andrew
All I really needed was to add unsigned 32bit int to a unsigned 64bit
int with restrictions that 32bit is largest int that can be defined.
Not hard, however, it was suggested that I get a general integer lib
that could do everything; signed/unsigned, mul/div/sub/add.
I didn't find anything initially that included what I needed
so wrote the add. Have to break it down into 16bit segments
to get the carry right for 33d bit. Would still like to find
a free lib. May need the other functions in the future.
Got to be several free libs out there.
Jon Kirwan
wrote:
I'm really not following this. I'm sorry, as it might just be my
fault in the way I am interpreting what you write. If a 32 bit result
is the largest result allowed (and I'm assuming that is what you mean
regarding the restriction) adding a 32 bit unsigned to a 64 bit
unsigned is even easier than you mention below. There is no need to
compute a 33rd bit. So I have to assume I don't understand your
restriction. I'm not even sure how you pass in the 64 bit int, nor
what size the function _result_ fits, to be honest. And you earlier
wrote "32b+32b" which seems to differ from today, too. So there is a
lot I still don't feel confident about understanding. Too much to be
of much use, I figure.
>Not hard, however, it was suggested that I get a general integer lib
>that could do everything; signed/unsigned, mul/div/sub/add.
>
>I didn't find anything initially that included what I needed
>so wrote the add. Have to break it down into 16bit segments
>to get the carry right for 33d bit. Would still like to find
>a free lib. May need the other functions in the future.
>Got to be several free libs out there.
There are. But well-healed ones are pretty big and do a lot more than
you are initially asking. You still haven't described speed, code
size, or how often these functions are required relative to the
overall application. So I can't even offer some thoughts.
Well, best of luck. Maybe someone else understands exactly what you
need and where to find it.
Jon
-jg
> There are. But well-healed ones are pretty big and do a lot more than
> you are initially asking. You still haven't described speed, code
> size, or how often these functions are required relative to the
> overall application. So I can't even offer some thoughts.
>
> Well, best of luck. Maybe someone else understands exactly what you
> need and where to find it.
Maybe I'm missing something, but this is AVR ? - and WinAVR has 64 bit
integer support, and is open source ?
- so that suggests a number of solutions ?
-jg
Jon Kirwan
Sounds like it might. Apparently, the OP is using something called
the CodeVision C compiler. So... there may be an issue or two, but
yes. Might be worth a look. I haven't used an AVR in some time, so
I'll leave this to the OP to figure out.
Jon
David Brown
avr-gcc handles 64-bit "long long int", and has all the necessary
library routines for arithmetic on long longs. It's not always very
efficient - they are rarely used, and thus code quality for 64-bit ints
is not a priority for avr-gcc development. But they work correctly,
which is the most important thing, and it's probably still more
efficient than doing things manually.
Andrew
Yes AVR, but have code in CodeVision, not WinAVR GCC.
Porting code is not an option.
speed and code size is not important.
ChrisQ
>
> Yes AVR, but have code in CodeVision, not WinAVR GCC.
> Porting code is not an option.
>
> speed and code size is not important.
Find some info (google) on shift and add, shift and subtract for
multiply and divide in assembler. Then work out the calling standard for
your C compiler so you know which registers the args appear in on entry
to your functions. If the docs don't specify this, write some code that
calls a dummy function that you can break / single step on on to examine
the code and also look at the assembler output if the args are pushed
onto the stack rather than being passed in registers. You need to range
check and trap error cases like divide by zero as well, but you can do
that in the first line or two of a divide function.
It's good practice and quite fun when it all works as intended. Not
rocket science and you should know how to do this sort of thing in any
case :-)...
Regards,
Chris