137a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan/* ===-- udivmoddi4.c - Implement __udivmoddi4 -----------------------------=== 237a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * 337a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * The LLVM Compiler Infrastructure 437a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * 59ad441ffec97db647fee3725b3424284fb913e14Howard Hinnant * This file is dual licensed under the MIT and the University of Illinois Open 69ad441ffec97db647fee3725b3424284fb913e14Howard Hinnant * Source Licenses. See LICENSE.TXT for details. 737a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * 837a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * ===----------------------------------------------------------------------=== 937a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * 1037a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * This file implements __udivmoddi4 for the compiler_rt library. 1137a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * 1237a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * ===----------------------------------------------------------------------=== 1337a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan */ 14b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar 15b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar#include "int_lib.h" 16b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar 1737a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan/* Effects: if rem != 0, *rem = a % b 1837a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * Returns: a / b 1937a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan */ 20b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar 2137a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan/* Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide */ 22b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar 231c5f89b1dd741135a4007ab577723d422f421eecAnton KorobeynikovCOMPILER_RT_ABI du_int 24b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar__udivmoddi4(du_int a, du_int b, du_int* rem) 25b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar{ 26b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar const unsigned n_uword_bits = sizeof(su_int) * CHAR_BIT; 27b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT; 28b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar udwords n; 29b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar n.all = a; 30b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar udwords d; 31b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar d.all = b; 32b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar udwords q; 33b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar udwords r; 34b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar unsigned sr; 3537a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* special cases, X is unknown, K != 0 */ 368bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan if (n.s.high == 0) 37b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar { 388bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan if (d.s.high == 0) 39b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar { 4037a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* 0 X 4137a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * --- 4237a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * 0 X 4337a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan */ 44b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar if (rem) 458bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan *rem = n.s.low % d.s.low; 468bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan return n.s.low / d.s.low; 47b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar } 4837a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* 0 X 4937a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * --- 5037a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * K X 5137a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan */ 52b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar if (rem) 538bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan *rem = n.s.low; 54b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar return 0; 55b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar } 568bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan /* n.s.high != 0 */ 578bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan if (d.s.low == 0) 58b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar { 598bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan if (d.s.high == 0) 60b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar { 6137a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* K X 6237a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * --- 6337a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * 0 0 6437a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan */ 65b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar if (rem) 668bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan *rem = n.s.high % d.s.low; 678bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan return n.s.high / d.s.low; 68b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar } 698bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan /* d.s.high != 0 */ 708bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan if (n.s.low == 0) 71b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar { 7237a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* K 0 7337a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * --- 7437a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * K 0 7537a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan */ 76b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar if (rem) 77b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar { 788bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan r.s.high = n.s.high % d.s.high; 798bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan r.s.low = 0; 80b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar *rem = r.all; 81b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar } 828bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan return n.s.high / d.s.high; 83b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar } 8437a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* K K 8537a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * --- 8637a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * K 0 8737a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan */ 888bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan if ((d.s.high & (d.s.high - 1)) == 0) /* if d is a power of 2 */ 89b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar { 90b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar if (rem) 91b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar { 928bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan r.s.low = n.s.low; 938bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan r.s.high = n.s.high & (d.s.high - 1); 94b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar *rem = r.all; 95b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar } 968bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan return n.s.high >> __builtin_ctz(d.s.high); 97b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar } 9837a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* K K 9937a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * --- 10037a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * K 0 10137a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan */ 1028bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan sr = __builtin_clz(d.s.high) - __builtin_clz(n.s.high); 10337a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* 0 <= sr <= n_uword_bits - 2 or sr large */ 104b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar if (sr > n_uword_bits - 2) 105b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar { 106b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar if (rem) 107b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar *rem = n.all; 108b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar return 0; 109b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar } 110b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar ++sr; 11137a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* 1 <= sr <= n_uword_bits - 1 */ 11237a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* q.all = n.all << (n_udword_bits - sr); */ 1138bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan q.s.low = 0; 1148bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan q.s.high = n.s.low << (n_uword_bits - sr); 11537a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* r.all = n.all >> sr; */ 1168bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan r.s.high = n.s.high >> sr; 1178bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr); 118b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar } 1198bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan else /* d.s.low != 0 */ 120b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar { 1218bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan if (d.s.high == 0) 122b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar { 12337a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* K X 12437a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * --- 12537a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * 0 K 12637a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan */ 1278bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan if ((d.s.low & (d.s.low - 1)) == 0) /* if d is a power of 2 */ 128b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar { 129b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar if (rem) 1308bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan *rem = n.s.low & (d.s.low - 1); 1318bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan if (d.s.low == 1) 132b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar return n.all; 133d426091fdf6a15db9a5db35d522fe69f5dee35afJoerg Sonnenberger sr = __builtin_ctz(d.s.low); 1348bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan q.s.high = n.s.high >> sr; 1358bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan q.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr); 136b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar return q.all; 137b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar } 13837a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* K X 13937a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * --- 14037a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan *0 K 14137a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan */ 1428bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan sr = 1 + n_uword_bits + __builtin_clz(d.s.low) - __builtin_clz(n.s.high); 14337a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* 2 <= sr <= n_udword_bits - 1 14437a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * q.all = n.all << (n_udword_bits - sr); 14537a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * r.all = n.all >> sr; 14637a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * if (sr == n_uword_bits) 14737a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * { 1488bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan * q.s.low = 0; 1498bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan * q.s.high = n.s.low; 1508bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan * r.s.high = 0; 1518bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan * r.s.low = n.s.high; 15237a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * } 15337a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * else if (sr < n_uword_bits) // 2 <= sr <= n_uword_bits - 1 15437a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * { 1558bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan * q.s.low = 0; 1568bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan * q.s.high = n.s.low << (n_uword_bits - sr); 1578bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan * r.s.high = n.s.high >> sr; 1588bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan * r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr); 15937a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * } 16037a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * else // n_uword_bits + 1 <= sr <= n_udword_bits - 1 16137a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * { 1628bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan * q.s.low = n.s.low << (n_udword_bits - sr); 1638bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan * q.s.high = (n.s.high << (n_udword_bits - sr)) | 1648bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan * (n.s.low >> (sr - n_uword_bits)); 1658bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan * r.s.high = 0; 1668bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan * r.s.low = n.s.high >> (sr - n_uword_bits); 16737a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * } 16837a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan */ 1698bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan q.s.low = (n.s.low << (n_udword_bits - sr)) & 170b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar ((si_int)(n_uword_bits - sr) >> (n_uword_bits-1)); 1718bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan q.s.high = ((n.s.low << ( n_uword_bits - sr)) & 172b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar ((si_int)(sr - n_uword_bits - 1) >> (n_uword_bits-1))) | 1738bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan (((n.s.high << (n_udword_bits - sr)) | 1748bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan (n.s.low >> (sr - n_uword_bits))) & 175b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar ((si_int)(n_uword_bits - sr) >> (n_uword_bits-1))); 1768bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan r.s.high = (n.s.high >> sr) & 177b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1)); 1788bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan r.s.low = ((n.s.high >> (sr - n_uword_bits)) & 179b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar ((si_int)(n_uword_bits - sr - 1) >> (n_uword_bits-1))) | 1808bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan (((n.s.high << (n_uword_bits - sr)) | 1818bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan (n.s.low >> sr)) & 182b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1))); 183b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar } 184b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar else 185b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar { 18637a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* K X 18737a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * --- 18837a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * K K 18937a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan */ 1908bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan sr = __builtin_clz(d.s.high) - __builtin_clz(n.s.high); 19137a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* 0 <= sr <= n_uword_bits - 1 or sr large */ 192b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar if (sr > n_uword_bits - 1) 193b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar { 194b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar if (rem) 195b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar *rem = n.all; 196b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar return 0; 197b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar } 198b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar ++sr; 19937a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* 1 <= sr <= n_uword_bits */ 20037a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* q.all = n.all << (n_udword_bits - sr); */ 2018bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan q.s.low = 0; 2028bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan q.s.high = n.s.low << (n_uword_bits - sr); 20337a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* r.all = n.all >> sr; 20437a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * if (sr < n_uword_bits) 20537a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * { 2068bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan * r.s.high = n.s.high >> sr; 2078bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan * r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr); 20837a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * } 20937a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * else 21037a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * { 2118bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan * r.s.high = 0; 2128bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan * r.s.low = n.s.high; 21337a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * } 21437a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan */ 2158bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan r.s.high = (n.s.high >> sr) & 216b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1)); 2178bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan r.s.low = (n.s.high << (n_uword_bits - sr)) | 2188bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan ((n.s.low >> sr) & 219b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1))); 220b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar } 221b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar } 22237a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* Not a special case 22337a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * q and r are initialized with: 22437a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * q.all = n.all << (n_udword_bits - sr); 22537a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * r.all = n.all >> sr; 22637a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * 1 <= sr <= n_udword_bits - 1 22737a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan */ 228b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar su_int carry = 0; 229b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar for (; sr > 0; --sr) 230b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar { 23137a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* r:q = ((r:q) << 1) | carry */ 2328bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan r.s.high = (r.s.high << 1) | (r.s.low >> (n_uword_bits - 1)); 2338bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan r.s.low = (r.s.low << 1) | (q.s.high >> (n_uword_bits - 1)); 2348bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan q.s.high = (q.s.high << 1) | (q.s.low >> (n_uword_bits - 1)); 2358bf1e094893cb24796137b47ee0d46d18d299996Edward O'Callaghan q.s.low = (q.s.low << 1) | carry; 23637a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan /* carry = 0; 23737a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * if (r.all >= d.all) 23837a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * { 23937a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * r.all -= d.all; 24037a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * carry = 1; 24137a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan * } 24237a6a455466e5b197311771a777ab241e471ed8aEdward O'Callaghan */ 243b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar const di_int s = (di_int)(d.all - r.all - 1) >> (n_udword_bits - 1); 244b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar carry = s & 1; 245b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar r.all -= d.all & s; 246b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar } 247b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar q.all = (q.all << 1) | carry; 248b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar if (rem) 249b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar *rem = r.all; 250b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar return q.all; 251b3a6901e66f55b35aa9e01bcb24134e6a65ea004Daniel Dunbar} 252