Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings

[wip][libc] Implemented fixed point divifx functions in llvm-libc #138238

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Draft
wants to merge 4 commits into
base: main
Choose a base branch
Loading
from

Conversation

kr-2003
Copy link
Contributor

@kr-2003 kr-2003 commented May 2, 2025

Currently work in progress

Fixing #129124

@kr-2003 kr-2003 marked this pull request as draft May 2, 2025 08:00
@llvmbot llvmbot added the libc label May 2, 2025
@llvmbot
Copy link
Member

llvmbot commented May 2, 2025

@llvm/pr-subscribers-libc

Author: Abhinav Kumar (kr-2003)

Changes

Currently work in progress

Fixing #129124


Full diff: https://github.com/llvm/llvm-project/pull/138238.diff

9 Files Affected:

  • (modified) libc/config/darwin/arm/entrypoints.txt (+1)
  • (modified) libc/include/stdfix.yaml (+8)
  • (added) libc/src/__support/fixed_point/divifx.h (+132)
  • (modified) libc/src/stdfix/CMakeLists.txt (+14)
  • (added) libc/src/stdfix/divir.cpp (+13)
  • (added) libc/src/stdfix/divir.h (+21)
  • (modified) libc/test/src/stdfix/CMakeLists.txt (+17)
  • (added) libc/test/src/stdfix/DiviFxTest.h (+40)
  • (added) libc/test/src/stdfix/divir_test.cpp (+13)
diff --git a/libc/config/darwin/arm/entrypoints.txt b/libc/config/darwin/arm/entrypoints.txt
index 70c888aec064c..1759da59a7e5a 100644
--- a/libc/config/darwin/arm/entrypoints.txt
+++ b/libc/config/darwin/arm/entrypoints.txt
@@ -581,6 +581,7 @@ if(LIBC_COMPILER_HAS_FIXED_POINT)
     libc.src.stdfix.abslk
     libc.src.stdfix.abslr
     libc.src.stdfix.absr
+    libc.src.stdfix.divir
     libc.src.stdfix.exphk
     libc.src.stdfix.expk
     libc.src.stdfix.roundhk
diff --git a/libc/include/stdfix.yaml b/libc/include/stdfix.yaml
index 5b385124eb63d..16d7650884e3c 100644
--- a/libc/include/stdfix.yaml
+++ b/libc/include/stdfix.yaml
@@ -238,6 +238,14 @@ functions:
     arguments:
       - type: unsigned long accum
     guard: LIBC_COMPILER_HAS_FIXED_POINT
+  - name: divir
+    standards:
+      - stdc_ext
+    return_type: int
+    arguments:
+      - type: int
+      - type: fract
+    guard: LIBC_COMPILER_HAS_FIXED_POINT
   - name: idivr
     standards:
       - stdc_ext
diff --git a/libc/src/__support/fixed_point/divifx.h b/libc/src/__support/fixed_point/divifx.h
new file mode 100644
index 0000000000000..af715612c327d
--- /dev/null
+++ b/libc/src/__support/fixed_point/divifx.h
@@ -0,0 +1,132 @@
+//===-- Division of integers by fixed-point numbers ---------*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides implementations for functions that divide a standard
+// integer type by a fixed-point type, returning a standard integer type result.
+// This corresponds to the divi<fx> family (e.g., divir, divik) described
+// in ISO/IEC TR 18037:2008 Annex C.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIBC_SRC___SUPPORT_FIXEDPOINT_INT_DIV_FX_H
+#define LLVM_LIBC_SRC___SUPPORT_FIXEDPOINT_INT_DIV_FX_H
+
+#include "include/llvm-libc-macros/stdfix-macros.h" // Fixed-point types
+#include "src/__support/CPP/bit.h"                  // bit_cast
+#include "src/__support/CPP/limits.h"               // numeric_limits (optional)
+#include "src/__support/CPP/type_traits.h"          // conditional_t, is_same_v
+#include "src/__support/macros/attributes.h"        // LIBC_INLINE
+#include "src/__support/macros/config.h" // LIBC_NAMESPACE_DECL, LIBC_COMPILER_HAS_FIXED_POINT
+#include "src/__support/macros/optimization.h" // LIBC_UNLIKELY
+
+#include "fx_rep.h" // FXRep for type info (FRACTION_LEN, StorageType)
+
+// Only define contents if the compiler supports fixed-point types
+#ifdef LIBC_COMPILER_HAS_FIXED_POINT
+
+// Check for 128-bit integer support needed for high precision intermediates
+#if defined(__SIZEOF_INT128__)
+#define LIBC_INTERNAL_HAS_INT128
+using int128_t = __int128_t;
+using uint128_t = __uint128_t;
+#endif
+
+namespace LIBC_NAMESPACE_DECL {
+namespace fixed_point {
+namespace internal {
+
+// --- Helper type traits for selecting intermediate calculation types ---
+
+template <typename IntType, int FractionalBits>
+using SelectDivIntermediateSigned =
+    cpp::conditional_t<
+        (sizeof(IntType) * 8 - 1 + FractionalBits <= 64), int64_t,
+#ifdef LIBC_INTERNAL_HAS_INT128
+        cpp::conditional_t<(sizeof(IntType) * 8 - 1 + FractionalBits <= 128),
+                           int128_t,
+                           void>
+#else
+        void
+#endif
+        >;
+
+template <typename IntType, int FractionalBits>
+using SelectDivIntermediateUnsigned = cpp::conditional_t<
+    (sizeof(IntType) * 8 - 1 + FractionalBits <= 64), uint64_t,
+#ifdef LIBC_INTERNAL_HAS_INT128
+    cpp::conditional_t<(sizeof(IntType) * 8 - 1 + FractionalBits <= 128),
+                       uint128_t, void>
+#else
+    void
+#endif
+    >;
+
+// --- Core implementation template ---
+
+
+template <typename IntType, typename FxType>
+LIBC_INLINE IntType divifx_impl(IntType i, FxType fx) {
+  // Get metadata about the fixed-point type using FXRep helper
+  using FX = FXRep<FxType>;
+  using StorageType = typename FX::StorageType;
+  constexpr int F = FX::FRACTION_LEN;        // Number of fractional bits
+  constexpr bool FxIsSigned = FX::SIGN_LEN; // Is the fx type signed?
+
+  // Extract the raw integer bits from the fixed-point divisor
+  StorageType raw_fx = cpp::bit_cast<StorageType>(fx);
+
+  volatile StorageType check_raw_fx = raw_fx;
+  if (LIBC_UNLIKELY(check_raw_fx == 0)) {
+
+  }
+
+  // Select appropriately sized intermediate types for the calculation
+  using IntermediateSigned = SelectDivIntermediateSigned<IntType, F>;
+  using IntermediateUnsigned = SelectDivIntermediateUnsigned<IntType, F>;
+
+  // Compile-time check: ensure a wide enough type was found.
+  static_assert(!cpp::is_same_v<IntermediateSigned, void>,
+                "Calculation requires intermediate precision exceeding "
+                "available types (int64_t or __int128_t).");
+
+  // Calculate the numerator: (i << F)
+  // Use the signed intermediate type for the numerator.
+  IntermediateSigned num = static_cast<IntermediateSigned>(i) << F;
+
+  // Perform the division: num / raw_fx
+  IntermediateSigned intermediate_result;
+  if constexpr (FxIsSigned) {
+    IntermediateSigned den = static_cast<IntermediateSigned>(raw_fx);
+    intermediate_result = num / den;
+  } else {
+    IntermediateUnsigned den = static_cast<IntermediateUnsigned>(raw_fx);
+    intermediate_result = num / den;
+  }
+
+  return static_cast<IntType>(intermediate_result);
+}
+
+} // namespace internal
+
+//===----------------------------------------------------------------------===//
+// Public API: divi<fx> functions
+//===----------------------------------------------------------------------===//
+
+// --- Signed Fract Types ---
+
+/** Divides int by fract, returns int. */
+LIBC_INLINE int divir(int i, fract f) {
+  return internal::divifx_impl<int, fract>(i, f);
+}
+
+} // namespace fixed_point
+} // namespace LIBC_NAMESPACE_DECL
+
+#endif // LIBC_COMPILER_HAS_FIXED_POINT
+
+#endif // LLVM_LIBC_SRC___SUPPORT_FIXEDPOINT_INT_DIV_FX_H
diff --git a/libc/src/stdfix/CMakeLists.txt b/libc/src/stdfix/CMakeLists.txt
index 843111e3f80b1..926035199c958 100644
--- a/libc/src/stdfix/CMakeLists.txt
+++ b/libc/src/stdfix/CMakeLists.txt
@@ -26,6 +26,20 @@ foreach(suffix IN ITEMS uhr ur ulr uhk uk)
   )
 endforeach()
 
+foreach(suffix IN ITEMS r)
+  add_entrypoint_object(
+    divi${suffix}
+    HDRS
+      divi${suffix}.h
+    SRCS
+      divi${suffix}.cpp
+    COMPILE_OPTIONS
+      ${libc_opt_high_flag}
+    DEPENDS
+      libc.src.__support.fixed_point.fx_bits
+  )
+endforeach()
+
 foreach(suffix IN ITEMS hr r lr hk k lk uhr ur ulr uhk uk ulk)
   add_entrypoint_object(
     round${suffix}
diff --git a/libc/src/stdfix/divir.cpp b/libc/src/stdfix/divir.cpp
new file mode 100644
index 0000000000000..a952f9fba492f
--- /dev/null
+++ b/libc/src/stdfix/divir.cpp
@@ -0,0 +1,13 @@
+#include "divir.h"
+#include "src/__support/common.h"
+#include "src/__support/fixed_point/divifx.h" // divifx_impl
+#include "src/__support/fixed_point/fx_bits.h"
+#include "src/__support/macros/config.h" // LIBC_NAMESPACE_DECL
+
+namespace LIBC_NAMESPACE_DECL {
+
+LLVM_LIBC_FUNCTION(int, divir, (int i, fract f)) {
+  return fixed_point::divir(i, f);
+}
+
+} // namespace LIBC_NAMESPACE_DECL
diff --git a/libc/src/stdfix/divir.h b/libc/src/stdfix/divir.h
new file mode 100644
index 0000000000000..ef803160ff1b5
--- /dev/null
+++ b/libc/src/stdfix/divir.h
@@ -0,0 +1,21 @@
+//===-- Implementation header for divir function ----------------*- 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_STDFIX_DIVIR_H
+#define LLVM_LIBC_SRC_STDFIX_DIVIR_H
+
+#include "include/llvm-libc-macros/stdfix-macros.h" // Provides 'fract' type
+#include "src/__support/macros/config.h"           // LIBC_NAMESPACE_DECL
+
+namespace LIBC_NAMESPACE_DECL {
+
+int divir(int i, fract f);
+
+} // namespace LIBC_NAMESPACE_DECL
+
+#endif // LLVM_LIBC_SRC_STDFIX_DIVIR_H
diff --git a/libc/test/src/stdfix/CMakeLists.txt b/libc/test/src/stdfix/CMakeLists.txt
index e2b4bc1805f7c..d2449b628e87f 100644
--- a/libc/test/src/stdfix/CMakeLists.txt
+++ b/libc/test/src/stdfix/CMakeLists.txt
@@ -43,6 +43,23 @@ foreach(suffix IN ITEMS uhr ur ulr uhk uk)
   )
 endforeach()
 
+foreach(suffix IN ITEMS r)
+  add_libc_test(
+    divi${suffix}_test
+    SUITE
+      libc-stdfix-tests
+    HDRS
+      DiviFxTest.h
+    SRCS
+      divi${suffix}_test.cpp
+    COMPILE_OPTIONS
+      ${libc_opt_high_flag}
+    DEPENDS
+      libc.src.stdfix.divi${suffix}
+      libc.src.__support.fixed_point.fx_bits
+  )
+endforeach()
+
 foreach(suffix IN ITEMS hr r lr hk k lk uhr ur ulr uhk uk ulk)
   add_libc_test(
     round${suffix}_test
diff --git a/libc/test/src/stdfix/DiviFxTest.h b/libc/test/src/stdfix/DiviFxTest.h
new file mode 100644
index 0000000000000..1ee2a5e7b2b48
--- /dev/null
+++ b/libc/test/src/stdfix/DiviFxTest.h
@@ -0,0 +1,40 @@
+//===-- Utility class to test bitsfx functions ------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "test/UnitTest/Test.h"
+
+#include "src/__support/fixed_point/fx_rep.h"
+#include "src/__support/fixed_point/divifx.h"
+
+template <typename T, typename XType>
+class DiviFxTest : public LIBC_NAMESPACE::testing::Test {
+
+  using FXRep = LIBC_NAMESPACE::fixed_point::FXRep<T>;
+  static constexpr T zero = FXRep::ZERO();
+  static constexpr T max = FXRep::MAX();
+  static constexpr T min = FXRep::MIN();
+  static constexpr T one_half = FXRep::ONE_HALF();
+  static constexpr T one_fourth = FXRep::ONE_FOURTH();
+  static constexpr T eps = FXRep::EPS();
+
+public:
+  typedef XType (*DiviFxFunc)(int, T);
+
+  void testSpecialNumbers(DiviFxFunc func) {
+    EXPECT_EQ(static_cast<XType>(200), func(100, one_half));
+    EXPECT_EQ(static_cast<XType>(400), func(100, one_fourth));
+    // std::cout << one_half << " " << one_fourth << std::endl;
+  }
+};
+
+#define LIST_DIVIFX_TESTS(Name, T, XType, func)                                \
+  using LlvmLibcDivifx##Name##Test = DiviFxTest<T, XType>;                       \
+  TEST_F(LlvmLibcDivifx##Name##Test, SpecialNumbers) {                           \
+    testSpecialNumbers(&func);                                                 \
+  }                                                                            \
+  static_assert(true, "Require semicolon.")
diff --git a/libc/test/src/stdfix/divir_test.cpp b/libc/test/src/stdfix/divir_test.cpp
new file mode 100644
index 0000000000000..1fbd0f24852f5
--- /dev/null
+++ b/libc/test/src/stdfix/divir_test.cpp
@@ -0,0 +1,13 @@
+//===-- Unittests for divir -------------------------------------------===//
+//
+// 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 "DiviFxTest.h"
+
+#include "src/stdfix/divir.h"
+
+LIST_DIVIFX_TESTS(r, fract, int, LIBC_NAMESPACE::divir);

Copy link

github-actions bot commented May 2, 2025

✅ With the latest revision this PR passed the C/C++ code formatter.

@kr-2003
Copy link
Contributor Author

kr-2003 commented May 2, 2025

@PiJoules For now I have tried implementing divir function. Can you check the logic for divifx function? Then, I can move forward with this PR.

@lntue lntue self-requested a review May 2, 2025 11:18
@PiJoules PiJoules self-requested a review May 5, 2025 17:15
@PiJoules
Copy link
Contributor

PiJoules commented May 5, 2025

@PiJoules For now I have tried implementing divir function. Can you check the logic for divifx function? Then, I can move forward with this PR.

Casting up then shifting before an integral division I think is a good general approach. Rather than unconditionally using a 128-bit int I think it would be instead better to cast just to an appropriate storage of a higher rank. Perhaps you can add something to internal::Storage along the lines of using HigherRankStorage = ... then you can use that in place of Intermediate[Un]Signed. I think it would also help to add some tests to assert we're not missing edge cases.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

Successfully merging this pull request may close these issues.

3 participants
Morty Proxy This is a proxified and sanitized view of the page, visit original site.