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