Как вычислить магические константы для деления на умножение для операции постоянного деления по модулю ⇐ C++

[Anonymous]

Я пытаюсь повторить оптимизацию «деление на умножение», выполненную в clang (и, возможно, в других компиляторах) при выполнении следующей операции (для использования в моем собственном компиляторе):

Код: Выделить всё

bool modulo(uint64_t value)
{
constexpr auto CONSTANT = 5;
return value % CONSTANT == 0;
}

Для моей цели «CONSTANT» можно считать простым числом (то есть нечетным числом) среди первых 2048 простых чисел.

Это приведет к следующей сборке для всех констант (изменение только магических чисел):

Код: Выделить всё

modulo(unsigned long): // example here for "CONSTANT==5"
movabs rax, -3689348814741910323
imul rax, rdi
movabs rcx, 3689348814741910324
cmp rax, rcx
setb al
ret

Мой вопрос: как надежно вычислить эти числа? Поскольку я не сильно разбираюсь в математике, я был бы признателен за пример кода на C++ (или аналогичном языке, чтобы я мог его перевести), а не просто за теоретическое объяснение.
Я уже нашел способ вычислить вторую константу для сравнения, примерно на основе восторга хакеров и исходного кода libdivde:

Код: Выделить всё

struct DivMagic64 {
int64_t magic;
uint64_t cmpConst;
};

constexpr DivMagic64 computeDivMagic(uint64_t d) {
assert(d >= 1 && (d & 1)); // only works for odd divisors

const uint64_t cmpConstant = ~uint64_t(0) / d + 1;

int64_t magic = ???;

return { magic, cmpConstant };
}

Основная проблема заключается в первой магической константе. Для некоторых делителей, таких как «5», его можно вычислить как «1 - cmpConstant», однако я понятия не имею, как clang получает значение для такого делителя, как 2573:

Код: Выделить всё

movabs rax, -5570586920043653947 // ???
imul rax, rdi
movabs rcx, 7169352535448719 // correctly calculated in computeDivMagic
cmp rax, rcx

Я также пытался использовать вышеупомянутый исходный код непосредственно для вычислений, однако они, похоже, требуют выполнения дополнительных операций с дивидендом, чего clang специально избегает в своих вычислениях.

Подробнее здесь: https://stackoverflow.com/questions/798 ... odulo-oper