BitArray.cpp 2.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104
  1. #include "utils/BitArray.h"
  2. #include "math/Math.h"
  3. static int roundUpDivide(int a, int b) {
  4. if(a % b == 0) {
  5. return a / b;
  6. }
  7. return a / b + 1;
  8. }
  9. static constexpr int INT_BITS = sizeof(int) * 8;
  10. static constexpr int DIVIDE_BITS = Math::roundUpLog2(INT_BITS);
  11. static int readBits(const int* data, int index, int bits) {
  12. int dataIndexA = (index * bits) >> DIVIDE_BITS;
  13. int dataIndexB = ((index + 1) * bits) >> DIVIDE_BITS;
  14. int shifts = (index * bits) & (INT_BITS - 1);
  15. if(dataIndexA == dataIndexB) {
  16. return (data[dataIndexA] >> shifts) & ((1 << bits) - 1);
  17. }
  18. int bitsInA = INT_BITS - shifts;
  19. int r = (data[dataIndexA] >> shifts) & ((1 << bitsInA) - 1);
  20. r |= (data[dataIndexB] & ((1 << (bits - bitsInA)) - 1)) << bitsInA;
  21. return r;
  22. }
  23. static void setBits(int* data, int index, int bits, int value) {
  24. int mask = (1 << bits) - 1;
  25. value &= mask;
  26. int dataIndexA = (index * bits) >> DIVIDE_BITS;
  27. int dataIndexB = ((index + 1) * bits) >> DIVIDE_BITS;
  28. int shifts = (index * bits) & (INT_BITS - 1);
  29. data[dataIndexA] &= ~(mask << shifts);
  30. data[dataIndexA] |= (value << shifts);
  31. if(dataIndexA != dataIndexB) {
  32. int leftBits = bits - (INT_BITS - shifts);
  33. int mask = (1 << leftBits) - 1;
  34. data[dataIndexB] &= ~mask;
  35. data[dataIndexB] |= (value >> (INT_BITS - shifts));
  36. }
  37. }
  38. BitArray::BitArray(int length, int bits)
  39. : length(length), bits(bits),
  40. data(new int[roundUpDivide(length * bits, sizeof(int))]) {
  41. }
  42. BitArray::BitArray(const BitArray& other) : BitArray(other.length, other.bits) {
  43. for(int i = 0; i < length; i++) {
  44. set(i, other.get(i));
  45. }
  46. }
  47. BitArray::BitArray(BitArray&& other) : length(0), bits(0), data(nullptr) {
  48. swap(other);
  49. }
  50. BitArray::~BitArray() {
  51. delete[] data;
  52. }
  53. BitArray& BitArray::operator=(BitArray other) {
  54. swap(other);
  55. return *this;
  56. }
  57. BitArray& BitArray::set(int index, int value) {
  58. setBits(data, index, bits, value);
  59. return *this;
  60. }
  61. int BitArray::get(int index) const {
  62. return readBits(data, index, bits);
  63. }
  64. int BitArray::getLength() const {
  65. return length;
  66. }
  67. int BitArray::getBits() const {
  68. return bits;
  69. }
  70. void BitArray::fill(int value) {
  71. for(int i = 0; i < length; i++) {
  72. set(i, value);
  73. }
  74. }
  75. void BitArray::resize(int newBits) {
  76. int* newData = new int[roundUpDivide(length * newBits, sizeof(int))];
  77. for(int i = 0; i < length; i++) {
  78. setBits(newData, i, newBits, get(i));
  79. }
  80. delete[] data;
  81. data = newData;
  82. bits = newBits;
  83. }
  84. void BitArray::swap(BitArray& other) {
  85. std::swap(length, other.length);
  86. std::swap(bits, other.bits);
  87. std::swap(data, other.data);
  88. }