badflyer

Peter Sulucz - April 2, 19

By default, .Net does not provide performance counters for the built in ThreadPool. Detecting ThreadPool starvation can be extremely difficult. We can use the frameworks internal trace source as a hook to implement some of our own statistics. This post provides an example of how to do just that, by writing out the ThreadPool queue length to the Console.

The ThreadPool does offer internal methods for querying the Queue Length directly, but they are designed to be used by a debugger, so are not thread safe. Ex: ThreadPool.GetQueuedWorkItems();

These are the methods we are interested in on the FrameworkEventSource:

[Event(30, Level = EventLevel.Verbose, Keywords = (EventKeywords)18L)]
public void ThreadPoolEnqueueWork(long workID)

[Event(31, Level = EventLevel.Verbose, Keywords = (EventKeywords)18L)]
public void ThreadPoolDequeueWork(long workID)

The following code snippet demonstrates how to create an in-process EventListener which subscribes to the FrameworkEventSource and keeps track of work item Enqueues and Dequeues. A growing queue can be used to track that the threadpool is having trouble keeping up with the amount of work that is assigned to it. ‘Main’ demonstrates the usage, and a program which starves the ThreadPool by creating work items which sleep in threads for 10 seconds. Ideally, the work done within OnEventWritten should be minimal.

using System;
using System.Diagnostics.Tracing;
using System.Threading;

class Program
{
    static void Main(string[] args)
    {
        using (var eventListener = new ThreadPoolWorkListener())
        {
            // Sleeping in threadpool threads will block them all up very quickly
            for (var i = 0; i < 100; i++)
            {
                ThreadPool.QueueUserWorkItem((a) => Thread.Sleep(10000));
            }

            // So I can read the console output.
            Console.ReadLine();
        }
    }

    /// <summary>
    /// An EventListener which listens to .Net's internal FrameworkEventSource
    /// </summary>
    private class ThreadPoolWorkListener : EventListener
    {
        /// <summary>
        /// The current thread pool length.
        /// </summary>
        private volatile int queueLength = 0;

        /// <summary>
        /// The framework event source.
        /// </summary>
        private EventSource frameworkSource = null;

        /// <summary>
        /// Callback which is called for every event source in the app domain.
        /// </summary>
        /// <param name="eventSource">The event source.</param>
        protected override void OnEventSourceCreated(EventSource eventSource)
        {
            base.OnEventSourceCreated(eventSource);

            // We care about .net's internal framework event source.
            if (eventSource.Name == "System.Diagnostics.Eventing.FrameworkEventSource")
            {
                this.frameworkSource = eventSource;

                // Register for 'Verbose' events with Keywork 18. Which are the threadpool events.
                this.EnableEvents(this.frameworkSource, EventLevel.Verbose, (EventKeywords)(18));
            }
        }

        /// <summary>
        /// Called when every event is written.
        /// </summary>
        /// <param name="eventData">The event data.</param>
        protected override void OnEventWritten(EventWrittenEventArgs eventData)
        {
            // Enqueue work item.
            if (eventData.EventId == 30)
            {
                var len = Interlocked.Increment(ref this.queueLength);
                Console.WriteLine("[{0:hh:mm:ss.ffffff}] Enqueue: {1} Thread pool length {2}", DateTime.UtcNow, eventData.Payload[0], len);
            }
            // Dequeue work item.
            else if (eventData.EventId == 31)
            {
                var len = Interlocked.Decrement(ref this.queueLength);
                Console.WriteLine("[{0:hh:mm:ss.ffffff}] Dequeue: {1} Thread pool length {2}", DateTime.UtcNow, eventData.Payload[0], len);
            }
        }

        /// <summary>
        /// Clean up and unregister.
        /// </summary>
        public override void Dispose()
        {
            if (this.frameworkSource != null)
            {
                // Cleanup.
                this.DisableEvents(this.frameworkSource);
                this.frameworkSource = null;
            }

            base.Dispose();
        }
    }
}

The programs output shows that the ThreadPool becomes very slow to spin up new threads as it detects that it is not making any more progress. With new items only being dequeued every second once the pool is full.

//[06:16:53.866470] Dequeue: 46389784 Thread pool length 76
//[06:16:54.818976] Dequeue: 46391980 Thread pool length 73
//[06:16:54.818976] Dequeue: 46392712 Thread pool length 72
//[06:16:55.820560] Dequeue: 46393444 Thread pool length 71
//[06:16:55.821565] Dequeue: 46394176 Thread pool length 70
//[06:16:56.820340] Dequeue: 46394908 Thread pool length 69
//[06:16:56.821342] Dequeue: 46395640 Thread pool length 68
//[06:16:57.816945] Dequeue: 46396372 Thread pool length 67
//[06:16:57.817923] Dequeue: 46397104 Thread pool length 66
//[06:16:58.821703] Dequeue: 46397836 Thread pool length 65
//[06:16:58.821703] Dequeue: 46398568 Thread pool length 64
//[06:16:59.822980] Dequeue: 46399300 Thread pool length 63
//[06:16:59.822980] Dequeue: 46400032 Thread pool length 62
//[06:17:00.817492] Dequeue: 46400764 Thread pool length 61

While the Task Parallel Library (TPL) uses the .Net ThreadPool by default, another interesting internal trace source to consider is the TPL trace source, ‘System.Threading.Tasks.TplEventSource’, which exposes events such as TaskScheduled and TaskCompleted. Hooking into those using the same method could give more detail on how the TPL is behaving for your application.

More detail for the FrameworkEventSource is available here: frameworkeventsource.cs
More detail for the TPLEventSource is available here: TPLETWProvider.cs
Peter Sulucz - March 25, 19

Using the regular ManualResetEvent provided by the .Net framework during async code can cause performance issues by blocking up available ThreadPool threads. Searching online Thread.Sleep() vs Task.Delay() will provide some more details. Below you fill find an implementation of ManualResetEvent which is async ready and soft on the ThreadPool.

If you don't care how things work, and all you need is some code, then scroll on down to the bottom!

The implementation hinges mostly around a TaskCompletionSource, which as itself can already be used as a ManualResetEvent. The basic idea is that the class contains a single TaskCompletionSource. When a thread invokes ‘WaitAsync’, they get a reference to the uncompleted task on the TaskCompletionSource. When another thread calls ‘Set’, we can complete the TaskCompletionSource, and all of the threads waiting on ‘WaitAsync’ can continue. The implementation below is not really any sort “ResetEvent” because it can’t be Reset.

public sealed class SuperBasicEventSlim
{
    private TaskCompletionSource<bool> completionSource = new TaskCompletionSource<bool>();

    public void Set()
    {
        this.completionSource.TrySetResult(true);
    }

    public Task WaitAsync()
    {
        return this.completionSource.Task;
    }
}

A TaskCompletionSource can’t transfer out of the completed state so in order to reset we will need to create a new one and start returning the new task. The below implementation is fully functional but doesn’t allow threads to Timeout or Cancel waiting. An important thing to note is that continuations with the "ExecuteSynchronously" attribute will execute immediately on the thread which called "Set". You will see below in the implementation that we provide that behavior, along with executing them on a ThreadPool thread.

public class BasicManualResetEvent
{
    private volatile TaskCompletionSource<bool> completionSource = new TaskCompletionSource<bool>();

    public void Set()
    {
        this.completionSource.TrySetResult(true);
    }

    public Task WaitAsync()
    {
        return this.completionSource.Task;
    }

    public void Reset()
    {
        var currentCompletionSource = this.completionSource;

        if (!currentCompletionSource.Task.IsCompleted)
        {
            return;
        }

        Interlocked.CompareExchange(ref this.completionSource, new TaskCompletionSource<bool>(), currentCompletionSource);
    }
}

The reason for the CompareExchange, is to prevent us from overwriting a new TaskCompletionSource if two threads try to Reset at the same time. We don’t want to leave anyone waiting on a task which we’ve lost all references to.

In order to be more ‘Async Friendly’, now we’re going to implement WaitAsync with both a CancellationToken and a Timeout. There are three scenarios to consider:

  • Set is called
  • Caller cancels the CancellationToken
  • Timeout expires

These scenarios are handled in the method ‘AwaitCompletion’. We always await two tasks. One of which is a TaskCompletionSource and another is a Delay. The TaskCompletionSource handles gets completed when someone calls ‘Set’. The Delay task is used to support a Timeout and a CancellationToken. If the user doesn’t specify a delay, we await an indefinite task (Task.Delay(-1)). One thing to note here is that the user has the option to exclude both a CancellationToken and a delay, in which case there is no reason to do any extra work, we can just return the original task.

private async Task<bool> AwaitCompletion(int timeoutMS, CancellationToken token)
{
    // Validate arguments.
    if (timeoutMS < -1 || timeoutMS > int.MaxValue)
    {
        throw new ArgumentException("The timeout must be either -1ms (indefinitely) or a positive ms value <= int.MaxValue");
    }

    CancellationTokenSource timeoutToken = null;

    // If the token cannot be cancelled, then we don't need to create any sort of linked token source.
    if (false == token.CanBeCanceled)
    {
        // If the wait is indefinite, then we don't need to create a second task at all to wait on, just wait for set. 
        if (timeoutMS == -1)
        {
            return await this.completionSource.Task;
        }

        timeoutToken = new CancellationTokenSource();
    }
    else
    {
        // A token source which will get canceled either when we cancel it, or when the linked token source is canceled.
        timeoutToken = CancellationTokenSource.CreateLinkedTokenSource(token);
    }

    using (timeoutToken)
    {
        // Create a task to account for our timeout. The continuation just eats the task cancelled exception, but makes sure to observe it.
        Task delayTask = Task.Delay(timeoutMS, timeoutToken.Token).ContinueWith((result) => { var e = result.Exception; }, TaskContinuationOptions.ExecuteSynchronously);

        var resultingTask = await Task.WhenAny(this.completionSource.Task, delayTask).ConfigureAwait(false);

        // The actual task finished, not the timeout, so we can cancel our cancellation token and return true.
        if (resultingTask != delayTask)
        {
            // Cancel the timeout token to cancel the delay if it is still going.
            timeoutToken.Cancel();
            return true;
        }

        // Otherwise, the delay task finished. So throw if it finished because it was canceled.
        token.ThrowIfCancellationRequested();
        return false;
    }
}

All four of the WaitAsync methods invoke this one with different arguments. The full code, which is ready to be copy/pasted is here below!

using System;
using System.Threading;
using System.Threading.Tasks;

/// <summary>
/// An async manual reset event.
/// </summary>
public sealed class ManualResetEventAsync
{
    // Inspiration from https://devblogs.microsoft.com/pfxteam/building-async-coordination-primitives-part-1-asyncmanualresetevent/
    // and the .net implementation of SemaphoreSlim

    /// <summary>
    ///  The timeout in milliseconds to wait indefinitly.
    /// </summary>
    private const int WaitIndefinitly = -1;

    /// <summary>
    /// True to run synchronous continuations on the thread which invoked Set. False to run them in the threadpool.
    /// </summary>
    private readonly bool runSynchronousContinuationsOnSetThread = true;

    /// <summary>
    /// The current task completion source.
    /// </summary>
    private volatile TaskCompletionSource<bool> completionSource = new TaskCompletionSource<bool>();

    /// <summary>
    /// Initializes a new instance of the <see cref="ManualResetEventAsync"/> class.
    /// </summary>
    /// <param name="isSet">True to set the task completion source on creation.</param>
    public ManualResetEventAsync(bool isSet)
        : this(isSet: isSet, runSynchronousContinuationsOnSetThread: true)
    {
    }

    /// <summary>
    /// Initializes a new instance of the <see cref="ManualResetEventAsync"/> class.
    /// </summary>
    /// <param name="isSet">True to set the task completion source on creation.</param>
    /// <param name="runSynchronousContinuationsOnSetThread">If you have synchronous continuations, they will run on the thread which invokes Set, unless you set this to false.</param>
    public ManualResetEventAsync(bool isSet, bool runSynchronousContinuationsOnSetThread)
    {
        this.runSynchronousContinuationsOnSetThread = runSynchronousContinuationsOnSetThread;

        if (isSet)
        {
            this.completionSource.TrySetResult(true);
        }
    }

    /// <summary>
    /// Wait for the manual reset event.
    /// </summary>
    /// <returns>A task which completes when the event is set.</returns>
    public Task WaitAsync()
    {
        return this.AwaitCompletion(ManualResetEventAsync.WaitIndefinitly, default(CancellationToken));
    }

    /// <summary>
    /// Wait for the manual reset event.
    /// </summary>
    /// <param name="token">A cancellation token.</param>
    /// <returns>A task which waits for the manual reset event.</returns>
    public Task WaitAsync(CancellationToken token)
    {
        return this.AwaitCompletion(ManualResetEventAsync.WaitIndefinitly, token);
    }

    /// <summary>
    /// Wait for the manual reset event.
    /// </summary>
    /// <param name="timeout">A timeout.</param>
    /// <param name="token">A cancellation token.</param>
    /// <returns>A task which waits for the manual reset event. Returns true if the timeout has not expired. Returns false if the timeout expired.</returns>
    public Task<bool> WaitAsync(TimeSpan timeout, CancellationToken token)
    {
        return this.AwaitCompletion((int)timeout.TotalMilliseconds, token);
    }

    /// <summary>
    /// Wait for the manual reset event.
    /// </summary>
    /// <param name="timeout">A timeout.</param>
    /// <returns>A task which waits for the manual reset event. Returns true if the timeout has not expired. Returns false if the timeout expired.</returns>
    public Task<bool> WaitAsync(TimeSpan timeout)
    {
        return this.AwaitCompletion((int)timeout.TotalMilliseconds, default(CancellationToken));
    }

    /// <summary>
    /// Set the completion source.
    /// </summary>
    public void Set()
    {
        if (this.runSynchronousContinuationsOnSetThread)
        {
            this.completionSource.TrySetResult(true);
        }
        else
        {
            // Run synchronous completions in the thread pool.
            Task.Run(() => this.completionSource.TrySetResult(true));
        }
    }

    /// <summary>
    /// Reset the manual reset event.
    /// </summary>
    public void Reset()
    {
        // Grab a reference to the current completion source.
        var currentCompletionSource = this.completionSource;

        // Check if there is nothing to be done, return.
        if (!currentCompletionSource.Task.IsCompleted)
        {
            return;
        }

        // Otherwise, try to replace it with a new completion source (if it is the same as the reference we took before).
        Interlocked.CompareExchange(ref this.completionSource, new TaskCompletionSource<bool>(), currentCompletionSource);
    }

    /// <summary>
    /// Await completion based on a timeout and a cancellation token.
    /// </summary>
    /// <param name="timeoutMS">The timeout in milliseconds.</param>
    /// <param name="token">The cancellation token.</param>
    /// <returns>A task (true if wait succeeded). (False on timeout).</returns>
    private async Task<bool> AwaitCompletion(int timeoutMS, CancellationToken token)
    {
        // Validate arguments.
        if (timeoutMS < -1 || timeoutMS > int.MaxValue)
        {
            throw new ArgumentException("The timeout must be either -1ms (indefinitely) or a positive ms value <= int.MaxValue");
        }

        CancellationTokenSource timeoutToken = null;

        // If the token cannot be cancelled, then we dont need to create any sort of linked token source.
        if (false == token.CanBeCanceled)
        {
            // If the wait is indefinite, then we don't need to create a second task at all to wait on, just wait for set. 
            if (timeoutMS == -1)
            {
                return await this.completionSource.Task;
            }

            timeoutToken = new CancellationTokenSource();
        }
        else
        {
            // A token source which will get canceled either when we cancel it, or when the linked token source is canceled.
            timeoutToken = CancellationTokenSource.CreateLinkedTokenSource(token);
        }

        using (timeoutToken)
        {
            // Create a task to account for our timeout. The continuation just eats the task cancelled exception, but makes sure to observe it.
            Task delayTask = Task.Delay(timeoutMS, timeoutToken.Token).ContinueWith((result) => { var e = result.Exception; }, TaskContinuationOptions.ExecuteSynchronously);

            var resultingTask = await Task.WhenAny(this.completionSource.Task, delayTask).ConfigureAwait(false);

            // The actual task finished, not the timeout, so we can cancel our cancellation token and return true.
            if (resultingTask != delayTask)
            {
                // Cancel the timeout token to cancel the delay if it is still going.
                timeoutToken.Cancel();
                return true;
            }

            // Otherwise, the delay task finished. So throw if it finished because it was canceled.
            token.ThrowIfCancellationRequested();
            return false;
        }
    }
}

There you have it! An async friendly ManualResetEvent implementation.

Peter Sulucz - September 20, 18

Here is a simple quadtree implementation done in typescript! It is used to improve the performance of collision testing between all of the little circles which get displayed. (Clicking will add more circles).

The majority of the quadtree is implemented in a few classes. Here are the few notable ones to look out for.

  • QuadTree
  • QuadTreeNode
  • QuadTreeDrawer

More information on a quadtree can be found online, but the idea behind its use here is the same as that of a binary tree. We keep subdividing the canvas into fourths, so that we can lessen the area we need to consider during collision checking. 3D physics engines commonly use an oct-tree, which divides 3-dimensional space into 8ths.

Take a look at how collisions are processed to speed up the simulation (QuadTree.UpdateRecursive). Normally, you'd have to test each ball against every other ball at n^2 efficiency. With a quadtree, we can walk down each branch of the tree, only considering collisions between objects in the current tree node and parent nodes. The worst case scenario would be an object directly in the middle of the screen, which would be a child of the root quadtree node. It would need to be tested against every other object on the screen in this implemention.

# Here's an example (TL = topleft, TR = topright, BL = bottomleft, BR = bottomright)
----------- -----------|-----------|------------                          ------                                         
|                      |           |           |                         | root |    <---- Children = []                 
|                      |           |     a     |                          ------                                         
|                      |           |           |                      TL  TR  BL  BR                                     
                       ------------d------------                     /    |    |    \                                    
|                      |           |           |                   null   |   null   \                                   
|                      |           |     b     |                       -----         -----                               
|                      |           |           | Children = [ d ] ->  | L1  |       | L1  |    <------ Children = [ c ]  
----------- -----------------------|------------                       -----         -----                               
|                      |                       |                 TL  TR  BL  BR       TL  TR  BL  BR                     
|                      |                       |                /    |   |     \      /    |   |    \                    
|                      |                       |              null   |  null    \   null null null null                  
                                   c                               -----       -----                                     
|                      |                       |Children = [ a ]->| L2  |     | L2  | <------ Children = [ b ]           
|                      |                       |                   -----       -----                                     
|                      |                       |                                                                         
----------- -----------|----------- ------------                                                                         

# You can see that 'c' is on a completely different branch of the tree, so it doesn't need to be tested against a and b.
# a and b are also in different branches, so they also need to be tested.
# d is on the parent node of both a and b. It needs to be checked against both a and b.
/**
* This is a full implementation of the demo above. A lot of the stuff in here
* is just to make it show up on the screen. 
**/

/** Helper methods... */
class Helpers{
    /** Create a random color. But can define some constants. */
    static RandomColor(red : number = undefined, green : number = undefined, blue : number = undefined) : string {
        let r = red != undefined ? red : Math.random() * 256;
        let b = blue != undefined ? blue : Math.random() * 256;
        let g = green != undefined ? green : Math.random() * 256;
        let a = 0.4;

        return "rgba(" + r + "," + g + "," + b + "," + a + ")";
    }

    /** Remove an item from an array. */
    static Remove<T>(array : Array<T>, item : T){
        let index = array.indexOf(item);
        if(index == -1){
            throw "Element does not exist";
        }
        array.splice(index, 1);
    }
}

/** A  2 dimensional vector */
class Vector{
    public x : number;
    public y : number;

    constructor(x : number = 0, y : number = 0){
        this.x = x;
        this.y = y;
    }

    /** The distance between two vectors. */
    static dist(a : Vector, b : Vector) : number{
        return Math.sqrt(Math.pow(b.x - a.x, 2) + Math.pow(b.y - a.y, 2));
    }

    /** The dot product of two vectors. */
    static dot(a : Vector, b : Vector) : number{
        return a.x * b.x + a.y * b.y;
    }

    /** Add this to another vector. And a new vector with the product. */
    add(v : Vector) : Vector{
        return new Vector(v.x + this.x, v.y + this.y);
    }

    /** Subtract another vector from this one, and return a new vector with the product. */
    subtract(v : Vector) : Vector {
        return new Vector(this.x - v.x, this.y - v.y);
    }

    /** Multiply this vector by a scale, and return new vector with the product. */
    scale(scale : number){
        return new Vector(this.x * scale, this.y * scale);
    }

    // Copy this vector
    clone(){
        return new Vector(this.x, this.y);
    }

    /** Flip this vector around. */
    invert(){
        return new Vector(-1 * this.x, -1 * this.y);
    }

    /** Find the magnitude of this vector. */
    magnitude(){
        return Math.sqrt(this.x * this.x + this.y * this.y);
    }

    /** Normalize this vector to a length of 1. */
    normalize(){
        var mag = this.magnitude();
        return new Vector(this.x / mag, this.y / mag);
    }
}

/** The bounding circle class. */
class BoundingCircle{
    readonly position : Vector;
    readonly radius : number;

    constructor(position : Vector, radius : number){
        this.position = position;
        this.radius = radius;
    }

    topLeft() : Vector{
        return new Vector(this.position.x - this.radius, this.position.y - this.radius);
    }

    bottomRight() : Vector{
        return new Vector(this.position.x + this.radius, this.position.y + this.radius);
    }
}

/** Properties for physics */
class PhysicsProperties{
    position : Vector;
    velocity : Vector;
    acceleration : Vector;
    radius : number;
    mass : number;

    constructor(){
        this.position = new Vector();
        this.velocity = new Vector();
        this.radius = 0;
        this.mass = 100000;
        this.acceleration = new Vector();
    }
    
    /** Get the bounding circle for this object. */
    getBounds() : BoundingCircle{
        let circle = new BoundingCircle(this.position, this.radius);
        return circle;
    }

    /** A fully elastic collision between two circles. */
    processColission(other : PhysicsProperties)
    {
        let mcalc = other.mass * 2 / (this.mass + other.mass);

        let postDiff = this.position.subtract(other.position);
        let velocityDiff = this.velocity.subtract(other.velocity);
        let dot = Vector.dot(velocityDiff, postDiff);
        let magnitude = postDiff.magnitude();

        let scalar = mcalc * dot / (magnitude * magnitude);

        let v1 = this.velocity.subtract(postDiff.scale(scalar));
    
        mcalc = this.mass * 2 / (this.mass + other.mass);
        postDiff = other.position.subtract(this.position);
        velocityDiff = other.velocity.subtract(this.velocity);
        dot = Vector.dot(velocityDiff, postDiff);
        magnitude = postDiff.magnitude();
        scalar = mcalc * dot / (magnitude * magnitude);

        let v2 = other.velocity.subtract(postDiff.scale(scalar));

        this.velocity = v1;
        other.velocity = v2;
    }
}

/** Context which is passed on each update. */
class UpdateContext{

    /** The milliseconds since the last update. */
    public readonly deltaMilliseconds : number;

    /** The width of the land. */
    public readonly width : number;

    /** The height of the land. */
    public readonly height : number;

    /** The current time. */
    public readonly currentTime : number;

    constructor(deltaMS : number, width : number, height : number, currentTime : number){
        this.deltaMilliseconds = deltaMS;
        this.width = width;
        this.height = height;
        this.currentTime = currentTime;
    }
}

/** Context passed to the draw call. */
class DrawContext{

    /** The graphics context. */
    public readonly graphics : CanvasRenderingContext2D;

    constructor(context : CanvasRenderingContext2D){
        this.graphics = context;
    }
}

/** An updateable class. */
abstract class GameComponent{

    /** Update. Return true if this item needs to be deleted. */
    abstract update(context : UpdateContext) : boolean; 
    
    public physics : PhysicsProperties;
}

/** A draweable class. */
abstract class DrawableGameComponent extends GameComponent{
    abstract draw(context : DrawContext);
}

/** The physics controller. */
class PhysicsController extends GameComponent{
    
    readonly quadTree : QuadTree;
    readonly compontents : Array<PhysicsProperties>

    constructor(worldSize : Vector){
        super();
        this.quadTree = new QuadTree(8, worldSize);
        this.compontents = new Array<PhysicsProperties>();
    }

    /** Update the physics controller. Updates collisions and the quad tree */
    update(context : UpdateContext) : boolean{
        this.quadTree.Update();
        return false;
    }

    /** Add an item. */
    add(item : PhysicsProperties){
        this.compontents.push(item);
        this.quadTree.add(item);
    }
}

/** A ball on the screen. */
class Ball extends DrawableGameComponent{
    
    physics : PhysicsProperties;
    protected color : string;

    constructor(position : Vector, velocity : Vector, radius : number, color: string){
        super();
        this.physics = new PhysicsProperties();
        this.physics.position = position;
        this.physics.velocity = velocity;
        this.physics.radius = radius;
        this.physics.mass = Math.PI * radius * radius;
        this.color = color;
    }

    static CreateRandom(bounds: Vector, minRadius: number, maxRadius: number, minVelocity: Vector, maxVelocity: Vector)
    {
        let radius = Math.random() * (maxRadius - minRadius) + minRadius;
        let position = new Vector(Math.random() * (bounds.x - radius) + radius, Math.random() * (bounds.y - radius) + radius);
        let velocity = new Vector((Math.random() * (maxVelocity.x - minVelocity.x) + minVelocity.x) * (Math.random() > 0.5 ? 1 : -1 ), (Math.random() * (maxVelocity.y - minVelocity.y) + minVelocity.y) * (Math.random() > 0.5 ? 1 : -1 ));

        return new Ball(position, velocity, radius, Helpers.RandomColor(0, 0, undefined));
    }

    /** Update properties of the ball  */
    update(context : UpdateContext) : boolean{

        this.physics.velocity = this.physics.velocity.add(this.physics.acceleration);
        this.physics.acceleration = new Vector()

        /** Bounce off the walls. */
        if(this.physics.position.x - this.physics.radius <= 0 || this.physics.position.x + this.physics.radius >= context.width){
            this.physics.velocity.x *= -1;
        }

        if(this.physics.position.y - this.physics.radius <= 0 || this.physics.position.y + this.physics.radius >= context.height){
            this.physics.velocity.y *= -1;
        }

        // Update the movement
        this.physics.position = this.physics.position.add(this.physics.velocity.scale(context.deltaMilliseconds / 1000));
        return false;
    }

    /** Draw the ball */
    draw(context : DrawContext){

        context.graphics.beginPath();
        context.graphics.fillStyle = this.color;
        context.graphics.ellipse(
            this.physics.position.x,
            this.physics.position.y,
            this.physics.radius,
            this.physics.radius,
            0,
            0,
            Math.PI * 2);
        context.graphics.fill();
        context.graphics.closePath();
    }
}

/** A quadtree */
class QuadTree
{
    /** The maximum depth. */
    private readonly maxLevels : number;

    /** The root node. */
    private readonly root : QuadTreeNode;

    /** The size of the map. */
    private readonly size : Vector;

    /** The list of components. */
    private readonly components : Array<ComponentWrapper>

    public collisionsProcessed : number;

    constructor(maxLevels : number, size : Vector){
        this.maxLevels = maxLevels;
        this.root = new QuadTreeNode(1, this.maxLevels, null, new Vector(), size.clone());

        this.components = new Array<ComponentWrapper>();
    }

    /** Get the root node. */
    getRoot() : QuadTreeNode{
        return this.root;
    }

    /** Add a component to the tree. */
    add(component : PhysicsProperties){
        let wrapper = new ComponentWrapper(component, null);
        this.components.push(wrapper);
        this.getFittingNode(wrapper);
    }

    /** Update the entire tree. */
    Update(){
        for(let i = 0; i < this.components.length; i++){
            let component = this.components[i];

            this.root.GetNodeForComponent(component);
        }

        this.collisionsProcessed = 0;
        this.UpdateRecursive(this.root, new Array<PhysicsProperties>());
    }

    /** Update each node, test for collisions. */
    private UpdateRecursive(node : QuadTreeNode, list : Array<PhysicsProperties>){

        /** Base case, exit. */
        if(node == null){
            return;
        }

        /** For every component on the node. */
        for(let i = 0; i < node.components.length; i++){

            /** Process every other component on the node. */
            for(let c = i + 1; c < node.components.length; c++){
                this.TestCollision(node.components[i].component, node.components[c].component);
            }

            /** Process everything which is currently in the list. AKA on a parent node. */
            for(let c = 0; c < list.length; c++){
                this.TestCollision(node.components[i].component, list[c]);
            }
        }

        /** Add everything to the list, so child nodes can check for collisions against them. */
        for(let i = 0; i < node.components.length; i++){
            list.push(node.components[i].component);
        }

        /** Update all child nodes. */
        this.UpdateRecursive(node.TopLeft, list);
        this.UpdateRecursive(node.BottomLeft, list);
        this.UpdateRecursive(node.TopRight, list);
        this.UpdateRecursive(node.BottomRight, list);

        /** Pop everything off the list to continue upwards. */
        for(let i = 0; i < node.components.length; i++){
            list.pop();
        }
    }

    /** Test a collision between two physics objexts. */
    private TestCollision(a : PhysicsProperties, b : PhysicsProperties)
    {
        let boundsA = a.getBounds();
        let boundsB = b.getBounds();

        let dist = Vector.dist(boundsA.position, boundsB.position);

        // Update the count.
        this.collisionsProcessed++;

        if(dist > boundsA.radius + boundsB.radius){
            return;
        }

        b.processColission(a);
    }

    /** This method is stupid. delete it. */
    private getFittingNode(component : ComponentWrapper) : QuadTreeNode{
        let node = this.root.GetNodeForComponent(component);
        return node;
    }
}

/** A node of the quad tree. */
class QuadTreeNode
{
    /** The child nodes. */
    private readonly cells : Array<QuadTreeNode>;

    /** The maximum depth. */
    private readonly maxDepth : number;

    /** The current depth */
    public readonly depth : number;

    /** The top left corner of the node. */
    public readonly topLeftBound : Vector;

    /** The bottom right corner of the node. */
    public readonly bottomRightBound : Vector;

    /** The center of the node. */
    public readonly centerBound : Vector;

    /** The components attached to the node. */
    public readonly components : Array<ComponentWrapper>

    /** The parent tree node. */
    public readonly parent : QuadTreeNode;

    constructor(depth : number, maxDepth : number, parent : QuadTreeNode, topLeftBound : Vector, bottomRightBound : Vector){
        this.depth = depth;
        this.maxDepth = maxDepth;
        this.cells = new Array(4);
        this.topLeftBound = topLeftBound;
        this.bottomRightBound = bottomRightBound;
        this.centerBound = new Vector((this.topLeftBound.x + this.bottomRightBound.x) / 2, (this.topLeftBound.y + this.bottomRightBound.y) / 2);
        this.components = new Array<ComponentWrapper>();
        this.parent = parent;
    }

    get TopLeft():QuadTreeNode{
        return this.cells[0];
    }

    get BottomLeft():QuadTreeNode{
        return this.cells[1];
    }

    get TopRight():QuadTreeNode{
        return this.cells[2];
    }

    get BottomRight():QuadTreeNode{
        return this.cells[3];
    }

    /** Get the deepest possible node for a component on the tree. 
     * Also prunes the tree if the component has left its node, and the node is empty.
    */
    GetNodeForComponent(wrapper : ComponentWrapper) : QuadTreeNode{
        let bounds = wrapper.component.getBounds();
        let tlNode = this.GetCellIndex(bounds.topLeft());
        let brNode = this.GetCellIndex(bounds.bottomRight());

        /** If we aren't at the max depth, and topleft/bottom right bounds fall within the same index,
         * then pass the responsibility to a child node. */
        if(tlNode == brNode && this.depth < this.maxDepth){
            return this.GetOrCreateQuadTreeNode(tlNode).GetNodeForComponent(wrapper);
        }

        /** If the cell has just entered the current node. Then add to this collection, and prune the old node */
        if(wrapper.node != this)
        {
            this.components.push(wrapper);

            if(wrapper.node != null){
                Helpers.Remove(wrapper.node.components, wrapper);
                wrapper.node.Prune();
            }
        }

        /** Then set this as the current node. */
        wrapper.node = this;
        return this;
    }

    private GetCellIndex(point : Vector){
        let left = point.x < this.centerBound.x;
        let top = point.y < this.centerBound.y;

        // 0 2
        // 1 3
        return (top ? 0 : 1) + (left ? 0 : 2);
    }

    /** Removes the current tree node, if it is empty **/
    private Prune(){
        if(this.components.length > 0 || this.parent == null){
            return;
        }

        this.parent.PruneChild(this);
    }

    /** Removes the provided child node.  */
    private PruneChild(child : QuadTreeNode){
        let index = this.cells.indexOf(child);
        this.cells[index] = null;
        this.Prune();
    }

    /** Gets or creates a new quad tree node. */
    private GetOrCreateQuadTreeNode(index : number) : QuadTreeNode{
        if(this.cells[index] == null){
            this.cells[index] = new QuadTreeNode(
                this.depth + 1,
                this.maxDepth,
                this,
                new Vector(
                    index < 2 ? this.topLeftBound.x : this.centerBound.x,
                    index % 2 == 0 ? this.topLeftBound.y : this.centerBound.y),
                new Vector(
                    index < 2 ? this.centerBound.x : this.bottomRightBound.x,
                    index % 2 == 0 ? this.centerBound.y : this.bottomRightBound.y
                ));
        }

        return this.cells[index];
    }
}

/** Wrapper item used by the quad tree. Maps physics properties to a quad tree node. */
class ComponentWrapper{
    public component : PhysicsProperties;
    public node : QuadTreeNode;
    
    constructor(component : PhysicsProperties, node : QuadTreeNode){
        this.component = component;
        this.node = node;
    }
}

/** Draws the quad tree */
class QuadTreeDrawer extends DrawableGameComponent{ 
    physics : PhysicsProperties;

    private tree : QuadTree;
    constructor(tree : QuadTree){
        super();
        this.tree = tree;
        this.physics = null;
    }

    /** Update. Does nothing, but required by game component. */
    update(context : UpdateContext) : boolean{
        return false;
    }

    /** Draw the quad tree. */
    draw(context : DrawContext){
        context.graphics.beginPath();
        context.graphics.strokeStyle = 'red';
        this.drawRecursive(this.tree.getRoot(), context.graphics);
        context.graphics.closePath();
    }

    /** Draw a quad tree node. And its children. */
    private drawRecursive(node : QuadTreeNode, graphics : CanvasRenderingContext2D){
        if(node == null){
            return;
        }

        this.drawRecursive(node.TopLeft, graphics);
        this.drawRecursive(node.BottomLeft, graphics);

        graphics.strokeRect(node.topLeftBound.x, node.topLeftBound.y, (node.bottomRightBound.x - node.topLeftBound.x), (node.bottomRightBound.y - node.topLeftBound.y));

        this.drawRecursive(node.TopRight, graphics);
        this.drawRecursive(node.BottomRight, graphics);
    }
}

/** Runs update logic, and executes update/draw on components.  */
class GameController
{
    private drawInterval: number;
    private updateInterval: number;

    private graphics : CanvasRenderingContext2D;
    private canvas : HTMLCanvasElement;

    private components : Array<GameComponent>;
    private drawables : Array<DrawableGameComponent>
    private phsyicsController : PhysicsController;

    private previousContext : UpdateContext;

    constructor(canvas: HTMLCanvasElement){
        this.canvas = canvas;
        this.graphics = canvas.getContext("2d");

        this.components = new Array<GameComponent>();
        this.phsyicsController = new PhysicsController(new Vector(this.canvas.width, this.canvas.height));
        this.drawables = new Array<DrawableGameComponent>();

        this.drawables.push(new QuadTreeDrawer(this.phsyicsController.quadTree));
    }

    public run(){
        // The default update context
        this.previousContext = new UpdateContext(0, this.canvas.width, this.canvas.height, Date.now());
        if(!this.drawInterval){
            this.drawInterval = window.setInterval(() => this.draw(), 10);
        }
        if(!this.updateInterval){
            this.updateInterval = window.setInterval(() => this.update(), 10);
        }
    }

    public stop(){
        if(this.drawInterval){
            window.clearInterval(this.drawInterval);
            this.drawInterval = null;
        }
        if(this.updateInterval){
            window.clearInterval(this.updateInterval);
            this.updateInterval = null;
        }
    }

    public addComponent(component : GameComponent){
        this.components.push(component);

        if(component instanceof DrawableGameComponent){
            this.drawables.push(component);
        }

        if(component.physics != null){
            this.phsyicsController.add(component.physics);
        }
    }

    public clear(){
        for(let i = 0; i < this.components.length; i++){
            this.components.pop();
        }
    }

    get UpdateablesCount() : number{
        return this.components.length;
    }

    get DraweablesCount() : number{
        return this.drawables.length;
    }

    get Physics() : PhysicsController{
        return this.phsyicsController;
    }

    private update(){
        let now = Date.now();
        let updateContext = new UpdateContext(now - this.previousContext.currentTime, this.canvas.width, this.canvas.height, now);
        this.previousContext = updateContext;

        this.phsyicsController.update(updateContext);

        for(let i = this.components.length - 1; i >= 0; i--){
            if(this.components[i].update(updateContext)){
                this.components.splice(i, 1);
            }
        }
    }

    private draw(){

        let drawContenxt = new DrawContext(this.graphics);
        this.graphics.fillStyle = 'rgba(100, 100, 100, 0.2)';
        this.graphics.fillRect(0, 0, this.canvas.width, this.canvas.height);

        for(let i = this.drawables.length - 1; i >= 0; i--){
            this.drawables[i].draw(drawContenxt);
        }
    }
}

/** outputs diagnostic data to the screen. */
class Diagnostics extends DrawableGameComponent{

    private readonly gameController : GameController;
    private readonly startPosition : Vector;

    constructor(gameController : GameController){
        super()
        this.gameController = gameController;

        this.startPosition = new Vector(0, 16);
    }

    update(context : UpdateContext) : boolean{
        return false;
    }

    draw(context : DrawContext){
        context.graphics.beginPath();
        context.graphics.font = '16px monospaced'
        context.graphics.fillStyle = 'white';
        context.graphics.fillText("updateables: " + this.gameController.UpdateablesCount, this.startPosition.x, this.startPosition.y);
        context.graphics.fillText("draweables: " + this.gameController.UpdateablesCount, this.startPosition.x, this.startPosition.y + 16);
        context.graphics.fillText("collisions tested: " + this.gameController.Physics.quadTree.collisionsProcessed, this.startPosition.x, this.startPosition.y + 32);
        context.graphics.closePath();
    }    
}

/** Main class. */
class Main {

    private canvas : HTMLCanvasElement;
    private controller : GameController; 

    constructor(parent) {
        this.initializeCanvas(parent);
        this.controller = new GameController(this.canvas);
    }
    run() {
        this.controller.run();
    }
    stop() {
        this.controller.stop();
    }
    initializeTest() {
        this.AddRandomBall(5);
        //window.onkeydown = (event) => {
        //    if(event.charCode === 0){
        //        // Spacebar
        //        this.AddRandomBall();
        //    }
        //}
        this.canvas.onclick = (event) => {
            //let ball = new Ball(new Vector(event.offsetX - 15, event.offsetY - 15), new Vector(), 15, 'red')
            //this.controller.addComponent(ball);
            this.AddRandomBall(10);
        };
    }
    AddRandomBall(count = 20) {
        for (let i = 0; i < count; i++) {
            var ball = Ball.CreateRandom(new Vector(this.canvas.width, this.canvas.height), 2, 4, new Vector(30, 30), new Vector(180, 180));
            this.controller.addComponent(ball);
        }
    }
    EnableDiagnostics() {
        let diagnostic = new Diagnostics(this.controller);
        this.controller.addComponent(diagnostic);
    }
    initializeCanvas(parent) {
        this.canvas = document.createElement('canvas');
        this.canvas.width = parent.clientWidth;
        this.canvas.height = Math.floor(parent.clientWidth * 0.6);
        parent.appendChild(this.canvas);
    }
}
function Run(arg = null) {
    if (null === arg || undefined === arg) {
        arg = document.currentScript.parentElement;
    }
    let m = new Main(arg);
    m.initializeTest();
    m.EnableDiagnostics();
    m.run();
}

Run();
Peter Sulucz - September 14, 18

Sometimes things just make more sense in SQL... Sometimes they don't. Here is a working implementation of the SHA2 algorithm written in T-SQL.

-- If you are here looking for code to actually use in production, here you go, no need to keep reading:

SELECT HASHBYTES('sha2_256', 'The quick brown fox jumps over the lazy dog')

To get things started, SQL doesn't support binary shifts by default. So here are some helper functions to do bit shifting. SHA256 requires a right shift, and a right rotation. (Right rotation in turn requires a left shift). Shift are implemented by doing power of 2 multiplication/division. Every time you multiply by two, you do a single left shift. Every time you divide by two, you do a single right shift.

-- 32 bit unsigned left shift.
CREATE FUNCTION SHL32
(
    @value  BIGINT,
    @amount BIGINT
)
RETURNS BIGINT
AS BEGIN
    RETURN (@value * POWER(CAST(2 AS BIGINT), @amount)) & 0xFFFFFFFF
END
GO

-- 32 bit unsigned right shift.
CREATE FUNCTION SHR32
(
    @value  BIGINT,
    @amount BIGINT
)
RETURNS BIGINT
AS BEGIN
    RETURN (@value / POWER(CAST(2 AS BIGINT), @amount)) & 0xFFFFFFFF
END
GO

-- 32 bit unsigned right rotation
CREATE FUNCTION ROTR32
(
    @value  BIGINT,
    @amount BIGINT
)
RETURNS BIGINT
AS BEGIN
    RETURN (dbo.SHR32(@value, @amount) | dbo.SHL32(@value, 32 - @amount)) & 0xFFFFFFFF
END
GO

Now that we have binary shift helpers, here is a working solution. The initial goal was to create the sproc without using any loops. It turned out to be incredibly difficult, so I did use a single loop in order to calculate the message schedule array.

--
-- SHA256 implementation
--
CREATE PROCEDURE SHA256
(
    @input VARBINARY(MAX)
)
AS BEGIN
    SET NOCOUNT ON
    SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED

    DECLARE @kvalues TABLE
    (
        id INT,
        val BIGINT
    )

    -- Initialize all of the K values
    INSERT INTO @kvalues
    VALUES 
     (0,  0x428a2f98),(1,  0x71374491),(2,  0xb5c0fbcf),(3,  0xe9b5dba5)
    ,(4,  0x3956c25b),(5,  0x59f111f1),(6,  0x923f82a4),(7,  0xab1c5ed5)
    ,(8,  0xd807aa98),(9,  0x12835b01),(10, 0x243185be),(11,0x550c7dc3)
    ,(12, 0x72be5d74),(13, 0x80deb1fe),(14, 0x9bdc06a7),(15, 0xc19bf174)
    ,(16, 0xe49b69c1),(17, 0xefbe4786),(18, 0x0fc19dc6),(19, 0x240ca1cc)
    ,(20, 0x2de92c6f),(21, 0x4a7484aa),(22, 0x5cb0a9dc),(23, 0x76f988da)
    ,(24, 0x983e5152),(25, 0xa831c66d),(26, 0xb00327c8),(27, 0xbf597fc7)
    ,(28, 0xc6e00bf3),(29, 0xd5a79147),(30, 0x06ca6351),(31, 0x14292967)
    ,(32, 0x27b70a85),(33, 0x2e1b2138),(34, 0x4d2c6dfc),(35, 0x53380d13)
    ,(36, 0x650a7354),(37, 0x766a0abb),(38, 0x81c2c92e),(39, 0x92722c85)
    ,(40, 0xa2bfe8a1),(41, 0xa81a664b),(42, 0xc24b8b70),(43, 0xc76c51a3)
    ,(44, 0xd192e819),(45, 0xd6990624),(46, 0xf40e3585),(47, 0x106aa070)
    ,(48, 0x19a4c116),(49, 0x1e376c08),(50, 0x2748774c),(51, 0x34b0bcb5)
    ,(52, 0x391c0cb3),(53, 0x4ed8aa4a),(54, 0x5b9cca4f),(55, 0x682e6ff3)
    ,(56, 0x748f82ee),(57, 0x78a5636f),(58, 0x84c87814),(59, 0x8cc70208)
    ,(60, 0x90befffa),(61, 0xa4506ceb),(62, 0xbef9a3f7),(63, 0xc67178f2)

    DECLARE @hvalues TABLE
    (
        a BIGINT
       ,b BIGINT
       ,c BIGINT
       ,d BIGINT
       ,e BIGINT
       ,f BIGINT
       ,g BIGINT
       ,h BIGINT
    )

    -- Initialize the initial H values
    INSERT INTO @hvalues
    VALUES
    (0x6a09e667
    ,0xbb67ae85
    ,0x3c6ef372
    ,0xa54ff53a
    ,0x510e527f
    ,0x9b05688c
    ,0x1f83d9ab
    ,0x5be0cd19)

    DECLARE @loop INT = 0

    -- Length of the input binary in bytes
    DECLARE @inputLength BIGINT = LEN(@input)

    -- Total length of the binary, including the 1 bit to append to the data, and the 8 byte length of the data
    DECLARE @totalLength BIGINT = @inputLength + 1 + 8

    -- Length that needs to padded with zeros
    DECLARE @padLength BIGINT = 64 - (@totalLength % 64)

    -- If the result is evenly divisible, than we don't need to pad
    SET @padLength = CASE WHEN @padLength = 64 THEN 0 ELSE @padLength END

    -- Declare the array of zeros we need to append, and pad with the right number of zeros.
    DECLARE @zeros VARBINARY(55) = CONVERT(VARBINARY(MAX), REPLICATE(CHAR(0), @padLength))

    -- Create the full length padded binary
    DECLARE @binary VARBINARY(MAX) = @input + 0x80 + @zeros + CONVERT(VARBINARY(8), (@inputLength * 8))

    DECLARE @messageSchedules TABLE
    (
        chunk INT
       ,id    INT
       ,val   BIGINT
    )

    -- Split the data into 4 byte words
    -- Copy 64 bytes (16 words) into each 64 word chunk
    -- The other 48 bits are all zero, they need to be calculated later.
    --
    -- Result:
    -- chunk | id | value
    ----------------------
    --   0   |  0 | 4 BYTES FROM index (0)
    --   0   |  1 | 4 BYTES FROM index (4)
    --          .
    --          .
    --   0   | 15 | 4 BYTES FROM index (60)
    --   0   | 16 | 0x00000000
    --          .
    --          .
    --   0   | 63 | 0x00000000
    --   1   |  0 | 4 BYTES FROM index (64)
    --          .
    --          .
    --   1   | 16 | 0x00000000
    --   1   | 17 | 0x00000000
   ;WITH splitter AS
    (
        SELECT
          0 AS id
         ,1 AS pos
         ,SUBSTRING(@binary, 1, 4) AS val
        UNION ALL
        SELECT
          s.id + 1 AS id
         ,CASE WHEN (((s.id + 1) % 64) < 16) THEN s.pos + 4 ELSE s.pos END
         ,CASE WHEN (((s.id + 1) % 64) < 16) THEN SUBSTRING(@binary, s.pos + 4, 4)
               ELSE 0x00000000
               END AS val
        FROM splitter s
        WHERE s.id + 1 < len(@binary)
    ) 
    INSERT INTO @messageSchedules
    SELECT
        s.id / 64 AS chunk
       ,s.id % 64 AS id
       ,CONVERT(BIGINT, s.val)
    FROM splitter s OPTION (MAXRECURSION 0)

    DECLARE @rows BIGINT = @@ROWCOUNT

    -- Sadly this bit I couldn't figure out how to make more SQL-y yet. 
    -- For every value, you need access to previously updated values in the table,
    -- Which doesn't work, since you cant see all of the values which you have updated.
    -- 
    -- We need to calculate the working values (everything we set to zero above, so anything
    --   with an id larger than 15)
    -- 
    -- for every id 16 <= i < 64
    --    @messageSchedules[i] = 0xFFFFFFFF 
    --              & (@messageSchedules[i-16] 
    --                  + (RIGHTROTATE(@messageSchedules[i-15], 7) ^ RIGHTROTATE(@messageSchedules[i-15], 18) ^ RIGHTSHIFT(@messageSchedules[i-15], 3))
    --                  + @messageSchedules[i-7] 
    --                  + (RIGHTROTATE(@messageSchedules[i-2], 17) ^ RIGHTROTATE(@messageSchedules[i-2], 19) ^ RIGHTSHIFT(@messageSchedules[i-2], 10)))
    SET @loop = 16
    WHILE @loop < @rows * 64
    BEGIN

        UPDATE ws
            SET ws.val = 0xFFFFFFFF 
                    & (ws16.val 
                    + (dbo.ROTR32(ws15.val, 7) 
                        ^ dbo.ROTR32(ws15.val,18) 
                        ^ dbo.SHR32(ws15.val, 3)) 
                    + ws7.val 
                    + (dbo.ROTR32(ws2.val, 17)
                        ^ dbo.ROTR32(ws2.val, 19)
                        ^ dbo.SHR32(ws2.val, 10)))
        FROM @messageSchedules ws
        JOIN @messageSchedules ws16
          ON ws.chunk = ws16.chunk AND ws.id - 16 = ws16.id
        JOIN @messageSchedules ws2
          ON ws.chunk = ws2.chunk AND ws.id - 2 = ws2.id
        JOIN @messageSchedules ws7
          ON ws.chunk = ws7.chunk AND ws.id - 7 = ws7.id
        JOIN @messageSchedules ws15
          ON ws.chunk = ws15.chunk AND ws.id - 15 = ws15.id
        WHERE ws.id >= 16 AND ws.id = @loop

        SET @loop = @loop + 1
    END

    -- This is the meat of it. 
    -- We start with row -1, which is made up of the h values. (ai,bi...hi) store the "initial" h value for the 64 byte set.
    -- a,b,c,d,e,g,h store the working values. They are all of the temp variables
    -- ai,bi,ci...hi store the base value for each 64 byte set of temp variables. At every new set of 64 bytes, we start with ai,bi,ci...
    --  At the end of every 64 bytes (a.id + 1) % 64 = 0, we store the new set of base values so we can add them back in at the end. (a.id + 1) % 64 = 63
   ;WITH abcdefgh AS
    (
        SELECT -1 AS id, a, b, c, d, e, f, g, h, a AS ai, b AS bi, c AS ci, d AS di, e AS ei, f AS fi, g AS gi, h AS hi
        FROM @hvalues

        UNION ALL

        SELECT
            a.id + 1 AS id,
            ((dbo.ROTR32(a.e, 6) ^ dbo.ROTR32(a.e, 11) ^ dbo.ROTR32(a.e, 25))      -- Sigma 1
                + ((a.e & a.f) ^ ((~a.e) & a.g))                                   -- Ch (choice function)
                + a.h                                                              
                + (SELECT val FROM @kvalues WHERE id = ((a.id + 1) % 64))          
                + bc.val                                                           
                + ((a.a & a.b) ^ (a.a & a.c) ^ (a.b & a.c))                        -- Maj (Majority Function)
                + (dbo.ROTR32(a.a, 2) ^ dbo.ROTR32(a.a, 13) ^ dbo.ROTR32(a.a, 22)) -- Sigma 0
                + CASE WHEN (a.id + 1) % 64 = 63 THEN a.ai ELSE 0 END)
                & 0xFFFFFFFF AS a,
            (a.a + CASE WHEN (a.id + 1) % 64 = 63 THEN a.bi ELSE 0 END) & 0xFFFFFFFF AS b,
            (a.b + CASE WHEN (a.id + 1) % 64 = 63 THEN a.ci ELSE 0 END) & 0xFFFFFFFF AS c,
            (a.c + CASE WHEN (a.id + 1) % 64 = 63 THEN a.di ELSE 0 END) & 0xFFFFFFFF AS d,
            (a.d + (dbo.ROTR32(a.e, 6) ^ dbo.ROTR32(a.e, 11) ^ dbo.ROTR32(a.e, 25)) -- Sigma 1
                + ((a.e & a.f) ^ ((~a.e) & a.g))                                    -- Ch (choice function)
                + a.h 
                + (SELECT val FROM @kvalues WHERE id = ((a.id + 1) % 64))
                + bc.val
                + CASE WHEN (a.id + 1) % 64 = 63 THEN a.ei ELSE 0 END)
                & 0xFFFFFFFF AS e,
            (a.e + CASE WHEN (a.id + 1) % 64 = 63 THEN a.fi ELSE 0 END) & 0xFFFFFFFF AS f,
            (a.f + CASE WHEN (a.id + 1) % 64 = 63 THEN a.gi ELSE 0 END) & 0xFFFFFFFF AS g,
            (a.g + CASE WHEN (a.id + 1) % 64 = 63 THEN a.hi ELSE 0 END) & 0xFFFFFFFF AS h
            ,CASE WHEN (a.id + 1) % 64 = 0 THEN a.a ELSE a.ai END
            ,CASE WHEN (a.id + 1) % 64 = 0 THEN a.b ELSE a.bi END
            ,CASE WHEN (a.id + 1) % 64 = 0 THEN a.c ELSE a.ci END
            ,CASE WHEN (a.id + 1) % 64 = 0 THEN a.d ELSE a.di END
            ,CASE WHEN (a.id + 1) % 64 = 0 THEN a.e ELSE a.ei END
            ,CASE WHEN (a.id + 1) % 64 = 0 THEN a.f ELSE a.fi END
            ,CASE WHEN (a.id + 1) % 64 = 0 THEN a.g ELSE a.gi END
            ,CASE WHEN (a.id + 1) % 64 = 0 THEN a.h ELSE a.hi END
        FROM abcdefgh a
        JOIN @messageSchedules bc ON bc.id = ((a.id + 1) % 64) AND bc.chunk = ((a.id + 1) / 64)
        CROSS JOIN @hvalues hv
    )
    SELECT TOP 1
            CONVERT(VARBINARY(4), a)
           + CONVERT(VARBINARY(4), b)
           + CONVERT(VARBINARY(4), c)
           + CONVERT(VARBINARY(4), d)
           + CONVERT(VARBINARY(4), e)
           + CONVERT(VARBINARY(4), f)
           + CONVERT(VARBINARY(4), g)
           + CONVERT(VARBINARY(4), h)
    FROM abcdefgh 
    ORDER BY id DESC OPTION (MAXRECURSION 0)

  END
GO

DECLARE @input VARBINARY(MAX) = CONVERT(VARBINARY(MAX), 'The quick brown fox jumps over the lazy dog')
EXECUTE SHA256 @input = @input -- Should be: 'd7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592'

SET @input = CONVERT(VARBINARY(MAX), '')
EXECUTE SHA256 @input = @input -- Should be: 'e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855'

And there you have it! SHA2 implemented in SQL. Most of the algorithm is implemented in the giant CTE (abcdefgh) at the bottom of the file. If you do it completely procedural-y (while loops), you can just follow the regular Wikipedia (https://en.wikipedia.org/wiki/SHA-2) example and get a pretty clear solution.

--
-- Procedural SHA256 implementation
--
CREATE PROCEDURE SHA256
(
    @input VARBINARY(MAX)
)
AS BEGIN
    SET NOCOUNT ON

    DECLARE @kvalues TABLE
    (
        id INT,
        val BIGINT
    )

    INSERT INTO @kvalues
    VALUES 
     (0,  0x428a2f98),(1,  0x71374491),(2,  0xb5c0fbcf),(3,  0xe9b5dba5)
    ,(4,  0x3956c25b),(5,  0x59f111f1),(6,  0x923f82a4),(7,  0xab1c5ed5)
    ,(8,  0xd807aa98),(9,  0x12835b01),(10, 0x243185be),(11,0x550c7dc3)
    ,(12, 0x72be5d74),(13, 0x80deb1fe),(14, 0x9bdc06a7),(15, 0xc19bf174)
    ,(16, 0xe49b69c1),(17, 0xefbe4786),(18, 0x0fc19dc6),(19, 0x240ca1cc)
    ,(20, 0x2de92c6f),(21, 0x4a7484aa),(22, 0x5cb0a9dc),(23, 0x76f988da)
    ,(24, 0x983e5152),(25, 0xa831c66d),(26, 0xb00327c8),(27, 0xbf597fc7)
    ,(28, 0xc6e00bf3),(29, 0xd5a79147),(30, 0x06ca6351),(31, 0x14292967)
    ,(32, 0x27b70a85),(33, 0x2e1b2138),(34, 0x4d2c6dfc),(35, 0x53380d13)
    ,(36, 0x650a7354),(37, 0x766a0abb),(38, 0x81c2c92e),(39, 0x92722c85)
    ,(40, 0xa2bfe8a1),(41, 0xa81a664b),(42, 0xc24b8b70),(43, 0xc76c51a3)
    ,(44, 0xd192e819),(45, 0xd6990624),(46, 0xf40e3585),(47, 0x106aa070)
    ,(48, 0x19a4c116),(49, 0x1e376c08),(50, 0x2748774c),(51, 0x34b0bcb5)
    ,(52, 0x391c0cb3),(53, 0x4ed8aa4a),(54, 0x5b9cca4f),(55, 0x682e6ff3)
    ,(56, 0x748f82ee),(57, 0x78a5636f),(58, 0x84c87814),(59, 0x8cc70208)
    ,(60, 0x90befffa),(61, 0xa4506ceb),(62, 0xbef9a3f7),(63, 0xc67178f2)

    DECLARE @hvalues TABLE
    (
        id INT,
        val BIGINT
    )

    INSERT INTO @hvalues
    VALUES
     (0, 0x6a09e667)
    ,(1, 0xbb67ae85)
    ,(2, 0x3c6ef372)
    ,(3, 0xa54ff53a)
    ,(4, 0x510e527f)
    ,(5, 0x9b05688c)
    ,(6, 0x1f83d9ab)
    ,(7, 0x5be0cd19)

    -- Initialize temp variables
    DECLARE @a BIGINT
    DECLARE @b BIGINT
    DECLARE @c BIGINT
    DECLARE @d BIGINT
    DECLARE @e BIGINT
    DECLARE @f BIGINT
    DECLARE @g BIGINT
    DECLARE @h BIGINT
    DECLARE @s1 BIGINT
    DECLARE @s0 BIGINT
    DECLARE @ch BIGINT
    DECLARE @maj BIGINT
    DECLARE @temp1 BIGINT
    DECLARE @temp2 BIGINT
    DECLARE @loop INT

    -- Length of the input binary in bytes
    DECLARE @inputLength BIGINT = LEN(@input)

    -- Total length of the binary, including the 1 bit to append to the data, and the 8 byte length of the data
    DECLARE @totalLength BIGINT = @inputLength + 1 + 8

    -- Length that needs to padded with zeros
    DECLARE @padLength BIGINT = 64 - (@totalLength % 64)

    -- If the result is evenly divisible, than we don't need to pad
    SET @padLength = CASE WHEN @padLength = 64 THEN 0 ELSE @padLength END

    -- Declare the array of zeros we need to append, and pad with the right number of zeros.
    DECLARE @zeros VARBINARY(55) = CONVERT(VARBINARY(MAX), REPLICATE(CHAR(0), @padLength))

    -- Create the full length padded binary
    DECLARE @binary VARBINARY(MAX) = @input + 0x80 + @zeros + CONVERT(VARBINARY(8), (@inputLength * 8))

    DECLARE @allDataLoop INT = 0
    DECLARE @binLength INT = DATALENGTH(@binary)

    DECLARE @messageSchedule TABLE
    (
        id INT,
        val BIGINT
    )

    WHILE (@allDataLoop <> @binLength)
    BEGIN
        DELETE FROM @messageSchedule

        -- Get all of the working bytes. 
       ;WITH cte AS
        (
            SELECT
                0 AS id
               ,SUBSTRING(@binary, @allDataLoop + 0 + 1, 4) AS val

            UNION ALL
        
            SELECT
                c.id + 1 AS id
               ,SUBSTRING(@binary, @allDataLoop + ((c.id + 1) * 4) + 1, 4) AS val
            FROM cte AS c
            WHERE c.id < 15
        )
        INSERT INTO @messageSchedule
        SELECT
          id,
          val
        FROM cte

        -- Calculate the values with indicies larger than 16 in the set of working bytes
        SET @loop = 16
        WHILE (@loop < 64)
        BEGIN
            INSERT INTO @messageSchedule
            SELECT
                @loop AS id
               ,0xFFFFFFFF & (ws16.val + (dbo.ROTR32(ws15.val, 7) ^ dbo.ROTR32(ws15.val,18) ^ dbo.SHR32(ws15.val, 3)) + ws7.val + (dbo.ROTR32(ws2.val, 17) ^ dbo.ROTR32(ws2.val, 19) ^ dbo.SHR32(ws2.val, 10))) AS val
            FROM @messageSchedule ws15
            JOIN @messageSchedule ws2
              ON ws2.id = @loop-2
            JOIN @messageSchedule ws16
              ON ws16.id = @loop-16
            JOIN @messageSchedule ws7
              ON ws7.id = @loop-7
            WHERE ws15.id = @loop-15

            SET @loop = @loop + 1
        END

        -- Initialize the temp variables
        SELECT @a = val FROM @hvalues WHERE id = 0
        SELECT @b = val FROM @hvalues WHERE id = 1
        SELECT @c = val FROM @hvalues WHERE id = 2
        SELECT @d = val FROM @hvalues WHERE id = 3
        SELECT @e = val FROM @hvalues WHERE id = 4
        SELECT @f = val FROM @hvalues WHERE id = 5
        SELECT @g = val FROM @hvalues WHERE id = 6
        SELECT @h = val FROM @hvalues WHERE id = 7

        SET @loop = 0
        WHILE (@loop < 64)
        BEGIN
            SET @s1 = (dbo.ROTR32(@e, 6) ^ dbo.ROTR32(@e, 11) ^ dbo.ROTR32(@e, 25)) & 0xFFFFFFFF -- Sigma 1
            SET @ch = ((@e & @f) ^ ((~@e) & @g)) & 0xFFFFFFFF                                    -- Ch (choice function)
            SET @temp1 = (@h + @s1 + @ch + (SELECT val FROM @kvalues WHERE id = @loop) + (SELECT val FROM @messageSchedule WHERE id = @loop)) & 0xFFFFFFFF

            SET @s0 = (dbo.ROTR32(@a, 2) ^ dbo.ROTR32(@a, 13) ^ dbo.ROTR32(@a, 22)) & 0xFFFFFFFF -- Sigma 0
            SET @maj = (@a & @b) ^ (@a & @c) ^ (@b & @c)                                         -- Maj (Majority Function)
            SET @temp2 = (@s0 + @maj) & 0xFFFFFFFF

            SET @h = @g
            SET @g = @f
            SET @f = @e
            SET @e = (@d + @temp1) & 0xFFFFFFFF
            SET @d = @c
            SET @c = @b
            SET @b = @a
            SET @a = (@temp1 + @temp2) & 0xFFFFFFFF

            SET @loop = @loop + 1
        END

        -- Update the base values
        UPDATE @hvalues SET val = (val + @a) & 0xFFFFFFFF WHERE id = 0 
        UPDATE @hvalues SET val = (val + @b) & 0xFFFFFFFF WHERE id = 1
        UPDATE @hvalues SET val = (val + @c) & 0xFFFFFFFF WHERE id = 2
        UPDATE @hvalues SET val = (val + @d) & 0xFFFFFFFF WHERE id = 3
        UPDATE @hvalues SET val = (val + @e) & 0xFFFFFFFF WHERE id = 4
        UPDATE @hvalues SET val = (val + @f) & 0xFFFFFFFF WHERE id = 5
        UPDATE @hvalues SET val = (val + @g) & 0xFFFFFFFF WHERE id = 6
        UPDATE @hvalues SET val = (val + @h) & 0xFFFFFFFF WHERE id = 7

        SET @allDataLoop = @allDataLoop + 64
    END

    DECLARE @result VARBINARY(MAX) = 0x
    SELECT @result += CONVERT(VARBINARY(4), val) FROM @hvalues
    SELECT @result
END
GO

DECLARE @input VARBINARY(MAX) = CONVERT(VARBINARY(MAX), 'The quick brown fox jumps over the lazy dog')
EXECUTE SHA256 @input = @input -- Should be: 'd7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592'

SET @input = CONVERT(VARBINARY(MAX), '')
EXECUTE SHA256 @input = @input -- Should be: 'e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855'

Clearly not as cool, but the procedural solution is pretty much textbook and much easier to follow.

Peter Sulucz - July 31, 18

Welcome to the msbuild cheat sheet. This is a list of some of the things I always need to search for when I am creating an MSBuild project .props/.targets file. The cheat sheet is in the form of a .proj file, which can be executed by MSBuild.

If you're ever having troubles with MSBuild, try "msbuild /verbosity:diagnostic", which will make MSBuild print out its entire knowledge of the world.

<Project xmlns="http://schemas.microsoft.com/developer/msbuild/2003">

    <!--
        How to define a variable.
            Just stick a new node in a property group.
    -->
    <PropertyGroup>
        <!-- This node in a property group will define a variable -->
        <TestVariable>Test Variable Value</TestVariable>
        
        <!-- Adding a condition, which checks if the variable is already defined,
             will allow you to override the variable in projects. 
             If the variable is not defined, it will evaulate to an empty string
             within the condition and be set with the value defined here.-->
        <TestVariableWithOverride Condition="'$(TestVariableWithOverride)' == ''">Test override.</TestVariableWithOverride>
    </PropertyGroup>

    <Target Name="main" DependsOnTargets="PrintMyVariables;PrintMSBuildVariables;Conditions;PrintPropertyFunctions;PrintOutBatching">
        <!-- Msbuild will process the first target in the file by default.
            By creating this target, and making it depend on the two following targets,
            we can ensure that they will all be executed
            -->
    </Target>

    <!--
        How to print a message.
    -->
    <Target Name="PrintMyVariables">
        <!-- Prints a basic message -->
        <Message Text="Here is my message.."></Message>
        
        <!-- Message importance. How messages are shown can change with the logger being used.
        These examples use the default console logger.-->
        
        <!-- Shows with atleast (Normal) verbosity -->
        <Message Text="Low importance" Importance="Low" />
        
        <!-- Shows with atleast (Normal) verbosity -->
        <Message Text="Normal importance (This is the default)" Importance="Normal" />
        
        <!-- Shows with atleast (Minimal) verbosity -->
        <Message Text="High importance" Importance="High" />
        
        <!-- Interpolates the value of the test variable into the string. -->
        <Message Text="My test variable: $(TestVariable)" />
    </Target>
    
    <!--
        Standard msbuild variables.
    -->
    <Target Name="PrintMSBuildVariables">
        <Message Text="MSBuildAssemblyVersion               -> '$(MSBuildAssemblyVersion)'             " />
        
        <!-- The absolute path of the folder where the MSBuild binaries that are currently being used are located -->
        <Message Text="MSBuildBinPath                       -> '$(MSBuildBinPath)'                     " />
        
        <!-- The path of the MSBuild subfolder under the \Program Files or \Program Files (x86) folder.
        This path always points to the 32-bit \Program Files folder on a 32-bit machine and \Program Files (x86)
        on a 64-bit machine. These two properties are the same-->
        <Message Text="MSBuildExtensionsPath                -> '$(MSBuildExtensionsPath)'              " />
        <Message Text="MSBuildExtensionsPath32              -> '$(MSBuildExtensionsPath32)'            " />
        
        <!-- The path of the MSBuild subfolder under the \Program Files folder.
        For a 64-bit machine, this path always points to the \Program Files folder.
        For a 32-bit machine, this path is blank. -->
        <Message Text="MSBuildExtensionsPath64              -> '$(MSBuildExtensionsPath64)'            " />
        
        <!-- Paths to the .net framework folders, if they are installed -->
        <Message Text="MSBuildFrameworkToolsPath            -> '$(MSBuildFrameworkToolsPath)'          " />
        <Message Text="MSBuildFrameworkToolsPath32          -> '$(MSBuildFrameworkToolsPath32)'        " />
        <Message Text="MSBuildFrameworkToolsPath64          -> '$(MSBuildFrameworkToolsPath64)'        " />
        <Message Text="MSBuildFrameworkToolsRoot            -> '$(MSBuildFrameworkToolsRoot)'          " />
        
        
        <Message Text="MSBuildLoadMicrosoftTargetsReadOnly  -> '$(MSBuildLoadMicrosoftTargetsReadOnly)'" />
        
        <!-- The maximum number of concurrent processes that are used when building.
        This is the value that you specified for /maxcpucount on the command line.
        If you specified /maxcpucount without specifying a value, then MSBuildNodeCount
        specifies the number of processors in the computer. -->
        <Message Text="MSBuildNodeCount                     -> '$(MSBuildNodeCount)'                   " />

        <Message Text="MSBuildProgramFiles32                -> '$(MSBuildProgramFiles32)'              " />
        <Message Text="MSBuildProjectDirectory              -> '$(MSBuildProjectDirectory)'            " />
        <Message Text="MSBuildProjectDirectoryNoRoot        -> '$(MSBuildProjectDirectoryNoRoot)'      " />
        <Message Text="MSBuildProjectExtension              -> '$(MSBuildProjectExtension)'            " />
        <Message Text="MSBuildProjectFile                   -> '$(MSBuildProjectFile)'                 " />
        <Message Text="MSBuildProjectFullPath               -> '$(MSBuildProjectFullPath)'             " />
        <Message Text="MSBuildProjectName                   -> '$(MSBuildProjectName)'                 " />
        <Message Text="MSBuildRuntimeType                   -> '$(MSBuildRuntimeType)'                 " />
        <Message Text="MSBuildRuntimeVersion                -> '$(MSBuildRuntimeVersion)'              " />
        <Message Text="MSBuildSDKsPath                      -> '$(MSBuildSDKsPath)'                    " />
        <Message Text="MSBuildStartupDirectory              -> '$(MSBuildStartupDirectory)'            " />
        
        <!-- Gets the current file. -->
        <Message Text="MSBuildThisFile                      -> '$(MSBuildThisFile)'                    " />
       
        <!-- Gets the current file directory. -->
        <Message Text="MSBuildThisFileDirectory             -> '$(MSBuildThisFileDirectory)'           " />

        <Message Text="MSBuildThisFileDirectoryNoRoot       -> '$(MSBuildThisFileDirectoryNoRoot)'     " />
        <Message Text="MSBuildThisFileExtension             -> '$(MSBuildThisFileExtension)'           " />
        <Message Text="MSBuildThisFileFullPath              -> '$(MSBuildThisFileFullPath)'            " />
        <Message Text="MSBuildThisFileName                  -> '$(MSBuildThisFileName)'                " />
        <Message Text="MSBuildToolsPath                     -> '$(MSBuildToolsPath)'                   " />
        <Message Text="MSBuildToolsPath32                   -> '$(MSBuildToolsPath32)'                 " />
        <Message Text="MSBuildToolsPath64                   -> '$(MSBuildToolsPath64)'                 " />
        <Message Text="MSBuildToolsRoot                     -> '$(MSBuildToolsRoot)'                   " />
        <Message Text="MSBuildToolsVersion                  -> '$(MSBuildToolsVersion)'                " />
        <Message Text="MSBuildUserExtensionsPath            -> '$(MSBuildUserExtensionsPath)'          " />
        <Message Text="MSBuildVersion                       -> '$(MSBuildVersion)'                     " />
    </Target>

    <!-- Condition tests. -->
    <Target Name="Conditions">
        <!-- String equality -->
        <Message Condition="yellow == 'yellow'"     Text="Quotes not required for one word.    -> yellow == 'yellow" />
        <Message Condition="YELLOW == yellow"       Text="Case is insensitive.                 -> YELLOW == yellow" />
        <Message Condition="red != blue"            Text="Not equals works too.                -> red != blue" />
        
        <!-- String unary operators -->
        <Message Condition="Exists('$(MSBuildProjectFullPath)')" Text="Checks if the file or folder exists. -> Exists('$(MSBuildProjectFullPath)')" />
        <Message Condition="HasTrailingSlash('test\')"           Text="Checks for a trailing slash /.       -> HasTrailingSlash('test\')" />

        <!-- Logical operators -->
        <message Condition="true AND true"          Text="AND operator                         -> true AND true" />
        <message Condition="true OR false"          Text="OR operator                          -> true OR false" />
        <message Condition="!false"                 Text="NOT operator                         -> !false" />
        <message Condition="(true AND false) OR true"   Text="Grouping works                       -> (true AND false) OR true" />
    </Target>
    
    <!-- Property Functions (You can nest them)-->
    <Target Name="PrintPropertyFunctions">
        <!-- There are lots of these. Most of them are just totally regular .net classes. Thanks MSDN-->
        <Message Text="The syntax to get a property is [Class]::Property. For example $([System.Int32]::MaxValue)" />
        
        <Message Text="Any method or property from          -> System.Byte                                  " />
        <Message Text="Any method or property from          -> System.Char                                  " />
        <Message Text="Any method or property from          -> System.Convert                               " />
        <Message Text="Any method or property from          -> System.DateTime                              " />
        <Message Text="Any method or property from          -> System.Decimal                               " />
        <Message Text="Any method or property from          -> System.Double                                " />
        <Message Text="Any method or property from          -> System.Enum                                  " />
        <Message Text="Any method or property from          -> System.Guid                                  " />
        <Message Text="Any method or property from          -> System.Int16                                 " />
        <Message Text="Any method or property from          -> System.Int32                                 " />
        <Message Text="Any method or property from          -> System.Int64                                 " />
        <Message Text="Any method or property from          -> System.IO.Path                               " />
        <Message Text="Any method or property from          -> System.Math                                  " />
        <Message Text="Any method or property from          -> System.UInt16                                " />
        <Message Text="Any method or property from          -> System.UInt32                                " />
        <Message Text="Any method or property from          -> System.UInt64                                " />
        <Message Text="Any method or property from          -> System.SByte                                 " />
        <Message Text="Any method or property from          -> System.Single                                " />
        <Message Text="Any method or property from          -> System.String                                " />
        <Message Text="Any method or property from          -> System.StringComparer                        " />
        <Message Text="Any method or property from          -> System.TimeSpan                              " />
        <Message Text="Any method or property from          -> System.Text.RegularExpressions.Regex         " />
        <Message Text="Any method or property from          -> Microsoft.Build.Utilities.ToolLocationHelper " />

        <Message Text="These methods work too               -> System.Environment::CommandLine                " />
        <Message Text="These methods work too               -> System.Environment::ExpandEnvironmentVariables " />
        <Message Text="These methods work too               -> System.Environment::GetEnvironmentVariable     " />
        <Message Text="These methods work too               -> System.Environment::GetEnvironmentVariables    " />
        <Message Text="These methods work too               -> System.Environment::GetFolderPath              " />
        <Message Text="These methods work too               -> System.Environment::GetLogicalDrives           " />
        <Message Text="These methods work too               -> System.IO.Directory::GetDirectories            " />
        <Message Text="These methods work too               -> System.IO.Directory::GetFiles                  " />
        <Message Text="These methods work too               -> System.IO.Directory::GetLastAccessTime         " />
        <Message Text="These methods work too               -> System.IO.Directory::GetLastWriteTime          " />
        <Message Text="These methods work too               -> System.IO.Directory::GetParent                 " />
        <Message Text="These methods work too               -> System.IO.File::Exists                         " />
        <Message Text="These methods work too               -> System.IO.File::GetCreationTime                " />
        <Message Text="These methods work too               -> System.IO.File::GetAttributes                  " />
        <Message Text="These methods work too               -> System.IO.File::GetLastAccessTime              " />
        <Message Text="These methods work too               -> System.IO.File::GetLastWriteTime               " />
        <Message Text="These methods work too               -> System.IO.File::ReadAllText                    " />
    
        <!-- Combining Paths
        This can be a little annoying, because you're never really sure if a variable includes the final backslash.
        To Get around this issue, you can use the regular Path.combine -->
        <Message Text="System.IO.Path::Combine              -> $([System.IO.Path]::Combine('C:\This\Is\How\', 'You\Combine\Paths', 'to\a\file.txt'))" />
        
        <!-- Special MSBuild operators -->
        <Message Text="Add two values(double/int/long)      -> [MSBuild]::Add(1.5, 2.5) = $([MSBuild]::Add(1.5, 2.5))" />
        <Message Text="Subtract two values(double/int/long) -> [MSBuild]::Subtract(7, 9) = $([MSBuild]::Subtract(7, 9))" />
        <Message Text="Multiply two values(double/int/long) -> [MSBuild]::Multiply(5, 4) = $([MSBuild]::Multiply(5, 4))" />
        <Message Text="Divide two values(double/int/long)   -> [MSBuild]::Divide(8, 2) = $([MSBuild]::Divide(8, 2))" />
        <Message Text="Modulo two values(double/int/long)   -> [MSBuild]::Modulo(42, 5) = $([MSBuild]::Modulo(42, 5))" />
        
        <!-- Haven't exactly figured out where to use these escape functions yet.. -->
        <Message Text="Escape a string                      -> [MSBuild]::Escape(' a% b$ c@ d; e? f* ') = $([MSBuild]::Escape(' a% b$ c@ d; e? f* '))" />
        <Message Text="Unescape a string                    -> [MSBuild]::Unescape('%25 %24 %40 %27 %3B %3F %2A') = $([MSBuild]::Unescape('%25 %24 %40 %27 %3B %3F %2A'))" />
        
        <!-- Bitwise operations are supported -->
        <Message Text="Bitwise Or                           -> [MSBuild]::BitwiseOr(1, 2) = $([MSBuild]::BitwiseOr(1, 2))" />
        <Message Text="Bitwise And                          -> [MSBuild]::BitwiseAnd(3, 1) = $([MSBuild]::BitwiseAnd(3, 1))" />
        <Message Text="Bitwise Xor                          -> [MSBuild]::BitwiseXor(1, 1) = $([MSBuild]::BitwiseXor(1, 1))" />
        <Message Text="Bitwise Not                          -> [MSBuild]::BitwiseNot(0) = $([MSBuild]::BitwiseNot(0))" />
        
        <!-- Nested example -->
        <Message Text="Nested example                       -> [MSBuild]::Subtract([MSBuild]::Add(10, 5), 7) = $([MSBuild]::Subtract([MSBuild]::Add(10, 5), 7)" />
    </Target>

    <!-- Test directory-->
    <PropertyGroup> 
        <!-- Test directory-->
        <TestDirectory>$([System.IO.Path]::Combine('$(TMP)', 'bftestfiles\'))</TestDirectory>
    </PropertyGroup>

    <!-- Create a directory -->
    <Target Name="CreateTestDirectory">
        <MakeDir Directories="$(TestDirectory)" />
    </Target>
    
    <!-- Delete a directory, along with all files inside -->
    <Target Name="DeleteTestDirectory" AfterTargets="PrintOutBatching">
        <RemoveDir Directories="$(TestDirectory)" />
    </Target>

    <!-- Write to a text file -->
    <Target Name="CreateTestFiles" DependsOnTargets="CreateTestDirectory">
        <WriteLinesToFile File="$([System.IO.Path]::Combine('$(TestDirectory)', '1-test.txt'))" Overwrite="True" Lines="Test 1" />
        <WriteLinesToFile File="$([System.IO.Path]::Combine('$(TestDirectory)', '2-test.txt'))" Lines="Test 2" />
    </Target>

    <!-- Perform an action for each item in a list -->
    <Target Name="PrintOutBatching" DependsOnTargets="CreateTestFiles">
    
        <!-- An item group which finds the .txt files we created in the test folder.
        A dynamic item group like this one, is evalued when the task is run.
        An item group declared directly under the project is evaluated when the project is loaded.
        Any files which are created during the build would only show up in a dynamic item group. -->
        <ItemGroup>
            <WindowsDll Include="$(TMP)\**\*test.txt"></WindowsDll>
        </ItemGroup>

        <!-- Each one of these is executed for each unique value found. Because of the '%' sign. 
        Notice that identical values like RootDir are only printed once.-->
        <Message Text="Full path                            ->  FullPath = %(WindowsDll.FullPath)" />
        <Message Text="Root dir                             ->  RootDir = %(WindowsDll.RootDir)" />
        <Message Text="The file name                        ->  Filename = %(WindowsDll.Filename)" />
        <Message Text="The extension                        ->  Extension = %(WindowsDll.Extension)" />
        <Message Text="The relative directory (include path)->  RelativeDir = %(WindowsDll.RelativeDir)" />
        <Message Text="The full file directory              ->  Directory = %(WindowsDll.Directory)" />
        <Message Text="Recursive directory (only if \**\)   ->  RecursiveDir = %(WindowsDll.RecursiveDir)" />
        <Message Text="Identity (Path from include)         ->  Identity = %(WindowsDll.Identity)" />
        <Message Text="The modified time                    ->  ModifiedTime = %(WindowsDll.ModifiedTime)" />
        <Message Text="The created time                     ->  CreatedTime = %(WindowsDll.CreatedTime)" />
        <Message Text="The accessed time                    ->  AccessedTime = %(WindowsDll.AccessedTime)" />
    </Target>
</Project>
Peter Sulucz - July 10, 18

Here it is, what everyone has been waiting for.. an MS build implementation of fizz buzz.

<Project DefaultTargets="CleanupRecur"
    xmlns="http://schemas.microsoft.com/developer/msbuild/2003">  
    
    <PropertyGroup>
        <Currval Condition="'$(Currval)' == ''">1</Currval>
        <FileBaseName>$(Targets)</FileBaseName>
        <FileBaseName Condition="'$(FileBaseName)' == ''">recurfile</FileBaseName>
        <NextMsbuildFile>$(FileBaseName)-$(Currval).proj</NextMsbuildFile>
        <NextIndex>$([MSBuild]::Add($(Currval), 1))</NextIndex>
        <Mod3 Condition="$([MSBuild]::Modulo($(Currval), 3)) == 0">true</Mod3>
        <Mod5 Condition="$([MSBuild]::Modulo($(Currval), 5)) == 0">true</Mod5>
    </PropertyGroup>

    <Target Name="CopyFile">
        <Message Text = "$(NextIndex)" />
        <Copy Condition="$(Currval) &lt; 100"
        SourceFiles="$(MSBuildProjectFile)"
        DestinationFiles="$(NextMsbuildFile)" />
    </Target>
    
    <Target Name="Fizz" DependsOnTargets="CopyFile">
        <Message Condition="'$(Mod3)' == 'true' AND '$(Mod5)' != 'true'" Text="Fizz" Importance="high"/>
        <Message Condition="'$(Mod5)' == 'true' AND '$(Mod3)' != 'true'" Text="Buzz" Importance="high"/>
        <Message Condition="'$(Mod3)' == 'true' AND '$(Mod5)' == 'true'" Text="FizzBuzz" Importance="high"/>
        <Message Condition="'$(Mod3)' != 'true' AND '$(Mod5)' != 'true'" Text="$(Currval)" Importance="high"/>
        <MSBuild Condition="$(Currval) &lt; 100" Projects="$(NextMsbuildFile)" Targets="CleanupRecur" Properties="Currval=$(NextIndex)"></MSBuild>
    </Target>

    <Target Name="CleanupRecur" DependsOnTargets="Fizz">
        <Delete Files="$(NextMsbuildFile)" />
    </Target>
</Project>

You can run it as follows.

# Pass the minimal flag to avoid a bunch of extra msbuild output
msbuild /v:minimal .\fizz.proj
# The project works by getting the current value of the count from an environment variable "Currval".
# It evaluates the mod3 and mod5 of Currval

# It then makes a copy of its own project file, to avoid MSBuild detecting any circular dependencies
# It than executes MSBuild on the new project file, since it is a dependency, passing the incremented environment variable to the new project

# Then it cleans up the newly copied file

There you have it. A working implementation of fizzbuzz using MSBuild.

Peter Sulucz - June 25, 18

Here is a powershell example of converting an expression in postfix notation into infix notation. A little background on postfix notation, is that the operators follow the operands. For example "(1 + 2) = 1 2 +". Postfix is much easier to interpret for a computer, since values are processed as they are used, and their is no need for parenthesis.

#
# Here is an example. 
# Postfix String: 1 2 - 3 * 4 * 5 - = -17
# Infix String:   ((((1 - 2) * 3) * 4) - 5) = -17
#

Here is an example of the algorithm followed by this example.

#
# Algorithm: For every item 'x' in the string
#    x -> number: push it onto the stack
#    x -> operator: pop two items of the stack, join them with x,
#                   then push the result back onto the stack.
#                   EX: "(stack.pop() x stack.pop())"
#
# Given the string "1 2 - 3 * 4 * 5 -"
#
# We use a stack to keep track of our progress.
#
# First item in the string = '1'
# '1' is a number so push it onto the stack
#
#  stack                  remaining: 2 - 3 * 4 * 5 -
#    1
#
# Next item in the string = '2'
# '2' is a number so push it onto the stack
#
#  stack                  remaining: - 3 * 4 * 5 -
#    2
#    1
#
# Next item in the string = '-'
# '-' is an operator, so pop two items of the stack, join, then push
#
#  stack                  remaining: 3 * 4 * 5 -
# (1 + 2)
#
# Next item in the string = '3'
# '3' is a number so push it onto the stack
#
#  stack                  remaining: * 4 * 5 -
#    3
# (1 + 2)
#
# Next item in the string = '*'
# '*' is an operator, so pop two items of the stack, join, then push
#
#  stack                  remaining: 4 * 5 -
# ((1 + 2) * 3)
#
# Next item in the string = '4'
# '4' is a number so push it onto the stack
#
#  stack                  remaining: * 5 -
#    4
# ((1 + 2) * 3)
#
# Next item in the string = '*'
# '*' is an operator, so pop two items of the stack, join, then push
#
#  stack                  remaining: 5 -
# ((1 + 2) * 3) * 4)
#
# Next item in the string = '5'
# '5' is a number so push it onto the stack
#
#  stack                  remaining: -
#    5
# ((1 + 2) * 3) * 4)
#
# Next item in the string = '-'
# '-' is an operator, so pop two items of the stack, join, then push

#  stack                  remaining:
# (((1 + 2) * 3) * 4) - 5)
#
# Now we just pop the last item off the stack, and we have our answer.

Here is the powershell which makes this all possible.

function PostfixTo-Infix
{
    param
    (
        [Parameter(Mandatory=$true)][string]$Postfix
    )
    process
    {
        # Split the string into the individual peices
        $values = $Postfix.Split(' ', [StringSplitOptions]::RemoveEmptyEntries)

        # Stack to store the values as they are being parsed
        $stack = [System.Collections.Generic.Stack[string]]::new()

        foreach($val in $values)
        {
            # Try to parse the value
            $intvalue = 0
            if([int]::TryParse($val, [ref]$intvalue))
            {
                # If the value is an integer, add it to the stack
                $stack.Push($val)

                # Then continue on
                continue;
            }
            else
            {
                # The value is an operator, so pop off the previous two values,
                # And join them with the operator. 
                $b = $stack.Pop();
                $a = $stack.Pop();

                # Then push the result onto the stack
                $stack.Push("($a $val $b)")
            }
        }

        # The final item on the stack must be our result.
        return $stack.Pop()
    }
}

There you have it. Results look like this:

PostfixTo-Infix '1 2 - 3 4 * 5 + *'
((1 - 2) * ((3 * 4) + 5))

In the spirit of good programming, here is a code golfy powershell one liner which also works. It mostly uses the same principal, but uses a hashtable as the stack. One caveat is that it prints all results out backwards, which is fine because there are parenthesis everywhere.

function PostfixTo-InfixGolf
{
    param
    (
        [Parameter(Mandatory=$true)][string]$p
    )
    process
    {
        $s=@{};$a=0;switch -regex($p.Split(' ')){'\d'{$s[$a++]=$_}default{$t="($($s[--$a]) $_ $($s[--$a]))";$s[$a++]=$t}};$s[--$a]
    }
}
Peter Sulucz - June 24, 18

Here are some instructions on how to deploy a NDIS virtual switch extension to a Hyper-V Virtual Switch. This will save you some headaches during the driver deployment and validation process. Of course, before doing any of this, make sure you have a test host set up in Test Mode. "bcdedit /set testsigning on" Then reboot.

First comes first, after creating a basic NDIS lightweight filter driver project, make sure that your INF file is configured correctly. Here is a basic example, which will create a modifying filter driver which build for x64, and attaches only to virtual switches.

;-------------------------------------------------------------------------
; basicndis.INF -- NDIS LightWeight Filter Driver
;-------------------------------------------------------------------------

[version]
; Do not change these values
Signature       = "$Windows NT$"
Class           = NetService
ClassGUID       = {4D36E974-E325-11CE-BFC1-08002BE10318}
Provider        = %Badflyer%
DriverVer       = 
CatalogFile     = basicndis.cat


[Manufacturer]
%Badflyer%=MSFT,NTx86,NTamd64,NTarm,NTarm64

; BADFLYER_basicndis can be used with netcfg.exe to install/uninstall the driver.
[MSFT.NTx86]
%basicndis_Desc%=Install, BADFLYER_basicndis

[MSFT.NTamd64]
%basicndis_Desc%=Install, BADFLYER_basicndis

[MSFT.NTarm]
%basicndis_Desc%=Install, BADFLYER_basicndis

[MSFT.NTarm64]
%basicndis_Desc%=Install, BADFLYER_basicndis

;-------------------------------------------------------------------------
; Installation Section
;-------------------------------------------------------------------------
[Install]
AddReg=Inst_Ndi
; All LWFs must include the 0x40000 bit (NCF_LW_FILTER).
Characteristics=0x40000

; This must be a random, unique value.
; FILTER_UNIQUE_NAME in filter.h must match this GUID identically.
; Both should have {curly braces}.
NetCfgInstanceId="{3ca735b3-e816-470b-905e-9d5097241c74}"

Copyfiles = basicndis.copyfiles.sys

[SourceDisksNames]
1=%basicndis_Desc%,"",,

[SourceDisksFiles]
basicndis.sys=1

[DestinationDirs]
DefaultDestDir=12
basicndis.copyfiles.sys=12

[basicndis.copyfiles.sys]
basicndis.sys,,,2


;-------------------------------------------------------------------------
; Ndi installation support
;-------------------------------------------------------------------------
[Inst_Ndi]
HKR, Ndi,Service,,"basicndis"
HKR, Ndi,CoServices,0x00010000,"basicndis"
HKR, Ndi,HelpText,,%basicndis_HelpText%

HKR, Ndi,FilterClass,, "ms_switch_filter"
; TODO: Specify whether you have a Modifying or Monitoring filter.
; For a Monitoring filter, use this:
;     HKR, Ndi,FilterType,0x00010001, 1 ; Monitoring filter
; For a Modifying filter, use this:
;     HKR, Ndi,FilterType,0x00010001, 2 ; Modifying filter
HKR, Ndi,FilterType,0x00010001,2
; Do not change these values. These are required for a vswitch filter driver.
HKR, Ndi\Interfaces,UpperRange,,"noupper"
HKR, Ndi\Interfaces,LowerRange,,"nolower"
; In order to work with the virtual switch, you must include "vmnetextension". 
; Can also include "ethernet" to work on regular network stacks.
HKR, Ndi\Interfaces, FilterMediaTypes,,"vmnetextension"
; TODO: Specify whether you have a Mandatory or Optional filter
; For a Mandatory filter, use this:
;     HKR, Ndi,FilterRunType,0x00010001, 1 ; Mandatory filter
; For an Optional filter, use this:
;     HKR, Ndi,FilterRunType,0x00010001, 2 ; Optional filter
; Optional filters will allow the network stack on continue working if the filter is not.
HKR, Ndi,FilterRunType,0x00010001, 2 ; Optional filter

;-------------------------------------------------------------------------
; Service installation support
;-------------------------------------------------------------------------
[Install.Services]
; 0x800 Means to start the service automatically after installation. Remove it if you do not want that.
AddService=basicndis,0x800,basicndis_Service_Inst

[basicndis_Service_Inst]
DisplayName     = %basicndis_Desc%
ServiceType     = 1 ;SERVICE_KERNEL_DRIVER
; Typically you will want your filter driver to start with SERVICE_SYSTEM_START.
; If it is an Optional filter, you may also use 3;SERVICE_DEMAND_START.
StartType       = 1 ;SERVICE_SYSTEM_START
ErrorControl    = 1 ;SERVICE_ERROR_NORMAL
ServiceBinary   = %12%\basicndis.sys
LoadOrderGroup  = NDIS
Description     = %basicndis_Desc%
AddReg          = NdisImPlatformBindingOptions.reg

[Install.Remove.Services]
; The SPSVCINST_STOPSERVICE flag instructs SCM to stop the NT service
; before uninstalling the driver.
DelService=basicndis,0x200 ; SPSVCINST_STOPSERVICE

[NdisImPlatformBindingOptions.reg]
; By default, when an LBFO team or Bridge is created, all filters will be
; unbound from the underlying members and bound to the TNic(s). This keyword
; allows a component to opt out of the default behavior
; To prevent binding this filter to the TNic(s):
;   HKR, Parameters, NdisImPlatformBindingOptions,0x00010001,1 ; Do not bind to TNic
; To prevent unbinding this filter from underlying members:
;   HKR, Parameters, NdisImPlatformBindingOptions,0x00010001,2 ; Do not unbind from Members
; To prevent both binding to TNic and unbinding from members:
;   HKR, Parameters, NdisImPlatformBindingOptions,0x00010001,3 ; Do not bind to TNic or unbind from Members
HKR, Parameters, NdisImPlatformBindingOptions,0x00010001,0 ; Subscribe to default behavior



[Strings]
; TODO: Customize these strings.
Badflyer = "badflyer" ;TODO: Replace with your manufacturer name
basicndis_Desc = "basicndis NDIS LightWeight Filter"
basicndis_HelpText = "basicndis NDIS LightWeight Filter"

The comments here are mostly from the NDIS lightweight filter template which comes with the Windows Driver Kit. Now you can install the driver onto a target computer. Assuming the target computer is a 64 bit machine.

; The important sections to note from the .info file:

; This specifies the x64 install, and we will need 'BADFLYER_basicndis' to install with netcfg
[MSFT.NTamd64]
%basicndis_Desc%=Install, BADFLYER_basicndis

; This specifies that this is a filtering extension
HKR, Ndi,FilterClass,, "ms_switch_filter"

; This specifies that we will bind to a virtual switch as an extension
HKR, Ndi\Interfaces, FilterMediaTypes,,"vmnetextension"

; 0x800 Automatically starts the driver after installation.
AddService=basicndis,0x800,basicndis_Service_Inst
  • Compile the project as x64
  • Copy the output to the target computer. (The target computer should bet in testmode "bcdedit /set testsigning on"). The output directory should contain atleast 3 files.
    • basicndis.cat
    • basicndis.inf
    • basicndis.sys
  • Use netcfg to install the driver. (instructions below)
  • Use powershell to enable the extension on the virtual switch (instructions below)

So, now that the files are copied over. You can use netcfg.exe to install the driver service. This will come by default on windows.

#
# You can lookup the documentation for netcfg online, but here is basically what needs to happen:
# netcfg /l <path to inf file> /c S /i <driver installation name from inf>
#
# The driver installation name can be found/set in the .inf file in the platform configuration section.
# EX:  ; BADFLYER_basicndis can be used with netcfg.exe to install/uninstall the driver.
#        [MSFT.NTx86]
#        %basicndis_Desc%=Install, BADFLYER_basicndis
#
# Here is an example
netcfg /l C:\Users\Administrator\Desktop\basicndis\basicndis.inf /c S /i BADFLYER_basicndis

If all goes well, you will get a nice happy message about success. If it does not, you will get an error code. Logs for netcfg can be found under "C:\Windows\INF\setupapi.dev.log" aka "%SYSTEMROOT%\INF\setupapi.dev.log" and "%SYSTEMROOT%\INF\setupapi.app.log".

Hopefully as is well, can you have gotten this far, you can enable the extension on the Hyper-V virtual switch. In this example, I have a VM Switch named "InternalSwitch".

PS C:\Users\Administrator> Get-VMSwitchExtension -VMSwitchName internalswitch | where { $_.Vendor -match 'badflyer' }


Id                  : 3CA735B3-E816-470B-905E-9D5097241C74
Name                : basicndis NDIS LightWeight Filter
Vendor              : badflyer
Version             : 23.54.47.252
ExtensionType       : Filter
ParentExtensionId   :
ParentExtensionName :
SwitchId            : 655c9bd4-0d5b-4322-8b39-1b9a58e0ce94
SwitchName          : InternalSwitch
Enabled             : False
Running             : True
CimSession          : CimSession: .
ComputerName        : WIN-7Q9KPM774O8
IsDeleted           : False

If you query for it, the driver is running, but is not enabled on the switch. But that's an easy fix.

Get-VMSwitchExtension -VMSwitchName internalswitch | where { $_.Vendor -match 'badflyer' } | Enable-VMSwitchExtension
# or
Get-VMSwitchExtension -VMSwitchName internalswitch | where { $_.Vendor -match 'badflyer' } | Disable-VMSwitchExtension

That's all there is to it. After that, your NDIS filter driver will begin to receive traffic from the virtual switch, and will be part of the virtual switch's driver stack.

# To uninstall the driver, simply use netcfg#
#
# netcfg /u <driver installation name from inf>
#
netcfg /u BADFLYER_basicndis

To start and stop the driver server, you can use:

# net start <name of service>
# net stop <name of service>
# Stop-Service <name of service>
# Start-Service <name of service>

# EX: (Note, in this example this is not the same as the name given to netcfg)
#    You can make them the same if you configure your inf that way, but the service
#    name is not necessarily the same as the name of the section used for installation.
net start basicndis
Peter Sulucz - June 21, 18

There are three different notations for expressing a mathematical equation.

  • prefix
  • infix
  • postfix

Basically, the just describe where operators lie in the equation compared to their operands. The most common of all of the formats is the one everyone is probably most familiar with, infix, which means that the operators lie in between their operands. Lets take for example the equation "1 + 5".

#
# Equation: "1 + 5"
#
#  Prefix:  "+ 1 5"
#  Infix:   "1 + 5"
#  Postfix: "1 5 +"
#

From the perspective of a computer, postfix if very easy to process, because an operator always follows its two operands, and their is no reason to use parenthesis. Prefix notation also does not require parenthesis, but is a little strange to work with.

In order to process prefix, we always take the right most operator in the expression, and apply it to the next two digits in the string. We do that until we are out of operators. Infix is processed using the order of operations. Postfix is processed by taking the left most operand in the expression, and applying it to the preceding digits every time.

#
# Equation1: "(1 + 5) * 3"
# Equation2: "1 + 5 * 3"
#
#  Prefix1:  "* + 1 5 3"   => "* 6 3"   => "18"
#  Infix1:   "(1 + 5) * 3" => "(6) * 3" => "18"
#  Postfix1: "3 1 5 + *"   => "3 6 *"   => "18"
#
#
#  Prefix2:  "+ * 3 5 1"   => "+ 15 1"  => "16"
#  Infix2:   "1 + 5 * 3"   => "1 + 15"  => "16"
#  Postfix2: "1 5 3 * +"   => "1 15 +"  => "16"
#

The postfix algorithm is quite simple to implement. Going through the string, every time you see a number, add it to a stack. If you see an operator, pop the last two items off of the stack and apply the operator. Push the result back onto the stack so that it can be used in following computations.

So here is an example of the postfix algorithm implemented in powershell.

function Eval-Postfix
{
    param
    (
        [Parameter(Mandatory = $true)][string]$expression
    )
    process
    {
        # Create a stack to store the numbers which aren't yet processed
        $stack = [System.Collections.Generic.Stack[int]]::new()

        # Split the input string into individual values
        $values = $expression.Split(' ', [System.StringSplitOptions]::RemoveEmptyEntries)

        foreach($val in $values)
        {
            # Try to parse the value
            $intvalue = 0
            if([int]::TryParse($val, [ref]$intvalue))
            {
                # If the value is an integer, add it to the stack
                $stack.Push($intvalue)

                # Then continue on
                continue;
            }

            # If the value is not an integer, we pop the top two numbers off the stack
            $b = $stack.Pop()
            $a = $stack.Pop()

            # Then perform the correct operation on them
            $result = switch($val)
            {
                '+' { $a + $b; break; }
                '-' { $a - $b; break; }
                '*' { $a * $b; break; }
                '/' { $a / $b; break; }
            }

            # Push the result back onto the stack
            $stack.Push($result)
        }

        # The only thing left on the stack should be a single value,
        # which is the result of the final operation
        return $stack.Pop()
    }
}

Just to be safe, here is code golf one liner which uses the same queue approach to solve the problem.

function Eval-Postfix
{
    param
    (
        [Parameter(Mandatory = $true)][string]$e
    )
    process
    {
        $s=@();switch -regex($e.Split(' ')){'\d'{$s=,+$_+$s}default{$a,$b,$s=$s;$s+=iex "$b$_$a"}};$s
    }
}

The code golf version uses a powershell array rather than a stack, and uses a switch as a loop. There you have it, both of these functions will output the results of postfix operations.

#
#  > Eval-Postfix "1 2 + 5 6 * +"
#     33
#
Peter Sulucz - June 12, 18

I had an issue recently where I needed to write some bits into a byte array in network order. In my case, I was writing an executable which could read a text file with some instructions on what to write into a network packet, then send that packet over the network.

// Here is an explanation:
//
// Say we have our buffer, which is 1 byte long:
//           ^
// buffer -> 00000000
//
// Now we want to write a 2 bit long value into it, which has the value 3 (binary 11).
//                 ^
// Now buffer -> 11000000
// Now lets write another value, this time 3 bits, with the value zero.
//                    ^
// Now buffer -> 11000000
// Now lets write another 2 bit value, but this time with the value 1. (binary 01).
//                      ^
// Now buffer -> 11000010
//
// He is an example for an ethernet frame
//
// An ethernet frame is laid out as follows:
//
// Destination MAC Address: 48 bits
// Source MAC Address:      48 bits
// Ethernet Type:           16 bits
//
// I wanted to be able to create a file which had some sort
//   of details like this, very generalized.
//
// For example:
// 0x00155E112233 int48
// 0x00155E445566 int48
// 0x0800         int16
//
// This would write an ethernet frame into a byte[] buffer. There are some more
//   complex cases in the IPv4 header, which need to write values that are 2 or 4 bits long.
//

That's where this bit of code was born. It takes a list of values and their bit length as an input, and writes them into a bit buffer.

/// <summary>
/// Simple struct for definiting a value and its bit length;
/// </summary>
public struct BitDefinition
{
    public BitDefinition(ulong value, byte bitLength)
    {
        this.Value = value;
        this.BitLength = bitLength;
    }

    public ulong Value;
    public byte BitLength;
}

public static byte[] WriteBits(IList<BitDefinition> bits)
{
    // Figure out the number of bytes we need in our array.
    var requiredBitLength = bits.Sum(b => b.BitLength);
    var requiredByteLength = requiredBitLength / 8 + (requiredBitLength % 8 == 0 ? 0 : 1);

    var buffer = new byte[requiredByteLength];
    unsafe
    {
        fixed (byte* bufferConstPtr = buffer)
        {
            // Initial offset withing the first byte is always zero.
            var bitOffset = 0;

            // We need a pointer we can actually change.
            var bufferPtr = bufferConstPtr;

            foreach(var bitDefinition in bits)
            {
                WriteBits(ref bufferPtr, ref bitOffset, bitDefinition.Value, bitDefinition.BitLength);
            }
        }
    }

    return buffer;
}

private static unsafe void WriteBits(ref byte * buffer, ref int bitOffset, ulong value, byte length)
{
    var bitsWritten = 0;

    if (length > 64)
    {
        throw new ArgumentOutOfRangeException("Length must be less than the size of a ulong");
    }

    while(bitsWritten < length)
    {
        // The number of bits left to write in total.
        var bitsRemaining = length - bitsWritten;

        // Size of the shift we need to do to get the target bits into the current byte.
        var shiftAmount = Math.Max(bitsRemaining - 8, 0);

        // The current byte value to write into the buffer.
        var currentVal = (byte)((value >> shiftAmount) & 0xFF);

        // The number of bits left to write.
        var currentByteBitsRemaining = Math.Min(8, bitsRemaining);

        // Move the value into the right offset and or it with the buffer.
        *buffer |= (byte)((currentVal << (8 - currentByteBitsRemaining)) >> bitOffset);

        // The number of written bits was either 
        var written = Math.Min(currentByteBitsRemaining, (8 - bitOffset));
        bitOffset += written;

        // If we have filled up the byte, then roll over to the next one.
        if(bitOffset == 8)
        {
            bitOffset = 0;
            buffer++;
        }

        // Add to the number of total bits written.
        bitsWritten += written;
    }
}

Any C# where you can use "unsafe" and pointers is great C#. This code also handles longer values which straddle the byte boundaries. And also values which are not byte aligned. Here is a test case.

static unsafe void Main(string[] args)
{
    var definitions = Enumerable.Range(0, 16).Select(i => new BitDefinition((ulong)i % 2, 1)).ToList();
    var bytes = WriteBits(definitions);

    for(var i = 0; i < bytes.Length; i++)
    {
        Console.WriteLine("{0} {1:}", i, Convert.ToString(bytes[i], 2).PadLeft(8, '0'));
    }
}

// Output:
// 0 01010101
// 1 01010101

There you have it! Some not overly complicated C# which can write bits to a buffer in order, in big-endian(network order) format.