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