blob: 897a4b9cd39e3cfa5de503d77c87e1a5be879b09 [file] [log] [blame]
#include <stdint.h>
extern uint64_t __udivmoddi4(uint64_t num, uint64_t den, uint64_t *p_rem);
extern int64_t __divmoddi4(int64_t num, int64_t den, int64_t *p_rem);
extern int64_t __moddi3(int64_t num, int64_t den);
extern int64_t __divdi3(int64_t num, int64_t den);
extern uint64_t __udivdi3(uint64_t num, uint64_t den);
extern uint64_t __umoddi3(uint64_t num, uint64_t den);
uint64_t __udivmoddi4(uint64_t num, uint64_t den, uint64_t *p_rem)
{
uint64_t quot = 0;
/* Trigger a division by zero at run time (trick taken from iPXE). */
if (den == 0) {
if (p_rem)
*p_rem = 0;
return 1/((unsigned)den);
}
if (num >= den) {
/* Align den to num to avoid wasting time on leftmost zero bits. */
int n = __builtin_clzll(den) - __builtin_clzll(num);
den <<= n;
do {
quot <<= 1;
if (num >= den) {
num -= den;
quot |= 1;
}
den >>= 1;
} while (n--);
}
if (p_rem)
*p_rem = num;
return quot;
}
int64_t __divmoddi4(int64_t num, int64_t den, int64_t *p_rem)
{
int32_t nmask = num < 0 ? -1 : 0;
int32_t qmask = (num ^ den) < 0 ? -1 : 0;
uint64_t quot;
/* Compute absolute values and do an unsigned division. */
num = (num + nmask) ^ nmask;
if (den < 0)
den = -den;
/* Copy sign of num^den into quotient, sign of num into remainder. */
quot = (__udivmoddi4(num, den, (uint64_t *)p_rem) + qmask) ^ qmask;
if (p_rem)
*p_rem = (*p_rem + nmask) ^ nmask;
return quot;
}
int64_t __moddi3(int64_t num, int64_t den)
{
int64_t rem;
__divmoddi4(num, den, &rem);
return rem;
}
int64_t __divdi3(int64_t num, int64_t den)
{
int64_t rem;
return __divmoddi4(num, den, &rem);
}
uint64_t __udivdi3(uint64_t num, uint64_t den)
{
uint64_t rem;
return __udivmoddi4(num, den, &rem);
}
uint64_t __umoddi3(uint64_t num, uint64_t den)
{
uint64_t rem;
__udivmoddi4(num, den, &rem);
return rem;
}
#ifdef TEST
#include <assert.h>
#define UTEST(a, b, q, r) assert(__udivdi3(a, b) == q && __umoddi3(a, b) == r)
#define STEST(a, b, q, r) assert(__divdi3(a, b) == q && __moddi3(a, b) == r)
int main()
{
UTEST(1, 1, 1, 0);
UTEST(2, 2, 1, 0);
UTEST(5, 3, 1, 2);
UTEST(10, 3, 3, 1);
UTEST(120, 3, 40, 0);
UTEST(120, 1, 120, 0);
UTEST(0x7FFFFFFFFFFFFFFFULL, 17, 0x787878787878787, 8);
UTEST(0x7FFFFFFFFFFFFFFFULL, 0x787878787878787, 17, 8);
UTEST(0x8000000000000001ULL, 17, 0x787878787878787, 10);
UTEST(0x8000000000000001ULL, 0x787878787878787, 17, 10);
UTEST(0, 5, 0, 0);
STEST(0x7FFFFFFFFFFFFFFFULL, 17, 0x787878787878787, 8);
STEST(0x7FFFFFFFFFFFFFFFULL, -17, -0x787878787878787, 8);
STEST(-0x7FFFFFFFFFFFFFFFULL, 17, -0x787878787878787, -8);
STEST(-0x7FFFFFFFFFFFFFFFULL, -17, 0x787878787878787, -8);
STEST(33, 5, 6, 3);
STEST(33, -5, -6, 3);
STEST(-33, 5, -6, -3);
STEST(-33, -5, 6, -3);
}
#endif