Help: overflow with (a*b) mod c

[bugzpodder]

Okay, I am using MIPS 32... but it doesnt really matter since i just want to deal with this issue in a more abstract level (relevant to probably every assembly lang, although i am no expert).

Anyways: the problem - compute r=(a*b) mod c
input restrictions: 0<=a,b,c<2^31 and c is non-zero
for any of you not familiar with mod, u=v mod w means u is the non-negative remainder you get when you divide v by w.
that means r<c and the output fits in a 32-bit register.
The problem is with overflow. a*b can be as many as 64-bits (the case i am interested in). computing a mod c and b mod c may not help at all since they can still be over 32-bits. note that if we want to compute u=v mod w, and v is 32-bits, it only takes 2 instructions (divide, get result). but in this case... the best algorithm i've implemented takes around 800 instructions. is there a fast and savvy way to do this efficiently?
technical details, when multiply in MIPS, the result is stored in two registers, HI and Lo, and Hi contains the higher order 32-bits and Lo contains lower order 32-bits of the product. thats probalby all u need to know about mips.

[Maven]

Okay, I am using MIPS 32... but it doesnt really matter since i just want to deal with this issue in a more abstract level (relevant to probably every assembly lang, although i am no expert).

Anyways: the problem - compute r=(a*b) mod c
input restrictions: 0<=a,b,c<2^31 and c is non-zero
for any of you not familiar with mod, u=v mod w means u is the non-negative remainder you get when you divide v by w.
that means r<c and the output fits in a 32-bit register.
The problem is with overflow. a*b can be as many as 64-bits (the case i am interested in). computing a mod c and b mod c may not help at all since they can still be over 32-bits. note that if we want to compute u=v mod w, and v is 32-bits, it only takes 2 instructions (divide, get result). but in this case... the best algorithm i've implemented takes around 800 instructions. is there a fast and savvy way to do this efficiently?
technical details, when multiply in MIPS, the result is stored in two registers, HI and Lo, and Hi contains the higher order 32-bits and Lo contains lower order 32-bits of the product. thats probalby all u need to know about mips.

I think I've got the jist of what you're saying. Basically you're trying to do math that has numbers larger then the registers you have correct? You only have a couple of options off the top of my head, thats either backdown on the size of the numbers you're working with to get them inside the register or do the math with strings. It's a lot of work doing it the string way but you won't have the restrictions on you're number size.

[Brandito]

I reverse engineered some code almost exactly like this.

The original code was:
enc = (pos2+pos1)%74 + 48; //pos2, pos1, and enc can be of type int.

The actually assembly looks like this:

mov    eax,DWORD PTR [ebp-12]
mov    ecx,DWORD PTR [ebp-8]
add    ecx,eax
mov    eax,0xdd67c8a7
imul   ecx
lea    eax,[edx+ecx*1]
mov    edx,eax
sar    edx,0x6
mov    eax,ecx
sar    eax,0x1f
sub    edx,eax
mov    eax,edx
shl    eax,0x3
add    eax,edx
shl    eax,0x2
add    eax,edx
add    eax,eax
sub    ecx,eax
mov    eax,ecx
add    eax,0x30
mov    DWORD PTR [ebp-16],eax

The magic happens with the imul ecx, which puts 32 bits of the high byte into edx and 32 bits of the low byte into eax.

Converting it back into C++ gives us:
enc = pos2+pos1-(((long long)pos2+pos1)*0xdd67c8a7>>38)*74+48;

Type "long long" gives us the needed 64 bits. But due to the insaine shifting... you actually can return a value that would fit in INT... not a Long Long! This is pretty much the magic behind the % and assembly.

I don't know if this is of any use... or leads you to any ideas. I know nothing of MIPS.

[sunburnt]

Instead of computing (a*b) mod m, you can compute it like this, which will be slower, but will not overflow.

Psuedocode Example:

integer a = 43, b = 77;
integer m = 16;
integer result = 0;
integer i;

for(i = 0; i < b; i = i + 1)
begin
   result = result + a; 
   result = result mod m;
end

// result is now the result of the statement (a*b) mod m