Re: [f-cpu] an instruciton

[Yann Guidon <whygee@f-cpu.org>]

hi,

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
http://www.f-cpu.seul.org/cedric/unstable/F-CPU_manual-0.2.7c-en-color.pdf
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:
>
> 00100
> 00000
> 00000
>
> 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.

> Regards,
>    Martin Vahi
>  
have fun,
YG

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