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) && \
33 defined(DECORATE_NAME))
34#ifdef __INTELLISENSE__
35#define UINT_T uint32_t
36#define UINT_C UINT32_C
37#define UINT_FMT_S PRIu32
38#define DECORATE_NAME(Name) Name##_u32
39#else
40#error All of UINT_T, UINT_C, UINT_FMT_S, UINT_FMT_ARG, and DECORATE_NAME must be defined before #including this file
41#endif
42#endif
43
44#define BITS (sizeof (UINT_T) * CHAR_BIT)
45
46#define ZERO UINT_C (0)
47
48// Default for UINT_FMT_ARG
49#ifndef UINT_FMT_ARG
50#define UINT_FMT_ARG(X) X
51#endif
52
53// Default comparison
54#ifndef UINT_LESSTHAN
55#define UINT_LESSTHAN(A, B) ((A) < (B))
56#endif
57
58#ifndef MC_UINT_MAX
59#define MC_UINT_MAX ~(UINT_C (0))
60#endif
61
62// Default addition
63#ifndef UINT_ADD
64#define UINT_ADD(A, B) ((A) + (B))
65#endif
66#ifndef UINT_SUB
67#define UINT_SUB(A, B) ((A) - (B))
68#endif
69
70// Default lshift (also handles negatives as right-shift)
71#ifndef UINT_LSHIFT
72static inline UINT_T
73DECORATE_NAME (_mc_default_lshift) (UINT_T lhs, int off)
74{
75 if (off < 0) {
76 return lhs >> -off;
77 } else {
78 return lhs << off;
79 }
80}
81#define UINT_LSHIFT DECORATE_NAME (_mc_default_lshift)
82#endif
83
84#ifndef UINT_BITOR
85#define UINT_BITOR(A, B) ((A) | (B))
86#endif
87
88static inline int
89DECORATE_NAME (_mc_compare) (UINT_T lhs, UINT_T rhs)
90{
91 if (UINT_LESSTHAN (lhs, rhs)) {
92 return -1;
93 } else if (UINT_LESSTHAN (rhs, lhs)) {
94 return 1;
95 } else {
96 return 0;
97 }
98}
99
100#define UINT_COMPARE DECORATE_NAME (_mc_compare)
101
102// MinCoverGenerator models the MinCoverGenerator type added in
103// SERVER-68600.
104typedef struct {
105 UINT_T _rangeMin;
106 UINT_T _rangeMax;
107 size_t _sparsity;
108 // _maxlen is the maximum bit length of edges in the mincover.
109 size_t _maxlen;
110} DECORATE_NAME (MinCoverGenerator);
111
112static inline DECORATE_NAME (MinCoverGenerator) *
113 DECORATE_NAME (MinCoverGenerator_new) (UINT_T rangeMin,
114 UINT_T rangeMax,
115 UINT_T max,
116 size_t sparsity,
117 mongocrypt_status_t *status)
118{
119 BSON_ASSERT_PARAM (status);
120
121 if (UINT_COMPARE (rangeMin, rangeMax) > 0) {
122 CLIENT_ERR ("Range min (%" UINT_FMT_S
123 ") must be less than or equal to range max (%" UINT_FMT_S
124 ") for range search",
125 UINT_FMT_ARG (rangeMin),
126 UINT_FMT_ARG (rangeMax));
127 return NULL;
128 }
129 if (UINT_COMPARE (rangeMax, max) > 0) {
130 CLIENT_ERR ("Range max (%" UINT_FMT_S
131 ") must be less than or equal to max (%" UINT_FMT_S
132 ") for range search",
133 UINT_FMT_ARG (rangeMax),
134 UINT_FMT_ARG (max));
135 return NULL;
136 }
137
138 if (sparsity == 0) {
139 CLIENT_ERR ("Sparsity must be > 0");
140 return NULL;
141 }
142 DECORATE_NAME (MinCoverGenerator) *mcg =
143 bson_malloc0 (sizeof (DECORATE_NAME (MinCoverGenerator)));
144 mcg->_rangeMin = rangeMin;
145 mcg->_rangeMax = rangeMax;
146 mcg->_maxlen = (size_t) BITS - DECORATE_NAME (mc_count_leading_zeros) (max);
147 mcg->_sparsity = sparsity;
148 return mcg;
149}
150
151static inline void
152DECORATE_NAME (MinCoverGenerator_destroy) (DECORATE_NAME (MinCoverGenerator) *
153 mcg)
154{
155 bson_free (mcg);
156}
157
158// applyMask applies a mask of 1 bits starting from the right.
159// Bits 0 to bit-1 are replaced with 1. Other bits are left as-is.
160static inline UINT_T
161DECORATE_NAME (applyMask) (UINT_T value, size_t maskedBits)
162{
163 const UINT_T ones = MC_UINT_MAX;
164
165 BSON_ASSERT (maskedBits <= (size_t) BITS);
166 BSON_ASSERT (maskedBits >= 0);
167
168 if (maskedBits == 0) {
169 return value;
170 }
171
172 const size_t shift = ((size_t) BITS - maskedBits);
173 const UINT_T mask = UINT_LSHIFT (ones, -(int) shift);
174 return UINT_BITOR (value, mask);
175}
176
177static inline bool
178DECORATE_NAME (MinCoverGenerator_isLevelStored) (
179 DECORATE_NAME (MinCoverGenerator) * mcg, size_t maskedBits)
180{
181 BSON_ASSERT_PARAM (mcg);
182 size_t level = mcg->_maxlen - maskedBits;
183 return 0 == maskedBits || 0 == (level % mcg->_sparsity);
184}
185
186char *
187DECORATE_NAME (MinCoverGenerator_toString) (
188 DECORATE_NAME (MinCoverGenerator) * mcg, UINT_T start, size_t maskedBits)
189{
190 BSON_ASSERT_PARAM (mcg);
191 BSON_ASSERT (maskedBits <= mcg->_maxlen);
192 BSON_ASSERT (maskedBits <= (size_t) BITS);
193 BSON_ASSERT (maskedBits >= 0);
194
195 if (maskedBits == mcg->_maxlen) {
196 return bson_strdup ("root");
197 }
198
199 UINT_T shifted = UINT_LSHIFT (start, -(int) maskedBits);
200 mc_bitstring valueBin = DECORATE_NAME (mc_convert_to_bitstring) (shifted);
201 char *ret =
202 bson_strndup (valueBin.str + ((size_t) BITS - mcg->_maxlen + maskedBits),
203 mcg->_maxlen + maskedBits);
204 return ret;
205}
206
207static inline void
208DECORATE_NAME (MinCoverGenerator_minCoverRec) (
209 DECORATE_NAME (MinCoverGenerator) * mcg,
210 mc_array_t *c,
211 UINT_T blockStart,
212 size_t maskedBits)
213{
214 BSON_ASSERT_PARAM (mcg);
215 BSON_ASSERT_PARAM (c);
216 const UINT_T blockEnd = DECORATE_NAME (applyMask) (blockStart, maskedBits);
217
218 if (UINT_COMPARE (blockEnd, mcg->_rangeMin) < 0 ||
219 UINT_COMPARE (blockStart, mcg->_rangeMax) > 0) {
220 return;
221 }
222
223 if (UINT_COMPARE (blockStart, mcg->_rangeMin) >= 0 &&
224 UINT_COMPARE (blockEnd, mcg->_rangeMax) <= 0 &&
225 DECORATE_NAME (MinCoverGenerator_isLevelStored) (mcg, maskedBits)) {
226 char *edge = DECORATE_NAME (MinCoverGenerator_toString) (
227 mcg, blockStart, maskedBits);
228 _mc_array_append_val (c, edge);
229 return;
230 }
231
232 BSON_ASSERT (maskedBits > 0);
233
234 const size_t newBits = maskedBits - 1u;
235 DECORATE_NAME (MinCoverGenerator_minCoverRec) (mcg, c, blockStart, newBits);
236 DECORATE_NAME (MinCoverGenerator_minCoverRec)
237 (mcg,
238 c,
239 UINT_BITOR (blockStart, UINT_LSHIFT (UINT_C (1), (int) newBits)),
240 newBits);
241}
242
243static inline mc_mincover_t *
244DECORATE_NAME (MinCoverGenerator_minCover) (DECORATE_NAME (MinCoverGenerator) *
245 mcg)
246{
247 BSON_ASSERT_PARAM (mcg);
248 mc_mincover_t *mc = mc_mincover_new ();
249 DECORATE_NAME (MinCoverGenerator_minCoverRec)
250 (mcg, &mc->mincover, ZERO, mcg->_maxlen);
251 return mc;
252}
253
254// adjustBounds increments *lowerBound if includeLowerBound is false and
255// decrements *upperBound if includeUpperBound is false.
256// lowerBound, min, upperBound, and max are expected to come from the result
257// of mc_getTypeInfo.
258static bool
259DECORATE_NAME (adjustBounds) (UINT_T *lowerBound,
260 bool includeLowerBound,
261 UINT_T min,
262 UINT_T *upperBound,
263 bool includeUpperBound,
264 UINT_T max,
265 mongocrypt_status_t *status)
266{
267 BSON_ASSERT_PARAM (lowerBound);
268 BSON_ASSERT_PARAM (upperBound);
269
270 if (!includeLowerBound) {
271 if (UINT_COMPARE (*lowerBound, max) >= 0) {
272 CLIENT_ERR ("Lower bound (%" UINT_FMT_S
273 ") must be less than the range maximum (%" UINT_FMT_S
274 ") if lower bound is excluded from range.",
275 UINT_FMT_ARG (*lowerBound),
276 UINT_FMT_ARG (max));
277 return false;
278 }
279 *lowerBound = UINT_ADD (*lowerBound, UINT_C (1));
280 }
281 if (!includeUpperBound) {
282 if (UINT_COMPARE (*upperBound, min) <= 0) {
283 CLIENT_ERR ("Upper bound (%" UINT_FMT_S
284 ") must be greater than the range minimum (%" UINT_FMT_S
285 ") if upper bound is excluded from range.",
286 UINT_FMT_ARG (*upperBound),
287 UINT_FMT_ARG (min));
288 return false;
289 }
290 *upperBound = UINT_SUB (*upperBound, UINT_C (1));
291 }
292 return true;
293}
294
295#undef UINT_T
296#undef UINT_C
297#undef UINT_FMT_S
298#undef UINT_FMT_ARG
299#undef DECORATE_NAME
300#undef BITS
301#undef UINT_COMPARE
302#undef UINT_ADD
303#undef UINT_SUB
304#undef UINT_LSHIFT
305#undef UINT_BITOR
306#undef MC_UINT_MAX
307#undef ZERO
308#undef UINT_LESSTHAN
struct _mongocrypt_status_t mongocrypt_status_t
Definition: mongocrypt.h:148
Definition: mc-range-mincover-generator.template.h:104