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

raw

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

raw

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

raw

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.

raw

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.

raw

#
#  > Eval-Postfix3 "1 2 + 5 6 * +"
#     33
#




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.

raw

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

raw

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

raw

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.




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.

raw

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

raw

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.

raw

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#

raw

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!




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.

raw

/// <summary>
/// The sql manager class.
/// </summary>
public sealed class SqlManager
{
    private readonly string connectionString;

    /// <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>
    /// <returns>An async task.</returns>
    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>
    /// Execute an SQL reader.
    /// </summary>
    /// <typeparam name="T1">The first type.</typeparam>
    /// <param name="storedProcedure">The stored procedure name.</param>
    /// <param name="parameters">The parameter changer.</param>
    /// <param name="reader1">The first reader.</param>
    /// <returns>The result sets.</returns>
    public Task<IReadOnlyCollection<T1>> Execute<T1>(string storedProcedure, Action<SqlParameterCollection> parameters, Func<SqlDataReader, T1> reader1)
        where T1 : class
    {
        return this.ExecuteInternal(storedProcedure, parameters, reader1).ContinueOnSuccess(result =>
        {
            return result[0].Cast<T1>().AsReadonly();
        });
    }

    /// <summary>
    /// Execute an SQL reader.
    /// </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>
    /// <param name="reader1">The first reader.</param>
    /// <param name="reader2">The second reader.</param>
    /// <returns>The result sets.</returns>
    public Task<(IReadOnlyCollection<T1>, IReadOnlyCollection<T2>)> Execute<T1, T2>(string storedProcedure, Action<SqlParameterCollection> parameters, Func<SqlDataReader, T1> reader1, Func<SqlDataReader, T2> reader2)
        where T1 : class
        where T2 : class
    {
        return this.ExecuteInternal(storedProcedure, parameters, reader1, reader2).ContinueOnSuccess(result =>
        {
            return (result[0].Cast<T1>().AsReadonly(), result[1].Cast<T2>().AsReadonly());
        });
    }

    /// <summary>
    /// Execute an SQL reader.
    /// </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>
    /// <param name="reader1">The first reader.</param>
    /// <param name="reader2">The second reader.</param>
    /// <returns>The result sets.</returns>
    public Task<(IReadOnlyCollection<T1>, IReadOnlyCollection<T2>, IReadOnlyCollection<T3>)> Execute<T1, T2, T3>(string storedProcedure, Action<SqlParameterCollection> parameters, Func<SqlDataReader, T1> reader1, Func<SqlDataReader, T2> reader2, Func<SqlDataReader, T3> reader3)
        where T1 : class
        where T2 : class
        where T3 : class
    {
        return this.ExecuteInternal(storedProcedure, parameters, reader1, reader2, reader3).ContinueOnSuccess(result =>
        {
            return (result[0].Cast<T1>().AsReadonly(), result[1].Cast<T2>().AsReadonly(), result[2].Cast<T3>().AsReadonly());
        });
    }

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

        command.Parameters.Add(error);
        command.Parameters.Add(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:
                throw new ItemNotFoundException(message ?? "The item was not found.");
            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>
    /// <param name="readers">The data reader functions.</param>
    /// <returns>All of the results.</returns>
    private async Task<IReadOnlyCollection<object>[]> ExecuteInternal(string storedProcedure, Action<SqlParameterCollection> parameters, params Func<SqlDataReader, object>[] readers)
    {
        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);

                var result = new IReadOnlyCollection<object>[readers.Length];

                using (var reader = await command.ExecuteReaderAsync())
                {
                    // Read each result set
                    for (var i = 0; i < readers.Length; i++)
                    {
                        // Make sure there is no error.
                        SqlManager.HandleCustomErrors(command);

                        var list = new List<object>();
                        while (await reader.ReadAsync())
                        {
                            list.Add(readers[i](reader));
                        }

                        result[i] = list;

                        // Something done messed up
                        if(false == await reader.NextResultAsync() && i < readers.Length - 1)
                        {
                            // 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:

raw

internal sealed class RatingsDataLayer : IRatingDataLayer
{
    /// <summary>
    /// The sql manager.
    /// </summary>
    private readonly SqlManager sqlManager;

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

    /// <summary>
    /// Rate a user.
    /// </summary>
    /// <param name="rating">The rating.</param>
    /// <returns>An async task.</returns>
    public Task RateUser(UserRatingData rating)
    {
        return this.sqlManager.Execute("ronny.rateuser", parameters =>
        {
            parameters.AddWithValue("source", rating.SourceUser);
            parameters.AddWithValue("target", rating.TargetUser);
            parameters.AddWithValue("value", rating.Value);
        });
    }

    /// <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 =>
        {
            parameters.AddWithValue("top", top);
            parameters.AddWithValue("skip", skip);
            parameters.AddWithValue("source", sourceUser);
            parameters.AddWithValue("target", targetUser);
            parameters.AddWithValue("startdate", startRange);
            parameters.AddWithValue("enddate", endRange);
            parameters.AddWithValue("minvalue", minValue);
            parameters.AddWithValue("maxvalue", maxValue);
        },
        UserRatingData.FromReader);
    }
}

raw

/// <summary>
/// From an sql data reader.
/// </summary>
/// <param name="reader">The reader.</param>
/// <returns>The user rating..</returns>
internal static UserRatingData FromReader(SqlDataReader reader)
{
    return new UserRatingData(
        (Guid)reader["targetid"],
        (Guid)reader["sourceid"],
        (DateTime)reader["whenoccured"],
        (byte)reader["rating"]);
}

raw

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!




There is no super easy way to find the bottom of the stack in x86. There's a register "ebp" which points to the base of the stack frame. The address to which "ebp" points, contains the value of the previous "ebp" for the previous stack frame. Its basically a linked list we can traverse until we get to the NULL ebp (which is the bottom frame of the stack).

raw

ULONG findStackBase()
{
    // EBP points to the previous value of ebp on the stack
    PULONG baseptr;
    __asm {
        mov baseptr, ebp
    }

    // Traverse the list until we get to the end.
    while (NULL != *baseptr)
    {
        baseptr = (PULONG)*baseptr;
    }

    return (ULONG)baseptr;
}

This code snippet gets the value of "ebp" and runs down the list of stack base pointers until we find the end.

This really only has a place as a debugging function. Orrr, maybe a way to control your poorly written recursive loop... Here's an example of program which executes a loop, by recursion. Once the loop makes it close to the bottom of the stack, it does a long jump back up to the top of the stack so that it can keep going.

raw

// precomp.h
#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <Windows.h>
#include <setjmp.h>
#include <winnetwk.h>
#include "looper.h"



// looper.h

#pragma once

// Typdef for the function to pass as an argument to the looping function.
typedef VOID(*looperfunc)(ULONG, PVOID);

VOID ExecuteLoop(ULONG count, looperfunc);



// looper.c

#include "precomp.h"
#include <setjmp.h>

#define STACK_RESET_LIMIT 1024 * 800 // 800kb, we should reset

typedef struct _loopcontext {
    ULONG current; // Current count
    ULONG maximum; // Maximum count
    jmp_buf jumpBuffer; // Buffer to store the jump location for longjump
    looperfunc func; // The function to execute 
    ULONG stackStart; // the bottom of the stack
} loopcontext, *Ploopcontext;

ULONG findStackBase()
{
    // EBP points to the previous value of ebp on the stack
    PULONG baseptr;
    __asm {
        mov baseptr, ebp
    }

    // Traverse the list until we get to the end.
    while (NULL != *baseptr)
    {
        baseptr = (PULONG)*baseptr;
    }

    return (ULONG)baseptr;
}

VOID loopHelper(Ploopcontext context)
{
    // Base condition
    if (context->current >= context->maximum)
    {
        return;
    }

    // Get the value of esp
    ULONG currentStackPtr;
    __asm {
        mov currentStackPtr, esp
    };
    // Execute our callback
    context->func(context->current, NULL);

    // Increment the loop counter
    context->current++;

    // Find our distance from the base of the stack (the stack grows downwards)
    ULONG distance = (context->stackStart - currentStackPtr);
    if (distance >= STACK_RESET_LIMIT)
    {
        longjmp((int*)&context->jumpBuffer, 1);
    }

    // Recurse
    loopHelper(context);
}

/// <Summary>
/// Execute a loop, using recursion
/// </Summary>
VOID ExecuteLoop(ULONG count, looperfunc func)
{
    // Initialize the loop context
    loopcontext context;
    context.current = 0;
    context.maximum = count;
    context.func = func;
    context.stackStart = findStackBase();

    setjmp((int*)&context.jumpBuffer);

    // Run the loop
    loopHelper(&context);
}



// main.c

#include "precomp.h"
#include "looper.h"

// This is the func
VOID testfunc(ULONG l, PVOID val)
{
    ULONG buffer[400];
    printf("looping %u \n", l);
}

int main(int arc, char ** argv)
{
    ExecuteLoop(10000, testfunc);
    return 0;
}




There have been a few cases recently where I have needed to keep track of an array of bits. Basically as a record to mark off when sections of something have completed. The simplest scenario is for something like a torrent file transfer. Let's say the file is made up of 100 chunks, which we can keep track of each completed chunk which was written by marking it in our bit buffer.

For example, our buffer "00000000". When the third item completes we can say "00100000", and so on. The simplest way to do this in C# would be to make an array of Booleans. This seemed like a total waste of memory to me, since Booleans in c# take up much more space than a single bit.

raw

public class ByteBitBuffer
{
    /// <summary>
    /// The binary buffer.
    /// </summary>
    private readonly byte[] bytes;

    /// <summary>
    /// Initializes a new instance of the <see cref="ByteBitBuffer"/> class.
    /// </summary>
    /// <param name="length">The length of the buffer.</param>
    public ByteBitBuffer(int length)
    {
        var len = length / 8;
        if(length % 8 != 0)
        {
            len++;
        }

        this.bytes = new byte[len];
    }

    /// <summary>
    /// Sets the value at an index.
    /// </summary>
    /// <param name="index">The index.</param>
    /// <param name="value">The value.</param>
    public void Set(int index, bool value)
    {
        byte mask = (byte)(1 << (index % 8));
        if(value)
        {
            this.bytes[index / 8] |= mask;
        }
        else
        {
            this.bytes[index / 8] &= (byte)~mask;
        }
    }

    /// <summary>
    /// Gets the value at an index.
    /// </summary>
    /// <param name="index">The index.</param>
    /// <returns>The value.</returns>
    public bool Get(int index)
    {
        return ((this.bytes[index / 8] >> (index % 8)) & 1) != 0; 
    }
}

This is what I ended up with. From a programmers perspective, this is great. I got to do everything that I love: bit manipulation and cramming as much data into as little space as possible. The real question is, how fast is this compared to the basic Boolean[] implementation.

The Boolean implementation is much simpler of course.

raw

public class BitBufferBools
{
    /// <summary>
    /// The boolean array.
    /// </summary>
    private readonly bool[] bools;

    /// <summary>
    /// Initializes a new instance of the <see cref="BitBufferBools"/> class.
    /// </summary>
    /// <param name="length">The length of the buffer.</param>
    public BitBufferBools(int length)
    {
        this.bools = new bool[length];
    }

    /// <summary>
    /// Sets the value at the index.
    /// </summary>
    /// <param name="index">The index.</param>
    /// <param name="value">The value.</param>
    public void Set(int index, bool value)
    {
        this.bools[index] = value;
    }

    /// <summary>
    /// Gets the value at the index.
    /// </summary>
    /// <param name="index">The index.</param>
    /// <returns>The value.</returns>
    public bool Get(int index)
    {
        return this.bools[index];
    }
}

C# also provides a class by default which can do the same thing as the two previous implementations named "System.Collections.BitArray".

My test harness for the code:

raw

static void Main(string[] args)
{
    // Run each method once to make sure they are all compiled
    Program.TestBitArray(1, 100);
    Program.TestBooleanArray(1, 100);
    Program.TestByteArray(1, 100);
    Program.TestIntArray(1, 100);
    Program.TestLongArray(1, 100);

    // Get the test values
    Console.Write("Iterations? ");
    var iterations = int.Parse(Console.ReadLine());
    Console.Write("Length? ");
    var length = int.Parse(Console.ReadLine());

    Console.WriteLine($"Performing tests with {iterations} iterations and length {length}.");

    // Test the boolean array
    Program.TestHarness("An array of bools", iterations, length, Program.TestBooleanArray);

    // Test System.Collection.BitArray
    Program.TestHarness("System.Collections.BitArray", iterations, length, Program.TestBitArray);

    // Test custom binary implementations
    Program.TestHarness("byte[]", iterations, length, Program.TestByteArray);
    Program.TestHarness("uint[]", iterations, length, Program.TestIntArray);
    Program.TestHarness("ulong[]", iterations, length, Program.TestLongArray);

    Console.ReadLine();
}

/// <summary>
/// The test harness.
/// </summary>
/// <param name="testName">The name of the test.</param>
/// <param name="iterations">The number of iterations.</param>
/// <param name="length">The length of the bit array.</param>
/// <param name="testAction">The test action.</param>
private static void TestHarness(string testName, int iterations, int length, Action<int, int> testAction)
{
    var watch = Stopwatch.StartNew();

    testAction(iterations, length);

    watch.Stop();
    Console.WriteLine($"Finished test: {testName} -> {watch.ElapsedMilliseconds}ms");
}

/// <summary>
/// Under the hood, just an array of bools.
/// </summary>
private static void TestBooleanArray(int iterations, int length)
{
    var bools = new BitBufferBools(length);

    for(var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bools.Set(l, !bools.Get(length - l - 1));
        }
    }
}

/// <summary>
/// Under the hood, a System.Collections.BitArray
/// </summary>
private static void TestBitArray(int iterations, int length)
{
    var bits = new BitArray(length);

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bits.Set(l, !bits.Get(length - l - 1));
        }
    }
}

/// <summary>
/// Under the hood, a byte[]
/// </summary>
private static void TestByteArray(int iterations, int length)
{
    var bits = new ByteBitBuffer(length);

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bits.Set(l, !bits.Get(length - l - 1));
        }
    }
}

/// <summary>
/// Under the hood, a uint[]
/// </summary>
private static void TestIntArray(int iterations, int length)
{
    var bits = new IntBitBuffer(length);

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bits.Set(l, !bits.Get(length - l - 1));
        }
    }
}

/// <summary>
/// Under the hood, a ulong[]
/// </summary>
private static void TestLongArray(int iterations, int length)
{
    var bits = new LongBitBuffer(length);

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bits.Set(l, !bits.Get(length - l - 1));
        }
    }
}

Here are the results, needless to say I was a little disappointed. But as it turns out, all of the bit manipulations are pretty expensive. So what you do save in space, you lose dearly in performance.

raw

// Iterations? 1000
// Length? 1000000
// Performing tests with 1000 iterations and length 1000000.
// Finished test: An array of bools -> 1255ms
// Finished test: System.Collections.BitArray -> 8127ms
// Finished test: byte[] -> 6462ms
// Finished test: uint[] -> 5609ms
// Finished test: ulong[] -> 5531ms

Since I was a little annoyed, I thought I would try one more thing. Maybe I could improve performance significantly by allocating my custom collections directly onto the stack.

raw

private static unsafe void TestStackAllocInts(int iterations, int length)
{
    var len = length / 32;
    if (length % 32 != 0)
    {
        len++;
    }

    uint * bits = stackalloc uint[len];

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            PointerBitBuffer.Set(bits, l, !PointerBitBuffer.Get(bits, length - l - 1));
        }
    }
}

public static unsafe class PointerBitBuffer
{
    public static void Set(uint * self, int index, bool value)
    {
        var mask = 1U << (index % 32);
        if (value)
        {
            self[index / 32] |= mask;
        }
        else
        {
            self[index / 32] &= ~mask;
        }
    }

    public static bool Get(uint* self, int index)
    {
        return ((self[index / 32] >> (index % 32)) & 1) != 0;
    }
}

This did improve performance a little. But sadly, allocating the Boolean[] directly onto the stack is an even larger performance increase.

raw

private static unsafe void TestStackAllocBools(int iterations, int length)
{
    bool* bits = stackalloc bool[length];

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bits[i] = !bits[length - l - 1];
        }
    }
}

So here are the final results:

raw

// Iterations? 1000
// Length? 1000000
// Performing tests with 1000 iterations and length 1000000.
// Finished test: An array of bools -> 1255ms
// Finished test: System.Collections.BitArray -> 8127ms
// Finished test: byte[] -> 6462ms
// Finished test: uint[] -> 5609ms
// Finished test: ulong[] -> 5531ms
// Finished test: stackalloc uint[] -> 4102ms
// Finished test: stackalloc ulong[] -> 5106ms
// Finished test: stackalloc bool[] -> 723ms

The moral of the story is, C# is incredibly fast with basic arrays. So if space is no constraint, just use a basic Boolean array to store a bit buffer, unless you actually need the ability to write it directly to binary.




Strings in C# are not mutable. Any string operation is actually creating a brand new string and allocating it onto the heap. C# also doesn't provide any sort of tools for you to modify an existing string without creating a new one. Using some clever pointer magic, you can alter a string in place. This is not generally recommended, but it could be useful in some cases.

raw

class Program
{
    private const string HelloWorld = "Hello World";

    static void Main(string[] args)
    {
        Console.WriteLine(HelloWorld);
        Program.ChangeString(HelloWorld, "badflyer");
        Console.WriteLine(HelloWorld);

        const string HelloWorld2 = "Hello World 2";

        Console.WriteLine(HelloWorld2);
        Program.ChangeString(HelloWorld2, "not hello");
        Console.WriteLine(HelloWorld2);

        Console.ReadLine();
    }

    private static void ChangeString(string target, string newValue)
    {
        if(newValue.Length > target.Length)
        {
            throw new ArgumentException("The new string cannot be longer than the current string");
        }

        unsafe
        {
            fixed (char* str = target)
            {
                // Change the length to match our new string. The length is stored as an int right in front of the first character
                *((int*)str - 1) = newValue.Length;

                // Copy the new string
                for(var i = 0; i < newValue.Length; i++)
                {
                    str[i] = newValue[i];
                }
            }
        }
    }
}

Here's the output of this program:

raw

// Hello World
// badflyer
// Hello World 2
// not hello

Long story short, C# stores strings on the heap just as C would store a BSTR. It starts with a 32 bit length, and then the string as a fixed array of two byte chars. When you use the "fixed" expression in c#, you get a pointer to the first character of the string. We can step back 4 bytes to get a pointer to the string length, then we can change the string length to match our incoming string. You can't make the string any longer, because there is no way to know what follows in the heap.




C# has a pretty neat namespace named "System.Reflection.Emit", which allows you to build assemblies at runtime using Intermediate Language. This is a basic example of how to create an assembly, define a global function, and execute that function.

The following is an example. It is designed to be easy to follow, but here is a quick overview. The first thing we do is define a dynamic assembly. Within that assembly, we define a module. The whole assembly vs. module thing can be a little confusing. An assembly contains the manifest, and a collection of modules. Now in practice, an assembly usually only has a single module defined inside of it. Any C# project you create will also follow this 1 to 1 relationship. The module contains all of the actual code. Within the module, we define a global function (unsupported by C#, but IL is cool with it). Using the IL generator on the function, we can load a string onto the evaluation stack ("hello world"), call a function (Console.WriteLine), and then return from our function.

raw

namespace ReflectionEmitHelloWorld
{
    using System;
    using System.Reflection;
    using System.Reflection.Emit;

    class Program
    {
        static void Main(string[] args)
        {
            // Define the assembly and module
            const string AssemblyName = "Badflyer.HelloWorld.dll";
            var assembly = AssemblyBuilder.DefineDynamicAssembly(new AssemblyName(AssemblyName), AssemblyBuilderAccess.RunAndCollect);
            var module = assembly.DefineDynamicModule(AssemblyName);

            // Define the method and get the Intermediate Language generator.
            var methodBuilder = module.DefineGlobalMethod("HelloWorld", MethodAttributes.Final | MethodAttributes.Public | MethodAttributes.Static, typeof(void), new Type[0]);
            var ilGenerator = methodBuilder.GetILGenerator();

            //// Too easy - but this works too
            // ilGenerator.EmitWriteLine("Hello World");

            // Get the method info for writeline
            var writeline = typeof(Console).GetMethod("WriteLine", BindingFlags.Public | BindingFlags.Static, Type.DefaultBinder, new[] { typeof(string) }, null);

            // Load the string onto the evaluation stack
            ilGenerator.Emit(OpCodes.Ldstr, "Hello World");

            // Call writeline
            ilGenerator.EmitCall(OpCodes.Call, writeline, new[] { typeof(string) });

            // Return
            ilGenerator.Emit(OpCodes.Ret);

            // Create the global functions (since that is what we defined)
            module.CreateGlobalFunctions();

            // Get our new method info
            var helloWorld = module.GetMethod("HelloWorld");
            // Invoke our new method.

            helloWorld.Invoke(null, null);

            // Wait for input
            Console.ReadLine();
        }
    }
}

Pretty cool! You can do things in IL which you cannot do from C# directly. Here for example we defined a global function which is not the member of any class. Following is the resulting IL which was generated from saving our generated .dll. Just a warning, dotnet core does not allow you to save the generated .dll. The regular .NET framework does.

raw

// To Save: var assembly = AssemblyBuilder.DefineDynamicAssembly(new AssemblyName(AssemblyName), AssemblyBuilderAccess.RunAndSave);
// To Save: assembly.Save(AssemblyName);
.method public final static 
 void HelloWorld () cil managed 
{
 // Method begins at RVA 0x2050
 // Code size 11 (0xb)
 .maxstack 1
 IL_0000: ldstr "Hello World"
 IL_0005: call void [mscorlib]System.Console::WriteLine(string)
 IL_000a: ret
}

And that's all there is to it! You can do a lot of learning by writing C# code snippets, and viewing the generated IL within the .dll with a tool. (For example ILSpy).




Sep 27, 2017

Here’s another journey through the world of simple programming problems… FizzBuzz, T-SQL edition. So just like the rest of the Fizz Buzz solutions. The idea is simple, for every number 1-100, if it’s divisible by 3 print ‘fizz’, if it’s divisible by 5 print ‘buzz’, if both print ‘fizzbuzz’, otherwise print the number. So here is a basic SQL solution:

raw

WITH ctCounter AS
(
	SELECT 1 AS Number

	UNION ALL

	SELECT Number + 1 AS Number
	FROM ctCounter
	WHERE Number < 100
)
SELECT ISNULL(NULLIF(CONCAT(fizz.f, buzz.b), ''), c.Number) FROM ctCounter c
LEFT JOIN (VALUES('fizz')) fizz(f)
  ON c.Number % 3 = 0
LEFT JOIN (VALUES('buzz')) buzz(b)
  ON c.Number % 5 = 0

This is a common table expression, which generates a row for each number between 1 and 100. Then joins with the values ‘fizz’ and ‘buzz’. After that, it concatenates the fizz and buzz together, and if it still results in an empty string, selects the original number. The NULLIF function is useful for that, because it is basically the inverse of ISNULL. If the first parameter matches the second parameter, it returns null, otherwise returns the first parameter.




Sep 25, 2017

Something which you shouldn’t be doing very often (or ever) is placing locks around chunks of asynchronous code. You’re almost always slowing down your code, and there has to be a better way to do it. Anyway, if you do try it, C# will give you a compile error along the lines of: ‘cannot await in the body of a lock statement’. This all makes sense, because locks are tied to a thread. If you are using the parallel task library, there is really no guarantee that your code is going to pick back up on the same thread where it originally left off. You can run into problems like this if you try to use a class like “ReadWriteLockSlim”, which doesn’t give compile warning about awaiting within the critical section, but will happily deadlock your code. So here is a solution to all your fears. Luckily SemaphoreSlim has async support.

This is a helper class which just makes a generic disposable for some coding sugar:

raw

    /// <summary>
    /// A class which can be disposed.
    /// </summary>
    public class Disposable : IDisposable
    {
        /// <summary>
        /// The action to perform on dispose.
        /// </summary>
        private readonly Action onDispose;

        /// <summary>
        /// Initializes a new dispoable.
        /// </summary>
        /// <param name="onDispose">The action to perform.</param>
        private Disposable(Action onDispose)
        {
            this.onDispose = onDispose;
        }

        /// <summary>
        /// Creates a disposable class.
        /// </summary>
        /// <param name="onDispose">The dispose action.</param>
        /// <returns>A disposable.</returns>
        public static IDisposable Create(Action onDispose)
        {
            return new Disposable(onDispose);
        }

        /// <summary>
        /// Dispose.
        /// </summary>
        public void Dispose()
        {
            onDispose();
        }
    }

This is a dummy object which needs a lock:

raw

public class LockableObject
    {
        private readonly SemaphoreSlim asyncLock = new SemaphoreSlim(1);

        /// <summary>
        /// Gets a lock on this object.
        /// </summary>
        /// <param name="token">The token.</param>
        /// <returns>A disposable which release the lock.</returns>
        public Task<IDisposable> GetLock(CancellationToken token)
        {
            return this.asyncLock.WaitAsync(token).ContinueWith(result =>
            {
                if (result.IsCompleted && !result.IsFaulted && !result.IsFaulted)
                {
                    return Disposable.Create(() => asyncLock.Release());
                }

                throw result.Exception?.InnerExceptions.FirstOrDefault() ?? result.Exception ??
                      new Exception("Failed to aquire the lock for an unknown reason.");
            });
        }
    }

Here is a little demo test program:

raw

class Program
    {
        static void Main(string[] args)
        {
            // This wont work...
            ////var obj = new object();
            ////
            ////lock (obj)
            ////{
            ////    await TestLock();
            ////}

            TestLock().GetAwaiter().GetResult();
        }

        /// <summary>
        /// Test to see if this lock works
        /// </summary>
        /// <returns>An async task.</returns>
        public static async Task TestLock()
        {
            const int number = 10000;
            var someObject = new LockableObject();

            var parallelSum = 0L;

            using (var barrier = new ManualResetEventSlim(false))
            {

                var tasks = Enumerable.Range(0, number).Select(i =&gt; Task.Run(async () =&gt;
                {
                    // Queue up everything behind this barrier so things try to do this all at once.
                    barrier.Wait();

                    using (await someObject.GetLock(CancellationToken.None)) // Comment out this line to make it fail
                    {
                        // Critical Section
                        var t = parallelSum;
                        parallelSum = t + 1;
                    }
                }));

                barrier.Set();

                await Task.WhenAll(tasks);

            }

            if (parallelSum != number)
            {
                throw new Exception($"The counter is wrong. Expected {number}, but got {parallelSum}");
            }
        }
    }

A major caveat here is that this lock is not at all recursive/re-entrant. If you try to call it within the same call stack, you will most certainly deadlock. Other than that, happy locking.




© 2018 - Peter Sulucz | disclaimer

log in