lib/Math/Factor/XS.xs

filter: Statementstmt 100% 80 / 80 Branchbran 86.0% 74 / 86 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 92.7% 154 / 166 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« blib/lib/Math/Factor/XS.pm ↑ Summary
1 #include "EXTERN.h"
2 #include "perl.h"
3 #include "XSUB.h"
4  
5 #define NEED_newRV_noinc_GLOBAL
6 #include "ppport.h"
7  
8 /* double_ulong_max_plus_1 is ULONG_MAX+1. This is usually a power of 2 and
9 thus can be represented exactly in a double. The calculation avoids
10 round-off if ulong is bigger than the mantissa of a double. */
11 static const double double_ulong_max_plus_1
12 = ((double) ((ULONG_MAX >> 1)+1)) * 2.0;
13  
14 #define COUNT_OR_PUSH(prime) \
15 do { \
16 if (ix) { \
17 count++; /* count_prime_factors() */ \
18 } else { \
19 mXPUSHu(prime); /* prime_factors() */ \
20 } \
21 } while (0)
22  
23 MODULE = Math::Factor::XS PACKAGE = Math::Factor::XS
24  
25 void
26 factors (number)
27 unsigned long number
28 PROTOTYPE: $
29 INIT:
30 unsigned long i, square_root;
31 AV *factors;
32 PPCODE:
33 /* range check */
34 {
35 10 double d = SvNV(ST(0));
36 10 ▶ if (! (d >= 0 && d < double_ulong_max_plus_1)) {
Branch: 2 branches
BranchTrueFalseTotal
if (! (d >= 0 && d < double_ulong_max_plus_1)) { 7 3 10
if (! (d >= 0 && d < double_ulong_max_plus_1)) { 2 5 7
37 5 croak ("Cannot factors() on %g", d);
38 }
39 }
40  
41 5 factors = newAV ();
42 5 square_root = sqrt (number);
43  
44 192 ▶ for (i = 2; i <= number; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 2; i <= number; i++) 192 0 192
45 {
46 192 ▶ if (i > square_root)
Branch: 1 branch
BranchTrueFalseTotal
if (i > square_root) 5 187 192
47 5 break;
48 187 ▶ if (number % i == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (number % i == 0) 15 172 187
49 {
50 15 unsigned long quot = number / i;
51 15 ▶ mXPUSHu(i);
Branch: 1 branch
BranchTrueFalseTotal
mXPUSHu(i); 0 15 15
52 15 ▶ if (quot > i)
Branch: 1 branch
BranchTrueFalseTotal
if (quot > i) 14 1 15
53 14 av_push (factors, newSVuv(quot));
54 }
55 }
56  
57 5 i = av_len(factors) + 1;
58 5 ▶ EXTEND (SP, i);
Branch: 1 branch
BranchTrueFalseTotal
EXTEND (SP, i); 0 5 5
59 19 ▶ while (i--)
Branch: 1 branch
BranchTrueFalseTotal
while (i--) 14 5 19
60 14 PUSHs (sv_2mortal(av_pop(factors)));
61  
62 5 SvREFCNT_dec (factors);
63  
64 void
65 xs_matches (number, factors_aref, ...)
66 unsigned long number
67 SV *factors_aref
68 PROTOTYPE: $\@
69 INIT:
70 AV *factors;
71 3 unsigned long *prev_base = NULL;
72 3 unsigned int b, c, p = 0;
73 3 unsigned int top = items - 1;
74 3 bool Skip_multiples = FALSE;
75 3 bool skip = FALSE;
76 PPCODE:
77 3 factors = (AV*)SvRV (factors_aref);
78  
79 3 ▶ if (av_len (factors) == -1)
Branch: 1 branch
BranchTrueFalseTotal
if (av_len (factors) == -1) 1 2 3
80 1 XSRETURN_EMPTY;
81  
82 2 ▶ if (SvROK (ST(top)) && SvTYPE (SvRV(ST(top))) == SVt_PVHV)
Branch: 2 branches
BranchTrueFalseTotal
if (SvROK (ST(top)) && SvTYPE (SvRV(ST(top))) == SVt_PVHV) 2 0 2
if (SvROK (ST(top)) && SvTYPE (SvRV(ST(top))) == SVt_PVHV) 1 1 2
83 {
84 1 const char *opt = "skip_multiples";
85 1 unsigned int len = strlen (opt);
86 1 HV *opts = (HV*)SvRV (ST(top));
87  
88 1 ▶ if (hv_exists (opts, opt, len))
Branch: 1 branch
BranchTrueFalseTotal
if (hv_exists (opts, opt, len)) 1 0 1
89 {
90 1 SV **val = hv_fetch (opts, opt, len, 0);
91 1 ▶ if (val)
Branch: 1 branch
BranchTrueFalseTotal
if (val) 1 0 1
92 1 Skip_multiples = SvTRUE (*val);
93 }
94 }
95  
96 30 ▶ for (b = 0; b <= av_len (factors); b++)
Branch: 1 branch
BranchTrueFalseTotal
for (b = 0; b <= av_len (factors); b++) 28 2 30
97 {
98 28 unsigned long base = SvUV (*av_fetch(factors, b, 0));
99 420 ▶ for (c = 0; c <= av_len (factors); c++)
Branch: 1 branch
BranchTrueFalseTotal
for (c = 0; c <= av_len (factors); c++) 392 28 420
100 {
101 392 unsigned long cmp = SvUV (*av_fetch(factors, c, 0));
102 392 ▶ if ((cmp >= base) && (base * cmp == number))
Branch: 2 branches
BranchTrueFalseTotal
if ((cmp >= base) && (base * cmp == number)) 210 182 392
if ((cmp >= base) && (base * cmp == number)) 14 196 210
103 {
104 14 ▶ if (Skip_multiples)
Branch: 1 branch
BranchTrueFalseTotal
if (Skip_multiples) 7 7 14
105 {
106 unsigned int i;
107 7 skip = FALSE;
108 25 ▶ for (i = 0; i < p; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < p; i++) 18 7 25
109 18 ▶ if (base % prev_base[i] == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (base % prev_base[i] == 0) 6 12 18
110 6 skip = TRUE;
111 }
112 14 ▶ if (!skip)
Branch: 1 branch
BranchTrueFalseTotal
if (!skip) 11 3 14
113 {
114 11 AV *match = newAV ();
115 11 av_push (match, newSVuv(base));
116 11 av_push (match, newSVuv(cmp));
117  
118 11 ▶ EXTEND (SP, 1);
Branch: 1 branch
BranchTrueFalseTotal
EXTEND (SP, 1); 0 11 11
119 11 PUSHs (sv_2mortal(newRV_noinc((SV*)match)));
120  
121 11 ▶ if (Skip_multiples)
Branch: 1 branch
BranchTrueFalseTotal
if (Skip_multiples) 4 7 11
122 {
123 4 ▶ if (!prev_base)
Branch: 1 branch
BranchTrueFalseTotal
if (!prev_base) 1 3 4
124 1 Newx (prev_base, 1, unsigned long);
125 else
126 3 Renew (prev_base, p + 1, unsigned long);
127 4 prev_base[p++] = base;
128 }
129 }
130 }
131 }
132 }
133  
134 2 Safefree (prev_base);
135  
136 # prime_factors() and count_prime_factors() done in a combined XSUB so
137 # as to use the share the factorizing loop and to save a few bytes of
138 # object code by sharing the boilerplate sub entry and exit.
139 #
140 # No PROTOTYPE since might add a "distinct" option.
141 #
142 void
143 prime_factors (number)
144 unsigned long number
145 ALIAS:
146 count_prime_factors = 1
147 INIT:
148 unsigned long i, limit;
149 unsigned incr;
150 2040 unsigned long count = 0;
151 PPCODE:
152 /* range check */
153 {
154 2040 double d = SvNV(ST(0));
155 2040 ▶ if (! (d >= 0 && d < double_ulong_max_plus_1)) {
Branch: 2 branches
BranchTrueFalseTotal
if (! (d >= 0 && d < double_ulong_max_plus_1)) { 2037 3 2040
if (! (d >= 0 && d < double_ulong_max_plus_1)) { 2 2035 2037
156 5 croak ("Cannot prime_factors() on %g", d);
157 }
158 }
159  
160 2035 ▶ if (number > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (number > 0) { 2033 2 2035
161 /* or perhaps __builtin_ctz() in new enough gcc, but usually there
162 won't be many twos */
163 4062 ▶ while (! (number & 1)) {
Branch: 1 branch
BranchTrueFalseTotal
while (! (number & 1)) { 2029 2033 4062
164 2029 ▶ COUNT_OR_PUSH(2);
Branch: 2 branches
BranchTrueFalseTotal
COUNT_OR_PUSH(2); 15 2014 2029
COUNT_OR_PUSH(2); 0 2014 2014
165 2029 number >>= 1;
166 }
167  
168 3054 ▶ while (! (number % 3)) {
Branch: 1 branch
BranchTrueFalseTotal
while (! (number % 3)) { 1021 2033 3054
169 1021 ▶ COUNT_OR_PUSH(3);
Branch: 2 branches
BranchTrueFalseTotal
COUNT_OR_PUSH(3); 11 1010 1021
COUNT_OR_PUSH(3); 0 1010 1010
170 1021 number /= 3;
171 }
172  
173 /* "incr" is alternately 2 and 4, giving i==5mod6 and i==1mod6, so
174 skip multiples of 2 and multiples of 3 */
175 2033 limit = sqrt (number);
176 2033 incr = 2;
177 15683 ▶ for (i = 5; i <= limit; i += incr, incr ^= 6)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 5; i <= limit; i += incr, incr ^= 6) 13650 2033 15683
178 {
179 13650 ▶ if (number % i == 0)
Branch: 1 branch
BranchTrueFalseTotal
if (number % i == 0) 943 12707 13650
180 {
181 do {
182 1137 number /= i;
183 1137 ▶ COUNT_OR_PUSH(i);
Branch: 2 branches
BranchTrueFalseTotal
COUNT_OR_PUSH(i); 2 1135 1137
COUNT_OR_PUSH(i); 0 1135 1135
184 1137 ▶ } while (number % i == 0);
Branch: 1 branch
BranchTrueFalseTotal
} while (number % i == 0); 194 943 1137
185 943 limit = sqrt (number); /* new smaller limit */
186 }
187 }
188 }
189  
190 2035 ▶ if (ix) {
Branch: 1 branch
BranchTrueFalseTotal
if (ix) { 17 2018 2035
191 /* count_prime_factors() */
192 17 count += (number > 1); /* possible prime left in number */
193 17 ▶ mXPUSHu(count);
Branch: 1 branch
BranchTrueFalseTotal
mXPUSHu(count); 0 17 17
194 } else {
195 /* prime_factors() */
196 2018 ▶ if (number > 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (number > 1) { 1858 160 2018
197 1858 ▶ mXPUSHu(number); /* possible prime left in number */
Branch: 1 branch
BranchTrueFalseTotal
mXPUSHu(number); /* possible prime left in number */ 0 1858 1858
198 }
199 }
« blib/lib/Math/Factor/XS.pm ↑ Summary