libgcc.c 9.5 KB

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