「数字6桁パスワードのMD5ハッシュ値の総当たり」CUDAを使うと0.20秒まではやくなったよ

http://tech-sketch.jp/2014/03/md5-openmp.html
↑を見つけてその後
[「数字6桁パスワードのMD5ハッシュ値の総当たり」OpenMPを使うと0.70秒までキタ](http://qiita.com/nmatsui/items/8a33941072668f3ac55b)にたどり着いたので、これらを参考にせっかくC言語で書いてあるのでCUDA化してみました。

# 環境

Windows8.1 Pro
CUDA : 7.5
CPU : corei7-4770K @ 3.50GHz
GPU : GeForce GTX 760 

今回使用したGPUは1152コアあります。最新のものは5000コア以上あるものもあるのでスペック的にはまあまあといった感じのものです。

ちなみにGPUのスペックはCUDAを入れていればdeviceQueryを実行すれば調べられます。
私の場合は

```
C:\ProgramData\NVIDIA Corporation\CUDA Samples\v7.5\1_Utilities\deviceQuery
```

に入っていました。

# 結果
C言語版のループを抜けるまでの時間を計測しました。

C言語：4.91秒
CUDA：0.20秒

高速化できましたね^ ^。

ただ、個人的にはもう少し早くなるかと思っていました。今回はCUDAに移植しただけであまり最適化的なことはやっていないので、そこらへんもやればもう少し早くなるのではないかと思います。


# CUDA化手順
かなり雑です。
一応コードは[これ](https://github.com/ko-he-/MD5_CUDA)です。
そのうちきれいにしたい...

CUDAは基本的にC言語の拡張のようなものなのです。なので、
[「数字6桁パスワードのMD5ハッシュ値の総当たり」OpenMPを使うと0.70秒までキタ](http://qiita.com/nmatsui/items/8a33941072668f3ac55b)の「Cで実装してみた」とhttp://openwall.info/wiki/people/solar/software/public-domain-source-code/md5
で公開されているC実装をもとにCUDA化していきます。

残念ながらCUDAではsprintf_sとかが使えない（はず？）のでそこら辺を書き換えが面倒でした。

まずはmain部分です。

```
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "md5.cuh"

int main(int argc, char* argv[])
{
	if (argc != 3) return 1;

	char* SALT = argv[1];
	char* PW = argv[2];
	char result[7];

	/*-----並列化された処理-----*/
	char *dev_SALT, *dev_PW, *dev_result;

	cudaMalloc((void**)&dev_SALT, strlen(SALT) *sizeof(char));
	cudaMalloc((void**)&dev_PW, strlen(PW) *sizeof(char));
	cudaMalloc((void**)&dev_result, 7 * sizeof(char));

	cudaMemcpy(dev_SALT, SALT, strlen(SALT) * sizeof(char), cudaMemcpyHostToDevice);
	cudaMemcpy(dev_PW, PW, strlen(PW) * sizeof(char), cudaMemcpyHostToDevice);

	md5_brute_force<<<1000, 1000 >>>(dev_SALT, dev_PW, dev_result);
	
	cudaMemcpy(result, dev_result, 7 * sizeof(char), cudaMemcpyDeviceToHost);
    /*---------------------*/
	printf("%s\n", result);

	return 0;
}
```

さらにhttp://openwall.info/wiki/people/solar/software/public-domain-source-code/md5　のmd5.c md5.hの関数の前にGPU側で呼ばれる関数であることを示す`__device__`をつけます。

そしてmd5.cに

```
// http://libc.blog47.fc2.com/blog-entry-30.html
//strlenのCUDA用
__device__ __host__ size_t strlen(const char *s)
{
	size_t n;
	for (n = 0; *s != '\0'; s++, n++);
	return n;
}

// http://www.geeksforgeeks.org/implement-itoa/
// itoaもCUDAに移すために上のリンクの説明を参考にCUDA化します
/* A utility function to reverse a string  */
__device__ void reverse(char str[], int length)
{
	int start = 0;
	int end = length - 1;
	while (start < end)
	{
		char temp = *(str + start);
		*(str + start) = *(str + end);
		*(str + end) = temp;

		//swap(*(str + start), *(str + end));
		start++;
		end--;
	}
}

// Implementation of itoa()
__device__ char* itoa(int num, char* str, int base)
{
	int i = 0;
	bool isNegative = false;

	/* Handle 0 explicitely, otherwise empty string is printed for 0 */
	if (num == 0)
	{
		str[i++] = '0';
		str[i] = '\0';
		return str;
	}

	// In standard itoa(), negative numbers are handled only with 
	// base 10. Otherwise numbers are considered unsigned.
	if (num < 0 && base == 10)
	{
		isNegative = true;
		num = -num;
	}

	// Process individual digits
	while (num != 0)
	{
		int rem = num % base;
		str[i++] = (rem > 9) ? (rem - 10) + 'a' : rem + '0';
		num = num / base;
	}

	// If number is negative, append '-'
	if (isNegative)
		str[i++] = '-';

	str[i] = '\0'; // Append string terminator

	// Reverse the string
	reverse(str, i);

	return str;
}


// CUDAではsprintf_sが使えない（んだった気がする）ので下のように地道に置き換えます。
__device__ void six_digit_decimal(char num_c[7], int num_i){
	char num[7] = "";
	int n = num_i;
	itoa(n, num, 10);
	int dig = 1;
	n /= 10;
	while (n != 0){
		dig++;
		n /= 10;
	}

	for (int j = 0; j < dig; j++){
		num_c[6 - dig + j] = num[j];
	}
}

__device__ void two_digit_hexadecimal(char num_c[3], int num_i){
	if (num_i < 16) {
		itoa(num_i, num_c, 16);
		num_c[1] = num_c[0];
		num_c[0] = '0';
	}
	else itoa(num_i, num_c, 16);
}

// http://stackoverflow.com/questions/20201335/add-char-arrays-in-cuda
// C言語のstrcatをCUDAで使うため上のURLから借りてきます。
__device__ char * my_strcpy(char *dest, const char *src){
	int i = 0;
	do {
		dest[i] = src[i];
	} while (src[i++] != 0);
	return dest;
}

__device__ char * my_strcat(char *dest, const char *src){
	int i = 0;
	while (dest[i] != 0) i++;
	my_strcpy(dest + i, src);
	return dest;
}

// 上のを参考にstrcmpもCUDAで実行できるようにします。
__device__ bool my_strcmp(char *dest, char *src){
	int i = 0;
	do {
		if (dest[i] != src[i]) return false;
	} while (src[i++] != 0);
	return true;
}

__global__ void md5_brute_force(char *SALT, char *PW, char *ret_result){
	int i = blockIdx.x * blockDim.x + threadIdx.x;
	MD5_CTX ctx;
	unsigned char hash[MD5_DIGEST_LENGTH];
	char result[MD5_DIGEST_LENGTH * 2 + 1];
	result[0] = '\0';
	char num_c[7] = "000000";
	six_digit_decimal(num_c, i);
	char origin[256] = "";
	my_strcat(origin, SALT);
	my_strcat(origin, "$");
	my_strcat(origin, num_c);

	MD5_Init(&ctx);
	MD5_Update(&ctx, origin, (unsigned long)strlen(origin));
	MD5_Final(hash, &ctx);
	for (int j = 0; j < MD5_DIGEST_LENGTH; j++) {
		char hex[3] = "";
		two_digit_hexadecimal(hex, hash[j]);
		my_strcat(result, hex);
	}
	if (my_strcmp(result, PW)) {
		six_digit_decimal(ret_result, i);
	}
}

```

を追加します。
md5.hには

```
extern __device__ __host__ size_t strlen(const char *s);
extern __device__ void reverse(char str[], int length);
extern __device__ char* itoa(int num, char* str, int base);
extern __device__ void six_digit_decimal(char num_c[7], int num_i);
extern __device__ void two_digit_hexadecimal(char num_c[3], int num_i);
extern __device__ char * my_strcpy(char *dest, const char *src);
extern __device__ char * my_strcat(char *dest, const char *src);
extern __device__ bool my_strcmp(char *dest, char *src);
extern __global__ void md5_brute_force(char *SALT, char *PW, char *ret_result);
```

を追加します。
これで実行できるはず。