64-bit Support: Multiplication to 128bit

General FreeBASIC programming questions.
stephanbrunker
Posts: 62
Joined: Nov 02, 2013 14:57

64-bit Support: Multiplication to 128bit

Post by stephanbrunker »

As far as i know, the x64-Architecture has a 128bit Register. My question is: Is a multiplication of two 64-bit Integers to a 128-bit Integer supported or is that yet to come? In the 32-bit, you can multiply Long * Long = Ulongint. I ask because a couple of crypto algorythms use that multiplication ... and it would effectively speed up at factor 4 or so against the 32-bit implementation with a bigint.
counting_pine
Site Admin
Posts: 6323
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Re: 64-bit Support: Multiplication to 128bit

Post by counting_pine »

stephanbrunker wrote:Is a multiplication of two 64-bit Integers to a 128-bit Integer supported or is that yet to come? In the 32-bit, you can multiply Long * Long = Ulongint.
It is? I didn't know that! If so, it sounds useful, but I don't know if it's intentional: Long is supposed to behave like Integer in 32-bit, and Integers are usually considered to be at least as large as Longs. But I'm pretty sure multiplying Integers returns an Integer..
Re 128-bit returns: currently the problem is we don't have a 128-bit Integer type at all yet. But maybe one could be added..
The alternative would be a function that returns two Longints, but that wouldn't be as nice to use.
marcov
Posts: 3455
Joined: Jun 16, 2005 9:45
Location: Netherlands
Contact:

Re: 64-bit Support: Multiplication to 128bit

Post by marcov »

In the 32-bit case the 64-bit type is added because it is added for many purposes (like diskspace that exceeded 2GB long ago)

The 128-bit cases are really specialized, I would first add an intrinsic (and maybe you can already access such intrinsic from libgcc with c backend)
stephanbrunker
Posts: 62
Joined: Nov 02, 2013 14:57

Re: 64-bit Support: Multiplication to 128bit

Post by stephanbrunker »

I have no clue about assembler programming, but I've read here:

http://msdn.microsoft.com/en-us/library ... s.85).aspx

that there're sixteen 128bit SSE Registers. I don't know for which purpose, but floating point calculations, divisions and multiplications of 64bit data seems the most likely usage. The result would be split over two 64bit integers. But this seems unsolved also in other languages. I've read of an _uint128_t in gcc and a 64x64=128bit asm ( http://locklessinc.com/articles/256bit_arithmetic/ ), but mostly it is solved by doing the multiplication or division in a couple of steps. And that is what I've done with my own bigint source. The speed of the division is mostly limited by the size of blocks used and I've spend months to speed it up as much as possible. To use 16bit blocksize, the neccessary testdivison to get the next 16-bits of the quotient has 48bit because of the carry from the previous round (max 16bit) and the possible overflow of the next least significant block (also 16bit). Because a division needs the most cycles and so I only have to calculate it once a round. Then you substract 16x16=32 bitwise. With a possible testdivision of 96bit, the blocksize can increased to 32bit, thus doubling the speed of the operation.
marcov
Posts: 3455
Joined: Jun 16, 2005 9:45
Location: Netherlands
Contact:

Re: 64-bit Support: Multiplication to 128bit

Post by marcov »

SSE registers have 64-bit double or 32-bit integer as largest sizes. Maybe newer ones also can do 64-bit ints, dunno.
They pack multiple such types in a 128bit (or 256-bit AVX) register. (the x87 copro also supports 64-bits integers, "comp")

SSE2+ can be a substitute for the coprocessor in some cases, but it doesn't provide higher capacity integers.

Note that the division of the largest integer (which is larger than a register) must fit in a register. It is not a general int<x> division, since then int<x>=int<x> div something should be possible, and only int<x-1>= int<x> div something is possible in a single instruction.

As said it is sometimes exposed as intrinsic for special cases, in the same way as division primitives that yield both division result and remainder in one go. But there is not enough support to make a complete type without soft emulation. (soft emulation of the integer type just one level above register size is fairly cheap though, and is commonly done for int64 on 32-bit systems)
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: 64-bit Support: Multiplication to 128bit

Post by albert »

@Marcov

Crypto using math can pretty much be decyphered by the CIA

My method http://www.fnxbasic.com/cgi-bin/yabb2/Y ... 1246910618
Takes a clump of message bits and generates 4 times as many garbage bits and then scrambles the message bits into the garbage to a user defined key (scramble order) , each colunm of numbers is a byte of the message and the numbers are where that bit of message is in the garbage bits.

I think in order to crack mine it would take checking every possible scramble order..
But mine allows you to multiply scramble , by copying the output to the input and scrambling with the same or a different key.
You have to write your own key encryption , cause if i put it in the code , then anyone with the code could decypher it.
So the key is not cyphered. It's just plain old 8 bit ascii.
counting_pine
Site Admin
Posts: 6323
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Re: 64-bit Support: Multiplication to 128bit

Post by counting_pine »

albert wrote:Crypto using math can pretty much be decyphered by the CIA
Broadly speaking, every conceivable method of cryptography involves "math" of some sort.
If you're unable to analyse an encryption algorithm mathematically, then you're unable to make any guarantees about its security. All you have to go on is intuition, and many people have been fooled by their intuition before when trying to create secure algorithms.
dkl
Site Admin
Posts: 3235
Joined: Jul 28, 2005 14:45
Location: Germany

Re: 64-bit Support: Multiplication to 128bit

Post by dkl »

Adding an int128 type could be interesting, but as I understand it would be available on 64bit only, and the compiler wouldn't support 128bit constants or constant folding, like gcc:
https://gcc.gnu.org/onlinedocs/gcc/_005 ... nt128.html

We can support 64bit constant folding easily in the 32bit compiler, but 128bit is a different story... even if the 64bit compiler could use int128, the 32bit compiler couldn't, so cross-compiling from 32bit to 64bit wouldn't be possible.
marcov
Posts: 3455
Joined: Jun 16, 2005 9:45
Location: Netherlands
Contact:

Re: 64-bit Support: Multiplication to 128bit

Post by marcov »

dkl wrote:Adding an int128 type could be interesting,
(the interesting one is the unsigned 128-bit one. SInce that requires a 129-bit type to evaluate 128-bit signed+ unsigned or severe hobbling)
We can support 64bit constant folding easily in the 32bit compiler, but 128bit is a different story... even if the 64bit compiler could use int128, the 32bit compiler couldn't, so cross-compiling from 32bit to 64bit wouldn't be possible.
Practical applications of a 128-bit integers outside math/encryption that I know of are in filesystems like ZFS (usually because their potentially distributed nature makes the range more inefficiently used) and high granularity timestamps (like epoch/unix time with nanoseconds resolution) .

And you can use 128-bit fses on 32-bit, and time doesn't depend on architecture....
MichaelW
Posts: 3500
Joined: May 16, 2006 22:34
Location: USA

Re: 64-bit Support: Multiplication to 128bit

Post by MichaelW »

stephanbrunker wrote:I have no clue about assembler programming, but I've read here...
This example (done under adverse conditions so I'm not sure that it's entirely correct):

Code: Select all


'' Use dim shared variables for easy access from assembly.

dim shared as longint gx, gy

gx=&h0000000000000002
gy=&h0000000000000010

print hex(gx,16)
print hex(gy,16)

asm
    ".intel_syntax noprefix"    '' Switch to Intel syntax
    "mov    rax, [GX$]"
    "imul   QWORD PTR [GY$]"    '' RDX:RAX <- 128-bit product
    "mov    [GX$], rdx"
    "mov    [GY$], rax"
    ".att_syntax prefix"        '' Switch back to AT&T syntax
end asm

print hex(gx,16);hex(gy,16)

asm
    ".intel_syntax noprefix"
    "mov    rdx, [GX$]"
    "mov    rax, [GY$]"
    "mov    QWORD PTR [GX$], 2"
    "idiv   QWORD PTR [GX$]"    '' RAX <- quotient, RDX <- remainder
    "mov    [GX$], rdx"
    "mov    [GY$], rax"
    ".att_syntax prefix"
end asm

print hex(gx,16);hex(gy,16)

sleep
Compiled with FreeBASIC Compiler - Version 1.00.0 (09-14-2014), built for win64 (64bit), and running on my 64-bit laptop under Windows 8.1, produces these results:

Code: Select all

0000000000000002
0000000000000010
00000000000000000000000000000020
00000000000000000000000000000010
I have no reasonable way to compare run times, but I think the multiply and divide instructions, together with the necessary setup instructions, are very likely faster than any multi-step calculation that produces the same result.
albert
Posts: 6000
Joined: Sep 28, 2006 2:41
Location: California, USA

Re: 64-bit Support: Multiplication to 128bit

Post by albert »

@MichaelW

Compiler output:
3.c: In function 'main':
3.c:32:28: error: expected ':' or ')' before '.' token
3.c:33:28: error: expected ':' or ')' before 'mov'
3.c:34:28: error: expected ':' or ')' before 'imul'
3.c:35:28: error: expected ':' or ')' before 'mov'
3.c:36:28: error: expected ':' or ')' before 'mov'
3.c:37:28: error: expected ':' or ')' before '.' token
3.c:42:28: error: expected ':' or ')' before '.' token
3.c:43:28: error: expected ':' or ')' before 'mov'
3.c:44:28: error: expected ':' or ')' before 'mov'
3.c:45:28: error: expected ':' or ')' before 'mov'
3.c:46:28: error: expected ':' or ')' before 'idiv'
3.c:47:28: error: expected ':' or ')' before 'mov'
3.c:48:28: error: expected ':' or ')' before 'mov'
3.c:49:28: error: expected ':' or ')' before '.' token
MichaelW
Posts: 3500
Joined: May 16, 2006 22:34
Location: USA

Re: 64-bit Support: Multiplication to 128bit

Post by MichaelW »

Albert,

I have no way to check this ATM, but I suspect that you are trying to compile with the 32-bit compiler.
fxm
Moderator
Posts: 12082
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: 64-bit Support: Multiplication to 128bit

Post by fxm »

And don't compile with option '-asm intel'.
MichaelW
Posts: 3500
Joined: May 16, 2006 22:34
Location: USA

Re: 64-bit Support: Multiplication to 128bit

Post by MichaelW »

fxm wrote:And don't compile with option '-asm intel'.
I'm not sure exactly what you mean, but I don't use the -asm intel option. Here is my command line:

Code: Select all

"c:\program files\freebasic\fbc" -w pendantic -v -R -RR -C -s console test.bas
And if I add -asm intel then I get:

Code: Select all


C:\Users\User\FreeBASIC My\Asm>"c:\program files\freebasic\fbc" -w pendantic -as
m intel -v -R -RR -C -s console test.bas
FreeBASIC Compiler - Version 1.00.0 (09-14-2014), built for win64 (64bit)
Copyright (C) 2004-2014 The FreeBASIC development team.
standalone
target:       win64, x86-64, 64bit
compiling:    test.bas -o test.c (main module)
compiling C:  c:\program files\freebasic\bin\win64\gcc.exe -m64 -march=x86-64 -S
 -nostdlib -nostdinc -Wall -Wno-unused-label -Wno-unused-function -Wno-unused-va
riable -Wno-unused-but-set-variable -Wno-main -Werror-implicit-function-declarat
ion -O0 -fno-strict-aliasing -frounding-math -fno-math-errno -fno-exceptions -fn
o-unwind-tables -fno-asynchronous-unwind-tables -masm=intel "test.c" -o "test.as
m"
test.c: In function 'main':
test.c:32:28: error: expected ':' or ')' before '.' token
  __asm__ __volatile__( "\t".intel_syntax noprefix"\n" :  :  : "cc", "memory", "
eax", "ebx", "ecx", "edx", "esp", "edi", "esi" );
                            ^
test.c:33:28: error: expected ':' or ')' before 'mov'
  __asm__ __volatile__( "\t"mov    rax, [GX$]"\n" :  :  : "cc", "memory", "eax",
 "ebx", "ecx", "edx", "esp", "edi", "esi" );
                            ^
test.c:34:28: error: expected ':' or ')' before 'imul'
  __asm__ __volatile__( "\t"imul   QWORD PTR [GY$]"    \n" :  :  : "cc", "memory
", "eax", "ebx", "ecx", "edx", "esp", "edi", "esi" );
                            ^
test.c:35:28: error: expected ':' or ')' before 'mov'
  __asm__ __volatile__( "\t"mov    [GX$], rdx"\n" :  :  : "cc", "memory", "eax",
 "ebx", "ecx", "edx", "esp", "edi", "esi" );
                            ^
test.c:36:28: error: expected ':' or ')' before 'mov'
  __asm__ __volatile__( "\t"mov    [GY$], rax"\n" :  :  : "cc", "memory", "eax",
 "ebx", "ecx", "edx", "esp", "edi", "esi" );
                            ^
test.c:37:28: error: expected ':' or ')' before '.' token
  __asm__ __volatile__( "\t".att_syntax prefix"\n" :  :  : "cc", "memory", "eax"
, "ebx", "ecx", "edx", "esp", "edi", "esi" );
                            ^
test.c:42:28: error: expected ':' or ')' before '.' token
  __asm__ __volatile__( "\t".intel_syntax noprefix"\n" :  :  : "cc", "memory", "
eax", "ebx", "ecx", "edx", "esp", "edi", "esi" );
                            ^
test.c:43:28: error: expected ':' or ')' before 'mov'
  __asm__ __volatile__( "\t"mov    rdx, [GX$]"\n" :  :  : "cc", "memory", "eax",
 "ebx", "ecx", "edx", "esp", "edi", "esi" );
                            ^
test.c:44:28: error: expected ':' or ')' before 'mov'
  __asm__ __volatile__( "\t"mov    rax, [GY$]"\n" :  :  : "cc", "memory", "eax",
 "ebx", "ecx", "edx", "esp", "edi", "esi" );
                            ^
test.c:45:28: error: expected ':' or ')' before 'mov'
  __asm__ __volatile__( "\t"mov    QWORD PTR [GX$], 2"\n" :  :  : "cc", "memory"
, "eax", "ebx", "ecx", "edx", "esp", "edi", "esi" );
                            ^
test.c:46:28: error: expected ':' or ')' before 'idiv'
  __asm__ __volatile__( "\t"idiv   QWORD PTR [GX$]"    \n" :  :  : "cc", "memory
", "eax", "ebx", "ecx", "edx", "esp", "edi", "esi" );
                            ^
test.c:47:28: error: expected ':' or ')' before 'mov'
  __asm__ __volatile__( "\t"mov    [GX$], rdx"\n" :  :  : "cc", "memory", "eax",
 "ebx", "ecx", "edx", "esp", "edi", "esi" );
                            ^
test.c:48:28: error: expected ':' or ')' before 'mov'
  __asm__ __volatile__( "\t"mov    [GY$], rax"\n" :  :  : "cc", "memory", "eax",
 "ebx", "ecx", "edx", "esp", "edi", "esi" );
                            ^
test.c:49:28: error: expected ':' or ')' before '.' token
  __asm__ __volatile__( "\t".att_syntax prefix"\n" :  :  : "cc", "memory", "eax"
, "ebx", "ecx", "edx", "esp", "edi", "esi" );
                            ^
compiling C failed: 'c:\program files\freebasic\bin\win64\gcc.exe' terminated wi
th exit code 1
Where with my normal command line I get:

Code: Select all

C:\Users\User\FreeBASIC My\Asm>"c:\program files\freebasic\fbc" -w pendantic -v
-R -RR -C -s console test.bas
FreeBASIC Compiler - Version 1.00.0 (09-14-2014), built for win64 (64bit)
Copyright (C) 2004-2014 The FreeBASIC development team.
standalone
target:       win64, x86-64, 64bit
compiling:    test.bas -o test.c (main module)
compiling C:  c:\program files\freebasic\bin\win64\gcc.exe -m64 -march=x86-64 -S
 -nostdlib -nostdinc -Wall -Wno-unused-label -Wno-unused-function -Wno-unused-va
riable -Wno-unused-but-set-variable -Wno-main -Werror-implicit-function-declarat
ion -O0 -fno-strict-aliasing -frounding-math -fno-math-errno -fno-exceptions -fn
o-unwind-tables -fno-asynchronous-unwind-tables "test.c" -o "test.asm"
assembling:   c:\program files\freebasic\bin\win64\as.exe --64 --strip-local-abs
olute "test.asm" -o "test.o"
linking:      c:\program files\freebasic\bin\win64\ld.exe -m i386pep -o "test.ex
e" -subsystem console "c:\program files\freebasic\lib\win64\fbextra.x" --stack 1
048576,1048576 -s -L "c:\program files\freebasic\lib\win64" -L "." "c:\program f
iles\freebasic\lib\win64\crt2.o" "c:\program files\freebasic\lib\win64\crtbegin.
o" "c:\program files\freebasic\lib\win64\fbrt0.o" "test.o" "-(" -lfb -lgcc -lmsv
crt -lkernel32 -luser32 -lmingw32 -lmingwex -lmoldname -lgcc_eh "-)" "c:\program
 files\freebasic\lib\win64\crtend.o"
fxm
Moderator
Posts: 12082
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: 64-bit Support: Multiplication to 128bit

Post by fxm »

I asked albert to just verify that the '-asm intel' option was not used in the compiler command.
('asm att' option per default)
See http://www.freebasic.net/forum/viewtopi ... 74#p199274
Post Reply