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