Tedd.MortonEncoding
1.0.1
Morton encoding and decoding for converting 2 and 3dimensional data to/from one dimension while preserving locality of the data points. In effect interleaving bits. See https://en.wikipedia.org/wiki/Zorder_curve
InstallPackage Tedd.MortonEncoding Version 1.0.1
dotnet add package Tedd.MortonEncoding version 1.0.1
<PackageReference Include="Tedd.MortonEncoding" Version="1.0.1" />
paket add Tedd.MortonEncoding version 1.0.1
#r "nuget: Tedd.MortonEncoding, 1.0.1"
// 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 zorder curve Morton encoder / decoder for .Net.
"Zorder, 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 CPUinstructions 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 2640 instructions. Each calculation rely on the result of prior calculation so reciprocal throughput is not utilized.
The two other common approaches which are forloop and lookup table are not implemented. The forlook introduces extra instructions for such a small operation. The lookuptable 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 nonlinear order where CPU prefetch is not able to assist (which is likely to happen).
A lookuptable 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 BMI2instructions. The magic numbers and LUTtable helped a lot. LUTtable is used in xUnit tests to verify both BMI2 and manual calculations.
Tedd.MortonEncoding
Efficient zorder curve Morton encoder / decoder for .Net.
"Zorder, 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 CPUinstructions 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 2640 instructions. Each calculation rely on the result of prior calculation so reciprocal throughput is not utilized.
The two other common approaches which are forloop and lookup table are not implemented. The forlook introduces extra instructions for such a small operation. The lookuptable 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 nonlinear order where CPU prefetch is not able to assist (which is likely to happen).
A lookuptable 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 BMI2instructions. The magic numbers and LUTtable helped a lot. LUTtable is used in xUnit tests to verify both BMI2 and manual calculations.
Release Notes
SplitXY and SplitXYZ
Dependencies

.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.Library (>= 1.6.1)

.NETStandard 1.1
 NETStandard.Library (>= 1.6.1)

.NETStandard 1.2
 NETStandard.Library (>= 1.6.1)

.NETStandard 1.3
 NETStandard.Library (>= 1.6.1)

.NETStandard 1.4
 NETStandard.Library (>= 1.6.1)

.NETStandard 1.5
 NETStandard.Library (>= 1.6.1)

.NETStandard 1.6
 NETStandard.Library (>= 1.6.1)

.NETStandard 2.0
 No dependencies.

.NETStandard 2.1
 No dependencies.
Used By
NuGet packages
This package is not used by any NuGet packages.
GitHub repositories
This package is not used by any popular GitHub repositories.