From c2a0ee58865c5abad40acc59549dd98f40a8f7aa Mon Sep 17 00:00:00 2001 From: Thomas Koenig Date: Mon, 27 Jan 2025 18:43:44 +0100 Subject: Add modular exponentiation for UNSIGNED. gcc/fortran/ChangeLog: * arith.cc (arith_power): Handle modular arithmetic for BT_UNSIGNED. (eval_intrinsic): Error for unsigned exponentiation with -pedantic. * expr.cc (gfc_type_convert_binary): Use type of first argument for unsigned exponentiation. * gfortran.texi: Mention arithmetic exponentiation. * resolve.cc (resolve_operator): Allow unsigned exponentiation. * trans-decl.cc (gfc_build_intrinsic_function_decls): Build declarations for unsigned exponentiation. * trans-expr.cc (gfc_conv_cst_uint_power): New function. (gfc_conv_power_op): Call it. Handle unsigned exponentiation. * trans.h (gfor_fndecl_unsigned_pow_list): Add declaration. libgfortran/ChangeLog: * Makefile.am: Add files for unsigned exponentiation. * Makefile.in: Regenerate. * gfortran.map: Add functions for unsigned exponentiation. * generated/pow_m16_m1.c: New file. * generated/pow_m16_m16.c: New file. * generated/pow_m16_m2.c: New file. * generated/pow_m16_m4.c: New file. * generated/pow_m16_m8.c: New file. * generated/pow_m1_m1.c: New file. * generated/pow_m1_m16.c: New file. * generated/pow_m1_m2.c: New file. * generated/pow_m1_m4.c: New file. * generated/pow_m1_m8.c: New file. * generated/pow_m2_m1.c: New file. * generated/pow_m2_m16.c: New file. * generated/pow_m2_m2.c: New file. * generated/pow_m2_m4.c: New file. * generated/pow_m2_m8.c: New file. * generated/pow_m4_m1.c: New file. * generated/pow_m4_m16.c: New file. * generated/pow_m4_m2.c: New file. * generated/pow_m4_m4.c: New file. * generated/pow_m4_m8.c: New file. * generated/pow_m8_m1.c: New file. * generated/pow_m8_m16.c: New file. * generated/pow_m8_m2.c: New file. * generated/pow_m8_m4.c: New file. * generated/pow_m8_m8.c: New file. * m4/powu.m4: New file. gcc/testsuite/ChangeLog: * gfortran.dg/unsigned_15.f90: Adjust error messages. * gfortran.dg/unsigned_43.f90: New test. * gfortran.dg/unsigned_44.f90: New test. --- libgfortran/generated/pow_m4_m4.c | 79 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 79 insertions(+) create mode 100644 libgfortran/generated/pow_m4_m4.c (limited to 'libgfortran/generated/pow_m4_m4.c') diff --git a/libgfortran/generated/pow_m4_m4.c b/libgfortran/generated/pow_m4_m4.c new file mode 100644 index 0000000..45cc693 --- /dev/null +++ b/libgfortran/generated/pow_m4_m4.c @@ -0,0 +1,79 @@ +/* Support routines for the intrinsic power (**) operator + for UNSIGNED, using modulo arithmetic. + Copyright (C) 2025 Free Software Foundation, Inc. + Contributed by Thomas Koenig. + +This file is part of the GNU Fortran 95 runtime library (libgfortran). + +Libgfortran is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public +License as published by the Free Software Foundation; either +version 3 of the License, or (at your option) any later version. + +Libgfortran 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 General Public License for more details. + +Under Section 7 of GPL version 3, you are granted additional +permissions described in the GCC Runtime Library Exception, version +3.1, as published by the Free Software Foundation. + +You should have received a copy of the GNU General Public License and +a copy of the GCC Runtime Library Exception along with this program; +see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +. */ + +#include "libgfortran.h" + + +/* Use Binary Method to calculate the powi. This is not an optimal but + a simple and reasonable arithmetic. See section 4.6.3, "Evaluation of + Powers" of Donald E. Knuth, "Seminumerical Algorithms", Vol. 2, "The Art + of Computer Programming", 3rd Edition, 1998. */ + +#if defined (HAVE_GFC_UINTEGER_4) && defined (HAVE_GFC_UINTEGER_4) + +GFC_UINTEGER_4 pow_m4_m4 (GFC_UINTEGER_4 x, GFC_UINTEGER_4 n); +export_proto(pow_m4_m4); + +inline static GFC_UINTEGER_4 +power_simple_m4_m4 (GFC_UINTEGER_4 x, GFC_UINTEGER_4 n) +{ + GFC_UINTEGER_4 pow = 1; + for (;;) + { + if (n & 1) + pow *= x; + n >>= 1; + if (n) + x *= x; + else + break; + } + return pow; +} + +/* For odd x, Euler's theorem tells us that x**(2^(m-1)) = 1 mod 2^m. + For even x, we use the fact that (2*x)^m = 0 mod 2^m. */ + +GFC_UINTEGER_4 +pow_m4_m4 (GFC_UINTEGER_4 x, GFC_UINTEGER_4 n) +{ + const GFC_UINTEGER_4 mask = (GFC_UINTEGER_4) (-1) / 2; + if (n == 0) + return 1; + + if (x == 0) + return 0; + + if (x & 1) + return power_simple_m4_m4 (x, n & mask); + + if (n > sizeof (x) * 8) + return 0; + + return power_simple_m4_m4 (x, n); +} + +#endif -- cgit v1.1