Return to nd.h CVS log

Up to [local] / OpenXM_contrib2 / asir2018 / engine

Annotation of OpenXM_contrib2/asir2018/engine/nd.h, Revision 1.9

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