Script 'mail_helper' called by obssrc Hello community, here is the log from the commit of package fplll for openSUSE:Factory checked in at 2022-05-25 20:35:12 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Comparing /work/SRC/openSUSE:Factory/fplll (Old) and /work/SRC/openSUSE:Factory/.fplll.new.2254 (New) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "fplll" Wed May 25 20:35:12 2022 rev:10 rq:979163 version:5.4.2 Changes: -------- --- /work/SRC/openSUSE:Factory/fplll/fplll.changes 2021-05-15 01:25:03.646840882 +0200 +++ /work/SRC/openSUSE:Factory/.fplll.new.2254/fplll.changes 2022-05-25 20:35:56.320342886 +0200 @@ -1,0 +2,7 @@ +Wed May 25 10:45:53 UTC 2022 - Jan Engelhardt <[email protected]> + +- Update to release 5.4.2 + * Exacteval fix + * Document the role of the `u` parameter in LLL_reduction + +------------------------------------------------------------------- Old: ---- fplll-5.4.1.tar.gz New: ---- fplll-5.4.2.tar.gz ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Other differences: ------------------ ++++++ fplll.spec ++++++ --- /var/tmp/diff_new_pack.bZFfAv/_old 2022-05-25 20:35:56.764343506 +0200 +++ /var/tmp/diff_new_pack.bZFfAv/_new 2022-05-25 20:35:56.768343511 +0200 @@ -1,7 +1,7 @@ # # spec file for package fplll # -# Copyright (c) 2021 SUSE LLC +# Copyright (c) 2022 SUSE LLC # # All modifications and additions to the file contributed by third parties # remain the property of their copyright owners, unless otherwise agreed @@ -18,7 +18,7 @@ Name: fplll %define lname libfplll7 -Version: 5.4.1 +Version: 5.4.2 Release: 0 Summary: Lenstra-Lov??sz Lattice Basis Reduction Algorithm Library License: LGPL-2.1-or-later ++++++ fplll-5.4.1.tar.gz -> fplll-5.4.2.tar.gz ++++++ ++++ 2025 lines of diff (skipped) ++++ retrying with extended exclude list diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/README.md new/fplll-5.4.2/README.md --- old/fplll-5.4.1/README.md 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/README.md 2022-05-24 19:36:03.000000000 +0200 @@ -17,8 +17,8 @@ @unpublished{fplll, author = {The {FPLLL} development team}, - title = {{fplll}, a lattice reduction library, {Version}: 5.4.1}, - year = 2021, + title = {{fplll}, a lattice reduction library, {Version}: 5.4.2}, + year = 2022, note = {Available at \url{https://github.com/fplll/fplll}}, url = {https://github.com/fplll/fplll} } @@ -409,7 +409,7 @@ - [json.hpp](fplll/io/json.hpp) is taken from https://github.com/nlohmann/json -- This project has been supported by ERC Starting Grant ERC-2013-StG-335086-LATTAC. +- This project has been supported by ERC Starting Grant ERC-2013-StG-335086-LATTAC, by the European Union PROMETHEUS project (Horizon 2020 Research and Innovation Program, grant 780701), by EPSRC grant EP/P009417/1 and by EPSRC grant EP/S020330/1. # Contributing # diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/configure.ac new/fplll-5.4.2/configure.ac --- old/fplll-5.4.1/configure.ac 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/configure.ac 2022-05-24 19:36:03.000000000 +0200 @@ -1,10 +1,11 @@ # -*- Autoconf -*- # Process this file with autoconf to produce a configure script. -AC_PREREQ(2.61) -AC_INIT(fplll, 5.4.1) +AC_PREREQ([2.69]) +AC_INIT([fplll],[5.4.2]) AC_CONFIG_SRCDIR([fplll/fplll.cpp]) AM_MAINTAINER_MODE([enable]) +AC_CANONICAL_TARGET # cf http://comments.gmane.org/gmane.comp.sysutils.autoconf.general/15737 @@ -19,7 +20,7 @@ AM_INIT_AUTOMAKE([foreign subdir-objects]) m4_ifdef([AM_SILENT_RULES], [AM_SILENT_RULES([yes])]) -AC_CONFIG_HEADER(config.h) +AC_CONFIG_HEADERS([config.h]) DEFAULT_CXXFLAGS="-O3 -Wall" @@ -40,7 +41,7 @@ # current, and set both revision and age to zero. FPLLL_LT_CURRENT=7 -FPLLL_LT_REVISION=0 +FPLLL_LT_REVISION=1 FPLLL_LT_AGE=0 AC_SUBST(FPLLL_LT_CURRENT) @@ -50,7 +51,7 @@ AC_PROG_INSTALL # Checks for programs. -AC_LANG_CPLUSPLUS +AC_LANG([C++]) AC_PROG_CXX AC_PROG_CC AC_PROG_MAKE_SET @@ -139,8 +140,6 @@ # the AC_SEARCH_LIBS macro works. AC_SUBST(LIBQD_LIBS) -# Checks for header files. -AC_HEADER_STDC AC_CHECK_HEADERS([limits.h cstdio iostream string limits vector]) # Checks for typedefs, structures, and compiler characteristics. @@ -176,7 +175,7 @@ AC_DEFINE([FPLLL_WITH_RECURSIVE_ENUM], [1], [recursive enumeration enabled])]) -max_parallel_enum_dim=80 +max_parallel_enum_dim=120 AC_ARG_WITH(max-parallel-enum-dim, AS_HELP_STRING([--with-max-parallel-enum-dim@<:@=DIM@:>@], [Maximum supported parallel enumeration dimension (max=160, default=120, disable=0).]), diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/fplll/Makefile.am new/fplll-5.4.2/fplll/Makefile.am --- old/fplll-5.4.1/fplll/Makefile.am 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/fplll/Makefile.am 2022-05-24 19:36:03.000000000 +0200 @@ -124,7 +124,6 @@ install-data-hook: echo "#include <fplll/fplll.h>" > "$(builddir)/fplll.h.root" - echo "using namespace fplll;" >> "$(builddir)/fplll.h.root" $(INSTALL) -m 644 "$(builddir)/fplll.h.root" "${DESTDIR}$(includedir)/fplll.h" rm -f "$(builddir)/fplll.h.root" diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/fplll/bkz_param.cpp new/fplll-5.4.2/fplll/bkz_param.cpp --- old/fplll-5.4.1/fplll/bkz_param.cpp 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/fplll/bkz_param.cpp 2022-05-24 19:36:03.000000000 +0200 @@ -81,7 +81,7 @@ { json js; { - std::ifstream fs(filename); + std::ifstream fs(strategy_full_path(filename)); if (fs.fail()) throw std::runtime_error("Cannot open strategies file."); fs >> js; diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/fplll/enum/enumerate_base.cpp new/fplll-5.4.2/fplll/enum/enumerate_base.cpp --- old/fplll-5.4.1/fplll/enum/enumerate_base.cpp 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/fplll/enum/enumerate_base.cpp 2022-05-24 19:36:03.000000000 +0200 @@ -77,69 +77,42 @@ << " newdist=" << newdist << " partdistbounds_k=" << partdistbounds[kk]); enumerate_recursive(opts<kk - 1, kk_start, dualenum, findsubsols, enable_reset>()); - if (partdist[kk] != 0.0) + if (!is_svp || partdist[kk] != 0.0) { x[kk] += dx[kk]; ddx[kk] = -ddx[kk]; dx[kk] = ddx[kk] - dx[kk]; - - enumf alphak2 = x[kk] - center[kk]; - enumf newdist2 = partdist[kk] + alphak2 * alphak2 * rdiag[kk]; - if (!(newdist2 <= partdistbounds[kk])) - return; - ++nodes[kk]; - alpha[kk] = alphak2; - if (kk == 0) - { - if (newdist2 > 0.0 || !is_svp) - process_solution(newdist2); - } - else - { - partdist[kk - 1] = newdist2; - if (dualenum) - center_partsums[kk - 1][kk - 1 + 1] = - center_partsums[kk - 1][kk - 1 + 1 + 1] - alpha[kk - 1 + 1] * mut[kk - 1][kk - 1 + 1]; - else - center_partsums[kk - 1][kk - 1 + 1] = - center_partsums[kk - 1][kk - 1 + 1 + 1] - x[kk - 1 + 1] * mut[kk - 1][kk - 1 + 1]; - if (kk > center_partsum_begin[kk - 1]) - center_partsum_begin[kk - 1] = kk; - center[kk - 1] = center_partsums[kk - 1][kk - 1 + 1]; - roundto(x[kk - 1], center[kk - 1]); - dx[kk - 1] = ddx[kk - 1] = (((int)(center[kk - 1] >= x[kk - 1]) & 1) << 1) - 1; - } } else { ++x[kk]; + } - enumf alphak2 = x[kk] - center[kk]; - enumf newdist2 = partdist[kk] + alphak2 * alphak2 * rdiag[kk]; - if (!(newdist2 <= partdistbounds[kk])) - return; - ++nodes[kk]; - alpha[kk] = alphak2; - if (kk == 0) - { - if (newdist2 > 0.0 || !is_svp) - process_solution(newdist2); - } + enumf alphak2 = x[kk] - center[kk]; + enumf newdist2 = partdist[kk] + alphak2 * alphak2 * rdiag[kk]; + if (!(newdist2 <= partdistbounds[kk])) + return; + ++nodes[kk]; + alpha[kk] = alphak2; + if (kk == 0) + { + if (newdist2 > 0.0 || !is_svp) + process_solution(newdist2); + } + else + { + partdist[kk - 1] = newdist2; + if (dualenum) + center_partsums[kk - 1][kk - 1 + 1] = + center_partsums[kk - 1][kk - 1 + 1 + 1] - alpha[kk - 1 + 1] * mut[kk - 1][kk - 1 + 1]; else - { - partdist[kk - 1] = newdist2; - if (dualenum) - center_partsums[kk - 1][kk - 1 + 1] = - center_partsums[kk - 1][kk - 1 + 1 + 1] - alpha[kk - 1 + 1] * mut[kk - 1][kk - 1 + 1]; - else - center_partsums[kk - 1][kk - 1 + 1] = - center_partsums[kk - 1][kk - 1 + 1 + 1] - x[kk - 1 + 1] * mut[kk - 1][kk - 1 + 1]; - if (kk > center_partsum_begin[kk - 1]) - center_partsum_begin[kk - 1] = kk; - center[kk - 1] = center_partsums[kk - 1][kk - 1 + 1]; - roundto(x[kk - 1], center[kk - 1]); - dx[kk - 1] = ddx[kk - 1] = (((int)(center[kk - 1] >= x[kk - 1]) & 1) << 1) - 1; - } + center_partsums[kk - 1][kk - 1 + 1] = + center_partsums[kk - 1][kk - 1 + 1 + 1] - x[kk - 1 + 1] * mut[kk - 1][kk - 1 + 1]; + if (kk > center_partsum_begin[kk - 1]) + center_partsum_begin[kk - 1] = kk; + center[kk - 1] = center_partsums[kk - 1][kk - 1 + 1]; + roundto(x[kk - 1], center[kk - 1]); + dx[kk - 1] = ddx[kk - 1] = (((int)(center[kk - 1] >= x[kk - 1]) & 1) << 1) - 1; } } } diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/fplll/enum/enumerate_base.h new/fplll-5.4.2/fplll/enum/enumerate_base.h --- old/fplll-5.4.1/fplll/enum/enumerate_base.h 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/fplll/enum/enumerate_base.h 2022-05-24 19:36:03.000000000 +0200 @@ -72,7 +72,7 @@ protected: /* configuration */ bool dual; - bool is_svp; + bool is_svp; // only for SVP: exploit symmetry in enumeration to half search space bool resetflag; /* enumeration input */ @@ -156,7 +156,17 @@ if (k >= k_end) return false; k_max = k; - ++x[k]; + if (is_svp) + { + // only for SVP: break symmetry at the top non-zero coefficient + ++x[k]; + } + else + { + x[k] += dx[k]; + ddx[k] = -ddx[k]; + dx[k] = ddx[k] - dx[k]; + } } return true; } diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/fplll/enum/evaluator.cpp new/fplll-5.4.2/fplll/enum/evaluator.cpp --- old/fplll-5.4.1/fplll/enum/evaluator.cpp 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/fplll/enum/evaluator.cpp 2022-05-24 19:36:03.000000000 +0200 @@ -283,7 +283,7 @@ vector<Z_NR<mpz_t>> new_sol, coord; gen_zero_vect(new_sol, n); - gen_zero_vect(coord, n); + gen_zero_vect(coord, gso.get_rows_of_b()); new_sol_dist = 0; // Computes the distance between x and zero @@ -320,7 +320,7 @@ vector<Z_NR<mpz_t>> new_sol, coord; gen_zero_vect(new_sol, n); - gen_zero_vect(coord, n); + gen_zero_vect(coord, gso.get_rows_of_b()); new_sol_dist = 0; // Computes the distance between x[[offset,d)] and zero diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/fplll/gso.h new/fplll-5.4.2/fplll/gso.h --- old/fplll-5.4.1/fplll/gso.h 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/fplll/gso.h 2022-05-24 19:36:03.000000000 +0200 @@ -213,7 +213,7 @@ ZT tmp; sqnorm = 0; vector_matrix_product(tmpvec, coordinates, b); - for (int j = 0; j < b.get_rows(); j++) + for (size_t j = 0; j < tmpvec.size(); j++) { tmp.mul(tmpvec[j], tmpvec[j]); sqnorm.add(sqnorm, tmp); diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/fplll/gso_interface.h new/fplll-5.4.2/fplll/gso_interface.h --- old/fplll-5.4.1/fplll/gso_interface.h 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/fplll/gso_interface.h 2022-05-24 19:36:03.000000000 +0200 @@ -71,6 +71,8 @@ * (in this case both must have the same number of rows). * If u is initially the identity matrix, multiplying transform by the * initial basis gives the current basis. + * In other words, u will contain the transformation matrix used on the basis b + * that was used to obtain the current basis. * @param u_inv_t * Inverse transform (should be empty, which disables the computation, or * initialized with identity matrix). It works only if u is not empty. @@ -202,21 +204,21 @@ * (lower triangular matrix) * mu(i, j) = r(i, j) / ||b*_j||^2. */ - const Matrix<FT> &get_mu_matrix() { return mu; } + const Matrix<FT> &get_mu_matrix() const { return mu; } /** * Returns the r matrix * Coefficients of the Gram Schmidt Orthogonalization * (lower triangular matrix) */ - const Matrix<FT> &get_r_matrix() { return r; } + const Matrix<FT> &get_r_matrix() const { return r; } /** * Returns the g matrix (Z_NR version of r) * Coefficients of the Gram Schmidt Orthogonalization * (lower triangular matrix) */ - const Matrix<ZT> &get_g_matrix() + const Matrix<ZT> &get_g_matrix() const { if (gptr == nullptr) { @@ -234,8 +236,8 @@ * The returned value is a reference to the coefficient of the internal * matrix, which may change if the matrix is modified. */ - inline const FT &get_mu_exp(int i, int j, long &expo); - inline const FT &get_mu_exp(int i, int j); + inline const FT &get_mu_exp(int i, int j, long &expo) const; + inline const FT &get_mu_exp(int i, int j) const; /** * Returns f = (b_i, b*_j) / ||b*_j||^2. @@ -262,8 +264,8 @@ * The returned value is a reference to the coefficient of the internal * matrix, which may change if the matrix is modified */ - inline const FT &get_r_exp(int i, int j, long &expo); - inline const FT &get_r_exp(int i, int j); + inline const FT &get_r_exp(int i, int j, long &expo) const; + inline const FT &get_r_exp(int i, int j) const; /** * Returns f = (b_i, b*_j). @@ -646,7 +648,7 @@ } template <class ZT, class FT> -inline const FT &MatGSOInterface<ZT, FT>::get_mu_exp(int i, int j, long &expo) +inline const FT &MatGSOInterface<ZT, FT>::get_mu_exp(int i, int j, long &expo) const { FPLLL_DEBUG_CHECK(i >= 0 && i < n_known_rows && j >= 0 && j < i && j < gso_valid_cols[i] && !in_row_op_range(i)); @@ -657,7 +659,8 @@ return mu(i, j); } -template <class ZT, class FT> inline const FT &MatGSOInterface<ZT, FT>::get_mu_exp(int i, int j) +template <class ZT, class FT> +inline const FT &MatGSOInterface<ZT, FT>::get_mu_exp(int i, int j) const { FPLLL_DEBUG_CHECK(i >= 0 && i < n_known_rows && j >= 0 && j < i && j < gso_valid_cols[i] && !in_row_op_range(i)); @@ -675,7 +678,7 @@ } template <class ZT, class FT> -inline const FT &MatGSOInterface<ZT, FT>::get_r_exp(int i, int j, long &expo) +inline const FT &MatGSOInterface<ZT, FT>::get_r_exp(int i, int j, long &expo) const { FPLLL_DEBUG_CHECK(i >= 0 && i < n_known_rows && j >= 0 && j < gso_valid_cols[i] && !in_row_op_range(i)); @@ -686,7 +689,8 @@ return r(i, j); } -template <class ZT, class FT> inline const FT &MatGSOInterface<ZT, FT>::get_r_exp(int i, int j) +template <class ZT, class FT> +inline const FT &MatGSOInterface<ZT, FT>::get_r_exp(int i, int j) const { FPLLL_DEBUG_CHECK(i >= 0 && i < n_known_rows && j >= 0 && j < gso_valid_cols[i] && !in_row_op_range(i)); diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/fplll/io/thread_pool.hpp new/fplll-5.4.2/fplll/io/thread_pool.hpp --- old/fplll-5.4.1/fplll/io/thread_pool.hpp 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/fplll/io/thread_pool.hpp 2022-05-24 19:36:03.000000000 +0200 @@ -27,10 +27,8 @@ * * \*********************************************************************************/ -// this file is slightly modified for fplll to use specialized header guards and namespace - -#ifndef FPLLL_THREAD_POOL_HPP -#define FPLLL_THREAD_POOL_HPP +#ifndef THREAD_POOL_HPP +#define THREAD_POOL_HPP #include <cstdint> #include <memory> @@ -44,10 +42,6 @@ #include <future> #include <atomic> - -#include <fplll/defs.h> -FPLLL_BEGIN_NAMESPACE - /*************************** example usage ***************************************\ grep "^//test.cpp" thread_pool.hpp -A33 > test.cpp g++ -std=c++11 -o test test.cpp -pthread -lpthread @@ -205,15 +199,19 @@ inline void thread_pool::push(const std::function<void()>& f) { - std::unique_lock<std::mutex> lock(_mutex); - _tasks.emplace(f); + { + std::unique_lock<std::mutex> lock(_mutex); + _tasks.emplace(f); + } _condition.notify_one(); } inline void thread_pool::push(std::function<void()>&& f) { - std::unique_lock<std::mutex> lock(_mutex); - _tasks.emplace(std::move(f)); + { + std::unique_lock<std::mutex> lock(_mutex); + _tasks.emplace(std::move(f)); + } _condition.notify_one(); } @@ -232,27 +230,42 @@ { if (threads < 1 || threads > int(_threads.size())+1) threads = int(_threads.size())+1; - for (int i = 0; i < threads; ++i) - this->push(f); - this->wait_work(); + { + std::unique_lock<std::mutex> lock(_mutex); + for (int i = 0; i < threads-1; ++i) + _tasks.emplace(f); + } + _condition.notify_all(); + f(); + this->wait_sleep(); } inline void thread_pool::run(const std::function<void(int)>& f, int threads) { if (threads < 1 || threads > int(_threads.size())+1) threads = int(_threads.size())+1; - for (int i = 0; i < threads; ++i) - this->push( [f,i](){f(i);} ); - this->wait_work(); + { + std::unique_lock<std::mutex> lock(_mutex); + for (int i = 0; i < threads-1; ++i) + _tasks.emplace( [=](){f(i);} ); + } + _condition.notify_all(); + f(threads-1); + this->wait_sleep(); } inline void thread_pool::run(const std::function<void(int,int)>& f, int threads) { if (threads < 1 || threads > int(_threads.size())+1) threads = int(_threads.size())+1; - for (int i = 0; i < threads; ++i) - this->push( [f,i,threads](){f(i,threads);} ); - this->wait_work(); + { + std::unique_lock<std::mutex> lock(_mutex); + for (int i = 0; i < threads-1; ++i) + _tasks.emplace( [=](){f(i,threads);} ); + } + _condition.notify_all(); + f(threads-1,threads); + this->wait_sleep(); } inline void thread_pool::resize(std::size_t nrthreads) @@ -338,6 +351,7 @@ if (++_i >= _count) { _i = 0; + lock.unlock(); _condition.notify_all(); } else @@ -348,6 +362,4 @@ } // namespace thread_pool -FPLLL_END_NAMESPACE - -#endif // FPLLL_THREAD_POOL_HPP +#endif // THREAD_POOL_HPP diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/fplll/lll.h new/fplll-5.4.2/fplll/lll.h --- old/fplll-5.4.1/fplll/lll.h 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/fplll/lll.h 2022-05-24 19:36:03.000000000 +0200 @@ -36,11 +36,9 @@ * needed). */ LLLReduction(MatGSOInterface<ZT, FT> &m, double delta, double eta, int flags); - #ifdef FPLLL_WITH_LONG_DOUBLE ~LLLReduction() { LDConvHelper::free(); } #endif - /** @brief LLL reduction. diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/fplll/main.cpp new/fplll-5.4.2/fplll/main.cpp --- old/fplll-5.4.1/fplll/main.cpp 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/fplll/main.cpp 2022-05-24 19:36:03.000000000 +0200 @@ -248,8 +248,8 @@ ZZ_mat<mpz_t> u; bool with_coord = strchr(format, 'c') != NULL; bool with_coord_std = strchr(format, 's') != NULL; - int flags = SVP_DEFAULT | (o.verbose ? SVP_VERBOSE : 0); int flagsLLL = LLL_DEFAULT | (o.verbose ? LLL_VERBOSE : 0); + int flags; int status; if (!o.no_lll) @@ -270,9 +270,15 @@ } if (target.empty()) + { + flags = SVP_DEFAULT | (o.verbose ? SVP_VERBOSE : 0); status = shortest_vector(b, sol_coord, SVPM_PROVED, flags); + } else - status = closest_vector(b, target, sol_coord, flags); + { + flags = CVP_DEFAULT | (o.verbose ? CVP_VERBOSE : 0); + status = closest_vector(b, target, sol_coord, CVPM_PROVED, flags); + } if (status != RED_SUCCESS) { diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/fplll/nr/nr_FP.inl new/fplll-5.4.2/fplll/nr/nr_FP.inl --- old/fplll-5.4.1/fplll/nr/nr_FP.inl 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/fplll/nr/nr_FP.inl 2022-05-24 19:36:03.000000000 +0200 @@ -29,7 +29,7 @@ */ inline FP_NR<F>(); inline FP_NR<F>(const FP_NR<F> &f); - inline ~FP_NR<F>(); + inline ~FP_NR(); inline FP_NR<F>(const double d) : FP_NR<F>() { *this = d; }; inline FP_NR<F>(const char *s) : FP_NR<F>() { *this = s; }; diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/fplll/nr/nr_Z.inl new/fplll-5.4.2/fplll/nr/nr_Z.inl --- old/fplll-5.4.1/fplll/nr/nr_Z.inl 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/fplll/nr/nr_Z.inl 2022-05-24 19:36:03.000000000 +0200 @@ -24,10 +24,10 @@ /** * Constructors. */ - inline Z_NR<Z>(); - inline Z_NR<Z>(const Z_NR<Z> &z); - inline Z_NR<Z>(const Z &z); - inline ~Z_NR<Z>(); + inline Z_NR(); + inline Z_NR(const Z_NR<Z> &z); + inline Z_NR(const Z &z); + inline ~Z_NR(); /** get data */ @@ -236,6 +236,14 @@ */ #ifdef FPLLL_WITH_LONG_DOUBLE +// Thread_local variables for doing numeric conversions. +// These are global to replace their previous usage, but member variables +// cannot be thread local and so they're declared at this scope. +// NOTE: these are extern because these can only have one definition. +// These are defined in util.cpp +extern thread_local mpfr_t temp_mpfr; +extern thread_local bool temp_mpfr_initialized; + class LDConvHelper { public: @@ -243,8 +251,8 @@ static long double mpz_get_ld(const mpz_t op) { init_temp(); - mpfr_set_z(temp, op, GMP_RNDN); - return mpfr_get_ld(temp, GMP_RNDN); // exact + mpfr_set_z(temp_mpfr, op, GMP_RNDN); + return mpfr_get_ld(temp_mpfr, GMP_RNDN); // exact } static void free() { free_temp(); } @@ -256,40 +264,36 @@ static long double mpz_get_ld_2exp(long *exp, const mpz_t op) { init_temp(); - mpfr_set_z(temp, op, GMP_RNDN); - return mpfr_get_ld_2exp(exp, temp, GMP_RNDN); // exact + mpfr_set_z(temp_mpfr, op, GMP_RNDN); + return mpfr_get_ld_2exp(exp, temp_mpfr, GMP_RNDN); // exact } /** Sets the value of rop from op. */ static void mpz_set_ld(mpz_t rop, long double op) { init_temp(); - mpfr_set_ld(temp, op, GMP_RNDN); // exact - mpfr_get_z(rop, temp, GMP_RNDN); + mpfr_set_ld(temp_mpfr, op, GMP_RNDN); // exact + mpfr_get_z(rop, temp_mpfr, GMP_RNDN); } private: static inline void init_temp() { - if (!temp_initialized) + if (!temp_mpfr_initialized) { - mpfr_init2(temp, numeric_limits<long double>::digits); - temp_initialized = true; + mpfr_init2(temp_mpfr, numeric_limits<long double>::digits); + temp_mpfr_initialized = true; } } static inline void free_temp() { - if (temp_initialized) + if (temp_mpfr_initialized) { - mpfr_clear(temp); - temp_initialized = false; + mpfr_clear(temp_mpfr); + temp_mpfr_initialized = false; } } - - // These static members are initialized in util.cpp - static mpfr_t temp; - static bool temp_initialized; }; #endif diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/fplll/util.cpp new/fplll-5.4.2/fplll/util.cpp --- old/fplll-5.4.1/fplll/util.cpp 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/fplll/util.cpp 2022-05-24 19:36:03.000000000 +0200 @@ -27,11 +27,13 @@ MINPREC_L2 }; -/* State of LDConvHelper (declared in nr.h, must be defined in exactly one - source file) */ +/* + Helper variables for LDConvHelper (declared in nr_Z.inl, must be defined in exactly + one source file) +*/ #ifdef FPLLL_WITH_LONG_DOUBLE -mpfr_t LDConvHelper::temp; -bool LDConvHelper::temp_initialized = false; +thread_local mpfr_t temp_mpfr; +thread_local bool temp_mpfr_initialized{false}; #endif /* State of the random generator (declared in nr.h, must be defined in exactly diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/fplll/util.h new/fplll-5.4.2/fplll/util.h --- old/fplll-5.4.1/fplll/util.h 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/fplll/util.h 2022-05-24 19:36:03.000000000 +0200 @@ -41,6 +41,7 @@ void vector_matrix_product(vector<ZT> &result, const vector<ZT> &x, const Matrix<ZT> &m) { int nrows = m.get_rows(), ncols = m.get_cols(); + FPLLL_CHECK(x.size() == (unsigned int)nrows, "vector_matrix_product(): dimensions do not match!"); gen_zero_vect(result, ncols); for (int i = 0; i < nrows; i++) for (int j = 0; j < ncols; j++) @@ -53,6 +54,7 @@ void vector_matrix_product(NumVect<ZT> &result, const NumVect<ZT> &x, const Matrix<ZT> &m) { int nrows = m.get_rows(), ncols = m.get_cols(); + FPLLL_CHECK(x.size() == nrows, "vector_matrix_product(): dimensions do not match!"); result.gen_zero(ncols); for (int i = 0; i < nrows; i++) for (int j = 0; j < ncols; j++) diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/fplll/wrapper.h new/fplll-5.4.2/fplll/wrapper.h --- old/fplll-5.4.1/fplll/wrapper.h 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/fplll/wrapper.h 2022-05-24 19:36:03.000000000 +0200 @@ -25,6 +25,28 @@ /* The matrix b must not be modified before calling lll(). lll() must be called only once. */ +/** + * @brief Wrapper. This class provides an externally callable API for LLL reducing some basis ``b``. + * This class forcibly instantiates some template declarations (see FPLLL_DECLARE_LLL(T) for more + * information at the bottom of this class) and provides an interface for calling provable, + * heuristic and fast variants of both LLL and HLLL. + * + * User note: all of the parameters passed into this class are non-const references. Thus, this + * class may overwrite these variables. + * + * In particular, the methods in this class typically + * over-write the parameter ``u`` with the transformation matrix applied to ``b`` to produce LLL(B). + * In other words, let C = LLL(B). Then we can write C = U B for some unimodular transformation + * matrix U. For this reason, ``u`` should either be an empty matrix or the identity matrix when it + * is passed in to this function, so that no information is lost. + * + * Similarly, the parameter ``u_inv`` will contain the inverse matrix ``u ^ -1``. + * This allows you to recover the original basis ``b`` by multiplying ``C`` by ``u_inv``. + * Note that all operations on this object are carried out on the transpose of this matrix + * (see gso_interface.h) for speed: hence the discrepancy between the names (see the lll_reduction + * method in wraper.cpp for this). This and other such behaviour on these parameters is described in + * some detail in gso_interface.h. + */ class Wrapper { public: diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/m4/ax_cxx_compile_stdcxx.m4 new/fplll-5.4.2/m4/ax_cxx_compile_stdcxx.m4 --- old/fplll-5.4.1/m4/ax_cxx_compile_stdcxx.m4 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/m4/ax_cxx_compile_stdcxx.m4 2022-05-24 19:36:03.000000000 +0200 @@ -16,7 +16,7 @@ # The second argument, if specified, indicates whether you insist on an # extended mode (e.g. -std=gnu++11) or a strict conformance mode (e.g. # -std=c++11). If neither is specified, you get whatever works, with -# preference for an extended mode. +# preference for no added switch, and then for an extended mode. # # The third argument, if specified 'mandatory' or if left unspecified, # indicates that baseline support for the specified C++ standard is @@ -35,13 +35,14 @@ # Copyright (c) 2015 Moritz Klammler <[email protected]> # Copyright (c) 2016, 2018 Krzesimir Nowak <[email protected]> # Copyright (c) 2019 Enji Cooper <[email protected]> +# Copyright (c) 2020 Jason Merrill <[email protected]> # # Copying and distribution of this file, with or without modification, are # permitted in any medium without royalty provided the copyright notice # and this notice are preserved. This file is offered as-is, without any # warranty. -#serial 11 +#serial 12 dnl This macro is based on the code from the AX_CXX_COMPILE_STDCXX_11 macro dnl (serial version number 13). @@ -62,6 +63,16 @@ AC_LANG_PUSH([C++])dnl ac_success=no + m4_if([$2], [], [dnl + AC_CACHE_CHECK(whether $CXX supports C++$1 features by default, + ax_cv_cxx_compile_cxx$1, + [AC_COMPILE_IFELSE([AC_LANG_SOURCE([_AX_CXX_COMPILE_STDCXX_testbody_$1])], + [ax_cv_cxx_compile_cxx$1=yes], + [ax_cv_cxx_compile_cxx$1=no])]) + if test x$ax_cv_cxx_compile_cxx$1 = xyes; then + ac_success=yes + fi]) + m4_if([$2], [noext], [], [dnl if test x$ac_success = xno; then for alternative in ${ax_cxx_compile_alternatives}; do diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/m4/ax_pthread.m4 new/fplll-5.4.2/m4/ax_pthread.m4 --- old/fplll-5.4.1/m4/ax_pthread.m4 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/m4/ax_pthread.m4 2022-05-24 19:36:03.000000000 +0200 @@ -14,20 +14,24 @@ # flags that are needed. (The user can also force certain compiler # flags/libs to be tested by setting these environment variables.) # -# Also sets PTHREAD_CC to any special C compiler that is needed for -# multi-threaded programs (defaults to the value of CC otherwise). (This -# is necessary on AIX to use the special cc_r compiler alias.) +# Also sets PTHREAD_CC and PTHREAD_CXX to any special C compiler that is +# needed for multi-threaded programs (defaults to the value of CC +# respectively CXX otherwise). (This is necessary on e.g. AIX to use the +# special cc_r/CC_r compiler alias.) # # NOTE: You are assumed to not only compile your program with these flags, # but also to link with them as well. For example, you might link with # $PTHREAD_CC $CFLAGS $PTHREAD_CFLAGS $LDFLAGS ... $PTHREAD_LIBS $LIBS +# $PTHREAD_CXX $CXXFLAGS $PTHREAD_CFLAGS $LDFLAGS ... $PTHREAD_LIBS $LIBS # # If you are only building threaded programs, you may wish to use these # variables in your default LIBS, CFLAGS, and CC: # # LIBS="$PTHREAD_LIBS $LIBS" # CFLAGS="$CFLAGS $PTHREAD_CFLAGS" +# CXXFLAGS="$CXXFLAGS $PTHREAD_CFLAGS" # CC="$PTHREAD_CC" +# CXX="$PTHREAD_CXX" # # In addition, if the PTHREAD_CREATE_JOINABLE thread-attribute constant # has a nonstandard name, this macro defines PTHREAD_CREATE_JOINABLE to @@ -83,11 +87,11 @@ # modified version of the Autoconf Macro, you may extend this special # exception to the GPL to apply to your modified version as well. -#serial 27 +#serial 30 AU_ALIAS([ACX_PTHREAD], [AX_PTHREAD]) AC_DEFUN([AX_PTHREAD], [ -AC_REQUIRE([AC_CANONICAL_HOST]) +AC_REQUIRE([AC_CANONICAL_TARGET]) AC_REQUIRE([AC_PROG_CC]) AC_REQUIRE([AC_PROG_SED]) AC_LANG_PUSH([C]) @@ -105,6 +109,7 @@ ax_pthread_save_CFLAGS="$CFLAGS" ax_pthread_save_LIBS="$LIBS" AS_IF([test "x$PTHREAD_CC" != "x"], [CC="$PTHREAD_CC"]) + AS_IF([test "x$PTHREAD_CXX" != "x"], [CXX="$PTHREAD_CXX"]) CFLAGS="$CFLAGS $PTHREAD_CFLAGS" LIBS="$PTHREAD_LIBS $LIBS" AC_MSG_CHECKING([for pthread_join using $CC $PTHREAD_CFLAGS $PTHREAD_LIBS]) @@ -153,7 +158,7 @@ # --thread-safe: KAI C++ # pthread-config: use pthread-config program (for GNU Pth library) -case $host_os in +case $target_os in freebsd*) @@ -243,7 +248,7 @@ # definitions is, on some systems, a strong hint that pthreads support is # correctly enabled -case $host_os in +case $target_os in darwin* | hpux* | linux* | osf* | solaris*) ax_pthread_check_macro="_REENTRANT" ;; @@ -386,7 +391,7 @@ # step ax_pthread_save_ac_link="$ac_link" ax_pthread_sed='s/conftest\.\$ac_ext/conftest.$ac_objext/g' - ax_pthread_link_step=`$as_echo "$ac_link" | sed "$ax_pthread_sed"` + ax_pthread_link_step=`AS_ECHO(["$ac_link"]) | sed "$ax_pthread_sed"` ax_pthread_2step_ac_link="($ac_compile) && (echo ==== >&5) && ($ax_pthread_link_step)" ax_pthread_save_CFLAGS="$CFLAGS" for ax_pthread_try in '' -Qunused-arguments -Wno-unused-command-line-argument unknown; do @@ -445,7 +450,7 @@ AC_CACHE_CHECK([whether more special flags are required for pthreads], [ax_cv_PTHREAD_SPECIAL_FLAGS], [ax_cv_PTHREAD_SPECIAL_FLAGS=no - case $host_os in + case $target_os in solaris*) ax_cv_PTHREAD_SPECIAL_FLAGS="-D_POSIX_PTHREAD_SEMANTICS" ;; @@ -475,25 +480,35 @@ # More AIX lossage: compile with *_r variant if test "x$GCC" != "xyes"; then - case $host_os in + case $target_os in aix*) AS_CASE(["x/$CC"], [x*/c89|x*/c89_128|x*/c99|x*/c99_128|x*/cc|x*/cc128|x*/xlc|x*/xlc_v6|x*/xlc128|x*/xlc128_v6], [#handle absolute path differently from PATH based program lookup AS_CASE(["x$CC"], [x/*], - [AS_IF([AS_EXECUTABLE_P([${CC}_r])],[PTHREAD_CC="${CC}_r"])], - [AC_CHECK_PROGS([PTHREAD_CC],[${CC}_r],[$CC])])]) + [ + AS_IF([AS_EXECUTABLE_P([${CC}_r])],[PTHREAD_CC="${CC}_r"]) + AS_IF([test "x${CXX}" != "x"], [AS_IF([AS_EXECUTABLE_P([${CXX}_r])],[PTHREAD_CXX="${CXX}_r"])]) + ], + [ + AC_CHECK_PROGS([PTHREAD_CC],[${CC}_r],[$CC]) + AS_IF([test "x${CXX}" != "x"], [AC_CHECK_PROGS([PTHREAD_CXX],[${CXX}_r],[$CXX])]) + ] + ) + ]) ;; esac fi fi test -n "$PTHREAD_CC" || PTHREAD_CC="$CC" +test -n "$PTHREAD_CXX" || PTHREAD_CXX="$CXX" AC_SUBST([PTHREAD_LIBS]) AC_SUBST([PTHREAD_CFLAGS]) AC_SUBST([PTHREAD_CC]) +AC_SUBST([PTHREAD_CXX]) # Finally, execute ACTION-IF-FOUND/ACTION-IF-NOT-FOUND: if test "x$ax_pthread_ok" = "xyes"; then diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/tests/Makefile.am new/fplll-5.4.2/tests/Makefile.am --- old/fplll-5.4.1/tests/Makefile.am 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/tests/Makefile.am 2022-05-24 19:36:03.000000000 +0200 @@ -31,10 +31,11 @@ lattices/example_cvp_out3 \ lattices/example_cvp_out4 \ lattices/example_cvp_out5 \ + lattices/example_list_cvp_in_lattice \ lattices/grammatrix_dimension4 \ lattices/grammatrix_dimension4_out \ lattices/grammatrix_dimension7 \ - lattices/grammatrix_dimension7_out + lattices/grammatrix_dimension7_out # include TOPBUILDIR for fplll_config.h AM_CPPFLAGS = -I$(TOPSRCDIR) -I$(TOPSRCDIR)/fplll -I$(TOPBUILDDIR) -DTESTDATADIR=\"$(TOPSRCDIR)/\" diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/tests/lattices/example_list_cvp_in_lattice new/fplll-5.4.2/tests/lattices/example_list_cvp_in_lattice --- old/fplll-5.4.1/tests/lattices/example_list_cvp_in_lattice 1970-01-01 01:00:00.000000000 +0100 +++ new/fplll-5.4.2/tests/lattices/example_list_cvp_in_lattice 2022-05-24 19:36:03.000000000 +0200 @@ -0,0 +1,24 @@ +[[8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] +[4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] +[4 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] +[4 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] +[4 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] +[4 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] +[4 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] +[2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] +[4 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] +[4 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0] +[4 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0] +[2 2 2 2 0 0 0 0 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0] +[4 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0] +[2 2 0 0 2 2 0 0 2 2 0 0 2 2 0 0 0 0 0 0 0 0 0 0] +[2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 0 0 0 0 0 0 0 0] +[2 0 0 2 2 0 0 2 2 0 0 2 2 0 0 2 0 0 0 0 0 0 0 0] +[4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0] +[2 0 2 0 2 0 0 2 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0] +[2 0 0 2 2 2 0 0 2 0 2 0 0 0 0 0 2 0 2 0 0 0 0 0] +[2 2 0 0 2 0 2 0 2 0 0 2 0 0 0 0 2 0 0 2 0 0 0 0] +[0 2 2 2 2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0] +[0 0 0 0 0 0 0 0 2 2 0 0 2 2 0 0 2 2 0 0 2 2 0 0] +[0 0 0 0 0 0 0 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0] +[-3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]] diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/tests/test_enum.cpp new/fplll-5.4.2/tests/test_enum.cpp --- old/fplll-5.4.1/tests/test_enum.cpp 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/tests/test_enum.cpp 2022-05-24 19:36:03.000000000 +0200 @@ -15,6 +15,7 @@ #include <cstring> #include <fplll/fplll.h> +#include <test_utils.h> using namespace fplll; @@ -44,6 +45,133 @@ } } +/** + @brief Test if list_CVP via enumeration function returns the correct amount of vectors + @return +*/ + +template <class FT> int test_list_cvp() +{ + ZZ_mat<mpz_t> u; + int status = 0; + ZZ_mat<mpz_t> A; + status |= read_file(A, TESTDATADIR "tests/lattices/example_list_cvp_in_lattice"); + + status |= lll_reduction(A); + if (status != RED_SUCCESS) + { + cerr << "LLL reduction failed: " << get_red_status_str(status) << endl; + return status; + } + + // Search for up to 999999 vectors, up to radius 32.5 around the origin + // the right answer is 196561 + FP_NR<FT> rad = 32.5; + FP_NR<FT> half_rad = 16.5; + const unsigned int right_answer = 196561; + + // Tests with two targets: 0, and something very close to 0. + + // HOLE: Not sure how to set that up + size_t d = A.get_rows(); + if (d != 24) + { + cerr << "Expected a lattice of dimension 24, got : " << d << endl; + return 1; + } + + ZZ_mat<mpz_t> empty_mat; + MatGSO<Z_NR<mpz_t>, FP_NR<FT>> gso(A, empty_mat, empty_mat, GSO_INT_GRAM); + + { + gso.update_gso(); + FastEvaluator<FP_NR<FT>> evaluator(999999); + Enumeration<Z_NR<mpz_t>, FP_NR<FT>> enum_obj(gso, evaluator); + + std::vector<FP_NR<FT>> target(d, 0.0); + enum_obj.enumerate(0, d, rad, 0, target); + if (evaluator.size() != right_answer) + { + cerr << "list CVP failed (center at 0), expected 196561 solutions, got : " << evaluator.size() + << endl; + return 1; + } + // cerr << "list CVP (at 0) PASSED : " << evaluator.size() << endl; + } + + { + gso.update_gso(); + FastEvaluator<FP_NR<FT>> evaluator(999999); + Enumeration<Z_NR<mpz_t>, FP_NR<FT>> enum_obj(gso, evaluator); + + std::vector<FP_NR<FT>> target(d, 0.0001); + enum_obj.enumerate(0, d, rad, 0, target); + if (evaluator.size() != right_answer) + { + cerr << "list CVP failed (center near 0), expected 196561 solutions, got : " + << evaluator.size() << endl; + return 1; + } + // cerr << "list CVP (near 0) PASSED : " << evaluator.size() << endl; + } + + for (size_t rep = 0; rep < 24; ++rep) + { + FastEvaluator<FP_NR<FT>> evaluator(999999); + Enumeration<Z_NR<mpz_t>, FP_NR<FT>> enum_obj(gso, evaluator); + + std::vector<FP_NR<FT>> can_target(d, 0.0); + + // Generate a point in the half lattice + for (size_t i = 0; i < d; ++i) + { + size_t c = (i == rep || rand() % 2); // make sure at least one of them is non-zero + // std::cerr << c; + if (!c) + continue; + for (size_t j = 0; j < d; ++j) + { + can_target[j] += 0.5 * A[i][j].get_d(); + } + } + + std::vector<FP_NR<FT>> target(d, 0.0); + // Convert it to GSO basis + for (size_t i = 0; i < d; ++i) + { + for (size_t j = 0; j < d; ++j) + { + target[i] += A[i][j].get_d() * can_target[j]; + } + + for (size_t j = 0; j < i; ++j) + { + FP_NR<FT> mu_ij; + gso.get_mu(mu_ij, i, j); + target[i] -= target[j] * mu_ij; + } + } + for (size_t i = 0; i < d; ++i) + { + FP_NR<FT> r_ii; + gso.get_r(r_ii, i, i); + target[i] /= r_ii; + } + + enum_obj.enumerate(0, d, half_rad, 0, target); + + if (evaluator.size() != 2 && evaluator.size() != 48) + { + cerr << "list CVP failed (halfway), expected 2 or 48 solutions, got : " << evaluator.size() + << endl; + return 1; + } + // cerr << "list CVP failed (halfway) PASSED : " << evaluator.size() << endl; + } + + return 0; +} + bool callback_firstf(size_t n, enumf *new_sol_coord, void *ctx) { if (new_sol_coord[0] == static_cast<double *>(ctx)[0]) @@ -92,7 +220,7 @@ int status = 0; status |= test_enum<double>(30); status |= test_callback_enum<double>(40); - + status |= test_list_cvp<double>(); if (status == 0) { std::cerr << "All tests passed." << std::endl; diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' --exclude Makefile.in --exclude configure --exclude config.guess --exclude '*.pot' --exclude mkinstalldirs --exclude aclocal.m4 --exclude config.sub --exclude depcomp --exclude install-sh --exclude ltmain.sh old/fplll-5.4.1/tests/test_svp.cpp new/fplll-5.4.2/tests/test_svp.cpp --- old/fplll-5.4.1/tests/test_svp.cpp 2021-05-14 18:32:12.000000000 +0200 +++ new/fplll-5.4.2/tests/test_svp.cpp 2022-05-24 19:36:03.000000000 +0200 @@ -32,6 +32,17 @@ DSVP_REDUCE }; +double inline norm(const vector<Z_NR<mpz_t>> &v) +{ + Z_NR<mpz_t> norm, tmp; + for (size_t i = 0; i < v.size(); i++) + { + tmp.mul(v[i], v[i]); + norm.add(norm, tmp); + } + return sqrt(norm.get_d()); +} + /** @brief Test if SVP function returns vector with right norm. @@ -45,7 +56,7 @@ vector<Z_NR<mpz_t>> sol_coord; // In the LLL-reduced basis vector<Z_NR<mpz_t>> sol_coord2; // In the initial basis vector<Z_NR<mpz_t>> solution; - ZZ_mat<mpz_t> u; + ZZ_mat<mpz_t> u(A.get_rows(), A.get_rows()); int status = lll_reduction(A, u, LLL_DEF_DELTA, LLL_DEF_ETA, LM_WRAPPER, FT_DEFAULT, 0, LLL_DEFAULT); @@ -252,6 +263,39 @@ return 0; } +/** + @brief test that proved is no worse than fast. + + @param d large dimension of initial lattice + @param d2 enumeration dimension + + */ + +int test_svp_proved_vs_fast(size_t d, size_t d2) +{ + ZZ_mat<mpz_t> A(d, d); + A.gen_qary_withq(d / 2, 65537); + + int r = lll_reduction(A); + ZZ_mat<mpz_t> B(d2, d); // so that LLL doesn't just solve it + vector<Z_NR<mpz_t>> sol_coord_proved, sol_coord_fast; + vector<Z_NR<mpz_t>> solution_proved, solution_fast; + + for (size_t i = 0; i < d2; i++) + { + for (int j = 0; j < A.get_cols(); j++) + B[i][j] = A[i][j]; + } + + r |= shortest_vector(B, sol_coord_proved, SVPM_PROVED); + r |= shortest_vector(B, sol_coord_fast, SVPM_FAST); + + vector_matrix_product(solution_proved, sol_coord_proved, B); + vector_matrix_product(solution_fast, sol_coord_fast, B); + r |= (norm(solution_fast) < norm(solution_proved)); + return r; +} + int test_rank_defect() { ZZ_mat<mpz_t> A = ZZ_mat<mpz_t>(4, 4); @@ -321,6 +365,8 @@ int main() { + RandGen::init_with_seed(0); + int status = 0; status |= test_filename<mpz_t>(TESTDATADIR "/tests/lattices/example_svp_in", TESTDATADIR "/tests/lattices/example_svp_out"); @@ -330,6 +376,7 @@ TESTDATADIR "/tests/lattices/example_dsvp_out", DSVP_REDUCE); status |= test_rank_defect(); + status |= test_svp_proved_vs_fast(100, 30); if (status == 0) {
