Charles Hbfs writes about algorithms, data encoding, bit tricks, dithering, and low-level programming topics.
Commenters cite it for specific pieces, such as pairing functions with good locality, the boiling-the-oceans quip, dithering, and fixed-point line drawing.
> filling out a 64 bit address space looks tough. I struggled to find something of the same magnitude of 2^64 and I got ‘number of iron atoms in an iron filing’
Reminded me of Jeff Bonwick's answer to the following question about his 'boiling the oceans' quip related to ZFS being a "128 bit filesystem":
> 64 bits would have been plenty ... but then you can't talk out of your ass about boiling oceans then, can you?
Sadly his Sun hosted blog was eaten by the migration to Oracle, so thanks to the Internet Archive again:
http://web.archive.org/web/20061111054630/http://blogs.sun.com/bonwick/date/20040925
That one dives into some of the "handwaving" a bit:
https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/
And that one goes into how much energy it would take to merely spin enough disks up:
https://www.reddit.com/r/DataHoarder/comments/71p8x4/reaching_the_limit_from_zfs/
The author of this post is oblivious to fractional bit encodings. When encoding an array of items, you can always encode the array optimally, only wasting less than 1 bit.
For example, if we had an array of n test scores from 1-100, we only need ceil(n*log2(100)) bits.
The key is that when reading the values, instead of shifting like we would normally to iterate an array, we instead divide by 100. Instead of masking bits, we get the current value by doing mod 100. Its equivalent to shifting/masking for a power of 2, but extends packing to fractional bits. It's quite beautiful.
Take a look at this blog post to understand more about fractional bit representations:
https://hbfs.wordpress.com/2011/11/01/fractional-bits-part-i/
I found this part of the code quite funny:
# If there are < 5 items, just return the median if len(l) < 5: # In this case, we fall back on the first median function we wrote. # Since we only run this on a list of 5 or fewer items, it doesn't # depend on the length of the input and can be considered constant # time. return nlogn_median(l) Hell, why not just use 2^140 instead of 5 as the cut-off point, then? This way you'd have constant time median finding for all arrays that can be represented in any real-world computer! :) [1]
[1] According to https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/
I had one as kid and picked up one a few years ago. Would have been interesting to see what TI could have done in early computer market if they hadn't crippled the machine (intentionally or not) and not fought third party development.
A game that might interest some here is Tunnels of Doom
http://www.ridingthecrest.com/edburns/classic-gaming/tunnels/
https://hbfs.wordpress.com/2008/12/16/tunnels-of-doom/
I can't find it right now but there was a lovely article on old ways and new ways to dither.
other articles:
- https://news.ycombinator.com/item?id=11886318
- https://www.cs.princeton.edu/courses/archive/fall00/cs426/lectures/dither/dither.pdf
- https://hbfs.wordpress.com/2013/12/31/dithering/#more-4980
Great work, it's always nice to see more Asm projects!
"Bare Metal" - does this mean the RPi can run blob-free?
A possible improvement I suggest is to gfx_draw_line in gfx.s - using a fixed-point algorithm could be simpler and faster: http://hbfs.wordpress.com/2009/07/28/faster-than-bresenhams-algorithm/