#include "util.h"
#include <iostream>

using namespace std;

int8 Util::jacobi(uint32 A, uint32 N) {
	
	int8 j = 1;
	uint32 X;
	
	while (A != 0) {
		while (A % 2 == 0) {
			A /= 2;
			if (N % 8 == 3 || N % 8 == 5)
				j *= -1;
		}
		X = A;
		A = N;
		N = X;
		if (A % 4 == 3 && N % 4 == 3)
			j *= -1;
		A %= N;
	}

	if (N != 1)
		j = 0;

	return j;
}

bool Util::isPrime3mod4(uint32 n) {
	
	if (n % 4 != 3)
		return false;

	return isPrime(n);

}

bool Util::isPrime(uint32 n) {

	uint32 i, upperLimit;
	
	upperLimit = (uint32)ceil(sqrt((unsigned long double)n));

	for (i = 3; i < upperLimit; i += 2)
		if (n % i == 0)
			return false;

	return true;

}

uint32 Util::hash(string id) {

	uint32 i, h;
	
	h = 0;
	for (i = 0; i < id.length(); i++) {
		h = 31 * h + id.at(i);
	}

	return h;	
}

uint32 Util::hash(string id, uint32 M) {

	uint32 h;
	uint32 position = (uint32)id.size() - 1;

	do {
		h = hash(id) % M;
		id.insert(0, id.at(position));
	} while (jacobi(h, M) != 1);	

	return h;	
}

uint32 Util::gcd(uint32 n1, uint32 n2) {

	uint32 remainder;

	remainder = n1 % n2;
	while (remainder != 0) {
		n1 = n2;
		n2 = remainder;
		remainder = n1 % n2;
	}

	return n2;
}

uint32 Util::powMod(uint32 base, uint32 exponent, uint32 modulus) {

	uint32 i;
	uint64 result = base;

	for (i = 1; i < exponent; i++) {
		result = (result * base) % modulus;
	}

	return (uint32)result;
}

uint32 Util::inv(uint32 n, uint32 M) {

	uint64 inverse;	

	inverse = 1;
	while ((inverse * n) % M != 1)
		inverse++;
	
	return (uint32)inverse;
	
}

uint32 Util::greater(uint32 n1, uint32 n2) {

	return (n1 > n2 ? n1 : n2);

}

uint32 Util::smaller(uint32 n1, uint32 n2) {

	return (n1 < n2 ? n1 : n2);

}

string Util::uint32ToString(uint32 n) {

	string s;
	char c[5];
	int i;
	union {
		uint32 u32;
		uint8  u8[4];
	} u;

	u.u32 = n;
	
	for (i = 0; i < 4; i++)
		c[i] = (u.u8[i] == 0 ? ' ' : (char)u.u8[i]);
	c[i] = '\0';

	s.append(c);
	return s;
	
}