1// Origin: abbott@dima.unige.it
2// PR c/5120
3
4extern void * malloc (__SIZE_TYPE__);
5extern void * calloc (__SIZE_TYPE__, __SIZE_TYPE__);
6
7typedef unsigned int FFelem;
8
9FFelem FFmul(const FFelem x, const FFelem y)
10{
11  return x;
12}
13
14
15struct DUPFFstruct
16{
17  int maxdeg;
18  int deg;
19  FFelem *coeffs;
20};
21
22typedef struct DUPFFstruct *DUPFF;
23
24
25int DUPFFdeg(const DUPFF f)
26{
27  return f->deg;
28}
29
30
31DUPFF 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
41void DUPFFfree(DUPFF x)
42{
43}
44
45void DUPFFswap(DUPFF x, DUPFF y)
46{
47}
48
49
50DUPFF DUPFFcopy(const DUPFF x)
51{
52  return x;
53}
54
55
56void DUPFFshift_add(DUPFF f, const DUPFF g, int deg, const FFelem coeff)
57{
58}
59
60
61DUPFF 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
117int 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}
127