4
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ While writing the functions i already thought that the mutable stuff would'nt be the optimal way, but since i'm not that familiar with all higher order functions yet, i really appreciate the feedback. \$\endgroup\$ – Streamline Jun 16 at 14:15
  • 2
    \$\begingroup\$ @Streamline: If you come from with a OO background as I do, it can be tempting to jump to the well known - but we then miss the best part of F# and FP. It took me some time to get familiar with the "awkward" concept of immutability, but the effort has paid off - also in respect to my understanding of OOP. \$\endgroup\$ – Henrik Hansen Jun 16 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.