Crash in DoubleWidth

[LiarPrincess]

(See below)

[LiarPrincess]

(Even more below)

[LiarPrincess]

(Found it!)

History

From forums.swift.org/Status check - Int128, UInt128: DoubleWidth is not a public type, but users are allowed to copy it into their projects. This makes it public enough that we care about correctness.

Those tests come from Oh-my-decimal:

• UInt128Tests and UInt256Tests - you may need to modify them to compile with DoubleWidth - see "Tests" section below.
• Python script to generate tests - the quality of the test cases is not that great - just some random numbers smashed together -> they will not excise edge cases for min/max etc. Only use unsigned types, so you have check any signed types yourself.
• UInt128 that will pass those tests.

Passing all of those test cases does not make your implementation "correct" - I treat them as "sanity checks", before running the decimal tests. The real test would be to plug DoubleWidth into oh-my-decimal and see if all of the Decimal tests pass.

Tests

Executing those test will either trigger an assertion or return incorrect result:

import XCTest
import _TestSupport

class X: XCTestCase {

  typealias UInt128 = DoubleWidth<UInt64>
  typealias Word = UInt64

  func test_a() {
    typealias _UInt16 = DoubleWidth<UInt8>
    typealias _UInt128 = DoubleWidth<UInt64>
    typealias _UInt256 = DoubleWidth<_UInt128>

    let lhs = _UInt16((high: 0b0011_0000, low: 0))
    let rhs = _UInt16((high: 0b0010_0000, low: 0))
    assert(lhs.leadingZeroBitCount == rhs.leadingZeroBitCount)
    _ = lhs.quotientAndRemainder(dividingBy: rhs)
  }

  func test_b() {
    // https://www.wolframalpha.com/input?i=311758830729407788314878278112166161571+%2F+259735543268722398904715765931073125012
    self.div(
      [0xea8a9116b7af33b7, 0x3d9d6779ddd22ca3], // 311758830729407788314878278112166161571
      [0xc3673efc7f1f37cc, 0x312f661057d0ba94], // 259735543268722398904715765931073125012
      [               0x1], // 1
      [0x2723521a388ffbeb,  0xc6e01698601720f] // 52023287460685389410162512181093036559
    )
  }

  func test_c() {
    // https://www.wolframalpha.com/input?i=213714108890282186096522258117935109183+%2F+205716886996038887182342392781884393270
    self.div(
      [0xa0c7d7165cf01386, 0xbf3f66a93056143f], // 213714108890282186096522258117935109183
      [0x9ac3a19b1e7d6b83, 0x513929792d588736], // 205716886996038887182342392781884393270
      [               0x1], // 1
      [ 0x604357b3e72a803, 0x6e063d3002fd8d09] // 7997221894243298914179865336050715913
    )
  }

  private func div(
    _ lhsWords: [Word],
    _ rhsWords: [Word],
    _ quotientWords: [Word],
    _ remainderWords: [Word],
    file: StaticString = #file,
    line: UInt = #line
  ) {
    let lhs = self.create(lhsWords)
    let rhs = self.create(rhsWords)
    let quotient = self.create(quotientWords)
    let remainder = self.create(remainderWords)

    print("lhs", lhs)
    print("rhs", rhs)
    print("expected.quotient", quotient)
    print("expected.remainder", remainder)

    let qr = lhs.quotientAndRemainder(dividingBy: rhs)
    print("result.quotient", qr.quotient)
    print("result.remainder", qr.remainder)
    XCTAssertEqual(qr.quotient, quotient, "quotientAndRemainder.quotient", file: file, line: line)
    XCTAssertEqual(qr.remainder, remainder, "quotientAndRemainder.remainder", file: file, line: line)
  }

  private func create(_ words: [Word]) -> UInt128 {
    switch words.count {
    case 1: return UInt128((0, words[0]))
    case 2: return UInt128((words[0], words[1]))
    default: fatalError("Unknown UInt128 input: \(words)")
    }
  }
}

Hint

// Edge case for the bit shifting below.
if self.leadingZeroBitCount == rhs.leadingZeroBitCount {
  // Quotient is 1 and remainder is the difference:
  // - lhs > rhs
  // - both operands have non-0 high bits
  // - both have the same high power of 2, so quotient has to be 1
  let quotient = Self(0, 1)
  let remainder = self - rhs
  return (quotient, remainder)
}

Random tests?

Since I had to download this package anyway, I looked into other tests and I noticed that you are using a lot of random. This will go through SystemRandomNumberGenerator which will call system random. As far as I know no stubbing will happen.

The problem is that each execution of your tests will give different numbers. Is this intended?

You already have LinearCongruentialGenerator implemented, so you can just copy it. Oh-my-decimal uses xorshift, and BigInt has some math formula. Even the Python script that generated tests in this issue starts with: random.seed(123456).

[LiarPrincess]

Btw. I forgot to mention:

• Ubuntu 22.04.3 LTS
• Swift version 5.7.3 (swift-5.7.3-RELEASE)
• Intel Pentium G4560

Same thing on mac with Intel cpu (I don't own M1/2).

---

New tests that will trigger assertion failure. Note that those areUInt256 tests, as all of the UInt128 tests will pass.

import XCTest
import _TestSupport

class XX: XCTestCase {

  typealias UInt128 = DoubleWidth<UInt64>
  typealias UInt256 = DoubleWidth<UInt128>
  typealias Word = UInt64

  func test_d() {
    // wolframalpha will fail, but this is close enough:
    // https://duckduckgo.com/?q=2369676578372158364766242369061213561181961479062237766620+%2F+102797312405202436815976773795958969482&t=canonical&ia=calculator
    self.div(
      [0x60a493eed96c8fb4, 0x8611720727ba6a57, 0x240b0df39efc63dc], // 2369676578372158364766242369061213561181961479062237766620
      [0x4d560aceb12c4d65, 0x9e142564bfe7548a], // 102797312405202436815976773795958969482
      [               0x1, 0x3fe8e956ae19058a], // 23051931251193218442
      [ 0x178515948bb2598, 0xd075f47b9a281f78] // 1953953567802622125048779101000179576
    )
  }

  func test_e() {
    // wolframalpha will fail, but this is close enough:
    // https://duckduckgo.com/?q=96467201117289166187766181030232879447148862859323917044548749804018359008044+%2F+4646260627574879223760172113656436161581617773435991717024&t=canonical&ia=calculator
    self.div(
      [0xd546803d3d0dfc06, 0xd3464e79bf536133, 0x60adffae7b060df9, 0x9db060d7f802fb2c], // 96467201117289166187766181030232879447148862859323917044548749804018359008044
      [0xbd7d39707431400d, 0xb5ef5a88e6ac3a63, 0x8d4db1bd988974a0], // 4646260627574879223760172113656436161581617773435991717024
      [               0x1, 0x20229e0d41a63655], // 20762331011904583253
      [0x77a083cdc2a7fd32, 0x40cc2c8564a9605f, 0xd884e2d91405820c] // 2933245778855346947389808606934720764144871598087733608972
    )
  }

  private func div(
    _ lhsWords: [Word],
    _ rhsWords: [Word],
    _ quotientWords: [Word],
    _ remainderWords: [Word],
    file: StaticString = #file,
    line: UInt = #line
  ) {
    let lhs = self.create(lhsWords)
    let rhs = self.create(rhsWords)
    let quotient = self.create(quotientWords)
    let remainder = self.create(remainderWords)

    print("lhs", lhs)
    print("rhs", rhs)
    print("expected.quotient", quotient)
    print("expected.remainder", remainder)

    let qr = lhs.quotientAndRemainder(dividingBy: rhs)
    print("result.quotient", qr.quotient)
    print("result.remainder", qr.remainder)
    XCTAssertEqual(qr.quotient, quotient, "quotientAndRemainder.quotient", file: file, line: line)
    XCTAssertEqual(qr.remainder, remainder, "quotientAndRemainder.remainder", file: file, line: line)
  }

  private func create(_ words: [Word]) -> UInt256 {
    func f(_ w0: Word, _ w1: Word, _ w2: Word, _ w3: Word) -> UInt256 {
      let h = UInt128((w0, w1))
      let l = UInt128((w2, w3))
      return UInt256((h, l))
    }

    switch words.count {
    case 1: return f(0, 0, 0, words[0])
    case 2: return f(0, 0, words[0], words[1])
    case 3: return f(0, words[0], words[1], words[2])
    case 4: return f(words[0], words[1], words[2], words[3])
    default: fatalError("Unknown UInt256 input: \(words)")
    }
  }
}

[LiarPrincess]

I confirm that #273 solves this issue.

In the PR I pasted all of my tests, so I will put them here for completeness:

• UInt128 - https://gist.github.com/LiarPrincess/54bbaaf3589e55ee25783fe9f6648c55
• UInt256 - https://gist.github.com/LiarPrincess/8b4d2891e0f8c557a9543d054790ad7b