Integers.swift.gyb

//===--- Integers.swift.gyb -----------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2015 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
// RUN: rm -rf %t && mkdir -p %t && %S/../../utils/gyb -DWORD_BITS=%target-ptrsize %s -o %t/out.swift
// RUN: %S/../../utils/line-directive %t/out.swift -- %target-build-swift -parse-stdlib %t/out.swift -o %t/a.out
// RUN: %S/../../utils/line-directive %t/out.swift -- %target-run %t/a.out
// REQUIRES: executable_test
import Swift

%{
#
# Utility code for later in this template
#
from math import log
from string import maketrans
  
# Number of bits in the Builtin.Word type
word_bits = int(WORD_BITS) # int(CMAKE_SIZEOF_VOID_P) * 8
  
# Number of bits in integer literals.
builtinIntLiteralBits = 2048
IntLiteral = 'Int%s' % builtinIntLiteralBits

# 32-bit iOS simulator doesn't have Int128 support, so we stop at
# double-word.  When we've implemented the arithmetic algorithms
# for bignum, we can go further.
fixedBitWidths = [2**x for x in range(3, 8) if 2**x <= 2*word_bits]
minFixedBits = fixedBitWidths[0]
maxFixedBits = fixedBitWidths[-1]
  
def capitalize(s):
  return s[:1].upper() + s[1:]

class struct(object):
  def __init__(self, **kw):
    self.__dict__ = kw
  def __repr__(self):
    return 'struct(%r)' % self.__dict__

binaryArithmetic = [
    struct(operator='+', name='add', llvmName='add', kind='+'),
    struct(operator='-', name='subtract', llvmName='sub', kind='+'),
    struct(operator='*', name='multiply', llvmName='mul', kind='*'),
    struct(operator='/', name='divideBy', llvmName='div', kind='/'),
    struct(
      operator='%', name='remainderWhenDividedBy', llvmName='rem', kind='/')
  ]


binaryBitwise = [
    struct(operator='&', name='and'),
    struct(operator='|', name='or'),
    struct(operator='^', name='xor')]

maskingShifts = [
    struct(
      operator='&>>', nonMaskingOperator='>>',
      name='maskingShiftRight', llvmName=lambda s:['lshr','ashr'][s]),
    struct(
      operator='&<<', nonMaskingOperator='<<',
      name='maskingShiftLeft', llvmName=lambda _: 'shl'),
  ]
}%

//===--- Bits for the Stdlib ----------------------------------------------===//

extension Bool {
  @_transparent
  public init(_ value: Builtin.Int1) {
    self.init(_builtinBooleanLiteral: value)
  }
  
  @_transparent
  // Renamed from _value to __value, because the deserializer crashes
  // if stdlib is compiled with -sil-serialize-all (rdar://problem/23620491).
  // TODO: rename it back to _value when the deserializer is fixed.
  public var __value: Builtin.Int1 {
    return Builtin.trunc_Int${word_bits}_Int1((self ? 1 : 0)._value)
  }
}

// This should go in the stdlib separately, probably.
extension IntegerLiteralConvertible
  where Self : _BuiltinIntegerLiteralConvertible {
  /// Create an instance initialized to `value`.
  @_transparent
  public init(integerLiteral value: Self) {
    self = value
  }
}

infix operator &<< { associativity none precedence 160 }
infix operator &<<= { associativity right precedence 90 assignment }
infix operator &>> { associativity none precedence 160 }
infix operator &>>= { associativity right precedence 90 assignment }

@_transparent
public func _assertCond(
  @autoclosure condition: () -> Bool,
  @autoclosure _ message: ()->String,
  file: StaticString = __FILE__, line: UInt = __LINE__) {
  let ok = condition()
  if _isDebugAssertConfiguration() {
    precondition(ok, message, file: file, line: line)
  }
  Builtin.condfail((!ok).__value)
}

//===--- Prototype Implementation -----------------------------------------===//

//===----------------------------------------------------------------------===//
//===--- ArithmeticType ---------------------------------------------------===//
//===----------------------------------------------------------------------===//
public protocol ArithmeticType {
  /// Initialize to zero
  init()
  
% for x in binaryArithmetic:
  // defaulted below
  @warn_unused_result
  func ${x.operator}(lhs: Self, rhs: Self) -> Self

  // defaulted below
  func ${x.operator}=(inout lhs: Self, rhs: Self)

  // implementation hook
  mutating func ${x.name}InPlace(rhs: Self)
% end

  /// defaulted below
  prefix func -(lhs: Self) -> Self
}

% for x in binaryArithmetic:
@_transparent
@warn_unused_result
public func ${x.operator} <T: ArithmeticType>(lhs: T, rhs: T) -> T {
  var lhs = lhs
  lhs.${x.name}InPlace(rhs)
  return lhs
}

@_transparent
public func ${x.operator}= <T: ArithmeticType>(inout lhs: T, rhs: T) {
  lhs.${x.name}InPlace(rhs)
}
% end

@_transparent
@warn_unused_result
public prefix func -<T: ArithmeticType>(x: T) -> T {
  return T() - x
}

//===----------------------------------------------------------------------===//
//===--- IntegerType ------------------------------------------------------===//
//===----------------------------------------------------------------------===//
public typealias Word = Int${word_bits}
public typealias UWord = UInt${word_bits}

public protocol IntegerType
  : Comparable, ArithmeticType, 
    IntegerLiteralConvertible, CustomStringConvertible  {

  // Dispatching through these puts less stress on the user reading
  // the interface and error messages (and on the type checker) than
  // does having many operator overloads.
  @warn_unused_result
  func isEqualTo(rhs: Self) -> Bool
  
  @warn_unused_result
  func isLessThan(rhs: Self) -> Bool

  /// The number of bits required to represent our value.  If `self`
  /// is negative, returns the index of the least significant bit of
  /// our representation such that all more-significant bits are 1.
  /// Has the value -1 if `self` is 0.
  var mostSignificantBit: Word { get }
  
  @warn_unused_result
  func word(n: Word) -> Word

  init<T : IntegerType>(_ source: T)
  
  init<T : IntegerType>(extendingOrTruncating source: T)  
}

//===--- Homogeneous comparison -------------------------------------------===//
@_transparent
@warn_unused_result
public func == <T : IntegerType>(lhs:T, rhs: T) -> Bool {
  return lhs.isEqualTo(rhs)
}

@_transparent
@warn_unused_result
public func < <T : IntegerType>(lhs: T, rhs: T) -> Bool {
  return lhs.isLessThan(rhs)
}

//===--- Heterogeneous comparison -----------------------------------------===//
@_transparent
@warn_unused_result
public func == <T : IntegerType, U : IntegerType>(lhs:T, rhs: U) -> Bool {
  return (lhs > 0) == (rhs > 0)
    && T(extendingOrTruncating: rhs) == lhs
    && U(extendingOrTruncating: lhs) == rhs
}

@_transparent
@warn_unused_result
public func != <T : IntegerType, U : IntegerType>(lhs:T, rhs: U) -> Bool {
  return !(lhs == rhs)
}

@_transparent
@warn_unused_result
public func < <T : IntegerType, U : IntegerType>(lhs: T, rhs: U) -> Bool {
  let lhsSign = lhs < 0 ? -1 : lhs > 0 ? 1 : 0
  let rhsSign = rhs < 0 ? -1 : rhs > 0 ? 1 : 0
  if lhsSign != rhsSign { return lhsSign < rhsSign }

  // if we get here, lhs and rhs have the same sign.  If they're
  // negative, then T and U are both signed types, and one of them can
  // represent values of the other type.  Otherwise, lhs and rhs are
  // positive, and one of T, U may be signed and the other unsigned.
  // In this case, we can conceptually subtract 1 from the bitWidth of
  // any signed type, and either the resulting bitWidths are the same
  // or one can represent every value of the other.
  
  let rT = T(extendingOrTruncating: rhs)

  // Can we round-trip rhs through T?
  if U(extendingOrTruncating: rT) == rhs {
    return lhs < rT
  }

  return U(extendingOrTruncating: lhs) < rhs
}

@inline(__always)
@warn_unused_result
public func <= <T : IntegerType, U : IntegerType>(lhs: T, rhs: U) -> Bool {
  return !(rhs < lhs)
}

@inline(__always)
@warn_unused_result
public func >= <T : IntegerType, U : IntegerType>(lhs: T, rhs: U) -> Bool {
  return !(lhs < rhs)
}

@inline(__always)
@warn_unused_result
public func > <T : IntegerType, U : IntegerType>(lhs: T, rhs: U) -> Bool {
  return rhs < lhs
}

//===--- Ambiguity breakers -----------------------------------------------===//
// These two versions of the operators are not ordered with respect to
// one another:
//
//     <T : Comparable>(T,T) -> Bool 
//     <T : IntegerType, U : IntegerType>(T,U) -> Bool 
//
// so we define:
//
//     <T : IntegerType>(T,T) -> Bool

@inline(__always)
@warn_unused_result
public func <= <T : IntegerType>(lhs: T, rhs: T) -> Bool {
  return !(rhs < lhs)
}

@inline(__always)
@warn_unused_result
public func >= <T : IntegerType>(lhs: T, rhs: T) -> Bool {
  return !(lhs < rhs)
}

@inline(__always)
@warn_unused_result
public func > <T : IntegerType>(lhs: T, rhs: T) -> Bool {
  return rhs < lhs
}

//===----------------------------------------------------------------------===//
//===--- FixedWidthIntegerType --------------------------------------------===//
//===----------------------------------------------------------------------===//
public enum ArithmeticOverflow { case None, Overflow }

public protocol FixedWidthIntegerType : IntegerType {
  static var bitWidth : Word { get }

% for x in binaryArithmetic:
%{
comment = '''
  /// Return a pair consisting of `self` ${x.operator} `rhs`,
  /// truncated to fit if necessary, and a flag indicating whether an
  /// arithmetic overflow occurred.''' + ('''
  ///
  /// Requires: `rhs != 0`''' if x.kind == '/' else '')
}%
${comment}
  @warn_unused_result
  func ${x.name}WithOverflow(
    rhs: Self
  ) -> (partialValue: Self, overflow: ArithmeticOverflow)
  % end
  
  static var max: Self { get }
  
  static var min: Self { get }

% for x in binaryBitwise + maskingShifts:
  @warn_unused_result
  func ${x.name}(rhs: Self) -> Self
% end

  @warn_unused_result
  func countLeadingZeros() -> Word

  init(_truncatingBits bits: Word)

  var _lowWord: Word { get }
}

% for x in binaryBitwise:
@warn_unused_result
@_transparent
public func ${x.operator} <T: FixedWidthIntegerType>(lhs: T, rhs: T) -> T {
  return lhs.${x.name}(rhs)
}

@_transparent
public func ${x.operator}= <T: FixedWidthIntegerType>(inout lhs: T, rhs: T) {
  lhs = lhs.${x.name}(rhs)
}
% end

% for x in maskingShifts:
@warn_unused_result
@_transparent
public func ${x.operator} <T: FixedWidthIntegerType>(lhs: T, rhs: T) -> T {
  return lhs.${x.name}(rhs)
}

@_transparent
public func ${x.operator}= <T: FixedWidthIntegerType>(inout lhs: T, rhs: T) {
  lhs = lhs ${x.operator} rhs
}

@warn_unused_result
@_transparent
public func ${x.operator} <
  T: FixedWidthIntegerType, U: IntegerType
>(lhs: T, rhs: U) -> T {
  return lhs.${x.name}(T(extendingOrTruncating: rhs))
}

@_transparent
public func ${x.operator}= <
  T: FixedWidthIntegerType, U: IntegerType
>(inout lhs: T, rhs: U) {
  lhs = lhs ${x.operator} rhs
}

@warn_unused_result
@_transparent
public func ${x.nonMaskingOperator} <
  T: FixedWidthIntegerType, U: IntegerType
>(lhs: T, rhs: U) -> T {
  let shift = rhs < -T.bitWidth ? -T.bitWidth
            : rhs > T.bitWidth ? T.bitWidth 
            : Word(rhs)
  return lhs ${x.nonMaskingOperator} shift
}

// "Smart shift", supporting overshifts and negative shifts

@warn_unused_result
@_transparent
public func ${x.nonMaskingOperator} <
  T: FixedWidthIntegerType
>(lhs: T, rhs: Word) -> T {
  let overshiftR = T.min < 0 ? lhs &>> (T.bitWidth - 1) : 0
  let overshiftL: T = 0
  if _fastPath(rhs >= 0) {
    if _fastPath(rhs < T.bitWidth) {
      return lhs.${x.name}(T(extendingOrTruncating: rhs))
    }
    return overshift${'LR'['R' in x.name]}
  }
  
  if _slowPath(rhs <= -T.bitWidth) {
    return overshift${'RL'['R' in x.name]}
  }
  return lhs ${x.operator.translate(maketrans('<>', '><'))} -rhs
}

@_transparent
public func ${x.nonMaskingOperator}= <
  T: FixedWidthIntegerType
>(inout lhs: T, rhs: T) {
  lhs = lhs ${x.nonMaskingOperator} rhs
}

@_transparent
public func ${x.nonMaskingOperator}= <
  T: FixedWidthIntegerType, U: IntegerType
>(inout lhs: T, rhs: U) {
  lhs = lhs ${x.nonMaskingOperator} rhs
}
% end

@warn_unused_result
@inline(__always)
public prefix func ~ <T: FixedWidthIntegerType>(x: T) -> T {
  return 0 &- x &- 1
}

extension FixedWidthIntegerType {
  public init<Other: IntegerType>(clamping source: Other) {
    if _slowPath(source < Self.min) {
      self = Self.min
    }
    else if _slowPath(source > Self.max) {
      self = Self.max
    }
    else { self = Self(extendingOrTruncating: source) }
  }
  
% for x in binaryArithmetic:
  @_transparent
  public mutating func ${x.name}InPlace(rhs: Self) {
    let (result, overflow) = self.${x.name}WithOverflow(rhs)
    _assertCond(overflow == .None, "overflow in ${x.name}")
    self = result
  }

  /// Return `self ${x.operator} rhs`.  If an arithmetic overflow
  /// occurs, the behavior is undefined.
  ///
  /// Note: use this function to avoid the cost of overflow checking
  /// when you are sure that the operation won't overflow.
  @warn_unused_result
  @_transparent
  public func unsafe${capitalize(x.name)}(rhs: Self) -> Self {
    let (result, overflow) = self.${x.name}WithOverflow(rhs)
    
    if (overflow != .None) {
      if (_isDebugAssertConfiguration()) {
        _preconditionFailure("overflow in unsafe${capitalize(x.name)}")
      }
      else {
        Builtin.conditionallyUnreachable()
      }
    }
    return result
  }
% end

  @_transparent
  public init() {
    self = 0
  }

  @_transparent
  public init<T : IntegerType>(extendingOrTruncating source: T) {
    if Self.bitWidth <= ${word_bits} {
      self = Self.init(_truncatingBits: source.word(0))
    }
    else {
      var result: Self = source < 0 ? ~0 : 0
      // start with the most significant word
      var n = source.mostSignificantBit / ${word_bits}
      while n >= 0 {
        // masking is OK here because this we have already ensured
        // that Self.bitWidth > ${word_bits}.  Not masking results in
        // infinite recursion.
        result &<<= ${word_bits}
        result |= Self(_truncatingBits: source.word(n))
        n -= 1
      }
      
      self = result
    }
  }

  @_transparent
  public func word(n: Word) -> Word {
    var n = n
    _precondition(n >= 0, "Negative word index")
    var x = self
    while n > 0 {
      // Using a masking shift here allows us to make more things
      // transparent, but this would have the wrong semantics if the
      // masking ever had an effect.
      _sanityCheck(Self.bitWidth > ${word_bits})
      x &>>= ${word_bits}
      n -= 1
    }
    return x._lowWord
  }

  @_transparent
  public // transparent
  static var _highBitIndex: Self {
    return Self.init(_truncatingBits: Self.bitWidth - 1)
  }
}

% for x in binaryArithmetic:
%   if x.kind != '/':
@warn_unused_result
public func &${x.operator} <T: FixedWidthIntegerType>(lhs: T, rhs: T) -> T {
  return lhs.${x.name}WithOverflow(rhs).partialValue
}
%   end
% end

//===----------------------------------------------------------------------===//
//===--- UnsignedIntegerType ----------------------------------------------===//
//===----------------------------------------------------------------------===//
public protocol UnsignedIntegerType : IntegerType {
}
extension UnsignedIntegerType {
  public var description: String {
    if self == 0 {
      return "0"
    }
    
    let ascii0 = 48
    var buf: [UnicodeScalar] = []

    var x = self
    repeat {
      let r = x % 10
      x /= 10
      buf.append(
        UnicodeScalar(
          ascii0 + Swift.Int(Word(extendingOrTruncating: r)._storage)))
    }
    while x != 0
    return String(buf.reverse().lazy.map { Character($0) })
  }
}

extension UnsignedIntegerType where Self : FixedWidthIntegerType {
  @_transparent
  public init<T : IntegerType>(_ source: T) {
    _assertCond(
      source >= 0, "negative value \(source) not representable by \(Self.self)")
    let requiredBits = source.mostSignificantBit + 1
    _assertCond(
      requiredBits <= Self.bitWidth,
      "\(Self.self) cannot store all \(requiredBits)  bits "
      + "needed for unsigned representation of \(source)")
    self.init(extendingOrTruncating: source)
  }
  
  @_transparent
  public static var max: Self {
    return ~0
  }
  
  @_transparent
  public static var min: Self {
    return 0
  }

  @_transparent
  public var mostSignificantBit: Word {
    return Self.bitWidth - 1 - self.countLeadingZeros()
  }
}

//===----------------------------------------------------------------------===//
//===--- SignedIntegerType ------------------------------------------------===//
//===----------------------------------------------------------------------===//

public protocol SignedIntegerType : IntegerType {
  typealias AbsoluteValue : IntegerType
  var absoluteValue: AbsoluteValue { get }
}

extension SignedIntegerType {
  public var description: String {
    let base = String(absoluteValue)
    return self < 0 ? "-" + base : base
  }
}

extension SignedIntegerType where Self : FixedWidthIntegerType {
  @_transparent
  public init<T : IntegerType>(_ source: T) {
    let requiredBits = source.mostSignificantBit + (source >= 0 ? 2 : 1)
    _assertCond(
      requiredBits <= Self.bitWidth,
      "\(Self.self) cannot store all \(requiredBits) bits "
      + "needed for signed representation of \(source)")
    self.init(extendingOrTruncating: source)
  }
  
  @_transparent
  public static var max: Self {
    return ~min
  }
  
  @_transparent
  public static var min: Self {
    return -1 &<< Self._highBitIndex
  }

  @_transparent
  public var mostSignificantBit: Word {
    let x = self < 0 ? ~self : self
    return Self.bitWidth - 1 - x.countLeadingZeros()
  }
}

//===--- Concrete FixedWidthIntegers --------------------------------------===//


% for bits in fixedBitWidths:
%   for signed in True, False:
%     Self = ('Int%d' if signed else 'UInt%d') % bits
%     Unsigned = 'Signed' if signed else 'Unsigned'
%     u = 's' if signed else 'u'
%     z = 's' if signed else 'z'
public struct ${Self}
  : FixedWidthIntegerType, ${Unsigned}IntegerType,
    _BuiltinIntegerLiteralConvertible {  

  @_transparent
  public init(_builtinIntegerLiteral x: _MaxBuiltinIntegerType) {
    _storage = Builtin.truncOrBitCast_${IntLiteral}_Int${bits}(x)
    Builtin.condfail(
      Builtin.cmp_ne_${IntLiteral}(
        Builtin.${'s' if signed else 'z'}extOrBitCast_Int${bits}_${IntLiteral}(
          _storage), x))
  }

  @warn_unused_result
  public func isEqualTo(rhs: ${Self}) -> Bool {
    return Bool(Builtin.cmp_eq_Int${bits}(_storage, rhs._storage))
  }
  
  @warn_unused_result
  public func isLessThan(rhs: ${Self}) -> Bool {
    return Bool(Builtin.cmp_${u}lt_Int${bits}(_storage, rhs._storage))
  }

%       for x in binaryArithmetic:
  /// Return a pair consisting of `self` ${x.operator} `rhs`,
  /// truncated to fit if necessary, and a flag indicating whether an
  /// arithmetic overflow occurred.
  @warn_unused_result
  @_transparent
  public func ${x.name}WithOverflow(
    rhs: ${Self}
  ) -> (partialValue: ${Self}, overflow: ArithmeticOverflow) {
    
%         if x.kind == '/':
    // No LLVM primitives for checking overflow of division
    // operations, so we check manually.
    if _slowPath(
      rhs == 0
      ${'|| self == %s.min && rhs == -1' % Self if signed else ''}
    ) {
      return (partialValue: self, overflow: .Overflow)
    }
    
    let (newStorage, overflow) = (
      Builtin.${u}${x.llvmName}_Int${bits}(self._storage, rhs._storage),
      false.__value)

%         else:

    let (newStorage, overflow)
    = Builtin.${u}${x.llvmName}_with_overflow_Int${bits}(
      self._storage, rhs._storage, false.__value)
%         end

    return (
      partialValue: ${Self}(newStorage),
      overflow: Bool(overflow) ? .Overflow : .None)
  }
%       end

  @_transparent
  public init(_ _storage: Builtin.Int${bits}) {
    self._storage = _storage
  }

% for x in binaryBitwise:
  @warn_unused_result
  @_transparent
  public func ${x.name}(rhs: ${Self}) -> ${Self} {
    return ${Self}(
      Builtin.${x.name}_Int${bits}(self._storage, rhs._storage))
  }
% end

% for x in maskingShifts:
  @warn_unused_result
  @_transparent
  public func ${x.name}(rhs: ${Self}) -> ${Self} {
    let rhs_ = rhs & ${Self}._highBitIndex
    return ${Self}(
      Builtin.${x.llvmName(signed)}_Int${bits}(self._storage, rhs_._storage))
  }
% end

  @_transparent
  public static var bitWidth : Word { return ${bits} }

  @_transparent
  @warn_unused_result
  public func countLeadingZeros() -> Word {
    return ${Self}(
      Builtin.int_ctlz_Int${bits}(self._storage, false.__value))._lowWord
  }
  
  @_transparent
  public // transparent
  var _lowWord: Word {
    % truncOrExt = z + 'ext' if bits <= word_bits else 'trunc'
    return Word(
      Builtin.${truncOrExt}OrBitCast_Int${bits}_Int${word_bits}(_storage)
    )
  }
  
  @_transparent
  public // transparent
  var _lowUnsignedWord: Word {
    % truncOrExt = z + 'ext' if bits <= word_bits else 'trunc'
    return Word(
      Builtin.${truncOrExt}OrBitCast_Int${bits}_Int${word_bits}(_storage)
    )
  }
  
  @_transparent
  public // transparent
  init(_truncatingBits bits: Word) {
    % truncOrExt = 'zext' if bits > word_bits else 'trunc'
    self.init(
      Builtin.${truncOrExt}OrBitCast_Int${word_bits}_Int${bits}(bits._storage))
  }

% if signed:
  @_transparent
  public var absoluteValue: U${Self} {
    let base = U${Self}(_storage)
    return self < 0 ? ~base + 1 : base
  }
% end
  
  public var _storage: Builtin.Int${bits}
}

%   end
% end


//===--- Tests ------------------------------------------------------------===//
typealias DWord = Int${word_bits*2}
typealias UDWord = UInt${word_bits*2}

import StdlibUnittest
var tests = TestSuite("Integers")

tests.test("Literals") {
  // Testing against the official Int types so as not to depend on
  // unimplemented stuff.
  let a: UInt8 = 0b1_0_11_0_111
  expectEqual(unsafeBitCast(a, Swift.UInt8.self), 0b1_0_11_0_111)

  let b: Int16 = 183
  expectEqual(unsafeBitCast(b, Swift.Int16.self), 0b1_0_11_0_111)

  let c: Int16 = -183
  expectEqual(unsafeBitCast(c, Swift.Int16.self), -183)

  let d: Int8 = 127
  expectEqual(unsafeBitCast(d, Swift.Int8.self), 127)

  let e: UInt8 = 255
  expectEqual(unsafeBitCast(e, Swift.UInt8.self), 255)
}

tests.test("Signed Literal Trap") {
  expectCrashLater()
  let _: Int8 = 128
}

tests.test("Unsigned Literal Trap") {
  expectCrashLater()
  let _: UInt8 = 256
}

tests.test("Equality") {
  expectEqual(183 as UInt8, 183)
  expectNotEqual(183 as UInt8, 184)
  
  expectEqual(49 as Int8, 49)
  expectNotEqual(-49 as Int8, 49)
}

func indexOrder<T: RandomAccessIndexType>(x: T, y: T)
  -> ExpectedComparisonResult {
  return x < y ? .LT : x > y ? .GT : .EQ
}

tests.test("Ordering") {
  checkComparable([127, 183, 184, 255] as [UInt8], oracle: indexOrder)
  checkComparable([-128, -1, 83, 84, 127] as [Int8], oracle: indexOrder)
  checkComparable([127, 183, 184, 255, 65535] as [UInt16], oracle: indexOrder)
  checkComparable([-32768, -32767, 83, 84, 32767] as [Int16], oracle: indexOrder)
}

tests.test("Simple-Arithmetic") {
  expectEqual(1 as Int8 + 2, 3)
  expectEqual(1 as Int8 - 2, -1)
  expectEqual(-5 as Int8 + 11, 6)
  expectEqual(3 as Int8 * 4, 12)
  expectEqual(4 as Int8 * -7, -28)
  expectEqual(-4 as Int8 * -7, 28)
  expectEqual(5 as Int8 / 2, 2)
  expectEqual(6 as Int8 / 2, 3)
  expectEqual(7 as Int8 / 2, 3)
  expectEqual(5 as Int8 % 3, 2)
  expectEqual(6 as Int8 % 3, 0)
  expectEqual(7 as Int8 % 3, 1)
}

tests.test("Simple-Bitwise") {
  expectEqual(0b100_1001 as Int8 >> 1, 0b10_0100)
  expectEqual(-0b100_1001 as Int8 >> 1, -0b10_0101)
  expectEqual(0b1011_0111 as UInt8 >> 1, 0b0101_1011)

  expectEqual(0b100_1001 as Int8 >> 1, 0b10_0100)
  expectEqual(-0b100_1001 as Int8 >> 1, -0b10_0101)
  expectEqual(0b1011_0111 as UInt8 >> 1, 0b0101_1011)
  
  expectEqual(0b1011_0111 as UInt8 & 0b0110_1110, 0b0010_0110)
  expectEqual(0b1011_0111 as UInt8 | 0b0110_1110, 0xFF)
  expectEqual(0b1011_0111 as UInt8 ^ 0b0110_1110, 0b1101_1001)
}

tests.test("MinMax") {
  expectEqual(255, UInt8.max)
  expectEqual(0, UInt8.min)
  expectEqual(127, Int8.max)
  expectEqual(-128, Int8.min)
}

tests.test("CountLeadingZeros") {
  expectEqual(0, UInt8.max.countLeadingZeros())
  expectEqual(8, UInt8.min.countLeadingZeros())
  expectEqual(1, Int8.max.countLeadingZeros())
  expectEqual(0, Int8.min.countLeadingZeros())
}

tests.test("mostSignificantBit") {
  expectEqual(7, UInt8.max.mostSignificantBit)
  expectEqual(-1, UInt8.min.mostSignificantBit)
  expectEqual(6, Int8.max.mostSignificantBit)
  expectEqual(6, Int8.min.mostSignificantBit)
}

tests.test("Conversion8to16") {
  expectEqual(255, UInt16(UInt8.max))
  expectEqual(255, Int16(UInt8.max))
  expectEqual(0, UInt16(UInt8.min))
  expectEqual(0, Int16(UInt8.min))
  expectEqual(127, Int16(Int8.max))
  let negativeValue = Int8.min
  expectCrashLater()
  _ = UInt16(negativeValue)
}


tests.test("Conversion16to8") {
  expectEqual(255, UInt8(255 as UInt16))
  expectEqual(255, UInt8(255 as Int16))
  
  expectEqual(0, UInt8(0 as UInt16))
  expectEqual(0, UInt8(0 as Int16))
  
  expectEqual(127, Int8(127 as UInt16))
  expectEqual(127, Int8(127 as Int16))
  
  expectEqual(-128, Int8(-128 as Int16))
  let tooLarge: UInt16 = 128
  expectCrashLater()
  _ = Int8(tooLarge)
}

tests.test("Conversion16to8a") {
  let tooLarge: Int16 = 128
  expectCrashLater()
  _ = Int8(tooLarge)
}

tests.test("Conversion16to8b") {
  let tooLarge: Int16 = 256
  expectCrashLater()
  _ = UInt8(tooLarge)
}

tests.test("Conversion16to8c") {
  let tooLarge: UInt16 = 256
  expectCrashLater()
  _ = UInt8(tooLarge)
}

tests.test("ConversionWordToDWord") {
  expectEqual(1 << ${word_bits} - 1, UDWord(UWord.max))
  expectEqual(1 << ${word_bits} - 1, DWord(UWord.max))
  expectEqual(0, UDWord(UWord.min))
  expectEqual(0, DWord(UWord.min))
  expectEqual(1 << ${word_bits-1} - 1, DWord(Word.max))
  let negativeValue = Word.min
  expectCrashLater()
  _ = UDWord(negativeValue)
}

tests.test("ConversionDWordToWord") {
  expectEqual(~0, UWord(1 << ${word_bits} - 1 as UDWord))
  expectEqual(~0, UWord(1 << ${word_bits} - 1 as DWord))
  
  expectEqual(0, UWord(0 as UDWord))
  expectEqual(0, UWord(0 as DWord))
  
  expectEqual(Word.max, Word(1 << ${word_bits-1} - 1 as UDWord))
  expectEqual(Word.max, Word(1 << ${word_bits-1} - 1 as DWord))
  
  expectEqual(Word.min, Word(-1 << ${word_bits-1} as DWord))
  let tooLarge: UDWord = 1 << ${word_bits-1}
  expectCrashLater()
  _ = Word(tooLarge)
}

tests.test("ConversionDWordToWordA") {
  let tooLarge: DWord = 1 << ${word_bits}
  expectCrashLater()
  _ = Word(tooLarge)
}

tests.test("ConversionDWordToWordB") {
  let tooLarge: DWord = 1 << ${word_bits}
  expectCrashLater()
  _ = UWord(tooLarge)
}

tests.test("ConversionDWordToWordC") {
  let tooLarge: UDWord = 1 << ${word_bits}
  expectCrashLater()
  _ = UWord(tooLarge)
}

tests.test("extendingOrTruncating") {
  
  expectEqual(-2, Int8(extendingOrTruncating: UInt8.max - 1))
  expectEqual(3, Int8(extendingOrTruncating: 3 as UInt8))
  expectEqual(UInt8.max - 1, UInt8(extendingOrTruncating: -2 as Int8))
  expectEqual(3, UInt8(extendingOrTruncating: 3 as Int8))

  expectEqual(-2, DWord(extendingOrTruncating: UDWord.max - 1))
  expectEqual(3, DWord(extendingOrTruncating: 3 as UDWord))
  expectEqual(UDWord.max - 1, UDWord(extendingOrTruncating: -2 as DWord))
  expectEqual(3, UDWord(extendingOrTruncating: 3 as DWord))
  
  expectEqual(-2, Int32(extendingOrTruncating: -2 as Int8))
  expectEqual(3, Int32(extendingOrTruncating: 3 as Int8))
  expectEqual(127, Int32(extendingOrTruncating: 127 as UInt8))
  expectEqual(129, Int32(extendingOrTruncating: 129 as UInt8))
  expectEqual((1 << 31 - 1) << 1, UInt32(extendingOrTruncating: -2 as Int8))
  expectEqual(3, UInt32(extendingOrTruncating: 3 as Int8))
  expectEqual(128, UInt32(extendingOrTruncating: 128 as UInt8))
  expectEqual(129, UInt32(extendingOrTruncating: 129 as UInt8))

  expectEqual(-2, DWord(extendingOrTruncating: -2 as Int8))
  expectEqual(3, DWord(extendingOrTruncating: 3 as Int8))
  expectEqual(127, DWord(extendingOrTruncating: 127 as UInt8))
  expectEqual(129, DWord(extendingOrTruncating: 129 as UInt8))
  expectEqual(
    (1 << ${word_bits*2-1} - 1) << 1,
    UDWord(extendingOrTruncating: -2 as Int8))
  expectEqual(3, UDWord(extendingOrTruncating: 3 as Int8))
  expectEqual(128, UDWord(extendingOrTruncating: 128 as UInt8))
  expectEqual(129, UDWord(extendingOrTruncating: 129 as UInt8))
  
  expectEqual(-2, Int8(extendingOrTruncating: -2 as DWord))
  expectEqual(-2, Int8(extendingOrTruncating: -1 << 67 - 2 as DWord))
  expectEqual(127, Int8(extendingOrTruncating: 127 as UDWord))
  expectEqual(-127, Int8(extendingOrTruncating: 129 as UDWord))
  expectEqual(0b1111_1100, UInt8(extendingOrTruncating: -4 as DWord))
  expectEqual(0b1111_1100, UInt8(extendingOrTruncating: -1 << 67 - 4 as DWord))
  expectEqual(128, UInt8(extendingOrTruncating: 128 + 1024 as UDWord))
  expectEqual(129, UInt8(extendingOrTruncating: 129 + 1024 as UDWord))
}  

tests.test("HeterogeneousEquality") {
  expectTrue(-1 as DWord != UDWord.max)
  expectTrue(DWord.max == UDWord.max / 2)
  expectTrue((0 as DWord) == 0 as UDWord)
  
  expectTrue(-1 as Int8 == -1 as DWord)
  expectTrue(UInt8.max != -1 as DWord)
  expectTrue(UInt8.max == 255 as DWord)
  expectTrue((0 as UInt8) == 0 as DWord)
  
  expectTrue(UInt8.max == 255 as UDWord)
  expectTrue(UInt8.max != UDWord.max)
  expectTrue((0 as UInt8) == (0 as UDWord))
}

tests.test("HeterogeneousOrdering") {
  expectTrue((-1 as DWord) < UDWord.max)
  expectTrue(DWord.max <= UDWord.max / 2)
  expectTrue(DWord.max >= UDWord.max / 2)
  expectTrue((0 as DWord) <= (0 as UDWord))
  expectTrue((0 as DWord) >= (0 as UDWord))
  
  expectTrue((-1 as Int8) <= -1 as DWord)
  expectTrue((-1 as Int8) >= -1 as DWord)
  expectTrue(UInt8.max > -1 as DWord)
  expectTrue(UInt8.max <= 255 as DWord)
  expectTrue(UInt8.max >= 255 as DWord)
  expectTrue((0 as UInt8) <= (0 as DWord))
  expectTrue((0 as UInt8) >= (0 as DWord))
  
  expectTrue(UInt8.max <= 255 as UDWord)
  expectTrue(UInt8.max >= 255 as UDWord)
  expectTrue(UInt8.max < UDWord.max)
  expectTrue((0 as UInt8) <= (0 as UDWord))
  expectTrue((0 as UInt8) >= (0 as UDWord))
}

tests.test("SmartBitShift/Homogeneous/Left/Int16") {
  let all1s = ~0 as Int16
  expectEqual(all1s, all1s << (0 as Int16))
  expectEqual(-2, all1s << (1 as Int16))
  expectEqual(Int16.min, all1s << (15 as Int16))
  expectEqual(0, all1s << (16 as Int16))

  expectEqual(-1, all1s << (-1 as Int16))
  expectEqual(-1, all1s << (-15 as Int16))
  expectEqual(-1, all1s << (-16 as Int16))
}

tests.test("SmartBitShift/Unconstrained/Left/Int16") {
  let all1s = ~0 as Int16
  expectEqual(all1s, all1s << 0)
  expectEqual(-2, all1s << 1)
  expectEqual(Int16.min, all1s << 15)
  expectEqual(0, all1s << 16)

  expectEqual(-1, all1s << -1)
  expectEqual(-1, all1s << -15)
  expectEqual(-1, all1s << -16)
}

tests.test("SmartBitShift/Homogeneous/Left/UInt16") {
  let all1s = ~0 as UInt16
  expectEqual(all1s, all1s << 0)
  expectEqual(0b1111_1111_1111_1110, all1s << 1)
  expectEqual(UInt16.max / 2 + 1, all1s << 15)
  expectEqual(0, all1s << 16)
}

tests.test("SmartBitShift/Heterogeneous/Left/Int16") {
  let all1s = ~0 as Int16
  expectEqual(all1s, all1s << (0 as Int8))
  expectEqual(-2, all1s << (1 as Int32))
  expectEqual(Int16.min, all1s << (15 as UInt32))
  expectEqual(0, all1s << (16 as UInt8))

  expectEqual(-1, all1s << (-1 as DWord))
  expectEqual(-1, all1s << (-15 as Word))
  expectEqual(-1, all1s << (-16 as Int32))
}

tests.test("SmartBitShift/Heterogeneous/Left/UInt16") {
  let all1s = ~0 as UInt16
  expectEqual(all1s, all1s << (0 as Int8))
  expectEqual(0b1111_1111_1111_1110, all1s << (1 as Int32))
  expectEqual(UInt16.max / 2 + 1, all1s << (15 as UInt32))
  expectEqual(0, all1s << (16 as UInt8))
  
  expectEqual(UInt16.max / 2, all1s << (-1 as DWord))
  expectEqual(1, all1s << (-15 as Word))
  expectEqual(0, all1s << (-16 as Int32))
}

tests.test("SmartBitShift/Unconstrained/Left/UInt16") {
  let all1s = ~0 as UInt16
  expectEqual(all1s, all1s << 0)
  expectEqual(0b1111_1111_1111_1110, all1s << 1)
  expectEqual(UInt16.max / 2 + 1, all1s << 15)
  expectEqual(0, all1s << 16)
  
  expectEqual(UInt16.max / 2, all1s << -1)
  expectEqual(1, all1s << -15)
  expectEqual(0, all1s << -16)
}

tests.test("Basics") {
  
  expectEqual(sizeof(Word.self), sizeof(Swift.Int.self))
  expectEqual(sizeof(DWord.self), 2 * sizeof(Swift.Int.self))

  typealias I8 = UInt8
  let b8: I8 = 0b1_0_11_0_111
  expectEqual(b8, 0b1_0_11_0_111)
  expectEqual(b8, 183)
  expectNotEqual(b8, I8())
  expectEqual(I8(), 0)
  expectEqual(8, I8.bitWidth)
  expectEqual(16, Int16.bitWidth)
  expectEqual(32, Int32.bitWidth)
}

runAllTests()