Commit Graph

6 Commits

Author SHA1 Message Date
Mathias Agopian
420f06bef3 implement 16 and 8 bits clz, ctz and popcount
This is needed for utils::bitset8 and bitset16.
2024-04-26 14:13:48 -07:00
Mathias Agopian
718e7ab064 remove a bunch of <functional> includes
This forces us to use an explicit hash class in a few place, but it
is cleaner.

remove utils::lower_bound and utils::upper_bound, which were not used.
2022-06-03 08:35:57 -07:00
Pixelflinger
8fb65a19b4 fix utils::ctz() when builtins are not available
Our fallback 64-bits ctz() was completely wrong. 
The unit tests were wrong too.
2020-03-10 15:41:43 -07:00
Philip Rideout
87a05f057a Fix out-of-bounds in an [unused] utility.
This was caught by ASAN.

Our algorithm header has many one-liners that compute the "next power of
two length / 2" but they all have the caveat that if the input is
already POT, then the "/ 2" part does not occur.

Usually we deal with this by testing the difference against zero.
However in `partition_point` we were skipping the test, thus causing a
potential out-of-bounds access.

I fixed `partition_point` and added a few more tests for non-POT cases.
2019-11-05 17:14:15 -08:00
Mathias Agopian
5ed80bc616 Add ctz to utils::algorithm
Use CTZ in bitset.forEachBitSet() so we can
efficiently go through them in order instead of
reverse order.
2018-08-17 19:48:23 -07:00
Romain Guy
b3d758f3b3 Initial commit 2018-08-03 10:38:22 -07:00