Tedd.MortonEncoding 1.0.1

Morton encoding and decoding for converting 2 and 3-dimensional data to/from one dimension while preserving locality of the data points. In effect interleaving bits. See https://en.wikipedia.org/wiki/Z-order_curve

Install-Package Tedd.MortonEncoding -Version 1.0.1
dotnet add package Tedd.MortonEncoding --version 1.0.1
<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
The NuGet Team does not provide support for this client. Please contact its maintainers for support.
#r "nuget: Tedd.MortonEncoding, 1.0.1"
#r directive can be used in F# Interactive, C# scripting and .NET Interactive. 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
The NuGet Team does not provide support for this client. Please contact its maintainers for support.

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.

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.

Release Notes

SplitXY and SplitXYZ

  • .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 History

Version Downloads Last updated
1.0.1 216 1/11/2020
1.0.0 212 1/9/2020