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