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
FFmul(const FFelem x,const FFelem y)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
DUPFFdeg(const DUPFF f)25 int DUPFFdeg(const DUPFF f)
26 {
27 return f->deg;
28 }
29
30
DUPFFnew(const int maxdeg)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
DUPFFfree(DUPFF x)41 void DUPFFfree(DUPFF x)
42 {
43 }
44
DUPFFswap(DUPFF x,DUPFF y)45 void DUPFFswap(DUPFF x, DUPFF y)
46 {
47 }
48
49
DUPFFcopy(const DUPFF x)50 DUPFF DUPFFcopy(const DUPFF x)
51 {
52 return x;
53 }
54
55
DUPFFshift_add(DUPFF f,const DUPFF g,int deg,const FFelem coeff)56 void DUPFFshift_add(DUPFF f, const DUPFF g, int deg, const FFelem coeff)
57 {
58 }
59
60
DUPFFexgcd(DUPFF * fcofac,DUPFF * gcofac,const DUPFF f,const DUPFF g)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
main()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 }
127