libmongocrypt
Loading...
Searching...
No Matches
mc-range-mincover-generator.template.h
1/*
2 * Copyright 2022-present MongoDB, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17// mc-range-mincover-generator.template.h is meant to be included in another
18// source file.
19
20// TODO: replace `CONCAT` with `BSON_CONCAT` after libbson dependency is
21// upgraded to 1.20.0 or higher.
22#ifndef CONCAT
23#define CONCAT_1(a, b) a##b
24#define CONCAT(a, b) CONCAT_1(a, b)
25#endif
26// TODO: replace `CONCAT3` with `BSON_CONCAT3` after libbson dependency is
27// upgraded to 1.20.0 or higher.
28#ifndef CONCAT3
29#define CONCAT3(a, b, c) CONCAT(a, CONCAT(b, c))
30#endif
31
32#if !(defined(UINT_T) && defined(UINT_C) && defined(UINT_FMT_S) && defined(DECORATE_NAME))
33#ifdef __INTELLISENSE__
34#define UINT_T uint32_t
35#define UINT_C UINT32_C
36#define UINT_FMT_S PRIu32
37#define DECORATE_NAME(Name) Name##_u32
38#else
39#error All of UINT_T, UINT_C, UINT_FMT_S, UINT_FMT_ARG, and DECORATE_NAME must be defined before #including this file
40#endif
41#endif
42
43#define BITS (sizeof(UINT_T) * CHAR_BIT)
44
45#define ZERO UINT_C(0)
46
47// Default for UINT_FMT_ARG
48#ifndef UINT_FMT_ARG
49#define UINT_FMT_ARG(X) X
50#endif
51
52// Default comparison
53#ifndef UINT_LESSTHAN
54#define UINT_LESSTHAN(A, B) ((A) < (B))
55#endif
56
57#ifndef MC_UINT_MAX
58#define MC_UINT_MAX ~(UINT_C(0))
59#endif
60
61// Default addition
62#ifndef UINT_ADD
63#define UINT_ADD(A, B) ((A) + (B))
64#endif
65#ifndef UINT_SUB
66#define UINT_SUB(A, B) ((A) - (B))
67#endif
68
69// Default lshift (also handles negatives as right-shift)
70#ifndef UINT_LSHIFT
71static inline UINT_T DECORATE_NAME(_mc_default_lshift)(UINT_T lhs, int off) {
72 if (off < 0) {
73 return lhs >> -off;
74 } else {
75 return lhs << off;
76 }
77}
78
79#define UINT_LSHIFT DECORATE_NAME(_mc_default_lshift)
80#endif
81
82#ifndef UINT_BITOR
83#define UINT_BITOR(A, B) ((A) | (B))
84#endif
85
86static inline int DECORATE_NAME(_mc_compare)(UINT_T lhs, UINT_T rhs) {
87 if (UINT_LESSTHAN(lhs, rhs)) {
88 return -1;
89 } else if (UINT_LESSTHAN(rhs, lhs)) {
90 return 1;
91 } else {
92 return 0;
93 }
94}
95
96#define UINT_COMPARE DECORATE_NAME(_mc_compare)
97
98// MinCoverGenerator models the MinCoverGenerator type added in
99// SERVER-68600.
100typedef struct {
101 UINT_T _rangeMin;
102 UINT_T _rangeMax;
103 size_t _sparsity;
104 uint32_t _trimFactor;
105 // _maxlen is the maximum bit length of edges in the mincover.
106 size_t _maxlen;
107} DECORATE_NAME(MinCoverGenerator);
108
109static inline DECORATE_NAME(MinCoverGenerator)
110 * DECORATE_NAME(MinCoverGenerator_new)(UINT_T rangeMin,
111 UINT_T rangeMax,
112 UINT_T max,
113 size_t sparsity,
114 uint32_t trimFactor,
115 mongocrypt_status_t *status) {
116 BSON_ASSERT_PARAM(status);
117
118 if (UINT_COMPARE(rangeMin, rangeMax) > 0) {
119 CLIENT_ERR("Range min (%" UINT_FMT_S ") must be less than or equal to range max (%" UINT_FMT_S
120 ") for range search",
121 UINT_FMT_ARG(rangeMin),
122 UINT_FMT_ARG(rangeMax));
123 return NULL;
124 }
125 if (UINT_COMPARE(rangeMax, max) > 0) {
126 CLIENT_ERR("Range max (%" UINT_FMT_S ") must be less than or equal to max (%" UINT_FMT_S ") for range search",
127 UINT_FMT_ARG(rangeMax),
128 UINT_FMT_ARG(max));
129 return NULL;
130 }
131
132 if (sparsity == 0) {
133 CLIENT_ERR("Sparsity must be > 0");
134 return NULL;
135 }
136 size_t maxlen = (size_t)BITS - DECORATE_NAME(mc_count_leading_zeros)(max);
137 if (trimFactor != 0 && trimFactor >= maxlen) {
138 CLIENT_ERR("Trim factor must be less than the number of bits (%zu) used to represent an element of the domain",
139 maxlen);
140 return NULL;
141 }
142 DECORATE_NAME(MinCoverGenerator) *mcg = bson_malloc0(sizeof(DECORATE_NAME(MinCoverGenerator)));
143 mcg->_rangeMin = rangeMin;
144 mcg->_rangeMax = rangeMax;
145 mcg->_maxlen = (size_t)BITS - DECORATE_NAME(mc_count_leading_zeros)(max);
146 mcg->_sparsity = sparsity;
147 mcg->_trimFactor = trimFactor;
148 return mcg;
149}
150
151static inline void DECORATE_NAME(MinCoverGenerator_destroy)(DECORATE_NAME(MinCoverGenerator) * mcg) {
152 bson_free(mcg);
153}
154
155// applyMask applies a mask of 1 bits starting from the right.
156// Bits 0 to bit-1 are replaced with 1. Other bits are left as-is.
157static inline UINT_T DECORATE_NAME(applyMask)(UINT_T value, size_t maskedBits) {
158 const UINT_T ones = MC_UINT_MAX;
159
160 BSON_ASSERT(maskedBits <= (size_t)BITS);
161 BSON_ASSERT(maskedBits >= 0);
162
163 if (maskedBits == 0) {
164 return value;
165 }
166
167 const size_t shift = ((size_t)BITS - maskedBits);
168 const UINT_T mask = UINT_LSHIFT(ones, -(int)shift);
169 return UINT_BITOR(value, mask);
170}
171
172static inline bool DECORATE_NAME(MinCoverGenerator_isLevelStored)(DECORATE_NAME(MinCoverGenerator) * mcg,
173 size_t maskedBits) {
174 BSON_ASSERT_PARAM(mcg);
175 size_t level = mcg->_maxlen - maskedBits;
176 return 0 == maskedBits || (level >= mcg->_trimFactor && 0 == (level % mcg->_sparsity));
177}
178
179char *
180DECORATE_NAME(MinCoverGenerator_toString)(DECORATE_NAME(MinCoverGenerator) * mcg, UINT_T start, size_t maskedBits) {
181 BSON_ASSERT_PARAM(mcg);
182 BSON_ASSERT(maskedBits <= mcg->_maxlen);
183 BSON_ASSERT(maskedBits <= (size_t)BITS);
184 BSON_ASSERT(maskedBits >= 0);
185
186 if (maskedBits == mcg->_maxlen) {
187 return bson_strdup("root");
188 }
189
190 UINT_T shifted = UINT_LSHIFT(start, -(int)maskedBits);
191 mc_bitstring valueBin = DECORATE_NAME(mc_convert_to_bitstring)(shifted);
192 char *ret = bson_strndup(valueBin.str + ((size_t)BITS - mcg->_maxlen + maskedBits), mcg->_maxlen + maskedBits);
193 return ret;
194}
195
196static inline void DECORATE_NAME(MinCoverGenerator_minCoverRec)(DECORATE_NAME(MinCoverGenerator) * mcg,
197 mc_array_t *c,
198 UINT_T blockStart,
199 size_t maskedBits) {
200 BSON_ASSERT_PARAM(mcg);
201 BSON_ASSERT_PARAM(c);
202 const UINT_T blockEnd = DECORATE_NAME(applyMask)(blockStart, maskedBits);
203
204 if (UINT_COMPARE(blockEnd, mcg->_rangeMin) < 0 || UINT_COMPARE(blockStart, mcg->_rangeMax) > 0) {
205 return;
206 }
207
208 if (UINT_COMPARE(blockStart, mcg->_rangeMin) >= 0 && UINT_COMPARE(blockEnd, mcg->_rangeMax) <= 0
209 && DECORATE_NAME(MinCoverGenerator_isLevelStored)(mcg, maskedBits)) {
210 char *edge = DECORATE_NAME(MinCoverGenerator_toString)(mcg, blockStart, maskedBits);
211 _mc_array_append_val(c, edge);
212 return;
213 }
214
215 BSON_ASSERT(maskedBits > 0);
216
217 const size_t newBits = maskedBits - 1u;
218 DECORATE_NAME(MinCoverGenerator_minCoverRec)(mcg, c, blockStart, newBits);
219 DECORATE_NAME(MinCoverGenerator_minCoverRec)
220 (mcg, c, UINT_BITOR(blockStart, UINT_LSHIFT(UINT_C(1), (int)newBits)), newBits);
221}
222
223static inline mc_mincover_t *DECORATE_NAME(MinCoverGenerator_minCover)(DECORATE_NAME(MinCoverGenerator) * mcg) {
224 BSON_ASSERT_PARAM(mcg);
225 mc_mincover_t *mc = mc_mincover_new();
226 DECORATE_NAME(MinCoverGenerator_minCoverRec)
227 (mcg, &mc->mincover, ZERO, mcg->_maxlen);
228 return mc;
229}
230
231// adjustBounds increments *lowerBound if includeLowerBound is false and
232// decrements *upperBound if includeUpperBound is false.
233// lowerBound, min, upperBound, and max are expected to come from the result
234// of mc_getTypeInfo.
235static bool DECORATE_NAME(adjustBounds)(UINT_T *lowerBound,
236 bool includeLowerBound,
237 UINT_T min,
238 UINT_T *upperBound,
239 bool includeUpperBound,
240 UINT_T max,
241 mongocrypt_status_t *status) {
242 BSON_ASSERT_PARAM(lowerBound);
243 BSON_ASSERT_PARAM(upperBound);
244
245 if (!includeLowerBound) {
246 if (UINT_COMPARE(*lowerBound, max) >= 0) {
247 CLIENT_ERR("Lower bound (%" UINT_FMT_S ") must be less than the range maximum (%" UINT_FMT_S
248 ") if lower bound is excluded from range.",
249 UINT_FMT_ARG(*lowerBound),
250 UINT_FMT_ARG(max));
251 return false;
252 }
253 *lowerBound = UINT_ADD(*lowerBound, UINT_C(1));
254 }
255 if (!includeUpperBound) {
256 if (UINT_COMPARE(*upperBound, min) <= 0) {
257 CLIENT_ERR("Upper bound (%" UINT_FMT_S ") must be greater than the range minimum (%" UINT_FMT_S
258 ") if upper bound is excluded from range.",
259 UINT_FMT_ARG(*upperBound),
260 UINT_FMT_ARG(min));
261 return false;
262 }
263 *upperBound = UINT_SUB(*upperBound, UINT_C(1));
264 }
265 return true;
266}
267
268#undef UINT_T
269#undef UINT_C
270#undef UINT_FMT_S
271#undef UINT_FMT_ARG
272#undef DECORATE_NAME
273#undef BITS
274#undef UINT_COMPARE
275#undef UINT_ADD
276#undef UINT_SUB
277#undef UINT_LSHIFT
278#undef UINT_BITOR
279#undef MC_UINT_MAX
280#undef ZERO
281#undef UINT_LESSTHAN
struct _mongocrypt_status_t mongocrypt_status_t
Definition: mongocrypt.h:152
Definition: mc-range-mincover-generator.template.h:100