#include <stdint.h>
#include <string.h>
#include <stdio.h>

//#define PRINT_RANGES
#define FAST_ATOI64
#define TEST_RANGE 0x1000000U

static const char * const itoa64 =
	"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

#ifdef FAST_ATOI64
static const uint8_t atoi64_partial[77] = {
	0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
	64, 64, 64, 64, 64, 64, 64,
	12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
	25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37,
	64, 64, 64, 64, 64, 64,
	38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
	51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63
};
#endif

static char *encode64_uint32(char *dst, size_t dstlen, uint32_t src)
{
	uint32_t start = 0, end = 47, chars = 1, bits = 0;

	do {
		uint32_t count = (end + 1 - start) << bits;
		if (src < count)
			break;
		if (start >= 63)
			return NULL;
		start = end + 1;
		end = start + (62 - end) / 2;
		src -= count;
		chars++;
		bits += 6;
	} while (1);

	if (dstlen <= chars) /* require room for a NUL terminator */
		return NULL;

	*dst++ = itoa64[start + (src >> bits)];

	while (--chars) {
		bits -= 6;
		*dst++ = itoa64[(src >> bits) & 0x3f];
	}

	*dst = 0; /* NUL terminate just in case */

	return dst;
}

static inline uint32_t atoi64(char src)
{
#ifdef FAST_ATOI64
	if (src >= '.' && src <= 'z')
		return atoi64_partial[(unsigned int)(unsigned char)src - '.'];
#else
	const char *ptr = strchr(itoa64, src);
	if (ptr)
		return ptr - itoa64;
#endif
	return 64;
}

static const char *decode64_uint32(uint32_t *dst, const char *src)
{
	uint32_t start = 0, end = 47, chars = 1, bits = 0;
	uint32_t c;

	c = atoi64(*src++);
	if (c > 63)
		goto fail;

	*dst = 0;
	while (c > end) {
		*dst += (end + 1 - start) << bits;
		start = end + 1;
		end = start + (62 - end) / 2;
		chars++;
		bits += 6;
	}

	*dst += (c - start) << bits;

	while (--chars) {
		c = atoi64(*src++);
		if (c > 63)
			goto fail;
		bits -= 6;
		*dst += c << bits;
	}

	return src;

fail:
	*dst = 0;
	return NULL;
}

static void print_encode64_uint32(uint32_t src)
{
	char buf[7];

	if (encode64_uint32(buf, sizeof(buf), src)) {
		uint32_t dst;
		if (decode64_uint32(&dst, buf) && dst == src)
			printf("%u\t%s\n", src, buf);
		else
			printf("%u\t%s\tdecoded to %u\n", src, buf, dst);
	} else
		printf("%u\tcouldn't encode\n", src);
}

static void test_encode64_uint32(size_t dstlen, uint32_t count)
{
	char buf[7];
	uint32_t range;

	if (dstlen > sizeof(buf)) {
		printf("Can't test dstlen %u\n", (unsigned int)dstlen);
		return;
	}

	range = 0;
	do {
		uint32_t offset;

		fprintf(stderr, "Testing %u to %u\r",
		    range, range + (TEST_RANGE - 1));

#ifdef _OPENMP
#pragma omp parallel for default(none) shared(dstlen, count, range) private(buf)
#endif
		for (offset = 0; offset < TEST_RANGE - 1; offset++) {
			uint32_t src = range + offset;
			if (encode64_uint32(buf, dstlen, src)) {
				uint32_t dst;
				if (decode64_uint32(&dst, buf) && dst == src) {
					if (src >= count)
						printf("\n%u\t%s\tunexpected\n",
						    src, buf);
					continue;
				}
				printf("\n%u\t%s\tdecoded to %u\n",
				    src, buf, dst);
			} else if (src < count)
				printf("\n%u\tcouldn't encode\n", src);
		}
	} while ((range += TEST_RANGE));

	printf("\ndstlen %u done\n", (unsigned int)dstlen);
}

#ifdef PRINT_RANGES
static void print_ranges(unsigned int first)
{
	unsigned int start = 0, end = first, chars = 1, bits = 0;
	unsigned long long base = 0;

	do {
		unsigned long long count =
		    (unsigned long long)(end + 1 - start) << bits;
		printf("%2u to %2u - %u char%s, range %llu to %llu\n",
		    start, end,
		    chars, chars == 1 ? "" : "s", base, base + count - 1);
		start = end + 1;
		end = start + (62 - end) / 2;
		chars++;
		base += count;
		bits += 6;
	} while (end <= 63);
}
#endif

int main(void)
{
	print_encode64_uint32(0);
	print_encode64_uint32(47);
	print_encode64_uint32(48);
	print_encode64_uint32(559);
	print_encode64_uint32(560);
	print_encode64_uint32(16943);
	print_encode64_uint32(16944);
	print_encode64_uint32(541231);
	print_encode64_uint32(541232);
	print_encode64_uint32(17318447);
	print_encode64_uint32(17318448);
	print_encode64_uint32(1091060271);
	print_encode64_uint32(1091060272);
	print_encode64_uint32(0x7fffffffU);
	print_encode64_uint32(0x80000000U);
	print_encode64_uint32(0xffffffffU);

#ifdef PRINT_RANGES
	print_ranges(15);
	puts("");
	print_ranges(31);
	puts("");
	print_ranges(47);
	puts("");
	print_ranges(55);
#endif

	test_encode64_uint32(7, 1091060272);
	test_encode64_uint32(6, 17318448);
	test_encode64_uint32(5, 541232);
	test_encode64_uint32(4, 16944);
	test_encode64_uint32(3, 560);
	test_encode64_uint32(2, 48);
	test_encode64_uint32(1, 0);

	return 0;
}