Implement fixed point fxdivi functions in llvm-libc

[PiJoules]

ISO 18037 describes various fixed point fxdivi functions which divide an integer by an integer and returns a fixed point type.

[llvmbot]

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1. Check that no other contributor has already been assigned to this issue. If you believe that no one is actually working on it despite an assignment, ping the person. After one week without a response, the assignee may be changed.
2. In the comments of this issue, request for it to be assigned to you, or just create a pull request after following the steps below. Mention this issue in the description of the pull request.
3. Fix the issue locally.
4. Run the test suite locally. Remember that the subdirectories under test/ create fine-grained testing targets, so you can e.g. use make check-clang-ast to only run Clang's AST tests.
5. Create a Git commit.
6. Run git clang-format HEAD~1 to format your changes.
7. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation. Mention this issue in the description of the pull request.

If you have any further questions about this issue, don't hesitate to ask via a comment in the thread below.

[llvmbot]

@llvm/issue-subscribers-good-first-issue

Author: None (PiJoules)

ISO 18037 describes various fixed point `fxdivi` functions which divide an integer by an integer and returns a fixed point type.

[llvmbot]

@llvm/issue-subscribers-libc

Author: None (PiJoules)

ISO 18037 describes various fixed point `fxdivi` functions which divide an integer by an integer and returns a fixed point type.

[moar55]

I would like to take this one :)

[PiJoules]

I would like to take this one :)

Assigned. Thanks!

[Devesh-Yadav10]

can i have this?

[moar55]

@PiJoules Hey do you have an idea what the operands for each case should be. Just normal int? or something akin to fxsqrt that we have where the operand types matches the output in some way.

[PiJoules]

@PiJoules Hey do you have an idea what the operands for each case should be. Just normal int? or something akin to fxsqrt that we have where the operand types matches the output in some way.

7.18a.6.1 The fixed-point arithmetic operation support functions has a list of the signatures for the fxdivi functions

fract rdivi(int, int);
long fract lrdivi(long int, long int);
accum kdivi(int, int);
long accum lkdivi(long int, long int);
unsigned fract urdivi(unsigned int, unsigned int);
unsigned long fract ulrdivi(unsigned long int, unsigned long int);
unsigned accum ukdivi(unsigned int, unsigned int);
unsigned long accum ulkdivi(unsigned long int, unsigned long int);

[moar55]

Hey, I have gotten busy for a while but I am picking this up again.
Just a quick question, is there a particular algorithm you have in mind i should be using for the division?
I am also curious if I can reuse FPUtil's generic div function in libc 🤔

[lntue]

I think we can do initial approximation + one or more round of newton-raphson, similar to sqrt: https://github.com/llvm/llvm-project/blob/main/libc/src/__support/fixed_point/sqrt.h

We can implement it one by one, starting with small types. For really small types (8-bit, or even 16-bit), probably shift-and-add algorithm could work well enough. We could try both approaches and benchmark code-size + latency.

[bojle]

@PiJoules I would like to take up this issue since I don't see any progress on this.
I'll be using #113359 as the template for changes that have to be made. As @lntue suggested, i'll give those methods of division a try. Anything else i should keep in mind before i start?

@moar55 are you still working on this?