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. Any suggestions for free C source for 64bit integer math?
Need C source for 64 bit integer math (have 32bit limit on my compiler)
Started by ●September 23, 2009
Reply by ●September 23, 20092009-09-23
Andrew wrote:> 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)> Any suggestions for free C source for 64bit integer math?
Reply by ●September 24, 20092009-09-24
On Sep 23, 9:48 pm, Andrew <asm...@blackstone.biz> wrote:> 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. > > Any suggestions for free > C source for 64bit integer math?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.
Reply by ●September 24, 20092009-09-24
Andrew wrote:> 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. > > Any suggestions for free > C source for 64bit integer math? > >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.
Reply by ●September 25, 20092009-09-25
On Wed, 23 Sep 2009 12:48:23 -0700, Andrew <asmith@blackstone.biz> wrote:>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. > >Any suggestions for free >C source for 64bit integer math?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.
Reply by ●September 25, 20092009-09-25
On Wed, 23 Sep 2009 12:48:23 -0700, Andrew wrote:> 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. > > Any suggestions for free > C source for 64bit integer math?#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; }
Reply by ●September 26, 20092009-09-26
Jon Kirwan wrote:> On Wed, 23 Sep 2009 12:48:23 -0700, Andrew <asmith@blackstone.biz> > wrote: > >> 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. >> >> Any suggestions for free >> C source for 64bit integer math? > > 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.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.
Reply by ●September 26, 20092009-09-26
On Sat, 26 Sep 2009 06:37:02 -0700, Andrew <asmith@blackstone.biz> wrote:>Jon Kirwan wrote: >> On Wed, 23 Sep 2009 12:48:23 -0700, Andrew <asmith@blackstone.biz> >> wrote: >> >>> 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. >>> >>> Any suggestions for free >>> C source for 64bit integer math? >> >> 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. > >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.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
Reply by ●September 27, 20092009-09-27
On Sep 27, 7:59=A0am, Jon Kirwan <j...@infinitefactors.org> wrote:> There are. =A0But well-healed ones are pretty big and do a lot more than > you are initially asking. =A0You still haven't described speed, code > size, or how often these functions are required relative to the > overall application. =A0So I can't even offer some thoughts. > > Well, best of luck. =A0Maybe 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
Reply by ●September 27, 20092009-09-27
On Sun, 27 Sep 2009 00:16:09 -0700 (PDT), -jg <jim.granville@gmail.com> wrote:>On Sep 27, 7:59�am, Jon Kirwan <j...@infinitefactors.org> wrote: >> 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 ?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
