The NSA Instruction (2019)
vaibhavsagar.com
vaibhavsagar.com
If I recall the Knuth lecture correctly, given a "sheep and goats" instruction where one of the sets is packed in reverse order, you can implement any n-bit permutation in something like log2(n) instructions. I don't remember if this is true if they're both packed in forward order. But it would be nice for some hardware crypto designs, like DES or more recently GIFT.
PEXT has at least two additional use cases I know of: manipulating bit indices for databases, and binary (GF2) matrix manipulation. I've used it in a (non-crypto) project to select a subset of columns from a binary matrix, to convert it to systematic form. This subroutine also used popcount.
What I really wanted in that project was another "NSA instruction": bit matrix multiply. Cray supercomputers can multiply two 64x64 binary matrices in one instruction, though I have no idea how many cycles it takes. With AVX2, the best I could do is 6 instructions plus precomputation for 8x8 x 8x32, which is 1/128'th the work.
Unfortunately we only have 1024 chickens in modern computers.
Today we know how to put 16 4 GHz CPUs on a single die. If we want, we can hook chips together to build a computer with 16,384 CPUs.
But we can't build a single chip running usefully at 16x4 GHz. We can't build a single system running at 16384x4 GHz.
If we could build that fast chip or system, all else being equal, the market would choose the single fast CPU over the pile of slow CPUs.
Right now "the market can't say so". It's impossible to provide such a system to the market. We're forced to buy computers with so many CPUs because we've pretty much hit the wall in terms of frequency scaling.
Intel Pentium 4, circa 2001, ran at about 1.4 GHz.
Intel Core i9, circa 2021, runs at about 3.5 GHz, with turbo boost to about 5.2 GHz.
That's about a 3x improvement in clock speed in 20 years. We simply can't make CPUs that run faster than that.
(I had to use x to represent multiplication, HN formatting gets funny with asterisks).
For "rank", the "popcount" instruction can be used. Interestingly, for "select", the "PDEP" instruction can be used: you can put the data array in the PDEP mask, and 1 << n in the value; basically flip the operands. I found this quite fascinating. For details, there is a short paper on this: "A Fast x86 Implementation of Select".
I wonder if those succinct data structures are in any way related to what NSA is doing. I think not, but who knows.
Edit, I see Roger Shepherd (one of the people in the know at above mentioned company) commented in the comp.arch thread (which I vaguely remember reading at the time) but no mention of MIB...
Did representatives of the “NSA” have a New Zealand accent?
Bit Scrambler / Chutes - shuffle bits around in a way that divides a stream.
This might also be useful in pre-filters for compression (entropy reduction) if you knew the content of the message. E.G. for ASCII text the upper 2-3 bits of each letter could be ranked to the side for better compression and a reduction of message size.
As others have pointed out, modern CPUs ended up with 'half' that instruction, so I wonder if there were any other reasons for the full instruction.
Disclaimer: I contributed the "expand" algorithm shown in Hacker's Delight.
Specifically, after WWII, Turing worked on the ACE 1 (later reduced to Pilot ACE) project to build an electronic computer, which didn't really progress due to management and bureaucracy overhead. He eventually went to Manchester, once they got their Manchester Mark 1 off the ground, which they tried to commercialize as "Ferranti Mark 1" (https://en.wikipedia.org/wiki/Ferranti_Mark_1).
While employed for the University, Turing IIRC continued to work as an external consultant for whatever became of G.C. & C.S. on the side. According to the book, he convinced them to buy such a machine (presumably for crypt-analysis?) and, on the Manchester side of things, insisted on some modifications to be made, including a "horizontal adder", so it could count the number of bits set in a word with a single instruction, i.e. a popcount instruction. This would pre-date the IBM Stretch mentioned in the article.
https://groups.google.com/g/comp.arch/c/UXEi7G6WHuU/m/Z2z7fC...
IBM Z-series machines do have population count, finally.
However, we re-discovered the fact that some Intel CPUs, including the Nehalem mentioned in the article, have a bug that severly affects popcnt's performance, see for example here: https://github.com/komrad36/LATCH/issues/3#issuecomment-2671...
Nevertheless, the first computer having this instruction was a British computer, the Ferranti Mark I (February 1951).
The name used by Ferranti Mark I for this instruction was "sideways add".
Also notable was that Ferranti Mark I had the equivalent of LZCNT (count leading zeroes) too.
Both instructions are very useful and they are standard now for modern instruction sets, but they were omitted in most computers after Ferranti Mark I, except in expensive supercomputers.
[1] https://web.archive.org/web/20180611180213/https://plus.goog...
Discrete hardware RNG's, like that of the Ferranti Mark I, are perfectly secure.
For a modern device, the best way to implement a hardware RNG is to just include an ADC (analog-digital converter) input. Then you may connect externally on the PCB some noisy analog amplifier, e.g. one which has a noisy resistor or diode at its input. Digitizing the noise with the ADC will provide the random numbers and the ADC input can be isolated and tested separately at any time, so the user can verify that there is no hidden functionality.
Most microcontrollers have ADC inputs, so it is easy to add a secure hardware RNG for them. The same could be done for a personal computer by making a noisy amplifier that can be plugged in the microphone input, or by making a USB device with a microcontroller.
But yes, it definitely pre-dates the 1961 IBM machine in the article.
But if you need to implement popcount or many other bit manipulation algorithms in software, a good book to look at is "Hacker's Delight" by Henry S. Warren, Jr, 2003.
"Hacker's Delight' page 65+ discuss "Counting 1-bits" (population counts). There are a lot of software algorithms to do this.
One approach is to set each 2-bit field to the count of 2 1-bit fields, then each 4-bit field to the count of 2 2-bit fields, etc., like this:
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
x = (x & 0x0000ffff) + (x >> 16);
I think this approach is a classic divide-and-conquer solution.
for(i=0; !x; ++i) {
x = (x-1)&x
}
return i;
It's not that fast unless your integer is really sparse (since it has a branch), but I've always liked the bit hack.
size_t count = sizeof(x) * 8;
while(x != -1) {
x |= x+1;
--count;
}
return count;Power9, ARM, x86 BMI, Nvidia PTX, AMD GCN, and AMD RDNA all have a popcount instruction.
Yeah, all mainstream CPUs and GPUs made in the past decade...
Unfortunately, there's no system I can think of where you'd need the software solution anymore... Maybe if you wanted popcount on an Arduino??
If you tell MSVC to issue a popcount instruction with "__popcnt64()" (etc.), it will. If you ask Gcc to issue a popcount instruction with "__builtin_popcount()", it will only do it if you have also told it to target an ISA that has one; otherwise it emulates.
The only portable way to get a popcount instruction, thus far, is to use C++'s std::bitset::count() in circumstances where the compiler believes the instruction would work. Pleasingly, Gcc and Clang are both happy to hold an integer type and its std::bitset representation in the same register at the same time, so there is no runtime penalty for a round-trip through std::bitset.
MSVC's standard library implementation of std::bitset does not use the popcount instruction.
asm(
"mov\t%1,%0\n"
"popcnt\t%1,%1"
: "=r"(Res) : "r"(Pop) : "cc");
asm("popcnt\t%0,%0" : "=r"(res) : "0"(pop) : "cc");
If you haven't told it that the target ISA has the POPCNT instruction, std::popcount() on MSVC will use runtime feature detection: https://godbolt.org/z/qab4Mjv1v
Faster Population Counts Using AVX2 Instructions, Computer Journal, Volume 61, Issue 1, 2018 https://arxiv.org/abs/1611.07612
CUDA's __activemask(); returns the 32-bit value of your current 32-wide EXEC mask. That is to say, if your current warp is:
int foo = 0;
if(threadIdx.x %= 2){
foo = __activemask();
}
popcount(__activemask()); returns the number of threads executing.
lanemask_lt() returns "0b0000000000000001" for the 0th lane. 0b0000000000000011 for the 1st lane. 0b0000000000000111... for the 2nd lane... and 111111111...111 for the last 31st lane.
popcount(__activemask() & lanemask_lt()); returns the "active lane count". All together now, we can make a parallel SIMD-stack that can push/pop together in parallel.
int head = 0;
char buffer[0x1000];
while(fooBar()){ // Dynamic! We don't know who is, or is not active anymore
int localPrefix = __popc(__activemask() & __lanemask_lt());
int totalWarpActive = __popc(__activemask());
buffer[head + localPrefix] = generateValueThisThread();
if(localPrefix == 0){
head += totalWarpActive; // Move the head forward, much like a "push" operation in single-thread land
// Only one thread should move the head
}
__syncthreads(); // Thread barrier, make sure everyone is waiting on activeThread#0 before continuing.
}
As such, you can dynamically load-balance between GPU threads (!!!) from a shared stack with minimal overheads.
If you want to extend this larger than one 32-wide CUDA-warp, you'll need to use __shared __ memory to share the prefix with the rest of the block.
It is a bad idea (too much overhead) to extend this much larger than a block, as there's no quick way to communicate outside of your block. Still though, having chunks of up to 1024 threads synchronized through a shared data-structure that only has nanoseconds of overhead is a nifty trick.
-----------
EDIT: Oh right, and this concept is now replicated very, very quickly in the dedicated __ballot_sync(...) function (which compiles down to just a few assembly instructions).
Playing with the "Exec-mask" is a hugely efficient way to synchronously, and dynamically gather information across your warp. So lots of little tricks have been built around this.
This is one of those moments!
PS: I once wrote a 3D engine, but clearly my knowledge is now so out of date as to be practically stone age compared to this kind of thing...
Horror story: I was once developing a TRN system for a spacecraft instrument which uses an ancient x86 processor that does not have popcnt, ended up using a look-up table instead...
It seems that look up tables are still faster when memory allows it though (http://www.dalkescientific.com/writings/diary/archive/2008/0...)
“I remember in one interview I was asked to write a function that returns true iff x is a power of two, so I wrote return 1 == __builtin_popcount(x). They liked that.”
I’m no longer a programmer, but I wondered why it wasn’t “return (__builtin_popcount(x) == 1)” - just out of interest.
== is a boolian comparison operator. Therefore, we are returning true or false depending on how the expression evaluates. __builtin_popcount(x) will return the number of set '1' bits in the binary int x. Since powers of 2 in binary are always a single 1 followed by 0's, this expression is checking whether the number of 1's in the binary representation of x is equal to 1, and returning true if this is the case. Otherwise, if there are more than 1 '1's, this indicates that x is not a multiple of 2, and should return false.
Example: 15 in binary is 01111. There are 4 '1's, so the 1 == 4 comparison returns false. Increment to 16, or 10000, and there is exactly 1 '1', and so the comparison 1 == 1 returns true.
Hope this helped. :)
It still doesn't have any. The proposed B, "bitmanip" extension has it (along with a raft of trivial variations: count leading zeroes, count trailing ones, yada yada) but that is not ratified and not implemented in any chip I know of. Since B is a huge extension, we can expect it will be routinely omitted even after it's ratified, and compilers will need special prodding to produce any such instructions.
It should have been in the base instruction set. We probably can blame its lack on the academic origins of the design. CS professors probably think of it as a thing not needed to implement Lisp, therefore not worth class time.
(Some people say, "Oh, but you can trap and emulate it", which adds insult to injury. Trapping and emulating eliminates all the value the instruction offers.)
Bitmanip includes other some nice stuff that other CPUs lack-- but I'd give it up happily to be able to count on popcount and clz being there.
I'm doubtful with your academic origins speculation. Even MMIX has SADD. It may be more the case that CLZs and popcounts are relatively rare. But in essentially every case they're used there in some performance critical inner-loop. They're not even necessarily obvious in source code because modern compilers are smart enough to detect obvious constructions and substitute the instruction.
The world of arm is full of important extensions that are optional but the world gets by. Hopefully at some point someone will standardize some RISC-V edition that turns a number of optional things mandatory and after it becomes popular enough that's what people will target.
An instruction executed relatively rarely in the course of running a program may achieve critical importance by reducing the latency of the most important result, or by each replacing what would otherwise be dozens of other instructions. Among candidates for such a distinction, popcount takes honors second only to multiplication.
Count-leading-zeroes and other variations rely on the same circuitry and can be emulated by preceding popcount with one or two conventional ALU operations, so are conveniences; popcount is the fully general, indispensible primitive.
No, it should not. Popcount is not necessary for all the microcontrollers and it does not fully share its circuitry with the other instructions of the basic ISA.
Popcount must be in an extension (like bitmanip) and it will be ratified and integrated into chips soon. The 1.0 version of the B extension is currently under review and is much simpler than the previous versions.
while(x != 0) { c += x&1; x >>= 1; }
Is this something that should be added to LLVM?
Edit: flip the order
In the case of the code you’ve posted, you’re shifting out the LSB before you check the bit, so it’s not quite right, but (in general) popcount is recognized and used when possible.
The two links in the article:
https://lemire.me/blog/2016/05/23/the-surprising-cleverness-...
And the LLVM source indicate to me it only picks up on x&(x-1) pattern, which would miss the popcount optimization on code like mine.
https://godbolt.org/z/qdWhxMPsf
Note the run output under clang.
edit:
> And the LLVM source indicate to me it only picks up on x&(x-1) pattern, which would miss the popcount optimization on code like mine.
Thanks for teaching me something this morning. That's annoying.
I think the portable solution is std::popcount in C++ (or equivalent in Rust).
https://doc.rust-lang.org/std/?search=count_ones
Internally Rust actually just staples LLVM's implementation into your code, via an intrinsic - but if that were ever to change the standard library count_ones() methods will do whatever happens instead so you should use that.
Example with int8_t:
int8_t i = -127; // 0b10000001
i >>= 1; // 0b11000000
i >>= 1; // 0b11100000
i >>= 1; // 0b11110000
i >>= 1; // 0b11111000
i >>= 1; // 0b11111100
i >>= 1; // 0b11111110
i >>= 1; // 0b11111111
i >>= 1; // 0b11111111 ad infinitum
So your program is not equivalent to popcount.
But maybe you are asking about uses of independent bits. A maximally efficient representation for a set with a fixed universe of members uses each bit position in a large-enough integer type to represent presence or absence of a possible member. Then, AND and OR operations correspond to set intersection and union operations. C++ provides std::bitset for this use. Useful such sets include days in the week or month, and letters in the alphabet.
The article mentions chess, where you might have a 64-bit word to represent the positions of (say) all the pawns on the board. Fairly simple bitwise operations identify all the positions those pawns threaten.
Modern symmetric cryptographic primitives often use principally bitwise operations, including shifts.