How to calculate division remainder in SPARC Assembly?

Question

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

Laughton

This is assembly?! For what chip? – Au

in SPARC. I must have written what architecture is.. – Laughton

#5190131. As originally asked, the question was about the 6800, but the answer is about eqally applicable to any processor without a divide instruction. – Appoggiatura

@JerryCoffin Wow, That's so awesome! – Laughton

Answer 1

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

Cassareep

I think that if (*dividendh >= 0x80) { *dividendh = (*dividendh << 1) | (*dividendl >> (8 - 1)); *dividendl <<= 1; *dividendh -= divisor; *dividendl |= 1; } is not necessary – Laughton

@manutd: if you remove that part, the code won't always work correctly. I'm going to update the answer with more code to demonstrate it. – Cassareep

I agree with you in case of that dividendh has some initial value (!= 0) But If dividendh has initial value as 0, The result of two function is same. – Laughton

Could you tell me Why did you put non-zero value in dividendh? Isn't it a reminder? If it is reminder, Wouldn't it be better to set the initial value of dividendh to zero? – Laughton

@manutd: many CPUs's division instructions divide 2N bits by N bits (and return N bits of quotient and N bits of remainder) basically doing the opposite of multiplication where you multiply N bits by N bits and get 2N bits. That's what I did. The calculations are done in-place (the remainder appears in dividendh and quotient in dividendl), which is also very typical of those divide instructions and division subroutines. – Cassareep

Thanks. However, in your code, you put the non-zero initial value to dividendh(for (dividendh = 0; dividendh <= 0xFF; dividendh++)). the initial setting value of remainder is non-zero. I wonder why you did? – Laughton

@manutd: I explained it: *dividendh contains 8 most significant bits of the dividend before calling u8div(), but after the call it contains the remainder. – Cassareep

Answer 2

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.

Bronze