[SOLVED] Signed 64bit multiplication on 32bit machine

[HugeCode]

Hi all. I'm facing new problem. I'm using this method to calculate result of 64bit unsigned multiplication:

Code: Select all

mov eax, low1
mul low2
mov esi, eax ;= low1*low2
mov edi, edx ;= overflowing result of low1*low2
mov eax, high1
mul low2
add edi, eax ;+= low2*high1
mov eax, low1
mul high2
add edi, eax ;+= low1*high2
;ommiting high1*high2 because it will surely overflow out of 64 bits
;result is not EDI:ESI

Every number is in format HIGHn:LOWn. Does anybody have idea what should be changed if I want to mutliply two signed 64bit numbers? Is it enough to change only muls to imuls? Please help.

[Brendan]

Hi,

Is it enough to change only muls to imuls?

For 64-bit * 64-bit unsigned integers you get a 128-bit result; and you'd do it like this:

Code: Select all

    result = (v1.high * v2.high) << 64 + (v1.high * v2.low) << 32 + (v1.low * v2.high) << 32 + v1.low * v2.low

If you change the muls to imuls; then "(v1.high * v2.high) << 64" is the only piece that will be right. Each of the other pieces ("(v1.high * v2.low) << 32", "32 + (v1.low * v2.high) << 32" and "v1.low * v2.low") will be wrong half the time (regardless of whether you use mul or imul), and the final result will be wrong 87.5% of the time.

The simplest way to do it correctly is to determine the sign of the result separately, then do unsigned multiplication of the absolute values and correct the sign afterwards; sort of like this:

Code: Select all

    sign = (v1.high ^ v2.high) >> 31;  // Determine sign of result
    result = abs(v1) * abs(v2);        // Unsigned multiplication
    if(sign != 0) {     
        result = -result;              // Negate result if result should've been negative
    }

To negate a number (for both "abs()" and the "result = -result") you won't be able to use the 'neg' instruction (it will only work on 32 bits of 64-bit or 128-bit value being negated). Instead; either subtract the value from zero (using 'sub' and 'sbb' instructions), or invert the bits (using 'not') and add one (using 'add' and 'adc').


Cheers,

Brendan

[Gigasoft]

For 64x64 => 64 multiplication, it doesn't matter if it's signed or unsigned, just use mul.

For 64x64 => 128 multiplication, perform an unsigned multiplication and add the following additional step: If operand 1 is negative, subtract operand 2 from the high part of the result. And if operand 2 is negative, subtact operand 1 from the high part of the result.

[HugeCode]

Thank you both, you really helped me.
Brendan: determining sign separately before calculation seems to be perfect, thank you!
Gigasoft: I don't understand that substractions. What are they for? What do you mean by the high part (maybe high 64bits, or high 32)?

[HugeCode]

Ok, now what about division? Brendan, in this topic I found your post containing code with 64bit division. Below it, there was comment about signed division, that in printf function (the topic was about it) there should be added '-' before number.
I have two more questions on 64bit division:

• What needs to be done with numbers when performing signed division? (Maybe just sign determination and then usage of unsigned division code as for multiplication?)
• Is there any way for performing 64bit/64bit division, or it's not needed and 64/32 bit division is enough for every operation?

Thanks.

[Brendan]

Hi,

Ok, now what about division? Brendan, in this topic I found your post containing code with 64bit division. Below it, there was comment about signed division, that in printf function (the topic was about it) there should be added '-' before number.
I have two more questions on 64bit division:

• What needs to be done with numbers when performing signed division? (Maybe just sign determination and then usage of unsigned division code as for multiplication?)
• Is there any way for performing 64bit/64bit division, or it's not needed and 64/32 bit division is enough for every operation?

Thanks.

For signed division; I'd do the same as I'd for to signed multiplication (separate sign; then calculate; then correct sign of result).

For dividing by an unsigned integer by a 64-bit unsigned integer you can't break it up into 2 or more smaller 32-bit divisions. The method I use is "shift and subtract", and goes like this:

Code: Select all

    result = 0;
    count = 0;
    remainder = numerator;

    while(highest_bit_of_divisor_not_set) {
        divisor = divisor << 1;
        count++;
    }
    while(remainder != 0) {
        if(remainder > divisor) {
            remainder = remainder - divisor;
            result = result | (1 << count);
        }
        if(count == 0) {
            break;
        }
        divisor = divisor >> 1;
        count--;
    }

Of course most of the operations above need to handle the width of the integers being used. I'd recommend implementing (and testing) code to perform these operations on 64-bit unsigned integers before writing the division itself. These would be:

• shifting left by 1 ('add' and 'adc', to add the value to itself instead)
• shifting right by 1 ('shr' and 'rcr' instructions)
• comparison (multiple 'cmp' instructions)
• subtraction ('sub' and 'sbb')
• setting a bit (the 'bts' instruction works well if your result is in memory)

Cheers,

Brendan

[Gigasoft]

I don't understand that substractions. What are they for? What do you mean by the high part (maybe high 64bits, or high 32)?

The high 64 bits. When you did the unsigned multiplication, an operand that was negative was regarded as larger than it really should be by 2^64, so you need to subtract 2^64 times the other operand.

Here is a quick and dirty way to divide (signed) 64 bit integers on x86:

Code: Select all

div64:
mov ecx,Denominator
or ecx,Denominator+4
jz dividedbyzero
fild Numerator
fild Denominator
fld st
fdivr st,st(2)
frndint
fld st
fistp Quotient
fmulp st(1),st
fsubp st(1),st
fistp Remainder
ret

The way I actually do it in my OS is slightly more involved, as it only uses integer instructions. This is unsigned, but a signed version can be made by doing what Brendan said, saving the signs and negating the result afterwards if different.

Code: Select all

public __aulldiv
__aulldiv:
mov eax,[esp+8]
mov ecx,[esp+16]
jecxz divu64_32
cmp eax,ecx
jb divu_0
push esi
mov edx,ecx
bsr ecx,edx
mov esi,[esp+16]
shrd esi,edx,cl
xchg edx,eax
mov eax,[esp+8]
cmp edx,esi
jb divu_ok
shrd eax,edx,1
shr edx,1
dec ecx
divu_ok:
div esi
add ecx,edi
shrd eax,edx,cl
mov esi,eax
mov ecx,eax
mul dword ptr [esp+16]
imul ecx,[esp+20]
add edx,ecx
sub eax,[esp+8]
sbb edx,[esp+12]
js divu_nofix
dec esi
divu_nofix:
mov eax,esi
xor edx,edx
pop esi
ret 16
divu64_32:
xor edx,edx
div dword ptr [esp+12]
push eax
mov eax,[esp+8]
div dword ptr [esp+16]
pop edx
ret 16
divu_0:
xor eax,eax
cdq
ret 16
public __aullrem
__aullrem:
mov eax,[esp+8]
mov ecx,[esp+16]
jecxz remu64_32
cmp eax,ecx
jb remu_0
push esi
mov edx,ecx
bsr ecx,edx
mov esi,[esp+16]
shrd esi,edx,cl
xchg edx,eax
mov eax,[esp+8]
cmp edx,esi
jb remu_ok
shrd eax,edx,1
shr edx,1
dec ecx
remu_ok:
div esi
add ecx,edi
shrd eax,edx,cl
mov ecx,eax
mul dword ptr [esp+16]
imul ecx,[esp+20]
add edx,ecx
sub eax,[esp+8]
sbb edx,[esp+12]
js remu_nofix
sub eax,[esp+16]
sbb edx,[esp+20]
remu_nofix:
neg eax
adc edx,0
neg edx
pop esi
ret 16
remu64_32:
xor edx,edx
div dword ptr [esp+12]
mov eax,[esp+4]
div dword ptr [esp+16]
xchg edx,eax
xor edx,edx
ret 16
remu_0:
xchg edx,eax
mov eax,[esp+4]
ret 16

[sortie]

If this is related to doing a 64-bit division on a 32-bit target using GCC - then you should build libgcc along with your cross-compiler and simply link your kernel with it. It will handle division of 64-bit integers for you along with other useful things that GCC relies on libgcc for.

[Griwes]

If this is related to doing a 64-bit division on a 32-bit target using GCC - then you should build libgcc along with your cross-compiler and simply link your kernel with it. It will handle division of 64-bit integers for you along with other useful things that GCC relies on libgcc for.

So you are basically saying "don't reinvent the wheel" to someone posting on OSDev forums?

[Brynet-Inc]

If you want to avoid using libgcc, BSD's libc provides compatible replacements for the 64-bit arithmetic/comparison and software float routines.

It may be missing some functions, but most of the frequently encountered ones should be implemented.

Code: Select all

cvs -qd [email protected]:/cvs co -P src/lib/libc/quad

[Gigasoft]

That code looks awful. How did they manage to turn a simple arithmetic operation into the monstrosity that is qdivrem.c?

[sortie]

If this is related to doing a 64-bit division on a 32-bit target using GCC - then you should build libgcc along with your cross-compiler and simply link your kernel with it. It will handle division of 64-bit integers for you along with other useful things that GCC relies on libgcc for.

So you are basically saying "don't reinvent the wheel" to someone posting on OSDev forums?

Haha - Nah, my point is that you shouldn't reinvent parts that the compiler supplies. If you insist on doing that, then you probably should reinvent the entire compiler as well.

[Griwes]

If this is related to doing a 64-bit division on a 32-bit target using GCC - then you should build libgcc along with your cross-compiler and simply link your kernel with it. It will handle division of 64-bit integers for you along with other useful things that GCC relies on libgcc for.

So you are basically saying "don't reinvent the wheel" to someone posting on OSDev forums?

Haha - Nah, my point is that you shouldn't reinvent parts that the compiler supplies. If you insist on doing that, then you probably should reinvent the entire compiler as well.

That's my plan

[HugeCode]

Brendan:
On this line:

Code: Select all

 if(remainder > divisor) {

wouldn't it be better if there was >=? For example if you try to divide two 64bit numbers with MSB=0x80 (result x/x=1), then (it looks like it for me) it won't work... There will be result 1 and remainder.

[Brendan]

Hi,

Brendan:
On this line:

Code: Select all

 if(remainder > divisor) {

wouldn't it be better if there was >=? For example if you try to divide two 64bit numbers with MSB=0x80 (result x/x=1), then (it looks like it for me) it won't work... There will be result 1 and remainder.

Yes, it should be ">=".

There's also a bunch of other things you'd want to add; like checking if the divisor is 0 or 1, checking if the divisor fits in 32-bit (and using a faster method if it does), and handling the case where "divisor = divisor << 1;" is larger than 64-bits properly.


Cheers,

Brendan