hilbert2d.c 4.73 KB
Newer Older
1
#include "dev/excit.h"
2
3
#include "hilbert2d.h"

Brice Videau's avatar
Brice Videau committed
4
5
6
/* Helper functions from: https://en.wikipedia.org/wiki/Hilbert_curve */

//rotate/flip a quadrant appropriately
7
8
static void rot(ssize_t n, ssize_t *x, ssize_t *y, ssize_t rx, ssize_t ry)
{
9
10
11
12
13
14
15
16
17
18
19
	if (ry == 0) {
		if (rx == 1) {
			*x = n - 1 - *x;
			*y = n - 1 - *y;
		}
		//Swap x and y
		ssize_t t = *x;

		*x = *y;
		*y = t;
	}
20
21
22
23
24
}

//convert (x,y) to d
static ssize_t xy2d(ssize_t n, ssize_t x, ssize_t y)
{
25
26
27
28
29
30
31
32
33
	ssize_t rx, ry, s, d = 0;

	for (s = n / 2; s > 0; s /= 2) {
		rx = (x & s) > 0;
		ry = (y & s) > 0;
		d += s * s * ((3 * rx) ^ ry);
		rot(s, &x, &y, rx, ry);
	}
	return d;
34
35
36
37
38
}

//convert d to (x,y)
static void d2xy(ssize_t n, ssize_t d, ssize_t *x, ssize_t *y)
{
39
40
41
42
43
44
45
46
47
48
49
	ssize_t rx, ry, s, t = d;

	*x = *y = 0;
	for (s = 1; s < n; s *= 2) {
		rx = 1 & (t / 2);
		ry = 1 & (t ^ rx);
		rot(s, x, y, rx, ry);
		*x += s * rx;
		*y += s * ry;
		t /= 4;
	}
50
51
52
53
}

/* End helper functions */

54
static int hilbert2d_it_alloc(excit_t data)
55
{
56
	struct hilbert2d_it_s *it = (struct hilbert2d_it_s *)data->data;
57

58
59
60
	it->n = 0;
	it->range_it = NULL;
	return EXCIT_SUCCESS;
61
62
}

63
static void hilbert2d_it_free(excit_t data)
64
{
65
	struct hilbert2d_it_s *it = (struct hilbert2d_it_s *)data->data;
66

67
	excit_free(it->range_it);
68
69
}

70
static int hilbert2d_it_copy(excit_t ddst, const excit_t dsrc)
71
{
72
73
74
75
76
77
78
79
80
81
	struct hilbert2d_it_s *dst = (struct hilbert2d_it_s *)ddst->data;
	const struct hilbert2d_it_s *src =
	    (const struct hilbert2d_it_s *)dsrc->data;
	excit_t copy = excit_dup(src->range_it);

	if (!copy)
		return -EXCIT_EINVAL;
	dst->range_it = copy;
	dst->n = src->n;
	return EXCIT_SUCCESS;
82
83
}

84
static int hilbert2d_it_rewind(excit_t data)
85
{
86
	struct hilbert2d_it_s *it = (struct hilbert2d_it_s *)data->data;
87

88
	return excit_rewind(it->range_it);
89
90
}

91
static int hilbert2d_it_peek(const excit_t data, ssize_t *val)
92
{
93
94
95
96
97
98
99
100
101
102
	struct hilbert2d_it_s *it = (struct hilbert2d_it_s *)data->data;
	ssize_t d;
	int err;

	err = excit_peek(it->range_it, &d);
	if (err)
		return err;
	if (val)
		d2xy(it->n, d, val, val + 1);
	return EXCIT_SUCCESS;
103
104
}

105
static int hilbert2d_it_next(excit_t data, ssize_t *val)
106
{
107
108
109
110
111
112
113
114
115
	struct hilbert2d_it_s *it = (struct hilbert2d_it_s *)data->data;
	ssize_t d;
	int err = excit_next(it->range_it, &d);

	if (err)
		return err;
	if (val)
		d2xy(it->n, d, val, val + 1);
	return EXCIT_SUCCESS;
116
117
}

118
static int hilbert2d_it_size(const excit_t data, ssize_t *size)
119
{
120
121
	const struct hilbert2d_it_s *it = (struct hilbert2d_it_s *)data->data;
	return excit_size(it->range_it, size);
122
123
}

124
static int hilbert2d_it_nth(const excit_t data, ssize_t n, ssize_t *val)
125
{
126
127
128
129
130
131
132
133
134
	ssize_t d;
	struct hilbert2d_it_s *it = (struct hilbert2d_it_s *)data->data;
	int err = excit_nth(it->range_it, n, &d);

	if (err)
		return err;
	if (val)
		d2xy(it->n, d, val, val + 1);
	return EXCIT_SUCCESS;
135
136
}

137
138
static int hilbert2d_it_rank(const excit_t data, const ssize_t *indexes,
			     ssize_t *n)
139
{
140
	struct hilbert2d_it_s *it = (struct hilbert2d_it_s *)data->data;
141

142
143
144
145
	if (indexes[0] < 0 || indexes[0] >= it->n || indexes[1] < 0
	    || indexes[1] >= it->n)
		return -EXCIT_EINVAL;
	ssize_t d = xy2d(it->n, indexes[0], indexes[1]);
146

147
	return excit_rank(it->range_it, &d, n);
148
149
}

150
static int hilbert2d_it_pos(const excit_t data, ssize_t *n)
151
{
152
	struct hilbert2d_it_s *it = (struct hilbert2d_it_s *)data->data;
153

154
	return excit_pos(it->range_it, n);
155
156
}

157
static int hilbert2d_it_split(const excit_t data, ssize_t n, excit_t *results)
158
{
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
	const struct hilbert2d_it_s *it = (struct hilbert2d_it_s *)data->data;
	int err = excit_split(it->range_it, n, results);

	if (err)
		return err;
	if (!results)
		return EXCIT_SUCCESS;
	for (int i = 0; i < n; i++) {
		excit_t tmp;

		tmp = results[i];
		results[i] = excit_alloc(EXCIT_HILBERT2D);
		if (!results[i]) {
			excit_free(tmp);
			err = -EXCIT_ENOMEM;
			goto error;
		}
		results[i]->dimension = 2;
		struct hilbert2d_it_s *res_it =
		    (struct hilbert2d_it_s *)results[i]->data;
		res_it->n = it->n;
		res_it->range_it = tmp;
	}
	return EXCIT_SUCCESS;
183
error:
184
185
186
	for (int i = 0; i < n; i++)
		excit_free(results[i]);
	return err;
187
188
189
190
}

int excit_hilbert2d_init(excit_t it, ssize_t order)
{
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
	struct hilbert2d_it_s *hilbert2d_it;

	if (!it || it->type != EXCIT_HILBERT2D || order <= 0)
		return -EXCIT_EINVAL;
	it->dimension = 2;
	hilbert2d_it = (struct hilbert2d_it_s *)it->data;
	hilbert2d_it->range_it = excit_alloc(EXCIT_RANGE);
	if (!hilbert2d_it->range_it)
		return -EXCIT_ENOMEM;
	int n = 1 << order;
	int err = excit_range_init(hilbert2d_it->range_it, 0, n * n - 1, 1);

	if (err)
		return err;
	hilbert2d_it->n = n;
	return EXCIT_SUCCESS;
207
208
}

209
210
211
212
213
214
215
216
217
218
219
220
221
struct excit_func_table_s excit_hilbert2d_func_table = {
	hilbert2d_it_alloc,
	hilbert2d_it_free,
	hilbert2d_it_copy,
	hilbert2d_it_next,
	hilbert2d_it_peek,
	hilbert2d_it_size,
	hilbert2d_it_rewind,
	hilbert2d_it_split,
	hilbert2d_it_nth,
	hilbert2d_it_rank,
	hilbert2d_it_pos
};
222