Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The NSA Instruction (2019)

vaibhavsagar.com

Post reply on HN
Print view View original

71–80 of 98 posts

Re: The NSA Instruction (2019)

#71

Post by throw5away »

implements wrote: post #63
oefrha wrote: post #3

Discussed at the time: https://news.ycombinator.com/item?id=20914479

In this discussion someone offers: “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.

If you accidentally write "return x = 1" when x is a variable, you always return true. If you return "1 = x", you cause a syntax error. So some people have gotten into the habit of writing constants on the left, even if the return value of __builtin_popcount is not assignable.

Re: The NSA Instruction (2019)

#72

Post by notacoward »

devit wrote: post #67
notacoward wrote: post #35

Back in the mid-2000s I worked at a company that made their own (MIPS-based) chips. NSA was one of our customers - supposedly the "defense" who could be considered the good side of NSA compared to the 10x larger "offense" but still. As we were planning for our second generation, they offered quite a bit of money if we'd implement a "sheep and goats" instruction. It would take two operands: an input and a mask. The ma…

That's equivalent to !0 << popcount(!(x & mask)) (where left shift must saturate and not truncate the shift count, otherwise you need to special case x = 0) and seems much less useful than popcount.

I think you're misunderstanding what the instruction (or similar ones that others have mentioned) would do. It's a specialized permutation function; every bit in the input is preserved, just in a different position. Your version doesn't have that property at all, and would indeed not be very useful.

Re: The NSA Instruction (2019)

#73

Post by Sniffnoy »

less_less wrote: post #39
notacoward wrote: post #35

Back in the mid-2000s I worked at a company that made their own (MIPS-based) chips. NSA was one of our customers - supposedly the "defense" who could be considered the good side of NSA compared to the 10x larger "offense" but still. As we were planning for our second generation, they offered quite a bit of money if we'd implement a "sheep and goats" instruction. It would take two operands: an input and a mask. The ma…

Half of this instruction is present in AMD64's BMI2 extension as PEXT, and the reverse operation as PDEP. Unlike "sheep and goats", PEXT just extracts the sheep into the LSB and ignores the goats. 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 rememb…

Heh, so it's an instruction for INTERCAL's "select" (~) operator...

Re: The NSA Instruction (2019)

#74

Post by jhallenworld »

notacoward wrote: post #35

Back in the mid-2000s I worked at a company that made their own (MIPS-based) chips. NSA was one of our customers - supposedly the "defense" who could be considered the good side of NSA compared to the 10x larger "offense" but still. As we were planning for our second generation, they offered quite a bit of money if we'd implement a "sheep and goats" instruction. It would take two operands: an input and a mask. The ma…

Compress and expand (from Hackers Delight) are like this, but only the selected bits are kept. These are quite useful instructions. One use is the hash function for perfect hash tables. The hash table includes a mask which picks the bits of the keys which actually change (between all keys) and compresses them all to the right as the hash index.

Disclaimer: I contributed the "expand" algorithm shown in Hacker's Delight.

Re: The NSA Instruction (2019)

#75

Post by iib »

adrian_b wrote: post #60
iib wrote: post #57

Earlier quoted context omitted.

Hardware random number generators do have some security issues though. Linux devs were opposed to solely relying on them, because they can be compromised by the vendor [1]. So they are at best used in algorithms that they can not compromise (still in [1], but lower, in the comments). [1] https://web.archive.org/web/20180611180213/https://plus.goog...

The security issues are not with hardware random number generators in general, but with those that are included inside complex devices like monolithic CPUs or TPMs, so that the owners of those devices cannot verify that the RNG's really do what they are claimed to do. 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 ju…

I remembered something, and I want to say as an aside, for anybody reading that at one point has to design a toy RNG from an ADC, as I had to some years ago, you should not take the last bits as they are--as was my first thought--, you should pass them through something like the von Neumann corrector [1].

[1] https://everything2.com/title/von+Neumann+corrector

Re: The NSA Instruction (2019)

#76

Post by implements »

throw5away wrote: post #71
implements wrote: post #63

Earlier quoted context omitted.

In this discussion someone offers: “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.

If you accidentally write "return x = 1" when x is a variable, you always return true. If you return "1 = x", you cause a syntax error. So some people have gotten into the habit of writing constants on the left, even if the return value of __builtin_popcount is not assignable.

Thanks for explaining - that makes sense.

Re: The NSA Instruction (2019)

#77

Post by ncmncm »

It is appalling that, after every other general-computing architecture in common use either started out with a popcount instruction, or had one added later at substantial expense, RISC-V came out without one.

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.)

Re: The NSA Instruction (2019)

#78

Post by ncmncm »

dragontamer wrote: post #47
dwheeler wrote: post #30

Obviously using a dedicated instruction is fastest in normal cases. 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…

> But if you need to implement popcount or many other bit manipulation algorithms in software 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??

Yet, practically all software running on 64-bit x86 machines is compiled without, because the original amd64 released in 2003 lacked it, and distributions still target that. Likewise, MSVC. There would be good reasons for Apple XCode not to, but that doesn't mean they don't.

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.

Re: The NSA Instruction (2019)

#79

Post by ncmncm »

iib wrote: post #57
adrian_b wrote: post #25

Earlier quoted context omitted.

Moreover, Ferranti Mark I included a hardware random number generator, another feature useful for cryptography, which was reintroduced only recently in modern CPUs.

Hardware random number generators do have some security issues though. Linux devs were opposed to solely relying on them, because they can be compromised by the vendor [1]. So they are at best used in algorithms that they can not compromise (still in [1], but lower, in the comments). [1] https://web.archive.org/web/20180611180213/https://plus.goog...

Indeed, AMD has more than once shipped CPUs in which the random-number instruction would always yield the same value, that had to be monkey-patched to yield apparently random numbers. A valuable hint.

Re: The NSA Instruction (2019)

#80

Post by ncmncm »

FridayoLeary wrote: post #42

A bit off- topic but i want to know; is binary code (01etc) still used today in programming/coding? And for what applications?

This seems like a strange question. All computing today uses binary code. We often write things in other bases for convenience, but at the hardware level, it is nothing but ones and zeroes.

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.

Post reply on HN