1  // [License]


2  // The AribaUnderlay Copyright


3  //


4  // Copyright (c) 20082009, Institute of Telematics, UniversitÃ€t Karlsruhe (TH)


5  //


6  // Institute of Telematics


7  // UniversitÃ€t Karlsruhe (TH)


8  // Zirkel 2, 76128 Karlsruhe


9  // Germany


10  //


11  // Redistribution and use in source and binary forms, with or without


12  // modification, are permitted provided that the following conditions are


13  // met:


14  //


15  // 1. Redistributions of source code must retain the above copyright


16  // notice, this list of conditions and the following disclaimer.


17  // 2. Redistributions in binary form must reproduce the above copyright


18  // notice, this list of conditions and the following disclaimer in the


19  // documentation and/or other materials provided with the distribution.


20  //


21  // THIS SOFTWARE IS PROVIDED BY THE INSTITUTE OF TELEMATICS ``AS IS'' AND


22  // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE


23  // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR


24  // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE ARIBA PROJECT OR


25  // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,


26  // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,


27  // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR


28  // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF


29  // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING


30  // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS


31  // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


32  //


33  // The views and conclusions contained in the software and documentation


34  // are those of the authors and should not be interpreted as representing


35  // official policies, either expressed or implied, of the Institute of


36  // Telematics.


37  // [License]


38 


39  /* This file implements some common bit operations for unsigned integer types


40  * and arrays. There are two different approaches in indexing bits inside arrays


41  * and integrals:


42  *


43  * In simple integer types the least significant bit (LSB) is identified by index zero.


44  * A length is specified from the LSB to the MSB. On the other hand, there is an


45  * inverted form of this representation. In this case, the MSB is identfied by index


46  * zero and the length identifies a range from the MSB to the LSB.


47  *


48  * Normal Inverted


49  * MSB LSB MSB LSB


50  * v v v v


51  * ++ ++


52  *  uint16_t   uint16_t 


53  * ++ ++


54  * ^ ^ ^ ^


55  * Index 15 0 0 15


56  * Length <+ +>


57  *


58  * Inside arrays the inverted form is used. Therefore an index of zero identifies the


59  * MSB of the first word in the array.


60  *


61  * TODO: TBC


62  */


63  #ifndef DATAUTILITIES_HPP_


64  #define DATAUTILITIES_HPP_


65 


66  #include "../internal/Utilities.hpp"


67 


68  #include <boost/cstdint.hpp>


69 


70  #include <memory>


71  #include <string>


72 


73  template<typename X> finline


74  static X shr( const X& value, unsigned int bits ) {


75  return (sizeof(X)*8 == bits) ? 0 : (value >> bits);


76  }


77 


78  template<typename X> finline


79  static X shl( const X& value, unsigned int bits ) {


80  return (sizeof(X)*8 == bits) ? 0 : (value << bits);


81  }


82 


83  /**


84  * TODO: Doc


85  */


86  template<typename X> finline


87  static X bitblk(size_t index, size_t length, bool value, if_uint(X)) {


88  if (index == 0 && length >= sizeof(X) * 8) return value ? ~0 : 0;


89  X x = shl(( shl( ((X) 1), length)  1), index);


90  return value ? x : ~x;


91  }


92 


93  /**


94  * TODO: Doc


95  */


96  template<typename X, bool value> finline


97  static X bitblk(size_t index, size_t length, if_uint(X)) {


98  return bitblk<X> (index, length, value);


99  }


100 


101  /**


102  * TODO: Doc


103  */


104  template<typename X, bool value> finline


105  static X bitblk(size_t length, if_uint(X)) {


106  if (length >= sizeof(X) * 8) return value ? ~0 : 0;


107  return value ? (((X) 1 << length)  1) : ~(((X) 1 << length)  1);


108  }


109 


110  /**


111  * This method copies bits from one integral to another


112  */


113  template<typename X, typename Y> finline


114  static Y bitcpy(X src, size_t srcIdx, Y dst, size_t dstIdx, size_t len =


115  sizeof(X) * 8, bool srcInvert = false, bool dstInvert = false,


116  if_uint(X),if_uint (Y) ) {


117  if (srcInvert) srcIdx = sizeof(X) * 8  srcIdx  len;


118  if (dstInvert) dstIdx = sizeof(Y) * 8  dstIdx  len;


119  Y value = ((Y)shr(src, srcIdx)) << dstIdx;


120  Y mask = bitblk<Y, 0> (dstIdx, len);


121  return (dst & mask)  (value & ~mask);


122  }


123 


124  /**


125  * This method copies bits from an array to another of the same


126  * integral type.


127  */


128  template<typename X> finline


129  static void bitcpy(X* src, size_t srcIdx, X* dst, size_t dstIdx, size_t len) {


130 


131  // word width


132  const size_t w = sizeof(X) * 8;


133 


134  // calculate indexes


135  size_t dwp = dstIdx % w, swp = srcIdx % w;


136  size_t idwp = w  dwp, iswp = w  swp;


137  dst += dstIdx / w;


138  src += srcIdx / w;


139 


140  // check direct copy


141  if (dwp == 0 && swp == 0 && len % w == 0) {


142  memcpy(dst, src, len / 8);


143  return;


144  }


145 


146  // check if first word only is affected


147  if ((dwp + len) <= w) {


148  X fw = shl(src[0],swp)  shr(src[1],iswp);


149  *dst = bitcpy(fw, 0, *dst, dwp, len, true, true);


150  return;


151  }


152 


153  // set first word


154  if (idwp != 0) {


155  X fw = shl(src[0],swp)  shr(src[1],iswp);


156  *dst = (*dst & ~(((X) 1 << idwp)  1))  shr(fw,dwp);


157 


158  // recalculate indexes & lengths


159  dst++;


160  src++;


161  len = idwp;


162  swp = (swp + idwp) % w;


163  iswp = w  swp;


164  }


165 


166  X a, b;


167 


168  // copy whole words


169  if (swp == 0) {


170  size_t numWords = len / w;


171  // use memory copy


172  memcpy(dst, src, numWords * sizeof(X));


173  src += numWords;


174  dst += numWords;


175  len = len % w;


176  a = src[0], b = src[1];


177  } else {


178  // use shifted copy


179  a = src[0], b = src[1];


180  while (len >= w) {


181  *dst = shl(a,swp)  shr(b,iswp);


182  dst++;


183  src++;


184  len = w;


185  a = b;


186  b = *src;


187  }


188  }


189 


190  // set last word


191  X lw = shl(a,swp)  shr(b,iswp), lm = (shl((X) 1,(w  len))  1);


192  *dst = (*dst & lm)  (lw & ~lm);


193  }


194 


195 


196 


197  /**


198  * array > integral


199  */


200  template<typename X, typename Y> finline


201  static void bitcpy(X* src, size_t srcIdx, Y& dst, size_t dstIdx, size_t len =


202  sizeof(Y) * 8, if_uint(Y),if_uint (X) ) {


203 


204  // word width


205  const size_t w = sizeof(X) * 8;


206 


207  // calculate indexes


208  size_t swp = srcIdx % w, iswp = w  swp;


209  src += srcIdx / w;


210 


211  // mask off bits


212  dst &= bitblk<Y,0>(dstIdx,len);


213 


214  // copy whole words


215  X a = src[0], b = src[1];


216  Y value = 0;


217  src++;


218  while (len >= w) {


219  X x = shl(a,swp)  shr(b,iswp);


220  value <<= w;


221  value = x;


222  src++;


223  len = w;


224  a = b; b = *src;


225  }


226 


227  // copy leftover


228  if ( len> 0 ) {


229  value <<= len;


230  value = ((shl(a,swp)  shr(b,iswp)) >> (w  len)) & (shl(1,len)1);


231  }


232 


233  // set value


234  dst = (value << dstIdx);


235  }


236 


237  /**


238  * TODO: Doc


239  */


240  // word > array


241  template<typename X> finline


242  static void bitcpy(X src, size_t srcIdx, X* dst, size_t dstIdx, size_t len =


243  sizeof(X) * 8, bool srcInvert = false, if_uint(X)) {


244 


245  // check inversion


246  if (srcInvert) srcIdx = sizeof(X) * 8  srcIdx  len;


247 


248  // word width


249  const size_t w = sizeof(X) * 8;


250 


251  // calculate indexes


252  size_t dwp = dstIdx % w;


253  dst += dstIdx / w;


254 


255  // copy directly


256  if (dwp == 0 && srcIdx == 0 && len == w) {


257  *dst = src;


258  } else


259 


260  // copy nonoverlapping word


261  if ((dwp + len) <= w) {


262  *dst = bitcpy(src, srcIdx, *dst, dwp, len, false, true);


263 


264  // copy overlapping word


265  } else {


266  size_t idwp = w  dwp;


267  src >>= srcIdx;


268  X mask1 = ~(shl(1,idwp)  1);


269  dst[0] = (dst[0] & mask1)  (shr(src,(len  idwp)) & ~mask1);


270  X mask2 = shl(1,(w  len + idwp))  1;


271  dst[1] = (dst[1] & mask2)  (shl(src, (w  len + idwp)) & ~mask2);


272  }


273  }


274 


275  /**


276  * TODO: Doc


277  */


278  // integral > array


279  template<typename Y, typename X> finline


280  static void bitcpy(Y src, size_t srcIdx, X* dst, size_t dstIdx, size_t len =


281  sizeof(Y) * 8, bool srcInvert = false, if_uint(X),if_uint (Y) ) {


282 


283  if (sizeof(Y) <= sizeof(X)) {


284  // check inversion


285  if (srcInvert)


286  srcIdx = sizeof(Y) * 8  srcIdx  len + (sizeof(X)sizeof(Y))*8;


287  bitcpy((X)src,srcIdx,dst,dstIdx,len,false);


288  } else {


289  // check inversion


290  if (srcInvert) srcIdx = sizeof(Y) * 8  srcIdx  len;


291  src = shr(src, srcIdx);


292 


293  const size_t dw = sizeof(X)*8;


294  while (len >= dw) {


295  X word = (X)shr(src,(lendw));


296  bitcpy(word,0,dst,dstIdx,dw);


297  dstIdx += dw;


298  len = dw;


299  }


300  X word = (X)src;


301  bitcpy(word,0,dst,dstIdx,len);


302  }


303  }


304 


305  /**


306  * TODO: Doc


307  */


308  template<typename T, typename X> finline


309  static T bitget(X* src, size_t idx, size_t len = sizeof(T) * 8, if_uint(X),if_uint (T) ) {


310  T x = 0;


311  bitcpy(src, idx, x, 0, len );


312  return x;


313  }


314 


315  /**


316  * TODO: Doc


317  */


318  template<typename T, typename X> finline


319  static T bitget(X src, size_t idx, size_t len = sizeof(T) * 8, if_uint(X),if_uint (T) ) {


320  T x = 0;


321  bitcpy(src, idx, x, 0, len );


322  return x;


323  }


324 


325  /**


326  * TODO: Doc


327  */


328  template<typename X> finline


329  static bool bitget(X* src, size_t index, if_uint(X)) {


330  uint8_t x = 0;


331  bitcpy(src, index, x, 0, 1);


332  return x != 0;


333  }


334 


335  /**


336  * TODO: Doc


337  */


338  template<typename X> finline


339  static bool bitget(X src, size_t index, if_uint(X)) {


340  uint8_t x = 0;


341  x = bitcpy(src, index, x, 0, 1);


342  return x != 0;


343  }


344 


345  /**


346  * TODO: Doc


347  */


348  template<typename T, typename X> finline


349  static void bitset(T src, X* dst, size_t index, if_uint(X),if_uint (T) ) {


350  bitcpy(src,0,dst,index);


351  }


352 


353  /**


354  * TODO: Doc


355  */


356  template<typename X> finline


357  static void bitset(bool src, X* dst, size_t index, if_uint(X) ) {


358  bitcpy(src != 0, 0, dst, index, 1);


359  }


360 


361  /**


362  * TODO: Doc


363  */


364  template<typename X> finline


365  static X bitset(bool src, X dst, size_t index, if_uint(X)) {


366  return bitcpy(src != 0, 0, dst, index, 1);


367  }


368 


369  /**


370  * TODO: Doc


371  */


372  template<typename X> finline


373  static X bitrev(X src, if_uint(X) ) {


374  const size_t width = sizeof(X) * 8;


375  X dst = 0;


376  for (size_t i = 0; i < width; i++)


377  dst = bitset(bitget(src, i), dst, width  i  1);


378  return dst;


379  }


380 


381  /**


382  * TODO: Doc


383  */


384  template<typename X> finline


385  static void bitrev(X* src, size_t len, if_uint(X) ) {


386  for (size_t i = 0; i < len / 2; i++) {


387  bool b0 = bitget(src, i);


388  bool b1 = bitget(src, len  i  1);


389  bitset(b1, src, i);


390  bitset(b0, src, len  i  1);


391  }


392  }


393 


394  /**


395  * TODO: Doc


396  */


397  template<typename X> finline


398  static X switch_endian(X src, if_uint(X) ) {


399  if (sizeof(X) == 1) return src;


400  X ret = 0;


401  for (size_t i = 0; i < sizeof(X); i++) {


402  ret <<= 8;


403  ret = src & 0xFF;


404  src >>= 8;


405  }


406  return ret;


407  }


408 


409  /**


410  * TODO: Doc


411  */


412  template<typename X> finline


413  static std::string bitstr(X src, int log2base = 4, if_uint(X)) {


414  const size_t word_width = sizeof(src) * 8;


415  const char digit[37] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";


416 


417  std::string str;


418  for (int i = word_width  log2base, j = 0; i >= 0; i = log2base, j++)


419  str.append(1, digit[(src >> i) & ((1 << log2base)  1)]);


420  return str;


421  }


422 


423  /**


424  * TODO: Doc


425  */


426  template<typename X> finline


427  static std::string bitstr(X* src, size_t len, int log2base = 4, bool dot =


428  false, if_uint(X)) {


429  std::string str;


430  for (size_t i = 0; i < len / 8 / sizeof(X); i++) {


431  if (i != 0 && dot) str.append(".");


432  str.append(bitstr(src[i], log2base));


433  }


434  return str;


435  }


436 


437  #endif /* DATAUTILITIES_HPP_ */

