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