/*************************************************************************
**                                                                      **
**  kbn.cxx                                                             **
**                                                                      **
**  C++ CLASS FOR BIG INTEGER ARITHMETIC                                **
**                                                                      **
**  Copyright (c)1996 Markku-Juhani O. Saarinen <mjos@math.jyu.fi>      **
**                                                                      **
*************************************************************************/

#include "kbn.h"

/*
**  copy(): kopioi lukuvektorin toiseen kbn:ään
*/

void kbn::copy (kbn_s *a, kbn_s *b)
{
    bcopy(a, b, sizeof(kbn_s) * (a[0] + 1) );
}

/*
**	sprint(): muuttaa luvun merkkijonoksi
*/

char *kbn::sprint (kbn_s *a)
{
    int i, t;
    char *pt;
    static char output_buffer[ (KBN_BASE_BITS/4)*KBN_VECTORSIZE + 5 ]; 
    const char hexconv[] = "0123456789ABCDEF";

    /* do a base hex conversion */
    
    pt = output_buffer;
    
    for (i=a[0]; i>=1; i--)
    {
    	t = a[i];
    	
 	    *pt++ = hexconv[(t >> 8) & 0xf];
 	    *pt++ = hexconv[(t >> 4) & 0xf];
 	    *pt++ = hexconv[t & 0xf];
    }
    *pt++ = '\0';

    /* skip the leading zeros */

    pt = output_buffer;
    while (*pt == '0')
    	pt++;
   
    return pt;
}

/*
**	setlong():  muuntaa longin kbn:ksi
*/

int kbn::setlong (unsigned long n, kbn_s *a)
{
    int  asiz;
    unsigned long t;

    asiz = 0;
    t = n;
    
    while ( t>0 )
    {
        a[++asiz] = t & KBN_BASE_MASK;
    	t >>= KBN_BASE_BITS;
    }
    
    a[0] = asiz;

    return 0;
}

/*
**  testbit():  testaa bitin
*/

int kbn::testbit (int bit)
{
    int offs, prec;

    offs = (bit / KBN_BASE_BITS) + 1;
    prec = bit % KBN_BASE_BITS;
    
    if (offs > vector[0] || offs < 1)
        return 0;
        
    return (vector[offs] & (1 << prec)) == 0 ? 0 : -1;
}

/*
**  setbit():   asettaa bitin 
*/

void kbn::setbit (int bit, int state)
{
    int i, offs, prec, siz;
    
    siz = vector[0];
    offs = (bit / KBN_BASE_BITS) + 1;
    prec = bit % KBN_BASE_BITS;

    if ( offs < 1 )
        return;
        
    if ( offs > siz )
    {
        if ( state )
        {
            for(i=siz+1; i<=offs; i++)
                vector[i] = 0;
            siz = offs;
        } else {
            return;
        }
    }
    
    if ( state )
        vector[offs] |= 1 << prec;
    else
        vector[offs] &= ~(1 << prec);

    while ( vector[siz] == 0 && siz > 0 )
        siz--;
    vector[0] = siz;
}

/*
**  cmp():  vertailu
**
**  -1      a > b
**  0       a = b
**  1       a < b
*/

int kbn::cmp(kbn_s *a, kbn_s *b)
{
    int asiz, bsiz, i, t;    
    
    asiz = a[0];
    while ( a[asiz] == 0 && asiz > 0 )
        asiz--;
    a[0] = asiz;

    bsiz = b[0];
    while ( b[bsiz] == 0 && bsiz > 0 )
        bsiz--;  
    b[0] = bsiz;
        
    if ( asiz < bsiz )
        return 1;
    if ( asiz > bsiz )
        return -1;

    for(i=asiz; i>0; i--)
    {
        t = ((int) a[i]) - ((int) b[i]);
        if ( t > 0 )
            return -1;
        if ( t < 0 )
            return 1; 
    
    }
    return 0;
}

/*
**	add(): yhteenlasku
*/

void kbn::add(kbn_s *a_in, kbn_s *b_in, kbn_s *c)
{
    int i, asiz, bsiz;
    kbn_l carry;
    kbn_s *a, *b;

    /* vaihdetaan a lyhyempi kuin b */

    if ( a_in[0] < b_in[0] )
    {
        a = a_in;
        b = b_in;
    } else {
        a = b_in;
        b = a_in;
    }

    asiz = a[0];
    bsiz = b[0];
    carry = 0;
    
    /* itse yhteenlaskurutiini */
    
    for (i=0; i<=asiz; i++)
    {
        carry += a[i] + b[i];
        c[i] = carry & KBN_BASE_MASK;
        carry >>= KBN_BASE_BITS;
    }
    while ( carry > 0 )
    {
        if (i<=bsiz)
            carry += b[i];
        c[i++] = carry;
        carry >>= KBN_BASE_BITS;
    }
    while( i<=bsiz )
        c[i++] = b[i];

    /* otetaan nollat veks lopusta */
    
    do {
        i--;
    } while( i>=1 && c[i] == 0 );

    /* kirjoitetaan pituus */

    c[0] = i;
}

/*
**  sub(): vähennyslasku
*/

void kbn::sub (kbn_s *a, kbn_s *b, kbn_s *c)
{
    int  asiz, bsiz, csiz, borrow;
        
    asiz = a[0];
    bsiz = b[0];
    borrow = 0;

    for(csiz=0; csiz < asiz; )    
    {
        csiz++;
        borrow = (c[csiz] = b[csiz] - a[csiz] - borrow) >= KBN_BASE ? 1 : 0;
        if ( borrow )
            c[csiz] &= KBN_BASE_MASK;    
    }

    while( csiz < bsiz )
    {
        csiz++;
        borrow = (c[csiz] = b[csiz] - borrow) >= KBN_BASE ? 1 : 0;
        if ( borrow )
            c[csiz] &= KBN_BASE_MASK;
    }
    
    if (borrow)
    {
        c[0] = 0;  
        return;
    }
    
    while ( c[csiz] == 0 && csiz > 0 )
        csiz--;
    
    c[0] = csiz;
        
    return;
}

/*
**  sqr(): neliöi luvun
*/

kbn& kbn::sqr ()
{
    int         i, j, k, vsiz, dsiz;
    kbn_s       *v, *d;
    kbn_l       carry, t;
    static kbn  ret_kbn;
   
    v = this->vector;
    d = ret_kbn.vector;
    vsiz = v[0];
    dsiz = 0;
    carry = 0;

    for (i=1; i<vsiz; i++)
    {
        t = 0;
        for (j=1, k=i; j < k; j++, k--)
            t += ((kbn_l) v[j]) * ((kbn_l) v[k]);
        carry += t << 1;
        if (j == k)
        {
            t = (kbn_l) v[j];
            carry += t*t;
 	    }
 	    d[++dsiz] = carry & KBN_BASE_MASK;
    	carry >>= KBN_BASE_BITS;   
    }   
   
    for (i=1; i<=vsiz; i++)
    {
        t = 0;
        for (j=i, k=vsiz; j < k; j++, k--)
            t += ((kbn_l) v[j]) * ((kbn_l) v[k]);
        carry += t << 1;
        if (j == k)
        {
            t = (kbn_l) v[j];
            carry += t*t;
 	    }
 	    d[++dsiz] = carry & KBN_BASE_MASK;
    	carry >>= KBN_BASE_BITS;           
    }
    
    while( carry>0 )
    {
     	d[++dsiz] = carry & KBN_BASE_MASK;
    	carry >>= KBN_BASE_BITS;   
    }
    
    while( d[dsiz] == 0 && dsiz > 0 )
        dsiz--;
    
    d[0] = dsiz;

    return ret_kbn;
}

/*
**	mul(): kertolasku
*/

void kbn::mul (kbn_s *a_in, kbn_s *b_in, kbn_s *d)
{
    int		    asiz, bsiz, dsiz;
    kbn_s       *a, *b;
    int		    i, j, k;
    kbn_l	    carry;
     
    /* tehokkuussyistä vaihdetaan b = pidempi luku */
     
    if ( a_in[0] > b_in[0] )
    {
        a = b_in;
        b = a_in;
    } else {
        a = a_in;
        b = b_in;
    }
    
    asiz = a[0];

    if ( asiz == 0 )
    {
        d[0] = 0;
        return; 
    }

    bsiz = b[0];
    dsiz = 0;
    carry = 0;
  
    /* kertolasku on kahdessa osassa */
 
    for (i=1; i<asiz; i++)
    {
    	for (j=1, k=i; j<=i; j++, k--)
    	    carry += ((kbn_l) a[j]) * ((kbn_l) b[k]);  	

 	    d[++dsiz] = carry & KBN_BASE_MASK;
    	carry >>= KBN_BASE_BITS;
    }
        
    for (; i < (asiz+bsiz); i++)
    {
    	for (j=asiz, k=i-asiz+1; k<=bsiz && j>=1; j--, k++)
    	    carry += ((kbn_l) a[j]) * ((kbn_l) b[k]);
   
    	d[++dsiz] = carry & KBN_BASE_MASK;
 	    carry >>= KBN_BASE_BITS; 
    }
    
    /* jos on "muistinumero", kirjotetaan se ulos */
        
    if ( carry > 0 )
    {
    	while ( carry > 0 )
    	{
    	    d[++dsiz] = carry & KBN_BASE_MASK;
    	    carry >>= KBN_BASE_BITS;
    	}
    } else {

        /* vaihtoehtoisesti pyritään napsimaan turhat nollat luvun */
        /* lopusta (eli siitä isosta päästä) */
    
        while (d[dsiz] == 0 && dsiz > 0)
            dsiz--;
    }
    
    /* kirjoitetaan vielä pituus */
   
    d[0] = dsiz;
}

/*
**  Pyöritys vasemmalle
*/ 

void kbn::rol(kbn_s *a, int no)
{
    int fulls, siz;

    /* t:ssä pitäisi olla ainakin 2*KBN_BASE_BITS bittiä */
    int i, t, part;

    if(a[0] == 0)
        return;

    fulls = (no / KBN_BASE_BITS) + 1;
    siz = a[0] + fulls;
    part = KBN_BASE_BITS - ( no % KBN_BASE_BITS );
        
    t = 0;
        
    /* vasemmalle pyöritys on implementoitu oikealle pyörityksenä */
    
    for(i=siz; i>fulls; i--)
    {
        t = (t << KBN_BASE_BITS) | a[i-fulls];
        a[i] = (t >> part) & KBN_BASE_MASK;     
    }
    
    if (i>0)
        a[i--] = ( t << (KBN_BASE_BITS - part) ) & KBN_BASE_MASK;  
    for(; i>0; i--)
        a[i] = 0;
    while(a[siz]==0 && siz>0)
        siz--;

    a[0] = siz;
}

/*
**  Bitin pyöritys oikealle
*/

void kbn::ror(kbn_s *a, int no)
{
    int fulls, part1, part2, siz, i, t1, t2;

    siz = a[0];
    if(siz == 0)
        return;

    fulls = (no / KBN_BASE_BITS) + 1;

    for(i=1; i<=fulls; i++)
        a[i+siz] = 0;
    siz -= fulls - 1;
    
    part1 = no % KBN_BASE_BITS;
    part2 = KBN_BASE_BITS - part1;

    t1 = a[fulls];

    for(i=1; i<=siz; i++)
    {
        t2 = t1;
        t1 = a[i+fulls];
        a[i] = ((t2 >> part1) | (t1 << part2)) & KBN_BASE_MASK;
    }
    
    while(a[siz] == 0 && siz>0)
        siz--;

    a[0] = siz;

}

/*
**  cntbits(): laskee bittien lukumäärän
*/

int kbn::cntbits(kbn_s *a)
{
    int asiz, prec;
    kbn_s t;
    
    asiz = a[0];
    while( a[asiz] == 0 && asiz < 0 )
        asiz--;
    
    prec = 0;
    if ( asiz > 0 )
    {     
        t = a[asiz] << 1;                 
        while (t < KBN_BASE)
        {
            t <<= 1;
            prec++;
        }
    } 

    a[0] = asiz;
    
    return ( asiz * KBN_BASE_BITS) - prec;
}

/*
**  mod(): Jakojäännös (modulo-operaattori)
*/

void kbn::mod(kbn_s *a, kbn_s *b, kbn_s *t)
{
    int tsiz, bsiz, i, j, adjust;
    long jaka, jako, vah;
    kbn_l oflo;
    
    copy(a, t);
    
    if ( b[0] == 0 || cmp(a, b) > 0 ) 
        return;
    
    adjust = KBN_BASE_BITS - 1 - ( (cntbits(b)-1) % KBN_BASE_BITS );
                
    rol(t, adjust);
    rol(b, adjust);
    tsiz = t[0];
    bsiz = b[0];

    jaka = b[bsiz] + 1;

    while( tsiz-bsiz > 0 )
    {
        jako = ( ( t[tsiz] << KBN_BASE_BITS ) | t[tsiz-1] ) / jaka;

        i = tsiz - bsiz - 1;
        vah = 0;
        for(j=1; j<=bsiz; j++)
        {
            vah += t[i+j] - (jako * b[j]);
            t[i+j] = vah & KBN_BASE_MASK;
            vah >>= KBN_BASE_BITS;
        }    

        oflo = (t[i+j]+vah) & KBN_BASE_MASK; 
   
        if(oflo) 
        {
            t[tsiz] = oflo;
        } else {
            tsiz--;
        }
    }
   
    t[0] = tsiz;    

    ror(b, adjust);
    ror(t, adjust);

    while( cmp(t, b) <= 0 )
        sub(b, t, t);
}

/*
**  addlong(); lisää long intin kbn:ään
*/

void kbn::addlong(kbn_s *a, long n)
{
    int i, asiz;
    kbn_l carry;

    carry = n;
    asiz = a[0];

    for(i=1; i<=asiz && carry > 0; i++)
    {
        carry += a[i];
        a[i] = carry & KBN_BASE_MASK;
        carry >>= KBN_BASE_BITS;
    }
    if ( carry > 0)
        a[++asiz] = carry;
    a[0] = asiz;
}


/*
**  Jakolasku
*/

void kbn::div(kbn_s *a, kbn_s *b, kbn_s *c)
{
    int tsiz, bsiz, i, j, csiz, cp, adjust;
    kbn_s t[KBN_VECTORSIZE];
    long jaka, jako, vah;
    kbn_l oflo;

    if ( b[0]==0 || cmp(a, b) > 0 ) 
    {
        c[0] = 0;
        return;
    }
    
    copy(a, t);
        
    adjust = KBN_BASE_BITS - ( (cntbits(b)-1) % KBN_BASE_BITS ) - 1;
     
    rol(t, adjust);
    rol(b, adjust);

    tsiz = t[0];
    bsiz = b[0];
    cp = KBN_VECTORSIZE-1;
    c[cp] = 0;
    c[cp-1] = 0;

    jaka = b[bsiz]+1;

    while( tsiz-bsiz > 0 )
    {
        jako = ( ( t[tsiz] << KBN_BASE_BITS ) | t[tsiz-1] ) / jaka;
              
        c[cp] += jako >> KBN_BASE_BITS;
        c[cp-1] += jako & KBN_BASE_MASK;
    
        i = tsiz - bsiz - 1;
        vah = 0;
        for(j=1; j<=bsiz; j++)
        {
            vah += t[i+j] - (jako * b[j]);
            t[i+j] = vah & KBN_BASE_MASK;
            vah >>= KBN_BASE_BITS;
        }    
        oflo = (t[i+j]+vah) & KBN_BASE_MASK; 
        
        if(oflo) 
        {
            t[tsiz] = oflo;
            oflo = 0;
        } else {
            cp--;
            tsiz--;
            c[cp-1] = 0;
        }
    }
   
    t[0] = tsiz;    

    ror(b, adjust);
    ror(t, adjust);
    
    for(i=cp, csiz=0; i<KBN_VECTORSIZE; i++)
        c[++csiz] = c[i];

    while(c[csiz]==0 && csiz>0)
        csiz--;
    c[0] = csiz;

    for(i=0; cmp(t, b) <= 0; i++ )
        sub(b, t, t);
        
    addlong(c, i);
    
}

/*
**  hexconv: muunnetaan heksastringi kbn-luvuksi
*/

void kbn::hexconv (char *in, kbn_s *pt)
{
    int i, j, ch, len;
    kbn_s n;

    i = strlen(in)-1;
    len = 0;
    
    while ( i>=0 )
    {
        n = 0;
        for(j=0; j < KBN_BASE_BITS && i >= 0; )
        {
            ch = in[i--];
            if(ch >= 'a' && ch <= 'f')
            {
                n |= (ch-'a'+10) << j;    
                j += 4;
            }
            if(ch >= 'A' && ch <= 'F')
            {
                n |= (ch-'A'+10) << j;
                j += 4;
            }
            if(ch >= '0' && ch <= '9')
            {
                n |= (ch-'0') << j;
                j += 4;
            }
        }
        pt[++len] = n;
    }
    
    pt[0] = len;

}

/*
**  konstruktori ja destruktori
*/

kbn::kbn ()  
{
    vector[0] = 0;
}

kbn::~kbn ()
{
    int i;
    
    for(i=0; i<=KBN_VECTORSIZE; i++)
        vector[i] = 0;
}

/*
**  funktiot
*/

/* 2 - kantainen logaritmi (bittien määrä - 1) */

int kbn::log2 ()
{
    return cntbits(vector)-1;
}

/* asettaa "pakatun" binääriluvun */

void kbn::load (unsigned char *pt, size_t len)
{
    int i, j, bits_in;
    kbn_l t;
     
    t = 0;
    j = 0;
    bits_in = 0;

    for(i=len-1; i>=0; i--)
    {
        t |= pt[i] << bits_in;
        bits_in += 8;

        
        while( bits_in >= KBN_BASE_BITS )
        {
            vector[++j] = t & KBN_BASE_MASK;
            t >>= KBN_BASE_BITS;
            bits_in -= KBN_BASE_BITS;
        }
        
        
    }

    if( bits_in > 0 )
        vector[++j] = t & ( (1<<bits_in) - 1);

    while ( vector[j] == 0 && j > 0 )
        j--;

    vector[0] = j;
}

/* tallettaa luvun "pakattuna" */

size_t kbn::save(unsigned char *pt)
{
    int i, j, len, bits_in;
    kbn_l t;

    j = 0;
    t = 0;
    len = vector[0];
    bits_in = (len * KBN_BASE_BITS) & 7;
  
    for(i=len; i>0; i--)
    {
        t <<= KBN_BASE_BITS;    
        t |= vector[i];
        bits_in += KBN_BASE_BITS;
    
        while ( bits_in >= 8 )
        {
            bits_in -= 8;
            pt[j++] = (t >> bits_in) & 0xff;
        }    
    }
    if (bits_in > 0)
        pt[j++] = t;
   
    return j;   
}

/*
**  streamioperaattorit
*/

ostream& operator<< (ostream& out, kbn &k)
{
    out << k.sprint(k.vector);
    return out;
}

istream& operator>> (istream& in, kbn &k)
{
    char buf[10000];
    in >> buf;   
    k.hexconv(buf, k.vector);
 
    return in;
}

/*
**  binääriset operaattorit
*/

kbn& kbn::operator+ (kbn& a)
{
    static kbn k;
    add(a.vector, this->vector, k.vector);
    return k;
}    

kbn& kbn::operator- (kbn& a)
{
    static kbn k;
    sub(a.vector, this->vector, k.vector);
    return k;
}    

kbn& kbn::operator* (kbn& a)
{
    static kbn k;
    mul(a.vector, this->vector, k.vector);
    return k;
}    

kbn& kbn::operator/ (kbn& a)
{
    static kbn k;
    div(this->vector, a.vector, k.vector);
    return k;
}    

kbn& kbn::operator% (kbn& a)
{
    static kbn k;
    mod(this->vector, a.vector, k.vector);
    return k;
}    

// bitinpyöritysoperaatiot

kbn& kbn::operator>> (long num)
{
    static kbn k;
    k = *this;
    ror(k.vector, num);
    return k;
}

kbn& kbn::operator<< (long num)
{
    static kbn k;
    k = *this;
    rol(k.vector, num);
    return k;
}


/*
**  vertailuoperaattorit
*/ 

int kbn::operator== (kbn& a)
{
    return cmp(this->vector, a.vector) == 0;
}

int kbn::operator!= (kbn& a){
    return cmp(this->vector, a.vector) != 0;
}

int kbn::operator< (kbn& a)
{
    return cmp(this->vector, a.vector) == 1;
}    

int kbn::operator<= (kbn& a)
{
    return cmp(this->vector, a.vector) != -1;
}    

int kbn::operator> (kbn& a)
{
    return cmp(this->vector, a.vector) == -1;
}    

int kbn::operator>= (kbn& a)
{
    return cmp(this->vector, a.vector) != 1;
}    
   
/*
**  sijoitusoperaattorit
*/

kbn& kbn::operator= (kbn &other)
{
    copy(other.vector, vector);
    return *this;
}

kbn& kbn::operator+= (kbn &other)
{
    add(other.vector, vector, vector);
    return *this;
}

kbn& kbn::operator-= (kbn &other)
{
    sub(other.vector, vector, vector);
    return *this;
}

kbn& kbn::operator*= (kbn &other)
{
    mul(other.vector, vector, vector);
    return *this;
}

kbn& kbn::operator/= (kbn &other)
{
    div(vector, other.vector, vector);
    return *this;
}

kbn& kbn::operator%= (kbn &other)
{
    mod(vector, other.vector, vector);
    return *this;
}

kbn& kbn::operator<<= (long num)
{
    rol(vector, num);
    return *this;
}

kbn& kbn::operator>>= (long num)
{
    ror(vector, num);
    return *this;
}

/*
**  sijoitusoperaattori; long int
*/

kbn& kbn::operator= (long num)
{
    setlong(num, vector);
    return *this;
}

/*
**  1 operandin operaattorit
*/

kbn& kbn::operator++ ()
{
    addlong(vector, 1);
    return *this;
}    

kbn& kbn::operator-- ()
{
    static kbn_s t[2] = {1, 1};
    sub(t, vector, vector);
    return *this;
}    

kbn& kbn::operator~ ()
{
    int i;
    
    for(i=vector[0]; i > 0; i--) 
        vector[i] ^= KBN_BASE_MASK;
    
    return *this;
}