Design

Requirements

  • These items definitely need the ability to remove the y prefix.

    • This will be done with a macro Y_NO_PREFIXES, which, if it is not 0, will cause the header with this stuff to create a bunch of defines of the form #define <item> y<item>.

    • For example, it will have #define s32a y_s32a (signed add for 32-bit), so the user can use s32a instead of y_s32a.

  • Implement signed with two’s-complement semantics only.

  • Implement using unsigned arithmetic only.

    • “Signed” integers should be structs with one field: n, an unsigned int of the correct size.

    • Implement format printing for signed numbers in y_printf() and friends.

      • Y_NO_PREFIXES should apply to those too, in order to prevent bugs where the system print() attempts to print these numbers.

  • Implement all functions using macros to select the correct number of bits, name, etc.

    • A macro invocation should result in a y_inline static inline function.

    • All functions should get some distinguishing identifier to prevent symbol collision.

    • All macro invocations should be in the header to allow the functions to be inlined even without -flto.

    • This will prevent users from being able to use them as function pointers.

      • Should I define versions that are meant for function pointers? They should have their own suffix if I do.

  • All libc functions that return signed values should be wrapped with careful code to do the conversions so as to prevent users from running into undefined behavior with libc.

    • Maybe unsigned return types too?

  • Define the following types:

    • y_s8 (s8 with no prefixes)

    • y_u8 (u8 with no prefixes, must have a macro y_u8s in that case to allow users to still use the u8 string literal prefix)

    • y_s16 (s16 with no prefixes)

    • y_u16 (u16 with no prefixes)

    • y_s32 (s32 with no prefixes)

    • y_u32 (u32 with no prefixes)

    • y_s64 (s64 with no prefixes)

    • y_u64 (u64 with no prefixes)

    • y_s128 (s128 with no prefixes and only when supported by the compiler)

    • y_u128 (u128 with no prefixes and only when supported by the compiler)

    • y_schar (schar with no prefixes)

    • y_uchar (uchar with no prefixes)

    • y_sshort (sshort with no prefixes)

    • y_ushort (ushort with no prefixes)

    • y_sint (sint with no prefixes)

    • y_uint (uint with no prefixes)

    • y_slong (slong with no prefixes)

    • y_ulong (ulong with no prefixes)

    • y_sllong (sllong with no prefixes)

    • y_ullong (ullong with no prefixes)

    • y_ssize (ssize with no prefixes)

    • y_usize (usize with no prefixes)

    • y_ptr (ptr with no prefixes)

Below, o1 is the first operand, and o2 is the second.

Arithmetic Ops

General Ops

These will not be directly implemented, but these requirements are the base requirements for all specific arithmetic ops (see below).

For the output of the dr and dm ops, see the mod_test.py script.

<t> stands in for the type minus the signed status. For example, for u8, u<t>a translates to u8a.

  • s<t>a (signed addition):

    • Just add (unsigned add is well-defined).

    • Overflow: If the sign bits of o1 and o2 match each other, but do not match the result sign bit.

  • u<t>a (unsigned addition):

    • Just add (unsigned add is well-defined).

    • Overflow: If the result is smaller than o1. (It is guaranteed to either be smaller than both or neither.)

  • s<t>s (signed subtraction):

    • Just subtract (unsigned subtract is well-defined).

    • Overflow: If the sign bits of o1 and o2 do not match and the sign bit of the result does not match the sign bit of o1, not o2.

  • u<t>s (unsigned subtraction):

    • Just subtract (unsigned subtract is well-defined).

    • Overflow: If the result is greater than o1. (It is guaranteed to either be greater than both or neither.)

  • s<t>m (signed multiplication):

    • Just multiply with integers twice as large (unsigned multiply is well-defined, and I have checked that all combinations of values of unsigned integers match what would happen if signed multiplication were defined as 2’s-complement).

    • Output: A struct with two fields, hi and lo. This is because the result can be twice as big as the inputs.

  • u<t>m (unsigned multiplication):

    • Just multiply with integers twice as large (unsigned multiply is well-defined, and I have checked that all combinations of values of unsigned integers match what would happen if signed multiplication were defined as 2’s-complement).

    • Output: A struct with two fields, hi and lo. This is because the result can be twice as big as the inputs.

  • s<t>d (signed division):

    • If o2 is 0, return an error.

    • If o1 is “negative”, negate it.

    • If o2 is “negative”, negate it.

    • Perform the division.

    • If the original signs of o1 and o2 don’t match, negate the quotient.

    • Overflow: If 1<<numbits-1 is divided by all 1’s (-1).

  • u<t>d (unsigned division):

    • If o2 is 0, return an error.

    • Perform the division.

  • s<t>dr (signed division with remainder):

    • If o2 is 0, return an error.

    • If o1 is “negative”, negate it.

    • If o2 is “negative”, negate it.

    • Perform the division.

    • Take the remainder.

    • If the original signs of o1 and o2 don’t match, negate the quotient.

    • If the original sign of o1 is negative, negate the remainder.

    • Output: a struct with two fields, q and r.

    • Overflow: If 1<<numbits-1 is divided by all 1’s (-1).

  • s<t>dm (signed division with modulus):

    • If o2 is 0, return an error.

    • If o1 is “negative”, negate it.

    • If o2 is “negative”, negate it.

    • Perform the division.

    • Take the remainder.

    • Calculate the modulus from the remainder:

      • If the original signs of o2 and o2 don’t match and the remainder is not zero, subtract the remainder from o2.

    • If the original signs of o1 and o2 don’t match, negate the quotient.

    • If the original sign of o2 is negative, negate the modulus.

    • Output: a struct with two fields, q and m.

    • Overflow: If 1<<numbits-1 is divided by all 1’s (-1).

  • u<t>dr (unsigned division with remainder):

    • If o2 is 0, return an error.

    • Perform the division.

    • Take the remainder.

    • Output: a struct with two fields, q and r.

    • There is no such thing as udm (unsigned division with modulus) because the behavior is exactly the same.

Suffixes

Each arithmetic operation can have several suffixes:

  • none: Will abort() on overflow, and in the case of division, on divide by 0.

  • o (overflow): will return a struct with the result and the overflow. Doesn’t apply to unsigned division.

  • s (saturating): if the arithmetic overflows, will return the highest (add and multiply with matching signs) or lowest (subtract and multiply with non-matching signs) number.

  • w (wrap): will wrap without returning the overflow.

Specific Ops

For ops with #, the supported bit numbers are:

  • 8

  • 16

  • 32

  • 64

  • 128 (if supported by the compiler)

The specific ops are basically the general ops combined with the types defined above combined with the suffixes defined above, combinatorially.

Bitwise Ops

Like the arithmetic operations, these are combined with the types above, but with no suffixes.

  • neg (negate):

    • Flip all the bits. (This is well-defined.)

  • sneg (signed negate):

    • Flip all the bits and add 1. (This is two’s-complement negation.)

  • sshl (signed shift left):

    • Just shifts left.

    • If o2 is greater than or equal to the number of bits in o1, returns 0.

    • Operands: o1 is signed; o2 is treated, or cast to, unsigned.

    • Overflow: When any bits shifted out do not match result sign bit.

  • ushl (unsigned shift left):

    • Just shifts left.

    • If o2 is greater than or equal to the number of bits in o1, returns 0.

    • Operands: o1 is signed; o2 is treated, or cast to, unsigned.

    • Overflow: If any non-zero bits are shifted out.

  • sshr (signed shift right, arithmetic shift right):

    • Grabs the sign bit.

    • Shifts right.

    • If the sign bit was 1, make all new bits 1.

      • This can be done with: s = 1 << o2; s -= 1; r |= s << numbits - o2.

      • Be sure to handle case of shifting by too many bits.

    • If o2 is greater than or equal to the number of bits in o1, return all bits equal to the original sign bit.

  • ushr (unsigned shift right, logical shift right):

    • Shifts right.

    • If o2 is greater than or equal to the number of bits in o1, returns 0.

  • and (bitwise and):

    • Just do a bitwise and; there is no UB.

  • or (bitwise or):

    • Just do a bitwise or; there is no UB.

  • xor (bitwise xor):

    • Just do a bitwise xor; there is no UB.

  • trunc (truncate):

    • Truncate to the largest size smaller than the current type (or same type if there are no smaller types).

    • It is defined as discarding the higher-order bits.

  • uext (unsigned zero extend):

    • Zero extend to the smallest size larger than the current type (or same type of there are no larger types).

  • sext (signed extend):

    • Copy the sign bit and create a type of the same size of the operand with all bits set to the sign bit.

    • Cast the sign bit integer to the next largest type.

    • Cast the operand to the next largest type.

    • Bitwise or.

  • ptr2int (pointer to integer):

    • Safely cast a pointer to an integer.

  • int2ptr (integer to pointer):

    • Safely cast an integer to a pointer.

  • bitrev (bitreverse):

    • Attempt to use compiler intrinsics where known.

    • Reverse the order of the bits.

  • bswap (byte swap):

    • Attempt to use compiler intrinsics where known.

    • Perform a byte swap (like bitrev but at the level of bytes, not bits).

  • ctpop (count population):

    • Attempt to use compiler intrinsics where known.

    • Count the number of bits set in the operand.

  • ctlz (count leading zeros):

    • Attempt to use compiler intrinsics where known.

    • Count the number of leading zeros in the operand.

    • Return the numbers of bits when operand is zero. (May be UB otherwise.)

  • cttz (count trailing zeros):

    • Attempt to use compiler intrinsics where known.

    • Count the number of trailing zeros in the operand.

    • Return the numbers of bits when operand is zero. (May be UB otherwise.)

  • rotl (rotate left):

    • Attempt to use compiler intrinsics where known.

    • Rotate the bits in the value left, putting the shifted out bits on the right.

  • rotr (rotate right):

    • Attempt to use compiler intrinsics where known.

    • Rotate the bits in the value right, putting the shifted out bits on the left.

  • fshl (funnel shift left):

    • Attempt to use compiler intrinsics where known.

    • Concat o1 and o2 into one value twice as big and shift left by o3. Then take the most significant bits equal to the size of the operands.

  • fshr (funnel shift right):

    • Attempt to use compiler intrinsics where known.

    • Concat o1 and o2 into one value twice as big and shift right by o3. Then take the least significant bits equal to the size of the operands.

Comparison Ops

Like the arithmetic operations, these are combined with the types above, but with no suffixes.

  • sn (signed is negative):

    • Returns true if the operand is greater than or equal to 1<<numbit-1, false otherwise. (This tests if the operand is negative.)

  • eq (equal):

    • Returns true if o1 and o2 are equal, false otherwise.

  • ne (not equal):

    • Returns true if o1 and o2 are not equal, false otherwise.

  • slt (signed less than):

    • If o1 is greater than or equal to 1<<numbits-1:

      • If o2 is greater than or equal to 1<<numbits-1, compare and return the result.

      • Else return true (o1 is less than o2).

    • Else:

      • If o2 is greater than or equal to 1<<numbits-1, return false (o1 is greater than o2).

      • Else compare and return the result.

  • sle (signed less than or equal):

    • If o1 is greater than or equal to 1<<numbits-1:

      • If o2 is greater than or equal to 1<<numbits-1, compare and return the result.

      • Else return true (o1 is less than o2).

    • Else:

      • If o2 is greater than or equal to 1<<numbits-1, return false (o1 is greater than o2).

      • Else compare and return the result.

  • sgt (signed greater than):

    • If o1 is greater than or equal to 1<<numbits-1:

      • If o2 is greater than or equal to 1<<numbits-1, compare and return the result.

      • Else return false (o1 is less than o2).

    • Else:

      • If o2 is greater than or equal to 1<<numbits-1, return true (o1 is greater than o2).

      • Else compare and return the result.

  • sge (signed greater than or equal):

    • If o1 is greater than or equal to 1<<numbits-1:

      • If o2 is greater than or equal to 1<<numbits-1, compare and return the result.

      • Else return false (o1 is less than o2).

    • Else:

      • If o2 is greater than or equal to 1<<numbits-1, return true (o1 is greater than o2).

      • Else compare and return the result.

  • ult (unsigned less than):

    • Compare and return the result.

  • ule (signed less than or equal):

    • Compare and return the result.

  • ugt (signed greater than):

    • Compare and return the result.

  • uge (signed greater than or equal):

    • Compare and return the result.

Conversion

I need routines for users to convert from actual signed integers to Yc’s versions.

When doing the conversion, there need to be #ifdef’s for different kinds of architectures, because unfortunately, there is no easy solution.

Then, there should be explicit checks for negative 0 (signed magnitued and 1’s complement) or INT_MIN (2’s complement).

Issues

  • Add division-type functions that have precondition that the divisor is not 0?

  • If I do the above, I should also add that for no overflow for division types, add, subtract, multiply, shift, etc.

Future

  • Implement vectorization.

    • Attempt to use compiler intrinsics where possible.

    • See the LLVM Language Reference for examples.