1 // Copyright 2016-2021 Francesco Biscani (bluescarni@gmail.com)
2 //
3 // This file is part of the mp++ library.
4 //
5 // This Source Code Form is subject to the terms of the Mozilla
6 // Public License v. 2.0. If a copy of the MPL was not distributed
7 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
8
9 #include <array>
10 #include <cassert>
11 #include <cstddef>
12 #include <cstdlib>
13 #include <cstring>
14 #include <ios>
15 #include <iostream>
16 #include <locale>
17 #include <stdexcept>
18 #include <type_traits>
19 #include <utility>
20 #include <vector>
21
22 #include <mp++/config.hpp>
23 #include <mp++/detail/gmp.hpp>
24 #include <mp++/detail/type_traits.hpp>
25 #include <mp++/detail/utils.hpp>
26 #include <mp++/integer.hpp>
27
28 namespace mppp
29 {
30
31 namespace detail
32 {
33
34 namespace
35 {
36
37 // Some misc tests to check that the mpz struct conforms to our expectations.
38 // This is crucial for the implementation of the union integer type.
39 struct expected_mpz_struct_t {
40 mpz_alloc_t _mp_alloc;
41 mpz_size_t _mp_size;
42 ::mp_limb_t *_mp_d;
43 };
44
45 static_assert(sizeof(expected_mpz_struct_t) == sizeof(mpz_struct_t) && std::is_standard_layout<mpz_struct_t>::value
46 && std::is_standard_layout<expected_mpz_struct_t>::value && offsetof(mpz_struct_t, _mp_alloc) == 0u
47 && offsetof(mpz_struct_t, _mp_size) == offsetof(expected_mpz_struct_t, _mp_size)
48 && offsetof(mpz_struct_t, _mp_d) == offsetof(expected_mpz_struct_t, _mp_d)
49 && std::is_same<::mp_limb_t *, decltype(std::declval<mpz_struct_t>()._mp_d)>::value &&
50 // mp_bitcnt_t is used in shift operators, so we double-check it is an unsigned integral. If it is not
51 // we might end up shifting by negative values, which is UB.
52 std::is_integral<::mp_bitcnt_t>::value && std::is_unsigned<::mp_bitcnt_t>::value &&
53 // The mpn functions accept sizes as ::mp_size_t, but we generally represent sizes as mpz_size_t.
54 // We need then to make sure we can always cast safely mpz_size_t to ::mp_size_t. Inspection
55 // of the gmp.h header seems to indicate that mpz_size_t is never larger than ::mp_size_t.
56 // NOTE: since mp_size_t is the size type used by mpn functions, it is expected that it cannot
57 // have smaller range than mpz_size_t, otherwise mpz_t would contain numbers too large to be
58 // used as arguments in the mpn functions.
59 // NOLINTNEXTLINE(misc-redundant-expression)
60 nl_min<mpz_size_t>() >= nl_min<::mp_size_t>() && nl_max<mpz_size_t>() <= nl_max<::mp_size_t>(),
61 "Invalid mpz_t struct layout and/or GMP types.");
62
63 #if MPPP_CPLUSPLUS >= 201703L
64
65 // If we have C++17, we can use structured bindings to test the layout of mpz_struct_t
66 // and its members' types.
test_mpz_struct_t()67 constexpr bool test_mpz_struct_t()
68 {
69 // NOTE: if mpz_struct_t has more or fewer members, this will result
70 // in a compile-time error.
71 auto [alloc, size, ptr] = mpz_struct_t{};
72 ignore(alloc, size, ptr);
73 // NOLINTNEXTLINE(misc-redundant-expression)
74 return std::is_same<decltype(alloc), mpz_alloc_t>::value && std::is_same<decltype(size), mpz_size_t>::value
75 && std::is_same<decltype(ptr), ::mp_limb_t *>::value;
76 }
77
78 static_assert(test_mpz_struct_t(), "The mpz_struct_t does not have the expected layout.");
79
80 #endif
81
82 // The reason we are asserting this is the following: in a few places we are using the wrap-around property
83 // of unsigned arithmetics, but if mp_limb_t is a narrow unsigned type (e.g., unsigned short or unsigned char)
84 // then there could be a promotion to other types triggered by the standard integral promotions,
85 // and the wrap around behaviour would not be there any more. This is just a theoretical concern at the moment.
86 static_assert(disjunction<std::is_same<::mp_limb_t, unsigned long>, std::is_same<::mp_limb_t, unsigned long long>,
87 std::is_same<::mp_limb_t, unsigned>>::value,
88 "Invalid type for mp_limb_t.");
89
90 } // namespace
91
clear()92 void mpz_alloc_cache::clear() noexcept
93 {
94 #if !defined(NDEBUG)
95 std::cout << "Cleaning up the mpz alloc cache." << std::endl;
96 #endif
97 // Get the GMP free() function.
98 void (*ffp)(void *, std::size_t) = nullptr;
99 ::mp_get_memory_functions(nullptr, nullptr, &ffp);
100 assert(ffp != nullptr);
101 for (std::size_t i = 0; i < max_size; ++i) {
102 // Free all the limbs arrays allocated for this size.
103 for (std::size_t j = 0; j < sizes[i]; ++j) {
104 ffp(static_cast<void *>(caches[i][j]), i + 1u);
105 }
106 // Reset the number of limbs array present in this
107 // cache entry.
108 sizes[i] = 0u;
109 }
110 }
111
112 #if defined(MPPP_HAVE_THREAD_LOCAL)
113
114 namespace
115 {
116
117 // Thread local allocation cache.
118 // NOTE: some link/notes regarding thread_local:
119 // - thread_local alone also implies "static":
120 // http://eel.is/c++draft/dcl.stc
121 // https://stackoverflow.com/questions/22794382/are-c11-thread-local-variables-automatically-static
122 // - all variables declared thread_local have "thread storage duration", that is,
123 // they live for the duration of the thread: http://eel.is/c++draft/basic.stc.thread
124 // - there are 2 ways variables with thread storage duration may be initialised:
125 // - static initialisation, which is possible for constexpr-like entities:
126 // http://eel.is/c++draft/basic.start.static
127 // Note that it says: "Constant initialization is performed if a variable or temporary object with static or thread
128 // storage duration is initialized by a constant initializer for the entity". So it seems like block-scope
129 // variables with thread storage duration will be initialised as part of constant initialisation at thread startup,
130 // if possible. See also the cppreference page:
131 // https://en.cppreference.com/w/cpp/language/storage_duration#Static_local_variables
132 // (here it is talking about static local variables, but it should apply also to thread_local variables
133 // as indicated here: https://en.cppreference.com/w/cpp/language/initialization).
134 // - dynamic initialisation otherwise, meaning that the variable is initialised the first time control
135 // passes through its declaration:
136 // http://eel.is/c++draft/stmt.dcl#4
137 // - destruction of objects with thread storage duration happens before the destruction of objects with
138 // static storage duration:
139 // http://eel.is/c++draft/basic.start.term#2
140 // - "All static initialization strongly happens before any dynamic initialization.":
141 // http://eel.is/c++draft/basic.start#static-2
142 // - "If the completion of the constructor or dynamic initialization of an object with thread storage duration is
143 // sequenced before that of another, the completion of the destructor of the second is sequenced before the initiation
144 // of the destructor of the first." (that is, objects are destroyed in reverse with respect to construction order):
145 // http://eel.is/c++draft/basic.start.term#3
146 // NOTE: because the ctor of mpz_alloc_cache is constexpr,
147 // then the init of this thread_local variable will happen
148 // before any dynamic initialisation:
149 // https://en.cppreference.com/w/cpp/language/constant_initialization
150 // NOLINTNEXTLINE(cppcoreguidelines-avoid-non-const-global-variables)
151 MPPP_CONSTINIT thread_local mpz_alloc_cache mpz_alloc_cache_inst;
152
153 // Implementation of the init of an mpz from cache.
mpz_init_from_cache_impl(mpz_struct_t & rop,std::size_t nlimbs)154 bool mpz_init_from_cache_impl(mpz_struct_t &rop, std::size_t nlimbs)
155 {
156 auto &mpzc = mpz_alloc_cache_inst;
157 if (nlimbs != 0u && nlimbs <= mpzc.max_size && mpzc.sizes[nlimbs - 1u] != 0u) {
158 // LCOV_EXCL_START
159 if (mppp_unlikely(nlimbs > make_unsigned(nl_max<mpz_alloc_t>()))) {
160 std::abort();
161 }
162 // LCOV_EXCL_STOP
163 const auto idx = nlimbs - 1u;
164 rop._mp_alloc = static_cast<mpz_alloc_t>(nlimbs);
165 rop._mp_size = 0;
166 rop._mp_d = mpzc.caches[idx][mpzc.sizes[idx] - 1u];
167 --mpzc.sizes[idx];
168 return true;
169 }
170 return false;
171 }
172
173 } // namespace
174
get_thread_local_mpz_cache()175 mpz_alloc_cache &get_thread_local_mpz_cache()
176 {
177 return mpz_alloc_cache_inst;
178 }
179
180 #endif
181
mpz_init_nlimbs(mpz_struct_t & rop,std::size_t nlimbs)182 void mpz_init_nlimbs(mpz_struct_t &rop, std::size_t nlimbs)
183 {
184 #if defined(MPPP_HAVE_THREAD_LOCAL)
185 if (!mpz_init_from_cache_impl(rop, nlimbs)) {
186 #endif
187 // LCOV_EXCL_START
188 // A bit of horrid overflow checking.
189 if (mppp_unlikely(nlimbs > nl_max<std::size_t>() / unsigned(GMP_NUMB_BITS))) {
190 // NOTE: here we are doing what GMP does in case of memory allocation errors. It does not make much sense
191 // to do anything else, as long as GMP does not provide error recovery.
192 std::abort();
193 }
194 // LCOV_EXCL_STOP
195 const auto nbits = static_cast<std::size_t>(unsigned(GMP_NUMB_BITS) * nlimbs);
196 // LCOV_EXCL_START
197 if (mppp_unlikely(nbits > nl_max<::mp_bitcnt_t>())) {
198 std::abort();
199 }
200 // LCOV_EXCL_STOP
201 // NOTE: nbits == 0 is allowed.
202 mpz_init2(&rop, static_cast<::mp_bitcnt_t>(nbits));
203 assert(make_unsigned_t<mpz_alloc_t>(rop._mp_alloc) >= nlimbs);
204 #if defined(MPPP_HAVE_THREAD_LOCAL)
205 }
206 #endif
207 }
208
mpz_init_nbits(mpz_struct_t & rop,::mp_bitcnt_t nbits,std::size_t nlimbs)209 void mpz_init_nbits(mpz_struct_t &rop, ::mp_bitcnt_t nbits, std::size_t nlimbs)
210 {
211 // Check nlimbs.
212 assert(nlimbs == nbits_to_nlimbs(nbits));
213 #if defined(MPPP_HAVE_THREAD_LOCAL)
214 if (!mpz_init_from_cache_impl(rop, nlimbs)) {
215 #endif
216 ignore(nlimbs);
217 // NOTE: nbits == 0 is allowed.
218 mpz_init2(&rop, nbits);
219 #if defined(MPPP_HAVE_THREAD_LOCAL)
220 }
221 #endif
222 }
223
mpz_clear_wrap(mpz_struct_t & m)224 void mpz_clear_wrap(mpz_struct_t &m)
225 {
226 #if defined(MPPP_HAVE_THREAD_LOCAL)
227 auto &mpzc = mpz_alloc_cache_inst;
228 const auto ualloc = make_unsigned(m._mp_alloc);
229 if (ualloc != 0u && ualloc <= mpzc.max_size && mpzc.sizes[ualloc - 1u] < mpzc.max_entries) {
230 const auto idx = ualloc - 1u;
231 mpzc.caches[idx][mpzc.sizes[idx]] = m._mp_d;
232 ++mpzc.sizes[idx];
233 } else {
234 #endif
235 mpz_clear(&m);
236 #if defined(MPPP_HAVE_THREAD_LOCAL)
237 }
238 #endif
239 }
240
mpz_to_str(std::vector<char> & out,const mpz_struct_t * mpz,int base)241 void mpz_to_str(std::vector<char> &out, const mpz_struct_t *mpz, int base)
242 {
243 assert(base >= 2 && base <= 62);
244 const auto size_base = mpz_sizeinbase(mpz, base);
245 // LCOV_EXCL_START
246 if (mppp_unlikely(size_base > nl_max<std::size_t>() - 2u)) {
247 throw std::overflow_error("Too many digits in the conversion of mpz_t to string");
248 }
249 // LCOV_EXCL_STOP
250 // Total max size is the size in base plus an optional sign and the null terminator.
251 const auto total_size = size_base + 2u;
252 // NOTE: possible improvement: use a null allocator to avoid initing the chars each time
253 // we resize up.
254 // Overflow check.
255 // LCOV_EXCL_START
256 if (mppp_unlikely(total_size > nl_max<std::vector<char>::size_type>())) {
257 throw std::overflow_error("Too many digits in the conversion of mpz_t to string");
258 }
259 // LCOV_EXCL_STOP
260 out.resize(static_cast<std::vector<char>::size_type>(total_size));
261 mpz_get_str(out.data(), base, mpz);
262 }
263
integer_stream_operator_impl(std::ostream & os,const mpz_struct_t * n,int n_sgn)264 std::ostream &integer_stream_operator_impl(std::ostream &os, const mpz_struct_t *n, int n_sgn)
265 {
266 // Get the stream width.
267 const auto width = os.width();
268
269 // Fetch the stream's flags.
270 const auto flags = os.flags();
271
272 // Start by figuring out the base.
273 const auto base = stream_flags_to_base(flags);
274
275 // Should we prefix the base? Do it only if:
276 // - the number is nonzero,
277 // - the showbase flag is set,
278 // - the base is not 10.
279 const bool with_base_prefix = n_sgn != 0 && (flags & std::ios_base::showbase) != 0 && base != 10;
280
281 // Uppercase?
282 const bool uppercase = (flags & std::ios_base::uppercase) != 0;
283
284 // Write out to a temporary vector in the required base. This will produce
285 // a representation in the required base, with no base prefix and no
286 // extra '+' for nonnegative integers.
287 MPPP_MAYBE_TLS std::vector<char> tmp;
288 mpz_to_str(tmp, n, base);
289 // NOTE: tmp contains the terminator, and it might be
290 // larger than needed. Make sure to shrink it so that
291 // the last element is the terminator.
292 tmp.resize(static_cast<decltype(tmp.size())>(std::strlen(tmp.data())) + 1u);
293
294 if (n_sgn == -1) {
295 // Negative number.
296 if (with_base_prefix) {
297 // If we need the base prefix, we will have to add the base after the minus sign.
298 assert(tmp[0] == '-');
299 if (base == 16) {
300 constexpr std::array<char, 2> hex_prefix = {{'0', 'x'}};
301 tmp.insert(tmp.begin() + 1, hex_prefix.begin(), hex_prefix.end());
302 } else {
303 tmp.insert(tmp.begin() + 1, '0');
304 }
305 }
306 } else {
307 // Nonnegative number. We will be prepending up to 3 characters to the number
308 // representation:
309 // - 1 or 2 for the base prefix ('0' for octal, '0x'/'0X' for hex),
310 // - the '+' sign, if requested.
311 const bool with_plus = (flags & std::ios_base::showpos) != 0;
312 // NOLINTNEXTLINE(cppcoreguidelines-pro-type-member-init, hicpp-member-init)
313 std::array<char, 3> prep_buffer;
314 const auto prep_n = [&prep_buffer, with_plus, with_base_prefix, base]() -> std::size_t {
315 std::size_t ret = 0;
316 if (with_plus) {
317 prep_buffer[ret++] = '+';
318 }
319 if (with_base_prefix) {
320 prep_buffer[ret++] = '0';
321 if (base == 16) {
322 prep_buffer[ret++] = 'x';
323 }
324 }
325 return ret;
326 }();
327 // Prepend the additional characters.
328 tmp.insert(tmp.begin(), prep_buffer.data(), prep_buffer.data() + prep_n);
329 }
330
331 // Apply a final toupper() transformation in base 16, if needed,
332 // but do it before doing the filling in order to avoid
333 // uppercasing the fill character.
334 if (base == 16 && uppercase) {
335 const auto &cloc = std::locale::classic();
336 for (decltype(tmp.size()) i = 0; i < tmp.size() - 1u; ++i) {
337 if (std::isalpha(tmp[i], cloc)) {
338 tmp[i] = std::toupper(tmp[i], cloc);
339 }
340 }
341 }
342
343 // Compute the total size of the number
344 // representation (i.e., without fill characters).
345 // NOTE: -1 because of the terminator.
346 assert(!tmp.empty());
347 const auto final_size = tmp.size() - 1u;
348
349 // We are going to do the filling
350 // only if the stream width is larger
351 // than the total size of the number.
352 if (width >= 0 && make_unsigned(width) > final_size) {
353 // Determine the fill type.
354 const auto fill = stream_flags_to_fill(flags);
355 // Compute how much fill we need.
356 const auto fill_size = safe_cast<decltype(tmp.size())>(make_unsigned(width) - final_size);
357 // Get the fill character.
358 const auto fill_char = os.fill();
359
360 switch (fill) {
361 case 1:
362 // Left fill: fill characters at the end.
363 // NOTE: minus 1 because of the terminator.
364 tmp.insert(tmp.end() - 1, fill_size, fill_char);
365 break;
366 case 2:
367 // Right fill: fill characters at the beginning.
368 tmp.insert(tmp.begin(), fill_size, fill_char);
369 break;
370 default: {
371 assert(fill == 3);
372
373 // Internal fill: the fill characters are always after the sign (if present)
374 // and the base prefix (if present).
375 auto delta = static_cast<int>(tmp[0] == '+' || tmp[0] == '-');
376 if (with_base_prefix) {
377 delta += 1 + static_cast<int>(base == 16);
378 }
379 tmp.insert(tmp.begin() + delta, fill_size, fill_char);
380 break;
381 }
382 }
383 }
384
385 // Write out the unformatted data.
386 // NOTE: minus 1 because of the terminator.
387 os.write(tmp.data(), safe_cast<std::streamsize>(tmp.size() - 1u));
388
389 // Reset the stream width to zero, like the operator<<() does for builtin types.
390 // https://en.cppreference.com/w/cpp/io/manip/setw
391 // Do it here so we ensure we don't alter the state of the stream until the very end.
392 os.width(0);
393
394 return os;
395 }
396
397 } // namespace detail
398
free_integer_caches()399 void free_integer_caches()
400 {
401 #if defined(MPPP_HAVE_THREAD_LOCAL)
402 detail::mpz_alloc_cache_inst.clear();
403 #endif
404 }
405
406 } // namespace mppp
407