PDP-8: count number of set bits in a word

[Paul Koning]

> On Apr 5, 2019, at 4:49 PM, Randy Dawson via cctalk <cctalk at classiccmp.org> wrote:
> 
> Hi Kyle,
> 
> hat's a really interesting problem, and the government (NSA) wanted this badly and done FAST.
> 
> they asked Seymour Cray to create a specific instruction for this and they called it 'population count'
> 
> Anybody know the why and how it is useful?
> 
> I am deep in matrix math books and 'classification algorithms' in statistics math, looking into electronics reliability WCCA, so this is an interesting topic.

I don't know how it was used in crypto, but I know of another application: the PLATO system uses it for fuzzy matches of text input.  The idea is to split the strings (user input and expected input) into tokens, then xor each token and do a population count on that.  "close" is defined as count < some threshold.  There may be more encoding in there, i.e., it's not necessarily an xor of the straight text, but that's the basic idea.

The implementation matches the "lookup table" technique, but with a fair amount of hardware thrown at it.  The 60-bit word is split into 15 4-bit pieces.  Each 4-bit piece is run through a logic block to generate a 3 bit count, then those counts are summed by a tree of adders to yield the final 6 bit result.  It's pretty compact, about 60 modules (where each module has about 30-50 transistors on it) and takes 800 ns (8 cycles, it's a 10 MHz machine) for the whole instruction, the actual count process is about half that.

	paul