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