Annotation of OpenXM_contrib2/asir2000/engine-27/igcdhack.c, Revision 1.1.1.1
1.1 noro 1: /* $OpenXM: OpenXM/src/asir99/engine-27/igcdhack.c,v 1.1.1.1 1999/11/10 08:12:27 noro Exp $ */
2: #if 0
3: #include "base.h"
4:
5: #define SWAP(a,b,Type) { Type temp=a; a = b; b = temp; }
6: #define SIGNED_VAL(a,s) ((s)>0?(a): -(a))
7: #endif
8:
9: #undef FULLSET
10:
11:
12: static int negate_nbd( b, l )
13: int *b, l;
14: /* It is assumed that l > 0 and b[0] != 0 */
15: {
16: int i, nz;
17:
18: *b = BASE27 - *b;
19: for ( nz = i = 1 ; i < l; ) {
20: b++, i++;
21: if ( (*b ^= BMASK27) != 0 ) nz = i;
22: }
23: return nz;
24: }
25:
26: /****************/
27: /****************/
28:
29: static int abs_U_V_maxrshift( u, lu, v, lv, a )
30: int *u, lu, *v, lv, *a;
31: /*
32: * Compute | U - V | >> (as much as possible) in a[], where U = u[0:lu-1]
33: * and V = v[0:lv-1]. Value returned is the length of the result
34: * multiplied by the sign of (U-V).
35: */
36: {
37: int sign, rsh, t, b, i, l, *p = a;
38:
39: /* first, determine U <, ==, > V */
40: sign = 1;
41: if ( lu == lv ) {
42: int i;
43:
44: for ( i = lu -1; i >= 0; i-- ) {
45: if ( u[i] == v[i] ) continue;
46: lu = lv = i + 1;
47: if ( u[i] > v[i] ) goto U_V;
48: else goto swap;
49: }
50: return 0;
51: } else if ( lu > lv ) goto U_V;
52: swap:
53: SWAP( lu, lv, int ); SWAP( u, v, int * );
54: sign = -1;
55: U_V: /* U > V, i.e., (lu > lv) || (lu == lv && u[lu-1] > v[lv-1]) */
56: for ( i = 0; i < lv; i++ ) if ( u[i] != v[i] ) break;
57: if ( i != 0 ) u += i, lu -= i, v += i, lv -= i;
58: if ( lv == 0 ) { /* no more pv[], and lu > 0 */
59: i = trailingzeros_nbd( u, &rsh );
60: i = rshift_nbd( u, lu, rsh, i, a );
61: return SIGNED_VAL( i, sign );
62: }
63: /**/
64: if ( (t = u[0] - v[0]) >= 0 ) b = 0;
65: else b = 1, t += BASE27;
66: TRAILINGZEROS( t, rsh );
67: /**/
68: if ( rsh != 0 ) {
69: int w, lsh = BSH27 - rsh;
70:
71: /* subtract v[*] from u[*] */
72: for ( i = 1, l = 0; i < lv; i++, t = w >> rsh ) {
73: if ( (w = u[i] - v[i] - b) >= 0 ) b = 0;
74: else b = 1, w += BASE27;
75: if ( (*p++ = t | ((w << lsh) & BMASK27)) != 0 ) l = i;
76: }
77: /* subtraction of V completed. Note there may exist non-0 borrow b */
78: if ( i >= lu ) /* lu == lv, and b==0 is implied */ goto chk_nz;
79: /* we still have (lu-i) elms in U */
80: if ( b != 0 ) { /* non-zero borrow */
81: if ( (w = u[i++] -1) != 0 ) t |= ((w << lsh) & BMASK27);
82: if ( i >= lu ) { /* lu == lv+1. The M.S. word w may beome 0 */
83: if ( w != 0 ) {
84: *p++ = t;
85: l = lv;
86: t = w >> rsh;
87: } else lu--;
88: goto chk_nz;
89: }
90: *p++ = t;
91: if ( w < 0 ) {
92: while ( (w = u[i++]) == 0 ) *p++ = BMASK27;
93: w -= 1;
94: *p++ = (BMASK27 >> rsh) | ((w << lsh) & BMASK27);
95: }
96: t = w >> rsh;
97: }
98: for ( ; i < lu; i++, t = w >> rsh ) *p++ = t | (((w = u[i]) << lsh) & BMASK27);
99: l = i -1;
100: chk_nz:
101: if ( t != 0 ) *p = t, l = /*1 + (p - a)*/ lu;
102: goto ret_nz;
103: }
104: /* rsh == 0 : need not be right-shifted */
105: *p++ = t, l = 1;
106: for ( i = 1; i < lv; ) {
107: if ( (t = u[i] - v[i] - b) >= 0 ) b = 0;
108: else b = 1, t += BASE27;
109: i++;
110: if ( (*p++ = t) != 0 ) l = i;
111: }
112: if ( i >= lu ) /* lu == lv, and b==0 is implied */ goto ret_nz;
113: if ( b != 0 ) { /* non-zero borrow */
114: t = u[i++] -1;
115: if ( i >= lu ) /* lu == lv+1. The M.S. word w may beome 0 */ goto chk_nz;
116: if ( t < 0 ) {
117: do *p++ = BMASK27; while ( (t = u[i++]) == 0 );
118: t -= 1;
119: if ( i >= lu ) {
120: l = lu;
121: if ( t == 0 ) l--;
122: else *p = t;
123: goto ret_nz;
124: }
125: }
126: *p++ = t;
127: }
128: for ( ; i < lu; i++ ) *p++ = u[i];
129: l = lu;
130: /**/
131: ret_nz:
132: return SIGNED_VAL( l, sign );
133: }
134:
135: /****************/
136: /****************/
137:
138: #ifdef CALL
139: static int aV_plus_c(), aV_plus_c_sh();
140: #endif
141: static int abs_U_aV_c(), abs_U_aV_c_sh();
142: static int abs_aVplusc_U(), abs_aVplusc_U_sh();
143:
144: static int abs_U_aV_maxrshift( u, lu, a, v, lv, ans )
145: int *u, lu, a, *v, lv, *ans;
146: {
147: int i, t, c, rsh, l, *p = ans, w, lsh;
148: int hi;
149:
150: if ( a == 1 ) return( (l = abs_U_V_maxrshift( u, lu, v, lv, ans )) >= 0 ? l : -l );
151: /**/
152: for ( l = lu <= lv ? lu : lv, i = c = 0; i < l; ) {
153: DMA27( a, v[i], c, hi, t)
154: c = hi;
155: if ( (t -= u[i++]) != 0 ) goto non0w;
156: }
157: /**/
158: if ( i < lv ) { /* no more u[] elm.'s, and we still have non-zero v[] elm's */
159: do {
160: DMA27( a, v[i], c, hi, t)
161: i++, c = hi;
162: } while ( t == 0 );
163: TRAILINGZEROS( t, rsh );
164: v += i, lv -= i;
165: #ifdef CALL
166: if ( rsh == 0 ) {
167: *p++ = t;
168: return( aV_plus_c( a, v, lv, c, p ) + 1 );
169: } else return aV_plus_c_sh( a, v, lv, c, rsh, t, ans );
170: #else
171: i = 0;
172: if ( rsh == 0 ) {
173: *p++ = t;
174: for ( ; i < lv; i++, c = hi, *p++ = t ) { DMA27( a, v[i], c, hi, t); }
175: if ( c == 0 ) return( i + 1 );
176: *p = c;
177: return( i + 2 );
178: } else {
179: for ( lsh = BSH27 - rsh; i < lv; i++, c = hi, t = w >> rsh ) {
180: DMA27( a, v[i], c, hi, w);
181: *p++ = t | ((w << lsh) & BMASK27);
182: }
183: if ( c != 0 ) {
184: *p++ = t | ((c << lsh) & BMASK27);
185: i++;
186: t = c >> rsh;
187: }
188: if ( t == 0 ) return i;
189: *p = t;
190: return( i + 1 );
191: }
192: #endif
193: }
194: /* no more v[] elm.'s */
195: if ( i >= lu ) {
196: if ( c == 0 ) return 0;
197: c_sh:
198: while ( (c&1) == 0 ) c >>= 1;
199: *p = c;
200: return 1;
201: }
202: t = u[i++] - c;
203: if ( i >= lu ) {
204: if ( t == 0 ) return 0;
205: c = t < 0 ? -t : t;
206: goto c_sh;
207: } else if ( t == 0 ) {
208: while ( (t = u[i++]) == 0 ) ;
209: c = 0;
210: } else if ( t < 0 ) t += BASE27, c = 1;
211: else c = 0;
212: /* diff turned out to be > 0 */
213: u += i, lu -= i;
214: TRAILINGZEROS( t, rsh );
215: i = 0;
216: if ( rsh == 0 ) {
217: *p++ = t;
218: if ( c != 0 ) {
219: for ( ; i < lu; *p++ = BMASK27 ) if ( (t = u[i++]) != 0 ) break;
220: t--;
221: if ( i >= lu && t == 0 ) return i;
222: *p++ = t;
223: }
224: for ( ; i < lu; i++ ) *p++ = u[i];
225: } else { /* rsh != 0 */
226: lsh = BSH27 - rsh;
227: if ( c != 0 ) { /* there still exists u[] elms.'s because diff is known to be > 0 */
228: if ( (w = u[i++]) == 0 ) {
229: *p++ = t | ((BMASK27 << lsh) & BMASK27);
230: for ( ; (w = u[i++]) == 0; *p++ = BMASK27 ) ;
231: t = BMASK27 >> rsh;
232: }
233: w--;
234: *p++ = t | ((w << lsh) & BMASK27);
235: t = w >> rsh;
236: }
237: for ( ; i < lu; i++, t = w >> rsh ) *p++ = t | (((w = u[i]) << lsh) & BMASK27);
238: if ( t == 0 ) return( i );
239: *p = t;
240: }
241: return( i + 1 );
242: /**/
243: non0w:
244: u += i, lu -= i, v += i, lv -= i;
245: /* | t + BASE27*(c + a*v[0:lv-1] - u[0:lu-1] | */
246: if ( lv < lu ) { /* a*V < U if lv<lu-1, and very likely if lv==lu-1 */
247: t = -t; /* We shall compute U - a*V */
248: if ( t < 0 ) t += BASE27, c++;
249: } else /* a*V > U if lv>lu, and very likely even if lv==lu */
250: if ( t < 0 ) t += BASE27, c--;
251: TRAILINGZEROS( t, rsh );
252: return( rsh == 0 ? (lv < lu ? abs_U_aV_c( t, u, lu, a, v, lv, c, ans ) :
253: abs_aVplusc_U( t, a, v, lv, c, u, lu, ans )) :
254: lv < lu ? abs_U_aV_c_sh( t, u, lu, a, v, lv, c, rsh, ans ) :
255: abs_aVplusc_U_sh( t, a, v, lv, c, u, lu, rsh, ans ) );
256: }
257:
258: /*********/
259:
260: static int aV_plus_c( a, v, lv, c, p )
261: int a, *v, lv, c, *p;
262: /*
263: * Compute (a*V + c) in p[], where V = v[0:lv-1].
264: */
265: {
266: int i, t;
267: int hi;
268:
269: for ( i = 0; i < lv; i++, *p++ = t, c = hi ) { DMA27( a, v[i], c, hi, t); }
270: if ( c == 0 ) return i;
271: *p = c;
272: return( i + 1 );
273: }
274:
275: static int aV_plus_c_sh( a, v, lv, c, rsh, t, p )
276: int a, *v, lv, c, rsh, *p;
277: /*
278: * Compute (t + BASE27*((a*V + c) >> rsh)) in p[], where V = v[0:lv-1].
279: */
280: {
281: int i, w, lsh = BSH27 - rsh;
282: int hi;
283:
284: for ( i = 0; i < lv; i++, c = hi, t = w >> rsh ) {
285: DMA27( a, v[i], c, hi, w);
286: *p++ = t | ((w << lsh) & BMASK27);
287: }
288: if ( c != 0 ) {
289: *p++ = t | ((c << lsh) & BMASK27);
290: i++;
291: t = c >> rsh;
292: }
293: if ( t == 0 ) return i;
294: *p = t;
295: return( i + 1 );
296: }
297:
298: /*********/
299:
300: static int abs_aVplusc_U( t, a, v, lv, c, u, lu, ans )
301: int t, a, *v, lv, c, *u, lu, *ans;
302: /* compute | t + BASE27*(a*V+c - U) | in ans[], where V=v[0:lv-1], U=u[0:lu-1],
303: * and a > 1, -1 <= c < BASE27, lv >= lu >=0 && t != 0 are assumed.
304: */
305: {
306: int i, l, b, *p = ans;
307: int hi;
308:
309: *p++ = t, l = 1;
310: if ( c < 0 ) c = 0, b = 1;
311: else b = 0;
312: for ( i = 0; i < lu; *p++ = t ) {
313: DMA27( a, v[i], c, hi, t);
314: t -= u[i++], c = hi;
315: if ( b != 0 ) t--;
316: b = 0;
317: if ( t > 0 ) l = i + 1;
318: else if ( t < 0 ) {
319: t += BASE27, l = i + 1;
320: if ( c != 0 ) c--;
321: else b = 1;
322: }
323: }
324: /* at this point, i == lu and we have written (i+1) entries in ans[] */
325: if ( i >= lv ) { /* no more elms in v[] */
326: if ( b != 0 ) {
327: if ( i == 0 ) { ans[i] = BASE27 - t; return 1; }
328: l = negate_nbd( ans, i ); /* <================ */
329: /* if ( (t = BMASK27 ^ ans[i]) == 0 ) return l;*/
330: if ( (t ^= BMASK27) == 0 ) return l;
331: ans[i] = t;
332: return( i + 1 );
333: }
334: if ( c == 0 ) return l;
335: *p = c;
336: return( i + 2 );
337: }
338: /* diff turned out to be > 0 */
339: if ( b != 0 ) { /* c == 0 */
340: while ( (b = v[i++]) == 0 ) *p++ = BMASK27;
341: DM27( a, b, hi, t );
342: if ( t != 0 ) t--, c = hi;
343: else t = BMASK27, c = hi - 1;
344: *p++ - t;
345: }
346: #ifdef CALL
347: return( aV_plus_c( a, &v[i], lv - i, c, p ) + i +1 );
348: #else
349: for ( ; i < lv; i++, *p++ = t, c = hi ) { DMA27( a, v[i], c, hi, t);}
350: if ( c == 0 ) return( i + 1 );
351: *p = c;
352: return( i + 2 );
353: #endif
354: }
355:
356: static int abs_aVplusc_U_sh( t, a, v, lv, c, u, lu, rsh, ans )
357: int t, a, *v, lv, c, *u, lu, rsh, *ans;
358: {
359: int i, l, w, b, lsh = BSH27 - rsh, *p = ans;
360: int hi;
361:
362: if ( c < 0 ) c = 0, b = 1;
363: else b = 0;
364: for ( i = 0; i < lu; t = w >> rsh ) {
365: DMA27( a, v[i], c, hi, w);
366: w -= u[i++], c = hi;
367: if ( b != 0 ) w--;
368: b = 0;
369: if ( w < 0 ) {
370: w += BASE27;
371: if ( c != 0 ) c--;
372: else b = 1;
373: }
374: if ( (*p++ = t | ((w << lsh) & BMASK27)) != 0 ) l = i;
375: }
376: /* at this point, i == lu and we have written i entries in ans[] */
377: if ( i >= lv ) {
378: if ( b != 0 ) { /* diff turned out to be < 0 */
379: if ( i == 0 ) {
380: *p = (BASE27 >> rsh) - t;
381: return 1;
382: }
383: l = negate_nbd( ans, i ); /* <================ */
384: if ( (t ^= (BMASK27 >> rsh)) == 0 ) return l;
385: *p = t;
386: return( i + 1 );
387: }
388: if ( c == 0 ) {
389: if ( t == 0 ) return l;
390: *p = t;
391: return( i + 1 );
392: }
393: *p++ = t | ((c << lsh) & BMASK27);
394: if ( (t = c >> rsh) == 0 ) return( i + 1 );
395: *p = t;
396: return( i + 2 );
397: }
398: /* lv >= lu+1 = i+1, and diff is > 0 */
399: if ( b != 0 ) { /* c == 0 */
400: if ( (w = v[i++]) == 0 ) {
401: *p++ = t | ((BMASK27 << lsh) & BMASK27);
402: while ( (w = v[i++]) == 0 ) *p++ = BMASK27;
403: t = BMASK27 >> rsh;
404: } else {
405: DM27( a, w, c, b );
406: if ( b != 0 ) b--;
407: else b = BMASK27, c--;
408: *p++ = t | ((b << lsh) & BMASK27);
409: t = b >> rsh;
410: }
411: }
412: /**/
413: #ifdef CALL
414: return( aV_plus_c_sh( a, &v[i], lv - i, c, rsh, t, p ) + i );
415: #else
416: for ( ; i < lv; i++, t = w >> rsh, c = hi ) {
417: DMA27( a, v[i], c, hi, w);
418: *p++ = t | ((w << lsh) & BMASK27);
419: }
420: if ( c != 0 ) {
421: *p++ = t | ((c << lsh) & BMASK27);
422: i++, t = c >> rsh;
423: }
424: if ( t == 0 ) return i;
425: *p = t;
426: return( i + 1 );
427: #endif
428: }
429:
430: /*********/
431:
432: static int abs_U_aV_c( t, u, lu, a, v, lv, c, ans )
433: int t, *u, lu, a, *v, lv, c, *ans;
434: /* compute | t + BASE27*(U - a*V - c) | in ans[], where U = u[0:lu-1], V = v[0:lv-1],
435: * c is <= BASE27-1, and lu >= lv+1 && t != 0 assumed.
436: */
437: {
438: int i, w, l, *p = ans;
439: int hi;
440:
441: *p++ = t, l = 1;
442: for ( i = 0; i < lv; *p++ = t ) {
443: DMA27( a, v[i], c, hi, w);
444: t = u[i] - w;
445: i++, c = hi;
446: if ( t != 0 ) l = i + 1;
447: if ( t < 0 ) t += BASE27, c++;
448: }
449: /* at this point, i == lv */
450: if ( lu == lv+1 ) {
451: if ( (t = u[i]) == c ) return l;
452: else if ( t > c ) { *p = t - c; return( lu + 1 ); }
453: l = negate_nbd( ans, lu ); /* <================ */
454: if ( (c -= (t + 1)) == 0 ) return l;
455: *p = c;
456: return( lu + 1 );
457: }
458: /* lu >= lv+2 and the diff turned out to be >= 0 */
459: if ( c != 0 ) {
460: /* note c <= BASE27. If c == BASE27, we must care about the length of the result
461: of the case when lu == lv+2 && u[lu-2:lu-1]=u[i:i+1] == BASE27 */
462: if ( c >= BASE27 && i+2 == lu && u[i+1] == 1 ) {
463: /* m.s. word of the diff becomes 0 */
464: if ( (t = u[i] - (c & BMASK27)) == 0 ) return l;
465: *p = t;
466: return lu;
467: }
468: for ( ; 1; c = 1, *p++ = t + BASE27 ) if ( (t = u[i++] - c) >= 0 ) break;
469: if ( t == 0 && i >= lu ) return lu;
470: *p++ = t;
471: }
472: for ( ; i < lu; i++ ) *p++ = u[i];
473: return( lu + 1 );
474: }
475:
476: static int abs_U_aV_c_sh( t, u, lu, a, v, lv, c, rsh, ans )
477: int t, *u, lu, a, *v, lv, c, rsh, *ans;
478: /* r-shift version of the above */
479: {
480: int i, w, l, lsh = BSH27 - rsh, *p = ans;
481: int hi;
482:
483: for ( l = i = 0; i < lv; t = w >> rsh ) {
484: DMA27( a, v[i], c, hi, w);
485: w = u[i] - w, c = hi;
486: i++;
487: if ( w < 0 ) w += BASE27, c++;
488: if ( (*p++ = t | ((w << lsh) & BMASK27)) != 0 ) l = i;
489: }
490: /* at this point, i == lv, and we have written lv elm.s in ans[] */
491: if ( lu == lv+1 ) {
492: if ( (w = u[i] - c) == 0 ) {
493: if ( t == 0 ) return l;
494: *p = t;
495: return lu; /* == lv+1 */
496: } else if ( w > 0 ) {
497: l0: *p++ = t | ((w << lsh) & BMASK27);
498: if ( (w >>= rsh) == 0 ) return lu; /* == lv+1 */
499: *p = w;
500: return( lu + 1 );
501: }
502: /* diff turned out to be < 0 */
503: w = - w - 1;
504: if ( lv == 0 ) { /* lu == 1 */
505: t = (BASE27 >> rsh) - t;
506: if ( w != 0 ) goto l0;
507: *p = t;
508: return 1;
509: }
510: l = negate_nbd( ans, lv ); /* <================ */
511: t ^= (BMASK27 >> rsh);
512: if ( w != 0 ) goto l0;
513: if ( t == 0 ) return l;
514: *p = t;
515: return lu; /* == lv + 1 */
516: }
517: /* now, lu >= lv+2 == i+2 */
518: if ( c != 0 ) {
519: /* note c <= BASE27. If c == BASE27, we must care about the length of the result
520: of the case when lu == lv+2 && u[lu-2:lu-1]=u[i:i+1] == BASE27 */
521: if ( c >= BASE27 && i+2 == lu && t == 0 && u[i] == 0 && u[i+1] == 1 )
522: return l; /* m.s. word of the diff has become 0 */
523: for ( ; 1; t = w >> rsh, c = 1 ) {
524: if ( (w = u[i++] - c) >= 0 ) break;
525: w += BASE27;
526: *p++ = t | ((w << lsh) & BMASK27);
527: }
528: t |= ((w << lsh) & BMASK27);
529: w >>= rsh;
530: if ( i >= lu ) {
531: if ( w != 0 ) {
532: *p++ = t;
533: *p = w;
534: return( lu + 1 );
535: } else if ( t == 0 ) return( i - 1 );
536: else { *p = t; return i; }
537: }
538: *p++ = t;
539: t = w;
540: }
541: for ( ; i < lu; i++, t = w >> rsh ) *p++ = t | (((w = u[i]) << lsh) & BMASK27);
542: if ( t == 0 ) return i;
543: *p = t;
544: return( i + 1 );
545: }
546:
547: /****************/
548: /****************/
549: #ifdef FULLSET
550: static int abs_axU_V_maxrshift(), abs_axU_bxV_maxrshift();
551:
552: static int abs_aU_bV_maxrshift( a, u, lu, b, v, lv, ans )
553: int a, *u, lu, b, *v, lv, *ans;
554: /*
555: * Compute | a*U - b*V | >> (as much as possible) in ans[], where U=u[0:lu-1]
556: * and V=v[0:lv-1].
557: */
558: {
559: if ( a == 1 ) return abs_U_aV_maxrshift( u, lu, b, v, lv, ans );
560: else if ( b == 1 ) return abs_U_aV_maxrshift( v, lv, a, u, lu, ans );
561: else if ( a == b ) return abs_axU_V_maxrshift( a, u, lu, v, lv, ans );
562: return abs_axU_bxV_maxrshift( a, u, lu, b, v, lv, ans );
563: }
564:
565: static int abs_axU_V_maxrshift( a, u, lu, v, lv, ans )
566: int a, *u, lu, *v, lv, *ans;
567: /*
568: * Compute a*| U - V | >> (as much as possible) in ans[], where U=u[0:lu-1]
569: * and V=v[0:lv-1], 0 < a < 2^BASE27.
570: */
571: {
572: int i, l, b, c, t, rsh, *p = ans, lsh, w, x;
573: int hi;
574:
575: if ( lu > lv ) goto U_V;
576: else if ( lu < lv ) goto swap;
577: else {
578: for ( i = lu; i-- > 0; ) {
579: if ( u[i] == v[i] ) continue;
580: lu = lv = i + 1;
581: if ( u[i] > v[i] ) goto U_V;
582: else goto swap;
583: }
584: return 0;
585: }
586: swap:
587: SWAP( lu, lv, int ); SWAP( u, v, int * );
588: U_V:
589: for ( b = c = i = 0; i < lv; ) {
590: if ( (w = u[i] - v[i] - b) < 0 ) w += BASE27, b = 1;
591: else b = 0;
592: DMA27( a, w, c, hi, t);
593: i++, c = hi;
594: if ( t != 0 ) goto non0w;
595: }
596: while ( i < lu ) {
597: if ( (w = u[i] - b) < 0 ) w += BASE27, b = 1;
598: else b = 0;
599: DMA27( a, w, c, hi, t);
600: i++, c = hi;
601: if ( t != 0 ) goto non0w;
602: }
603: if ( b != 0 ) c -= a;
604: else if ( c == 0 ) return 0;
605: while ( (c&1) == 0 ) c >>= 1;
606: *p = c;
607: return 1;
608: /**/
609: non0w:
610: u += i, lu -= i, v += i, lv -= i;
611: TRAILINGZEROS( t, rsh );
612: i = 0;
613: if ( rsh == 0 ) {
614: *p++ = t, l = 0;
615: for ( ; i < lv; c = hi ) {
616: if ( (w = u[i] - v[i] - b) < 0 ) w += BASE27, b = 1;
617: else b = 0;
618: DMA27( a, w, c, hi, t);
619: i++;
620: if ( (*p++ = t) != 0 ) l = i;
621: }
622: for ( ; i < lu; c = hi ) {
623: if ( (w = u[i] - b) < 0 ) w += BASE27, b = 1;
624: else b = 1;
625: DMA27( a, w, c, hi, t);
626: i++;
627: if ( (*p++ = t) != 0 ) l = i;
628: }
629: if ( b != 0 ) c -= a;
630: if ( c == 0 ) return( l + 1 );
631: *p = c;
632: return( i + 2 );
633: } else {
634: for ( lsh = BSH27 - rsh, l = 0; i < lv; c = hi, t = x >> rsh ) {
635: if ( (w = u[i] - v[i] - b) < 0 ) w += BASE27, b = 1;
636: else b = 0;
637: DMA27( a, w, c, hi, x);
638: i++;
639: if ( (*p++ = t | ((x << lsh) & BMASK27)) != 0 ) l = i;
640: }
641: for ( ; i < lu; i++, c = hi, t = x >> rsh ) {
642: if ( (w = u[i] - b) < 0 ) w += BASE27, b = 1;
643: else b = 0;
644: DMA27( a, w, c, hi, x);
645: i++;
646: if ( (*p++ = t | ((x << lsh) & BMASK27)) != 0 ) l = i;
647: }
648: if ( b != 0 ) c -= a;
649: if ( c != 0 ) {
650: *p++ = t | ((c << lsh) & BMASK27);
651: i++, t = c >> rsh;
652: } else if ( t == 0 ) return l;
653: if ( t == 0 ) return( i );
654: *p = t;
655: return( i + 1 );
656: }
657: }
658: #endif /* FULLSET */
659:
660: static int abs_axU_bxV_maxrshift( a, u, lu, b, v, lv, ans )
661: int a, *u, lu, b, *v, lv, *ans;
662: /*
663: * Compute | a*U - b*V | >> (as much as possible) in ans[], where U=u[0:lu-1]
664: * and V=v[0:lv-1], 0 < a, b < 2^BASE27.
665: */
666: {
667: int i, l, c, d, s, t, w, rsh, *p = ans, lsh;
668: int hi;
669: #if 0
670: static int bw_int32();
671: #endif
672:
673: BitWidth( a, c ); BitWidth( u[lu -1], s );
674: BitWidth( b, d ); BitWidth( v[lv -1], t );
675: if ( lu < lv || lu == lv && (c + s) < (d + t) ) {
676: SWAP( a, b, int ); SWAP( lu, lv, int ); SWAP( u, v, int * );
677: }
678: for ( i = c = d = 0; i < lv; ) {
679: DMA27( a, u[i], c, hi, t); /* 0 <= c <= 2^BSH27 -2 */
680: c = hi;
681: DMA27( b, v[i], d, hi, s); /* 0 <= d <= 2^BSH27 -1 */
682: i++, d = hi;
683: if ( (t -= s) == 0 ) continue;
684: else if ( t < 0 ) {
685: t += BASE27;
686: if ( c != 0 ) c--;
687: else d++;
688: }
689: goto non0w;
690: }
691: if ( i >= lu ) { /* no more elm.'s in u[] and v[] */
692: only_c:
693: if ( (c -= d) == 0 ) return 0;
694: else if ( c < 0 ) c = -c;
695: sh_onlyc:
696: /* TRAILINGZEROS( c, rsh ); */
697: while ( (c&1) == 0 ) c >>= 1;
698: *p = c;
699: return 1;
700: }
701: /* there is at least one more elm. in u[] */
702: DMA27( a, u[i], c, hi, t);
703: i++, c = hi;
704: if ( i >= lu ) { /* in this case, diff still can be <= 0 */
705: if ( hi == 0 ) { c = t; goto only_c; }
706: if ( (t -= d) == 0 ) { c = hi; goto sh_onlyc; }
707: else if ( t < 0 ) t += BASE27, hi--;
708: TRAILINGZEROS( t, rsh );
709: if ( rsh == 0 ) *p++ = t;
710: else {
711: *p++ = t | ((hi << (BSH27 - rsh)) & BMASK27);
712: hi >>= rsh;
713: }
714: if ( hi == 0 ) return 1;
715: *p = hi;
716: return 2;
717: } /* diff turned out to be > 0 */ else if ( (t -= d) > 0 ) d = 0;
718: else if ( t < 0 ) t += BASE27, d = 1;
719: else {
720: while ( i < lu ) {
721: DMA27( a, u[i], c, hi, t);
722: i++, c = hi;
723: if ( t != 0 ) break;
724: }
725: }
726: u += i, lu -= i;
727: TRAILINGZEROS( t, rsh );
728: l = i = 0;
729: if ( rsh == 0 ) {
730: *p++ = t;
731: goto no_more_v;
732: } else goto no_more_v_sh;
733: /**/
734: non0w:
735: u += i, lu -= i, v += i, lv -= i;
736: TRAILINGZEROS( t, rsh );
737: i = 0;
738: if ( rsh == 0 ) {
739: *p++ = t, l = 0;
740: for ( ; i < lv; *p++ = t ) {
741: DMA27( a, u[i], c, hi, t);
742: c = hi;
743: DMA27( b, v[i], d, hi, s);
744: i++, d = hi;
745: if ( (t -= s) == 0 ) continue;
746: else if ( t < 0 ) {
747: t += BASE27;
748: if ( c != 0 ) c--;
749: else d++;
750: }
751: l = i;
752: }
753: no_more_v:
754: if ( i >= lu ) {
755: final_c_d:
756: if ( (c -= d) == 0 ) return( l + 1 );
757: else if ( c < 0 ) {
758: l = negate_nbd( ans, i + 1 ); /* <================ */
759: if ( (c = -c - 1) == 0 ) return l;
760: }
761: *p = c;
762: return( i + 2 );
763: }
764: /* a*u[i:lu-1] + c - d */
765: if ( c >= d ) c -= d;
766: else {
767: DMA27( a, u[i], c, hi, t);
768: if ( i+1 >= lu ) {
769: if ( hi == 0 ) { c = t; goto final_c_d; }
770: if ( (t -= d) < 0 ) t += BASE27, c = hi - 1;
771: else c = hi;
772: i++, *p++ = t;
773: goto final_c;
774: }
775: i++, c = hi;
776: if ( (t -= d) >= 0 ) *p++ = t;
777: else {
778: *p++ = t + BASE27;
779: if ( c != 0 ) c--;
780: else {
781: for ( ; i < lu; *p++ = BMASK27 ) {
782: DMA27( a, u[i], c, hi, t);
783: i++, c = hi;
784: if ( t == 0 ) continue;
785: *p++ = t - 1;
786: goto aU;
787: }
788: c--;
789: goto final_c;
790: }
791: }
792: }
793: /*** return( aV_plus_c( a, &u[i], lu - i, c, p ) + i + 1 ); ***/
794: aU:
795: for ( ; i < lu; i++, c = hi, *p++ = t ) { DMA27( a, u[i], c, hi, t); }
796: final_c:
797: if ( c == 0 ) return( i + 1 );
798: *p = c;
799: return( i + 2 );
800: } else { /* rsh != 0 */
801: for ( lsh = BSH27 - rsh; i < lv; t = w >> rsh ) {
802: DMA27( a, u[i], c, hi, w);
803: c = hi;
804: DMA27( b, v[i], d, hi, s);
805: i++, d = hi;
806: if ( (w -= s) < 0 ) {
807: w += BASE27;
808: if ( c != 0 ) c--;
809: else d++;
810: }
811: if ( (*p++ = t | ((w << lsh) & BMASK27)) != 0 ) l = i;
812: }
813: no_more_v_sh:
814: if ( i >= lu ) {
815: final_c_d_sh:
816: if ( (c -= d) == 0 )
817: if ( t == 0 ) return l;
818: else { *p = t; return( i + 1 ); }
819: else if ( c < 0 ) {
820: if ( i == 0 ) t = (BASE27 >> rsh) - t;
821: else {
822: l = negate_nbd( ans, i ); /* <================ */
823: /* t = (BASE27 >> rsh) - t;*/
824: t ^= ((BMASK27 >> rsh));
825: }
826: c = -c -1;
827: }
828: *p++ = t | ((c << lsh) & BMASK27);
829: if ( (c >>= rsh) == 0 ) return( i + 1 );
830: *p = c;
831: return( i + 2 );
832: } else if ( c >= d ) c -= d;
833: else {
834: DMA27( a, u[i], c, hi, w);
835: if ( i+1 >= lu ) {
836: if ( hi == 0 ) { c = w; goto final_c_d_sh; }
837: if ( (w -= d) < 0 ) w += BASE27, c = hi - 1;
838: else c = hi;
839: i++, *p++ = t | ((w << lsh) & BMASK27);
840: t = w >> rsh;
841: goto final_c_sh;
842: }
843: i++, c = hi;
844: if ( (w -= d) >= 0 ) { *p++ = t | ((w << lsh) & BMASK27); t = w >> rsh; }
845: else {
846: w += BASE27;
847: *p++ = t | ((w << lsh) & BMASK27);
848: t = w >> rsh;
849: if ( c != 0 ) c--;
850: else {
851: while ( i < lu ) {
852: DMA27( a, u[i], c, hi, w);
853: i++, c = hi;
854: if ( w == 0 ) {
855: *p++ = t | ((BMASK27 << lsh) & BMASK27);
856: t = BMASK27 >> rsh;
857: continue;
858: } else {
859: w--;
860: *p++ = t | ((w << lsh) & BMASK27);
861: t = w >> rsh;
862: goto aU_sh;
863: }
864: }
865: c--;
866: goto final_c_sh;
867: }
868: }
869: }
870: /*** return( aV_plus_c_sh( a, &u[i], lu - i, c, rsh, t ) + i ); ***/
871: aU_sh:
872: for ( ; i < lu; i++, c = hi, t = w >> rsh ) {
873: DMA27( a, u[i], c, hi, w);
874: *p++ = t | ((w << lsh) & BMASK27);
875: }
876: final_c_sh:
877: if ( c != 0 ) {
878: *p++ = t | ((c << lsh) & BMASK27);
879: i++, t = c >> rsh;
880: }
881: if ( t == 0 ) return i;
882: *p = t;
883: return( i + 1 );
884: }
885: }
886: /****************/
887: /****************/
888: #ifdef FULLSET
889: static int UplusV_maxrshift(), aUplusV_maxrshift(), axUplusV_maxrshift(), aUplusbV_maxrshift();
890:
891: static int aU_plus_bV_maxrshift( a, u, lu, b, v, lv, ans )
892: int a, *u, lu, b, *v, lv, *ans;
893: {
894: if ( a == 1 )
895: return( b == 1 ? UplusV_maxrshift( u, lu, v, lv, ans ) :
896: aUplusV_maxrshift( b, v, lv, u, lu, ans ) );
897: else if ( b == 1 ) return aUplusV_maxrshift( a, u, lu, v, lv, ans );
898: else if ( a == b ) return axUplusV_maxrshift( a, u, lu, v, lv, ans );
899: return aUplusbV_maxrshift( a, u, lu, b, v, lv, ans );
900: }
901:
902: static int UplusV_maxrshift( u, lu, v, lv, ans )
903: int *u, lu, *v, lv, *ans;
904: /*
905: * Compute ( (U + V) >> (as much as possible) ) in ans[], where U=u[0:lu-1],
906: * V=v[0:lv-1], and 0 < a < BASE27.
907: */
908: {
909: int i, t, c, rsh, *p = ans;
910: int hi;
911:
912: if ( lu < lv ) { SWAP( lu, lv, int ); SWAP( u, v, int * ); }
913: for ( c = i = 0; i < lv; ) {
914: t = (c += (u[i] + v[i])) & BMASK27;
915: /* 0 <= c <= 2*(2^BSH27 -1) + 1 = 2^BSH27 + (2^BSH27 -1) */
916: i++, c >>= BSH27;
917: if ( t != 0 ) goto non0w;
918: }
919: while ( i < lu ) {
920: t = (c += u[i]) & BMASK27;
921: i++, c >>= BSH27;
922: if ( t != 0 ) goto non0w;
923: }
924: *p = c;
925: return 1;
926: /**/
927: non0w:
928: u += i, lu -= i, v += i, lv -= i;
929: TRAILINGZEROS( t, rsh );
930: i = 0;
931: if ( rsh == 0 ) {
932: *p++ = t;
933: for ( ; i < lv; i++, c >>= BSH27 ) *p++ = (c += (u[i] + v[i])) & BMASK27;
934: if ( c != 0 ) {
935: while ( i < lu )
936: if ( (c = u[i++] + 1) >= BASE27 ) *p++ = c & BMASK27;
937: else {
938: *p++ = c;
939: goto cpu;
940: }
941: *p = 1; /* == c */
942: return( lu + 2 );
943: }
944: cpu:
945: for ( ; i < lu; i++ ) *p++ = u[i];
946: return( lu + 1 );
947: } else {
948: int lsh = BSH27 - rsh;
949:
950: for ( ; i < lv; i++, c >>= BSH27 ) {
951: c += (u[i] + v[i]);
952: *p++ = t | ((c << lsh) & BMASK27);
953: t = (c & BMASK27) >> rsh;
954: }
955: if ( c != 0 ) {
956: while ( i < lu ) {
957: c = u[i++] + 1;
958: *p++ = t | ((c << lsh) & BMASK27);
959: t = (c & BMASK27) >> rsh;
960: if ( (c >>= BSH27) == 0 ) goto cpu_sh;
961: }
962: *p = t | (1 << lsh);
963: return( lu + 1 );
964: }
965: cpu_sh:
966: for ( ; i < lu; t = c >> rsh ) *p++ = t | (((c = u[i++]) << lsh) & BMASK27);
967: if ( t == 0 ) return( lu );
968: *p = t;
969: return( lu + 1 );
970: }
971: }
972:
973: static int aUplusV_maxrshift( a, u, lu, v, lv, ans )
974: int a, *u, lu, *v, lv, *ans;
975: /*
976: * Compute ( (a*U + V) >> (as much as possible) ) in ans[], where U=u[0:lu-1],
977: * V=v[0:lv-1], and 1 < a < BASE27.
978: */
979: {
980: int i, l, t, c, rsh, *p = ans, w, lsh;
981: int hi;
982:
983: for ( l = lu < lv ? lu : lv, c = i = 0; i < l; ) {
984: /* Note that (carry in a*U[*]) <= 2^BSH27-2 because {(2^j-1)}^2 + (2^j-2)
985: * = 2^j*(2^j -2)+(2^j -1), and the following c is <= 2^j -1 because
986: * {(2^j -1)}^2 + (2^j -1) + (2^j -1) = 2^j*(2^j -1) + (2^j -1).
987: * ^^^^^^carry^^^^^^ pv[?].
988: */
989: c += v[i];
990: DMA27( a, u[i], c, hi, t);
991: i++, c = hi;
992: if ( t != 0 ) goto non0sum;
993: }
994: if ( i >= lu ) { /* compute (c + v[i:lv-1]) */
995: while ( i < lv ) {
996: t = (c += v[i++]) & BMASK27;
997: c >>= BSH27;
998: if ( t != 0 ) goto non0w_v;
999: }
1000: *p = 1;
1001: return 1;
1002: non0w_v:
1003: v += i, lv -= i;
1004: i = 0;
1005: TRAILINGZEROS( t, rsh );
1006: if ( rsh == 0 ) {
1007: *p++ = t;
1008: L_addv:
1009: if ( c != 0 ) {
1010: while ( i < lv )
1011: if ( (c = u[i++] + 1) >= BASE27 ) *p++ = c & BMASK27;
1012: else {
1013: *p++ = c;
1014: goto cpv;
1015: }
1016: *p = 1; /* == c */
1017: return( lv + 2 );
1018: }
1019: cpv:
1020: for ( ; i < lv; i++ ) *p++ = v[i];
1021: return( lv + 1 );
1022: } else {
1023: lsh = BSH27 - rsh;
1024: L_addv_sh:
1025: if ( c != 0 ) {
1026: while ( i < lv ) {
1027: c += v[i++];
1028: *p++ = t | ((c << lsh) & BMASK27);
1029: t = (c & BMASK27) >> rsh;
1030: if ( (c >>= BSH27) == 0 ) goto cpv_sh;
1031: }
1032: *p = t | (1 << lsh);
1033: return( lv + 1 );
1034: }
1035: cpv_sh:
1036: for ( ; i < lv; t = c >> rsh ) *p++ = t | (((c = v[i++]) << lsh) & BMASK27);
1037: if ( t == 0 ) return( lv );
1038: *p = t;
1039: return( lv + 1 );
1040: }
1041: } else { /* i >= lv, and compute (c + a*u[i:lu-1]) */
1042: while ( i < lu ) {
1043: DMA27( a, u[i], c, hi, t);
1044: i++, c = hi;
1045: if ( t != 0 ) goto non0w_u;
1046: }
1047: TRAILINGZEROS( c, rsh );
1048: *p = c;
1049: return 1;
1050: /**/
1051: non0w_u:
1052: u += i, lu -= i;
1053: TRAILINGZEROS( t, rsh );
1054: i = 0;
1055: if ( rsh == 0 ) {
1056: *p++ = t;
1057: L_addu:
1058: #ifdef CALL
1059: return( aV_plus_c( a, u, lv, c, p ) + 1 );
1060: #else
1061: for ( ; i < lu; i++, *p++ = t, c = hi ) { DMA27( a, u[i], c, hi, t); }
1062: if ( c == 0 ) return( lu + 1 );
1063: *p = c;
1064: return( lu + 2 );
1065: #endif
1066: } else {
1067: lsh = BSH27 - rsh;
1068: L_addu_sh:
1069: #ifdef CALL
1070: return aV_plus_c_sh( a, u, lu, c, rsh, t, p );
1071: #else
1072: for ( ; i < lu; i++, c = hi, t = w >> rsh ) {
1073: DMA27( a, u[i], c, hi, w);
1074: *p++ = t | ((w << lsh) & BMASK27);
1075: }
1076: if ( c != 0 ) {
1077: *p++ = t | ((c << lsh) & BMASK27);
1078: i++, t = c >> rsh;
1079: }
1080: if ( t == 0 ) return i;
1081: *p = t;
1082: return( i + 1 );
1083: #endif
1084: }
1085: }
1086: /**/
1087: non0sum:
1088: u += i, lu -= i, v += i, lv -= i, l -= i;
1089: TRAILINGZEROS( t, rsh );
1090: i = 0;
1091: if ( rsh == 0 ) {
1092: *p++ = t;
1093: for ( ; i < l; i++, *p++ = t, c = hi ) {
1094: c += v[i];
1095: DMA27( a, u[i], c, hi, t);
1096: }
1097: if ( i >= lu ) /* compute (c + v[i:lv-1]). note i may be >= lv */ goto L_addv;
1098: else /* i >= lv, and compute (c + u[i:lu-1]) */ goto L_addu;
1099: } else {
1100: lsh = BSH27 - rsh;
1101: for ( ; i < l; i++, c = hi, t = w >> rsh ) {
1102: c += v[i];
1103: DMA27( a, u[i], c, hi, w);
1104: *p++ = t | ((w << lsh) & BMASK27);
1105: }
1106: if ( i >= lu ) /* compute (c + v[i:lv-1]) >> rsh. note i may be >= lv */ goto L_addv_sh;
1107: else /* i >= lv, and compute (c + u[i:lu-1]) >> rsh */ goto L_addu_sh;
1108: }
1109: }
1110:
1111:
1112: static int axUplusV_maxrshift( a, u, lu, v, lv, ans )
1113: int a, *u, lu, *v, lv, *ans;
1114: /*
1115: * Compute ( a*(U + V) >> (as much as possible) ) in ans[], where U=u[0:lu-1],
1116: * V=v[0:lv-1], and 1 < a < BASE27.
1117: */
1118: {
1119: int i, t, c, d, rsh, w, *p = ans, lsh, x;
1120: int hi;
1121:
1122: if ( lu < lv ) { SWAP( lu, lv, int ); SWAP( u, v, int * ); }
1123: for ( i = c = d = 0; i < lv; ) {
1124: w = (d += (u[i] + v[i])) & BMASK27;
1125: DMA27( a, w, c, hi, t);
1126: i++, d >>= BSH27, c = hi;
1127: if ( t != 0 ) goto non0w;
1128: }
1129: while ( i < lu ) {
1130: w = (d += u[i++]) & BMASK27;
1131: DMA27( a, w, c, hi, t);
1132: d >>= BSH27, c = hi;
1133: if ( t != 0 ) goto non0w;
1134: }
1135: if ( d != 0 ) c += a;
1136: TRAILINGZEROS( c, rsh );
1137: if ( rsh != 0 || c <= BMASK27 ) { *p = c; return 1; }
1138: *p++ = c & BMASK27;
1139: *p = c >> BSH27;
1140: return 2;
1141: /**/
1142: non0w:
1143: u += i, lu -= i, v += i, lv -= i;
1144: TRAILINGZEROS( t, rsh );
1145: i = 0;
1146: if ( rsh == 0 ) {
1147: *p++ = t;
1148: for ( ; i < lv; i++, d >>= BSH27, *p++ = t, c = hi ) {
1149: w = (d += (u[i] + v[i])) & BMASK27;
1150: DMA27( a, w, c, hi, t);
1151: }
1152: for ( ; i < lu; d >>= BSH27, *p++ = t, c = hi ) {
1153: w = (d += u[i++]) & BMASK27;
1154: DMA27( a, w, c, hi, t);
1155: }
1156: if ( d != 0 ) c += a;
1157: if ( c == 0 ) return( lu + 1 );
1158: *p++ = c & BMASK27;
1159: if ( (c >>= BSH27) == 0 ) return( lu + 2 );
1160: *p = c;
1161: return( lu + 3 );
1162: } else {
1163: for ( lsh = BSH27 - rsh; i < lv; i++, d >>= BSH27, t = x >> rsh, c = hi ) {
1164: w = (d += (u[i] + v[i])) & BMASK27;
1165: DMA27( a, w, c, hi, x);
1166: *p++ = t | ((x << lsh) & BMASK27);
1167: }
1168: for ( ; i < lu; d >>= BSH27, t = x >> rsh, c = hi ) {
1169: w = (d += u[i++]) & BMASK27;
1170: DMA27( a, w, c, hi, x);
1171: *p++ = t | ((x << lsh) & BMASK27);
1172: }
1173: if ( d != 0 ) c += a;
1174: t |= ((c << lsh) & BMASK27);
1175: c >>= rsh;
1176: if ( c != 0 ) {
1177: *p++ = t;
1178: *p = c;
1179: return( lu + 2 );
1180: } else if ( t == 0 ) return lu;
1181: *p = t;
1182: return( lu + 1 );
1183: }
1184: }
1185: #endif /* FULLSET */
1186:
1187: static int aUplusbV_maxrshift( a, u, lu, b, v, lv, ans )
1188: int a, *u, lu, b, *v, lv, *ans;
1189: /*
1190: * Compute ( (a*U + b*V) >> (as much as possible) ) in ans[], where U=u[0:lu-1],
1191: * V=v[0:lv-1], and 0 < a,b < BASE27.
1192: */
1193: {
1194: int i, c, d, s, t, w, rsh, *p = ans, lsh;
1195: int hi;
1196:
1197: if ( lu < lv ) { SWAP( a, b, int ); SWAP( lu, lv, int ); SWAP( u, v, int * ); }
1198: for ( c = d = i = 0; i < lv; ) {
1199: DMA27( a, u[i], c, hi, t); /* 0 <= c <= 2^BSH27 -1 */
1200: c = hi;
1201: DMA27( b, v[i], d, hi, s); /* 0 <= d <= 2^BSH27 -2 */
1202: i++, d = hi, t += s;
1203: if ( t > BMASK27 ) c++, t &= BMASK27;
1204: if ( t != 0 ) goto non0w;
1205: }
1206: c += d;
1207: for ( d = 0; i < lu; ) {
1208: DMA27( a, u[i], c, hi, t);
1209: i++, c = hi;
1210: if ( t != 0 ) goto non0w;
1211: }
1212: TRAILINGZEROS( c, rsh );
1213: if ( rsh != 0 || c <= BMASK27 ) { *p = c; return 1; }
1214: *p++ = c & BMASK27;
1215: *p = 1;
1216: return 2;
1217: /**/
1218: non0w:
1219: u += i, lu -= i, v += i, lv -= i;
1220: TRAILINGZEROS( t, rsh );
1221: i = 0;
1222: if ( rsh == 0 ) {
1223: *p++ = t;
1224: for ( ; i < lv; i++, *p++ = t ) {
1225: DMA27( a, u[i], c, hi, t);
1226: c = hi;
1227: DMA27( b, v[i], d, hi, s);
1228: d = hi, t += s;
1229: if ( t > BMASK27 ) c++, t &= BMASK27;
1230: }
1231: c += d;
1232: for ( ; i < lu; i++, *p++ = t, c = hi ) {
1233: DMA27( a, u[i], c, hi, t);
1234: }
1235: if ( c == 0 ) return( lu + 1 );
1236: else if ( c <= BMASK27 ) { *p = c; return( lu + 2 ); }
1237: *p++ = c & BMASK27;
1238: *p = 1;
1239: return( lu + 3 );
1240: } else {
1241: for ( lsh = BSH27 - rsh; i < lv; i++, t = w >> rsh ) {
1242: DMA27( a, u[i], c, hi, w);
1243: c = hi;
1244: DMA27( b, v[i], d, hi, s);
1245: d = hi, w += s;
1246: if ( w > BMASK27 ) c++, w &= BMASK27;
1247: *p++ = t | ((w << lsh) & BMASK27);
1248: }
1249: c += d; /* <= 2^BSH27 + (2^BSH27 - 3) */
1250: for ( ; i < lu; i++, c = hi, t = w >> rsh ) {
1251: DMA27( a, u[i], c, hi, w);
1252: *p++ = t | ((w << lsh) & BMASK27);
1253: }
1254: if ( c == 0 ) {
1255: if ( t == 0 ) return lu;
1256: *p = t;
1257: return( lu + 1 );
1258: }
1259: *p++ = t | ((c << lsh) & BMASK27);
1260: if ( (c >>= rsh) == 0 ) return( lu + 1 );
1261: *p = c;
1262: return( lu + 2 );
1263: }
1264: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to igcdhack.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib2 / asir2000 / engine-27