1 /* Copyright (C) 2005-2008 Damien Stehle. 2 Copyright (C) 2007 David Cade. 3 Copyright (C) 2011 Xavier Pujol. 4 Copyright (C) 2013 Damien Stehle 5 6 This file is part of fplll. fplll is free software: you 7 can redistribute it and/or modify it under the terms of the GNU Lesser 8 General Public License as published by the Free Software Foundation, 9 either version 2.1 of the License, or (at your option) any later version. 10 11 fplll is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU Lesser General Public License for more details. 15 16 You should have received a copy of the GNU Lesser General Public License 17 along with fplll. If not, see <http://www.gnu.org/licenses/>. */ 18 19 #ifndef FPLLL_DEFS_H 20 #define FPLLL_DEFS_H 21 22 #ifndef __CYGWIN__ 23 #define FPLLL_WITH_LONG_DOUBLE 24 #endif 25 26 #define FPLLL_WITH_DPE 27 #define FPLLL_WITH_ZDOUBLE 28 #define FPLLL_WITH_ZLONG 29 #define FPLLL_WITH_GETRUSAGE 30 31 #include <algorithm> 32 #include <climits> 33 #include <cmath> 34 #include <cstddef> 35 #include <cstdio> 36 #include <cstdlib> 37 #include <cstring> 38 #include <ctime> 39 #include <fstream> 40 #include <iostream> 41 #include <limits> 42 #include <sstream> 43 #include <stdexcept> 44 #include <string> 45 46 #ifdef FPLLL_WITH_GETRUSAGE 47 #include <sys/resource.h> 48 #include <sys/time.h> 49 #include <unistd.h> 50 #endif 51 52 #include "fplll_config.h" 53 #ifdef HAVE_LIBMPIR 54 #include <mpir.h> 55 #endif 56 #ifdef HAVE_LIBGMP 57 #include <gmp.h> 58 #endif 59 #include <mpfr.h> 60 #ifdef FPLLL_WITH_DPE 61 #include "nr/dpe.h" 62 #endif 63 64 #if defined(__sun) || defined(__CYGWIN__) 65 #include <ieeefp.h> 66 extern "C" long double ldexpl(long double x, int exp); 67 #ifndef NAN 68 #define NAN __builtin_nanf("") 69 #endif 70 #endif 71 72 #define FPLLL_INFO(x) \ 73 { \ 74 cerr << x << endl; \ 75 } 76 #define FPLLL_ABORT(x) \ 77 { \ 78 cerr << "fplll: " << x << endl; \ 79 abort(); \ 80 } 81 #define FPLLL_CHECK(x, y) \ 82 { \ 83 if (!(x)) \ 84 FPLLL_ABORT(y); \ 85 } 86 87 #ifdef DEBUG 88 #include <cassert> 89 extern int debug_depth; 90 #define FPLLL_TRACE(x) std::cerr << "TRACE: " << std::string(debug_depth * 2, ' ') << x << std::endl 91 struct DebugTracer 92 { DebugTracerDebugTracer93 DebugTracer(const char *f) : f(f) { debug_depth++; } ~DebugTracerDebugTracer94 ~DebugTracer() 95 { 96 debug_depth--; 97 FPLLL_TRACE("</" << f << ">"); 98 } 99 std::string f; 100 }; 101 #define FPLLL_DEBUG_ABORT(x) FPLLL_ABORT(x) 102 #define FPLLL_DEBUG_CHECK(x) assert(x); 103 #define FPLLL_TRACE_IN(x) \ 104 FPLLL_TRACE("<" << __func__ << " " << x << ">"); \ 105 DebugTracer debugTracer(__func__); 106 #define FPLLL_DEBUG_SAFEVECT 107 #else 108 #define FPLLL_DEBUG_ABORT(x) 109 #define FPLLL_DEBUG_CHECK(x) 110 #define FPLLL_TRACE(x) 111 #define FPLLL_TRACE_IN(x) 112 #endif 113 114 #define FPLLL_BEGIN_NAMESPACE \ 115 namespace fplll \ 116 { 117 #define FPLLL_END_NAMESPACE } 118 119 /** \namespace fplll 120 The fplll namespace */ 121 FPLLL_BEGIN_NAMESPACE 122 123 using namespace std; 124 125 /* this trick will not work on 16-bit machines*/ 126 #if (LONG_MAX == 2147483647L) 127 const int CPU_SIZE = 32; 128 const int CPU_SIZE_1 = 30; 129 const double MAX_LONG_FAST = 0x1p30; 130 const long int EXPO_MAX = 30; 131 #else 132 const int CPU_SIZE = 64; 133 const int CPU_SIZE_1 = 53; 134 const double MAX_LONG_FAST = 0x1p53; 135 const long int EXPO_MAX = 53; 136 #endif 137 138 const int MAX_EXP_DOUBLE = 1000; 139 const int PREC_DOUBLE = 53; 140 const int PREC_DD = 106; 141 const int PREC_QD = 212; 142 143 const double LLL_DEF_DELTA = 0.99; 144 const double LLL_DEF_ETA = 0.51; 145 const double LLL_DEF_EPSILON = 0.01; 146 const int SIZE_RED_FAILURE_THRESH = 5; 147 148 // Constraint: 1/2 < eta - theta 149 const double HLLL_DEF_THETA = 0.001; 150 // Constant for the size reduction. 151 const double HLLL_DEF_C = 0.1; 152 153 enum RedStatus 154 { 155 RED_SUCCESS = 0, 156 // Skips value 1 157 RED_GSO_FAILURE = 2, 158 RED_BABAI_FAILURE = 3, 159 RED_LLL_FAILURE = 4, 160 RED_ENUM_FAILURE = 5, 161 RED_BKZ_FAILURE = 6, 162 RED_BKZ_TIME_LIMIT = 7, 163 RED_BKZ_LOOPS_LIMIT = 8, 164 RED_HLLL_FAILURE = 9, 165 RED_HLLL_NORM_FAILURE = 10, 166 RED_HLLL_SR_FAILURE = 11, 167 RED_URL_ERR = 12, 168 RED_STATUS_MAX = 13 169 }; 170 171 const char *const RED_STATUS_STR[RED_STATUS_MAX] = { 172 "success", 173 "", 174 "infinite number in GSO", 175 "infinite loop in babai", 176 "infinite loop in LLL", 177 "error in SVP solver", 178 "error in BKZ", 179 "time limit exceeded in BKZ", 180 "loops limit exceeded in BKZ", 181 "error in HLLL", 182 "increase of the norm", 183 "error in weak size reduction", 184 "Please see https://github.com/fplll/fplll/wiki/fplll-errors-FAQ for more information."}; 185 186 enum LLLMethod 187 { 188 LM_WRAPPER = 0, 189 LM_PROVED = 1, 190 LM_HEURISTIC = 2, 191 LM_FAST = 3 192 }; 193 194 const char *const LLL_METHOD_STR[6] = {"wrapper", "proved", "heuristic", "fast"}; 195 196 // LM_HEURISTIC is not (yet) an option for HLLL and cannot be called from the fplll binary, then 197 // we leave empty the third string. 198 const char *const HLLL_METHOD_STR[4] = {"wrapper", "proved", "", "fast"}; 199 200 enum IntType 201 { 202 ZT_MPZ = 0, 203 ZT_LONG = 1, 204 ZT_DOUBLE = 2 205 }; 206 207 const char *const INT_TYPE_STR[5] = {"mpz", "long", "double"}; 208 209 enum FloatType 210 { 211 FT_DEFAULT = 0, 212 FT_DOUBLE = 1, 213 FT_LONG_DOUBLE = 2, 214 FT_DPE = 3, 215 FT_DD = 4, 216 FT_QD = 5, 217 FT_MPFR = 6 218 }; 219 220 const char *const FLOAT_TYPE_STR[7] = {"", "double", "long double", "dpe", "dd", "qd", "mpfr"}; 221 222 enum LLLFlags 223 { 224 LLL_VERBOSE = 1, 225 LLL_EARLY_RED = 2, 226 LLL_SIEGEL = 4, 227 LLL_DEFAULT = 0 228 }; 229 230 enum SVPMethod 231 { 232 SVPM_FAST = 0, 233 SVPM_PROVED = 2 234 }; 235 236 enum CVPMethod 237 { 238 CVPM_FAST = 0, 239 CVPM_PROVED = 2 240 }; 241 242 enum SVPFlags 243 { 244 SVP_DEFAULT = 0, 245 SVP_VERBOSE = 1, 246 SVP_OVERRIDE_BND = 2, 247 SVP_DUAL = 4 248 }; 249 250 enum CVPFlags 251 { 252 CVP_DEFAULT = SVP_DEFAULT, 253 CVP_VERBOSE = SVP_VERBOSE 254 }; 255 256 const double BKZ_DEF_AUTO_ABORT_SCALE = 1.0; 257 const int BKZ_DEF_AUTO_ABORT_MAX_NO_DEC = 5; 258 const double BKZ_DEF_GH_FACTOR = 1.1; 259 const double BKZ_DEF_MIN_SUCCESS_PROBABILITY = 0.5; 260 const int BKZ_DEF_RERANDOMIZATION_DENSITY = 3; 261 262 enum BKZFlags 263 { 264 BKZ_DEFAULT = 0, 265 BKZ_VERBOSE = 1, 266 BKZ_NO_LLL = 2, 267 BKZ_MAX_LOOPS = 4, 268 BKZ_MAX_TIME = 8, 269 BKZ_BOUNDED_LLL = 0x10, 270 BKZ_AUTO_ABORT = 0x20, 271 BKZ_DUMP_GSO = 0x40, 272 BKZ_GH_BND = 0x80, 273 BKZ_SD_VARIANT = 0x100, 274 BKZ_SLD_RED = 0x200 275 }; 276 277 enum HKZFlags 278 { 279 HKZ_DEFAULT = 0, 280 HKZ_VERBOSE = 1 281 }; 282 283 #ifndef FPLLL_DEFAULT_STRATEGY_PATH 284 #define FPLLL_DEFAULT_STRATEGY_PATH "" 285 #endif 286 287 #ifndef FPLLL_DEFAULT_STRATEGY 288 #define FPLLL_DEFAULT_STRATEGY "" 289 #endif 290 291 enum PrunerMetric 292 { 293 PRUNER_METRIC_PROBABILITY_OF_SHORTEST = 0, 294 PRUNER_METRIC_EXPECTED_SOLUTIONS = 1 295 }; 296 297 enum PrunerFlags 298 { 299 PRUNER_CVP = 300 0x1, // Do not Halve the count of nodes, according to enumeration optimization from symmetry 301 // Descent methods. If several activated, pruner will execute them in the order below. 302 PRUNER_START_FROM_INPUT = 0x2, 303 PRUNER_GRADIENT = 0x4, // Activate the gradient descent 304 PRUNER_NELDER_MEAD = 0x8, 305 // Verbosity 306 PRUNER_VERBOSE = 0x10, 307 // Optimize w.r.t to half of the coefficients (those of even indices) 308 // (by default this is not enabled) 309 PRUNER_HALF = 0x20, 310 // Optimize goal set to single enumeration cost while fixing the probability ~ target. Note that 311 // flags PRUNER_HALF and PRUNER_SINGLE are mutually exclusive. 312 PRUNER_SINGLE = 0x40 313 }; 314 315 #define PRUNER_ZEALOUS (PRUNER_GRADIENT | PRUNER_NELDER_MEAD) 316 317 FPLLL_END_NAMESPACE 318 319 #endif 320