bit_storage.h

00001 /* 
00002  * File:   bit_storage.h
00003  * Author: jdaniels
00004  *
00005  * Created on September 22, 2015, 7:24 AM
00006  */
00007 
00008 #ifndef BIT_STORAGE_H
00009 #define BIT_STORAGE_H
00010 #include <limits>
00011 #include <stdint.h>
00012 
00013 #define ELEMENTS_NEEDED(bits,TUnitOfStorage) \
00014     ( \
00015         size_t((bits)/(sizeof(TUnitOfStorage)*8)) \
00016         + \
00017         size_t( \
00018            ( \
00019               (((bits) % (sizeof(TUnitOfStorage)*8)) > 0 ? 1 : 0) \
00020            ) \
00021          ) \
00022     )
00023     
00024 #define BYTES_NEEDED(bits) (ELEMENTS_NEEDED(bits,uint8_t))
00025 
00026 template<
00027     size_t BitsOfData, 
00028     class TUnitOfStorage=uint8_t,
00029     bool MSBInIndexZero=true>
00030 struct bit_storage_t
00031 {
00032     
00033     typedef bit_storage_t<BitsOfData,TUnitOfStorage,MSBInIndexZero> data_type;
00034     typedef TUnitOfStorage element_type;    
00035 
00036     private:
00037     
00038     element_type _elements[ELEMENTS_NEEDED(BitsOfData,element_type)];
00039     
00040     public:
00041     
00042     // Get an element sized bit mask with the first n-bits, masked on (1). 
00043     // Default is all bits for the element type turned on. Explicitly passing 0 or a value greater than the 
00044     // number of bits per element has the same result.
00045     static const element_type element_mask(size_t bits=0) { 
00046         element_type all_bits=std::numeric_limits<element_type>::max();
00047         if (bits==0||bits>BitsOfData)
00048             return all_bits;
00049         return (all_bits >> (BitsOfData-bits));
00050     }
00051     
00052     static size_t bits_per_element() { return (sizeof(element_type)*8); }
00053     
00054     inline element_type& element(const size_t& index) { 
00055         return _elements[index];
00056     }
00057 
00058     inline size_t element_index_of(const size_t& bit) {
00059         return MSBInIndexZero ? (element_count()-1) - (ELEMENTS_NEEDED(bit+1,element_type)-1) : ELEMENTS_NEEDED(bit+1,element_type)-1;
00060     }
00061 
00062     inline element_type& element_for(const size_t& bit) { 
00063         return element(element_index_of(bit)); 
00064     }
00065 
00066     inline element_type* elements() { return _elements; }
00067 
00068         inline uint8_t& byte(const size_t& index) { 
00069         return bytes()[index];
00070     }
00071 
00072     inline size_t byte_index_of(const size_t& bit) {
00073         return MSBInIndexZero ? (byte_count()-1) - (BYTES_NEEDED(bit+1)-1) : BYTES_NEEDED(bit+1)-1;
00074     }
00075 
00076 
00077     inline uint8_t& byte_for(const size_t& bit) { 
00078         return byte(byte_index_of(bit)); 
00079     }
00080 
00081     inline uint8_t* bytes() { return (uint8_t*) _elements; }
00082 
00083     inline size_t bit_size() { return BitsOfData; }
00084 
00085     inline size_t element_count() { 
00086         return sizeof(_elements)/sizeof(element_type);//ELEMENTS_NEEDED(BitsOfData,element_type);
00087     }
00088 
00089      inline size_t element_size() { return sizeof(element_type); }
00090      inline size_t element_bit_size() { return element_size()*8; }
00091      inline size_t byte_count() { return sizeof(_elements); }
00092 
00093     inline element_type element_mask_for(size_t bit) {
00094         return element_type(1) << element_type(bit % bits_per_element());
00095     }
00096 
00097     inline void set(const size_t& bit, const bool& value=true)
00098     { 
00099         if (value)
00100             element_for(bit) |= element_mask_for(bit);
00101         else
00102             clear(bit);
00103     }
00104 
00105     inline void toggle(const size_t& bit)
00106     { 
00107         element_for(bit) ^= element_mask_for(bit);
00108     }
00109 
00110     inline void clear(const size_t& bit) {
00111         element_for(bit) &= ~element_mask_for(bit);
00112     }
00113     
00114     inline bool get(const size_t& bit)
00115     { 
00116         return element_for(bit) & element_mask_for(bit);
00117     }
00118     
00119     inline void set_all() {
00120         //memset(_elements,0xFF,sizeof(_elements));
00121         const element_type mask=element_mask();
00122         for(size_t idx=0;idx<element_count();idx++)
00123         {
00124             _elements[idx]=mask;
00125         }
00126     }
00127     
00128     inline void toggle_all() {
00129         
00130         const element_type mask=element_mask();
00131         for(size_t idx=0;idx<element_count();idx++)
00132         {
00133             _elements[idx] ^=mask;
00134         }
00135         
00136     }
00137 
00138     inline void clear_all() {
00139         /*
00140         const element_type mask=element_mask();
00141         for(size_t idx=0;idx<element_count();idx++)
00142         {
00143             _elements[idx] =0;
00144         }*/
00145         memset(_elements,0x00,sizeof(_elements));
00146     }
00147     
00148     inline bool calc_window_endpoint_crossed(const size_t& bit, const bool& is_msb=true)
00149     {
00150         if (is_msb) {
00151             return (bit < (element_bit_size()-1));
00152         }
00153         else {
00154             return (bit > (BitsOfData-(element_bit_size()-1)));
00155         }        
00156     }
00157     
00158     inline size_t msb_index_for(const size_t& bit, const bool& is_msb=true)
00159     {
00160         size_t element_high_bit = element_bit_size()-1;
00161         size_t msb = (is_msb || (bit + element_high_bit >= BitsOfData)) ?
00162                      bit : bit + element_high_bit;
00163             
00164         return element_index_of(msb);
00165     }
00166     
00167     inline size_t lsb_index_for(const size_t& bit, const bool& is_msb=false)
00168     {
00169         size_t lsb=bit;
00170         if (is_msb && bit >= element_bit_size()) 
00171             lsb=bit-(element_bit_size()-1);
00172         return element_index_of(lsb);
00173     }
00174 
00175     /**
00176         retrieve an element-sized window of bits starting with the specified bit.
00177         
00178             @param bit the bit offset to retrieve the window from
00179             @param is_msb indicates if the bit is the most significant bit.
00180     */
00181     inline element_type get_window(const size_t& bit, const bool& is_msb=true) {
00182         size_t msb_idx = msb_index_for(bit,is_msb);
00183         size_t lsb_idx = lsb_index_for(bit,is_msb);
00184         
00185         if (msb_idx == lsb_idx && !calc_window_endpoint_crossed(bit,is_msb)) 
00186             return _elements[msb_idx];
00187         element_type msb_element = _elements[msb_idx];
00188         element_type lsb_element = _elements[lsb_idx];
00189         size_t msb= is_msb ? bit : bit + element_bit_size()-1;
00190         size_t lsb_shift = ((msb + 1) % element_bit_size());
00191         size_t msb_shift = element_bit_size() - lsb_shift;
00192 
00193         if (calc_window_endpoint_crossed(bit,is_msb)) {
00194             if (is_msb)
00195                 return element_type(msb_element << msb_shift) >>msb_shift;
00196             else
00197                 return element_type(lsb_element >> lsb_shift);
00198         }
00199         return element_type(msb_element << msb_shift) | element_type(lsb_element>>lsb_shift);        
00200     }
00201     
00202     /**
00203         Applies the bits from an element to a window of bits within the storage. used during shift operations.
00204     */
00205     inline void set_window(const size_t& bit, const element_type& data, const bool& is_msb=true) {
00206         size_t msb_idx = msb_index_for(bit,is_msb);
00207         size_t lsb_idx = lsb_index_for(bit,is_msb);
00208         
00209         if (msb_idx == lsb_idx && !calc_window_endpoint_crossed(bit,is_msb)) 
00210             _elements[msb_idx]=data;
00211             
00212         element_type& msb_element = _elements[msb_idx];
00213         element_type& lsb_element = _elements[lsb_idx];
00214         /*
00215          * Take bits msb through 0, split on the element boundary at bit position N
00216          * place bits msb to msb-N of data into msb-N to 0 of the msb element.
00217          * place msb
00218          */                
00219         size_t msb= is_msb ? bit : bit + element_bit_size()-1;
00220         size_t lsb=  msb - (element_bit_size()-1);
00221         
00222         size_t split = ((msb + 1) % element_bit_size());
00223         
00224         size_t lsb_shift = split;
00225         size_t msb_shift = element_bit_size() - lsb_shift;
00226         
00227         element_type msb_data_mask = (~element_type(0)) << msb_shift;
00228         element_type lsb_data_mask = (~element_type(0)) >> lsb_shift;
00229         element_type msb_data = (data & msb_data_mask) >> msb_shift;
00230         element_type lsb_data = (data & lsb_data_mask) << lsb_shift;
00231         element_type msb_kept = msb_element & ~(msb_data_mask);
00232         element_type lsb_kept = lsb_element & ~(lsb_data_mask);
00233         
00234         element_type msb_new = msb_kept | msb_data;
00235         element_type lsb_new = lsb_kept | lsb_data;
00236         if (!calc_window_endpoint_crossed(bit,is_msb)) {
00237             msb_element = msb_new;
00238             lsb_element = lsb_new;
00239         }
00240         else if (is_msb) {
00241             msb_element = msb_new;
00242         }
00243         else {
00244             lsb_element = lsb_new;
00245         }    
00246     }
00247 
00248     inline void __rs_msb_zero(const size_t& n, const int& ws, const int& s, const int& s1){
00249         int i=element_count()-1;
00250         if (s==0) {
00251             for(;i>=ws;i--) 
00252                 _elements[i]=_elements[i-ws];
00253         }
00254         else {
00255             for(;i>ws;i--) 
00256                 _elements[i]= element_type(_elements[i-ws] >> s) | element_type(_elements[i-ws-1] << s1);
00257 
00258             _elements[ws] = element_type(_elements[0] >> s);
00259         }
00260         for (i=ws-1;i>=0;i--)
00261                _elements[i]=0;
00262     }
00263     
00264     inline void __rs_lsb_zero(const size_t& n, const int& ws, const int& s, const int& s1){
00265         const int z= element_count()- ws -1;
00266         int i=0;
00267         if (s==0) {
00268             for(;i<=z;i++)
00269                 _elements[i]= _elements[i+ws];
00270         }
00271         else
00272         {
00273             for(;i<z;i++)            
00274                 _elements[i] = ((_elements[i + ws] >> s) | (_elements[i + ws + 1] << s1));
00275             
00276             _elements[z] = _elements[element_count()-1] >> s;
00277         }   
00278         for(i=z+1;i<element_count();i++)
00279             _elements[i]=0;
00280     }
00281 
00282     inline void __ls_lsb_zero(const size_t& n, const int& ws, const int& s, const int& s1){
00283         int i=element_count()-1;
00284         if (s==0) {
00285             for(;i>ws;i--) 
00286                 _elements[i]=_elements[i-ws];
00287         }
00288         else {
00289             for(;i>ws;i--) 
00290                 _elements[i]= element_type(_elements[i-ws] << s) | element_type(_elements[i-ws-1] >> s1);
00291 
00292             _elements[ws] = element_type(_elements[0] << s);
00293         }
00294         for (i=ws-1;i>=0;i--)
00295                _elements[i]=0;        
00296     }
00297     
00298     inline void __ls_msb_zero(const size_t& n, const int& ws, const int& s, const int& s1){
00299         const int z= element_count()- ws -1;
00300         int i=0;
00301         if (s==0) {
00302             for(;i<=z;i++)
00303                 _elements[i]= _elements[i+ws];
00304         }
00305         else
00306         {
00307             for(;i<z;i++)            
00308                 _elements[i] = ((_elements[i + ws] << s) | (_elements[i + ws + 1] >> s1));
00309             
00310             _elements[z] = _elements[element_count()-1] << s;
00311         }   
00312         for(i=z+1;i<element_count();i++)
00313             _elements[i]=0;
00314     }
00315         
00316     inline void shift_right(const size_t& n) {
00317         if (n>=BitsOfData) {
00318             memset(_elements,0,sizeof(_elements));
00319             return;
00320         }
00321 
00322         const int ws=n/element_bit_size();
00323         const int s=n%element_bit_size();
00324         const int s1=element_bit_size()-s;
00325         
00326         if (MSBInIndexZero)
00327             __rs_msb_zero(n,ws,s,s1);
00328         else
00329             __rs_lsb_zero(n,ws,s,s1);
00330     }
00331     
00332     inline void shift_left(const size_t& n) {
00333         if (n>=BitsOfData) {
00334             memset(_elements,0,sizeof(_elements));
00335             return;
00336         }
00337 
00338         const int ws=n/element_bit_size();
00339         const int s=n%element_bit_size();
00340         const int s1=element_bit_size()-s;
00341         
00342         if (MSBInIndexZero)
00343             __ls_msb_zero(n,ws,s,s1);
00344         else
00345             __ls_lsb_zero(n,ws,s,s1);        
00346     }    
00347 
00348 };
00349 
00350 #endif  /* BIT_STORAGE_H */
00351