1  // Origin: abbott@dima.unige.it
       2  // PR c/5120
       3  
       4  extern void * malloc (__SIZE_TYPE__);
       5  extern void * calloc (__SIZE_TYPE__, __SIZE_TYPE__);
       6  
       7  typedef unsigned int FFelem;
       8  
       9  FFelem FFmul(const FFelem x, const FFelem y)
      10  {
      11    return x;
      12  }
      13  
      14  
      15  struct DUPFFstruct
      16  {
      17    int maxdeg;
      18    int deg;
      19    FFelem *coeffs;
      20  };
      21  
      22  typedef struct DUPFFstruct *DUPFF;
      23  
      24  
      25  int DUPFFdeg(const DUPFF f)
      26  {
      27    return f->deg;
      28  }
      29  
      30  
      31  DUPFF DUPFFnew(const int maxdeg)
      32  {
      33    DUPFF ans = (DUPFF)malloc(sizeof(struct DUPFFstruct));
      34    ans->coeffs = 0;
      35    if (maxdeg >= 0) ans->coeffs = (FFelem*)calloc(maxdeg+1,sizeof(FFelem));
      36    ans->maxdeg = maxdeg;
      37    ans->deg = -1;
      38    return ans;
      39  }
      40  
      41  void DUPFFfree(DUPFF x)
      42  {
      43  }
      44  
      45  void DUPFFswap(DUPFF x, DUPFF y)
      46  {
      47  }
      48  
      49  
      50  DUPFF DUPFFcopy(const DUPFF x)
      51  {
      52    return x;
      53  }
      54  
      55  
      56  void DUPFFshift_add(DUPFF f, const DUPFF g, int deg, const FFelem coeff)
      57  {
      58  }
      59  
      60  
      61  DUPFF DUPFFexgcd(DUPFF *fcofac, DUPFF *gcofac, const DUPFF f, const DUPFF g)
      62  {
      63    DUPFF u, v, uf, ug, vf, vg;
      64    FFelem q, lcu, lcvrecip, p;
      65    int df, dg, du, dv;
      66  
      67    printf("DUPFFexgcd called on degrees %d and %d\n", DUPFFdeg(f), DUPFFdeg(g));
      68    if (DUPFFdeg(f) < DUPFFdeg(g)) return DUPFFexgcd(gcofac, fcofac, g, f);  /*** BUG IN THIS LINE ***/
      69    if (DUPFFdeg(f) != 2 || DUPFFdeg(g) != 1) abort();
      70    if (f->coeffs[0] == 0) return f;
      71    /****** NEVER REACH HERE IN THE EXAMPLE ******/
      72    p = 2;
      73  
      74    df = DUPFFdeg(f);  if (df < 0) df = 0; /* both inputs are zero */
      75    dg = DUPFFdeg(g);  if (dg < 0) dg = 0; /* one input is zero */
      76    u = DUPFFcopy(f);
      77    v = DUPFFcopy(g);
      78  
      79    uf = DUPFFnew(dg); uf->coeffs[0] = 1; uf->deg = 0;
      80    ug = DUPFFnew(df);
      81    vf = DUPFFnew(dg);
      82    vg = DUPFFnew(df); vg->coeffs[0] = 1; vg->deg = 0;
      83  
      84    while (DUPFFdeg(v) > 0)
      85    {
      86      dv = DUPFFdeg(v);
      87      lcvrecip = FFmul(1, v->coeffs[dv]);
      88      while (DUPFFdeg(u) >= dv)
      89      {
      90        du = DUPFFdeg(u);
      91        lcu = u->coeffs[du];
      92        q = FFmul(lcu, lcvrecip);
      93        DUPFFshift_add(u, v, du-dv, p-q);
      94        DUPFFshift_add(uf, vf, du-dv, p-q);
      95        DUPFFshift_add(ug, vg, du-dv, p-q);
      96      }
      97      DUPFFswap(u, v);
      98      DUPFFswap(uf, vf);
      99      DUPFFswap(ug, vg);
     100    }
     101    if (DUPFFdeg(v) == 0)
     102    {
     103      DUPFFswap(u, v);
     104      DUPFFswap(uf, vf);
     105      DUPFFswap(ug, vg);
     106    }
     107    DUPFFfree(vf);
     108    DUPFFfree(vg);
     109    DUPFFfree(v);
     110    *fcofac = uf;
     111    *gcofac = ug;
     112    return u;
     113  }
     114  
     115  
     116  
     117  int main()
     118  {
     119    DUPFF f, g, cf, cg, h;
     120    f = DUPFFnew(1); f->coeffs[1] = 1; f->deg = 1;
     121    g = DUPFFnew(2); g->coeffs[2] = 1; g->deg = 2;
     122  
     123    printf("calling DUPFFexgcd on degrees %d and %d\n", DUPFFdeg(f), DUPFFdeg(g)) ;
     124    h = DUPFFexgcd(&cf, &cg, f, g);
     125    return 0;
     126  }