flat assembler
Message board for the users of flat assembler.

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

Author
Thread Post new topic Reply to topic
bitRAKE



Joined: 21 Jul 2003
Posts: 3486
Location: vpcmipstrm
bitRAKE
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 Wink
; 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,\
0xF06AD7AE9717877E,0x85839D6EFFBD7DC6,0x64D325D1C5371682,0xCADD0CCCFDFFBBE1,\
0x626E33B8D04B4331,0xBBF73C790D94F79D,0x471C4AB3ED3D82A5,0xFEC507705E4AE6E5,\
0xE73A9B91F3AA4DB2,0x87AE44F332E923A7,0x3CB91648E428E975,0xA3781EB01B49D867,\
0x4FA1508419E0EAA4,0x038B352D9BAD30F4,0x485B71A8EF64452A,0x0DD40DC8CB8F9A2D,\
0x4C514F1B229DCAA2,0x22AC268E9666E4A8,0x66769145F5F5880A,0x9D0ACD3B9E8C682F,\
0x4F810320ABEB9403,0x4E70F21608C061AB,0x1C1CAEF1EBDCEFBC,0x72134ECF06ED82BF    
... now we can do the proper AVX512 version of ShiShua.

_________________
¯\(°_o)/¯ unlicense.org
Post 29 May 2022, 15:03
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3486
Location: vpcmipstrm
bitRAKE
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)/¯ unlicense.org
Post 03 Aug 2022, 00:07
View user's profile Send private message Visit poster's website Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 18844
Location: In your JS exploiting you and your system
revolution
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.
Post 03 Aug 2022, 01:38
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.