1 module vest.utils.bitint; 2 3 // Bit manipulations 4 5 6 import core.stdc.stdint : uint8_t; 7 import std.traits : isArray; 8 import std.algorithm : min; 9 10 struct BitInt(T = size_t) 11 { 12 private: 13 T _value = 0; 14 enum T one = cast(T) 1; 15 16 public: 17 enum uint8_t length = cast(uint8_t)( 8 * T.sizeof ); 18 alias value this; 19 20 this(S)(S v) 21 if(!isArray!S) 22 { 23 _value = cast(T) v; 24 } 25 this(uint8_t[] states) 26 { 27 foreach(size_t i; 0 .. length) { 28 set(i, states[i]); 29 } 30 } 31 BitInt!T opAssign(S)(S rhs) 32 if(!isArray!S) 33 { 34 _value = cast(T) rhs; 35 return this; 36 } 37 BitInt!T opAssign(uint8_t[] states) 38 { 39 _value = BitInt!T(states)._value; 40 return this; 41 } 42 43 BitInt!T opOpAssign(string op)(T rhs) 44 { 45 mixin("_value "~op~"= rhs;"); 46 return this; 47 } 48 BitInt!T opOpAssign(string op)(BitInt!T rhs) 49 { 50 return opOpAssign!op(rhs._value); 51 } 52 T opOpAssign(string op)(uint8_t[] rhs) 53 { 54 return opOpAssign!op(BitInt!T(rhs)); 55 } 56 57 uint8_t get(size_t index) const pure nothrow @safe 58 { 59 return ( 0 == ( _value & (one << (length - 1 - (index % length))) ) ) ? uint8_t(0) : uint8_t(1); 60 } 61 uint8_t opIndex(size_t index) const pure nothrow @safe 62 { 63 return get(index); 64 } 65 uint8_t[] array() const pure nothrow @safe 66 { 67 uint8_t[] res; 68 res.length = length; 69 foreach(uint8_t i; 0..length) { 70 res[i] = get(i); 71 } 72 73 return res; 74 } 75 T value() const pure nothrow @safe 76 { 77 return _value; 78 } 79 80 ref BitInt set(size_t index, int state) pure nothrow @safe 81 { 82 T val = (one << (length - 1 - index % length)); 83 _value = state ? (_value | val) : (_value & ~cast(size_t)(val)); 84 return this; 85 } 86 ref BitInt on(size_t index) pure nothrow @safe 87 { 88 return set(index, true); 89 } 90 ref BitInt off(size_t index) pure nothrow @safe 91 { 92 return set(index, false); 93 } 94 95 uint8_t opDollar(size_t dim : 0LU)() const pure nothrow @safe 96 { 97 return length; 98 } 99 100 bool opIndexAssign(int state, size_t index) nothrow pure @safe 101 { 102 set(index, state); 103 return cast(bool) state; 104 } 105 106 uint8_t[] opSlice(size_t i, size_t j) const nothrow pure @safe 107 { 108 return array()[i .. j]; 109 } 110 uint8_t[] opSlice() const nothrow pure @safe 111 { 112 return array(); 113 } 114 115 uint8_t[] opSliceAssign(uint8_t[] states, size_t i_beg, size_t i_end) nothrow pure @safe 116 in(states.length >= i_end - i_beg) 117 { 118 foreach(size_t i; i_beg .. i_end) { 119 set(i, states[i - i_beg]); 120 } 121 return states; 122 } 123 uint8_t opSliceAssign(uint8_t state, size_t i_beg, size_t i_end) nothrow pure @safe 124 { 125 foreach(size_t i; i_beg .. i_end) { 126 set(i, state); 127 } 128 return state; 129 } 130 uint8_t opSliceAssign(uint8_t state) nothrow pure @safe 131 { 132 foreach(size_t i; 0 .. length) { 133 set(i, state); 134 } 135 return state; 136 } 137 uint8_t[] opSliceAssign(uint8_t[] states) nothrow pure @safe 138 { 139 auto end = min(length, states.length); 140 foreach(size_t i; 0 .. end) { 141 set(i, states[i]); 142 } 143 return states; 144 } 145 146 size_t opSliceOpAssign(string s : "&")(size_t state, size_t i_beg, size_t i_end) nothrow pure @safe 147 { 148 auto rhs = BitInt!T(state); 149 foreach(size_t i; i_beg .. i_end) { 150 set(i, get(i) & rhs[$ - i_end + i]); 151 } 152 153 return state; 154 } 155 size_t opSliceOpAssign(string s : "|")(size_t state, size_t i_beg, size_t i_end) nothrow pure @safe 156 { 157 auto rhs = BitInt!T(state); 158 foreach(size_t i; i_beg .. i_end) { 159 set(i, get(i) | rhs[$ - i_end + i]); 160 } 161 162 return state; 163 } 164 165 T opSliceOpAssign(string s : "|")(T state) nothrow pure @safe 166 { 167 _value |= BitInt!T(state)._value; 168 return _value; 169 } 170 T opSliceOpAssign(string s : "&")(T state) nothrow pure @safe 171 { 172 _value &= BitInt!T(state)._value; 173 return _value; 174 } 175 176 T opSliceOpAssign(string s : "|")(uint8_t[] states) nothrow pure @safe 177 { 178 auto end = min(length, states.length); 179 foreach(size_t i; 0..end) { 180 set(i, get(i) | states[i]); 181 } 182 return _value; 183 } 184 T opSliceOpAssign(string s : "&")(uint8_t[] states) nothrow pure @safe 185 { 186 auto end = min(length, states.length); 187 foreach(size_t i; 0..end) { 188 set(i, get(i) & states[i]); 189 } 190 return _value; 191 } 192 193 uint8_t[] opSliceOpAssign(string s : "|")(uint8_t[] states, size_t i_beg, size_t i_end) nothrow pure @safe 194 { 195 foreach(size_t i; i_beg .. i_end) { 196 set(i, get(i) | states[i-i_beg]); 197 } 198 return states; 199 } 200 uint8_t[] opSliceOpAssign(string s : "&")(uint8_t[] states, size_t i_beg, size_t i_end) nothrow pure @safe 201 { 202 foreach(size_t i; i_beg .. i_end) { 203 set(i, get(i) & states[i-i_beg]); 204 } 205 return states; 206 } 207 208 T opAssign(string s : "|")(T state) nothrow pure @safe 209 { 210 _value |= state; 211 return state; 212 } 213 T opAssign(string s : "&")(T state) nothrow pure @safe 214 { 215 _value &= state; 216 return state; 217 } 218 219 bool opEquals(S)(in BitInt!S rhs) const 220 { 221 return _value == rhs._value; 222 } 223 bool opEquals(T rhs) const 224 { 225 return _value == rhs; 226 } 227 bool opEquals(uint8_t[] states) const 228 { 229 return _value == BitInt!T(states)._value; 230 } 231 } 232 233 234 235 nothrow unittest{ 236 import core.stdc.stdint; 237 238 { 239 size_t y = BitInt!size_t(5); 240 assert(5 == y); 241 } 242 { 243 BitInt!uint8_t x = 5; 244 245 assert(x[$ - 3] == x.get(x.length -3)); 246 assert(x[$ - 4] == x.get(x.length -4)); 247 assert(1 == x[$ - 1 - 2]); 248 assert(0 == x[$ - 1 - 3]); 249 assert(x.array == [0, 0, 0, 0, 0, 1, 0, 1]); 250 assert(x.array == x[]); 251 } 252 { 253 assert([0, 0, 0, 0, 0, 0, 0, 1] == BitInt!uint8_t(1).array); 254 assert([0, 0, 0, 0, 0, 0, 1, 0] == BitInt!uint8_t(2).array); 255 assert([0, 0, 0, 0, 0, 0, 1, 1] == BitInt!uint8_t(3).array); 256 assert([0, 0, 0, 0, 0, 1, 0, 0] == BitInt!uint8_t(4).array); 257 assert([0, 0, 0, 0, 0, 1, 0, 1] == BitInt!uint8_t(5).array); 258 assert([0, 0, 0, 0, 0, 1, 1, 0] == BitInt!uint8_t(6).array); 259 assert([0, 0, 0, 0, 0, 1, 1, 1] == BitInt!uint8_t(7).array); 260 assert([0, 0, 0, 0, 1, 0, 0, 0] == BitInt!uint8_t(8).array); 261 assert([0, 0, 0, 0, 1, 0, 0, 1] == BitInt!uint8_t(9).array); 262 assert([0, 0, 0, 0, 1, 0, 1, 0] == BitInt!uint8_t(10).array); 263 assert([0, 0, 0, 0, 1, 0, 1, 1] == BitInt!uint8_t(11).array); 264 assert([0, 0, 0, 0, 1, 1, 0, 0] == BitInt!uint8_t(12).array); 265 assert([0, 0, 0, 1, 0, 0, 0, 0] == BitInt!uint8_t(16).array); 266 assert([0, 0, 0, 1, 1, 0, 0, 1] == BitInt!uint8_t(25).array); 267 268 assert(BitInt!uint16_t(25)[$-8..$] == BitInt!uint8_t(25).array); 269 } 270 { 271 BitInt!uint8_t x = 5; 272 273 x = BitInt!size_t(133); 274 assert([1, 0, 0, 0, 0, 1, 0, 1] == x.array); 275 assert(133 == x); 276 } 277 { 278 BitInt!uint8_t x; 279 x[] = [1, 0, 1, 0, 1, 1, 0, 1]; 280 281 assert([1, 0, 1, 0, 1, 1, 0, 1] == x[]); 282 assert(173 == x); 283 284 x.set(1, 1); 285 x[2] = 0; 286 x[$ - 2] = 1; 287 assert([1, 1, 0, 0, 1, 1, 1, 1] == x.array); 288 assert(207 == x); 289 } 290 { 291 BitInt!uint8_t x = [0, 1, 0, 1, 0, 1, 0, 1]; 292 293 x[$ - 3..$] = 1; 294 x[0 .. 3] = 0; 295 assert([0, 0, 0, 1, 0, 1, 1, 1] == x); 296 assert(23 == x); 297 assert([0, 1, 0, 1, 0, 1, 0, 1] != x); 298 assert(85 != x); 299 } 300 { 301 BitInt!uint8_t x = [0, 1, 0, 1, 0, 1, 0, 1]; 302 303 x[2 .. $ - 3] = [ 1, 1, 1]; 304 assert([0, 1, 1, 1, 1, 1, 0, 1] == x); 305 assert(125 == x); 306 307 x[3..5] = [0, 0]; 308 assert([0, 1, 1, 0, 0, 1, 0, 1] == x); 309 assert(101 == x); 310 311 x[] = 0; 312 assert([0, 0, 0, 0, 0, 0, 0, 0] == x); 313 assert(0 == x); 314 315 x[] = 1; 316 assert([1, 1, 1, 1, 1, 1, 1, 1] == x); 317 assert(255 == x); 318 } 319 { 320 BitInt!size_t x = 255; 321 BitInt!uint8_t y = x; 322 assert(x.value == y.value); 323 } 324 { 325 BitInt!uint8_t x = 255; 326 BitInt!size_t y = x; 327 assert(x.value == y.value); 328 } 329 { 330 BitInt!uint16_t x = 0; 331 BitInt!uint8_t y = 255; 332 333 x[1..5] = y[3..$]; 334 assert([0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] == x); 335 336 x = y; 337 assert([0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1] == x); 338 } 339 { 340 BitInt!uint16_t x = 0; 341 BitInt!uint8_t y = 255; 342 343 x[] = y[]; 344 assert([1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0] == x); 345 } 346 { 347 BitInt!uint16_t x = 0; 348 349 x[1..5] = 1; 350 x[2] = 0; 351 x[$-2..$] = 1; 352 353 assert([0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1] == x); 354 } 355 { 356 BitInt!uint16_t x = [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]; 357 x[0..$] &= 255; 358 assert([0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1] == x); 359 } 360 { 361 BitInt!uint16_t x = uint16_t.max; 362 x[0..$] &= 255; 363 assert([0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1] == x); 364 } 365 { 366 BitInt!uint16_t x = [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]; 367 x[0..$] |= 255; 368 assert([0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1] == x); 369 } 370 { 371 BitInt!uint16_t x = 0; 372 x[0..$] |= 255; 373 assert([0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1] == x); 374 assert(255 == x); 375 } 376 { 377 BitInt!uint16_t x = [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]; 378 x[] &= 255; 379 assert([0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1] == x); 380 } 381 { 382 BitInt!uint16_t x = uint16_t.max; 383 x[] &= 255; 384 assert([0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1] == x); 385 } 386 { 387 BitInt!uint16_t x = [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]; 388 x[] |= 255; 389 assert([0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1] == x); 390 } 391 { 392 BitInt!uint16_t x = 0; 393 x[] |= 255; 394 assert([0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1] == x); 395 assert(255 == x); 396 } 397 { 398 BitInt!uint8_t x = 0; 399 400 x[0..2] = 255; 401 assert(192 == x); 402 assert([1, 1, 0, 0, 0, 0, 0, 0] == x); 403 404 x[2..4] |= 255; 405 assert(240 == x); 406 assert([1, 1, 1, 1, 0, 0, 0, 0] == x); 407 408 x[1..3] &= 0; 409 assert(144 == x); 410 assert([1, 0, 0, 1, 0, 0, 0, 0] == x); 411 412 x[] |= 7; 413 assert(151 == x); 414 assert([1, 0, 0, 1, 0, 1, 1, 1] == x); 415 416 x[] &= 127; 417 assert([0, 0, 0, 1, 0, 1, 1, 1] == x); 418 } 419 { 420 BitInt!uint8_t x = 0; 421 x[0..5] |= [1, 0, 1, 0, 1, 0, 1, 0]; 422 assert([1, 0, 1, 0, 1, 0, 0, 0] == x); 423 424 x[4..$] |= BitInt!uint8_t(uint8_t.max)[]; 425 assert([1, 0, 1, 0, 1, 1, 1, 1] == x); 426 } 427 { 428 BitInt!uint8_t x = size_t.max; 429 x[0..5] &= [1, 0, 1, 0, 1, 0, 1, 0]; 430 assert([1, 0, 1, 0, 1, 1, 1, 1] == x); 431 432 x[$-2..$] &= 0; 433 assert([1, 0, 1, 0, 1, 1, 0, 0] == x); 434 } 435 { 436 BitInt!uint8_t x = size_t.max; 437 x[0..5] &= [1, 0, 1, 0, 1, 0, 1, 0]; 438 assert([1, 0, 1, 0, 1, 1, 1, 1] == x); 439 440 x[$-2..$] &= 0; 441 assert([1, 0, 1, 0, 1, 1, 0, 0] == x); 442 } 443 { 444 BitInt!uint8_t x = size_t.max; 445 x[] &= 7; 446 assert(7 == x); 447 x = 0; 448 x[] |= 7; 449 assert(7 == x); 450 } 451 { 452 BitInt!uint8_t x = size_t.max; 453 454 x &= 7; 455 assert(7 == x); 456 x = 0; 457 x |= 7; 458 assert(7 == x); 459 460 x += 55; 461 assert(62 == x); 462 463 x -= 14; 464 assert(48 == x); 465 466 x = [1,0,1,0,1,0,1,0,1]; 467 x |= 227; 468 assert(235 == x); 469 } 470 { 471 BitInt!uint8_t x = 0; 472 473 x |= [1, 0, 0, 1, 0, 1, 1, 1]; 474 assert(151 == x); 475 476 x = 0; 477 x |= BitInt!uint8_t([1, 0, 0, 1, 0, 1, 1, 1]); 478 assert(151 == x); 479 480 x = 0; 481 x |= 151; 482 assert(151 == x); 483 } 484 { 485 BitInt!uint8_t x = 0; 486 x += [1, 0, 0, 1, 0, 1, 1, 1]; 487 assert(151 == x); 488 489 x = 0; 490 x += BitInt!uint8_t([1, 0, 0, 1, 0, 1, 1, 1]); 491 assert(151 == x); 492 493 x = 0; 494 x += 151; 495 assert(151 == x); 496 } 497 { 498 BitInt!uint8_t x = 0; 499 x[] |= 151; 500 assert(151 == x); 501 } 502 { 503 BitInt!uint8_t x = 0; 504 x[] |= BitInt!uint8_t([1, 0, 0, 1, 0, 1, 1, 1]); 505 assert(151 == x); 506 } 507 { 508 BitInt!uint8_t x = 0; 509 x[] |= [1, 0, 0, 1, 0, 1, 1, 1]; 510 assert(151 == x); 511 x = uint8_t.max; 512 x[] &= [1, 0, 0, 1, 0, 1, 1, 1]; 513 assert(151 == x); 514 } 515 { 516 BitInt!uint8_t x = 0; 517 518 x[] |= [1, 0, 1, 1, 1]; 519 assert([1, 0, 1, 1, 1, 0, 0, 0] == x); 520 521 522 x[] &= BitInt!uint32_t(uint32_t.max)[]; 523 assert([1, 0, 1, 1, 1, 0, 0, 0] == x); 524 } 525 }