1 | //
|
2 | // JKBigInteger.m
|
3 | // JKBigInteger
|
4 | //
|
5 | // Created by Jānis Kiršteins on 5/21/13.
|
6 | // Copyright (c) 2013 Jānis Kiršteins. All rights reserved.
|
7 | //
|
8 |
|
9 | // Licensed under the MIT License
|
10 |
|
11 | #import "JKBigInteger.h"
|
12 |
|
13 | @implementation JKBigInteger {
|
14 | @private
|
15 | mp_int m_value;
|
16 | }
|
17 |
|
18 | + (BOOL)supportsSecureCoding {
|
19 | return YES;
|
20 | }
|
21 |
|
22 | - (id)initWithValue:(mp_int *)value {
|
23 |
|
24 | self = [super init];
|
25 |
|
26 | if (self) {
|
27 | mp_init_copy(&m_value, value);
|
28 | }
|
29 |
|
30 | return self;
|
31 | }
|
32 |
|
33 | - (mp_int *)value {
|
34 | return &m_value;
|
35 | }
|
36 |
|
37 | - (id)initWithUnsignedLong:(unsigned long)unsignedLong {
|
38 |
|
39 | self = [super init];
|
40 |
|
41 | if (self) {
|
42 | mp_set_int(&m_value, unsignedLong);
|
43 | }
|
44 |
|
45 | return self;
|
46 | }
|
47 |
|
48 | - (id)init {
|
49 | return [self initWithUnsignedLong:0];
|
50 | }
|
51 |
|
52 | - (id)initWithCString:(char *)cString andRadix:(int)radix {
|
53 |
|
54 | if (radix < 2 || radix > 64) {
|
55 | return nil;
|
56 | }
|
57 |
|
58 | self = [super init];
|
59 |
|
60 | if (self) {
|
61 | mp_init(&m_value);
|
62 | int result;
|
63 | result = mp_read_radix(&m_value, cString, radix);
|
64 |
|
65 | if (result != MP_OKAY) {
|
66 | mp_clear(&m_value);
|
67 | return nil;
|
68 | }
|
69 | }
|
70 |
|
71 | return self;
|
72 | }
|
73 | - (id)initWithCString:(char *)cString {
|
74 |
|
75 | int radix = 10;
|
76 | return [self initWithCString:cString andRadix:radix];
|
77 | }
|
78 |
|
79 | - (id)initWithString:(NSString *)string andRadix:(int)radix {
|
80 | return [self initWithCString:(char *)[string UTF8String] andRadix:radix];
|
81 | }
|
82 |
|
83 | - (id)initWithString:(NSString *)string {
|
84 |
|
85 | int radix = 10;
|
86 | return [self initWithCString:(char *)[string UTF8String] andRadix:radix];
|
87 | }
|
88 |
|
89 | - (id)initWithCoder:(NSCoder *)decoder {
|
90 |
|
91 | self = [super init];
|
92 |
|
93 | if (self) {
|
94 | int sign = [decoder decodeInt32ForKey:@"JKBigIntegerSign"];
|
95 | int alloc = [decoder decodeInt32ForKey:@"JKBigIntegerAlloc"];
|
96 |
|
97 | mp_init_size(&m_value, alloc);
|
98 |
|
99 | NSData *data = (NSData *)[decoder decodeObjectOfClass:[NSData class] forKey:@"JKBigIntegerDP"];
|
100 | mp_digit *temp = (mp_digit *)[data bytes];
|
101 |
|
102 | for (unsigned int i = 0; i < alloc; ++i) {
|
103 | m_value.dp[i] = temp[i];
|
104 | }
|
105 |
|
106 | m_value.used = alloc;
|
107 | m_value.sign = sign;
|
108 | }
|
109 |
|
110 | return self;
|
111 | }
|
112 | - (void)encodeWithCoder:(NSCoder *)encoder {
|
113 |
|
114 | mp_clamp(&m_value);
|
115 |
|
116 | NSData *data = [NSData dataWithBytes:(const void *)m_value.dp
|
117 | length:m_value.alloc * sizeof(mp_digit)];
|
118 |
|
119 | [encoder encodeObject:data forKey:@"JKBigIntegerDP"];
|
120 | [encoder encodeInteger:m_value.alloc forKey:@"JKBigIntegerAlloc"];
|
121 | [encoder encodeInteger:m_value.sign forKey:@"JKBigIntegerSign"];
|
122 | }
|
123 |
|
124 | - (id)add:(JKBigInteger *)bigInteger {
|
125 |
|
126 | mp_int sum;
|
127 | mp_init(&sum);
|
128 |
|
129 | mp_add(&m_value, [bigInteger value], &sum);
|
130 |
|
131 | id newBigInteger = [[JKBigInteger alloc] initWithValue:&sum];
|
132 | mp_clear(&sum);
|
133 |
|
134 | return newBigInteger;
|
135 | }
|
136 |
|
137 | - (id)subtract:(JKBigInteger *)bigInteger {
|
138 |
|
139 | mp_int difference;
|
140 | mp_init(&difference);
|
141 |
|
142 | mp_sub(&m_value, [bigInteger value], &difference);
|
143 |
|
144 | id newBigInteger = [[JKBigInteger alloc] initWithValue:&difference];
|
145 | mp_clear(&difference);
|
146 |
|
147 | return newBigInteger;
|
148 | }
|
149 |
|
150 | - (id)multiply:(JKBigInteger *)bigInteger {
|
151 |
|
152 | mp_int product;
|
153 | mp_init(&product);
|
154 |
|
155 | mp_mul(&m_value, [bigInteger value], &product);
|
156 |
|
157 | JKBigInteger *newBigInteger = [[JKBigInteger alloc] initWithValue:&product];
|
158 | mp_clear(&product);
|
159 |
|
160 | return newBigInteger;
|
161 | }
|
162 |
|
163 | - (id)divide:(JKBigInteger *)bigInteger {
|
164 |
|
165 | int result;
|
166 | mp_int quotient;
|
167 | mp_init("ient);
|
168 |
|
169 | result = mp_div(&m_value, [bigInteger value], "ient, NULL);
|
170 | if (result == MP_VAL) {
|
171 | mp_clear("ient);
|
172 | return nil;
|
173 | }
|
174 |
|
175 | JKBigInteger *newBigInteger = [[JKBigInteger alloc] initWithValue:"ient];
|
176 | mp_clear("ient);
|
177 |
|
178 | return newBigInteger;
|
179 | }
|
180 |
|
181 | - (id)remainder:(JKBigInteger *)bigInteger {
|
182 |
|
183 | int result;
|
184 | mp_int remainder;
|
185 | mp_init(&remainder);
|
186 |
|
187 | result = mp_div(&m_value, [bigInteger value], NULL, &remainder);
|
188 | if (result == MP_VAL) {
|
189 | mp_clear(&remainder);
|
190 | return nil;
|
191 | }
|
192 |
|
193 | JKBigInteger *newBigInteger = [[JKBigInteger alloc] initWithValue:&remainder];
|
194 | mp_clear(&remainder);
|
195 |
|
196 | return newBigInteger;
|
197 | }
|
198 |
|
199 | - (NSArray *)divideAndRemainder:(JKBigInteger *)bigInteger {
|
200 |
|
201 | int result;
|
202 | mp_int quotient, remainder;
|
203 | mp_init_multi("ient, &remainder, NULL);
|
204 |
|
205 | result = mp_div(&m_value, [bigInteger value], "ient, &remainder);
|
206 | if (result == MP_VAL) {
|
207 | mp_clear_multi("ient, &remainder, NULL);
|
208 | return nil;
|
209 | }
|
210 |
|
211 | JKBigInteger *quotientBigInteger = [[JKBigInteger alloc] initWithValue:"ient];
|
212 | JKBigInteger *remainderBigInteger = [[JKBigInteger alloc] initWithValue:&remainder];
|
213 | mp_clear_multi("ient, &remainder, NULL);
|
214 |
|
215 | return @[quotientBigInteger, remainderBigInteger];
|
216 | }
|
217 |
|
218 | - (id)pow:(unsigned int)exponent {
|
219 |
|
220 | int result;
|
221 | mp_int power;
|
222 | mp_init(&power);
|
223 |
|
224 | result = mp_expt_d(&m_value, (mp_digit)exponent, &power);
|
225 | if (result == MP_VAL) {
|
226 | mp_clear(&power);
|
227 | return nil;
|
228 | }
|
229 |
|
230 | JKBigInteger *newBigInteger = [[JKBigInteger alloc] initWithValue:&power];
|
231 | mp_clear(&power);
|
232 |
|
233 | return newBigInteger;
|
234 | }
|
235 |
|
236 | - (id)pow:(JKBigInteger*)exponent andMod: (JKBigInteger*)modulus {
|
237 |
|
238 | int result;
|
239 | mp_int output;
|
240 | mp_init(&output);
|
241 |
|
242 | result = mp_exptmod(&m_value, &exponent->m_value, &modulus->m_value, &output);
|
243 | if (result == MP_VAL) {
|
244 | mp_clear(&output);
|
245 | return nil;
|
246 | }
|
247 |
|
248 | JKBigInteger *newBigInteger = [[JKBigInteger alloc] initWithValue:&output];
|
249 | mp_clear(&output);
|
250 |
|
251 | return newBigInteger;
|
252 | }
|
253 |
|
254 | - (id)negate {
|
255 |
|
256 | mp_int negate;
|
257 | mp_init(&negate);
|
258 | mp_neg(&m_value, &negate);
|
259 |
|
260 | JKBigInteger *newBigInteger = [[JKBigInteger alloc] initWithValue:&negate];
|
261 | mp_clear(&negate);
|
262 |
|
263 | return newBigInteger;
|
264 | }
|
265 |
|
266 | - (id)abs {
|
267 |
|
268 | mp_int absolute;
|
269 | mp_init(&absolute);
|
270 | mp_abs(&m_value, &absolute);
|
271 |
|
272 | JKBigInteger *newBigInteger = [[JKBigInteger alloc] initWithValue:&absolute];
|
273 | mp_clear(&absolute);
|
274 |
|
275 | return newBigInteger;
|
276 | }
|
277 |
|
278 | - (id)bitwiseXor:(JKBigInteger *)bigInteger {
|
279 |
|
280 | mp_int xor;
|
281 | mp_init(&xor);
|
282 | mp_xor(&m_value, [bigInteger value], &xor);
|
283 |
|
284 | JKBigInteger *newBigInteger = [[JKBigInteger alloc] initWithValue:&xor];
|
285 | mp_clear(&xor);
|
286 |
|
287 | return newBigInteger;
|
288 | }
|
289 |
|
290 | - (id)bitwiseOr:(JKBigInteger *)bigInteger {
|
291 |
|
292 | mp_int or;
|
293 | mp_init(&or);
|
294 | mp_or(&m_value, [bigInteger value], &or);
|
295 |
|
296 | JKBigInteger *newBigInteger = [[JKBigInteger alloc] initWithValue:&or];
|
297 | mp_clear(&or);
|
298 |
|
299 | return newBigInteger;
|
300 | }
|
301 |
|
302 | - (id)bitwiseAnd:(JKBigInteger *)bigInteger {
|
303 |
|
304 | mp_int and;
|
305 | mp_init(&and);
|
306 | mp_and(&m_value, [bigInteger value], &and);
|
307 |
|
308 | JKBigInteger *newBigInteger = [[JKBigInteger alloc] initWithValue:&and];
|
309 | mp_clear(&and);
|
310 |
|
311 | return newBigInteger;
|
312 | }
|
313 |
|
314 | - (id)shiftLeft:(unsigned int)n {
|
315 |
|
316 | mp_int lShift;
|
317 | mp_init(&lShift);
|
318 | mp_mul_2d(&m_value, n, &lShift);
|
319 |
|
320 | JKBigInteger *newBigInteger = [[JKBigInteger alloc] initWithValue:&lShift];
|
321 | mp_clear(&lShift);
|
322 |
|
323 | return newBigInteger;
|
324 | }
|
325 |
|
326 | - (id)shiftRight:(unsigned int)n {
|
327 |
|
328 | mp_int rShift;
|
329 | mp_init(&rShift);
|
330 | mp_div_2d(&m_value, n, &rShift, NULL);
|
331 |
|
332 | JKBigInteger *newBigInteger = [[JKBigInteger alloc] initWithValue:&rShift];
|
333 | mp_clear(&rShift);
|
334 |
|
335 | return newBigInteger;
|
336 | }
|
337 | - (id)gcd:(JKBigInteger *)bigInteger {
|
338 |
|
339 | int result;
|
340 | mp_int gcd;
|
341 | mp_init(&gcd);
|
342 |
|
343 | result = mp_gcd(&m_value, [bigInteger value], &gcd);
|
344 | if (result == MP_VAL) {
|
345 | mp_clear(&gcd);
|
346 | return nil;
|
347 | }
|
348 |
|
349 | JKBigInteger *newBigInteger = [[JKBigInteger alloc] initWithValue:&gcd];
|
350 | mp_clear(&gcd);
|
351 |
|
352 | return newBigInteger;
|
353 | }
|
354 |
|
355 | - (NSComparisonResult) compare:(JKBigInteger *)bigInteger {
|
356 |
|
357 | NSComparisonResult comparisonResult;
|
358 | comparisonResult = mp_cmp([bigInteger value], &m_value);
|
359 |
|
360 | switch (comparisonResult) {
|
361 | case MP_GT:
|
362 | return NSOrderedAscending;
|
363 | case MP_EQ:
|
364 | return NSOrderedSame;
|
365 | case MP_LT:
|
366 | return NSOrderedDescending;
|
367 | default:
|
368 | return 0;
|
369 | }
|
370 | }
|
371 |
|
372 | - (unsigned long)unsignedIntValue {
|
373 | return mp_get_int(&m_value);
|
374 | }
|
375 |
|
376 | - (NSString *)stringValue {
|
377 |
|
378 | int radix = 10;
|
379 | return [self stringValueWithRadix:radix];
|
380 | }
|
381 |
|
382 | - (NSString *)stringValueWithRadix:(int)radix {
|
383 |
|
384 | int stringSize;
|
385 | mp_radix_size(&m_value, radix, &stringSize);
|
386 | char cString[stringSize];
|
387 | mp_toradix(&m_value, cString, radix);
|
388 |
|
389 | for (int i = 0; i < stringSize; ++i) {
|
390 | cString[i] = (char)tolower(cString[i]);
|
391 | }
|
392 |
|
393 | return [NSString stringWithUTF8String:cString];
|
394 | }
|
395 |
|
396 | - (NSString *)description {
|
397 | return [self stringValue];
|
398 | }
|
399 |
|
400 | - (void)dealloc {
|
401 | mp_clear(&m_value);
|
402 | }
|
403 |
|
404 |
|
405 | - (unsigned int)countBytes {
|
406 | return (unsigned int) mp_unsigned_bin_size(&m_value);
|
407 | }
|
408 |
|
409 |
|
410 | - (void)toByteArraySigned: (unsigned char*) byteArray {
|
411 | mp_to_signed_bin(&m_value, byteArray);
|
412 | }
|
413 |
|
414 |
|
415 | - (void)toByteArrayUnsigned: (unsigned char*) byteArray {
|
416 | mp_to_unsigned_bin(&m_value, byteArray);
|
417 | }
|
418 |
|
419 | @end
|