module passwd.util;

@safe:

import std.range.primitives;

import passwd.exception;
public import passwd.securewipe;

/// Fill buf with random bytes of cryptographic quality
void fillSecureRandom(ubyte[] buf) @nogc nothrow @trusted
{
	arc4random_buf(buf.ptr, buf.length);
}

/// Parses crypt(3) output or salt in Modular Crypt Format (MCF)
const(CryptPieces) cryptSplit(const(char)[] crypt) pure
{
	import std.algorithm.iteration : splitter;
	import std.algorithm.searching : canFind, startsWith;
	import std.utf : byCodeUnit;

	auto crypt_c = crypt.byCodeUnit;
	enforce!ValueException(crypt_c.startsWith("$"), "Hashed password must start with $");
	auto pieces = crypt_c.splitter('$');
	auto num_pieces = pieces.walkLength;
	enforce!ValueException(num_pieces >= 3 && num_pieces <= 5, "Expected 2 to 4 $ characters in hashed password");

	assert (pieces.front.empty);
	pieces.popFront();

	auto algo_id = pieces.front.source;
	pieces.popFront();

	const(char)[] params;
	// parameters are optional, but they always contain an '=', and the salt never does because it uses the B64 characters
	if (pieces.front.canFind('='))
	{
		params = pieces.front.source;
		pieces.popFront();
		enforce!ValueException(!pieces.empty, "Missing salt (or invalid salt containing = character)");
	}

	auto salt_txt = pieces.front.source;
	pieces.popFront();

	const(char)[] digest_txt;
	if (!pieces.empty)
	{
		digest_txt = pieces.front.source;
		pieces.popFront();
	}

	/*
		bcrypt's salt strings deviate a little from the usual MCF.

		There's no "param_name=" for the log_rounds param, and the B64-encoded digest gets concatenated directly to the B64 salt without a '$' separator.

		That means the parameter is currently in salt_txt, and the B64 salt has to be split from the B64 digest by length.
	*/
	if (algo_id.startsWith("2"))
	{
		params = salt_txt;
		// Valid example looks like $2b$04$WNiYqMnuLlK9V11NmAKCNeG4nDdfI2Uqvo1MTvCehk2D4F4FSbICy
		enforce!ValueException(digest_txt.length == 22 || digest_txt.length == 53, "Invalid bcrypt digest length");
		salt_txt = digest_txt[0..22];
		digest_txt = digest_txt[22..$];
	}

	enforce!ValueException(pieces.empty, "Trailing data or corrupted format of hashed password");
	return const(CryptPieces)(algo_id, params, salt_txt, digest_txt);
}

///
unittest
{
	const result = cryptSplit("$5$rounds=10000$saltstringsaltst$3xv.VbSHBb41AL9AvLeujZkZRBAwqFMz2.opqey6IcA");
	assert (result.algo_id == "5");
	assert (result.params == "rounds=10000");
	assert (result.salt_txt == "saltstringsaltst");
	assert (result.digest_txt == "3xv.VbSHBb41AL9AvLeujZkZRBAwqFMz2.opqey6IcA");
}

unittest
{
	assertThrown!ValueException(cryptSplit(""));
	assertThrown!ValueException(cryptSplit("$"));
	assertThrown!ValueException(cryptSplit("$$$$$$$$"));
	assertThrown!ValueException(cryptSplit("1$rounds=10$salt$"));
	cryptSplit("$5$salt");
	assertThrown!ValueException(cryptSplit("$5$salt$xyz$extra"));
	assertThrown!ValueException(cryptSplit("$5$rounds=10"));
	assertThrown!ValueException(cryptSplit("$5$salt$rounds=10$xyz"));
}

/// Result of parsing MCF data
struct CryptPieces
{
	char[] algo_id;  /// Standard ID for hashing algorithm
	char[] params;  /// Extra parameters for hashing algorithm (may be empty)
	char[] salt_txt;  /// Plain text salt string
	char[] digest_txt;  /// Plain text result of hashing algorithm
}

/**
	Encode data using crypt(3) base 64

	Note: This is *not* the same base 64 as used in many internet standards.
*/
string cryptB64Encode(const(ubyte)[] data) pure
{
	import std.array : appender;
	auto ret_app = appender!string;
	data.cryptB64Encode(ret_app);
	return ret_app.data;
}

unittest
{
	import std..string : representation;
	assert (cryptB64Encode([]) == "");
	assert (cryptB64Encode([0]) == "..");
	assert (cryptB64Encode([1]) == "/.");
	assert (cryptB64Encode("asdfqwer".representation) == "VB5Na3rRZ75");
	assert (cryptB64Encode([0xff]) == "z1");
	assert (cryptB64Encode([0xff, 0xff]) == "zzD");
	assert (cryptB64Encode([0xff, 0xff, 0xff]) == "zzzz");
	assert (cryptB64Encode([0xff, 0xff, 0xff, 0xff]) == "zzzzz1");
}

/**
	Encode data using crypt(3) base 64 to an output range

	Note: This is *not* the same base 64 as used in many internet standards.
*/
void cryptB64Encode(Out)(const(ubyte)[] data, ref Out output) if (isOutputRange!(Out, char))
{
	import std.range : chunks, retro;
	foreach (chunk; data.chunks(3))
	{
		uint v = 0;
		foreach (b; chunk.retro)
		{
			v <<= 8;
			v |= b;
		}

		// l + 1 == ceil(l * 8.0 / 6) for 1 <= l <= 3
		assert (1 <= chunk.length && chunk.length <= 3);
		v.cryptB64Chars(output, chunk.length+1);
	}
}

@nogc
unittest
{
	import std.utf : byCodeUnit;
	char[2] buf;
	auto buf_p = buf[].byCodeUnit;
	ubyte[1] data = [42];
	cryptB64Encode(data[], buf_p);
	assert (buf[0] == 'e');
	assert (buf[1] == '.');
}

// The base 64 used in MIME and other internet standards uses a different set of characters and has a padding scheme

/**
	Decode crypt(3) base 64 to an output range

	Note: This is *not* the same base 64 as used in many internet standards.
*/
void cryptB64Decode(Out)(const(char)[] data, ref Out output) if (isOutputRange!(Out, ubyte))
{
	int bits_count = 0;
	uint v = 0;
	foreach (char c; data)
	{
		v |= cryptB64DecodeChar(c) << bits_count;
		bits_count += 6;
		if (bits_count >= 8)
		{
			output.put(cast(ubyte)(v & 0xff));
			v >>= 8;
			bits_count -= 8;
		}
	}

	while (bits_count > 0)
	{
		output.put(cast(ubyte)(v & 0xff));
		v >>= 8;
		bits_count -= 8;
	}
	assert (v == 0);
}

unittest
{
	import std.array : appender;
	auto decoded_app = appender!(ubyte[]);
	assertThrown!ValueException("!!!".cryptB64Decode(decoded_app));
	"e.".cryptB64Decode(decoded_app);
	assert (decoded_app[] == [42, 0]);
}

unittest
{
	bool testRoundTrip(const(ubyte)[] d)
	{
		import std.array : appender;
		import std..string : chomp;
		import std.algorithm.searching : endsWith;
		// Because B64 is 6b and ubytes are 8b and there's no padding, the round trip can add some extra 0 values to the ends
		auto encoded_app = appender!(char[]);
		d.cryptB64Encode(encoded_app);
		auto encoded = encoded_app[].chomp(".");
		auto decoded_app = appender!(ubyte[]);
		encoded.cryptB64Decode(decoded_app);
		auto decoded = decoded_app[];
		if (decoded.endsWith([0])) decoded = decoded[0..$-1];
		return d == decoded;
	}

	import std..string : representation;
	assert (testRoundTrip([]));
	assert (testRoundTrip("0".representation));
	assert (testRoundTrip("01".representation));
	assert (testRoundTrip("012".representation));
	assert (testRoundTrip("0123".representation));
	assert (testRoundTrip("01234".representation));
	assert (testRoundTrip("012345".representation));
	assert (testRoundTrip("0123456".representation));
	assert (testRoundTrip("01234567".representation));
	assert (testRoundTrip("012345678".representation));
	assert (testRoundTrip("0123456789".representation));
}

package:

/// Write `length` bytes of `data` to an output range, repeating `data` as necessary
void stretchPut(Out)(ref Out output, const(ubyte)[] data, size_t length) if (isOutputRange!(Out, ubyte))
{
	import std.algorithm.iteration : joiner;
	import std.range : repeat, take;
	foreach (x; repeat(data).joiner.take(length)) output.put(x);
}

///
unittest
{
	import std.array : appender;
	auto result_app = appender!(ubyte[]);
	result_app.stretchPut([0, 1, 2], 7);
	assert (result_app[] == [0, 1, 2, 0, 1, 2, 0]);
}

/**
	Decompose a permutation into a series of swaps (0 i0) . (1 i1) . (2 i2) ...

	The decomposition can be naturally represented by the array [i0, i1, i2...].

	E.g., the permutation [2 1 0] decomposes to (0 2) . (1 1) . (2 2), meaning that taking element index 2,
	then element #1, then element #0 is equivalent to swapping #0 with #2, then swapping #1 with #1 (no-op),
	then swapping #2 with #2 (no-op).  The decomposition would be [2, 1, 2].  The last swap is always a no-op,
	so the decomposition can be shortened to [2, 1].

	The advantage of the swap decomposition form is that it lets the permutation be applied to an array in-place.
*/
size_t[] permSwapDecomposition(size_t[] perm) pure
{
	import std.algorithm.mutation : swap;
	import std.array : array;
	import std.range : iota;
	if (perm.length < 2) return [];
	// We calculate the decomposition by incrementally running the permutation on an array v.
	// v_idx_of[x] keeps track of the index of the value x in v, so if we need to bring x to the current position, j,
	// that's a swap of v[j] with v[v_idx_of[x]], so v_idx_of[x] gets added to the decomposition.
	// We can keep v_idx_of and v in sync by making appropriate swaps.
	auto v = iota(perm.length).array;
	auto v_idx_of = iota(perm.length).array;
	auto ret = new size_t[perm.length-1];
	foreach (j; 0..ret.length)
	{
		const x = perm[j];
		ret[j] = v_idx_of[x];
		const old = v[j];
		swap(v[j], v[v_idx_of[x]]);
		swap(v_idx_of[x], v_idx_of[old]);
	}
	return ret;
}

unittest
{
	assert (permSwapDecomposition([]) == []);
	assert (permSwapDecomposition([2, 1, 0]) == [2, 1]);

	// Test that the decomposition does what it's supposed to
	// I.e., make a list of swaps that's equivalent to the original permutation
	bool test(size_t[] perm)
	{
		import std.algorithm.mutation : swap;
		import std.array : array;
		import std.range : iota;
		auto decomp = permSwapDecomposition(perm);
		auto v = iota(perm.length).array;
		foreach (j; 0..decomp.length)
		{
			swap(v[j], v[decomp[j]]);
		}
		return v == perm;
	}

	assert (test([0]));
	assert (test([0, 1]));
	assert (test([1, 0]));

	assert (test([1, 0, 4, 2, 3,]));
	assert (test([2, 1, 4, 3, 0,]));
	assert (test([0, 4, 3, 2, 1,]));
	assert (test([1, 2, 0, 3, 4,]));
	assert (test([0, 2, 3, 4, 1,]));
	assert (test([4, 3, 2, 0, 1,]));

	assert (test([4, 3, 0, 2, 1, 5,]));
	assert (test([4, 3, 5, 0, 1, 2,]));
	assert (test([2, 0, 1, 5, 4, 3,]));
	assert (test([4, 5, 0, 2, 1, 3,]));
	assert (test([0, 1, 3, 5, 2, 4,]));
	assert (test([4, 2, 1, 3, 0, 5,]));
	assert (test([5, 2, 4, 1, 0, 3,]));
}

private:

/// libbsd's portable and robust cryptographic randomness generator
extern(C) void arc4random_buf(void *buf, size_t nbytes) @nogc nothrow;

immutable crypt_b64_tab = "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

/// Decode a single crypt(3) base 64 digit to its numerical value
ubyte cryptB64DecodeChar(char c) pure
{
	switch (c)
	{
		case 'a': .. case 'z':
			return cast(ubyte)(c - 'a' + 38);
		case 'A': .. case 'Z':
			return cast(ubyte)(c - 'A' + 12);
		static assert ('.' + 1 == '/' && '/' + 1 == '0');
		case '.': .. case '9':
			return cast(ubyte)(c - '.');
		default:
			throw new ValueException("Invalid (crypt) base 64 value");
	}
}

unittest
{
	foreach (j; 0..64)
	{
		assert (j == cryptB64DecodeChar(crypt_b64_tab[j]));
	}
}

/**
	Encode an integer to `num_chars` crypt(3) base 64 digits, writing to an output range

	Note: the caller is responsible for setting the right `num_chars` to output the value correctly.
*/
void cryptB64Chars(Out)(uint v, ref Out output, size_t num_chars) if (isOutputRange!(Out, char))
{
	while (num_chars--)
	{
		output.put(crypt_b64_tab[v & 0x3f]);
		v >>= 6;
	}
	assert (v == 0);
}