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