Annotation of OpenXM_contrib2/asir2000/engine-27/igcdhack.c, Revision 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