+++ /dev/null
-// 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;
-}