xref: /5.5.2/couchstore/tests/views/spatial.cc (revision 6ef489f3)
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 */
26static 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. */
45static 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 */
65static 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
85void 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
152void 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
177void 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
203void 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
226static 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
239void 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
277void 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 */
312static 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
325void 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
356void 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
383void 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