1 // Copyright 2017 PDFium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com 6 7 #include "core/fxcrt/cfx_decimal.h" 8 9 #include <algorithm> 10 #include <utility> 11 12 #include "core/fxcrt/fx_extension.h" 13 14 #define FXMATH_DECIMAL_SCALELIMIT 0x1c 15 #define FXMATH_DECIMAL_NEGMASK (0x80000000L) 16 #define FXMATH_DECIMAL_FORCEBOOL(x) (!!(x)) 17 #define FXMATH_DECIMAL_MAKEFLAGS(NEG, SCALE) \ 18 (((SCALE) << 0x10) | ((NEG) ? FXMATH_DECIMAL_NEGMASK : 0)) 19 #define FXMATH_DECIMAL_FLAGS2NEG(FLAGS) \ 20 FXMATH_DECIMAL_FORCEBOOL((FLAGS)&FXMATH_DECIMAL_NEGMASK) 21 #define FXMATH_DECIMAL_FLAGS2SCALE(FLAGS) \ 22 ((uint8_t)(((FLAGS) & ~FXMATH_DECIMAL_NEGMASK) >> 0x10)) 23 #define FXMATH_DECIMAL_RSHIFT32BIT(x) ((x) >> 0x10 >> 0x10) 24 #define FXMATH_DECIMAL_LSHIFT32BIT(x) ((x) << 0x10 << 0x10) 25 26 namespace { 27 28 inline uint8_t decimal_helper_div10(uint64_t& phi, 29 uint64_t& pmid, 30 uint64_t& plo) { 31 uint8_t retVal; 32 pmid += FXMATH_DECIMAL_LSHIFT32BIT(phi % 0xA); 33 phi /= 0xA; 34 plo += FXMATH_DECIMAL_LSHIFT32BIT(pmid % 0xA); 35 pmid /= 0xA; 36 retVal = plo % 0xA; 37 plo /= 0xA; 38 return retVal; 39 } 40 41 inline uint8_t decimal_helper_div10_any(uint64_t nums[], uint8_t numcount) { 42 uint8_t retVal = 0; 43 for (int i = numcount - 1; i > 0; i--) { 44 nums[i - 1] += FXMATH_DECIMAL_LSHIFT32BIT(nums[i] % 0xA); 45 nums[i] /= 0xA; 46 } 47 if (numcount) { 48 retVal = nums[0] % 0xA; 49 nums[0] /= 0xA; 50 } 51 return retVal; 52 } 53 54 inline void decimal_helper_mul10(uint64_t& phi, uint64_t& pmid, uint64_t& plo) { 55 plo *= 0xA; 56 pmid = pmid * 0xA + FXMATH_DECIMAL_RSHIFT32BIT(plo); 57 plo = (uint32_t)plo; 58 phi = phi * 0xA + FXMATH_DECIMAL_RSHIFT32BIT(pmid); 59 pmid = (uint32_t)pmid; 60 } 61 62 inline void decimal_helper_mul10_any(uint64_t nums[], uint8_t numcount) { 63 nums[0] *= 0xA; 64 for (int i = 1; i < numcount; i++) { 65 nums[i] = nums[i] * 0xA + FXMATH_DECIMAL_RSHIFT32BIT(nums[i - 1]); 66 nums[i - 1] = (uint32_t)nums[i - 1]; 67 } 68 } 69 70 inline void decimal_helper_normalize(uint64_t& phi, 71 uint64_t& pmid, 72 uint64_t& plo) { 73 phi += FXMATH_DECIMAL_RSHIFT32BIT(pmid); 74 pmid = (uint32_t)pmid; 75 pmid += FXMATH_DECIMAL_RSHIFT32BIT(plo); 76 plo = (uint32_t)plo; 77 phi += FXMATH_DECIMAL_RSHIFT32BIT(pmid); 78 pmid = (uint32_t)pmid; 79 } 80 81 inline void decimal_helper_normalize_any(uint64_t nums[], uint8_t len) { 82 for (int i = len - 2; i > 0; i--) { 83 nums[i + 1] += FXMATH_DECIMAL_RSHIFT32BIT(nums[i]); 84 nums[i] = (uint32_t)nums[i]; 85 } 86 for (int i = 0; i < len - 1; i++) { 87 nums[i + 1] += FXMATH_DECIMAL_RSHIFT32BIT(nums[i]); 88 nums[i] = (uint32_t)nums[i]; 89 } 90 } 91 92 inline int8_t decimal_helper_raw_compare_any(uint64_t a[], 93 uint8_t al, 94 uint64_t b[], 95 uint8_t bl) { 96 int8_t retVal = 0; 97 for (int i = std::max(al - 1, bl - 1); i >= 0; i--) { 98 uint64_t l = (i >= al ? 0 : a[i]), r = (i >= bl ? 0 : b[i]); 99 retVal += (l > r ? 1 : (l < r ? -1 : 0)); 100 if (retVal) 101 return retVal; 102 } 103 return retVal; 104 } 105 106 inline void decimal_helper_dec_any(uint64_t a[], uint8_t al) { 107 for (int i = 0; i < al; i++) { 108 if (a[i]--) 109 return; 110 } 111 } 112 113 inline void decimal_helper_inc_any(uint64_t a[], uint8_t al) { 114 for (int i = 0; i < al; i++) { 115 a[i]++; 116 if ((uint32_t)a[i] == a[i]) 117 return; 118 a[i] = 0; 119 } 120 } 121 122 inline void decimal_helper_raw_mul(uint64_t a[], 123 uint8_t al, 124 uint64_t b[], 125 uint8_t bl, 126 uint64_t c[], 127 uint8_t cl) { 128 ASSERT(al + bl <= cl); 129 for (int i = 0; i < cl; i++) 130 c[i] = 0; 131 132 for (int i = 0; i < al; i++) { 133 for (int j = 0; j < bl; j++) { 134 uint64_t m = (uint64_t)a[i] * b[j]; 135 c[i + j] += (uint32_t)m; 136 c[i + j + 1] += FXMATH_DECIMAL_RSHIFT32BIT(m); 137 } 138 } 139 for (int i = 0; i < cl - 1; i++) { 140 c[i + 1] += FXMATH_DECIMAL_RSHIFT32BIT(c[i]); 141 c[i] = (uint32_t)c[i]; 142 } 143 for (int i = 0; i < cl; i++) 144 c[i] = (uint32_t)c[i]; 145 } 146 147 inline void decimal_helper_raw_div(uint64_t a[], 148 uint8_t al, 149 uint64_t b[], 150 uint8_t bl, 151 uint64_t c[], 152 uint8_t cl) { 153 for (int i = 0; i < cl; i++) 154 c[i] = 0; 155 156 uint64_t left[16] = {0}; 157 uint64_t right[16] = {0}; 158 left[0] = 0; 159 for (int i = 0; i < al; i++) 160 right[i] = a[i]; 161 162 uint64_t tmp[16]; 163 while (decimal_helper_raw_compare_any(left, al, right, al) <= 0) { 164 uint64_t cur[16]; 165 for (int i = 0; i < al; i++) 166 cur[i] = left[i] + right[i]; 167 168 for (int i = al - 1; i >= 0; i--) { 169 if (i) 170 cur[i - 1] += FXMATH_DECIMAL_LSHIFT32BIT(cur[i] % 2); 171 cur[i] /= 2; 172 } 173 174 decimal_helper_raw_mul(cur, al, b, bl, tmp, 16); 175 switch (decimal_helper_raw_compare_any(tmp, 16, a, al)) { 176 case -1: 177 for (int i = 0; i < 16; i++) 178 left[i] = cur[i]; 179 180 left[0]++; 181 decimal_helper_normalize_any(left, al); 182 break; 183 case 1: 184 for (int i = 0; i < 16; i++) 185 right[i] = cur[i]; 186 decimal_helper_dec_any(right, al); 187 break; 188 case 0: 189 for (int i = 0; i < std::min(al, cl); i++) 190 c[i] = cur[i]; 191 return; 192 } 193 } 194 for (int i = 0; i < std::min(al, cl); i++) 195 c[i] = left[i]; 196 } 197 198 inline bool decimal_helper_outofrange(uint64_t a[], uint8_t al, uint8_t goal) { 199 for (int i = goal; i < al; i++) { 200 if (a[i]) 201 return true; 202 } 203 return false; 204 } 205 206 inline void decimal_helper_shrinkintorange(uint64_t a[], 207 uint8_t al, 208 uint8_t goal, 209 uint8_t& scale) { 210 bool bRoundUp = false; 211 while (scale != 0 && (scale > FXMATH_DECIMAL_SCALELIMIT || 212 decimal_helper_outofrange(a, al, goal))) { 213 bRoundUp = decimal_helper_div10_any(a, al) >= 5; 214 scale--; 215 } 216 if (bRoundUp) { 217 decimal_helper_normalize_any(a, goal); 218 decimal_helper_inc_any(a, goal); 219 } 220 } 221 222 inline void decimal_helper_truncate(uint64_t& phi, 223 uint64_t& pmid, 224 uint64_t& plo, 225 uint8_t& scale, 226 uint8_t minscale = 0) { 227 while (scale > minscale) { 228 uint64_t thi = phi, tmid = pmid, tlo = plo; 229 if (decimal_helper_div10(thi, tmid, tlo) != 0) 230 break; 231 232 phi = thi; 233 pmid = tmid; 234 plo = tlo; 235 scale--; 236 } 237 } 238 239 } // namespace 240 241 CFX_Decimal::CFX_Decimal() : m_uHi(0), m_uLo(0), m_uMid(0), m_uFlags(0) {} 242 243 CFX_Decimal::CFX_Decimal(uint64_t val) 244 : m_uHi(0), 245 m_uLo(static_cast<uint32_t>(val)), 246 m_uMid(static_cast<uint32_t>(FXMATH_DECIMAL_RSHIFT32BIT(val))), 247 m_uFlags(0) {} 248 249 CFX_Decimal::CFX_Decimal(uint32_t val) 250 : m_uHi(0), m_uLo(static_cast<uint32_t>(val)), m_uMid(0), m_uFlags(0) {} 251 252 CFX_Decimal::CFX_Decimal(uint32_t lo, 253 uint32_t mid, 254 uint32_t hi, 255 bool neg, 256 uint8_t scale) 257 : m_uHi(hi), 258 m_uLo(lo), 259 m_uMid(mid), 260 m_uFlags(FXMATH_DECIMAL_MAKEFLAGS( 261 neg && IsNotZero(), 262 (scale > FXMATH_DECIMAL_SCALELIMIT ? 0 : scale))) {} 263 264 CFX_Decimal::CFX_Decimal(int32_t val) { 265 if (val >= 0) { 266 *this = CFX_Decimal(static_cast<uint32_t>(val)); 267 } else { 268 *this = CFX_Decimal(static_cast<uint32_t>(-val)); 269 SetNegate(); 270 } 271 } 272 273 CFX_Decimal::CFX_Decimal(float val, uint8_t scale) { 274 float newval = fabs(val); 275 uint64_t phi; 276 uint64_t pmid; 277 uint64_t plo; 278 plo = static_cast<uint64_t>(newval); 279 pmid = static_cast<uint64_t>(newval / 1e32); 280 phi = static_cast<uint64_t>(newval / 1e64); 281 newval = fmod(newval, 1.0f); 282 for (uint8_t iter = 0; iter < scale; iter++) { 283 decimal_helper_mul10(phi, pmid, plo); 284 newval *= 10; 285 plo += static_cast<uint64_t>(newval); 286 newval = fmod(newval, 1.0f); 287 } 288 289 plo += FXSYS_round(newval); 290 decimal_helper_normalize(phi, pmid, plo); 291 m_uHi = static_cast<uint32_t>(phi); 292 m_uMid = static_cast<uint32_t>(pmid); 293 m_uLo = static_cast<uint32_t>(plo); 294 m_uFlags = FXMATH_DECIMAL_MAKEFLAGS(val < 0 && IsNotZero(), scale); 295 } 296 297 CFX_Decimal::CFX_Decimal(const WideStringView& strObj) { 298 const wchar_t* str = strObj.unterminated_c_str(); 299 const wchar_t* strBound = str + strObj.GetLength(); 300 bool pointmet = false; 301 bool negmet = false; 302 uint8_t scale = 0; 303 m_uHi = 0; 304 m_uMid = 0; 305 m_uLo = 0; 306 while (str != strBound && *str == ' ') 307 str++; 308 if (str != strBound && *str == '-') { 309 negmet = 1; 310 str++; 311 } else if (str != strBound && *str == '+') { 312 str++; 313 } 314 315 while (str != strBound && (std::iswdigit(*str) || *str == '.') && 316 scale < FXMATH_DECIMAL_SCALELIMIT) { 317 if (*str == '.') { 318 if (!pointmet) 319 pointmet = 1; 320 } else { 321 m_uHi = m_uHi * 0xA + FXMATH_DECIMAL_RSHIFT32BIT((uint64_t)m_uMid * 0xA); 322 m_uMid = m_uMid * 0xA + FXMATH_DECIMAL_RSHIFT32BIT((uint64_t)m_uLo * 0xA); 323 m_uLo = m_uLo * 0xA + (*str - '0'); 324 if (pointmet) 325 scale++; 326 } 327 str++; 328 } 329 m_uFlags = FXMATH_DECIMAL_MAKEFLAGS(negmet && IsNotZero(), scale); 330 } 331 332 CFX_Decimal::operator WideString() const { 333 WideString retString; 334 WideString tmpbuf; 335 uint64_t phi = m_uHi; 336 uint64_t pmid = m_uMid; 337 uint64_t plo = m_uLo; 338 while (phi || pmid || plo) 339 tmpbuf += decimal_helper_div10(phi, pmid, plo) + '0'; 340 341 uint8_t outputlen = (uint8_t)tmpbuf.GetLength(); 342 uint8_t scale = (uint8_t)FXMATH_DECIMAL_FLAGS2SCALE(m_uFlags); 343 while (scale >= outputlen) { 344 tmpbuf += '0'; 345 outputlen++; 346 } 347 if (FXMATH_DECIMAL_FLAGS2NEG(m_uFlags) && IsNotZero()) 348 retString += '-'; 349 350 for (uint8_t idx = 0; idx < outputlen; idx++) { 351 if (idx == (outputlen - scale) && scale != 0) 352 retString += '.'; 353 retString += tmpbuf[outputlen - 1 - idx]; 354 } 355 return retString; 356 } 357 358 CFX_Decimal::operator double() const { 359 double pow = (double)(1 << 16) * (1 << 16); 360 double base = static_cast<double>(m_uHi) * pow * pow + 361 static_cast<double>(m_uMid) * pow + static_cast<double>(m_uLo); 362 int8_t scale = FXMATH_DECIMAL_FLAGS2SCALE(m_uFlags); 363 bool bNeg = FXMATH_DECIMAL_FLAGS2NEG(m_uFlags); 364 return (bNeg ? -1 : 1) * base * ::pow(10.0, -scale); 365 } 366 367 void CFX_Decimal::SetScale(uint8_t newscale) { 368 uint8_t oldscale = FXMATH_DECIMAL_FLAGS2SCALE(m_uFlags); 369 if (newscale > oldscale) { 370 uint64_t phi = m_uHi; 371 uint64_t pmid = m_uMid; 372 uint64_t plo = m_uLo; 373 for (uint8_t iter = 0; iter < newscale - oldscale; iter++) 374 decimal_helper_mul10(phi, pmid, plo); 375 376 m_uHi = static_cast<uint32_t>(phi); 377 m_uMid = static_cast<uint32_t>(pmid); 378 m_uLo = static_cast<uint32_t>(plo); 379 m_uFlags = FXMATH_DECIMAL_MAKEFLAGS( 380 FXMATH_DECIMAL_FLAGS2NEG(m_uFlags) && IsNotZero(), newscale); 381 } else if (newscale < oldscale) { 382 uint64_t phi; 383 uint64_t pmid; 384 uint64_t plo; 385 phi = 0; 386 pmid = 0; 387 plo = 5; 388 for (uint8_t iter = 0; iter < oldscale - newscale - 1; iter++) 389 decimal_helper_mul10(phi, pmid, plo); 390 391 phi += m_uHi; 392 pmid += m_uMid; 393 plo += m_uLo; 394 decimal_helper_normalize(phi, pmid, plo); 395 for (uint8_t iter = 0; iter < oldscale - newscale; iter++) 396 decimal_helper_div10(phi, pmid, plo); 397 398 m_uHi = static_cast<uint32_t>(phi); 399 m_uMid = static_cast<uint32_t>(pmid); 400 m_uLo = static_cast<uint32_t>(plo); 401 m_uFlags = FXMATH_DECIMAL_MAKEFLAGS( 402 FXMATH_DECIMAL_FLAGS2NEG(m_uFlags) && IsNotZero(), newscale); 403 } 404 } 405 406 uint8_t CFX_Decimal::GetScale() { 407 return FXMATH_DECIMAL_FLAGS2SCALE(m_uFlags); 408 } 409 410 void CFX_Decimal::SetNegate() { 411 if (IsNotZero()) 412 m_uFlags ^= FXMATH_DECIMAL_NEGMASK; 413 } 414 415 void CFX_Decimal::Swap(CFX_Decimal& val) { 416 std::swap(m_uHi, val.m_uHi); 417 std::swap(m_uMid, val.m_uMid); 418 std::swap(m_uLo, val.m_uLo); 419 std::swap(m_uFlags, val.m_uFlags); 420 } 421 422 CFX_Decimal CFX_Decimal::operator*(const CFX_Decimal& val) const { 423 uint64_t a[3] = {m_uLo, m_uMid, m_uHi}, 424 b[3] = {val.m_uLo, val.m_uMid, val.m_uHi}; 425 uint64_t c[6]; 426 decimal_helper_raw_mul(a, 3, b, 3, c, 6); 427 bool neg = FXMATH_DECIMAL_FLAGS2NEG(m_uFlags) ^ 428 FXMATH_DECIMAL_FLAGS2NEG(val.m_uFlags); 429 uint8_t scale = FXMATH_DECIMAL_FLAGS2SCALE(m_uFlags) + 430 FXMATH_DECIMAL_FLAGS2SCALE(val.m_uFlags); 431 decimal_helper_shrinkintorange(c, 6, 3, scale); 432 return CFX_Decimal(static_cast<uint32_t>(c[0]), static_cast<uint32_t>(c[1]), 433 static_cast<uint32_t>(c[2]), neg, scale); 434 } 435 436 CFX_Decimal CFX_Decimal::operator/(const CFX_Decimal& val) const { 437 if (!val.IsNotZero()) 438 return CFX_Decimal(); 439 440 bool neg = FXMATH_DECIMAL_FLAGS2NEG(m_uFlags) ^ 441 FXMATH_DECIMAL_FLAGS2NEG(val.m_uFlags); 442 uint64_t a[7] = {m_uLo, m_uMid, m_uHi}, 443 b[3] = {val.m_uLo, val.m_uMid, val.m_uHi}, c[7] = {0}; 444 uint8_t scale = 0; 445 if (FXMATH_DECIMAL_FLAGS2SCALE(m_uFlags) < 446 FXMATH_DECIMAL_FLAGS2SCALE(val.m_uFlags)) { 447 for (int i = FXMATH_DECIMAL_FLAGS2SCALE(val.m_uFlags) - 448 FXMATH_DECIMAL_FLAGS2SCALE(m_uFlags); 449 i > 0; i--) { 450 decimal_helper_mul10_any(a, 7); 451 } 452 } else { 453 scale = FXMATH_DECIMAL_FLAGS2SCALE(m_uFlags) - 454 FXMATH_DECIMAL_FLAGS2SCALE(val.m_uFlags); 455 } 456 457 uint8_t minscale = scale; 458 if (!IsNotZero()) 459 return CFX_Decimal(0, 0, 0, 0, minscale); 460 461 while (!a[6]) { 462 decimal_helper_mul10_any(a, 7); 463 scale++; 464 } 465 466 decimal_helper_div10_any(a, 7); 467 scale--; 468 decimal_helper_raw_div(a, 6, b, 3, c, 7); 469 decimal_helper_shrinkintorange(c, 6, 3, scale); 470 decimal_helper_truncate(c[2], c[1], c[0], scale, minscale); 471 return CFX_Decimal(static_cast<uint32_t>(c[0]), static_cast<uint32_t>(c[1]), 472 static_cast<uint32_t>(c[2]), neg, scale); 473 } 474
