| 1048 | ///////////// SINT64 |
| 1049 | |
| 1050 | static inline struct libdivide_s64_t libdivide_internal_s64_gen(int64_t d, int branchfree) { |
| 1051 | if (d == 0) { |
| 1052 | LIBDIVIDE_ERROR("divider must be != 0"); |
| 1053 | } |
| 1054 | |
| 1055 | struct libdivide_s64_t result; |
| 1056 | |
| 1057 | // If d is a power of 2, or negative a power of 2, we have to use a shift. |
| 1058 | // This is especially important because the magic algorithm fails for -1. |
| 1059 | // To check if d is a power of 2 or its inverse, it suffices to check |
| 1060 | // whether its absolute value has exactly one bit set. This works even for |
| 1061 | // INT_MIN, because abs(INT_MIN) == INT_MIN, and INT_MIN has one bit set |
| 1062 | // and is a power of 2. |
| 1063 | uint64_t ud = (uint64_t)d; |
| 1064 | uint64_t absD = (d < 0) ? -ud : ud; |
| 1065 | uint32_t floor_log_2_d = 63 - libdivide_count_leading_zeros64(absD); |
| 1066 | // check if exactly one bit is set, |
| 1067 | // don't care if absD is 0 since that's divide by zero |
| 1068 | if ((absD & (absD - 1)) == 0) { |
| 1069 | // Branchfree and non-branchfree cases are the same |
| 1070 | result.magic = 0; |
| 1071 | result.more = floor_log_2_d | (d < 0 ? LIBDIVIDE_NEGATIVE_DIVISOR : 0); |
| 1072 | } else { |
| 1073 | // the dividend here is 2**(floor_log_2_d + 63), so the low 64 bit word |
| 1074 | // is 0 and the high word is floor_log_2_d - 1 |
| 1075 | uint8_t more; |
| 1076 | uint64_t rem, proposed_m; |
| 1077 | proposed_m = libdivide_128_div_64_to_64(1ULL << (floor_log_2_d - 1), 0, absD, &rem); |
| 1078 | const uint64_t e = absD - rem; |
| 1079 | |
| 1080 | // We are going to start with a power of floor_log_2_d - 1. |
| 1081 | // This works if works if e < 2**floor_log_2_d. |
| 1082 | if (!branchfree && e < (1ULL << floor_log_2_d)) { |
| 1083 | // This power works |
| 1084 | more = floor_log_2_d - 1; |
| 1085 | } else { |
| 1086 | // We need to go one higher. This should not make proposed_m |
| 1087 | // overflow, but it will make it negative when interpreted as an |
| 1088 | // int32_t. |
| 1089 | proposed_m += proposed_m; |
| 1090 | const uint64_t twice_rem = rem + rem; |
| 1091 | if (twice_rem >= absD || twice_rem < rem) proposed_m += 1; |
| 1092 | // note that we only set the LIBDIVIDE_NEGATIVE_DIVISOR bit if we |
| 1093 | // also set ADD_MARKER this is an annoying optimization that |
| 1094 | // enables algorithm #4 to avoid the mask. However we always set it |
| 1095 | // in the branchfree case |
| 1096 | more = floor_log_2_d | LIBDIVIDE_ADD_MARKER; |
| 1097 | } |
| 1098 | proposed_m += 1; |
| 1099 | int64_t magic = (int64_t)proposed_m; |
| 1100 | |
| 1101 | // Mark if we are negative |
| 1102 | if (d < 0) { |
| 1103 | more |= LIBDIVIDE_NEGATIVE_DIVISOR; |
| 1104 | if (!branchfree) { |
| 1105 | magic = -magic; |
| 1106 | } |
| 1107 | } |
no test coverage detected