js/src/jslong.cpp

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is Mozilla Communicator client code, released
  16  * March 31, 1998.
  17  *
  18  * The Initial Developer of the Original Code is
  19  * Netscape Communications Corporation.
  20  * Portions created by the Initial Developer are Copyright (C) 1998
  21  * the Initial Developer. All Rights Reserved.
  22  *
  23  * Contributor(s):
  24  *
  25  * Alternatively, the contents of this file may be used under the terms of
  26  * either of the GNU General Public License Version 2 or later (the "GPL"),
  27  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  28  * in which case the provisions of the GPL or the LGPL are applicable instead
  29  * of those above. If you wish to allow use of your version of this file only
  30  * under the terms of either the GPL or the LGPL, and not to allow others to
  31  * use your version of this file under the terms of the MPL, indicate your
  32  * decision by deleting the provisions above and replace them with the notice
  33  * and other provisions required by the GPL or the LGPL. If you do not delete
  34  * the provisions above, a recipient may use your version of this file under
  35  * the terms of any one of the MPL, the GPL or the LGPL.
  36  *
  37  * ***** END LICENSE BLOCK ***** */
  38
  39 #include "jsstddef.h"
  40 #include "jstypes.h"
  41 #include "jslong.h"
  42
  43 #ifndef JS_HAVE_LONG_LONG
  44 /*
  45 ** Divide 64-bit a by 32-bit b, which must be normalized so its high bit is 1.
  46 */
  47 static void norm_udivmod32(JSUint32 *qp, JSUint32 *rp, JSUint64 a, JSUint32 b)
  48 {
  49     JSUint32 d1, d0, q1, q0;
  50     JSUint32 r1, r0, m;
  51
  52     d1 = jshi16(b);
  53     d0 = jslo16(b);
  54     r1 = a.hi % d1;
  55     q1 = a.hi / d1;
  56     m = q1 * d0;
  57     r1 = (r1 << 16) | jshi16(a.lo);
  58     if (r1 < m) {
  59         q1--, r1 += b;
  60         if (r1 >= b     /* i.e., we didn't get a carry when adding to r1 */
  61             && r1 < m) {
  62             q1--, r1 += b;
  63         }
  64     }
  65     r1 -= m;
  66     r0 = r1 % d1;
  67     q0 = r1 / d1;
  68     m = q0 * d0;
  69     r0 = (r0 << 16) | jslo16(a.lo);
  70     if (r0 < m) {
  71         q0--, r0 += b;
  72         if (r0 >= b
  73             && r0 < m) {
  74             q0--, r0 += b;
  75         }
  76     }
  77     *qp = (q1 << 16) | q0;
  78     *rp = r0 - m;
  79 }
  80
  81 static JSUint32 CountLeadingZeros(JSUint32 a)
  82 {
  83     JSUint32 t;
  84     JSUint32 r = 32;
  85
  86     if ((t = a >> 16) != 0)
  87         r -= 16, a = t;
  88     if ((t = a >> 8) != 0)
  89         r -= 8, a = t;
  90     if ((t = a >> 4) != 0)
  91         r -= 4, a = t;
  92     if ((t = a >> 2) != 0)
  93         r -= 2, a = t;
  94     if ((t = a >> 1) != 0)
  95         r -= 1, a = t;
  96     if (a & 1)
  97         r--;
  98     return r;
  99 }
 100
 101 JS_PUBLIC_API(void) jsll_udivmod(JSUint64 *qp, JSUint64 *rp, JSUint64 a, JSUint64 b)
 102 {
 103     JSUint32 n0, n1, n2;
 104     JSUint32 q0, q1;
 105     JSUint32 rsh, lsh;
 106
 107     n0 = a.lo;
 108     n1 = a.hi;
 109
 110     if (b.hi == 0) {
 111         if (b.lo > n1) {
 112             /* (0 q0) = (n1 n0) / (0 D0) */
 113
 114             lsh = CountLeadingZeros(b.lo);
 115
 116             if (lsh) {
 117                 /*
 118                  * Normalize, i.e. make the most significant bit of the
 119                  * denominator be set.
 120                  */
 121                 b.lo = b.lo << lsh;
 122                 n1 = (n1 << lsh) | (n0 >> (32 - lsh));
 123                 n0 = n0 << lsh;
 124             }
 125
 126             a.lo = n0, a.hi = n1;
 127             norm_udivmod32(&q0, &n0, a, b.lo);
 128             q1 = 0;
 129
 130             /* remainder is in n0 >> lsh */
 131         } else {
 132             /* (q1 q0) = (n1 n0) / (0 d0) */
 133
 134             if (b.lo == 0)              /* user wants to divide by zero! */
 135                 b.lo = 1 / b.lo;        /* so go ahead and crash */
 136
 137             lsh = CountLeadingZeros(b.lo);
 138
 139             if (lsh == 0) {
 140                 /*
 141                  * From (n1 >= b.lo)
 142                  *   && (the most significant bit of b.lo is set),
 143                  * conclude that
 144                  *      (the most significant bit of n1 is set)
 145                  *   && (the leading quotient digit q1 = 1).
 146                  *
 147                  * This special case is necessary, not an optimization
 148                  * (Shifts counts of 32 are undefined).
 149                  */
 150                 n1 -= b.lo;
 151                 q1 = 1;
 152             } else {
 153                 /*
 154                  * Normalize.
 155                  */
 156                 rsh = 32 - lsh;
 157
 158                 b.lo = b.lo << lsh;
 159                 n2 = n1 >> rsh;
 160                 n1 = (n1 << lsh) | (n0 >> rsh);
 161                 n0 = n0 << lsh;
 162
 163                 a.lo = n1, a.hi = n2;
 164                 norm_udivmod32(&q1, &n1, a, b.lo);
 165             }
 166
 167             /* n1 != b.lo... */
 168
 169             a.lo = n0, a.hi = n1;
 170             norm_udivmod32(&q0, &n0, a, b.lo);
 171
 172             /* remainder in n0 >> lsh */
 173         }
 174
 175         if (rp) {
 176             rp->lo = n0 >> lsh;
 177             rp->hi = 0;
 178         }
 179     } else {
 180         if (b.hi > n1) {
 181             /* (0 0) = (n1 n0) / (D1 d0) */
 182
 183             q0 = 0;
 184             q1 = 0;
 185
 186             /* remainder in (n1 n0) */
 187             if (rp) {
 188                 rp->lo = n0;
 189                 rp->hi = n1;
 190             }
 191         } else {
 192             /* (0 q0) = (n1 n0) / (d1 d0) */
 193
 194             lsh = CountLeadingZeros(b.hi);
 195             if (lsh == 0) {
 196                 /*
 197                  * From (n1 >= b.hi)
 198                  *   && (the most significant bit of b.hi is set),
 199                  * conclude that
 200                  *      (the most significant bit of n1 is set)
 201                  *   && (the quotient digit q0 = 0 or 1).
 202                  *
 203                  * This special case is necessary, not an optimization.
 204                  */
 205
 206                 /*
 207                  * The condition on the next line takes advantage of that
 208                  * n1 >= b.hi (true due to control flow).
 209                  */
 210                 if (n1 > b.hi || n0 >= b.lo) {
 211                     q0 = 1;
 212                     a.lo = n0, a.hi = n1;
 213                     JSLL_SUB(a, a, b);
 214                 } else {
 215                     q0 = 0;
 216                 }
 217                 q1 = 0;
 218
 219                 if (rp) {
 220                     rp->lo = n0;
 221                     rp->hi = n1;
 222                 }
 223             } else {
 224                 JSInt64 m;
 225
 226                 /*
 227                  * Normalize.
 228                  */
 229                 rsh = 32 - lsh;
 230
 231                 b.hi = (b.hi << lsh) | (b.lo >> rsh);
 232                 b.lo = b.lo << lsh;
 233                 n2 = n1 >> rsh;
 234                 n1 = (n1 << lsh) | (n0 >> rsh);
 235                 n0 = n0 << lsh;
 236
 237                 a.lo = n1, a.hi = n2;
 238                 norm_udivmod32(&q0, &n1, a, b.hi);
 239                 JSLL_MUL32(m, q0, b.lo);
 240
 241                 if ((m.hi > n1) || ((m.hi == n1) && (m.lo > n0))) {
 242                     q0--;
 243                     JSLL_SUB(m, m, b);
 244                 }
 245
 246                 q1 = 0;
 247
 248                 /* Remainder is ((n1 n0) - (m1 m0)) >> lsh */
 249                 if (rp) {
 250                     a.lo = n0, a.hi = n1;
 251                     JSLL_SUB(a, a, m);
 252                     rp->lo = (a.hi << rsh) | (a.lo >> lsh);
 253                     rp->hi = a.hi >> lsh;
 254                 }
 255             }
 256         }
 257     }
 258
 259     if (qp) {
 260         qp->lo = q0;
 261         qp->hi = q1;
 262     }
 263 }
 264 #endif /* !JS_HAVE_LONG_LONG */