1
0

Bits.h 4.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158
  1. /* vim: set expandtab ts=4 sw=4: */
  2. /*
  3. * You may redistribute this program and/or modify it under the terms of
  4. * the GNU General Public License as published by the Free Software Foundation,
  5. * either version 3 of the License, or (at your option) any later version.
  6. *
  7. * This program is distributed in the hope that it will be useful,
  8. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  9. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  10. * GNU General Public License for more details.
  11. *
  12. * You should have received a copy of the GNU General Public License
  13. * along with this program. If not, see <https://www.gnu.org/licenses/>.
  14. */
  15. #ifndef Bits_H
  16. #define Bits_H
  17. #include "util/Assert.h"
  18. #include "util/Gcc.h"
  19. #include "util/Linker.h"
  20. Linker_require("util/Bits.c")
  21. #include <stdint.h>
  22. #include <stddef.h>
  23. /**
  24. * Find first set bit in a 64 bit integer.
  25. */
  26. static inline int Bits_ffs64(uint64_t number)
  27. {
  28. if (!number) {
  29. return 0;
  30. }
  31. int out = 1;
  32. while (!(number & 1)) {
  33. number >>= 1;
  34. out++;
  35. }
  36. return out;
  37. }
  38. static inline int Bits_popCountx64(uint64_t number)
  39. {
  40. return __builtin_popcountll(number);
  41. }
  42. static inline int Bits_popCountx32(uint32_t number)
  43. {
  44. int out = 0;
  45. for (int i = 0; i < 32; i++) {
  46. out += ((number >> i) & 1);
  47. }
  48. return out;
  49. }
  50. static inline int Bits_log2x64(uint64_t number)
  51. {
  52. if (!number) { return 0; }
  53. return 63 - __builtin_clzll(number);
  54. }
  55. int Bits_log2x64_stupid(uint64_t number);
  56. /** Largest possible number whose log2 is bitCount. */
  57. static inline uint64_t Bits_maxBits64(uint32_t bitCount)
  58. {
  59. Assert_ifParanoid(bitCount < 64);
  60. return (((uint64_t)1) << bitCount) - 1;
  61. }
  62. static inline int Bits_log2x32(uint32_t number)
  63. {
  64. int out = 0;
  65. while (number >>= 1) {
  66. out++;
  67. }
  68. return out;
  69. }
  70. /**
  71. * Bitwise reversal of the a number.
  72. * This is endian safe.
  73. */
  74. static inline uint64_t Bits_bitReverse64(uint64_t toReverse)
  75. {
  76. #define Bits_rotateAndMask(mask, rotateBits) \
  77. toReverse = ((toReverse >> rotateBits) & mask) | ((toReverse & mask) << rotateBits)
  78. Bits_rotateAndMask(0x5555555555555555ull, 1);
  79. Bits_rotateAndMask(0x3333333333333333ull, 2);
  80. Bits_rotateAndMask(0x0F0F0F0F0F0F0F0Full, 4);
  81. return __builtin_bswap64(toReverse);
  82. #undef Bits_rotateAndMask
  83. }
  84. /**
  85. * @param buffer the space of check if it's zero.
  86. * @length the nuber of bytes to check for zero'd-ness.
  87. * @return true if all bytes checked are zero.
  88. */
  89. static inline int Bits_isZero(const void* buffer, size_t length)
  90. {
  91. uint8_t* buff = (uint8_t*) buffer;
  92. for (size_t i = 0; i < length; i++) {
  93. if (buff[i]) {
  94. return 0;
  95. }
  96. }
  97. return 1;
  98. }
  99. #define Bits_memmove(a,b,c) __builtin_memmove(a,b,c)
  100. #define Bits_memset(a,b,c) __builtin_memset(a,b,c)
  101. #define Bits_memcmp(a,b,c) __builtin_memcmp(a,b,c)
  102. /**
  103. * Bits_memcpy()
  104. * Alias to POSIX memcpy(), allows for extra debugging checks.
  105. *
  106. * @param out buffer to write to.
  107. * @param in buffer to read from.
  108. * @param length number of bytes to copy.
  109. * @param file name of the file calling this, for logging.
  110. * @param line the line number of the calling file, for logging.
  111. * @param constant true if the length should be checked for being constant.
  112. * @return out
  113. */
  114. #define Bits_memcpy(a,b,c) Bits__memcpy(a,b,c,Gcc_SHORT_FILE,Gcc_LINE)
  115. static inline void* Bits__memcpy(void* out,
  116. const void* in,
  117. size_t length,
  118. char* file,
  119. int line)
  120. {
  121. const char* inc = in;
  122. const char* outc = out;
  123. // Check that pointers don't alias.
  124. if (outc >= inc && outc < inc + length) {
  125. Assert_failure("%s:%d: memcpy() pointers alias each other", file, line);
  126. }
  127. return __builtin_memcpy(out, in, length);
  128. }
  129. void* Bits_memmem(const void* haystack, size_t haystackLen, const void* needle, size_t needleLen);
  130. static inline uint16_t Bits_get16(uint8_t* bytes)
  131. {
  132. uint16_t x = 0;
  133. Bits_memcpy(&x, bytes, 2);
  134. return x;
  135. }
  136. static inline void Bits_put16(uint8_t* bytes, uint16_t num)
  137. {
  138. Bits_memcpy(bytes, &num, 2);
  139. }
  140. #endif