Algorithm to calculate Inverse Factorial of Natural Numbers

Note:

1. All numbers are Natural numbers. Unless until specified
2. This works if the inverse factorial of the number is guaranteed to be a natural number. If you came here hoping to get gamma or pi function based solutions, Sorry turn back.

Calculating factorial is hard. But is there a way one can speedily calculate inverse factorial?. Suppose you were given a number that was promised to be factorial of a whole number will you able to tell the inverse factorial of that number. The post presents two observations on factorials and then formulates an algorithm to use these observations to perform the inverse of a factorial.

Observation 1 [Counting trailing zeroes]

Observation: All the factorials after 5! end in zeroes, i.e. The factorial has a lot of trailing zeroes at the end.

First step was to gather data. And to make matters simple I wrote a python script to plot the number of zeroes in factorial of the given number vs the number.

The graph is linear. Which is good!!. Now maybe we could find some relation to the number of zeroes in factorial of the number and the number itself. Just to make sure I also ran it from 0 to 20000. 

No surprises there. 

You can try the same using this python script.

How are the zeroes in the factorial related to the number itself?

This is simple a factorial is simply a product of all the natural numbers from 1 to that number. So a zero occurs every time we multiply a 10. Which means every time a 2x5 happens there is a zero. So there is a extra zero every 5 numbers. We don't have to worry about availability of '2's as they are in abundance (By the time you gain a factor of 5 we cross two even numbers).

[0] :: 0!   -> 1

[0] :: 1!   -> 1

[0] :: 2!   -> 2

[0] :: 3!   -> 6

[0] :: 4!   -> 24

[1] :: 5!   -> 120

[1] :: 6!   -> 720

[1] :: 7!   -> 5040

[1] :: 8!   -> 40320

[1] :: 9!   -> 362880

[2] :: 10! -> 3628800

[2] :: 11! -> 39916800

[2] :: 12! -> 479001600

[2] :: 13! -> 6227020800

[2] :: 14! -> 87178291200

[3] :: 15! -> 1307674368000

[3] :: 16! -> 20922789888000

[3] :: 17! -> 355687428096000

[3] :: 18! -> 6402373705728000

[3] :: 19! -> 121645100408832000

[4] :: 20! -> 2432902008176640000

It is clear that the pattern seems to follow. So the graphs look linear for big data. But are actually stepped. So generating the same graph for 0 to 100 we get

Now this is interesting. our hypothesis seems to hold, somewhat. But there seems to be no factorial with 5 zeroes at all, and there are these weird places where the zeroes seem to increase an extra digit. In fact 24! -> 620448401733239439360000 and  25! -> 15511210043330985984000000, from 4 zeroes to 6 zeroes. Lets zoom out a little.

As you can see the jumps seem to happen at factors of powers of 5. Or one zero jump at 25! 50! 75! and two zero jump at 125! 250! 375! etc. Lets plot the increase in number of zeroes.

For a larger data set

Try it out using this python script.

So this is cool. Lets try and explain. Our hypothesis that for every 2x5 there is a zero is correct. But that doesn't mean that for every 5 numbers there is a jump in number of zeroes of the factorial of the number. Lets see 24 has 4 '5's which are at 5, 10, 15, and 20, But 25 has 6 '5's at 5, 10, 15, 20 and two at 25 because 25 = 5x5. So given a number if we can calculate number of 5's that make the factorial of the number we can say the number of zeroes that the number makes. 

Formulating it given a number n

sum of (n/k) where {k = 5^m, m = 1,2,3.... | k < n}. ('/' signifies integer division)

For n = 26 we get (26/5) = 5 and (26/25) = 1. We cannot do (26/125) as 125 is > 26. So we can conclude that as 5+1 = 6. 26! has 6 zeroes. 

Doing the same for 80! we get (80/5) = 16, (80/25) = 3. Therefore 80! must have 19 trailing zeroes.

80!=71569457046263802294811533723186532165584657342365752577109445058227039255480148842668944867280814080000000000000000000

Which is correct. 

Lets summarize,

Given a number we can safely say how may zeroes that the factorial might have. Which is done by the formula above.

So given a factorial of a number, By counting the number of zeroes one must be able to say that the number is within these 5 numbers, as all of them have factorials with same number of zeroes. But how does one work this in reverse. 

Let try to figure out the number given that factorial of that number has 44 trailing numbers. 

Now we know that 44 was written as a + b + c .... , where a is number of factors of 5, b of 25 ...

So we can work reverse 44/5 = 8, 44/25 = 1. Therefore 44 - 8 = 36 must be the number of '5' factors and 8 - 1 = 7 must be the number of factors of '25' and 1 must be the number of factors of '125'

Therefore number must be somewhere between 36*5 = 180 and 37*5 = 185(not inclusive). So the factorials of numbers 180 to 184 have 44 trailing zeroes  

180!=200896062499134299656951336898466838917540340798867777940435335160044860953395980941180138112097309735631594101037399609671032132186331495273609598531966730972945653558819806475064353856858157445040809209560358463319644664891114256430017824141796753818192338642302693327818731986039603200000000000000000000000000000000000000000000

181!= 36362187312343308237908191978622497844074801684595067807218795663968119832564672550353604998289613062149318532287769329350456815925726000644523337334285978306103163294146384971986648048091326497552386466930424881860855684345291680413833226169665212441092813294256787492335190489473168179200000000000000000000000000000000000000000000

182!=6617918090846482099299290940109294607621613906596302340913820810842197809526770404164356109688709577311175972876374017941783140498482132117303247394840048051710775719534642064901569944752621422554534336981337328498675734550843085835317647162879068664278892019554735323605004669084116608614400000000000000000000000000000000000000000000

183!=1211079010624906224171770242040000913194755344907123328387229208384122199143398983962077168073033852647945203036376445283346314711222230177466494273255728793463071956674839497876987299889729720327479783667584731115257659422804284707863129430806869565563037239578516564219715854442393339376435200000000000000000000000000000000000000000000

184!=222838537954982745247605724535360168027834983462910692423250174342678484642385413049022198925438228887221917358693265932135721906864890352653834946279054097997205240028170467609365663179710268540256280194835590525207409333795988386246815815268464000063598852082447047816427717217400374445264076800000000000000000000000000000000000000000000

One has to be careful while evaluating these. Because, take for example you find 10 zeroes this corresponds to 9 + 1 not 10 - 10/5 = 8 and 10/5 = 2 therefore 8+2. The best way to evaluate this, that I could come up with is to take an array where 0 index corresponds to number of '5's and 1 corresponds to number of '25's and so on and populate it. Check the final code for my answer

Now we can point out the number from its factorial to the accuracy of 5. But how do we get to the exact number.

Observation 2 [Number of digits in the number]

The number of digits of a factorial of a number increases with the increase in the number. This was obvious, But first the data

It is steadily increasing. Though not linear. Trying the same on a larger data set.

So, Its settled. The length of the factorial has something to do with the number. However one has to take into account that for smaller numbers this wouldn't work. 

And this seems to happen only below 10 twice. Shouldn't be a big deal as for these numbers the regular way of calculating the factorial and verifying would suffice and would be sufficiently fast enough.

Now the standard way of determining the number of digits in the number is to do a logarithm base 10 of the number and add one to the lower round off. Or to say

floor(log10(n)) + 1 (floor does the round off to lower number)

For example number of digits in 342345234 can be calculated by this method as log10(342345234) = 8.53446428616 so 8 + 1 = 9

Now to the magic part 'Stirling's Approximation'. It is written as 

ln(n!) = nln(n) - n , where ln is logarithm base e

So given n!, floor( log10(n!) + 1) gives us the number of digits in the number. 

Adapting the approximation formula. 

Let d be the number of digits in the factorial of a number n

d = floor( log10(n!) ) + 1
d = floor( ln(n!) / ln(10) ) + 1
d = floor( ( nln(n) - n ) / ln(10) ) + 1 

Can we approximate n from d?. I am not gonna try. But some careful observation should tell you that it might not simplify things.

Algorithm for Inverse Factorial

Now we can get back to the main problem. 

We can make guesses for 5 numbers and calculate the number of digits to pinpoint the number. As long as you can calculate ln(n) and ln(10) accurately we can approximate the number. And hence the inverse factorial.

However, its worth noting that it is all an approximation. And might not hold all too well for long. You might want to read through the error in stirling's approximation. But this must be accurate for quite large numbers. As the number of digits increase too rapidly in factorial function evident from the graph.

So for the final act lets put all together and guess the factorial of the number.

I wrote a python script to do all the simulations. Get it here.

Here are the results.

This is the error in determining the inverse factorial of the number vs the number. The script used to generate this is here.

And this shows the number vs the inverse factorial of the factorial of the number. You can try it out using this script.

I've tried this method up to 20000!. And does seem to do really well. However any bigger would heat up my computer crazy. But if you can, try and let me know.

Cheers!!

Note:

1. This algorithm assumes that there exists an inverse factorial for the given number. However this might not be the case always.
2. This only works for numbers written in base 10. Which is very inefficient. However it can be made to work for other base numbers with a few modifications.

Building Racket for Android

I've been using Racket for academic purposes and decided to try it running on android. I was able to get it built for android. This post details the efforts made and is also meant to be sort of a log entry.

Download the source from github. Use this script to compile it on linux/mac.

It's simple to compile it for android. However the real trouble lies in getting it to run, because you need to have all the startup files and also the binary should know where to find them. So first time you run it on a android device it shows this error message

Welcome to Racket v6.7.0.3.
standard-module-name-resolver: collection not found
  for module path: (submod (lib "racket/init") configure-runtime)
  collection: "racket"
  in collection directories:
   /data/.racket/6.7.0.3/collects
   /home/regnarts/workspace/scheme/android/armv5/racket/collects
standard-module-name-resolver: collection not found
  for module path: racket/interactive
  collection: "racket"
  in collection directories:
   /data/.racket/6.7.0.3/collects
  /home/regnarts/workspace/scheme/android/armv5/racket/collects
standard-module-name-resolver: collection not found
  for module path: racket/base
  collection: "racket"
  in collection directories:
   /data/.racket/6.7.0.3/collects
   /home/regnarts/workspace/scheme/android/armv5/racket/collects

Which is expected. Now you can fix this in two ways one is by using '-S' to specify the path that the interpreter is expected to look at. Or as the README suggests, edit the binary to change the default collects directory path name!!. You might want to go through the README and this post to get it working .

Once that is done the interpreter should start-up and behave as it would do on any other platform. However the boot time is notoriously long. Got to figure out a way to reduce it. This is not a main project but something I did to kill time. So I am not going to look into it now. However it would be really nice to get something like DRRacket to work on Android. This can be made into a app with moderate effort. But that's the story for another day.

Finally I could get my interpreter to run on racket running on Android.

Cheers!!

Cross-Compiling for Embedded Linux based systems

After my recent work with porting multiple things for android. I thought that it would be nice to do a tutorial for cross compiling existing linux projects over to the embedded devices. I will soon get into the details. For cross-compiling linux based binaries/libraries basically you need 3 things

1. Toolchain
2. Headers
3. Libraries

Toolchain

Depending upon the selected target you can always find a toolchain. Toolchains are always architecture specific (Duh!?). For example if your device is ARM based you cannot compile for it with MIPS toolchain. The most common toolchain that you will find for a device is GCC. It is open source toolchain. You might also find different flavours like linaro. Or find a different toolchain itself like clang/LLVM. Whatever the choice you will need these for most of the projects.

1. C compiler 
2. Assembler
3. C++ compiler
4. Pre-Processor
5. Linker utilities
6. Archive utilities

However, Observe that we are talking of a c or c++ based project here. Java, Python, Perl projects inherently depend upon their Interpreter or Virtual Machine to run. And also they are designed to be portable. Hence once compiled they should be able to run on any system provided the availability of the fore said things.

Headers 

These are basically collection of .h/.hh files that contain definitions of the functions/structures ,etc., the way it would be found on the real device. These are mostly created when you compile the kernel, and many more are added by the supporting libraries. Pre-Processor uses these to verify that the function calls that you will be making to the Operating system actually exist and are defined. One might in theory edit these files and add his own stuff or definitions and the project would pass the pre-processing step and compile. However if the system is to be linked these definitions have to be found somewhere. If the OS expects its binaries to be pre-linked then the linking process would fail. If dynamic linking is taken into account then it would fail and throw up a fault at run time. For example you might link your project with a 3.xx kernel based header and newer version of libraries. But if you try to run the project on a older kernel or with older libraries. Then it would not run and throw up a fault.

Libraries

These are basically there so that the linker can verify and statically link the binaries. It is however expected that the same library files exist on the device for it to work. You might in theory simply copy the library to the device and expect it to work. But sometimes, or most of the times the dependencies may not be the same and it would fail.

Now for a practical example take a look at port of LibAV to android. LibAV is an open source implementation of codecs for media play back and encoding. I had to use it to a personal project. I have however uploaded the source to github. It would be interesting to look into the build scripts that I have used to build the libraries. There are basically 3 of them for different architectures, namely ARM, MIPS and X86. This project was configured with autoconf. So it has a configure script that can be easily run. And thanks to popularity of Android, LibAV actually officially claim to support android(previously, wasn't the case). Observe that I configure the build with multiple parameters. But mainly the cross-compiler toolchain

which is configured at cross-prefix. The headers and libraries are located in sysroot, under include and lib directories respectively. Rest of the configurations are mainly project specific. Running this script obviously requires to to edit for your system, the locations would not be same. But in the same project under android directory you will find that multiple ARCH directories are there with executables of the same library compiled. If you are trying to port something linux to android, then do take a look in to the build scripts. You will find a variety of pointers for the job.

Have Fun!

Cheers !!

The Androux project

Finally, I've completed the linux support for the ports. I have decided to call the project androux. A play on words android and linux. You can grab the source from github. Finally "make" works and the compile script works on linux x86_64. The build scripts still won't run if you are using 32 bit machine. Will try to bring support for that in future. The android shell is not fit to run the configure scripts and hence a port of few utilities like sed and bash shell is required. I am working on it.

As of now you can create a Makefile and compile your projects on the device. I have tried a basic test and make works fine.

Visit github for instructions on compiling.

After compiling, you need to copy system folder created to the system folder of your device. You also need to copy the include and lib folders from platform directory corresponding to android version that your device runs.

The final system image will be quite big and I am quite sure that the partitions that are created in your phone by default are not enough to hold it all. There are two ways of approaching this problem, either extend the system partition, if the inbuilt flash can hold it or create a new partition in the sdcard and change the mount scripts to mount that partition as system instead.

When writing install scripts in make file we need to take care that system partition is mounted r/w. By default the system partition is read only in android. Or you could choose another install location.

I still haven't had time or resources to test on an actual device. Please let me know if any of you can do so and share the results

Cheers ! :-)
Stay Awesome  

MAKE compile script added

Quick repo update. I've added the compile script for make

Have fun!! Cheers :-)

c++ and g++ compile scripts fixed to build on mac OS X

I have finally found time to fix the scripts to build c++ and g++. I have pushed the code to the github. You can grab a snapshot here - https://github.com/heliumfire/androux. Or you can alternatively do

git clone -depth=1 https://github.com/heliumfire/androux

I am also working on getting linux scripts to work so that building can be supported on ubuntu. Next plan is to fix make and bash so that everything can be run smoothly on the device.

Future plans is to grab a AOSP source and integrate into it. I was thinking of first trying it on GB. Still haven't done it yet.

As far as putting it up on a real device. I am trying to procure an android device, unfortunately its an old one running GB (xperia play). I need help to try it out on other devices. Let me know if anyone is willing to.

Source for linux utilities on Android

Hi all,

I have finally made time to push the source of my ports to github. Access the source at https://github.com/heliumfire/androux. To get the source clone the repo by
git clone https://github.com/heliumfire/androux. As of now the source only compiles binutils gmp mpc and mpfr. And will only work on linux. I will put up more stuff as the time comes

Cheers, Have fun :)

Make for Android and associated problems

NOTE: Your phone, your responsibility. (all stuff from previous posts)

I managed to compile make for android. But unfortunately it is not foolproof. Download it here and push the contents to the /system folder in the emulator. But there is one slight problem. There is a function that make uses called ttyname(). This function is supposed to be defined in libc. But as android doesn't run on standard libc but bionic. It has not been implemented and left as a stub. It basically returns the name of the terminal device like "/dev/pts/1". I think the best way to get around would be to implement it in bionic stubs code itself. But that would require replacing libc. And I don't like the sound of it. Another way would be to implement it in make. But I wasn't gonna spend this night doing that. So instead i hardcoded it to return "root".

And fortunately enough make seems to work fine without it. I wrote a small makefile and compiled to check. Sorry I did't include that in the package. But have fun trying it out by writing your own.

Let me know if you have any thoughts on implementation of ttyname.

PS: I have made progress on putting the scripts together for build system. Stay tuned 

System image [android-19] with gcc, g++, file and vim

I have uploaded the system image so that you can simply download it and try it out without having to remount or push. Copy the android-19 directory to "system-images" directory of your sdk and create a new avd for android-19 or use the old one doesn't matter. Just remember to close any avds that are open and restart them.

I have also included two source files for hello world, one for C and another for C++. They are there in "/system/bin" directory. Check the system by

Cheers, Have a nice day !!!

Edit: I've also included file and vim binaries, check em out

C C++ programming on Android [added g++ and vim to the package] (ARM specific)

NOTE: Same as old one. If you are dumb enough to spoil your device or emulator (lol), don't blame me. Try at your own risk

For long we have distanced using android as a development machine. This might not be far.

Yesterday, I successfully compiled gcc that could run on android. And today without much delay g++ is here. I've also added vim from my older post. Now you can push all the binaries to the phone and have a nice programming package on phone. I have done a basic sanity test on the binaries and they seem to be working fine. I've also included three sample programs in the bin directory. If possible remove them before pushing to the device. (for details on how to push them to the emulator see my last post)

This system will create binaries that will definitely run on all arm (32 bit) android devices. That means you can compile on your phone and then send it to another phone and it would work (lol, what am I writing. Sorry, sleepy :( ). This will create similar binaries to that of your ndk. So basically all the executables that you could compile with your ndk. Now you can on the phone.

Now to the backsides of it. It takes up large space (around 500 MB). Most of the system partitions are smaller than this so it would require that the partitions be resized and mounted. I could probably make a zip to install but due to this problem it wouldn't work on most devices. You need to edit the system partition size. And I have no idea how to do that, because I don't have an android phone. But if there is anyone willing to do this, please let me know how that turns out.

I've seen a friend of mine try use vim on his phone. And trust me it sucks. We will need a better editor and also a better terminal. For now I would suggest using terminal emulator to try it out. But it will not be as good as a personal computer. I wonder how it will be on a physical keyboard android device. I will search for my old HTC Dream, and hopefully it will work. I also have memory issues on that to be taken care of (half GB extra system storage on HTC Dream, you got to be kidding me). I will let you guys know how that turns out. Meanwhile have fun trying it out.

And ya I almost forgot download it here.

PS: I did try to make a nice build system out of this. But due to my laziness and non-linear working style it has become difficult to put together a script to do the whole build as I initially intended to. But I promise that in near future that I will try and put it up on github or something, after I get it to work. 

GCC on Android [ARM Specific]

NOTE: I am not responsible for whatever damage you might cause to your emulator or device. You wish to try it out, its by your own will.

Last week, I compiled binutils for android. This week I have another of linux utility for you - "GCC". I haven't fully tested any of these. I've only checked for their sanity. Also owing to the fact that I do not own an android device makes it more problematic. I've only tested it on emulator. I expect it work on devices. I will be more than thankful if anyone can confirm it. The package is very big [around 154 MB zip]. I will probably write how I achieved it some time in future. Unzip the file and copy the contents of the "sysroot" directory to "/system/" in your emulator.You might need to do

adb remount

before that in order to mount the /system/ partition as rw. If you are willing to try in a mobile device.  Open the device prompt by "adb shell" and then

# mount
rootfs / rootfs ro 0 0
tmpfs /dev tmpfs rw,nosuid,mode=755 0 0
devpts /dev/pts devpts rw,mode=600 0 0
proc /proc proc rw 0 0
sysfs /sys sysfs rw 0 0
none /acct cgroup rw,cpuacct 0 0
tmpfs /mnt/asec tmpfs rw,mode=755,gid=1000 0 0
tmpfs /mnt/obb tmpfs rw,mode=755,gid=1000 0 0
none /dev/cpuctl cgroup rw,cpu 0 0
/dev/block/mtdblock0 /system yaffs2 rw 0 0
/dev/block/mtdblock1 /data yaffs2 rw,nosuid,nodev 0 0
/dev/block/mtdblock2 /cache yaffs2 rw,nosuid,nodev 0 0

will display the various devices and the mount points. Now you can do remount on "/system" directory. In my case this will be

mount -o remount,rw /dev/block/mtdblock0 /system

Because my system files are contained in "/dev/block/mtdblock0". Now that you have remounted push all the contents of "sysroot" directory to "/system". (Please note that this won't work if you don't have enough space in the system partition. You will need to find a way to increase the space. If you are using an emulator start the emulator with "emulator" binary in sdk "/tools" directory by invoking "./emulator -partition-size 1024 @<avd-name>",  the size of partition can be adjusted to your will. Note that you will need to first create an "avd" for this. Use the GUI in eclipse to do so)

adb push  sysroot/ /system/

[NOTE: This command might not work in all systems. adb push doesn't handle directories. It only works on my macbook. On my ubuntu it doesn't work. If it doesn't work find a better way to handle this or you are stuck copying each of them manually. Or write a script to copy all the contents]

 Now you can use vim that I had previously compiled and posted months ago in conjunction with gcc to create c programs on your mobile and compile them over your device. I could have also included the vim program in the package. I forgot that unfortunately

Somewhere in the bin directory I've included two hello world programs by mistake. one is written in 'c' and the other in assembly. Compile them to test the working of the system.

Above is the output from my adb. And yes I forgot to include a newline character in the hello.c program, get over it.

I expect everything to go fine. There are two versions of toolchain in there, one that produces code for "arm-linux-androideabi" (default one). There is also a second one "arm-none-eabi" this can, in theory be used to produce os independent code like for an arm micro-controller.

I am working on another stupid idea now. I'll let you guys know of when that happens :)

Binutils on Android

This is a quick post. I managed to compile binutils to run on android. I have just run a sanity test on them. I am still not sure of its behaviour. But as of now, every thing seems to be running smooth. Once again, I haven't had much time to test it. The assembler seems to be working, I verified it by assembling hello world program on device then pulling it back and linking it with ndk. The compiled program, sure enough spit out "hello, world!". You can download the compiled package here.

I shall keep you posted on the future developments.

PS: Please don't question why the port

Porting VIM to android [ARM]

Last week I tried porting VIM to android. I felt that I could give you guys a complete walkthrough. That way you could get the idea of the process and try porting something else.

So I started and very soon realized that I would need to port ncurses also. So first I had to download ncurses. Took the latest version. Which was ncurses-5.9 at the time i did the port. Always try to compile things for your system first. So i did that. It's a straight forward procedure. Had to fun configure and then make.

That did the job. I was not interested in installing anyways. So i directly ran './configure --help' this lists out all the options available. 

.

The most important ones were displayed in the end. Those were the set of flags that we can pass on to the build system.

The configure script allowed me to configure both the compilers and their flags preprocessor and linker flags. This was great. So I set about trying to get it built. It is always a good thing to write a script to do your configure and make. so I wrote mine "build_for_android.sh". So basically I wrote whatever I could think of to make the build happen. The initial shell script looked like this.

NDK=/home/regnarts/android/android-ndk-r8e
CROSS_COMPILE=${NDK}/toolchains/arm-linux-androideabi-4.7/prebuilt/linux-x86_64/bin/arm-linux-androideabi-
PREFIX=`pwd`/../sysroot
COPTS=--sysroot=${NDK}/platforms/android-9/arch-arm
./configure \
        CC=${CROSS_COMPILE}gcc \
        CFLAGS=${COPTS} \
        CPPFLAGS=${COPTS} \
        CPP=${CROSS_COMPILE}cpp \
        CXX=${CROSS_COMPILE}c++ \
        --host=arm \
        --prefix=${PREFIX}
make

After this I ran make, only to encounter an error 

Upon investigation and a bit of googling I found out that android's LOCALE was broken. So I had to uncomment the flag HAVE_LOCALE_H. I tried to see if there was a possibility of doing it as a flag passed through configure but I finally settled over sed. I quickly figured out that the flag was being defined in "include/ncurses_cfg.h". So I just added
sed -i 's/#define HAVE_LOCALE_H 1/#define HAVE_LOCALE_H 0/' include/ncurses_cfg.h
to the build script. Now upon running the script and make I got this

Observe that this only contains a few undefined references. I ran a search for the required symbols in the lib directory of ndk.

I couldn't find it anywhere in the android lib directory. But googled it that I need to include the library libgnustl_static.a. I knew just including -lgnustl_static wouldn't work. Because the library wasn't there in sysroot we specified. So merely including '-lgnustl_static' wouldn't help. So we need to find the library. And it was there in <ndk-root>/sources/cxx-stl/gnu-libstdc++/4.7/libs/armeabi-v7a. So I included a '-Lflag' to fix it. And finally it worked.

Running make install it put all the output in the sysroot directory as I had pointed out in the script. The directory now held all the binaries required to build VIM.

So now I went forward and downloaded VIM source. Unpacked it the same way. Then went on to directly run './configure --help'. I was presented with a similar set of options. So I wrote a 'build_for_android.sh' for this one too.

But I got a series of errors as such these were resolved by setting the required variables. So I added
export vim_cv_terminfo='yes'
export vim_cv_bcopy_handles_overlap='no'
export vim_cv_memcpy_handles_overlap='no'
export vim_cv_stat_ignores_slash='no'
export vim_cv_memmove_handles_overlap='no'
export vim_cv_getcwd_broken='no'
export vim_cv_tty_group=world
export vim_cv_toupper_broken='set' 
to 'build_for_android.sh'.
This took a long time as everytime I set one another would pop up. After fixing this up I found another

But this was easy. Observe that we haven't provided path for the linker to search for ncurses library that we have built. Including that to the build the configure ran smoothly. Then I ran make

Now these are all c library symbols. Why aren't they being found?, but upon closer inspection I saw this

The script was running gcc as a linker. And It wasn't including any flags that we had passed on. So I consulted the configures help menu again. And learned that I had not set the LDFLAGS. So I straightaway corrected the script. And now ran make again.
Now I did my check and couldn't find these symbols anywhere. They weren't in any library that was included in the ndk[r8e]. After spending some quality time over it I was frustrated. It simply wasn't available in android. I had to implement it myself. So I googled out source for the function.

#include <stdlib.h>
#include <string.h>
#include <wchar.h>

int mblen(const char *s, size_t n)
{
        static mbstate_t mbs;
        size_t rval;

        if (s == NULL) {
                /* No support for state dependent encodings. */
                memset(&mbs, 0, sizeof(mbs));
                return (0);
        }
        rval = mbrtowc(NULL, s, n, &mbs);
        if (rval == (size_t)-1 || rval == (size_t)-2)
                return (-1);
        return ((int)rval);
}

And then added to the file from where the function was called

And now running make got it compiled completely. I did make install and

There it was. I wasted no time and pushed it to my device and tried running it over adb.

I wanted to check it up with terminal emulator. But unfortunately my touch screen is broken making it impossible to use my phone. I am not sure if it will completely support it. Let me know if you guys find out Download the source scripts and binaries from here.

I recently gave a talk about this at GDG BlrDroid. Here is the video

Android Kernel Compile | Galaxy Fit S5670 | ARM Basics

Very recently I was asked by one of my professors to compile a custom kernel to his phone. He gave me an old Samsung Galaxy Fit phone.  This post documents the process carried out to do the same.

The phone runs ARMv6-compatible processor rev 5 (v6l) and supports features like

swp [SWaP] & swpb [SWaPByte]

This instruction is deprecated as of ARMv7 even in some later versions of ARMv6

This instruction was used to implement exclusive access to semaphores themselves.

Semaphores are used to manage access to a shared resource. Depending on the type of semaphore, one or more clients may be granted access.

Before accessing a resource, a client must read the semaphore value and check that it indicates whether the client can proceed, or whether it must wait. When the client is about to proceed it must change the semaphore value to inform other clients.

A fundamental issue with semaphores is that they themselves are shared resources, which – as we just learned – must be protected by semaphores.

SWP (Swap) and SWPB (Swap Byte) provide a method for software synchronization that does not require disabling interrupts. This is achieved by performing a special type of memory access, reading a value into a processor register and writing a value to a memory location as an atomic operation. The example code below shows the implementation of simple mutex functions using the SWPinstruction. SWP and SWPB are not supported in the Thumb instruction set, so the example must be assembled for ARM.
binary mutex functions

    EXPORT lock_mutex_swp
lock_mutex_swp PROC
    LDR r2, =locked
    SWP r1, r2, [r0]       ; Swap R2 with location [R0], [R0] value placed in R1
    CMP r1, r2             ; Check if memory value was ‘locked’
    BEQ lock_mutex_swp     ; If so, retry immediately
    BX  lr                 ; If not, lock successful, return
    ENDP

    EXPORT unlock_mutex_swp
unlock_mutex_swp
    LDR r1, =unlocked
    STR r1, [r0]           ; Write value ‘unlocked’ to location [R0]
    BX  lr
    ENDP

In the SWP instruction in above example, R1 is the destination register that receives the value from the memory location, and R2 is the source register that is written to the memory location. You can use the same register for destination and source. For example 

        SWP r2, r2, [r0]       ; Swap R2 with location [R0], [R0] value placed in R2

is a valid instruction.

But there are certain limitations to this. If an interrupt triggers while a swap operation is taking place, the processor must complete both the load and the store part of the instruction before taking the interrupt, increasing interrupt latency. Because Load-Exclusive and Store-Exclusive are separate instructions, this effect is reduced when using the new synchronization primitives. In our source for Galaxy Fit we will find that swp or swpb aren't used to create atomic operations but Load-Exclusive and Store-Exclusive. Here is an example 

static inline void atomic_add(int i, atomic_t *v)

{

unsigned long tmp;

int result;

__asm__ __volatile__("@ atomic_add\n"

"1: ldrex %0, [%3]\n"

" add %0, %0, %4\n"

" strex %1, %0, [%3]\n"

" teq %1, #0\n"

" bne 1b"

: "=&r" (result), "=&r" (tmp), "+Qo" (v->counter)

: "r" (&v->counter), "Ir" (i)

: "cc");

}

This is taken from atomic.h of /arch/arm/include/asm/ directory.

In a multi-core system, preventing access to main memory for all processors for the duration of a swap instruction can reduce overall system performance. This is especially true in a multi-core system where processors operate at different frequencies but share the same main memory.

half [Half - Precision Floating Point Support]

In the ARM's VFP [Vector Floating Point Co-Processor] the support for 'half' means that it supports 16 bit floating point numbers and conversions between 16-32 bit floating point numbers. Half-precision floating-point numbers are provided as an optional extension to the VFPv3 architecture.

Half-precision floating-point format

Where:

   S (bit[15]):      Sign bit
   E (bits[14:10]):  Biased exponent
   T (bits[9:0]):    Mantissa.

The meanings of these fields depend on the format that is selected.

thumb [The Thumb Instruction set]

The Thumb instruction set is a subset of the most commonly used 32-bit ARM instructions. Thumb instructions are each 16 bits long, and have a corresponding 32-bit ARM instruction that has the same effect on the processor model. Thumb instructions operate with the standard ARM register configuration, allowing excellent interoperability between ARM and Thumb states.

On execution, 16-bit Thumb instructions are transparently decompressed to full 32-bit ARM instructions in real time, without performance loss.

Thumb has all the advantages of a 32-bit core:

• 32-bit address space
• 32-bit registers
• 32-bit shifter, and Arithmetic Logic Unit (ALU)
• 32-bit memory transfer.

Thumb therefore offers a long branch range, powerful arithmetic operations, and a large address space.

Thumb code is typically 65% of the size of ARM code, and provides 160% of the performance of ARM code when running from a 16-bit memory system.

The availability of both 16-bit Thumb and 32-bit ARM instruction sets gives designers the flexibility to emphasize performance or code size on a subroutine level, according to the requirements of their applications. For example, critical loops for applications such as fast interrupts and DSP algorithms can be coded using the full ARM instruction set then linked with Thumb code

fastmult [Fast Multiplication]

This refers to the fact that the processor can do 32 bit multiplication. The processor implementing this provides hardware to preform 32bit x 32 bit = 64 bit operation. This is a common feature in almost all the processors nowadays. But still they guys who built the kernel felt the need to mention it.

vfp [Vector Floating Point Co-Processor]

The VFP coprocessor supports floating point arithmetic operations and is a functional block within.

The VFP has its own bank of 32 registers for single-precision operands that you can:

• use in pairs for double-precision operands
• operate loads and stores of VFP registers in parallel with arithmetic operations.

The VFP supports a wide range of single and double precision operations, including ABS, NEG, COPY, MUL, MAC, DIV, and SQRT. The VFP effectively executes most of these in a single cycle. Sometime in future I promise to do a tutorial on this and NEON instructions.

edsp [DSP extensions]

The ARM DSP instruction set extensions increase the DSP processing capability of ARM solutions in high-performance applications, while offering the low power consumption required by portable, battery-powered devices. DSP extensions are optimized for a broad range of software applications including servo motor control, Voice over IP (VOIP) and video & audio codecs, where the extensions increase the DSP performance to enable efficient processing of the required tasks.

Features

• Single-cycle 16x16 and 32x16 MAC implementations
• 2-3 x DSP performance improvement over ARM7™ processor-based CPU products
• Zero overhead saturation extension support
• New instructions to load and store pairs of registers, with enhanced addressing modes
• New CLZ instruction improves normalization in arithmetic operations and improves divide performance
• Full support in the ARMv5TE, ARMv6 and ARMv7 architectures

Applications

• Audio encode/decode (MP3: AAC, WMA)
• Servo motor control (HDD/DVD)
• MPEG4 decode
• Voice and handwriting recognition
• Embedded control
• Bit exact algorithms (GSM-AMR)

java [Jazelle]

Jazelle DBX (Direct Bytecode eXecution) allows some ARM processors to execute Java bytecode in hardware as a third execution state alongside the existing ARM and Thumb modes. Jazelle functionality was specified in the ARMv5TEJ architecture and the first processor with Jazelle technology was the ARM926EJ-S. Jazelle is denoted by a 'J' appended to the CPU name, except for post-v5 cores where it is required (albeit only in trivial form) for architecture conformance.

These are the extra features that the processor supports over the regular ones. The kernel can only be complied over linux or Mac. For this one I will be using linux. First we need to install a few requirements and then download the source.

You will find the following files in the kernel source. Next install the required programs to compile the source. Run the following line in your terminal.

sudo apt-get install git-core gnupg flex bison gperf libsdl-dev libesd0-dev libwxgtk2.6-dev build-essential zip curl libncurses5-dev zlib1g-dev valgrind

Extract the kernel source. And also download the toolchain. Now extract the toolchain. and place it in a folder. You'll find the following in the toolchain folder.

Go to the kernel source and edit the Makefile to add the CROSS_COMPILE to point to the toolchain. It must look like this

Make sure the path is right. For me the toolchain was in /home/regnarts/S3/arm-2011.03 check the full path before updating.

Now to make this kernel there is a small problem. The original kernel source that was released by the samsung didn't have any support for Ext filesystem. That was because the original rom for this phone runs on samsung's proprietary RFS file system. So if you want to only run the stock rom over the kernel then just jump this part. Else you will need to enable the support for this in the config file. Find /arch/arm/configs/beni_rev01_defconfig and change the File System settings as shown below.

There is another important thing. The phone uses proprietary wifi/wireless drivers. So their source code is not provided. Therefore we need to just use the already existing ones. But the problem is that insmod checks for the kernel version before loading the modules. So if there is a mismatch. The kernel won't load the modules. Therefore you'll need to name the kernel as the module wishes to see it. Run

make menuconfig

This opens up the menu to configure the kernel.

In general setup append the name "-pref-CL928291" to the Local version. Now you are good to go. Run the make script that came with the kernel make_kernel_GT-S5670.sh. Or run

make beni_rev01_defconfig
make

That should give us the kernel. You will find it as /arch/arm/boot/zImage. Congratulations you've built the kernel for your phone. However you will need to still put it up in to the phone. For this we shall make the android's very popular "recovery flashable" zip file.

Download a sample file. Extract the zip, you'll find this

Now the file boot.img is the kernel+ramdisk file. But in order to build a boot.img you'll first need a ramdisk. We shall take the ramdisk from the sample previously downloaded. Use boot-tools to unpack and use the boot.img. The following must help
To unpack the boot.img

tools/unpackbootimg -i source_img/boot.img -o unpack

To unpack ramdisk (If you want to)

gzip -dc ../unpack/boot.img-ramdisk.gz | cpio -i

Replace boot.img-zImage with your own zImage and then run

tools/mkbootimg --kernel unpack/boot.img-zImage --ramdisk unpack/boot.img-ramdisk-new.gz -o target_img/boot.img --base `cat unpack/boot.img-base`

With the new boot.img replace it in the update.zip and zip it again.
This will flash in most of the recoveries if you turn of the signature verification. If you are unable to do it in your recovery. Then you'll need to sign it. Use this to sign it from linux.

export CLASSPATH=$CLASSPATH:./lib.jar
java testsign update.zip update-finished.zip

Now flash the zip file from recovery.

I'll discuss overclocking this phone in the next blog post.

Serial Communicaion Level Converters | RPi / BeagleBoard to Arduino / ATMegaX | UART

Working on my college project I came across the problem of interfacing a custom designed control board based on ATMega8 microcontroller to RPi that would run the main program. UART seemed to be the best option. The problem is that RPi runs its UART at 3.3V level and BeagleBoard runs its at 1.8V level and ATMegaX runs its UART at 5V level. Therefore there was a need for converter. Here are the schematics and design of the one that I built.

It is simply two transistor based inverters shifting the logic up and resistor network putting the logic down. The resistor logic is to step down the voltage for RPi. If you intend to use this for BeagleBoard then please change the resistances to appropriate values. You can download the PCB file and pdf.

Note:
We need to replace the lines  
dwc_otg.lpm_enable=0 console=ttyAMA0,115200 kgdboc=ttyAMA0,115200 console=tty1 root=/dev/mmcblk0p2 rootfstype=ext4 elevator=deadline rootwait
with
dwc_otg.lpm_enable=0 console=tty1 root=/dev/mmcblk0p2 rootfstype=ext4 elevator=deadline rootwait
in /boot/cmdline.txt
and comment out the line
#Spawn a getty on Raspberry Pi serial line 
T0:23:respawn:/sbin/getty -L ttyAMA0 115200 vt100
to get
#Spawn a getty on Raspberry Pi serial line 
#T0:23:respawn:/sbin/getty -L ttyAMA0 115200 vt100
in /etc/inittab
In Raspberry Pi if you wish to use the port for other uses than the terminal access.
In BeagleBoard you will need to setup the pins to work as serial. Please refer to the relevant documentation
Use software like minicom to access the ports.