You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@impala.apache.org by ta...@apache.org on 2017/12/14 17:48:38 UTC
[1/8] impala git commit: IMPALA-5848: Account for TCMalloc overhead
in MemTracker
Repository: impala
Updated Branches:
refs/heads/master 0936e3296 -> 3cbbaf3b3
IMPALA-5848: Account for TCMalloc overhead in MemTracker
This patch adds a new MemTracker under the Process MemTracker called
"TCMalloc Overhead" which accounts for different cache freelists
maintained by TCMalloc. This added accounting also helps bring down
the amount of untracked memory.
An example dump of the Process MemTracker now looks like:
Process: Limit=8.34 GB Total=119.10 MB Peak=119.10 MB
Buffer Pool: Free Buffers: Total=0
Buffer Pool: Clean Pages: Total=0
Buffer Pool: Unused Reservation: Total=0
TCMalloc Overhead: Total=11.42 MB
Untracked Memory: Total=107.69 MB
Testing:
Tested manually by checking the memz webpage.
Change-Id: I602e9d5e8e8d7470dcfe4addde3265057c16263a
Reviewed-on: http://gerrit.cloudera.org:8080/8782
Reviewed-by: Bikramjeet Vig <bi...@cloudera.com>
Tested-by: Impala Public Jenkins
Project: http://git-wip-us.apache.org/repos/asf/impala/repo
Commit: http://git-wip-us.apache.org/repos/asf/impala/commit/9a6e5fa9
Tree: http://git-wip-us.apache.org/repos/asf/impala/tree/9a6e5fa9
Diff: http://git-wip-us.apache.org/repos/asf/impala/diff/9a6e5fa9
Branch: refs/heads/master
Commit: 9a6e5fa99650c4d916aa577742a7758af53f14ee
Parents: 0936e32
Author: Bikramjeet Vig <bi...@cloudera.com>
Authored: Wed Dec 6 14:55:40 2017 -0800
Committer: Impala Public Jenkins <im...@gerrit.cloudera.org>
Committed: Wed Dec 13 02:05:21 2017 +0000
----------------------------------------------------------------------
be/src/runtime/exec-env.cc | 15 +++++++++++++++
1 file changed, 15 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/impala/blob/9a6e5fa9/be/src/runtime/exec-env.cc
----------------------------------------------------------------------
diff --git a/be/src/runtime/exec-env.cc b/be/src/runtime/exec-env.cc
index 6fb572c..2df696e 100644
--- a/be/src/runtime/exec-env.cc
+++ b/be/src/runtime/exec-env.cc
@@ -336,6 +336,21 @@ Status ExecEnv::Init() {
if (!aggressive_decommit_enabled) {
return Status("TCMalloc aggressive decommit is required but is disabled.");
}
+ // A MemTracker for TCMalloc overhead which is the difference between the physical bytes
+ // reserved (TcmallocMetric::PHYSICAL_BYTES_RESERVED) and the bytes in use
+ // (TcmallocMetrics::BYTES_IN_USE). This overhead accounts for all the cached freelists
+ // used by TCMalloc.
+ IntGauge* negated_bytes_in_use = obj_pool_->Add(new NegatedGauge<int64_t>(
+ MakeTMetricDef("negated_tcmalloc_bytes_in_use", TMetricKind::GAUGE, TUnit::BYTES),
+ TcmallocMetric::BYTES_IN_USE));
+ vector<IntGauge*> overhead_metrics;
+ overhead_metrics.push_back(negated_bytes_in_use);
+ overhead_metrics.push_back(TcmallocMetric::PHYSICAL_BYTES_RESERVED);
+ SumGauge<int64_t>* tcmalloc_overhead = obj_pool_->Add(new SumGauge<int64_t>(
+ MakeTMetricDef("tcmalloc_overhead", TMetricKind::GAUGE, TUnit::BYTES),
+ overhead_metrics));
+ obj_pool_->Add(
+ new MemTracker(tcmalloc_overhead, -1, "TCMalloc Overhead", mem_tracker_.get()));
#endif
mem_tracker_->RegisterMetrics(metrics_.get(), "mem-tracker.process");
[2/8] impala git commit: IMPALA-5754: Improve randomness of
rand()/random()
Posted by ta...@apache.org.
http://git-wip-us.apache.org/repos/asf/impala/blob/4feb4f3a/bin/run_clang_tidy.sh
----------------------------------------------------------------------
diff --git a/bin/run_clang_tidy.sh b/bin/run_clang_tidy.sh
index e879b35..36d46ce 100755
--- a/bin/run_clang_tidy.sh
+++ b/bin/run_clang_tidy.sh
@@ -38,7 +38,8 @@ fi
DIRS=$(ls -d "${IMPALA_HOME}/be/src/"*/ | grep -v gutil | grep -v kudu |\
grep -v thirdparty | tr '\n' ' ')
# Include/exclude select thirdparty dirs.
-DIRS=$DIRS$(ls -d "${IMPALA_HOME}/be/src/thirdparty/"*/ | grep -v mpfit | tr '\n' ' ')
+DIRS=$DIRS$(ls -d "${IMPALA_HOME}/be/src/thirdparty/"*/ | grep -v mpfit |\
+ grep -v pcg-cpp | tr '\n' ' ')
PIPE_DIRS=$(echo "${DIRS}" | tr ' ' '|')
# Reduce the concurrency to one less than the number of cores in the system. Note than
http://git-wip-us.apache.org/repos/asf/impala/blob/4feb4f3a/testdata/workloads/functional-query/queries/QueryTest/alloc-fail-init.test
----------------------------------------------------------------------
diff --git a/testdata/workloads/functional-query/queries/QueryTest/alloc-fail-init.test b/testdata/workloads/functional-query/queries/QueryTest/alloc-fail-init.test
index fe4fa87..5130cdb 100644
--- a/testdata/workloads/functional-query/queries/QueryTest/alloc-fail-init.test
+++ b/testdata/workloads/functional-query/queries/QueryTest/alloc-fail-init.test
@@ -43,7 +43,7 @@ FunctionContext::Allocate() failed to allocate 1 bytes.
---- QUERY
select rand() from functional.alltypes;
---- CATCH
-FunctionContext::Allocate() failed to allocate 4 bytes.
+FunctionContext::Allocate() failed to allocate 16 bytes.
====
---- QUERY
select case when min(int_col) = 0 then 0 end from functional.alltypes
http://git-wip-us.apache.org/repos/asf/impala/blob/4feb4f3a/testdata/workloads/functional-query/queries/QueryTest/random.test
----------------------------------------------------------------------
diff --git a/testdata/workloads/functional-query/queries/QueryTest/random.test b/testdata/workloads/functional-query/queries/QueryTest/random.test
new file mode 100644
index 0000000..19d2611
--- /dev/null
+++ b/testdata/workloads/functional-query/queries/QueryTest/random.test
@@ -0,0 +1,24 @@
+# These computations take a while so we do not want to add too many test cases
+# They also require a non-trivial amount of data to get reasonable results.
+====
+---- QUERY
+select count(distinct rand()), count(*) from alltypes a;
+---- TYPES
+bigint, bigint
+---- RESULTS
+7300,7300
+====
+---- QUERY
+select count(distinct rand(100)), count(*) from alltypes a;
+---- TYPES
+bigint, bigint
+---- RESULTS
+7300,7300
+====
+---- QUERY
+select count(distinct rand()), count(*) from alltypes a, alltypes b;
+---- TYPES
+bigint, bigint
+---- RESULTS
+53290000,53290000
+====
http://git-wip-us.apache.org/repos/asf/impala/blob/4feb4f3a/tests/query_test/test_queries.py
----------------------------------------------------------------------
diff --git a/tests/query_test/test_queries.py b/tests/query_test/test_queries.py
index 3caeebe..997b59a 100644
--- a/tests/query_test/test_queries.py
+++ b/tests/query_test/test_queries.py
@@ -172,6 +172,12 @@ class TestQueriesTextTables(ImpalaTestSuite):
vector.get_value('exec_option')['num_nodes'] = 1
self.run_test_case('QueryTest/distinct-estimate', vector)
+ def test_random(self, vector):
+ # These results will vary slightly depending on how the values get split up
+ # so only run with 1 node and on text.
+ vector.get_value('exec_option')['num_nodes'] = 1
+ self.run_test_case('QueryTest/random', vector)
+
def test_mixed_format(self, vector):
self.run_test_case('QueryTest/mixed-format', vector)
[4/8] impala git commit: IMPALA-5754: Improve randomness of
rand()/random()
Posted by ta...@apache.org.
IMPALA-5754: Improve randomness of rand()/random()
Currently implementation of rand/random built-in functions
use rand_r of C library. We recognized its randomness was poor.
pcg32 of third party library shows better randomness than rand_r.
Testing:
Revise unit test in expr-test
Add E2E test to random.test
Change-Id: Idafdd5fe7502ff242c76a91a815c565146108684
Reviewed-on: http://gerrit.cloudera.org:8080/8355
Reviewed-by: Jim Apple <jb...@apache.org>
Tested-by: Impala Public Jenkins
Project: http://git-wip-us.apache.org/repos/asf/impala/repo
Commit: http://git-wip-us.apache.org/repos/asf/impala/commit/4feb4f3a
Tree: http://git-wip-us.apache.org/repos/asf/impala/tree/4feb4f3a
Diff: http://git-wip-us.apache.org/repos/asf/impala/diff/4feb4f3a
Branch: refs/heads/master
Commit: 4feb4f3a549a79646b52f6aabb75c3f529d5cfe8
Parents: 9a6e5fa
Author: Jinchul <ji...@gmail.com>
Authored: Mon Oct 23 15:24:12 2017 +0900
Committer: Impala Public Jenkins <im...@gerrit.cloudera.org>
Committed: Wed Dec 13 10:04:40 2017 +0000
----------------------------------------------------------------------
LICENSE.txt | 1 +
be/src/exprs/expr-test.cc | 25 +-
be/src/exprs/math-functions-ir.cc | 36 +-
be/src/thirdparty/pcg-cpp-0.98/LICENSE.txt | 201 ++
be/src/thirdparty/pcg-cpp-0.98/README.md | 52 +
.../pcg-cpp-0.98/include/pcg_extras.hpp | 637 +++++++
.../pcg-cpp-0.98/include/pcg_random.hpp | 1751 ++++++++++++++++++
.../pcg-cpp-0.98/include/pcg_uint128.hpp | 750 ++++++++
bin/rat_exclude_files.txt | 2 +
bin/run_clang_tidy.sh | 3 +-
.../queries/QueryTest/alloc-fail-init.test | 2 +-
.../queries/QueryTest/random.test | 24 +
tests/query_test/test_queries.py | 6 +
13 files changed, 3458 insertions(+), 32 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/impala/blob/4feb4f3a/LICENSE.txt
----------------------------------------------------------------------
diff --git a/LICENSE.txt b/LICENSE.txt
index aa211ad..d4c4307 100644
--- a/LICENSE.txt
+++ b/LICENSE.txt
@@ -669,6 +669,7 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
--------------------------------------------------------------------------------
be/src/thirdparty/mustache: Apache 2.0 license
+be/src/thirdparty/pcg-cpp-0.98: Apache 2.0 license
be/src/expr/hll-bias.h: Apache 2.0 license
shell/ext-py/sasl-0.1.1: Apache 2.0 license
http://git-wip-us.apache.org/repos/asf/impala/blob/4feb4f3a/be/src/exprs/expr-test.cc
----------------------------------------------------------------------
diff --git a/be/src/exprs/expr-test.cc b/be/src/exprs/expr-test.cc
index 5670bcf..35599c0 100644
--- a/be/src/exprs/expr-test.cc
+++ b/be/src/exprs/expr-test.cc
@@ -1132,6 +1132,12 @@ int64_t ExprTest::ConvertValue<int64_t>(const string& value) {
}
template <>
+double ExprTest::ConvertValue<double>(const string& value) {
+ StringParser::ParseResult result;
+ return StringParser::StringToFloat<double>(value.data(), value.size(), &result);
+}
+
+template <>
TimestampValue ExprTest::ConvertValue<TimestampValue>(const string& value) {
return TimestampValue::Parse(value.data(), value.size());
}
@@ -4895,16 +4901,15 @@ TEST_F(ExprTest, MathFunctions) {
TestValue("dsqrt(81.0)", TYPE_DOUBLE, 9);
// Run twice to test deterministic behavior.
- uint32_t seed = 0;
- double expected = static_cast<double>(rand_r(&seed)) / static_cast<double>(RAND_MAX);
- TestValue("rand()", TYPE_DOUBLE, expected);
- TestValue("rand()", TYPE_DOUBLE, expected);
- TestValue("random()", TYPE_DOUBLE, expected); // Test alias
- seed = 1234;
- expected = static_cast<double>(rand_r(&seed)) / static_cast<double>(RAND_MAX);
- TestValue("rand(1234)", TYPE_DOUBLE, expected);
- TestValue("rand(1234)", TYPE_DOUBLE, expected);
- TestValue("random(1234)", TYPE_DOUBLE, expected); // Test alias
+ for (uint32_t seed : {0, 1234}) {
+ stringstream rand, random;
+ rand << "rand(" << seed << ")";
+ random << "random(" << seed << ")";
+ const double expected_result = ConvertValue<double>(GetValue(rand.str(),
+ TYPE_DOUBLE));
+ TestValue(rand.str(), TYPE_DOUBLE, expected_result);
+ TestValue(random.str(), TYPE_DOUBLE, expected_result); // Test alias
+ }
// Test bigint param.
TestValue("pmod(10, 3)", TYPE_BIGINT, 1);
http://git-wip-us.apache.org/repos/asf/impala/blob/4feb4f3a/be/src/exprs/math-functions-ir.cc
----------------------------------------------------------------------
diff --git a/be/src/exprs/math-functions-ir.cc b/be/src/exprs/math-functions-ir.cc
index cc86d5b..531bf24 100644
--- a/be/src/exprs/math-functions-ir.cc
+++ b/be/src/exprs/math-functions-ir.cc
@@ -18,6 +18,7 @@
#include "exprs/math-functions.h"
#include <iomanip>
+#include <random>
#include <sstream>
#include <math.h>
@@ -27,6 +28,7 @@
#include "util/string-parser.h"
#include "runtime/runtime-state.h"
#include "runtime/string-value.inline.h"
+#include "thirdparty/pcg-cpp-0.98/include/pcg_random.hpp"
#include "common/names.h"
@@ -148,9 +150,7 @@ DoubleVal MathFunctions::Pow(FunctionContext* ctx, const DoubleVal& base,
void MathFunctions::RandPrepare(
FunctionContext* ctx, FunctionContext::FunctionStateScope scope) {
if (scope == FunctionContext::THREAD_LOCAL) {
- uint32_t* seed = ctx->Allocate<uint32_t>();
- RETURN_IF_NULL(ctx, seed);
- ctx->SetFunctionState(scope, seed);
+ uint32_t seed = 0;
if (ctx->GetNumArgs() == 1) {
// This is a call to RandSeed, initialize the seed
// TODO: should we support non-constant seed?
@@ -160,26 +160,22 @@ void MathFunctions::RandPrepare(
}
DCHECK_EQ(ctx->GetArgType(0)->type, FunctionContext::TYPE_BIGINT);
BigIntVal* seed_arg = static_cast<BigIntVal*>(ctx->GetConstantArg(0));
- if (seed_arg->is_null) {
- *seed = 0;
- } else {
- *seed = seed_arg->val;
- }
- } else {
- // This is a call to Rand, initialize seed to 0
- // TODO: can we change this behavior? This is stupid.
- *seed = 0;
+ if (!seed_arg->is_null) seed = seed_arg->val;
}
+ pcg32* generator = ctx->Allocate<pcg32>();
+ RETURN_IF_NULL(ctx, generator);
+ ctx->SetFunctionState(scope, generator);
+ new (generator) pcg32(seed);
}
}
DoubleVal MathFunctions::Rand(FunctionContext* ctx) {
- uint32_t* seed =
- reinterpret_cast<uint32_t*>(ctx->GetFunctionState(FunctionContext::THREAD_LOCAL));
- DCHECK(seed != NULL);
- *seed = rand_r(seed);
- // Normalize to [0,1].
- return DoubleVal(static_cast<double>(*seed) / RAND_MAX);
+ pcg32* const generator =
+ reinterpret_cast<pcg32*>(ctx->GetFunctionState(FunctionContext::THREAD_LOCAL));
+ DCHECK(generator != nullptr);
+ static const double min = 0, max = 1;
+ std::uniform_real_distribution<double> distribution(min, max);
+ return DoubleVal(distribution(*generator));
}
DoubleVal MathFunctions::RandSeed(FunctionContext* ctx, const BigIntVal& seed) {
@@ -190,9 +186,9 @@ DoubleVal MathFunctions::RandSeed(FunctionContext* ctx, const BigIntVal& seed) {
void MathFunctions::RandClose(FunctionContext* ctx,
FunctionContext::FunctionStateScope scope) {
if (scope == FunctionContext::THREAD_LOCAL) {
- uint8_t* seed = reinterpret_cast<uint8_t*>(
+ uint8_t* generator = reinterpret_cast<uint8_t*>(
ctx->GetFunctionState(FunctionContext::THREAD_LOCAL));
- ctx->Free(seed);
+ ctx->Free(generator);
ctx->SetFunctionState(FunctionContext::THREAD_LOCAL, nullptr);
}
}
http://git-wip-us.apache.org/repos/asf/impala/blob/4feb4f3a/be/src/thirdparty/pcg-cpp-0.98/LICENSE.txt
----------------------------------------------------------------------
diff --git a/be/src/thirdparty/pcg-cpp-0.98/LICENSE.txt b/be/src/thirdparty/pcg-cpp-0.98/LICENSE.txt
new file mode 100644
index 0000000..8dada3e
--- /dev/null
+++ b/be/src/thirdparty/pcg-cpp-0.98/LICENSE.txt
@@ -0,0 +1,201 @@
+ Apache License
+ Version 2.0, January 2004
+ http://www.apache.org/licenses/
+
+ TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+ 1. Definitions.
+
+ "License" shall mean the terms and conditions for use, reproduction,
+ and distribution as defined by Sections 1 through 9 of this document.
+
+ "Licensor" shall mean the copyright owner or entity authorized by
+ the copyright owner that is granting the License.
+
+ "Legal Entity" shall mean the union of the acting entity and all
+ other entities that control, are controlled by, or are under common
+ control with that entity. For the purposes of this definition,
+ "control" means (i) the power, direct or indirect, to cause the
+ direction or management of such entity, whether by contract or
+ otherwise, or (ii) ownership of fifty percent (50%) or more of the
+ outstanding shares, or (iii) beneficial ownership of such entity.
+
+ "You" (or "Your") shall mean an individual or Legal Entity
+ exercising permissions granted by this License.
+
+ "Source" form shall mean the preferred form for making modifications,
+ including but not limited to software source code, documentation
+ source, and configuration files.
+
+ "Object" form shall mean any form resulting from mechanical
+ transformation or translation of a Source form, including but
+ not limited to compiled object code, generated documentation,
+ and conversions to other media types.
+
+ "Work" shall mean the work of authorship, whether in Source or
+ Object form, made available under the License, as indicated by a
+ copyright notice that is included in or attached to the work
+ (an example is provided in the Appendix below).
+
+ "Derivative Works" shall mean any work, whether in Source or Object
+ form, that is based on (or derived from) the Work and for which the
+ editorial revisions, annotations, elaborations, or other modifications
+ represent, as a whole, an original work of authorship. For the purposes
+ of this License, Derivative Works shall not include works that remain
+ separable from, or merely link (or bind by name) to the interfaces of,
+ the Work and Derivative Works thereof.
+
+ "Contribution" shall mean any work of authorship, including
+ the original version of the Work and any modifications or additions
+ to that Work or Derivative Works thereof, that is intentionally
+ submitted to Licensor for inclusion in the Work by the copyright owner
+ or by an individual or Legal Entity authorized to submit on behalf of
+ the copyright owner. For the purposes of this definition, "submitted"
+ means any form of electronic, verbal, or written communication sent
+ to the Licensor or its representatives, including but not limited to
+ communication on electronic mailing lists, source code control systems,
+ and issue tracking systems that are managed by, or on behalf of, the
+ Licensor for the purpose of discussing and improving the Work, but
+ excluding communication that is conspicuously marked or otherwise
+ designated in writing by the copyright owner as "Not a Contribution."
+
+ "Contributor" shall mean Licensor and any individual or Legal Entity
+ on behalf of whom a Contribution has been received by Licensor and
+ subsequently incorporated within the Work.
+
+ 2. Grant of Copyright License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ copyright license to reproduce, prepare Derivative Works of,
+ publicly display, publicly perform, sublicense, and distribute the
+ Work and such Derivative Works in Source or Object form.
+
+ 3. Grant of Patent License. Subject to the terms and conditions of
+ this License, each Contributor hereby grants to You a perpetual,
+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+ (except as stated in this section) patent license to make, have made,
+ use, offer to sell, sell, import, and otherwise transfer the Work,
+ where such license applies only to those patent claims licensable
+ by such Contributor that are necessarily infringed by their
+ Contribution(s) alone or by combination of their Contribution(s)
+ with the Work to which such Contribution(s) was submitted. If You
+ institute patent litigation against any entity (including a
+ cross-claim or counterclaim in a lawsuit) alleging that the Work
+ or a Contribution incorporated within the Work constitutes direct
+ or contributory patent infringement, then any patent licenses
+ granted to You under this License for that Work shall terminate
+ as of the date such litigation is filed.
+
+ 4. Redistribution. You may reproduce and distribute copies of the
+ Work or Derivative Works thereof in any medium, with or without
+ modifications, and in Source or Object form, provided that You
+ meet the following conditions:
+
+ (a) You must give any other recipients of the Work or
+ Derivative Works a copy of this License; and
+
+ (b) You must cause any modified files to carry prominent notices
+ stating that You changed the files; and
+
+ (c) You must retain, in the Source form of any Derivative Works
+ that You distribute, all copyright, patent, trademark, and
+ attribution notices from the Source form of the Work,
+ excluding those notices that do not pertain to any part of
+ the Derivative Works; and
+
+ (d) If the Work includes a "NOTICE" text file as part of its
+ distribution, then any Derivative Works that You distribute must
+ include a readable copy of the attribution notices contained
+ within such NOTICE file, excluding those notices that do not
+ pertain to any part of the Derivative Works, in at least one
+ of the following places: within a NOTICE text file distributed
+ as part of the Derivative Works; within the Source form or
+ documentation, if provided along with the Derivative Works; or,
+ within a display generated by the Derivative Works, if and
+ wherever such third-party notices normally appear. The contents
+ of the NOTICE file are for informational purposes only and
+ do not modify the License. You may add Your own attribution
+ notices within Derivative Works that You distribute, alongside
+ or as an addendum to the NOTICE text from the Work, provided
+ that such additional attribution notices cannot be construed
+ as modifying the License.
+
+ You may add Your own copyright statement to Your modifications and
+ may provide additional or different license terms and conditions
+ for use, reproduction, or distribution of Your modifications, or
+ for any such Derivative Works as a whole, provided Your use,
+ reproduction, and distribution of the Work otherwise complies with
+ the conditions stated in this License.
+
+ 5. Submission of Contributions. Unless You explicitly state otherwise,
+ any Contribution intentionally submitted for inclusion in the Work
+ by You to the Licensor shall be under the terms and conditions of
+ this License, without any additional terms or conditions.
+ Notwithstanding the above, nothing herein shall supersede or modify
+ the terms of any separate license agreement you may have executed
+ with Licensor regarding such Contributions.
+
+ 6. Trademarks. This License does not grant permission to use the trade
+ names, trademarks, service marks, or product names of the Licensor,
+ except as required for reasonable and customary use in describing the
+ origin of the Work and reproducing the content of the NOTICE file.
+
+ 7. Disclaimer of Warranty. Unless required by applicable law or
+ agreed to in writing, Licensor provides the Work (and each
+ Contributor provides its Contributions) on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+ implied, including, without limitation, any warranties or conditions
+ of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+ PARTICULAR PURPOSE. You are solely responsible for determining the
+ appropriateness of using or redistributing the Work and assume any
+ risks associated with Your exercise of permissions under this License.
+
+ 8. Limitation of Liability. In no event and under no legal theory,
+ whether in tort (including negligence), contract, or otherwise,
+ unless required by applicable law (such as deliberate and grossly
+ negligent acts) or agreed to in writing, shall any Contributor be
+ liable to You for damages, including any direct, indirect, special,
+ incidental, or consequential damages of any character arising as a
+ result of this License or out of the use or inability to use the
+ Work (including but not limited to damages for loss of goodwill,
+ work stoppage, computer failure or malfunction, or any and all
+ other commercial damages or losses), even if such Contributor
+ has been advised of the possibility of such damages.
+
+ 9. Accepting Warranty or Additional Liability. While redistributing
+ the Work or Derivative Works thereof, You may choose to offer,
+ and charge a fee for, acceptance of support, warranty, indemnity,
+ or other liability obligations and/or rights consistent with this
+ License. However, in accepting such obligations, You may act only
+ on Your own behalf and on Your sole responsibility, not on behalf
+ of any other Contributor, and only if You agree to indemnify,
+ defend, and hold each Contributor harmless for any liability
+ incurred by, or claims asserted against, such Contributor by reason
+ of your accepting any such warranty or additional liability.
+
+ END OF TERMS AND CONDITIONS
+
+ APPENDIX: How to apply the Apache License to your work.
+
+ To apply the Apache License to your work, attach the following
+ boilerplate notice, with the fields enclosed by brackets "{}"
+ replaced with your own identifying information. (Don't include
+ the brackets!) The text should be enclosed in the appropriate
+ comment syntax for the file format. We also recommend that a
+ file or class name and description of purpose be included on the
+ same "printed page" as the copyright notice for easier
+ identification within third-party archives.
+
+ Copyright {yyyy} {name of copyright owner}
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
http://git-wip-us.apache.org/repos/asf/impala/blob/4feb4f3a/be/src/thirdparty/pcg-cpp-0.98/README.md
----------------------------------------------------------------------
diff --git a/be/src/thirdparty/pcg-cpp-0.98/README.md b/be/src/thirdparty/pcg-cpp-0.98/README.md
new file mode 100644
index 0000000..f2858db
--- /dev/null
+++ b/be/src/thirdparty/pcg-cpp-0.98/README.md
@@ -0,0 +1,52 @@
+# PCG Random Number Generation, C++ Edition
+
+[PCG-Random website]: http://www.pcg-random.org
+
+This code provides an implementation of the PCG family of random number
+generators, which are fast, statistically excellent, and offer a number of
+useful features.
+
+Full details can be found at the [PCG-Random website]. This version
+of the code provides many family members -- if you just want one
+simple generator, you may prefer the minimal C version of the library.
+
+There are two kinds of generator, normal generators and extended generators.
+Extended generators provide *k* dimensional equidistribution and can perform
+party tricks, but generally speaking most people only need the normal
+generators.
+
+There are two ways to access the generators, using a convenience typedef
+or by using the underlying templates directly (similar to C++11's `std::mt19937` typedef vs its `std::mersenne_twister_engine` template). For most users, the convenience typedef is what you want, and probably you're fine with `pcg32` for 32-bit numbers. If you want 64-bit numbers, either use `pcg64` (or, if you're on a 32-bit system, making 64 bits from two calls to `pcg32_k2` may be faster).
+
+## Documentation and Examples
+
+Visit [PCG-Random website] for information on how to use this library, or look
+at the sample code in the `sample` directory -- hopefully it should be fairly
+self explanatory.
+
+## Building
+
+The code is written in C++11, as an include-only library (i.e., there is
+nothing you need to build). There are some provided demo programs and tests
+however. On a Unix-style system (e.g., Linux, Mac OS X) you should be able
+to just type type
+
+ make
+
+To build the demo programs.
+
+## Testing
+
+Run
+
+ make test
+
+## Directory Structure
+
+The directories are arranged as follows:
+
+* `include` -- contains `pcg_random.hpp` and supporting include files
+* `test-high` -- test code for the high-level API where the functions have
+ shorter, less scary-looking names.
+* `sample` -- sample code, some similar to the code in `test-high` but more
+ human readable, some other examples too
http://git-wip-us.apache.org/repos/asf/impala/blob/4feb4f3a/be/src/thirdparty/pcg-cpp-0.98/include/pcg_extras.hpp
----------------------------------------------------------------------
diff --git a/be/src/thirdparty/pcg-cpp-0.98/include/pcg_extras.hpp b/be/src/thirdparty/pcg-cpp-0.98/include/pcg_extras.hpp
new file mode 100644
index 0000000..ec3e569
--- /dev/null
+++ b/be/src/thirdparty/pcg-cpp-0.98/include/pcg_extras.hpp
@@ -0,0 +1,637 @@
+/*
+ * PCG Random Number Generation for C++
+ *
+ * Copyright 2014 Melissa O'Neill <on...@pcg-random.org>
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * For additional information about the PCG random number generation scheme,
+ * including its license and other licensing options, visit
+ *
+ * http://www.pcg-random.org
+ */
+
+/*
+ * This file provides support code that is useful for random-number generation
+ * but not specific to the PCG generation scheme, including:
+ * - 128-bit int support for platforms where it isn't available natively
+ * - bit twiddling operations
+ * - I/O of 128-bit and 8-bit integers
+ * - Handling the evilness of SeedSeq
+ * - Support for efficiently producing random numbers less than a given
+ * bound
+ */
+
+#ifndef PCG_EXTRAS_HPP_INCLUDED
+#define PCG_EXTRAS_HPP_INCLUDED 1
+
+#include <cinttypes>
+#include <cstddef>
+#include <cstdlib>
+#include <cstring>
+#include <cassert>
+#include <limits>
+#include <iostream>
+#include <type_traits>
+#include <utility>
+#include <locale>
+#include <iterator>
+#include <utility>
+
+#ifdef __GNUC__
+ #include <cxxabi.h>
+#endif
+
+/*
+ * Abstractions for compiler-specific directives
+ */
+
+#ifdef __GNUC__
+ #define PCG_NOINLINE __attribute__((noinline))
+#else
+ #define PCG_NOINLINE
+#endif
+
+/*
+ * Some members of the PCG library use 128-bit math. When compiling on 64-bit
+ * platforms, both GCC and Clang provide 128-bit integer types that are ideal
+ * for the job.
+ *
+ * On 32-bit platforms (or with other compilers), we fall back to a C++
+ * class that provides 128-bit unsigned integers instead. It may seem
+ * like we're reinventing the wheel here, because libraries already exist
+ * that support large integers, but most existing libraries provide a very
+ * generic multiprecision code, but here we're operating at a fixed size.
+ * Also, most other libraries are fairly heavyweight. So we use a direct
+ * implementation. Sadly, it's much slower than hand-coded assembly or
+ * direct CPU support.
+ *
+ */
+#if __SIZEOF_INT128__
+ namespace pcg_extras {
+ typedef __uint128_t pcg128_t;
+ }
+ #define PCG_128BIT_CONSTANT(high,low) \
+ ((pcg128_t(high) << 64) + low)
+#else
+ #include "pcg_uint128.hpp"
+ namespace pcg_extras {
+ typedef pcg_extras::uint_x4<uint32_t,uint64_t> pcg128_t;
+ }
+ #define PCG_128BIT_CONSTANT(high,low) \
+ pcg128_t(high,low)
+ #define PCG_EMULATED_128BIT_MATH 1
+#endif
+
+
+namespace pcg_extras {
+
+/*
+ * We often need to represent a "number of bits". When used normally, these
+ * numbers are never greater than 128, so an unsigned char is plenty.
+ * If you're using a nonstandard generator of a larger size, you can set
+ * PCG_BITCOUNT_T to have it define it as a larger size. (Some compilers
+ * might produce faster code if you set it to an unsigned int.)
+ */
+
+#ifndef PCG_BITCOUNT_T
+ typedef uint8_t bitcount_t;
+#else
+ typedef PCG_BITCOUNT_T bitcount_t;
+#endif
+
+/*
+ * C++ requires us to be able to serialize RNG state by printing or reading
+ * it from a stream. Because we use 128-bit ints, we also need to be able
+ * ot print them, so here is code to do so.
+ *
+ * This code provides enough functionality to print 128-bit ints in decimal
+ * and zero-padded in hex. It's not a full-featured implementation.
+ */
+
+template <typename CharT, typename Traits>
+std::basic_ostream<CharT,Traits>&
+operator<<(std::basic_ostream<CharT,Traits>& out, pcg128_t value)
+{
+ auto desired_base = out.flags() & out.basefield;
+ bool want_hex = desired_base == out.hex;
+
+ if (want_hex) {
+ uint64_t highpart = uint64_t(value >> 64);
+ uint64_t lowpart = uint64_t(value);
+ auto desired_width = out.width();
+ if (desired_width > 16) {
+ out.width(desired_width - 16);
+ }
+ if (highpart != 0 || desired_width > 16)
+ out << highpart;
+ CharT oldfill;
+ if (highpart != 0) {
+ out.width(16);
+ oldfill = out.fill('0');
+ }
+ auto oldflags = out.setf(decltype(desired_base){}, out.showbase);
+ out << lowpart;
+ out.setf(oldflags);
+ if (highpart != 0) {
+ out.fill(oldfill);
+ }
+ return out;
+ }
+ constexpr size_t MAX_CHARS_128BIT = 40;
+
+ char buffer[MAX_CHARS_128BIT];
+ char* pos = buffer+sizeof(buffer);
+ *(--pos) = '\0';
+ constexpr auto BASE = pcg128_t(10ULL);
+ do {
+ auto div = value / BASE;
+ auto mod = uint32_t(value - (div * BASE));
+ *(--pos) = '0' + mod;
+ value = div;
+ } while(value != pcg128_t(0ULL));
+ return out << pos;
+}
+
+template <typename CharT, typename Traits>
+std::basic_istream<CharT,Traits>&
+operator>>(std::basic_istream<CharT,Traits>& in, pcg128_t& value)
+{
+ typename std::basic_istream<CharT,Traits>::sentry s(in);
+
+ if (!s)
+ return in;
+
+ constexpr auto BASE = pcg128_t(10ULL);
+ pcg128_t current(0ULL);
+ bool did_nothing = true;
+ bool overflow = false;
+ for(;;) {
+ CharT wide_ch = in.get();
+ if (!in.good())
+ break;
+ auto ch = in.narrow(wide_ch, '\0');
+ if (ch < '0' || ch > '9') {
+ in.unget();
+ break;
+ }
+ did_nothing = false;
+ pcg128_t digit(uint32_t(ch - '0'));
+ pcg128_t timesbase = current*BASE;
+ overflow = overflow || timesbase < current;
+ current = timesbase + digit;
+ overflow = overflow || current < digit;
+ }
+
+ if (did_nothing || overflow) {
+ in.setstate(std::ios::failbit);
+ if (overflow)
+ current = ~pcg128_t(0ULL);
+ }
+
+ value = current;
+
+ return in;
+}
+
+/*
+ * Likewise, if people use tiny rngs, we'll be serializing uint8_t.
+ * If we just used the provided IO operators, they'd read/write chars,
+ * not ints, so we need to define our own. We *can* redefine this operator
+ * here because we're in our own namespace.
+ */
+
+template <typename CharT, typename Traits>
+std::basic_ostream<CharT,Traits>&
+operator<<(std::basic_ostream<CharT,Traits>&out, uint8_t value)
+{
+ return out << uint32_t(value);
+}
+
+template <typename CharT, typename Traits>
+std::basic_istream<CharT,Traits>&
+operator>>(std::basic_istream<CharT,Traits>& in, uint8_t target)
+{
+ uint32_t value = 0xdecea5edU;
+ in >> value;
+ if (!in && value == 0xdecea5edU)
+ return in;
+ if (value > uint8_t(~0)) {
+ in.setstate(std::ios::failbit);
+ value = ~0U;
+ }
+ target = uint8_t(value);
+ return in;
+}
+
+/* Unfortunately, the above functions don't get found in preference to the
+ * built in ones, so we create some more specific overloads that will.
+ * Ugh.
+ */
+
+inline std::ostream& operator<<(std::ostream& out, uint8_t value)
+{
+ return pcg_extras::operator<< <char>(out, value);
+}
+
+inline std::istream& operator>>(std::istream& in, uint8_t& value)
+{
+ return pcg_extras::operator>> <char>(in, value);
+}
+
+
+
+/*
+ * Useful bitwise operations.
+ */
+
+/*
+ * XorShifts are invertable, but they are someting of a pain to invert.
+ * This function backs them out. It's used by the whacky "inside out"
+ * generator defined later.
+ */
+
+template <typename itype>
+inline itype unxorshift(itype x, bitcount_t bits, bitcount_t shift)
+{
+ if (2*shift >= bits) {
+ return x ^ (x >> shift);
+ }
+ itype lowmask1 = (itype(1U) << (bits - shift*2)) - 1;
+ itype highmask1 = ~lowmask1;
+ itype top1 = x;
+ itype bottom1 = x & lowmask1;
+ top1 ^= top1 >> shift;
+ top1 &= highmask1;
+ x = top1 | bottom1;
+ itype lowmask2 = (itype(1U) << (bits - shift)) - 1;
+ itype bottom2 = x & lowmask2;
+ bottom2 = unxorshift(bottom2, bits - shift, shift);
+ bottom2 &= lowmask1;
+ return top1 | bottom2;
+}
+
+/*
+ * Rotate left and right.
+ *
+ * In ideal world, compilers would spot idiomatic rotate code and convert it
+ * to a rotate instruction. Of course, opinions vary on what the correct
+ * idiom is and how to spot it. For clang, sometimes it generates better
+ * (but still crappy) code if you define PCG_USE_ZEROCHECK_ROTATE_IDIOM.
+ */
+
+template <typename itype>
+inline itype rotl(itype value, bitcount_t rot)
+{
+ constexpr bitcount_t bits = sizeof(itype) * 8;
+ constexpr bitcount_t mask = bits - 1;
+#if PCG_USE_ZEROCHECK_ROTATE_IDIOM
+ return rot ? (value << rot) | (value >> (bits - rot)) : value;
+#else
+ return (value << rot) | (value >> ((- rot) & mask));
+#endif
+}
+
+template <typename itype>
+inline itype rotr(itype value, bitcount_t rot)
+{
+ constexpr bitcount_t bits = sizeof(itype) * 8;
+ constexpr bitcount_t mask = bits - 1;
+#if PCG_USE_ZEROCHECK_ROTATE_IDIOM
+ return rot ? (value >> rot) | (value << (bits - rot)) : value;
+#else
+ return (value >> rot) | (value << ((- rot) & mask));
+#endif
+}
+
+/* Unfortunately, both Clang and GCC sometimes perform poorly when it comes
+ * to properly recognizing idiomatic rotate code, so for we also provide
+ * assembler directives (enabled with PCG_USE_INLINE_ASM). Boo, hiss.
+ * (I hope that these compilers get better so that this code can die.)
+ *
+ * These overloads will be preferred over the general template code above.
+ */
+#if PCG_USE_INLINE_ASM && __GNUC__ && (__x86_64__ || __i386__)
+
+inline uint8_t rotr(uint8_t value, bitcount_t rot)
+{
+ asm ("rorb %%cl, %0" : "=r" (value) : "0" (value), "c" (rot));
+ return value;
+}
+
+inline uint16_t rotr(uint16_t value, bitcount_t rot)
+{
+ asm ("rorw %%cl, %0" : "=r" (value) : "0" (value), "c" (rot));
+ return value;
+}
+
+inline uint32_t rotr(uint32_t value, bitcount_t rot)
+{
+ asm ("rorl %%cl, %0" : "=r" (value) : "0" (value), "c" (rot));
+ return value;
+}
+
+#if __x86_64__
+inline uint64_t rotr(uint64_t value, bitcount_t rot)
+{
+ asm ("rorq %%cl, %0" : "=r" (value) : "0" (value), "c" (rot));
+ return value;
+}
+#endif // __x86_64__
+
+#endif // PCG_USE_INLINE_ASM
+
+
+/*
+ * The C++ SeedSeq concept (modelled by seed_seq) can fill an array of
+ * 32-bit integers with seed data, but sometimes we want to produce
+ * larger or smaller integers.
+ *
+ * The following code handles this annoyance.
+ *
+ * uneven_copy will copy an array of 32-bit ints to an array of larger or
+ * smaller ints (actually, the code is general it only needing forward
+ * iterators). The copy is identical to the one that would be performed if
+ * we just did memcpy on a standard little-endian machine, but works
+ * regardless of the endian of the machine (or the weirdness of the ints
+ * involved).
+ *
+ * generate_to initializes an array of integers using a SeedSeq
+ * object. It is given the size as a static constant at compile time and
+ * tries to avoid memory allocation. If we're filling in 32-bit constants
+ * we just do it directly. If we need a separate buffer and it's small,
+ * we allocate it on the stack. Otherwise, we fall back to heap allocation.
+ * Ugh.
+ *
+ * generate_one produces a single value of some integral type using a
+ * SeedSeq object.
+ */
+
+ /* uneven_copy helper, case where destination ints are less than 32 bit. */
+
+template<class SrcIter, class DestIter>
+SrcIter uneven_copy_impl(
+ SrcIter src_first, DestIter dest_first, DestIter dest_last,
+ std::true_type)
+{
+ typedef typename std::iterator_traits<SrcIter>::value_type src_t;
+ typedef typename std::iterator_traits<DestIter>::value_type dest_t;
+
+ constexpr bitcount_t SRC_SIZE = sizeof(src_t);
+ constexpr bitcount_t DEST_SIZE = sizeof(dest_t);
+ constexpr bitcount_t DEST_BITS = DEST_SIZE * 8;
+ constexpr bitcount_t SCALE = SRC_SIZE / DEST_SIZE;
+
+ size_t count = 0;
+ src_t value;
+
+ while (dest_first != dest_last) {
+ if ((count++ % SCALE) == 0)
+ value = *src_first++; // Get more bits
+ else
+ value >>= DEST_BITS; // Move down bits
+
+ *dest_first++ = dest_t(value); // Truncates, ignores high bits.
+ }
+ return src_first;
+}
+
+ /* uneven_copy helper, case where destination ints are more than 32 bit. */
+
+template<class SrcIter, class DestIter>
+SrcIter uneven_copy_impl(
+ SrcIter src_first, DestIter dest_first, DestIter dest_last,
+ std::false_type)
+{
+ typedef typename std::iterator_traits<SrcIter>::value_type src_t;
+ typedef typename std::iterator_traits<DestIter>::value_type dest_t;
+
+ constexpr auto SRC_SIZE = sizeof(src_t);
+ constexpr auto SRC_BITS = SRC_SIZE * 8;
+ constexpr auto DEST_SIZE = sizeof(dest_t);
+ constexpr auto SCALE = (DEST_SIZE+SRC_SIZE-1) / SRC_SIZE;
+
+ while (dest_first != dest_last) {
+ dest_t value(0UL);
+ unsigned int shift = 0;
+
+ for (size_t i = 0; i < SCALE; ++i) {
+ value |= dest_t(*src_first++) << shift;
+ shift += SRC_BITS;
+ }
+
+ *dest_first++ = value;
+ }
+ return src_first;
+}
+
+/* uneven_copy, call the right code for larger vs. smaller */
+
+template<class SrcIter, class DestIter>
+inline SrcIter uneven_copy(SrcIter src_first,
+ DestIter dest_first, DestIter dest_last)
+{
+ typedef typename std::iterator_traits<SrcIter>::value_type src_t;
+ typedef typename std::iterator_traits<DestIter>::value_type dest_t;
+
+ constexpr bool DEST_IS_SMALLER = sizeof(dest_t) < sizeof(src_t);
+
+ return uneven_copy_impl(src_first, dest_first, dest_last,
+ std::integral_constant<bool, DEST_IS_SMALLER>{});
+}
+
+/* generate_to, fill in a fixed-size array of integral type using a SeedSeq
+ * (actually works for any random-access iterator)
+ */
+
+template <size_t size, typename SeedSeq, typename DestIter>
+inline void generate_to_impl(SeedSeq&& generator, DestIter dest,
+ std::true_type)
+{
+ generator.generate(dest, dest+size);
+}
+
+template <size_t size, typename SeedSeq, typename DestIter>
+void generate_to_impl(SeedSeq&& generator, DestIter dest,
+ std::false_type)
+{
+ typedef typename std::iterator_traits<DestIter>::value_type dest_t;
+ constexpr auto DEST_SIZE = sizeof(dest_t);
+ constexpr auto GEN_SIZE = sizeof(uint32_t);
+
+ constexpr bool GEN_IS_SMALLER = GEN_SIZE < DEST_SIZE;
+ constexpr size_t FROM_ELEMS =
+ GEN_IS_SMALLER
+ ? size * ((DEST_SIZE+GEN_SIZE-1) / GEN_SIZE)
+ : (size + (GEN_SIZE / DEST_SIZE) - 1)
+ / ((GEN_SIZE / DEST_SIZE) + GEN_IS_SMALLER);
+ // this odd code ^^^^^^^^^^^^^^^^^ is work-around for
+ // a bug: http://llvm.org/bugs/show_bug.cgi?id=21287
+
+ if (FROM_ELEMS <= 1024) {
+ uint32_t buffer[FROM_ELEMS];
+ generator.generate(buffer, buffer+FROM_ELEMS);
+ uneven_copy(buffer, dest, dest+size);
+ } else {
+ uint32_t* buffer = (uint32_t*) malloc(GEN_SIZE * FROM_ELEMS);
+ generator.generate(buffer, buffer+FROM_ELEMS);
+ uneven_copy(buffer, dest, dest+size);
+ free(buffer);
+ }
+}
+
+template <size_t size, typename SeedSeq, typename DestIter>
+inline void generate_to(SeedSeq&& generator, DestIter dest)
+{
+ typedef typename std::iterator_traits<DestIter>::value_type dest_t;
+ constexpr bool IS_32BIT = sizeof(dest_t) == sizeof(uint32_t);
+
+ generate_to_impl<size>(std::forward<SeedSeq>(generator), dest,
+ std::integral_constant<bool, IS_32BIT>{});
+}
+
+/* generate_one, produce a value of integral type using a SeedSeq
+ * (optionally, we can have it produce more than one and pick which one
+ * we want)
+ */
+
+template <typename UInt, size_t i = 0UL, size_t N = i+1UL, typename SeedSeq>
+inline UInt generate_one(SeedSeq&& generator)
+{
+ UInt result[N];
+ generate_to<N>(std::forward<SeedSeq>(generator), result);
+ return result[i];
+}
+
+template <typename RngType>
+auto bounded_rand(RngType& rng, typename RngType::result_type upper_bound)
+ -> typename RngType::result_type
+{
+ typedef typename RngType::result_type rtype;
+ rtype threshold = (RngType::max() - RngType::min() + rtype(1) - upper_bound)
+ % upper_bound;
+ for (;;) {
+ rtype r = rng() - RngType::min();
+ if (r >= threshold)
+ return r % upper_bound;
+ }
+}
+
+template <typename Iter, typename RandType>
+void shuffle(Iter from, Iter to, RandType&& rng)
+{
+ typedef typename std::iterator_traits<Iter>::difference_type delta_t;
+ auto count = to - from;
+ while (count > 1) {
+ delta_t chosen(bounded_rand(rng, count));
+ --count;
+ --to;
+ using std::swap;
+ swap(*(from+chosen), *to);
+ }
+}
+
+/*
+ * Although std::seed_seq is useful, it isn't everything. Often we want to
+ * initialize a random-number generator some other way, such as from a random
+ * device.
+ *
+ * Technically, it does not meet the requirements of a SeedSequence because
+ * it lacks some of the rarely-used member functions (some of which would
+ * be impossible to provide). However the C++ standard is quite specific
+ * that actual engines only called the generate method, so it ought not to be
+ * a problem in practice.
+ */
+
+template <typename RngType>
+class seed_seq_from {
+private:
+ RngType rng_;
+
+ typedef uint_least32_t result_type;
+
+public:
+ template<typename... Args>
+ seed_seq_from(Args&&... args) :
+ rng_(std::forward<Args>(args)...)
+ {
+ // Nothing (else) to do...
+ }
+
+ template<typename Iter>
+ void generate(Iter start, Iter finish)
+ {
+ for (auto i = start; i != finish; ++i)
+ *i = result_type(rng_());
+ }
+
+ constexpr size_t size() const
+ {
+ return (sizeof(typename RngType::result_type) > sizeof(result_type)
+ && RngType::max() > ~size_t(0UL))
+ ? ~size_t(0UL)
+ : size_t(RngType::max());
+ }
+};
+
+/*
+ * Sometimes you might want a distinct seed based on when the program
+ * was compiled. That way, a particular instance of the program will
+ * behave the same way, but when recompiled it'll produce a different
+ * value.
+ */
+
+template <typename IntType>
+struct static_arbitrary_seed {
+private:
+ static constexpr IntType fnv(IntType hash, const char* pos) {
+ return *pos == '\0'
+ ? hash
+ : fnv((hash * IntType(16777619U)) ^ *pos, (pos+1));
+ }
+
+public:
+ static constexpr IntType value = fnv(IntType(2166136261U ^ sizeof(IntType)),
+ __DATE__ __TIME__ __FILE__);
+};
+
+// Sometimes, when debugging or testing, it's handy to be able print the name
+// of a (in human-readable form). This code allows the idiom:
+//
+// cout << printable_typename<my_foo_type_t>()
+//
+// to print out my_foo_type_t (or its concrete type if it is a synonym)
+
+template <typename T>
+struct printable_typename {};
+
+template <typename T>
+std::ostream& operator<<(std::ostream& out, printable_typename<T>) {
+ const char *implementation_typename = typeid(T).name();
+#ifdef __GNUC__
+ int status;
+ const char* pretty_name =
+ abi::__cxa_demangle(implementation_typename, NULL, NULL, &status);
+ if (status == 0)
+ out << pretty_name;
+ free((void*) pretty_name);
+ if (status == 0)
+ return out;
+#endif
+ out << implementation_typename;
+ return out;
+}
+
+} // namespace pcg_extras
+
+#endif // PCG_EXTRAS_HPP_INCLUDED
[3/8] impala git commit: IMPALA-5754: Improve randomness of
rand()/random()
Posted by ta...@apache.org.
http://git-wip-us.apache.org/repos/asf/impala/blob/4feb4f3a/be/src/thirdparty/pcg-cpp-0.98/include/pcg_random.hpp
----------------------------------------------------------------------
diff --git a/be/src/thirdparty/pcg-cpp-0.98/include/pcg_random.hpp b/be/src/thirdparty/pcg-cpp-0.98/include/pcg_random.hpp
new file mode 100644
index 0000000..3f04d85
--- /dev/null
+++ b/be/src/thirdparty/pcg-cpp-0.98/include/pcg_random.hpp
@@ -0,0 +1,1751 @@
+/*
+ * PCG Random Number Generation for C++
+ *
+ * Copyright 2014 Melissa O'Neill <on...@pcg-random.org>
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * For additional information about the PCG random number generation scheme,
+ * including its license and other licensing options, visit
+ *
+ * http://www.pcg-random.org
+ */
+
+/*
+ * This code provides the reference implementation of the PCG family of
+ * random number generators. The code is complex because it implements
+ *
+ * - several members of the PCG family, specifically members corresponding
+ * to the output functions:
+ * - XSH RR (good for 64-bit state, 32-bit output)
+ * - XSH RS (good for 64-bit state, 32-bit output)
+ * - XSL RR (good for 128-bit state, 64-bit output)
+ * - RXS M XS (statistically most powerful generator)
+ * - XSL RR RR (good for 128-bit state, 128-bit output)
+ * - and RXS, RXS M, XSH, XSL (mostly for testing)
+ * - at potentially *arbitrary* bit sizes
+ * - with four different techniques for random streams (MCG, one-stream
+ * LCG, settable-stream LCG, unique-stream LCG)
+ * - and the extended generation schemes allowing arbitrary periods
+ * - with all features of C++11 random number generation (and more),
+ * some of which are somewhat painful, including
+ * - initializing with a SeedSequence which writes 32-bit values
+ * to memory, even though the state of the generator may not
+ * use 32-bit values (it might use smaller or larger integers)
+ * - I/O for RNGs and a prescribed format, which needs to handle
+ * the issue that 8-bit and 128-bit integers don't have working
+ * I/O routines (e.g., normally 8-bit = char, not integer)
+ * - equality and inequality for RNGs
+ * - and a number of convenience typedefs to mask all the complexity
+ *
+ * The code employes a fairly heavy level of abstraction, and has to deal
+ * with various C++ minutia. If you're looking to learn about how the PCG
+ * scheme works, you're probably best of starting with one of the other
+ * codebases (see www.pcg-random.org). But if you're curious about the
+ * constants for the various output functions used in those other, simpler,
+ * codebases, this code shows how they are calculated.
+ *
+ * On the positive side, at least there are convenience typedefs so that you
+ * can say
+ *
+ * pcg32 myRNG;
+ *
+ * rather than:
+ *
+ * pcg_detail::engine<
+ * uint32_t, // Output Type
+ * uint64_t, // State Type
+ * pcg_detail::xsh_rr_mixin<uint32_t, uint64_t>, true, // Output Func
+ * pcg_detail::specific_stream<uint64_t>, // Stream Kind
+ * pcg_detail::default_multiplier<uint64_t> // LCG Mult
+ * > myRNG;
+ *
+ */
+
+#ifndef PCG_RAND_HPP_INCLUDED
+#define PCG_RAND_HPP_INCLUDED 1
+
+#include <cinttypes>
+#include <cstddef>
+#include <cstdlib>
+#include <cstring>
+#include <cassert>
+#include <limits>
+#include <iostream>
+#include <type_traits>
+#include <utility>
+#include <locale>
+#include <new>
+#include <stdexcept>
+
+/*
+ * The pcg_extras namespace contains some support code that is likley to
+ * be useful for a variety of RNGs, including:
+ * - 128-bit int support for platforms where it isn't available natively
+ * - bit twiddling operations
+ * - I/O of 128-bit and 8-bit integers
+ * - Handling the evilness of SeedSeq
+ * - Support for efficiently producing random numbers less than a given
+ * bound
+ */
+
+#include "pcg_extras.hpp"
+
+namespace pcg_detail {
+
+using namespace pcg_extras;
+
+/*
+ * The LCG generators need some constants to function. This code lets you
+ * look up the constant by *type*. For example
+ *
+ * default_multiplier<uint32_t>::multiplier()
+ *
+ * gives you the default multipler for 32-bit integers. We use the name
+ * of the constant and not a generic word like value to allow these classes
+ * to be used as mixins.
+ */
+
+template <typename T>
+struct default_multiplier {
+ // Not defined for an arbitrary type
+};
+
+template <typename T>
+struct default_increment {
+ // Not defined for an arbitrary type
+};
+
+#define PCG_DEFINE_CONSTANT(type, what, kind, constant) \
+ template <> \
+ struct what ## _ ## kind<type> { \
+ static constexpr type kind() { \
+ return constant; \
+ } \
+ };
+
+PCG_DEFINE_CONSTANT(uint8_t, default, multiplier, 141U)
+PCG_DEFINE_CONSTANT(uint8_t, default, increment, 77U)
+
+PCG_DEFINE_CONSTANT(uint16_t, default, multiplier, 12829U)
+PCG_DEFINE_CONSTANT(uint16_t, default, increment, 47989U)
+
+PCG_DEFINE_CONSTANT(uint32_t, default, multiplier, 747796405U)
+PCG_DEFINE_CONSTANT(uint32_t, default, increment, 2891336453U)
+
+PCG_DEFINE_CONSTANT(uint64_t, default, multiplier, 6364136223846793005ULL)
+PCG_DEFINE_CONSTANT(uint64_t, default, increment, 1442695040888963407ULL)
+
+PCG_DEFINE_CONSTANT(pcg128_t, default, multiplier,
+ PCG_128BIT_CONSTANT(2549297995355413924ULL,4865540595714422341ULL))
+PCG_DEFINE_CONSTANT(pcg128_t, default, increment,
+ PCG_128BIT_CONSTANT(6364136223846793005ULL,1442695040888963407ULL))
+
+
+/*
+ * Each PCG generator is available in four variants, based on how it applies
+ * the additive constant for its underlying LCG; the variations are:
+ *
+ * single stream - all instances use the same fixed constant, thus
+ * the RNG always somewhere in same sequence
+ * mcg - adds zero, resulting in a single stream and reduced
+ * period
+ * specific stream - the constant can be changed at any time, selecting
+ * a different random sequence
+ * unique stream - the constant is based on the memory addresss of the
+ * object, thus every RNG has its own unique sequence
+ *
+ * This variation is provided though mixin classes which define a function
+ * value called increment() that returns the nesessary additive constant.
+ */
+
+
+
+/*
+ * unique stream
+ */
+
+
+template <typename itype>
+class unique_stream {
+protected:
+ static constexpr bool is_mcg = false;
+
+ // Is never called, but is provided for symmetry with specific_stream
+ void set_stream(...)
+ {
+ abort();
+ }
+
+public:
+ typedef itype state_type;
+
+ constexpr itype increment() const {
+ return itype(reinterpret_cast<unsigned long>(this) | 1);
+ }
+
+ constexpr itype stream() const
+ {
+ return increment() >> 1;
+ }
+
+ static constexpr bool can_specify_stream = false;
+
+ static constexpr size_t streams_pow2()
+ {
+ return (sizeof(itype) < sizeof(size_t) ? sizeof(itype)
+ : sizeof(size_t))*8 - 1u;
+ }
+
+protected:
+ constexpr unique_stream() = default;
+};
+
+
+/*
+ * no stream (mcg)
+ */
+
+template <typename itype>
+class no_stream {
+protected:
+ static constexpr bool is_mcg = true;
+
+ // Is never called, but is provided for symmetry with specific_stream
+ void set_stream(...)
+ {
+ abort();
+ }
+
+public:
+ typedef itype state_type;
+
+ static constexpr itype increment() {
+ return 0;
+ }
+
+ static constexpr bool can_specify_stream = false;
+
+ static constexpr size_t streams_pow2()
+ {
+ return 0u;
+ }
+
+protected:
+ constexpr no_stream() = default;
+};
+
+
+/*
+ * single stream/sequence (oneseq)
+ */
+
+template <typename itype>
+class oneseq_stream : public default_increment<itype> {
+protected:
+ static constexpr bool is_mcg = false;
+
+ // Is never called, but is provided for symmetry with specific_stream
+ void set_stream(...)
+ {
+ abort();
+ }
+
+public:
+ typedef itype state_type;
+
+ static constexpr itype stream()
+ {
+ return default_increment<itype>::increment() >> 1;
+ }
+
+ static constexpr bool can_specify_stream = false;
+
+ static constexpr size_t streams_pow2()
+ {
+ return 0u;
+ }
+
+protected:
+ constexpr oneseq_stream() = default;
+};
+
+
+/*
+ * specific stream
+ */
+
+template <typename itype>
+class specific_stream {
+protected:
+ static constexpr bool is_mcg = false;
+
+ itype inc_ = default_increment<itype>::increment();
+
+public:
+ typedef itype state_type;
+ typedef itype stream_state;
+
+ constexpr itype increment() const {
+ return inc_;
+ }
+
+ itype stream()
+ {
+ return inc_ >> 1;
+ }
+
+ void set_stream(itype specific_seq)
+ {
+ inc_ = (specific_seq << 1) | 1;
+ }
+
+ static constexpr bool can_specify_stream = true;
+
+ static constexpr size_t streams_pow2()
+ {
+ return (sizeof(itype)*8) - 1u;
+ }
+
+protected:
+ specific_stream() = default;
+
+ specific_stream(itype specific_seq)
+ : inc_((specific_seq << 1) | itype(1U))
+ {
+ // Nothing (else) to do.
+ }
+};
+
+
+/*
+ * This is where it all comes together. This function joins together three
+ * mixin classes which define
+ * - the LCG additive constant (the stream)
+ * - the LCG multiplier
+ * - the output function
+ * in addition, we specify the type of the LCG state, and the result type,
+ * and whether to use the pre-advance version of the state for the output
+ * (increasing instruction-level parallelism) or the post-advance version
+ * (reducing register pressure).
+ *
+ * Given the high level of parameterization, the code has to use some
+ * template-metaprogramming tricks to handle some of the suble variations
+ * involved.
+ */
+
+template <typename xtype, typename itype,
+ typename output_mixin,
+ bool output_previous = true,
+ typename stream_mixin = oneseq_stream<itype>,
+ typename multiplier_mixin = default_multiplier<itype> >
+class engine : protected output_mixin,
+ public stream_mixin,
+ protected multiplier_mixin {
+protected:
+ itype state_;
+
+ struct can_specify_stream_tag {};
+ struct no_specifiable_stream_tag {};
+
+ using stream_mixin::increment;
+ using multiplier_mixin::multiplier;
+
+public:
+ typedef xtype result_type;
+ typedef itype state_type;
+
+ static constexpr size_t period_pow2()
+ {
+ return sizeof(state_type)*8 - 2*stream_mixin::is_mcg;
+ }
+
+ // It would be nice to use std::numeric_limits for these, but
+ // we can't be sure that it'd be defined for the 128-bit types.
+
+ static constexpr result_type min()
+ {
+ return result_type(0UL);
+ }
+
+ static constexpr result_type max()
+ {
+ return ~result_type(0UL);
+ }
+
+protected:
+ itype bump(itype state)
+ {
+ return state * multiplier() + increment();
+ }
+
+ itype base_generate()
+ {
+ return state_ = bump(state_);
+ }
+
+ itype base_generate0()
+ {
+ itype old_state = state_;
+ state_ = bump(state_);
+ return old_state;
+ }
+
+public:
+ result_type operator()()
+ {
+ if (output_previous)
+ return this->output(base_generate0());
+ else
+ return this->output(base_generate());
+ }
+
+ result_type operator()(result_type upper_bound)
+ {
+ return bounded_rand(*this, upper_bound);
+ }
+
+protected:
+ static itype advance(itype state, itype delta,
+ itype cur_mult, itype cur_plus);
+
+ static itype distance(itype cur_state, itype newstate, itype cur_mult,
+ itype cur_plus, itype mask = ~itype(0U));
+
+ itype distance(itype newstate, itype mask = ~itype(0U)) const
+ {
+ return distance(state_, newstate, multiplier(), increment(), mask);
+ }
+
+public:
+ void advance(itype delta)
+ {
+ state_ = advance(state_, delta, this->multiplier(), this->increment());
+ }
+
+ void backstep(itype delta)
+ {
+ advance(-delta);
+ }
+
+ void discard(itype delta)
+ {
+ advance(delta);
+ }
+
+ bool wrapped()
+ {
+ if (stream_mixin::is_mcg) {
+ // For MCGs, the low order two bits never change. In this
+ // implementation, we keep them fixed at 3 to make this test
+ // easier.
+ return state_ == 3;
+ } else {
+ return state_ == 0;
+ }
+ }
+
+ engine(itype state = itype(0xcafef00dd15ea5e5ULL))
+ : state_(this->is_mcg ? state|state_type(3U)
+ : bump(state + this->increment()))
+ {
+ // Nothing else to do.
+ }
+
+ // This function may or may not exist. It thus has to be a template
+ // to use SFINAE; users don't have to worry about its template-ness.
+
+ template <typename sm = stream_mixin>
+ engine(itype state, typename sm::stream_state stream_seed)
+ : stream_mixin(stream_seed),
+ state_(this->is_mcg ? state|state_type(3U)
+ : bump(state + this->increment()))
+ {
+ // Nothing else to do.
+ }
+
+ template<typename SeedSeq>
+ engine(SeedSeq&& seedSeq, typename std::enable_if<
+ !stream_mixin::can_specify_stream
+ && !std::is_convertible<SeedSeq, itype>::value
+ && !std::is_convertible<SeedSeq, engine>::value,
+ no_specifiable_stream_tag>::type = {})
+ : engine(generate_one<itype>(std::forward<SeedSeq>(seedSeq)))
+ {
+ // Nothing else to do.
+ }
+
+ template<typename SeedSeq>
+ engine(SeedSeq&& seedSeq, typename std::enable_if<
+ stream_mixin::can_specify_stream
+ && !std::is_convertible<SeedSeq, itype>::value
+ && !std::is_convertible<SeedSeq, engine>::value,
+ can_specify_stream_tag>::type = {})
+ : engine(generate_one<itype,1,2>(seedSeq),
+ generate_one<itype,0,2>(seedSeq))
+ {
+ // Nothing else to do.
+ }
+
+
+ template<typename... Args>
+ void seed(Args&&... args)
+ {
+ new (this) engine(std::forward<Args>(args)...);
+ }
+
+ template <typename xtype1, typename itype1,
+ typename output_mixin1, bool output_previous1,
+ typename stream_mixin_lhs, typename multiplier_mixin_lhs,
+ typename stream_mixin_rhs, typename multiplier_mixin_rhs>
+ friend bool operator==(const engine<xtype1,itype1,
+ output_mixin1,output_previous1,
+ stream_mixin_lhs, multiplier_mixin_lhs>&,
+ const engine<xtype1,itype1,
+ output_mixin1,output_previous1,
+ stream_mixin_rhs, multiplier_mixin_rhs>&);
+
+ template <typename xtype1, typename itype1,
+ typename output_mixin1, bool output_previous1,
+ typename stream_mixin_lhs, typename multiplier_mixin_lhs,
+ typename stream_mixin_rhs, typename multiplier_mixin_rhs>
+ friend itype1 operator-(const engine<xtype1,itype1,
+ output_mixin1,output_previous1,
+ stream_mixin_lhs, multiplier_mixin_lhs>&,
+ const engine<xtype1,itype1,
+ output_mixin1,output_previous1,
+ stream_mixin_rhs, multiplier_mixin_rhs>&);
+
+ template <typename CharT, typename Traits,
+ typename xtype1, typename itype1,
+ typename output_mixin1, bool output_previous1,
+ typename stream_mixin1, typename multiplier_mixin1>
+ friend std::basic_ostream<CharT,Traits>&
+ operator<<(std::basic_ostream<CharT,Traits>& out,
+ const engine<xtype1,itype1,
+ output_mixin1,output_previous1,
+ stream_mixin1, multiplier_mixin1>&);
+
+ template <typename CharT, typename Traits,
+ typename xtype1, typename itype1,
+ typename output_mixin1, bool output_previous1,
+ typename stream_mixin1, typename multiplier_mixin1>
+ friend std::basic_istream<CharT,Traits>&
+ operator>>(std::basic_istream<CharT,Traits>& in,
+ engine<xtype1, itype1,
+ output_mixin1, output_previous1,
+ stream_mixin1, multiplier_mixin1>& rng);
+};
+
+template <typename CharT, typename Traits,
+ typename xtype, typename itype,
+ typename output_mixin, bool output_previous,
+ typename stream_mixin, typename multiplier_mixin>
+std::basic_ostream<CharT,Traits>&
+operator<<(std::basic_ostream<CharT,Traits>& out,
+ const engine<xtype,itype,
+ output_mixin,output_previous,
+ stream_mixin, multiplier_mixin>& rng)
+{
+ auto orig_flags = out.flags(std::ios_base::dec | std::ios_base::left);
+ auto space = out.widen(' ');
+ auto orig_fill = out.fill();
+
+ out << rng.multiplier() << space
+ << rng.increment() << space
+ << rng.state_;
+
+ out.flags(orig_flags);
+ out.fill(orig_fill);
+ return out;
+}
+
+
+template <typename CharT, typename Traits,
+ typename xtype, typename itype,
+ typename output_mixin, bool output_previous,
+ typename stream_mixin, typename multiplier_mixin>
+std::basic_istream<CharT,Traits>&
+operator>>(std::basic_istream<CharT,Traits>& in,
+ engine<xtype,itype,
+ output_mixin,output_previous,
+ stream_mixin, multiplier_mixin>& rng)
+{
+ auto orig_flags = in.flags(std::ios_base::dec | std::ios_base::skipws);
+
+ itype multiplier, increment, state;
+ in >> multiplier >> increment >> state;
+
+ if (!in.fail()) {
+ bool good = true;
+ if (multiplier != rng.multiplier()) {
+ good = false;
+ } else if (rng.can_specify_stream) {
+ rng.set_stream(increment >> 1);
+ } else if (increment != rng.increment()) {
+ good = false;
+ }
+ if (good) {
+ rng.state_ = state;
+ } else {
+ in.clear(std::ios::failbit);
+ }
+ }
+
+ in.flags(orig_flags);
+ return in;
+}
+
+
+template <typename xtype, typename itype,
+ typename output_mixin, bool output_previous,
+ typename stream_mixin, typename multiplier_mixin>
+itype engine<xtype,itype,output_mixin,output_previous,stream_mixin,
+ multiplier_mixin>::advance(
+ itype state, itype delta, itype cur_mult, itype cur_plus)
+{
+ // The method used here is based on Brown, "Random Number Generation
+ // with Arbitrary Stride,", Transactions of the American Nuclear
+ // Society (Nov. 1994). The algorithm is very similar to fast
+ // exponentiation.
+ //
+ // Even though delta is an unsigned integer, we can pass a
+ // signed integer to go backwards, it just goes "the long way round".
+
+ constexpr itype ZERO = 0u; // itype may be a non-trivial types, so
+ constexpr itype ONE = 1u; // we define some ugly constants.
+ itype acc_mult = 1;
+ itype acc_plus = 0;
+ while (delta > ZERO) {
+ if (delta & ONE) {
+ acc_mult *= cur_mult;
+ acc_plus = acc_plus*cur_mult + cur_plus;
+ }
+ cur_plus = (cur_mult+ONE)*cur_plus;
+ cur_mult *= cur_mult;
+ delta >>= 1;
+ }
+ return acc_mult * state + acc_plus;
+}
+
+template <typename xtype, typename itype,
+ typename output_mixin, bool output_previous,
+ typename stream_mixin, typename multiplier_mixin>
+itype engine<xtype,itype,output_mixin,output_previous,stream_mixin,
+ multiplier_mixin>::distance(
+ itype cur_state, itype newstate, itype cur_mult, itype cur_plus, itype mask)
+{
+ constexpr itype ONE = 1u; // itype could be weird, so use constant
+ itype the_bit = stream_mixin::is_mcg ? itype(4u) : itype(1u);
+ itype distance = 0u;
+ while ((cur_state & mask) != (newstate & mask)) {
+ if ((cur_state & the_bit) != (newstate & the_bit)) {
+ cur_state = cur_state * cur_mult + cur_plus;
+ distance |= the_bit;
+ }
+ assert((cur_state & the_bit) == (newstate & the_bit));
+ the_bit <<= 1;
+ cur_plus = (cur_mult+ONE)*cur_plus;
+ cur_mult *= cur_mult;
+ }
+ return stream_mixin::is_mcg ? distance >> 2 : distance;
+}
+
+template <typename xtype, typename itype,
+ typename output_mixin, bool output_previous,
+ typename stream_mixin_lhs, typename multiplier_mixin_lhs,
+ typename stream_mixin_rhs, typename multiplier_mixin_rhs>
+itype operator-(const engine<xtype,itype,
+ output_mixin,output_previous,
+ stream_mixin_lhs, multiplier_mixin_lhs>& lhs,
+ const engine<xtype,itype,
+ output_mixin,output_previous,
+ stream_mixin_rhs, multiplier_mixin_rhs>& rhs)
+{
+ if (lhs.multiplier() != rhs.multiplier()
+ || lhs.increment() != rhs.increment())
+ throw std::logic_error("incomparable generators");
+ return rhs.distance(lhs.state_);
+}
+
+
+template <typename xtype, typename itype,
+ typename output_mixin, bool output_previous,
+ typename stream_mixin_lhs, typename multiplier_mixin_lhs,
+ typename stream_mixin_rhs, typename multiplier_mixin_rhs>
+bool operator==(const engine<xtype,itype,
+ output_mixin,output_previous,
+ stream_mixin_lhs, multiplier_mixin_lhs>& lhs,
+ const engine<xtype,itype,
+ output_mixin,output_previous,
+ stream_mixin_rhs, multiplier_mixin_rhs>& rhs)
+{
+ return (lhs.multiplier() == rhs.multiplier())
+ && (lhs.increment() == rhs.increment())
+ && (lhs.state_ == rhs.state_);
+}
+
+template <typename xtype, typename itype,
+ typename output_mixin, bool output_previous,
+ typename stream_mixin_lhs, typename multiplier_mixin_lhs,
+ typename stream_mixin_rhs, typename multiplier_mixin_rhs>
+inline bool operator!=(const engine<xtype,itype,
+ output_mixin,output_previous,
+ stream_mixin_lhs, multiplier_mixin_lhs>& lhs,
+ const engine<xtype,itype,
+ output_mixin,output_previous,
+ stream_mixin_rhs, multiplier_mixin_rhs>& rhs)
+{
+ return !operator==(lhs,rhs);
+}
+
+
+template <typename xtype, typename itype,
+ template<typename XT,typename IT> class output_mixin,
+ bool output_previous = (sizeof(itype) <= 8)>
+using oneseq_base = engine<xtype, itype,
+ output_mixin<xtype, itype>, output_previous,
+ oneseq_stream<itype> >;
+
+template <typename xtype, typename itype,
+ template<typename XT,typename IT> class output_mixin,
+ bool output_previous = (sizeof(itype) <= 8)>
+using unique_base = engine<xtype, itype,
+ output_mixin<xtype, itype>, output_previous,
+ unique_stream<itype> >;
+
+template <typename xtype, typename itype,
+ template<typename XT,typename IT> class output_mixin,
+ bool output_previous = (sizeof(itype) <= 8)>
+using setseq_base = engine<xtype, itype,
+ output_mixin<xtype, itype>, output_previous,
+ specific_stream<itype> >;
+
+template <typename xtype, typename itype,
+ template<typename XT,typename IT> class output_mixin,
+ bool output_previous = (sizeof(itype) <= 8)>
+using mcg_base = engine<xtype, itype,
+ output_mixin<xtype, itype>, output_previous,
+ no_stream<itype> >;
+
+/*
+ * OUTPUT FUNCTIONS.
+ *
+ * These are the core of the PCG generation scheme. They specify how to
+ * turn the base LCG's internal state into the output value of the final
+ * generator.
+ *
+ * They're implemented as mixin classes.
+ *
+ * All of the classes have code that is written to allow it to be applied
+ * at *arbitrary* bit sizes, although in practice they'll only be used at
+ * standard sizes supported by C++.
+ */
+
+/*
+ * XSH RS -- high xorshift, followed by a random shift
+ *
+ * Fast. A good performer.
+ */
+
+template <typename xtype, typename itype>
+struct xsh_rs_mixin {
+ static xtype output(itype internal)
+ {
+ constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
+ constexpr bitcount_t xtypebits = bitcount_t(sizeof(xtype) * 8);
+ constexpr bitcount_t sparebits = bits - xtypebits;
+ constexpr bitcount_t opbits =
+ sparebits-5 >= 64 ? 5
+ : sparebits-4 >= 32 ? 4
+ : sparebits-3 >= 16 ? 3
+ : sparebits-2 >= 4 ? 2
+ : sparebits-1 >= 1 ? 1
+ : 0;
+ constexpr bitcount_t mask = (1 << opbits) - 1;
+ constexpr bitcount_t maxrandshift = mask;
+ constexpr bitcount_t topspare = opbits;
+ constexpr bitcount_t bottomspare = sparebits - topspare;
+ constexpr bitcount_t xshift = topspare + (xtypebits+maxrandshift)/2;
+ bitcount_t rshift =
+ opbits ? bitcount_t(internal >> (bits - opbits)) & mask : 0;
+ internal ^= internal >> xshift;
+ xtype result = xtype(internal >> (bottomspare - maxrandshift + rshift));
+ return result;
+ }
+};
+
+/*
+ * XSH RR -- high xorshift, followed by a random rotate
+ *
+ * Fast. A good performer. Slightly better statistically than XSH RS.
+ */
+
+template <typename xtype, typename itype>
+struct xsh_rr_mixin {
+ static xtype output(itype internal)
+ {
+ constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
+ constexpr bitcount_t xtypebits = bitcount_t(sizeof(xtype)*8);
+ constexpr bitcount_t sparebits = bits - xtypebits;
+ constexpr bitcount_t wantedopbits =
+ xtypebits >= 128 ? 7
+ : xtypebits >= 64 ? 6
+ : xtypebits >= 32 ? 5
+ : xtypebits >= 16 ? 4
+ : 3;
+ constexpr bitcount_t opbits =
+ sparebits >= wantedopbits ? wantedopbits
+ : sparebits;
+ constexpr bitcount_t amplifier = wantedopbits - opbits;
+ constexpr bitcount_t mask = (1 << opbits) - 1;
+ constexpr bitcount_t topspare = opbits;
+ constexpr bitcount_t bottomspare = sparebits - topspare;
+ constexpr bitcount_t xshift = (topspare + xtypebits)/2;
+ bitcount_t rot = opbits ? bitcount_t(internal >> (bits - opbits)) & mask
+ : 0;
+ bitcount_t amprot = (rot << amplifier) & mask;
+ internal ^= internal >> xshift;
+ xtype result = xtype(internal >> bottomspare);
+ result = rotr(result, amprot);
+ return result;
+ }
+};
+
+/*
+ * RXS -- random xorshift
+ */
+
+template <typename xtype, typename itype>
+struct rxs_mixin {
+static xtype output_rxs(itype internal)
+ {
+ constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
+ constexpr bitcount_t xtypebits = bitcount_t(sizeof(xtype)*8);
+ constexpr bitcount_t shift = bits - xtypebits;
+ constexpr bitcount_t extrashift = (xtypebits - shift)/2;
+ bitcount_t rshift = shift > 64+8 ? (internal >> (bits - 6)) & 63
+ : shift > 32+4 ? (internal >> (bits - 5)) & 31
+ : shift > 16+2 ? (internal >> (bits - 4)) & 15
+ : shift > 8+1 ? (internal >> (bits - 3)) & 7
+ : shift > 4+1 ? (internal >> (bits - 2)) & 3
+ : shift > 2+1 ? (internal >> (bits - 1)) & 1
+ : 0;
+ internal ^= internal >> (shift + extrashift - rshift);
+ xtype result = internal >> rshift;
+ return result;
+ }
+};
+
+/*
+ * RXS M XS -- random xorshift, mcg multiply, fixed xorshift
+ *
+ * The most statistically powerful generator, but all those steps
+ * make it slower than some of the others. We give it the rottenest jobs.
+ *
+ * Because it's usually used in contexts where the state type and the
+ * result type are the same, it is a permutation and is thus invertable.
+ * We thus provide a function to invert it. This function is used to
+ * for the "inside out" generator used by the extended generator.
+ */
+
+/* Defined type-based concepts for the multiplication step. They're actually
+ * all derived by truncating the 128-bit, which was computed to be a good
+ * "universal" constant.
+ */
+
+template <typename T>
+struct mcg_multiplier {
+ // Not defined for an arbitrary type
+};
+
+template <typename T>
+struct mcg_unmultiplier {
+ // Not defined for an arbitrary type
+};
+
+PCG_DEFINE_CONSTANT(uint8_t, mcg, multiplier, 217U)
+PCG_DEFINE_CONSTANT(uint8_t, mcg, unmultiplier, 105U)
+
+PCG_DEFINE_CONSTANT(uint16_t, mcg, multiplier, 62169U)
+PCG_DEFINE_CONSTANT(uint16_t, mcg, unmultiplier, 28009U)
+
+PCG_DEFINE_CONSTANT(uint32_t, mcg, multiplier, 277803737U)
+PCG_DEFINE_CONSTANT(uint32_t, mcg, unmultiplier, 2897767785U)
+
+PCG_DEFINE_CONSTANT(uint64_t, mcg, multiplier, 12605985483714917081ULL)
+PCG_DEFINE_CONSTANT(uint64_t, mcg, unmultiplier, 15009553638781119849ULL)
+
+PCG_DEFINE_CONSTANT(pcg128_t, mcg, multiplier,
+ PCG_128BIT_CONSTANT(17766728186571221404ULL, 12605985483714917081ULL))
+PCG_DEFINE_CONSTANT(pcg128_t, mcg, unmultiplier,
+ PCG_128BIT_CONSTANT(14422606686972528997ULL, 15009553638781119849ULL))
+
+
+template <typename xtype, typename itype>
+struct rxs_m_xs_mixin {
+ static xtype output(itype internal)
+ {
+ constexpr bitcount_t xtypebits = bitcount_t(sizeof(xtype) * 8);
+ constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
+ constexpr bitcount_t opbits = xtypebits >= 128 ? 6
+ : xtypebits >= 64 ? 5
+ : xtypebits >= 32 ? 4
+ : xtypebits >= 16 ? 3
+ : 2;
+ constexpr bitcount_t shift = bits - xtypebits;
+ constexpr bitcount_t mask = (1 << opbits) - 1;
+ bitcount_t rshift =
+ opbits ? bitcount_t(internal >> (bits - opbits)) & mask : 0;
+ internal ^= internal >> (opbits + rshift);
+ internal *= mcg_multiplier<itype>::multiplier();
+ xtype result = internal >> shift;
+ result ^= result >> ((2U*xtypebits+2U)/3U);
+ return result;
+ }
+
+ static itype unoutput(itype internal)
+ {
+ constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
+ constexpr bitcount_t opbits = bits >= 128 ? 6
+ : bits >= 64 ? 5
+ : bits >= 32 ? 4
+ : bits >= 16 ? 3
+ : 2;
+ constexpr bitcount_t mask = (1 << opbits) - 1;
+
+ internal = unxorshift(internal, bits, (2U*bits+2U)/3U);
+
+ internal *= mcg_unmultiplier<itype>::unmultiplier();
+
+ bitcount_t rshift = opbits ? (internal >> (bits - opbits)) & mask : 0;
+ internal = unxorshift(internal, bits, opbits + rshift);
+
+ return internal;
+ }
+};
+
+
+/*
+ * RXS M -- random xorshift, mcg multiply
+ */
+
+template <typename xtype, typename itype>
+struct rxs_m_mixin {
+ static xtype output(itype internal)
+ {
+ constexpr bitcount_t xtypebits = bitcount_t(sizeof(xtype) * 8);
+ constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
+ constexpr bitcount_t opbits = xtypebits >= 128 ? 6
+ : xtypebits >= 64 ? 5
+ : xtypebits >= 32 ? 4
+ : xtypebits >= 16 ? 3
+ : 2;
+ constexpr bitcount_t shift = bits - xtypebits;
+ constexpr bitcount_t mask = (1 << opbits) - 1;
+ bitcount_t rshift = opbits ? (internal >> (bits - opbits)) & mask : 0;
+ internal ^= internal >> (opbits + rshift);
+ internal *= mcg_multiplier<itype>::multiplier();
+ xtype result = internal >> shift;
+ return result;
+ }
+};
+
+/*
+ * XSL RR -- fixed xorshift (to low bits), random rotate
+ *
+ * Useful for 128-bit types that are split across two CPU registers.
+ */
+
+template <typename xtype, typename itype>
+struct xsl_rr_mixin {
+ static xtype output(itype internal)
+ {
+ constexpr bitcount_t xtypebits = bitcount_t(sizeof(xtype) * 8);
+ constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
+ constexpr bitcount_t sparebits = bits - xtypebits;
+ constexpr bitcount_t wantedopbits = xtypebits >= 128 ? 7
+ : xtypebits >= 64 ? 6
+ : xtypebits >= 32 ? 5
+ : xtypebits >= 16 ? 4
+ : 3;
+ constexpr bitcount_t opbits = sparebits >= wantedopbits ? wantedopbits
+ : sparebits;
+ constexpr bitcount_t amplifier = wantedopbits - opbits;
+ constexpr bitcount_t mask = (1 << opbits) - 1;
+ constexpr bitcount_t topspare = sparebits;
+ constexpr bitcount_t bottomspare = sparebits - topspare;
+ constexpr bitcount_t xshift = (topspare + xtypebits) / 2;
+
+ bitcount_t rot =
+ opbits ? bitcount_t(internal >> (bits - opbits)) & mask : 0;
+ bitcount_t amprot = (rot << amplifier) & mask;
+ internal ^= internal >> xshift;
+ xtype result = xtype(internal >> bottomspare);
+ result = rotr(result, amprot);
+ return result;
+ }
+};
+
+
+/*
+ * XSL RR RR -- fixed xorshift (to low bits), random rotate (both parts)
+ *
+ * Useful for 128-bit types that are split across two CPU registers.
+ * If you really want an invertable 128-bit RNG, I guess this is the one.
+ */
+
+template <typename T> struct halfsize_trait {};
+template <> struct halfsize_trait<pcg128_t> { typedef uint64_t type; };
+template <> struct halfsize_trait<uint64_t> { typedef uint32_t type; };
+template <> struct halfsize_trait<uint32_t> { typedef uint16_t type; };
+template <> struct halfsize_trait<uint16_t> { typedef uint8_t type; };
+
+template <typename xtype, typename itype>
+struct xsl_rr_rr_mixin {
+ typedef typename halfsize_trait<itype>::type htype;
+
+ static itype output(itype internal)
+ {
+ constexpr bitcount_t htypebits = bitcount_t(sizeof(htype) * 8);
+ constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
+ constexpr bitcount_t sparebits = bits - htypebits;
+ constexpr bitcount_t wantedopbits = htypebits >= 128 ? 7
+ : htypebits >= 64 ? 6
+ : htypebits >= 32 ? 5
+ : htypebits >= 16 ? 4
+ : 3;
+ constexpr bitcount_t opbits = sparebits >= wantedopbits ? wantedopbits
+ : sparebits;
+ constexpr bitcount_t amplifier = wantedopbits - opbits;
+ constexpr bitcount_t mask = (1 << opbits) - 1;
+ constexpr bitcount_t topspare = sparebits;
+ constexpr bitcount_t xshift = (topspare + htypebits) / 2;
+
+ bitcount_t rot =
+ opbits ? bitcount_t(internal >> (bits - opbits)) & mask : 0;
+ bitcount_t amprot = (rot << amplifier) & mask;
+ internal ^= internal >> xshift;
+ htype lowbits = htype(internal);
+ lowbits = rotr(lowbits, amprot);
+ htype highbits = htype(internal >> topspare);
+ bitcount_t rot2 = lowbits & mask;
+ bitcount_t amprot2 = (rot2 << amplifier) & mask;
+ highbits = rotr(highbits, amprot2);
+ return (itype(highbits) << topspare) ^ itype(lowbits);
+ }
+};
+
+
+/*
+ * XSH -- fixed xorshift (to high bits)
+ *
+ * You shouldn't use this at 64-bits or less.
+ */
+
+template <typename xtype, typename itype>
+struct xsh_mixin {
+ static xtype output(itype internal)
+ {
+ constexpr bitcount_t xtypebits = bitcount_t(sizeof(xtype) * 8);
+ constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
+ constexpr bitcount_t sparebits = bits - xtypebits;
+ constexpr bitcount_t topspare = 0;
+ constexpr bitcount_t bottomspare = sparebits - topspare;
+ constexpr bitcount_t xshift = (topspare + xtypebits) / 2;
+
+ internal ^= internal >> xshift;
+ xtype result = internal >> bottomspare;
+ return result;
+ }
+};
+
+/*
+ * XSL -- fixed xorshift (to low bits)
+ *
+ * You shouldn't use this at 64-bits or less.
+ */
+
+template <typename xtype, typename itype>
+struct xsl_mixin {
+ inline xtype output(itype internal)
+ {
+ constexpr bitcount_t xtypebits = bitcount_t(sizeof(xtype) * 8);
+ constexpr bitcount_t bits = bitcount_t(sizeof(itype) * 8);
+ constexpr bitcount_t sparebits = bits - xtypebits;
+ constexpr bitcount_t topspare = sparebits;
+ constexpr bitcount_t bottomspare = sparebits - topspare;
+ constexpr bitcount_t xshift = (topspare + xtypebits) / 2;
+
+ internal ^= internal >> xshift;
+ xtype result = internal >> bottomspare;
+ return result;
+ }
+};
+
+/* ---- End of Output Functions ---- */
+
+
+template <typename baseclass>
+struct inside_out : private baseclass {
+ inside_out() = delete;
+
+ typedef typename baseclass::result_type result_type;
+ typedef typename baseclass::state_type state_type;
+ static_assert(sizeof(result_type) == sizeof(state_type),
+ "Require a RNG whose output function is a permutation");
+
+ static bool external_step(result_type& randval, size_t i)
+ {
+ state_type state = baseclass::unoutput(randval);
+ state = state * baseclass::multiplier() + baseclass::increment()
+ + state_type(i*2);
+ result_type result = baseclass::output(state);
+ randval = result;
+ state_type zero =
+ baseclass::is_mcg ? state & state_type(3U) : state_type(0U);
+ return result == zero;
+ }
+
+ static bool external_advance(result_type& randval, size_t i,
+ result_type delta, bool forwards = true)
+ {
+ state_type state = baseclass::unoutput(randval);
+ state_type mult = baseclass::multiplier();
+ state_type inc = baseclass::increment() + state_type(i*2);
+ state_type zero =
+ baseclass::is_mcg ? state & state_type(3U) : state_type(0U);
+ state_type dist_to_zero = baseclass::distance(state, zero, mult, inc);
+ bool crosses_zero =
+ forwards ? dist_to_zero <= delta
+ : (-dist_to_zero) <= delta;
+ if (!forwards)
+ delta = -delta;
+ state = baseclass::advance(state, delta, mult, inc);
+ randval = baseclass::output(state);
+ return crosses_zero;
+ }
+};
+
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2, typename baseclass, typename extvalclass, bool kdd = true>
+class extended : public baseclass {
+public:
+ typedef typename baseclass::state_type state_type;
+ typedef typename baseclass::result_type result_type;
+ typedef inside_out<extvalclass> insideout;
+
+private:
+ static constexpr bitcount_t rtypebits = sizeof(result_type)*8;
+ static constexpr bitcount_t stypebits = sizeof(state_type)*8;
+
+ static constexpr bitcount_t tick_limit_pow2 = 64U;
+
+ static constexpr size_t table_size = 1UL << table_pow2;
+ static constexpr size_t table_shift = stypebits - table_pow2;
+ static constexpr state_type table_mask =
+ (state_type(1U) << table_pow2) - state_type(1U);
+
+ static constexpr bool may_tick =
+ (advance_pow2 < stypebits) && (advance_pow2 < tick_limit_pow2);
+ static constexpr size_t tick_shift = stypebits - advance_pow2;
+ static constexpr state_type tick_mask =
+ may_tick ? state_type(
+ (uint64_t(1) << (advance_pow2*may_tick)) - 1)
+ // ^-- stupidity to appease GCC warnings
+ : ~state_type(0U);
+
+ static constexpr bool may_tock = stypebits < tick_limit_pow2;
+
+ result_type data_[table_size];
+
+ PCG_NOINLINE void advance_table();
+
+ PCG_NOINLINE void advance_table(state_type delta, bool isForwards = true);
+
+ result_type& get_extended_value()
+ {
+ state_type state = this->state_;
+ if (kdd && baseclass::is_mcg) {
+ // The low order bits of an MCG are constant, so drop them.
+ state >>= 2;
+ }
+ size_t index = kdd ? state & table_mask
+ : state >> table_shift;
+
+ if (may_tick) {
+ bool tick = kdd ? (state & tick_mask) == state_type(0u)
+ : (state >> tick_shift) == state_type(0u);
+ if (tick)
+ advance_table();
+ }
+ if (may_tock) {
+ bool tock = state == state_type(0u);
+ if (tock)
+ advance_table();
+ }
+ return data_[index];
+ }
+
+public:
+ static constexpr size_t period_pow2()
+ {
+ return baseclass::period_pow2() + table_size*extvalclass::period_pow2();
+ }
+
+ __attribute__((always_inline)) result_type operator()()
+ {
+ result_type rhs = get_extended_value();
+ result_type lhs = this->baseclass::operator()();
+ return lhs ^ rhs;
+ }
+
+ result_type operator()(result_type upper_bound)
+ {
+ return bounded_rand(*this, upper_bound);
+ }
+
+ void set(result_type wanted)
+ {
+ result_type& rhs = get_extended_value();
+ result_type lhs = this->baseclass::operator()();
+ rhs = lhs ^ wanted;
+ }
+
+ void advance(state_type distance, bool forwards = true);
+
+ void backstep(state_type distance)
+ {
+ advance(distance, false);
+ }
+
+ extended(const result_type* data)
+ : baseclass()
+ {
+ datainit(data);
+ }
+
+ extended(const result_type* data, state_type seed)
+ : baseclass(seed)
+ {
+ datainit(data);
+ }
+
+ // This function may or may not exist. It thus has to be a template
+ // to use SFINAE; users don't have to worry about its template-ness.
+
+ template <typename bc = baseclass>
+ extended(const result_type* data, state_type seed,
+ typename bc::stream_state stream_seed)
+ : baseclass(seed, stream_seed)
+ {
+ datainit(data);
+ }
+
+ extended()
+ : baseclass()
+ {
+ selfinit();
+ }
+
+ extended(state_type seed)
+ : baseclass(seed)
+ {
+ selfinit();
+ }
+
+ // This function may or may not exist. It thus has to be a template
+ // to use SFINAE; users don't have to worry about its template-ness.
+
+ template <typename bc = baseclass>
+ extended(state_type seed, typename bc::stream_state stream_seed)
+ : baseclass(seed, stream_seed)
+ {
+ selfinit();
+ }
+
+private:
+ void selfinit();
+ void datainit(const result_type* data);
+
+public:
+
+ template<typename SeedSeq, typename = typename std::enable_if<
+ !std::is_convertible<SeedSeq, result_type>::value
+ && !std::is_convertible<SeedSeq, extended>::value>::type>
+ extended(SeedSeq&& seedSeq)
+ : baseclass(seedSeq)
+ {
+ generate_to<table_size>(seedSeq, data_);
+ }
+
+ template<typename... Args>
+ void seed(Args&&... args)
+ {
+ new (this) extended(std::forward<Args>(args)...);
+ }
+
+ template <bitcount_t table_pow2_, bitcount_t advance_pow2_,
+ typename baseclass_, typename extvalclass_, bool kdd_>
+ friend bool operator==(const extended<table_pow2_, advance_pow2_,
+ baseclass_, extvalclass_, kdd_>&,
+ const extended<table_pow2_, advance_pow2_,
+ baseclass_, extvalclass_, kdd_>&);
+
+ template <typename CharT, typename Traits,
+ bitcount_t table_pow2_, bitcount_t advance_pow2_,
+ typename baseclass_, typename extvalclass_, bool kdd_>
+ friend std::basic_ostream<CharT,Traits>&
+ operator<<(std::basic_ostream<CharT,Traits>& out,
+ const extended<table_pow2_, advance_pow2_,
+ baseclass_, extvalclass_, kdd_>&);
+
+ template <typename CharT, typename Traits,
+ bitcount_t table_pow2_, bitcount_t advance_pow2_,
+ typename baseclass_, typename extvalclass_, bool kdd_>
+ friend std::basic_istream<CharT,Traits>&
+ operator>>(std::basic_istream<CharT,Traits>& in,
+ extended<table_pow2_, advance_pow2_,
+ baseclass_, extvalclass_, kdd_>&);
+
+};
+
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2,
+ typename baseclass, typename extvalclass, bool kdd>
+void extended<table_pow2,advance_pow2,baseclass,extvalclass,kdd>::datainit(
+ const result_type* data)
+{
+ for (size_t i = 0; i < table_size; ++i)
+ data_[i] = data[i];
+}
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2,
+ typename baseclass, typename extvalclass, bool kdd>
+void extended<table_pow2,advance_pow2,baseclass,extvalclass,kdd>::selfinit()
+{
+ // We need to fill the extended table with something, and we have
+ // very little provided data, so we use the base generator to
+ // produce values. Although not ideal (use a seed sequence, folks!),
+ // unexpected correlations are mitigated by
+ // - using XOR differences rather than the number directly
+ // - the way the table is accessed, its values *won't* be accessed
+ // in the same order the were written.
+ // - any strange correlations would only be apparent if we
+ // were to backstep the generator so that the base generator
+ // was generating the same values again
+ result_type xdiff = baseclass::operator()() - baseclass::operator()();
+ for (size_t i = 0; i < table_size; ++i) {
+ data_[i] = baseclass::operator()() ^ xdiff;
+ }
+}
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2,
+ typename baseclass, typename extvalclass, bool kdd>
+bool operator==(const extended<table_pow2, advance_pow2,
+ baseclass, extvalclass, kdd>& lhs,
+ const extended<table_pow2, advance_pow2,
+ baseclass, extvalclass, kdd>& rhs)
+{
+ auto& base_lhs = static_cast<const baseclass&>(lhs);
+ auto& base_rhs = static_cast<const baseclass&>(rhs);
+ return base_lhs == base_rhs
+ && !memcmp((void*) lhs.data_, (void*) rhs.data_, sizeof(lhs.data_));
+}
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2,
+ typename baseclass, typename extvalclass, bool kdd>
+inline bool operator!=(const extended<table_pow2, advance_pow2,
+ baseclass, extvalclass, kdd>& lhs,
+ const extended<table_pow2, advance_pow2,
+ baseclass, extvalclass, kdd>& rhs)
+{
+ return lhs != rhs;
+}
+
+template <typename CharT, typename Traits,
+ bitcount_t table_pow2, bitcount_t advance_pow2,
+ typename baseclass, typename extvalclass, bool kdd>
+std::basic_ostream<CharT,Traits>&
+operator<<(std::basic_ostream<CharT,Traits>& out,
+ const extended<table_pow2, advance_pow2,
+ baseclass, extvalclass, kdd>& rng)
+{
+ auto orig_flags = out.flags(std::ios_base::dec | std::ios_base::left);
+ auto space = out.widen(' ');
+ auto orig_fill = out.fill();
+
+ out << rng.multiplier() << space
+ << rng.increment() << space
+ << rng.state_;
+
+ for (const auto& datum : rng.data_)
+ out << space << datum;
+
+ out.flags(orig_flags);
+ out.fill(orig_fill);
+ return out;
+}
+
+template <typename CharT, typename Traits,
+ bitcount_t table_pow2, bitcount_t advance_pow2,
+ typename baseclass, typename extvalclass, bool kdd>
+std::basic_istream<CharT,Traits>&
+operator>>(std::basic_istream<CharT,Traits>& in,
+ extended<table_pow2, advance_pow2,
+ baseclass, extvalclass, kdd>& rng)
+{
+ extended<table_pow2, advance_pow2, baseclass, extvalclass> new_rng;
+ auto& base_rng = static_cast<baseclass&>(new_rng);
+ in >> base_rng;
+
+ if (in.fail())
+ return in;
+
+ auto orig_flags = in.flags(std::ios_base::dec | std::ios_base::skipws);
+
+ for (auto& datum : new_rng.data_) {
+ in >> datum;
+ if (in.fail())
+ goto bail;
+ }
+
+ rng = new_rng;
+
+bail:
+ in.flags(orig_flags);
+ return in;
+}
+
+
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2,
+ typename baseclass, typename extvalclass, bool kdd>
+void
+extended<table_pow2,advance_pow2,baseclass,extvalclass,kdd>::advance_table()
+{
+ bool carry = false;
+ for (size_t i = 0; i < table_size; ++i) {
+ if (carry) {
+ carry = insideout::external_step(data_[i],i+1);
+ }
+ bool carry2 = insideout::external_step(data_[i],i+1);
+ carry = carry || carry2;
+ }
+}
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2,
+ typename baseclass, typename extvalclass, bool kdd>
+void
+extended<table_pow2,advance_pow2,baseclass,extvalclass,kdd>::advance_table(
+ state_type delta, bool isForwards)
+{
+ typedef typename baseclass::state_type base_state_t;
+ typedef typename extvalclass::state_type ext_state_t;
+ constexpr bitcount_t basebits = sizeof(base_state_t)*8;
+ constexpr bitcount_t extbits = sizeof(ext_state_t)*8;
+ static_assert(basebits <= extbits || advance_pow2 > 0,
+ "Current implementation might overflow its carry");
+
+ base_state_t carry = 0;
+ for (size_t i = 0; i < table_size; ++i) {
+ base_state_t total_delta = carry + delta;
+ ext_state_t trunc_delta = ext_state_t(total_delta);
+ if (basebits > extbits) {
+ carry = total_delta >> extbits;
+ } else {
+ carry = 0;
+ }
+ carry +=
+ insideout::external_advance(data_[i],i+1, trunc_delta, isForwards);
+ }
+}
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2,
+ typename baseclass, typename extvalclass, bool kdd>
+void extended<table_pow2,advance_pow2,baseclass,extvalclass,kdd>::advance(
+ state_type distance, bool forwards)
+{
+ static_assert(kdd,
+ "Efficient advance is too hard for non-kdd extension. "
+ "For a weak advance, cast to base class");
+ state_type zero =
+ baseclass::is_mcg ? this->state_ & state_type(3U) : state_type(0U);
+ if (may_tick) {
+ state_type ticks = distance >> (advance_pow2*may_tick);
+ // ^-- stupidity to appease GCC
+ // warnings
+ state_type adv_mask =
+ baseclass::is_mcg ? tick_mask << 2 : tick_mask;
+ state_type next_advance_distance = this->distance(zero, adv_mask);
+ if (!forwards)
+ next_advance_distance = (-next_advance_distance) & tick_mask;
+ if (next_advance_distance < (distance & tick_mask)) {
+ ++ticks;
+ }
+ if (ticks)
+ advance_table(ticks, forwards);
+ }
+ if (forwards) {
+ if (may_tock && this->distance(zero) <= distance)
+ advance_table();
+ baseclass::advance(distance);
+ } else {
+ if (may_tock && -(this->distance(zero)) <= distance)
+ advance_table(state_type(1U), false);
+ baseclass::advance(-distance);
+ }
+}
+
+} // namespace pcg_detail
+
+namespace pcg_engines {
+
+using namespace pcg_detail;
+
+/* Predefined types for XSH RS */
+
+typedef oneseq_base<uint8_t, uint16_t, xsh_rs_mixin> oneseq_xsh_rs_16_8;
+typedef oneseq_base<uint16_t, uint32_t, xsh_rs_mixin> oneseq_xsh_rs_32_16;
+typedef oneseq_base<uint32_t, uint64_t, xsh_rs_mixin> oneseq_xsh_rs_64_32;
+typedef oneseq_base<uint64_t, pcg128_t, xsh_rs_mixin> oneseq_xsh_rs_128_64;
+
+typedef unique_base<uint8_t, uint16_t, xsh_rs_mixin> unique_xsh_rs_16_8;
+typedef unique_base<uint16_t, uint32_t, xsh_rs_mixin> unique_xsh_rs_32_16;
+typedef unique_base<uint32_t, uint64_t, xsh_rs_mixin> unique_xsh_rs_64_32;
+typedef unique_base<uint64_t, pcg128_t, xsh_rs_mixin> unique_xsh_rs_128_64;
+
+typedef setseq_base<uint8_t, uint16_t, xsh_rs_mixin> setseq_xsh_rs_16_8;
+typedef setseq_base<uint16_t, uint32_t, xsh_rs_mixin> setseq_xsh_rs_32_16;
+typedef setseq_base<uint32_t, uint64_t, xsh_rs_mixin> setseq_xsh_rs_64_32;
+typedef setseq_base<uint64_t, pcg128_t, xsh_rs_mixin> setseq_xsh_rs_128_64;
+
+typedef mcg_base<uint8_t, uint16_t, xsh_rs_mixin> mcg_xsh_rs_16_8;
+typedef mcg_base<uint16_t, uint32_t, xsh_rs_mixin> mcg_xsh_rs_32_16;
+typedef mcg_base<uint32_t, uint64_t, xsh_rs_mixin> mcg_xsh_rs_64_32;
+typedef mcg_base<uint64_t, pcg128_t, xsh_rs_mixin> mcg_xsh_rs_128_64;
+
+/* Predefined types for XSH RR */
+
+typedef oneseq_base<uint8_t, uint16_t, xsh_rr_mixin> oneseq_xsh_rr_16_8;
+typedef oneseq_base<uint16_t, uint32_t, xsh_rr_mixin> oneseq_xsh_rr_32_16;
+typedef oneseq_base<uint32_t, uint64_t, xsh_rr_mixin> oneseq_xsh_rr_64_32;
+typedef oneseq_base<uint64_t, pcg128_t, xsh_rr_mixin> oneseq_xsh_rr_128_64;
+
+typedef unique_base<uint8_t, uint16_t, xsh_rr_mixin> unique_xsh_rr_16_8;
+typedef unique_base<uint16_t, uint32_t, xsh_rr_mixin> unique_xsh_rr_32_16;
+typedef unique_base<uint32_t, uint64_t, xsh_rr_mixin> unique_xsh_rr_64_32;
+typedef unique_base<uint64_t, pcg128_t, xsh_rr_mixin> unique_xsh_rr_128_64;
+
+typedef setseq_base<uint8_t, uint16_t, xsh_rr_mixin> setseq_xsh_rr_16_8;
+typedef setseq_base<uint16_t, uint32_t, xsh_rr_mixin> setseq_xsh_rr_32_16;
+typedef setseq_base<uint32_t, uint64_t, xsh_rr_mixin> setseq_xsh_rr_64_32;
+typedef setseq_base<uint64_t, pcg128_t, xsh_rr_mixin> setseq_xsh_rr_128_64;
+
+typedef mcg_base<uint8_t, uint16_t, xsh_rr_mixin> mcg_xsh_rr_16_8;
+typedef mcg_base<uint16_t, uint32_t, xsh_rr_mixin> mcg_xsh_rr_32_16;
+typedef mcg_base<uint32_t, uint64_t, xsh_rr_mixin> mcg_xsh_rr_64_32;
+typedef mcg_base<uint64_t, pcg128_t, xsh_rr_mixin> mcg_xsh_rr_128_64;
+
+
+/* Predefined types for RXS M XS */
+
+typedef oneseq_base<uint8_t, uint8_t, rxs_m_xs_mixin> oneseq_rxs_m_xs_8_8;
+typedef oneseq_base<uint16_t, uint16_t, rxs_m_xs_mixin> oneseq_rxs_m_xs_16_16;
+typedef oneseq_base<uint32_t, uint32_t, rxs_m_xs_mixin> oneseq_rxs_m_xs_32_32;
+typedef oneseq_base<uint64_t, uint64_t, rxs_m_xs_mixin> oneseq_rxs_m_xs_64_64;
+typedef oneseq_base<pcg128_t, pcg128_t, rxs_m_xs_mixin> oneseq_rxs_m_xs_128_128;
+
+typedef unique_base<uint8_t, uint8_t, rxs_m_xs_mixin> unique_rxs_m_xs_8_8;
+typedef unique_base<uint16_t, uint16_t, rxs_m_xs_mixin> unique_rxs_m_xs_16_16;
+typedef unique_base<uint32_t, uint32_t, rxs_m_xs_mixin> unique_rxs_m_xs_32_32;
+typedef unique_base<uint64_t, uint64_t, rxs_m_xs_mixin> unique_rxs_m_xs_64_64;
+typedef unique_base<pcg128_t, pcg128_t, rxs_m_xs_mixin> unique_rxs_m_xs_128_128;
+
+typedef setseq_base<uint8_t, uint8_t, rxs_m_xs_mixin> setseq_rxs_m_xs_8_8;
+typedef setseq_base<uint16_t, uint16_t, rxs_m_xs_mixin> setseq_rxs_m_xs_16_16;
+typedef setseq_base<uint32_t, uint32_t, rxs_m_xs_mixin> setseq_rxs_m_xs_32_32;
+typedef setseq_base<uint64_t, uint64_t, rxs_m_xs_mixin> setseq_rxs_m_xs_64_64;
+typedef setseq_base<pcg128_t, pcg128_t, rxs_m_xs_mixin> setseq_rxs_m_xs_128_128;
+
+ // MCG versions don't make sense here, so aren't defined.
+
+/* Predefined types for XSL RR (only defined for "large" types) */
+
+typedef oneseq_base<uint32_t, uint64_t, xsl_rr_mixin> oneseq_xsl_rr_64_32;
+typedef oneseq_base<uint64_t, pcg128_t, xsl_rr_mixin> oneseq_xsl_rr_128_64;
+
+typedef unique_base<uint32_t, uint64_t, xsl_rr_mixin> unique_xsl_rr_64_32;
+typedef unique_base<uint64_t, pcg128_t, xsl_rr_mixin> unique_xsl_rr_128_64;
+
+typedef setseq_base<uint32_t, uint64_t, xsl_rr_mixin> setseq_xsl_rr_64_32;
+typedef setseq_base<uint64_t, pcg128_t, xsl_rr_mixin> setseq_xsl_rr_128_64;
+
+typedef mcg_base<uint32_t, uint64_t, xsl_rr_mixin> mcg_xsl_rr_64_32;
+typedef mcg_base<uint64_t, pcg128_t, xsl_rr_mixin> mcg_xsl_rr_128_64;
+
+
+/* Predefined types for XSL RR RR (only defined for "large" types) */
+
+typedef oneseq_base<uint64_t, uint64_t, xsl_rr_rr_mixin>
+ oneseq_xsl_rr_rr_64_64;
+typedef oneseq_base<pcg128_t, pcg128_t, xsl_rr_rr_mixin>
+ oneseq_xsl_rr_rr_128_128;
+
+typedef unique_base<uint64_t, uint64_t, xsl_rr_rr_mixin>
+ unique_xsl_rr_rr_64_64;
+typedef unique_base<pcg128_t, pcg128_t, xsl_rr_rr_mixin>
+ unique_xsl_rr_rr_128_128;
+
+typedef setseq_base<uint64_t, uint64_t, xsl_rr_rr_mixin>
+ setseq_xsl_rr_rr_64_64;
+typedef setseq_base<pcg128_t, pcg128_t, xsl_rr_rr_mixin>
+ setseq_xsl_rr_rr_128_128;
+
+ // MCG versions don't make sense here, so aren't defined.
+
+/* Extended generators */
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2,
+ typename BaseRNG, bool kdd = true>
+using ext_std8 = extended<table_pow2, advance_pow2, BaseRNG,
+ oneseq_rxs_m_xs_8_8, kdd>;
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2,
+ typename BaseRNG, bool kdd = true>
+using ext_std16 = extended<table_pow2, advance_pow2, BaseRNG,
+ oneseq_rxs_m_xs_16_16, kdd>;
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2,
+ typename BaseRNG, bool kdd = true>
+using ext_std32 = extended<table_pow2, advance_pow2, BaseRNG,
+ oneseq_rxs_m_xs_32_32, kdd>;
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2,
+ typename BaseRNG, bool kdd = true>
+using ext_std64 = extended<table_pow2, advance_pow2, BaseRNG,
+ oneseq_rxs_m_xs_64_64, kdd>;
+
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2, bool kdd = true>
+using ext_oneseq_rxs_m_xs_32_32 =
+ ext_std32<table_pow2, advance_pow2, oneseq_rxs_m_xs_32_32, kdd>;
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2, bool kdd = true>
+using ext_mcg_xsh_rs_64_32 =
+ ext_std32<table_pow2, advance_pow2, mcg_xsh_rs_64_32, kdd>;
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2, bool kdd = true>
+using ext_oneseq_xsh_rs_64_32 =
+ ext_std32<table_pow2, advance_pow2, oneseq_xsh_rs_64_32, kdd>;
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2, bool kdd = true>
+using ext_setseq_xsh_rr_64_32 =
+ ext_std32<table_pow2, advance_pow2, setseq_xsh_rr_64_32, kdd>;
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2, bool kdd = true>
+using ext_mcg_xsl_rr_128_64 =
+ ext_std64<table_pow2, advance_pow2, mcg_xsl_rr_128_64, kdd>;
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2, bool kdd = true>
+using ext_oneseq_xsl_rr_128_64 =
+ ext_std64<table_pow2, advance_pow2, oneseq_xsl_rr_128_64, kdd>;
+
+template <bitcount_t table_pow2, bitcount_t advance_pow2, bool kdd = true>
+using ext_setseq_xsl_rr_128_64 =
+ ext_std64<table_pow2, advance_pow2, setseq_xsl_rr_128_64, kdd>;
+
+} // namespace pcg_engines
+
+typedef pcg_engines::setseq_xsh_rr_64_32 pcg32;
+typedef pcg_engines::oneseq_xsh_rr_64_32 pcg32_oneseq;
+typedef pcg_engines::unique_xsh_rr_64_32 pcg32_unique;
+typedef pcg_engines::mcg_xsh_rs_64_32 pcg32_fast;
+
+typedef pcg_engines::setseq_xsl_rr_128_64 pcg64;
+typedef pcg_engines::oneseq_xsl_rr_128_64 pcg64_oneseq;
+typedef pcg_engines::unique_xsl_rr_128_64 pcg64_unique;
+typedef pcg_engines::mcg_xsl_rr_128_64 pcg64_fast;
+
+typedef pcg_engines::setseq_rxs_m_xs_8_8 pcg8_once_insecure;
+typedef pcg_engines::setseq_rxs_m_xs_16_16 pcg16_once_insecure;
+typedef pcg_engines::setseq_rxs_m_xs_32_32 pcg32_once_insecure;
+typedef pcg_engines::setseq_rxs_m_xs_64_64 pcg64_once_insecure;
+typedef pcg_engines::setseq_xsl_rr_rr_128_128 pcg128_once_insecure;
+
+typedef pcg_engines::oneseq_rxs_m_xs_8_8 pcg8_oneseq_once_insecure;
+typedef pcg_engines::oneseq_rxs_m_xs_16_16 pcg16_oneseq_once_insecure;
+typedef pcg_engines::oneseq_rxs_m_xs_32_32 pcg32_oneseq_once_insecure;
+typedef pcg_engines::oneseq_rxs_m_xs_64_64 pcg64_oneseq_once_insecure;
+typedef pcg_engines::oneseq_xsl_rr_rr_128_128 pcg128_oneseq_once_insecure;
+
+
+// These two extended RNGs provide two-dimensionally equidistributed
+// 32-bit generators. pcg32_k2_fast occupies the same space as pcg64,
+// and can be called twice to generate 64 bits, but does not required
+// 128-bit math; on 32-bit systems, it's faster than pcg64 as well.
+
+typedef pcg_engines::ext_setseq_xsh_rr_64_32<6,16,true> pcg32_k2;
+typedef pcg_engines::ext_oneseq_xsh_rs_64_32<6,32,true> pcg32_k2_fast;
+
+// These eight extended RNGs have about as much state as arc4random
+//
+// - the k variants are k-dimensionally equidistributed
+// - the c variants offer better crypographic security
+//
+// (just how good the cryptographic security is is an open question)
+
+typedef pcg_engines::ext_setseq_xsh_rr_64_32<6,16,true> pcg32_k64;
+typedef pcg_engines::ext_mcg_xsh_rs_64_32<6,32,true> pcg32_k64_oneseq;
+typedef pcg_engines::ext_oneseq_xsh_rs_64_32<6,32,true> pcg32_k64_fast;
+
+typedef pcg_engines::ext_setseq_xsh_rr_64_32<6,16,false> pcg32_c64;
+typedef pcg_engines::ext_oneseq_xsh_rs_64_32<6,32,false> pcg32_c64_oneseq;
+typedef pcg_engines::ext_mcg_xsh_rs_64_32<6,32,false> pcg32_c64_fast;
+
+typedef pcg_engines::ext_setseq_xsl_rr_128_64<5,16,true> pcg64_k32;
+typedef pcg_engines::ext_oneseq_xsl_rr_128_64<5,128,true> pcg64_k32_oneseq;
+typedef pcg_engines::ext_mcg_xsl_rr_128_64<5,128,true> pcg64_k32_fast;
+
+typedef pcg_engines::ext_setseq_xsl_rr_128_64<5,16,false> pcg64_c32;
+typedef pcg_engines::ext_oneseq_xsl_rr_128_64<5,128,false> pcg64_c32_oneseq;
+typedef pcg_engines::ext_mcg_xsl_rr_128_64<5,128,false> pcg64_c32_fast;
+
+// These eight extended RNGs have more state than the Mersenne twister
+//
+// - the k variants are k-dimensionally equidistributed
+// - the c variants offer better crypographic security
+//
+// (just how good the cryptographic security is is an open question)
+
+typedef pcg_engines::ext_setseq_xsh_rr_64_32<10,16,true> pcg32_k1024;
+typedef pcg_engines::ext_oneseq_xsh_rs_64_32<10,32,true> pcg32_k1024_fast;
+
+typedef pcg_engines::ext_setseq_xsh_rr_64_32<10,16,false> pcg32_c1024;
+typedef pcg_engines::ext_oneseq_xsh_rs_64_32<10,32,false> pcg32_c1024_fast;
+
+typedef pcg_engines::ext_setseq_xsl_rr_128_64<10,16,true> pcg64_k1024;
+typedef pcg_engines::ext_oneseq_xsl_rr_128_64<10,128,true> pcg64_k1024_fast;
+
+typedef pcg_engines::ext_setseq_xsl_rr_128_64<10,16,false> pcg64_c1024;
+typedef pcg_engines::ext_oneseq_xsl_rr_128_64<10,128,false> pcg64_c1024_fast;
+
+// These generators have an insanely huge period (2^524352), and is suitable
+// for silly party tricks, such as dumping out 64 KB ZIP files at an arbitrary
+// point in the future. [Actually, over the full period of the generator, it
+// will produce every 64 KB ZIP file 2^64 times!]
+
+typedef pcg_engines::ext_setseq_xsh_rr_64_32<14,16,true> pcg32_k16384;
+typedef pcg_engines::ext_oneseq_xsh_rs_64_32<14,32,true> pcg32_k16384_fast;
+
+#endif // PCG_RAND_HPP_INCLUDED
http://git-wip-us.apache.org/repos/asf/impala/blob/4feb4f3a/be/src/thirdparty/pcg-cpp-0.98/include/pcg_uint128.hpp
----------------------------------------------------------------------
diff --git a/be/src/thirdparty/pcg-cpp-0.98/include/pcg_uint128.hpp b/be/src/thirdparty/pcg-cpp-0.98/include/pcg_uint128.hpp
new file mode 100644
index 0000000..99b20e7
--- /dev/null
+++ b/be/src/thirdparty/pcg-cpp-0.98/include/pcg_uint128.hpp
@@ -0,0 +1,750 @@
+/*
+ * PCG Random Number Generation for C++
+ *
+ * Copyright 2014 Melissa O'Neill <on...@pcg-random.org>
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ * For additional information about the PCG random number generation scheme,
+ * including its license and other licensing options, visit
+ *
+ * http://www.pcg-random.org
+ */
+
+/*
+ * This code provides a a C++ class that can provide 128-bit (or higher)
+ * integers. To produce 2K-bit integers, it uses two K-bit integers,
+ * placed in a union that allowes the code to also see them as four K/2 bit
+ * integers (and access them either directly name, or by index).
+ *
+ * It may seem like we're reinventing the wheel here, because several
+ * libraries already exist that support large integers, but most existing
+ * libraries provide a very generic multiprecision code, but here we're
+ * operating at a fixed size. Also, most other libraries are fairly
+ * heavyweight. So we use a direct implementation. Sadly, it's much slower
+ * than hand-coded assembly or direct CPU support.
+ */
+
+#ifndef PCG_UINT128_HPP_INCLUDED
+#define PCG_UINT128_HPP_INCLUDED 1
+
+#include <cstdint>
+#include <cstdio>
+#include <cassert>
+#include <climits>
+#include <utility>
+#include <initializer_list>
+#include <type_traits>
+
+/*
+ * We want to lay the type out the same way that a native type would be laid
+ * out, which means we must know the machine's endian, at compile time.
+ * This ugliness attempts to do so.
+ */
+
+#ifndef PCG_LITTLE_ENDIAN
+ #if defined(__BYTE_ORDER__)
+ #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+ #define PCG_LITTLE_ENDIAN 1
+ #elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
+ #define PCG_LITTLE_ENDIAN 0
+ #else
+ #error __BYTE_ORDER__ does not match a standard endian, pick a side
+ #endif
+ #elif __LITTLE_ENDIAN__ || _LITTLE_ENDIAN
+ #define PCG_LITTLE_ENDIAN 1
+ #elif __BIG_ENDIAN__ || _BIG_ENDIAN
+ #define PCG_LITTLE_ENDIAN 0
+ #elif __x86_64 || __x86_64__ || __i386 || __i386__
+ #define PCG_LITTLE_ENDIAN 1
+ #elif __powerpc__ || __POWERPC__ || __ppc__ || __PPC__ \
+ || __m68k__ || __mc68000__
+ #define PCG_LITTLE_ENDIAN 0
+ #else
+ #error Unable to determine target endianness
+ #endif
+#endif
+
+namespace pcg_extras {
+
+// Recent versions of GCC have intrinsics we can use to quickly calculate
+// the number of leading and trailing zeros in a number. If possible, we
+// use them, otherwise we fall back to old-fashioned bit twiddling to figure
+// them out.
+
+#ifndef PCG_BITCOUNT_T
+ typedef uint8_t bitcount_t;
+#else
+ typedef PCG_BITCOUNT_T bitcount_t;
+#endif
+
+/*
+ * Provide some useful helper functions
+ * * flog2 floor(log2(x))
+ * * trailingzeros number of trailing zero bits
+ */
+
+#ifdef __GNUC__ // Any GNU-compatible compiler supporting C++11 has
+ // some useful intrinsics we can use.
+
+inline bitcount_t flog2(uint32_t v)
+{
+ return 31 - __builtin_clz(v);
+}
+
+inline bitcount_t trailingzeros(uint32_t v)
+{
+ return __builtin_ctz(v);
+}
+
+inline bitcount_t flog2(uint64_t v)
+{
+#if UINT64_MAX == ULONG_MAX
+ return 63 - __builtin_clzl(v);
+#elif UINT64_MAX == ULLONG_MAX
+ return 63 - __builtin_clzll(v);
+#else
+ #error Cannot find a function for uint64_t
+#endif
+}
+
+inline bitcount_t trailingzeros(uint64_t v)
+{
+#if UINT64_MAX == ULONG_MAX
+ return __builtin_ctzl(v);
+#elif UINT64_MAX == ULLONG_MAX
+ return __builtin_ctzll(v);
+#else
+ #error Cannot find a function for uint64_t
+#endif
+}
+
+#else // Otherwise, we fall back to bit twiddling
+ // implementations
+
+inline bitcount_t flog2(uint32_t v)
+{
+ // Based on code by Eric Cole and Mark Dickinson, which appears at
+ // https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn
+
+ static const uint8_t multiplyDeBruijnBitPos[32] = {
+ 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
+ 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
+ };
+
+ v |= v >> 1; // first round down to one less than a power of 2
+ v |= v >> 2;
+ v |= v >> 4;
+ v |= v >> 8;
+ v |= v >> 16;
+
+ return multiplyDeBruijnBitPos[(uint32_t)(v * 0x07C4ACDDU) >> 27];
+}
+
+inline bitcount_t trailingzeros(uint32_t v)
+{
+ static const uint8_t multiplyDeBruijnBitPos[32] = {
+ 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
+ 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
+ };
+
+ return multiplyDeBruijnBitPos[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
+}
+
+inline bitcount_t flog2(uint64_t v)
+{
+ uint32_t high = v >> 32;
+ uint32_t low = uint32_t(v);
+
+ return high ? 32+flog2(high) : flog2(low);
+}
+
+inline bitcount_t trailingzeros(uint64_t v)
+{
+ uint32_t high = v >> 32;
+ uint32_t low = uint32_t(v);
+
+ return low ? trailingzeros(low) : trailingzeros(high)+32;
+}
+
+#endif
+
+template <typename UInt>
+inline bitcount_t clog2(UInt v)
+{
+ return flog2(v) + ((v & (-v)) != v);
+}
+
+template <typename UInt>
+inline UInt addwithcarry(UInt x, UInt y, bool carryin, bool* carryout)
+{
+ UInt half_result = y + carryin;
+ UInt result = x + half_result;
+ *carryout = (half_result < y) || (result < x);
+ return result;
+}
+
+template <typename UInt>
+inline UInt subwithcarry(UInt x, UInt y, bool carryin, bool* carryout)
+{
+ UInt half_result = y + carryin;
+ UInt result = x - half_result;
+ *carryout = (half_result < y) || (result > x);
+ return result;
+}
+
+
+template <typename UInt, typename UIntX2>
+class uint_x4 {
+// private:
+public:
+ union {
+#if PCG_LITTLE_ENDIAN
+ struct {
+ UInt v0, v1, v2, v3;
+ } w;
+ struct {
+ UIntX2 v01, v23;
+ } d;
+#else
+ struct {
+ UInt v3, v2, v1, v0;
+ } w;
+ struct {
+ UIntX2 v23, v01;
+ } d;
+#endif
+ // For the array access versions, the code that uses the array
+ // must handle endian itself. Yuck.
+ UInt wa[4];
+ UIntX2 da[2];
+ };
+
+public:
+ uint_x4() = default;
+
+ constexpr uint_x4(UInt v3, UInt v2, UInt v1, UInt v0)
+#if PCG_LITTLE_ENDIAN
+ : w{v0, v1, v2, v3}
+#else
+ : w{v3, v2, v1, v0}
+#endif
+ {
+ // Nothing (else) to do
+ }
+
+ constexpr uint_x4(UIntX2 v23, UIntX2 v01)
+#if PCG_LITTLE_ENDIAN
+ : d{v01,v23}
+#else
+ : d{v23,v01}
+#endif
+ {
+ // Nothing (else) to do
+ }
+
+ template<class Integral,
+ typename std::enable_if<(std::is_integral<Integral>::value
+ && sizeof(Integral) <= sizeof(UIntX2))
+ >::type* = nullptr>
+ constexpr uint_x4(Integral v01)
+#if PCG_LITTLE_ENDIAN
+ : d{UIntX2(v01),0UL}
+#else
+ : d{0UL,UIntX2(v01)}
+#endif
+ {
+ // Nothing (else) to do
+ }
+
+ explicit constexpr operator uint64_t() const
+ {
+ return d.v01;
+ }
+
+ explicit constexpr operator uint32_t() const
+ {
+ return w.v0;
+ }
+
+ explicit constexpr operator int() const
+ {
+ return w.v0;
+ }
+
+ explicit constexpr operator uint16_t() const
+ {
+ return w.v0;
+ }
+
+ explicit constexpr operator uint8_t() const
+ {
+ return w.v0;
+ }
+
+ typedef typename std::conditional<std::is_same<uint64_t,
+ unsigned long>::value,
+ unsigned long long,
+ unsigned long>::type
+ uint_missing_t;
+
+ explicit constexpr operator uint_missing_t() const
+ {
+ return d.v01;
+ }
+
+ explicit constexpr operator bool() const
+ {
+ return d.v01 || d.v23;
+ }
+
+ template<typename U, typename V>
+ friend uint_x4<U,V> operator*(const uint_x4<U,V>&, const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend std::pair< uint_x4<U,V>,uint_x4<U,V> >
+ divmod(const uint_x4<U,V>&, const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend uint_x4<U,V> operator+(const uint_x4<U,V>&, const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend uint_x4<U,V> operator-(const uint_x4<U,V>&, const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend uint_x4<U,V> operator<<(const uint_x4<U,V>&, const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend uint_x4<U,V> operator>>(const uint_x4<U,V>&, const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend uint_x4<U,V> operator&(const uint_x4<U,V>&, const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend uint_x4<U,V> operator|(const uint_x4<U,V>&, const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend uint_x4<U,V> operator^(const uint_x4<U,V>&, const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend bool operator==(const uint_x4<U,V>&, const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend bool operator!=(const uint_x4<U,V>&, const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend bool operator<(const uint_x4<U,V>&, const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend bool operator<=(const uint_x4<U,V>&, const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend bool operator>(const uint_x4<U,V>&, const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend bool operator>=(const uint_x4<U,V>&, const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend uint_x4<U,V> operator~(const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend uint_x4<U,V> operator-(const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend bitcount_t flog2(const uint_x4<U,V>&);
+
+ template<typename U, typename V>
+ friend bitcount_t trailingzeros(const uint_x4<U,V>&);
+
+ uint_x4& operator*=(const uint_x4& rhs)
+ {
+ uint_x4 result = *this * rhs;
+ return *this = result;
+ }
+
+ uint_x4& operator/=(const uint_x4& rhs)
+ {
+ uint_x4 result = *this / rhs;
+ return *this = result;
+ }
+
+ uint_x4& operator%=(const uint_x4& rhs)
+ {
+ uint_x4 result = *this % rhs;
+ return *this = result;
+ }
+
+ uint_x4& operator+=(const uint_x4& rhs)
+ {
+ uint_x4 result = *this + rhs;
+ return *this = result;
+ }
+
+ uint_x4& operator-=(const uint_x4& rhs)
+ {
+ uint_x4 result = *this - rhs;
+ return *this = result;
+ }
+
+ uint_x4& operator&=(const uint_x4& rhs)
+ {
+ uint_x4 result = *this & rhs;
+ return *this = result;
+ }
+
+ uint_x4& operator|=(const uint_x4& rhs)
+ {
+ uint_x4 result = *this | rhs;
+ return *this = result;
+ }
+
+ uint_x4& operator^=(const uint_x4& rhs)
+ {
+ uint_x4 result = *this ^ rhs;
+ return *this = result;
+ }
+
+ uint_x4& operator>>=(bitcount_t shift)
+ {
+ uint_x4 result = *this >> shift;
+ return *this = result;
+ }
+
+ uint_x4& operator<<=(bitcount_t shift)
+ {
+ uint_x4 result = *this << shift;
+ return *this = result;
+ }
+
+};
+
+template<typename U, typename V>
+bitcount_t flog2(const uint_x4<U,V>& v)
+{
+#if PCG_LITTLE_ENDIAN
+ for (uint8_t i = 4; i !=0; /* dec in loop */) {
+ --i;
+#else
+ for (uint8_t i = 0; i < 4; ++i) {
+#endif
+ if (v.wa[i] == 0)
+ continue;
+ return flog2(v.wa[i]) + (sizeof(U)*CHAR_BIT)*i;
+ }
+ abort();
+}
+
+template<typename U, typename V>
+bitcount_t trailingzeros(const uint_x4<U,V>& v)
+{
+#if PCG_LITTLE_ENDIAN
+ for (uint8_t i = 0; i < 4; ++i) {
+#else
+ for (uint8_t i = 4; i !=0; /* dec in loop */) {
+ --i;
+#endif
+ if (v.wa[i] != 0)
+ return trailingzeros(v.wa[i]) + (sizeof(U)*CHAR_BIT)*i;
+ }
+ return (sizeof(U)*CHAR_BIT)*4;
+}
+
+template <typename UInt, typename UIntX2>
+std::pair< uint_x4<UInt,UIntX2>, uint_x4<UInt,UIntX2> >
+ divmod(const uint_x4<UInt,UIntX2>& orig_dividend,
+ const uint_x4<UInt,UIntX2>& divisor)
+{
+ // If the dividend is less than the divisor, the answer is always zero.
+ // This takes care of boundary cases like 0/x (which would otherwise be
+ // problematic because we can't take the log of zero. (The boundary case
+ // of division by zero is undefined.)
+ if (orig_dividend < divisor)
+ return { uint_x4<UInt,UIntX2>(0UL), orig_dividend };
+
+ auto dividend = orig_dividend;
+
+ auto log2_divisor = flog2(divisor);
+ auto log2_dividend = flog2(dividend);
+ // assert(log2_dividend >= log2_divisor);
+ bitcount_t logdiff = log2_dividend - log2_divisor;
+
+ constexpr uint_x4<UInt,UIntX2> ONE(1UL);
+ if (logdiff == 0)
+ return { ONE, dividend - divisor };
+
+ // Now we change the log difference to
+ // floor(log2(divisor)) - ceil(log2(dividend))
+ // to ensure that we *underestimate* the result.
+ logdiff -= 1;
+
+ uint_x4<UInt,UIntX2> quotient(0UL);
+
+ auto qfactor = ONE << logdiff;
+ auto factor = divisor << logdiff;
+
+ do {
+ dividend -= factor;
+ quotient += qfactor;
+ while (dividend < factor) {
+ factor >>= 1;
+ qfactor >>= 1;
+ }
+ } while (dividend >= divisor);
+
+ return { quotient, dividend };
+}
+
+template <typename UInt, typename UIntX2>
+uint_x4<UInt,UIntX2> operator/(const uint_x4<UInt,UIntX2>& dividend,
+ const uint_x4<UInt,UIntX2>& divisor)
+{
+ return divmod(dividend, divisor).first;
+}
+
+template <typename UInt, typename UIntX2>
+uint_x4<UInt,UIntX2> operator%(const uint_x4<UInt,UIntX2>& dividend,
+ const uint_x4<UInt,UIntX2>& divisor)
+{
+ return divmod(dividend, divisor).second;
+}
+
+
+template <typename UInt, typename UIntX2>
+uint_x4<UInt,UIntX2> operator*(const uint_x4<UInt,UIntX2>& a,
+ const uint_x4<UInt,UIntX2>& b)
+{
+ uint_x4<UInt,UIntX2> r = {0U, 0U, 0U, 0U};
+ bool carryin = false;
+ bool carryout;
+ UIntX2 a0b0 = UIntX2(a.w.v0) * UIntX2(b.w.v0);
+ r.w.v0 = UInt(a0b0);
+ r.w.v1 = UInt(a0b0 >> 32);
+
+ UIntX2 a1b0 = UIntX2(a.w.v1) * UIntX2(b.w.v0);
+ r.w.v2 = UInt(a1b0 >> 32);
+ r.w.v1 = addwithcarry(r.w.v1, UInt(a1b0), carryin, &carryout);
+ carryin = carryout;
+ r.w.v2 = addwithcarry(r.w.v2, UInt(0U), carryin, &carryout);
+ carryin = carryout;
+ r.w.v3 = addwithcarry(r.w.v3, UInt(0U), carryin, &carryout);
+
+ UIntX2 a0b1 = UIntX2(a.w.v0) * UIntX2(b.w.v1);
+ carryin = false;
+ r.w.v2 = addwithcarry(r.w.v2, UInt(a0b1 >> 32), carryin, &carryout);
+ carryin = carryout;
+ r.w.v3 = addwithcarry(r.w.v3, UInt(0U), carryin, &carryout);
+
+ carryin = false;
+ r.w.v1 = addwithcarry(r.w.v1, UInt(a0b1), carryin, &carryout);
+ carryin = carryout;
+ r.w.v2 = addwithcarry(r.w.v2, UInt(0U), carryin, &carryout);
+ carryin = carryout;
+ r.w.v3 = addwithcarry(r.w.v3, UInt(0U), carryin, &carryout);
+
+ UIntX2 a1b1 = UIntX2(a.w.v1) * UIntX2(b.w.v1);
+ carryin = false;
+ r.w.v2 = addwithcarry(r.w.v2, UInt(a1b1), carryin, &carryout);
+ carryin = carryout;
+ r.w.v3 = addwithcarry(r.w.v3, UInt(a1b1 >> 32), carryin, &carryout);
+
+ r.d.v23 += a.d.v01 * b.d.v23 + a.d.v23 * b.d.v01;
+
+ return r;
+}
+
+
+template <typename UInt, typename UIntX2>
+uint_x4<UInt,UIntX2> operator+(const uint_x4<UInt,UIntX2>& a,
+ const uint_x4<UInt,UIntX2>& b)
+{
+ uint_x4<UInt,UIntX2> r = {0U, 0U, 0U, 0U};
+
+ bool carryin = false;
+ bool carryout;
+ r.w.v0 = addwithcarry(a.w.v0, b.w.v0, carryin, &carryout);
+ carryin = carryout;
+ r.w.v1 = addwithcarry(a.w.v1, b.w.v1, carryin, &carryout);
+ carryin = carryout;
+ r.w.v2 = addwithcarry(a.w.v2, b.w.v2, carryin, &carryout);
+ carryin = carryout;
+ r.w.v3 = addwithcarry(a.w.v3, b.w.v3, carryin, &carryout);
+
+ return r;
+}
+
+template <typename UInt, typename UIntX2>
+uint_x4<UInt,UIntX2> operator-(const uint_x4<UInt,UIntX2>& a,
+ const uint_x4<UInt,UIntX2>& b)
+{
+ uint_x4<UInt,UIntX2> r = {0U, 0U, 0U, 0U};
+
+ bool carryin = false;
+ bool carryout;
+ r.w.v0 = subwithcarry(a.w.v0, b.w.v0, carryin, &carryout);
+ carryin = carryout;
+ r.w.v1 = subwithcarry(a.w.v1, b.w.v1, carryin, &carryout);
+ carryin = carryout;
+ r.w.v2 = subwithcarry(a.w.v2, b.w.v2, carryin, &carryout);
+ carryin = carryout;
+ r.w.v3 = subwithcarry(a.w.v3, b.w.v3, carryin, &carryout);
+
+ return r;
+}
+
+
+template <typename UInt, typename UIntX2>
+uint_x4<UInt,UIntX2> operator&(const uint_x4<UInt,UIntX2>& a,
+ const uint_x4<UInt,UIntX2>& b)
+{
+ return uint_x4<UInt,UIntX2>(a.d.v23 & b.d.v23, a.d.v01 & b.d.v01);
+}
+
+template <typename UInt, typename UIntX2>
+uint_x4<UInt,UIntX2> operator|(const uint_x4<UInt,UIntX2>& a,
+ const uint_x4<UInt,UIntX2>& b)
+{
+ return uint_x4<UInt,UIntX2>(a.d.v23 | b.d.v23, a.d.v01 | b.d.v01);
+}
+
+template <typename UInt, typename UIntX2>
+uint_x4<UInt,UIntX2> operator^(const uint_x4<UInt,UIntX2>& a,
+ const uint_x4<UInt,UIntX2>& b)
+{
+ return uint_x4<UInt,UIntX2>(a.d.v23 ^ b.d.v23, a.d.v01 ^ b.d.v01);
+}
+
+template <typename UInt, typename UIntX2>
+uint_x4<UInt,UIntX2> operator~(const uint_x4<UInt,UIntX2>& v)
+{
+ return uint_x4<UInt,UIntX2>(~v.d.v23, ~v.d.v01);
+}
+
+template <typename UInt, typename UIntX2>
+uint_x4<UInt,UIntX2> operator-(const uint_x4<UInt,UIntX2>& v)
+{
+ return uint_x4<UInt,UIntX2>(0UL,0UL) - v;
+}
+
+template <typename UInt, typename UIntX2>
+bool operator==(const uint_x4<UInt,UIntX2>& a, const uint_x4<UInt,UIntX2>& b)
+{
+ return (a.d.v01 == b.d.v01) && (a.d.v23 == b.d.v23);
+}
+
+template <typename UInt, typename UIntX2>
+bool operator!=(const uint_x4<UInt,UIntX2>& a, const uint_x4<UInt,UIntX2>& b)
+{
+ return !operator==(a,b);
+}
+
+
+template <typename UInt, typename UIntX2>
+bool operator<(const uint_x4<UInt,UIntX2>& a, const uint_x4<UInt,UIntX2>& b)
+{
+ return (a.d.v23 < b.d.v23)
+ || ((a.d.v23 == b.d.v23) && (a.d.v01 < b.d.v01));
+}
+
+template <typename UInt, typename UIntX2>
+bool operator>(const uint_x4<UInt,UIntX2>& a, const uint_x4<UInt,UIntX2>& b)
+{
+ return operator<(b,a);
+}
+
+template <typename UInt, typename UIntX2>
+bool operator<=(const uint_x4<UInt,UIntX2>& a, const uint_x4<UInt,UIntX2>& b)
+{
+ return !(operator<(b,a));
+}
+
+template <typename UInt, typename UIntX2>
+bool operator>=(const uint_x4<UInt,UIntX2>& a, const uint_x4<UInt,UIntX2>& b)
+{
+ return !(operator<(a,b));
+}
+
+
+
+template <typename UInt, typename UIntX2>
+uint_x4<UInt,UIntX2> operator<<(const uint_x4<UInt,UIntX2>& v,
+ const bitcount_t shift)
+{
+ uint_x4<UInt,UIntX2> r = {0U, 0U, 0U, 0U};
+ const bitcount_t bits = sizeof(UInt) * CHAR_BIT;
+ const bitcount_t bitmask = bits - 1;
+ const bitcount_t shiftdiv = shift / bits;
+ const bitcount_t shiftmod = shift & bitmask;
+
+ if (shiftmod) {
+ UInt carryover = 0;
+#if PCG_LITTLE_ENDIAN
+ for (uint8_t out = shiftdiv, in = 0; out < 4; ++out, ++in) {
+#else
+ for (uint8_t out = 4-shiftdiv, in = 4; out != 0; /* dec in loop */) {
+ --out, --in;
+#endif
+ r.wa[out] = (v.wa[in] << shiftmod) | carryover;
+ carryover = (v.wa[in] >> (bits - shiftmod));
+ }
+ } else {
+#if PCG_LITTLE_ENDIAN
+ for (uint8_t out = shiftdiv, in = 0; out < 4; ++out, ++in) {
+#else
+ for (uint8_t out = 4-shiftdiv, in = 4; out != 0; /* dec in loop */) {
+ --out, --in;
+#endif
+ r.wa[out] = v.wa[in];
+ }
+ }
+
+ return r;
+}
+
+template <typename UInt, typename UIntX2>
+uint_x4<UInt,UIntX2> operator>>(const uint_x4<UInt,UIntX2>& v,
+ const bitcount_t shift)
+{
+ uint_x4<UInt,UIntX2> r = {0U, 0U, 0U, 0U};
+ const bitcount_t bits = sizeof(UInt) * CHAR_BIT;
+ const bitcount_t bitmask = bits - 1;
+ const bitcount_t shiftdiv = shift / bits;
+ const bitcount_t shiftmod = shift & bitmask;
+
+ if (shiftmod) {
+ UInt carryover = 0;
+#if PCG_LITTLE_ENDIAN
+ for (uint8_t out = 4-shiftdiv, in = 4; out != 0; /* dec in loop */) {
+ --out, --in;
+#else
+ for (uint8_t out = shiftdiv, in = 0; out < 4; ++out, ++in) {
+#endif
+ r.wa[out] = (v.wa[in] >> shiftmod) | carryover;
+ carryover = (v.wa[in] << (bits - shiftmod));
+ }
+ } else {
+#if PCG_LITTLE_ENDIAN
+ for (uint8_t out = 4-shiftdiv, in = 4; out != 0; /* dec in loop */) {
+ --out, --in;
+#else
+ for (uint8_t out = shiftdiv, in = 0; out < 4; ++out, ++in) {
+#endif
+ r.wa[out] = v.wa[in];
+ }
+ }
+
+ return r;
+}
+
+} // namespace pcg_extras
+
+#endif // PCG_UINT128_HPP_INCLUDED
http://git-wip-us.apache.org/repos/asf/impala/blob/4feb4f3a/bin/rat_exclude_files.txt
----------------------------------------------------------------------
diff --git a/bin/rat_exclude_files.txt b/bin/rat_exclude_files.txt
index fdb1926..30ebc26 100644
--- a/bin/rat_exclude_files.txt
+++ b/bin/rat_exclude_files.txt
@@ -79,6 +79,7 @@ tests/comparison/ORACLE.txt
bin/distcc/README.md
tests/comparison/POSTGRES.txt
docs/README.md
+be/src/thirdparty/pcg-cpp-0.98/README.md
# http://www.apache.org/legal/src-headers.html: "Test data for which the addition of a
# source header would cause the tests to fail."
@@ -139,6 +140,7 @@ NOTICE.txt
# Notices in thirdparty sources included in the Impala repo and called out in /LICENSE.txt
be/src/thirdparty/squeasel/LICENSE
+be/src/thirdparty/pcg-cpp-0.98/LICENSE.txt
# http://www.apache.org/legal/src-headers.html: 'Snippet' files that are combined as form
# a larger file where the larger file would have duplicate licensing headers.
[6/8] impala git commit: IMPALA-6301: Fix test failures when username
or group name contains dots
Posted by ta...@apache.org.
IMPALA-6301: Fix test failures when username or group name contains dots
Some tests use the local user's group name to construct SQLs, which may
lead to syntax errors when group name contains dots. We need to quote
the group names in SQL to avoid this error. Besides, a test in
test_admission_controller uses '\w+' to match the local user name. This
expression cannot match usernames with dots, which causes test failure
as well. Instead, we should use '\S+'.
Change-Id: Ib8ae15bb6a929dc48d3ad2176c8b3fafff87f32b
Reviewed-on: http://gerrit.cloudera.org:8080/8807
Reviewed-by: Thomas Tauber-Marshall <tm...@cloudera.com>
Reviewed-by: Michael Ho <kw...@cloudera.com>
Tested-by: Impala Public Jenkins
Project: http://git-wip-us.apache.org/repos/asf/impala/repo
Commit: http://git-wip-us.apache.org/repos/asf/impala/commit/5c593be5
Tree: http://git-wip-us.apache.org/repos/asf/impala/tree/5c593be5
Diff: http://git-wip-us.apache.org/repos/asf/impala/diff/5c593be5
Branch: refs/heads/master
Commit: 5c593be59c725f004ead81af94931852410e3a1c
Parents: 2fcbf36
Author: stiga-huang <hu...@gmail.com>
Authored: Sat Dec 9 17:50:22 2017 -0800
Committer: Impala Public Jenkins <im...@gerrit.cloudera.org>
Committed: Wed Dec 13 23:06:45 2017 +0000
----------------------------------------------------------------------
.../queries/QueryTest/grant_revoke.test | 38 ++++++++++----------
.../queries/QueryTest/grant_revoke_kudu.test | 14 ++++----
tests/authorization/test_grant_revoke.py | 6 ++--
.../custom_cluster/test_admission_controller.py | 4 +--
4 files changed, 31 insertions(+), 31 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/impala/blob/5c593be5/testdata/workloads/functional-query/queries/QueryTest/grant_revoke.test
----------------------------------------------------------------------
diff --git a/testdata/workloads/functional-query/queries/QueryTest/grant_revoke.test b/testdata/workloads/functional-query/queries/QueryTest/grant_revoke.test
index f78f1f5..a69a93f 100644
--- a/testdata/workloads/functional-query/queries/QueryTest/grant_revoke.test
+++ b/testdata/workloads/functional-query/queries/QueryTest/grant_revoke.test
@@ -37,7 +37,7 @@ grant all on server to grant_revoke_test_ALL_SERVER
---- QUERY
# Group name will be replaced with the actual user's group in the test
# framework.
-grant role grant_revoke_test_ALL_SERVER to group $GROUP_NAME
+grant role grant_revoke_test_ALL_SERVER to group `$GROUP_NAME`
====
---- QUERY
show current roles
@@ -152,7 +152,7 @@ show create function grant_rev_db.fn
STRING
====
---- QUERY
-revoke role grant_revoke_test_ALL_SERVER from group $GROUP_NAME
+revoke role grant_revoke_test_ALL_SERVER from group `$GROUP_NAME`
====
---- QUERY
create database grant_rev_db location '$FILESYSTEM_PREFIX/test-warehouse/grant_rev_db.db'
@@ -186,7 +186,7 @@ show create function _impala_builtins.sin
STRING
====
---- QUERY
-grant role grant_revoke_test_ALL_TEST_DB to group $GROUP_NAME
+grant role grant_revoke_test_ALL_TEST_DB to group `$GROUP_NAME`
====
---- QUERY
# Should now have all privileges on the test db
@@ -207,7 +207,7 @@ create table grant_rev_db.test_tbl2(i int) location '$FILESYSTEM_PREFIX/test-war
does not have privileges to access: $NAMENODE/test-warehouse/grant_rev_test_tbl2
====
---- QUERY
-grant role grant_revoke_test_ALL_URI to group $GROUP_NAME
+grant role grant_revoke_test_ALL_URI to group `$GROUP_NAME`
====
---- QUERY
grant all on uri '$FILESYSTEM_PREFIX/test-warehouse/grant_rev_test_tbl2' to grant_revoke_test_ALL_URI
@@ -286,7 +286,7 @@ show tables in grant_rev_db
does not have privileges to access: grant_rev_db.*
====
---- QUERY
-grant role grant_revoke_test_SELECT_INSERT_TEST_TBL to group $GROUP_NAME
+grant role grant_revoke_test_SELECT_INSERT_TEST_TBL to group `$GROUP_NAME`
====
---- QUERY
GRANT SELECT ON TABLE grant_rev_db.test_tbl1 TO grant_revoke_test_SELECT_INSERT_TEST_TBL
@@ -349,14 +349,14 @@ User 'test_user' does not have privileges to execute: DROP_ROLE
---- USER
test_user
---- QUERY
-grant role grant_revoke_test_ALL_SERVER to group $GROUP_NAME
+grant role grant_revoke_test_ALL_SERVER to group `$GROUP_NAME`
---- CATCH
User 'test_user' does not have privileges to execute: GRANT_ROLE
====
---- USER
test_user
---- QUERY
-revoke role grant_revoke_test_ALL_SERVER from group $GROUP_NAME
+revoke role grant_revoke_test_ALL_SERVER from group `$GROUP_NAME`
---- CATCH
User 'test_user' does not have privileges to execute: REVOKE_ROLE
====
@@ -486,12 +486,12 @@ STRING, STRING, STRING, STRING, STRING, STRING, BOOLEAN, STRING
root
====
---- QUERY
-REVOKE ROLE grant_revoke_test_ALL_URI FROM GROUP $GROUP_NAME;
-REVOKE ROLE grant_revoke_test_SELECT_INSERT_TEST_TBL FROM GROUP $GROUP_NAME;
+REVOKE ROLE grant_revoke_test_ALL_URI FROM GROUP `$GROUP_NAME`;
+REVOKE ROLE grant_revoke_test_SELECT_INSERT_TEST_TBL FROM GROUP `$GROUP_NAME`;
---- RESULTS
====
---- QUERY
-GRANT ROLE grant_revoke_test_ALL_SERVER TO GROUP $GROUP_NAME
+GRANT ROLE grant_revoke_test_ALL_SERVER TO GROUP `$GROUP_NAME`
---- RESULTS
====
---- QUERY
@@ -693,7 +693,7 @@ scope, database, table, column, uri, privilege, grant_option, create_time
STRING, STRING, STRING, STRING, STRING, STRING, BOOLEAN, STRING
====
---- QUERY
-revoke role grant_revoke_test_ALL_SERVER from group $GROUP_NAME
+revoke role grant_revoke_test_ALL_SERVER from group `$GROUP_NAME`
====
---- QUERY
# Test 'grant all on server' with explicit server name specified.
@@ -704,7 +704,7 @@ create role grant_revoke_test_ALL_SERVER1
grant all on server server1 to grant_revoke_test_ALL_SERVER1
====
---- QUERY
-grant role grant_revoke_test_ALL_SERVER1 to group $GROUP_NAME
+grant role grant_revoke_test_ALL_SERVER1 to group `$GROUP_NAME`
====
---- QUERY
drop database grant_rev_db cascade
@@ -713,7 +713,7 @@ drop database grant_rev_db cascade
create database grant_rev_db location '$FILESYSTEM_PREFIX/test-warehouse/grant_rev_db.db'
====
---- QUERY
-revoke role grant_revoke_test_ALL_SERVER1 from group $GROUP_NAME
+revoke role grant_revoke_test_ALL_SERVER1 from group `$GROUP_NAME`
====
---- QUERY
create database grant_rev_db location '$FILESYSTEM_PREFIX/test-warehouse/grant_rev_db.db'
@@ -743,14 +743,14 @@ STRING, STRING, STRING, STRING, STRING, STRING, BOOLEAN, STRING
---- QUERY
# IMPALA-4951: make sure database is visible to a user having only column level access
# to a table in the database
-grant role grant_revoke_test_ALL_SERVER to group $GROUP_NAME
+grant role grant_revoke_test_ALL_SERVER to group `$GROUP_NAME`
---- RESULTS
====
---- QUERY
create role grant_revoke_test_COLUMN_PRIV
====
---- QUERY
-grant role grant_revoke_test_COLUMN_PRIV to group $GROUP_NAME;
+grant role grant_revoke_test_COLUMN_PRIV to group `$GROUP_NAME`;
====
---- QUERY
create database if not exists grant_rev_db;
@@ -759,7 +759,7 @@ create database if not exists grant_rev_db;
create table grant_rev_db.test_tbl4 (col1 int, col2 int);
====
---- QUERY
-revoke role grant_revoke_test_ALL_SERVER from group $GROUP_NAME
+revoke role grant_revoke_test_ALL_SERVER from group `$GROUP_NAME`
====
---- QUERY
show grant role grant_revoke_test_COLUMN_PRIV
@@ -798,17 +798,17 @@ show databases
STRING,STRING
====
---- QUERY
-grant role grant_revoke_test_ALL_SERVER to group $GROUP_NAME
+grant role grant_revoke_test_ALL_SERVER to group `$GROUP_NAME`
---- RESULTS
====
---- QUERY
drop database if exists grant_rev_db cascade
====
---- QUERY
-revoke role grant_revoke_test_ALL_SERVER from group $GROUP_NAME
+revoke role grant_revoke_test_ALL_SERVER from group `$GROUP_NAME`
====
---- QUERY
-revoke role grant_revoke_test_COLUMN_PRIV from group $GROUP_NAME
+revoke role grant_revoke_test_COLUMN_PRIV from group `$GROUP_NAME`
====
---- QUERY
# Cleanup test roles
http://git-wip-us.apache.org/repos/asf/impala/blob/5c593be5/testdata/workloads/functional-query/queries/QueryTest/grant_revoke_kudu.test
----------------------------------------------------------------------
diff --git a/testdata/workloads/functional-query/queries/QueryTest/grant_revoke_kudu.test b/testdata/workloads/functional-query/queries/QueryTest/grant_revoke_kudu.test
index c552773..a3b9354 100644
--- a/testdata/workloads/functional-query/queries/QueryTest/grant_revoke_kudu.test
+++ b/testdata/workloads/functional-query/queries/QueryTest/grant_revoke_kudu.test
@@ -16,7 +16,7 @@ show roles
STRING
====
---- QUERY
-grant role grant_revoke_test_ALL_SERVER to group $GROUP_NAME
+grant role grant_revoke_test_ALL_SERVER to group `$GROUP_NAME`
====
---- QUERY
grant all on server to grant_revoke_test_ALL_SERVER
@@ -25,14 +25,14 @@ grant all on server to grant_revoke_test_ALL_SERVER
create database grant_rev_db
====
---- QUERY
-grant role grant_revoke_test_ALL_TEST_DB to group $GROUP_NAME
+grant role grant_revoke_test_ALL_TEST_DB to group `$GROUP_NAME`
====
---- QUERY
# Should now have all privileges on the test db
grant all on database grant_rev_db to grant_revoke_test_ALL_TEST_DB
====
---- QUERY
-revoke role grant_revoke_test_ALL_SERVER from group $GROUP_NAME
+revoke role grant_revoke_test_ALL_SERVER from group `$GROUP_NAME`
====
---- QUERY
show current roles
@@ -88,7 +88,7 @@ alter table grant_rev_db.kudu_tbl set tblproperties('external'='true');
does not have privileges to access:
====
---- QUERY
-grant role grant_revoke_test_ALL_SERVER to group $GROUP_NAME
+grant role grant_revoke_test_ALL_SERVER to group `$GROUP_NAME`
====
---- QUERY
# Now the alter table succeeds
@@ -102,13 +102,13 @@ alter table grant_rev_db.kudu_tbl set tblproperties('EXTERNAL'='FALSE');
create role grant_revoke_test_KUDU
====
---- QUERY
-grant role grant_revoke_test_KUDU to group $GROUP_NAME;
+grant role grant_revoke_test_KUDU to group `$GROUP_NAME`;
====
---- QUERY
-revoke role grant_revoke_test_ALL_SERVER from group $GROUP_NAME
+revoke role grant_revoke_test_ALL_SERVER from group `$GROUP_NAME`
====
---- QUERY
-revoke role grant_revoke_test_ALL_TEST_DB from group $GROUP_NAME
+revoke role grant_revoke_test_ALL_TEST_DB from group `$GROUP_NAME`
====
---- QUERY
insert into grant_rev_db.kudu_tbl values (1, "foo");
http://git-wip-us.apache.org/repos/asf/impala/blob/5c593be5/tests/authorization/test_grant_revoke.py
----------------------------------------------------------------------
diff --git a/tests/authorization/test_grant_revoke.py b/tests/authorization/test_grant_revoke.py
index 9430350..34ee513 100644
--- a/tests/authorization/test_grant_revoke.py
+++ b/tests/authorization/test_grant_revoke.py
@@ -69,7 +69,7 @@ class TestGrantRevoke(CustomClusterTestSuite, ImpalaTestSuite):
self.client.execute("create role grant_revoke_test_admin")
try:
self.client.execute("grant all on server to grant_revoke_test_admin")
- self.client.execute("grant role grant_revoke_test_admin to group %s" % group_name)
+ self.client.execute("grant role grant_revoke_test_admin to group `%s`" % group_name)
self.cleanup_db('grant_rev_db', sync_ddl=0)
finally:
self.client.execute("drop role grant_revoke_test_admin")
@@ -117,7 +117,7 @@ class TestGrantRevoke(CustomClusterTestSuite, ImpalaTestSuite):
self.client.execute("create role {0}".format(role_name))
self.client.execute("grant all on server to {0}".format(role_name))
self.client.execute(
- "grant role {0} to group {1}".format(
+ "grant role {0} to group `{1}`".format(
role_name, grp.getgrnam(getuser()).gr_name))
self.client.execute("create database " + db_name)
@@ -180,7 +180,7 @@ class TestGrantRevoke(CustomClusterTestSuite, ImpalaTestSuite):
# Wait a few seconds to make sure the update propagates to the statestore.
sleep(3)
# Update the role, increasing its catalog verion.
- self.client.execute("grant role {0} to group {1}".format(
+ self.client.execute("grant role {0} to group `{1}`".format(
role_name, grp.getgrnam(getuser()).gr_name))
result = self.client.execute("show tables in functional")
assert 'alltypes' in result.data
http://git-wip-us.apache.org/repos/asf/impala/blob/5c593be5/tests/custom_cluster/test_admission_controller.py
----------------------------------------------------------------------
diff --git a/tests/custom_cluster/test_admission_controller.py b/tests/custom_cluster/test_admission_controller.py
index 020bb67..ccbbd32 100644
--- a/tests/custom_cluster/test_admission_controller.py
+++ b/tests/custom_cluster/test_admission_controller.py
@@ -255,12 +255,12 @@ class TestAdmissionController(TestAdmissionControllerBase, HS2TestSuite):
try:
for pool in ['', 'not_a_pool_name']:
expected_error =\
- "No mapping found for request from user '\w+' with requested pool '%s'"\
+ "No mapping found for request from user '\S+' with requested pool '%s'"\
% (pool)
self.__check_pool_rejected(client, pool, expected_error)
# Check rejected if user does not have access.
- expected_error = "Request from user '\w+' with requested pool 'root.queueC' "\
+ expected_error = "Request from user '\S+' with requested pool 'root.queueC' "\
"denied access to assigned pool 'root.queueC'"
self.__check_pool_rejected(client, 'root.queueC', expected_error)
[7/8] impala git commit: IMPALA-6070: Parallelize another bit of data
load.
Posted by ta...@apache.org.
IMPALA-6070: Parallelize another bit of data load.
The two Kudu loads and Hive UDFs can all run in parallel. This
should shave about 4 minutes off of the data load. (Current
timings are 3.5, 4, and 0.6 minutes, see below.)
I've run dataload with this change many times.
Loading Kudu functional (logging to /home/ubuntu/Impala/logs/data_loading/load-kudu.log)...
Loading workload 'functional-query' using exploration strategy 'core' in table formats 'kudu/none/none' OK (Took: 3 min 29 sec)
Loading Kudu TPCH (logging to /home/ubuntu/Impala/logs/data_loading/load-kudu-tpch.log)...
Loading workload 'tpch' using exploration strategy 'core' in table formats 'kudu/none/none' OK (Took: 4 min 0 sec)
Loading Hive UDFs (logging to /home/ubuntu/Impala/logs/data_loading/build-and-copy-hive-udfs.log)...
Loading Hive UDFs OK (Took: 0 min 41 sec)
Change-Id: I7e93ee5a77ec9271b980b88bef7ad512ecbe0407
Reviewed-on: http://gerrit.cloudera.org:8080/8822
Reviewed-by: Dimitris Tsirogiannis <dt...@cloudera.com>
Tested-by: Impala Public Jenkins
Project: http://git-wip-us.apache.org/repos/asf/impala/repo
Commit: http://git-wip-us.apache.org/repos/asf/impala/commit/11dbb395
Tree: http://git-wip-us.apache.org/repos/asf/impala/tree/11dbb395
Diff: http://git-wip-us.apache.org/repos/asf/impala/diff/11dbb395
Branch: refs/heads/master
Commit: 11dbb3952a1c598f27de281c5020ed2df325d6e8
Parents: 5c593be
Author: Philip Zeyliger <ph...@cloudera.com>
Authored: Tue Dec 12 15:38:54 2017 -0800
Committer: Impala Public Jenkins <im...@gerrit.cloudera.org>
Committed: Thu Dec 14 02:28:40 2017 +0000
----------------------------------------------------------------------
testdata/bin/create-load-data.sh | 7 ++++---
1 file changed, 4 insertions(+), 3 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/impala/blob/11dbb395/testdata/bin/create-load-data.sh
----------------------------------------------------------------------
diff --git a/testdata/bin/create-load-data.sh b/testdata/bin/create-load-data.sh
index 099fe59..df6622a 100755
--- a/testdata/bin/create-load-data.sh
+++ b/testdata/bin/create-load-data.sh
@@ -507,13 +507,14 @@ fi
if $KUDU_IS_SUPPORTED; then
# Tests depend on the kudu data being clean, so load the data from scratch.
- run-step "Loading Kudu functional" load-kudu.log \
+ run-step-backgroundable "Loading Kudu functional" load-kudu.log \
load-data "functional-query" "core" "kudu/none/none" force
- run-step "Loading Kudu TPCH" load-kudu-tpch.log \
+ run-step-backgroundable "Loading Kudu TPCH" load-kudu-tpch.log \
load-data "tpch" "core" "kudu/none/none" force
fi
-run-step "Loading Hive UDFs" build-and-copy-hive-udfs.log \
+run-step-backgroundable "Loading Hive UDFs" build-and-copy-hive-udfs.log \
build-and-copy-hive-udfs
+run-step-wait-all
run-step "Running custom post-load steps" custom-post-load-steps.log \
custom-post-load-steps
[5/8] impala git commit: IMPALA-6270: remove redundant version
properties
Posted by ta...@apache.org.
IMPALA-6270: remove redundant version properties
Removes properties that are already defined in the impala-parent pom.
I ran the tests.
Change-Id: I6812e11bb41716450ef29bb523773479e9f76eec
Reviewed-on: http://gerrit.cloudera.org:8080/8827
Reviewed-by: Zach Amsden <za...@cloudera.com>
Tested-by: Impala Public Jenkins
Project: http://git-wip-us.apache.org/repos/asf/impala/repo
Commit: http://git-wip-us.apache.org/repos/asf/impala/commit/2fcbf36c
Tree: http://git-wip-us.apache.org/repos/asf/impala/tree/2fcbf36c
Diff: http://git-wip-us.apache.org/repos/asf/impala/diff/2fcbf36c
Branch: refs/heads/master
Commit: 2fcbf36c32b12f8434eac0370b7f214acba7cc4c
Parents: 4feb4f3
Author: Philip Zeyliger <ph...@cloudera.com>
Authored: Tue Dec 12 20:04:33 2017 -0800
Committer: Impala Public Jenkins <im...@gerrit.cloudera.org>
Committed: Wed Dec 13 22:48:10 2017 +0000
----------------------------------------------------------------------
tests/test-hive-udfs/pom.xml | 2 --
1 file changed, 2 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/impala/blob/2fcbf36c/tests/test-hive-udfs/pom.xml
----------------------------------------------------------------------
diff --git a/tests/test-hive-udfs/pom.xml b/tests/test-hive-udfs/pom.xml
index 9c2e1bd..a1a855a 100644
--- a/tests/test-hive-udfs/pom.xml
+++ b/tests/test-hive-udfs/pom.xml
@@ -36,8 +36,6 @@ under the License.
<properties>
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
- <hadoop.version>${env.IMPALA_HADOOP_VERSION}</hadoop.version>
- <hive.version>${env.IMPALA_HIVE_VERSION}</hive.version>
</properties>
<dependencies>
[8/8] impala git commit: IMPALA-6319: Fix alloc/free mismatch.
Posted by ta...@apache.org.
IMPALA-6319: Fix alloc/free mismatch.
Testing under ASAN:
- reproduced locally
- does not reproduce after fix
- locally ran test_aggregation.py which passed
Change-Id: Ia695201e61d8afc23636f826264635c85d3a228a
Reviewed-on: http://gerrit.cloudera.org:8080/8838
Tested-by: Impala Public Jenkins
Reviewed-by: Jim Apple <jb...@apache.org>
Project: http://git-wip-us.apache.org/repos/asf/impala/repo
Commit: http://git-wip-us.apache.org/repos/asf/impala/commit/3cbbaf3b
Tree: http://git-wip-us.apache.org/repos/asf/impala/tree/3cbbaf3b
Diff: http://git-wip-us.apache.org/repos/asf/impala/diff/3cbbaf3b
Branch: refs/heads/master
Commit: 3cbbaf3b30dd53fd45d45632ed250f79bdd8b48d
Parents: 11dbb39
Author: Alex Behm <al...@cloudera.com>
Authored: Wed Dec 13 22:27:31 2017 -0800
Committer: Alex Behm <al...@cloudera.com>
Committed: Thu Dec 14 16:58:53 2017 +0000
----------------------------------------------------------------------
be/src/util/mpfit-util.h | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/impala/blob/3cbbaf3b/be/src/util/mpfit-util.h
----------------------------------------------------------------------
diff --git a/be/src/util/mpfit-util.h b/be/src/util/mpfit-util.h
index 9eac3c2..9e8d067 100644
--- a/be/src/util/mpfit-util.h
+++ b/be/src/util/mpfit-util.h
@@ -77,7 +77,7 @@ class ObjectiveFunction {
/// Function parameters to be determined by fitting.
const int num_params_;
- std::unique_ptr<double> params_;
+ std::unique_ptr<double[]> params_;
/// MPFit result structure. Populated by in LmsFit(). All pointers in this structure
/// are optional and must be allocated and owned by the caller of mpfit(). Passing