Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Just something I wrote in 30 minutes to solve this challenge: http://www.h11e.com/ It does about 1 million inputs/sec on a quad-core i5-750.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Security.Cryptography;
namespace HashChallenge
{
public class Program
{
private static byte[] _smallestHash;
private static string _smalleshHashInput;
private static object _lockSource = new object();
public static void Main()
{
// These initial vectors were chosen to be something unlikely to be in the space tested by others. I kept adding zeros until I was
// satisfied that I would never exhaust the space in the given time. And of course each thread should search a separate space, so I
// tacked on letters at the end.
byte[] inputA = new byte[] { (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'a' };
byte[] inputB = new byte[] { (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'b' };
byte[] inputC = new byte[] { (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'c' };
byte[] inputD = new byte[] { (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'0', (byte)'d' };
_smallestHash = new SHA512Cng().ComputeHash(inputA);
_smalleshHashInput = Encoding.ASCII.GetString(inputA);
Console.WriteLine("{0}: {1}", BitConverter.ToString(_smallestHash).Replace("-", String.Empty), _smalleshHashInput);
Task.Run(() => FindSmallestHash(inputA));
Task.Run(() => FindSmallestHash(inputB));
Task.Run(() => FindSmallestHash(inputC));
Task.Run(() => FindSmallestHash(inputD));
// Console.ReadKey() will block the console, preventing output. This accomplishes the same thing without blocking.
bool done = false;
while (!done)
{
if (Console.KeyAvailable)
done = true;
// Don't want to actually spinwait.
Thread.Sleep(1000);
}
}
private static void FindSmallestHash(byte[] input)
{
SHA512 hasher = new SHA512Cng();
byte[] smallestHash = hasher.ComputeHash(input);
while (true)
{
IncrementInput(input);
byte[] newHash = hasher.ComputeHash(input);
// Each thread maintains its own smallest hash. We only compare against the global lowest when we've found our own
// lowest. This reduces lock contention to near zero.
if (HashLessThan(newHash, smallestHash))
{
smallestHash = newHash;
SwapSmallestHash(newHash, Encoding.ASCII.GetString(input));
}
}
}
private static void IncrementInput(byte[] input)
{
int index = 0;
input[index]++;
// We use '0' - '9' so that the result will be something we can easily type. Could have used any range of printable characters.
while (input[index] > '9')
{
input[index] = (byte)'0';
index++;
input[index]++;
}
}
private static bool HashLessThan(byte[] newHash, byte[] currentHash)
{
int index = 0;
while (index < newHash.Length)
{
if (newHash[index] < currentHash[index])
return true;
if (newHash[index] > currentHash[index])
return false;
index++;
}
return false;
}
private static void SwapSmallestHash(byte[] newSmallestHash, string input)
{
lock (_lockSource)
{
// We compare again once inside the lock to ensure that we don't hit a race condition and overwrite a lower hash.
if (HashLessThan(newSmallestHash, _smallestHash))
{
_smallestHash = newSmallestHash;
_smalleshHashInput = input;
Console.WriteLine("{0}: {1}", BitConverter.ToString(_smallestHash).Replace("-", String.Empty).ToLower(), _smalleshHashInput);
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.