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