/*
 * origin: FreeBSD /usr/src/lib/libcrypt/crypt-md5.c
 * This is a heavily modified version for musl libc.
 */
/*-
 * Copyright (c) 2003 Poul-Henning Kamp
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <string.h>
#include <stdint.h>
#include "md5.h"

static unsigned char itoa64[] =
	"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

static char *to64(char *s, unsigned int v, int n)
{
	while (--n >= 0) {
		*s++ = itoa64[v & 0x3f];
		v >>= 6;
	}
	return s;
}

static char *md5crypt(const char *key, const char *setting, char *output)
{
	MD5_CTX ctx;
	unsigned char md[MD5_DIGEST_LENGTH];
	unsigned int i;
	unsigned int klen = strlen(key); // TODO: key limit: fit into unsigned int
	unsigned int slen;
	const char *salt;
	char *p;

	// TODO: missing $1$ or >8byte salt?
	/* check setting: $1$ followed by max 8 bytes salt until '$' or '\0' */
	if (setting[0] != '$' || setting[1] != '1' || setting[2] != '$')
		return 0;
	salt = setting + 3;
	for (i = 0; i < 8 && salt[i] && salt[i] != '$'; i++);
	slen = i;

	/* md5(key salt key) */
	MD5_Init(&ctx);
	MD5_Update(&ctx, key, klen);
	MD5_Update(&ctx, salt, slen);
	MD5_Update(&ctx, key, klen);
	MD5_Final(md, &ctx);

	/* md5(key $1$ salt repeated-md weird-key[0]-0) */
	MD5_Init(&ctx);
	MD5_Update(&ctx, key, klen);
	MD5_Update(&ctx, setting, 3 + slen);
	for (i = klen; i > sizeof md; i -= sizeof md)
		MD5_Update(&ctx, md, sizeof md);
	MD5_Update(&ctx, md, i);
	md[0] = 0;
	for (i = klen; i; i >>= 1)
		if (i & 1)
			MD5_Update(&ctx, md, 1);
		else
			MD5_Update(&ctx, key, 1);
	MD5_Final(md, &ctx);

	/* On a 60 MHz Pentium this takes 34 ms */
	for (i = 0; i < 1000; i++) {
		MD5_Init(&ctx);
		if (i % 2)
			MD5_Update(&ctx, key, klen);
		else
			MD5_Update(&ctx, md, sizeof md);
		if (i % 3)
			MD5_Update(&ctx, salt, slen);
		if (i % 7)
			MD5_Update(&ctx, key, klen);
		if (i % 2)
			MD5_Update(&ctx, md, sizeof md);
		else
			MD5_Update(&ctx, key, klen);
		MD5_Final(md, &ctx);
	}

	/* output is $1$<salt>$<hash> */
	memcpy(output, setting, 3 + slen);
	p = output + 3 + slen;
	*p++ = '$';
	// TODO: assumes >24 bit int
	p = to64(p, (md[0]<<16)|(md[6]<<8)|md[12], 4);
	p = to64(p, (md[1]<<16)|(md[7]<<8)|md[13], 4);
	p = to64(p, (md[2]<<16)|(md[8]<<8)|md[14], 4);
	p = to64(p, (md[3]<<16)|(md[9]<<8)|md[15], 4);
	p = to64(p, (md[4]<<16)|(md[10]<<8)|md[5], 4);
	p = to64(p, md[11], 2);
	*p = 0;

	return output;
}

char *__crypt_md5(const char *key, const char *setting, char *output)
{
	static const char testkey[] = "Xy01@#\x01\x02\x80\x7f\xff\r\n\x81\t !";
	static const char testsetting[] = "$1$abcd0123$";
	static const char testhash[] = "$1$abcd0123$9Qcg8DyviekV3tDGMZynJ1";
	char testbuf[64];
	char *p, *q;

	p = md5crypt(key, setting, output);
	q = md5crypt(testkey, testsetting, testbuf);
	if (!p || q != testbuf || memcmp(testbuf, testhash, sizeof testhash))
		return "*";
	return p;
}