1 /*
2 * bignum.c
3 * GlowWorm
4 *
5 * Created by Curtis Jones on 2006.06.28.
6 * Copyright 2006 __MyCompanyName__. All rights reserved.
7 *
8 */
9
10 #include "bignum.h"
11
12 extern void bzero (void *, size_t);
13 extern void * memcpy (void *, const void *, size_t);
14 extern int printf(const char *, ...);
15 extern int snprintf(char *, size_t, const char *, ...);
16
17 char * BIGNUM_BASE_CHAR = "0123456789abcdefghijklmnopqrstuvwxyz";
18
19 static bignum_t * BIGNUM_ZERO;
20 static bignum_t * BIGNUM_ONE;
21 static bignum_t * BIGNUM_TWO;
22 static bignum_t * BIGNUM_THREE;
23 static bignum_t * BIGNUM_FOUR;
24 static bignum_t * BIGNUM_FIVE;
25 static bignum_t * BIGNUM_SIX;
26 static bignum_t * BIGNUM_SEVEN;
27 static bignum_t * BIGNUM_EIGHT;
28 static bignum_t * BIGNUM_NINE;
29 static bignum_t * BIGNUM_TEN;
30 static bignum_t * BIGNUM_ELEVEN;
31 static bignum_t * BIGNUM_TWELVE;
32 static bignum_t * BIGNUM_THIRTEEN;
33 static bignum_t * BIGNUM_FOURTEEN;
34 static bignum_t * BIGNUM_FIFTEEN;
35 static bignum_t * BIGNUM_SIXTEEN;
36 static bignum_t * BIGNUM_SEVENTEEN;
37 static bignum_t * BIGNUM_EIGHTEEN;
38 static bignum_t * BIGNUM_NINETEEN;
39 static bignum_t * BIGNUM_TWENTY;
40 static bignum_t * BIGNUM_THIRTY_TWO;
41 static bignum_t * BIGNUM_ONE_HUNDRED;
42
43
44
45
46
47 inline bignum_t * bignum_zero () { return BIGNUM_ZERO; }
48 inline bignum_t * bignum_one () { return BIGNUM_ONE; }
49 inline bignum_t * bignum_two () { return BIGNUM_TWO; }
50 inline bignum_t * bignum_three () { return BIGNUM_THREE; }
51 inline bignum_t * bignum_four () { return BIGNUM_FOUR; }
52 inline bignum_t * bignum_five () { return BIGNUM_FIVE; }
53 inline bignum_t * bignum_six () { return BIGNUM_SIX; }
54 inline bignum_t * bignum_seven () { return BIGNUM_SEVEN; }
55 inline bignum_t * bignum_eight () { return BIGNUM_EIGHT; }
56 inline bignum_t * bignum_nine () { return BIGNUM_NINE; }
57 inline bignum_t * bignum_ten () { return BIGNUM_TEN; }
58 inline bignum_t * bignum_eleven () { return BIGNUM_ELEVEN; }
59 inline bignum_t * bignum_twelve () { return BIGNUM_TWELVE; }
60 inline bignum_t * bignum_thirteen () { return BIGNUM_THIRTEEN; }
61 inline bignum_t * bignum_fourteen () { return BIGNUM_FOURTEEN; }
62 inline bignum_t * bignum_fifteen () { return BIGNUM_FIFTEEN; }
63 inline bignum_t * bignum_sixteen () { return BIGNUM_SIXTEEN; }
64 inline bignum_t * bignum_seventeen () { return BIGNUM_SEVENTEEN; }
65 inline bignum_t * bignum_eighteen () { return BIGNUM_EIGHTEEN; }
66 inline bignum_t * bignum_nineteen () { return BIGNUM_NINETEEN; }
67 inline bignum_t * bignum_twenty () { return BIGNUM_TWENTY; }
68 inline bignum_t * bignum_thirty_two () { return BIGNUM_THIRTY_TWO; }
69 inline bignum_t * bignum_one_hundred () { return BIGNUM_ONE_HUNDRED; }
70
71 /**
72 * Allocates and returns a new bignum_t instance. It is initially set to
73 * positive zero.
74 *
75 */
76 bignum_t *
77 bignum_alloc ()
78 {
79 bignum_t * num = (bignum_t *)malloc(sizeof(bignum_t));
80
81 BIGNUM_BASE_TYPE base = 0;
82
83 bzero(num, sizeof(bignum_t));
84
85 num->sign = BIGNUM_POSITIVE;
86 num->oofm = 0;
87 num->sofb = sizeof(BIGNUM_BASE_TYPE);
88 num->size = 10;
89 num->base = (u_int64_t)(base - 1) + 1;
90
91 num->numb = (BIGNUM_BASE_TYPE *)malloc(10 * num->sofb);
92
93 return num;
94 }
95
96 /**
97 * Frees num along with any memory num had previously allocated.
98 *
99 */
100 void
101 bignum_free (bignum_t *num)
102 {
103 if (num != NULL) {
104 if (num->numb != NULL)
105 free( num->numb );
106
107 free( num );
108 }
109 }
110
111 /**
112 *
113 *
114 */
115 void
116 bignum_init ()
117 {
118 BIGNUM_ZERO = bignum_alloc(); bignum_set(BIGNUM_ZERO, 0);
119 BIGNUM_ONE = bignum_alloc(); bignum_set(BIGNUM_ONE, 1);
120 BIGNUM_TWO = bignum_alloc(); bignum_set(BIGNUM_TWO, 2);
121 BIGNUM_THREE = bignum_alloc(); bignum_set(BIGNUM_THREE, 3);
122 BIGNUM_FOUR = bignum_alloc(); bignum_set(BIGNUM_FOUR, 4);
123 BIGNUM_FIVE = bignum_alloc(); bignum_set(BIGNUM_FIVE, 5);
124 BIGNUM_SIX = bignum_alloc(); bignum_set(BIGNUM_SIX, 6);
125 BIGNUM_SEVEN = bignum_alloc(); bignum_set(BIGNUM_SEVEN, 7);
126 BIGNUM_EIGHT = bignum_alloc(); bignum_set(BIGNUM_EIGHT, 8);
127 BIGNUM_NINE = bignum_alloc(); bignum_set(BIGNUM_NINE, 9);
128 BIGNUM_TEN = bignum_alloc(); bignum_set(BIGNUM_TEN, 10);
129 BIGNUM_ELEVEN = bignum_alloc(); bignum_set(BIGNUM_ELEVEN, 11);
130 BIGNUM_TWELVE = bignum_alloc(); bignum_set(BIGNUM_TWELVE, 12);
131 BIGNUM_THIRTEEN = bignum_alloc(); bignum_set(BIGNUM_THIRTEEN, 13);
132 BIGNUM_FOURTEEN = bignum_alloc(); bignum_set(BIGNUM_FOURTEEN, 14);
133 BIGNUM_FIFTEEN = bignum_alloc(); bignum_set(BIGNUM_FIFTEEN, 15);
134 BIGNUM_SIXTEEN = bignum_alloc(); bignum_set(BIGNUM_SIXTEEN, 16);
135 BIGNUM_SEVENTEEN = bignum_alloc(); bignum_set(BIGNUM_SEVENTEEN, 17);
136 BIGNUM_EIGHTEEN = bignum_alloc(); bignum_set(BIGNUM_EIGHTEEN, 18);
137 BIGNUM_NINETEEN = bignum_alloc(); bignum_set(BIGNUM_NINETEEN, 19);
138 BIGNUM_TWENTY = bignum_alloc(); bignum_set(BIGNUM_TWENTY, 20);
139 BIGNUM_THIRTY_TWO = bignum_alloc(); bignum_set(BIGNUM_THIRTY_TWO, 32);
140 BIGNUM_ONE_HUNDRED = bignum_alloc(); bignum_set(BIGNUM_ONE_HUNDRED, 100);
141 }
142
143 /**
144 * Prints a base 16 representation of num.
145 *
146 */
147 void
148 bignum_print (bignum_t *num)
149 {
150 u_int64_t i = 0;
151 u_int64_t n = num->oofm;
152
153 printf("bignum={sign=%d, oofm=%llu, size=%llu, numb=0x",
154 num->sign, num->oofm, num->size);
155
156 if (n > 0) {
157 for (i = n-1; i >= 0 && i < n; --i)
158 #if defined(BIGNUM_SOFB_08)
159 printf("%02hhX ", num->numb[i]);
160 #elif defined(BIGNUM_SOFB_16)
161 printf("%04hX ", num->numb[i]);
162 #elif defined(BIGNUM_SOFB_32)
163 printf("%08lX ", num->numb[i]);
164 #elif defined(BIGNUM_SOFB_64)
165 printf("%016llX ", num->numb[i]);
166 #endif
167 }
168 else
169 printf("0");
170
171 printf("}\n");
172 }
173
174 /**
175 * Converts num to base 16 and puts that value into str. If len is insufficient
176 * the value is truncated. Returns the total number of characters in the
177 * resulting string.
178 *
179 */
180 int
181 bignum_cstr (bignum_t *num, int len, char *str)
182 {
183 u_int64_t i = 0;
184 u_int64_t n = num->oofm;
185 int pnt = 0;
186
187 pnt += snprintf(str, len, "0x");
188
189 if (n > 0) {
190 for (i = n-1; i >= 0 && i < n; --i)
191 #if defined(BIGNUM_SOFB_08)
192 pnt += snprintf(str+pnt, len-pnt, "%02hhX ", num->numb[i]);
193 #elif defined(BIGNUM_SOFB_16)
194 pnt += snprintf(str+pnt, len-pnt, "%04hX ", num->numb[i]);
195 #elif defined(BIGNUM_SOFB_32)
196 pnt += snprintf(str+pnt, len-pnt, "%08lX ", num->numb[i]);
197 #elif defined(BIGNUM_SOFB_64)
198 pnt += snprintf(str+pnt, len-pnt, "%016llX ", num->numb[i]);
199 #endif
200 }
201 else
202 pnt += snprintf(str+pnt, len-pnt, "0 ");
203
204 return pnt;
205 }
206
207 /**
208 * Don't forget to free the returned char*.
209 *
210 */
211 char *
212 bignum_cstr_base2 (bignum_t *num, int precision, int base)
213 {
214 char * str;
215
216 if (NULL == (str = (char *)malloc(precision+1)))
217 return NULL;
218
219 bignum_cstr_base(num, precision, str, base);
220
221 return str;
222 }
223
224 /**
225 * Converts num into the specified base and puts that value into str. If
226 * str_len is less than the necessary length to hold the new number, then
227 * scientific notation is used. Returns the total number of digits that the
228 * converted number *should* be represented by if str_len allows for it.
229 *
230 * The efficiency of this could be improved by allocating an additional buffer
231 * to use as a temporary storage space and then just memmove()
232 */
233 int
234 bignum_cstr_base (bignum_t *num, int str_len, char *str, int base)
235 {
236 if (base < 2)
237 return -1;
238
239 if (base > 36)
240 return -2;
241
242 int str_pos = 0;
243 char * str_ptr = str + (str_len - 2);
244
245 bignum_t * num_base = bignum_alloc(); // target base
246 bignum_t * num_tmp1 = bignum_alloc(); // quotient from division operation
247 bignum_t * num_tmp2 = bignum_alloc(); // remainder from division operation
248 bignum_t * num_tmp3 = bignum_alloc(); // working copy of num
249 bignum_t * num_tmp4 = NULL; // used for swapping tmp1 and tmp3
250
251 bignum_set(num_base, base);
252 bignum_set_bn(num_tmp3, num);
253
254 // if the number in zero, then the result is the same for all bases, so just
255 // set it and return.
256 //
257 if (bignum_iszero(num)) {
258 str[0] = '0';
259 str[1] = '\0';
260 return 1;
261 }
262
263 // divide the given number by the given radix. the quotient of each such
264 // division operation represents the next largest magnitude of the base
265 // converted value. stop when we hit zero.
266 //
267 while (!bignum_iszero(num_tmp3))
268 {
269 bignum_div(num_tmp1, num_tmp2, num_tmp3, num_base);
270
271 *(str_ptr-((str_pos++)%(str_len-1))) = BIGNUM_BASE_CHAR[__bignum_get(num_tmp2,0)];
272
273 num_tmp4 = num_tmp3;
274 num_tmp3 = num_tmp1;
275 num_tmp1 = num_tmp4;
276 }
277
278 // set the terminating binary zero at the end of the string.
279 //
280 *(str_ptr+1) = '\0';
281
282 // if the resulting string is less than the size of the string buffer we were
283 // given, then shift the string to the front of the buffer and set a
284 // terminating zero after it.
285 //
286 if (str_pos < str_len - 1) {
287 memmove(str, str+(str_len-str_pos-1), str_pos);
288 *(str+str_pos) = '\0';
289 }
290
291 // if the resulting string is greater than the size of the string buffer we
292 // were given, then we need to shift the numbers around so that they start at
293 // the top of the string buffer.
294 //
295 // the method used here involves a read position and a write position. the
296 // read position is set at the point where the last (ie, highest order of
297 // magnitude) value was written, and the write position is set to the start
298 // of the same buffer.
299 //
300 // digit values are swapped, amounting to no more than one swap per digit in
301 // the string and possibly fewer.
302 //
303 // this process is complicated a little bit by the need to insert a decimal
304 // point after the first digit because we need to express the value in
305 // scientific notation. this is accomplished by manually setting the the
306 // first digit and the following decimal point and setting the read position
307 // to minus-one the position of the highest order of magintude value (which,
308 // of course, is the position of the lowest order of magnitude value), which
309 // is where the second digit in the un-altered string - which would have been
310 // over-written by the decimal point - is stored.
311 //
312 // finally, there is special case handling for situations where no shifting
313 // is required or the digits only need to be shifted once.
314 //
315 else if (str_pos > str_len - 1)
316 {
317 char tmp;
318 char expo[10];
319 int read = ((str_len-1) - (str_pos % (str_len-1))) - 1;
320 int write = 0;
321 int elen = 0;
322
323 elen = snprintf(expo, 10, "x10^%d", str_pos-1);
324
325 // if the digits are already in the correct oreientation, then we just need
326 // to insert the decimal point after shifting down all but the first digit.
327 //
328 if (read == -1 || read == str_len - 2) {
329 memmove(str+2, str+1, str_len-3);
330 *(str+1) = '.';
331 }
332
333 // if the digits are shifted by one, then "manually" set the first digit
334 // and the decimal point and we're done.
335 //
336 else if (read == 0) {
337 *(str+0) = *(str+1);
338 *(str+1) = '.';
339 }
340
341 // some arbitrary amount of shifting needs to take place and room needs to
342 // be made for the decimal point. this'll do all of that. and more!
343 //
344 else {
345 *(str+(read++)) = *(str+write);
346 *(str+(write++)) = *(str+read);
347 *(str+(read++)) = *(str+write);
348 *(str+(write++)) = '.';
349
350 while (1) {
351 if (read >= str_len-1) {
352 read = ((str_len-1) - (str_pos % (str_len-1))) - 1;
353
354 if (read <= write)
355 break;
356 }
357
358 // if the write position is now over-lapping with the scientific
359 // notation portion of the string, then there's no point in continuing.
360 //
361 if (write >= str_len - elen)
362 break;
363
364 tmp = *(str+write);
365 *(str+write) = *(str+read);
366 *(str+read) = tmp;
367
368 read++;
369 write++;
370 }
371 }
372
373 // copy the scientific notation text onto the end of the string.
374 //
375 memcpy(str+(str_len-(elen+1)), expo, elen);
376 }
377
378 bignum_free(num_base);
379 bignum_free(num_tmp1);
380 bignum_free(num_tmp2);
381 bignum_free(num_tmp3);
382
383 return str_pos;
384 }
385
386 /**
387 * Converts num into the specified base and puts that value into str. If
388 * str_len is less than the necessary length to hold the new number, then
389 * scientific notation is used. Returns the total number of digits that the
390 * converted number *should* be represented by if str_len allows for it.
391 *
392 * Same as bignum_cstr_base, but incurs additional memory overhead for the
393 * sake of speed.
394 *
395 */
396 /*
397 int
398 bignum_cstr_base_fast (bignum_t *num, int str_len, char *str, int base)
399 {
400 if (base < 2)
401 return -1;
402
403 if (base > 36)
404 return -2;
405
406 int str_pos = 0;
407 char * str_ptr = str + (str_len - 2);
408
409 bignum_t * num_base = bignum_alloc(); // target base
410 bignum_t * num_tmp1 = bignum_alloc(); // quotient from division operation
411 bignum_t * num_tmp2 = bignum_alloc(); // remainder from division operation
412 bignum_t * num_tmp3 = bignum_alloc(); // working copy of num
413 bignum_t * num_tmp4 = NULL; // used for swapping tmp1 and tmp3
414
415 bignum_set(num_base, base);
416 bignum_set_bn(num_tmp3, num);
417
418 // if the number in zero, then the result is the same for all bases, so just
419 // set it and return.
420 //
421 if (bignum_iszero(num)) {
422 str[0] = '0';
423 str[1] = '\0';
424 return 1;
425 }
426
427 // divide the given number by the given radix. the quotient of each such
428 // division operation represents the next largest magnitude of the base
429 // converted value. stop when we hit zero.
430 //
431 while (!bignum_iszero(num_tmp3))
432 {
433 bignum_div(num_tmp1, num_tmp2, num_tmp3, num_base);
434
435 *(str_ptr-((str_pos++)%(str_len-1))) = BIGNUM_BASE_CHAR[__bignum_get(num_tmp2,0)];
436
437 num_tmp4 = num_tmp3;
438 num_tmp3 = num_tmp1;
439 num_tmp1 = num_tmp4;
440 }
441
442 // set the terminating binary zero at the end of the string.
443 //
444 *(str_ptr+1) = '\0';
445
446 // if the resulting string is less than the size of the string buffer we were
447 // given, then shift the string to the front of the buffer and set a
448 // terminating zero after it.
449 //
450 if (str_pos < str_len - 1) {
451 memmove(str, str+(str_len-str_pos-1), str_pos);
452 *(str+str_pos) = '\0';
453 }
454
455 // if the resulting string is greater than the size of the string buffer we
456 // were given, then we need to shift the numbers around so that they start at
457 // the top of the string buffer.
458 //
459 // the method used here involves a read position and a write position. the
460 // read position is set at the point where the last (ie, highest order of
461 // magnitude) value was written, and the write position is set to the start
462 // of the same buffer.
463 //
464 // digit values are swapped, amounting to no more than one swap per digit in
465 // the string and possibly fewer.
466 //
467 // this process is complicated a little bit by the need to insert a decimal
468 // point after the first digit because we need to express the value in
469 // scientific notation. this is accomplished by manually setting the the
470 // first digit and the following decimal point and setting the read position
471 // to minus-one the position of the highest order of magintude value (which,
472 // of course, is the position of the lowest order of magnitude value), which
473 // is where the second digit in the un-altered string - which would have been
474 // over-written by the decimal point - is stored.
475 //
476 // finally, there is special case handling for situations where no shifting
477 // is required or the digits only need to be shifted once.
478 //
479 else if (str_pos > str_len - 1)
480 {
481 char tmp;
482 char expo[10];
483 int read = ((str_len-1) - (str_pos % (str_len-1))) - 1;
484 int write = 0;
485 int elen = 0;
486
487 elen = snprintf(expo, 10, "x10^%d", str_pos-1);
488
489 // if the digits are already in the correct oreientation, then we just need
490 // to insert the decimal point after shifting down all but the first digit.
491 //
492 if (read == -1 || read == str_len - 2) {
493 memmove(str+2, str+1, str_len-3);
494 *(str+1) = '.';
495 }
496
497 // if the digits are shifted by one, then "manually" set the first digit
498 // and the decimal point and we're done.
499 //
500 else if (read == 0) {
501 *(str+0) = *(str+1);
502 *(str+1) = '.';
503 }
504
505 // some arbitrary amount of shifting needs to take place and room needs to
506 // be made for the decimal point. this'll do all of that. and more!
507 //
508 else {
509 char * buf;
510
511 if (NULL == (buf = malloc(strlen)))
512 return -1;
513
514 memcpy(buf, str+read, strlen);
515
516 *(str+(read++)) = *(str+write);
517 *(str+(write++)) = *(str+read);
518 *(str+(read++)) = *(str+write);
519 *(str+(write++)) = '.';
520
521 while (1) {
522 if (read >= str_len-1) {
523 read = ((str_len-1) - (str_pos % (str_len-1))) - 1;
524
525 if (read <= write)
526 break;
527 }
528
529 // if the write position is now over-lapping with the scientific
530 // notation portion of the string, then there's no point in continuing.
531 //
532 if (write >= str_len - elen)
533 break;
534
535 tmp = *(str+write);
536 *(str+write) = *(str+read);
537 *(str+read) = tmp;
538
539 read++;
540 write++;
541 }
542 }
543
544 // copy the scientific notation text onto the end of the string.
545 //
546 memcpy(str+(str_len-(elen+1)), expo, elen);
547 }
548
549 bignum_free(num_base);
550 bignum_free(num_tmp1);
551 bignum_free(num_tmp2);
552 bignum_free(num_tmp3);
553
554 return str_pos;
555 }
556 */
557
558 /**
559 * Sets the value of num to the value contained in buf. Returns an instance
560 * of num.
561 *
562 */
563 bignum_t *
564 bignum_setbytes (bignum_t *num, unsigned char *buf, int len)
565 {
566 int i = 0;
567 u_int64_t pos = 0;
568 BIGNUM_BASE_TYPE val = 0;
569
570 __bignum_zero(num);
571
572 for (i = 0; i <= len - 4; i+=4) {
573 val = 0;
574 val |= (((BIGNUM_BASE_TYPE)buf[len-(i+4)]) << 24);
575 val |= (((BIGNUM_BASE_TYPE)buf[len-(i+3)]) << 16);
576 val |= (((BIGNUM_BASE_TYPE)buf[len-(i+2)]) << 8);
577 val |= (((BIGNUM_BASE_TYPE)buf[len-(i+1)]) );
578
579 __bignum_set(num, pos++, val);
580 }
581
582 if (len - i == 3) {
583 val = 0;
584 val |= (((BIGNUM_BASE_TYPE)buf[len-(i+3)]) << 16);
585 val |= (((BIGNUM_BASE_TYPE)buf[len-(i+2)]) << 8);
586 val |= (((BIGNUM_BASE_TYPE)buf[len-(i+1)]) );
587
588 __bignum_set(num, pos++, val);
589 }
590 else if (len - i == 2) {
591 val = 0;
592 val |= (((BIGNUM_BASE_TYPE)buf[len-(i+2)]) << 8);
593 val |= (((BIGNUM_BASE_TYPE)buf[len-(i+1)]) );
594
595 __bignum_set(num, pos++, val);
596 }
597 else if (len - i == 1) {
598 val = 0;
599 val |= (((BIGNUM_BASE_TYPE)buf[len-(i+1)]) );
600
601 __bignum_set(num, pos++, val);
602 }
603
604 num->oofm = pos;
605
606 return num;
607 }
608
609 /**
610 * Copies the value of num into buf. Returns buf.
611 *
612 */
613 unsigned char *
614 bignum_getbytes (bignum_t *num, unsigned char *buf)
615 {
616 u_int64_t i=1, j=0, oofm=num->oofm;
617
618 if (oofm == 0) {
619 *buf = '\0';
620 return buf;
621 }
622
623 if (num->numb[oofm-1] > 0x00FF0000ull) {
624 buf[j++] = (num->numb[oofm-1] >> 24) & 0xFF;
625 buf[j++] = (num->numb[oofm-1] >> 16) & 0xFF;
626 buf[j++] = (num->numb[oofm-1] >> 8) & 0xFF;
627 buf[j++] = (num->numb[oofm-1] ) & 0xFF;
628 }
629 else if (num->numb[oofm-1] > 0x0000FF00ull) {
630 buf[j++] = (num->numb[oofm-1] >> 16) & 0xFF;
631 buf[j++] = (num->numb[oofm-1] >> 8) & 0xFF;
632 buf[j++] = (num->numb[oofm-1] ) & 0xFF;
633 }
634 else if (num->numb[oofm-1] > 0x000000FFull) {
635 buf[j++] = (num->numb[oofm-1] >> 8) & 0xFF;
636 buf[j++] = (num->numb[oofm-1] ) & 0xFF;
637 }
638 else
639 buf[j++] = (num->numb[oofm-1] ) & 0xFF;
640
641 for (oofm -= 2; i < num->oofm; ++i, oofm--) {
642 buf[j++] = (num->numb[oofm] >> 24) & 0xFF;
643 buf[j++] = (num->numb[oofm] >> 16) & 0xFF;
644 buf[j++] = (num->numb[oofm] >> 8) & 0xFF;
645 buf[j++] = (num->numb[oofm] ) & 0xFF;
646 }
647
648 return buf;
649 }
650
651 /**
652 * Returns a u_int32_t representation of the bignum_t. If the bignum_t
653 * overflows the u_int32_t type, that data is discarded, so make sure you are
654 * aware of whether the bignum_t is going to fit into this data size.
655 *
656 */
657 u_int32_t
658 bignum_get_uint32 (bignum_t *num)
659 {
660 if (num == NULL)
661 return 0;
662
663 return num->numb[0];
664 }
665
666 /**
667 * Shifts the value of num by cnt.
668 *
669 */
670 bignum_t *
671 bignum_rshift (bignum_t *num, u_int64_t cnt)
672 {
673 u_int64_t i; // counter
674 u_int64_t bpmag = num->sofb * 8; // bits per magnitude
675 u_int64_t large = cnt / bpmag; //
676 u_int64_t small = cnt - (large * bpmag); //
677
678 for (i = 0; i < num->oofm - 1; ++i) {
679 num->numb[i] >>= small;
680 num->numb[i] |= (num->numb[i+1] << (bpmag - small));
681 }
682
683 num->numb[i] >>= small;
684
685 return num;
686 }
687
688 /**
689 * Sets the value of res to num right-shifted amt times. If res is null, a new
690 * bignum_t is allocated.
691 *
692 * Returns res, or the newly allocated res. Returns NULL if num or amt are
693 * null.
694 *
695 */
696 bignum_t *
697 bignum_rshift_multi (bignum_t *res, bignum_t *num, bignum_t *amt)
698 {
699 u_int32_t oofm_cnt = 0;
700 u_int32_t bits_cnt = 0;
701
702 if (num == NULL)
703 return NULL;
704
705 if (amt == NULL)
706 return NULL;
707
708 if (res == NULL)
709 if (NULL == (res = bignum_alloc()))
710 return NULL;
711
712 __bignum_zero(res);
713
714 // if amt is greater than num->oofm * 32 then
715 // set res = 0
716 //
717 //
718
719 // u_int64_t oofm = num->oofm *
720
721 // memset
722
723 // use memset for the "(int) oofm / 32" amount of the shift, and
724 // use >> for the "oofm % 32" amount of the shift
725
726 // determine the number of 32-bit orders-of-magnitude that we need to shift
727 // the value by, which can be accomplished with memset, and also determine
728 // the number of bits that need to be shifted, using >>.
729 {
730 bignum_t * shift_oofm_cnt = bignum_alloc();
731 bignum_t * shift_bits_cnt = bignum_alloc();
732
733 bignum_div(shift_oofm_cnt, shift_bits_cnt, amt, bignum_thirty_two());
734
735 oofm_cnt = bignum_get_uint32(shift_oofm_cnt);
736 bits_cnt = bignum_get_uint32(shift_bits_cnt);
737
738 bignum_free(shift_oofm_cnt);
739 bignum_free(shift_bits_cnt);
740 }
741
742
743
744 return res;
745 }
746
747 /**
748 * Returns 1 if the bit specified by bit is set and zero otherwise.
749 *
750 */
751 int
752 bignum_isbitset (bignum_t *num, u_int64_t bit)
753 {
754 u_int64_t bpmag = num->sofb * 8; // bits per magnitude
755 u_int64_t large = bit / bpmag; // magnitude
756 u_int64_t small = bit - (large * bpmag); // bit within magnitude
757
758 return (num->numb[large] >> (small - 1)) & 0x1;
759 }
760
761 /**
762 * Returns the lowest set bit of num or negative one if num is zero.
763 *
764 */
765 u_int64_t
766 bignum_lowest_set_bit (bignum_t *num)
767 {
768 u_int64_t i, j;
769 u_int64_t bpmag = num->sofb * 8;
770
771 for (i = 0; i < num->oofm; ++i) {
772 for (j = 0; j < bpmag; ++j) {
773 if ((num->numb[i] >> j) & 1)
774 return (i * bpmag) + j;
775 }
776 }
777
778 return -1;
779 }
780
781 /**
782 * Returns the number of bits in num.
783 *
784 */
785 u_int64_t
786 bignum_bitlen (bignum_t *num)
787 {
788 int i = 0;
789 u_int64_t bpmag = num->sofb * 8;
790
791 if (bignum_iszero(num))
792 return 0;
793
794 for (i = bpmag - 1; i >= 0; --i)
795 if ((num->numb[num->oofm-1] >> i) & 1)
796 return ((num->oofm-1) * bpmag) + (i+1);
797
798 return 0;
799 }
800
801 /**
802 * Returns the number of bytes in num.
803 *
804 */
805 u_int64_t
806 bignum_bytelen (bignum_t *num)
807 {
808 int bytes = 0;
809 BIGNUM_BASE_TYPE numb = num->numb[num->oofm - 1];
810
811 if (num->oofm == 0)
812 return 0;
813
814 else if (num->oofm > 1)
815 bytes = (num->oofm - 1) * num->sofb;
816
817 if ((numb >> 24) & 0xFF)
818 bytes += 4;
819 else if ((numb >> 16) & 0xFF)
820 bytes += 3;
821 else if ((numb >> 8) & 0xFF)
822 bytes += 2;
823 else if ((numb ) & 0xFF)
824 bytes += 1;
825
826 return bytes;
827 }
828
829
830
831
832
833 /**
834 * Returns the BIGNUM_BASE_TYPE of num at position pos.
835 *
836 */
837 inline BIGNUM_BASE_TYPE
838 __bignum_get (bignum_t *num, u_int64_t pos)
839 {
840 if (pos >= num->oofm)
841 return 0;
842
843 return *(num->numb+pos);
844 }
845
846 /**
847 * Sets the BIGNUM_BASE_TYPE of num at position pos to val.
848 *
849 */
850 inline void
851 __bignum_set (bignum_t *num, u_int64_t pos, BIGNUM_BASE_TYPE val)
852 {
853 if (pos >= BIGNUM_MAX_ORDERS)
854 return;
855
856 if (num->size <= pos)
857 __bignum_grow(num, pos+1);
858
859 if (num->size <= pos)
860 printf("%s().. failed to grow to %d\n", __PRETTY_FUNCTION__, (pos+1));
861 else
862 num->numb[pos] = val;
863 }
864
865 /**
866 * Increases the size of num to size orders of magnitude (BIGNUM_BASE_TYPE),
867 * if necessary. Does not shrink the size of num if it is greater than size.
868 *
869 */
870 void
871 __bignum_grow (bignum_t *num, u_int64_t size)
872 {
873 BIGNUM_BASE_TYPE * ptr = NULL;
874
875 if (size >= BIGNUM_MAX_ORDERS) {
876 printf("%s().. requested size of %llu exceeds max of %d\n", __PRETTY_FUNCTION__, size, BIGNUM_MAX_ORDERS);
877 return;
878 }
879
880 if (size < num->size)
881 return;
882
883 if (num->size * 2 >= size)
884 size = BIGNUM_MIN(num->size*2, BIGNUM_MAX_ORDERS);
885 else
886 size = BIGNUM_MIN(size*2, BIGNUM_MAX_ORDERS);
887
888 if (NULL == (ptr = (BIGNUM_BASE_TYPE *)realloc(num->numb, size * num->sofb))) {
889 printf("%s().. failed to realloc, %d\n", __PRETTY_FUNCTION__, errno);
890 return;
891 }
892
893 num->numb = ptr;
894 num->size = size;
895 }
896
897 /**
898 * Set the value of num to zero.
899 *
900 */
901 void
902 __bignum_zero (bignum_t *num)
903 {
904 bzero(num->numb, num->size * num->sofb);
905 num->oofm = 0;
906 num->sign = BIGNUM_POSITIVE;
907 }
908
909 /**
910 * Removes any trailing zeroes from num.
911 *
912 */
913 void
914 __bignum_trim (bignum_t *num)
915 {
916 u_int64_t i = 0;
917
918 for (i = num->oofm - 1; i < ((u_int64_t)0) - 1 && num->oofm > 0; --i) {
919 if (num->numb[i] != 0)
920 break;
921 else
922 num->oofm--;
923 }
924 }
syntax highlighted by Code2HTML, v. 0.9.1