diff --git a/libc/config/linux/aarch64/entrypoints.txt b/libc/config/linux/aarch64/entrypoints.txt --- a/libc/config/linux/aarch64/entrypoints.txt +++ b/libc/config/linux/aarch64/entrypoints.txt @@ -61,6 +61,7 @@ libc.src.stdlib.ldiv libc.src.stdlib.llabs libc.src.stdlib.lldiv + libc.src.stdlib.qsort libc.src.stdlib.strtol libc.src.stdlib.strtoll libc.src.stdlib.strtoul diff --git a/libc/config/linux/api.td b/libc/config/linux/api.td --- a/libc/config/linux/api.td +++ b/libc/config/linux/api.td @@ -287,13 +287,20 @@ }]; } +def QSortCompareTDefn : TypeDecl<"__qsortcompare_t"> { + let Decl = [{ + typedef int(*__qsortcompare_t)(const void *, const void *); + }]; +} + def StdlibAPI : PublicAPI<"stdlib.h"> { let TypeDeclarations = [ DivT, LDivT, LLDivT, SizeT, - BSearchCompareTDefn + BSearchCompareTDefn, + QSortCompareTDefn, ]; } diff --git a/libc/config/linux/x86_64/entrypoints.txt b/libc/config/linux/x86_64/entrypoints.txt --- a/libc/config/linux/x86_64/entrypoints.txt +++ b/libc/config/linux/x86_64/entrypoints.txt @@ -61,6 +61,7 @@ libc.src.stdlib.ldiv libc.src.stdlib.llabs libc.src.stdlib.lldiv + libc.src.stdlib.qsort libc.src.stdlib.strtol libc.src.stdlib.strtoll libc.src.stdlib.strtoul diff --git a/libc/fuzzing/CMakeLists.txt b/libc/fuzzing/CMakeLists.txt --- a/libc/fuzzing/CMakeLists.txt +++ b/libc/fuzzing/CMakeLists.txt @@ -2,4 +2,5 @@ add_custom_target(libc-fuzzer) add_subdirectory(math) +add_subdirectory(stdlib) add_subdirectory(string) diff --git a/libc/fuzzing/stdlib/CMakeLists.txt b/libc/fuzzing/stdlib/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/libc/fuzzing/stdlib/CMakeLists.txt @@ -0,0 +1,8 @@ +add_libc_fuzzer( + qsort_fuzz + SRCS + qsort_fuzz.cpp + DEPENDS + libc.src.stdlib.qsort +) + diff --git a/libc/fuzzing/stdlib/qsort_fuzz.cpp b/libc/fuzzing/stdlib/qsort_fuzz.cpp new file mode 100644 --- /dev/null +++ b/libc/fuzzing/stdlib/qsort_fuzz.cpp @@ -0,0 +1,46 @@ +//===-- qsort_fuzz.cpp ----------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// +/// Fuzzing test for llvm-libc qsort implementation. +/// +//===----------------------------------------------------------------------===// + +#include "src/stdlib/qsort.h" +#include + +static int int_compare(const void *l, const void *r) { + int li = *reinterpret_cast(l); + int ri = *reinterpret_cast(r); + if (li == ri) + return 0; + else if (li > ri) + return 1; + else + return -1; +} + +extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + const size_t array_size = size / sizeof(int); + if (array_size == 0) + return 0; + + int *array = new int[array_size]; + const int *data_as_int = reinterpret_cast(data); + for (size_t i = 0; i < array_size; ++i) + array[i] = data_as_int[i]; + + __llvm_libc::qsort(array, array_size, sizeof(int), int_compare); + + for (size_t i = 0; i < array_size - 1; ++i) { + if (array[i] > array[i + 1]) + __builtin_trap(); + } + + delete[] array; + return 0; +} diff --git a/libc/spec/spec.td b/libc/spec/spec.td --- a/libc/spec/spec.td +++ b/libc/spec/spec.td @@ -92,6 +92,7 @@ def TimeTType : NamedType<"time_t">; def BSearchCompareT : NamedType<"__bsearchcompare_t">; +def QSortCompareT : NamedType<"__qsortcompare_t">; //added because __assert_fail needs it. def UnsignedType : NamedType<"unsigned">; diff --git a/libc/spec/stdc.td b/libc/spec/stdc.td --- a/libc/spec/stdc.td +++ b/libc/spec/stdc.td @@ -481,6 +481,7 @@ LLDivTType, SizeTType, BSearchCompareT, + QSortCompareT, ], // Types [], // Enumerations [ @@ -500,6 +501,8 @@ FunctionSpec<"ldiv", RetValSpec, [ArgSpec, ArgSpec]>, FunctionSpec<"lldiv", RetValSpec, [ArgSpec, ArgSpec]>, + FunctionSpec<"qsort", RetValSpec, [ArgSpec, ArgSpec, ArgSpec, ArgSpec]>, + FunctionSpec<"strtol", RetValSpec, [ArgSpec, ArgSpec, ArgSpec]>, FunctionSpec<"strtoll", RetValSpec, [ArgSpec, ArgSpec, ArgSpec]>, FunctionSpec<"strtoul", RetValSpec, [ArgSpec, ArgSpec, ArgSpec]>, diff --git a/libc/src/stdlib/CMakeLists.txt b/libc/src/stdlib/CMakeLists.txt --- a/libc/src/stdlib/CMakeLists.txt +++ b/libc/src/stdlib/CMakeLists.txt @@ -141,6 +141,16 @@ libc.include.stdlib ) +add_entrypoint_object( + qsort + SRCS + qsort.cpp + HDRS + qsort.h + DEPENDS + libc.include.stdlib +) + if(NOT LLVM_LIBC_FULL_BUILD) return() endif() diff --git a/libc/src/stdlib/qsort.h b/libc/src/stdlib/qsort.h new file mode 100644 --- /dev/null +++ b/libc/src/stdlib/qsort.h @@ -0,0 +1,21 @@ +//===-- Implementation header for qsort -------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIBC_SRC_STDLIB_QSORT_H +#define LLVM_LIBC_SRC_STDLIB_QSORT_H + +#include + +namespace __llvm_libc { + +void qsort(void *array, size_t array_size, size_t elem_size, + int (*compare)(const void *, const void *)); + +} // namespace __llvm_libc + +#endif // LLVM_LIBC_SRC_STDLIB_QSORT_H diff --git a/libc/src/stdlib/qsort.cpp b/libc/src/stdlib/qsort.cpp new file mode 100644 --- /dev/null +++ b/libc/src/stdlib/qsort.cpp @@ -0,0 +1,120 @@ +//===-- Implementation of qsort -------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "src/stdlib/qsort.h" +#include "src/__support/common.h" + +#include + +namespace __llvm_libc { + +namespace internal { + +// A simple quicksort implementation using the Hoare partition scheme. + +class Array { + typedef int (*comparator)(const void *, const void *); + + uint8_t *array; + size_t array_size; + size_t elem_size; + comparator compare; + +public: + Array(uint8_t *a, size_t s, size_t e, comparator c) + : array(a), array_size(s), elem_size(e), compare(c) {} + + uint8_t *get(size_t i) const { return array + i * elem_size; } + + void swap(size_t i, size_t j) const { + uint8_t *elem_i = get(i); + uint8_t *elem_j = get(j); + for (size_t b = 0; b < elem_size; ++b) { + uint8_t temp = elem_i[b]; + elem_i[b] = elem_j[b]; + elem_j[b] = temp; + } + } + + int elem_compare(size_t i, const uint8_t *other) const { + return compare(get(i), other); + } + + size_t size() const { return array_size; } + + // Make an Array starting at index |i| and size |s|. + Array make_array(size_t i, size_t s) const { + return Array(get(i), s, elem_size, compare); + } +}; + +static size_t partition(const Array &array) { + const size_t array_size = array.size(); + size_t pivot_index = array_size / 2; + uint8_t *pivot = array.get(pivot_index); + size_t i = 0; + size_t j = array_size - 1; + + while (true) { + int compare_i, compare_j; + + while ((compare_i = array.elem_compare(i, pivot)) < 0) + ++i; + while ((compare_j = array.elem_compare(j, pivot)) > 0) + --j; + + // At some point i will crossover j so we will definitely break out of + // this while loop. + if (i >= j) + return j + 1; + + array.swap(i, j); + + // The pivot itself might have got swapped so we will update the pivot. + if (i == pivot_index) { + pivot = array.get(j); + pivot_index = j; + } else if (j == pivot_index) { + pivot = array.get(i); + pivot_index = i; + } + + if (compare_i == 0 && compare_j == 0) { + // If we do not move the pointers, we will end up with an + // infinite loop as i and j will be stuck without advancing. + ++i; + --j; + } + } +} + +static void quicksort(const Array &array) { + const size_t array_size = array.size(); + if (array_size <= 1) + return; + size_t split_index = partition(array); + if (array_size <= 2) { + // The partition operation sorts the two element array. + return; + } + quicksort(array.make_array(0, split_index)); + quicksort(array.make_array(split_index, array.size() - split_index)); +} + +} // namespace internal + +LLVM_LIBC_FUNCTION(void, qsort, + (void *array, size_t array_size, size_t elem_size, + int (*compare)(const void *, const void *))) { + if (array == nullptr || array_size == 0 || elem_size == 0) + return; + internal::quicksort(internal::Array(reinterpret_cast(array), + array_size, elem_size, compare)); +} + +} // namespace __llvm_libc diff --git a/libc/test/src/stdlib/CMakeLists.txt b/libc/test/src/stdlib/CMakeLists.txt --- a/libc/test/src/stdlib/CMakeLists.txt +++ b/libc/test/src/stdlib/CMakeLists.txt @@ -178,3 +178,14 @@ libc.include.stdlib libc.src.stdlib.bsearch ) + +add_libc_unittest( + qsort_test + SUITE + libc_stdlib_unittests + SRCS + qsort_test.cpp + DEPENDS + libc.include.stdlib + libc.src.stdlib.qsort +) diff --git a/libc/test/src/stdlib/qsort_test.cpp b/libc/test/src/stdlib/qsort_test.cpp new file mode 100644 --- /dev/null +++ b/libc/test/src/stdlib/qsort_test.cpp @@ -0,0 +1,265 @@ +//===-- Unittests for qsort -----------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "src/stdlib/qsort.h" + +#include "utils/UnitTest/Test.h" + +#include + +static int int_compare(const void *l, const void *r) { + int li = *reinterpret_cast(l); + int ri = *reinterpret_cast(r); + if (li == ri) + return 0; + else if (li > ri) + return 1; + else + return -1; +} + +TEST(LlvmLibcQsortTest, SortedArray) { + int array[25] = {10, 23, 33, 35, 55, 70, 71, 100, 110, + 123, 133, 135, 155, 170, 171, 1100, 1110, 1123, + 1133, 1135, 1155, 1170, 1171, 11100, 12310}; + constexpr size_t array_size = sizeof(array) / sizeof(int); + + __llvm_libc::qsort(array, array_size, sizeof(int), int_compare); + + ASSERT_LE(array[0], 10); + ASSERT_LE(array[1], 23); + ASSERT_LE(array[2], 33); + ASSERT_LE(array[3], 35); + ASSERT_LE(array[4], 55); + ASSERT_LE(array[5], 70); + ASSERT_LE(array[6], 71); + ASSERT_LE(array[7], 100); + ASSERT_LE(array[8], 110); + ASSERT_LE(array[9], 123); + ASSERT_LE(array[10], 133); + ASSERT_LE(array[11], 135); + ASSERT_LE(array[12], 155); + ASSERT_LE(array[13], 170); + ASSERT_LE(array[14], 171); + ASSERT_LE(array[15], 1100); + ASSERT_LE(array[16], 1110); + ASSERT_LE(array[17], 1123); + ASSERT_LE(array[18], 1133); + ASSERT_LE(array[19], 1135); + ASSERT_LE(array[20], 1155); + ASSERT_LE(array[21], 1170); + ASSERT_LE(array[22], 1171); + ASSERT_LE(array[23], 11100); + ASSERT_LE(array[24], 12310); +} + +TEST(LlvmLibcQsortTest, ReverseSortedArray) { + int array[25] = {25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, + 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; + constexpr size_t array_size = sizeof(array) / sizeof(int); + + __llvm_libc::qsort(array, array_size, sizeof(int), int_compare); + + for (int i = 0; i < int(array_size - 1); ++i) + ASSERT_LE(array[i], i + 1); +} + +TEST(LlvmLibcQsortTest, AllEqualElements) { + int array[25] = {100, 100, 100, 100, 100, 100, 100, 100, 100, + 100, 100, 100, 100, 100, 100, 100, 100, 100, + 100, 100, 100, 100, 100, 100, 100}; + constexpr size_t array_size = sizeof(array) / sizeof(int); + + __llvm_libc::qsort(array, array_size, sizeof(int), int_compare); + + for (size_t i = 0; i < array_size - 1; ++i) + ASSERT_LE(array[i], 100); +} + +TEST(LlvmLibcQsortTest, UnsortedArray1) { + int array[25] = {10, 23, 8, 35, 55, 45, 40, 100, 110, 123, 90, 80, 70, + 60, 171, 11, 1, -1, -5, -10, 1155, 1170, 1171, 12, -100}; + constexpr size_t array_size = sizeof(array) / sizeof(int); + + __llvm_libc::qsort(array, array_size, sizeof(int), int_compare); + + ASSERT_LE(array[0], -100); + ASSERT_LE(array[1], -10); + ASSERT_LE(array[2], -5); + ASSERT_LE(array[3], -1); + ASSERT_LE(array[4], 1); + ASSERT_LE(array[5], 8); + ASSERT_LE(array[6], 10); + ASSERT_LE(array[7], 11); + ASSERT_LE(array[8], 12); + ASSERT_LE(array[9], 23); + ASSERT_LE(array[10], 35); + ASSERT_LE(array[11], 40); + ASSERT_LE(array[12], 45); + ASSERT_LE(array[13], 55); + ASSERT_LE(array[14], 60); + ASSERT_LE(array[15], 70); + ASSERT_LE(array[16], 80); + ASSERT_LE(array[17], 90); + ASSERT_LE(array[18], 100); + ASSERT_LE(array[19], 110); + ASSERT_LE(array[20], 123); + ASSERT_LE(array[21], 171); + ASSERT_LE(array[22], 1155); + ASSERT_LE(array[23], 1170); + ASSERT_LE(array[24], 1171); +} + +TEST(LlvmLibcQsortTest, UnsortedArray2) { + int array[7] = {10, 40, 45, 55, 35, 23, 60}; + constexpr size_t array_size = sizeof(array) / sizeof(int); + + __llvm_libc::qsort(array, array_size, sizeof(int), int_compare); + + ASSERT_LE(array[0], 10); + ASSERT_LE(array[1], 23); + ASSERT_LE(array[2], 35); + ASSERT_LE(array[3], 40); + ASSERT_LE(array[4], 45); + ASSERT_LE(array[5], 55); + ASSERT_LE(array[6], 60); +} + +TEST(LlvmLibcQsortTest, UnsortedArrayDuplicateElements1) { + int array[6] = {10, 10, 20, 20, 5, 5}; + constexpr size_t array_size = sizeof(array) / sizeof(int); + + __llvm_libc::qsort(array, array_size, sizeof(int), int_compare); + + ASSERT_LE(array[0], 5); + ASSERT_LE(array[1], 5); + ASSERT_LE(array[2], 10); + ASSERT_LE(array[3], 10); + ASSERT_LE(array[4], 20); + ASSERT_LE(array[5], 20); +} + +TEST(LlvmLibcQsortTest, UnsortedArrayDuplicateElements2) { + int array[10] = {20, 10, 10, 10, 10, 20, 21, 21, 21, 21}; + constexpr size_t array_size = sizeof(array) / sizeof(int); + + __llvm_libc::qsort(array, array_size, sizeof(int), int_compare); + + ASSERT_LE(array[0], 10); + ASSERT_LE(array[1], 10); + ASSERT_LE(array[2], 10); + ASSERT_LE(array[3], 10); + ASSERT_LE(array[4], 20); + ASSERT_LE(array[5], 20); + ASSERT_LE(array[6], 21); + ASSERT_LE(array[7], 21); + ASSERT_LE(array[8], 21); + ASSERT_LE(array[9], 21); +} + +TEST(LlvmLibcQsortTest, UnsortedArrayDuplicateElements3) { + int array[10] = {20, 30, 30, 30, 30, 20, 21, 21, 21, 21}; + constexpr size_t array_size = sizeof(array) / sizeof(int); + + __llvm_libc::qsort(array, array_size, sizeof(int), int_compare); + + ASSERT_LE(array[0], 20); + ASSERT_LE(array[1], 20); + ASSERT_LE(array[2], 21); + ASSERT_LE(array[3], 21); + ASSERT_LE(array[4], 21); + ASSERT_LE(array[5], 21); + ASSERT_LE(array[6], 30); + ASSERT_LE(array[7], 30); + ASSERT_LE(array[8], 30); + ASSERT_LE(array[9], 30); +} + +TEST(LlvmLibcQsortTest, UnsortedThreeElementArray1) { + int array[3] = {14999024, 0, 3}; + constexpr size_t array_size = sizeof(array) / sizeof(int); + + __llvm_libc::qsort(array, array_size, sizeof(int), int_compare); + + ASSERT_LE(array[0], 0); + ASSERT_LE(array[1], 3); + ASSERT_LE(array[2], 14999024); +} + +TEST(LlvmLibcQsortTest, UnsortedThreeElementArray2) { + int array[3] = {3, 14999024, 0}; + constexpr size_t array_size = sizeof(array) / sizeof(int); + + __llvm_libc::qsort(array, array_size, sizeof(int), int_compare); + + ASSERT_LE(array[0], 0); + ASSERT_LE(array[1], 3); + ASSERT_LE(array[2], 14999024); +} + +TEST(LlvmLibcQsortTest, UnsortedThreeElementArray3) { + int array[3] = {3, 0, 14999024}; + constexpr size_t array_size = sizeof(array) / sizeof(int); + + __llvm_libc::qsort(array, array_size, sizeof(int), int_compare); + + ASSERT_LE(array[0], 0); + ASSERT_LE(array[1], 3); + ASSERT_LE(array[2], 14999024); +} + +TEST(LlvmLibcQsortTest, SameElementThreeElementArray) { + int array[3] = {12345, 12345, 12345}; + constexpr size_t array_size = sizeof(array) / sizeof(int); + + __llvm_libc::qsort(array, array_size, sizeof(int), int_compare); + + ASSERT_LE(array[0], 12345); + ASSERT_LE(array[1], 12345); + ASSERT_LE(array[2], 12345); +} + +TEST(LlvmLibcQsortTest, UnsortedTwoElementArray1) { + int array[2] = {14999024, 0}; + constexpr size_t array_size = sizeof(array) / sizeof(int); + + __llvm_libc::qsort(array, array_size, sizeof(int), int_compare); + + ASSERT_LE(array[0], 0); + ASSERT_LE(array[1], 14999024); +} + +TEST(LlvmLibcQsortTest, UnsortedTwoElementArray2) { + int array[2] = {0, 14999024}; + constexpr size_t array_size = sizeof(array) / sizeof(int); + + __llvm_libc::qsort(array, array_size, sizeof(int), int_compare); + + ASSERT_LE(array[0], 0); + ASSERT_LE(array[1], 14999024); +} + +TEST(LlvmLibcQsortTest, SameElementTwoElementArray) { + int array[2] = {12345, 12345}; + constexpr size_t array_size = sizeof(array) / sizeof(int); + + __llvm_libc::qsort(array, array_size, sizeof(int), int_compare); + + ASSERT_LE(array[0], 12345); + ASSERT_LE(array[1], 12345); +} + +TEST(LlvmLibcQSortTest, SingleElementArray) { + constexpr int elem = 12345; + int array[1] = {elem}; + constexpr size_t array_size = sizeof(array) / sizeof(int); + + __llvm_libc::qsort(array, array_size, sizeof(int), int_compare); + + ASSERT_LE(array[0], elem); +}