Line data Source code
1 : /*
2 : Copyright 2018-2024, Barcelona Supercomputing Center (BSC), Spain
3 : Copyright 2015-2024, Johannes Gutenberg Universitaet Mainz, Germany
4 :
5 : This software was partially supported by the
6 : EC H2020 funded project NEXTGenIO (Project ID: 671951, www.nextgenio.eu).
7 :
8 : This software was partially supported by the
9 : ADA-FS project under the SPPEXA project funded by the DFG.
10 :
11 : This file is part of GekkoFS.
12 :
13 : GekkoFS is free software: you can redistribute it and/or modify
14 : it under the terms of the GNU General Public License as published by
15 : the Free Software Foundation, either version 3 of the License, or
16 : (at your option) any later version.
17 :
18 : GekkoFS is distributed in the hope that it will be useful,
19 : but WITHOUT ANY WARRANTY; without even the implied warranty of
20 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 : GNU General Public License for more details.
22 :
23 : You should have received a copy of the GNU General Public License
24 : along with GekkoFS. If not, see <https://www.gnu.org/licenses/>.
25 :
26 : SPDX-License-Identifier: GPL-3.0-or-later
27 : */
28 :
29 : #include <catch2/catch.hpp>
30 : #include <fmt/format.h>
31 : #include <arithmetic.hpp>
32 :
33 : using namespace gkfs::utils::arithmetic;
34 : constexpr auto test_reps = 200u;
35 :
36 : namespace {
37 :
38 : /**
39 : * Check if @n is a power of two by (rather inefficiently)
40 : * performing successive divisions by 2 in an attempt to reach 1.
41 : *
42 : * @param n the number to check
43 : * @returns true if @n is a power of 2, false otherwise
44 : */
45 : bool
46 20000 : check_power_of_2(uint64_t n) {
47 20000 : if(n == 0) {
48 : return false;
49 : }
50 :
51 39980 : while(n != 1) {
52 39952 : if(n % 2 != 0) {
53 : return false;
54 : }
55 19982 : n /= 2;
56 : }
57 :
58 : return true;
59 : }
60 :
61 : } // namespace
62 :
63 :
64 10002 : SCENARIO(" powers of 2 can be correctly detected ",
65 : "[utils][numeric][is_power_of_2]") {
66 :
67 40008 : GIVEN(" a positive number ") {
68 :
69 30007 : WHEN(" n is 0 ") {
70 :
71 1 : const uint64_t n = 0;
72 :
73 4 : THEN(" is_power_of_2(n) returns false ") {
74 2 : REQUIRE(is_power_of_2(n) == false);
75 : }
76 : }
77 :
78 30007 : WHEN(" n is 1 ") {
79 :
80 1 : const uint64_t n = 1;
81 :
82 4 : THEN(" is_power_of_2(n) returns true ") {
83 2 : REQUIRE(is_power_of_2(n) == true);
84 : }
85 : }
86 :
87 40006 : WHEN(" n is neither 0 nor 1 ") {
88 :
89 40014 : AND_WHEN(" n is a power of 2 ") {
90 :
91 10016 : const std::size_t n = GENERATE(
92 : filter([](uint64_t m) { return check_power_of_2(m); },
93 : range(0, 10000)));
94 :
95 56 : THEN(" is_power_of_2(n) returns false ") {
96 42 : REQUIRE(is_power_of_2(n) == true);
97 : }
98 : }
99 :
100 39986 : AND_WHEN(" n is not a power of 2 ") {
101 :
102 19988 : const std::size_t n = GENERATE(
103 : filter([](uint64_t m) { return !check_power_of_2(m); },
104 : range(0, 10000)));
105 :
106 39944 : THEN(" is_power_of_2(n) returns false ") {
107 29958 : REQUIRE(is_power_of_2(n) == false);
108 : }
109 : }
110 : }
111 : }
112 10002 : }
113 :
114 56014 : SCENARIO(" divisibility by powers of 2 can be correctly detected ",
115 : "[utils][numeric][is_aligned]") {
116 :
117 224056 : GIVEN(" a number and a block_size ") {
118 :
119 56016 : const uint64_t n = GENERATE(range(0, 1000), range(20000, 23000),
120 : std::numeric_limits<uint64_t>::max());
121 56014 : const std::size_t block_size =
122 80028002 : GENERATE(filter([](uint64_t bs) { return is_power_of_2(bs); },
123 : range(0, 10000)));
124 :
125 56014 : CAPTURE(n, block_size);
126 :
127 56014 : bool expected = n % block_size == 0;
128 112028 : REQUIRE(is_aligned(n, block_size) == expected);
129 : }
130 56014 : }
131 :
132 6817 : SCENARIO(" offsets can be left-aligned to block size boundaries ",
133 : "[utils][numeric][align_left]") {
134 :
135 27268 : GIVEN(" a block size ") {
136 :
137 6817 : const std::size_t block_size =
138 206802 : GENERATE(filter([](uint64_t bs) { return is_power_of_2(bs); },
139 : range(0, 100000)));
140 :
141 20468 : WHEN(" offset is 0 ") {
142 :
143 17 : const uint64_t offset = 0;
144 :
145 34 : CAPTURE(offset, block_size);
146 :
147 68 : THEN(" the left-aligned offset is 0 ") {
148 17 : const uint64_t aligned_offset = align_left(offset, block_size);
149 34 : REQUIRE(aligned_offset == 0);
150 : }
151 : }
152 :
153 23851 : WHEN(" offset is smaller than block size ") {
154 :
155 3434 : const uint64_t offset = GENERATE_COPY(
156 : take(test_reps, random(std::size_t{0}, block_size - 1)));
157 :
158 6800 : CAPTURE(offset, block_size);
159 :
160 13600 : THEN(" the left-aligned offset is 0 ") {
161 3400 : const uint64_t aligned_offset = align_left(offset, block_size);
162 6800 : REQUIRE(aligned_offset == 0);
163 : }
164 : }
165 :
166 23851 : WHEN(" offset is larger than block size ") {
167 :
168 3434 : const uint64_t offset = GENERATE_COPY(
169 : take(test_reps, random(block_size, block_size * 31)));
170 :
171 6800 : CAPTURE(offset, block_size);
172 :
173 10200 : THEN(" the left-aligned offset is the left boundary of the "
174 3400 : "containing block ") {
175 3400 : const uint64_t aligned_offset = align_left(offset, block_size);
176 3400 : const uint64_t exp_offset =
177 3400 : static_cast<uint64_t>(offset / block_size) * block_size;
178 6800 : REQUIRE(aligned_offset == exp_offset);
179 : }
180 : }
181 : }
182 6817 : }
183 :
184 6817 : SCENARIO(" offsets can be right-aligned to block size boundaries ",
185 : "[utils][numeric][align_right]") {
186 :
187 27268 : GIVEN(" a block size ") {
188 :
189 206802 : const std::size_t block_size = GENERATE(filter(
190 : [](uint64_t bs) { return is_power_of_2(bs); }, range(0, 100000)));
191 :
192 20468 : WHEN(" offset is 0 ") {
193 :
194 17 : const uint64_t offset = 0;
195 :
196 34 : CAPTURE(offset, block_size);
197 :
198 68 : THEN(" the right-aligned offset is block_size ") {
199 17 : const uint64_t aligned_offset = align_right(offset, block_size);
200 17 : const uint64_t expected_offset = block_size;
201 34 : REQUIRE(aligned_offset == expected_offset);
202 : }
203 : }
204 :
205 23851 : WHEN(" offset is smaller than block_size ") {
206 :
207 3434 : const uint64_t offset = GENERATE_COPY(
208 : take(test_reps, random(std::size_t{0}, block_size - 1)));
209 :
210 6800 : CAPTURE(offset, block_size);
211 :
212 13600 : THEN(" the right-aligned offset is 0 ") {
213 3400 : const uint64_t aligned_offset = align_right(offset, block_size);
214 3400 : const uint64_t expected_offset = block_size;
215 6800 : REQUIRE(aligned_offset == expected_offset);
216 : }
217 : }
218 :
219 23851 : WHEN(" offset is larger than block_size ") {
220 :
221 3434 : const uint64_t offset = GENERATE_COPY(
222 : take(test_reps, random(block_size, block_size * 31)));
223 :
224 6800 : CAPTURE(offset, block_size);
225 :
226 10200 : THEN(" the right-aligned offset is the right boundary of the "
227 3400 : "containing block ") {
228 3400 : const uint64_t aligned_offset = align_right(offset, block_size);
229 3400 : const uint64_t expected_offset =
230 3400 : static_cast<uint64_t>(offset / block_size + 1) *
231 : block_size;
232 6800 : REQUIRE(aligned_offset == expected_offset);
233 : }
234 : }
235 : }
236 6817 : }
237 :
238 6851 : SCENARIO(" overrun distance can be computed correctly ",
239 : "[utils][numeric][block_overrun]") {
240 :
241 27404 : GIVEN(" a block size ") {
242 :
243 206836 : const std::size_t block_size = GENERATE(filter(
244 : [](uint64_t bs) { return is_power_of_2(bs); }, range(0, 100000)));
245 :
246 23987 : WHEN(" offset is smaller than block_size ") {
247 :
248 10319 : AND_WHEN(" offset equals 0 ") {
249 :
250 17 : const uint64_t offset = 0;
251 :
252 34 : CAPTURE(offset, block_size);
253 :
254 68 : THEN(" the computed overrun distance equals 0 ") {
255 17 : const uint64_t overrun = block_overrun(offset, block_size);
256 17 : const uint64_t expected_overrun = 0;
257 34 : REQUIRE(overrun == expected_overrun);
258 : }
259 : }
260 :
261 13702 : AND_WHEN(" 0 < offset < block_size ") {
262 :
263 3434 : const uint64_t offset = GENERATE_COPY(take(
264 : test_reps, random(std::size_t{0}, block_size - 1)));
265 :
266 6800 : CAPTURE(offset, block_size);
267 :
268 13600 : THEN(" the computed overrun distance equals offset ") {
269 3400 : const uint64_t overrun = block_overrun(offset, block_size);
270 3400 : const uint64_t expected_overrun = offset;
271 6800 : REQUIRE(overrun == expected_overrun);
272 : }
273 : }
274 :
275 10319 : AND_WHEN(" offset equals block_size - 1 ") {
276 :
277 17 : const uint64_t offset = block_size - 1;
278 :
279 34 : CAPTURE(offset, block_size);
280 :
281 68 : THEN(" the computed overrun distance equals block_size - 1 ") {
282 17 : const uint64_t overrun = block_overrun(offset, block_size);
283 17 : const uint64_t expected_overrun = block_size - 1;
284 34 : REQUIRE(overrun == expected_overrun);
285 : }
286 : }
287 : }
288 :
289 20570 : WHEN(" offset equals block_size ") {
290 :
291 17 : const uint64_t offset = block_size;
292 :
293 34 : CAPTURE(offset, block_size);
294 :
295 68 : THEN(" the computed overrun distance equals 0 ") {
296 17 : const uint64_t overrun = block_overrun(offset, block_size);
297 17 : const uint64_t expected_overrun = 0;
298 34 : REQUIRE(overrun == expected_overrun);
299 : }
300 : }
301 :
302 23953 : WHEN(" offset is larger than block_size ") {
303 :
304 3434 : const uint64_t offset = GENERATE_COPY(
305 : take(test_reps, random(block_size, block_size * 31)));
306 :
307 6800 : CAPTURE(offset, block_size);
308 :
309 10200 : THEN(" the computed overrun distance equals the difference between "
310 3400 : "offset and its closest block's left boundary ") {
311 3400 : const uint64_t overrun = block_overrun(offset, block_size);
312 3400 : const uint64_t expected_overrun =
313 3400 : offset -
314 3400 : static_cast<uint64_t>(offset / block_size) * block_size;
315 6800 : REQUIRE(overrun == expected_overrun);
316 : }
317 : }
318 : }
319 6851 : }
320 :
321 6851 : SCENARIO(" underrun distance can be computed correctly ",
322 : "[utils][numeric][block_underrun]") {
323 :
324 27404 : GIVEN(" a block size ") {
325 :
326 206836 : const std::size_t block_size = GENERATE(filter(
327 : [](uint64_t bs) { return is_power_of_2(bs); }, range(0, 100000)));
328 :
329 23987 : WHEN(" offset is smaller than block_size ") {
330 :
331 10319 : AND_WHEN(" offset equals 0 ") {
332 :
333 17 : const uint64_t offset = 0;
334 :
335 34 : CAPTURE(offset, block_size);
336 :
337 68 : THEN(" the computed underrun distance equals block_size ") {
338 17 : const uint64_t underrun =
339 17 : block_underrun(offset, block_size);
340 17 : const uint64_t expected_underrun = block_size;
341 34 : REQUIRE(underrun == expected_underrun);
342 : }
343 : }
344 :
345 13702 : AND_WHEN(" 0 < offset < block_size ") {
346 :
347 3434 : const uint64_t offset = GENERATE_COPY(take(
348 : test_reps, random(std::size_t{0}, block_size - 1)));
349 :
350 6800 : CAPTURE(offset, block_size);
351 :
352 13600 : THEN(" the computed underrun distance equals offset ") {
353 3400 : const uint64_t underrun =
354 3400 : block_underrun(offset, block_size);
355 3400 : const uint64_t expected_underrun = block_size - offset;
356 6800 : REQUIRE(underrun == expected_underrun);
357 : }
358 : }
359 :
360 10319 : AND_WHEN(" offset equals block_size - 1 ") {
361 :
362 17 : const uint64_t offset = block_size - 1;
363 :
364 34 : CAPTURE(offset, block_size);
365 :
366 68 : THEN(" the computed underrun distance equals block_size - 1 ") {
367 17 : const uint64_t underrun =
368 17 : block_underrun(offset, block_size);
369 17 : const uint64_t expected_underrun = block_size - offset;
370 34 : REQUIRE(underrun == expected_underrun);
371 : }
372 : }
373 : }
374 :
375 20570 : WHEN(" offset equals block_size ") {
376 :
377 17 : const uint64_t offset = block_size;
378 :
379 34 : CAPTURE(offset, block_size);
380 :
381 68 : THEN(" the computed underrun distance equals block_size ") {
382 17 : const uint64_t underrun = block_underrun(offset, block_size);
383 17 : const uint64_t expected_underrun = block_size;
384 34 : REQUIRE(underrun == expected_underrun);
385 : }
386 : }
387 :
388 23953 : WHEN(" offset is larger than block_size ") {
389 :
390 3434 : const uint64_t offset = GENERATE_COPY(
391 : take(test_reps, random(block_size, block_size * 31)));
392 :
393 6800 : CAPTURE(offset, block_size);
394 :
395 10200 : THEN(" the computed underrun distance equals the difference between "
396 3400 : "offset and its closest block's right boundary ") {
397 3400 : const uint64_t underrun = block_underrun(offset, block_size);
398 3400 : const uint64_t expected_underrun =
399 3400 : static_cast<uint64_t>(offset / block_size + 1) *
400 3400 : block_size -
401 : offset;
402 6800 : REQUIRE(underrun == expected_underrun);
403 : }
404 : }
405 : }
406 6851 : }
407 :
408 6885 : SCENARIO(" chunk IDs can be computed correctly ",
409 : "[utils][numeric][block_index]") {
410 :
411 27540 : GIVEN(" an offset and a block size ") {
412 :
413 206870 : const std::size_t block_size = GENERATE(filter(
414 : [](uint64_t bs) { return is_power_of_2(bs); }, range(0, 100000)));
415 :
416 24089 : WHEN(" offset is smaller than block_size ") {
417 :
418 10319 : AND_WHEN(" offset equals 0 ") {
419 :
420 17 : const uint64_t offset = 0;
421 :
422 34 : CAPTURE(offset, block_size);
423 :
424 68 : THEN(" the computed chunk ID equals 0 ") {
425 17 : const uint64_t id = block_index(offset, block_size);
426 17 : const uint64_t expected_id = 0;
427 34 : REQUIRE(id == expected_id);
428 : }
429 : }
430 :
431 13702 : AND_WHEN(" 0 < offset < block_size ") {
432 :
433 3434 : const uint64_t offset = GENERATE_COPY(take(
434 : test_reps, random(std::size_t{0}, block_size - 1)));
435 :
436 6800 : CAPTURE(offset, block_size);
437 :
438 13600 : THEN(" the computed chunk ID equals 0 ") {
439 3400 : const uint64_t id = block_index(offset, block_size);
440 3400 : const uint64_t expected_id = 0;
441 6800 : REQUIRE(id == expected_id);
442 : }
443 : }
444 :
445 10319 : AND_WHEN(" offset equals block_size - 1 ") {
446 :
447 17 : const uint64_t offset = block_size - 1;
448 :
449 34 : CAPTURE(offset, block_size);
450 :
451 68 : THEN(" the computed chunk ID equals 0 ") {
452 17 : const uint64_t id = block_index(offset, block_size);
453 17 : const uint64_t expected_id = 0;
454 34 : REQUIRE(id == expected_id);
455 : }
456 : }
457 : }
458 :
459 20672 : WHEN(" offset equals block_size ") {
460 :
461 17 : const uint64_t offset = block_size;
462 :
463 34 : CAPTURE(offset, block_size);
464 :
465 68 : THEN(" the computed chunk ID equals 1 ") {
466 17 : const uint64_t id = block_index(offset, block_size);
467 17 : const uint64_t expected_id = 1;
468 34 : REQUIRE(id == expected_id);
469 : }
470 : }
471 :
472 24089 : WHEN(" offset is larger than block_size ") {
473 :
474 13702 : AND_WHEN(" block_size < offset < 2^63 - 1 ") {
475 :
476 3434 : const uint64_t offset = GENERATE_COPY(take(
477 : test_reps,
478 : random(block_size,
479 : std::numeric_limits<uint64_t>::max() / 2 - 1)));
480 :
481 6800 : CAPTURE(offset, block_size);
482 :
483 10200 : THEN(" the computed chunk ID is equal to dividing the offset by "
484 3400 : "the block_size ") {
485 :
486 3400 : const uint64_t id = block_index(offset, block_size);
487 3400 : const uint64_t expected_id = offset / block_size;
488 6800 : REQUIRE(id == expected_id);
489 : }
490 : }
491 :
492 : // The following test specifically exercises issue #137
493 10319 : AND_WHEN(" offset == 2^63 ") {
494 :
495 17 : const uint64_t offset =
496 : std::numeric_limits<uint64_t>::max() / 2 + 1;
497 :
498 34 : CAPTURE(offset, block_size);
499 :
500 51 : THEN(" the computed chunk ID is equal to dividing the offset by "
501 17 : "the block_size ") {
502 :
503 17 : const uint64_t id = block_index(offset, block_size);
504 17 : const uint64_t expected_id = offset / block_size;
505 34 : REQUIRE(id == expected_id);
506 : }
507 : }
508 :
509 : // The following test specifically exercises issue #137
510 10319 : AND_WHEN(" offset == 2^64 - 1") {
511 :
512 17 : const uint64_t offset = std::numeric_limits<uint64_t>::max();
513 :
514 34 : CAPTURE(offset, block_size);
515 :
516 51 : THEN(" the computed chunk ID is equal to dividing the offset by "
517 17 : "the block_size ") {
518 :
519 17 : const uint64_t id = block_index(offset, block_size);
520 17 : const uint64_t expected_id = offset / block_size;
521 34 : REQUIRE(id == expected_id);
522 : }
523 : }
524 : }
525 : }
526 6885 : }
527 :
528 2750770 : SCENARIO(" the number of chunks involved in an operation can be computed "
529 : "correctly ",
530 : "[utils][numeric][block_count]") {
531 :
532 11003080 : GIVEN(" an offset, an operation size, and a block size ") {
533 :
534 2950755 : const std::size_t block_size = GENERATE(filter(
535 : [](uint64_t bs) { return is_power_of_2(bs); }, range(0, 100000)));
536 :
537 9629378 : WHEN(" offset < block_size ") {
538 :
539 4138038 : AND_WHEN(" offset == 0 ") {
540 :
541 6834 : const uint64_t offset = 0;
542 :
543 20519 : AND_WHEN(" offset + size == 0 ") {
544 :
545 17 : const size_t size = 0;
546 :
547 34 : CAPTURE(offset, size, block_size);
548 :
549 68 : THEN(" the computed block count == 0 ") {
550 17 : const std::size_t n =
551 17 : block_count(offset, size, block_size);
552 17 : const std::size_t expected_n = 0;
553 34 : REQUIRE(n == expected_n);
554 : }
555 : }
556 :
557 23902 : AND_WHEN(" 0 < offset + size < block_size ") {
558 :
559 3434 : const size_t size = GENERATE_COPY(take(
560 : test_reps, random(std::size_t{1}, block_size)));
561 :
562 6800 : CAPTURE(offset, size, block_size);
563 :
564 13600 : THEN(" the computed block count == 1 ") {
565 3400 : const std::size_t n =
566 3400 : block_count(offset, size, block_size);
567 3400 : const std::size_t expected_n = 1;
568 6800 : REQUIRE(n == expected_n);
569 : }
570 : }
571 :
572 20519 : AND_WHEN(" offset + size == block_size ") {
573 :
574 17 : const size_t size = block_size;
575 :
576 34 : CAPTURE(offset, size, block_size);
577 :
578 68 : THEN(" the computed block count == 1 ") {
579 17 : const std::size_t n =
580 17 : block_count(offset, size, block_size);
581 17 : const std::size_t expected_n = 1;
582 34 : REQUIRE(n == expected_n);
583 : }
584 : }
585 :
586 23902 : AND_WHEN(" offset + size > block_size ") {
587 :
588 3434 : const size_t size = GENERATE_COPY(
589 : take(test_reps,
590 : random(block_size + 1,
591 : std::numeric_limits<uint64_t>::max())));
592 :
593 6800 : CAPTURE(offset, size, block_size);
594 :
595 10200 : THEN(" the computed block count corresponds to the number "
596 3400 : "of blocks involved in the operation ") {
597 3400 : const std::size_t n =
598 3400 : block_count(offset, size, block_size);
599 6800 : const std::size_t expected_n =
600 3400 : (offset + size) / block_size -
601 3400 : offset / block_size +
602 3400 : ((offset + size) % block_size ? 1u : 0);
603 :
604 6800 : REQUIRE(n == expected_n);
605 : }
606 : }
607 : }
608 :
609 5498004 : AND_WHEN(" 0 < offset < block_size ") {
610 :
611 1366834 : const uint64_t offset = GENERATE_COPY(take(
612 : test_reps, random(std::size_t{0}, block_size - 1)));
613 :
614 4103800 : AND_WHEN(" offset + size == offset ") {
615 :
616 3400 : const size_t size = 0;
617 :
618 6800 : CAPTURE(offset, size, block_size);
619 :
620 13600 : THEN(" the computed block count == 1 ") {
621 3400 : const std::size_t n =
622 3400 : block_count(offset, size, block_size);
623 3400 : const std::size_t expected_n = 0;
624 6800 : REQUIRE(n == expected_n);
625 : }
626 : }
627 :
628 4780400 : AND_WHEN(" 0 < offset + size < block_size ") {
629 :
630 686800 : const size_t size = GENERATE_COPY(
631 : take(test_reps,
632 : random(std::size_t{1}, block_size - offset)));
633 :
634 1360000 : CAPTURE(offset, size, block_size);
635 :
636 2720000 : THEN(" the computed block count equals 1 ") {
637 680000 : const std::size_t n =
638 680000 : block_count(offset, size, block_size);
639 680000 : const std::size_t expected_n = 1;
640 1360000 : REQUIRE(n == expected_n);
641 : }
642 : }
643 :
644 4103800 : AND_WHEN(" offset + size == block_size ") {
645 :
646 3400 : const size_t size = block_size - offset;
647 :
648 6800 : CAPTURE(offset, size, block_size);
649 :
650 13600 : THEN(" the computed block count == 1 ") {
651 3400 : const std::size_t n =
652 3400 : block_count(offset, size, block_size);
653 3400 : const std::size_t expected_n = 1;
654 6800 : REQUIRE(n == expected_n);
655 : }
656 : }
657 :
658 4780400 : AND_WHEN(" offset + size > block_size ") {
659 :
660 686800 : const size_t size = GENERATE_COPY(
661 : take(test_reps,
662 : random(block_size + 1,
663 : std::numeric_limits<uint64_t>::max())));
664 :
665 1360000 : CAPTURE(offset, size, block_size);
666 :
667 2040000 : THEN(" the computed block count corresponds to the number "
668 680000 : "of blocks involved in the operation ") {
669 680000 : const std::size_t n =
670 680000 : block_count(offset, size, block_size);
671 1360000 : const std::size_t expected_n =
672 680000 : (offset + size) / block_size -
673 1360000 : offset / block_size +
674 680000 : ((offset + size) % block_size ? 1u : 0);
675 :
676 1360000 : REQUIRE(n == expected_n);
677 : }
678 : }
679 : }
680 :
681 4134638 : AND_WHEN(" offset == block_size - 1 ") {
682 :
683 3434 : const size_t offset = block_size - 1;
684 :
685 10319 : AND_WHEN(" offset + size == offset ") {
686 :
687 17 : const size_t size = 0;
688 :
689 34 : CAPTURE(offset, size, block_size);
690 :
691 68 : THEN(" the computed block count == 0 ") {
692 17 : const std::size_t n =
693 17 : block_count(offset, size, block_size);
694 17 : const std::size_t expected_n = 0;
695 34 : REQUIRE(n == expected_n);
696 : }
697 : }
698 :
699 10319 : AND_WHEN(" offset + size == block_size ") {
700 :
701 17 : const size_t size = 1;
702 :
703 34 : CAPTURE(offset, size, block_size);
704 :
705 68 : THEN(" the computed block count == 1 ") {
706 17 : const std::size_t n =
707 17 : block_count(offset, size, block_size);
708 17 : const std::size_t expected_n = 1;
709 34 : REQUIRE(n == expected_n);
710 : }
711 : }
712 :
713 13702 : AND_WHEN(" offset + size > block_size ") {
714 :
715 3434 : const size_t size = GENERATE_COPY(
716 : take(test_reps,
717 : random(block_size + 1,
718 : std::numeric_limits<uint64_t>::max())));
719 :
720 6800 : CAPTURE(offset, size, block_size);
721 :
722 10200 : THEN(" the computed block count corresponds to the number "
723 3400 : "of blocks involved in the operation ") {
724 3400 : const std::size_t n =
725 3400 : block_count(offset, size, block_size);
726 6800 : const std::size_t expected_n =
727 3400 : (offset + size) / block_size -
728 6800 : offset / block_size +
729 3400 : ((offset + size) % block_size ? 1u : 0);
730 :
731 6800 : REQUIRE(n == expected_n);
732 : }
733 : }
734 : }
735 : }
736 :
737 8259144 : WHEN(" offset == block_size ") {
738 :
739 6834 : const uint64_t offset = block_size;
740 :
741 20519 : AND_WHEN(" offset + size == block_size ") {
742 :
743 17 : const size_t size = 0;
744 :
745 34 : CAPTURE(offset, size, block_size);
746 :
747 68 : THEN(" the computed block count == 1 ") {
748 17 : const std::size_t n = block_count(offset, size, block_size);
749 17 : const std::size_t expected_n = 0;
750 34 : REQUIRE(n == expected_n);
751 : }
752 : }
753 :
754 23902 : AND_WHEN(" offset + size == M * block_size ") {
755 3434 : const size_t m = GENERATE(range(0u, test_reps));
756 3400 : const size_t size = m * block_size;
757 :
758 6800 : CAPTURE(offset, size, block_size);
759 :
760 13600 : THEN(" the computed block count == M ") {
761 3400 : const std::size_t n = block_count(offset, size, block_size);
762 3400 : const std::size_t expected_n = m;
763 6800 : REQUIRE(n == expected_n);
764 : }
765 : }
766 :
767 23902 : AND_WHEN(" offset + size < 2^64 - 1") {
768 :
769 3434 : const size_t size = GENERATE_COPY(take(
770 : test_reps,
771 : random(std::size_t{1},
772 : std::numeric_limits<uint64_t>::max() - offset)));
773 :
774 10200 : THEN(" the computed block count corresponds to the number "
775 3400 : "of blocks involved in the operation ") {
776 3400 : const std::size_t n = block_count(offset, size, block_size);
777 6800 : const std::size_t expected_n =
778 6800 : (offset + size) / block_size - offset / block_size +
779 3400 : ((offset + size) % block_size ? 1u : 0);
780 :
781 6800 : REQUIRE(n == expected_n);
782 : }
783 : }
784 :
785 20519 : AND_WHEN(" offset + size == 2^64 - 1") {
786 :
787 17 : const size_t size =
788 17 : std::numeric_limits<uint64_t>::max() - offset;
789 :
790 51 : THEN(" the computed block count corresponds to the number "
791 17 : "of blocks involved in the operation ") {
792 17 : const std::size_t n = block_count(offset, size, block_size);
793 34 : const std::size_t expected_n =
794 34 : (offset + size) / block_size - offset / block_size +
795 17 : ((offset + size) % block_size ? 1u : 0);
796 :
797 34 : REQUIRE(n == expected_n);
798 : }
799 : }
800 : }
801 :
802 9619178 : WHEN(" offset > block_size ") {
803 :
804 5460604 : AND_WHEN(" block_size < offset < 2^63 - 1 ") {
805 :
806 1360034 : const uint64_t offset = GENERATE_COPY(take(
807 : test_reps,
808 : random(block_size,
809 : std::numeric_limits<uint64_t>::max() / 2 - 1)));
810 :
811 4083400 : AND_WHEN(" offset + size == block_size ") {
812 :
813 3400 : const size_t size = 0;
814 :
815 6800 : CAPTURE(offset, size, block_size);
816 :
817 13600 : THEN(" the computed block count == 1 ") {
818 3400 : const std::size_t n =
819 3400 : block_count(offset, size, block_size);
820 3400 : const std::size_t expected_n = 0;
821 6800 : REQUIRE(n == expected_n);
822 : }
823 : }
824 :
825 4753200 : AND_WHEN(" offset + size == M * block_size ") {
826 680000 : const size_t m = GENERATE_COPY(range(2u, test_reps));
827 673200 : const size_t size = m * block_size - (offset % block_size);
828 :
829 1346400 : CAPTURE(offset, size, block_size, m);
830 :
831 2692800 : THEN(" the computed block count == M ") {
832 673200 : const std::size_t n =
833 673200 : block_count(offset, size, block_size);
834 673200 : const std::size_t expected_n = m;
835 1346400 : REQUIRE(n == expected_n);
836 : }
837 : }
838 :
839 4760000 : AND_WHEN(" offset + size < 2^64 - 1") {
840 :
841 686800 : const size_t size = GENERATE_COPY(
842 : take(test_reps,
843 : random(std::size_t{1},
844 : std::numeric_limits<uint64_t>::max() -
845 : offset)));
846 :
847 2040000 : THEN(" the computed block count corresponds to the number "
848 680000 : "of blocks involved in the operation ") {
849 680000 : const std::size_t n =
850 680000 : block_count(offset, size, block_size);
851 1360000 : const std::size_t expected_n =
852 680000 : (offset + size) / block_size -
853 1360000 : offset / block_size +
854 680000 : ((offset + size) % block_size ? 1u : 0);
855 :
856 1360000 : REQUIRE(n == expected_n);
857 : }
858 : }
859 :
860 4083400 : AND_WHEN(" offset + size == 2^64 - 1") {
861 :
862 3400 : const size_t size =
863 3400 : std::numeric_limits<uint64_t>::max() - offset;
864 :
865 10200 : THEN(" the computed block count corresponds to the number "
866 3400 : "of blocks involved in the operation ") {
867 3400 : const std::size_t n =
868 3400 : block_count(offset, size, block_size);
869 6800 : const std::size_t expected_n =
870 3400 : (offset + size) / block_size -
871 6800 : offset / block_size +
872 3400 : ((offset + size) % block_size ? 1u : 0);
873 :
874 6800 : REQUIRE(n == expected_n);
875 : }
876 : }
877 : }
878 :
879 4107438 : AND_WHEN(" offset == 2^63 ") {
880 :
881 6834 : const uint64_t offset =
882 : std::numeric_limits<uint64_t>::max() / 2 + 1;
883 :
884 20519 : AND_WHEN(" offset + size == block_size ") {
885 :
886 17 : const size_t size = 0;
887 :
888 34 : CAPTURE(offset, size, block_size);
889 :
890 68 : THEN(" the computed block count == 1 ") {
891 17 : const std::size_t n =
892 17 : block_count(offset, size, block_size);
893 17 : const std::size_t expected_n = 0;
894 34 : REQUIRE(n == expected_n);
895 : }
896 : }
897 :
898 23902 : AND_WHEN(" offset + size == M * block_size ") {
899 3434 : const size_t m = GENERATE(range(0u, test_reps));
900 3400 : const size_t size = m * block_size;
901 :
902 6800 : CAPTURE(offset, size, block_size);
903 :
904 13600 : THEN(" the computed block count == M ") {
905 3400 : const std::size_t n =
906 3400 : block_count(offset, size, block_size);
907 3400 : const std::size_t expected_n = m;
908 6800 : REQUIRE(n == expected_n);
909 : }
910 : }
911 :
912 23902 : AND_WHEN(" offset + size < 2^64 - 1") {
913 :
914 3434 : const size_t size = GENERATE_COPY(
915 : take(test_reps,
916 : random(std::size_t{1},
917 : std::numeric_limits<uint64_t>::max() -
918 : offset)));
919 :
920 10200 : THEN(" the computed block count corresponds to the number "
921 3400 : "of blocks involved in the operation ") {
922 3400 : const std::size_t n =
923 3400 : block_count(offset, size, block_size);
924 6800 : const std::size_t expected_n =
925 3400 : (offset + size) / block_size -
926 6800 : offset / block_size +
927 3400 : ((offset + size) % block_size ? 1u : 0);
928 :
929 6800 : REQUIRE(n == expected_n);
930 : }
931 : }
932 :
933 20519 : AND_WHEN(" offset + size == 2^64 - 1") {
934 :
935 17 : const size_t size =
936 : std::numeric_limits<uint64_t>::max() - offset;
937 :
938 51 : THEN(" the computed block count corresponds to the number "
939 17 : "of blocks involved in the operation ") {
940 17 : const std::size_t n =
941 17 : block_count(offset, size, block_size);
942 34 : const std::size_t expected_n =
943 17 : (offset + size) / block_size -
944 34 : offset / block_size +
945 17 : ((offset + size) % block_size ? 1u : 0);
946 :
947 34 : REQUIRE(n == expected_n);
948 : }
949 : }
950 : }
951 :
952 4100638 : AND_WHEN(" offset == 2^64 - 1 ") {
953 :
954 34 : const uint64_t offset = std::numeric_limits<uint64_t>::max();
955 :
956 119 : AND_WHEN(" offset + size == offset ") {
957 :
958 17 : const size_t size = 0;
959 :
960 34 : CAPTURE(offset, size, block_size);
961 :
962 68 : THEN(" the computed block count == 1 ") {
963 17 : const std::size_t n =
964 17 : block_count(offset, size, block_size);
965 17 : const std::size_t expected_n = 0;
966 34 : REQUIRE(n == expected_n);
967 : }
968 : }
969 :
970 102 : AND_WHEN(" offset + size == 2^64 ") {
971 : // TODO: here we should check that we actually hit an
972 : // assert(), but Catch2 does not have facilities to
973 : // support this yet
974 : }
975 : }
976 : }
977 : }
978 2750770 : }
|