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  /**


74  * TODO: Doc


75  */


76  template<typename X> finline


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


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


79  X x = ((((X) 1) << length)  1) << index;


80  return value ? x : ~x;


81  }


82 


83  /**


84  * TODO: Doc


85  */


86  template<typename X, bool value> finline


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


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


89  }


90 


91  /**


92  * TODO: Doc


93  */


94  template<typename X, bool value> finline


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


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


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


98  }


99 


100  /**


101  * This method copies bits from one integral to another


102  */


103  template<typename X, typename Y> finline


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


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


106  if_uint(X),if_uint (Y) ) {


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


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


109  Y value = ((Y) (src >> srcIdx)) << dstIdx;


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


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


112  }


113 


114  /**


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


116  * integral type.


117  */


118  template<typename X> finline


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


120 


121  // word width


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


123 


124  // calculate indexes


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


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


127  dst += dstIdx / w;


128  src += srcIdx / w;


129 


130  // check direct copy


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


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


133  return;


134  }


135 


136  // check if first word only is affected


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


138  X fw = (src[0] << swp)  (src[1] >> iswp);


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


140  return;


141  }


142 


143  // set first word


144  if (idwp != 0) {


145  X fw = (src[0] << swp)  (src[1] >> iswp);


146  *dst = (*dst & ~(((X) 1 << idwp)  1))  (fw >> dwp);


147 


148  // recalculate indexes & lengths


149  dst++;


150  src++;


151  len = idwp;


152  swp = (swp + idwp) % w;


153  iswp = w  swp;


154  }


155 


156  X a, b;


157 


158  // copy whole words


159  if (swp == 0) {


160  size_t numWords = len / w;


161  // use memory copy


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


163  src += numWords;


164  dst += numWords;


165  len = len % w;


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


167  } else {


168  // use shifted copy


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


170  while (len >= w) {


171  *dst = (a << swp)  (b >> iswp);


172  dst++;


173  src++;


174  len = w;


175  a = b;


176  b = *src;


177  }


178  }


179 


180  // set last word


181  X lw = (a << swp)  (b >> iswp), lm = (((X) 1 << (w  len))  1);


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


183  }


184 


185  /**


186  * array > integral


187  */


188  template<typename X, typename Y> finline


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


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


191 


192  // word width


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


194 


195  // calculate indexes


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


197  src += srcIdx / w;


198 


199  // mask off bits


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


201 


202  // copy whole words


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


204  Y value = 0;


205  src++;


206  while (len >= w) {


207  X x = (a << swp)  (b >> iswp);


208  value <<= w;


209  value = x;


210  src++;


211  len = w;


212  a = b; b = *src;


213  }


214 


215  // copy leftover


216  if ( len> 0 ) {


217  value <<= len;


218  value = (((a << swp)  (b >> iswp)) >> (w  len)) & ((1 << len)1);


219  }


220 


221  // set value


222  dst = (value << dstIdx);


223  }


224 


225  /**


226  * TODO: Doc


227  */


228  // word > array


229  template<typename X> finline


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


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


232 


233  // check inversion


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


235 


236  // word width


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


238 


239  // calculate indexes


240  size_t dwp = dstIdx % w;


241  dst += dstIdx / w;


242 


243  // copy directly


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


245  *dst = src;


246  } else


247 


248  // copy nonoverlapping word


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


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


251 


252  // copy overlapping word


253  } else {


254  size_t idwp = w  dwp;


255  src >>= srcIdx;


256  X mask1 = ~((1 << idwp)  1);


257  dst[0] = (dst[0] & mask1)  ((src >> (len  idwp)) & ~mask1);


258  X mask2 = (1 << (w  len + idwp))  1;


259  dst[1] = (dst[1] & mask2)  ((src << (w  len + idwp)) & ~mask2);


260  }


261  }


262 


263  /**


264  * TODO: Doc


265  */


266  // integral > array


267  template<typename Y, typename X> finline


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


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


270 


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


272  // check inversion


273  if (srcInvert)


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


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


276  } else {


277  // check inversion


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


279  src >>= srcIdx;


280 


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


282  while (len >= dw) {


283  X word = (X)(src >> (lendw));


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


285  dstIdx += dw;


286  len = dw;


287  }


288  X word = (X)src;


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


290  }


291  }


292 


293  /**


294  * TODO: Doc


295  */


296  template<typename T, typename X> finline


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


298  T x = 0;


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


300  return x;


301  }


302 


303  /**


304  * TODO: Doc


305  */


306  template<typename T, typename X> finline


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


308  T x = 0;


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


310  return x;


311  }


312 


313  /**


314  * TODO: Doc


315  */


316  template<typename X> finline


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


318  uint8_t x = 0;


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


320  return x != 0;


321  }


322 


323  /**


324  * TODO: Doc


325  */


326  template<typename X> finline


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


328  uint8_t x = 0;


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


330  return x != 0;


331  }


332 


333  /**


334  * TODO: Doc


335  */


336  template<typename T, typename X> finline


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


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


339  }


340 


341  /**


342  * TODO: Doc


343  */


344  template<typename X> finline


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


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


347  }


348 


349  /**


350  * TODO: Doc


351  */


352  template<typename X> finline


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


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


355  }


356 


357  /**


358  * TODO: Doc


359  */


360  template<typename X> finline


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


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


363  X dst = 0;


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


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


366  return dst;


367  }


368 


369  /**


370  * TODO: Doc


371  */


372  template<typename X> finline


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


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


375  bool b0 = bitget(src, i);


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


377  bitset(b1, src, i);


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


379  }


380  }


381 


382  /**


383  * TODO: Doc


384  */


385  template<typename X> finline


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


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


388  X ret = 0;


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


390  ret <<= 8;


391  ret = src & 0xFF;


392  src >>= 8;


393  }


394  return ret;


395  }


396 


397  /**


398  * TODO: Doc


399  */


400  template<typename X> finline


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


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


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


404 


405  std::string str;


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


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


408  return str;


409  }


410 


411  /**


412  * TODO: Doc


413  */


414  template<typename X> finline


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


416  false, if_uint(X)) {


417  std::string str;


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


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


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


421  }


422  return str;


423  }


424 


425  #endif /* DATAUTILITIES_HPP_ */

