/*
 * Copyright 2015 MongoDB, 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.
 */

#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <ctype.h>

#include "bson-decimal128.h"
#include "bson-types.h"
#include "bson-macros.h"
#include "bson-string.h"


#define BSON_DECIMAL128_EXPONENT_MAX 6111
#define BSON_DECIMAL128_EXPONENT_MIN -6176
#define BSON_DECIMAL128_EXPONENT_BIAS 6176
#define BSON_DECIMAL128_MAX_DIGITS 34

#define BSON_DECIMAL128_SET_NAN(dec) \
   do { (dec).high = 0x7c00000000000000ull; (dec).low = 0; } while (0);
#define BSON_DECIMAL128_SET_INF(dec, isneg) \
   do { \
      (dec).high = 0x7800000000000000ull + 0x8000000000000000ull * (isneg); \
      (dec).low = 0; \
   } while (0);

/**
 * _bson_uint128_t:
 *
 * This struct represents a 128 bit integer.
 */
typedef struct
{
   uint32_t parts[4]; /* 32-bit words stored high to low. */
} _bson_uint128_t;


/**
 *------------------------------------------------------------------------------
 *
 * _bson_uint128_divide1B --
 *
 *    This function divides a #_bson_uint128_t by 1000000000 (1 billion) and
 *    computes the quotient and remainder.
 *
 *    The remainder will contain 9 decimal digits for conversion to string.
 *
 * @value     The #_bson_uint128_t operand.
 * @quotient  A pointer to store the #_bson_uint128_t quotient.
 * @rem       A pointer to store the #uint64_t remainder.
 *
 * Returns:
 *    The quotient at @quotient and the remainder at @rem.
 *
 * Side effects:
 *    None.
 *
 *------------------------------------------------------------------------------
 */
static void
_bson_uint128_divide1B (_bson_uint128_t  value,    /* IN */
                        _bson_uint128_t *quotient, /* OUT */
                        uint32_t        *rem) /* OUT */
{
   const uint32_t DIVISOR = 1000 * 1000 * 1000;
   uint64_t _rem = 0;
   int i = 0;

   if (!value.parts[0] && !value.parts[1] &&
       !value.parts[2] && !value.parts[3]) {
      *quotient = value;
      *rem = 0;
      return;
   }


   for (i = 0; i <= 3; i++) {
      _rem <<= 32;  /* Adjust remainder to match value of next dividend */
      _rem += value.parts[i];                      /* Add the divided to _rem */
      value.parts[i] = (uint32_t)(_rem / DIVISOR);
      _rem %= DIVISOR;                             /* Store the remainder */
   }

   *quotient = value;
   *rem = _rem;
}


/**
 *------------------------------------------------------------------------------
 *
 * bson_decimal128_to_string --
 *
 *    This function converts a BID formatted decimal128 value to string,
 *    accepting a &bson_decimal128_t as @dec.  The string is stored at @str.
 *
 * @dec : The BID formatted decimal to convert.
 * @str : The output decimal128 string. At least %BSON_DECIMAL128_STRING characters.
 *
 * Returns:
 *    None.
 *
 * Side effects:
 *    None.
 *
 *------------------------------------------------------------------------------
 */
void
bson_decimal128_to_string (const bson_decimal128_t *dec,        /* IN  */
                           char                    *str)        /* OUT */
{
   uint32_t COMBINATION_MASK = 0x1f;   /* Extract least significant 5 bits */
   uint32_t EXPONENT_MASK = 0x3fff;    /* Extract least significant 14 bits */
   uint32_t COMBINATION_INFINITY = 30; /* Value of combination field for Inf */
   uint32_t COMBINATION_NAN = 31;      /* Value of combination field for NaN */
   uint32_t EXPONENT_BIAS = 6176;      /* decimal128 exponent bias */

   char *str_out = str;                /* output pointer in string */
   char significand_str[35];           /* decoded significand digits */


   /* Note: bits in this routine are referred to starting at 0, */
   /* from the sign bit, towards the coefficient. */
   uint32_t high;                    /* bits 0 - 31 */
   uint32_t midh;                    /* bits 32 - 63 */
   uint32_t midl;                    /* bits 64 - 95 */
   uint32_t low;                     /* bits 96 - 127 */
   uint32_t combination;             /* bits 1 - 5 */
   uint32_t biased_exponent;         /* decoded biased exponent (14 bits) */
   uint32_t significand_digits = 0;  /* the number of significand digits */
   uint32_t significand[36] = { 0 }; /* the base-10 digits in the significand */
   uint32_t *significand_read = significand; /* read pointer into significand */
   int32_t exponent;                 /* unbiased exponent */
   int32_t scientific_exponent;      /* the exponent if scientific notation is
                                      * used */
   bool is_zero = false;             /* true if the number is zero */

   uint8_t significand_msb;          /* the most signifcant significand bits (50-46) */
   _bson_uint128_t significand128;   /* temporary storage for significand decoding */
   size_t i;                         /* indexing variables */
   int j, k;

   memset (significand_str, 0, sizeof (significand_str));

   if ((int64_t)dec->high < 0) {  /* negative */
      *(str_out++) = '-';
   }

   low = (uint32_t)dec->low,
   midl = (uint32_t)(dec->low >> 32),
   midh = (uint32_t)dec->high,
   high = (uint32_t)(dec->high >> 32);

   /* Decode combination field and exponent */
   combination = (high >> 26) & COMBINATION_MASK;

   if (BSON_UNLIKELY ((combination >> 3) == 3)) {
      /* Check for 'special' values */
      if (combination == COMBINATION_INFINITY) {  /* Infinity */
         strcpy (str_out, "Inf");
         return;
      } else if (combination == COMBINATION_NAN) { /* NaN */
         /* str, not str_out, to erase the sign */
         strcpy (str, "NaN");
         /* we don't care about the NaN payload. */
         return;
      } else {
         biased_exponent = (high >> 15) & EXPONENT_MASK;
         significand_msb = 0x8 + ((high >> 14) & 0x1);
      }
   } else {
      significand_msb = (high >> 14) & 0x7;
      biased_exponent = (high >> 17) & EXPONENT_MASK;
   }

   exponent = biased_exponent - EXPONENT_BIAS;
   /* Create string of significand digits */

   /* Convert the 114-bit binary number represented by */
   /* (high, midh, midl, low) to at most 34 decimal */
   /* digits through modulo and division. */
   significand128.parts[0] = (high & 0x3fff) + ((significand_msb & 0xf) << 14);
   significand128.parts[1] = midh;
   significand128.parts[2] = midl;
   significand128.parts[3] = low;

   if (significand128.parts[0] == 0 && significand128.parts[1] == 0 &&
       significand128.parts[2] == 0 && significand128.parts[3] == 0) {
      is_zero = true;
   } else if (significand128.parts[0] >= (1 << 17)) {
      /* The significand is non-canonical or zero.
       * In order to preserve compatability with the densely packed decimal
       * format, the maximum value for the significand of decimal128 is
       * 1e34 - 1.  If the value is greater than 1e34 - 1, the IEEE 754
       * standard dictates that the significand is interpreted as zero.
       */
      is_zero = true;
   } else {
      for (k = 3; k >= 0; k--) {
         uint32_t least_digits = 0;
         _bson_uint128_divide1B (significand128, &significand128,
                                 &least_digits);

         /* We now have the 9 least significant digits (in base 2). */
         /* Convert and output to string. */
         if (!least_digits) { continue; }

         for (j = 8; j >= 0; j--) {
            significand[k * 9 + j] = least_digits % 10;
            least_digits /= 10;
         }
      }
   }

   /* Output format options: */
   /* Scientific - [-]d.dddE(+/-)dd or [-]dE(+/-)dd */
   /* Regular    - ddd.ddd */

   if (is_zero) {
      significand_digits = 1;
      *significand_read = 0;
   } else {
      significand_digits = 36;
      while (!(*significand_read)) {
         significand_digits--;
         significand_read++;
      }
   }

   scientific_exponent = significand_digits - 1 + exponent;

   /* The scientific exponent checks are dictated by the string conversion
    * specification and are somewhat arbitrary cutoffs.
    *
    * We must check exponent > 0, because if this is the case, the number
    * has trailing zeros.  However, we *cannot* output these trailing zeros,
    * because doing so would change the precision of the value, and would
    * change stored data if the string converted number is round tripped.
    */
   if (scientific_exponent < -6 || exponent > 0) {
      /* Scientific format */
      *(str_out++) = *(significand_read++) + '0';
      significand_digits--;

      if (significand_digits) {
         *(str_out++) = '.';
      }

      for (i = 0; i < significand_digits; i++) {
         *(str_out++) = *(significand_read++) + '0';
      }
      /* Exponent */
      *(str_out++) = 'E';
      bson_snprintf (str_out, 6, "%+d", scientific_exponent);
   } else {
      /* Regular format with no decimal place */
      if (exponent >= 0) {
         for (i = 0; i < significand_digits; i++) {
            *(str_out++) = *(significand_read++) + '0';
         }
         *str_out = '\0';
      } else {
         int32_t radix_position = significand_digits + exponent;

         if (radix_position > 0) {        /* non-zero digits before radix */
            for (i = 0; i < radix_position; i++) {
               *(str_out++) = *(significand_read++) + '0';
            }
         } else {                         /* leading zero before radix point */
            *(str_out++) = '0';
         }

         *(str_out++) = '.';
         while (radix_position++ < 0) {   /* add leading zeros after radix */
            *(str_out++) = '0';
         }

         for (i = 0; i < significand_digits - BSON_MAX (radix_position - 1, 0);
              i++) {
            *(str_out++) = *(significand_read++) + '0';
         }
         *str_out = '\0';
      }
   }
}


typedef struct
{
   uint64_t high,
            low;
} _bson_uint128_6464_t;


/**
 *-------------------------------------------------------------------------
 *
 * mul64x64 --
 *
 *    This function multiplies two &uint64_t into a &_bson_uint128_6464_t.
 *
 * Returns:
 *    The product of @left and @right.
 *
 * Side Effects:
 *    None.
 *
 *-------------------------------------------------------------------------
 */
static void
_mul_64x64 (uint64_t              left,    /* IN */
            uint64_t              right,   /* IN */
            _bson_uint128_6464_t *product) /* OUT */
{
   uint64_t left_high, left_low,
            right_high, right_low,
            product_high, product_mid, product_mid2, product_low;
   _bson_uint128_6464_t rt = { 0 };

   if (!left && !right) {
      *product = rt;
      return;
   }

   left_high = left >> 32;
   left_low = (uint32_t)left;
   right_high = right >> 32;
   right_low = (uint32_t)right;

   product_high = left_high * right_high;
   product_mid = left_high * right_low;
   product_mid2 = left_low * right_high;
   product_low = left_low * right_low;

   product_high += product_mid >> 32;
   product_mid = (uint32_t)product_mid + product_mid2 + (product_low >> 32);

   product_high = product_high + (product_mid >> 32);
   product_low = (product_mid << 32) + (uint32_t)product_low;

   rt.high = product_high;
   rt.low = product_low;
   *product = rt;
}

/**
 *------------------------------------------------------------------------------
 *
 * _dec128_tolower --
 *
 *    This function converts the ASCII character @c to lowercase.  It is locale
 *    insensitive (unlike the stdlib tolower).
 *
 * Returns:
 *    The lowercased character.
 */
char
_dec128_tolower (char c)
{
   if (isupper (c)) {
      c += 32;
   }

   return c;
}

/**
 *------------------------------------------------------------------------------
 *
 * _dec128_istreq --
 *
 *    This function compares the null-terminated *ASCII* strings @a and @b
 *    for case-insensitive equality.
 *
 * Returns:
 *    true if the strings are equal, false otherwise.
 */
bool
_dec128_istreq (const char *a, /* IN */
                const char *b /* IN */)
{
   while (*a != '\0' || *b != '\0') {
      /* strings are different lengths. */
      if (*a == '\0' || *b == '\0') {
         return false;
      }

      if (_dec128_tolower (*a) != _dec128_tolower (*b)) {
         return false;
      }

      a++;
      b++;
   }

   return true;
}

/**
 *------------------------------------------------------------------------------
 *
 * bson_decimal128_from_string --
 *
 *    This function converts @string in the format [+-]ddd[.]ddd[E][+-]dddd to
 *    decimal128.  Out of range values are converted to +/-Infinity.  Invalid
 *    strings are converted to NaN.
 *
 *    If more digits are provided than the available precision allows,
 *    round to the nearest expressable decimal128 with ties going to even will
 *    occur.
 *
 *    Note: @string must be ASCII only!
 *
 * Returns:
 *    true on success, or false on failure. @dec will be NaN if @str was invalid
 *    The &bson_decimal128_t converted from @string at @dec.
 *
 * Side effects:
 *    None.
 *
 *------------------------------------------------------------------------------
 */
bool
bson_decimal128_from_string (const char        *string, /* IN */
                             bson_decimal128_t *dec) /* OUT */
{
   _bson_uint128_6464_t significand = { 0 };

   const char *str_read = string;  /* Read pointer for consuming str. */

   /* Parsing state tracking */
   bool is_negative = false;
   bool saw_radix = false;
   bool includes_sign = false;  /* True if the input string contains a sign. */
   bool found_nonzero = false;

   size_t significant_digits = 0;    /* Total number of significant digits
                                      * (no leading or trailing zero) */
   size_t ndigits_read = 0;   /* Total number of significand digits read */
   size_t ndigits = 0;        /* Total number of digits (no leading zeros) */
   size_t radix_position = 0; /* The number of the digits after radix */
   size_t first_nonzero = 0;  /* The index of the first non-zero in *str* */

   uint16_t digits[BSON_DECIMAL128_MAX_DIGITS] = { 0 };
   uint16_t ndigits_stored = 0;      /* The number of digits in digits */
   uint16_t *digits_insert = digits;  /* Insertion pointer for digits */
   size_t first_digit = 0;      /* The index of the first non-zero digit */
   size_t last_digit = 0;       /* The index of the last digit */

   int32_t exponent = 0;
   size_t i = 0;                   /* loop index over array */
   uint64_t significand_high = 0;  /* The high 17 digits of the significand */
   uint64_t significand_low = 0;   /* The low 17 digits of the significand */
   uint16_t biased_exponent = 0;   /* The biased exponent */

   BSON_ASSERT (dec);
   dec->high = 0;
   dec->low = 0;

   if (*str_read == '+' || *str_read == '-') {
      is_negative = *(str_read++) == '-';
      includes_sign = true;
   }

   /* Check for Infinity or NaN */
   if (!isdigit (*str_read) && *str_read != '.') {
      if (_dec128_istreq (str_read, "inf") ||
          _dec128_istreq (str_read, "infinity")) {
         BSON_DECIMAL128_SET_INF (*dec, is_negative);
         return true;
      } else if (_dec128_istreq (str_read, "nan")) {
         BSON_DECIMAL128_SET_NAN (*dec);
         return true;
      }

      BSON_DECIMAL128_SET_NAN (*dec);
      return false;
   }

   /* Read digits */
   while (isdigit (*str_read) || *str_read == '.') {
      if (*str_read == '.') {
         if (saw_radix) {
            BSON_DECIMAL128_SET_NAN (*dec);
            return false;
         }

         saw_radix = true;
         str_read++;
         continue;
      }

      if (ndigits_stored < 34) {
         if (*str_read != '0' || found_nonzero) {
            if (!found_nonzero) {
               first_nonzero = ndigits_read;
            }

            found_nonzero = true;
            *(digits_insert++) = *(str_read) - '0'; /* Only store 34 digits */
            ndigits_stored++;
         }
      }

      if (found_nonzero) {
         ndigits++;
      }

      if (saw_radix) {
         radix_position++;
      }

      ndigits_read++;
      str_read++;
   }

   if (saw_radix && !ndigits_read) {
      BSON_DECIMAL128_SET_NAN (*dec);
      return false;
   }

   /* Read exponent if exists */
   if (*str_read == 'e' || *str_read == 'E') {
      int nread = 0;
#ifdef _MSC_VER
# define SSCANF sscanf_s
#else
# define SSCANF sscanf
#endif
      int read_exponent = SSCANF (++str_read, "%d%n", &exponent, &nread);
      str_read += nread;

      if (!read_exponent || nread == 0) {
         BSON_DECIMAL128_SET_NAN (*dec);
         return false;
      }

#undef SSCANF
   }

   if (*str_read) {
      BSON_DECIMAL128_SET_NAN (*dec);
      return false;
   }

   /* Done reading input. */
   /* Find first non-zero digit in digits */
   first_digit = 0;

   if (!ndigits_stored) {  /* value is zero */
      first_digit = 0;
      last_digit = 0;
      digits[0] = 0;
      ndigits = 1;
      ndigits_stored = 1;
      significant_digits = 0;
   } else {
      last_digit = ndigits_stored - 1;
      significant_digits = ndigits;
      /* Mark trailing zeros as non-significant */
      while (string[first_nonzero + significant_digits - 1 +
                    includes_sign + saw_radix] == '0') {
         significant_digits--;
      }
   }


   /* Normalization of exponent */
   /* Correct exponent based on radix position, and shift significand as needed */
   /* to represent user input */

   /* Overflow prevention */
   if (exponent <= radix_position && radix_position - exponent > (1 << 14)) {
      exponent = BSON_DECIMAL128_EXPONENT_MIN;
   } else {
      exponent -= radix_position;
   }

   /* Attempt to normalize the exponent */
   while (exponent > BSON_DECIMAL128_EXPONENT_MAX) {
      /* Shift exponent to significand and decrease */
      last_digit++;

      if (last_digit - first_digit > BSON_DECIMAL128_MAX_DIGITS) {
         /* The exponent is too great to shift into the significand. */
         if (significant_digits == 0) {
            /* Value is zero, we are allowed to clamp the exponent. */
            exponent = BSON_DECIMAL128_EXPONENT_MAX;
            break;
         }

         /* Overflow is not permitted, error. */
         BSON_DECIMAL128_SET_NAN (*dec);
         return false;
      }

      exponent--;
   }

   while (exponent < BSON_DECIMAL128_EXPONENT_MIN ||
          ndigits_stored < ndigits) {
      /* Shift last digit */
      if (last_digit == 0) {
         /* underflow is not allowed, but zero clamping is */
         if (significant_digits == 0) {
            exponent = BSON_DECIMAL128_EXPONENT_MIN;
            break;
         }

         BSON_DECIMAL128_SET_NAN (*dec);
         return false;
      }

      if (ndigits_stored < ndigits) {
         if (string[ndigits - 1 + includes_sign + saw_radix] - '0' != 0 &&
             significant_digits != 0) {
            BSON_DECIMAL128_SET_NAN (*dec);
            return false;
         }

         ndigits--; /* adjust to match digits not stored */
      } else {
         if (digits[last_digit] != 0) {
            /* Inexact rounding is not allowed. */
            BSON_DECIMAL128_SET_NAN (*dec);
            return false;
         }


         last_digit--; /* adjust to round */
      }

      if (exponent < BSON_DECIMAL128_EXPONENT_MAX) {
         exponent++;
      } else {
         BSON_DECIMAL128_SET_NAN (*dec);
         return false;
      }
   }

   /* Round */
   /* We've normalized the exponent, but might still need to round. */
   if (last_digit - first_digit + 1 < significant_digits) {
      size_t end_of_string = ndigits_read + includes_sign + saw_radix;
      uint8_t round_digit;
      uint8_t round_bit = 0;

      /* There are non-zero digits after last_digit that need rounding. */
      /* We round to nearest, ties to even */
      round_digit =
         string[first_nonzero + last_digit + includes_sign + saw_radix + 1] -
         '0';

      if (round_digit != 0) {
         /* Inexact (non-zero) rounding is not allowed */
         BSON_DECIMAL128_SET_NAN (*dec);
         return false;
      }
   }

   /* Encode significand */
   significand_high = 0,  /* The high 17 digits of the significand */
   significand_low = 0;   /* The low 17 digits of the significand */

   if (significant_digits == 0) {  /* read a zero */
      significand_high = 0;
      significand_low = 0;
   } else if (last_digit - first_digit < 17) {
      int d_idx = first_digit;
      significand_low = digits[d_idx++];

      for (; d_idx <= last_digit; d_idx++) {
         significand_low *= 10;
         significand_low += digits[d_idx];
         significand_high = 0;
      }
   } else {
      int d_idx = first_digit;
      significand_high = digits[d_idx++];

      for (; d_idx <= last_digit - 17; d_idx++) {
         significand_high *= 10;
         significand_high += digits[d_idx];
      }

      significand_low = digits[d_idx++];

      for (; d_idx <= last_digit; d_idx++) {
         significand_low *= 10;
         significand_low += digits[d_idx];
      }
   }

   _mul_64x64 (significand_high,
               100000000000000000ull,
               &significand);
   significand.low += significand_low;

   if (significand.low < significand_low) {
      significand.high += 1;
   }


   biased_exponent = (exponent + (int16_t)BSON_DECIMAL128_EXPONENT_BIAS);

   /* Encode combination, exponent, and significand. */
   if ((significand.high >> 49) & 1) {
      /* Encode '11' into bits 1 to 3 */
      dec->high |= (0x3ull << 61);
      dec->high |= (biased_exponent & 0x3fffull) << 47;
      dec->high |= significand.high & 0x7fffffffffffull;
   } else {
      dec->high |= (biased_exponent & 0x3fffull) << 49;
      dec->high |= significand.high & 0x1ffffffffffffull;
   }

   dec->low = significand.low;

   /* Encode sign */
   if (is_negative) {
	   dec->high |= 0x8000000000000000ull;
   }

   return true;
}