IgrOS-Kernel 0.1.34.545
Simple C++20 Kernel for i386/x86_64
Loading...
Searching...
No Matches
kMath.hpp
Go to the documentation of this file.
1
11
12
13#pragma once
14
15
16// C++
17#include <bit>
18#include <concepts>
19#include <type_traits>
20// IgrOS-Kernel arch
21#include <arch/types.hpp>
22
23
24// Kernel library code zone
25namespace igros::klib {
26
27
30 template<std::integral T>
31 struct divmod_t final {
34
38 constexpr auto operator==(const divmod_t &other) const noexcept -> bool = default;
39 };
40
41
45 template<class T, class D>
46 concept kdivisible = std::integral<T> && std::integral<D> && (std::is_signed_v<T> == std::is_signed_v<D>);
47
48
55 [[nodiscard]]
56 constexpr auto kudivmod64(const igros_quad_t dividend, const igros_quad_t divisor) noexcept -> divmod_t<igros_quad_t> {
57
58#if defined(IGROS_ARCH_i386)
59 // Divisor fits 32 bits: two hardware divisions (high part, then remainder:low part)
60 if (!std::is_constant_evaluated() && (0_u64 != divisor) && (0_u64 == (divisor >> 32))) {
61 const auto divisor32 {static_cast<igros_dword_t>(divisor)};
62 const auto high {static_cast<igros_dword_t>(dividend >> 32)};
63 const auto low {static_cast<igros_dword_t>(dividend)};
64 const auto quotientHigh {high / divisor32};
65 auto remainder {high % divisor32}; // NOLINT(misc-const-correctness): written by DIV
66 auto quotientLow {igros_dword_t {}}; // NOLINT(misc-const-correctness): written by DIV
67 // EDX:EAX / divisor (EDX < divisor, so quotient fits EAX)
68 asm(
69 "divl %[divisor]"
70 : "=a"(quotientLow), "+d"(remainder)
71 : "a"(low), [divisor] "rm"(divisor32)
72 : "cc"
73 );
75 .quotient = (static_cast<igros_quad_t>(quotientHigh) << 32) | quotientLow,
76 .remainder = remainder,
77 };
78 }
79#endif
80
81 // Divisor greater than dividend (or zero)
82 if ((0_u64 == divisor) || (divisor > dividend)) {
83 return divmod_t<igros_quad_t> {.quotient = 0_u64, .remainder = dividend};
84 }
85
86 // Shift-subtract long division: align divisor highest bit with dividend highest bit
87 const auto shift {static_cast<igros_dword_t>(std::countl_zero(divisor) - std::countl_zero(dividend))};
88 auto aligned {divisor << shift};
89 auto res {divmod_t<igros_quad_t> {.quotient = 0_u64, .remainder = dividend}};
90 // One quotient bit per shift
91 for (auto bit {0_u32}; bit <= shift; ++bit) {
92 res.quotient <<= 1;
93 if (res.remainder >= aligned) {
94 res.remainder -= aligned;
95 res.quotient |= 1_u64;
96 }
97 aligned >>= 1;
98 }
99 return res;
100 }
101
102
112 template<std::integral T, std::integral D>
113 requires kdivisible<T, D>
114 [[nodiscard]]
115 constexpr auto kdivmod(const T dividend, const D divisor) noexcept -> divmod_t<T> {
116
117 // Native division for CPU word sized values
118 if constexpr ((sizeof(T) <= sizeof(igros_usize_t)) && (sizeof(D) <= sizeof(igros_usize_t))) {
119 return divmod_t<T> {
120 static_cast<T>(dividend / divisor),
121 static_cast<T>(dividend % divisor),
122 };
123
124 // Unsigned values wider than CPU word
125 } else if constexpr (std::is_unsigned_v<T>) {
126 const auto res {kudivmod64(dividend, divisor)};
127 return divmod_t<T> {
128 static_cast<T>(res.quotient),
129 static_cast<T>(res.remainder),
130 };
131
132 // Signed values wider than CPU word: divide magnitudes
133 } else {
134 const auto absDividend {(dividend < 0) ? (0_u64 - static_cast<igros_quad_t>(dividend)) : static_cast<igros_quad_t>(dividend)};
135 const auto absDivisor {(divisor < 0) ? (0_u64 - static_cast<igros_quad_t>(divisor)) : static_cast<igros_quad_t>(divisor)};
136 const auto res {kudivmod64(absDividend, absDivisor)};
137 // Quotient is negative when signs differ, remainder takes dividend sign
138 const auto quotient {((dividend < 0) != (divisor < 0)) ? (0_u64 - res.quotient) : res.quotient};
139 const auto remainder {(dividend < 0) ? (0_u64 - res.remainder) : res.remainder};
140 return divmod_t<T> {
141 static_cast<T>(quotient),
142 static_cast<T>(remainder),
143 };
144 }
145 }
146
147
148} // namespace igros::klib
149
Integers of the same signedness (mixed ones convert signed to unsigned silently).
Definition kMath.hpp:46
std::size_t igros_usize_t
Unsigned size.
Definition types.hpp:51
std::uint32_t igros_dword_t
32-bit unsigned integer
Definition types.hpp:43
std::uint64_t igros_quad_t
64-bit unsigned integer
Definition types.hpp:44
Freestanding kernel library: printing, math, alignment, flags, strings.
constexpr auto kdivmod(const T dividend, const D divisor) noexcept -> divmod_t< T >
Divide integer by integer of the same signedness.
Definition kMath.hpp:115
constexpr auto kudivmod64(const igros_quad_t dividend, const igros_quad_t divisor) noexcept -> divmod_t< igros_quad_t >
64-bit unsigned division for 32-bit CPU (no 64-bit "/" and "%" without libgcc __udivdi3/__umoddi3)
Definition kMath.hpp:56
Combined division & modulo result.
Definition kMath.hpp:31
T remainder
Remainder (sign of dividend).
Definition kMath.hpp:33
constexpr auto operator==(const divmod_t &other) const noexcept -> bool=default
Comparison.
T quotient
Quotient (truncated towards zero).
Definition kMath.hpp:32
Common C++ types redefinition.