/* Copyright (c) 2009 Ian Piumarta
 * All rights reserved.
 * See the file COPYING for details.
 */

#include "_mpint.h"

/* quo = dend / dsor; rem = dend % dsor (answer the remainder) */

mp_t *mp_div(mp_t *quo, mp_t *rem, mp_t *dend, mp_t *dsor)
{
  mp_clear(rem);
  if (mp_zerop(dsor)) return mp_clear(quo);
  if (mp_zerop(dend)) return mp_clear(quo);
  mp_t out= MP_INITIALISER;
  int n= 0;
  if (dsor->width < dend->width) {
    mp_size_t w= dend->width - dsor->width;
    mp_shiftl(dsor, 32 * w);
    n += 32 * w;
    while (mp_cmp(dsor, dend) > 0) {
      mp_shiftr(dsor, 1);
      --n;
    }
  }
  while (mp_cmp(dsor, dend) <= 0) {
    mp_shiftl(dsor, 1);
    ++n;
  }
  mp_copy(rem, dend);
  while (n--) {
    mp_shiftr(dsor, 1);
    mp_shiftl(&out, 1);
    if (mp_cmp(dsor, rem) <= 0) {
      mp_sub(rem, dsor);
      mp_digitAtPut(&out, 0, mp_digitAt(&out, 0) | 1);
    }
  }
  mp_copy(quo, &out);
  mp_clear(&out);
  mp_normalise(quo);
  return mp_normalise(rem);
}