stdlib/public/core/SipHash.swift.gyb

//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
/// This file implements SipHash-2-4 and SipHash-1-3
/// (https://131002.net/siphash/).
///
/// This file is based on the reference C implementation, which was released
/// to public domain by:
///
/// * Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
/// * Daniel J. Bernstein <djb@cr.yp.to>
//===----------------------------------------------------------------------===//

%{
# Number of bits in the Builtin.Word type
word_bits = int(CMAKE_SIZEOF_VOID_P) * 8
}%

@_fixed_layout // FIXME(sil-serialize-all)
@_versioned
internal enum _SipHashDetail {
  @_versioned
  @inline(__always)
  internal static func _rotate(_ x: UInt64, leftBy amount: UInt64) -> UInt64 {
    return (x &<< amount) | (x &>> (64 - amount))
  }

  @_versioned
  @inline(__always)
  internal static func _sipRound(
    v0: inout UInt64,
    v1: inout UInt64,
    v2: inout UInt64,
    v3: inout UInt64
  ) {
    v0 = v0 &+ v1
    v1 = _rotate(v1, leftBy: 13)
    v1 ^= v0
    v0 = _rotate(v0, leftBy: 32)
    v2 = v2 &+ v3
    v3 = _rotate(v3, leftBy: 16)
    v3 ^= v2
    v0 = v0 &+ v3
    v3 = _rotate(v3, leftBy: 21)
    v3 ^= v0
    v2 = v2 &+ v1
    v1 = _rotate(v1, leftBy: 17)
    v1 ^= v2
    v2 = _rotate(v2, leftBy: 32)
  }
}

% for (c_rounds, d_rounds) in [(2, 4), (1, 3)]:
%   Self = '_SipHash{}{}'.format(c_rounds, d_rounds)

@_fixed_layout // FIXME(sil-serialize-all)
public // @testable
struct ${Self} {
  // "somepseudorandomlygeneratedbytes"
  @_versioned
  internal var v0: UInt64 = 0x736f6d6570736575

  @_versioned
  internal var v1: UInt64 = 0x646f72616e646f6d

  @_versioned
  internal var v2: UInt64 = 0x6c7967656e657261

  @_versioned
  internal var v3: UInt64 = 0x7465646279746573

  /// This value holds the byte count and the pending bytes that haven't been
  /// compressed yet, in the format that the finalization step needs. (The least
  /// significant 56 bits hold the trailing bytes, while the most significant 8
  /// bits hold the count of bytes appended so far, mod 256.)
  @_versioned
  internal var tailAndByteCount: UInt64 = 0

  @inline(__always)
  public init(key: (UInt64, UInt64)) {
    v3 ^= key.1
    v2 ^= key.0
    v1 ^= key.1
    v0 ^= key.0
  }

  @_versioned
  internal var byteCount: UInt64 {
    @inline(__always)
    get {
      return tailAndByteCount &>> 56
    }
  }

  @_versioned
  internal var tail: UInt64 {
    @inline(__always)
    get {
      return tailAndByteCount & ~(0xFF &<< 56)
    }
  }

  @inline(__always)
  @_versioned
  internal mutating func _compress(_ m: UInt64) {
    v3 ^= m
    for _ in 0..<${c_rounds} {
      _SipHashDetail._sipRound(v0: &v0, v1: &v1, v2: &v2, v3: &v3)
    }
    v0 ^= m
  }

  @inline(__always)
  public mutating func append(_ value: Int) {
    append(UInt(bitPattern: value))
  }

  @inline(__always)
  public mutating func append(_ value: UInt) {
    % if word_bits == 64:
    append(UInt64(_truncatingBits: value._lowWord))
    % elif word_bits == 32:
    append(UInt32(_truncatingBits: value._lowWord))
    % else:
    fatalError("Unsupported word width")
    % end
  }

  @inline(__always)
  public mutating func append(_ value: Int32) {
    append(UInt32(bitPattern: value))
  }

  @inline(__always)
  public mutating func append(_ value: UInt32) {
    let m = UInt64(_truncatingBits: value._lowWord)
    if byteCount & 4 == 0 {
      _sanityCheck(byteCount & 7 == 0 && tail == 0)
      tailAndByteCount = (tailAndByteCount | m) &+ (4 &<< 56)
    } else {
      _sanityCheck(byteCount & 3 == 0)
      _compress((m &<< 32) | tail)
      tailAndByteCount = (byteCount &+ 4) &<< 56
    }
  }

  @inline(__always)
  public mutating func append(_ value: Int64) {
    append(UInt64(bitPattern: value))
  }

  @inline(__always)
  public mutating func append(_ m: UInt64) {
    if byteCount & 4 == 0 {
      _sanityCheck(byteCount & 7 == 0 && tail == 0)
      _compress(m)
      tailAndByteCount = tailAndByteCount &+ (8 &<< 56)
    } else {
      _sanityCheck(byteCount & 3 == 0)
      _compress((m &<< 32) | tail)
      tailAndByteCount = ((byteCount &+ 8) &<< 56) | (m &>> 32)
    }
  }

  @inline(__always)
  public mutating func finalize(
    tailBytes: UInt64,
    tailByteCount: Int
  ) -> UInt64 {
    _sanityCheck(tailByteCount >= 0)
    _sanityCheck(tailByteCount < 8 - (byteCount & 7))
    _sanityCheck(tailBytes >> (tailByteCount << 3) == 0)
    let count = UInt64(_truncatingBits: tailByteCount._lowWord)
    let currentByteCount = byteCount & 7
    tailAndByteCount |= (tailBytes &<< (currentByteCount &<< 3))
    tailAndByteCount = tailAndByteCount &+ (count &<< 56)
    return finalize()
  }

  @inline(__always)
  public mutating func finalize() -> UInt64 {
    _compress(tailAndByteCount)

    v2 ^= 0xff

    for _ in 0..<${d_rounds} {
      _SipHashDetail._sipRound(v0: &v0, v1: &v1, v2: &v2, v3: &v3)
    }

    return (v0 ^ v1 ^ v2 ^ v3)
  }
}
% end