/src/server/include/my_bit.h

Source (jump to first uncovered line)
/* Copyright (c) 2007, 2011, Oracle and/or its affiliates.
   Copyright (c) 2009, 2020, MariaDB Corporation.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; version 2 of the License.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */

#ifndef MY_BIT_INCLUDED
#define MY_BIT_INCLUDED

/*
  Some useful bit functions
*/

C_MODE_START

extern const uchar _my_bits_reverse_table[256];


/*
  my_bit_log2_xxx()

  In the given value, find the highest bit set,
  which is the smallest X that satisfies the condition: (2^X >= value).
  Can be used as a reverse operation for (1<<X), to find X.

  Examples:
  - returns 0 for (1<<0)
  - returns 1 for (1<<1)
  - returns 2 for (1<<2)
  - returns 2 for 3, which has (1<<2) as the highest bit set.

  Note, the behaviour of log2(0) is not defined.
  Let's return 0 for the input 0, for the code simplicity.
  See the 000x branch. It covers both (1<<0) and 0.
*/
static inline CONSTEXPR uint my_bit_log2_hex_digit(uint8 value)
{
  return value & 0x0C ? /*1100*/ (value & 0x08 ? /*1000*/ 3 : /*0100*/ 2) :
                        /*0010*/ (value & 0x02 ? /*0010*/ 1 : /*000x*/ 0);
}
static inline CONSTEXPR uint my_bit_log2_uint8(uint8 value)
{
  return value & 0xF0 ? my_bit_log2_hex_digit((uint8) (value >> 4)) + 4:
                        my_bit_log2_hex_digit(value);
}
static inline CONSTEXPR uint my_bit_log2_uint16(uint16 value)
{
  return value & 0xFF00 ? my_bit_log2_uint8((uint8) (value >> 8)) + 8 :
                          my_bit_log2_uint8((uint8) value);
}
static inline CONSTEXPR uint my_bit_log2_uint32(uint32 value)
{
  return value & 0xFFFF0000UL ?
         my_bit_log2_uint16((uint16) (value >> 16)) + 16 :
         my_bit_log2_uint16((uint16) value);
}
static inline CONSTEXPR uint my_bit_log2_uint64(ulonglong value)
{
  return value & 0xFFFFFFFF00000000ULL ?
         my_bit_log2_uint32((uint32) (value >> 32)) + 32 :
         my_bit_log2_uint32((uint32) value);
}
static inline CONSTEXPR uint my_bit_log2_size_t(size_t value)
{
#ifdef __cplusplus
  static_assert(sizeof(size_t) <= sizeof(ulonglong),
                "size_t <= ulonglong is an assumption that needs to be fixed "
                "for this architecture. Please create an issue on "
                "https://jira.mariadb.org");
#endif
  return my_bit_log2_uint64((ulonglong) value);
}


/*
Count bits in 32bit integer

  Algorithm by Sean Anderson, according to:
  http://graphics.stanford.edu/~seander/bithacks.html
  under "Counting bits set, in parallel"

 (Original code public domain).
*/
static inline uint my_count_bits_uint32(uint32 v)
{
  v = v - ((v >> 1) & 0x55555555);
  v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
  return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
}


static inline uint my_count_bits(ulonglong x)
{
  return my_count_bits_uint32((uint32)x) + my_count_bits_uint32((uint32)(x >> 32));
}




/*
  Next highest power of two

  SYNOPSIS
    my_round_up_to_next_power()
    v   Value to check

  RETURN
    Next or equal power of 2
    Note: 0 will return 0

  NOTES
    Algorithm by Sean Anderson, according to:
    http://graphics.stanford.edu/~seander/bithacks.html
    (Original code public domain)

    Comments shows how this works with 01100000000000000000000000001011
*/

static inline uint32 my_round_up_to_next_power(uint32 v)
{
  v--;      /* 01100000000000000000000000001010 */
  v|= v >> 1;   /* 01110000000000000000000000001111 */
  v|= v >> 2;   /* 01111100000000000000000000001111 */
  v|= v >> 4;   /* 01111111110000000000000000001111 */
  v|= v >> 8;   /* 01111111111111111100000000001111 */
  v|= v >> 16;    /* 01111111111111111111111111111111 */
  return v+1;   /* 10000000000000000000000000000000 */
}

static inline uint32 my_clear_highest_bit(uint32 v)
{
  uint32 w=v >> 1;
  w|= w >> 1;
  w|= w >> 2;
  w|= w >> 4;
  w|= w >> 8;
  w|= w >> 16;
  return v & w;
}

static inline uint32 my_reverse_bits(uint32 key)
{
  return
    ((uint32)_my_bits_reverse_table[ key      & 255] << 24) |
    ((uint32)_my_bits_reverse_table[(key>> 8) & 255] << 16) |
    ((uint32)_my_bits_reverse_table[(key>>16) & 255] <<  8) |
     (uint32)_my_bits_reverse_table[(key>>24)      ];
}

/*
  a number with the n lowest bits set
  an overflow-safe version of  (1 << n) - 1
*/
static inline uint64 my_set_bits(int n)
{
  return (((1ULL << (n - 1)) - 1) << 1) | 1;
}

/* Create a mask of the significant bits for the last byte (1,3,7,..255) */
static inline uchar last_byte_mask(uint bits)
{
  /* Get the number of used bits-1 (0..7) in the last byte */
  unsigned int const used = (bits - 1U) & 7U;
  /* Return bitmask for the significant bits */
  return (uchar) ((2U << used) - 1);
}

#ifdef _MSC_VER
#include <intrin.h>
#endif

/*
  Find the position of the first(least significant) bit set in
  the argument. Returns 64 if the argument was 0.
*/
static inline uint my_find_first_bit(ulonglong n)
{
  if(!n)
    return 64;
#if defined(__GNUC__)
  return __builtin_ctzll(n);
#elif defined(_MSC_VER)
#if defined(_M_IX86)
  unsigned long bit;
  if( _BitScanForward(&bit, (uint)n))
    return bit;
  _BitScanForward(&bit, (uint)(n>>32));
  return bit + 32;
#else
  unsigned long bit;
  _BitScanForward64(&bit, n);
  return bit;
#endif
#else
  /* Generic case */
  uint  shift= 0;
  static const uchar last_bit[16] = { 32, 0, 1, 0,
                                      2, 0, 1, 0,
                                      3, 0, 1, 0,
                                      2, 0, 1, 0};
  uint bit;
  while ((bit = last_bit[(n >> shift) & 0xF]) == 32)
    shift+= 4;
  return shift+bit;
#endif
}
C_MODE_END

#endif /* MY_BIT_INCLUDED */

Coverage Report

Created: 2024-06-18 07:03

Line	Count	Source (jump to first uncovered line)
1		/* Copyright (c) 2007, 2011, Oracle and/or its affiliates.
2		Copyright (c) 2009, 2020, MariaDB Corporation.
3
4		This program is free software; you can redistribute it and/or modify
5		it under the terms of the GNU General Public License as published by
6		the Free Software Foundation; version 2 of the License.
7
8		This program is distributed in the hope that it will be useful,
9		but WITHOUT ANY WARRANTY; without even the implied warranty of
10		MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11		GNU General Public License for more details.
12
13		You should have received a copy of the GNU General Public License
14		along with this program; if not, write to the Free Software
15		Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335 USA */
16
17		#ifndef MY_BIT_INCLUDED
18		#define MY_BIT_INCLUDED
19
20		/*
21		Some useful bit functions
22		*/
23
24		C_MODE_START
25
26		extern const uchar _my_bits_reverse_table[256];
27
28
29		/*
30		my_bit_log2_xxx()
31
32		In the given value, find the highest bit set,
33		which is the smallest X that satisfies the condition: (2^X >= value).
34		Can be used as a reverse operation for (1<<X), to find X.
35
36		Examples:
37		- returns 0 for (1<<0)
38		- returns 1 for (1<<1)
39		- returns 2 for (1<<2)
40		- returns 2 for 3, which has (1<<2) as the highest bit set.
41
42		Note, the behaviour of log2(0) is not defined.
43		Let's return 0 for the input 0, for the code simplicity.
44		See the 000x branch. It covers both (1<<0) and 0.
45		*/
46		static inline CONSTEXPR uint my_bit_log2_hex_digit(uint8 value)
47	0	{
48	0	return value & 0x0C ? /1100/ (value & 0x08 ? /1000/ 3 : /0100/ 2) :
49	0	/0010/ (value & 0x02 ? /0010/ 1 : /000x/ 0);
50	0	} Unexecuted instantiation: ctype-simple.c:my_bit_log2_hex_digit Unexecuted instantiation: ctype-uca.c:my_bit_log2_hex_digit Unexecuted instantiation: my_alloc.c:my_bit_log2_hex_digit
51		static inline CONSTEXPR uint my_bit_log2_uint8(uint8 value)
52	0	{
53	0	return value & 0xF0 ? my_bit_log2_hex_digit((uint8) (value >> 4)) + 4:
54	0	my_bit_log2_hex_digit(value);
55	0	} Unexecuted instantiation: ctype-simple.c:my_bit_log2_uint8 Unexecuted instantiation: ctype-uca.c:my_bit_log2_uint8 Unexecuted instantiation: my_alloc.c:my_bit_log2_uint8
56		static inline CONSTEXPR uint my_bit_log2_uint16(uint16 value)
57	0	{
58	0	return value & 0xFF00 ? my_bit_log2_uint8((uint8) (value >> 8)) + 8 :
59	0	my_bit_log2_uint8((uint8) value);
60	0	} Unexecuted instantiation: ctype-simple.c:my_bit_log2_uint16 Unexecuted instantiation: ctype-uca.c:my_bit_log2_uint16 Unexecuted instantiation: my_alloc.c:my_bit_log2_uint16
61		static inline CONSTEXPR uint my_bit_log2_uint32(uint32 value)
62	0	{
63	0	return value & 0xFFFF0000UL ?
64	0	my_bit_log2_uint16((uint16) (value >> 16)) + 16 :
65	0	my_bit_log2_uint16((uint16) value);
66	0	} Unexecuted instantiation: ctype-simple.c:my_bit_log2_uint32 Unexecuted instantiation: ctype-uca.c:my_bit_log2_uint32 Unexecuted instantiation: my_alloc.c:my_bit_log2_uint32
67		static inline CONSTEXPR uint my_bit_log2_uint64(ulonglong value)
68	0	{
69	0	return value & 0xFFFFFFFF00000000ULL ?
70	0	my_bit_log2_uint32((uint32) (value >> 32)) + 32 :
71	0	my_bit_log2_uint32((uint32) value);
72	0	} Unexecuted instantiation: ctype-simple.c:my_bit_log2_uint64 Unexecuted instantiation: ctype-uca.c:my_bit_log2_uint64 Unexecuted instantiation: my_alloc.c:my_bit_log2_uint64
73		static inline CONSTEXPR uint my_bit_log2_size_t(size_t value)
74	0	{
75	0	#ifdef __cplusplus
76	0	static_assert(sizeof(size_t) <= sizeof(ulonglong),
77	0	"size_t <= ulonglong is an assumption that needs to be fixed "
78	0	"for this architecture. Please create an issue on "
79	0	"https://jira.mariadb.org");
80	0	#endif
81	0	return my_bit_log2_uint64((ulonglong) value);
82	0	} Unexecuted instantiation: ctype-simple.c:my_bit_log2_size_t Unexecuted instantiation: ctype-uca.c:my_bit_log2_size_t Unexecuted instantiation: my_alloc.c:my_bit_log2_size_t
83
84
85		/*
86		Count bits in 32bit integer
87
88		Algorithm by Sean Anderson, according to:
89		http://graphics.stanford.edu/~seander/bithacks.html
90		under "Counting bits set, in parallel"
91
92		(Original code public domain).
93		*/
94		static inline uint my_count_bits_uint32(uint32 v)
95	0	{
96	0	v = v - ((v >> 1) & 0x55555555);
97	0	v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
98	0	return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
99	0	} Unexecuted instantiation: ctype-simple.c:my_count_bits_uint32 Unexecuted instantiation: ctype-uca.c:my_count_bits_uint32 Unexecuted instantiation: my_alloc.c:my_count_bits_uint32
100
101
102		static inline uint my_count_bits(ulonglong x)
103	0	{
104	0	return my_count_bits_uint32((uint32)x) + my_count_bits_uint32((uint32)(x >> 32));
105	0	} Unexecuted instantiation: ctype-simple.c:my_count_bits Unexecuted instantiation: ctype-uca.c:my_count_bits Unexecuted instantiation: my_alloc.c:my_count_bits
106
107
108
109
110		/*
111		Next highest power of two
112
113		SYNOPSIS
114		my_round_up_to_next_power()
115		v Value to check
116
117		RETURN
118		Next or equal power of 2
119		Note: 0 will return 0
120
121		NOTES
122		Algorithm by Sean Anderson, according to:
123		http://graphics.stanford.edu/~seander/bithacks.html
124		(Original code public domain)
125
126		Comments shows how this works with 01100000000000000000000000001011
127		*/
128
129		static inline uint32 my_round_up_to_next_power(uint32 v)
130	0	{
131	0	v--; /* 01100000000000000000000000001010 */
132	0	v\|= v >> 1; /* 01110000000000000000000000001111 */
133	0	v\|= v >> 2; /* 01111100000000000000000000001111 */
134	0	v\|= v >> 4; /* 01111111110000000000000000001111 */
135	0	v\|= v >> 8; /* 01111111111111111100000000001111 */
136	0	v\|= v >> 16; /* 01111111111111111111111111111111 */
137	0	return v+1; /* 10000000000000000000000000000000 */
138	0	} Unexecuted instantiation: ctype-simple.c:my_round_up_to_next_power Unexecuted instantiation: ctype-uca.c:my_round_up_to_next_power Unexecuted instantiation: my_alloc.c:my_round_up_to_next_power
139
140		static inline uint32 my_clear_highest_bit(uint32 v)
141	0	{
142	0	uint32 w=v >> 1;
143	0	w\|= w >> 1;
144	0	w\|= w >> 2;
145	0	w\|= w >> 4;
146	0	w\|= w >> 8;
147	0	w\|= w >> 16;
148	0	return v & w;
149	0	} Unexecuted instantiation: ctype-simple.c:my_clear_highest_bit Unexecuted instantiation: ctype-uca.c:my_clear_highest_bit Unexecuted instantiation: my_alloc.c:my_clear_highest_bit
150
151		static inline uint32 my_reverse_bits(uint32 key)
152	0	{
153	0	return
154	0	((uint32)_my_bits_reverse_table[ key & 255] << 24) \|
155	0	((uint32)_my_bits_reverse_table[(key>> 8) & 255] << 16) \|
156	0	((uint32)_my_bits_reverse_table[(key>>16) & 255] << 8) \|
157	0	(uint32)_my_bits_reverse_table[(key>>24) ];
158	0	} Unexecuted instantiation: ctype-simple.c:my_reverse_bits Unexecuted instantiation: ctype-uca.c:my_reverse_bits Unexecuted instantiation: my_alloc.c:my_reverse_bits
159
160		/*
161		a number with the n lowest bits set
162		an overflow-safe version of (1 << n) - 1
163		*/
164		static inline uint64 my_set_bits(int n)
165	0	{
166	0	return (((1ULL << (n - 1)) - 1) << 1) \| 1;
167	0	} Unexecuted instantiation: ctype-simple.c:my_set_bits Unexecuted instantiation: ctype-uca.c:my_set_bits Unexecuted instantiation: my_alloc.c:my_set_bits
168
169		/* Create a mask of the significant bits for the last byte (1,3,7,..255) */
170		static inline uchar last_byte_mask(uint bits)
171	0	{
172	0	/* Get the number of used bits-1 (0..7) in the last byte */
173	0	unsigned int const used = (bits - 1U) & 7U;
174	0	/* Return bitmask for the significant bits */
175	0	return (uchar) ((2U << used) - 1);
176	0	} Unexecuted instantiation: ctype-simple.c:last_byte_mask Unexecuted instantiation: ctype-uca.c:last_byte_mask Unexecuted instantiation: my_alloc.c:last_byte_mask
177
178		#ifdef _MSC_VER
179		#include <intrin.h>
180		#endif
181
182		/*
183		Find the position of the first(least significant) bit set in
184		the argument. Returns 64 if the argument was 0.
185		*/
186		static inline uint my_find_first_bit(ulonglong n)
187	0	{
188	0	if(!n)
189	0	return 64;
190	0	#if defined(__GNUC__)
191	0	return __builtin_ctzll(n);
192	0	#elif defined(_MSC_VER)
193	0	#if defined(_M_IX86)
194	0	unsigned long bit;
195	0	if( _BitScanForward(&bit, (uint)n))
196	0	return bit;
197	0	_BitScanForward(&bit, (uint)(n>>32));
198	0	return bit + 32;
199	0	#else
200	0	unsigned long bit;
201	0	_BitScanForward64(&bit, n);
202	0	return bit;
203	0	#endif
204	0	#else
205	0	/* Generic case */
206	0	uint shift= 0;
207	0	static const uchar last_bit[16] = { 32, 0, 1, 0,
208	0	2, 0, 1, 0,
209	0	3, 0, 1, 0,
210	0	2, 0, 1, 0};
211	0	uint bit;
212	0	while ((bit = last_bit[(n >> shift) & 0xF]) == 32)
213	0	shift+= 4;
214	0	return shift+bit;
215	0	#endif
216	0	} Unexecuted instantiation: ctype-simple.c:my_find_first_bit Unexecuted instantiation: ctype-uca.c:my_find_first_bit Unexecuted instantiation: my_alloc.c:my_find_first_bit
217		C_MODE_END
218
219		#endif /* MY_BIT_INCLUDED */