Software piracy and Open Source (OSS)

Software piracy eats up a lot of revenue of the big guys. One might think that since piracy is bad for software companies selling proprietary software, it is good for open source. It is surprising to see many open source followers correlate lower business or loss of software giants (due to piracy) with growth or victory of open source. I believe this is not true.

Take example of Microsoft Windows. Paying for windows is a new concept for many people in the place I come from. Undoubtedly, Windows is the best operating system to go for if you are a serious gamer, as almost all games that come for PC are targeted at Windows. If you do not have Windows, you are left out. At this point, there are two choices - either legally buy a copy of Windows, or use a pirated copy. If you buy, you have already fueled the proprietary engine.

Assuming you chose to use pirated copy instead, you essentially got it for free (in a free beer sense, even though you do not have the sources and consent that you can freely modify and redistribute). This is where comparison starts between pirated proprietary software and the open source alternative. Many times the open source alternatives are under-manned and under-funded, which means they lack some (probably game changing) features that are present only in the proprietary software. This makes the open source versions look inferior. The general public does not think twice; they can get both for same price - free! Obviously they would go for the better proprietary version. They do not realize that they are weighing watermelons (well funded, manned and planned proprietary software) against grapes(OSS), and the OSS alternative loses popularity. As OSS versions' popularity reduces, more and more people turn to the proprietary software, either buying it or using pirated copies - a vicious circle. As more and more people use Windows, more and more softwares (utilities, office software, games, multimedia etc.) are made available for windows (many times exclusively), which in turn attracts even more people towards Windows. If not a single person used pirated Windows, the number of installations of Windows would be _significantly_ lesser than it is now, which would force application developers to write software that also runs on other operating systems, which in turn will lead to more adaptation of non-Windows operating systems by people. It is essentially a balance, which miraculously tilts in favor of proprietary software when it is pirated. This is why some companies deliberately let people use pirated copies of their softwares long enough to set the `vendor lock-in'.

I believe this is true for any proprietary software and it's OSS alternatives. To break this cycle, next time someone asks you for a pirated copy of a software, hand him an (or a list of) OSS alternative, ask him to support the development team by providing money, manuals, free advertisement space, compute power etc.

When two or more OSS softwares doing similar things compete against each other, the price and piracy factors are missing from the equation, but everything else still holds - the better the software at solving users' problems, the more followers/popularity/user-base it will get. A purely merit based system/balance! We want people to fairly compare proprietary software and corresponding OSS on equal grounds, which means asking users to compare the copy of Windows they _bought_ for a couple hundred dollars, with Linux which is available for free.

I still do not know if the open source model is the best for our industry, but if you strongly believe in open source, please persuade people not to pirate.

Duplicate or missing numbers in an array

This is one of the most frequently asked questions in CS job written tests and interviews. Though other solutions like counting sort, linked-list-loop detection, sum etc. exist, they have their own complexities and limitations.

here is one O(n) approach I came up with (during a test), which actually seems to work.

Throughout, I assume that the numbers are between [1..n], all positive and integers are large enough to hold all of these (but not necessarily their sum, which can be an issue with the sum based approach), and XOR works with regular semantics.

given an array of length n which contains elements from [1..n] without repetitions, let x = XOR(all elements of the array)
Then

x = n if n = 0 mod 4
x = 1 if n = 1 mod 4
x = n+1 if n = 2 mod 4
x = 0 if n = 3 mod 4

We know n and also the expected value of x if the missing number was there. Just XOR the result of XORing all elements of the given array with expected x from given n, which gives the missing number. The same argument holds for one repeated number too.

Here is a sample C program which finds one repeated number.

---

int n = 100000;

int a[n + 1];
int rep = n - 1;
int i = 0;
int idx = 0;
for(i = 1; i <= n; i++){
  a[idx++] = i;
  if(i == rep)
    a[idx++] = i;
}

int res = 0;
for(i = 0; i < n + 1; i++){
  res ^= a[i];
}
switch(n % 4){
  case 0 : res ^= n;     break;
  case 1 : res ^= 1;     break;
  case 2 : res ^= n + 1; break;
  case 3 : res ^= 0;     break;
}
printf("%d\n", res);

---

Going lambda/functional with m4

m4 is the GNU version of traditional macro processor. Even though it is a single pass macro processor, unlike cpp, it can also process the substitutions of a macro, we can define a macro to define another macro, and use the newly created macro, and so on. Thus, we can, in some sense, use m4 as a functional programming language.

Recursive version of factorial program is straightforward in m4:

define(`rec_fact', `ifelse($1,0,1,`eval'($1 * `rec_fact'(`eval'($1 - 1))))')
rec_fact(15)

We can also create non-recursive version in m4. Since lambda terms are essentially anonymous functions, we write m4 macros to create and destroy new pseudo-anonymous macro definitions. Following macro defines the Y combinator equivalent in m4.

dnl Thanks to Toby White (http://uszla.me.uk/space/essays/m4Y)

define(define(`Y_COMB', `dnl
pushdef(`recur',dnl
`pushdef(`y_anon',dnl
`$1''changequote([,])(['changequote([,])`changequote`]`$[]1'(``$[]1'')dnl
['changequote([,])'changequote`])changequote`dnl
(changequote([,])`$[]1'changequote)dnl
`popdef(`y_anon')')'dnl
`y_anon')dnl
pushdef(`y_anon',`dnl
recur(`recur')'changequote([,])(`$[]1')changequote`dnl
popdef(`recur')`'popdef(`y_anon')')`'dnl
'`y_anon')`'dnl

This essentially is a version of fixed point combinator given by Haskell Curry and is defined as Y = \lambda f.(\lambda x.f (x x)) (\lambda x.f (x x)). This is similar to recur(recur). \lambda x.f (x x) is implemented as $1(`$1') in y_anon.

The non-recursive version of factorial can be written as :

define(`ARG1', `changequote([,])`$[]1'changequote')dnl
define(`F_fact',`dnl
pushdef(`anon',dnl
`ifelse'(ARG1,1,1, dnl
``eval''(ARG1 * ``$1''(`eval'(ARG1 - 1))))dnl
`popdef(`anon')')'dnl
`anon')dnl

And now all we need to do to call this non-recursive factorial functions is:

Y_COMB(`F_fact')(5)

We can also define a sugar function named fact that expands to Y_COMB(`F_fact').

Not just tail recursion but we can also run any kind of general recursive program in non-recursive fashion:

define(`F_fib',`dnl
pushdef(`anon',dnl
`ifelse'(ARG1,1,1, ARG1,2,1, dnl
``eval''(``$1''(`eval'(ARG1 - 2)) + ``$1''(`eval'(ARG1 - 1))))dnl
`popdef(`anon')')'dnl
`anon')dnl
Y_COMB(`F_fib')(11)

Run the above with m4 -dV to get sequence of reductions, it helps a lot with debugging.

Note that data constructors are also actual functions in m4, and there is no built-in support for say tuples or lists. It is more lambda-ish than say Haskell-ish. We have to build all such structures ourselves. The evaluation scheme is not full-lazy.

Pidgin : Log in invisible for Google Talk (XMPP/Jabber)

I am a big fan of pidgin, primarily due to it's configurability and plugin support. One of major turn-off people report around me is that pidgin does not support logging in as invisible with gtalk account. Not that I am a big fan of invisibility, I built a plugin that lets you do just that.

Not supporting neat 'sign on as invisible' for gtalk is basically due to lack of time and willingness on Pidgin developers' part. Not that they can't, they just don't want to at the moment due to some extra stuff gtalk uses/needs.

Installation instructions:

It is written in Perl, which means you need perl 5+, pidgin-perl and libpurple-perl packages.


On apt based systems (like Ubuntu), do (as root)
apt-get install pidgin-perl

looks like Ubuntu 9.10 has this built in.

on fedora and alike

yum install pidgin-perl

That should install all required packages, with dependencies.

Download and extract the plugin perl script.
Save it to your ~/.purple/plugins/ directory. That is, /home/{username}/.purple/plugins/.
If you find that hard, there is an install script included.

Usage:
Go to Tools->Plugins. Find 'Google Talk Invisible Plugin' and enable it.
Now, when you set your status as "Extended Away", you become invisible. Simple!

This is the pre-pre-pre-...-alpha release, which means I did not go through the trouble of activating the INVISIBLE status for gtalk accounts, and hijacked xa instead. I hope it is not a big mistake.

Update : there is a serious bug in this plugin. After you become invisible, you can not get updates to your contact list, and hence if you start pidgin with the plugin enabled in extended away mode, you may not see any online friends at all. I am working on it.

Basic Authenticating pseudo-proxy with bash/netcat

Yes, you can also do authentication with netcat.

#!/bin/bash
# @author : Prashant Borole (prashantb  :can be reached at:     cse iitb ac in)

# A simple proxy-proxy that authenticates on users' behalf.
# Known limitations :
#       Works for Basic proxy authentication at the moment (though it is not that hard to add digest support)
#       Can process single request at a time. Any parallel requests will not be satisfied. This may lead to referred elements not being loaded, eg. images. Download accelerators are rendered useless.
#       Due to the logging format, there can be storage issues when downloading huge files.
#       Significantly slower than squid or some custom asyncio implementation as each request spawns bunch of new processes
#       No cache. Each request is strictly sent to upstream proxy
#       no https or ftp support

# TODO put this in some standard location
CONFIG_FILE="$HOME/.proxy.conf"

export LISTEN_PORT=
export PROXY=
export PROXY_PORT=
export LOG_FILE=

init()
{
        exec   2>&- 2>&1
        exec   5>&1
        exec   >>"$LOG_FILE"
}

readConfig()
{
        # really cheap config parsing.
        # FIXME improve
        # echo "Loading Configuration from $CONFIG_FILE"
        export LISTEN_PORT=$(grep "LISTEN_PORT=" "$CONFIG_FILE" | cut -d '=' -f2)
        export PROXY=$(grep "PROXY=" "$CONFIG_FILE" | cut -d '=' -f2)
        export PROXY_PORT=$(grep "PROXY_PORT=" "$CONFIG_FILE" | cut -d '=' -f2)
        export LOG_FILE=$(grep "LOG_FILE=" "$CONFIG_FILE" | cut -d '=' -f2)
}

if [ "$1" != "--" ]; then
        # read the config initially
        readConfig
        
        # accept credentials
        echo -n "$PROXY:$PROXY_PORT    user name : "
        read USER_NAME
        echo -n "$USER_NAME@$PROXY:$PROXY_PORT Password : "
        read -s PASSWORD
        echo
        export B64CRED=`echo -ne "$USER_NAME:$PASSWORD" | base64`
        unset USER_NAME PASSWORD
        echo "Credentials accepted."

        # launch in background
        $0 -- &
        exit 0
else
        trap 'echo "cleaning up $TMP_DIR" ; rm -fr "$TMP_DIR"; killall -9  nc tee >/dev/null 2>&1' EXIT
        trap 'echo "Shutting down proxy server on port $LISTEN_PORT" ; exit 0' SIGUSR1
        trap 'echo "Reloading config..." ; readConfig' SIGUSR2
        trap 'echo "[UNCLEAN] Shutting down proxy server on port $LISTEN_PORT" ; exit 1' SIGINT SIGKILL SIGSEGV SIGPIPE SIGHUP SIGTERM SIGABRT

        readConfig
        init
        echo "`date`   Server $0[$$] started"
fi

TMP_DIR=`mktemp -d /tmp/proxy.XXXXXXXX`

BACK_FIFO="$TMP_DIR"/back_fifo
# create a pipe
mknod "$BACK_FIFO" p

echo "Accepting connections on port $LISTEN_PORT"
while true ; do
        nc -l "$LISTEN_PORT" 0<$BACK_FIFO | tee request | (while read line ; do if [ "$line" = "^M" ] ; then echo "Proxy-Authorization: Basic $B64CRED" ; echo ; else echo "$line" ; fi;  done) | nc -w 5 "$PROXY" "$PROXY_PORT" | tee response 1>$BACK_FIFO
        head -n+1 request
        head -n+1 response
done

echo "THIS SHOULD NEVER HAPPEN. SOMETHING IS WRONG !!!"
exit 1

Note that you can NOT use something like sed or awk, because they simply give up when there is no text to read. This breaks the pipe. A "while read" loop just cuts it :)

Java Unicode (source code)

We all know that Java is great with Unicode. I was surprised to know that the compiler itself has moved on. The Java source itself can be in Unicode now!!

Check out the sample Java source file

 1 /**
 2  * @author prashant
 3  *
 4  */
 5 public class JavaUnicodeTest{
 6     static class मज्जाआहे  {
 7         public मज्जाआहे()     {
 8             System.out.println("constructor of " + this.getClass().getCanonicalName());
 9         }
10
11         int पाचद्या()       {
12             return 5;
13         }
14     }
15
16     public static void main(String[] args) {
17         मज्जाआहे o = new मज्जाआहे();
18         System.out.println(o.पाचद्या());
19     }
20 }

Using OpenJDK
java version "1.6.0_0"
OpenJDK Runtime Environment (IcedTea6 1.5) (fedora-27.b16.fc11-x86_64)
OpenJDK 64-Bit Server VM (build 14.0-b15, mixed mode)

It runs fine, giving

constructor of JavaUnicodeTest.मज्जाआहे
5

weird, eh?

random status in Pidgin :- fortune

There is a nice utility called 'fortune' for linux. Basically a database of funny/witty quotes accumulated over decades which can be read either directly from flat files or using the 'fortune' front-end.

What can you use it for? Display random quotes in your mail signature (with due references/credits), on your home page or IM status :P

#!/bin/bash while true :; do MSG=`fortune -ae` zenity --question --text="$MSG" && (purple-remote "setstatus?message=$MSG" && sleep 1800); done;

Make sure you have zenity and fortune packages installed.

Start pidgin and then this script. It will get a new random status every 1800 seconds and ask whether you want it as status, the process repeats immediately if you press cancel, and status is set otherwise.

'fortune' is used for name sake here. You can pull in random statuses from some web page (and probably scrape them), or some RSS feed if available, or from your own compiled database of statuses, reading one at random.

This is what you do when you are bored to core sitting in an office on Monday afternoon waiting for the benchmarks to complete.