1use super::BigInt;
2use super::Sign::{Minus, NoSign, Plus};
3
4use crate::big_digit::{self, BigDigit, DoubleBigDigit};
5use crate::biguint::IntDigits;
6
7use alloc::vec::Vec;
8use core::cmp::Ordering::{Equal, Greater, Less};
9use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign};
10use num_traits::{ToPrimitive, Zero};
11
12// Negation in two's complement.
13// acc must be initialized as 1 for least-significant digit.
14//
15// When negating, a carry (acc == 1) means that all the digits
16// considered to this point were zero. This means that if all the
17// digits of a negative BigInt have been considered, carry must be
18// zero as we cannot have negative zero.
19//
20// 01 -> ...f ff
21// ff -> ...f 01
22// 01 00 -> ...f ff 00
23// 01 01 -> ...f fe ff
24// 01 ff -> ...f fe 01
25// ff 00 -> ...f 01 00
26// ff 01 -> ...f 00 ff
27// ff ff -> ...f 00 01
28#[inline]
29fn negate_carry(a: BigDigit, acc: &mut DoubleBigDigit) -> BigDigit {
30 *acc += DoubleBigDigit::from(!a);
31 let lo: u64 = *acc as BigDigit;
32 *acc >>= big_digit::BITS;
33 lo
34}
35
36// + 1 & -ff = ...0 01 & ...f 01 = ...0 01 = + 1
37// +ff & - 1 = ...0 ff & ...f ff = ...0 ff = +ff
38// answer is pos, has length of a
39fn bitand_pos_neg(a: &mut [BigDigit], b: &[BigDigit]) {
40 let mut carry_b: u128 = 1;
41 for (ai: &mut u64, &bi: u64) in a.iter_mut().zip(b.iter()) {
42 let twos_b: u64 = negate_carry(a:bi, &mut carry_b);
43 *ai &= twos_b;
44 }
45 debug_assert!(b.len() > a.len() || carry_b == 0);
46}
47
48// - 1 & +ff = ...f ff & ...0 ff = ...0 ff = +ff
49// -ff & + 1 = ...f 01 & ...0 01 = ...0 01 = + 1
50// answer is pos, has length of b
51fn bitand_neg_pos(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
52 let mut carry_a: u128 = 1;
53 for (ai: &mut u64, &bi: u64) in a.iter_mut().zip(b.iter()) {
54 let twos_a: u64 = negate_carry(*ai, &mut carry_a);
55 *ai = twos_a & bi;
56 }
57 debug_assert!(a.len() > b.len() || carry_a == 0);
58 match Ord::cmp(&a.len(), &b.len()) {
59 Greater => a.truncate(b.len()),
60 Equal => {}
61 Less => {
62 let extra: &[u64] = &b[a.len()..];
63 a.extend(iter:extra.iter().cloned());
64 }
65 }
66}
67
68// - 1 & -ff = ...f ff & ...f 01 = ...f 01 = - ff
69// -ff & - 1 = ...f 01 & ...f ff = ...f 01 = - ff
70// -ff & -fe = ...f 01 & ...f 02 = ...f 00 = -100
71// answer is neg, has length of longest with a possible carry
72fn bitand_neg_neg(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
73 let mut carry_a = 1;
74 let mut carry_b = 1;
75 let mut carry_and = 1;
76 for (ai, &bi) in a.iter_mut().zip(b.iter()) {
77 let twos_a = negate_carry(*ai, &mut carry_a);
78 let twos_b = negate_carry(bi, &mut carry_b);
79 *ai = negate_carry(twos_a & twos_b, &mut carry_and);
80 }
81 debug_assert!(a.len() > b.len() || carry_a == 0);
82 debug_assert!(b.len() > a.len() || carry_b == 0);
83 match Ord::cmp(&a.len(), &b.len()) {
84 Greater => {
85 for ai in a[b.len()..].iter_mut() {
86 let twos_a = negate_carry(*ai, &mut carry_a);
87 *ai = negate_carry(twos_a, &mut carry_and);
88 }
89 debug_assert!(carry_a == 0);
90 }
91 Equal => {}
92 Less => {
93 let extra = &b[a.len()..];
94 a.extend(extra.iter().map(|&bi| {
95 let twos_b = negate_carry(bi, &mut carry_b);
96 negate_carry(twos_b, &mut carry_and)
97 }));
98 debug_assert!(carry_b == 0);
99 }
100 }
101 if carry_and != 0 {
102 a.push(1);
103 }
104}
105
106forward_val_val_binop!(impl BitAnd for BigInt, bitand);
107forward_ref_val_binop!(impl BitAnd for BigInt, bitand);
108
109// do not use forward_ref_ref_binop_commutative! for bitand so that we can
110// clone as needed, avoiding over-allocation
111impl BitAnd<&BigInt> for &BigInt {
112 type Output = BigInt;
113
114 #[inline]
115 fn bitand(self, other: &BigInt) -> BigInt {
116 match (self.sign, other.sign) {
117 (NoSign, _) | (_, NoSign) => BigInt::ZERO,
118 (Plus, Plus) => BigInt::from(&self.data & &other.data),
119 (Plus, Minus) => self.clone() & other,
120 (Minus, Plus) => other.clone() & self,
121 (Minus, Minus) => {
122 // forward to val-ref, choosing the larger to clone
123 if self.len() >= other.len() {
124 self.clone() & other
125 } else {
126 other.clone() & self
127 }
128 }
129 }
130 }
131}
132
133impl BitAnd<&BigInt> for BigInt {
134 type Output = BigInt;
135
136 #[inline]
137 fn bitand(mut self, other: &BigInt) -> BigInt {
138 self &= other;
139 self
140 }
141}
142
143forward_val_assign!(impl BitAndAssign for BigInt, bitand_assign);
144
145impl BitAndAssign<&BigInt> for BigInt {
146 fn bitand_assign(&mut self, other: &BigInt) {
147 match (self.sign, other.sign) {
148 (NoSign, _) => {}
149 (_, NoSign) => self.set_zero(),
150 (Plus, Plus) => {
151 self.data &= &other.data;
152 if self.data.is_zero() {
153 self.sign = NoSign;
154 }
155 }
156 (Plus, Minus) => {
157 bitand_pos_neg(self.digits_mut(), other.digits());
158 self.normalize();
159 }
160 (Minus, Plus) => {
161 bitand_neg_pos(self.digits_mut(), other.digits());
162 self.sign = Plus;
163 self.normalize();
164 }
165 (Minus, Minus) => {
166 bitand_neg_neg(self.digits_mut(), other.digits());
167 self.normalize();
168 }
169 }
170 }
171}
172
173// + 1 | -ff = ...0 01 | ...f 01 = ...f 01 = -ff
174// +ff | - 1 = ...0 ff | ...f ff = ...f ff = - 1
175// answer is neg, has length of b
176fn bitor_pos_neg(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
177 let mut carry_b = 1;
178 let mut carry_or = 1;
179 for (ai, &bi) in a.iter_mut().zip(b.iter()) {
180 let twos_b = negate_carry(bi, &mut carry_b);
181 *ai = negate_carry(*ai | twos_b, &mut carry_or);
182 }
183 debug_assert!(b.len() > a.len() || carry_b == 0);
184 match Ord::cmp(&a.len(), &b.len()) {
185 Greater => {
186 a.truncate(b.len());
187 }
188 Equal => {}
189 Less => {
190 let extra = &b[a.len()..];
191 a.extend(extra.iter().map(|&bi| {
192 let twos_b = negate_carry(bi, &mut carry_b);
193 negate_carry(twos_b, &mut carry_or)
194 }));
195 debug_assert!(carry_b == 0);
196 }
197 }
198 // for carry_or to be non-zero, we would need twos_b == 0
199 debug_assert!(carry_or == 0);
200}
201
202// - 1 | +ff = ...f ff | ...0 ff = ...f ff = - 1
203// -ff | + 1 = ...f 01 | ...0 01 = ...f 01 = -ff
204// answer is neg, has length of a
205fn bitor_neg_pos(a: &mut [BigDigit], b: &[BigDigit]) {
206 let mut carry_a: u128 = 1;
207 let mut carry_or: u128 = 1;
208 for (ai: &mut u64, &bi: u64) in a.iter_mut().zip(b.iter()) {
209 let twos_a: u64 = negate_carry(*ai, &mut carry_a);
210 *ai = negate_carry(a:twos_a | bi, &mut carry_or);
211 }
212 debug_assert!(a.len() > b.len() || carry_a == 0);
213 if a.len() > b.len() {
214 for ai: &mut u64 in a[b.len()..].iter_mut() {
215 let twos_a: u64 = negate_carry(*ai, &mut carry_a);
216 *ai = negate_carry(twos_a, &mut carry_or);
217 }
218 debug_assert!(carry_a == 0);
219 }
220 // for carry_or to be non-zero, we would need twos_a == 0
221 debug_assert!(carry_or == 0);
222}
223
224// - 1 | -ff = ...f ff | ...f 01 = ...f ff = -1
225// -ff | - 1 = ...f 01 | ...f ff = ...f ff = -1
226// answer is neg, has length of shortest
227fn bitor_neg_neg(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
228 let mut carry_a: u128 = 1;
229 let mut carry_b: u128 = 1;
230 let mut carry_or: u128 = 1;
231 for (ai: &mut u64, &bi: u64) in a.iter_mut().zip(b.iter()) {
232 let twos_a: u64 = negate_carry(*ai, &mut carry_a);
233 let twos_b: u64 = negate_carry(a:bi, &mut carry_b);
234 *ai = negate_carry(a:twos_a | twos_b, &mut carry_or);
235 }
236 debug_assert!(a.len() > b.len() || carry_a == 0);
237 debug_assert!(b.len() > a.len() || carry_b == 0);
238 if a.len() > b.len() {
239 a.truncate(b.len());
240 }
241 // for carry_or to be non-zero, we would need twos_a == 0 or twos_b == 0
242 debug_assert!(carry_or == 0);
243}
244
245forward_val_val_binop!(impl BitOr for BigInt, bitor);
246forward_ref_val_binop!(impl BitOr for BigInt, bitor);
247
248// do not use forward_ref_ref_binop_commutative! for bitor so that we can
249// clone as needed, avoiding over-allocation
250impl BitOr<&BigInt> for &BigInt {
251 type Output = BigInt;
252
253 #[inline]
254 fn bitor(self, other: &BigInt) -> BigInt {
255 match (self.sign, other.sign) {
256 (NoSign, _) => other.clone(),
257 (_, NoSign) => self.clone(),
258 (Plus, Plus) => BigInt::from(&self.data | &other.data),
259 (Plus, Minus) => other.clone() | self,
260 (Minus, Plus) => self.clone() | other,
261 (Minus, Minus) => {
262 // forward to val-ref, choosing the smaller to clone
263 if self.len() <= other.len() {
264 self.clone() | other
265 } else {
266 other.clone() | self
267 }
268 }
269 }
270 }
271}
272
273impl BitOr<&BigInt> for BigInt {
274 type Output = BigInt;
275
276 #[inline]
277 fn bitor(mut self, other: &BigInt) -> BigInt {
278 self |= other;
279 self
280 }
281}
282
283forward_val_assign!(impl BitOrAssign for BigInt, bitor_assign);
284
285impl BitOrAssign<&BigInt> for BigInt {
286 fn bitor_assign(&mut self, other: &BigInt) {
287 match (self.sign, other.sign) {
288 (_, NoSign) => {}
289 (NoSign, _) => self.clone_from(source:other),
290 (Plus, Plus) => self.data |= &other.data,
291 (Plus, Minus) => {
292 bitor_pos_neg(self.digits_mut(), b:other.digits());
293 self.sign = Minus;
294 self.normalize();
295 }
296 (Minus, Plus) => {
297 bitor_neg_pos(self.digits_mut(), b:other.digits());
298 self.normalize();
299 }
300 (Minus, Minus) => {
301 bitor_neg_neg(self.digits_mut(), b:other.digits());
302 self.normalize();
303 }
304 }
305 }
306}
307
308// + 1 ^ -ff = ...0 01 ^ ...f 01 = ...f 00 = -100
309// +ff ^ - 1 = ...0 ff ^ ...f ff = ...f 00 = -100
310// answer is neg, has length of longest with a possible carry
311fn bitxor_pos_neg(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
312 let mut carry_b = 1;
313 let mut carry_xor = 1;
314 for (ai, &bi) in a.iter_mut().zip(b.iter()) {
315 let twos_b = negate_carry(bi, &mut carry_b);
316 *ai = negate_carry(*ai ^ twos_b, &mut carry_xor);
317 }
318 debug_assert!(b.len() > a.len() || carry_b == 0);
319 match Ord::cmp(&a.len(), &b.len()) {
320 Greater => {
321 for ai in a[b.len()..].iter_mut() {
322 let twos_b = !0;
323 *ai = negate_carry(*ai ^ twos_b, &mut carry_xor);
324 }
325 }
326 Equal => {}
327 Less => {
328 let extra = &b[a.len()..];
329 a.extend(extra.iter().map(|&bi| {
330 let twos_b = negate_carry(bi, &mut carry_b);
331 negate_carry(twos_b, &mut carry_xor)
332 }));
333 debug_assert!(carry_b == 0);
334 }
335 }
336 if carry_xor != 0 {
337 a.push(1);
338 }
339}
340
341// - 1 ^ +ff = ...f ff ^ ...0 ff = ...f 00 = -100
342// -ff ^ + 1 = ...f 01 ^ ...0 01 = ...f 00 = -100
343// answer is neg, has length of longest with a possible carry
344fn bitxor_neg_pos(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
345 let mut carry_a = 1;
346 let mut carry_xor = 1;
347 for (ai, &bi) in a.iter_mut().zip(b.iter()) {
348 let twos_a = negate_carry(*ai, &mut carry_a);
349 *ai = negate_carry(twos_a ^ bi, &mut carry_xor);
350 }
351 debug_assert!(a.len() > b.len() || carry_a == 0);
352 match Ord::cmp(&a.len(), &b.len()) {
353 Greater => {
354 for ai in a[b.len()..].iter_mut() {
355 let twos_a = negate_carry(*ai, &mut carry_a);
356 *ai = negate_carry(twos_a, &mut carry_xor);
357 }
358 debug_assert!(carry_a == 0);
359 }
360 Equal => {}
361 Less => {
362 let extra = &b[a.len()..];
363 a.extend(extra.iter().map(|&bi| {
364 let twos_a = !0;
365 negate_carry(twos_a ^ bi, &mut carry_xor)
366 }));
367 }
368 }
369 if carry_xor != 0 {
370 a.push(1);
371 }
372}
373
374// - 1 ^ -ff = ...f ff ^ ...f 01 = ...0 fe = +fe
375// -ff & - 1 = ...f 01 ^ ...f ff = ...0 fe = +fe
376// answer is pos, has length of longest
377fn bitxor_neg_neg(a: &mut Vec<BigDigit>, b: &[BigDigit]) {
378 let mut carry_a = 1;
379 let mut carry_b = 1;
380 for (ai, &bi) in a.iter_mut().zip(b.iter()) {
381 let twos_a = negate_carry(*ai, &mut carry_a);
382 let twos_b = negate_carry(bi, &mut carry_b);
383 *ai = twos_a ^ twos_b;
384 }
385 debug_assert!(a.len() > b.len() || carry_a == 0);
386 debug_assert!(b.len() > a.len() || carry_b == 0);
387 match Ord::cmp(&a.len(), &b.len()) {
388 Greater => {
389 for ai in a[b.len()..].iter_mut() {
390 let twos_a = negate_carry(*ai, &mut carry_a);
391 let twos_b = !0;
392 *ai = twos_a ^ twos_b;
393 }
394 debug_assert!(carry_a == 0);
395 }
396 Equal => {}
397 Less => {
398 let extra = &b[a.len()..];
399 a.extend(extra.iter().map(|&bi| {
400 let twos_a = !0;
401 let twos_b = negate_carry(bi, &mut carry_b);
402 twos_a ^ twos_b
403 }));
404 debug_assert!(carry_b == 0);
405 }
406 }
407}
408
409forward_all_binop_to_val_ref_commutative!(impl BitXor for BigInt, bitxor);
410
411impl BitXor<&BigInt> for BigInt {
412 type Output = BigInt;
413
414 #[inline]
415 fn bitxor(mut self, other: &BigInt) -> BigInt {
416 self ^= other;
417 self
418 }
419}
420
421forward_val_assign!(impl BitXorAssign for BigInt, bitxor_assign);
422
423impl BitXorAssign<&BigInt> for BigInt {
424 fn bitxor_assign(&mut self, other: &BigInt) {
425 match (self.sign, other.sign) {
426 (_, NoSign) => {}
427 (NoSign, _) => self.clone_from(other),
428 (Plus, Plus) => {
429 self.data ^= &other.data;
430 if self.data.is_zero() {
431 self.sign = NoSign;
432 }
433 }
434 (Plus, Minus) => {
435 bitxor_pos_neg(self.digits_mut(), other.digits());
436 self.sign = Minus;
437 self.normalize();
438 }
439 (Minus, Plus) => {
440 bitxor_neg_pos(self.digits_mut(), other.digits());
441 self.normalize();
442 }
443 (Minus, Minus) => {
444 bitxor_neg_neg(self.digits_mut(), other.digits());
445 self.sign = Plus;
446 self.normalize();
447 }
448 }
449 }
450}
451
452pub(super) fn set_negative_bit(x: &mut BigInt, bit: u64, value: bool) {
453 debug_assert_eq!(x.sign, Minus);
454 let data = &mut x.data;
455
456 let bits_per_digit = u64::from(big_digit::BITS);
457 if bit >= bits_per_digit * data.len() as u64 {
458 if !value {
459 data.set_bit(bit, true);
460 }
461 } else {
462 // If the Uint number is
463 // ... 0 x 1 0 ... 0
464 // then the two's complement is
465 // ... 1 !x 1 0 ... 0
466 // |-- bit at position 'trailing_zeros'
467 // where !x is obtained from x by flipping each bit
468 let trailing_zeros = data.trailing_zeros().unwrap();
469 if bit > trailing_zeros {
470 data.set_bit(bit, !value);
471 } else if bit == trailing_zeros && !value {
472 // Clearing the bit at position `trailing_zeros` is dealt with by doing
473 // similarly to what `bitand_neg_pos` does, except we start at digit
474 // `bit_index`. All digits below `bit_index` are guaranteed to be zero,
475 // so initially we have `carry_in` = `carry_out` = 1. Furthermore, we
476 // stop traversing the digits when there are no more carries.
477 let bit_index = (bit / bits_per_digit).to_usize().unwrap();
478 let bit_mask = (1 as BigDigit) << (bit % bits_per_digit);
479 let mut digit_iter = data.digits_mut().iter_mut().skip(bit_index);
480 let mut carry_in = 1;
481 let mut carry_out = 1;
482
483 let digit = digit_iter.next().unwrap();
484 let twos_in = negate_carry(*digit, &mut carry_in);
485 let twos_out = twos_in & !bit_mask;
486 *digit = negate_carry(twos_out, &mut carry_out);
487
488 for digit in digit_iter {
489 if carry_in == 0 && carry_out == 0 {
490 // Exit the loop since no more digits can change
491 break;
492 }
493 let twos = negate_carry(*digit, &mut carry_in);
494 *digit = negate_carry(twos, &mut carry_out);
495 }
496
497 if carry_out != 0 {
498 // All digits have been traversed and there is a carry
499 debug_assert_eq!(carry_in, 0);
500 data.digits_mut().push(1);
501 }
502 } else if bit < trailing_zeros && value {
503 // Flip each bit from position 'bit' to 'trailing_zeros', both inclusive
504 // ... 1 !x 1 0 ... 0 ... 0
505 // |-- bit at position 'bit'
506 // |-- bit at position 'trailing_zeros'
507 // bit_mask: 1 1 ... 1 0 .. 0
508 // This is done by xor'ing with the bit_mask
509 let index_lo = (bit / bits_per_digit).to_usize().unwrap();
510 let index_hi = (trailing_zeros / bits_per_digit).to_usize().unwrap();
511 let bit_mask_lo = big_digit::MAX << (bit % bits_per_digit);
512 let bit_mask_hi =
513 big_digit::MAX >> (bits_per_digit - 1 - (trailing_zeros % bits_per_digit));
514 let digits = data.digits_mut();
515
516 if index_lo == index_hi {
517 digits[index_lo] ^= bit_mask_lo & bit_mask_hi;
518 } else {
519 digits[index_lo] = bit_mask_lo;
520 for digit in &mut digits[index_lo + 1..index_hi] {
521 *digit = big_digit::MAX;
522 }
523 digits[index_hi] ^= bit_mask_hi;
524 }
525 } else {
526 // We end up here in two cases:
527 // bit == trailing_zeros && value: Bit is already set
528 // bit < trailing_zeros && !value: Bit is already cleared
529 }
530 }
531}
532