4 #include "base/cl_sysdep.h"
7 #include "integer/cl_I.h"
12 #include "base/digitseq/cl_DS.h"
13 #include "integer/conv/cl_I_cached_power.h"
17 static const cl_I digits_to_I_base2 (const char * MSBptr, uintC len, uintD base)
19 // base is a power of two: write the digits from least significant
20 // to most significant into the result NUDS. Result needs
21 // 1+ceiling(len*log(base)/(intDsize*log(2))) or some more digits.
23 var uintD* erg_MSDptr;
25 var uintD* erg_LSDptr;
26 var int b = (base==2 ? 1 : base==4 ? 2 : base==8 ? 3 : base==16 ? 4 : /*base==32*/ 5);
27 num_stack_alloc(1+(len*b)/intDsize,,erg_LSDptr=);
28 erg_MSDptr = erg_LSDptr; erg_len = 0;
29 var uintD d = 0; // resulting digit
30 var int ch_where = 0; // position of ch inside d
31 var uintC min_len = 0; // first non-zero digit
32 while (min_len < len && *(const uintB *)(MSBptr+min_len) == '0') {
35 while (len > min_len) {
36 var uintB ch = *(const uintB *)(MSBptr+len-1); // next character
37 if (ch!='.') { // skip decimal point
38 // Compute value of ch ('0'-'9','A'-'Z','a'-'z'):
40 if (ch > '9'-'0') { // not a digit?
42 if (ch > 'Z'-'A'+10) {// not an uppercase letter?
43 ch = ch+'A'-'a'; // must be lowercase!
46 d = d | (uintD)ch<<ch_where;
47 ch_where = ch_where+b;
48 if (ch_where >= intDsize) {
49 // d is ready to be written into the NUDS:
50 lsprefnext(erg_MSDptr) = d;
51 ch_where = ch_where-intDsize;
52 d = (uintD)ch >> (b-ch_where); // carry
58 if (d != 0) { // is there anything left over?
59 lsprefnext(erg_MSDptr) = d;
62 return NUDS_to_I(erg_MSDptr,erg_len);
65 static const cl_I digits_to_I_baseN (const char * MSBptr, uintC len, uintD base)
67 // base is not a power of two: Add digits one by one. Result needs
68 // 1+ceiling(len*log(base)/(intDsize*log(2))) or some more digits.
70 var uintD* erg_MSDptr;
72 var uintD* erg_LSDptr;
73 var uintC need = 1+floor(len,intDsize*256); // > len/(intDsize*256) >=0
74 switch (base) { // multiply need with ceiling(256*log(base)/log(2)):
75 case 2: need = 256*need; break;
76 case 3: need = 406*need; break;
77 case 4: need = 512*need; break;
78 case 5: need = 595*need; break;
79 case 6: need = 662*need; break;
80 case 7: need = 719*need; break;
81 case 8: need = 768*need; break;
82 case 9: need = 812*need; break;
83 case 10: need = 851*need; break;
84 case 11: need = 886*need; break;
85 case 12: need = 918*need; break;
86 case 13: need = 948*need; break;
87 case 14: need = 975*need; break;
88 case 15: need = 1001*need; break;
89 case 16: need = 1024*need; break;
90 case 17: need = 1047*need; break;
91 case 18: need = 1068*need; break;
92 case 19: need = 1088*need; break;
93 case 20: need = 1107*need; break;
94 case 21: need = 1125*need; break;
95 case 22: need = 1142*need; break;
96 case 23: need = 1159*need; break;
97 case 24: need = 1174*need; break;
98 case 25: need = 1189*need; break;
99 case 26: need = 1204*need; break;
100 case 27: need = 1218*need; break;
101 case 28: need = 1231*need; break;
102 case 29: need = 1244*need; break;
103 case 30: need = 1257*need; break;
104 case 31: need = 1269*need; break;
105 case 32: need = 1280*need; break;
106 case 33: need = 1292*need; break;
107 case 34: need = 1303*need; break;
108 case 35: need = 1314*need; break;
109 case 36: need = 1324*need; break;
112 // Now we have need >= len*log(base)/(intDsize*log(2)).
114 // Add digits one by one:
115 num_stack_alloc(need,,erg_LSDptr=);
116 // erg_MSDptr/erg_len/erg_LSDptr is a NUDS, erg_len < need.
117 erg_MSDptr = erg_LSDptr; erg_len = 0;
119 var uintD newdigit = 0;
121 var uintD factor = 1;
122 while (chx < power_table[base-2].k && len > 0) {
123 var uintB ch = *(const uintB *)MSBptr; MSBptr++; // next character
124 // Compute value of ('0'-'9','A'-'Z','a'-'z'):
126 if (ch > '9'-'0') { // not a digit?
128 if (ch > 'Z'-'A'+10) {// not an uppercase letter?
129 ch = ch+'A'-'a'; // must be lowercase!
132 factor = factor*base;
133 newdigit = base*newdigit+ch;
137 var uintD carry = mulusmall_loop_lsp(factor,erg_LSDptr,erg_len,newdigit);
139 // need to extend NUDS:
140 lsprefnext(erg_MSDptr) = carry;
144 return NUDS_to_I(erg_MSDptr,erg_len);
147 static const cl_I digits_to_I_divconq (const char * MSBptr, uintC len, uintD base)
149 // This is quite insensitive to the breakeven point.
150 // On a 1GHz Athlon I get approximately:
151 // base 3: breakeven around 25000
152 // base 10: breakeven around 8000
153 // base 36: breakeven around 2000
154 if (len>80000/base) {
155 // Divide-and-conquer:
156 // Find largest i such that B = base^(k*2^i) satisfies B <= X.
157 var const cached_power_table_entry * p;
158 var uintC len_B = power_table[base-2].k;
159 for (uintC i = 0; ; i++) {
160 p = cached_power(base, i);
165 return digits_to_I_divconq(MSBptr,len-len_B,base) * p->base_pow
166 + digits_to_I_divconq(MSBptr+len-len_B,len_B,base);
168 return digits_to_I_baseN(MSBptr, len, base);
172 const cl_I digits_to_I (const char * MSBptr, uintC len, uintD base)
174 if ((base & (base-1)) == 0) {
175 return digits_to_I_base2(MSBptr, len, base);
177 // digits_to_I_divconq cannot handle decimal points, so remove it here
179 const uintD * digits_copy;
180 num_stack_alloc(len,,digits_copy=);
181 char * copy_ptr = (char *)digits_copy;
183 for (uintC i = 0; i < len; ++i) {
184 const char ch = MSBptr[i];
185 if (ch != '.') { // skip decimal point
190 return digits_to_I_divconq((const char*)digits_copy, n, base);