By now, a lot of Mac users are probably familiar with Messages, Apple’s new Instant Messaging app. One of the features which this app stealthily removed was formatting: that is, all incoming messages are automatically stripped of bold, italic, and various other font tags. But, being the poorly coded program that it is, Messages sometimes fails to reformat an incoming message. I decided to investigate this further.

I first noticed that Messages didn’t always reformat incoming messages when my friend sent me a quote which was copied from a website. For some reason, the text remained bold when I saw it on my machine. I decided to throw up the LibOrange Xcode project that I already had lying around on my computer in order to log the HTML of the message which somehow eluded Apple’s reformatting.

At first glance, the body of the message seemed ordinary: there were no tags which stood out; in fact, the HTML itself had nothing to do with why Messages was failing to reformat. However, the message did contain a very unique attribute which allowed it to slip past the reformatting process.

As a quote, the message was not only formatted, but also surrounded by ” characters. And, as many fellow copy-and-pasters know, most websites use special characters for open/close quotes; these characters are not the standard ASCII quote character, but rather a UTF-16 character. When I realized that these fancy quotes surrounded the message, I came to a conclusion: unicode characters break Messages’ reformatter.

I tested this theory with LibOrange. I setup a simple AOL screenname which automatically echo’d messages I typed, replacing &lt; and &gt; with < and >. I found that, if an HTML format tag came after a unicode character in the message, Messages did not remove it:

A UTF-16 quote breaks Messages' reformatting

So, what conclusion can I draw from this? One which I already drew a while ago: Messages was poorly implemented. On top of that, what I’ve found shows that Apple’s code which processes incoming messages is not perfect. With this in mind, it might be possible for someone to derive an exploit which could be triggered simply by sending someone a message. However, this doesn’t seem likely to be possible, but who knows; if Apple fails at one thing, what else may they have failed at?

The new Macbook Pro, along with its retina display, includes a new, simplified display settings preference pane. This preference pane, while allowing the user to switch between various retina-friendly preset resolutions, does not allow for the selection of custom resolutions. In fact, the available resolutions do not even include the display’s native resolution, 2880×1800.

Despite the simplified preference pane, however, it is still possible for an application to modify the resolution manually. In fact, I personally crafted a simple command-line application to do just this: the application allows the user to set many common resolutions, including the native, full resolution. A user can download this executable with this link; it can be executed by dragging the unzipped file into Terminal, typing a width, a space, and a height (both in pixels), and hitting enter.

I have posted the source code to GitHub. In the future, I plan to craft a more user-friendly version of this software; typically a CLI is scary to users, especially when they are required to compile it themselves through Xcode.  As of now, the command-line executable supports additional arguments to set fields such as the bit-depth and scale (a value of 2 for retina display, 1 for regular displays).  Since the program only allows the user to specify pre-defined screen preferences which have been built-in to I/O Kit’s drivers, a –modes flag allows the user to list all available settings.

One other technical note: in the process of working with Apple’s Quartz Display Services framework, I discovered something which was essential and which Apple’s API refused to provide: the ability to get a dictionary of attributes for a given screen mode.  However, I noticed that the CFType which apple would give me responded to -description, printing out all of the desired info.  Once I knew that this data structure was hiding my precious metadata, I did some hacking.  I found the offset in the CFType at which a pointer to the info dictionary is stored; I then made a method to retrieve that dictionary.  While this is a dirty, disgusting hack, it had to be done.

Many years ago, a young and curious version of myself took an interest in calculators, and with such an interest, I felt that it was necessary for me to own every different kind of calculator that I could get my hands on. After expressing my interest to my father, he went out and bought me a Casio fx-9750G PLUS programmable calculator. At the time, however, I was not that big into programming, and thus the calculator was left to collect dust in my closet.

Recently, however, I decided to take it out again, simply because it had advanced expression parsing that I believed to be necessary for certain subjects in school. For instance, the calculator allows the entry of expressions such as “(((2.5*9.81)^2 + 2) – 32)/(64^2)”, making something that would otherwise be a hassle to calculate into a piece of cake. At first, my only ambition was to be able to do such calculations with ease, which would lessen my anxiety on science and math exams. Being a programmer, though, I soon discovered the underlying delight of my calculator, the BASIC programming environment. The fx-9750G PLUS includes an environment in which you can enter programs in Casio’s BASIC language, using one of many built-in functions and operations. I quickly began to write programs that helped me with problems on tests, and other programs that really weren’t useful for school at all.

Pretty soon, I realized that entering programs on my calculator before I planned them wasn’t the best practice, since I would then have to modify the program on my calculator in order to fix bugs. I took to the habit of writing programs in my notebook before entering them on my calculator, which did ease some of the pain, but also left something to be desired. The problem was, I could think through programs all I wanted to on paper, but how could I test them? That’s when I made the decision to make a custom BASIC interpreter for my computer that would allow me to enter and test BASIC programs on the fly, with the joy of typing on a qwerty keyboard instead of Casio’s poorly thought out keyboard layout.

Since I did not plan on fully recreating Casio’s language, I decided to call my mutated spin-off ANBasic. Before I even set out on this project, I’d been dreaming for a long while of making some form of proprietary byte-code, just because I liked the idea of creating data that is unreadable to humans but easily understandable to machines. So, it was my decision early on that my ANBasic interpreter would process a script, compile it to ANBasic byte-code, and then would be able to execute this byte-code at a later point in time.

The first step to implementing this project was to design a simple tokenizer for the ANBasic language. This tokenizer would read a raw script file, split it up line by line, and pick out tokens, such as mathematical operators, function and variable names, etc. Once the tokenizer was done, I created a “grouper,” a small set of subroutines that processed control-flow statements, applied the order of operations (PEMDAS), and grouped functions with arguments. The grouped script would then be written to a binary byte-code file in my custom byte-code format. The runtime would then load this grouped script from a file, and execute the grouped script using a series of Objective-C categories on different code objects.

Although the compiler itself generates a grouped script, and could easily execute it without writing it to a file, I already had my mind set on designing a byte-code format, so that is what I did. And, if I do say so myself, the final product is pretty nifty. Although my ANBasic project isn’t quite done as of yet, it can currently compile a variety of control-flow statements, functions, expressions, etc., and can execute them. I have tested it with some of the programs that I wrote for my calculator, and it works like a charm. You can check out the ANBasicCompiler Github repository for yourself and see what I’ve been working on. At this point, I’ve already pretty much lost interest in my Casio, as I’ve recently obtained a new TI-Nspire calculator. Despite this change, I still stuck to finishing my ANBasic project, which ended up teaching me some valuable lessons about tokenization and lexical analyzation, not to mention the fact that I simply had nothing better to do.

In computer science, a queue is an abstract data structure that, when used correctly, can be used to search through nodes in an efficient and exhaustive way. This kind of search is also known as a Breadth-first search. A queue is made with a stack that can push and pop “nodes.” A node can be expanded into zero or more sub-nodes, which are then pushed to the end of the stack. Every time a node is popped from the front of the stack, checks are made to see if it is the search destination. If it is not, it is expanded, and the sub-nodes are pushed to the end of the stack. If there are no items left to pop from the stack, the search has been completed with no results.

This search algorithm can be applied to many things, one of which being unit conversions. In science and throughout one’s life, units are used for different things. One might use meters for distance, kilograms for weight, or minutes for time. Most units can be linked to other units with equivalencies. For instance, one foot is equal to 12 inches, meaning that there is an equivalency between feet and inches. Further more, one yard is equal to three feet, meaning that a yard is 36 inches. A conversion like this can be done by following an equivalency chain. Although there are multiple ways to implement something that does these kind of conversions, I chose to use queues, creating an interesting and thought-intensive programming exercise.

I designed a unit converter in Objective-C that uses queues for unit conversion. The converter runs with a pre-compiled list of pretty basic equivalencies. From these, it can convert any compatible units that were programmed in before hand. For example, it knows that one foot is 12 inches, and that one yard is three feet. So, in order for it to convert from inches to yards, it must follow this equivalency chain, in this case using a queue.

First, the queue starts out with one node, or the starting point. In this case, we are starting with inches. It then pushes the available equivalencies that it knows for inches. Since the pre-programmed equivalencies are pretty bare-bones, the inch unit only has one equivalency, stating that there are 12 inches in a foot. So, the new feet node is pushed to the queue, and the inches node is removed. It expands and pops the feet node, which has an equivalency to yards. When it gets around to popping the yards node, it realizes that yards is the unit that it wants, and traces back a history data structure to figure out the equivalency chain that it has followed.

On Github, I have posted a sample project that allows the user to enter two units. It then tells you the final equivalency (e.g. inches to yards), as well as the equivalency path that it took to get that answer. Here is an example of the usage:

Have: km
Want: inch
1 kilometer = 39370.078800 inchs
kilometer -> meter -> yard -> foot -> inch

As you can see, the user entered the “have” and “want” units, and the program did the rest. The framework for unit conversion is pretty easily expandable, having a simple ConversionConst.h file where equivalencies and units can be added/removed. This file gives the program its intelligence. I worked hard to make the API able to convert units without being given very much equivalency information. It can do its job as long as the equivalency chain between two units exists in the pre-compiled information.

For the past couple of days I have been investigating Automatic Reference Counting (or ARC) that comes with LLVM 3.0. This compiler takes memory management off the developers hands, provided that a few simple rules are followed, and that conventions are kept.

I decided that the best way to get used to ARC would not be to write a new project using ARC, but instead to port some existing code to ARC. One of the libraries that I maintain, ANImageBitmapRep, seemed like a good candidate, since it is used in a number of projects that, in the future, may be ported to ARC themselves.

Realizing that ARC is not yet widely used, I decided to add conditional statements to the code that would allow it to be compiled with ARC, while still being able to work with old compilers, or with ARC disabled. I did this using the __has_feature(objc_arc) macro in conjunction with the #if compiler directive.

One of the confusing pieces to the migration to ARC was that ANImageBitmapRep, using underlying CoreGraphics objects, has many functions that return Core Foundation types such as CGImageRef. Because of this, I had to figure out how to autorelease a CF type manually, without directly calling the now forbidden autorelease instance method. In order to trick ARC to doing this, I created a function marked with __attribute__((ns_returns_autoreleased)), indicating that the return value should be retained and autoreleased. This helper function took a CGImageRef and returned an object (the result of a bridged cast from CGImageRef to id).

Besides this, all that I really had to do was remove all of my retain/release calls, and fix a couple circular retain cycles. Finally, I got a compiled version of ANImageBitmapRep and an iOS demo app to compile and run using ARC. Testing for leaks on the final product was a success, revealing that ARC had done it’s job of releasing everything that it aught to. This port was a great success, and I suspect that in the future I will be writing more code for ARC only, despite the fact that I will not be able to use the __weak ownership qualifier for compatibility issues.

Apple recently released Xcode 4.2, complete with the LLVM 3.0 compiler. This new compiler includes better optimizations than LLVM-GCC had in Xcode 4.1, and comes with some pretty nifty features. The most notable new feature is ARC, or Automatic Reference Counting. If you are not familiar, Objective-C is a language based heavily on retain counts for manual memory management, and therefore ARC is quite a big deal.

Every (good) Objective-C programmer knows how to keep track of his retain counts in a manageable way. Using good conventions, it’s possible to make your app leak-free, but it certainly does take a lot of work, and seems like a rather pointless practice in this day and age. Objective-C, C++, and C are pretty much the only languages that still emphasize memory management as a major concern, making them seem rather obsolete when compared with languages such as Java or PHP.

Luckily, the new LLVM compiler does away with all of this. By automatically tracking objects’ lifecycles, the compiler can intelligently insert memory management code at compile time. One of the major downsides is that, in order for this to work properly, one must follow a set of new conventions. For instance, there are several __attribute indicators that may sometimes need to be put in different functions, specifying the retain lifecycle that a given object should have.

For initializers, there is a special __attribute for objects that will be “consumed” by the class. This is to say that, when passing object X into an initializer, the caller agrees that X had a +1 retain count, and that it is passing ownership to the callee.

Return values can be marked with __attribute((ns_returns_retained)) to indicate that the object has a +1 retain count, and that the ownership is to be passed to the caller.

Another thing that ARC enforces is that, in order to store Objective-C objects as C pointers, bridging must be used. This seemed like an obvious tactic to me, knowing all too well how the NSArray implementation must look. I figure that, if I were to see the code for NSArray, I would see something along the lines of a void **, allocated with malloc(), and populated with pointers to Objective-C objects. When casting a retainable object to a C pointer, one should use the (__bridge_retained T) op cast. This retains op, then casts it to the given type, T. To cast back from C pointer to Objective-C object, (__bridge_transfer T) will cast the pointer back to an Objective-C object, noting to release the object when it goes out of scope, or after the last place that it is used. Plain (__bridge T) will simply cast between object or pointer, without worrying about retain counts.

One more notable feature of ARC that I noticed is the __weak and __strong ownership qualifiers. If a variable has the __strong ownership qualifier, all objects assigned to that variable will be retained. Unlike with __strong, __weak variables do not retain/release values. Instead, every __weak variable is set to nil whenever the object that they referenced is deallocated. This will prevent invalid access of dealloc’d objects, which tends to be a pretty common issue in Objective-C code. Each of these qualifiers can be used for instance variables, local variables, and even function arguments.

What do you use when you want a server to communicate with a client over TCP? Some people would tell you to use HTTP. Some people would write their own binary protocol. A friend of mine is actively developing an IM client which communicates with a server using JSON. Unfortunately, some of this data needs to be raw binary, such as buddy icons, etc. Along with that, he uses JSON-framework for encoding and decoding.

JSON (JavaScript Object Notation), is a lightweight, human-readable way of representing dictionaries, arrays, strings, and numbers. For instance, a dictionary containing a single key might look something like this: ["myKey":999999]. You may immediately notice that the data could be smaller. There are two bytes already taken for the open and close brackets. Another two taken by the quotation marks. A few wasted bytes where a four-byte binary integer could be used to represent the number 999999. To some, this is fairly irrelevant. But consider the same amount of overhead for a very large amount of data. A more efficient binary storage method would be nice, and very handy to many.

I created a project called KeyedBits, a binary archive format. First I started off by writing a very simply Objective-C encoder and decoder that I called KBKit, which used some fancy object orientation to achieve its goal. Unfortunately, benchmarking this implementation gave unpromising results. Although it appears that KeyedBits saves an average of around 13%, KBKit was almost two times slower than JSON-framework. My natural reaction was not to optimize my Objective-C implementation, but to write another one in C.

I had already sacrificed the elegance and beauty of JSON, instead using a rather ugly binary format that only looks good when viewed in a hex editor. Now, I had to sacrifice the elegance of KBKit and instead write a C framework. For lack of a better name, I decided to call this C framework KBCKit.

It turns out that encoding was neck-and-neck between JSON-framework and KBKit. The real tie breaker was decoding. After I implemented both the encoder and decoder for KBCKit, and had written an Objective-C wrapper for each, I found that I was successful. KBCKit now is able to encode and decode almost twice as fast as JSON-framework. This, on top of the fact that there’s little overhead, makes KeyedBits a great alternative to JSON in Objective-C applications.

The lesson to be learned here is that sometimes beauty is not better than efficiency. Sure, my C implementation isn’t as fancy as my Objective-C implementation, but it certainly has a better end result. There are times when it’s okay to use a high-level language, but there are also times when it’s simply not appropriate. Imagine if the Linux kernel had been written in C++ instead of C. It would probably be a lot easier on the eyes, but ultimately easy on the eyes isn’t its purpose. Things like kernels, video decoders, and KBCKit were made to be used, not drawn on paper and hung in an art museum. The user doesn’t care how elegant the code is, they just want something with raw speed and power.

Recently I have been spending much time programming an operating system in C and assembly, using simple data structures and calling function after function.  I have decided to take a break from OS development, and instead work on some more high-level stuff in Objective-C.  I am currently working on an app called SuperLists, but today I wasn’t in the mood to work on an iPhone app.  Instead I decided to put some object-oriented programming to work in a mathematical expression parser.

A long while ago I wrote something very similar to this.  You can see the post for that here.  That expression parser didn’t correctly utilize the object-oriented programming model, and certainly wasn’t neat and organized.  The parser that I wrote today has the same final result as the old one, but is structured in a much better and more elegant way.

When parsing human readable text, the first thing your parser should do is convert a human-readable string into a data structure that the program can understand.  This stage is actually the definition of parsing, whereas calculating the result of the expression is known as evaluating.  So, I planned out a structure that would hold different operators, numbers, variables and functions.  This structure contains a base class, EPToken, with subclasses like EPOperator and EPNumericalToken.

After parsing the string given by the user, it is up to the evaluator to use the parsed tokens and calculate an end result.  The evaluator must follow the order of operations, whereas the parser simply reads the sequential tokens from the string.  To achieve this, the evaluator first recursively evaluates the “sub-expressions”, which are potential expressions contained within ( and ).  Next, all functions such as sin and sqrt are evaluated.  Finally, the evaluator evaluates different operators, such as ^, +, -, etc.

Every time a part of the expression is evaluated, that part is replaced by the numerical result.  For instance, when evaluating the ^ expression in 3x + 10^2 + sin(y), the result would be 3x + 100 + sin(y).  Once all operators, functions, and variables are evaluated, the only thing left in the expression should be a numerical constant.  This constant is the final result of the expression.

I finished the parser in only a few hours, and posted the code to a Github repository.  The project includes a demo of how to use my NSNumber additions to parse expressions with custom variables.  Custom functions can be used, but not when using the NSNumber convenience methods.

So Apple, want to explain why NSImage doesn’t support saving ICNS files? No, I won’t! Because I love proprietary software.

Today I was writing a small Cocoa application that “exports” a pre-made application with a custom icon and display name. Of course any Mac developer knows that all Mac app’s icons need to be in the ICNS format. I figured that, since Apple is the creator, owner, and maintainer of the ICNS format that they would surely have an API for exporting them. After all, Apple does have several apps that can create ICNS files. It turns out this this is not the case.

Apple’s NSImage class can load ICNS files, but cannot save them. I have no doubt in my mind that Apple has code sitting out there to export these files. The only reason that Apple wouldn’t give out this code is that they want to have as much control over the ICNS format as possible.

In my opinion, the ICNS format is nothing special. It has a two-field header followed by an array of different images. The format of these images differs based on their type. More information can be found on the ICNS Wikipedia page.

Anyway, I went along and wrote a small encoder for ICNS files. If you are not familiar, every ICNS file can store the same image in different sizes. For some bazar reason, different image sizes are encoded with different formats. Both 512×512 and 256×256 images are stored as JPEG2000 data inside of the ICNS file’s contents, making that the ideal size for me to implement. Apple already has an API for exporting JPEG2000 files, so all my encoder would need to do would be write the ICNS headers and the pre-encoded JPEG2000 data.

I finished my encoder in under an hour, which is not surprising when taking into account the simplicity of the ICNS format. I uploaded the entire project to Github, and the code for ICNS files can be found in BasicICNSExport.m.

When writing a private or sensitive document, encryption is always your friend. Whether it be your holiday shopping list, or a secret government document, PDF encryption is sometimes looked upon as the solution. Now, why anybody would ever use PDF is beyond me. All I know is that it’s not uncommon to stumble upon one of these documents and not be able to access their contents.

Before I can explain to you how one might go about cracking a PDF, I have to explain to you how encryption works from a PDF standpoint. When setting a password in any modern PDF viewer, you have two options for encryption. The first is a password required to open the document, also known as the user password. This password is used for encryption. The second password is optional, and, if present, sets permissions that should not be allowed unless the second password is given. The second password, also known as the owner password, is not used in the encryption process, and is just there for a false sense of security. This being said, it is up to the PDF viewer to govern the rules set by the creator of the PDF, as long as the correct user password was given. With the user password, any PDF viewer can read, copy, print, edit, etc. The owner password is just there for show, and is enforced by pretty much every professional PDF viewer.

The PDF encryption process is slightly more complicated than one might think. Normally, something like this might be done by MD5 hashing the password, and using some of the output buffer as an encryption key. In my opinion, this is a perfectly good and reliable method of security, but Adobe clearly doesn’t think so. The encryption key used in a PDF file can be calculated by mashing up some information from the PDF document along with the passphrase entered by the user. This encryption key can then be verified by decrypting a buffer stored in the PDF file. If the output of this buffer is a pre-defined string (in Adobe’s specification), then the encryption key is correct. This is the only easy way to validate a password for a PDF file, given that Adobe uses a simple RC4 encryption algorithm, which allows any key, no matter how invalid, to be used for decryption without error or warning.

So, knowing all of this, I set out to make a PDF cracker. The normal procedure when cracking a password with brute force is something like this: pick a password, check if its correct, if not, repeat. This all seems very simple, but how do we perform the second step? Like I said above, you need a bunch of bits of information from the PDF document (all available in it’s binary contents), and of course the magic, pre-defined Adobe encryption string.

As I discovered, getting data from a PDF file is pretty straight forward. PDF files are split into parts. A part can either be an “Object”, or a “Stream.” For my cracker program, I would have to find the trailer object, read the document ID, then find the encryption object. The encryption object contains all of the pieces of data (other than the document ID) that is needed for generating the encryption key.

The process of actually reading objects from a PDF file is pretty simple, but I will not describe them here. To see how I do it, check out my code for it in PDFReader.c in my cracker program. Anyway, with this information, all that was left to do was actually write the code to test a password.

Generating the encryption key is a multi-step process. You need to pad the user password (passphrase used for encryption) to a 32-byte buffer. You then append the hash of the “owner” password (readily available in the PDF’s contents). Finally, you append a four-byte, little endian permissions number (also found in the PDF file), followed by the document ID. MD5 hashing this gives you a 16-byte buffer, the first five of which being the encryption key. This key is then used to decrypt the “user” hash from the encryption object. If this is equal to a special string defined by Adobe, then the user password and other information was correct.

My PDFCrack program itself is a command-line, UNIX application. It takes either a dictionary file, or reads passwords to test from standard input. If no dictionary source is specified, it generates strings systematically in order, testing each and every string as a potential password.

As I always do, I have posted this code to a GitHub repository. Unfortunately this cracker only works on PDF version 1.3 and 1.4 (exported by Pages ’09 on Mac OS X). It could probably be expanded for other, newer versions of the PDF specification, but I have no real reason to do that myself. If you would like to expand on it, please, fork my repository and get to work. That’s what open source is for, isn’t it?