udivsi3.c 1.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566
  1. /* ===-- udivsi3.c - Implement __udivsi3 -----------------------------------===
  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 __udivsi3 for the compiler_rt library.
  11. *
  12. * ===----------------------------------------------------------------------===
  13. */
  14. #include "int_lib.h"
  15. /* Returns: a / b */
  16. /* Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide */
  17. ARM_EABI_FNALIAS(uidiv, udivsi3)
  18. /* This function should not call __divsi3! */
  19. COMPILER_RT_ABI su_int
  20. __udivsi3(su_int n, su_int d)
  21. {
  22. const unsigned n_uword_bits = sizeof(su_int) * CHAR_BIT;
  23. su_int q;
  24. su_int r;
  25. unsigned sr;
  26. /* special cases */
  27. if (d == 0)
  28. return 0; /* ?! */
  29. if (n == 0)
  30. return 0;
  31. sr = __builtin_clz(d) - __builtin_clz(n);
  32. /* 0 <= sr <= n_uword_bits - 1 or sr large */
  33. if (sr > n_uword_bits - 1) /* d > r */
  34. return 0;
  35. if (sr == n_uword_bits - 1) /* d == 1 */
  36. return n;
  37. ++sr;
  38. /* 1 <= sr <= n_uword_bits - 1 */
  39. /* Not a special case */
  40. q = n << (n_uword_bits - sr);
  41. r = n >> sr;
  42. su_int carry = 0;
  43. for (; sr > 0; --sr)
  44. {
  45. /* r:q = ((r:q) << 1) | carry */
  46. r = (r << 1) | (q >> (n_uword_bits - 1));
  47. q = (q << 1) | carry;
  48. /* carry = 0;
  49. * if (r.all >= d.all)
  50. * {
  51. * r.all -= d.all;
  52. * carry = 1;
  53. * }
  54. */
  55. const si_int s = (si_int)(d - r - 1) >> (n_uword_bits - 1);
  56. carry = s & 1;
  57. r -= d & s;
  58. }
  59. q = (q << 1) | carry;
  60. return q;
  61. }