[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [f-cpu] an instruciton


Martin Vahi wrote:

OK, may be I'm spamming, haven't read the F-CPU doc's yet,
but does F-CPU have an instruction, that just COUNTS THE
BITS IN A CERTAIN REGISTER? For instance, let's say register
X has the following contents: 0110011010 and
the sugested instruction just counts the "1"-bits in that
register. The result in this example is 5.

yes, there is even a better thing : the "Hamming distance",
but plain popcount is just hamming distance with register 0.

the instruction is detailed more or less at
pages 58, 101 and 102.

Remark : the definition of the POPC unit (that performs the population count)
has changed, the manual is outdated (it always is, by definition :-/).
look at http://www.f-cpu.seul.org/new/19c3-presentation.pdf
page 21 for the current synoptic view : the pocount
unit is preceded by a XOR of the 2 instruction operands.
This is useful in some applications as well as during
fabrication-time and power-up time integrity self-tests,
in conjunction with the LFSR. Because of this more general
use, i have dropped the old form where the 2nd operand
was substracted to the POPC result.

 What is this instruction good for? Well, in image
recognition and as the sound recognition task is EQUAL TO
image recognition(time as one dimension and frequencies as
the other dimension), then it will also become handy in any
sound related tasks like certain user interfaces.

 So, how can the prementioned instruction be used
in image and sound processing? By masks and in comparison.

Let's say, that I want to compare the image:

00000                          00100
01010  to a database sample  01010
00100                          00100

and I do it with some probabilety. Let's say, that
I consider the image recognized, if it differs
from the sample by n bits(at the moment, n=1).
So I just XOR the sample with the database version
and I get:


And in order to know, if I have a match, I have
to count, how many "1"-bits do I have.

that's exactly what the current unit does : XOR 2 operands and give 7 bits
(so the result can range from 0 to 64).

Well, generally
it's no problem, it can be done by shifting, but as
in image processing it's one of the most vastly used
operations and there are many samples to compare. The
suggested instruction can speed up the image and sound
recognition software atleast as many times, as many shifts should
be done withought using that instruction(aproxemately the
with of the registers, 64?).

Unfortunately I wasn't able to find
that kind of an instruction in the Intel's instruction set.

don't bother and give it up now (been there, done that, etc).
i ended up computing the popcount in MMX using a bit-parallel approach.

Please correct me, if I'm wrong, I haven't done almost any lowlevel
programming for the Intel processors. I must say, that the prementioned
instruction is specially useful with wide registers and, as we all
know, Intel sticks with the 32 bits, provided that we
exclude the "Itanic".

POPCOUNT  is also known as the "canonical NSA instruction" because
it is mandatory to all computers delivered to this "organisation".
it can be found in CRAYs and ALPHAs to name the best known examples.
a simple google search will give you some rough ideas about it.

Martin Vahi

have fun,

To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe f-cpu       in the body. http://f-cpu.seul.org/