February 1, 2016

Swiftly Idle

Posted in Uncategorized at 9:00 pm by tetontech

With the release of the open source Swift compiler, it becomes feasible to write Swift server-side apps for Linux. Server-side apps require two basic components, parallel processing (threading), and the ability to never exit.

While these two requirements are not scheduled to be fully ready for the Linux version of the compiler until Swift 3.0, I wanted to get ahead of the curve and start experimenting now. To do this I decided to design and create, using the Swift 2.2 open source compiler on OS X, an app I’m calling Courier.

Since Courier is intended to run constantly without consuming CPU resources I thought I’d share a code example that keeps the main thread in an idle state but allows the main thread to respond to dispatches from GCD. This fundamental ability is the basis for all servers and other types of monitoring apps…even GUI apps and OS’s.

Below is the code for a function I’m calling waitAndListen. It will setup listening for changes to one of the server’s directories. When a change is detected, it will report what happened.

To make this work, all the listening has to be set up early in the source code. To make the waitAndListen example easier to understand, I’ve moved the code for setting up listening into a function called watchDirectory. We’ll look at that function a little later.

1 func waitAndListen(){
2    //call a custom function to watch for changes in the "stuff" directory.
3    let source = watchDirectory("stuff")
4    //setup the current thread's runloop in an infinite loop 
5    //to keep the app going
6    while(true){
7        CFRunLoopRunInMode(kCFRunLoopDefaultMode, 3600.0, true)
8        print("looping")
9   }
10 }

Line 6 is where the good stuff starts. It is the beginning of an infinite loop. Don’t worry. It won’t soak up your CPU cycles. Line 7 makes sure of that. Line 7 is a special function call. What it does is make a OS blocking call that returns every hour (the second parameter) or when the ‘stuff’ directory is changed, which ever comes first. Until then it sits and waits. The first argument isn’t particularly important to this discussion, but the third parameter, a boolean, is used to indicate if CFRunLoopRunInMode should exit after it is interrupted. I’ve set it to true for this example to keep things simpler.

There are more complicated examples of using CFRunLoopRunInMode on the web. Those usually check the return value of CFRunLoopRunInMode to determine if the application should exit. Since I’m writing something that should never exit of its own choice, that kind of check is unneeded.

In short, lines 6 – 9 are all that is needed to create an application designed to never exit normally.

One nice thing about using CFRunLoopRunIn Mode to put the main thread into a waiting state is the main thread can still be used for computation. The watchDirectory function, called in line 3, makes the application to wake up the main thread and use it when changes are made to the ‘stuff’ directory. watchDirectory is longer and more complicated than the code in waitAndListen. We’ll take it a step at a time.

In line 2 below, a file descriptor is created. This descriptor refers to the ‘stuff’ directory and is used later as part of the code required to listen for changes to the ‘stuff’ directory.

Line 4 is where we get a reference to the main thread. If you don’t want to use the main thread for handling changes you can use GCD’s dispatch_get_global_queue instead. If you choose to use the global queue rather than the main thread, the main thread will never be wakened by events. Instead, the background thread will become active each time a change is made.

Grand Central Dispatch (GCD) is a dispatching engine. Line 5 adds a new, non-preexisting event source to GCD. The _VNODE constant tells GCD the type of events it should dispatch are file and directory events. The descriptor for the directory we want to watch is passed as the second parameter so GCD knows which directory to monitor.

The third parameter consists of a series of constants that are assembled using swift’s bitwise OR operator. The options used in this example sets up the dispatch source to include all types of file and directory events. You can restrict these to a smaller set if you choose. Lastly, the queue to dispatch to is passed in as the last parameter.

With a dispatch source added to GCD, GCD needs to be told what to do when a change is made to the directory being watching. That is done by adding the closure beginning on line 7 as a dispatch handler.

1 func watchDirectory(directoryPath: String) -> OS_dispatch_source{
2    let directoryDescriptor = UInt(open(directoryPath, O_RDONLY))
3    //attach the listener to the main thread.
4    let queue = dispatch_get_main_queue()
5    let dispatchSource = dispatch_source_create(DISPATCH_SOURCE_TYPE_VNODE, 
                 directoryDescriptor, DISPATCH_VNODE_DELETE 
 6   //assign a closure to be the listener for directory change events
 7   dispatch_source_set_event_handler(dispatchSource){
 8       let eventType = dispatch_source_get_data(dispatchSource)
 9       //detect the different types of changes and handle them
 13          )
 14           {
 16               //handle removing and deleting
 17            }
 18      //when something is added or something is removed from this 
 19      //directory it is a WRITE
 21      {
 22           //handle a write
 23      }
 24  }
 25  dispatch_source_set_cancel_handler(dispatchSource){
 26       close(Int32(directoryDescriptor))
 27  }
 28  dispatch_resume(dispatchSource)
 29   return dispatchSource
 30 }

Lines 7 through 24 consists of the code GCD executes each time a change is made to the ‘stuff’ directory. The example above varies its behavior depending on the type of event. It handles deletions and renamings in one way and adding files and directories in another. Before it can handle the events differently, the code must determine the type of event that happened. To do this,  the dispatch_get_source_data function (line 8) is called each time a change is made.

Once eventType is set to the type of event that happened, the example uses if conditional statements to handle the various types of events. The event could be directory or file creation, deletions, renaming, etc. You can see the if statements for this example on lines 10 and 20.

There are a bunch of events associated with each if statement. Since I’m preparing to run this code on both OS X and Linux, I’ll need to experiment with the event types on Linux before I can decide exactly how to break up the types across my applications’s statements. I’m assuming there will be differences in how Linux handles these events compared to OS X.

If you want to cancel watching the directory, the dispatch_source_set_cancel_handler must be called. The example shows that function cleaning up the file descriptor that refers to the directory.

Line 28 is very important. If you don’t resume/restart the dispatching engine, no events will ever be captured and dispatched to the listener you’ve areated. In other words, your code for handling the changes to the directory won’t be called when the directory is changed.

Overall the API for watching a directory or file isn’t too bad.

Now….back to creating Courier. :)


November 12, 2015

Adding Custom Class Properties with Swift Extensions

Posted in Uncategorized at 10:59 pm by tetontech

The previous posting, Functionally Dreaming with Swift, was an exploration of what is possible when coding for iOS and OS X. As part of the code example I ran across the need to uniquely identify any given user interface element in Interface Builder (IB). One commonly explored way to do this is to use the restoration ID of a UIView as a unique identifier. But this has nothing to do with restoration id’s regular use. Using it for uniqueness but not restoration behavior doesn’t pass ‘the smell test.’ It abuses an existing property and can cause restoration behavior when it is not wanted.

What, then, is a poor Swift programmer to do? Swift extensions can’t add stored properties.

There is a solution. IB has the ability to apply Key-Value coding to any User Interface (UI) element but only for existing properties. Somehow stored properties have to be mocked-up so we can take advantage of IB’s Key-Value coding application. This is actually easier than one would think.

Let’s start by dropping IB from the picture so we can keep things simple. Imagine for some reason you wanted to extend all UIViews (this would include UIButtons, UILabels, UIImageViews, etc.) to have a stored property called sillyName. If all went well then you would be able to set the sillyName attribute in the ViewController’s viewDidLoad method.

Image 1: Setting a property added by an extension.

Image 1: Setting a property added by an extension.

Image 1 shows how this would look. Since sillyName would be like any other property it would be set in Swift’s normal way. You would also get the value by putting

let aSillyName = self.view.sillyName

in your code. The way to make this possible it to mock up a custom property.

In Swift, private declarations of structs is allowed in many places. Extensions is one of those places. Let’s draw on that and Swift’s ability to create calculated extension properties. Image 2 shows how to mock up a sillyName stored property as part of an extension.

Image 2: The source code for mocking up a stored property.

Image 2: The source code for mocking up a stored property.

Lines 27 – 29 embed a private struct into an extension. It is important to understand that this is different than attempting to add a named value (let) or a variable (var) to UIView as a part of the extension. In this case there is no instance of SillyCustomProperties created.

Instead of using an instance, we will use it ‘statically.’ This allows us to write code like line 32. In that line of code, the static struct property is accessed and returned from the get method of the extension’s calculated sillyName property. The sillyName calculated property is defined on line 30 as a String Optional and the setter is defined on lines 34 – 36.

This is a lot of fun, but there is a significant problem with the code in Image 2. The struct and its static values are shared among all UIView instances. That means that there could only be one sillyName and it would be applied to ALL UIViews. Each time it was set it would be updated for all UIViews. This means that we don’t yet have the ability to use this approach to apply unique identifiers to UIViews. If we tried they would all share the same ID. That is NOT good. To solve this problem we need to apply a little Objective-C ‘magic’.

Since UIView’s are instances of Classes and custom key-value pairs CAN be added to any class instance, we can ‘calculate’ a Swift property by storing and retrieving a value using Objective-C Key-Value coding. This can look a little nasty since we will need to call C functions and pass pointers.

Image 3: Mocking stored properties with unique values.

Image 3: Mocking stored properties with unique values.

Image 3 contains the ‘magic.’ Let’s replace the bodies of the get and set methods. In the new get method body, the objc_getAssociatedObject function retrieves the value associated with a custom key using Objective-C Key-Value coding. The function has two parameters. The first is the class instance that has the custom key and value. In this example it will be a UIView since we passed self and UIView is what we have extended.

The second parameter is the key for which we want the value. Line 40 shows the NSString pointer to the memory location of sillyName being passed. The & is what forces the parameter to be a pointer. NSString is inferred by the compiler since objc_getAssociatedObject requires an void*, C’s version of Swift’s AnyObject type, as its second parameter. If you would like more information on how to interact with C functions there is an earlier post about that.

The objc_setAssociatedObject is similar to objc_getAssociedObject but has one additional parameter, an indicator stating  the memory for the NSString created as a result of calling the function should be retained rather than released. This reserves the memory used for the NSString until we decide to get rid of it  (I.E. replace the value associated with sillyName with some other string). Now we can assign unique values to any type of UIView in interface builder.

Image 4: Setting Key-Value pairs using Interface Builder.

Image 4: Setting Key-Value pairs using Interface Builder.

Image 3 shows a UIImageView and the Identity Inspector’s (the blue icon in the Utilities list) description of the view. The section titled, “User Defined Runtime Attributes” is IB’s location where you can assign values to the properties of the UIView. In this case the value ‘squiggles’ is assigned to the sillyName property. Since sillyName was mocked up as a stored property of all UIViews by our extension, this definition does not cause a compile-time failure like it would if we hadn’t mocked up sillyName.

With all these pieces in place, we can modify this approach so we can meet the need for unique identifiers for any view. The code for this is almost exactly the same as what you have already seen. As seen in Image 5, the only differences are the name of the Struct and the name of the struct’s String property. Ignore the Bool properties. They are for something else entirely.

Image 5: Mocking up SwiftlyFunctional's uniqueID

Image 5: Mocking up SwiftlyFunctional’s uniqueID

So there you are. This pattern can be used to add ‘stored’ properties to classes. I you want to see how the Unique ID was set for this code look in the Functionally Dreaming with Swift posting.

November 10, 2015

Functionally Dreaming with Swift

Posted in Uncategorized at 5:16 pm by tetontech

Making iOS or OS X apps using a functional programming approach means dealing with a lot of application pieces designed using an Object Oriented (OO) approach if you use the default templates and libraries. The user interface (UI) and the data transmission and storage behaviors for both OS’s are heavily object oriented. This dramatically restricts the space where functional programming designs and techniques can be applied.

Having experienced this restriction I decided to explore what iOS development would be like if the UI behaviors were functional rather than OO in their design. Swift, much more than Objective-C, enables this kind of exploration so I created a Swift example of what could be done. I call it SwiftlyFunctional and an example Xcode project is in my gitHub repository.

Swift uses pass-by-reference for instances of classes and pass by value for structs. To have a ‘truly’ functional approach the UI Elements of iOS and OS X would have to be changed to be structs. That isn’t going to happen and I have no desire to write struct wrappers for the many different types of UI elements in iOS and OS X. It wouldn’t be impossible, but is outside of the scope of what I wanted to explore. I’m chose to ignore this problem as part of my dreaming.

When laying out what I hoped to accomplish, I decided I still wanted to be able to use Interface Builder (IB) to design and layout the UI, but not be restricted to using the Object Oriented (OO) design enforced by the current Xcode templates. Because of this, I decided to dump working with the ApplicationDelegate and ViewController classes generated in a new iOS and OS X projects.  Instead of using the ViewController class to add IBAction Selectors to UI elements and gesture recognizers as is traditionally done, I  wanted to use Swift functions and closures to handle UI events.

With these goals in mind, I began my dreaming. What I show here is what I came up with but it is only one of many ways this could be done. I’ll show you how to use the SwiftlyFunctional code in this posting. In subsequent postings I’ll describe how some of the more interesting portions of the code work.

Image 1: The structure of a SwiftlyFunctional app

Image 1: The structure of a SwiftlyFunctional app

Let’s start with the structure of a functional iOS app. Image 1 shows that the ApplicationDelegate.swift and ViewController.swift files are gone. Instead you can see the SwiftlyFunc.swift and Main.swift files. You can call Main.swift anything you would like except for main.swift. The capitalization is important. If you try to use main.swift you will get a compilation error. This is likely due to the hidden files in all Swift apps that allow for Objective-C interactions. The file main.h is part of the default Objective-C projects.

Main.swift is where you will begin writing the code for your application. It contains the main(application:userView:launchReasons) function. This function acts somewhat similar to the C main function and is the where the app will start running your code.

the main function, as you can see in the example code, is where you can attach Swift functions or closures to application events such as ‘did become active’ and UI elements like buttons, images and labels.

In the example source code, and in Image 2, you can see an example of adding a closure for the ‘did become active’ application event.

Image 2: Attaching a closure to an Application level event.

The addApplicationEventHandler(application:theEventType) function is part of the SwiftlyFunctional API. It can be used to add a closure to any app event except application(didFinishLaunchingWithOptions:launchOptions). That one happens much earlier than will be captured and made available for closures. The addApplicationEventHandler function has three parameters, the application running (this is the first parameter of the main function), an enum for the type of application event to map to, and a closure with no parameters and a void return. In image two the closure only prints a string to the console, but you would be able to perform any computation normally associated with a ‘did become active’ event in iOS.

Image 3: The types of events that can be linked to closures.

Image 3: The types of events that can be linked to closures.

image 3 contains the complete list of Application events to which SwifltyFunctional can add closures or function. If other events are added by Apple they can be easily added to the enum.

Assigning closures to events for UIControl elements such as Buttons is nearly the same. One major difference is the closure must be associated with an event triggered by a specific UI element. In the case of the example, this is a UIButton. To make this possible, a reference to the button is needed. The SwiftlyFunctional API has a method, getViewByUniqueID(containingView:anID).

The first parameter passed to getViewByUniqueID in Image 4 is ‘userView.’ This UIView is the same as the second parameter of the main function and represents the topmost view of the view controller in the view hierarchy created in IB.

Image 4: Attaching closures to UIButton events.

The second parameter is the type of event, TouchDown and TouchUpInside for this code snippet. These event types are part of of the standard iOS library UIControlEvents struct. Like the addApplicationEventHandler function, the last parameter is the closure to activate when the event of touchEventType occurs.

Closures can also be attached to gestureRecognizers. In the SwiftlyFunctional example project users Interface Builder to add a TapGestureRecognizer to chalk.png’s UIImageView. The TapGestureRecognizer and the UIImageView both have a uinqueID added to them using KeyPaths. You can see how this is done by examining the right-hand side of Image 5.

Image 5: UITapGestureRecognizer for a UIImageView.

Set up this way, the SwiftlyFunctional’s getViewByUniqueID, getGestureRecognizerByUniqueID, and addTouchEventHandler functions can be used to find the recognizer and attach a closure to it (See Image 6).

Image 6: Attaching a closure to a UIGestureRecognizer event.

Unlike closures for UIControls such as UIButtons, no UIEvent object is passed to the closure by SwiftlyFunctional. UIGestureRecognizers contain the information obtainable from UIEvents. Notice that the location of the tap in the UIImageView is directly available without getting or using a Set of UITouches like you saw in the UIButton code snippet.

So there it is. Now closures can be attached to Application, UIControl, and UIGestureRecognizer events using a functional rather than an OO approach. Take a look at the example project, specifically the SwiftlyFunc.swift file, to see how this was done. I’ll follow up this posting with a couple of explanations of the SwiftlyFunctional code.

November 3, 2015

SwiftlyHybrid and AndyHybrid

Posted in Uncategorized at 8:28 pm by tetontech

In several of my previous posts over the last seven years I’ve described how to use web views with HTML5, CSS3, and JavaScript to develop installable apps for both iOS and Android. The earliest examples lead to the creation of QuickConnect (QC) and influenced the development of its first competitor, PhoneGap/Cordova. Those tools and others like them included extensive ‘bridging code’ to enable calls to Objective-C or Java and then back to JavaScript so the weaknesses of the older versions of the web views could be overcome.

As the iOS and Android web views’ capabilities have grown, the need to augment them with additional native iOS and Android code has decreased. Now audio and video can be recorded and played within the web views. Pictures can be taken and voices can be used to read text. Data can be easily stored and retrieved from local and remote stores. Nearly all of the functionality developers now need is encapsulated in the web views. Because of the continual growth of HTML5, CSS3, JavaScript, and web view support for them, heavy and complicated tools like QC and PhoneGap/Cordova are no longer needed. Instead much lighter and more standardized tools can be used. I’ve created SwiftlyHybrid and AndyHybrid to show what can be done. You’ll find each of them in their gitHub repositories. They are MIT licensed so feel free to do anything you like with them. SwiftlyHybrid has iOS and OS X example projects and AndyHybrid includes an Android Studio example project.

SwiftlyHybrid uses Apple’s WKWebView and the Swift programming language. AndyHybrid uses Google’s WebView that ships with Lollipop and Marshmallow. (Google claims this version of WebView will degrade gracefully when running on older Android OS versions.) Over time, the API’s for these two web views and their HTML5, CSS3, and JavaScript support have been converging. This means it is easier to write hybrid apps than ever before.

For both SwiftlyHybrid and AndyHybrid nearly all applications will only need to replace the HTML, CSS, and JavaScript files with custom ones and be done. For those few apps that still need to do something not possible in the web views’ sandbox I’ve created a standardized way to call from JavaScript to Swift or Android and get results back. HTML5 support and this bridge help SwiftlyHybrid and AndyHybrid use less RAM and CPU than the older QC and PhoneGap/Cordova tools, yet they are less complicated, and just as capable.

If you want to make calls down to Swift for iOS or Java for Android using one or both of these tools, the JavaScript code is the same. Here is a silly example that works for Both SwiftlyHybrid and AndyHybrid. In the example a message is put together and then past to the native code using the postMessage method.

var clicks = 0
function sendCount(){
    var message = {"cmd":"increment","count":clicks,
        var response = JSON.parse(responseAsJSON)
        clicks = response['count']
        document.querySelector("#messages_from_java").innerText = 
                                                  "Count is "+clicks

The message is a JavaScript associative array. it contains the command “increment” and some data, the current value of the “clicks” variable, and a callback function. Calling the postMessage function provided by both SwiftlyHybrid and AndyHybrid will convert the message associative array into JSON and send it to the native code portion of your app. In order for the callback function to be passed, it must be converted to a string otherwise the JSON library will strip it out. Since this message isn’t going across the internet or an internal network we don’t have to worry about XSS attacks so executing the string in the native code as JavaScript isn’t a security issue.

The Swift code for handling the message is in the SwiftlyMessageHandler.swift file in the SwiftlyHybrid example. It looks like this:

let command = sentData["cmd"] as! String
        var response = Dictionary<String,AnyObject>()
        if command == "increment"{
            guard var count = sentData["count"] as? Int else{
            response["count"] = count
        let callbackString = sentData["callbackFunc"] as? String
        sendResponse(response, callback: callbackString)

The current count is first pulled from the data sent from JavaScript. It is incremented and then SwiftlyHybrid’s sendResponse method is used to execute the callback JavaScript function using the response dictionary as a parameter to the JavaScript callback function.

The Java code for AndyHybrid is very similar. It is in the JavaScriptCommunication.java file.

HashMap<String, Object> message = (HashMap) JSONUtilities.parse(aMessageAsJSON);
String command = (String)message.get("cmd");
Serializable response = null;
       long count = (long)message.get("count");
       HashMap<String,Object> dataMap = new HashMap<>();
       response = dataMap;
String asyncCallback = (String) message.get("callbackFunc");
sendResponse(response, asyncCallback);

In both languages the command is retrieved from the associative array generated from the JSON message string, the count is also retrieved and incremented, a response is created containing the updated count, and the response is passed to the callback JavaScript function. The callback, in both cases, is executed within the web view and in the web view’s thread.

Having shown you the JavaScript, Swift, and Android Java to do communication between the two ‘layers’ of hybrid apps, I must say again, seldom is this type of inter-thread communication needed. Most of what you will want to do can be done directly in JavaScript, HTML, and CSS.

July 31, 2015

A Little Bit of Fun

Posted in Uncategorized at 9:24 pm by tetontech

I’ve recently put a free book up on Apple’s book store. It’s a little bit of fun I did in my ‘spare’ time. I call it “Doing Stuff With C.” Here is the URL. https://itunes.apple.com/us/book/doing-stuff-with-c/id1023155821?mt=11

I’ve tried to take a simplified, light-hearted approach to introducing C to someone who doesn’t know anything about it. I envision this as the first of a free book series, Doing Stuff With…., that covers the same material in each book but for different languages/platforms. I’m hoping to have the next book, Doing Stuff With Java, done next week.

I’d love to hear feedback on this little bit of fun and where to take the series next (I’m already planning Doing Stuff With Swift).

FYI, you will find other for-money books by me on Amazon and the other online stores. Don’t buy them. They are out of date. I did them through traditional publishers. That causes problems with keeping the information from going stale.

All of this writing AND working on Swiftly Secure??? Good thing I’m taking the next 5 weeks off from work!


Encryption development update

Posted in Uncategorized at 5:17 pm by tetontech

In order to continue with the development of my socialist millionaire protocol implementation that uses a 4096 bit key I need to find a generator for a Galois field of that size. This is no short term undertaking. Even using the access I have to a supercomputer it is going to take a while to find a generator.

The current level of mathematical understanding is that these generators must be brute-forced since there is no known pattern for what is and isn’t a Galois generator. So while my code is using the supercomputer to do a brute force search, I’m attacking the problem of finding a pattern. I’ve attempted to take a non-obvious approach and have already seen some interesting patterns. If what I’m seeing as patterns hold, I should be able to find a generator long before the brute force approach does. That would be nice since checking even one generator for 2^4096 values to see if the generator actually is a generator takes a long time, let alone multiple possible generators.

I’m eager to get the pattern found so I can share it with you and complete the SMP implementation.

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.


Next page


Get every new post delivered to your Inbox.

Join 329 other followers

%d bloggers like this: