eic-opticks/sysrap/SBit.cc

0001 /*
0002  * Copyright (c) 2019 Opticks Team. All Rights Reserved.
0003  *
0004  * This file is part of Opticks
0005  * (see https://bitbucket.org/simoncblyth/opticks).
0006  *
0007  * Licensed under the Apache License, Version 2.0 (the "License");
0008  * you may not use this file except in compliance with the License.
0009  * You may obtain a copy of the License at
0010  *
0011  *   http://www.apache.org/licenses/LICENSE-2.0
0012  *
0013  * Unless required by applicable law or agreed to in writing, software
0014  * distributed under the License is distributed on an "AS IS" BASIS,
0015  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0016  * See the License for the specific language governing permissions and
0017  * limitations under the License.
0018  */
0019
0020 #include "SBit.hh"
0021
0022 #include <cstdlib>
0023 #include <iostream>
0024 #include <cstring>
0025 #include <cassert>
0026 #include <sstream>
0027 #include <bitset>
0028 #include <vector>
0029 #include <algorithm>
0030
0031 #include "ssys.h"
0032
0033
0034 #if defined(_MSC_VER)
0035
0036 #include <intrin.h>
0037
0038 int SBit::ffs(int i)
0039 {
0040     // https://msdn.microsoft.com/en-us/library/wfd9z0bb.aspx
0041     unsigned long mask = i ;
0042     unsigned long index ;
0043     unsigned char masknonzero = _BitScanForward( &index, mask );
0044     return masknonzero ? index + 1 : 0 ;
0045 }
0046
0047 #elif defined(__MINGW32__)
0048
0049 int SBit::ffs(int i)
0050 {
0051    return __builtin_ffs(i);
0052 }
0053
0054 #else
0055
0056 int SBit::ffs(int i)
0057 {
0058    return ::ffs(i);
0059 }
0060
0061 long long SBit::ffsll(long long i)
0062 {
0063    return ::ffsll(i);
0064 }
0065
0066
0067 #endif
0068
0069
0070
0071 /**
0072 ana/nibble.py::
0073
0074     def count_nibbles(x):
0075         """
0076         NB: x can be an np.array
0077
0078         https://stackoverflow.com/questions/38225571/count-number-of-zero-nibbles-in-an-unsigned-64-bit-integer
0079         """
0080
0081         ## gather the zeroness (the OR of all 4 bits)
0082         x |= x >> 1               # or-with-1bit-right-shift-self is or-of-each-consequtive-2-bits
0083         x |= x >> 2               # or-with-2bit-right-shift-self is or-of-each-consequtive-4-bits in the lowest slot
0084         x &= 0x1111111111111111   # pluck the zeroth bit of each of the 16 nibbles
0085
0086         x = (x + (x >> 4)) & 0xF0F0F0F0F0F0F0F    # sum occupied counts of consequtive nibbles, and pluck them
0087         count = (x * 0x101010101010101) >> 56     #  add up byte totals into top byte,  and shift that down to pole 64-8 = 56
0088
0089         return count
0090 **/
0091
0092 unsigned long long SBit::count_nibbles(unsigned long long x)
0093 {
0094     x |= x >> 1 ;
0095     x |= x >> 2 ;
0096     x &= 0x1111111111111111ull ;
0097
0098     x = (x + (x >> 4)) & 0xF0F0F0F0F0F0F0Full ;
0099
0100     unsigned long long count = (x * 0x101010101010101ull) >> 56 ;
0101     return count ;
0102 }
0103
0104
0105 bool SBit::HasOneSetBit(int msk0)
0106 {
0107     int idx0 = SBit::ffs(msk0) - 1 ;  // 0-based index of lsb least-significant-bit set
0108     int msk1 = ( 0x1 << idx0 );
0109     return msk0 == msk1 ;
0110 }
0111
0112
0113
0114 struct LengthOrder
0115 {
0116     bool operator() (const std::string& s1, const std::string& s2)
0117     {
0118         size_t n1 = std::count(s1.begin(), s1.end(), ',');
0119         size_t n2 = std::count(s2.begin(), s2.end(), ',');
0120
0121         // if( n1 > 0 ) n1 += 1 ;     // move favor for PosString
0122         // if( n2 > 0 ) n2 += 1 ;
0123
0124         size_t l1 = s1.length() - n1 ;    // favor PosString by not counting commas
0125         size_t l2 = s2.length() - n2 ;
0126
0127         return l1 < l2 ;
0128     }
0129 };
0130
0131
0132 template <typename T>
0133 std::string SBit::String(T v)  // static
0134 {
0135     std::vector<std::string> str ;
0136     str.push_back( BinString(v) );   // use the default annotation option
0137     str.push_back( HexString(v) );
0138     str.push_back( DecString(v) );
0139     str.push_back( PosString(v) );
0140
0141     LengthOrder length_order ;
0142     std::sort( str.begin(), str.end(),  length_order );
0143
0144     return str[0] ;
0145 }
0146
0147
0148 template <typename T>
0149 std::string SBit::BinString(T v, bool anno)  // static
0150 {
0151     std::bitset<sizeof(T)*8> bs(v) ;
0152     bool express_flipped = 2*bs.count() > bs.size() ; // more than half the bits are set
0153     if( express_flipped ) bs.flip();
0154
0155     std::stringstream ss ;
0156     ss
0157         << ( express_flipped ? "~" : " " )
0158         << ( anno ? "0b" : "" )
0159         << bs.to_string() ;
0160         ;
0161
0162     std::string s = ss.str();
0163     return s ;
0164 }
0165
0166 template <typename T>
0167 std::string SBit::HexString(T v, bool anno)  // static
0168 {
0169     std::bitset<64> bs(v) ;  assert( bs.size() == 64 ) ;
0170     bool express_flipped = 2*bs.count() > bs.size() ; // more than half the bits are set
0171     if( express_flipped ) bs.flip();
0172     unsigned long long ull = bs.to_ullong() ;
0173
0174     std::stringstream ss ;
0175     ss
0176         << ( express_flipped ? "~" : "" )
0177         << ( anno ? "0x" : "" )
0178         << std::hex << ull << std::dec
0179         ;
0180
0181     std::string s = ss.str();
0182     return s ;
0183 }
0184
0185 template <typename T>
0186 std::string SBit::DecString(T v, bool anno)  // static
0187 {
0188     std::bitset<64> bs(v) ;  assert( bs.size() == 64 ) ;
0189     bool express_flipped = 2*bs.count() > bs.size() ; // more than half the bits are set
0190     if( express_flipped ) bs.flip();
0191     unsigned long long ull = bs.to_ullong() ;
0192
0193     std::stringstream ss ;
0194     ss
0195        << ( express_flipped ? "~" : "" )
0196        << ( anno ? "0d" : "" )
0197        << std::dec << ull
0198        ;
0199
0200     std::string s = ss.str();
0201     return s ;
0202 }
0203
0204 template <typename T>
0205 std::string SBit::PosString(T v, char delim, bool anno)  // static
0206 {
0207     std::bitset<64> bs(v) ;  assert( bs.size() == 64 ) ;
0208
0209     int hi = -1 ;  // find the highest set bit
0210     for(int i=0 ; i < int(bs.size()) ; i++ ) if(bs[i]) hi=i ;
0211
0212     bool express_flipped = 2*bs.count() > bs.size() ; // more than half the bits are set
0213     if( express_flipped ) bs.flip();
0214
0215     std::stringstream ss ;
0216     if(express_flipped) ss << "~" ;
0217     if(anno) ss << "0p" ;
0218
0219     for(int i=0 ; i < int(bs.size()) ; i++ )
0220     {
0221         if(bs[i])
0222         {
0223             ss << i ;
0224             if(bs.count() == 1 || i < hi ) ss << delim ;
0225             // when 1 bit set always include the delim
0226             // otherwise skip the delim for the last set bit
0227         }
0228     }
0229
0230     if(bs.count() == 0) ss << delim ;  // no-bits set : still output delim as blank is too difficult to recognize as a value
0231     std::string s = ss.str() ;
0232     return s ;
0233 }
0234
0235
0236 /**
0237 SBit::ParseAnnotation
0238 ----------------------
0239
0240 Parses unsigned long long (64 bit) integer strings such as : "0x001" "0b001" "0p001" "~0x001" "t0x001"
0241 and returns the integer string without the annotation prefix and sets the output arguments:
0242
0243 complement
0244     bool is true when the string starts with ~ or t
0245     (t is used as "~" can be problematic as it has special meaning to the shell)
0246 anno
0247     char is set to one of 'x','b','d','p' OR '_' if there is no such prefix
0248
0249     x : hex
0250     b : binary
0251     d : decimal
0252     p : non-standard posString prefix which specifies positions of bits that are set
0253
0254 All the below correspond to the same number::
0255
0256      2
0257      0d2
0258      0x2
0259     ~0b1101
0260      0b0010
0261      1,
0262      0p1,
0263
0264     t0b1101
0265
0266     t1,
0267     t0p1
0268
0269 **/
0270
0271 const char* SBit::ANNO = "xbdp" ;
0272
0273 const char* SBit::ParseAnnotation(bool& complement, char& anno, const char* str_ )
0274 {
0275     complement = strlen(str_) > 0 && ( str_[0] == '~' || str_[0] == 't' ) ;     // str_ starts with ~ or t
0276     int postcomp =  complement ? 1 : 0 ;                                        // offset to skip the complement first character
0277     anno = strlen(str_+postcomp) > 2 && str_[postcomp] == '0' && strchr(ANNO, str_[postcomp+1]) != nullptr ?  str_[postcomp+1] : '_' ;
0278     return str_ + postcomp + ( anno == '_' ? 0 : 2 ) ;
0279 }
0280
0281 /**
0282 SBit::FromBinString
0283 ----------------------
0284
0285
0286 **/
0287
0288 unsigned long long SBit::FromBinString(const char* str_ )
0289 {
0290     bool complement ;
0291     char anno ;
0292     const char* str = ParseAnnotation(complement, anno, str_ );
0293     assert( anno == 'b' || anno == '_' );
0294
0295     assert( sizeof(unsigned long long)*8 == 64 ) ;
0296     unsigned long long ull = std::bitset<64>(str).to_ullong() ;
0297     return complement ? ~ull : ull  ;
0298 }
0299
0300 unsigned long long SBit::FromHexString(const char* str_ )
0301 {
0302     bool complement ;
0303     char anno ;
0304     const char* str = ParseAnnotation(complement, anno, str_ );
0305     assert( anno == 'x' || anno == '_' );
0306
0307     unsigned long long ull ;
0308     std::stringstream ss;
0309     ss << std::hex << str  ;
0310     ss >> ull ;
0311     return complement ? ~ull : ull  ;
0312 }
0313
0314 unsigned long long SBit::FromDecString(const char* str_ )
0315 {
0316     bool complement ;
0317     char anno ;
0318     const char* str = ParseAnnotation(complement, anno, str_ );
0319     assert( anno == 'd' || anno == '_' );
0320
0321     unsigned long long ull ;
0322     std::stringstream ss;
0323     ss << std::dec << str ;
0324     ss >> ull ;
0325     return complement ? ~ull : ull  ;
0326 }
0327
0328 unsigned long long SBit::FromPosString(const char* str_, char delim)
0329 {
0330     bool complement ;
0331     char anno ;
0332     const char* str = ParseAnnotation(complement, anno, str_ );
0333     assert( anno == 'p' || anno == '_' );
0334
0335     std::stringstream ss;
0336     ss.str(str)  ;
0337
0338     assert( sizeof(unsigned long long)*8 == 64 );
0339
0340     std::bitset<64> bs ; // all bits start zero
0341     std::string s;
0342     while (std::getline(ss, s, delim))
0343     {
0344         if(s.empty()) continue ;   // "," should give zero
0345         int ipos = std::atoi(s.c_str()) ;
0346         bs.set(ipos, true);
0347     }
0348     unsigned long long ull = bs.to_ullong() ;
0349
0350 #ifdef DEBUG
0351     std::cout
0352         << "SBit::FromPosString"
0353         << " str_[" << str_ << "]"
0354         << " str[" << str << "]"
0355         << " anno " << anno
0356         << " ull " << ull
0357         << std::endl
0358         ;
0359 #endif
0360
0361     return complement ? ~ull : ull  ;
0362 }
0363
0364
0365
0366 unsigned long long SBit::FromEString(const char* ekey, const char* fallback)
0367 {
0368     const char* str = ssys::getenvvar(ekey) ;
0369
0370     if(0) std::cout
0371         << "SBit::FromEString"
0372         << " ekey[" << ( ekey ? ekey : "-" ) << "]\n"
0373         << " str[" << ( str ? str : "-" ) << "]\n"
0374         << "\n"
0375         ;
0376
0377     return SBit::FromString(str ? str : fallback);
0378 }
0379
0380 /**
0381 SBit::FromString
0382 ---------------------
0383
0384 A PosString is a comma delimited list of ints that indicate that
0385 those bit positions are set. For example::
0386
0387
0388    "0,"       -> 1     # must include a delim to distinguish from normal int
0389    "0,1"      -> 3
0390    "0,1,2"    -> 7
0391    "0,1,2,3"  -> 15
0392
0393    "~0,"      -> all bits set other than first
0394
0395
0396 **/
0397
0398
0399 unsigned long long SBit::FromString(const char* str )
0400 {
0401     bool complement ;
0402     char anno ;
0403     ParseAnnotation(complement, anno, str );
0404
0405     bool anno_expect = strchr(ANNO, anno ) != nullptr  || anno == '_' ;
0406     if(!anno_expect) std::cout << "SBit::FromString unexpected anno " << anno << " from str " << str  << std::endl ;
0407     assert(anno_expect);
0408
0409     unsigned long long ull = 0ull ;
0410     if( strchr(str, ',') != nullptr )
0411     {
0412         ull = FromPosString(str, ',') ;
0413     }
0414     else
0415     {
0416         switch( anno )
0417         {
0418             case 'x': ull = FromHexString(str) ; break ;
0419             case 'b': ull = FromBinString(str) ; break ;
0420             case 'd': ull = FromDecString(str) ; break ;
0421             case 'p': ull = FromPosString(str) ; break ;
0422             case '_': ull = FromDecString(str) ; break ;
0423             default : assert(0)                ; break ;
0424         }
0425     }
0426     return ull ;
0427 }
0428
0429
0430
0431
0432 template std::string SBit::BinString(char,bool);
0433 template std::string SBit::BinString(int,bool);
0434 template std::string SBit::BinString(long,bool);
0435 template std::string SBit::BinString(long long,bool);
0436
0437 template std::string SBit::BinString(unsigned char,bool);
0438 template std::string SBit::BinString(unsigned int,bool);
0439 template std::string SBit::BinString(unsigned long,bool);
0440 template std::string SBit::BinString(unsigned long long,bool);
0441
0442
0443 template std::string SBit::HexString(char,bool);
0444 template std::string SBit::HexString(int,bool);
0445 template std::string SBit::HexString(long,bool);
0446 template std::string SBit::HexString(long long,bool);
0447
0448 template std::string SBit::HexString(unsigned char,bool);
0449 template std::string SBit::HexString(unsigned int,bool);
0450 template std::string SBit::HexString(unsigned long,bool);
0451 template std::string SBit::HexString(unsigned long long,bool);
0452
0453
0454 template std::string SBit::DecString(char,bool);
0455 template std::string SBit::DecString(int,bool);
0456 template std::string SBit::DecString(long,bool);
0457 template std::string SBit::DecString(long long,bool);
0458
0459 template std::string SBit::DecString(unsigned char,bool);
0460 template std::string SBit::DecString(unsigned int,bool);
0461 template std::string SBit::DecString(unsigned long,bool);
0462 template std::string SBit::DecString(unsigned long long,bool);
0463
0464
0465
0466 template std::string SBit::PosString(char,char,bool);
0467 template std::string SBit::PosString(int,char,bool);
0468 template std::string SBit::PosString(long,char,bool);
0469 template std::string SBit::PosString(long long,char,bool);
0470
0471 template std::string SBit::PosString(unsigned char,char,bool);
0472 template std::string SBit::PosString(unsigned int,char,bool);
0473 template std::string SBit::PosString(unsigned long,char,bool);
0474 template std::string SBit::PosString(unsigned long long,char,bool);
0475
0476
0477
0478 template std::string SBit::String(char);
0479 template std::string SBit::String(int);
0480 template std::string SBit::String(long);
0481 template std::string SBit::String(long long);
0482
0483 template std::string SBit::String(unsigned char);
0484 template std::string SBit::String(unsigned int);
0485 template std::string SBit::String(unsigned long);
0486 template std::string SBit::String(unsigned long long);
0487
0488