| 1 | // -*- Mode: C -*-
|
|---|
| 2 | //
|
|---|
| 3 | // Cforall Version 1.0.0 Copyright (C) 2020 University of Waterloo
|
|---|
| 4 | //
|
|---|
| 5 | // The contents of this file are covered under the licence agreement in the
|
|---|
| 6 | // file "LICENCE" distributed with Cforall.
|
|---|
| 7 | //
|
|---|
| 8 | // bitmanip.hfa --
|
|---|
| 9 | //
|
|---|
| 10 | // Author : Peter A. Buhr
|
|---|
| 11 | // Created On : Sat Mar 14 18:12:27 2020
|
|---|
| 12 | // Last Modified By : Peter A. Buhr
|
|---|
| 13 | // Last Modified On : Mon Mar 16 14:28:46 2020
|
|---|
| 14 | // Update Count : 49
|
|---|
| 15 | //
|
|---|
| 16 |
|
|---|
| 17 | #pragma once
|
|---|
| 18 |
|
|---|
| 19 | // Reference: Bit Twiddling Hacks: http://graphics.stanford.edu/%7Eseander/bithacks.html#CountBitsSetNaive
|
|---|
| 20 |
|
|---|
| 21 | // Bits are numbered 1-N.
|
|---|
| 22 |
|
|---|
| 23 | #include <assert.h>
|
|---|
| 24 |
|
|---|
| 25 | static inline {
|
|---|
| 26 | // Count leading 0 bits.
|
|---|
| 27 | 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__; }
|
|---|
| 28 | 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__; }
|
|---|
| 29 | unsigned int cl0( unsigned int n ) { return n != 0 ? __builtin_clz( n ) : sizeof(n) * __CHAR_BIT__; }
|
|---|
| 30 | unsigned int cl0( unsigned long int n ) { return n != 0 ? __builtin_clzl( n ) : sizeof(n) * __CHAR_BIT__; }
|
|---|
| 31 | unsigned int cl0( unsigned long long int n ) { return n != 0 ? __builtin_clzll( n ) : sizeof(n) * __CHAR_BIT__; }
|
|---|
| 32 |
|
|---|
| 33 | // Count trailing 0 bits.
|
|---|
| 34 | unsigned int ct0( unsigned char n ) { return n != 0 ? __builtin_ctz( n ) : sizeof(n) * __CHAR_BIT__; }
|
|---|
| 35 | unsigned int ct0( unsigned short int n ) { return n != 0 ? __builtin_ctz( n ) : sizeof(n) * __CHAR_BIT__; }
|
|---|
| 36 | unsigned int ct0( unsigned int n ) { return n != 0 ? __builtin_ctz( n ) : sizeof(n) * __CHAR_BIT__; }
|
|---|
| 37 | unsigned int ct0( unsigned long int n ) { return n != 0 ? __builtin_ctzl( n ) : sizeof(n) * __CHAR_BIT__; }
|
|---|
| 38 | unsigned int ct0( unsigned long long int n ) { return n != 0 ? __builtin_ctzll( n ) : sizeof(n) * __CHAR_BIT__; }
|
|---|
| 39 |
|
|---|
| 40 | // Count all 1 bits.
|
|---|
| 41 | unsigned int ca1( unsigned char n ) { return __builtin_popcount( n ); }
|
|---|
| 42 | unsigned int ca1( unsigned short int n ) { return __builtin_popcount( n ); }
|
|---|
| 43 | unsigned int ca1( unsigned int n ) { return __builtin_popcount( n ); }
|
|---|
| 44 | unsigned int ca1( unsigned long int n ) { return __builtin_popcountl( n ); }
|
|---|
| 45 | unsigned int ca1( unsigned long long int n ) { return __builtin_popcountll( n ); }
|
|---|
| 46 |
|
|---|
| 47 | // Count all 0 bits.
|
|---|
| 48 | unsigned int ca0( unsigned char n ) { return sizeof(n) * __CHAR_BIT__ - __builtin_popcount( n ); }
|
|---|
| 49 | unsigned int ca0( unsigned short int n ) { return sizeof(n) * __CHAR_BIT__ - __builtin_popcount( n ); }
|
|---|
| 50 | unsigned int ca0( unsigned int n ) { return sizeof(n) * __CHAR_BIT__ - __builtin_popcount( n ); }
|
|---|
| 51 | unsigned int ca0( unsigned long int n ) { return sizeof(n) * __CHAR_BIT__ - __builtin_popcountl( n ); }
|
|---|
| 52 | unsigned int ca0( unsigned long long int n ) { return sizeof(n) * __CHAR_BIT__ - __builtin_popcountll( n ); }
|
|---|
| 53 |
|
|---|
| 54 | // Find least significiant set bit. (ffs)
|
|---|
| 55 | unsigned int fls( unsigned int n ) { return __builtin_ffs( n ); }
|
|---|
| 56 | unsigned int fls( unsigned long int n ) { return __builtin_ffsl( n ); }
|
|---|
| 57 | unsigned int fls( unsigned long long int n ) { return __builtin_ffsll( n ); }
|
|---|
| 58 |
|
|---|
| 59 | // Find most significiant set bit.
|
|---|
| 60 | unsigned int fms( unsigned char n ) { return n != 0 ? sizeof(unsigned int) * __CHAR_BIT__ - __builtin_clz( n ) : 0; }
|
|---|
| 61 | unsigned int fms( unsigned short int n ) { return n != 0 ? sizeof(unsigned int) * __CHAR_BIT__ - __builtin_clz( n ) : 0; }
|
|---|
| 62 | unsigned int fms( unsigned int n ) { return n != 0 ? sizeof(n) * __CHAR_BIT__ - __builtin_clz( n ) : 0; }
|
|---|
| 63 | unsigned int fms( unsigned long int n ) { return n != 0 ? sizeof(n) * __CHAR_BIT__ - __builtin_clzl( n ) : 0; }
|
|---|
| 64 | unsigned int fms( unsigned long long int n ) { return n != 0 ? sizeof(n) * __CHAR_BIT__ - __builtin_clzll( n ) : 0; }
|
|---|
| 65 |
|
|---|
| 66 | // Check for power of 2
|
|---|
| 67 | bool pow2( unsigned long int value ) {
|
|---|
| 68 | return (value & (value - 1)) == 0; // clears bits below value, rounding down to the next lower multiple of value
|
|---|
| 69 | } // pow2
|
|---|
| 70 |
|
|---|
| 71 | // Returns value aligned at the floor of align.
|
|---|
| 72 | unsigned long int floor( unsigned long int value, unsigned long int align ) {
|
|---|
| 73 | assert( pow2( align ) );
|
|---|
| 74 | return value & -align; // clear bits above or equal to align, giving value % align
|
|---|
| 75 | } // floor
|
|---|
| 76 |
|
|---|
| 77 | // Returns value aligned at the ceiling of align.
|
|---|
| 78 | unsigned long int ceiling( unsigned long int value, unsigned long int align ) {
|
|---|
| 79 | assert( pow2( align ) );
|
|---|
| 80 | return -floor( -value, align ); // negate, round down, negate is the same as round up
|
|---|
| 81 | } // ceiling
|
|---|
| 82 | }
|
|---|
| 83 |
|
|---|
| 84 | // Local Variables: //
|
|---|
| 85 | // tab-width: 4 //
|
|---|
| 86 | // End: //
|
|---|
