Integer overflows in partition_right_branchless

[asl]

Looks like there are multiple possible integer overflows in partition_right_branchless.

The first kind of overflow happens on the case when the sequence is already correctly partitioned. In this case first >= last and therefore there is an overflow in the loop condition: while (last - first > 2 * block_size) { This could be fixed by this tiny patch (I have not changed the indentation to show the idea):

--- a/pdqsort.h
+++ b/pdqsort.h
@@ -224,7 +224,6 @@ namespace pdqsort_detail {
         if (!already_partitioned) {
             std::iter_swap(first, last);
             ++first;
-        }

         // The following branchless partitioning is derived from "BlockQuicksort: How Branch
         // Mispredictions don’t affect Quicksort" by Stefan Edelkamp and Armin Weiss.
@@ -325,6 +324,7 @@ namespace pdqsort_detail {
             while (num_r--) std::iter_swap(last - offsets_r[num_r], first), ++first;
             last = first;
         }
+        }

         // Put the pivot in the right place.
         Iter pivot_pos = first - 1;

However, the use of int variables there is also a bit suspicious. I have not checked all possible code paths to ensure that they cannot overflow in some cases though

[orlp]

Ugh, if the enums type is unsigned (which the compiler is allowed to do) this is a legitimate issue. I'll have to fix this. I am absolutely neck deep in work at the moment though, so it might take a couple weeks until I find a slot I can really sit down and get this right.

My preferred fix would be to not change the structure of the code, but to fix the comparisons themselves.

Thanks for the report.

[asl]

Right. And I do have a real code that exhibits the problem just using the Apple-provided clang on Darwin, I have not checked what happened with integer promotion here, but the condition definitely evaluated to true :)

[orlp]

Oh that's more serious than I thought then. Just for sanity's sake (and that there isn't another issue), could you check that the enum values with that compiler are unsigned in pdqsort's code? I don't have access to an Apple machine.

I will try to give this more priority.

[orlp]

Out of sight, out of mind...

My holiday is almost over and now I remember this issue is still open. I will fix this this week, sorry for the delay.

[past-due]

@orlp: Just pinging to see if you'd had a chance to look into this yet.

Thanks for the fantastic project!

[orlp]

@past-due Crap... I'm fixing this today before I forget again.

[orlp]

Fixed with https://github.com/orlp/pdqsort/commit/2dc2bbdcb7a090e28a626c178ea1b31a51ca0485.