login  home  contents  what's new  discussion  bug reports     help  links  subscribe  changes  refresh  edit
SandBox
HyperG  ← ↑ →  NumericalQuadrature

MortonCode
  
last edited 15 years ago by Bill Page

Edit detail for MortonCode revision 2 of 4
1 2 3 4
Editor: Bill Page
Time: 2009/11/04 21:37:13 GMT-8
Note: fast bit twiddling 
added:
Interleave bits by Binary Magic Numbers

  This is a fast bit manipulation for combining two hash codes that does not use MOD of a large prime number. Based on the an algorithm by By Sean Eron Anderson.

Ref: http://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN

\begin{spad}
)abbrev package MORTON Morton
Morton() : with
    morton2: (SingleInteger,SingleInteger) -> SingleInteger
  == add

    -- Shift lower 16 bits of x to even positions of 32 bit word
    spread(x:SingleInteger):SingleInteger ==
      x := LOGAND(x,65535)$Lisp -- 16rFFFF = 2^16-1
      x := LOGAND(LOGIOR(x,ASH(x,8)$Lisp)$Lisp,16711935)$Lisp   -- 16r00FF00FF
      x := LOGAND(LOGIOR(x,ASH(x,4)$Lisp)$Lisp,252645135)$Lisp  -- 16r0F0F0F0F
      x := LOGAND(LOGIOR(x,ASH(x,2)$Lisp)$Lisp,858993459)$Lisp  -- 16r33333333
      x := LOGAND(LOGIOR(x,ASH(x,1)$Lisp)$Lisp,1431655765)$Lisp -- 16r55555555

    -- Interleave bits of x and y so the bits of x are in the odd positions
    -- and the bits of y are in the even positions of a 29 bit SingleInteger
    morton2(x:SingleInteger, y:SingleInteger):SingleInteger ==
      LOGAND(LOGIOR(spread y,ASH(spread x,1)$Lisp)$Lisp,536870911)$Lisp
      -- 16r1FFFFFFF = 2^29 -1
\end{spad}

\begin{axiom}
matrix [[morton2(hash i,hash j) for j in 1..5] for i in 1..5]
\end{axiom}

References to Morton codes:

axiom
-- i'th group of n bits of h
bits(h,n,i) == And(mask n,shift(h,-n*i))
Type: Void
axiom
-- mix groups of n bits of h with groups of m bits of k
morton(h,n,k,m) ==
 r:SingleInteger:=0
 if n+m > 0 then
   i:=0
   -- stop before fixnum overflow
   while (i+1)*(n+m) <= 29 repeat
     mix:=Or(shift(bits(h,n,i),m),bits(k,m,i))
     r:=Or(r,shift(mix,i*(n+m)))
     i:=i+1
 r
Type: Void
axiom
listHash(l) ==
 r:SingleInteger:=0
 i:=0
 while not empty?(l) repeat
   -- equalize hash weight by number of elements
   r:=morton(r,i,hash first l,1)
   l:=rest l
   i:=i+1
 r
Type: Void

axiom
[hash i for i in 1..5]
\label{eq1}\left[{361475674}, \:{361475691}, \:{361475707}, \:{361475592}, \:{361475608}\right](1)
 
Type: List(Integer)
axiom
[morton(0,0,hash i,1) for i in 1..5]
axiom
Compiling function bits with type (NonNegativeInteger,
      NonNegativeInteger,NonNegativeInteger) -> SingleInteger
axiom
Compiling function bits with type (Integer,PositiveInteger,
      NonNegativeInteger) -> SingleInteger
axiom
Compiling function morton with type (NonNegativeInteger,
      NonNegativeInteger,Integer,PositiveInteger) -> SingleInteger
\label{eq2}\left[{361475674}, \:{361475691}, \:{361475707}, \:{361475592}, \:{361475608}\right](2)
 
Type: List(SingleInteger)
axiom
listHash([1])
axiom
Compiling function bits with type (SingleInteger,NonNegativeInteger,
      NonNegativeInteger) -> SingleInteger
axiom
Compiling function morton with type (SingleInteger,
      NonNegativeInteger,Integer,PositiveInteger) -> SingleInteger
axiom
Compiling function listHash with type List(PositiveInteger) -> 
      SingleInteger
\label{eq3}361475674(3)
 
Type: SingleInteger
axiom
matrix [[listHash([i,j]) for j in 1..5] for i in 1..5]
\label{eq4}\left[ \begin{array}{ccccc} {217854924}&{217855693}&{217855949}&{217850568}&{217850824} \ {217856462}&{217857231}&{217857487}&{217852106}&{217852362} \ {217856974}&{217857743}&{217857999}&{217852618}&{217852874} \ {217846212}&{217846981}&{217847237}&{217841856}&{217842112} \ {217846724}&{217847493}&{217847749}&{217842368}&{217842624} (4)
 
Type: Matrix(SingleInteger)
axiom
matrix [[listHash([1,i,j]) for j in 1..5] for i in 1..5]
\label{eq5}\left[ \begin{array}{ccccc} {1867320}&{1895993}&{1900089}&{1601072}&{1605168} \ {1924666}&{1953339}&{1957435}&{1658418}&{1662514} \ {1932858}&{1961531}&{1965627}&{1666610}&{1670706} \ {1334824}&{1363497}&{1367593}&{1068576}&{1072672} \ {1343016}&{1371689}&{1375785}&{1076768}&{1080864} (5)
 
Type: Matrix(SingleInteger)
axiom
matrix [[listHash([2,i,j]) for j in 1..5] for i in 1..5]
\label{eq6}\left[ \begin{array}{ccccc} {1982012}&{2010685}&{2014781}&{1715764}&{1719860} \ {2039358}&{2068031}&{2072127}&{1773110}&{1777206} \ {2047550}&{2076223}&{2080319}&{1781302}&{1785398} \ {1449516}&{1478189}&{1482285}&{1183268}&{1187364} \ {1457708}&{1486381}&{1490477}&{1191460}&{1195556} (6)
 
Type: Matrix(SingleInteger)

Interleave bits by Binary Magic Numbers

This is a fast bit manipulation for combining two hash codes that does not use MOD of a large prime number. Based on the an algorithm by By Sean Eron Anderson.

Ref: http://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN

spad
)abbrev package MORTON Morton
Morton() : with
    morton2: (SingleInteger,SingleInteger) -> SingleInteger
  == add

    -- Shift lower 16 bits of x to even positions of 32 bit word
    spread(x:SingleInteger):SingleInteger ==
      x := LOGAND(x,65535)$Lisp -- 16rFFFF = 2^16-1
      x := LOGAND(LOGIOR(x,ASH(x,8)$Lisp)$Lisp,16711935)$Lisp   -- 16r00FF00FF
      x := LOGAND(LOGIOR(x,ASH(x,4)$Lisp)$Lisp,252645135)$Lisp  -- 16r0F0F0F0F
      x := LOGAND(LOGIOR(x,ASH(x,2)$Lisp)$Lisp,858993459)$Lisp  -- 16r33333333
      x := LOGAND(LOGIOR(x,ASH(x,1)$Lisp)$Lisp,1431655765)$Lisp -- 16r55555555

    -- Interleave bits of x and y so the bits of x are in the odd positions
    -- and the bits of y are in the even positions of a 29 bit SingleInteger
    morton2(x:SingleInteger, y:SingleInteger):SingleInteger ==
      LOGAND(LOGIOR(spread y,ASH(spread x,1)$Lisp)$Lisp,536870911)$Lisp
      -- 16r1FFFFFFF = 2^29 -1
spad
   Compiling FriCAS source code from file 
      /var/zope2/var/LatexWiki/3849729568657923935-25px003.spad using 
      old system compiler.
   MORTON abbreviates package Morton 
------------------------------------------------------------------------
   initializing NRLIB MORTON for Morton 
   compiling into NRLIB MORTON 
   compiling local spread : SingleInteger -> SingleInteger
Time: 0.05 SEC.

   compiling exported morton2 : (SingleInteger,SingleInteger) -> SingleInteger
Time: 0.01 SEC.

(time taken in buildFunctor:  0)

;;;     ***       |Morton| REDEFINED

;;;     ***       |Morton| REDEFINED
Time: 0 SEC.

   Cumulative Statistics for Constructor Morton
      Time: 0.06 seconds

   finalizing NRLIB MORTON 
   Processing Morton for Browser database:
--->-->Morton((morton2 ((SingleInteger) (SingleInteger) (SingleInteger)))): Not documented!!!!
--->-->Morton(constructor): Not documented!!!!
--->-->Morton(): Missing Description
; compiling file "/var/zope2/var/LatexWiki/MORTON.NRLIB/MORTON.lsp" (written 04 NOV 2009 09:36:48 PM):
; compiling (/VERSIONCHECK 2)
; compiling (DEFUN |MORTON;spread| ...)
; compiling (DEFUN |MORTON;morton2;3Si;2| ...)
; compiling (DEFUN |Morton| ...)
; compiling (DEFUN |Morton;| ...)
; compiling (MAKEPROP (QUOTE |Morton|) ...)
; compiling (MAKEPROP (QUOTE |Morton|) ...)

; /var/zope2/var/LatexWiki/MORTON.NRLIB/MORTON.fasl written
; compilation finished in 0:00:00.071
------------------------------------------------------------------------
   Morton is now explicitly exposed in frame initial 
   Morton will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/MORTON.NRLIB/MORTON

axiom
matrix [[morton2(hash i,hash j) for j in 1..5] for i in 1..5]
\label{eq7}\left[ \begin{array}{ccccc} {217854924}&{217855693}&{217855949}&{217850568}&{217850824} \ {217856462}&{217857231}&{217857487}&{217852106}&{217852362} \ {217856974}&{217857743}&{217857999}&{217852618}&{217852874} \ {217846212}&{217846981}&{217847237}&{217841856}&{217842112} \ {217846724}&{217847493}&{217847749}&{217842368}&{217842624} (7)
 
Type: Matrix(SingleInteger)