Chinaunix

标题: 那位兄弟在看eCos,问个问题 [打印本页]

作者: qfox 时间: 2007-04-05 12:24
标题: 那位兄弟在看eCos,问个问题
最近在看eCos,对如下一段代码不是很明白

cyg_uint32 hal_lsbit_index(cyg_uint32 mask)
{
cyg_uint32 n = mask;
static const signed char tab[64] =
{ -1, 0, 1, 12, 2, 6, 0, 13, 3, 0, 7, 0, 0, 0, 0, 14, 10,
4, 0, 0, 8, 0, 0, 25, 0, 0, 0, 0, 0, 21, 27 , 15, 31, 11,
5, 0, 0, 0, 0, 0, 9, 0, 0, 24, 0, 0 , 20, 26, 30, 0, 0, 0,
0, 23, 0, 19, 29, 0, 22, 18, 28, 17, 16, 0
};
n &= ~(n-1UL);
n = (n<<16)-n;
n = (n<<6)+n;
n = (n<<4)+n;
return tab[n>>26];
}

复制代码

代码位置：hal/mips/arch/hal_misc.c
功能：应该是通过查询mask中最右边的1来得到一个index值，继而通过index来查询run_queue
就是不明白怎么实现的，呵呵，看i386中就一个bsf指令就搞定，这个怎么这么麻烦

作者: epegasus 时间: 2007-04-05 16:00
这贴怎么没人回呢?看在我也碰过redboot的份上我就胡说两句
n &= ~(n-1UL);结果等价于n&=(~n)+1;这个自己可以证明,这样就很容易明白结果是得到"最右边的1"
至于这3行:n = (n<<16)-n;
n = (n<<6)+n;
n = (n<<4)+n;

return tab[n>>26];
是个散列函数吧,即n*17*65*65535/2^26,对于n不同结果不同,应该是空间换时间的方法
至于这个散列函数的是什么原理,要懂数学的来证明了

作者: qfox 时间: 2007-04-05 16:17

原帖由 epegasus 于 2007-4-5 16:00 发表
这贴怎么没人回呢?看在我也碰过redboot的份上我就胡说两句
n &= ~(n-1UL);结果等价于n&=(~n)+1;这个自己可以证明,这样就很容易明白结果是得到"最右边的1"
至于这3行:n = (n<<16)-n;
...

tks,n &= ~(n-1UL);这个我也看明白了，就是后面的一砣计算，迷惑~
再有一个问题；
在Interrupt_end中

externC void
interrupt_end(
cyg_uint32 isr_ret,
Cyg_Interrupt *intr,
HAL_SavedRegisters *regs
)
{
CYG_REPORT_FUNCTION();
#ifdef CYGPKG_KERNEL_SMP_SUPPORT
Cyg_Scheduler::lock();
#endif
// Sometimes we have a NULL intr object pointer.
cyg_vector vector = (intr!=NULL)?intr->vector:0;
CYG_INSTRUMENT_INTR(END, vector, isr_ret);
CYG_UNUSED_PARAM( cyg_vector, vector ); // prevent compiler warning
#ifndef CYGIMP_KERNEL_INTERRUPTS_CHAIN
// Only do this if we are in a non-chained configuration.
// If we are chained, then chain_isr below will do the DSR
// posting.
if( isr_ret & Cyg_Interrupt::CALL_DSR && intr != NULL ) intr->post_dsr();
#endif
#ifdef CYGDBG_KERNEL_DEBUG_GDB_THREAD_SUPPORT
// If we have GDB support enabled, and there is the possibility
// that this thread will be context switched as a result of this
// interrupt, then save the pointer to the saved thread context in
// the thread object so that GDB can get a meaningful context to
// look at.
Cyg_Scheduler::get_current_thread()->set_saved_context(regs);
#endif
// Now unlock the scheduler, which may also call DSRs
// and cause a thread switch to happen.
Cyg_Scheduler::unlock();
Cyg_Scheduler::get_current_thread()->set_saved_context(0);
#endif
CYG_INSTRUMENT_INTR(RESTORE, vector, 0);
}

复制代码

如果不是多处理器，那就没有lock，可后面直接unlock了。那么是什么时候lock的？
谢谢赐教

作者: qfox 时间: 2007-04-06 18:31
标题: 回复 3楼 qfox 的帖子
看明白了，原来一陷入isr就加锁了，不过这么定义符号还是第一次看到：
__asm__(#x)
还有这个
__attribute__ ((alias (#__symbol__)))
哪位给讲讲。谢谢

作者: ssh_33 时间: 2008-07-09 23:39
标题: 回复 #1 qfox 的帖子
执行完第一步之后就是2^n的整数，即只有原来的最低有效位为1
再往后的话就是乘以一个多项式
1+2^(-4) + 2^(-6) + 2^(-10) - 2^(-16) - 2^(-20) - 2^(-22)- 2^(-26)

即

[2^(26)+2^(22) + 2^(20) + 2^(16) - 2^(10) - 2^(6) - 2^(4) -1]/2^(26)

这个多项式分解开就是[2^(16) - 1]*[2^(6) +1]*[2^(4)+ 1]/2^26

前面三句分别对应这个多项式的分子上的前三项，这三项可以互换位置，
也就是说代码中的：
n = (n<<16)-n;
n = (n<<6)+n;
n = (n<<4)+n;
可以互换，最后一项n>>26则必须在最后。

至于这个多项式是如何构造出来的，要看数论/近世代数/离散数学学得如何了，反正我目前还没弄清楚原理。

构造这个多项式的目的是把32个数(2^n, n属于[0：31])映射到互不重叠的一个区域，每个区域可以经过最简单的运算得到区域号，

最后的运算n>>26即除以2^26，也就意味着映射后的区域个数为2^(32-26)=2^6=64，这就是数组为什么是64个的原因，当然能映射到更少更好，但是必须是在这个映射唯一的情况下让这个运算的次数最少，也就是分解了多项式后因式的个数最少，从而可以在最短且确定的时间内找出最低有效位的位置。

映射的区域数更少也必须右移26位（如果区域数在32到64之间的话），比32更少的话肯定不能形成单映射，32个数映射到32个区域呢，这个还不清楚是否可行。相信这已经是最优的算法了。

[ 本帖最后由 ssh_33 于 2008-7-10 18:56 编辑 ]

作者: epegasus 时间: 2008-07-10 09:18
上来第一贴就挖坟，而且挖的这么有档次

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2