Line data Source code
1 : /*
2 : This file is part of TALER
3 : (C) 2025 Taler Systems SA
4 :
5 : TALER is free software; you can redistribute it and/or modify it under the
6 : terms of the GNU Lesser General Public License as published by the Free Software
7 : Foundation; either version 3, or (at your option) any later version.
8 :
9 : TALER is distributed in the hope that it will be useful, but WITHOUT ANY
10 : WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
11 : A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12 :
13 : You should have received a copy of the GNU General Public License along with
14 : TALER; see the file COPYING. If not, see <http://www.gnu.org/licenses/>
15 : */
16 : /**
17 : * @file src/util/amount_quantity.c
18 : * @brief Parsing quantities and other decimal fractions
19 : * @author Christian Grothoff
20 : */
21 : #include "platform.h"
22 : #include <gnunet/gnunet_util_lib.h>
23 : #include <gnunet/gnunet_db_lib.h>
24 : #include <taler/taler_json_lib.h>
25 : #include "taler/taler_merchant_util.h"
26 :
27 :
28 : /**
29 : * Multiply two 64-bit values and store result as high/low 64-bit parts.
30 : */
31 : static void
32 245 : mul64_overflow (uint64_t a,
33 : uint64_t b,
34 : uint64_t *hi,
35 : uint64_t *lo)
36 : {
37 245 : uint64_t a_lo = a & 0xFFFFFFFF;
38 245 : uint64_t a_hi = a >> 32;
39 245 : uint64_t b_lo = b & 0xFFFFFFFF;
40 245 : uint64_t b_hi = b >> 32;
41 :
42 245 : uint64_t p0 = a_lo * b_lo;
43 245 : uint64_t p1 = a_lo * b_hi;
44 245 : uint64_t p2 = a_hi * b_lo;
45 245 : uint64_t p3 = a_hi * b_hi;
46 :
47 245 : uint64_t carry = ((p0 >> 32) + (p1 & 0xFFFFFFFF) + (p2 & 0xFFFFFFFF)) >> 32;
48 :
49 245 : *lo = p0 + (p1 << 32) + (p2 << 32);
50 245 : *hi = p3 + (p1 >> 32) + (p2 >> 32) + carry;
51 245 : }
52 :
53 :
54 : /**
55 : * Add two 128-bit numbers represented as hi/lo pairs.
56 : * Returns 1 on overflow, 0 otherwise.
57 : */
58 : static int
59 175 : add128 (uint64_t a_hi,
60 : uint64_t a_lo,
61 : uint64_t b_hi,
62 : uint64_t b_lo,
63 : uint64_t *r_hi,
64 : uint64_t *r_lo)
65 : {
66 : uint64_t carry;
67 :
68 175 : *r_lo = a_lo + b_lo;
69 175 : carry = (*r_lo < a_lo) ? 1 : 0;
70 175 : *r_hi = a_hi + b_hi + carry;
71 :
72 175 : return (*r_hi < a_hi) || ((*r_hi == a_hi) && carry && (b_hi == UINT64_MAX));
73 : }
74 :
75 :
76 : /**
77 : * Subtract two 128-bit numbers represented as hi/lo pairs.
78 : * Returns 1 on underflow, 0 otherwise.
79 : */
80 : static int
81 35 : sub128 (uint64_t a_hi,
82 : uint64_t a_lo,
83 : uint64_t b_hi,
84 : uint64_t b_lo,
85 : uint64_t *r_hi,
86 : uint64_t *r_lo)
87 : {
88 : uint64_t carry;
89 :
90 35 : carry = (a_lo < b_lo) ? 1 : 0;
91 35 : *r_lo = a_lo - b_lo;
92 35 : *r_hi = a_hi - b_hi - carry;
93 :
94 35 : return (a_hi < b_hi) || ((a_hi == b_hi) && carry);
95 : }
96 :
97 :
98 : /**
99 : * Divide a 128-bit number by a 64-bit number.
100 : * Returns quotient in q_hi/q_lo and remainder in r.
101 : */
102 : static void
103 105 : div128_64 (uint64_t n_hi,
104 : uint64_t n_lo,
105 : uint64_t d,
106 : uint64_t *q_hi,
107 : uint64_t *q_lo,
108 : uint64_t *r)
109 : {
110 : uint64_t remainder;
111 :
112 : #if defined(__SIZEOF_INT128__)
113 : {
114 : /* Use native 128-bit division where the compiler supports it.
115 : This also avoids the overflow of the bit-by-bit fallback below
116 : when d > 2^63 (there 'remainder <<= 1' would drop the top bit). */
117 105 : __uint128_t n = (((__uint128_t) n_hi) << 64) | (__uint128_t) n_lo;
118 :
119 105 : *q_hi = (uint64_t) ((n / d) >> 64);
120 105 : *q_lo = (uint64_t) (n / d);
121 105 : *r = (uint64_t) (n % d);
122 105 : return;
123 : }
124 : #endif
125 :
126 : if (0 == n_hi)
127 : {
128 : *q_hi = 0;
129 : *q_lo = n_lo / d;
130 : *r = n_lo % d;
131 : return;
132 : }
133 : GNUNET_break (d < INT64_MAX); /* theoretical algo limit... */
134 : /* Note: very slow method, could be done faster, but
135 : in practice we expect the above short-cut to apply
136 : in virtually all cases, so we keep it simple here.
137 : WARNING: this fallback is only correct for d <= 2^63;
138 : for larger divisors 'remainder <<= 1' overflows. All
139 : platforms with __uint128_t take the fast path above. */
140 : remainder = 0;
141 : *q_hi = 0;
142 : *q_lo = 0;
143 : for (int i = 127; i >= 0; i--)
144 : {
145 : remainder <<= 1;
146 : if (i >= 64)
147 : remainder |= (n_hi >> (i - 64)) & 1;
148 : else
149 : remainder |= (n_lo >> i) & 1;
150 :
151 : if (remainder >= d)
152 : {
153 : remainder -= d;
154 : if (i >= 64)
155 : *q_hi |= (1ULL << (i - 64));
156 : else
157 : *q_lo |= (1ULL << i);
158 : }
159 : }
160 : *r = remainder;
161 : }
162 :
163 :
164 : enum GNUNET_GenericReturnValue
165 35 : TALER_MERCHANT_amount_multiply_by_quantity (
166 : struct TALER_Amount *result,
167 : const struct TALER_Amount *unit_price,
168 : const struct TALER_MERCHANT_ProductQuantity *factor,
169 : enum TALER_MERCHANT_RoundMode rm,
170 : const struct TALER_Amount *atomic_amount)
171 : {
172 : uint64_t price_hi;
173 : uint64_t price_lo;
174 : uint64_t factor_hi;
175 : uint64_t factor_lo;
176 : uint64_t prod_hi;
177 : uint64_t prod_lo;
178 : uint64_t raw_hi;
179 : uint64_t raw_lo;
180 : uint64_t rem;
181 : uint64_t atomic_hi;
182 : uint64_t atomic_lo;
183 : uint64_t rounded_hi;
184 : uint64_t rounded_lo;
185 : uint64_t remainder;
186 :
187 35 : if (GNUNET_OK !=
188 35 : TALER_amount_cmp_currency (unit_price,
189 : atomic_amount))
190 : {
191 0 : GNUNET_break (0);
192 0 : return GNUNET_SYSERR;
193 : }
194 35 : GNUNET_assert (factor->fractional < TALER_MERCHANT_UNIT_FRAC_BASE);
195 35 : GNUNET_assert (unit_price->fraction < TALER_AMOUNT_FRAC_BASE);
196 35 : GNUNET_assert (atomic_amount->fraction < TALER_AMOUNT_FRAC_BASE);
197 35 : GNUNET_assert (GNUNET_OK ==
198 : TALER_amount_set_zero (unit_price->currency,
199 : result));
200 :
201 35 : if (TALER_amount_is_zero (atomic_amount))
202 : {
203 0 : GNUNET_break (0);
204 0 : return GNUNET_SYSERR;
205 : }
206 :
207 : /* Convert unit_price to fractional units */
208 35 : mul64_overflow (unit_price->value,
209 : TALER_AMOUNT_FRAC_BASE,
210 : &price_hi,
211 : &price_lo);
212 35 : if (add128 (price_hi,
213 : price_lo,
214 : 0,
215 35 : unit_price->fraction,
216 : &price_hi,
217 : &price_lo))
218 0 : return GNUNET_NO;
219 :
220 : /* Convert factor to fractional units */
221 35 : mul64_overflow (factor->integer,
222 : TALER_MERCHANT_UNIT_FRAC_BASE,
223 : &factor_hi,
224 : &factor_lo);
225 35 : if (add128 (factor_hi,
226 : factor_lo,
227 : 0,
228 35 : factor->fractional,
229 : &factor_hi,
230 : &factor_lo))
231 0 : return GNUNET_NO;
232 :
233 : /* Multiply price by factor: (price_hi:price_lo) * (factor_hi:factor_lo) */
234 : {
235 : uint64_t p0_hi, p0_lo, p1_hi, p1_lo, p2_hi, p2_lo, p3_hi, p3_lo;
236 :
237 35 : mul64_overflow (price_lo,
238 : factor_lo,
239 : &p0_hi,
240 : &p0_lo);
241 35 : mul64_overflow (price_lo,
242 : factor_hi,
243 : &p1_hi,
244 : &p1_lo);
245 35 : mul64_overflow (price_hi,
246 : factor_lo,
247 : &p2_hi,
248 : &p2_lo);
249 35 : mul64_overflow (price_hi,
250 : factor_hi,
251 : &p3_hi,
252 : &p3_lo);
253 : /* Check for overflow in 128-bit result */
254 35 : if ( (0 != p3_hi) ||
255 35 : (0 != p3_lo) ||
256 35 : (0 != p2_hi) ||
257 35 : (0 != p1_hi) )
258 0 : return GNUNET_NO;
259 :
260 : /* Add all fractions together */
261 35 : prod_hi = p0_hi;
262 35 : prod_lo = p0_lo;
263 35 : if (add128 (prod_hi,
264 : prod_lo,
265 : p1_lo,
266 : 0,
267 : &prod_hi,
268 : &prod_lo))
269 0 : return GNUNET_NO;
270 35 : if (add128 (prod_hi,
271 : prod_lo,
272 : p2_lo,
273 : 0,
274 : &prod_hi,
275 : &prod_lo))
276 0 : return GNUNET_NO;
277 : }
278 :
279 : /* Divide by MERCHANT_UNIT_FRAC_BASE */
280 35 : div128_64 (prod_hi,
281 : prod_lo,
282 : TALER_MERCHANT_UNIT_FRAC_BASE,
283 : &raw_hi,
284 : &raw_lo,
285 : &rem);
286 :
287 : /* Convert atomic_amount to fractional units */
288 35 : mul64_overflow (atomic_amount->value,
289 : TALER_AMOUNT_FRAC_BASE,
290 : &atomic_hi,
291 : &atomic_lo);
292 35 : if (add128 (atomic_hi,
293 : atomic_lo,
294 : 0,
295 35 : atomic_amount->fraction,
296 : &atomic_hi,
297 : &atomic_lo))
298 : {
299 0 : GNUNET_break (0);
300 0 : return GNUNET_SYSERR;
301 : }
302 35 : if (atomic_hi > 0)
303 : {
304 : /* outside of supported range */
305 0 : GNUNET_break (0);
306 0 : return GNUNET_SYSERR;
307 : }
308 :
309 : /* Compute remainder when dividing by atomic_amount and round down */
310 : {
311 : uint64_t q_hi, q_lo;
312 35 : uint64_t half_atomic = atomic_lo >> 1;
313 35 : bool round_up = false;
314 :
315 35 : div128_64 (raw_hi,
316 : raw_lo,
317 : atomic_lo,
318 : &q_hi,
319 : &q_lo,
320 : &remainder);
321 35 : sub128 (raw_hi,
322 : raw_lo,
323 : 0,
324 : remainder,
325 : &rounded_hi,
326 : &rounded_lo);
327 35 : switch (rm)
328 : {
329 0 : case TALER_MERCHANT_ROUND_NEAREST:
330 0 : round_up = (remainder > half_atomic) ||
331 0 : (remainder == half_atomic && (q_lo & 1));
332 0 : break;
333 35 : case TALER_MERCHANT_ROUND_UP:
334 35 : round_up = (remainder > 0);
335 35 : break;
336 0 : case TALER_MERCHANT_ROUND_DOWN:
337 0 : break;
338 : }
339 35 : if ( (round_up) &&
340 0 : (add128 (rounded_hi,
341 : rounded_lo,
342 : atomic_hi,
343 : atomic_lo,
344 : &rounded_hi,
345 : &rounded_lo)) )
346 0 : return GNUNET_NO;
347 : }
348 :
349 : /* Convert back to value and fraction */
350 : {
351 : uint64_t final_value;
352 : uint64_t final_fraction;
353 : uint64_t q_hi;
354 :
355 35 : div128_64 (rounded_hi,
356 : rounded_lo,
357 : TALER_AMOUNT_FRAC_BASE,
358 : &q_hi,
359 : &final_value,
360 : &final_fraction);
361 :
362 : /* Check for overflow */
363 35 : if (0 != q_hi)
364 0 : return GNUNET_NO;
365 :
366 35 : result->value = final_value;
367 35 : result->fraction = (uint32_t) final_fraction;
368 : }
369 35 : return GNUNET_OK;
370 : }
|
