## Sep 20, 2018

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.

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. */
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{

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

topLeft() : Vector{
}

bottomRight() : Vector{
}
}

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

constructor(){
this.position = new Vector();
this.velocity = new Vector();
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. */

/** The width of the land. */

/** The height of the land. */

/** The current time. */

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. */

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{

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

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

this.compontents.push(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.color = color;
}

{
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.acceleration = new Vector()

/** Bounce off the walls. */
this.physics.velocity.x *= -1;
}

this.physics.velocity.y *= -1;
}

// Update the movement
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,
0,
0,
Math.PI * 2);
context.graphics.fill();
context.graphics.closePath();
}
}

{
/** The maximum depth. */

/** The root node. */

/** The size of the map. */

/** The list of components. */

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. */
return this.root;
}

/** Add a component to the tree. */
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++;

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. */
{
/** The child nodes. */

/** The maximum depth. */

/** The current depth */

/** The top left corner of the node. */

/** The bottom right corner of the node. */

/** The center of the node. */

/** The components attached to the node. */

/** The parent tree node. */

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;
}

return this.cells[0];
}

return this.cells[1];
}

return this.cells[2];
}

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.
*/
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){
}

/** 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.  */
let index = this.cells.indexOf(child);
this.cells[index] = null;
this.Prune();
}

/** Gets or creates a new quad tree node. */
if(this.cells[index] == null){
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;

constructor(component : PhysicsProperties, node : QuadTreeNode){
this.component = component;
this.node = node;
}
}

/** Draws the quad tree */
physics : PhysicsProperties;

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>();

}

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;
}
}

this.components.push(component);

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

if(component.physics != null){
}
}

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{

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() {
//window.onkeydown = (event) => {
//    if(event.charCode === 0){
//        // Spacebar
//    }
//}
this.canvas.onclick = (event) => {
//let ball = new Ball(new Vector(event.offsetX - 15, event.offsetY - 15), new Vector(), 15, 'red')
};
}
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));
}
}
EnableDiagnostics() {
let diagnostic = new Diagnostics(this.controller);
}
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();``````

## Sep 14, 2018

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

-- 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

-- 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.

## Jul 31, 2018

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)'          " />

<!-- 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="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>``````

## Jul 10, 2018

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>
<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.

## Jun 25, 2018

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]
}
}``````

## Jun 24, 2018

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}
DriverVer       =
CatalogFile     = basicndis.cat

[Manufacturer]

; BADFLYER_basicndis can be used with netcfg.exe to install/uninstall the driver.
[MSFT.NTx86]

[MSFT.NTamd64]

[MSFT.NTarm]

[MSFT.NTarm64]

;-------------------------------------------------------------------------
; Installation Section
;-------------------------------------------------------------------------
[Install]
; 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.

[basicndis_Service_Inst]
DisplayName     = %basicndis_Desc%
ServiceType     = 1 ;SERVICE_KERNEL_DRIVER
; 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
Description     = %basicndis_Desc%

[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.
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]

; 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.

• 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]
#
# Here is an example

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
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>
#

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``````

## Jun 21, 2018

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-Postfix3 "1 2 + 5 6 * +"
#     33
#``````

## Jun 12, 2018

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.

## Jun 09, 2018

In case you have ever been interested into how to display Pascal's triangle in F#, here is a solution! Went with a little bit of a different approach than usual since F# is a functional language.

``````
// Here is the general strategy I went with:
//
// Example, starting with the second row:
// previous row = 1 | 1
//
// Using the previous row, append a 0 to the beginning (so [1 | 1] becomes [0 | 1 | 1])
//   and combine with the same sequence, but with a zero stuck on the end (so [1 | 1] becomes [1 | 1 | 0])
//
// Sequence 1:    0 | 1 | 1
// Sequence 2:    1 | 1 | 0
//
// Now sum the values together which are at the same index
//
//                0 | 1 | 1
//              + 1 | 1 | 0
//              -----------
//                1 | 2 | 1
//
// We can do this recursively from each row, to get the next row
//
//  1
//      0 | 1
//    + 1 | 0
//    -------
//      1 | 1
//             0 | 1 | 1
//           + 1 | 1 | 0
//           -----------
//             1 | 2 | 1
//                        0 | 1 | 2 | 1
//                      + 1 | 2 | 1 | 0
//                      ---------------
//                        1 | 3 | 3 | 1
//                                       0 | 1 | 3 | 3 | 1
//                                     + 1 | 3 | 3 | 1 | 0
//                                     -------------------
//                                       1 | 4 | 6 | 4 | 1
//
// The results leave us with pascal's triange
//
//         1
//       1 | 1
//     1 | 2 | 1
//   1 | 3 | 3 | 1
// 1 | 4 | 6 | 4 | 1
//``````

Knowing all of that, here is the F# which gets it all done. By the way, the reason for using BigIntegers ( [0I] <- the I means BigInteger) is because these number grow very large, very quickly.

``````
let pascalshelper previousRow =
// Create a sequence with a zero prepended
let leftseq = seq {yield 0I; yield! previousRow}
// Create a sequence with a zero appended
let rightseq = seq {yield! previousRow; yield 0I}
// Zip up the two sequences by adding the values together at each index
Seq.map2 (fun a b -> a + b) leftseq rightseq |> Seq.toList

let rec pascals depth =
// Base case is the first row, which just has a single item
let currentRow = match depth with
| 1 -> [ 1I; ]
| _ -> pascals(depth - 1) |> pascalshelper
// Print out the list
printfn "%A" currentRow
currentRow

[<EntryPoint>]
let main argv =
pascals 10 |> ignore
0 // exit 0``````

Here is a bit shorter (mostly because I made the variable/function names shorter) solution which does the exact same thing, but is a little harder to follow. Also, instead of using "yield", Seq.append can be used to concatenate two arrays.

``````
let h l =
Seq.map2 (fun a b -> a + b) (Seq.append [0I] l) (Seq.append l [0I]) |> Seq.toList

let rec p x =
let r = match x with
| 1 -> [1I]
| _ -> p(x - 1) |> h
printfn "%A" r
r

[<EntryPoint>]
let main argv =
p 10 |> ignore
0``````

There you have it! To show a comparison, here is the same thing in C#

``````
class Program
{
static BigInteger[] PascalsHelper(BigInteger[] previousList)
{
var zero = new[] { new BigInteger(0) };
var leftSide = zero.Concat(previousList);
var rightSide = previousList.Concat(zero);

var result = new BigInteger[previousList.Length + 1];

using (var leftEnum = leftSide.GetEnumerator())
using (var rightEnum = rightSide.GetEnumerator())
{
// We know the length of the enumerables, so no need to bounds check the MoveNext() calls.
for(var i = 0; i < result.Length; i++)
{
leftEnum.MoveNext();
rightEnum.MoveNext();
result[i] = leftEnum.Current + rightEnum.Current;
}
}

return result;
}

static BigInteger[] Pascals(int depth)
{
var current = 1 == depth ? new[] { new BigInteger(1) }
: PascalsHelper(Pascals(depth - 1));
Console.WriteLine(String.Join(" ", current));
return current;
}

static void Main(string[] args)
{
Pascals(10);
}
}``````

The solution doesn't seem very "C#" to me. But it works!

## Apr 24, 2018

Here is the SQL data layer implementation which I use in all of my services. This class keeps all database access uniform and through stored procedures. It also requires a structure for stored procedures to follow, in order to support error handling.

• Stored Procedures
• Must take an @errormessage NVARCHAR(2048) OUTPUT parameter
• Must have an INT return value for their error code
• Result Sets
• Each result set must have a function which can parse it from a reader row.

``````
/// <summary>
/// The sql manager class.
/// </summary>
public sealed class SqlManager
{

/// <summary>
/// Initializes a new instance of the <see cref="SqlManager"/> class.
/// </summary>
/// <param name="connectionString"></param>
public SqlManager(string connectionString)
{
this.connectionString = connectionString;
}

/// <summary>
/// Execute a non-query.
/// </summary>
/// <param name="storedProcedure">The stored proc.</param>
/// <param name="parameters">The paramters.</param>
public async Task Execute(string storedProcedure, Action<SqlParameterCollection> parameters)
{
using (var connection = new SqlConnection(this.connectionString))
{
await connection.OpenAsync();
using (var command = connection.CreateCommand())
{
// Initialize parameters
parameters(command.Parameters);

// Setup the stored proc.
SqlManager.InitializeCommandSqlCommand(storedProcedure, command);

await command.ExecuteNonQueryAsync();

// Make sure there is no error.
SqlManager.HandleCustomErrors(command);
}
}
}

/// <summary>
/// </summary>
/// <typeparam name="T1">The first type.</typeparam>
/// <param name="storedProcedure">The stored procedure name.</param>
/// <param name="parameters">The parameter changer.</param>
/// <returns>The result sets.</returns>
where T1 : class
{
{
});
}

/// <summary>
/// </summary>
/// <typeparam name="T1">The first type.</typeparam>
/// <typeparam name="T2">The second type.</typeparam>
/// <param name="storedProcedure">The stored procedure name.</param>
/// <param name="parameters">The parameter changer.</param>
/// <returns>The result sets.</returns>
where T1 : class
where T2 : class
{
{
});
}

/// <summary>
/// </summary>
/// <typeparam name="T1">The first type.</typeparam>
/// <typeparam name="T2">The second type.</typeparam>
/// <typeparam name="T3">The third type.</typeparam>
/// <param name="storedProcedure">The stored procedure name.</param>
/// <param name="parameters">The parameter changer.</param>
/// <returns>The result sets.</returns>
where T1 : class
where T2 : class
where T3 : class
{
{
});
}

/// <summary>
/// Modified an sql command to be a stored proc.
/// </summary>
/// <param name="storedProcedure">The stored procedure name.</param>
/// <param name="command">The command to modify.</param>
private static void InitializeCommandSqlCommand(string storedProcedure, SqlCommand command)
{
// Stored proc
command.CommandText = storedProcedure;
command.CommandType = CommandType.StoredProcedure;

var error = new SqlParameter("errormessage", SqlDbType.NVarChar, 2048){ Direction = ParameterDirection.Output };
var returnValue = new SqlParameter("ReturnValue", SqlDbType.Int, 4) { Direction = ParameterDirection.ReturnValue };

}

/// <summary>
/// Handle errors from SQL.
/// </summary>
/// <param name="command">The command.</param>
private static void HandleCustomErrors(SqlCommand command)
{
var retvalue = command.Parameters["ReturnValue"]?.Value as int? ?? 0;
var message = command.Parameters["errormessage"]?.Value as string;

// These match errors.sql
switch (retvalue)
{
case 0:
return;
case 50001:
throw new InvalidArgumentException(message ?? "Invalid argument exception.");
case 50002:
case 50003:
throw new DuplicateItemViolationException(message ?? "Duplicate item detected.");

default:
if (retvalue > 50000)
{
throw new NotImplementedException(message ?? \$"Handling for error {retvalue} is missing.");
}
else
{
throw new Exception(message ?? "SQL failure. Generic. No error. Everything's fucked. #Yolo.");
}
}

}

/// <summary>
/// Execute an SQL data reader.
/// </summary>
/// <param name="storedProcedure">The stored procedure name.</param>
/// <param name="parameters">The parameter setter upper.</param>
/// <returns>All of the results.</returns>
{
using (var connection = new SqlConnection(this.connectionString))
{
await connection.OpenAsync();
using (var command = connection.CreateCommand())
{
// Initialize parameters
parameters(command.Parameters);

// Setup the stored proc.
SqlManager.InitializeCommandSqlCommand(storedProcedure, command);

{
for (var i = 0; i < readers.Length; i++)
{
// Make sure there is no error.
SqlManager.HandleCustomErrors(command);

var list = new List<object>();
{
}

result[i] = list;

// Something done messed up
{
// Try to eat the soft error. This throws an exception on failure.
SqlManager.HandleCustomErrors(command);

throw new DataException(\$"Expected {readers.Length} result sets. Got {i + 1}");
}
}

// After execution, one last check to make sure all is well.
SqlManager.HandleCustomErrors(command);
}

return result;
}
}
}
}``````

The datalayer is used as follows:

``````
internal sealed class RatingsDataLayer : IRatingDataLayer
{
/// <summary>
/// The sql manager.
/// </summary>

public RatingsDataLayer(string connectionString)
{
this.sqlManager = new SqlManager(connectionString);
}

/// <summary>
/// Rate a user.
/// </summary>
/// <param name="rating">The rating.</param>
{
return this.sqlManager.Execute("ronny.rateuser", parameters =>
{
});
}

/// <summary>
/// Get ratings for a user.
/// </summary>
/// <param name="top">The top.</param>
/// <param name="skip">The skip.</param>
/// <param name="targetUser">The target user.</param>
/// <param name="sourceUser">The source user.</param>
/// <param name="minValue">The min value.</param>
/// <param name="maxValue">The max value.</param>
/// <param name="startRange">The start date range.</param>
/// <param name="endRange">The end date range.</param>
/// <returns>The ratings.</returns>
public Task<IReadOnlyCollection<UserRatingData>> GetRatings(int? top, int? skip, Guid? targetUser, Guid? sourceUser, int? minValue, int? maxValue, DateTime? startRange, DateTime? endRange)
{
return this.sqlManager.Execute("ronny.getratings", parameters =>
{
},
}
}``````

``````
/// <summary>
/// From an sql data reader.
/// </summary>
/// <returns>The user rating..</returns>
{
return new UserRatingData(
}``````

``````
CREATE PROCEDURE ronny.getratings
@errormessage   NVARCHAR(2048)          OUTPUT
,@top            INT                     = 100
,@skip           INT                     = 0
,@source         UNIQUEIDENTIFIER        = NULL
,@target         UNIQUEIDENTIFIER        = NULL
,@startdate      DATETIME2               = NULL
,@enddate        DATETIME2               = NULL
,@minvalue       TINYINT                 = NULL
,@maxvalue       TINYINT                 = NULL
AS
DECLARE @error            INT       = 0

SET TRANSACTION ISOLATION LEVEL SNAPSHOT

SELECT
r.targetid
,r.sourceid
,r.whenoccured
,r.rating
FROM ronny.ratings r
WHERE
(@source IS NULL OR r.sourceid = @source)
AND (@target IS NULL OR r.targetid = @target)
AND (@startdate IS NULL OR r.whenoccured >= @startdate)
AND (@enddate IS NULL OR r.whenoccured <= @enddate)
AND (@minvalue IS NULL OR r.rating >= @minvalue)
AND (@maxvalue IS NULL OR r.rating <= @maxvalue)
ORDER BY r.whenoccured
OFFSET (@skip) ROWS
FETCH NEXT (@top) ROWS ONLY

RETURN 0``````

There you have it!