1 | use core::ops::{BitAnd, BitOr, BitXor, Not, Shl, Shr}; |
---|---|

2 | |

3 | use crate::bounds::Bounded; |

4 | use crate::ops::checked::*; |

5 | use crate::ops::saturating::Saturating; |

6 | use crate::{Num, NumCast}; |

7 | |

8 | /// Generic trait for primitive integers. |

9 | /// |

10 | /// The `PrimInt` trait is an abstraction over the builtin primitive integer types (e.g., `u8`, |

11 | /// `u32`, `isize`, `i128`, ...). It inherits the basic numeric traits and extends them with |

12 | /// bitwise operators and non-wrapping arithmetic. |

13 | /// |

14 | /// The trait explicitly inherits `Copy`, `Eq`, `Ord`, and `Sized`. The intention is that all |

15 | /// types implementing this trait behave like primitive types that are passed by value by default |

16 | /// and behave like builtin integers. Furthermore, the types are expected to expose the integer |

17 | /// value in binary representation and support bitwise operators. The standard bitwise operations |

18 | /// (e.g., bitwise-and, bitwise-or, right-shift, left-shift) are inherited and the trait extends |

19 | /// these with introspective queries (e.g., `PrimInt::count_ones()`, `PrimInt::leading_zeros()`), |

20 | /// bitwise combinators (e.g., `PrimInt::rotate_left()`), and endianness converters (e.g., |

21 | /// `PrimInt::to_be()`). |

22 | /// |

23 | /// All `PrimInt` types are expected to be fixed-width binary integers. The width can be queried |

24 | /// via `T::zero().count_zeros()`. The trait currently lacks a way to query the width at |

25 | /// compile-time. |

26 | /// |

27 | /// While a default implementation for all builtin primitive integers is provided, the trait is in |

28 | /// no way restricted to these. Other integer types that fulfil the requirements are free to |

29 | /// implement the trait was well. |

30 | /// |

31 | /// This trait and many of the method names originate in the unstable `core::num::Int` trait from |

32 | /// the rust standard library. The original trait was never stabilized and thus removed from the |

33 | /// standard library. |

34 | pub trait PrimInt: |

35 | Sized |

36 | + Copy |

37 | + Num |

38 | + NumCast |

39 | + Bounded |

40 | + PartialOrd |

41 | + Ord |

42 | + Eq |

43 | + Not<Output = Self> |

44 | + BitAnd<Output = Self> |

45 | + BitOr<Output = Self> |

46 | + BitXor<Output = Self> |

47 | + Shl<usize, Output = Self> |

48 | + Shr<usize, Output = Self> |

49 | + CheckedAdd<Output = Self> |

50 | + CheckedSub<Output = Self> |

51 | + CheckedMul<Output = Self> |

52 | + CheckedDiv<Output = Self> |

53 | + Saturating |

54 | { |

55 | /// Returns the number of ones in the binary representation of `self`. |

56 | /// |

57 | /// # Examples |

58 | /// |

59 | /// ``` |

60 | /// use num_traits::PrimInt; |

61 | /// |

62 | /// let n = 0b01001100u8; |

63 | /// |

64 | /// assert_eq!(n.count_ones(), 3); |

65 | /// ``` |

66 | fn count_ones(self) -> u32; |

67 | |

68 | /// Returns the number of zeros in the binary representation of `self`. |

69 | /// |

70 | /// # Examples |

71 | /// |

72 | /// ``` |

73 | /// use num_traits::PrimInt; |

74 | /// |

75 | /// let n = 0b01001100u8; |

76 | /// |

77 | /// assert_eq!(n.count_zeros(), 5); |

78 | /// ``` |

79 | fn count_zeros(self) -> u32; |

80 | |

81 | /// Returns the number of leading ones in the binary representation |

82 | /// of `self`. |

83 | /// |

84 | /// # Examples |

85 | /// |

86 | /// ``` |

87 | /// use num_traits::PrimInt; |

88 | /// |

89 | /// let n = 0xF00Du16; |

90 | /// |

91 | /// assert_eq!(n.leading_ones(), 4); |

92 | /// ``` |

93 | fn leading_ones(self) -> u32 { |

94 | (!self).leading_zeros() |

95 | } |

96 | |

97 | /// Returns the number of leading zeros in the binary representation |

98 | /// of `self`. |

99 | /// |

100 | /// # Examples |

101 | /// |

102 | /// ``` |

103 | /// use num_traits::PrimInt; |

104 | /// |

105 | /// let n = 0b0101000u16; |

106 | /// |

107 | /// assert_eq!(n.leading_zeros(), 10); |

108 | /// ``` |

109 | fn leading_zeros(self) -> u32; |

110 | |

111 | /// Returns the number of trailing ones in the binary representation |

112 | /// of `self`. |

113 | /// |

114 | /// # Examples |

115 | /// |

116 | /// ``` |

117 | /// use num_traits::PrimInt; |

118 | /// |

119 | /// let n = 0xBEEFu16; |

120 | /// |

121 | /// assert_eq!(n.trailing_ones(), 4); |

122 | /// ``` |

123 | fn trailing_ones(self) -> u32 { |

124 | (!self).trailing_zeros() |

125 | } |

126 | |

127 | /// Returns the number of trailing zeros in the binary representation |

128 | /// of `self`. |

129 | /// |

130 | /// # Examples |

131 | /// |

132 | /// ``` |

133 | /// use num_traits::PrimInt; |

134 | /// |

135 | /// let n = 0b0101000u16; |

136 | /// |

137 | /// assert_eq!(n.trailing_zeros(), 3); |

138 | /// ``` |

139 | fn trailing_zeros(self) -> u32; |

140 | |

141 | /// Shifts the bits to the left by a specified amount, `n`, wrapping |

142 | /// the truncated bits to the end of the resulting integer. |

143 | /// |

144 | /// # Examples |

145 | /// |

146 | /// ``` |

147 | /// use num_traits::PrimInt; |

148 | /// |

149 | /// let n = 0x0123456789ABCDEFu64; |

150 | /// let m = 0x3456789ABCDEF012u64; |

151 | /// |

152 | /// assert_eq!(n.rotate_left(12), m); |

153 | /// ``` |

154 | fn rotate_left(self, n: u32) -> Self; |

155 | |

156 | /// Shifts the bits to the right by a specified amount, `n`, wrapping |

157 | /// the truncated bits to the beginning of the resulting integer. |

158 | /// |

159 | /// # Examples |

160 | /// |

161 | /// ``` |

162 | /// use num_traits::PrimInt; |

163 | /// |

164 | /// let n = 0x0123456789ABCDEFu64; |

165 | /// let m = 0xDEF0123456789ABCu64; |

166 | /// |

167 | /// assert_eq!(n.rotate_right(12), m); |

168 | /// ``` |

169 | fn rotate_right(self, n: u32) -> Self; |

170 | |

171 | /// Shifts the bits to the left by a specified amount, `n`, filling |

172 | /// zeros in the least significant bits. |

173 | /// |

174 | /// This is bitwise equivalent to signed `Shl`. |

175 | /// |

176 | /// # Examples |

177 | /// |

178 | /// ``` |

179 | /// use num_traits::PrimInt; |

180 | /// |

181 | /// let n = 0x0123456789ABCDEFu64; |

182 | /// let m = 0x3456789ABCDEF000u64; |

183 | /// |

184 | /// assert_eq!(n.signed_shl(12), m); |

185 | /// ``` |

186 | fn signed_shl(self, n: u32) -> Self; |

187 | |

188 | /// Shifts the bits to the right by a specified amount, `n`, copying |

189 | /// the "sign bit" in the most significant bits even for unsigned types. |

190 | /// |

191 | /// This is bitwise equivalent to signed `Shr`. |

192 | /// |

193 | /// # Examples |

194 | /// |

195 | /// ``` |

196 | /// use num_traits::PrimInt; |

197 | /// |

198 | /// let n = 0xFEDCBA9876543210u64; |

199 | /// let m = 0xFFFFEDCBA9876543u64; |

200 | /// |

201 | /// assert_eq!(n.signed_shr(12), m); |

202 | /// ``` |

203 | fn signed_shr(self, n: u32) -> Self; |

204 | |

205 | /// Shifts the bits to the left by a specified amount, `n`, filling |

206 | /// zeros in the least significant bits. |

207 | /// |

208 | /// This is bitwise equivalent to unsigned `Shl`. |

209 | /// |

210 | /// # Examples |

211 | /// |

212 | /// ``` |

213 | /// use num_traits::PrimInt; |

214 | /// |

215 | /// let n = 0x0123456789ABCDEFi64; |

216 | /// let m = 0x3456789ABCDEF000i64; |

217 | /// |

218 | /// assert_eq!(n.unsigned_shl(12), m); |

219 | /// ``` |

220 | fn unsigned_shl(self, n: u32) -> Self; |

221 | |

222 | /// Shifts the bits to the right by a specified amount, `n`, filling |

223 | /// zeros in the most significant bits. |

224 | /// |

225 | /// This is bitwise equivalent to unsigned `Shr`. |

226 | /// |

227 | /// # Examples |

228 | /// |

229 | /// ``` |

230 | /// use num_traits::PrimInt; |

231 | /// |

232 | /// let n = -8i8; // 0b11111000 |

233 | /// let m = 62i8; // 0b00111110 |

234 | /// |

235 | /// assert_eq!(n.unsigned_shr(2), m); |

236 | /// ``` |

237 | fn unsigned_shr(self, n: u32) -> Self; |

238 | |

239 | /// Reverses the byte order of the integer. |

240 | /// |

241 | /// # Examples |

242 | /// |

243 | /// ``` |

244 | /// use num_traits::PrimInt; |

245 | /// |

246 | /// let n = 0x0123456789ABCDEFu64; |

247 | /// let m = 0xEFCDAB8967452301u64; |

248 | /// |

249 | /// assert_eq!(n.swap_bytes(), m); |

250 | /// ``` |

251 | fn swap_bytes(self) -> Self; |

252 | |

253 | /// Reverses the order of bits in the integer. |

254 | /// |

255 | /// The least significant bit becomes the most significant bit, second least-significant bit |

256 | /// becomes second most-significant bit, etc. |

257 | /// |

258 | /// # Examples |

259 | /// |

260 | /// ``` |

261 | /// use num_traits::PrimInt; |

262 | /// |

263 | /// let n = 0x12345678u32; |

264 | /// let m = 0x1e6a2c48u32; |

265 | /// |

266 | /// assert_eq!(n.reverse_bits(), m); |

267 | /// assert_eq!(0u32.reverse_bits(), 0); |

268 | /// ``` |

269 | fn reverse_bits(self) -> Self { |

270 | reverse_bits_fallback(self) |

271 | } |

272 | |

273 | /// Convert an integer from big endian to the target's endianness. |

274 | /// |

275 | /// On big endian this is a no-op. On little endian the bytes are swapped. |

276 | /// |

277 | /// # Examples |

278 | /// |

279 | /// ``` |

280 | /// use num_traits::PrimInt; |

281 | /// |

282 | /// let n = 0x0123456789ABCDEFu64; |

283 | /// |

284 | /// if cfg!(target_endian = "big") { |

285 | /// assert_eq!(u64::from_be(n), n) |

286 | /// } else { |

287 | /// assert_eq!(u64::from_be(n), n.swap_bytes()) |

288 | /// } |

289 | /// ``` |

290 | fn from_be(x: Self) -> Self; |

291 | |

292 | /// Convert an integer from little endian to the target's endianness. |

293 | /// |

294 | /// On little endian this is a no-op. On big endian the bytes are swapped. |

295 | /// |

296 | /// # Examples |

297 | /// |

298 | /// ``` |

299 | /// use num_traits::PrimInt; |

300 | /// |

301 | /// let n = 0x0123456789ABCDEFu64; |

302 | /// |

303 | /// if cfg!(target_endian = "little") { |

304 | /// assert_eq!(u64::from_le(n), n) |

305 | /// } else { |

306 | /// assert_eq!(u64::from_le(n), n.swap_bytes()) |

307 | /// } |

308 | /// ``` |

309 | fn from_le(x: Self) -> Self; |

310 | |

311 | /// Convert `self` to big endian from the target's endianness. |

312 | /// |

313 | /// On big endian this is a no-op. On little endian the bytes are swapped. |

314 | /// |

315 | /// # Examples |

316 | /// |

317 | /// ``` |

318 | /// use num_traits::PrimInt; |

319 | /// |

320 | /// let n = 0x0123456789ABCDEFu64; |

321 | /// |

322 | /// if cfg!(target_endian = "big") { |

323 | /// assert_eq!(n.to_be(), n) |

324 | /// } else { |

325 | /// assert_eq!(n.to_be(), n.swap_bytes()) |

326 | /// } |

327 | /// ``` |

328 | fn to_be(self) -> Self; |

329 | |

330 | /// Convert `self` to little endian from the target's endianness. |

331 | /// |

332 | /// On little endian this is a no-op. On big endian the bytes are swapped. |

333 | /// |

334 | /// # Examples |

335 | /// |

336 | /// ``` |

337 | /// use num_traits::PrimInt; |

338 | /// |

339 | /// let n = 0x0123456789ABCDEFu64; |

340 | /// |

341 | /// if cfg!(target_endian = "little") { |

342 | /// assert_eq!(n.to_le(), n) |

343 | /// } else { |

344 | /// assert_eq!(n.to_le(), n.swap_bytes()) |

345 | /// } |

346 | /// ``` |

347 | fn to_le(self) -> Self; |

348 | |

349 | /// Raises self to the power of `exp`, using exponentiation by squaring. |

350 | /// |

351 | /// # Examples |

352 | /// |

353 | /// ``` |

354 | /// use num_traits::PrimInt; |

355 | /// |

356 | /// assert_eq!(2i32.pow(4), 16); |

357 | /// ``` |

358 | fn pow(self, exp: u32) -> Self; |

359 | } |

360 | |

361 | fn one_per_byte<P: PrimInt>() -> P { |

362 | // i8, u8: return 0x01 |

363 | // i16, u16: return 0x0101 = (0x01 << 8) | 0x01 |

364 | // i32, u32: return 0x01010101 = (0x0101 << 16) | 0x0101 |

365 | // ... |

366 | let mut ret = P::one(); |

367 | let mut shift = 8; |

368 | let mut b = ret.count_zeros() >> 3; |

369 | while b != 0 { |

370 | ret = (ret << shift) | ret; |

371 | shift <<= 1; |

372 | b >>= 1; |

373 | } |

374 | ret |

375 | } |

376 | |

377 | fn reverse_bits_fallback<P: PrimInt>(i: P) -> P { |

378 | let rep_01: P = one_per_byte(); |

379 | let rep_03 = (rep_01 << 1) | rep_01; |

380 | let rep_05 = (rep_01 << 2) | rep_01; |

381 | let rep_0f = (rep_03 << 2) | rep_03; |

382 | let rep_33 = (rep_03 << 4) | rep_03; |

383 | let rep_55 = (rep_05 << 4) | rep_05; |

384 | |

385 | // code above only used to determine rep_0f, rep_33, rep_55; |

386 | // optimizer should be able to do it in compile time |

387 | let mut ret = i.swap_bytes(); |

388 | ret = ((ret & rep_0f) << 4) | ((ret >> 4) & rep_0f); |

389 | ret = ((ret & rep_33) << 2) | ((ret >> 2) & rep_33); |

390 | ret = ((ret & rep_55) << 1) | ((ret >> 1) & rep_55); |

391 | ret |

392 | } |

393 | |

394 | macro_rules! prim_int_impl { |

395 | ($T:ty, $S:ty, $U:ty) => { |

396 | impl PrimInt for $T { |

397 | #[inline] |

398 | fn count_ones(self) -> u32 { |

399 | <$T>::count_ones(self) |

400 | } |

401 | |

402 | #[inline] |

403 | fn count_zeros(self) -> u32 { |

404 | <$T>::count_zeros(self) |

405 | } |

406 | |

407 | #[cfg(has_leading_trailing_ones)] |

408 | #[inline] |

409 | fn leading_ones(self) -> u32 { |

410 | <$T>::leading_ones(self) |

411 | } |

412 | |

413 | #[inline] |

414 | fn leading_zeros(self) -> u32 { |

415 | <$T>::leading_zeros(self) |

416 | } |

417 | |

418 | #[cfg(has_leading_trailing_ones)] |

419 | #[inline] |

420 | fn trailing_ones(self) -> u32 { |

421 | <$T>::trailing_ones(self) |

422 | } |

423 | |

424 | #[inline] |

425 | fn trailing_zeros(self) -> u32 { |

426 | <$T>::trailing_zeros(self) |

427 | } |

428 | |

429 | #[inline] |

430 | fn rotate_left(self, n: u32) -> Self { |

431 | <$T>::rotate_left(self, n) |

432 | } |

433 | |

434 | #[inline] |

435 | fn rotate_right(self, n: u32) -> Self { |

436 | <$T>::rotate_right(self, n) |

437 | } |

438 | |

439 | #[inline] |

440 | fn signed_shl(self, n: u32) -> Self { |

441 | ((self as $S) << n) as $T |

442 | } |

443 | |

444 | #[inline] |

445 | fn signed_shr(self, n: u32) -> Self { |

446 | ((self as $S) >> n) as $T |

447 | } |

448 | |

449 | #[inline] |

450 | fn unsigned_shl(self, n: u32) -> Self { |

451 | ((self as $U) << n) as $T |

452 | } |

453 | |

454 | #[inline] |

455 | fn unsigned_shr(self, n: u32) -> Self { |

456 | ((self as $U) >> n) as $T |

457 | } |

458 | |

459 | #[inline] |

460 | fn swap_bytes(self) -> Self { |

461 | <$T>::swap_bytes(self) |

462 | } |

463 | |

464 | #[cfg(has_reverse_bits)] |

465 | #[inline] |

466 | fn reverse_bits(self) -> Self { |

467 | <$T>::reverse_bits(self) |

468 | } |

469 | |

470 | #[inline] |

471 | fn from_be(x: Self) -> Self { |

472 | <$T>::from_be(x) |

473 | } |

474 | |

475 | #[inline] |

476 | fn from_le(x: Self) -> Self { |

477 | <$T>::from_le(x) |

478 | } |

479 | |

480 | #[inline] |

481 | fn to_be(self) -> Self { |

482 | <$T>::to_be(self) |

483 | } |

484 | |

485 | #[inline] |

486 | fn to_le(self) -> Self { |

487 | <$T>::to_le(self) |

488 | } |

489 | |

490 | #[inline] |

491 | fn pow(self, exp: u32) -> Self { |

492 | <$T>::pow(self, exp) |

493 | } |

494 | } |

495 | }; |

496 | } |

497 | |

498 | // prim_int_impl!(type, signed, unsigned); |

499 | prim_int_impl!(u8, i8, u8); |

500 | prim_int_impl!(u16, i16, u16); |

501 | prim_int_impl!(u32, i32, u32); |

502 | prim_int_impl!(u64, i64, u64); |

503 | prim_int_impl!(u128, i128, u128); |

504 | prim_int_impl!(usize, isize, usize); |

505 | prim_int_impl!(i8, i8, u8); |

506 | prim_int_impl!(i16, i16, u16); |

507 | prim_int_impl!(i32, i32, u32); |

508 | prim_int_impl!(i64, i64, u64); |

509 | prim_int_impl!(i128, i128, u128); |

510 | prim_int_impl!(isize, isize, usize); |

511 | |

512 | #[cfg(test)] |

513 | mod tests { |

514 | use crate::int::PrimInt; |

515 | |

516 | #[test] |

517 | pub fn reverse_bits() { |

518 | use core::{i16, i32, i64, i8}; |

519 | |

520 | assert_eq!( |

521 | PrimInt::reverse_bits(0x0123_4567_89ab_cdefu64), |

522 | 0xf7b3_d591_e6a2_c480 |

523 | ); |

524 | |

525 | assert_eq!(PrimInt::reverse_bits(0i8), 0); |

526 | assert_eq!(PrimInt::reverse_bits(-1i8), -1); |

527 | assert_eq!(PrimInt::reverse_bits(1i8), i8::MIN); |

528 | assert_eq!(PrimInt::reverse_bits(i8::MIN), 1); |

529 | assert_eq!(PrimInt::reverse_bits(-2i8), i8::MAX); |

530 | assert_eq!(PrimInt::reverse_bits(i8::MAX), -2); |

531 | |

532 | assert_eq!(PrimInt::reverse_bits(0i16), 0); |

533 | assert_eq!(PrimInt::reverse_bits(-1i16), -1); |

534 | assert_eq!(PrimInt::reverse_bits(1i16), i16::MIN); |

535 | assert_eq!(PrimInt::reverse_bits(i16::MIN), 1); |

536 | assert_eq!(PrimInt::reverse_bits(-2i16), i16::MAX); |

537 | assert_eq!(PrimInt::reverse_bits(i16::MAX), -2); |

538 | |

539 | assert_eq!(PrimInt::reverse_bits(0i32), 0); |

540 | assert_eq!(PrimInt::reverse_bits(-1i32), -1); |

541 | assert_eq!(PrimInt::reverse_bits(1i32), i32::MIN); |

542 | assert_eq!(PrimInt::reverse_bits(i32::MIN), 1); |

543 | assert_eq!(PrimInt::reverse_bits(-2i32), i32::MAX); |

544 | assert_eq!(PrimInt::reverse_bits(i32::MAX), -2); |

545 | |

546 | assert_eq!(PrimInt::reverse_bits(0i64), 0); |

547 | assert_eq!(PrimInt::reverse_bits(-1i64), -1); |

548 | assert_eq!(PrimInt::reverse_bits(1i64), i64::MIN); |

549 | assert_eq!(PrimInt::reverse_bits(i64::MIN), 1); |

550 | assert_eq!(PrimInt::reverse_bits(-2i64), i64::MAX); |

551 | assert_eq!(PrimInt::reverse_bits(i64::MAX), -2); |

552 | } |

553 | |

554 | #[test] |

555 | pub fn reverse_bits_i128() { |

556 | use core::i128; |

557 | |

558 | assert_eq!(PrimInt::reverse_bits(0i128), 0); |

559 | assert_eq!(PrimInt::reverse_bits(-1i128), -1); |

560 | assert_eq!(PrimInt::reverse_bits(1i128), i128::MIN); |

561 | assert_eq!(PrimInt::reverse_bits(i128::MIN), 1); |

562 | assert_eq!(PrimInt::reverse_bits(-2i128), i128::MAX); |

563 | assert_eq!(PrimInt::reverse_bits(i128::MAX), -2); |

564 | } |

565 | } |

566 |