| 2076 | |
| 2077 | |
| 2078 | static int quorem(Bigint *b, Bigint *S) |
| 2079 | { |
| 2080 | int n; |
| 2081 | ULong *bx, *bxe, q, *sx, *sxe; |
| 2082 | ULLong borrow, carry, y, ys; |
| 2083 | |
| 2084 | n= S->wds; |
| 2085 | if (b->wds < n) |
| 2086 | return 0; |
| 2087 | sx= S->p.x; |
| 2088 | sxe= sx + --n; |
| 2089 | bx= b->p.x; |
| 2090 | bxe= bx + n; |
| 2091 | q= *bxe / (*sxe + 1); /* ensure q <= true quotient */ |
| 2092 | if (q) |
| 2093 | { |
| 2094 | borrow= 0; |
| 2095 | carry= 0; |
| 2096 | do |
| 2097 | { |
| 2098 | ys= *sx++ * (ULLong)q + carry; |
| 2099 | carry= ys >> 32; |
| 2100 | y= *bx - (ys & FFFFFFFF) - borrow; |
| 2101 | borrow= y >> 32 & (ULong)1; |
| 2102 | *bx++= (ULong) (y & FFFFFFFF); |
| 2103 | } |
| 2104 | while (sx <= sxe); |
| 2105 | if (!*bxe) |
| 2106 | { |
| 2107 | bx= b->p.x; |
| 2108 | while (--bxe > bx && !*bxe) |
| 2109 | --n; |
| 2110 | b->wds= n; |
| 2111 | } |
| 2112 | } |
| 2113 | if (cmp(b, S) >= 0) |
| 2114 | { |
| 2115 | q++; |
| 2116 | borrow= 0; |
| 2117 | carry= 0; |
| 2118 | bx= b->p.x; |
| 2119 | sx= S->p.x; |
| 2120 | do |
| 2121 | { |
| 2122 | ys= *sx++ + carry; |
| 2123 | carry= ys >> 32; |
| 2124 | y= *bx - (ys & FFFFFFFF) - borrow; |
| 2125 | borrow= y >> 32 & (ULong)1; |
| 2126 | *bx++= (ULong) (y & FFFFFFFF); |
| 2127 | } |
| 2128 | while (sx <= sxe); |
| 2129 | bx= b->p.x; |
| 2130 | bxe= bx + n; |
| 2131 | if (!*bxe) |
| 2132 | { |
| 2133 | while (--bxe > bx && !*bxe) |
| 2134 | --n; |
| 2135 | b->wds= n; |