6

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?

Cᴏʀʏ
  • 105,112
  • 20
  • 162
  • 194
Will
  • 3,413
  • 7
  • 50
  • 107
  • Check out "G" here: http://stackoverflow.com/questions/15072552/use-scientific-notation-only-if-needed . You could also store a hash http://stackoverflow.com/questions/3404715/c-sharp-hashcode-for-array-of-ints treating each digit as a member of an int array eg 1234 becomes int[]{1,2,3,4}; – Shannon Holsinger Sep 01 '16 at 02:28
  • What precision do you actually require? Ticks aren't guaranteed to be unique either, unless you do something [like this](http://stackoverflow.com/a/14369695/74757). – Cᴏʀʏ Sep 01 '16 at 02:30
  • @Cᴏʀʏ Yep; I saw that post while I was looking. There's reasonable delay between message transmissions so it's not like I'm launching space shuttles or something where a millisecond means you end up a trillion kilometers off course or something. – Will Sep 01 '16 at 02:32
  • @ShannonHolsinger Wasn't familiar with 'G'... may be worth looking into. – Will Sep 01 '16 at 02:34
  • @Will: you could drop a couple of digits by subtracting off a known value, say, the number of ticks up until the beginning of the century, before doing anything else to it. On the other side, add back on the known number of ticks. – Cᴏʀʏ Sep 01 '16 at 02:35
  • I don't know how many values you need to store, but you could simply increment an integer like an SQL ID, then remove old values and decrement to 0 every X increments. I like the hash idea better, but I'm just saying... – Shannon Holsinger Sep 01 '16 at 02:35
  • @ShannonHolsinger Ideally the values would be spending not a second within the dictionary, but this is not an ideal situation... Timestamping was just the first idea that came to my mind. Unfortunately, because of the disconnect between the two machines, while incrementing an integral value from 0 to Infinite would likely not cause too many problems there would be no way to tell the program sending the headers "Hey, you need to reset now" unless I specified an arbitrary value ( "Reset at 100, 1000, whatever" ). I will look into the Hash idea... – Will Sep 01 '16 at 02:38
  • @Will, have you had a chance to review my answer? If you're ok with millisecond accuracy, the timestamp encoding I explain gets you down to an 8 character string. – Cᴏʀʏ Sep 01 '16 at 15:11

1 Answers1

19

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

Community
  • 1
  • 1
Cᴏʀʏ
  • 105,112
  • 20
  • 162
  • 194
  • 1
    This explains how talented developer you are @Cory.You are awesome.Thank you for this awesome explanation.And thank you for taking your precious time to do the good to the world. – Daryl Apr 17 '19 at 07:00