Control Data 6000 series
CPU instructions

Logical operations

• Logical Product is the boolean AND operation
• Logical addition is the boolean OR operation
• Logical difference is the boolean Exclusive OR (EXOR) operation

Note about Pop-count or "sideways add" [from]:

Seymour Cray's first supercomputer (the Control Data 6600) sported such an instruction, as did all subsequent Control Data machines until the advent of the 180 series in the mid '80s. It was almost a tradition that one of the first of any new faster CDC machine was delivered to a "good customer" - picked up at the factory by an anonymous truck, and never heard from again. We always wondered what such an instruction might be useful for - until one of the first of the 180 series (n'th generation successor to the 6600) was delivered to such a customer, and cries of anguish erupted that this machine didn't have such an instruction. We scrambled and had to create a very tight code sequence within the instruction stack that could be generated via a Fortran intrinsic function. Simon Lavington also mentions in his book that the venerable 6600 inherited some ideas from the Manchester Atlas. I never found out what specifically - did the Atlas sport such an instruction? - perhaps also inherited from Mark I? I'm not sure if Cray's other machines (built after he left Control Data) had such an instruction, but I'm told they did.

However, and without boring through detail, I can perhaps give a flavor of how it was used a long time ago and in a manner that is interesting from a cryptanalysis perspective - and given that it jibes with similar discussion in the papers mentioned above. In one of the first "interactive" environments supported on the 6600 - the Intercom time-sharing system, we had a utility that allowed one to search a text file for some arbitrary character string - much as any text editor allows today.
This was implemented approx. as follows. Each line of text in the file had appended to it a 60-bit word, the contents of which were a bit vector. If there were one or more of the letter "A" in the line, bit 1 was set, if there were one or more of the letter "B" in the line, then bit 2 was set, etc... thus setting some sub-set of 36 bits corresponding to the characters A..Z and 0..9.
Let's call this word appended to each line its "thumbprint". There are 24 bits left - more about that later. Now to search for any line containing some search string, all you have to do is create a similar thumbprint for the search string, and loop through the thumbprints of the lines in the text file, checking each against your search thumbprint. "Checking" in this sense means doing a logical "AND" between the two to extract matching bits, and then counting how many bits matched - hence the pop-count instruction. A "hit" would of course only be tentative. It does not tell you that the line in question contains the actual string you are looking for - only that the line contains somewhere some (count of) the characters contained in your search string.
This little loop could however be coded in an extremely tight manner to fit in the instruction stack (equivalent to instruction cache in today's technology) thus allowing a very fast winnowing of interesting text lines that can then be examined more closely. The actual instructions used within the loop also made good use of the parallelism offered by the separate functional units of the 6600 cpu - and in later machines - pipelining. The extra 24 bits were used in other applications (of similar ilk) to reflect not single characters, but the occurrence of certain digraphs in the text line. Thus bit 40 in the thumbprint might indicate whether a given "interesting" digraph did or did not occur in a given line. Later the border between the 36 bits and 24 bits within the 60-bit word was moved and successively tuned. Certain bits of the original 36 were commoned up - i.e. a particular bit might indicate the presence of any of Z, X, or Q because maybe they are relatively uncommon. This would free up two more bits for use as digraph flags - and so on. Then, in another place, the whole mechanism was turned on its head. It wasn't used to *look for* a certain character string, but rather to *reject* certain lines of text as being uninteresting. (Others might use the word "implausible" here.) Furthermore, the concept of a thumbprint per "line of text" was refined to support differing granularity of the thumbprinting, and of course the size of the thumbprint itself, as 64 bits became a more common word-size.
Some thirty years later, I find the paper cited by Steve Bellovin on "Probable Plaintext Cryptanalysis" to be extrememely interesting - in particular it cites another paper about "A Programmable Plaintext Recognizer". This is the only open documentation I have ever come across that discusses this kind of mechanism in any detail. .

Jitze Couperus, Control Data Systems

For years, I had heard the story about NSA liking that instruction. But I never understood why, until I started working on plaintext recognizers, and independently derived the need for it. There are other instruction types that are useful for cryptanalysts. The CDC Star had a lovely set of vector operations under masks. And the Harvest add-on to the IBM 7030 (Stretch), described in a book by Buchholz ("Planning a Computer System", McGraw-Hill, 1962) was intended for NSA as well.

Steve Bellovin

For what it's worth, the same instruction was taken out of the widely-released versions of the Digital Equipment VAX, at the request of the NSA. Allegedly, there were versions that had the opcode in the machine for that same customer.

Jon Callas

---

CPU Error Modes