Как выполнить 64-разрядное деление с помощью 32-разрядной инструкции деления?

Это (AFAIK) конкретный вопрос в этой общей теме.

Вот ситуация:

У меня есть встроенная система (игровая консоль), основанная на 32-битном RISC-микроконтроллере (вариант NEC V810). Я хочу написать математическую библиотеку с фиксированной запятой. Я читал эту статью, но прилагаемый исходный код написан на сборке 386, поэтому он не может быть использован напрямую или изменен.

В V810 есть встроенное целое умножение / деление, но я хочу использовать формат 18.14, упомянутый в статье выше. Это требует деления 64-битного int на 32-битное int, а V810 только (со знаком или без знака) выполняет 32-битное /32-битное деление (что дает 32-битное отношение и 32-битное остаток).

Итак, мой вопрос: как мне симулировать 64-битное /32-битное деление с 32-битным /32-битным (чтобы обеспечить предварительное смещение дивиденда)? Или, если взглянуть на проблему по-другому, как лучше разделить фиксированную точку 18,14 на другую, используя стандартные 32-битные арифметические / логические операции? ("лучший" означает самый быстрый, самый маленький или оба).

Алгебра, сборка (V810) и псевдокод все в порядке. Я буду звонить код из C.

Заранее спасибо!

РЕДАКТИРОВАТЬ: Каким-то образом я пропустил этот вопрос... Тем не менее, он все еще будет нуждаться в некоторой модификации, чтобы быть супер-эффективным (он должен быть быстрее, чем div с плавающей точкой, предоставляемый v810, хотя это может быть уже...), так что не стесняйтесь делать мою работу за меня в обмен на очки репутации;) (и, конечно, кредит в моей библиотечной документации).

Источник

2 ответа

Решение

В GCC есть такая подпрограмма для многих процессоров, которая называется _divdi3 (обычно реализуется с использованием обычного вызова divmod). Вот один Некоторые ядра Unix также имеют реализацию, например, FreeBSD.

Источник

Если ваш дивиденд без знака 64 бита, ваш делитель без знака 32 бита, архитектура i386 (x86), div Инструкция по сборке может помочь вам с подготовкой:

#include <stdint.h>
/* Returns *a % b, and sets *a = *a_old / b; */
uint32_t UInt64DivAndGetMod(uint64_t *a, uint32_t b) {
#ifdef __i386__  /* u64 / u32 division with little i386 machine code. */
  uint32_t upper = ((uint32_t*)a)[1], r;
  ((uint32_t*)a)[1] = 0;
  if (upper >= b) {   
    ((uint32_t*)a)[1] = upper / b;
    upper %= b;
  }
  __asm__("divl %2" : "=a" (((uint32_t*)a)[0]), "=d" (r) :
      "rm" (b), "0" (((uint32_t*)a)[0]), "1" (upper));
  return r;
#else
  const uint64_t q = *a / b;  /* Calls __udivdi3 in libgcc. */
  const uint32_t r = *a - b * q;  /* `r = *a % b' would use __umoddi3. */
  *a = q;
  return r;
#endif
}

Если строка выше с __udivdi3 не компилируется для вас, используйте __div64_32 функция из ядра Linux: https://github.com/torvalds/linux/blob/master/lib/div64.c

Источник
Другие вопросы по тегам