OpenCoverage

make-prime-list.c

Absolute File Name:

/home/opencoverage/opencoverage/guest-scripts/coreutils/src/src/make-prime-list.c

Source code

Switch to Preprocessed file

Line Source Count

1 /* Factoring of uintmax_t numbers. Generation of needed tables. -

2 -

3 Contributed to the GNU project by Torbjörn Granlund and Niels Möller -

4 Contains code from GNU MP. -

5 -

7 -

8 This program is free software; you can redistribute it and/or modify it under -

9 the terms of the GNU General Public License as published by the Free Software -

10 Foundation; either version 3 of the License, or (at your option) any later -

11 version. -

12 -

13 This program is distributed in the hope that it will be useful, but WITHOUT ANY -

14 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A -

15 PARTICULAR PURPOSE. See the GNU General Public License for more details. -

16 -

17 You should have received a copy of the GNU General Public License along with -

18 this program. If not, see https://www.gnu.org/licenses/. */ -

19 -

20 #include <config.h> -

21 -

22 #include <limits.h> -

23 #include <stdint.h> -

24 #include <inttypes.h> -

25 #include <stdio.h> -

26 #include <string.h> -

27 #include <stdlib.h> -

28 #include <errno.h> -

29 -

30 /* Deactivate config.h's "rpl_"-prefixed definitions of these symbols. */ -

31 #undef fclose -

32 #undef malloc -

33 #undef strerror -

34 -

35 /* An unsigned type that is no narrower than 32 bits and no narrower -

36 than unsigned int. It's best to make it as wide as possible. -

37 For GCC 4.6 and later, use a heuristic to guess whether unsigned -

38 __int128 works on your platform. If this heuristic does not work -

39 for you, please report a bug; in the meantime compile with, e.g., -

40 -Dwide_uint='unsigned __int128' to override the heuristic. */ -

41 #ifndef wide_uint -

42 # if 4 < __GNUC__ + (6 <= __GNUC_MINOR__) && ULONG_MAX >> 31 >> 31 >> 1 != 0 -

43 typedef unsigned __int128 wide_uint; -

44 # else -

45 typedef uintmax_t wide_uint; -

46 # endif -

47 #endif -

48 -

49 struct prime -

50 { -

51 unsigned p; -

52 wide_uint pinv; /* Inverse mod b = 2^{bitsize of wide_uint} */ -

53 wide_uint lim; /* floor ((wide_uint) -1 / p) */ -

54 }; -

55 -

56 static wide_uint _GL_ATTRIBUTE_CONST -

57 binvert (wide_uint a) -

58 { -

59 wide_uint x = 0xf5397db1 >> (4*((a/2) & 0x7)); -

60 for (;;) -

61 { -

62 wide_uint y = 2*x - x*x*a; -

if (y == x)

y == x	Description
TRUE	evaluated 668 times by 1 test Evaluated by: make-prime-list
FALSE	evaluated 3293 times by 1 test Evaluated by: make-prime-list

668-3293

return x;

executed 668 times by 1 test: return x;

Executed by:

make-prime-list

668

65 x = y; -

}

executed 3293 times by 1 test: end of block

Executed by:

make-prime-list

3293

}

never executed: end of block

68 -

69 static void -

70 process_prime (struct prime *info, unsigned p) -

71 { -

72 wide_uint max = -1; -

73 info->p = p; -

74 info->pinv = binvert (p); -

75 info->lim = max / p; -

}

executed 668 times by 1 test: end of block

Executed by:

make-prime-list

668

77 -

78 static void -

79 print_wide_uint (wide_uint n, int nesting, unsigned wide_uint_bits) -

80 { -

81 /* Number of bits per integer literal. 8 is too many, because -

82 uintmax_t is 32 bits on some machines so we cannot shift by 32 bits. -

83 So use 7. */ -

84 int hex_digits_per_literal = 7; -

85 int bits_per_literal = hex_digits_per_literal * 4; -

86 -

87 unsigned remainder = n & ((1 << bits_per_literal) - 1); -

88 -

if (n != remainder)

n != remainder	Description
TRUE	evaluated 2672 times by 1 test Evaluated by: make-prime-list
FALSE	evaluated 668 times by 1 test Evaluated by: make-prime-list

668-2672

90 { -

91 int needs_parentheses = n >> bits_per_literal >> bits_per_literal != 0; -

if (needs_parentheses)

needs_parentheses	Description
TRUE	evaluated 2004 times by 1 test Evaluated by: make-prime-list
FALSE	evaluated 668 times by 1 test Evaluated by: make-prime-list

668-2004

printf ("(");

executed 2004 times by 1 test: printf ("(");

Executed by:

make-prime-list

2004

94 print_wide_uint (n >> bits_per_literal, nesting + 1, wide_uint_bits); -

if (needs_parentheses)

needs_parentheses	Description
TRUE	evaluated 2004 times by 1 test Evaluated by: make-prime-list
FALSE	evaluated 668 times by 1 test Evaluated by: make-prime-list

668-2004

printf (")\n%*s", nesting + 3, "");

executed 2004 times by 1 test: printf (")\n%*s", nesting + 3, "");

Executed by:

make-prime-list

2004

97 printf (" << %d | ", bits_per_literal); -

}

executed 2672 times by 1 test: end of block

Executed by:

make-prime-list

2672

else if (nesting)

nesting	Description
TRUE	evaluated 668 times by 1 test Evaluated by: make-prime-list
FALSE	never evaluated

0-668

100 { -

101 printf ("(uintmax_t) "); -

102 hex_digits_per_literal -

103 = ((wide_uint_bits - 1) % bits_per_literal) % 4 + 1; -

104

}

executed 668 times by 1 test: end of block

Executed by:

make-prime-list

668

105 -

106 printf ("0x%0*xU", hex_digits_per_literal, remainder); -

107

}

executed 3340 times by 1 test: end of block

Executed by:

make-prime-list

3340

108 -

109 static void -

110 output_primes (const struct prime *primes, unsigned nprimes) -

111 { -

112 unsigned i; -

113 unsigned p; -

114 int is_prime; -

115 -

116 /* Compute wide_uint_bits by repeated shifting, rather than by -

117 multiplying sizeof by CHAR_BIT, as this works even if the -

118 wide_uint representation has holes. */ -

119 unsigned wide_uint_bits = 0; -

120 wide_uint mask = -1; -

121

for (wide_uint_bits = 0; mask; wide_uint_bits++)

mask	Description
TRUE	evaluated 128 times by 1 test Evaluated by: make-prime-list
FALSE	evaluated 1 time by 1 test Evaluated by: make-prime-list

1-128

122

mask >>= 1;

executed 128 times by 1 test: mask >>= 1;

Executed by:

make-prime-list

128

123 -

124 puts ("/* Generated file -- DO NOT EDIT */\n"); -

125 printf ("#define WIDE_UINT_BITS %u\n", wide_uint_bits); -

126 -

127

for (i = 0, p = 2; i < nprimes; i++)

i < nprimes	Description
TRUE	evaluated 668 times by 1 test Evaluated by: make-prime-list
FALSE	evaluated 1 time by 1 test Evaluated by: make-prime-list

1-668

128 { -

129

unsigned int d8 = i + 8 < nprimes ? primes[i + 8].p - primes[i].p : 0xff;

i + 8 < nprimes	Description
TRUE	evaluated 660 times by 1 test Evaluated by: make-prime-list
FALSE	evaluated 8 times by 1 test Evaluated by: make-prime-list

8-660

130

if (255 < d8) /* this happens at 668221 */

255 < d8	Description
TRUE	never evaluated
FALSE	evaluated 668 times by 1 test Evaluated by: make-prime-list

0-668

131

abort ();

never executed: abort ();

132 printf ("P (%u, %u,\n (", primes[i].p - p, d8); -

133 print_wide_uint (primes[i].pinv, 0, wide_uint_bits); -

134 printf ("),\n UINTMAX_MAX / %u)\n", primes[i].p); -

135 p = primes[i].p; -

136

}

executed 668 times by 1 test: end of block

Executed by:

make-prime-list

668

137 -

138 printf ("\n#undef FIRST_OMITTED_PRIME\n"); -

139 -

140 /* Find next prime */ -

141 do -

142 { -

143 p += 2; -

144

for (i = 0, is_prime = 1; is_prime; i++)

is_prime	Description
TRUE	evaluated 20 times by 1 test Evaluated by: make-prime-list
FALSE	never evaluated

0-20

145 { -

146

if (primes[i].p * primes[i].p > p)

primes[i].p * primes[i].p > p	Description
TRUE	evaluated 1 time by 1 test Evaluated by: make-prime-list
FALSE	evaluated 19 times by 1 test Evaluated by: make-prime-list

1-19

147

break;

executed 1 time by 1 test: break;

Executed by:

make-prime-list

148

if (p * primes[i].pinv <= primes[i].lim)

p * primes[i].... primes[i].lim	Description
TRUE	evaluated 1 time by 1 test Evaluated by: make-prime-list
FALSE	evaluated 18 times by 1 test Evaluated by: make-prime-list

1-18

149 { -

150 is_prime = 0; -

151

break;

executed 1 time by 1 test: break;

Executed by:

make-prime-list

152 } -

153

}

executed 18 times by 1 test: end of block

Executed by:

make-prime-list

154

}

executed 2 times by 1 test: end of block

Executed by:

make-prime-list

155

while (!is_prime);

!is_prime	Description
TRUE	evaluated 1 time by 1 test Evaluated by: make-prime-list
FALSE	evaluated 1 time by 1 test Evaluated by: make-prime-list

156 -

157 printf ("#define FIRST_OMITTED_PRIME %u\n", p); -

158

}

executed 1 time by 1 test: end of block

Executed by:

make-prime-list

159 -

160 static void * -

161 xalloc (size_t s) -

162 { -

163 void *p = malloc (s); -

164

if (p)

p	Description
TRUE	evaluated 2 times by 1 test Evaluated by: make-prime-list
FALSE	never evaluated

0-2

165

return p;

executed 2 times by 1 test: return p;

Executed by:

make-prime-list

166 -

167 fprintf (stderr, "Virtual memory exhausted.\n"); -

168

exit (EXIT_FAILURE);

never executed: exit ( 1 );

169 } -

170 -

171 int -

172 main (int argc, char **argv) -

173 { -

174 int limit; -

175 -

176 char *sieve; -

177 size_t size, i; -

178 -

179 struct prime *prime_list; -

180 unsigned nprimes; -

181 -

182

if (argc != 2)

argc != 2	Description
TRUE	never evaluated
FALSE	evaluated 1 time by 1 test Evaluated by: make-prime-list

0-1

183 { -

184 fprintf (stderr, "Usage: %s LIMIT\n" -

185 "Produces a list of odd primes <= LIMIT\n", argv[0]); -

186

return EXIT_FAILURE;

never executed: return 1 ;

187 } -

188 limit = atoi (argv[1]); -

189

if (limit < 3)

limit < 3	Description
TRUE	never evaluated
FALSE	evaluated 1 time by 1 test Evaluated by: make-prime-list

0-1

190

return EXIT_SUCCESS;

never executed: return 0 ;

191 -

192 /* Make limit odd */ -

193

if ( !(limit & 1))

!(limit & 1)	Description
TRUE	evaluated 1 time by 1 test Evaluated by: make-prime-list
FALSE	never evaluated

0-1

194

limit--;

executed 1 time by 1 test: limit--;

Executed by:

make-prime-list

195 -

196 size = (limit-1)/2; -

197 /* sieve[i] represents 3+2*i */ -

198 sieve = xalloc (size); -

199 memset (sieve, 1, size); -

200 -

201 prime_list = xalloc (size * sizeof (*prime_list)); -

202 nprimes = 0; -

203 -

204

for (i = 0; i < size;)

i < size	Description
TRUE	evaluated 668 times by 1 test Evaluated by: make-prime-list
FALSE	evaluated 1 time by 1 test Evaluated by: make-prime-list

1-668

205 { -

206 unsigned p = 3+2*i; -

207 unsigned j; -

208 -

209 process_prime (&prime_list[nprimes++], p); -

210 -

211

for (j = (p*p - 3)/2; j < size; j+= p)

j < size	Description
TRUE	evaluated 2797 times by 1 test Evaluated by: make-prime-list
FALSE	evaluated 668 times by 1 test Evaluated by: make-prime-list

668-2797

212

sieve[j] = 0;

executed 2797 times by 1 test: sieve[j] = 0;

Executed by:

make-prime-list

2797

213 -

214

while (++i < size && sieve[i] == 0)

++i < size	Description
TRUE	evaluated 2498 times by 1 test Evaluated by: make-prime-list
FALSE	evaluated 1 time by 1 test Evaluated by: make-prime-list

sieve[i] == 0	Description
TRUE	evaluated 1831 times by 1 test Evaluated by: make-prime-list
FALSE	evaluated 667 times by 1 test Evaluated by: make-prime-list

1-2498

215

;

executed 1831 times by 1 test: ;

Executed by:

make-prime-list

1831

216

}

executed 668 times by 1 test: end of block

Executed by:

make-prime-list

668

217 -

218 output_primes (prime_list, nprimes); -

219 -

220 free (sieve); -

221 free (prime_list); -

222 -

223

if (ferror (stdout) + fclose (stdout))

ferror ( stdou...ose ( stdout )	Description
TRUE	never evaluated
FALSE	evaluated 1 time by 1 test Evaluated by: make-prime-list

0-1

224 { -

225 fprintf (stderr, "write error: %s\n", strerror (errno)); -

226

return EXIT_FAILURE;

never executed: return 1 ;

227 } -

228 -

229

return EXIT_SUCCESS;

executed 1 time by 1 test: return 0 ;

Executed by:

make-prime-list

230 } -

Source code

Switch to Preprocessed file

Generated by Squish Coco 4.1.2