fork(1) download
  1. #include <cstddef>
  2. #include <cstdint>
  3. #include <type_traits>
  4.  
  5. // bool val. to bool type
  6. template <const bool Bool>
  7. struct BoolType {};
  8.  
  9. template<>
  10. struct BoolType<true> {
  11. typedef std::true_type Type;
  12. };
  13.  
  14. template<>
  15. struct BoolType<false> {
  16. typedef std::false_type Type;
  17. };
  18.  
  19. #define BOOL_TYPE(BoolVal) BoolType<BoolVal>::Type
  20.  
  21. // HINT: std::add_const / std::remove_const also can be used
  22. template <typename T, const bool Constant>
  23. struct AddRemoveConst {};
  24.  
  25. template <typename T>
  26. struct AddRemoveConst<T, true> {
  27. typedef const T Type;
  28. };
  29.  
  30. template <typename T>
  31. struct AddRemoveConst<T, false> {
  32. typedef T Type;
  33. };
  34.  
  35. #define ADD_REMOVE_CONST(Type, StaticPredicate) AddRemoveConst<Type, StaticPredicate>::Type
  36.  
  37. // std::is_fundamental [http://w...content-available-to-author-only...s.com/reference/type_traits/is_fundamental/]
  38. enum class ECFundamentalTypeTags {
  39. UNIDENTIFIED,
  40. BOOL,
  41. SIGNED_CHAR,
  42. UNSIGNED_CHAR,
  43. // Signedness of wchar_t is unspecified
  44. // [http://stackoverflow.com/questions/11953363/wchar-t-is-unsigned-or-signed]
  45. WCHAR,
  46.  
  47. //// 'char16_t' AND 'char32_t' SHOULD be a keywords since the C++11,
  48. //// BUT MS VS Community 2013 Upd 5 does NOT supports that
  49. //// AND specifys 'char16_t' AND 'char32_t' as a typdef aliases instead
  50. //// (so they are NOT presented here)
  51.  
  52. SIGNED_SHORT_INT,
  53. UNSIGNED_SHORT_INT,
  54. SIGNED_INT,
  55. UNSIGNED_INT,
  56. SIGNED_LONG_INT,
  57. UNSIGNED_LONG_INT,
  58. SIGNED_LONG_LONG_INT, // C++11
  59. UNSIGNED_LONG_LONG_INT, // C++11
  60. FLOAT,
  61. DOUBLE,
  62. LONG_DOUBLE,
  63. VOID_,
  64. NULLPTR // C++11 std::nullptr_t
  65. };
  66.  
  67. template <typename T, class TypeTags = ECFundamentalTypeTags>
  68. struct TypeTag {
  69. static const auto TAG = TypeTags::UNIDENTIFIED;
  70. };
  71.  
  72. template <class TypeTags>
  73. struct TypeTag<bool, TypeTags> {
  74. static const auto TAG = TypeTags::BOOL;
  75. };
  76.  
  77. template <class TypeTags>
  78. struct TypeTag<signed char, TypeTags> {
  79. static const auto TAG = TypeTags::SIGNED_CHAR;
  80. };
  81.  
  82. template <class TypeTags>
  83. struct TypeTag<unsigned char, TypeTags> {
  84. static const auto TAG = TypeTags::UNSIGNED_CHAR;
  85. };
  86.  
  87. template <class TypeTags>
  88. struct TypeTag<wchar_t, TypeTags> {
  89. static const auto TAG = TypeTags::WCHAR;
  90. };
  91.  
  92. template <class TypeTags>
  93. struct TypeTag<signed short int, TypeTags> {
  94. static const auto TAG = TypeTags::SIGNED_SHORT_INT;
  95. };
  96.  
  97. template <class TypeTags>
  98. struct TypeTag<unsigned short int, TypeTags> {
  99. static const auto TAG = TypeTags::UNSIGNED_SHORT_INT;
  100. };
  101.  
  102. template <class TypeTags>
  103. struct TypeTag<signed int, TypeTags> {
  104. static const auto TAG = TypeTags::SIGNED_INT;
  105. };
  106.  
  107. template <class TypeTags>
  108. struct TypeTag<unsigned int, TypeTags> {
  109. static const auto TAG = TypeTags::UNSIGNED_INT;
  110. };
  111.  
  112. template <class TypeTags>
  113. struct TypeTag<signed long int, TypeTags> {
  114. static const auto TAG = TypeTags::SIGNED_LONG_INT;
  115. };
  116.  
  117. template <class TypeTags>
  118. struct TypeTag<unsigned long int, TypeTags> {
  119. static const auto TAG = TypeTags::UNSIGNED_LONG_INT;
  120. };
  121.  
  122. template <class TypeTags>
  123. struct TypeTag<signed long long int, TypeTags> {
  124. static const auto TAG = TypeTags::SIGNED_LONG_LONG_INT;
  125. };
  126.  
  127. template <class TypeTags>
  128. struct TypeTag<unsigned long long int, TypeTags> {
  129. static const auto TAG = TypeTags::UNSIGNED_LONG_LONG_INT;
  130. };
  131.  
  132. template <class TypeTags>
  133. struct TypeTag<float, TypeTags> {
  134. static const auto TAG = TypeTags::FLOAT;
  135. };
  136.  
  137. template <class TypeTags>
  138. struct TypeTag<double, TypeTags> {
  139. static const auto TAG = TypeTags::DOUBLE;
  140. };
  141.  
  142. template <class TypeTags>
  143. struct TypeTag<long double, TypeTags> {
  144. static const auto TAG = TypeTags::LONG_DOUBLE;
  145. };
  146.  
  147. template <class TypeTags>
  148. struct TypeTag<void, TypeTags> {
  149. static const auto TAG = TypeTags::VOID_;
  150. };
  151.  
  152. template <class TypeTags>
  153. struct TypeTag<std::nullptr_t, TypeTags> {
  154. static const auto TAG = TypeTags::NULLPTR;
  155. };
  156.  
  157. #define TYPE_TAG(Object) TypeTag<std::decay<decltype(Object)>::type>::TAG
  158.  
  159. // Size is in bytes
  160. // Fixed width integer types (since C++11): http://e...content-available-to-author-only...e.com/w/cpp/types/integer
  161. // See also: http://w...content-available-to-author-only...4.com/en/t/0012/
  162. template <const size_t Size, const bool Signed>
  163. struct IntegralTypeBySize {
  164. static const auto TAG = ECFundamentalTypeTags::UNIDENTIFIED;
  165. };
  166.  
  167. template<>
  168. struct IntegralTypeBySize<1U, true> {
  169. typedef int8_t Type;
  170. static const auto TAG = TypeTag<Type, ECFundamentalTypeTags>::TAG;
  171. };
  172.  
  173. template<>
  174. struct IntegralTypeBySize<2U, true> {
  175. typedef int16_t Type;
  176. static const auto TAG = TypeTag<Type, ECFundamentalTypeTags>::TAG;
  177. };
  178.  
  179. template<>
  180. struct IntegralTypeBySize<4U, true> {
  181. typedef int32_t Type;
  182. static const auto TAG = TypeTag<Type, ECFundamentalTypeTags>::TAG;
  183. };
  184.  
  185. template<>
  186. struct IntegralTypeBySize<8U, true> {
  187. typedef int64_t Type;
  188. static const auto TAG = TypeTag<Type, ECFundamentalTypeTags>::TAG;
  189. };
  190.  
  191. template<>
  192. struct IntegralTypeBySize<1U, false> {
  193. typedef uint8_t Type;
  194. static const auto TAG = TypeTag<Type, ECFundamentalTypeTags>::TAG;
  195. };
  196.  
  197. template<>
  198. struct IntegralTypeBySize<2U, false> {
  199. typedef uint16_t Type;
  200. static const auto TAG = TypeTag<Type, ECFundamentalTypeTags>::TAG;
  201. };
  202.  
  203. template<>
  204. struct IntegralTypeBySize<4U, false> {
  205. typedef uint32_t Type;
  206. static const auto TAG = TypeTag<Type, ECFundamentalTypeTags>::TAG;
  207. };
  208.  
  209. template<>
  210. struct IntegralTypeBySize<8U, false> {
  211. typedef uint64_t Type;
  212. static const auto TAG = TypeTag<Type, ECFundamentalTypeTags>::TAG;
  213. };
  214.  
  215. #include <cstring>
  216. #include <cassert>
  217. #include <cstdio>
  218.  
  219. #include <mutex>
  220. #include <atomic>
  221. #include <limits>
  222. #include <algorithm>
  223.  
  224. // Abstract
  225. // [!] In C++14 many of this funcs can be 'constexpr' [!]
  226. class MathUtils {
  227.  
  228. public:
  229.  
  230. // Up to 10^18; returns zero if degree > 18
  231. // Complexity: constant - O(1)
  232. static long long int getTenPositiveDegree(const size_t degree = 0U) throw() {
  233. static const long long int TABLE[] =
  234. // 32 bit
  235. {1LL, 10LL, 100LL, 1000LL, 10000LL, 100000LL, 1000000LL, 10000000LL, 100000000LL, 1000000000LL,
  236. // 64 bit
  237. 10000000000LL, 100000000000LL, 1000000000000LL, 10000000000000LL, 100000000000000LL,
  238. 1000000000000000LL, 10000000000000000LL, 100000000000000000LL, 1000000000000000000LL};
  239. return degree < (sizeof(TABLE) / sizeof(*TABLE)) ? TABLE[degree] : 0LL; // 0 if too high
  240. }
  241.  
  242. // Returns 1 for (0, 21), 6 for (1, 360), 2 for (1, 120), 7 for (0, 7), 4 for (1, 40);
  243. // 0 for (0, 920) OR (3, 10345) OR (0, 0) OR (4, 10) etc
  244. // 'allBelowOrderDigitsIsZero' will be true for
  245. // (0, 7) OR (0, 20) OR (1, 130) OR (2, 12300) OR (0, 0)
  246. // Negative numbers are allowed; order starts from zero
  247. // (for number 3219 zero order digit is 9)
  248. // Complexity: constant - O(1)
  249. static size_t getDigitOfOrder(const size_t order, const long long int num,
  250. bool& allBelowOrderDigitsIsZero) throw()
  251. {
  252. const auto degK = getTenPositiveDegree(order);
  253. const auto shiftedVal = num / degK; // shifting to the speicified order, ignoring remnant
  254. allBelowOrderDigitsIsZero = num == (shiftedVal * degK); // shift back without adding remnant
  255. return static_cast<size_t>(std::abs(shiftedVal % 10LL)); // getting the exact digit
  256. }
  257.  
  258. // 'arraySize' will holds {9, 0, 2, 6, 4, 1} for 902641,
  259. // {5, 4, 8, 2, 3} for 54823 etc if 'symbols' is false
  260. // {'9', '0', '2', '6', '4', '1', '\0'} AND {'5', '4', '8', '2', '3', '\0'} otherwise
  261. // 'count' will hold actual digits count (64 bit numbers can have up to 20 digits)
  262. // i. e. 'count' determines digit's degree (highest nonze-zero order)
  263. // Fills buffer in the reversed order (from the end), returns ptr. to the actual str. start
  264. // Returns nullptr on ANY error
  265. // Negative numbers ok, adds sign. for the negative num. if 'symbols' is true
  266. // Can be used as a num-to-str. convertion function
  267. // (produces correct POD C str. if 'symbols' is true)
  268. // 'num' will hold the remain digits, if the buffer is too small
  269. // [!] OPTIMIZATION HINT: wrap args. into the struct passed by reference [!]
  270. // Complexity: linear - O(n) in the number degree (log10(num))
  271. static char* getArrayOfDigits(long long int& num, size_t& count,
  272. char* arrayPtr, size_t arraySize,
  273. size_t (&countByDigit)[10U], // statistics
  274. const bool symbols = false) throw()
  275. {
  276. count = size_t();
  277. memset(countByDigit, 0, sizeof(countByDigit));
  278.  
  279. if (!arrayPtr || arraySize < 2U) return nullptr;
  280. arrayPtr += arraySize; // shift to the past-the-end
  281. if (symbols) {
  282. *--arrayPtr = '\0'; // placing str. terminator
  283. --arraySize; // altering remain size
  284. }
  285. const bool negative = num < 0LL;
  286. if (negative) num = -num; // revert ('%' for the negative numbers produces negative results)
  287. char currDigit;
  288.  
  289. auto getCurrCharUpdateIfReqAndAdd = [&]() throw() {
  290. currDigit = num % 10LL;
  291. num /= 10LL;
  292.  
  293. ++countByDigit[currDigit];
  294. if (symbols) currDigit += '0';
  295.  
  296. *--arrayPtr = currDigit;
  297. ++count;
  298. };
  299.  
  300. while (true) {
  301. getCurrCharUpdateIfReqAndAdd(); // do the actual job
  302. if (!num) break; // that was a last digit
  303. if (count >= arraySize) return nullptr; // check borders
  304. }
  305. if (negative && symbols) {
  306. if (count >= arraySize) return nullptr; // check borders
  307. *--arrayPtr = '-'; // place negative sign.
  308. }
  309. return arrayPtr;
  310. }
  311.  
  312. // 90980000 -> 9098, -1200 -> -12, 46570 -> 4657, -44342 -> -44342, 0 -> 0 etc
  313. // Ok with negative numbers
  314. // Complexity: linear - O(n) in the 1 + trailing zero digits count in a number,
  315. // up to the number degree (log10(num))
  316. static void rewindToFirstNoneZeroDigit(long long int& num,
  317. size_t& skippedDigitsCount) throw()
  318. {
  319. skippedDigitsCount = size_t();
  320. if (!num) return;
  321.  
  322. auto currDigit = num % 10LL;
  323. while (!currDigit) { // while zero digit
  324. num /= 10LL;
  325. ++skippedDigitsCount;
  326.  
  327. currDigit = num % 10LL;
  328. }
  329. }
  330.  
  331. // (2, 1234) -> 34; (0, <whatever>) -> 0; (1, -6732) -> 2; (325, 12) -> 12
  332. // Complexity: constant - O(1)
  333. template<typename TNumType>
  334. static TNumType getLastNDigitsOfNum(const size_t n, const TNumType num) throw() {
  335. if (!n || !num) return static_cast<TNumType>(0);
  336.  
  337. const auto divider = getTenPositiveDegree(n);
  338. if (!divider) return num; // if too high 'n'
  339.  
  340. auto result = static_cast<TNumType>(num % divider);
  341. if (result < TNumType()) result = -result; // revert if negative
  342.  
  343. return result;
  344. }
  345.  
  346. // [!] Unoptimal, linear complexity, do NOT use [!]
  347. // Better for the low numbers
  348. // 0 -> 1; 3 -> 1; 45 -> 2; -45675 = 5; 236693856836413986 = 18
  349. template<typename TNumType>
  350. static size_t getDigitCount(TNumType num) throw() {
  351. static const auto divider = static_cast<TNumType>(10);
  352. size_t count = size_t();
  353. do {
  354. ++count;
  355. num /= divider;
  356. } while (num);
  357. return count;
  358. }
  359.  
  360. // [!] Use standart log10 instead,
  361. // see: http://stackoverflow.com/questions/7317414/what-is-the-complexity-of-the-log-function[!]
  362. // Returns 10 for 2362659283, 4 for -9543, 1 for 9, 1 for 0 etc
  363. // Complexity: logarithmic - O(log2(TABLE item count) + 1)
  364. static size_t getDigitCountEx(long long int num) throw() {
  365. static const long long int TABLE[] =
  366. // 32 bit
  367. {0LL, 10LL, 100LL, 1000LL, 10000LL, 100000LL, 1000000LL, 10000000LL, 100000000LL, 1000000000LL,
  368. // 64 bit
  369. 10000000000LL, 100000000000LL, 1000000000000LL, 10000000000000LL, 100000000000000LL,
  370. 1000000000000000LL, 10000000000000000LL, 100000000000000000LL, 1000000000000000000LL};
  371. static const auto TABLE_END = TABLE + std::extent<decltype(TABLE)>::value; // past-the-end elem.
  372.  
  373. if (num < 0LL) num = -num; // reverse
  374. // Returns a ptr. to the first elem. in the range, which compares greater
  375. return std::upper_bound<>(TABLE, TABLE_END, num) - TABLE;
  376. }
  377.  
  378. // (0, <whatever>) -> 0; (97, 21) -> 21; (56453, 0) -> 0; (3, 546429) -> 546
  379. // Complexity: amortized constant ~O(1), based on the 'log10' complexity
  380. // [http://stackoverflow.com/questions/7317414/what-is-the-complexity-of-the-log-function]
  381. template<typename TNumType>
  382. static TNumType getFirstNDigitsOfNum(const size_t n, const TNumType num) throw() {
  383. if (!n) return TNumType();
  384.  
  385. const auto count = static_cast<size_t>(log10(num)) + 1U;
  386. if (count <= n) return num;
  387.  
  388. return num / static_cast<TNumType>(getTenPositiveDegree(count - n)); // reduce
  389. }
  390.  
  391. // [!] Do NOT confuse this with the std. C++ keyword 'xor'
  392. // (which is an alias for the bitwise operator '^') [!]
  393. // Better use in logic utils
  394. static bool XOR(const bool b1, const bool b2) throw() {
  395. return (b1 || b2) && !(b1 && b2);
  396. }
  397.  
  398. // Returns zero if too high pow. (if > 63)
  399. // [!] Use 63 idx. very carefully - ONLY to get the appropriate bit. mask
  400. // (zeroes + sign bit set), BUT NOT the appropriate value (returns negative num.) [!]
  401. static long long int getPowerOf2(const size_t pow) throw() {
  402. static const long long int POWERS[] = { // 0 - 62
  403. 1LL, 2LL, 4LL, 8LL, 16LL, 32LL, 64LL, // 8 bit
  404. 128LL, 256LL, 512LL, 1024LL, 2048LL, 4096LL, 8192LL, 16384LL, 32768LL, // 16 bit
  405. //// 32 bit
  406. 65536LL, 131072LL, 262144LL, 524288LL, 1048576LL, 2097152LL,
  407. 4194304LL, 8388608LL, 16777216LL, 33554432LL,
  408. 67108864LL, 134217728LL, 268435456LL, 536870912LL, 1073741824LL,
  409. //// 64 bit
  410. 2147483648LL, 4294967296LL, 8589934592LL, 17179869184LL, 34359738368LL, 68719476736LL,
  411. 137438953472LL, 274877906944LL, 549755813888LL, 1099511627776LL, 2199023255552LL,
  412. 4398046511104LL, 8796093022208LL, 17592186044416LL, 35184372088832LL, 70368744177664LL,
  413. 140737488355328LL, 281474976710656LL, 562949953421312LL, 1125899906842624LL, 2251799813685248LL,
  414. 4503599627370496LL, 9007199254740992LL, 18014398509481984LL, 36028797018963968LL,
  415. 72057594037927936LL, 144115188075855872LL, 288230376151711744LL, 576460752303423488LL,
  416. 1152921504606846976LL, 2305843009213693952LL, 4611686018427387904LL,
  417. -9223372036854775808LL // 63-th bit (sign bit) set bit mask
  418. };
  419. return pow >= std::extent<decltype(POWERS)>::value ? 0LL : POWERS[pow];
  420. }
  421.  
  422. // [!] Use standart 'exp2' instead [!]
  423. // In C++11 better use templated constexpr version
  424. // Supports negative power, uses lazy evaluation
  425. // Returns zero if absolute pow. is too high (> 63)
  426. // [!] Does NOT thread safe lazy init.; slower [!]
  427. static long double getPowerOf2Ex(const int pow) throw() {
  428. static const auto MAX_POWER = 63U; // hello, Homer!
  429. if (std::abs(pow) > MAX_POWER) return 0.0L; // too high
  430.  
  431. static bool INITED = false; // false does NOT really needed here, coze static
  432. static long double POWERS[MAX_POWER * 2U + 1U]; // zero initialized, coze static
  433. static const size_t MIDDLE = MAX_POWER;
  434.  
  435. if (!INITED) {
  436. auto idx = 1U; // power[63] == 0 (rest as is), power[64] == 2, power[62] == 1/2
  437. for (long double k = 2.0L; idx <= MAX_POWER; k *= 2.0L, ++idx) {
  438. POWERS[MIDDLE + idx] = k;
  439. POWERS[MIDDLE - idx] = 1.0L / k;
  440. }
  441. POWERS[MIDDLE] = 1.0L; // set power[63] to the 1
  442.  
  443. INITED = true;
  444. }
  445. return POWERS[MIDDLE + pow];
  446. }
  447.  
  448. // [!] Use standart 'log2' instead [!]
  449. // Returns zero if the incoming number have more then 1 bit setted OR NO bit setted
  450. // '100' (4) -> 3; '1' (1) -> 0
  451. // Complexity: logarithmic O(log2(64))
  452. // Almost equivalent to the log2(X)
  453. // OPTIMIZATION HINT 1: better use the compiler intrinsic func. like '__lzcnt'
  454. // (https://e...content-available-to-author-only...a.org/wiki/Find_first_set)
  455. // (see 'LZCNT' VS 'BSR' correct usage in 'getBitStrEx')
  456. // OPTIMIZATION HINT 2: O(1) algo. using De Bruijn sequence -
  457. // http://stackoverflow.com/questions/3465098/bit-twiddling-which-bit-is-set
  458. static size_t getBitIdx(const unsigned long long int oneBitNum) throw() {
  459. if (!oneBitNum) return size_t();
  460.  
  461. static const unsigned long long int POWERS[] = { // 0 - 63
  462. 1ULL, 2ULL, 4ULL, 8ULL, 16ULL, 32ULL, 64ULL, // 8 bit
  463. 128ULL, 256ULL, 512ULL, 1024ULL, 2048ULL, 4096ULL, 8192ULL, 16384ULL, 32768ULL, // 16 bit
  464. //// 32 bit
  465. 65536ULL, 131072ULL, 262144ULL, 524288ULL, 1048576ULL, 2097152ULL, 4194304ULL,
  466. 8388608ULL, 16777216ULL, 33554432ULL, 67108864ULL, 134217728ULL, 268435456ULL,
  467. 536870912ULL, 1073741824ULL,
  468. //// 64 bit
  469. 2147483648ULL, 4294967296ULL, 8589934592ULL, 17179869184ULL, 34359738368ULL, 68719476736ULL,
  470. 137438953472ULL, 274877906944ULL, 549755813888ULL, 1099511627776ULL, 2199023255552ULL,
  471. 4398046511104ULL, 8796093022208ULL, 17592186044416ULL, 35184372088832ULL, 70368744177664ULL,
  472. 140737488355328ULL, 281474976710656ULL, 562949953421312ULL, 1125899906842624ULL,
  473. 2251799813685248ULL, 4503599627370496ULL, 9007199254740992ULL, 18014398509481984ULL,
  474. 36028797018963968ULL, 72057594037927936ULL, 144115188075855872ULL, 288230376151711744ULL,
  475. 576460752303423488ULL, 1152921504606846976ULL, 2305843009213693952ULL, 4611686018427387904ULL,
  476. 9223372036854775808ULL
  477. }; // ofc. this table could be filled automatically using '<<' operator
  478. static const auto COUNT = std::extent<decltype(POWERS)>::value;
  479.  
  480. auto comparator = [](const void* const value1Ptr, const void* const value2Ptr) throw() -> int {
  481. const auto num1 = *static_cast<const unsigned long long int* const>(value1Ptr);
  482. const auto num2 = *static_cast<const unsigned long long int* const>(value2Ptr);
  483.  
  484. return num1 < num2 ? -1 : (num1 > num2 ? 1 : 0);
  485. };
  486. // OPTIMIZATION HINT: replace with the C++ std::lower_bound (OR binary_search)
  487. auto const elemPtr = bsearch(&oneBitNum, POWERS, COUNT, sizeof(*POWERS), comparator);
  488. if (!elemPtr) return size_t(); // NOT found
  489.  
  490. return static_cast<decltype(&*POWERS)>(elemPtr) - POWERS; // get idx. computing ptr. shift
  491. }
  492.  
  493. struct BitCount {
  494.  
  495. BitCount& operator+=(const BitCount& bitCount) throw() {
  496. total += bitCount.total;
  497. positive += bitCount.positive;
  498.  
  499. return *this;
  500. }
  501.  
  502. void clear() throw() {
  503. total = size_t();
  504. positive = size_t();
  505. }
  506.  
  507. size_t total; // significant ONLY (intermediate zero bits including ofc.)
  508. size_t positive;
  509. };
  510.  
  511. // Linear complexity, optimized by skipping zero bits
  512. // Works with the negative numbers
  513. // (setted sign. bit counts as positive AND meaning: included in 'total')
  514. template<typename TNumType>
  515. static void getBitCount(TNumType num, BitCount& count) throw() {
  516. count.clear();
  517.  
  518. if (!num) return;
  519. if (num < TNumType()) { // if negative
  520. // Reverse, reset sign bit (to allow Brian Kernighan's trix to work correct)
  521. num &= std::numeric_limits<decltype(num)>::max();
  522. ++count.positive; // count sign bit as positive
  523. ++count.total; // count sign bit as meaning (significant)
  524. }
  525. // Determine bit count by the most significant bit set
  526. count.total += static_cast<size_t>(log2(num)) + 1U;
  527. do {
  528. ++count.positive;
  529. // Brian Kernighan's trix (clear the least significant bit set)
  530. num &= (num - TNumType(1U));
  531. } while (num);
  532. }
  533.  
  534. // [!] 'TNumType' should have 2N bytes size [!]
  535. // Should be faster, uses lazy-inited lookup table
  536. // [!] Does NOT thread safe when NOT yet inited [!]
  537. // Works with the negative numbers
  538. // (setted sign. bit counts as positive AND meaning: included in 'total')
  539. template<typename TNumType>
  540. static void getBitCountEx(TNumType num, BitCount& count) throw() {
  541. count.clear();
  542.  
  543. if (!num) return;
  544. if (num < TNumType()) { // if negative
  545. // Reverse, reset sign bit (to allow bitwise right shifting to work correct)
  546. num &= std::numeric_limits<decltype(num)>::max();
  547. ++count.positive; // count sign bit as positive
  548. ++count.total; // count sign bit as meaning (significant)
  549. }
  550. static_assert(!(sizeof(num) % 2U), "'TNumType' should have 2N bytes size");
  551.  
  552. const auto counts = getBitCountsLookupTable();
  553.  
  554. static const TNumType FIRST_2_BYTES = 65535; // 1111 1111 1111 1111
  555. size_t idxInTable;
  556.  
  557. size_t iterCount = 0U, lastTotal = 0U;
  558. for (;; ++iterCount, num >>= 16U) { // 16 bits in 2 bytes (2 * 8)
  559. if (!num) break;
  560.  
  561. idxInTable = num & FIRST_2_BYTES; // get ONLY first 2 (lest significant) bytes
  562. if (!idxInTable) continue;
  563.  
  564. const auto& currCounts = counts[idxInTable];
  565. count.positive += currCounts.positive;
  566. lastTotal = currCounts.total; // replace by the last (most significant pair) count
  567. }
  568. // 16 bits in 2 bytes (in EACH iteration); AT least one iteration
  569. count.total += (lastTotal + (iterCount - 1U) * 16U);
  570. }
  571.  
  572. // 'bitCount' determines how many bits will be set to 1
  573. // (ALL others will be set to 0) AND can NOT be larger then 64
  574. // Bits will be filled starting from the least significant
  575. // (by default) OR from most significant (if 'reversedOrder' is true)
  576. static unsigned long long int getBitMask(const size_t bitCount,
  577. const bool reversedOrder = false) throw()
  578. {
  579. static const unsigned long long int MASKS[]
  580. = {0ULL, 1ULL, 3ULL, 7ULL, 15ULL, 31ULL, 63ULL, 127ULL, 255ULL, 511ULL, 1023ULL,
  581. 2047ULL, 4095ULL, 8191ULL, 16383ULL, 32767ULL, 65535ULL, 131071ULL, 262143ULL,
  582. 524287ULL, 1048575ULL, 2097151ULL, 4194303ULL, 8388607ULL, 16777215ULL, 33554431ULL,
  583. 67108863ULL, 134217727ULL, 268435455ULL, 536870911ULL, 1073741823ULL, 2147483647ULL,
  584. 4294967295ULL, 8589934591ULL, 17179869183ULL, 34359738367ULL, 68719476735ULL,
  585. 137438953471ULL, 274877906943ULL, 549755813887ULL, 1099511627775ULL, 2199023255551ULL,
  586. 4398046511103ULL, 8796093022207ULL, 17592186044415ULL, 35184372088831ULL,
  587. 70368744177663ULL, 140737488355327ULL, 281474976710655ULL, 562949953421311ULL,
  588. 1125899906842623ULL, 2251799813685247ULL, 4503599627370495ULL, 9007199254740991ULL,
  589. 18014398509481983ULL, 36028797018963967ULL, 72057594037927935ULL, 144115188075855871ULL,
  590. 288230376151711743ULL, 576460752303423487ULL, 1152921504606846975ULL, 2305843009213693951ULL,
  591. 4611686018427387903ULL, 9223372036854775807ULL,
  592. // Last, equal to the 'std::numeric_limits<unsigned long long int>::max()'
  593. 18446744073709551615ULL};
  594. static const auto COUNT = std::extent<decltype(MASKS)>::value;
  595.  
  596. if (bitCount >= COUNT) return MASKS[COUNT - 1U]; // return last
  597. return reversedOrder ? MASKS[COUNT - 1U] ^ MASKS[COUNT - 1U - bitCount] : MASKS[bitCount];
  598. }
  599.  
  600. // Will set bits with the specified indexes to 1 (OR to 0 if 'SetToZero' is true)
  601. // ANY value from the 'idxs' array should NOT be larger then 62
  602. // [!] Should work correct with the signed num. types (NOT tested) [!]
  603. template<const bool SetToZero = false, typename TNumType, const size_t IndexesCount>
  604. static void setBits(TNumType& valueToUpdate, const size_t(&idxs)[IndexesCount]) throw() {
  605. static const size_t MAX_BIT_IDX = std::min(sizeof(valueToUpdate) * 8U - 1U, 62U);
  606.  
  607. decltype(0LL) currBitMask;
  608. for (const auto bitIdx : idxs) {
  609. if (bitIdx > MAX_BIT_IDX) continue; // skip invalid idxs
  610.  
  611. currBitMask = getPowerOf2(bitIdx);
  612. if (SetToZero) {
  613. valueToUpdate &= ~currBitMask; // use reversed mask to UNset the specified bit
  614. } else valueToUpdate |= currBitMask; // set specified bit
  615. }
  616. }
  617.  
  618. //// Use next two funcs to parse individual bits, individual bytes,
  619. //// variable count of bits (multiply of 2 OR 8 OR NOT)
  620. //// For other bit-working algos see http://g...content-available-to-author-only...d.edu/~seander/bithacks.html
  621.  
  622. // Returns meaning (holding actual data) parts count (other parts will be filled with zeroes)
  623. // First meaning part will hold the least significant bit(s) AND so on
  624. // At the func. end 'num' will hold unprocessed data (if left)
  625. // shifted to the beginning (to the least significant bit)
  626. // [!] 'bitCountInPart' can NOT be larger then the actual bit count
  627. // in the types 'TPartType' OR 'TNumType' (MAX = 64) [!]
  628. // Prefer 'TPartType' to be unsigned integral number type (as so 'TNumType')
  629. // [!] If 'num' is a NEGATIVE number, then the sign.
  630. // bit will be FORCEFULLY RESETED, so do NOT use NEGATIVE numbers here [!]
  631. template<typename TNumType, class TPartType, const size_t PartCount>
  632. static unsigned int parseByBits(TNumType& num, size_t bitCountInPart,
  633. TPartType (&parts)[PartCount]) throw()
  634. {
  635. auto filledParts = 0U, meaningParts = 0U; // counters
  636.  
  637. if (bitCountInPart && num) { // fill meaning parts
  638. if (num < TNumType()) { // if negative
  639. //// Reverse, reset sign bit (to allow bitwise right shifting to work correct)
  640. //// std::remove_reference<decltype(num)>::type == TNumType
  641. num &= std::numeric_limits<typename std::remove_reference<decltype(num)>::type>::max();
  642. }
  643. static const auto PART_SIZE =
  644. std::min(sizeof(TNumType) * 8U, sizeof(TPartType) * 8U); // in bits
  645.  
  646. if (bitCountInPart > PART_SIZE) bitCountInPart = PART_SIZE; // check & correct
  647. const TNumType bitMask =
  648. static_cast<TNumType>(getBitMask(bitCountInPart, false)); // to extract the part
  649.  
  650. do {
  651. parts[meaningParts++] = static_cast<TPartType>(num & bitMask);
  652. num >>= bitCountInPart;
  653. } while (meaningParts < PartCount && num);
  654. }
  655. filledParts += meaningParts;
  656.  
  657. while (filledParts < PartCount)
  658. parts[filledParts++] = static_cast<TPartType>(0U); // zeroize remaining parts
  659. return meaningParts;
  660. }
  661.  
  662. // Return the last meaning (holding actual data) part INDEX
  663. // OR -1 if NOT any meaning part is presented
  664. // NOT meaning parts (including zero-size AND negative-size parts) will be filled with zeroes
  665. // First meaning part will hold the least significant bit(s) AND so on
  666. // At the func. end 'num' will hold unprocessed data (if left)
  667. // shifted to the beginning (to the least significant bit)
  668. // [!] ANY part size from the 'partSizes' can NOT be higher then
  669. // the actual size in bits of the types 'TNumType' OR 'TPartType' (MAX = 64) [!]
  670. // Prefer 'TPartType' AND 'TPartSizeType' to be unsigned integral number types (as so 'TNumType')
  671. // [!] If 'num' is a NEGATIVE number, then the sign. bit will be FORCEFULLY RESETED,
  672. // so do NOT use NEGATIVE numbers here [!]
  673. template<typename TNumType, class TPartSizeType, class TPartType, const size_t PartCount>
  674. static int parseByBitsEx(TNumType& num, const TPartSizeType (&partSizes)[PartCount],
  675. TPartType (&parts)[PartCount]) throw()
  676. {
  677. auto filledParts = 0U;
  678. auto lastMeaning = -1; // idx.
  679.  
  680. if (num) { // fill meaning parts AND invalid-size parts (if presented)
  681. auto meaningParts = 0U, incorrectParts = 0U; // counters
  682.  
  683. if (num < TNumType()) { // if negative
  684. //// Reverse, reset sign bit (to allow bitwise right shifting to work correct)
  685. //// std::remove_reference<decltype(num)>::type == TNumType
  686. num &= std::numeric_limits<typename std::remove_reference<decltype(num)>::type>::max();
  687. }
  688. static const auto MAX_PART_SIZE =
  689. std::min(sizeof(TNumType) * 8U, sizeof(TPartType) * 8U); // in bits
  690.  
  691. TNumType bitMask;
  692. TPartSizeType currPartSize;
  693. do {
  694. currPartSize = partSizes[meaningParts];
  695.  
  696. if (currPartSize < TPartSizeType(1U)) { // invalid-size part
  697. parts[filledParts++] = TPartType(); // zeroize part
  698. ++incorrectParts;
  699. continue;
  700. }
  701. if (currPartSize > MAX_PART_SIZE) currPartSize = MAX_PART_SIZE; // check & correct
  702.  
  703. bitMask = static_cast<TNumType>(getBitMask(currPartSize, false)); // to extract the part
  704.  
  705. parts[lastMeaning = filledParts++] = static_cast<TPartType>(num & bitMask);
  706. ++meaningParts;
  707.  
  708. num >>= currPartSize;
  709. } while (num && filledParts < PartCount);
  710. }
  711. while (filledParts < PartCount)
  712. parts[filledParts++] = TPartType(); // zeroize remaining parts
  713.  
  714. return lastMeaning;
  715. }
  716.  
  717. // Linear complexity (N = count of the meaning bits in a number,
  718. // up to a sizeof(TNumType) * 8 for negative numbers)
  719. // Returns ptr. to the actual beginning of the str.
  720. // (buffer will be filled in the reversed order - from the end)
  721. // For the negative numbers sign bit simb. in the str. will be set at its place
  722. // (according to the size of the 'TNumType')
  723. // AND intermediate unmeaning zero bits will be filled -
  724. // BUT ALL of this will happen ONLY if the buf. is large enough
  725. // If the provided buf. is too small to hold all the data containing in 'num',
  726. // then 'num' will hold the remaining data
  727. // (INCLUDING sign bit at it's ACTUAL place for the NEGATIVE number)
  728. // shifted to the beginning (to the LEAST significant bit) after return from the func.
  729. // [!] Works with the negative numbers [!]
  730. // Returns bit str. representation in the direct bit order
  731. template<typename TNumType>
  732. static char* getBitStr(TNumType& num, char* const strBuf, const size_t strBufSize) throw() {
  733. if (!strBuf || !strBufSize) return nullptr;
  734.  
  735. const auto negative = num < TNumType();
  736. if (negative)
  737. num &= std::numeric_limits<TNumType>::max(); // reverse, reset sign bit
  738.  
  739. char* const bufLastCharPtr = strBuf + (strBufSize - 1U);
  740. char* start = bufLastCharPtr; // point to the last smb.
  741. *start-- = '\0'; // set the str. terminator
  742.  
  743. while (num && start >= strBuf) { // reverse fill buf.
  744. *start-- = '0' + (num & TNumType(1U));
  745. num >>= 1U;
  746. }
  747. if (negative) {
  748. char* const signBitSymbPtr = bufLastCharPtr - sizeof(TNumType) * 8U;
  749. // If buffer size is quite enough to hold the sign bit symb.
  750. if (signBitSymbPtr >= strBuf) {
  751. while (start > signBitSymbPtr)
  752. *start-- = '0'; // set unmeaning zero bits between sign AND meaning bits
  753. *start-- = '1'; // set sign bit symb.
  754. }
  755. if (num) // return sign bit ONLY if some data remains
  756. num |= std::numeric_limits<TNumType>::min();
  757. }
  758. return start + 1U;
  759. }
  760.  
  761. // 'hashSizeInBits' AND 'FNVPrime' should NOT be zero
  762. // (for FNV primes see here: http://i...content-available-to-author-only...e.com/chongo/tech/comp/fnv/)
  763. // 'hashSizeInBits' should NOT be larger (OR even equal)
  764. // then size of 'unsigned long long int' in bits
  765. // In the general case, almost any offset_basis will serve so long as it is non-zero
  766. static unsigned long long int generateFNV1OffsetBasis(const size_t hashSizeInBits,
  767. const unsigned long long int FNVPrime) throw()
  768. {
  769. static const auto ULL_SIZE_IN_BITS = sizeof(unsigned long long int) * 8U;
  770. static const char* const OFFSET_STR =
  771. "chongo <Landon Curt Noll> /\\../\\!"; // http://w...content-available-to-author-only...e.com/chongo/odd/bat.html
  772.  
  773. if (!hashSizeInBits || hashSizeInBits >= ULL_SIZE_IN_BITS || !FNVPrime) return 0ULL;
  774.  
  775. const unsigned long long int hashMod =
  776. static_cast<decltype(hashMod)>(std::pow(2.0, ULL_SIZE_IN_BITS));
  777. auto offsetBasis = 0ULL;
  778.  
  779. for (auto currChar = OFFSET_STR; *currChar; ++currChar) {
  780. offsetBasis = (offsetBasis * FNVPrime) % hashMod;
  781. offsetBasis ^= *currChar;
  782. }
  783. return offsetBasis;
  784. }
  785.  
  786. // 'str' SHOULD be a POD C null-terminated str.
  787. // Returns zero for an empty str.
  788. // FNV-1a algorithm description: http://i...content-available-to-author-only...e.com/chongo/tech/comp/fnv/#FNV-1a
  789. static size_t getFNV1aHash(const char* str) throw() {
  790. if (!str || !*str) return size_t();
  791. static_assert(4U == sizeof(size_t) || 8U == sizeof(size_t),
  792. "Known primes & offsets for 32 OR 64 bit hashes ONLY");
  793.  
  794. //// C++11 OPTIMIZATION HINT: better use 'constexpr' instead of 'const'
  795.  
  796. // In the general case, almost any offset_basis will serve so long as it is non - zero
  797. static const unsigned long long int BASISES[] =
  798. {2166136261ULL, 14695981039346656037ULL}; // 32 bit, 64 bit
  799. static const size_t OFFSET_BASIS =
  800. static_cast<decltype(OFFSET_BASIS)>(BASISES[sizeof(size_t) / 4U - 1U]);
  801.  
  802. // Some primes do hash better than other primes for a given integer size
  803. static const unsigned long long int PRIMES[] =
  804. {16777619ULL, 1099511628211ULL}; // 32 bit, 64 bit
  805. static const size_t PRIME =
  806. static_cast<decltype(OFFSET_BASIS)>(PRIMES[sizeof(size_t) / 4U - 1U]);
  807.  
  808. auto hash = OFFSET_BASIS;
  809. do {
  810. hash ^= *str++; // xor is performed on the low order octet (8 bits) of hash
  811. hash *= PRIME;
  812. } while (*str);
  813.  
  814. return hash;
  815. }
  816.  
  817. //// Use 'parseNum' to format file size, date/time numbers etc. in to the human readable strs
  818. //// (bytes count, seconds count in formated str. (short|long):
  819. //// 1025 b = 1 kb 1 b, 421 sec = 1 h 1 min 1 sec)
  820. //// For example:
  821. //// gbytes mbytes kbytes bytes - divider = 1024
  822. //// millions thousands hundreds tens ones etc - divider = 10 ^ x
  823.  
  824. // 'dividers' is an array of numbers which will be used as a dividers to get the appropriate result,
  825. // which will be placed at the corresponding place in the 'results' array
  826. // Func. will stop it work when either 'num' will have NO more data OR zero divider is met
  827. // OR the 'resultsCount' limit is reached
  828. // Func. will use either 'divider' OR 'dividers' dependig on the content of this values:
  829. // if 'divider' is NOT zero - it will be used, otherwise i-th value from the 'dividers' will be used
  830. // (if 'dividers' is NOT a nullptr)
  831. // Both 'dividers' AND 'results' arrays SHOULD have at least 'resultsCount' size
  832. // After return 'resultsCount' will hold an actual elems count in the 'results' array
  833. // After return 'num' will hold the rest data which is NOT fitted into the 'results' array
  834. static void parseNum(unsigned long long int& num,
  835. const size_t divider, const size_t* const dividers,
  836. size_t* const results, size_t& resultsCount) throw()
  837. {
  838. if (!results || !resultsCount) {
  839. resultsCount = 0U;
  840. return;
  841. }
  842. auto resultIdx = 0U;
  843. size_t currDivider;
  844.  
  845. for (; num && resultIdx < resultsCount; ++resultIdx) {
  846. currDivider = divider ? divider : (dividers ? dividers[resultIdx] : 0U);
  847. if (!currDivider) break;
  848.  
  849. results[resultIdx] = num % currDivider;
  850. num /= currDivider;
  851. }
  852. resultsCount = resultIdx;
  853. }
  854.  
  855. #pragma warning(disable: 4005)
  856. #ifdef _MSC_VER
  857. #define _CRT_SECURE_NO_WARNINGS
  858. #endif
  859. #pragma warning(default: 4005)
  860.  
  861. // Date/time str. wil be added (concatenated) to the provided 'str'; returns 'str'
  862. // 'TStrType' should support '+=' operator on the POD C strs AND chars
  863. // AND 'empty' func. which returns true if the str. IS empty (false otherwise)
  864. // [!!] Use this to format ONLY the time passed, NOT the actual date/time [!!]
  865. // TO DO: improve RU language support
  866. template<typename TStrType>
  867. static TStrType& addFormattedDateTimeStr(unsigned long long int timeInSecs, TStrType& str,
  868. const bool longPrefixes = true,
  869. const bool eng = true) throw()
  870. {
  871. static const char* const ENG_LONG_POSTFIXES[] =
  872. {"seconds", "minutes", "hours", "days", "months", "years", "centuries", "millenniums"};
  873. static const char* const ENG_SHORT_POSTFIXES[] =
  874. {"sec", "min", "hr", "d", "mon", "yr", "cen", "mil"};
  875.  
  876. static const char* const RU_LONG_POSTFIXES[] =
  877. {"секунд", "минут", "часов", "дней", "месяцев", "лет", "веков", "тысячелетий"};
  878. static const char* const RU_SHORT_POSTFIXES[] =
  879. {"сек", "мин", "час", "дн", "мес", "лет", "век", "тыс"};
  880.  
  881. static const auto COUNT = std::extent<decltype(ENG_LONG_POSTFIXES)>::value;
  882.  
  883. auto getPostfix = [&](const size_t idx) throw() {
  884. auto const list = longPrefixes ? (eng ? ENG_LONG_POSTFIXES : RU_LONG_POSTFIXES) // LONG
  885. : (eng ? ENG_SHORT_POSTFIXES : RU_SHORT_POSTFIXES); // SHORT
  886. return idx < COUNT ? list[idx] : "";
  887. };
  888.  
  889. static const size_t DIVIDERS[] =
  890. // \/ 60 seconds in the minute \/ 10 centuries in the millennium
  891. {60U, 60U, 24U, 30U, 12U, 100U, 10U};
  892. // ^ Month last approximately 29.53 days
  893.  
  894. size_t timings[COUNT]; // = {0}
  895. auto timingsCount = std::extent<decltype(DIVIDERS)>::value;
  896.  
  897. if (!timeInSecs) { // zero secs
  898. *timings = 0U;
  899. timingsCount = 1U;
  900. } else parseNum(timeInSecs, 0U, DIVIDERS, timings, timingsCount);
  901.  
  902. bool prev = !(str.empty());
  903. char strBuf[32U];
  904.  
  905. if (timeInSecs) { // some data rest (after ALL divisions)
  906. sprintf(strBuf, "%llu", timeInSecs);
  907.  
  908. if (prev) str += ' '; else prev = true;
  909. str += strBuf;
  910. str += ' ';
  911. str += getPostfix(COUNT - 1U);
  912. }
  913. for (auto timingIdx = timingsCount - 1U; timingIdx < timingsCount; --timingIdx) {
  914. if (timings[timingIdx]) { // if NOT zero
  915. sprintf(strBuf, "%llu", timings[timingIdx]);
  916.  
  917. if (prev) str += ' '; else prev = true;
  918. str += strBuf;
  919. str += ' ';
  920. str += getPostfix(timingIdx);
  921. }
  922. }
  923. return str;
  924. }
  925. #ifdef _MSC_VER
  926. #undef _CRT_SECURE_NO_WARNINGS
  927. #endif
  928.  
  929. // Ineffective
  930. static unsigned char ReverseBitsInByte(const unsigned char c) throw() {
  931. if (!c) return c; // zero byte, nothing to do
  932.  
  933. static const auto BIT_COUNT = sizeof(c) * 8U;
  934. static const auto STOP_BIT_IDX = BIT_COUNT / 2U;
  935.  
  936. auto RBitMask = 1U, LBitMask = 0U;
  937. auto currBitR = 0U, currBitL = 0U; // left <- right
  938. auto shiftDistance = 0U;
  939. size_t c_ = c; // to fit the register [OPTIMIZATION]
  940.  
  941. for (size_t currBitIdx = 0U; currBitIdx < STOP_BIT_IDX; ++currBitIdx) {
  942. currBitR = c_ & RBitMask;
  943.  
  944. shiftDistance = BIT_COUNT - 2U * currBitIdx - 1U;
  945. LBitMask = RBitMask << shiftDistance;
  946. currBitL = c & LBitMask;
  947.  
  948. // If ONLY one enabled (nothing to do if both in the same state)
  949. if (XOR(currBitL != 0U, currBitR != 0U)) {
  950. if (currBitL) { // 'L' enabled, 'R' - NOT
  951. c_ &= ~LBitMask; // disable 'L'
  952. c_ |= RBitMask; // enable 'R'
  953. } else { // 'R' enabled, 'L' - NOT
  954. c_ &= ~RBitMask; // disable 'R'
  955. c_ |= LBitMask; // enable 'L'
  956. }
  957. }
  958. RBitMask <<= 1U;
  959. }
  960. return static_cast<unsigned char>(c_);
  961. }
  962.  
  963. // Effective, uses lookup table (const complexity)
  964. // [http://stackoverflow.com/questions/746171/best-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c]
  965. static unsigned char ReverseBitsInByteEx(const unsigned char c) throw() {
  966. static const unsigned char LOOKUP_TABLE[] = {
  967. 0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
  968. 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
  969. 0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
  970. 0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
  971. 0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
  972. 0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
  973. 0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
  974. 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
  975. 0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
  976. 0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
  977. 0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
  978. 0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
  979. 0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
  980. 0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
  981. 0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
  982. 0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF };
  983. return LOOKUP_TABLE[c];
  984. }
  985.  
  986. struct ReverseBitsInByteExFunctor {
  987. auto operator()(const unsigned char c) throw() -> decltype(ReverseBitsInByteEx(c)) {
  988. return ReverseBitsInByteEx(c);
  989. }
  990. };
  991.  
  992. // ANY integral num. types
  993. // Linear complexity in sizeof(TIntegralNumType)
  994. template <typename TIntegralNumType,
  995. typename TIntgeralNumPartType = unsigned char,
  996. class ReverseBitsInPartFunctor = ReverseBitsInByteExFunctor>
  997. static TIntegralNumType ReverseBits(const TIntegralNumType num) throw() {
  998. static_assert(1U == sizeof(unsigned char), "'unsigned char' type SHOULD be 1 byte long!");
  999. // SHOULD fits perfectly
  1000. static_assert(!(sizeof(decltype(num)) % sizeof(TIntgeralNumPartType)),
  1001. "Size of 'num' type SHOULD be even size of 'TIntgeralNumPartType'");
  1002. typedef typename std::remove_const<decltype(num)>::type TMutableNumType;
  1003. union Converter {
  1004. TMutableNumType i;
  1005. // Sizeof(char) is ALWAYS 1U, considering to the CPP standart
  1006. // 'sizeof(decltype(num))' obviously SHOULD be larger then
  1007. // 'sizeof(TIntgeralNumPartType)' OR compile error
  1008. TIntgeralNumPartType c[sizeof(decltype(num)) / sizeof(TIntgeralNumPartType)];
  1009. } resultConverter, originalConverter;
  1010. originalConverter.i = num;
  1011. static const auto COUNT = std::extent<decltype(resultConverter.c)>::value;
  1012.  
  1013. TIntgeralNumPartType currOriginalPart;
  1014. ReverseBitsInPartFunctor bitReversingFunctor;
  1015. //// Reversing algo.: 1) reverse parts 2) reverse bits in parts
  1016. for (size_t partIdx = 0U; partIdx < COUNT; ++partIdx) {
  1017. currOriginalPart =
  1018. originalConverter.c[COUNT - partIdx - 1U]; // reverse the part order
  1019. resultConverter.c[partIdx] =
  1020. bitReversingFunctor(currOriginalPart); // reverse the bit order
  1021. }
  1022. return resultConverter.i;
  1023. }
  1024.  
  1025. // Just like 'ReverseBits', BUT uses dynamically generated AND larger lookup table
  1026. // Thread safe; const complexity, should be faster, then 'ReverseBits'
  1027. // [!] Size of 'TIntegralNumType' SHOULD divisible by 2 [!]
  1028. template <typename TIntegralNumType>
  1029. static TIntegralNumType ReverseBitsEx(const TIntegralNumType num) throw() {
  1030. static_assert(2U == sizeof(uint16_t), "'uint16_t' SHOULD be 2 bytes large!");
  1031. static uint16_t LOOKUP_TABLE[65536U]; // 2^16 items, total of 128 Kb
  1032. typedef std::decay<decltype(*LOOKUP_TABLE)>::type TPartType;
  1033. static const auto COUNT = std::extent<decltype(LOOKUP_TABLE)>::value;
  1034.  
  1035. static std::atomic<bool> LOOKUP_TABLE_FILLED = false;
  1036. static std::mutex MUTEX;
  1037.  
  1038. auto fillLookupTable = [&]() throw() {
  1039.  
  1040. union Separator {
  1041. TPartType ui;
  1042. unsigned char ucs[sizeof(TPartType)];
  1043. } separator = {0};
  1044. static_assert(sizeof(separator) <= sizeof(size_t),
  1045. "'size_t' SHOULD be large enough!");
  1046.  
  1047. // Zero item inited with zeroes as a static
  1048. for (size_t idx = 1U; idx < COUNT; ++idx) {
  1049. separator.ui = idx;
  1050.  
  1051. *separator.ucs =
  1052. ReverseBitsInByteEx(*separator.ucs); // first, reverse bits order
  1053. separator.ucs[1U] =
  1054. ReverseBitsInByteEx(separator.ucs[1U]); // from the small lookup table
  1055. std::swap(*separator.ucs, separator.ucs[1U]); // second, reverse the bytes order
  1056.  
  1057. LOOKUP_TABLE[idx] = separator.ui;
  1058. }
  1059. LOOKUP_TABLE_FILLED = true;
  1060. };
  1061.  
  1062. if (!LOOKUP_TABLE_FILLED) { // if first launch, atomic flag check will
  1063. const std::lock_guard<decltype(MUTEX)> autoLock(MUTEX);
  1064. if (!LOOKUP_TABLE_FILLED) fillLookupTable(); // double checking lock
  1065. }
  1066.  
  1067. struct ReverseBitsInWordFunctor { // word = 2 bytes
  1068. auto operator()(const TPartType num) throw() -> decltype(LOOKUP_TABLE[num]) {
  1069. return LOOKUP_TABLE[num];
  1070. }
  1071. };
  1072.  
  1073. return ReverseBits<decltype(num), TPartType, ReverseBitsInWordFunctor>(num);
  1074. }
  1075.  
  1076. class BitOrderTester {
  1077.  
  1078. public:
  1079.  
  1080. static const BitOrderTester INSTANCE;
  1081.  
  1082. bool reversedBitOrder = false;
  1083.  
  1084. private:
  1085.  
  1086. BitOrderTester() throw() {
  1087. // sizeof(char) SHOULD be ALWAYS 1U, due to the CPP standart
  1088. static_assert(sizeof(char) == 1U, "'char' type is NOT 1 byte large!");
  1089. static_assert(sizeof(int) > sizeof('A'), "Too small 'int' size");
  1090.  
  1091. union Converter {
  1092. int i;
  1093. char c[sizeof(decltype(i))];
  1094. } converter = {0};
  1095.  
  1096. *converter.c = 'A'; // sets zero byte - then test is zero byte LSB OR MSB
  1097. // true if zero byte considered LSB (least significant byte)
  1098. // => the bit order is left <- right (3-th byte is MSB - most significant byte)
  1099. reversedBitOrder = ('A' == converter.i);
  1100. }
  1101.  
  1102. ~BitOrderTester() = default;
  1103.  
  1104. BitOrderTester(const BitOrderTester&) throw() = delete;
  1105. BitOrderTester(BitOrderTester&&) throw() = delete;
  1106. BitOrderTester& operator=(const BitOrderTester&) throw() = delete;
  1107. BitOrderTester& operator=(BitOrderTester&&) throw() = delete;
  1108. };
  1109.  
  1110. enum class ECompareStrategy {
  1111. CS_LEFT_TO_RIGHT, // direct
  1112. CS_RIGHT_TO_LEFT, // reversed
  1113. CS_SHUFFLE_CONVERGING, // right-left-right etc, edges -> center
  1114. CS_SHUFFLE_DIVERGENT // middle, right-left-right etc, center -> edges
  1115. };
  1116.  
  1117. template<class T>
  1118. typename std::enable_if<(sizeof(T) < 2U)>::type // 1 byte size
  1119. static ReverseBytes(T& obj) throw() {} // nothing to reverse
  1120.  
  1121. template<class T>
  1122. typename std::enable_if<(sizeof(T) > 1U)>::type // 2, 4, 8
  1123. static ReverseBytes(T& obj) throw() {
  1124. ReverseBytes_(obj);
  1125. }
  1126.  
  1127. //// [!] 'fastCompareMemChunks' AND 'compareMem' - BAD concept, slow, do NOT use [!]
  1128.  
  1129. // [!] WARNING: looks like can be slower then 'strcmp' OR 'memcmp' [!]
  1130. // 'SampleChunkSize' SHOULD be {1, 2, 4, 8}
  1131. // If 'stopAtZeroBlock' is true - comparison will end when the first zeroised mem. chunk is met,
  1132. // use it when comparing two arrays (with the known size) of a POD C strs.
  1133. // (end of arrays SHOULD be zeroised!) [OPTIMIZATION]
  1134. // Set 'KeepByteOrder' when the real diff. value of the mem. chunks
  1135. // is imprtnat (NOT just the fact of diff. itself)
  1136. template<const size_t SampleChunkSize, const bool SignedSample = true,
  1137. const bool KeepByteOrder = false>
  1138. static long long int
  1139. fastCompareMemChunks(const void* const chunk1, const void* const chunk2, size_t iterCount,
  1140. const ECompareStrategy cmpStrat = ECompareStrategy::CS_SHUFFLE_CONVERGING,
  1141. const bool stopAtZeroBlock = false) throw()
  1142. {
  1143. static_assert(1U == SampleChunkSize || 2U == SampleChunkSize ||
  1144. 4U == SampleChunkSize || 8U == SampleChunkSize,
  1145. "Invalid 'SampleChunkSize' template param. for 'fastCompareMemChunks'");
  1146. typedef typename IntegralTypeBySize<SampleChunkSize, SignedSample>::Type TSampleChunkType;
  1147.  
  1148. if (!iterCount || chunk1 == chunk2) return 0LL;
  1149. if (!chunk1 || !chunk2)
  1150. return (reinterpret_cast<long long int>(chunk1) - reinterpret_cast<long long int>(chunk2));
  1151.  
  1152. //// When converting between two pointer types, it's possible that
  1153. //// the specific memory address held in the pointer needs to change
  1154. //// 'static_cast will' make the appropriate adjustment,
  1155. //// 'reinterpret_cast' will avoid changing the pointer's stored value
  1156. auto chunk1Re = reinterpret_cast<const TSampleChunkType*>(chunk1);
  1157. auto chunk2Re = reinterpret_cast<const TSampleChunkType*>(chunk2);
  1158.  
  1159. TSampleChunkType elem1, elem2;
  1160.  
  1161. const auto iterCountIsEven = !(iterCount % 2U);
  1162. // If iter. count is even - separately chek the uncheked
  1163. // (first in the seq.) elem. (ONLY for CS_SHUFFLE_DIVERGENT)
  1164. // Special case to NOT overlook the first elem.
  1165. if (ECompareStrategy::CS_SHUFFLE_DIVERGENT == cmpStrat && iterCountIsEven) {
  1166. elem1 = *chunk1Re, elem2 = *chunk2Re;
  1167. // If 'KeepByteOrder' used for strs lower cmp.
  1168. if (KeepByteOrder && BitOrderTester::INSTANCE.reversedBitOrder) {
  1169. ReverseBytes(elem1), ReverseBytes(elem2);
  1170. }
  1171. if (elem1 != elem2) // compare first elems
  1172. return static_cast<long long int>(elem1) - static_cast<long long int>(elem2);
  1173. if (1U == iterCount) return 0LL; // the single elem. which was checked above
  1174. }
  1175. const auto lastIterIdx = iterCount - 1U;
  1176. const auto middleElemIdx = iterCount / 2U;
  1177.  
  1178. ptrdiff_t ptrShift = 1; // per iteration; 'CS_LEFT_TO_RIGHT' by default (from start)
  1179. // Shift (per 2 iters) of the 'ptrShift' itself (ONLY for the shuffle strats)
  1180. ptrdiff_t ptrShiftShift = 0;
  1181. bool shuffleStrat = false;
  1182.  
  1183. auto prepare = [&]() throw() {
  1184. switch (cmpStrat) {
  1185. case ECompareStrategy::CS_RIGHT_TO_LEFT:
  1186. chunk1Re += lastIterIdx, chunk2Re += lastIterIdx; // move to the END
  1187. ptrShift = -1; // from the end
  1188. break;
  1189.  
  1190. case ECompareStrategy::CS_SHUFFLE_CONVERGING:
  1191. shuffleStrat = true;
  1192. chunk1Re += lastIterIdx, chunk2Re += lastIterIdx; // shift to the END
  1193. ptrShift = 0 - lastIterIdx;
  1194. ptrShiftShift = -1; // converging
  1195. break;
  1196.  
  1197. case ECompareStrategy::CS_SHUFFLE_DIVERGENT:
  1198. shuffleStrat = true;
  1199. chunk1Re += middleElemIdx, chunk2Re += middleElemIdx; // shift to the middle
  1200. ptrShift = 1;
  1201. ptrShiftShift = 1; // diverging
  1202. // [!] Special case - the very first elem. was already checked [!]
  1203. if (iterCountIsEven) --iterCount;
  1204. break;
  1205. }
  1206. };
  1207. prepare();
  1208.  
  1209. for (size_t iterIdx = 0U; iterIdx < iterCount; ++iterIdx) {
  1210. elem1 = *chunk1Re, elem2 = *chunk2Re;
  1211. // 'KeepByteOrder' used for strs lower cmp.
  1212. if (KeepByteOrder && BitOrderTester::INSTANCE.reversedBitOrder) {
  1213. ReverseBytes(elem1), ReverseBytes(elem2);
  1214. }
  1215. if ((stopAtZeroBlock && !elem1) || elem1 != elem2)
  1216. return static_cast<long long int>(elem1) - static_cast<long long int>(elem2);
  1217.  
  1218. chunk1Re += ptrShift, chunk2Re += ptrShift;
  1219. if (shuffleStrat) {
  1220. ptrShift = -ptrShift; // reverse
  1221. ptrShift += (ptrShift < 0) ? -ptrShiftShift : ptrShiftShift; // shift shifter
  1222. }
  1223. }
  1224. return 0LL;
  1225. }
  1226.  
  1227. // Returns sizeof(T), where T - is an unsigned integral type,
  1228. // which meets the condition '0U == toFitSize % sizeof(T)'
  1229. // 'fitsRegister' flag used for OPTIMIZATION,
  1230. // true by default AND should possibly never be torned off
  1231. /* EXPLANATION:
  1232.   If a type is bigger than a register, then simple arithmetic operations
  1233.   would require more than one instruction
  1234.   If it is smaller than a register, then loading and storing the values of a register
  1235.   would require the program to mask out the unused bits,
  1236.   to avoid overwriting other data
  1237.   */
  1238. static size_t GetLargestFittableUIntSize(const size_t toFitSize,
  1239. const bool fitsRegister = true) throw()
  1240. {
  1241. // C++ standart guarantees char to be 1 byte long
  1242. static_assert(1U == sizeof(unsigned char),
  1243. "'unsigned char' SHOULD be 1 byte long");
  1244. static const size_t TYPE_SIZES[]
  1245. = {sizeof(unsigned long long int), sizeof(unsigned long int),
  1246. sizeof(unsigned int), sizeof(unsigned short int), sizeof(unsigned char)};
  1247.  
  1248. for (const auto typeSize : TYPE_SIZES) {
  1249. if (!(toFitSize % typeSize)) { // fits size
  1250.  
  1251. // SHOULD be placeable in to the CPU register (which is typically sizeof(int) large)
  1252. if (fitsRegister) {
  1253. // TO DO: better use '__cpuid' intrinsic
  1254. // to determine if underlying processor is actually 64-bit
  1255. if (sizeof(int) >= typeSize) return typeSize; // fits (effectively OR NOT)
  1256. } else return typeSize;
  1257. }
  1258. }
  1259. assert(false); // critical failure
  1260. return size_t();
  1261. }
  1262.  
  1263. // [!] WARNING: looks like can be slower then 'strcmp' OR 'memcmp' [!]
  1264. // 'chunk1Size' AND 'chunk2Size' is in bytes
  1265. // Set ANY of 'chunk1Size' OR 'chunk2Size' to zero if it represents
  1266. // a null-terminated str. which actuall len. is unknown
  1267. // (the comparison will goes up to a terminating char in this caze)
  1268. // If the chunks compared NOT like a strs -
  1269. // chuks with the diff. sizes considered clearly diffirent
  1270. // Returns diff. between the two last unmatched subchunks of mem.
  1271. // (NOT between the two last unmatched elems!!)
  1272. // See 'stopAtZeroBlock' description at 'fastCompareMemChunks'
  1273. // 'stopAtZeroBlock' AND 'cmpStrat' used ONLY if comparing NOT as a strs.
  1274. // (if BOTH mem. blocks size is known), otherwise ignored
  1275. // Use this to compare strs with the diff. char types
  1276. // 'SignednessCompare' meaningfull ONLY if NOT compared as a strs (if raw compare)
  1277. // See 'KeepByteOrder' descr. at 'fastCompareMemChunks' func. descr.
  1278. template<const bool SignednessCompare = false, const bool KeepByteOrder = false,
  1279. typename TElemType1, class TElemType2>
  1280. static long long int compareMem(const TElemType1* chunk1, const size_t chunk1Size,
  1281. const TElemType2* chunk2, const size_t chunk2Size,
  1282. const ECompareStrategy cmpStrat =
  1283. ECompareStrategy::CS_SHUFFLE_CONVERGING,
  1284. const bool stopAtZeroBlock = false) throw()
  1285. {
  1286. if (static_cast<const void*>(chunk1) == static_cast<const void*>(chunk2)) return 0LL;
  1287. if (!chunk1 || !chunk2)
  1288. return (reinterpret_cast<long long int>(chunk1) - reinterpret_cast<long long int>(chunk2));
  1289.  
  1290. // Size is in bytes; true if actuall len. is unknown
  1291. const auto compareAsStrs = !chunk1Size || !chunk2Size;
  1292.  
  1293. auto compareStrs = [&]() throw() {
  1294. while (true) {
  1295. if (!*chunk1 || (*chunk1 != *chunk2)) {
  1296. if (SignednessCompare) {
  1297. const unsigned long long int ui1 = *chunk1, ui2 = *chunk2;
  1298. return static_cast<long long int>(ui1) - static_cast<long long int>(ui2);
  1299. } else {
  1300. return static_cast<long long int>(*chunk1) - static_cast<long long int>(*chunk2);
  1301. }
  1302. }
  1303. ++chunk1, ++chunk2;
  1304. }
  1305. };
  1306.  
  1307. // 'chunk1Size' AND 'chunk2Size' SHOULD be equal AND NOT zero!!
  1308. auto rawCompare = [&]() throw() {
  1309. // TO DO: better determine underlying processor's actual size
  1310. // of the register (CPU bit's count), then simply using 'int'
  1311. typedef int TCPURegType; // signedness??
  1312.  
  1313. // End tail size (NOT fitted into the main comparing sequence)
  1314. const auto restBytesCount = chunk1Size % sizeof(TCPURegType);
  1315.  
  1316. // Firstly, compare the rest tail at the end
  1317. auto firstComparingStage = [&]() throw() {
  1318. auto chunk1Shifted = reinterpret_cast<const char*>(chunk1);
  1319. auto chunk2Shifted = reinterpret_cast<const char*>(chunk2);
  1320. const auto skipBytesCount = chunk1Size - restBytesCount;
  1321. chunk1Shifted += skipBytesCount, chunk2Shifted += skipBytesCount; // shift ptrs. to the tail
  1322.  
  1323. // If 'short int' is fittable into the tail
  1324. if (!(restBytesCount % sizeof(unsigned short int))) {
  1325. return fastCompareMemChunks<sizeof(short int), !SignednessCompare, KeepByteOrder>
  1326. (chunk1Shifted, chunk2Shifted, restBytesCount / sizeof(short int), // int >= short int
  1327. cmpStrat, stopAtZeroBlock);
  1328. }
  1329. // 'sizeof(char)' SHOULD be ALWAYS 1U according to the CPP standart
  1330. return fastCompareMemChunks<sizeof(char), !SignednessCompare, KeepByteOrder>
  1331. (chunk1Shifted, chunk2Shifted, restBytesCount / sizeof(char), // short int >= char
  1332. cmpStrat, stopAtZeroBlock);
  1333. };
  1334. if (restBytesCount) { // tail exist - exec. the first stage
  1335. const auto firstComparingStageResult = firstComparingStage();
  1336. if (firstComparingStageResult)
  1337. return firstComparingStageResult; // if NOT equal (return diff.)
  1338. }
  1339. // If tail is NOT the whole sequence - exec. second comparing stage
  1340. if (restBytesCount < chunk1Size) {
  1341. return fastCompareMemChunks<sizeof(TCPURegType), !SignednessCompare, KeepByteOrder>
  1342. (chunk1, chunk2, chunk1Size / sizeof(TCPURegType), cmpStrat, stopAtZeroBlock);
  1343. }
  1344. return 0LL; // tail is the whole sequence AND equal
  1345. };
  1346.  
  1347. if (!compareAsStrs) {
  1348. // If the chunks compared NOT like a strs -
  1349. // chuks with the diff. sizes considered clearly diffirent
  1350. if (chunk1Size != chunk2Size) return chunk1Size - chunk2Size;
  1351. return rawCompare();
  1352. } else {
  1353. // Comparing elem-to-elem from start to end, up to a str. terminator (zero elem.)
  1354. return compareStrs();
  1355. }
  1356. }
  1357.  
  1358. private:
  1359.  
  1360. MathUtils() throw() = delete;
  1361. ~MathUtils() throw() = delete;
  1362. MathUtils(const MathUtils&) throw() = delete;
  1363. MathUtils(MathUtils&&) throw() = delete;
  1364. MathUtils& operator=(const MathUtils&) throw() = delete;
  1365. MathUtils& operator=(MathUtils&&) throw() = delete;
  1366.  
  1367. // For 'getBitCountEx' ONLY
  1368. // [!] Does NOT thread safe, lazy init. [!]
  1369. static const BitCount* getBitCountsLookupTable() throw() {
  1370. static bool INITED = false;
  1371. static BitCount COUNTS[65536U]; // for 2 bytes [65 kb * 4 = 260 Kbytes]
  1372. static const auto COUNT = std::extent<decltype(COUNTS)>::value;
  1373.  
  1374. if (!INITED) {
  1375. for (size_t idx = 0U; idx < COUNT; ++idx) {
  1376. getBitCount(idx, COUNTS[idx]);
  1377. }
  1378. INITED = true;
  1379. }
  1380. return COUNTS;
  1381. }
  1382.  
  1383. template <typename T>
  1384. static void ReverseBytes_(T& obj) throw() {
  1385. static_assert(sizeof(T) && !(sizeof(T) % 2U), "Size of type 'T' SHOULD be multiple of 2!");
  1386. static const auto STOP_BYTE_IDX = sizeof(T) / 2U;
  1387.  
  1388. /* OK conversion [http://e...content-available-to-author-only...e.com/w/cpp/language/reinterpret_cast](see 'Type aliasing')
  1389.   AliasedType is char or unsigned char:
  1390.   this permits examination of the object representation of any object as an array of unsigned char
  1391.   */
  1392. auto const data = reinterpret_cast<unsigned char*>(&obj);
  1393. for (size_t currByteIdx = 0U; currByteIdx < STOP_BYTE_IDX; ++currByteIdx) {
  1394. std::swap(data[currByteIdx], data[(sizeof(T) - 1U) - currByteIdx]);
  1395. }
  1396. }
  1397. };
  1398.  
  1399. const MathUtils::BitOrderTester MathUtils::BitOrderTester::INSTANCE;
  1400.  
  1401. #include <iostream>
  1402.  
  1403. int main() {
  1404. for (size_t i = 0U; i < 10U; ++i) {
  1405. assert(MathUtils::getTenPositiveDegree(i) == std::pow(10.0, i));
  1406. }
  1407. for (size_t power = 0U; power < 10U; ++power) {
  1408. assert(std::pow(2.0, power) == MathUtils::getPowerOf2(power));
  1409. }
  1410. auto flag = false;
  1411. auto digit_1_ = MathUtils::getDigitOfOrder(3U, 10345LL, flag);
  1412. assert(!digit_1_);
  1413. assert(!flag);
  1414. ////
  1415. char buf[24U] = {'\0'};;
  1416. auto zeroDigitsCount2 = size_t();
  1417. size_t countByDigit[10U] = {0};
  1418.  
  1419. // 123456789
  1420. auto returnPtr = "";
  1421. auto n2 = 123456789LL;
  1422. auto n2_initial_ = n2;
  1423. auto count2 = size_t();
  1424. memset(buf, 0, sizeof(buf));
  1425. memset(countByDigit, 0, sizeof(countByDigit));
  1426. returnPtr = MathUtils::getArrayOfDigits(n2, count2, buf,
  1427. std::extent<decltype(buf)>::value,
  1428. countByDigit, true);
  1429.  
  1430. const size_t countByDigit_TEST1[] = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1};
  1431. assert(!memcmp(countByDigit, countByDigit_TEST1, sizeof(countByDigit)));
  1432.  
  1433. assert(0U == *countByDigit);
  1434. assert(returnPtr >= buf);
  1435. assert(count2 < std::extent<decltype(buf)>::value);
  1436. assert(count2 == strlen(returnPtr));
  1437. assert(atoll(returnPtr) == n2_initial_);
  1438. assert(!n2);
  1439. std::cout << n2_initial_ << " = " << returnPtr << std::endl;
  1440. ////
  1441. auto num3 = 90980000LL;
  1442. auto skippedDigitsCount = 0U;
  1443. MathUtils::rewindToFirstNoneZeroDigit(num3, skippedDigitsCount);
  1444. assert(4U == skippedDigitsCount);
  1445. assert(9098LL == num3);
  1446. ////
  1447. assert(34 == MathUtils::getLastNDigitsOfNum(2U, 1234));
  1448. assert(0L == MathUtils::getLastNDigitsOfNum(0U, 1234L));
  1449. assert(2LL == MathUtils::getLastNDigitsOfNum(1U, -6732LL));
  1450. assert(12 == MathUtils::getLastNDigitsOfNum(325U, 12));
  1451. ////
  1452. assert(0 == MathUtils::getFirstNDigitsOfNum(0U, 6428));
  1453. assert(0 == MathUtils::getFirstNDigitsOfNum(56453U, 0));
  1454. assert(0L == MathUtils::getFirstNDigitsOfNum(0U, 0L));
  1455. assert(0LL == MathUtils::getFirstNDigitsOfNum(97U, 0LL));
  1456. ////
  1457. size_t results_0004[] = {1U, 2U, 3U, 4U, 5U, 6U, 7U, 8U};
  1458. auto resultsCount_0004 = std::extent<decltype(results_0004)>::value;
  1459. auto num_0004 = 343580602368ULL;
  1460. auto num_0004Copy = num_0004;
  1461. MathUtils::parseNum(num_0004, 1024U, nullptr, results_0004, resultsCount_0004);
  1462. assert(!num_0004);
  1463. assert(4U == resultsCount_0004);
  1464. assert(319U == results_0004[3U]);
  1465.  
  1466. auto num_0004Copy2 = 0ULL;
  1467. auto k = 1ULL;
  1468. for (auto idx = 0U; idx < resultsCount_0004; ++idx) {
  1469. num_0004Copy2 += results_0004[idx] * k;
  1470. k *= 1024ULL;
  1471. }
  1472. assert(num_0004Copy2 == num_0004Copy);
  1473. ////
  1474. std::string dateTimeStr_001 = "date/time:";
  1475. MathUtils::addFormattedDateTimeStr(1234567890ULL, dateTimeStr_001, false);
  1476. std::cout << 1234567890 << " = " << dateTimeStr_001 << std::endl;
  1477. ////
  1478. MathUtils::BitCount bc;
  1479. // 1100000001010111111110100000000110000100010010000001111010001
  1480. MathUtils::getBitCount(1732477657834652625LL, bc);
  1481. assert(24U == bc.positive);
  1482. assert(61U == bc.total);
  1483. ////
  1484. assert(127 == MathUtils::getBitMask(7, false));
  1485. assert(8388607 == MathUtils::getBitMask(23, false));
  1486.  
  1487. auto temp1 = std::pow(2.0, 63.0);
  1488. assert(temp1 == MathUtils::getBitMask(1, true));
  1489. temp1 += std::pow(2.0, 62.0);
  1490. temp1 += std::pow(2.0, 61.0);
  1491. auto temp2 = MathUtils::getBitMask(3, true);
  1492. assert(temp1 == temp2);
  1493. temp1 += std::pow(2.0, 60.0);
  1494. temp1 += std::pow(2.0, 59.0);
  1495. temp1 += std::pow(2.0, 58.0);
  1496. temp1 += std::pow(2.0, 57.0);
  1497. temp2 = MathUtils::getBitMask(7, true);
  1498. assert(temp1 == temp2);
  1499. ////
  1500. auto v_01 = 0ULL, v_02 = 0ULL;
  1501. auto v_01b = 0UL, v_02b = 0UL;
  1502. // 1 + 8 + 256 + 32 768 + 17 592 186 044 416 = 17 592 186 077 449
  1503. const size_t idxs1[] = {0U, 3U, 8U, 15U, 44U};
  1504. MathUtils::setBits(v_01, idxs1);
  1505. v_02 = 0ULL;
  1506. for (double idx : idxs1) {
  1507. v_02 |= static_cast<decltype(v_02)>(std::pow(2.0, idx));
  1508. }
  1509. assert(v_01 == v_02);
  1510. ////
  1511. auto lastMeaningIdx = 0;
  1512. // 0001 0110 0111 0001 1110 0000 0000 1111 1011 0101 1011 0000 0010
  1513. auto num_03 = 394853539863298ULL;
  1514. const size_t partSizes_3[] = {7U, 2U, 16U, 10U, 1U, 19U, 5U}; // 60
  1515. size_t parts_3[std::extent<decltype(partSizes_3)>::value] = {123456789};
  1516. lastMeaningIdx = MathUtils::parseByBitsEx(num_03, partSizes_3, parts_3);
  1517.  
  1518. assert(5 == lastMeaningIdx); // total meaning: 6
  1519. assert(!num_03);
  1520.  
  1521. assert( 2U == parts_3[0U]); // 0000010
  1522. assert( 2U == parts_3[1U]); // 10
  1523. assert(32173U == parts_3[2U]); // 0111110110101101
  1524. assert( 768U == parts_3[3U]); // 1100000000
  1525. assert( 1U == parts_3[4U]); // 1
  1526. assert( 5745U == parts_3[5U]); // 0000001011001110001
  1527. ////
  1528. char strBuf_003[32U] = {0};
  1529. char* strBufPtr_003 = nullptr;
  1530. // 1111110010101011110111111000001110101011001000010110101100100011
  1531. auto num_006 = -239852398529385693LL;
  1532. auto num_006_copy_ = num_006;
  1533. char strBuf_004[64U + 8U] = {0};
  1534. strBufPtr_003 = MathUtils::getBitStr(num_006, strBuf_004, std::extent<decltype(strBuf_004)>::value);
  1535. assert(!strcmp(strBufPtr_003,
  1536. "1111110010101011110111111000001110101011001000010110101100100011"));
  1537. assert(!num_006);
  1538. std::cout << num_006_copy_ << " =\n\t" << strBufPtr_003 << std::endl;
  1539. ////
  1540. auto c_23_ = '\0';
  1541. auto res_23_ = MathUtils::ReverseBitsInByte(88U);
  1542. assert(26U == res_23_); // 0101 1000 -> 0001 1010
  1543. assert(26U == MathUtils::ReverseBitsInByteEx(88U));
  1544. c_23_ = 88;
  1545. assert(26 == MathUtils::ReverseBits(c_23_));
  1546. ////
  1547. assert(!MathUtils::XOR(true, true));
  1548. assert(!MathUtils::XOR(false, false));
  1549. assert(MathUtils::XOR(true, false));
  1550. assert(MathUtils::XOR(false, true));
  1551.  
  1552. return 0;
  1553. }
Success #stdin #stdout 0s 3468KB
stdin
Standard input is empty
stdout
123456789 = 123456789
1234567890 = date/time: 39 yr 8 mon 8 d 23 hr 31 min 30 sec
-239852398529385693 =
	1111110010101011110111111000001110101011001000010110101100100011