Skip to content

Commit 6c0d83f

Browse files
Dricmoyclaude
andcommitted
apacheGH-51222: [C++] Avoid overflow in binary_slice with extreme step and bounds
Co-Authored-By: Claude Opus 5.5 <[email protected]>
1 parent 4b75d50 commit 6c0d83f

2 files changed

Lines changed: 76 additions & 18 deletions

File tree

‎cpp/src/arrow/compute/kernels/scalar_string_ascii.cc‎

Lines changed: 48 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -2640,12 +2640,36 @@ struct SliceBytesTransform : StringSliceTransformBase {
26402640
// on the resulting slice lengths, so return a worst case estimate.
26412641
return input_bytes;
26422642
}
2643-
// SliceOptions uses INT64_MIN/MAX for open-ended bounds. Clamp both bounds
2644-
// before arithmetic so equivalent out-of-range indices cannot overflow the size estimate.
2645-
const int64_t start = std::clamp(opt.start, -input_bytes, input_bytes);
2646-
const int64_t stop = std::clamp(opt.stop, -input_bytes, input_bytes);
2647-
int64_t max_slice_bytes = (stop - start + opt.step - 1) / opt.step;
2648-
return std::min(input_bytes, ninputs * std::max<int64_t>(0, max_slice_bytes));
2643+
const int64_t max_slice_bytes = MaxSliceBytes(opt, input_bytes);
2644+
// The output is never larger than the input; avoid overflowing the product
2645+
if (max_slice_bytes > 0 && ninputs > input_bytes / max_slice_bytes) {
2646+
return input_bytes;
2647+
}
2648+
return std::min(input_bytes, ninputs * max_slice_bytes);
2649+
}
2650+
2651+
// Upper bound on the output size for one string of at most `max_string_bytes`
2652+
// bytes, when start and stop have the same sign.
2653+
static int64_t MaxSliceBytes(const SliceOptions& opt, int64_t max_string_bytes) {
2654+
// start and stop may be INT64_MIN/INT64_MAX (e.g. the default stop). Indices
2655+
// past either end select the same bytes as the end itself, where
2656+
// -max_string_bytes - 1 is "before the first byte" when slicing backward.
2657+
const int64_t lower = -max_string_bytes - 1;
2658+
const int64_t start = std::clamp(opt.start, lower, max_string_bytes);
2659+
const int64_t stop = std::clamp(opt.stop, lower, max_string_bytes);
2660+
return NumSelectedBytes(opt.step > 0 ? stop - start : start - stop, opt.step);
2661+
}
2662+
2663+
// ceil(span / |step|), without overflow for any non-zero step
2664+
static int64_t NumSelectedBytes(int64_t span, int64_t step) {
2665+
if (span <= 0) {
2666+
return 0;
2667+
}
2668+
if (step >= span || step <= -span) {
2669+
return 1;
2670+
}
2671+
// |step| < span, so negating step cannot overflow
2672+
return (span - 1) / (step > 0 ? step : -step) + 1;
26492673
}
26502674

26512675
int64_t Transform(const uint8_t* input, int64_t input_string_bytes, uint8_t* output) {
@@ -2728,11 +2752,14 @@ struct SliceBytesTransform : StringSliceTransformBase {
27282752
uint8_t* dest = output;
27292753
const uint8_t* i = begin_sliced;
27302754

2731-
while (i < end_sliced) {
2732-
*dest = *i;
2755+
while (true) {
2756+
*dest++ = *i;
2757+
// Don't step past end_sliced, a large step would overflow the pointer
2758+
if (opt.step >= end_sliced - i) {
2759+
break;
2760+
}
27332761
// skip step codeunits
27342762
i += opt.step;
2735-
dest++;
27362763
}
27372764
return dest - output;
27382765
}
@@ -2747,7 +2774,8 @@ struct SliceBytesTransform : StringSliceTransformBase {
27472774

27482775
if (opt.start >= 0) {
27492776
// +1 because begin_sliced acts as as the end of a reverse iterator
2750-
begin_sliced = std::min(begin + opt.start + 1, end);
2777+
// (clamp first so that INT64_MAX doesn't overflow)
2778+
begin_sliced = std::min(opt.start, end - 1) + 1;
27512779
} else {
27522780
// -1 because start=-1 means the last byte, which is 0 advances
27532781
begin_sliced = std::max(end + opt.start + 1, begin);
@@ -2756,7 +2784,8 @@ struct SliceBytesTransform : StringSliceTransformBase {
27562784

27572785
// similar to opt.start
27582786
if (opt.stop >= 0) {
2759-
end_sliced = std::min(begin + opt.stop + 1, end);
2787+
// clamp first so that INT64_MAX doesn't overflow
2788+
end_sliced = std::min(opt.stop, end - 1) + 1;
27602789
} else {
27612790
end_sliced = std::max(end + opt.stop + 1, begin);
27622791
}
@@ -2787,12 +2816,15 @@ struct SliceBytesTransform : StringSliceTransformBase {
27872816
// Copy computed slice to output
27882817
uint8_t* dest = output;
27892818
const uint8_t* i = begin_sliced;
2790-
while (i > end_sliced) {
2819+
while (true) {
27912820
// write a single codepoint
2792-
*dest = *i;
2821+
*dest++ = *i;
2822+
// Don't step past end_sliced, a large step would overflow the pointer
2823+
if (opt.step <= end_sliced - i) {
2824+
break;
2825+
}
27932826
// and skip the remainder
27942827
i += opt.step;
2795-
dest++;
27962828
}
27972829

27982830
return dest - output;
@@ -2806,11 +2838,11 @@ struct SliceBytesTransform : StringSliceTransformBase {
28062838
if (step > 0) {
28072839
// forward slice
28082840
auto [begin_index, end_index] = SliceForwardRange(options, input_width_32);
2809-
return static_cast<int32_t>((end_index - begin_index + step - 1) / step);
2841+
return static_cast<int32_t>(NumSelectedBytes(end_index - begin_index, step));
28102842
} else {
28112843
// backward slice
28122844
auto [begin_index, end_index] = SliceBackwardRange(options, input_width_32);
2813-
return static_cast<int32_t>((end_index - begin_index + step + 1) / step);
2845+
return static_cast<int32_t>(NumSelectedBytes(begin_index - end_index, step));
28142846
}
28152847
}
28162848
};

‎cpp/src/arrow/compute/kernels/scalar_string_test.cc‎

Lines changed: 28 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -858,6 +858,15 @@ TEST_F(TestFixedSizeBinaryKernels, BinarySlicePosPos) {
858858
SliceOptions options_step_neg{5, 0, -2};
859859
CheckUnary("binary_slice", R"(["abcdef", "foobaz"])", fixed_size_binary(3),
860860
R"(["fdb", "zbo"])", &options_step_neg);
861+
862+
constexpr auto min = std::numeric_limits<int64_t>::min();
863+
constexpr auto max = std::numeric_limits<int64_t>::max();
864+
SliceOptions options_max_step{1, max, max};
865+
CheckUnary("binary_slice", R"(["abcdef", "foobaz"])", fixed_size_binary(1),
866+
R"(["b", "o"])", &options_max_step);
867+
SliceOptions options_min_step{max, 0, min};
868+
CheckUnary("binary_slice", R"(["abcdef", "foobaz"])", fixed_size_binary(1),
869+
R"(["f", "z"])", &options_min_step);
861870
}
862871

863872
TEST_F(TestFixedSizeBinaryKernels, BinarySlicePosNeg) {
@@ -2714,6 +2723,15 @@ TYPED_TEST(TestBinaryKernels, SliceBytesPosPos) {
27142723
this->template MakeArray<std::string>({"abcdef", long_input}),
27152724
this->template MakeArray<std::string>({"b", std::string(60, 'x')}),
27162725
&options_default_stop_step);
2726+
SliceOptions options_max_step{/*start=*/1, /*stop=*/max, /*step=*/max};
2727+
this->CheckUnary("binary_slice", this->MakeArray({"", "a", "abc"}),
2728+
this->MakeArray({"", "", "b"}), &options_max_step);
2729+
SliceOptions options_max_start_neg{/*start=*/max, /*stop=*/0, /*step=*/-1};
2730+
this->CheckUnary("binary_slice", this->MakeArray({"", "a", "abcdef"}),
2731+
this->MakeArray({"", "", "fedcb"}), &options_max_start_neg);
2732+
options_max_start_neg.step = std::numeric_limits<int64_t>::min();
2733+
this->CheckUnary("binary_slice", this->MakeArray({"", "a", "abcdef"}),
2734+
this->MakeArray({"", "", "f"}), &options_max_start_neg);
27172735

27182736
SliceOptions options{2, 4};
27192737
this->CheckUnary(
@@ -2765,8 +2783,7 @@ TYPED_TEST(TestBinaryKernels, SliceBytesNegNeg) {
27652783
const std::string long_input(300, 'x');
27662784
SliceOptions options_extreme_start{/*start=*/min, /*stop=*/-1};
27672785
this->CheckUnary("binary_slice", this->template MakeArray<std::string>({"x"}),
2768-
this->template MakeArray<std::string>({""}),
2769-
&options_extreme_start);
2786+
this->template MakeArray<std::string>({""}), &options_extreme_start);
27702787

27712788
SliceOptions options_min{/*start=*/-1, /*stop=*/min};
27722789
this->CheckUnary("binary_slice",
@@ -2777,6 +2794,9 @@ TYPED_TEST(TestBinaryKernels, SliceBytesNegNeg) {
27772794
this->template MakeArray<std::string>({"abcdef", long_input}),
27782795
this->template MakeArray<std::string>({"fa", std::string(60, 'x')}),
27792796
&options_min_step_neg);
2797+
SliceOptions options_reverse{/*start=*/-1, /*stop=*/min, /*step=*/-1};
2798+
this->CheckUnary("binary_slice", this->MakeArray({"abcdef"}),
2799+
this->MakeArray({"fedcba"}), &options_reverse);
27802800

27812801
SliceOptions options{-2, -1};
27822802
this->CheckUnary(
@@ -2801,6 +2821,12 @@ TYPED_TEST(TestBinaryKernels, SliceBytesNegNeg) {
28012821
}
28022822

28032823
TYPED_TEST(TestBinaryKernels, SliceBytesNegPos) {
2824+
SliceOptions options_max_stop_neg{/*start=*/-1,
2825+
/*stop=*/std::numeric_limits<int64_t>::max(),
2826+
/*step=*/-1};
2827+
this->CheckUnary("binary_slice", this->MakeArray({"", "a", "abcdef"}),
2828+
this->MakeArray({"", "", ""}), &options_max_stop_neg);
2829+
28042830
SliceOptions options{-2, 4};
28052831
this->CheckUnary(
28062832
"binary_slice",

0 commit comments

Comments
 (0)