libmongocrypt
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
71 static 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 
86 static 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.
100 typedef 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 
109 static 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 
151 static 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.
157 static 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 
172 static 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 
179 char *
180 DECORATE_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 
196 static 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 
223 static 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.
235 static 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