/**************************************************************************/
/* math_funcs_binary.h */
/**************************************************************************/
/* This file is part of: */
/* GODOT ENGINE */
/* https://godotengine.org */
/**************************************************************************/
/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
/* */
/* Permission is hereby granted, free of charge, to any person obtaining */
/* a copy of this software and associated documentation files (the */
/* "Software"), to deal in the Software without restriction, including */
/* without limitation the rights to use, copy, modify, merge, publish, */
/* distribute, sublicense, and/or sell copies of the Software, and to */
/* permit persons to whom the Software is furnished to do so, subject to */
/* the following conditions: */
/* */
/* The above copyright notice and this permission notice shall be */
/* included in all copies or substantial portions of the Software. */
/* */
/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
/**************************************************************************/
#pragma once
#include "core/typedefs.h"
namespace Math {
/* Functions to handle powers of 2 and shifting. */
// Returns `true` if a positive integer is a power of 2, `false` otherwise.
template <typename T>
constexpr bool is_power_of_2(const T x) {
return x && ((x & (x - 1)) == 0);
}
// Function to find the next power of 2 to an integer.
constexpr uint64_t next_power_of_2(uint64_t p_number) {
if (p_number == 0) {
return 0;
}
--p_number;
p_number |= p_number >> 1;
p_number |= p_number >> 2;
p_number |= p_number >> 4;
p_number |= p_number >> 8;
p_number |= p_number >> 16;
p_number |= p_number >> 32;
return ++p_number;
}
constexpr uint32_t next_power_of_2(uint32_t p_number) {
if (p_number == 0) {
return 0;
}
--p_number;
p_number |= p_number >> 1;
p_number |= p_number >> 2;
p_number |= p_number >> 4;
p_number |= p_number >> 8;
p_number |= p_number >> 16;
return ++p_number;
}
// Function to find the previous power of 2 to an integer.
constexpr uint64_t previous_power_of_2(uint64_t p_number) {
p_number |= p_number >> 1;
p_number |= p_number >> 2;
p_number |= p_number >> 4;
p_number |= p_number >> 8;
p_number |= p_number >> 16;
p_number |= p_number >> 32;
return p_number - (p_number >> 1);
}
constexpr uint32_t previous_power_of_2(uint32_t p_number) {
p_number |= p_number >> 1;
p_number |= p_number >> 2;
p_number |= p_number >> 4;
p_number |= p_number >> 8;
p_number |= p_number >> 16;
return p_number - (p_number >> 1);
}
// Function to find the closest power of 2 to an integer.
constexpr uint64_t closest_power_of_2(uint64_t p_number) {
uint64_t nx = next_power_of_2(p_number);
uint64_t px = previous_power_of_2(p_number);
return (nx - p_number) > (p_number - px) ? px : nx;
}
constexpr uint32_t closest_power_of_2(uint32_t p_number) {
uint32_t nx = next_power_of_2(p_number);
uint32_t px = previous_power_of_2(p_number);
return (nx - p_number) > (p_number - px) ? px : nx;
}
// Get a shift value from a power of 2.
constexpr int32_t get_shift_from_power_of_2(uint64_t p_bits) {
for (uint64_t i = 0; i < (uint64_t)64; i++) {
if (p_bits == (uint64_t)((uint64_t)1 << i)) {
return i;
}
}
return -1;
}
constexpr int32_t get_shift_from_power_of_2(uint32_t p_bits) {
for (uint32_t i = 0; i < (uint32_t)32; i++) {
if (p_bits == (uint32_t)((uint32_t)1 << i)) {
return i;
}
}
return -1;
}
template <typename T>
constexpr T nearest_power_of_2_templated(T p_number) {
--p_number;
// The number of operations on x is the base two logarithm
// of the number of bits in the type. Add three to account
// for sizeof(T) being in bytes.
constexpr size_t shift_steps = get_shift_from_power_of_2((uint64_t)sizeof(T)) + 3;
// If the compiler is smart, it unrolls this loop.
// If it's dumb, this is a bit slow.
for (size_t i = 0; i < shift_steps; i++) {
p_number |= p_number >> (1 << i);
}
return ++p_number;
}
// Function to find the nearest (bigger) power of 2 to an integer.
constexpr uint64_t nearest_shift(uint64_t p_number) {
uint64_t i = 63;
do {
i--;
if (p_number & ((uint64_t)1 << i)) {
return i + (uint64_t)1;
}
} while (i != 0);
return 0;
}
constexpr uint32_t nearest_shift(uint32_t p_number) {
uint32_t i = 31;
do {
i--;
if (p_number & ((uint32_t)1 << i)) {
return i + (uint32_t)1;
}
} while (i != 0);
return 0;
}
// constexpr function to find the floored log2 of a number
template <typename T>
constexpr T floor_log2(T x) {
return x < 2 ? x : 1 + floor_log2(x >> 1);
}
// Get the number of bits needed to represent the number.
// IE, if you pass in 8, you will get 4.
// If you want to know how many bits are needed to store 8 values however, pass in (8 - 1).
template <typename T>
constexpr T get_num_bits(T x) {
return floor_log2(x);
}
} //namespace Math