dev/core/super/com/google/gwt/lang/BigLongLibBase.java - gwt - Git at Google

 /*
  * Copyright 2010 Google Inc.
  *
  * Licensed 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 com.google.gwt.lang;

 /**
  * Implements a Java <code>long</code> in a way that can be translated to
  * JavaScript.
  */
 class BigLongLibBase {

   /*
    * Implementation: A LongEmul containing three values {l, m, h} (low, middle,
    * high) such that (x.l + ((long) x.m << 22) + ((long) x.h << 44)) is equal to
    * the original long integer. The constant 22 is chosen since some browsers
    * are faster when operating on integers of 24 bits or less.
    *
    * By convention, we expect and maintain that the upper bits of each word be
    * zeroed.
    *
    * Note that this class must be careful using type "long". Being the
    * implementation of the long type for Production Mode, any place it uses a
    * long is not usable in Production Mode. There is currently one such method:
    * {@link LongLib#getAsLongArray}.
    */
   static class BigLong {
     int l, m, h;
   }


   // Note that the {@link LonghLib#mul} method implicitly depends on the
   // specific value BITS == 22
   protected static final int BITS = 22;
   protected static final int BITS01 = 2 * BITS;
   protected static final int BITS2 = 64 - BITS01;
   protected static final int MASK = (1 << BITS) - 1;
   protected static final int MASK_2 = (1 << BITS2) - 1;
   protected static BigLong remainder;

   protected static final int SIGN_BIT = BITS2 - 1;
   protected static final int SIGN_BIT_VALUE = 1 << SIGN_BIT;
   protected static final double TWO_PWR_15_DBL = 0x8000;
   protected static final double TWO_PWR_16_DBL = 0x10000;
   protected static final double TWO_PWR_22_DBL = 0x400000;
   protected static final double TWO_PWR_31_DBL = TWO_PWR_16_DBL
       * TWO_PWR_15_DBL;
   protected static final double TWO_PWR_32_DBL = TWO_PWR_16_DBL
       * TWO_PWR_16_DBL;
   protected static final double TWO_PWR_44_DBL = TWO_PWR_22_DBL
       * TWO_PWR_22_DBL;
   protected static final double TWO_PWR_63_DBL = TWO_PWR_32_DBL
       * TWO_PWR_31_DBL;

   protected static BigLong create(int value) {
     int a0 = value & MASK;
     int a1 = (value >> BITS) & MASK;
     int a2 = (value < 0) ? MASK_2 : 0;

     if (LongLib.RUN_IN_JVM) {
       BigLong a = new BigLong();
       a.l = a0;
       a.m = a1;
       a.h = a2;
       return a;
     }
     return create0(a0, a1, a2);
   }

   protected static BigLong create(int a0, int a1, int a2) {
     if (LongLib.RUN_IN_JVM) {
       BigLong a = new BigLong();
       a.l = a0;
       a.m = a1;
       a.h = a2;
       return a;
     }
     return create0(a0, a1, a2);
   }

   protected static BigLong divMod(BigLong a, BigLong b,
       boolean computeRemainder) {
     if (isZero(b)) {
       throw new ArithmeticException("divide by zero");
     }
     if (isZero(a)) {
       if (computeRemainder) {
         remainder = create(); // zero
       }
       return create(); // zero
     }

     // MIN_VALUE / MIN_VALUE = 1, anything other a / MIN_VALUE is 0
     if (isMinValue(b)) {
       return divModByMinValue(a, computeRemainder);
     }

     // Normalize b to abs(b), keeping track of the parity in 'negative'.
     // We can do this because we have already ensured that b != MIN_VALUE.
     boolean negative = false;
     if (isNegative(b)) {
       b = BigLongLib.neg(b);
       negative = !negative;
     }

     // If b == 2^n, bpower will be n, otherwise it will be -1
     int bpower = powerOfTwo(b);

     // True if the original value of a is negative
     boolean aIsNegative = false;
     // True if the original value of a is Long.MIN_VALUE
     boolean aIsMinValue = false;

     /*
      * Normalize a to a positive value, keeping track of the sign change in
      * 'negative' (which tracks the sign of both a and b and is used to
      * determine the sign of the quotient) and 'aIsNegative' (which is used to
      * determine the sign of the remainder).
      *
      * For all values of a except MIN_VALUE, we can just negate a and modify
      * negative and aIsNegative appropriately. When a == MIN_VALUE, negation is
      * not possible without overflowing 64 bits, so instead of computing
      * abs(MIN_VALUE) / abs(b) we compute (abs(MIN_VALUE) - 1) / abs(b). The
      * only circumstance under which these quotients differ is when b is a power
      * of two, which will divide abs(MIN_VALUE) == 2^64 exactly. In this case,
      * we can get the proper result by shifting MIN_VALUE in unsigned fashion.
      *
      * We make a single copy of a before the first operation that needs to
      * modify its value.
      */
     boolean aIsCopy = false;
     if (isMinValue(a)) {
       aIsMinValue = true;
       aIsNegative = true;
       // If b is not a power of two, treat -a as MAX_VALUE (instead of the
       // actual value (MAX_VALUE + 1)).
       if (bpower == -1) {
         a = create(BigLongLib.Const.MAX_VALUE);
         aIsCopy = true;
         negative = !negative;
       } else {
         // Signed shift of MIN_VALUE produces the right answer
         BigLong c = BigLongLib.shr(a, bpower);
         if (negative) {
           negate(c);
         }
         if (computeRemainder) {
           remainder = create(); // zero
         }
         return c;
       }
     } else if (isNegative(a)) {
       aIsNegative = true;
       a = BigLongLib.neg(a);
       aIsCopy = true;
       negative = !negative;
     }

     // Now both a and b are non-negative

     // If b is a power of two, just shift
     if (bpower != -1) {
       return divModByShift(a, bpower, negative, aIsNegative, computeRemainder);
     }

     // if a < b, the quotient is 0 and the remainder is a
     if (BigLongLib.compare(a, b) < 0) {
       if (computeRemainder) {
         if (aIsNegative) {
           remainder = BigLongLib.neg(a);
         } else {
           remainder = create(a);
         }
       }
       return create(); // zero
     }

     // Generate the quotient using bit-at-a-time long division
     return divModHelper(aIsCopy ? a : create(a), b, negative, aIsNegative,
         aIsMinValue, computeRemainder);
   }

   protected static int getH(BigLong a) {
     if (LongLib.RUN_IN_JVM) {
       return a.h;
     }
     return getHNative(a);
   }

   protected static int getL(BigLong a) {
     if (LongLib.RUN_IN_JVM) {
       return a.l;
     }
     return getLNative(a);
   }

   protected static int getM(BigLong a) {
     if (LongLib.RUN_IN_JVM) {
       return a.m;
     }
     return getMNative(a);
   }

   protected static boolean isMinValue(BigLong a) {
     return getH(a) == SIGN_BIT_VALUE && getM(a) == 0 && getL(a) == 0;
   }

   protected static boolean isNegative(BigLong a) {
     return sign(a) != 0;
   }

   protected static boolean isZero(BigLong a) {
     return getL(a) == 0 && getM(a) == 0 && getH(a) == 0;
   }

   /**
    * a = -a
    */
   protected static void negate(BigLong a) {
     int neg0 = (~getL(a) + 1) & MASK;
     int neg1 = (~getM(a) + (neg0 == 0 ? 1 : 0)) & MASK;
     int neg2 = (~getH(a) + ((neg0 == 0 && neg1 == 0) ? 1 : 0)) & MASK_2;

     if (LongLib.RUN_IN_JVM) {
       a.l = neg0;
       a.m = neg1;
       a.h = neg2;
     } else {
       setL(a, neg0);
       setM(a, neg1);
       setH(a, neg2);
     }
   }

   /**
    * @return 0 if a is >= 0, 1 if a < 0.
    */
   protected static int sign(BigLong a) {
     return getH(a) >> (BITS2 - 1);
   }

   // Assumes a is non-negative
   protected static double toDoubleHelper(BigLong a) {
     return getL(a) + (getM(a) * TWO_PWR_22_DBL) + (getH(a) * TWO_PWR_44_DBL);
   }

   /**
    * Return the number of leading zeros of a long value.
    */
   // package-private for testing
   static int numberOfLeadingZeros(BigLong a) {
     int b2 = Integer.numberOfLeadingZeros(getH(a));
     if (b2 == 32) {
       int b1 = Integer.numberOfLeadingZeros(getM(a));
       if (b1 == 32) {
         return Integer.numberOfLeadingZeros(getL(a)) + 32;
       } else {
         return b1 + BITS2 - (32 - BITS);
       }
     } else {
       return b2 - (32 - BITS2);
     }
   }

   /**
    * Creates a long instance equal to 0.
    */
   private static BigLong create() {
     if (LongLib.RUN_IN_JVM) {
       return new BigLong();
     }
     return create0(0, 0, 0);
   }

   /**
    * Creates a long instance equal to a given long.
    */
   static BigLong create(BigLong a) {
     if (LongLib.RUN_IN_JVM) {
       BigLong b = new BigLong();
       b.l = getL(a);
       b.m = getM(a);
       b.h = getH(a);
       return b;
     }
     return create0(getL(a), getM(a), getH(a));
   }

   private static native BigLong create0(int l, int m, int h) /*-{
     return {l:l,m:m,h:h};
   }-*/;

   private static BigLong divModByMinValue(BigLong a, boolean computeRemainder) {
     // MIN_VALUE / MIN_VALUE == 1, remainder = 0
     // (a != MIN_VALUE) / MIN_VALUE == 0, remainder == a
     if (isMinValue(a)) {
       if (computeRemainder) {
         remainder = create(); // zero
       }
       return create(BigLongLib.Const.ONE);
     }
     if (computeRemainder) {
       remainder = create(a);
     }
     return create(); // zero
   }

   private static BigLong divModByShift(BigLong a, int bpower,
       boolean negative, boolean aIsNegative, boolean computeRemainder) {
     BigLong c = BigLongLib.shr(a, bpower);
     if (negative) {
       negate(c);
     }

     if (computeRemainder) {
       a = maskRight(a, bpower);
       if (aIsNegative) {
         remainder = BigLongLib.neg(a);
       } else {
         remainder = create(a);
       }
     }
     return c;
   }

   private static BigLong divModHelper(BigLong a, BigLong b,
       boolean negative, boolean aIsNegative, boolean aIsMinValue,
       boolean computeRemainder) {
     // Align the leading one bits of a and b by shifting b left
     int shift = numberOfLeadingZeros(b) - numberOfLeadingZeros(a);
     BigLong bshift = BigLongLib.shl(b, shift);

     BigLong quotient = create();
     while (shift >= 0) {
       boolean gte = trialSubtract(a, bshift);
       if (gte) {
         setBit(quotient, shift);
         if (isZero(a)) {
           break;
         }
       }

       toShru1(bshift);
       shift--;
     }

     if (negative) {
       negate(quotient);
     }

     if (computeRemainder) {
       if (aIsNegative) {
         remainder = BigLongLib.neg(a);
         if (aIsMinValue) {
           remainder = BigLongLib.sub(remainder, BigLongLib.Const.ONE);
         }
       } else {
         remainder = create(a);
       }
     }

     return quotient;
   }

   private static native int getHNative(BigLong a) /*-{
     return a.h;
   }-*/;

   private static native int getLNative(BigLong a) /*-{
     return a.l;
   }-*/;

   private static native int getMNative(BigLong a) /*-{
     return a.m;
   }-*/;

   /**
    * a &= ((1L << bits) - 1)
    */
   private static BigLong maskRight(BigLong a, int bits) {
     int b0, b1, b2;
     if (bits <= BITS) {
       b0 = getL(a) & ((1 << bits) - 1);
       b1 = b2 = 0;
     } else if (bits <= BITS01) {
       b0 = getL(a);
       b1 = getM(a) & ((1 << (bits - BITS)) - 1);
       b2 = 0;
     } else {
       b0 = getL(a);
       b1 = getM(a);
       b2 = getH(a) & ((1 << (bits - BITS01)) - 1);
     }

     return create(b0, b1, b2);
   }

   /**
    * Return the exact log base 2 of a, or -1 if a is not a power of two:
    *
    * <pre>
    * if (x == 2^n) {
    *   return n;
    * } else {
    *   return -1;
    * }
    * </pre>
    */
   private static int powerOfTwo(BigLong a) {
     // Power of two or 0
     int l = getL(a);
     if ((l & (l - 1)) != 0) {
       return -1;
     }
     int m = getM(a);
     if ((m & (m - 1)) != 0) {
       return -1;
     }
     int h = getH(a);
     if ((h & (h - 1)) != 0) {
       return -1;
     }
     if (h == 0 && m == 0 && l == 0) {
       return -1;
     }
     if (h == 0 && m == 0 && l != 0) {
       return Integer.numberOfTrailingZeros(l);
     }
     if (h == 0 && m != 0 && l == 0) {
       return Integer.numberOfTrailingZeros(m) + BITS;
     }
     if (h != 0 && m == 0 && l == 0) {
       return Integer.numberOfTrailingZeros(h) + BITS01;
     }

     return -1;
   }

   private static void setBit(BigLong a, int bit) {
     if (LongLib.RUN_IN_JVM) {
       if (bit < BITS) {
         a.l |= 0x1 << bit;
       } else if (bit < BITS01) {
         a.m |= 0x1 << (bit - BITS);
       } else {
         a.h |= 0x1 << (bit - BITS01);
       }
     } else {
       if (bit < BITS) {
         setBitL(a, bit);
       } else if (bit < BITS01) {
         setBitM(a, bit - BITS);
       } else {
         setBitH(a, bit - BITS01);
       }
     }
   }

   private static native void setBitH(BigLong a, int bit) /*-{
     a.h |= 1 << bit;
   }-*/;

   private static native void setBitL(BigLong a, int bit) /*-{
     a.l |= 1 << bit;
   }-*/;

   private static native void setBitM(BigLong a, int bit) /*-{
     a.m |= 1 << bit;
   }-*/;

   private static native void setH(BigLong a, int x) /*-{
     a.h = x;
   }-*/;

   private static native void setL(BigLong a, int x) /*-{
     a.l = x;
   }-*/;

   private static native void setM(BigLong a, int x) /*-{
     a.m = x;
   }-*/;

   /**
    * a >>= 1. Assumes a >= 0.
    */
   private static void toShru1(BigLong a) {
     int a1 = getM(a);
     int a2 = getH(a);
     int a0 = getL(a);

     if (LongLib.RUN_IN_JVM) {
       a.h = a2 >>> 1;
       a.m = (a1 >>> 1) | ((a2 & 0x1) << (BITS - 1));
       a.l = (a0 >>> 1) | ((a1 & 0x1) << (BITS - 1));
     } else {
       setH(a, a2 >>> 1);
       setM(a, (a1 >>> 1) | ((a2 & 0x1) << (BITS - 1)));
       setL(a, (a0 >>> 1) | ((a1 & 0x1) << (BITS - 1)));
     }
   }

   /**
    * Attempt to subtract b from a if a >= b:
    *
    * <pre>
    * if (a >= b) {
    *   a -= b;
    *   return true;
    * } else {
    *   return false;
    * }
    * </pre>
    */
   private static boolean trialSubtract(BigLong a, BigLong b) {
     // Early exit
     int sum2 = getH(a) - getH(b);
     if (sum2 < 0) {
       return false;
     }

     int sum0 = getL(a) - getL(b);
     int sum1 = getM(a) - getM(b) + (sum0 >> BITS);
     sum2 += (sum1 >> BITS);

     if (sum2 < 0) {
       return false;
     }

     if (LongLib.RUN_IN_JVM) {
       a.l = sum0 & MASK;
       a.m = sum1 & MASK;
       a.h = sum2 & MASK_2;
     } else {
       setL(a, sum0 & MASK);
       setM(a, sum1 & MASK);
       setH(a, sum2 & MASK_2);
     }

     return true;
   }

   /**
    * Not instantiable outside this package.
    */
   BigLongLibBase() {
   }
 }
	/*
	* Copyright 2010 Google Inc.
	*
	* Licensed 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 com.google.gwt.lang;

	/**
	* Implements a Java <code>long</code> in a way that can be translated to
	* JavaScript.
	*/
	class BigLongLibBase {

	/*
	* Implementation: A LongEmul containing three values {l, m, h} (low, middle,
	* high) such that (x.l + ((long) x.m << 22) + ((long) x.h << 44)) is equal to
	* the original long integer. The constant 22 is chosen since some browsers
	* are faster when operating on integers of 24 bits or less.
	*
	* By convention, we expect and maintain that the upper bits of each word be
	* zeroed.
	*
	* Note that this class must be careful using type "long". Being the
	* implementation of the long type for Production Mode, any place it uses a
	* long is not usable in Production Mode. There is currently one such method:
	* {@link LongLib#getAsLongArray}.
	*/
	static class BigLong {
	int l, m, h;
	}


	// Note that the {@link LonghLib#mul} method implicitly depends on the
	// specific value BITS == 22
	protected static final int BITS = 22;
	protected static final int BITS01 = 2 * BITS;
	protected static final int BITS2 = 64 - BITS01;
	protected static final int MASK = (1 << BITS) - 1;
	protected static final int MASK_2 = (1 << BITS2) - 1;
	protected static BigLong remainder;

	protected static final int SIGN_BIT = BITS2 - 1;
	protected static final int SIGN_BIT_VALUE = 1 << SIGN_BIT;
	protected static final double TWO_PWR_15_DBL = 0x8000;
	protected static final double TWO_PWR_16_DBL = 0x10000;
	protected static final double TWO_PWR_22_DBL = 0x400000;
	protected static final double TWO_PWR_31_DBL = TWO_PWR_16_DBL
	* TWO_PWR_15_DBL;
	protected static final double TWO_PWR_32_DBL = TWO_PWR_16_DBL
	* TWO_PWR_16_DBL;
	protected static final double TWO_PWR_44_DBL = TWO_PWR_22_DBL
	* TWO_PWR_22_DBL;
	protected static final double TWO_PWR_63_DBL = TWO_PWR_32_DBL
	* TWO_PWR_31_DBL;

	protected static BigLong create(int value) {
	int a0 = value & MASK;
	int a1 = (value >> BITS) & MASK;
	int a2 = (value < 0) ? MASK_2 : 0;

	if (LongLib.RUN_IN_JVM) {
	BigLong a = new BigLong();
	a.l = a0;
	a.m = a1;
	a.h = a2;
	return a;
	}
	return create0(a0, a1, a2);
	}

	protected static BigLong create(int a0, int a1, int a2) {
	if (LongLib.RUN_IN_JVM) {
	BigLong a = new BigLong();
	a.l = a0;
	a.m = a1;
	a.h = a2;
	return a;
	}
	return create0(a0, a1, a2);
	}

	protected static BigLong divMod(BigLong a, BigLong b,
	boolean computeRemainder) {
	if (isZero(b)) {
	throw new ArithmeticException("divide by zero");
	}
	if (isZero(a)) {
	if (computeRemainder) {
	remainder = create(); // zero
	}
	return create(); // zero
	}

	// MIN_VALUE / MIN_VALUE = 1, anything other a / MIN_VALUE is 0
	if (isMinValue(b)) {
	return divModByMinValue(a, computeRemainder);
	}

	// Normalize b to abs(b), keeping track of the parity in 'negative'.
	// We can do this because we have already ensured that b != MIN_VALUE.
	boolean negative = false;
	if (isNegative(b)) {
	b = BigLongLib.neg(b);
	negative = !negative;
	}

	// If b == 2^n, bpower will be n, otherwise it will be -1
	int bpower = powerOfTwo(b);

	// True if the original value of a is negative
	boolean aIsNegative = false;
	// True if the original value of a is Long.MIN_VALUE
	boolean aIsMinValue = false;

	/*
	* Normalize a to a positive value, keeping track of the sign change in
	* 'negative' (which tracks the sign of both a and b and is used to
	* determine the sign of the quotient) and 'aIsNegative' (which is used to
	* determine the sign of the remainder).
	*
	* For all values of a except MIN_VALUE, we can just negate a and modify
	* negative and aIsNegative appropriately. When a == MIN_VALUE, negation is
	* not possible without overflowing 64 bits, so instead of computing
	* abs(MIN_VALUE) / abs(b) we compute (abs(MIN_VALUE) - 1) / abs(b). The
	* only circumstance under which these quotients differ is when b is a power
	* of two, which will divide abs(MIN_VALUE) == 2^64 exactly. In this case,
	* we can get the proper result by shifting MIN_VALUE in unsigned fashion.
	*
	* We make a single copy of a before the first operation that needs to
	* modify its value.
	*/
	boolean aIsCopy = false;
	if (isMinValue(a)) {
	aIsMinValue = true;
	aIsNegative = true;
	// If b is not a power of two, treat -a as MAX_VALUE (instead of the
	// actual value (MAX_VALUE + 1)).
	if (bpower == -1) {
	a = create(BigLongLib.Const.MAX_VALUE);
	aIsCopy = true;
	negative = !negative;
	} else {
	// Signed shift of MIN_VALUE produces the right answer
	BigLong c = BigLongLib.shr(a, bpower);
	if (negative) {
	negate(c);
	}
	if (computeRemainder) {
	remainder = create(); // zero
	}
	return c;
	}
	} else if (isNegative(a)) {
	aIsNegative = true;
	a = BigLongLib.neg(a);
	aIsCopy = true;
	negative = !negative;
	}

	// Now both a and b are non-negative

	// If b is a power of two, just shift
	if (bpower != -1) {
	return divModByShift(a, bpower, negative, aIsNegative, computeRemainder);
	}

	// if a < b, the quotient is 0 and the remainder is a
	if (BigLongLib.compare(a, b) < 0) {
	if (computeRemainder) {
	if (aIsNegative) {
	remainder = BigLongLib.neg(a);
	} else {
	remainder = create(a);
	}
	}
	return create(); // zero
	}

	// Generate the quotient using bit-at-a-time long division
	return divModHelper(aIsCopy ? a : create(a), b, negative, aIsNegative,
	aIsMinValue, computeRemainder);
	}

	protected static int getH(BigLong a) {
	if (LongLib.RUN_IN_JVM) {
	return a.h;
	}
	return getHNative(a);
	}

	protected static int getL(BigLong a) {
	if (LongLib.RUN_IN_JVM) {
	return a.l;
	}
	return getLNative(a);
	}

	protected static int getM(BigLong a) {
	if (LongLib.RUN_IN_JVM) {
	return a.m;
	}
	return getMNative(a);
	}

	protected static boolean isMinValue(BigLong a) {
	return getH(a) == SIGN_BIT_VALUE && getM(a) == 0 && getL(a) == 0;
	}

	protected static boolean isNegative(BigLong a) {
	return sign(a) != 0;
	}

	protected static boolean isZero(BigLong a) {
	return getL(a) == 0 && getM(a) == 0 && getH(a) == 0;
	}

	/**
	* a = -a
	*/
	protected static void negate(BigLong a) {
	int neg0 = (~getL(a) + 1) & MASK;
	int neg1 = (~getM(a) + (neg0 == 0 ? 1 : 0)) & MASK;
	int neg2 = (~getH(a) + ((neg0 == 0 && neg1 == 0) ? 1 : 0)) & MASK_2;

	if (LongLib.RUN_IN_JVM) {
	a.l = neg0;
	a.m = neg1;
	a.h = neg2;
	} else {
	setL(a, neg0);
	setM(a, neg1);
	setH(a, neg2);
	}
	}

	/**
	* @return 0 if a is >= 0, 1 if a < 0.
	*/
	protected static int sign(BigLong a) {
	return getH(a) >> (BITS2 - 1);
	}

	// Assumes a is non-negative
	protected static double toDoubleHelper(BigLong a) {
	return getL(a) + (getM(a) * TWO_PWR_22_DBL) + (getH(a) * TWO_PWR_44_DBL);
	}

	/**
	* Return the number of leading zeros of a long value.
	*/
	// package-private for testing
	static int numberOfLeadingZeros(BigLong a) {
	int b2 = Integer.numberOfLeadingZeros(getH(a));
	if (b2 == 32) {
	int b1 = Integer.numberOfLeadingZeros(getM(a));
	if (b1 == 32) {
	return Integer.numberOfLeadingZeros(getL(a)) + 32;
	} else {
	return b1 + BITS2 - (32 - BITS);
	}
	} else {
	return b2 - (32 - BITS2);
	}
	}

	/**
	* Creates a long instance equal to 0.
	*/
	private static BigLong create() {
	if (LongLib.RUN_IN_JVM) {
	return new BigLong();
	}
	return create0(0, 0, 0);
	}

	/**
	* Creates a long instance equal to a given long.
	*/
	static BigLong create(BigLong a) {
	if (LongLib.RUN_IN_JVM) {
	BigLong b = new BigLong();
	b.l = getL(a);
	b.m = getM(a);
	b.h = getH(a);
	return b;
	}
	return create0(getL(a), getM(a), getH(a));
	}

	private static native BigLong create0(int l, int m, int h) /*-{
	return {l:l,m:m,h:h};
	}-*/;

	private static BigLong divModByMinValue(BigLong a, boolean computeRemainder) {
	// MIN_VALUE / MIN_VALUE == 1, remainder = 0
	// (a != MIN_VALUE) / MIN_VALUE == 0, remainder == a
	if (isMinValue(a)) {
	if (computeRemainder) {
	remainder = create(); // zero
	}
	return create(BigLongLib.Const.ONE);
	}
	if (computeRemainder) {
	remainder = create(a);
	}
	return create(); // zero
	}

	private static BigLong divModByShift(BigLong a, int bpower,
	boolean negative, boolean aIsNegative, boolean computeRemainder) {
	BigLong c = BigLongLib.shr(a, bpower);
	if (negative) {
	negate(c);
	}

	if (computeRemainder) {
	a = maskRight(a, bpower);
	if (aIsNegative) {
	remainder = BigLongLib.neg(a);
	} else {
	remainder = create(a);
	}
	}
	return c;
	}

	private static BigLong divModHelper(BigLong a, BigLong b,
	boolean negative, boolean aIsNegative, boolean aIsMinValue,
	boolean computeRemainder) {
	// Align the leading one bits of a and b by shifting b left
	int shift = numberOfLeadingZeros(b) - numberOfLeadingZeros(a);
	BigLong bshift = BigLongLib.shl(b, shift);

	BigLong quotient = create();
	while (shift >= 0) {
	boolean gte = trialSubtract(a, bshift);
	if (gte) {
	setBit(quotient, shift);
	if (isZero(a)) {
	break;
	}
	}

	toShru1(bshift);
	shift--;
	}

	if (negative) {
	negate(quotient);
	}

	if (computeRemainder) {
	if (aIsNegative) {
	remainder = BigLongLib.neg(a);
	if (aIsMinValue) {
	remainder = BigLongLib.sub(remainder, BigLongLib.Const.ONE);
	}
	} else {
	remainder = create(a);
	}
	}

	return quotient;
	}

	private static native int getHNative(BigLong a) /*-{
	return a.h;
	}-*/;

	private static native int getLNative(BigLong a) /*-{
	return a.l;
	}-*/;

	private static native int getMNative(BigLong a) /*-{
	return a.m;
	}-*/;

	/**
	* a &= ((1L << bits) - 1)
	*/
	private static BigLong maskRight(BigLong a, int bits) {
	int b0, b1, b2;
	if (bits <= BITS) {
	b0 = getL(a) & ((1 << bits) - 1);
	b1 = b2 = 0;
	} else if (bits <= BITS01) {
	b0 = getL(a);
	b1 = getM(a) & ((1 << (bits - BITS)) - 1);
	b2 = 0;
	} else {
	b0 = getL(a);
	b1 = getM(a);
	b2 = getH(a) & ((1 << (bits - BITS01)) - 1);
	}

	return create(b0, b1, b2);
	}

	/**
	* Return the exact log base 2 of a, or -1 if a is not a power of two:
	*
	* <pre>
	* if (x == 2^n) {
	* return n;
	* } else {
	* return -1;
	* }
	* </pre>
	*/
	private static int powerOfTwo(BigLong a) {
	// Power of two or 0
	int l = getL(a);
	if ((l & (l - 1)) != 0) {
	return -1;
	}
	int m = getM(a);
	if ((m & (m - 1)) != 0) {
	return -1;
	}
	int h = getH(a);
	if ((h & (h - 1)) != 0) {
	return -1;
	}
	if (h == 0 && m == 0 && l == 0) {
	return -1;
	}
	if (h == 0 && m == 0 && l != 0) {
	return Integer.numberOfTrailingZeros(l);
	}
	if (h == 0 && m != 0 && l == 0) {
	return Integer.numberOfTrailingZeros(m) + BITS;
	}
	if (h != 0 && m == 0 && l == 0) {
	return Integer.numberOfTrailingZeros(h) + BITS01;
	}

	return -1;
	}

	private static void setBit(BigLong a, int bit) {
	if (LongLib.RUN_IN_JVM) {
	if (bit < BITS) {
	a.l \|= 0x1 << bit;
	} else if (bit < BITS01) {
	a.m \|= 0x1 << (bit - BITS);
	} else {
	a.h \|= 0x1 << (bit - BITS01);
	}
	} else {
	if (bit < BITS) {
	setBitL(a, bit);
	} else if (bit < BITS01) {
	setBitM(a, bit - BITS);
	} else {
	setBitH(a, bit - BITS01);
	}
	}
	}

	private static native void setBitH(BigLong a, int bit) /*-{
	a.h \|= 1 << bit;
	}-*/;

	private static native void setBitL(BigLong a, int bit) /*-{
	a.l \|= 1 << bit;
	}-*/;

	private static native void setBitM(BigLong a, int bit) /*-{
	a.m \|= 1 << bit;
	}-*/;

	private static native void setH(BigLong a, int x) /*-{
	a.h = x;
	}-*/;

	private static native void setL(BigLong a, int x) /*-{
	a.l = x;
	}-*/;

	private static native void setM(BigLong a, int x) /*-{
	a.m = x;
	}-*/;

	/**
	* a >>= 1. Assumes a >= 0.
	*/
	private static void toShru1(BigLong a) {
	int a1 = getM(a);
	int a2 = getH(a);
	int a0 = getL(a);

	if (LongLib.RUN_IN_JVM) {
	a.h = a2 >>> 1;
	a.m = (a1 >>> 1) \| ((a2 & 0x1) << (BITS - 1));
	a.l = (a0 >>> 1) \| ((a1 & 0x1) << (BITS - 1));
	} else {
	setH(a, a2 >>> 1);
	setM(a, (a1 >>> 1) \| ((a2 & 0x1) << (BITS - 1)));
	setL(a, (a0 >>> 1) \| ((a1 & 0x1) << (BITS - 1)));
	}
	}

	/**
	* Attempt to subtract b from a if a >= b:
	*
	* <pre>
	* if (a >= b) {
	* a -= b;
	* return true;
	* } else {
	* return false;
	* }
	* </pre>
	*/
	private static boolean trialSubtract(BigLong a, BigLong b) {
	// Early exit
	int sum2 = getH(a) - getH(b);
	if (sum2 < 0) {
	return false;
	}

	int sum0 = getL(a) - getL(b);
	int sum1 = getM(a) - getM(b) + (sum0 >> BITS);
	sum2 += (sum1 >> BITS);

	if (sum2 < 0) {
	return false;
	}

	if (LongLib.RUN_IN_JVM) {
	a.l = sum0 & MASK;
	a.m = sum1 & MASK;
	a.h = sum2 & MASK_2;
	} else {
	setL(a, sum0 & MASK);
	setM(a, sum1 & MASK);
	setH(a, sum2 & MASK_2);
	}

	return true;
	}

	/**
	* Not instantiable outside this package.
	*/
	BigLongLibBase() {
	}
	}