Annotation of OpenXM_contrib2/asir2000/engine/nd.h, Revision 1.10
1.1 noro 1: #include "ca.h"
2: #include "parse.h"
3: #include "ox.h"
4: #include "base.h"
5: #include "inline.h"
6: #include <time.h>
7:
8: #if defined(__GNUC__)
9: #define INLINE inline
10: #elif defined(VISUAL)
11: #define INLINE __inline
12: #else
13: #define INLINE
14: #endif
15:
16: typedef unsigned int UINT;
17:
18: #define USE_GEOBUCKET 1
19: #define USE_UNROLL 1
20:
21: #define REDTAB_LEN 32003
22:
23: /* GeoBucket for polynomial addition */
24:
25: typedef struct oPGeoBucket {
26: int m;
27: struct oND *body[32];
28: } *PGeoBucket;
29:
30: /* distributed polynomial; linked list rep. */
31: typedef struct oND {
32: struct oNM *body;
33: int nv;
34: int len;
35: int sugar;
36: } *ND;
37:
38: /* distributed polynomial; array rep. */
39: typedef struct oNDV {
40: struct oNMV *body;
41: int nv;
42: int len;
43: int sugar;
44: } *NDV;
45:
46: typedef union oNDC {
47: int m;
1.10 ! noro 48: Z z;
1.1 noro 49: P p;
50: } *NDC;
51:
52: /* monomial; linked list rep. */
53: typedef struct oNM {
54: struct oNM *next;
55: union oNDC c;
56: UINT dl[1];
57: } *NM;
58:
59: /* monomial; array rep. */
60: typedef struct oNMV {
61: union oNDC c;
62: UINT dl[1];
63: } *NMV;
64:
65: /* history of reducer */
66: typedef struct oRHist {
67: struct oRHist *next;
68: int index;
69: int sugar;
70: UINT dl[1];
71: } *RHist;
72:
73: /* S-pair list */
74: typedef struct oND_pairs {
75: struct oND_pairs *next;
76: int i1,i2;
77: int sugar;
78: UINT lcm[1];
79: } *ND_pairs;
80:
81: /* index and shift count for each exponent */
82: typedef struct oEPOS {
83: int i; /* index */
84: int s; /* shift */
85: } *EPOS;
86:
87: typedef struct oBlockMask {
88: int n;
89: struct order_pair *order_pair;
90: UINT **mask;
91: } *BlockMask;
92:
93: typedef struct oBaseSet {
94: int len;
95: NDV *ps;
96: UINT **bound;
97: } *BaseSet;
98:
99: typedef struct oNM_ind_pair
100: {
101: NM mul;
102: int index,sugar;
103: } *NM_ind_pair;
104:
105: typedef struct oIndArray
106: {
107: char width;
108: int head;
109: union {
110: unsigned char *c;
111: unsigned short *s;
112: unsigned int *i;
113: } index;
114: } *IndArray;
115:
116: extern int (*ndl_compare_function)(UINT *a1,UINT *a2);
117: extern int nd_dcomp;
118:
119: extern NM _nm_free_list;
120: extern ND _nd_free_list;
121: extern ND_pairs _ndp_free_list;
122:
123: extern struct order_spec *dp_current_spec;
124: extern char *Demand;
125: extern VL CO;
126: extern int Top,Reverse,DP_Print,dp_nelim,do_weyl,NoSugar;
127: extern int *current_weyl_weight_vector;
128:
129: /* fundamental macros */
130: #define TD(d) (d[0])
131: #define HDL(d) ((d)->body->dl)
132: #define HTD(d) (TD(HDL(d)))
133: #define HCM(d) ((d)->body->c.m)
1.10 ! noro 134: #define HCZ(d) ((d)->body->c.z)
1.1 noro 135: #define HCP(d) ((d)->body->c.p)
136: #define CM(a) ((a)->c.m)
1.10 ! noro 137: #define CZ(a) ((a)->c.z)
1.1 noro 138: #define CP(a) ((a)->c.p)
139: #define DL(a) ((a)->dl)
140: #define SG(a) ((a)->sugar)
141: #define LEN(a) ((a)->len)
142: #define LCM(a) ((a)->lcm)
143: #define GET_EXP(d,a) (((d)[nd_epos[a].i]>>nd_epos[a].s)&nd_mask0)
144: #define GET_EXP_MASK(d,a,m) ((((d)[nd_epos[a].i]&(m)[nd_epos[a].i])>>nd_epos[a].s)&nd_mask0)
145: #define PUT_EXP(r,a,e) ((r)[nd_epos[a].i] |= ((e)<<nd_epos[a].s))
146: #define XOR_EXP(r,a,e) ((r)[nd_epos[a].i] ^= ((e)<<nd_epos[a].s))
147:
148: #define GET_EXP_OLD(d,a) (((d)[oepos[a].i]>>oepos[a].s)&omask0)
149: #define PUT_EXP_OLD(r,a,e) ((r)[oepos[a].i] |= ((e)<<oepos[a].s))
150:
151: #define ROUND_FOR_ALIGN(s) ((((s)+sizeof(void *)-1)/sizeof(void *))*sizeof(void *))
152:
153: /* macros for term comparison */
154: #define TD_DL_COMPARE(d1,d2)\
155: (TD(d1)>TD(d2)?1:(TD(d1)<TD(d2)?-1:ndl_lex_compare(d1,d2)))
156: #if 0
157: #define DL_COMPARE(d1,d2)\
158: (nd_dcomp>0?TD_DL_COMPARE(d1,d2)\
159: :(nd_dcomp==0?ndl_lex_compare(d1,d2)\
160: :(nd_blockmask?ndl_block_compare(d1,d2)\
161: :(*ndl_compare_function)(d1,d2))))
162: #else
163: #define DL_COMPARE(d1,d2)\
164: (nd_dcomp>0?TD_DL_COMPARE(d1,d2):(*ndl_compare_function)(d1,d2))
165: #endif
166:
167: /* allocators */
168: #define NEWRHist(r) \
169: ((r)=(RHist)MALLOC(sizeof(struct oRHist)+(nd_wpd-1)*sizeof(UINT)))
170: #define NEWND_pairs(m) \
171: if(!_ndp_free_list)_NDP_alloc();\
172: (m)=_ndp_free_list; _ndp_free_list = NEXT(_ndp_free_list)
173: #define NEWNM(m)\
174: if(!_nm_free_list)_NM_alloc();\
175: (m)=_nm_free_list; _nm_free_list = NEXT(_nm_free_list)
176: #define MKND(n,m,len,d)\
177: if(!_nd_free_list)_ND_alloc();\
178: (d)=_nd_free_list; _nd_free_list = (ND)BDY(_nd_free_list);\
179: NV(d)=(n); LEN(d)=(len); BDY(d)=(m)
180: #define NEWNDV(d) ((d)=(NDV)MALLOC(sizeof(struct oNDV)))
181: #define MKNDV(n,m,l,d) NEWNDV(d); NV(d)=(n); BDY(d)=(m); LEN(d) = l;
182: #define NEWNM_ind_pair(p)\
183: ((p)=(NM_ind_pair)MALLOC(sizeof(struct oNM_ind_pair)))
184:
185: /* allocate and link a new object */
186: #define NEXTRHist(r,c) \
187: if(!(r)){NEWRHist(r);(c)=(r);}else{NEWRHist(NEXT(c));(c)=NEXT(c);}
188: #define NEXTNM(r,c) \
189: if(!(r)){NEWNM(r);(c)=(r);}else{NEWNM(NEXT(c));(c)=NEXT(c);}
190: #define NEXTNM2(r,c,s) \
191: if(!(r)){(c)=(r)=(s);}else{NEXT(c)=(s);(c)=(s);}
192: #define NEXTND_pairs(r,c) \
193: if(!(r)){NEWND_pairs(r);(c)=(r);}else{NEWND_pairs(NEXT(c));(c)=NEXT(c);}
194: #define MKNM_ind_pair(p,m,i,s) (NEWNM_ind_pair(p),(p)->mul=(m),(p)->index=(i),(p)->sugar = (s))
195:
196: /* deallocators */
197: #define FREENM(m) NEXT(m)=_nm_free_list; _nm_free_list=(m)
198: #define FREENDP(m) NEXT(m)=_ndp_free_list; _ndp_free_list=(m)
199: #define FREEND(m) BDY(m)=(NM)_nd_free_list; _nd_free_list=(m)
200:
201: /* macro for increasing pointer to NMV */
202: #define NMV_ADV(m) (m = (NMV)(((char *)m)+nmv_adv))
203: #define NMV_OADV(m) (m = (NMV)(((char *)m)+oadv))
204: #define NDV_NADV(m) (m = (NMV)(((char *)m)+newadv))
205: #define NMV_PREV(m) (m = (NMV)(((char *)m)-nmv_adv))
206: #define NMV_OPREV(m) (m = (NMV)(((char *)m)-oadv))
207:
208: /* external functions */
209: #if 1
210: void GC_gcollect();
211: #endif
212: NODE append_one(NODE,int);
213:
214: /* manipulation of coefficients */
215: void nd_removecont(int mod,ND p);
216: void nd_removecont2(ND p1,ND p2);
1.10 ! noro 217: void removecont_array(Z *c,int n);
1.1 noro 218:
219: /* GeoBucket functions */
220: ND normalize_pbucket(int mod,PGeoBucket g);
221: int head_pbucket(int mod,PGeoBucket g);
1.10 ! noro 222: int head_pbucket_z(PGeoBucket g);
1.1 noro 223: void add_pbucket_symbolic(PGeoBucket g,ND d);
224: void add_pbucket(int mod,PGeoBucket g,ND d);
225: void free_pbucket(PGeoBucket b);
1.10 ! noro 226: void mulz_pbucket(PGeoBucket g,Z c);
1.1 noro 227: NM remove_head_pbucket_symbolic(PGeoBucket g);
228: PGeoBucket create_pbucket();
229:
230: /* manipulation of pairs and bases */
231: int nd_newps(int mod,ND a,ND aq);
232: ND_pairs nd_newpairs( NODE g, int t );
233: ND_pairs nd_minp( ND_pairs d, ND_pairs *prest );
234: ND_pairs nd_minsugarp( ND_pairs d, ND_pairs *prest );
235: NODE update_base(NODE nd,int ndp);
236: ND_pairs update_pairs( ND_pairs d, NODE /* of index */ g, int t);
237: ND_pairs equivalent_pairs( ND_pairs d1, ND_pairs *prest );
238: ND_pairs crit_B( ND_pairs d, int s );
239: ND_pairs crit_M( ND_pairs d1 );
240: ND_pairs crit_F( ND_pairs d1 );
241: int crit_2( int dp1, int dp2 );
242: int ndv_newps(int m,NDV a,NDV aq);
243:
244: /* top level functions */
245: void nd_gr(LIST f,LIST v,int m,int f4,struct order_spec *ord,LIST *rp);
246: void nd_gr_trace(LIST f,LIST v,int trace,int homo,struct order_spec *ord,LIST *rp);
247: NODE nd_f4(int m);
248: NODE nd_gb(int m,int ishomo,int checkonly);
249: NODE nd_gb_trace(int m,int ishomo);
250:
251: /* ndl functions */
252: int ndl_weight(UINT *d);
253: void ndl_weight_mask(UINT *d);
254: void ndl_homogenize(UINT *d,UINT *r,int obpe,EPOS oepos,int weight);
255: void ndl_dehomogenize(UINT *p);
256: void ndl_reconstruct(UINT *d,UINT *r,int obpe,EPOS oepos);
257: INLINE int ndl_reducible(UINT *d1,UINT *d2);
258: INLINE int ndl_lex_compare(UINT *d1,UINT *d2);
259: INLINE int ndl_block_compare(UINT *d1,UINT *d2);
1.2 noro 260: INLINE int ndl_matrix_compare(UINT *d1,UINT *d2);
1.3 noro 261: INLINE int ndl_composite_compare(UINT *d1,UINT *d2);
1.1 noro 262: INLINE int ndl_equal(UINT *d1,UINT *d2);
263: INLINE void ndl_copy(UINT *d1,UINT *d2);
264: INLINE void ndl_zero(UINT *d);
265: INLINE void ndl_add(UINT *d1,UINT *d2,UINT *d);
266: INLINE void ndl_addto(UINT *d1,UINT *d2);
267: INLINE void ndl_sub(UINT *d1,UINT *d2,UINT *d);
268: INLINE int ndl_hash_value(UINT *d);
269:
270: /* normal forms */
271: INLINE int ndl_find_reducer(UINT *g);
272: int nd_sp(int mod,int trace,ND_pairs p,ND *nf);
1.10 ! noro 273: int nd_nf(int mod,ND g,NDV *ps,int full,Q *dn,ND *nf);
1.1 noro 274: int nd_nf_pbucket(int mod,ND g,NDV *ps,int full,ND *nf);
275:
276: /* finalizers */
277: NODE ndv_reducebase(NODE x);
278: NODE ndv_reduceall(int m,NODE f);
279:
280: /* allocators */
281: void nd_free_private_storage();
282: void _NM_alloc();
283: void _ND_alloc();
284: void nd_free(ND p);
285: void nd_free_redlist();
286:
287: /* printing */
288: void ndl_print(UINT *dl);
289: void nd_print(ND p);
1.10 ! noro 290: void nd_print_z(ND p);
1.1 noro 291: void ndp_print(ND_pairs d);
292:
293:
294: /* setup, reconstruct */
295: void nd_init_ord(struct order_spec *spec);
1.6 noro 296: ND_pairs nd_reconstruct(int trace,ND_pairs ndp);
1.1 noro 297: void ndv_setup(int mod,int trace,NODE f);
298: void nd_setup_parameters(int nvar,int max);
299: BlockMask nd_create_blockmask(struct order_spec *ord);
300: EPOS nd_create_epos(struct order_spec *ord);
301: int nd_get_exporigin(struct order_spec *ord);
302: void ndv_mod(int mod,NDV p);
303: NDV ndv_dup(int mod,NDV p);
304: ND nd_dup(ND p);
305:
306: /* ND functions */
307: int ndv_check_candidate(NODE input,int obpe,int oadv,EPOS oepos,NODE cand);
308: void nd_mul_c(int mod,ND p,int mul);
1.10 ! noro 309: void nd_mul_c_z(ND p,Z mul);
1.1 noro 310: void nd_mul_c_p(VL vl,ND p,P mul);
311: ND nd_remove_head(ND p);
312: ND nd_separate_head(ND p,ND *head);
313: int nd_length(ND p);
314: void nd_append_red(UINT *d,int i);
315: UINT *ndv_compute_bound(NDV p);
1.4 noro 316: UINT *nd_compute_bound(ND p);
1.1 noro 317: ND nd_copy(ND p);
318: ND nd_merge(ND p1,ND p2);
319: ND nd_add(int mod,ND p1,ND p2);
1.10 ! noro 320: ND nd_add_z(ND p1,ND p2);
1.1 noro 321: ND nd_add_sf(ND p1,ND p2);
1.7 noro 322: ND nd_quo(int mod,PGeoBucket p,NDV d);
1.1 noro 323: INLINE int nd_length(ND p);
324: NODE nd_f4_red(int m,ND_pairs sp0,UINT *s0vect,int col,NODE rp0);
325: NODE nd_f4_red_dist(int m,ND_pairs sp0,UINT *s0vect,int col,NODE rp0);
1.8 noro 326: NODE nd_f4_red_main(int m,ND_pairs sp0,int nsp,UINT *s0vect,int col,
327: NM_ind_pair *rvect,int *rhead,IndArray *imat,int nred);
1.10 ! noro 328: NODE nd_f4_red_z_main(ND_pairs sp0,int nsp,UINT *s0vect,int col,
1.8 noro 329: NM_ind_pair *rvect,int *rhead,IndArray *imat,int nred);
1.1 noro 330:
331: /* NDV functions */
332: ND weyl_ndv_mul_nm(int mod,NM m0,NDV p);
333: void weyl_mul_nm_nmv(int n,int mod,NM m0,NMV m1,NM *tab,int tlen);
334: void ndv_mul_c(int mod,NDV p,int mul);
1.10 ! noro 335: void ndv_mul_c_z(NDV p,Z mul);
1.1 noro 336: ND ndv_mul_nm_symbolic(NM m0,NDV p);
337: ND ndv_mul_nm(int mod,NM m0,NDV p);
1.5 noro 338: ND ndv_mul_nmv_trunc(int mod,NMV m0,NDV p,UINT *d);
1.1 noro 339: void ndv_realloc(NDV p,int obpe,int oadv,EPOS oepos);
340: NDV ndv_dup_realloc(NDV p,int obpe,int oadv,EPOS oepos);
341: void ndv_homogenize(NDV p,int obpe,int oadv,EPOS eops);
342: void ndv_dehomogenize(NDV p,struct order_spec *spec);
343: void ndv_removecont(int mod,NDV p);
344: void ndv_print(NDV p);
1.10 ! noro 345: void ndv_print_z(NDV p);
1.1 noro 346: void ndv_free(NDV p);
347: void ndv_save(NDV p,int index);
348: NDV ndv_load(int index);
349:
350: /* converters */
351: ND ptond(VL vl,VL dvl,P p);
352: NDV ptondv(VL vl,VL dvl,P p);
353: P ndvtop(int mod,VL vl,VL dvl,NDV p);
354: NDV ndtondv(int mod,ND p);
355: ND ndvtond(int mod,NDV p);
356: int nm_ind_pair_to_vect(int m,UINT *s0,int n,NM_ind_pair pair,UINT *r);
357: IndArray nm_ind_pair_to_vect_compress(int m,UINT *s0,int n,NM_ind_pair pair);
358: int nd_to_vect(int mod,UINT *s0,int n,ND d,UINT *r);
1.10 ! noro 359: int nd_to_vect_z(UINT *s0,int n,ND d,Z *r);
! 360: NDV vect_to_ndv_z(Z *vect,int spcol,int col,int *rhead,UINT *s0vect);
1.1 noro 361:
362: /* elimination */
363: int nd_gauss_elim_mod(int **mat0,int *sugar,int row,int col,int md,int *colstat);
364: int nd_gauss_elim_sf(int **mat0,int *sugar,int row,int col,int md,int *colstat);
1.10 ! noro 365: int nd_gauss_elim_z(Z **mat0,int *sugar,int row,int col,int *colstat);
1.1 noro 366:
367: int ndl_ww_lex_compare(UINT *a1,UINT *a2);
1.8 noro 368:
1.1 noro 369:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to nd.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib2 / asir2000 / engine