Simple Rolling Hash- Part 1

To process strings quickly I decided to try some hashing techniques to quickly append strings and make sub-strings (or slices) in time O(1) - constant time.


I also wanted to be able to search a string for some usually smaller string or word in linear time. This technique is called a rolling hash.

http://en.wikipedia.org/wiki/Rolling_hash

Background

A 'hash' is a number that is generated from some data in such a way that the distribution of the numbers looks random and there is a low probability that the same number is re-used.

For example, a hash of a string could be to multiply the length of the string by the sum of all the characters (this probably isn't a good hash method, but it explains the concept).

eg.

hash(abc) = 3 * 97+98+99 = 588

My Requirement - O(1) String Comparison

To speed-up string comparisons I was looking to use a 28-bit hash.

My aim was to have string comparison performed in roughly constant-time. To do this, I couldn't simply scan both strings looking for a mis-match as this would take O(N) time where N is the length of the two strings (unequal length strings can never match).

Instead I had to use some form of a hash of each string and only scan the strings if the hashes were equal. 

I looked at the DJB and SDBM hash functions for their simplicity. SDBM seems the better one by all accounts, but both would do for my simple purpose.

My Strings

My strings are not simply an array of characters. 

I divide each string into non-mutable fixed-length strings - currently 64 x 8-bit characters or 16/21 Unicode characters.

(My aim is to pick a fixed-length size that is 'just right' most of the time. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39.6999&rep=rep1&type=pdf )

This design, I was hoping, would reduce the cost of appending strings by allowing the new string to be formed as a linked list of the two source strings.

So, 

"abc" + "defg" -> ( "abc" , "defg" ) 

As a side benefit, this also allowed for a more straight-forward memory management and garbage collection scheme - if all memory allocations are the same size, then they can be easily and cheaply recycled, and memory is much less likely to become fragmented.

Although this would be fast - constant-time O(1) - I would have to re-calculate the hash for the new string which would result in linear-time O(N) behaviour and therefore negate any real performance gains: appending strings would still be O(N).

What I needed was a hash that could be generated from the individual hashes of the two source strings. 

With a little modulo arithmetic I was able to determine that if the hash functions were of the form:

hash(n) = k * hash(n-1) + char(n), and h(0)=0

then the resulting string would have a hash of

hash( s1+s2 ) = k ** length( s2 ) * hash( s1 ) + hash( s2 )

So now, I could append two strings and calculate the hash of the new string in constant-time.

Continued in Part 2.

Apple's new iPhone license agreement

ars technica covers it well


http://arstechnica.com/apple/news/2010/04/apple-takes-aim-at-adobe-or-android.ars?utm_source=rss&utm_medium=rss&utm_campaign=rss


Apple's new API license includes the following:

The new version of 3.3.1 reads:

3.3.1 — Applications may only use Documented APIs in the manner prescribed by Apple and must not use or call any private APIs. Applications must be originally written in Objective-C, C, C++, or JavaScript as executed by the iPhone OS WebKit engine, and only code written in C, C++, and Objective-C may compile and directly link against the Documented APIs (e.g., Applications that link to Documented APIs through an intermediary translation or compatibility layer or tool are prohibited).

This seems to mean that developers can not use tools that translate programs from one platform to the iPhone, or frameworks that try to make all smart-phones look-alike.

This is clearly a closed, dictatorial stance.

There are already many iPhone apps and games that are openly built this way - what do they do?

xmlvm, howto, xokoban, legions

But how can they test that a code-generator/cross compiler was used?

Perhaps this will spawn a new breed of code-generators that actually translate code from one language to another with same variable names, comments, parameters, etc.

Now that would be cool.

Solar Panel Update

Yesterday was the first anniversary of our photo-voltaic solar panel installation.

Generated

We have generated 1951 kWh of electrical energy.

This works out to be 5.34 kWh per day on average. A lot less than the 7.5 kWh per day that we were told to expect. At 7.5 kWh we should have generated 2737 kWh over the year.

They base this on Solar Irradiation Maps such as these. Sydney, for example, should receive 5.5 equivalent peak sun hours (PSH). Our 9 panels have an effective area of about 10 square metres. At 15% efficiency, we should generate 1.5 kW during full sun. At 5.5 PSH we should be getting 8.25 kWh per day on average. This roughly agrees with the companies estimate of 7.5 kWh per day. Perhaps something is wrong.

This variation is disappointing. It works out to be 71% of what should be possible. Now we have had a very wet summer so that would limit our generation capacity.

Our average daily consumption is about 6.23 kWh for the last year - 2274 kWh. The wet summer didn't help here either: we had to use an old clothes dryer on several days.

The system is therefore supplying about 85% of our needs. On the up side, we are now being paid 60c for each kWh generated and it costs us about 20c for each kWh consumed.

Electricity earns us $2.00 per day - excluding service charges.

Gas

To heat our water we use natural gas. We consume about 27 MJ per day on average. This is equivalent to 7.5 kWh per day, so our total energy consumption is about 14 kWh per day.

Gas costs us 50c per day - excluding service charges. This is about 7c per kWh.

Heating

We have a reasonably efficient wood fire for winter heating. I can only guess that we would use 10 to 20 kg of wood for about 100 days each year.  At 15MJ/kg we consume about 40-80 kWh each day for these 100 days or about 11 to 23 kWh per day on average.

Ignoring the capital cost and fuel for the occasional chain-saw use, the wood costs us nothing.

LPG

Our car runs on LPG. We consume about 8L per day. At 27.8 MJ/L this is a massive 62 kWh per day - just to run a car.

This is nearly double what we use in our house.

LPG costs us about $5.60 per day or 9c per kWh.

Total

In total, we generate about 5 kWh per day and consume 75 kWh per day (I have excluded the wood since we only plan to use wood that would otherwise have been chipped at the tip).

We have a long way to go before we are sustainable. The car is by far the biggest problem.

In terms of cost per kWh, electricity is double the cost of LPG and triple the cost of natural gas.

Directory to XML BASH Script

Ever wanted to get a directory into an XML structure?

Here is a quick, short and easily modifiable BASH script that works well.

To see how it works, you could run it like this:

scriptname dir | xmllint --format - | less

for dir, you can use . .. ./ ../ or / as well as subdirectories and full directory paths.

You might also be interested in this project: xml-dir-listing

How it works

The script first makes special directory specifiers easily useable. It then calls doDir with the directory.

doDir uses ls to get all files in the current directory. If the file is actually a directory and not a sym-link, it calls itself to process the subdirectory. Otherwise it outputs the file name.

Certain special directories (. and ..) are ignored to avoid infinite loops.

The program can use a lot of stack space so I increase it - I just guessed a value. It also can take a long time, so I renice the process so you can do other things.

To stop it, you may need to enter a lot (10-20) of ctrl-c's. I'm not sure why.

Sample Output

<dir>

<dirname><![CDATA[/usr/share/doc/distcc/example]]></dirname>

<file><![CDATA[init]]></file>

<file><![CDATA[init-suse]]></file>

<file><![CDATA[logrotate]]></file>

<file><![CDATA[xinetd]]></file>

</dir>

<file><![CDATA[protocol-1.txt]]></file>

<file><![CDATA[protocol-2.txt]]></file>

<file><![CDATA[reporting-bugs.txt]]></file>

<file><![CDATA[status-1.txt]]></file>

<file><![CDATA[survey.txt]]></file>

</dir>

<dir>

<dirname><![CDATA[/usr/share/doc/groff]]></dirname>

</dir>

<dir>

<dirname><![CDATA[/usr/share/emacs]]></dirname>

<dir>

<dirname><![CDATA[/usr/share/emacs/22.1]]></dirname>

<dir>

<dirname><![CDATA[/usr/share/emacs/22.1/etc]]></dirname>

</dir>

<dir>

<dirname><![CDATA[/usr/share/emacs/site-lisp]]></dirname>

</dir>

<dir>

<dirname><![CDATA[/usr/share/enscript]]></dirname>

<file><![CDATA[88591.enc]]></file>

<file><![CDATA[885910.enc]]></file>

<file><![CDATA[88592.enc]]></file>

</dir>

The Script

#!/bin/bash


# WARNING: To break this, you need to enter a lot of ctrl-c's


# heavy recursion so allow a bigger stack
ulimit -s 32768


# run with low priority so you can do other stuff while it works
renice -n +19 -p $$


function doDir {
  # directory name may contain illegal XML characters so we won't use attributes 

  #echo "<dir name=\"${1}\">"
  echo "<dir>"
  echo "<dirname><![CDATA[${1}]]></dirname>"
  # get all files and directories
  ls -Ab1 "$1/" | while read file; do
  # recursively process directories but not sym-links
  if [ -d "${1}/${file}" ] && [ ! -h "${1}/${file}" ]; then
    # don't do . and .. either
    if [ "$file" != "." ] && [ "$file" != ".." ]; then
      doDir "${1}/${file}"
    fi
  else
    # output the file
    echo "<file><![CDATA[$file]]></file>"
  fi
  done
  echo "</dir>"
}


# normalise initial directories so they all work
DIR=$1
if [ "."   == "$DIR" ]; then DIR="$(pwd)" ; fi
if [ ".."  == "$DIR" ]; then DIR=".."     ; fi
if [ "../" == "$DIR" ]; then DIR=".."     ; fi
if [ "./"  == "$DIR" ]; then DIR="$(pwd)" ; fi
if [ "/"   == "$DIR" ]; then DIR=""       ; fi


doDir $DIR

UPDATE: HP C7280 Ink System Failure

UPDATE: We had another paper jam recently and it caused what seemed to be this same fault. Moving gear back to it's correct position solved problem.

I had this problem today.

Ink System Failure... 0xc05d0381 (I did get another code after resetting the printer as well.)

It may have started two days ago when our first piece of paper jambed.

Note to self: when removing jammed paper, reassemble the pieces to see if you got it all out.

It worked fine today, but tonight it started making horrid gear-grinding noises. Then I got the 'Ink System Failure' message.

I tried a number of suggested remedies (see the 'fixyourownprinter' forum) but all they succeeded in doing was to factory default my printer - now I had to re-enter that very long wireless router SSID code again.

But it is such a pleasure with the HP Setup UI (did any HP tester actually use it? The input field doesn't even show all the characters so the last 3 are entered blind!)

After several power cycling events, I decided to investigate. I noticed how the ink pumps on the print head seemed to work - a black arm attached to a white gear is allowed to rotate about 1/2 a turn. The black arm is connected to a metal shaft which rocks a spring-steel sheet that depress some rubber boots. Like you might have on a lawn mower.

The printer head can move all the way to the left. When it does, the gears engage with some other gears to drive this pump.

In the picture you can see 2 white gears in the middle of the picture. The left one can rotate around the larger one and can rest in two possible positions.

The position shown in the photo seems to be the correct position. The incorrect position is to the right of the larger gear. My little white gear was in the incorrect position so I moved it.

Now my printer complained that I had a jam. And indeed, I still had a small piece of paper stuck in the area where the head parks itself.

I removed it with chop-sticks and all was well. The printer cycled ink through the cartridges and was happy again.

Buying new Tyres? What do Tyre Markings Mean?

Buying new tyres?

1. If you live in Australia, spend $10 or go to a library and get the Choice test for tyres that your car uses (or something close).
2. Look at the recommended tyres and decide what features you want more than others. 

In my case, I want best wet weather cornering and braking, followed by dry weather cornering and braking - then price.


I need 205/65R15, 215/60R15, or 225/60R15 tyres. I have 7" wide rims (15x7J) so I can use 8" to 9" tyres (205 - 225 and maybe 235).


You can change widths and profiles if your rims are the right width and you consider speedo errors.


For example  a 205/65R15 has the same circumference as these:

• 215/60R15 (1.3% error),
• 225/60R15 (0.5% error), and 
• 235/55R15 (1.2% error). 

Here is my Math.


Circumference = pi * ( rim_size * 25.4 + 2 * ( profile / 100 ) * width )


A worked example might help.

For 225/60R15, C = pi * (15*25.4 + 2*60/100*225) = 2045mm
What to look for.

• Tread Wear 300+ (3 time 'standard' tyre life) 
• Traction (braking in the wet) AA or A 
• Temperature A 

Other Markings

The tyre manufacture date is also on tyres. It seems to be stamped in rather than the other text which is raised. Look for something like 2309 - meaning 23rd week in 2009.


Here are photos of the Treadwear, Traction, Temperature, tyre size and date from one of my old tyres.

Treadwear 300
Traction A
Temperature A


Tread width 225mm
Profile 60% (of 225mm)
Tyre Radial (R)
Rim 15"
96V load and speed rating


Manufactured in the 49th week of 2007

Car Tubeless Tyre Repair

I have just 'repaired' my first car tyre.

We ran over a No. 2. No, not that sort, a real No. 2... The sort that is fixed with 1" nails to fence posts... Only it wasn't fixed to the post anymore.

Both nails punctured the tyre.

A neighbour once showed me how to repair a Bob-Cat tyre so I thought I would have a go. It only had to last a week until I put a new set of tyres on the car anyway.

I bought a tubeless tyre repair kit ($15) and one repaired hole is good and the other is a wait-and-see repair.

C Pre-Processor Niceness

I haven't programmed in C for years. 

I have forgotten a little, but I am finding that I am remembering more as I write and test my code.



CPP


The C Pre-Processor is so nice.



This has to be one of the nicest asserts that I have ever used:

ASSERT( 1==0 ); 

which outputs something like this:

ASSERT: "1==0" failed in pc-clisp.c line 672. 

All built with CPP macros:

This turns abc into "abc" - nice. You can use #x in your macro, but the wiki page used QUOTE so I have taken their advice.

#define QUOTE(x) #x

_TEST does the hard work. If the test is false it prints the failed message to stderr with the test, file and line number.

#define _TEST( type , test , action ) {\

  if( !(test) ){ \

    fprintf( stderr ,\

      QUOTE(type) ": %s failed in %s line %d.\n" , "\"" QUOTE(test) "\"" ,\

      __FILE__ ,\

      __LINE__ );\

    action;\

    }\

  }

ASSERT uses the generic _TEST to run the test and if it fails, to exit the program.

#define ASSERT( test ) _TEST( ASSERT , test , exit(1) )

You might like to define TEST and CHECK as well.

TEST just runs the test and prints any failed message.
CHECK, instead, returns false on a failure.

#define CHECK( test ) _TEST( CHECK , test , return (1==0) )

#define TEST( test ) _TEST( TEST , test , )

 For more information, see the wiki entry.

The iPad and the new GoogleOS

I like it.

Apple's insistence on using storage to differentiate pricing is an OK idea, but the price difference between models is hard to support.

Anyway, in my last post I dreamt of my ideal device. Now that the iPad has been seen by most, you could visualise my ideal device as an iPad that folds in half.

It, of course, needs a camera, needs to work as a phone and needs to run ChromeOS, but otherwise it is close.

Folded in half it would be about 7.5"x4.8" (190mm x 120mm), 1" (25mm) thick.

The Future

I think the PC has matured and is in decline. 

Netbooks have harmed the laptop market. Their low cost and high portability has meant that laptops and desktop have had to cut margins to sell. Microsoft too, has probably had to reduce margins to ensure their OS - old as it is - is the de-facto standard. I recently saw that Aldi advertised a 17" Core II Duo laptop with everything you could need for $900 AU. Even though it is many times better in almost every respect, the market wants laptops to be sub $1000 AU.

Where a big laptop fails is it's size. Consumers have their adequate 15" laptop or their 22" desktop and it still does the job just fine - even with Windows XP. They now want to be free to roam around their homes or around town with a take-anywhere Netbook.

They have their big-screen touch phones too. Great as a phone and as a media player but they are not too good at web browsing. So a market is born: a small screen web browser.

The Netbook was first and does the job by scaling down a laptop so that it is ultra portable. Apple thought better, and made a smaller device that still offered a 10" screen that could be used in portrait or landscape. And they added 3G for that always-on experience.

What the iPhone, Androids and Nokia's have shown, is that the new killer-app is an app store. A place to buy your software, be it office applications, games, music, video, books or just cool toys.

The OS is irrelevant.

The design is far more important than the hardware. Low powered computers are fast enough - adequate. You don't need to worry about storage, frame rates, resolution and interfaces since they have everything that you typically need. Now it is more important to consider looks, weight, portability, battery life and Apps.

What Apple and Google have also done is to reduce the risk of malware by selecting the ARM microprocessor and a more secure-by-design operating system. ARM processors don't allow some of the techniques used to cause a PC to execute foreign code, and UNIX and Linux have demonstrated that they are resistant to malware.

Apps too, are more likely to be web apps - based on HTML and JavaScript. These can be easily sandboxed to protect the OS and other core applications and services. Google also has their Native Client which allows native compiled code to run safely and securely on a PC or ARM machine.

A new OS will enter the scene.

Perhaps a few. Windows will decline as more devices are sold with Android, Linux and OS-X. I don't think Symbian will survive either.

If the OS is irrelevant then it will shrink and become a specific purpose, custom OS for the particular device. If all the applications run in a browser then applications will no longer depend on OS services. Instead they will mostly depend on browser services - the browser is the new OS and it includes the secure, windowing/graphics environment for games, music, videos, office applications and browsing.

Recently Google released a new programming language called Go. To me, it seems to be a descendant of a language designed at Bell Labs called Newsqueak. Rob Pike developed Newsqueak and is also developing Go. Ken Thompson, who also worked at Bell Labs, is also part of the Go development effort at Google. Both Newsqueak and Go are used to do systems programming - a language to build or experiment with operating systems. Why would Google want that - they use Linux don't they?

Ken Thompson and Rob Pike both worked on Plan 9 and it's descendent, Inferno, which was open-sourced in 2005.

I think Google is looking to use Go to compile a descendant of Inferno to become the base OS for Google and Android. Why? Go makes concurrent programming easy, and future servers and appliances are going to have lots of CPUs and GPUs.

Background

This is a video (2007) of Rob Pike talking about Newsqueak, Plan-9 and a toy window system.

My Dream Device

This started out as a wave discussion with a friend. Initially I was thinking about a NetBook/tablet type of device, but as I made my wish-list I realised that it had to be a phone.

CPU

• ARM not sure which one. ARM is a far more secure instruction set than x86. My understanding is that an ARM instruction can not jump into the middle of any other instruction so a major source of vulnerabilities are eliminated.

NETWORK

• WiFi 11n Settle for 11g. Nothing surprising here.
• 3G. This will need to be 4G shortly - WiMAX or LTE?

OS

• If it were a NetBook then I'd like Ubuntu. But for a Phone it has to be Android or possibly ChromeOS in the future.
• Open.

HDD

• Flash.
• Micro SD

GPS

• GPS (A-GPS)
• Compass

SCREEN

For me, a Netbook needs an 11" to 12" screen. Current 9"-10" devices are just a little too small for lot's of use. But for a phone, 11"-12" is too big.

I have an iPod Touch. It is great but web browsing is barely useable. So the screen needs to be bigger. By way of comparison, I also have a Casio FX-82-like calculator. It is 5/8" (16mm) thick, 3 3/8" (85mm) wide and about 6 1/4" long (155mm). It easily fits in a pocket and not too big to be a phone.

So, a bit bigger wider and a bit thicker than a scientific calculator.

• Something that will fit in a pocket.
• Let's say two 4"-ish x 7"-ish screens hinged along their long sides to form a book-like device.
• How about the Golden Ratio (about 1.618). The screen could be 3.7"x6" (7" diagonal). The two screens together would be 6"x7.4" or 9.5" - that's a NetBook size, but it would fit in your pocket.
• I think the combined ePaper/LCD screen of Pixel Qi would do nicely.
• Video should run on either 1 or both screens.
• Page reading in portrait mode - no window borders.
• Full HD resolution when combined

SIZE

• Thin <3/4" (19mm)
• Thin margin around the screens - say 1/8" (3mm).

KEYBOARD

• 2 Touch screens with On-screen keyboard. One screen could be the main screen and the other working as touchscreen keyboard. The keyboard could enter ePaper mode to save power and the other screen would only need color LCD when watching videos or viewing/taking pictures.

PHONE

• Mic and Ear speaker on the outside of the case.
• There would need to be a spot or touch surface to answer a call.
• To make call you would open the device and select or dial the number. Once dialed the lid can be closed and it works like a phone for there on.

EXTRAS

• Camera 3-5MP - A book-like design would make this a little impractical, but one above a screen and another on the outside would be possible.
• Stereo Speakers
• 8 Hr battery life when uses as a NetBook - both screens on etc.
• 7 days closed.
• Mic/Headphone jack - like the iPhone
• Bluetooth (for external keyboard/display while on my desk - why not use it at work and home as well while it is charging?)
• Removable battery
• Vibrate for errors, tactile feedback, alarms.
• Induction charging mat
• Solar panel to lengthen battery life a little bit - it would make for a nice external surface as well.