Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/tesseract/src/ccutil/qrsequence.h @ 2:b50eed0cc0ef upstream

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