201 lines · c
1//===-- udivmoddi4.c - Implement __udivmoddi4 -----------------------------===//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// This file implements __udivmoddi4 for the compiler_rt library.10//11//===----------------------------------------------------------------------===//12 13#include "int_lib.h"14 15// Effects: if rem != 0, *rem = a % b16// Returns: a / b17 18// Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide19 20#if defined(_MSC_VER) && !defined(__clang__)21// MSVC throws a warning about mod 0 here, disable it for builds that22// warn-as-error23#pragma warning(push)24#pragma warning(disable : 4723 4724)25#endif26 27COMPILER_RT_ABI du_int __udivmoddi4(du_int a, du_int b, du_int *rem) {28 const unsigned n_uword_bits = sizeof(su_int) * CHAR_BIT;29 const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT;30 udwords n;31 n.all = a;32 udwords d;33 d.all = b;34 udwords q;35 udwords r;36 unsigned sr;37 // special cases, X is unknown, K != 038 if (n.s.high == 0) {39 if (d.s.high == 0) {40 // 0 X41 // ---42 // 0 X43 if (rem)44 *rem = n.s.low % d.s.low;45 return n.s.low / d.s.low;46 }47 // 0 X48 // ---49 // K X50 if (rem)51 *rem = n.s.low;52 return 0;53 }54 // n.s.high != 055 if (d.s.low == 0) {56 if (d.s.high == 0) {57 // K X58 // ---59 // 0 060 if (rem)61 *rem = n.s.high % d.s.low;62 return n.s.high / d.s.low;63 }64 // d.s.high != 065 if (n.s.low == 0) {66 // K 067 // ---68 // K 069 if (rem) {70 r.s.high = n.s.high % d.s.high;71 r.s.low = 0;72 *rem = r.all;73 }74 return n.s.high / d.s.high;75 }76 // K K77 // ---78 // K 079 if ((d.s.high & (d.s.high - 1)) == 0) /* if d is a power of 2 */ {80 if (rem) {81 r.s.low = n.s.low;82 r.s.high = n.s.high & (d.s.high - 1);83 *rem = r.all;84 }85 return n.s.high >> ctzsi(d.s.high);86 }87 // K K88 // ---89 // K 090 sr = clzsi(d.s.high) - clzsi(n.s.high);91 // 0 <= sr <= n_uword_bits - 2 or sr large92 if (sr > n_uword_bits - 2) {93 if (rem)94 *rem = n.all;95 return 0;96 }97 ++sr;98 // 1 <= sr <= n_uword_bits - 199 // q.all = n.all << (n_udword_bits - sr);100 q.s.low = 0;101 q.s.high = n.s.low << (n_uword_bits - sr);102 // r.all = n.all >> sr;103 r.s.high = n.s.high >> sr;104 r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);105 } else /* d.s.low != 0 */ {106 if (d.s.high == 0) {107 // K X108 // ---109 // 0 K110 if ((d.s.low & (d.s.low - 1)) == 0) /* if d is a power of 2 */ {111 if (rem)112 *rem = n.s.low & (d.s.low - 1);113 if (d.s.low == 1)114 return n.all;115 sr = ctzsi(d.s.low);116 q.s.high = n.s.high >> sr;117 q.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);118 return q.all;119 }120 // K X121 // ---122 // 0 K123 sr = 1 + n_uword_bits + clzsi(d.s.low) - clzsi(n.s.high);124 // 2 <= sr <= n_udword_bits - 1125 // q.all = n.all << (n_udword_bits - sr);126 // r.all = n.all >> sr;127 if (sr == n_uword_bits) {128 q.s.low = 0;129 q.s.high = n.s.low;130 r.s.high = 0;131 r.s.low = n.s.high;132 } else if (sr < n_uword_bits) /* 2 <= sr <= n_uword_bits - 1 */ {133 q.s.low = 0;134 q.s.high = n.s.low << (n_uword_bits - sr);135 r.s.high = n.s.high >> sr;136 r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);137 } else /* n_uword_bits + 1 <= sr <= n_udword_bits - 1 */ {138 q.s.low = n.s.low << (n_udword_bits - sr);139 q.s.high = (n.s.high << (n_udword_bits - sr)) |140 (n.s.low >> (sr - n_uword_bits));141 r.s.high = 0;142 r.s.low = n.s.high >> (sr - n_uword_bits);143 }144 } else {145 // K X146 // ---147 // K K148 sr = clzsi(d.s.high) - clzsi(n.s.high);149 // 0 <= sr <= n_uword_bits - 1 or sr large150 if (sr > n_uword_bits - 1) {151 if (rem)152 *rem = n.all;153 return 0;154 }155 ++sr;156 // 1 <= sr <= n_uword_bits157 // q.all = n.all << (n_udword_bits - sr);158 q.s.low = 0;159 if (sr == n_uword_bits) {160 q.s.high = n.s.low;161 r.s.high = 0;162 r.s.low = n.s.high;163 } else {164 q.s.high = n.s.low << (n_uword_bits - sr);165 r.s.high = n.s.high >> sr;166 r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr);167 }168 }169 }170 // Not a special case171 // q and r are initialized with:172 // q.all = n.all << (n_udword_bits - sr);173 // r.all = n.all >> sr;174 // 1 <= sr <= n_udword_bits - 1175 su_int carry = 0;176 for (; sr > 0; --sr) {177 // r:q = ((r:q) << 1) | carry178 r.s.high = (r.s.high << 1) | (r.s.low >> (n_uword_bits - 1));179 r.s.low = (r.s.low << 1) | (q.s.high >> (n_uword_bits - 1));180 q.s.high = (q.s.high << 1) | (q.s.low >> (n_uword_bits - 1));181 q.s.low = (q.s.low << 1) | carry;182 // carry = 0;183 // if (r.all >= d.all)184 // {185 // r.all -= d.all;186 // carry = 1;187 // }188 const di_int s = (di_int)(d.all - r.all - 1) >> (n_udword_bits - 1);189 carry = s & 1;190 r.all -= d.all & s;191 }192 q.all = (q.all << 1) | carry;193 if (rem)194 *rem = r.all;195 return q.all;196}197 198#if defined(_MSC_VER) && !defined(__clang__)199#pragma warning(pop)200#endif201