/** * ***** BEGIN LICENSE BLOCK ***** * * Copyright 2017-2022 Yzena Tech * * Licensed under the Yzena Viral User License, Version 0.1 (the "Yzena Viral * User License" or "YVUL"), the GNU Affero General Public License (the "GNU * AGPL"), Version 3.0, and the Server Side Public License (the "SSPL"), * Version 1. You may not use this file except in compliance with all of those * licenses. * * You may obtain a copy of the Yzena Viral User License at * * https://yzena.com/yzena-viral-user-license/ * * Unless required by applicable law or agreed to in writing, software * distributed under the Yzena Viral User License is distributed under the * following disclaimer: * * As far as the law allows, this software comes as is, without any * warranty or condition, and no contributor will be liable to anyone for * any damages related to this software or this license, under any kind of * legal claim. * * You may obtain a copy of the GNU Affero General Public License at * * https://www.gnu.org/licenses/agpl-3.0.html * * Unless required by applicable law or agreed to in writing, software * distributed under the GNU Affero General Public License is distributed under * the following disclaimer: * * This software is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero * General Public License for more details. * * You may obtain a copy of the Server Side Public License at * * https://www.mongodb.com/licensing/server-side-public-license * * Unless required by applicable law or agreed to in writing, software * distributed under the Server Side Public License is distributed under the * following disclaimer: * * This software is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the Server * Side Public License for more details. * * ****** END LICENSE BLOCK ****** * * ***************************************************************** * * ******* BEGIN FILE DESCRIPTION ******* * * Public header file for safe arithmetic. * * ******** END FILE DESCRIPTION ******** */ #ifndef YC_ARITH_H #define YC_ARITH_H /* For C++ compatibility */ #ifdef __cplusplus extern "C" { #endif /** * @file yc/arith.h */ /** * @defgroup arith arith * Public function definitions and types for Yc's safe arithmetic. * @{ */ //! @cond Doxygen suppress. #include #include #include #include #include #include //! @endcond #include #include //! @cond Doxygen suppress. // Workarounds for AIX's POSIX incompatibility #ifndef SIZE_MAX #define SIZE_MAX __SIZE_MAX__ #endif // SIZE_MAX #ifndef UINTMAX_C #define UINTMAX_C __UINTMAX_C #endif // UINTMAX_C #ifndef UINT32_C #define UINT32_C __UINT32_C #endif // UINT32_C #ifndef UINT_FAST32_MAX #define UINT_FAST32_MAX __UINT_FAST32_MAX__ #endif // UINT_FAST32_MAX #ifndef UINT16_MAX #define UINT16_MAX __UINT16_MAX__ #endif // UINT16_MAX #ifndef SIG_ATOMIC_MAX #define SIG_ATOMIC_MAX __SIG_ATOMIC_MAX__ #endif // SIG_ATOMIC_MAX #if YC_64BIT #ifdef y_NO_BUILTIN_128 #define YC_INT128_STRUCT #else // y_NO_BUILTIN_128 #ifndef __SIZEOF_INT128__ #define YC_INT128_STRUCT #else // __SIZEOF_INT128__ #if __SIZEOF_INT128__ == 0 #define YC_INT128_STRUCT #endif // __SIZEOF_INT128__ == 0 #endif // __SIZEOF_INT128__ #endif // y_NO_BUILTIN_128 #ifdef YC_INT128_STRUCT #define YC_BOTTOM32 (((uint_fast64_t) 0xffffffffULL)) #define YC_TRUNC32(n) ((n) & (YC_BOTTOM32)) #define YC_CHOP32(n) ((n) >> 32) /** * @typedef uint128_t * A 128-bit integer. */ typedef struct uint128_t { uint64_t l; uint64_t h; } uint128_t; typedef uint128_t int128_t; typedef int128_t y_s128; typedef uint128_t y_u128; extern const y_s128 y_s128_max; extern const y_s128 y_s128_min; extern const y_u128 y_u128_max; y_inline static inline uint128_t yc_a128(const uint64_t a, const uint64_t b); y_inline static inline uint128_t yc_s128(const uint64_t a, const uint64_t b); y_inline static inline uint128_t yc_m128(const uint64_t a, const uint64_t b); y_inline static inline uint128_t yc_n128(const uint128_t a); y_inline static inline uint128_t yc_sn128(const uint128_t a); y_inline static inline bool yc_eq128(const uint128_t a, const uint128_t b); y_inline static inline bool yc_ne128(const uint128_t a, const uint128_t b); y_inline static inline bool yc_ult128(const uint128_t a, const uint128_t b); y_inline static inline bool yc_ule128(const uint128_t a, const uint128_t b); y_inline static inline bool yc_ugt128(const uint128_t a, const uint128_t b); y_inline static inline bool yc_uge128(const uint128_t a, const uint128_t b); y_inline static inline bool yc_slt128(const uint128_t a, const uint128_t b); y_inline static inline bool yc_sle128(const uint128_t a, const uint128_t b); y_inline static inline bool yc_sgt128(const uint128_t a, const uint128_t b); y_inline static inline bool yc_sge128(const uint128_t a, const uint128_t b); #else // YC_INT128_STRUCT /** * @typedef uint128_t * A 128-bit integer. */ typedef __uint128_t uint128_t; #endif // YC_INT128_STRUCT #endif // YC_64BIT //! @endcond /** * @typedef llong * A single word typedef for long long. */ typedef long long llong; // clang-format off //! @cond Doxygen suppress. #define y_MAX_8 (255ULL) #define y_MAX_16 (65535ULL) #define y_MAX_32 (4294967295ULL) #define y_MAX_64 (18446744073709551615ULL) #ifdef YC_INT128_STRUCT #define y_MAX_128 ({ .l = y_MAX_64, .h = y_MAX_64 }) #else // YC_INT128_STRUCT #define y_MAX_128 (340282366920938463463374607431768211455ULL) #endif // YC_INT128_STRUCT #define yc_int1(a, t) \ typedef t a; \ typedef struct { a n; a o; } a ## o; \ typedef struct { a q; a r; } a ## dres; \ typedef struct { a q; a r; bool o; } a ## dreso; \ extern const size_t a ## _bits; \ extern const a a ## _min; \ extern const a a ## _max; #define yc_sn(t) \ y_inline static inline \ t \ t ## sn(const t a) \ { \ return a >= t ## _min; \ } #define yc_eq(t) \ y_inline static inline \ bool \ t ## eq(const t a, const t b) \ { \ return a == b; \ } #define yc_ne(t) \ y_inline static inline \ bool \ t ## ne(const t a, const t b) \ { \ return a != b; \ } #define yc_slt(t) \ y_inline static inline \ bool \ t ## slt(const t a, const t b) \ { \ if (a >= t ## _min) \ { \ return b >= t ## _min ? a < b : true; \ } \ else \ { \ return b >= t ## _min ? false : a < b; \ } \ } #define yc_ult(t) \ y_inline static inline \ bool \ t ## ult(const t a, const t b) \ { \ return a < b; \ } #define yc_sle(t) \ y_inline static inline \ bool \ t ## sle(const t a, const t b) \ { \ if (a >= t ## _min) \ { \ return b >= t ## _min ? a <= b : true; \ } \ else \ { \ return b >= t ## _min ? false : a <= b; \ } \ } #define yc_ule(t) \ y_inline static inline \ bool \ t ## ule(const t a, const t b) \ { \ return a <= b; \ } #define yc_sgt(t) \ y_inline static inline \ bool \ t ## sgt(const t a, const t b) \ { \ if (a >= t ## _min) \ { \ return b >= t ## _min ? a > b : false; \ } \ else \ { \ return b >= t ## _min ? true : a > b; \ } \ } #define yc_ugt(t) \ y_inline static inline \ bool \ t ## ugt(const t a, const t b) \ { \ return a > b; \ } #define yc_sge(t) \ y_inline static inline \ bool \ t ## sge(const t a, const t b) \ { \ if (a >= t ## _min) \ { \ return b >= t ## _min ? a >= b : false; \ } \ else \ { \ return b >= t ## _min ? true : a >= b; \ } \ } #define yc_uge(t) \ y_inline static inline \ bool \ t ## uge(const t a, const t b) \ { \ return a >= b; \ } #define yc_neg(t) \ y_inline static inline \ t \ t ## neg(const t a) \ { \ return (~(a)); \ } #define yc_sneg(t) \ y_inline static inline \ t \ t ## sneg(const t a) \ { \ return (~(a)) + 1; \ } #define yc_shl(t, z) \ y_inline static inline \ t \ t ## shl(const t a, const t b) \ { \ t i; \ if (b >= z) i = 0; \ else i = (t) (((t) a) << ((t) b)); \ return i; \ } #define yc_sshr(t, z) \ y_inline static inline \ t \ t ## shr(const t a, const t b) \ { \ t i; \ bool sign = ((a & t ## _min) != 0); \ if (b >= z) i = (t) (sign ? y_u ## z ## _max : 0); \ else \ { \ i = (t) ((t) a) >> ((t) b); \ if (sign) \ { \ t ext = (t) (((((t) 1) << b) - 1) << ((t) (((t) z) - ((t) b)))); \ i |= ext; \ } \ } \ return i; \ } #define yc_ushr(t, z) \ y_inline static inline \ t \ t ## shr(const t a, const t b) \ { \ t i; \ if (b >= z) i = 0; \ else i = a >> b; \ return i; \ } #define yc_and(t) \ y_inline static inline \ t \ t ## and(const t a, const t b) \ { \ return a & b; \ } #define yc_or(t) \ y_inline static inline \ t \ t ## or(const t a, const t b) \ { \ return a | b; \ } #define yc_xor(t) \ y_inline static inline \ t \ t ## xor(const t a, const t b) \ { \ return a ^ b; \ } #define yc_trunc(t, z2) \ y_inline static inline \ t \ t ## trunc(const t a) \ { \ return (t) (uint ## z2 ## _t) a; \ } #define yc_sext(t, z, z2) \ y_inline static inline \ uint ## z2 ## _t \ t ## sext(const t a) \ { \ const uint ## z2 ## _t bit = \ (uint ## z2 ## _t) (t ## _min & a ? t ## _min : 0); \ const uint ## z2 ## _t sext = (uint ## z2 ## _t) (((bit << 1) - 1) << z); \ return sext | ((uint ## z2 ## _t) a); \ } #ifdef YC_INT128_STRUCT #define yc_sext64(t, z, z2) \ y_inline static inline \ uint ## z2 ## _t \ t ## sext(const t a) \ { \ const t bit = ((t ## _min & a) != 0); \ const uint ## z2 ## _t sext = \ { .l = a, .h = ((t) 0) - bit }; \ return sext; \ } #endif // YC_INT128_STRUCT #define yc_uext(t, z2) \ y_inline static inline \ uint ## z2 ## _t \ t ## uext(const t a) \ { \ return (uint ## z2 ## _t) a; \ } #ifdef YC_INT128_STRUCT #define yc_uext64(t, z2) \ y_inline static inline \ uint ## z2 ## _t \ t ## uext(const t a) \ { \ uint ## z2 ## _t r = { .l = a, .h = 0 }; \ return r; \ } #endif // YC_INT128_STRUCT #define yc_addw(t) \ y_inline static inline \ t \ t ## aw(const t a, const t b) \ { \ return a + b; \ } #define yc_saddo(t) \ y_inline static inline \ t ## o \ t ## ao(const t a, const t b) \ { \ t ## o i; \ i.n = t ## aw(a, b); \ i.o = ((a & t ## _min) == (b & t ## _min)) & \ ((i.n & t ## _min) != (a & t ## _min)); \ return i; \ } #define yc_uaddo(t) \ y_inline static inline \ t ## o \ t ## ao(const t a, const t b) \ { \ t ## o i; \ i.n = t ## aw(a, b); \ i.o = (a >= i.n); \ return i; \ } #define yc_sadds(t) \ y_inline static inline \ t \ t ## as(const t a, const t b) \ { \ t ## o i; \ i = t ## ao(a, b); \ if (i.o) i.n = t ## _min - ((a & t ## _min) == 0); \ return i.n; \ } #define yc_uadds(t) \ y_inline static inline \ t \ t ## as(const t a, const t b) \ { \ t ## o i; \ i = t ## ao(a, b); \ if (i.o) i.n = t ## _max; \ return i.n; \ } #define yc_sadd(t) \ y_inline static inline \ t \ t ## a(const t a, const t b) \ { \ t ## o i; \ i = t ## ao(a, b); \ if (y_unlikely(i.o)) \ { \ y_panicva("signed overflow on add with params: 0x%llx, 0x%llx", \ (unsigned long long) a, (unsigned long long) b); \ } \ return i.n; \ } #define yc_uadd(t) \ y_inline static inline \ t \ t ## a(const t a, const t b) \ { \ t ## o i; \ i = t ## ao(a, b); \ if (y_unlikely(i.o)) \ { \ y_panicva("unsigned overflow on add with params: 0x%llx, 0x%llx", \ (unsigned long long) a, (unsigned long long) b); \ } \ return i.n; \ } #define yc_subw(t) \ y_inline static inline \ t \ t ## sw(const t a, const t b) \ { \ return a - b; \ } #define yc_ssubo(t) \ y_inline static inline \ t ## o \ t ## so(const t a, const t b) \ { \ t ## o i; \ i.n = t ## sw(a, b); \ i.o = ((a & t ## _min) != (b & t ## _min)) & \ ((i.n & t ## _min) != (a & t ## _min)); \ return i; \ } #define yc_usubo(t) \ y_inline static inline \ t ## o \ t ## so(const t a, const t b) \ { \ t ## o i; \ i.n = t ## sw(a, b); \ i.o = (a <= i.n); \ return i; \ } #define yc_ssubs(t) \ y_inline static inline \ t \ t ## ss(const t a, const t b) \ { \ t ## o i; \ i = t ## so(a, b); \ if (i.o) i.n = t ## _min - ((a & t ## _min) == 0); \ return i.n; \ } #define yc_usubs(t) \ y_inline static inline \ t \ t ## ss(const t a, const t b) \ { \ t ## o i; \ i = t ## so(a, b); \ if (i.o) i.n = 0; \ return i.n; \ } #define yc_ssub(t) \ y_inline static inline \ t \ t ## s(const t a, const t b) \ { \ t ## o i; \ i = t ## so(a, b); \ if (y_unlikely(i.o)) \ { \ y_panicva("signed overflow on subtract with params: 0x%llx, 0x%llx", \ (unsigned long long) a, (unsigned long long) b); \ } \ return i.n; \ } #define yc_usub(t) \ y_inline static inline \ t \ t ## s(const t a, const t b) \ { \ t ## o i; \ i = t ## so(a, b); \ if (y_unlikely(i.o)) \ { \ y_panicva("unsigned overflow on subtract with params: 0x%llx, 0x%llx", \ (unsigned long long) a, (unsigned long long) b); \ } \ return i.n; \ } #define yc_mulw(t) \ y_inline static inline \ t \ t ## mw(const t a, const t b) \ { \ t i; \ i = a * b; \ return i; \ } #define yc_smulo(t, z, z2) \ y_inline static inline \ t ## o \ t ## mo(const t a, const t b) \ { \ const uint ## z2 ## _t r = ((uint ## z2 ## _t) a) * b; \ const uint ## z2 ## _t r2 = ((uint ## z2 ## _t) y_u ## z ## _max); \ t ## o i; \ i.n = (t) (r & r2); \ i.o = (r >= r2) || ((a & t ## _min) == (b & t ## _min)) & \ ((i.n & t ## _min) != (a & t ## _min)); \ return i; \ } #ifdef YC_INT128_STRUCT #define yc_smulo64(t, z2) \ y_inline static inline \ t ## o \ t ## mo(const t a, const t b) \ { \ const uint ## z2 ## _t r = yc_m128(a, b); \ t ## o i; \ i.n = (t) (r.l); \ i.o = (r.h != 0) || ((a & t ## _min) == (b & t ## _min)) & \ ((i.n & t ## _min) != (a & t ## _min)); \ return i; \ } #endif // YC_INT128_STRUCT #define yc_umulo(t, z, z2) \ y_inline static inline \ t ## o \ t ## mo(const t a, const t b) \ { \ const uint ## z2 ## _t r = ((uint ## z2 ## _t) a) * b; \ const uint ## z2 ## _t r2 = ((uint ## z2 ## _t) t ## _max); \ t ## o i; \ i.n = (uint ## z ## _t) (r & r2); \ i.o = (uint ## z ## _t) (r >> z); \ return i; \ } #ifdef YC_INT128_STRUCT #define yc_umulo64(t, z2) \ y_inline static inline \ t ## o \ t ## mo(const t a, const t b) \ { \ const uint ## z2 ## _t r = yc_m128(a, b); \ t ## o i; \ i.n = (t) (r.l); \ i.o = r.h; \ return i; \ } #endif // YC_INT128_STRUCT #define yc_smuls(t) \ y_inline static inline \ t \ t ## ms(const t a, const t b) \ { \ t ## o i; \ i = t ## mo(a, b); \ if (i.o) i.n = t ## _min - ((a & t ## _min) == 0); \ return i.n; \ } #define yc_umuls(t) \ y_inline static inline \ t \ t ## ms(const t a, const t b) \ { \ t ## o i; \ i = t ## mo(a, b); \ if (i.o) i.n = t ## _max; \ return i.n; \ } #define yc_smul(t) \ y_inline static inline \ t \ t ## m(const t a, const t b) \ { \ t ## o i; \ i = t ## mo(a, b); \ if (y_unlikely(i.o)) \ { \ y_panicva("signed overflow on multiply with params: 0x%llx, 0x%llx", \ (unsigned long long) a, (unsigned long long) b); \ } \ return i.n; \ } #define yc_umul(t) \ y_inline static inline \ t \ t ## m(const t a, const t b) \ { \ t ## o i; \ i = t ## mo(a, b); \ if (y_unlikely(i.o)) \ { \ y_panicva("unsigned overflow on multiply with params: 0x%llx, 0x%llx", \ (unsigned long long) a, (unsigned long long) b); \ } \ return i.n; \ } #define yc_sdivo(t, z) \ y_inline static inline \ t ## o \ t ## do(t a, t b) \ { \ t ## o i; \ if (b == 0) y_panica("division by zero"); \ const bool aneg = (a >= t ## _min); \ const bool bneg = (b >= t ## _min); \ if (aneg) a = t ## sneg(a); \ if (bneg) b = t ## sneg(b); \ i.n = a / b; \ if (aneg != bneg) i.n = (~(i.n)) + 1; \ i.o = (a == t ## _min && b == y_u ## z ## _max); \ return i; \ } #define yc_sremo(t, z) \ y_inline static inline \ t ## o \ t ## remo(t a, t b) \ { \ t ## o i; \ if (b == 0) y_panica("division by zero"); \ const bool aneg = (a >= t ## _min); \ const bool bneg = (b >= t ## _min); \ if (aneg) a = t ## sneg(a); \ if (bneg) b = t ## sneg(b); \ i.n = a % b; \ if (aneg != bneg) i.n = (~(i.n)) + 1; \ i.o = (a == t ## _min && b == y_u ## z ## _max); \ return i; \ } #define yc_smodo(t, z) \ y_inline static inline \ t ## o \ t ## modo(t a, t b) \ { \ t ## o i; \ if (b == 0) y_panica("division by zero"); \ const bool aneg = (a >= t ## _min); \ const bool bneg = (b >= t ## _min); \ if (aneg) a = t ## sneg(a); \ if (bneg) b = t ## sneg(b); \ i.n = a % b; \ if (aneg != bneg && i.n) i.n = b - i.n; \ if (bneg) i.n = (~(i.n)) + 1; \ i.o = (a == t ## _min && b == y_u ## z ## _max); \ return i; \ } #define yc_sdiv(t) \ y_inline static inline \ t \ t ## d(const t a, const t b) \ { \ t ## o i; \ i = t ## do(a, b); \ if (y_unlikely(i.o)) \ { \ y_panicva("signed overflow on division with params: 0x%llx, 0x%llx", \ (unsigned long long) a, (unsigned long long) b); \ } \ return i.n; \ } #define yc_srem(t) \ y_inline static inline \ t \ t ## rem(const t a, const t b) \ { \ t ## o i; \ i = t ## remo(a, b); \ if (y_unlikely(i.o)) \ { \ y_panicva("signed overflow on remainder with params: 0x%llx, 0x%llx", \ (unsigned long long) a, (unsigned long long) b); \ } \ return i.n; \ } #define yc_smod(t) \ y_inline static inline \ t \ t ## mod(const t a, const t b) \ { \ t ## o i; \ i = t ## modo(a, b); \ if (y_unlikely(i.o)) \ { \ y_panicva("signed overflow on modulus with params: 0x%llx, 0x%llx", \ (unsigned long long) a, (unsigned long long) b); \ } \ return i.n; \ } #define yc_sdivremo(t, z) \ y_inline static inline \ t ## dreso \ t ## dro(t a, t b) \ { \ t ## dreso i; \ if (b == 0) y_panica("division by zero"); \ const bool aneg = (a >= t ## _min); \ const bool bneg = (b >= t ## _min); \ if (aneg) a = t ## sneg(a); \ if (bneg) b = t ## sneg(b); \ i.q = a / b; \ i.r = a % b; \ if (aneg != bneg) i.q = (~(i.q)) + 1; \ i.o = (a == t ## _min && b == y_u ## z ## _max); \ return i; \ } #define yc_sdivmodo(t, z) \ y_inline static inline \ t ## dreso \ t ## dmo(t a, t b) \ { \ t ## dreso i; \ if (b == 0) y_panica("division by zero"); \ const bool aneg = (a >= t ## _min); \ const bool bneg = (b >= t ## _min); \ if (aneg) a = t ## sneg(a); \ if (bneg) b = t ## sneg(b); \ i.q = a / b; \ i.r = a % b; \ if (aneg != bneg) \ { \ i.q = (~(i.q)) + 1; \ if (i.r) i.r = b - i.r; \ } \ if (bneg) i.r = (~(i.r)) + 1; \ i.o = (a == t ## _min && b == y_u ## z ## _max); \ return i; \ } #define yc_sdivrem(t) \ y_inline static inline \ t ## dres \ t ## dr(const t a, const t b) \ { \ t ## dres i; \ t ## dreso j; \ j = t ## dro(a, b); \ if (y_unlikely(j.o)) \ { \ y_panicva("signed overflow on divrem with params: 0x%llx, 0x%llx", \ (unsigned long long) a, (unsigned long long) b); \ } \ i.q = j.q; \ i.r = j.r; \ return i; \ } #define yc_sdivmod(t) \ y_inline static inline \ t ## dres \ t ## dm(const t a, const t b) \ { \ t ## dres i; \ t ## dreso j; \ j = t ## dmo(a, b); \ if (y_unlikely(j.o)) \ { \ y_panicva("signed overflow on divmod with params: 0x%llx, 0x%llx", \ (unsigned long long) a, (unsigned long long) b); \ } \ i.q = j.q; \ i.r = j.r; \ return i; \ } #define yc_sdivw(t) \ y_inline static inline \ t \ t ## dw(t a, t b) \ { \ t i; \ if (b == 0) y_panica("division by zero"); \ const bool aneg = (a >= t ## _min); \ const bool bneg = (b >= t ## _min); \ if (aneg) a = t ## sneg(a); \ if (bneg) b = t ## sneg(b); \ i = a / b; \ if (aneg != bneg) i = (~(i)) + 1; \ return i; \ } #define yc_sremw(t, z) \ y_inline static inline \ t \ t ## remw(t a, t b) \ { \ t i; \ if (b == 0) y_panica("division by zero"); \ const bool aneg = (a >= t ## _min); \ const bool bneg = (b >= t ## _min); \ if (aneg) a = t ## sneg(a); \ if (bneg) b = t ## sneg(b); \ i = a % b; \ if (aneg != bneg) i = (~(i)) + 1; \ return i; \ } #define yc_smodw(t) \ y_inline static inline \ t \ t ## modw(t a, t b) \ { \ t i; \ if (b == 0) y_panica("division by zero"); \ const bool aneg = (a >= t ## _min); \ const bool bneg = (b >= t ## _min); \ if (aneg) a = t ## sneg(a); \ if (bneg) b = t ## sneg(b); \ i = a % b; \ if (aneg != bneg && i) i = b - i; \ if (bneg) i = (~(i)) + 1; \ return i; \ } #define yc_sdivremw(t) \ y_inline static inline \ t ## dres \ t ## drw(t a, t b) \ { \ t ## dres i; \ if (b == 0) y_panica("division by zero"); \ const bool aneg = (a >= t ## _min); \ const bool bneg = (b >= t ## _min); \ if (aneg) a = t ## sneg(a); \ if (bneg) b = t ## sneg(b); \ i.q = a / b; \ i.r = a % b; \ if (aneg != bneg) i.q = (~(i.q)) + 1; \ return i; \ } #define yc_sdivmodw(t) \ y_inline static inline \ t ## dres \ t ## dmw(t a, t b) \ { \ t ## dres i; \ if (b == 0) y_panica("division by zero"); \ const bool aneg = (a >= t ## _min); \ const bool bneg = (b >= t ## _min); \ if (aneg) a = t ## sneg(a); \ if (bneg) b = t ## sneg(b); \ i.q = a / b; \ i.r = a % b; \ if (aneg != bneg) \ { \ i.q = (~(i.q)) + 1; \ if (i.r) i.r = b - i.r; \ } \ if (bneg) i.r = (~(i.r)) + 1; \ return i; \ } #define yc_udiv(t) \ y_inline static inline \ t \ t ## d(const t a, const t b) \ { \ if (b == 0) y_panica("division by zero"); \ return a / b; \ } #define yc_udivrem(t) \ y_inline static inline \ t ## dres \ t ## dr(const t a, const t b) \ { \ t ## dres i; \ if (b == 0) y_panica("division by zero"); \ i.q = a / b; \ i.r = a % b; \ return i; \ } #define yc_urem(t) \ y_inline static inline \ t \ t ## r(const t a, const t b) \ { \ if (b == 0) y_panica("division by zero"); \ return a % b; \ } #define yc_sint(a, n, s, s2, s12) \ yc_int1(a, n) \ yc_sn(a) \ yc_eq(a) \ yc_ne(a) \ yc_slt(a) \ yc_sle(a) \ yc_sgt(a) \ yc_sge(a) \ yc_neg(a) \ yc_sneg(a) \ yc_shl(a, s) \ yc_sshr(a, s) \ yc_and(a) \ yc_or(a) \ yc_xor(a) \ yc_trunc(a, s12) \ yc_sext(a, s, s2) \ yc_addw(a) \ yc_saddo(a) \ yc_sadds(a) \ yc_sadd(a) \ yc_subw(a) \ yc_ssubo(a) \ yc_ssubs(a) \ yc_ssub(a) \ yc_mulw(a) \ yc_smulo(a, s, s2) \ yc_smuls(a) \ yc_smul(a) \ yc_sdivo(a, s) \ yc_sremo(a, s) \ yc_smodo(a, s) \ yc_sdivremo(a, s) \ yc_sdivmodo(a, s) \ yc_sdiv(a) \ yc_srem(a) \ yc_smod(a) \ yc_sdivrem(a) \ yc_sdivmod(a) \ yc_sdivw(a) \ yc_sremw(a, s) \ yc_smodw(a) \ yc_sdivremw(a) \ yc_sdivmodw(a) \ #ifdef YC_INT128_STRUCT #define yc_sint64(a, n, s, s2, s12) \ yc_int1(a, n) \ yc_sn(a) \ yc_eq(a) \ yc_ne(a) \ yc_slt(a) \ yc_sle(a) \ yc_sgt(a) \ yc_sge(a) \ yc_neg(a) \ yc_sneg(a) \ yc_shl(a, s) \ yc_sshr(a, s) \ yc_and(a) \ yc_or(a) \ yc_xor(a) \ yc_trunc(a, s, s12) \ yc_sext64(a, s, s2) \ yc_addw(a) \ yc_saddo(a) \ yc_sadds(a) \ yc_sadd(a) \ yc_subw(a) \ yc_ssubo(a) \ yc_ssubs(a) \ yc_ssub(a) \ yc_mulw(a) \ yc_smulo64(a, s, s2) \ yc_smuls(a) \ yc_smul(a) \ yc_sdivo(a, s) \ yc_sremo(a, s) \ yc_smodo(a, s) \ yc_sdivremo(a, s) \ yc_sdivmodo(a, s) \ yc_sdiv(a) \ yc_srem(a) \ yc_smod(a) \ yc_sdivrem(a) \ yc_sdivmod(a) \ yc_sdivw(a) \ yc_sremw(a, s) \ yc_smodw(a) \ yc_sdivremw(a) \ yc_sdivmodw(a) \ #endif // YC_INT128_STRUCT #define yc_uint(a, n, s, s2, s12) \ yc_int1(a, n) \ yc_eq(a) \ yc_ne(a) \ yc_ult(a) \ yc_ule(a) \ yc_ugt(a) \ yc_uge(a) \ yc_neg(a) \ yc_sneg(a) \ yc_shl(a, s) \ yc_ushr(a, s) \ yc_and(a) \ yc_or(a) \ yc_xor(a) \ yc_trunc(a, s12) \ yc_uext(a, s2) \ yc_addw(a) \ yc_uaddo(a) \ yc_uadds(a) \ yc_uadd(a) \ yc_subw(a) \ yc_usubo(a) \ yc_usubs(a) \ yc_usub(a) \ yc_mulw(a) \ yc_umulo(a, s, s2) \ yc_umuls(a) \ yc_umul(a) \ yc_udiv(a) \ yc_udivrem(a) \ yc_urem(a) \ #ifdef YC_INT128_STRUCT #define yc_uint64(a, n, s, s2, s12) \ yc_int1(a, n) \ yc_eq(a) \ yc_ne(a) \ yc_ult(a) \ yc_ule(a) \ yc_ugt(a) \ yc_uge(a) \ yc_neg(a) \ yc_sneg(a) \ yc_shl(a, s) \ yc_ushr(a, s) \ yc_and(a) \ yc_or(a) \ yc_xor(a) \ yc_trunc(a, s, s12) \ yc_uext64(a, s2) \ yc_addw(a) \ yc_uaddo(a) \ yc_uadds(a) \ yc_uadd(a) \ yc_subw(a) \ yc_usubo(a) \ yc_usubs(a) \ yc_usub(a) \ yc_mulw(a) \ yc_umulo64(a, s, s2) \ yc_umuls(a) \ yc_umul(a) \ yc_udiv(a) \ yc_udivrem(a) \ yc_urem(a) \ #endif // YC_INT128_STRUCT yc_uint(y_u8, uint8_t, 8, 16, 8) yc_sint(y_s8, uint8_t, 8, 16, 8) yc_uint(y_u16, uint16_t, 16, 32, 8) yc_sint(y_s16, uint16_t, 16, 32, 8) yc_uint(y_u32, uint32_t, 32, 64, 16) yc_sint(y_s32, uint32_t, 32, 64, 16) #ifdef YC_INT128_STRUCT yc_uint64(y_u64, uint64_t, 64, 128, 32) yc_sint64(y_s64, uint64_t, 64, 128, 32) #else // YC_INT128_STRUCT yc_uint(y_u64, uint64_t, 64, 128, 32) yc_sint(y_s64, uint64_t, 64, 128, 32) #endif // YC_INT128_STRUCT yc_uint(y_uchar, unsigned char, CHAR_BIT, 16, 8) yc_sint(y_schar, unsigned char, CHAR_BIT, 16, 8) #if USHRT_MAX == y_MAX_16 #define YC_SHORT_BITS (16) yc_uint(y_ushort, unsigned short, 16, 32, 8) yc_sint(y_sshort, unsigned short, 16, 32, 8) #elif USHRT_MAX == y_MAX_32 #define YC_SHORT_BITS (32) yc_uint(y_ushort, unsigned short, 32, 64, 16) yc_sint(y_sshort, unsigned short, 32, 64, 16) #else #error shorts must be 16 or 32 bits #endif // USHRT_MAX #if UINT_MAX == y_MAX_16 #define YC_INT_BITS (16) yc_uint(y_uint, unsigned int, 16, 32, 8) yc_sint(y_sint, unsigned int, 16, 32, 8) #elif UINT_MAX == y_MAX_32 #define YC_INT_BITS (32) yc_uint(y_uint, unsigned int, 32, 64, 16) yc_sint(y_sint, unsigned int, 32, 64, 16) #elif UINT_MAX == y_MAX_64 #define YC_INT_BITS (64) #ifdef YC_INT128_STRUCT yc_uint64(y_uint, unsigned int, 64, 128, 32) yc_sint64(y_sint, unsigned int, 64, 128, 32) #else // YC_INT128_STRUCT yc_uint(y_uint, unsigned int, 64, 128, 32) yc_sint(y_sint, unsigned int, 64, 128, 32) #endif // YC_INT128_STRUCT #else #error ints must be 16, 32, or 64 bits #endif // UINT_MAX #if ULONG_MAX == y_MAX_32 #define YC_LONG_BITS (32) yc_uint(y_ulong, unsigned long, 32, 64, 16) yc_sint(y_slong, unsigned long, 32, 64, 16) #elif ULONG_MAX == y_MAX_64 #define YC_LONG_BITS (64) #ifdef YC_INT128_STRUCT yc_uint64(y_ulong, unsigned long, 64, 128, 32) yc_sint64(y_slong, unsigned long, 64, 128, 32) #else // YC_INT128_STRUCT yc_uint(y_ulong, unsigned long, 64, 128, 32) yc_sint(y_slong, unsigned long, 64, 128, 32) #endif // YC_INT128_STRUCT #else #error longs must be 32 or 64 bits #endif // ULONG_MAX #if ULLONG_MAX == y_MAX_64 #define YC_LLONG_BITS (64) #ifdef YC_INT128_STRUCT yc_uint64(y_ullong, unsigned long long, 64, 128, 32) yc_sint64(y_sllong, unsigned long long, 64, 128, 32) #else // YC_INT128_STRUCT yc_uint(y_ullong, unsigned long long, 64, 128, 32) yc_sint(y_sllong, unsigned long long, 64, 128, 32) #endif // YC_INT128_STRUCT #elif ULLONG_MAX == y_MAX_128 #define YC_LLONG_BITS (128) yc_uint(y_ullong, unsigned long long, 128, 256, 64) yc_sint(y_sllong, unsigned long long, 128, 256, 64) #else #error long longs must be 64 or 128 bits #endif // ULLONG_MAX #if SIZE_MAX == y_MAX_16 #define YC_SIZE_BITS (16) yc_uint(y_usize, size_t, 16, 32, 8) yc_sint(y_ssize, size_t, 16, 32, 8) #elif SIZE_MAX == y_MAX_32 #define YC_SIZE_BITS (32) yc_uint(y_usize, size_t, 32, 64, 16) yc_sint(y_ssize, size_t, 32, 64, 16) #elif SIZE_MAX == y_MAX_64 #define YC_SIZE_BITS (64) #ifdef YC_INT128_STRUCT yc_uint64(y_usize, size_t, 64, 128, 32) yc_sint64(y_ssize, size_t, 64, 128, 32) #else // YC_INT128_STRUCT yc_uint(y_usize, size_t, 64, 128, 32) yc_sint(y_ssize, size_t, 64, 128, 32) #endif // YC_INT128_STRUCT #else #error size_t must be 16, 32, or 64 bits #endif // SIZE_MAX #if UINTPTR_MAX == y_MAX_16 #define YC_INTPTR_BITS (16) yc_uint(y_uptr, uintptr_t, 16, 32, 8) yc_sint(y_sptr, uintptr_t, 16, 32, 8) #elif UINTPTR_MAX == y_MAX_32 #define YC_INTPTR_BITS (32) yc_uint(y_uptr, uintptr_t, 32, 64, 16) yc_sint(y_sptr, uintptr_t, 32, 64, 16) #elif UINTPTR_MAX == y_MAX_64 #define YC_INTPTR_BITS (64) #ifdef YC_INT128_STRUCT yc_uint64(y_uptr, uintptr_t, 64, 128, 32) yc_sint64(y_sptr, uintptr_t, 64, 128, 32) #else // YC_INT128_STRUCT yc_uint(y_uptr, uintptr_t, 64, 128, 32) yc_sint(y_sptr, uintptr_t, 64, 128, 32) #endif // YC_INT128_STRUCT #else #error uintptr_t must be 16, 32, or 64 bits #endif // UINTPTR_MAX #if UINTMAX_MAX == y_MAX_16 #define YC_INTMAX_BITS (16) yc_uint(y_umax, uintmax_t, 16, 32, 8) yc_sint(y_smax, uintmax_t, 16, 32, 8) #elif UINTMAX_MAX == y_MAX_32 #define YC_INTMAX_BITS (32) yc_uint(y_umax, uintmax_t, 32, 64, 16) yc_sint(y_smax, uintmax_t, 32, 64, 16) #elif UINTMAX_MAX == y_MAX_64 #define YC_INTMAX_BITS (64) #ifdef YC_INT128_STRUCT yc_uint64(y_umax, uintmax_t, 64, 128, 32) yc_sint64(y_smax, uintmax_t, 64, 128, 32) #else // YC_INT128_STRUCT yc_uint(y_umax, uintmax_t, 64, 128, 32) yc_sint(y_smax, uintmax_t, 64, 128, 32) #endif // YC_INT128_STRUCT #else #error uintmax_t must be 16, 32, or 64 bits #endif // UINTMAX_MAX y_inline static inline void* int2ptr(const y_uptr a) { return (void*) a; } y_inline static inline y_uptr ptr2int(const void* a) { return (y_uptr) a; } #define yc_2y(ts, tu) \ y_inline static inline \ tu \ ts ## 2y(const ts s) \ { \ return (tu) s; \ } yc_2y(char, y_schar) yc_2y(short, y_sshort) yc_2y(int, y_sint) yc_2y(long, y_slong) yc_2y(llong, y_sllong) yc_2y(int8_t, y_s8) yc_2y(int16_t, y_s16) yc_2y(int32_t, y_s32) yc_2y(int64_t, y_s64) yc_2y(ssize_t, y_ssize) yc_2y(intmax_t, y_smax) yc_2y(intptr_t, y_sptr) #undef y_MAX_8 #undef y_MAX_16 #undef y_MAX_32 #undef y_MAX_64 #undef y_MAX_128 #undef yc_neg #undef yc_sneg #undef yc_sshl #undef yc_ushl #undef yc_sshr #undef yc_ushr #undef yc_and #undef yc_or #undef yc_xor #undef yc_trunc #undef yc_addw #undef yc_saddo #undef yc_uaddo #undef yc_sadds #undef yc_uadds #undef yc_sadd #undef yc_uadd #undef yc_subw #undef yc_ssubo #undef yc_usubo #undef yc_ssubs #undef yc_usubs #undef yc_ssub #undef yc_usub #undef yc_mulw #undef yc_smulo #undef yc_umulo #undef yc_smuls #undef yc_umuls #undef yc_smul #undef yc_umul #undef yc_sdivo #undef yc_sremo #undef yc_smodo #undef yc_sdiv #undef yc_srem #undef yc_smod #undef yc_sdivremo #undef yc_sdivmodo #undef yc_sdivrem #undef yc_sdivmod #undef yc_sdivw #undef yc_sremw #undef yc_smodw #undef yc_sdivremw #undef yc_sdivmodw #undef yc_udiv #undef yc_udivrem #undef yc_urem #undef yc_int1 #undef yc_sint #undef yc_uint #undef yc_s2u //! @endcond Doxygen suppress. #ifdef YC_INT128_STRUCT y_inline static inline uint128_t yc_a128(const uint64_t a, const uint64_t b) { uint128_t r; r.l = a + b; r.h = (r.l < a); return r; } y_inline static inline uint128_t yc_s128(const uint64_t a, const uint64_t b) { const uint64_t c = (~(b)) + 1; return yc_a128(a, c); } y_inline static inline uint128_t yc_m128(const uint64_t a, const uint64_t b) { uint128_t r; const uint_fast64_t al = y_TRUNC32(a); const uint_fast64_t ah = y_CHOP32(a); const uint_fast64_t bl = y_TRUNC32(b); const uint_fast64_t bh = y_CHOP32(b); const uint_fast64_t c0 = al * bl; const uint_fast64_t c1 = al * bh; const uint_fast64_t c2 = ah * bl; const uint_fast64_t c3 = ah * bh; const uint128_t carry = yc_a128((uint64_t) c1, (uint64_t) c2); r = yc_a128(c0, (y_TRUNC32(carry.l)) << 32); r.h = y_CHOP32(carry.l) + c3 + (carry.h << 32); return r; } y_inline static inline uint128_t yc_n128(const uint128_t a) { const uint128_t r = { .l = ~(a.l), .h = ~(a.h) }; return r; } y_inline static inline uint128_t yc_sn128(const uint128_t a) { uint128_t r; const uint128_t b = yc_n128(a); r.l = b.l + 1; r.h = b.h + (r.l < b.l); return r; } y_inline static inline bool yc_eq128(const uint128_t a, const uint128_t b) { return (a.l == b.l && a.h == b.h); } y_inline static inline bool yc_ne128(const uint128_t a, const uint128_t b) { return (a.l != b.l || a.h != b.h); } y_inline static inline bool yc_ult128(const uint128_t a, const uint128_t b) { return (a.h < b.h || (a.h == b.h && a.l < b.l)); } y_inline static inline bool yc_ule128(const uint128_t a, const uint128_t b) { return (a.h < b.h || (a.h == b.h && a.l <= b.l)); } y_inline static inline bool yc_ugt128(const uint128_t a, const uint128_t b) { return (a.h > b.h || (a.h == b.h && a.l > b.l)); } y_inline static inline bool yc_uge128(const uint128_t a, const uint128_t b) { return (a.h > b.h || (a.h == b.h && a.l >= b.l)); } y_inline static inline bool yc_slt128(const uint128_t a, const uint128_t b) { if (a.h >= y_s64_min) { return b.h >= y_s64_min ? yc_ult128(a, b) : true; } else { return b.h >= y_s64_min ? false : yc_ult128(a, b); } } y_inline static inline bool yc_sle128(const uint128_t a, const uint128_t b) { if (a.h >= y_s64_min) { return b.h >= y_s64_min ? yc_ule128(a, b) : true; } else { return b.h >= y_s64_min ? false : yc_ule128(a, b); } } y_inline static inline bool yc_sgt128(const uint128_t a, const uint128_t b) { if (a.h >= y_s64_min) { return b.h >= y_s64_min ? yc_ugt128(a, b) : false; } else { return b.h >= y_s64_min ? true : yc_ugt128(a, b); } } y_inline static inline bool yc_sge128(const uint128_t a, const uint128_t b) { if (a.h >= y_s64_min) { return b.h >= y_s64_min ? yc_uge128(a, b) : false; } else { return b.h >= y_s64_min ? true : yc_uge128(a, b); } } #endif // YC_INT128_STRUCT #undef YC_BOTTOM32 #undef YC_TRUNC32 #undef YC_CHOP32 // clang-format on /** * Left rotate 16-bit @a x by @a k bits. This has no undefined behavior. * @param x 16-bit value to rotate. * @param k Number of bits to rotate. The true rotation amount is this param * modulus 16. * @return The rotated 16-bit value. */ y_inline static inline uint16_t y_lrot16(uint16_t x, y_sint k) y_inline { return ((uint16_t) (x << (k & 15))) | ((uint16_t) (x >> (y_sintsneg(k) & 15))); } /** * Right rotate 16-bit @a x by @a k bits. This has no undefined behavior. * @param x 16-bit value to rotate. * @param k Number of bits to rotate. The true rotation amount is this param * modulus 16. * @return The rotated 16-bit value. */ y_inline static inline uint16_t y_rrot16(uint16_t x, y_sint k) y_inline { return ((uint16_t) (x >> (k & 15))) | ((uint16_t) (x << (y_sintsneg(k) & 15))); } /** * Left rotate 32-bit @a x by @a k bits. This has no undefined behavior. * @param x 32-bit value to rotate. * @param k Number of bits to rotate. The true rotation amount is this param * modulus 32. * @return The rotated 32-bit value. */ y_inline static inline uint32_t y_lrot32(uint32_t x, y_sint k) y_inline { return ((uint32_t) (x << (k & 31))) | ((uint32_t) (x >> (y_sintsneg(k) & 31))); } /** * Right rotate 32-bit @a x by @a k bits. This has no undefined behavior. * @param x 32-bit value to rotate. * @param k Number of bits to rotate. The true rotation amount is this param * modulus 32. * @return The rotated 32-bit value. */ y_inline static inline uint32_t y_rrot32(uint32_t x, y_sint k) y_inline { return ((uint32_t) (x >> (k & 31))) | ((uint32_t) (x << (y_sintsneg(k) & 31))); } /** * Left rotate 64-bit @a x by @a k bits. This has no undefined behavior. * @param x 64-bit value to rotate. * @param k Number of bits to rotate. The true rotation amount is this param * modulus 64. * @return The rotated 64-bit value. */ y_inline static inline uint64_t y_lrot64(uint64_t x, y_sint k) y_inline { return (x << (k & 63)) | (x >> (y_sintsneg(k) & 63)); } /** * Right rotate 64-bit @a x by @a k bits. This has no undefined behavior. * @param x 64-bit value to rotate. * @param k Number of bits to rotate. The true rotation amount is this param * modulus 64. * @return The rotated 64-bit value. */ y_inline static inline uint64_t y_rrot64(uint64_t x, y_sint k) y_inline { return (x >> (k & 63)) | (x << (y_sintsneg(k) & 63)); } /** * @} */ #ifdef __cplusplus } #endif #endif // YC_ARITH_H