1 // This Source Code Form is subject to the terms of the Mozilla Public 2 // License, v. 2.0. If a copy of the MPL was not distributed with this 3 // file, You can obtain one at http://mozilla.org/MPL/2.0/. 4 5 //! Helper types for chunks. 6 7 use std::fmt::Debug; 8 use std::marker::PhantomData; 9 10 use typenum::*; 11 12 // Chunk sizes 13 14 /// A trait used to decide the size of an array. 15 /// 16 /// `<N as ChunkLength<A>>::SizedType` for a type level integer N will have the 17 /// same size as `[A; N]`. 18 pub trait ChunkLength<A>: Unsigned { 19 type SizedType; 20 } 21 22 impl<A> ChunkLength<A> for UTerm { 23 type SizedType = (); 24 } 25 26 #[doc(hidden)] 27 #[allow(dead_code)] 28 pub struct SizeEven<A, B> { 29 parent1: B, 30 parent2: B, 31 _marker: PhantomData<A>, 32 } 33 34 #[doc(hidden)] 35 #[allow(dead_code)] 36 pub struct SizeOdd<A, B> { 37 parent1: B, 38 parent2: B, 39 data: A, 40 } 41 42 impl<A, N> ChunkLength<A> for UInt<N, B0> 43 where 44 N: ChunkLength<A>, 45 { 46 type SizedType = SizeEven<A, N::SizedType>; 47 } 48 49 impl<A, N> ChunkLength<A> for UInt<N, B1> 50 where 51 N: ChunkLength<A>, 52 { 53 type SizedType = SizeOdd<A, N::SizedType>; 54 } 55 56 // Bit field sizes 57 58 /// A type level number signifying the number of bits in a bitmap. 59 /// 60 /// This trait is implemented for type level numbers from `U1` to `U128`. 61 /// 62 /// # Examples 63 /// 64 /// ```rust 65 /// # #[macro_use] extern crate sized_chunks; 66 /// # extern crate typenum; 67 /// # use sized_chunks::types::Bits; 68 /// # use typenum::U10; 69 /// # fn main() { 70 /// assert_eq!( 71 /// std::mem::size_of::<<U10 as Bits>::Store>(), 72 /// std::mem::size_of::<u16>() 73 /// ); 74 /// # } 75 /// ``` 76 pub trait Bits: Unsigned { 77 /// A primitive integer type suitable for storing this many bits. 78 type Store: Default + Copy + PartialEq + Debug; 79 get(bits: &Self::Store, index: usize) -> bool80 fn get(bits: &Self::Store, index: usize) -> bool; set(bits: &mut Self::Store, index: usize, value: bool) -> bool81 fn set(bits: &mut Self::Store, index: usize, value: bool) -> bool; len(bits: &Self::Store) -> usize82 fn len(bits: &Self::Store) -> usize; first_index(bits: &Self::Store) -> Option<usize>83 fn first_index(bits: &Self::Store) -> Option<usize>; 84 } 85 86 macro_rules! bits_for { 87 ($num:ty, $result:ty) => { 88 impl Bits for $num { 89 type Store = $result; 90 91 fn get(bits: &$result, index: usize) -> bool { 92 debug_assert!(index < Self::USIZE); 93 bits & (1 << index) != 0 94 } 95 96 fn set(bits: &mut $result, index: usize, value: bool) -> bool { 97 debug_assert!(index < Self::USIZE); 98 let mask = 1 << index; 99 let prev = *bits & mask; 100 if value { 101 *bits |= mask; 102 } else { 103 *bits &= !mask; 104 } 105 prev != 0 106 } 107 108 fn len(bits: &$result) -> usize { 109 bits.count_ones() as usize 110 } 111 112 fn first_index(bits: &$result) -> Option<usize> { 113 if *bits == 0 { 114 None 115 } else { 116 Some(bits.trailing_zeros() as usize) 117 } 118 } 119 } 120 }; 121 } 122 123 macro_rules! bits_for_256 { 124 ($num:ty) => { 125 impl Bits for $num { 126 type Store = [u128; 2]; 127 128 fn get(bits: &Self::Store, index: usize) -> bool { 129 debug_assert!(index < Self::USIZE); 130 if index < 128 { 131 bits[0] & (1 << index) != 0 132 } else { 133 bits[1] & (1 << (index - 128)) != 0 134 } 135 } 136 137 fn set(bits: &mut Self::Store, index: usize, value: bool) -> bool { 138 debug_assert!(index < Self::USIZE); 139 let mask = 1 << (index & 127); 140 let bits = if index < 128 { 141 &mut bits[0] 142 } else { 143 &mut bits[1] 144 }; 145 let prev = *bits & mask; 146 if value { 147 *bits |= mask; 148 } else { 149 *bits &= !mask; 150 } 151 prev != 0 152 } 153 154 fn len(bits: &Self::Store) -> usize { 155 (bits[0].count_ones() + bits[1].count_ones()) as usize 156 } 157 158 fn first_index(bits: &Self::Store) -> Option<usize> { 159 if bits[0] == 0 { 160 if bits[1] == 0 { 161 None 162 } else { 163 Some(bits[1].trailing_zeros() as usize + 128) 164 } 165 } else { 166 Some(bits[0].trailing_zeros() as usize) 167 } 168 } 169 } 170 }; 171 } 172 173 bits_for!(U1, u8); 174 bits_for!(U2, u8); 175 bits_for!(U3, u8); 176 bits_for!(U4, u8); 177 bits_for!(U5, u8); 178 bits_for!(U6, u8); 179 bits_for!(U7, u8); 180 bits_for!(U8, u8); 181 bits_for!(U9, u16); 182 bits_for!(U10, u16); 183 bits_for!(U11, u16); 184 bits_for!(U12, u16); 185 bits_for!(U13, u16); 186 bits_for!(U14, u16); 187 bits_for!(U15, u16); 188 bits_for!(U16, u16); 189 bits_for!(U17, u32); 190 bits_for!(U18, u32); 191 bits_for!(U19, u32); 192 bits_for!(U20, u32); 193 bits_for!(U21, u32); 194 bits_for!(U22, u32); 195 bits_for!(U23, u32); 196 bits_for!(U24, u32); 197 bits_for!(U25, u32); 198 bits_for!(U26, u32); 199 bits_for!(U27, u32); 200 bits_for!(U28, u32); 201 bits_for!(U29, u32); 202 bits_for!(U30, u32); 203 bits_for!(U31, u32); 204 bits_for!(U32, u32); 205 bits_for!(U33, u64); 206 bits_for!(U34, u64); 207 bits_for!(U35, u64); 208 bits_for!(U36, u64); 209 bits_for!(U37, u64); 210 bits_for!(U38, u64); 211 bits_for!(U39, u64); 212 bits_for!(U40, u64); 213 bits_for!(U41, u64); 214 bits_for!(U42, u64); 215 bits_for!(U43, u64); 216 bits_for!(U44, u64); 217 bits_for!(U45, u64); 218 bits_for!(U46, u64); 219 bits_for!(U47, u64); 220 bits_for!(U48, u64); 221 bits_for!(U49, u64); 222 bits_for!(U50, u64); 223 bits_for!(U51, u64); 224 bits_for!(U52, u64); 225 bits_for!(U53, u64); 226 bits_for!(U54, u64); 227 bits_for!(U55, u64); 228 bits_for!(U56, u64); 229 bits_for!(U57, u64); 230 bits_for!(U58, u64); 231 bits_for!(U59, u64); 232 bits_for!(U60, u64); 233 bits_for!(U61, u64); 234 bits_for!(U62, u64); 235 bits_for!(U63, u64); 236 bits_for!(U64, u64); 237 bits_for!(U65, u128); 238 bits_for!(U66, u128); 239 bits_for!(U67, u128); 240 bits_for!(U68, u128); 241 bits_for!(U69, u128); 242 bits_for!(U70, u128); 243 bits_for!(U71, u128); 244 bits_for!(U72, u128); 245 bits_for!(U73, u128); 246 bits_for!(U74, u128); 247 bits_for!(U75, u128); 248 bits_for!(U76, u128); 249 bits_for!(U77, u128); 250 bits_for!(U78, u128); 251 bits_for!(U79, u128); 252 bits_for!(U80, u128); 253 bits_for!(U81, u128); 254 bits_for!(U82, u128); 255 bits_for!(U83, u128); 256 bits_for!(U84, u128); 257 bits_for!(U85, u128); 258 bits_for!(U86, u128); 259 bits_for!(U87, u128); 260 bits_for!(U88, u128); 261 bits_for!(U89, u128); 262 bits_for!(U90, u128); 263 bits_for!(U91, u128); 264 bits_for!(U92, u128); 265 bits_for!(U93, u128); 266 bits_for!(U94, u128); 267 bits_for!(U95, u128); 268 bits_for!(U96, u128); 269 bits_for!(U97, u128); 270 bits_for!(U98, u128); 271 bits_for!(U99, u128); 272 bits_for!(U100, u128); 273 bits_for!(U101, u128); 274 bits_for!(U102, u128); 275 bits_for!(U103, u128); 276 bits_for!(U104, u128); 277 bits_for!(U105, u128); 278 bits_for!(U106, u128); 279 bits_for!(U107, u128); 280 bits_for!(U108, u128); 281 bits_for!(U109, u128); 282 bits_for!(U110, u128); 283 bits_for!(U111, u128); 284 bits_for!(U112, u128); 285 bits_for!(U113, u128); 286 bits_for!(U114, u128); 287 bits_for!(U115, u128); 288 bits_for!(U116, u128); 289 bits_for!(U117, u128); 290 bits_for!(U118, u128); 291 bits_for!(U119, u128); 292 bits_for!(U120, u128); 293 bits_for!(U121, u128); 294 bits_for!(U122, u128); 295 bits_for!(U123, u128); 296 bits_for!(U124, u128); 297 bits_for!(U125, u128); 298 bits_for!(U126, u128); 299 bits_for!(U127, u128); 300 bits_for!(U128, u128); 301 bits_for_256!(U129); 302 bits_for_256!(U130); 303 bits_for_256!(U131); 304 bits_for_256!(U132); 305 bits_for_256!(U133); 306 bits_for_256!(U134); 307 bits_for_256!(U135); 308 bits_for_256!(U136); 309 bits_for_256!(U137); 310 bits_for_256!(U138); 311 bits_for_256!(U139); 312 bits_for_256!(U140); 313 bits_for_256!(U141); 314 bits_for_256!(U142); 315 bits_for_256!(U143); 316 bits_for_256!(U144); 317 bits_for_256!(U145); 318 bits_for_256!(U146); 319 bits_for_256!(U147); 320 bits_for_256!(U148); 321 bits_for_256!(U149); 322 bits_for_256!(U150); 323 bits_for_256!(U151); 324 bits_for_256!(U152); 325 bits_for_256!(U153); 326 bits_for_256!(U154); 327 bits_for_256!(U155); 328 bits_for_256!(U156); 329 bits_for_256!(U157); 330 bits_for_256!(U158); 331 bits_for_256!(U159); 332 bits_for_256!(U160); 333 bits_for_256!(U161); 334 bits_for_256!(U162); 335 bits_for_256!(U163); 336 bits_for_256!(U164); 337 bits_for_256!(U165); 338 bits_for_256!(U166); 339 bits_for_256!(U167); 340 bits_for_256!(U168); 341 bits_for_256!(U169); 342 bits_for_256!(U170); 343 bits_for_256!(U171); 344 bits_for_256!(U172); 345 bits_for_256!(U173); 346 bits_for_256!(U174); 347 bits_for_256!(U175); 348 bits_for_256!(U176); 349 bits_for_256!(U177); 350 bits_for_256!(U178); 351 bits_for_256!(U179); 352 bits_for_256!(U180); 353 bits_for_256!(U181); 354 bits_for_256!(U182); 355 bits_for_256!(U183); 356 bits_for_256!(U184); 357 bits_for_256!(U185); 358 bits_for_256!(U186); 359 bits_for_256!(U187); 360 bits_for_256!(U188); 361 bits_for_256!(U189); 362 bits_for_256!(U190); 363 bits_for_256!(U191); 364 bits_for_256!(U192); 365 bits_for_256!(U193); 366 bits_for_256!(U194); 367 bits_for_256!(U195); 368 bits_for_256!(U196); 369 bits_for_256!(U197); 370 bits_for_256!(U198); 371 bits_for_256!(U199); 372 bits_for_256!(U200); 373 bits_for_256!(U201); 374 bits_for_256!(U202); 375 bits_for_256!(U203); 376 bits_for_256!(U204); 377 bits_for_256!(U205); 378 bits_for_256!(U206); 379 bits_for_256!(U207); 380 bits_for_256!(U208); 381 bits_for_256!(U209); 382 bits_for_256!(U210); 383 bits_for_256!(U211); 384 bits_for_256!(U212); 385 bits_for_256!(U213); 386 bits_for_256!(U214); 387 bits_for_256!(U215); 388 bits_for_256!(U216); 389 bits_for_256!(U217); 390 bits_for_256!(U218); 391 bits_for_256!(U219); 392 bits_for_256!(U220); 393 bits_for_256!(U221); 394 bits_for_256!(U222); 395 bits_for_256!(U223); 396 bits_for_256!(U224); 397 bits_for_256!(U225); 398 bits_for_256!(U226); 399 bits_for_256!(U227); 400 bits_for_256!(U228); 401 bits_for_256!(U229); 402 bits_for_256!(U230); 403 bits_for_256!(U231); 404 bits_for_256!(U232); 405 bits_for_256!(U233); 406 bits_for_256!(U234); 407 bits_for_256!(U235); 408 bits_for_256!(U236); 409 bits_for_256!(U237); 410 bits_for_256!(U238); 411 bits_for_256!(U239); 412 bits_for_256!(U240); 413 bits_for_256!(U241); 414 bits_for_256!(U242); 415 bits_for_256!(U243); 416 bits_for_256!(U244); 417 bits_for_256!(U245); 418 bits_for_256!(U246); 419 bits_for_256!(U247); 420 bits_for_256!(U248); 421 bits_for_256!(U249); 422 bits_for_256!(U250); 423 bits_for_256!(U251); 424 bits_for_256!(U252); 425 bits_for_256!(U253); 426 bits_for_256!(U254); 427 bits_for_256!(U255); 428 bits_for_256!(U256); 429