#include <stdlib.h>			// Provides malloc and abs
#include <string.h>			// For string-handling functions
#include <assert.h>			// Provides assert
#include <math.h>			// For ceil() and other fun functions
#include <gmp.h>			// Provides the mpz_* functions
#include <jni.h>			// Provides the JNI interface
#include 'BigInteger.h'		// Documents the class being implemented

/*
 * Definition of a common function type
 */
typedef void (*mpz_binop_t)(mpz_t,mpz_t,mpz_t);

/*
 * Structures used to organize class and method/field ids.
 */
static struct {
	jclass cls;
	jmethodID gc;
	jobject ref;
} system;

static struct {
	jclass cls;
	jfieldID ptr;
	jobject ref;
} bigint;

/*
 * This function attempts to allocate a new mpz_t, and if it can't, attempts to garbage collect.
 * If it still can't create a new mpz_t, attempts to throw an OutOfMemoryError and returs NULL.
 * This allocation method exists primarily to make the allocation process simpler, but also to
 * act as a pressure valve for Java's tendency to create a ton of intermediate objects.
 *
 * Since it isn't intended to be used beyond this file, it's not in BigInteger.h and it's stored
 * at the top here.
 */
mpz_t* allocate(JNIEnv * env)
{
	if((*env)->ExceptionOccurred(env)) return NULL;  // Don't pass me a bum environment!
	mpz_t* ptr = (mpz_t*)malloc(sizeof(mpz_t));
	if(ptr != NULL) return ptr;
	(*env)->CallStaticVoidMethod(env,system.cls,system.gc);
	ptr = (mpz_t*)malloc(sizeof(mpz_t));
	if(ptr == NULL) (*env)->ThrowNew(env,(*env)->FindClass(env,"java/lang/OutOfMemoryError"),"");
	return ptr;
}

/*
 * This function creates and initializes a new mpz_t named "rop", then performs a generic
 * three-argument mpz_t operation with the first argument being "rop", and then returns
 * the jlong value equivalent to rop's address.  In short, it provides the generic beginning
 * and ending code for most of the arithmatic methods.
 */
jlong binop_template(JNIEnv * env,mpz_binop_t mpz_f,mpz_t op1,mpz_t op2)
{
	mpz_t* newPtr = allocate(env);
	if(newPtr == NULL) return (jlong)0;
	mpz_init(*newPtr);
	mpz_f(*newPtr,op1,op2);
	return (jlong)newPtr;
}


/*
 * Class:     BigInteger
 * Method:    registerSystem
 * Signature: (Ljava/lang/Class;)V
 */
JNIEXPORT void JNICALL Java_BigInteger_registerSystem
  (JNIEnv * env, jclass objc, jclass sys)

{
	system.cls = sys;
	bigint.cls = objc;
	system.ref = (*env)->NewGlobalRef(env,sys);
	bigint.ref = (*env)->NewGlobalRef(env,objc);
	system.gc = (*env)->GetMethodID(env,sys,"gc","()V");
	bigint.ptr = (*env)->GetFieldID(env,objc,"ptr","J");
}

/*
 * Class:     BigInteger
 * Method:    allocateNativeBytes
 * Signature: ([B)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_allocateNativeBytes
  (JNIEnv * env, jclass objc, jbyteArray array)

{
	// Allocates a BigInteger consisting of precisely the bytes in "array" through
	// the mpz_import function, and then returns the long to it.  Returns 0 if there
	// is an error.
	jsize len = (*env)->GetArrayLength(env,array);
	mpz_t* newPtr = allocate(env);
	if(newPtr == NULL) return (jlong)0; // Error condition -- out of memory?
	jbyte* carr = (*env)->GetByteArrayElements(env,array,NULL);
	mpz_import(*newPtr,len,1,sizeof(jbyte),1,0,carr);
	(*env)->ReleaseByteArrayElements(env,array,JNI_ABORT); // JNI_ABORT -- should be no change.
	return (jlong)newPtr;
}

/*
 * Class:     BigInteger
 * Method:    allocateNativeSignum
 * Signature: (I[B)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_allocateNativeSignum
  (JNIEnv * env, jclass objc, jint signum, jbyteArray array)

{
	// Allocates the bytes of "array" precisely, and then makes sure that the
	// sign of the BigInteger is the same as "signum".  Returns 0 if there is
	// an error.
	mpz_t* newPtr = (mpz_t*)allocateNativeBytes(env,obj,array);
	if(newPtr == 0) return (jlong)0; // Propogating an error condition
	if(signum != mpz_sgn(*newPtr)) mpz_neg(*newPtr,*newPtr);
	return (jlong)newPtr;
}

/*
 * Class:     BigInteger
 * Method:    allocateNativeString
 * Signature: (Ljava/lang/String;I)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_allocateNativeString
  (JNIEnv * env, jclass objc, jstring str, jint radix)

{
	// This code is really ugly due to extensive error checking.  It attempts to allocate
	// a biginteger based on the string "str", assuming that it is in radix "radix".  Assuming
	// everything works, it's almost fast.  If things fail, it throws an exception and returns 0.

	// First make sure we can get the string's characters
	char* chars = (char*)(*env)->GetStringUTFChars(env, str, NULL);
	if(chars == NULL) {
		if(!(*env)->ExceptionOccurred(env)) {
			jclass exc = (*env)->FindClass(env,"java/lang/InternalError");
			(*env)->ThrowNew(env,exc,"Could not acquire String characters");
		}
		return (jlong)0;
	}

	// Now allocate a new mpz_t
	mpz_t* newPtr = allocate(env);
	if(newPtr == NULL) return (jlong)0; // Propogating an error condition

	// Now initialize the mpz_t with the respective chars and let them go
	int err = mpz_init_set_str(*newPtr,chars,radix);
	(*env)->ReleaseStringUTFChars(env, str, chars);
	if(err) {
		jclass badNumber = (*env)->FindClass(env, "java/lang/NumberFormatException");
		(*env)->ThrowNew(env,badNumber,"");
		mpz_clear(*newPtr);
		free((void*)newPtr);
		return (jlong)0;
	}
	return (jlong)newPtr;
}

/*
 * Class:     BigInteger
 * Method:    allocateNativeBlock
 * Signature: (I[B)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_allocateNativeBlock
  (JNIEnv * env, jclass objc, jint numbits, jbyteArray array)
{
	// Allocates a BigInteger built on array consisting of precisely numbits bits.  The
	// array may not consist of FEWER bytes than ceil(numbits/8), but may consist of more.
	// If there is an error, returns 0.
	mpz_t* newPtr = (mpz_t*)Java_BigInteger_allocateNativeBytes(env,objc,array);
	if((*env)->ExceptionOccurred(env) || newPtr == 0) return (jlong)0; // Error condition
	mpz_setbit(*newPtr,0); // Make sure it's 1 here -- big enough for the bitlength
	if(mpz_sizeinbase(*newPtr,2) > numbits) {
		mpz_tdiv_q_2exp(*newPtr,*newPtr,mpz_sizeinbase(*newPtr,2) - numbits); // Bit shift
		mpz_setbit(*newPtr,0); // Make sure it's 1 here -- big enough for the bitlength
	}
	return (jlong)newPtr;
}

/*
 * Class:     BigInteger
 * Method:    allocateNativeRandom
 * Signature: (IILjava/util/Random;)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_allocateNativeRandom
{
	// Allocates a random BigInteger that is probably prime using "certainty" certainty tests
	// (at least (1/2)^certainty certainty), "rnd" as the random number generator, and consisting
	// of "bitlength" length.  The exception checking is probably a bit over-intense here, but
	// this isn't expected to be a "quick" method, and it's better to be safe than sorry.

	// Create the byte array we'll be working with
	jsize byteLen = bitlength/8;
	if(bitlength % 8) byteLen++; // Fix truncation problems
	jbyteArray array = (*env)->NewByteArray(env,byteLen);
	if((*env)->ExceptionOccurred(env)) return (jlong)0;

	// Now get the method we'll be using to generate the random bytes
	jmethodID randMethod = (*env)->GetMethodID(env,
											   (*env)->GetObjectClass(env,rnd),
											   "nextBytes",
											   "([B)V");
	if((*env)->ExceptionOccurred(env)) return (jlong)0;

	// Now generate the prime
	mpz_t* newPtr = NULL;
	do {
		// Clean up if we need to
		if(newPtr) {
			mpz_clear(*newPtr);
			free((void*)newPtr);
			newPtr = NULL;
		}

		// Generate the random bytes
		(*env)->CallVoidMethod(env,rnd,randMethod,array);
		if((*env)->ExceptionOccurred(env)) return (jlong)0;

		// Create a prime BigInteger of bitlength length
		newPtr = (mpz_t*)Java_BigInteger_allocateNativeBlock(env,objc,bitlength,array);
		if((*env)->ExceptionOccurred(env) || newPtr == NULL) return (jlong)0;
		mpz_nextprime(*newPtr,*newPtr); // Actually generate the next highest prime
	} while(mpz_sizeinbase(*newPtr,2) != bitLength ||
			!mpz_probab_prime_p(*newPtr,certainty));

	(*env)->DeleteLocalRef(env,array);
	return newPtr;
}

/*
 * Class:     BigInteger
 * Method:    valueOfNative
 * Signature: (J)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_valueOfNative
  (JNIEnv * env, jclass objc, jlong val)
{
	mpz_t* newPtr = allocate(env);
	if(newPtr == NULL) return (jlong)0;
	mpz_init_set_si(newPtr,val);
	return (jlong)newPtr;
}

/*
 * Class:     BigInteger
 * Method:    addNative
 * Signature: (JJ)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_addNative
  (JNIEnv * env, jclass objc, jlong melong, jlong themlong)

{
    assert((melong != 0) && (themlong != 0));
    return binop_template(env,&mpz_add,*((mpz_t*)melong),*((mpz_t*)themlong));
}

/*
 * Class:     BigInteger
 * Method:    subtractNative
 * Signature: (JJ)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_subtractNative
  (JNIEnv * env, jclass objc, jlong melong, jlong themlong)

{
    assert((melong != 0) && (themlong != 0));
	return binop_template(env,&mpz_subt,*((mpz_t*)melong),*((mpz_t*)themlong));
}

/*
 * Class:     BigInteger
 * Method:    multiplyNative
 * Signature: (JJ)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_multiplyNative
  (JNIEnv * env, jclass objc, jlong melong, jlong themlong)
{
    assert((melong != 0) && (themlong != 0));
	return binop_template(env,&mpz_mul,*((mpz_t*)melong),*((mpz_t*)themlong));
}

/*
 * Class:     BigInteger
 * Method:    divideNative
 * Signature: (JJ)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_divideNative
  (JNIEnv * env, jclass objc, jlong melong, jlong themlong)
{
    assert((melong != 0) && (themlong != 0));
	return binop_template(env,&mpz_tdiv_q,*((mpz_t*)melong),*((mpz_t*)themlong));
}

/*
 * Class:     BigInteger
 * Method:    divideAndRemainderNative
 * Signature: ([JJJ)V
 */
JNIEXPORT void JNICALL Java_BigInteger_divideAndRemainderNative
  (JNIEnv * env, jclass objc, jlongArray out, jlong melong, jlong themlong)
{
	// Get the pointers to the appropriate elements
    assert((melong != 0) && (themlong != 0));
	mpz_t* me = (mpz_t*)melong;
	mpz_t* them = (mpz_t*)themlong;

	// Get and initialize the quotient pointer
	mpz_t* qptr = allocate(env);
	if(qptr == NULL) return;
	mpz_init(*qptr);

	// Get and initialize the remainder pointer
	mpz_t* rptr = allocate(env);
	if(rptr == NULL) return;
	mpz_init(*rptr);

	// The division; all this support for effectively one line of code!
	mpz_tdiv_qr(*qptr,*rptr,*me,*them);

	// Place the results into the array and then return it
	jlong* outPtr = (*env)->GetLongArrayElements(env,out,NULL);
	if(outPtr == NULL) {
		if(!(*env)->ExceptionOccurred(env)) {
			jclass exc = (*env)->FindClass(env,"java/lang/InternalError");
			(*env)->ThrowNew(env,exc,"Could not acquire array elements");
		}

		// Clean up after ourselves
		mpz_clear(*qptr);
		mpz_clear(*rptr);
		free((void*)qptr);
		free((void*)rptr);
		return;
	}
	outPtr[0] = (jlong)qptr;
	outPtr[1] = (jlong)rptr;
	(*env)->ReleaseLongArrayElements(env,out,outPtr,NULL);
	return;
}

/*
 * Class:     BigInteger
 * Method:    remainderNative
 * Signature: (JJ)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_remainderNative
  (JNIEnv * env, jclass objc, jlong melong, jlong themlong)
{
    assert((melong != 0) && (themlong != 0));
	return binop_template(env,&mpz_tdiv_r,*((mpz_t*)melong),*((mpz_t*)themlong));
}

/*
 * Class:     BigInteger
 * Method:    powNative
 * Signature: (JI)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_powNative
  (JNIEnv * env, jclass objc, jlong melong, jint pow)

{
    assert(melong != 0);
	mpz_t* me = (mpz_t*)melong;
	mpz_t* newPtr = allocate(env);
	if(newPtr == NULL) return (jlong)0;
	mpz_init(*newPtr);
	mpz_pow_ui(*newPtr,*me,(unsigned long)pow);
	return (jlong)newPtr;
}

/*
 * Class:     BigInteger
 * Method:    gcdNative
 * Signature: (JJ)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_gcdNative
  (JNIEnv * env, jclass objc, jlong melong, jlong themlong)
{
    assert((melong != 0) && (themlong != 0));
	return binop_template(env,&mpz_gcd,*((mpz_t*)melong),*((mpz_t*)themlong));
}

/*
 * Class:     BigInteger
 * Method:    negateNative
 * Signature: (J)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_negateNative
  (JNIEnv * env, jclass objc, jlong melong)

{
    assert(melong != 0);
	mpz_t* me = (mpz_t*)melong;
	mpz_t* newPtr = allocate(env);
	if(newPtr == NULL) return (jlong)0;
	mpz_init_set(*newPtr,*me);
	mpz_neg(*newPtr,*newPtr);
	return (jlong)newPtr;
}

/*
 * Class:     BigInteger
 * Method:    signum
 * Signature: ()I
 */
JNIEXPORT jint JNICALL Java_BigInteger_signum
  (JNIEnv * env, jobject obj)

{
	mpz_t* me = (mpz_t*)((*env)->GetLongField(env,obj,bigint.ptr));
	return (jint)mpz_sgn(*me);
}

/*
 * Class:     BigInteger
 * Method:    modNative
 * Signature: (JJ)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_modNative
  (JNIEnv * env, jclass objc, jlong melong, jlong themlong)
{
    assert((melong != 0) && (themlong != 0));
	return binop_template(env,&mpz_mod,*((mpz_t*)melong),*((mpz_t*)themlong));
}

/*
 * Class:     BigInteger
 * Method:    modPowNative
 * Signature: (JJJ)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_modPowNative
  (JNIEnv * env, jclass objc, jlong melong, jlong explong, jlong modlong)

{
	// Get the pointers in order
    assert((melong != 0) && (explong != 0) && (modlong != 0));
	mpz_t* me = (mpz_t*)melong;
	mpz_t* exp = (mpz_t*)explong;
	mpz_t* mod = (mpz_t*)modlong;
	mpz_t* newPtr = allocate(env);
	if(newPtr == NULL) return (jlong)0;
	mpz_init(*newPtr);
	mpz_powm(*newPtr,*me,*exp,*mod);
	return (jlong)newPtr;
}

/*
 * Class:     BigInteger
 * Method:    modInverseNative
 * Signature: (JJ)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_modInverseNative
  (JNIEnv * env, jclass objc, jlong melong, jlong themlong)

{
    assert((melong != 0) && (themlong != 0));
	mpz_t* me = (mpz_t*)melong;
	mpz_t* them = (mpz_t*)themlong;
	mpz_t* newPtr = allocate(env);
	if(newPtr == NULL) return (jlong)0;
	mpz_init(*newPtr);
	int retVal = mpz_invert(*newPtr,*me,*them);
	if(retVal == 0) {
		jclass noInverse = (*env)->FindClass(env, "java/lang/ArithmeticException");
		(*env)->ThrowNew(env,noInverse,"No modular inverse found");
		mpz_clear(*newPtr);
		free((void*)newPtr);
		return (jlong)0;
	}
}

/*
 * Class:     BigInteger
 * Method:    shiftLeftNative
 * Signature: (JI)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_shiftLeftNative
  (JNIEnv * env, jclass objc, jlong melong, jint n)
{
    assert(melong != 0);
	mpz_t* me = (mpz_t*)melong;
	mpz_t* newPtr = allocate(env);
	if(newPtr == NULL) return (jlong)0;
	mpz_init(*newPtr);
	mpz_mul_2exp(*newPtr,*me,(unsigned long)n);
	return (jlong)newPtr;
}

/*
 * Class:     BigInteger
 * Method:    shiftRightNative
 * Signature: (JI)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_shiftRightNative
  (JNIEnv * env, jclass objc, jlong melong, jint n)
{
    assert(melong != 0);
	mpz_t* me = (mpz_t*)melong;
	mpz_t* newPtr = allocate(env);
	if(newPtr == NULL) return (jlong)0;
	mpz_init(*newPtr);
	mpz_tdiv_q_2exp(*newPtr,*me,(unsigned long)n);
	return (jlong)newPtr;
}

/*
 * Class:     BigInteger
 * Method:    andNative
 * Signature: (JJ)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_andNative
  (JNIEnv * env, jclass objc, jlong melong, jlong themlong)
{
    assert((melong != 0) && (themlong != 0));
	return binop_template(env,&mpz_and,*((mpz_t*)melong),*((mpz_t*)themlong));
}

/*
 * Class:     BigInteger
 * Method:    orNative
 * Signature: (JJ)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_orNative
  (JNIEnv * env, jclass objc, jlong melong, jlong themlong)
{
    assert((melong != 0) && (themlong != 0));
	return binop_template(env,&mpz_ior,*((mpz_t*)melong),*((mpz_t*)themlong));
}

/*
 * Class:     BigInteger
 * Method:    xorNative
 * Signature: (JJ)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_xorNative
  (JNIEnv * env, jclass objc, jlong melong, jlong themlong)
{
    assert((melong != 0) && (themlong != 0));
	return binop_template(env,&mpz_xor,*((mpz_t*)melong),*((mpz_t*)themlong));
}

/*
 * Class:     BigInteger
 * Method:    notNative
 * Signature: (J)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_notNative
  (JNIEnv * env, jclass objc, jlong melong)

{
    assert((melong != 0));
	mpz_t* me = (mpz_t*)melong;
	mpz_t* newPtr = allocate(env);
	if(newPtr == NULL) return (jlong)0;
	mpz_init_set(*newPtr,*me);
	mpz_com(*newPtr,*newPtr);
	return (jlong)newPtr;
}

/*
 * Class:     BigInteger
 * Method:    andNotNative
 * Signature: (JJ)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_andNotNative
  (JNIEnv * env, jclass objc, jlong melong, jlong themlong)

{
    assert((melong != 0) && (themlong != 0));
	mpz_t* me = (mpz_t*)melong;
	mpz_t* them = (mpz_t*)themlong;
	mpz_t* newPtr = allocate(env);
	if(newPtr == NULL) return (jlong)0;
	mpz_init_set(*newPtr,*me);
	mpz_com(*newPtr,*newPtr);
	mpz_and(*newPtr,*newPtr,*me);
	return (jlong)newPtr;
}

/*
 * Class:     BigInteger
 * Method:    testBit
 * Signature: (I)Z
 */
JNIEXPORT jboolean JNICALL Java_BigInteger_testBit
  (JNIEnv * env, jobject obj, jint n)

{
	if(n < 0) {
		jclass negBit = (*env)->FindClass(env, "java/lang/ArithmeticException");
		(*env)->ThrowNew(env,negBit,"Negative bit index");
		return (jboolean)JNI_FALSE;
	}
	mpz_t* me = (mpz_t*)((*env)->GetLongField(env,obj,bigint.ptr));
    assert(*me != NULL);
	return (jboolean)mpz_tstbit(*me, (unsigned long)n);
}

/*
 * Class:     BigInteger
 * Method:    setBitNative
 * Signature: (JI)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_setBitNative
  (JNIEnv * env, jclass objc, jlong melong, jint n)
{
    assert((melong != 0));
	mpz_t* me = (mpz_t*)melong;
	mpz_t* newPtr = allocate(env);
	if(newPtr == NULL) return (jlong)0;
	mpz_init_set(*newPtr,*me);
	mpz_setbit(*newPtr,(unsigned long)n);
	return (jlong)newPtr;
}

/*
 * Class:     BigInteger
 * Method:    clearBitNative
 * Signature: (JI)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_clearBitNative
  (JNIEnv * env, jclass objc, jlong melong, jint n)
{
    assert((melong != 0));
	mpz_t* me = (mpz_t*)melong;
	mpz_t* newPtr = allocate(env);
	if(newPtr == NULL) return (jlong)0;
	mpz_init_set(*newPtr,*me);
	mpz_clrbit(*newPtr,(unsigned long)n);
	return (jlong)newPtr;
}

/*
 * Class:     BigInteger
 * Method:    flipBitNative
 * Signature: (JI)J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_flipBitNative
  (JNIEnv * env, jclass objc, jlong melong, jint n)

{
    assert((melong != 0));
	mpz_t* me = (mpz_t*)melong;
	mpz_t* newPtr = allocate(env);
	if(newPtr == NULL) return (jlong)0;
	mpz_init_set(*newPtr,*me);
	if(mpz_tstbit(*me, (unsigned long)n) == 1) {
		mpz_setbit(*newPtr,(unsigned long)n);
	} else {
		mpz_clrbit(*newPtr,(unsigned long)n);
	}
	return (jlong)newPtr;
}

/*
 * Class:     BigInteger
 * Method:    getLowestSetBit
 * Signature: ()I
 */
JNIEXPORT jint JNICALL Java_BigInteger_getLowestSetBit
  (JNIEnv * env, jobject obj)

{
	mpz_t* me = (mpz_t*)((*env)->GetLongField(env,obj,bigint.ptr));
    assert(*me != NULL);
	return (jint)mpz_scan1(*me,0);
}

/*
 * Class:     BigInteger
 * Method:    bitLength
 * Signature: ()I
 */
JNIEXPORT jint JNICALL Java_BigInteger_bitLength
  (JNIEnv * env, jobject obj)
{
	mpz_t* me = (mpz_t*)((*env)->GetLongField(env,obj,bigint.ptr));
    assert(*me != NULL);
	return (jint)mpz_sizeinbase(*me,2);
}

/*
 * Class:     BigInteger
 * Method:    bitCount
 * Signature: ()I
 */
JNIEXPORT jint JNICALL Java_BigInteger_bitCount
  (JNIEnv * env, jobject obj)

{
	mpz_t* me = (mpz_t*)((*env)->GetLongField(env,obj,bigint.ptr));
    assert(*me != NULL);
	if(mpz_sgn(*me) < 0) {
		mpz_t* tmp = allocate(env);
		if(tmp == NULL) return (jlong)0;
		mpz_init_set(*tmp,*me);
		mpz_com(*tmp,*tmp);
		jint n = (jint)mpz_popcount(*tmp);
		mpz_clear(*tmp);
		free((void*)tmp);
		return n;
	}
	return (jint)mpz_popcount(*me);
}

/*
 * Class:     BigInteger
 * Method:    isProbablePrime
 * Signature: (I)Z
 */
JNIEXPORT jboolean JNICALL Java_BigInteger_isProbablePrime
  (JNIEnv * env, jobject obj, jint n)

{
	if(n < 0) n = 1;
	mpz_t* me = (mpz_t*)((*env)->GetLongField(env,obj,bigint.ptr));
    assert(*me != NULL);
	if(mpz_probab_prime_p(*me,(unsigned long)n) == 0) return (jboolean)JNI_FALSE;
	return (jboolean)JNI_TRUE;
}

/*
 * Class:     BigInteger
 * Method:    compareTo
 * Signature: (Ljava/math/BigInteger;)I
 */
JNIEXPORT jint JNICALL Java_BigInteger_compareTo
  (JNIEnv *, jobject meobj, jobject themobj)

{
	if(themobj == NULL) {
		jclass nullPtr = (*env)->FindClass(env, "java/lang/NullPointerException");
		(*env)->ThrowNew(env,nullPtr,"Null parameter");
		return 1;
	}
	mpz_t* me = (mpz_t*)((*env)->GetLongField(env,meobj,bigint.ptr));
	mpz_t* them = (mpz_t*)((*env)->GetLongField(env,themobj,bigint.ptr));
	assert(me != NULL && them != NULL);

	int result = mpz_cmp(*me,*them);
	switch(result) {
		case -1:
		case 0:
		case 1:
			return result;
		default:
			return result/abs(result);
	}
}

/*
 * Class:     BigInteger
 * Method:    hashCodeNative
 * Signature: (J)I
 */
JNIEXPORT jint JNICALL Java_BigInteger_hashCodeNative
  (JNIEnv * env, jclass objc, jlong melong)

{
	// Okay, the trick here is generating a hashcode that's reflective of the BigInteger's value
	// but fits into 32 signed bits (the definition of a jint).
	// The way we're doing it is as follows: first, if the mpz fits into 32 bits, just return the
	// value of the mpz.  Otherwise, XOR all the limbs of the number together, and then shift-XOR
	// by 32 bits until the limb is at or under 32 bits.  Cast the limb to a jint (truncating it
	// if necessary), and return that resulting jint.
    assert((melong != 0));
	mpz_t* me = (mpz_t*)melong;
	if(sizeof(int) == 4) {
		if(mpz_fits_sint_p(*me)) return (jint)mpz_get_si(*me);
	} else if(sizeof(short) == 4) {
		if(mpz_fits_sshort_p(*me)) return (jint)mpz_get_si(*me);
	}
	mp_limb_t hash = 0;
	size_t len = mpz_size(*me);
	for(size_t i = 0; i < len; i++) {
		hash = hash ^ mpz_getlimbn(*me,i);
	}
	int limbsize = mp_bits_per_limb / 8;
	while(limbsize > 4) {
		hash = hash ^ (hash >> 4);
		limbsize = limbsize - 4;
	}
	return (jint)hash;
}

/*
 * Class:     BigInteger
 * Method:    toString
 * Signature: (I)Ljava/lang/String;
 */
JNIEXPORT jstring JNICALL Java_BigInteger_toString__I
  (JNIEnv * env, jobject obj, jint n)

{
	// Match the API by defaulting to 10
	if(n > 36 || n < 2) n = 10;

	// Find our pointer and then construct the string (checking for errors)
	mpz_t* me = (mpz_t*)((*env)->GetLongField(env,obj,bigint.ptr));
    assert(*me != NULL);
	char* str = mpz_get_str(NULL,n,*me);
	jstring jstr = (*env)->NewStringUTF(env,str);
	if(jstr == NULL) {
		if(!(*env)->ExceptionOccurred(env)) {
			jclass exc = (*env)->FindClass(env,"java/lang/InternalError");
			(*env)->ThrowNew(env,exc,"Could not construct String");
		}
	}
	free((void*)str);
	return jstr;
}

/*
 * Class:     BigInteger
 * Method:    toString
 * Signature: ()Ljava/lang/String;
 */
JNIEXPORT jstring JNICALL Java_BigInteger_toString__
  (JNIEnv * env, jobject obj)

{
	return Java_BigInteger_toString__I(env,obj,(jint)10);
}

/*
 * Class:     BigInteger
 * Method:    toByteArray
 * Signature: ()[B
 */
JNIEXPORT jbyteArray JNICALL Java_BigInteger_toByteArray
  (JNIEnv * env, jobject obj)

{
	mpz_t* me = (mpz_t*)((*env)->GetLongField(env,obj,bigint.ptr));
    assert(*me != NULL);
	size_t cnt;
	jbyte* bytes = (jbyte*)mpz_export(NULL,&cnt,1,sizeof(jbyte),1,0,*me);
	if(bytes == NULL) {
		// obj == 0 -- stupid convention in mpz_export to return NULL in this case.
		bytes = malloc(1);
		bytes[0] = 0;
		cnt = 1;
	}

	// Construct the array; careful here to make sure things always work
	jbyteArray out = (*env)->NewByteArray(env,cnt);
	if(out == NULL) {
		if(!(*env)->ExceptionOccurred(env)) {
			jclass exc = (*env)->FindClass(env,"java/lang/InternalError");
			(*env)->ThrowNew(env,exc,"Could not construct new byte array");
		}
		free((void*)bytes);
		return NULL;
	}

	(*env)->SetByteArrayRegion(env,out,0,cnt,bytes);
	free((void*)bytes);
	if((*env)->ExceptionOccurred(env)) return NULL;
	return out;
}

/*
 * Class:     BigInteger
 * Method:    longValue
 * Signature: ()J
 */
JNIEXPORT jlong JNICALL Java_BigInteger_longValue
  (JNIEnv * env, jobject obj)

{
	mpz_t* me = (mpz_t*)((*env)->GetLongField(env,obj,bigint.ptr));
    assert(*me != NULL);
	return (jlong)mpz_get_si(*me);
}

/*
 * Class:     BigInteger
 * Method:    doubleValue
 * Signature: ()D
 */
JNIEXPORT jdouble JNICALL Java_BigInteger_doubleValue
  (JNIEnv * env, jobject obj)
{
	mpz_t* me = (mpz_t*)((*env)->GetLongField(env,obj,bigint.ptr));
    assert(*me != NULL);
	return (jlong)mpz_get_d(*me);
}

/*
 * Class:     BigInteger
 * Method:    finalizeNative
 * Signature: (J)V
 */
JNIEXPORT void JNICALL Java_BigInteger_finalizeNative
  (JNIEnv * env, jclass objc, jlong melong)

{
	mpz_t* me = (mpz_t*)melong;
    assert(*me != NULL);
	mpz_clear(*me);
	free((void*)me);
	return;
}

#ifdef __cplusplus
}
#endif
#endif