Skip to content

Instantly share code, notes, and snippets.

@CodesInChaos

CodesInChaos/ArrayHelpers.cs

Created July 25, 2012 12:43
Download ZIP

Revisions

  1. CodesInChaos revised this gist Jul 25, 2012. 1 changed file with 3 additions and 1 deletion.
    4 changes: 3 additions & 1 deletion Base58EncodingTests.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -6,6 +6,7 @@ namespace Merkator.BitCoin.Tests
    [TestClass]
    public class Base58EncodingTests
    {
    // Test cases from https://github.com/bitcoin/bitcoin/blob/master/src/test/base58_tests.cpp
    Tuple<string, byte[]>[] testCases = new Tuple<string, byte[]>[]{
    Tuple.Create("",new byte[]{}),
    Tuple.Create("1112",new byte[]{0x00, 0x00, 0x00, 0x01}),
    @@ -53,6 +54,7 @@ public void DecodeInvalidChar()
    Base58Encoding.Decode("ab0");
    }

    // Example address from https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses
    byte[] addressBytes = new byte[] { 0x00, 0x01, 0x09, 0x66, 0x77, 0x60, 0x06, 0x95, 0x3D, 0x55, 0x67, 0x43, 0x9E, 0x5E, 0x39, 0xF8, 0x6A, 0x0D, 0x27, 0x3B, 0xEE };
    string addressText = "16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM";
    string brokenAddressText = "16UwLl9Risc3QfPqBUvKofHmBQ7wMtjvM";
    @@ -79,4 +81,4 @@ public void DecodeBrokenBitcoinAddress()
    Assert.AreEqual(BitConverter.ToString(addressBytes), BitConverter.ToString(actualBytes));
    }
    }
    }
    }
  2. CodesInChaos created this gist Jul 25, 2012.
    65 changes: 65 additions & 0 deletions ArrayHelpers.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,65 @@
    using System;
    using System.Diagnostics.Contracts;
    using System.Linq;

    namespace Merkator.Tools
    {
    public class ArrayHelpers
    {
    public static T[] ConcatArrays<T>(params T[][] arrays)
    {
    Contract.Requires(arrays != null);
    Contract.Requires(Contract.ForAll(arrays, (arr) => arr != null));
    Contract.Ensures(Contract.Result<T[]>() != null);
    Contract.Ensures(Contract.Result<T[]>().Length == arrays.Sum(arr => arr.Length));

    var result = new T[arrays.Sum(arr => arr.Length)];
    int offset = 0;
    for (int i = 0; i < arrays.Length; i++)
    {
    var arr = arrays[i];
    Buffer.BlockCopy(arr, 0, result, offset, arr.Length);
    offset += arr.Length;
    }
    return result;
    }

    public static T[] ConcatArrays<T>(T[] arr1, T[] arr2)
    {
    Contract.Requires(arr1 != null);
    Contract.Requires(arr2 != null);
    Contract.Ensures(Contract.Result<T[]>() != null);
    Contract.Ensures(Contract.Result<T[]>().Length == arr1.Length + arr2.Length);

    var result = new T[arr1.Length + arr2.Length];
    Buffer.BlockCopy(arr1, 0, result, 0, arr1.Length);
    Buffer.BlockCopy(arr2, 0, result, arr1.Length, arr2.Length);
    return result;
    }

    public static T[] SubArray<T>(T[] arr, int start, int length)
    {
    Contract.Requires(arr != null);
    Contract.Requires(start >= 0);
    Contract.Requires(length >= 0);
    Contract.Requires(start + length <= arr.Length);
    Contract.Ensures(Contract.Result<T[]>() != null);
    Contract.Ensures(Contract.Result<T[]>().Length == length);

    var result = new T[length];
    Buffer.BlockCopy(arr, start, result, 0, length);
    return result;
    }

    public static T[] SubArray<T>(T[] arr, int start)
    {
    Contract.Requires(arr != null);
    Contract.Requires(start >= 0);
    Contract.Requires(start <= arr.Length);
    Contract.Ensures(Contract.Result<T[]>() != null);
    Contract.Ensures(Contract.Result<T[]>().Length == arr.Length - start);

    return SubArray(arr, start, arr.Length - start);
    }
    }
    }
    133 changes: 133 additions & 0 deletions Base58Encoding.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,133 @@
    using System;
    using System.Collections.Generic;
    using System.Diagnostics.Contracts;
    using System.Linq;
    using System.Numerics;
    using System.Security.Cryptography;
    using System.Text;
    using System.Threading.Tasks;
    using Merkator.Tools;

    namespace Merkator.BitCoin
    {
    // Implements https://en.bitcoin.it/wiki/Base58Check_encoding
    public static class Base58Encoding
    {
    public const int CheckSumSizeInBytes = 4;

    public static byte[] AddCheckSum(byte[] data)
    {
    Contract.Requires<ArgumentNullException>(data != null);
    Contract.Ensures(Contract.Result<byte[]>().Length == data.Length + CheckSumSizeInBytes);
    byte[] checkSum = GetCheckSum(data);
    byte[] dataWithCheckSum = ArrayHelpers.ConcatArrays(data, checkSum);
    return dataWithCheckSum;
    }

    //Returns null if the checksum is invalid
    public static byte[] VerifyAndRemoveCheckSum(byte[] data)
    {
    Contract.Requires<ArgumentNullException>(data != null);
    Contract.Ensures(Contract.Result<byte[]>() == null || Contract.Result<byte[]>().Length + CheckSumSizeInBytes == data.Length);
    byte[] result = ArrayHelpers.SubArray(data, 0, data.Length - CheckSumSizeInBytes);
    byte[] givenCheckSum = ArrayHelpers.SubArray(data, data.Length - CheckSumSizeInBytes);
    byte[] correctCheckSum = GetCheckSum(result);
    if (givenCheckSum.SequenceEqual(correctCheckSum))
    return result;
    else
    return null;
    }

    private const string Digits = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";

    public static string Encode(byte[] data)
    {
    Contract.Requires<ArgumentNullException>(data != null);
    Contract.Ensures(Contract.Result<string>() != null);

    // Decode byte[] to BigInteger
    BigInteger intData = 0;
    for (int i = 0; i < data.Length; i++)
    {
    intData = intData * 256 + data[i];
    }

    // Encode BigInteger to Base58 string
    string result = "";
    while (intData > 0)
    {
    int remainder = (int)(intData % 58);
    intData /= 58;
    result = Digits[remainder] + result;
    }

    // Append `1` for each leading 0 byte
    for (int i = 0; i < data.Length && data[i] == 0; i++)
    {
    result = '1' + result;
    }
    return result;
    }

    public static string EncodeWithCheckSum(byte[] data)
    {
    Contract.Requires<ArgumentNullException>(data != null);
    Contract.Ensures(Contract.Result<string>() != null);
    return Encode(AddCheckSum(data));
    }

    public static byte[] Decode(string s)
    {
    Contract.Requires<ArgumentNullException>(s != null);
    Contract.Ensures(Contract.Result<byte[]>() != null);

    // Decode Base58 string to BigInteger
    BigInteger intData = 0;
    for (int i = 0; i < s.Length; i++)
    {
    int digit = Digits.IndexOf(s[i]); //Slow
    if (digit < 0)
    throw new FormatException(string.Format("Invalid Base58 character `{0}` at position {1}", s[i], i));
    intData = intData * 58 + digit;
    }

    // Encode BigInteger to byte[]
    // Leading zero bytes get encoded as leading `1` characters
    int leadingZeroCount = s.TakeWhile(c => c == '1').Count();
    var leadingZeros = Enumerable.Repeat((byte)0, leadingZeroCount);
    var bytesWithoutLeadingZeros =
    intData.ToByteArray()
    .Reverse()// to big endian
    .SkipWhile(b => b == 0);//strip sign byte
    var result = leadingZeros.Concat(bytesWithoutLeadingZeros).ToArray();
    return result;
    }

    // Throws `FormatException` if s is not a valid Base58 string, or the checksum is invalid
    public static byte[] DecodeWithCheckSum(string s)
    {
    Contract.Requires<ArgumentNullException>(s != null);
    Contract.Ensures(Contract.Result<byte[]>() != null);
    var dataWithCheckSum = Decode(s);
    var dataWithoutCheckSum = VerifyAndRemoveCheckSum(dataWithCheckSum);
    if (dataWithoutCheckSum == null)
    throw new FormatException("Base58 checksum is invalid");
    return dataWithoutCheckSum;
    }

    private static byte[] GetCheckSum(byte[] data)
    {
    Contract.Requires<ArgumentNullException>(data != null);
    Contract.Ensures(Contract.Result<byte[]>() != null);

    SHA256 sha256 = new SHA256Managed();
    byte[] hash1 = sha256.ComputeHash(data);
    byte[] hash2 = sha256.ComputeHash(hash1);

    var result = new byte[CheckSumSizeInBytes];
    Buffer.BlockCopy(hash2, 0, result, 0, result.Length);

    return result;
    }
    }
    }
    82 changes: 82 additions & 0 deletions Base58EncodingTests.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,82 @@
    using System;
    using Microsoft.VisualStudio.TestTools.UnitTesting;

    namespace Merkator.BitCoin.Tests
    {
    [TestClass]
    public class Base58EncodingTests
    {
    Tuple<string, byte[]>[] testCases = new Tuple<string, byte[]>[]{
    Tuple.Create("",new byte[]{}),
    Tuple.Create("1112",new byte[]{0x00, 0x00, 0x00, 0x01}),
    Tuple.Create("2g",new byte[]{0x61}),
    Tuple.Create("a3gV",new byte[]{0x62,0x62,0x62}),
    Tuple.Create("aPEr",new byte[]{0x63,0x63,0x63}),
    Tuple.Create("2cFupjhnEsSn59qHXstmK2ffpLv2",new byte[]{0x73,0x69,0x6d,0x70,0x6c,0x79,0x20,0x61,0x20,0x6c,0x6f,0x6e,0x67,0x20,0x73,0x74,0x72,0x69,0x6e,0x67}),
    Tuple.Create("1NS17iag9jJgTHD1VXjvLCEnZuQ3rJDE9L",new byte[]{0x00,0xeb,0x15,0x23,0x1d,0xfc,0xeb,0x60,0x92,0x58,0x86,0xb6,0x7d,0x06,0x52,0x99,0x92,0x59,0x15,0xae,0xb1,0x72,0xc0,0x66,0x47}),
    Tuple.Create("ABnLTmg",new byte[]{0x51,0x6b,0x6f,0xcd,0x0f}),
    Tuple.Create("3SEo3LWLoPntC",new byte[]{0xbf,0x4f,0x89,0x00,0x1e,0x67,0x02,0x74,0xdd}),
    Tuple.Create("3EFU7m",new byte[]{0x57,0x2e,0x47,0x94}),
    Tuple.Create("EJDM8drfXA6uyA",new byte[]{0xec,0xac,0x89,0xca,0xd9,0x39,0x23,0xc0,0x23,0x21}),
    Tuple.Create("Rt5zm",new byte[]{0x10,0xc8,0x51,0x1e}),
    Tuple.Create("1111111111",new byte[]{0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00})
    };

    [TestMethod]
    public void Encode()
    {
    foreach (var tuple in testCases)
    {
    var bytes = tuple.Item2;
    var expectedText = tuple.Item1;
    var actualText = Base58Encoding.Encode(bytes);
    Assert.AreEqual(expectedText, actualText);
    }
    }

    [TestMethod]
    public void Decode()
    {
    foreach (var tuple in testCases)
    {
    var text = tuple.Item1;
    var expectedBytes = tuple.Item2;
    var actualBytes = Base58Encoding.Decode(text);
    Assert.AreEqual(BitConverter.ToString(expectedBytes), BitConverter.ToString(actualBytes));
    }
    }

    [TestMethod]
    [ExpectedException(typeof(FormatException))]
    public void DecodeInvalidChar()
    {
    Base58Encoding.Decode("ab0");
    }

    byte[] addressBytes = new byte[] { 0x00, 0x01, 0x09, 0x66, 0x77, 0x60, 0x06, 0x95, 0x3D, 0x55, 0x67, 0x43, 0x9E, 0x5E, 0x39, 0xF8, 0x6A, 0x0D, 0x27, 0x3B, 0xEE };
    string addressText = "16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM";
    string brokenAddressText = "16UwLl9Risc3QfPqBUvKofHmBQ7wMtjvM";

    [TestMethod]
    public void EncodeBitcoinAddress()
    {
    var actualText = Base58Encoding.EncodeWithCheckSum(addressBytes);
    Assert.AreEqual(addressText, actualText);
    }

    [TestMethod]
    public void DecodeBitcoinAddress()
    {
    var actualBytes = Base58Encoding.DecodeWithCheckSum(addressText);
    Assert.AreEqual(BitConverter.ToString(addressBytes), BitConverter.ToString(actualBytes));
    }

    [TestMethod]
    [ExpectedException(typeof(FormatException))]
    public void DecodeBrokenBitcoinAddress()
    {
    var actualBytes = Base58Encoding.DecodeWithCheckSum(brokenAddressText);
    Assert.AreEqual(BitConverter.ToString(addressBytes), BitConverter.ToString(actualBytes));
    }
    }
    }