home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / nsprpub / pr / src / misc / prlong.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  5.8 KB  |  260 lines
  1. /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
  2. /*
  3.  * The contents of this file are subject to the Netscape Public License
  4.  * Version 1.0 (the "NPL"); you may not use this file except in
  5.  * compliance with the NPL.  You may obtain a copy of the NPL at
  6.  * http://www.mozilla.org/NPL/
  7.  * 
  8.  * Software distributed under the NPL is distributed on an "AS IS" basis,
  9.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the NPL
  10.  * for the specific language governing rights and limitations under the
  11.  * NPL.
  12.  * 
  13.  * The Initial Developer of this code under the NPL is Netscape
  14.  * Communications Corporation.  Portions created by Netscape are
  15.  * Copyright (C) 1998 Netscape Communications Corporation.  All Rights
  16.  * Reserved.
  17.  */
  18.  
  19. #include "primpl.h"
  20.  
  21. static PRInt64 ll_zero = LL_INIT( 0x00000000,0x00000000 );
  22. static PRInt64 ll_maxint = LL_INIT( 0x7fffffff, 0xffffffff );
  23. static PRInt64 ll_minint = LL_INIT( 0x80000000, 0x00000000 );
  24.  
  25. #if defined(HAVE_WATCOM_BUG_2)
  26. PRInt64 __pascal __loadds __export
  27.     LL_Zero(void) { return ll_zero; }
  28. PRInt64 __pascal __loadds __export
  29.     LL_MaxInt(void) { return ll_maxint; }
  30. PRInt64 __pascal __loadds __export
  31.     LL_MinInt(void) { return ll_minint; }
  32. #else
  33. PR_IMPLEMENT(PRInt64) LL_Zero(void) { return ll_zero; }
  34. PR_IMPLEMENT(PRInt64) LL_MaxInt(void) { return ll_maxint; }
  35. PR_IMPLEMENT(PRInt64) LL_MinInt(void) { return ll_minint; }
  36. #endif
  37.  
  38. #ifndef HAVE_LONG_LONG
  39. /*
  40. ** Divide 64-bit a by 32-bit b, which must be normalized so its high bit is 1.
  41. */
  42. static void norm_udivmod32(PRUint32 *qp, PRUint32 *rp, PRUint64 a, PRUint32 b)
  43. {
  44.     PRUint32 d1, d0, q1, q0;
  45.     PRUint32 r1, r0, m;
  46.  
  47.     d1 = _hi16(b);
  48.     d0 = _lo16(b);
  49.     r1 = a.hi % d1;
  50.     q1 = a.hi / d1;
  51.     m = q1 * d0;
  52.     r1 = (r1 << 16) | _hi16(a.lo);
  53.     if (r1 < m) {
  54.         q1--, r1 += b;
  55.         if (r1 >= b    /* i.e., we didn't get a carry when adding to r1 */
  56.         && r1 < m) {
  57.         q1--, r1 += b;
  58.     }
  59.     }
  60.     r1 -= m;
  61.     r0 = r1 % d1;
  62.     q0 = r1 / d1;
  63.     m = q0 * d0;
  64.     r0 = (r0 << 16) | _lo16(a.lo);
  65.     if (r0 < m) {
  66.         q0--, r0 += b;
  67.         if (r0 >= b
  68.         && r0 < m) {
  69.         q0--, r0 += b;
  70.     }
  71.     }
  72.     *qp = (q1 << 16) | q0;
  73.     *rp = r0 - m;
  74. }
  75.  
  76. static PRUint32 CountLeadingZeros(PRUint32 a)
  77. {
  78.     PRUint32 t;
  79.     PRUint32 r = 32;
  80.  
  81.     if ((t = a >> 16) != 0)
  82.     r -= 16, a = t;
  83.     if ((t = a >> 8) != 0)
  84.     r -= 8, a = t;
  85.     if ((t = a >> 4) != 0)
  86.     r -= 4, a = t;
  87.     if ((t = a >> 2) != 0)
  88.     r -= 2, a = t;
  89.     if ((t = a >> 1) != 0)
  90.     r -= 1, a = t;
  91.     if (a & 1)
  92.     r--;
  93.     return r;
  94. }
  95.  
  96. PR_IMPLEMENT(void) ll_udivmod(PRUint64 *qp, PRUint64 *rp, PRUint64 a, PRUint64 b)
  97. {
  98.     PRUint32 n0, n1, n2;
  99.     PRUint32 q0, q1;
  100.     PRUint32 rsh, lsh;
  101.  
  102.     n0 = a.lo;
  103.     n1 = a.hi;
  104.  
  105.     if (b.hi == 0) {
  106.     if (b.lo > n1) {
  107.         /* (0 q0) = (n1 n0) / (0 D0) */
  108.  
  109.         lsh = CountLeadingZeros(b.lo);
  110.  
  111.         if (lsh) {
  112.         /*
  113.          * Normalize, i.e. make the most significant bit of the
  114.          * denominator be set.
  115.          */
  116.         b.lo = b.lo << lsh;
  117.         n1 = (n1 << lsh) | (n0 >> (32 - lsh));
  118.         n0 = n0 << lsh;
  119.         }
  120.  
  121.         a.lo = n0, a.hi = n1;
  122.         norm_udivmod32(&q0, &n0, a, b.lo);
  123.         q1 = 0;
  124.  
  125.         /* remainder is in n0 >> lsh */
  126.     } else {
  127.         /* (q1 q0) = (n1 n0) / (0 d0) */
  128.  
  129.         if (b.lo == 0)        /* user wants to divide by zero! */
  130.         b.lo = 1 / b.lo;    /* so go ahead and crash */
  131.  
  132.         lsh = CountLeadingZeros(b.lo);
  133.  
  134.         if (lsh == 0) {
  135.         /*
  136.          * From (n1 >= b.lo)
  137.          *   && (the most significant bit of b.lo is set),
  138.          * conclude that
  139.          *    (the most significant bit of n1 is set)
  140.          *   && (the leading quotient digit q1 = 1).
  141.          *
  142.          * This special case is necessary, not an optimization
  143.          * (Shifts counts of 32 are undefined).
  144.          */
  145.         n1 -= b.lo;
  146.         q1 = 1;
  147.         } else {
  148.         /*
  149.          * Normalize.
  150.          */
  151.         rsh = 32 - lsh;
  152.  
  153.         b.lo = b.lo << lsh;
  154.         n2 = n1 >> rsh;
  155.         n1 = (n1 << lsh) | (n0 >> rsh);
  156.         n0 = n0 << lsh;
  157.  
  158.         a.lo = n1, a.hi = n2;
  159.         norm_udivmod32(&q1, &n1, a, b.lo);
  160.         }
  161.  
  162.         /* n1 != b.lo... */
  163.  
  164.         a.lo = n0, a.hi = n1;
  165.         norm_udivmod32(&q0, &n0, a, b.lo);
  166.  
  167.         /* remainder in n0 >> lsh */
  168.     }
  169.  
  170.     if (rp) {
  171.         rp->lo = n0 >> lsh;
  172.         rp->hi = 0;
  173.     }
  174.     } else {
  175.     if (b.hi > n1) {
  176.         /* (0 0) = (n1 n0) / (D1 d0) */
  177.  
  178.         q0 = 0;
  179.         q1 = 0;
  180.  
  181.         /* remainder in (n1 n0) */
  182.         if (rp) {
  183.         rp->lo = n0;
  184.         rp->hi = n1;
  185.         }
  186.     } else {
  187.         /* (0 q0) = (n1 n0) / (d1 d0) */
  188.  
  189.         lsh = CountLeadingZeros(b.hi);
  190.         if (lsh == 0) {
  191.         /*
  192.          * From (n1 >= b.hi)
  193.          *   && (the most significant bit of b.hi is set),
  194.          * conclude that
  195.          *      (the most significant bit of n1 is set)
  196.          *   && (the quotient digit q0 = 0 or 1).
  197.          *
  198.          * This special case is necessary, not an optimization.
  199.          */
  200.  
  201.         /*
  202.          * The condition on the next line takes advantage of that
  203.          * n1 >= b.hi (true due to control flow).
  204.          */
  205.         if (n1 > b.hi || n0 >= b.lo) {
  206.             q0 = 1;
  207.             a.lo = n0, a.hi = n1;
  208.             LL_SUB(a, a, b);
  209.         } else {
  210.             q0 = 0;
  211.         }
  212.         q1 = 0;
  213.  
  214.         if (rp) {
  215.             rp->lo = n0;
  216.             rp->hi = n1;
  217.         }
  218.         } else {
  219.         PRInt64 m;
  220.  
  221.         /*
  222.          * Normalize.
  223.          */
  224.         rsh = 32 - lsh;
  225.  
  226.         b.hi = (b.hi << lsh) | (b.lo >> rsh);
  227.         b.lo = b.lo << lsh;
  228.         n2 = n1 >> rsh;
  229.         n1 = (n1 << lsh) | (n0 >> rsh);
  230.         n0 = n0 << lsh;
  231.  
  232.         a.lo = n1, a.hi = n2;
  233.         norm_udivmod32(&q0, &n1, a, b.hi);
  234.         LL_MUL32(m, q0, b.lo);
  235.  
  236.         if ((m.hi > n1) || ((m.hi == n1) && (m.lo > n0))) {
  237.             q0--;
  238.             LL_SUB(m, m, b);
  239.         }
  240.  
  241.         q1 = 0;
  242.  
  243.         /* Remainder is ((n1 n0) - (m1 m0)) >> lsh */
  244.         if (rp) {
  245.             a.lo = n0, a.hi = n1;
  246.             LL_SUB(a, a, m);
  247.             rp->lo = (a.hi << rsh) | (a.lo >> lsh);
  248.             rp->hi = a.hi >> lsh;
  249.         }
  250.         }
  251.     }
  252.     }
  253.  
  254.     if (qp) {
  255.     qp->lo = q0;
  256.     qp->hi = q1;
  257.     }
  258. }
  259. #endif /* !HAVE_LONG_LONG */
  260.