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 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_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 105 : mul64_overflow (uint64_t a,
33 : uint64_t b,
34 : uint64_t *hi,
35 : uint64_t *lo)
36 : {
37 105 : uint64_t a_lo = a & 0xFFFFFFFF;
38 105 : uint64_t a_hi = a >> 32;
39 105 : uint64_t b_lo = b & 0xFFFFFFFF;
40 105 : uint64_t b_hi = b >> 32;
41 :
42 105 : uint64_t p0 = a_lo * b_lo;
43 105 : uint64_t p1 = a_lo * b_hi;
44 105 : uint64_t p2 = a_hi * b_lo;
45 105 : uint64_t p3 = a_hi * b_hi;
46 :
47 105 : uint64_t carry = ((p0 >> 32) + (p1 & 0xFFFFFFFF) + (p2 & 0xFFFFFFFF)) >> 32;
48 :
49 105 : *lo = p0 + (p1 << 32) + (p2 << 32);
50 105 : *hi = p3 + (p1 >> 32) + (p2 >> 32) + carry;
51 105 : }
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 75 : 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 75 : *r_lo = a_lo + b_lo;
69 75 : carry = (*r_lo < a_lo) ? 1 : 0;
70 75 : *r_hi = a_hi + b_hi + carry;
71 :
72 75 : 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 15 : 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 15 : carry = (a_lo < b_lo) ? 1 : 0;
91 15 : *r_lo = a_lo - b_lo;
92 15 : *r_hi = a_hi - b_hi - carry;
93 :
94 15 : 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 45 : 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 45 : if (0 == n_hi)
113 : {
114 45 : *q_hi = 0;
115 45 : *q_lo = n_lo / d;
116 45 : *r = n_lo % d;
117 45 : return;
118 : }
119 :
120 : /* Note: very slow method, could be done faster, but
121 : in practice we expect the above short-cut to apply
122 : in virtually all cases, so we keep it simple here;
123 : also, if it mattered, we should use __uint128_t on
124 : systems that support it. */
125 0 : remainder = 0;
126 0 : *q_hi = 0;
127 0 : *q_lo = 0;
128 0 : for (int i = 127; i >= 0; i--)
129 : {
130 0 : remainder <<= 1;
131 0 : if (i >= 64)
132 0 : remainder |= (n_hi >> (i - 64)) & 1;
133 : else
134 0 : remainder |= (n_lo >> i) & 1;
135 :
136 0 : if (remainder >= d)
137 : {
138 0 : remainder -= d;
139 0 : if (i >= 64)
140 0 : *q_hi |= (1ULL << (i - 64));
141 : else
142 0 : *q_lo |= (1ULL << i);
143 : }
144 : }
145 0 : *r = remainder;
146 : }
147 :
148 :
149 : enum GNUNET_GenericReturnValue
150 15 : TALER_MERCHANT_amount_multiply_by_quantity (
151 : struct TALER_Amount *result,
152 : const struct TALER_Amount *unit_price,
153 : const struct TALER_MERCHANT_ProductQuantity *factor,
154 : enum TALER_MERCHANT_RoundMode rm,
155 : const struct TALER_Amount *atomic_amount)
156 : {
157 : uint64_t price_hi;
158 : uint64_t price_lo;
159 : uint64_t factor_hi;
160 : uint64_t factor_lo;
161 : uint64_t prod_hi;
162 : uint64_t prod_lo;
163 : uint64_t raw_hi;
164 : uint64_t raw_lo;
165 : uint64_t rem;
166 : uint64_t atomic_hi;
167 : uint64_t atomic_lo;
168 : uint64_t rounded_hi;
169 : uint64_t rounded_lo;
170 : uint64_t remainder;
171 :
172 15 : if (GNUNET_OK !=
173 15 : TALER_amount_cmp_currency (unit_price,
174 : atomic_amount))
175 : {
176 0 : GNUNET_break (0);
177 0 : return GNUNET_SYSERR;
178 : }
179 15 : GNUNET_assert (factor->fractional < TALER_MERCHANT_UNIT_FRAC_BASE);
180 15 : GNUNET_assert (unit_price->fraction < TALER_AMOUNT_FRAC_BASE);
181 15 : GNUNET_assert (atomic_amount->fraction < TALER_AMOUNT_FRAC_BASE);
182 15 : GNUNET_assert (GNUNET_OK ==
183 : TALER_amount_set_zero (unit_price->currency,
184 : result));
185 :
186 15 : if (TALER_amount_is_zero (atomic_amount))
187 : {
188 0 : GNUNET_break (0);
189 0 : return GNUNET_SYSERR;
190 : }
191 :
192 : /* Convert unit_price to fractional units */
193 15 : mul64_overflow (unit_price->value,
194 : TALER_AMOUNT_FRAC_BASE,
195 : &price_hi,
196 : &price_lo);
197 15 : if (add128 (price_hi,
198 : price_lo,
199 : 0,
200 15 : unit_price->fraction,
201 : &price_hi,
202 : &price_lo))
203 0 : return GNUNET_NO;
204 :
205 : /* Convert factor to fractional units */
206 15 : mul64_overflow (factor->integer,
207 : TALER_MERCHANT_UNIT_FRAC_BASE,
208 : &factor_hi,
209 : &factor_lo);
210 15 : if (add128 (factor_hi,
211 : factor_lo,
212 : 0,
213 15 : factor->fractional,
214 : &factor_hi,
215 : &factor_lo))
216 0 : return GNUNET_NO;
217 :
218 : /* Multiply price by factor: (price_hi:price_lo) * (factor_hi:factor_lo) */
219 : {
220 : uint64_t p0_hi, p0_lo, p1_hi, p1_lo, p2_hi, p2_lo, p3_hi, p3_lo;
221 :
222 15 : mul64_overflow (price_lo,
223 : factor_lo,
224 : &p0_hi,
225 : &p0_lo);
226 15 : mul64_overflow (price_lo,
227 : factor_hi,
228 : &p1_hi,
229 : &p1_lo);
230 15 : mul64_overflow (price_hi,
231 : factor_lo,
232 : &p2_hi,
233 : &p2_lo);
234 15 : mul64_overflow (price_hi,
235 : factor_hi,
236 : &p3_hi,
237 : &p3_lo);
238 : /* Check for overflow in 128-bit result */
239 15 : if ( (0 != p3_hi) ||
240 15 : (0 != p3_lo) ||
241 15 : (0 != p2_hi) ||
242 15 : (0 != p1_hi) )
243 0 : return GNUNET_NO;
244 :
245 : /* Add all fractions together */
246 15 : prod_hi = p0_hi;
247 15 : prod_lo = p0_lo;
248 15 : if (add128 (prod_hi,
249 : prod_lo,
250 : p1_lo,
251 : 0,
252 : &prod_hi,
253 : &prod_lo))
254 0 : return GNUNET_NO;
255 15 : if (add128 (prod_hi,
256 : prod_lo,
257 : p2_lo,
258 : 0,
259 : &prod_hi,
260 : &prod_lo))
261 0 : return GNUNET_NO;
262 : }
263 :
264 : /* Divide by MERCHANT_UNIT_FRAC_BASE */
265 15 : div128_64 (prod_hi,
266 : prod_lo,
267 : TALER_MERCHANT_UNIT_FRAC_BASE,
268 : &raw_hi,
269 : &raw_lo,
270 : &rem);
271 :
272 : /* Convert atomic_amount to fractional units */
273 15 : mul64_overflow (atomic_amount->value,
274 : TALER_AMOUNT_FRAC_BASE,
275 : &atomic_hi,
276 : &atomic_lo);
277 15 : if (add128 (atomic_hi,
278 : atomic_lo,
279 : 0,
280 15 : atomic_amount->fraction,
281 : &atomic_hi,
282 : &atomic_lo))
283 : {
284 0 : GNUNET_break (0);
285 0 : return GNUNET_SYSERR;
286 : }
287 15 : if (atomic_hi > 0)
288 : {
289 : /* outside of supported range */
290 0 : GNUNET_break (0);
291 0 : return GNUNET_SYSERR;
292 : }
293 :
294 : /* Compute remainder when dividing by atomic_amount and round down */
295 : {
296 : uint64_t q_hi, q_lo;
297 15 : uint64_t half_atomic = atomic_lo >> 1;
298 15 : bool round_up = false;
299 :
300 15 : div128_64 (raw_hi,
301 : raw_lo,
302 : atomic_lo,
303 : &q_hi,
304 : &q_lo,
305 : &remainder);
306 15 : sub128 (raw_hi,
307 : raw_lo,
308 : 0,
309 : remainder,
310 : &rounded_hi,
311 : &rounded_lo);
312 15 : switch (rm)
313 : {
314 0 : case TALER_MERCHANT_ROUND_NEAREST:
315 0 : round_up = (remainder > half_atomic) ||
316 0 : (remainder == half_atomic && (q_lo & 1));
317 0 : break;
318 15 : case TALER_MERCHANT_ROUND_UP:
319 15 : round_up = (remainder > 0);
320 15 : break;
321 0 : case TALER_MERCHANT_ROUND_DOWN:
322 0 : break;
323 : }
324 15 : if ( (round_up) &&
325 0 : (add128 (rounded_hi,
326 : rounded_lo,
327 : atomic_hi,
328 : atomic_lo,
329 : &rounded_hi,
330 : &rounded_lo)) )
331 0 : return GNUNET_NO;
332 : }
333 :
334 : /* Convert back to value and fraction */
335 : {
336 : uint64_t final_value;
337 : uint64_t final_fraction;
338 : uint64_t q_hi;
339 :
340 15 : div128_64 (rounded_hi,
341 : rounded_lo,
342 : TALER_AMOUNT_FRAC_BASE,
343 : &q_hi,
344 : &final_value,
345 : &final_fraction);
346 :
347 : /* Check for overflow */
348 15 : if (0 != q_hi)
349 0 : return GNUNET_NO;
350 :
351 15 : result->value = final_value;
352 15 : result->fraction = (uint32_t) final_fraction;
353 : }
354 15 : return GNUNET_OK;
355 : }
|
