In the mid 1990’s I was shown a snippet of C source code which remains what I consider to be the most beautiful code I have ever seen. The code was introduced to me as:<\/p>\n
It’s a devastatingly deviously unrolled byte-copying loop, devised by Tom Duff while he was at Lucasfilm. In it’s “classic” form, it looks like:<\/p><\/blockquote>\n
<\/p>\n
register n = (count + 7) \/ 8; \/* count > 0 assumed *\/\r\nswitch (count % 8) {\r\n case 0: do { *to = *from++;\r\n case 7: *to = *from++;\r\n case 6: *to = *from++;\r\n case 5: *to = *from++;\r\n case 4: *to = *from++;\r\n case 3: *to = *from++;\r\n case 2: *to = *from++;\r\n case 1: *to = *from++;\r\n } while (--n > 0);\r\n}<\/pre>\nThe code is described elsewhere on the internet as Duff’s Device<\/a>.<\/p>\n
The code implements an 8 ways unrolled loop which copies a block of data to a single memory address which is likely to be a port address. Typically, unrolled loops do cleanup after the main body of the loop has executed. This code uses the fall-through behaviour of C’s switch statement to do the cleanup on the way into the loop which makes the code more compact.<\/p>\n
switch(count % 8) {<\/pre>\nC’s post increment operator is used to identify the address of the source data for copying and then advances the next address after the copy. This is done in one expression.<\/p>\n
*from++;<\/pre>\nThe number of times needed through the body of the loop is calculated once before entering the loop.<\/p>\n
register n = (count + 7) \/ 8; \/* count > 0 assumed *\/<\/pre>\nAnd using C’s pre decrement operator, decrements and tests the count each time through the loop.<\/p>\n
while (--n > 0);<\/pre>\nGiven the tight coupling between C and the hardware that it is compiled to run on, this code should be amazingly fast on most architectures.<\/p>\n
I tip my hat to Tom Duff for his beautiful, and fast, code to copy data.<\/p>\n","protected":false},"excerpt":{"rendered":"
In the mid 1990’s I was shown a snippet of C source code which remains what I consider to be the most beautiful code I have ever seen. The code was introduced to me as: It’s a devastatingly deviously unrolled … Continue reading