import { compare_alt } from './compare' ; import { equals } from './equals' ; import { modulo as mod } from './intdiv' ; import { select , select_alt } from './select' ; import { trim_zeroes_left } from './trim' ; param { Uint8Array } a param { Uint8Array } b returns { Uint8Array } export function add ( a , b ) { const out = new Uint8Array ( Math . max ( a . length , b . length ) ) ; let c = 0 ; for ( let i = out . length - 1 ; i >= 0 ; i -- ) { c += a [ i ] + b [ i ] ; out [ i ] = c & 0xff ; c >>>= 8 ; } return out ; } param { Uint8Array } a param { Uint8Array } b returns { Uint8Array } export function and ( a , b ) { if ( a . length !== b . length ) { throw new Error ( 'Both arrays must be of equal length' ) ; } const c = new Uint8Array ( a . length ) ; for ( let i = 0 ; i < c . length ; i ++ ) { c [ i ] = a [ i ] & b [ i ] ; } return c ; } param { Uint8Array } a returns { bigint } export function count_trailing_zero_bits ( a ) { let b = 0n ; let num = 0n ; let found = 0n ; let bit = 0 ; for ( let i = a . length - 1 ; i >= 0 ; i -- ) { for ( let j = 0 ; j < 8 ; j ++ ) { bit = ( a [ i ] >>> j ) & 1 ; num = ( ( BigInt ( - bit ) & b ) & ~ found ) ^ ( num & found ) ; found |= BigInt ( - bit ) ; b ++ ; } } return num ; } param { Uint8Array } a param { Uint8Array } b returns { Uint8Array } export function divide ( a , b ) { return division ( a , b ) [ 0 ] ; } param { Uint8Array } a param { Uint8Array } b returns { Uint8Array } export function gcd ( a , b ) { return xgcd ( a , b ) [ 1 ] ; } param { Uint8Array } num returns { boolean } export function is_nonzero ( num ) { let d = 0 ; for ( let i = num . length - 1 ; i >= 0 ; i -- ) { d |= num [ i ] ; } return d !== 0 ; } param { Uint8Array } y returns { number } export function lsb ( y ) { return y [ y . length - 1 ] & 1 ; } param { Uint8Array } x export function lshift1 ( x ) { let carry = 0 ; let tmp = 0 ; for ( let i = x . length - 1 ; i >= 0 ; i -- ) { tmp = x [ i ] ; x [ i ] = ( tmp << 1 ) | carry ; carry = ( tmp >>> 7 ) & 1 ; } } param { Uint8Array } a param { Uint8Array } b returns { Uint8Array } export function modulo ( a , b ) { return division ( a , b ) [ 1 ] ; } param { Uint8Array } a param { Uint8Array } x param { Uint8Array } m export function modPow ( a , x , m ) { const zero = new Uint8Array ( m . length + 1 ) ; const one = zero . slice ( ) ; one [ one . length - 1 ] = 1 ; const two = zero . slice ( ) ; two [ two . length - 1 ] = 2 ; let length = zero . length << 1 ; const mod = normalize ( m , length ) ; let result = normalize ( one , length ) ; let base = normalize ( a , length ) ; let e = normalize ( x , length ) ; let p ; while ( is_nonzero ( e ) ) { p = multiply ( result , base ) ; p = normalize ( modulo ( p , mod ) , length , true ) ; result = select_alt ( lsb ( e ) , p , result ) ; rshift1 ( e , true ) ; p = multiply ( base , base ) ; p = normalize ( modulo ( p , mod ) , length , true ) ; base = p ; } return normalize ( result , zero . length - 1 ) ; } param { Uint8Array } x param { Uint8Array } m export function modInverse ( x , m ) { const [ a , y ] = xgcd ( x , m ) ; const one = new Uint8Array ( x . length ) ; one [ one . length - 1 ] = 1 ; if ( ! equals ( one , y ) ) { throw new Error ( 'inverse does not exist' ) ; } return a ; } param { Uint8Array } x returns { number } export function msb ( x ) { return ( x [ 0 ] >>> 7 ) & 1 ; } param { Uint8Array } a param { Uint8Array } b param { Number ? } ops returns { Uint8Array } export function multiply ( a , b , ops ? ) { let z = new Uint8Array ( a . length + b . length ) ; let x = new Uint8Array ( z . length ) ; let y = new Uint8Array ( z . length ) ; x . set ( a , z . length - a . length ) ; y . set ( b , z . length - b . length ) ; if ( ! ops ) { ops = Math . max ( x . length , y . length ) << 3 ; } while ( ops > 0 ) { z = select_alt ( lsb ( y ) , add ( z , x ) , z ) ; lshift1 ( x ) ; rshift1 ( y ) ; ops -- ; } return z ; } param { Uint8Array } a param { number } l param { boolean } unsigned export function normalize ( a , l , unsigned ? ) { const out = new Uint8Array ( l ) ; const neg = unsigned ? 0x00 : ( ( - msb ( a ) ) & 0xff ) ; let j = a . length - 1 ; const tmp = new Int32Array ( 1 ) ; for ( let i = l - 1 ; i >= 0 ; i -- , j -- ) { tmp [ 0 ] = j >>> 31 ; tmp [ 0 ] *= - 1 ; const fill = ~ tmp [ 0 ] & 0xff ; const index = mod ( j , a . length ) & fill ; out [ i ] = ( a [ index ] & fill ) ^ ( neg & ~ fill ) ; } return out ; } param { Uint8Array } a param { Uint8Array } b returns { Uint8Array } export function or ( a , b ) { if ( a . length !== b . length ) { throw new Error ( 'Both arrays must be of equal length' ) ; } const c = new Uint8Array ( a . length ) ; for ( let i = 0 ; i < c . length ; i ++ ) { c [ i ] = a [ i ] | b [ i ] ; } return c ; } param { Uint8Array } a param { Uint8Array } n returns { Uint8Array } export function pow ( a , n ) { const one = new Uint8Array ( a . length ) ; one [ one . length - 1 ] = 1 ; let A = one . slice ( ) ; let S = a . slice ( ) ; let e = n . slice ( ) ; let Aprime ; let Sprime ; do { Aprime = multiply ( A , S ) ; A = select_alt ( lsb ( e ) , Aprime , normalize ( A , Aprime . length ) ) ; rshift1 ( e , true ) ; Sprime = multiply ( S , S ) ; S = select ( is_nonzero ( e ) , Sprime , normalize ( S , Sprime . length ) ) ; } while ( is_nonzero ( e ) ) ; return trim_zeroes_left ( A ) ; } param { Uint8Array } y param { boolean ? } unsigned export function rshift1 ( y , unsigned ? ) { let carry = unsigned ? 0 : msb ( y ) ; let tmp = 0 ; for ( let i = 0 ; i < y . length ; i ++ ) { tmp = y [ i ] & 1 ; y [ i ] = ( y [ i ] >>> 1 ) | ( carry << 7 ) ; carry = tmp ; } } param { Uint8Array } a param { bigint } e export function shift_left ( a , e ) { const out = new Uint8Array ( a . length ) ; let index = a . length - 1 - ( Number ( e >> 3n ) & 0x7fffffff ) ; const s = Number ( e & 7n ) ; const m = ( 1 << s ) - 1 ; let x = 0 ; let y = 0 ; let tmp = 0 ; let carry = 0 ; for ( let i = a . length - 1 ; i >= 0 ; index -- , i -- ) { x = ~ ( index >> 31 ) ; y = ( mod ( index , a . length ) & x ) ; tmp = ( a [ i ] >>> ( 8 - s ) ) & m ; out [ y ] = ( ( ( ( a [ i ] << s ) & 0xff ) | carry ) & x ) ^ ( out [ y ] & ~ x ) ; carry = tmp ; } return out ; } param { Uint8Array } a param { bigint } e export function shift_right ( a , e ) { const out = new Uint8Array ( a . length ) ; let index = ( Number ( e >> 3n ) & 0x7fffffff ) ; const s = Number ( e & 7n ) ; const m = ~ ( ( 1 << s ) - 1 ) ; let x = 0 ; let y = 0 ; let tmp = 0 ; let carry = 0 ; for ( let i = 0 ; i < a . length ; i ++ , index ++ ) { x = ~ ( ( a . length - index - 1 ) >> 31 ) ; y = ( mod ( index , a . length ) & x ) ; tmp = ( a [ i ] << ( 8 - s ) ) & m ; out [ y ] = ( ( ( ( a [ i ] >>> s ) & 0xff ) | carry ) & x ) ^ ( out [ y ] & ~ x ) ; carry = tmp ; } return out ; } param { Uint8Array } a param { Uint8Array } b returns { Uint8Array } export function sub ( a , b ) { const out = new Uint8Array ( Math . max ( a . length , b . length ) ) ; const c = new Int16Array ( 1 ) ; for ( let i = out . length - 1 ; i >= 0 ; i -- ) { c [ 0 ] += a [ i ] - b [ i ] ; out [ i ] = c [ 0 ] & 0xff ; c [ 0 ] >>= 8 ; } return out ; } param { Uint8Array } a param { Uint8Array } b returns { Uint8Array } export function xor ( a , b ) { if ( a . length !== b . length ) { throw new Error ( 'Both arrays must be of equal length' ) ; } const c = new Uint8Array ( a . length ) ; for ( let i = 0 ; i < c . length ; i ++ ) { c [ i ] = a [ i ] ^ b [ i ] ; } return c ; } param { bigint } a param { bigint } b returns { bigint } function minBigInt ( a , b ) { let d = b - a ; d = ( d >> 63n ) & d ; a += d ; return a ; } param { Uint8Array } x param { Uint8Array } y returns { Uint8Array [ ] } function xgcd ( x , y ) { if ( x . length !== y . length ) { throw new Error ( 'Normalize your Uint8Array lengths first' ) ; } const zero = new Uint8Array ( y . length ) ; const one = zero . slice ( ) ; one [ one . length - 1 ] = 1 ; const g = minBigInt ( count_trailing_zero_bits ( x ) , count_trailing_zero_bits ( y ) ) ; shift_right ( x , g ) ; shift_right ( y , g ) ; let u = x . slice ( ) ; let v = y . slice ( ) ; let A = one . slice ( ) ; let B = zero . slice ( ) ; let C = zero . slice ( ) ; let D = one . slice ( ) ; let bits ; let swap ; do { for ( bits = count_trailing_zero_bits ( u ) ; bits > 0n ; bits -- ) { rshift1 ( u ) ; swap = ( ~ lsb ( A ) & ~ lsb ( B ) ) & 1 ; A = select_alt ( swap , A , add ( A , y ) ) ; rshift1 ( A ) ; B = select_alt ( swap , B , sub ( B , x ) ) ; rshift1 ( B ) ; } for ( bits = count_trailing_zero_bits ( v ) ; bits > 0n ; bits -- ) { rshift1 ( v ) ; swap = ( ~ lsb ( C ) & ~ lsb ( D ) ) & 1 ; C = select_alt ( swap , C , add ( C , y ) ) ; rshift1 ( C ) ; D = select_alt ( swap , D , sub ( D , x ) ) ; rshift1 ( D ) ; } swap = ( 1 - ( compare_alt ( u , v ) [ 0 ] >>> 31 ) ) ; u = select_alt ( swap , sub ( u , v ) , u ) ; A = select_alt ( swap , sub ( A , C ) , A ) ; B = select_alt ( swap , sub ( B , D ) , B ) ; swap = 1 - swap ; v = select_alt ( swap , sub ( v , u ) , v ) ; C = select_alt ( swap , sub ( C , A ) , C ) ; D = select_alt ( swap , sub ( D , B ) , D ) ; } while ( is_nonzero ( u ) ) ; return [ C , shift_left ( v , g ) ] ; } param { Uint8Array } num param { Uint8Array } denom returns { Uint8Array } function division ( num , denom ) { if ( ! is_nonzero ( denom ) ) { throw new Error ( 'Division by zero' ) ; } const length = Math . max ( num . length , denom . length ) ; const zero = new Uint8Array ( length ) ; let bits = ( length << 3 ) - 1 ; let N = normalize ( num , length , true ) ; let D = normalize ( denom , length , true ) ; let Q = zero . slice ( ) ; let R = zero . slice ( ) ; let Qprime ; let Rprime ; let compared ; let swap ; let byte ; let b ; let i ; for ( i = 0 ; i <= bits ; i ++ ) { byte = i >>> 3 ; b = ( ( bits - i ) & 7 ) ; lshift1 ( R ) ; R [ R . length - 1 ] |= ( N [ byte ] >>> b ) & 1 ; compared = compare_alt ( R , D ) ; swap = ( 1 - ( compared [ 0 ] >>> 31 ) ) ; Rprime = sub ( R , D ) ; Qprime = Q . slice ( ) ; Qprime [ byte ] |= ( 1 << b ) ; R = select_alt ( swap , Rprime , R ) ; Q = select_alt ( swap , Qprime , Q ) ; } return [ Q , R ] ; }