kbn.cpp

来自「RSA C++源代码DEMO,附加DESMD5等众多算法」· C++ 代码 · 共 341 行

/*************************************************************************
**                                                                      **
**  kbn.cxx                                                             **
**                                                                      **
**  C++ CLASS FOR BIG INTEGER ARITHMETIC                                **
**                                                                      **
**  Copyright (c)1996 Markku-Juhani O. Saarinen <[e-mail]>      **
**                                                                      **
*************************************************************************/

#include "kbn.h"

/*     
**     copy
**  a ------> b
*/

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

/*
**	HEX print
*/

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";

    /* dec to 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;
}

/*
**	long ----> kbn
*/

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

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

    return 0;
}

/*
**  if bit is set return 0, else return -1
*/

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;
}

/*
**  set bit <=== state
*/

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;
}

/*
**  compare a and b
**
**  -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;
}

/*
**	a + b = c
*/

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] = (kbn_s)( 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;
}

/*
**  a - b = c
*/

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;
}

/*
**  kbn ^ kbn
*/

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] = (kbn_s)( 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] = (kbn_s)( carry & KBN_BASE_MASK );
    	carry >>= KBN_BASE_BITS;           
    }
    
    while( carry>0 )
    {
     	d[++dsiz] = (kbn_s)( carry & KBN_BASE_MASK );
    	carry >>= KBN_BASE_BITS;   
    }
    
    while( d[dsiz] == 0 && dsiz > 0 )
        dsiz--;
    
    d[0] = dsiz;

    return ret_kbn;
}

/*
**	a_in * b_in = d
*/

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