Swapping two variables without using a temp variable

That is something I learned yesterday and I found it very cool. Thus it is something I must share.

I remember the swap algorithm was taught  in the very first days of college. It is very basic algorithm, but it is used in the foundations of several other algorithms. Until now,  it seemed  to me pretty obvious that its implementation would be inevitably (in C++03):

template<typename T>
void swap(T& x, T& y){
        T temp = x;
        x = y;
        y = temp;
}

In other words, it would always require at least 3 registers for the exchange.

If you are working in a pretty limited environment, a micro-controller for instance, you may not have 3 registers available for use. Therefore you cannot do the swap.

Well, that was I thought until yesterday. Then, I found I should review some material from my old "reduction of logical circuits" class  instead of playing Doom3 (It's kind of old game now, but it is only 10 bucks at iTunes!).

If your data is suitable for bitwise operations then you can do the follow (in C):

void swap(int* x, int* y){
    *x ^= *y;
    *y ^= *x;
    *x ^= *y;
}   

Why does it work ?

Explanation can be found at Wikipedia, but I intend to be more didactic here. Firstly, we need to remember some properties of the exclusive-or (xor) operation:

• P1 - Commutativity  x^y = y^x
• P2 - Associativity      (x^y)^z = x^(y^z)
• P3 - x^x = 0
• P4 - x^0 = x

So let's step through the algorithm. We are going to use two registers: A which initially will hold the value for x, and B which will hold for y. Thus, we have before the call to swap:

A x
B y

Then we execute *x ^= *y  or, to be clearer *x = *x ^ *y :

A x^y
B y

Okay, we still cannot apply any of the properties above. So let's move to the next line *y = *y ^ *x . But remember that x in the code does not refer to the value  that variable x hold before swap was called. It in fact points to our register A. So that line really means  B <-- B xor A. So the registers are now modified to :

A x^y
B y^(x^y)

Now we have something interesting. Let's apply the properties to the register B:

y^(x^y) --P1--> y^(y^x) --P2--> (y^y)^x --P3--> 0^x --P1--> x^0 --P4--> x

Wow! So at this point we have :

A x^y
B x

We are closer to our goal. Now we execute the last line  *x = *x ^ *y which in fact mean to us, using our register definitions, A <-- A xor B :

A (x^y)^x
B  x

Applying similar reasoning to register A:

(x^y)^x = (y^x)^x = y^(x^x) = y^0 = y

That means that now we have:

A y
B x

Voilá! We achieved what we wanted! Registers A and B were swapped  only  with the  help of exclusive-or operations. No extra temporary register was needed.

Using Native Code (JNI) on Android Apps

Android is written in Java and period. You must be able to do everything you need in Java.  But some applications like games using OpenGL will need some extra performance, and therefore they will go native.  As someone who had C++ as the lingua franca  at college, I took special interest on how the Java Native Interface (JNI) works on Android. Thus, I made a small Android app that requests the native layer to sum two integers. In its turn, the native layer displays the result on a TextView.

What do you need:

• Android Software Development Kit
• Android Native Development Kit

Preparing the field

First we create a simple activity that has a method with the native qualifier. That tells the JVM  that that method is not implemented in Java but by the native layer on C or C++. With Eclipse and ADT 20 that is pretty easy.

package com.example.testjni;

import android.os.Bundle;
import android.app.Activity;
import android.view.Menu;
import android.widget.TextView;

public class MainActivity extends Activity {

    static {
        System.loadLibrary("teste");
    }
    
    @Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        sum(3,5);
        
    }

    public void setTextView(String text) {
        TextView tv = (TextView)findViewById(R.id.text);
        tv.setText(text);
    }

    @Override
    public boolean onCreateOptionsMenu(Menu menu) {
        getMenuInflater().inflate(R.menu.activity_main, menu);
        return true;
    }
    
    public native int sum(int a, int b);
}

The code above creates a simple activity with a TextView. Line 11 instructs the Dalvik VM to load the shared library teste.so. You will see later that this the name of the library that will be generated to hold the native implementation of the method sum(int,int).  This is done inside a static block so it is executed when the class MainActivity is loaded and therefore before any instance of it is created; so Dalvik can execute the native method when requested.

My intention is that the activity after creating the views will call the native method to calculate the sum of 3 and 5, and then set the TextView with the result.

Generating the Header file

I created a jni folder in the project's directory  to hold all the native code. Now we need to implement the native method. When the native method is called, the JVM will look for C function with a  particular signature. The easiest way to know which signature you should use for your implementation is to use the javah tool from the JDK.

#javah -classpath ./bin/classes:~/Downloads/android-sdk-macosx/platforms/android-16/android.jar -d ./jni com.example.testjni.MainActivity

I ran the command above in the project's folder as above. javah needs the definition of all classes in your program. Thus I set the classpath  to the folder where the class files for my project are put (bin/classes) and I also added the path to the android.jar.  In my case I am using the API level 16, so I picked the right android.jar for it.  the -d parameter tells to output the header file to folder jni.  You need to pass the full qualified name ( i.e., including package name) of the class with the native method.  That command generated the follow header:

/* DO NOT EDIT THIS FILE - it is machine generated */
#include <jni.h>
/* Header for class com_example_testjni_MainActivity */

#ifndef _Included_com_example_testjni_MainActivity
#define _Included_com_example_testjni_MainActivity
#ifdef __cplusplus
extern "C" {
#endif

/*
 * Class:     com_example_testjni_MainActivity
 * Method:    sum
 * Signature: (II)I
 */
JNIEXPORT jint JNICALL Java_com_example_testjni_MainActivity_sum
  (JNIEnv *, jobject, jint, jint);

#ifdef __cplusplus
}
#endif
#endif

Note that even if the code gets compile on C++, the C-linkage is forced for the function, so the JVM can find the method without had to deal with the C++ mangling . C++ supports overloading function and mangles function signatures (embeds  parameters type, class and namespace scopes in the name) in order to support it.

Implementing the native method

I will show the implementation in C and C++.  The reason behind that is  that although the two languages are very similar ( you can compile C code with a C++ compiler),  the JNI  for C++ offer some inline methods to make it more object oriented.

The C code

#include <stdio.h>
#include stdlib.h>
#include <jni.h>
#include <android/log.h>
#include "com_example_testjni_MainActivity.h"


#define LOG_TAG "TesteNativeC"
#define LOGI(...) ((void)__android_log_print(ANDROID_LOG_INFO, LOG_TAG, __VA_ARGS__))

static char* buildString(jint a, jint b, jint sum){
    const char* fmt_string = "The sum of %d and %d is %d";
    const int buffer_size = snprintf(NULL,0,fmt_string,a,b,sum);
    LOGI("Buffer size is %d",buffer_size);
    char* buffer = (char*) malloc((buffer_size+1) * sizeof(char));
    if( buffer != NULL){
        snprintf(buffer,(buffer_size+1),fmt_string,a,b,sum);
    }
        return buffer;
}


JNIEXPORT jint JNICALL Java_com_example_testjni_MainActivity_sum
  (JNIEnv * env, jobject obj, jint a, jint b){
    jint result =  a+b;
    jclass cls = (*env)->GetObjectClass(env, obj);
    jmethodID mid = (*env)->GetMethodID(env, cls, "setTextView", "(Ljava/lang/String;)V");
    if(mid == 0) return 0;
    char* text = buildString(a,b,result);
    if(text != NULL){
        LOGI("At this point string is <<%s>>",text);
        jstring textToDisplay = (*env)->NewStringUTF(env,text);
        (*env)->CallVoidMethod(env, obj, mid, textToDisplay); 
        free(text);
    }
    
    return result;
  }

Function buildString is declared static because it is not intended to be exported, used outside of the library. Its objective is to build the string "The sum of 3 and 5 is 8".  For that, we call function snprintf from the standard C library. Note that I am using snprintf , the "safe-version" of sprintf. The reason for that is to prevent buffer overrun,  a common technique used by attackers to inject malicious .  In our case we don't need to do that because input does not come from external source. However, best practices should always be enforced. snprintf is used twice: first with a NULL parameter  to calculate the size of the necessary buffer to hold the string, and a second time to build the string.

The implementation of the native method follow conventional JNI idioms and it is very similar to using reflection in Java. So I just calculated the sum, retrieved the reference to the setTextView(String) method of the activity, build the string and called the method.  And, this is very important, I  released the allocated char array. NewStringUTF does a copy of the passed char array, so you need to free the buffer to not get a memory leak.


The C++ code

#include <jni.h>
#include <sstream>
#include <string>
#include <android/log.h>
#include "com_example_testjni_MainActivity.h"

#define LOGI(...) ((void)__android_log_print(ANDROID_LOG_INFO, LOG_TAG, __VA_ARGS__))

using std::stringstream;
using std::string;

const char* LOG_TAG = "TesteNativeCpp";

static string buildString(jint a, jint b, jint sum){
    stringstream buffer;
    buffer<<"The sum of "<<a<<" and "<<b<<" is "<<sum;
    return buffer.str();
}

JNIEXPORT jint JNICALL Java_com_example_testjni_MainActivity_sum
  (JNIEnv * env, jobject obj, jint a, jint b){
    jint result =  a+b;
    jclass cls = env->GetObjectClass(obj);
    
    jmethodID mid = env->GetMethodID(cls, "setTextView", "(Ljava/lang/String;)V");
    if(mid == 0) return 0;
    
    string text = buildString(a,b,result);
    LOGI("At this point string is <<%s>>",text.c_str());
    jstring textToDisplay = env->NewStringUTF(text.c_str());
    env->CallVoidMethod(obj, mid,textToDisplay); 

    return result;
  }
  

The C++ code is not much different. I could have used the same code  as of the C version for the function buildString, but I decided to do a code that is closer to latest C++ standards ( Not C++11 yet :-) ). Besides this uses STL containers. Using STL requires extra build config to compile. So I have the chance to show you how to setup the build for that case.

Note that for C++, env works more like an object : if in C we have (*env)->function(env,parameters), in C++ we have env->method(parameters).

Building

Now we need a Makefile for the job. I created the file Android.mk under the jni folder

LOCAL_PATH := $(call my-dir)

include $(CLEAR_VARS)

LOCAL_MODULE    := teste
LOCAL_SRC_FILES := teste.cpp
LOCAL_LDLIBS    := -llog

include $(BUILD_SHARED_LIBRARY)

This makefile is based on the one use for the "hello word" sample of the NDK. LOCAL_MODULE will tell to generate the shared object teste.so. LOCAL_SRC_FILES lists the files to be compiled. cpp extension is required for C++ files. LOCAL_LDLIDS tells to link against the library that allows our native code to output log to logcat.
Remember I said we need extra config to use STL containers. This means to create an Application.mk file besides the Android.mk in the jni folder

APP_STL := stlport_static

This single line sets the  STL library to be linked static.

Now we can build . You just  need to invoke <ndk_folder>/ndk-build on you project folder. This will generate the shared library that will be packaged on you APK. After you have built the library, you just need to build your APK as you would normally do (Eclipse or ant).

And that is the final result :

Why Computer Science is not an Exact Science?

I had a simple task today. Write a comparator for integers. My attempt was:

int compare(int a, int b){
    return a - b;
}

As you know this function must return a negative number if a<b, a positive number if a>b, and zero if both numbers are equal. As in any Exact Science, to show that something is correct you must conduct a proof.

There are three claims to prove:

• If a < b, the algorithm returns a negative number.

In fact if a<b, then b=a+c, where c is a positive number. Thus a<a+c and  a-b = a-(a+c) = -c, a negative number

• if a>b, the algorithm returns a positive number.  

Using the same reasoning, a>b => a=b+c => a-b = b+c-b = c, a positive number

• if a=b, the algorithm returns zero.

Trivially : a=b => a-b = a-a = 0.

But yet, the algorithm is incorrect.
"How come? Didn't you just prove it correct with mathematical rigor?"
Yes, I did. Your professor from the Algorithm Analysis course would like this proof. But as I said, it is completely wrong.  Guess why? Just an small tip : 2³¹-1

Yes! Integer overflow! My biggest mistake here was to assume a,b ∈ ℤ. Actually, they are restricted to (considering VM Java and 32bits for C/C++)  the interval [-2³¹,2³¹-1] . And the math is pretty weird for outsiders: the  sum of two very small negative integers may resulting in a positive number, and the sum of two very big positive numbers may yield a negative number.

"So let us account for the overflows. Let's put a check on your code. If ..."
Hey! Wait! Before complicating the code I want to show you how the Java Library implements the comparison:

 public static int compare(int x, int y) {
     return (x < y) ? -1 : ((x == y) ? 0 : 1);
 }

Imagine my duh! face when I read that.

Two lessons I learned here:

• Theory is good, but practice is always better.  In theory integers are infinite. In practice they are limited by the word size, and they came in signed and unsigned flavors.  That also applies to more complicated data structures. Your perfect hash function may not be perfect when you consider  the hardware  and software constraints.
• Do not pre-optimize code,  focus first in making it the most readable as possible.  By trying to making the comparison with a single operation I made it not readable by others at first sight. And worst: instead of saving "microseconds", I introduced a bug.