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

# Edit detail for MortonCode revision 4 of 4

 1 2 3 4 Editor: Bill Page Time: 2009/11/04 23:32:41 GMT-8 Note: Lebesgue curves

changed:
-References to Morton codes:
References to Morton codes (also known as z-order and Lebesgue curves):

- http://www.mathcurve.com/fractals/lebesgue/lebesgue.shtml


References to Morton codes (also known as z-order and Lebesgue curves):

fricas
-- i'th group of n bits of h
bits(h,n,i) == And(mask n,shift(h,-n*i))
Type: Void
fricas
-- 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
fricas
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

fricas
[hash i for i in 1..5]
 (1)
Type: List(SingleInteger?)
fricas
[morton(0,0,hash i,1) for i in 1..5]
fricas
Compiling function bits with type (NonNegativeInteger,
NonNegativeInteger, NonNegativeInteger) -> SingleInteger
fricas
Compiling function bits with type (SingleInteger, PositiveInteger,
NonNegativeInteger) -> SingleInteger
fricas
Compiling function morton with type (NonNegativeInteger,
NonNegativeInteger, SingleInteger, PositiveInteger) ->
SingleInteger
 (2)
Type: List(SingleInteger?)
fricas
listHash([1])
fricas
Compiling function bits with type (SingleInteger, NonNegativeInteger
, NonNegativeInteger) -> SingleInteger
fricas
Compiling function morton with type (SingleInteger,
NonNegativeInteger, SingleInteger, PositiveInteger) ->
SingleInteger
fricas
Compiling function listHash with type List(PositiveInteger) ->
SingleInteger
 (3)
Type: SingleInteger?
fricas
matrix [[listHash([i,j]) for j in 1..5] for i in 1..5]
 (4)
Type: Matrix(SingleInteger?)
fricas
matrix [[listHash([1,i,j]) for j in 1..5] for i in 1..5]
 (5)
Type: Matrix(SingleInteger?)
fricas
matrix [[listHash([2,i,j]) for j in 1..5] for i in 1..5]
 (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.

)abbrev package MORTON Morton
Morton() : with
morton2: (SingleInteger,SingleInteger) -> SingleInteger
-- Shift lower 16 bits of x to even positions of 32 bit word
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
   Compiling FriCAS source code from file
using old system compiler.
MORTON abbreviates package Morton
------------------------------------------------------------------------
initializing NRLIB MORTON for Morton
compiling into NRLIB MORTON
compiling local spread : SingleInteger -> SingleInteger
Time: 0.01 SEC.
compiling exported morton2 : (SingleInteger,SingleInteger) -> SingleInteger
Time: 0 SEC.
(time taken in buildFunctor:  0)
;;;     ***       |Morton| REDEFINED
;;;     ***       |Morton| REDEFINED
Time: 0 SEC.
Cumulative Statistics for Constructor Morton
Time: 0.01 seconds
finalizing NRLIB MORTON
Processing Morton for Browser database:
--->-->Morton(constructor): Not documented!!!!
--->-->Morton((morton2 ((SingleInteger) (SingleInteger) (SingleInteger)))): Not documented!!!!
--->-->Morton(): Missing Description
; compiling file "/var/aw/var/LatexWiki/MORTON.NRLIB/MORTON.lsp" (written 04 APR 2022 07:28:32 PM):
; /var/aw/var/LatexWiki/MORTON.NRLIB/MORTON.fasl written
; compilation finished in 0:00:00.012
------------------------------------------------------------------------
Morton is now explicitly exposed in frame initial
Morton will be automatically loaded when needed from
/var/aw/var/LatexWiki/MORTON.NRLIB/MORTON

fricas
matrix [[morton2(hash i,hash j) for j in 1..5] for i in 1..5]
 (7)
Type: Matrix(SingleInteger?)