MTToolBox  0.2.10
AlgorithmCalculateParity.hpp
[詳解]
1 #ifndef MTTOOLBOX_ALGORITHM_CALCULATE_PARITY_HPP
2 #define MTTOOLBOX_ALGORITHM_CALCULATE_PARITY_HPP
3 
58 #include <stdint.h>
59 #include <stdio.h>
60 #include <limits.h>
61 #include <string.h>
62 #include <stdlib.h>
63 #include <errno.h>
64 #include <iostream>
65 #include <inttypes.h>
66 #include <NTL/GF2X.h>
67 #include <NTL/vec_GF2.h>
68 #include <NTL/mat_GF2.h>
70 #include <MTToolBox/util.hpp>
71 
72 namespace MTToolBox {
73  using namespace std;
74 
90  template<typename U, typename G>
92 
93  public:
110  U searchParity (G& g, const NTL::GF2X& f) {
111  int mexp = g.getMexp();
112 #if defined(DEBUG)
113  cout << "searchParity start" << endl;
114  cout << "degree of f = " << deg(f) << endl;
115 #endif
116  int maxdegree = g.bitSize();
117  word_width = bit_size<U>();
118  int base_num = maxdegree - mexp;
119  internal_state bases[word_width];
120  internal_state work_base;
121  int count;
122  int bit_pos = 0;
123 
124  for (int i = 0; i < word_width; i++) {
125  bases[i].rg = new G(g);
126  bases[i].rg->setZero();
127  bases[i].zero = true;
128  setZero(bases[i].next);
129  }
130  work_base.rg = new G(g);
131  work_base.rg->setZero();
132  work_base.zero = true;
133  setZero(work_base.next);
134 #if defined(DEBUG)
135  cout << "searchParity before while loop" << endl;
136  cout << "word_width = " << word_width << endl;
137  cout << "bit_pos = " << bit_pos << endl;
138  cout << "maxdegree = " << maxdegree << endl;
139  cout << "base_num = " << base_num << endl;
140 #endif
141  while(bit_pos < maxdegree) {
142  calc_basis(work_base, f, &bit_pos);
143  addBase(bases, word_width, work_base);
144  count = 0;
145  for (int i = 0; i < word_width; i++) {
146  if (!isZero(bases[i].next)) {
147  count++;
148  }
149  }
150 #if defined(DEBUG)
151  cout << "in while loop count = " << count << endl;
152 #endif
153  if (count >= base_num) {
154  break;
155  }
156  }
157 #if defined(DEBUG)
158  cout << "searchParity after while loop" << endl;
159 #endif
160  for (int i = 0; i < word_width; i++) {
161  delete bases[i].rg;
162  }
163 #if defined(DEBUG)
164  cout << "----" << endl;
165  for (int i = 0; i < word_width; i++) {
166  if (isZero(bases[i].next)) {
167  continue;
168  }
169  int w = word_width / 4;
170  cout << setw(2) << dec << i << " ";
171  cout << hex << setfill('0') << setw(w) << bases[i].next << endl;
172  cout << dec;
173  }
174  cout << "----" << endl;
175 #endif
176  U parity = search_parity_check_vector(bases, base_num);
177  g.setParityValue(parity);
178  return parity;
179  }
180 
181  private:
182  /* internal state */
183  struct internal_state {
184  bool zero;
185  U next;
186  G * rg;
187  };
188 
189  int word_width;
190 
202  void calc_basis(internal_state& st, const NTL::GF2X& f, int *bit_pos) {
203 #if defined(DEBUG)
204  cout << "calc_basis start bit_pos = " << dec << *bit_pos << endl;
205 #endif
206  int maxdegree = st.rg->bitSize();
207  for (;*bit_pos < maxdegree;) {
208 #if defined(DEBUG)
209  cout << "in calc_basis bit_pos = " << dec << *bit_pos << endl;
210 #endif
211  // 全状態空間の中で1ビットだけ1を立てる
212  st.rg->setOneBit(*bit_pos);
213 #if defined(DEBUG)
214  if (st.rg->isZero()) {
215  cout << "ERROR rg is ZERO" << endl;
216  }
217 #endif
218  (*bit_pos)++;
219  // fによる写像でfのカーネルの像を0にする
220  annihilate(st.rg, f);
221 #if defined(DEBUG)
222  if (st.rg->isZero()) {
223  cout << "ZERO after annihilate" << endl;
224  cout << "deg(f) = " << deg(f) << endl;
225  } else {
226  cout << "NON ZERO after annihilate" << endl;
227  }
228 #endif
229  set_state(st);
230  if (!st.zero) {
231  break;
232  }
233  }
234 #if defined(DEBUG)
235  cout << "calc_basis end bit_pos = " << dec << *bit_pos << endl;
236 #endif
237  }
238 
250  void set_state(internal_state& st) {
251 #if defined(DEBUG)
252  cout << "set_state start" << endl;
253 #endif
254  if (st.rg->isZero()) {
255  st.zero = true;
256  setZero(st.next);
257 #if defined(DEBUG)
258  cout << "set_state end zero" << endl;
259 #endif
260  return;
261  }
262  st.zero = false;
263  st.rg->generate();
264  st.next = st.rg->getParityValue();
265  while (isZero(st.next)) {
266  if (st.rg->isZero()) {
267  st.zero = true;
268  break;
269  }
270  st.rg->generate();
271  st.next = st.rg->getParityValue();
272  }
273 #if defined(DEBUG)
274  cout << "set_state end parity = "
275  << hex << setfill('0') << setw(8) << st.next << dec << endl;
276 #endif
277  }
278 
292  void add_state(internal_state& dist, const internal_state& src) {
293  dist.rg->add(*src.rg);
294  dist.next ^= src.next;
295  }
296 
308  void get_next_state(internal_state& st) {
309  if (st.zero) {
310  return;
311  }
312  set_state(st);
313  }
314 
333  void addBase(internal_state bases[], int size, internal_state& work) {
334 #if defined(DEBUG)
335  cout << "addBase start" << endl;
336 #endif
337  int count = bit_size<U>() * 10;
338  for (;count >= 0;) {
339  count--;
340 #if defined(DEBUG)
341  cout << "addBase work.next = " << hex << work.next << endl;
342 #endif
343  if (isZero(work.next)) {
344  get_next_state(work);
345  if (work.zero) {
346 #if defined(DEBUG)
347  cout << "addBase end work.zero" << endl;
348 #endif
349  return;
350  }
351  }
352  int pivot = calc_1pos(work.next);
353 #if defined(DEBUG)
354  cout << "addBase pivot = " << dec << pivot << endl;
355 #endif
356  if (pivot >= size) {
357  cout << "pivot > size error pivot = " << dec << pivot
358  << " size = " << dec << size << endl;
359  throw "pivot > size error";
360  }
361  if (isZero(bases[pivot].next)) {
362  add_state(bases[pivot], work);
363 #if defined(DEBUG)
364  cout << "addBase end next == 0" << endl;
365 #endif
366  return;
367  }
368  add_state(work, bases[pivot]);
369  }
370 #if defined(DEBUG)
371  cout << "addBase end" << endl;
372 #endif
373  }
374 
391  U search_parity_check_vector(internal_state base[], int size) {
392 #if defined(DEBUG)
393  cout << "search_parity_check_vector start" << endl;
394 #endif
395  NTL::mat_GF2 mx;
396  NTL::mat_GF2 my;
397 
398  mx.SetDims(word_width, size);
399  U mask;
400  int pos = bit_size<U>() - 1;
401  setZero(mask);
402  setBitOfPos(&mask, pos, 1);
403  for (int i = 0; i < word_width; i++) {
404  int cnt = 0;
405  for (int j = 0; j < word_width; j++) {
406  if (isZero(base[j].next)) {
407  continue;
408  }
409  if (!isZero(mask & base[j].next)) {
410  mx.put(i, cnt, 1);
411  } else {
412  mx.put(i, cnt, 0);
413  }
414  cnt++;
415  }
416  pos--;
417  setZero(mask);
418  setBitOfPos(&mask, pos, 1);
419  }
420  kernel(my, mx);
421  if (my.NumRows() == 0) {
422  cout << "parity vector can't find" << endl;
423  throw "parity vector can't find";
424  }
425 #if defined(DEBUG)
426  cout << "dim mx = "<< mx.NumRows() << endl;
427  cout << "-----" << endl;
428  for (int i = 0; i < mx.NumRows(); i++) {
429  for (int j = 0; j < mx.NumCols(); j++) {
430  cout << mx.get(i, j);
431  }
432  cout << endl;
433  }
434  cout << "dim kernel = "<< my.NumRows() << endl;
435  cout << "-----" << endl;
436  for (int i = 0; i < my.NumRows(); i++) {
437  for (int j = 0; j < my.NumCols(); j++) {
438  cout << my.get(i, j);
439  }
440  cout << endl;
441  }
442  cout << "search_parity_check_vector end" << endl;
443 #endif
444  return fromGF2Vec<U>(my[0]);
445  }
446 
447  }; // End of class AlgorithmSearchParity
448 } // End of name space MTToolBox
449 #endif // MTTOOLBOX_ALGORITHM_CALCULATE_PARITY_HPP
可約ジェネレータのパリティチェックベクトルを求める。
Definition: AlgorithmCalculateParity.hpp:91
void setBitOfPos(U *bits, int pos, unsigned int b)
変数の指定位置のビットを1または0にセットする SIMD型は、そのSIMD型のファイルでこのテンプレートを特殊化...
Definition: util.hpp:632
ユーティリティ関数群
void annihilate(EquidistributionCalculatable< U, V > *rg, const NTL::GF2X &poly)
可約疑似乱数生成器の状態空間を多項式で殲滅する。
Definition: ReducibleGenerator.hpp:148
U searchParity(G &g, const NTL::GF2X &f)
qによってannihilateされる空間の基底を求め、パリティチェック用の定数を求める
Definition: AlgorithmCalculateParity.hpp:110
void setZero(U &x)
ゼロをセットする SIMD型は、そのSIMD型のファイルでこのテンプレートを特殊化する。
Definition: util.hpp:586
static int calc_1pos(uint16_t x)
入力をビット列とみなして最上位の1の位置を0とした最も右側の(下位の)1の位置を返す。 ...
Definition: util.hpp:279
bool isZero(U x)
ゼロかどうか、判定する。 SIMD型は、そのSIMD型のファイルでこのテンプレートを特殊化する。 ...
Definition: util.hpp:691
MTToolBox の名前空間