linux-ext4 - binary search in ext4_ext_binsearch

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Message-ID: <1270697176.21760.27.camel@minskey-desktop>
Date:	Thu, 08 Apr 2010 11:26:16 +0800
From:	minskey <chaohong_guo@...ux.intel.com>
To:	linux-ext4@...r.kernel.org
Subject: binary search in ext4_ext_binsearch_idx()



in ext4_ext_binsearch_idx() routine, there is the following code:

 while (l <= r) {
                m = l + (r - l) / 2;
                if (block < le32_to_cpu(m->ei_block))
                        r = m - 1;
                else
                        l = m + 1;
 }

 path->p_idx = l - 1;

The code always runs logN iterations to get the expected extent,
if 3-way comparison is used, we can save some iterations when 
(block == le32_to_cpu(m->ei_block)) at the first iteration.

some other routines, such as ext4_ext_binsearch() etc, use the
same algorithm (2-way comparison), Is there any special goal ? 



thanks,
-minskey




--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html