//===--- 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 -----------------------------------------===//

/// Prints the message if the body is uncommented; used for
/// diagnostics.
@_transparent
public func _log(@autoclosure message: ()->String) {
  // print(message())
}

//===----------------------------------------------------------------------===//
//===--- 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 uword(n: Word) -> UWord

  var countRepresentedWords: Word { get }

  /// Replace as many bits as possible of the `n`th UWord of our
  /// representation with newBits, returning `true` iff all of the
  /// bits were replaced.
  mutating func replaceUWord(n: Word, with newBits: UWord) -> Bool
  
  init<T : IntegerType>(_ source: T)
  
  init<T : IntegerType>(extendingOrTruncating source: T)

  mutating func addInPlace<RHS: IntegerType>(rhs: RHS) -> ArithmeticOverflow

  /// The most significant word in a signed representation of `self`.
  ///
  ///     (x.word(x.signWordIndex) < 0) == (self < 0)
  ///
  /// and, for all `i` > `x.signWordIndex`,
  ///
  ///     x.word(i) == x.word(x.signWordIndex) >> (Word.bitWidth - 1)
  ///
  var signWordIndex: Word { get }
  
  mutating func signedOverflowIntoWord(
    wordIndex: Word, overflow: Bool, originalSign: Word) -> ArithmeticOverflow  

  static var isSigned: Bool { get }
}

extension IntegerType {
  @_transparent
  @warn_unused_result
  public func word(n: Word) -> Word {
    return Word(uword(n)._storage)
  }

  /// The number of words required to represent our value.  If `self`
  /// is negative, returns the index of the least significant words of
  /// our representation such that all more-significant words are -1.
  /// Has the value -1 if `self` is 0.
  @_transparent
  public // transparent
  var _mostSignificantWord: Word {
    return mostSignificantBit &>> ${int(log(word_bits,2))}
  }
}

//===--- 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

@_transparent
@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)
}

@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 {
  @_transparent
  public init(_ overflow: Bool) { self = overflow ? .Overflow : .None }
  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: UWord)

  var _lowUWord: UWord { 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.isSigned ? 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.uword(0))
    }
    else {
      var result: Self = source < 0 ? ~0 : 0
      // start with the most significant word
      var n = source._mostSignificantWord
      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.uword(n))
        n -= 1
      }
      
      self = result
    }
  }

  @_transparent
  public func uword(n: Word) -> UWord {
    _precondition(n >= 0, "Negative word index")
    if _fastPath(n < countRepresentedWords) {
      let shift = UWord(n._storage) &* ${word_bits}
      let bitWidth = UWord(Self.bitWidth._storage)
      _sanityCheck(shift < bitWidth)
      return (self &>> Self(_truncatingBits: shift))._lowUWord
    }
    return self < 0 ? ~0 : 0
  }

  public var countRepresentedWords: Word {
    return (Self.bitWidth + ${word_bits} - 1) / ${word_bits}
  }
  
  // @_transparent
  public mutating func replaceUWord(n: Word, with newBits: UWord) -> Bool {
    let flippedBits = uword(n) ^ newBits
    self ^= Self(_truncatingBits: flippedBits) << (${word_bits} * n)
    if uword(n) != newBits {
      _log("###### overflow replacing word \(n) with \(newBits.hex)")
    }
    return uword(n) == newBits
  }
  
  @_transparent
  public // transparent
  static var _highBitIndex: Self {
    return Self.init(_truncatingBits: UWord(Self.bitWidth._storage) &- 1)
  }
}

extension UWord {
  public typealias AdditiveOperator
    = (UWord) -> (UWord, carryIn: Bool)
     -> (result: UWord, carryFlag: Bool, overflowFlag: Bool)

  % for name in 'add', 'subtract':
  // @_transparent
  public // transparent
  func _${name}ing(
    rhs: UWord, carryIn: Bool
  ) -> (result: UWord, carryFlag: Bool, overflowFlag: Bool) {
    _log("**** \(self.hex)._${name}ing(\(rhs.hex), carryIn: \(carryIn))")
    let signedRHS = Word(bitPattern: rhs)
    
    let (uResult0, carry0) = self.${name}WithOverflow(rhs)
    let (sResult0, overflow0)
      = Word(bitPattern: self).${name}WithOverflow(signedRHS)
    
    let (uResult1, carry1) = uResult0.${name}WithOverflow(carryIn ? 1 : 0)
    let (_, overflow1) = sResult0.${name}WithOverflow(carryIn ? 1 : 0)

    let result = (
      result: uResult1,
      carryFlag: carry0 != .None || carry1 != .None,
      overflowFlag: overflow0 != .None || overflow1 != .None
    )
    _log("**** -> sum: \(result.result.hex), "
      + "carry: \(result.carryFlag), overflow: \(result.overflowFlag)")
    return result
  }
  % end
}

% 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 {
  @_transparent
  public static var isSigned: Bool { return false }
  
  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()
  }
  
  @_transparent
  public var signWordIndex: Word {
    // If our high bit is set, then our signed representation contains
    // one additional word.
    let ifHighBitSetThen0Else1 = Word((~self &>> (Self.bitWidth - 1))._lowUWord)
    return (Self.bitWidth - ifHighBitSetThen0Else1) / ${word_bits}
  }

  @_transparent
  public mutating func signedOverflowIntoWord(
    wordIndex: Word, overflow: Bool, originalSign: Word
  ) -> ArithmeticOverflow {
    // We were performing a signed operation on unsigned storage.  If
    // the result was negative, we've overflowed.
    return word(countRepresentedWords - 1) < 0 ? .Overflow : .None
  }
}

//===----------------------------------------------------------------------===//
//===--- 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
  }
  
  @_transparent
  public static var isSigned: Bool { return true }
}

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()
  }

  @_transparent
  public var signWordIndex: Word {
    return (Self.bitWidth - 1) / ${word_bits}
  }

  @_transparent
  public mutating func signedOverflowIntoWord(
    wordIndex: Word, overflow: Bool, originalSign: Word
  ) -> ArithmeticOverflow {
    return overflow ? .Overflow : .None
  }
}

//===--- 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))
  }

  @_transparent
  public init(bitPattern x: ${'U' if signed else ''}Int${bits}) {
    _storage = x._storage
  }

  @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: ArithmeticOverflow(Bool(overflow)))
  }
%       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 Word(
      ${Self}(
        Builtin.int_ctlz_Int${bits}(self._storage, false.__value)
      )._lowUWord._storage)
  }
  
  @_transparent
  public // transparent
  var _lowUWord: UWord {
    % truncOrExt = z + 'ext' if bits <= word_bits else 'trunc'
    return UWord(
      Builtin.${truncOrExt}OrBitCast_Int${bits}_Int${word_bits}(_storage)
    )
  }
  
  @_transparent
  public // transparent
  init(_truncatingBits bits: UWord) {
    % 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

//===----------------------------------------------------------------------===//
//===--- Multiprecision ---------------------------------------------------===//
//===----------------------------------------------------------------------===//

//===--- Addition and Subtraction -----------------------------------------===//
//
// * Treat both operands as infinite-precision numbers, proceeding a
//   word-at-a-time.
//
// * Signed/Unsigned mixes treat the unsigned number as signed,
//   thereby adding 1 significant bit (which could result in using an
//   extra word), and doing a signed operation.
//
// * Operations proceed one word at a time.  Signed operations are
//   composed of unsigned operations for all but the highest word.
//
// * Overflows in fixed-width integers are detected by two methods:
//   - Checking the overflow flag when the most significant word of the
//     result is computed.
//   - Attempting to store bits that can't be represented.
//
// * In [un]signed operations, the maximum number of bits required to
//   store a result is one more than the maximum number of bits
//   required to store the [un]signed representation of both operands.
//   When that number is one more than the number of bits
//   representable by the [un]signed result type, we can use the
//   carry/overflow flag to detect overflow.
//
extension IntegerType {
  public mutating func unsignedAddInPlace<RHS: IntegerType>(
    rhs: RHS, uwordOperator: UWord.AdditiveOperator
  ) -> ArithmeticOverflow {
    _log("* \(Self.self)(\(self.hex)).unsignedAddInPlace"
      + "(\(RHS.self)(\(rhs.hex)))")
    let (carry, knownOverflow) = self.unsignedAddInPlace(
      rhs,
      countWords: max(self.countRepresentedWords, rhs.countRepresentedWords),
      uwordOperator: uwordOperator
    )
    return knownOverflow ?? ArithmeticOverflow(carry)
  }
  
  public mutating func unsignedAddInPlace<RHS: IntegerType>(
    rhs: RHS, countWords: Word, uwordOperator: UWord.AdditiveOperator
  ) -> (carry: Bool, knownOverflow: ArithmeticOverflow?) {
    _log("** \(Self.self)(\(self.hex)).unsignedAddInPlace"
      + "(\(RHS.self)(\(rhs.hex)), countWords: \(countWords))")
    _log("*** rhs.countRepresentedWords: \(rhs.countRepresentedWords)")
    
    var i: Word = 0
    var carry: Bool = false
    
    while i < countWords {
      let sum: UWord
      (sum, carry, _) = uwordOperator(uword(i))(rhs.uword(i), carryIn: carry)
      
      if !self.replaceUWord(i, with: sum) {
        return (false, .Overflow)
      }
      i += 1
      // optimization: if we've processed all represented words on the
      // rhs and there's no carry out, the lhs can not be further
      // affected and no overflow can occur.  This probably doesn't
      // matter for fixed-width integers but may be significant with
      // larger BigNums.  On the other hand, we may not want to
      // optimize for that :-)
      if carry == (rhs < 0) && i >= rhs.countRepresentedWords {
        _log("*** early exit; carry can't affect lhs")
        return (carry, .None as ArithmeticOverflow)
      }
    }
    return (carry, nil)
  }
  
  public mutating func signedAddInPlace<RHS: IntegerType>(
    rhs: RHS, uwordOperator: UWord.AdditiveOperator
  ) -> ArithmeticOverflow {
    _log("* \(Self.self)(\(self.hex)).signedAddInPlace"
      + "(\(RHS.self)(\(rhs.hex)))")
    // Do a multiword unsigned operation on all the words below the sign
    // word.  We may overflow here or discover that there is no
    // overflow.
    let lowWordCount = self.signWordIndex
    
    let (lowCarry, lowOverflowKnown)
      = self.unsignedAddInPlace(
        rhs, countWords: lowWordCount, uwordOperator: uwordOperator)

    if let finalOverflow = lowOverflowKnown { return finalOverflow }
    
    // Save off the sign word so that we don't lose it if the highest
    // stored bit of the lhs flips.  When this addition proceeds past
    // the highest stored word, we still need to be able to retrieve
    // the old sign word.
    var oldSign = self.word(lowWordCount)
    
    var wordIndex: Word = lowWordCount
    var overflow: Bool, carry: Bool = lowCarry
    
    repeat {
      let bits: UWord
      (bits, carry, overflow) = uwordOperator(oldSign._lowUWord)(
        rhs.uword(wordIndex), carryIn: carry)
      if !self.replaceUWord(wordIndex, with: bits) {
        return .Overflow
      }
      oldSign &>>= ${word_bits - 1} // further sign words are 0 or -1
      wordIndex += 1
    }
    while wordIndex <= rhs.signWordIndex

    return signedOverflowIntoWord(
      wordIndex, overflow: overflow, originalSign: oldSign)
  }
}

extension IntegerType {
  % for name in 'add', 'subtract':
  public mutating func ${name}InPlace<RHS: IntegerType>(
    rhs: RHS
  ) -> ArithmeticOverflow {
    return Self.isSigned || RHS.isSigned
    ? signedAddInPlace(rhs, uwordOperator: UWord._${name}ing)
    : unsignedAddInPlace(rhs, uwordOperator: UWord._${name}ing)
  }
  % end
}

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

@inline(__always)
public func +=<T: IntegerType, U: IntegerType>(inout lhs: T, rhs: U) {
  let overflow = lhs.addInPlace(rhs)
  _assertCond(overflow == .None, "overflow in multiprecision add.")
}

@inline(__always)
public func -=<T: IntegerType, U: IntegerType>(inout lhs: T, rhs: U) {
  let overflow = lhs.subtractInPlace(rhs)
  _assertCond(overflow == .None, "overflow in multiprecision subtract.")
}

//===--- Tests ------------------------------------------------------------===//

extension IntegerType {
  /// a hex representation of every bit in the number
  func hexBits(bitWidth: Word) -> String {
    let hexDigits: [UnicodeScalar] = [
      "0", "1", "2", "3", "4", "5", "6", "7",
      "8", "9", "A", "B", "C", "D", "E", "F"]

    var result = "".unicodeScalars
    var x = self
    var nibbles: Word = 0
    repeat {
      if nibbles % 4 == 0 && nibbles != 0 {
        result.insert("_", atIndex: result.startIndex)
      }
      let lowUWord = x.uword(0)
      result.insert(
        hexDigits[Swift.Int(lowUWord._storage) & 0xF],
        atIndex: result.startIndex
      )
      x.replaceUWord(0, with: lowUWord & ~0xF)
      x /= 16
      nibbles += 1
    }
    while (nibbles << 2 < bitWidth || (x != 0 && x + 1 != 0))
    return (self < 0 ? "[-]" : "[+]") + String(result)
  }
  
  var hex: String { return hexBits(0) }
}

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

import StdlibUnittest

// Also import modules which are used by StdlibUnittest internally. This
// workaround is needed to link all required libraries in case we compile
// StdlibUnittest with -sil-serialize-all.
import SwiftPrivate
#if _runtime(_ObjC)
import ObjectiveC
#endif

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(-1, (0 as Int8).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)
}

tests.test("uword") {
  let x = UDWord(Word.max)
  expectEqual(Word.max._lowUWord, x.uword(0))
  expectEqual(0, x.uword(1))
  
  let y = DWord(Word.min)
  expectEqual(Word.min._lowUWord, y.uword(0))
  expectEqual(~0, y.uword(1))

  let z = UWord(~Word.min) + 1
  expectEqual(Word.min._lowUWord, z.uword(0))
  expectEqual(0, z.uword(1))
}

tests.test("Multiprecision/+/DWord") {
  var x = DWord.max - 2
  x += (1 as UInt8)
  expectEqual(DWord.max - 1, x)
  x += (-1 as Int8)
  expectEqual(DWord.max - 2, x)

  x = DWord.min
  x += (1 as UInt8)
  expectEqual(DWord.min + 1, x)

  x += (-1 as Int8)
  expectEqual(DWord.min, x)

  x = DWord(UWord.max)
  x += (1 as Int8)
  expectEqual(DWord(UWord.max) + 1, x)
  x += (-1 as Int8)
  expectEqual(DWord(UWord.max), x)
  x += (1 as UDWord)
  expectEqual(DWord(UWord.max) + 1, x)
  
  x = DWord(Word.max)
  var overflow: ArithmeticOverflow
  overflow = x.addInPlace(Word.min)
  expectEqual(.None, overflow)
  expectEqual(-1, x)

  overflow = x.addInPlace(DWord.min)
  expectEqual(.Overflow, overflow)
  expectEqual(DWord.max, x)

  overflow = x.addInPlace(1 as Word)
  expectEqual(.Overflow, overflow)
  expectEqual(DWord.min, x)

  x = 1
  overflow = x.addInPlace(DWord.max)
  expectEqual(.Overflow, overflow)
  expectEqual(DWord.min, x)
}

tests.test("Multiprecision/+/UDWord") {
  var x = UDWord.max - 2
  x += (1 as UInt8)
  expectEqual(UDWord.max - 1, x)
  x += (-1 as Int8)
  expectEqual(UDWord.max - 2, x)

  x = UDWord.min
  x += (1 as UInt8)
  expectEqual(1, x)

  x += (-1 as Int8)
  expectEqual(UDWord.min, x)

  x = UDWord(UWord.max)
  x += (1 as Int8)
  expectEqual(UDWord(UWord.max) + 1, x)
  x += (-1 as Int8)
  expectEqual(UDWord(UWord.max), x)
  x += (1 as DWord)
  expectEqual(UDWord(UWord.max) + 1, x)
  x += (-1 as DWord)
  expectEqual(UDWord(UWord.max), x)
  
  x = UDWord(Word.max)
  var overflow: ArithmeticOverflow
  overflow = x.addInPlace(Word.min)
  expectEqual(.Overflow, overflow)
  expectEqual(UDWord.max, x)

  overflow = x.addInPlace(DWord.min)
  expectEqual(.None, overflow)
  overflow = x.addInPlace(DWord.min)
  expectEqual(.Overflow, overflow)
  expectEqual(UDWord.max, x)

  overflow = x.addInPlace(1 as Int8)
  expectEqual(.Overflow, overflow)
  expectEqual(0, x)

  x = 1
  overflow = x.addInPlace(UDWord.max)
  expectEqual(.Overflow, overflow)
  expectEqual(0, x)
}

tests.test("Multiprecision/-/DWord") {
  var x = DWord.max - 2
  x -= (-1 as Int8)
  expectEqual(DWord.max - 1, x)
  x -= (1 as Int8)
  expectEqual(DWord.max - 2, x)

  x = DWord.min
  x -= (-1 as Int8)
  expectEqual(DWord.min + 1, x)

  x -= (1 as Int8)
  expectEqual(DWord.min, x)

  x = DWord(UWord.max)
  x -= (-1 as Int8)
  expectEqual(DWord(UWord.max) + 1, x)
  x -= (1 as Int8)
  expectEqual(DWord(UWord.max), x)
  x -= (-1 as DWord)
  expectEqual(DWord(UWord.max) + 1, x)
  
  x = DWord(Word.max)
  var overflow: ArithmeticOverflow
  overflow = x.subtractInPlace(UWord(~Word.min) + 1)
  expectEqual(.None, overflow)
  expectEqual(-1, x)

  overflow = x.subtractInPlace(UDWord(~DWord.min) + 1)
  expectEqual(.Overflow, overflow)
  expectEqual(DWord.max, x)

  overflow = x.subtractInPlace(-1 as Word)
  expectEqual(.Overflow, overflow)
  expectEqual(DWord.min, x)

  x = 1
  overflow = x.subtractInPlace(DWord.min + 1)
  expectEqual(.Overflow, overflow)
  expectEqual(DWord.min, x)
}

tests.test("Multiprecision/-/UDWord") {
  var x = UDWord.max - 2
  x -= (-1 as Int8)
  expectEqual(UDWord.max - 1, x)
  x -= (1 as UInt8)
  expectEqual(UDWord.max - 2, x)

  x = UDWord.min
  x -= (-1 as Int8)
  expectEqual(1, x)

  x -= (1 as Int8)
  expectEqual(UDWord.min, x)

  x = UDWord(UWord.max)
  x -= (-1 as Int8)
  expectEqual(UDWord(UWord.max) + 1, x)
  x -= (1 as Int8)
  expectEqual(UDWord(UWord.max), x)
  x -= (-1 as DWord)
  expectEqual(UDWord(UWord.max) + 1, x)
  x -= (1 as DWord)
  expectEqual(UDWord(UWord.max), x)
  
  x = UDWord(Word.max)
  var overflow: ArithmeticOverflow
  overflow = x.subtractInPlace(UWord(~Word.min) + 1)
  expectEqual(.Overflow, overflow)
  expectEqual(UDWord.max, x)

  overflow = x.subtractInPlace(UDWord(DWord.max) + 1)
  expectEqual(.None, overflow)
  overflow = x.subtractInPlace(UDWord(DWord.max) + 1)
  expectEqual(.Overflow, overflow)
  expectEqual(UDWord.max, x)

  overflow = x.subtractInPlace(DWord.max)
  expectEqual(.None, overflow)
  overflow = x.subtractInPlace(DWord.max)
  expectEqual(.None, overflow)
  expectEqual(1, x)
  
  overflow = x.subtractInPlace(2 as UDWord)
  expectEqual(.Overflow, overflow)
  expectEqual(UDWord.max, x)
  
  overflow = x.subtractInPlace(-1 as Int8)
  expectEqual(.Overflow, overflow)
  expectEqual(0, x)

  x = 1
  overflow = x.subtractInPlace(UDWord.max)
  expectEqual(.Overflow, overflow)
  expectEqual(2, x)
}

tests.test("Multiprecision/+/Int16") {
  var x = Int16.max - 2
  x += (1 as UDWord)
  expectEqual(Int16.max - 1, x)
  x += (-1 as DWord)
  expectEqual(Int16.max - 2, x)

  x = Int16.min
  x += (1 as UDWord)
  expectEqual(Int16.min + 1, x)
  
  x += (-1 as DWord)
  expectEqual(Int16.min, x)
}

tests.test("Multiprecision/Overflow/+/Int16") {
  var x = Int16.max - 1
  x += 1 as UInt16
  expectCrashLater()
  x += 1 as UInt16
}

tests.test("Multiprecision/Underflow/+/Int16") {
  var x = Int16.min + 1
  x += -1 as Int32
  expectCrashLater()
  x += -1 as Int32
}


tests.test("Multiprecision/Overflow/+/UInt16") {
  var x = UInt16.max - 1
  x += 1 as Int16
  expectCrashLater()
  x += 1 as Int16
}

tests.test("Multiprecision/Underflow/+/UInt16") {
  var x = UInt16.min + 1
  x += -1 as DWord
  expectCrashLater()
  x += -1 as DWord
}


tests.test("Multiprecision/Overflow/+/Word") {
  var x = Word.max - 1
  x += 1 as UWord
  expectCrashLater()
  x += 1 as UWord
}

tests.test("Multiprecision/Underflow/+/Word") {
  var x = Word.min + 1
  x += -1 as Int32
  expectCrashLater()
  x += -1 as Int32
}


tests.test("Multiprecision/Overflow/+/UWord") {
  var x = UWord.max - 1
  x += 1 as Word
  expectCrashLater()
  x += 1 as Word
}

tests.test("Multiprecision/Underflow/+/UWord") {
  var x = UWord.min + 1
  x += -1 as DWord
  expectCrashLater()
  x += -1 as DWord
}

tests.test("Multiprecision/Overflow/+/DWord") {
  var x = DWord.max - 1
  x += 1 as UWord
  expectCrashLater()
  x += 1 as UWord
}

tests.test("Multiprecision/Underflow/+/DWord") {
  var x = DWord.min + 1
  x += -1 as Int32
  expectCrashLater()
  x += -1 as Int32
}


tests.test("Multiprecision/Overflow/+/UDWord") {
  var x = UDWord.max - 1
  x += 1 as Word
  expectCrashLater()
  x += 1 as Word
}

tests.test("Multiprecision/Underflow/+/UDWord") {
  var x = UDWord.min + 1
  x += -1 as DWord
  expectCrashLater()
  x += -1 as DWord
}


runAllTests()