64-bit Support: Multiplication to 128bit
-
- Posts: 62
- Joined: Nov 02, 2013 14:57
64-bit Support: Multiplication to 128bit
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.
-
- Site Admin
- Posts: 6323
- Joined: Jul 05, 2005 17:32
- Location: Manchester, Lancs
Re: 64-bit Support: Multiplication to 128bit
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..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.
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.
Re: 64-bit Support: Multiplication to 128bit
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)
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)
-
- Posts: 62
- Joined: Nov 02, 2013 14:57
Re: 64-bit Support: Multiplication to 128bit
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.
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.
Re: 64-bit Support: Multiplication to 128bit
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)
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)
Re: 64-bit Support: Multiplication to 128bit
@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.
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.
-
- Site Admin
- Posts: 6323
- Joined: Jul 05, 2005 17:32
- Location: Manchester, Lancs
Re: 64-bit Support: Multiplication to 128bit
Broadly speaking, every conceivable method of cryptography involves "math" of some sort.albert wrote:Crypto using math can pretty much be decyphered by the CIA
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.
Re: 64-bit Support: Multiplication to 128bit
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.
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.
Re: 64-bit Support: Multiplication to 128bit
(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)dkl wrote:Adding an int128 type could be interesting,
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) .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.
And you can use 128-bit fses on 32-bit, and time doesn't depend on architecture....
Re: 64-bit Support: Multiplication to 128bit
This example (done under adverse conditions so I'm not sure that it's entirely correct):stephanbrunker wrote:I have no clue about assembler programming, but I've read here...
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
Code: Select all
0000000000000002
0000000000000010
00000000000000000000000000000020
00000000000000000000000000000010
Re: 64-bit Support: Multiplication to 128bit
@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
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
Re: 64-bit Support: Multiplication to 128bit
Albert,
I have no way to check this ATM, but I suspect that you are trying to compile with the 32-bit compiler.
I have no way to check this ATM, but I suspect that you are trying to compile with the 32-bit compiler.
Re: 64-bit Support: Multiplication to 128bit
And don't compile with option '-asm intel'.
Re: 64-bit Support: Multiplication to 128bit
I'm not sure exactly what you mean, but I don't use the -asm intel option. Here is my command line:fxm wrote:And don't compile with option '-asm intel'.
Code: Select all
"c:\program files\freebasic\fbc" -w pendantic -v -R -RR -C -s console test.bas
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
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"
Re: 64-bit Support: Multiplication to 128bit
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
('asm att' option per default)
See http://www.freebasic.net/forum/viewtopi ... 74#p199274