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