| blob | d7c559a2afa7ad89ebd41e107483064275e88fdd |
5 </head><body>
6 <!-- Generated by Doxygen 1.2.15 -->
7 <center>
8 <a class="qindex" href="main.html">Main Page</a> <a class="qindex" href="annotated.html">Compound List</a> <a class="qindex" href="files.html">File List</a> <a class="qindex" href="functions.html">Compound Members</a> <a class="qindex" href="globals.html">File Members</a> </center>
9 <hr><h1>Lattice.c</h1><a href="Lattice_8c.html">Go to the documentation of this file.</a><div class="fragment"><pre>00001 <font class="preprocessor">#include <stdlib.h></font>
11 00003
12 00004
13 <a name="l00005"></a><a class="code" href="structfactor.html">00005</a> <font class="keyword">typedef</font> <font class="keyword">struct </font>{
14 <a name="l00006"></a><a class="code" href="structfactor.html#m0">00006</a> <font class="keywordtype">int</font> count;
15 <a name="l00007"></a><a class="code" href="structfactor.html#m1">00007</a> <font class="keywordtype">int</font> *fac;
17 00009
18 00010 <font class="keyword">static</font> <a class="code" href="structfactor.html">factor</a> <a class="code" href="Lattice_8c.html#a0">allfactors</a> (<font class="keywordtype">int</font> num);
19 00011
23 <a name="l00015"></a><a class="code" href="Lattice_8c.html#a1">00015</a> <font class="keywordtype">void</font> <a class="code" href="Lattice_8c.html#a1">PrintLatticeUnion</a>(FILE *fp, <font class="keywordtype">char</font> *format, LatticeUnion *Head) {
24 00016
25 00017 LatticeUnion *temp;
26 00018
31 00023
35 <a name="l00027"></a><a class="code" href="Lattice_8c.html#a2">00027</a> <font class="keywordtype">void</font> <a class="code" href="Lattice_8c.html#a2">LatticeUnion_Free</a>(LatticeUnion *Head) {
36 00028
37 00029 LatticeUnion *temp;
38 00030
40 00032 temp = Head;
43 00035 free(temp);
44 00036 }
47 00039
51 <a name="l00043"></a><a class="code" href="Lattice_8c.html#a3">00043</a> LatticeUnion *<a class="code" href="Lattice_8c.html#a3">LatticeUnion_Alloc</a>(<font class="keywordtype">void</font>) {
52 00044
53 00045 LatticeUnion *temp;
54 00046
60 00052
62 00054 <font class="comment"> * Given two Lattices 'A' and 'B', return True if they have the same affine </font>
65 <a name="l00057"></a><a class="code" href="Lattice_8c.html#a4">00057</a> Bool <a class="code" href="Lattice_8c.html#a4">sameAffinepart</a> (Lattice *A, Lattice *B) {
66 00058
68 00060
71 00063 fp = fopen(<font class="stringliteral">"_debug"</font>,<font class="stringliteral">"a"</font>);
73 00065 fclose(fp);
77 00069 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a23">value_ne</a>(A->p[i][A->NbColumns-1],B->p[i][B->NbColumns-1]))
81 00073
83 00075 <font class="comment"> * Return an empty lattice of dimension 'dimension-1'. An empty lattice is </font>
86 <a name="l00078"></a><a class="code" href="Lattice_8c.html#a5">00078</a> Lattice *<a class="code" href="Lattice_8c.html#a5">EmptyLattice</a>(<font class="keywordtype">int</font> dimension) {
87 00079
88 00080 Lattice *result;
90 00082
93 00085 fp = fopen (<font class="stringliteral">"_debug"</font>, <font class="stringliteral">"a"</font>);
95 00087 fclose (fp);
98 00090 result = (Lattice *) <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(dimension, dimension);
102 00094 <a class="code" href="arithmetique_8h.html#a12">value_set_si</a>(result->p[i-1][i-1],1);
105 00097
107 00099 <font class="comment"> * Return True if Lattice 'A' is empty, otherwise return False. </font>
109 <a name="l00101"></a><a class="code" href="Lattice_8c.html#a6">00101</a> Bool <a class="code" href="Lattice_8c.html#a6">isEmptyLattice</a> (Lattice *A) {
110 00102
112 00104
115 00107 fp = fopen(<font class="stringliteral">"_debug"</font>, <font class="stringliteral">"a"</font>);
117 00109 fclose(fp);
122 00114 <font class="keywordflow">if</font>(<a class="code" href="arithmetique_8h.html#a68">value_notzero_p</a>(A->p[i][j])) {
124 00116 }
125 00117 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a69">value_one_p</a>(A->p[i][A->NbColumns-1])) {
127 00119 }
130 00122
132 00124 <font class="comment"> * Given a Lattice 'A', check whether it is linear or not, i.e. whether the </font>
133 00125 <font class="comment"> * affine part is NULL or not. If affine part is empty, it returns True other-</font>
136 <a name="l00128"></a><a class="code" href="Lattice_8c.html#a7">00128</a> Bool <a class="code" href="Lattice_8c.html#a7">isLinear</a>(Lattice *A) {
137 00129
139 00131
142 00134 fp = fopen (<font class="stringliteral">"_debug"</font>, <font class="stringliteral">"a"</font>);
144 00136 fclose (fp);
148 00140 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a68">value_notzero_p</a>(A->p[i][A->NbColumns-1])) {
150 00142 }
153 00145
155 00147 <font class="comment"> * Return the affine Hermite normal form of the affine lattice 'A'. The unique </font>
156 00148 <font class="comment"> * affine Hermite form if a lattice is stored in 'H' and the unimodular matrix </font>
167 <a name="l00159"></a><a class="code" href="Lattice_8c.html#a8">00159</a> <font class="keywordtype">void</font> <a class="code" href="Lattice_8c.html#a8">AffineHermite</a> (Lattice *A, Lattice **H, Matrix **U) {
168 00160
169 00161 Lattice *temp;
170 00162 Bool flag = True;
171 00163
174 00166 fp = fopen (<font class="stringliteral">"_debug"</font>, <font class="stringliteral">"a"</font>);
176 00168 fclose (fp);
179 00171 <font class="keywordflow">if</font> (<a class="code" href="Lattice_8c.html#a7">isLinear</a>(A) == False)
182 00174 flag = False ;
184 00176 }
185 00177 <a class="code" href="NormalForms_8c.html#a16">Hermite</a>((Matrix *)temp,(Matrix **) H, U);
195 00187 }
199 00191
201 00193 <font class="comment"> * Given a Polylib matrix 'A' that rerepresents an affine function, return the</font>
202 00194 <font class="comment"> * affine Smith normal form 'Delta' of 'A' and unimodular matrices 'U' and 'V'</font>
207 00199 <font class="comment"> * (3) The Smith Normal Form Delta must be Dehomogenised and also </font>
208 00200 <font class="comment"> * corresponding changes must be made to the Unimodular Matrices </font>
212 <a name="l00204"></a><a class="code" href="Lattice_8c.html#a9">00204</a> <font class="keywordtype">void</font> <a class="code" href="Lattice_8c.html#a9">AffineSmith</a>(Lattice *A, Lattice **U, Lattice **V, Lattice **Diag) {
213 00205
214 00206 Lattice *temp;
215 00207 Lattice *Uinv;
218 00210
221 00213 fp = fopen(<font class="stringliteral">"_debug"</font>, <font class="stringliteral">"a"</font>);
223 00215 fclose(fp);
226 00218 <a class="code" href="arithmetique_8h.html#a10">value_init</a>(sum); <a class="code" href="arithmetique_8h.html#a10">value_init</a>(tmp);
227 00219 <a class="code" href="arithmetique_8h.html#a10">value_init</a>(quo); <a class="code" href="arithmetique_8h.html#a10">value_init</a>(rem);
229 00221 <a class="code" href="NormalForms_8c.html#a15">Smith</a>((Matrix *)temp, (Matrix **)U, (Matrix **)V, (Matrix **)Diag);
231 00223
236 00228
239 00231 *V = (Lattice *) <a class="code" href="Matop_8c.html#a5">Matrix_Copy</a> ((Matrix *)temp);
241 00233
244 00236 *Diag = (Lattice *)<a class="code" href="Matop_8c.html#a5">Matrix_Copy</a> ((Matrix *)temp);
246 00238
247 00239 temp = (Lattice *) <a class="code" href="Matop_8c.html#a5">Matrix_Copy</a> ((Matrix *) *U);
248 00240 Uinv = (Lattice *) <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a> (U[0]->NbRows, U[0]->NbColumns);
249 00241 <a class="code" href="matrix_8c.html#a13">Matrix_Inverse</a>( (Matrix *) temp, (Matrix *) Uinv);
251 00243
255 00247 <a class="code" href="arithmetique_8h.html#a47">value_multiply</a>(tmp,Uinv->p[i][j],U[0]->p[j][U[0]->NbColumns-1]);
257 00249 }
258 00250 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(Diag[0]->p[i][j],sum);
259 00251 }
262 00254 <a class="code" href="arithmetique_8h.html#a12">value_set_si</a>(U[0]->p[i][U[0]->NbColumns-1],0);
264 00256 <a class="code" href="arithmetique_8h.html#a51">value_division</a>(quo,Diag[0]->p[i][Diag[0]->NbColumns-1],Diag[0]->p[i][i]);
265 00257 <a class="code" href="arithmetique_8h.html#a52">value_modulus</a>(rem,Diag[0]->p[i][Diag[0]->NbColumns-1],Diag[0]->p[i][i]);
266 00258
268 00260 <a class="code" href="arithmetique_8h.html#a16">value_print</a>(stdout,<a class="code" href="arithmetique_8h.html#a5">VALUE_FMT</a>,rem);
270 00262 <a class="code" href="arithmetique_8h.html#a16">value_print</a>(stdout,<a class="code" href="arithmetique_8h.html#a5">VALUE_FMT</a>,quo);
272 00264
273 00265 <font class="comment">/* Apparently the % operator is strange when sign are different */</font>
274 00266 <font class="keywordflow">if</font>(<a class="code" href="arithmetique_8h.html#a64">value_neg_p</a>(rem)) {
275 00267 <a class="code" href="arithmetique_8h.html#a43">value_addto</a>(rem,rem,Diag[0]->p[i][i]);
277 00269 };
279 00271 <a class="code" href="arithmetique_8h.html#a16">value_print</a>(stdout,<a class="code" href="arithmetique_8h.html#a5">VALUE_FMT</a>,rem);
281 00273 <a class="code" href="arithmetique_8h.html#a16">value_print</a>(stdout,<a class="code" href="arithmetique_8h.html#a5">VALUE_FMT</a>,quo);
283 00275 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>( Diag[0]->p[i][Diag[0]->NbColumns-1],rem);
284 00276 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(V[0]->p[i][V[0]->NbColumns-1],quo);
285 00277 }
286 00278 <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(sum); <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(tmp);
287 00279 <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(quo); <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(rem);
290 00282
292 00284 <font class="comment"> * Given a lattice 'A' and a boolean variable 'Forward', homogenise the lattice</font>
293 00285 <font class="comment"> * if 'Forward' is True, otherwise if 'Forward' is False, dehomogenise the </font>
304 <a name="l00296"></a><a class="code" href="Lattice_8c.html#a10">00296</a> Lattice *<a class="code" href="Lattice_8c.html#a10">Homogenise</a>(Lattice *A, Bool Forward) {
305 00297
306 00298 Lattice *result;
307 00299
310 00302 fp = fopen(<font class="stringliteral">"_debug"</font>,<font class="stringliteral">"a"</font>);
312 00304 fclose(fp);
317 00309 <a class="code" href="Matop_8c.html#a10">PutColumnFirst</a>((Matrix *)result, A->NbColumns-1);
318 00310 <a class="code" href="Matop_8c.html#a9">PutRowFirst</a>((Matrix *)result, result->NbRows-1);
319 00311 }
323 00315 }
326 00318
328 00320 <font class="comment"> * Given two lattices 'A' and 'B', verify if lattice 'A' is included in 'B' or</font>
329 00321 <font class="comment"> * not. If 'A' is included in 'B' the 'A' intersection 'B', will be 'A'. So, </font>
330 00322 <font class="comment"> * compute 'A' intersection 'B' and check if it is the same as 'A'. </font>
332 <a name="l00324"></a><a class="code" href="Lattice_8c.html#a11">00324</a> Bool <a class="code" href="Lattice_8c.html#a11">LatticeIncludes</a>(Lattice *A, Lattice *B) {
333 00325
334 00326 Lattice *temp, *UA, *HA;
335 00327 Bool flag = False;
336 00328
339 00331 fp = fopen(<font class="stringliteral">"_debug"</font>, <font class="stringliteral">"a"</font>);
341 00333 fclose(fp);
346 00338 <font class="keywordflow">if</font> (<a class="code" href="Lattice_8c.html#a12">sameLattice</a>(temp, HA) == True)
347 00339 flag = True;
348 00340
354 00346
356 00348 <font class="comment"> * Given two lattices 'A' and 'B', verify if 'A' and 'B' are the same lattice.</font>
358 00350 <font class="comment"> * The Affine Hermite form of two full dimensional matrices are </font>
359 00351 <font class="comment"> * unique. So, take the Affine Hermite form of both 'A' and 'B' and compare the</font>
360 00352 <font class="comment"> * matrices. If they are equal, the function returns True, else it returns </font>
363 <a name="l00355"></a><a class="code" href="Lattice_8c.html#a12">00355</a> Bool <a class="code" href="Lattice_8c.html#a12">sameLattice</a>(Lattice *A, Lattice *B) {
364 00356
365 00357 Lattice *HA, *HB, *UA, *UB;
367 00359 Bool result = True;
368 00360
371 00363 fp = fopen(<font class="stringliteral">"_debug"</font>, <font class="stringliteral">"a"</font>);
373 00365 fclose(fp);
378 00370
381 00373 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a23">value_ne</a>(HA->p[i][j],HB->p[i][j])) {
382 00374 result = False;
384 00376 }
385 00377
390 00382
393 00385
395 00387 <font class="comment"> * Given a matrix 'A' and an integer 'dimension', do the following: </font>
396 00388 <font class="comment"> * If dimension < A->dimension), output a (dimension * dimension) submatrix of </font>
397 00389 <font class="comment"> * A. Otherwise the output matrix is [A 0][0 ID]. The order if the identity </font>
398 00390 <font class="comment"> * matrix is (dimension - A->dimension). The input matrix is not necessarily </font>
401 <a name="l00393"></a><a class="code" href="Lattice_8c.html#a13">00393</a> Lattice *<a class="code" href="Lattice_8c.html#a13">ChangeLatticeDimension</a>(Lattice *A, <font class="keywordtype">int</font> dimension) {
402 00394
404 00396 Lattice *Result ;
405 00397
410 00402 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(Result->p[i][j],A->p[i][j]);
412 00404 }
415 00407 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(Result->p[i][j],A->p[i][j]);
416 00408
421 00413 }
426 00418
428 00420 <font class="comment"> * Given an affine lattice 'A', return a matrix of the linear part of the </font>
431 <a name="l00423"></a><a class="code" href="Lattice_8c.html#a14">00423</a> Lattice *<a class="code" href="Lattice_8c.html#a14">ExtractLinearPart</a>(Lattice *A) {
432 00424
433 00425 Lattice *Result;
435 00427 Result = (Lattice *) <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(A->NbRows-1, A->NbColumns-1);
438 00430 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(Result->p[i][j],A->p[i][j]);
441 00433
442 00434 <font class="keyword">static</font> Matrix *<a class="code" href="Lattice_8c.html#a17">MakeDioEqforInter</a>(Matrix *A, Matrix *B);
443 00435
445 00437 <font class="comment"> * Given two lattices 'A' and 'B', return the intersection of the two lattcies.</font>
448 00440 <font class="comment"> * (1) Verify if the lattcies 'A' and 'B' have the same affine part. </font>
449 00441 <font class="comment"> * If they have same affine part, then only their Linear parts </font>
450 00442 <font class="comment"> * need to be intersected. If they don't have the same affine</font>
451 00443 <font class="comment"> * part then the affine part has to be taken into consideration. </font>
452 00444 <font class="comment"> * For this, homogenise the lattices to get their Hermite Forms</font>
455 00447 <font class="comment"> * (2) Step(2) involves, solving the Diophantine Equations in order </font>
456 00448 <font class="comment"> * to extract the intersection of the Lattices. The Diophantine</font>
457 00449 <font class="comment"> * equations are formed taking into consideration whether the </font>
464 00456 <font class="comment"> * (5) If the lattices have different affine parts and they were </font>
467 <a name="l00459"></a><a class="code" href="Lattice_8c.html#a16">00459</a> Lattice *<a class="code" href="Lattice_8c.html#a16">LatticeIntersection</a>(Lattice *X, Lattice *Y) {
468 00460
470 00462 Lattice *result = NULL, *U = NULL ;
471 00463 Lattice *A = NULL, *B = NULL, *H = NULL;
472 00464 Matrix *fordio;
473 00465 Vector *X1 = NULL;
474 00466
477 00469 fp = fopen(<font class="stringliteral">"_debug"</font>, <font class="stringliteral">"a"</font>);
479 00471 fclose(fp);
483 00475 fprintf(stderr, <font class="stringliteral">"\nIn LatticeIntersection : The Input Matrix X is a not a well defined Lattice\n"</font>);
484 00476 <font class="keywordflow">return</font> <a class="code" href="Lattice_8c.html#a5">EmptyLattice</a>(X->NbRows);
485 00477 }
486 00478
488 00480 fprintf (stderr, <font class="stringliteral">"\nIn LatticeIntersection : The Input Matrix Y is a not a well defined Lattice\n"</font>);
489 00481 <font class="keywordflow">return</font> <a class="code" href="Lattice_8c.html#a5">EmptyLattice</a>(X->NbRows);
490 00482 }
491 00483
493 00485 fprintf (stderr, <font class="stringliteral">"\nIn LatticeIntersection : The Input Lattices X and Y are of incompatible dimensions\n"</font>);
494 00486 <font class="keywordflow">return</font> <a class="code" href="Lattice_8c.html#a5">EmptyLattice</a>(X->NbRows);
495 00487 }
496 00488
497 00489 <font class="keywordflow">if</font> (<a class="code" href="Matop_8c.html#a7">isinHnf</a>(X))
504 00496 }
505 00497
506 00498 <font class="keywordflow">if</font> (<a class="code" href="Matop_8c.html#a7">isinHnf</a>(Y))
513 00505 }
514 00506
515 00507 <font class="keywordflow">if</font> ((<a class="code" href="Lattice_8c.html#a6">isEmptyLattice</a>(A)) || (<a class="code" href="Lattice_8c.html#a6">isEmptyLattice</a> (B))) {
520 00512 }
524 00516 exist = <a class="code" href="SolveDio_8c.html#a1">SolveDiophantine</a>(fordio,(Matrix **) &U, &X1);
525 00517 <font class="keywordflow">if</font> (exist < 0) { <font class="comment">/* Intersection is NULL */</font>
528 00520 }
529 00521
530 00522 result = (Lattice *)<a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(X->NbRows, X->NbColumns);
533 00525 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(result->p[i][j],U->p[i][j]);
534 00526
536 00528 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(result->p[i][result->NbColumns-1],X1->p[i]);
538 00530 <a class="code" href="arithmetique_8h.html#a12">value_set_si</a>(result->p[result->NbRows-1][i],0);
539 00531 <a class="code" href="arithmetique_8h.html#a12">value_set_si</a>(result->p[result->NbRows-1][result->NbColumns-1],1);
540 00532
544 00536
548 00540
551 00543
553 00545
554 00546 <font class="keywordflow">if</font> (<a class="code" href="Lattice_8c.html#a6">isEmptyLattice</a> (result)) {
556 00548 <font class="keywordflow">return</font> (<a class="code" href="Lattice_8c.html#a5">EmptyLattice</a> (X->NbRows));
557 00549 }
560 00552
561 <a name="l00553"></a><a class="code" href="Lattice_8c.html#a17">00553</a> <font class="keyword">static</font> Matrix * <a class="code" href="Lattice_8c.html#a17">MakeDioEqforInter</a> (Lattice *A, Lattice *B) {
562 00554
563 00555 Matrix *Dio ;
565 00557
568 00560 fp = fopen(<font class="stringliteral">"_debug"</font>, <font class="stringliteral">"a"</font>);
570 00562 fclose(fp);
573 00565 Dio = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(2*(A->NbRows-1) + 1, 3 * (A->NbColumns-1)+1);
574 00566
578 00570
581 00573 <a class="code" href="arithmetique_8h.html#a12">value_set_si</a>(Dio->p[i+A->NbRows-1][i],1);
582 00574 }
585 00577 <a class="code" href="arithmetique_8h.html#a54">value_oppose</a>(Dio->p[i][j+A->NbRows-1],A->p[i][j]);
586 00578 <a class="code" href="arithmetique_8h.html#a54">value_oppose</a>(Dio->p[i+(A->NbRows-1)][j+2*(A->NbRows-1)],B->p[i][j]);
587 00579 }
588 00580
590 00582
592 00584 <a class="code" href="arithmetique_8h.html#a54">value_oppose</a>(Dio->p[i][Dio->NbColumns-1],A->p[i][A->NbColumns-1]);
593 00585 <a class="code" href="arithmetique_8h.html#a54">value_oppose</a>(Dio->p[i+A->NbRows-1][Dio->NbColumns-1],B->p[i][A->NbColumns-1]) ;
594 00586 }
595 00587 <a class="code" href="arithmetique_8h.html#a12">value_set_si</a>(Dio->p[Dio->NbRows-1][Dio->NbColumns-1],1);
598 00590
599 00591 <font class="keyword">static</font> <font class="keywordtype">void</font> <a class="code" href="Lattice_8c.html#a18">AddLattice</a>(LatticeUnion *,Matrix *, Matrix *, <font class="keywordtype">int</font> , <font class="keywordtype">int</font>);
600 00592 LatticeUnion *<a class="code" href="Lattice_8c.html#a22">SplitLattice</a>(Matrix *, Matrix *, Matrix *);
601 00593
602 00594
603 00595
605 00597 <font class="comment"> * The function is transforming a lattice X in a union of lattices based on a starting lattice Y.</font>
606 00598 <font class="comment"> * Note1: If the intersection of X and Y lattices is empty the result is identic with the first argument (X) because no operation can be made.</font>
607 00599 <font class="comment"> *Note2: The function is availabe only for simple Lattices and not for a union of Lattices.</font>
610 00602 <font class="comment"> * Step 2: Extract the Linear Parts of the Lattices A and Intersection.</font>
611 00603 <font class="comment"> * (while dealing with Basis we only deal with the Linear Parts)</font>
617 00609 <font class="comment"> * parts we obtained in Step 2. Our Task is now to find U1 and</font>
633 00625 <font class="comment"> * of the actual inverse. The number by which we have to divide</font>
634 00626 <font class="comment"> * the matrix, is not obtained here as the input matrix is not</font>
635 00627 <font class="comment"> * a Polylib matrix { We input only the Linear part }. Later I</font>
643 00635 <font class="comment"> * Step 6 : Find U2 = Matrix_Inverse (U2inverse). Here there is no prob</font>
648 00640 <font class="comment"> * Step 9 : Earlier when we computed M1Inverse, we knew that it was not</font>
650 00642 <font class="comment"> * number, such that ( M1Inverse / number ) would give us the </font>
656 00648 <font class="comment"> * We Divide the matrix Delta by this number, to get the actual</font>
659 00651 <font class="comment"> * This function returns the Union of Lattices in such a way </font>
662 00654 <font class="comment"> *If the intersection between X and Y is empty then the result is NULL.</font>
664 00656
665 00657
666 <a name="l00658"></a><a class="code" href="Lattice_8c.html#a20">00658</a> LatticeUnion *<a class="code" href="Lattice_8c.html#a20">Lattice2LatticeUnion</a>(Lattice *X,Lattice *Y)
667 00659 {
668 00660 Lattice *B1 = NULL, *B2 = NULL, *newB1 = NULL, *newB2 = NULL, *Intersection=NULL;
669 00661 Matrix *U = NULL,*M1 = NULL, *M2 = NULL, *M1Inverse = NULL,*MtProduct = NULL;
670 00662 Matrix *Vinv, *V , *temp, *DiagMatrix ;
671 00663
672 00664 LatticeUnion *Head = NULL, *tempHead = NULL;
675 00667
676 00668
678 00670 <font class="keywordflow">if</font> (<a class="code" href="Lattice_8c.html#a6">isEmptyLattice</a>(Intersection) == True) {
679 00671 fprintf(stderr,<font class="stringliteral">"\nIn Lattice2LatticeUnion : The Input Lattices X and Y does not have any common part\n"</font>);
681 00673 }
682 00674
685 00677 M2 = (Matrix *)<a class="code" href="Lattice_8c.html#a14">ExtractLinearPart</a>(Intersection);
686 00678
687 00679 M1Inverse = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(M1->NbRows,M1->NbColumns);
691 00683
692 00684 MtProduct = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(M1->NbRows, M1->NbColumns);
694 00686 <a class="code" href="NormalForms_8c.html#a15">Smith</a>(MtProduct, &U, &Vinv, &DiagMatrix);
695 00687 V = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(Vinv->NbRows,Vinv->NbColumns);
698 00690 B1 = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(M1->NbRows, U->NbColumns);
699 00691 B2 = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(M2->NbRows, V->NbColumns);
704 00696 <a class="code" href="arithmetique_8h.html#a51">value_division</a>(k,B2->p[0][0],B1->p[0][0]);
705 00697 <a class="code" href="arithmetique_8h.html#a51">value_division</a>(k,DiagMatrix->p[0][0],k);
707 00699 <a class="code" href="arithmetique_8h.html#a51">value_division</a>(DiagMatrix->p[i][i],DiagMatrix->p[i][i],k);
708 00700 newB1 = <a class="code" href="Lattice_8c.html#a13">ChangeLatticeDimension</a>(B1, B1->NbRows + 1);
710 00702 newB2 = <a class="code" href="Lattice_8c.html#a13">ChangeLatticeDimension</a>(B2, B2->NbRows +1);
713 00705 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(newB2->p[i][newB1->NbRows-1],Intersection->p[i][X->NbRows-1]);
714 00706 Head = <a class="code" href="Lattice_8c.html#a22">SplitLattice</a>(newB1,newB2,DiagMatrix);
719 00711 }
720 00712
721 00713
729 00721 <font class="comment"> * Return the Union of lattices that constitute the difference the lattices </font>
730 00722 <font class="comment"> * 'A' and 'B'. The dimensions of 'A' and 'B' should be the same. </font>
732 00724 <font class="comment"> * Inorder to Find the Difference of Lattices, we make use of</font>
735 00727 <font class="comment"> * Theorem : Given Two Lattices L1 and L2, (L2 subset of L1) there exists a</font>
736 00728 <font class="comment"> * Basis B = {b1, b2,..bn} of L1 and integers {a1, a2...,an} such </font>
737 00729 <font class="comment"> * that a1 divides a2, a2 divides a3 and so on and {a1b1, a2b2 ,...,</font>
738 00730 <font class="comment"> * .., anbn} is a Basis of L2. So given this theorem we can express </font>
739 00731 <font class="comment"> * the Lattice L1 in terms of Union of Lattices Involving L2, such </font>
740 00732 <font class="comment"> * that Lattice L1 = B1 = Union of (B2 + i1b1 + i2b2 + .. inbn) such</font>
741 00733 <font class="comment"> * that 0 <= i1 < a1; 0 <= i2 < a2; ....... 0 <= in < an. We also</font>
742 00734 <font class="comment"> * know that A/B = A/(A Intersection B) and that (A Intersection B) </font>
743 00735 <font class="comment"> * is a subset of A. So, Making use of these two facts, we find the </font>
744 00736 <font class="comment"> * A/B. We Split The Lattice A in terms of Lattice (A Int B). From </font>
750 00742 <font class="comment"> * Step 2: Extract the Linear Parts of the Lattices A and Intersection.</font>
751 00743 <font class="comment"> * (while dealing with Basis we only deal with the Linear Parts)</font>
757 00749 <font class="comment"> * parts we obtained in Step 2. Our Task is now to find U1 and</font>
773 00765 <font class="comment"> * of the actual inverse. The number by which we have to divide</font>
774 00766 <font class="comment"> * the matrix, is not obtained here as the input matrix is not</font>
775 00767 <font class="comment"> * a Polylib matrix { We input only the Linear part }. Later I</font>
783 00775 <font class="comment"> * Step 6 : Find U2 = Matrix_Inverse (U2inverse). Here there is no prob</font>
788 00780 <font class="comment"> * Step 9 : Earlier when we computed M1Inverse, we knew that it was not</font>
790 00782 <font class="comment"> * number, such that ( M1Inverse / number ) would give us the </font>
796 00788 <font class="comment"> * We Divide the matrix Delta by this number, to get the actual</font>
799 00791 <font class="comment"> * This function returns the Union of Lattices in such a way </font>
801 00793 <font class="comment"> * Step 11 : To Remove B2 From the list of the Union of Lattices.</font>
803 00795 <font class="comment"> * Step 12 : Free the Memory that is now not needed and return Head.</font>
806 <a name="l00798"></a><a class="code" href="Lattice_8c.html#a21">00798</a> LatticeUnion *<a class="code" href="Lattice_8c.html#a21">LatticeDifference</a>(Lattice *A,Lattice *B) {
807 00799
808 00800 Lattice *Intersection = NULL;
809 00801 LatticeUnion *Head = NULL, *tempHead = NULL;
810 00802 Matrix *H , *U1 , *X, *Y ;
811 00803
814 00806 fp = fopen(<font class="stringliteral">"_debug"</font>, <font class="stringliteral">"a"</font>);
816 00808 fclose(fp);
820 00812 fprintf(stderr,<font class="stringliteral">"\nIn LatticeDifference : The Input Matrix A is not a proper Lattice \n"</font>);
822 00814 }
823 00815
825 00817 fprintf(stderr,<font class="stringliteral">"\nIn LatticeDifference : The Input Matrix B is not a proper Lattice \n"</font>);
827 00819 }
828 00820
830 00822 fprintf(stderr,<font class="stringliteral">"\nIn Lattice Difference : The Input Lattices A and B have "</font>);
833 00825 }
834 00826
835 00827 <font class="keywordflow">if</font> (<a class="code" href="Matop_8c.html#a7">isinHnf</a> (A) != True) {
840 00832 }
843 00835
844 00836 <font class="keywordflow">if</font> (<a class="code" href="Matop_8c.html#a7">isinHnf</a>(B) != True) {
849 00841 }
852 00844 <font class="keywordflow">if</font> (<a class="code" href="Lattice_8c.html#a6">isEmptyLattice</a>(X)) {
854 00846 }
855 00847
857 00849
858 00850 <font class="comment">/* If the spliting operation can't be done the result is X. */</font>
859 00851
867 00859 }
868 00860
869 00861 tempHead = Head;
873 00865 free(tempHead);
874 00866
879 00871
882 00874
883 00875
885 00877 <font class="comment"> * Given a Lattice 'B1' and a Lattice 'B2' and a Diagonal Matrix 'C' such that</font>
886 00878 <font class="comment"> * 'B2' is a subset of 'B1' and C[0][0] divides C[1][1], C[1][1] divides C[2]</font>
887 00879 <font class="comment"> * [2] and so on, output the list of matrices whose union is B1. The function</font>
888 00880 <font class="comment"> * expresses the Lattice B1 in terms of B2 Unions of B1 = Union of {B2 + i0b0 +</font>
889 00881 <font class="comment"> * i1b1 + .... + inbn} where 0 <= i0 < C[0][0]; 0 <= i1 < C[1][1] and so on and</font>
890 00882 <font class="comment"> * {b0 ... bn} are the columns of Lattice B1. The list is so formed that the </font>
893 <a name="l00885"></a><a class="code" href="Lattice_8c.html#a22">00885</a> LatticeUnion *<a class="code" href="Lattice_8c.html#a22">SplitLattice</a>(Lattice *B1, Lattice *B2, Matrix *C) {
894 00886
896 00888
897 00889 LatticeUnion *Head = NULL;
902 00894 <a class="code" href="Lattice_8c.html#a18">AddLattice</a>(Head,B1,B2,<a class="code" href="arithmetique_8h.html#a7">VALUE_TO_INT</a>(C->p[i][i]),i);
905 00897
907 00899 <font class="comment"> * Given lattices 'B1' and 'B2', an integer 'NumofTimes', a column number </font>
908 00900 <font class="comment"> * 'Colnumber' and a pointer to a list of lattices, the function does the </font>
910 00902 <font class="comment"> * For every lattice in the list, it adds a set of lattices such that the </font>
911 00903 <font class="comment"> * affine part of the new lattices is greater than the original lattice by 0 to</font>
914 00906 <font class="comment"> * Three pointers are defined to point at various points of the list. They are:</font>
916 00908 <font class="comment"> * tail -> It always points to the last element in the list. </font>
917 00909 <font class="comment"> * marker -> It points to the element, which is the last element of the Input </font>
920 <a name="l00912"></a><a class="code" href="Lattice_8c.html#a18">00912</a> <font class="keyword">static</font> <font class="keywordtype">void</font> <a class="code" href="Lattice_8c.html#a18">AddLattice</a> (LatticeUnion *Head, Matrix *B1, Matrix *B2, <font class="keywordtype">int</font> NumofTimes, <font class="keywordtype">int</font> Colnumber) {
921 00913
922 00914 LatticeUnion *temp, *tail, *marker;
925 00917
927 00919 tail = Head;
930 00922 marker = tail;
931 00923
934 00926 Lattice *tempMatrix, *H, *U;
935 00927
936 00928 tempMatrix = (Lattice *)<a class="code" href="Matop_8c.html#a5">Matrix_Copy</a>(temp->M);
939 00931 <a class="code" href="arithmetique_8h.html#a47">value_multiply</a>(tmp,tmp,B1->p[j][Colnumber]);
940 00932 <a class="code" href="arithmetique_8h.html#a43">value_addto</a>(tempMatrix->p[j][B2->NbColumns-1],tempMatrix->p[j][B2->NbColumns-1],tmp);
941 00933 }
942 00934 tail->next = (LatticeUnion *)malloc(<font class="keyword">sizeof</font>(LatticeUnion));
949 00941 }
952 00944 }
956 00948
958 00950 <font class="comment"> * Given a polyhedron 'A', store the Hermite basis 'B' and return the true </font>
967 00959 <font class="comment"> * 2) Then there are the rays and lines which contribute to the</font>
969 00961 <font class="comment"> * So we append to the rays and lines. So now we get a matrix</font>
971 00963 <font class="comment"> * where l1 to lk are either rays or lines of the Polyhedron A.</font>
983 <a name="l00975"></a><a class="code" href="Lattice_8c.html#a23">00975</a> <font class="keywordtype">int</font> <a class="code" href="Lattice_8c.html#a23">FindHermiteBasisofDomain</a>(Polyhedron *A, Matrix **B) {
984 00976
986 00978 Matrix *temp,*temp1, *tempinv, *Newmat ;
987 00979 Matrix *vert, *rays, *result;
988 00980 Polyhedron *Image;
993 00985
996 00988 fp = fopen(<font class="stringliteral">"_debug"</font>, <font class="stringliteral">"a"</font>);
998 00990 fclose(fp);
1005 00997 }
1006 00998
1007 00999 <a class="code" href="arithmetique_8h.html#a10">value_init</a>(lcm); <a class="code" href="arithmetique_8h.html#a10">value_init</a>(fact);
1009 01001
1012 01004 <font class="keywordflow">if</font> ((<a class="code" href="arithmetique_8h.html#a68">value_notzero_p</a>(A->Ray[i][0])) && <a class="code" href="arithmetique_8h.html#a68">value_notzero_p</a>(A->Ray[i][A->Dimension+1]))
1013 01005 noofvertices++;
1015 01007 noofrays ++;
1016 01008
1017 01009 vert = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(noofvertices,A->Dimension+1);
1018 01010 rays = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(noofrays,A->Dimension);
1021 01013
1023 01015 <font class="keywordflow">if</font> ((<a class="code" href="arithmetique_8h.html#a68">value_notzero_p</a>(A->Ray[i][0])) && <a class="code" href="arithmetique_8h.html#a68">value_notzero_p</a>(A->Ray[i][A->Dimension+1])) {
1025 01017 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(vert->p[vercount][j-1],A->Ray[i][j]);
1026 01018 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(lcm,*<a class="code" href="Matop_8c.html#a0">Lcm</a>(lcm,A->Ray[i][j-1]));
1027 01019 vercount++;
1028 01020 }
1031 01023 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(rays->p[raycount][j-1],A->Ray[i][j]);
1032 01024 raycount++;
1033 01025 }
1034 01026 }
1035 01027
1038 01030 <a class="code" href="arithmetique_8h.html#a51">value_division</a>(fact,lcm,vert->p[i][vert->NbColumns-1]);
1040 01032 <a class="code" href="arithmetique_8h.html#a47">value_multiply</a>(vert->p[i][j],vert->p[i][j],fact);
1041 01033 }
1042 01034
1044 01036 temp = <a class="code" href="Matop_8c.html#a15">RemoveColumn</a>(vert,vert->NbColumns-1);
1046 01038
1048 01040 vert = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(temp->NbRows-1, temp->NbColumns);
1051 01043 <a class="code" href="arithmetique_8h.html#a48">value_substract</a>(vert->p[i-1][j],temp->p[0][j],temp->p[i][j]);
1052 01044
1055 01047 result = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(vert->NbRows+rays->NbRows, vert->NbColumns);
1058 01050 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(result->p[i][j],vert->p[i][j]);
1059 01051
1062 01054 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(result->p[i][j],rays->p[i-vert->NbRows][j]);
1063 01055
1066 01058
1068 01060 temp1 = <a class="code" href="Lattice_8c.html#a13">ChangeLatticeDimension</a>(temp,temp->NbRows+1);
1069 01061
1073 01065
1076 01068 tempinv = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(temp->NbRows,temp->NbColumns);
1079 01071 Image = <a class="code" href="polyhedron_8c.html#a53">DomainImage</a>(A,tempinv,MAXNOOFRAYS);
1080 01072 Newmat = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(temp1->NbRows,temp1->NbColumns);
1088 01080 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a67">value_zero_p</a>(Image->Constraint[i][0])) {
1090 01082 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(Newmat->p[rank+equcount][j-1],Image->Constraint[i][j]);
1091 01083 ++equcount ;
1092 01084 }
1094 01086 <a class="code" href="arithmetique_8h.html#a12">value_set_si</a>(Newmat->p[Newmat->NbRows-1][i],0);
1095 01087 <a class="code" href="arithmetique_8h.html#a12">value_set_si</a>(Newmat->p[Newmat->NbRows-1][Newmat->NbColumns-1],1);
1096 01088 temp = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(Newmat->NbRows, Newmat->NbColumns);
1098 01090 B[0] = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(temp1->NbRows,temp->NbColumns);
1099 01091
1101 01093
1107 01099
1109 01101 <font class="comment"> * Return the image of a lattice 'A' by the invertible, affine, rational </font>
1112 <a name="l01104"></a><a class="code" href="Lattice_8c.html#a24">01104</a> Lattice *<a class="code" href="Lattice_8c.html#a24">LatticeImage</a>(Lattice *A, Matrix *M) {
1113 01105
1114 01106 Lattice *Img, *temp, *Minv;
1115 01107
1118 01110 fp = fopen(<font class="stringliteral">"_debug"</font>, <font class="stringliteral">"a"</font>);
1120 01112 fclose(fp);
1123 01115 <font class="keywordflow">if</font> ((A->NbRows != M->NbRows) || (M->NbRows != M->NbColumns))
1124 01116 <font class="keywordflow">return</font> (<a class="code" href="Lattice_8c.html#a5">EmptyLattice</a> (A->NbRows));
1125 01117
1126 01118 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a69">value_one_p</a>(M->p[M->NbRows-1][M->NbColumns-1])) {
1127 01119 Img = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a> ( M->NbRows, A->NbColumns );
1130 01122 }
1132 01124 Minv = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(temp->NbColumns, temp->NbRows);
1135 01127
1140 01132
1142 01134 <font class="comment"> * Return the preimage of a lattice 'L' by an affine, rational function 'G'.</font>
1147 01139 <font class="comment"> * (3) If there is solution to the Diophantine eq., extract the </font>
1148 01140 <font class="comment"> * general solution and the particular solution of x and that </font>
1151 <a name="l01143"></a><a class="code" href="Lattice_8c.html#a25">01143</a> Lattice *<a class="code" href="Lattice_8c.html#a25">LatticePreimage</a>(Lattice *L, Matrix *G) {
1152 01144
1153 01145 Matrix *Dio, *U ;
1154 01146 Lattice *Result;
1155 01147 Vector *X;
1159 01151
1162 01154 fp = fopen(<font class="stringliteral">"_debug"</font>, <font class="stringliteral">"a"</font>);
1164 01156 fclose(fp);
1169 01161 fprintf (stderr, <font class="stringliteral">"\nIn LatticePreimage: Incompatible types of Lattice and the function\n"</font>);
1170 01162 <font class="keywordflow">return</font> (<a class="code" href="Lattice_8c.html#a5">EmptyLattice</a>(G->NbColumns));
1171 01163 }
1172 01164
1173 01165 <a class="code" href="arithmetique_8h.html#a10">value_init</a>(divisor); <a class="code" href="arithmetique_8h.html#a10">value_init</a>(tmp);
1174 01166
1176 01168 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(divisor,G->p[G->NbRows-1][G->NbColumns-1]);
1177 01169 Dio = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a>(G->NbRows, G->NbColumns+L->NbColumns-1);
1180 01172 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(Dio->p[i][j],G->p[i][j]);
1181 01173
1184 01176 <a class="code" href="arithmetique_8h.html#a47">value_multiply</a>(tmp,divisor,L->p[i][j]);
1185 01177 <a class="code" href="arithmetique_8h.html#a54">value_oppose</a>(Dio->p[i][j+G->NbColumns-1],tmp);
1186 01178 }
1187 01179
1189 01181 <a class="code" href="arithmetique_8h.html#a47">value_multiply</a>(tmp,divisor,L->p[i][L->NbColumns-1]);
1190 01182 <a class="code" href="arithmetique_8h.html#a48">value_substract</a>(tmp,G->p[i][G->NbColumns-1],tmp);
1191 01183 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(Dio->p[i][Dio->NbColumns-1],tmp);
1192 01184 }
1194 01186 <a class="code" href="arithmetique_8h.html#a12">value_set_si</a>(Dio->p[Dio->NbRows-1][i],0);
1195 01187
1196 01188 <a class="code" href="arithmetique_8h.html#a12">value_set_si</a>(Dio->p[Dio->NbRows-1][Dio->NbColumns-1],1);
1197 01189 rank = <a class="code" href="SolveDio_8c.html#a1">SolveDiophantine</a>(Dio, &U, &X);
1198 01190
1202 01194 Result = <a class="code" href="matrix_8c.html#a0">Matrix_Alloc</a> (G->NbColumns, G->NbColumns);
1205 01197 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(Result->p[i][j],U->p[i][j]);
1206 01198
1208 01200 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(Result->p[i][Result->NbColumns-1],X->p[i]);
1212 01204 <a class="code" href="arithmetique_8h.html#a12">value_set_si</a>(Result->p[Result->NbRows-1][i],0);
1214 01206 }
1220 01212
1222 01214 <font class="comment"> * Return True if the matrix 'm' is a valid lattice, otherwise return False. </font>
1223 01215 <font class="comment"> * Note: A valid lattice has the last row as [0 0 0 ... 1]. </font>
1225 <a name="l01217"></a><a class="code" href="Lattice_8c.html#a26">01217</a> Bool <a class="code" href="Lattice_8c.html#a26">IsLattice</a>(Matrix *m) {
1226 01218
1228 01220
1231 01223 fp = fopen (<font class="stringliteral">"_debug"</font>, <font class="stringliteral">"a"</font>);
1233 01225 fclose (fp);
1238 01230
1241 01233
1243 01235 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a68">value_notzero_p</a>(m->p[m->NbRows-1][i]))
1245 01237 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a70">value_notone_p</a>(m->p[i][i]))
1249 01241
1253 <a name="l01245"></a><a class="code" href="Lattice_8c.html#a27">01245</a> Bool <a class="code" href="Lattice_8c.html#a27">isfulldim</a>(Matrix *m) {
1254 01246
1255 01247 Matrix *h, *u ;
1257 01249
1263 01255
1266 01258 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a67">value_zero_p</a>(h->p[i][i])) {
1270 01262 }
1275 01267
1277 01269 <font class="comment"> * This function takes as input a lattice list in which the lattices have the </font>
1278 01270 <font class="comment"> * same linear part, and almost the same affinepart, i.e. if A and B are two </font>
1279 01271 <font class="comment"> * of the lattices in the above lattice list and [a1, .. , an] and [b1 .. bn]</font>
1280 01272 <font class="comment"> * are the affineparts of A and B respectively, then for 0 < i < n ai = bi and</font>
1281 01273 <font class="comment"> * 'an' may not be equal to 'bn'. These are not the affine parts in the n-th</font>
1282 01274 <font class="comment"> * dimension, but the lattices have been tranformed such that the value of the </font>
1283 01275 <font class="comment"> * elment in the dimension on which we are simplifying is in the last row and</font>
1285 01277 <font class="comment"> * This function also takes as input the dimension along which we</font>
1286 01278 <font class="comment"> * are simplifying and takes the diagonal element of the lattice along that</font>
1287 01279 <font class="comment"> * dimension and tries to find out the factors of that element and sees if the</font>
1288 01280 <font class="comment"> * list of lattices can be simplified using these factors. The output of this </font>
1289 01281 <font class="comment"> * function is the list of lattices in the simplified form and a flag to indic-</font>
1290 01282 <font class="comment"> * ate whether any form of simplification was actually done or not. </font>
1292 <a name="l01284"></a><a class="code" href="Lattice_8c.html#a28">01284</a> <font class="keyword">static</font> Bool <a class="code" href="Lattice_8c.html#a28">Simplify</a>(LatticeUnion **InputList, LatticeUnion **ResultList, <font class="keywordtype">int</font> dim) {
1293 01285
1295 01287 LatticeUnion *prev, *temp;
1297 01289 Bool retval = False;
1299 01291 <a class="code" href="arithmetique_8h.html#a93">Value</a> cnt, aux, k, fac, num, tmp, foobar;
1300 01292
1301 01293 <font class="keywordflow">if</font> ((*InputList == NULL) || (InputList[0]->next == NULL))
1303 01295
1304 01296 <a class="code" href="arithmetique_8h.html#a10">value_init</a>(aux); <a class="code" href="arithmetique_8h.html#a10">value_init</a>(cnt);
1305 01297 <a class="code" href="arithmetique_8h.html#a10">value_init</a>(k); <a class="code" href="arithmetique_8h.html#a10">value_init</a>(fac);
1306 01298 <a class="code" href="arithmetique_8h.html#a10">value_init</a>(num); <a class="code" href="arithmetique_8h.html#a10">value_init</a>(tmp);
1308 01300
1310 01302 allfac = <a class="code" href="Lattice_8c.html#a0">allfactors</a>(<a class="code" href="arithmetique_8h.html#a7">VALUE_TO_INT</a>(InputList[0]->M->p[dim][dim]));
1312 01304 <font class="keywordflow">for</font> (temp = InputList[0]; temp != NULL; temp = temp->next)
1314 01306 <font class="keywordflow">for</font>(i = 0; i < allfac.<a class="code" href="structfactor.html#m0">count</a>; i++) {
1315 01307 <a class="code" href="arithmetique_8h.html#a12">value_set_si</a>(foobar,allfac.<a class="code" href="structfactor.html#m1">fac</a>[i]);
1316 01308 <a class="code" href="arithmetique_8h.html#a51">value_division</a>(aux,InputList[0]->M->p[dim][dim],foobar);
1317 01309 <font class="keywordflow">if</font>(<a class="code" href="arithmetique_8h.html#a25">value_ge</a>(cnt,aux))
1319 01311 }
1320 01312 <font class="keywordflow">if</font> (i == allfac.<a class="code" href="structfactor.html#m0">count</a>) {
1321 01313 <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(cnt); <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(aux);
1322 01314 <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(k); <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(fac);
1323 01315 <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(num); <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(tmp);
1326 01318 }
1327 01319 <font class="keywordflow">for</font> (; i < allfac.<a class="code" href="structfactor.html#m0">count</a>; i++) {
1328 01320 Bool Present = False;
1330 01322
1332 01324 <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(cnt); <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(aux);
1333 01325 <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(k); <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(fac);
1334 01326 <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(num); <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(tmp);
1337 01329 }
1338 01330 <a class="code" href="arithmetique_8h.html#a12">value_set_si</a>(foobar,allfac.<a class="code" href="structfactor.html#m1">fac</a>[i]);
1339 01331 <a class="code" href="arithmetique_8h.html#a51">value_division</a>(num,InputList[0]->M->p[dim][dim],foobar);
1340 01332 <font class="keywordflow">while</font> (<a class="code" href="arithmetique_8h.html#a26">value_lt</a>(k,foobar)) {
1341 01333 Present = False;
1343 01335 <font class="keywordflow">for</font> (temp = *InputList; temp != NULL; temp = temp->next) {
1344 01336 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a22">value_eq</a>(temp->M->p[temp->M->NbRows-1][temp->M->NbColumns-1],fac)) {
1345 01337 <a class="code" href="arithmetique_8h.html#a12">value_set_si</a>(foobar,allfac.<a class="code" href="structfactor.html#m1">fac</a>[i]);
1347 01339 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a25">value_ge</a>(fac,(*InputList)->M->p[dim][dim])) {
1348 01340 Present = True;
1350 01342 }
1351 01343 }
1352 01344 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a24">value_gt</a>(temp->M->p[temp->M->NbRows-1][temp->M->NbColumns-1],fac))
1354 01346 }
1356 01348 retval = True;
1358 01350 *ResultList = temp = (LatticeUnion *)malloc(<font class="keyword">sizeof</font>(LatticeUnion));
1360 01352 <font class="keywordflow">for</font> (temp = *ResultList; temp->next != NULL; temp = temp->next);
1361 01353 temp->next = (LatticeUnion *) malloc (<font class="keyword">sizeof</font> (LatticeUnion));
1363 01355 }
1364 01356 temp->M = <a class="code" href="Matop_8c.html#a5">Matrix_Copy</a>(InputList[0]->M);
1366 01358 <a class="code" href="arithmetique_8h.html#a12">value_set_si</a>(foobar,allfac.<a class="code" href="structfactor.html#m1">fac</a>[i]);
1367 01359 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(temp->M->p[dim][dim],foobar);
1368 01360 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(temp->M->p[dim][width],k);
1369 01361 <a class="code" href="arithmetique_8h.html#a12">value_set_si</a>(temp->M->p[width][width],1);
1370 01362
1373 01365 prev = NULL;
1376 01368 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a22">value_eq</a>(temp->M->p[width][width],tmp)) {
1378 01370 prev = temp;
1381 01373 free(prev);
1382 01374 }
1386 01378 free(temp);
1388 01380 }
1389 01381 <a class="code" href="arithmetique_8h.html#a12">value_set_si</a>(foobar,allfac.<a class="code" href="structfactor.html#m1">fac</a>[i]);
1391 01383 }
1393 01385 prev = temp;
1395 01387 }
1396 01388 }
1397 01389 }
1399 01391 }
1400 01392 }
1401 01393 <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(cnt); <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(aux);
1402 01394 <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(k); <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(fac);
1403 01395 <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(num); <a class="code" href="arithmetique_8h.html#a14">value_clear</a>(tmp);
1407 01399
1409 01401 <font class="comment"> * This function is used in the qsort function in sorting the lattices. Given </font>
1410 01402 <font class="comment"> * two lattices 'A' and 'B', both in HNF, where A = [ [a11 0], [a21, a22, 0] .</font>
1411 01403 <font class="comment"> * .... [an1, .., ann] ] and B = [ [b11 0], [b21, b22, 0] ..[bn1, .., bnn] ],</font>
1412 01404 <font class="comment"> * then A < B, if there exists a pair <i,j> such that [aij < bij] and for every</font>
1413 01405 <font class="comment"> * other pair <i1, j1>, 0<=i1<i, 0<=j1<j [ai1j1 = bi1j1]. </font>
1415 <a name="l01407"></a><a class="code" href="Lattice_8c.html#a29">01407</a> <font class="keyword">static</font> <font class="keywordtype">int</font> <a class="code" href="Lattice_8c.html#a29">LinearPartCompare</a>(<font class="keyword">const</font> <font class="keywordtype">void</font> *A, <font class="keyword">const</font> <font class="keywordtype">void</font> *B) {
1416 01408
1417 01409 Lattice **L1, **L2;
1419 01411
1420 01412 L1 = (Lattice **) A;
1421 01413 L2 = (Lattice **) B;
1422 01414
1425 01417 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a24">value_gt</a>(L1[0]->p[i][j],L2[0]->p[i][j]))
1427 01419 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a26">value_lt</a>(L1[0]->p[i][j],L2[0]->p[i][j]))
1429 01421 }
1432 01424
1434 01426 <font class="comment"> * This function takes as input a List of Lattices and sorts them on the basis</font>
1435 01427 <font class="comment"> * of their Linear parts. It sorts in place, as a result of which the input </font>
1438 <a name="l01430"></a><a class="code" href="Lattice_8c.html#a30">01430</a> <font class="keyword">static</font> <font class="keywordtype">void</font> <a class="code" href="Lattice_8c.html#a30">LinearPartSort</a> (LatticeUnion *Head) {
1439 01431
1441 01433 Lattice **Latlist;
1442 01434 LatticeUnion *temp ;
1443 01435
1446 01438 cnt ++;
1447 01439
1449 01441
1453 01445
1454 01446 qsort(Latlist, cnt, <font class="keyword">sizeof</font>(Lattice *), <a class="code" href="Lattice_8c.html#a29">LinearPartCompare</a>);
1455 01447
1459 01451
1460 01452 free (Latlist);
1463 01455
1465 01457 <font class="comment"> * This function is used in 'AfiinePartSort' in sorting the lattices with the</font>
1466 01458 <font class="comment"> * same linear part. GIven two lattices 'A' and 'B' with affineparts [a1 .. an]</font>
1467 01459 <font class="comment"> * and [b1 ... bn], then A < B if for some 0 < i <= n, ai < bi and for 0 < i1 <</font>
1470 <a name="l01462"></a><a class="code" href="Lattice_8c.html#a31">01462</a> <font class="keyword">static</font> <font class="keywordtype">int</font> <a class="code" href="Lattice_8c.html#a31">AffinePartCompare</a>(<font class="keyword">const</font> <font class="keywordtype">void</font> *A, <font class="keyword">const</font> <font class="keywordtype">void</font> *B) {
1471 01463
1473 01465 Lattice **L1, **L2;
1474 01466
1475 01467 L1 = (Lattice **)A;
1476 01468 L2 = (Lattice **)B;
1477 01469
1479 01471 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a24">value_gt</a>(L1[0]->p[i][L1[0]->NbColumns-1],L2[0]->p[i][L1[0]->NbColumns-1]))
1481 01473
1482 01474 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a26">value_lt</a>(L1[0]->p[i][L1[0]->NbColumns-1],L2[0]->p[i][L1[0]->NbColumns-1]))
1484 01476 }
1487 01479
1489 01481 <font class="comment"> * This function takes a list of lattices with the same linear part and sorts</font>
1490 01482 <font class="comment"> * them on the basis of their affine part. The sorting is done in place.</font>
1492 <a name="l01484"></a><a class="code" href="Lattice_8c.html#a32">01484</a> <font class="keyword">static</font> <font class="keywordtype">void</font> <a class="code" href="Lattice_8c.html#a32">AffinePartSort</a> (LatticeUnion *List) {
1493 01485
1495 01487 Lattice **LatList;
1496 01488 LatticeUnion *tmp;
1497 01489
1500 01492 cnt ++;
1501 01493
1503 01495
1507 01499
1508 01500 qsort(LatList,cnt, <font class="keyword">sizeof</font> (Lattice *), <a class="code" href="Lattice_8c.html#a31">AffinePartCompare</a>);
1509 01501
1515 01507
1516 <a name="l01508"></a><a class="code" href="Lattice_8c.html#a33">01508</a> <font class="keyword">static</font> Bool <a class="code" href="Lattice_8c.html#a33">AlmostSameAffinePart</a>(LatticeUnion *A, LatticeUnion *B) {
1517 01509
1519 01511
1522 01514
1524 01516 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a23">value_ne</a>(A->M->p[i][A->M->NbColumns-1],B->M->p[i][A->M->NbColumns-1]))
1528 01520
1530 01522 <font class="comment"> * This function takes a list of lattices having the same linear part and tries</font>
1531 01523 <font class="comment"> * to simplify these lattices. This may not be the only way of simplifying the</font>
1532 01524 <font class="comment"> * lattices. The function returns a list of partially simplified lattices and </font>
1533 01525 <font class="comment"> * also a flag to tell whether any simplification was performed at all. </font>
1535 <a name="l01527"></a><a class="code" href="Lattice_8c.html#a34">01527</a> <font class="keyword">static</font> Bool <a class="code" href="Lattice_8c.html#a34">AffinePartSimplify</a>(LatticeUnion *curlist, LatticeUnion **newlist) {
1536 01528
1539 01531 LatticeUnion *temp, *curr, *next;
1540 01532 LatticeUnion *nextlist;
1541 01533 Bool change = False, chng;
1542 01534
1545 01537
1550 01542 }
1551 01543
1553 01545 <font class="keywordflow">for</font> (i = 0; i < curlist->M->NbRows - 1; i ++) {
1554 01546
1555 01547 <font class="comment">/* Interchanging the elements of the Affine part for easy computation</font>
1557 01549
1558 01550 <font class="keywordflow">for</font> (temp = curlist; temp != NULL; temp = temp->next) {
1559 01551 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(aux,temp->M->p[temp->M->NbRows-1][temp->M->NbColumns-1]);
1560 01552 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(temp->M->p[temp->M->NbRows-1][temp->M->NbColumns-1],temp->M->p[i][temp->M->NbColumns-1]);
1561 01553 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(temp->M->p[i][temp->M->NbColumns-1],aux);
1562 01554 }
1564 01556 nextlist = NULL;
1565 01557 curr = curlist;
1568 01560 <font class="keywordflow">if</font> (!<a class="code" href="Lattice_8c.html#a33">AlmostSameAffinePart</a>(curr, next)) {
1570 01562 chng = <a class="code" href="Lattice_8c.html#a28">Simplify</a>(&curlist, newlist, i);
1572 01564 nextlist = curlist;
1574 01566 LatticeUnion *tmp;
1577 01569 }
1578 01570 change = change | chng ;
1579 01571 curlist = next;
1580 01572 }
1581 01573 curr = next;
1582 01574 }
1583 01575 curlist = nextlist;
1584 01576
1585 01577 <font class="comment">/* Interchanging the elements of the Affine part for easy computation</font>
1587 01579
1588 01580 <font class="keywordflow">for</font>(temp = curlist; temp != NULL; temp = temp->next) {
1589 01581 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(aux,temp->M->p[temp->M->NbRows-1][temp->M->NbColumns-1]);
1590 01582 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(temp->M->p[temp->M->NbRows-1][temp->M->NbColumns-1],temp->M->p[i][temp->M->NbColumns-1]);
1591 01583 <a class="code" href="arithmetique_8h.html#a11">value_assign</a>(temp->M->p[i][temp->M->NbColumns-1],aux);
1592 01584 }
1595 01587 }
1597 01589 *newlist = nextlist;
1599 01591 <font class="keywordflow">for</font> (curr = *newlist; curr->next != NULL; curr = curr->next);
1601 01593 }
1605 01597
1606 <a name="l01598"></a><a class="code" href="Lattice_8c.html#a35">01598</a> <font class="keyword">static</font> Bool <a class="code" href="Lattice_8c.html#a35">SameLinearPart</a>(LatticeUnion *A, LatticeUnion *B) {
1607 01599
1613 01605 <font class="keywordflow">if</font> (<a class="code" href="arithmetique_8h.html#a23">value_ne</a>(A->M->p[i][j],B->M->p[i][j]))
1615 01607
1618 01610
1620 01612 <font class="comment"> * Given a union of lattices, return a simplified list of lattices. </font>
1622 <a name="l01614"></a><a class="code" href="Lattice_8c.html#a36">01614</a> LatticeUnion *<a class="code" href="Lattice_8c.html#a36">LatticeSimplify</a>(LatticeUnion *latlist) {
1623 01615
1624 01616 LatticeUnion *curlist, *nextlist;
1625 01617 LatticeUnion *curr, *next;
1626 01618 Bool change = True, chng;
1627 01619
1628 01620 curlist = latlist;
1630 01622 change = False;
1632 01624 curr = curlist;
1633 01625 nextlist = NULL;
1636 01628 <font class="keywordflow">if</font> (!<a class="code" href="Lattice_8c.html#a35">SameLinearPart</a>(curr, next)) {
1638 01630 chng = <a class="code" href="Lattice_8c.html#a34">AffinePartSimplify</a>(curlist, &nextlist);
1639 01631 change = change | chng ;
1640 01632 curlist = next;
1641 01633 }
1642 01634 curr = next;
1643 01635 }
1644 01636 curlist = nextlist;
1645 01637 }
1648 01640
1649 <a name="l01641"></a><a class="code" href="Lattice_8c.html#a37">01641</a> <font class="keywordtype">int</font> <a class="code" href="Lattice_8c.html#a37">intcompare</a> (<font class="keyword">const</font> <font class="keywordtype">void</font> *a, <font class="keyword">const</font> <font class="keywordtype">void</font> *b) {
1650 01642
1652 01644
1661 01653
1662 01654 <font class="keyword">static</font> <font class="keywordtype">int</font> <a class="code" href="Lattice_8c.html#a38">polylib_sqrt</a>(<font class="keywordtype">int</font> i);
1663 <a name="l01655"></a><a class="code" href="Lattice_8c.html#a0">01655</a> <font class="keyword">static</font> <a class="code" href="structfactor.html">factor</a> <a class="code" href="Lattice_8c.html#a0">allfactors</a> (<font class="keywordtype">int</font> num) {
1664 01656
1670 01662
1671 01663 list = (<font class="keywordtype">int</font> *)malloc(<font class="keyword">sizeof</font> (<font class="keywordtype">int</font>));
1673 01665
1674 01666 tmp = num;
1675 01667 <font class="keywordflow">for</font> (i = 2; i <= <a class="code" href="Lattice_8c.html#a38">polylib_sqrt</a>(tmp); i++) {
1678 01670 list = (<font class="keywordtype">int</font> *) malloc (<font class="keyword">sizeof</font> (<font class="keywordtype">int</font>));
1681 01673 }
1683 01675 newlist = (<font class="keywordtype">int</font> *) malloc (<font class="keyword">sizeof</font> (<font class="keywordtype">int</font>) * 2 * noofelmts + 1);
1685 01677 newlist[j] = list[j] ;
1686 01678 newlist[j] = i;
1689 01681 free (list);
1690 01682 list = newlist;
1692 01684 }
1693 01685 tmp = tmp / i;
1695 01687 }
1696 01688 }
1697 01689
1699 01691 newlist = (<font class="keywordtype">int</font> *) malloc (<font class="keyword">sizeof</font> (<font class="keywordtype">int</font>) * 2 * noofelmts + 1);
1701 01693 newlist[j] = list[j] ;
1702 01694 newlist[j] = tmp;
1705 01697 free (list);
1706 01698 list = newlist;
1708 01700 }
1709 01701 qsort (list, noofelmts, <font class="keyword">sizeof</font>(<font class="keywordtype">int</font>), <a class="code" href="Lattice_8c.html#a37">intcompare</a>);
1713 01705 list[count++] = list[i];
1715 01707 count --;
1716 01708
1717 01709 result.<a class="code" href="structfactor.html#m1">fac</a> = (<font class="keywordtype">int</font> *) malloc (<font class="keyword">sizeof</font> (<font class="keywordtype">int</font>) * count);
1721 01713 free (list);
1724 01716
1725 <a name="l01717"></a><a class="code" href="Lattice_8c.html#a38">01717</a> <font class="keyword">static</font> <font class="keywordtype">int</font> <a class="code" href="Lattice_8c.html#a38">polylib_sqrt</a> (<font class="keywordtype">int</font> i) {
1726 01718
1730 01722
1735 01727 j ++;
1736 01728 }
1739 01731
1740 01732
1741 01733
1742 01734
1743 01735
1744 01736
1745 01737
1746 </pre></div><hr><address align="right"><small>Generated on Fri Nov 8 12:10:06 2002 for Polylib by
1750 </body>
1751 </html>