MTToolBox  0.2.10
util.hpp
[詳解]
1 #ifndef MTTOOLBOX_UTIL_HPP
2 #define MTTOOLBOX_UTIL_HPP
3 
24 //#include <stdio.h>
25 #include <iostream>
26 #include <iomanip>
27 #include <sstream>
28 #include <inttypes.h>
29 #include <stdint.h>
30 #include <stdexcept>
31 #include <NTL/GF2X.h>
32 
33 #if defined(USE_SHA)
34 #include <openssl/sha.h>
35 #endif
36 
37 namespace MTToolBox {
38  inline static int count_bit(uint16_t x);
39  inline static int count_bit(uint32_t x);
40  inline static int count_bit(uint64_t x);
41  inline static uint32_t reverse_bit(uint32_t x);
42  inline static uint64_t reverse_bit(uint64_t x);
43 
63  template<typename T>
64  int bit_size() {
65  return static_cast<int>(sizeof(T) * 8);
66  }
67 
79  inline static void UNUSED_VARIABLE(void * x) {
80  (void)x;
81  }
82 
98  template<typename T>
99  T floor2p(T n) {
100  if (n == 1) {
101  return 1;
102  } else {
103  return 2 * floor2p<T>(n / 2);
104  }
105  }
106 
127  inline static void print_binary(std::ostream& os,
128  NTL::GF2X& poly,
129  bool breakline = true) {
130  using namespace NTL;
131  if (deg(poly) < 0) {
132  os << "0deg=-1" << std::endl;
133  return;
134  }
135  for(int i = 0; i <= deg(poly); i++) {
136  if(rep(coeff(poly, i)) == 1) {
137  os << '1';
138  } else {
139  os << '0';
140  }
141  if (breakline && ((i % 32) == 31)) {
142  os << std::endl;
143  }
144  }
145  os << "deg=" << deg(poly) << std::endl;
146  }
147 
169  template<typename T>
170  int get_range(T input, int start, int end) {
171  if (end < start) {
172  //printf("get_range:%d, %d\n", start, end);
173  std::cout << "get_range:" << start << ", " << end << std::endl;
174  exit(0);
175  }
176  return input % (end - start + 1) + start;
177  }
178 
196  template<typename T>
197  void fill_table(T dist_tbl[], T src_tbl[], int size) {
198  for(int i = 1; i < size; i++) {
199  for(int j = 1, k = 0; j <= i; j <<= 1, k++) {
200  if (i & j) {
201  dist_tbl[i] ^= src_tbl[k];
202  }
203  }
204  }
205  }
206 
207 #if defined(USE_SHA)
208 
232  inline static void poly_sha1(std::string& str, const NTL::GF2X& poly) {
233  using namespace NTL;
234  using namespace std;
235  SHA_CTX ctx;
236  SHA1_Init(&ctx);
237  if (deg(poly) < 0) {
238  SHA1_Update(&ctx, "-1", 2);
239  }
240  for(int i = 0; i <= deg(poly); i++) {
241  if(rep(coeff(poly, i)) == 1) {
242  SHA1_Update(&ctx, "1", 1);
243  } else {
244  SHA1_Update(&ctx, "0", 1);
245  }
246  }
247  unsigned char md[SHA_DIGEST_LENGTH];
248  SHA1_Final(md, &ctx);
249  stringstream ss;
250  for (int i = 0; i < SHA_DIGEST_LENGTH; i++) {
251  ss << setfill('0') << setw(2) << hex
252  << static_cast<int>(md[i]);
253  }
254  ss >> str;
255  }
256 #endif
257 
279  static inline int calc_1pos(uint16_t x)
280  {
281  if (x == 0) {
282  return -1;
283  }
284  int16_t y = (int16_t)x;
285  y = count_bit((uint16_t)((y & -y) - 1));
286  return 15 - y;
287  }
288 
313  static inline int calc_1pos(uint32_t x)
314  {
315  if (x == 0) {
316  return -1;
317  }
318  int32_t y = (int32_t)x;
319  y = count_bit((uint32_t)(y & -y) - 1);
320  return 31 - y;
321  }
322 
347  static inline int calc_1pos(uint64_t x)
348  {
349  if (x == 0) {
350  return -1;
351  }
352  int64_t y = (int64_t)x;
353  y = count_bit((uint64_t)(y & -y) - 1);
354  return 63 - y;
355  }
356 
377  inline static int count_bit(uint16_t x) {
378  x -= (x >> 1) & UINT16_C(0x5555);
379  x = ((x >> 2) & UINT16_C(0x3333)) + (x & UINT16_C(0x3333));
380  x = ((x >> 4) + x) & UINT16_C(0x0f0f);
381  x += (x >> 8);
382  return (int)(x & 0x1f);
383  }
384 
398  inline static int count_bit(uint32_t x) {
399  x -= (x >> 1) & UINT32_C(0x55555555);
400  x = ((x >> 2) & UINT32_C(0x33333333)) + (x & UINT32_C(0x33333333));
401  x = ((x >> 4) + x) & UINT32_C(0x0f0f0f0f);
402  x += (x >> 8);
403  x += (x >> 16);
404  return (int)(x & 0x3f);
405  }
406 
420  inline static int count_bit(uint64_t x) {
421  x -= (x >> 1) & UINT64_C(0x5555555555555555);
422  x = ((x >> 2) & UINT64_C(0x3333333333333333))
423  + (x & UINT64_C(0x3333333333333333));
424  x = ((x >> 4) + x) & UINT64_C(0x0f0f0f0f0f0f0f0f);
425  x += (x >> 8);
426  x += (x >> 16);
427  x += (x >> 32);
428  return (int)(x & 0x7f);
429  }
430 
453  inline static uint32_t reverse_bit(uint32_t x)
454  {
455  uint32_t y = 0x55555555;
456  x = (((x >> 1) & y) | ((x & y) << 1));
457  y = 0x33333333;
458  x = (((x >> 2) & y) | ((x & y) << 2));
459  y = 0x0f0f0f0f;
460  x = (((x >> 4) & y) | ((x & y) << 4));
461  y = 0x00ff00ff;
462  x = (((x >> 8) & y) | ((x & y) << 8));
463  return((x >> 16) | (x << 16));
464  }
465 
479  inline static uint64_t reverse_bit(uint64_t x)
480  {
481  uint64_t y = UINT64_C(0x5555555555555555);
482  x = (((x >> 1) & y) | ((x & y) << 1));
483  y = UINT64_C(0x3333333333333333);
484  x = (((x >> 2) & y) | ((x & y) << 2));
485  y = UINT64_C(0x0f0f0f0f0f0f0f0f);
486  x = (((x >> 4) & y) | ((x & y) << 4));
487  y = UINT64_C(0x00ff00ff00ff00ff);
488  x = (((x >> 8) & y) | ((x & y) << 8));
489  y = UINT64_C(0x0000ffff0000ffff);
490  x = (((x >> 16) & y) | ((x & y) << 16));
491  return((x >> 32) | (x << 32));
492  }
493 
509  inline static void LCM(NTL::GF2X& lcm, const NTL::GF2X& x,
510  const NTL::GF2X& y) {
511  using namespace NTL;
512  GF2X gcd;
513  GCD(gcd, x, y);
514  mul(lcm, x, y);
515  lcm /= gcd;
516  }
517 
535  template<typename U>
536  inline static void toGF2Vec(NTL::vec_GF2& result, U value) {
537  U mask = 1;
538  int bitSize = bit_size<U>();
539  result.SetLength(bitSize);
540  mask = mask << (bitSize - 1);
541  for (int i = 0; i < bitSize; i++) {
542  if (value & mask) {
543  result.put(i, 1);
544  } else {
545  result.put(i, 0);
546  }
547  mask = mask >> 1;
548  }
549  }
550 
551 
566  template<typename U>
567  inline U getOne() {
568  return static_cast<U>(1);
569  }
570 
585  template<typename U>
586  inline void setZero(U& x) {
587  x = 0;
588  }
589 
608  template<typename U>
609  inline unsigned int getBitOfPos(U bits, int pos) {
610  return (bits >> pos) & 1;
611  }
612 
631  template<typename U>
632  inline void setBitOfPos(U *bits, int pos, unsigned int b) {
633  b = b & 1;
634  U mask = ~(static_cast<U>(1) << pos);
635  *bits &= mask;
636  *bits |= static_cast<U>(b) << pos;
637  }
638 
654  template<typename U>
655  inline static U fromGF2Vec(NTL::vec_GF2& value) {
656  U result;
657  setZero(result);
658  U mask;
659  setZero(mask);
660  int bitSize = bit_size<U>();
661  int pos = bitSize - 1;
662  setBitOfPos(&mask, pos, 1);
663  for (int i = 0; i < bitSize; i++) {
664  if (!IsZero(value[i])) {
665  result |= mask;
666  }
667  pos--;
668  setZero(mask);
669  setBitOfPos(&mask, pos, 1);
670  }
671  return result;
672  }
673 
690  template<typename U>
691  inline bool isZero(U x) {
692  return x == 0;
693  }
694 
713  template<typename U, typename V>
714  inline U convert(V x) {
715  return static_cast<U>(x);
716  }
717 }
718 #endif //MTTOOLBOX_UTIL_HPP
T floor2p(T n)
n を越えない最大の2のべき乗を返す。
Definition: util.hpp:99
int bit_size()
T のビットサイズを返す。
Definition: util.hpp:64
static void UNUSED_VARIABLE(void *x)
使用しない変数のワーニングを止める
Definition: util.hpp:79
static int count_bit(uint16_t x)
1 の個数を数える
Definition: util.hpp:377
U convert(V x)
V 型をU型に変換する SIMD型は、そのSIMD型のファイルでこのテンプレートを特殊化する。 ...
Definition: util.hpp:714
static U fromGF2Vec(NTL::vec_GF2 &value)
GF(2)ベクトルを符号なし整数に変換する。 上位ビットがベクトルの初めの要素になる。(デバッグの時見やす...
Definition: util.hpp:655
U getOne()
その型の1を返す SIMD型は、そのSIMD型のファイルでこのテンプレートを特殊化する。
Definition: util.hpp:567
void setBitOfPos(U *bits, int pos, unsigned int b)
変数の指定位置のビットを1または0にセットする SIMD型は、そのSIMD型のファイルでこのテンプレートを特殊化...
Definition: util.hpp:632
static void print_binary(std::ostream &os, NTL::GF2X &poly, bool breakline=true)
出力ストリーム os に多項式 poly を01の文字列で出力する。
Definition: util.hpp:127
unsigned int getBitOfPos(U bits, int pos)
特定位置のビットを求める SIMD型は、そのSIMD型のファイルでこのテンプレートを特殊化する。 ...
Definition: util.hpp:609
static void toGF2Vec(NTL::vec_GF2 &result, U value)
符号なし整数をGF(2)ベクトルに変換する。 上位ビットがベクトルの初めの要素になる。(デバッグの時見やす...
Definition: util.hpp:536
static void LCM(NTL::GF2X &lcm, const NTL::GF2X &x, const NTL::GF2X &y)
多項式の最小公倍数を求める。
Definition: util.hpp:509
void setZero(U &x)
ゼロをセットする SIMD型は、そのSIMD型のファイルでこのテンプレートを特殊化する。
Definition: util.hpp:586
static int calc_1pos(uint16_t x)
入力をビット列とみなして最上位の1の位置を0とした最も右側の(下位の)1の位置を返す。 ...
Definition: util.hpp:279
void fill_table(T dist_tbl[], T src_tbl[], int size)
GF(2)ベクトルのパラメータテーブルから、より高速で冗長なルックアップテーブルを作成する。 ...
Definition: util.hpp:197
static uint32_t reverse_bit(uint32_t x)
ビットを反転する
Definition: util.hpp:453
bool isZero(U x)
ゼロかどうか、判定する。 SIMD型は、そのSIMD型のファイルでこのテンプレートを特殊化する。 ...
Definition: util.hpp:691
int get_range(T input, int start, int end)
input を start と end の間の数に変換する。
Definition: util.hpp:170
MTToolBox の名前空間