Tuesday, December 29, 2009

iKeyEx 0.2b, CrashReporter 0.2e, class-dump-z 0.2a released

Change log for iKeyEx 0.2b:

  • iKeyEx now uses postinst triggers to register layouts and input managers (r594). Keyboard makers may leave out the [pre|post][inst|rm] scripts now because the list will be updated as your keyboard is installed or removed. (You still need a postinst script if you want to support automatic purging.) As a side effect, all input modes explicitly deleted by the user (via Mix and Match) will be added back in and activated. If you really don't want that layout, uninstall it from Cydia.

  • Fixed issue 470: iKeyEx left/right arrows don't work in multi-line text input controls (r593).

  • No longer crashes for a layout with different landscape and portrait layout classes (r588). Thanks erik_joya for reporting!



Change log for CrashReporter 0.2e:

  • Fixed issue 481: CrashReport doesn't recognize FAT binaries. (r592)



Change log for class-dump-z 0.2a (except Windows, I need to reinstall VS2008 first):

  • Support for "hints file" (r589). See this wiki page for detail. Thanks rpetrich for suggestion!

Tuesday, December 15, 2009

iKeyEx and 5-Row QWERTY 0.2a will be on Cydia soon.

The minor updates for iKeyEx (r579) and 5-Row QWERTY (r580) are released and will be on the Big Boss repo within 2 days. They can be downloaded from here as usual.

These updates are to address some defects reported after 0.2 is put on the repo, for iKeyEx:
  • Keyboards for Hebrew, Arabic and other right-to-left languages will default to use right-to-left input direction. (r578. Thanks DB42/OpenHebrew for reporting!)

  • Eliminated the built-in keyboard selection list in Settings, which became useless when iKeyEx is installed (it cannot be respected because the keyboard list is not safemode-safe otherwise). (r579)


For 5-Row QWERTY:
  • The , and . keys are swapped back to their expected position. (Thanks Optimo for noticing!)

  • Reset the special characters won't duplicate the double quote (") anymore. (r580)

  • Changing the layout flushes the cache correctly now. (issue 471)

Friday, December 4, 2009

iKeyEx 0.2~rc1, Cangjie 0.2-3, CrashReporter 0.2d released

O hai, long time no post!

This is because I have posted many material which were to be put here to the "iPhone Development Wiki" created by Dustin Howett. (And also because of "schoolworks and tests" :p) This blog will remain for release notes only.

Back to the main topic, there are 3 major releases today: iKeyEx 0.2~rc1:
  • Different layouts in portrait and landscape orientation is supported again (r509, thanks DB42 for noticing)
  • CrashReporter support (r548)
  • Hooks only UIKit (r548).
  • Config file is now placed in ~/Library/Preferences/hk.kennytm.iKeyEx3.plist (r559).
  • Keyboard settings won't be lost due to Safe mode anymore.
  • .cin IME: Stop radical composition on failure by default.
  • .cin IME: Corrected sorting.
  • Other minor stuff.


Cangjie 0.2-3:
  • The shift key will be disabled in the 倉頡QWERTY鍵盤. If you want to enter English letters in this keyboard layout, long press on a key (e.g. 水 -> [水][E]).


CrashReporter 0.2d:
  • Made UIProgressHUD truly model to avoid crash due to accidental file deletion during symbolication.
  • Smarter suspect identification.
  • Symbolication in command line with the "-s" flag.
  • Complains if you did not install syslogd :)

Monday, September 28, 2009

Sorry Ollie Kett but...

can I sell this scriptlet for $0.99?

javascript:var s=document.documentElement.outerHTML.replace(/&/g,"&amp;").replace(/</g,"&lt;").replace(/>/g,"&gt;").replace(/\n/g,"<br/>");document.open();document.write(s);document.close();


Disclaimer: This is not how Source Explore works. I did not even buy, try, pirate, or do anything with this app.

Saturday, September 26, 2009

Compiling iPhoneOS (3.1) apps with Xcode 3.2 without Provisioning Profile

Note: I don't know if this method still works, and I don't care. (And do not use the dd method mentioned in the article. It is extremely fragile to patch a binary file.)

Note 2: Please also check http://iphonedevwiki.howett.net/index.php?title=Xcode#Developing_without_Provisioning_Profile.

I want to compile.


This is easiest to solve. To compile you still need a certificate that can code-sign, but think this as a lip-service. Here is the procedure to create a self-signed code-signing certificate using Keychain Access. Make sure you create the certificate in the "login" (default) keychain, not the "System" keychain. After the certificate is created, perform these steps:
  1. Open /Developer/Platforms/iPhoneOS.platform/Info.plist. (Backup if you want to be safe.)
  2. Go to line 46. Replace the XCiPhoneOSCodeSignContext with XCCodeSignContext
  3. Go to line 79. Replace the XCiPhoneOSCodeSignContext with XCCodeSignContext
  4. Save the file.
  5. Restart Xcode.
  6. Compile!

After doing this, you can't use entitlements with Xcode anymore. But you have ldid -Sxyz.xml that does the same job.

Friday, September 25, 2009

GreenTea devices — You can still use Maps.

I have forcefully enabled GreenTea on my device (with MobileSubstrate) but almost everything behaves normally (iTunes is still accessible, YouTube is not hidden, Maps shows everywhere, etc.). The only difference I've noticed is:
  • There is no Hybrid mode in Maps when GreenTea is on.

Oh well.

Thursday, September 24, 2009

China, no Google Maps for you (maybe)

Today I was making the API for GraphicsServices, and found something... interesting.

Since 3.0 it was "well known" that there is a mysterious capability called as "Green Tea". Nothing was known except for this funny name. Things start to get clear in the 3.1 firmware. The GraphicsServices of 3.1 has a new set of API for querying some properties of Maps and MapKit. Strangely, in the disassembly of these functions, the mysterious "Green Tea" capability was refered, e.g.
Boolean GSMapKitUserShifting() {
static CFStringRef gtDefault = CFSTR("MapKitUserShiftingGreenTea");
static CFStringRef ngtDefault = CFSTR("MapKitUserShiftingNonGreenTea");
if (GSSystemHasCapability(CFSTR("green-tea")))
return GetMapsDefault(gtDefault);
else
return GetMapsDefault(ngtDefault);
}

It means the "Green Tea" capability is related to Maps, and takes different default values. No big deal right?

Sunday, September 20, 2009

class-dump-z 0.2-0 released.

(The version jump is mainly because every other project is moving to 0.2 era.)

Download: http://code.google.com/p/networkpx/downloads/detail?name=class-dump-z_0.2-0.tar.gz.

Note: Mac OS X 10.6 is required in this version.

What's changed:
  • Universal binary is supported. You can choose different architectures with the -u switch. (Not -arch or --arch because I didn't use getopt_long.)
  • Completely recognizes the new __LINKEDIT format. XXUnknownSuperclass shall no longer appears for 3.1 binaries.
  • __attribute__((visibility("hidden"))) will be included as well when the class is not exported (e.g. UIKeyboardLayoutStar).
  • Options to hide categories and protocols.
  • Sort class alphabetically, but keep class methods and -init methods on top (suggested by ashikase)
  • Option to choose between +(void)foo; and + (void)foo;. (suggested by ashikase)
  • Fixes a minor bug where timeOut:(int)out was written instead of timeOut:(int)anOut.

About the LC_DYLD_INFO[_ONLY] command.

With the introduction of the new __LINKEDIT format in iPhoneOS 3.1, many tools in the open toolchain are broken. This is all due to the unknown new commands LC_DYLD_INFO[_ONLY]. Although it's known to exist by many now, I found no useful documentation about this new format. Therefore, I'll outline what it is. Alternatively, you can study the source code of dyldinfo which contains every information here.

Friday, September 18, 2009

QuickScroll 2.2a should be available on Cydia soon.

QuickScroll 2.2 2.2a is released, and this marks the completion (so far) of the QuickScroll project. Thanks to the gdb for 3.1 I've finally squashed the "HiCalc" bug. I have already submitted it to BigBoss and should be available in a day. If you can't wait, you can still download from here.

Change log from 2.1a:
  • The scrolling indicator is no longer visible when scrollbar is used.
  • You should be able to use the scroller in HiCalc and other apps that canCancelContentTouches.

Change log from 2.2:
  • Fixed an obscure bug that causes crashing when the scroll view disappears. Thanks Optimo for discovering.

Porting the SDK's gdb for 3.1

The gdb on Cydia currently doesn't work on 3.1 because of the new Mach-O format. We could compile gdb from source (which I've failed to do so), wait for someone else to compile from source (which I'm still waiting), or just use the gdb in the SDK.

Update: saurik has updated the gdb package that works in 3.1, which will be available tomorrow. You can download it now from http://apt.saurik.com/debs/gdb_1128-8_iphoneos-arm.deb.


The SDK's gdb is in /Developer/Platforms/iPhoneOS.platform/Developer/usr/libexec/gdb/gdb-arm-apple-darwin. While you can run it directly on your Mac, it is in fact a fat binary with 3 architectures:

file gdb-arm-apple-darwin

gdb-arm-apple-darwin: Mach-O universal binary with 3 architectures
gdb-arm-apple-darwin (for architecture ppc): Mach-O executable ppc
gdb-arm-apple-darwin (for architecture i386): Mach-O executable i386
gdb-arm-apple-darwin (for architecture armv5): Mach-O executable arm


The ARMv5 portion is what we want. But this gdb is useless to run on the iPhoneOS because it lacks all the essential entitlements. While entitlements can be inserted using ldid, there is a limitation needs to be worked-around: ldid doesn't support the armv5 architecture. We have to modify the source code of ldid to allow it:
@@ -557,6 +557,7 @@
case 12: switch (framework->cpusubtype) {
case 0: arch = "arm"; break;
case 6: arch = "armv6"; break;
+ case 7: arch = "armv5"; break;
default: arch = NULL; break;
} break;

(I have also lipo -thin-ed the gdb before ldid-ing to make everything smooth.) After applying this patch, the ldid should recognize armv5 correctly. Now, save this portion of text as an XML file (e.g. gdb.xml):
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
<dict>
<key>com.apple.springboard.debugapplications</key>
<true/>
<key>get-task-allow</key>
<true/>
<key>task_for_pid-allow</key>
<true/>
<key>run-unsigned-code</key>
<true/>
</dict>
</plist>

and then run:
ldid -Sgdb.xml gdb

, and the gdb should now be completely usable on the iPhoneOS.

Thursday, September 17, 2009

iKeyEx 0.1-99j released, now works in 3.1

Download: http://code.google.com/p/networkpx/downloads/detail?name=hk.kennytm.iKeyEx3-0.1-99j.deb

This version is an emergency release to make it work in 3.1 (r497, r498). Along with it there are also these changes:
  1. Fixed a crash when uninstalling the Chinese Phrase Tables package (r491)
  2. Fixed a crash when phrases longer than 2 characters are processed (r499)
  3. Fixed a bug in characters sorting, that the sorted array is incorrect (r499).

Wednesday, September 16, 2009

QuickScroll 2.1a.

Download: http://code.google.com/p/networkpx/downloads/detail?name=hk.kennytm.quickscroll2-0.2-1a.deb.

New features:
  • QuickScroll can be disabled for each particular app, including SpringBoard.
  • Activate by scrolling. (This is off by default since you can't have smooth scrolling with QuickScroll. Oh you have 3GS? Forget I what say then...)
  • New icon design by Sagitt.
  • Localizations.


After this release all features will be frozen. That is, no new features will be accepted, no matter how ingenious it is. (Ya know, this thing gotta be pushed out some day). Only bug fix and new localizations will be allowed for 2.2 (the public version).

Tuesday, September 15, 2009

QuickScroll 2.1.

Download: http://code.google.com/p/networkpx/downloads/detail?name=hk.kennytm.quickscroll2-0.2-1.deb

Changes:
  • The scrollers should now be easier to grab and move around.
  • Duration now really defaults to 2 seconds on first install. Thanks fusen for noticing.
  • Scrollbars can be chosen to jump on spot instead of next page. Thanks Sagitt for suggestion.


(If there're no other bugs I'll submit this version to BigBoss.)

Monday, September 14, 2009

QuickScroll 2 released

With a 333% size increase*, QuickScroll 2 is released to improve the scrolling experience.


  • QuickScroll 2 now introduces scrollbars, which is the default.

  • Besides PDF files, scroll views that explicitly allowed for paging can also be targeted.

  • The old scroller is still accessible, but you can now move it around (and occupies much less space).

  • (To jump to a page, tap the 123 icon at the lower right corner in scroll bar mode, or tap the ← arrow button in scroller dialog mode.)

  • These configuration can be set in Settings.

  • As you can see, there are 2 more gestures you can choose. The two-finger tap should allow you activate QuickScroll in a table view easier.

  • I've eliminated the close button. The scrollers will disappear in 2 seconds of inactivity.

  • QuickScroll's scrollers are now actually a subview of the scrolling view, while in the 1st version it is an alert box. This change allows QuickScroll to be used in very high-level windows like those in SBSettings and GriP.

  • I don't know how to localize PreferenceLoader entries yet. So no localizations in this version, sorry.




*: 24 KiB → 104 KiB on disk.

Friday, September 11, 2009

Get UIView hierarchy, take 3.

The previous post about dumping UIView hierarchy is actually over-complicated. Actually all you need is one command (in gdb):

po [[[UIApplication sharedApplication] keyWindow] scriptingInfoWithChildren]


The result will be very verbose, make sure your terminal has enough scrollback.

Thursday, September 10, 2009

iKeyEx 0.1-99i released.

Download = here.

Changes:
  • Fixed issue 313. In an alt (numbers) plane, pressing the space key will go back to the main (alphabets) plane.
  • Typing the apostrophe (') in the main plane no longer auto-switch to the alt plane.
  • Fixed issue 312, and many other auto-shift related quirks.
  • .cin IME:
    • Number of candidates is limited to avoid near-infinite loop. 64.0 candidates should be enough for everyone.
    • Multi-radical continuation works again.
    • Fixed cases where blank candidates appear.
    • Candidate searching now operates in serial for reliability. You may experience some degrade in performance.
    • A progress indicator is added when the Patricia tree dump for the IME was first generated. This is essential for some huge IME like 輕鬆輸入法, which takes nearly 2 minutes for the first launch.


(Chinese Users: 倉頡輸入法及額外字頻表及詞庫亦更新至 0.2-1 版,這與 0.2-0 版內容上其實沒分別,只是製作 deb 時改用了 gnutar,從而避免因含非 ASCII 檔名而導致安裝失敗。若果你正在使用這些軟件,則不用更新。)

By the way, if you find any bugs, please report at Issues in the project page. If you leave a comment here or the wiki I can't guarantee I can dig and fix that.

Preemptive Warning: Comments not related to this content will be ignored.

Monday, September 7, 2009

Introducing Subjective-C, an objc_msgSend[_[st|fp]ret]? logger.

Time ago I logged calls to objc_msgSend to understand how to construct UIKBKeyboards. But that logger is known to cause problems due to asserting the arguments use less than 1024 bytes. I needed to log calls again for issue 312, but the old buggy behavior leads me to rewriting it more reliably.

The result is the dynamic library called Subjective-C. It has the following new features:
  • Stack-safe. No arguments will be lost due to this logger.
  • Call tree construction.
  • Filtering.

along with the old features:
  • Print and format all arguments, and the return value.


Note:
  • Due to licensing, only the ARM version is released, although the x86 version works perfectly.
  • If your product depends on Subjective-C (why?), please note that it is GPLv3.
  • (No, it won't help even if I BSD everything.)


Sample output




+[UIScroller _registerForNotifications]
+[NSString alloc] {
+[NSString allocWithZone:] (0x0)
}
+[NSBundle mainBundle] {
-[NSRecursiveLock lock] <0x1007540>
-[NSRecursiveLock unlock] <0x1007540>
} = <NSBundle 0x100db50>
-[NSBundle bundleIdentifier] <0x100db50> {
-[NSBundle infoDictionary] <0x100db50> {
-[NSBundle _cfBundle] <0x100db50> = 0x1009d60
} = <NSCFDictionary 0x100af10>
-[NSCFDictionary objectForKey:] <0x100af10> (@"CFBundleIdentifier") = @"com.yourcompany.Untitled4"
} = @"com.yourcompany.Untitled4"
-[NSPlaceholderString initWithFormat:] <0x100cf70> (@"%@.UIKit.migserver") {
-[NSPlaceholderString initWithFormat:locale:arguments:] <0x100cf70> (@"%@.UIKit.migserver", nil, "∞≠") {
-[NSCFString respondsToSelector:] <0x100adb0> (@selector(descriptionWithLocale:)) {
-[NSCFString class] <0x100adb0> = NSCFString
+[NSCFString resolveInstanceMethod:] (@selector(descriptionWithLocale:)) = NO
} = NO
-[NSCFString description] <0x100adb0> = /*self*/ @"com.yourcompany.Untitled4"
} = @"com.yourcompany.Untitled4.UIKit.migserver"
} = @"com.yourcompany.Untitled4.UIKit.migserver"


Wednesday, September 2, 2009

stmXX


static int rx_reserve[8];

...

__asm__(" mov r1, #1\n"
" mov r2, #2\n"
" mov r3, #3\n"
" ldr r0, (reserve)\n"
" mov r4, r0\n"
" ????? r0!, {r1-r3}\n"
" str r0, [r4, #16]\n"
" b after_data\n"
"reserve:\n"
" .long _rx_reserve+12\n"
"after_data:\n");

printf("%d %d %d [%d] %d %d %d;\ndelta = %d\n",
rx_reserve[0], rx_reserve[1], rx_reserve[2], rx_reserve[3], rx_reserve[4], rx_reserve[5], rx_reserve[6],
rx_reserve[7]-(int)(rx_reserve+3) );


?????Result
stmia0 0 0 [1] 2 3 0;
delta = 12
stmib0 0 0 [0] 1 2 3;
delta = 12
stmda0 1 2 [3] 0 0 0;
delta = -12
stmdb1 2 3 [0] 0 0 0;
delta = -12

Tuesday, September 1, 2009

iKeyEx & 5-Row QWERTY 0.1-99h are released

Downloads can be found in here as usual.

Changes from "g" are:

  • You can now long-press control keys (left, right, etc) to repeat actions.
  • ANSI and X11 apps for control keys are now correctly detected.
  • The config file is moved to ~/Library/Keyboard/iKeyEx::config.plist. This allows the config to be preserved even after firmware upgrade. (Permission problems will also be fixed during installation.)
  • PSBundle for layouts and IMEs. Normal users can find them in Settings → iKeyEx → Customize.
  • In the delete cache page, the total file size of the cache entry will be reported.
  • Candidate calculation in .cin IMEs now actually runs in background.
  • Associated phrases (aka Completion) can be disabled.
  • iKeyEx-KBMan now registers input modes correctly without causing crashes. Also it now purges layout cache correctly.


The "h" version of iKeyEx is considered a release candidate. I'll try to get it to BigBoss's beta repo if no major bug is found.

Many of the changes in "g" and "h" are to prepare for the 5 Row QWERTY layout. Of course, the major change for 5 Row QWERTY is it works on 3.0, but even compared with 0.1-9b, there are a few points to need to notice:
  1. You'll find that the Tab, Esc, Page Up keys etc become words instead of symbols. This is because, with the system fonts all the previous symbols cannot be rendered. For consistency I just change them all into words.
  2. The "Autocorrection" part of the old pref bundle is now handled by Mix & Match.
  3. Sometimes your customization won't take effect. Try to Delete cache if that happens.

There are no modifications other than these.

Sunday, August 30, 2009

iKeyEx 0.1-99g is released

Download.

Changelog:
  • “Text with traits” is now supported, that means your can add color, change font and text size for each key. However, you still cannot use key with image.
  • Native control keys support. (Left, right, home, page down, etc.)

Wednesday, August 26, 2009

Easier way to get UIView hierarchy.

Before I documented how you can obtain the UIView hierarchy in syslog. It uses custom function, but there is are 2 built-in way to get this.

The first, standard way is to send a GSEvent type #500 to the application, then the dump will be written to /tmp/UIDump in plist format. You can achieve the same by calling in gdb:

call (void)[[UIApplication sharedApplication] _dumpUIHierarchy:0]

When the dump is completed, a Darwin notification "com.apple.UIHierarchyDump.finished" will be posted.

(You can also take a screenshot with _dumpScreenContents:0 / GSEvent type #501, but the file is in JPEG and pressing Lock+Home isn't that hard...)

(Note: May fail for AppStore apps due to sandboxing.)

GSEvent Recording and Playback in 3.0

iPhoneOS has built-in API for application macro since 2.x. (Of course it was never documented.) (And the API was really changed in 3.0 to adopt for multiple recorders.)

For example, to record everything you've done during the for yourUIApplication:

recorder = [Recorder new];
[yourUIApplication _addRecorder:recorder];
[recorder release];

The command _addRecorder: adds the object to the application's event recorder array. You can remove your recorder at anytime with

[yourUIApplication _removeRecorder:recorder];


An event recorder must conform to the informal protocol

@protocol UIEventRecorder
-(void)recordApplicationEvent:(NSDictionary*)event;
@end

Here, "event" is a GSEvent converted to a plist using GSEventCreatePlistRepresentation(). You can add the event to an array and save that array for later reference, e.g.

@interface Recorder : NSObject { NSMutableArray* eventList; } @end
@implementation Recorder
-(id)init { if ((self = [super init])) eventList = [NSMutableArray new]; return self; }
-(void)save { [eventList writeToFile:@"events.plist" atomically:YES]; }
-(void)recordApplicationEvent:(NSDictionary*)event { [eventList addObject:event]; }
@end



Now say you want to play back the events you've previously collected. Just use this code:

NSArray* eventList = [NSArray arrayWithContentsOfFile:@"events.plist"];
float playbackRate = 1;
[app _playbackEvents:eventList atPlaybackRate:playbackRate messageWhenDone:target withSelector:@selector(done:)];

The higher the playback rate, the faster the system will run the events.

When the playback is finished, the "done:" selector will be called for "target". This selector must have a signature of

-(void)done:(NSDictionary*)detail;

the "detail" argument contains exactly 1 key, "UIApplicationEventRecordingDeliveryTimeUserInfoKey", which points to an array of the time the corresponding event happened.

Tuesday, August 25, 2009

Decompressing .zip files with iWorkImport.framework.

.zip files need to be supported in lots of places on the iPhoneOS. .ipa are zip files, .docx are zip files, .key are zip files. Unfortunately there is no centralized framework or library to handle these zip files. In fact, all Bom.framework, OfficeImport.framework and iWorkImport.framework have their own, private implementation to decompress a .zip file. Out of the three, iWorkImport.framework is the friendliest.

This example code shows how to open a .zip file and read the content:

http://pastebin.com/f16274c11

(Of course, if you write your new application, you should not unzip like this :) use something documented such as ziparchive.)

Monday, August 24, 2009

Trivia for Preference Bundles.

1. How to create that red delete button?


The red delete button in VPN is in fact very easy to implement. All you need to do is add the following code:


#import <UIKit/UIPreferencesDeleteTableCell.h>
@interface PSDeleteTableCell : UIPreferencesDeleteTableCell @end
@implementation PSDeleteTableCell
-(void)setValueChangedTarget:(id)target action:(SEL)action userInfo:(NSDictionary*)info {
[self setTarget:target];
[self setAction:action];
}
-(UILabel*)titleTextLabel {
UILabel* res = [super titleTextLabel];
res.textColor = [UIColor whiteColor];
return res;
}
@end


and then in the specifier plist, modify your button as:

...
{ cell = PSButtonCell;
action = nukeFromOrbit;
label = "Nuke from Orbit;
...
cellClass = PSDeleteTableCell;
},
...


The result is:



2. PSEditableListController


Normally list controllers inherit from the PSListController, but you can make a class inherit from PSEditableListController so that it becomes... editable! Actually, more like deletable. There will be an extra Edit/Done button on the top right hand corner, pressing it will reveal the deletion control. If you actually delete a cell, the corresponding specifier's deletionAction will be called.

3. A list of editing panes


There are several editing panes in Preferences.framework and .app. To use those panes, just use the specifier plist

{ cell = PSLinkCell;
detail = PSDetailController;
pane = PaneName;
... }


  • PSMultiValueEditingPane (Include just a PSSegmentCell, useless by itself.)

  • PSTextEditingPane (A pane containing a text field and a keyboard.)

  • RegulatoryPane (A static image showing the device is FCC approved and in other countries as well.)

  • LegalMessagePane

  • TimeZonePane (Time zone selector. The returned value doesn't contain just time zone, but also city location.)

  • RingtonePane (Note that the ringtone will be played when selected.)

Sunday, August 23, 2009

iKeyEx 0.1-99f Released, now supports .cin IME.

Download: here

Changelog: There were 3 versions in between, "d" was mainly to fix issue 1, "e" was an emergency release to fix a crashing bug on the preferences, and "f" fixes rest of the bugs and improves performance of characters tables.

    • Fixed issue 1. .cin input manager can be used natively with iKeyEx.
    • You can now the method to invoke the keyboard chooser, the disable it completely
    • Fixed a bug that causes crash when a layout.plist using text with traits is encountered. Thanks DB42 (of OpenHebrew) for reporting!
    • UI for cache removal.
    • Basic localization (en, es, zh_TW, zh_CN).

    • Fixed a bug that may cause preferences to crash. Thanks @mikitomo for reporting!
    • Loading characters table is now much faster (from O(n) to O(1)), that the second time you use a .cin input method will load instantly, instead of need to wait for 1 ~ 3 seconds (at a price of ~200 KiB disk space).
    • Name for layout.plist keyboard cache are now correctly generated. Thanks DB42 for reporting!
    • Keyboard list will be properly updated after Mix and match.
    • The counter in "Delete cache" will be properly updated after a cache entry is removed.
    • Candidate list computation won't lock up the application forever (at worst case) anymore.
    • Support for layout.plist on non-default keyboard type is fixed. Thanks DB42 for reporting!


Actually issue 1 was a major reason why the iKeyEx project exists, and now it is finally implemented. The .cin input method is mainly for use in table-based Chinese input method, but it can be used to implement that things too, e.g. the MultiTap method + Text prediction can be made on top of a .cin IME. The technical detail of .cin files and the technology around it can be found here.

The IME support is nowhere versatile. The .cin IME in iKeyEx so far only supports:
  1. Prefix searching (like autocompletion)
  2. Phrase completion

In the future it may also support:
  1. Key charges
  2. Dynamic dictionaries.

Wednesday, August 12, 2009

Embedding a preference bundle, in your app.

If you want to use Preferences.framework in your app, you can do it like this.

First, make a PSListController subclass as you would when creating a Preference Bundle. Then create a subclass of PSRootController, with code like this:
@interface MyRootController : PSRootController
@end
@implementation MyRootController
-(void)setupRootListForSize:(CGSize)size {
PSSpecifier* spec = [[PSSpecifier alloc] init];
spec.name = @"Anything";

MyListController* root = [[MyListController alloc] initForContentSize:size];
root.rootController = self;
[root viewWillBecomeVisible:spec];
[spec setTarget:root];
[spec release];
root.parentController = self;

[self pushController:root];
[root release];
}
@end

Finally, in your app's delegate, write these code:
-(void)applicationDidFinishLaunching:(UIApplication *)application {
window.frame = [UIScreen mainScreen].applicationFrame;
...
MyRootController* rootCtrler = [[MyRootController alloc] initWithTitle:@"Some Title" identifier:@"com.yourcompany.appName"];
[window addSubview:[rootCtrler contentView]];
}


Why do this? One major reason it that we can now debug the Pref Bundle in Simulator, and speed up development.

iKeyEx 0.1-99c and QuickScroll 0.1-12d released

iKeyEx 0.1-99c was released, changes were:
  1. Fixed a silly bug causing autocorrection not working for internal input modes.
  2. nlist nows checks for N_ARM_THUMB_DEF just for safety. Probably make it works for 3GS, probably not.
  3. Input modes won't suddenly "reset" now.


QuickScroll 0.1-12d (@r437) fixed a bug where you could scroll horizontally (and actually, vertically too) one pixel too far. Also, it now synchronizes when content size change (e.g. additional content of a web page is loaded, or orientation is changed).

QuickScroll 0.1-12c released (bug fixes)

QuickScroll 0.1-12c was released. The changes include:
  • Can scroll to the top in MobileNotes now.
  • Now the triple tap will iterate all touches, eliminating any possibility that a triple tap (that ought to be caught) is missed.
  • QuickScroll will be suppressed on non-scrollable views.
  • QuickScroll (PDF paging) will be suppressed on PDF files with 0 pages (usually those incomplete files).
  • Japanese localization.

(And the dylib size drained down from 20,000 bytes to 19,968 bytes :( )

0.1-12c was submitted to BigBoss, so it should appear in a few days. Those who can't wait can download from here.




Meanwhile I want to explain one decision. Why triple tap? My initial intension was three-finger touch, but I sometimes hold the device with one hand and the other occupied, so any multitouch ideas are ruled out. But how about, like, triple-tapping the home button? This won't work either, as it is possible that two web views appear on screen simultaneously. This excluded all solutions not using the screen, e.g. using the home/lock buttons, shaking the device, etc.




If you have installed iKeyEx 0.1-99b (make sure you're using 0.1-99b) and experienced Crash and not using 3GS please email me kennytm@gmail.com, preferably with a crash log (and syslog if possible).

Tuesday, August 11, 2009

QuickScroll 0.1-12b released, supports PDF paging and activating from anywhere

Download is here, as usual. The seventy people who have installed 0.1-12a should also upgrade for a correct offset calculation in MobileSafari.


Now QuickScroll becomes a 1.5-day project, so there are much more features introduced.

Changes:

  1. Activate QuickScroll from anywhere, like web pages, long text views, tables, MobileTerminal, SpringBoards, just anywhere you can scroll. (Blame MobileSafari for requiring me to introduce this.)

  2. Jump to any page in a PDF file.

  3. Fixed from 0.1-12: Rotating from portrait to landscape position no longer makes the "Close" button unreachable.

  4. Modified: The alert box is now smaller.

  5. Language support for English, Spanish, Italian (thanks Sagitt for a few translations) and Chinese (T+S).





This version should be stable enough and I think no more features are needed (besides more localizations). The very same package shall appear in Cydia repo soon if I receive no bug reports by tomorrow (14:00 at GMT+8).


P.S. The dylib is exactly 20,000 bytes.

Monday, August 10, 2009

QuickScroll 0.1-12 released

QuickScroll 0.1-12 is released. It's a quick (:p) project done within half a day.

QuickScroll lets you scroll through a Web page (including PDF files and Word documents) quickly. To use:
  1. In a long web page, triple tap on anywhere (hold one finger and triple tap the other to avoid resizing).
  2. A dialog will appear. Drag the green box to scroll around.


Sunday, August 9, 2009

iKeyEx 0.1-99b is released (3.0 only)

Hi girls and guys. 0.1-99f has been released. Maybe check the newest post first before commenting? ;p




iKeyEx 0.1-99b is released. This is a beta version, and the release version will use the version number "0.2".




Compared with the iKeyEx 2.x series, a lot of things are changed that may render an existing keyboard useless.

Firstly, text with traits are not supported yet, meaning keyboard that entirely relying on it such as 1Click@Thai (com.iclick.thai5rowkeyboard) will entirely unusable in this version.

Secondly, libiKeyEx.dylib is rewritten and uses a different API. That means existing keyboard more complex than a standard keyboard, including ℏClipboard and 5 Row QWERTY cannot run. If dependence is not a lot, however, transition to 3.x is pretty easy.

Thirdly, the input mode architecture is changed. Previously, an input mode linked to exactly one layout. It is decoupled on 0.1-99b. For example, I can have a 5-row QWERTY keyboard for English, for Japanese and for Chinese simultaneously. You can do it in the Mix & Match options in Settings → iKeyEx. But because a layout no longer completely defines an input mode, installing a keyboard may not be immediately usable.

Example 1: The Deutsch 5 Row Keyboard (com.ipuhelin.keyboards-5rowdeutsch) will be installed using English (US) as input manager. You can fix it by choosing Settings → iKeyEx → Mix and Match → 5RowDeutsch → Input manager → German (Germany).

Example 2: The Dvorak 5Row Keyboard (hk.alim.dvorak5row) was installed without adding itself to the list of input modes. In 2.x you'd add it from International Keyboards, but this is more complicated on 3.x due to the decoupling. The procedure can be summarized into this pic:


In words,
  1. Go to Settings → iKeyEx
  2. Select "Mix and Match",
  3. then "Create", to create a new input mode.
  4. Now, select "Layout",
  5. and change it to "5-Row DVORAK" at the top.
  6. After that, select "Name"
  7. and give it a name. It must not be empty.
  8. Finally, go back to the iKeyEx screen and tap "Keyboard"
  9. You should be able to see the new input mode. Tap on (+) to add it.


I haven't put in any localization yet. They will appear in the next version.

Friday, August 7, 2009

The 8th property list object

We've been long told that there're only 7 types of property list objects: CFString, CFNumber, CFBoolean, CFDate, CFData, CFArray, and CFDictionary. These are the only types that can be encoded into a property list without conversion. At least it's what on the surface. There's in fact an eighth type of property list object, called _CFKeyedArchiverUID, to support the NSKeyed[Un]Archiver.

An archived data is actually a binary property list. The encoded objects are laid out linearly, and each object has a UID numbered serially. Objects can be linked to each other, forming an "Object Graph". The links are encoded as _CFKeyedArchiverUIDs.

A _CFKeyedArchiverUID is essentially a 32-bit integer. Why isn't a CFNumber be used? Because it would then be impossible to distinguish between a regular number and a link.

Becuase _CFKeyedArchiverUID is not publicly documented (you can find its trace in the CF source code), it is a perfect type to conceal these supposed-to-be internal information.

But it introduce problems when handling with plist files that have a _CFKeyedArchiverUID. Firstly, Apple's Property List Editor does not recognize them. And even worse, these UIDs are stripped when saved. You can try this: open any .nib file, without any modification save it as another file. You'll find that the new file becomes smaller.

Also, _CFKeyedArchiverUID does not have a specialized -description method. When you NSLog a dictionary containing with object, a <NSCFType: 0xpointer> will be displayed (although CFShow does show the content).

In XML format, _CFKeyedArchiverUID will be output as
<dict> <key>CF$UID</key> <integer>123</integer> </dict>

This means any dictionaries containing a single entry with key CF$UID and an integer value will be converted to a _CFKeyedArchiverUID.

Wednesday, August 5, 2009

LC_DYLD_INFO_ONLY demystified

One day after I found no useful info on LC_DYLD_INFO_ONLY, there's already a paste showing the answer (this is Google cache, the original one is already invalidated). I have copied it to pastie in case the Google cache is removed. From the comment we clearly see the intent, and hints to how to decode this command.

Using CPRegularExpression (not!)

AppSupport.framework contains a class called CPRegularExpression, which performs regular expression matching. Here is an interface and some sample code.

However, I strongly recommend against using this class. Why? Because the backend of CPRegularExpression is in fact regexec. regexec is underpowered and not fast at all (for commonly encountered regexes, at least). Combined with the dynamic nature of Objective-C it means very slow (you can get an IMP to speed this up though). Instead, you should use the more powerful and faster PCRE (it's of course hard to use, but there're plenty of wrappers).

class-dump-z 0.1-11s released.

class-dump-z 0.1-11s is released. (When iKeyEx 3.0 is released I'll upgrade the versioning to 0.2. Let's hope I won't exhaust all alphabets first.)

Change log:
  • Won't crash on 3.1 binaries now, but external class info is absent. For example, for SpringBoard, SBAppWindow : UIView will be shown as SBAppWindow : XXUnknownSuperclass.
  • Private ivar detection. From whether the ivar symbol is exported we can guess if that ivar is @private/@package or @protected/@public. class-dump-z 0.1-11s now recognizes this piece of information.
  • -h super now works even the method includes non-id/void/SEL types.
  • Argument reordering now works on Linux (again).

Technical detail on why class-dump-z 0.1-11r crash with 3.1 SpringBoard, and why the external class info cannot be extracted in 0.1-11s.

If you use class-dump-z 0.1-11r on the 3.1 SpringBoard, you'll get an exception saying
terminate called after throwing an instance of 'std::logic_error'
what(): basic_string::_S_construct NULL not valid
Abort trap

This is because a code similar to this is called:
std::string s = NULL;

Debugging reveals such an error occurs at MachO_File_ObjC::get_superclass_name. What happened is that, the definition of SBAppWindow class of 3.1 SpringBoard resolves to:
 class_t OBJC_CLASS_$_SBAppWindow = {
isa: OBJC_METACLASS_$_SBAppWindow,
superclass: NULL,
cache: NULL,
vtable: NULL,
data: (pointer to Data)
};

The superclass pointer is NULL. Which is fine, as such already happens before 3.1. But how can the system know the superclass if the pointer is NULL? Before 3.1, this location is in fact referenced by an entry in the relocation table. At runtime, the dynamic linker will replace data referenced in the relocation table by the real address.

The problem is the 3.1 SpringBoard has no relocation table! We can check:
Load command 6
cmd LC_DYSYMTAB
cmdsize 80
ilocalsym 0
nlocalsym 1
iextdefsym 1
nextdefsym 1
iundefsym 2
nundefsym 1330
tocoff 0
ntoc 0
modtaboff 0
nmodtab 0
extrefsymoff 0
nextrefsyms 0
indirectsymoff 1138584
nindirectsyms 1943
extreloff 0
nextrel 0
locreloff 0
nlocrel 0

Because of this, class-dump-z 0.1-11r cannot resolve what that address will be, and returns NULL. The code afterward see this NULL unexpected and result in exception.

0.1-11s now checks for this failure, but it's just a bad workaround. Because every externally referred class, like NSObject, UIView, etc. will become XXUnknownSuperclass.

Now, if we don't know the superclass, how can the iPhoneOS be? There, I introduce you the Load Command 0x80000022:
Load command 4
cmd ?(0x80000022) Unknown load command
cmdsize 48
00000000 00000000 00106000 00006c6c 00000000 00000000 0010cc6c 00005324
00111f90 00000198

It is run without the 3.1 SDK. Because this is an unknown command, nm totally fails on the 3.1 SpringBoard.
nm: for architecture armv6 object: SpringBoard malformed object (unknown load command 4)

Googling suggests it appears only on 3.1+ and Snow Leopard+. That means the ABI will be changed on SL? And relocation table won't be used? Maybe. With a 3.1 SDK, we can see that the load command is in fact called LC_DYLD_INFO_ONLY. The content is

struct dyld_info_only_32 {
uint32_t rebase_off;
uint32_t rebase_size;
uint32_t bind_off; // 0x106000
uint32_t bind_size; // 0x6c6c
uint32_t weak_bind_off;
uint32_t weak_bind_size;
uint32_t lazy_bind_off; // 0x10cc6c
uint32_t lazy_bind_size; // 0x5324
uint32_t export_off; // 0x111f90
uint32_t export_size; // 0x198
}

This load command is not documented on Apple's site either, and google yields no useful result at all. But we can find the string _OBJC_CLASS_$_UIWindow at 0x106ea0 inside the so called "bind" table, so definitely something important can be found here.

Monday, August 3, 2009

Partial support for iKeyEx layout.plist on 3.0

The layout.plist to UIKBKeyboard conversion function is done. As promised, an executable that converts layout.plist to .keyboard files can be downloaded from here.

This program converts a layout.plist into 8 .keyboard files which can be loaded by UIKit natively. For example, if you want to install the Colemak keyboard,
  1. ssh into your device
  2. Download layout-plist-to-keyboards by typing:
    wget http://networkpx.googlecode.com/files/layout-plist-to-keyboards
  3. Change that file to an executable:
    chmod a+x layout-plist-to-keyboards
  4. Download the layout.plist for Colemak:
    wget http://networkpx.googlecode.com/svn/trunk/hk.kennytm.Colemak/deb/Library/iKeyEx/Keyboards/Colemak.keyboard/layout.plist
  5. Perform the conversion:
    ./layout-plist-to-keyboards layout.plist
  6. Check that there are 8 .keyboard files in the directory.
    ls
  7. Move all these keyboards to UIKit.framework (requires root permission):
    mv *.keyboard /System/Library/Frameworks/UIKit.framework/

Now all QWERTY keyboards are replaced by Colemak.

If you don't want to replace the QWERTY keyboard, you can rename them to something else. Say, you'll never use the Thai keyboard, then name them iPhone-Portrait-Thai.keyboard, etc. Now you can activate the Thai keyboard to use the custom one.

This solution is not a replacement of a full iKeyEx. For example, 5-Row QWERTY won't work completely because the custom-code injecting part is not done yet (but Punctuation Mod should work). hClipboard won't work at all since it's no a layout.plist. Other caveats are listed here. Please don't host Cydia packages publicly that uses this solution, because every keyboard will become mutually exclusive now :) Only for personal use.

Saturday, August 1, 2009

class-dump-z 0.1-11r released, supports Windows

A minor revision of class-dump-z was released. The new version:
  • Adds a Windows x86 version.
  • Arguments can be placed arbitrarily (e.g. class-dump-z UIKit -a -A now works).
Updated on Aug 2:
  • If you have installed the iPhone SDK, the -y switch is no longer necessary when using -h super.
  • Also, using -h super won't crash now.

GriP 0.1-11r Released to fix Crashing with Exchange mail accounts

As titled. If you are experience crashes when new mails arrive to an Exchange mail account, please upgrade to GriP 0.1-11r. Detail can be found in issue 242.

Friday, July 31, 2009

GriP, GriPGRIP & class-dump-z 0.1-11q Released

Starting from this version, Memory Watcher will not be included in GriP. Instead, it will be moved to a new package, "GriP Really Impressive Pack" (GriPGRIP). The distinction is that, GriP shall only contains the most needed extensions, i.e.
  • Mail
  • Push notification
  • SMS (by xshad0w, not included in 0.1-11q yet),
the 2 themes, Default and Double Height Status Bar (also by xshad0w, also not included yet), and 3 modal table themes, Default, HUD and Translucent Black (I may remove the last one too). On the other hand, GriPGRIP is a collection of all other stuff that will utilize GriP, like calendar events, remote Growl notifications, themes, etc. (The distinction is because GriP is growing to 1 MiB pretty soon. I want to keep the size down.)




Anyway, 0.1-11q is mainly an issue-fixing release, that include:
  • Issue 223. You can configure some GriP messages to wake the device up.
  • Issue 176. An new option so that GriP message can be expanded by default.
  • Issue 209. You've Got Mail will show the user name of the mail owner, instead of the address.
  • Issue 168. All apps can be selected shown in Game Mode. The UI is improved too :)
  • Issue 172. Multiple push notifications from the same app will be coalesced.
  • Suspension behavior can be updated properly.


If you have GriP 0.1-11p, you don't need GriPGRIP 0.1-11q, because there's nothing new.




And class-dump-z. There are 4 new features in this release:
  • The -N flag, which allows you to disable struct name prettifying (__CFArray* → CFArrayRef).
  • Optional properties. Such a thing does not exist directly, but can be inferred when its getter and setter are optional. (See the UITextTraits protocol for example).
  • The -h proto flag, which will hide all methods that's just adopting a protocol.
  • The -h super flag, which will hide all inherited methods.

Note that if you use the -h super flag directly on the Mac, it is almost certain that class-dump-z will crash. This is because to get the superclass info class-dump-z must open some framework bundles, and by default it will search in /System/Library/..., which certainly does not contain anything iPhoneOS-related. You have to provide the -y flag to specify the sysroot as well. For those who have installed SDK, you need to add

-y /Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS3.0.sdk

Thursday, July 30, 2009

Text input on 3.0, Part 4 — UIKBKeylistReference

  • When I was preparing this whole stuff many wrong directions were taken and generates quite a number of utilities that could be useful later. Who knows? Head to http://code.google.com/p/networkpx/source/browse/etc if you are interested.
  • You will need UIKB*.h to compile my examples. The headers can be found in my other project page at github. However, besides ActorKit no header there is actually complete (yet).





Hopefully it's the last of the series. I'm now making a convert from layout.plist to .keyboard files. This is a major foundation for backward-compatibility with previous keyboards, and also allows you to use custom keyboards on 3.0 without iKeyEx (but, without all the benefits like unlimited numbers of keyboards). The basic idea is described in Part 1.

Anyway...

Unlike the old UIKeyboardLayoutRoman, the new UIKeyboardLayoutStar is "scalable", that means this keyboard will still look sharp even if used on a 10" tablet PC. This is because the whole UIKeyboardLayoutStar is drawn at run time with Rounded rectangles and Gradients and Shadows and stuff. It's vector graphics. (In constrast, UIKeyboardLayoutRoman is precomposed into a PNG image.)

But even the layout has the potential to be scalable, all keyboards I've created before (using Star) is not, because I haven't told it what to scale. It's like an iPhone app, most of them can be easily presented in landscape mode, but if the programmer doesn't implement the -shouldAutorotateToInterfaceOrientation: method the app will always stuck in portrait mode.

As I've repeated many times, keyboard construction occupies 70% mass of UIKit, and that's roughly 8 MiB of code. There are 148 keyboards defined in UIKit so far, so each keyboard will be defined by 55 KiB of code and data. And unfortunately, most of these are code. Now, ARM's register-relative addressing mode allows a maximum span of 11 bits, i.e. 8 KiB, but there's 55 KiB of code! That means each single function must be chopped into chunks by the compiler. To the analyzing decompiler (ravel-arm), it is a difficult situation, because an unconditional branch at the end may mean a tail-function-call. The data after may be interpreted as code, and ruins all stored computation in between. This is happening in the keyboard-defining functions, so by static analyzing the code I can only get to how Apple defines keys up to the Capital Letter U (that's Q, W, E, R, T, Y, U), and then a branch across some mis-codified data, and all selector and class info are lost.

So? Initially I dumped all 148 keyboards and analyzed the resulting archive, but this doesn't tell us the implementation detail. Eventually I hooked objc_msgSend to give what's being called (since I knew only Obj-C functions are called and no structs are returned, I've ignored all other messaging variants).

The result is over 9000 bytes and I can't pastie it. But I can pastie part of the decompiled result. The UIKBKeylistReference part is what I was missing. Now let's plug in the keyboard, and we get... a dangling Q as we've expected.

But if we resize the keyboard from 320x216 to 240x216? Yes, the key is correctly scaled down:

And removing the references even make the dimensions wrong, so the scaling is really the reference in effect.

(When the reference is defined, the original geometry of the keys will be overridden).
(Also note that this keyboard cannot be scaled vertically, because the vertical measures of the rows are absolute values (pixels).)

One puzzling property of references is the "flag". Yes we know it must be bitfield of some sort, but what? If we decompile the class UIKBKeylistReference we get:
  • 1 = isKeysetReference
  • 2 = isKeylistReference
  • 4 = isKeysReference
  • 8 = isNamedKeyReference
  • 0x10 = isKeyIndexReference
  • 0x20 = isKeyIndexRangeReference
  • 0x40 = isGeometryReference
  • 0x80 = isAttributesReference

Apparently it refers to while the name elements interpreted.

Why we care about scaling? One, it allows us to define landscape and portrait keyboards with the same content (the keys), and to switch between the two we just need to change the outermost dimension, and the rest will be seamlessly changed. And two, who said the keyboard size must be fixed at 320x216 / 480x162? What if there is really an Apple tablet and uses the iPhoneOS? Or there's an iPhone mini? The resolution can't be the same, so the keyboard size must be altered as well. On 2.x we're forced to hard-code these 4 numbers because UIKeyboardLayoutRoman expects us to do so. Now having the better solution with UIKeyboardLayoutStar, I'd rather spend more time to take advantage of it and make iKeyEx more robust in the future.

Monday, July 27, 2009

Multiple Row Selection with UITableView — The Easy Way

Cocoa with Love introduced the hard way to implement multiple row selection for 2.x firmware. On 3.x, there is a much easier way to do the same, if you dare you embrace undocumented methods.

Multi-selection is regarded as one of the editing style. Therefore, to make a cell multi-selectable, implement this in your UITableViewDelegate:
-(UITableViewCellEditingStyle)tableView:(UITableView*)tableView editingStyleForRowAtIndexPath:(NSIndexPath*)indexPath {
...
return 3;
}

The "3" here means multiselection. The result is like this:


To get the selected rows, call the -indexPathsForSelectedRows method on the table view.
NSArray* selectedRows = [tableView indexPathsForSelectedRows];


If you dislike the red check mark, you can use the undocumented multiselectCheckmarkColor property to change it. Unfortunately, it has to be applied on the whole table.
tableView.multiselectCheckmarkColor = [UIColor blueColor];

The light blue background color cannot be changed unless you subclass or categorize UITableViewCell and override the -_multiselectBackgroundColor method, like this:
-(UIColor*)_multiselectBackgroundColor { return [UIColor yellowColor]; }

Saturday, July 18, 2009

class-dump-z & GriP 0.1-11p released

Downloads available in http://code.google.com/p/networkpx/downloads/list as usual.

What's new in GriP: Again, another attempt to fix issue 129.

What's new in class-dump-z:
  • Doesn't crash with WebKit.framework anymore.
    • The offending struct is XXStruct_GIci6C. Due to some strange thing in the GCC that compiles WebKit, the type of function pointer is encoded into "^" (pointer to !#$^*@#NO_CARRIER) instead of "^?" (pointer to some unknown stuff). The original class-dump won't handle this stuff either, and spit out a huge error string.
  • Doesn't crash with Symbolication.framework anymore.
    • The offending class is VMUCallTreeNode, which contains a union to a pointer to a static-typed objective-C class, which will cause a segfault in 0.1-11o. This was just an error in class-dump-z.
  • Forward declaration of some structs were missing if it is nested. Not anymore.
  • Fixed issue 187. It was because class-dump-z missed the LC_LOAD_WEAK_DYLIB commands.
  • Fixed issue 198.
  • Linux version: PCRE is static-linked. No need to search for the right version of libpcre.so anymore.

Thursday, July 9, 2009

Analyzing Objective-C's for-in loop (fast enumeration)

Objective-C 2.0 supports for-in loop like this:

for (XXSomeClass* obj in someArray) {
[obj doSomething];
}


it's nice to the programmer, but painful for the disassemblers because the simple loop above is translated into this bulky ASM:

            ldr               r1,[pc,#0xe8]
mov r3,#0x0
str r3,[sp,#0x44] // state
str r3,[sp,#0x48] // itemsPtr
str r3,[sp,#0x4c] // mutationsPtr
str r3,[sp,#0x50] // extra[0]
str r3,[sp,#0x54] // extra[1]
str r3,[sp,#0x58] // extra[2]
str r3,[sp,#0x5c] // extra[3]
str r3,[sp,#0x60] // extra[4]
ldr sl,[pc,r1]
add r3,r3,#0x10
str r3,[sp]
mov r1,sl
add r2,sp,#0x44
add r3,sp,#0x4
bl objc_msgSend (stub) ; [someArray countByEnumeratingWithState: objects:count:]
subs r5,r0,#0x0
beq loc_000100
ldr r3,[sp,#0x4c]
ldr r3,[r3]
mov r6,r3
loc_000094: mov r4,#0x0
b loc_0000a4
loc_00009c: ldr r3,[sp,#0x4c]
ldr r3,[r3]
loc_0000a4: cmp r6,r3
beq loc_0000b4
mov r0,r8
bl objc_enumerationMutation (stub)
loc_0000b4: nop
nop
nop
nop
nop
add r4,r4,#0x1
cmp r5,r4
bhi loc_00009c
mov r3,#0x10
str r3,[sp]
mov r0,r8
mov r1,sl ; "countByEnumeratingWithState:objects:count:"
add r2,sp,#0x44
add r3,sp,#0x4
bl objc_msgSend (stub) ; [? ?]
subs r5,r0,#0x0
ldrne r3,[sp,#0x4c]
ldrne r3,[r3]
bne loc_000094
loc_000100: ...


The disassembled code is
NSFastEnumerationState enumState;
enumState.state = 0;
enumState.itemsPtr = NULL;
enumState.mutationsPtr = 0;
enumState.extra[0] = 0;
enumState.extra[1] = 0;
enumState.extra[2] = 0;
enumState.extra[3] = 0;
enumState.extra[4] = 0;
NSUInteger count = 16;
id buffer[10];
do {
NSUInteger copiedItemsCount = [someArray countByEnumeratingWithState:&enumState objects:buffer count:count];
for (unsigned long i = 0; i < copiedItemsCount; ++ i) {
if (*(enumState.mutationsPtr) != 0)
objc_enumerationMutation(someArray);
[enumState.itemsPtr[i] doSomething];
}
} while(copiedItemsCount != 0);


What does the state and extra do? Up to the implementor. (And objc_enumerationMutation simply kills the program and reports that a mutation happened.)

Wednesday, July 8, 2009

Text input on 3.0, Part 3 -- Hooking

I think the best solution for now is put a hook at -[UIKeyboardLayoutStar setKeyboardName:appearance:]. If we see a custom name, we could put our own keyboard into the cache dictionary.

Who called -[UIKeyboardLayoutStar setKeyboardName:appearance:]? From the backtrace,
#1  0x30b16dae in -[UIKeyboardLayoutStar showKeyboardType:appearance:orientation:] ()
#2 0x30a1da78 in -[UIKeyboardImpl updateLayout] ()
#3 0x30a1a175 in -[UIKeyboardImpl setDelegate:force:] ()
#4 0x30a1815a in -[UIKeyboardImpl setDelegate:] ()

and the calling code of -[UIKeyboardLayoutStar showKeyboardType:appearance:orientation:] is
[self setKeyboardName:UIKeyboardGetKBStarKeyboardName(
UIKeyboardGetCurrentInputMode(),
orientation, keyboardType)
appearance:appearance];

and UIKeyboardGetKBStarKeyboardName is hard-coded to generate the expected keyboard name. But before we start we must ensure the input mode can be handled by UIKit! In 3.0 there's a function UIKeyboardGetSupportedInputModes() which returns the 46 hard-coded input mode names. Well, we could of course use MSHookFunction to replace it, but I'd like to see if it's possible to do it with Objective-C only, because MSHookFunction is not available on x86. And actually there is a trick — we see that UIKeyboardGetSupportedInputModes() returns a shared object, which is an NSMutableArray*. What does this mean? Well, we can call this function once on initialization, modify it, and from that point on UIKeyboardGetSupportedInputModes() will record our change.

Then we need to trick UIKit into thinking our keyboard uses UIKeyboardLayoutStar. This information is extracted in UIKeyboardInputModeUsesKBStar(), which is again hard-coded. However, this function uses an NSDictionary* which cannot be accessed outside. So we can't test on simulator? Not really, we could actually hook -[NSDictionary initWithObjectsAndKeys:] instead, and swap it back to the original method when done.

There are a few other hard-coded dictionary in UIKeyboardInputManagerClassForInputMode(), UIKeyboardLayoutDefaultTypeForInputModeIsASCIICapable(), UIKeyboardGetKBStarKeyboardName(), etc. After all these are replaced we can get a totally empty keyboard without error — a good start.

Now we can insert the actual hook to -setKeyboardName:appearance: and set the keyboard. This part is not difficult because there's are reference implementations, like that disassembly of getKeyboardiPhonePortraitQWERTY() and dump of various keyboard files.

Monday, July 6, 2009

Text input on 3.0, Part 2.

In the last part, we found that we may be able to use the .keyboard format via GetKeyboardDataFromBundle(). This function is only called from -[UIKeyboardLayoutStar setKeyboardName:appearance:], and is not exported, so it seems .keyboard really only contains the keyboard geometry.

To see if it really works, let's save an internal keyboard into a file:

[NSKeyedArchiver archiveRootObject:UIKBGetKeyboardByName(@"iPhone-Portrait-Arabic") toFile:@"/tmp/iPhone-Portrait-Arabic.keyboard"]

unfortunately, UIKBGetKeyboardByName is not an exported symbol, so we have to use nlist or lookup_function_pointers. Now, rename this file to e.g. iPhone-Portrait-QWERTY.keyboard (the English keybaord) and place it to UIKit.framework — and, indeed, the English keyboard becomes Arabic!

But how to create a UIKBKeyboard? A UIKBKeyboard has 3 major components: name (NSString*), visualStyle (NSString*) and keyplanes (NSArray*). The name is just the name you'd expect (iPhone-Portrait-Arabic), while the visualStyle must be one of @"iPhone-Standard" or @"iPhone-Alert". These are easy to construct. The meat are all in the keyplanes variable. The keyplanes is an array of UIKBKeyplane*. Difference keyplanes are switched between using the shift and 123/ABC keys. Again, each keyplane has a name (NSString*, e.g. @"Capital-Letters"); keylayouts, an array of UIKBKeylayout*; attributes, a UIKBAttributeList* and finally supported-types, an array of NSString*, etc., etc...

The content is summarized into http://code.google.com/p/networkpx/wiki/keyboard_file_spec. With the format analyzed, we can try to create our own keyboard using this new format.

Text input on 3.0, Part 1.

2 little notes:
  1. GriP 0.1-11o has been released to fix issue 129, and that's the only change.
  2. class-dump-z 0.1-11o has been released for Mac, iPhone and Linux. See this page for a comparison of other class-dumps.




The rest of this text is written at the same time I'm doing the reverse engineering. You may feel confused, because that's how researching goes.


The text input framework is greatly revamped in 3.0. The new UIKit, which is 5 times bigger than 2.0, has 70% of weight taken up by keyboard layouts. And the nontrivial letter-based input managers, once part of UIKit, is moved into its private framework, TextInput.

What was changed? As the first try, let's view the view hierarchy, although this time we can do it in compile time. From the class-dump we know the old UIKeyboard class is still there, so let's run the statement
UILogViewHierarchy( [UIKeyboard activeKeyboard] );
when the keyboard is present.

So we got this with the English keyboard:

<UIKeyboard: 0xd47980; frame = (0 264; 320 216); opaque = NO; layer = <CALayer: 0xd47d00>> ({{0, 264}, {320, 216}}, (null), #0, 3)
..<UIKeyboardImpl: 0xd3da20; frame = (0 0; 320 216); opaque = NO; layer = <CALayer: 0xd37b40>> ({{0, 0}, {320, 216}}, (null), #0, 3)
....<UIKeyboardLayoutStar: 0xd48650; frame = (0 0; 320 216); layer = <CALayer: 0xd4ba40>> ({{0, 0}, {320, 216}}, (null), #0, 3)
......<UIKBKeyplaneView: 0xd59250; frame = (0 0; 320 216); userInteractionEnabled = NO; layer = <CALayer: 0xd59300>> ({{0, 0}, {320, 216}}, (null), #0, 3)
........<UIKBKeyView: 0xd595e0; frame = (1 119; 40 42); opaque = NO; userInteractionEnabled = NO; layer = <CALayer: 0xd596b0>> ({{1, 119}, {40, 42}}, (null), #0, 4)
........<UIKBKeyView: 0xd59af0; frame = (279 119; 40 42); opaque = NO; userInteractionEnabled = NO; layer = <CALayer: 0xd59b60>> ({{279, 119}, {40, 42}}, (null), #0, 4)
........<UIKBKeyView: 0xd59d10; frame = (1 173; 38 42); opaque = NO; userInteractionEnabled = NO; layer = <CALayer: 0xd59d50>> ({{1, 173}, {38, 42}}, (null), #0, 4)
........<UIKBKeyView: 0xd59e20; frame = (41 173; 38 42); opaque = NO; userInteractionEnabled = NO; layer = <CALayer: 0xd59e60>> ({{41, 173}, {38, 42}}, (null), #0, 4)
........<UIKBKeyView: 0xd4dca0; frame = (81 173; 158 42); opaque = NO; userInteractionEnabled = NO; layer = <CALayer: 0xd4dab0>> ({{81, 173}, {158, 42}}, (null), #0, 4)
........<UIKBKeyView: 0xd5bd10; frame = (241 173; 78 42); opaque = NO; userInteractionEnabled = NO; layer = <CALayer: 0xd5bd50>> ({{241, 173}, {78, 42}}, (null), #0, 4)


In fact, all other keyboards — except the handwriting ones, and emoji also — now uses UIKeyboardLayoutStar to manager the layout. (The old UIKeyboardLayoutRoman is still there.)

The 6 UIKBKeyView are the special keys, as shown here:


The class dump of UIKeyboardLayoutStar shows some interesting members, e.g. m_keyboardName, m_keyplaneName, the list of dictionaries, etc. Take the Arabic keyboard as example.

  • m_keyboardName = @"iPhone-Portrait-Arabic"
  • m_keyplaneName = @"Letters"
  • m_states is a dictionary of 35 entries, with keys as UIKBKey to values as NSNumber (integers).
  • m_keyboard is the keyboard (UIKBKeyboard), which contains a lot of geometry info.


If we can replace UIKBKeyboard, then we can make our own layout. Where is that UIKBKeyboard set? Looking at the disassembly of UIKit (which is kinda painful now due to its huge size), we see the relevant part is at -[UIKeyboardLayoutStar setKeyboardName:appearance:]:

NSString* UIKeyboardGetCurrentInputMode();
NSBundle* UIKeyboardBundleForInputMode(NSString* mode);
NSData* GetKeyboardDataFromBundle(NSString* name, NSBundle* kbbundle);
NSBundle* _UIKitBundle();
UIKBKeyboard* UIKBGetKeyboardByName(NSString* name);

@implementation UIKeyboardLayoutStar
-(void)setKeyboardName:(NSString*)name appearance:(UIKeyboardAppearance)appr {
UIKBKeyboard* keyboard = [m_keyboards objectForKey:name];
if (keyboard == nil) {
NSData* keyboardData = GetKeyboardDataFromBundle(name, UIKeyboardBundleForInputMode(UIKeyboardGetCurrentInputMode()));
if (keyboardData == nil)
keyboardData = GetKeyboardDataFromBundle(name, _UIKitBundle());
if (keyboardData != nil) {
NSKeyedUnarchiver* keyboardArchive = [[NSKeyedUnarchiver alloc] initForReadingWithData:keyboardData];
keyboard = [keyboardArchive decodeObjectForKey:@"keyboard"];
[keyboardArchive finishDecoding];
[keyboardArchive release];
} else
keyboard = UIKBGetKeyboardByName(name);
}

if (keyboard == nil)
return;

// the rest are not interesting at the moment.
}
@end


So they defined 3 ways to fetch the UIKBKeyboard, (1) GetKeyboardDataFromBundle from the keyboard bundle (/System/Library/TextInput/TextInput_xx.bundle/), (2) GetKeyboardDataFromBundle from the UIKit bundle, and (3) UIKBGetKeyboardByName.

What does GetKeyboardDataFromBundle do? Basically,
GetKeyboardDataFromBundle (name, bundle) {
Go to the bundle's resource path;
Open ".keyboard";
Return the content of this file as NSData*.
}


But there isn't a single .keyboard file in the TextInput bundles! How about in UIKit.bundle? No, not even one. So the only path taken would be by UIKBGetKeyboardByName. And what does it do? Search from a function table with that name, and call that function. This probably explain the 70% mass of UIKit — these are functions to define the keyboards. Why they don't use the .keyboard files is a mystery, but from this it seems we can exploit the format to let iKeyEx run on it.

Wednesday, June 24, 2009

GriP 0.1-11n Released

GriP 0.1-11n (r344) is released and can be downloaded from http://code.google.com/p/networkpx/downloads/detail?name=hk.kennytm.grip-0.1-11n.deb. This version will be the last revision with Memory Watcher bundled. Starting from next revision, Memory Watcher will be moved to another package.

GriP 0.1-11n features following changes:
  • (r327) GriP will use Preference Loader to inject the preferences. You'll have to install PreferenceLoader first.
  • (r327) GriP Modal Tables can now be themed.
  • (r331) All recent GriP messages will be logged.
  • (r332) The detail disclosure thing (▼) is available in You've Got Mail again.
  • (r333) Game mode now works in 3.0
  • (r334) Dismissing the modal table by home button works correctly in 3.0.
  • (r340) Added Polish localization.
  • (r343) 3.0 Push notification plug-in.
  • (As usual) Other bug fixes.


Note that if you've downloaded the r341 version that I've uploaded by mistake this morning, you'll experience a memory leak. Please upgrade immediately.

Tuesday, June 23, 2009

Sending push notification locally.

So far I haven't found a reliable push notification app yet to test GriP Push Notification (QuickPigeon is the most reliable one I've ever tried, but it held up 2 trial mails quite a long time).

So what about faking push notifications? After a push notification is just a TCP packet. The first thing I do is to set a breakpoint on the most suspicious method -- -[SBRemoteNotificationServer connection:didReceiveMessageForTopic:userInfo:] (0x9ffa5). And indeed, when a push notification comes, the break point is hit (multiple times).

I used the breakpoint command
call (void)CFShow($r2)
call (void)CFShow($r3)
call (void)CFShow(*$sp)
c

to record the arguments. And not surprisingly, the userInfo is an NSDictionary of the payload, like
{
aps = {
sound = "hello.aif";
alert = "Hello world!";
};
};

The Apple's documentation on this is more in detail. The "topic" parameter is the bundle ID of the app to receive the notification, and connection is an APSConnection object.

Given these results, we can craft our notification packet with a Mobile Substrate extension.

Right now, you can download FakePushNotification.zip and test it out. To install:
  1. Put the .dylib and the .plist to /Library/MobileSubstrate/DynamicLibraries
  2. Put the executable (FakePushNotification) to /usr/bin and chmod a+x it.
  3. Respring
  4. In command line, type e.g.:
    FakePushNotification com.yourcompany.pushEnabledApp -
    aps={
    alert={
    body = "Hello world!";
    action-loc-key = "Welcome!";
    };
    };
    ^D

    The "payload" must be in plist format, not JSON format.

Note: the program is written to demonstrate how it can be done. It is not bug free. In particular, sending a string that cannot be interpreted as a plist will cause your device crash and go into safe mode. Use with caution.

Monday, June 22, 2009

openURL for 3.0 (and 2.x too, probably)

openURL is part of Erica Utilities. On 3.0, it is not usable anymore because Apple now always throw a "There can only be one UIApplication instance." error even if [UIApplication sharedApplication] still returns nil.

But openURL doesn't require UIApplication. The core method, -[UIApplication openURL:] is actually a wrapper of the undocumented function, GSEventSendApplicationOpenURL.

I've rewritten openURL using GSEventSendApplicationOpenURL, and can be downloaded from http://code.google.com/p/networkpx/downloads/detail?name=openURL.zip. Note that GSEventSendApplicationOpenURL relies on the Graphics Services private framework, and this framework isn't very stable, so there is a chance it won't work on 4.0.

You'll notice that there's now a new argument, "port-name". That's actually not quite useful, but I found that it's used in UIKit, so just added it in. (One more reason is that, the function that obtains the default port is renamed in 3.0.) And that piece of UIKit code doesn't work :(.

3.0's presentModalViewController:withTransition:

In 3.0 the algorithm -presentModalViewController:animated: is changed. The most prominent change I can see is that the modal view controller will always use the application frame instead of the parent view controller's frame. This breaks modal table theming in GriP. Fortunately, probably Apple also thinks the change to too drastic, they've also provided -_legacyPresentModalViewController:withTransition: that uses the old algorithm, so until iPhoneOS 4.0 comes we can still ignore this problem.

The 3.0's -presentModalViewController:animated: calls the undocumented method -presentModalViewController:withTransition: as a backend, where the 2nd parameter "transition" is an integer. For official SDK there're 5 official transitions (present and dismiss count as 2): Slide up/down, Flip to left/right, and cross fade.

But -presentModalViewController:withTransition: supports a bit more:
ParameterTransition
0None
1Push from right to left
2Push from left to right
3Push from bottom to top
6Fade
7Push from top to bottom
8Slide from bottom to top
9Reveal from top to bottom
10Flip from left to right
11Flip from right to left

Saturday, June 20, 2009

3.0 Status

Updates:
  1. iKeyEx beta for 3.0 has been out there for weeks. Check the newest posts.
  2. Calculator.searchBundle won't work until someone completely rewrites Spotlight. The guy behind iFile tried to enable custom search bundles before, but the overly-optimized interface made it impossible without rewrites.





iPhoneOS 3.0 has been released and jailbroken, and I've also upgraded, so from now on my primary focus of OS will be 3.0, instead of 2.2.1.

GriP worked pretty well on 3.0. It is predictable as GriP was designed to be as SDK-compatible as much, and I've tested it on 3.0b1 (simulator) from the start.

But iKeyEx is totally different. It cannot work on 3.0 without in-depth investigation on UIKit again. The primary reason is in 3.0 Apple redesigned a lot in language UI. 80% code of UIKit is about the new keyboard UIKeyboardLayoutStar. The input manager is so heavy that split into its own private framework, TextInput.framework. That carries away UIKeyboardInputManagerAlphabet which iKeyEx relies on.

iKeyEx will be 3.0-ready, of course, but it will be a long time to wait.

(And because 3.0 supports single-clipboard copy-and-paste natively, I'll discontinue the current form ℏClipboard. I may write a multi-clipboard extension though.)

As for the side-projects, Calculator.searchBundle does not work as I expected. I need to check the source code of Search.framework again. And I haven't checked if AdKiller works or not.

Sunday, June 7, 2009

An incomplete list of entitlement keys


KeyTypeUsed byChecked byNotes
com.apple.springboard.debugapplicationsbooleangdb
gdbserver
SpringBoard:
_SBXXCancelWatchdogAssertionForProcess
_SBXXRenewWatchdogAssertionForProcess
_SBXXAddWatchdogAssertionForProcess
_SBXXLaunchApplicationForDebugging

com.apple.springboard.launchapplicationsbooleaniapd
Cydia.app
Preferences.app
Web.app
SpringBoard:
_SBXXLaunchApplicationWithIdentifier

com.apple.springboard.opensensitiveurlbooleanCoreLocation.framework
dataaccessd
ManagedConfiguration.framework
AppStore.app
MobileAddressBook.app
MobileMail.app
MobileMusicPlayer.app
MobileSafari.app
MobileStore.app
Preferences.app
locationd
SpringBoard:
_SBXXOpenSensitiveURL

com.apple.springboard.wipedevice
boolean
dataaccessd
Preferences.app
SpringBoard:
_SBXXDataReset

com.apple.springboard.setnowplayinginformation
boolean
YouTube.framework
MobileMail.app
MobileSafari.app
YouTube.app
?

com.apple.springboard.activateawayviewplugins
boolean

SpringBoard:
_SBXXEnableLockScreenBundle

com.apple.remotenotification.server.preferences
boolean
Preferences.app
SpringBoard:
_SBRNSetBundleIdentifierTypes

get-task-allowbooleangdb
gdbserver
?The only documented entitlement key, means "Can be debugged".
task_for_pid-allowbooleanReportCrash
ps
gdb
gdbserver
kernel
keychain-access-groupsarray of stringsToo many
?Everyone uses it has the value (apple).
application-identifierstringToo many
?The content may not be the same as the bundle ID. For example, the application-identifier for AppStore apps will be (10 random characters).(bundle ID)
allow-obliterate-devicebooleanSpringBoard
?
seatbelt-profiles
array of strings
MobileMail.app
MobileSafari.app
Web.app
kernel?

modify-anchor-certificates
boolean
Preferences.app
?



The entitlement of a task can be obtained using the undocumented SecTask*** functions. Because of this, a library can define a set of entitlement keys other applications using it must follow.

Friday, June 5, 2009

GriP 0.1-11m released

GriP 0.1-11m (r323) is released, and can be downloaded at http://code.google.com/p/networkpx/downloads/detail?name=hk.kennytm.grip-0.1-11m.deb.

The biggest change in 11m is the support for "Modal Table View". You've Got Mail has been modified to support this. The new mail message now looks like:

Note that the "detail disclosure button" is not there. When you tap on the message a table will pop up:

You can click on each item to view the message (not as ideal as MobileMail.app, but still readable):


Why is this change? My rationale is that, if you want to show the detail, you are focusing on the message, and stuffing that much information in that message is not good. If you're focusing on it, why not maximize the view? Hence it is shown as a "Modal Table View".

Does this contradict with the philosophy behind GriP (unobstructive)? No, because this modal thing already has user confirmation, while for alert boxes they just pop up with no prior consent.

(If you don't like this, you can always downgrade to 0.1-11k available in http://code.google.com/p/networkpx/downloads/detail?name=hk.kennytm.grip-0.1-11k.deb.)

Thursday, June 4, 2009

Displaying UIView hierarchy of a compiled app

Suppose you want to investigate the view hierarchy of some app you did not write. There is a simple way using GDB:

  1. Compile UIUtilities.m into a dylib or bundle. You can download it precompiled here.
  2. Upload the file to the device, e.g. /var/mobile/UIUtilities.bundle. Do not put it in /var/root/.
  3. Now attach gdb to the executable you want to investigate.
  4. Inject UIUtilities to the executable. In the gdb prompt, type:
    call (int)dlopen("/var/mobile/UIUtilities.bundle", 10)
    If a nonzero value appears, injection succeeded.
  5. Finally, type:
    call (void)UILogViewHierarchy((int)[[UIApplication sharedApplication] keyWindow])
    The UIView hierarchy of the key window will be recorded in syslog.

Monday, June 1, 2009

Testing various Regular Expression solutions, Part 1.5

One thing I really like about blogs is that you can exchange ideas and learn something you naturally won't know for a lifetime because you are not an expert. (And I hate you, Xanga Friends Lock users.)

Firstly, I have added the 3 options -DNS_BLOCK_ASSERTIONS=1 -DRKL_CACHE_SIZE=307 -DRKL_FAST_MUTABLE_CHECK=1 as instructed and able to reduce the running time from 1.7s to 0.7s, but still quite slow compared with ICU at 0.25s. Then I increased the cache size to 709, and the running time is now 0.4s. Further increasing to 1619 starts make the running time longer probably due to excessive memory use.

RKL,307 RKL,709
-------------------
0.691226s 0.384044s
0.692440s 0.381194s
0.684274s 0.381550s
0.689568s 0.382489s
0.683985s 0.384499s


Then I consider rolling all 16 pattern into one big RegExp like RE1|RE2|RE3|.... One problem with this is each pattern must not have back-references, but this is fine for wildcard rules since back-references do not appear at all. But another nasty thing is that AdBlock Plus rules has the so called filter options which prevents simple merging to take place. Anyway, the running time after merging are:

ICU       PCRE      regex.h   RKLite    JSRegExp
-------------------------------------------------------------
0.260404s 0.189028s 2.526485s 0.268121s 0.141875s AllInOne
0.256532s 0.160290s 2.526872s 0.264368s 0.141586s
0.257263s 0.160135s 2.536937s 0.266934s 0.142434s
0.256900s 0.160222s 2.532003s 0.265274s 0.141467s
0.256744s 0.160232s 2.528987s 0.264851s 0.142299s
-------------------------------------------------------------
0.253102s 0.067551s 0.235714s 0.382489s 0.113274s SeveralInst (median of 5)

So while RegexKitLite does become faster, all other methods are dragged down, esp. the POSIX ERE. This confirms johne's statement.

There are some other developments: (1) I've found the fnmatch function that does wildcard matching, but the running time is 0.8s, probably due to the use of recursion and implicit calls on locales. (2) Then I've written a specific routine that checks using pure C string, and the result is dramatic -- the function only takes 0.02 seconds! This restored some of my logical beliefs :D.

fnmatch5
---------
0.021076s
0.021167s
0.021065s
0.021229s
0.021238s


The new source code can be found in: http://pastie.org/496783.

Sunday, May 31, 2009

Testing various Regular Expression solutions, Part 1

Edit: Please check also Part 1.5 for some further analysis.

For AdKiller to work properly, Regular expression matching should be supported. There are various RegExp solutions for the iPhoneOS:
  1. regex.h
  2. ICU's regular expression engine
  3. PCRE
  4. RegexKitLite, which is an ObjC wrapper of the ICU engine.
  5. JavaScriptCore's regular expression engine.
  6. Do it yourself!

For Ad blocking, we only need to test if the Regular Expression matches, so I've limited the test case to a simple RegExp.test only.

In this part, I'll test for the AdBlockPlus "wildcard rules", where a * matches anything, and optional | at the beginning or end to indicate an anchor. Because of the simplicity, we can actually do the test without using RegExp (e.g. using CFStringFind).

From the complexity of the RegExp engines, we would expect the time taken follow this order:
CFStringFind << regex.h << JSRegExp < ICU < RegexKitLite < PCRE



But somewhat surprisingly, the actual time taken is like this:
ICU       PCRE      regex.h   RKLite    JSRegExp  CFStrFind
-----------------------------------------------------------
0.253456s 0.069918s 1.726371s 1.651787s 0.139437s 0.078097s
0.275680s 0.067150s 1.715131s 1.652074s 0.112813s 0.075818s
0.251526s 0.067994s 1.716483s 1.637005s 0.113267s 0.075716s
0.250806s 0.067551s 1.721203s 1.626927s 0.113274s 0.075726s
0.251498s 0.067168s 1.716587s 1.651783s 0.113605s 0.076064s


So the ordering would be:
PCRE < CFStringFind < JSRegExp < ICU << RegexKitLite < regex.h


The most complex engine is the fastest! CFStringFind ranks the second probably because my code is not optimized, but this shows the PCRE engine is really efficient. JSRegExp was originally a PCRE with everything irrelevant to Javascript stripped out, but that is slower than PCRE by 2 times. The WebKit devs should think of what's wrong. RegexKitLite's performance is pretty disappointing. Although it is advertised as very efficient, it is still 6~7 times slower than bare-bone ICU. The problem is probably directly using NSString as the RegExp holder, instead of a dedicated RegExp class. And regex.h's result is really a *WTF*.


Edit: I have redone the test to eliminate some inconsistency (case sensitivity) and convert the regex.h's syntax form BRE to ERE. The result is impressive: ERE is faster than BRE by 7 fold, make in in par with ICU. The new results are:
Methods
ICU PCRE regex.h RKLite JSRegExp CFStrFind
-----------------------------------------------------------
0.253736s 0.069918s 0.238111s 1.651787s 0.139437s 0.070956s
0.254308s 0.067150s 0.235963s 1.652074s 0.112813s 0.068302s
0.252483s 0.067994s 0.235714s 1.637005s 0.113267s 0.068710s
0.251647s 0.067551s 0.234380s 1.626927s 0.113274s 0.068353s
0.253102s 0.067168s 0.235367s 1.651783s 0.113605s 0.068280s

and the new ordering is:
PCRE ≈ CFStringFind < JSRegExp < regex.h < ICU << RegexKitLite

So PCRE is still the fastest, but with a smaller margin. And RegexKitLite is now win the title of the slowest RegEx implementation.

To conclude this part, we should use PCRE for wildcard testing, if speed and clarity are important.

The source code of the test can be found in http://pastie.org/495990. Basically, 323 URLs collected from 3 different sources are matched against 16 wildcard rules. The file is compiled with:
/Developer/Platforms/iPhoneOS.platform/Developer/usr/bin/gcc-4.0 -arch armv6 -std=c99 -isysroot /Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS2.2.1.sdk -I/Developer/Platforms/iPhoneOS.platform/Developer/usr/include/gcc/darwin/default -I/Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS2.2.1.sdk/usr/lib/gcc/arm-apple-darwin9/4.0.1/include -L/usr/local/lib -Wall -mcpu=arm1176jzf-s -O2 -L. -framework CoreFoundation -framework Foundation -licucore -lpcre main.m RegexKitLite.m ; ldid -S a.out
and run on a jailbroken iPod Touch 1G, firmware version 2.2.1.