9
3

my_bit.h 3.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135
  1. /* Copyright (c) 2007, 2011, Oracle and/or its affiliates.
  2. Copyright (c) 2009-2011, Monty Program Ab
  3. This program is free software; you can redistribute it and/or modify
  4. it under the terms of the GNU General Public License as published by
  5. the Free Software Foundation; version 2 of the License.
  6. This program is distributed in the hope that it will be useful,
  7. but WITHOUT ANY WARRANTY; without even the implied warranty of
  8. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  9. GNU General Public License for more details.
  10. You should have received a copy of the GNU General Public License
  11. along with this program; if not, write to the Free Software
  12. Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
  13. #ifndef MY_BIT_INCLUDED
  14. #define MY_BIT_INCLUDED
  15. #include <my_global.h>
  16. /*
  17. Some useful bit functions
  18. */
  19. C_MODE_START
  20. extern const char _my_bits_nbits[256];
  21. extern const uchar _my_bits_reverse_table[256];
  22. /*
  23. Find smallest X in 2^X >= value
  24. This can be used to divide a number with value by doing a shift instead
  25. */
  26. static inline uint my_bit_log2(ulong value)
  27. {
  28. uint bit;
  29. for (bit=0 ; value > 1 ; value>>=1, bit++) ;
  30. return bit;
  31. }
  32. static inline uint my_count_bits(ulonglong v)
  33. {
  34. #if SIZEOF_LONG_LONG > 4
  35. /* The following code is a bit faster on 16 bit machines than if we would
  36. only shift v */
  37. ulong v2=(ulong) (v >> 32);
  38. return (uint) (uchar) (_my_bits_nbits[(uchar) v] +
  39. _my_bits_nbits[(uchar) (v >> 8)] +
  40. _my_bits_nbits[(uchar) (v >> 16)] +
  41. _my_bits_nbits[(uchar) (v >> 24)] +
  42. _my_bits_nbits[(uchar) (v2)] +
  43. _my_bits_nbits[(uchar) (v2 >> 8)] +
  44. _my_bits_nbits[(uchar) (v2 >> 16)] +
  45. _my_bits_nbits[(uchar) (v2 >> 24)]);
  46. #else
  47. return (uint) (uchar) (_my_bits_nbits[(uchar) v] +
  48. _my_bits_nbits[(uchar) (v >> 8)] +
  49. _my_bits_nbits[(uchar) (v >> 16)] +
  50. _my_bits_nbits[(uchar) (v >> 24)]);
  51. #endif
  52. }
  53. static inline uint my_count_bits_uint32(uint32 v)
  54. {
  55. return (uint) (uchar) (_my_bits_nbits[(uchar) v] +
  56. _my_bits_nbits[(uchar) (v >> 8)] +
  57. _my_bits_nbits[(uchar) (v >> 16)] +
  58. _my_bits_nbits[(uchar) (v >> 24)]);
  59. }
  60. /*
  61. Next highest power of two
  62. SYNOPSIS
  63. my_round_up_to_next_power()
  64. v Value to check
  65. RETURN
  66. Next or equal power of 2
  67. Note: 0 will return 0
  68. NOTES
  69. Algorithm by Sean Anderson, according to:
  70. http://graphics.stanford.edu/~seander/bithacks.html
  71. (Orignal code public domain)
  72. Comments shows how this works with 01100000000000000000000000001011
  73. */
  74. static inline uint32 my_round_up_to_next_power(uint32 v)
  75. {
  76. v--; /* 01100000000000000000000000001010 */
  77. v|= v >> 1; /* 01110000000000000000000000001111 */
  78. v|= v >> 2; /* 01111100000000000000000000001111 */
  79. v|= v >> 4; /* 01111111110000000000000000001111 */
  80. v|= v >> 8; /* 01111111111111111100000000001111 */
  81. v|= v >> 16; /* 01111111111111111111111111111111 */
  82. return v+1; /* 10000000000000000000000000000000 */
  83. }
  84. static inline uint32 my_clear_highest_bit(uint32 v)
  85. {
  86. uint32 w=v >> 1;
  87. w|= w >> 1;
  88. w|= w >> 2;
  89. w|= w >> 4;
  90. w|= w >> 8;
  91. w|= w >> 16;
  92. return v & w;
  93. }
  94. static inline uint32 my_reverse_bits(uint32 key)
  95. {
  96. return
  97. (_my_bits_reverse_table[ key & 255] << 24) |
  98. (_my_bits_reverse_table[(key>> 8) & 255] << 16) |
  99. (_my_bits_reverse_table[(key>>16) & 255] << 8) |
  100. _my_bits_reverse_table[(key>>24) ];
  101. }
  102. /*
  103. a number with the n lowest bits set
  104. an overflow-safe version of (1 << n) - 1
  105. */
  106. static inline uint32 my_set_bits(int n)
  107. {
  108. return (((1UL << (n - 1)) - 1) << 1) | 1;
  109. }
  110. C_MODE_END
  111. #endif /* MY_BIT_INCLUDED */