-
+ 36AA7BC45976C3792B00414443B35C0DE1C172B5D2DDF26FF62736CF8642F3D2260FD45216F075DA1024A27CED6E03004A41CC3A7508877462A7A06C11EA4339
smg_comms/mpi/mpi-bit.c
(0 . 0)(1 . 262)
3682 /* mpi-bit.c - MPI bit level fucntions
3683 * Modified by No Such Labs. (C) 2015. See README.
3684 *
3685 * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10,
3686 * SHA256(gnupg-1.4.10.tar.gz):
3687 * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a
3688 * (C) 1994-2005 Free Software Foundation, Inc.
3689 *
3690 * This program is free software: you can redistribute it and/or modify
3691 * it under the terms of the GNU General Public License as published by
3692 * the Free Software Foundation, either version 3 of the License, or
3693 * (at your option) any later version.
3694 *
3695 * This program is distributed in the hope that it will be useful,
3696 * but WITHOUT ANY WARRANTY; without even the implied warranty of
3697 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
3698 * GNU General Public License for more details.
3699 *
3700 * You should have received a copy of the GNU General Public License
3701 * along with this program. If not, see <http://www.gnu.org/licenses/>.
3702 */
3703
3704 #include <stdio.h>
3705 #include <stdlib.h>
3706 #include <assert.h>
3707
3708 #include "knobs.h"
3709 #include "mpi-internal.h"
3710 #include "longlong.h"
3711
3712
3713 #ifdef MPI_INTERNAL_NEED_CLZ_TAB
3714 #ifdef __STDC__
3715 const
3716 #endif
3717 unsigned char
3718 __clz_tab[] =
3719 {
3720 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,
3721 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,
3722 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,
3723 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,
3724 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,
3725 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,
3726 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,
3727 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,
3728 };
3729 #endif
3730
3731
3732 #define A_LIMB_1 ((mpi_limb_t)1)
3733
3734
3735 /****************
3736 * Sometimes we have MSL (most significant limbs) which are 0;
3737 * this is for some reasons not good, so this function removes them.
3738 */
3739 void
3740 mpi_normalize( MPI a )
3741 {
3742 if( mpi_is_opaque (a) )
3743 return;
3744
3745 for( ; a->nlimbs && !a->d[a->nlimbs-1]; a->nlimbs-- )
3746 ;
3747 }
3748
3749
3750
3751 /****************
3752 * Return the number of bits in A.
3753 */
3754 unsigned
3755 mpi_get_nbits( MPI a )
3756 {
3757 unsigned n;
3758
3759 mpi_normalize( a );
3760 if( a->nlimbs ) {
3761 mpi_limb_t alimb = a->d[a->nlimbs-1];
3762 if( alimb )
3763 count_leading_zeros( n, alimb );
3764 else
3765 n = BITS_PER_MPI_LIMB;
3766 n = BITS_PER_MPI_LIMB - n + (a->nlimbs-1) * BITS_PER_MPI_LIMB;
3767 }
3768 else
3769 n = 0;
3770 return n;
3771 }
3772
3773
3774 /****************
3775 * Test whether bit N is set.
3776 */
3777 int
3778 mpi_test_bit( MPI a, unsigned n )
3779 {
3780 unsigned limbno, bitno;
3781 mpi_limb_t limb;
3782
3783 limbno = n / BITS_PER_MPI_LIMB;
3784 bitno = n % BITS_PER_MPI_LIMB;
3785
3786 if( limbno >= a->nlimbs )
3787 return 0; /* too far left: this is a 0 */
3788 limb = a->d[limbno];
3789 return (limb & (A_LIMB_1 << bitno))? 1: 0;
3790 }
3791
3792
3793 /****************
3794 * Set bit N of A.
3795 */
3796 void
3797 mpi_set_bit( MPI a, unsigned n )
3798 {
3799 unsigned limbno, bitno;
3800
3801 limbno = n / BITS_PER_MPI_LIMB;
3802 bitno = n % BITS_PER_MPI_LIMB;
3803
3804 if( limbno >= a->nlimbs ) { /* resize */
3805 if( a->alloced >= limbno )
3806 mpi_resize(a, limbno+1 );
3807 a->nlimbs = limbno+1;
3808 }
3809 a->d[limbno] |= (A_LIMB_1<<bitno);
3810 }
3811
3812 /****************
3813 * Set bit N of A. and clear all bits above
3814 */
3815 void
3816 mpi_set_highbit( MPI a, unsigned n )
3817 {
3818 unsigned limbno, bitno;
3819
3820 limbno = n / BITS_PER_MPI_LIMB;
3821 bitno = n % BITS_PER_MPI_LIMB;
3822
3823 if( limbno >= a->nlimbs ) { /* resize */
3824 if( a->alloced >= limbno )
3825 mpi_resize(a, limbno+1 );
3826 a->nlimbs = limbno+1;
3827 }
3828 a->d[limbno] |= (A_LIMB_1<<bitno);
3829 for( bitno++; bitno < BITS_PER_MPI_LIMB; bitno++ )
3830 a->d[limbno] &= ~(A_LIMB_1 << bitno);
3831 a->nlimbs = limbno+1;
3832 }
3833
3834 /****************
3835 * clear bit N of A and all bits above
3836 */
3837 void
3838 mpi_clear_highbit( MPI a, unsigned n )
3839 {
3840 unsigned limbno, bitno;
3841
3842 limbno = n / BITS_PER_MPI_LIMB;
3843 bitno = n % BITS_PER_MPI_LIMB;
3844
3845 if( limbno >= a->nlimbs )
3846 return; /* not allocated, so no effect */
3847
3848 for( ; bitno < BITS_PER_MPI_LIMB; bitno++ )
3849 a->d[limbno] &= ~(A_LIMB_1 << bitno);
3850
3851 /* adjust nlimbs to clear any leading zero-value limbs (normalize) */
3852 a->nlimbs = limbno+1;
3853 for( ; a->nlimbs && !a->d[a->nlimbs-1]; a->nlimbs-- );
3854
3855 }
3856
3857 /****************
3858 * Clear bit N of A.
3859 */
3860 void
3861 mpi_clear_bit( MPI a, unsigned n )
3862 {
3863 unsigned limbno, bitno;
3864
3865 limbno = n / BITS_PER_MPI_LIMB;
3866 bitno = n % BITS_PER_MPI_LIMB;
3867
3868 if( limbno >= a->nlimbs )
3869 return; /* don't need to clear this bit, it's to far to left */
3870 a->d[limbno] &= ~(A_LIMB_1 << bitno);
3871 }
3872
3873
3874 /****************
3875 * Shift A by N bits to the right
3876 * FIXME: should use alloc_limb if X and A are same.
3877 */
3878 void
3879 mpi_rshift( MPI x, MPI a, unsigned n )
3880 {
3881 mpi_ptr_t xp;
3882 mpi_size_t xsize;
3883
3884 xsize = a->nlimbs;
3885 x->sign = a->sign;
3886 RESIZE_IF_NEEDED(x, xsize);
3887 xp = x->d;
3888
3889 if( xsize ) {
3890 mpihelp_rshift( xp, a->d, xsize, n);
3891 MPN_NORMALIZE( xp, xsize);
3892 }
3893 x->nlimbs = xsize;
3894 }
3895
3896
3897 /****************
3898 * Shift A by COUNT limbs to the left
3899 * This is used only within the MPI library
3900 */
3901 void
3902 mpi_lshift_limbs( MPI a, unsigned int count )
3903 {
3904 mpi_ptr_t ap = a->d;
3905 int n = a->nlimbs;
3906 int i;
3907
3908 if( !count || !n )
3909 return;
3910
3911 RESIZE_IF_NEEDED( a, n+count );
3912
3913 for( i = n-1; i >= 0; i-- )
3914 ap[i+count] = ap[i];
3915 for(i=0; i < count; i++ )
3916 ap[i] = 0;
3917 a->nlimbs += count;
3918 }
3919
3920
3921 /****************
3922 * Shift A by COUNT limbs to the right
3923 * This is used only within the MPI library
3924 */
3925 void
3926 mpi_rshift_limbs( MPI a, unsigned int count )
3927 {
3928 mpi_ptr_t ap = a->d;
3929 mpi_size_t n = a->nlimbs;
3930 unsigned int i;
3931
3932 if( count >= n ) {
3933 a->nlimbs = 0;
3934 return;
3935 }
3936
3937 for( i = 0; i < n - count; i++ )
3938 ap[i] = ap[i+count];
3939 ap[i] = 0;
3940 a->nlimbs -= count;
3941 }
3942
3943