Skip to content

Instantly share code, notes, and snippets.

@Horusiath
Last active January 22, 2023 22:48
Show Gist options
  • Save Horusiath/c1d8f5babd8b3931aa8a35184c7a5974 to your computer and use it in GitHub Desktop.
Save Horusiath/c1d8f5babd8b3931aa8a35184c7a5974 to your computer and use it in GitHub Desktop.
Collaborative drawing canvas using SIMD-powered Shelf conflict resolution algorithm
(*
* 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
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment