Testcase failed after converting codes from Objective-C to Swift

Question

I am doing some bitwise operations in Swift style, which these codes are originally written in Objective-C/C. I use UnsafeMutablePointer to state the beginning index of memory address and use UnsafeMutableBufferPointer for accessing the element within the scope.

You can access the original Objective-C file Here.

public init(size: Int) {
    self.size = size
    self.bitsLength = (size + 31) / 32
    self.startIdx = UnsafeMutablePointer<Int32>.alloc(bitsLength * sizeof(Int32))
    self.bits = UnsafeMutableBufferPointer(start: startIdx, count: bitsLength)
}

/**
 * @param from first bit to check
 * @return index of first bit that is set, starting from the given index, or size if none are set
 *  at or beyond its given index
 */
public func nextSet(from: Int) -> Int {
    if from >= size { return size }
    var bitsOffset = from / 32
    var currentBits: Int32 = bits[bitsOffset]
    currentBits &= ~((1 << (from & 0x1F)) - 1).to32
    while currentBits == 0 {
        if ++bitsOffset == bitsLength {
            return size
        }
        currentBits = bits[bitsOffset]
    }
    let result: Int = bitsOffset * 32 + numberOfTrailingZeros(currentBits).toInt
    return result > size ? size : result
}

func numberOfTrailingZeros(i: Int32) -> Int {
    var i = i
    guard i != 0 else { return 32 }
    var n = 31
    var y: Int32
    y = i << 16
    if y != 0 { n = n - 16; i = y }
    y = i << 8
    if y != 0 { n = n - 8; i = y }
    y = i << 4
    if y != 0 { n = n - 4; i = y }
    y = i << 2
    if y != 0 { n = n - 2; i = y }
    return n - Int((UInt((i << 1)) >> 31))
}

Testcase:

func testGetNextSet1() {
    // Passed
    var bits = BitArray(size: 32)
    for i in 0..<bits.size {
        XCTAssertEqual(32, bits.nextSet(i), "\(i)")
    }
    // Failed
    bits = BitArray(size: 34)
    for i in 0..<bits.size {
        XCTAssertEqual(34, bits.nextSet(i), "\(i)")
    }
}

Can someone guide me why the second testcase fail but the objective-c version pass ?

Edit: As @vacawama mentioned: If you break testGetNextSet into 2 tests, both pass.

Edit2: When I run tests with xctool, and tests which calling BitArray's nextSet() will crash while running.

Mow

How are .toInt and .to32 implemented? – Unforgettable

@Unforgettable It's an extension of Int public var to32：Int32｛return Int32(truncatingBitPattern：self)｝ – Mow

This statement is troublesome: return n - Int((UInt((i << 1)) >> 31)). If i is negative, this will crash. – Unforgettable

Answer 1

Objective-C version of numberOfTrailingZeros:

// Ported from OpenJDK Integer.numberOfTrailingZeros implementation
- (int32_t)numberOfTrailingZeros:(int32_t)i {
    int32_t y;
    if (i == 0) return 32;
    int32_t n = 31;
    y = i <<16; if (y != 0) { n = n -16; i = y; }
    y = i << 8; if (y != 0) { n = n - 8; i = y; }
    y = i << 4; if (y != 0) { n = n - 4; i = y; }
    y = i << 2; if (y != 0) { n = n - 2; i = y; }
    return n - (int32_t)((uint32_t)(i << 1) >> 31);
}

When translating numberOfTrailingZeros, you changed the return value from Int32 to Int. That is fine, but the last line of the function is not operating properly as you translated it.

In numberOfTrailingZeros, replace this:

return n - Int((UInt((i << 1)) >> 31))

With this:

return n - Int(UInt32(bitPattern: i << 1) >> 31)

The cast to UInt32 removes all but the lower 32 bits. Since you were casting to UInt, you weren't removing those bits. It is necessary to use bitPattern to make this happen.

Unforgettable

It looks like that XCTAssertEqual failed: ("Optional(34)") is not equal to ("Optional(32)") which shows 34 times. – Mow

It's working for me if I test on a 64-bit device (iPhone 5S and later). Can you update your question to show all of your code (including implementations of .toInt, .to32, and the rest of the BitArray implementation. Perhaps I did it differently. – Unforgettable

I just uploaded an example repo here, please checkout for more info. – Mow

First, shouldn't the second assert in testGetNextSet be XCTAssertEqual(34, array.nextSet(i), "\(i)") ? Why is it referencing bitArray. The same goes for the loop. But even with that change testGetNextSet fails. Weird. If you break testGetNextSet into 2 tests, both pass. – Unforgettable

Exactly, I just made a typo, sorry for that stupid mistake. – Mow

I've posted a new answer about how I finally figured out this issue. Anyway, thanks for your points. – Mow

Answer 2

Finally I found out that startIdx just need to be initialized after allocation.

self.startIdx = UnsafeMutablePointer<Int32>.alloc(bitsLength * sizeof(Int32))
self.startIdx.initializeFrom(Array(count: bitsLength, repeatedValue: 0))

Or use calloc with just one line code:

self.startIdx = unsafeBitCast(calloc(bitsLength, sizeof(Int32)), UnsafeMutablePointer<Int32>.self)

Furthermore, I use lazy var to defer the Initialization of UnsafeMutableBufferPointer until the property is first used.

lazy var bits: UnsafeMutableBufferPointer<Int32> = {
   return UnsafeMutableBufferPointer<Int32>(start: self.startIdx, count: self.bitsLength)
}()

On the other hand, don't forget to deinit:

deinit {
    startIdx.destroy()
    startIdx.dealloc(bitsLength * sizeof(Int32))
}

Mow