text: /* ===-- udivmodti4.c - Implement __udivmodti4 -----------------------------===
   *
   *                    The LLVM Compiler Infrastructure
   *
   * This file is dual licensed under the MIT and the University of Illinois Open
   * Source Licenses. See LICENSE.TXT for details.
   *
   * ===----------------------------------------------------------------------===
   *
   * This file implements __udivmodti4 for the compiler_rt library.
   *
   * ===----------------------------------------------------------------------===
   */ 
  
  #if __x86_64
  
  #include "int_lib.h"
  
  /* Effects: if rem != 0, *rem = a % b 
   * Returns: a / b 
   */
  
  /* Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide */
  
  tu_int
  __udivmodti4(tu_int a, tu_int b, tu_int* rem)
  {
      const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT;
      const unsigned n_utword_bits = sizeof(tu_int) * CHAR_BIT;
      utwords n;
      n.all = a;
      utwords d;
      d.all = b;
      utwords q;
      utwords r;
      unsigned sr;
      /* special cases, X is unknown, K != 0 */
      if (n.s.high == 0)
      {
          if (d.s.high == 0)
          {
              /* 0 X
               * ---
               * 0 X
               */
              if (rem)
                  *rem = n.s.low % d.s.low;
              return n.s.low / d.s.low;
          }
          /* 0 X
           * ---
           * K X
           */
          if (rem)
              *rem = n.s.low;
          return 0;
      }
      /* n.s.high != 0 */
      if (d.s.low == 0)
      {
          if (d.s.high == 0)
          {
              /* K X
               * ---
               * 0 0
               */
              if (rem)
                  *rem = n.s.high % d.s.low;
              return n.s.high / d.s.low;
          }
          /* d.s.high != 0 */
          if (n.s.low == 0)
          {
              /* K 0
               * ---
               * K 0
               */
              if (rem)
              {
                  r.s.high = n.s.high % d.s.high;
                  r.s.low = 0;
                  *rem = r.all;
              }
              return n.s.high / d.s.high;
          }
          /* K K
           * ---
           * K 0
           */
          if ((d.s.high & (d.s.high - 1)) == 0)     /* if d is a power of 2 */
          {
              if (rem)
              {
                  r.s.low = n.s.low;
                  r.s.high = n.s.high & (d.s.high - 1);
                  *rem = r.all;
              }
              return n.s.high >> __builtin_ctzll(d.s.high);
          }
          /* K K
           * ---
           * K 0
           */
          sr = __builtin_clzll(d.s.high) - __builtin_clzll(n.s.high);
          /* 0 <= sr <= n_udword_bits - 2 or sr large */
          if (sr > n_udword_bits - 2)
          {
             if (rem)
                  *rem = n.all;
              return 0;
          }
          ++sr;
          /* 1 <= sr <= n_udword_bits - 1 */
          /* q.all = n.all << (n_utword_bits - sr); */
          q.s.low = 0;
          q.s.high = n.s.low << (n_udword_bits - sr);
          /* r.all = n.all >> sr; */
          r.s.high = n.s.high >> sr;
          r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
      }
      else  /* d.s.low != 0 */
      {
          if (d.s.high == 0)
          {
              /* K X
               * ---
               * 0 K
               */
              if ((d.s.low & (d.s.low - 1)) == 0)     /* if d is a power of 2 */
              {
                  if (rem)
                      *rem = n.s.low & (d.s.low - 1);
                  if (d.s.low == 1)
                      return n.all;
                  unsigned sr = __builtin_ctzll(d.s.low);
                  q.s.high = n.s.high >> sr;
                  q.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
                  return q.all;
              }
              /* K X
               * ---
               * 0 K
               */
              sr = 1 + n_udword_bits + __builtin_clzll(d.s.low)
                                     - __builtin_clzll(n.s.high);
              /* 2 <= sr <= n_utword_bits - 1
               * q.all = n.all << (n_utword_bits - sr);
               * r.all = n.all >> sr;
               * if (sr == n_udword_bits)
               * {
               *     q.s.low = 0;
               *     q.s.high = n.s.low;
               *     r.s.high = 0;
               *     r.s.low = n.s.high;
               * }
               * else if (sr < n_udword_bits)  // 2 <= sr <= n_udword_bits - 1
               * {
               *     q.s.low = 0;
               *     q.s.high = n.s.low << (n_udword_bits - sr);
               *     r.s.high = n.s.high >> sr;
               *     r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
               * }
               * else              // n_udword_bits + 1 <= sr <= n_utword_bits - 1
               * {
               *     q.s.low = n.s.low << (n_utword_bits - sr);
               *     q.s.high = (n.s.high << (n_utword_bits - sr)) |
               *              (n.s.low >> (sr - n_udword_bits));
               *     r.s.high = 0;
               *     r.s.low = n.s.high >> (sr - n_udword_bits);
               * }
               */
              q.s.low =  (n.s.low << (n_utword_bits - sr)) &
                       ((di_int)(int)(n_udword_bits - sr) >> (n_udword_bits-1));
              q.s.high = ((n.s.low << ( n_udword_bits - sr))                        &
                       ((di_int)(int)(sr - n_udword_bits - 1) >> (n_udword_bits-1))) |
                       (((n.s.high << (n_utword_bits - sr))                       |
                       (n.s.low >> (sr - n_udword_bits)))                         &
                       ((di_int)(int)(n_udword_bits - sr) >> (n_udword_bits-1)));
              r.s.high = (n.s.high >> sr) &
                       ((di_int)(int)(sr - n_udword_bits) >> (n_udword_bits-1));
              r.s.low =  ((n.s.high >> (sr - n_udword_bits))                        &
                       ((di_int)(int)(n_udword_bits - sr - 1) >> (n_udword_bits-1))) |
                       (((n.s.high << (n_udword_bits - sr))                       |
                       (n.s.low >> sr))                                           &
                       ((di_int)(int)(sr - n_udword_bits) >> (n_udword_bits-1)));
          }
          else
          {
              /* K X
               * ---
               * K K
               */
              sr = __builtin_clzll(d.s.high) - __builtin_clzll(n.s.high);
              /*0 <= sr <= n_udword_bits - 1 or sr large */
              if (sr > n_udword_bits - 1)
              {
                 if (rem)
                      *rem = n.all;
                  return 0;
              }
              ++sr;
              /* 1 <= sr <= n_udword_bits */
              /* q.all = n.all << (n_utword_bits - sr); */
              q.s.low = 0;
              q.s.high = n.s.low << (n_udword_bits - sr);
              /* r.all = n.all >> sr;
               * if (sr < n_udword_bits)
               * {
               *     r.s.high = n.s.high >> sr;
               *     r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
               * }
               * else
               * {
               *     r.s.high = 0;
               *     r.s.low = n.s.high;
               * }
               */
              r.s.high = (n.s.high >> sr) &
                       ((di_int)(int)(sr - n_udword_bits) >> (n_udword_bits-1));
              r.s.low = (n.s.high << (n_udword_bits - sr)) |
                      ((n.s.low >> sr)                   &
                      ((di_int)(int)(sr - n_udword_bits) >> (n_udword_bits-1)));
          }
      }
      /* Not a special case
       * q and r are initialized with:
       * q.all = n.all << (n_utword_bits - sr);
       * r.all = n.all >> sr;
       * 1 <= sr <= n_utword_bits - 1
       */
      su_int carry = 0;
      for (; sr > 0; --sr)
      {
          /* r:q = ((r:q)  << 1) | carry */
          r.s.high = (r.s.high << 1) | (r.s.low  >> (n_udword_bits - 1));
          r.s.low  = (r.s.low  << 1) | (q.s.high >> (n_udword_bits - 1));
          q.s.high = (q.s.high << 1) | (q.s.low  >> (n_udword_bits - 1));
          q.s.low  = (q.s.low  << 1) | carry;
          /* carry = 0;
           * if (r.all >= d.all)
           * {
           *     r.all -= d.all;
           *      carry = 1;
           * }
           */
          const ti_int s = (ti_int)(d.all - r.all - 1) >> (n_utword_bits - 1);
          carry = s & 1;
          r.all -= d.all & s;
      }
      q.all = (q.all << 1) | carry;
      if (rem)
          *rem = r.all;
      return q.all;
  }
  
  #endif /* __x86_64 */
  