1 /* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 
3 /**
4  * @copyright 2013 Couchbase, Inc.
5  *
6  * @author Volker Mische <volker@couchbase.com>
7  *
8  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
9  * use this file except in compliance with the License. You may obtain a copy of
10  * the License at
11  *
12  *  http://www.apache.org/licenses/LICENSE-2.0
13  *
14  * Unless required by applicable law or agreed to in writing, software
15  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
16  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
17  * License for the specific language governing permissions and limitations under
18  * the License.
19  **/
20 
21 #include "spatial_tests.h"
22 
23 #include <platform/cb_malloc.h>
24 
25 /* Convert a binary number encoded as string to an uint32 */
b2u(const char *binary)26 static uint32_t b2u(const char *binary)
27 {
28     uint32_t result = 0;
29 
30     while(*binary != '\0')
31     {
32         result <<= 1;
33         if (*binary == '1') {
34             result |= 1;
35         }
36         binary++;
37     }
38     return result;
39 }
40 
41 
42 /* Convert a binary number encoded as string to an unsigned char array
43  * The size (in bytes) will be used for padding the result with leading
44  * zeros. */
b2c(const char *binary, size_t size)45 static unsigned char *b2c(const char *binary, size_t size)
46 {
47     int i = 0;
48     /* The offset is on the input string, hence it is in bits */
49     size_t offset = size*8 - strlen(binary);
50     unsigned char *result = (unsigned char *)cb_calloc(
51         size, sizeof(unsigned char));
52 
53     for(i = 0; *binary != '\0'; i++, binary++) {
54         result[(i+offset)/8] <<= 1;
55         if (*binary == '1') {
56             result[(i+offset)/8] |= 1;
57         }
58     }
59     return result;
60 }
61 
62 
63 /* Return an assertable value: != 0 when the interleaving returned the
64  * expected result */
interleaving(uint32_t numbers[], const uint16_t size_numbers, const char *expected)65 static int interleaving(uint32_t numbers[],
66                         const uint16_t size_numbers,
67                         const char *expected)
68 {
69     unsigned char *interleaved;
70     unsigned char *expected_bin;
71     int ret = 0;
72 
73     interleaved = interleave_uint32s(numbers, size_numbers/sizeof(uint32_t));
74     expected_bin = b2c(expected, size_numbers);
75 
76     ret = memcmp((void *)interleaved, expected_bin, size_numbers) == 0;
77 
78     cb_free(interleaved);
79     cb_free(expected_bin);
80 
81     return ret;
82 }
83 
84 
test_interleaving()85 void test_interleaving()
86 {
87     uint32_t *numbers;
88     uint32_t numbers_size;
89 
90     fprintf(stderr, "Running spatial interleaving tests\n");
91 
92     numbers_size = 2 * sizeof(uint32_t);
93     numbers = (uint32_t *)cb_malloc(numbers_size);
94     numbers[0] = b2u("111111000000");
95     numbers[1] = b2u("000000111111");
96     cb_assert(interleaving(numbers, numbers_size, "101010101010010101010101"));
97     cb_free(numbers);
98 
99     numbers_size = 3 * sizeof(uint32_t);
100     numbers = (uint32_t *)cb_malloc(numbers_size);
101     numbers[0] = b2u("1101");
102     numbers[1] = b2u("0101");
103     numbers[2] = b2u("1111");
104     cb_assert(interleaving(numbers, numbers_size, "101111001111"));
105     cb_free(numbers);
106 
107     numbers_size = 4 * sizeof(uint32_t);
108     numbers = (uint32_t *)cb_malloc(numbers_size);
109     numbers[0] = b2u("0000");
110     numbers[1] = b2u("1111");
111     numbers[2] = b2u("1111");
112     numbers[3] = b2u("0000");
113     cb_assert(interleaving(numbers, numbers_size, "0110011001100110"));
114     cb_free(numbers);
115 
116     numbers_size = 5 * sizeof(uint32_t);
117     numbers = (uint32_t *)cb_malloc(numbers_size);
118     numbers[0] = b2u("11");
119     numbers[1] = b2u("01");
120     numbers[2] = b2u("11");
121     numbers[3] = b2u("00");
122     numbers[4] = b2u("10");
123     cb_assert(interleaving(numbers, numbers_size, "1010111100"));
124     cb_free(numbers);
125 
126     numbers_size = 2 * sizeof(uint32_t);
127     numbers = (uint32_t *)cb_malloc(numbers_size);
128     numbers[0] = b2u("11111111111111111111111111111111");
129     numbers[1] = b2u("00000000000000000000000000000000");
130     cb_assert(interleaving(numbers, numbers_size, "1010101010101010101010101010101010101010101010101010101010101010"));
131     cb_free(numbers);
132 
133     numbers_size = 12 * sizeof(uint32_t);
134     numbers = (uint32_t *)cb_malloc(numbers_size);
135     numbers[0] = b2u("11");
136     numbers[1] = b2u("00");
137     numbers[2] = b2u("11");
138     numbers[3] = b2u("11");
139     numbers[4] = b2u("00");
140     numbers[5] = b2u("00");
141     numbers[6] = b2u("11");
142     numbers[7] = b2u("11");
143     numbers[8] = b2u("11");
144     numbers[9] = b2u("00");
145     numbers[10] = b2u("00");
146     numbers[11] = b2u("00");
147     cb_assert(interleaving(numbers, numbers_size, "101100111000101100111000"));
148     cb_free(numbers);
149 }
150 
151 
test_spatial_scale_factor()152 void test_spatial_scale_factor()
153 {
154     double mbb[] = {1.0, 3.0, 30.33, 31.33, 15.4, 138.7, 7.8, 7.8};
155     uint16_t dim = (sizeof(mbb)/sizeof(double))/2;
156     uint32_t max = ZCODE_MAX_VALUE;
157     scale_factor_t *sf = NULL;
158 
159     fprintf(stderr, "Running spatial scale factor tests\n");
160 
161     sf = spatial_scale_factor(mbb, dim, max);
162 
163     cb_assert(sf->offsets[0] == mbb[0]);
164     cb_assert(sf->offsets[1] == mbb[2]);
165     cb_assert(sf->offsets[2] == mbb[4]);
166     cb_assert(sf->offsets[3] == mbb[6]);
167     cb_assert((uint32_t)(sf->scales[0]*(mbb[1]-mbb[0])) == max);
168     cb_assert((uint32_t)(sf->scales[1]*(mbb[3]-mbb[2])) == max);
169     cb_assert((uint32_t)(sf->scales[2]*(mbb[5]-mbb[4])) == max);
170     cb_assert((uint32_t)(sf->scales[3]) == 0);
171     cb_assert(sf->dim == dim);
172 
173     free_spatial_scale_factor(sf);
174 }
175 
176 
test_spatial_center()177 void test_spatial_center()
178 {
179     double mbb[] = {1.0, 3.0, 30.33, 31.33, 15.4, 138.7, 7.8, 7.8};
180     double mbb2[] = {6.3, 18.7};
181     sized_mbb_t mbb_struct;
182     double *center;
183 
184     fprintf(stderr, "Running spatial scale factor tests\n");
185 
186     mbb_struct.mbb = mbb;
187     mbb_struct.num = sizeof(mbb)/sizeof(double);
188     center = spatial_center(&mbb_struct);
189     cb_assert(center[0] == 2.0);
190     cb_assert(center[1] == 30.83);
191     cb_assert(center[2] == 77.05);
192     cb_assert(center[3] == 7.8);
193     cb_free(center);
194 
195     mbb_struct.mbb = mbb2;
196     mbb_struct.num = sizeof(mbb2)/sizeof(double);
197     center = spatial_center(&mbb_struct);
198     cb_assert(center[0] == 12.5);
199     cb_free(center);
200 }
201 
202 
test_spatial_scale_point()203 void test_spatial_scale_point()
204 {
205     double mbb[] = {1.0, 3.0, 30.33, 31.33, 15.4, 138.7, 7.8, 7.8};
206     double point[] = {2.0, 31.0, 42.02, 7.8};
207     uint16_t dim = (sizeof(mbb)/sizeof(double))/2;
208     uint32_t max = ZCODE_MAX_VALUE;
209     scale_factor_t *sf = NULL;
210     uint32_t *scaled;
211 
212     fprintf(stderr, "Running spatial scale point tests\n");
213 
214     sf = spatial_scale_factor(mbb, dim, max);
215     scaled = spatial_scale_point(point, sf);
216     cb_assert(scaled[0] == UINT32_MAX/2);
217     cb_assert(scaled[1] > UINT32_MAX/2 && scaled[1] > 0);
218     cb_assert(scaled[2] < UINT32_MAX/2 && scaled[2] > 0);
219     cb_assert(scaled[3] == 0);
220 
221     free_spatial_scale_factor(sf);
222     cb_free(scaled);
223 }
224 
225 
cmp_bytes(const unsigned char *bitmap, const char *expected, const uint8_t size)226 static int cmp_bytes(const unsigned char *bitmap,
227                      const char *expected,
228                      const uint8_t size)
229 {
230     int result = 0;
231     unsigned char *tmp = b2c(expected, size);
232 
233     result = memcmp(bitmap, tmp, size) == 0;
234     cb_free(tmp);
235 
236     return result;
237 }
238 
test_set_bit_sized()239 void test_set_bit_sized()
240 {
241     uint8_t size = 1;
242     unsigned char* bitmap = b2c("00010001", size);
243     unsigned char* bitmap2 = b2c("0000000000000000", 2);
244 
245     fprintf(stderr, "Running set bit sized tests\n");
246 
247     set_bit_sized(bitmap, size, 1);
248     cb_assert(cmp_bytes(bitmap, "00010011", size));
249 
250     set_bit_sized(bitmap, size, 7);
251     cb_assert(cmp_bytes(bitmap, "10010011", size));
252     set_bit_sized(bitmap, size, 2);
253     cb_assert(cmp_bytes(bitmap, "10010111", size));
254     set_bit_sized(bitmap, size, 3);
255     cb_assert(cmp_bytes(bitmap, "10011111", size));
256     /* Setting the same bit doesn't change the value */
257     set_bit_sized(bitmap, size, 3);
258     cb_assert(cmp_bytes(bitmap, "10011111", size));
259 
260     size = 2;
261     set_bit_sized(bitmap2, size, 0);
262     cb_assert(cmp_bytes(bitmap2, "0000000000000001", size));
263     set_bit_sized(bitmap2, size, 13);
264     cb_assert(cmp_bytes(bitmap2, "0010000000000001", size));
265     set_bit_sized(bitmap2, size, 7);
266     cb_assert(cmp_bytes(bitmap2, "0010000010000001", size));
267     set_bit_sized(bitmap2, size, 3);
268     cb_assert(cmp_bytes(bitmap2, "0010000010001001", size));
269     set_bit_sized(bitmap2, size, 12);
270     cb_assert(cmp_bytes(bitmap2, "0011000010001001", size));
271 
272     cb_free(bitmap);
273     cb_free(bitmap2);
274 }
275 
276 
test_encode_spatial_key()277 void test_encode_spatial_key()
278 {
279     sized_mbb_t mbb_struct;
280     char encoded[66];
281     double mbb[] = {6.3, 18.7};
282     double mbb2[] = {1.0, 3.0, 30.33, 31.33, 15.4, 138.7, 7.8, 7.8};
283     unsigned char expected[] = {
284         0x00, 0x02, 0x33, 0x33, 0x33, 0x33, 0x33, 0x33, 0x19, 0x40,
285         0x33, 0x33, 0x33, 0x33, 0x33, 0xb3, 0x32, 0x40
286     };
287     unsigned char expected2[] = {
288         0x00, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xf0, 0x3f,
289         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x08, 0x40, 0x14, 0xae,
290         0x47, 0xe1, 0x7a, 0x54, 0x3e, 0x40, 0x14, 0xae, 0x47, 0xe1,
291         0x7a, 0x54, 0x3f, 0x40, 0xcd, 0xcc, 0xcc, 0xcc, 0xcc, 0xcc,
292         0x2e, 0x40, 0x66, 0x66, 0x66, 0x66, 0x66, 0x56, 0x61, 0x40,
293         0x33, 0x33, 0x33, 0x33, 0x33, 0x33, 0x1f, 0x40, 0x33, 0x33,
294         0x33, 0x33, 0x33, 0x33, 0x1f, 0x40
295     };
296 
297     fprintf(stderr, "Running encode spatial key tests\n");
298 
299     mbb_struct.mbb = mbb;
300     mbb_struct.num = sizeof(mbb)/sizeof(double);
301     encode_spatial_key(&mbb_struct, (char *)&encoded, sizeof(encoded));
302     cb_assert(memcmp(encoded, expected, 18) == 0);
303 
304     mbb_struct.mbb = mbb2;
305     mbb_struct.num = sizeof(mbb2)/sizeof(double);
306     encode_spatial_key(&mbb_struct, (char *)&encoded, sizeof(encoded));
307     cb_assert(memcmp(encoded, expected2, 66) == 0);
308 }
309 
310 
311 /* Compares two arrays of doubles. 1 if equal, 0 if not equal */
is_double_array_equal(double *a, double *b, int len)312 static bool is_double_array_equal(double *a, double *b, int len)
313 {
314     int i;
315 
316     for (i = 0; i < len; ++i) {
317         if (a[i] != b[i]) {
318             return false;
319         }
320     }
321 
322     return true;
323 }
324 
test_decode_spatial_key()325 void test_decode_spatial_key()
326 {
327     sized_mbb_t decoded;
328     unsigned char mbb[] = {
329         0x00, 0x02, 0x33, 0x33, 0x33, 0x33, 0x33, 0x33, 0x19, 0x40,
330         0x33, 0x33, 0x33, 0x33, 0x33, 0xb3, 0x32, 0x40
331     };
332     unsigned char mbb2[] = {
333         0x00, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xf0, 0x3f,
334         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x08, 0x40, 0x14, 0xae,
335         0x47, 0xe1, 0x7a, 0x54, 0x3e, 0x40, 0x14, 0xae, 0x47, 0xe1,
336         0x7a, 0x54, 0x3f, 0x40, 0xcd, 0xcc, 0xcc, 0xcc, 0xcc, 0xcc,
337         0x2e, 0x40, 0x66, 0x66, 0x66, 0x66, 0x66, 0x56, 0x61, 0x40,
338         0x33, 0x33, 0x33, 0x33, 0x33, 0x33, 0x1f, 0x40, 0x33, 0x33,
339         0x33, 0x33, 0x33, 0x33, 0x1f, 0x40
340     };
341     double expected[] = {6.3, 18.7};
342     double expected2[] = {1.0, 3.0, 30.33, 31.33, 15.4, 138.7, 7.8, 7.8};
343 
344     fprintf(stderr, "Running decode spatial key tests\n");
345 
346     decode_spatial_key((char *)mbb, &decoded);
347     cb_assert(decoded.num == 2);
348     cb_assert(is_double_array_equal(decoded.mbb, expected, 2));
349 
350     decode_spatial_key((char *)mbb2, &decoded);
351     cb_assert(decoded.num == 8);
352     cb_assert(is_double_array_equal(decoded.mbb, expected2, 8));
353 }
354 
355 
test_expand_mbb()356 void test_expand_mbb()
357 {
358     sized_mbb_t mbb_struct_a, mbb_struct_b;
359     double mbb_a[] = {6.3, 18.7};
360     double mbb_b[] = {10.1, 31.5};
361     double expected_mbb[] = {6.3, 31.5};
362     double mbb2_a[] = {3.0, 5.0, 100.1, 150.2, 12.5, 13.75};
363     double mbb2_b[] = {2.9, 4.9, 80.0, 222.2, 13.0, 13.1};
364     double expected2_mbb[] = {2.9, 5.0, 80.0, 222.2, 12.5, 13.75};
365 
366     fprintf(stderr, "Running expand MBB tests\n");
367 
368     mbb_struct_a.num = 2;
369     mbb_struct_a.mbb = mbb_a;
370     mbb_struct_b.num = 2;
371     mbb_struct_b.mbb = mbb_b;
372     expand_mbb(&mbb_struct_a, &mbb_struct_b);
373     cb_assert(is_double_array_equal(mbb_struct_a.mbb, expected_mbb, 2));
374 
375     mbb_struct_a.num = 6;
376     mbb_struct_a.mbb = mbb2_a;
377     mbb_struct_b.num = 6;
378     mbb_struct_b.mbb = mbb2_b;
379     expand_mbb(&mbb_struct_a, &mbb_struct_b);
380     cb_assert(is_double_array_equal(mbb_struct_a.mbb, expected2_mbb, 6));
381 }
382 
test_view_spatial_reduce()383 void test_view_spatial_reduce()
384 {
385     sized_mbb_t original_mbb, expander_mbb;
386 
387     original_mbb.num = expander_mbb.num = 6;
388     double mbb1[] = {60, 60, 115, 115, 1, 6};
389     double mbb2[] = {63, 63, 1506, 1506, 1, 6};
390     original_mbb.mbb = mbb1;
391     original_mbb.num = expander_mbb.num = 6;
392     expander_mbb.mbb = mbb2;
393 
394     nodelist root, child;
395     char encoded1[128], encoded2[128], dst[128];
396     size_t size;
397 
398     encode_spatial_key(&original_mbb, (char *)&encoded1, sizeof(encoded1));
399     encode_spatial_key(&expander_mbb, (char *)&encoded2, sizeof(encoded2));
400 
401     root.key.buf = encoded1;
402     child.key.buf = encoded2;
403 
404     root.next = &child;
405     child.next = NULL;
406 
407     fprintf(stderr, "Running view_spatial_reduce test\n");
408     view_spatial_reduce(dst, &size, &root, 2, NULL);
409 
410 }
411 
412