pintos-os.org Git - pintos-anon/blob - src/lib/arithmetic.c

   1 #include <stdint.h>
   2
   3 /* On x86, division of one 64-bit integer by another cannot be
   4    done with a single instruction or a short sequence.  Thus, GCC
   5    implements 64-bit division and remainder operations through
   6    function calls.  These functions are normally obtained from
   7    libgcc, which is automatically included by GCC in any link
   8    that it does.
   9
  10    Some x86-64 machines, however, have a compiler and utilities
  11    that can generate 32-bit x86 code without having any of the
  12    necessary libraries, including libgcc.  Thus, we can make
  13    Pintos work on these machines by simply implementing our own
  14    64-bit division routines, which are the only routines from
  15    libgcc that Pintos requires.
  16
  17    Completeness is another reason to include these routines.  If
  18    Pintos is completely self-contained, then that makes it that
  19    much less mysterious. */
  20
  21 /* Uses x86 DIVL instruction to divide 64-bit N by 32-bit D to
  22    yield a 32-bit quotient.  Returns the quotient.
  23    Traps with a divide error (#DE) if the quotient does not fit
  24    in 32 bits. */
  25 static inline uint32_t
  26 divl (uint64_t n, uint32_t d)
  27 {
  28   uint32_t n1 = n >> 32;
  29   uint32_t n0 = n;
  30   uint32_t q, r;
  31
  32   asm ("divl %4"
  33        : "=d" (r), "=a" (q)
  34        : "0" (n1), "1" (n0), "rm" (d));
  35
  36   return q;
  37 }
  38
  39 /* Returns the number of leading zero bits in X,
  40    which must be nonzero. */
  41 static int
  42 nlz (uint32_t x)
  43 {
  44   /* This technique is portable, but there are better ways to do
  45      it on particular systems.  With sufficiently new enough GCC,
  46      you can use __builtin_clz() to take advantage of GCC's
  47      knowledge of how to do it.  Or you can use the x86 BSR
  48      instruction directly. */
  49   int n = 0;
  50   if (x <= 0x0000FFFF)
  51     {
  52       n += 16;
  53       x <<= 16;
  54     }
  55   if (x <= 0x00FFFFFF)
  56     {
  57       n += 8;
  58       x <<= 8;
  59     }
  60   if (x <= 0x0FFFFFFF)
  61     {
  62       n += 4;
  63       x <<= 4;
  64     }
  65   if (x <= 0x3FFFFFFF)
  66     {
  67       n += 2;
  68       x <<= 2;
  69     }
  70   if (x <= 0x7FFFFFFF)
  71     n++;
  72   return n;
  73 }
  74
  75 /* Divides unsigned 64-bit N by unsigned 64-bit D and returns the
  76    quotient. */
  77 static uint64_t
  78 udiv64 (uint64_t n, uint64_t d)
  79 {
  80   if ((d >> 32) == 0)
  81     {
  82       /* Proof of correctness:
  83
  84          Let n, d, b, n1, and n0 be defined as in this function.
  85          Let [x] be the "floor" of x.  Let T = b[n1/d].  Assume d
  86          nonzero.  Then:
  87              [n/d] = [n/d] - T + T
  88                    = [n/d - T] + T                         by (1) below
  89                    = [(b*n1 + n0)/d - T] + T               by definition of n
  90                    = [(b*n1 + n0)/d - dT/d] + T
  91                    = [(b(n1 - d[n1/d]) + n0)/d] + T
  92                    = [(b[n1 % d] + n0)/d] + T,             by definition of %
  93          which is the expression calculated below.
  94
  95          (1) Note that for any real x, integer i: [x] + i = [x + i].
  96
  97          To prevent divl() from trapping, [(b[n1 % d] + n0)/d] must
  98          be less than b.  Assume that [n1 % d] and n0 take their
  99          respective maximum values of d - 1 and b - 1:
 100                  [(b(d - 1) + (b - 1))/d] < b
 101              <=> [(bd - 1)/d] < b
 102              <=> [b - 1/d] < b
 103          which is a tautology.
 104
 105          Therefore, this code is correct and will not trap. */
 106       uint64_t b = 1ULL << 32;
 107       uint32_t n1 = n >> 32;
 108       uint32_t n0 = n;
 109       uint32_t d0 = d;
 110
 111       return divl (b * (n1 % d0) + n0, d0) + b * (n1 / d0);
 112     }
 113   else
 114     {
 115       /* Based on the algorithm and proof available from
 116          http://www.hackersdelight.org/revisions.pdf. */
 117       if (n < d)
 118         return 0;
 119       else
 120         {
 121           uint32_t d1 = d >> 32;
 122           int s = nlz (d1);
 123           uint64_t q = divl (n >> 1, (d << s) >> 32) >> (31 - s);
 124           return n - (q - 1) * d < d ? q - 1 : q;
 125         }
 126     }
 127 }
 128
 129 /* Divides unsigned 64-bit N by unsigned 64-bit D and returns the
 130    remainder. */
 131 static uint32_t
 132 umod64 (uint64_t n, uint64_t d)
 133 {
 134   return n - d * udiv64 (n, d);
 135 }
 136
 137 /* Divides signed 64-bit N by signed 64-bit D and returns the
 138    quotient. */
 139 static int64_t
 140 sdiv64 (int64_t n, int64_t d)
 141 {
 142   uint64_t n_abs = n >= 0 ? (uint64_t) n : -(uint64_t) n;
 143   uint64_t d_abs = d >= 0 ? (uint64_t) d : -(uint64_t) d;
 144   uint64_t q_abs = udiv64 (n_abs, d_abs);
 145   return (n < 0) == (d < 0) ? (int64_t) q_abs : -(int64_t) q_abs;
 146 }
 147
 148 /* Divides signed 64-bit N by signed 64-bit D and returns the
 149    remainder. */
 150 static int32_t
 151 smod64 (int64_t n, int64_t d)
 152 {
 153   return n - d * sdiv64 (n, d);
 154 }
 155 \f
 156 /* These are the routines that GCC calls. */
 157
 158 long long __divdi3 (long long n, long long d);
 159 long long __moddi3 (long long n, long long d);
 160 unsigned long long __udivdi3 (unsigned long long n, unsigned long long d);
 161 unsigned long long __umoddi3 (unsigned long long n, unsigned long long d);
 162
 163 /* Signed 64-bit division. */
 164 long long
 165 __divdi3 (long long n, long long d)
 166 {
 167   return sdiv64 (n, d);
 168 }
 169
 170 /* Signed 64-bit remainder. */
 171 long long
 172 __moddi3 (long long n, long long d)
 173 {
 174   return smod64 (n, d);
 175 }
 176
 177 /* Unsigned 64-bit division. */
 178 unsigned long long
 179 __udivdi3 (unsigned long long n, unsigned long long d)
 180 {
 181   return udiv64 (n, d);
 182 }
 183
 184 /* Unsigned 64-bit remainder. */
 185 unsigned long long
 186 __umoddi3 (unsigned long long n, unsigned long long d)
 187 {
 188   return umod64 (n, d);
 189 }