1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (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 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.statistics.descriptive;
18
19 import java.math.BigInteger;
20 import java.nio.ByteBuffer;
21 import org.apache.commons.numbers.core.DD;
22
23 /**
24 * A mutable 128-bit signed integer.
25 *
26 * <p>This is a specialised class to implement an accumulator of {@code long} values.
27 *
28 * <p>Note: This number uses a signed long integer representation of:
29 *
30 * <pre>value = 2<sup>64</sup> * hi64 + lo64</pre>
31 *
32 * <p>If the high value is zero then the low value is the long representation of the
33 * number including the sign bit. Otherwise the low value corresponds to a correction
34 * term for the scaled high value which contains the sign-bit of the number.
35 *
36 * @since 1.1
37 */
38 final class Int128 {
39 /** Mask for the lower 32-bits of a long. */
40 private static final long MASK32 = 0xffff_ffffL;
41
42 /** low 64-bits. */
43 private long lo;
44 /** high 64-bits. */
45 private long hi;
46
47 /**
48 * Create an instance.
49 */
50 private Int128() {
51 // No-op
52 }
53
54 /**
55 * Create an instance.
56 *
57 * @param x Value.
58 */
59 private Int128(long x) {
60 lo = x;
61 }
62
63 /**
64 * Create an instance using a direct binary representation.
65 * This is package-private for testing.
66 *
67 * @param hi High 64-bits.
68 * @param lo Low 64-bits.
69 */
70 Int128(long hi, long lo) {
71 this.lo = lo;
72 this.hi = hi;
73 }
74
75 /**
76 * Create an instance. The initial value is zero.
77 *
78 * @return the instance
79 */
80 static Int128 create() {
81 return new Int128();
82 }
83
84 /**
85 * Create an instance of the {@code long} value.
86 *
87 * @param x Value.
88 * @return the instance
89 */
90 static Int128 of(long x) {
91 return new Int128(x);
92 }
93
94 /**
95 * Adds the value.
96 *
97 * @param x Value.
98 */
99 void add(long x) {
100 final long y = lo;
101 final long r = y + x;
102 // Overflow if the result has the opposite sign of both arguments
103 // (+,+) -> -
104 // (-,-) -> +
105 // Detect opposite sign:
106 if (((y ^ r) & (x ^ r)) < 0) {
107 // Carry overflow bit
108 hi += x < 0 ? -1 : 1;
109 }
110 lo = r;
111 }
112
113 /**
114 * Adds the value.
115 *
116 * @param x Value.
117 */
118 void add(Int128 x) {
119 // Avoid issues adding to itself
120 final long l = x.lo;
121 final long h = x.hi;
122 add(l);
123 hi += h;
124 }
125
126 /**
127 * Compute the square of the low 64-bits of this number.
128 *
129 * <p>Warning: This ignores the upper 64-bits. Use with caution.
130 *
131 * @return the square
132 */
133 UInt128 squareLow() {
134 final long x = lo;
135 final long upper = IntMath.squareHigh(x);
136 return new UInt128(upper, x * x);
137 }
138
139 /**
140 * Convert to a BigInteger.
141 *
142 * @return the value
143 */
144 BigInteger toBigInteger() {
145 long h = hi;
146 long l = lo;
147 // Special cases
148 if (h == 0) {
149 return BigInteger.valueOf(l);
150 }
151 if (l == 0) {
152 return BigInteger.valueOf(h).shiftLeft(64);
153 }
154
155 // The representation is 2^64 * hi64 + lo64.
156 // Here we avoid evaluating the addition:
157 // BigInteger.valueOf(l).add(BigInteger.valueOf(h).shiftLeft(64))
158 // It is faster to create from bytes.
159 // BigInteger bytes are an unsigned integer in BigEndian format, plus a sign.
160 // If both values are positive we can use the values unchanged.
161 // Otherwise selective negation is used to create a positive magnitude
162 // and we track the sign.
163 // Note: Negation of -2^63 is valid to create an unsigned 2^63.
164
165 int sign = 1;
166 if ((h ^ l) < 0) {
167 // Opposite signs and lo64 is not zero.
168 // The lo64 bits are an adjustment to the magnitude of hi64
169 // to make it smaller.
170 // Here we rearrange to [2^64 * (hi64-1)] + [2^64 - lo64].
171 // The second term [2^64 - lo64] can use lo64 as an unsigned 64-bit integer.
172 // The first term [2^64 * (hi64-1)] does not work if low is zero.
173 // It would work if zero was detected and we carried the overflow
174 // bit up to h to make it equal to: (h - 1) + 1 == h.
175 // Instead lo64 == 0 is handled as a special case above.
176
177 if (h >= 0) {
178 // Treat (unchanged) low as an unsigned add
179 h = h - 1;
180 } else {
181 // As above with negation
182 h = ~h; // -h - 1
183 l = -l;
184 sign = -1;
185 }
186 } else if (h < 0) {
187 // Invert negative values to create the equivalent positive magnitude.
188 h = -h;
189 l = -l;
190 sign = -1;
191 }
192
193 return new BigInteger(sign,
194 ByteBuffer.allocate(Long.BYTES * 2)
195 .putLong(h).putLong(l).array());
196 }
197
198 /**
199 * Convert to a {@code double}.
200 *
201 * @return the value
202 */
203 double toDouble() {
204 long h = hi;
205 long l = lo;
206 // Special cases
207 if (h == 0) {
208 return l;
209 }
210 if (l == 0) {
211 return h * 0x1.0p64;
212 }
213 // Both h and l are non-zero and can be negated to a positive magnitude.
214 // Use the same logic as toBigInteger to create magnitude (h, l) and a sign.
215 int sign = 1;
216 if ((h ^ l) < 0) {
217 // Here we rearrange to [2^64 * (hi64-1)] + [2^64 - lo64].
218 if (h >= 0) {
219 h = h - 1;
220 } else {
221 // As above with negation
222 h = ~h; // -h - 1
223 l = -l;
224 sign = -1;
225 }
226 } else if (h < 0) {
227 // Invert negative values to create the equivalent positive magnitude.
228 h = -h;
229 l = -l;
230 sign = -1;
231 }
232 final double x = IntMath.uint128ToDouble(h, l);
233 return sign < 0 ? -x : x;
234 }
235
236 /**
237 * Convert to a double-double.
238 *
239 * @return the value
240 */
241 DD toDD() {
242 // Don't combine two 64-bit DD numbers:
243 // DD.of(hi).scalb(64).add(DD.of(lo))
244 // It is more accurate to create a 96-bit number and add the final 32-bits.
245 // Sum low to high.
246 // Note: Masking a negative hi number will create a small positive magnitude
247 // to add to a larger negative number:
248 // e.g. x = (x & 0xff) + ((x >> 8) << 8)
249 return DD.of(lo).add((hi & MASK32) * 0x1.0p64).add((hi >> Integer.SIZE) * 0x1.0p96);
250 }
251
252 /**
253 * Convert to an {@code int}; throwing an exception if the value overflows an {@code int}.
254 *
255 * @return the value
256 * @throws ArithmeticException if the value overflows an {@code int}.
257 * @see Math#toIntExact(long)
258 */
259 int toIntExact() {
260 return Math.toIntExact(toLongExact());
261 }
262
263 /**
264 * Convert to a {@code long}; throwing an exception if the value overflows a {@code long}.
265 *
266 * @return the value
267 * @throws ArithmeticException if the value overflows a {@code long}.
268 */
269 long toLongExact() {
270 if (hi != 0) {
271 throw new ArithmeticException("long integer overflow");
272 }
273 return lo;
274 }
275
276 /**
277 * Return the lower 64-bits as a {@code long} value.
278 *
279 * <p>If the high value is zero then the low value is the long representation of the
280 * number including the sign bit. Otherwise this value corresponds to a correction
281 * term for the scaled high value which contains the sign-bit of the number
282 * (see {@link Int128}).
283 *
284 * @return the low 64-bits
285 */
286 long lo64() {
287 return lo;
288 }
289
290 /**
291 * Return the higher 64-bits as a {@code long} value.
292 *
293 * @return the high 64-bits
294 * @see #lo64()
295 */
296 long hi64() {
297 return hi;
298 }
299 }