1 /* 2 * This file is part of GNU CC. 3 * 4 * GNU CC is free software; you can redistribute it and/or modify 5 * it under the terms of the GNU General Public License as published 6 * by the Free Software Foundation; either version 2, or (at your 7 * option) any later version. 8 * 9 * GNU CC is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public 15 * License along with GNU CC; see the file COPYING. If not, write 16 * to the Free Software Foundation, 59 Temple Place - Suite 330, 17 * Boston, MA 02111-1307, USA. 18 */ 19 20 typedef unsigned int UWtype; 21 typedef unsigned int UHWtype; 22 typedef unsigned long long UDWtype; 23 #define W_TYPE_SIZE 32 24 25 typedef unsigned char UQItype; 26 typedef long SItype; 27 typedef unsigned long USItype; 28 typedef long long DItype; 29 typedef unsigned long long DSItype; 30 31 #include "longlong.h" 32 33 34 typedef int word_type; 35 typedef long Wtype; 36 typedef long long DWtype; 37 38 struct DWstruct { Wtype low, high;}; 39 40 typedef union 41 { 42 struct DWstruct s; 43 DWtype ll; 44 } DWunion; 45 46 #define BITS_PER_UNIT 8 47 48 UDWtype 49 __udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp); 50 51 const UQItype __clz_tab[256] = 52 { 53 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, 54 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, 55 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 56 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 57 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 58 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 59 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 60 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8 61 }; 62 63 64 DWtype 65 __ashldi3 (DWtype u, word_type b) 66 { 67 if (b == 0) 68 return u; 69 70 const DWunion uu = {.ll = u}; 71 const word_type bm = (sizeof (Wtype) * BITS_PER_UNIT) - b; 72 DWunion w; 73 74 if (bm <= 0) 75 { 76 w.s.low = 0; 77 w.s.high = (UWtype) uu.s.low << -bm; 78 } 79 else 80 { 81 const UWtype carries = (UWtype) uu.s.low >> bm; 82 83 w.s.low = (UWtype) uu.s.low << b; 84 w.s.high = ((UWtype) uu.s.high << b) | carries; 85 } 86 87 return w.ll; 88 } 89 90 DWtype 91 __ashrdi3 (DWtype u, word_type b) 92 { 93 if (b == 0) 94 return u; 95 96 const DWunion uu = {.ll = u}; 97 const word_type bm = (sizeof (Wtype) * BITS_PER_UNIT) - b; 98 DWunion w; 99 100 if (bm <= 0) 101 { 102 /* w.s.high = 1..1 or 0..0 */ 103 w.s.high = uu.s.high >> (sizeof (Wtype) * BITS_PER_UNIT - 1); 104 w.s.low = uu.s.high >> -bm; 105 } 106 else 107 { 108 const UWtype carries = (UWtype) uu.s.high << bm; 109 110 w.s.high = uu.s.high >> b; 111 w.s.low = ((UWtype) uu.s.low >> b) | carries; 112 } 113 114 return w.ll; 115 } 116 117 DWtype 118 __lshrdi3 (DWtype u, word_type b) 119 { 120 if (b == 0) 121 return u; 122 123 const DWunion uu = {.ll = u}; 124 const word_type bm = (sizeof (Wtype) * BITS_PER_UNIT) - b; 125 DWunion w; 126 127 if (bm <= 0) 128 { 129 w.s.high = 0; 130 w.s.low = (UWtype) uu.s.high >> -bm; 131 } 132 else 133 { 134 const UWtype carries = (UWtype) uu.s.high << bm; 135 136 w.s.high = (UWtype) uu.s.high >> b; 137 w.s.low = ((UWtype) uu.s.low >> b) | carries; 138 } 139 140 return w.ll; 141 } 142 143 word_type 144 __cmpdi2 (DWtype a, DWtype b) 145 { 146 const DWunion au = {.ll = a}; 147 const DWunion bu = {.ll = b}; 148 149 if (au.s.high < bu.s.high) 150 return 0; 151 else if (au.s.high > bu.s.high) 152 return 2; 153 if ((UWtype) au.s.low < (UWtype) bu.s.low) 154 return 0; 155 else if ((UWtype) au.s.low > (UWtype) bu.s.low) 156 return 2; 157 return 1; 158 } 159 160 UDWtype 161 __udivmoddi4 (UDWtype n, UDWtype d, UDWtype *rp) 162 { 163 const DWunion nn = {.ll = n}; 164 const DWunion dd = {.ll = d}; 165 DWunion rr; 166 UWtype d0, d1, n0, n1, n2; 167 UWtype q0, q1; 168 UWtype b, bm; 169 170 d0 = dd.s.low; 171 d1 = dd.s.high; 172 n0 = nn.s.low; 173 n1 = nn.s.high; 174 175 #if !UDIV_NEEDS_NORMALIZATION 176 if (d1 == 0) 177 { 178 if (d0 > n1) 179 { 180 /* 0q = nn / 0D */ 181 182 udiv_qrnnd (q0, n0, n1, n0, d0); 183 q1 = 0; 184 185 /* Remainder in n0. */ 186 } 187 else 188 { 189 /* qq = NN / 0d */ 190 191 if (d0 == 0) 192 d0 = 1 / d0; /* Divide intentionally by zero. */ 193 194 udiv_qrnnd (q1, n1, 0, n1, d0); 195 udiv_qrnnd (q0, n0, n1, n0, d0); 196 197 /* Remainder in n0. */ 198 } 199 200 if (rp != 0) 201 { 202 rr.s.low = n0; 203 rr.s.high = 0; 204 *rp = rr.ll; 205 } 206 } 207 208 #else /* UDIV_NEEDS_NORMALIZATION */ 209 210 if (d1 == 0) 211 { 212 if (d0 > n1) 213 { 214 /* 0q = nn / 0D */ 215 216 count_leading_zeros (bm, d0); 217 218 if (bm != 0) 219 { 220 /* Normalize, i.e. make the most significant bit of the 221 denominator set. */ 222 223 d0 = d0 << bm; 224 n1 = (n1 << bm) | (n0 >> (W_TYPE_SIZE - bm)); 225 n0 = n0 << bm; 226 } 227 228 udiv_qrnnd (q0, n0, n1, n0, d0); 229 q1 = 0; 230 231 /* Remainder in n0 >> bm. */ 232 } 233 else 234 { 235 /* qq = NN / 0d */ 236 237 if (d0 == 0) 238 d0 = 1 / d0; /* Divide intentionally by zero. */ 239 240 count_leading_zeros (bm, d0); 241 242 if (bm == 0) 243 { 244 /* From (n1 >= d0) /\ (the most significant bit of d0 is set), 245 conclude (the most significant bit of n1 is set) /\ (the 246 leading quotient digit q1 = 1). 247 248 This special case is necessary, not an optimization. 249 (Shifts counts of W_TYPE_SIZE are undefined.) */ 250 251 n1 -= d0; 252 q1 = 1; 253 } 254 else 255 { 256 /* Normalize. */ 257 258 b = W_TYPE_SIZE - bm; 259 260 d0 = d0 << bm; 261 n2 = n1 >> b; 262 n1 = (n1 << bm) | (n0 >> b); 263 n0 = n0 << bm; 264 265 udiv_qrnnd (q1, n1, n2, n1, d0); 266 } 267 268 /* n1 != d0... */ 269 270 udiv_qrnnd (q0, n0, n1, n0, d0); 271 272 /* Remainder in n0 >> bm. */ 273 } 274 275 if (rp != 0) 276 { 277 rr.s.low = n0 >> bm; 278 rr.s.high = 0; 279 *rp = rr.ll; 280 } 281 } 282 #endif /* UDIV_NEEDS_NORMALIZATION */ 283 284 else 285 { 286 if (d1 > n1) 287 { 288 /* 00 = nn / DD */ 289 290 q0 = 0; 291 q1 = 0; 292 293 /* Remainder in n1n0. */ 294 if (rp != 0) 295 { 296 rr.s.low = n0; 297 rr.s.high = n1; 298 *rp = rr.ll; 299 } 300 } 301 else 302 { 303 /* 0q = NN / dd */ 304 305 count_leading_zeros (bm, d1); 306 if (bm == 0) 307 { 308 /* From (n1 >= d1) /\ (the most significant bit of d1 is set), 309 conclude (the most significant bit of n1 is set) /\ (the 310 quotient digit q0 = 0 or 1). 311 312 This special case is necessary, not an optimization. */ 313 314 /* The condition on the next line takes advantage of that 315 n1 >= d1 (true due to program flow). */ 316 if (n1 > d1 || n0 >= d0) 317 { 318 q0 = 1; 319 sub_ddmmss (n1, n0, n1, n0, d1, d0); 320 } 321 else 322 q0 = 0; 323 324 q1 = 0; 325 326 if (rp != 0) 327 { 328 rr.s.low = n0; 329 rr.s.high = n1; 330 *rp = rr.ll; 331 } 332 } 333 else 334 { 335 UWtype m1, m0; 336 /* Normalize. */ 337 338 b = W_TYPE_SIZE - bm; 339 340 d1 = (d1 << bm) | (d0 >> b); 341 d0 = d0 << bm; 342 n2 = n1 >> b; 343 n1 = (n1 << bm) | (n0 >> b); 344 n0 = n0 << bm; 345 346 udiv_qrnnd (q0, n1, n2, n1, d1); 347 umul_ppmm (m1, m0, q0, d0); 348 349 if (m1 > n1 || (m1 == n1 && m0 > n0)) 350 { 351 q0--; 352 sub_ddmmss (m1, m0, m1, m0, d1, d0); 353 } 354 355 q1 = 0; 356 357 /* Remainder in (n1n0 - m1m0) >> bm. */ 358 if (rp != 0) 359 { 360 sub_ddmmss (n1, n0, n1, n0, m1, m0); 361 rr.s.low = (n1 << b) | (n0 >> bm); 362 rr.s.high = n1 >> bm; 363 *rp = rr.ll; 364 } 365 } 366 } 367 } 368 369 const DWunion ww = {{.low = q0, .high = q1}}; 370 return ww.ll; 371 } 372 373 DWtype 374 __divdi3 (DWtype u, DWtype v) 375 { 376 word_type c = 0; 377 DWunion uu = {.ll = u}; 378 DWunion vv = {.ll = v}; 379 DWtype w; 380 381 if (uu.s.high < 0) 382 c = ~c, 383 uu.ll = -uu.ll; 384 if (vv.s.high < 0) 385 c = ~c, 386 vv.ll = -vv.ll; 387 388 w = __udivmoddi4 (uu.ll, vv.ll, (UDWtype *) 0); 389 if (c) 390 w = -w; 391 392 return w; 393 } 394 395 DWtype 396 __negdi2 (DWtype u) 397 { 398 const DWunion uu = {.ll = u}; 399 const DWunion w = { {.low = -uu.s.low, 400 .high = -uu.s.high - ((UWtype) -uu.s.low > 0) } }; 401 402 return w.ll; 403 } 404 405 406 DWtype 407 __muldi3 (DWtype u, DWtype v) 408 { 409 const DWunion uu = {.ll = u}; 410 const DWunion vv = {.ll = v}; 411 DWunion w = {.ll = __umulsidi3 (uu.s.low, vv.s.low)}; 412 413 w.s.high += ((UWtype) uu.s.low * (UWtype) vv.s.high 414 + (UWtype) uu.s.high * (UWtype) vv.s.low); 415 416 return w.ll; 417 } 418 419 DWtype 420 __moddi3 (DWtype u, DWtype v) 421 { 422 word_type c = 0; 423 DWunion uu = {.ll = u}; 424 DWunion vv = {.ll = v}; 425 DWtype w; 426 427 if (uu.s.high < 0) 428 c = ~c, 429 uu.ll = -uu.ll; 430 if (vv.s.high < 0) 431 vv.ll = -vv.ll; 432 433 (void) __udivmoddi4 (uu.ll, vv.ll, (UDWtype*)&w); 434 if (c) 435 w = -w; 436 437 return w; 438 } 439 440 word_type 441 __ucmpdi2 (DWtype a, DWtype b) 442 { 443 const DWunion au = {.ll = a}; 444 const DWunion bu = {.ll = b}; 445 446 if ((UWtype) au.s.high < (UWtype) bu.s.high) 447 return 0; 448 else if ((UWtype) au.s.high > (UWtype) bu.s.high) 449 return 2; 450 if ((UWtype) au.s.low < (UWtype) bu.s.low) 451 return 0; 452 else if ((UWtype) au.s.low > (UWtype) bu.s.low) 453 return 2; 454 return 1; 455 } 456 457 458 UDWtype 459 __udivdi3 (UDWtype n, UDWtype d) 460 { 461 return __udivmoddi4 (n, d, (UDWtype *) 0); 462 } 463 464 UDWtype 465 __umoddi3 (UDWtype u, UDWtype v) 466 { 467 UDWtype w; 468 (void) __udivmoddi4 (u, v, &w); 469 470 return w; 471 } 472 473 static USItype 474 udivmodsi4(USItype num, USItype den, word_type modwanted) 475 { 476 USItype bit = 1; 477 USItype res = 0; 478 479 while (den < num && bit && !(den & (1L<<31))) 480 { 481 den <<=1; 482 bit <<=1; 483 } 484 while (bit) 485 { 486 if (num >= den) 487 { 488 num -= den; 489 res |= bit; 490 } 491 bit >>=1; 492 den >>=1; 493 } 494 if (modwanted) return num; 495 return res; 496 } 497 498 SItype 499 __divsi3 (SItype a, SItype b) 500 { 501 word_type neg = 0; 502 SItype res; 503 504 if (a < 0) 505 { 506 a = -a; 507 neg = !neg; 508 } 509 510 if (b < 0) 511 { 512 b = -b; 513 neg = !neg; 514 } 515 516 res = udivmodsi4 (a, b, 0); 517 518 if (neg) 519 res = -res; 520 521 return res; 522 } 523 524 525 SItype 526 __udivsi3 (SItype a, SItype b) 527 { 528 return udivmodsi4 (a, b, 0); 529 } 530 531 532 SItype 533 __modsi3 (SItype a, SItype b) 534 { 535 word_type neg = 0; 536 SItype res; 537 538 if (a < 0) 539 { 540 a = -a; 541 neg = 1; 542 } 543 544 if (b < 0) 545 b = -b; 546 547 res = udivmodsi4 (a, b, 1); 548 549 if (neg) 550 res = -res; 551 552 return res; 553 } 554 555 SItype 556 __mulsi3 (SItype a, SItype b) 557 { 558 SItype res = 0; 559 USItype cnt = a; 560 561 while (cnt) 562 { 563 if (cnt & 1) 564 { 565 res += b; 566 } 567 b <<= 1; 568 cnt >>= 1; 569 } 570 571 return res; 572 } 573 574 SItype 575 __umodsi3 (SItype a, SItype b) 576 577 { 578 return udivmodsi4 (a, b, 1); 579 } 580 581 int 582 __gcc_bcmp (const unsigned char *s1, const unsigned char *s2, unsigned long size) 583 { 584 while (size > 0) 585 { 586 const unsigned char c1 = *s1++, c2 = *s2++; 587 if (c1 != c2) 588 return c1 - c2; 589 size--; 590 } 591 return 0; 592 } 593