/*
Licensed to the Apache Software Foundation (ASF) under one
or more contributor license agreements.  See the NOTICE file
distributed with this work for additional information
regarding copyright ownership.  The ASF licenses this file
to you under the Apache License, Version 2.0 (the
"License"); you may not use this file except in compliance
with the License.  You may obtain a copy of the License at

  http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing,
software distributed under the License is distributed on an
"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
KIND, either express or implied.  See the License for the
specific language governing permissions and limitations
under the License.
*/

use std::fmt;
use std::cmp::Ordering;
use std::str::SplitWhitespace;

use rom;
use rom::{Chunk, NLEN};

#[cfg(target_pointer_width = "32")]
use rom::DChunk;

#[derive(Copy, Clone)]
pub struct BIG {
 	pub w: [Chunk; rom::NLEN]
}

//mod dbig;

use dbig::DBIG;
use rand::RAND;

impl fmt::Display for BIG {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut big = self.clone();
        write!(f, "BIG: [ {} ]", big.tostring())
    }
}

impl fmt::Debug for BIG {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut big = self.clone();
        write!(f, "BIG: [ {} ]", big.tostring())
    }
}

impl PartialEq for BIG {
    fn eq(&self, other: &BIG) -> bool {
        return self.w == other.w;
    }
}

impl Ord for BIG {
    fn cmp(&self, other: &BIG) -> Ordering {
        let r = BIG::comp(self, other);
        if r > 0 {
            return Ordering::Greater;
        }
        if r < 0 {
            return Ordering::Less;
        }
        return Ordering::Equal;
    }
}

impl Eq for BIG { }

impl PartialOrd for BIG {
    fn partial_cmp(&self, other: &BIG) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl BIG {

   pub fn new() -> BIG {
        BIG {
        	w: [0; rom::NLEN]
         }
    }

    pub fn new_int(x:isize) -> BIG {
    	let mut s= BIG::new();
    	s.w[0]=x as Chunk;
    	return s;
    }

    pub fn new_ints(a:&[Chunk]) -> BIG {
    	let mut s= BIG::new();
    	for i in 0..rom::NLEN {s.w[i]=a[i]}
    	return s;
    }

    pub fn new_copy(y:&BIG) -> BIG {
    	let mut s= BIG::new();   
    	for i in 0..rom::NLEN {s.w[i]=y.w[i]}
    	return s;	
    }

    pub fn new_big(y:&BIG) -> BIG {
        let mut s= BIG::new();   
        for i in 0..rom::NLEN {s.w[i]=y.w[i]}
        return s;   
    }

    pub fn new_dcopy(y:&DBIG) -> BIG {
    	let mut s= BIG::new();   
    	for i in 0..rom::NLEN {s.w[i]=y.w[i]}
    	return s;	
    } 

	pub fn get(&self,i:usize) -> Chunk {
		return self.w[i]; 
	}

	pub fn set(&mut self,i:usize,x:Chunk) {
		self.w[i]=x;	
	}

	pub fn xortop(&mut self,x:Chunk) {
		self.w[rom::NLEN-1]^=x;
	}

	pub fn ortop(&mut self,x:Chunk) {
		self.w[rom::NLEN-1]|=x;
	}

/* test for zero */
	pub fn iszilch(&self) -> bool {
		for i in 0 ..rom::NLEN {
			if self.w[i]!=0 {return false}
		}
		return true; 
	}

/* set to zero */
	pub fn zero(&mut self) {
		for i in 0 ..rom::NLEN {
			self.w[i]=0
		}
	}

/* Test for equal to one */
	pub fn isunity(&self) -> bool {
		for i in 0 ..rom::NLEN {
			if self.w[i]!=0 {return false}
		}
		if self.w[0]!=1 {return false}
		return true;
	}

/* set to one */
	pub fn one(&mut self) {
		self.w[0]=1;
		for i in 1 ..rom::NLEN {
			self.w[i]=0;
		}
	}

/* Copy from another BIG */
	pub fn copy(&mut self,x: &BIG) {
		for i in 0 ..rom::NLEN {
			self.w[i]=x.w[i]
		}
	}

    pub fn dcopy(&mut self,x: &DBIG)
    {
        for i in 0 ..rom::NLEN {self.w[i] = x.w[i]}
    }

/* calculate Field Excess */
	pub fn excess(a:&BIG) -> Chunk {
		return (a.w[rom::NLEN-1]&rom::OMASK)>>(rom::MODBITS%rom::BASEBITS)
	}

    pub fn ff_excess(a:&BIG) -> Chunk {
        return (a.w[rom::NLEN-1]&rom::P_OMASK)>>(rom::P_MB)
    }

#[cfg(target_pointer_width = "32")]
    pub fn pexceed(a: &BIG,b: &BIG) -> bool {
        let ea=BIG::excess(a);
        let eb=BIG::excess(b);        
        if ((ea+1) as DChunk)*((eb+1) as DChunk) > rom::FEXCESS as DChunk {return true}
        return false
    }

#[cfg(target_pointer_width = "32")]
    pub fn sexceed(a: &BIG) -> bool {
        let ea=BIG::excess(a);
        if ((ea+1) as DChunk)*((ea+1) as DChunk) > rom::FEXCESS as DChunk {return true}
        return false
    }

#[cfg(target_pointer_width = "32")]
    pub fn ff_pexceed(a: &BIG,b: &BIG) -> bool {
        let ea=BIG::ff_excess(a);
        let eb=BIG::ff_excess(b);
        if ((ea+1) as DChunk)*((eb+1) as DChunk) > rom::P_FEXCESS as DChunk {return true}
        return false;
    }

#[cfg(target_pointer_width = "32")]
    pub fn ff_sexceed(a: &BIG) -> bool {
        let ea=BIG::ff_excess(a);
        if ((ea+1) as DChunk)*((ea+1) as DChunk) > rom::P_FEXCESS as DChunk {return true}
        return false;
    }

/* Get top and bottom half of =x*y+c+r */
#[cfg(target_pointer_width = "32")]
    pub fn muladd(a: Chunk,b: Chunk,c: Chunk,r: Chunk) -> (Chunk,Chunk) {
        let prod:DChunk = (a as DChunk)*(b as DChunk)+(c as DChunk)+(r as DChunk);
        let bot=(prod&(rom::BMASK as DChunk)) as Chunk;
        let top=(prod>>rom::BASEBITS) as Chunk;   
        return (top,bot);     
    }

#[cfg(target_pointer_width = "64")]
    pub fn pexceed(a: &BIG,b: &BIG) -> bool {
        let ea=BIG::excess(a);
        let eb=BIG::excess(b);        
        if (ea+1) > rom::FEXCESS/(eb+1) {return true}
        return false
    }

#[cfg(target_pointer_width = "64")]
    pub fn sexceed(a: &BIG) -> bool {
        let ea=BIG::excess(a);
        if (ea+1) > rom::FEXCESS/(ea+1) {return true}
        return false
    }

#[cfg(target_pointer_width = "64")]
    pub fn ff_pexceed(a: &BIG,b: &BIG) -> bool {
        let ea=BIG::ff_excess(a);
        let eb=BIG::ff_excess(b);
        if (ea+1) > rom::P_FEXCESS/(eb+1) {return true}
        return false;
    }

#[cfg(target_pointer_width = "64")]
    pub fn ff_sexceed(a: &BIG) -> bool {
        let ea=BIG::ff_excess(a);
        if (ea+1) > rom::P_FEXCESS/(ea+1) {return true}
        return false;
    }    

#[cfg(target_pointer_width = "64")]
    pub fn muladd(a: Chunk,b: Chunk,c: Chunk,r: Chunk) -> (Chunk,Chunk) {
        let x0=a&rom::HMASK;
        let x1=a>>rom::HBITS;
        let y0=b&rom::HMASK;
        let y1=b>>rom::HBITS;
        let mut bot=x0*y0;
        let mut top=x1*y1;
        let mid=x0*y1+x1*y0;
        let u0=mid&rom::HMASK;
        let u1=mid>>rom::HBITS;
        bot+= u0 <<rom::HBITS;
        bot+=c; bot+=r;
        top+=u1;
        let carry=bot>>rom::BASEBITS;
        bot&=rom::BMASK;
        top+=carry;
        return (top,bot);
    }

/* 
alise BIG - force all digits < 2^rom::BASEBITS */
    pub fn norm(&mut self) -> Chunk
    {
        let mut carry=0 as Chunk;
        for i in 0 ..rom::NLEN-1 {
            let d=self.w[i]+carry;
            self.w[i]=d&rom::BMASK;
            carry=d>>rom::BASEBITS;
        }
        self.w[rom::NLEN-1]+=carry;
        return (self.w[rom::NLEN-1]>>((8*rom::MODBYTES)%rom::BASEBITS)) as Chunk;
    }

/* Conditional swap of two bigs depending on d using XOR - no branches */
	pub fn cswap(&mut self,b: &mut BIG,d: isize) {
		let mut c= d as Chunk;
		c=!(c-1);
		for i in 0 ..rom::NLEN {
			let t=c&(self.w[i]^b.w[i]);
			self.w[i]^=t;
			b.w[i]^=t;
		}
	}

	pub fn cmove(&mut self,g:&BIG,d: isize) {
		let b= -d as Chunk;
		for i in 0 ..rom::NLEN {
			self.w[i]^=(self.w[i]^g.w[i])&b;
		}
	}

/* Shift right by less than a word */
	pub fn fshr(&mut self, k: usize) -> isize {
		let n = k;
		let w=self.w[0]&((1<<n)-1); /* shifted out part */
		for i in 0 ..rom::NLEN-1 {
			self.w[i]=(self.w[i]>>k)|((self.w[i+1]<<(rom::BASEBITS-n))&rom::BMASK);
		}
		self.w[rom::NLEN-1]=self.w[rom::NLEN-1]>>k;
		return w as isize;
	}

 /* general shift right */
	pub fn shr(&mut self,k:usize) {
		let n=k%rom::BASEBITS;
		let m=k/rom::BASEBITS;
		for i in 0 ..rom::NLEN-m-1 {
			self.w[i]=(self.w[m+i]>>n)|((self.w[m+i+1]<<(rom::BASEBITS-n))&rom::BMASK)
		}
		self.w[rom::NLEN-m-1]=self.w[rom::NLEN-1]>>n;
		for i in rom::NLEN-m ..rom::NLEN 
			{self.w[i]=0}
	}	

/* Shift right by less than a word */
	pub fn fshl(&mut self,k:usize) -> isize {
		let n=k;
		self.w[rom::NLEN-1]=((self.w[rom::NLEN-1]<<n))|(self.w[rom::NLEN-2]>>(rom::BASEBITS-n));
		for i in (1 ..rom::NLEN-1).rev() {
			self.w[i]=((self.w[i]<<k)&rom::BMASK)|(self.w[i-1]>>(rom::BASEBITS-n));
		}
		self.w[0]=(self.w[0]<<n)&rom::BMASK;
		return (self.w[rom::NLEN-1]>>((8*rom::MODBYTES)%rom::BASEBITS)) as isize /* return excess - only used in ff.c */
	}

/* general shift left */
	pub fn shl(&mut self,k: usize) {
		let n=k%rom::BASEBITS;
		let m=k/rom::BASEBITS;

		self.w[rom::NLEN-1]=self.w[rom::NLEN-1-m]<<n;
		if rom::NLEN>=m+2 {self.w[rom::NLEN-1]|=self.w[rom::NLEN-m-2]>>(rom::BASEBITS-n)}
		for i in (m+1 ..rom::NLEN-1).rev() {
			self.w[i]=((self.w[i-m]<<n)&rom::BMASK)|(self.w[i-m-1]>>(rom::BASEBITS-n));
		}
		self.w[m]=(self.w[0]<<n)&rom::BMASK; 
		for i in 0 ..m {self.w[i]=0}
	}

/* return number of bits */
	pub fn nbits(&mut self) -> usize {
		let mut k=rom::NLEN-1;
		self.norm();
		while (k as isize)>=0 && self.w[k]==0 {k=k.wrapping_sub(1)}
		if (k as isize) <0 {return 0}
		let mut bts=rom::BASEBITS*k;
		let mut c=self.w[k];
		while c!=0 {c/=2; bts+=1;}
		return bts;
	}

/* Convert to Hex String */
	pub fn tostring(&mut self) -> String {
		let mut s = String::new();
		let mut len=self.nbits();

		if len%4==0 {
			len/=4;
		} else {
			len/=4;
			len+=1;
		}
		let mb=(rom::MODBYTES*2) as usize;
		if len<mb {len=mb}

		for i in (0 ..len).rev() {
			let mut b=BIG::new_copy(&self);
			b.shr(i*4);
			s=s + &format!("{:X}", b.w[0]&15);
		}
		return s;
	}	

    pub fn add(&mut self,r:&BIG) {
		for i in 0 ..rom::NLEN {
			self.w[i]+=r.w[i] 
		}
	}

    pub fn dbl(&mut self) {
        for i in 0 ..rom::NLEN {
            self.w[i]+=self.w[i]
        }        
    }

/* return this+x */
	pub fn plus(&self,x: &BIG) -> BIG {
		let mut s=BIG::new();
		for i in 0 ..rom::NLEN {
			s.w[i]=self.w[i]+x.w[i];
		}
		return s;
	}

    pub fn inc(&mut self,x:isize) {
    	self.norm();
    	self.w[0]+=x as Chunk; 
    }

//    pub fn incl(&mut self,x:Chunk) {
//        self.norm();
//        self.w[0]+=x; 
//    }

/* return self-x */
	pub fn minus(&self,x:& BIG) -> BIG {
		let mut d=BIG::new();
		for i in 0 ..rom::NLEN {
			d.w[i]=self.w[i]-x.w[i];
		}
		return d;
	}

/* self-=x */
	pub fn sub(&mut self,x:&BIG) {
		for i in 0 ..rom::NLEN {
			self.w[i]-=x.w[i]; 
		}
	} 

/* reverse subtract this=x-this */ 
	pub fn rsub(&mut self,x:&BIG) {
		for i in 0 ..rom::NLEN {
			self.w[i]=x.w[i]-self.w[i] 
		}
	} 

/* self-=x, where x is int */
	pub fn dec(&mut self,x:isize) {
		self.norm();
		self.w[0]-= x as Chunk;
	} 

/* self*=x, where x is small int<NEXCESS */
	pub fn imul(&mut self,c: isize) {
		for i in 0 ..rom::NLEN { 
			self.w[i]*=c as Chunk;
		}
	}

/* convert this BIG to byte array */
	pub fn tobytearray(&mut self,b: &mut [u8],n:usize) {
		self.norm();
		let mut c=BIG::new_copy(self);

		for i in (0 ..(rom::MODBYTES as usize)).rev() {
			b[i+n]=(c.w[0]&0xff) as u8;
			c.fshr(8);
		}
	}

/* convert from byte array to BIG */
	pub fn frombytearray(b: &[u8],n:usize) -> BIG {
		let mut m=BIG::new();
		for i in 0 ..(rom::MODBYTES as usize) {
			m.fshl(8); m.w[0]+=(b[i+n]&0xff) as Chunk;
		}
		return m; 
	}

	pub fn tobytes(&mut self,b: &mut [u8]) {
		self.tobytearray(b,0)
	}

	pub fn frombytes(b: &[u8]) -> BIG {
		return BIG::frombytearray(b,0)
	}

    pub fn to_hex(&self) -> String {
        let mut ret: String = String::with_capacity(NLEN * 16 + NLEN - 1);

        for i in 0..NLEN {
            if i == NLEN-1 {
                ret.push_str(&format!("{:X}", self.w[i]));
            } else {
                ret.push_str(&format!("{:X} ", self.w[i]));
            }
        }
        return ret;
    }

    pub fn from_hex_iter(iter: &mut SplitWhitespace) -> BIG {
        let mut ret:BIG = BIG::new();
        for i in 0..NLEN {
            let v = iter.next();
            match v {
                Some(x) => {
                    ret.w[i] = u64::from_str_radix(x, 16).unwrap() as Chunk;
                },
                None => {
                    break;
                }
            }
        }
        return ret;
    }

    pub fn from_hex(val: String) -> BIG {
        let mut iter = val.split_whitespace();
        return BIG::from_hex_iter(&mut iter);
    }

/* self*=x, where x is >NEXCESS */
    pub fn pmul(&mut self,c: isize) -> Chunk {
        let mut carry=0 as Chunk;
        self.norm();
        for i in 0 ..rom::NLEN {
            let ak=self.w[i];
            let tuple=BIG::muladd(ak,c as Chunk,carry,0 as Chunk);
            carry=tuple.0; self.w[i]=tuple.1;
        }
        return carry;
    }  

/* self*=c and catch overflow in DBIG */
    pub fn pxmul(&mut self,c: isize) -> DBIG
    {
        let mut m=DBIG::new();
        let mut carry=0 as Chunk;
        for j in 0 ..rom::NLEN {
            let tuple=BIG::muladd(self.w[j],c as Chunk,carry,m.w[j]);
            carry=tuple.0; m.w[j]=tuple.1; 
        }
        m.w[rom::NLEN]=carry;
        return m;
    }

/* divide by 3 */
    pub fn div3(&mut self) -> Chunk
    {
        let mut carry=0 as Chunk;
        self.norm();
        let base=1<<rom::BASEBITS;
        for i in (0 ..rom::NLEN).rev() {
            let ak=carry*base+self.w[i];
            self.w[i]=ak/3;
            carry=ak%3;
        }
        return carry;
    }

/* return a*b where result fits in a BIG */
    pub fn smul(a: &BIG,b: &BIG) -> BIG {
        let mut c=BIG::new();
        for i in 0 ..rom::NLEN {
            let mut carry=0 as Chunk; 
            for j in 0 ..rom::NLEN {
                if i+j<rom::NLEN {
                    let tuple=BIG::muladd(a.w[i],b.w[j],carry,c.w[i+j]);
                    carry=tuple.0; c.w[i+j]=tuple.1;
                }
            }
        }
        return c;
    }

/* Compare a and b, return 0 if a==b, -1 if a<b, +1 if a>b. Inputs must be normalised */
    pub fn comp(a: &BIG,b: &BIG) -> isize {
        for i in (0 ..rom::NLEN).rev() {
            if a.w[i]==b.w[i] {continue}
            if a.w[i]>b.w[i] {return 1}
            else  {return -1}
        }
        return 0;
    }

/* set x = x mod 2^m */
    pub fn mod2m(&mut self,m: usize)
    {
        let wd=m/rom::BASEBITS;
        let bt=m%rom::BASEBITS;
        let msk=(1<<bt)-1;
        self.w[wd]&=msk;
        for i in wd+1 ..rom::NLEN {self.w[i]=0}
    }

/* Arazi and Qi inversion mod 256 */
    pub fn invmod256(a: isize) -> isize {
        let mut t1:isize=0;
        let mut c=(a>>1)&1;
        t1+=c;
        t1&=1;
        t1=2-t1;
        t1<<=1;
        let mut u=t1+1;
    
    // i=2
        let mut b=a&3;
        t1=u*b; t1>>=2;
        c=(a>>2)&3;
        let mut t2=(u*c)&3;
        t1+=t2;
        t1*=u; t1&=3;
        t1=4-t1;
        t1<<=2;
        u+=t1;
    
    // i=4
        b=a&15;
        t1=u*b; t1>>=4;
        c=(a>>4)&15;
        t2=(u*c)&15;
        t1+=t2;
        t1*=u; t1&=15;
        t1=16-t1;
        t1<<=4;
        u+=t1;
    
        return u;
    }

/* return parity */
    pub fn parity(&self) -> isize {
        return (self.w[0]%2) as isize;
    }

/* return n-th bit */
    pub fn bit(&self,n: usize) -> isize {
        if (self.w[n/(rom::BASEBITS as usize)]&(1<<(n%rom::BASEBITS)))>0 {return 1;}
        else {return 0;}
    }

/* return n last bits */
    pub fn lastbits(&mut self,n: usize) -> isize
    {
        let msk =  ((1<<n)-1) as Chunk; 
        self.norm();
        return (self.w[0]&msk) as isize;
    }

/* a=1/a mod 2^256. This is very fast! */
    pub fn invmod2m(&mut self) {
        let mut u=BIG::new();
        let mut b=BIG::new();
        let mut c=BIG::new();
    
        u.inc(BIG::invmod256(self.lastbits(8)));
    
        let mut i=8;
        while i<rom::BIGBITS {
            b.copy(self);
            b.mod2m(i);
            let mut t1=BIG::smul(&u,&b);
            t1.shr(i);
            c.copy(self);
            c.shr(i);
            c.mod2m(i);
    
            let mut t2=BIG::smul(&u,&c);
            t2.mod2m(i);
            t1.add(&t2);
            b=BIG::smul(&t1,&u);
            t1.copy(&b);
            t1.mod2m(i);
    
            t2.one(); t2.shl(i); t1.rsub(&t2); t1.norm();
            t1.shl(i);
            u.add(&t1);
            i<<=1;
        }
        u.mod2m(rom::BIGBITS);
        self.copy(&u);
        self.norm();
    }

/* reduce self mod m */
    pub fn rmod(&mut self,n: &BIG) {
        let mut k=0;
        let mut m=BIG::new_copy(n);
	    let mut r=BIG::new();
        self.norm();
        if BIG::comp(self,&m)<0 {return}
        loop {
            m.fshl(1);
            k += 1;
            if BIG::comp(self,&m)<0 {break}
        }
    
        while k>0 {
            m.fshr(1);

		r.copy(self);
		r.sub(&m);
		r.norm();
		self.cmove(&r,(1-((r.w[rom::NLEN-1]>>(rom::CHUNK-1))&1)) as isize);
/*
            if BIG::comp(self,&m)>=0 {
				self.sub(&m);
				self.norm();
            } */
            k -= 1;
        }
    }

/* divide self by m */
    pub fn div(&mut self,n: &BIG) {
        let mut k=0;
        self.norm();
        let mut e=BIG::new_int(1);
        let mut b=BIG::new_copy(self);
        let mut m=BIG::new_copy(n);
        let mut r=BIG::new();
        self.zero();
    
        while BIG::comp(&b,&m)>=0 {
            e.fshl(1);
            m.fshl(1);
            k += 1;
        }
    
        while k>0 {
            m.fshr(1);
            e.fshr(1);

		r.copy(&b);
		r.sub(&m);
		r.norm();
		let d=(1-((r.w[rom::NLEN-1]>>(rom::CHUNK-1))&1)) as isize;
		b.cmove(&r,d);
		r.copy(self);
		r.add(&e);
		r.norm();
		self.cmove(&r,d);
/*
            if BIG::comp(&b,&m)>=0 {
				self.add(&e);
				self.norm();
				b.sub(&m);
				b.norm();
            } */
            k -= 1;
        }
    }

/* get 8*MODBYTES size random number */
    pub fn random(rng: &mut RAND) -> BIG {
        let mut m=BIG::new();
        let mut j=0;
        let mut r:u8=0;
/* generate random BIG */ 
        for _ in 0..8*(rom::MODBYTES as usize)  {
            if j==0 {
                r=rng.getbyte()
            } else {r>>=1}

            let b= (r as Chunk)&1; 
            m.shl(1); m.w[0]+=b;// m.inc(b)
            j+=1; j&=7; 
        }
        return m;
    }

/* Create random BIG in portable way, one bit at a time */
    pub fn randomnum(q: &BIG,rng: &mut RAND) -> BIG {
        let mut d=DBIG::new();
        let mut j=0;
        let mut r:u8=0;
        for _ in 0..2*(rom::MODBITS as usize) {
            if j==0 {
                r=rng.getbyte();
            } else {r>>=1}

            let b= (r as Chunk)&1;
            d.shl(1); d.w[0]+=b; // m.inc(b);
            j+=1; j&=7; 
        }
        let m=d.dmod(q);
        return m;
    }


   /* Jacobi Symbol (this/p). Returns 0, 1 or -1 */
    pub fn jacobi(&mut self,p: &BIG) -> isize {
        let mut m:usize=0;
        let mut t=BIG::new();
        let mut x=BIG::new();
        let mut n=BIG::new();
        let zilch=BIG::new();
        let one=BIG::new_int(1);
        if p.parity()==0 || BIG::comp(self,&zilch)==0 || BIG::comp(p,&one)<=0 {return 0}
        self.norm();

        x.copy(self);
        n.copy(p);
        x.rmod(p);

        while BIG::comp(&n,&one)>0 {
            if BIG::comp(&x,&zilch)==0 {return 0}
            let n8=n.lastbits(3) as usize;
            let mut k=0;
            while x.parity()==0 {
				k += 1;
				x.shr(1);
            }
            if k%2==1 {m+=(n8*n8-1)/8}
            m+=(n8-1)*((x.lastbits(2) as usize)-1)/4;
            t.copy(&n);
            t.rmod(&x);
            n.copy(&x);
            x.copy(&t);
            m%=2;
    
        }
        if m==0 {return 1}
        else {return -1}
    }

/* self=1/self mod p. Binary method */
    pub fn invmodp(&mut self,p: &BIG) {
        self.rmod(p);
        let mut u=BIG::new_copy(self);
        let mut v=BIG::new_copy(p);
        let mut x1=BIG::new_int(1);
        let mut x2=BIG::new();
        let mut t=BIG::new();
        let one=BIG::new_int(1);
    
        while (BIG::comp(&u,&one) != 0 ) && (BIG::comp(&v,&one) != 0 ) {
            while u.parity()==0 {
				u.shr(1);
				if x1.parity() != 0 {
                    x1.add(p);
                    x1.norm();
				}
				x1.shr(1);
            }
            while v.parity()==0 {
				v.shr(1);
				if x2.parity() != 0  {
                    x2.add(p);
                    x2.norm();
				}
				x2.shr(1);
            }
            if BIG::comp(&u,&v)>=0 {
				u.sub(&v);
				u.norm();
                if BIG::comp(&x1,&x2)>=0 {x1.sub(&x2)}
				else
				{
                    t.copy(p);
                    t.sub(&x2);
                    x1.add(&t);
				}
				x1.norm();
            }
            else
            {
				v.sub(&u);
				v.norm();
                if BIG::comp(&x2,&x1)>=0 {x2.sub(&x1)}
				else
				{
                    t.copy(p);
                    t.sub(&x1);
                    x2.add(&t);
				}
				x2.norm();
            }
        }
        if BIG::comp(&u,&one)==0 {self.copy(&x1)}
        else {self.copy(&x2)}
    }

   /* return a*b as DBIG */
#[cfg(target_pointer_width = "32")]
    pub fn mul(a: &BIG,b: &BIG) -> DBIG {
        let mut c=DBIG::new();
        let rm=rom::BMASK as DChunk;
        let rb=rom::BASEBITS;
     //   a.norm();
     //   b.norm();

        let mut d: [DChunk; rom::DNLEN] = [0; rom::DNLEN];
        for i in 0 ..rom::NLEN {
            d[i]=(a.w[i] as DChunk)*(b.w[i] as DChunk);
        }
        let mut s=d[0];
        let mut t=s; c.w[0]=(t&rm) as Chunk; 
        let mut co=t>>rb;
        for k in 1 ..rom::NLEN {
            s+=d[k]; t=co+s;
            for i in 1+k/2..k+1
                {t+=((a.w[i]-a.w[k-i]) as DChunk)*((b.w[k-i]-b.w[i]) as DChunk)}
            c.w[k]=(t&rm) as Chunk; co=t>>rb;
        }
        for k in rom::NLEN ..2*rom::NLEN-1 {
            s-=d[k-rom::NLEN]; t=co+s;
            let mut i=1+k/2;
            while i<rom::NLEN {
                t+=((a.w[i]-a.w[k-i]) as DChunk)*((b.w[k-i]-b.w[i]) as DChunk);
                i+=1;
            }
        
            c.w[k]=(t&rm) as Chunk; co=t>>rb;
        }
        c.w[2*rom::NLEN-1]=co as Chunk;
        return c;
    }

/* return a^2 as DBIG */
#[cfg(target_pointer_width = "32")]
    pub fn sqr(a: &BIG) -> DBIG {
        let mut c=DBIG::new();
        let rm=rom::BMASK as DChunk;
        let rb=rom::BASEBITS;
    //    a.norm();
 
        let mut t=(a.w[0] as DChunk)*(a.w[0] as DChunk);
        c.w[0]=(t&rm) as Chunk; let mut co=t>>rb;
        t=(a.w[1] as DChunk)*(a.w[0] as DChunk); t+=t; t+=co;
        c.w[1]=(t&rm) as Chunk; co=t>>rb;
        
        let last=rom::NLEN-(rom::NLEN%2);
        let mut j=2;
        while j<last {
            t=(a.w[j] as DChunk)*(a.w[0] as DChunk); for i in 1 ..(j+1)/2 {t+=(a.w[j-i] as DChunk)*(a.w[i] as DChunk)} ; t+=t; t+=co; t+=(a.w[j/2] as DChunk)*(a.w[j/2] as DChunk);
            c.w[j]=(t&rm) as Chunk; co=t>>rb;
            t=(a.w[j+1] as DChunk)*(a.w[0] as DChunk); for i in 1 ..(j+2)/2 {t+=(a.w[j+1-i] as DChunk)*(a.w[i] as DChunk)} ; t+=t; t+=co;
            c.w[j+1]=(t&rm) as Chunk; co=t>>rb;
            j+=2;
        }
        j=last;
        if rom::NLEN%2==1 {
            t=(a.w[j] as DChunk)*(a.w[0] as DChunk); for i in 1 ..(j+1)/2 {t+=(a.w[j-i] as DChunk)*(a.w[i] as DChunk)} ; t+=t; t+=co; t+=(a.w[j/2] as DChunk)*(a.w[j/2] as DChunk);
            c.w[j]=(t&rm) as Chunk; co=t>>rb; j += 1;
            t=(a.w[rom::NLEN-1] as DChunk)*(a.w[j-rom::NLEN+1] as DChunk); for i in j-rom::NLEN+2 ..(j+1)/2 {t+=(a.w[j-i] as DChunk)*(a.w[i] as DChunk)}; t+=t; t+=co;
            c.w[j]=(t&rm) as Chunk; co=t>>rb; j += 1;
        }
        while j<rom::DNLEN-2 {
            t=(a.w[rom::NLEN-1] as DChunk)*(a.w[j-rom::NLEN+1] as DChunk); for i in j-rom::NLEN+2 ..(j+1)/2 {t+=(a.w[j-i] as DChunk)*(a.w[i] as DChunk)} ; t+=t; t+=co; t+=(a.w[j/2] as DChunk)*(a.w[j/2] as DChunk);
            c.w[j]=(t&rm) as Chunk; co=t>>rb;
            t=(a.w[rom::NLEN-1] as DChunk)*(a.w[j-rom::NLEN+2] as DChunk); for i in j-rom::NLEN+3 ..(j+2)/2 {t+=(a.w[j+1-i] as DChunk)*(a.w[i] as DChunk)} ; t+=t; t+=co;
            c.w[j+1]=(t&rm) as Chunk; co=t>>rb;
            j+=2;
        }
        t=(a.w[rom::NLEN-1] as DChunk)*(a.w[rom::NLEN-1] as DChunk)+co;
        c.w[rom::DNLEN-2]=(t&rm) as Chunk; co=t>>rb;
        c.w[rom::DNLEN-1]=co as Chunk;
        
        return c;
    }


#[cfg(target_pointer_width = "32")]
    fn monty(d: &mut DBIG) -> BIG {
        let mut b=BIG::new();           
        let md=BIG::new_ints(&rom::MODULUS);
        let rm=rom::BMASK as DChunk;
        let rb=rom::BASEBITS;

        let mut dd: [DChunk; rom::NLEN] = [0; rom::NLEN];
        let mut v: [Chunk; rom::NLEN] = [0; rom::NLEN];
            
        b.zero();
            
        let mut t=d.w[0] as DChunk; v[0]=(((t&rm) as Chunk).wrapping_mul(rom::MCONST))&rom::BMASK; t+=(v[0] as DChunk)*(md.w[0] as DChunk); let mut c=(d.w[1] as DChunk)+(t>>rb); let mut s:DChunk=0;
        for k in 1 ..rom::NLEN {
            t=c+s+(v[0] as DChunk)*(md.w[k] as DChunk);
            let mut i=1+k/2;
            while i<k {
                t+=((v[k-i]-v[i]) as DChunk)*((md.w[i]-md.w[k-i]) as DChunk);
                i+=1;
            }
            v[k]=(((t&rm) as Chunk).wrapping_mul(rom::MCONST))&rom::BMASK; t+=(v[k] as DChunk)*(md.w[0] as DChunk); c=(d.w[k+1] as DChunk)+(t>>rb);
            dd[k]=(v[k] as DChunk)*(md.w[k] as DChunk); s+=dd[k];
        }
            
        for k in rom::NLEN ..2*rom::NLEN-1
        {
            t=c+s;
            let mut i=1+k/2;
            while i<rom::NLEN {
                t+=((v[k-i]-v[i]) as DChunk)*((md.w[i]-md.w[k-i]) as DChunk);
                i+=1;
            }
            b.w[k-rom::NLEN]=(t&rm) as Chunk; c=(d.w[k+1] as DChunk)+(t>>rb); s-=dd[k-rom::NLEN+1];
        }
        b.w[rom::NLEN-1]=(c&rm) as Chunk;  
        b.norm();
        return b;
    }
    

/* return a*b as DBIG */
#[cfg(target_pointer_width = "64")]
    pub fn mul(a: &BIG,b: &BIG) -> DBIG {
        let mut c=DBIG::new();
        let mut carry;

        for i in 0 ..rom::NLEN {
            carry=0;
            for j in 0 ..rom::NLEN {
                let tuple=BIG::muladd(a.w[i],b.w[j],carry,c.w[i+j]);
                carry=tuple.0; c.w[i+j]=tuple.1;
            }
            c.w[rom::NLEN+i]=carry;
        }
        return c;
    } 

/* return a^2 as DBIG */
#[cfg(target_pointer_width = "64")]
    pub fn sqr(a: &BIG) -> DBIG {
        let mut c=DBIG::new();
        let mut carry;

        for i in 0 ..rom::NLEN {
            carry=0;
            for j in i+1 ..rom::NLEN {
                let tuple=BIG::muladd(2*a.w[i],a.w[j],carry,c.w[i+j]);
                carry=tuple.0; c.w[i+j]=tuple.1;
            //carry,c.w[i+j]=muladd(2*a.w[i],a.w[j],carry,c.w[i+j])
            //carry=c.muladd(2*a.w[i],a.w[j],carry,i+j)
            }
            c.w[rom::NLEN+i]=carry;
        }

        for i in 0 ..rom::NLEN {
            let tuple=BIG::muladd(a.w[i],a.w[i],0,c.w[2*i]);
            c.w[2*i]=tuple.1;
            c.w[2*i+1]+=tuple.0;
        //c.w[2*i+1]+=c.muladd(a.w[i],a.w[i],0,2*i)
        }
        c.norm();
        return c;
    } 

#[cfg(target_pointer_width = "64")]
    fn monty(d: &mut DBIG) -> BIG {
        let mut b=BIG::new();     
        let md=BIG::new_ints(&rom::MODULUS);
        let mut carry;
        let mut m;
        for i in 0 ..rom::NLEN {
            if rom::MCONST==-1 { 
                m=(-d.w[i])&rom::BMASK;
            } else {
                if rom::MCONST==1 {
                    m=d.w[i];
                } else {
                    m=(rom::MCONST.wrapping_mul(d.w[i]))&rom::BMASK;
                }
            }

            carry=0;
            for j in 0 ..rom::NLEN {
                let tuple=BIG::muladd(m,md.w[j],carry,d.w[i+j]);
                carry=tuple.0; d.w[i+j]=tuple.1;
            }
            d.w[rom::NLEN+i]+=carry;
        }

        for i in 0 ..rom::NLEN {
            b.w[i]=d.w[rom::NLEN+i];
        } 
        b.norm();
        return b;  
    }


/* reduce a DBIG to a BIG using the appropriate form of the modulus */
/* dd */
    pub fn modulo(d: &mut DBIG) -> BIG {
    
        if rom::MODTYPE==rom::PSEUDO_MERSENNE {
            let mut b=BIG::new();
            let mut t=d.split(rom::MODBITS);
            b.dcopy(&d);
            let v=t.pmul(rom::MCONST as isize);
            let tw=t.w[rom::NLEN-1];
            t.w[rom::NLEN-1] &= rom::TMASK;
            t.w[0]+=rom::MCONST*((tw>>rom::TBITS)+(v<<(rom::BASEBITS-rom::TBITS)));
    
            b.add(&t);
            b.norm();
            return b;
        }
    
        if rom::MODTYPE==rom::MONTGOMERY_FRIENDLY
        {
            let mut b=BIG::new();
            for i in 0 ..rom::NLEN {
                let x=d.w[i];

                let tuple=BIG::muladd(x,rom::MCONST-1,x,d.w[rom::NLEN+i-1]);
                d.w[rom::NLEN+i]+=tuple.0; d.w[rom::NLEN+i-1]=tuple.1;
            }
    
            b.zero();
    
            for i in 0 ..rom::NLEN {
                b.w[i]=d.w[rom::NLEN+i];
            }
            b.norm();
            return b;
        }
            
        if rom::MODTYPE==rom::GENERALISED_MERSENNE
        { // GoldiLocks Only
            let mut b=BIG::new();            
            let t=d.split(rom::MODBITS);
            let rm2=(rom::MODBITS/2) as usize;
            b.dcopy(&d);
            b.add(&t);
            let mut dd=DBIG::new_scopy(&t);
            dd.shl(rm2);
            
            let mut tt=dd.split(rom::MODBITS);
            let lo=BIG::new_dcopy(&dd);
            b.add(&tt);
            b.add(&lo);
            b.norm();
            tt.shl(rm2);
            b.add(&tt);
            
            let carry=b.w[rom::NLEN-1]>>rom::TBITS;
            b.w[rom::NLEN-1]&=rom::TMASK;
            b.w[0]+=carry;
            
            b.w[(224/rom::BASEBITS) as usize]+=carry<<(224%rom::BASEBITS);
            b.norm();
            return b;
        }
       
        if rom::MODTYPE==rom::NOT_SPECIAL {
            return BIG::monty(d);
        }     
        return BIG::new();
    }

    /* return a*b mod m */
    pub fn modmul(a: &mut BIG,b: &mut BIG,m: &BIG) -> BIG {
        a.rmod(m);
        b.rmod(m);
        let mut d=BIG::mul(a,b);
        return d.dmod(m);
    }
    
    /* return a^2 mod m */
    pub fn modsqr(a: &mut BIG,m: &BIG) -> BIG {
        a.rmod(m);
        let mut d=BIG::sqr(a);
        return d.dmod(m);
    }
    
    /* return -a mod m */
    pub fn modneg(a: &mut BIG,m: &BIG) -> BIG {
        a.rmod(m);
        return m.minus(a);
    }

    /* return this^e mod m */
    pub fn powmod(&mut self,e: &mut BIG,m: &BIG) -> BIG {
        self.norm();
        e.norm();
        let mut a=BIG::new_int(1);
        let mut z=BIG::new_copy(e);
        let mut s=BIG::new_copy(self);
        loop {      
            let bt=z.parity();       
            z.fshr(1);    
            if bt==1 {a=BIG::modmul(&mut a,&mut s,m)}
            if z.iszilch() {break}
            s=BIG::modsqr(&mut s,m);         
        }
        return a;
    }

}
 
/*
fn main() {
	let fd: [i32; rom::NLEN as usize] = [1, 2, 3, 4, 5, 6, 7, 8, 9];	
	let mut x= BIG::new();
	x.inc(3);
 	println!("{}", x.w[0]);	
 	let mut y= BIG::new_int(7);
 	println!("{}", y.w[0]);	
 	y=BIG::new_copy(&x);
	println!("{}", y.w[0]); 	
	x.add(&y);
	x.add(&y);
	println!("{}", x.w[0]); 	
	let mut z= BIG::new_ints(&fd);
	println!("{}", z.w[0]); 	
	z.shr(3);
	z.norm();
	println!("{:X}", z.w[0]); 	

	println!("{}",z.tostring());

    let mut a = BIG::new_int(3);
    let mut m = BIG::new_ints(&MODULUS);

    println!("rom::MODULUS= {}",m.tostring());

    let mut e = BIG::new_copy(&m);
    e.dec(1); e.norm();
    println!("Exponent= {}",e.tostring());
//    for i in 0..20
//    {
        a=a.powmod(&mut e,&mut m);
//        a.inc(2);
//    }
    println!("Result= {}",a.tostring());

}
*/