libgcc.c 9.5 KB

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