[libc] [stdfix] Implement fixed-point `mulifx` functions

[duncpro]

The fixed-point mulifx family of functions from ISO 18037 are not in llvm-libc yet.

The muli functions multiply an integer operand by a fixed-point operand and return an integer value.
...
If an integer result of one of these functions overflows, the behavior is undefined.

- ISO 18037

Definitions

int mulir(int, fract);
long int mulilr(long int, long fract);
int mulik(int, accum);
long int mulilk(long int, long accum);

unsigned int muliur(unsigned int, unsigned fract);
unsigned long int muliulr(unsigned long int, unsigned long fract);
unsigned int muliuk(unsigned int, unsigned accum);
unsigned long int muliulk(unsigned long int, unsigned long accum);

Implementation

For accum types this could be implemented by converting the integer operand into an accum with no fractional value, and then using the multiplication operator on the two accums. Then truncating the result's fractional value, and finally bitcasting to the integer type.

For fract types we could convert the fract into an accum with no integral value, and then use the same routine above.

[duncpro]

I'd like to work on this.

[duncpro]

Clang is able to convert from integral to fixed-point, and vice versa, and between fixed-point types via static_cast it appears.

That means the implementation can be as simple as... (I think)

fract

#include "mulir.h"
#include "src/__support/common.h"
#include "src/__support/macros/config.h"

namespace LIBC_NAMESPACE_DECL {

LLVM_LIBC_FUNCTION(int, mulir, (int x, fract y)) { 
  accum p = static_cast<accum>(x) * static_cast<accum>(y);
  return static_cast<int>(p);
}

} // namespace LIBC_NAMESPACE_DECL

accum

#include "mulik.h"
#include "src/__support/common.h"
#include "src/__support/macros/config.h"

namespace LIBC_NAMESPACE_DECL {

LLVM_LIBC_FUNCTION(int, mulik, (int x, accum y)) { 
  accum p = static_cast<accum>(x) * static_cast<accum>(y);
  return static_cast<int>(p);
}

} // namespace LIBC_NAMESPACE_DECL

We can use a template<A, B> to write a generic function that implements this approach for all multifx where A is integral type and B is the fixed-point type. However I'm not sure how we can properly constrain the template so that it is only defined for legal pairings of types. For instance <int, accum> is legal but <long, unsigned short accum> is not legal for instance.

Ideally we'll actually static_cast to the shortest accum-type that is still long enough to hold all possible integer values. So we'll need a way of resolving that accum-type given an integral type.

[lntue]

Clang is able to convert from integral to fixed-point, and vice versa, and between fixed-point types via static_cast it appears.

That means the implementation can be as simple as... (I think)

fract

#include "mulir.h"
#include "src/__support/common.h"
#include "src/__support/macros/config.h"

namespace LIBC_NAMESPACE_DECL {

LLVM_LIBC_FUNCTION(int, mulir, (int x, fract y)) { 
  accum p = static_cast<accum>(x) * static_cast<accum>(y);
  return static_cast<int>(p);
}

} // namespace LIBC_NAMESPACE_DECL

accum

#include "mulik.h"
#include "src/__support/common.h"
#include "src/__support/macros/config.h"

namespace LIBC_NAMESPACE_DECL {

LLVM_LIBC_FUNCTION(int, mulik, (int x, accum y)) { 
  accum p = static_cast<accum>(x) * static_cast<accum>(y);
  return static_cast<int>(p);
}

} // namespace LIBC_NAMESPACE_DECL

We can use a template<A, B> to write a generic function that implements this approach for all multifx where A is integral type and B is the fixed-point type. However I'm not sure how we can properly constrain the template so that it is only defined for legal pairings of types. For instance <int, accum> is legal but <long, unsigned short accum> is not legal for instance.

I think the tricky case is when the int x input is outside of accum type's range, but the result is not overflow or underflow.

[duncpro]

Intue, what do you think of this approach?

Let Z be the type of the unsigned integral operand z.
Let F be the type of the unsigned fixed-point operand f.

If there exists an accum type A such that...

• The number of fractional bits in A is at least the number of fractional bits in F.
• The number of integral bits in A is at least the number of integral bits in Z.
• The number of integral bits in A is at least the number of integral bits in F.

Then we static_cast both operands to A, let the compiler implement the multiplication, and then static_cast the result to Z and return it.

If no such type A exists, then we use a fallback library-level implementation of binary multiplication using bitstrings.
We'll know the max-width of the bit strings at compile time, so no allocation is needed.