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

http://stackoverflow.com/questions/5189631/how-can-i-take-mod-of-a-number-in-assembly-in-motorola-m6800/5189800#5189800. As originally asked, the question was about the 6800, but the answer is about eqally applicable to any processor without a divide instruction. — Jerry Coffin, Oct 10 '11 at 05:34

score 3 · Answer 1 · answered Oct 10 '11 at 06:24

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.

Alexey Frunze · Accepted Answer · 2011-10-10T10:51:06.193

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

edited Oct 10 '11 at 10:51

answered Oct 10 '11 at 05:57

Alexey Frunze

61,140
12
83
180

I think that `if (*dividendh >= 0x80) { *dividendh = (*dividendh << 1) | (*dividendl >> (8 - 1)); *dividendl <<= 1; *dividendh -= divisor; *dividendl |= 1; }` is not necessary – manutd Oct 10 '11 at 10:30
@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. – Alexey Frunze Oct 10 '11 at 10:49
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. – manutd Oct 10 '11 at 11:47
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? – manutd Oct 10 '11 at 11:51
@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. – Alexey Frunze Oct 10 '11 at 11:56
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? – manutd Oct 10 '11 at 12:09
@manutd: I explained it: *dividendh contains 8 most significant bits of the dividend before calling u8div(), but after the call it contains the remainder. – Alexey Frunze Oct 10 '11 at 18:57

How to calculate division remainder in SPARC Assembly?

2 Answers2

Linked