My Project
kChinese.cc
Go to the documentation of this file.
1 #include "misc/auxiliary.h"
2 
3 #include "misc/intvec.h"
4 #include "misc/options.h"
6 #include "polys/matpol.h"
7 #include "polys/simpleideals.h"
8 #include "coeffs/longrat.h"
9 #include "Singular/feOpt.h"
10 #include "kernel/polys.h"
11 #include "kernel/mod2.h"
12 
13 #ifdef HAVE_VSPACE
14 
15 #define mpz_isNeg(A) ((A)->_mp_size<0)
16 number nlRInit (long i);
17 
19 #include "kernel/ideals.h"
20 #include <sys/types.h>
21 #include <sys/wait.h>
22 #include <unistd.h>
23 
24 // send a number via a string s
25 static char *send_number(char *s, number n)
26 {
27  long *d=(long*)s;
28  if (SR_HDL(n) & SR_INT)
29  {
30  *d=(long)n;
31  s+=SIZEOF_LONG;
32  }
33  else
34  {
35  *d=n->s*2;/* n->s in 0..3: 0..6, use +8 for neg. numbers */
36  s+=SIZEOF_LONG;
37  if (mpz_isNeg(n->z)) { *d+=8; mpz_neg(n->z,n->z); }
38  size_t l;
39  d=(long*)s;
40  s+=SIZEOF_LONG;
41  mpz_export(s,&l,-1,sizeof(mp_limb_t),0,0,n->z);
42  *d=l;
43  s+=l*sizeof(mp_limb_t);
44  if (n->s!=3)
45  {
46  d=(long*)s;
47  s+=SIZEOF_LONG;
48  mpz_export(s,&l,-1,sizeof(mp_limb_t),0,0,n->n);
49  *d=l;
50  s+=l*sizeof(mp_limb_t);
51  }
52  }
53  return s;
54 }
55 
56 static char * get_number(char *s, number *n)
57 {
58  // format: last bit 1: imm. number (long)
59  // otherwise: 0,2: size(long) mpz, size(long) mpz
60  // 6: size(long) mpz
61  // 8,10: size(long) -mpz, size(long) mpz
62  // 14: size(long) -mpz
63  long *d=(long*)s;
64  s+=SIZEOF_LONG;
65  if (((*d)&1)==1) // immidiate number
66  {
67  *n=(number)(*d);
68  }
69  else
70  {
71  *n=nlRInit(0);
72  BOOLEAN neg=(*d>=8);
73  if (neg) *d-=8;
74  (*n)->s=(*d)/2;
75  d=(long*)s;
76  s+=SIZEOF_LONG;
77  size_t l=*d;
78  mpz_realloc2((*n)->z,l*sizeof(mp_limb_t)*8);
79  mpz_import((*n)->z,l,-1,sizeof(mp_limb_t),0,0,s);
80  if (neg) mpz_neg((*n)->z,(*n)->z);
81  s+=l*sizeof(mp_limb_t);
82  if ((*n)->s!=3)
83  {
84  d=(long*)s;
85  s+=SIZEOF_LONG;
86  l=*d;
87  mpz_init2((*n)->n,l*sizeof(mp_limb_t)*8);
88  mpz_import((*n)->n,l,-1,sizeof(mp_limb_t),0,0,s);
89  s+=l*sizeof(mp_limb_t);
90  }
91  }
92  return s;
93 }
94 
95 static long size_number(number n)
96 {
97  long ll=SIZEOF_LONG;
98  if (SR_HDL(n) & SR_INT)
99  {
100  return SIZEOF_LONG;
101  }
102  else
103  {
104  if (n->s==3)
105  {
106  ll+=SIZEOF_LONG*2; /* n->s, mpz size */
107  long l=mpz_size1(n->z);
108  ll+=l*sizeof(mp_limb_t);
109  }
110  else
111  {
112  ll+=SIZEOF_LONG*3; /* n->s, mpz size(n->z) mpz size(n->n)*/
113  size_t l=mpz_size1(n->z);
114  ll+=l*sizeof(mp_limb_t);
115  l=mpz_size1(n->n);
116  ll+=l*sizeof(mp_limb_t);
117  }
118  }
119  return ll;
120 }
121 
122 static char* send_mon(char *s, poly m, const ring r)
123 {
124  // format: number exp[0..r->ExpL_Size]
125  s=send_number(s,p_GetCoeff(m,r));
126  memcpy(s,m->exp,r->ExpL_Size*sizeof(long));
127  s+=r->ExpL_Size*sizeof(long);
128  return s;
129 }
130 
131 static char* get_mon(char *s, poly *m, const ring r)
132 {
133  (*m)=p_Init(r);
134  s=get_number(s,&p_GetCoeff(*m,r));
135  memcpy((*m)->exp,s,r->ExpL_Size*sizeof(long));
136  s+=r->ExpL_Size*sizeof(long);
137  return s;
138 }
139 
140 static long size_mon(poly m, const ring r)
141 {
142  long ll=size_number(p_GetCoeff(m,r));
143  ll+=r->ExpL_Size*sizeof(long);
144  return ll;
145 }
146 
147 static char* send_poly(char *s, int ind, poly p, const ring r)
148 {
149  // format: index(long) length(long) mon...
150  //p_Write(p,r);PrintLn();
151  long *d=(long*)s;
152  *d=ind;
153  s+=SIZEOF_LONG;
154  long l=pLength(p);
155  d=(long*)s;
156  *d=l;
157  s+=SIZEOF_LONG;
158  while(p!=NULL)
159  {
160  s=send_mon(s,p,r);
161  pIter(p);
162  }
163  return s;
164 }
165 
166 static char* get_poly(char *s,int &ind, poly *p,const ring r)
167 {
168  long *d=(long*)s;
169  ind=*d;
170  s+=SIZEOF_LONG;
171  d=(long*)s;
172  long l=*d;
173  s+=SIZEOF_LONG;
174  for(long i=0;i<l;i++)
175  {
176  poly m;
177  s=get_mon(s,&m,r);
178  pNext(m)=*p;
179  *p=m;
180  }
181  *p=pReverse(*p);
182  return s;
183 }
184 
185 static long size_poly(poly p, const ring r)
186 {
187  long l=SIZEOF_LONG*2;
188  while(p!=NULL)
189  {
190  l+=size_mon(p,r);
191  pIter(p);
192  }
193  return l;
194 }
195 
196 ideal id_ChineseRemainder_0(ideal *xx, number *q, int rl, const ring r)
197 {
198  int cnt=0;int rw=0; int cl=0;
199  // find max. size of xx[.]:
200  for(int j=rl-1;j>=0;j--)
201  {
202  int i=IDELEMS(xx[j])*xx[j]->nrows;
203  if (i>cnt) cnt=i;
204  if (xx[j]->nrows >rw) rw=xx[j]->nrows; // for lifting matrices
205  if (xx[j]->ncols >cl) cl=xx[j]->ncols; // for lifting matrices
206  }
207  if (rw*cl !=cnt)
208  {
209  WerrorS("format mismatch in CRT");
210  return NULL;
211  }
212  int cpus=(int)(long)feOptValue(FE_OPT_CPUS);
215  /* start no more than MAX_PROCESS-1 children */
216  if ((cpus==1) || (2*cpus>=cnt))
217  /* at least 2 polys for each process, or switch to seriell version */
218  return id_ChineseRemainder(xx,q,rl,r);
219  ideal result=idInit(cnt,xx[0]->rank);
220  result->nrows=rw; // for lifting matrices
221  result->ncols=cl; // for lifting matrices
222  int parent_pid=getpid();
223  using namespace vspace;
224  vmem_init();
225  // Create a queue of int
226  VRef<Queue<int> > queue = vnew<Queue<int> >();
227  for(int i=cnt-1;i>=0; i--)
228  {
229  queue->enqueue(i); // the tasks: construct poly p[i]
230  }
231  for(int i=cpus;i>=0;i--)
232  {
233  queue->enqueue(-1); // stop sign, one for each child
234  }
235  // Create a queue of polys
236  VRef<Queue<VRef<VString> > > rqueue = vnew<Queue<VRef<VString> > >();
237  for (int i=0;i<cpus;i++)
238  {
239  int pid = fork_process();
240  if (pid==0) break; //child
241  }
242  if (parent_pid!=getpid()) // child ------------------------------------------
243  {
244  number *x=(number *)omAlloc(rl*sizeof(number));
245  poly *p=(poly *)omAlloc(rl*sizeof(poly));
246  CFArray inv_cache(rl);
248  n_SwitchChinRem=1;
249  loop
250  {
251  int ind=queue->dequeue();
252  if (ind== -1)
253  {
254  exit(0);
255  }
256 
257  for(int j=rl-1;j>=0;j--)
258  {
259  if(ind>=IDELEMS(xx[j])*xx[j]->nrows) // out of range of this ideal
260  p[j]=NULL;
261  else
262  p[j]=xx[j]->m[ind];
263  }
264  poly res=p_ChineseRemainder(p,x,q,rl,inv_cache,r);
265  long l=size_poly(res,r);
266  //printf("size: %ld kB\n",(l+1023)/1024);
267  VRef<VString> msg = vstring(l+1);
268  char *s=(char*)msg->str();
269  send_poly(s,ind,res,r);
270  rqueue->enqueue(msg);
271  if (TEST_OPT_PROT) printf(".");
272  }
273  }
274  else // parent ---------------------------------------------------
275  {
276  if (TEST_OPT_PROT) printf("%d children created\n",cpus);
277  VRef<VString> msg;
278  while(cnt>0)
279  {
280  msg=rqueue->dequeue();
281  char *s=(char*)msg->str();
282  int ind;
283  poly p=NULL;
284  get_poly(s,ind,&p,r);
285  //printf("got res[%d]\n",ind);
286  result->m[ind]=p;
287  msg.free();
288  cnt--;
289  }
290  // removes queues
291  queue.free();
292  rqueue.free();
293  vmem_deinit();
294  }
295  return result;
296 }
297 
298 ideal id_Farey_0(ideal x, number N, const ring r)
299 {
300  int cnt=IDELEMS(x)*x->nrows;
301  int cpus=(int)(long)feOptValue(FE_OPT_CPUS);
304  /* start no more than MAX_PROCESS-1 children */
305  if (2*cpus>=cnt) /* at least 2 polys for each process,
306  or switch to seriell version */
307  return id_Farey(x,N,r);
308  ideal result=idInit(cnt,x->rank);
309  result->nrows=x->nrows; // for lifting matrices
310  result->ncols=x->ncols; // for lifting matrices
311 
312  int parent_pid=getpid();
313  using namespace vspace;
314  vmem_init();
315  // Create a queue of int
316  VRef<Queue<int> > queue = vnew<Queue<int> >();
317  for(int i=cnt-1;i>=0; i--)
318  {
319  queue->enqueue(i); // the tasks: construct poly p[i]
320  }
321  for(int i=cpus;i>=0;i--)
322  {
323  queue->enqueue(-1); // stop sign, one for each child
324  }
325  // Create a queue of polys
326  VRef<Queue<VRef<VString> > > rqueue = vnew<Queue<VRef<VString> > >();
327  for (int i=0;i<cpus;i++)
328  {
329  int pid = fork_process();
330  if (pid==0) break; //child
331  }
332  if (parent_pid!=getpid()) // child ------------------------------------------
333  {
334  loop
335  {
336  int ind=queue->dequeue();
337  if (ind== -1)
338  {
339  exit(0);
340  }
341 
342  poly res=p_Farey(x->m[ind],N,r);
343  long l=size_poly(res,r);
344  VRef<VString> msg = vstring(l+1);
345  char *s=(char*)msg->str();
346  send_poly(s,ind,res,r);
347  rqueue->enqueue(msg);
348  if (TEST_OPT_PROT) printf(".");
349  }
350  }
351  else // parent ---------------------------------------------------
352  {
353  if (TEST_OPT_PROT) printf("%d children created\n",cpus);
354  VRef<VString> msg;
355  while(cnt>0)
356  {
357  msg=rqueue->dequeue();
358  char *s=(char*)msg->str();
359  int ind;
360  poly p=NULL;
361  get_poly(s,ind,&p,r);
362  //printf("got res[%d]\n",ind);
363  result->m[ind]=p;
364  msg.free();
365  cnt--;
366  }
367  // wait for the children to finish
368  sleep(1);
369  // removes queues
370  queue.free();
371  rqueue.free();
372  vmem_deinit();
373  }
374  return result;
375 }
376 
377 void test_n(poly n)
378 {
379  p_Write(n,currRing);
380  char *buf=(char*)omAlloc0(2048*1000);
381  int ll=size_poly(n,currRing);
382  printf("size: %d\n",ll);
383  char *s=send_poly(buf,12345,n,currRing);
384  printf("send len: %d\n",(int)(s-buf));
385  long *d=(long*)buf;
386  for(int i=0;i<=ll/SIZEOF_LONG;i++) printf("%ld ",d[i]);
387  printf("\n");
388  n=NULL;
389  s=get_poly(buf,ll,&n,currRing);
390  printf("read len: %d\n",(int)(s-buf));
391  Print(":index: %d\n",ll);
392  p_Write(n,currRing);
393  PrintLn();
394  omFree(buf);
395 }
396 #endif
All the auxiliary stuff.
int BOOLEAN
Definition: auxiliary.h:87
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:56
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
Variable x
Definition: cfModGcd.cc:4082
int p
Definition: cfModGcd.cc:4078
cl
Definition: cfModGcd.cc:4100
int int ncols
Definition: cf_linsys.cc:32
int nrows
Definition: cf_linsys.cc:32
#define Print
Definition: emacs.cc:80
return result
Definition: facAbsBiFact.cc:75
const CanonicalForm int s
Definition: facAbsFact.cc:51
CanonicalForm res
Definition: facAbsFact.cc:60
int j
Definition: facHensel.cc:110
void WerrorS(const char *s)
Definition: feFopen.cc:24
static void * feOptValue(feOptIndex opt)
Definition: feOpt.h:40
#define EXTERN_VAR
Definition: globaldefs.h:6
ideal id_Farey(ideal x, number N, const ring r)
Definition: ideals.cc:2848
static char * get_number(char *s, number *n)
Definition: kChinese.cc:56
#define mpz_isNeg(A)
Definition: kChinese.cc:15
static char * get_poly(char *s, int &ind, poly *p, const ring r)
Definition: kChinese.cc:166
static long size_poly(poly p, const ring r)
Definition: kChinese.cc:185
static char * send_poly(char *s, int ind, poly p, const ring r)
Definition: kChinese.cc:147
ideal id_Farey_0(ideal x, number N, const ring r)
Definition: kChinese.cc:298
void test_n(poly n)
Definition: kChinese.cc:377
static long size_number(number n)
Definition: kChinese.cc:95
number nlRInit(long i)
Definition: longrat.cc:2530
static char * send_mon(char *s, poly m, const ring r)
Definition: kChinese.cc:122
ideal id_ChineseRemainder_0(ideal *xx, number *q, int rl, const ring r)
Definition: kChinese.cc:196
static char * send_number(char *s, number n)
Definition: kChinese.cc:25
static char * get_mon(char *s, poly *m, const ring r)
Definition: kChinese.cc:131
static long size_mon(poly m, const ring r)
Definition: kChinese.cc:140
poly p_ChineseRemainder(poly *xx, mpz_ptr *x, mpz_ptr *q, int rl, mpz_ptr *C, const ring R)
VAR int n_SwitchChinRem
Definition: longrat.cc:3094
#define SR_INT
Definition: longrat.h:67
#define pIter(p)
Definition: monomials.h:37
#define pNext(p)
Definition: monomials.h:36
#define p_GetCoeff(p, r)
Definition: monomials.h:50
static const int MAX_PROCESS
Definition: vspace.h:1419
pid_t fork_process()
Definition: vspace.cc:993
static void vmem_deinit()
Definition: vspace.h:1742
static VRef< VString > vstring(const char *s)
Definition: vspace.h:2101
static Status vmem_init()
Definition: vspace.h:1738
#define omAlloc(size)
Definition: omAllocDecl.h:210
#define omFree(addr)
Definition: omAllocDecl.h:261
#define omAlloc0(size)
Definition: omAllocDecl.h:211
#define NULL
Definition: omList.c:12
#define TEST_OPT_PROT
Definition: options.h:103
poly p_Farey(poly p, number N, const ring r)
Definition: p_polys.cc:54
void p_Write(poly p, ring lmRing, ring tailRing)
Definition: polys0.cc:342
static poly pReverse(poly p)
Definition: p_polys.h:337
static unsigned pLength(poly a)
Definition: p_polys.h:191
static poly p_Init(const ring r, omBin bin)
Definition: p_polys.h:1322
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition: polys.cc:13
Compatiblity layer for legacy polynomial operations (over currRing)
void PrintLn()
Definition: reporter.cc:310
#define mpz_size1(A)
Definition: si_gmp.h:17
int status int void * buf
Definition: si_signals.h:59
ideal idInit(int idsize, int rank)
initialise an ideal / module
Definition: simpleideals.cc:35
ideal id_ChineseRemainder(ideal *xx, number *q, int rl, const ring r)
#define IDELEMS(i)
Definition: simpleideals.h:23
#define loop
Definition: structs.h:75
void free()
Definition: vspace.h:1805
#define SR_HDL(A)
Definition: tgb.cc:35