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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
#include <vespa/vespalib/testkit/test_kit.h>
#include <vespa/vespalib/util/fiddle.h>
using namespace vespalib::bits;
TEST("require that mix mixes") {
EXPECT_EQUAL(0xffffffffu, mix(0xffffffffu, 0x00000000, 100));
EXPECT_EQUAL(0xffffffffu, mix(0xffffffffu, 0x00000000, 33));
EXPECT_EQUAL(0x00000000u, mix(0x00000000, 0xffffffffu, 100));
EXPECT_EQUAL(0x00000000u, mix(0x00000000, 0xffffffffu, 33));
EXPECT_EQUAL(0xffffffffu, mix(0xffffffffu, 0x00000000, 32));
EXPECT_EQUAL(0xfffffffeu, mix(0xffffffffu, 0x00000000, 31));
EXPECT_EQUAL(0xfffffffcu, mix(0xffffffffu, 0x00000000, 30));
EXPECT_EQUAL(0xfffffff8u, mix(0xffffffffu, 0x00000000, 29));
EXPECT_EQUAL(0xfffffff0u, mix(0xffffffffu, 0x00000000, 28));
EXPECT_EQUAL(0xffffffe0u, mix(0xffffffffu, 0x00000000, 27));
EXPECT_EQUAL(0xffffffc0u, mix(0xffffffffu, 0x00000000, 26));
EXPECT_EQUAL(0xffffff80u, mix(0xffffffffu, 0x00000000, 25));
EXPECT_EQUAL(0xffffff00u, mix(0xffffffffu, 0x00000000, 24));
EXPECT_EQUAL(0xfffffe00u, mix(0xffffffffu, 0x00000000, 23));
EXPECT_EQUAL(0xfffffc00u, mix(0xffffffffu, 0x00000000, 22));
EXPECT_EQUAL(0xfffff800u, mix(0xffffffffu, 0x00000000, 21));
EXPECT_EQUAL(0xfffff000u, mix(0xffffffffu, 0x00000000, 20));
EXPECT_EQUAL(0xffffe000u, mix(0xffffffffu, 0x00000000, 19));
EXPECT_EQUAL(0xffffc000u, mix(0xffffffffu, 0x00000000, 18));
EXPECT_EQUAL(0xffff8000u, mix(0xffffffffu, 0x00000000, 17));
EXPECT_EQUAL(0xffff0000u, mix(0xffffffffu, 0x00000000, 16));
EXPECT_EQUAL(0xfffe0000u, mix(0xffffffffu, 0x00000000, 15));
EXPECT_EQUAL(0xfffc0000u, mix(0xffffffffu, 0x00000000, 14));
EXPECT_EQUAL(0xfff80000u, mix(0xffffffffu, 0x00000000, 13));
EXPECT_EQUAL(0xfff00000u, mix(0xffffffffu, 0x00000000, 12));
EXPECT_EQUAL(0xffe00000u, mix(0xffffffffu, 0x00000000, 11));
EXPECT_EQUAL(0xffc00000u, mix(0xffffffffu, 0x00000000, 10));
EXPECT_EQUAL(0xff800000u, mix(0xffffffffu, 0x00000000, 9));
EXPECT_EQUAL(0xff000000u, mix(0xffffffffu, 0x00000000, 8));
EXPECT_EQUAL(0xfe000000u, mix(0xffffffffu, 0x00000000, 7));
EXPECT_EQUAL(0xfc000000u, mix(0xffffffffu, 0x00000000, 6));
EXPECT_EQUAL(0xf8000000u, mix(0xffffffffu, 0x00000000, 5));
EXPECT_EQUAL(0xf0000000u, mix(0xffffffffu, 0x00000000, 4));
EXPECT_EQUAL(0xe0000000u, mix(0xffffffffu, 0x00000000, 3));
EXPECT_EQUAL(0xc0000000u, mix(0xffffffffu, 0x00000000, 2));
EXPECT_EQUAL(0x80000000u, mix(0xffffffffu, 0x00000000, 1));
EXPECT_EQUAL(0x00000000u, mix(0xffffffffu, 0x00000000, 0));
EXPECT_EQUAL(0x00000000u, mix(0x00000000, 0xffffffffu, 32));
EXPECT_EQUAL(0x00000001u, mix(0x00000000, 0xffffffffu, 31));
EXPECT_EQUAL(0x00000003u, mix(0x00000000, 0xffffffffu, 30));
EXPECT_EQUAL(0x00000007u, mix(0x00000000, 0xffffffffu, 29));
EXPECT_EQUAL(0x0000000fu, mix(0x00000000, 0xffffffffu, 28));
EXPECT_EQUAL(0x0000001fu, mix(0x00000000, 0xffffffffu, 27));
EXPECT_EQUAL(0x0000003fu, mix(0x00000000, 0xffffffffu, 26));
EXPECT_EQUAL(0x0000007fu, mix(0x00000000, 0xffffffffu, 25));
EXPECT_EQUAL(0x000000ffu, mix(0x00000000, 0xffffffffu, 24));
EXPECT_EQUAL(0x000001ffu, mix(0x00000000, 0xffffffffu, 23));
EXPECT_EQUAL(0x000003ffu, mix(0x00000000, 0xffffffffu, 22));
EXPECT_EQUAL(0x000007ffu, mix(0x00000000, 0xffffffffu, 21));
EXPECT_EQUAL(0x00000fffu, mix(0x00000000, 0xffffffffu, 20));
EXPECT_EQUAL(0x00001fffu, mix(0x00000000, 0xffffffffu, 19));
EXPECT_EQUAL(0x00003fffu, mix(0x00000000, 0xffffffffu, 18));
EXPECT_EQUAL(0x00007fffu, mix(0x00000000, 0xffffffffu, 17));
EXPECT_EQUAL(0x0000ffffu, mix(0x00000000, 0xffffffffu, 16));
EXPECT_EQUAL(0x0001ffffu, mix(0x00000000, 0xffffffffu, 15));
EXPECT_EQUAL(0x0003ffffu, mix(0x00000000, 0xffffffffu, 14));
EXPECT_EQUAL(0x0007ffffu, mix(0x00000000, 0xffffffffu, 13));
EXPECT_EQUAL(0x000fffffu, mix(0x00000000, 0xffffffffu, 12));
EXPECT_EQUAL(0x001fffffu, mix(0x00000000, 0xffffffffu, 11));
EXPECT_EQUAL(0x003fffffu, mix(0x00000000, 0xffffffffu, 10));
EXPECT_EQUAL(0x007fffffu, mix(0x00000000, 0xffffffffu, 9));
EXPECT_EQUAL(0x00ffffffu, mix(0x00000000, 0xffffffffu, 8));
EXPECT_EQUAL(0x01ffffffu, mix(0x00000000, 0xffffffffu, 7));
EXPECT_EQUAL(0x03ffffffu, mix(0x00000000, 0xffffffffu, 6));
EXPECT_EQUAL(0x07ffffffu, mix(0x00000000, 0xffffffffu, 5));
EXPECT_EQUAL(0x0fffffffu, mix(0x00000000, 0xffffffffu, 4));
EXPECT_EQUAL(0x1fffffffu, mix(0x00000000, 0xffffffffu, 3));
EXPECT_EQUAL(0x3fffffffu, mix(0x00000000, 0xffffffffu, 2));
EXPECT_EQUAL(0x7fffffffu, mix(0x00000000, 0xffffffffu, 1));
EXPECT_EQUAL(0xffffffffu, mix(0x00000000, 0xffffffffu, 0));
}
TEST("require that leading zeros are counted correctly") {
EXPECT_EQUAL(32u, leading_zeros(0x00000000u));
EXPECT_EQUAL(31u, leading_zeros(0x00000001u));
EXPECT_EQUAL(30u, leading_zeros(0x00000003u));
EXPECT_EQUAL(29u, leading_zeros(0x00000007u));
EXPECT_EQUAL(28u, leading_zeros(0x0000000fu));
EXPECT_EQUAL(27u, leading_zeros(0x0000001fu));
EXPECT_EQUAL(26u, leading_zeros(0x0000003fu));
EXPECT_EQUAL(25u, leading_zeros(0x0000007fu));
EXPECT_EQUAL(24u, leading_zeros(0x000000ffu));
EXPECT_EQUAL(23u, leading_zeros(0x000001ffu));
EXPECT_EQUAL(22u, leading_zeros(0x000003ffu));
EXPECT_EQUAL(21u, leading_zeros(0x000007ffu));
EXPECT_EQUAL(20u, leading_zeros(0x00000fffu));
EXPECT_EQUAL(19u, leading_zeros(0x00001fffu));
EXPECT_EQUAL(18u, leading_zeros(0x00003fffu));
EXPECT_EQUAL(17u, leading_zeros(0x00007fffu));
EXPECT_EQUAL(16u, leading_zeros(0x0000ffffu));
EXPECT_EQUAL(15u, leading_zeros(0x0001ffffu));
EXPECT_EQUAL(14u, leading_zeros(0x0003ffffu));
EXPECT_EQUAL(13u, leading_zeros(0x0007ffffu));
EXPECT_EQUAL(12u, leading_zeros(0x000fffffu));
EXPECT_EQUAL(11u, leading_zeros(0x001fffffu));
EXPECT_EQUAL(10u, leading_zeros(0x003fffffu));
EXPECT_EQUAL( 9u, leading_zeros(0x007fffffu));
EXPECT_EQUAL( 8u, leading_zeros(0x00ffffffu));
EXPECT_EQUAL( 7u, leading_zeros(0x01ffffffu));
EXPECT_EQUAL( 6u, leading_zeros(0x03ffffffu));
EXPECT_EQUAL( 5u, leading_zeros(0x07ffffffu));
EXPECT_EQUAL( 4u, leading_zeros(0x0fffffffu));
EXPECT_EQUAL( 3u, leading_zeros(0x1fffffffu));
EXPECT_EQUAL( 2u, leading_zeros(0x3fffffffu));
EXPECT_EQUAL( 1u, leading_zeros(0x7fffffffu));
EXPECT_EQUAL( 0u, leading_zeros(0xffffffffu));
EXPECT_EQUAL(8u, leading_zeros(0x00ffff00u));
EXPECT_EQUAL(8u, leading_zeros(0x00fffe00u));
EXPECT_EQUAL(8u, leading_zeros(0x00fffc00u));
EXPECT_EQUAL(8u, leading_zeros(0x00fff800u));
EXPECT_EQUAL(8u, leading_zeros(0x00fff000u));
EXPECT_EQUAL(8u, leading_zeros(0x00ffe000u));
EXPECT_EQUAL(8u, leading_zeros(0x00ffc000u));
EXPECT_EQUAL(8u, leading_zeros(0x00ff8000u));
EXPECT_EQUAL(8u, leading_zeros(0x00ff0000u));
EXPECT_EQUAL(8u, leading_zeros(0x00fe0000u));
EXPECT_EQUAL(8u, leading_zeros(0x00fc0000u));
EXPECT_EQUAL(8u, leading_zeros(0x00f80000u));
EXPECT_EQUAL(8u, leading_zeros(0x00f00000u));
EXPECT_EQUAL(8u, leading_zeros(0x00e00000u));
EXPECT_EQUAL(8u, leading_zeros(0x00c00000u));
EXPECT_EQUAL(8u, leading_zeros(0x00800000u));
}
void verify_range_split(uint32_t min, uint32_t max,
uint32_t expect_suffix,
uint32_t expect_first_max,
uint32_t expect_last_min)
{
uint32_t first_max = 0;
uint32_t last_min = 0;
EXPECT_EQUAL(expect_suffix, split_range(min, max, first_max, last_min));
EXPECT_EQUAL(expect_first_max, first_max);
EXPECT_EQUAL(expect_last_min, last_min);
}
TEST("require that ranges are split correctly") {
TEST_DO(verify_range_split(0, 0, 0, 0, 0));
TEST_DO(verify_range_split(503, 503, 0, 503, 503));
TEST_DO(verify_range_split(0xc5, 0xf7, 6, 0xdf, 0xe0));
}
TEST_MAIN() { TEST_RUN_ALL(); }
|
