libgcc2.c 3.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235
  1. // SPDX-License-Identifier: GPL-2.0+
  2. /*
  3. * Copyright (C) 1989-2013 Free Software Foundation, Inc.
  4. */
  5. #include "libgcc2.h"
  6. DWtype
  7. __ashldi3(DWtype u, shift_count_type b)
  8. {
  9. if (b == 0)
  10. return u;
  11. const DWunion uu = {.ll = u};
  12. const shift_count_type bm = W_TYPE_SIZE - b;
  13. DWunion w;
  14. if (bm <= 0) {
  15. w.s.low = 0;
  16. w.s.high = (UWtype)uu.s.low << -bm;
  17. } else {
  18. const UWtype carries = (UWtype) uu.s.low >> bm;
  19. w.s.low = (UWtype)uu.s.low << b;
  20. w.s.high = ((UWtype)uu.s.high << b) | carries;
  21. }
  22. return w.ll;
  23. }
  24. DWtype
  25. __ashrdi3(DWtype u, shift_count_type b)
  26. {
  27. if (b == 0)
  28. return u;
  29. const DWunion uu = {.ll = u};
  30. const shift_count_type bm = W_TYPE_SIZE - b;
  31. DWunion w;
  32. if (bm <= 0) {
  33. /* w.s.high = 1..1 or 0..0 */
  34. w.s.high = uu.s.high >> (W_TYPE_SIZE - 1);
  35. w.s.low = uu.s.high >> -bm;
  36. } else {
  37. const UWtype carries = (UWtype) uu.s.high << bm;
  38. w.s.high = uu.s.high >> b;
  39. w.s.low = ((UWtype)uu.s.low >> b) | carries;
  40. }
  41. return w.ll;
  42. }
  43. DWtype
  44. __lshrdi3(DWtype u, shift_count_type b)
  45. {
  46. if (b == 0)
  47. return u;
  48. const DWunion uu = {.ll = u};
  49. const shift_count_type bm = W_TYPE_SIZE - b;
  50. DWunion w;
  51. if (bm <= 0) {
  52. w.s.high = 0;
  53. w.s.low = (UWtype)uu.s.high >> -bm;
  54. } else {
  55. const UWtype carries = (UWtype)uu.s.high << bm;
  56. w.s.high = (UWtype)uu.s.high >> b;
  57. w.s.low = ((UWtype)uu.s.low >> b) | carries;
  58. }
  59. return w.ll;
  60. }
  61. unsigned long
  62. udivmodsi4(unsigned long num, unsigned long den, int modwanted)
  63. {
  64. unsigned long bit = 1;
  65. unsigned long res = 0;
  66. while (den < num && bit && !(den & (1L<<31))) {
  67. den <<= 1;
  68. bit <<= 1;
  69. }
  70. while (bit) {
  71. if (num >= den) {
  72. num -= den;
  73. res |= bit;
  74. }
  75. bit >>= 1;
  76. den >>= 1;
  77. }
  78. if (modwanted)
  79. return num;
  80. return res;
  81. }
  82. long
  83. __divsi3(long a, long b)
  84. {
  85. int neg = 0;
  86. long res;
  87. if (a < 0) {
  88. a = -a;
  89. neg = !neg;
  90. }
  91. if (b < 0) {
  92. b = -b;
  93. neg = !neg;
  94. }
  95. res = udivmodsi4(a, b, 0);
  96. if (neg)
  97. res = -res;
  98. return res;
  99. }
  100. long
  101. __modsi3(long a, long b)
  102. {
  103. int neg = 0;
  104. long res;
  105. if (a < 0) {
  106. a = -a;
  107. neg = 1;
  108. }
  109. if (b < 0)
  110. b = -b;
  111. res = udivmodsi4(a, b, 1);
  112. if (neg)
  113. res = -res;
  114. return res;
  115. }
  116. long
  117. __udivsi3(long a, long b)
  118. {
  119. return udivmodsi4(a, b, 0);
  120. }
  121. long
  122. __umodsi3(long a, long b)
  123. {
  124. return udivmodsi4(a, b, 1);
  125. }
  126. UDWtype
  127. __udivmoddi4(UDWtype n, UDWtype d, UDWtype *rp)
  128. {
  129. UDWtype q = 0, r = n, y = d;
  130. UWtype lz1, lz2, i, k;
  131. /*
  132. * Implements align divisor shift dividend method. This algorithm
  133. * aligns the divisor under the dividend and then perform number of
  134. * test-subtract iterations which shift the dividend left. Number of
  135. * iterations is k + 1 where k is the number of bit positions the
  136. * divisor must be shifted left to align it under the dividend.
  137. * quotient bits can be saved in the rightmost positions of the
  138. * dividend as it shifts left on each test-subtract iteration.
  139. */
  140. if (y <= r) {
  141. lz1 = __builtin_clzll(d);
  142. lz2 = __builtin_clzll(n);
  143. k = lz1 - lz2;
  144. y = (y << k);
  145. /*
  146. * Dividend can exceed 2 ^ (width - 1) - 1 but still be less
  147. * than the aligned divisor. Normal iteration can drops the
  148. * high order bit of the dividend. Therefore, first
  149. * test-subtract iteration is a special case, saving its
  150. * quotient bit in a separate location and not shifting
  151. * the dividend.
  152. */
  153. if (r >= y) {
  154. r = r - y;
  155. q = (1ULL << k);
  156. }
  157. if (k > 0) {
  158. y = y >> 1;
  159. /*
  160. * k additional iterations where k regular test
  161. * subtract shift dividend iterations are done.
  162. */
  163. i = k;
  164. do {
  165. if (r >= y)
  166. r = ((r - y) << 1) + 1;
  167. else
  168. r = (r << 1);
  169. i = i - 1;
  170. } while (i != 0);
  171. /*
  172. * First quotient bit is combined with the quotient
  173. * bits resulting from the k regular iterations.
  174. */
  175. q = q + r;
  176. r = r >> k;
  177. q = q - (r << k);
  178. }
  179. }
  180. if (rp)
  181. *rp = r;
  182. return q;
  183. }
  184. UDWtype
  185. __udivdi3(UDWtype n, UDWtype d)
  186. {
  187. return __udivmoddi4(n, d, (UDWtype *)0);
  188. }