Skip to content

Optimize HashSink and _MD5Sink.updateHash (RFC impl) - #1013

Merged
jonasfj merged 9 commits into
dart-lang:mainfrom
jonasfj:crypto-md5-step4
Oct 19, 2026
Merged

Optimize HashSink and _MD5Sink.updateHash (RFC impl)#1013
jonasfj merged 9 commits into
dart-lang:mainfrom
jonasfj:crypto-md5-step4

Conversation

@jonasfj

@jonasfj jonasfj commented Oct 14, 2026 •
edited
Loading

Copy link
Copy Markdown
Member

[Optimize HashSink and _MD5Sink.updateHash to reduce allocations and improve MD5 throughput (~1.4x in AOT, ~1.25x in JIT):

4 commits:

  • Make HashSink extend ByteConversionSink directly:
    Eliminates the _ByteAdapterSink wrapper allocation and virtual Sink<List<int>> dispatch in startChunkedConversion, and overrides addSlice to avoid sublist allocations.

  • Share buffer between _chunk and _chunk32 in HashSink:
    Uses a single Uint32List(chunkSizeInWords) buffer shared by _chunk and _byteDataView, and skips the 16-word getUint32 copy loop per block when _endian == Endian.host.

  • Pad in-place in HashSink._finalizeAndProcessData and use setUint64:
    Writes the 0x80 marker, zero padding, and 64-bit bit-length directly into _chunk without allocating a temporary padding Uint8List, and uses _byteDataView.setUint64 when !const bool.fromEnvironment('dart.library.js_interop').

  • Implement _MD5Sink.updateHash following RFC 1321:
    Translates MD5Transform from RFC 1321 Appendix A.3 directly using @pragma('vm:prefer-inline') helpers (_f/_g/_h/_i and _ff/_gg/_hh/_ii) with constant shift amounts, constant chunk indices, and inlined sine table constants, removing the _noise and _shiftAmounts lookup tables.](https://dart-review.googlesource.com/c/sdk/+/566323/2..4)

@jonasfj
jonasfj requested a review from a team as a code owner October 14, 2026 13:12
@jonasfj jonasfj closed this Oct 14, 2026
@jonasfj jonasfj reopened this Oct 14, 2026
@jonasfj
jonasfj marked this pull request as draft October 14, 2026 13:26
@jonasfj
jonasfj force-pushed the crypto-md5-step4 branch 2 times, most recently from 6e90666 to 1b964a5 Compare October 14, 2026 14:06
@jonasfj jonasfj changed the title Optimize HashSink and _MD5Sink.updateHash Optimize HashSink and _MD5Sink.updateHash (RFC impl) Oct 14, 2026
@jonasfj

jonasfj commented Oct 14, 2026

Copy link
Copy Markdown
Member Author

This is a bit faster than #1014, and honestly, easier to review.

@jonasfj

jonasfj commented Oct 15, 2026

Copy link
Copy Markdown
Member Author

I verified the actual rounds against the lines from the RFC:
https://diff.googleplex.com/#key=IBEqQkaqjPVr

@jonasfj
jonasfj force-pushed the crypto-md5-step4 branch 2 times, most recently from 77dbd75 to efe25cc Compare October 15, 2026 08:20
@jonasfj
jonasfj marked this pull request as ready for review October 15, 2026 08:36
@jonasfj
jonasfj requested a review from sigurdm October 15, 2026 08:42
@jonasfj
[crypto] Add md5 tests with RFC 1321 and NESSIE test vectors
4388639 
Add test/md5_test.dart covering md5 directly (previously md5 was only
exercised indirectly through the RFC 2202 HMAC-MD5 vectors):

- RFC 1321 Appendix A.5 test suite (7 vectors).
- NESSIE test vectors: set 1 ("abcdbcde...nopq", one million "a"),
  set 2 (n zero bytes for n = 0..127, i.e. every residue modulo the
  64-byte block size through both padding branches), and set 4
  (128 zero bits iterated 100000 times).
- md5("a" * n) for n around the 56/64 and 120/128 byte padding
  boundaries, with non-zero content so stale buffer bytes would show.

All vectors were cross-checked against Python's hashlib.
@jonasfj
[crypto] Make HashSink extend ByteConversionSink directly
036c6ad 
Make HashSink extend ByteConversionSink instead of implementing
Sink<List<int>> and wrapping it with ByteConversionSink.from(...) in
each Hash.startChunkedConversion implementation.

Also override HashSink.addSlice to pass (data, start, end) directly to
_addData without allocating a sublist copy.
@jonasfj
[crypto] Make HashSink._byteDataView a final field
f715852 
Initialize _byteDataView in the constructor instead of lazily in
_addData, so it is non-nullable and the `??=` and `!` are gone from the
hot loop. A redirecting constructor is used because the view is created
from _chunk, which cannot be referenced while it is itself being
initialized in the same initializer list.

No behavior change.
@jonasfj
[crypto] Extract HashSink._processChunk helper
f8cbd87 
Move the endian conversion and updateHash call from the _addData loop
into a _processChunk helper, so that a following change can process the
final padded chunk without going through _addData.

No behavior change.
@jonasfj
[crypto] Pad in-place in HashSink._finalizeAndProcessData
5978ae3 
Write the 0x80 terminator, zero padding and 64-bit message length
directly into _chunk and process it with _processChunk, instead of
allocating a temporary padding Uint8List and feeding it through
_addData.

A second chunk is needed exactly when the terminator leaves fewer than
_signatureBytes bytes in the current chunk, which is the same condition
the previous _roundUp arithmetic expressed. Every byte of the final
chunk(s) that is not input data is written explicitly, since _chunk is
reused and still holds earlier input.
@jonasfj
[crypto] Use ByteData.setUint64 in HashSink._finalizeAndProcessData
385e7d9 
Write the 64-bit message length with a single setUint64 call, except on
web targets where dart2js does not support it and the two setUint32
writes are kept. The check is a const bool.fromEnvironment on
dart.library.js_interop (the same condition sha512.dart uses to pick
its implementation), so the unused branch is eliminated at compile
time.
@jonasfj
[crypto] Implement _MD5Sink.updateHash following RFC 1321
4d2b813 
Translate MD5Transform from RFC 1321 Appendix A.3 (md5c.c) directly using
prefer-inline helpers _f/_g/_h/_i and _ff/_gg/_hh/_ii with constant shift
amounts (_s11.._s44), constant chunk indices (x[0]..x[15]), and inlined
sine table constants, removing the _noise and _shiftAmounts lookup tables.

The helpers carry both @pragma('vm:prefer-inline') and
@pragma('dart2js:prefer-inline'); dart2js ignores the former, and
without inlining the 64 helper calls per block make md5 slower than
the previous loop on dart2js.
sigurdm
sigurdm approved these changes Oct 19, 2026
View reviewed changes

@sigurdm sigurdm left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM with a couple of minor comments!

Also, the PR description still reflects the earlier 4-commit version of the branch (in particular the second bullet: "Share buffer between _chunk and _chunk32 in HashSink: Uses a single Uint32List(chunkSizeInWords) buffer shared by _chunk and _byteDataView, and skips the 16-word getUint32 copy loop per block when _endian == Endian.host", which was replaced by making _byteDataView a final field, and the new test/md5_test.dart commit isn't mentioned). Could you update the PR description before squash-merging so the commit message matches the landed code?

Comment thread pkgs/crypto/lib/src/md5.dart Resolved
Comment thread pkgs/crypto/lib/src/hash_sink.dart Resolved
@sigurdm

sigurdm commented Oct 19, 2026

Copy link
Copy Markdown
Contributor

Gemini has manually checked all 64 MD5 round calls in _MD5Sink.updateHash against RFC 1321 (the (a, b, c, d) register rotation, _ff/_gg/_hh/_ii round function selection, x[k] message schedule indices, _s11.._s44 shift constants, and the $\lfloor 2^{32} |\sin(i)| \rfloor$ table constants), verified the 1-block and 2-block in-place padding boundaries in HashSink._finalizeAndProcessData for both 64-bit and 128-bit length fields, and cross-checked all test vectors in test/md5_test.dart against Python's hashlib.md5.

@sigurdm

sigurdm commented Oct 19, 2026 •
edited
Loading

Copy link
Copy Markdown
Contributor

As a follow-up idea: the other hashes already inherit the HashSink improvements from this PR, and similar updateHash changes look promising for sha512/sha384, sha1, and sha256/sha224 (quick 1 MB AOT dart compile exe benchmark):

Hash Current (this PR) Adapted updateHash Speedup (AOT)
SHA-512 / SHA-384 55.0 MB/s 153.1 MB/s ~2.78x
SHA-1 107.6 MB/s 156.9 MB/s ~1.46x
SHA-256 / SHA-224 81.9 MB/s 94.1 MB/s (unroll 8) / 37.0 MB/s (unroll 64) ~1.15x
  • SHA-384 / SHA-512 (lib/src/sha512_fastsinks.dart): _shr64 still emulates unsigned 64-bit right-shift as (x >> n) & ~(-1 << (64 - n)) (from before Dart 2.14 added >>>), and _rotr64/_shr64/_ch/_maj/_bsig0/_bsig1/_ssig0/_ssig1 lack @pragma('vm:prefer-inline'). Replacing _shr64 with x >>> n, adding @pragma('vm:prefer-inline'), and adding bounds-check hints (chunk[31]; _extended[79]; _noise64[79]; _digest[7];) nearly triples AOT throughput (55 MB/s → 153 MB/s).
  • SHA-1 (lib/src/sha1.dart): _Sha1Sink.updateHash currently runs a single 0..80 loop that branches on i < 16, i < 20, i < 40, and i < 60 every iteration and shuffles 5 locals (e = d; d = c; ...). Separating the 16..80 message-schedule expansion and running four i += 5 stage loops (rotating (a, b, c, d, e) in place across 5 inline step calls) eliminates the branches and register moves (108 MB/s → 157 MB/s).
  • SHA-224 / SHA-256 (lib/src/sha256.dart): _rotr32.._ssig1 in _Sha32BitSink are currently unannotated instance methods. Because each SHA-256 step is larger than MD5, unrolling all 64 rounds into one method causes register spilling and regresses AOT (82 MB/s → 37 MB/s), but making the helpers static with @pragma('vm:prefer-inline') / @pragma('dart2js:prefer-inline') and unrolling by 8 inside for (var i = 0; i < 64; i += 8) improves AOT to 94 MB/s.

@jonasfj
[crypto] Add prefer-inline pragmas to add32 and rotl32
3c7f71d 
dart2js did not inline rotl32 into _MD5Sink.updateHash, leaving 64
calls per block and preventing the constant shift amounts from being
folded. With @pragma('dart2js:prefer-inline') the rotation is inlined
and constant-folded; @pragma('vm:prefer-inline') makes the VM's
existing behavior explicit.
@jonasfj
[crypto] Clarify zero-fill comment in HashSink._finalizeAndProcessData
9d382b0 
Since _chunk is reused, the fillRange up to _chunk.length - 8 is what
zeroes the high 64 bits of a 128-bit length field; say so in the
comment instead of "skip ahead 8". Also use _byteDataView directly
instead of a local.
@jonasfj
jonasfj merged commit 72e71ca into dart-lang:main Oct 19, 2026
22 checks passed
@jonasfj
jonasfj deleted the crypto-md5-step4 branch October 19, 2026 19:57
copybara-service Bot pushed a commit to dart-lang/sdk that referenced this pull request Oct 20, 2026
@natebosch dart-scoped@luci-project-accounts.iam.gserviceaccount.com
[deps] rev core, dartdoc, ecosystem, http, native, shelf, test, tools…
66c1f3d 
…, web

Revisions updated by `dart tools/rev_sdk_deps.dart`.

core (https://github.com/dart-lang/core/compare/4d80610..72e71ca):
  72e71ca0  Mon Oct 19 21:57:11 2026 +0200  Jonas Finnemann Jensen  Optimize `HashSink` and `_MD5Sink.updateHash` (RFC impl) (dart-lang/core#1013)

dartdoc (https://github.com/dart-lang/dartdoc/compare/e1859cf..c0e19cf):
  c0e19cf6  Mon Oct 19 11:41:42 2026 -0700  Konstantin Scheglov  Import analyzer ast with explicit show. (dart-lang/dartdoc#4300)

ecosystem (https://github.com/dart-lang/ecosystem/compare/622ef61..0ab0cfd):
  0ab0cfd  Mon Oct 19 15:44:26 2026 +0200  Moritz  fix(firehose): bump dependency_validator to support analyzer 14 (dart-lang/ecosystem#453)
  44a0768  Wed Oct 14 09:37:29 2026 -0700  Nate Bosch  Improve firehose publish validation log output (dart-lang/ecosystem#468)

http (https://github.com/dart-lang/http/compare/7d7aae2..a8a24a0):
  a8a24a0  Mon Oct 19 13:31:34 2026 -0700  Kevin Moore  docs(web_socket): remove non-user-visible changelog entry (dart-lang/http#2023)
  6f6ac5f  Mon Oct 19 16:29:43 2026 -0400  Mouad Debbar  [http_multi_server] Retry `loopback(0)` when IPv6 port is already bound (dart-lang/http#2025)
  6e91ce3  Tue Oct 13 16:25:39 2026 -0700  Kevin Moore  Sync root README.md package table from pubspec.yaml files (dart-lang/http#2024)

native (https://github.com/dart-lang/native/compare/cc7e4b0..3cbe319):
  3cbe319e3  Tue Oct 13 15:47:18 2026 +0200  Daco Harkes  [hooks_runner] Fail eagerly when file locking is not supported on file system (dart-lang/native#3679)

shelf (https://github.com/dart-lang/shelf/compare/b2cb503..b66665b):
  b66665b  Fri Oct 16 15:12:05 2026 -0700  Kevin Moore  chore: add health workflow and prepare shelf 1.4.3, shelf_router 1.1.5, and shelf_static 1.2.0 (dart-lang/shelf#546)

test (https://github.com/dart-lang/test/compare/9bf69a8..d1afeb1):
  d1afeb14  Fri Oct 16 20:41:51 2026 -0400  Mouad Debbar  Confirmation that `tearDown` is called on timeout (dart-lang/test#2798)
  3f6c2f14  Thu Oct 15 18:21:35 2026 -0700  Jacob MacDonald  Enable asserts in the cli compiler (dart-lang/test#2795)

tools (https://github.com/dart-lang/tools/compare/c1471db..f6c7a2d):
  f6c7a2d62  Mon Oct 19 07:59:24 2026 -0700  Kevin Moore  [pubspec_parse] Preserve input maps and YamlMap source spans (dart-lang/tools#2653)
  f1a55d953  Mon Oct 19 07:53:51 2026 -0700  Kevin Moore  [yaml] Fix tag URI decoding, numeric tag RangeErrors, and dead checks (dart-lang/tools#2630)
  340ded284  Mon Oct 19 07:43:31 2026 -0700  Kevin Moore  [unified_analytics] Prepare for 8.2.0 release (dart-lang/tools#2689)
  a73703543  Fri Oct 16 11:55:03 2026 -0700  Kevin Moore  [unified_analytics] Bump version to 8.2.0-wip (dart-lang/tools#2688)

web (https://github.com/dart-lang/web/compare/63e6662..4e60e61):
  4e60e61  Mon Oct 19 10:02:22 2026 -0700  dependabot[bot]  Bump source-map-js from 1.2.1 to 1.2.2 in /web_generator (dart-lang/web#591)
  7d63637  Mon Oct 19 09:50:26 2026 -0700  Kevin Moore  Add an api.txt golden for package:web (dart-lang/web#590)

[email protected]

Change-Id: Ibe6ac8a8246a27caa8a4846ea1acc78c801ee2ae
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/566781
Commit-Queue: Nate Bosch <[email protected]>
Reviewed-by: Brian Quinlan <[email protected]>
@jonasfj jonasfj mentioned this pull request Oct 20, 2026
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@sigurdm sigurdm sigurdm approved these changes

Assignees

No one assigned

Labels

package:crypto

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@jonasfj @sigurdm