Как рассчитать остаток от деления в сборке SPARC?

Вот псевдокод, который вычисляет деление двух положительных целых чисел.
Регистр HR сохраняет остаток, а LR сохраняет делимое. (и в конечном итоге сохраняет root)

Однако я думаю, что у этого алгоритма есть некоторые проблемы.
Потому что этот алгоритм иногда не восстанавливает вычитание. (Деление является продолжением вычитания.)

Например, 6 / 3 (0110 / 011)
Этот алгоритм вычитает -3 еще раз. (Такая ситуация никогда не возникает, когда мы вычисляем это деление вручную)
Так что я думаю, что у этого алгоритма есть некоторые проблемы.
Вы не согласны со мной? Как рассчитать остаток от деления в сборке?

for i = 1 to num_of_bits do
(HR LR) << 1
if (HR >= 0) then
   HR = HR - DIVISOR
else
   HR = HR + DIVISOR
endif
if (HR > 0) then LR(lsb) = 1 endif
endfor

algorithm assembly division integer-division sparc
person manutd    schedule 10.10.2011    source источник
comment
Это сборка?! Для какого чипа?   -  person Matt Phillips    schedule 10.10.2011
comment
в СПАРК. Я, должно быть, написал, что такое архитектура..   -  person manutd    schedule 10.10.2011
comment
stackoverflow.com/questions/5189631/. Как изначально было задано, вопрос был о 6800, но ответ в равной степени применим к любому процессору без инструкции деления.   -  person Jerry Coffin    schedule 10.10.2011
comment
@JerryCoffin Вау, это так здорово!   -  person manutd    schedule 10.10.2011

Ответы (2)


arrow_upward
1
arrow_downward

Я не говорю на ассемблере SPARC, но говорю на Си. Вот пример реализации алгоритма деления 16/8=8,8:

#include <stdio.h>

typedef unsigned char uint8;
typedef unsigned int uint;

int u8div(uint8* dividendh, uint8* dividendl, uint8 divisor)
{
  int i;

  if (*dividendh >= divisor)
    return 0; // overflow

  for (i = 0; i < 8; i++)
  {
    if (*dividendh >= 0x80)
    {
      *dividendh = (*dividendh << 1) | (*dividendl >> (8 - 1));
      *dividendl <<= 1;

      *dividendh -= divisor;
      *dividendl |= 1;
    }
    else
    {
      *dividendh = (*dividendh << 1) | (*dividendl >> (8 - 1));
      *dividendl <<= 1;

      if (*dividendh >= divisor)
      {
        *dividendh -= divisor;
        *dividendl |= 1;
      }
    }
  }

  return 1;
}

int u8div2(uint8* dividendh, uint8* dividendl, uint8 divisor)
{
  uint dividend = (*dividendh << 8) | *dividendl;

  if (*dividendh >= divisor)
    return 0; // overflow

  *dividendl = dividend / divisor;
  *dividendh = dividend % divisor;

  return 1;
}

int main(void)
{
  uint dividendh, dividendl, divisor;

  for (dividendh = 0; dividendh <= 0xFF; dividendh++)
    for (dividendl = 0; dividendl <= 0xFF; dividendl++)
      for (divisor = 0; divisor <= 0xFF; divisor++)
      {
        uint8 divh = dividendh, divl = dividendl, divr = divisor;
        uint8 divh2 = dividendh, divl2 = dividendl;

        printf("0x%04X/0x%02X=", (divh << 8) | divl, divr);

        if (u8div(&divh, &divl, divr))
          printf("0x%02X.0x%02X", divl, divh);
        else
          printf("ovf");

        printf(" ");

        if (u8div2(&divh2, &divl2, divr))
          printf("0x%02X.0x%02X", divl2, divh2);
        else
          printf("ovf");

        if ((divl != divl2) || (divh != divh2))
          printf(" err"); // "err" will be printed if u8div() computes incorrect result

        printf("\n");
      }

  return 0;
}
person Alexey Frunze    schedule 10.10.2011
comment
Я думаю, что if (*dividendh >= 0x80) { *dividendh = (*dividendh << 1) | (*dividendl >> (8 - 1)); *dividendl <<= 1; *dividendh -= divisor; *dividendl |= 1; } не нужно - person manutd; 10.10.2011
comment
@manutd: если вы удалите эту часть, код не всегда будет работать правильно. Я собираюсь обновить ответ дополнительным кодом, чтобы продемонстрировать это. - person Alexey Frunze; 10.10.2011
comment
Я согласен с вами в случае, если дивиденд имеет некоторое начальное значение (! = 0). Но если дивиденд имеет начальное значение как 0, результат двух функций одинаков. - person manutd; 10.10.2011
comment
Не могли бы вы сказать мне, почему вы присвоили дивидендам ненулевое значение? Разве это не напоминание? Если это напоминание, не лучше ли установить начальное значение дивиденда равным нулю? - person manutd; 10.10.2011
comment
@manutd: инструкции деления многих процессоров делят 2N бит на N бит (и возвращают N бит частного и N бит остатка), в основном делая противоположное умножению, когда вы умножаете N бит на N бит и получаете 2N бит. Это то, что я сделал. Вычисления выполняются на месте (остаток появляется в делимом и частное в делимом), что также очень типично для команд деления и подпрограмм деления. - person Alexey Frunze; 10.10.2011
comment
Спасибо. Однако в вашем коде вы помещаете ненулевое начальное значение в дивидендh(for (dividendh = 0; dividendh <= 0xFF; dividendh++)). начальное значение остатка не равно нулю. Интересно, почему вы это сделали? - person manutd; 10.10.2011
comment
@manutd: я объяснил это: *dividendh содержит 8 старших битов дивиденда перед вызовом u8div(), но после вызова он содержит остаток. - person Alexey Frunze; 10.10.2011

arrow_upward
3
arrow_downward

Несколько реализаций алгоритма деления (который также вычисляет остаток) можно найти в приложении E к архитектуре SPARC. руководство.

Более новая версия архитектуры SPARC включает в себя операторы деления UDIV и SDIV.

Дальнейшую реализацию можно найти здесь.

person Codo    schedule 10.10.2011