The Tor Browser / file comparison
comparison: nsprpub/pr/src/misc/prlong.c
nsprpub/pr/src/misc/prlong.c
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:6e51d8403698 |
|---|---|
| 1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ | |
| 2 /* This Source Code Form is subject to the terms of the Mozilla Public | |
| 3 * License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
| 5 | |
| 6 #include "prlong.h" | |
| 7 | |
| 8 static PRInt64 ll_zero = LL_INIT( 0x00000000,0x00000000 ); | |
| 9 static PRInt64 ll_maxint = LL_INIT( 0x7fffffff, 0xffffffff ); | |
| 10 static PRInt64 ll_minint = LL_INIT( 0x80000000, 0x00000000 ); | |
| 11 static PRUint64 ll_maxuint = LL_INIT( 0xffffffff, 0xffffffff ); | |
| 12 | |
| 13 PR_IMPLEMENT(PRInt64) LL_Zero(void) { return ll_zero; } | |
| 14 PR_IMPLEMENT(PRInt64) LL_MaxInt(void) { return ll_maxint; } | |
| 15 PR_IMPLEMENT(PRInt64) LL_MinInt(void) { return ll_minint; } | |
| 16 PR_IMPLEMENT(PRUint64) LL_MaxUint(void) { return ll_maxuint; } | |
| 17 | |
| 18 #ifndef HAVE_LONG_LONG | |
| 19 /* | |
| 20 ** Divide 64-bit a by 32-bit b, which must be normalized so its high bit is 1. | |
| 21 */ | |
| 22 static void norm_udivmod32(PRUint32 *qp, PRUint32 *rp, PRUint64 a, PRUint32 b) | |
| 23 { | |
| 24 PRUint32 d1, d0, q1, q0; | |
| 25 PRUint32 r1, r0, m; | |
| 26 | |
| 27 d1 = _hi16(b); | |
| 28 d0 = _lo16(b); | |
| 29 r1 = a.hi % d1; | |
| 30 q1 = a.hi / d1; | |
| 31 m = q1 * d0; | |
| 32 r1 = (r1 << 16) | _hi16(a.lo); | |
| 33 if (r1 < m) { | |
| 34 q1--, r1 += b; | |
| 35 if (r1 >= b /* i.e., we didn't get a carry when adding to r1 */ | |
| 36 && r1 < m) { | |
| 37 q1--, r1 += b; | |
| 38 } | |
| 39 } | |
| 40 r1 -= m; | |
| 41 r0 = r1 % d1; | |
| 42 q0 = r1 / d1; | |
| 43 m = q0 * d0; | |
| 44 r0 = (r0 << 16) | _lo16(a.lo); | |
| 45 if (r0 < m) { | |
| 46 q0--, r0 += b; | |
| 47 if (r0 >= b | |
| 48 && r0 < m) { | |
| 49 q0--, r0 += b; | |
| 50 } | |
| 51 } | |
| 52 *qp = (q1 << 16) | q0; | |
| 53 *rp = r0 - m; | |
| 54 } | |
| 55 | |
| 56 static PRUint32 CountLeadingZeros(PRUint32 a) | |
| 57 { | |
| 58 PRUint32 t; | |
| 59 PRUint32 r = 32; | |
| 60 | |
| 61 if ((t = a >> 16) != 0) | |
| 62 r -= 16, a = t; | |
| 63 if ((t = a >> 8) != 0) | |
| 64 r -= 8, a = t; | |
| 65 if ((t = a >> 4) != 0) | |
| 66 r -= 4, a = t; | |
| 67 if ((t = a >> 2) != 0) | |
| 68 r -= 2, a = t; | |
| 69 if ((t = a >> 1) != 0) | |
| 70 r -= 1, a = t; | |
| 71 if (a & 1) | |
| 72 r--; | |
| 73 return r; | |
| 74 } | |
| 75 | |
| 76 PR_IMPLEMENT(void) ll_udivmod(PRUint64 *qp, PRUint64 *rp, PRUint64 a, PRUint64 b) | |
| 77 { | |
| 78 PRUint32 n0, n1, n2; | |
| 79 PRUint32 q0, q1; | |
| 80 PRUint32 rsh, lsh; | |
| 81 | |
| 82 n0 = a.lo; | |
| 83 n1 = a.hi; | |
| 84 | |
| 85 if (b.hi == 0) { | |
| 86 if (b.lo > n1) { | |
| 87 /* (0 q0) = (n1 n0) / (0 D0) */ | |
| 88 | |
| 89 lsh = CountLeadingZeros(b.lo); | |
| 90 | |
| 91 if (lsh) { | |
| 92 /* | |
| 93 * Normalize, i.e. make the most significant bit of the | |
| 94 * denominator be set. | |
| 95 */ | |
| 96 b.lo = b.lo << lsh; | |
| 97 n1 = (n1 << lsh) | (n0 >> (32 - lsh)); | |
| 98 n0 = n0 << lsh; | |
| 99 } | |
| 100 | |
| 101 a.lo = n0, a.hi = n1; | |
| 102 norm_udivmod32(&q0, &n0, a, b.lo); | |
| 103 q1 = 0; | |
| 104 | |
| 105 /* remainder is in n0 >> lsh */ | |
| 106 } else { | |
| 107 /* (q1 q0) = (n1 n0) / (0 d0) */ | |
| 108 | |
| 109 if (b.lo == 0) /* user wants to divide by zero! */ | |
| 110 b.lo = 1 / b.lo; /* so go ahead and crash */ | |
| 111 | |
| 112 lsh = CountLeadingZeros(b.lo); | |
| 113 | |
| 114 if (lsh == 0) { | |
| 115 /* | |
| 116 * From (n1 >= b.lo) | |
| 117 * && (the most significant bit of b.lo is set), | |
| 118 * conclude that | |
| 119 * (the most significant bit of n1 is set) | |
| 120 * && (the leading quotient digit q1 = 1). | |
| 121 * | |
| 122 * This special case is necessary, not an optimization | |
| 123 * (Shifts counts of 32 are undefined). | |
| 124 */ | |
| 125 n1 -= b.lo; | |
| 126 q1 = 1; | |
| 127 } else { | |
| 128 /* | |
| 129 * Normalize. | |
| 130 */ | |
| 131 rsh = 32 - lsh; | |
| 132 | |
| 133 b.lo = b.lo << lsh; | |
| 134 n2 = n1 >> rsh; | |
| 135 n1 = (n1 << lsh) | (n0 >> rsh); | |
| 136 n0 = n0 << lsh; | |
| 137 | |
| 138 a.lo = n1, a.hi = n2; | |
| 139 norm_udivmod32(&q1, &n1, a, b.lo); | |
| 140 } | |
| 141 | |
| 142 /* n1 != b.lo... */ | |
| 143 | |
| 144 a.lo = n0, a.hi = n1; | |
| 145 norm_udivmod32(&q0, &n0, a, b.lo); | |
| 146 | |
| 147 /* remainder in n0 >> lsh */ | |
| 148 } | |
| 149 | |
| 150 if (rp) { | |
| 151 rp->lo = n0 >> lsh; | |
| 152 rp->hi = 0; | |
| 153 } | |
| 154 } else { | |
| 155 if (b.hi > n1) { | |
| 156 /* (0 0) = (n1 n0) / (D1 d0) */ | |
| 157 | |
| 158 q0 = 0; | |
| 159 q1 = 0; | |
| 160 | |
| 161 /* remainder in (n1 n0) */ | |
| 162 if (rp) { | |
| 163 rp->lo = n0; | |
| 164 rp->hi = n1; | |
| 165 } | |
| 166 } else { | |
| 167 /* (0 q0) = (n1 n0) / (d1 d0) */ | |
| 168 | |
| 169 lsh = CountLeadingZeros(b.hi); | |
| 170 if (lsh == 0) { | |
| 171 /* | |
| 172 * From (n1 >= b.hi) | |
| 173 * && (the most significant bit of b.hi is set), | |
| 174 * conclude that | |
| 175 * (the most significant bit of n1 is set) | |
| 176 * && (the quotient digit q0 = 0 or 1). | |
| 177 * | |
| 178 * This special case is necessary, not an optimization. | |
| 179 */ | |
| 180 | |
| 181 /* | |
| 182 * The condition on the next line takes advantage of that | |
| 183 * n1 >= b.hi (true due to control flow). | |
| 184 */ | |
| 185 if (n1 > b.hi || n0 >= b.lo) { | |
| 186 q0 = 1; | |
| 187 a.lo = n0, a.hi = n1; | |
| 188 LL_SUB(a, a, b); | |
| 189 } else { | |
| 190 q0 = 0; | |
| 191 } | |
| 192 q1 = 0; | |
| 193 | |
| 194 if (rp) { | |
| 195 rp->lo = n0; | |
| 196 rp->hi = n1; | |
| 197 } | |
| 198 } else { | |
| 199 PRInt64 m; | |
| 200 | |
| 201 /* | |
| 202 * Normalize. | |
| 203 */ | |
| 204 rsh = 32 - lsh; | |
| 205 | |
| 206 b.hi = (b.hi << lsh) | (b.lo >> rsh); | |
| 207 b.lo = b.lo << lsh; | |
| 208 n2 = n1 >> rsh; | |
| 209 n1 = (n1 << lsh) | (n0 >> rsh); | |
| 210 n0 = n0 << lsh; | |
| 211 | |
| 212 a.lo = n1, a.hi = n2; | |
| 213 norm_udivmod32(&q0, &n1, a, b.hi); | |
| 214 LL_MUL32(m, q0, b.lo); | |
| 215 | |
| 216 if ((m.hi > n1) || ((m.hi == n1) && (m.lo > n0))) { | |
| 217 q0--; | |
| 218 LL_SUB(m, m, b); | |
| 219 } | |
| 220 | |
| 221 q1 = 0; | |
| 222 | |
| 223 /* Remainder is ((n1 n0) - (m1 m0)) >> lsh */ | |
| 224 if (rp) { | |
| 225 a.lo = n0, a.hi = n1; | |
| 226 LL_SUB(a, a, m); | |
| 227 rp->lo = (a.hi << rsh) | (a.lo >> lsh); | |
| 228 rp->hi = a.hi >> lsh; | |
| 229 } | |
| 230 } | |
| 231 } | |
| 232 } | |
| 233 | |
| 234 if (qp) { | |
| 235 qp->lo = q0; | |
| 236 qp->hi = q1; | |
| 237 } | |
| 238 } | |
| 239 #endif /* !HAVE_LONG_LONG */ |
