Wouldn't a minimalist implementation just look up shortened URLs in a map and spit out a redirect to the original URL? Seems like that could be done in a few KiB.
TBH, You can pretty much do a single PHP file, with no dependencies, and without mod_rewrite. Just site.com/?fDS- for example, and it redirects. Storage can be MySQL or some other DB or even a flat file with locking.