// Origin: abbott@dima.unige.it
// PR c/5120

extern void * malloc (__SIZE_TYPE__);
extern void * calloc (__SIZE_TYPE__, __SIZE_TYPE__);

typedef unsigned int FFelem;

FFelem FFmul(const FFelem x, const FFelem y)
{
  return x;
}


struct DUPFFstruct
{
  int maxdeg;
  int deg;
  FFelem *coeffs;
};

typedef struct DUPFFstruct *DUPFF;


int DUPFFdeg(const DUPFF f)
{
  return f->deg;
}


DUPFF DUPFFnew(const int maxdeg)
{
  DUPFF ans = (DUPFF)malloc(sizeof(struct DUPFFstruct));
  ans->coeffs = 0;
  if (maxdeg >= 0) ans->coeffs = (FFelem*)calloc(maxdeg+1,sizeof(FFelem));
  ans->maxdeg = maxdeg;
  ans->deg = -1;
  return ans;
}

void DUPFFfree(DUPFF x)
{
}

void DUPFFswap(DUPFF x, DUPFF y)
{
}


DUPFF DUPFFcopy(const DUPFF x)
{
  return x;
}


void DUPFFshift_add(DUPFF f, const DUPFF g, int deg, const FFelem coeff)
{
}


DUPFF DUPFFexgcd(DUPFF *fcofac, DUPFF *gcofac, const DUPFF f, const DUPFF g)
{
  DUPFF u, v, uf, ug, vf, vg;
  FFelem q, lcu, lcvrecip, p;
  int df, dg, du, dv;

  printf("DUPFFexgcd called on degrees %d and %d\n", DUPFFdeg(f), DUPFFdeg(g));
  if (DUPFFdeg(f) < DUPFFdeg(g)) return DUPFFexgcd(gcofac, fcofac, g, f);  /*** BUG IN THIS LINE ***/
  if (DUPFFdeg(f) != 2 || DUPFFdeg(g) != 1) abort();
  if (f->coeffs[0] == 0) return f;
  /****** NEVER REACH HERE IN THE EXAMPLE ******/
  p = 2;

  df = DUPFFdeg(f);  if (df < 0) df = 0; /* both inputs are zero */
  dg = DUPFFdeg(g);  if (dg < 0) dg = 0; /* one input is zero */
  u = DUPFFcopy(f);
  v = DUPFFcopy(g);

  uf = DUPFFnew(dg); uf->coeffs[0] = 1; uf->deg = 0;
  ug = DUPFFnew(df);
  vf = DUPFFnew(dg);
  vg = DUPFFnew(df); vg->coeffs[0] = 1; vg->deg = 0;

  while (DUPFFdeg(v) > 0)
  {
    dv = DUPFFdeg(v);
    lcvrecip = FFmul(1, v->coeffs[dv]);
    while (DUPFFdeg(u) >= dv)
    {
      du = DUPFFdeg(u);
      lcu = u->coeffs[du];
      q = FFmul(lcu, lcvrecip);
      DUPFFshift_add(u, v, du-dv, p-q);
      DUPFFshift_add(uf, vf, du-dv, p-q);
      DUPFFshift_add(ug, vg, du-dv, p-q);
    }
    DUPFFswap(u, v);
    DUPFFswap(uf, vf);
    DUPFFswap(ug, vg);
  }
  if (DUPFFdeg(v) == 0)
  {
    DUPFFswap(u, v);
    DUPFFswap(uf, vf);
    DUPFFswap(ug, vg);
  }
  DUPFFfree(vf);
  DUPFFfree(vg);
  DUPFFfree(v);
  *fcofac = uf;
  *gcofac = ug;
  return u;
}


int main()
{
  DUPFF f, g, cf, cg, h;
  f = DUPFFnew(1); f->coeffs[1] = 1; f->deg = 1;
  g = DUPFFnew(2); g->coeffs[2] = 1; g->deg = 2;

  printf("calling DUPFFexgcd on degrees %d and %d\n", DUPFFdeg(f), DUPFFdeg(g)) ;
  h = DUPFFexgcd(&cf, &cg, f, g);
  return 0;
}