login  home  contents  what's new  discussion  bug reports     help  links  subscribe  changes  refresh  edit

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)