A brief history of the popcnt instruction

[sje]

A brief history of the popcnt instruction:

The first instance of a "count bits" CPU instruction dates back to the 1960s and the Control Data Corporation, the makers of the CDC line of mainframe computers. According to a long since declassified report, the US National Security Agency went to Seymour Cray (then the lead designer at CDC) and asked for a bit count CPU instruction that could be used on the planned CDC 6000 series computers which had 60 bit long words. (These machines were the ones used by the Chess 4.x team with their bitboard program.)

Considering that the government was the main customer of CDC mainframes, Cray was happy to comply. But why did the NSA need a bit count instruction? Were they secretly writing chess programs? What was the instruction anyway?

The actual instruction was "CXi Xj" and in meant "count the number of 1 bits in 60 bit register Xj [j: 0-7] and put the result in register Xi [i: 0-7]". In the low end CDC mainframes, a small auxiliary circuit was tacked on to the floating point divide functional unit. (There was no integer divider.) For the better models, like the ones the government bought, an entire dedicated bit counter was connected to the CPU. This was all done back in the days of rackmounted machines when a CPU needed a tractor trailer for delivery.

The NSA needed the CXi opcode to generate a text line hash for intercepted messages, perhaps mostly cables that were line formatted. For each character in a given line of text, a routine would set a bit in a word with the bit position based on the character code. The 60 bit words of the machine would handle any major alphabet. After each line had been read, the CXi instruction would be executed on the produced word to give a count of distinct characters or the input text line. This count was used as a hash that in turn was used for text matching among messages and perhaps cryptanalysis as well.

Some time after that, similar one-line hashes were used in programs like the Unix "diff" utility to quickly match blocks of text lines. But the government did it first.