Back to index

lightning-sunbird  0.9+nobinonly
prlong.c
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is the Netscape Portable Runtime (NSPR).
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1998-2000
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *
00024  * Alternatively, the contents of this file may be used under the terms of
00025  * either the GNU General Public License Version 2 or later (the "GPL"), or
00026  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00027  * in which case the provisions of the GPL or the LGPL are applicable instead
00028  * of those above. If you wish to allow use of your version of this file only
00029  * under the terms of either the GPL or the LGPL, and not to allow others to
00030  * use your version of this file under the terms of the MPL, indicate your
00031  * decision by deleting the provisions above and replace them with the notice
00032  * and other provisions required by the GPL or the LGPL. If you do not delete
00033  * the provisions above, a recipient may use your version of this file under
00034  * the terms of any one of the MPL, the GPL or the LGPL.
00035  *
00036  * ***** END LICENSE BLOCK ***** */
00037 
00038 #include "primpl.h"
00039 
00040 static PRInt64 ll_zero = LL_INIT( 0x00000000,0x00000000 );
00041 static PRInt64 ll_maxint = LL_INIT( 0x7fffffff, 0xffffffff );
00042 static PRInt64 ll_minint = LL_INIT( 0x80000000, 0x00000000 );
00043 static PRUint64 ll_maxuint = LL_INIT( 0xffffffff, 0xffffffff );
00044 
00045 #if defined(HAVE_WATCOM_BUG_2)
00046 PRInt64 __pascal __loadds __export
00047     LL_Zero(void) { return ll_zero; }
00048 PRInt64 __pascal __loadds __export
00049     LL_MaxInt(void) { return ll_maxint; }
00050 PRInt64 __pascal __loadds __export
00051     LL_MinInt(void) { return ll_minint; }
00052 PRUint64 __pascal __loadds __export
00053     LL_MaxUint(void) { return ll_maxuint; }
00054 #else
00055 PR_IMPLEMENT(PRInt64) LL_Zero(void) { return ll_zero; }
00056 PR_IMPLEMENT(PRInt64) LL_MaxInt(void) { return ll_maxint; }
00057 PR_IMPLEMENT(PRInt64) LL_MinInt(void) { return ll_minint; }
00058 PR_IMPLEMENT(PRUint64) LL_MaxUint(void) { return ll_maxuint; }
00059 #endif
00060 
00061 #ifndef HAVE_LONG_LONG
00062 /*
00063 ** Divide 64-bit a by 32-bit b, which must be normalized so its high bit is 1.
00064 */
00065 static void norm_udivmod32(PRUint32 *qp, PRUint32 *rp, PRUint64 a, PRUint32 b)
00066 {
00067     PRUint32 d1, d0, q1, q0;
00068     PRUint32 r1, r0, m;
00069 
00070     d1 = _hi16(b);
00071     d0 = _lo16(b);
00072     r1 = a.hi % d1;
00073     q1 = a.hi / d1;
00074     m = q1 * d0;
00075     r1 = (r1 << 16) | _hi16(a.lo);
00076     if (r1 < m) {
00077         q1--, r1 += b;
00078         if (r1 >= b  /* i.e., we didn't get a carry when adding to r1 */
00079            && r1 < m) {
00080            q1--, r1 += b;
00081        }
00082     }
00083     r1 -= m;
00084     r0 = r1 % d1;
00085     q0 = r1 / d1;
00086     m = q0 * d0;
00087     r0 = (r0 << 16) | _lo16(a.lo);
00088     if (r0 < m) {
00089         q0--, r0 += b;
00090         if (r0 >= b
00091            && r0 < m) {
00092            q0--, r0 += b;
00093        }
00094     }
00095     *qp = (q1 << 16) | q0;
00096     *rp = r0 - m;
00097 }
00098 
00099 static PRUint32 CountLeadingZeros(PRUint32 a)
00100 {
00101     PRUint32 t;
00102     PRUint32 r = 32;
00103 
00104     if ((t = a >> 16) != 0)
00105        r -= 16, a = t;
00106     if ((t = a >> 8) != 0)
00107        r -= 8, a = t;
00108     if ((t = a >> 4) != 0)
00109        r -= 4, a = t;
00110     if ((t = a >> 2) != 0)
00111        r -= 2, a = t;
00112     if ((t = a >> 1) != 0)
00113        r -= 1, a = t;
00114     if (a & 1)
00115        r--;
00116     return r;
00117 }
00118 
00119 PR_IMPLEMENT(void) ll_udivmod(PRUint64 *qp, PRUint64 *rp, PRUint64 a, PRUint64 b)
00120 {
00121     PRUint32 n0, n1, n2;
00122     PRUint32 q0, q1;
00123     PRUint32 rsh, lsh;
00124 
00125     n0 = a.lo;
00126     n1 = a.hi;
00127 
00128     if (b.hi == 0) {
00129        if (b.lo > n1) {
00130            /* (0 q0) = (n1 n0) / (0 D0) */
00131 
00132            lsh = CountLeadingZeros(b.lo);
00133 
00134            if (lsh) {
00135               /*
00136                * Normalize, i.e. make the most significant bit of the
00137                * denominator be set.
00138                */
00139               b.lo = b.lo << lsh;
00140               n1 = (n1 << lsh) | (n0 >> (32 - lsh));
00141               n0 = n0 << lsh;
00142            }
00143 
00144            a.lo = n0, a.hi = n1;
00145            norm_udivmod32(&q0, &n0, a, b.lo);
00146            q1 = 0;
00147 
00148            /* remainder is in n0 >> lsh */
00149        } else {
00150            /* (q1 q0) = (n1 n0) / (0 d0) */
00151 
00152            if (b.lo == 0)          /* user wants to divide by zero! */
00153               b.lo = 1 / b.lo;     /* so go ahead and crash */
00154 
00155            lsh = CountLeadingZeros(b.lo);
00156 
00157            if (lsh == 0) {
00158               /*
00159                * From (n1 >= b.lo)
00160                *   && (the most significant bit of b.lo is set),
00161                * conclude that
00162                *     (the most significant bit of n1 is set)
00163                *   && (the leading quotient digit q1 = 1).
00164                *
00165                * This special case is necessary, not an optimization
00166                * (Shifts counts of 32 are undefined).
00167                */
00168               n1 -= b.lo;
00169               q1 = 1;
00170            } else {
00171               /*
00172                * Normalize.
00173                */
00174               rsh = 32 - lsh;
00175 
00176               b.lo = b.lo << lsh;
00177               n2 = n1 >> rsh;
00178               n1 = (n1 << lsh) | (n0 >> rsh);
00179               n0 = n0 << lsh;
00180 
00181               a.lo = n1, a.hi = n2;
00182               norm_udivmod32(&q1, &n1, a, b.lo);
00183            }
00184 
00185            /* n1 != b.lo... */
00186 
00187            a.lo = n0, a.hi = n1;
00188            norm_udivmod32(&q0, &n0, a, b.lo);
00189 
00190            /* remainder in n0 >> lsh */
00191        }
00192 
00193        if (rp) {
00194            rp->lo = n0 >> lsh;
00195            rp->hi = 0;
00196        }
00197     } else {
00198        if (b.hi > n1) {
00199            /* (0 0) = (n1 n0) / (D1 d0) */
00200 
00201            q0 = 0;
00202            q1 = 0;
00203 
00204            /* remainder in (n1 n0) */
00205            if (rp) {
00206               rp->lo = n0;
00207               rp->hi = n1;
00208            }
00209        } else {
00210            /* (0 q0) = (n1 n0) / (d1 d0) */
00211 
00212            lsh = CountLeadingZeros(b.hi);
00213            if (lsh == 0) {
00214               /*
00215                * From (n1 >= b.hi)
00216                *   && (the most significant bit of b.hi is set),
00217                * conclude that
00218                *      (the most significant bit of n1 is set)
00219                *   && (the quotient digit q0 = 0 or 1).
00220                *
00221                * This special case is necessary, not an optimization.
00222                */
00223 
00224               /*
00225                * The condition on the next line takes advantage of that
00226                * n1 >= b.hi (true due to control flow).
00227                */
00228               if (n1 > b.hi || n0 >= b.lo) {
00229                   q0 = 1;
00230                   a.lo = n0, a.hi = n1;
00231                   LL_SUB(a, a, b);
00232               } else {
00233                   q0 = 0;
00234               }
00235               q1 = 0;
00236 
00237               if (rp) {
00238                   rp->lo = n0;
00239                   rp->hi = n1;
00240               }
00241            } else {
00242               PRInt64 m;
00243 
00244               /*
00245                * Normalize.
00246                */
00247               rsh = 32 - lsh;
00248 
00249               b.hi = (b.hi << lsh) | (b.lo >> rsh);
00250               b.lo = b.lo << lsh;
00251               n2 = n1 >> rsh;
00252               n1 = (n1 << lsh) | (n0 >> rsh);
00253               n0 = n0 << lsh;
00254 
00255               a.lo = n1, a.hi = n2;
00256               norm_udivmod32(&q0, &n1, a, b.hi);
00257               LL_MUL32(m, q0, b.lo);
00258 
00259               if ((m.hi > n1) || ((m.hi == n1) && (m.lo > n0))) {
00260                   q0--;
00261                   LL_SUB(m, m, b);
00262               }
00263 
00264               q1 = 0;
00265 
00266               /* Remainder is ((n1 n0) - (m1 m0)) >> lsh */
00267               if (rp) {
00268                   a.lo = n0, a.hi = n1;
00269                   LL_SUB(a, a, m);
00270                   rp->lo = (a.hi << rsh) | (a.lo >> lsh);
00271                   rp->hi = a.hi >> lsh;
00272               }
00273            }
00274        }
00275     }
00276 
00277     if (qp) {
00278        qp->lo = q0;
00279        qp->hi = q1;
00280     }
00281 }
00282 #endif /* !HAVE_LONG_LONG */