Botan  1.11.15
src/lib/math/mp/mp_shift.cpp
Go to the documentation of this file.
00001 /*
00002 * MP Shift Algorithms
00003 * (C) 1999-2007,2014 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/mem_ops.h>
00010 
00011 namespace Botan {
00012 
00013 extern "C" {
00014 
00015 /*
00016 * Single Operand Left Shift
00017 */
00018 void bigint_shl1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
00019    {
00020    if(word_shift)
00021       {
00022       copy_mem(x + word_shift, x, x_size);
00023       clear_mem(x, word_shift);
00024       }
00025 
00026    if(bit_shift)
00027       {
00028       word carry = 0;
00029       for(size_t j = word_shift; j != x_size + word_shift + 1; ++j)
00030          {
00031          word temp = x[j];
00032          x[j] = (temp << bit_shift) | carry;
00033          carry = (temp >> (MP_WORD_BITS - bit_shift));
00034          }
00035       }
00036    }
00037 
00038 /*
00039 * Single Operand Right Shift
00040 */
00041 void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
00042    {
00043    if(x_size < word_shift)
00044       {
00045       clear_mem(x, x_size);
00046       return;
00047       }
00048 
00049    if(word_shift)
00050       {
00051       copy_mem(x, x + word_shift, x_size - word_shift);
00052       clear_mem(x + x_size - word_shift, word_shift);
00053       }
00054 
00055    if(bit_shift)
00056       {
00057       word carry = 0;
00058 
00059       size_t top = x_size - word_shift;
00060 
00061       while(top >= 4)
00062          {
00063          word w = x[top-1];
00064          x[top-1] = (w >> bit_shift) | carry;
00065          carry = (w << (MP_WORD_BITS - bit_shift));
00066 
00067          w = x[top-2];
00068          x[top-2] = (w >> bit_shift) | carry;
00069          carry = (w << (MP_WORD_BITS - bit_shift));
00070 
00071          w = x[top-3];
00072          x[top-3] = (w >> bit_shift) | carry;
00073          carry = (w << (MP_WORD_BITS - bit_shift));
00074 
00075          w = x[top-4];
00076          x[top-4] = (w >> bit_shift) | carry;
00077          carry = (w << (MP_WORD_BITS - bit_shift));
00078 
00079          top -= 4;
00080          }
00081 
00082       while(top)
00083          {
00084          word w = x[top-1];
00085          x[top-1] = (w >> bit_shift) | carry;
00086          carry = (w << (MP_WORD_BITS - bit_shift));
00087 
00088          top--;
00089          }
00090       }
00091    }
00092 
00093 /*
00094 * Two Operand Left Shift
00095 */
00096 void bigint_shl2(word y[], const word x[], size_t x_size,
00097                  size_t word_shift, size_t bit_shift)
00098    {
00099    for(size_t j = 0; j != x_size; ++j)
00100       y[j + word_shift] = x[j];
00101    if(bit_shift)
00102       {
00103       word carry = 0;
00104       for(size_t j = word_shift; j != x_size + word_shift + 1; ++j)
00105          {
00106          word w = y[j];
00107          y[j] = (w << bit_shift) | carry;
00108          carry = (w >> (MP_WORD_BITS - bit_shift));
00109          }
00110       }
00111    }
00112 
00113 /*
00114 * Two Operand Right Shift
00115 */
00116 void bigint_shr2(word y[], const word x[], size_t x_size,
00117                  size_t word_shift, size_t bit_shift)
00118    {
00119    if(x_size < word_shift) return;
00120 
00121    for(size_t j = 0; j != x_size - word_shift; ++j)
00122       y[j] = x[j + word_shift];
00123    if(bit_shift)
00124       {
00125       word carry = 0;
00126       for(size_t j = x_size - word_shift; j > 0; --j)
00127          {
00128          word w = y[j-1];
00129          y[j-1] = (w >> bit_shift) | carry;
00130          carry = (w << (MP_WORD_BITS - bit_shift));
00131          }
00132       }
00133    }
00134 
00135 }
00136 
00137 }