Message-ID: <3C5431F8.A1DA1480@picsel.com>
Date: Sun, 27 Jan 2002 16:59:36 +0000
From: Vadim Borshchev <vadim.borshchev@picsel.com>
Organization: Picsel Technologies Ltd.
X-Mailer: Mozilla 4.77 [en] (X11; U; Linux 2.2.19pre17 i686)
X-Accept-Language: en-GB, en
MIME-Version: 1.0
Newsgroups: comp.sys.arm
Subject: Re: ARM7TDMI leading zero count source code
References: <a2onr1$ril$1@news.planetinternet.be>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Complaints-To: abuse@clara.net (please include full headers)
X-Trace: 901193402400d4a4120058028802148064d40b00328830883a000e703c544026
NNTP-Posting-Date: Sun, 27 Jan 2002 18:00:06 GMT
Lines: 50


Phil wrote:
> 
> Does anyone have any fast source to calculate the number of leading zeros
> (like the v5 clz instruction) on ARM7TDMI ?
> 
> Any suggestions how to do this are welcome.
> 

Try the following code.  Compile to assembly output and do your best
optimizing it :)


/*  Count leading zeros */

static const unsigned clz_magic = 0x7dcd629;
static const char clz_table[] = {
     0, 31,  9, 30,  3,  8, 18, 29,
     2,  5,  7, 14, 12, 17, 22, 28,
     1, 10,  4, 19,  6, 15, 13, 23,
    11, 20, 16, 24, 21, 25, 26, 27
};

unsigned clz (unsigned x) {
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    return x ? clz_table[((clz_magic * x) + clz_magic) >> 27] : 32;
}


/* Count trailing zeros */

static const unsigned ctz_magic = 0xfb9ac52;
static const char ctz_table[] = {
    31,  0, 22,  1, 28, 23, 13,  2,
    29, 26, 24, 17, 19, 14,  9,  3,
    30, 21, 27, 12, 25, 16, 18,  8,
    20, 11, 15,  7, 10,  6,  5,  4
};

unsigned ctz (unsigned x) {
    return (x &= -x) ? ctz_table[(x * ctz_magic) >> 27] : 32;
}



Sincerely,
  Vadim Borshchev