Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/bitmanip.hfa

    r66f3bae r03eabf4  
    1111// Created On       : Sat Mar 14 18:12:27 2020
    1212// Last Modified By : Peter A. Buhr
    13 // Last Modified On : Sun Apr 19 22:29:58 2020
    14 // Update Count     : 121
     13// Last Modified On : Mon Mar 16 14:28:46 2020
     14// Update Count     : 49
    1515//
    1616
    … …  
    2121// Bits are numbered 1-N.
    2222
    23 //#include <assert.h>
    24 
    25 #define __bitsizeof( n ) (sizeof(n) * __CHAR_BIT__)
     23#include <assert.h>
    2624
    2725static inline {
    28         // Count leading 0 bits.
    29         unsigned int leading0s( unsigned char n ) { return n != 0 ? __builtin_clz( n ) - (__bitsizeof(unsigned int) - __bitsizeof(n)) : __bitsizeof(n); }
    30         unsigned int leading0s( unsigned short int n ) { return n != 0 ? __builtin_clz( n ) - (__bitsizeof(unsigned int) - __bitsizeof(n)) : __bitsizeof(n); }
    31         unsigned int leading0s( unsigned int n ) { return n != 0 ? __builtin_clz( n ) : __bitsizeof(n); }
    32         unsigned int leading0s( unsigned long int n ) { return n != 0 ? __builtin_clzl( n ) : __bitsizeof(n); }
    33         unsigned int leading0s( unsigned long long int n ) { return n != 0 ? __builtin_clzll( n ) : __bitsizeof(n); }
     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__; }
    3432
    35         // Count trailing 0 bits.
    36         unsigned int trailing0s( unsigned char n ) { return n != 0 ? __builtin_ctz( n ) : __bitsizeof(n); }
    37         unsigned int trailing0s( unsigned short int n ) { return n != 0 ? __builtin_ctz( n ) : __bitsizeof(n); }
    38         unsigned int trailing0s( unsigned int n ) { return n != 0 ? __builtin_ctz( n ) : __bitsizeof(n); }
    39         unsigned int trailing0s( unsigned long int n ) { return n != 0 ? __builtin_ctzl( n ) : __bitsizeof(n); }
    40         unsigned int trailing0s( unsigned long long int n ) { return n != 0 ? __builtin_ctzll( n ) : __bitsizeof(n); }
     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__; }
    4139
    42         // Count all 1 bits.
    43         unsigned int all1s( unsigned char n ) { return __builtin_popcount( n ); }
    44         unsigned int all1s( unsigned short int n ) { return __builtin_popcount( n ); }
    45         unsigned int all1s( unsigned int n ) { return __builtin_popcount( n ); }
    46         unsigned int all1s( unsigned long int n ) { return __builtin_popcountl( n ); }
    47         unsigned int all1s( unsigned long long int n ) { return __builtin_popcountll( n ); }
     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 ); }
    4846
    49         // Count all 0 bits.
    50         unsigned int all0s( unsigned char n ) { return __bitsizeof(n) - __builtin_popcount( n ); }
    51         unsigned int all0s( unsigned short int n ) { return __bitsizeof(n) - __builtin_popcount( n ); }
    52         unsigned int all0s( unsigned int n ) { return __bitsizeof(n) - __builtin_popcount( n ); }
    53         unsigned int all0s( unsigned long int n ) { return __bitsizeof(n) - __builtin_popcountl( n ); }
    54         unsigned int all0s( unsigned long long int n ) { return __bitsizeof(n) - __builtin_popcountll( n ); }
     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 ); }
    5553
    56         // Find least significiant zero bit. (ffs)
    57         unsigned int low0( unsigned char n ) { return __builtin_ffs( (typeof(n))~n ); }
    58         unsigned int low0( unsigned short int n ) { return __builtin_ffs( (typeof(n))~n ); }
    59         unsigned int low0( unsigned int n ) { return __builtin_ffs( ~n ); }
    60         unsigned int low0( unsigned long int n ) { return __builtin_ffsl( ~n ); }
    61         unsigned int low0( unsigned long long int n ) { return __builtin_ffsll( ~n ); }
     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 ); }
    6258
    63         // Find least significiant one bit.
    64         unsigned int low1( unsigned int n ) { return __builtin_ffs( n ); }
    65         unsigned int low1( unsigned long int n ) { return __builtin_ffsl( n ); }
    66         unsigned int low1( unsigned long long int n ) { return __builtin_ffsll( n ); }
     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; }
    6765
    68         // Find most significiant zero bit.
    69         unsigned int high0( unsigned char n ) { return n == (typeof(n))-1 ? 0 : __bitsizeof(unsigned int) - __builtin_clz( (typeof(n))~n ); }
    70         unsigned int high0( unsigned short int n ) { return n == (typeof(n))-1 ? 0 : __bitsizeof(unsigned int) - __builtin_clz( (typeof(n))~n ); }
    71         unsigned int high0( unsigned int n ) { return n == -1 ? 0 : __bitsizeof(n) - __builtin_clz( ~n ); }
    72         unsigned int high0( unsigned long int n ) { return n == -1 ? 0 : __bitsizeof(n) - __builtin_clzl( ~n ); }
    73         unsigned int high0( unsigned long long int n ) { return n == -1 ? 0 : __bitsizeof(n) - __builtin_clzll( ~n ); }
     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
    7470
    75         // Find most significiant one bit.
    76         unsigned int high1( unsigned char n ) { return n == 0 ? 0 : __bitsizeof(unsigned int) - __builtin_clz( n ); }
    77         unsigned int high1( unsigned short int n ) { return n == 0 ? 0 : __bitsizeof(unsigned int) - __builtin_clz( n ); }
    78         unsigned int high1( unsigned int n ) { return n == 0 ? 0 : __bitsizeof(n) - __builtin_clz( n ); }
    79         unsigned int high1( unsigned long int n ) { return n == 0 ? 0 : __bitsizeof(n) - __builtin_clzl( n ); }
    80         unsigned int high1( unsigned long long int n ) { return n == 0 ? 0 : __bitsizeof(n) - __builtin_clzll( n ); }
     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
    8176
    82         // Check for power of 2, clears bits below n, rounding down to the next lower multiple of n.  0 is not a power of 2
    83         // but this computation returns true because of the two's complement, so it is a special case.
    84         bool is_pow2( unsigned char n ) { return n == 0 ? false : (n & (n - 1)) == 0; }
    85         bool is_pow2( unsigned short int n ) { return n == 0 ? false : (n & (n - 1)) == 0; }
    86         bool is_pow2( unsigned int n ) { return n == 0 ? false : (n & (n - 1)) == 0; }
    87         bool is_pow2( unsigned long int n ) { return n == 0 ? false : (n & (n - 1)) == 0; }
    88         bool is_pow2( unsigned long long int n ) { return n == 0 ? false : (n & (n - 1)) == 0; }
    89 
    90         // Returns n aligned at the floor of align, clear bits above or equal to align, giving n % align.
    91         signed char floor2( signed char n, char align ) { /*assert( is_pow2( align ) );*/ return n & -align; }
    92         unsigned char floor2( unsigned char n, unsigned char align ) { /*assert( is_pow2( align ) );*/ return n & -align; }
    93         short int floor2( short int n, short int align ) { /*assert( is_pow2( align ) );*/ return n & -align; }
    94         unsigned short int floor2( unsigned short int n, unsigned short int align ) { /*assert( is_pow2( align ) );*/ return n & -align; }
    95         int floor2( int n, int align ) { /*assert( is_pow2( align ) );*/ return n & -align; }
    96         unsigned int floor2( unsigned int n, unsigned int align ) { /*assert( is_pow2( align ) );*/ return n & -align; }
    97         long int floor2( long int n, long int align ) { /*assert( is_pow2( align ) );*/ return n & -align; }
    98         unsigned long int floor2( unsigned long int n, unsigned long int align ) { /*assert( is_pow2( align ) );*/ return n & -align; }
    99         long long int floor2( long long int n, long long int align ) { /*assert( is_pow2( align ) );*/ return n & -align; }
    100         unsigned long long int floor2( unsigned long long int n, unsigned long long int align ) { /*assert( is_pow2( align ) );*/ return n & -align; }
    101 
    102         // forall( otype T | { T ?&?( T, T ); T -?( T ); } )
    103         // T floor2( T n, T align ) { /* assert( is_pow2( align ) ); */ return n & -align; }
    104 
    105         signed char floor( signed char n, char align ) { return n / align * align; }
    106         unsigned char floor( unsigned char n, unsigned char align ) { return n / align * align; }
    107         short int floor( short int n, short int align ) { return n / align * align; }
    108         unsigned short int floor( unsigned short int n, unsigned short int align ) { return n / align * align; }
    109         int floor( int n, int align ) { return n / align * align; }
    110         unsigned int floor( unsigned int n, unsigned int align ) { return n / align * align; }
    111         long int floor( long int n, long int align ) { return n / align * align; }
    112         unsigned long int floor( unsigned long int n, unsigned long int align ) { return n / align * align; }
    113         long long int floor( long long int n, long long int align ) { return n / align * align; }
    114         unsigned long long int floor( unsigned long long int n, unsigned long long int align ) { return n / align * align; }
    115 
    116         // forall( otype T | { T ?/?( T, T ); T ?*?( T, T ); } )
    117         // T floor( T n, T align ) { return n / align * align; }
    118 
    119         // Returns n aligned at the ceiling of align, negate, round down, negate is the same as round up.
    120         signed char ceiling2( signed char n, char align ) { /*assert( is_pow2( align ) );*/ return -floor2( -n, align ); }
    121         unsigned char ceiling2( unsigned char n, unsigned char align ) { /*assert( is_pow2( align ) );*/ return -floor2( -n, align ); }
    122         short int ceiling2( short int n, short int align ) { /*assert( is_pow2( align ) );*/ return -floor2( -n, align ); }
    123         unsigned short int ceiling2( unsigned short int n, unsigned short int align ) { /*assert( is_pow2( align ) );*/ return -floor2( -n, align ); }
    124         int ceiling2( int n, int align ) { /*assert( is_pow2( align ) );*/ return -floor2( -n, align ); }
    125         unsigned int ceiling2( unsigned int n, unsigned int align ) { /*assert( is_pow2( align ) );*/ return -floor2( -n, align ); }
    126         long int ceiling2( long int n, long int align ) { /*assert( is_pow2( align ) );*/ return -floor2( -n, align ); }
    127         unsigned long int ceiling2( unsigned long int n, unsigned long int align ) { /*assert( is_pow2( align ) );*/ return -floor2( -n, align ); }
    128         long long int ceiling2( long long int n, long long int align ) { /*assert( is_pow2( align ) );*/ return -floor2( -n, align ); }
    129         unsigned long long int ceiling2( unsigned long long int n, unsigned long long int align ) { /*assert( is_pow2( align ) );*/ return -floor2( -n, align ); }
    130 
    131         // forall( otype T | { T floor2( T, T ); T -?( T ); } )
    132         // T ceiling2( T n, T align ) { /* assert( is_pow2( align ) ); */ return -floor2( -n, align ); }
    133 
    134         signed char ceiling( signed char n, char align ) { return (n + (align - 1)) / align; }
    135         unsigned char ceiling( unsigned char n, unsigned char align ) { return (n + (align - 1)) / align; }
    136         short int ceiling( short int n, short int align ) { return (n + (align - 1)) / align; }
    137         unsigned short int ceiling( unsigned short int n, unsigned short int align ) { return (n + (align - 1)) / align; }
    138         int ceiling( int n, int align ) { return (n + (align - 1)) / align; }
    139         unsigned int ceiling( unsigned int n, unsigned int align ) { return (n + (align - 1)) / align; }
    140         long int ceiling( long int n, long int align ) { return (n + (align - 1)) / align; }
    141         unsigned long int ceiling( unsigned long int n, unsigned long int align ) { return (n + (align - 1)) / align; }
    142         long long int ceiling( long long int n, long long int align ) { return (n + (align - 1)) / align; }
    143         unsigned long long int ceiling( unsigned long long int n, unsigned long long int align ) { return (n + (align - 1)) / align; }
    144 
    145         // forall( otype T | { void ?{}( T &, one_t ); T ?+?( T, T ); T ?-?( T, T ); T ?/?( T, T ); } )
    146         // T ceiling( T n, T align ) { return (n + (align - (T){1})) / align; }
    147 } // distribution
     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}
    14883
    14984// Local Variables: //
Note: See TracChangeset for help on using the changeset viewer.