Annotation of OpenXM_contrib2/asir2000/engine/nd.h, Revision 1.1
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;
! 48: Q z;
! 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)
! 134: #define HCQ(d) ((d)->body->c.z)
! 135: #define HCP(d) ((d)->body->c.p)
! 136: #define CM(a) ((a)->c.m)
! 137: #define CQ(a) ((a)->c.z)
! 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);
! 217: void removecont_array(Q *c,int n);
! 218:
! 219: /* GeoBucket functions */
! 220: ND normalize_pbucket(int mod,PGeoBucket g);
! 221: int head_pbucket(int mod,PGeoBucket g);
! 222: int head_pbucket_q(PGeoBucket g);
! 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);
! 226: void mulq_pbucket(PGeoBucket g,Q c);
! 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);
! 260: INLINE int ndl_equal(UINT *d1,UINT *d2);
! 261: INLINE void ndl_copy(UINT *d1,UINT *d2);
! 262: INLINE void ndl_zero(UINT *d);
! 263: INLINE void ndl_add(UINT *d1,UINT *d2,UINT *d);
! 264: INLINE void ndl_addto(UINT *d1,UINT *d2);
! 265: INLINE void ndl_sub(UINT *d1,UINT *d2,UINT *d);
! 266: INLINE int ndl_hash_value(UINT *d);
! 267:
! 268: /* normal forms */
! 269: INLINE int ndl_find_reducer(UINT *g);
! 270: int nd_sp(int mod,int trace,ND_pairs p,ND *nf);
! 271: int nd_nf(int mod,ND g,NDV *ps,int full,NDC dn,ND *nf);
! 272: int nd_nf_pbucket(int mod,ND g,NDV *ps,int full,ND *nf);
! 273:
! 274: /* finalizers */
! 275: NODE ndv_reducebase(NODE x);
! 276: NODE ndv_reduceall(int m,NODE f);
! 277:
! 278: /* allocators */
! 279: void nd_free_private_storage();
! 280: void _NM_alloc();
! 281: void _ND_alloc();
! 282: void nd_free(ND p);
! 283: void nd_free_redlist();
! 284:
! 285: /* printing */
! 286: void ndl_print(UINT *dl);
! 287: void nd_print(ND p);
! 288: void nd_print_q(ND p);
! 289: void ndp_print(ND_pairs d);
! 290:
! 291:
! 292: /* setup, reconstruct */
! 293: void nd_init_ord(struct order_spec *spec);
! 294: ND_pairs nd_reconstruct(int mod,int trace,ND_pairs ndp);
! 295: void ndv_setup(int mod,int trace,NODE f);
! 296: void nd_setup_parameters(int nvar,int max);
! 297: BlockMask nd_create_blockmask(struct order_spec *ord);
! 298: EPOS nd_create_epos(struct order_spec *ord);
! 299: int nd_get_exporigin(struct order_spec *ord);
! 300: void ndv_mod(int mod,NDV p);
! 301: NDV ndv_dup(int mod,NDV p);
! 302: ND nd_dup(ND p);
! 303:
! 304: /* ND functions */
! 305: int ndv_check_candidate(NODE input,int obpe,int oadv,EPOS oepos,NODE cand);
! 306: void nd_mul_c(int mod,ND p,int mul);
! 307: void nd_mul_c_q(ND p,Q mul);
! 308: void nd_mul_c_p(VL vl,ND p,P mul);
! 309: ND nd_remove_head(ND p);
! 310: ND nd_separate_head(ND p,ND *head);
! 311: int nd_length(ND p);
! 312: void nd_append_red(UINT *d,int i);
! 313: UINT *ndv_compute_bound(NDV p);
! 314: ND nd_copy(ND p);
! 315: ND nd_merge(ND p1,ND p2);
! 316: ND nd_add(int mod,ND p1,ND p2);
! 317: ND nd_add_q(ND p1,ND p2);
! 318: ND nd_add_sf(ND p1,ND p2);
! 319: INLINE int nd_length(ND p);
! 320: NODE nd_f4_red(int m,ND_pairs sp0,UINT *s0vect,int col,NODE rp0);
! 321: NODE nd_f4_red_dist(int m,ND_pairs sp0,UINT *s0vect,int col,NODE rp0);
! 322:
! 323: /* NDV functions */
! 324: ND weyl_ndv_mul_nm(int mod,NM m0,NDV p);
! 325: void weyl_mul_nm_nmv(int n,int mod,NM m0,NMV m1,NM *tab,int tlen);
! 326: void ndv_mul_c(int mod,NDV p,int mul);
! 327: void ndv_mul_c_q(NDV p,Q mul);
! 328: ND ndv_mul_nm_symbolic(NM m0,NDV p);
! 329: ND ndv_mul_nm(int mod,NM m0,NDV p);
! 330: void ndv_realloc(NDV p,int obpe,int oadv,EPOS oepos);
! 331: NDV ndv_dup_realloc(NDV p,int obpe,int oadv,EPOS oepos);
! 332: void ndv_homogenize(NDV p,int obpe,int oadv,EPOS eops);
! 333: void ndv_dehomogenize(NDV p,struct order_spec *spec);
! 334: void ndv_removecont(int mod,NDV p);
! 335: void ndv_print(NDV p);
! 336: void ndv_print_q(NDV p);
! 337: void ndv_free(NDV p);
! 338: void ndv_save(NDV p,int index);
! 339: NDV ndv_load(int index);
! 340:
! 341: /* converters */
! 342: ND ptond(VL vl,VL dvl,P p);
! 343: NDV ptondv(VL vl,VL dvl,P p);
! 344: P ndvtop(int mod,VL vl,VL dvl,NDV p);
! 345: NDV ndtondv(int mod,ND p);
! 346: ND ndvtond(int mod,NDV p);
! 347: int nm_ind_pair_to_vect(int m,UINT *s0,int n,NM_ind_pair pair,UINT *r);
! 348: IndArray nm_ind_pair_to_vect_compress(int m,UINT *s0,int n,NM_ind_pair pair);
! 349: int nd_to_vect(int mod,UINT *s0,int n,ND d,UINT *r);
! 350:
! 351: /* elimination */
! 352: int nd_gauss_elim_mod(int **mat0,int *sugar,int row,int col,int md,int *colstat);
! 353: int nd_gauss_elim_sf(int **mat0,int *sugar,int row,int col,int md,int *colstat);
! 354:
! 355: int ndl_ww_lex_compare(UINT *a1,UINT *a2);
! 356:
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