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 #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
59 static 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 
74 static 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.
88 typedef struct {
89  UINT_T _rangeMin;
90  UINT_T _rangeMax;
91  size_t _sparsity;
92  int32_t _trimFactor;
93  // _maxlen is the maximum bit length of edges in the mincover.
94  size_t _maxlen;
95 } DECORATE_NAME(MinCoverGenerator);
96 
97 static 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  mc_optional_int32_t opt_trimFactor,
103  mongocrypt_status_t *status,
104  bool use_range_v2) {
105  BSON_ASSERT_PARAM(status);
106 
107  if (UINT_COMPARE(rangeMin, rangeMax) > 0) {
108  CLIENT_ERR("Range min (%" UINT_FMT_S ") must be less than or equal to range max (%" UINT_FMT_S
109  ") for range search",
110  UINT_FMT_ARG(rangeMin),
111  UINT_FMT_ARG(rangeMax));
112  return NULL;
113  }
114  if (UINT_COMPARE(rangeMax, max) > 0) {
115  CLIENT_ERR("Range max (%" UINT_FMT_S ") must be less than or equal to max (%" UINT_FMT_S ") for range search",
116  UINT_FMT_ARG(rangeMax),
117  UINT_FMT_ARG(max));
118  return NULL;
119  }
120 
121  if (sparsity == 0) {
122  CLIENT_ERR("Sparsity must be > 0");
123  return NULL;
124  }
125  size_t maxlen = (size_t)BITS - DECORATE_NAME(mc_count_leading_zeros)(max);
126  int32_t trimFactor = trimFactorDefault(maxlen, opt_trimFactor, use_range_v2);
127  if (trimFactor != 0 && mc_cmp_greater_equal_su(trimFactor, maxlen)) {
128  CLIENT_ERR("Trim factor must be less than the number of bits (%ld) used to represent an element of the domain, "
129  "but got %" PRId32,
130  maxlen,
131  trimFactor);
132  return NULL;
133  }
134  if (trimFactor < 0) {
135  CLIENT_ERR("Trim factor must be >= 0, but got (%" PRId32 ")", trimFactor);
136  return NULL;
137  }
138  DECORATE_NAME(MinCoverGenerator) *mcg = bson_malloc0(sizeof(DECORATE_NAME(MinCoverGenerator)));
139  mcg->_rangeMin = rangeMin;
140  mcg->_rangeMax = rangeMax;
141  mcg->_maxlen = (size_t)BITS - DECORATE_NAME(mc_count_leading_zeros)(max);
142  mcg->_sparsity = sparsity;
143  mcg->_trimFactor = trimFactor;
144  return mcg;
145 }
146 
147 static inline void DECORATE_NAME(MinCoverGenerator_destroy)(DECORATE_NAME(MinCoverGenerator) * mcg) {
148  bson_free(mcg);
149 }
150 
151 // applyMask applies a mask of 1 bits starting from the right.
152 // Bits 0 to bit-1 are replaced with 1. Other bits are left as-is.
153 static inline UINT_T DECORATE_NAME(applyMask)(UINT_T value, size_t maskedBits) {
154  const UINT_T ones = MC_UINT_MAX;
155 
156  BSON_ASSERT(maskedBits <= (size_t)BITS);
157  BSON_ASSERT(maskedBits >= 0);
158 
159  if (maskedBits == 0) {
160  return value;
161  }
162 
163  const size_t shift = ((size_t)BITS - maskedBits);
164  const UINT_T mask = UINT_LSHIFT(ones, -(int)shift);
165  return UINT_BITOR(value, mask);
166 }
167 
168 static inline bool DECORATE_NAME(MinCoverGenerator_isLevelStored)(DECORATE_NAME(MinCoverGenerator) * mcg,
169  size_t maskedBits) {
170  BSON_ASSERT_PARAM(mcg);
171  size_t level = mcg->_maxlen - maskedBits;
172  BSON_ASSERT(mc_in_range_size_t_signed(mcg->_trimFactor));
173  size_t trimFactor_sz = (size_t)mcg->_trimFactor;
174  return 0 == maskedBits || (level >= trimFactor_sz && 0 == (level % mcg->_sparsity));
175 }
176 
177 char *
178 DECORATE_NAME(MinCoverGenerator_toString)(DECORATE_NAME(MinCoverGenerator) * mcg, UINT_T start, size_t maskedBits) {
179  BSON_ASSERT_PARAM(mcg);
180  BSON_ASSERT(maskedBits <= mcg->_maxlen);
181  BSON_ASSERT(maskedBits <= (size_t)BITS);
182  BSON_ASSERT(maskedBits >= 0);
183 
184  if (maskedBits == mcg->_maxlen) {
185  return bson_strdup("root");
186  }
187 
188  UINT_T shifted = UINT_LSHIFT(start, -(int)maskedBits);
189  mc_bitstring valueBin = DECORATE_NAME(mc_convert_to_bitstring)(shifted);
190  char *ret = bson_strndup(valueBin.str + ((size_t)BITS - mcg->_maxlen + maskedBits), mcg->_maxlen + maskedBits);
191  return ret;
192 }
193 
194 static inline void DECORATE_NAME(MinCoverGenerator_minCoverRec)(DECORATE_NAME(MinCoverGenerator) * mcg,
195  mc_array_t *c,
196  UINT_T blockStart,
197  size_t maskedBits) {
198  BSON_ASSERT_PARAM(mcg);
199  BSON_ASSERT_PARAM(c);
200  const UINT_T blockEnd = DECORATE_NAME(applyMask)(blockStart, maskedBits);
201 
202  if (UINT_COMPARE(blockEnd, mcg->_rangeMin) < 0 || UINT_COMPARE(blockStart, mcg->_rangeMax) > 0) {
203  return;
204  }
205 
206  if (UINT_COMPARE(blockStart, mcg->_rangeMin) >= 0 && UINT_COMPARE(blockEnd, mcg->_rangeMax) <= 0
207  && DECORATE_NAME(MinCoverGenerator_isLevelStored)(mcg, maskedBits)) {
208  char *edge = DECORATE_NAME(MinCoverGenerator_toString)(mcg, blockStart, maskedBits);
209  _mc_array_append_val(c, edge);
210  return;
211  }
212 
213  BSON_ASSERT(maskedBits > 0);
214 
215  const size_t newBits = maskedBits - 1u;
216  DECORATE_NAME(MinCoverGenerator_minCoverRec)(mcg, c, blockStart, newBits);
217  DECORATE_NAME(MinCoverGenerator_minCoverRec)
218  (mcg, c, UINT_BITOR(blockStart, UINT_LSHIFT(UINT_C(1), (int)newBits)), newBits);
219 }
220 
221 static inline mc_mincover_t *DECORATE_NAME(MinCoverGenerator_minCover)(DECORATE_NAME(MinCoverGenerator) * mcg) {
222  BSON_ASSERT_PARAM(mcg);
223  mc_mincover_t *mc = mc_mincover_new();
224  DECORATE_NAME(MinCoverGenerator_minCoverRec)
225  (mcg, &mc->mincover, ZERO, mcg->_maxlen);
226  return mc;
227 }
228 
229 static inline int32_t DECORATE_NAME(MinCoverGenerator_usedTrimFactor)(DECORATE_NAME(MinCoverGenerator) * mcg) {
230  BSON_ASSERT_PARAM(mcg);
231  return mcg->_trimFactor;
232 }
233 
234 // adjustBounds increments *lowerBound if includeLowerBound is false and
235 // decrements *upperBound if includeUpperBound is false.
236 // lowerBound, min, upperBound, and max are expected to come from the result
237 // of mc_getTypeInfo.
238 static bool DECORATE_NAME(adjustBounds)(UINT_T *lowerBound,
239  bool includeLowerBound,
240  UINT_T min,
241  UINT_T *upperBound,
242  bool includeUpperBound,
243  UINT_T max,
244  mongocrypt_status_t *status) {
245  BSON_ASSERT_PARAM(lowerBound);
246  BSON_ASSERT_PARAM(upperBound);
247 
248  if (!includeLowerBound) {
249  if (UINT_COMPARE(*lowerBound, max) >= 0) {
250  CLIENT_ERR("Lower bound (%" UINT_FMT_S ") must be less than the range maximum (%" UINT_FMT_S
251  ") if lower bound is excluded from range.",
252  UINT_FMT_ARG(*lowerBound),
253  UINT_FMT_ARG(max));
254  return false;
255  }
256  *lowerBound = UINT_ADD(*lowerBound, UINT_C(1));
257  }
258  if (!includeUpperBound) {
259  if (UINT_COMPARE(*upperBound, min) <= 0) {
260  CLIENT_ERR("Upper bound (%" UINT_FMT_S ") must be greater than the range minimum (%" UINT_FMT_S
261  ") if upper bound is excluded from range.",
262  UINT_FMT_ARG(*upperBound),
263  UINT_FMT_ARG(min));
264  return false;
265  }
266  *upperBound = UINT_SUB(*upperBound, UINT_C(1));
267  }
268  return true;
269 }
270 
271 #undef UINT_T
272 #undef UINT_C
273 #undef UINT_FMT_S
274 #undef UINT_FMT_ARG
275 #undef DECORATE_NAME
276 #undef BITS
277 #undef UINT_COMPARE
278 #undef UINT_ADD
279 #undef UINT_SUB
280 #undef UINT_LSHIFT
281 #undef UINT_BITOR
282 #undef MC_UINT_MAX
283 #undef ZERO
284 #undef UINT_LESSTHAN
struct _mongocrypt_status_t mongocrypt_status_t
Definition: mongocrypt.h:152
Definition: mc-range-mincover-generator.template.h:88