1 //===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===//
8 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
15 /* By Nguyen Anh Quynh <aquynh@gmail.com>, 2013-2015 */
36 /// Hi_32 - This function returns the high 32 bits of a 64 bit value.
41 /// Lo_32 - This function returns the low 32 bits of a 64 bit value.
46 /// isUIntN - Checks if an unsigned integer fits into the given (dynamic)
47 /// bit width.
49 	return x == (x & (~0ULL >> (64 - N)));  in isUIntN()
52 /// isIntN - Checks if an signed integer fits into the given (dynamic)
53 /// bit width.
55 //  return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1)));
58 /// isMask_32 - This function returns true if the argument is a sequence of ones
59 /// starting at the least significant bit with the remainder zero (32 bit
65 /// isMask_64 - This function returns true if the argument is a sequence of ones
66 /// starting at the least significant bit with the remainder zero (64 bit
72 /// isShiftedMask_32 - This function returns true if the argument contains a
73 /// sequence of ones with the remainder zero (32 bit version.)
76 	return isMask_32((Value - 1) | Value);  in isShiftedMask_32()
79 /// isShiftedMask_64 - This function returns true if the argument contains a
80 /// sequence of ones with the remainder zero (64 bit version.)
82 	return isMask_64((Value - 1) | Value);  in isShiftedMask_64()
85 /// isPowerOf2_32 - This function returns true if the argument is a power of
86 /// two > 0. Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
88 	return Value && !(Value & (Value - 1));  in isPowerOf2_32()
91 /// CountLeadingZeros_32 - this function performs the platform optimal form of
92 /// counting the number of zeros from the most significant bit to the first one
93 /// bit.  Ex. CountLeadingZeros_32(0x00F000FF) == 8.
120 /// CountLeadingOnes_32 - this function performs the operation of
121 /// counting the number of ones from the most significant bit to the first zero
122 /// bit.  Ex. CountLeadingOnes_32(0xFF0FFF00) == 8.
128 /// CountLeadingZeros_64 - This function performs the platform optimal form
129 /// of counting the number of zeros from the most significant bit to the first
130 /// one bit (64 bit edition.)
131 /// Returns 64 if the word is zero.
137 	if (!Value) return 64;  in CountLeadingZeros_64()
145 		if (!Value) return 64;  in CountLeadingZeros_64()
148 		for (Shift = 64 >> 1; Shift; Shift >>= 1) {  in CountLeadingZeros_64()
170 			// same as 32 bit value  in CountLeadingZeros_64()
178 /// CountLeadingOnes_64 - This function performs the operation
179 /// of counting the number of ones from the most significant bit to the first
180 /// zero bit (64 bit edition.)
181 /// Returns 64 if the word is all ones.
186 /// CountTrailingZeros_32 - this function performs the platform optimal form of
187 /// counting the number of zeros from the least significant bit to the first one
188 /// bit.  Ex. CountTrailingZeros_32(0xFF00FF00) == 8.
199 	// Replace "-Value" by "1+~Value" in the following commented code to avoid   in CountTrailingZeros_32()
201 	//    return Mod37BitPosition[(-Value & Value) % 37];  in CountTrailingZeros_32()
206 /// CountTrailingOnes_32 - this function performs the operation of
207 /// counting the number of ones from the least significant bit to the first zero
208 /// bit.  Ex. CountTrailingOnes_32(0x00FF00FF) == 8.
214 /// CountTrailingZeros_64 - This function performs the platform optimal form
215 /// of counting the number of zeros from the least significant bit to the first
216 /// one bit (64 bit edition.)
217 /// Returns 64 if the word is zero.
220 	return Value ? __builtin_ctzll(Value) : 64;  in CountTrailingZeros_64()
223 		64, 0, 1, 39, 2, 15, 40, 23, 3, 12, 16, 59, 41, 19, 24, 54,  in CountTrailingZeros_64()
224 		4, 64, 13, 10, 17, 62, 60, 28, 42, 30, 20, 51, 25, 44, 55,  in CountTrailingZeros_64()
229 	// Replace "-Value" by "1+~Value" in the following commented code to avoid   in CountTrailingZeros_64()
231 	//    return Mod67Position[(-Value & Value) % 67];  in CountTrailingZeros_64()
236 /// CountTrailingOnes_64 - This function performs the operation
237 /// of counting the number of ones from the least significant bit to the first
238 /// zero bit (64 bit edition.)
239 /// Returns 64 if the word is all ones.
244 /// CountPopulation_32 - this function counts the number of set bits in a value.
251 	uint32_t v = Value - ((Value >> 1) & 0x55555555);  in CountPopulation_32()
257 /// CountPopulation_64 - this function counts the number of set bits in a value,
258 /// (64 bit edition.)
263 	uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL);  in CountPopulation_64()
270 /// Log2_32 - This function returns the floor log base 2 of the specified value,
271 /// -1 if the value is zero. (32 bit edition.)
272 /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
274 	return 31 - CountLeadingZeros_32(Value);  in Log2_32()
277 /// Log2_64 - This function returns the floor log base 2 of the specified value,
278 /// -1 if the value is zero. (64 bit edition.)
280 	return 63 - CountLeadingZeros_64(Value);  in Log2_64()
283 /// Log2_32_Ceil - This function returns the ceil log base 2 of the specified
284 /// value, 32 if the value is zero. (32 bit edition).
287 	return 32-CountLeadingZeros_32(Value-1);  in Log2_32_Ceil()
290 /// Log2_64_Ceil - This function returns the ceil log base 2 of the specified
291 /// value, 64 if the value is zero. (64 bit edition.)
293 	return 64-CountLeadingZeros_64(Value-1);  in Log2_64_Ceil()
296 /// GreatestCommonDivisor64 - Return the greatest common divisor of the two
307 /// BitsToDouble - This function takes a 64-bit integer and returns the bit
318 /// BitsToFloat - This function takes a 32-bit integer and returns the bit
329 /// DoubleToBits - This function takes a double and returns the bit
330 /// equivalent 64-bit integer.  Note that copying doubles around
342 /// FloatToBits - This function takes a float and returns the bit
343 /// equivalent 32-bit integer.  Note that copying floats around
355 /// MinAlign - A and B are either alignments or offsets.  Return the minimum
360 	// Replace "-Value" by "1+~Value" in the following commented code to avoid   in MinAlign()
362 	//    return (A | B) & -(A | B);  in MinAlign()
366 /// NextPowerOf2 - Returns the next power of two (in 64-bits)
378 /// Returns the next integer (mod 2**64) that is greater than or equal to
379 /// \p Value and is a multiple of \p Align. \p Align must be non-zero.
388 	return ((Value + Align - 1) / Align) * Align;  in RoundUpToAlignment()
391 /// Returns the offset to the next integer (mod 2**64) that is greater than
393 /// non-zero.
395 	return RoundUpToAlignment(Value, Align) - Value;  in OffsetToAlignment()
398 /// abs64 - absolute value of a 64-bit int.  Not all environments support
399 /// "abs" on whatever their name for the 64-bit int type is.  The absolute
402 	return (x < 0) ? -x : x;  in abs64()
405 /// \brief Sign extend number in the bottom B bits of X to a 32-bit int.
408 	return (int32_t)(X << (32 - B)) >> (32 - B);  in SignExtend32()
411 /// \brief Sign extend number in the bottom B bits of X to a 64-bit int.
412 /// Requires 0 < B <= 64.
414 	return (int64_t)(X << (64 - B)) >> (64 - B);  in SignExtend64()
417 /// \brief Count number of 0's from the most significant bit to the least
433 	for (i = bits; --i; ) {  in countLeadingZeros()
435 		count--;  in countLeadingZeros()