那位兄弟在看eCos,问个问题

qfox

最近在看eCos,对如下一段代码不是很明白

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

复制代码

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

epegasus

这贴怎么没人回呢?看在我也碰过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

原帖由 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中

1. 
   
2. externC void
   
3. interrupt_end(
   
4.     cyg_uint32          isr_ret,
   
5.     Cyg_Interrupt       *intr,
   
6.     HAL_SavedRegisters  *regs
   
7.     )
   
8. {
   
9.     CYG_REPORT_FUNCTION();
   
10. 
    
11. #ifdef CYGPKG_KERNEL_SMP_SUPPORT
    
12.   Cyg_Scheduler::lock();
    
13. #endif
    
14. 
    
15.     // Sometimes we have a NULL intr object pointer.
    
16.     cyg_vector vector = (intr!=NULL)?intr->vector:0;
    
17. 
    
18.     CYG_INSTRUMENT_INTR(END, vector, isr_ret);
    
19.    
    
20.     CYG_UNUSED_PARAM( cyg_vector, vector ); // prevent compiler warning
    
21.    
    
22. #ifndef CYGIMP_KERNEL_INTERRUPTS_CHAIN
    
23. 
    
24.     // Only do this if we are in a non-chained configuration.
    
25.     // If we are chained, then chain_isr below will do the DSR
    
26.     // posting.
    
27. 
    
28.     if( isr_ret & Cyg_Interrupt::CALL_DSR && intr != NULL ) intr->post_dsr();
    
29. 
    
30. #endif   
    
31. 
    
32. #ifdef CYGDBG_KERNEL_DEBUG_GDB_THREAD_SUPPORT
    
33. 
    
34.     // If we have GDB support enabled, and there is the possibility
    
35.     // that this thread will be context switched as a result of this
    
36.     // interrupt, then save the pointer to the saved thread context in
    
37.     // the thread object so that GDB can get a meaningful context to
    
38.     // look at.
    
39.    
    
40.     Cyg_Scheduler::get_current_thread()->set_saved_context(regs);
    
41.    
    
42. #endif   
    
43.    
    
44.     // Now unlock the scheduler, which may also call DSRs
    
45.     // and cause a thread switch to happen.
    
46.         Cyg_Scheduler::unlock();
    
47.        
    
48. 
    
49.     Cyg_Scheduler::get_current_thread()->set_saved_context(0);
    
50.    
    
51. #endif   
    
52.    
    
53. 
    
54.     CYG_INSTRUMENT_INTR(RESTORE, vector, 0);   
    
55. }
    

复制代码

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

qfox

看明白了，原来一陷入isr就加锁了，不过这么定义符号还是第一次看到：
__asm__(#x)
还有这个
__attribute__ ((alias (#__symbol__)))
哪位给讲讲。谢谢

ssh_33

执行完第一步之后就是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

上来第一贴就挖坟，而且挖的这么有档次