| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i = 2; i <= number; i++) |
192 |
0 |
192 |
|
| 45 |
|
| { |
| 46 |
192 |
▶ | if (i > square_root) |
Branch: 1 branch
| Branch | True | False | Total |
| if (i > square_root) |
5 |
187 |
192 |
|
| 47 |
5 |
| break; |
| 48 |
187 |
▶ | if (number % i == 0) |
Branch: 1 branch
| Branch | True | False | Total |
| if (number % i == 0) |
15 |
172 |
187 |
|
| 49 |
|
| { |
| 50 |
15 |
| unsigned long quot = number / i; |
| 51 |
15 |
▶ | mXPUSHu(i); |
Branch: 1 branch
| Branch | True | False | Total |
| mXPUSHu(i); |
0 |
15 |
15 |
|
| 52 |
15 |
▶ | if (quot > i) |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| EXTEND (SP, i); |
0 |
5 |
5 |
|
| 59 |
19 |
▶ | while (i--) |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i = 0; i < p; i++) |
18 |
7 |
25 |
|
| 109 |
18 |
▶ | if (base % prev_base[i] == 0) |
Branch: 1 branch
| Branch | True | False | Total |
| if (base % prev_base[i] == 0) |
6 |
12 |
18 |
|
| 110 |
6 |
| skip = TRUE; |
| 111 |
|
| } |
| 112 |
14 |
▶ | if (!skip) |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| EXTEND (SP, 1); |
0 |
11 |
11 |
|
| 119 |
11 |
| PUSHs (sv_2mortal(newRV_noinc((SV*)match))); |
| 120 |
|
| |
| 121 |
11 |
▶ | if (Skip_multiples) |
Branch: 1 branch
| Branch | True | False | Total |
| if (Skip_multiples) |
4 |
7 |
11 |
|
| 122 |
|
| { |
| 123 |
4 |
▶ | if (!prev_base) |
Branch: 1 branch
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| while (! (number & 1)) { |
2029 |
2033 |
4062 |
|
| 164 |
2029 |
▶ | COUNT_OR_PUSH(2); |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| while (! (number % 3)) { |
1021 |
2033 |
3054 |
|
| 169 |
1021 |
▶ | COUNT_OR_PUSH(3); |
Branch: 2 branches
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| for (i = 5; i <= limit; i += incr, incr ^= 6) |
13650 |
2033 |
15683 |
|
| 178 |
|
| { |
| 179 |
13650 |
▶ | if (number % i == 0) |
Branch: 1 branch
| Branch | True | False | Total |
| if (number % i == 0) |
943 |
12707 |
13650 |
|
| 180 |
|
| { |
| 181 |
|
| do { |
| 182 |
1137 |
| number /= i; |
| 183 |
1137 |
▶ | COUNT_OR_PUSH(i); |
Branch: 2 branches
| Branch | True | False | Total |
| COUNT_OR_PUSH(i); |
2 |
1135 |
1137 |
| COUNT_OR_PUSH(i); |
0 |
1135 |
1135 |
|
| 184 |
1137 |
▶ | } while (number % i == 0); |
Branch: 1 branch
| Branch | True | False | Total |
| } 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| mXPUSHu(count); |
0 |
17 |
17 |
|
| 194 |
|
| } else { |
| 195 |
|
| /* prime_factors() */ |
| 196 |
2018 |
▶ | if (number > 1) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (number > 1) { |
1858 |
160 |
2018 |
|
| 197 |
1858 |
▶ | mXPUSHu(number); /* possible prime left in number */ |
Branch: 1 branch
| Branch | True | False | Total |
| mXPUSHu(number); /* possible prime left in number */ |
0 |
1858 |
1858 |
|
| 198 |
|
| } |
| 199 |
|
| } |