Need C source for 64 bit integer math (have 32bit limit on my compiler)

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)

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.

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).

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.

link:

Btw - the code-archive is worth bookmarking and checking once per quater. The author still adds new stuff every couple of month.

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.

#include #include #include

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;

/* (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

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.

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.

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

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

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

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.

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