//  ============================================================
//
//  bits.cpp
//
//  Copyright 2002, Dennis Meilicke and Rene Peralta
//
//  ============================================================
//
//  Description:
//
//  Functions for determining the number of significant bits.
//  That is, determine the most significant bit that is set.
//
//  To do:
//
//  This should be moved to a 'traits' object...
//
//  ============================================================
#include <lnv3/ln3impl.h>


size_t
NumBits( digit_t x )
{
    if (x & 0xffff0000)
    {
        if (x & 0xff000000)
        {
            if (x & 0xf0000000)
            {
                if (x & 0xc0000000)
                    if (x & 0x80000000)
                        return 32;
                    else
                        return 31;
                    else
                        if (x & 0x20000000)
                            return 30;
                        else
                            return 29;
            }
            else 
                if (x & 0x0c000000)
                    if (x & 0x08000000)
                        return 28;
                    else
                        return 27;
                    else
                        if (x & 0x02000000)
                            return 26;
                        else
                            return 25;
        }
        else
            if (x & 0x00f00000)
            {
                if (x & 0x00c00000)
                    if (x & 0x00800000)
                        return 24;
                    else
                        return 23;
                    else
                        if (x & 0x00200000)
                            return 22;
                        else
                            return 21;
            }
            else
                if (x & 0x000c0000)
                {
                    if (x & 0x00080000)
                        return 20;
                    else
                        return 19;
                }
                else
                    if (x & 0x00020000)
                        return 18;
                    else
                        return 17;
    }
    else
        if (x & 0xff00)
        {
            if (x & 0xf000)
            {
                if (x & 0xc000)
                {
                    if (x & 0x8000)
                        return 16;
                    else
                        return 15;
                }
                else
                    if (x & 0x2000)
                        return 14;
                    else
                        return 13;
            }
            else
                if (x & 0x0c00)
                {
                    if (x & 0x0800)
                        return 12;
                    else
                        return 11;
                }
                else
                    if (x & 0x0200)
                        return 10;
                    else
                        return 9;
        }
        else
            if (x & 0x00f0)
            {
                if (x & 0x00c0)
                {
                    if (x & 0x0080)
                        return 8;
                    else
                        return 7;
                }
                else 
                    if (x & 0x0020)
                        return 6;
                    else
                        return 5; 
            }
            else
                if (x & 0x000c)
                {
                    if (x & 0x0008)
                        return 4;
                    else
                        return 3;
                }
                else
                    if (x & 0x0002)
                        return 2;
                    else
                        return 1;
                    
    return 0;
}


//  ============================================================


size_t
NumBits( const Base * const A )
{
    size_t ret = 0;
    if( A->size > 1 )
        ret += ( A->size - 1 ) * 8 * sizeof(digit_t);
    if( A->size > 0 )
        ret += NumBits( A->digit[ A->size - 1 ] );
    return ret;
}


//  ============================================================


void
And( Base *A, const Base * const B )
{
    A->size = min( A->size, B->size );

    for( size_t i=0 ; i<A->size ; i++ )
    {
        A->digit[ i ] &= B->digit[ i ];
    }

    //
    //  We may have caused one or more leading digits to become
    //  zero.  Adjust the size accordingly.
    //
    for( ; ( A->size ) && ( A->digit[ A->size - 1 ] == 0 ) ; A->size-- )
        ;
}


//  ============================================================


void
Or( Base *A, const Base * const B )
{
    size_t minSize = min( A->size, B->size );

    for( size_t i=0 ; i<minSize ; i++ )
    {
        A->digit[ i ] |= B->digit[ i ];
    }

    if( B->size > A->size )
    {
        for( size_t i=minSize ; i<B->size ; i++ )
            A->digit[ i ] = B->digit[ i ];
        A->size = B->size;
    }
}


//  ============================================================


void
Xor( Base *A, const Base * const B )
{
    size_t minSize = min( A->size, B->size );

    for( size_t i=0 ; i<minSize ; i++ )
    {
        A->digit[ i ] ^= B->digit[ i ];
    }

    if( B->size > A->size )
    {
        for( size_t i=minSize ; i<B->size ; i++ )
            A->digit[ i ] = B->digit[ i ];
        A->size = B->size;
    }

    //
    //  We may have caused one or more leading digits to become
    //  zero.  Adjust the size accordingly.
    //
    for( ; ( A->size ) && ( A->digit[ A->size - 1 ] == 0 ) ; A->size-- )
        ;
}


//  ============================================================


void
Not( Base *A )
{
    for( size_t i=0 ; i<A->size ; i++ )
    {
        A->digit[ i ] = ~A->digit[ i ];
    }

    //
    //  We may have caused one or more leading digits to become
    //  zero.  Adjust the size accordingly.
    //
    for( ; ( A->size ) && ( A->digit[ A->size - 1 ] == 0 ) ; A->size-- )
        ;
}


//  ============================================================


short
GetBit( const Base * const X, size_t bit )
//
//  Description
//
//  Return the 'i'th bit of the number.
//
{
    size_t index = bit / ( sizeof( digit_t ) * 8 );
    size_t shift = bit % ( sizeof( digit_t ) * 8 );
    digit_t bitMask = (shift) ? (1 << shift) : 1 ;
    return ( ( X->digit[ index ] & bitMask ) ? 1 : 0 );
}


//  ============================================================


void
SetBit( Base *X, size_t bit, short value )
{
    size_t index = bit / ( sizeof( digit_t ) * 8 );
    size_t shift = bit % ( sizeof( digit_t ) * 8 );
    digit_t bitMask = (shift) ? (1 << shift) : 1 ;
    if( value )
        X->digit[ index ] |= bitMask;
    else
        X->digit[ index ] &= (~bitMask);
    return;
}