/*
 * =====================================================================================
 *
 *       Filename:  test.cpp
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  21/06/2009 09:56:17
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  John Ryland (jryland), jryland@xiaofrog.com
 *        Company:  InvertedLogic
 *
 * =====================================================================================
 */

#include <stdio.h>
#include <limits.h>


#define bitsof(type)        ((sizeof(type) * CHAR_BIT)
#define INTEGER_BITS        (sizeof(int) * CHAR_BIT)
#define INTEGER_MSB         (INTEGER_BITS - 1)


#define ARCH_X86            1
#define ARCH_ARM            0
#define ARCH_PPC            0
#define ARCH_SH3            0


unsigned int integerAbs(int number)
{
    const int mask = number >> sizeof(int) * CHAR_BIT - 1;
    return (unsigned int)((number + mask) ^ mask);
    //return (unsigned int)((number ^ mask) - mask);
}


// if number < 0 then returns -1 else 0
inline int integerSign0(int number)
{
    int sign;
    // Both methods of calculating the sign of the number are portable, however efficency is different on different architectures
#ifdef ARCH_X86
    //sign = -(int)((unsigned int)((int)number >> INTEGER_MSB));
    sign = number >> (sizeof(int) * CHAR_BIT - 1); 
#else
    sign = -(number < 0);  // if number < 0 then -1, else 0.
#endif
    return sign;
}


// if number < 0 then returns -1 else +1
inline int integerSign1(int number)
{
    int sign;
    sign = +1 | (number >> (sizeof(int) * CHAR_BIT - 1));
    return sign;
}


// 32-bit method
//      for (int count = 0; number; number >>= 1) count += number & 1;
inline unsigned int integerBitsSet(unsigned int number)
{
    number = number - ((number >> 1) & 0x55555555);
    number = (number & 0x33333333) + ((number >> 2) & 0x33333333);
    return ((number + (number >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}


inline unsigned int integerParity(unsigned int number)
{
    number ^= number >> 16;
    number ^= number >> 8;
    number ^= number >> 4;
    number &= 0xf;
    return (0x6996 >> number) & 1;
}

#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))


inline unsigned char byteReverseBits(unsigned char number)
{
    return ((number * 0x0802LU & 0x22110LU) | (number * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16; 
}


// LSB bit is position 0
// MSB bit is position 31
inline unsigned int integerMSB(unsigned int number)
{
#if 1
    int r;          // result goes here
    static const int MultiplyDeBruijnBitPosition[32] = 
    {
        0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    };
    unsigned v = number;
    v |= v >> 1; // first round down to power of 2 
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v = (v >> 1) + 1;
    return MultiplyDeBruijnBitPosition[(unsigned int)(v * 0x077CB531U) >> 27];
/*

    unsigned int r; // result of log2(v) will go here
    unsigned int shift;
    r =     (number > 0xFFFF) << 4; number >>= r;
    shift = (number > 0xFF  ) << 3; number >>= shift; r |= shift;
    shift = (number > 0xF   ) << 2; number >>= shift; r |= shift;
    shift = (number > 0x3   ) << 1; number >>= shift; r |= shift;
    r |= (number >> 1);
    return r;
*/

/*
    // Improved Idea, but not quite working yet, should reduce operation by one cycle
    unsigned int msb = 0;
    const unsigned int mask[5] = { 0xFFFF0000, 0xFF00FF00, 0xF0F0F0F0, 0xCCCCCCCC, 0xAAAAAAAA };
    for (int i = 0; i < 5; i++) {
        unsigned int t = number & mask[i];
        int x = 

        int sign = -(t < 0);  // if number < 0 then -1, else 0.
        //int sign = (-(int)t) >> 31;
        int sign2 = -sign;
        //int sign = 0;
        if ( t )
            sign2 = i;//sign * i;
        else
            sign2 = -1;//sign;//sign * i;

        //int sign = (-(int)t) >> 31;
        //sign = -sign;
        
        msb += (16 >> (sign2));

//        number = number + t - number*sign;

        if ( t ) {
//            msb += (16 >> i);
            number = t;
  //      } else {
  //          number = number;
        }

//      msb += (number & mask[i]) ? (16>>i) : 0;
    }
    return msb;
*/
#else
    // Original code for above but slightly less efficient
    unsigned int msb = 0;
    const int mask[5] = { 65536, 256, 16, 4, 2 };
    for (int i = 0; i < 5; i++)
        msb += (number >= (mask[i] << msb)) ? (16 >> i) : 0;
    return msb;
#endif
}


inline int integerMin(int x, int y)
{
    return (x < y) ? x : y;
    //return y ^ ((x ^ y) & -(x < y));
    //return y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)));
}


inline int integerMax(int x, int y)
{
    return (x < y) ? y : x;
    //return x ^ ((x ^ y) & -(x < y));
    //return x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)));
}


inline unsigned int countRightZeros0(unsigned int v)
{
if (!v) return 31;
if (v & 0x1) return 0;
if (v & 0x2) return 1;
/*
if (v & 0x4) return 2;
if (v & 0x8) return 3;
if (v & 0x10) return 4;
if (v & 32) return 5;
if (v & 64) return 6;
if (v & 128) return 7;
if (v & 512) return 9;
*/
v = v - (v & (v - 1)); // LSB position
int
r  = ((v & 0xFFFF0000)!=0) << 4;
r |= ((v & 0xFF00FF00)!=0) << 3;
r |= ((v & 0xF0F0F0F0)!=0) << 2;
r |= ((v & 0xCCCCCCCC)!=0) << 1;
r |= ((v & 0xAAAAAAAA)!=0);
/*
r  = ((unsigned int)-(int)(v & 0xFFFF0000) >> 31) << 4;
r |= ((unsigned int)-(int)(v & 0xFF00FF00) >> 31) << 3;
r |= ((unsigned int)-(int)(v & 0xF0F0F0F0) >> 31) << 2;
r |= ((unsigned int)-(int)(v & 0xCCCCCCCC) >> 31) << 1;
r |= ((unsigned int)-(int)(v & 0xAAAAAAAA) >> 31);
*/
return r;
}

inline unsigned int countRightZeros1(unsigned int v)
{
    unsigned int c;     // c will be the number of zero bits on the right,
    // so if v is 1101000 (base 2), then c will be 3
    // NOTE: if 0 == v, then c = 31.
    if (v & 0x1) 
    {
        // special case for odd v (assumed to happen half of the time)
        c = 0;
    }
    else
    {
        c = 1;
        if ((v & 0xffff) == 0) 
        {  
            v >>= 16;  
            c += 16;
        }
        if ((v & 0xff) == 0) 
        {  
            v >>= 8;  
            c += 8;
        }
        if ((v & 0xf) == 0) 
        {  
            v >>= 4;
            c += 4;
        }
        if ((v & 0x3) == 0) 
        {  
            v >>= 2;
            c += 2;
        }
        c -= v & 0x1;
    }   
    return c;
}



bool test_integerMSB(unsigned int number)
{
    unsigned int result = integerMSB(number);
    //printf("integerMSB for %i is %i.\n", number, result);
    if (number == 0 && result == 0)
        return true;
    bool okay = number & (1 << result); // Check it contains this MSB bit
    if (!okay) {
        printf("integerMSB failed for %i, the returned MSB (%i) is not present.\n", number, result);
        if (number > 10)
        return okay;
    }
    unsigned int mask = 0;
    for (int i = 0; i <= result; i++)
        mask |= 1 << i;
    okay = !(number & ~mask); // Check no other bits higher than the MSB bit
    if (!okay)
        printf("integerMSB failed for %i, the returned MSB (%i) is not the highest.\n", number, result);
        if (number < 10)
            return true;
    return okay;
}


int main(int argc, char *argv[])
{
    int result;
    const float percentOfInts = 1.0f / 42949672.0f;
    #if 0
    for (unsigned int i = 0; i < UINT_MAX; i++) {
        if ( (i & 0x1FFFFF) == 1 ) {
            printf("%.2f%%\r", float(i) * percentOfInts);
            fflush(stdout);
        }
        int r0 = countRightZeros0(i);
        int r1 = countRightZeros1(i);
        if ( r0 != r1 ) {
            printf("countRightZeros for %i is %i not %i.\n", i, r1, r0);
            return 0;
        }
        /*
        result += integerMSB(i);
        if ( !test_integerMSB(i) ) {
            result = integerMSB(i);
            printf("integerMSB for %i is %i.\n", i, result);
            return 0;
        }
        */
    }
    #endif
    printf("Doing timing for 0\n");
    for (unsigned int i = 0; i < UINT_MAX; i++) {
        if ( (i & 0x1FFFFF) == 1 ) {
            printf("%.2f%%\r", float(i) * percentOfInts);
            fflush(stdout);
        }
        result += countRightZeros0(i);
    }
    /*
    printf("Doing timing for 1\n");
    for (unsigned int i = 0; i < UINT_MAX; i++) {
        if ( (i & 0x1FFFFF) == 1 ) {
            printf("%.2f%%\r", float(i) * percentOfInts);
            fflush(stdout);
        }
        result += countRightZeros1(i);
    }
    */
    return result;

    printf("result: %i\n", integerSign0(1234));
    printf("result: %d\n", integerSign0(-1234));
    printf("result: %i\n", integerSign0(0));
    printf("result: %i\n", -1);
    return 0;
}