What can you do in 2k LOC of C?

http://www.h4ck3r.net/2011/02/02/what-can-you-do-in-2k-of-c/

by s3graham • 15 years ago

156 109 15 years ago

mayank• 15 years ago

I wrote EasyEXIF: http://code.google.com/p/easyexif/

About 120 lines of C++ [see 1] that parses basic EXIF information out of a JPEG image. I found all the other EXIF parsing tools and libraries a little too heavyweight for something as simple as getting the date and time a picture was taken, or the f/stop or exposure time. It only uses string.h for memcpy and memset, and no other headers.

[1] http://code.google.com/p/easyexif/source/browse/trunk/exif.c... (note: Google's source view screws up my whitespace)

silentbicycle20• 15 years ago

I'm working on a text indexing/retrieval program, like locate (http://www.openbsd.org/cgi-bin/man.cgi?query=locate) but for content and not just filenames, and with an index <=2% the size of the indexed data.

It's very nearly together (integrating individually working parts now), and is currently ~1,500 lines (according to sloccount).

Adding support for indexing Unicode text, more configuration, composite search queries (A and B near C and not D), etc. will no doubt make the source expand a bit, but it's still pretty small.

If you're interested in trying it out once it's ready, contact info is in my profile. I'm shooting for within a week or two for a beta vulgaris. (Requires Unix. ANSI C, strung together with sh and/or awk to avoid dependencies.)

ajays• 15 years ago

Does the index include the dictionary too, in your calculation? I'd be interested in seeing this indexing/retrieval program of yours, I hope you release it soon!

silentbicycle20• 15 years ago

Yes.

whakojacko• 15 years ago

Anyone know how big nginx is? I wouldnt at all be surprised if its under 2k LOC.

maximilianburke• 15 years ago

As of 0.9.4, the core module is almost 21,000 lines of code and the entire nginx source tree is about 118,000 lines.

silentbicycle20• 15 years ago

You're probably joking, but sloccount says:

    ansic:        82714 (99.68%)
    perl:           124 (0.15%)
    sh:              78 (0.09%)
    asm:             48 (0.06%)
    cpp:             17 (0.02%)

(for nginx-0.8.53)

silentbicycle20• 15 years ago

Why have I gotten 13 upvotes for this? Serious question.

abecedarius6• 15 years ago

I was tempted to show off some toys I feel fatherly pride for, like my 500-line spreadsheet, but the only C program in this size range that I still use much is http://wry.me/~darius/software/req.tar.gz -- a rewrite-rule-based programmable calculator. Since it's >20 years old it's not at all what I'd write now.

(Toy spreadsheet at https://github.com/darius/vicissicalc)

sliverstorm2• 15 years ago

If you think about it for a second, you realize that TrueType rasterization can't be that hard because printers were doing it long ago on crappy little embedded processors, but the default is just to fall back on the big ugly library, and then wrap it and pretend it's not there. How about instead, just write some good code?

This is why 'modern' software can still manage to bring a 3GHz quad-core to it's knees, IMHO

sliverstorm2• 15 years ago

I personally suspect the explosion of storage space is the biggest factor in all this. I was just writing software for a uC with 2kb program space last week, and I started to bump into the limit. Optimizing my code for size actually resulted in much better code, because I had to stop and think "How can I do this... smarter?"

(Though if you're trying to fit 8kb into 2kb and have to start doing voodoo, it's true the quality will suffer)

radu_floricica• 15 years ago

Current software (compiled code) would usually fit perfectly in the 20Mb hard drives I was using 20 years ago. The extra space is taken by various data files. I don't think I ever cared about compiled size with PC software, even when working with 360kb floppies.

cdavid2• 15 years ago

This is also why we have many more softwares available now.

The improvement in hardware specs are so useful not only because it is faster, but also because we can do much more without having to care about the details. Writing tiny, efficient libraries is cool, but it takes a lot of time, everything else being equal, so if you can afford not doing it, you don't.

gnaritas2• 15 years ago

> This is also why we have many more softwares available now.

Assuming English isn't your first language, that would be phrased "much more software"; software is always singular.

pygy_• 15 years ago

Roberto Ierusalimschy's lpeg is around 2.4k loc of ansi C without any dependency beside libC and lua.h (needed to interface with Lua, since it's a Lua library).

It implements an efficient pattern matching system based on Parsing Expression Grammars (akin to CFGs, but without ambiguities). It consists of a Pattern/Grammar to bytecode compiler and a custom VM to interpret the result of the compiling phase.

Nice and clean.

http://www.inf.puc-rio.br/~roberto/lpeg/lpeg.html

http://en.wikipedia.org/wiki/Parsing_expression_grammar

silentbicycle20• 15 years ago

The Lua code itself (while not <2 kloc) is also clean, well designed C, and definitely worth study. It gets quite a bit of functionality out of 12.6 kloc, and if you work with C, Lua is an ally (it's like Tcl, but good). :)

Also, in my experience, LPEG is a great fit for middle-ground parsing - more complex than Perlish regexps (which it handles well), and including those a bit more complex still, but it's awkward for really complex parsing (since it inherently combines lexing and parsing).

But I dissed Perl and Tcl, so -1. Screw useful information. ;)

beagle33• 15 years ago

> but it's awkward for really complex parsing (since it inherently combines lexing and parsing).

I'm kind of surprised by that statement - grammars for programming languages expressed in PEG always seem much cleaner to me than the lex/parse separation. Can you give an example of a grammar that you find is complicated by PEG?

haberman4• 15 years ago

The core of my protobuf-decoding library upb (https://github.com/haberman/upb/wiki) is 3k SLOC of C. That includes

  * a hash table implementation
  * a reference-counted string type
  * a generic interface for doing tree traversals of protobuf data
  * the protobuf decoder itself (which implements the previous interface)
  * all the code to load proto descriptors (including bootstrapping the first one,
    which is necessary to load others)

silentbicycle20• 15 years ago

It really says something about C that so many useful-but-small systems have a good chunk of code devoted to hash table implementations, atoms ("a reference-counted string type"), etc.

When working with C, it sometimes makes sense to have bespoke data structures, but it always makes me think of Hanson's _C Interfaces and Implementations_, Greenspun's tenth rule, etc.

My 1500loc C project also has a hash table implementation (and, soon, dynamic arrays (gasp!)). That and serializing custom data structures to disk accounts for more than half of its code. It's fast as hell, but I originally prototyped it in like 100 lines of Lua.

barrkel• 15 years ago

Sadly, I've written many hash-table implementations that are only ever used once, in a function. The hash table is just a local array, and the structures I work with generally already have a next pointer available for simplistic chaining.

Minimal hashtable implementation: an array declaration, a memset call, and a template search loop which either uses pointers or locations (pointers to 'next' pointers), depending on whether you need to look up the item, or potentially remove it. Roughly 2+n lines for n hash operations.

beagle33• 15 years ago

> It really says something about C that so many useful-but-small systems have a good chunk of code devoted to hash table implementations, atoms ("a reference-counted string type"), etc.

Well, the only reason for that is that C never had a hash table in its standard library. The same assertion is true about any other programming language I've seen that doesn't.

Python's and Lua's dicts are really hard to top (at least in the general case, and definitely inside the language), so there aren't even any attempts. Java's is slow and horrible, so there are hundreds of replacements, but they're all interface compatible.

> That and serializing custom data structures to disk accounts for more than half of its code.

That's one of the the things K gets unbelievably right - there is one routine (which with Arthur's style is probably 10 lines of C) for serialize, and another for deserialize. They work for any K structure, and they do that with blinding speed thanks to being totally memory mapped. My C code has switched to that approach as well - and it works really, really well.

haberman4• 15 years ago

> It really says something about C that so many useful-but-small systems have a good chunk of code devoted to hash table implementations

For this speed-obsessed project, I wouldn't have it any other way:

  Benchmarking hash lookups in an integer-keyed hash table.

  Table size: 8, keys: 1-8 ====
  upb_inttable(seq): 410 M/s
  upb_inttable(rand): 334 M/s
  std::map<int32_t, int32_t>(seq): 149 M/s
  std::map<int32_t, int32_t>(rand): 170 M/s
  __gnu_cxx::hash_map<uint32_t, uint32_t>(seq): 69.9 M/s
  __gnu_cxx::hash_map<uint32_t, uint32_t>(rand): 68.0 M/s

  Table size: 64, keys: 1-64 ====
  upb_inttable(seq): 410 M/s
  upb_inttable(rand): 333 M/s
  std::map<int32_t, int32_t>(seq): 32.4 M/s
  std::map<int32_t, int32_t>(rand): 33.4 M/s
  __gnu_cxx::hash_map<uint32_t, uint32_t>(seq): 67.9 M/s
  __gnu_cxx::hash_map<uint32_t, uint32_t>(rand): 71.4 M/s

  Table size: 512, keys: 1-512 ====
  upb_inttable(seq): 407 M/s
  upb_inttable(rand): 330 M/s
  std::map<int32_t, int32_t>(seq): 20.8 M/s
  std::map<int32_t, int32_t>(rand): 17.2 M/s
  __gnu_cxx::hash_map<uint32_t, uint32_t>(seq): 70.8 M/s
  __gnu_cxx::hash_map<uint32_t, uint32_t>(rand): 64.6 M/s

  Table size: 64, keys: 1-32 and 10133-10164 ====
  upb_inttable(seq): 394 M/s
  upb_inttable(rand): 334 M/s
  std::map<int32_t, int32_t>(seq): 32.0 M/s
  std::map<int32_t, int32_t>(rand): 30.7 M/s
  __gnu_cxx::hash_map<uint32_t, uint32_t>(seq): 71.3 M/s
  __gnu_cxx::hash_map<uint32_t, uint32_t>(rand): 70.6 M/s

Zev• 15 years ago

An JSON / XML / YAML parser?

The fastest JSON parser that I know of is implemented in ~1800 lines of Objective-C: https://github.com/johnezang/JSONKit. Its about 2-3x faster than the yajl bindings for Objective-C are, in my testing.

zephjc• 15 years ago

Write a basic Lisp interpreter/compiler and write everything else in Lisp? :)

Would compiling Lisp code count against the challenge's LOC limit?

abecedarius6• 15 years ago

I did once write a 2k-line bytecode interpreter and runtime for R4RS Scheme -- the compiler, library, and debugger were another 2-3kloc of Scheme. I even used it as my main hacking platform for years. But I didn't post it here because:

* It depends on the Boehm garbage collector.

* (This is embarrassing.) It stopped working after some version bump of GCC, and the cause is not at all obvious to me. Since I don't Scheme much anymore I gave up.

http://wry.me/~darius/software/uts.tar.gz if anyone cares.

silentbicycle20• 15 years ago

No blame, but I'm curious "why you don't Scheme much anymore". Was it due to Python, Common Lisp, etc?

I switched from (Chicken) Scheme to Common Lisp (and, in parallel, from Python to Lua), and, having read a lot of old code of yours, I'm curious about your choices - you seem consistently sensible and pragmatic. (Sorry to put you on the spot.)

joe_the_user• 15 years ago

The next question is:

How many of these 2K sections can you string together to make something of further use? (using another 2k section, of course)

js2• 15 years ago

  $ git show e83c5163316f89bfbde7d9ab23ca2e25604af290 --stat
  commit e83c5163316f89bfbde7d9ab23ca2e25604af290
  Author: Linus Torvalds <torvalds@ppc970.osdl.org>
  Date:   Thu Apr 7 15:13:13 2005 -0700

    Initial revision of "git", the information manager from hell

   Makefile       |   40 +++++++++
   README         |  168 ++++++++++++++++++++++++++++++++++++
   cache.h        |   93 ++++++++++++++++++++
   cat-file.c     |   23 +++++
   commit-tree.c  |  172 +++++++++++++++++++++++++++++++++++++
   init-db.c      |   51 +++++++++++
   read-cache.c   |  259 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   read-tree.c    |   43 +++++++++
   show-diff.c    |   81 ++++++++++++++++++
   update-cache.c |  248 +++++++++++++++++++++++++++++++++++++++++++++++++++++
   write-tree.c   |   66 ++++++++++++++
   11 files changed, 1244 insertions(+), 0 deletions(-)

:-)

bdonlan• 15 years ago

To be fair, that's 1244 _lines_, not bytes :)

kevinherron• 15 years ago

So is what the OP is talking about :o (lines vs. bytes)

s3graham3• 15 years ago

Ah, that's a good one, and worth study at that revision with so few lines. Thanks!

pnathan2• 15 years ago

I wrote an cooperative multitasking RTOS for an ATMega processor in 1200 or so lines.

jpd• 15 years ago

If you're willing to share the code, I'm sure many of us would love to see it.

pnathan2• 15 years ago

Here you go!

https://bitbucket.org/pnathan/uirtos

Turned out it was a preemptive RTOS. I had forgotten that.

HeyLaughingBoy• 15 years ago

I wrote a preemptive multitasking one for an AVR in about the same amount of code :-)

derleth• 15 years ago

How much memory does the code the blog poster described leak? How does it respond to edge cases and invalid input? Finally, is it portable beyond one specific OS? Beyond POSIX or Windows-based systems?

Those questions are especially pertinent in C.

jbri• 15 years ago

The only dependencies are the C standard libraries (this is even mentioned in the blog post). So unless there's some terrible hackery going on (and skimming the source files, it doesn't look like there is), these are going to be more portable than most of the mega-libs you'd be choosing instead.

What makes you so incredulous about this?

s3graham3• 15 years ago

Mine or stb_*? I know stb_image is quite careful not to leak. It may not handle all perverse input files gracefully though.

As for twok, I believe the error handling to be decent and I don't believe it leaks. I'd be happy to hear of any errors you find. It's only portable to Windows, OS X, and Linux because that's all I have access to. It may work on BSD also.

JoeAltmaier2• 15 years ago

Right! Coming up with standalone C means coming up with your own versions of hard-to-write simple "system calls" like memove.

I debugged a memcopy (taken from Linux! 10 years ago) on a RISC processor - it had 12 bugs in a dozen lines of code. Not designed to run on RISC but shows how hard it can be to get this stuff right.

sigil2• 15 years ago

> simple "system calls" like memove

Minor, pet-peevy point: memmove(3) and memcpy(3) are not system calls. (http://en.wikipedia.org/wiki/System_call)

jerf2• 15 years ago

Getting a standards-compliant XML parser into 2K lines is going to be a challenge, if you're not going to cheat on what a "line" is. You must be able to deal with both UTF-8 and UTF-16 [1] (and remember UTF-16 can be in either endian order), you have several tables of things like what chars are valid where, you've got data structures to declare, and there's a lot of edge cases that may not leap to mind but if you don't cover them you don't really have an XML parser, like CDATA handling, entity loading from a DTD, parsing DTDs at least well enough to get those entities, processor commands, etc. A useful subset certainly, something I'd actually call a real XML parser, I'm skeptical. Not quite ready to write the idea off, but skeptical. (It's saved from me writing if off entirely because if I read the spec correctly a parser is not required to resolve external DTD references, if it was it would be stick-a-fork-in-it done, you'd eat hundreds of lines just using raw sockets to do HTTP requests and manage them even halfway properly.)

A JSON parser? Heck yes, even with the UTF-8 handling. It wouldn't even necessarily suck.

[1] http://www.w3.org/TR/REC-xml/#charsets

tzs• 15 years ago

> Getting a standards-compliant XML parser into 2K lines is going to be a challenge

This is a pretty good argument against XML.

arethuza• 15 years ago

I would say its an argument for using JSON in situations where you need stuff to be small, fast and simple and XML in situations where you need it (where you want to do a queries easily over the document structure, which XPath is fairly decent at, interop with systems that insist on XML and things that are more document-ish rather than data-ish.

jerf2• 15 years ago

Yes, that point may have had some influence on the way I phrased my post.

s3graham3• 15 years ago

Sounds like a challenge (to someone ;) A good XML test suite to confirm "fullness" must exist?

johne2• 15 years ago

A JSON parser at ~2K lines: https://github.com/johnezang/JSONKit I'm the author, so I'm obviously biased :). It has strict Unicode standard UTF-8 parsing ("passes" http://www.cl.cam.ac.uk/~mgk25/ucs/examples/UTF-8-test.txt) and has a whiz-bang LRU cache with a clever aging replacement policy that saves lots of time by reusing already seen and instantiated immutable objects (think JSON dictionaries: the keys in "key": value pairs tend to repeat an awful lot). A further benefit is this saves lots of memory too. For converting JSON to 'native' ObjC/Foundation objects, it's faster than the other ObjC JSON libraries by 2-10x (HEAVILY dependent on the JSON being parsed, typical is 2-4x), and serializing ObjC -> JSON is (usually) even faster.

So, in short, it's possible to write a very high performance JSON serializer and deserializer in ObjC in ~2K lines of code. For JSONKit, most it is actually pure C (which in turn uses Core Foundation, which is a pure C API interface version for the equivalent native ObjC objects), with public API ObjC stub bindings making use of the C code.

kurige• 15 years ago

A JSON parser (of sorts) in roughly 150 lines of C code. I'm not the author.

https://github.com/quartzjer/js0n

drobilla• 15 years ago

I recently wrote a Turtle[1] parser and abbreviating serialiser[2] in just over 2K lines, which I'd say is roughly equivalent in complexity to doing the same for JSON. This is with UTF-8 support, full conformance, URI parsing/resolution, line/column error reporting, etc. A more kludgy job could be quite a bit smaller still...

[1] http://www.w3.org/TeamSubmission/turtle/ [2]: http://drobilla.net/software/serd/

sofuture3• 15 years ago

Shocked that silentbicycle hasn't mentioned it already, but Arthur Whitney whipped up the first prototype/inspiration for the J language in a short bit of macro heavy C over the course of an afternoon.

42 lines?

http://pastebin.com/s2usuqDq

If this interests you at all, absolutely worth reading Roger Hui's retrospective on the subject (more about J + Ken Iverson, but definitely fascinating) http://keiapl.org/rhui/

ehsanul6• 15 years ago

That's interesting, but damn is that some ugly code. Slightly obfuscated on purpose? Though of course it wouldn't win the IOCCC.

On the other hand, it's notable that many IOCCC submissions happen to pack a lot of functionality in often less than 2k. I remember reading a few descriptions of some the winning entries, but I can't find that now. Here's a glimpse though: http://cboard.cprogramming.com/brief-history-cprogramming-co...

ehsanul6• 15 years ago

Nevermind the comment about it being slightly obfuscated. Have to realize that this is the creator of J we're talking about. He probably saw it as highly expressive code (much meaning in as few characters as possible). Though I can't agree, it is definitely amazing that something so small could be the start of something like J.

silentbicycle20• 15 years ago

Having spent a lot of time meditating on it (as sofuture mentioned), it isn't "slightly obfuscated" so much as "stubbornly written like APL rather than C".

If you become inexplicably fascinated by that code and want help unraveling it, my contact info is in my profile.

I don't consider it noteworthy as a useful program under 2kloc (on modern hardware it usually just crashes, it's quite cavalier with pointer casting, and clearly a quick prototype either way), but it's like a pink space laser beam of insight about the APL mindset. Real APLs take more than a page, but not that much more. Eliding loops does that.

A lot of the IOCCC code is also delightfully perverse, too. Highly recommended.

EliRivers2• 15 years ago

"That's interesting, but damn is that some ugly code"

I would disagree. That code is beautiful. Elegance and brevity; it's as close to a pure expression of the coder's thoughts as it's reasonably possible to get.

jpr2• 15 years ago

> http://pastebin.com/s2usuqDq

I'm going to save this for the next time someone asks why there aren't more females in CS/programming. I just tell them that this kind of code is held in high esteem, instead of being ridiculed for the stupidity that it is.

aisi• 15 years ago

And how is that at all related to female numbers in CS/programming?

EliRivers2• 15 years ago

Are you saying that women can't appreciate elegance and brevity? Perhaps your kind of attitude is why there aren't more females in programming.

ehsanul6• 15 years ago

On a related note, reading J's getting started guide has been pretty interesting so far: http://www.jsoftware.com/help/primer/contents.htm

sigil2• 15 years ago

How about micro_httpd, an inetd-style HTTP/1.0 server in 200 lines of C. (http://acme.com/software/micro_httpd/)

nostrademons3• 15 years ago

In 2000 lines of C, you can encode the HTML5 "named character character entity" table.

http://dev.w3.org/html5/spec/Overview.html#named-character-r...

I hate HTML.

johne2• 15 years ago

O.. M.. F.. G.. I had no idea they did this. I mean, what is the point? Talk about "not invented here" mentality: "I've got a fantastic idea! Unicode already has an official name for every Unicode character, so let's throw all of that out and come up with our own names that have no relation to what those Unicode guys did! And while we're at it, HTML4, HTML5? Version numbers are for pu$$7$s, so lets drop that too, and then randomly throw in a few hundred extra character entities every two to eighteen months for a fresh 'What's new' bullet point!"

nostrademons3• 15 years ago

It's for backwards compatibility, like most of the HTML5 spec. If browsers suddenly start becoming HTML5-compliant and as a result most of the web stops working, then they've failed.

I agree with the reasoning. But damn, it makes things suck going forwards. This is why we can't have nice things. :-(

just-a-c-hacker• 15 years ago

How about an X11 tiling window manager? http://dwm.suckless.org/

limmeau2• 15 years ago

Fabrice Bellard's IOCCC entry of 2002 was a C-subset compiler in 617 wc-lines (ELF version).

http://bellard.org/otcc/

beagle33• 15 years ago

It's an amazing piece of work: Those 617 lines are in its own C subset, so it can compile itself into a native code ELF version.

This evolved into bellard's "tcc" compiler, which is the fastest (compile-time wise) available on linux, the only one I'm aware of that can be used as a library to run code in memory (without having to generate an .so and load that). And it's output performance, while lacking compared to -O3 gcc or clang - is not too shabby!

grammaton• 15 years ago

Back in The Day (tm) I wrote a full Gnutella client in about 1600 lines of code.

What can you do in 2k LOC of C?

Related Stories