Is it possible to reduce the length of DateTime.Now.Ticks.ToString("X") and still maintain uniqueness?

Question

I have a limitation with some hardware with which I am working wherein I can only broadcast ( wirelessly ) 26 characters.

To overcome this limitation, the first broadcast transmits a timestamp converted into hexadecimal ( DateTime.Now.Ticks.ToString( "X" ) ), along with the length of the message being transmitted ( also as a hexadecimal string ).

The receiving software tests for header messages, and when it confirms that it receives one, stores the time stamp ( reconverted into a long ) in a dictionary :

/*************************************************************************
 * _pendingMessages.Add( DateTime.Now.Ticks, Tuple.Create( MessageLength, string.Empty ) );
 * T.Item1 = Message Length
 * T.Item2 = Message ( when Message.Length == Length, Pop Message )
 *************************************************************************/
private static Dictionary<long, Tuple<long, string>> _pendingMessages;

Unfortunately, the time stamp has to be passed each time, and it's... over half the allotted character length ( at 15 characters right now ).

So I was thinking that, rather than pass the entire time stamp, that I might be able to reduce it by summing the value of the characters of the hex string :

For Example :

DateTime.Now.Ticks.ToSTring("X").Sum( C => C ).ToString("X");

Unfortunately, a quick test blew that idea away rather unceremoniously

( duplicate keys rather quickly ) :

Dictionary<string, long> _dctTest = new Dictionary<string, long>( );
while ( true ){
    long dtNow = DateTime.Now.Ticks;
    string strKey = dtNow.ToString("X").Sum( C => C ).ToStrings("X");
    _dctTest.Add( strKey, dtNow ); //<=====Explodes after less than a second.
}

So my question is - is there any way for me to reliably reduce the length of my "Key" while still ( reasonably ) guaranteeing uniqueness?

Answer 1

Here's something to kick-start some answers. I'm not claiming this is an optimal solution but I can get you millisecond precision with only 11 characters 8 characters 7 characters of encoded data.

Assuming millisecond accuracy is good enough, we can reduce the precision of our algorithm from the get-go. A tick represents 100 nanoseconds. There are 10,000 ticks in a millisecond. Here's the algorithm:

Start with a known, large number of ticks that occurred in the past. This example uses the beginning of the century.

long centuryBegin = new DateTime(2001, 1, 1).Ticks; 
// 631139040000000000

Now take a snapshot of the current timestamp:

long currentDate = DateTime.Now.Ticks;
// 636083231371736598

Take the difference, and reduce the precision to millisecond-level:

long shortTicks = (currentDate - centuryBegin) / 10000L; 
// 494419137173

Now we just base64-encode the string:

string base64Ticks = Convert.ToBase64String(BitConverter.GetBytes(shortTicks));
// lVKtHXMAAAA=

However, without going into too much detail of why, the trailing "AAAA=" will be present on any encoded number of this number of bytes, so we can remove it!

base64Ticks = base64Ticks.Substring(0, 7);
// lVKtHXM

You now have a 7-character string lVKtHXM for transmission. On the other side:

// Decode the base64-encoded string back into bytes
// Note we need to add on the "AAAA=" that we stripped off    
byte[] data = new byte[8];
Convert.FromBase64String(base64Ticks + "AAAA=").CopyTo(data, 0);

// From the bytes, convert back to a long, multiply by 10,000, and then
// add on the known century begin number of ticks
long originalTicks = (BitConverter.ToInt64(data, 0) * 10000L) + centuryBegin;
// 636083231371730000

Let's check the difference between the two:

 636083231371736598 (original ticks)
-636083231371730000 (decoded ticks)
===================
               6598 (difference)

And you can see this gets you to within 6,598 ticks, or 0.6598 milliseconds, of the original timestamp. The difference will always be <= 1 ms.

In terms of uniqueness, I tried this on 100,000 fake transmissions, sleeping for 1 millisecond in between each attempt, and there were no collisions.

To round out this post, here are some helper methods you might use:

public static string EncodeTransmissionTimestamp(DateTime date)
{
    long shortTicks = (date.Ticks - 631139040000000000L) / 10000L; 
    return Convert.ToBase64String(BitConverter.GetBytes(shortTicks)).Substring(0, 7);
}

public static DateTime DecodeTransmissionTimestamp(string encodedTimestamp)
{
    byte[] data = new byte[8];
    Convert.FromBase64String(encodedTimestamp + "AAAA=").CopyTo(data, 0);
    return new DateTime((BitConverter.ToInt64(data, 0) * 10000L) + 631139040000000000L);
}

Some of this work was inspired by this post: Compress large Integers into smallest possible string