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.examples.jmh.descriptive;
18
19 import java.math.BigInteger;
20 import java.nio.ByteBuffer;
21 import org.apache.commons.numbers.core.DD;
22
23 /**
24 * A 128-bit unsigned integer.
25 *
26 * <p>This is a copy of {@code o.a.c.statistics.descriptive.UInt128} to allow benchmarking.
27 * Additional methods may have been added for comparative benchmarks.
28 *
29 * <p>This is a specialised class to implement an accumulator of {@code long} values
30 * generated by squaring {@code int} values.
31 *
32 * @since 1.1
33 */
34 final class UInt128 {
35 /** Mask for the lower 32-bits of a long. */
36 private static final long MASK32 = 0xffff_ffffL;
37
38 // Data is stored using integers to allow efficient sum-with-carry addition
39
40 /** low 32-bits. */
41 private int d;
42 /** low 32-bits. */
43 private int c;
44 /** high 64-bits. */
45 private long ab;
46
47 /**
48 * Create an instance.
49 */
50 private UInt128() {
51 // No-op
52 }
53
54 /**
55 * Create an instance.
56 *
57 * @param x Value.
58 */
59 private UInt128(long x) {
60 d = (int) x;
61 c = (int) (x >>> Integer.SIZE);
62 }
63
64 /**
65 * Create an instance using a direct binary representation.
66 *
67 * @param hi High 64-bits.
68 * @param mid Middle 32-bits.
69 * @param lo Low 32-bits.
70 */
71 private UInt128(long hi, int mid, int lo) {
72 this.d = lo;
73 this.c = mid;
74 this.ab = hi;
75 }
76
77 /**
78 * Create an instance using a direct binary representation.
79 * This is package-private for testing.
80 *
81 * @param hi High 64-bits.
82 * @param lo Low 64-bits.
83 */
84 UInt128(long hi, long lo) {
85 this.d = (int) lo;
86 this.c = (int) (lo >>> Integer.SIZE);
87 this.ab = hi;
88 }
89
90 /**
91 * Create an instance. The initial value is zero.
92 *
93 * @return the instance
94 */
95 static UInt128 create() {
96 return new UInt128();
97 }
98
99 /**
100 * Create an instance of the {@code long} value.
101 * The value is assumed to be an unsigned 64-bit integer.
102 *
103 * @param x Value (must be positive).
104 * @return the instance
105 */
106 static UInt128 of(long x) {
107 return new UInt128(x);
108 }
109
110 /**
111 * Create an instance of the {@code UInt96} value.
112 *
113 * @param x Value.
114 * @return the instance
115 */
116 static UInt128 of(UInt96 x) {
117 final int lo = x.lo32();
118 final long hi = x.hi64();
119 final UInt128 y = new UInt128();
120 y.d = lo;
121 y.c = (int) hi;
122 y.ab = hi >>> Integer.SIZE;
123 return y;
124 }
125
126 /**
127 * Adds the value in place. It is assumed to be positive, for example the square of an
128 * {@code int} value. However no check is performed for a negative value.
129 *
130 * <p>Note: This addition handles {@value Long#MIN_VALUE} as an unsigned
131 * value of 2^63.
132 *
133 * @param x Value.
134 */
135 void addPositive(long x) {
136 // Sum with carry.
137 // Assuming x is positive then x + lo will not overflow 64-bits
138 // so we do not have to split x into upper and lower 32-bit values.
139 long s = x + (d & MASK32);
140 d = (int) s;
141 s = (s >>> Integer.SIZE) + (c & MASK32);
142 c = (int) s;
143 ab += s >>> Integer.SIZE;
144 }
145
146 /**
147 * Adds the value in-place.
148 *
149 * @param x Value.
150 */
151 void add(UInt128 x) {
152 // Avoid issues adding to itself
153 final int dd = x.d;
154 final int cc = x.c;
155 final long aabb = x.ab;
156 // Sum with carry.
157 long s = (dd & MASK32) + (d & MASK32);
158 d = (int) s;
159 s = (s >>> Integer.SIZE) + (cc & MASK32) + (c & MASK32);
160 c = (int) s;
161 ab += (s >>> Integer.SIZE) + aabb;
162 }
163
164 /**
165 * Multiply by the unsigned value.
166 * Any overflow bits are lost.
167 *
168 * @param x Value.
169 * @return the product
170 */
171 UInt128 unsignedMultiply(int x) {
172 final long xx = x & MASK32;
173 // Multiply with carry.
174 long product = xx * (d & MASK32);
175 final int dd = (int) product;
176 product = (product >>> Integer.SIZE) + xx * (c & MASK32);
177 final int cc = (int) product;
178 // Possible overflow here and bits are lost
179 final long aabb = (product >>> Integer.SIZE) + xx * ab;
180 return new UInt128(aabb, cc, dd);
181 }
182
183 /**
184 * Subtracts the value.
185 * Any overflow bits (negative result) are lost.
186 *
187 * @param x Value.
188 * @return the difference
189 */
190 UInt128 subtract(UInt128 x) {
191 // Difference with carry.
192 long diff = (d & MASK32) - (x.d & MASK32);
193 final int dd = (int) diff;
194 diff = (diff >> Integer.SIZE) + (c & MASK32) - (x.c & MASK32);
195 final int cc = (int) diff;
196 // Possible overflow here and bits are lost containing info on the
197 // magnitude of the true negative value
198 final long aabb = (diff >> Integer.SIZE) + ab - x.ab;
199 return new UInt128(aabb, cc, dd);
200 }
201
202 /**
203 * Convert to a BigInteger.
204 *
205 * @return the value
206 */
207 BigInteger toBigInteger() {
208 // Test if we have more than 63-bits
209 if (ab != 0 || c < 0) {
210 final ByteBuffer bb = ByteBuffer.allocate(Integer.BYTES * 4)
211 .putLong(ab)
212 .putInt(c)
213 .putInt(d);
214 return new BigInteger(1, bb.array());
215 }
216 // Create from a long
217 return BigInteger.valueOf(((c & MASK32) << Integer.SIZE) | (d & MASK32));
218 }
219
220 /**
221 * Convert to a double-double.
222 *
223 * @return the value
224 */
225 DD toDD() {
226 // Sum low to high
227 return DD.ofSum(d & MASK32, (c & MASK32) * 0x1.0p32)
228 .add((ab & MASK32) * 0x1.0p64)
229 .add((ab >>> Integer.SIZE) * 0x1.0p96);
230 }
231
232 /**
233 * Convert to a {@code double}.
234 *
235 * @return the value
236 */
237 double toDouble() {
238 return IntMath.uin128ToDouble(hi64(), lo64());
239 }
240
241 /**
242 * Return the lower 64-bits as a {@code long} value.
243 *
244 * @return the low 64-bits
245 */
246 long lo64() {
247 return (d & MASK32) | ((c & MASK32) << Integer.SIZE);
248 }
249
250 /**
251 * Return the low 32-bits as an {@code int} value.
252 *
253 * @return bits 32-1
254 */
255 int lo32() {
256 return d;
257 }
258
259 /**
260 * Return the middle 32-bits as an {@code int} value.
261 *
262 * @return bits 64-33
263 */
264 int mid32() {
265 return c;
266 }
267
268 /**
269 * Return the higher 64-bits as a {@code long} value.
270 *
271 * @return bits 128-65
272 */
273 long hi64() {
274 return ab;
275 }
276
277 /**
278 * Return the higher 32-bits as an {@code int} value.
279 *
280 * @return bits 128-97
281 */
282 int hi32() {
283 return (int) (ab >>> Integer.SIZE);
284 }
285 }