1 /////////////////////////////////////////////////////////////////////// 2 // File: qrsequence.h 3 // Description: Quasi-random sequence generator class. 4 // Author: Ranjith Unnikrishnan 5 // Created: Wed May 20 2009 6 // 7 // Class to generate a (deterministic) quasi-random Van der Corput sequence that 8 // covers the interval [0,N) without repetition. 9 // 10 // The sequence is generated by reversing the base-2 representation of the 11 // sequence of natural numbers {0, 1,... M-1}, where M is 2^{num_bits_} and 12 // num_bits is the minimum number of bits required to represent N. If a reversed 13 // numbers is >= N it is rejected and the next natural number is considered 14 // until a valid output number is found. 15 // 16 // (C) Copyright 2009, Google Inc. 17 // Licensed under the Apache License, Version 2.0 (the "License"); you may not 18 // use this file except in compliance with the License. You may obtain a copy 19 // of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required 20 // by applicable law or agreed to in writing, software distributed under the 21 // License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS 22 // OF ANY KIND, either express or implied. See the License for the specific 23 // language governing permissions and limitations under the License. 24 // 25 /////////////////////////////////////////////////////////////////////// 26 27 #ifndef TESSERACT_CCUTIL_QRSEQUENCE_H_ 28 #define TESSERACT_CCUTIL_QRSEQUENCE_H_ 29 30 #include <math.h> 31 32 class QRSequenceGenerator { 33 public: 34 // Object is initalized with the size of the output range. QRSequenceGenerator(int N)35 explicit QRSequenceGenerator(int N) : N_(N), next_num_(0) { 36 num_bits_ = ceil(log(static_cast<double>(N)) / log(2.0)); 37 } 38 39 // Main worker method that retrieves the next number in the sequence. 40 // Returns kInvalidVal if called more than N times after object initialization GetVal()41 int GetVal() { 42 const int kInvalidVal = -1; 43 const int kMaxNaturalNumberValue = 1 << num_bits_; 44 if (next_num_ >= kMaxNaturalNumberValue) 45 return kInvalidVal; 46 int n = next_num_; 47 48 while (next_num_ < kMaxNaturalNumberValue) { 49 n = GetBinaryReversedInteger(next_num_++); 50 if (n < N_) break; 51 } 52 return (next_num_ > kMaxNaturalNumberValue) ? kInvalidVal : n; 53 } 54 55 protected: 56 // Outputs the integer formed by reversing the bits of the input integer. Only 57 // the lowest num_bits_ bits of the input integer are reversed. GetBinaryReversedInteger(int in_val)58 int GetBinaryReversedInteger(int in_val) const { 59 int bit_pos = num_bits_; 60 int out_val = 0; 61 while(bit_pos--) { 62 // Set the value of the last bit. 63 out_val |= (in_val & 0x1); 64 if (bit_pos > 0) { 65 // Left-shift output value to prepare for storing the next bit. 66 out_val <<= 1; 67 } 68 // Right-shift input value to prepare for retrieving the next bit. 69 in_val >>= 1; 70 } 71 return out_val; 72 } 73 int N_; 74 // Next number to be considered for reversal and output. 75 int next_num_; 76 // number of bits required to represent the numbers of the sequence 77 int num_bits_; 78 }; 79 80 #endif // TESSERACT_CCUTIL_QRSEQUENCE_H_ 81