pkg/analyzer/test/src/utilities/hash/blake3_test.dart

// Copyright (c) 2026, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

import 'dart:math';
import 'dart:typed_data';

import 'package:analyzer/src/utilities/hash/blake3.dart';
import 'package:test/test.dart';

import 'blake3_reference.dart';

void main() {
  // Avoid dart:mirrors so the same suite can run in AOT as well as JIT.
  group('Blake3', () {
    late Blake3Test suite;
    setUp(() => suite = Blake3Test());
    test('official vectors', () => suite.test_officialVectors());
    test(
      'block and tree boundaries',
      () => suite.test_blockAndTreeBoundaries(),
    );
    test('offset views', () => suite.test_offsetViews());
    test(
      'random and structured inputs',
      () => suite.test_randomAndStructuredInputs(),
    );
    test('reuse and ownership', () => suite.test_reuseAndOwnership());
    test('streaming official vectors', () => suite.test_streamingVectors());
    test('streaming split boundaries', () => suite.test_streamingSplits());
    test('streaming tree boundaries', () => suite.test_streamingTrees());
    test('streaming input views', () => suite.test_streamingViews());
    test('streaming lifecycle', () => suite.test_streamingLifecycle());
  });
}

/// Unkeyed 32-byte prefixes from upstream BLAKE3 1.8.7 test vectors (CC0).
///
/// https://github.com/BLAKE3-team/BLAKE3/blob/f3149ec5bb5449af877ba20377a11008ff499fa2/test_vectors/test_vectors.json
///
/// Input byte i is i % 251. These fixed expectations are not generated by any
/// Dart implementation. Tests need neither native code nor an upstream checkout.
const _blake3Vectors = <int, String>{
  0: 'af1349b9f5f9a1a6a0404dea36dcc9499bcb25c9adc112b7cc9a93cae41f3262',
  1: '2d3adedff11b61f14c886e35afa036736dcd87a74d27b5c1510225d0f592e213',
  2: '7b7015bb92cf0b318037702a6cdd81dee41224f734684c2c122cd6359cb1ee63',
  3: 'e1be4d7a8ab5560aa4199eea339849ba8e293d55ca0a81006726d184519e647f',
  4: 'f30f5ab28fe047904037f77b6da4fea1e27241c5d132638d8bedce9d40494f32',
  5: 'b40b44dfd97e7a84a996a91af8b85188c66c126940ba7aad2e7ae6b385402aa2',
  6: '06c4e8ffb6872fad96f9aaca5eee1553eb62aed0ad7198cef42e87f6a616c844',
  7: '3f8770f387faad08faa9d8414e9f449ac68e6ff0417f673f602a646a891419fe',
  8: '2351207d04fc16ade43ccab08600939c7c1fa70a5c0aaca76063d04c3228eaeb',
  63: 'e9bc37a594daad83be9470df7f7b3798297c3d834ce80ba85d6e207627b7db7b',
  64: '4eed7141ea4a5cd4b788606bd23f46e212af9cacebacdc7d1f4c6dc7f2511b98',
  65: 'de1e5fa0be70df6d2be8fffd0e99ceaa8eb6e8c93a63f2d8d1c30ecb6b263dee',
  127: 'd81293fda863f008c09e92fc382a81f5a0b4a1251cba1634016a0f86a6bd640d',
  128: 'f17e570564b26578c33bb7f44643f539624b05df1a76c81f30acd548c44b45ef',
  129: '683aaae9f3c5ba37eaaf072aed0f9e30bac0865137bae68b1fde4ca2aebdcb12',
  1023: '10108970eeda3eb932baac1428c7a2163b0e924c9a9e25b35bba72b28f70bd11',
  1024: '42214739f095a406f3fc83deb889744ac00df831c10daa55189b5d121c855af7',
  1025: 'd00278ae47eb27b34faecf67b4fe263f82d5412916c1ffd97c8cb7fb814b8444',
  2048: 'e776b6028c7cd22a4d0ba182a8bf62205d2ef576467e838ed6f2529b85fba24a',
  2049: '5f4d72f40d7a5f82b15ca2b2e44b1de3c2ef86c426c95c1af0b6879522563030',
  3072: 'b98cb0ff3623be03326b373de6b9095218513e64f1ee2edd2525c7ad1e5cffd2',
  3073: '7124b49501012f81cc7f11ca069ec9226cecb8a2c850cfe644e327d22d3e1cd3',
  4096: '015094013f57a5277b59d8475c0501042c0b642e531b0a1c8f58d2163229e969',
  4097: '9b4052b38f1c5fc8b1f9ff7ac7b27cd242487b3d890d15c96a1c25b8aa0fb995',
  5120: '9cadc15fed8b5d854562b26a9536d9707cadeda9b143978f319ab34230535833',
  5121: '628bd2cb2004694adaab7bbd778a25df25c47b9d4155a55f8fbd79f2fe154cff',
  6144: '3e2e5b74e048f3add6d21faab3f83aa44d3b2278afb83b80b3c35164ebeca205',
  6145: 'f1323a8631446cc50536a9f705ee5cb619424d46887f3c376c695b70e0f0507f',
  7168: '61da957ec2499a95d6b8023e2b0e604ec7f6b50e80a9678b89d2628e99ada77a',
  7169: 'a003fc7a51754a9b3c7fae0367ab3d782dccf28855a03d435f8cfe74605e7817',
  8192: 'aae792484c8efe4f19e2ca7d371d8c467ffb10748d8a5a1ae579948f718a2a63',
  8193: 'bab6c09cb8ce8cf459261398d2e7aef35700bf488116ceb94a36d0f5f1b7bc3b',
  16384: 'f875d6646de28985646f34ee13be9a576fd515f76b5b0a26bb324735041ddde4',
  31744: '62b6960e1a44bcc1eb1a611a8d6235b6b4b78f32e7abc4fb4c6cdcce94895c47',
  102400: 'bc3e3d41a1146b069abffad3c0d44860cf664390afce4d9661f7902e7943e085',
};

class Blake3Test {
  final hasher = ScalarBlake3();

  /// Checks empty input, and also lengths immediately before, at, and after 64-byte
  /// block and 1024-byte chunk boundaries against the independent reference.
  /// Chunk counts around powers of two exercise both complete and incomplete
  /// trees, including reductions that merge several pending subtrees.
  void test_blockAndTreeBoundaries() {
    var lengths = {
      0,
      for (var block = 1; block <= 129; block++)
        for (final delta in [-1, 0, 1]) block * 64 + delta,
      for (final chunks in [
        for (var i = 1; i <= 20; i++) i,
        31,
        32,
        33,
        63,
        64,
        65,
        127,
        128,
        129,
        255,
        256,
        257,
        511,
        512,
        513,
      ])
        for (final delta in [-1, 0, 1]) chunks * 1024 + delta,
    };
    var random = Random(538901);
    var bytes = _randomBytes(random, lengths.reduce(max));
    for (var length in lengths) {
      _check(Uint8List.sublistView(bytes, 0, length));
    }
  }

  void test_officialVectors() {
    for (var entry in _blake3Vectors.entries) {
      var input = Uint8List.fromList([
        for (var i = 0; i < entry.key; i++) i % 251,
      ]);
      var expected = _decodeHex(entry.value);
      expect(
        referenceBlake3(input),
        expected,
        reason: 'reference ${entry.key}',
      );
      _check(input, expected: expected);
    }
  }

  /// Hashes the same bytes at offsets 0..31 to cover aligned and unaligned views.
  /// Each view must match the digest of a standalone input, excluding the
  /// surrounding sentinel bytes. Comparing the entire backing buffer afterward
  /// checks that neither the input nor the sentinel bytes were modified.
  void test_offsetViews() {
    var random = Random(29);
    for (var length in [
      0,
      1,
      63,
      64,
      65,
      1023,
      1024,
      1025,
      4095,
      4096,
      4097,
      65537,
    ]) {
      var bytes = _randomBytes(random, length);
      var expected = referenceBlake3(bytes);
      for (var offset = 0; offset < 32; offset++) {
        var backing = Uint8List(length + 64)..fillRange(0, length + 64, 0xa5);
        backing.setRange(offset, offset + length, bytes);
        var before = Uint8List.fromList(backing);
        _check(
          Uint8List.sublistView(backing, offset, offset + length),
          expected: expected,
        );
        expect(
          backing,
          before,
          reason: 'input/sentinels $length offset $offset',
        );
      }
    }
  }

  void test_randomAndStructuredInputs() {
    var random = Random(20260920);
    for (var i = 0; i < 64; i++) {
      _check(_randomBytes(random, random.nextInt(20000)));
    }
    for (var length in [1, 65, 1024, 2049, 8192, 262145]) {
      for (var value in [0, 0x80, 0xff]) {
        _check(Uint8List(length)..fillRange(0, length, value));
      }
    }
  }

  /// Checks that one hasher can process differently sized, unmodifiable inputs
  /// while keeping every returned digest independently owned. Empty and small
  /// inputs after large inputs exercise the reset of reusable scratch storage.
  /// Mutating the input buffers and making later hash calls must leave saved
  /// digests intact. Mutating one digest must not affect other digests or the
  /// result of a subsequent hash call.
  void test_reuseAndOwnership() {
    var random = Random(7);
    var saved = <(Uint8List, Uint8List)>[];
    for (var length in [524289, 0, 1, 1024, 63, 8193, 0, 65, 4096]) {
      var bytes = _randomBytes(random, length);
      var expected = referenceBlake3(bytes);
      var digest = hasher.hash(bytes.asUnmodifiableView());
      expect(digest, expected);
      expect(digest.length, 32);
      saved.add((digest, Uint8List.fromList(digest)));
      bytes.fillRange(0, length, 0);
    }
    for (var (digest, expected) in saved) {
      expect(digest, expected, reason: 'retained digest changed');
    }
    saved.last.$1.fillRange(0, 32, 0);
    expect(hasher.hash(Uint8List(0)), _decodeHex(_blake3Vectors[0]!));
    for (var (digest, expected) in saved.take(saved.length - 1)) {
      expect(digest, expected, reason: 'digest storage aliases');
    }
  }

  void test_streamingLifecycle() {
    var sink = ScalarBlake3Sink();
    var expected = referenceBlake3(Uint8List.fromList([1, 2, 3]));
    var input = Uint8List.fromList([1, 2, 3]);
    sink.add(input);
    input.fillRange(0, input.length, 0);
    var first = sink.finish();
    expect(first, expected);
    var saved = sink.finish();
    first.fillRange(0, first.length, 0);
    expect(sink.finish(), expected);
    var empty = Uint8List(0);
    var next = Uint8List.fromList([4]);
    expect(() => sink.add(empty), throwsStateError);
    expect(() => sink.add(next), throwsStateError);

    for (var length in [65537, 0, 64, 1, 1024, 1025, 0]) {
      sink.reset();
      var bytes = Uint8List.fromList([
        for (var i = 0; i < length; i++) i & 255,
      ]);
      sink.add(bytes);
      expect(sink.finish(), referenceBlake3(bytes));
      expect(saved, expected);
    }
    sink.reset();
    sink.add(Uint8List(4097));
    sink.reset();
    expect(sink.finish(), referenceBlake3(Uint8List(0)));

    sink.reset();
    sink.add(Uint8List.fromList([1, 2, 3]));
    expect(sink.finish(), expected);
  }

  void test_streamingSplits() {
    var sink = ScalarBlake3Sink();
    var empty = Uint8List(0);
    var random = Random(563962);
    for (var length in [
      0,
      1,
      63,
      64,
      65,
      127,
      128,
      129,
      1023,
      1024,
      1025,
      2048,
      2049,
    ]) {
      var input = _randomBytes(random, length);
      var expected = referenceBlake3(input);
      for (var split = 0; split <= length; split++) {
        sink.reset();
        sink.add(Uint8List.sublistView(input, 0, split));
        sink.add(empty);
        sink.add(Uint8List.sublistView(input, split, length));
        expect(sink.finish(), expected, reason: '$length split $split');
      }
    }
  }

  void test_streamingTrees() {
    var random = Random(17);
    var sink = ScalarBlake3Sink();
    for (var chunks in [3, 4, 7, 8, 15, 16, 31, 32, 127, 128, 255, 256]) {
      for (var delta in [-1, 0, 1]) {
        var input = _randomBytes(random, chunks * 1024 + delta);
        sink.reset();
        for (var start = 0; start < input.length;) {
          var end = min(input.length, start + 1 + random.nextInt(8192));
          sink.add(Uint8List.sublistView(input, start, end));
          start = end;
        }
        expect(sink.finish(), referenceBlake3(input));
      }
    }
  }

  void test_streamingVectors() {
    var sink = ScalarBlake3Sink();
    for (var entry in _blake3Vectors.entries) {
      var input = Uint8List.fromList([
        for (var i = 0; i < entry.key; i++) i % 251,
      ]);
      var expected = _decodeHex(entry.value);
      for (var size in [1, 3, 4, 63, 64, 65, 1023, 1024, 1025, 16384]) {
        sink.reset();
        for (var start = 0; start < input.length; start += size) {
          sink.add(
            Uint8List.sublistView(
              input,
              start,
              min(start + size, input.length),
            ),
          );
        }
        expect(sink.finish(), expected, reason: '${entry.key} pieces of $size');
      }
    }
  }

  void test_streamingViews() {
    var random = Random(42);
    for (var length in [0, 63, 64, 65, 1023, 1024, 1025, 4097]) {
      var input = _randomBytes(random, length);
      var expected = referenceBlake3(input);
      for (var offset = 0; offset < 32; offset++) {
        var backing = Uint8List(length + 64)..fillRange(0, length + 64, 0xa5);
        backing.setRange(offset, offset + length, input);
        var original = Uint8List.fromList(backing);
        var view = Uint8List.sublistView(backing, offset, offset + length);
        var sink = ScalarBlake3Sink();
        sink.add(view.asUnmodifiableView());
        expect(backing, original);
        backing.fillRange(0, backing.length, 0);
        expect(sink.finish(), expected);

        sink.reset();
        sink.add(
          Uint8List.sublistView(
            original.asUnmodifiableView(),
            offset,
            offset + length,
          ),
        );
        expect(sink.finish(), expected);
      }
    }
  }

  void _check(Uint8List input, {Uint8List? expected}) {
    expected ??= referenceBlake3(input);
    expect(
      hasher.hash(input),
      expected,
      reason: 'length ${input.length}, offset ${input.offsetInBytes}',
    );
  }

  Uint8List _decodeHex(String hex) => Uint8List.fromList([
    for (var i = 0; i < hex.length; i += 2)
      int.parse(hex.substring(i, i + 2), radix: 16),
  ]);

  Uint8List _randomBytes(Random random, int length) =>
      Uint8List.fromList(List.generate(length, (_) => random.nextInt(256)));
}