Re^5: Module for 128-bit integer math?

[salva]

I have just uploaded Math::Int128 to CPAN (GitHub repository).

It has to be compiled with the development version of GCC for its 128bit integer support.

At this point, the module is completely experimental, has been only slightly tested (it has no tests, yet) and may contain lots of bugs, so, don't think about using it for anything serious!

[ikegami]

• Does int128() and uint128() croak for "0400000000000000000000000000000000000000"?
• Does $x + undef and the like warn? (Note that «undef + $x» cannot warn without making «my $x; $x += int128(...)» warn.)
• Does signed to unsigned promotion occur when required? (e.g. when adding two a large number overflows.)
• Does unsigned to signed promotion occur when required? (e.g. when subtraction overflows to something negative.)
• Are the string buffers always suitably aligned for a int128_t? (You use memcpy in some spots, but casts in others.)

[salva]

Does int128() and uint128() croak for "0400000000000000000000000000000000000000"?

It should now ;-)

Does $x + undef and the like warn?

yes

(Note that «undef + $x» cannot warn without making «my $x; $x += int128(...)» warn.)

Operations with undefs always generate warnings. Emulating the Perl behavior for built-ins up to this level is not one of my targets.

Does signed to unsigned promotion occur when required? (e.g. when adding two a large number overflows.)

Does unsigned to signed promotion occur when required? (e.g. when subtraction overflows to something negative.)

No, automatic promotions would just complicate the semantics of the module too much. Currently, the module provides modulo 2**128 signed and unsigned arithmetic and the semantics are pretty simple:
• Mixing Math::UInt128 with Perl native types always generates Math::UInt128 values.
• Mixing Math::Int128 with Perl native types always generates Math::Int128 values.
• If Math::UInt128 and Math::Int128 types are mixed in some operation, the result is cast to the type of the left operator.

Are the string buffers always suitably aligned for a int128_t? (You use memcpy in some spots, but casts in others.)

Internally 128bit values are stored on the stack or on the PV slot of an SV allocated with newSV(16). As GCC seems to use 64bit instructions to load 128 bits integers from memory, alignment should be right.

[ikegami]

So you say that newSV(16) always allocates the bytes on a suitable memory boundary. I didn't know of any such guarantee, thus my question.

Well, then you can replace those calls to Copy with casts and assignments

Update: Fixed bad grammar. Also, the second paragraph should be ignored because it makes sense to support passing OOK strings to native_to_int128 functions.

[syphilis]

I have just uploaded Math::Int128 to CPAN

Just tried building it using the mingw64 compiler, and it failed spectacularly. I speculate that this is a shortcoming of the compiler ... though it does have the 16 byte __int128 data type. However, the __int128 data type appears to be a signed value only.
The "unsigned __int128" is, afaict, an unknown type and, I suspect, the cause of the errors reproduced below.

Trying to determine sizeof(unsigned __int128) in a C program produces the compile-time error:
expected ')' before '__int128'

Salva, let me know if there's any point in following this further with that compiler, and I'll certainly try to work through it. Here's what I get when running dmake (x64 build of perl-5.12.0):

C:\sis\Math-Int128-0.01>dmake test
cp lib/Math/Int128.pm blib\lib\Math\Int128.pm
C:\_64\perl512_M\bin\perl.exe C:\_64\perl512_M\lib\ExtUtils\xsubpp  -t
+ypemap C:\
_64\perl512_M\lib\ExtUtils\typemap  Int128.xs > Int128.xsc && C:\_64\p
+erl512_M\b
in\perl.exe -MExtUtils::Command -e "mv" -- Int128.xsc Int128.c
x86_64-w64-mingw32-gcc -c  -I.  -s -O2 -DWIN32 -DHAVE_DES_FCRYPT -DWIN
+64 -DCONSE
RVATIVE -DPERL_IMPLICIT_CONTEXT -DPERL_IMPLICIT_SYS -fno-strict-aliasi
+ng -mms-bi
tfields -DPERL_MSVCRT_READFIX -g -O0      -DVERSION=\"0.01\"    -DXS_V
+ERSION=\"0
.01\"  "-IC:\_64\perl512_M\lib\CORE"   Int128.c
Int128.xs:15:27: error: expected '=', ',', ';', 'asm' or '__attribute_
+_' before
'uint128_t'
Int128.xs:63:17: error: expected declaration specifiers or '...' befor
+e 'uint128
_t'
Int128.xs: In function 'newSVu128':
Int128.xs:66:22: error: 'u128' undeclared (first use in this function)
Int128.xs:66:22: note: each undeclared identifier is reported only onc
+e for each
 function it appears in
Int128.xs: At top level:
Int128.xs:99:1: error: expected '=', ',', ';', 'asm' or '__attribute__
+' before '
atoa128'
Int128.xs:169:1: error: expected '=', ',', ';', 'asm' or '__attribute_
+_' before
'SvU128'
Int128.xs: In function 'su128_to_number':
Int128.xs:210:5: error: 'uint128_t' undeclared (first use in this func
+tion)
Int128.xs:210:15: error: expected ';' before 'u128'
Int128.xs:212:10: error: 'u128' undeclared (first use in this function
+)
Int128.xs: At top level:
Int128.xs:221:26: error: expected ')' before 'u128'
Int128.xs:247:23: error: expected ')' before 'i128'
Int128.xs: In function 'XS_Math__Int128_uint128':
Int128.xs:274:5: error: too many arguments to function 'newSVu128'
Int128.xs:63:1: note: declared here
Int128.xs: In function 'XS_Math__Int128_net_to_uint128':
Int128.xs:333:55: error: 'uint128_t' undeclared (first use in this fun
+ction)
Int128.xs:333:65: error: expected ')' before 'pv'
Int128.xs:334:65: error: expected ')' before 'pv'
Int128.xs:335:63: error: expected ')' before 'pv'
Int128.xs:336:61: error: expected ')' before 'pv'
Int128.xs:337:59: error: expected ')' before 'pv'
Int128.xs:338:57: error: expected ')' before 'pv'
Int128.xs:339:55: error: expected ')' before 'pv'
Int128.xs:340:53: error: expected ')' before 'pv'
Int128.xs:341:51: error: expected ')' before 'pv'
Int128.xs:342:49: error: expected ')' before 'pv'
Int128.xs:343:47: error: expected ')' before 'pv'
Int128.xs:344:45: error: expected ')' before 'pv'
Int128.xs:345:43: error: expected ')' before 'pv'
Int128.xs:346:41: error: expected ')' before 'pv'
Int128.xs:347:39: error: expected ')' before 'pv'
Int128.xs:348:37: error: expected ')' before 'pv'
Int128.xs:348:37: error: too many arguments to function 'newSVu128'
Int128.xs:63:1: note: declared here
Int128.xs: In function 'XS_Math__Int128_uint128_to_net':
Int128.xs:375:5: error: 'uint128_t' undeclared (first use in this func
+tion)
Int128.xs:375:15: error: expected ';' before 'u128'
Int128.xs:383:36: error: 'u128' undeclared (first use in this function
+)
Int128.xs: In function 'XS_Math__Int128_native_to_uint128':
Int128.xs:411:5: error: too many arguments to function 'newSVu128'
Int128.xs:63:1: note: declared here
Int128.xs: In function 'XS_Math__Int128_uint128_to_native':
Int128.xs:437:5: error: 'uint128_t' undeclared (first use in this func
+tion)
Int128.xs:437:15: error: expected ';' before 'u128'
Int128.xs:443:5: error: 'u128' undeclared (first use in this function)
Int128.xs: In function 'XS_Math__Int128_uint128_to_hex':
Int128.xs:453:5: error: 'uint128_t' undeclared (first use in this func
+tion)
Int128.xs:453:15: error: expected ';' before 'u128'
Int128.xs:459:17: error: 'u128' undeclared (first use in this function
+)
Int128.xs: In function 'XS_Math__Int128__left':
Int128.xs:623:9: error: 'uint128_t' undeclared (first use in this func
+tion)
Int128.xs:623:19: error: expected ';' before 'b'
Int128.xs:626:13: error: 'b' undeclared (first use in this function)
Int128.xs:635:19: error: expected ';' before 'b'
Int128.xs: In function 'XS_Math__Int128__right':
Int128.xs:652:9: error: 'uint128_t' undeclared (first use in this func
+tion)
Int128.xs:652:19: error: expected ';' before 'b'
Int128.xs:655:13: error: 'b' undeclared (first use in this function)
Int128.xs:664:19: error: expected ';' before 'b'
Int128.xs: In function 'XS_Math__UInt128__add':
Int128.xs:938:9: error: too many arguments to function 'newSVu128'
Int128.xs:63:1: note: declared here
Int128.xs: In function 'XS_Math__UInt128__sub':
Int128.xs:957:27: error: too many arguments to function 'newSVu128'
Int128.xs:63:1: note: declared here
Int128.xs: In function 'XS_Math__UInt128__mul':
Int128.xs:973:9: error: too many arguments to function 'newSVu128'
Int128.xs:63:1: note: declared here
Int128.xs: In function 'XS_Math__UInt128__div':
Int128.xs:988:5: error: 'uint128_t' undeclared (first use in this func
+tion)
Int128.xs:988:15: error: expected ';' before 'up'
Int128.xs:989:15: error: expected ';' before 'down'
Int128.xs:993:13: error: 'up' undeclared (first use in this function)
Int128.xs:994:13: error: 'down' undeclared (first use in this function
+)
Int128.xs:1002:9: error: too many arguments to function 'newSVu128'
Int128.xs:63:1: note: declared here
Int128.xs: In function 'XS_Math__UInt128__remainder':
Int128.xs:1021:5: error: 'uint128_t' undeclared (first use in this fun
+ction)
Int128.xs:1021:15: error: expected ';' before 'up'
Int128.xs:1022:15: error: expected ';' before 'down'
Int128.xs:1026:13: error: 'up' undeclared (first use in this function)
Int128.xs:1027:13: error: 'down' undeclared (first use in this functio
+n)
Int128.xs:1035:9: error: too many arguments to function 'newSVu128'
Int128.xs:63:1: note: declared here
Int128.xs: In function 'XS_Math__UInt128__left':
Int128.xs:1054:9: error: 'uint128_t' undeclared (first use in this fun
+ction)
Int128.xs:1054:19: error: expected ';' before 'a'
Int128.xs:1056:13: error: 'a' undeclared (first use in this function)
Int128.xs:1057:13: error: 'b' undeclared (first use in this function)
Int128.xs:1063:9: error: too many arguments to function 'newSVu128'
Int128.xs:63:1: note: declared here
Int128.xs: In function 'XS_Math__UInt128__right':
Int128.xs:1082:9: error: 'uint128_t' undeclared (first use in this fun
+ction)
Int128.xs:1082:19: error: expected ';' before 'a'
Int128.xs:1084:13: error: 'a' undeclared (first use in this function)
Int128.xs:1085:13: error: 'b' undeclared (first use in this function)
Int128.xs:1091:9: error: too many arguments to function 'newSVu128'
Int128.xs:63:1: note: declared here
Int128.xs:1094:19: error: expected ';' before 'b'
Int128.xs: In function 'XS_Math__UInt128__spaceship':
Int128.xs:1111:5: error: 'uint128_t' undeclared (first use in this fun
+ction)
Int128.xs:1111:15: error: expected ';' before 'left'
Int128.xs:1112:15: error: expected ';' before 'right'
Int128.xs:1115:9: error: 'left' undeclared (first use in this function
+)
Int128.xs:1116:9: error: 'right' undeclared (first use in this functio
+n)
Int128.xs: In function 'XS_Math__UInt128__and':
Int128.xs:1209:9: error: too many arguments to function 'newSVu128'
Int128.xs:63:1: note: declared here
Int128.xs: In function 'XS_Math__UInt128__or':
Int128.xs:1225:9: error: too many arguments to function 'newSVu128'
Int128.xs:63:1: note: declared here
Int128.xs: In function 'XS_Math__UInt128__xor':
Int128.xs:1241:9: error: too many arguments to function 'newSVu128'
Int128.xs:63:1: note: declared here
Int128.xs: In function 'XS_Math__UInt128__bnot':
Int128.xs:1266:5: error: too many arguments to function 'newSVu128'
Int128.xs:63:1: note: declared here
Int128.xs: In function 'XS_Math__UInt128__neg':
Int128.xs:1276:5: error: too many arguments to function 'newSVu128'
Int128.xs:63:1: note: declared here
Int128.xs: In function 'XS_Math__UInt128__clone':
Int128.xs:1306:5: error: too many arguments to function 'newSVu128'
Int128.xs:63:1: note: declared here
dmake:  Error code 129, while making 'Int128.o'

Cheers,
Rob

[salva]

Probably the version of GCC you are using is not recent enough.

What do you get when you run...?

x86_64-w64-mingw32-gcc --version

[syphilis]

I get:

C:\>x86_64-w64-mingw32-gcc --version
x86_64-w64-mingw32-gcc (GCC) 4.6.0 20100414 (experimental)
Copyright (C) 2010 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There i
+s NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PUR
+POSE.

C:\>

Update: But, in addition to the version number, there's also the consideration of what features have been ported to MinGW.

Cheers,
Rob

[BrowserUk]

Wow! That was fast!

Unfortunately, I don't think I'll be able to make use of it :(

Whilst I have MinGW for 32-bit setup and working, I've never succeeded in getting a 64-bit version to work in conjunction with my 64-perl. And I need this to work there.

I will download it and see if I can build it for 32-bit, but it won't be for a couple of days as I'm out tomorrow. I'll also try to knock up a test script, though it won't use Test::*. For this kind of thing I favour a random testing mechanism. Eg. generate a couple of numbers; multiply them; divide the results by one of them and check that result matches the other. Similarly for add/subract, shift-left/right etc.

I've started to develop a my own using MSC and a struct containing two 64-bit ints. Add/subtract and multiply work--albeit that the latter uses a slow algorithm. I'm a bit hung up on div/mod at the moment.

For a first pass I'm doing this using standard C math. In theory, it should be quicker using the 128-bit XMM registers, but the docs for the SSE/SSE2/SSE3 et al. intrinsics are less than detailed. Counter to my understanding earlier in this thread, those instructions don't support 128-bit math directly. They do support SIMD operations on pairs of 64-bit ints/uints, which in theory should speed up multiplication/division no end, but the combinations of incantations required are not at all clear. I've failed completely to turn up any examples on the web.

Maybe if I can get it something to fly here, we could look at adding it to your module; or making a Win module that yours can defer to on this platform?

One thing that might be useful to me if you have the time, is an assembler dump of the sources. Can gcc do that? And if it can, would it show the actual operations involved, or just calls to system library routines? Are they inlined?

[ikegami]

One thing that might be useful to me if you have the time, is an assembler dump of the sources. Can gcc do that?

gcc -S a.c

And if it can, would it show the actual operations involved, or just calls to system library routines?

It provides the assembler code for the code you are compiling, which would include inlined functions, but I don't see why it would disassemble existing objects.

$ cat a.c
#include <stdio.h>

int main() {
   printf("Hello, World!\n");
   return 0;
}

$ cat a.s
        .file   "a.c"
        .section        .rodata
.LC0:
        .string "Hello, World!"
        .text
.globl main
        .type   main, @function
main:
        leal    4(%esp), %ecx
        andl    $-16, %esp
        pushl   -4(%ecx)
        pushl   %ebp
        movl    %esp, %ebp
        pushl   %ecx
        subl    $4, %esp
        movl    $.LC0, (%esp)
        call    puts
        movl    $0, %eax
        addl    $4, %esp
        popl    %ecx
        popl    %ebp
        leal    -4(%ecx), %esp
        ret
        .size   main, .-main
        .ident  "GCC: (Debian 4.3.2-1.1) 4.3.2"
        .section        .note.GNU-stack,"",@progbits

Are they inlined?

I can't try to install the dev gcc needed for Math::Int128 at this moment.

[salva]

C code:
Read more... (538 Bytes)
Assembler generated by gcc -O3 -march=core2:
Read more... (2 kB)
So, it uses inlined 64bits arithmetic, except for division and modulo operations that are library calls.

[BrowserUk]

but I don't see why it would disassemble existing objects.

It obviously wouldn't disassemble anything.

But if the 128-bit math functions were marked inline, their implementation would show up.

If not inlined, then the names of the routines called to perform it should be visible, and that would aid tracking down their implementation in the library sources.