content: package com.alibaba.fastjson2.util;
  
  import com.alibaba.fastjson2.JSONException;
  
  final class MutableBigInteger {
      private static final int[][] BIG_TEN_POWERS_MAGIC_TABLE = {
              {1},
              {10},
              {100},
              {1000},
              {10000},
              {100000},
              {1000000},
              {10000000},
              {100000000},
              {1000000000},
              {2, 1410065408},
              {23, 1215752192},
              {232, -727379968},
              {2328, 1316134912},
              {23283, 276447232},
              {232830, -1530494976},
              {2328306, 1874919424},
              {23283064, 1569325056},
              {232830643, -1486618624},
              {-1966660860, -1981284352},
              {5, 1808227885, 1661992960},
              {54, 902409669, -559939584},
              {542, 434162106, -1304428544},
              {5421, 46653770, -159383552},
              {54210, 466537709, -1593835520},
              {542101, 370409800, 1241513984},
              {5421010, -590869294, -469762048},
              {54210108, -1613725636, -402653184},
              {542101086, 1042612833, 268435456},
              {1, 1126043566, 1836193738, -1610612736},
              {12, -1624466224, 1182068202, 1073741824},
              {126, 935206946, -1064219866, -2147483648},
              {1262, 762134875, -2052264063, 0},
              {12621, -968585837, 952195850, 0},
              {126217, -1095923776, 932023908, 0},
              {1262177, 1925664130, 730304488, 0},
              {12621774, 2076772117, -1286889712, 0},
              {126217744, -707115303, 16004768, 0},
              {1262177448, 1518781562, 160047680, 0},
              {2, -263127405, -1992053564, 1600476800, 0},
              {29, 1663693251, 1554300843, -1175101184, 0},
              {293, -542936671, -1636860747, 1133890048, 0},
              {2938, -1134399408, 811261716, -1546001408, 0},
              {29387, 1540907809, -477317426, 1719855104, 0},
              {293873, -1770791086, -478206960, 18681856, 0},
              {2938735, -528041668, -487102304, 186818560, 0},
              {29387358, -985449376, -576055744, 1868185600, 0},
              {293873587, -1264559160, -1465590140, 1501986816, 0},
              {-1356231419, 239310294, -1770999509, 2134966272, 0},
              {6, -677412302, -1901864351, -530125902, -125173760, 0},
              {68, 1815811577, -1838774318, -1006291715, -1251737600, 0},
              {684, 978246591, -1207873989, -1472982551, 367525888, 0},
              {6842, 1192531325, 806162004, -1844923622, -619708416, 0},
              {68422, -959588637, -528314547, -1269367028, -1902116864, 0},
              {684227, -1005951770, -988178167, 191231613, -1841299456, 0},
              {6842277, -1469583101, -1291847078, 1912316135, -1233125376, 0},
              {68422776, -1810929116, -33568888, 1943292173, 553648128, 0},
              {684227765, -929421967, -335688876, -2041914749, 1241513984, 0},
              {1, -1747656935, -704285069, 938078541, 1055688992, -469762048, 0},
              {15, -296700158, 1547083904, 790850820, 1966955336, -402653184, 0},
              {159, 1327965719, -1709030143, -681426388, -1805283111, 268435456, 0},
              {1593, 394755308, 89567762, 1775670717, -872961926, -1610612736, 0},
              {15930, -347414216, 895677624, 576837993, -139684662, 1073741824, 0},
              {159309, 820825138, 366841649, 1473412643, -1396846618, -2147483648, 0}
      };
  
      static final long LONG_MASK = 0xffffffffL;
      static final int KNUTH_POW2_THRESH_LEN = 6;
      static final int KNUTH_POW2_THRESH_ZEROS = 3;
  
      static long divideKnuthLong(long intCompact, int ql, int scale) {
          int[] pow10 = MutableBigInteger.BIG_TEN_POWERS_MAGIC_TABLE[scale];
          int[] magic_a, magic_b;
          int v0 = (int) (intCompact >>> 32), v1 = (int) intCompact;
          if (ql <= 0) {
              int n = -ql;
              int nInts = n >>> 5;
              int nBits = n & 0x1f;
              if (nBits == 0) {
                  magic_a = new int[2 + nInts];
                  magic_a[0] = v0;
                  magic_a[1] = v1;
              } else {
                  int i = 0;
                  int nBits2 = 32 - nBits;
                  int highBits = v0 >>> nBits2;
                  if (highBits != 0) {
                      magic_a = new int[3 + nInts];
                      magic_a[i++] = highBits;
                  } else {
                      magic_a = new int[2 + nInts];
                  }
                  magic_a[i] = v0 << nBits | v1 >>> nBits2;
                  magic_a[i + 1] = v1 << nBits;
              }
              magic_b = pow10;
          } else {
              magic_a = new int[]{v0, v1};
              magic_b = shiftLeft(pow10, ql);
          }
  
          if (magic_a.length < magic_b.length) {
              return 0;
          }
  
          if (magic_a.length == magic_b.length && equals(magic_a, magic_b)) {
              return 1;
          }
  
          // Special case one word divisor
          if (magic_b.length == 1) {
              return divideOneWordLong(magic_a, magic_b[0]);
          }
  
          // Cancel common powers of two if we're above the KNUTH_POW2_* thresholds
          if (magic_a.length >= KNUTH_POW2_THRESH_LEN) {
              int trailingZeroBits = Math.min(getLowestSetBit(magic_a), getLowestSetBit(magic_b));
              if (trailingZeroBits >= KNUTH_POW2_THRESH_ZEROS * 32) {
                  throw new JSONException("assert error");
              }
          }
  
          int intLen = magic_a.length;
          // assert div.intLen > 1
          // D1 normalize the divisor
          int shift = Integer.numberOfLeadingZeros(magic_b[0]);
          // Copy divisor value to protect divisor
          final int dlen = magic_b.length;
          int[] divisor;
          int[] remarr;
          int nlen = intLen;
          if (shift > 0) {
              divisor = new int[dlen];
              primitiveLeftShift(magic_b, shift, divisor, 0);
              if (Integer.numberOfLeadingZeros(magic_a[0]) >= shift) {
                  remarr = new int[intLen + 1];
                  primitiveLeftShift(magic_a, shift, remarr, 1);
              } else {
                  remarr = new int[intLen + 2];
                  nlen++;
                  int rFrom = 0;
                  int c = 0;
                  int n2 = 32 - shift;
                  for (int i = 1; i < intLen + 1; i++, rFrom++) {
                      int b = c;
                      c = magic_a[rFrom];
                      remarr[i] = (b << shift) | (c >>> n2);
                  }
                  remarr[intLen + 1] = c << shift;
              }
          } else {
              divisor = magic_b.clone();
              remarr = new int[intLen + 1];
              System.arraycopy(magic_a, 0, remarr, 1, intLen);
          }
  
          final int limit = nlen - dlen + 1;
          int[] q = new int[limit];
  
          // Insert leading 0 in rem
          remarr[0] = 0;
  
          int dh = divisor[0];
          long dhLong = dh & LONG_MASK;
          int dl = divisor[1];
  
          // D2 Initialize j
          for (int j = 0; j < limit - 1; j++) {
              // D3 Calculate qhat
              // estimate qhat
              int qhat;
              int qrem;
              boolean skipCorrection = false;
              int nh = remarr[j];
              int nh2 = nh + 0x80000000;
              int nm = remarr[j + 1];
  
              if (nh == dh) {
                  qhat = ~0;
                  qrem = nh + nm;
                  skipCorrection = qrem + 0x80000000 < nh2;
              } else {
                  long nChunk = (((long) nh) << 32) | (nm & LONG_MASK);
                  qhat = (int) Long.divideUnsigned(nChunk, dhLong);
                  qrem = (int) Long.remainderUnsigned(nChunk, dhLong);
              }
  
              if (qhat == 0) {
                  continue;
              }
  
              if (!skipCorrection) { // Correct qhat
                  long nl = remarr[j + 2] & LONG_MASK;
                  long rs = ((qrem & LONG_MASK) << 32) | nl;
                  long estProduct = (dl & LONG_MASK) * (qhat & LONG_MASK);
  
                  if (unsignedLongCompare(estProduct, rs)) {
                      qhat--;
                      qrem = (int) ((qrem & LONG_MASK) + dhLong);
                      if ((qrem & LONG_MASK) >= dhLong) {
                          estProduct -= (dl & LONG_MASK);
                          rs = ((qrem & LONG_MASK) << 32) | nl;
                          if (unsignedLongCompare(estProduct, rs)) {
                              qhat--;
                          }
                      }
                  }
              }
  
              // D4 Multiply and subtract
              remarr[j] = 0;
              int borrow; // = mulsub(remarr, divisor, qhat, dlen, j);
              {
                  long xLong = qhat & LONG_MASK;
                  long carry = 0;
                  int offset = j + dlen;
  
                  for (int k = dlen - 1; k >= 0; k--) {
                      long product = (divisor[k] & LONG_MASK) * xLong + carry;
                      long difference = remarr[offset] - product;
                      remarr[offset--] = (int) difference;
                      carry = (product >>> 32)
                              + (((difference & LONG_MASK) >
                              (((~(int) product) & LONG_MASK))) ? 1 : 0);
                  }
                  borrow = (int) carry;
              }
  
              // D5 Test remainder
              if (borrow + 0x80000000 > nh2) {
                  // D6 Add back
                  divadd(divisor, remarr, j + 1);
                  qhat--;
              }
  
              // Store the quotient digit
              q[j] = qhat;
          } // D7 loop on j
          // D3 Calculate qhat
          // estimate qhat
          int qhat;
          int qrem;
          boolean skipCorrection = false;
          int nh = remarr[limit - 1];
          int nh2 = nh + 0x80000000;
          int nm = remarr[limit];
  
          if (nh == dh) {
              qhat = ~0;
              qrem = nh + nm;
              skipCorrection = qrem + 0x80000000 < nh2;
          } else {
              long nChunk = (((long) nh) << 32) | (nm & LONG_MASK);
              qhat = (int) Long.divideUnsigned(nChunk, dhLong);
              qrem = (int) Long.remainderUnsigned(nChunk, dhLong);
          }
          if (qhat != 0) {
              if (!skipCorrection) { // Correct qhat
                  long nl = remarr[limit + 1] & LONG_MASK;
                  long rs = ((qrem & LONG_MASK) << 32) | nl;
                  long estProduct = (dl & LONG_MASK) * (qhat & LONG_MASK);
  
                  if (unsignedLongCompare(estProduct, rs)) {
                      qhat--;
                      qrem = (int) ((qrem & LONG_MASK) + dhLong);
                      if ((qrem & LONG_MASK) >= dhLong) {
                          estProduct -= (dl & LONG_MASK);
                          rs = ((qrem & LONG_MASK) << 32) | nl;
                          if (unsignedLongCompare(estProduct, rs)) {
                              qhat--;
                          }
                      }
                  }
              }
  
              // D4 Multiply and subtract
              int borrow;
              remarr[limit - 1] = 0;
              {
                  // mulsubBorrow
                  int offset = limit - 1 + dlen;
                  long xLong = qhat & LONG_MASK;
                  long carry = 0;
                  for (int j = dlen - 1; j >= 0; j--) {
                      long product = (divisor[j] & LONG_MASK) * xLong + carry;
                      long difference = remarr[offset--] - product;
                      carry = (product >>> 32)
                              + (((difference & LONG_MASK) >
                              (((~(int) product) & LONG_MASK))) ? 1 : 0);
                  }
                  borrow = (int) carry;
              }
  
              // D5 Test remainder
              if (borrow + 0x80000000 > nh2) {
                  // D6 Add back
                  qhat--;
              }
  
              // Store the quotient digit
              q[(limit - 1)] = qhat;
          }
  
          int index = 0;
          while (index < limit && q[index] == 0) {
              index++;
          }
          if (limit == index) {
              return 0;
          }
          return ((q[limit - 2] & LONG_MASK) << 32) + (q[limit - 1] & LONG_MASK);
      }
  
      private static boolean equals(int[] magic_a, int[] magic_b) {
          boolean equals = true;
          // Add Integer.MIN_VALUE to make the comparison act as unsigned integer
          // comparison.
          for (int i = 0, j = 0; i < magic_a.length; i++, j++) {
              if (magic_a[i] + 0x80000000 != magic_b[j] + 0x80000000) {
                  return false;
              }
          }
          return true;
      }
  
      private static int[] shiftLeft(int[] mag, int n) {
          int nInts = n >>> 5;
          int nBits = n & 0x1f;
          int magLen = mag.length;
          int[] newMag;
          if (nBits == 0) {
              newMag = new int[magLen + nInts];
              System.arraycopy(mag, 0, newMag, 0, magLen);
          } else {
              int i = 0;
              int nBits2 = 32 - nBits;
              int highBits = mag[0] >>> nBits2;
              if (highBits != 0) {
                  newMag = new int[magLen + nInts + 1];
                  newMag[i++] = highBits;
              } else {
                  newMag = new int[magLen + nInts];
              }
              int j = 0;
              while (j < magLen - 1) {
                  newMag[i++] = mag[j++] << nBits | mag[j] >>> nBits2;
              }
              newMag[i] = mag[j] << nBits;
          }
          return newMag;
      }
  
      private static int getLowestSetBit(int[] value) {
          if (value.length == 0) {
              return -1;
          }
          int j = value.length - 1, b;
          while ((j > 0) && (value[j] == 0)) {
              j--;
          }
          b = value[j];
          if (b == 0) {
              return -1;
          }
          return ((value.length - 1 - j) << 5) + Integer.numberOfTrailingZeros(b);
      }
  
      private static long divideOneWordLong(int[] value, int divisor) {
          long divisorLong = divisor & LONG_MASK;
          int intLen = value.length;
  
          // Special case of one word dividend
          if (value.length == 1) {
              return Integer.divideUnsigned(value[0], divisor);
          }
  
          int[] qValue = new int[intLen];
          long rem = 0;
          for (int xlen = intLen; xlen > 0; xlen--) {
              long dividendEstimate = (rem << 32) |
                      (value[intLen - xlen] & LONG_MASK);
              int q = (int) Long.divideUnsigned(dividendEstimate, divisorLong);
              rem = Long.remainderUnsigned(dividendEstimate, divisorLong);
              qValue[intLen - xlen] = q;
          }
  
          return longValue(qValue, intLen);
      }
  
      private static void primitiveLeftShift(int[] val, int n, int[] result, int resFrom) {
          int n2 = 32 - n;
          final int m = val.length - 1;
          int b = val[0];
          for (int i = 0; i < m; i++) {
              int c = val[i + 1];
              result[resFrom + i] = (b << n) | (c >>> n2);
              b = c;
          }
          result[resFrom + m] = b << n;
      }
  
      private static long longValue(int[] value, int intLen) {
          if (intLen == 0) {
              return 0;
          }
  
          int index = 0;
          while (index < intLen && value[index] == 0) {
              index++;
          }
          if (intLen == index) {
              return 0;
          }
          return ((value[intLen - 2] & LONG_MASK) << 32)
                  + (value[intLen - 1] & LONG_MASK);
      }
  
      private static boolean unsignedLongCompare(long one, long two) {
          return (one + Long.MIN_VALUE) > (two + Long.MIN_VALUE);
      }
  
      private static int divadd(int[] a, int[] result, int offset) {
          long carry = 0;
  
          for (int j = a.length - 1; j >= 0; j--) {
              long sum = (a[j] & LONG_MASK) +
                      (result[j + offset] & LONG_MASK) + carry;
              result[j + offset] = (int) sum;
              carry = sum >>> 32;
          }
          return (int) carry;
      }
  }
  