Nathan Evans' Nemesis of the Moment

Super fast way to extract width/height dimensions of PNG and JPEG images

Posted in .NET Framework, F# by Nathan B. Evans on April 17, 2015

Turns out that getting the width and height of an image file can be quite tricky if you don’t want to read the whole file into memory. The System.Drawing.Image type in .NET will read it all into memory; not good.

So I read the PNG and JPEG specifications and came up with this.

PNG was easy, as that has a static file header where the width and height are always stored in the same place. But JPEG is far far trickier since the header is built up of segments which are not in any particular order. There can be dozens of these header segments. There is always a particular segment called a Start Of Frame (SOF) which is the one that contains the width/height.

I’ve tried to build this as robustly and defensively as possible since I intend to use on both the server-side and on low memory mobile devices. It is also good at detecting invalid or malformed files and failing fast on those conditions.

It supports big and little endian architectures. And it supports memory streams, file streams and network streams i.e. both seekable and unseekable streams.

The JPEG implementation uses a little mutable state for performance and memory conservation reasons.

ImageSize for F#

/// Provides services to extract header or metadata information from image files of supported types.
module nbevans.Util.ImageSize =
    type DimensionsResult =
    | Success of Width : int * Height : int
    | Malformed of Information : string
    | NotSupported

    [<AutoOpen>]
    module private Utils =
        let ntoh buffer index length =
            if BitConverter.IsLittleEndian then Array.Reverse(buffer, index, length)
            buffer

        let ntoh_int32 buffer index =
            BitConverter.ToInt32(ntoh buffer index 4, index)

        let ntoh_int16 buffer index =
            BitConverter.ToInt16(ntoh buffer index 2, index)

        type Stream with
            /// Advances the position of the stream by seeking by a specified offset from the current position.
            /// Unlike Seek(), this method is safe for network streams and other types of stream where seeking is not possible.
            /// For these such "unseekable" streams, data will be read instead and immediately discarded.
            member stream.Advance(offset) =
                if stream.CanSeek then
                    stream.Seek(int64 offset, SeekOrigin.Current)
                else
                    let buffer = Array.zeroCreate offset
                    stream.Read(buffer, 0, offset) |> ignore
                    stream.Position

    module Png =
        /// Gets the width & height dimensions of a PNG image.
        let dimensions (sourceStream:Stream) =
            let signature = Array.zeroCreate 8
            if sourceStream.Read(signature, 0, 8) <> 8 || signature <> [| 137uy; 80uy; 78uy; 71uy; 13uy; 10uy; 26uy; 10uy |] then
                NotSupported
            else
                let chunk = Array.zeroCreate 8
                if sourceStream.Advance(8) <> 16L || sourceStream.Read(chunk, 0, 8) <> 8 then
                    Malformed "Expected chunk is not present."
                else
                    Success (ntoh_int32 chunk 0, ntoh_int32 chunk 4)

    module Jpeg =
        [<AutoOpen>]
        module private Markers =
            // All data markers are 2 bytes, where the first byte is a 0xFF prefix.
            let Prefix = 0xFFuy
            // The first data marker (i.e. first 2 bytes of the file) of every JPEG is this.
            let SOI_StartOfImage = 0xD8uy
            // JPEG has lots of different internal encoding types, which are indicated with a SOF data marker.
            // There are many like baseline, progressive, sequential, differential and various combinations of these too.
            // Fortunately the width/height is present in the same position of all of these SOF headers.
            let SOFn_StartOfFrame = [| 0xC0uy; 0xC1uy; 0xC2uy; 0xC3uy; 0xC5uy; 0xC6uy; 0xC7uy; 0xC9uy; 0xCAuy; 0xCBuy; 0xCDuy; 0xCEuy; 0xCFuy |]
            let SOS_StartOfScan = 0xDAuy

        /// Gets the width & height dimensions of a JPEG image.
        let dimensions (sourceStream:Stream) =
            let signature = Array.zeroCreate 2
            if sourceStream.Read(signature, 0, 2) <> 2 || signature.[0] <> Prefix || signature.[1] <> SOI_StartOfImage then
                NotSupported
            else
                let mutable result = Option<DimensionsResult>.None
                let marker = Array.zeroCreate 4

                while result.IsNone do
                    result <-
                        if sourceStream.Read(marker, 0, 4) <> 4 then
                            Some <| Malformed "Next data marker header cannot be read."
                        else
                            if marker.[0] = Prefix && SOFn_StartOfFrame |> Array.exists ((=) marker.[1]) then
                                // Reuse the marker array as a new buffer, skip over the first byte in the payload (which contains "sample precision"),
                                // and read the 4 bytes that contain two 16-bit values of the width and height, respectively.
                                let buffer = marker
                                sourceStream.Advance(1) |> ignore
                                if sourceStream.Read(buffer, 0, 4) <> 4 then
                                    Some <| Malformed "SOF data marker payload cannot be read."
                                else
                                    let lines = int <| ntoh_int16 buffer 0
                                    let samplesPerLine = int <| ntoh_int16 buffer 2
                                    Some <| Success (samplesPerLine, lines)

                            else if marker.[0] = Prefix && marker.[1] = SOS_StartOfScan then
                                // If we've reached the SOS marker then we missed the SOF marker.
                                // That's pretty bizarre and suggests a corrupt JPEG, or at least an unsupported SOF marker.
                                Some <| Malformed "SOS data marker was encountered prematurely."

                            else if marker.[0] <> Prefix then
                                // All data markers identifiers are 2 bytes and the first byte must be 0xFF.
                                Some <| Malformed "Next data marker header is malformed."

                            else
                                // After the data marker identifier is a 2 byte length (inclusive) of the payload.
                                // We need this to let us skip over the markers/payloads that are not interesting.
                                let length = (int <| ntoh_int16 marker 2) - 2
                                sourceStream.Advance(length) |> ignore
                                None

                defaultArg result (Malformed "End of data markers encountered prematurely.")
Advertisements
Tagged with: , , , , ,

Super skinny XML document generation with F#

Posted in .NET Framework, F# by Nathan B. Evans on April 15, 2015

I needed to generate some simple XML documents, in memory, from some F# script. From my C# days I was already familiar with the System.Xml.Linq namespace, which I still quite like. But it wasn’t particularly clean to use from F#. So I wrote a really simple F# wrapper for some of its most commonly used features.

XmlToolkit for F#

module nbevans.Util.XmlToolkit
open System.Text
open System.Xml
open System.Xml.Linq
open System.IO

let XDeclaration version encoding standalone = XDeclaration(version, encoding, standalone)
let XLocalName localName namespaceName = XName.Get(localName, namespaceName)
let XName expandedName = XName.Get(expandedName)
let XDocument xdecl content = XDocument(xdecl, content |> Seq.map (fun v -> v :> obj) |> Seq.toArray)
let XComment (value:string) = XComment(value) :> obj
let XElementNS localName namespaceName content = XElement(XLocalName localName namespaceName, content |> Seq.map (fun v -> v :> obj) |> Seq.toArray) :> obj
let XElement expandedName content = XElement(XName expandedName, content |> Seq.map (fun v -> v :> obj) |> Seq.toArray) :> obj
let XAttributeNS localName namespaceName value = XAttribute(XLocalName localName namespaceName, value) :> obj
let XAttribute expandedName value = XAttribute(XName expandedName, value) :> obj

type XDocument with
    /// Saves the XML document to a MemoryStream using UTF-8 encoding, indentation and character checking.
    member doc.Save() =
        let ms = new MemoryStream()
        use xtw = XmlWriter.Create(ms, XmlWriterSettings(Encoding = Encoding.UTF8, Indent = true, CheckCharacters = true))
        doc.Save(xtw)
        ms.Position <- 0L
        ms

The principle of this module is that it overrides the key type names like System.Xml.Linq.XElement and the others with F# functions that effectively provide the equivalent constructor behaviour but in a more functional signature. Then a XDocument type extension adds a useful Save() function (since the stock ones are so useless on their own). … and here is an example usage straight from my app (but hopefully you will get the idea):

let doc =
    XDocument (XDeclaration "1.0" "UTF-8" "yes") [
        XComment "This document was automatically generated by a configuration script."
        XElement "Metadata" [
            XElement "SystemMetadata" [
                XElement "ScannedBy" ["PCT"]
                XElement "GenerationDate" [DateTime.UtcNow.ToString("s")]
                XElement "IndexedBy" ["UNKNOWN"]
                XElement "IndexedOn" ["UNKNOWN"]
                XElement "FileName" [createPackageContentFileName cp.Id fileName]
                XElement "ScanInfo" [
                    XElement "NumberOfPagesScanned" [string formPdfPageCount]
                    XElement "IpAddress" ["UNKNOWN"]
                    XElement "MachineName" ["UNKNOWN"]
                    XElement "NumberOfBlankPages" ["0"]
                ]
            ]
            XElement "UserDefinedMetadata" [
                XElement "Address1" [defaultArg (gp.Fields.TryFind "property-address") "UNKNOWN"]
                XElement "Postcode" [defaultArg (gp.Fields.TryFind "property-postcode") "UNKNOWN"]
                XElement "Patchcode" ["1"]
                XElement "Reviewdate" [DateTime.UtcNow.AddYears(1).ToString("s")]
            ]
        ]
    ]

let ms = doc.Save()
// 'ms' at this point contains a System.IO.MemoryStream of the generated XML document.
// That was my use-case, but maybe you will want to adapt this code or the XmlToolkit module itself to use a different type of stream; perhaps a FileStream. I'm a firm believer in K.I.S.S to avoid over-engineering.
Tagged with: , , ,

Really simple way to split a F# sequence into chunks / partitions

Posted in .NET Framework, F# by Nathan B. Evans on March 13, 2014

I needed a simple function to split a (potentially infinite) sequence into chunks, suitable for processing. My exact use-case for this was actually in optimising my Azure blob storage uploads. I would split a sequence of 1,000s of items into batches of 60 or so items and then upload them concurrently across 60 connections to the Azure blob store. The performance benefits from this (after also messing around with ServicePointManager’s stupid connection limits and Nagle algorithm stuff) were simply staggering but that’s kind of another story.

I searched high and low for a suitable F# function to do this, but there was nothing. And all the samples I found on the web had design flaws or were overly complex. The design flaws were usually that it would seek the sequence more than once which is highly inefficient and could even cause side affects depending upon the source of the sequence.

I got frustrated and quickly wrote my own, though I will warn you that it uses mutable state. But as a result is very fast…

/// Returns a sequence that yields chunks of length n.
/// Each chunk is returned as an array.
let toChunks n (s:seq<'t>) = seq {
    let pos = ref 0
    let buffer = Array.zeroCreate<'t> n

    for x in s do
        buffer.[!pos] <- x
        if !pos = n - 1 then
            yield buffer |> Array.copy
            pos := 0
        else
            incr pos

    if !pos > 0 then
        yield Array.sub buffer 0 !pos
}

// Ridiculously imperative, but it works and is performant; won't seek the sequence more than once.
// If you're using in a forward-only manner and won't be holding references to the returned chunks
// then you can get rid of the Array.copy to gain some extra perf and reduce GC.

Here’s the Gist if that’s better for you: https://gist.github.com/nbevans/9429542

Oh, this is MIT licensed so you know that I won’t come calling.

Enjoy.

Tagged with: , ,

Quick and dirty literal port of my PBKDF2 password hash function from C# to F#

Posted in .NET Framework, F# by Nathan B. Evans on March 13, 2014

Now that I’m fully on board the F# bandwagon I’ve found myself wanting to refactor some of my old utility functions that I’ve had for years in C# land. Sure, I could just reference my C# assemblies, and probably should have. But there’s something nice about porting some code over to your shiny new language, if only just as a learning exercise.

module Crypto.Pbkdf2
open System
open System.Security.Cryptography

let private subkeyLength = 32
let private saltSize = 16

/// Hashes a password by a specified number of iterations using the PBKDF2 crypto function.
let hash password iterations =
    use algo = new Rfc2898DeriveBytes(password, saltSize, iterations)
    let salt = algo.Salt
    let bytes = algo.GetBytes(subkeyLength)

    let iters = if BitConverter.IsLittleEndian then BitConverter.GetBytes(iterations) else BitConverter.GetBytes(iterations) |> Array.rev

    let parts = Array.zeroCreate<byte> 54
    Buffer.BlockCopy(salt, 0, parts, 1, saltSize)
    Buffer.BlockCopy(bytes, 0, parts, 17, subkeyLength)
    Buffer.BlockCopy(iters, 0, parts, 50, sizeof<int>)

    Convert.ToBase64String(parts)

/// Hashes a password using 10,000 iterations of the PBKDF2 crypto function.
let fastHash password = hash password 10000

/// Hashes a password using 100,000 iterations of the PBKDF2 crypto function.
let strongHash password = hash password 100000

/// Hashes a password using 300,000 iterations of the PBKDF2 crypto function.
let uberHash password = hash password 300000

/// Verifies a PBKDF2 hashed password with a candidate password.
/// Returns true if the candidate password is correct.
/// The hashed password must have been originally generated by one of the hash functions within this module.
let verify hashedPassword (password:string) =
    let parts = Convert.FromBase64String(hashedPassword)
    if parts.Length <> 54 || parts.[0] <> byte 0 then
        false
    else
        let salt = Array.zeroCreate<byte> saltSize
        Buffer.BlockCopy(parts, 1, salt, 0, saltSize)

        let bytes = Array.zeroCreate<byte> subkeyLength
        Buffer.BlockCopy(parts, 17, bytes, 0, subkeyLength)

        let iters = Array.zeroCreate<byte> sizeof<int>
        Buffer.BlockCopy(parts, 50, iters, 0, sizeof<int>);

        let iters = if BitConverter.IsLittleEndian then iters else iters |> Array.rev

        let iterations = BitConverter.ToInt32(iters, 0)

        use algo = new Rfc2898DeriveBytes(password, salt, iterations)
        let challengeBytes = algo.GetBytes(32)

        match Seq.compareWith (fun a b -> if a = b then 0 else 1) bytes challengeBytes with
        | v when v = 0 -> true
        | _ -> false

Here’s the Gist, if it’s better for you: https://gist.github.com/nbevans/9519088

Sure the code is quite imperative in style, but it is just a utility function and I literally did a “one pass” refactor from the C# code. It’s not really worth giving a second pass just for the sake of making it more pure functional.

This is MIT licensed by the way. I ain’t going to come calling.

Enjoy.

Tagged with: , , ,