ECE 222 - Restoring Binary Division Algorithm

gistfile1.c

/*
Output:

Q:  17, A:   0, M:   5 [00000000 00010001]
Q:  34, A:   0, M:   5 [00000000 00100010]
Q:  68, A:   0, M:   5 [00000000 01000100]
Q: 136, A:   0, M:   5 [00000000 10001000]
Q:  16, A:   1, M:   5 [00000001 00010000]
Q:  32, A:   2, M:   5 [00000010 00100000]
Q:  64, A:   4, M:   5 [00000100 01000000]
Q: 129, A:   3, M:   5 [00000011 10000001]
Q:   3, A:   2, M:   5 [00000010 00000011]
17 / 5 = 3
17 % 5 = 2
                   
*/

#include <stdio.h>

void binout_helper(int in, int left) {
  if (left == 0) return;
  binout_helper(in >> 1, left - 1);
  printf("%d",in & 1);
}

void binout(int in) {
  binout_helper(in,8);
}

void print_status(int Q,int A, int M) {
  printf("Q: %3d, A: %3d, M: %3d [",Q,A,M);
  binout(A); printf(" ");
  binout(Q); printf("]\n");
}

int main() {
  unsigned char dividend = 17;
  unsigned char divisor = 5;

  // NOTE: In a real binary division circuit, A would have one more bit than Q
  unsigned char A = 0;
  unsigned char Q = dividend;
  unsigned char M = divisor;

  print_status(Q,A,M);

  for (int i = 0; i < 8; i++) {

    // Step 1: Shift A and Q left
    int AQ = (A << 8) + Q;
    AQ <<= 1;
    A = (AQ >> 8) & 0xFF;
    Q = AQ & 0xFF;

    // Step 2: Subtract M from A, place answer in A
    A -= M;

    if (A & (1 << 7)) {
      // If the sign bit of A is 1, set q_0 to 0 
      Q &= ~1;
      // and add M back to A (restore A)
      A += M;
    } else {
      // otherwise, set q_0 to 1
      Q |= 1;
    }

    print_status(Q,A,M);
  }

  unsigned char quotient = Q;
  unsigned char remainder = A;

  printf("%d / %d = %d\n" ,dividend,divisor,quotient);
  printf("%d %% %d = %d\n",dividend,divisor,remainder);
  return 0;
}