//                               -*- Mode: C -*- 
// 
// Cforall Version 1.0.0 Copyright (C) 2020 University of Waterloo
// 
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// bitmanip.hfa -- 
// 
// Author           : Peter A. Buhr
// Created On       : Sat Mar 14 18:12:27 2020
// Last Modified By : Peter A. Buhr
// Last Modified On : Mon Mar 16 14:28:46 2020
// Update Count     : 49
// 

#pragma once

// Reference: Bit Twiddling Hacks: http://graphics.stanford.edu/%7Eseander/bithacks.html#CountBitsSetNaive

// Bits are numbered 1-N.

#include <assert.h>

static inline {
    // Count leading 0 bits.
    unsigned int cl0( unsigned char n ) { return n != 0 ? __builtin_clz( n ) - (sizeof(unsigned int) * __CHAR_BIT__ - sizeof(n) * __CHAR_BIT__) : sizeof(n) * __CHAR_BIT__; }
    unsigned int cl0( unsigned short int n ) { return n != 0 ? __builtin_clz( n ) - (sizeof(unsigned int) * __CHAR_BIT__ - sizeof(n) * __CHAR_BIT__) : sizeof(n) * __CHAR_BIT__; }
    unsigned int cl0( unsigned int n ) { return n != 0 ? __builtin_clz( n ) : sizeof(n) * __CHAR_BIT__; }
    unsigned int cl0( unsigned long int n ) { return n != 0 ? __builtin_clzl( n ) : sizeof(n) * __CHAR_BIT__; }
    unsigned int cl0( unsigned long long int n ) { return n != 0 ? __builtin_clzll( n ) : sizeof(n) * __CHAR_BIT__; }

    // Count trailing 0 bits.
    unsigned int ct0( unsigned char n ) { return n != 0 ? __builtin_ctz( n ) : sizeof(n) * __CHAR_BIT__; }
    unsigned int ct0( unsigned short int n ) { return n != 0 ? __builtin_ctz( n ) : sizeof(n) * __CHAR_BIT__; }
    unsigned int ct0( unsigned int n ) { return n != 0 ? __builtin_ctz( n ) : sizeof(n) * __CHAR_BIT__; }
    unsigned int ct0( unsigned long int n ) { return n != 0 ? __builtin_ctzl( n ) : sizeof(n) * __CHAR_BIT__; }
    unsigned int ct0( unsigned long long int n ) { return n != 0 ? __builtin_ctzll( n ) : sizeof(n) * __CHAR_BIT__; }

    // Count all 1 bits.
    unsigned int ca1( unsigned char n ) { return __builtin_popcount( n ); }
    unsigned int ca1( unsigned short int n ) { return __builtin_popcount( n ); }
    unsigned int ca1( unsigned int n ) { return __builtin_popcount( n ); }
    unsigned int ca1( unsigned long int n ) { return __builtin_popcountl( n ); }
    unsigned int ca1( unsigned long long int n ) { return __builtin_popcountll( n ); }

    // Count all 0 bits.
    unsigned int ca0( unsigned char n ) { return sizeof(n) * __CHAR_BIT__ - __builtin_popcount( n ); }
    unsigned int ca0( unsigned short int n ) { return sizeof(n) * __CHAR_BIT__ - __builtin_popcount( n ); }
    unsigned int ca0( unsigned int n ) { return sizeof(n) * __CHAR_BIT__ - __builtin_popcount( n ); }
    unsigned int ca0( unsigned long int n ) { return sizeof(n) * __CHAR_BIT__ - __builtin_popcountl( n ); }
    unsigned int ca0( unsigned long long int n ) { return sizeof(n) * __CHAR_BIT__ - __builtin_popcountll( n ); }

    // Find least significiant set bit. (ffs)
    unsigned int fls( unsigned int n ) { return __builtin_ffs( n ); }
    unsigned int fls( unsigned long int n ) { return __builtin_ffsl( n ); }
    unsigned int fls( unsigned long long int n ) { return __builtin_ffsll( n ); }

    // Find most significiant set bit.
    unsigned int fms( unsigned char n ) { return n != 0 ? sizeof(unsigned int) * __CHAR_BIT__ - __builtin_clz( n ) : 0; }
    unsigned int fms( unsigned short int n ) { return n != 0 ? sizeof(unsigned int) * __CHAR_BIT__ - __builtin_clz( n ) : 0; }
    unsigned int fms( unsigned int n ) { return n != 0 ? sizeof(n) * __CHAR_BIT__ - __builtin_clz( n ) : 0; }
    unsigned int fms( unsigned long int n ) { return n != 0 ? sizeof(n) * __CHAR_BIT__ - __builtin_clzl( n ) : 0; }
    unsigned int fms( unsigned long long int n ) { return n != 0 ? sizeof(n) * __CHAR_BIT__ - __builtin_clzll( n ) : 0; }

    // Check for power of 2
    bool pow2( unsigned long int value ) {
		return (value & (value - 1)) == 0;				// clears bits below value, rounding down to the next lower multiple of value
    } // pow2

    // Returns value aligned at the floor of align.
    unsigned long int floor( unsigned long int value, unsigned long int align ) {
		assert( pow2( align ) );
		return value & -align;							// clear bits above or equal to align, giving value % align
    } // floor

    // Returns value aligned at the ceiling of align.
    unsigned long int ceiling( unsigned long int value, unsigned long int align ) {
		assert( pow2( align ) );
		return -floor( -value, align );					// negate, round down, negate is the same as round up
    } // ceiling
}

// Local Variables: //
// tab-width: 4 //
// End: //