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
22 /**
23 * A mutable 96-bit unsigned integer.
24 *
25 * <p>This is a specialised class to implement an accumulator of {@code long} values
26 * generated by squaring {@code int} values from an array (max observations=2^31).
27 *
28 * @since 1.1
29 */
30 final class UInt96 {
31 /** Mask for the lower 32-bits of a long. */
32 private static final long MASK32 = 0xffff_ffffL;
33
34 // Low data is stored using an integer to allow efficient sum-with-carry addition
35
36 /** bits 32-1 (low 32-bits). */
37 private int c;
38 /** bits 96-33. */
39 private long ab;
40
41 /**
42 * Create an instance.
43 */
44 private UInt96() {
45 // No-op
46 }
47
48 /**
49 * Create an instance.
50 *
51 * @param x Value.
52 */
53 private UInt96(long x) {
54 c = (int) x;
55 ab = (int) (x >>> Integer.SIZE);
56 }
57
58 /**
59 * Create an instance using a direct binary representation.
60 * This is package-private for testing.
61 *
62 * @param hi High 64-bits.
63 * @param lo Low 32-bits.
64 */
65 UInt96(long hi, int lo) {
66 this.c = lo;
67 this.ab = hi;
68 }
69
70 /**
71 * Create an instance. The initial value is zero.
72 *
73 * @return the instance
74 */
75 static UInt96 create() {
76 return new UInt96();
77 }
78
79 /**
80 * Create an instance of the {@code long} value.
81 * The value is assumed to be an unsigned 64-bit integer.
82 *
83 * @param x Value (must be positive).
84 * @return the instance
85 */
86 static UInt96 of(long x) {
87 return new UInt96(x);
88 }
89
90 /**
91 * Adds the value. It is assumed to be positive, for example the square of an
92 * {@code int} value. However no check is performed for a negative value.
93 *
94 * <p>Note: This addition handles {@value Long#MIN_VALUE} as an unsigned
95 * value of 2^63.
96 *
97 * @param x Value.
98 */
99 void addPositive(long x) {
100 // Sum with carry.
101 // Assuming x is positive then x + lo will not overflow 64-bits
102 // so we do not have to split x into upper and lower 32-bit values.
103 final long s = x + (c & MASK32);
104 c = (int) s;
105 ab += s >>> Integer.SIZE;
106 }
107
108 /**
109 * Adds the value.
110 *
111 * @param x Value.
112 */
113 void add(UInt96 x) {
114 // Avoid issues adding to itself
115 final int cc = x.c;
116 final long aabb = x.ab;
117 // Sum with carry.
118 final long s = (cc & MASK32) + (c & MASK32);
119 c = (int) s;
120 ab += (s >>> Integer.SIZE) + aabb;
121 }
122
123 /**
124 * Convert to a BigInteger.
125 *
126 * @return the value
127 */
128 BigInteger toBigInteger() {
129 if (ab != 0) {
130 final ByteBuffer bb = ByteBuffer.allocate(Integer.BYTES * 3)
131 .putLong(ab)
132 .putInt(c);
133 return new BigInteger(1, bb.array());
134 }
135 return BigInteger.valueOf(c & MASK32);
136 }
137
138 /**
139 * Return the lower 32-bits as an {@code int} value.
140 *
141 * @return bits 32-1
142 */
143 int lo32() {
144 return c;
145 }
146
147 /**
148 * Return the higher 64-bits as a {@code long} value.
149 *
150 * @return bits 96-33
151 */
152 long hi64() {
153 return ab;
154 }
155 }