clear

// 巴雷特模乘原理

a       = dup( 48, 66 )
b       = dup( 48, 55 )
m       = dup( 48, 36 )

// 要求a * b mod m
// 先计算a * b
ab      = big_mul( $a, $b )

// 求m的位数
k       = getbit_length( $m )
// 缩小一点，然后放大，要求0x10^(k-1)<=m<0x10^k
k       = div( $k, 04 )
k       = sub( $k, 01 )

base    = shl( 01, int( 0x$k * 4 ) )

while $base < $m
    base    = shl( $base, 04 )
    k       = add( $k, 01 )
loop

bk      = shl( $base, int( 0x$k * 4 ) )

u       = big_div( $bk, $m )

// 去低位
t       = shr( $ab, int( ( ( 0x$k - 1 ) * 4 ) ) )

// 乘以u
t       = big_mul( $t, $u )

// 右移取整
t       = shr( $t, int( ( ( 0x$k + 1 ) * 4 ) ) )

t       = big_mul( $t, $m )

r       = big_sub( $ab, $t )

while $r >= $m
    r   = big_sub( $r, $m )
loop

r       = big_add( $r, 00 )

test    = big_mod_mul( $a, $b, $m )

if $test != $r
    ?
    pause
endif

end

int a = 0x1234;
int b = 0x41;
int k = getk( b );
int bk = 1 << ( 2 * k );
int u = bk / b;

// 去低位
int t = (a >> (k - 1));
// 乘u
t *= u;
// 右移取整
t >>= ( k + 1 );

int r = a - ( t * b );

while( r >= b )
    {
    r -= b;
    }