/*
    * Licensed to the Apache Software Foundation (ASF) under one or more
    * contributor license agreements.  See the NOTICE file distributed with
    * this work for additional information regarding copyright ownership.
    * The ASF licenses this file to You under the Apache License, Version 2.0
    * (the "License"); you may not use this file except in compliance with
    * the License.  You may obtain a copy of the License at
    *
    *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package org.apache.commons.statistics.descriptive;
  
  import java.math.BigInteger;
  import java.nio.ByteBuffer;
  import org.apache.commons.numbers.core.DD;
  
  /**
   * A mutable 128-bit signed integer.
   *
   * <p>This is a specialised class to implement an accumulator of {@code long} values.
   *
   * <p>Note: This number uses a signed long integer representation of:
   *
   * <pre>value = 2<sup>64</sup> * hi64 + lo64</pre>
   *
   * <p>If the high value is zero then the low value is the long representation of the
   * number including the sign bit. Otherwise the low value corresponds to a correction
   * term for the scaled high value which contains the sign-bit of the number.
   *
   * @since 1.1
   */
  final class Int128 {
      /** Mask for the lower 32-bits of a long. */
      private static final long MASK32 = 0xffff_ffffL;
      /** 2^53. */
      private static final long TWO_POW_53 = 1L << 53;
  
      /** low 64-bits. */
      private long lo;
      /** high 64-bits. */
      private long hi;
  
      /**
       * Create an instance.
       */
      private Int128() {
          // No-op
      }
  
      /**
       * Create an instance.
       *
       * @param x Value.
       */
      private Int128(long x) {
          lo = x;
      }
  
      /**
       * Create an instance using a direct binary representation.
       * This is package-private for testing.
       *
       * @param hi High 64-bits.
       * @param lo Low 64-bits.
       */
      Int128(long hi, long lo) {
          this.lo = lo;
          this.hi = hi;
      }
  
      /**
       * Create an instance. The initial value is zero.
       *
       * @return the instance
       */
      static Int128 create() {
          return new Int128();
      }
  
      /**
       * Create an instance of the {@code long} value.
       *
       * @param x Value.
       * @return the instance
       */
      static Int128 of(long x) {
          return new Int128(x);
      }
  
      /**
       * Adds the value.
       *
       * @param x Value.
      */
     void add(long x) {
         final long y = lo;
         final long r = y + x;
         // Overflow if the result has the opposite sign of both arguments
         // (+,+) -> -
         // (-,-) -> +
         // Detect opposite sign:
         if (((y ^ r) & (x ^ r)) < 0) {
             // Carry overflow bit
             hi += x < 0 ? -1 : 1;
         }
         lo = r;
     }
 
     /**
      * Adds the value.
      *
      * @param x Value.
      */
     void add(Int128 x) {
         // Avoid issues adding to itself
         final long l = x.lo;
         final long h = x.hi;
         add(l);
         hi += h;
     }
 
     /**
      * Compute the square of the low 64-bits of this number.
      *
      * <p>Warning: This ignores the upper 64-bits. Use with caution.
      *
      * @return the square
      */
     UInt128 squareLow() {
         final long x = lo;
         final long upper = IntMath.squareHigh(x);
         return new UInt128(upper, x * x);
     }
 
     /**
      * Convert to a BigInteger.
      *
      * @return the value
      */
     BigInteger toBigInteger() {
         long h = hi;
         long l = lo;
         // Special cases
         if (h == 0) {
             return BigInteger.valueOf(l);
         }
         if (l == 0) {
             return BigInteger.valueOf(h).shiftLeft(64);
         }
 
         // The representation is 2^64 * hi64 + lo64.
         // Here we avoid evaluating the addition:
         // BigInteger.valueOf(l).add(BigInteger.valueOf(h).shiftLeft(64))
         // It is faster to create from bytes.
         // BigInteger bytes are an unsigned integer in BigEndian format, plus a sign.
         // If both values are positive we can use the values unchanged.
         // Otherwise selective negation is used to create a positive magnitude
         // and we track the sign.
         // Note: Negation of -2^63 is valid to create an unsigned 2^63.
 
         int sign = 1;
         if ((h ^ l) < 0) {
             // Opposite signs and lo64 is not zero.
             // The lo64 bits are an adjustment to the magnitude of hi64
             // to make it smaller.
             // Here we rearrange to [2^64 * (hi64-1)] + [2^64 - lo64].
             // The second term [2^64 - lo64] can use lo64 as an unsigned 64-bit integer.
             // The first term [2^64 * (hi64-1)] does not work if low is zero.
             // It would work if zero was detected and we carried the overflow
             // bit up to h to make it equal to: (h - 1) + 1 == h.
             // Instead lo64 == 0 is handled as a special case above.
 
             if (h >= 0) {
                 // Treat (unchanged) low as an unsigned add
                 h = h - 1;
             } else {
                 // As above with negation
                 h = ~h; // -h - 1
                 l = -l;
                 sign = -1;
             }
         } else if (h < 0) {
             // Invert negative values to create the equivalent positive magnitude.
             h = -h;
             l = -l;
             sign = -1;
         }
 
         return new BigInteger(sign,
             ByteBuffer.allocate(Long.BYTES * 2)
                 .putLong(h).putLong(l).array());
     }
 
     /**
      * Convert to a {@code double}.
      *
      * @return the value
      */
     double toDouble() {
         long h = hi;
         long l = lo;
         // Special cases
         if (h == 0) {
             return l;
         }
         if (l == 0) {
             return h * 0x1.0p64;
         }
         // Both h and l are non-zero and can be negated to a positive magnitude.
         // Use the same logic as toBigInteger to create magnitude (h, l) and a sign.
         int sign = 1;
         if ((h ^ l) < 0) {
             // Here we rearrange to [2^64 * (hi64-1)] + [2^64 - lo64].
             if (h >= 0) {
                 h = h - 1;
             } else {
                 // As above with negation
                 h = ~h; // -h - 1
                 l = -l;
                 sign = -1;
             }
         } else if (h < 0) {
             // Invert negative values to create the equivalent positive magnitude.
             h = -h;
             l = -l;
             sign = -1;
         }
         final double x = IntMath.uint128ToDouble(h, l);
         return sign < 0 ? -x : x;
     }
 
     /**
      * Convert to a double-double.
      *
      * @return the value
      */
     DD toDD() {
         // Don't combine two 64-bit DD numbers:
         // DD.of(hi).scalb(64).add(DD.of(lo))
         // It is more accurate to create a 96-bit number and add the final 32-bits.
         // Sum low to high.
         // Note: Masking a negative hi number will create a small positive magnitude
         // to add to a larger negative number:
         // e.g. x = (x & 0xff) + ((x >> 8) << 8)
         return DD.of(lo).add((hi & MASK32) * 0x1.0p64).add((hi >> Integer.SIZE) * 0x1.0p96);
     }
 
     /**
      * Divide by the count {@code n}, returning the value as a {@code double}.
      *
      * @param n Count.
      * @return the quotient
      */
     double divideToDouble(long n) {
         final DD a = toDD();
         if (n < TWO_POW_53) {
             // n is a representable double
             return a.divide(n).doubleValue();
         }
         // Extended precision divide when n > 2^53
         return a.divide(DD.of(n)).doubleValue();
     }
 
     /**
      * Convert to an {@code int}; throwing an exception if the value overflows an {@code int}.
      *
      * @return the value
      * @throws ArithmeticException if the value overflows an {@code int}.
      * @see Math#toIntExact(long)
      */
     int toIntExact() {
         return Math.toIntExact(toLongExact());
     }
 
     /**
      * Convert to a {@code long}; throwing an exception if the value overflows a {@code long}.
      *
      * @return the value
      * @throws ArithmeticException if the value overflows a {@code long}.
      */
     long toLongExact() {
         if (hi != 0) {
             throw new ArithmeticException("long integer overflow");
         }
         return lo;
     }
 
     /**
      * Return the lower 64-bits as a {@code long} value.
      *
      * <p>If the high value is zero then the low value is the long representation of the
      * number including the sign bit. Otherwise this value corresponds to a correction
      * term for the scaled high value which contains the sign-bit of the number
      * (see {@link Int128}).
      *
      * @return the low 64-bits
      */
     long lo64() {
         return lo;
     }
 
     /**
      * Return the higher 64-bits as a {@code long} value.
      *
      * @return the high 64-bits
      * @see #lo64()
      */
     long hi64() {
         return hi;
     }
 }