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) 
                                ->(UInt64,UInt64){
    var carryAmount:UInt64 = 0
    let sum:UInt64 = 0
    //check for overflow
    if ~leftAddend < rightAddend{
        carryAmount = 1
        sum = rightAddend - ~leftAddend - 1
    }
    else{
       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]) 
                                              ->[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], 
                                                    partialProduct[1])
            //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 6, 2011

QuickConnect and the Mac app store

Posted in misc tagged , , , , , , at 7:50 pm by tetontech

The mac app store is up.  Do you want to put an app up?  QC has supported hybrid mac development for two years.  It is ready for you now.  All you have to do is make your selection as you see in the picture below and start making your app.

I’m currently adding more functionality to QC Mac.  The update should be out next week but you can get stared now.  Develop your app in HTML, CSS, and JavaScript just like your hybrid iOS, Android, Blackberry apps.

Selecting QC for the Mac

March 13, 2010

Developing for Blackberry on the Mac

Posted in Blackberry development tagged , , , , , at 5:03 am by tetontech

After attempting to develop for Blackberry on the Mac in several ways I have finally come across a way that works.  Here is how you can get this to work.

  1. Download and install VirtualBox version 3.1.4 or greater.  The earlier versions do not work with the blackberry simulator.
  2. Install WinXP in VirtualBox.  This worked for me.  I have not tried Win7 yet but will in the near future.
  3. From within your Win installation download and install the blackberry JDE 5.0 not earlier versions.  Make sure you get the JDE not the eclipse plugin.

At this point you can use the JDE to develop, compile, and run in the blackberry simulator from within your Win installation.

There is another option.  I am compiling and creating the .cod Blackberry application file inside of Xcode.  I will soon be releasing a version of QuickConnect that has a Blackberry template based on what I am doing now.  At that point we should be able to create one application and run it on the iPhone, Android, Blackberry, and Palm WebOS.  In fact there will be one QuickConnect template that will build for all of these platforms in addition to templates for each individual platform.

After I compile the application and generate the .cod file in Xcode I then place the .cod file in a VirtualBox shared directory.   I can then launch the simulator directly by running the .bat file for the 9559 simulator called 9550.bat.  It is found in the Simulator directory of the JDE 5.0 installation directory.

With the simulator running I select file->Load Java Program and pick the .cod file from the shared directory.  Using the Blackberry simulator I then run the application.

September 24, 2009

Native JSON Parser in Safari

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

I just got through running a test and found the Safari has built-in Native JSON parsing and stringifying.  Unfortunately Mobile Safari does not yet have this feature.  I am hoping to be able to remove the json2.js file from QCMac but am unsure yet as to how the native parsing compares to json2.js parsing.

Hopefully the comparison is good and it will soon be found in Mobile Safari so it will also be included in the UIWebView.

August 29, 2009

QuickConnectiPhone 1.5.0 is now available

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

QCiPhone 1.5.0 has just been uploaded to sourceForge.  They are saying that it may take about 15 minutes to become visible as the default download for OS X machines.

A note to 3.0 API users. The dashcode QC template no longer appears as an option.  I am looking for ways to get it to show up again.End

Because of the 3.0 Dashcode changes I have not been able to update the Dashcode examples to the latest QC source.  All of the Xcode examples are updated.

The release includes examples of how to use the video and audio tags in booth QCiPhone and QCMac applications.

QuickConnectMac 1.0 is also included in this release.  It allows you to create hybrid applications that run on Mac machines just like you do for the iPhone and iPod touch.

QuickConnectPHP 1.0 is another template that can be used on the Mac side.  It isn’t used to create hybrid applications but is used to create PHP web applications.

Also included, for those interested, is QCErlang 1.0.  It is an updated version of an Xcode template for developing erlang applications.  It includes auto-completes for most of the commonly used functions.

Defect fixes in this release include:

1.  UIWebView no longer ends up with a black background after re-displaying the Default.png file while the page loads.

2.  DataAccessObject in-browser database use fixed and updated to new methodology for the retention of which BCF in the stack is to be called next.

3.  Updated the embedded map code to use the current data passing scheme from and to Objective-C

4.  HTML Elements with touch events inside of Elements made scrollable no longer react to ontouchstart, ontouchmove, and ontouchend unless the event is not due to scrolling

August 28, 2009

HTML 5 Video and Audio in UIWebView and WebView

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

I have been playing with the video and audio tags in the UIWebView on the iPhone and WebView on the Mac.  I tried them in the QT WebView as well on linux.  I am pleased to announce that they work great!  I have tried it with mp3, mp4, and wmv.  All worked on all three platforms.

It looks like this is a good way to display videos for your users to play in your hybrid applications.

Let’s say you have a video called someCrazyMovie.mp4 that you want to display to your users.  On the iPhone or the Mac put it in the Resources group of your Xcode project that uses a UIWebView.  Point the UIWebView to a local html file, also in the resources file.

In this html file put the following code.

<video src=”someCrazyMovie.mp4>A movie description as an alt</video>

When you run your application you will see the first frame of the video used as a representational image.  You can play it by clicking it.  On the iPhone and iPod touch the movie player launches to play the movie.

The tag lets you size it, display or not display the video controls, etc.

The audio tag is used much the same way.

I’ll include an example for both the iPhone and the Mac in the 1.5.0 release of QuickConnectiPhone 1.5.0

July 2, 2009

Cocoa WebView and the Adobe Flash plugin

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

Since hybrid applications using the UIWebView are not recognized by the Adobe Flash plugin installer it appears that you cannot embed flash in a page displayed in a UIWebView and expect it to play swf files.

It is also true that the plugin has a defect. If you launch the default browser, be it Safari or Firefox, from within your application to display play a swf file the plugin crashes both browsers. If the browser is already open and running then the browser will open a window and you can play the swf.

I am including this ability in a future release of QuickConnectMac and QuickConnectWin but my opinion is don’t waste your time. Produce the movies as mp4s and you’ll have a much better user experience.

January 16, 2009

QuickConnect Porting and Development schedule

Posted in Android Development, iPhone development, misc tagged , , , , , , , , , , , , at 6:20 pm by tetontech

I recently got a request for information regarding the planned development and porting of QuickConnect and thought it should be shared here as well.

I am particularly excited about the ad hoc networking.  It will be great when an iPhone, an Android phone, a Linux based phone, macs, linux machines and even PC’s can discover each other and not need to care what the other device/machine is.  Then an application can be anywhere and interoperate with versions of itself or other services on any of the platforms.  And the applications can be written in JavaScript on all of the platforms.  Wow.

The current porting situation is as follows:

  • iPhone: release 1.1.1 available 1.1.2 next few days 1.5 beta in next few days as well
  • Android: beta 1.0 available today if all goes well
  • Mac: 1.0 beta 1 is currently shipping
  • LinuxQT: beta 1.0 in a week or so
  • MobileQT: about two weeks after LinuxQT beta
  • Microsoft porting will happen after the MobileQT port is nearing completion.

The iPhone 1.1.2 release will include access from JavaScript to:

  • device information – OS, device type, UID
  • The iPhone 1.5 beta 1 release will include access from JavaScript to:
  • ad hoc networking and service discovery (Bonjour Networking)

The iPhone 1.5 beta 2 release will include access from JavaScript to:

  • Raw socket networking (access via the synch cable)

The Android 1.0 beta 1 will include access from JavaScript to:

  • Browser and Native SQLite databases via the wrapper
  • AJAX wrapper
  • Vibrate
  • Play Sounds
  • Record and Play Audio
  • GPS data
  • accelerometer data

Android 1.0 beta 2 release will include access from JavaScript to:

  • Embedded Google Maps

Android 1.5 beta 1 will include access from JavaScript to:

  • ad hoc networking and service discovery

The LinuxQT 1.0 beta 1 will include access from JavaScript to:

  • Browser and Native SQLite databases via the wrapper
  • AJAX wrapper
  • Drag and Drop utility if web view supports CSS transitions(experimenting with this now)

The LinuxQT 1.0 beta 2 will include access from JavaScript to:

  • Embedded Google Maps

The LinuxQT 1.5 beta 1 will include access from JavaScript to:

  • ad hoc networking

The MobileQT 1.0 beta 1 will include access from JavaScript to(when the device supports it):

  • Vibration
  • accelerometerdata
  • GPS data
  • Browser and Native SQLite databases via the wrapper
  • AJAX
  • Play sounds
  • Play/record audio

The MobileQT 1.0 beta 2 will include access from JavaScript to:

  • Embedded Google Maps

The MobileQT 1.5 beta 1 will include access from JavaScript to:

  • ad hoc networking

December 5, 2008

SQLite Access and Use

Posted in Uncategorized tagged , , , , , , , , , , , at 5:41 pm by tetontech

I have now written access code for the SQLite database in a few languages and on various platforms. There is a dramatic difference in the ease of use from a programmers perspective.

The easiest to use, strangely enough, are the Objective-C classes from Apple and the C++ classes from QT(Nokia).
The next easiest to use would be the Java classes in the Android phone and the most difficult to use would have to be the JavaScript functions that are part of the upcoming standard.

I say the JavaScript is the hardest since all of the calls are designed to be asynchronous and programmers are not used to interacting with a database in that fashion.

You would think that with the programmer friendly API of Google’s Android that SQLite access would be easy. In fact, I assumed that it would be somewhat similar to JDBC. It is not. I find it particularly nasty since none of the classes are familiar and you have to work out the class relationships all over again. That would be fine if there was one nice main class as in the Apple and QT implementations but there are not.

So, all in all I would have to say that Apple and QT tie for first place. Google Android is a very distant second, and the JavaScript W3 standard implementation is in third place.

November 29, 2008

QuickConnectiPhone 1.0 RC3 available

Posted in iPhone development, mac development, misc, PHP tagged , , , , , , , , , , , , , , , , , , , , at 7:38 am by tetontech

The latest release candidate, 3, is now available for QuickConnectiPhone a framework that allows you to build your installable iPhone applications in HTML, CSS, and JavaScript. If you want to create an iPhone application but don’t have time to or maybe don’t want to learn Objective-C you can use QuickConnect instead.

This release, like RC 2, includes an installer.

It also includes support for embedding Google maps in your installable JavaScript application. This new functionallity, in addition to the previously added capabilities of GPS location, acceleration, JavaScript debugging in Xcode, device vibration and sound, etc., adds new power to your applications easily. All you need to do is make one JavaScript method call that includes the locations where you want a pin dropped and a description. The framework does the rest and your custom map is displayed.

Database access is just as easy. A wrapper for the SQLite database used natively on the iPhone is included in the framework. It supplies you with two methods, getData and setData, that are easily used to access and modify your data.

AJAX is also supported by a wrapper with getData and setData methods.

In addition, this installer will install QuickConnectMac. You can now quickly port your JavaScript application from your iPhone to a Mac. Most of this porting will consist of changing your HTML and CSS to fit the larger screen.

Also, QuickConnectPHP is included. This is an implementation of the QuickConnect framework in PHP. It allows you to create web applications quickly and easily using the same engineered approach that you use for your iPhone and Mac applications. It includes a MySQL wrapper that supplies both of the getData and setData methods as well.

Next page

%d bloggers like this: