#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;
|
}
|
}
|
}
|
}
|
