Hacker News Reader

Men in black always want popcount (it's been added to various architectures over the years at their request) so this makes sense given his background.

>Men in black always want popcount (it's been added to various architectures over the years at their request)

I've heard this a few times, do you have anything that explains this?

It is said that NSA has requested the addition of POPCNT to the Control Data Corporation CDC 6600 (1964), as a condition for procurement.

The condition has remained in force later, so all its successors, like CDC 7600 (1969) or Cray-1 (1976), have included POPCNT.

POPCNT has been added to the x86 ISA by AMD, in "Barcelona", in 2007, presumably because some customer for AMD Opteron has requested it. This happened during the period when the AMD server CPUs were much better than the Intel Xeons, so any wise customer was buying Opterons, not Xeons. Intel has followed AMD and it has added POPCNT to Nehalem, in 2008/2009 (for server CPUs, Nehalem has been the first that was better for any purpose than the AMD server CPUs, unlike for consumer CPUs, where Intel had surpassed AMD already since the middle of 2007, with Core 2).

> POPCNT has been added to the x86 ISA by AMD, in "Barcelona", in 2007, presumably because some customer for AMD Opteron has requested it.

Might have been Cray, they were using Opteron in that era.

And any clue about what they were doing with POPCNT? Does it has any particular use in encryption?

Yes, encryption:

https://vaibhavsagar.com/blog/2019/09/08/popcount/

Check out https://vaibhavsagar.com/blog/2019/09/08/popcount/

Back in my days as a CPU logic designer, I actually worked on a scientific mainframe where the MIB came by and said "We'll buy some if you add a vector pop count."

Anyway.... if you have cipher text that has been scrambled by a linear-feedback shift register, you can take two copies of the cipher text, shift one copy by N bits, XOR them together, and do a pop count on the result. Repeat for bunch of different N's. For some N that corresponds to the length of the LFSR the auto-correlation will be much better. So now you have at least that to go on... of course you don't know the feedback equation and you don't know the initialization constant, but you have the start of a handle.

Semi-related: one thing I liked about the video game Turing Complete [1] is that, once you've built the computer and implemented its (binary) machine code ... it doesn't give you an assembly language, or suggest one!

It has you start programming in binary, and then just tells you how to make your own mnemonics to substitute for having to write out each 8-bit input. So you end up picking them based on what commands appear most often in practice.

One instruction I ended up creating was JNEQCI, "jump if not equal, comparing to immediate". (jump if not equal where the first operand is treated as a register and the second as a constant/immediate value)

[1] from LevelHead, and similar to nand2tetris in that you build a computer from its circuits and then program it

All Zachtronics games are a strong recommend for anybody who doesn't already know them.

Exapunks and Opus Magnum are probably the more casual ones to get into, but everything they make is awesome and pretty challenging.

FYI, Turing Complete - while a fantastic game, is not made by Zachtronics.

Oops, fixed. Thanks. I had just lumped it in with all the others.

IIRC it also introduced index based addressing. Before that, people just wrote self modifying code to index arrays...

True.

The 8 index registers ("B-tube") are called B0 to B7 in this manual.

The B0 index register is hardwired to have the read-only value "0".

A read-only null register continues to be used in many modern instruction sets, e.g. in POWER or in Aarch64.

As bit-serial machines, popcnt etc would have been a bit easier than parallel machines. (Heck, I'm glad the world moved on from using teleprinter code for numbers and instructions; hideous isn't it?!)

POPCNT and LZCNT were added back with SSE4.2, which means all Intel CPUs since Nehalem and Haswell (respectively) and AMD since Barcelona support them.

to save you time, this is a summary of the links various people here are posting:

popcnt of a word counts the number of bits that are "1"

https://www.talkchess.com/forum3/viewtopic.php?t=38521

the NSA wanted to do cryptanalysis on intercepted messages, and since the CDC 6000 had 60-bit words, one word was enough to store most alphabets they were interested in. They were able to:

    Split a message into lines
    Set a bit for each unique character they encountered per line
    Use popcount to count the distinct characters
    Use the count as a hash for further cryptanalysis

Curiously, popcount seems to have disappeared from instruction sets between the mid-1970s and the mid-2000s.

(of course for all we know this could be NSA disinformation ;)

That's the answer to the NSA question. There are other uses described here https://vaibhavsagar.com/blog/2019/09/08/popcount/ including for Hamming codes and Neural nets and more.