mpi-genesis~ 1
mpi-genesis~ 2 * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
mpi-genesis~ 3 *
mpi-genesis~ 4 * This file is part of GnuPG.
mpi-genesis~ 5 *
mpi-genesis~ 6 * GnuPG is free software; you can redistribute it and/or modify
mpi-genesis~ 7 * it under the terms of the GNU General Public License as published by
mpi-genesis~ 8 * the Free Software Foundation; either version 3 of the License, or
mpi-genesis~ 9 * (at your option) any later version.
mpi-genesis~ 10 *
mpi-genesis~ 11 * GnuPG is distributed in the hope that it will be useful,
mpi-genesis~ 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
mpi-genesis~ 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
mpi-genesis~ 14 * GNU General Public License for more details.
mpi-genesis~ 15 *
mpi-genesis~ 16 * You should have received a copy of the GNU General Public License
mpi-genesis~ 17 * along with this program; if not, see <http:
mpi-genesis~ 18 */
mpi-genesis~ 19
mpi-genesis~ 20 #include <config.h>
mpi-genesis~ 21 #include <stdio.h>
mpi-genesis~ 22 #include <stdlib.h>
mpi-genesis~ 23 #include <assert.h>
mpi-genesis~ 24 #include "mpi-internal.h"
mpi-genesis~ 25 #include "longlong.h"
mpi-genesis~ 26
mpi-genesis~ 27
mpi-genesis~ 28 #ifdef MPI_INTERNAL_NEED_CLZ_TAB
mpi-genesis~ 29 #ifdef __STDC__
mpi-genesis~ 30 const
mpi-genesis~ 31 #endif
mpi-genesis~ 32 unsigned char
mpi-genesis~ 33 __clz_tab[] =
mpi-genesis~ 34 {
mpi-genesis~ 35 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
mpi-genesis~ 36 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
mpi-genesis~ 37 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
mpi-genesis~ 38 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
mpi-genesis~ 39 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
mpi-genesis~ 40 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
mpi-genesis~ 41 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
mpi-genesis~ 42 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
mpi-genesis~ 43 };
mpi-genesis~ 44 #endif
mpi-genesis~ 45
mpi-genesis~ 46
mpi-genesis~ 47 #define A_LIMB_1 ((mpi_limb_t)1)
mpi-genesis~ 48
mpi-genesis~ 49
mpi-genesis~ 50
mpi-genesis~ 51 * Sometimes we have MSL (most significant limbs) which are 0;
mpi-genesis~ 52 * this is for some reasons not good, so this function removes them.
mpi-genesis~ 53 */
mpi-genesis~ 54 void
mpi-genesis~ 55 mpi_normalize( MPI a )
mpi-genesis~ 56 {
mpi-genesis~ 57 if( mpi_is_opaque (a) )
mpi-genesis~ 58 return;
mpi-genesis~ 59
mpi-genesis~ 60 for( ; a->nlimbs && !a->d[a->nlimbs-1]; a->nlimbs-- )
mpi-genesis~ 61 ;
mpi-genesis~ 62 }
mpi-genesis~ 63
mpi-genesis~ 64
mpi-genesis~ 65
mpi-genesis~ 66
mpi-genesis~ 67 * Return the number of bits in A.
mpi-genesis~ 68 */
mpi-genesis~ 69 unsigned
mpi-genesis~ 70 mpi_get_nbits( MPI a )
mpi-genesis~ 71 {
mpi-genesis~ 72 unsigned n;
mpi-genesis~ 73
mpi-genesis~ 74 mpi_normalize( a );
mpi-genesis~ 75 if( a->nlimbs ) {
mpi-genesis~ 76 mpi_limb_t alimb = a->d[a->nlimbs-1];
mpi-genesis~ 77 if( alimb )
mpi-genesis~ 78 count_leading_zeros( n, alimb );
mpi-genesis~ 79 else
mpi-genesis~ 80 n = BITS_PER_MPI_LIMB;
mpi-genesis~ 81 n = BITS_PER_MPI_LIMB - n + (a->nlimbs-1) * BITS_PER_MPI_LIMB;
mpi-genesis~ 82 }
mpi-genesis~ 83 else
mpi-genesis~ 84 n = 0;
mpi-genesis~ 85 return n;
mpi-genesis~ 86 }
mpi-genesis~ 87
mpi-genesis~ 88
mpi-genesis~ 89
mpi-genesis~ 90 * Test whether bit N is set.
mpi-genesis~ 91 */
mpi-genesis~ 92 int
mpi-genesis~ 93 mpi_test_bit( MPI a, unsigned n )
mpi-genesis~ 94 {
mpi-genesis~ 95 unsigned limbno, bitno;
mpi-genesis~ 96 mpi_limb_t limb;
mpi-genesis~ 97
mpi-genesis~ 98 limbno = n / BITS_PER_MPI_LIMB;
mpi-genesis~ 99 bitno = n % BITS_PER_MPI_LIMB;
mpi-genesis~ 100
mpi-genesis~ 101 if( limbno >= a->nlimbs )
mpi-genesis~ 102 return 0;
mpi-genesis~ 103 limb = a->d[limbno];
mpi-genesis~ 104 return (limb & (A_LIMB_1 << bitno))? 1: 0;
mpi-genesis~ 105 }
mpi-genesis~ 106
mpi-genesis~ 107
mpi-genesis~ 108
mpi-genesis~ 109 * Set bit N of A.
mpi-genesis~ 110 */
mpi-genesis~ 111 void
mpi-genesis~ 112 mpi_set_bit( MPI a, unsigned n )
mpi-genesis~ 113 {
mpi-genesis~ 114 unsigned limbno, bitno;
mpi-genesis~ 115
mpi-genesis~ 116 limbno = n / BITS_PER_MPI_LIMB;
mpi-genesis~ 117 bitno = n % BITS_PER_MPI_LIMB;
mpi-genesis~ 118
mpi-genesis~ 119 if( limbno >= a->nlimbs ) {
mpi-genesis~ 120 if( a->alloced >= limbno )
mpi-genesis~ 121 mpi_resize(a, limbno+1 );
mpi-genesis~ 122 a->nlimbs = limbno+1;
mpi-genesis~ 123 }
mpi-genesis~ 124 a->d[limbno] |= (A_LIMB_1<<bitno);
mpi-genesis~ 125 }
mpi-genesis~ 126
mpi-genesis~ 127
mpi-genesis~ 128 * Set bit N of A. and clear all bits above
mpi-genesis~ 129 */
mpi-genesis~ 130 void
mpi-genesis~ 131 mpi_set_highbit( MPI a, unsigned n )
mpi-genesis~ 132 {
mpi-genesis~ 133 unsigned limbno, bitno;
mpi-genesis~ 134
mpi-genesis~ 135 limbno = n / BITS_PER_MPI_LIMB;
mpi-genesis~ 136 bitno = n % BITS_PER_MPI_LIMB;
mpi-genesis~ 137
mpi-genesis~ 138 if( limbno >= a->nlimbs ) {
mpi-genesis~ 139 if( a->alloced >= limbno )
mpi-genesis~ 140 mpi_resize(a, limbno+1 );
mpi-genesis~ 141 a->nlimbs = limbno+1;
mpi-genesis~ 142 }
mpi-genesis~ 143 a->d[limbno] |= (A_LIMB_1<<bitno);
mpi-genesis~ 144 for( bitno++; bitno < BITS_PER_MPI_LIMB; bitno++ )
mpi-genesis~ 145 a->d[limbno] &= ~(A_LIMB_1 << bitno);
mpi-genesis~ 146 a->nlimbs = limbno+1;
mpi-genesis~ 147 }
mpi-genesis~ 148
mpi-genesis~ 149
mpi-genesis~ 150 * clear bit N of A and all bits above
mpi-genesis~ 151 */
mpi-genesis~ 152 void
mpi-genesis~ 153 mpi_clear_highbit( MPI a, unsigned n )
mpi-genesis~ 154 {
mpi-genesis~ 155 unsigned limbno, bitno;
mpi-genesis~ 156
mpi-genesis~ 157 limbno = n / BITS_PER_MPI_LIMB;
mpi-genesis~ 158 bitno = n % BITS_PER_MPI_LIMB;
mpi-genesis~ 159
mpi-genesis~ 160 if( limbno >= a->nlimbs )
mpi-genesis~ 161 return;
mpi-genesis~ 162
mpi-genesis~ 163 for( ; bitno < BITS_PER_MPI_LIMB; bitno++ )
mpi-genesis~ 164 a->d[limbno] &= ~(A_LIMB_1 << bitno);
mpi-genesis~ 165 a->nlimbs = limbno+1;
mpi-genesis~ 166 }
mpi-genesis~ 167
mpi-genesis~ 168
mpi-genesis~ 169 * Clear bit N of A.
mpi-genesis~ 170 */
mpi-genesis~ 171 void
mpi-genesis~ 172 mpi_clear_bit( MPI a, unsigned n )
mpi-genesis~ 173 {
mpi-genesis~ 174 unsigned limbno, bitno;
mpi-genesis~ 175
mpi-genesis~ 176 limbno = n / BITS_PER_MPI_LIMB;
mpi-genesis~ 177 bitno = n % BITS_PER_MPI_LIMB;
mpi-genesis~ 178
mpi-genesis~ 179 if( limbno >= a->nlimbs )
mpi-genesis~ 180 return;
mpi-genesis~ 181 a->d[limbno] &= ~(A_LIMB_1 << bitno);
mpi-genesis~ 182 }
mpi-genesis~ 183
mpi-genesis~ 184
mpi-genesis~ 185
mpi-genesis~ 186 * Shift A by N bits to the right
mpi-genesis~ 187 * FIXME: should use alloc_limb if X and A are same.
mpi-genesis~ 188 */
mpi-genesis~ 189 void
mpi-genesis~ 190 mpi_rshift( MPI x, MPI a, unsigned n )
mpi-genesis~ 191 {
mpi-genesis~ 192 mpi_ptr_t xp;
mpi-genesis~ 193 mpi_size_t xsize;
mpi-genesis~ 194
mpi-genesis~ 195 xsize = a->nlimbs;
mpi-genesis~ 196 x->sign = a->sign;
mpi-genesis~ 197 RESIZE_IF_NEEDED(x, xsize);
mpi-genesis~ 198 xp = x->d;
mpi-genesis~ 199
mpi-genesis~ 200 if( xsize ) {
mpi-genesis~ 201 mpihelp_rshift( xp, a->d, xsize, n);
mpi-genesis~ 202 MPN_NORMALIZE( xp, xsize);
mpi-genesis~ 203 }
mpi-genesis~ 204 x->nlimbs = xsize;
mpi-genesis~ 205 }
mpi-genesis~ 206
mpi-genesis~ 207
mpi-genesis~ 208
mpi-genesis~ 209 * Shift A by COUNT limbs to the left
mpi-genesis~ 210 * This is used only within the MPI library
mpi-genesis~ 211 */
mpi-genesis~ 212 void
mpi-genesis~ 213 mpi_lshift_limbs( MPI a, unsigned int count )
mpi-genesis~ 214 {
mpi-genesis~ 215 mpi_ptr_t ap = a->d;
mpi-genesis~ 216 int n = a->nlimbs;
mpi-genesis~ 217 int i;
mpi-genesis~ 218
mpi-genesis~ 219 if( !count || !n )
mpi-genesis~ 220 return;
mpi-genesis~ 221
mpi-genesis~ 222 RESIZE_IF_NEEDED( a, n+count );
mpi-genesis~ 223
mpi-genesis~ 224 for( i = n-1; i >= 0; i-- )
mpi-genesis~ 225 ap[i+count] = ap[i];
mpi-genesis~ 226 for(i=0; i < count; i++ )
mpi-genesis~ 227 ap[i] = 0;
mpi-genesis~ 228 a->nlimbs += count;
mpi-genesis~ 229 }
mpi-genesis~ 230
mpi-genesis~ 231
mpi-genesis~ 232
mpi-genesis~ 233 * Shift A by COUNT limbs to the right
mpi-genesis~ 234 * This is used only within the MPI library
mpi-genesis~ 235 */
mpi-genesis~ 236 void
mpi-genesis~ 237 mpi_rshift_limbs( MPI a, unsigned int count )
mpi-genesis~ 238 {
mpi-genesis~ 239 mpi_ptr_t ap = a->d;
mpi-genesis~ 240 mpi_size_t n = a->nlimbs;
mpi-genesis~ 241 unsigned int i;
mpi-genesis~ 242
mpi-genesis~ 243 if( count >= n ) {
mpi-genesis~ 244 a->nlimbs = 0;
mpi-genesis~ 245 return;
mpi-genesis~ 246 }
mpi-genesis~ 247
mpi-genesis~ 248 for( i = 0; i < n - count; i++ )
mpi-genesis~ 249 ap[i] = ap[i+count];
mpi-genesis~ 250 ap[i] = 0;
mpi-genesis~ 251 a->nlimbs -= count;
mpi-genesis~ 252 }
mpi-genesis~ 253
mpi-genesis~ 254