Implementation:ClickHouse ClickHouse PCG Uint128

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

Overview

Portable 128-bit unsigned integer implementation for platforms without native support.

Description

This header provides a 128-bit unsigned integer class `uint_x4` that emulates 128-bit arithmetic using four 32-bit integers or two 64-bit integers arranged in a union. It implements all standard arithmetic operations (addition, subtraction, multiplication, division, modulo), bitwise operations (AND, OR, XOR, shifts), comparison operators, and provides endian-aware layout. The implementation uses careful carry propagation for multi-precision arithmetic and includes optimized division using binary search with logarithmic complexity.

Usage

Use this implementation when working with PCG generators that require 128-bit state on platforms that lack native `__uint128_t` support, or when you need consistent 128-bit integer behavior across different architectures.

Code Reference

Source Location

• Repository: ClickHouse
• File: base/pcg-random/pcg_uint128.hpp
• Lines: 1-748

Signature

namespace pcg_extras {

template <typename UInt, typename UIntX2>
class uint_x4 {
public:
    // Construction
    uint_x4();
    uint_x4(UInt v3, UInt v2, UInt v1, UInt v0);
    uint_x4(UIntX2 v23, UIntX2 v01);
    template<typename Integral> uint_x4(Integral v01);

    // Conversions
    explicit operator uint64_t() const;
    explicit operator uint32_t() const;
    explicit operator bool() const;

    // Arithmetic operators
    uint_x4 operator+(const uint_x4& rhs) const;
    uint_x4 operator-(const uint_x4& rhs) const;
    uint_x4 operator*(const uint_x4& rhs) const;
    uint_x4 operator/(const uint_x4& rhs) const;
    uint_x4 operator%(const uint_x4& rhs) const;

    // Bitwise operators
    uint_x4 operator&(const uint_x4& rhs) const;
    uint_x4 operator|(const uint_x4& rhs) const;
    uint_x4 operator^(const uint_x4& rhs) const;
    uint_x4 operator~() const;
    uint_x4 operator<<(bitcount_t shift) const;
    uint_x4 operator>>(bitcount_t shift) const;

    // Comparison operators
    bool operator==(const uint_x4& rhs) const;
    bool operator!=(const uint_x4& rhs) const;
    bool operator<(const uint_x4& rhs) const;
    bool operator<=(const uint_x4& rhs) const;
    bool operator>(const uint_x4& rhs) const;
    bool operator>=(const uint_x4& rhs) const;

    // Compound assignment
    uint_x4& operator+=(const uint_x4& rhs);
    uint_x4& operator*=(const uint_x4& rhs);
    uint_x4& operator>>=(bitcount_t shift);
    // ... and others
};

// Helper functions
bitcount_t flog2(const uint_x4& v);      // Floor of log2
bitcount_t trailingzeros(const uint_x4& v);

// Typical instantiation
typedef uint_x4<uint32_t, uint64_t> pcg128_t;

}

Import

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

I/O Contract

Operation Category	Input Types	Output Type	Performance Notes
Arithmetic (+, -, *)	uint_x4, uint_x4	uint_x4	O(1) with carry propagation
Division (/, %)	uint_x4, uint_x4	uint_x4 or pair	O(log n) using binary search
, ^)	uint_x4, uint_x4	uint_x4	O(1) on 64-bit parts
Shifts (<<, >>)	uint_x4, bitcount_t	uint_x4	O(1) with endian handling
Comparisons	uint_x4, uint_x4	bool	O(1) lexicographic
Bit operations	uint_x4	bitcount_t	O(1) or O(log n)

Usage Examples

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

using namespace pcg_extras;

// Construction
uint_x4<uint32_t, uint64_t> a(0x12345678, 0x9ABCDEF0,
                               0xFEDCBA98, 0x76543210);

// From high/low 64-bit parts
uint_x4<uint32_t, uint64_t> b(0x123456789ABCDEF0ULL,
                               0xFEDCBA9876543210ULL);

// From integer
uint_x4<uint32_t, uint64_t> c(42ULL);

// Arithmetic operations
auto sum = a + b;
auto difference = a - b;
auto product = a * c;
auto quotient = a / c;
auto remainder = a % c;

// Bitwise operations
auto bit_and = a & b;
auto bit_or = a | b;
auto bit_xor = a ^ b;
auto complement = ~a;

// Shifts
auto left_shifted = a << 32;
auto right_shifted = a >> 16;

// Comparisons
if (a < b) {
    std::cout << "a is less than b\n";
}

bool equal = (a == b);
bool not_equal = (a != b);

// Conversion to smaller types
uint64_t low_bits = uint64_t(a);
uint32_t lowest = uint32_t(a);

// Use in PCG generator state
typedef uint_x4<uint32_t, uint64_t> pcg128_t;

pcg128_t state(0xcafef00dd15ea5e5ULL, 0x0123456789abcdefULL);
pcg128_t multiplier(0x2360ED051FC65DA4ULL, 0x4385DF649FCCF645ULL);
pcg128_t increment(0x5851F42D4C957F2DULL, 0x14057B7EF767814FULL);

// LCG step: state = state * multiplier + increment
state = state * multiplier + increment;

// Find position of highest set bit
bitcount_t log2_val = flog2(state);

// Count trailing zeros
pcg128_t mask(0, 0x00FF000000000000ULL);
bitcount_t trailing = trailingzeros(mask);

// Division with remainder
auto div_result = divmod(a, b);
pcg128_t quot = div_result.first;
pcg128_t rem = div_result.second;

// Compound assignments
pcg128_t accumulator(0ULL);
accumulator += pcg128_t(100ULL);
accumulator *= pcg128_t(2ULL);
accumulator >>= 4;

// Use as loop counter
pcg128_t counter(0ULL);
pcg128_t limit(1000000ULL);
while (counter < limit) {
    // Process...
    counter += pcg128_t(1ULL);
}

// Implement LCG with 128-bit state
class LCG128 {
    pcg128_t state_;
    pcg128_t multiplier_;
    pcg128_t increment_;

public:
    LCG128(uint64_t seed)
        : state_(seed)
        , multiplier_(0x2360ED051FC65DA4ULL, 0x4385DF649FCCF645ULL)
        , increment_(0x5851F42D4C957F2DULL, 0x14057B7EF767814FULL)
    {}

    uint64_t next() {
        state_ = state_ * multiplier_ + increment_;
        return uint64_t(state_ >> 64);
    }
};

// Check for overflow
pcg128_t large_value(~0ULL, ~0ULL);  // Max value
if (large_value + pcg128_t(1ULL) == pcg128_t(0ULL)) {
    std::cout << "Overflow detected\n";
}

// Boolean conversion
pcg128_t zero(0ULL);
pcg128_t nonzero(1ULL);
if (nonzero) {
    std::cout << "Non-zero value\n";
}
if (!zero) {
    std::cout << "Zero value\n";
}

Related Pages

• Principle:ClickHouse_ClickHouse_PCG_Random_Number_Generation