lib/std/hash/blake3.rad 8.5 KiB raw
1
//! Streaming unkeyed BLAKE3 with 32-byte digests.
2
3
@test export mod tests;
4
5
use std::bits;
6
use std::fmt;
7
use std::mem;
8
9
/// Number of bytes in one BLAKE3 compression block.
10
constant BLOCK_BYTES: u32 = 64;
11
/// Number of 32-bit words in one BLAKE3 compression block.
12
constant BLOCK_WORDS: u32 = BLOCK_BYTES / 4;
13
/// Number of bytes in a BLAKE3 digest.
14
export constant DIGEST_BYTES: u32 = 32;
15
16
/// Initial chaining words from the BLAKE3 specification.
17
constant IV: [u32; 8] = [
18
    0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
19
    0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19,
20
];
21
/// Flag for the first block of a chunk.
22
constant CHUNK_START: u32 = 1;
23
/// Flag for the last block of a chunk.
24
constant CHUNK_END: u32 = 2;
25
/// Flag for a parent node of the hash tree.
26
constant PARENT: u32 = 4;
27
/// Flag for the root output of the hash tree.
28
constant ROOT: u32 = 8;
29
30
/// Byte offsets for the two column and two diagonal message vectors per round.
31
constant SCHEDULE: *[u32] = &[
32
    0, 8, 16, 24, 4, 12, 20, 28, 32, 40, 48, 56, 36, 44, 52, 60,
33
    8, 12, 28, 16, 24, 40, 0, 52, 4, 48, 36, 60, 44, 20, 56, 32,
34
    12, 40, 52, 28, 16, 48, 8, 56, 24, 36, 44, 32, 20, 0, 60, 4,
35
    40, 48, 56, 52, 28, 36, 12, 60, 16, 44, 20, 4, 0, 8, 32, 24,
36
    48, 36, 60, 56, 52, 44, 40, 32, 28, 20, 0, 24, 8, 12, 4, 16,
37
    36, 44, 32, 60, 56, 20, 48, 4, 52, 0, 8, 16, 12, 40, 24, 28,
38
    44, 20, 4, 32, 60, 0, 36, 24, 56, 8, 12, 28, 40, 48, 16, 52,
39
];
40
41
/// A 32-byte BLAKE3 digest.
42
export record Digest: Copy {
43
    /// Digest bytes in output order.
44
    bytes: [u8; DIGEST_BYTES],
45
}
46
47
/// Compression input for a chunk block or a parent node.
48
record Output: Copy {
49
    /// Input chaining words.
50
    words: [u32; 8],
51
    /// Little-endian message words with zero padding.
52
    block: [u32; BLOCK_WORDS],
53
    /// Chunk number, or zero for a parent or root output.
54
    counter: u64,
55
    /// Number of message bytes in the block.
56
    length: u32,
57
    /// Node and block flags.
58
    flags: u32,
59
}
60
61
/// Incremental state for a message shorter than 2^64 bytes.
62
export opaque record State {
63
    /// Current chunk chaining words.
64
    words: [u32; 8],
65
    /// Partial block, retained until more input or finalization.
66
    block: [u8; BLOCK_BYTES],
67
    /// Number of initialized bytes in the block.
68
    used: u32,
69
    /// Number of compressed blocks in the current chunk, from zero to 15.
70
    blocks: u32,
71
    /// Current chunk number.
72
    counter: u64,
73
    /// Number of input bytes.
74
    length: u64,
75
    /// Left subtree values, eight words each. 54 levels cover 2^64 bytes.
76
    stack: [u32; 432],
77
    /// Number of subtree values in the stack.
78
    depth: u32,
79
}
80
81
/// Initialize an unkeyed BLAKE3 message.
82
export fn new() -> State {
83
    return State {
84
        words: IV,
85
        block: [0; BLOCK_BYTES],
86
        used: 0,
87
        blocks: 0,
88
        counter: 0,
89
        length: 0,
90
        stack: [0; 432],
91
        depth: 0,
92
    };
93
}
94
95
/// Compress one block into eight output words with seven wrapping rounds.
96
/// The input arrays must be initialized. The metadata contains the counter
97
/// halves, block length and flags. The schedule must contain 112 offsets,
98
/// each of which addresses a message word. All result words are written.
99
unsafe fn compressWords(
100
    result: &mut [u32; 8],
101
    words: &[u32; 8],
102
    message: &[u32; BLOCK_WORDS],
103
    metadata: &[u32; 4],
104
    iv: &[u32; 8],
105
    schedule: *u32
106
);
107
108
/// Read exactly 64 bytes into little-endian message words.
109
/// The input address must provide 64 readable bytes. It can be unaligned.
110
unsafe fn loadBlock(result: &mut [u32; BLOCK_WORDS], bytes: &u8);
111
112
/// Compress a node and return its first eight output words.
113
fn compress(input: &Output) -> [u32; 8] {
114
    let metadata: [u32; 4] = [
115
        input.counter as u32, (input.counter >> 32) as u32,
116
        input.length, input.flags,
117
    ];
118
    let mut result: [u32; 8] = undefined;
119
    unsafe {
120
        compressWords(
121
            &mut result, &input.words, &input.block, &metadata, &IV, SCHEDULE.ptr
122
        );
123
    }
124
    return result;
125
}
126
127
/// Read one complete block as little-endian words.
128
fn readBlock(bytes: &[u8]) -> [u32; BLOCK_WORDS] {
129
    assert bytes.len >= BLOCK_BYTES;
130
    let mut result: [u32; BLOCK_WORDS] = undefined;
131
    unsafe {
132
        loadBlock(&mut result, bytes.ptr);
133
    }
134
    return result;
135
}
136
137
/// Join two subtree values into a parent compression input.
138
fn parent(left: &[u32], right: &[u32]) -> Output {
139
    let mut block: [u32; BLOCK_WORDS] = [0; BLOCK_WORDS];
140
    for i in 0 as u32 .. 8 {
141
        set block[i] = left[i];
142
        set block[i + 8] = right[i];
143
    }
144
    return Output { words: IV, block, counter: 0, length: BLOCK_BYTES, flags: PARENT };
145
}
146
147
/// Add message bytes. The complete message must be shorter than 2^64 bytes.
148
export fn update(state: &mut State, bytes: &[u8]) {
149
    assert bytes.len as u64 <= mem::U64_MAX - state.length;
150
    set state.length += bytes.len as u64;
151
    let mut offset: u32 = 0;
152
    while offset < bytes.len {
153
        let flags = CHUNK_START if state.blocks == 0 else 0;
154
        if state.used == BLOCK_BYTES {
155
            let mut output = Output {
156
                words: state.words,
157
                block: readBlock(&state.block[..]),
158
                counter: state.counter,
159
                length: BLOCK_BYTES,
160
                flags,
161
            };
162
            if state.blocks == 15 {
163
                set output.flags |= CHUNK_END;
164
                let mut value = compress(&output);
165
                set state.counter += 1;
166
                // Each trailing zero completes one left subtree.
167
                let merges = bits::trailingZeros64(state.counter);
168
                for _ in 0 .. merges {
169
                    set state.depth -= 1;
170
                    let start = state.depth * 8;
171
                    set value = compress(&parent(&state.stack[start .. start + 8], &value[..]));
172
                }
173
                let start = state.depth * 8;
174
                for i in 0 as u32 .. 8 {
175
                    set state.stack[start + i] = value[i];
176
                }
177
                set state.depth += 1;
178
                set state.words = IV;
179
                set state.blocks = 0;
180
            } else {
181
                set state.words = compress(&output);
182
                set state.blocks += 1;
183
            }
184
            set state.used = 0;
185
            continue;
186
        }
187
        // Full nonfinal blocks can be read from the input slice.
188
        if state.used == 0 and bytes.len - offset > BLOCK_BYTES and state.blocks < 15 {
189
            set state.words = compress(&Output {
190
                words: state.words,
191
                block: readBlock(&bytes[offset .. offset + BLOCK_BYTES]),
192
                counter: state.counter,
193
                length: BLOCK_BYTES,
194
                flags,
195
            });
196
            set state.blocks += 1;
197
            set offset += BLOCK_BYTES;
198
            continue;
199
        }
200
        let space = BLOCK_BYTES - state.used;
201
        let remaining = bytes.len - offset;
202
        let count = remaining if remaining < space else space;
203
        try! mem::copy(
204
            &mut state.block[state.used .. state.used + count], &bytes[offset .. offset + count]
205
        );
206
        set state.used += count;
207
        set offset += count;
208
    }
209
}
210
211
/// Complete the final chunk and hash tree, then return the root digest.
212
export fn finish(input: State) -> Digest {
213
    let mut state = input;
214
    mem::fill(&mut state.block[state.used ..], 0);
215
    let flags = CHUNK_END | (CHUNK_START if state.blocks == 0 else 0);
216
    let mut output = Output {
217
        words: state.words,
218
        block: readBlock(&state.block[..]),
219
        counter: state.counter,
220
        length: state.used,
221
        flags,
222
    };
223
    while state.depth > 0 {
224
        set state.depth -= 1;
225
        let start = state.depth * 8;
226
        let right = compress(&output);
227
        set output = parent(&state.stack[start .. start + 8], &right[..]);
228
    }
229
    set output.counter = 0;
230
    set output.flags |= ROOT;
231
    let words = compress(&output);
232
    let mut result = Digest { bytes: [0; DIGEST_BYTES] };
233
    for word, i in &words[..] {
234
        mem::store32Le(&mut result.bytes[..], i * 4, word);
235
    }
236
    return result;
237
}
238
239
/// Compute the unkeyed digest of one byte sequence.
240
export fn digest(bytes: &[u8]) -> Digest {
241
    let mut state = new();
242
    update(&mut state, bytes);
243
    return finish(state);
244
}
245
246
/// Parse a digest from exactly 64 hexadecimal digits, in either letter case.
247
export fn parse(text: &[u8]) -> Digest throws (fmt::ParseError) {
248
    let mut result = Digest { bytes: [0; DIGEST_BYTES] };
249
    if text.len <> result.bytes.len * 2 {
250
        throw fmt::ParseError::Invalid;
251
    }
252
    try fmt::parseHex(text, &mut result.bytes[..]);
253
    return result;
254
}