main.dart

// SPDX-FileCopyrightText: Copyright 2026, Sarah Aronson <dev@ourcana.space> and the willow_dart contributors
// SPDX-License-Identifier: MIT OR Apache-2.0

library;

import 'dart:typed_data';

const int william3Width = 32;
const int william3ChunkSize = 1024;
const int _blockLen = 64;

const int _chunkStart = 1 << 0;
const int _chunkEnd = 1 << 1;
const int _parent = 1 << 2;
const int _root = 1 << 3;

const List<int> _iv = [
  0xc88f633b,
  0x4168fbf2,
  0x6ba32583,
  0xb0ff1847,
  0xac57e47d,
  0xa8931330,
  0x796a4645,
  0x6b28a3ee,
];

const List<List<int>> _msgSchedule = [
  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],
  [2, 6, 3, 10, 7, 0, 4, 13, 1, 11, 12, 5, 9, 14, 15, 8],
  [3, 4, 10, 12, 13, 2, 7, 14, 6, 5, 9, 0, 11, 15, 8, 1],
  [10, 7, 12, 9, 14, 3, 13, 15, 4, 0, 11, 2, 5, 8, 1, 6],
  [12, 13, 9, 11, 15, 10, 14, 8, 7, 2, 5, 3, 0, 1, 6, 4],
  [9, 14, 11, 5, 8, 12, 15, 1, 13, 3, 0, 10, 2, 6, 4, 7],
  [11, 15, 5, 0, 1, 9, 8, 6, 14, 10, 2, 12, 3, 4, 7, 13],
];

int _rotr32(int x, int n) {
  x &= 0xFFFFFFFF;
  return ((x >> n) | (x << (32 - n))) & 0xFFFFFFFF;
}

void _g(Uint32List s, int a, int b, int c, int d, int x, int y) {
  s[a] = (s[a] + s[b] + x) & 0xFFFFFFFF;
  s[d] = _rotr32(s[d] ^ s[a], 16);
  s[c] = (s[c] + s[d]) & 0xFFFFFFFF;
  s[b] = _rotr32(s[b] ^ s[c], 12);
  s[a] = (s[a] + s[b] + y) & 0xFFFFFFFF;
  s[d] = _rotr32(s[d] ^ s[a], 8);
  s[c] = (s[c] + s[d]) & 0xFFFFFFFF;
  s[b] = _rotr32(s[b] ^ s[c], 7);
}

void _round(Uint32List state, Uint32List msg, int r) {
  final sch = _msgSchedule[r];
  _g(state, 0, 4, 8, 12, msg[sch[0]], msg[sch[1]]);
  _g(state, 1, 5, 9, 13, msg[sch[2]], msg[sch[3]]);
  _g(state, 2, 6, 10, 14, msg[sch[4]], msg[sch[5]]);
  _g(state, 3, 7, 11, 15, msg[sch[6]], msg[sch[7]]);
  _g(state, 0, 5, 10, 15, msg[sch[8]], msg[sch[9]]);
  _g(state, 1, 6, 11, 12, msg[sch[10]], msg[sch[11]]);
  _g(state, 2, 7, 8, 13, msg[sch[12]], msg[sch[13]]);
  _g(state, 3, 4, 9, 14, msg[sch[14]], msg[sch[15]]);
}

Uint32List _wordsFromLe64(Uint8List block) {
  final out = Uint32List(16);
  final bd = ByteData.sublistView(block);
  for (var i = 0; i < 16; i++) {
    out[i] = bd.getUint32(i * 4, Endian.little);
  }
  return out;
}

void _compressInPlace(
  Uint32List cv,
  Uint8List block,
  int blockLen,
  int counter,
  int flags,
) {
  final m = _wordsFromLe64(block);
  final state = Uint32List(16);
  state.setRange(0, 8, cv);
  state.setRange(8, 12, _iv);
  state[12] = counter & 0xFFFFFFFF;
  state[13] = (counter >> 32) & 0xFFFFFFFF;
  state[14] = blockLen & 0xFFFFFFFF;
  state[15] = flags & 0xFFFFFFFF;

  for (var r = 0; r < 7; r++) {
    _round(state, m, r);
  }

  for (var i = 0; i < 8; i++) {
    cv[i] = state[i] ^ state[i + 8];
  }
}

Uint8List _cvBytes(Uint32List cv) {
  final out = Uint8List(32);
  final bd = ByteData.sublistView(out);
  for (var i = 0; i < 8; i++) {
    bd.setUint32(i * 4, cv[i], Endian.little);
  }
  return out;
}

Uint8List _hash1({
  required Uint8List input,
  required List<int> key,
  required int counter,
  required int flags,
  required int flagsStart,
  required int flagsEnd,
}) {
  final cv = Uint32List.fromList(key);
  var offset = 0;
  var blockFlags = flags | flagsStart;

  // empty input returns the bare key bytes with no compression..?
  if (input.isEmpty) {
    return _cvBytes(cv);
  }

  while (offset < input.length) {
    final left = input.length - offset;
    if (left <= _blockLen) {
      blockFlags |= flagsEnd;
    }

    final Uint8List block;
    if (left < _blockLen) {
      block = Uint8List(_blockLen);
      block.setRange(0, left, input, offset);
    } else {
      block = Uint8List.sublistView(input, offset, offset + _blockLen);
    }

    _compressInPlace(cv, block, _blockLen, counter, blockFlags);

    blockFlags = flags;
    offset += left < _blockLen ? left : _blockLen;
  }

  return _cvBytes(cv);
}

Uint8List _hashChunk(Uint8List chunk, {required bool isRoot}) {
  var flagsEnd = _chunkEnd;
  if (isRoot) flagsEnd |= _root;
  return _hash1(
    input: chunk,
    key: _iv,
    counter: 0,
    flags: 0,
    flagsStart: _chunkStart,
    flagsEnd: flagsEnd,
  );
}

Uint8List _hashInner(
  Uint8List left,
  Uint8List right,
  int subtreeLen, {
  required bool isRoot,
}) {
  var flags = _parent;
  if (isRoot) flags |= _root;
  final block = Uint8List(_blockLen);
  block.setRange(0, 32, left);
  block.setRange(32, 64, right);
  return _hash1(
    input: block,
    key: _iv,
    counter: subtreeLen,
    flags: flags,
    flagsStart: 0,
    flagsEnd: 0,
  );
}

int _leftSplit(int n) {
  if ((n & (n - 1)) == 0) return n >> 1;
  var p = 1;
  while ((p << 1) < n) {
    p <<= 1;
  }
  return p;
}

Uint8List _doBatch(Uint8List bytes, int start, int end, bool isRoot) {
  final len = end - start;
  if (len <= william3ChunkSize) {
    return _hashChunk(
      Uint8List.sublistView(bytes, start, end),
      isRoot: isRoot,
    );
  }
  final leftLen = _leftSplit(len);
  final left = _doBatch(bytes, start, start + leftLen, false);
  final right = _doBatch(bytes, start + leftLen, end, false);
  return _hashInner(left, right, len, isRoot: isRoot);
}

Uint8List william3Hash(List<int> input) {
  final bytes = input is Uint8List ? input : Uint8List.fromList(input);
  return _doBatch(bytes, 0, bytes.length, true);
}

class William3Hasher {
  final List<_Subtree> _stack = [];
  final Uint8List _chunkBuf = Uint8List(william3ChunkSize);
  int _chunkLen = 0;
  int _totalLen = 0;

  void add(List<int> bytes) {
    var i = 0;
    while (i < bytes.length) {
      if (_chunkLen == william3ChunkSize) {
        _completeChunk();
      }
      final room = william3ChunkSize - _chunkLen;
      final take = (bytes.length - i) < room ? (bytes.length - i) : room;
      for (var k = 0; k < take; k++) {
        // List<int> may hold values >255; don't trust! mask setRange
        _chunkBuf[_chunkLen + k] = bytes[i + k] & 0xFF;
        // TODO: correctness should be enforced to save ops...
      }
      _chunkLen += take;
      _totalLen += take;
      i += take;
    }
  }

  void _completeChunk() {
    final label = _hashChunk(
      Uint8List.sublistView(_chunkBuf, 0, _chunkLen),
      isRoot: false,
    );
    var node = _Subtree(label, _chunkLen);
    _chunkLen = 0;
    while (_stack.isNotEmpty && _stack.last.chunks == node.chunks) {
      final left = _stack.removeLast();
      final merged = _hashInner(
        left.label,
        node.label,
        left.byteLen + node.byteLen,
        isRoot: false,
      );
      node = _Subtree(merged, left.byteLen + node.byteLen, left.chunks * 2);
    }
    _stack.add(node);
  }

  Uint8List digest() {
    if (_totalLen <= william3ChunkSize) {
      return _hashChunk(
        Uint8List.sublistView(_chunkBuf, 0, _chunkLen),
        isRoot: true,
      );
    }

    final stack = List<_Subtree>.from(_stack);
    _Subtree? acc;
    if (_chunkLen > 0) {
      final label = _hashChunk(
        Uint8List.sublistView(_chunkBuf, 0, _chunkLen),
        isRoot: false,
      );
      acc = _Subtree(label, _chunkLen);
    }

    while (stack.isNotEmpty) {
      final left = stack.removeLast();
      if (acc == null) {
        acc = left;
        continue;
      }
      final newLen = left.byteLen + acc.byteLen;
      final isRoot = stack.isEmpty;
      final merged = _hashInner(left.label, acc.label, newLen, isRoot: isRoot);
      acc = _Subtree(merged, newLen);
    }

    return acc!.label;
  }
}

class _Subtree {
  final Uint8List label;
  final int byteLen;
  final int chunks;
  _Subtree(this.label, this.byteLen, [this.chunks = 1]);
}

// SPDX-FileCopyrightText: 2026 Sarah Aronson
// SPDX-License-Identifier: MIT OR Apache-2.0

void main() {
  final vectors = <(String, List<int>, List<int>)>[
    ('empty', List<int>.filled(0, 0), <int>[59, 99, 143, 200, 242, 251, 104, 65, 131, 37, 163, 107, 71, 24, 255, 176, 125, 228, 87, 172, 48, 19, 147, 168, 69, 70, 106, 121, 238, 163, 40, 107]),
    ('1 x 0x00', List<int>.filled(1, 0), <int>[45, 15, 76, 38, 148, 217, 210, 239, 109, 30, 192, 102, 72, 242, 255, 71, 227, 171, 85, 143, 59, 195, 232, 222, 3, 222, 108, 10, 143, 125, 146, 9]),
    ('1024 x 0x01', List<int>.filled(1024, 1), <int>[242, 177, 126, 219, 185, 216, 149, 65, 56, 20, 89, 207, 65, 27, 7, 116, 80, 61, 55, 190, 199, 61, 17, 28, 25, 234, 232, 117, 202, 92, 25, 93]),
    ('1025 x 0x02', List<int>.filled(1025, 2), <int>[219, 231, 162, 187, 226, 242, 23, 168, 73, 98, 18, 128, 177, 35, 87, 172, 234, 183, 208, 0, 137, 58, 57, 195, 180, 21, 221, 196, 108, 142, 201, 212]),
    ('4097 x 0x03', List<int>.filled(4097, 3), <int>[213, 158, 45, 108, 119, 139, 160, 205, 101, 51, 60, 72, 4, 138, 223, 12, 139, 139, 84, 43, 68, 123, 194, 98, 166, 165, 16, 84, 40, 125, 205, 189]),
  ];
  var failed = 0;
  for (final (name, input, expected) in vectors) {
    final ok = _eq(william3Hash(input), expected);
    if (!ok) failed++;
    print('${ok ? "PASS" : "FAIL"}  $name');
  }
  print(failed == 0 ? 'all ${vectors.length} vectors passed' : '$failed of ${vectors.length} FAILED');
}

bool _eq(List<int> a, List<int> b) {
  if (a.length != b.length) return false;
  for (var i = 0; i < a.length; i++) {
    if (a[i] != b[i]) return false;
  }
  return true;
}