amount_quantity.c (8836B)
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 "taler/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 (0 == n_hi) 113 { 114 *q_hi = 0; 115 *q_lo = n_lo / d; 116 *r = n_lo % d; 117 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 remainder = 0; 126 *q_hi = 0; 127 *q_lo = 0; 128 for (int i = 127; i >= 0; i--) 129 { 130 remainder <<= 1; 131 if (i >= 64) 132 remainder |= (n_hi >> (i - 64)) & 1; 133 else 134 remainder |= (n_lo >> i) & 1; 135 136 if (remainder >= d) 137 { 138 remainder -= d; 139 if (i >= 64) 140 *q_hi |= (1ULL << (i - 64)); 141 else 142 *q_lo |= (1ULL << i); 143 } 144 } 145 *r = remainder; 146 } 147 148 149 enum GNUNET_GenericReturnValue 150 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 if (GNUNET_OK != 173 TALER_amount_cmp_currency (unit_price, 174 atomic_amount)) 175 { 176 GNUNET_break (0); 177 return GNUNET_SYSERR; 178 } 179 GNUNET_assert (factor->fractional < TALER_MERCHANT_UNIT_FRAC_BASE); 180 GNUNET_assert (unit_price->fraction < TALER_AMOUNT_FRAC_BASE); 181 GNUNET_assert (atomic_amount->fraction < TALER_AMOUNT_FRAC_BASE); 182 GNUNET_assert (GNUNET_OK == 183 TALER_amount_set_zero (unit_price->currency, 184 result)); 185 186 if (TALER_amount_is_zero (atomic_amount)) 187 { 188 GNUNET_break (0); 189 return GNUNET_SYSERR; 190 } 191 192 /* Convert unit_price to fractional units */ 193 mul64_overflow (unit_price->value, 194 TALER_AMOUNT_FRAC_BASE, 195 &price_hi, 196 &price_lo); 197 if (add128 (price_hi, 198 price_lo, 199 0, 200 unit_price->fraction, 201 &price_hi, 202 &price_lo)) 203 return GNUNET_NO; 204 205 /* Convert factor to fractional units */ 206 mul64_overflow (factor->integer, 207 TALER_MERCHANT_UNIT_FRAC_BASE, 208 &factor_hi, 209 &factor_lo); 210 if (add128 (factor_hi, 211 factor_lo, 212 0, 213 factor->fractional, 214 &factor_hi, 215 &factor_lo)) 216 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 mul64_overflow (price_lo, 223 factor_lo, 224 &p0_hi, 225 &p0_lo); 226 mul64_overflow (price_lo, 227 factor_hi, 228 &p1_hi, 229 &p1_lo); 230 mul64_overflow (price_hi, 231 factor_lo, 232 &p2_hi, 233 &p2_lo); 234 mul64_overflow (price_hi, 235 factor_hi, 236 &p3_hi, 237 &p3_lo); 238 /* Check for overflow in 128-bit result */ 239 if ( (0 != p3_hi) || 240 (0 != p3_lo) || 241 (0 != p2_hi) || 242 (0 != p1_hi) ) 243 return GNUNET_NO; 244 245 /* Add all fractions together */ 246 prod_hi = p0_hi; 247 prod_lo = p0_lo; 248 if (add128 (prod_hi, 249 prod_lo, 250 p1_lo, 251 0, 252 &prod_hi, 253 &prod_lo)) 254 return GNUNET_NO; 255 if (add128 (prod_hi, 256 prod_lo, 257 p2_lo, 258 0, 259 &prod_hi, 260 &prod_lo)) 261 return GNUNET_NO; 262 } 263 264 /* Divide by MERCHANT_UNIT_FRAC_BASE */ 265 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 mul64_overflow (atomic_amount->value, 274 TALER_AMOUNT_FRAC_BASE, 275 &atomic_hi, 276 &atomic_lo); 277 if (add128 (atomic_hi, 278 atomic_lo, 279 0, 280 atomic_amount->fraction, 281 &atomic_hi, 282 &atomic_lo)) 283 { 284 GNUNET_break (0); 285 return GNUNET_SYSERR; 286 } 287 if (atomic_hi > 0) 288 { 289 /* outside of supported range */ 290 GNUNET_break (0); 291 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 uint64_t half_atomic = atomic_lo >> 1; 298 bool round_up = false; 299 300 div128_64 (raw_hi, 301 raw_lo, 302 atomic_lo, 303 &q_hi, 304 &q_lo, 305 &remainder); 306 sub128 (raw_hi, 307 raw_lo, 308 0, 309 remainder, 310 &rounded_hi, 311 &rounded_lo); 312 switch (rm) 313 { 314 case TALER_MERCHANT_ROUND_NEAREST: 315 round_up = (remainder > half_atomic) || 316 (remainder == half_atomic && (q_lo & 1)); 317 break; 318 case TALER_MERCHANT_ROUND_UP: 319 round_up = (remainder > 0); 320 break; 321 case TALER_MERCHANT_ROUND_DOWN: 322 break; 323 } 324 if ( (round_up) && 325 (add128 (rounded_hi, 326 rounded_lo, 327 atomic_hi, 328 atomic_lo, 329 &rounded_hi, 330 &rounded_lo)) ) 331 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 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 if (0 != q_hi) 349 return GNUNET_NO; 350 351 result->value = final_value; 352 result->fraction = (uint32_t) final_fraction; 353 } 354 return GNUNET_OK; 355 }