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) && \
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
72 static inline UINT_T
73 DECORATE_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 
88 static inline int
89 DECORATE_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.
104 typedef 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 
112 static 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 
151 static inline void
152 DECORATE_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.
160 static inline UINT_T
161 DECORATE_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 
177 static inline bool
178 DECORATE_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 
186 char *
187 DECORATE_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 
207 static inline void
208 DECORATE_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 
243 static inline mc_mincover_t *
244 DECORATE_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.
258 static bool
259 DECORATE_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