Botan  1.11.15
src/lib/math/mp/mp_misc.cpp
Go to the documentation of this file.
00001 /*
00002 * MP Misc Functions
00003 * (C) 1999-2008 Jack Lloyd
00004 *
00005 * Botan is released under the Simplified BSD License (see license.txt)
00006 */
00007 
00008 #include <botan/internal/mp_core.h>
00009 #include <botan/internal/mp_madd.h>
00010 
00011 namespace Botan {
00012 
00013 extern "C" {
00014 
00015 /*
00016 * Compare two MP integers
00017 */
00018 s32bit bigint_cmp(const word x[], size_t x_size,
00019                   const word y[], size_t y_size)
00020    {
00021    if(x_size < y_size) { return (-bigint_cmp(y, y_size, x, x_size)); }
00022 
00023    while(x_size > y_size)
00024       {
00025       if(x[x_size-1])
00026          return 1;
00027       x_size--;
00028       }
00029 
00030    for(size_t i = x_size; i > 0; --i)
00031       {
00032       if(x[i-1] > y[i-1])
00033          return 1;
00034       if(x[i-1] < y[i-1])
00035          return -1;
00036       }
00037 
00038    return 0;
00039    }
00040 
00041 /*
00042 * Do a 2-word/1-word Division
00043 */
00044 word bigint_divop(word n1, word n0, word d)
00045    {
00046    word high = n1 % d, quotient = 0;
00047 
00048    for(size_t i = 0; i != MP_WORD_BITS; ++i)
00049       {
00050       word high_top_bit = (high & MP_WORD_TOP_BIT);
00051 
00052       high <<= 1;
00053       high |= (n0 >> (MP_WORD_BITS-1-i)) & 1;
00054       quotient <<= 1;
00055 
00056       if(high_top_bit || high >= d)
00057          {
00058          high -= d;
00059          quotient |= 1;
00060          }
00061       }
00062 
00063    return quotient;
00064    }
00065 
00066 /*
00067 * Do a 2-word/1-word Modulo
00068 */
00069 word bigint_modop(word n1, word n0, word d)
00070    {
00071    word z = bigint_divop(n1, n0, d);
00072    word dummy = 0;
00073    z = word_madd2(z, d, &dummy);
00074    return (n0-z);
00075    }
00076 
00077 }
00078 
00079 }