1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// Filename: hilbert.c
//
// Purpose: Hilbert and Linked-list utility procedures for BayeSys3.
//
// History: TreeSys.c 17 Apr 1996 - 31 Dec 2002
// Peano.c 10 Apr 2001 - 11 Jan 2003
// merged 1 Feb 2003
// Arith debug 28 Aug 2003
// Hilbert.c 14 Oct 2003
// 2 Dec 2003
//-----------------------------------------------------------------------------
/*
Copyright (c) 1996-2003 Maximum Entropy Data Consultants Ltd,
114c Milton Road, Cambridge CB4 1XE, England
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
#include "license.txt"
*/
#include <stdio.h>
typedef unsigned int coord_t; // char,short,int for up to 8,16,32 bits per word
static void TransposetoAxes(
coord_t* X, // I O position [n]
int b, // I # bits
int n) // I dimension
{
coord_t M, P, Q, t;
int i;
// Gray decode by H ^ (H/2)
t = X[n-1] >> 1;
for( i = n-1; i; i-- )
X[i] ^= X[i-1];
X[0] ^= t;
// Undo excess work
M = 2 << (b - 1);
for( Q = 2; Q != M; Q <<= 1 )
{
P = Q - 1;
for( i = n-1; i; i-- )
if( X[i] & Q ) X[0] ^= P; // invert
else{ t = (X[0] ^ X[i]) & P; X[0] ^= t; X[i] ^= t; } // exchange
if( X[0] & Q ) X[0] ^= P; // invert
}
}
static void AxestoTranspose(
coord_t* X, // I O position [n]
int b, // I # bits
int n) // I dimension
{
coord_t P, Q, t;
int i;
// Inverse undo
for( Q = 1 << (b - 1); Q > 1; Q >>= 1 )
{
P = Q - 1;
if( X[0] & Q ) X[0] ^= P; // invert
for( i = 1; i < n; i++ )
if( X[i] & Q ) X[0] ^= P; // invert
else{ t = (X[0] ^ X[i]) & P; X[0] ^= t; X[i] ^= t; } // exchange
}
// Gray encode (inverse of decode)
for( i = 1; i < n; i++ )
X[i] ^= X[i-1];
t = X[n-1];
for( i = 1; i < b; i <<= 1 )
X[n-1] ^= X[n-1] >> i;
t ^= X[n-1];
for( i = n-2; i >= 0; i-- )
X[i] ^= t;
}
/* This is an sample use of Skilling's functions above.
* You will need to modify the code if the value of BITS or DIMS is changed.
* The the output of this can be used to order the node name entries in slurm.conf */
#define BITS 5 /* number of bits used to store the axis values, size of Hilbert space */
#define DIMS 3 /* number of dimensions in the Hilbert space */
main(int argc, char **argv)
{
int i, H;
coord_t X[DIMS]; // any position in 32x32x32 cube for BITS=5
if (argc != (DIMS + 1)) {
printf("Usage %s X Y Z\n", argv[0]);
exit(1);
}
for (i=0; i<DIMS; i++)
X[i] = atoi(argv[i+1]);
printf("Axis coordinates = %d %d %d\n", X[0], X[1], X[2]);
AxestoTranspose(X, BITS, DIMS); // Hilbert transpose for 5 bits and 3 dimensions
H = ((X[2]>>0 & 1) << 0) + ((X[1]>>0 & 1) << 1) + ((X[0]>>0 & 1) << 2) +
((X[2]>>1 & 1) << 3) + ((X[1]>>1 & 1) << 4) + ((X[0]>>1 & 1) << 5) +
((X[2]>>2 & 1) << 6) + ((X[1]>>2 & 1) << 7) + ((X[0]>>2 & 1) << 8) +
((X[2]>>3 & 1) << 9) + ((X[1]>>3 & 1) << 10) + ((X[0]>>3 & 1) << 11) +
((X[2]>>4 & 1) << 12) + ((X[1]>>4 & 1) << 13) + ((X[0]>>4 & 1) << 14);
printf("Hilbert integer = %d (%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d)\n", H,
X[0]>>4 & 1, X[1]>>4 & 1, X[2]>>4 & 1, X[0]>>3 & 1, X[1]>>3 & 1,
X[2]>>3 & 1, X[0]>>2 & 1, X[1]>>2 & 1, X[2]>>2 & 1, X[0]>>1 & 1,
X[1]>>1 & 1, X[2]>>1 & 1, X[0]>>0 & 1, X[1]>>0 & 1, X[2]>>0 & 1);
#if 0
/* Used for validation purposes */
TransposetoAxes(X, BITS, DIMS); // Hilbert transpose for 5 bits and 3 dimensions
printf("Axis coordinates = %d %d %d\n", X[0], X[1], X[2]);
#endif
}
|
