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