The "Unix philosophy" is all about small programs that do one thing well, but easily work together to accomplish complicated things. The summary I'm most familiar with is Peter H. Salus's Continue reading spawn() of Satan

# All posts by Tavian Barnes

# Cracking DHCE (Diffie-Hellman color exchange)

I recently saw a video that explains Diffie–Hellman key exchange in terms of mixing colors of paint. It's a wonderfully simple and informative analogy, that Wikipedia actually uses as well. If you don't know about Diffie-Hellman, definitely watch the video and/or read the Wikipedia page to get a handle on it—it's not that complicated once you get the "trick." The color analogy intrigued me because I know just enough about both cryptography and color theory to be dangerous. So in this post, I'm going to attack the security of the color exchange protocol. ("Real" Diffie-Hellman remains secure, as far as I know.) Continue reading Cracking DHCE (Diffie-Hellman color exchange)

# bfs from the ground up, part 3: optimization

I recently released version 1.1.3 of `bfs`

, my breadth-first drop-in replacement for the UNIX `find`

command. The major change in this release is a refactor of the optimizer, so I figured it would be a good time to write up some of the details of its implementation. Continue reading bfs from the ground up, part 3: optimization

# bfs from the ground up, part 2: parsing

Today is the release of version 1.0 of `bfs`

, a fully-compatible^{*} drop-in replacement for the UNIX `find`

command. I thought this would be a good occasion to write more about its implementation. This post will talk about how I parse the command line. Continue reading bfs from the ground up, part 2: parsing

# A quick trick for faster naïve matrix multiplication

If you need to multiply some matrices together very quickly, usually it's best to use a highly optimized library like ATLAS. But sometimes adding such a dependency isn't worth it, if you're worried about portability, code size, etc. If you just need *good* performance, rather than *the best possible* performance, it can make sense to hand-roll your own matrix multiplication function. Continue reading A quick trick for faster naïve matrix multiplication

# bfs from the ground up, part 1: traversal

`bfs`

is a tool I've been writing for about a year, with the goal of being a drop-in replacement for the UNIX `find`

command. This series of posts will be deep technical explorations of its implementation, starting from the lower levels all the way up to the user interface. `bfs`

is small (only about 3,500 lines of C code), which makes it possible to do a fairly complete analysis. But the codebase is fairly clean and highly optimized, which should make the analysis interesting. Continue reading bfs from the ground up, part 1: traversal

# The Approximating and Eliminating Search Algorithm

Nearest neighbour search is a very natural problem: given a target point and a set of candidates, find the closest candidate to the target. For points in the standard k-dimensional Euclidean space, k-d trees and related data structures offer a good solution. But we're not always so lucky.

Continue reading The Approximating and Eliminating Search Algorithm

# Java autoboxing performance

In Java, primitives (`int`

, `double`

, `char`

) are not `Object`

s. But since a lot of Java code requires `Object`

s, the language provides *boxed* versions of all primitive types (`Integer`

, `Double`

, `Character`

). Autoboxing allows you to write code like

# Fast, Branchless Ray/Bounding Box Intersections, Part 2: NaNs

In part 1, I outlined an algorithm for computing intersections between rays and axis-aligned bounding boxes. The idea to eliminate branches by relying on IEEE 754 floating point properties goes back to Brian Smits in [1], and the implementation was fleshed out by Amy Williams. et al. in [2].

Continue reading Fast, Branchless Ray/Bounding Box Intersections, Part 2: NaNs

# Efficient Integer Exponentiation in C

It's surprisingly difficult to find a good code snippet for this on Google, so here's an efficient computation of integer powers in C, using binary exponentiation: