Something went wrong. Try again.
Nix flake packaging the official Zig compiler binaries, with tagged releases and daily nightlies updated automatically.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265// SPDX-FileCopyrightText: 2026 Jeffrey C. Ollie <jeff@ocjtech.us>//// SPDX-License-Identifier: MIT
//! Decoding of Nix's base-32 hash encoding, the form `nix-prefetch-url`//! prints a hash in, so that it can be turned back into raw bytes and from//! there into the hex and SRI forms the generated expression uses.//!//! It is not RFC 4648 base32 and nothing in the standard library reads it.//! The alphabet is its own, and the bit order is the reverse of what the//! string suggests: the hash is read as one little-endian stream of bits, cut//! into five-bit digits starting from the least significant, and those digits//! are written out most significant first. So the *last* character of the//! string holds the lowest five bits of the first byte, and the first//! character holds whatever is left over at the top of the last byte.
const std = @import("std");
/// The 32 digits, in order of value. It is `0-9a-z` with `e`, `o`, `u` and/// `t` left out, so that a hash can never spell anything unfortunate.const alphabet = "0123456789abcdfghijklmnpqrsvwxyz";
/// Maps every byte to the digit it stands for, or null if it is not one of/// the alphabet, so that decoding is a table lookup rather than a search./// Built at compile time from `alphabet`, so the two cannot disagree.const reverse: [256]?u5 = reverse: { std.debug.assert(alphabet.len == 32); var rv: [256]?u5 = @splat(null); for (alphabet, 0..) |ch, i| { rv[ch] = i; } const rc = rv; break :reverse rc;};
/// Walks an encoded string from its last character to its first, which is/// from its least significant digit to its most -- the order in which the/// digits' bits land in the output.const Reverse = struct { str: []const u8, /// The position in `str` of the character last returned; `str.len` /// before the first call to `next`, and zero once all have been. index: usize,
pub fn init(str: []const u8) Reverse { return .{ .str = str, .index = str.len, }; }
pub const Next = struct { /// The value of the character. digit: u5, /// Its place value, counted from the end of the string: zero for the /// last character, one for the one before it, and so on. The digit's /// bits start at bit `index * 5` of the output. index: usize, };
/// Returns the next digit, or null once the start of the string has been /// passed. A character outside the alphabet is `error.InvalidCharacter`. pub fn next(self: *Reverse) !?Next { if (self.index == 0) return null; self.index -= 1; return .{ .digit = reverse[self.str[self.index]] orelse return error.InvalidCharacter, .index = self.str.len - self.index - 1, }; }};
/// How many characters `encode` makes of `len` bytes: one for every five/// bits, rounded up. 20 bytes make 32 characters and 32 bytes make 52.pub fn encodedLen(len: usize) usize { return std.math.divCeil(usize, len * 8, 5) catch unreachable;}
/// Encodes `input` into `output` and returns the part of `output` that holds/// the result, `encodedLen(input.len)` characters long; `output` must have/// room for at least that. This is the form `nix-hash --type sha256 --base32`/// and `nix-prefetch-url` print, and what `decode` reads back.////// When `input.len * 8` is not a multiple of five, the first character has/// bits left over at its top, and they are always written as zero -- which/// is what `decode` insists on.pub fn encode(output: []u8, input: []const u8) []const u8 { const len = encodedLen(input.len); std.debug.assert(output.len >= len);
for (output[0..len], 0..) |*ch, k| { // The characters are written most significant first, so the one at // `k` is the digit whose bits start at bit `b` of the input, taken // as one little-endian stream: bit `j` of byte `i` onwards. const b = (len - k - 1) * 5; const i = @divFloor(b, 8); const j = @mod(b, 8);
// The part of the digit in byte `i`, and whatever it takes from the // low bits of the next byte when `j` is above 3 -- unless there is no // next byte, which is where the zero padding comes from. `shl`, where // a plain `<<` would not, allows the shift of 8 that `j` of 0 asks // for, and gives nothing, which is right: all five bits are in byte // `i` then. const low = input[i] >> @intCast(j); const high = if (i + 1 < input.len) std.math.shl(u8, input[i + 1], 8 - j) else 0; ch.* = alphabet[@as(u5, @truncate(low | high))]; } return output[0..len];}
/// Decodes `input` into `output` and returns the part of `output` that holds/// the result.////// The result is `input.len * 5 / 8` bytes long, rounded down, and `output`/// must have room for at least that: 32 characters make a 20-byte SHA-1, 52 a/// 32-byte SHA-256. The length follows from the input alone, so a hash with/// zero bytes at the end still comes back at full length.////// When `input.len * 5` is not a multiple of eight, the digits hold more bits/// than the hash has, and the spare ones -- at the top of the first character/// -- must be zero. A set one is `error.InvalidPadding` rather than being/// dropped, the same as Nix itself, since a string that says more than a/// hash can hold is not a hash of that length. A character outside the/// alphabet is `error.InvalidCharacter`.pub fn decode(output: []u8, input: []const u8) error{ InvalidCharacter, InvalidPadding }![]const u8 { const len = @divTrunc(input.len * 5, 8); std.debug.assert(output.len >= len);
// Every digit is OR-ed into place, so the buffer has to start clear. @memset(output[0..len], 0);
var it: Reverse = .init(input);
while (try it.next()) |n| { // The digit occupies bits `b` to `b + 4` of the output, taken as one // little-endian stream: bit `j` of byte `i` onwards. const b = n.index * 5; const i = @divFloor(b, 8); const j = @mod(b, 8);
// As much of the digit as fits in byte `i`. `shl` drops the bits // shifted past the top of the byte rather than overflowing, which is // what is wanted: they are the ones picked up below. const low = std.math.shl(u8, n.digit, j); if (i < len) { output[i] |= low; } else if (low != 0) { return error.InvalidPadding; }
// Whatever did not fit, when `j` is above 3, carries into the low // bits of the next byte -- unless there is no next byte, in which // case it has to be nothing. const high = std.math.shr(u8, n.digit, 8 - @as(u4, @intCast(j))); if (i + 1 < len) { output[i + 1] |= high; } else if (high != 0) { return error.InvalidPadding; } } return output[0..len];}
test decode { const alloc = std.testing.allocator; { const in = "vw46m23bizj4n8afrc0fj19wrp7mj3c0"; var buf: [128]u8 = undefined; const actual = out: { const out = try decode(&buf, in); break :out try std.fmt.allocPrint(alloc, "{x}", .{out}); }; defer alloc.free(actual); try std.testing.expectEqualStrings("800d59cfcd3c05e900cb4e214be48f6b886a08df", actual); } { const in = "1b8m03r63zqhnjf7l5wnldhh7c134ap5vpj0850ymkq1iyzicy5s"; var buf: [128]u8 = undefined; const actual = out: { const out = try decode(&buf, in); break :out try std.fmt.allocPrint(alloc, "sha256-{b64}", .{out}); }; defer alloc.free(actual); try std.testing.expectEqualStrings("sha256-ungWv48Bz+pBQUDeXa4iI7ADYaOWF3qctBD/YfIAFa0=", actual); } { const in = "0vbg7rhyvg7yxn3sbcx7xih0x5kp2vmdp1ckwkma08ankddmg527"; var buf: [128]u8 = undefined; const actual = out: { const out = try decode(&buf, in); break :out try std.fmt.allocPrint(alloc, "sha256-{b64}", .{out}); }; defer alloc.free(actual); try std.testing.expectEqualStrings("sha256-R5RXW5tWIaDq5JOF2+oWd5YOYOyns6WH7f687WE+b20=", actual); } { // The same SHA-256 as above with its first character one higher, // which sets the lowest of the four bits past the end of the hash. var buf: [32]u8 = undefined; try std.testing.expectError( error.InvalidPadding, decode(&buf, "2b8m03r63zqhnjf7l5wnldhh7c134ap5vpj0850ymkq1iyzicy5s"), ); } { // `e` is one of the letters the alphabet leaves out. var buf: [32]u8 = undefined; try std.testing.expectError( error.InvalidCharacter, decode(&buf, "eb8m03r63zqhnjf7l5wnldhh7c134ap5vpj0850ymkq1iyzicy5s"), ); } { // An output exactly the size of the hash is enough. var buf: [32]u8 = undefined; const out = try decode(&buf, "1b8m03r63zqhnjf7l5wnldhh7c134ap5vpj0850ymkq1iyzicy5s"); try std.testing.expectEqual(32, out.len); } { var buf: [0]u8 = undefined; try std.testing.expectEqual(0, (try decode(&buf, "")).len); }}
test encode { { // A SHA-1: 20 bytes, 160 bits, which is exactly 32 digits. var raw: [20]u8 = undefined; _ = try std.fmt.hexToBytes(&raw, "800d59cfcd3c05e900cb4e214be48f6b886a08df"); var buf: [32]u8 = undefined; try std.testing.expectEqualStrings("vw46m23bizj4n8afrc0fj19wrp7mj3c0", encode(&buf, &raw)); } { // A SHA-256: 256 bits in 52 digits, with four bits of padding. var raw: [32]u8 = undefined; try std.base64.standard.Decoder.decode(&raw, "ungWv48Bz+pBQUDeXa4iI7ADYaOWF3qctBD/YfIAFa0="); var buf: [52]u8 = undefined; try std.testing.expectEqualStrings("1b8m03r63zqhnjf7l5wnldhh7c134ap5vpj0850ymkq1iyzicy5s", encode(&buf, &raw)); } { var buf: [0]u8 = undefined; try std.testing.expectEqualStrings("", encode(&buf, "")); }}
test "encode and decode are inverses" { var prng: std.Random.DefaultPrng = .init(0x6e69783332); const random = prng.random();
// Every length up to a SHA-512 and a little past, which covers every // amount of padding the first character can carry. for (0..70) |len| { var raw: [70]u8 = undefined; random.bytes(raw[0..len]);
var text: [encodedLen(70)]u8 = undefined; const encoded = encode(&text, raw[0..len]); try std.testing.expectEqual(encodedLen(len), encoded.len);
var back: [70]u8 = undefined; try std.testing.expectEqualSlices(u8, raw[0..len], try decode(&back, encoded)); }}