/*
 * 8bit divide and modulo routines by using add/sub/shift only
 *
 * Uses the bruteforce algorithm, start from 0 and add divisor
 * until we reach dividend. The number of times divisor was added
 * is the division result. Modulo and signed routines are derived
 * from this basic routine.
 *
 * The idea was to get the routines as small and simple as possible.
 *
 * Written by Harry "Piru" Sintonen <sintonen@iki.fi>.
 * Placed in Public Domain.
 *
 */

#include <stdio.h>

int udiv(unsigned char a, unsigned char b);
int umod(unsigned char a, unsigned char b);
int sdiv(signed char a, signed char b);
int smod(signed char a, signed char b);

/* these need to be implemented, left as an excersice of the coder */
#define umul(a,b) ((a)*(b))
#define smul(a,b) ((a)*(b))

int main(void)
{
  unsigned char i, j;
  signed char a, b;

  for (j = 0; j != 255; j++)
  {
    for (i = 1; i != 255; i++)
    {
      if (udiv(j, i) != j / i)
      {
        printf("udiv %d/%d bugged\n", j, i);
        return 1;
      }

      if (umod(j, i) != j % i)
      {
        printf("umod %d%%%d bugged\n", j, i);
        return 1;
      }
    }
  }
  printf("udiv/umod ok\n");

  for (b = -128; b != 127; b++)
  {
    for (a = -128; a != 127; a++)
    {
      if (a == 0) a++;

      if (sdiv(b, a) != b / a)
      {
        printf("sdiv %d/%d bugged\n", b, a);
        return 1;
      }

      if (smod(b, a) != b % a)
      {
        printf("smod %d%%%d bugged\n", b, a);
        return 1;
      }
    }
  }
  printf("sdiv/smod ok\n");

  return 0;
}


int udiv(unsigned char a, unsigned char b)
{
  int m = 0, cnt = 0;

#if 0
  /* division by zero check, implementation specific */
  if (b == 0)
    return 0/b;
#endif

#if 0
  /* speedups, with cost of extra code */
  if (b > a)
    return 0;

  if (b == a)
    return 1;

  switch (b)
  {
    case 128: a >>= 1;
    case 64:  a >>= 1;
    case 32:  a >>= 1;
    case 16:  a >>= 1;
    case 8:   a >>= 1;
    case 4:   a >>= 1;
    case 2:   a >>= 1;
    case 1:   return a;
  }
#endif

  while (m < a)
  {
    m += b;
    cnt++;
  }

  if (m != a)
    cnt--;

  return cnt;
}

int umod(unsigned char a, unsigned char b)
{
  return a - umul(udiv(a, b), b);
}

int sdiv(signed char a, signed char b)
{
  int r;

  r = udiv(a < 0 ? -a : a, b < 0 ? -b : b);

  return (a < 0 && b > 0) || (a > 0 && b < 0) ? -r : r;
}

int smod(signed char a, signed char b)
{
  return a - smul(sdiv(a, b), b);
}

/*
 * EOF
 */