Collaborative drawing canvas using SIMD-powered Shelf conflict resolution algorithm

Canvas.fs

(*
 * Copyright 2022 Bartosz Sypytkowski
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *)
namespace Demo.Canvas

open System
open System.Numerics

type Bitmap = uint[]

/// A canvas Conflict-free replicated data type. It allows uses to
/// concurrently draw pixels and uses Shelf merge resolution
/// algorithm to deal with conflicting updates.
[<NoComparison; NoEquality>]
type Canvas =
    { width: int
      height: int
      mutable pixels: Bitmap     // RGBA pixels to be displayed
      mutable versions: Bitmap } // versions used for conflict resolution
    
[<RequireQualifiedAccess>]
module Canvas =
    
    let create width height =
        let total = width * height
        { width = width
          height = height
          pixels = Array.zeroCreate total
          versions = Array.zeroCreate total }
        
    /// Draws a single pixel at coordinates (`w`,`h`) using provided `colour`.
    let draw colour w h canvas =
        let offset = h * canvas.width + w
        // set pixel at the offset to a given colour
        canvas.pixels[offset] <- colour  
        // increment version number of modified pixel
        canvas.versions[offset] <- canvas.versions[offset] + 1u 
        
    /// We merge from `a` into `b`. Conflict resolution is a follows:
    /// 1. for corresponding pixels compare numbers from versions bitmap
    /// 2. if `a`'s version for a pixel was higher, use pixel from `a`
    /// 3. if `b`'s version for a pixel was higher, use pixel from `b`
    /// 4. if versions where equal use "brighter" pixel (one with higher color value)
    let merge a b =
        assert (a.versions.Length = a.pixels.Length &&
                b.versions.Length = b.pixels.Length &&
                b.versions.Length = a.versions.Length)
        let mutable i = 0
        
        // SIMD loop
        while i + Vector<uint>.Count <= a.versions.Length do
            let avv = Vector(a.versions, i) // a versions vector
            let apv = Vector(a.pixels, i)   // a pixels vector
            let bvv = Vector(b.versions, i) // b versions vector
            let bpv = Vector(b.pixels, i)   // b pixels vector
            // create mask for pixels where `a` version is greater
            let ma = Vector.GreaterThanOrEqual(avv, bvv)
            // create mask for pixels where `b` version is greater
            let mb = Vector.GreaterThanOrEqual(bvv, avv)
            // apply both masks to pixels and take the max of them
            let result = Vector.Max(Vector.BitwiseAnd(ma, apv), Vector.BitwiseAnd(mb, bpv))
            // write merge result back to `b`
            result.CopyTo(b.pixels, i)
            // take max of `a` and `b` versions and write them to `b`
            Vector.Max(avv, bvv).CopyTo(b.versions, i)
            i <- i + Vector<uint>.Count
            
        // slow loop used when remainder of a bitmap doesn't
        // fit SIMD registers
        while i < a.versions.Length do
            let bv = b.versions[i]
            let av = a.versions[i]
            let cmp = bv.CompareTo av
            if cmp < 0 then
                b.pixels[i] <- a.pixels[i]
            elif cmp = 0 then
                b.pixels[i] <- Math.Max(b.pixels[i], a.pixels[i])
            b.versions[i] <- Math.Max(bv, av)
            i <- i + 1

Canvas.Tests.fs

module Demo.Canvas.Tests

open System
open System.IO
open System.Runtime.InteropServices
open SkiaSharp

let [<Literal>] RED   = 0xff0000ffu
let [<Literal>] YELLOW = 0xee22eeffu
let [<Literal>] WIDTH = 1920
let [<Literal>] HEIGHT = 1024
    
let save fpath canvas =    
    let slice = ReadOnlySpan(canvas.pixels)
    let bytes: ReadOnlySpan<byte> = MemoryMarshal.Cast(slice)
    let info = SKImageInfo(WIDTH, HEIGHT, SKColorType.Rgba8888)
    let image = SKImage.FromPixelCopy(info, bytes)
    
    use data = image.Encode(SKEncodedImageFormat.Png, 80)
    use stream = File.OpenWrite fpath
    data.SaveTo stream

let test () =
    let canvas1 = Canvas.create WIDTH HEIGHT
    let canvas2 = Canvas.create WIDTH HEIGHT
    
    // draw 2/3 of the upper-left part of canvas red
    for w in 0..int(float(WIDTH) * 0.67) do
      for h in 0..int(float(HEIGHT) * 0.67) do
          Canvas.draw RED w h canvas1
    save "./red.png" canvas1
          
    // draw 2/3 of the lower-right part of canvas yellow
    for w in int(float(WIDTH) * 0.33)..(WIDTH-1) do
      for h in int(float(HEIGHT) * 0.33)..(HEIGHT-1) do
          Canvas.draw YELLOW w h canvas2
    save "./yellow.png" canvas2
          
    Canvas.merge canvas2 canvas1
    save "./merged.png" canvas1