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.

@vacawama It's an extension of Int `public var to32：Int32｛return Int32(truncatingBitPattern：self)｝` — Zigii Wong, Apr 16 '16 at 12:00
This statement is troublesome: `return n - Int((UInt((i << 1)) >> 31))`. If `i` is negative, this will crash. — vacawama, Apr 16 '16 at 12:21

score 3 · Accepted Answer · answered Apr 16 '16 at 13:48

3

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.

answered Apr 16 '16 at 13:48

vacawama

150,663
30
266
294

It looks like that `XCTAssertEqual failed: ("Optional(34)") is not equal to ("Optional(32)") ` which shows 34 times. – Zigii Wong Apr 17 '16 at 06:43
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. – vacawama Apr 17 '16 at 11:23
I just uploaded an example repo [here](https://github.com/wongzigii/SwiftBit), please checkout for more info. – Zigii Wong Apr 17 '16 at 14:57
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. – vacawama Apr 17 '16 at 16:53
Exactly, I just made a typo, sorry for that stupid mistake. – Zigii Wong Apr 17 '16 at 17:14
I've posted a new answer about how I finally figured out this issue. Anyway, thanks for your points. – Zigii Wong May 11 '16 at 02:58

Zigii Wong · Answer 2 · 2016-05-09T15:10:35.007

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

Testcase failed after converting codes from Objective-C to Swift

2 Answers2

Linked