177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao/* ===-- udivmoddi4.c - Implement __udivmoddi4 -----------------------------=== 277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * 377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * The LLVM Compiler Infrastructure 477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * 577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * This file is distributed under the University of Illinois Open Source 677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * License. See LICENSE.TXT for details. 777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * 877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * ===----------------------------------------------------------------------=== 977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * 1077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * This file implements __udivmoddi4 for the compiler_rt library. 1177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * 1277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * ===----------------------------------------------------------------------=== 1377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao */ 1477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao 1577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao#include "int_lib.h" 1677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao 1777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao/* Effects: if rem != 0, *rem = a % b 1877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * Returns: a / b 1977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao */ 2077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao 2177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao/* Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide */ 2277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao 2377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liaodu_int 2477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao__udivmoddi4(du_int a, du_int b, du_int* rem) 2577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao{ 2677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao const unsigned n_uword_bits = sizeof(su_int) * CHAR_BIT; 2777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT; 2877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao udwords n; 2977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao n.all = a; 3077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao udwords d; 3177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao d.all = b; 3277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao udwords q; 3377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao udwords r; 3477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao unsigned sr; 3577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* special cases, X is unknown, K != 0 */ 3677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (n.s.high == 0) 3777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao { 3877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (d.s.high == 0) 3977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao { 4077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* 0 X 4177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * --- 4277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * 0 X 4377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao */ 4477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (rem) 4577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao *rem = n.s.low % d.s.low; 4677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao return n.s.low / d.s.low; 4777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao } 4877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* 0 X 4977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * --- 5077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * K X 5177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao */ 5277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (rem) 5377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao *rem = n.s.low; 5477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao return 0; 5577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao } 5677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* n.s.high != 0 */ 5777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (d.s.low == 0) 5877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao { 5977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (d.s.high == 0) 6077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao { 6177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* K X 6277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * --- 6377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * 0 0 6477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao */ 6577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (rem) 6677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao *rem = n.s.high % d.s.low; 6777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao return n.s.high / d.s.low; 6877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao } 6977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* d.s.high != 0 */ 7077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (n.s.low == 0) 7177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao { 7277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* K 0 7377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * --- 7477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * K 0 7577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao */ 7677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (rem) 7777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao { 7877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao r.s.high = n.s.high % d.s.high; 7977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao r.s.low = 0; 8077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao *rem = r.all; 8177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao } 8277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao return n.s.high / d.s.high; 8377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao } 8477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* K K 8577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * --- 8677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * K 0 8777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao */ 8877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if ((d.s.high & (d.s.high - 1)) == 0) /* if d is a power of 2 */ 8977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao { 9077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (rem) 9177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao { 9277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao r.s.low = n.s.low; 9377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao r.s.high = n.s.high & (d.s.high - 1); 9477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao *rem = r.all; 9577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao } 9677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao return n.s.high >> __builtin_ctz(d.s.high); 9777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao } 9877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* K K 9977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * --- 10077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * K 0 10177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao */ 10277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao sr = __builtin_clz(d.s.high) - __builtin_clz(n.s.high); 10377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* 0 <= sr <= n_uword_bits - 2 or sr large */ 10477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (sr > n_uword_bits - 2) 10577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao { 10677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (rem) 10777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao *rem = n.all; 10877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao return 0; 10977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao } 11077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao ++sr; 11177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* 1 <= sr <= n_uword_bits - 1 */ 11277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* q.all = n.all << (n_udword_bits - sr); */ 11377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao q.s.low = 0; 11477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao q.s.high = n.s.low << (n_uword_bits - sr); 11577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* r.all = n.all >> sr; */ 11677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao r.s.high = n.s.high >> sr; 11777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr); 11877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao } 11977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao else /* d.s.low != 0 */ 12077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao { 12177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (d.s.high == 0) 12277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao { 12377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* K X 12477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * --- 12577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * 0 K 12677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao */ 12777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if ((d.s.low & (d.s.low - 1)) == 0) /* if d is a power of 2 */ 12877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao { 12977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (rem) 13077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao *rem = n.s.low & (d.s.low - 1); 13177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (d.s.low == 1) 13277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao return n.all; 13377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao unsigned sr = __builtin_ctz(d.s.low); 13477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao q.s.high = n.s.high >> sr; 13577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao q.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr); 13677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao return q.all; 13777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao } 13877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* K X 13977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * --- 14077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao *0 K 14177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao */ 14277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao sr = 1 + n_uword_bits + __builtin_clz(d.s.low) - __builtin_clz(n.s.high); 14377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* 2 <= sr <= n_udword_bits - 1 14477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * q.all = n.all << (n_udword_bits - sr); 14577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * r.all = n.all >> sr; 14677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * if (sr == n_uword_bits) 14777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * { 14877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * q.s.low = 0; 14977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * q.s.high = n.s.low; 15077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * r.s.high = 0; 15177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * r.s.low = n.s.high; 15277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * } 15377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * else if (sr < n_uword_bits) // 2 <= sr <= n_uword_bits - 1 15477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * { 15577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * q.s.low = 0; 15677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * q.s.high = n.s.low << (n_uword_bits - sr); 15777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * r.s.high = n.s.high >> sr; 15877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr); 15977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * } 16077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * else // n_uword_bits + 1 <= sr <= n_udword_bits - 1 16177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * { 16277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * q.s.low = n.s.low << (n_udword_bits - sr); 16377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * q.s.high = (n.s.high << (n_udword_bits - sr)) | 16477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * (n.s.low >> (sr - n_uword_bits)); 16577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * r.s.high = 0; 16677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * r.s.low = n.s.high >> (sr - n_uword_bits); 16777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * } 16877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao */ 16977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao q.s.low = (n.s.low << (n_udword_bits - sr)) & 17077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao ((si_int)(n_uword_bits - sr) >> (n_uword_bits-1)); 17177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao q.s.high = ((n.s.low << ( n_uword_bits - sr)) & 17277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao ((si_int)(sr - n_uword_bits - 1) >> (n_uword_bits-1))) | 17377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao (((n.s.high << (n_udword_bits - sr)) | 17477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao (n.s.low >> (sr - n_uword_bits))) & 17577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao ((si_int)(n_uword_bits - sr) >> (n_uword_bits-1))); 17677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao r.s.high = (n.s.high >> sr) & 17777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1)); 17877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao r.s.low = ((n.s.high >> (sr - n_uword_bits)) & 17977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao ((si_int)(n_uword_bits - sr - 1) >> (n_uword_bits-1))) | 18077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao (((n.s.high << (n_uword_bits - sr)) | 18177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao (n.s.low >> sr)) & 18277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1))); 18377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao } 18477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao else 18577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao { 18677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* K X 18777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * --- 18877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * K K 18977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao */ 19077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao sr = __builtin_clz(d.s.high) - __builtin_clz(n.s.high); 19177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* 0 <= sr <= n_uword_bits - 1 or sr large */ 19277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (sr > n_uword_bits - 1) 19377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao { 19477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (rem) 19577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao *rem = n.all; 19677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao return 0; 19777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao } 19877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao ++sr; 19977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* 1 <= sr <= n_uword_bits */ 20077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* q.all = n.all << (n_udword_bits - sr); */ 20177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao q.s.low = 0; 20277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao q.s.high = n.s.low << (n_uword_bits - sr); 20377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* r.all = n.all >> sr; 20477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * if (sr < n_uword_bits) 20577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * { 20677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * r.s.high = n.s.high >> sr; 20777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr); 20877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * } 20977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * else 21077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * { 21177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * r.s.high = 0; 21277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * r.s.low = n.s.high; 21377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * } 21477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao */ 21577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao r.s.high = (n.s.high >> sr) & 21677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1)); 21777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao r.s.low = (n.s.high << (n_uword_bits - sr)) | 21877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao ((n.s.low >> sr) & 21977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao ((si_int)(sr - n_uword_bits) >> (n_uword_bits-1))); 22077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao } 22177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao } 22277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* Not a special case 22377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * q and r are initialized with: 22477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * q.all = n.all << (n_udword_bits - sr); 22577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * r.all = n.all >> sr; 22677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * 1 <= sr <= n_udword_bits - 1 22777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao */ 22877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao su_int carry = 0; 22977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao for (; sr > 0; --sr) 23077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao { 23177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* r:q = ((r:q) << 1) | carry */ 23277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao r.s.high = (r.s.high << 1) | (r.s.low >> (n_uword_bits - 1)); 23377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao r.s.low = (r.s.low << 1) | (q.s.high >> (n_uword_bits - 1)); 23477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao q.s.high = (q.s.high << 1) | (q.s.low >> (n_uword_bits - 1)); 23577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao q.s.low = (q.s.low << 1) | carry; 23677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao /* carry = 0; 23777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * if (r.all >= d.all) 23877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * { 23977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * r.all -= d.all; 24077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * carry = 1; 24177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao * } 24277ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao */ 24377ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao const di_int s = (di_int)(d.all - r.all - 1) >> (n_udword_bits - 1); 24477ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao carry = s & 1; 24577ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao r.all -= d.all & s; 24677ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao } 24777ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao q.all = (q.all << 1) | carry; 24877ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao if (rem) 24977ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao *rem = r.all; 25077ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao return q.all; 25177ed6142daed1e068fbda64405d0de9845e40e1Shih-wei Liao} 252