1 /** \ingroup py_c
2 * \file python/mpw-py.c
3 */
4
5 #define _REENTRANT 1 /* XXX config.h collides with pyconfig.h */
6
7 #include "config.h"
8
9 #include "Python.h"
10 #include "longintrepr.h"
11
12 #ifdef __LCLINT__
13 #undef PyObject_HEAD
14 #define PyObject_HEAD int _PyObjectHead;
15 #endif
16
17 #include "beecrypt/python/mpw-py.h"
18 #include "beecrypt/python/rng-py.h"
19
20 #include "debug-py.c"
21
22 #define ABS(_x) ((_x) < 0 ? -(_x) : (_x))
23 #if !defined(MAX)
24 #define MAX(x, y) ((x) < (y) ? (y) : (x))
25 #endif
26 #if !defined(MIN)
27 #define MIN(x, y) ((x) > (y) ? (y) : (x))
28 #endif
29
30 #define MPBITCNT(_s, _d) (MP_WORDS_TO_BITS(_s) - mpmszcnt((_s), (_d)))
31
32 #define BITS_TO_DIGITS(_b) (((_b) + SHIFT - 1)/SHIFT)
33 #define DIGITS_TO_BITS(_d) ((_d) * SHIFT)
34
35 /*@unchecked@*/
36 static int _ie = 0x44332211;
37 /*@unchecked@*/
38 static union _dendian {
39 /*@unused@*/
40 int i;
41 char b[4];
42 } *_endian = (union _dendian *)&_ie;
43 #define IS_BIG_ENDIAN() (_endian->b[0] == '\x44')
44 #define IS_LITTLE_ENDIAN() (_endian->b[0] == '\x11')
45
46 /*@unchecked@*/
47 static int _mpw_debug = 0;
48
49 /*@unchecked@*/ /*@observer@*/
50 static const char *initialiser_name = "";
51
52 /*@unchecked@*/ /*@observer@*/
53 static const struct {
54 /* Number of digits in the conversion base that always fits in an mp_limb_t.
55 For example, for base 10 on a machine where a mp_limb_t has 32 bits this
56 is 9, since 10**9 is the largest number that fits into a mp_limb_t. */
57 int chars_per_limb;
58
59 /* log(2)/log(conversion_base) */
60 double chars_per_bit_exactly;
61
62 /* base**chars_per_limb, i.e. the biggest number that fits a word, built by
63 factors of base. Exception: For 2, 4, 8, etc, big_base is log2(base),
64 i.e. the number of bits used to represent each digit in the base. */
65 unsigned int big_base;
66
67 /* A BITS_PER_MP_LIMB bit approximation to 1/big_base, represented as a
68 fixed-point number. Instead of dividing by big_base an application can
69 choose to multiply by big_base_inverted. */
70 unsigned int big_base_inverted;
71 } mp_bases[257] = {
72 /* 0 */ {0, 0.0, 0, 0},
73 /* 1 */ {0, 1e37, 0, 0},
74 /* 2 */ {32, 1.0000000000000000, 0x1, 0x0},
75 /* 3 */ {20, 0.6309297535714574, 0xcfd41b91, 0x3b563c24},
76 /* 4 */ {16, 0.5000000000000000, 0x2, 0x0},
77 /* 5 */ {13, 0.4306765580733931, 0x48c27395, 0xc25c2684},
78 /* 6 */ {12, 0.3868528072345416, 0x81bf1000, 0xf91bd1b6},
79 /* 7 */ {11, 0.3562071871080222, 0x75db9c97, 0x1607a2cb},
80 /* 8 */ {10, 0.3333333333333333, 0x3, 0x0},
81 /* 9 */ {10, 0.3154648767857287, 0xcfd41b91, 0x3b563c24},
82 /* 10 */ {9, 0.3010299956639812, 0x3b9aca00, 0x12e0be82},
83 /* 11 */ {9, 0.2890648263178878, 0x8c8b6d2b, 0xd24cde04},
84 /* 12 */ {8, 0.2789429456511298, 0x19a10000, 0x3fa39ab5},
85 /* 13 */ {8, 0.2702381544273197, 0x309f1021, 0x50f8ac5f},
86 /* 14 */ {8, 0.2626495350371935, 0x57f6c100, 0x74843b1e},
87 /* 15 */ {8, 0.2559580248098155, 0x98c29b81, 0xad0326c2},
88 /* 16 */ {8, 0.2500000000000000, 0x4, 0x0},
89 /* 17 */ {7, 0.2446505421182260, 0x18754571, 0x4ef0b6bd},
90 /* 18 */ {7, 0.2398124665681314, 0x247dbc80, 0xc0fc48a1},
91 /* 19 */ {7, 0.2354089133666382, 0x3547667b, 0x33838942},
92 /* 20 */ {7, 0.2313782131597592, 0x4c4b4000, 0xad7f29ab},
93 /* 21 */ {7, 0.2276702486969530, 0x6b5a6e1d, 0x313c3d15},
94 /* 22 */ {7, 0.2242438242175754, 0x94ace180, 0xb8cca9e0},
95 /* 23 */ {7, 0.2210647294575037, 0xcaf18367, 0x42ed6de9},
96 /* 24 */ {6, 0.2181042919855316, 0xb640000, 0x67980e0b},
97 /* 25 */ {6, 0.2153382790366965, 0xe8d4a51, 0x19799812},
98 /* 26 */ {6, 0.2127460535533632, 0x1269ae40, 0xbce85396},
99 /* 27 */ {6, 0.2103099178571525, 0x17179149, 0x62c103a9},
100 /* 28 */ {6, 0.2080145976765095, 0x1cb91000, 0x1d353d43},
101 /* 29 */ {6, 0.2058468324604344, 0x23744899, 0xce1decea},
102 /* 30 */ {6, 0.2037950470905062, 0x2b73a840, 0x790fc511},
103 /* 31 */ {6, 0.2018490865820999, 0x34e63b41, 0x35b865a0},
104 /* 32 */ {6, 0.2000000000000000, 0x5, 0x0},
105 /* 33 */ {6, 0.1982398631705605, 0x4cfa3cc1, 0xa9aed1b3},
106 /* 34 */ {6, 0.1965616322328226, 0x5c13d840, 0x63dfc229},
107 /* 35 */ {6, 0.1949590218937863, 0x6d91b519, 0x2b0fee30},
108 /* 36 */ {6, 0.1934264036172708, 0x81bf1000, 0xf91bd1b6},
109 /* 37 */ {6, 0.1919587200065601, 0x98ede0c9, 0xac89c3a9},
110 /* 38 */ {6, 0.1905514124267734, 0xb3773e40, 0x6d2c32fe},
111 /* 39 */ {6, 0.1892003595168700, 0xd1bbc4d1, 0x387907c9},
112 /* 40 */ {6, 0.1879018247091076, 0xf4240000, 0xc6f7a0b},
113 /* 41 */ {5, 0.1866524112389434, 0x6e7d349, 0x28928154},
114 /* 42 */ {5, 0.1854490234153689, 0x7ca30a0, 0x6e8629d},
115 /* 43 */ {5, 0.1842888331487062, 0x8c32bbb, 0xd373dca0},
116 /* 44 */ {5, 0.1831692509136336, 0x9d46c00, 0xa0b17895},
117 /* 45 */ {5, 0.1820879004699383, 0xaffacfd, 0x746811a5},
118 /* 46 */ {5, 0.1810425967800402, 0xc46bee0, 0x4da6500f},
119 /* 47 */ {5, 0.1800313266566926, 0xdab86ef, 0x2ba23582},
120 /* 48 */ {5, 0.1790522317510414, 0xf300000, 0xdb20a88},
121 /* 49 */ {5, 0.1781035935540111, 0x10d63af1, 0xe68d5ce4},
122 /* 50 */ {5, 0.1771838201355579, 0x12a05f20, 0xb7cdfd9d},
123 /* 51 */ {5, 0.1762914343888821, 0x1490aae3, 0x8e583933},
124 /* 52 */ {5, 0.1754250635819545, 0x16a97400, 0x697cc3ea},
125 /* 53 */ {5, 0.1745834300480449, 0x18ed2825, 0x48a5ca6c},
126 /* 54 */ {5, 0.1737653428714400, 0x1b5e4d60, 0x2b52db16},
127 /* 55 */ {5, 0.1729696904450771, 0x1dff8297, 0x111586a6},
128 /* 56 */ {5, 0.1721954337940981, 0x20d38000, 0xf31d2b36},
129 /* 57 */ {5, 0.1714416005739134, 0x23dd1799, 0xc8d76d19},
130 /* 58 */ {5, 0.1707072796637201, 0x271f35a0, 0xa2cb1eb4},
131 /* 59 */ {5, 0.1699916162869140, 0x2a9ce10b, 0x807c3ec3},
132 /* 60 */ {5, 0.1692938075987814, 0x2e593c00, 0x617ec8bf},
133 /* 61 */ {5, 0.1686130986895011, 0x3257844d, 0x45746cbe},
134 /* 62 */ {5, 0.1679487789570419, 0x369b13e0, 0x2c0aa273},
135 /* 63 */ {5, 0.1673001788101741, 0x3b27613f, 0x14f90805},
136 /* 64 */ {5, 0.1666666666666667, 0x6, 0x0},
137 /* 65 */ {5, 0.1660476462159378, 0x4528a141, 0xd9cf0829},
138 /* 66 */ {5, 0.1654425539190583, 0x4aa51420, 0xb6fc4841},
139 /* 67 */ {5, 0.1648508567221603, 0x50794633, 0x973054cb},
140 /* 68 */ {5, 0.1642720499620502, 0x56a94400, 0x7a1dbe4b},
141 /* 69 */ {5, 0.1637056554452156, 0x5d393975, 0x5f7fcd7f},
142 /* 70 */ {5, 0.1631512196835108, 0x642d7260, 0x47196c84},
143 /* 71 */ {5, 0.1626083122716342, 0x6b8a5ae7, 0x30b43635},
144 /* 72 */ {5, 0.1620765243931223, 0x73548000, 0x1c1fa5f6},
145 /* 73 */ {5, 0.1615554674429964, 0x7b908fe9, 0x930634a},
146 /* 74 */ {5, 0.1610447717564444, 0x84435aa0, 0xef7f4a3c},
147 /* 75 */ {5, 0.1605440854340214, 0x8d71d25b, 0xcf5552d2},
148 /* 76 */ {5, 0.1600530732548213, 0x97210c00, 0xb1a47c8e},
149 /* 77 */ {5, 0.1595714156699382, 0xa1563f9d, 0x9634b43e},
150 /* 78 */ {5, 0.1590988078692941, 0xac16c8e0, 0x7cd3817d},
151 /* 79 */ {5, 0.1586349589155960, 0xb768278f, 0x65536761},
152 /* 80 */ {5, 0.1581795909397823, 0xc3500000, 0x4f8b588e},
153 /* 81 */ {5, 0.1577324383928644, 0xcfd41b91, 0x3b563c24},
154 /* 82 */ {5, 0.1572932473495469, 0xdcfa6920, 0x28928154},
155 /* 83 */ {5, 0.1568617748594410, 0xeac8fd83, 0x1721bfb0},
156 /* 84 */ {5, 0.1564377883420715, 0xf9461400, 0x6e8629d},
157 /* 85 */ {4, 0.1560210650222250, 0x31c84b1, 0x491cc17c},
158 /* 86 */ {4, 0.1556113914024939, 0x342ab10, 0x3a11d83b},
159 /* 87 */ {4, 0.1552085627701551, 0x36a2c21, 0x2be074cd},
160 /* 88 */ {4, 0.1548123827357682, 0x3931000, 0x1e7a02e7},
161 /* 89 */ {4, 0.1544226628011101, 0x3bd5ee1, 0x11d10edd},
162 /* 90 */ {4, 0.1540392219542636, 0x3e92110, 0x5d92c68},
163 /* 91 */ {4, 0.1536618862898642, 0x4165ef1, 0xf50dbfb2},
164 /* 92 */ {4, 0.1532904886526781, 0x4452100, 0xdf9f1316},
165 /* 93 */ {4, 0.1529248683028321, 0x4756fd1, 0xcb52a684},
166 /* 94 */ {4, 0.1525648706011593, 0x4a75410, 0xb8163e97},
167 /* 95 */ {4, 0.1522103467132434, 0x4dad681, 0xa5d8f269},
168 /* 96 */ {4, 0.1518611533308632, 0x5100000, 0x948b0fcd},
169 /* 97 */ {4, 0.1515171524096389, 0x546d981, 0x841e0215},
170 /* 98 */ {4, 0.1511782109217764, 0x57f6c10, 0x74843b1e},
171 /* 99 */ {4, 0.1508442006228941, 0x5b9c0d1, 0x65b11e6e},
172 /* 100 */ {4, 0.1505149978319906, 0x5f5e100, 0x5798ee23},
173 /* 101 */ {4, 0.1501904832236880, 0x633d5f1, 0x4a30b99b},
174 /* 102 */ {4, 0.1498705416319474, 0x673a910, 0x3d6e4d94},
175 /* 103 */ {4, 0.1495550618645152, 0x6b563e1, 0x314825b0},
176 /* 104 */ {4, 0.1492439365274121, 0x6f91000, 0x25b55f2e},
177 /* 105 */ {4, 0.1489370618588283, 0x73eb721, 0x1aadaccb},
178 /* 106 */ {4, 0.1486343375718350, 0x7866310, 0x10294ba2},
179 /* 107 */ {4, 0.1483356667053617, 0x7d01db1, 0x620f8f6},
180 /* 108 */ {4, 0.1480409554829326, 0x81bf100, 0xf91bd1b6},
181 /* 109 */ {4, 0.1477501131786861, 0x869e711, 0xe6d37b2a},
182 /* 110 */ {4, 0.1474630519902391, 0x8ba0a10, 0xd55cff6e},
183 /* 111 */ {4, 0.1471796869179852, 0x90c6441, 0xc4ad2db2},
184 /* 112 */ {4, 0.1468999356504447, 0x9610000, 0xb4b985cf},
185 /* 113 */ {4, 0.1466237184553111, 0x9b7e7c1, 0xa5782bef},
186 /* 114 */ {4, 0.1463509580758620, 0xa112610, 0x96dfdd2a},
187 /* 115 */ {4, 0.1460815796324244, 0xa6cc591, 0x88e7e509},
188 /* 116 */ {4, 0.1458155105286054, 0xacad100, 0x7b8813d3},
189 /* 117 */ {4, 0.1455526803620167, 0xb2b5331, 0x6eb8b595},
190 /* 118 */ {4, 0.1452930208392429, 0xb8e5710, 0x627289db},
191 /* 119 */ {4, 0.1450364656948130, 0xbf3e7a1, 0x56aebc07},
192 /* 120 */ {4, 0.1447829506139581, 0xc5c1000, 0x4b66dc33},
193 /* 121 */ {4, 0.1445324131589439, 0xcc6db61, 0x4094d8a3},
194 /* 122 */ {4, 0.1442847926987864, 0xd345510, 0x3632f7a5},
195 /* 123 */ {4, 0.1440400303421672, 0xda48871, 0x2c3bd1f0},
196 /* 124 */ {4, 0.1437980688733776, 0xe178100, 0x22aa4d5f},
197 /* 125 */ {4, 0.1435588526911310, 0xe8d4a51, 0x19799812},
198 /* 126 */ {4, 0.1433223277500932, 0xf05f010, 0x10a523e5},
199 /* 127 */ {4, 0.1430884415049874, 0xf817e01, 0x828a237},
200 /* 128 */ {4, 0.1428571428571428, 0x7, 0x0},
201 /* 129 */ {4, 0.1426283821033600, 0x10818201, 0xf04ec452},
202 /* 130 */ {4, 0.1424021108869747, 0x11061010, 0xe136444a},
203 /* 131 */ {4, 0.1421782821510107, 0x118db651, 0xd2af9589},
204 /* 132 */ {4, 0.1419568500933153, 0x12188100, 0xc4b42a83},
205 /* 133 */ {4, 0.1417377701235801, 0x12a67c71, 0xb73dccf5},
206 /* 134 */ {4, 0.1415209988221527, 0x1337b510, 0xaa4698c5},
207 /* 135 */ {4, 0.1413064939005528, 0x13cc3761, 0x9dc8f729},
208 /* 136 */ {4, 0.1410942141636095, 0x14641000, 0x91bf9a30},
209 /* 137 */ {4, 0.1408841194731412, 0x14ff4ba1, 0x86257887},
210 /* 138 */ {4, 0.1406761707131039, 0x159df710, 0x7af5c98c},
211 /* 139 */ {4, 0.1404703297561400, 0x16401f31, 0x702c01a0},
212 /* 140 */ {4, 0.1402665594314587, 0x16e5d100, 0x65c3ceb1},
213 /* 141 */ {4, 0.1400648234939879, 0x178f1991, 0x5bb91502},
214 /* 142 */ {4, 0.1398650865947379, 0x183c0610, 0x5207ec23},
215 /* 143 */ {4, 0.1396673142523192, 0x18eca3c1, 0x48ac9c19},
216 /* 144 */ {4, 0.1394714728255649, 0x19a10000, 0x3fa39ab5},
217 /* 145 */ {4, 0.1392775294872041, 0x1a592841, 0x36e98912},
218 /* 146 */ {4, 0.1390854521985406, 0x1b152a10, 0x2e7b3140},
219 /* 147 */ {4, 0.1388952096850913, 0x1bd51311, 0x2655840b},
220 /* 148 */ {4, 0.1387067714131417, 0x1c98f100, 0x1e7596ea},
221 /* 149 */ {4, 0.1385201075671774, 0x1d60d1b1, 0x16d8a20d},
222 /* 150 */ {4, 0.1383351890281539, 0x1e2cc310, 0xf7bfe87},
223 /* 151 */ {4, 0.1381519873525671, 0x1efcd321, 0x85d2492},
224 /* 152 */ {4, 0.1379704747522905, 0x1fd11000, 0x179a9f4},
225 /* 153 */ {4, 0.1377906240751463, 0x20a987e1, 0xf59e80eb},
226 /* 154 */ {4, 0.1376124087861776, 0x21864910, 0xe8b768db},
227 /* 155 */ {4, 0.1374358029495937, 0x226761f1, 0xdc39d6d5},
228 /* 156 */ {4, 0.1372607812113589, 0x234ce100, 0xd021c5d1},
229 /* 157 */ {4, 0.1370873187823978, 0x2436d4d1, 0xc46b5e37},
230 /* 158 */ {4, 0.1369153914223921, 0x25254c10, 0xb912f39c},
231 /* 159 */ {4, 0.1367449754241439, 0x26185581, 0xae150294},
232 /* 160 */ {4, 0.1365760475984821, 0x27100000, 0xa36e2eb1},
233 /* 161 */ {4, 0.1364085852596902, 0x280c5a81, 0x991b4094},
234 /* 162 */ {4, 0.1362425662114337, 0x290d7410, 0x8f19241e},
235 /* 163 */ {4, 0.1360779687331669, 0x2a135bd1, 0x8564e6b7},
236 /* 164 */ {4, 0.1359147715670014, 0x2b1e2100, 0x7bfbb5b4},
237 /* 165 */ {4, 0.1357529539050150, 0x2c2dd2f1, 0x72dadcc8},
238 /* 166 */ {4, 0.1355924953769864, 0x2d428110, 0x69ffc498},
239 /* 167 */ {4, 0.1354333760385373, 0x2e5c3ae1, 0x6167f154},
240 /* 168 */ {4, 0.1352755763596663, 0x2f7b1000, 0x5911016e},
241 /* 169 */ {4, 0.1351190772136599, 0x309f1021, 0x50f8ac5f},
242 /* 170 */ {4, 0.1349638598663645, 0x31c84b10, 0x491cc17c},
243 /* 171 */ {4, 0.1348099059658080, 0x32f6d0b1, 0x417b26d8},
244 /* 172 */ {4, 0.1346571975321549, 0x342ab100, 0x3a11d83b},
245 /* 173 */ {4, 0.1345057169479844, 0x3563fc11, 0x32dee622},
246 /* 174 */ {4, 0.1343554469488779, 0x36a2c210, 0x2be074cd},
247 /* 175 */ {4, 0.1342063706143054, 0x37e71341, 0x2514bb58},
248 /* 176 */ {4, 0.1340584713587979, 0x39310000, 0x1e7a02e7},
249 /* 177 */ {4, 0.1339117329233981, 0x3a8098c1, 0x180ea5d0},
250 /* 178 */ {4, 0.1337661393673756, 0x3bd5ee10, 0x11d10edd},
251 /* 179 */ {4, 0.1336216750601996, 0x3d311091, 0xbbfb88e},
252 /* 180 */ {4, 0.1334783246737591, 0x3e921100, 0x5d92c68},
253 /* 181 */ {4, 0.1333360731748201, 0x3ff90031, 0x1c024c},
254 /* 182 */ {4, 0.1331949058177136, 0x4165ef10, 0xf50dbfb2},
255 /* 183 */ {4, 0.1330548081372441, 0x42d8eea1, 0xea30efa3},
256 /* 184 */ {4, 0.1329157659418126, 0x44521000, 0xdf9f1316},
257 /* 185 */ {4, 0.1327777653067443, 0x45d16461, 0xd555c0c9},
258 /* 186 */ {4, 0.1326407925678156, 0x4756fd10, 0xcb52a684},
259 /* 187 */ {4, 0.1325048343149731, 0x48e2eb71, 0xc193881f},
260 /* 188 */ {4, 0.1323698773862368, 0x4a754100, 0xb8163e97},
261 /* 189 */ {4, 0.1322359088617821, 0x4c0e0f51, 0xaed8b724},
262 /* 190 */ {4, 0.1321029160581950, 0x4dad6810, 0xa5d8f269},
263 /* 191 */ {4, 0.1319708865228925, 0x4f535d01, 0x9d15039d},
264 /* 192 */ {4, 0.1318398080287045, 0x51000000, 0x948b0fcd},
265 /* 193 */ {4, 0.1317096685686114, 0x52b36301, 0x8c394d1d},
266 /* 194 */ {4, 0.1315804563506306, 0x546d9810, 0x841e0215},
267 /* 195 */ {4, 0.1314521597928493, 0x562eb151, 0x7c3784f8},
268 /* 196 */ {4, 0.1313247675185968, 0x57f6c100, 0x74843b1e},
269 /* 197 */ {4, 0.1311982683517524, 0x59c5d971, 0x6d02985d},
270 /* 198 */ {4, 0.1310726513121843, 0x5b9c0d10, 0x65b11e6e},
271 /* 199 */ {4, 0.1309479056113158, 0x5d796e61, 0x5e8e5c64},
272 /* 200 */ {4, 0.1308240206478128, 0x5f5e1000, 0x5798ee23},
273 /* 201 */ {4, 0.1307009860033912, 0x614a04a1, 0x50cf7bde},
274 /* 202 */ {4, 0.1305787914387386, 0x633d5f10, 0x4a30b99b},
275 /* 203 */ {4, 0.1304574268895465, 0x65383231, 0x43bb66bd},
276 /* 204 */ {4, 0.1303368824626505, 0x673a9100, 0x3d6e4d94},
277 /* 205 */ {4, 0.1302171484322746, 0x69448e91, 0x374842ee},
278 /* 206 */ {4, 0.1300982152363760, 0x6b563e10, 0x314825b0},
279 /* 207 */ {4, 0.1299800734730872, 0x6d6fb2c1, 0x2b6cde75},
280 /* 208 */ {4, 0.1298627138972530, 0x6f910000, 0x25b55f2e},
281 /* 209 */ {4, 0.1297461274170591, 0x71ba3941, 0x2020a2c5},
282 /* 210 */ {4, 0.1296303050907487, 0x73eb7210, 0x1aadaccb},
283 /* 211 */ {4, 0.1295152381234257, 0x7624be11, 0x155b891f},
284 /* 212 */ {4, 0.1294009178639407, 0x78663100, 0x10294ba2},
285 /* 213 */ {4, 0.1292873358018581, 0x7aafdeb1, 0xb160fe9},
286 /* 214 */ {4, 0.1291744835645007, 0x7d01db10, 0x620f8f6},
287 /* 215 */ {4, 0.1290623529140715, 0x7f5c3a21, 0x14930ef},
288 /* 216 */ {4, 0.1289509357448472, 0x81bf1000, 0xf91bd1b6},
289 /* 217 */ {4, 0.1288402240804449, 0x842a70e1, 0xefdcb0c7},
290 /* 218 */ {4, 0.1287302100711566, 0x869e7110, 0xe6d37b2a},
291 /* 219 */ {4, 0.1286208859913518, 0x891b24f1, 0xddfeb94a},
292 /* 220 */ {4, 0.1285122442369443, 0x8ba0a100, 0xd55cff6e},
293 /* 221 */ {4, 0.1284042773229231, 0x8e2ef9d1, 0xcceced50},
294 /* 222 */ {4, 0.1282969778809442, 0x90c64410, 0xc4ad2db2},
295 /* 223 */ {4, 0.1281903386569819, 0x93669481, 0xbc9c75f9},
296 /* 224 */ {4, 0.1280843525090381, 0x96100000, 0xb4b985cf},
297 /* 225 */ {4, 0.1279790124049077, 0x98c29b81, 0xad0326c2},
298 /* 226 */ {4, 0.1278743114199984, 0x9b7e7c10, 0xa5782bef},
299 /* 227 */ {4, 0.1277702427352035, 0x9e43b6d1, 0x9e1771a9},
300 /* 228 */ {4, 0.1276667996348261, 0xa1126100, 0x96dfdd2a},
301 /* 229 */ {4, 0.1275639755045533, 0xa3ea8ff1, 0x8fd05c41},
302 /* 230 */ {4, 0.1274617638294791, 0xa6cc5910, 0x88e7e509},
303 /* 231 */ {4, 0.1273601581921740, 0xa9b7d1e1, 0x8225759d},
304 /* 232 */ {4, 0.1272591522708010, 0xacad1000, 0x7b8813d3},
305 /* 233 */ {4, 0.1271587398372755, 0xafac2921, 0x750eccf9},
306 /* 234 */ {4, 0.1270589147554692, 0xb2b53310, 0x6eb8b595},
307 /* 235 */ {4, 0.1269596709794558, 0xb5c843b1, 0x6884e923},
308 /* 236 */ {4, 0.1268610025517973, 0xb8e57100, 0x627289db},
309 /* 237 */ {4, 0.1267629036018709, 0xbc0cd111, 0x5c80c07b},
310 /* 238 */ {4, 0.1266653683442337, 0xbf3e7a10, 0x56aebc07},
311 /* 239 */ {4, 0.1265683910770258, 0xc27a8241, 0x50fbb19b},
312 /* 240 */ {4, 0.1264719661804097, 0xc5c10000, 0x4b66dc33},
313 /* 241 */ {4, 0.1263760881150453, 0xc91209c1, 0x45ef7c7c},
314 /* 242 */ {4, 0.1262807514205999, 0xcc6db610, 0x4094d8a3},
315 /* 243 */ {4, 0.1261859507142915, 0xcfd41b91, 0x3b563c24},
316 /* 244 */ {4, 0.1260916806894653, 0xd3455100, 0x3632f7a5},
317 /* 245 */ {4, 0.1259979361142023, 0xd6c16d31, 0x312a60c3},
318 /* 246 */ {4, 0.1259047118299582, 0xda488710, 0x2c3bd1f0},
319 /* 247 */ {4, 0.1258120027502338, 0xdddab5a1, 0x2766aa45},
320 /* 248 */ {4, 0.1257198038592741, 0xe1781000, 0x22aa4d5f},
321 /* 249 */ {4, 0.1256281102107963, 0xe520ad61, 0x1e06233c},
322 /* 250 */ {4, 0.1255369169267456, 0xe8d4a510, 0x19799812},
323 /* 251 */ {4, 0.1254462191960791, 0xec940e71, 0x15041c33},
324 /* 252 */ {4, 0.1253560122735751, 0xf05f0100, 0x10a523e5},
325 /* 253 */ {4, 0.1252662914786691, 0xf4359451, 0xc5c2749},
326 /* 254 */ {4, 0.1251770521943144, 0xf817e010, 0x828a237},
327 /* 255 */ {4, 0.1250882898658681, 0xfc05fc01, 0x40a1423},
328 /* 256 */ {4, 0.1250000000000000, 0x8, 0x0},
329 };
330
prtmpw(const char * msg,mpwObject * x)331 static void prtmpw(const char * msg, mpwObject * x)
332 /*@global stderr, fileSystem @*/
333 /*@modifies stderr, fileSystem @*/
334 {
335 fprintf(stderr, "%5.5s %p[%d]:\t", msg, MPW_DATA(x), MPW_SIZE(x)), mpfprintln(stderr, MPW_SIZE(x), MPW_DATA(x));
336 }
337
338 static size_t
mpsizeinbase(size_t xsize,mpw * xdata,size_t base)339 mpsizeinbase(size_t xsize, mpw* xdata, size_t base)
340 /*@*/
341 {
342 size_t nbits;
343 size_t res;
344
345 if (xsize == 0)
346 return 1;
347
348 /* XXX assumes positive integer. */
349 nbits = MP_WORDS_TO_BITS(xsize) - mpmszcnt(xsize, xdata);
350 if ((base & (base-1)) == 0) { /* exact power of 2 */
351 size_t lbits = mp_bases[base].big_base;
352 res = (nbits + (lbits - 1)) / lbits;
353 } else {
354 res = (nbits * mp_bases[base].chars_per_bit_exactly) + 1;
355 }
356 if (_mpw_debug < -1)
357 fprintf(stderr, "*** mpsizeinbase(%p[%d], %d) res %u\n", xdata, xsize, base, (unsigned)res);
358 return res;
359 }
360
361 #ifdef DYING
362 /*@-boundswrite@*/
myndivmod(mpw * result,size_t xsize,const mpw * xdata,size_t ysize,const mpw * ydata,register mpw * workspace)363 static void myndivmod(mpw* result, size_t xsize, const mpw* xdata, size_t ysize, const mpw* ydata, register mpw* workspace)
364 {
365 /* result must be xsize+1 in length */
366 /* workspace must be ysize+1 in length */
367 /* expect ydata to be normalized */
368 mpw q;
369 mpw msw = *ydata;
370 size_t qsize = xsize-ysize;
371
372 *result = (mpge(ysize, xdata, ydata) ? 1 : 0);
373 mpcopy(xsize, result+1, xdata);
374 if (*result)
375 (void) mpsub(ysize, result+1, ydata);
376 result++;
377
378 while (qsize--)
379 {
380 q = mppndiv(result[0], result[1], msw);
381
382 /*@-evalorder@*/
383 *workspace = mpsetmul(ysize, workspace+1, ydata, q);
384 /*@=evalorder@*/
385
386 while (mplt(ysize+1, result, workspace))
387 {
388 (void) mpsubx(ysize+1, workspace, ysize, ydata);
389 q--;
390 }
391 (void) mpsub(ysize+1, result, workspace);
392 *(result++) = q;
393 }
394 }
395 /*@=boundswrite@*/
396 #endif
397
398 static char *
mpstr(char * t,size_t nt,size_t size,mpw * data,mpw base)399 mpstr(char * t, size_t nt, size_t size, mpw* data, mpw base)
400 /*@modifies t @*/
401 {
402 static char bchars[] = "0123456789abcdefghijklmnopqrstuvwxyz";
403 size_t asize = size + 1;
404 mpw* adata = alloca(asize * sizeof(*adata));
405 size_t anorm;
406 mpw* zdata = alloca((asize+1) * sizeof(*zdata));
407 mpw* wksp = alloca((1+1) * sizeof(*wksp));
408 size_t result;
409
410 if (_mpw_debug < -1)
411 fprintf(stderr, "*** mpstr(%p[%d], %p[%d], %d):\t", t, nt, data, size, base), mpfprintln(stderr, size, data);
412
413 mpsetx(asize, adata, size, data);
414
415 t[nt] = '\0';
416 while (nt--) {
417
418 mpndivmod(zdata, asize, adata, 1, &base, wksp);
419
420 if (_mpw_debug < -1) {
421 fprintf(stderr, " a %p[%d]:\t", adata, asize), mpfprintln(stderr, asize, adata);
422 fprintf(stderr, " z %p[%d]:\t", zdata, asize+1), mpfprintln(stderr, asize+1, zdata);
423 }
424 result = zdata[asize];
425 t[nt] = bchars[result];
426
427 if (mpz(asize, zdata))
428 break;
429
430 anorm = asize - mpsize(asize, zdata);
431 if (anorm < asize)
432 asize -= anorm;
433 mpsetx(asize+1, adata, asize, zdata+anorm);
434 asize++;
435 }
436 /* XXX Fill leading zeroes (if any). */
437 while (nt--)
438 t[nt] = '0';
439 return t;
440 }
441
442 static PyObject *
mpw_format(mpwObject * z,size_t base,int addL)443 mpw_format(mpwObject * z, size_t base, int addL)
444 /*@modifies t @*/
445 {
446 size_t zsize = MPW_SIZE(z);
447 mpw* zdata = MPW_DATA(z);
448 PyStringObject * so;
449 size_t i;
450 size_t nt;
451 size_t size;
452 mpw* data;
453 char * t, * te;
454 char prefix[5];
455 char * tcp = prefix;
456 int sign;
457
458 if (z == NULL || !mpw_Check(z)) {
459 PyErr_BadInternalCall();
460 return NULL;
461 }
462
463 if (_mpw_debug < -1)
464 fprintf(stderr, "*** mpw_format(%p,%d,%d):\t", z, base, addL), mpfprintln(stderr, zsize, zdata);
465
466 assert(base >= 2 && base <= 36);
467
468 i = 0;
469 if (addL && initialiser_name != NULL)
470 i = strlen(initialiser_name) + 2; /* e.g. 'mpw(' + ')' */
471
472 sign = z->ob_size;
473 nt = MPBITCNT(zsize, zdata);
474 if (nt == 0) {
475 base = 10; /* '0' in every base, right */
476 nt = 1;
477 size = 1;
478 data = alloca(size * sizeof(*data));
479 *data = 0;
480 } else if (sign < 0) {
481 *tcp++ = '-';
482 i += 1; /* space to hold '-' */
483 size = MP_ROUND_B2W(nt);
484 data = zdata + (zsize - size);
485 } else {
486 size = MP_ROUND_B2W(nt);
487 data = zdata + (zsize - size);
488 }
489
490 if (addL && size > 1)
491 i++; /* space for 'L' suffix */
492
493 nt = mpsizeinbase(size, data, base);
494 i += nt;
495
496 if (base == 16) {
497 *tcp++ = '0';
498 *tcp++ = 'x';
499 i += 2; /* space to hold '0x' */
500 } else if (base == 8) {
501 *tcp++ = '0';
502 i += 1; /* space to hold the extra '0' */
503 } else if (base > 10) {
504 *tcp++ = '0' + base / 10;
505 *tcp++ = '0' + base % 10;
506 *tcp++ = '#';
507 i += 3; /* space to hold e.g. '12#' */
508 } else if (base < 10) {
509 *tcp++ = '0' + base;
510 *tcp++ = '#';
511 i += 2; /* space to hold e.g. '6#' */
512 }
513
514 so = (PyStringObject *)PyString_FromStringAndSize((char *)0, i);
515 if (so == NULL)
516 return NULL;
517
518 /* get the beginning of the string memory and start copying things */
519 te = PyString_AS_STRING(so);
520 if (addL && initialiser_name != NULL && *initialiser_name != '\0') {
521 te = stpcpy(te, initialiser_name);
522 *te++ = '('; /*')'*/
523 }
524
525 /* copy the already prepared prefix; e.g. sign and base indicator */
526 *tcp = '\0';
527 t = te = stpcpy(te, prefix);
528
529 (void) mpstr(te, nt, size, data, base);
530
531 /* Nuke leading zeroes. */
532 nt = 0;
533 while (t[nt] == '0')
534 nt++;
535 if (t[nt] == '\0') /* all zeroes special case. */
536 nt--;
537 if (nt > 0)
538 do {
539 *t = t[nt];
540 } while (*t++ != '\0');
541
542 te += strlen(te);
543
544 if (addL) {
545 if (size > 1)
546 *te++ = 'L';
547 if (initialiser_name != NULL && *initialiser_name != '\0')
548 *te++ = /*'('*/ ')';
549 }
550 *te = '\0';
551
552 assert(te - PyString_AS_STRING(so) <= i);
553
554 if (te - PyString_AS_STRING(so) != i)
555 so->ob_size -= i - (te - PyString_AS_STRING(so));
556
557 return (PyObject *)so;
558 }
559
560 /**
561 * Precomputes the sliding window table for computing powers of x.
562 *
563 * Sliding Window Exponentiation, Algorithm 14.85 in "Handbook of Applied Cryptography".
564 *
565 * First of all, the table with the powers of g can be reduced by
566 * about half; the even powers don't need to be accessed or stored.
567 *
568 * Get up to K bits starting with a one, if we have that many still available.
569 *
570 * Do the number of squarings of A in the first column, then multiply by
571 * the value in column two, and finally do the number of squarings in
572 * column three.
573 *
574 * This table can be used for K=2,3,4 and can be extended.
575 *
576 *
577 \verbatim
578 0 : - | - | -
579 1 : 1 | g1 @ 0 | 0
580 10 : 1 | g1 @ 0 | 1
581 11 : 2 | g3 @ 1 | 0
582 100 : 1 | g1 @ 0 | 2
583 101 : 3 | g5 @ 2 | 0
584 110 : 2 | g3 @ 1 | 1
585 111 : 3 | g7 @ 3 | 0
586 1000 : 1 | g1 @ 0 | 3
587 1001 : 4 | g9 @ 4 | 0
588 1010 : 3 | g5 @ 2 | 1
589 1011 : 4 | g11 @ 5 | 0
590 1100 : 2 | g3 @ 1 | 2
591 1101 : 4 | g13 @ 6 | 0
592 1110 : 3 | g7 @ 3 | 1
593 1111 : 4 | g15 @ 7 | 0
594 \endverbatim
595 *
596 */
mpslide(size_t xsize,const mpw * xdata,size_t size,mpw * slide)597 static void mpslide(size_t xsize, const mpw* xdata,
598 size_t size, /*@out@*/ mpw* slide)
599 /*@modifies slide @*/
600 {
601 size_t rsize = (xsize > size ? xsize : size);
602 mpw* result = alloca(2 * rsize * sizeof(*result));
603
604 mpsqr(result, xsize, xdata); /* x^2 temp */
605 mpsetx(size, slide, xsize+xsize, result);
606 if (_mpw_debug < 0)
607 fprintf(stderr, "\t x^2:\t"), mpfprintln(stderr, size, slide);
608 mpmul(result, xsize, xdata, size, slide); /* x^3 */
609 mpsetx(size, slide+size, xsize+size, result);
610 if (_mpw_debug < 0)
611 fprintf(stderr, "\t x^3:\t"), mpfprintln(stderr, size, slide+size);
612 mpmul(result, size, slide, size, slide+size); /* x^5 */
613 mpsetx(size, slide+2*size, size+size, result);
614 if (_mpw_debug < 0)
615 fprintf(stderr, "\t x^5:\t"), mpfprintln(stderr, size, slide+2*size);
616 mpmul(result, size, slide, size, slide+2*size); /* x^7 */
617 mpsetx(size, slide+3*size, size+size, result);
618 if (_mpw_debug < 0)
619 fprintf(stderr, "\t x^7:\t"), mpfprintln(stderr, size, slide+3*size);
620 mpmul(result, size, slide, size, slide+3*size); /* x^9 */
621 mpsetx(size, slide+4*size, size+size, result);
622 if (_mpw_debug < 0)
623 fprintf(stderr, "\t x^9:\t"), mpfprintln(stderr, size, slide+4*size);
624 mpmul(result, size, slide, size, slide+4*size); /* x^11 */
625 mpsetx(size, slide+5*size, size+size, result);
626 if (_mpw_debug < 0)
627 fprintf(stderr, "\t x^11:\t"), mpfprintln(stderr, size, slide+5*size);
628 mpmul(result, size, slide, size, slide+5*size); /* x^13 */
629 mpsetx(size, slide+6*size, size+size, result);
630 if (_mpw_debug < 0)
631 fprintf(stderr, "\t x^13:\t"), mpfprintln(stderr, size, slide+6*size);
632 mpmul(result, size, slide, size, slide+6*size); /* x^15 */
633 mpsetx(size, slide+7*size, size+size, result);
634 if (_mpw_debug < 0)
635 fprintf(stderr, "\t x^15:\t"), mpfprintln(stderr, size, slide+7*size);
636 mpsetx(size, slide, xsize, xdata); /* x^1 */
637 if (_mpw_debug < 0)
638 fprintf(stderr, "\t x^1:\t"), mpfprintln(stderr, size, slide);
639 }
640
641 /*@observer@*/ /*@unchecked@*/
642 static byte mpslide_presq[16] =
643 { 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 4, 2, 4, 3, 4 };
644
645 /*@observer@*/ /*@unchecked@*/
646 static byte mpslide_mulg[16] =
647 { 0, 0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7 };
648
649 /*@observer@*/ /*@unchecked@*/
650 static byte mpslide_postsq[16] =
651 { 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 };
652
653 /**
654 * Exponentiation with precomputed sliding window table.
655 */
656 /*@-boundsread@*/
mpnpowsld_w(mpnumber * n,size_t size,const mpw * slide,size_t psize,const mpw * pdata)657 static void mpnpowsld_w(mpnumber* n, size_t size, const mpw* slide,
658 size_t psize, const mpw* pdata)
659 /*@modifies n @*/
660 {
661 size_t rsize = (n->size > size ? n->size : size);
662 mpw* rdata = alloca(2 * rsize * sizeof(*rdata));
663 short lbits = 0;
664 short kbits = 0;
665 byte s;
666 mpw temp;
667 short count;
668
669 if (_mpw_debug < 0)
670 fprintf(stderr, "npowsld: p\t"), mpfprintln(stderr, psize, pdata);
671 /* 2. A = 1, i = t. */
672 mpzero(n->size, n->data);
673 n->data[n->size-1] = 1;
674
675 /* Find first bit set in exponent. */
676 temp = *pdata;
677 count = 8 * sizeof(temp);
678 while (count != 0) {
679 if (temp & MP_MSBMASK)
680 break;
681 temp <<= 1;
682 count--;
683 }
684
685 while (psize) {
686 while (count != 0) {
687
688 /* Shift next bit of exponent into sliding window. */
689 kbits <<= 1;
690 if (temp & MP_MSBMASK)
691 kbits++;
692
693 /* On 1st non-zero in window, try to collect K bits. */
694 if (kbits != 0) {
695 if (lbits != 0)
696 lbits++;
697 else if (temp & MP_MSBMASK)
698 lbits = 1;
699 else
700 {};
701
702 /* If window is full, then compute and clear window. */
703 if (lbits == 4) {
704 if (_mpw_debug < 0)
705 fprintf(stderr, "*** #1 lbits %d kbits %d\n", lbits, kbits);
706 for (s = mpslide_presq[kbits]; s > 0; s--) {
707 mpsqr(rdata, n->size, n->data);
708 mpsetx(n->size, n->data, 2*n->size, rdata);
709 if (_mpw_debug < 0)
710 fprintf(stderr, "\t pre1:\t"), mpfprintln(stderr, n->size, n->data);
711 }
712
713 mpmul(rdata, n->size, n->data,
714 size, slide+mpslide_mulg[kbits]*size);
715 mpsetx(n->size, n->data, n->size+size, rdata);
716 if (_mpw_debug < 0)
717 fprintf(stderr, "\t mul1:\t"), mpfprintln(stderr, n->size, n->data);
718
719 for (s = mpslide_postsq[kbits]; s > 0; s--) {
720 mpsqr(rdata, n->size, n->data);
721 mpsetx(n->size, n->data, 2*n->size, rdata);
722 if (_mpw_debug < 0)
723 fprintf(stderr, "\tpost1:\t"), mpfprintln(stderr, n->size, n->data);
724 }
725
726 lbits = kbits = 0;
727 }
728 } else {
729 mpsqr(rdata, n->size, n->data);
730 mpsetx(n->size, n->data, 2*n->size, rdata);
731 if (_mpw_debug < 0)
732 fprintf(stderr, "\t sqr:\t"), mpfprintln(stderr, n->size, n->data);
733 }
734
735 temp <<= 1;
736 count--;
737 }
738 if (--psize) {
739 count = 8 * sizeof(temp);
740 temp = *(pdata++);
741 }
742 }
743
744 if (kbits != 0) {
745 if (_mpw_debug < 0)
746 fprintf(stderr, "*** #1 lbits %d kbits %d\n", lbits, kbits);
747 for (s = mpslide_presq[kbits]; s > 0; s--) {
748 mpsqr(rdata, n->size, n->data);
749 mpsetx(n->size, n->data, 2*n->size, rdata);
750 if (_mpw_debug < 0)
751 fprintf(stderr, "\t pre2:\t"), mpfprintln(stderr, n->size, n->data);
752 }
753
754 mpmul(rdata, n->size, n->data,
755 size, slide+mpslide_mulg[kbits]*size);
756 mpsetx(n->size, n->data, n->size+size, rdata);
757 if (_mpw_debug < 0)
758 fprintf(stderr, "\t mul2:\t"), mpfprintln(stderr, n->size, n->data);
759
760 for (s = mpslide_postsq[kbits]; s > 0; s--) {
761 mpsqr(rdata, n->size, n->data);
762 mpsetx(n->size, n->data, 2*n->size, rdata);
763 if (_mpw_debug < 0)
764 fprintf(stderr, "\tpost2:\t"), mpfprintln(stderr, n->size, n->data);
765 }
766 }
767 }
768 /*@=boundsread@*/
769
770 /**
771 * mpnpow_w
772 *
773 * Uses sliding window exponentiation; needs extra storage:
774 * if K=3, needs 4*size, if K=4, needs 8*size
775 */
776 /*@-boundsread@*/
mpnpow_w(mpnumber * n,size_t xsize,const mpw * xdata,size_t psize,const mpw * pdata)777 static void mpnpow_w(mpnumber* n, size_t xsize, const mpw* xdata,
778 size_t psize, const mpw* pdata)
779 /*@modifies n @*/
780 {
781 size_t xbits = MPBITCNT(xsize, xdata);
782 size_t pbits = MPBITCNT(psize, pdata);
783 size_t nbits;
784 mpw *slide;
785 size_t nsize;
786 size_t size;
787
788 /* Special case: 0**P and X**(-P) */
789 if (xbits == 0 || (psize > 0 && mpmsbset(psize, pdata))) {
790 mpnsetw(n, 0);
791 return;
792 }
793 /* Special case: X**0 and 1**P */
794 if (pbits == 0 || mpisone(xsize, xdata)) {
795 mpnsetw(n, 1);
796 return;
797 }
798
799 /* Normalize (to mpw boundary) exponent. */
800 pdata += psize - MP_ROUND_B2W(pbits);
801 psize -= MP_BITS_TO_WORDS(pbits);
802
803 /* Calculate size of result. */
804 if (xbits == 0) xbits = 1;
805 nbits = (*pdata) * xbits;
806 nsize = MP_ROUND_B2W(nbits);
807
808 /* XXX Add 1 word to carry sign bit */
809 if (!mpmsbset(xsize, xdata) && (nbits & (MP_WBITS - 1)) == 0)
810 nsize++;
811
812 size = MP_ROUND_B2W(15 * xbits);
813
814 if (_mpw_debug < 0)
815 fprintf(stderr, "*** pbits %d xbits %d nsize %d size %d\n", pbits, xbits, nsize, size);
816 mpnsize(n, nsize);
817
818 /* 1. Precompute odd powers of x (up to 2**K). */
819 slide = (mpw*) alloca( (8*size) * sizeof(mpw));
820
821 mpslide(xsize, xdata, size, slide);
822
823 /*@-internalglobs -mods@*/ /* noisy */
824 mpnpowsld_w(n, size, slide, psize, pdata);
825 /*@=internalglobs =mods@*/
826
827 }
828 /*@=boundsread@*/
829
830 /* ---------- */
831
832 mpwObject *
mpw_New(int ob_size)833 mpw_New(int ob_size)
834 /*@*/
835 {
836 size_t size = ABS(ob_size);
837 mpwObject * z;
838
839 /* XXX Make sure that 0 has allocated space. */
840 if (size == 0)
841 size++;
842 z = PyObject_NEW_VAR(mpwObject, &mpw_Type, size);
843 if (z == NULL)
844 return NULL;
845
846 z->ob_size = ob_size;
847
848 if (size > 0)
849 memset(&z->data, 0, size * sizeof(*z->data));
850
851 return z;
852 }
853
854 static mpwObject *
mpw_Copy(mpwObject * a)855 mpw_Copy(mpwObject *a)
856 /*@*/
857 {
858 mpwObject * z;
859
860 z = mpw_FromMPW(MPW_SIZE(a), MPW_DATA(a), 1);
861 if (z != NULL)
862 z->ob_size = a->ob_size;
863 return z;
864 }
865
866 static mpwObject *
mpw_FromLong(long ival)867 mpw_FromLong(long ival)
868 /*@*/
869 {
870 mpwObject * z = mpw_New(1);
871
872 if (z == NULL)
873 return NULL;
874
875 if (ival < 0) {
876 z->ob_size = -z->ob_size;
877 ival = -ival;
878 }
879 z->data[0] = (mpw) ival;
880
881 return z;
882 }
883
884 static mpwObject *
mpw_FromDouble(double dval)885 mpw_FromDouble(double dval)
886 {
887 mpwObject * z = mpw_New(1);
888
889 if (z == NULL)
890 return NULL;
891
892 if (dval < 0) {
893 z->ob_size = -z->ob_size;
894 dval = -dval;
895 }
896 z->data[0] = (mpw) dval;
897
898 return z;
899 }
900
901 #ifdef NOTYET
902 static mpwObject *
mpw_FromString(const char * str,char ** sep,int base)903 mpw_FromString(const char * str, char ** sep, int base)
904 /*@*/
905 {
906 const char * s = str, * se;
907 mpwObject * z = NULL;
908 mpw zbase, zval;
909 int sign = 1;
910 int ndigits;
911
912 if ((base != 0 && base < 2) || base > 36) {
913 PyErr_SetString(PyExc_ValueError, "mpw() arg 2 must be >= 2 and <= 36");
914 return NULL;
915 }
916 while (*s != '\0' && isspace(Py_CHARMASK(*s)))
917 s++;
918 if (*s == '+')
919 ++s;
920 else if (*s == '-') {
921 ++s;
922 sign = -1;
923 }
924 while (*s != '\0' && isspace(Py_CHARMASK(*s)))
925 s++;
926 if (base == 0) {
927 if (s[0] != '0')
928 base = 10;
929 else if (s[1] == 'x' || s[1] == 'X')
930 base = 16;
931 else
932 base = 8;
933 }
934 if (base == 16 && s[0] == '0' && (s[1] == 'x' || s[1] == 'X'))
935 s += 2;
936
937 /* Validate characters as digits of base. */
938 for (se = s; *se != '\0'; se++) {
939 int k;
940
941 if (*se <= '9')
942 k = *se - '0';
943 else if (*se >= 'a')
944 k = *se - 'a' + 10;
945 else if (*se >= 'A')
946 k = *se - 'A' + 10;
947 else
948 k = -1;
949 if (k < 0 || k >= base)
950 break;
951 }
952 if (se == s)
953 goto onError;
954
955 ndigits = (se - s);
956
957 if (*se == 'L' || *se == 'l')
958 se++;
959 while (*se && isspace(Py_CHARMASK(*se)))
960 se++;
961 if (sep)
962 *sep = se;
963 if (*se != '\0')
964 goto onError;
965
966 /* Allocate mpw. */
967
968 /* Convert digit string. */
969 zbase = base;
970 for (se = s; *se != '\0'; se++) {
971 if (*se <= '9')
972 zval = *se - '0';
973 else if (*se >= 'a')
974 zval = *se - 'a' + 10;
975 else if (*se >= 'A')
976 zval = *se - 'A' + 10;
977 }
978
979 if (sign < 0 && z != NULL && z->ob_size != 0)
980 z->ob_size = -(z->ob_size);
981
982 return z;
983
984 onError:
985 PyErr_Format(PyExc_ValueError, "invalid literal for mpw(): %.200s", str);
986 Py_XDECREF(z);
987 return NULL;
988 }
989 #endif
990
991 static mpwObject *
mpw_FromHEX(const char * hex)992 mpw_FromHEX(const char * hex)
993 /*@*/
994 {
995 size_t len = strlen(hex);
996 size_t size = MP_NIBBLES_TO_WORDS(len + MP_WNIBBLES - 1);
997 mpwObject * z = mpw_New(size);
998
999 if (z != NULL && size > 0)
1000 hs2ip(MPW_DATA(z), size, hex, len);
1001
1002 return z;
1003 }
1004
1005 mpwObject *
mpw_FromMPW(size_t size,mpw * data,int normalize)1006 mpw_FromMPW(size_t size, mpw* data, int normalize)
1007 {
1008 mpwObject * z;
1009
1010 if (normalize) {
1011 size_t norm = size - MP_ROUND_B2W(MPBITCNT(size, data));
1012 if (norm > 0 && norm < size) {
1013 size -= norm;
1014 data += norm;
1015 }
1016 }
1017
1018 z = mpw_New(size);
1019 if (z == NULL)
1020 return NULL;
1021
1022 if (size > 0)
1023 memcpy(&z->data, data, size * sizeof(*z->data));
1024
1025 return z;
1026 }
1027
1028 static mpwObject *
mpw_FromLongObject(PyLongObject * lo)1029 mpw_FromLongObject(PyLongObject *lo)
1030 /*@*/
1031 {
1032 mpwObject * z;
1033 int lsize = ABS(lo->ob_size);
1034 int lbits = DIGITS_TO_BITS(lsize);
1035 size_t zsize = MP_BITS_TO_WORDS(lbits) + 1;
1036 mpw* zdata;
1037 unsigned char * zb;
1038 size_t nzb;
1039 int is_littleendian = 0;
1040 int is_signed = 0;
1041
1042 lsize = zsize;
1043 if (lo->ob_size < 0)
1044 lsize = -lsize;
1045 z = mpw_New(lsize);
1046 if (z == NULL)
1047 return NULL;
1048
1049 zdata = MPW_DATA(z);
1050 zb = (unsigned char *) zdata;
1051 nzb = MP_WORDS_TO_BYTES(zsize);
1052
1053 /* Grab long as big-endian unsigned octets. */
1054 if (_PyLong_AsByteArray(lo, zb, nzb, is_littleendian, is_signed)) {
1055 Py_DECREF(z);
1056 return NULL;
1057 }
1058
1059 /* Endian swap zdata's mpw elements. */
1060 if (IS_LITTLE_ENDIAN()) {
1061 mpw w = 0;
1062 int zx = 0;
1063 while (nzb) {
1064 w <<= 8;
1065 w |= *zb++;
1066 nzb--;
1067 if ((nzb % MP_WBYTES) == 0) {
1068 zdata[zx++] = w;
1069 w = 0;
1070 }
1071 }
1072 }
1073
1074 return z;
1075 }
1076
1077 /* ---------- */
1078
1079 static void
mpw_dealloc(mpwObject * s)1080 mpw_dealloc(/*@only@*/mpwObject * s)
1081 /*@modifies s @*/
1082 {
1083 if (_mpw_debug < -1)
1084 fprintf(stderr, "*** mpw_dealloc(%p[%s])\n", s, lbl(s));
1085
1086 PyObject_Del(s);
1087 }
1088
1089 static int
mpw_compare(mpwObject * a,mpwObject * b)1090 mpw_compare(mpwObject * a, mpwObject * b)
1091 /*@*/
1092 {
1093 size_t asize = MPW_SIZE(a);
1094 mpw* adata = MPW_DATA(a);
1095 size_t bsize = MPW_SIZE(b);
1096 mpw* bdata = MPW_DATA(b);
1097 int ret;
1098
1099 if (mpeqx(asize, adata, bsize, bdata))
1100 ret = 0;
1101 else if (mpgtx(asize, adata, bsize, bdata))
1102 ret = 1;
1103 else
1104 ret = -1;
1105
1106 if (_mpw_debug)
1107 fprintf(stderr, "*** mpw_compare(%p[%s],%p[%s]) ret %d\n", a, lbl(a), b, lbl(b), ret);
1108 return ret;
1109 }
1110
1111 static PyObject *
mpw_repr(mpwObject * a)1112 mpw_repr(mpwObject * a)
1113 /*@*/
1114 {
1115 PyObject * so = mpw_format(a, 10, 1);
1116 if (_mpw_debug && so != NULL)
1117 fprintf(stderr, "*** mpw_repr(%p): \"%s\"\n", a, PyString_AS_STRING(so));
1118 return so;
1119 }
1120
1121 /** \ingroup py_c
1122 */
1123 static PyObject *
mpw_str(mpwObject * a)1124 mpw_str(mpwObject * a)
1125 /*@*/
1126 {
1127 PyObject * so = mpw_format(a, 10, 0);
1128 if (so != NULL && _mpw_debug < -1)
1129 fprintf(stderr, "*** mpw_str(%p): \"%s\"\n", a, PyString_AS_STRING(so));
1130 return so;
1131 }
1132
1133 #ifdef DYING
1134 /** \ingroup py_c
1135 */
mpw_init(mpwObject * z,PyObject * args,PyObject * kwds)1136 static int mpw_init(mpwObject * z, PyObject *args, PyObject *kwds)
1137 /*@modifies s @*/
1138 {
1139 PyObject * o = NULL;
1140 long l = 0;
1141
1142 if (!PyArg_ParseTuple(args, "|O:Cvt", &o)) return -1;
1143
1144 if (o == NULL) {
1145 mpnsetw(&z->n, l);
1146 } else if (PyInt_Check(o)) {
1147 l = PyInt_AsLong(o);
1148 mpnsetw(&z->n, l);
1149 } else if (PyLong_Check(o)) {
1150 PyLongObject *lo = (PyLongObject *)o;
1151 int lsize = ABS(lo->ob_size);
1152 int lbits = DIGITS_TO_BITS(lsize);
1153 size_t zsize = MP_BITS_TO_WORDS(lbits) + 1;
1154 mpw* zdata = alloca(zsize * sizeof(*zdata));
1155 unsigned char * zb = (unsigned char *) zdata;
1156 size_t nzb = MP_WORDS_TO_BYTES(zsize);
1157 int is_littleendian = 0;
1158 int is_signed = 1;
1159
1160 /* Grab long as big-endian signed octets. */
1161 if (_PyLong_AsByteArray(lo, zb, nzb, is_littleendian, is_signed))
1162 return -1;
1163
1164 /* Endian swap zdata's mpw elements. */
1165 if (IS_LITTLE_ENDIAN()) {
1166 mpw w = 0;
1167 int zx = 0;
1168 while (nzb) {
1169 w <<= 8;
1170 w |= *zb++;
1171 nzb--;
1172 if ((nzb % MP_WBYTES) == 0) {
1173 zdata[zx++] = w;
1174 w = 0;
1175 }
1176 }
1177 }
1178 mpnset(&z->n, zsize, zdata);
1179 } else if (PyFloat_Check(o)) {
1180 double d = PyFloat_AsDouble(o);
1181 /* XXX TODO: check for overflow/underflow. */
1182 l = (long) (d + 0.5);
1183 mpnsetw(&z->n, l);
1184 } else if (PyString_Check(o)) {
1185 const unsigned char * hex = PyString_AsString(o);
1186 /* XXX TODO: check for hex. */
1187 mpnsethex(&z->n, hex);
1188 } else if (mpw_Check(o)) {
1189 mpwObject *a = (mpwObject *)o;
1190 mpncopy(&z->n, &a->n);
1191 } else {
1192 PyErr_SetString(PyExc_TypeError, "non-numeric coercion failed (mpw_init)");
1193 return -1;
1194 }
1195
1196 if (_mpw_debug)
1197 fprintf(stderr, "*** mpw_init(%p[%s],%p[%s],%p[%s]):\t", z, lbl(z), args, lbl(args), kwds, lbl(kwds)), mpfprintln(stderr, MPW_SIZE(z), MPW_DATA(z));
1198
1199 return 0;
1200 }
1201 #endif
1202
1203 /** \ingroup py_c
1204 */
mpw_free(mpwObject * s)1205 static void mpw_free(/*@only@*/ mpwObject * s)
1206 /*@modifies s @*/
1207 {
1208 if (_mpw_debug)
1209 fprintf(stderr, "*** mpw_free(%p[%s])\n", s, lbl(s));
1210 PyObject_Del(s);
1211 }
1212
1213 /** \ingroup py_c
1214 * Convert integer to mpw.
1215 */
1216 static mpwObject *
mpw_i2mpw(PyObject * o)1217 mpw_i2mpw(PyObject * o)
1218 /*@modifies o @*/
1219 {
1220 if (mpw_Check(o)) {
1221 Py_INCREF(o);
1222 return (mpwObject *)o;
1223 }
1224 if (PyInt_Check(o))
1225 return mpw_FromLong(PyInt_AsLong(o));
1226 else if (PyLong_Check(o))
1227 return mpw_FromLongObject((PyLongObject *)o);
1228 else if (PyFloat_Check(o))
1229 return mpw_FromDouble(PyFloat_AsDouble(o));
1230 else if (PyString_Check(o))
1231 return mpw_FromHEX(PyString_AS_STRING(o));
1232
1233 PyErr_SetString(PyExc_TypeError, "number coercion (to mpwObject) failed");
1234 return NULL;
1235 }
1236
1237 static PyObject *
mpw_new(PyTypeObject * type,PyObject * args,PyObject * kwds)1238 mpw_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1239 /*@*/
1240 {
1241 mpwObject *z;
1242
1243 if (type != &mpw_Type) {
1244 mpwObject *tz;
1245 size_t size;
1246
1247 assert(PyType_IsSubtype(type, &mpw_Type));
1248 tz = (mpwObject *)mpw_new(&mpw_Type, args, kwds);
1249 if (tz == NULL)
1250 return NULL;
1251
1252 size = ABS(tz->ob_size);
1253 z = (mpwObject *) type->tp_alloc(type, size);
1254 if (z == NULL)
1255 return NULL;
1256
1257 z->ob_size = tz->ob_size;
1258 if (size > 0)
1259 memcpy(&z->data, &tz->data, size * sizeof(*z->data));
1260 Py_DECREF(tz);
1261 } else {
1262 PyObject * x = NULL;
1263 int base = -909;
1264 static char *kwlist[] = {"x", "base", 0};
1265
1266 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:mpw", kwlist, &x, &base))
1267 return NULL;
1268
1269 if (x != NULL) {
1270 /* XXX make sure new instance, not old reference. */
1271 if (mpw_Check(x)) {
1272 mpwObject *zo = (mpwObject *)x;
1273 z = mpw_Copy(zo);
1274 } else
1275 z = mpw_i2mpw(x);
1276 } else
1277 z = mpw_FromLong(0);
1278 }
1279
1280 if (_mpw_debug < -1)
1281 fprintf(stderr, "*** mpw_new(%p[%s],%p[%s],%p[%s])\t", type, lbl(type), args, lbl(args), kwds, lbl(kwds)), mpfprintln(stderr, MPW_SIZE(z), MPW_DATA(z));
1282
1283 return (PyObject *)z;
1284 }
1285
1286 /** \ingroup py_c
1287 * Compute 2 argument operations.
1288 */
1289 static PyObject *
mpw_ops2(const char * fname,char op,mpwObject * x,mpwObject * m)1290 mpw_ops2(const char *fname, char op, mpwObject *x, mpwObject *m)
1291 /*@*/
1292 {
1293 mpwObject * z = NULL;
1294 size_t xsize;
1295 mpw* xdata;
1296 size_t msize;
1297 mpw* mdata;
1298 size_t mnorm;
1299 size_t asize;
1300 mpw* adata;
1301 size_t bsize;
1302 mpw* bdata;
1303 size_t shift;
1304 size_t zsize;
1305 mpw* zdata;
1306 mpw* wksp;
1307 mpbarrett b;
1308 int carry;
1309 int zsign = 0;
1310
1311 mpbzero(&b);
1312 if (x == NULL || m == NULL)
1313 goto exit;
1314
1315 xsize = MPW_SIZE(x);
1316 xdata = MPW_DATA(x);
1317 msize = MPW_SIZE(m);
1318 mdata = MPW_DATA(m);
1319 mnorm = msize - mpsize(msize, mdata);
1320 if (mnorm > 0 && mnorm < msize) {
1321 msize -= mnorm;
1322 mdata += mnorm;
1323 }
1324
1325 if (_mpw_debug < 0) {
1326 prtmpw("a", x);
1327 prtmpw("b", m);
1328 }
1329
1330 switch (op) {
1331 default:
1332 goto exit;
1333 /*@notreached@*/ break;
1334 case '+':
1335 zsize = MAX(xsize, msize) + 1;
1336 zdata = alloca(zsize * sizeof(*zdata));
1337 mpsetx(zsize, zdata, xsize, xdata);
1338 if (x->ob_size < 0) {
1339 zsign = 1;
1340 if (m->ob_size < 0) {
1341 carry = mpaddx(zsize-1, zdata+1, msize, mdata);
1342 if (carry) {
1343 if (_mpw_debug)
1344 fprintf(stderr, "add --: carry\n");
1345 *zdata = 1;
1346 }
1347 } else {
1348 carry = mpsubx(zsize-1, zdata+1, msize, mdata);
1349 if (carry) {
1350 if (_mpw_debug)
1351 fprintf(stderr, "add -+: borrow\n");
1352 *zdata = MP_ALLMASK;
1353 mpneg(zsize, zdata);
1354 zsign = 0;
1355 }
1356 }
1357 } else {
1358 zsign = 0;
1359 if (m->ob_size < 0) {
1360 carry = mpsubx(zsize-1, zdata+1, msize, mdata);
1361 if (carry) {
1362 if (_mpw_debug)
1363 fprintf(stderr, "add +-: borrow\n");
1364 *zdata = MP_ALLMASK;
1365 mpneg(zsize, zdata);
1366 zsign = 1;
1367 }
1368 } else {
1369 carry = mpaddx(zsize-1, zdata+1, msize, mdata);
1370 if (carry) {
1371 if (_mpw_debug)
1372 fprintf(stderr, "add ++: carry\n");
1373 *zdata = 1;
1374 }
1375 }
1376 }
1377 z = mpw_FromMPW(zsize, zdata, 1);
1378 if (zsign)
1379 z->ob_size = -z->ob_size;
1380 break;
1381 case '-':
1382 zsize = MAX(xsize, msize) + 1;
1383 zdata = alloca(zsize * sizeof(*zdata));
1384 mpsetx(zsize, zdata, xsize, xdata);
1385 if (x->ob_size < 0) {
1386 zsign = 1;
1387 if (m->ob_size < 0) {
1388 carry = mpsubx(zsize-1, zdata+1, msize, mdata);
1389 if (carry) {
1390 if (_mpw_debug)
1391 fprintf(stderr, "sub --: borrow\n");
1392 *zdata = MP_ALLMASK;
1393 mpneg(zsize, zdata);
1394 zsign = 0;
1395 }
1396 } else {
1397 carry = mpaddx(zsize-1, zdata+1, msize, mdata);
1398 if (carry) {
1399 if (_mpw_debug)
1400 fprintf(stderr, "sub -+: carry\n");
1401 *zdata = 1;
1402 }
1403 }
1404 } else {
1405 zsign = 0;
1406 if (m->ob_size < 0) {
1407 carry = mpaddx(zsize-1, zdata+1, msize, mdata);
1408 if (carry) {
1409 if (_mpw_debug)
1410 fprintf(stderr, "sub +-: carry\n");
1411 *zdata = 1;
1412 }
1413 } else {
1414 carry = mpsubx(zsize-1, zdata+1, msize, mdata);
1415 if (carry) {
1416 if (_mpw_debug)
1417 fprintf(stderr, "sub ++: borrow\n");
1418 *zdata = MP_ALLMASK;
1419 mpneg(zsize, zdata);
1420 zsign = 1;
1421 }
1422 }
1423 }
1424 z = mpw_FromMPW(zsize-1, zdata+1, 1);
1425 if (zsign)
1426 z->ob_size = -z->ob_size;
1427 break;
1428 case '*':
1429 zsize = xsize + msize;
1430 zdata = alloca(zsize * sizeof(*zdata));
1431 zsign = x->ob_size * m->ob_size;
1432 mpmul(zdata, xsize, xdata, msize, mdata);
1433 z = mpw_FromMPW(zsize, zdata, 1);
1434 if (zsign < 0)
1435 z->ob_size = -z->ob_size;
1436 break;
1437 case '/':
1438 asize = xsize+1;
1439 adata = alloca(asize * sizeof(*adata));
1440 mpsetx(asize, adata, xsize, xdata);
1441 bsize = msize;
1442 bdata = alloca(bsize * sizeof(*bdata));
1443 mpsetx(bsize, bdata, msize, mdata);
1444
1445 zsize = asize + 1;
1446 zdata = alloca(zsize * sizeof(*zdata));
1447 zsign = x->ob_size * m->ob_size;
1448 wksp = alloca((bsize+1) * sizeof(*wksp));
1449
1450 shift = mpnorm(bsize, bdata);
1451 mplshift(asize, adata, shift);
1452 mpndivmod(zdata, asize, adata, bsize, bdata, wksp);
1453
1454 zsize -= bsize;
1455
1456 if (zsign < 0)
1457 (void) mpaddw(zsize, zdata, (mpw)1);
1458
1459 z = mpw_FromMPW(zsize, zdata, 1);
1460 if (zsign < 0)
1461 z->ob_size = -z->ob_size;
1462 break;
1463 case '%':
1464 asize = xsize+1;
1465 adata = alloca(asize * sizeof(*adata));
1466 mpsetx(asize, adata, xsize, xdata);
1467 bsize = msize;
1468 bdata = mdata;
1469
1470 zsize = asize;
1471 zdata = alloca(zsize * sizeof(*zdata));
1472 zsign = x->ob_size * m->ob_size;
1473 wksp = alloca((2*bsize+1) * sizeof(*wksp));
1474
1475 mpmod(zdata, asize, adata, bsize, bdata, wksp);
1476
1477 if (zsign < 0) {
1478 if (m->ob_size < 0) {
1479 (void) mpsubx(zsize, zdata, bsize, bdata);
1480 mpneg(zsize, zdata);
1481 } else {
1482 zsign = 0;
1483 mpneg(zsize, zdata);
1484 (void) mpaddx(zsize, zdata, bsize, bdata);
1485 }
1486 }
1487 z = mpw_FromMPW(zsize, zdata, 1);
1488 if (zsign < 0) {
1489 z->ob_size = -z->ob_size;
1490 } else if (zsign > 0) {
1491 if (x->ob_size < 0)
1492 z->ob_size = -z->ob_size;
1493 }
1494 break;
1495 case '<':
1496 /* XXX FIXME: enlarge? negative count? sign?. */
1497 shift = (size_t) (msize == 1 ? mdata[0] : 0);
1498 z = mpw_FromMPW(xsize, xdata, 0);
1499 if (shift > 0)
1500 mplshift(MPW_SIZE(z), MPW_DATA(z), shift);
1501 break;
1502 case '>':
1503 /* XXX FIXME: enlarge? negative count? sign?. */
1504 shift = (size_t) (msize == 1 ? mdata[0] : 0);
1505 z = mpw_FromMPW(xsize, xdata, 0);
1506 if (shift > 0)
1507 mprshift(MPW_SIZE(z), MPW_DATA(z), shift);
1508 break;
1509 case '&':
1510 /* XXX reset to original size for now. */
1511 msize = MPW_SIZE(m);
1512 mdata = MPW_DATA(m);
1513 if (xsize <= msize) {
1514 z = mpw_FromMPW(xsize, xdata, 0);
1515 mpand(MPW_SIZE(z), MPW_DATA(z), mdata + (msize - xsize));
1516 } else {
1517 z = mpw_FromMPW(msize, mdata, 0);
1518 mpand(MPW_SIZE(z), MPW_DATA(z), xdata + (xsize - msize));
1519 }
1520 break;
1521 case '|':
1522 /* XXX reset to original size for now. */
1523 msize = MPW_SIZE(m);
1524 mdata = MPW_DATA(m);
1525 if (xsize <= msize) {
1526 z = mpw_FromMPW(xsize, xdata, 0);
1527 mpor(MPW_SIZE(z), MPW_DATA(z), mdata + (msize - xsize));
1528 } else {
1529 z = mpw_FromMPW(msize, mdata, 0);
1530 mpor(MPW_SIZE(z), MPW_DATA(z), xdata + (xsize - msize));
1531 }
1532 break;
1533 case '^':
1534 /* XXX reset to original size for now. */
1535 msize = MPW_SIZE(m);
1536 mdata = MPW_DATA(m);
1537 if (xsize <= msize) {
1538 z = mpw_FromMPW(xsize, xdata, 0);
1539 mpxor(MPW_SIZE(z), MPW_DATA(z), mdata + (msize - xsize));
1540 } else {
1541 z = mpw_FromMPW(msize, mdata, 0);
1542 mpxor(MPW_SIZE(z), MPW_DATA(z), xdata + (xsize - msize));
1543 }
1544 break;
1545 case 'P':
1546 { mpnumber zn;
1547
1548 mpnzero(&zn);
1549 if (msize == 0 || (msize == 1 && *mdata == 0))
1550 mpnsetw(&zn, 1);
1551 else if (mpz(xsize, xdata) || m->ob_size < 0)
1552 mpnsetw(&zn, 0);
1553 else {
1554 zsign = (x->ob_size > 0 || mpeven(msize, mdata)) ? 1 : -1;
1555 mpnpow_w(&zn, xsize, xdata, msize, mdata);
1556 }
1557 z = mpw_FromMPW(zn.size, zn.data, 1);
1558 mpnfree(&zn);
1559 if (zsign < 0)
1560 z->ob_size = -z->ob_size;
1561 } break;
1562 case 'G':
1563 wksp = alloca((xsize) * sizeof(*wksp));
1564 z = mpw_New(msize);
1565 mpgcd_w(xsize, xdata, mdata, MPW_DATA(z), wksp);
1566 break;
1567 case 'I':
1568 wksp = alloca((7*msize+6)*sizeof(*wksp));
1569 z = mpw_New(msize);
1570 (void) mpextgcd_w(msize, wksp, mdata, MPW_DATA(z), wksp+msize);
1571 break;
1572 #ifdef DYING
1573 case 'R':
1574 { rngObject * r = ((rngObject *)x);
1575
1576 wksp = alloca(msize*sizeof(*wksp));
1577 mpbset(&b, msize, mdata);
1578 z = mpw_New(msize);
1579 mpbrnd_w(&b, &r->rngc, MPW_DATA(z), wksp);
1580 } break;
1581 #endif
1582 case 'S':
1583 wksp = alloca((4*msize+2)*sizeof(*wksp));
1584 mpbset(&b, msize, mdata);
1585 z = mpw_New(msize);
1586 mpbsqrmod_w(&b, xsize, xdata, MPW_DATA(z), wksp);
1587 break;
1588 }
1589
1590 if (_mpw_debug)
1591 fprintf(stderr, "*** mpw_%s %p[%d]\t", fname, MPW_DATA(z), MPW_SIZE(z)), mpfprintln(stderr, MPW_SIZE(z), MPW_DATA(z));
1592
1593 exit:
1594 mpbfree(&b);
1595 Py_XDECREF(x);
1596 Py_XDECREF(m);
1597 return (PyObject *)z;
1598 }
1599
1600 /** \ingroup py_c
1601 * Compute 3 argument operations.
1602 */
1603 static PyObject *
mpw_ops3(const char * fname,char op,mpwObject * x,mpwObject * y,mpwObject * m)1604 mpw_ops3(const char *fname, char op,
1605 mpwObject *x, mpwObject *y, mpwObject *m)
1606 /*@*/
1607 {
1608 mpwObject * z = NULL;
1609 size_t xsize;
1610 mpw* xdata;
1611 size_t ysize;
1612 mpw* ydata;
1613 size_t msize;
1614 mpw* mdata;
1615 size_t zsize;
1616 mpw* zdata;
1617 mpbarrett b;
1618 mpw* wksp;
1619
1620 mpbzero(&b);
1621 if (x == NULL || y == NULL || m == NULL)
1622 goto exit;
1623
1624 if (_mpw_debug < 0) {
1625 prtmpw("a", x);
1626 prtmpw("b", y);
1627 prtmpw("c", m);
1628 }
1629
1630 xsize = MPW_SIZE(x);
1631 xdata = MPW_DATA(x);
1632 ysize = MPW_SIZE(y);
1633 ydata = MPW_DATA(y);
1634 msize = MPW_SIZE(m);
1635 mdata = MPW_DATA(m);
1636
1637 mpbset(&b, msize, mdata);
1638
1639 zsize = b.size;
1640 zdata = alloca(zsize * sizeof(*zdata));
1641 wksp = alloca((4*zsize+2)*sizeof(*wksp));
1642
1643 switch (op) {
1644 case '/':
1645 case '%':
1646 default:
1647 goto exit;
1648 /*@notreached@*/ break;
1649 case '+':
1650 fname = "Addm";
1651 mpbaddmod_w(&b, xsize, xdata, ysize, ydata, zdata, wksp);
1652 break;
1653 case '-':
1654 fname = "Subm";
1655 mpbsubmod_w(&b, xsize, xdata, ysize, ydata, zdata, wksp);
1656 break;
1657 case '*':
1658 fname = "Mulm";
1659 mpbmulmod_w(&b, xsize, xdata, ysize, ydata, zdata, wksp);
1660 break;
1661 case 'P':
1662 fname = "Powm";
1663 mpbpowmod_w(&b, xsize, xdata, ysize, ydata, zdata, wksp);
1664 break;
1665 }
1666
1667 z = mpw_FromMPW(zsize, zdata, 1);
1668
1669 if (_mpw_debug < 0)
1670 fprintf(stderr, "*** mpw_%s %p[%d]\t", fname, MPW_DATA(z), MPW_SIZE(z)), mpfprintln(stderr, MPW_SIZE(z), MPW_DATA(z));
1671
1672 exit:
1673 mpbfree(&b);
1674 Py_XDECREF(x);
1675 Py_XDECREF(y);
1676 Py_XDECREF(m);
1677 return (PyObject *)z;
1678 }
1679
1680 /* ---------- */
1681
1682 /** \ingroup py_c
1683 */
1684 static PyObject *
mpw_Debug(mpwObject * s,PyObject * args)1685 mpw_Debug(/*@unused@*/ mpwObject * s, PyObject * args)
1686 /*@globals _Py_NoneStruct @*/
1687 /*@modifies _Py_NoneStruct @*/
1688 {
1689 if (!PyArg_ParseTuple(args, "i:Debug", &_mpw_debug)) return NULL;
1690 Py_INCREF(Py_None);
1691 return Py_None;
1692 }
1693
1694 /** \ingroup py_c
1695 * Compute gcd(x, y).
1696 */
1697 static PyObject *
mpw_Gcd(mpwObject * s,PyObject * args)1698 mpw_Gcd(mpwObject * s, PyObject * args)
1699 /*@*/
1700 {
1701 PyObject * xo, * mo;
1702
1703 if (!PyArg_ParseTuple(args, "OO:Gcd", &xo, &mo)) return NULL;
1704 return mpw_ops2("Gcd", 'G', mpw_i2mpw(xo), mpw_i2mpw(mo));
1705 }
1706
1707 /** \ingroup py_c
1708 * Compute inverse (modulo m) of x.
1709 */
1710 static PyObject *
mpw_Invm(mpwObject * s,PyObject * args)1711 mpw_Invm(/*@unused@*/ mpwObject * s, PyObject * args)
1712 /*@*/
1713 {
1714 PyObject * xo, * mo;
1715
1716 if (!PyArg_ParseTuple(args, "OO:Invm", &xo, &mo)) return NULL;
1717 return mpw_ops2("Invm", 'I', mpw_i2mpw(xo), mpw_i2mpw(mo));
1718 }
1719
1720 /** \ingroup py_c
1721 * Compute x*x (modulo m).
1722 */
1723 static PyObject *
mpw_Sqrm(mpwObject * s,PyObject * args)1724 mpw_Sqrm(mpwObject * s, PyObject * args)
1725 /*@*/
1726 {
1727 PyObject * xo, * mo;
1728
1729 if (!PyArg_ParseTuple(args, "OO:Sqrm", &xo, &mo)) return NULL;
1730 return mpw_ops2("Sqrm", 'S', mpw_i2mpw(xo), mpw_i2mpw(mo));
1731 }
1732
1733 /** \ingroup py_c
1734 * Compute x+y (modulo m).
1735 */
1736 static PyObject *
mpw_Addm(mpwObject * s,PyObject * args)1737 mpw_Addm(mpwObject * s, PyObject * args)
1738 /*@*/
1739 {
1740 PyObject * xo, * yo, * mo;
1741
1742 if (!PyArg_ParseTuple(args, "OOO:Addm", &xo, &yo, &mo)) return NULL;
1743 return mpw_ops3("Addm", '+',
1744 mpw_i2mpw(xo), mpw_i2mpw(yo), mpw_i2mpw(mo));
1745 }
1746
1747 /** \ingroup py_c
1748 * Compute x-y (modulo m).
1749 */
1750 static PyObject *
mpw_Subm(mpwObject * s,PyObject * args)1751 mpw_Subm(mpwObject * s, PyObject * args)
1752 /*@*/
1753 {
1754 PyObject * xo, * yo, * mo;
1755
1756 if (!PyArg_ParseTuple(args, "OOO:Subm", &xo, &yo, &mo)) return NULL;
1757 return mpw_ops3("Subm", '-',
1758 mpw_i2mpw(xo), mpw_i2mpw(yo), mpw_i2mpw(mo));
1759 }
1760
1761 /** \ingroup py_c
1762 * Compute x*y (modulo m).
1763 */
1764 static PyObject *
mpw_Mulm(mpwObject * s,PyObject * args)1765 mpw_Mulm(mpwObject * s, PyObject * args)
1766 /*@*/
1767 {
1768 PyObject * xo, * yo, * mo;
1769
1770 if (!PyArg_ParseTuple(args, "OOO:Mulm", &xo, &yo, &mo)) return NULL;
1771 return mpw_ops3("Mulm", '*',
1772 mpw_i2mpw(xo), mpw_i2mpw(yo), mpw_i2mpw(mo));
1773 }
1774
1775 /** \ingroup py_c
1776 * Compute x**y (modulo m).
1777 */
1778 static PyObject *
mpw_Powm(mpwObject * s,PyObject * args)1779 mpw_Powm(mpwObject * s, PyObject * args)
1780 /*@*/
1781 {
1782 PyObject * xo, * yo, * mo;
1783
1784 if (!PyArg_ParseTuple(args, "OOO:Powm", &xo, &yo, &mo)) return NULL;
1785 return mpw_ops3("Powm", 'P',
1786 mpw_i2mpw(xo), mpw_i2mpw(yo), mpw_i2mpw(mo));
1787 }
1788
1789 #ifdef DYNING
1790 /** \ingroup py_c
1791 * Return random number 1 < r < b-1.
1792 */
1793 static PyObject *
mpw_Rndm(mpwObject * s,PyObject * args)1794 mpw_Rndm(mpwObject * s, PyObject * args)
1795 /*@*/
1796 {
1797 PyObject * xo, * mo;
1798
1799 if (!PyArg_ParseTuple(args, "OO:Rndm", &mo, &xo)) return NULL;
1800 if (!is_rng(xo)) {
1801 PyErr_SetString(PyExc_TypeError, "mpw.rndm() requires rng_Type argument");
1802 return NULL;
1803 }
1804 return mpw_ops2("Rndm", 'R', (mpwObject*)xo, mpw_i2mpw(mo));
1805 }
1806 #endif
1807
1808 /*@-fullinitblock@*/
1809 /*@unchecked@*/ /*@observer@*/
1810 static struct PyMethodDef mpw_methods[] = {
1811 {"Debug", (PyCFunction)mpw_Debug, METH_VARARGS,
1812 NULL},
1813 {"gcd", (PyCFunction)mpw_Gcd, METH_VARARGS,
1814 NULL},
1815 {"invm", (PyCFunction)mpw_Invm, METH_VARARGS,
1816 NULL},
1817 {"sqrm", (PyCFunction)mpw_Sqrm, METH_VARARGS,
1818 NULL},
1819 {"addm", (PyCFunction)mpw_Addm, METH_VARARGS,
1820 NULL},
1821 {"subm", (PyCFunction)mpw_Subm, METH_VARARGS,
1822 NULL},
1823 {"mulm", (PyCFunction)mpw_Mulm, METH_VARARGS,
1824 NULL},
1825 {"powm", (PyCFunction)mpw_Powm, METH_VARARGS,
1826 NULL},
1827 #ifdef DYING
1828 {"rndm", (PyCFunction)mpw_Rndm, METH_VARARGS,
1829 NULL},
1830 #endif
1831 {NULL, NULL} /* sentinel */
1832 };
1833 /*@=fullinitblock@*/
1834
mpw_getattro(PyObject * o,PyObject * n)1835 static PyObject * mpw_getattro(PyObject * o, PyObject * n)
1836 /*@*/
1837 {
1838 return PyObject_GenericGetAttr(o, n);
1839 }
1840
mpw_setattro(PyObject * o,PyObject * n,PyObject * v)1841 static int mpw_setattro(PyObject * o, PyObject * n, PyObject * v)
1842 /*@*/
1843 {
1844 return PyObject_GenericSetAttr(o, n, v);
1845 }
1846
1847 /* ---------- */
1848
1849 static PyObject *
mpw_add(PyObject * a,PyObject * b)1850 mpw_add(PyObject * a, PyObject * b)
1851 /*@*/
1852 {
1853 return mpw_ops2("add", '+', mpw_i2mpw(a), mpw_i2mpw(b));
1854 }
1855
1856 static PyObject *
mpw_sub(PyObject * a,PyObject * b)1857 mpw_sub(PyObject * a, PyObject * b)
1858 /*@*/
1859 {
1860 return mpw_ops2("sub", '-', mpw_i2mpw(a), mpw_i2mpw(b));
1861 }
1862
1863 static PyObject *
mpw_mul(PyObject * a,PyObject * b)1864 mpw_mul(PyObject * a, PyObject * b)
1865 /*@*/
1866 {
1867 return mpw_ops2("mul", '*', mpw_i2mpw(a), mpw_i2mpw(b));
1868 }
1869
1870 static PyObject *
mpw_div(PyObject * a,PyObject * w)1871 mpw_div(PyObject * a, PyObject * w)
1872 /*@*/
1873 {
1874 mpwObject * b = mpw_i2mpw(w);
1875
1876 if (mpz(MPW_SIZE(b), MPW_DATA(b))) {
1877 Py_DECREF(b);
1878 PyErr_SetString(PyExc_ZeroDivisionError, "mpw_divide by zero");
1879 return NULL;
1880 }
1881 return mpw_ops2("div", '/', mpw_i2mpw(a), b);
1882 }
1883
1884 static PyObject *
mpw_classic_div(PyObject * a,PyObject * b)1885 mpw_classic_div(PyObject * a, PyObject * b)
1886 /*@*/
1887 {
1888 if (Py_DivisionWarningFlag &&
1889 PyErr_Warn(PyExc_DeprecationWarning, "classic long division") < 0)
1890 return NULL;
1891 return mpw_div(a, b);
1892 }
1893
1894 static PyObject *
mpw_mod(PyObject * a,PyObject * b)1895 mpw_mod(PyObject * a, PyObject * b)
1896 /*@*/
1897 {
1898 return mpw_ops2("rem", '%', mpw_i2mpw(a), mpw_i2mpw(b));
1899 }
1900
1901 static PyObject *
mpw_divmod(PyObject * v,PyObject * w)1902 mpw_divmod(PyObject * v, PyObject * w)
1903 /*@*/
1904 {
1905 PyObject * z = NULL;
1906 mpwObject * q = NULL;
1907 mpwObject * r = NULL;
1908 mpwObject * a = mpw_i2mpw(v);
1909 size_t asize;
1910 mpw* adata;
1911 size_t anorm;
1912 mpwObject * b = mpw_i2mpw(w);
1913 size_t bsize;
1914 mpw* bdata;
1915 size_t bnorm;
1916 size_t zsize;
1917 mpw* zdata;
1918 mpw* wksp;
1919 int qsign = 0;
1920
1921 if (a == NULL || b == NULL)
1922 goto exit;
1923
1924 asize = MPW_SIZE(a);
1925 adata = MPW_DATA(a);
1926 anorm = mpsize(asize, adata);
1927 bsize = MPW_SIZE(b);
1928 bdata = MPW_DATA(b);
1929 bnorm = mpsize(bsize, bdata);
1930
1931 if (mpz(bsize, bdata)) {
1932 PyErr_SetString(PyExc_ZeroDivisionError, "mpw_divmod by zero");
1933 goto exit;
1934 }
1935
1936 if (anorm < asize) {
1937 asize -= anorm;
1938 adata += anorm;
1939 }
1940 zsize = asize + 1;
1941 zdata = alloca(zsize * sizeof(*zdata));
1942 if (bnorm < bsize) {
1943 bsize -= bnorm;
1944 bdata += bnorm;
1945 }
1946 qsign = a->ob_size * b->ob_size;
1947 wksp = alloca((bsize+1) * sizeof(*wksp));
1948
1949 mpndivmod(zdata, asize, adata, bsize, bdata, wksp);
1950
1951 if (_mpw_debug < 0) {
1952 fprintf(stderr, " a %p[%d]:\t", adata, asize), mpfprintln(stderr, asize, adata);
1953 fprintf(stderr, " b %p[%d]:\t", bdata, bsize), mpfprintln(stderr, bsize, bdata);
1954 fprintf(stderr, " z %p[%d]:\t", zdata, zsize), mpfprintln(stderr, zsize, zdata);
1955 }
1956
1957 zsize -= bsize;
1958 r = mpw_FromMPW(bsize, zdata+zsize, 1);
1959 if (r == NULL)
1960 goto exit;
1961 if (qsign < 0) {
1962 if (b->ob_size < 0) {
1963 (void) mpsubx(MPW_SIZE(r), MPW_DATA(r), bsize, bdata);
1964 mpneg(MPW_SIZE(r), MPW_DATA(r));
1965 } else {
1966 mpneg(MPW_SIZE(r), MPW_DATA(r));
1967 (void) mpaddx(MPW_SIZE(r), MPW_DATA(r), bsize, bdata);
1968 }
1969 (void) mpaddw(zsize, zdata, (mpw)1);
1970 }
1971 if (b->ob_size < 0)
1972 r->ob_size = -r->ob_size;
1973
1974 q = mpw_FromMPW(zsize, zdata, 1);
1975 if (q == NULL) {
1976 Py_DECREF(r);
1977 goto exit;
1978 }
1979 if (qsign < 0)
1980 q->ob_size = -q->ob_size;
1981
1982 if (_mpw_debug) {
1983 prtmpw("q", q);
1984 prtmpw("r", r);
1985 fprintf(stderr, "*** mpw_divmod(%p,%p)\n", a, b);
1986 }
1987 if ((z = PyTuple_New(2)) == NULL) {
1988 Py_DECREF(q);
1989 Py_DECREF(r);
1990 goto exit;
1991 }
1992
1993 (void) PyTuple_SetItem(z, 0, (PyObject *)q);
1994 (void) PyTuple_SetItem(z, 1, (PyObject *)r);
1995
1996 exit:
1997 Py_XDECREF(a);
1998 Py_XDECREF(b);
1999 return (PyObject *)z;
2000 }
2001
2002 static PyObject *
mpw_pow(PyObject * a,PyObject * b,PyObject * c)2003 mpw_pow(PyObject * a, PyObject * b, PyObject * c)
2004 /*@*/
2005 {
2006 if (c != Py_None)
2007 return mpw_ops3("Powm", 'P', mpw_i2mpw(a), mpw_i2mpw(b), mpw_i2mpw(c));
2008 else
2009 return mpw_ops2("pow", 'P', mpw_i2mpw(a), mpw_i2mpw(b));
2010 }
2011
2012 static PyObject *
mpw_neg(mpwObject * a)2013 mpw_neg(mpwObject * a)
2014 /*@*/
2015 {
2016 mpwObject *z;
2017
2018 if (a->ob_size == 0 && mpw_CheckExact(a)) {
2019 /* -0 == 0 */
2020 Py_INCREF(a);
2021 z = a;
2022 } else {
2023 z = mpw_Copy(a);
2024 if (z != NULL)
2025 z->ob_size = -(a->ob_size);
2026 }
2027
2028 if (z != NULL && _mpw_debug)
2029 fprintf(stderr, "*** mpw_neg %p[%d]\t", MPW_DATA(z), MPW_SIZE(z)), mpfprintln(stderr, MPW_SIZE(z), MPW_DATA(z));
2030
2031 return (PyObject *)z;
2032 }
2033
2034 static PyObject *
mpw_pos(mpwObject * a)2035 mpw_pos(mpwObject * a)
2036 /*@*/
2037 {
2038 mpwObject *z;
2039
2040 if (mpw_CheckExact(a)) {
2041 Py_INCREF(a);
2042 z = a;
2043 } else
2044 z = mpw_Copy(a);
2045
2046 if (z != NULL && _mpw_debug)
2047 fprintf(stderr, "*** mpw_pos %p[%d]\t", MPW_DATA(z), MPW_SIZE(z)), mpfprintln(stderr, MPW_SIZE(z), MPW_DATA(z));
2048
2049 return (PyObject *)z;
2050 }
2051
2052 static PyObject *
mpw_abs(mpwObject * a)2053 mpw_abs(mpwObject * a)
2054 /*@*/
2055 {
2056 mpwObject * z;
2057
2058 if (a->ob_size < 0)
2059 z = (mpwObject *)mpw_neg(a);
2060 else
2061 z = (mpwObject *)mpw_pos(a);
2062
2063 if (z != NULL && _mpw_debug)
2064 fprintf(stderr, "*** mpw_abs %p[%d]\t", MPW_DATA(z), MPW_SIZE(z)), mpfprintln(stderr, MPW_SIZE(z), MPW_DATA(z));
2065
2066 return (PyObject *)z;
2067 }
2068
2069 static int
mpw_nonzero(mpwObject * a)2070 mpw_nonzero(mpwObject * a)
2071 /*@*/
2072 {
2073 return ABS(a->ob_size) != 0;
2074 }
2075
2076 static PyObject *
mpw_invert(mpwObject * a)2077 mpw_invert(mpwObject * a)
2078 /*@*/
2079 {
2080 /* Implement ~z as -(z+1) */
2081 mpwObject * z = mpw_Copy(a);
2082
2083 if (z != NULL) {
2084 mpw val = 1;
2085 int carry;
2086
2087 carry = mpaddx(MPW_SIZE(z), MPW_DATA(z), 1, &val);
2088 z->ob_size = -(a->ob_size);
2089 }
2090 return (PyObject *)z;
2091 }
2092
2093 static PyObject *
mpw_lshift(PyObject * a,PyObject * b)2094 mpw_lshift(PyObject * a, PyObject * b)
2095 /*@*/
2096 {
2097 return mpw_ops2("lshift", '<', mpw_i2mpw(a), mpw_i2mpw(b));
2098 }
2099
2100 static PyObject *
mpw_rshift(PyObject * a,PyObject * b)2101 mpw_rshift(PyObject * a, PyObject * b)
2102 /*@*/
2103 {
2104 return mpw_ops2("rshift", '>', mpw_i2mpw(a), mpw_i2mpw(b));
2105 }
2106
2107 static PyObject *
mpw_and(PyObject * a,PyObject * b)2108 mpw_and(PyObject * a, PyObject * b)
2109 /*@*/
2110 {
2111 return mpw_ops2("and", '&', mpw_i2mpw(a), mpw_i2mpw(b));
2112 }
2113
2114 static PyObject *
mpw_xor(PyObject * a,PyObject * b)2115 mpw_xor(PyObject * a, PyObject * b)
2116 /*@*/
2117 {
2118 return mpw_ops2("xor", '^', mpw_i2mpw(a), mpw_i2mpw(b));
2119 }
2120
2121 static PyObject *
mpw_or(PyObject * a,PyObject * b)2122 mpw_or(PyObject * a, PyObject * b)
2123 /*@*/
2124 {
2125 return mpw_ops2("or", '|', mpw_i2mpw(a), mpw_i2mpw(b));
2126 }
2127
2128 static int
mpw_coerce(PyObject ** pv,PyObject ** pw)2129 mpw_coerce(PyObject ** pv, PyObject ** pw)
2130 /*@modifies *pv, *pw @*/
2131 {
2132
2133 if (_mpw_debug)
2134 fprintf(stderr, "*** mpw_coerce(%p[%s],%p[%s])\n", pv, lbl(*pv), pw, lbl(*pw));
2135
2136 if (mpw_Check(*pw))
2137 Py_INCREF(*pw);
2138 else if (PyInt_Check(*pw))
2139 *pw = (PyObject *) mpw_FromLong(PyInt_AsLong(*pw));
2140 else if (PyLong_Check(*pw))
2141 *pw = (PyObject *) mpw_FromLongObject((PyLongObject *)(*pw));
2142 else if (PyFloat_Check(*pw))
2143 *pw = (PyObject *) mpw_FromDouble(PyFloat_AsDouble(*pw));
2144 else if (PyString_Check(*pw))
2145 *pw = (PyObject *) mpw_FromHEX(PyString_AS_STRING(*pw));
2146 else {
2147 PyErr_SetString(PyExc_TypeError, "non-numeric coercion failed (mpw_coerce)");
2148 return 1;
2149 }
2150
2151 Py_INCREF(*pv);
2152 return 0;
2153 }
2154
2155 static PyObject *
mpw_int(mpwObject * a)2156 mpw_int(mpwObject * a)
2157 /*@*/
2158 {
2159 size_t anorm = MPW_SIZE(a) - MP_ROUND_B2W(MPBITCNT(MPW_SIZE(a), MPW_DATA(a)));
2160 size_t asize = MPW_SIZE(a) - anorm;
2161 mpw* adata = MPW_DATA(a) + anorm;
2162 long ival = 0;
2163
2164 if (asize > 1) {
2165 PyErr_SetString(PyExc_ValueError, "mpw_int: arg too long to convert");
2166 return NULL;
2167 }
2168 if (asize == 1)
2169 ival = adata[0];
2170 if (a->ob_size < 0)
2171 ival = -ival;
2172
2173 return Py_BuildValue("i", ival);
2174 }
2175
2176 static PyObject *
mpw_long(mpwObject * a)2177 mpw_long(mpwObject * a)
2178 /*@*/
2179 {
2180 size_t abits = MPBITCNT(MPW_SIZE(a), MPW_DATA(a));
2181 size_t anorm = MPW_SIZE(a) - MP_ROUND_B2W(abits);
2182 size_t asize = MPW_SIZE(a) - anorm;
2183 mpw* adata = MPW_DATA(a) + anorm;
2184 size_t zsize = asize;
2185 mpw* zdata = alloca(zsize * sizeof(*zdata));
2186 int lsize = BITS_TO_DIGITS(abits);
2187 PyLongObject *lo = _PyLong_New(lsize);
2188 int digx;
2189
2190 if (lo == NULL)
2191 return NULL;
2192
2193 mpcopy(asize, zdata, adata);
2194
2195 for (digx = 0; digx < lsize; digx++) {
2196 lo->ob_digit[digx] = zdata[zsize - 1] & MASK;
2197 mprshift(zsize, zdata, SHIFT);
2198 }
2199
2200 while (digx > 0 && lo->ob_digit[digx-1] == 0)
2201 digx--;
2202 lo->ob_size = (a->ob_size >= 0 ? digx : -digx);
2203
2204 return (PyObject *)lo;
2205 }
2206
2207 static PyObject *
mpw_float(mpwObject * a)2208 mpw_float(mpwObject * a)
2209 /*@*/
2210 {
2211 PyObject * so = mpw_format(a, 10, 0);
2212 char * s, * se;
2213 double d;
2214
2215 if (so == NULL)
2216 return NULL;
2217 s = PyString_AS_STRING(so);
2218 se = NULL;
2219 d = strtod(s, &se);
2220
2221 if (_mpw_debug)
2222 fprintf(stderr, "*** mpw_float(%p): s %p \"%s\" se %p d %g\n", a, s, s, se, d);
2223 Py_DECREF(so);
2224
2225 return Py_BuildValue("d", d);
2226 }
2227
2228 static PyObject *
mpw_oct(mpwObject * a)2229 mpw_oct(mpwObject * a)
2230 /*@*/
2231 {
2232 return mpw_format(a, 8, 1);
2233 }
2234
2235 static PyObject *
mpw_hex(mpwObject * a)2236 mpw_hex(mpwObject * a)
2237 /*@*/
2238 {
2239 return mpw_format(a, 16, 1);
2240 }
2241
2242 static PyNumberMethods mpw_as_number = {
2243 (binaryfunc) mpw_add, /* nb_add */
2244 (binaryfunc) mpw_sub, /* nb_subtract */
2245 (binaryfunc) mpw_mul, /* nb_multiply */
2246 (binaryfunc) mpw_classic_div, /* nb_divide */
2247 (binaryfunc) mpw_mod, /* nb_remainder */
2248 (binaryfunc) mpw_divmod, /* nb_divmod */
2249 (ternaryfunc) mpw_pow, /* nb_power */
2250 (unaryfunc) mpw_neg, /* nb_negative */
2251 (unaryfunc) mpw_pos, /* nb_positive */
2252 (unaryfunc) mpw_abs, /* nb_absolute */
2253 (inquiry) mpw_nonzero, /* nb_nonzero */
2254 (unaryfunc) mpw_invert, /* nb_invert */
2255 (binaryfunc) mpw_lshift, /* nb_lshift */
2256 (binaryfunc) mpw_rshift, /* nb_rshift */
2257 (binaryfunc) mpw_and, /* nb_and */
2258 (binaryfunc) mpw_xor, /* nb_xor */
2259 (binaryfunc) mpw_or, /* nb_or */
2260 (coercion) mpw_coerce, /* nb_coerce */
2261
2262 (unaryfunc) mpw_int, /* nb_int */
2263 (unaryfunc) mpw_long, /* nb_long */
2264 (unaryfunc) mpw_float, /* nb_float */
2265 (unaryfunc) mpw_oct, /* nb_oct */
2266 (unaryfunc) mpw_hex, /* nb_hex */
2267
2268 /* Added in release 2.0 */
2269 (binaryfunc) 0, /* nb_inplace_add */
2270 (binaryfunc) 0, /* nb_inplace_subtract */
2271 (binaryfunc) 0, /* nb_inplace_multiply */
2272 (binaryfunc) 0, /* nb_inplace_divide */
2273 (binaryfunc) 0, /* nb_inplace_remainder */
2274 (ternaryfunc)0, /* nb_inplace_power */
2275 (binaryfunc) 0, /* nb_inplace_lshift */
2276 (binaryfunc) 0, /* nb_inplace_rshift */
2277 (binaryfunc) 0, /* nb_inplace_and */
2278 (binaryfunc) 0, /* nb_inplace_xor */
2279 (binaryfunc) 0, /* nb_inplace_or */
2280
2281 /* Added in release 2.2 */
2282 /* The following require the Py_TPFLAGS_HAVE_CLASS flag */
2283 (binaryfunc) mpw_div, /* nb_floor_divide */
2284 (binaryfunc) 0, /* nb_true_divide */
2285 (binaryfunc) 0, /* nb_inplace_floor_divide */
2286 (binaryfunc) 0 /* nb_inplace_true_divide */
2287
2288 };
2289
2290 /* ---------- */
2291
2292 /**
2293 */
2294 /*@unchecked@*/ /*@observer@*/
2295 static char mpw_doc[] =
2296 "";
2297
2298 /*@-fullinitblock@*/
2299 PyTypeObject mpw_Type = {
2300 PyObject_HEAD_INIT(&PyType_Type)
2301 0, /* ob_size */
2302 "_bc.mpw", /* tp_name */
2303 sizeof(mpwObject) - sizeof(mpw),/* tp_basicsize */
2304 sizeof(mpw), /* tp_itemsize */
2305 /* methods */
2306 (destructor) mpw_dealloc, /* tp_dealloc */
2307 0, /* tp_print */
2308 0, /* tp_getattr */
2309 0, /* tp_setattr */
2310 (cmpfunc) mpw_compare, /* tp_compare */
2311 (reprfunc) mpw_repr, /* tp_repr */
2312 &mpw_as_number, /* tp_as_number */
2313 0, /* tp_as_sequence */
2314 0, /* tp_as_mapping */
2315 (hashfunc)0, /* tp_hash */
2316 0, /* tp_call */
2317 (reprfunc) mpw_str, /* tp_str */
2318 (getattrofunc) mpw_getattro, /* tp_getattro */
2319 (setattrofunc) mpw_setattro, /* tp_setattro */
2320 0, /* tp_as_buffer */
2321 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
2322 Py_TPFLAGS_BASETYPE, /* tp_flags */
2323 mpw_doc, /* tp_doc */
2324 0, /* tp_traverse */
2325 0, /* tp_clear */
2326 0, /* tp_richcompare */
2327 0, /* tp_weaklistoffset */
2328 0, /* tp_iter */
2329 0, /* tp_iternext */
2330 mpw_methods, /* tp_methods */
2331 0, /* tp_members */
2332 0, /* tp_getset */
2333 0, /* tp_base */
2334 0, /* tp_dict */
2335 0, /* tp_descr_get */
2336 0, /* tp_descr_set */
2337 0, /* tp_dictoffset */
2338 0, /* tp_init */
2339 0, /* tp_alloc */
2340 (newfunc) mpw_new, /* tp_new */
2341 (destructor) mpw_free, /* tp_free */
2342 0, /* tp_is_gc */
2343 };
2344 /*@=fullinitblock@*/
2345
2346 /* ---------- */
2347