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

raw

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

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

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

You can run it as follows.

raw

# Pass the minimal flag to avoid a bunch of extra msbuild output
msbuild /v:minimal .\fizz.proj

raw

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




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.

raw

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

raw

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

raw

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:

raw

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.

raw

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




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.

raw

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

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


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

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

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

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

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

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

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

Copyfiles = basicndis.copyfiles.sys

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

[SourceDisksFiles]
basicndis.sys=1

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

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


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

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

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

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

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

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



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

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

raw

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

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

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

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

; 0x800 Automatically starts the driver after installation.
AddService=basicndis,0x800,basicndis_Service_Inst

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

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

raw

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

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

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

raw

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


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

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

raw

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.

raw

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

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

raw

# 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




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.




© 2018 - Peter Sulucz | disclaimer

log in