Evo C++ Library v0.5.1
bits.h
Go to the documentation of this file.
1 // Evo C++ Library
2 /* Copyright 2019 Justin Crowell
3 Distributed under the BSD 2-Clause License -- see included file LICENSE.txt for details.
4 */
6 
7 #pragma once
8 #ifndef INCL_evo_bits_h
9 #define INCL_evo_bits_h
10 
11 #include "type.h"
12 
13 // Disable certain MSVC warnings for this file
14 #if defined(_MSC_VER)
15  #include <intrin.h>
16  #pragma warning(push)
17  #pragma warning(disable:4146)
18 #endif
19 
20 namespace evo {
25 
27 
29 namespace impl {
30 #if defined(__GNUC__) && !defined(EVO_NOBUILTIN_BITS) && !defined(EVO_GCC_NOBUILTIN_POPCOUNT)
31  template<class T,int S=sizeof(T)> struct BitsPopCount {
32  static int popcount(uint32 mask) {
33  return (uint)__builtin_popcount(mask);
34  }
35  };
36  template<class T> struct BitsPopCount<T,4> {
37  static int popcount(uint32 mask) {
38  #if defined(EVO_64)
39  return (uint)__builtin_popcount(mask);
40  #else
41  return (uint)__builtin_popcountl(mask);
42  #endif
43  }
44  };
45  template<class T> struct BitsPopCount<T,8> {
46  static int popcount(uint64 mask) {
47  return (uint)__builtin_popcountll(mask);
48  }
49  };
50 #else
51  template<class T,int S=sizeof(T)> struct BitsPopCount {
52  static int popcount(uint32 mask) {
53  mask -= ((mask >> 1) & 0x55555555);
54  mask = (mask & 0x33333333) + ((mask >> 2) & 0x33333333);
55  return (int)((((mask + (mask >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24);
56  }
57  };
58  template<class T> struct BitsPopCount<T,8> {
59  static int popcount(uint64 mask) {
60  return BitsPopCount<uint32>::popcount((uint32)(mask & 0xFFFFFFFFUL)) +
61  BitsPopCount<uint32>::popcount((uint32)((mask >> 32) & 0xFFFFFFFFUL));
62  }
63  };
64 #endif
65 }
68 #if defined(_MSC_VER) && !defined(EVO_NOBUILTIN_BITS)
69  namespace impl {
70  template<class T,int S=sizeof(T)> struct BitsClz {
71  // Not used: INVALID_INTEGER_TYPE
72  };
73  template<class T> struct BitsClz<T,1> {
74  static uint clz(uint8 mask) {
75  ulong i;
76  if (_BitScanReverse(&i, (uint32)mask) == 0)
77  return NONE;
78  return (uint)(7 - i);
79  }
80  };
81  template<class T> struct BitsClz<T,2> {
82  static uint clz(uint16 mask) {
83  ulong i;
84  if (_BitScanReverse(&i, (uint32)mask) == 0)
85  return NONE;
86  return (uint)(15 - i);
87  }
88  };
89  template<class T> struct BitsClz<T,4> {
90  static uint clz(uint32 mask) {
91  ulong i;
92  if (_BitScanReverse(&i, mask) == 0)
93  return NONE;
94  return (uint)(31 - i);
95  }
96  };
97  template<class T> struct BitsClz<T,8> {
98  static uint clz(uint64 mask) {
99  ulong i;
100  #if defined(EVO_64)
101  if (_BitScanReverse64(&i, mask) == 0)
102  return NONE;
103  return (uint)(63 - i);
104  #else
105  if (_BitScanReverse(&i, ((mask >> 32) & 0x00000000FFFFFFFFUL)) != 0)
106  return (uint)(31 - i);
107  else if (_BitScanReverse(&i, (mask & 0x00000000FFFFFFFFUL)) != 0)
108  return (uint)(63 - i);
109  return NONE;
110  #endif
111  }
112  };
113  }
114 
115  inline bool bits_cpu_popcnt() {
116  #if defined(_M_ARM)
117  return false; // Not supported by ARM
118  #else
119  int cpuinfo[4];
120  __cpuid(cpuinfo, 0x00000001);
121  return (cpuinfo[2] & 0x800000) != 0;
122  #endif
123  }
124 #elif defined(__GNUC__) && !defined(EVO_NOBUILTIN_BITS)
125  namespace impl {
126  template<class T,int S=sizeof(T)> struct BitsClz {
127  // Not used: INVALID_INTEGER_TYPE
128  };
129  template<class T> struct BitsClz<T,1> {
130  static uint clz(uint8 mask) {
131  const uint OFFSET = (sizeof(uint) * 8) - 8;
132  if (mask == 0)
133  return NONE;
134  return (uint)__builtin_clz((uint)mask) - OFFSET;
135  }
136  };
137  template<class T> struct BitsClz<T,2> {
138  static uint clz(uint16 mask) {
139  const uint OFFSET = (sizeof(uint) * 8) - 16;
140  if (mask == 0)
141  return NONE;
142  return (uint)__builtin_clz((uint)mask) - OFFSET;
143  }
144  };
145  template<class T> struct BitsClz<T,4> {
146  static uint clz(uint32 mask) {
147  if (mask == 0)
148  return NONE;
149  #if defined(EVO_64)
150  return (uint)__builtin_clz(mask);
151  #else
152  return (uint)__builtin_clzl(mask);
153  #endif
154  }
155  };
156  template<class T> struct BitsClz<T,8> {
157  static uint clz(uint64 mask) {
158  if (mask == 0)
159  return NONE;
160  return (uint)__builtin_clzll(mask);
161  }
162  };
163  }
164 
165  inline bool bits_cpu_popcnt() {
166  return false;
167  }
168 #else
169 
170  namespace impl {
171  template<class T,int S=sizeof(T)> struct BitsClz {
172  // Not used: INVALID_INTEGER_TYPE
173  };
174  template<class T> struct BitsClz<T,1> {
175  static uint clz(uint8 mask) {
176  if (mask == 0)
177  return NONE;
178  mask |= (mask >> 1);
179  mask |= (mask >> 2);
180  mask |= (mask >> 4);
181  return 8 - BitsPopCount<T>::popcount(mask);
182  }
183  };
184  template<class T> struct BitsClz<T,2> {
185  static uint clz(uint16 mask) {
186  if (mask == 0)
187  return NONE;
188  mask |= (mask >> 1);
189  mask |= (mask >> 2);
190  mask |= (mask >> 4);
191  mask |= (mask >> 8);
192  return 16 - BitsPopCount<T>::popcount(mask);
193  }
194  };
195  template<class T> struct BitsClz<T,4> {
196  static uint clz(uint32 mask) {
197  if (mask == 0)
198  return NONE;
199  mask |= (mask >> 1);
200  mask |= (mask >> 2);
201  mask |= (mask >> 4);
202  mask |= (mask >> 8);
203  mask |= (mask >> 16);
204  return 32 - BitsPopCount<T>::popcount(mask);
205  }
206  };
207  template<class T> struct BitsClz<T,8> {
208  static uint clz(uint64 mask) {
209  if (mask == 0)
210  return NONE;
211  mask |= (mask >> 1);
212  mask |= (mask >> 2);
213  mask |= (mask >> 4);
214  mask |= (mask >> 8);
215  mask |= (mask >> 16);
216  mask |= (mask >> 32);
217  return 64 - BitsPopCount<T>::popcount(mask);
218  }
219  };
220  }
231  inline bool bits_cpu_popcnt() {
232  return false;
233  }
234 #endif
235 
241 template<class T>
242 inline int bits_popcount(T mask) {
243  return impl::BitsPopCount<T>::popcount(mask);
244 }
245 
254 template<class T>
255 inline uint bits_clz(T mask) {
256  return impl::BitsClz<T>::clz(mask);
257 }
258 
265 inline uint bits_clz8(uint8 mask) {
266  return impl::BitsClz<uint8>::clz(mask);
267 }
268 
275 inline uint bits_clz16(uint16 mask) {
276  return impl::BitsClz<uint16>::clz(mask);
277 }
278 
285 inline uint bits_clz32(uint32 mask) {
286  return impl::BitsClz<uint32>::clz(mask);
287 }
288 
295 inline uint bits_clz64(uint64 mask) {
296  return impl::BitsClz<uint64>::clz(mask);
297 }
298 
300 
308 template<class T=ulong,class TSize=SizeT>
309 struct Bits {
310  typedef T Value;
311  typedef TSize Size;
312 
313  static const uint BYTES = sizeof(T);
314  static const uint BITS = BYTES * 8;
315  static const uint BITS_MINUS_1 = BITS - 1;
316  static const T RBIT = 0x01;
317  static const T LBIT = RBIT << BITS_MINUS_1;
318  static const T ZERO = 0;
319  static const T ALLBITS = T(~ZERO);
320 
329  static T align_left(T value, uint count) {
330  if (count >= BITS)
331  return value;
332  return value << (BITS - count);
333  }
334 
343  static T align_right(T value, uint count) {
344  if (count >= BITS)
345  return value;
346  return value >> (BITS - count);
347  }
348 
358  static T mask(uint start, uint count) {
359  assert( start + count <= BITS );
360  if (start > 0)
361  return (((RBIT << count) - 1) << (BITS - (start + count)));
362  return -(LBIT >> (count - 1));
363  }
364 
374  static T safemask(uint start, uint count) {
375  if (start < BITS && count > 0) {
376  const uint end = start + count;
377  if (end <= BITS) {
378  // Copied from mask()
379  if (start > 0)
380  return (((RBIT << count) - 1) << (BITS - end));
381  return -(LBIT >> (count - 1));
382  } else if (start > 0)
383  return (LBIT >> (start - 1)) - 1;
384  return ALLBITS;
385  }
386  return ZERO;
387  }
388 
396  static Size array_size(Size bitsize) {
397  return (bitsize + BITS_MINUS_1) / BITS;
398  }
399 
407  static Size array_bitsize(Size chunks) {
408  return (chunks * BITS);
409  }
410 
418  static Size array_countbits(const T* data, Size bitsize) {
419  assert( !IntegerT<T>::SIGN );
420  Size count = 0;
421  for (Size pos = 0, i = 0; pos < bitsize; pos += BITS, ++i)
422  count += bits_popcount(data[i]);
423  assert( count <= bitsize );
424  return count;
425  }
426 
436  static Size array_countbits(const T* data, Size bitsize, Size pos, Size count) {
437  assert( !IntegerT<T>::SIGN );
438  if (pos < bitsize && count > 0) {
439  // bitsize becomes maxcount
440  bitsize -= pos;
441  if (count > bitsize)
442  count = bitsize;
443 
444  Size index = (pos / BITS);
445  const Size offset = pos - (index * BITS);
446  const Size offset_end = offset + count;
447  const T* p = data + index;
448  if (offset_end <= BITS) {
449  // All in 1 chunk
450  const T maskval = (count == BITS ? ALLBITS : (((RBIT << count) - 1) << (BITS - offset_end)));
451  return bits_popcount(*p & maskval);
452  } else {
453  Size result = 0;
454 
455  // First partial chunk
456  if (offset > 0) {
457  count -= (BITS - offset);
458  result += bits_popcount(*p & ((LBIT >> (offset - 1)) - 1));
459  ++p;
460  }
461 
462  // Remaining chunks
463  while (count >= BITS) {
464  count -= BITS;
465  result += bits_popcount(*p & ALLBITS);
466  ++p;
467  }
468 
469  // Last partial chunk
470  if (count > 0)
471  result += bits_popcount(*p & -(LBIT >> (count - 1)));
472 
473  return result;
474  }
475  }
476  return 0;
477  }
478 
486  static bool array_checkall(const T* data, Size bitsize) {
487  assert( !IntegerT<T>::SIGN );
488  Size i = 0, sz = bitsize / BITS;
489  for (; i < sz; ++i)
490  if (data[i] != ALLBITS)
491  return false;
492  Size pos = bitsize - (i * BITS);
493  if (pos > 0)
494  if ((data[i] | ((LBIT >> (pos - 1)) - 1)) != ALLBITS)
495  return false;
496  return true;
497  }
498 
508  static bool array_checkall(const T* data, Size bitsize, Size pos, Size count) {
509  assert( !IntegerT<T>::SIGN );
510  if (pos < bitsize && count > 0) {
511  // bitsize becomes maxcount
512  bitsize -= pos;
513  if (count > bitsize)
514  count = bitsize;
515 
516  Size index = (pos / BITS);
517  const Size offset = pos - (index * BITS);
518  const Size offset_end = offset + count;
519  const T* p = data + index;
520  if (offset_end <= BITS) {
521  // All in 1 chunk
522  const T maskval = (count == BITS ? ALLBITS : (((RBIT << count) - 1) << (BITS - offset_end)));
523  return (*p | (T)~maskval) == ALLBITS;
524  } else {
525  // First partial chunk
526  if (offset > 0) {
527  count -= (BITS - offset);
528  if ((*p | (T)~((LBIT >> (offset - 1)) - 1)) != ALLBITS)
529  return false;
530  ++p;
531  }
532 
533  // Remaining chunks
534  while (count >= BITS) {
535  count -= BITS;
536  if (*p != ALLBITS)
537  return false;
538  ++p;
539  }
540 
541  // Last partial chunk
542  return (count == 0 || (*p | (T)~-(LBIT >> (count - 1))) == ALLBITS);
543  }
544  }
545  return true;
546  }
547 
555  static bool array_checkany(const T* data, Size bitsize) {
556  for (Size pos = 0, i = 0; pos < bitsize; pos += BITS, ++i)
557  if (data[i] != 0)
558  return true;
559  return false;
560  }
561 
571  static bool array_checkany(const T* data, Size bitsize, Size pos, Size count) {
572  assert( !IntegerT<T>::SIGN );
573  if (pos < bitsize && count > 0) {
574  // bitsize becomes maxcount
575  bitsize -= pos;
576  if (count > bitsize)
577  count = bitsize;
578 
579  Size index = (pos / BITS);
580  const Size offset = pos - (index * BITS);
581  const Size offset_end = offset + count;
582  const T* p = data + index;
583  if (offset_end <= BITS) {
584  // All in 1 chunk
585  const T maskval = (count == BITS ? ALLBITS : (((RBIT << count) - 1) << (BITS - offset_end)));
586  return (*p & maskval) != ZERO;
587  } else {
588  // First partial chunk
589  if (offset > 0) {
590  count -= (BITS - offset);
591  if ((*p & (T)((LBIT >> (offset - 1)) - 1)) != ZERO)
592  return true;
593  ++p;
594  }
595 
596  // Remaining chunks
597  while (count >= BITS) {
598  count -= BITS;
599  if (*p != ZERO)
600  return true;
601  ++p;
602  }
603 
604  // Last partial chunk
605  return (count != 0 && (*p & (T)-(LBIT >> (count - 1))) != ZERO);
606  }
607  }
608  return false;
609  }
610 
615  struct IterState {
616  const T* data;
617  Size size;
618  Size index;
619  Size pos;
620  T chunk;
621 
622  IterState() {
623  data = NULL;
624  size = 0;
625  index = NONE;
626  pos = 0;
627  chunk = 0;
628  }
629  };
630 
641  static Size array_iter(IterState& state, const T* data, Size bitsize) {
642  state.data = data;
643  state.size = (bitsize + BITS - 1) / BITS;
644  for (Size i = 0, sz = state.size; i < sz; ++i) {
645  if (data[i] != 0) {
646  state.chunk = data[i];
647  state.index = i;
648  state.pos = bits_clz(state.chunk);
649  return state.pos + (i * BITS);
650  }
651  }
652  state.index = NONE;
653  return NONE;
654  }
655 
664  static Size array_iternext(IterState& state) {
665  Size i = state.index;
666  Size sz = state.size;
667  if (i < sz) {
668  // Resume from previous bit
669  if (state.pos < BITS_MINUS_1) {
670  state.chunk &= ((LBIT >> state.pos) - 1);
671  if (state.chunk != 0) {
672  // Next bit is in same chunk
673  state.pos = bits_clz(state.chunk);
674  return state.pos + (i * BITS);
675  }
676  }
677  ++i;
678 
679  // Check remaining chunks
680  for (const T* data = state.data; i < sz; ++i) {
681  if (data[i] != 0) {
682  state.chunk = data[i];
683  state.index = i;
684  state.pos = bits_clz(state.chunk);
685  return state.pos + (i * BITS);
686  }
687  }
688  state.index = NONE;
689  }
690  return NONE;
691  }
692 
702  static bool array_get(const T* data, Size bitsize, Size pos) {
703  assert( !IntegerT<T>::SIGN );
704  if (pos < bitsize) {
705  const Size i = (pos / BITS);
706  return ( data[i] & (LBIT >> (pos - (i * BITS))) ) != 0;
707  }
708  return false;
709  }
710 
721  static bool array_set(T* data, Size bitsize, Size pos, bool value=true) {
722  assert( !IntegerT<T>::SIGN );
723  if (pos < bitsize) {
724  const Size i = (pos / BITS);
725  const T mask = (LBIT >> (pos - (i * BITS)));
726  if (value)
727  data[i] |= mask;
728  else
729  data[i] &= ~mask;
730  return true;
731  }
732  return false;
733  }
734 
746  static Size array_set_multi(T* data, Size bitsize, Size pos=0, Size count=ALL, bool value=true) {
747  #if defined(EVO_OLDCC) // Fixes undefined reference on older compilers
748  const T ALLBITS = Bits<T,SizeT>::ALLBITS;
749  const T ZERO = Bits<T,SizeT>::ZERO;
750  #endif
751  assert( !IntegerT<T>::SIGN );
752  if (pos < bitsize && count > 0) {
753  // bitsize becomes return value
754  bitsize -= pos;
755  if (count > bitsize)
756  count = bitsize;
757  else
758  bitsize = count;
759 
760  Size index = (pos / BITS);
761  const Size offset = pos - (index * BITS);
762  const Size offset_end = offset + count;
763  T* p = data + index;
764  T maskval;
765  if (offset_end <= BITS) {
766  // All in 1 chunk
767  maskval = (count == BITS ? ALLBITS : (((RBIT << count) - 1) << (BITS - offset_end)));
768  if (value)
769  *p |= maskval;
770  else
771  *p &= ~maskval;
772  } else {
773  // First partial chunk
774  if (offset > 0) {
775  count -= (BITS - offset);
776  maskval = (LBIT >> (offset - 1)) - 1;
777  if (value)
778  *p |= maskval;
779  else
780  *p &= ~maskval;
781  ++p;
782  }
783 
784  // Remaining chunks
785  maskval = (value ? ALLBITS : ZERO);
786  while (count >= BITS) {
787  count -= BITS;
788  *p = maskval;
789  ++p;
790  }
791 
792  // Last partial chunk
793  if (count > 0) {
794  maskval = -(LBIT >> (count - 1));
795  if (value)
796  *p |= maskval;
797  else
798  *p &= ~maskval;
799  }
800  }
801  return bitsize;
802  }
803  return 0;
804  }
805 
815  static bool array_toggle(T* data, Size bitsize, Size pos) {
816  assert( !IntegerT<T>::SIGN );
817  if (pos < bitsize) {
818  const Size i = (pos / BITS);
819  data[i] ^= (LBIT >> (pos - (i * BITS)));
820  return true;
821  }
822  return false;
823  }
824 
835  static Size array_toggle_multi(T* data, Size bitsize, Size pos=0, Size count=ALL) {
836  assert( !IntegerT<T>::SIGN );
837  if (pos < bitsize && count > 0) {
838  // bitsize becomes return value
839  bitsize -= pos;
840  if (count > bitsize)
841  count = bitsize;
842  else
843  bitsize = count;
844 
845  Size index = (pos / BITS);
846  const Size offset = pos - (index * BITS);
847  const Size offset_end = offset + count;
848  T* p = data + index;
849  if (offset_end <= BITS) {
850  // All in 1 chunk
851  const T maskval = (count == BITS ? ALLBITS : (((RBIT << count) - 1) << (BITS - offset_end)));
852  *p ^= maskval;
853  } else {
854  // First partial chunk
855  if (offset > 0) {
856  count -= (BITS - offset);
857  *p ^= (LBIT >> (offset - 1)) - 1;
858  ++p;
859  }
860 
861  // Remaining chunks
862  while (count >= BITS) {
863  count -= BITS;
864  *p ^= ALLBITS;
865  ++p;
866  }
867 
868  // Last partial chunk
869  if (count > 0)
870  *p ^= -(LBIT >> (count - 1));
871  }
872  return bitsize;
873  }
874  return 0;
875  }
876 
894  template<class U>
895  static bool array_store(T* data, Size bitsize, Size pos, Size count, U value) {
896  assert( !IntegerT<T>::SIGN );
897  if (count > 0) {
898  if (count > (Size)IntegerT<U>::BITS)
899  count = (Size)IntegerT<U>::BITS;
900 
901  if (pos >= bitsize)
902  return false;
903  bitsize -= pos;
904 
905  typename ToUnsigned<U>::Type uvalue = (typename ToUnsigned<U>::Type)value;
906 
907  if (count < (Size)IntegerT<U>::BITS)
908  // Mask out bits not being stored
909  uvalue &= ((IntegerT<U>::RBIT << count) - 1);
910 
911  Size index = (pos / BITS);
912  const Size offset = pos - (index * BITS);
913  const Size offset_end = offset + count;
914  T* p = data + index;
915  T maskval;
916  if (offset_end <= BITS) {
917  // All in 1 chunk
918  const uint lshift = BITS - offset_end;
919  maskval = (count == BITS ? 0 : ~(((RBIT << count) - 1) << lshift));
920  *p = (*p & maskval) | (T(uvalue) << lshift);
921  } else {
922  // First partial chunk
923  if (offset > 0) {
924  count -= (BITS - offset);
925  maskval = (LBIT >> (offset - 1)) - 1;
926  *p = (*p & ~maskval) | (T(uvalue >> count) & maskval);
927  ++p;
928  }
929 
930  // Remaining chunks
931  while (count >= BITS) {
932  count -= BITS;
933  *p = T(uvalue >> count);
934  ++p;
935  }
936 
937  // Last partial chunk
938  if (count > 0) {
939  maskval = -(LBIT >> (count - 1));
940  *p = (*p & ~maskval) | ((T(uvalue) << (BITS - count)) & maskval);
941  }
942  }
943  return true;
944  }
945  return false;
946  }
947 
962  template<class U EVO_ONCPP11(=uint32)>
963  static U array_extractl(const T* data, Size bitsize, Size pos, Size count) {
964  assert( !IntegerT<T>::SIGN );
965  assert( !IntegerT<U>::SIGN );
966  if (pos < bitsize && count > 0) {
967  bitsize -= pos;
968  if (count > bitsize)
969  count = bitsize;
970  if (count > (Size)IntegerT<U>::BITS)
971  count = (Size)IntegerT<U>::BITS;
972 
973  Size index = (pos / BITS);
974  const Size offset = pos - (index * BITS);
975  const Size offset_end = offset + count;
976  const T* ptr = data + index;
977 
978  if (offset_end <= BITS) {
979  // All in 1 chunk
980  if (count == BITS)
981  return U(*ptr); // whole chunk
982  return U( (*ptr & (T(~(ALLBITS >> count)) >> offset)) >> (BITS - offset_end) )
983  << ((Size)IntegerT<U>::BITS - count); // left align
984  } else {
985  // Use bitsize to store extracted bitsize
986  bitsize = count;
987  U result;
988 
989  // First partial chunk
990  if (offset > 0) {
991  count -= (BITS - offset);
992  result = U(*ptr & (ALLBITS >> offset)) << count;
993  ++ptr;
994  } else
995  result = 0;
996 
997  // Whole chunks
998  while (count >= BITS) {
999  count -= BITS;
1000  result |= U(*ptr) << count;
1001  ++ptr;
1002  }
1003 
1004  // Last partial chunk
1005  if (count > 0)
1006  result |= (*ptr & ~(ALLBITS >> count)) >> (BITS - count);
1007 
1008  // Left align
1009  return result << ((Size)IntegerT<U>::BITS - bitsize);
1010  }
1011  }
1012  return 0;
1013  }
1014 
1032  template<class U EVO_ONCPP11(=uint32)>
1033  static U array_extractr(const T* data, Size bitsize, Size pos, Size count) {
1034  assert( !IntegerT<T>::SIGN );
1035  assert( !IntegerT<U>::SIGN );
1036  if (pos < bitsize && count > 0) {
1037  if (count > (Size)IntegerT<U>::BITS)
1038  count = (Size)IntegerT<U>::BITS;
1039  bitsize -= pos;
1040 
1041  Size truncbits = 0;
1042  if (count > bitsize) {
1043  // Pretend to extract bits after end of array
1044  truncbits = count - bitsize;
1045  count = bitsize;
1046  }
1047 
1048  Size index = (pos / BITS);
1049  const Size offset = pos - (index * BITS);
1050  const Size offset_end = offset + count;
1051  const T* ptr = data + index;
1052  U result;
1053 
1054  if (offset_end <= BITS) {
1055  // All in 1 chunk
1056  if (count == BITS)
1057  result = U(*ptr);
1058  else
1059  result = U( (*ptr & (T(~(ALLBITS >> count)) >> offset)) >> (BITS - offset_end) );
1060  } else {
1061  // First partial chunk
1062  if (offset > 0) {
1063  count -= (BITS - offset);
1064  result = U(*ptr & (ALLBITS >> offset)) << count;
1065  ++ptr;
1066  } else
1067  result = 0;
1068 
1069  // Whole chunks
1070  while (count >= BITS) {
1071  count -= BITS;
1072  result |= U(*ptr) << count;
1073  ++ptr;
1074  }
1075 
1076  // Last partial chunk
1077  if (count > 0)
1078  result |= (*ptr & ~(ALLBITS >> count)) >> (BITS - count);
1079  }
1080 
1081  assert( truncbits < (Size)IntegerT<U>::BITS );
1082  return result << truncbits;
1083  }
1084  return 0;
1085  }
1086 
1100  static Size array_copy(T* data, Size bitsize, T* src_data, Size src_bitsize, Size src_pos=0, Size src_count=ALL) {
1101  assert( !IntegerT<T>::SIGN );
1102  if (src_pos < src_bitsize && src_count > 0) {
1103  if (src_count > bitsize)
1104  src_count = bitsize;
1105 
1106  // src_bitsize becomes return value
1107  src_bitsize -= src_pos;
1108  if (src_count > src_bitsize)
1109  src_count = src_bitsize;
1110  else
1111  src_bitsize = src_count;
1112 
1113  Size src_index = (src_pos / BITS);
1114  const Size src_offset = src_pos - (src_index * BITS);
1115  const Size src_offset_end = src_offset + src_count;
1116  const T* src_p = src_data + src_index;
1117  if (src_offset_end <= BITS) {
1118  // All in 1 chunk
1119  *data = (*data & ~(ALLBITS << src_offset)) | ((*src_p & (ALLBITS >> src_offset)) << src_offset);
1120  } else if (src_offset > 0) {
1121  // Copy each chunk while reading with offset
1122  const Size leadbits = (BITS - src_offset);
1123  T maskval1 = ALLBITS >> src_offset;
1124  T maskval2 = ~maskval1;
1125  while (src_count >= BITS) {
1126  src_count -= BITS;
1127  *data = ((*src_p & maskval1) << src_offset) | ((src_p[1] & maskval2) >> leadbits);
1128  ++src_p;
1129  ++data;
1130  }
1131  // Last partial chunk
1132  if (src_count > 0) {
1133  maskval1 = ALLBITS >> src_count;
1134  maskval2 = ~maskval1;
1135  *data = (*data & maskval1) | ((*src_p << src_offset) & maskval2);
1136  }
1137  } else {
1138  // Copy full chunks
1139  while (src_count >= BITS) {
1140  src_count -= BITS;
1141  *data = *src_p;
1142  ++data;
1143  ++src_p;
1144  }
1145  // Last partial chunk
1146  if (src_count > 0) {
1147  const T maskval = ALLBITS >> src_count;
1148  *data = (*data & maskval) | (*src_p & ~maskval);
1149  }
1150  }
1151  return src_bitsize;
1152  }
1153  return 0;
1154  }
1155 
1163  static void array_shiftl(T* data, Size bitsize, uint count) {
1164  assert( !IntegerT<T>::SIGN );
1165  assert( count >= 0 );
1166  if (bitsize > 0) {
1167  if (count >= bitsize) {
1168  array_set_multi(data, bitsize, 0, ALL, false);
1169  } else {
1170  const Size chunks = count / BITS;
1171  const Size offset = count - (chunks * BITS);
1172  T* p_out = data;
1173  const T* p_in = data + chunks;
1174  const T* p_end = data + (bitsize / BITS);
1175  if (offset > 0) {
1176  // Shift with offset
1177  const Size rbits = BITS - offset;
1178  const T* p_shift_end = p_end - chunks - 1;
1179  while (p_out < p_shift_end) {
1180  *p_out = (*p_in << offset) | (p_in[1] >> rbits);
1181  ++p_out;
1182  ++p_in;
1183  }
1184  *p_out = (*p_in << offset);
1185  ++p_out;
1186  } else {
1187  // Shift full chunks
1188  const T* p_shift_end = p_end - chunks;
1189  while (p_out < p_shift_end) {
1190  *p_out = *p_in;
1191  ++p_out;
1192  ++p_in;
1193  }
1194  }
1195 
1196  // Clear remaining chunks
1197  for (; p_out < p_end; ++p_out)
1198  *p_out = 0;
1199  }
1200  }
1201  }
1202 
1210  static void array_shiftr(T* data, Size bitsize, uint count) {
1211  assert( !IntegerT<T>::SIGN );
1212  if (bitsize > 0) {
1213  if (count >= bitsize) {
1214  array_set_multi(data, bitsize, 0, ALL, false);
1215  } else {
1216  const Size chunks = count / BITS;
1217  const Size offset = count - (chunks * BITS);
1218  T* p_out = data + ((bitsize + (BITS-1)) / BITS);;
1219  const T* p_in = p_out - chunks - 1;
1220  if (offset > 0) {
1221  // Shift with offset
1222  const Size lbits = BITS - offset;
1223  const T* p_shift_end = data + chunks + 1;
1224  const Size partial_tail = bitsize % BITS;
1225  if (partial_tail > 0) {
1226  // Mask out unused bits at end
1227  if (p_out > p_shift_end) {
1228  --p_in;
1229  *--p_out = ((*p_in << lbits) | (p_in[1] >> offset)) & ~(ALLBITS >> partial_tail);
1230  } else {
1231  *--p_out = (*p_in >> offset) & ~(ALLBITS >> partial_tail);
1232  return;
1233  }
1234  }
1235  while (p_out > p_shift_end) {
1236  --p_in;
1237  *--p_out = (*p_in << lbits) | (p_in[1] >> offset);
1238  }
1239  *--p_out = (*p_in >> offset);
1240  } else {
1241  // Shift full chunks
1242  const T* p_shift_end = data + chunks;
1243  while (p_out > p_shift_end) {
1244  *--p_out = *p_in;
1245  --p_in;
1246  }
1247  }
1248 
1249  // Clear remaining chunks
1250  while (p_out > data)
1251  *--p_out = 0;
1252  }
1253  }
1254  }
1255 };
1256 
1258 
1259 }
1260 #if defined(_MSC_VER)
1261  #pragma warning(pop)
1262 #endif
1263 #endif
evo::Bits::IterState::data
const T * data
Definition: bits.h:616
evo::Bits::array_set_multi
static Size array_set_multi(T *data, Size bitsize, Size pos=0, Size count=ALL, bool value=true)
Set or clear count bits at position in chunked bit array.
Definition: bits.h:746
evo::Bits::array_iternext
static Size array_iternext(IterState &state)
Iterate to next set bit in array.
Definition: bits.h:664
evo::Bits::array_toggle
static bool array_toggle(T *data, Size bitsize, Size pos)
Toggle bit at position in chunked bit array.
Definition: bits.h:815
evo::Bits::array_get
static bool array_get(const T *data, Size bitsize, Size pos)
Get bit at position from chunked bit array.
Definition: bits.h:702
evo::Bits::array_shiftl
static void array_shiftl(T *data, Size bitsize, uint count)
Shift to the left in chunked bit array.
Definition: bits.h:1163
evo::bits_clz64
uint bits_clz64(uint64 mask)
Get leading zero count on bitmask (uint64).
Definition: bits.h:295
evo::Bits::IterState::size
Size size
Definition: bits.h:617
evo::bits_clz16
uint bits_clz16(uint16 mask)
Get leading zero count on bitmask (uint16).
Definition: bits.h:275
evo::bits_clz
uint bits_clz(T mask)
Get leading zero count on bitmask.
Definition: bits.h:255
evo::Bits::array_checkall
static bool array_checkall(const T *data, Size bitsize)
Check if all bits are set in bit array.
Definition: bits.h:486
evo::Bits::align_right
static T align_right(T value, uint count)
Align bits on left to the right.
Definition: bits.h:343
evo::Bits::array_extractl
static U array_extractl(const T *data, Size bitsize, Size pos, Size count)
Extract bits from chunked bit array.
Definition: bits.h:963
evo::Bits::align_left
static T align_left(T value, uint count)
Align bits on right to the left.
Definition: bits.h:329
evo::bits_popcount
int bits_popcount(T mask)
Get population count (number of bits set) for value.
Definition: bits.h:242
evo::IntegerT
Basic integer type.
Definition: type.h:980
evo::Bits::array_countbits
static Size array_countbits(const T *data, Size bitsize, Size pos, Size count)
Count number of set bits in subset of bit array.
Definition: bits.h:436
evo::Bits::array_toggle_multi
static Size array_toggle_multi(T *data, Size bitsize, Size pos=0, Size count=ALL)
Toggle count bits at position in chunked bit array.
Definition: bits.h:835
evo::Bits::array_store
static bool array_store(T *data, Size bitsize, Size pos, Size count, U value)
Stores bits in chunked bit array.
Definition: bits.h:895
evo::Bits::array_copy
static Size array_copy(T *data, Size bitsize, T *src_data, Size src_bitsize, Size src_pos=0, Size src_count=ALL)
Copy bits from another array.
Definition: bits.h:1100
evo::Bits::IterState::IterState
IterState()
Definition: bits.h:622
evo::bits_clz8
uint bits_clz8(uint8 mask)
Get leading zero count on bitmask (uint8).
Definition: bits.h:265
evo::ToUnsigned::Type
T Type
Translated type.
Definition: meta.h:373
evo::Bits::array_checkany
static bool array_checkany(const T *data, Size bitsize, Size pos, Size count)
Check if any bits are set in subset of bit array.
Definition: bits.h:571
evo::Bits::array_countbits
static Size array_countbits(const T *data, Size bitsize)
Count number of set bits in bit array.
Definition: bits.h:418
evo::ALL
static const EndT ALL
Special integer value for indicating all items or all remaining items.
Definition: type.h:1839
evo::Bits::array_extractr
static U array_extractr(const T *data, Size bitsize, Size pos, Size count)
Extract bits from chunked bit array.
Definition: bits.h:1033
evo::Bits::Value
T Value
Chunk value type.
Definition: bits.h:310
evo::Bits::IterState::pos
Size pos
Definition: bits.h:619
evo::Bits::mask
static T mask(uint start, uint count)
Get bitmask with count bits set from start position.
Definition: bits.h:358
evo::bits_clz32
uint bits_clz32(uint32 mask)
Get leading zero count on bitmask (uint32).
Definition: bits.h:285
evo
Evo C++ Library namespace.
Definition: alg.h:11
evo::NONE
static const EndT NONE
Special integer value for indicating no item or unknown item.
Definition: type.h:1832
evo::Bits::safemask
static T safemask(uint start, uint count)
Get bitmask with count bits set from start position, with bounds checking for safety.
Definition: bits.h:374
evo::Bits::array_set
static bool array_set(T *data, Size bitsize, Size pos, bool value=true)
Set or clear bit at position in chunked bit array.
Definition: bits.h:721
evo::Bits::array_checkall
static bool array_checkall(const T *data, Size bitsize, Size pos, Size count)
Check if all bits are set in subset of bit array.
Definition: bits.h:508
evo::bits_cpu_popcnt
bool bits_cpu_popcnt()
Runtime check whether current CPU supports the POPCNT instruction.
Definition: bits.h:231
evo::Bits::array_iter
static Size array_iter(IterState &state, const T *data, Size bitsize)
Iterate to first set bit in array.
Definition: bits.h:641
evo::Bits::IterState
Bit array iteration state.
Definition: bits.h:615
evo::Bits::array_shiftr
static void array_shiftr(T *data, Size bitsize, uint count)
Shift to the right in chunked bit array.
Definition: bits.h:1210
evo::Bits::IterState::index
Size index
Definition: bits.h:618
evo::Bits::array_size
static Size array_size(Size bitsize)
Calculate array size in chunks for number of bits.
Definition: bits.h:396
evo::Bits::Size
TSize Size
Size integer type.
Definition: bits.h:311
evo::Bits::IterState::chunk
T chunk
Definition: bits.h:620
evo::Bits
Traits and helpers for bit manipulation.
Definition: bits.h:309
evo::Bits::array_bitsize
static Size array_bitsize(Size chunks)
Calculate array size in bits for number of chunks.
Definition: bits.h:407
type.h
Evo basic types and traits.
evo::Bits::array_checkany
static bool array_checkany(const T *data, Size bitsize)
Check if any bits are set in bit array.
Definition: bits.h:555
Generated on Tue May 7 2019 18:17:25 for Evo C++ Library v0.5.1 by   doxygen 1.8.13