udivmoddi4.c 6.5 KB

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