CODEWITHSUNDEEP
algorithmassemblydivisioninteger-divisionsparc
manutd
manutd

Reputation: 564

How to calculate division remainder in SPARC Assembly?

Here is the pseudo code which computes division of two positive integers.
HR register saves remainder, and LR saves dividend. (and eventually saves root)

However I think this algorithm has some problem.
Because this algorithm sometimes don't recover subtraction.(Division is a continuation of subtraction.)

For example 6 / 3 (0110 / 011)
This algorithm subtract -3 one more time. (This situation never occur when we calculate this division by hand)
So I think this algorithm has some problem.
Don't you agree with me? How to calculate division remainder in Assembly?

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

Upvotes: 2

Views: 2789

Answers (2)

Alexey Frunze
Alexey Frunze

Reputation: 62096

I don't speak SPARC asm, but I do speak C. Here's a sample implementation of the algorithm for 16/8=8,8 division:

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

Upvotes: 1

Codo
Codo

Reputation: 78915

Several implementation of the division algorithm (that also computes the remainder) can be found in appendix E of the SPARC architecture manual.

Newer version of the SPARC architecture include the division operators UDIV and SDIV.

A furhter implemenation can be found here.

Upvotes: 3

Related Questions