udivmodti4.c 6.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238
  1. /* ===-- udivmodti4.c - Implement __udivmodti4 -----------------------------===
  2. *
  3. * The LLVM Compiler Infrastructure
  4. *
  5. * This file is dual licensed under the MIT and the University of Illinois Open
  6. * Source Licenses. See LICENSE.TXT for details.
  7. *
  8. * ===----------------------------------------------------------------------===
  9. *
  10. * This file implements __udivmodti4 for the compiler_rt library.
  11. *
  12. * ===----------------------------------------------------------------------===
  13. */
  14. #include "int_lib.h"
  15. #ifdef CRT_HAS_128BIT
  16. /* Effects: if rem != 0, *rem = a % b
  17. * Returns: a / b
  18. */
  19. /* Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide */
  20. COMPILER_RT_ABI tu_int
  21. __udivmodti4(tu_int a, tu_int b, tu_int* rem)
  22. {
  23. const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT;
  24. const unsigned n_utword_bits = sizeof(tu_int) * CHAR_BIT;
  25. utwords n;
  26. n.all = a;
  27. utwords d;
  28. d.all = b;
  29. utwords q;
  30. utwords r;
  31. unsigned sr;
  32. /* special cases, X is unknown, K != 0 */
  33. if (n.s.high == 0)
  34. {
  35. if (d.s.high == 0)
  36. {
  37. /* 0 X
  38. * ---
  39. * 0 X
  40. */
  41. if (rem)
  42. *rem = n.s.low % d.s.low;
  43. return n.s.low / d.s.low;
  44. }
  45. /* 0 X
  46. * ---
  47. * K X
  48. */
  49. if (rem)
  50. *rem = n.s.low;
  51. return 0;
  52. }
  53. /* n.s.high != 0 */
  54. if (d.s.low == 0)
  55. {
  56. if (d.s.high == 0)
  57. {
  58. /* K X
  59. * ---
  60. * 0 0
  61. */
  62. if (rem)
  63. *rem = n.s.high % d.s.low;
  64. return n.s.high / d.s.low;
  65. }
  66. /* d.s.high != 0 */
  67. if (n.s.low == 0)
  68. {
  69. /* K 0
  70. * ---
  71. * K 0
  72. */
  73. if (rem)
  74. {
  75. r.s.high = n.s.high % d.s.high;
  76. r.s.low = 0;
  77. *rem = r.all;
  78. }
  79. return n.s.high / d.s.high;
  80. }
  81. /* K K
  82. * ---
  83. * K 0
  84. */
  85. if ((d.s.high & (d.s.high - 1)) == 0) /* if d is a power of 2 */
  86. {
  87. if (rem)
  88. {
  89. r.s.low = n.s.low;
  90. r.s.high = n.s.high & (d.s.high - 1);
  91. *rem = r.all;
  92. }
  93. return n.s.high >> __builtin_ctzll(d.s.high);
  94. }
  95. /* K K
  96. * ---
  97. * K 0
  98. */
  99. sr = __builtin_clzll(d.s.high) - __builtin_clzll(n.s.high);
  100. /* 0 <= sr <= n_udword_bits - 2 or sr large */
  101. if (sr > n_udword_bits - 2)
  102. {
  103. if (rem)
  104. *rem = n.all;
  105. return 0;
  106. }
  107. ++sr;
  108. /* 1 <= sr <= n_udword_bits - 1 */
  109. /* q.all = n.all << (n_utword_bits - sr); */
  110. q.s.low = 0;
  111. q.s.high = n.s.low << (n_udword_bits - sr);
  112. /* r.all = n.all >> sr; */
  113. r.s.high = n.s.high >> sr;
  114. r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
  115. }
  116. else /* d.s.low != 0 */
  117. {
  118. if (d.s.high == 0)
  119. {
  120. /* K X
  121. * ---
  122. * 0 K
  123. */
  124. if ((d.s.low & (d.s.low - 1)) == 0) /* if d is a power of 2 */
  125. {
  126. if (rem)
  127. *rem = n.s.low & (d.s.low - 1);
  128. if (d.s.low == 1)
  129. return n.all;
  130. sr = __builtin_ctzll(d.s.low);
  131. q.s.high = n.s.high >> sr;
  132. q.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
  133. return q.all;
  134. }
  135. /* K X
  136. * ---
  137. * 0 K
  138. */
  139. sr = 1 + n_udword_bits + __builtin_clzll(d.s.low)
  140. - __builtin_clzll(n.s.high);
  141. /* 2 <= sr <= n_utword_bits - 1
  142. * q.all = n.all << (n_utword_bits - sr);
  143. * r.all = n.all >> sr;
  144. */
  145. if (sr == n_udword_bits)
  146. {
  147. q.s.low = 0;
  148. q.s.high = n.s.low;
  149. r.s.high = 0;
  150. r.s.low = n.s.high;
  151. }
  152. else if (sr < n_udword_bits) // 2 <= sr <= n_udword_bits - 1
  153. {
  154. q.s.low = 0;
  155. q.s.high = n.s.low << (n_udword_bits - sr);
  156. r.s.high = n.s.high >> sr;
  157. r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
  158. }
  159. else // n_udword_bits + 1 <= sr <= n_utword_bits - 1
  160. {
  161. q.s.low = n.s.low << (n_utword_bits - sr);
  162. q.s.high = (n.s.high << (n_utword_bits - sr)) |
  163. (n.s.low >> (sr - n_udword_bits));
  164. r.s.high = 0;
  165. r.s.low = n.s.high >> (sr - n_udword_bits);
  166. }
  167. }
  168. else
  169. {
  170. /* K X
  171. * ---
  172. * K K
  173. */
  174. sr = __builtin_clzll(d.s.high) - __builtin_clzll(n.s.high);
  175. /*0 <= sr <= n_udword_bits - 1 or sr large */
  176. if (sr > n_udword_bits - 1)
  177. {
  178. if (rem)
  179. *rem = n.all;
  180. return 0;
  181. }
  182. ++sr;
  183. /* 1 <= sr <= n_udword_bits
  184. * q.all = n.all << (n_utword_bits - sr);
  185. * r.all = n.all >> sr;
  186. */
  187. q.s.low = 0;
  188. if (sr == n_udword_bits)
  189. {
  190. q.s.high = n.s.low;
  191. r.s.high = 0;
  192. r.s.low = n.s.high;
  193. }
  194. else
  195. {
  196. r.s.high = n.s.high >> sr;
  197. r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
  198. q.s.high = n.s.low << (n_udword_bits - sr);
  199. }
  200. }
  201. }
  202. /* Not a special case
  203. * q and r are initialized with:
  204. * q.all = n.all << (n_utword_bits - sr);
  205. * r.all = n.all >> sr;
  206. * 1 <= sr <= n_utword_bits - 1
  207. */
  208. su_int carry = 0;
  209. for (; sr > 0; --sr)
  210. {
  211. /* r:q = ((r:q) << 1) | carry */
  212. r.s.high = (r.s.high << 1) | (r.s.low >> (n_udword_bits - 1));
  213. r.s.low = (r.s.low << 1) | (q.s.high >> (n_udword_bits - 1));
  214. q.s.high = (q.s.high << 1) | (q.s.low >> (n_udword_bits - 1));
  215. q.s.low = (q.s.low << 1) | carry;
  216. /* carry = 0;
  217. * if (r.all >= d.all)
  218. * {
  219. * r.all -= d.all;
  220. * carry = 1;
  221. * }
  222. */
  223. const ti_int s = (ti_int)(d.all - r.all - 1) >> (n_utword_bits - 1);
  224. carry = s & 1;
  225. r.all -= d.all & s;
  226. }
  227. q.all = (q.all << 1) | carry;
  228. if (rem)
  229. *rem = r.all;
  230. return q.all;
  231. }
  232. #endif /* CRT_HAS_128BIT */