132 lines · plain
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include <clc/clc_convert.h>10#include <clc/integer/clc_hadd.h>11#include <clc/integer/definitions.h>12#include <clc/internal/clc.h>13 14// For all types EXCEPT long, which is implemented separately15#define __CLC_MUL_HI_IMPL(BGENTYPE, GENTYPE, GENSIZE) \16 _CLC_OVERLOAD _CLC_DEF GENTYPE __clc_mul_hi(GENTYPE x, GENTYPE y) { \17 BGENTYPE large_x = __clc_convert_##BGENTYPE(x); \18 BGENTYPE large_y = __clc_convert_##BGENTYPE(y); \19 BGENTYPE large_mul_hi = (large_x * large_y) >> (BGENTYPE)GENSIZE; \20 return __clc_convert_##GENTYPE(large_mul_hi); \21 }22 23#define __CLC_MUL_HI_DEC_IMPL(BTYPE, TYPE, BITS) \24 __CLC_MUL_HI_IMPL(BTYPE, TYPE, BITS) \25 __CLC_MUL_HI_IMPL(BTYPE##2, TYPE##2, BITS) \26 __CLC_MUL_HI_IMPL(BTYPE##3, TYPE##3, BITS) \27 __CLC_MUL_HI_IMPL(BTYPE##4, TYPE##4, BITS) \28 __CLC_MUL_HI_IMPL(BTYPE##8, TYPE##8, BITS) \29 __CLC_MUL_HI_IMPL(BTYPE##16, TYPE##16, BITS)30 31_CLC_OVERLOAD _CLC_DEF long __clc_mul_hi(long x, long y) {32 long f, o, i;33 ulong l;34 35 // Move the high/low halves of x/y into the lower 32-bits of variables so36 // that we can multiply them without worrying about overflow.37 long x_hi = x >> 32;38 long x_lo = x & UINT_MAX;39 long y_hi = y >> 32;40 long y_lo = y & UINT_MAX;41 42 // Multiply all of the components according to FOIL method43 f = x_hi * y_hi;44 o = x_hi * y_lo;45 i = x_lo * y_hi;46 l = x_lo * y_lo;47 48 // Now add the components back together in the following steps:49 // F: doesn't need to be modified50 // O/I: Need to be added together.51 // L: Shift right by 32-bits, then add into the sum of O and I52 // Once O/I/L are summed up, then shift the sum by 32-bits and add to F.53 //54 // We use hadd to give us a bit of extra precision for the intermediate sums55 // but as a result, we shift by 31 bits instead of 3256 return (long)(f + (__clc_hadd(o, (i + (long)((ulong)l >> 32))) >> 31));57}58 59_CLC_OVERLOAD _CLC_DEF ulong __clc_mul_hi(ulong x, ulong y) {60 ulong f, o, i;61 ulong l;62 63 // Move the high/low halves of x/y into the lower 32-bits of variables so64 // that we can multiply them without worrying about overflow.65 ulong x_hi = x >> 32;66 ulong x_lo = x & UINT_MAX;67 ulong y_hi = y >> 32;68 ulong y_lo = y & UINT_MAX;69 70 // Multiply all of the components according to FOIL method71 f = x_hi * y_hi;72 o = x_hi * y_lo;73 i = x_lo * y_hi;74 l = x_lo * y_lo;75 76 // Now add the components back together, taking care to respect the fact that:77 // F: doesn't need to be modified78 // O/I: Need to be added together.79 // L: Shift right by 32-bits, then add into the sum of O and I80 // Once O/I/L are summed up, then shift the sum by 32-bits and add to F.81 //82 // We use hadd to give us a bit of extra precision for the intermediate sums83 // but as a result, we shift by 31 bits instead of 3284 return (f + (__clc_hadd(o, (i + (l >> 32))) >> 31));85}86 87// Vector-based mul_hi implementation for logn/ulong. See comments in the scalar88// versions for more detail.89#define __CLC_MUL_HI_LONG_VEC_IMPL(TY, UTY) \90 _CLC_OVERLOAD _CLC_DEF TY __clc_mul_hi(TY x, TY y) { \91 TY f, o, i; \92 UTY l; \93 \94 TY x_hi = x >> 32; \95 TY x_lo = x & UINT_MAX; \96 TY y_hi = y >> 32; \97 TY y_lo = y & UINT_MAX; \98 \99 f = x_hi * y_hi; \100 o = x_hi * y_lo; \101 i = x_lo * y_hi; \102 l = __clc_convert_##UTY(x_lo * y_lo); \103 i += __clc_convert_##TY(l >> (UTY)32); \104 \105 return f + (__clc_hadd(o, i) >> (TY)31); \106 }107 108#define __CLC_MUL_HI_LONG_IMPL(BTYPE, UBTYPE) \109 __CLC_MUL_HI_LONG_VEC_IMPL(BTYPE##2, UBTYPE##2) \110 __CLC_MUL_HI_LONG_VEC_IMPL(BTYPE##3, UBTYPE##3) \111 __CLC_MUL_HI_LONG_VEC_IMPL(BTYPE##4, UBTYPE##4) \112 __CLC_MUL_HI_LONG_VEC_IMPL(BTYPE##8, UBTYPE##8) \113 __CLC_MUL_HI_LONG_VEC_IMPL(BTYPE##16, UBTYPE##16)114 115#define __CLC_MUL_HI_TYPES() \116 __CLC_MUL_HI_DEC_IMPL(short, char, 8) \117 __CLC_MUL_HI_DEC_IMPL(ushort, uchar, 8) \118 __CLC_MUL_HI_DEC_IMPL(int, short, 16) \119 __CLC_MUL_HI_DEC_IMPL(uint, ushort, 16) \120 __CLC_MUL_HI_DEC_IMPL(long, int, 32) \121 __CLC_MUL_HI_DEC_IMPL(ulong, uint, 32) \122 __CLC_MUL_HI_LONG_IMPL(long, ulong) \123 __CLC_MUL_HI_LONG_IMPL(ulong, ulong)124 125__CLC_MUL_HI_TYPES()126 127#undef __CLC_MUL_HI_TYPES128#undef __CLC_MUL_HI_LONG_IMPL129#undef __CLC_MUL_HI_LONG_VEC_IMPL130#undef __CLC_MUL_HI_DEC_IMPL131#undef __CLC_MUL_HI_IMPL132