amount_quantity.c (9435B)
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 mul64_overflow (uint64_t a, 33 uint64_t b, 34 uint64_t *hi, 35 uint64_t *lo) 36 { 37 uint64_t a_lo = a & 0xFFFFFFFF; 38 uint64_t a_hi = a >> 32; 39 uint64_t b_lo = b & 0xFFFFFFFF; 40 uint64_t b_hi = b >> 32; 41 42 uint64_t p0 = a_lo * b_lo; 43 uint64_t p1 = a_lo * b_hi; 44 uint64_t p2 = a_hi * b_lo; 45 uint64_t p3 = a_hi * b_hi; 46 47 uint64_t carry = ((p0 >> 32) + (p1 & 0xFFFFFFFF) + (p2 & 0xFFFFFFFF)) >> 32; 48 49 *lo = p0 + (p1 << 32) + (p2 << 32); 50 *hi = p3 + (p1 >> 32) + (p2 >> 32) + carry; 51 } 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 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 *r_lo = a_lo + b_lo; 69 carry = (*r_lo < a_lo) ? 1 : 0; 70 *r_hi = a_hi + b_hi + carry; 71 72 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 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 carry = (a_lo < b_lo) ? 1 : 0; 91 *r_lo = a_lo - b_lo; 92 *r_hi = a_hi - b_hi - carry; 93 94 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 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 __uint128_t n = (((__uint128_t) n_hi) << 64) | (__uint128_t) n_lo; 118 119 *q_hi = (uint64_t) ((n / d) >> 64); 120 *q_lo = (uint64_t) (n / d); 121 *r = (uint64_t) (n % d); 122 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 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 if (GNUNET_OK != 188 TALER_amount_cmp_currency (unit_price, 189 atomic_amount)) 190 { 191 GNUNET_break (0); 192 return GNUNET_SYSERR; 193 } 194 GNUNET_assert (factor->fractional < TALER_MERCHANT_UNIT_FRAC_BASE); 195 GNUNET_assert (unit_price->fraction < TALER_AMOUNT_FRAC_BASE); 196 GNUNET_assert (atomic_amount->fraction < TALER_AMOUNT_FRAC_BASE); 197 GNUNET_assert (GNUNET_OK == 198 TALER_amount_set_zero (unit_price->currency, 199 result)); 200 201 if (TALER_amount_is_zero (atomic_amount)) 202 { 203 GNUNET_break (0); 204 return GNUNET_SYSERR; 205 } 206 207 /* Convert unit_price to fractional units */ 208 mul64_overflow (unit_price->value, 209 TALER_AMOUNT_FRAC_BASE, 210 &price_hi, 211 &price_lo); 212 if (add128 (price_hi, 213 price_lo, 214 0, 215 unit_price->fraction, 216 &price_hi, 217 &price_lo)) 218 return GNUNET_NO; 219 220 /* Convert factor to fractional units */ 221 mul64_overflow (factor->integer, 222 TALER_MERCHANT_UNIT_FRAC_BASE, 223 &factor_hi, 224 &factor_lo); 225 if (add128 (factor_hi, 226 factor_lo, 227 0, 228 factor->fractional, 229 &factor_hi, 230 &factor_lo)) 231 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 mul64_overflow (price_lo, 238 factor_lo, 239 &p0_hi, 240 &p0_lo); 241 mul64_overflow (price_lo, 242 factor_hi, 243 &p1_hi, 244 &p1_lo); 245 mul64_overflow (price_hi, 246 factor_lo, 247 &p2_hi, 248 &p2_lo); 249 mul64_overflow (price_hi, 250 factor_hi, 251 &p3_hi, 252 &p3_lo); 253 /* Check for overflow in 128-bit result */ 254 if ( (0 != p3_hi) || 255 (0 != p3_lo) || 256 (0 != p2_hi) || 257 (0 != p1_hi) ) 258 return GNUNET_NO; 259 260 /* Add all fractions together */ 261 prod_hi = p0_hi; 262 prod_lo = p0_lo; 263 if (add128 (prod_hi, 264 prod_lo, 265 p1_lo, 266 0, 267 &prod_hi, 268 &prod_lo)) 269 return GNUNET_NO; 270 if (add128 (prod_hi, 271 prod_lo, 272 p2_lo, 273 0, 274 &prod_hi, 275 &prod_lo)) 276 return GNUNET_NO; 277 } 278 279 /* Divide by MERCHANT_UNIT_FRAC_BASE */ 280 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 mul64_overflow (atomic_amount->value, 289 TALER_AMOUNT_FRAC_BASE, 290 &atomic_hi, 291 &atomic_lo); 292 if (add128 (atomic_hi, 293 atomic_lo, 294 0, 295 atomic_amount->fraction, 296 &atomic_hi, 297 &atomic_lo)) 298 { 299 GNUNET_break (0); 300 return GNUNET_SYSERR; 301 } 302 if (atomic_hi > 0) 303 { 304 /* outside of supported range */ 305 GNUNET_break (0); 306 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 uint64_t half_atomic = atomic_lo >> 1; 313 bool round_up = false; 314 315 div128_64 (raw_hi, 316 raw_lo, 317 atomic_lo, 318 &q_hi, 319 &q_lo, 320 &remainder); 321 sub128 (raw_hi, 322 raw_lo, 323 0, 324 remainder, 325 &rounded_hi, 326 &rounded_lo); 327 switch (rm) 328 { 329 case TALER_MERCHANT_ROUND_NEAREST: 330 round_up = (remainder > half_atomic) || 331 (remainder == half_atomic && (q_lo & 1)); 332 break; 333 case TALER_MERCHANT_ROUND_UP: 334 round_up = (remainder > 0); 335 break; 336 case TALER_MERCHANT_ROUND_DOWN: 337 break; 338 } 339 if ( (round_up) && 340 (add128 (rounded_hi, 341 rounded_lo, 342 atomic_hi, 343 atomic_lo, 344 &rounded_hi, 345 &rounded_lo)) ) 346 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 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 if (0 != q_hi) 364 return GNUNET_NO; 365 366 result->value = final_value; 367 result->fraction = (uint32_t) final_fraction; 368 } 369 return GNUNET_OK; 370 }