flat assembler
Message board for the users of flat assembler.

 Index > Macroinstructions > [fasmg] exotic constants ...
Author
bitRAKE

Joined: 21 Jul 2003
Posts: 3946
Location: vpcmipstrm
bitRAKE 29 May 2022, 15:03
I don't know what else to call them - exotic constants is an good as anything else I suppose. Many algorithms initialize a space with complex constants as a known basis to start some process. For example, we have SHA-256 - using the fractional square and cube roots of primes. Another example is ShiShua using phi (ϕ).

How would we generate these constants at compile-time? Or what if we want to use different constants for our own flavor of security-by-obscurity?
Code:
```calminstruction hex_nibble digit*, command: display
compute digit, 0FFh and '0123456789ABCDEF' shr (digit*8)
arrange command, command digit
assemble command
end calminstruction

calminstruction ROOT? result*, remainder*, N*
local rem, prox, bit, temp
compute rem, 0
check N = 0
jyes done

compute prox, 0
compute bit, 1 shl (((bsr N) + 1) and -2)

check N > 0
jyes more
arrange bit, =err 'square root of negative number'
assemble bit
exit
more:
compute temp, rem + bit + prox
check N < temp
compute rem, rem shr 1
jyes reduce
compute rem, rem + bit
compute prox, temp
reduce:
compute bit, bit shr 2
check bit
jyes more
done:
publish result, rem
compute rem, N - prox
publish remainder, rem
end calminstruction

; big integer broken into integer array
; little-endian, not efficient
; grain should be a power of two
calminstruction BIGHEX value*, grain:8, cmd:display
local awk, digit, big, k

compute         big, value

arrange         awk, cmd '0x'
assemble        awk

compute         k, grain shl 1
jump            nibs
next:   ; 32 bytes per line
check           (k - (grain shl 1)) and 63
jyes            same
arrange         awk, cmd ',\',10,'0x'
assemble        awk
jump            nibs
same:   arrange         awk, cmd ',0x'
assemble        awk
nibs:   compute         digit, (big shr ((k-1) shl 2)) and 0Fh
call            hex_nibble, digit, cmd
compute         k, k - 1
check           k and ((grain shl 1) - 1)
jyes            nibs
compute         k, k + (grain shl 2)
check           big shr ((k - (grain shl 1)) shl 2)
jyes            next
end calminstruction

; phi: square root of five, minus one; divided by two (scaled by bits bits)
macro ShiShua q:16
local t0, t1, bits
bits = q shl 6
ROOT t0, t1, (5 shl (bits+bits))
t0 = (t0 - (1 shl bits)) shr 1

; big-endian at the qword scale, but little-endian qwords (weird!)
t1 = 0
repeat q
t1 = (t1 shl 64) or (t0 and ((-1) bswap 8))
t0 = t0 shr 64
end repeat
BIGHEX t1
end macro
ShiShua 32    ```
... resulting in the needed constant data for ShiShua:
Code:
```0x9E3779B97F4A7C15,0xF39CC0605CEDC834,0x1082276BF3A27251,0xF86C6A11D0C18E95,\
0x2767F0B153D27B7F,0x0347045B5BF1827F,0x01886F0928403002,0xC1D64BA40F335E36,\
0x626E33B8D04B4331,0xBBF73C790D94F79D,0x471C4AB3ED3D82A5,0xFEC507705E4AE6E5,\
0xE73A9B91F3AA4DB2,0x87AE44F332E923A7,0x3CB91648E428E975,0xA3781EB01B49D867,\
0x4C514F1B229DCAA2,0x22AC268E9666E4A8,0x66769145F5F5880A,0x9D0ACD3B9E8C682F,\
0x4F810320ABEB9403,0x4E70F21608C061AB,0x1C1CAEF1EBDCEFBC,0x72134ECF06ED82BF    ```
... now we can do the proper AVX512 version of ShiShua.

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

Last edited by bitRAKE on 22 Oct 2023, 22:15; edited 1 time in total
29 May 2022, 15:03
bitRAKE

Joined: 21 Jul 2003
Posts: 3946
Location: vpcmipstrm
bitRAKE 03 Aug 2022, 00:07
More constants for our fixed point needs ...

This time we are using periodic continued fractions:
Code:
```; integer coefficient,
; constant coefficients,
; repeating coefficients,
; precision (fractional bits)
struc CFRACT a0*,a_const*,a_repeat*,N*
local error, h0,k0, h1,k1, c,r,a_n, h_n,k_n
h1 = 1
k1 = 0

h_n = a0
k_n = 1

n = 1
error = 1
while error <> 0
; resolve present a(n)
iterate c,a_const
if n <= %%
indx n
a_n = c
break
else
a_n = %%
iterate r,a_repeat
indx 1+((n-a_n-1) mod %%)
a_n = r
break
end iterate
end if
end iterate

h0 = h1
k0 = k1
h1 = h_n
k1 = k_n
h_n = a_n * h1 + h0
k_n = a_n * k1 + k0

error = (h_n shl N) / k_n - (h1 shl N) / k1
n = n + 1
end while
. = (h1 shl N) / k1
end struc

; SOME EXAMPLES:

; https://wikipedia.org/wiki/Golden_ratio
; https://oeis.org/A001622
golden  CFRACT 1, 1, 1, 64                      ; golden ratio

root2   CFRACT 1, 2, 2, 64                      ; square root of 2
root3   CFRACT 1, 1, <2,1>, 64                  ; square root of 3
root31  CFRACT 5, 1, <1,3,5,3,1,1,10,1>, 64     ; square root of 31
tan1    CFRACT 1, 1, <1,n>, 64                  ; tan(1)
e64     CFRACT 2, <1,2>, <1,1,(2*n+2)/3>, 64    ; euler constant to 64-bit

; see https://oeis.org/A001203 for more digits, no pattern known
pi      CFRACT 3, <7,15,1,292,1,1,1,2,1,3,1,14,2,1,1,2,2,2,2,1,84,2,1,1>,1, 64    ```
... easy enough to output the numerator and denominator, for MUL/DIV use.

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup
03 Aug 2022, 00:07
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20142
revolution 03 Aug 2022, 01:38
bitRAKE wrote:
Or what if we want to use different constants for our own flavor of security-by-obscurity?
Using other constants is certainly possible, but we have to be careful that the strength of the algorithm isn't weakened. Without trustworthy cryptanalysis of the new values showing the strength you might end up making it worse.
03 Aug 2022, 01:38
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum