File: rp-private.h

package info (click to toggle)
ratpoints 1:2.1.3-1
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, jessie, jessie-kfreebsd, sid, stretch
  • size: 572 kB
  • ctags: 230
  • sloc: ansic: 4,201; makefile: 155
file content (159 lines) | stat: -rw-r--r-- 5,992 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
/***********************************************************************
 * ratpoints-2.1.2                                                     *
 *  - A program to find rational points on hyperelliptic curves        *
 * Copyright (C) 2008, 2009  Michael Stoll                             *
 *                                                                     *
 * This program 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 2 of   *
 * the License, or (at your option) any later version.                 *
 *                                                                     *
 * This program 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.                        *
 *                                                                     *
 * You should have received a copy of version 2 of the GNU General     *
 * Public License along with this program.                             *
 * If not, see <http://www.gnu.org/licenses/>.                         *
 ***********************************************************************/

/***********************************************************************
 * rp-private.h                                                        *
 *                                                                     *
 * Header file with information local to the ratpoints code            *
 *                                                                     *
 * Michael Stoll, Apr 14, 2009                                         *
 ***********************************************************************/

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>

#define LONG_LENGTH (8*sizeof(long))
   /* number of bits in an unsigned long */
#define LONG_SHIFT ((LONG_LENGTH == 16) ? 4 : \
                    (LONG_LENGTH == 32) ? 5 : \
		    (LONG_LENGTH == 64) ? 6 : 0)
#define LONG_MASK (~(-1L<<LONG_SHIFT))

/* Check if SSE instructions can be used.
   We assume that one SSE word of 128 bit is two long's,
   so check that a long is 64 bit = 8 byte.
*/
#ifndef __SSE2__
#undef USE_SSE
#endif
#if __WORDSIZE != 64
#undef USE_SSE
#endif

#include "ratpoints.h"

#define FLOOR(a,b) (((a) < 0) ? -(1 + (-(a)-1) / (b)) : (a) / (b))
#define CEIL(a,b) (((a) <= 0) ? -(-(a) / (b)) : 1 + ((a)-1) / (b))

/* Some Macros for working with SSE registers */
#ifdef USE_SSE

#include <emmintrin.h>

#define AND(a,b) ((ratpoints_bit_array)__builtin_ia32_andps((__v4sf)(a), (__v4sf)(b)))
#define EXT0(a) ((unsigned long)__builtin_ia32_vec_ext_v2di((__v2di)(a), 0))
#define EXT1(a) ((unsigned long)__builtin_ia32_vec_ext_v2di((__v2di)(a), 1))
#define TEST(a) (EXT0(a) || EXT1(a))
#define RBA(a,b) ((__v2di){(a), (b)})

/* Use SSE 128 bit registers for the bit arrays */
typedef __v2di ratpoints_bit_array;
#define zero (RBA(0LL, 0LL))

#define RBA_LENGTH (128)
   /* number of bits in a ratpoints_bit_array */
#define RBA_SHIFT ((RBA_LENGTH == 128) ? 7 : 0)
#define RBA_MASK (~(-1L<<RBA_SHIFT))

#else
/* Use unsigned long for the bit arrays */
typedef unsigned long ratpoints_bit_array;
#define zero ((ratpoints_bit_array)0UL)

#define RBA_LENGTH LONG_LENGTH
   /* number of bits in a ratpoints_bit_array */
#define RBA_SHIFT LONG_SHIFT
#define RBA_MASK LONG_MASK

#endif

#define WIDTH (int)(LONG_LENGTH/4)

/* set up data related to the set of primes considered */
#ifndef RATPOINTS_MAX_BITS_IN_PRIME
# define RATPOINTS_MAX_BITS_IN_PRIME 7
#endif

#if (RATPOINTS_MAX_BITS_IN_PRIME == 10)
# define RATPOINTS_NUM_PRIMES 171
# define RATPOINTS_MAX_PRIME 1021
# define RATPOINTS_MAX_PRIME_EVEN 1024

#elif (RATPOINTS_MAX_BITS_IN_PRIME == 9)
# define RATPOINTS_NUM_PRIMES 96
# define RATPOINTS_MAX_PRIME 509
# define RATPOINTS_MAX_PRIME_EVEN 512

#elif (RATPOINTS_MAX_BITS_IN_PRIME == 8)
# define RATPOINTS_NUM_PRIMES 53
# define RATPOINTS_MAX_PRIME 251
# define RATPOINTS_MAX_PRIME_EVEN 256

#elif (RATPOINTS_MAX_BITS_IN_PRIME == 7)
# define RATPOINTS_NUM_PRIMES 30
# define RATPOINTS_MAX_PRIME 127
# define RATPOINTS_MAX_PRIME_EVEN 128

#elif (RATPOINTS_MAX_BITS_IN_PRIME == 6)
# define RATPOINTS_NUM_PRIMES 17
# define RATPOINTS_MAX_PRIME 61
# define RATPOINTS_MAX_PRIME_EVEN 64

#elif (RATPOINTS_MAX_BITS_IN_PRIME == 5)
# define RATPOINTS_NUM_PRIMES 10
# define RATPOINTS_MAX_PRIME 31
# define RATPOINTS_MAX_PRIME_EVEN 32

#else
# define RATPOINTS_MAX_BITS_IN_PRIME 7
# define RATPOINTS_NUM_PRIMES 30
# define RATPOINTS_MAX_PRIME 127
# define RATPOINTS_MAX_PRIME_EVEN 128

#endif
/* so that RATPOINTS_MAX_PRIME < RATPOINTS_MAX_PRIME_EVEN
                               = 2^RATPOINTS_MAX_BITS_IN_PRIME */

typedef struct { long p; long offset; ratpoints_bit_array *ptr; } sieve_spec;

typedef enum { num_all, num_even, num_odd, num_none } bit_selection;

typedef ratpoints_bit_array* (*ratpoints_init_fun)(void*, long, void*);

typedef struct 
        { ratpoints_init_fun init; long p; int *is_f_square; 
          const long *inverses;
          long offset; ratpoints_bit_array* sieve[RATPOINTS_MAX_PRIME]; }
        ratpoints_sieve_entry;

/* The following function is provided in find_points.c : */
long _ratpoints_check_point(long a, long b, ratpoints_args *args, int *quit,
                 int process(long, long, const mpz_t, void*, int*), void *info);

/* The following function is provided in sift.c : */
long _ratpoints_sift0(long b, long w_low, long w_high, 
           ratpoints_args *args, bit_selection which_bits,
           ratpoints_bit_array *survivors, sieve_spec *sieves, int *quit, 
           int process(long, long, const mpz_t, void*, int*), void *info);

/* The following function is provided in sturm.c : */
long _ratpoints_compute_sturm(ratpoints_args*);