Another Murmur3 implementation - 128 bit output, 64 bit platform version

Another Murmur3 implementation - 128 bit output, 64 bit platform version

/// <summary>
/// Taken from here - http://blog.teamleadnet.com/2012/08/murmurhash3-ultra-fast-hash-algorithm.html
/// but corrected the code and made the class re-usable, the original will only work on the first call
/// There's another version here: http://pastebin.com/aP8aRRHK
/// Corrected the code using code from https://github.com/darrenkopp/murmurhash-net/blob/master/MurmurHash/Unmanaged/Murmur128UnmanagedX64.cs
/// In ProcessBytes both h1 and h2 should be set to the seed
/// 128 bit output, 64 bit platform version
/// </summary>
internal class Murmur3
{
 // 128 bit output, 64 bit platform version
 private static readonly ulong READ_SIZE = 16;
 private static readonly ulong C1 = 0x87c37b91114253d5L;
 private static readonly ulong C2 = 0x4cf5ad432745937fL;

 private ulong length;
 private uint seed = 0; // if want to start with a seed, create a constructor
 private ulong h1;
 private ulong h2;


 /// <summary>
 /// Murmur3 constructor
 /// </summary>
 /// <param name="seed"></param>
 public Murmur3(uint seed = 0)
 {
  this.seed = seed;
 }

 /// <summary>
 /// Compute a hash from an input byte array
 /// </summary>
 /// <param name="input"></param>
 /// <returns></returns>
 public byte[] ComputeHash(byte[] input)
 {
  ProcessBytes(input);
  return Hash;
 }

 /// <summary>
 /// Create a string hash from an input string
 /// </summary>
 /// <param name="input"></param>
 /// <returns></returns>
 public string ComputeHash(string input)
 {
  Byte[] inBytes = Encoding.UTF8.GetBytes(input);
  Byte[] hash = this.ComputeHash(inBytes);
  string output = Convert.ToBase64String(hash);
  return output.TrimEnd('='); // There can be up to 2 trailing '=' characters which are just for padding (Not required for a hash)
 }

 #region Private Methods

 
 /// <summary>
 /// 
 /// </summary>
 private byte[] Hash
 {
  get
  {
   h1 ^= length;
   h2 ^= length;

   h1 += h2;
   h2 += h1;

   h1 = Murmur3.MixFinal(h1);
   h2 = Murmur3.MixFinal(h2);

   h1 += h2;
   h2 += h1;

   var hash = new byte[Murmur3.READ_SIZE];

   Array.Copy(BitConverter.GetBytes(h1), 0, hash, 0, 8);
   Array.Copy(BitConverter.GetBytes(h2), 0, hash, 8, 8);

   return hash;
  }
 }
 
 private void MixBody(ulong k1, ulong k2)
 {
  h1 ^= MixKey1(k1);

  h1 = h1.RotateLeft(27);
  h1 += h2;
  h1 = h1*5 + 0x52dce729;

  h2 ^= MixKey2(k2);

  h2 = h2.RotateLeft(31);
  h2 += h1;
  h2 = h2*5 + 0x38495ab5;
 }

 private static ulong MixKey1(ulong k1)
 {
  k1 *= C1;
  k1 = k1.RotateLeft(31);
  k1 *= C2;
  return k1;
 }

 private static ulong MixKey2(ulong k2)
 {
  k2 *= C2;
  k2 = k2.RotateLeft(33);
  k2 *= C1;
  return k2;
 }

 private static ulong MixFinal(ulong k)
 {
  // avalanche bits

  k ^= k >> 33;
  k *= 0xff51afd7ed558ccdL;
  k ^= k >> 33;
  k *= 0xc4ceb9fe1a85ec53L;
  k ^= k >> 33;
  return k;
 }

 private void ProcessBytes(byte[] bb)
 {
  h2 = seed;
  h1 = seed;
  this.length = 0L;

  int pos = 0;
  ulong remaining = (ulong) bb.Length;

  // read 128 bits, 16 bytes, 2 longs in eacy cycle
  while (remaining >= READ_SIZE)
  {
   ulong k1 = bb.GetUInt64(pos);
   pos += 8;

   ulong k2 = bb.GetUInt64(pos);
   pos += 8;

   length += READ_SIZE;
   remaining -= READ_SIZE;

   MixBody(k1, k2);
  }

  // if the input MOD 16 != 0
  if (remaining > 0)
   ProcessBytesRemaining(bb, remaining, pos);
 }

 private void ProcessBytesRemaining(byte[] bb, ulong remaining, int pos)
 {
  ulong k1 = 0;
  ulong k2 = 0;
  length += remaining;

  // little endian (x86) processing
  switch (remaining)
  {
   case 15:
    k2 ^= (ulong) bb[pos + 14] << 48; // fall through
    goto case 14;
   case 14:
    k2 ^= (ulong) bb[pos + 13] << 40; // fall through
    goto case 13;
   case 13:
    k2 ^= (ulong) bb[pos + 12] << 32; // fall through
    goto case 12;
   case 12:
    k2 ^= (ulong) bb[pos + 11] << 24; // fall through
    goto case 11;
   case 11:
    k2 ^= (ulong) bb[pos + 10] << 16; // fall through
    goto case 10;
   case 10:
    k2 ^= (ulong) bb[pos + 9] << 8; // fall through
    goto case 9;
   case 9:
    k2 ^= (ulong) bb[pos + 8]; // fall through
    goto case 8;
   case 8:
    k1 ^= bb.GetUInt64(pos);
    break;
   case 7:
    k1 ^= (ulong) bb[pos + 6] << 48; // fall through
    goto case 6;
   case 6:
    k1 ^= (ulong) bb[pos + 5] << 40; // fall through
    goto case 5;
   case 5:
    k1 ^= (ulong) bb[pos + 4] << 32; // fall through
    goto case 4;
   case 4:
    k1 ^= (ulong) bb[pos + 3] << 24; // fall through
    goto case 3;
   case 3:
    k1 ^= (ulong) bb[pos + 2] << 16; // fall through
    goto case 2;
   case 2:
    k1 ^= (ulong) bb[pos + 1] << 8; // fall through
    goto case 1;
   case 1:
    k1 ^= (ulong) bb[pos]; // fall through
    break;
   default:
    throw new Exception("Something went wrong with remaining bytes calculation.");
  }

  h1 ^= MixKey1(k1);
  h2 ^= MixKey2(k2);
 }

 #endregion Private Methods

}

/// <summary>
/// Some helper functions for reading 64 bit integers from a byte array and rotating unsigned longs:
/// </summary>
public static class IntHelpers
{
 /// <summary>
 /// 
 /// </summary>
 /// <param name="original"></param>
 /// <param name="bits"></param>
 /// <returns></returns>
 public static ulong RotateLeft(this ulong original, int bits)
 {
  return (original << bits) | (original >> (64 - bits));
 }

 /// <summary>
 /// 
 /// </summary>
 /// <param name="original"></param>
 /// <param name="bits"></param>
 /// <returns></returns>
 public static ulong RotateRight(this ulong original, int bits)
 {
  return (original >> bits) | (original << (64 - bits));
 }

 /// <summary>
 /// 
 /// </summary>
 /// <param name="bb"></param>
 /// <param name="pos"></param>
 /// <returns></returns>
 public static unsafe ulong GetUInt64(this byte[] bb, int pos)
 {
  // we only read aligned longs, so a simple casting is enough
  fixed (byte* pbyte = &bb[pos])
  {
   return *((ulong*) pbyte);
  }
 }
}

Unit tests to verify the implementation (but it also shows how to use it).

// Test vectors taken from here: https://github.com/karanlyons/murmurHash3.js/blob/master/tests.html
[Test]
public void Murmur3ValidityTests()
{
 TestVector("I will not buy this tobacconist's, it is scratched.", 0, new ulong[] { 0xd30654abbd8227e3, 0x67d73523f0079673 });
 TestVector("", 0, new ulong[] { 0x0000000000000000, 0x0000000000000000 });
 TestVector("0", 0, new ulong[] { 0x2ac9debed546a380, 0x3a8de9e53c875e09 });
 TestVector("01", 0, new ulong[] { 0x649e4eaa7fc1708e, 0xe6945110230f2ad6 });
 TestVector("012", 0, new ulong[] { 0xce68f60d7c353bdb, 0x00364cd5936bf18a });
 TestVector("0123", 0, new ulong[] { 0x0f95757ce7f38254, 0xb4c67c9e6f12ab4b });
 TestVector("01234", 0, new ulong[] { 0x0f04e459497f3fc1, 0xeccc6223a28dd613 });
 TestVector("012345", 0, new ulong[] { 0x88c0a92586be0a27, 0x81062d6137728244 });
 TestVector("0123456", 0, new ulong[] { 0x13eb9fb82606f7a6, 0xb4ebef492fdef34e });
 TestVector("01234567", 0, new ulong[] { 0x8236039b7387354d, 0xc3369387d8964920 });
 TestVector("012345678", 0, new ulong[] { 0x4c1e87519fe738ba, 0x72a17af899d597f1 });
 TestVector("0123456789", 0, new ulong[] { 0x3f9652ac3effeb24, 0x8027a17cf2990b07 });
 TestVector("0123456789a", 0, new ulong[] { 0x4bc3eacd29d38629, 0x7cb2d9e797da9c92 });
 TestVector("0123456789ab", 0, new ulong[] { 0x66352b8cee9e3ca7, 0xa9edf0b381a8fc58 });
 TestVector("0123456789abc", 0, new ulong[] { 0x5eb2f8db4265931e, 0x801ce853e61d0ab7 });
 TestVector("0123456789abcd", 0, new ulong[] { 0x07a4a014dd59f71a, 0xaaf437854cd22231 });
 TestVector("0123456789abcde", 0, new ulong[] { 0xa62dd5f6c0bf2351, 0x4fccf50c7c544cf0 });
 TestVector("0123456789abcdef", 0, new ulong[] { 0x4be06d94cf4ad1a7, 0x87c35b5c63a708da });
 TestVector("", 1, new ulong[] { 0x4610abe56eff5cb5, 0x51622daa78f83583 });
}

private void TestVector(string key, uint seed, ulong[] hash)
{
 var hasher = new Murmur3(seed);
 Byte[] inBytes = Encoding.UTF8.GetBytes(key);
 Byte[] res = hasher.ComputeHash(inBytes);
 ulong check0 = BitConverter.ToUInt64(res, 0);
 ulong check1 = BitConverter.ToUInt64(res, 8);
 Assert.That(hash[0] == check0);
 Assert.That(hash[1] == check1);
}

Using Newtonsoft (Open Source) JSON Serializer

Here is how to serialize and deserialize a JSON object to and from a string

string json = JsonConvert.SerializeObject(target, Formatting.Indented); // Serialize to a string
var reconstituted = JsonConvert.DeserializeObject<ClassOfTarget>(json); // Deserialize from a string

Documentation is here: http://www.newtonsoft.com/json/help/html/Introduction.htm

Can use with attributes:

[DataContract] // ONLY 'marked' properties are serialized in this case
public class ClassOfTarget
{
...
[DataMember] // Use this attribute to 'mark' a property
public Dictionary<string, string> Mappings { get; set; }
...
}

Newtonsoft JSON serializer will recognise these Microsoft attributes and they also have a few of their own they will recognise as well.

Serializing/Deserializing to a file using some extension methods

using Newtonsoft.Json;

public static class JsonExtensions
{

  public static void WriteToJsonFile<T>(
    this T objectToWrite, 
    string filePath
    // This next parameter is optional but ensures that 
    // when you have types mixed with their derived types
    // they can be serialized as well
    bool derivedTypesPresent = false) 
      where T : new()
  {
    FileInfo file = new FileInfo(filePath);
    Debug.Assert(!file.Exists);
    try
    {
      // Serialize JSON directly to a file
      using (StreamWriter sw = new StreamWriter(file.FullName))
      {
        using (JsonWriter writer = new JsonTextWriter(sw))
        {
          JsonSerializer serializer = new JsonSerializer();
          serializer.Formatting = Formatting.Indented;
          if (derivedTypesPresent) // Store type info in JSON
            serializer.TypeNameHandling = TypeNameHandling.All; 

          // target is the object you want serialized
          serializer.Serialize(writer, objectToWrite); 
        }
      }
    }
    catch (JsonSerializationException ex)
    {
        Trace.WriteLine($"Json Serialization Exception occurred: {ex}");
    }
  }

  public static T ReadFromJsonFile<T>(
    this string filePath
    // This next parameter is optional but ensures that 
    // when you have types mixed with their derived types
    // they can be serialized as well
    bool derivedTypesPresent = false)
      where T : class, new()
  {
    FileInfo file = new FileInfo(filePath);
    Debug.Assert(file.Exists);
    T reconstituted = null;

    try
    {
      // deserialize JSON directly from a file
      using (var reader = file.OpenText())
      {
        var serializer = new JsonSerializer();
        if (derivedTypesPresent) // Store type info in JSON
          serializer.TypeNameHandling = TypeNameHandling.All; 
        reconstituted = (T)serializer.Deserialize(reader, typeof(T));
      }
    }
    catch (JsonSerializationException ex)
    {
        Trace.WriteLine($"Json Serialization Exception occurred: {ex}");
    }
    return reconstituted;
  }
  
  public static string WriteToJsonString<T>(
    this T objectToWrite,
    //This parameter is optional but ensures that 
    //when you have types mixed with their derived types
    // they can be serialized as well
    bool derivedTypesPresent = false)
    where T : new()
  {
    string json = "";
    Debug.Assert(objectToWrite != null);
    try
    {
        var serializerSettings = new JsonSerializerSettings();
        serializerSettings.DefaultValueHandling = DefaultValueHandling.IgnoreAndPopulate;
        if (derivedTypesPresent) // Then store type info in JSON as well
            serializerSettings.TypeNameHandling = TypeNameHandling.All;

        // Serialize to a string  
        json = JsonConvert.SerializeObject(objectToWrite, Formatting.None); 
    }
    catch (JsonSerializationException ex)
    {
        Trace.WriteLine($"Json Serialization Exception occurred: {ex}");
    }
    return json.ToString();
  }

  public static T ReadFromJsonString<T>(
    this string json,
    bool derivedTypesPresent = false)
    where T : class, new()
  {
    Debug.Assert(!string.IsNullOrWhiteSpace(json));
    T reconstituted = null;

    try
    {
        var serializerSettings = new JsonSerializerSettings();
        serializerSettings.DefaultValueHandling = DefaultValueHandling.
            IgnoreAndPopulate;
        if (derivedTypesPresent) // Then store type info in JSON as well
            serializerSettings.TypeNameHandling = TypeNameHandling.All;

        reconstituted = JsonConvert.DeserializeObject<T>(json, 
            serializerSettings);
    }
    catch (JsonSerializationException ex)
    {
        Trace.WriteLine($"Json Serialization Exception occurred: {ex}");
    }
    return reconstituted;
  }

}

And to serialise and deserialise to and from a file:

StarSystem myObject = new StarSystem(...);
// To write an object to a json file
myObject.WriteToJsonFile<StarSystem>(filePath);
// To read an object from a jsonfile
myObject = filePath.ReadFromJsonFile<StarSystem>(); 

And to serialise and deserialise to and from a string:

StarSystem myObject = new StarSystem(...);
// To write an object to a json string
string json = myObject.WriteToJsonString<StarSystem>();
// To read an object from a json string
myObject = json.ReadFromJsonString<StarSystem>(); 

To convert the JSON to XML, use the JSON string like so

// To convert the JSON to XML
string json = ....
XNode node = JsonConvert.DeserializeXNode(json, "Title");
string xml = node.ToString();

Loading application settings from a custom configuration file

Here is a unit test to show how to load configuration data from a custom configuration file (useful in unit tests)

private string configContents =
 @"<?xml version='1.0' encoding='utf-8'?>" +
 @"<configuration>" +
 @"  <startup>" +
 @"    <supportedRuntime version='v4.0' sku='.NETFramework,Version=v4.5.2'/>" +
 @"  </startup>" +
 @"  <appSettings>" +
 @"" +
 @"    <add key='intValue' value='42' />" +
 @"    <add key='stringValue' value='blah, blah, blah' />" +
 @"" +
 @"  </appSettings>" +
 @"</configuration>";

[Test]
public void RawCustomConfigTest()
{
 // Write out the test config file
 string exeDir = System.IO.Path.GetDirectoryName(new Uri(Assembly.GetExecutingAssembly().GetName().CodeBase).LocalPath);
 string configPath = Path.Combine(exeDir, "Test.config");
 File.WriteAllText(configPath, configContents, Encoding.UTF8);

 // Read it in
 SysConfig.ExeConfigurationFileMap map = new SysConfig.ExeConfigurationFileMap { ExeConfigFilename = configPath };
 SysConfig.Configuration config = SysConfig.ConfigurationManager.OpenMappedExeConfiguration(map, SysConfig.ConfigurationUserLevel.None);
 var appSettings = config.AppSettings.Settings;

 // Read in the test entries
 string intValue = TryGetValue(appSettings, "intValue", "-1");
 string stringValue = TryGetValue(appSettings, "stringValue", "");
 string otherValue = TryGetValue(appSettings, "DoesNotExistInConfig", "not present"); // does not exist in the config file

 // Show that it worked
 Assert.That(intValue == "42");
 Assert.That(stringValue == "blah, blah, blah");
 Assert.That(otherValue == "not present");
}

private static string TryGetValue(SysConfig.KeyValueConfigurationCollection appSettings, string name, string defaultValue)
{
 try
 {
  return appSettings[name].Value;
 }
 catch (NullReferenceException)
 {
  return defaultValue;
 }
}

MemoryCache Extension

The MemoryCache class does not have a "Clear()" method.
Here is  an extension that does the job

// Extend MemoryCache functionality
public static class MemoryCacheExtensions
{
 // Clear the cache
 public static void Clear(this MemoryCache cache)
 {
  List<string> cacheKeys = cache.Select(kvp => kvp.Key).ToList();
  foreach (string cacheKey in cacheKeys)
  {
   cache.Remove(cacheKey);
  }
 }
}