跳转到内容

std.hash.cityhash

标准库Zig 0.17.0官方原文
源码std/hash/cityhash.zig

第 1 行

std.hash.cityhash.CityHash32

命名空间

第 16 行

std.hash.cityhash.CityHash32.c1

常量

第 20 行

u32

std.hash.cityhash.CityHash32.c2

常量

第 21 行

u32

std.hash.cityhash.CityHash32.fmix

函数

第 24 行

fn fmix(h: u32) u32

参数

h: u32

std.hash.cityhash.CityHash32.hash

函数

第 87 行

pub fn hash(str: []const u8) u32

参数

str: []const u8

std.hash.cityhash.CityHash32.hash32Len0To4

函数

第 51 行

fn hash32Len0To4(str: []const u8) u32

参数

str: []const u8

std.hash.cityhash.CityHash32.hash32Len13To24

函数

第 75 行

fn hash32Len13To24(str: []const u8) u32

参数

str: []const u8

std.hash.cityhash.CityHash32.hash32Len5To12

函数

第 62 行

fn hash32Len5To12(str: []const u8) u32

参数

str: []const u8

std.hash.cityhash.CityHash32.mur

函数

第 40 行

fn mur(a: u32, h: u32) u32

参数

a: u32
h: u32

std.hash.cityhash.CityHash32.rotr32

函数

第 35 行

fn rotr32(x: u32, comptime r: u32) u32

参数

x: u32
r: u32

std.hash.cityhash.CityHash32.Self

别名

第 17 行

别名目标 std.hash.cityhash.CityHash32

std.hash.cityhash.CityHash32hashIgnoreSeed

函数

第 345 行

fn CityHash32hashIgnoreSeed(str: []const u8, seed: u32) u32

参数

str: []const u8
seed: u32

std.hash.cityhash.CityHash64

命名空间

第 170 行

std.hash.cityhash.CityHash64.hash

函数

第 292 行

pub fn hash(str: []const u8) u64

参数

str: []const u8

std.hash.cityhash.CityHash64.hash128To64

函数

第 200 行

fn hash128To64(low: u64, high: u64) u64

参数

low: u64
high: u64

std.hash.cityhash.CityHash64.hashLen0To16

函数

第 204 行

fn hashLen0To16(str: []const u8) u64

参数

str: []const u8

std.hash.cityhash.CityHash64.hashLen16

函数

第 187 行

fn hashLen16(u: u64, v: u64) u64

参数

u: u64
v: u64

std.hash.cityhash.CityHash64.hashLen16Mul

函数

第 191 行

fn hashLen16Mul(low: u64, high: u64, mul: u64) u64

参数

low: u64
high: u64
mul: u64

std.hash.cityhash.CityHash64.hashLen17To32

函数

第 230 行

fn hashLen17To32(str: []const u8) u64

参数

str: []const u8

std.hash.cityhash.CityHash64.hashLen33To64

函数

第 241 行

fn hashLen33To64(str: []const u8) u64

参数

str: []const u8

std.hash.cityhash.CityHash64.hashWithSeed

函数

第 336 行

pub fn hashWithSeed(str: []const u8, seed: u64) u64

参数

str: []const u8
seed: u64

std.hash.cityhash.CityHash64.hashWithSeeds

函数

第 340 行

pub fn hashWithSeeds(str: []const u8, seed0: u64, seed1: u64) u64

参数

str: []const u8
seed0: u64
seed1: u64

std.hash.cityhash.CityHash64.k0

常量

第 174 行

u64

std.hash.cityhash.CityHash64.k1

常量

第 175 行

u64

std.hash.cityhash.CityHash64.k2

常量

第 176 行

u64

std.hash.cityhash.CityHash64.rotr64

函数

第 179 行

fn rotr64(x: u64, comptime r: u64) u64

参数

x: u64
r: u64

std.hash.cityhash.CityHash64.Self

别名

第 171 行

别名目标 std.hash.cityhash.CityHash64

std.hash.cityhash.CityHash64.shiftmix

函数

第 183 行

fn shiftmix(v: u64) u64

参数

v: u64

std.hash.cityhash.CityHash64.weakHashLen32WithSeeds

函数

第 281 行

fn weakHashLen32WithSeeds(ptr: [*]const u8, a: u64, b: u64) WeakPair

参数

ptr: [*]const u8
a: u64
b: u64

std.hash.cityhash.CityHash64.weakHashLen32WithSeedsHelper

函数

第 269 行

fn weakHashLen32WithSeedsHelper(w: u64, x: u64, y: u64, z: u64, a: u64, b: u64) WeakPair

参数

w: u64
x: u64
y: u64
z: u64
a: u64
b: u64

std.hash.cityhash.CityHash64.WeakPair

容器

第 264 行

字段

first: u64
second: u64

std.hash.cityhash.do

函数

第 354 行

fn do() !void

std.hash.cityhash.do

函数

第 367 行

fn do() !void

std.hash.cityhash.fetch32

函数

第 8 行

fn fetch32(ptr: [*]const u8, offset: usize) u32

参数

ptr: [*]const u8
offset: usize

std.hash.cityhash.fetch64

函数

第 12 行

fn fetch64(ptr: [*]const u8, offset: usize) u64

参数

ptr: [*]const u8
offset: usize

std.hash.cityhash.offsetPtr

函数

第 3 行

inline fn offsetPtr(ptr: [*]const u8, offset: usize) [*]const u8

参数

ptr: [*]const u8
offset: usize

std.hash.cityhash.std

别名

第 1 行

别名目标 std

std.hash.cityhash.verify

别名

第 350 行

别名目标 std.hash.verify

源码

std/hash/cityhash.zig

const std = @import("std");

inline fn offsetPtr(ptr: [*]const u8, offset: usize) [*]const u8 {
    // ptr + offset 在编译期不可用,因此需要改用此方式。
    return @as([*]const u8, @ptrCast(&ptr[offset]));
}

fn fetch32(ptr: [*]const u8, offset: usize) u32 {
    return std.mem.readInt(u32, offsetPtr(ptr, offset)[0..4], .little);
}

fn fetch64(ptr: [*]const u8, offset: usize) u64 {
    return std.mem.readInt(u64, offsetPtr(ptr, offset)[0..8], .little);
}

pub const CityHash32 = struct {
    const Self = @This();

    // 32 位哈希所用魔数,复制自 Murmur3。
    const c1: u32 = 0xcc9e2d51;
    const c2: u32 = 0x1b873593;

    // 从 Murmur3 复制的 32 位到 32 位整数哈希。
    fn fmix(h: u32) u32 {
        var h1: u32 = h;
        h1 ^= h1 >> 16;
        h1 *%= 0x85ebca6b;
        h1 ^= h1 >> 13;
        h1 *%= 0xc2b2ae35;
        h1 ^= h1 >> 16;
        return h1;
    }

    // 循环右移辅助函数
    fn rotr32(x: u32, comptime r: u32) u32 {
        return (x >> r) | (x << (32 - r));
    }

    // 来自 Murmur3、用于组合两个 32 位值的辅助函数。
    fn mur(a: u32, h: u32) u32 {
        var a1: u32 = a;
        var h1: u32 = h;
        a1 *%= c1;
        a1 = rotr32(a1, 17);
        a1 *%= c2;
        h1 ^= a1;
        h1 = rotr32(h1, 19);
        return h1 *% 5 +% 0xe6546b64;
    }

    fn hash32Len0To4(str: []const u8) u32 {
        const len: u32 = @as(u32, @truncate(str.len));
        var b: u32 = 0;
        var c: u32 = 9;
        for (str) |v| {
            b = b *% c1 +% @as(u32, @bitCast(@as(i32, @intCast(@as(i8, @bitCast(v))))));
            c ^= b;
        }
        return fmix(mur(b, mur(len, c)));
    }

    fn hash32Len5To12(str: []const u8) u32 {
        var a: u32 = @as(u32, @truncate(str.len));
        var b: u32 = a *% 5;
        var c: u32 = 9;
        const d: u32 = b;

        a +%= fetch32(str.ptr, 0);
        b +%= fetch32(str.ptr, str.len - 4);
        c +%= fetch32(str.ptr, (str.len >> 1) & 4);

        return fmix(mur(c, mur(b, mur(a, d))));
    }

    fn hash32Len13To24(str: []const u8) u32 {
        const len: u32 = @as(u32, @truncate(str.len));
        const a: u32 = fetch32(str.ptr, (str.len >> 1) - 4);
        const b: u32 = fetch32(str.ptr, 4);
        const c: u32 = fetch32(str.ptr, str.len - 8);
        const d: u32 = fetch32(str.ptr, str.len >> 1);
        const e: u32 = fetch32(str.ptr, 0);
        const f: u32 = fetch32(str.ptr, str.len - 4);

        return fmix(mur(f, mur(e, mur(d, mur(c, mur(b, mur(a, len)))))));
    }

    pub fn hash(str: []const u8) u32 {
        if (str.len <= 24) {
            if (str.len <= 4) {
                return hash32Len0To4(str);
            } else {
                if (str.len <= 12)
                    return hash32Len5To12(str);
                return hash32Len13To24(str);
            }
        }

        const len: u32 = @as(u32, @truncate(str.len));
        var h: u32 = len;
        var g: u32 = c1 *% len;
        var f: u32 = g;

        const a0: u32 = rotr32(fetch32(str.ptr, str.len - 4) *% c1, 17) *% c2;
        const a1: u32 = rotr32(fetch32(str.ptr, str.len - 8) *% c1, 17) *% c2;
        const a2: u32 = rotr32(fetch32(str.ptr, str.len - 16) *% c1, 17) *% c2;
        const a3: u32 = rotr32(fetch32(str.ptr, str.len - 12) *% c1, 17) *% c2;
        const a4: u32 = rotr32(fetch32(str.ptr, str.len - 20) *% c1, 17) *% c2;

        h ^= a0;
        h = rotr32(h, 19);
        h = h *% 5 +% 0xe6546b64;
        h ^= a2;
        h = rotr32(h, 19);
        h = h *% 5 +% 0xe6546b64;
        g ^= a1;
        g = rotr32(g, 19);
        g = g *% 5 +% 0xe6546b64;
        g ^= a3;
        g = rotr32(g, 19);
        g = g *% 5 +% 0xe6546b64;
        f +%= a4;
        f = rotr32(f, 19);
        f = f *% 5 +% 0xe6546b64;
        var iters = (str.len - 1) / 20;
        var ptr = str.ptr;
        while (iters != 0) : (iters -= 1) {
            const b0: u32 = rotr32(fetch32(ptr, 0) *% c1, 17) *% c2;
            const b1: u32 = fetch32(ptr, 4);
            const b2: u32 = rotr32(fetch32(ptr, 8) *% c1, 17) *% c2;
            const b3: u32 = rotr32(fetch32(ptr, 12) *% c1, 17) *% c2;
            const b4: u32 = fetch32(ptr, 16);

            h ^= b0;
            h = rotr32(h, 18);
            h = h *% 5 +% 0xe6546b64;
            f +%= b1;
            f = rotr32(f, 19);
            f = f *% c1;
            g +%= b2;
            g = rotr32(g, 18);
            g = g *% 5 +% 0xe6546b64;
            h ^= b3 +% b1;
            h = rotr32(h, 19);
            h = h *% 5 +% 0xe6546b64;
            g ^= b4;
            g = @byteSwap(g) *% 5;
            h +%= b4 *% 5;
            h = @byteSwap(h);
            f +%= b0;
            const t: u32 = h;
            h = f;
            f = g;
            g = t;
            ptr = offsetPtr(ptr, 20);
        }
        g = rotr32(g, 11) *% c1;
        g = rotr32(g, 17) *% c1;
        f = rotr32(f, 11) *% c1;
        f = rotr32(f, 17) *% c1;
        h = rotr32(h +% g, 19);
        h = h *% 5 +% 0xe6546b64;
        h = rotr32(h, 17) *% c1;
        h = rotr32(h +% f, 19);
        h = h *% 5 +% 0xe6546b64;
        h = rotr32(h, 17) *% c1;
        return h;
    }
};

pub const CityHash64 = struct {
    const Self = @This();

    // 位于 2^63 与 2^64 之间、供多种用途使用的若干质数。
    const k0: u64 = 0xc3a5c85c97cb3127;
    const k1: u64 = 0xb492b66fbe98f273;
    const k2: u64 = 0x9ae16a3b2f90404f;

    // 循环右移辅助函数
    fn rotr64(x: u64, comptime r: u64) u64 {
        return (x >> r) | (x << (64 - r));
    }

    fn shiftmix(v: u64) u64 {
        return v ^ (v >> 47);
    }

    fn hashLen16(u: u64, v: u64) u64 {
        return @call(.always_inline, hash128To64, .{ u, v });
    }

    fn hashLen16Mul(low: u64, high: u64, mul: u64) u64 {
        var a: u64 = (low ^ high) *% mul;
        a ^= (a >> 47);
        var b: u64 = (high ^ a) *% mul;
        b ^= (b >> 47);
        b *%= mul;
        return b;
    }

    fn hash128To64(low: u64, high: u64) u64 {
        return @call(.always_inline, hashLen16Mul, .{ low, high, 0x9ddfea08eb382d69 });
    }

    fn hashLen0To16(str: []const u8) u64 {
        const len: u64 = @as(u64, str.len);
        if (len >= 8) {
            const mul: u64 = k2 +% len *% 2;
            const a: u64 = fetch64(str.ptr, 0) +% k2;
            const b: u64 = fetch64(str.ptr, str.len - 8);
            const c: u64 = rotr64(b, 37) *% mul +% a;
            const d: u64 = (rotr64(a, 25) +% b) *% mul;
            return hashLen16Mul(c, d, mul);
        }
        if (len >= 4) {
            const mul: u64 = k2 +% len *% 2;
            const a: u64 = fetch32(str.ptr, 0);
            return hashLen16Mul(len +% (a << 3), fetch32(str.ptr, str.len - 4), mul);
        }
        if (len > 0) {
            const a: u8 = str[0];
            const b: u8 = str[str.len >> 1];
            const c: u8 = str[str.len - 1];
            const y: u32 = @as(u32, @intCast(a)) +% (@as(u32, @intCast(b)) << 8);
            const z: u32 = @as(u32, @truncate(str.len)) +% (@as(u32, @intCast(c)) << 2);
            return shiftmix(@as(u64, @intCast(y)) *% k2 ^ @as(u64, @intCast(z)) *% k0) *% k2;
        }
        return k2;
    }

    fn hashLen17To32(str: []const u8) u64 {
        const len: u64 = @as(u64, str.len);
        const mul: u64 = k2 +% len *% 2;
        const a: u64 = fetch64(str.ptr, 0) *% k1;
        const b: u64 = fetch64(str.ptr, 8);
        const c: u64 = fetch64(str.ptr, str.len - 8) *% mul;
        const d: u64 = fetch64(str.ptr, str.len - 16) *% k2;

        return hashLen16Mul(rotr64(a +% b, 43) +% rotr64(c, 30) +% d, a +% rotr64(b +% k2, 18) +% c, mul);
    }

    fn hashLen33To64(str: []const u8) u64 {
        const len: u64 = @as(u64, str.len);
        const mul: u64 = k2 +% len *% 2;
        const a: u64 = fetch64(str.ptr, 0) *% k2;
        const b: u64 = fetch64(str.ptr, 8);
        const c: u64 = fetch64(str.ptr, str.len - 24);
        const d: u64 = fetch64(str.ptr, str.len - 32);
        const e: u64 = fetch64(str.ptr, 16) *% k2;
        const f: u64 = fetch64(str.ptr, 24) *% 9;
        const g: u64 = fetch64(str.ptr, str.len - 8);
        const h: u64 = fetch64(str.ptr, str.len - 16) *% mul;

        const u: u64 = rotr64(a +% g, 43) +% (rotr64(b, 30) +% c) *% 9;
        const v: u64 = ((a +% g) ^ d) +% f +% 1;
        const w: u64 = @byteSwap((u +% v) *% mul) +% h;
        const x: u64 = rotr64(e +% f, 42) +% c;
        const y: u64 = (@byteSwap((v +% w) *% mul) +% g) *% mul;
        const z: u64 = e +% f +% c;
        const a1: u64 = @byteSwap((x +% z) *% mul +% y) +% b;
        const b1: u64 = shiftmix((z +% a1) *% mul +% d +% h) *% mul;
        return b1 +% x;
    }

    const WeakPair = struct {
        first: u64,
        second: u64,
    };

    fn weakHashLen32WithSeedsHelper(w: u64, x: u64, y: u64, z: u64, a: u64, b: u64) WeakPair {
        var a1: u64 = a;
        var b1: u64 = b;
        a1 +%= w;
        b1 = rotr64(b1 +% a1 +% z, 21);
        const c: u64 = a1;
        a1 +%= x;
        a1 +%= y;
        b1 +%= rotr64(a1, 44);
        return WeakPair{ .first = a1 +% z, .second = b1 +% c };
    }

    fn weakHashLen32WithSeeds(ptr: [*]const u8, a: u64, b: u64) WeakPair {
        return @call(.always_inline, weakHashLen32WithSeedsHelper, .{
            fetch64(ptr, 0),
            fetch64(ptr, 8),
            fetch64(ptr, 16),
            fetch64(ptr, 24),
            a,
            b,
        });
    }

    pub fn hash(str: []const u8) u64 {
        if (str.len <= 32) {
            if (str.len <= 16) {
                return hashLen0To16(str);
            } else {
                return hashLen17To32(str);
            }
        } else if (str.len <= 64) {
            return hashLen33To64(str);
        }

        var len: u64 = @as(u64, str.len);

        var x: u64 = fetch64(str.ptr, str.len - 40);
        var y: u64 = fetch64(str.ptr, str.len - 16) +% fetch64(str.ptr, str.len - 56);
        var z: u64 = hashLen16(fetch64(str.ptr, str.len - 48) +% len, fetch64(str.ptr, str.len - 24));
        var v: WeakPair = weakHashLen32WithSeeds(offsetPtr(str.ptr, str.len - 64), len, z);
        var w: WeakPair = weakHashLen32WithSeeds(offsetPtr(str.ptr, str.len - 32), y +% k1, x);

        x = x *% k1 +% fetch64(str.ptr, 0);
        len = (len - 1) & ~@as(u64, @intCast(63));

        var ptr: [*]const u8 = str.ptr;
        while (true) {
            x = rotr64(x +% y +% v.first +% fetch64(ptr, 8), 37) *% k1;
            y = rotr64(y +% v.second +% fetch64(ptr, 48), 42) *% k1;
            x ^= w.second;
            y +%= v.first +% fetch64(ptr, 40);
            z = rotr64(z +% w.first, 33) *% k1;
            v = weakHashLen32WithSeeds(ptr, v.second *% k1, x +% w.first);
            w = weakHashLen32WithSeeds(offsetPtr(ptr, 32), z +% w.second, y +% fetch64(ptr, 16));
            const t: u64 = z;
            z = x;
            x = t;

            ptr = offsetPtr(ptr, 64);
            len -= 64;
            if (len == 0)
                break;
        }

        return hashLen16(hashLen16(v.first, w.first) +% shiftmix(y) *% k1 +% z, hashLen16(v.second, w.second) +% x);
    }

    pub fn hashWithSeed(str: []const u8, seed: u64) u64 {
        return @call(.always_inline, Self.hashWithSeeds, .{ str, k2, seed });
    }

    pub fn hashWithSeeds(str: []const u8, seed0: u64, seed1: u64) u64 {
        return hashLen16(hash(str) -% seed0, seed1);
    }
};

fn CityHash32hashIgnoreSeed(str: []const u8, seed: u32) u32 {
    _ = seed;
    return CityHash32.hash(str);
}

const verify = @import("verify.zig");

test "cityhash32" {
    const Test = struct {
        fn do() !void {
            // SMHasher 未提供该算法的 32 位版本。
            // 本实现已与 Google Abseil 版本对照验证。
            try std.testing.expectEqual(verify.smhasher(CityHash32hashIgnoreSeed), 0x68254F81);
        }
    };
    try Test.do();
    @setEvalBranchQuota(75000);
    try comptime Test.do();
}

test "cityhash64" {
    const Test = struct {
        fn do() !void {
            // 此实现与 SMHasher 的 CityHash64 实现不兼容!
            // 已针对 Google Abseil 版本进行验证。
            try std.testing.expectEqual(verify.smhasher(CityHash64.hashWithSeed), 0x5FABC5C5);
        }
    };
    try Test.do();
    @setEvalBranchQuota(75000);
    try comptime Test.do();
}