| 879 | /////////// SINT32 |
| 880 | |
| 881 | static inline struct libdivide_s32_t libdivide_internal_s32_gen(int32_t d, int branchfree) { |
| 882 | if (d == 0) { |
| 883 | LIBDIVIDE_ERROR("divider must be != 0"); |
| 884 | } |
| 885 | |
| 886 | struct libdivide_s32_t result; |
| 887 | |
| 888 | // If d is a power of 2, or negative a power of 2, we have to use a shift. |
| 889 | // This is especially important because the magic algorithm fails for -1. |
| 890 | // To check if d is a power of 2 or its inverse, it suffices to check |
| 891 | // whether its absolute value has exactly one bit set. This works even for |
| 892 | // INT_MIN, because abs(INT_MIN) == INT_MIN, and INT_MIN has one bit set |
| 893 | // and is a power of 2. |
| 894 | uint32_t ud = (uint32_t)d; |
| 895 | uint32_t absD = (d < 0) ? -ud : ud; |
| 896 | uint32_t floor_log_2_d = 31 - libdivide_count_leading_zeros32(absD); |
| 897 | // check if exactly one bit is set, |
| 898 | // don't care if absD is 0 since that's divide by zero |
| 899 | if ((absD & (absD - 1)) == 0) { |
| 900 | // Branchfree and normal paths are exactly the same |
| 901 | result.magic = 0; |
| 902 | result.more = floor_log_2_d | (d < 0 ? LIBDIVIDE_NEGATIVE_DIVISOR : 0); |
| 903 | } else { |
| 904 | LIBDIVIDE_ASSERT(floor_log_2_d >= 1); |
| 905 | |
| 906 | uint8_t more; |
| 907 | // the dividend here is 2**(floor_log_2_d + 31), so the low 32 bit word |
| 908 | // is 0 and the high word is floor_log_2_d - 1 |
| 909 | uint32_t rem, proposed_m; |
| 910 | proposed_m = libdivide_64_div_32_to_32(1U << (floor_log_2_d - 1), 0, absD, &rem); |
| 911 | const uint32_t e = absD - rem; |
| 912 | |
| 913 | // We are going to start with a power of floor_log_2_d - 1. |
| 914 | // This works if works if e < 2**floor_log_2_d. |
| 915 | if (!branchfree && e < (1U << floor_log_2_d)) { |
| 916 | // This power works |
| 917 | more = floor_log_2_d - 1; |
| 918 | } else { |
| 919 | // We need to go one higher. This should not make proposed_m |
| 920 | // overflow, but it will make it negative when interpreted as an |
| 921 | // int32_t. |
| 922 | proposed_m += proposed_m; |
| 923 | const uint32_t twice_rem = rem + rem; |
| 924 | if (twice_rem >= absD || twice_rem < rem) proposed_m += 1; |
| 925 | more = floor_log_2_d | LIBDIVIDE_ADD_MARKER; |
| 926 | } |
| 927 | |
| 928 | proposed_m += 1; |
| 929 | int32_t magic = (int32_t)proposed_m; |
| 930 | |
| 931 | // Mark if we are negative. Note we only negate the magic number in the |
| 932 | // branchfull case. |
| 933 | if (d < 0) { |
| 934 | more |= LIBDIVIDE_NEGATIVE_DIVISOR; |
| 935 | if (!branchfree) { |
| 936 | magic = -magic; |
| 937 | } |
| 938 | } |
no test coverage detected