#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <openssl/sha.h>

// todo maybe use clz cpu instruction
int count_leading_zeroes(unsigned char* hash, int len) {
	int count = 0;
	for(int i = 0; i < len; i++) {
		if(hash[i] != 0) {
			if(hash[i] & 128) return count;
			else if(hash[i] & 64) return count + 1;
			else if(hash[i] & 32) return count + 2;
			else if(hash[i] & 16) return count + 3;
			else if(hash[i] & 8) return count + 4;
			else if(hash[i] & 4) return count + 5;
			else if(hash[i] & 2) return count + 6;
			else if(hash[i] & 1) return count + 7;
		} else count += 8;
	}
	return count;
}

int HASH_LENGTH = 256 / 8;

double timediff(struct timespec *tstart, struct timespec *tend) {
	return ((double)tend->tv_sec + 1.0e-9*tend->tv_nsec) - 
           ((double)tstart->tv_sec + 1.0e-9*tstart->tv_nsec);
}

int print_every = (int)1e8;

char* ToString(char* bufferEnd, uint64_t i) {
	// http://stackoverflow.com/a/18859192/2639190
	char *p = bufferEnd;
	*(--p) = '\0';
	lldiv_t qr;
	qr.quot = i;
	do {
		qr = lldiv(qr.quot, 10);
		*(--p) = llabs(qr.rem) + '0';
	} while (qr.quot);
	return p;
}

int main(int argc, char **argv) {
	int minbits = atoi(argv[1]);
	struct timespec begin;
	clock_gettime(CLOCK_MONOTONIC, &begin);
	char message_constant[200];
	int message_constant_len = sprintf(message_constant, "%s %09ld.", argv[2], begin.tv_nsec);
	unsigned char hash[HASH_LENGTH];
	SHA256_CTX constant_ctx;
	SHA256_Init(&constant_ctx);
	SHA256_Update(&constant_ctx, message_constant, message_constant_len);
	SHA256_CTX full_ctx;
	char message_tail_buf[200];
	for(uint64_t i = 0; i < 1e16; i++) {
		full_ctx = constant_ctx;
		char* message_tail = ToString(message_tail_buf + 200, i);
		SHA256_Update(&full_ctx, message_tail, (message_tail_buf + 200) - message_tail - 1);
		SHA256_Final(hash, &full_ctx);
		if(i!=0 && i%print_every == 0) {
			struct timespec end; clock_gettime(CLOCK_MONOTONIC, &end);
			fprintf(stderr, "%.3f MHash/s\n", print_every/1e6/(timediff(&begin, &end)));
			begin = end;
		}
		if(count_leading_zeroes(hash, HASH_LENGTH) >= minbits) {
			for(int i = 0; i < HASH_LENGTH; i++) printf("%02x", hash[i]);
			printf(" %s%s\n", message_constant, message_tail);
			return 0;
		}
	}
	return 0;
}