#include <stdlib.h>

unsigned udiv (unsigned x, unsigned y, unsigned *r);

int sdiv (int x, int y, int *r)
{
  unsigned r2, q;

  q = udiv ((x < 0) ? -x : x, (y < 0) ? -y : y, &r2);
  if (x < 0) q = -q, r2 = -r2;
  if (y < 0) q = -q;
  if (r) *r = r2;
  return q;
}

unsigned udiv (unsigned x, unsigned y, unsigned *r)
{
  unsigned q = 0;
  unsigned m = 1;

  if (y == 0) abort ();

  while ((y << 1) && (x >= (y << 1)))
    m <<= 1, y <<= 1;

  while (m)
    {
      if (x >= y)
        x -= y, q += m;
      m >>= 1;
      y >>= 1;
    }

  if (r) *r = x;

  return q;
}