Convert to and from variable length quantities

Question

As part of small MIDI library i've implemented the conversion of a VLQ (variable length quantity) for byte[] -> bigint and bigint -> byte[]. Even though the maximum value for a MIDI VLQ is defined as 0x0FFF_FFFF i've decided to allow larger values for the moment.

If there are any improvements for the code, coding style, ..., please let me know.

Implementation:

module VariableLengthQuantity

    /// <summary>
    /// Reads a variable length quantity from the given byte array and returns a tuple
    /// of the value of the quantity and the remaining bytes of the array.
    /// </summary>
    /// <param name="bytes">A byte array that contains the variable length quantity.</param>
    /// <returns>A tuple of the quantity as <see cref="BigInteger"/> and the remaining bytes of th array.</returns>
    /// <exception cref="System.ArgumentException">
    /// <paramref name="bytes"/> has a length of 0 or
    /// <paramref name="bytes"/> is missing the end byte of the quentity.
    /// </exception>
    let toBigInt (bytes: byte[]) =
        if bytes.Length = 0 then
            invalidArg "bytes" "The byte array from which to build the variable length quantity has to have at least one element."

        let quantityBytes =
            // Modified version of Array.takeWhile.
            // Take all bytes from the array until a byte is found that
            // has the 7th bit not set (byte &&& 0x80 = 0).
            let mutable count = 0

            while count < bytes.Length && (bytes.[count] &&& 0x80uy) > 0uy do
                count <- count + 1

            if count = bytes.Length then
                invalidArg "bytes" ("Cannot fetch the bytes for a variable length quantity from the given " +
                    "byte array because the end byte of the quantity is missing.")

            count <- count + 1

            Array.sub bytes 0 count

        let mutable quantity = 0I
        let mutable currentBit = 0

        for i = quantityBytes.Length - 1 downto 0 do
            let quantityByte = quantityBytes.[i]

            // Bit 7 is a status bit.
            for bit = 0 to 6 do
                quantity <- quantity ||| (bigint (int ((quantityByte >>> bit) &&& 1uy)) <<< currentBit)
                currentBit <- currentBit + 1

        quantity, bytes.[quantityBytes.Length..]

    /// <summary>
    /// Creates a variable length quantity byte array from the given <see cref="BigInteger" />
    /// </summary>
    /// <param name="value">The value for which to create the variable length quantity byte array.</param>
    /// <returns>The created byte array.</returns>
    /// <exception cref="System.ArgumentException">
    /// <paramref name="value"/> is negative.
    /// </exception>
    let toByteArray (value: bigint) =
        if value.Sign = -1 then
            invalidArg "value" "The given value must be greater or equal to zero."

        match value with
        | x when x <= 127I -> [| byte value |]
        | _ ->
            let valueBytes = value.ToByteArray()
            let mutable resultBitIndex = 0
            let mutable resultHelper = 0I

            for i = 0 to valueBytes.Length - 1 do
                let byte = valueBytes.[i]

                for bit = 0 to 7 do
                    match resultBitIndex % 8 with                
                    | 7 ->
                        // Last bit of a byte is reserved for the more bytes indicator.
                        // Therefore the last bit of of each byte is skipped and the the last bit of the
                        // following byte is set to 1. Because the last bit is skipped the first byte
                        // always has 0 as value for the 7th bit.
                        resultBitIndex <- resultBitIndex + 1 
                        resultHelper <- resultHelper ||| bigint (1 <<< (resultBitIndex + 7))

                    | _ -> ()

                    resultHelper <- resultHelper |||  (bigint (int ((byte >>> bit) &&& 1uy)) <<< resultBitIndex)
                    resultBitIndex <- resultBitIndex + 1

            // Result array has to be MSB first.
            resultHelper.ToByteArray() |> Array.rev |> Array.skipWhile (fun x -> x = 0x80uy)

Test cases:

open Microsoft.VisualStudio.TestTools.UnitTesting
open System

[<TestClass>]
type TestVariableLengthQuantity () =

    [<TestMethod>]
    [<ExpectedException(typeof<ArgumentException>)>]
    member this.ToBigInt_ArrayLengthZero () =
        VariableLengthQuantity.toBigInt [||]
        |> ignore

    [<TestMethod>]
    [<ExpectedException(typeof<ArgumentException>)>]
    member this.ToBigInt_ArrayMissingEndByte () =
        VariableLengthQuantity.toBigInt [| 0x82uy; 0x84uy; 0x80uy; 0x8Auy |]
        |> ignore

    [<TestMethod>]
    member this.ToBigInt_SingleByte () =
        let result1, rem1 = VariableLengthQuantity.toBigInt [| 0x00uy |]
        let result2, rem2 = VariableLengthQuantity.toBigInt [| 0x71uy |]
        let result3, rem3 = VariableLengthQuantity.toBigInt [| 0x52uy |]
        let result4, rem4 = VariableLengthQuantity.toBigInt [| 0x44uy |]

        Assert.AreEqual(0I, result1)
        Assert.AreEqual(0, rem1.Length)

        Assert.AreEqual(113I, result2)
        Assert.AreEqual(0, rem2.Length)

        Assert.AreEqual(82I, result3)
        Assert.AreEqual(0, rem3.Length)

        Assert.AreEqual(68I, result4)
        Assert.AreEqual(0, rem4.Length)

    [<TestMethod>]
    member this.ToBigInt_MultipleBytes () =
        let result1, rem1 = VariableLengthQuantity.toBigInt [| 0x94uy; 0xE4uy; 0x6Buy |]
        let result2, rem2 = VariableLengthQuantity.toBigInt [| 0xDBuy; 0xB6uy; 0x01uy |]
        let result3, rem3 = VariableLengthQuantity.toBigInt [| 0x83uy; 0xFEuy; 0x7Fuy |]

        Assert.AreEqual(340_587I, result1)
        Assert.AreEqual(0, rem1.Length)

        Assert.AreEqual(1_497_857I, result2)
        Assert.AreEqual(0, rem2.Length)

        Assert.AreEqual(65_407I, result3)
        Assert.AreEqual(0, rem3.Length)

    [<TestMethod>]
    member this.ToBigInt_TrailingBytes () =
        let result1, rem1 = VariableLengthQuantity.toBigInt [| 0x94uy; 0xE4uy; 0x6Buy; 0xFFuy; 0x59uy |]
        let result2, rem2 = VariableLengthQuantity.toBigInt [| 0xDBuy; 0xB6uy; 0x01uy; 0x12uy |]

        Assert.AreEqual(340_587I, result1)
        Assert.AreEqual(2, rem1.Length)

        Assert.AreEqual(1_497_857I, result2)
        Assert.AreEqual(1, rem2.Length)


    [<TestMethod>]
    [<ExpectedException(typeof<ArgumentException>)>]
    member this.ToByteArray_NegativeNumber () =
        VariableLengthQuantity.toByteArray -1I
        |> ignore

    [<TestMethod>]
    member this.ToByteArray () =
        let bytes1 = VariableLengthQuantity.toByteArray 0I
        let bytes2 = VariableLengthQuantity.toByteArray 113I
        let bytes3 = VariableLengthQuantity.toByteArray 65_407I
        let bytes4 = VariableLengthQuantity.toByteArray 340_587I
        let bytes5 = VariableLengthQuantity.toByteArray 1_497_857I

        let expected1 = [| 0x00uy |]
        let expected2 = [| 0x71uy |]
        let expected3 = [| 0x83uy; 0xFEuy; 0x7Fuy |]
        let expected4 = [| 0x94uy; 0xE4uy; 0x6Buy |]
        let expected5 = [| 0xDBuy; 0xB6uy; 0x01uy |]

        CollectionAssert.AreEqual(expected1, bytes1)
        CollectionAssert.AreEqual(expected2, bytes2)
        CollectionAssert.AreEqual(expected3, bytes3)
        CollectionAssert.AreEqual(expected4, bytes4)
        CollectionAssert.AreEqual(expected5, bytes5)

Answer 1

It seems to work well with the provided test cases. The obvious objection when talking about functional programming in F# is to the use of mutable variables and loops. Instead it is common to use higher order functions and recursion.

For inspiration, below is toBigInt in a more functional style:

let toBigInt (bytes: byte[]) =
    if bytes.Length = 0 then
        invalidArg "bytes" "The byte array from which to build the variable length quantity has to have at least one element."

    let numUsableBytes = 
        let indexOpt = bytes |> Array.tryFindIndex (fun b -> b &&& 0x80uy = 0uy)
        match indexOpt with 
        | Some(index) -> index + 1
        | None -> invalidArg "bytes" ("Cannot fetch the bytes for a variable length quantity from the given " +
                    "byte array because the end byte of the quantity is missing.")

    let rec composeNum num bit resultBit byte =
        if bit = 7 then num, resultBit
        else
            composeNum (num ||| (bigint (int ((byte >>> bit) &&& 1uy)) <<< resultBit)) (bit + 1) (resultBit + 1) byte

    let result, _ = 
        Array.foldBack 
            (fun byte (num, resultBit) -> (composeNum num 0 resultBit byte)) 
            (bytes |> Array.take numUsableBytes)
            (0I, 0)
    result, bytes.[numUsableBytes..]

In the same way it is relatively easy to change toByteArray too.