This is the fifteenth part of the Async Wandering series. For your convenience you can find other parts in the table of contents in Part 1 – Why creating Form from WinForms in unit tests breaks async?

You probably heard that async is all about not blocking the operating system level thread. This is the fundamental principle of asynchronous programming. If you block the operating system level thread, you lose all the benefits of the asynchronous code.

You also need to keep in mind how to write your C# code. You probably heard that you should keep async all the way up. This is rather easy to keep because the compiler takes care of that. What’s slightly harder to remember is to keep ConfigureAwait(false) all the way down. If you don’t do it this way, the compiler won’t help you and you may run into some nasty deadlocking issues, especially if you use some weird SynchronizationContext.

Last but not least, you probably know that the asynchronous code is only useful if your code is IO-bound. You probably heard that many times. However, what might be very surprising is that C# actually does a lot to make your application work even if your code is CPU-bound and you still use async. This is very misleading and may let you believe that you know async, whereas you only know async in C#. Let’s see why.

There is plenty of no threads!

One of the best articles about async is C# is titled There Is No Thread. Stephen Cleary shows that it’s all about continuations and juggling the lambdas to run your code when some IO-bound operation finishes. I even used this title in my Internals of Async talk in which I explain all the internals of synchronization contexts, continuations, and the machinery behind the scenes.

However, it’s only a figure of speech. At the very end of the day, we need to have some thread to run the code. Depending on your synchronization context, there may be some dedicated thread to run the continuations (like in desktop or Blazor applications), or we can use threads from the thread pool. If you think carefully about the asynchronous code, you should notice that this is the place where C# either bites you hard (and causes many deadlocks) or saves your application even if you are doing something very wrong. How? Because C# uses many threads.

By default, C# uses the thread pool to run continuations. The thread pool runs some not-so-trivial algorithm to spawn new threads when there is plenty of work to be done. This is not part of the asynchronous programming paradigm per se. This is just the implementation detail of C#’s asynchronous code which heavily impacts how your applications scale. Other languages don’t do it in the same way and what works well in C# may fail badly somewhere else. For instance, Python’s asyncio uses just one thread even though Python supports multithreading. While this is just an implementation detail, it have tremendous performance implications. Let’s see why.

One thread can kill you

Let’s take a typical message processing flow. We take a message from the service bus, refresh the lease periodically, and process the message in the background. Let’s say that our flow is IO-bound and we use async to benefit from non-blocking thread instead of spawning multiple threads. Let’s simulate the system. You can find the whole code in this gist.
We start with a message that will store when we received it, when we refreshed the lease for the last time, the identifier of the message, and the final status (if we lost the message or finished successfully):

public class Message
{
	public DateTime LastRefreshTime { get; set; }
	public DateTime ReceiveTime { get; set; }
	public bool WasLost { get; set; }
	public bool WasFinished { get; set; }
	public int Id { get; set; }
}

Now, we want to configure timings in our application. We can specify how long it takes to receive the message from the bus, how many operations we need to perform on each message, and how long they all take:

public class Settings
{
	public int MessagesCount { get; set; }
	public TimeSpan ReceivingDuration { get; set; }
	public TimeSpan ProcessingCPUDuration { get; set; }
	public TimeSpan ProcessingIODuration { get; set; }
	public int ProcessingLoops { get; set; }
	public TimeSpan RefreshDelay { get; set; }
	public TimeSpan RefreshDuration { get; set; }
	public TimeSpan MessageLeaseTimeout { get; set; }
}

Finally, we have some statistics showing how we did:

public class Stats
{
	public int GeneratedMessages { get; set; }
	public int ProcessedSuccessfully { get; set; }
	public int Lost { get; set; }
}

Let’s now see the scaffodling code:

public static async Task Simulate()
{
	Initialize();
	StartMonitoringThread();
	await RunLoop();
}

private static void Initialize()
{
	CurrentStats = new Stats();
	CurrentSettings = new Settings
	{
		ReceivingDuration = TimeSpan.FromMilliseconds(250),
		RefreshDelay = TimeSpan.FromSeconds(2),
		RefreshDuration = TimeSpan.FromMilliseconds(250),
		MessageLeaseTimeout = TimeSpan.FromSeconds(5),
		ProcessingCPUDuration = TimeSpan.FromMilliseconds(100),
		ProcessingIODuration = TimeSpan.FromMilliseconds(1000),
		ProcessingLoops = 20,
		MessagesCount = 100
	};
}

private static void StartMonitoringThread()
{
	Thread monitoringThread = new Thread(() =>
	{
		while (true)
		{
			Thread.Sleep(TimeSpan.FromSeconds(3));
			Log($"Received messages {CurrentStats.GeneratedMessages}, " +
				$"success {CurrentStats.ProcessedSuccessfully}, " +
				$"failed {CurrentStats.Lost}, " +
				$"still running {CurrentStats.GeneratedMessages - CurrentStats.ProcessedSuccessfully - CurrentStats.Lost}");
		}
	});
	monitoringThread.IsBackground = true;
	monitoringThread.Start();
}

We have the Simulate method that runs the magic. It starts by initializing the timings and setting up some monitoring thread to print statistics every three seconds.

When it comes to the timings: we will run 20 loops for each message. In each loop’s iteration, we will do some CPU-bound operation (taking 100 milliseconds), and then some IO-bound operation (taking 1000 milliseconds). We can see that the CPU operation is 10 times shorter than the IO-bound one.

Finally, we have the heart of our system:

private static async Task RunLoop()
{
	while (true)
	{
		var message = await ReceiveMessage();
		if (message == null) continue;

		KeepLease(message);
		ProcessMessage(message);
	}
}

We receive the message, keep refreshing the lease, and process the message. Some error-handling code is omitted for brevity.

Receiving the message is rather straightforward – we check if we have more messages in the queue, then take one, otherwise we simply return:

public static async Task<Message?> ReceiveMessage()
{
	await Task.Yield();
	await Task.Delay(CurrentSettings.ReceivingDuration);

	if (CurrentSettings.MessagesCount-- > 0)
	{
		CurrentStats.GeneratedMessages++;
		Message message = new Message
		{
			LastRefreshTime = DateTime.Now,
			WasLost = false,
			Id = CurrentStats.GeneratedMessages,
			ReceiveTime = DateTime.Now
		};
		Log($"New message received with id {message.Id}");
		return message;
	}
	else
	{
		return null;
	}
}

Keeping a lease is also clear – we wait for some time, then refresh the lease and check if we made it on time:

public static async Task KeepLease(Message message)
{
	await Task.Yield();

	while (message.WasFinished == false) // This is unsafe according to memory model
	{
		await Task.Delay(CurrentSettings.RefreshDelay);

		if (DateTime.Now > message.LastRefreshTime + CurrentSettings.MessageLeaseTimeout)
		{
			message.WasLost = true;
			CurrentStats.Lost++;
			Log($"Lost lease for message {message.Id}");
			return;
		}
		else
		{
			await Task.Delay(CurrentSettings.RefreshDuration);
			Log($"Refreshed lease for message {message.Id}");
			message.LastRefreshTime = DateTime.Now;
		}
	}

	CurrentStats.ProcessedSuccessfully++;
}

Finally, the heart of our message processing. We simply run a loop and do the work:

public static async Task ProcessMessage(Message message)
{
	await Task.Yield();

	for (int part = 0; part < CurrentSettings.ProcessingLoops && message.WasLost == false; ++part)
	{
		Thread.Sleep(CurrentSettings.ProcessingCPUDuration); // CPU-bound part

		await Task.Delay(CurrentSettings.ProcessingIODuration); // IO-bound part
	}

	message.WasFinished = true;
	if (!message.WasLost)
	{
		Log($"Finished message with id {message.Id} in {DateTime.Now - message.ReceiveTime}");
	}
}

Notice that we block the thread for the CPU-bound operation and use await for the IO-bound one.

We also have this logging method that prints the timestamp, thread ID, and the message:

public static void Log(string message)
{
	Console.WriteLine($"{DateTime.Now}\t{Thread.CurrentThread.ManagedThreadId}\t{message}");
}

Let’s run the code, let it go for a while, and then see what happens:

11/9/2024 12:05:06 PM   4       New message received with id 1
11/9/2024 12:05:06 PM   6       New message received with id 2
11/9/2024 12:05:06 PM   6       New message received with id 3
11/9/2024 12:05:07 PM   8       New message received with id 4
11/9/2024 12:05:07 PM   8       New message received with id 5
11/9/2024 12:05:07 PM   4       New message received with id 6
11/9/2024 12:05:08 PM   4       New message received with id 7
11/9/2024 12:05:08 PM   4       New message received with id 8
11/9/2024 12:05:08 PM   11      New message received with id 9
11/9/2024 12:05:08 PM   8       Refreshed lease for message 1
11/9/2024 12:05:08 PM   12      New message received with id 10
11/9/2024 12:05:08 PM   11      Refreshed lease for message 2
11/9/2024 12:05:09 PM   12      New message received with id 11
11/9/2024 12:05:09 PM   7       Received messages 11, success 0, failed 0, still running 11
11/9/2024 12:05:09 PM   11      Refreshed lease for message 3
11/9/2024 12:05:09 PM   11      New message received with id 12
11/9/2024 12:05:09 PM   12      Refreshed lease for message 4
11/9/2024 12:05:09 PM   6       New message received with id 13
11/9/2024 12:05:09 PM   8       Refreshed lease for message 5
11/9/2024 12:05:09 PM   12      New message received with id 14
11/9/2024 12:05:10 PM   12      Refreshed lease for message 6
11/9/2024 12:05:10 PM   12      New message received with id 15
11/9/2024 12:05:10 PM   11      Refreshed lease for message 7
11/9/2024 12:05:10 PM   11      New message received with id 16
11/9/2024 12:05:10 PM   6       Refreshed lease for message 8
11/9/2024 12:05:10 PM   12      New message received with id 17
11/9/2024 12:05:10 PM   11      Refreshed lease for message 9
11/9/2024 12:05:10 PM   8       New message received with id 18
11/9/2024 12:05:10 PM   11      Refreshed lease for message 1
11/9/2024 12:05:11 PM   4       Refreshed lease for message 10
11/9/2024 12:05:11 PM   13      New message received with id 19
11/9/2024 12:05:11 PM   12      Refreshed lease for message 2
11/9/2024 12:05:11 PM   13      Refreshed lease for message 11
11/9/2024 12:05:11 PM   11      New message received with id 20
11/9/2024 12:05:11 PM   6       Refreshed lease for message 3
11/9/2024 12:05:11 PM   4       Refreshed lease for message 12
11/9/2024 12:05:11 PM   13      New message received with id 21
11/9/2024 12:05:11 PM   13      Refreshed lease for message 4
11/9/2024 12:05:11 PM   4       Refreshed lease for message 13
11/9/2024 12:05:11 PM   4       New message received with id 22
11/9/2024 12:05:12 PM   4       Refreshed lease for message 5
11/9/2024 12:05:12 PM   6       Refreshed lease for message 14
11/9/2024 12:05:12 PM   13      New message received with id 23
11/9/2024 12:05:12 PM   7       Received messages 23, success 0, failed 0, still running 23
11/9/2024 12:05:12 PM   4       Refreshed lease for message 6
11/9/2024 12:05:12 PM   4       Refreshed lease for message 15
...
11/9/2024 12:05:50 PM   15      Finished message with id 84 in 00:00:22.3550821
11/9/2024 12:05:50 PM   15      Refreshed lease for message 83
11/9/2024 12:05:50 PM   4       Refreshed lease for message 100
11/9/2024 12:05:50 PM   8       Finished message with id 85 in 00:00:22.3554494
11/9/2024 12:05:50 PM   15      Refreshed lease for message 84
11/9/2024 12:05:50 PM   20      Refreshed lease for message 92
11/9/2024 12:05:50 PM   20      Finished message with id 86 in 00:00:22.3882717
11/9/2024 12:05:50 PM   8       Refreshed lease for message 93
11/9/2024 12:05:51 PM   4       Refreshed lease for message 85
11/9/2024 12:05:51 PM   20      Finished message with id 87 in 00:00:22.3452990
11/9/2024 12:05:51 PM   4       Refreshed lease for message 94
11/9/2024 12:05:51 PM   20      Refreshed lease for message 86
11/9/2024 12:05:51 PM   7       Received messages 100, success 86, failed 0, still running 14
11/9/2024 12:05:51 PM   14      Finished message with id 88 in 00:00:22.3968974
11/9/2024 12:05:51 PM   13      Refreshed lease for message 87
11/9/2024 12:05:51 PM   4       Refreshed lease for message 95
11/9/2024 12:05:51 PM   4       Refreshed lease for message 88
11/9/2024 12:05:51 PM   14      Finished message with id 89 in 00:00:22.3782384
11/9/2024 12:05:51 PM   4       Refreshed lease for message 96
11/9/2024 12:05:51 PM   15      Finished message with id 90 in 00:00:22.3557212
11/9/2024 12:05:51 PM   15      Refreshed lease for message 89
11/9/2024 12:05:52 PM   13      Refreshed lease for message 97
11/9/2024 12:05:52 PM   20      Refreshed lease for message 90
11/9/2024 12:05:52 PM   15      Finished message with id 91 in 00:00:22.4805351
11/9/2024 12:05:52 PM   15      Refreshed lease for message 98
11/9/2024 12:05:52 PM   20      Refreshed lease for message 91
11/9/2024 12:05:52 PM   15      Refreshed lease for message 99
11/9/2024 12:05:52 PM   15      Finished message with id 92 in 00:00:22.3979587
11/9/2024 12:05:52 PM   4       Refreshed lease for message 100
11/9/2024 12:05:52 PM   20      Finished message with id 93 in 00:00:22.3374987
11/9/2024 12:05:53 PM   4       Refreshed lease for message 92
11/9/2024 12:05:53 PM   4       Finished message with id 94 in 00:00:22.3451488
11/9/2024 12:05:53 PM   4       Refreshed lease for message 93
11/9/2024 12:05:53 PM   13      Refreshed lease for message 94
11/9/2024 12:05:53 PM   13      Finished message with id 95 in 00:00:22.3784563
11/9/2024 12:05:53 PM   13      Finished message with id 96 in 00:00:22.3800325
11/9/2024 12:05:53 PM   13      Refreshed lease for message 95
11/9/2024 12:05:54 PM   4       Finished message with id 97 in 00:00:22.3312738
11/9/2024 12:05:54 PM   20      Refreshed lease for message 96
11/9/2024 12:05:54 PM   7       Received messages 100, success 96, failed 0, still running 4
11/9/2024 12:05:54 PM   13      Finished message with id 98 in 00:00:22.3502617
11/9/2024 12:05:54 PM   4       Refreshed lease for message 97
11/9/2024 12:05:54 PM   13      Finished message with id 99 in 00:00:22.3527442
11/9/2024 12:05:54 PM   4       Refreshed lease for message 98
11/9/2024 12:05:54 PM   4       Finished message with id 100 in 00:00:22.3675039
11/9/2024 12:05:54 PM   13      Refreshed lease for message 99
11/9/2024 12:05:55 PM   13      Refreshed lease for message 100
11/9/2024 12:05:57 PM   7       Received messages 100, success 100, failed 0, still running 0

We can see that all messaged were processed successfully in around 50 seconds. Processing a message was taking around 22 seconds which makes perfect sense since we had 20 iterations taking around 1100 milliseconds each. No failures, all was good.

Let’s now increase the CPU-bound operation time to 1 second (to match the IO-bound part). This is what happens:

11/9/2024 12:06:57 PM   8       New message received with id 1
11/9/2024 12:06:57 PM   11      New message received with id 2
11/9/2024 12:06:58 PM   11      New message received with id 3
11/9/2024 12:06:58 PM   4       New message received with id 4
11/9/2024 12:06:58 PM   13      New message received with id 5
11/9/2024 12:06:58 PM   13      New message received with id 6
11/9/2024 12:06:59 PM   14      New message received with id 7
11/9/2024 12:06:59 PM   11      New message received with id 8
11/9/2024 12:06:59 PM   4       New message received with id 9
11/9/2024 12:06:59 PM   15      Refreshed lease for message 1
11/9/2024 12:06:59 PM   4       New message received with id 10
11/9/2024 12:07:00 PM   12      Refreshed lease for message 2
11/9/2024 12:07:00 PM   12      New message received with id 11
11/9/2024 12:07:00 PM   7       Received messages 11, success 0, failed 0, still running 11
11/9/2024 12:07:00 PM   6       Refreshed lease for message 3
11/9/2024 12:07:00 PM   16      New message received with id 12
11/9/2024 12:07:00 PM   14      Refreshed lease for message 4
11/9/2024 12:07:00 PM   14      New message received with id 13
11/9/2024 12:07:00 PM   15      Refreshed lease for message 5
11/9/2024 12:07:00 PM   4       New message received with id 14
11/9/2024 12:07:01 PM   13      Refreshed lease for message 6
11/9/2024 12:07:01 PM   12      New message received with id 15
11/9/2024 12:07:01 PM   6       Refreshed lease for message 7
11/9/2024 12:07:01 PM   16      New message received with id 16
11/9/2024 12:07:01 PM   14      Refreshed lease for message 8
11/9/2024 12:07:01 PM   4       Refreshed lease for message 9
11/9/2024 12:07:02 PM   13      Refreshed lease for message 1
11/9/2024 12:07:02 PM   12      Refreshed lease for message 10
11/9/2024 12:07:02 PM   12      New message received with id 17
11/9/2024 12:07:02 PM   6       Refreshed lease for message 2
11/9/2024 12:07:02 PM   16      Refreshed lease for message 11
11/9/2024 12:07:02 PM   14      Refreshed lease for message 3
11/9/2024 12:07:02 PM   14      Refreshed lease for message 12
11/9/2024 12:07:02 PM   4       Refreshed lease for message 4
11/9/2024 12:07:03 PM   13      Refreshed lease for message 13
11/9/2024 12:07:03 PM   13      Refreshed lease for message 5
11/9/2024 12:07:03 PM   12      Refreshed lease for message 14
11/9/2024 12:07:03 PM   12      New message received with id 18
11/9/2024 12:07:03 PM   7       Received messages 18, success 0, failed 0, still running 18
11/9/2024 12:07:03 PM   16      Refreshed lease for message 6
11/9/2024 12:07:03 PM   16      Refreshed lease for message 15
...
11/9/2024 12:08:38 PM   21      Finished message with id 88 in 00:00:42.4181405
11/9/2024 12:08:38 PM   42      Finished message with id 90 in 00:00:41.9138898
11/9/2024 12:08:38 PM   8       Refreshed lease for message 91
11/9/2024 12:08:38 PM   28      Refreshed lease for message 85
11/9/2024 12:08:38 PM   28      Refreshed lease for message 88
11/9/2024 12:08:39 PM   24      Finished message with id 85 in 00:00:43.9296927
11/9/2024 12:08:39 PM   16      Finished message with id 93 in 00:00:40.6588087
11/9/2024 12:08:39 PM   7       Received messages 100, success 88, failed 0, still running 12
11/9/2024 12:08:39 PM   21      Refreshed lease for message 93
11/9/2024 12:08:39 PM   23      Refreshed lease for message 94
11/9/2024 12:08:39 PM   16      Refreshed lease for message 92
11/9/2024 12:08:40 PM   23      Refreshed lease for message 97
11/9/2024 12:08:40 PM   16      Refreshed lease for message 99
11/9/2024 12:08:40 PM   21      Refreshed lease for message 96
11/9/2024 12:08:40 PM   42      Refreshed lease for message 98
11/9/2024 12:08:40 PM   16      Refreshed lease for message 90
11/9/2024 12:08:40 PM   42      Refreshed lease for message 95
11/9/2024 12:08:40 PM   42      Refreshed lease for message 100
11/9/2024 12:08:40 PM   24      Finished message with id 94 in 00:00:41.3801588
11/9/2024 12:08:40 PM   8       Finished message with id 92 in 00:00:41.9121719
11/9/2024 12:08:40 PM   8       Finished message with id 95 in 00:00:41.1802881
11/9/2024 12:08:40 PM   24      Finished message with id 96 in 00:00:40.9180345
11/9/2024 12:08:40 PM   24      Refreshed lease for message 91
11/9/2024 12:08:40 PM   52      Refreshed lease for message 85
11/9/2024 12:08:41 PM   24      Finished message with id 98 in 00:00:41.3325727
11/9/2024 12:08:41 PM   21      Finished message with id 91 in 00:00:43.1595798
11/9/2024 12:08:42 PM   24      Refreshed lease for message 94
11/9/2024 12:08:42 PM   42      Refreshed lease for message 92
11/9/2024 12:08:42 PM   24      Refreshed lease for message 99
11/9/2024 12:08:42 PM   8       Refreshed lease for message 97
11/9/2024 12:08:42 PM   42      Refreshed lease for message 96
11/9/2024 12:08:42 PM   24      Finished message with id 97 in 00:00:42.6127819
11/9/2024 12:08:42 PM   42      Refreshed lease for message 98
11/9/2024 12:08:42 PM   42      Finished message with id 99 in 00:00:40.4341505
11/9/2024 12:08:42 PM   7       Received messages 100, success 95, failed 0, still running 5
11/9/2024 12:08:42 PM   21      Refreshed lease for message 95
11/9/2024 12:08:42 PM   42      Refreshed lease for message 100
11/9/2024 12:08:43 PM   42      Refreshed lease for message 91
11/9/2024 12:08:43 PM   8       Finished message with id 100 in 00:00:41.1363357
11/9/2024 12:08:44 PM   21      Refreshed lease for message 97
11/9/2024 12:08:44 PM   52      Refreshed lease for message 99
11/9/2024 12:08:44 PM   52      Refreshed lease for message 100
11/9/2024 12:08:45 PM   7       Received messages 100, success 100, failed 0, still running 0

This time it took nearly 2 minutes to process all the messages. Each message is now taking around 40 seconds. Still, all worked.

Let’s now talk about threads. You can see that the examples use multiple threads to handle the messages. In the second execution, there were around 60 active messages at one time, so this created many threads (we can see that at least 50 threads were created based on the log above). Our application scales well and we can’t complain. Seems like async is doing a really good job!

However, what would happen if we moved this code to some other asynchronous platform? For instance, to Python’s asyncio that uses only single thread? We can emulate that in C# by running the code above in a WinForms context that forces continuations to go through one thread. Let’s change the CPU-bound operation duration to 100 milliseconds (to the original value) and let’s run this from the WinForms app now:

11/9/2024 12:19:20 PM   1       New message received with id 1
11/9/2024 12:19:20 PM   1       New message received with id 2
11/9/2024 12:19:20 PM   1       New message received with id 3
11/9/2024 12:19:21 PM   1       New message received with id 4
11/9/2024 12:19:21 PM   1       New message received with id 5
11/9/2024 12:19:22 PM   1       New message received with id 6
11/9/2024 12:19:22 PM   1       New message received with id 7
11/9/2024 12:19:22 PM   1       Refreshed lease for message 1
11/9/2024 12:19:22 PM   1       New message received with id 8
11/9/2024 12:19:22 PM   11      Received messages 8, success 0, failed 0, still running 8
11/9/2024 12:19:23 PM   1       Refreshed lease for message 2
11/9/2024 12:19:23 PM   1       New message received with id 9
11/9/2024 12:19:23 PM   1       Refreshed lease for message 3
11/9/2024 12:19:23 PM   1       New message received with id 10
11/9/2024 12:19:23 PM   1       Refreshed lease for message 4
11/9/2024 12:19:24 PM   1       Refreshed lease for message 5
11/9/2024 12:19:24 PM   1       New message received with id 11
11/9/2024 12:19:24 PM   1       Refreshed lease for message 6
11/9/2024 12:19:24 PM   1       New message received with id 12
11/9/2024 12:19:25 PM   1       Refreshed lease for message 7
11/9/2024 12:19:25 PM   1       Refreshed lease for message 1
11/9/2024 12:19:25 PM   1       Refreshed lease for message 8
11/9/2024 12:19:25 PM   1       New message received with id 13
11/9/2024 12:19:25 PM   11      Received messages 13, success 0, failed 0, still running 13
11/9/2024 12:19:26 PM   1       Refreshed lease for message 2
11/9/2024 12:19:26 PM   1       Refreshed lease for message 9
...
11/9/2024 12:21:15 PM   1       Refreshed lease for message 58
11/9/2024 12:21:15 PM   1       Refreshed lease for message 62
11/9/2024 12:21:15 PM   1       Finished message with id 46 in 00:00:42.5373955
11/9/2024 12:21:16 PM   1       Refreshed lease for message 49
11/9/2024 12:21:16 PM   1       Refreshed lease for message 51
11/9/2024 12:21:16 PM   1       Refreshed lease for message 53
11/9/2024 12:21:17 PM   1       New message received with id 65
11/9/2024 12:21:17 PM   1       Refreshed lease for message 55
11/9/2024 12:21:17 PM   1       Refreshed lease for message 46
11/9/2024 12:21:17 PM   1       Refreshed lease for message 57
11/9/2024 12:21:17 PM   1       Refreshed lease for message 59
11/9/2024 12:21:17 PM   11      Received messages 65, success 43, failed 3, still running 19
11/9/2024 12:21:17 PM   1       Refreshed lease for message 61
11/9/2024 12:21:17 PM   1       Refreshed lease for message 48
...
11/9/2024 12:22:53 PM   11      Received messages 100, success 90, failed 3, still running 7
11/9/2024 12:22:53 PM   1       Refreshed lease for message 97
11/9/2024 12:22:53 PM   1       Refreshed lease for message 99
11/9/2024 12:22:54 PM   1       Refreshed lease for message 94
11/9/2024 12:22:54 PM   1       Refreshed lease for message 96
11/9/2024 12:22:54 PM   1       Finished message with id 95 in 00:00:32.1189187
11/9/2024 12:22:54 PM   1       Refreshed lease for message 98
11/9/2024 12:22:54 PM   1       Refreshed lease for message 100
11/9/2024 12:22:55 PM   1       Refreshed lease for message 95
11/9/2024 12:22:56 PM   1       Finished message with id 96 in 00:00:31.0536654
11/9/2024 12:22:56 PM   1       Refreshed lease for message 99
11/9/2024 12:22:56 PM   1       Refreshed lease for message 97
11/9/2024 12:22:56 PM   11      Received messages 100, success 92, failed 3, still running 5
11/9/2024 12:22:56 PM   1       Refreshed lease for message 96
11/9/2024 12:22:57 PM   1       Refreshed lease for message 98
11/9/2024 12:22:57 PM   1       Refreshed lease for message 100
11/9/2024 12:22:57 PM   1       Finished message with id 97 in 00:00:30.1211740
11/9/2024 12:22:58 PM   1       Refreshed lease for message 99
11/9/2024 12:22:58 PM   1       Refreshed lease for message 97
11/9/2024 12:22:58 PM   1       Finished message with id 98 in 00:00:29.1238261
11/9/2024 12:22:59 PM   1       Refreshed lease for message 98
11/9/2024 12:22:59 PM   1       Refreshed lease for message 100
11/9/2024 12:22:59 PM   11      Received messages 100, success 95, failed 3, still running 2
11/9/2024 12:22:59 PM   1       Finished message with id 99 in 00:00:28.1643467
11/9/2024 12:23:00 PM   1       Refreshed lease for message 99
11/9/2024 12:23:00 PM   1       Finished message with id 100 in 00:00:27.2119750
11/9/2024 12:23:01 PM   1       Refreshed lease for message 100
11/9/2024 12:23:02 PM   11      Received messages 100, success 97, failed 3, still running 0

It wasn’t that bad and we can see that we indeed ran on a single thread. First, notice that now it took nearly 4 minutes to complete. That’s understandable as we now run things on a single thread. Also, notice that each message was taking around 30-40 seconds to complete. That is much longer than before. This is because messages compete for the CPU time and we don’t have any parallelism. It’s also worth noting that we lost 3 messages. That’s not that bad. The system overscaled just a bit and couldn’t deal with the load but the stabilized and finished processing.

Let’s now increase the CPU-bound duration to 1 second and try again:

11/9/2024 12:24:26 PM   1       New message received with id 1
11/9/2024 12:24:27 PM   1       New message received with id 2
11/9/2024 12:24:29 PM   12      Received messages 2, success 0, failed 0, still running 2
11/9/2024 12:24:29 PM   1       New message received with id 3
11/9/2024 12:24:29 PM   1       Refreshed lease for message 1
11/9/2024 12:24:32 PM   12      Received messages 3, success 0, failed 0, still running 3
11/9/2024 12:24:32 PM   1       Refreshed lease for message 2
11/9/2024 12:24:33 PM   1       New message received with id 4
11/9/2024 12:24:34 PM   1       Lost lease for message 3
11/9/2024 12:24:34 PM   1       Refreshed lease for message 1
11/9/2024 12:24:35 PM   12      Received messages 4, success 0, failed 1, still running 3
11/9/2024 12:24:38 PM   12      Received messages 4, success 0, failed 1, still running 3
11/9/2024 12:24:39 PM   1       Refreshed lease for message 2
11/9/2024 12:24:39 PM   1       New message received with id 5
11/9/2024 12:24:39 PM   1       Lost lease for message 4
11/9/2024 12:24:39 PM   1       Refreshed lease for message 1
11/9/2024 12:24:41 PM   12      Received messages 5, success 0, failed 2, still running 3
11/9/2024 12:24:43 PM   1       New message received with id 6
11/9/2024 12:24:44 PM   12      Received messages 6, success 0, failed 2, still running 4
11/9/2024 12:24:46 PM   1       Refreshed lease for message 5
...
11/9/2024 12:31:48 PM   1       Lost lease for message 98
11/9/2024 12:31:51 PM   12      Received messages 99, success 7, failed 88, still running 4
11/9/2024 12:31:52 PM   1       Refreshed lease for message 97
11/9/2024 12:31:52 PM   1       Refreshed lease for message 92
11/9/2024 12:31:52 PM   1       Refreshed lease for message 86
11/9/2024 12:31:54 PM   12      Received messages 99, success 7, failed 88, still running 4
11/9/2024 12:31:54 PM   1       New message received with id 100
11/9/2024 12:31:54 PM   1       Lost lease for message 99
11/9/2024 12:31:54 PM   1       Finished message with id 86 in 00:01:04.5795457
11/9/2024 12:31:57 PM   12      Received messages 100, success 7, failed 89, still running 4
11/9/2024 12:31:57 PM   1       Refreshed lease for message 86
11/9/2024 12:31:57 PM   1       Refreshed lease for message 97
11/9/2024 12:31:58 PM   1       Refreshed lease for message 92
11/9/2024 12:31:59 PM   1       Lost lease for message 100
11/9/2024 12:32:00 PM   12      Received messages 100, success 8, failed 90, still running 2
11/9/2024 12:32:01 PM   1       Refreshed lease for message 97
11/9/2024 12:32:02 PM   1       Refreshed lease for message 92
11/9/2024 12:32:03 PM   12      Received messages 100, success 8, failed 90, still running 2
11/9/2024 12:32:04 PM   1       Refreshed lease for message 97
11/9/2024 12:32:05 PM   1       Refreshed lease for message 92
11/9/2024 12:32:06 PM   12      Received messages 100, success 8, failed 90, still running 2
11/9/2024 12:32:08 PM   1       Refreshed lease for message 97
11/9/2024 12:32:09 PM   12      Received messages 100, success 8, failed 90, still running 2
11/9/2024 12:32:09 PM   1       Refreshed lease for message 92
11/9/2024 12:32:11 PM   1       Refreshed lease for message 97
11/9/2024 12:32:12 PM   12      Received messages 100, success 8, failed 90, still running 2
11/9/2024 12:32:12 PM   1       Finished message with id 92 in 00:00:55.4921671
11/9/2024 12:32:13 PM   1       Refreshed lease for message 92
11/9/2024 12:32:14 PM   1       Refreshed lease for message 97
11/9/2024 12:32:15 PM   12      Received messages 100, success 9, failed 90, still running 1
11/9/2024 12:32:17 PM   1       Refreshed lease for message 97
11/9/2024 12:32:18 PM   12      Received messages 100, success 9, failed 90, still running 1
11/9/2024 12:32:19 PM   1       Refreshed lease for message 97
11/9/2024 12:32:21 PM   12      Received messages 100, success 9, failed 90, still running 1
11/9/2024 12:32:21 PM   1       Refreshed lease for message 97
11/9/2024 12:32:24 PM   1       Refreshed lease for message 97
11/9/2024 12:32:24 PM   12      Received messages 100, success 9, failed 90, still running 1
11/9/2024 12:32:27 PM   1       Refreshed lease for message 97
11/9/2024 12:32:27 PM   12      Received messages 100, success 9, failed 90, still running 1
11/9/2024 12:32:28 PM   1       Finished message with id 97 in 00:00:50.4062632
11/9/2024 12:32:29 PM   1       Refreshed lease for message 97
11/9/2024 12:32:30 PM   12      Received messages 100, success 10, failed 90, still running 0

And here things start to collapse. It took us 8 minutes to process all messages, each of them was taking around 1 minute, and we failed to process 90 out of one hundred. We lost 90% of all of the messages. Our system became unreliable just because we increased the CPU-bound part of the message processing. But why did it break the application exactly? What happened?

You don’t control the priority of continuations

Our application runs three distinct operations in total:

• Take the message from the queue
• Refresh the lease of the message
• Do some processing of the message

Every single time we await the task, we release the thread and let it do something else. Once the IO-bound operation finishes, we schedule it to run on the same thread. However, the order of continuations doesn’t reflect the importance of what we should do.

In order to keep the system stable, we need to refresh the leases. Therefore, if there is any continuation that wants to refresh the lease (the continuation in KeepLease method), it should run before everything else.

Once we don’t have any continuations for refreshing the leases, we should run continuations for message processing. Obviously, if some KeepLease continuation gets scheduled, it should preempt other continuations.

Finally, when we have no continuations for refreshing the leases or processing the messages, we should run the continuation for getting new message from the queue. In other words, we receive a new message only when we have some idle CPU time that we can use to process something more.

Unfortunately, the async in C# doesn’t let you easily prioritize the continuations. However, this is not a problem most of the times because C# uses multiple threads! Once a continuation is free to run, the thread pool will grow to run the continuation earlier if possible. This is not part of the async programming paradigm and you can’t take it for granted. However, when we run things on a single thread, then continuations have no priorities and message processing continuations may stop lease refreshing continuations from running. Even worse, we may run continuation that receives new message from the bus even though we are already overloaded.

Depending on the nature of your platform (be it C# with different synchronization context, Python with single-threaded asyncio, or JavaScript with one and only one thread), you may get different results. Your application may scale well or may fail badly.

Let’s fix it

We can fix this issue in many ways. Conceptually, we need three different queues: the first one represents the lease refreshments, the second is for message processing, and the third is for getting new message from the bus. We would then have one processor that would check each of the queues in order and execute the operations accordingly. Unfortunately, rewriting the application from async paradigm to a consumer with multiple queues is not straightforward.

Instead, we can reorder the continuations. The trick is to introduce a priority for each continuation. We do the following:

1. We store a desired priority of continuations running on a thread
2. When a continuation wants to run, it checks if the desired priority is equal to the priority of the continuation
3. If it’s equal, then the continuation resets the desired priority to some invalid value and continues
4. Otherwise, the continuation bumps the priority if possible and lets other continuations run

The protocol is based on the following idea: some continuation sets the desired priority to be at least the priority of the continuation and then lets other continuations to run. If there are other continuations of lower priority, they will simply release the CPU and reschedule themselves. If there are continuations of some higher priority, they will bump the desired priority. And if there are no continuations, then th original continuation will finally get the CPU, run the code, and reset the priority, so other continuations can run the same dance over and over. Here is the code:

public static async Task Prioritize(int priority)
{
	var cookie = Guid.NewGuid();

	while (true)
	{
		if (CurrentSettings.DesiredPriority == priority && CurrentSettings.Cookie == cookie)
		{
			CurrentSettings.DesiredPriority = -1;
			CurrentSettings.Cookie = Guid.Empty;
			return;
		}
		else
		{
			if (CurrentSettings.DesiredPriority < priority)
			{
				CurrentSettings.DesiredPriority = priority;
				CurrentSettings.Cookie = cookie;
				await Task.Yield();
				continue;
			}
			else
			{
				await Task.Yield();
				continue;
			}
		}
	}
}

We need to run this method every single time when we run await. For instance, KeepLease becomes this:

public static async Task KeepLease(Message message)
{
	await Task.Yield();
	await Prioritize(3);

	while (message.WasFinished == false) // This is unsafe according to memory model
	{
		await Task.Delay(CurrentSettings.RefreshDelay);
		await Prioritize(3);

		if (DateTime.Now > message.LastRefreshTime + CurrentSettings.MessageLeaseTimeout)
		{
			message.WasLost = true;
			CurrentStats.Lost++;
			Log($"Lost lease for message {message.Id}");
			return;
		}
		else
		{
			await Task.Delay(CurrentSettings.RefreshDuration);
			await Prioritize(3);
			Log($"Refreshed lease for message {message.Id}");
			message.LastRefreshTime = DateTime.Now;
		}
	}

	CurrentStats.ProcessedSuccessfully++;
}

You can find the full snippet here. Let’s see it in action:

11/9/2024 12:35:42 PM   1       New message received with id 1
11/9/2024 12:35:43 PM   1       New message received with id 2
11/9/2024 12:35:45 PM   12      Received messages 2, success 0, failed 0, still running 2
11/9/2024 12:35:45 PM   1       Refreshed lease for message 1
11/9/2024 12:35:46 PM   1       Refreshed lease for message 2
11/9/2024 12:35:48 PM   12      Received messages 2, success 0, failed 0, still running 2
11/9/2024 12:35:48 PM   1       Refreshed lease for message 1
11/9/2024 12:35:49 PM   1       Refreshed lease for message 2
11/9/2024 12:35:51 PM   12      Received messages 2, success 0, failed 0, still running 2
11/9/2024 12:35:51 PM   1       Refreshed lease for message 1
11/9/2024 12:35:52 PM   1       Refreshed lease for message 2
11/9/2024 12:35:53 PM   1       New message received with id 3
11/9/2024 12:35:54 PM   12      Received messages 3, success 0, failed 0, still running 3
11/9/2024 12:35:55 PM   1       Refreshed lease for message 1
11/9/2024 12:35:56 PM   1       Refreshed lease for message 3
11/9/2024 12:35:57 PM   12      Received messages 3, success 0, failed 0, still running 3
11/9/2024 12:35:58 PM   1       Refreshed lease for message 1
11/9/2024 12:35:58 PM   1       Refreshed lease for message 2
11/9/2024 12:35:59 PM   1       Refreshed lease for message 3
11/9/2024 12:36:00 PM   12      Received messages 3, success 0, failed 0, still running 3
11/9/2024 12:36:01 PM   1       Refreshed lease for message 1
11/9/2024 12:36:02 PM   1       Refreshed lease for message 3
11/9/2024 12:36:03 PM   12      Received messages 3, success 0, failed 0, still running 3
...
11/9/2024 1:09:00 PM    1       Refreshed lease for message 100
11/9/2024 1:09:00 PM    1       Refreshed lease for message 98
11/9/2024 1:09:02 PM    12      Received messages 100, success 97, failed 0, still running 3
11/9/2024 1:09:03 PM    1       Refreshed lease for message 99
11/9/2024 1:09:03 PM    1       Refreshed lease for message 100
11/9/2024 1:09:04 PM    1       Refreshed lease for message 98
11/9/2024 1:09:05 PM    1       Finished message with id 98 in 00:00:46.5274062
11/9/2024 1:09:05 PM    12      Received messages 100, success 97, failed 0, still running 3
11/9/2024 1:09:06 PM    1       Refreshed lease for message 100
11/9/2024 1:09:06 PM    1       Refreshed lease for message 99
11/9/2024 1:09:07 PM    1       Refreshed lease for message 98
11/9/2024 1:09:08 PM    12      Received messages 100, success 98, failed 0, still running 2
11/9/2024 1:09:09 PM    1       Refreshed lease for message 100
11/9/2024 1:09:09 PM    1       Refreshed lease for message 99
11/9/2024 1:09:11 PM    12      Received messages 100, success 98, failed 0, still running 2
11/9/2024 1:09:12 PM    1       Refreshed lease for message 99
11/9/2024 1:09:12 PM    1       Refreshed lease for message 100
11/9/2024 1:09:14 PM    12      Received messages 100, success 98, failed 0, still running 2
11/9/2024 1:09:15 PM    1       Refreshed lease for message 99
11/9/2024 1:09:15 PM    1       Refreshed lease for message 100
11/9/2024 1:09:17 PM    1       Finished message with id 99 in 00:00:51.5793525
11/9/2024 1:09:17 PM    1       Refreshed lease for message 99
11/9/2024 1:09:17 PM    1       Refreshed lease for message 100
11/9/2024 1:09:17 PM    12      Received messages 100, success 99, failed 0, still running 1
11/9/2024 1:09:19 PM    1       Refreshed lease for message 100
11/9/2024 1:09:20 PM    12      Received messages 100, success 99, failed 0, still running 1
11/9/2024 1:09:22 PM    1       Refreshed lease for message 100
11/9/2024 1:09:23 PM    12      Received messages 100, success 99, failed 0, still running 1
11/9/2024 1:09:25 PM    1       Refreshed lease for message 100
11/9/2024 1:09:26 PM    12      Received messages 100, success 99, failed 0, still running 1
11/9/2024 1:09:27 PM    1       Refreshed lease for message 100
11/9/2024 1:09:29 PM    12      Received messages 100, success 99, failed 0, still running 1
11/9/2024 1:09:29 PM    1       Refreshed lease for message 100
11/9/2024 1:09:30 PM    1       Finished message with id 100 in 00:00:54.5227973
11/9/2024 1:09:32 PM    1       Refreshed lease for message 100
11/9/2024 1:09:32 PM    12      Received messages 100, success 100, failed 0, still running 0

We can see that the code runs much slower and it takes 35 minutes to complete. However, all messages are processed successfully and the code scales automatically. We don’t need to manually control the thread pool size, but the application simply processes fewer or more messages depending on the actual CPU-bound processing time.

Summary

async programming is very hard. We were told many times that it’s as simple as putting async here and await there. C# did a lot to get rid of deadlocks as nearly every platform now uses no synchronization context (as compared with old ASP.NET which had its own context or all the desktop apps that were running with a single thread). Also, C# uses a thread pool and can fix many programmer’s mistakes that can limit the scalability.

However, asynchronous programming can be implemented in many other ways. You can’t assume that it will use many threads or that the coroutine will be triggered immediately. Many quirks can decrease the performance. Python’s asyncio is a great example of how asynchronous programming can work much differently, especially if you take the Python’s performance into consideration. What’s IO-bound in C#, can easily become CPU-bound in Python because Python is way slower.

This is the fifth part of the Bit Twiddling series. For your convenience you can find other parts in the table of contents in Par 1 — Modifying Android application on a binary level

Today we’re going to fix the audio latency in mstsc.exe. Something that people really ask about on the Internet and there is no definite solution. I’ll show how to hack mstsc.exe to fix the latency. First, I’ll explain why existing solutions do not work and what needs to be done, and at the end of this post I provide an automated PowerShell script that does the magic.

What is the issue

First, a disclaimer. I’ll describe what I suspect is happening. I’m not an expert of the RDP and I didn’t see the source code of mstsc.exe. I’m just guessing what happens based on what I see.

RDP supports multiple channels. There is a separate channel for video and another one for audio. Unfortunately, these two channels are not synchronized which means that they are synchronized on the client on a best effort basis (or rather sheer luck). To understand why it’s hard to synchronize two independent streams, we need to understand how much different they are.

Video is something that doesn’t need to be presented “for some time”. We can simply take the last video frame and show it to the user. If frames are buffered, we just process them as fast as possible to present the last state. You can see that mstsc.exe does exactly that by connecting to a remote host, playing some video, and then suspending the mstsc.exe process with ProcessExplorer. When you resume it after few seconds, you’ll see the video moving much faster until the client catches up with the latest state.

When it comes to audio, things are much different. You can’t just jump to the latest audio because you’d loose the content as it would be unintelligible. Each audio piece has its desired length. When you get delayed, you could just skip the packets (and lose some audio), play it faster (which would make it less intelligible for some time), or just play it as it goes. However, to decide what to do, you would need to understand whether the piece you want to play is delayed or not. You can’t tell that without timestamps or time markers, and I believe RDP doesn’t send those.

As long as you’re getting audio packets “on time”, there is no issue. You just play them. The first part is if you get them “in time”. This depends on your network quality and on the server that sends you the sound. From my experience, Windows Server is better when it comes to speed of sending updates. I can see my mouse moving faster and audio delayed less often when I connect to the Windows Server than Windows 10 (or other client edition). Therefore, use Windows Server where possible. Just keep in mind that you’ll need CAL licenses to send microphone and camera to the server which is a bummer (client edition lets you do that for free). Making the packets to be sent as fast as possible is the problem number one.

However, there is another part to that. If your client gets delayed for whatever reason (CPU spike, overload, or preemption), your sound will effectively slow down. You will just play it “later” even though you received it “on time”. Unfortunately, RDP cannot detect whether this happened because there are no timestamps in the stream. As far as I can tell, this is the true reason why your sound is often delayed. You can get “no latency audio” over the Internet and I had it many times. However, the longer you run the client, the higher the chance that you’ll go out of sync. This is the problem number two.

Therefore, we need to “resync” the client. Let’s see how to do it.

Why existing solutions don’t work and what fix we need

First, let me explain why existing solutions won’t work. Many articles on the Internet tell you to change the audio quality to High in Group Policy and enforce the quality in your rdp.file by setting audioqualitymode:i:2. This fixes the problem number one (although I don’t see much difference to be honest), but it doesn’t address the problem number two.

Some other articles suggest other fixes on the remote side. All these fixes have one thing in common – they don’t fix the client. If the mstsc.exe client cannot catch up when it gets delayed, then the only thing you can do is to reset the audio stream. Actually, this is how you can fix the delay easily – just restart the audio service:

net stop audiosrv & timeout 3 & net start audiosrv

I add the timeout to give some time to clear the buffer on the client. Once the buffer is empty, we restart the service and then the audio should be in sync. Try this to verify if it’s physically possible to deliver the audio “on time” in your networking conditions.

Unfortunately, restarting the audio service have many issues. First, it resets the devices on the remote end, so your audio streams may break and you’ll need to restart them. Second, this simply takes time. You probably don’t want to lose a couple of seconds of audio and microphone when you’re presenting (and unfortunately, you’ll get delayed exactly during that time).

What we need is to fix the client to catch up when there is a delay. However, how can we do that when we don’t have any timestamps? Well, the solution is simple – just drop some audio packages (like 10%) periodically to sync over time. This will decrease the audio quality to some extent and won’t fix the delay immediately, but after few seconds we’ll get back on track. Obviously, you could implement some better heuristics and solutions. There is one problem, though – we need to do that in the mstsc.exe itself. And here comes the low level magic. Let’s implement the solution that drops the audio frames to effectively “resync” the audio.

How to identify

We need to figure out how the sound is played. Let’s take ApiMonitor to trace the application. Luckily enough, it seems that the waveOutPrepareHeader is used, as we can see in the screenshot:

Let’s break there win WinDBG:

bu 0x00007ffb897d3019

kb

 # RetAddr               : Args to Child                                                           : Call Site														
00 00007ffb`897d1064     : 00000252`6d68beb8 00000252`6d68beb8 00000000`000014ac 00000252`6d68be00 : mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite+0x6d														
01 00007ffb`897e7ee8     : 00000000`00000000 00000073`bfc7fcb9 00000252`6d68be00 00000252`7e69df80 : mstscax!CRdpWinAudioWaveoutPlayback::vcwaveWritePCM+0xec														
02 00007ffb`898e73bf     : 00000000`00000001 00000000`00000003 00000073`bfc7d055 00000073`00001000 : mstscax!CRdpWinAudioWaveoutPlayback::RenderThreadProc+0x2c8														
03 00007ffc`02e57344     : 00000000`000000ac 00000252`6d68be00 00000000`00000000 00000000`00000000 : mstscax!CRdpWinAudioWaveoutPlayback::STATIC_ThreadProc+0xdf														
04 00007ffc`046826b1     : 00000000`00000000 00000000`00000000 00000000`00000000 00000000`00000000 : KERNEL32!BaseThreadInitThunk+0x14														
05 00000000`00000000     : 00000000`00000000 00000000`00000000 00000000`00000000 00000000`00000000 : ntdll!RtlUserThreadStart+0x21

We can see a method named mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite. Let’s see it:

u mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite+0x6d		
									
mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite:											
00007ffb`897d2fac 48895c2410      mov     qword ptr [rsp+10h],rbx											
00007ffb`897d2fb1 55              push    rbp											
00007ffb`897d2fb2 56              push    rsi											
00007ffb`897d2fb3 57              push    rdi											
00007ffb`897d2fb4 4883ec40        sub     rsp,40h											
00007ffb`897d2fb8 488bf2          mov     rsi,rdx											
00007ffb`897d2fbb 488bd9          mov     rbx,rcx											
00007ffb`897d2fbe 488b0543287500  mov     rax,qword ptr [mstscax!WPP_GLOBAL_Control (00007ffb`89f25808)]											
00007ffb`897d2fc5 488d2d3c287500  lea     rbp,[mstscax!WPP_GLOBAL_Control (00007ffb`89f25808)]											
00007ffb`897d2fcc 483bc5          cmp     rax,rbp											
00007ffb`897d2fcf 740a            je      mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite+0x2f (00007ffb`897d2fdb)											
00007ffb`897d2fd1 f6401c01        test    byte ptr [rax+1Ch],1											
00007ffb`897d2fd5 0f85e8000000    jne     mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite+0x117 (00007ffb`897d30c3)											
00007ffb`897d2fdb 83bbc000000000  cmp     dword ptr [rbx+0C0h],0											
00007ffb`897d2fe2 7418            je      mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite+0x50 (00007ffb`897d2ffc)											
00007ffb`897d2fe4 488b8bb8000000  mov     rcx,qword ptr [rbx+0B8h]											
00007ffb`897d2feb 4885c9          test    rcx,rcx											
00007ffb`897d2fee 740c            je      mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite+0x50 (00007ffb`897d2ffc)											
00007ffb`897d2ff0 48ff15a9295c00  call    qword ptr [mstscax!_imp_EnterCriticalSection (00007ffb`89d959a0)]											
00007ffb`897d2ff7 0f1f440000      nop     dword ptr [rax+rax]											
00007ffb`897d2ffc 488b4b70        mov     rcx,qword ptr [rbx+70h]											
00007ffb`897d3000 4885c9          test    rcx,rcx											
00007ffb`897d3003 0f84f2000000    je      mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite+0x14f (00007ffb`897d30fb)											
00007ffb`897d3009 41b830000000    mov     r8d,30h											
00007ffb`897d300f 488bd6          mov     rdx,rsi											
00007ffb`897d3012 48ff15e7a87900  call    qword ptr [mstscax!_imp_waveOutPrepareHeader (00007ffb`89f6d900)]											
00007ffb`897d3019 0f1f440000      nop     dword ptr [rax+rax]

Okay, we can see that this method passes the audio packet to the API. When we look at WAVEHDR structure, we can see that it has the following fields:

typedef struct wavehdr_tag {
  LPSTR              lpData;
  DWORD              dwBufferLength;
  DWORD              dwBytesRecorded;
  DWORD_PTR          dwUser;
  DWORD              dwFlags;
  DWORD              dwLoops;
  struct wavehdr_tag  *lpNext;
  DWORD_PTR          reserved;
} WAVEHDR, *LPWAVEHDR;

This is exactly what we see in ApiMonitor. Seems like the dwBufferLength is what we might want to change. When we shorten this buffer, we’ll effectively make the audio last shorter. We can do that for some of the packets to not break the quality much, and then all should be good.

We can verify that this works with this breakpoint:

bp 00007ffb`897d3012 "r @$t0 = poi(rdx + 8); r @$t1 = @$t0 / 2; ed rdx+8 @$t1; g"

Unfortunately, this makes the client terribly slow. We need to patch the code in place. Effectively, we need to inject a shellcode.

First, we need to allocate some meory with VirtualAllocEx via .dvalloc.

.dvalloc 1024

The debugger allocates the memory. In my case the address is 25fb8960000.

The address of the WinAPI function is in the memory, so we need to remember to extract the pointer from the address:

00007ffb`897d3012 48ff15e7a87900  call    qword ptr [mstscax!_imp_waveOutPrepareHeader (00007ffb`89f6d900)]

Now we need to do two things: first, we need to patch the call site to call our shellcode instead of [mstscax!_imp_waveOutPrepareHeader (00007ffb89f6d900)]. Second, we need to construct a shell code that fixes the audio packet for some of the packets, and then calls [mstscax!_imp_waveOutPrepareHeader (00007ffb89f6d900)] correctly.

To do the first thing, we can do the absolute jump trick. We put the address in the rax register, push it on the stack, and then return. This is the code:

mov rax, 0x25fb8960000	;Move the address to the register
push rax		;Push the address on the stack
ret			;Return. This takes the address from the stuck and jumps
nop			;Nops are just to not break the following instructions when you disassemble with u
nop
nop
nop

We can compile the code with Online assembler and we should get a shell code. We can then put it in place with this line:

e	mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite+5d		0x48 0xB8 0x00 0x00 0x96 0xb8 0x5f 0x02 0x00 0x00 0x50 0xC3 0x90 0x90 0x90 0x90

Unfortunately, this patch is long. We need to break few lines and then restore them in the shellcode. So our shell code starts with the lines that we broke:

mov r8d, 0x30	;Preserved code
mov rdx,rsi	;Preserved code

Next, we need to preserve our working registers:

push rbx
push rdx

Okay, now we can do the logic. We want to modify the buffer length. However, we don’t want to do it for all of the packets. We need some source of randomness, like time, random values, or something else. Fortunately, the WAVEHDR structure has the field dwUser which may be “random enough” for our needs. Let’s take that value modulo some constant, and then change the packet length only for some cases.

First, let’s preserve the buffer length for the sake of what we do later:

mov rax, [rdx + 8]	;Load buffer length (that's the second field of the structure)
push rax		;Store buffer length on the stack

Now, let’s load dwUser and divide it by some constant like 23:

mov rax, [rdx + 16]	;Load dwUser which is the fourth field
mov rbx, 23		;Move the constant to the register
xor rdx, rdx		;Clear upper divisor part
div rbx			;Divide

Now, we can restore the buffer length to rax:

pop rax	;Restore buffer length

At this point we have rax with the buffer length, and rdx with the remainder. We can now compare the reminder and skip the code modifying the pucket length if needed:

cmp rdx, 20	;Compare with 20	
jbe 0x17	;Skip the branch

We can see that we avoid the buffer length modification if the remainder is at most 20. Effectively, we have 20/22 = 0.909% chance that we won’t modify the package. This means that we modify something like 9% of the packages, assuming the dwUser has a good distribution. The code is written in this way so you can tune the odds of changing the packet.

Now, let’s modify the package. We want to divide the buffer length by 2, however, we want to keep it generic to be able to experiment with other values:

mov rbx, 1	;Move 1 to rbx to multiply by 1/2
xor rdx, rdx	;Clear remainder
mul rbx		;Multiply
mov rbx, 2	;Store 2 to rbx to multiply by 1/2
xor rdx, rdx	;Clear remainder
div rbx		;Divide

You can play with other values, obviously. From my experiments, halving the value works the best.

Now it’s rather easy. rax has the new buffer length or the original one if we decided not to modify it. Let’s restore other registers:

pop rdx
pop rbx

Let’s update the buffer length:

mov [rdx + 8], rax

Now, we need to prepare the jump addresses. First, we want to put the original return address of the method mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite which is mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite+0x6d:

mov rax, 0x00007ffb897d3019
push rax

Now, we can jump to the WinAPI method:

push rbx
mov rbx, 0x00007ffbe6c6a860
mov rax, [rbx]
pop rbx
push rax
ret

That’s it. The final shellcode looks like this:

mov r8d, 0x30
mov rdx,rsi
push rbx
push rdx
mov rax, [rdx + 8]
push rax
mov rax, [rdx + 16]
mov rbx, 23
xor rdx, rdx
div rbx
pop rax
cmp rdx, 20
jbe 0x17
mov rbx, 1
xor rdx, rdx
mul rbx
mov rbx, 2
xor rdx, rdx
div rbx
pop rdx
pop rbx
mov [rdx + 8], rax
mov rax, 0x00007ffb897d3019
push rax
push rbx
mov rbx, 0x00007ffbe6c6a860
mov rax, [rbx]
pop rbx
push rax
ret

We can implant it with this:

e	25f`b8960000		0x41 0xB8 0x30 0x00 0x00 0x00 0x48 0x89 0xF2 0x53 0x52 0x48 0x8B 0x42 0x08 0x50 0x48 0x8B 0x42 0x10 0x48 0xC7 0xc3 0x17 0x00 0x00 0x00 0x48 0x31 0xD2 0x48 0xF7 0xF3 0x58 0x48 0x83 0xFA 0x14 0x76 0x1A 0x48 0xC7 0xC3 0x01 0x00 0x00 0x00 0x48 0x31 0xD2 0x48 0xF7 0xE3 0x48 0xC7 0xC3 0x02 0x00 0x00 0x00 0x48 0x31 0xD2 0x48 0xF7 0xF3 0x5A 0x5B 0x48 0x89 0x42 0x08 0x48 0xB8 0x19 0x30 0x7D 0x89 0xFB 0x7F 0x00 0x00 0x50 0x48 0xBB 0x60 0xA8 0xC6 0xE6 0xFB 0x7F 0x00 0x00 0x50 0xC3

Automated fix

We can now fix the code automatically. We need to do the following:

• Start mstsc.exe
• Find it’s process ID
• Attach the debugger and find all the addresses: free memory, mstsc.exe method, WinAPI method
• Construct the shellcode
• Attach the debugger and patch the code
• Detach the debugger

We can do all of that with PowerShell. Here is the code:

Function Run-Mstsc($rdpPath, $cdbPath, $numerator, $denominator){
	$id = get-random
	$code = @"
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Threading;
	
namespace MstscPatcher
{
	public class Env$id {
		public static void Start() {
			Process[] processes = Process.GetProcessesByName("mstsc");
			RunProcess("mstsc.exe", "$rdpPath");
			Thread.Sleep(3000);
			Process[] processes2 = Process.GetProcessesByName("mstsc");
			var idToPatch = processes2.Select(p => p.Id).OrderBy(i => i).Except(processes.Select(p => p.Id).OrderBy(i => i)).First();
			Patch(idToPatch);
		}
		
		public static void Patch(int id){
			Console.WriteLine(id);
			var addresses = RunCbd(id, @"
.sympath srv*C:\tmp*http://msdl.microsoft.com/download/symbols
.reload
!address
u mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite+100
.dvalloc 1024
qd
			");
			
			string freeMemoryAddress = addresses.Where(o => o.Contains("Allocated 2000 bytes starting at")).First().Split(' ').Last().Trim();
			Console.WriteLine("Free memory: " + freeMemoryAddress);
			
			var patchAddress = addresses.SkipWhile(o => !o.StartsWith("mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite:"))
				.SkipWhile(o => !o.Contains("r8d,30h"))
				.First().Split(' ').First().Trim();
			Console.WriteLine("Patch address: " + patchAddress);
			var returnAddress = (Convert.ToUInt64(patchAddress.Replace(((char)96).ToString(),""), 16) + 0x10).ToString("X").Replace("0x", "");
			Console.WriteLine("Return address: " + returnAddress);
			
			var winApiAddress = addresses.SkipWhile(o => !o.Contains("[mstscax!_imp_waveOutPrepareHeader"))
				.First().Split('(')[1].Split(')')[0].Trim();
			Console.WriteLine("WinAPI address: " + winApiAddress);
			
			Func<string, IEnumerable<string>> splitInPairs = address => address.Where((c, i) => i % 2 == 0).Zip(address.Where((c, i) => i % 2 == 1), (first, second) => first.ToString() + second.ToString());			
			Func<string, string> translateToBytes = address => string.Join(" ", splitInPairs(address.Replace(((char)96).ToString(), "").PadLeft(16, '0')).Reverse().Select(p => "0x" + p));
						
			var finalScript = @"
.sympath srv*C:\tmp*http://msdl.microsoft.com/download/symbols
.reload
e	" + patchAddress + @"	0x48 0xB8 " + translateToBytes(freeMemoryAddress) + @" 0x50 0xC3 0x90 0x90 0x90 0x90	
e	" + freeMemoryAddress + @"	0x41 0xB8 0x30 0x00 0x00 0x00 0x48 0x89 0xF2 0x53 0x52 0x48 0x8B 0x42 0x08 0x50 0x48 0x8B 0x42 0x10 0x48 0xC7 0xc3 $denominator 0x00 0x00 0x00 0x48 0x31 0xD2 0x48 0xF7 0xF3 0x58 0x48 0x83 0xFA $numerator 0x76 0x1A 0x48 0xC7 0xC3 0x01 0x00 0x00 0x00 0x48 0x31 0xD2 0x48 0xF7 0xE3 0x48 0xC7 0xC3 0x02 0x00 0x00 0x00 0x48 0x31 0xD2 0x48 0xF7 0xF3 0x5A 0x5B 0x48 0x89 0x42 0x08 0x48 0xB8 " + translateToBytes(returnAddress) + @" 0x50 0x53 0x48 0xBB " + translateToBytes(winApiAddress) + @" 0x48 0x8B 0x03 0x5B 0x50 0xC3	
qd
			";
			Console.WriteLine(finalScript);
			RunCbd(id, finalScript);
		}
		
		public static string[] RunCbd(int id, string script) {
			Console.WriteLine(script);
			File.WriteAllText("mstsc.txt", script);
			string output = "";
			Process process = RunProcess("$cdbPath", "-p " + id + " -cf mstsc.txt", text => output += text + "\n");
			process.WaitForExit();
			File.Delete("mstsc.txt");
			
			return output.Split('\n');
		}
		
		public static Process RunProcess(string fileName, string arguments, Action<string> outputReader = null){
			ProcessStartInfo startInfo = new ProcessStartInfo
			{
				FileName = fileName,
				Arguments = arguments,
				UseShellExecute = outputReader == null,
				RedirectStandardOutput = outputReader != null,
				RedirectStandardError = outputReader != null
			};
			
			if(outputReader != null){
				var process = new Process{
					StartInfo = startInfo
				};
				process.OutputDataReceived += (sender, args) => outputReader(args.Data);
				process.ErrorDataReceived += (sender, args) => outputReader(args.Data);

				process.Start();
				process.BeginOutputReadLine();
				process.BeginErrorReadLine();
				return process;
			}else {
				return Process.Start(startInfo);
			}
		}
	}
}
"@.Replace('$id', $id)
	$assemblies = ("System.Core","System.Xml.Linq","System.Data","System.Xml", "System.Data.DataSetExtensions", "Microsoft.CSharp")
	Add-Type -referencedAssemblies $assemblies -TypeDefinition $code -Language CSharp
	iex "[MstscPatcher.Env$id]::Start()"
}


Run-Mstsc "my_rdp_settings.rdp".Replace("\", "\\") "cdb.exe".Replace("\", "\\") "0x14" "0x17"

We compile some C# code on the fly. First, we find existing mstsc.exe instances (line 16), then run the new instance (line 17), wait a bit for the mstsc.exe to spawn a child process, and then find the id (lines 19-20). We can then patch the existing id.

First, we look for addresses. We do all the manual steps we did above to find the memory address, and two function addresses. The script is in lines 27-32. Notice that I load symbols as we need them and CDB may not have them configured on the box.

We can now parse the output. We first extract the allocated memory in lines 35-36.

Next, we look for the call site. We dump the whole method, and then find the first occurrence of mov 8d,30h. That’s our call site. This is in lines 38-41.

Next, we calculate the return address which is 16 bytes further. This is in lines 42-43.

Finally, I calculate the WinAPI method address. I extract the location of the pointer for the method (lines 45-47).

Next, we need to construct the shell code. This is exactly what we did above. We just need to format addresses properly (this is in helper methods in lines 49-50), and then build the script (lines 52-558). We can run it and that’s it. The last thing is customization of the values. You can see in line 108 that I made two parameters to change numerator and denominator for the odds of modifying the package. This way you can easily change how many packets are broken. The more you break, the faster you resynchronize, however, the worse the sound is.

That’s it. I verified that on Windows 10 22H2 x64, Windows 11 22H2 x64, Windows Server 2016 1607 x64, and Windows Server 2019 1809 x64, and it worked well. Your mileage may vary, however, the approach should work anywhere. Generally, to make this script work somewhere else, you just need to adjust how we find the call site, the return address, and the address of the WinAPI function. Assuming that the WinAPI is still called via the pointer stored in memory, then you won’t need to touch the machine code payload.

Below is the script for x86 bit (worked on Windows 10 10240 x86). Main differences are in how we access the data structure as the pointer is on the stack (and not in the register).

Function Run-Mstsc($rdpPath, $cdbPath, $numerator, $denominator){
	$id = get-random
	$code = @"
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Threading;
	
namespace MstscPatcher
{
	public class Env$id {
		public static void Start() {
			Process[] processes = Process.GetProcessesByName("mstsc");
			RunProcess("mstsc.exe", "$rdpPath");
			Thread.Sleep(3000);
			Process[] processes2 = Process.GetProcessesByName("mstsc");
			var idToPatch = processes2.Select(p => p.Id).OrderBy(i => i).Except(processes.Select(p => p.Id).OrderBy(i => i)).First();
			Patch(idToPatch);
		}
		
		public static void Patch(int id){
			Console.WriteLine(id);
			var addresses = RunCbd(id, @"
.sympath srv*C:\tmp*http://msdl.microsoft.com/download/symbols
.reload
!address
u mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite+100
.dvalloc 1024
qd
			");
			
			string freeMemoryAddress = addresses.Where(o => o.Contains("Allocated 2000 bytes starting at")).First().Split(' ').Last().Trim();
			Console.WriteLine("Free memory: " + freeMemoryAddress);
			
			var patchAddress = addresses.SkipWhile(o => !o.StartsWith("mstscax!CRdpWinAudioWaveoutPlayback::vcwaveOutWrite:"))
				.SkipWhile(o => !(o.Contains("dword ptr [ebx+3Ch]") && o.Contains("push")))
				.First().Split(' ').First().Trim();
			Console.WriteLine("Patch address: " + patchAddress);
			var returnAddress = (Convert.ToUInt64(patchAddress.Replace(((char)96).ToString(),""), 16) + 0x9).ToString("X").Replace("0x", "");
			Console.WriteLine("Return address: " + returnAddress);
			
			var winApiAddress = addresses.SkipWhile(o => !o.Contains("[mstscax!_imp__waveOutPrepareHeader"))
				.First().Split('(')[1].Split(')')[0].Trim();
			Console.WriteLine("WinAPI address: " + winApiAddress);
			
			Func<string, IEnumerable<string>> splitInPairs = address => address.Where((c, i) => i % 2 == 0).Zip(address.Where((c, i) => i % 2 == 1), (first, second) => first.ToString() + second.ToString());			
			Func<string, string> translateToBytes = address => string.Join(" ", splitInPairs(address.Replace(((char)96).ToString(), "").PadLeft(8, '0')).Reverse().Select(p => "0x" + p));
						
			var finalScript = @"
.sympath srv*C:\tmp*http://msdl.microsoft.com/download/symbols
.reload
e	" + patchAddress + @"	0xB8 " + translateToBytes(freeMemoryAddress) + @" 0x50 0xC3 0x90 0x90	
e	" + freeMemoryAddress + @"	0xFF 0x73 0x3C 0x53 0x52 0x8B 0x53 0x3C 0x52 0x8B 0x42 0x04 0x50 0x8B 0x42 0x0C 0xBB $denominator 0x00 0x00 0x00 0x31 0xD2 0xF7 0xF3 0x58 0x83 0xFA $numerator 0x76 0x12 0xBB 0x01 0x00 0x00 0x00 0x31 0xD2 0xF7 0xE3 0xBB 0x02 0x00 0x00 0x00 0x31 0xD2 0xF7 0xF3 0x5A 0x89 0x42 0x04 0x5A 0x5B 0xB8 " + translateToBytes(returnAddress) + @" 0x50 0x53 0xBB " + translateToBytes(winApiAddress) + @" 0x8B 0x03 0x5B 0x50 0xC3	
qd
			";
			Console.WriteLine(finalScript);
			RunCbd(id, finalScript);
		}
		
		public static string[] RunCbd(int id, string script) {
			Console.WriteLine(script);
			File.WriteAllText("mstsc.txt", script);
			string output = "";
			Process process = RunProcess("$cdbPath", "-p " + id + " -cf mstsc.txt", text => output += text + "\n");
			process.WaitForExit();
			File.Delete("mstsc.txt");
			
			return output.Split('\n');
		}
		
		public static Process RunProcess(string fileName, string arguments, Action<string> outputReader = null){
			ProcessStartInfo startInfo = new ProcessStartInfo
			{
				FileName = fileName,
				Arguments = arguments,
				UseShellExecute = outputReader == null,
				RedirectStandardOutput = outputReader != null,
				RedirectStandardError = outputReader != null
			};
			
			if(outputReader != null){
				var process = new Process{
					StartInfo = startInfo
				};
				process.OutputDataReceived += (sender, args) => outputReader(args.Data);
				process.ErrorDataReceived += (sender, args) => outputReader(args.Data);

				process.Start();
				process.BeginOutputReadLine();
				process.BeginErrorReadLine();
				return process;
			}else {
				return Process.Start(startInfo);
			}
		}
	}
}
"@.Replace('$id', $id)
	$assemblies = ("System.Core","System.Xml.Linq","System.Data","System.Xml", "System.Data.DataSetExtensions", "Microsoft.CSharp")
	Add-Type -referencedAssemblies $assemblies -TypeDefinition $code -Language CSharp
	iex "[MstscPatcher.Env$id]::Start()"
}

Run-Mstsc "my_rdp_settings.rdp".Replace("\", "\\") "cdb.exe".Replace("\", "\\") "0x14" "0x17"

Some keyword to make this easier to find on the Internet

Her some keywords to make this article easier to find on the Internet.

audio latency in mstsc.exe
audio latency in rdp
audio delay in mstsc.exe
audio delay in rdp
laggy sound in rdp
sound desynchronized in rdp
sound latency in rdp
slow audio
how to fix audio in rdp

Enjoy!

We use case classes in Scala and the Jackson library for XML serialization. We have a class that has a list of some nested class. When serializing it, we would like to name the nested element properly.

We start with these classes:

case class Person(val Name: String)
 
@JsonPropertyOrder(Array("People"))
case class Base
(
	val People: List[Person]
)

When we try to serialize it, we’ll get something like this:

< Base>
    < People>
        < People>
            < Name>Some name here</Name>
        </People>
    </People>
</Base>

You can see that we have Base -> People -> People instead of Base -> People -> Person. We can try to fix it with regular annotations:

case class Base
(
	@JacksonXmlElementWrapper(localName = "People")
	@JacksonXmlProperty(localName = "Person")
	val People: List[Person]
)

It now serializes correctly. However, when you try to deserialize it, you get the following exception:

Exception in thread "main" com.fasterxml.jackson.databind.JsonMappingException: Could not find creator property with name 'Person'

This fails because we use JacksonXmlProperty to rename the property and this gets handled incorrectly.

The issue is with how Scala implements case classes. Fields are always stored as private fields with getters (and setters if you use var), and the annotations are propagated to the constructor parameters.

My way of fixing it was the following:

• Do not propagate annotations to the constructor
• Create another constructor that has a different signature that the default one
• Mark the constructor as @JsonCreator

This way, Jackson creates the object with default values using the new constructor, and then sets the fields with reflection. So, this is how the code should look like:

case class Base
(
	@(JacksonXmlElementWrapper @field @getter)(localName = "People")
	@(JacksonXmlProperty @field @getter)(localName = "Person")
	val People: List[Person]
) {
   @JsonCreator
   def this(
	v1: List[Person]
	ignored: String
   ) = {
    this(v1)
   }
}

You could go with some different constructor if needed (like a parameterless one and pass nulls explicitly).

This works with Jackson 2.13.0.

This is the fourth part of the Bit Twiddling series. For your convenience you can find other parts in the table of contents in Par 1 — Modifying Android application on a binary level

Today we’re going to disable CTRL+ALT+HOME shortcut in mstsc. We want to disable the shortcut so it doesn’t “unfocus” the RDP session but still works inside the connection. I needed that for easier work in nested RDPs and I couldn’t find any decent RDP client for Windows that wouldn’t have this shortcut. The only one I found was Thincast but it lacked some other features as well.

Let’s begin.

Finding the entry point

The hardest part is as always finding “the place”. I took API Monitor which is like strace for Windows. I started the mstsc.exe, connected to some machine, pressed CTRL+ALT+HOME and observed what happened. After some digging here and there I found that when I press CTRL+ALT+HOME, the WM_USER+19 message is sent inside the application:

This is clearly a hint what’s going on. We can see that the key combination is captured by mstscax.dll which is the ActiveX part of the RDP. We also found the call stack and the address 0x000007ffec2d82fe2.

Analyzing the code

Now we can use WinDBG or whatever other debugger to figure out what’s going on. I attached to the running mstsc.exe, added a breakpoint with bu 0x00007ffec2d82fe2 and then pressed CTLR+ALT+HOME. As expected, the breakpoint was hit and I could observe the call stack:

0:003> kb
 # RetAddr               : Args to Child                                                           : Call Site
00 00007ffe`c2d27655     : 00000000`00000000 00000000`00000000 00000000`00000024 00000000`00008000 : mstscax!CTSCoreEventSource::InternalFireAsyncNotification+0xca
01 00007ffe`c2d262a5     : 00000000`00000100 00000000`00000000 00000000`00000024 00000135`bc82ea28 : mstscax!CTSInput::IHPostMessageToMainWindow+0x1c5
02 00007ffe`c2d261c8     : 00000000`00000001 00000000`01470001 00000000`003f0b28 00000000`00000113 : mstscax!CTSInput::IHInputCaptureWndProc+0x85
03 00007fff`5a04ef75     : 00000000`00000001 00000033`4faff2d0 00000000`003f0b28 00000000`80000022 : mstscax!CTSInput::IHStaticInputCaptureWndProc+0x58
04 00007fff`5a04e69d     : 00000000`00000000 00007ffe`c2d26170 00000033`4f5d3800 00007fff`3f646aae : USER32!UserCallWinProcCheckWow+0x515
05 00007fff`3f64ab32     : 00007ffe`c2d26170 00000000`00000000 00000000`ffffffff 00007fff`3f646a35 : USER32!DispatchMessageWorker+0x49d
06 00007fff`3f643997     : 00000000`00000000 00000000`00000000 00000135`bc830b00 00007fff`00000000 : apimonitor_drv_x64+0xab32
07 00000135`bc8fb89f     : 00000135`bc25da6a 00000000`00000001 00000000`00000001 00000000`00000001 : apimonitor_drv_x64+0x3997
08 00000135`bc25da6a     : 00000000`00000001 00000000`00000001 00000000`00000001 00000135`bd33e0e0 : 0x00000135`bc8fb89f
09 00000000`00000001     : 00000000`00000001 00000000`00000001 00000135`bd33e0e0 00007ffe`c2cd761c : 0x00000135`bc25da6a
0a 00000000`00000001     : 00000000`00000001 00000135`bd33e0e0 00007ffe`c2cd761c 00000033`4faff480 : 0x1
0b 00000000`00000001     : 00000135`bd33e0e0 00007ffe`c2cd761c 00000033`4faff480 00000135`bba40000 : 0x1
0c 00000135`bd33e0e0     : 00007ffe`c2cd761c 00000033`4faff480 00000135`bba40000 00000000`00000083 : 0x1
0d 00007ffe`c2cd761c     : 00000033`4faff480 00000135`bba40000 00000000`00000083 00000000`7ffef000 : 0x00000135`bd33e0e0
0e 00007ffe`c2cd7444     : 00000000`00000000 4e478f48`d4f63727 00000000`000051c0 0000aa52`0fad086d : mstscax!PAL_System_CondWait+0x1cc
0f 00007ffe`c2cf0f75     : 00000000`00000400 00000000`00000000 00000033`4faff8c0 00000135`bd35a720 : mstscax!CTSThreadInternal::ThreadSignalWait+0x34
10 00007ffe`c2cf1f8d     : 00000000`00000000 00000000`00000000 00000135`bd35a720 00000000`00000400 : mstscax!CTSThread::internalMsgPump+0x6d
11 00007ffe`c2d8693c     : 00000000`00000000 00007ffe`c2cee22d 00000135`bd344640 00007ffe`c2fdf3f0 : mstscax!CTSThread::internalThreadMsgLoop+0x14d
12 00007ffe`c3128550     : 00007ffe`c3475808 00000033`4faff8c0 00000000`00000000 00000135`ba29b8c0 : mstscax!CTSThread::ThreadMsgLoop+0x1c
13 00007ffe`c2fdeca8     : 00000135`bd35a720 00000135`ba29b8c0 00000135`bd35a720 00000135`ba29b748 : mstscax!CSND::SND_Main+0x148
14 00007ffe`c2fe73c2     : 00000135`bd35d100 00000135`bd35a720 00000033`4f67e3f0 00000000`00000000 : mstscax!CTSThread::TSStaticThreadEntry+0x258
15 00007fff`5a1f7344     : 00000000`00000000 00000000`00000000 00000000`00000000 00000000`00000000 : mstscax!PAL_System_Win32_ThreadProcWrapper+0x32
16 00007fff`5b7a26b1     : 00000000`00000000 00000000`00000000 00000000`00000000 00000000`00000000 : KERNEL32!BaseThreadInitThunk+0x14
17 00000000`00000000     : 00000000`00000000 00000000`00000000 00000000`00000000 00000000`00000000 : ntdll!RtlUserThreadStart+0x21

Perfect! We can see the method names and they are really useful. We can immediately see that some IHStaticInputCaptureWndProc method captures the regular message from the OS, then it calls the window procedure IHInputCaptureWndProc, and then the method posts the message to the main mstsc.exe window in IHPostMessageToMainWindow.

This shows us the way. We can also ask the WinDBG to get the call stack with addresses to find out that mstscax!CTSInput::IHInputCaptureWndProc+0x85 is mstscax+0x562a5. We can now dump the code:

0:004> u mstscax+0x562a5-0x85 mstscax+0x562a5
mstscax+0x56220:
00007ffe`c2d26220 4053            push    rbx
00007ffe`c2d26222 55              push    rbp
00007ffe`c2d26223 56              push    rsi
00007ffe`c2d26224 57              push    rdi
00007ffe`c2d26225 4154            push    r12
00007ffe`c2d26227 4155            push    r13
00007ffe`c2d26229 4156            push    r14
00007ffe`c2d2622b 4157            push    r15
00007ffe`c2d2622d 4881ece8000000  sub     rsp,0E8h
00007ffe`c2d26234 488b05cdc37500  mov     rax,qword ptr [mstscax!DllUnregisterServer+0x6f1308 (00007ffe`c3482608)]
00007ffe`c2d2623b 4833c4          xor     rax,rsp
00007ffe`c2d2623e 48898424d0000000 mov     qword ptr [rsp+0D0h],rax
00007ffe`c2d26246 33ed            xor     ebp,ebp
00007ffe`c2d26248 0f57c0          xorps   xmm0,xmm0
00007ffe`c2d2624b 448bf5          mov     r14d,ebp
00007ffe`c2d2624e 896c245c        mov     dword ptr [rsp+5Ch],ebp
00007ffe`c2d26252 f30f7f442470    movdqu  xmmword ptr [rsp+70h],xmm0
00007ffe`c2d26258 498bf1          mov     rsi,r9
00007ffe`c2d2625b 418bd8          mov     ebx,r8d
00007ffe`c2d2625e 4c8be2          mov     r12,rdx
00007ffe`c2d26261 488bf9          mov     rdi,rcx
00007ffe`c2d26264 488b059df57400  mov     rax,qword ptr [mstscax!DllUnregisterServer+0x6e4508 (00007ffe`c3475808)]
00007ffe`c2d2626b 4c8d2d96f57400  lea     r13,[mstscax!DllUnregisterServer+0x6e4508 (00007ffe`c3475808)]
00007ffe`c2d26272 4c8bbc2450010000 mov     r15,qword ptr [rsp+150h]
00007ffe`c2d2627a 493bc5          cmp     rax,r13
00007ffe`c2d2627d 740a            je      mstscax+0x56289 (00007ffe`c2d26289)
00007ffe`c2d2627f f6401c01        test    byte ptr [rax+1Ch],1
00007ffe`c2d26283 0f85c6010000    jne     mstscax+0x5644f (00007ffe`c2d2644f)
00007ffe`c2d26289 39af88030000    cmp     dword ptr [rdi+388h],ebp
00007ffe`c2d2628f 0f85f1020000    jne     mstscax+0x56586 (00007ffe`c2d26586)
00007ffe`c2d26295 4d8bcf          mov     r9,r15
00007ffe`c2d26298 4c8bc6          mov     r8,rsi
00007ffe`c2d2629b 8bd3            mov     edx,ebx
00007ffe`c2d2629d 488bcf          mov     rcx,rdi
00007ffe`c2d262a0 e8eb110000      call    mstscax+0x57490 (00007ffe`c2d27490)
00007ffe`c2d262a5 85c0            test    eax,eax

Great. We can see that the line 00007ffe`c2d262a0 calls some internal method and then tests if the output of the call is equal to 0 (this is the meaning of test eax,eax). We can now comment out this line and see what happens (mind the empty line):

a 00007ffe`c2d262a0
xor eax,eax
nop
nop
nop

g

We come back to mstsc.exe and we can see that CTRL+ALT+HOME doesn’t unfocus the window anymore! We can also check that the combination is handled properly inside the connection so it still unfocuses nested RDPs.

Automation

Automating this is pretty straightforward with cdb. We could modify the dll in place, but that would affect all the RDP connections we ever make. If we want to disable CTRL+ALT+HOME for some of them only, then this is what we can do:

First, create the file mstsc.txt with the following code:

a mstscax+0x562a0
xor eax, eax
nop
nop
nop

qd

Next, create batch file no_home.bat

cdb.exe -p %1 -cf mstsc.txt

Finally, run it like this:

no_home.bat PROCESS_ID_OF_MSTSC_YOU_WANT_TO_HACK

Changing shortcut to something else

How about we change shortcut instead of getting rid of it entirely? Let’s disassemble the method a bit more:

0:001> u mstscax+0x57655-0x1c5 mstscax+0x57655
mstscax!CTSInput::IHPostMessageToMainWindow:
00007ffe`c2d27490 48895c2408      mov     qword ptr [rsp+8],rbx
00007ffe`c2d27495 48896c2410      mov     qword ptr [rsp+10h],rbp
00007ffe`c2d2749a 4889742418      mov     qword ptr [rsp+18h],rsi
00007ffe`c2d2749f 57              push    rdi
00007ffe`c2d274a0 4156            push    r14
00007ffe`c2d274a2 4157            push    r15
00007ffe`c2d274a4 4883ec30        sub     rsp,30h
00007ffe`c2d274a8 33db            xor     ebx,ebx
00007ffe`c2d274aa 4d8bf1          mov     r14,r9
00007ffe`c2d274ad 498be8          mov     rbp,r8
00007ffe`c2d274b0 8bf2            mov     esi,edx
00007ffe`c2d274b2 488bf9          mov     rdi,rcx
00007ffe`c2d274b5 399958030000    cmp     dword ptr [rcx+358h],ebx
00007ffe`c2d274bb 0f8582000000    jne     mstscax!CTSInput::IHPostMessageToMainWindow+0xb3 (00007ffe`c2d27543)
00007ffe`c2d274c1 81fa00010000    cmp     edx,100h
00007ffe`c2d274c7 0f8489000000    je      mstscax!CTSInput::IHPostMessageToMainWindow+0xc6 (00007ffe`c2d27556)
00007ffe`c2d274cd b901000000      mov     ecx,1
00007ffe`c2d274d2 8d82fcfeffff    lea     eax,[rdx-104h]
00007ffe`c2d274d8 3bc1            cmp     eax,ecx
00007ffe`c2d274da 0f47cb          cmova   ecx,ebx
00007ffe`c2d274dd 399f24030000    cmp     dword ptr [rdi+324h],ebx
00007ffe`c2d274e3 0f84c3040000    je      mstscax!CTSInput::IHPostMessageToMainWindow+0x51c (00007ffe`c2d279ac)
00007ffe`c2d274e9 448bc3          mov     r8d,ebx
00007ffe`c2d274ec 81fe04010000    cmp     esi,104h
00007ffe`c2d274f2 0f84c7040000    je      mstscax!CTSInput::IHPostMessageToMainWindow+0x52f (00007ffe`c2d279bf)
00007ffe`c2d274f8 8bd3            mov     edx,ebx
00007ffe`c2d274fa 85c9            test    ecx,ecx
00007ffe`c2d274fc 0f85d1040000    jne     mstscax!CTSInput::IHPostMessageToMainWindow+0x543 (00007ffe`c2d279d3)
00007ffe`c2d27502 8bc3            mov     eax,ebx
00007ffe`c2d27504 85d2            test    edx,edx
00007ffe`c2d27506 0f8558010000    jne     mstscax!CTSInput::IHPostMessageToMainWindow+0x1d4 (00007ffe`c2d27664)
00007ffe`c2d2750c 85c0            test    eax,eax
00007ffe`c2d2750e 0f8550010000    jne     mstscax!CTSInput::IHPostMessageToMainWindow+0x1d4 (00007ffe`c2d27664)
00007ffe`c2d27514 8bc3            mov     eax,ebx
00007ffe`c2d27516 4585c0          test    r8d,r8d
00007ffe`c2d27519 0f85c8040000    jne     mstscax!CTSInput::IHPostMessageToMainWindow+0x557 (00007ffe`c2d279e7)
00007ffe`c2d2751f 85c0            test    eax,eax
00007ffe`c2d27521 0f85c0040000    jne     mstscax!CTSInput::IHPostMessageToMainWindow+0x557 (00007ffe`c2d279e7)
00007ffe`c2d27527 488b6c2458      mov     rbp,qword ptr [rsp+58h]
00007ffe`c2d2752c 8bc3            mov     eax,ebx
00007ffe`c2d2752e 488b5c2450      mov     rbx,qword ptr [rsp+50h]
00007ffe`c2d27533 488b742460      mov     rsi,qword ptr [rsp+60h]
00007ffe`c2d27538 4883c430        add     rsp,30h
00007ffe`c2d2753c 415f            pop     r15
00007ffe`c2d2753e 415e            pop     r14
00007ffe`c2d27540 5f              pop     rdi
00007ffe`c2d27541 c3              ret
00007ffe`c2d27542 cc              int     3
00007ffe`c2d27543 81fe13010000    cmp     esi,113h
00007ffe`c2d27549 0f851f010000    jne     mstscax!CTSInput::IHPostMessageToMainWindow+0x1de (00007ffe`c2d2766e)
00007ffe`c2d2754f bb01000000      mov     ebx,1
00007ffe`c2d27554 ebd1            jmp     mstscax!CTSInput::IHPostMessageToMainWindow+0x97 (00007ffe`c2d27527)
00007ffe`c2d27556 8b8128030000    mov     eax,dword ptr [rcx+328h]
00007ffe`c2d2755c be00800000      mov     esi,8000h
00007ffe`c2d27561 483be8          cmp     rbp,rax
00007ffe`c2d27564 0f8470010000    je      mstscax!CTSInput::IHPostMessageToMainWindow+0x24a (00007ffe`c2d276da)
00007ffe`c2d2756a 8b8744030000    mov     eax,dword ptr [rdi+344h]
00007ffe`c2d27570 483be8          cmp     rbp,rax
00007ffe`c2d27573 0f84dc010000    je      mstscax!CTSInput::IHPostMessageToMainWindow+0x2c5 (00007ffe`c2d27755)
00007ffe`c2d27579 8b8748030000    mov     eax,dword ptr [rdi+348h]
00007ffe`c2d2757f 483be8          cmp     rbp,rax
00007ffe`c2d27582 0f8440020000    je      mstscax!CTSInput::IHPostMessageToMainWindow+0x338 (00007ffe`c2d277c8)
00007ffe`c2d27588 8b874c030000    mov     eax,dword ptr [rdi+34Ch]
00007ffe`c2d2758e 483be8          cmp     rbp,rax
00007ffe`c2d27591 0f84a4020000    je      mstscax!CTSInput::IHPostMessageToMainWindow+0x3ab (00007ffe`c2d2783b)
00007ffe`c2d27597 8b8750030000    mov     eax,dword ptr [rdi+350h]
00007ffe`c2d2759d 483be8          cmp     rbp,rax
00007ffe`c2d275a0 0f8408030000    je      mstscax!CTSInput::IHPostMessageToMainWindow+0x41e (00007ffe`c2d278ae)
00007ffe`c2d275a6 4883fd24        cmp     rbp,24h
00007ffe`c2d275aa 0f8471030000    je      mstscax!CTSInput::IHPostMessageToMainWindow+0x491 (00007ffe`c2d27921)
00007ffe`c2d275b0 4883fd2d        cmp     rbp,2Dh
00007ffe`c2d275b4 0f856dffffff    jne     mstscax!CTSInput::IHPostMessageToMainWindow+0x97 (00007ffe`c2d27527)
00007ffe`c2d275ba 8d4de5          lea     ecx,[rbp-1Bh]
00007ffe`c2d275bd 48ff15acec5b00  call    qword ptr [mstscax!_imp_GetKeyState (00007ffe`c32e6270)]
00007ffe`c2d275c4 0f1f440000      nop     dword ptr [rax+rax]
00007ffe`c2d275c9 6685c6          test    si,ax
00007ffe`c2d275cc 0f8455ffffff    je      mstscax!CTSInput::IHPostMessageToMainWindow+0x97 (00007ffe`c2d27527)
00007ffe`c2d275d2 8d4de4          lea     ecx,[rbp-1Ch]
00007ffe`c2d275d5 48ff1594ec5b00  call    qword ptr [mstscax!_imp_GetKeyState (00007ffe`c32e6270)]
00007ffe`c2d275dc 0f1f440000      nop     dword ptr [rax+rax]
00007ffe`c2d275e1 6685c6          test    si,ax
00007ffe`c2d275e4 0f843dffffff    je      mstscax!CTSInput::IHPostMessageToMainWindow+0x97 (00007ffe`c2d27527)
00007ffe`c2d275ea e8c581fcff      call    mstscax!CClientUtilsWin32::UT_IsRunningInAppContainer (00007ffe`c2cef7b4)
00007ffe`c2d275ef 85c0            test    eax,eax
00007ffe`c2d275f1 0f8430ffffff    je      mstscax!CTSInput::IHPostMessageToMainWindow+0x97 (00007ffe`c2d27527)
00007ffe`c2d275f7 488b050ae27400  mov     rax,qword ptr [mstscax!WPP_GLOBAL_Control (00007ffe`c3475808)]
00007ffe`c2d275fe 4c8d3d03e27400  lea     r15,[mstscax!WPP_GLOBAL_Control (00007ffe`c3475808)]
00007ffe`c2d27605 493bc7          cmp     rax,r15
00007ffe`c2d27608 7430            je      mstscax!CTSInput::IHPostMessageToMainWindow+0x1aa (00007ffe`c2d2763a)
00007ffe`c2d2760a f6401c01        test    byte ptr [rax+1Ch],1
00007ffe`c2d2760e 742a            je      mstscax!CTSInput::IHPostMessageToMainWindow+0x1aa (00007ffe`c2d2763a)
00007ffe`c2d27610 80781904        cmp     byte ptr [rax+19h],4
00007ffe`c2d27614 7224            jb      mstscax!CTSInput::IHPostMessageToMainWindow+0x1aa (00007ffe`c2d2763a)
00007ffe`c2d27616 e82de60000      call    mstscax!RdpWppGetCurrentThreadActivityIdPrefix (00007ffe`c2d35c48)
00007ffe`c2d2761b 488b0de6e17400  mov     rcx,qword ptr [mstscax!WPP_GLOBAL_Control (00007ffe`c3475808)]
00007ffe`c2d27622 4c8d0557ca5c00  lea     r8,[mstscax!WPP_f5f71bb7bac236b27f26969128cc1e12_Traceguids (00007ffe`c32f4080)]
00007ffe`c2d27629 448bc8          mov     r9d,eax
00007ffe`c2d2762c bafd000000      mov     edx,0FDh
00007ffe`c2d27631 488b4910        mov     rcx,qword ptr [rcx+10h]
00007ffe`c2d27635 e85ecdfcff      call    mstscax!WPP_SF_D (00007ffe`c2cf4398)
00007ffe`c2d2763a 488b8f60050000  mov     rcx,qword ptr [rdi+560h]
00007ffe`c2d27641 4533c0          xor     r8d,r8d
00007ffe`c2d27644 488b01          mov     rax,qword ptr [rcx]
00007ffe`c2d27647 418d5010        lea     edx,[r8+10h]
00007ffe`c2d2764b 488b4048        mov     rax,qword ptr [rax+48h]
00007ffe`c2d2764f ff1523f75b00    call    qword ptr [mstscax!_guard_dispatch_icall_fptr (00007ffe`c32e6d78)]
00007ffe`c2d27655 c7871404000001000000 mov dword ptr [rdi+414h],1

The most interesting line is:

00007ffe`c2d275a6 4883fd24        cmp     rbp,24h

0x24 is the code key of HOME. We can replace it with something else, like insert which is 2D:

e mstscax+0x575A9 0x2D

And there you go. You can now press CTRL+ALT+HOME to unfocus nested RDP and CTRL+ALT+INSERT to unfocus the outer one. This gives you two levels of unfocusing.

This is the twentieth part of the Types and Programming Languages series. For your convenience you can find other parts in the table of contents in Part 1 — Do not return in finally

Sometimes you may ask yourself how hard you work. You could count the hours of work but we all know that some things are harder and some others are easier. One hour isn’t the same effort in different activities. Similarly, it’s easier to work when you’re not supervised and there is no time pressure. With deadlines ahead of you, the same amount of work now becomes harder and more stressful. Another factor is when you can do your work. Maybe you can work 24/7 and do it when you just feel like it, or maybe you need to stick to a strict schedule.

Being that said, there are many factors that affect “how hard” the work is. I was considering that recently and this is the formula I think works in my case. Let’s call this “Work Complexity Model”:

Let’s say that at your work you need to do coding, doc writing, and mentoring. Therefore, your set of activities would have these three elements. You then need to asses the cost of context switch which is your personal coefficient. It doesn’t matter per se and do not compare it with others. You can use it to compare your effort in different months when you move between projects or tasks.

Next, you need to decide on the period, for instance a single quarter.

Next, for each activity you need to measure how many increments you have. If you need to deliver your work at the end of the sprint, then you would have six increments (two increments each month). If you need to deliver something every day, then you would have ninety increments.

You then need to measure the size of the increment. Obviously, this is very subjective and it’s up to you to define how hard a particular piece of work is. Technically, this should be the amount of energy (physical and mental) you spent on the task. Since it’s hard to measure, you can just count the number of hours dedicated to the task and then multiply that by how intense and frustrating the work was.

Finally, you need to include the length of the timeframe to do the work. If you can work asynchronously 24/7, then your timeframe would be the whole period. If you can do your work during work days 9-5, then it’s just these working hours.

Let’s say that you can do coding 24/7, same for doc writing, but the mentoring you can do only on Mondays 9-5. You need to deliver your coding artifacts every other week, your doc writing twice a week, and your mentoring every Monday. Therefore, this would be your complexity over 3 months.

See that the formula has the following features:

• It shows that context switching has some cost that scales non-linearly with the number of activities
• Number of increments affects the result much more than the size of the increments. That’s because supervision tends to slow us much more
• The length of the timeframe is also included in the formula

It’s up to you what your values for C and S are. The goal of this formula is not to give you some absolute scale. It’s much more to compare your different projects to have some numbers showing you how hard it was, as we know that our memory misleads us often.

This is the twentieth fifth part of the Availability Anywhere series. For your convenience you can find other parts in the table of contents in Part 1 – Connecting to SSH tunnel automatically in Windows

Today we’re going to make our VR experience even better. This is continuation of the previous part.

As mentioned before, there are issues with ALT+TAB and WINDOWS key. I remapped CAPS LOCK to WINDOWS with PowerToys, but today we’re doing something better.

First, I was looking for a good full-size keyboard with touchpad that I could use with VR. The best thing I found is Perixx PERIBOARD-313. Touchpad is in some weird position but I got used to that. It has this irritating Fn key, lacks Right WINDOWS, and the space is quite short, but generally the keyboard is good enough.

However, it’s a wired keyboard. You can plug that into your VR headset and it works well. The keyboard has additional USB slots, so you can plug more devices to your VR this way. Still, we’d like to make it wireless. To do that, I’m using Bluetooth Adapter for Keyboard & Mouse (BT-500). This adapter has a couple of interesting features. First, it turns your wired keyboard or mouse into a wireless one. Second, it can remap keys on the fly, add macros, or have custom settings that you can switch between easily.

I’m using the adapter to remap Left WINDOWS to CAPS LOCK, and TAB to SCROLL LOCK. This is my setup:

map add l_com caps_lock
map add tab scroll_lock
save
reboot

Next, I remap CAPS LOCK to Left WINDOWS back using PowerToys. I do the same for SCROLL LOCK and TAB.

Finally, I use another adapter to turn any wired mouse into wireless one. You could go with Bluetooth mouse instead. With these things in place, I now have a “regular” wireless keyboard that I can use with VR. Even though it’s Android behind the scenes, all is just like a regular Windows laptop.

As a side note, I tried remapping keys to F13 and similar special keys. Unfortunately, Quest 3 doesn’t handle these properly and my remote machine I connect to over vSpatial doesn’t receive the keys.

This is the one hundred and sixth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Let’s solve Golden Waste (Złoty Odpad) riddle. We have a board with golden coins on it. One of the coins is a starting point and is numbered 1. We need to go along the blue lines and collect all the coins with the following rules:

• we must collect a coin when we get to it
• when collecting a coin, we can either continue straight or turn left or right; we can’t turn around (do U turn)

Let’s solve that with ILP. The idea is as follows:

• We want to number coins from one to n (number of coins); we represent this number with a bitset (to make things faster)
• each coin has two bitsets indicating which direction we entered this coin (up, right, bottom, left) and which direction we left
• for each coin, we analyze all four directions and make sure that all coins on the path in that direction have either lower number (so they were collected earlier) or we entered the first coin with higher number from the correct direction

Let’s see the code:

public class Field {
	public IVariable[] DirectionIn {get;set;}
	public IVariable[] DirectionOut {get;set;}
	public IVariable[] Number {get;set;}
}

var board = new string[]{
	" X     X",
	"    X X ",
	"   XX X1",
	"X      X",
	"  XXXX  ",
	"X  XX   ",
	"    XX  ",
	"XXXX X  "
};

var numbersCount = board.SelectMany(line => line.Select(character => character)).Count(character => character != ' ');

var fields = board.Select(line => line.Select(f => f != ' ' ? new Field{
	DirectionIn = Enumerable.Range(0, 4).Select(i => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray(),
	DirectionOut = Enumerable.Range(0, 4).Select(i => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray(),
	Number = Enumerable.Range(0, numbersCount).Select(i => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()
} : null).ToArray()).ToArray();

for(int row=0;row<board.Length;++row){
	for(int column=0;column<board[0].Length;++column){
		if(board[row][column] != ' '){
			var thisField = fields[row][column];
			
			// If this is one, then select it
			if(board[row][column] == '1'){
				thisField.Number[0].Set<Equal>(solver.FromConstant(1));
			}
			
			// Exactly one number
			solver.Set<Equal>(solver.FromConstant(1), solver.Operation<Addition>(thisField.Number));
			
			// Cannot turn around
			for(int direction=0;direction<4;++direction){
				thisField.DirectionIn[direction].Operation<Addition>(thisField.DirectionOut[direction]).Set<LessOrEqual>(solver.FromConstant(1));
			}
			
			// Exactly one direction in
			solver.Set<Equal>(solver.FromConstant(1), solver.Operation<Addition>(thisField.DirectionIn));
			
			// Exactly one direction out
			solver.Set<Equal>(solver.FromConstant(1), solver.Operation<Addition>(thisField.DirectionOut));
			
			// Either this is last fields
			// Or there is some other field with value + 1  and input direction matching output direction
			// 0 going up, 1 going right, 2 going down, 3 going left
			var isNotLastField = thisField.Number[numbersCount-1].Operation<BinaryNegation>();
			
			Func<Field, IVariable> numberHash = f => solver.Operation<Addition>(
				Enumerable.Range(0, numbersCount).Select(p => solver.Operation<Multiplication>(f.Number[p], solver.FromConstant(p))).ToArray()
			);
			
			Func<Field, int, int, int, IVariable, IVariable> matchField = (localThis, r, c, directionIn, shouldCarryOn) => {
				if(board[r][c] != ' '){
					var thatField = fields[r][c];
					
					var isLowerNumber = solver.Operation<IsLessOrEqual>(
						numberHash(thatField),
						numberHash(localThis)
					);
					
					var isNextNumber = solver.Operation<IsEqual>(
						solver.Operation<Addition>(solver.FromConstant(1), numberHash(localThis)),
						numberHash(thatField)
					);
					
					var isDirectionInMatching = thatField.DirectionIn[directionIn];
					
					solver.Set<Equal>(
						solver.FromConstant(1),
						solver.Operation<MaterialImplication>(
							solver.Operation<Conjunction>(shouldCarryOn),
							solver.Operation<Disjunction>(
								isLowerNumber,
								solver.Operation<Conjunction>(isNextNumber, isDirectionInMatching)
							)
						)
					);
					
					return solver.Operation<Conjunction>(shouldCarryOn, isLowerNumber);
				}
				
				return shouldCarryOn;
			};
			
			IVariable shouldContinue;
			
			// Going up
			shouldContinue = thisField.DirectionOut[0].Operation<Conjunction>(isNotLastField);
			for(int row2 = row-1;row2>=0;--row2){
				shouldContinue = shouldContinue.Operation<Conjunction>(matchField(thisField, row2, column, 2, shouldContinue));
			}
			shouldContinue.Set<Equal>(solver.FromConstant(0));
			
			// Going down
			shouldContinue = thisField.DirectionOut[2].Operation<Conjunction>(isNotLastField);
			for(int row2 = row+1;row2<board.Length;++row2){
				shouldContinue = shouldContinue.Operation<Conjunction>(matchField(thisField, row2, column, 0, shouldContinue));
			}
			shouldContinue.Set<Equal>(solver.FromConstant(0));
			
			// Going left
			shouldContinue = thisField.DirectionOut[3].Operation<Conjunction>(isNotLastField);
			for(int column2=column-1;column2>=0;--column2){
				shouldContinue = shouldContinue.Operation<Conjunction>(matchField(thisField, row, column2, 1, shouldContinue));
			}
			shouldContinue.Set<Equal>(solver.FromConstant(0));
			
			// Going right
			shouldContinue = thisField.DirectionOut[1].Operation<Conjunction>(isNotLastField);
			for(int column2=column+1;column2<board[0].Length;++column2){
				shouldContinue = shouldContinue.Operation<Conjunction>(matchField(thisField, row, column2, 3, shouldContinue));
			}
			shouldContinue.Set<Equal>(solver.FromConstant(0));
		}
	}
}

// All numbers are different
for(int number=0;number<numbersCount;++number){
	solver.Operation<Addition>(fields.SelectMany(f => f).Where(f => f != null).Select(f => f.Number[number]).ToArray()).Set<Equal>(solver.FromConstant(1));
}

solver.AddGoal("goal", solver.FromConstant(0));
solver.Solve();

for(int row=0;row<board.Length;++row){
	for(int column=0;column<board.Length;++column){
		if(board[row][column] != ' '){
			var thisField = fields[row][column];
			
			for(int number=0;number<numbersCount;++number){
				if(solver.GetValue(thisField.Number[number]) > 0){
					Console.Write((number < 9 ? " " : "") + (number + 1) + " ");
				}
			}
		}else{
			Console.Write("   ");
		}
	}
	Console.WriteLine();
}

First, we define our coin class (lines 1-5). Next, we define a starting board (lines 7-16). We also count the number of coins (18) and then initialize variables (20-24).

Next, we iterate over all fields (26) and look for coins (28). We hardcode the starting point (31-34). Next, we make sure that the bitset indicating the number has exactly one value (36-37), that we can’t exit the coin to go back (to the U-turn) (39-42), and that there is exactly one input direction and output direction (44-48).

Now, we encode the main part. We first store a variable indicating whether this is the last coin to collect (53). We define a helper variable that will decode number bitset into a single integer so we can compare them easily (55-57). Finally, we encode the main function that builds the path.

The idea is: we start from some coin localThis and we check other fields along some straight line. When we spot another coin, we calculate if it has lower number (and was collected earlier) (63), or is exactly next to be collected (68-71), and that we entered from the right direction (73). We then enforce this with material implication (75-84). Finally, we return the flag indicating whether we should continue looking along this path (lines 86, 89).

We then use this function in four directions: (94-99, 101-106, 108-113, 115-120). Finally, we just make sure that all coins have different numbers (125-128) and solve the problem. Output:

Tried aggregator 3 times.
MIP Presolve eliminated 1270 rows and 609 columns.
MIP Presolve modified 33469 coefficients.
Aggregator did 895 substitutions.
Reduced MIP has 1886 rows, 1454 columns, and 32267 nonzeros.
Reduced MIP has 1454 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.06 sec. (89.01 ticks)
Probing time = 0.00 sec. (4.29 ticks)
Tried aggregator 1 time.
Reduced MIP has 1886 rows, 1454 columns, and 32267 nonzeros.
Reduced MIP has 1454 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (11.67 ticks)
Probing time = 0.00 sec. (4.28 ticks)
Clique table members: 2759.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 12 threads.
Root relaxation solution time = 0.05 sec. (52.10 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0        0.0000   508                      0.0000      874
      0     0        0.0000   481                   Cuts: 238     1192
      0     0        0.0000   580                   Cuts: 410     2048
      0     0        0.0000   532                   Cuts: 192     2580
      0     0        0.0000   660                   Cuts: 498     3396
      0     2        0.0000   263                      0.0000     3400
Elapsed time = 2.36 sec. (2430.37 ticks, tree = 0.01 MB, solutions = 0)
     25    27        0.0000   372                      0.0000     9792
    182   146        0.0000   480                      0.0000    34215
    360   218        0.0000   359                      0.0000    59248
    473   275        0.0000   382                      0.0000    86080
    630   392        0.0000   392                      0.0000   102841
    961   441    infeasible                            0.0000   127669
   1029   455    infeasible                            0.0000   146053
   1149   479        0.0000   408                      0.0000   163289
   1216   540        0.0000   440                      0.0000   176188
   1551   579    infeasible                            0.0000   232730
Elapsed time = 5.97 sec. (5824.01 ticks, tree = 0.56 MB, solutions = 0)
   1690   585    infeasible                            0.0000   289363
   1805   601        0.0000   515                      0.0000   325263
   1983   602        0.0000   477                      0.0000   373383
   2124   600        0.0000   455                      0.0000   431960
   2316   589    infeasible                            0.0000   490860
   2546   600        0.0000   570                      0.0000   544653
   2586   598        0.0000   562                      0.0000   584681
   2750   632    infeasible                            0.0000   643752
   2914   652    infeasible                            0.0000   681857
   3119   652        0.0000   679                      0.0000   725066
Elapsed time = 22.92 sec. (18464.39 ticks, tree = 1.39 MB, solutions = 0)
   3251   658        0.0000   695                      0.0000   811097
   3287   656    infeasible                            0.0000   849022
   3404   681        0.0000   528                      0.0000   907778
   3484   695    infeasible                            0.0000   930758
   3586   721        0.0000   648                      0.0000   954548
   3874   774        0.0000   588                      0.0000  1014376
   4009   807        0.0000   444                      0.0000  1049944
   4065   821        0.0000   502                      0.0000  1069917
   4327   865        0.0000   407                      0.0000  1144971
   4367   877        0.0000   521                      0.0000  1160531
Elapsed time = 39.03 sec. (29642.77 ticks, tree = 1.74 MB, solutions = 0)
   4472   910        0.0000   417                      0.0000  1190811
   4763   909    infeasible                            0.0000  1275674
   4797   921        0.0000   475                      0.0000  1295329
   4821   935        0.0000   481                      0.0000  1312840
   4857   949        0.0000   508                      0.0000  1332501
   4918   960        0.0000   520                      0.0000  1392387
   5005   997        0.0000   455                      0.0000  1432805
   5072  1020        0.0000   594                      0.0000  1448193
   5160  1040        0.0000   321                      0.0000  1479499
   5246  1048        0.0000   398                      0.0000  1504146
Elapsed time = 54.63 sec. (42147.18 ticks, tree = 2.13 MB, solutions = 0)
   5426  1124        0.0000   423                      0.0000  1544836
   5711  1181    infeasible                            0.0000  1604289
   5787  1158    infeasible                            0.0000  1631589
   5850  1169        0.0000   595                      0.0000  1655718
   5966  1183        0.0000   596                      0.0000  1695224
   6145  1204        0.0000   611                      0.0000  1770821
   6253  1242        0.0000   595                      0.0000  1814478
   6279  1244    infeasible                            0.0000  1843727
   6318  1247    infeasible                            0.0000  1878957
   6342  1249    infeasible                            0.0000  1894346
Elapsed time = 70.39 sec. (54490.95 ticks, tree = 3.57 MB, solutions = 0)
   6453  1240        0.0000   653                      0.0000  1946631
   6764  1281        0.0000   556                      0.0000  2047656
   6804  1283    infeasible                            0.0000  2063706
   6864  1299    infeasible                            0.0000  2080575
   7032  1340        0.0000   404                      0.0000  2123133
   7164  1346        0.0000   386                      0.0000  2158194
   7320  1336        0.0000   389                      0.0000  2205352
   7598  1302        0.0000   492                      0.0000  2275263
   7824  1294        0.0000   386                     -0.0000  2350430
   7831  1300        0.0000   442                     -0.0000  2352517
Elapsed time = 93.77 sec. (77852.80 ticks, tree = 58.94 MB, solutions = 0)
   7850  1311        0.0000   404                     -0.0000  2355298
   7923   969        0.0000   442                     -0.0000  2366582
   8187   689        0.0000   402                     -0.0000  2400804
   8559   412        0.0000   318                     -0.0000  2435661
   8948   389    infeasible                           -0.0000  2470993
   9576   476        0.0000   330                     -0.0000  2520604
  10159   477        0.0000   334                     -0.0000  2579870
  10555   518        0.0000   303                     -0.0000  2618541
  10930   518        0.0000   303                     -0.0000  2664466
  11282   519        0.0000   418                     -0.0000  2711235
Elapsed time = 103.23 sec. (87766.62 ticks, tree = 1.00 MB, solutions = 0)
  11651   566        0.0000   366                     -0.0000  2758926
  11693   565        0.0000   380                     -0.0000  2764222
  12058   290        0.0000   402                     -0.0000  2801170
  12633   230    infeasible                           -0.0000  2865597
  13570   230        0.0000   239                     -0.0000  2948118
  14733   263    infeasible                           -0.0000  3061474
  15820   202        0.0000   287                     -0.0000  3169807
  17003   275        0.0000   300                     -0.0000  3281567
  17989   304        0.0000   216                     -0.0000  3379704
  19041   267        0.0000   359                     -0.0000  3481728
Elapsed time = 116.88 sec. (103305.54 ticks, tree = 0.03 MB, solutions = 0)
  20430   274    infeasible                           -0.0000  3627297
  21450   423        0.0000   302                     -0.0000  3711606
  23285   375        0.0000   276                     -0.0000  3861744
  24549   281    infeasible                           -0.0000  3979235
  26136   435        0.0000   218                     -0.0000  4127636
  27561   391        0.0000   288                     -0.0000  4249779
  29100   424        0.0000   240                     -0.0000  4376829
  30874   439        0.0000   277                     -0.0000  4524167
  32176   415        0.0000   317                     -0.0000  4638570
  33981   443        0.0000   303                     -0.0000  4798347
Elapsed time = 128.17 sec. (112887.60 ticks, tree = 0.05 MB, solutions = 0)
  35594   351        0.0000   374                     -0.0000  4933169
  36777   478        0.0000   341                     -0.0000  5045144
  38466   458        0.0000   241                     -0.0000  5209098
  39471   471        0.0000   314                     -0.0000  5311307
  41132   528        0.0000   166                     -0.0000  5465492
  42639   520    infeasible                           -0.0000  5596801
  44371   393    infeasible                           -0.0000  5747683
  45828   546        0.0000   318                     -0.0000  5889722
  47025   530        0.0000   263                     -0.0000  6007087
  52571   586    infeasible                           -0.0000  6553399
Elapsed time = 142.38 sec. (125333.77 ticks, tree = 0.08 MB, solutions = 0)
  58950   670        0.0000   353                     -0.0000  7130024
  64631   643        0.0000   281                     -0.0000  7646642
  69621   603    infeasible                           -0.0000  8169867
  74350   602        0.0000   264                     -0.0000  8669095
  80366   715        0.0000   176                     -0.0000  9230184
  85904   475        0.0000   319                     -0.0000  9771470
  91692   502        0.0000   316                     -0.0000 10317244
  97439   608        0.0000   262                     -0.0000 10808574
 103409   594        0.0000   155                     -0.0000 11361920
 109112   645    infeasible                           -0.0000 11891245
Elapsed time = 186.53 sec. (163579.26 ticks, tree = 0.06 MB, solutions = 0)
 114282   994    infeasible                           -0.0000 12422478
 119356   803    infeasible                           -0.0000 12941160
 125898   915        0.0000   273                     -0.0000 13509013
 132155   881        0.0000   262                     -0.0000 14064545
 137866   886    infeasible                           -0.0000 14590510
 143707   914        0.0000   288                     -0.0000 15177172
 149235   807        0.0000   285                     -0.0000 15701530
 154911   675        0.0000   178                     -0.0000 16241618
 161882   821        0.0000   201                     -0.0000 16817652
 169771   823        0.0000   294                     -0.0000 17381212
Elapsed time = 245.55 sec. (201783.67 ticks, tree = 0.09 MB, solutions = 0)
 177104   765        0.0000   153                     -0.0000 17960080
 184942   821        0.0000   317                     -0.0000 18569902
 192554   749        0.0000   260                     -0.0000 19131939
 198295   787        0.0000   244                     -0.0000 19644341
 204161   727        0.0000   203                     -0.0000 20187350
 210163   575        0.0000   188                     -0.0000 20746953
 217540   898        0.0000   223                     -0.0000 21304646
 224070   780    infeasible                           -0.0000 21843454
 230533   820        0.0000   263                     -0.0000 22406991
 236733   779        0.0000   272                     -0.0000 22960102
Elapsed time = 300.91 sec. (240013.77 ticks, tree = 0.07 MB, solutions = 0)
 242658   745    infeasible                           -0.0000 23514500
 247652   787        0.0000   344                     -0.0000 24030942
 252764   942    infeasible                           -0.0000 24564913
 258233   961        0.0000   325                     -0.0000 25099913
 263573   874        0.0000   322                     -0.0000 25638923
 268963   864        0.0000   284                     -0.0000 26164593
 273168   887        0.0000   278                     -0.0000 26658456
 277901   886        0.0000   210                     -0.0000 27176495
 283861   956        0.0000   313                     -0.0000 27737094
 289071  1070    infeasible                           -0.0000 28251655
Elapsed time = 344.66 sec. (278234.91 ticks, tree = 0.14 MB, solutions = 0)
 293946  1036        0.0000   295                     -0.0000 28774451
 298674  1027        0.0000   270                     -0.0000 29314425
 304035   901        0.0000   291                     -0.0000 29855358
 308755  1004        0.0000   260                     -0.0000 30377899
 313952  1082        0.0000   182                     -0.0000 30884392
 319647  1011    infeasible                           -0.0000 31447232
 325025   962        0.0000   368                     -0.0000 31993586
 331144  1152    infeasible                           -0.0000 32537413
 336554  1085        0.0000   293                     -0.0000 33082843
 342745  1060        0.0000   310                     -0.0000 33644741
Elapsed time = 399.03 sec. (316477.28 ticks, tree = 0.09 MB, solutions = 0)
 348043  1070        0.0000   325                     -0.0000 34195498
 353051  1083    infeasible                           -0.0000 34733741
 357706  1092        0.0000   204                     -0.0000 35234117
 362868  1098        0.0000   396                     -0.0000 35793118
 367279  1060        0.0000   250                     -0.0000 36308791
 372233  1152        0.0000   240                     -0.0000 36828052
 377434  1040        0.0000   218                     -0.0000 37350915
 382616  1201        0.0000   283                     -0.0000 37889699
 387312  1104        0.0000   321                     -0.0000 38398280
 392225  1292        0.0000   250                     -0.0000 38920991
Elapsed time = 447.94 sec. (354693.45 ticks, tree = 0.12 MB, solutions = 0)
 397318  1139        0.0000   375                     -0.0000 39441204
 402948  1109        0.0000   301                     -0.0000 39988911
 408043  1211        0.0000   325                     -0.0000 40527949
 413033  1266    infeasible                           -0.0000 41021940
 418087  1259        0.0000   336                     -0.0000 41533403
 422935  1164        0.0000   238                     -0.0000 42063377
 427481  1148        0.0000   288                     -0.0000 42573987
 432508  1157        0.0000   310                     -0.0000 43081190
 437531  1104        0.0000   393                     -0.0000 43621012
 442498  1095    infeasible                           -0.0000 44152646
Elapsed time = 493.66 sec. (392931.47 ticks, tree = 0.11 MB, solutions = 0)
 447235  1243        0.0000   367                     -0.0000 44673781
 454167  1167        0.0000   364                     -0.0000 45252390
 459563  1358        0.0000   258                     -0.0000 45779187
 465352  1280        0.0000   276                     -0.0000 46357473
 470467  1164    infeasible                           -0.0000 46875991
 475439  1234        0.0000   351                     -0.0000 47413722
 480265  1176        0.0000   341                     -0.0000 47920454
 485190  1296        0.0000   308                     -0.0000 48445537
 489439  1203        0.0000   275                     -0.0000 48969330
 494417  1212    infeasible                           -0.0000 49473099
Elapsed time = 543.44 sec. (431141.50 ticks, tree = 0.11 MB, solutions = 0)
 499878  1134        0.0000   212                     -0.0000 50001890
 505210  1150        0.0000   348                     -0.0000 50541821
 510703  1177        0.0000   288                     -0.0000 51085904
 516296  1191        0.0000   315                     -0.0000 51627983
 522136  1340        0.0000   275                     -0.0000 52196564
 527818  1254    infeasible                           -0.0000 52747921
 533847  1184    infeasible                           -0.0000 53277168
 539496  1225        0.0000   267                     -0.0000 53838500
 545609  1258        0.0000   324                     -0.0000 54438657
 550950  1279        0.0000   239                     -0.0000 54978252
Elapsed time = 608.14 sec. (469350.48 ticks, tree = 0.11 MB, solutions = 0)
 556262  1247        0.0000   248                     -0.0000 55503690
 562223  1376        0.0000   353                     -0.0000 56086832
 567933  1384        0.0000   303                     -0.0000 56644010
 573375  1411        0.0000   201                     -0.0000 57189815
 578931  1373    infeasible                           -0.0000 57706883
 584688  1302        0.0000   337                     -0.0000 58273497
 590210  1307    infeasible                           -0.0000 58818386
 596342  1262        0.0000   400                     -0.0000 59389073
 601521  1501        0.0000   261                     -0.0000 59915960
 607666  1618        0.0000   316                     -0.0000 60463241
Elapsed time = 655.89 sec. (507553.95 ticks, tree = 0.14 MB, solutions = 0)
 613534  1464    infeasible                           -0.0000 61020365
 619827  1346    infeasible                           -0.0000 61571663
 625674  1185        0.0000   337                     -0.0000 62134994
 630902  1230    infeasible                           -0.0000 62649879
 636152  1269        0.0000   267                     -0.0000 63170593
 641404  1232    infeasible                           -0.0000 63717245
 647098  1131        0.0000   277                     -0.0000 64283791
 651991  1146        0.0000   280                     -0.0000 64792110
 657625  1102        0.0000   336                     -0.0000 65339290
 662514  1143        0.0000   288                     -0.0000 65886969
Elapsed time = 701.64 sec. (545809.44 ticks, tree = 0.10 MB, solutions = 0)
 667761   982    infeasible                           -0.0000 66435420
 672993   997    infeasible                           -0.0000 66975538
 678105   878        0.0000   333                     -0.0000 67497233
 684034   904        0.0000   243                     -0.0000 68064925
 688856  1029    infeasible                           -0.0000 68561991
 694528   996        0.0000   357                     -0.0000 69108002
 699668   949        0.0000   315                     -0.0000 69630518
 704198   991    infeasible                           -0.0000 70161775
 708775  1017        0.0000   359                     -0.0000 70646954
 713778  1124        0.0000   319                     -0.0000 71197164
Elapsed time = 753.45 sec. (584025.21 ticks, tree = 0.10 MB, solutions = 0)
 718098  1053    infeasible                           -0.0000 71697499
 722978  1157        0.0000   354                     -0.0000 72209736
 727746  1094    infeasible                           -0.0000 72707109
 732735  1208        0.0000   321                     -0.0000 73253307
 737382  1158        0.0000   262                     -0.0000 73777309
 741743  1186        0.0000   314                     -0.0000 74282073
 746089  1111        0.0000   231                     -0.0000 74770022
 750690  1071        0.0000   333                     -0.0000 75294136
 756570  1056        0.0000   183                     -0.0000 75849757
 761838   990    infeasible                           -0.0000 76384511
Elapsed time = 806.95 sec. (622255.57 ticks, tree = 0.09 MB, solutions = 0)
 766503  1047        0.0000   199                     -0.0000 76884595
 772155   973        0.0000   357                     -0.0000 77445968
 777804   905        0.0000   307                     -0.0000 78018695
 782798  1022        0.0000   255                     -0.0000 78543623
 787886   915        0.0000   354                     -0.0000 79080195
 792781   837        0.0000   207                     -0.0000 79607676
 798278   812        0.0000   288                     -0.0000 80149715
 804008   877        0.0000   352                     -0.0000 80674521
 810292   950        0.0000   221                     -0.0000 81234497
 816081  1096        0.0000   248                     -0.0000 81761078
Elapsed time = 864.78 sec. (660493.24 ticks, tree = 0.09 MB, solutions = 0)
 821608   981        0.0000   339                     -0.0000 82343536
 826874   806        0.0000   328                     -0.0000 82820634
 832016   757        0.0000   328                     -0.0000 83327447
 837482   787        0.0000   308                     -0.0000 83869680
 842139   731        0.0000   323                     -0.0000 84381411
 847060   783    infeasible                           -0.0000 84938335
 851915   664        0.0000   290                     -0.0000 85467634
 857317   674        0.0000   237                     -0.0000 85996304
 862563   625    infeasible                           -0.0000 86529643
 868267   601        0.0000   337                     -0.0000 87056256
Elapsed time = 919.34 sec. (698703.51 ticks, tree = 0.06 MB, solutions = 0)
 874538   564        0.0000   289                     -0.0000 87647117
 880183   486    infeasible                           -0.0000 88177720
 885096   474        0.0000   393                     -0.0000 88714039
 890118   478        0.0000   278                     -0.0000 89215217
 894929   452    infeasible                           -0.0000 89745753
 899775   557        0.0000   289                     -0.0000 90248578
 905044   588        0.0000   284                     -0.0000 90809349
 909687   539        0.0000   291                     -0.0000 91299572
 914621   535        0.0000   372                     -0.0000 91835448
 919578   534        0.0000   259                     -0.0000 92373542
Elapsed time = 979.02 sec. (736908.26 ticks, tree = 0.05 MB, solutions = 0)
 924284   528    infeasible                           -0.0000 92897665
 928973   614        0.0000   284                     -0.0000 93422898
 933775   525        0.0000   303                     -0.0000 93952475
 938738   533        0.0000   248                     -0.0000 94478367
 943372   431        0.0000   174                     -0.0000 94995204
 948523   447        0.0000   334                     -0.0000 95503630
 953489   585        0.0000   402                     -0.0000 96027542
 958414   528        0.0000   374                     -0.0000 96555477
 962500   423        0.0000   353                     -0.0000 97053906
 967184   482        0.0000   268                     -0.0000 97556109
Elapsed time = 1033.42 sec. (775159.19 ticks, tree = 0.05 MB, solutions = 0)
 971887   500        0.0000   316                     -0.0000 98087834
 975986   487        0.0000   300                     -0.0000 98569907
 980549   469    infeasible                           -0.0000 99091590
 985736   427    infeasible                           -0.0000 99606175
 990496   452    infeasible                           -0.0000 1.00e+008
 996024   427        0.0000   367                     -0.0000 1.01e+008
 1001487   326        0.0000   399                     -0.0000 1.01e+008
 1006410   393        0.0000   338                     -0.0000 1.02e+008
 1010756   381        0.0000   340                     -0.0000 1.02e+008
 1015858   393        0.0000   400                     -0.0000 1.03e+008
Elapsed time = 1085.41 sec. (813376.28 ticks, tree = 0.05 MB, solutions = 0)
 1021091   437        0.0000   279                     -0.0000 1.03e+008
 1027315   368        0.0000   253                     -0.0000 1.04e+008
 1032859   283        0.0000   261                     -0.0000 1.04e+008
 1037989   506        0.0000   315                     -0.0000 1.05e+008
 1043080   291        0.0000   329                     -0.0000 1.05e+008
 1048499   481        0.0000   238                     -0.0000 1.06e+008
 1054622   474    infeasible                           -0.0000 1.06e+008
 1059697   488    infeasible                           -0.0000 1.07e+008
 1065295   516        0.0000   215                     -0.0000 1.07e+008
 1070060   537        0.0000   293                     -0.0000 1.08e+008
Elapsed time = 1150.30 sec. (851586.95 ticks, tree = 0.16 MB, solutions = 0)
 1075283   516        0.0000   255                     -0.0000 1.08e+008
 1080812   392        0.0000   336                     -0.0000 1.09e+008
 1085879   298        0.0000   336                     -0.0000 1.10e+008
 1091175   558    infeasible                           -0.0000 1.10e+008
 1096144   557    infeasible                           -0.0000 1.11e+008
 1100783   505        0.0000   271                     -0.0000 1.11e+008
 1106516   471        0.0000   305                     -0.0000 1.12e+008
 1111268   484        0.0000   365                     -0.0000 1.12e+008
 1116540   569        0.0000   303                     -0.0000 1.13e+008
 1121296   601        0.0000   299                     -0.0000 1.13e+008
Elapsed time = 1210.66 sec. (889845.90 ticks, tree = 0.06 MB, solutions = 0)
 1125401   527    infeasible                           -0.0000 1.14e+008
 1129996   481        0.0000   330                     -0.0000 1.14e+008
 1133934   408        0.0000   305                     -0.0000 1.15e+008
 1138889   437    infeasible                           -0.0000 1.15e+008
 1143893   449        0.0000   220                     -0.0000 1.16e+008
 1149074   467        0.0000   364                     -0.0000 1.16e+008
 1153624   329        0.0000   352                     -0.0000 1.17e+008
 1158969   491    infeasible                           -0.0000 1.17e+008
 1163791   431    infeasible                           -0.0000 1.18e+008
 1167484   332        0.0000   318                     -0.0000 1.18e+008
Elapsed time = 1264.00 sec. (928040.04 ticks, tree = 0.26 MB, solutions = 0)
 1171268   317    infeasible                           -0.0000 1.19e+008
 1175984   329        0.0000   287                     -0.0000 1.19e+008
 1180925   323        0.0000   293                     -0.0000 1.20e+008
 1185958   242        0.0000   415                     -0.0000 1.20e+008
 1191580   223    infeasible                           -0.0000 1.21e+008
*1194993   186      integral     0        0.0000       -0.0000 1.21e+008    0.00%

Root node processing (before b&c):
  Real time             =    2.33 sec. (2407.88 ticks)
Parallel b&c, 12 threads:
  Real time             = 1294.31 sec. (947046.19 ticks)
  Sync time (average)   =  178.58 sec.
  Wait time (average)   =    0.08 sec.
                          ------------
Total (root+branch&cut) = 1296.64 sec. (949454.07 ticks)
   17                18
             4     3
          6  5     2  1
20                   19
      14  7 13 12
21        8  9
            10 11
22 16 15 23    24

This is the nineteenth part of the Types and Programming Languages series. For your convenience you can find other parts in the table of contents in Part 1 — Do not return in finally

Who is a senior software engineer? How do we become one? Does it matter at all? Let’s see some dimensions we can discuss when “assessing” someone’s skills.

Maturity

What does it mean to be mature? Many people think it’s important to point bad sides of solutions. No matter if we’re talking about the software engineering, social insurance, taxes, or whatever other thing that people like to discuss. However, that’s not the point. While it may seem that good engineers (professionals in general) can find drawbacks of solutions and identify where they fail, that’s not what we need. Let’s see some levels how people progress and what’s important.

First level – just complaining

This is easy and we do that so often. “Taxes are too high and they should be lower”. “This code is just broken and we should fix it”. Both of these statements may be 100% correct and yet they are completely non-actionable. It’s easy to “just complain” but it’s hard to explain why things are wrong and how to make them right.

When it comes to software engineering, we can give these statements literally about anything. We very often do that when criticizing some programming language, technology, library, framework, programming paradigm, particular solution, or anything else. This is just a trash talk that brings nothing.

Second level – being good at complaining

This is much harder. When someone achieves this level, they can easily point drawbacks of some particular solution and explain what they mean. What’s more, they are very often correct and make really good calls. They can for instance explain why a particular GC implementation won’t work here, why such and such library is not good enough, why some code is unreadable, or why some solution is slow. They can easily find edge cases where the solution will fail or explain why designs won’t work.

However, this is still not what we need. We need to understand that reality is never perfect. We can’t make our code (taxes, social insurance, health agency, whatever else) perfect. We can’t avoid all the problems. It’s not enough to just show where things won’t work and that they have drawbacks because everything have drawbacks. Interestingly enough, many software architects are on this level because they can always tell you “what not to do” but they can never give a good solution. Similarly, politicians are great at criticizing others but very rarely give solutions.

Another example is when software engineers can provide many options but can never decide which one to choose because all of them have some issues. Later, they typically push the decision on someone else (client, product owner, software architect) and then can complain that a wrong decision has been made.

Third level – giving solutions

Finally, people realize that the world is not perfect, and yet we need to deal with it somehow. They can give ideas (and even criticize them) and they can make decisions what to do. Even though they understand things will not be perfect, they can take the risk or even consciously pick something that they know will not work perfectly.

It’s important to understand that once one makes a choice, they will always be criticized. Always. That’s because one cannot pick a perfect solution because it doesn’t exist. Therefore, if you want to become mature enough and achieve this level, you need to accept that you will be always criticized. No matter if you’re a software engineer, software architect, or a politician. You’ll always get criticized, no matter what you do.

Seniority

Now, we can discuss what it means to be a “senior”. It’s important to understand that it’s not about skills per se. It’s about the proper attitude, skills, and experience.

There are three basic levels we can consider here.

Junior

Juniors (entry level people) cannot work independently. They aren’t experienced or skilled enough to deliver results on their own. No matter if we’re talking about software engineers, architects, politicians, or product owners. Juniors can’t work on their own and need some guidance to make progress.

Some claim that “X is not an entry-level position” where X can be whatever (scrum master, product owner, project manager, you pick one). I believe in general this is not true. No matter what our role is, we’ll need some guidance initially.

Mid

Mids (regulars) can work independently but they don’t have this something that distinguishes them from other regulars. They “just do the job”. They aren’t role models yet but they can work on their own. We can rely on them, we don’t need to supervise them, and we can expect they have good enough skills to do the job.

Senior

Seniors understand what their role is and how it interacts with other roles around. They can improve the role and not only themselves. They can grow others, can share knowledge, can teach, and they can adapt to changing conditions.

Notice that it doesn’t mean seniors have great skills. Pretty often they are not well skilled at all. However, they can use their skills efficiently and they understand how to grow up themselves and others around. They use their full potential and unblock the full potential of others around.

Senior Engineer vs Architect (vs others)

Based on previous sections, does it mean that seniors don’t need to be good at coding? Or that being an architect requires teaching others?

The answer is a little bit more complex. There are two basic things that we can recognize in software engineering: roles and skills.

Role

Software engineer is a role. Same is architect (and actually every flavor of architect like business architect, enterprise architect, solutions architect, etc.). Each role requires specific skillset and different roles may require similar skills.

Being that said, we should understand that “architect” is not “the next level after senior”. Software architect is a completely separate role. It requires different skills and generates different results. Therefore, one doesn’t need to become a senior engineer before becoming a software architect. Same with scrum masters, product owners, project managers, or people managers.

This also means that architects don’t need to be “experts” in programming. Just like there may be a junior software engineer, there may be a junior architect. It’s just another role.

Skills

Each role requires skills. Some skills may be needed for many roles, for instance dealing with numbers is required for accountants and salespeople. We can measure how good skills we have and we can typically say that we are novice, professionals, or experts. Obviously, we can recognize more levels or even assign numbers. That doesn’t change the point, it only changes the naming.

When it comes to software engineering, we can later recognize many skill dimensions.

Technology

Technology can be your favorite tech stack like C#, Spring, or LAMP. This can be a programming language, database, framework, library, paradigm, application, or whatever else.

For instance, an expert in C# will be able to explain how GC works, what is generational hypothesis, how locks are implemented, or why we can’t inherit from structures.

Area

Area is a particular part of the application. This can be backend, frontend, infrastructure, database, desktop, mobile, or whatever else.

For instance, an expert in web backend would be able to explain SNI, CORS, SOP, certificates, scaling, impersonation, caching, and other things typically used in web backends.

Domain

Domain is a particular part of the reality that we model in software. For instance, this could be payments, medical applications, high frequency trading, or logistics.

For instance, an expert in banking would explain what a credit score is, how to calculate it, what PCI is, how to deal with international transactions, what is ELIXIR, SEPA, or SORBNET.

Who am I

Based on what we said above, it’s possible that one is a senior software engineer + expert in backends + junior in C# + professional in banking. Therefore, we can see why there are software architects that seemingly don’t know how to code.

Programmer vs Software Engineer

Is there a difference between programming and software engineering? That’s a matter of naming and doesn’t matter much. If one doesn’t like to be called programmer, then let’s call them software engineers. This doesn’t matter at all.

What matters is the understanding that programming is not the only thing in “programming” (or “software engineering”). Much more important is “integrating software over time”. It’s easy to write some code. It’s hard to maintain the code over years when technologies around change, operating systems become deprecated, and network technologies disappear. Actually, writing the code is the easiest part of programming. Maintaining the code over years and keeping it alive for decades is what makes the software engineering (or programming) hard.

In short, it doesn’t matter whether we call ourselves programmers or software engineers. What matters is if we can write the code or can develop the same codebase for decades.

How do I know what to do next?

And now comes the tricky part. When someone says they look for “senior programmers”, how do I know what they mean?

The short answer is: you don’t. You won’t know until you ask them what they mean. And this is how you should look for a job: just clarify what the expectations are, what you can do, how good you are in it, and what you get in return. It doesn’t matter if they call you junior, senior, architect, principal, staff, fellow, or distinguished. That doesn’t matter at all (putting psychological aspects aside). What matters is what your role is and what you’re expected to do. That’s it.

This is the twentieth part of the Availability Anywhere series. For your convenience you can find other parts in the table of contents in Part 1 – Connecting to SSH tunnel automatically in Windows

We already know how to use full-tunnel VPN from a virtual machine on the host with TCP over File System. Today we’re going to see how to nest full-tunnel VPN inside another full-tunnel VPN.

Imagine that you take your corporate laptop and go to the office. You want to connect to your client’s network, so you use full-tunnel VPN (something like Cisco AnyConnect or Wireguard). Your client configured their firewall to allow your office’s IP address. All works.

Now, you want to work from home. You take your corporate laptop and come back home. You try connecting to your client’s network, but they didn’t allow your home’s IP address to connect. You try connecting to your office’s network with a VPN and this works well. However, you can’t connect to your client’s VPN now because you can’t have two full-tunnel VPNs enabled. How to deal with that?

I managed to get something like that to work with the following setup:

1. On the host, install Hyper-V
2. On the host, install Hyper-V guest called VM_A. I used Windows 10 x86. It’s better to use x86 VM to avoid some issues with nested virtualization.
3. On the host, enable virtualization extension for VM_A with Get-VM | where Name -eq "VM_A" | Set-VMProcessor -ExposeVirtualizationExtensions $true
4. On the host, connect to Hyper-V guest VM_A with shared drive C:
5. In Hyper-V guest VM_A, install Virtual Box 4.2.36 which works on Windows x86. Some other version of Virtual Box possibly can work.
6. In Hyper-V guest VM_A, create Virtual Box guest VM_B. I used Windows 7 x86. Again, use x86 VM version.
7. Configure VirtualBox guest VM_B networking as NAT with default interface type (something like Intel PRO/1000 MT Desktop)
8. In VirtualBox guest VM_B, install Virtual Box guest addins
9. In VirtualBox, configure shared directory \\tsclient\C with full read-write options (uncheck read only) and with automount
10. In Hyper-V guest VM_A, configure VPN to your office’s network. Let’s call this connection VPN_A.
11. In VirtualBox guest VM_B, configure VPN to your client’s network. Let’s call this connection VPN_B
12. You may need to set DNS in VirtualBox guest VM_B to something like 8.8.8.8
13. Enable VPN_A, then enable VPN_B.

All should work. Mind that in order to use VPN based on layer 3 GRE protocol (like PPTP) for VPN_A, you may need to reconfigure Hyper-V guest to use bridging. I don’t know if it’s possible to use GRE-based VPN for VPN_B in this setup (I doubt that). However, typical corporate VPN-s use HTTPS on the way to avoid issues.

I tested this setup with Wireguard as VPN_A and Windows’ SSTP as VPN_B. It worked correctly. When VPN_A was enabled and VPN_B was disabled, then VirtualBox guest VM_B was visible to the internet from the IP address of VPN_A (so the IP address of the office). When both VPN_A and VPN_B were enabled, VirtualBox guest VM_B was visible to the internet from the IP address of VPN_B (client’s IP address). Also, shared drive from host was visible in VirtualBox guest VM_B when both VPN_A and VPN_B were enabled. Therefore, you can use TCP over File System properly to route the traffic from the host through any of the VPNs.

This is the one hundred and fifth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we are going to solve the Sudoku Cube. It’s a variation of the regular Rubik’s cube in which we have digits on the cube and each side must have exactly nine different digits from one to nine. What’s more, digits on a side must all look the same direction.

I took photos of my cube. You can see them below:

The tricky part is what to do. With the regular cube it’s rather clear where each piece should go. The hard part is figuring out how to put it into place. With Sudoku Cube it’s much harder. We don’t actually see where to put each element. The first step is to “solve the grid”. We need to understand where to put elements.

Solving the grid

First, notice that the number 1 is symmetrical. We don’t know whether it’s facing “up” or “down”. Therefore, we need to assume it can look both directions. We could actually wonder similarly for number eight (which side is “up”) or six/nine, but for them we can make some assumptions. Eight should be narrower at the top. Nine has a label on it.

Second, we don’t know which directions the sides look into. Also, it may not be obvious from the very beginning, but each center has an orientation. This is different from the regular cube. There are algorithms to do so and we’ll see them later. However, for now we need to assume that any side can look any direction. Sometimes the cube is convenient and the “middle strap” sides look upwards, but we can’t assume that.

Therefore, we need to figure out where pieces go. Once we have that, we can then solve the grid.

We start by defining the permutations in this way:

This looks cryptic, so let’s analyze step by step.

Let’s start with the corners marked with red arrows and numbers. We can see six faces of the cube. Going from left to right, top to bottom, the faces are: up, left, front, right, back, down. We have eight corners of the cube. Therefore, there are eight pieces that we can rotate and put in given places. Places are numbered from oen to eight, and permutations are numbered from zero to two. We are going to encode each piece as a list of numbers and list of rotations.

Let’s take the Picture from the above in which you can see free sides of the cube. Let’s say that the side with numbers 3, 9, 4, 6, 1, 5, 5, 7, 9 is the front side, and the side with numbers 5, 4, 6, 3, 6, 5, 8, 2, 2 is the top one. You can see that we have a corner with number 4 to the right of 9 and above 5. This is the corner that we marked as 1_0 on the diagram screen. So we can see, that we can encode this corner as having one with the following sequence of numbers: 4, 8, 4. Therefore 1_0 = 4, 1_1 = 8, 1_2 = 4.

You can see the arrow going up. This is an arbitrary indication which face I consider “upwards” of this given field. Similarly, for other fields. We want to encode the rotation of a piece based on the orientation of the digit. We have four directions: aligned with the arrow encoded as zero, rotated clockwise once by ninety degrees encoded as one, rotated twice encoded as two, rotated three times encoded as three. Therefore, the rotations of the numbers 4, 8, 4 are 3, 2, 1.

We can now take each corner and encode it properly. This should be the encoding:

var corners = new []{
	new Corner(solver, "c1") { Values = new[]{4, 8, 4}, Rotations = new[] {3, 2, 1}},
	new Corner(solver, "c2") { Values = new[]{9, 5, 1}, Rotations = new[] {3, 2, 1}},
	new Corner(solver, "c3") { Values = new[]{5, 9, 1}, Rotations = new[] {2, 2, 1}},
	new Corner(solver, "c4") { Values = new[]{3, 7, 5}, Rotations = new[] {1, 0, 3}},
	new Corner(solver, "c5") { Values = new[]{2, 6, 7}, Rotations = new[] {0, 3, 0}},
	new Corner(solver, "c6") { Values = new[]{6, 3, 7}, Rotations = new[] {2, 1, 2}},
	new Corner(solver, "c7") { Values = new[]{4, 1, 6}, Rotations = new[] {3, 0, 0}},
	new Corner(solver, "c8") { Values = new[]{8, 9, 2}, Rotations = new[] {3, 1, 0}}
};

We can do the same for edges (middles on the sides). We have twelve edges, each edge has two pieces. They are marked with green numbers and arrows. This is how we encode the cube:

var edges = new []{
	new Edge(solver, "e1") { Values = new[]{9, 3}, Rotations = new[] {0, 3}},
	new Edge(solver, "e2") { Values = new[]{5, 2}, Rotations = new[] {0, 2}},
	new Edge(solver, "e3") { Values = new[]{7, 6}, Rotations = new[] {1, 2}},
	new Edge(solver, "e4") { Values = new[]{9, 8}, Rotations = new[] {2, 0}},
	new Edge(solver, "e5") { Values = new[]{3, 2}, Rotations = new[] {0, 2}},
	new Edge(solver, "e6") { Values = new[]{6, 9}, Rotations = new[] {1, 3}},
	new Edge(solver, "e7") { Values = new[]{2, 3}, Rotations = new[] {1, 3}},
	new Edge(solver, "e8") { Values = new[]{8, 5}, Rotations = new[] {3, 3}},
	new Edge(solver, "e9") { Values = new[]{8, 8}, Rotations = new[] {1, 2}},
	new Edge(solver, "e10") { Values = new[]{4, 2}, Rotations = new[] {1, 1}},
	new Edge(solver, "e11") { Values = new[]{3, 4}, Rotations = new[] {2, 0}},
	new Edge(solver, "e12") { Values = new[]{1, 7}, Rotations = new[] {3, 0}}
};

We also have centers. We don’t care about their orientation at this point.

Formulas

We basically want to do the following:

• For each corner: assign exactly one position to a corner (position from one to eight) and one permutation (from zero to two)
• Do the same for edges (twelve positions and two permutations)
• Make sure that each face has all pieces but center oriented the same way
• Make sure that number one can be oriented upside down (as it looks the same)
• Make sure each face has digits from one to nine

Sounds easy. Let’s see the first implementation.

First implementation

Let’s start by encoding the grid. First, we’d like to encode the positions from the chart above. For corners, we take the value like 4_1 and serialize it to one number as 4 * 3 + 1 = 13. We do similarly for edges:

// 0 means empty
// Values are 1_0, 1_1, 1_2, 2_0, 2_1, ...
// Corners have 3 elements, so: 1_0 = 3 * 1 + 0 = 3
// Edges have 2 elements, so: 1_0 = 2 * 1 + 0 = 2
var diagram = new []{
	new[] {0, 0, 0, 16, 17, 26, 0, 0, 0, 0, 0, 0},
	new[] {0, 0, 0, 23, 0, 11, 0, 0, 0, 0, 0, 0},
	new[] {0, 0, 0, 14, 3, 4, 0, 0, 0, 0, 0, 0},
	new[] {17, 22, 13, 12, 2, 3, 5, 10, 25, 24, 16, 15},
	new[] {21, 0, 9, 8, 0, 4, 5, 0, 14, 15, 0, 20},
	new[] {19, 24, 11, 9, 6, 6, 7, 12, 23, 21, 18, 18},
	new[] {0, 0, 0, 10, 7, 8, 0, 0, 0, 0, 0, 0},
	new[] {0, 0, 0, 25, 0, 13, 0, 0, 0, 0, 0, 0},
	new[] {0, 0, 0, 20, 19, 22, 0, 0, 0, 0, 0, 0},
};

Now, we encode the orientation of each field (arrows). We assume -1 means empty field:

var fieldsOrientations = new []{
	new[] {-1, -1, -1, 3, 0, 0, -1, -1, -1, -1, -1, -1},
	new[] {-1, -1, -1, 3, 0, 1, -1, -1, -1, -1, -1, -1},
	new[] {-1, -1, -1, 2, 2, 1, -1, -1, -1, -1, -1, -1},
	new[] {3, 0, 0, 3, 0, 0, 3, 0, 0, 3, 0, 0},
	new[] {3, 0, 1, 3, 0, 1, 3, 0, 1, 3, 0, 1},
	new[] {2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1},
	new[] {-1, -1, -1, 3, 0, 0, -1, -1, -1, -1, -1, -1},
	new[] {-1, -1, -1, 3, 0, 1, -1, -1, -1, -1, -1, -1},
	new[] {-1, -1, -1, 2, 2, 1, -1, -1, -1, -1, -1, -1}
};

Now, let’s make sure that each piece is put in a different position:

// Make corners in distinct positions
solver.Set<AllDifferent>(corners[0].FinalPosition, corners.Skip(1).Select(c => c.FinalPosition).ToArray());

// Make edges in distinct positions
solver.Set<AllDifferent>(edges[0].FinalPosition, edges.Skip(1).Select(e => e.FinalPosition).ToArray());

Let’s now start the magic. The idea is as follows: we ask the solver to assign positions and rotations to the pieces. We then iterate over all possibilities, check if a given possibility was selected by the solver, and then calculate the outcome. We then add the requirements to make the grid solved. Let’s begin with the corners.

Func<int, int, Tuple<IVariable, IVariable>> setupSingleCorner = (x, y) => {
	int number = diagram[x][y];
	int position = number / 3 - 1;
	int permutation = number % 3;
	
	IVariable piecePermutation = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(2));
	IVariable finalPermutation = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(2));
	IVariable pieceRotationValue = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(3));
	IVariable finalRotation = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(3));
	IVariable cornerValue = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(9)).Set<GreaterOrEqual>(solver.FromConstant(1));
	
	foreach(var corner in corners){
		var matchingCorner = solver.Operation<IsEqual>(corner.FinalPosition, solver.FromConstant(position));
		
		solver.Operation<MaterialImplication>(
			matchingCorner,
			solver.Operation<IsEqual>(corner.FinalPermutation, piecePermutation)
		).Set<Equal>(solver.FromConstant(1));
		
		for(int possiblePermutation=0;possiblePermutation<3;++possiblePermutation){
			var matchingPermutation = matchingCorner.Operation<Conjunction>(finalPermutation.Operation<IsEqual>(solver.FromConstant(possiblePermutation)));
		
			solver.Operation<MaterialImplication>(
				matchingPermutation,
				solver.Operation<IsEqual>(pieceRotationValue, solver.FromConstant(corner.Rotations[possiblePermutation]))
			).Set<Equal>(solver.FromConstant(1));
			
			solver.Operation<MaterialImplication>(
				matchingPermutation,
				solver.Operation<IsEqual>(cornerValue, solver.FromConstant(corner.Values[possiblePermutation]))
			).Set<Equal>(solver.FromConstant(1));
		}
	}
	
	solver.Set<Equal>(
		finalPermutation, 
		solver.Operation<Remainder>(
			solver.Operation<Addition>(solver.FromConstant(permutation), piecePermutation),
			solver.FromConstant(3)
		)
	);
	
	solver.Set<Equal>(
		finalRotation, 
		solver.Operation<Remainder>(
			solver.Operation<Addition>(solver.FromConstant(fieldsOrientations[x][y]), pieceRotationValue),
			solver.FromConstant(4)
		)
	);
	
	return Tuple.Create(cornerValue, finalRotation);
};

For each corner from the diagram, we deserialize its position and permutation (lines 2-4). Next, we need to prepare some variables (lines 6-10) and then decipher the solution.

We iterate over each possible piece (line 12) and see if the corner was assigned to the field we analyze now (line 13). If that’s the case, then we copy the value of the assigned permutation to the temporary variable (lines 15-18).

Next, we do some magic. We would like to check all possible permutations to see which one was selected. To do that, we need to calculate what we call here finalPermutation. However, this is some kind of a cyclic dependency. First, we copy the permutation assigned by the solver and called corner.FinalPermutation to the variable piecePermutation (lines 15-18). Next, we need to add the permutation of the field to that value, calculate the modulo three, and assign that to the variable finalPermutation (lines 35-41). However, we then (or technically earlier) use the variable finalPermutation in line 21 to answer whether the current permutation we analyze is the one that was selected. Once we have that, we can copy the rotation of the corner (lines 23-26) and the value of the corner (lines 28-32).

Next, we do another time travel and we calculate the final orientation of the field by adding the orientation of the corner and the orientation (direction of the arrow) of the field. That’s in lines 43-49.

Finally, we return both the value and the final orientation (line 51).

Okay, we can now iterate over all corners of a given face:

Func<int, int, Tuple<IVariable, IVariable>[]> setupCorners = (x, y) => {
	var valuesAndRotations = new []{
		setupSingleCorner(x, y),
		setupSingleCorner(x, y+2),
		setupSingleCorner(x+2, y+2),
		setupSingleCorner(x+2, y)
	};
	
	return valuesAndRotations;
};

We need to do a very similar code with the edges:

Func<int, int, Tuple<IVariable, IVariable>> setupSingleEdge = (x, y) => {
	int number = diagram[x][y];
	int position = number / 2 - 1;
	int permutation = number % 2;
	
	IVariable piecePermutation = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(1));
	IVariable finalPermutation = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(1));
	IVariable pieceRotationValue = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(3));
	IVariable finalRotation = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(3));
	IVariable edgeValue = solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set<LessOrEqual>(solver.FromConstant(9)).Set<GreaterOrEqual>(solver.FromConstant(1));
	
	calculatedRotations[x][y] = finalRotation;
	
	foreach(var edge in edges){
		var matchingEdge = solver.Operation<IsEqual>(edge.FinalPosition, solver.FromConstant(position));
		
		solver.Operation<MaterialImplication>(
			matchingEdge,
			solver.Operation<IsEqual>(edge.FinalPermutation, piecePermutation)
		).Set<Equal>(solver.FromConstant(1));
		
		for(int possiblePermutation=0;possiblePermutation<2;++possiblePermutation){
			var matchingPermutation = matchingEdge.Operation<Conjunction>(finalPermutation.Operation<IsEqual>(solver.FromConstant(possiblePermutation)));
		
			solver.Operation<MaterialImplication>(
				matchingPermutation,
				solver.Operation<IsEqual>(pieceRotationValue, solver.FromConstant(edge.Rotations[possiblePermutation]))
			).Set<Equal>(solver.FromConstant(1));
			
			solver.Operation<MaterialImplication>(
				matchingPermutation,
				solver.Operation<IsEqual>(edgeValue, solver.FromConstant(edge.Values[possiblePermutation]))
			).Set<Equal>(solver.FromConstant(1));
		}
	}
	
	solver.Set<Equal>(
		finalPermutation, 
		solver.Operation<Remainder>(
			solver.Operation<Addition>(solver.FromConstant(permutation), piecePermutation),
			solver.FromConstant(2)
		)
	);
	
	solver.Set<Equal>(
		finalRotation, 
		solver.Operation<Remainder>(
			solver.Operation<Addition>(solver.FromConstant(fieldsOrientations[x][y]), pieceRotationValue),
			solver.FromConstant(4)
		)
	);
	
	return Tuple.Create(edgeValue, finalRotation);
};

We iterate over all edges of a face:

Func<int, int, Tuple<IVariable, IVariable>[]> setupEdges = (x, y) => {
	var valuesAndRotations = new []{
		setupSingleEdge(x, y+1),
		setupSingleEdge(x+1, y),
		setupSingleEdge(x+1, y+2),
		setupSingleEdge(x+2, y+1)
	};
	
	return valuesAndRotations;
};

And we also get the value of the center:

Func<int, int, IVariable> setupCenter = (x, y) => {
	return solver.FromConstant(int.Parse("" + centers[x][y]));
};

We can now setup a single face:

Action<int, int> setupSingleFace = (x, y) => {
	var valuesAndRotations = setupCorners(x, y).Concat(setupEdges(x, y)).ToArray();
	
	var valuesAndRotationsAndOnes = valuesAndRotations.Select(t => {
		var anotherPossibleRotation = solver.Operation<Condition>(
			t.Item1.Operation<IsEqual>(solver.FromConstant(1)),
			t.Item2.Operation<Addition>(solver.FromConstant(2)).Operation<Remainder>(solver.FromConstant(4)),
			t.Item2
		);
		
		return Tuple.Create(t.Item1, t.Item2, anotherPossibleRotation);
	}).ToArray();
	
	// Make pairwise rotations equal = make pieces (but center) look the same direction
	for(int id=1; id < valuesAndRotationsAndOnes.Length; ++id){
		solver.Set<Equal>(
			solver.Operation<Disjunction>(
				solver.Operation<IsEqual>(valuesAndRotationsAndOnes[id].Item2, valuesAndRotationsAndOnes[id-1].Item2),
				solver.Operation<IsEqual>(valuesAndRotationsAndOnes[id].Item2, valuesAndRotationsAndOnes[id-1].Item3),
				solver.Operation<IsEqual>(valuesAndRotationsAndOnes[id].Item3, valuesAndRotationsAndOnes[id-1].Item2),
				solver.Operation<IsEqual>(valuesAndRotationsAndOnes[id].Item3, valuesAndRotationsAndOnes[id-1].Item3)
			),
			solver.FromConstant(1)
		);
	}
	
	var center = setupCenter(x + 1, y+1);
	
	// Make sudoku numbers
	solver.Set<AllDifferent>(center, valuesAndRotationsAndOnes.Select(t => t.Item1).ToArray());
};

We take all the values and rotations of corners and edges (line 2). We then need to take all the ones and calculate additional rotation. We check if the value is one (line 6) and if that’s the case, then we add another rotation (upside-down), otherwise we return the same rotation (lines 7-8).

Finally, we take all the sides and make sure that they all have the same rotations. So for each pair of pieces, either their rotations are equal, or their rotation and alternative rotation are equal, or their alternative rotations are equal (lines 15-25).

Finally, we add the center (line 27) and make sure that all numbers are different (line 30) which means that we have the sudoku requirement met.

We can now configure all faces:

Action setupFaces = () => {
	setupSingleFace(0, 3);
	setupSingleFace(3, 0);
	setupSingleFace(3, 3);
	setupSingleFace(3, 6);
	setupSingleFace(3, 9);
	setupSingleFace(6, 3);
};

setupFaces();

Let’s now add the goal, solve the problem, and print the result:

solver.AddGoal("goal", solver.FromConstant(0));

solver.Solve();

var template = new []{
	"     ---         ",
	"    |   |        ",
	"    |   |        ",
	"    |   |        ",
	" --- --- --- ---",
	"|   |   |   |   |",
	"|   |   |   |   |",
	"|   |   |   |   |",
	" --- --- --- --- ",
	"    |   |        ",
	"    |   |        ",
	"    |   |        ",
	"     ---         "
};

var numbersGrid = template.Select(x => x.ToArray()).ToArray();
var rotationsGrid = template.Select(x => x.ToArray()).ToArray();

Action<int, int, int, int> printSingleCorner = (x, y, destinationX, destinationY) => {
	int number = diagram[x][y];
	int position = number / 3 - 1;
	int permutation = number % 3;
	
	var matchingCorner = corners.First(c => (int)Math.Round(solver.GetValue(c.FinalPosition)) == position);
	var piecePermutation = (int)Math.Round(solver.GetValue(matchingCorner.FinalPermutation));
	
	var finalPermutation = (permutation + piecePermutation) % 3;
	numbersGrid[destinationX][destinationY] = matchingCorner.Values[finalPermutation].ToString()[0];
	
	rotationsGrid[destinationX][destinationY] = matchingCorner.Rotations[finalPermutation].ToString()[0];
};

Action<int, int, int, int> printCorners = (x, y, destinationX, destinationY) => {
	printSingleCorner(x, y, destinationX, destinationY);
	printSingleCorner(x, y+2, destinationX, destinationY + 2);
	printSingleCorner(x+2, y+2, destinationX + 2, destinationY + 2);
	printSingleCorner(x+2, y, destinationX + 2, destinationY);
};

Action<int, int, int, int> printSingleEdge = (x, y, destinationX, destinationY) => {
	int number = diagram[x][y];
	int position = number / 2 - 1;
	int permutation = number % 2;
	
	var matchingEdge = edges.First(e => (int)Math.Round(solver.GetValue(e.FinalPosition)) == position);
	var piecePermutation = (int)Math.Round(solver.GetValue(matchingEdge.FinalPermutation));
	
	var finalPermutation = (permutation + piecePermutation) % 2;
	numbersGrid[destinationX][destinationY] = matchingEdge.Values[finalPermutation].ToString()[0];
	
	rotationsGrid[destinationX][destinationY] = matchingEdge.Rotations[finalPermutation].ToString()[0];
};

Action<int, int, int, int> printEdges = (x, y, destinationX, destinationY) => {
	printSingleEdge(x, y+1, destinationX, destinationY + 1);
	printSingleEdge(x+1, y, destinationX + 1, destinationY);
	printSingleEdge(x+1, y+2, destinationX + 1, destinationY + 2);
	printSingleEdge(x+2, y+1, destinationX + 2, destinationY + 1);
};

Action<int, int, int, int> printCenters = (x, y, destinationX, destinationY) => {
	numbersGrid[destinationX+1][destinationY+1] = centers[x+1][y+1];
};

Action<int, int, int, int> printSingleFace = (x, y, destinationX, destinationY) => {
	printCorners(x, y, destinationX, destinationY);
	printEdges(x, y, destinationX, destinationY);
	printCenters(x, y, destinationX, destinationY);
};

Action printFaces = () => {
	printSingleFace(0, 3, 1, 5);
	printSingleFace(3, 0, 5, 1);
	printSingleFace(3, 3, 5, 5);
	printSingleFace(3, 6, 5, 9);
	printSingleFace(3, 9, 5, 13);
	printSingleFace(6, 3, 9, 5);
};

printFaces();

for(int row = 0; row < template.Length; ++ row){
	Console.Write(new String(numbersGrid[row]));
	Console.Write("          ");
	Console.WriteLine(new String(rotationsGrid[row]));
}

This works. In theory. I tried running that with NEOS for eight hours and it didn’t solve the problem, unfortunately. It was simply too complex.

Let’s see another solution.

Second implementation

In this solution we’ll apply many optimizations. We’ll store the positions as bitmasks instead of integers to use boolean flags (which are much faster). We won’t calculate the obtained direction of the face, but we’ll enforce which face must be selected. Finally, we won’t check the options and see if they were selected, but rather we will calculate what was selected end enforce the options. Let’s start.

First, we create a bitmask for directions of each face. We have six faces (sides) and four directions for each:

// face0_up, face0_right, face0_down, face0_left, face1_up ...
// front = 0, right = 1, back = 2, left = 3, up = 4, down = 5
var facesDirections = Enumerable.Range(0, 6 * 4).Select(d => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray();

Next, we encode a bitmask what value was assigned to each corner side. We have six faces, four corners for each face, and nine numbers to choose from:

// face0_corner_top_right_value1, face0_corner_top_right_value2, ..., face0_corner_top_right_value9, face0_corner_bottom_right_value1,
// ..., face0_corner_bottom_right_value9, face0_corner_bottom_left_value1, ..., face0_corner_top_left_value_9, face1_corner_top_right_value1...
var cornersNumbers = Enumerable.Range(0, 6*4*9).Select(n => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray();

We do the similar for edges:

// face0_top_value1, face_0_top_value2, ..., face0_top_value9, face0_right_value1
// ..., face0_right_value9, face0_bottom_value1, ..., face0_bottom_value9, face0_left_value1, ...
// face0_left_value9, face1_top_value1...
var edgeNumbers = Enumerable.Range(0, 6*4*9).Select(n => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray();

Now, we can use these bitmasks to constrain the solution. We make sure that digits on a face look all the same direction. So, for each face we take the direction flags and make sure that only one flag is selected:

// Each face has exactly one direction
for(var faceId = 0; faceId < 6; ++faceId){
	solver.Operation<Addition>(facesDirections.Skip(faceId * 4).Take(4).ToArray()).Set<Equal>(solver.FromConstant(1));
}

We then make sure each corner has exactly one number. We have six faces and four corners on each face:

// Each corner has exactly one number
for(var cornerId = 0; cornerId < 6 * 4; ++cornerId){
	solver.Operation<Addition>(cornersNumbers.Skip(cornerId * 9).Take(9).ToArray()).Set<Equal>(solver.FromConstant(1));
}

We now need to see how corners are stored. Previously, corner.FinalPosition was an integer. Now it’s a long bitmasks of positions and permutations. We have eight possible positions and three permutations:

public class Corner$id {
	public int[] Values {get;set;}
	public int[] Rotations {get;set;}
	public IVariable[] FinalPosition {get; set;}
	public string Prefix {get;set;}
	
	public Corner(IMilpManager solver, string prefix){
		// position1_permutation0, position1_permutation1, position1_permutation2, position2_permutation0, ...
		FinalPosition = Enumerable.Range(0, 8*3).Select(d => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray();
		Prefix = prefix;
	}
}

Next, we make sure that each corner piece has exactly one position and one rotation selected:

// Each corner is in one place
foreach(var corner in corners){
	solver.Operation<Addition>(corner.FinalPosition).Set<Equal>(solver.FromConstant(1));
}

Next we need to make sure that each corner of the cube has exactly one piece assigned. We have eight corners, for each corner we take bit flags of each piece, and make sure that only one was selected:

// Exactly one piece in given corner
for(var cornerId = 0; cornerId < 8; ++cornerId){
	solver.Operation<Addition>(
		corners.SelectMany(corner => corner.FinalPosition.Skip(cornerId * 3).Take(3)).ToArray()
	).Set<Equal>(solver.FromConstant(1));
}

We do the same for edges:

// Each edge has exactly one number
for(var edgeId = 0; edgeId < 6 * 4; ++edgeId){
	solver.Operation<Addition>(edgeNumbers.Skip(edgeId * 9).Take(9).ToArray()).Set<Equal>(solver.FromConstant(1));
}

// Each edge is in one place
foreach(var edge in edges){
	solver.Operation<Addition>(edge.FinalPosition).Set<Equal>(solver.FromConstant(1));
}

// Exactly one piece in given edge
for(var edgeId = 0; edgeId < 12; ++edgeId){
	solver.Operation<Addition>(
		edges.SelectMany(edge => edge.FinalPosition.Skip(edgeId * 2).Take(2)).ToArray()
	).Set<Equal>(solver.FromConstant(1));
}

Now we need to make sure that each side has sudoku numbers:

var faceToCenters = new Dictionary<int, Tuple<int, int>>{
	{0, Tuple.Create(4, 4)},
	{1, Tuple.Create(4, 7)},
	{2, Tuple.Create(4, 10)},
	{3, Tuple.Create(4, 1)},
	{4, Tuple.Create(1, 4)},
	{5, Tuple.Create(7, 4)}
};

// Sudoku numbers on each face
for(var faceId = 0; faceId < 6; ++faceId){
	var centerPosition = faceToCenters[faceId];
	var centerNumber = int.Parse("" + centers[centerPosition.Item1][centerPosition.Item2]);

	var cornerDigits = Enumerable.Range(0, 4).Select(p => cornersNumbers.Skip(faceId * 4 * 9).Skip(p * 9).Take(9).ToArray()).ToArray();
	var edgeDigits = Enumerable.Range(0, 4).Select(p => edgeNumbers.Skip(faceId * 4 * 9).Skip(p * 9).Take(9).ToArray()).ToArray();
	var centerDigit = new [] { Enumerable.Range(0, 9).Select(i => i == centerNumber - 1 ? solver.FromConstant(1) : solver.FromConstant(0)).ToArray() };
	var vectors = cornerDigits.Concat(edgeDigits).Concat(centerDigit).ToArray();
		
	for(var digit = 0; digit < 9; ++ digit){
		solver.Operation<Addition>(vectors.Select(v => v[digit]).ToArray()).Set<Equal>(solver.FromConstant(1));
	}
}

We need two additional mappings from corners and edges to faces:

var cornersToFaces = new Dictionary<Tuple<int, int>, int> {
	{Tuple.Create(0, 3), 4},
	{Tuple.Create(0, 5), 4},
	{Tuple.Create(2, 3), 4},
	{Tuple.Create(2, 5), 4},
	{Tuple.Create(3, 0), 3},
	{Tuple.Create(3, 2), 3},
	{Tuple.Create(5, 0), 3},
	{Tuple.Create(5, 2), 3},
	{Tuple.Create(3, 3), 0},
	{Tuple.Create(3, 5), 0},
	{Tuple.Create(5, 3), 0},
	{Tuple.Create(5, 5), 0},
	{Tuple.Create(3, 6), 1},
	{Tuple.Create(3, 8), 1},
	{Tuple.Create(5, 6), 1},
	{Tuple.Create(5, 8), 1},
	{Tuple.Create(3, 9), 2},
	{Tuple.Create(3, 11), 2},
	{Tuple.Create(5, 9), 2},
	{Tuple.Create(5, 11), 2},
	{Tuple.Create(6, 3), 5},
	{Tuple.Create(6, 5), 5},
	{Tuple.Create(8, 3), 5},
	{Tuple.Create(8, 5), 5},
};

var edgesToFaces = new Dictionary<Tuple<int, int>, int> {
	{Tuple.Create(0, 4), 4},
	{Tuple.Create(1, 3), 4},
	{Tuple.Create(1, 5), 4},
	{Tuple.Create(2, 4), 4},
	{Tuple.Create(3, 1), 3},
	{Tuple.Create(4, 0), 3},
	{Tuple.Create(4, 2), 3},
	{Tuple.Create(5, 1), 3},
	{Tuple.Create(3, 4), 0},
	{Tuple.Create(4, 3), 0},
	{Tuple.Create(4, 5), 0},
	{Tuple.Create(5, 4), 0},
	{Tuple.Create(3, 7), 1},
	{Tuple.Create(4, 6), 1},
	{Tuple.Create(4, 8), 1},
	{Tuple.Create(5, 7), 1},
	{Tuple.Create(3, 10), 2},
	{Tuple.Create(4, 9), 2},
	{Tuple.Create(4, 11), 2},
	{Tuple.Create(5, 10), 2},
	{Tuple.Create(6, 4), 5},
	{Tuple.Create(7, 3), 5},
	{Tuple.Create(7, 5), 5},
	{Tuple.Create(8, 4), 5},
};

We also need to know where each corner is (whether it’s right top, right bottom, left bottom, left top). Similarly for edges (top, right, bottom, left):

var cornersToDiagonalEnds = new Dictionary<Tuple<int, int>, int> {
	{Tuple.Create(0, 3), 3},
	{Tuple.Create(0, 5), 0},
	{Tuple.Create(2, 3), 2},
	{Tuple.Create(2, 5), 1},
	{Tuple.Create(3, 0), 3},
	{Tuple.Create(3, 2), 0},
	{Tuple.Create(5, 0), 2},
	{Tuple.Create(5, 2), 1},
	{Tuple.Create(3, 3), 3},
	{Tuple.Create(3, 5), 0},
	{Tuple.Create(5, 3), 2},
	{Tuple.Create(5, 5), 1},
	{Tuple.Create(3, 6), 3},
	{Tuple.Create(3, 8), 0},
	{Tuple.Create(5, 6), 2},
	{Tuple.Create(5, 8), 1},
	{Tuple.Create(3, 9), 3},
	{Tuple.Create(3, 11), 0},
	{Tuple.Create(5, 9), 2},
	{Tuple.Create(5, 11), 1},
	{Tuple.Create(6, 3), 3},
	{Tuple.Create(6, 5), 0},
	{Tuple.Create(8, 3), 2},
	{Tuple.Create(8, 5), 1},
};

var edgesToAxisEnds = new Dictionary<Tuple<int, int>, int> {
	{Tuple.Create(0, 4), 0},
	{Tuple.Create(1, 3), 3},
	{Tuple.Create(1, 5), 1},
	{Tuple.Create(2, 4), 2},
	{Tuple.Create(3, 1), 0},
	{Tuple.Create(4, 0), 3},
	{Tuple.Create(4, 2), 1},
	{Tuple.Create(5, 1), 2},
	{Tuple.Create(3, 4), 0},
	{Tuple.Create(4, 3), 3},
	{Tuple.Create(4, 5), 1},
	{Tuple.Create(5, 4), 2},
	{Tuple.Create(3, 7), 0},
	{Tuple.Create(4, 6), 3},
	{Tuple.Create(4, 8), 1},
	{Tuple.Create(5, 7), 2},
	{Tuple.Create(3, 10), 0},
	{Tuple.Create(4, 9), 3},
	{Tuple.Create(4, 11), 1},
	{Tuple.Create(5, 10), 2},
	{Tuple.Create(6, 4), 0},
	{Tuple.Create(7, 3), 3},
	{Tuple.Create(7, 5), 1},
	{Tuple.Create(8, 4), 2},
};

With all that prepared we can finally assert the corners:

Action<int, int> setupSingleCorner = (x, y) => {
	int number = diagram[x][y];
	int position = number / 3 - 1;
	int permutation = number % 3;
	var face = cornersToFaces[Tuple.Create(x, y)];
	var diagonalEnd = cornersToDiagonalEnds[Tuple.Create(x, y)];
	
	foreach(var corner in corners){
		for(var piecePermutation = 0; piecePermutation < 3; ++piecePermutation){
			var wasPicked = corner.FinalPosition.Skip(position * 3).Skip(piecePermutation).First();
			var finalPermutation = (permutation + piecePermutation) % 3;
			var finalRotation = (corner.Rotations[finalPermutation] + fieldsOrientations[x][y]) % 4;
			var value = corner.Values[finalPermutation];
			
			if(value == 1){
				solver.Operation<MaterialImplication>(
					wasPicked,
					solver.Operation<Disjunction>(
						facesDirections.Skip(face * 4).Take(4).ToArray()[finalRotation],
						facesDirections.Skip(face * 4).Take(4).ToArray()[(finalRotation + 2)%4]
					)
				).Set<Equal>(solver.FromConstant(1));
			}else{
				solver.Operation<MaterialImplication>(
					wasPicked,
					facesDirections.Skip(face * 4).Take(4).ToArray()[finalRotation]
				).Set<Equal>(solver.FromConstant(1));
			}
			
			solver.Operation<MaterialImplication>(
				wasPicked,
				cornersNumbers.Skip(face * 4 * 9).Skip(diagonalEnd * 9).Take(9).ToArray()[value - 1]
			).Set<Equal>(solver.FromConstant(1));
		}
	}
};

We take some metadata about the piece we are in (lines 2-6). Next, we iterate over all corners and permutations. However, this time instead of asking “is this corner in that permutation assigned to this field”, we simply take what was assigned and enforce the proper bitflags.

We first take the bit indicating whether a given piece was assigned to this corner and this permutation (line 10). Next, we calculate the final permutation in this field (line 11) and the final rotation including directions of the arrows (line 12). We also take the value of the piece (line 13). Notice that this time we don’t extract these values from the ILP variables. We precalculate them outside of the model which is much faster.

We can now do two simple constraints. First, if this digit is one (line 15) then we enforce this constraint: if this piece was picked (line 17), then direction of the face needs to be either the same as the direction of the piece (line 19) or the opposite (line 20). If the digit is not one, then we enforce the constraint, that if the piece was picked, than the boolean flag indicating the direction of the face must be selected (line 26).

The crucial difference is that we don’t calculate the direction within the model now. We do the causation outside of the model. We encode something like “I don’t know what piece was selected, but if the piece I’m currently looking at was selected, then this bit flag of the face direction must be selected too”.

The next constraint we add is for the numbers: if the piece was picked (line 31) then the number assigned to the corner is selected (line 32). Again, we don’t care about the actual value if it was selected or not. We just make sure that if it was selected, then some other bit flag is set.

We can now setup all corners:

Action<int, int> setupCorners = (x, y) => {
	setupSingleCorner(x, y);
	setupSingleCorner(x, y+2);
	setupSingleCorner(x+2, y+2);
	setupSingleCorner(x+2, y);
};

We do very similar stuff for edges:

Action<int, int> setupSingleEdge = (x, y) => {
	int number = diagram[x][y];
	int position = number / 2 - 1;
	int permutation = number % 2;
	var face = edgesToFaces[Tuple.Create(x, y)];
	var axisEnd = edgesToAxisEnds[Tuple.Create(x, y)];
	
	foreach(var edge in edges){
		for(var piecePermutation = 0; piecePermutation < 2; ++piecePermutation){
			var wasPicked = edge.FinalPosition.Skip(position * 2).Skip(piecePermutation).First();
			var finalPermutation = (permutation + piecePermutation) % 2;
			var finalRotation = (edge.Rotations[finalPermutation] + fieldsOrientations[x][y]) % 4;
			var value = edge.Values[finalPermutation];
			
			if(value == 1){
				solver.Operation<MaterialImplication>(
					wasPicked,
					solver.Operation<Disjunction>(
						facesDirections.Skip(face * 4).Take(4).ToArray()[finalRotation],
						facesDirections.Skip(face * 4).Take(4).ToArray()[(finalRotation + 2)%4]
					)
				).Set<Equal>(solver.FromConstant(1));
			}else{
				solver.Operation<MaterialImplication>(
					wasPicked,
					facesDirections.Skip(face * 4).Take(4).ToArray()[finalRotation]
				).Set<Equal>(solver.FromConstant(1));
			}
			
			solver.Operation<MaterialImplication>(
				wasPicked,
				edgeNumbers.Skip(face * 4 * 9).Skip(axisEnd * 9).Take(9).ToArray()[value - 1]
			).Set<Equal>(solver.FromConstant(1));
		}
	}
};

Action<int, int> setupEdges = (x, y) => {
	setupSingleEdge(x, y+1);
	setupSingleEdge(x+1, y);
	setupSingleEdge(x+1, y+2);
	setupSingleEdge(x+2, y+1);
};

Finally, we encode faces:

Action<int, int> setupSingleFace = (x, y) => {
	setupCorners(x, y);
	setupEdges(x, y);
};

Action setupFaces = () => {
	setupSingleFace(0, 3);
	setupSingleFace(3, 0);
	setupSingleFace(3, 3);
	setupSingleFace(3, 6);
	setupSingleFace(3, 9);
	setupSingleFace(6, 3);
};

setupFaces();

We run it and this is the result we get:

Tried aggregator 2 times.
MIP Presolve eliminated 7285 rows and 3504 columns.
MIP Presolve modified 1149 coefficients.
Aggregator did 3596 substitutions.
Reduced MIP has 979 rows, 844 columns, and 4885 nonzeros.
Reduced MIP has 844 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.03 sec. (15.56 ticks)
Found incumbent of value 0.000000 after 0.03 sec. (24.88 ticks)

Root node processing (before b&c):
  Real time             =    0.03 sec. (25.19 ticks)
Parallel b&c, 12 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.03 sec. (25.19 ticks)
     ---                        ---
    |239|                      |333|
    |568|                      |3 3|
    |147|                      |333|
 --- --- --- ---           --- --- --- ---
|829|523|681|529|          |222|111|111|111|
|157|618|974|347|          |2 2|1 1|1 1|1 1|
|634|497|532|681|          |222|111|111|111|
 --- --- --- ---            --- --- --- ---
    |863|                      |111|
    |219|                      |1 1|
    |457|                      |111|
     ---                        ---

It took 30 milliseconds to find the answer. First implementation couldn’t do that in 8 hours. Not to mention that the first implementation ran on Gurobi in NEOS, and the second one was running with CPLEX on my local machine.

Reading the solution

Let’s read the solution. We can see that when we hold the cube in a way that the top side has center 6, front side has center 1, and bottom side has center 1, then the top side looks to the left, left side looks down, front and right and back and down sides look to the right. We can also see all the numbers assigned, so we know the “colors” of the pieces. We can now apply the regular algorithms for solving the cube.

The last remaining piece is how to rotate centers. There are two algorithms for that:

• Top center clockwise and front center counter-clockwise: f b’ l r’ u d’ f’ u’ d l’ r f’ b u
• Top center 180 degrees: u r l uu r’ l’ u r l uu r’ l’

We can now easily solve the cube:

Lessons learned

There are some important tricks we applied to optimize the solution:

1. We stored numbers as bitflags instead of storing them as integers. This is a common trick. If you know the range of the variables, then don’t use integers. Bitflags are much faster.
2. We precalcualted results outside of the model. Instead of creating a variable with a value of the face rotation, we calculated the rotation outside of the model, and then added a constraint (basically, an “if” condition in the ILP)
3. We didn’t compare numbers. Generally, don’t do that if it’s possible. Instead, just create a boolean flag indicating the result of comparison and use it later onw. The difference is subtle but improves the performance a lot.
4. We didn’t use “if else” conditions. They look easy, but they are really the performance killer.

With all these improvements in place, we managed to solve the cube in milliseconds.