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

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

9 голосов
/ 26 августа 2010

Это (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 ]

5 голосов
/ 26 августа 2010

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

1 голос
/ 01 февраля 2017

Если ваш дивиденд 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

...