MathUtils.h
4.28 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#pragma once
#include "il2cpp-config.h"
#include <assert.h>
#include <cmath>
#include <limits>
#include <stdint.h>
namespace il2cpp
{
namespace utils
{
namespace MathUtils
{
// Do math on low/high part separately as 64-bit integers because otherwise
// we might easily overflow during initial multiplication
inline int64_t A_Times_B_DividedBy_C(int64_t multiplicand, int64_t multiplier, int64_t divisor)
{
IL2CPP_ASSERT((llabs(divisor) & (1LL << 62)) == 0 && "Can't divide by numbers with absolute value larger than 2^62 - 1.");
bool resultIsNegative = static_cast<uint64_t>(multiplicand ^ multiplier ^ divisor) >> 63; // Result is negative if odd number of operands are negative
multiplicand = llabs(multiplicand);
IL2CPP_ASSERT(multiplicand > 0 && "Can't multiply by -2^63.");
multiplier = llabs(multiplier);
IL2CPP_ASSERT(multiplier > 0 && "Can't multiply by -2^63.");
divisor = llabs(divisor); // We already asserted on divisor size
uint64_t multiplicand_low = multiplicand & 0xFFFFFFFF;
uint64_t multiplicand_high = multiplicand >> 32;
uint64_t multiplier_low = multiplier & 0xFFFFFFFF;
uint64_t multiplier_high = multiplier >> 32;
// We're gonna assume our multiplicated value is 128-bit integer
// so we're gonna compose it of two uint64_t's
// a * b =
// (a_high * 2^32 + a_low) * (b_high * 2^32 + b_low) =
// a_high * b_high * 2^64 + (a_high * b_low + a_low * b_high) * 2^32 + a_low * b_low
uint64_t dividends[2] =
{
multiplicand_low * multiplier_low, // low part, bits [0, 63]
multiplicand_high * multiplier_high // high part, bits [64, 127]
};
uint64_t resultMid1 = multiplicand_high * multiplier_low + multiplicand_low * multiplier_high; // mid part, bits [32, 95]
dividends[1] += resultMid1 >> 32; // add the higher bits of mid part ([64, 95]) to high part
resultMid1 = (resultMid1 & 0xFFFFFFFF) << 32; // Now this contains the lower bits of mid part ([32, 63])
// Check for lower part overflow below adding the lower bits of mid part to it
// Add carry to high part if overflow occurs
if (dividends[0] > std::numeric_limits<uint64_t>::max() - resultMid1)
dividends[1]++;
dividends[0] += resultMid1; // add the lower bits of mid part to low part
// At this point, we got our whole divident 128-bit value inside 'dividends'
uint64_t workValue = 0; // Value that we're gonna be dividing
uint64_t result = 0; // The final result
const uint64_t kOne = 1;
int bitIndex = 127; // Current bit that we're gonna be add to the workValue
// Let's find the starting point for our division
// We'll keep adding bits from our divident to the workValue until it's higher than the divisor
// We did divisor = llabs(divisor) earlier, so cast to unsigned is safe
while (workValue < static_cast<uint64_t>(divisor))
{
workValue <<= 1;
if (bitIndex > -1)
{
workValue |= (dividends[bitIndex / 64] & (kOne << (bitIndex % 64))) != 0;
}
else
{
return 0;
}
bitIndex--;
}
// Main division loop
for (; bitIndex > -2 || workValue >= static_cast<uint64_t>(divisor); bitIndex--)
{
result <<= 1; // Shift result left
// Since it's binary, the division result can be only 0 and 1
// It's 1 if workValue is higher or equal to divisor
if (workValue >= static_cast<uint64_t>(divisor))
{
workValue -= static_cast<uint64_t>(divisor);
result++;
}
// Shift work value to the left and append the next bit of our dividend
IL2CPP_ASSERT((workValue & (1LL << 63)) == 0 && "overflow!");
if (bitIndex > -1)
{
workValue <<= 1;
workValue |= (dividends[bitIndex / 64] & (kOne << (bitIndex % 64))) != 0;
}
}
// Negate result if it's supposed to be negative
if (resultIsNegative)
return -static_cast<int64_t>(result);
return result;
}
}
}
}