How to remove commas from quoted strings in csv files

I needed to remove commas (,) from within double quotes (") in a Comma Separated Variable (CSV) file.

For example, you can use cut -d, -f2,4,5 to extract fields 2, 4 and 5.

But if there is a comma in the text of a field like this "hello, world" you are generally stuck.

Also SQLite can also import csv files, but again commas in quotes cause problems.

I was stuck until I managed to create this sed script that will work in many cases.


# This bash function uses sed to remove up to 4 individual commas
# sequences from a quoted string in a csv file.


# eg. "Hello,, World, nice day." -> "Hello World nice day."



function removeCommas(){
  while read data; do
    echo "$data" | sed -e 's/^/,/g' | sed -e "s/$/,/g" \
      | sed -e 's/\(,\"[^,]*\),*\([^,]*\),*\([^,]*\),*\([^,]*\),*\(.*\",\)/\1\2\3\4\5/g' \
      | sed -e 's/^,//g' | sed -e 's/,$//g'
  done
}


A friend mentioned that the sed commands can be combined as follows:


    echo "$data" \
      | sed \
      -e 's/^/,/g' \
      -e "s/$/,/g" \
      -e 's/\(,\"[^,]*\),*\([^,]*\),*\([^,]*\),*\([^,]*\),*\(.*\",\)/\1\2\3\4\5/g' \
      -e 's/^,//g' \
      -e 's/,$//g'


How it works


The engine uses sed.


This sed statement takes input from stdin and replaces the regular expression 'from' with 'to' for any and all occurrences of 'from'.


sed -e 's/from/to/g'

First, I add a comma to the start and end of each line with this:

sed -e 's/^/,/g' | sed -e "s/$/,/g"

These make the function work for special cases and they get removed after the commas have been removed.

The 'from' string starts of by finding the beginning of a quoted string ',\"' then all non-comma characters '[^,]*'.

This pattern is enclosed in brackets '\(' and '\)' to assign the matching pattern to, in this case, part 1.

Then it matches the next one or more commas ',*'. This is not in brackets since we don't want them.

The next part of the pattern '\([^,]*\)' is like the first: it finds a string of non-comma characters and keeps the values as part 2.

Then we skip over any commas again.

This sequence can be repeated as many times as you like. I did it 3 times.

The pattern ends like it starts. But this time it reads any character including commas up to the trailing quote using '.*'. Then it reads the trailing quote '\"' and comma ','. All of this makes part 5.

This means that it will only filter the first 4 sequences of commas. To make it do more, repeat the middle pattern ',*\([^,]*\)' and increase the output parts (below).

The 'to' expression is simply the concatenation of the 5 parts of the quoted string that are guaranteed to not contain a comma (well, except possibly for the last part), where '\N' is the nth part.

\1\2\3\4\5

Testing

I tested the function with this.

function testthis(){

  echo -n "\"$1\" --> \"$2\"..."

  echo "$1" | removeCommas | grep -qE "$2" && echo "Pass" \

    || echo "FAIL"

}

# test removeCommas

testthis "this test should fail to test the 'tester'" "anything but this"

testthis "" ""

testthis "," ","

testthis ",," ",,"

testthis ",\"\"," ",\"\","

testthis ",\",\"," ",\"\","

testthis "1,2,\"3,4 5 6 7\",8,9,10" "1,2,\"34 5 6 7\",8,9,10"

testthis "1,2,\"3,4,5 6 7\",8,9,10" "1,2,\"345 6 7\",8,9,10"

testthis "1,2,\"3,4,5,6 7\",8,9,10" "1,2,\"3456 7\",8,9,10"

testthis "1,2,\"3,4,5,6,7\",8,9,10" "1,2,\"34567\",8,9,10"

testthis "1,2,\"3,,4,,5,,6,,7\",8,9,10" "1,2,\"34567\",8,9,10"

testthis "1,2,\"3,,4,,5,,6,,7,8\",8,9,10" "1,2,\"34567,8\",8,9,10"

testthis "\"tricky one where the quoted string starts the line 3,,4,,5,,6,,7,8\",8,9,10" "\"tricky one where the quoted string starts the line 34567,8\",8,9,10

testthis "1,2,\"3,,4,,5,,6,,7,8 tricky one where the quoted string ends the line \"" "1,2,\"34567,8 tricky one where the quoted string ends the line \""

Firewall Rule Testing with BASH and TCPTraceRoute

I wanted to block the use of any DNS server except those that I select (google, openDNS and my router).

I also wanted to make sure that these DNS servers work and that others do not.

So I made a BASH script to verify my firewall rules.

#!/bin/bash

# only particular DNS servicer are allowed to be contacted. 

# this tests that this is so

LOCAL="the.IP.address.of.your.router"

ALLOW="8.8.8.8 8.8.4.4 208.67.220.220 208.67.222.222"

BLOCK="220.233.0.4 61.88.88.88 202.139.83.3 61.9.194.49 61.9.195.193 61.9.133.193 61.9.134.49 203.161.158.2"

echo "Testing DNS servers via UDP that are allowed to work..."

for d in $LOCAL $ALLOW; do

  dig @$d somename +time=1 +tries=1 +notcp > /dev/null

  [ $? -ne 0 ] && echo "FAIL: Failed to get response from $d via UDP." && exit 1

  echo "PASS: $d responded via UDP."

done

echo "Testing DNS servers via TCP that are allowed to work..."

for d in $LOCAL $ALLOW; do

  dig @$d somename +time=1 +tries=1 +tcp > /dev/null

  [ $? -ne 0 ] && echo "FAIL: Failed to get response from $d via TCP." && exit 1

  echo "PASS: $d responded via TCP."

done

echo "Testing DNS servers via UDP that are NOT allowed to work..."

for d in $BLOCK; do 

  dig @$d somename +time=1 +tries=1 +notcp > /dev/null 

  [ $? -eq 0 ] && echo "FAIL: Got response from blocked DNS server $d via UDP." && exit 1 

  echo "PASS: DNS server $d via UDP was correctly blocked." 

done 

echo "Testing DNS servers via TCP that are NOT allowed to work..." 

for d in $BLOCK; do 

  dig @$d somename +time=1 +tries=1 +tcp > /dev/null 

  [ $? -eq 0 ] && echo "FAIL: Got response from blocked DNS server $d via TCP." && exit 1 

  echo "PASS: DNS server $d via TCP was correctly blocked." 

done 

echo "" 

echo "Firewall PASSed."

Then I thought that I might be able to test other TCP blocking rules by setting the IP packet's time-to-live (TTL) to a small number and looking for ICMP time expired packets. To do this I needed to use tcptraceroute to get the core functionality. On the Mac I got this from fink.

If I get some response, the firewall is NOT blocking an outgoing port. If I get stars (* * *) then it probably is blocking the port.

#!/bin/bash

echo "Testing blocked outgoing port..."

# set TTL to 2 hops: host to ADSL router, ADSL router to ISP gateway

# if the ISP responds to TCP TTL timeouts then a blocked port should get '2  *'

# whereas an open outgoing port should get something more complicated like this:

# '2  37.1.233.220.static.exetel.com.au (220.233.1.37)  23.176 ms'

#sudo tcptraceroute -q 1 -w 1 -f 2 -m 2 www.google.com 79 | grep '2  *' && echo "blocked"

BLOCK="135 136 137 138 139 445 593 1863 110 9000 5190 23 1503 1720 53"

VICTIM="www.some.real.site.com"

# The victim should not get any packets if the firewall rules are right.

for p in $BLOCK; do

  sudo tcptraceroute -q 1 -w 1 -f 2 -m 2 $VICTIM $p | grep '2  \*'

  [ $? -ne 0 ] && echo "FAIL: Port $p is open for outgoing traffic." && exit 1

  echo "PASS: Port $p is blocked for outgoing traffic."

  echo ""

done

ALLOW="80 8080 443 25 21 119 22 123"

VICTIM="www.some.real.site.com"

# again, the victim should not get any packets since TTL is so small.

for p in $ALLOW; do

  sudo tcptraceroute -q 1 -w 1 -f 2 -m 2 $VICTIM $p | grep '2  \*'

  [ $? -eq 0 ] && echo "FAIL: Port $p is blocked for outgoing traffic." && exit 1

  echo "PASS: Port $p is open for outgoing traffic."

  echo ""

done

echo "" 

echo "Firewall PASSed."

You will need to modify the script to suit your firewall rules.

A Post from the command line using GoogleCL

One small step for Google. One giant leap for scripting.

Google Captured Data and Passwords in Australia - an Estimate

Most would have heard by now that Google's StreetView cars have been taking pictures of our streets and at the same time collecting WiFi SSIDs. But they have also been collecting other data that has got them into trouble with Governments and privacy groups.

http://googleblog.blogspot.com/search/label/privacy

Google sponsored report

http://www.google.com/googleblogs/pdfs/friedberg_sourcecode_analysis_060910.pdf

In Australia it is no different. Senator Conroy has been very vocal about this.

http://www.abc.net.au/news/stories/2010/05/25/2908415.htm

I was chatting to a friend and a quick calculation seemed to indicate that the amount of data and passwords captured must be small.

So, with lots of assumptions I have looked at two cases: the 'best' case and the 'worse' case.

To do any estimation I needed numbers. Fortunately our Bureau of Statistics (ABS) provided what I needed.

Here are my assumptions:

1. From the ABS December 2009, 5.2M ADSL and Cable subscribers. http://abs.gov.au/ausstats/abs@.nsf/mf/8153.0/

2. 114,400 TB downloaded data per year (ABS)

3. Uploaded data is 5 - 20% of downloaded data.

4. Between 50 and 80% of all subscribers use encrypted WiFi.

5. WiFi range from an indoor household Access Point is +-100m to +-250m.

6. The StreetView car samples 5 channels per second (See report).

7. Data in overlapping channels can be received in channels 1, 6, 11.

8. StreetView car travels at 30 - 50 km/h between 8:00 and 16:00. The car need bright light to take photos and for safety (fatigue) reasons they would only do 8 hour shifts - probably with breaks every 2 hours or so.

9. Uploaded data is sent evenly throughout the day from domestic homes and that between 8:00 and 16:00 the upload data rates are average.

10. Households send 1 - 10 non-secured passwords per day.

11. Household use the internet between 16 and 20 hours per day.

WiFi Reception Performance

One important variable that I did not model was the error rate of received frames that is related to distance: the further away from a WiFi access point, the lower the change of receiving a frame without error. The assumption that you can receive all frames within 100m (worse case) or within 250m (best case) is, frankly, silly and unrealistic. This will mean that any result is going to establish an upper limit for both cases.

WiFi Channels

So basically I assume the street car samples 3 channels at the rate of 5 per second. I conservatively assume that data on all the other WiFi channels can read using just these 3 channels. I doubt this is correct so again it will establish an upper limit for both cases.

Reception Period

I calculate the time the car is in range of a WiFi base is between 14 and 60 seconds and can sample between 5 and 20 seconds worth of data. The car probably travels at a speed between 30 and 50 km/h and can collect WiFi frames from any given access point for one third of the time.

Data Collected

By assuming that households transmit data continuously, and knowing the average amount of data sent each second I can estimate the amount of data collected on average per WiFi access point.

Australians downloaded 114,000 TB of data in 2009. Most web browsing is downloading, especially when we are talking about reading bank accounts and email.

Assuming uploaded data is between 5 and 20% of the amount we download, I arrived at an upload data amount of between 5700 - 23,000 TB per year or 400 - 1400 bps.

This means that they can record between 250 and 3400 Bytes of data per WiFi access point (SSID).

Password Capture

I have assumed that passwords are sent in the clear (unencrypted) between 1 to 10 times per day. Most sites (such as banks) use HTTPS and email hosting services generally support encrypted SMTP/POP/IMAP to send account and password information. But some sites may still allow access to mail and other discussion sites using unencrypted passwords. It is these passwords that Google could have captured on unencrypted WiFi access points.

The probability of capturing a password is between 0.002% and 0.14% so this means that between 17 and 3600 passwords would be captured Australia-wide as the StreetView car drove by.

Resulting Estimate

Data collected: 250 - 3400 Bytes per WiFi access point
Passwords collected: 17 - 3600 Australia-wide

The difference between my best and worse case is just over 1 order of magnitude for bytes collected and just over 2 orders of magnitude for passwords collected. This reflects the level of uncertainty on my estimates.

I think the real values will be much lower for these reasons:

1. During the day is not the peak time for downloads from households. On weekdays, on average, many family members will be at school or at work so it stands to reason that less internet activity will take place.

2. Encrypted WiFi access points seems to be closer to 80% rather than 50%. People are more aware about security and ISPs have done a lot to encourage the security of wireless networks.

3. Few services use unencrypted passwords - I can not think of any except for POP based email. All banks use some for of encryption - to do otherwise would be incompetent. Unfortunately it may be the small businesses that allow staff to access their email via unencrypted POP that are letting their employees down. GMail and Yahoo only seem to allow encrypted authentication so your account name and password are safe.

4. WiFi range is probably not even 100m and hardly 250m and the ability to pickup a transmission from a laptop/mobile at these distances is low. The further away from a WiFi access point, the higher the probability of receiving an errored frame that would contain no reliable data.

5. Uploaded data is probably less that 5% of Downloaded data. A packet containing an account name and password is small compared to the resulting page that gets downloaded.

6. Even when a WiFi access point is unencrypted, typically traffic to sites that require privacy are encrypted. So the actual unencrypted data is publicly available web pages, images, video and javascript code.

My Guess

The above best and worse case set an upper limit. But the worse case is too optimistic regarding the amount of uploaded traffic, WiFi range and the number of unencrypted access points. So I would suggest the number of passwords collected to be around 17 - say 10 to 100 - Australia-wide and the amount of unencrypted personal data to be much less - say 10 to 100 bytes per household.

IPhoto Script to Remove Missing Photos

For some reason when you try to open photos you get a big exclamation mark! This seems to happen when the actual photo is missing. Perhaps it has been deleted through the file system or perhaps iPhoto is confused or perhaps because iPhoto crashed during some operation. Who knows.

I wrote this script to find these 'photos' and to move them to the trash.

tell application "iPhoto"

  set curPhotos to selection

  if (count of curPhotos) ≤ 0 then

    display alert "You need to select the photos you want me to process."

  else

    set countPhotos to count of items in curPhotos

    repeat with i from 1 to countPhotos

      set thisPhoto to item i of curPhotos

      try

        set t to info for (image path of thisPhoto as POSIX file)

      on error eStr number eNum partial result rList from badObj to expectedType

        log eStr

        select thisPhoto

        remove thisPhoto

      end try

    end repeat

  end if

end tell

Open Script Editor,  cut and paste the above script into the editor, Compile it to check for errors, and save it to a file - perhaps on your desktop but anywhere is fine.

To run it, open iPhoto, select the Photos Library, Select all photos you want to process (Edit - Select All is what I usually do), and then switch back to the Script Editor and press Run.

When it finishes you may have some missing photos in your trash. You can decide what to do with them at this point - I just empty the trash.

If you use it, write a short comment about whether it was helpful or not or whether it worked or not. If you improve the script, let me know as well.

Steve Jobs on Flash

Steve Jobs has posted his thoughts on Adobe's Flash and why Apple have not allowed Flash to be installed on iPhones and iPads.

Adobe have, probably accidently, developed something like HTMLv5 years (8?) ahead of W3C. They saw the need for a standard, OS-agnostic platform for the development of applications and the presentation of content including video, audio, animation and interactivity.

Adobe's Actionscript was also fast. It seems that all other browsers felt that there was no need to work on Javascript speed because CPU's were getting faster each year - as a consequence of Moore's Law.

But something happened early this decade - CPU speed (clock rates) started to slow and to compensate, manufacturers began to introduce multi-core processors.

Web pages, however, seem to be hard to render using multiple threads and so Javascript performance began to stagnate.

Enter Google. They believe in open standards, an open web and everything running in the browser, sourced from the internet. To make this possible, Javascript needed to be fast so they started the Chrome browser project which incorporated a new and fast V8 Javascript engine. Shortly afterwards, it seemed, Webkit (Apple) and Mozilla began to pickup their Javascript performance as well. And now, we see Microsoft is also working on Javascript performance and standards compliance for IE9.

Adobe have had a good run, but standardisation has caught them up. (In a similar way, standardisation caught Lotus Notes which, for the time it was developed, was - or appeared to be - visionary: Tabbed workspace, forms, separation of data from presentation, security, encryption, signed applications...).

Back to Steve Job's posting. Steve thinks that Flash is closed and the Apple is the exact opposite - meaning open.

Open

First, there’s “Open”.

Adobe’s Flash products are 100% proprietary. They are only available from Adobe, and Adobe has sole authority as to their future enhancement, pricing, etc. While Adobe’s Flash products are widely available, this does not mean they are open, since they are controlled entirely by Adobe and available only from Adobe. By almost any definition, Flash is a closed system.

Apple has many proprietary products too. Though the operating system for the iPhone, iPod and iPad is proprietary, we strongly believe that all standards pertaining to the web should be open. Rather than use Flash, Apple has adopted HTML5, CSS and JavaScript – all open standards. Apple’s mobile devices all ship with high performance, low power implementations of these open standards. HTML5, the new web standard that has been adopted by Apple, Google and many others, lets web developers create advanced graphics, typography, animations and transitions without relying on third party browser plug-ins (like Flash). HTML5 is completely open and controlled by a standards committee, of which Apple is a member.

Apple even creates open standards for the web. For example, Apple began with a small open source project and created WebKit, a complete open-source HTML5 rendering engine that is the heart of the Safari web browser used in all our products. WebKit has been widely adopted. Google uses it for Android’s browser, Palm uses it, Nokia uses it, and RIM (Blackberry) has announced they will use it too. Almost every smartphone web browser other than Microsoft’s uses WebKit. By making its WebKit technology open, Apple has set the standard for mobile web browsers.

What if we take what Steve wrote and swap 'Apple' with 'Adobe' and 'Flash' with 'Mac OS X'? This is what we get:

Apple’s Mac OS X products are 100% proprietary. They are only available from Apple, and Apple has sole authority as to their future enhancement, pricing, etc. While Apple’s Mac OS X products are widely available, this does not mean they are open, since they are controlled entirely by Apple and available only from Apple. By almost any definition, Mac OS X is a closed system. 

It isn't perfect, but it is very close to the truth. Apple use open source, contribute to and develop with open source software, but they produce very proprietary software. You can not run OS X on any other hardware other than Apple hardware. To write well-integrated  OS X applications, you need to use Apple's proprietary interfaces - Carbon or Cocoa. These applications will not run on other OSs (Windows or Linux) and so some developers choose to use frameworks that allow developers to write applications that will run on any OS platform - or they use Java. Steve doesn't like this.

And now, use have to use Apple's APIs directly to write applications for the iPhone and iPad. This has upset Adobe (and probably a number of other organisations that make cross-platform frameworks such as XMLVM).

I think Steve accepts an open web, but everything else should be closed, and Apple is certainly insisting on this path. The iTunes store can only really be used with iTunes and iTunes can only be used with iPods and iPhones and now iPads.

I wonder when iTunes will stop supporting Windows?

iPhoto, iDVD and iMovie only work on OS X too. Keeping your photos on a Mac using Apple's software does tend you lock you in to using Apple hardware and software for a long time.

Full Web

Second, there’s the “full web”.

Adobe has repeatedly said that Apple mobile devices cannot access “the full web” because 75% of video on the web is in Flash. What they don’t say is that almost all this video is also available in a more modern format, H.264, and viewable on iPhones, iPods and iPads. YouTube, with an estimated 40% of the web’s video, shines in an app bundled on all Apple mobile devices, with the iPad offering perhaps the best YouTube discovery and viewing experience ever. Add to this video from Vimeo, Netflix, Facebook, ABC, CBS, CNN, MSNBC, Fox News, ESPN, NPR, Time, The New York Times, The Wall Street Journal, Sports Illustrated, People, National Geographic, and many, many others. iPhone, iPod and iPad users aren’t missing much video.

Another Adobe claim is that Apple devices cannot play Flash games. This is true. Fortunately, there are over 50,000 games and entertainment titles on the App Store, and many of them are free. There are more games and entertainment titles available for iPhone, iPod and iPad than for any other platform in the world.

Adobe claim that by not having Flash, iPhone users are missing out on the full web experience. It is true that any Flash content can not be displayed on the iPhone/iPad, but I think most web sites will develop special versions of their sites specifically for iPhone/Android devices that have limited screen sizes and limited user input interfaces: mice and touch pads offer very fine pointing and clicking controls whereas fingers are a little less accurate and cover-up what you are touching. On-screen keyboards are great but they are no match for a reasonably large physical keyboard.

In time, keyboards may well disappear, but they will be replaced with something that works as good as the real thing, not something that slows you down.

So iPhone and Android users alike are already missing some of the full web experience, but they have the advantage of mobility and newer customised web sites that will only make the experience better.

The existence or lack of H.264 is not really an issue. Flash now supports H.264 and any video will be in a format that iPhone users will be able to view. Interestingly H.264 is proprietary (and Apples has some interest in the patents associated with it) so Steve is not pushing for an open web experience here - he want's royalties and refuses to add the open source Ogg/Theora audio and video formats to Safari to help make the web truly open and free.

Security

Third, there’s reliability, security and performance.

Symantec recently highlighted Flash for having one of the worst security records in 2009. We also know first hand that Flash is the number one reason Macs crash. We have been working with Adobe to fix these problems, but they have persisted for several years now. We don’t want to reduce the reliability and security of our iPhones, iPods and iPads by adding Flash.

In addition, Flash has not performed well on mobile devices. We have routinely asked Adobe to show us Flash performing well on a mobile device, any mobile device, for a few years now. We have never seen it. Adobe publicly said that Flash would ship on a smartphone in early 2009, then the second half of 2009, then the first half of 2010, and now they say the second half of 2010. We think it will eventually ship, but we’re glad we didn’t hold our breath. Who knows how it will perform?

Steve is also worried about Adobe's Flash reliability and security. He has the statistics and claims that Flash is the number one cause of Mac crashes. I wonder what the number two cause is?

So, he say that it is best to keep Flash away from the iPhone and iPad.

Google has taken a different, seemingly more rational approach. They have decided to include Flash into Chrome and have made plans to address reliability and security issues.

Google seeks to eliminate problems rather than add layers to reduce risk. Their Native Client does just this: an architecture to allow any plugin to run so long as it can be validated that it complies to hard rules to that prevent software doing anything harmful. This has to be better than validated compiler tool chains, signed applications, layers of malware filtering and heuristic code analysis.

Battery Life

Fourth, there’s battery life.

To achieve long battery life when playing video, mobile devices must decode the video in hardware; decoding it in software uses too much power. Many of the chips used in modern mobile devices contain a decoder called H.264 – an industry standard that is used in every Blu-ray DVD player and has been adopted by Apple, Google (YouTube), Vimeo, Netflix and many other companies.

Although Flash has recently added support for H.264, the video on almost all Flash websites currently requires an older generation decoder that is not implemented in mobile chips and must be run in software. The difference is striking: on an iPhone, for example, H.264 videos play for up to 10 hours, while videos decoded in software play for less than 5 hours before the battery is fully drained.

When websites re-encode their videos using H.264, they can offer them without using Flash at all. They play perfectly in browsers like Apple’s Safari and Google’s Chrome without any plugins whatsoever, and look great on iPhones, iPods and iPads.

Steve ignores other Flash applications here (which may or may not be kind to battery life) and focuses on H.264 video playback. Again, if Flash now supports H.264 then this is a non-issue (except that web sites would need to re-encode their content which they have to do for the iPhone/iPad anyway).

Touch

Fifth, there’s Touch.

Flash was designed for PCs using mice, not for touch screens using fingers. For example, many Flash websites rely on “rollovers”, which pop up menus or other elements when the mouse arrow hovers over a specific spot. Apple’s revolutionary multi-touch interface doesn’t use a mouse, and there is no concept of a rollover. Most Flash websites will need to be rewritten to support touch-based devices. If developers need to rewrite their Flash websites, why not use modern technologies like HTML5, CSS and JavaScript?

Even if iPhones, iPods and iPads ran Flash, it would not solve the problem that most Flash websites need to be rewritten to support touch-based devices.

Steve says that touch interfaces don't work the same as mice/touchpads and therefore Flash applications wont work anyway. Interestingly, Flash started out as a PenPoint OS which may have had similar behaviour to a touch interface, but I don't know.

What Steve fails to mention is that many web sites also make use of mouseover events to show text and graphics as your mouse pointer hovers over a particular word, link or image. Blogger uses tooltips which help a little in explaining the function of a button. Even Apple's web store for the iPhone uses 'rollovers' to display the help, account and cart menus! I guess Apple had to re-write these sites for the iPhone.

Actually, I just checked - the store is virtually unusable on an iPod touch. You can click on the help menu and a menu will be displayed so you can then double-touch to zoom in. Wouldn't this work for Flash too?

All web sites that need mouseover events to operate will have to be re-written for the iPhone so banning Flash does not fix this - the web site owner needs to do some work to make their sites more accessible for iPhone and iPad users. So why is this an issue Steve? This looks like hypocrisy to me.

The 'real' reason

Sixth, the most important reason.

Besides the fact that Flash is closed and proprietary, has major technical drawbacks, and doesn’t support touch based devices, there is an even more important reason we do not allow Flash on iPhones, iPods and iPads. We have discussed the downsides of using Flash to play video and interactive content from websites, but Adobe also wants developers to adopt Flash to create apps that run on our mobile devices.

We know from painful experience that letting a third party layer of software come between the platform and the developer ultimately results in sub-standard apps and hinders the enhancement and progress of the platform. If developers grow dependent on third party development libraries and tools, they can only take advantage of platform enhancements if and when the third party chooses to adopt the new features. We cannot be at the mercy of a third party deciding if and when they will make our enhancements available to our developers.

This becomes even worse if the third party is supplying a cross platform development tool. The third party may not adopt enhancements from one platform unless they are available on all of their supported platforms. Hence developers only have access to the lowest common denominator set of features. Again, we cannot accept an outcome where developers are blocked from using our innovations and enhancements because they are not available on our competitor’s platforms.

Flash is a cross platform development tool. It is not Adobe’s goal to help developers write the best iPhone, iPod and iPad apps. It is their goal to help developers write cross platform apps. And Adobe has been painfully slow to adopt enhancements to Apple’s platforms. For example, although Mac OS X has been shipping for almost 10 years now, Adobe just adopted it fully (Cocoa) two weeks ago when they shipped CS5. Adobe was the last major third party developer to fully adopt Mac OS X.

Our motivation is simple – we want to provide the most advanced and innovative platform to our developers, and we want them to stand directly on the shoulders of this platform and create the best apps the world has ever seen. We want to continually enhance the platform so developers can create even more amazing, powerful, fun and useful applications. Everyone wins – we sell more devices because we have the best apps, developers reach a wider and wider audience and customer base, and users are continually delighted by the best and broadest selection of apps on any platform.

Steve simply wants to make it hard for any developer to write applications for multiple platforms.

It may be true that frameworks limit the features, but equally it may be true that the Apple iPhone/iPad OS is the lowest common denominator - why do you think that Apple will always have more features that your competitors? Can you merge directories of the same name in OS X Finder yet?

If this is a real reason, then why not specify that any framework must support the whole API? This surely would address your concerns about having all the features available to the developer.

Conclusion


I am not a fan of Flash, but it is generally required for YouTube for PC and laptop users.

I agree the HTMLv5 is the future but I disagree that it should only include a patented and proprietary H.264.

Apple could allow Flash on the iPhone since web sites have to be re-written anyway for iPhone users.

Battery life while playing videos may not be an issue if Flash on the iPhone/iPad used H.264 and Flash had access the Apple's H.264 API.

Security is solvable and Google and Adobe seem to be about to demonstrate this.

Postscript

The person who sent me the link to Steve's posting owns a Mac and an iPod that I know for certain. They are going to say 'bye bye' to Apple based on Steve's compelling argument against proprietary software:

Jobs makes a compelling case for not trusting a proprietary company who has sole control over their proprietary products.

So, bye bye Apple.

I have 3 Mac Book Pros, iPod Nano, iPod Touch, Time Capsule and have been influential in at least the purchase of a Mac Mini over the last 5 years (about $15,000 worth at time of purchase). I am re-considering my use of Apple software and hardware and I will certainly not purchase anywhere near the amount of Apple products in the next 5 years - if any.

I will also be removing the shackles of proprietary Apple software by moving my photo and music collections to Open Source software and online services such as Google Docs. Not just because of this open letter about Flash, but because Apple is removing people's freedom to develop and use software the way they choose to.

Simple Rolling Hash- Part 3

The Rolling Hash

Now that there is a way to remove the first character and append a new last character (in constant time) to a string hash value, we can also use this hash function suite to perform substring searches in linear time.

To find a substring of length m in a string of length n you might proceed as follows:

Start at the first character of the string

Compare the substring to the string for m characters.

If same, then the substring is found.

else, repeat from the next character of the string (stop when there are less than m characters left in the string)

In practice this works well since it is unlikely that more than a few character will match each round so the effective time efficiency is much less than O(N x M). But for some strings, such as DNA which have small alphabets, the number of matches in each round could be large.

By using a rolling hash this can be reduced to linear-time.

Calculate the hash of the substring we are searching for.

Start with a hash of the first m characters of the string

If the hash values match then the substring is found - probably.

else remove the first character of the string from the hash and add the m+1 th character to the hash.

Now the hash is of m characters from the next character of the string.

This process is O(N).

The catch is that this finds a substring with high probability. To ensure that it is a match we need to check each character.

A Good Hash Function

My next question was 'is this hash good enough?'.

After some research I found that hashing is similar to a problem called Balls and Bins. The idea is to analyse mathematically the result of randomly throwing m balls into n bins.

It turns out that if a hash function is 'good' then it should produce results similar to randomly throwing balls (strings) into bins (string hash numbers).

I am no mathematician so this was slow going and a bit frustrating since I don't know all the tricks used to simplify problems.

I found that for a good hash function, the number of unused hash numbers after generating hash numbers from n random-like strings should be n/e. This is easy to test: I made an array of size n, generated random strings, hashed them, and incremented the element of the array indexed by the hash number.

(To keep the array size small, I first reduced the 28 bit hash number to a 16 bit number by mod 65536).

The probability that a hash number was used once is also n/e. And likewise it is easy to calculate the probabilities of a hash number being used k times:

Pr[ k ] = 1/ek!

And the probability that a hash number is used k or more times is roughly

Pr[ >=k ] ~ ((e/k)**k)/e

(to be completed)

Simple Rolling Hash- Part 2

String Slicing

I also wanted to extract substrings of appended or fixed-length strings quickly as well. 

Since most strings would be less than 64 characters (I reasoned), this too would be virtually constant-time. 

In the case of appended strings, the slicing would be proportional to the number of appended strings which would be roughly O(N) but with a very small constant factor in the order of at least 1/10 th on average.

Again, to ensure that the hash calculation would not harm performance, I needed a way to adjust the hash of a string by the hash of the leading or trailing substrings.

eg. 

hash( "def" ) = some_function( hash ( "abcdef" ) , hash( "abc" ) )

hash( "abc" ) = some_function( hash ( "abcdef" ) , hash( "def" ) )

To do this I needed to choose carefully the value of k such that k * inv(k) = 2**28 + 1, where inv(k) is the multiplicative inverse of k - ie. k and inv(k) are factors of 2**28+1.

Lucky Break

This part is simply a fluke. I needed my hash to be 28 bits so that I can store type information in the other 4 bits of a 32-bit value. 

I could use a hash that is less that 28 bits, but not more. Fortunately, 2**28 +1, which is 268,435,457 has two prime factors: 17 and 15790321.

It is also fortunate that 17 is a reasonable multiplier for a hash as well since, I reasoned, it preserves the low 4 bits of each character which contain the most information for the letters and numbers and punctuation characters.

I have found another hash function that uses k=17.

http://www.codeproject.com/KB/recipes/hash_functions.aspx

Removing Characters and Calculating the New Hash in O(1)

To remove a leading character from a string of length n, you need to remove it's component of the hash which has been multiplied by k, n-1 times. So the new hash is

hash( s' ) = hash( s ) - k**(n-1) * c, where c is the first character of the string s

This can be done in constant-time, but removing M characters takes linear-time, O(M).

In the more general case, removing a leading substring of m characters follows the same pattern: here the leading substring has been multiplied by k, n - m times.

hash( s' ) = hash( s ) - k**(n-m) * hash( f ), where f represents the leading m characters of the string s.

To remove the trailing character from a string of length n, you need to subtract it from the hash and then divide the hash of the string by k. Division can be performed by multiplying by the inverse of k which is 15790321.

hash( s' ) = ( hash( s ) - c ) * inv( k ), where c is the last character of the string s.

To remove the trailing m characters from a string of length n, you need to subtract the hash of the m characters and then divide the hash of the string by k**m. Again, division can be performed by multiplying by the inverse of k which is 15790321.

hash( s' ) = ( hash( s ) - hash( t ) ) * inv( k )**m, where t is the last m characters of the string s.

Unfortunaely in the general case, to remove substrings from a string, I need the hash of each substring which takes linear-time.

Reducing Substring Hash Time

Here is where the fixed-length strings help: The only substrings that need to be calculated are the first and last fixed-length strings of a slice. And these substrings are between 1 and 63 characters long. 

eg. Assume the fixed-length strings are 3 characters long and slice a string to return 6 characters from the second.

( "abc" , "def" , "ghi" ) :2:6 -> ( "bc" , "def" , "g" )

In this case, the hash for "bc" and "g" have to be calculated, but the hash for "def" remains the same.

We can always guarantee minimal time by observing that if the substring to be removed is greater than half the length of the fixed-length string then it is better to re-calculate the hash of the resulting substring. This way, worst case is calculating the hash of fixed-length characters, or 64 in my case.

If it happens that the hash of the substrings is known then we get back to constant-time.

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.