Monday, October 31, 2011

So you think that money is the root of all evil?

Have you ever asked what is the root of money? Money is a tool of exchange, which can't exist unless there are goods produced and men able to produce them. Money is the material shape of the principle that men who wish to deal with one another must deal by trade and give value for value. Money is not the tool of the moochers, who claim your product by tears, or of the looters, who take it from you by force. Money is made possible only by the men who produce. Is this what you consider evil?

When you accept money in payment for your effort, you do so only on the conviction that you will exchange it for the product of the effort of others. It is not the moochers or the looters who give value to money. Not an ocean of tears not all the guns in the world can transform those pieces of paper in your wallet into the bread you will need to survive tomorrow. Those pieces of paper, which should have been gold, are a token of honor--your claim upon the energy of the men who produce. Your wallet is your statement of hope that somewhere in the world around you there are men who will not default on that moral principle which is the root of money. Is this what you consider evil?

Have you ever looked for the root of production? Take a look at an electric generator and dare tell yourself that it was created by the muscular effort of unthinking brutes. Try to grow a seed of wheat without the knowledge left to you by men who had to discover it for the first time. Try to obtain your food by means of nothing but physical motions--and you'll learn that man's mind is the root of all the goods produced and of all the wealth that has ever existed on earth.

But you say that money is made by the strong at the expense of the weak? What strength do you mean? It is not the strength of guns or muscles. Wealth is the product of man's capacity to think. Then is money made by the man who invents a motor at the expense of those who did not invent it? Is money made by the intelligent at the expense of the fools? By the able at the expense of the incompetent? By the ambitious at the expense of the lazy? Money is made--before it can be looted or mooched--made by the effort of every honest man, each to the extent of his ability. An honest man is one who knows that he can't consume more than he has produced.

To trade by means of money is the code of the men of good will. Money rests on the axiom that every man is the owner of his mind and his effort. Money allows no power to prescribe the value of your effort except the voluntary choice of the man who is willing to trade you his effort in return. Money permits you to obtain for your goods and your labor that which they are worth to the men who buy them, but no more. Money permits no deals except those to mutual benefit by the unforced judgment of the traders. Money demands of you the recognition that men must work for their own benefit, not for their own injury, for their gain, not their loss--the recognition that they are not beasts of burden, born to carry the weight of your misery--that you must offer them values, not wounds--that the common bond among men is not the exchange of suffering, but the exchange of goods. Money demands that you sell, not your weakness to men's stupidity, but your talent to their reason; it demands that you buy, not the shoddiest they offer, but the best that your money can find. And when men live by trade--with reason, not force, as their final arbiter--it is the best product that wins, the best performance, the man of best judgment and highest ability--and the degree of a man's productiveness is the degree of his reward. This is the code of existence whose tool and symbol is money. Is this what you consider evil?

But money is only a tool. It will take you wherever you wish, but it will not replace you as the driver. It will give you the means for the satisfaction of your desires, but it will not provide you with desires. Money is the scourge of the men who attempt to reverse the law of causality--the men who seek to replace the mind by seizing the products of the mind.

Money will not purchase happiness for the man who has no concept of what he wants: money will not give him a code of values, if he's evaded the knowledge of what to value, and it will not provide him with a purpose, if he's evaded the choice of what to seek. Money will not buy intelligence for the fool, or admiration for the coward, or respect for the incompetent. The man who attempts to purchase the brains of his superiors to serve him, with his money replacing his judgment, ends up by becoming the victim of his inferiors. The men of intelligence desert him, but the cheats and the frauds come flocking to him, drawn by a law which he has not discovered: that no man may be smaller than his money. Is this the reason why you call it evil?

Only the man who does not need it, is fit to inherit wealth--the man who would make his own fortune no matter where he started. If an heir is equal to his money, it serves him; if not, it destroys him. But you look on and you cry that money corrupted him. Did it? Or did he corrupt his money? Do not envy a worthless heir; his wealth is not yours and you would have done no better with it. Do not think that it should have been distributed among you; loading the world with fifty parasites instead of one, would not bring back the dead virtue which was the fortune. Money is a living power that dies without its root. Money will not serve the mind that cannot match it. Is this the reason why you call it evil?

Money is your means of survival. The verdict you pronounce upon the source of your livelihood is the verdict you pronounce upon your life. If the source is corrupt, you have damned your own existence. Did you get your money by fraud? By pandering to men's vices or men's stupidity? By catering to fools, in the hope of getting more than your ability deserves? By lowering your standards? By doing work you despise for purchasers you scorn? If so, then your money will not give you a moment's or a penny's worth of joy. Then all the things you buy will become, not a tribute to you, but a reproach; not an achievement, but a reminder of shame. Then you'll scream that money is evil. Evil, because it would not pinch-hit for your self-respect? Evil, because it would not let you enjoy your depravity? Is this the root of your hatred of money?

Money will always remain an effect and refuse to replace you as the cause. Money is the product of virtue, but it will not give you virtue and it will not redeem your vices. Money will not give you the unearned, neither in matter nor in spirit. Is this the root of your hatred of money?

Or did you say it's the love of money that's the root of all evil? To love a thing is to know and love its nature. To love money is to know and love the fact that money is the creation of the best power within you, and your passkey to trade your effort for the effort of the best among men. It's the person who would sell his soul for a nickel, who is loudest in proclaiming his hatred of money--and he has good reason to hate it. The lovers of money are willing to work for it. They know they are able to deserve it.

Let me give you a tip on a clue to men's characters: the man who damns money has obtained it dishonorably; the man who respects it has earned it.

Run for your life from any man who tells you that money is evil. That sentence is the leper's bell of an approaching looter. So long as men live together on earth and need means to deal with one another--their only substitute, if they abandon money, is the muzzle of a gun.

But money demands of you the highest virtues, if you wish to make it or to keep it. Men who have no courage, pride or self-esteem, men who have no moral sense of their right to their money and are not willing to defend it as they defend their life, men who apologize for being rich--will not remain rich for long. They are the natural bait for the swarms of looters that stay under rocks for centuries, but come crawling out at the first smell of a man who begs to be forgiven for the guilt of owning wealth. They will hasten to relieve him of the guilt--and of his life, as he deserves.

Then you will see the rise of the men of the double standard--the men who live by force, yet count on those who live by trade to create the value of their looted money--the men who are the hitchhikers of virtue. In a moral society, these are the criminals, and the statutes are written to protect you against them. But when a society establishes criminals-by-right and looters-by-law--men who use force to seize the wealth of disarmed victims--then money becomes its creators' avenger. Such looters believe it safe to rob defenseless men, once they've passed a law to disarm them. But their loot becomes the magnet for other looters, who get it from them as they got it. Then the race goes, not to the ablest at production, but to those most ruthless at brutality. When force is the standard, the murderer wins over the pickpocket. And then that society vanishes, in a spread of ruins and slaughter.

Do you wish to know whether that day is coming? Watch money. Money is the barometer of a society's virtue. When you see that trading is done, not by consent, but by compulsion--when you see that in order to produce, you need to obtain permission from men who produce nothing--when you see that money is flowing to those who deal, not in goods, but in favors--when you see that men get richer by graft and by pull than by work, and your laws don't protect you against them, but protect them against you--when you see corruption being rewarded and honesty becoming a self-sacrifice--you may know that your society is doomed. Money is so noble a medium that it does not compete with guns and it does not make terms with brutality. It will not permit a country to survive as half-property, half-loot.

Whenever destroyers appear among men, they start by destroying money, for money is men's protection and the base of a moral existence. Destroyers seize gold and leave to its owners a counterfeit pile of paper. This kills all objective standards and delivers men into the arbitrary power of an arbitrary setter of values. Gold was an objective value, an equivalent of wealth produced. Paper is a mortgage on wealth that does not exist, backed by a gun aimed at those who are expected to produce it. Paper is a check drawn by legal looters upon an account which is not theirs: upon the virtue of the victims. Watch for the day when it bounces, marked, "Account overdrawn."

When you have made evil the means of survival, do not expect men to remain good. Do not expect them to stay moral and lose their lives for the purpose of becoming the fodder of the immoral. Do not expect them to produce, when production is punished and looting rewarded. Do not ask, "Who is destroying the world?" You are.

You stand in the midst of the greatest achievements of the greatest productive civilization and you wonder why it's crumbling around you, while you're damning its life-blood--money. You look upon money as the savages did before you, and you wonder why the jungle is creeping back to the edge of your cities. Throughout men's history, money was always seized by looters of one brand or another, whose names changed, but whose method remained the same: to seize wealth by force and to keep the producers bound, demeaned, defamed, deprived of honor. That phrase about the evil of money, which you mouth with such righteous recklessness, comes from a time when wealth was produced by the labor of slaves--slaves who repeated the motions once discovered by somebody's mind and left unimproved for centuries. So long as production was ruled by force, and wealth was obtained by conquest, there was little to conquer, Yet through all the centuries of stagnation and starvation, men exalted the looters, as aristocrats of the sword, as aristocrats of birth, as aristocrats of the bureau, and despised the producers, as slaves, as traders, as shopkeepers--as industrialists.

To the glory of mankind, there was, for the first and only time in history, a country of money--and I have no higher, more reverent tribute to pay to America, for this means: a country of reason, justice, freedom, production, achievement. For the first time, man's mind and money were set free, and there were no fortunes-by-conquest, but only fortunes-by-work, and instead of swordsmen and slaves, there appeared the real maker of wealth, the greatest worker, the highest type of human being--the self-made man--the American industrialist.

If you ask me to name the proudest distinction of Americans, I would choose--because it contains all the others--the fact that they were the people who created the phrase "to make money." No other language or nation had ever used these words before; men had always thought of wealth as a static quantity--to be seized, begged, inherited, shared, looted or obtained as a favor. Americans were the first to understand that wealth has to be created. The words "to make money" hold the essence of human morality.

Yet these were the words for which Americans were denounced by the rotted cultures of the looters' continents. Now the looters' credo has brought you to regard your proudest achievements as a hallmark of shame, your prosperity as guilt, your greatest men, the industrialists, as blackguards, and your magnificent factories as the product and property of muscular labor, the labor of whip-driven slaves, like the pyramids of Egypt. The rotter who simpers that he sees no difference between the power of the dollar and the power of the whip, ought to learn the difference on his own hide-- as, I think, he will.

Until and unless you discover that money is the root of all good, you ask for your own destruction. When money ceases to be the tool by which men deal with one another, then men become the tools of men. Blood, whips and guns--or dollars. Take your choice--there is no other--and your time is running out.

-- Francisco d'Anconia
Atlas Shrugged by Ayn Rand

Thursday, September 15, 2011

MonoTouch Tips & Tricks: Updating the Location of an MKAnnotation

I just spent a day figuring this out, so figured I'd share it with the world because I'm sure other people are going to want to know how to do this...

So the question is,

How can I get my MKMapView to respond to coordinate changes in my custom MKAnnotations?

As it turns out, this is incredibly simple. In your MKAnnotation subclass, whenever you want to change your Coordinate property value, you need to do the following:

void UpdateCoordinate (CLLocationCoordinate2D newCoordinate)
{
    this.WillChangeValue ("coordinate");
    this.Coordinate = newCoordinate;
    this.DidChangeValue ("coordinate");
}

That's it! It really is that simple...

The reason this works is because MKMapView observes changes in its list of MKAnnotations, you just need to signal to it that changes are about to happen (and did happen).

Happy hacking!

Sunday, August 14, 2011

GMime 2.5.10: A Call For Testers

I've just released GMime 2.5.10 which I hope to be the last of the 2.5 releases before I release 2.6.0. I feel that I've stretched the development of 2.6.0 out for far too long (2.5 development began at the end of April, 2009) and even though I didn't get around to doing everything I had hoped to do, I feel that the latest 2.5.x releases are such an improvement over 2.4.x that I just want to get it out there for developers to start using. But before I make a 2.6.0 release, I'm hoping to get some feedback and some testing.

What's new?

New for the release of 2.5.10 is GMimePartIter which replaces the need for g_mime_object_foreach()and its awkward callback requirement, instead allowing you to take the far nicer iterator approach that is popular in the C# and Java worlds (known as IEnumerator in C#). This new iterator, like the foreach function it replaces, iterates over the MIME tree structure in depth-first order.

Inspired by IMAP's FETCH body part-specifier syntax, I've implemented a method allowing you to jump to a part based on a part-specifier string (aka a path): g_mime_part_iter_jump_to(). Also implemented is a function called g_mime_part_iter_get_path(), which can be used to tell you the current part-specifier path of the iterator.

For example, if you had the following MIME message structure:

multipart/related
  multipart/alternative
    text/plain
    text/html
  image/jpeg

The body part-specifier paths would be:

1    multipart/alternative
1.1  text/plain
1.2  text/html
2    image/jpeg

This means that g_mime_part_iter_jump_to(iter, "1.2") would jump to the part specified by the path "1.2" which, as we can see above, would be the text/html part. Calling g_mime_part_iter_next(iter) would iterate to the next part, being the image/jpeg, while calling g_mime_part_iter_prev(iter) would iterate backwards to the text/plain part and calling it again would iterate backwards to the multipart/alternative.

What I Need From Testers

My feeling is that developers will want to use this cool new body part-specifier path functionality for aiding them in implementing IMAP servers and/or clients. Because of this, it would be great if GMime's implementation matched IMAP's specification exactly. The problem is that I don't have the time or energy to verify that the paths work out to be identical in all cases. So... if you are one of those developers who is interested in using this functionality and need it to be identical to IMAP's syntax (or would really like it to be), I'm hoping that you could test it out and make sure that it matches. Especially worthwhile of testing, I'd imagine, is having message/rfc822 parts in the tree. I suspect that, if anywhere, this is where differences may be.

If body part-specifier paths aren't something you care about, don't fret; the rest of the iterator API needs testing as well and if you have no interest in the iterator API at all, perhaps you'd be willing to test the S/MIME functionality (especially since I haven't figured out how to test it myself, given that I don't have an S/MIME cert nor have I figured out how to generate one or add one to my gpgsm keyring).

Your help will be greatly appreciated.

Wednesday, August 3, 2011

Debugging Your MonoTouch Apps: The Future

One of the "paper cuts" developers have been having with developing their MonoTouch 4.0.x (and earlier) applications is that for some networking setups, the IP of the developer's workstation detected by MonoDevelop and given to the iPhone or iPad device for debugging purposes is not correct. This often happens if the WiFi is a different network than the network that the developer's machine is connected to (although there are other scenarios as well).

Since it does not seem to be widely known about, allow me to point out that current versions of MonoTouch allow developers to modify the IP that the runtime should connect to for debugging via the iOS Settings app found on any iPhone or iPad (or Simulator). You can see a screenshot of this per-App Settings page in the screenshot to the left. Each of these fields are editable, allowing you to override the defaults filled-in by MonoDevelop.

For our upcoming 4.1 release, Rolf Kvinge and I (but mostly Rolf) have been working on improving this. Rolf has modified the code to check the value of the IP provided in the per-App Settings and if it is set to nil or "automatic", the debugger falls back to checking for a file bundled with the app called MonoTouchDebugConfiguration.txt which can list any number of IP's to try and connect to, each one being on a separate line prefixed with "IP: ". For example:

IP: 10.0.1.31
IP: 192.168.1.31
IP: 204.11.102.79

The runtime will then attempt to connect to each of these IPs asynchronously until it establishes a connection to one of them (at which point it aborts the other waiting connections). This config file solution will hopefully help simplify things for developers a bit by allowing them to pre-configure which IPs to try for their local network configuration w/o having to manually override the iPhone debug settings on the device or simulator.

For Phase 2 of our plan for World Domination, Rolf is hard at work adding support to MonoDevelop and the runtime to allow for USB debugging which will obsolete the above functionality in future versions where the developer has a MonoDevelop which supports USB debugging. For developers stuck on an older MonoDevelop (like 2.4), the solution illustrated above requires no changes to MonoDevelop and so will be available for use.

Thursday, April 14, 2011

Moonlight on Android

For the past week, the Moonlight team has been busy porting Moonlight to Android devices and today, showed it off at Mix 11.

The video shows Moonlight running on both a Motorola Xoom tablet and a Nexus S phone.

Keep in mind that we're still in the early phases of porting and there's still a lot of work left to do before we can ship a product, but it's still exciting!

Update: For those of you reading my blog from Planet GNOME (or some other planet that doesn't show the video above), you can find it here, on YouTube.

Update: Now you can see Moonlight rendering video with 3D transforms, too!

Thursday, April 7, 2011

Optimizing Merge Sort

A number of years ago I wrote about the Merge Sort algorithm. One of the advantages of Merge Sort is that it is a stable sort, meaning that elements that compare as being equal remain in their original order after being sorted.

Well, today I had need of employing a stable sorting routine for sorting elements by a ZIndex in Moonlight. Up until today, we had been using qsort() which, while not guaranteed to be a stable sort on any platform, happens to be implemented in glibc as a stable sort except in out-of-memory conditions. Since we'd like Moonlight to work on platforms other than Linux+glibc (such as Mac OS or BSD), it has become important enough to implement properly.

To start, I dusted off my generic MergeSort() implementation from years ago when I was writing articles about various sorting algorithms. This is what I had to start with:

#define MID(lo, hi) (lo + ((hi - lo) >> 1))

static void
msort (void *array, void *buf, size_t low, size_t high, size_t size,
       int (* compare) (const void *, const void *))
{
    register char *lo, *hi, *b;
    char *al, *am, *ah;
    size_t mid;
    
    mid = MID (low, high);
    
    if (mid + 1 < high)
        msort (array, buf, mid + 1, high, size, compare);
    
    if (mid > low)
        msort (array, buf, low, mid, size, compare);
    
    ah = ((char *) array) + ((high + 1) * size);
    am = ((char *) array) + ((mid + 1) * size);
    al = ((char *) array) + (low * size);
    
    b = (char *) buf;
    lo = al;
    hi = am;
    
    while (lo < am && hi < ah) {
        if (compare (lo, hi) <= 0) {
            memcpy (b, lo, size);
            lo += size;
        } else {
            memcpy (b, hi, size);
            hi += size;
        }
        
        b += size;
    }
    
    if (lo < am)
        memcpy (b, lo, am - lo);
    else if (hi < ah)
        memcpy (b, hi, (ah + size) - hi);
    
    memcpy (al, buf, ah - al);
}

int
MergeSort (void *base, size_t nmemb, size_t size,
           int (* compare) (const void *, const void *))
{
    void *tmp;
    
    if (nmemb < 2)
        return 0;
    
    if (!(tmp = malloc (nmemb * size))) {
        errno = ENOMEM;
        return -1;
    }
    
    msort (base, tmp, 0, nmemb - 1, size, compare);
    
    free (tmp);
    
    return 0;
}

Since performance is very important, I clocked this implementation against qsort() and got the following results on my Intel Core2 Quad Q6600 2.4 GHz machine using arrays of 10 million ints:

  • Randomized input: 14.13s vs qsort()'s 6.77s
  • Sorted input: 4.41s vs qsort()'s 1.54s
  • Reversed input: 4.26s vs qsort()'s 1.90s

Clearly the above MergeSort() implementation did not fare well against glibc's qsort() on my system, so it was time to look at what I could do to improve the performance.

The most obvious optimization I could see was to try and batch my memcpy() calls. In other words, instead of calling memcpy() to copy each and every element into our temporary buffer, it'd be more efficient to copy blocks of elements at a time:

static void
msort (void *array, void *buf, size_t low, size_t high, size_t size,
       int (* compare) (const void *, const void *))
{
    char *al, *am, *ah, *ls, *hs, *lo, *hi, *b;
    size_t mid;
    
    mid = MID (low, high);
    
    if (mid + 1 < high)
        msort (array, buf, mid + 1, high, size, compare);
    
    if (mid > low)
        msort (array, buf, low, mid, size, compare);
    
    ah = ((char *) array) + ((high + 1) * size);
    am = ((char *) array) + ((mid + 1) * size);
    al = ((char *) array) + (low * size);
    
    b = (char *) buf;
    lo = al;
    hi = am;
    
    do {
        ls = lo;
        hs = hi;
        
        if (lo > al || hi > am) {
            /* our last loop already compared lo & hi and found lo <= hi */
            lo += size;
        }
        
        while (lo < am && compare (lo, hi) <= 0)
            lo += size;
 
        if (lo > ls) {
            memcpy (b, ls, lo - ls);
            b += (lo - ls);
        }
 
        if (lo < am) {
            /* our last compare tells us hi < lo */
            hi += size;
            
            while (hi < ah && compare (hi, lo) < 0)
                hi += size;
            
            memcpy (b, hs, hi - hs);
            b += (hi - hs);
        }
    } while (lo < am && hi < ah);
    
    if (lo < am)
        memcpy (b, lo, am - lo);
    else if (hi < ah)
        memcpy (b, hi, ah - hi);
    
    memcpy (al, buf, ah - al);
}

The results were promising. For the exact same inputs (including the exact same random array), we now get:

  • Randomized input: 10.45s
  • Sorted input: 2.08s
  • Reversed input: 2.03s

The only other way that we can reduce the number of memcpy() calls we make is to avoid copying leading and trailing elements into our temporary buffer if it's not necessary to merge them. Here's the solution I came up with:

static void
msort (void *array, void *buf, size_t low, size_t high, size_t size,
       int (* compare) (const void *, const void *))
{
    char *a1, *al, *am, *ah, *ls, *hs, *lo, *hi, *b;
    size_t copied = 0;
    size_t mid;
    
    mid = MID (low, high);
    
    if (mid + 1 < high)
        msort (array, buf, mid + 1, high, size, compare);
    
    if (mid > low)
        msort (array, buf, low, mid, size, compare);
    
    ah = ((char *) array) + ((high + 1) * size);
    am = ((char *) array) + ((mid + 1) * size);
    a1 = al = ((char *) array) + (low * size);
    
    b = (char *) buf;
    lo = al;
    hi = am;
    
    do {
        ls = lo;
        hs = hi;
        
        if (lo > al || hi > am) {
            /* our last loop already compared lo & hi and found lo <= hi */
            lo += size;
        }
        
        while (lo < am && compare (lo, hi) <= 0)
            lo += size;
        
        if (lo < am) {
            if (copied == 0) {
                /* avoid copying the leading items */
                a1 = lo;
                ls = lo;
            }
            
            /* our last compare tells us hi < lo */
            hi += size;
            
            while (hi < ah && compare (hi, lo) < 0)
                hi += size;
            
            if (lo > ls) {
                memcpy (b, ls, lo - ls);
                copied += (lo - ls);
                b += (lo - ls);
            }
            
            memcpy (b, hs, hi - hs);
            copied += (hi - hs);
            b += (hi - hs);
        } else if (copied) {
            memcpy (b, ls, lo - ls);
            copied += (lo - ls);
            b += (lo - ls);
            
            /* copy everything we needed to re-order back into array */
            memcpy (a1, buf, copied);
            return;
        } else {
            /* everything already in order */
            return;
        }
    } while (hi < ah);
    
    if (lo < am) {
        memcpy (b, lo, am - lo);
        copied += (am - lo);
    }
    
    memcpy (a1, buf, copied);
}

Once again, reducing the amount of copying paid off:

  • Randomized input: 9.80s
  • Sorted input: 0.95s
  • Reversed input: 2.05s

Update 2011-05-18: One final optimization that can be tried is pre-calculating the optimum way to copy elements between buffers. This calculation, while not terribly expensive itself, adds up with every call to memcpy(). Let's start off by writing some handy macros:

#define COPYBY(TYPE, a, b, n) {         \
    long __n = (n) / sizeof (TYPE);     \
    register TYPE *__a = (TYPE *) (a);  \
    register TYPE *__b = (TYPE *) (b);  \
                                        \
    do {                                \
        *__a++ = *__b++;                \
    } while (--__n > 0);                \
}

#define MEMCOPY(dest, src, n) {                 \
    switch (copy_mode) {                        \
    case 1: COPYBY (long, dest, src, n); break; \
    case 2: COPYBY (int, dest, src, n); break;  \
    default: memcpy (dest, src, n);             \
    }                                           \
}

Now that these handy macros are written, we can plug them into our Merge Sort implementation:

static void
msort (void *array, void *buf, size_t low, size_t high, size_t size,
       int copy_mode, int (* compare) (const void *, const void *))
{
    char *a1, *al, *am, *ah, *ls, *hs, *lo, *hi, *b;
    size_t copied = 0;
    size_t mid;
    
    mid = MID (low, high);
    
    if (mid + 1 < high)
        msort (array, buf, mid + 1, high, size, compare);
    
    if (mid > low)
        msort (array, buf, low, mid, size, compare);
    
    ah = ((char *) array) + ((high + 1) * size);
    am = ((char *) array) + ((mid + 1) * size);
    a1 = al = ((char *) array) + (low * size);
    
    b = (char *) buf;
    lo = al;
    hi = am;
    
    do {
        ls = lo;
        hs = hi;
        
        if (lo > al || hi > am) {
            /* our last loop already compared lo & hi and found lo <= hi */
            lo += size;
        }
        
        while (lo < am && compare (lo, hi) <= 0)
            lo += size;
        
        if (lo < am) {
            if (copied == 0) {
                /* avoid copying the leading items */
                a1 = lo;
                ls = lo;
            }
            
            /* our last compare tells us hi < lo */
            hi += size;
            
            while (hi < ah && compare (hi, lo) < 0)
                hi += size;
            
            if (lo > ls) {
                MEMCOPY (b, ls, lo - ls);
                copied += (lo - ls);
                b += (lo - ls);
            }
            
            MEMCOPY (b, hs, hi - hs);
            copied += (hi - hs);
            b += (hi - hs);
        } else if (copied) {
            MEMCOPY (b, ls, lo - ls);
            copied += (lo - ls);
            b += (lo - ls);
            
            /* copy everything we needed to re-order back into array */
            MEMCOPY (a1, buf, copied);
            return;
        } else {
            /* everything already in order */
            return;
        }
    } while (hi < ah);
    
    if (lo < am) {
        MEMCOPY (b, lo, am - lo);
        copied += (am - lo);
    }
    
    MEMCOPY (a1, buf, copied);
}

int
MergeSort (void *base, size_t nmemb, size_t size,
           int (* compare) (const void *, const void *))
{
    int copy_mode;
    void *tmp;
    
    if (nmemb < 2)
        return 0;
    
    if (!(tmp = malloc (nmemb * size))) {
        errno = ENOMEM;
        return -1;
    }
    
    if ((((char *) base) - ((char *) 0)) % sizeof (long) == 0 && (size % sizeof (long)) == 0)
        copy_mode = 1;
    else if ((((char *) base) - ((char *) 0)) % sizeof (int) == 0 && (size % sizeof (int)) == 0)
        copy_mode = 2;
    else
        copy_mode = 0;
    
    msort (base, tmp, 0, nmemb - 1, size, copy_mode, compare);
    
    free (tmp);
    
    return 0;
}

This handy trick seems to have worked out rather well:

  • Randomized input: 7.79s
  • Sorted input: 0.99s
  • Reversed input: 1.69s

At this point, I can't think of any other obvious optimizations so I'm going to call it a day.

For a recap, here are the results of all 4 implementations compared side-by-side with the results from qsort():

qsort()msort() v1msort() v2msort() v3msort() v4
random:6.7714.1310.459.807.79
sorted:1.544.412.080.950.99
reversed:1.904.262.032.051.69

Sunday, April 3, 2011

Low-Fat Turkey Sausage Recipe

Just made my own home-made turkey sausage and figured I'd share my recipe with my fellow hackers.

What you'll need:

  • 1.3 lbs ground turkey (I use 93/7)
  • 1 teaspoon ground black pepper
  • 1/4 teaspoon cayenne pepper
  • 1/2 teaspoon salt
  • 1/2 teaspoon ground ginger
  • 1/2 teaspoon dried sage

Mix it all up real good and make a bunch of patties and brown in a frying pan at medium heat, over the grille, or where ever and you are done.

The result is very tasty and low fat.

Monday, January 24, 2011

Habanero Heat Chili


Habanero Heat Wave, originally uploaded by jstedfast.

Spiced up a traditional chili recipe with a handful of habanero peppers to keep me warm in this extremely cold Boston weather we've been having.

Saturday, January 22, 2011

Installing A Custom ROM on your Samsung Captivate

Like a lot of people, I'm tired of waiting for AT&T to get their acts together to release the long-awaited Froyo update for my Samsung Captivate phone.

I'm about to take matters into my own hands... but where do I begin?

Many of the forum threads out there contain the information needed to install a custom ROM, but the information is scattered about here and there which is confusing and not exactly confidence-inspiring. That's all about to change...

Step 1: Rooting Your Phone

The first step to installing a custom ROM is rooting your phone. This allows you to gain access to protected bits of your phone that you'll need in order to backup your existing data and the ability to install that custom ROM.

The easiest way to do this is to use the One-Click Root application for the Captivate, but before you can do that, first you need to download and install the Microsoft .NET Framework 4.0 and the Samsung USB drivers onto your computer.

Once you install those two pieces of software on your computer, the next step is to download the One-Click Root zip containing the easiest program I could find to root your phone for you.

Now you'll need to configure your Captivate's USB debug settings. To do this, first make sure you are at your phone's Home screen. Then tap the Menu button on the lower left-hand side of your phone and select Settings. Scroll down and tap on the Applications item. You should see a Development option. Select that and then enable the USB debugging checkbox at the top.

Now connect your Captivate phone to your computer via a USB cable.

Unzip the zip file and run the One-Click Root program. This will pop up a window with the Samsung Galaxy S logo and two buttons on the right ("One-Click Root" and "One-Click Unroot"). Click the button that says "One-Click Root".

This will cause your phone to reboot into a mode allowing you to to use your phone's volume buttons to navigate a text-mode screen of menu options up and down. Follow the directions in the blue text-mode window on your computer screen and select the reinstall packages menu item on your phone. Press the Power button to start the process.

After the process is complete, your phone will reboot again - this time it will boot you back into the normal mode that you are familiar with.

At this point, it is safe to disconnect your phone from your computer.

For an extremely helpful video to walk you through the process of rooting your phone, watch this video.

Step 2: Backing Up Your Phone

It is always a good idea to make a backup of your phone before proceeding any further, so here's how to do that:

Open the Android Marketplace application and search for and install "Titanium Backup", the free version is fine.

Once that finishes downloading, run the Titanium Backup program and tap on the Backup/Restore button at the top of the screen.

Select each of the apps you'd like to backup and click the Backup! button for each. Next, tap the Menu button, select More and then Create "update.zip"... and follow the directions on the next screen before finally clicking the button to create the update.zip file.

At this point, you'll want to copy that update.zip file along with the folder named TitaniumBackup off your phone and onto your computer. To do this, first go back to your phone's Home screen and then click Menu. Select Settings, Applications, and then USB settings (if this pops up a menu saying you'll need to disable USB debugging, just click OK). Now select Mass storage and then click Home again.

Re-connect your phone to your computer via the USB cable and then pull down the notification tray from the top of the screen on your phone.

Select the USB connected item which will pop up a dialog box with two buttons: Mount and Unmount. Select Mount. This will allow your computer to view the contents on each of your phone's internal memory drives.

On your phone's main drive, you should find a file named update.zip and a folder named TitaniumBackup. Copy them over to your computer for safe keeping.

Step 3: Install A Custom ROM

Keeping your phone connected to the computer from the previous step, download the ClockWork Recovery zip and then copy it over to your phone, renaming it to update.zip (overwriting Titanium Backup's update.zip if it is still there from Step 2).

Once you've downloaded the zip file containing your chosen custom ROM (I'll be installing the latest version of Cognition), you'll need to copy the downloaded zip over to your phone's internal memory drive.

Once you've done that, disconnect your phone from your computer and turn off your phone. Next, hold down both volume buttons and the power button at the same time. This should boot you into an Android system menu.

Select reinstall packages using the volume-down button to select it and then pressing the power button to activate. This will install ClockWork Recovery and then bring you back to a green text-mode menu screen (if it doesn't, select reboot system now, turn off your phone and try the procedure again).

Select the install zip from sdcard option using your phone's volume buttons and press the power button.

At the next green menu screen, select choose zip from sdcard.

Navigate the file system to select your ROM zip file and then press the power button.

Finally, confirm that you want to install the ROM by selecting the Yes menu option.

At this point, your phone should be installing the custom ROM that you've chosen. This will take a few minutes, so go watch some TV, update your Facebook page, or go tweet about how you're installing your custom ROM on your Captivate phone (make that a few dozen tweets, because installing will take a while).

Note: If the "Installing..." screen stays at "Finding update package..." for more than a minute or two (this always seems to happen to me), something is probably wrong. Simply pop out the battery and then boot the phone into recovery mode and try again.

Once the install is complete, you'll find yourself back at a green menu. Select +++++Go Back+++++. At the next green menu screen, select reboot system now and press the power button.

The first boot up will likely take longer than normal (Cognition's ROM gives you cool female computer voice updates explaining what it is doing), so don't be discouraged if it takes a good 5 minutes or so to boot up.

Congratulations, you've just installed your custom ROM!

Step 4: Restoring Your Applications

The first thing you'll need to do is open up the Android Market application and install Titanium Backup again (or you could connect your phone to your computer and copy the update.zip that was created by Titanium Backup program back onto your phone and reboot it into recovery mode to install the update.zip that way).

If you installed Cognition, like I did, then it will come pre-bundled with Titanium Backup so you'll have everything you need.

Launch Titanium Backup and tap Backup/Restore. Next, press your phone's Menu button and select Batch. This will bring you to a menu of actions with a "Run" button next to each one. Scroll down to Restore missing apps with data and then tap the Run button next to it, following the instructions that follow.

At this point you may need to reboot your phone in order for some of your apps to be seen by the phone (since some may need to be there at boot-up), so go ahead and do that.

You are now finished!

Tuesday, January 18, 2011

I am Disappoint: No Love for Froyo on Galaxy S

Based on an anonymous post on the XDA Developer Forums, the reason behind the lack of a Froyo update for Samsung Galaxy S phones in the US appears to be because Samsung is greedy.

The following quote is the entirety of the message as it appears on the forums for your convenience (with added emphasis by me).

Hello,

I’m going to step across the NDAs and explain the issues behind the Android Froyo update to Samsung Galaxy S phones in the United States. I think most of you have come to this realization yourself now: the withholding of the Froyo update is a largely political one, not a technological one: Froyo runs quite well on Galaxy S phones, as those of you that have run leaked updates may have noticed.

To explain the political situation, first, a primer on how phone firmware upgrades work for carriers. When a carrier decides to sell a phone, a contract is usually written between the phone manufacturer and the carrier. In this contract, the cost of updates (to the carrier) is usually outlined. Updates are usually broken into several types: critical updates, maintenance updates, and feature updates. Critical updates are those that resolve a critical bug in the phone, such as the phone overheating. Maintenance updates involve routine updates to resolve bugs and other issues reported by the carrier. Finally, feature updates add some new feature in software that wasn’t present before. Critical updates are usually free, maintenance updates have some maintenance fee associated with them, and feature updates are usually costly.

In the past, most phone updates would mainly consist of critical and maintenance updates. Carriers almost never want to incur the cost of a feature update because it is of little benefit to them, adds little to the device, and involves a lot of testing on the carrier end. Android has changed the playing field, however – since the Android Open Source Project is constantly being updated, and that information being made widely available to the public, there is pressure for the phone to be constantly updated with the latest version of Android. With most manufacturers, such as HTC, Motorola, etc. This is fine and considered a maintenance upgrade. Samsung, however, considers it a feature update, and requires carriers to pay a per device update fee for each incremental Android update.

Now, here’s where the politics come in: most U.S. carriers aren’t very happy with Samsung’s decision to charge for Android updates as feature updates, especially since they are essentially charging for the Android Open Source Project’s efforts, and the effort on Samsung’s end is rather minimal. As a result of perhaps, corporate collusion, all U.S. carriers have decided to refuse to pay for the Android 2.2 update, in hopes that the devaluation of the Galaxy S line will cause Samsung to drop their fees and give the update to the carriers. The situation has panned out differently in other parts of the world, but this is the situation in the United States.

Some of you might have noticed Verion’s Fascinate updated, but without 2.2 : This is a result of a maintenance agreement Samsung must honor combined with Verizon’s unwillingness to pay the update fees. In short, Android 2.2 is on hold for Galaxy S phones until the U.S. carriers and Samsung reach a consensus.

Some might wonder why I didn’t deliver this over a more legitimate news channel – the short answer: I don’t want to lose my job. I do, however, appreciate transparency, which is why I'm here.

Having bought a Samsung Galaxy S phone back in August with the expectation that it would get the Froyo update soon, I am disappoint.

This is just one more annoyance added to my growing list of annoyances about Android-based phones and my Galaxy S phone in particular.

Bitch and moan about Apple being evil all you want, but even Apple doesn't do this to their users. I will never ever buy another Samsung Android phone again. This really rubs me the wrong way.

Update: People have been commenting that Android devices have gotten better OS update support than iPhones. This is simply not the case. The iPhone 3G came out ~6 months before the Android G1 and the G1 stopped getting updates (latest update was Android 1.6) looooooooong before the iPhone 3G stopped getting updates. Apple at least kept providing updates to the 3G through iOS 4.1.x, latest update being this past fall. So even though the iPhone 3G is older than the G1, it got OS updates until long after updates stopped coming for the G1. My point is that to even compare the G1 to the iPhone 3G in terms of time supported by new OS upgrades, the G1 would have to at least have Android 2.2 (which came out how long ago?? I mean, even 2.3 is out now). In other words: Apple pushes all OS upgrades for their iPhones for at least 2 years (length of a contract) while no Android handset maker ever has - the G1 got OS upgrades for what? 6 months?

Code Snippet Licensing

All code posted to this blog is licensed under the MIT/X11 license unless otherwise stated in the post itself.