Implementation:ClickHouse ClickHouse PCG Extras

Knowledge Sources	ClickHouse
Domains	Random_Number_Generation, Utilities
Last Updated	2026-02-08 00:00 GMT

Overview

Support utilities for PCG random number generators including 128-bit integer operations, bit manipulation, I/O, and seeding helpers.

Description

This header provides infrastructure code supporting the PCG random number generation scheme. It includes 128-bit integer support for platforms without native `__uint128_t`, bit twiddling operations like rotate and unxorshift, stream I/O operators for 128-bit and 8-bit integers, bounded random number generation, Fisher-Yates shuffle implementation, and `seed_seq_from` adapter for initializing RNGs from arbitrary random sources. The code handles both native 128-bit support and emulated versions transparently.

Usage

Use these utilities when working with PCG generators: for seeding from devices, implementing bounded random selections, shuffling sequences, or when you need portable 128-bit arithmetic for generator state manipulation.

Code Reference

Source Location

• Repository: ClickHouse
• File: base/pcg-random/pcg_extras.hpp
• Lines: 1-558

Signature

namespace pcg_extras {

// 128-bit integer type (native or emulated)
typedef pcg128_t;  // __uint128_t or uint_x4<uint32_t, uint64_t>

// Bit manipulation
template <typename itype>
itype unxorshift(itype x, bitcount_t bits, bitcount_t shift);

template <typename itype>
itype rotl(itype value, bitcount_t rot);

template <typename itype>
itype rotr(itype value, bitcount_t rot);

// Bounded random number generation
template <typename RngType>
auto bounded_rand(RngType& rng, typename RngType::result_type upper_bound);

// Shuffle algorithm
template <typename Iter, typename RandType>
void shuffle(Iter from, Iter to, RandType&& rng);

// Seed sequence adapter
template <typename RngType>
class seed_seq_from {
    template<typename Iter>
    void generate(Iter start, Iter finish);
};

// Stream I/O for 128-bit integers
template <typename CharT, typename Traits>
std::basic_ostream<CharT,Traits>& operator<<(std::basic_ostream<CharT,Traits>&, pcg128_t);

template <typename CharT, typename Traits>
std::basic_istream<CharT,Traits>& operator>>(std::basic_istream<CharT,Traits>&, pcg128_t&);

}

Import

#include "base/pcg-random/pcg_extras.hpp"

I/O Contract

Component	Input	Output	Constraints
bounded_rand	RNG, upper_bound	Random value in [0, upper_bound)	Unbiased selection
shuffle	Iterator range, RNG	Shuffled sequence	Fisher-Yates algorithm
rotl/rotr	Value, rotation count	Rotated value	Bit count modulo size
unxorshift	XORed value, shift amount	Original value	Inverts XOR-right-shift
seed_seq_from	RNG, iterator range	Fills range with random data	32-bit values
Stream I/O	pcg128_t value	Decimal or hex output	Handles full 128 bits

Usage Examples

#include "base/pcg-random/pcg_extras.hpp"
#include <random>
#include <vector>

// Bounded random selection without bias
pcg32 rng;
int die_roll = pcg_extras::bounded_rand(rng, 6) + 1;  // Fair die [1,6]

// Generate random number in arbitrary range
int random_in_range(pcg32& rng, int min_val, int max_val) {
    return min_val + pcg_extras::bounded_rand(rng, max_val - min_val + 1);
}

// Shuffle a vector
std::vector<int> cards = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
pcg_extras::shuffle(cards.begin(), cards.end(), rng);

// Seed from random device
std::random_device rd;
pcg_extras::seed_seq_from<std::random_device> seed_source(rd);
pcg32 rng_from_device(seed_source);

// Use 128-bit arithmetic
pcg_extras::pcg128_t large_val = PCG_128BIT_CONSTANT(0x123456789ABCDEF0ULL,
                                                      0xFEDCBA9876543210ULL);
std::cout << "128-bit value: " << large_val << std::endl;

// Bit rotation for custom mixing
uint32_t mixed = pcg_extras::rotl(value, 13);
uint64_t rotated = pcg_extras::rotr(value, 7);

// Invert XOR-shift operations
uint32_t original = 0x12345678;
uint32_t xored = original ^ (original >> 16);
uint32_t recovered = pcg_extras::unxorshift(xored, 32, 16);
assert(recovered == original);

// Random sampling without replacement
std::vector<int> population(100);
std::iota(population.begin(), population.end(), 0);
pcg_extras::shuffle(population.begin(), population.end(), rng);
std::vector<int> sample(population.begin(), population.begin() + 10);

// Weighted random selection using bounded_rand
int weighted_choice(pcg32& rng, const std::vector<int>& weights) {
    int total = std::accumulate(weights.begin(), weights.end(), 0);
    int choice = pcg_extras::bounded_rand(rng, total);
    int cumsum = 0;
    for (size_t i = 0; i < weights.size(); ++i) {
        cumsum += weights[i];
        if (choice < cumsum) return i;
    }
    return weights.size() - 1;
}

// Read/write RNG state with 128-bit support
pcg64 rng64;  // Uses 128-bit state
std::ostringstream oss;
oss << rng64;  // Serializes including 128-bit values
std::string state = oss.str();

std::istringstream iss(state);
pcg64 restored_rng;
iss >> restored_rng;  // Deserializes 128-bit state

Related Pages

• Principle:ClickHouse_ClickHouse_PCG_Random_Number_Generation