My Project
Loading...
Searching...
No Matches
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"
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)
16number nlRInit (long i);
17
18#include "reporter/si_signals.h"
20#include "kernel/ideals.h"
21#include "Singular/cntrlc.h"
22#include <sys/types.h>
23#include <sys/wait.h>
24#include <unistd.h>
26
27// send a number via a string s
28static char *send_number(char *s, number n)
29{
30 long *d=(long*)s;
31 if (SR_HDL(n) & SR_INT)
32 {
33 *d=(long)n;
34 s+=SIZEOF_LONG;
35 }
36 else
37 {
38 *d=n->s*2;/* n->s in 0..3: 0..6, use +8 for neg. numbers */
39 s+=SIZEOF_LONG;
40 if (mpz_isNeg(n->z)) { *d+=8; mpz_neg(n->z,n->z); }
41 size_t l;
42 d=(long*)s;
43 s+=SIZEOF_LONG;
44 mpz_export(s,&l,-1,sizeof(mp_limb_t),0,0,n->z);
45 *d=l;
46 s+=l*sizeof(mp_limb_t);
47 if (n->s!=3)
48 {
49 d=(long*)s;
50 s+=SIZEOF_LONG;
51 mpz_export(s,&l,-1,sizeof(mp_limb_t),0,0,n->n);
52 *d=l;
53 s+=l*sizeof(mp_limb_t);
54 }
55 }
56 return s;
57}
58
59static char * get_number(char *s, number *n)
60{
61 // format: last bit 1: imm. number (long)
62 // otherwise: 0,2: size(long) mpz, size(long) mpz
63 // 6: size(long) mpz
64 // 8,10: size(long) -mpz, size(long) mpz
65 // 14: size(long) -mpz
66 long *d=(long*)s;
67 s+=SIZEOF_LONG;
68 if (((*d)&1)==1) // immediate number
69 {
70 *n=(number)(*d);
71 }
72 else
73 {
74 *n=nlRInit(0);
75 BOOLEAN neg=(*d>=8);
76 if (neg) *d-=8;
77 (*n)->s=(*d)/2;
78 d=(long*)s;
79 s+=SIZEOF_LONG;
80 size_t l=*d;
81 mpz_realloc2((*n)->z,l*sizeof(mp_limb_t)*8);
82 mpz_import((*n)->z,l,-1,sizeof(mp_limb_t),0,0,s);
83 if (neg) mpz_neg((*n)->z,(*n)->z);
84 s+=l*sizeof(mp_limb_t);
85 if ((*n)->s!=3)
86 {
87 d=(long*)s;
88 s+=SIZEOF_LONG;
89 l=*d;
90 mpz_init2((*n)->n,l*sizeof(mp_limb_t)*8);
91 mpz_import((*n)->n,l,-1,sizeof(mp_limb_t),0,0,s);
92 s+=l*sizeof(mp_limb_t);
93 }
94 }
95 return s;
96}
97
98static long size_number(number n)
99{
100 long ll=SIZEOF_LONG;
101 if (SR_HDL(n) & SR_INT)
102 {
103 return SIZEOF_LONG;
104 }
105 else
106 {
107 if (n->s==3)
108 {
109 ll+=SIZEOF_LONG*2; /* n->s, mpz size */
110 long l=mpz_size1(n->z);
111 ll+=l*sizeof(mp_limb_t);
112 }
113 else
114 {
115 ll+=SIZEOF_LONG*3; /* n->s, mpz size(n->z) mpz size(n->n)*/
116 size_t l=mpz_size1(n->z);
117 ll+=l*sizeof(mp_limb_t);
118 l=mpz_size1(n->n);
119 ll+=l*sizeof(mp_limb_t);
120 }
121 }
122 return ll;
123}
124
125static char* send_mon(char *s, poly m, const ring r)
126{
127 // format: number exp[0..r->ExpL_Size]
129 memcpy(s,m->exp,r->ExpL_Size*sizeof(long));
130 s+=r->ExpL_Size*sizeof(long);
131 return s;
132}
133
134static char* get_mon(char *s, poly *m, const ring r)
135{
136 (*m)=p_Init(r);
137 s=get_number(s,&p_GetCoeff(*m,r));
138 memcpy((*m)->exp,s,r->ExpL_Size*sizeof(long));
139 s+=r->ExpL_Size*sizeof(long);
140 return s;
141}
142
143static long size_mon(poly m, const ring r)
144{
145 long ll=size_number(p_GetCoeff(m,r));
146 ll+=r->ExpL_Size*sizeof(long);
147 return ll;
148}
149
150static char* send_poly(char *s, int ind, poly p, const ring r)
151{
152 // format: index(long) length(long) mon...
153 //p_Write(p,r);PrintLn();
154 long *d=(long*)s;
155 *d=ind;
156 s+=SIZEOF_LONG;
157 long l=pLength(p);
158 d=(long*)s;
159 *d=l;
160 s+=SIZEOF_LONG;
161 while(p!=NULL)
162 {
163 s=send_mon(s,p,r);
164 pIter(p);
165 }
166 return s;
167}
168
169static char* get_poly(char *s,int &ind, poly *p,const ring r)
170{
171 long *d=(long*)s;
172 ind=*d;
173 s+=SIZEOF_LONG;
174 d=(long*)s;
175 long l=*d;
176 s+=SIZEOF_LONG;
177 for(long i=0;i<l;i++)
178 {
179 poly m;
180 s=get_mon(s,&m,r);
181 pNext(m)=*p;
182 *p=m;
183 }
184 *p=pReverse(*p);
185 return s;
186}
187
188static long size_poly(poly p, const ring r)
189{
190 long l=SIZEOF_LONG*2;
191 while(p!=NULL)
192 {
193 l+=size_mon(p,r);
194 pIter(p);
195 }
196 return l;
197}
198
199ideal id_ChineseRemainder_0(ideal *xx, number *q, int rl, const ring r)
200{
201 int cnt=0;int rw=0; int cl=0;
202 // find max. size of xx[.]:
203 for(int j=rl-1;j>=0;j--)
204 {
205 int i=IDELEMS(xx[j])*xx[j]->nrows;
206 if (i>cnt) cnt=i;
207 if (xx[j]->nrows >rw) rw=xx[j]->nrows; // for lifting matrices
208 if (xx[j]->ncols >cl) cl=xx[j]->ncols; // for lifting matrices
209 }
210 if (rw*cl !=cnt)
211 {
212 WerrorS("format mismatch in CRT");
213 return NULL;
214 }
215 int cpus=(int)(long)feOptValue(FE_OPT_CPUS);
218 /* start no more than MAX_PROCESS-1 children */
219 cpus=si_min(cpus,cnt/5);
220 if (cpus<=1)
221 /* at least 5 polys for each process, or switch to seriell version */
222 return id_ChineseRemainder(xx,q,rl,r);
223 ideal result=idInit(cnt,xx[0]->rank);
224 result->nrows=rw; // for lifting matrices
225 result->ncols=cl; // for lifting matrices
226 int parent_pid=getpid();
227 using namespace vspace;
228 vmem_init();
229 // Create a queue of int
230 VRef<Queue<int> > queue = vnew<Queue<int> >();
231 for(int i=cnt-1;i>=0; i--)
232 {
233 queue->enqueue(i); // the tasks: construct poly p[i]
234 }
235 for(int i=cpus;i>=0;i--)
236 {
237 queue->enqueue(-1); // stop sign, one for each child
238 }
239 // Create a queue of polys
241 int *pids=(int*)omAlloc0(cpus*sizeof(int));
242 for (int i=0;i<cpus;i++)
243 {
244 int pid = fork_process();
245 if (pid==0) break; //child
246 pids[i]=pid;
247 }
248 if (parent_pid!=getpid()) // child ------------------------------------------
249 {
252 feSetOptValue(FE_OPT_CPUS,0);
253 number *x=(number *)omAlloc(rl*sizeof(number));
254 poly *p=(poly *)omAlloc(rl*sizeof(poly));
255 CFArray inv_cache(rl);
258 loop
259 {
260 int ind=queue->dequeue();
261 if (ind== -1)
262 {
263 _exit(0);
264 }
265
266 for(int j=rl-1;j>=0;j--)
267 {
268 if(ind>=IDELEMS(xx[j])*xx[j]->nrows) // out of range of this ideal
269 p[j]=NULL;
270 else
271 p[j]=xx[j]->m[ind];
272 }
273 poly res=p_ChineseRemainder(p,x,q,rl,inv_cache,r);
274 long l=size_poly(res,r);
275 //printf("size: %ld kB\n",(l+1023)/1024);
276 VRef<VString> msg = vstring(l+1);
277 char *s=(char*)msg->str();
278 send_poly(s,ind,res,r);
279 rqueue->enqueue(msg);
280 if (TEST_OPT_PROT) printf(".");
281 }
282 }
283 else // parent ---------------------------------------------------
284 {
285 if (TEST_OPT_PROT) printf("%d children created\n",cpus);
286 VRef<VString> msg;
287 while(cnt>0)
288 {
289 msg=rqueue->dequeue();
290 char *s=(char*)msg->str();
291 int ind;
292 poly p=NULL;
293 get_poly(s,ind,&p,r);
294 //printf("got res[%d]\n",ind);
295 result->m[ind]=p;
296 msg.free();
297 cnt--;
298 }
299 int i=cpus-1;
300 int done=0;
301 while(done!=cpus)
302 {
303 BOOLEAN all_done=TRUE;
304 if (pids[i]>0)
305 {
306 int p=si_waitpid(pids[i],NULL,WNOHANG);
307 if (p>0)
308 {
309 pids[i]=0;
310 done++;
311 }
312 }
313 if (i==0) i=cpus;
314 i--;
315 }
316 omFreeSize(pids,cpus*sizeof(int));
317 // removes queues
318 queue.free();
319 rqueue.free();
320 vmem_deinit();
321 }
322 return result;
323}
324
325ideal id_Farey_0(ideal x, number N, const ring r)
326{
327 int cnt=IDELEMS(x)*x->nrows;
328 int cpus=(int)(long)feOptValue(FE_OPT_CPUS);
331 /* start no more than MAX_PROCESS-1 children */
332 cpus=si_min(cpus,cnt/5);
333 if (cpus<=1) /* at least 5 polys for each process,
334 or switch to seriell version */
335 return id_Farey(x,N,r);
336 ideal result=idInit(cnt,x->rank);
337 result->nrows=x->nrows; // for lifting matrices
338 result->ncols=x->ncols; // for lifting matrices
339
340 int parent_pid=getpid();
341 using namespace vspace;
342 vmem_init();
343 // Create a queue of int
344 VRef<Queue<int> > queue = vnew<Queue<int> >();
345 for(int i=cnt-1;i>=0; i--)
346 {
347 queue->enqueue(i); // the tasks: construct poly p[i]
348 }
349 for(int i=cpus;i>=0;i--)
350 {
351 queue->enqueue(-1); // stop sign, one for each child
352 }
353 // Create a queue of polys
355 int *pids=(int*)omAlloc0(cpus*sizeof(int));
356 for (int i=0;i<cpus;i++)
357 {
358 int pid = fork_process();
359 if (pid==0) break; //child
360 pids[i]=pid;
361 }
362 if (parent_pid!=getpid()) // child ------------------------------------------
363 {
366 feSetOptValue(FE_OPT_CPUS,0);
367 loop
368 {
369 int ind=queue->dequeue();
370 if (ind== -1)
371 {
372 _exit(0);
373 }
374
375 poly res=p_Farey(x->m[ind],N,r);
376 long l=size_poly(res,r);
377 VRef<VString> msg = vstring(l+1);
378 char *s=(char*)msg->str();
379 send_poly(s,ind,res,r);
380 rqueue->enqueue(msg);
381 if (TEST_OPT_PROT) printf(".");
382 }
383 }
384 else // parent ---------------------------------------------------
385 {
386 if (TEST_OPT_PROT) printf("%d children created\n",cpus);
387 VRef<VString> msg;
388 while(cnt>0)
389 {
390 msg=rqueue->dequeue();
391 char *s=(char*)msg->str();
392 int ind;
393 poly p=NULL;
394 get_poly(s,ind,&p,r);
395 //printf("got res[%d]\n",ind);
396 result->m[ind]=p;
397 msg.free();
398 cnt--;
399 }
400 int i=cpus-1;
401 int done=0;
402 while(done!=cpus)
403 {
404 BOOLEAN all_done=TRUE;
405 if (pids[i]>0)
406 {
407 int p=si_waitpid(pids[i],NULL,WNOHANG);
408 if (p>0)
409 {
410 pids[i]=0;
411 done++;
412 }
413 }
414 if (i==0) i=cpus;
415 i--;
416 }
417 omFreeSize(pids,cpus*sizeof(int));
418 // removes queues
419 queue.free();
420 rqueue.free();
421 vmem_deinit();
422 }
423 return result;
424}
425
426#if 0
427// debug for send_poly
428void test_n(poly n)
429{
430 p_Write(n,currRing);
431 char *buf=(char*)omAlloc0(2048*1000);
432 int ll=size_poly(n,currRing);
433 printf("size: %d\n",ll);
434 char *s=send_poly(buf,12345,n,currRing);
435 printf("send len: %d\n",(int)(s-buf));
436 long *d=(long*)buf;
437 for(int i=0;i<=ll/SIZEOF_LONG;i++) printf("%ld ",d[i]);
438 printf("\n");
439 n=NULL;
440 s=get_poly(buf,ll,&n,currRing);
441 printf("read len: %d\n",(int)(s-buf));
442 Print(":index: %d\n",ll);
443 p_Write(n,currRing);
444 PrintLn();
445 omFree(buf);
446}
447#endif
448#endif
All the auxiliary stuff.
int BOOLEAN
Definition auxiliary.h:88
#define TRUE
Definition auxiliary.h:101
static int si_min(const int a, const int b)
Definition auxiliary.h:126
Array< CanonicalForm > CFArray
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:4090
int p
Definition cfModGcd.cc:4086
cl
Definition cfModGcd.cc:4108
int int ncols
Definition cf_linsys.cc:32
int nrows
Definition cf_linsys.cc:32
si_hdl_typ si_set_signal(int sig, si_hdl_typ signal_handler)
meta function for binding a signal to an handler
Definition cntrlc.cc:121
void sig_term_hdl_child(int)
Definition cntrlc.cc:86
#define Print
Definition emacs.cc:80
return result
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
const char * feSetOptValue(feOptIndex opt, char *optarg)
Definition feOpt.cc:154
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:3074
static char * get_poly(char *s, int &ind, poly *p, const ring r)
Definition kChinese.cc:169
#define mpz_isNeg(A)
Definition kChinese.cc:15
static char * get_mon(char *s, poly *m, const ring r)
Definition kChinese.cc:134
static long size_poly(poly p, const ring r)
Definition kChinese.cc:188
ideal id_Farey_0(ideal x, number N, const ring r)
Definition kChinese.cc:325
static long size_number(number n)
Definition kChinese.cc:98
static char * send_poly(char *s, int ind, poly p, const ring r)
Definition kChinese.cc:150
static char * send_number(char *s, number n)
Definition kChinese.cc:28
number nlRInit(long i)
Definition longrat.cc:2522
static char * send_mon(char *s, poly m, const ring r)
Definition kChinese.cc:125
ideal id_ChineseRemainder_0(ideal *xx, number *q, int rl, const ring r)
Definition kChinese.cc:199
static char * get_number(char *s, number *n)
Definition kChinese.cc:59
static long size_mon(poly m, const ring r)
Definition kChinese.cc:143
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:3086
#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
VRef< T > vnew()
Definition vspace.h:1872
pid_t fork_process()
Definition vspace.cc:1081
static void vmem_deinit()
Definition vspace.h:1742
static Status vmem_init()
Definition vspace.h:1738
static VRef< VString > vstring(const char *s)
Definition vspace.h:2101
#define omFreeSize(addr, size)
#define omAlloc(size)
#define omFree(addr)
#define omAlloc0(size)
#define NULL
Definition omList.c:12
#define TEST_OPT_PROT
Definition options.h:105
poly p_Farey(poly p, number N, const ring r)
Definition p_polys.cc:54
static int pLength(poly a)
Definition p_polys.h:190
void p_Write(poly p, ring lmRing, ring tailRing)
Definition polys0.cc:342
static poly pReverse(poly p)
Definition p_polys.h:337
static poly p_Init(const ring r, omBin bin)
Definition p_polys.h:1336
VAR ring currRing
Widely used global variable which specifies the current polynomial ring for Singular interpreter and ...
Definition polys.cc:13
Compatibility 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:69
ideal idInit(int idsize, int rank)
initialise an ideal / module
ideal id_ChineseRemainder(ideal *xx, number *q, int rl, const ring r)
#define IDELEMS(i)
#define loop
Definition structs.h:71
void free()
Definition vspace.h:1805
#define SR_HDL(A)
Definition tgb.cc:35