mortif Module

  1. mortif.f90
  2. mortif

  • Uses:

  • penf
module~~mortif~~UsesGraph module~mortif mortif penf penf penf->module~mortif
Help

MORTIF, MORTon Indexer (Z-order) Fortran environment.

A library to encode/decode integer indexes into Morton's (Z-order) ordering. Morton's code (Z-order) is a scheme to map multi-dimensional arrays onto to a linear with a great deal of spatial locality.

References

[1] A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing, Morton G.M., technical report, IBM, 1966. [2] On Spatial Orders and Location Codes, Stocco, LJ and Schrack, G, IEEE Transaction on Computers, vol 58, n 3, March 2009. [3] Out-of-Core Construction of Sparse Voxel Octrees, J. Baert, A. Lagae and Ph. Dutré, Proceedings of the Fifth ACM SIGGRAPH/Eurographics conference on High-Performance Graphics, 2013.

Used By

module~~mortif~~UsedByGraph module~mortif mortif program~mortif_test_correctness mortif_test_correctness module~mortif->program~mortif_test_correctness
Help

Variables

Functions

Subroutines


Variables

TypeVisibility AttributesNameInitial
integer(kind=I8P), private, parameter:: mask32_32 =int(Z'FFFFFFFF', I8P)

0000000000000000000000000000000011111111111111111111111111111111.
integer(kind=I8P), private, parameter:: mask16_48 =int(Z'FFFF', I8P)

0000000000000000000000000000000000000000000000001111111111111111.
integer(kind=I8P), private, parameter:: mask16_32 =int(Z'FFFF00000000FFFF', I8P)

1111111111111111000000000000000000000000000000001111111111111111.
integer(kind=I8P), private, parameter:: mask16_16 =int(Z'FFFF0000FFFF', I8P)

0000000000000000111111111111111100000000000000001111111111111111.
integer(kind=I8P), private, parameter:: mask8_56 =int(Z'FF', I8P)

0000000000000000000000000000000000000000000000000000000011111111.
integer(kind=I8P), private, parameter:: mask8_16 =int(Z'FF0000FF0000FF', I8P)

0000000011111111000000000000000011111111000000000000000011111111.
integer(kind=I8P), private, parameter:: mask8_8 =int(Z'FF00FF00FF00FF', I8P)

0000000011111111000000001111111100000000111111110000000011111111.
integer(kind=I8P), private, parameter:: mask4_60 =int(Z'F', I8P)

0000000000000000000000000000000000000000000000000000000000001111.
integer(kind=I8P), private, parameter:: mask4_8 =int(Z'F00F00F00F00F00F', I8P)

1111000000001111000000001111000000001111000000001111000000001111.
integer(kind=I8P), private, parameter:: mask4_4 =int(Z'F0F0F0F0F0F0F0F', I8P)

0000111100001111000011110000111100001111000011110000111100001111.
integer(kind=I8P), private, parameter:: mask2_62 =int(Z'3', I8P)

0000000000000000000000000000000000000000000000000000000000000011.
integer(kind=I8P), private, parameter:: mask2_4 =int(z'30C30C30C30C30C3', I8P)

0011000011000011000011000011000011000011000011000011000011000011.
integer(kind=I8P), private, parameter:: mask2_2 =int(Z'3333333333333333', I8P)

0011001100110011001100110011001100110011001100110011001100110011.
integer(kind=I8P), private, parameter:: mask1_2 =int(Z'9249249249249249', I8P)

1001001001001001001001001001001001001001001001001001001001001001.
integer(kind=I8P), private, parameter:: mask1_1 =int(Z'5555555555555555', I8P)

0101010101010101010101010101010101010101010101010101010101010101.
integer(kind=I8P), private, parameter:: signif(1:5) =[mask2_62, mask4_60, mask8_56, mask16_48, mask32_32]

Binary mask for selecting significant bits.
integer(kind=I8P), private, parameter:: mask(1:6,1:2) =reshape([mask1_1, mask2_2, mask4_4, mask8_8, mask16_16, mask32_32, mask1_2, mask2_4, mask4_8, mask8_16, mask16_32, mask32_32], [6, 2])

Binary mask for perfoming significant bits shifting.
integer(kind=I1P), private, parameter:: shft(1:6,1:2) =reshape([1_I1P, 2_I1P, 4_I1P, 8_I1P, 16_I1P, 32_I1P, 2_I1P, 4_I1P, 8_I1P, 16_I1P, 32_I1P, 64_I1P], [6, 2])

Shift number array.
real(kind=R4P), private, parameter:: log10_2_inv =1._R4P/log10(2._R4P)

Real parameter for computing the number of shifts (Ns).

The number of shifts is computed by \(2^{Ns}=b\) where b is the significant bits. As a consequence \(Ns=\frac{log(b)}{log2}\) therefore it is convenient to store the value of \(\frac{1}{log2}\).

Functions

private elemental function dilatate(i, b, z) result(d)

Dilatate integer of 32 bits to integer of 64 bits.

Arguments

Type IntentOptional AttributesName
integer(kind=I4P), intent(in) :: i

Input integer.
integer(kind=I2P), intent(in) :: b

Number of significant bits of 'i' (2/4/8/16/32).
integer(kind=I1P), intent(in) :: z

Number of zero 'i' (1/2).

Return Value integer(kind=I8P)

Dilated integer.

public elemental function morton2D(i, j, b) result(code)

Encode 2 integer (32 bits) indexes into 1 integer (64 bits) Morton's code.

Arguments

Type IntentOptional AttributesName
integer(kind=I4P), intent(in) :: i

I index.
integer(kind=I4P), intent(in) :: j

J index.
integer(kind=I2P), intent(in), optional :: b

Number of significant bits of 'i' (2/4/8/16/32).

Return Value integer(kind=I8P)

Morton's code.

public elemental function morton3D(i, j, k, b) result(code)

Encode 3 integer (32 bits) indexes into 1 integer (64 bits) Morton's code.

Arguments

Type IntentOptional AttributesName
integer(kind=I4P), intent(in) :: i

I index.
integer(kind=I4P), intent(in) :: j

J index.
integer(kind=I4P), intent(in) :: k

K index.
integer(kind=I2P), intent(in), optional :: b

Number of significant bits of 'i' (2/4/8/16/32).

Return Value integer(kind=I8P)

Morton's code.


Subroutines

private elemental subroutine contract(i, b, z, c)

Contract integer of 64 bits into integer of 32 bits.

Arguments

Type IntentOptional AttributesName
integer(kind=I8P), intent(in) :: i

Input integer.
integer(kind=I2P), intent(in) :: b

Number of significant bits of 'i' (2/4/8/16/32).
integer(kind=I1P), intent(in) :: z

Number of zero 'i' (1/2).
integer(kind=I4P), intent(out) :: c

Contracted integer.

public elemental subroutine demorton2D(code, i, j, b)

Decode 1 integer (64 bits) Morton's code into 2 integer (32 bits) indexes.

Arguments

Type IntentOptional AttributesName
integer(kind=I8P), intent(in) :: code

Morton's code.
integer(kind=I4P), intent(inout) :: i

I index.
integer(kind=I4P), intent(inout) :: j

J index.
integer(kind=I2P), intent(in), optional :: b

Number of significant bits of 'i' (2/4/8/16/32).

public elemental subroutine demorton3D(code, i, j, k, b)

Decode 1 integer (64 bits) Morton's code into 3 integer (16 bits) indexes.

Arguments

Type IntentOptional AttributesName
integer(kind=I8P), intent(in) :: code

Morton's code.
integer(kind=I4P), intent(inout) :: i

I index.
integer(kind=I4P), intent(inout) :: j

J index.
integer(kind=I4P), intent(inout) :: k

K index.
integer(kind=I2P), intent(in), optional :: b

Number of significant bits of 'i' (2/4/8/16).

All Modules