Tedd.MortonEncoding 1.0.1

.NET Core 2.1 This package targets .NET Core 2.1. The package is compatible with this framework or higher. .NET Standard 1.0 This package targets .NET Standard 1.0. The package is compatible with this framework or higher. .NET Framework 4.6.1 This package targets .NET Framework 4.6.1. The package is compatible with this framework or higher. 
dotnet add package Tedd.MortonEncoding --version 1.0.1                

                    
                

            
NuGet\Install-Package Tedd.MortonEncoding -Version 1.0.1
This command is intended to be used within the Package Manager Console in Visual Studio, as it uses the NuGet module's version of Install-Package. 
<PackageReference Include="Tedd.MortonEncoding" Version="1.0.1" />
For projects that support PackageReference, copy this XML node into the project file to reference the package. 
paket add Tedd.MortonEncoding --version 1.0.1                

                    
                

            
#r "nuget: Tedd.MortonEncoding, 1.0.1"
#r directive can be used in F# Interactive and Polyglot Notebooks. Copy this into the interactive tool or source code of the script to reference the package. 
// Install Tedd.MortonEncoding as a Cake Addin
#addin nuget:?package=Tedd.MortonEncoding&version=1.0.1

// Install Tedd.MortonEncoding as a Cake Tool
#tool nuget:?package=Tedd.MortonEncoding&version=1.0.1

Tedd.MortonEncoding

Efficient z-order curve Morton encoder / decoder for .Net.

"Z-order, Lebesgue curve, Morton space filling curve, Morton order or Morton code map multidimensional data to one dimension while preserving locality of the data points." Wikipedia article.

Example

// Take some numbers that illustrate well
var x = (UInt32)0b00000000_00000000;
var y = (UInt32)0b00000000_11111111;

// Encode
var result = MortonEncoding.Encode(x, y);

// Test that result is now: 0b10101010_10101010
Assert.Equal("1010101010101010", Convert.ToString(result,2));

// Decode
MortonEncoding.Decode(result, out var xBack, out var yBack);

// Test that we got back the same values as we started with
Assert.Equal(x, xBack);
Assert.Equal(y, yBack);

Hardware accelleration

For .Net Core 3 and up CPU-instructions PEXT and PDEP are used to speed up calculations for CPU's that support BMI2. Most recent X86/X64 supports this.

In case of .Net 4, .Net core 1/2 and CPU's that don't support BMI2 a software implementation is automatically chosen instead. For those interested in the details: This approach uses AND, XOR and SHIFT operations to calculate the number. The calculations are around 13 instructions per dimension, so 26-40 instructions. Each calculation rely on the result of prior calculation so reciprocal throughput is not utilized.

The two other common approaches which are for-loop and lookup table are not implemented. The for-look introduces extra instructions for such a small operation. The lookup-table will perform well in a tight loop benchmark, but relies on lookup table occupying precious L1 cache and may cause extra latency if accessed in non-linear order where CPU prefetch is not able to assist (which is likely to happen).

A lookup-table approach is however used in xUnit test to verify the output from both BMI2 and manual bit operation approach.

Credits

Thanks to Jeroen Baert's blog entry, as well as Julien Bilalte's comment on using BMI2-instructions. The magic numbers and LUT-table helped a lot. LUT-table is used in xUnit tests to verify both BMI2 and manual calculations.

Product Compatible and additional computed target framework versions.
.NET net5.0 was computed.  net5.0-windows was computed.  net6.0 was computed.  net6.0-android was computed.  net6.0-ios was computed.  net6.0-maccatalyst was computed.  net6.0-macos was computed.  net6.0-tvos was computed.  net6.0-windows was computed.  net7.0 was computed.  net7.0-android was computed.  net7.0-ios was computed.  net7.0-maccatalyst was computed.  net7.0-macos was computed.  net7.0-tvos was computed.  net7.0-windows was computed.  net8.0 was computed.  net8.0-android was computed.  net8.0-browser was computed.  net8.0-ios was computed.  net8.0-maccatalyst was computed.  net8.0-macos was computed.  net8.0-tvos was computed.  net8.0-windows was computed. 
.NET Core netcoreapp1.0 was computed.  netcoreapp1.1 was computed.  netcoreapp2.0 was computed.  netcoreapp2.1 is compatible.  netcoreapp2.2 is compatible.  netcoreapp3.0 is compatible.  netcoreapp3.1 is compatible. 
.NET Standard netstandard1.0 is compatible.  netstandard1.1 is compatible.  netstandard1.2 is compatible.  netstandard1.3 is compatible.  netstandard1.4 is compatible.  netstandard1.5 is compatible.  netstandard1.6 is compatible.  netstandard2.0 is compatible.  netstandard2.1 is compatible. 
.NET Framework net45 was computed.  net451 was computed.  net452 was computed.  net46 was computed.  net461 is compatible.  net462 is compatible.  net463 was computed.  net47 is compatible.  net471 is compatible.  net472 is compatible.  net48 is compatible.  net481 was computed. 
MonoAndroid monoandroid was computed. 
MonoMac monomac was computed. 
MonoTouch monotouch was computed. 
Tizen tizen30 was computed.  tizen40 was computed.  tizen60 was computed. 
Universal Windows Platform uap was computed.  uap10.0 was computed. 
Windows Phone wp8 was computed.  wp81 was computed.  wpa81 was computed. 
Windows Store netcore was computed.  netcore45 was computed.  netcore451 was computed. 
Xamarin.iOS xamarinios was computed. 
Xamarin.Mac xamarinmac was computed. 
Xamarin.TVOS xamarintvos was computed. 
Xamarin.WatchOS xamarinwatchos was computed. 
Compatible target framework(s)
Included target framework(s) (in package)
Learn more about Target Frameworks and .NET Standard.

  • .NETCoreApp 2.1

    • No dependencies.

  • .NETCoreApp 2.2

    • No dependencies.

  • .NETCoreApp 3.0

    • No dependencies.

  • .NETCoreApp 3.1

    • No dependencies.

  • .NETFramework 4.6.1

    • No dependencies.

  • .NETFramework 4.6.2

    • No dependencies.

  • .NETFramework 4.7

    • No dependencies.

  • .NETFramework 4.7.1

    • No dependencies.

  • .NETFramework 4.7.2

    • No dependencies.

  • .NETFramework 4.8

    • No dependencies.

  • .NETStandard 1.0

  • .NETStandard 1.1

  • .NETStandard 1.2

  • .NETStandard 1.3

  • .NETStandard 1.4

  • .NETStandard 1.5

  • .NETStandard 1.6

  • .NETStandard 2.0

    • No dependencies.

  • .NETStandard 2.1

    • No dependencies.

NuGet packages

This package is not used by any NuGet packages.

GitHub repositories

This package is not used by any popular GitHub repositories.

Version Downloads Last updated
1.0.1 927 1/11/2020
1.0.0 510 1/9/2020

SplitXY and SplitXYZ