Generating the SHA256 magic constants using comptime

Showcase
1

I’m preparing code samples for a talk on Cryptography that I’m doing with a friend next month, one of which is the SHA256 algorithm. This uses “the first 32 bits of the fractional parts of the cube roots of the first 64 primes” as part of the hash generation and “the first 32 bits of the fractional parts of the square roots of the first eight primes” as the initial hash values. In my first iteration I just hardcoded them like this:

// SHA256 constants - these are the first 32 bits of the fractional parts
// of the cube roots of the first 64 prime numbers
const K = [64]u32{
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
    0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
    0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
    0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
    0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
    0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
    0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
    0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2,
};

// Initial hash values - these are the first 32 bits of the fractional parts
// of the square roots of the first 8 prime numbers
const INITIAL_HASH = [8]u32{
    0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
    0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19,
};

But then I thought “wouldn’t it be more fun to calculate them?” and then I also thought “I bet Zig could do that at comptime” and I was right:

// Generate first 64 primes at comptime
const prime_table: [64]u32 = blk: {
    @setEvalBranchQuota(2048);
    var primes: [64]u32 = undefined;
    var found: usize = 0;
    var n: u32 = 2;
    while (found < 64) : (n += 1) {
        var is_prime = true;
        var d: u32 = 2;
        while (d * d <= n) : (d += 1) {
            if (n % d == 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) {
            primes[found] = n;
            found += 1;
        }
    }
    break :blk primes;
};

const POW2_32: f64 = @floatFromInt(1 << 32);

pub fn sqrt(x: f64) f64 {
    return @sqrt(x);
}

pub fn cbrt(x: f64) f64 {
    return std.math.cbrt(x);
}

pub fn genConstants(comptime count: usize, comptime root: fn (x: f64) f64) [count]u32 {
    const primes = prime_table[0..count];
    var table: [count]u32 = undefined;
    for (primes, 0..) |p, i| {
        const r = root(@floatFromInt(p));
        // Convert fractional float into 32‑bit word
        const f = r - @floor(r);
        table[i] = @intFromFloat(f * POW2_32);
    }
    return table;
}

The sqrt and cbrt functions are there because you can’t pass @sqrt (or std.math.sqrt) and std.math.cbrt as function pointers.

I’m doing the examples in Zig because (a) I love it and I want to tell people about it, and (b) I’m still early in my learning journey so it’s good to have things to do with it. So if there’s any improvements I could make to the above code I’d love to hear about them.

8 Likes
2

Perhaps use a loop label to immediately continue with the outer loop instead of breaking out of the inner loop and managing a variable whether to skip the remaining code in the loop body.

// With label 'search'
search: while (found < 64) : (n += 1) {
      var d: u32 = 2;
      while (d * d <= n) : (d += 1) {
          if (n % d == 0) continue :search;
      }
      primes[found] = n;
      found += 1;
}

// original
while (found < 64) : (n += 1) {
      var is_prime = true;
      var d: u32 = 2;
      while (d * d <= n) : (d += 1) {
          if (n % d == 0) {
              is_prime = false;
              break;
          }
      }
      if (is_prime) {
          primes[found] = n;
          found += 1;
      }
}
1 Like