February 16, 2015

Swiftly Secure, Part 3 – Dividing Huge Numbers

Posted in iPhone development, mac development tagged , , , , , at 9:05 pm by tetontech

Let’s face reality. Computer division is ugly. It’s not the case, but it might seem to some people that those who conceived the computers we use today dropped the ball. Addition and Multiplication algorithms at both code and hardware levels are fairly straight forward, even if there is significant computational cost involved. Division, on the other hand, can seem like it was ‘tacked on’ afterwards. To think this thought is to do a disservice to the computational founders. The problem didn’t arise with them. It came from how we humans have done division for millennia. The age-old long hand grade school division algorithm taught to young people around the world is the problem. It is a guess-and-check process and computers are notoriously bad at guessing. It is no wonder the founders struggled. What else did they have to base division on?

When I set out to find a division algorithm to implement for Swiftly Secure and this posting, the other common division method, inverting the divisor, jumped right out of old and new computer science patents and research. The inversion idea is that a / b is the same as a * 1/b and it may be easier to calculate 1/b than to do the original division. Modern research into division seems to be fixated on optimizing variations on this approach. Each variation seems to share the same weakness as the grade school algorithm–they end up being guess-and-check algorithms trying to outdo Isaac Newton’s division algorithm or its more modern variants and replacements. This doesn’t resolve the problem, it shifts it to an area where guessing is hopefully easier.

I’m going to make a bold statement here. Computers are bad at guessing. I wanted to come up with an algorithm where no guessing was going on to use in Swiftly Secure. I think I’ve found one. It works for integer division for single word integers and huge numbers that require multiple words to represent them. I haven’t tested the algorithm for applicability to floating point division yet.

The idea behind the solution is this–since computers work in binary maybe there is something in the binary representations of the dividend, a, the divisor, b, and the quotient, q (a / b = q) that allows calculation of the quotient without guessing. There is. Finding it was a significant process and like all good answers to interesting questions, after I found it it the solution seemed obvious. Here it is simplified.

The difference between the index of the highest on-bit of a (the dividend) and b (the divisor) is often the index of the highest on-bit of q (the quotient).

A) if a / b = q

B) then  i[a] – i[b] = i[q] (where i means the index of the highest on-bit)

Where statement B isn’t true, the difference calculated is always one too large. When the difference is off is completely predictable, calculable, and derivable from  the value of the dividend (I’ll show how to do this later in this posting).

Interesting, but h0w does this help us not guess and check? Instead of guessing and checking by attacking the dividend and/or the divisor and then seeing if the quotient is ‘close enough’, as is done by Newton’s method and its decedents, this realization allows us to attack the quotient, q, directly. As an example lets look at a simple one-word division.


127 / 17 = 7 Remainder 8

decimal                 binary (bigendian)              highest on-bit index (zero based)

127                        01111111                                               6

17                         00010001                                            4

7                          00000111                                              2


i[127] = 6,

i[17] = 4, and

i[7] = 2

6-4 = 2

The answer’s highest on-bit index is calculable. This implies an algorithm that reduces the dividend while increasing the quotient.

1) calculate the quotient’ highest on-bit index.

2) calculate the numeric value of the quotient’s highest on-bit index

3) add the numeric value calculated to a running quotient accumulator

4) subtract from the dividend the numeric value * the divisor

5) loop back to 1) until the updated dividend is less than the divisor

6) the final value of the dividend is the division’s remainder

No guessing is involved nor is there a ‘stop when close enough’ guess as in Newton’s and many other divisor inversion methods. The code for this algorithm, even for huge multi-word unsigned integers, lays out easily in Swift.

func divide(var dividend:[UInt64], divisor:[UInt64]) 
    var quotient = [UInt64]()
     * sanity checking for division by zero, empty arrays, and 
     * where the divisor > dividend goes here
    //5) loop until the divisor > dividend
    while compare(dividend, divisor) >= 0{
        //1) calculate the highest on-bit index
        let highestQuotientBit = calculateHighBitIndex(dividend, divisor)
        //2) calculate the numeric value of the highest on-bit
        let dividendPartialValue = shift_1_LeftBy(highestQuotientBit)
        //3) update the value of the quotient collector
        quotient = add(quotient, dividendPartialValue)
        //4 subtract the calculated numeric value from the dividend
        let tooSmallBy = multiply(dividendPartialValue, divisor)
        dividend = subtract(dividend, tooSmallBy)
    //the amount left in the dividend is the remainder
    return (removeLeadingZeros(quotient),removeLeadingZeros(dividend),nil)

In this algorithm I take advantage of the multiplication algorithm discussed and implemented in a previous post. There are several additional helper functions I’ve created to make the divide function’s implementation easier to understand.

The most interesting of these helper functions is calculateHighBitIndex. It calculates the index of the highest on-bit of the quotient for any divisor-dividend pair. To help you understand it, I’ll show the equations for calculating when the difference between the dividend and divisor’s highest on-bit index, described above, is too high by 1.

when a / b = q

if  a <= (b *  (1 << (i[a] – i[b]))) – 1

then i[a] – i[b] is too large by 1

This is a pattern I found by examining every integer division possible using unsigned 8 bit integers. I’ve been running an exhaustive check of all possible UInt64 divisions. It hasn’t failed yet but is obviously taking a long time. I’m also working on a mathematical proof but won’t bore you with it here.

Describing the equations using words, if 1 is left-shifted by the highest on-bit index difference, the result is then multiplied by the dividend, and reduced by 1, we get a value for the largest dividend where the highest on-bit index difference is too large. The source code is as follows.

//calculate the highest on-bit of a multi-word quotient 
//given multi-word dividends and divisors
func calculateHighBitIndex(var dividend:[UInt64], var divisor:[UInt64]) 
    var calculatedIndex:UInt64 = 0
    if dividend != divisor{
        //cleanup the dividend and the divisor before processing
        //by removing any leading zero valued array elements
        dividend = removeLeadingZeros(dividend)
        divisor = removeLeadingZeros(divisor)
        //dividend's highest bit location ( log2 dividend) 
        //for 64 bit array elements
        let dividendLog2 = UInt64(floorLogBase2(dividend[0]) 
                      + (dividend.count - 1 ) << 6)
        //divisor's highest bit location (log2 divisor)
        //for 64 bit array elements
        let divisorLog2 = UInt64(floorLogBase2(divisor[0]) 
                      + (divisor.count - 1) << 6)
        //calculate the inter-highest on-bit index
        calculatedIndex = dividendLog2 - divisorLog2
        //calculate the maximum dividend value yielding the error
        var maxLocation:[UInt64] = subtract(multiply(divisor,
        //check if the calculated index needs to be reduced by 1
        if compare (dividend, maxLocation) <= 0{
    return calculatedIndex

I created the floorLogBase2 function because the built-in log function works on doubles, is imprecise, and there is an easy, efficient algorithm to calculate log base 2 for unsigned ints. The code for this function is

func floorLogBase2(var x:UInt64) ->Int{
    //calculate the numeric value of the highest bit (1,2,4,8,etc.)
    x |= (x >> UInt64(1))
    x |= (x >> UInt64(2))
    x |= (x >> UInt64(4))
    x |= (x >> UInt64(8))
    x |= (x >> UInt64(16))
    x |= (x >> UInt64(32))
    let numericValueOfHighestBit = (x - (x >> 1))
    //lookup log base 2 of the value
    //it is faster to look up the log than calculate it
    return bitLocations[numericValueOfHighestBit]!

The last line of the floorLogBase2 function uses a Dictionary to look up the logarithm. The Dictionary’s key is 2^n and the value is n.

The other helper functions (compare, add, subtract, shift_1_leftBy, and removeLeadingZeros) aren’t that interesting. The source code for them will be part of the open source Swiftly Secure library I’ll be putting on GitHub when its complete.

When I started looking for a way to divide huge multi-word numbers, I wanted to find a way to do computerized division without the guesses required by other modern methods. I found one and a way to implement it in Swift. As I wrote the Swift code, I kept optimal computational practice in mind, but I make no claims regarding how ‘optimal’ this algorithm is compared to others. I plan on doing theoretical (big O) and actual comparisons a little later. First I have to find a way to efficiently raise huge multi-word numbers to huge multi-word powers without repeatedly multiplying the base number by itself. This is the last missing piece to completing Swiftly Secure’s implementation of the socialist millionaire protocol.

[UInt64]^[UInt64] is my next task and posting.


February 10, 2015

Swiftly Secure, Part 2 – Multiplying Huge Numbers

Posted in iPhone development, mac development tagged , , , , , , , at 12:11 am by tetontech

In my previous post I mentioned how two 64 bit numbers could be multiplied together without ever overflowing. The approach taken was a variation of the grade school multiplication algorithm. In this posting I continue my path to an implementation of the Socialist Millionaire protocol used to securely communicate between 2 or more peers. In order use socialist millionaire I will have to multiply numbers that are much too large to fit into a 64 bit integer. This means I’ll need to multiply arrays of numbers by arrays of numbers.

There are algorithms out there for doing multi-word multiplication. Warren, at hackers delight, lays out a C version of Knuth’s grade school algorithm. It works, but has a design point I was unwilling to follow. It requires the arrays being multiplied to consist of half-word numbers rather than full word numbers. I wanted to explore code using arrays of unsigned 64 bit numbers to represent the very long numbers. It seemed a waste to only use 32 bits per number.

With that in mind I sat down to figure out how to apply the multiplication algorithm used in the last post in this new situation. I wasn’t surprised when I found was easily adaptable from multiplying two Swift UInt64’s to multiplying two Swift UInt64 arrays (Please see the graphics and discussion in the previous post to understand the algorithm basics).

Part of the new algorithm implementation includes adding two UInt64’s in situations where they could readily overflow. That meant I needed to create an add method to handle this correctly. It isn’t that complicated but does require the use of bitwise operators and comparisons.

func add(leftAddend:UInt64, rightAddend:UInt64) 
    var carryAmount:UInt64 = 0
    let sum:UInt64 = 0
    //check for overflow
    if ~leftAddend < rightAddend{
        carryAmount = 1
        sum = rightAddend - ~leftAddend - 1
       sum = rightAddend + leftAddend
    return (carryAmount,sum)

This implementation of add checks to see if overflow will happen before doing the addition. If there is no danger of overflow the two addends are combined. If overflow will happen the amount of overflow is stored and the sum is set to the maximum value of a UInt64.

In either case the add function returns the sum and a number representing how much too large the real sum is if it was to fit into a UInt64. We’ll use this carry amount in the multi-word multiplication algorithm.

Another change I made from Warren’s implementation was to have the arrays of numbers be in big endian format. This didn’t add significantly to the complicatedness of the algorithm but is how people ‘normally’ think of numbers. This can make it easier for some to see how the input relates to the algorithm’s output.

If the algorithm is implemented correctly some simple multiplications and their results should match these below. All arrays of numbers are base 2^64 where each array element represents a 64 bit ‘digit’ in big endian bit order.

  • multiply([UInt64.max/2 + 1],[2])     => [1,0]
  •  multiply([1,0,0],[1,1])                          => [0,1,1,0,0]
  • multiply([2,2],[UInt64.max/2 + 1])  => [1,1,0]
  • multiply([UInt64.max, UInt64.max, UInt64.max], [UInt64.max, UInt64.max])          => [18446744073709551615, 18446744073709551615, 18446744073709551615, 18446744073709551615, 1]

In this implementation of the grade school algorithm discussed in the previous post the ‘bit’ size of the multiplicand and the multiplier are unknown. This means we can’t use the nice trick with the << operator and bit masks to create portions of the product we can add together. Instead we’ll collect the product portions directly into an array of UInt64’s.

If we create an array for the resultant product sized to be the sum of the sizes of the multiplicand and the multiplier it will always be large enough to hold the product. Sometimes it will be 1 digit too large but that will always be in the most significant digit location when it does happen. You can see an example of this if you look at the second bullet point of the list above. This is OK since a zero value in that place doesn’t affect the value of the number anyway.

The multi-word multiplication implementation of the algorithm looks like this.

func multiply(multiplicand:[UInt64], multiplier:[UInt64]) 
    let multiplicandSize  = multiplicand.count
    let multiplierSize = multiplier.count
    let productSize = multiplicandSize + multiplierSize
    //create an array that is large enough 
    //to hold the product
    var product = [UInt64](count: productSize, 
                                         repeatedValue: 0)
    //follow the grade school methodology 
    //to do multiplication
    for index in stride(from: multiplierSize - 1, 
                                          to: -1, by: -1){
        let multiplierElement = multiplier[index]
        for subIndex in stride(from: multiplicandSize - 1, 
                                           to: -1, by: -1){
            let multiplicandElement = multiplicand[subIndex]
            //calculate the product and the carry amount
            let partialProduct:[UInt64] = 
        multiplyWithOverflow(multiplicandElement, multiplierElement)
            //calculate the location of the product
            let productIndex = (subIndex + index + 1)
            //calculate the index of the carry amount
            let carryIndex = productIndex - 1
            //calculate the amount to be inserted 
            //into the product and carry locations. 
            //Add the current calculated product to any amount that 
            //was previously carried forward.
            let (carryAmount, productSum) = add(product[productIndex], 
            //the carrySum will never be able overflow.
            let (_, carrySum) = add(product[carryIndex], 
                                      carryAmount + partialProduct[0])
            product[carryIndex] = carrySum
            product[productIndex] = productSum
    return product

In this implementation each partial product is calculated and the overflow is placed in the next higher bit location. The partial product is then added to anything that was ‘carried’ over previously into the product’s location. For both the carryAmount and the partial product the add method described above was used to ensure overflows were handled correctly. While this algorithm isn’t quite as clean as the one in the last post, It is still fairly straight forward.

Since the socialist millionaire algorithm requires a division as one of its steps, my next posting will show an algorithm for multi-word division and subtraction. At this point, it looks like there will be some very interesting ideas to point out.

January 20, 2015

Swiftly Secure, Part 1 – Large Number Multiplication

Posted in iPhone development, mac development, Uncategorized tagged , , , at 8:52 pm by tetontech

I have a swift iOS project where I want users to be able to communicate between their devices by sharing data via a server. I want their communications to be encrypted in such a way that no one can decrypt them except the two parties communicating. In fact, I want their communications to be encrypted end-to-end without them being de-cryptable when they are on the server. To accomplish this, I’ve decided on using the Socialist Millionaire protocol since it handles both encryption and authentication.

Doing encryption of this type means I’m going to need to multiply integers that are too large to fit in any of the standard Swift or Objective-C integers. I explored some existing large number libraries in C, but the most commonly used ones appear to be GPL or LGPL licensed. I won’t use libraries under those licenses in a closed source app so I decided to create something of my own.

In this posting I’m going to show you a part of what I’m creating — how to multiply numbers in swift without encountering overflow problems. Overflow issues aren’t very common in business situations, numbers there tend to be small compared to the size of a 64 bit signed integer, but in some scientific computation situations and in my Socialist Millionaire implementation encryption overflow is an issue. Sampling from a random number stream and multiplying the results is another source of overflow situations. In fact, random sampling and multiplying has a very high probability of overflow if the random number generator yields results that are close to being evenly distributed.

I want to keep the example in this post simple, so I will show you an implementation of the grade school method. Multiplying 99 x 99 the way I was taught in grade school (multiply, carry, and then add) is a good place to start.


There is an alternative way of doing this same multiplication (multiply, add, then carry). In this example each time 9 is multiplied by 9 the result is written on a new line. All except the first partial product are shifted left —  one place for the second and third product, two places for the fourth product.


The second method is the one I’m going to show in this posting. An example of bits being manipulated is helpful. To make it easier to understand we’ll stick with 8 bit numbers where each nibble (4 bits) represents one ‘digit’ for multiplication purposes.


Following the second grade school multiplication method using nibbles, lets multiply 255 x 255. Multiplying those two numbers should overflow an 8 bit result but we’ll keep that from happening without loosing any data.

Keep in mind that 0b1111 x 0b1111 = 0b11100001 (15 x 15 = 225).
The two part base 256 product, one 8 bit number representing the ones place and the other representing the 256’s place, is the result of left shifting the upper half of two nibble pairs and adding them to their corresponding bottom halves,

1111 << 4 + 1110 yields 11111110 and

0000 << 4 + 0001 yields 00000001.

The code example below follows the same pattern as the 8 bit multiplication without overflow table and uses the constant and variable names listed in the first column.


 * I did this big endian since it was easier to think about this part of the algorithm this way
func multiplyWithOverflow(multiplicand:UInt64, multiplier:UInt64) ->[UInt64]{
    //multiply to get all addends
    let lowerLowBits = (multiplier & bottomHalfBitMask) 
                       * (multiplicand & bottomHalfBitMask)
    let lowerHighBits = (multiplier & bottomHalfBitMask) 
                       * (multiplicand >> 32)
    let upperLowBits = (multiplier >> 32) 
                       * (multiplicand & bottomHalfBitMask)
    let upperHighBits = (multiplier >> 32) 
                       * (multiplicand >> 32)
    //get the 4 bit sums of the addends. There are 4. Some may be zero
    let bottom = lowerLowBits & bottomHalfBitMask
    let middleBottom = (lowerLowBits >> 32) + (lowerHighBits & bottomHalfBitMask) 
                  + (upperLowBits & bottomHalfBitMask) + (bottom >> 32)
    let middleTop = (lowerHighBits >> 32) + (upperLowBits >> 32) 
                  + (upperHighBits & bottomHalfBitMask) + (middleBottom >> 32)
    let top = (upperHighBits >> 32) + (middleTop >> 32)
    //combine the 32 bit sums to make two 64 bit values
    let bottom2N64 = (middleBottom << 32) + bottom
    let top2N64 = (top << 32) + (middleTop & bottomHalfBitMask)
    return [top2N64,bottom2N64]

If you want to use this overflow protection in a situation where overflow is infrequent, business, games, some simulations, etc., you will want to add an if statement to this code or allow the multiplication to overflow and then handle the situation as an error. Checking to see if two numbers will overflow before multiplying them turns out to be fairly easy. All you have to do is find the location of the highest bit in both numbers and add those locations together. If the location sum is greater that 63 the two numbers will overflow when multiplied.

In my next post, I’ll show how to represent huge numbers as arrays of UInt64’s and multiply those together, another component I need when implementing the Socialist Millionaire protocol.

October 24, 2014

Swift, Reflection, Downcasting, Protocols, and Structs: A solution

Posted in iPhone development, mac development tagged , , , at 10:01 pm by tetontech

Currently, Swift does not have the ability to do full reflection. It can, through the mirror struct, examine property names and values. Swift does not allow you to set the values directly. You can, however, instantiate a struct based on the structs type but the compiler will crash if you attempt to do this in any anonymous way. In addition to no real reflection abilities, Swift objects and structs do not support key-value coding. It turns out that a solution to some of the reflection issues in Swift is the addition of key-value coding to structs. An additional restriction to doing reflection in Swift is the inability to downcast an instance who’s type Any or AnyObject to a known protocol. It may be that Apple is resolving these issues but that doesn’t help those of us who need to do reflection now. Let’s look at what is available in Swift. This will show us its current limitations.

The reflect function and MirrorType

The reflect function and MirrorType structure were designed by Apple to display information for the Xcode IDE. Xcode uses these to show debugging information. This is why the results are read-only. The example below shows a struct being examined. The struct is not complex. It represents a person and has name, age, optional height, and calculated description properties.

struct Person:Printable{
    var name:String
    var age:Int
    var height:Double?
    var description:String {
        return "name:\(self.name) age:\(self.age) height:\(self.height)"

Using the standard MirrorType and the reflection function we can get almost all of the properties and their values. Unfortunately there are problems accessing both the description property and working with the height. The description doesn’t show up in the children and the value returned for the height is an optional.

let aPerson = Person(name:"Sally", age:35, height:5.9)
let structMirror = reflect(aPerson)
let numChildren = structMirror.count
println("child count:\(numChildren)")
for index in 0..<numChildren{
   let (propertyName, propertyMirror) = structMirror[index]
   println("name: \(propertyName) value: \(propertyMirror.value)")

Run Results:

child count:3
name: name value: Sally
name: age value: 35
name: height value: Optional(5.9)


The height being an optional would not be a problem except there is no way to ask if something is an optional. If there was, then we could eventually get the underlying value. Since there isn’t a way to detect an optional I could not use this approach in my project. I needed the actual value. I needed it to corrctly building a piece of Sqlite insertion SQL. You will probably run into the same limitation in your projects.


In Swift an instance can be created from the struct or object’s description. Doing this to create a new Person is shown below.

let child = Person.self(name: "bob", age: 3, height: 2.5)

This works great as long as you know ahead of time what type of instance needs to be created. It is possible to store the Person.self value, it’s type is Metatype, in a constant, variable, or collection and create an instance using the variable.

let personType = Person.self
let personFromType = personType(name: "jessie", age: 14, height: 5.2)

Creating collections of different types of Metatypes, a feature needed in most reflection based coding, is also possible. It does require that each struct implement a common protocol. For this example I’ve created the Thing protocol. It declares that any Thing must have a name of type string.

protocol Thing{
    var name:String { get set }

I’ve modified the Person struct to implement Thing and created a Dog struct that is also a Thing.

struct Person:Printable,Thing{
    var name:String
    var age:Int
    var height:Double?
    var description:String {
        return "name:\(self.name) age:\(self.age) height:\(self.height)"
struct Dog:Thing{
    var name:String
    var breed:String
protocol Thing{
    var name:String { get set }

Now an Array or a Dictionary can be created that holds both Person and Dog Metatypes.

let initializerList:[Thing.Type] = [Person.self, Dog.self]
let initializerDict:[String:Thing.Type] = ["Person":Person.self, "Dog":Dog.self]

It seems strait forward to initialize a Person. The following code seems like it should work but fails to compile.

let aMetaType = initializerDict["Person"]!
let anotherPerson = aMetatype()

The compiler failure says that a Thing doesn’t have an init function. That is true. The Thing protocol has no init function with no parameters defined. We can add one and modify the structs to also have init functions with no parameters. Now the compiler error goes away, but to do this well all the properties of the structs have to either be Optionals or have meaningful default values. Changing the properties to Optionals causes the problem mentioned earlier regarding getting actual values out of Optionals without know what type they are.

Adding an init to the Thing protocol causes another problem. Initializing a struct from the stored Metatype causes the compiler to segmentation fault (crash). The compiler should have either failed to compile the code since Thing doesn’t have an actual init function or a virtual lookup should have been done to call the Person’s init function.

So we have hit three dead ends using Swift’s standard behavior. We can’t get actual values from optional properties, we can’t create instances from commonly stored Metatypes, and the compiler crashes when we try to do anything complex.

Another reflection issue in Swift is the inability to downcast from Any to a custom protocol type, another common need when using reflection in code. You can downcast to a standard type like String (anAny as String) and even a custom type like Person (anAny as Person). But there is a compilation failure if you try to downcast to Thing (anAny as Thing). The error states that Any and Thing are unrelated. This indicates that custom protocols are not an Any.

What useful reflection can be done under these limitations?

A Solution

As mentioned in a previous post, I’m writing a library to work with Swift structs in the same way that CoreData works with objects. To create this library I  must do reflection. I need to convert structs into SQL statements and Sqlite result sets into Arrays of structs who’s types are unknown. To get around Swift’s current reflection limitations I applied key-value coding. The custom protocol KeyValueCodable makes this possible.

protocol KeyValueCodable{
    var KVTypeName:String {get}
    subscript(index:String)->Any? { get set }
    func instantiate()->KeyValueCodable
    func downCastFromAny(anAny:Any)->KeyValueCodable?

KeyValueCodable includes an initializer without any parameters, but it is only used by KeyValueCodable‘s instantiate function so we avoid the compiler crashing problem. It overcomes the issue of retrieving actual values from optionals by having a subscript that can return and set the values of any type of property. It overcomes the down casting problem by having each struct do its own downcast. It also overcomes a previously unmentioned reflection problem. You can’t get a string representation of a struct’s name from Swift’s standard reflection behavior.

Using KeyValueCodable puts more responsibility on the programmer than is usually required in other languages, but it makes both reflection and key-value coding possible. Here is the Person struct modified to implement the KeyValueCodable protocol. There is much more code in Person than there was before, but most of it is boiler-plate code. It can be copied, pasted, and modified.

struct Person:Printable,KeyValueCodable{
    let KVTypeName = "Person"
    var name:String?
    var age:Int?
    var height:Double?
    var description:String {
        return "name:\(self.name) age:\(self.age) height:\(self.height)"
    func instantiate() -> KeyValueCodable {
        return Person()
    func downCastFromAny(anAny: Any) -> KeyValueCodable? {
        if isKVCodable(anAny){
            let mirror = reflect(anAny)
            let numChildren = mirror.count
            var aPerson = Person()
            for index in 0..<numChildren{
                 let (propertyName, propertyMirror) = mirror[index]
                 switch propertyName{
                 case "id":
                     aPerson["id"] = propertyMirror.value as? String
                 case "name":
                     aPerson["name"] = propertyMirror.value as? String
                 case "height":
                     aPerson["height"] = propertyMirror.value as? Double
                 case "age":
                     aPerson["age"] = propertyMirror.value as? Int
                     0//do nothing
             return aPerson
         return nil
     subscript(index:String) -> Any?{
            switch index{
            case "name":
                return name
            case "age":
                return age
            case "height":
                return height
            case "KVTypeName":
                return KVTypeName
                return nil
            switch index{
            case "name":
                name = aValue as? String
            case "age":
                age = aValue as? Int
            case "height":
                height = aValue as? Double
                0//do nothing

Person now has a subscript which can be used to get and set the value of any parameter. This is also true when the Person has been upcast to a KeyValueCodable. Person can now be ‘downcast’ from an Any. This is done by creating a copy of the data in the Any and applying it to a new Person. This isn’t such a big deal since Swift structs are copied every time they are passed to a function anyway.

There is a function, isKVCodable, called in the downCastFromAny function. It uses reflect and MirrorType to look for the KVTypeName property required to be part of each KeyValueCodable.

func isKVCodable(possibleCodable:Any?)->Bool{
    if let anActualAny = possibleCodable?{
        let mirror = reflect(anActualAny)
        let numChildren = mirror.count
        var aCodable:KeyValueCodable?
        //discover if is a codable
        for index in 0..<numChildren{
            let (fieldName, fieldMirror) = mirror[index]
            if fieldName == "KVTypeName"{
                return true
    return false

Using KeyValueCodable I’ve been able to overcome Swift’s limitation for my reflection heavy project. I look forward to making it even more generic and useful for everyone. Suggestions are appreciated.

In another posting I will describe how to use reflection to find and access a struct’s methods.


October 22, 2014

Swift, C libraries, and Mapping Swift types to C pointer types

Posted in iPhone development, mac development tagged , , , , at 11:02 pm by tetontech

In my last posting I described a swift library, SwiftlyDB, I wrote to insert data into a SQLite database using the sqlite3 library. I promised some ‘lessons learned’ postings about what I picked up during the creation of that library. This is the first of those postings.

In Swift and Objective-C SQLite is accessed using a C library. This means a whole series of pointers are needed to move data back and forth between Swift and C. Thankfully Xcode will handle most, but not all, required Swift-to-C pointer conversions for you. When it doesn’t You will need to get used to COpaquePointer, UnsafePointer, and UnsafeMutablePointer. These Swift types represent C pointers, const pointers, and pointer pointers (**) respectively.


COpaquePointers represent pointers to any non-standard C data type. They can be a simple pointer or a pointer to an array, but they are not used to point to int, char, double, and other primitive types. When creating a Swift variable that refers to a sqlite instance, a COpaquePointer is used since a sqlite3 pointer is not a primitive type such as int or char. I assume the Swift pointer is called an opaque pointer since there is no way to tell what kind of C construct it represents just by looking at it. If you can’t see through glass to what is behind it,  the glass is opaque, right?

One result of calling sqlite3_open is the population of a COpaquePointer with the sqlite instance. This is done by passing the opaque pointer to the sqlite3_open function. The following two-line example shows a pointer being created and passed to the that function.

    var theDB:COpaquePointer = nil
    sqlite3_open((fileLocation as NSString).
                          cStringUsingEncoding(NSUTF8StringEncoding), &theDB)

Not so bad really. There is that & operator confusing the situation, and the conversion of an NSString to a C string to muddy the waters, but all in all, not too bad….until you look at the signature for sqlite3_open function.


Swift function signature – sqlite3_open(filename: UnsafePointer<Int8>,

ppDb: UnsafeMutablePointer<COpaquePointer>) -> Int

C function signature – int sqlite3_open(const char *filename, sqlite3 **ppDb )

Now things look much messier. The second parameter in the Swift signature seems to be a mess. The clue to figuring out what it means is the parameter name, ppDb. ppDb stands for Database pointer pointer. So the UnsafeMutablePointer<COpaquePointer> declaration must match up with the sqlite3** type. In the case of sqlite3_open, and in many other C functions, pointer pointers (**) are used to retrieve pointers to items generated during the function’s execution that are not returned. The UnsafeMutablePointer name was selected to reflect the in-and-out  nature of the C pointers represented by UnsafeMutablePointers. The pointer is unsafe since it might be null, and it is mutable since what the pointer is pointing at can change (it starts out pointing at null and can end up pointing at a swift3 instance). Swift provides the & operator to generate UnsafeMutablePointers from COpaquePointers. Don’t try to instantiate one yourself. Using the init method of UnsafeMutablePointer didn’t work at the time I wrote the library.


The sibling to the changeable UnsafeMutablePointer is the unchangeable UnsafePointer. In C terminology these are constant (const) pointers. The value of what they pointing at can be changed, but they can not be changed to point at a different memory location. The first parameter of sqlite3_open, seen in the Swift function signature above, is an UnsafePointer to an 8bit int. This must match the C parameter type of const char *. That is confusing until you understand a C character is the same thing as a C 8bit int.

When dealing with any C library, keeping these mappings between C and Swift pointer types in mind makes Swift-to-C library calls much easier.

August 20, 2014

Swift, Extensions, Protocols, and Operator overloading

Posted in Uncategorized tagged , , , , , at 4:39 pm by tetontech

I’m working on a Swift matrix manipulation library. Since I want that library to be flexible enough to be used outside of my planned use, a simulation engine, it needs to be able to handle complex numbers. Swift doesn’t have representations for imaginary or complex numbers so I created one. You can get the source for the entire library at my gitHub repo. I call the library SwiftlyComplex. Regardless of why I created the library, there are some Swift programming concepts the library illustrates.

I wanted my representation of complex numbers to be able to have Int and Double type parts but not String or other invalid types. Swift’s implementation of Int and Double have no common base class so I could have done something silly with Swifts Any type and do a bunch of run-time checking or I could have overloaded all my functions to handle all possible combinations of Int and Double. Both of these are bad ideas. For example, if the complex number’s init function had two parameters, one of the real component and one for the imaginary, using the overloading idea I would need to create four init methods that do essentially the same thing, initialize the complex number’s properties. The overloading approach would also make it difficult to declare the complex number’s property types as well. Not a good approach.

So what I did instead was create a BaseNumeric protocol.

protocol BaseNumeric {
    func asDouble() -> Double
    func asInt() -> Int
extension Int:BaseNumeric {
    func asDouble() -> Double{
        return Double(self)
    func asInt() -> Int{
    return self
extension Double:BaseNumeric {
    func asDouble() -> Double{
        return self
    func asInt() -> Int{
        return Int(self)

As you can see, I used this protocol to extend both Int and Double. This allowed me to make one version of all of the complex number’s init and other functions. I also had BaseNumeric add a couple of helper functions to Int and Double to return Double and Int versions of the number. This reduced code duplication in my complex number representation.

BaseNumeric also needed to override the -, +, *, and / operators. They are all very similar. We’ll look at just the override for the – operator.

func - (lhs:BaseNumeric, rhs:BaseNumeric) -> BaseNumeric{
    if lhs is Double || rhs is Double {
        return lhs.asDouble() - rhs.asDouble()
        return lhs.asInt() - rhs.asInt()

This version of the – operator can be placed between two BaseNumeric values, be they Ints, Doubles, or some combination of those, and returns a BaseNumeric. The operator checks the type to see if either BaseNumeric is a Double. If at least one is, then the result is calculated as a Double. If not, the result is calculated and returned as an Int BaseNumeric.

With the BaseNumeric protocol extending both Int and Double, I could now create a struct to represent complex numbers. I called it Complex. Complex implements Swift’s standard Printable protocol so using println() is easy. Implementing Printable meant I needed to add a calculated property of type String called description.

Following this same pattern, I added two custom calculated properties for the common complex number calculations modulus and conjugate. While you may not be dealing with complex numbers yourself, calculated properties in your code will work the same way. They are declared as variables, the return type is declared, the calculation is done, and a value is returned.

import Foundation

struct Complex:Printable{
    var real:BaseNumeric
    var imaginary:BaseNumeric
    var description: String{
        return "\(self.real) + \(self.imaginary)i"
    var modululus: Double{
        let squaredReal = real * real
        let squaredImaginary = imaginary * imaginary
        return sqrt((squaredImaginary + squaredReal).asDouble())
    var conjugate: Complex{
        let inversImaginary = imaginary * -1
        return Complex(real: real, imaginary: inversImaginary)
    func combine(rhs:Complex, combineBehavior:(BaseNumeric, BaseNumeric) -> BaseNumeric) -> Complex{
        var realPart = combineBehavior(self.real, rhs.real)
        var imaginaryPart = combineBehavior(self.imaginary, rhs.imaginary)
        return Complex(real: realPart, imaginary: imaginaryPart)

I also added a combine function. This function allowed me to do both addition and subtraction of my Complex structs with one set of code rather than duplicate the code for both behaviors. To accomplish this, I needed to pass an instance of a Complex to combine with the ‘self’ instance, and a closure, called combineBehavior in the parameter list. The closure would either add or subtract the component pieces of the Complex structs depending on if I wanted addition or subtraction. Calling the combine function in an overloaded version of the + operator shows how to pass the closure.

func +(lhs: Complex, rhs: Complex) -> Complex{
    return lhs.combine(rhs, combineBehavior: {(leftValue:BaseNumeric,rightValue:BaseNumeric) -> BaseNumeric in
        return leftValue + rightValue

Since + is defined by Swift as an infix operator, I didn’t need to declare it myself. For a discussion of overloading standard operators and creating custom operators please see my previous posting on that topic.

In addition to the + and – operators, I overloaded the  * and / operators for my Complex class. They calculate the multiplication and division of complex numbers directly since there is not common code between these operators that could be shared.

Now I can create complex numbers using the Complex structure.

     let first = Complex(real: -2, imaginary: 3)
     let second = Complex(real: 1.0, imaginary: 2.0)

and manipulate them using the overloaded operators.

     let difference = first - second
     println("difference: \(difference)")
     let product = first * second
     println("product: \(product)")
     let quotient = first / second
     println("quotient: \(quotient)")

This makes it much easier to create, manipulate, and display complex numbers.

July 15, 2014

Swift to JavaScript and JavaScript to Swift. A round trip.

Posted in Uncategorized tagged , , , , , at 9:12 pm by tetontech

Edit: Since originally writing this post I have Created the SwiftlyHybrid and AndyHybrid libraries and put them on gitHub. If you are interested in the topic discussed here I would suggest also reading the SwiftlyHybrid and AndyHybrid follow up posting.

In a previous post I showed how to make a call from JavaScript to Swift. Take a look there for a more in-depth discussion of the code to accomplish that data transfer. This example expands on what I did in that post by showing how to make a call from JavaScript to Swift, do a calculation, and then pass the results back to JavaScript. The source code is very similar. It uses one method, evaluateJavaScript(), of the WKWebView class that wasn’t available in Apple’s previous Swift beta.

In the view controller’s userContentController method we’ll need to have access to the WKWebView created in the viewDidLoad method. This requires the addition of a WKWebView attribute to the ViewController class. After trying a couple of experimental ideas I remembered the correct, Swifty way to do this. I couldn’t create the WebView on the same line as the attribute was declared since the initializer for the WKWebView isn’t as simple as adding some integer attribute (var someInt = 3). Instead the initializer needs a frame and a WKWebViewConfiguration. Because of this the WKWebView must be initialized in the viewDidLoad method (This may change if Apple adds a WKWebView to Interface Builder).

The Swift way to declare an attribute and initialize it in something other than an init method is to make the attribute optional using the ? operator.

class ViewController: UIViewController, WKScriptMessageHandler {
    var theWebView: WKWebView?

In the viewDidLoad method the WKWebView can now be created using the WKWebView function. Once theWebView has been set, the ! operator is needed to declare that we know theWebView attribute is not nil.

(Warning: the functionallity of WKWebView has changed since this code was written. You must move all resources (html, JavaScript, Css, images, and other files) into the temp directory or WKWebView will not load the resources. This may change in the future as WebKit changes or it might not.)

    override func viewDidLoad() {
        var path = NSBundle.mainBundle().pathForResource("index", 
                               ofType: "html")
        var url = NSURL(fileURLWithPath: path)
        var request = NSURLRequest(URL: url)

        var theConfiguration = WKWebViewConfiguration()
                                   name: "interOp")

        theWebView = WKWebView(frame: self.view.frame, 
                             configuration: theConfiguration)


As in the previous example, the userContentController() method must be implemented to handle the messages captured by the script message handler that was added to theConfiguration. In this example the message’s body, the data sent from the JavaScript is interpreted as an NSDictionary since the JavaScript sends an associative array.

    func userContentController(userContentController: 
       didReceiveScriptMessage message: WKScriptMessage!) {
        let sentData = message.body as NSDictionary
        let aCount:Int = Int(sentData["count"] as NSNumber)
        theWebView!.evaluateJavaScript("storeAndShow( \(aCount + 1) )", 
                                        completionHandler: nil)

The other change to the previous example is the addition of the call to theWebView’s evaluateJavaScript method. It has two parameters; a string that is the Javascript to be executed, and a function or closure that will be notified once the JavaScript completes. In this example I don’t need to know when the JavaScript completes so I passed nil as the second parameter.

The javascript for this example is strait forward; an onclick listener function to send a message to the Swift message handler, and the storeAndShow function that the Swift code will call to send a message back to the JavaScript.

var count = 0

function sendCount(){
    var message = {"count":count}

function storeAndShow(updatedCount){
    count = updatedCount
    document.querySelector("#resultDisplay").innerHTML = count

For my own code I would send a Dictionary back to the JavaScript where it would be used as an associative array. I left that out of this example since I didn’t think it was necessary to show.

Overall, the interaction between Swift and Javascript using the WKWebView is more strait forward than using the old UIWebView. It is nice to have a JavaScript way to directly call to Swift. I also like the selection of JSON as the data transfer format for the JS to Swift communication. It reflects the decision I made to adopt that format for QCHybrid years ago. It would be better if the values in the dictionary knew their type so casting using the as operator wasn’t needed but I can live with it the way it is.

July 7, 2014

Swift, C libraries, and a Speed Test

Posted in iPhone development, mac development tagged , , , , , , , , , at 7:20 pm by tetontech

In a previous post I showed how to statically link a C library into a Swift app. I mentioned in that posting that converting data for use in libraries written in other languages can be costly. I have done some testing by passing 3 basic data types between Swift and C. The results are very interesting and not what I would have predicted based on calling C functions from other languages I’ve used.

The three types I tested were Ints, Doubles, and Strings. I did the test by calling an echo function for each type in both Swift and C. I supposed that calling the C echo function would be slower that calling the Swift echo function in each case. This was not so. It was faster to convert a Swift Int to a c int, pass it to a C function, and then convert the returned C int into a Swift Int than to call the Swift echo function that required no conversion. The difference was not huge, around 300 milliseconds for 100,000,000 calls, but it was consistent.

Doing conversions for Doubles, passing them to a C function, and converting the resultant c double to a Swift Double was also faster than calling a Swift function that echoed a Swift double it was passed. Once again the difference was not huge. There was around an 80 millisecond difference.

The Swift String to char* conversion is messy so I figured converting a Swift string and passing a char*  would be slow. It was so slow that I reduced the number of function calls I was timing to 1,000,000. Making that many calls it was around 12 times slower to convert a Swift String to a char*, pass the char* to C, and convert the resultant char* back to a Swift String.

So what conclusions do I draw? The compiler is currently optimizing C calls requiring number conversions slightly more effectively than the Swift calls. Because of this, if all I’m passing are simple things like Ints and Doubles I can go ahead and use C libraries without much concern. If I’m passing more complex things like Strings or Structs, I would avoid using them in C calls when possible.

Here is the code for the Swift and the C echo functions.

    func doSwiftIntStuff(anInt:Int) -> (Int){
        return anInt
    func doSwiftDoubleStuff(aDouble:Double) -> (Double){
        return aDouble
    func doSwiftStringStuff(aString:String) -> (String){
        return aString
    int doIntStuff(int anInt){
        return anInt;

    char* doStringStuff(char* aStr){
        return aStr;

    double doDoubleStuff(double aDouble){
        return aDouble;

Here is an example of converting and passing a Swift Int

    var initialTime = NSDate()
    let aNum = 3
    for index in 0..100_000_000 {
        let aResult = Int(doIntStuff(Int32(aNum)))
    println("Swift result C int: \(initialTime.timeIntervalSinceNow)")

Here is an example of converting and passing a Swift String. Notice that this example will only handle ASCII strings.

initialTime = NSDate()
for index in 0..1_000_000 {
    var ascii = aString.dataUsingEncoding(NSASCIIStringEncoding, 
    var stringAsChars = CChar[](count:ascii.length, repeatedValue:CChar(0))
    ascii.getBytes(&stringAsChars, length:ascii.length)
    let aResult:String = String.fromCString(doStringStuff(&stringAsChars))
println("Swift result C string: \(initialTime.timeIntervalSinceNow)")

July 3, 2014

Swift and Statically Linking C libraries

Posted in iPhone development, mac development tagged , , , , at 5:26 pm by tetontech

In preparation for creating a simulation engine more robust and current than the simple one I described in a previous post I decided to do some sandboxing of how to statically link and use an existing C library.

Rather than use something complex I created a simple C library that has one function, doStuff. This function is declared in the StuffStatic.h header file

//  StuffStatic.h
//  StuffStatic

int doStuff(int anInt);


and defined in the StuffStatic.c implementation file.

//  StuffStatic.c
//  StuffStatic

#import <stdio.h> 
#import "StuffStatic.h"

int doStuff(int anInt){
    int result = anInt * 2;
    printf("the result is %d\n",result);
    return result;

This code was compiled into libStuffStatic.a.

To use this library in a Swift app I added the libStuffStatic.a file and the StuffStatic directory containing the StuffStatic.h file to the project by dragging them into the Supporting Files group.

Interestingly, Xcode didn’t ask if I wanted to add the bridging header file I knew would be needed to make the C calls from within Swift. Rather than go through the process of manually adding a bridging file I used Xcode to create a junk.c file. This triggered the creation of the bridging header file and made all of the changes to the project required to use it. I then deleted the junk.c file from my project.

The bridging header file is used to do an import of the header files for the library. Any header from the library you include in this file automatically makes available anything defined in it to Swift. Because of this you can make calls to the functions in the header files directly in any Swift file without worrying about doing an include statement.

Since my swift project was just a sandbox project I decided to use the doStuff function directly in the ViewController’s viewDidLoad method. I wanted to simulate a number being calculated in Swift, passed to C, and a returned C int being used in Swift.

override func viewDidLoad() {
        let aNum = 3
        let aResult = Int(doStuff(Int32(aNum)))
        println("Swift result: \(aResult)")

Xcode won’t do autoboxing for us so we have to do it ourselves. To convert the Swift Int aNum to a C int I passed aNum to the Int32 constructor. doStuff could then use it directly. Since doStuff returns a C int I passed its result to Swifts Int constructor and stored the new Swift Int in the aResult constant.

When data types are bridged between languages there is a computational speed cost. I haven’t yet tested what this cost is for Swift-to-C and C-to-Swift bridging. That is on my plate for next week.

June 30, 2014

Swift, NSOperationQueues, Closures, and Threading

Posted in iPhone development, mac development tagged , , , at 3:49 pm by tetontech

In a previous posting I showed how to inherit from NSOperation to do work in background processes using NSOperationQueues. In another, I showed how to use Grand Central Dispatch, GCD, to do threading. In this post I’ll give a simple example of using NSOperationQueues without NSOperations.

For this example I created a single view application, added a label to the view using Interface Builder, and added an IBOutlet for the label called ‘theLabel’ to the ViewController for the view. theLabel can only be updated by the main application thread. This means that inside the code running in the background there must be a a call that runs code in the main application thread.

To take advantage of Swift’s closures, this example uses the NSOperationQueue method called ‘addOperationWithBlock.’ Blocks are the Objective-C equivalent to Swift’s closures. Line’s 2 and 4 show the addOperationWithBlock method being used.

Line 2 adds a closure to a background queue that was created on line 1. The code in the closure will be run on a background thread. Line 4 adds a closure to the main thread’s queue for execution. Line 4 does this by taking advantage of the NSOperationQueue class method ‘mainQueue.’ mainQueue returns the queue for the application’s main thread. This means that anything in the closure defined on lines 4 – 6 will execute in the application’s main thread.

1       var backgroundQueue = NSOperationQueue()
2       backgroundQueue.addOperationWithBlock(){
3           println("hello from background")
4           NSOperationQueue.mainQueue().addOperationWithBlock(){
5               self.theLabel.text = "updated from main thread"
6           }
7       }

By creating a closure within a closure you can execute code in a background thread and after it has completed you can execute code in the main or ‘UI’ thread. You can also use if statements to update the UI in different ways depending on what happens in the background thread.


Next page

%d bloggers like this: