5 Apr
2019
5 Apr
'19
8:59 a.m.
Just wondering if anyone has come up with a fast way to count the number of
1s in a word on a PDP-8. The obvious way is looping 12 times, rotating the
word through the link or sign bit, incrementing a count based on the value
of the link or sign.
With a small lookup table, you can reduce the total number of loops by
counting multiple groups of bits at a time, but this of course comes with
the cost of using more memory. Any other suggestions?
Much appreciated,
Kyle
5 Apr
5 Apr
9:56 a.m.
I suppose you could test each nybble for zero, then equate a 16-element LUT
on nybbles not zero?
--
Anders Nelson
+1 (517) 775-6129
www.erogear.com
On Fri, Apr 5, 2019 at 11:59 AM Kyle Owen via cctalk <cctalk at classiccmp.org>
wrote:
Just wondering if anyone has come up with a fast way
to count the number of
1s in a word on a PDP-8. The obvious way is looping 12 times, rotating the
word through the link or sign bit, incrementing a count based on the value
of the link or sign.
With a small lookup table, you can reduce the total number of loops by
counting multiple groups of bits at a time, but this of course comes with
the cost of using more memory. Any other suggestions?
Much appreciated,
Kyle
12:08 p.m.
From: Kyle Owen via cctalk: Friday, April 05, 2019 8:59 AM
Just wondering if anyone has come up with a fast way
to count the number of
1s in a word on a PDP-8. The obvious way is looping 12 times, rotating the
word through the link or sign bit, incrementing a count based on the value
of the link or sign.
That's probably the shortest, but not the fastest. (I get 13 words.)
You could use RTL and check two bits at a time, for a probably-faster
version. (That one is 32 words with the loop unrolled.)
With a small lookup table, you can reduce the total
number of loops by
counting multiple groups of bits at a time, but this of course comes with
the cost of using more memory. Any other suggestions?
I know a hack to clear a single bit at a time. Here's my first attempt (14
words):
/
/ Return the number of bits that were set in AC.
CBITS, .-.
DCA CBMASK / Save the value
DCA CBCNT / No bits yet
CBLP, TAD CBMASK / Get bits, or bits-1
AND CBMASK / Likely clear bottom bit
SNA / Last one?
JMP CBRET
ISZ CBCNT / One more bit
DCA CBMASK / New mask
CMA / Complement bottom bit
JMP CBLP / ...and go again
CBRET, TAD CBCNT / Get result
JMP I CBITS / ...and return
CBMASK, .-.
CBCNT, .-.
$
The run time is related to the number of bits set, and independent of their
position.
It feels like we did this a year or two ago? Or maybe in the PiDP group?
Vince
1:49 p.m.
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.
Randy
________________________________
From: cctalk <cctalk-bounces at classiccmp.org> on behalf of Vincent Slyngstad via
cctalk <cctalk at classiccmp.org>
Sent: Friday, April 5, 2019 12:08 PM
To: Kyle Owen; General Discussion: On-Topic and Off-Topic Posts
Subject: Re: PDP-8: count number of set bits in a word
From: Kyle Owen via cctalk: Friday, April 05, 2019 8:59 AM
Just wondering if anyone has come up with a fast way
to count the number of
1s in a word on a PDP-8. The obvious way is looping 12 times, rotating the
word through the link or sign bit, incrementing a count based on the value
of the link or sign.
That's probably the shortest, but not the fastest. (I get 13 words.)
You could use RTL and check two bits at a time, for a probably-faster
version. (That one is 32 words with the loop unrolled.)
With a small lookup table, you can reduce the total
number of loops by
counting multiple groups of bits at a time, but this of course comes with
the cost of using more memory. Any other suggestions?
I know a hack to clear a single bit at a time. Here's my first attempt (14
words):
/
/ Return the number of bits that were set in AC.
CBITS, .-.
DCA CBMASK / Save the value
DCA CBCNT / No bits yet
CBLP, TAD CBMASK / Get bits, or bits-1
AND CBMASK / Likely clear bottom bit
SNA / Last one?
JMP CBRET
ISZ CBCNT / One more bit
DCA CBMASK / New mask
CMA / Complement bottom bit
JMP CBLP / ...and go again
CBRET, TAD CBCNT / Get result
JMP I CBITS / ...and return
CBMASK, .-.
CBCNT, .-.
$
The run time is related to the number of bits set, and independent of their
position.
It feels like we did this a year or two ago? Or maybe in the PiDP group?
Vince
2:02 p.m.
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
3:07 p.m.
A general discussion of population count:
https://stackoverflow.com/questions/8590432/when-to-use-parallel-counting-m…
2087
days inactive
2087
days old
5 comments
6 participants
participants (6)
-
anders.k.nelson＠gmail.com -
kylevowen＠gmail.com -
paulkoning＠comcast.net -
phil＠ultimate.com -
rdawson16＠hotmail.com -
v.slyngstad＠frontier.com