[Cryptech-Commits] [sw/libhal] 06/12: Portable fix for ks_find() fencepost error.

git at cryptech.is git at cryptech.is
Fri Sep 16 19:53:14 UTC 2016


This is an automated email from the git hooks/post-receive script.

sra at hactrn.net pushed a commit to branch ksng
in repository sw/libhal.

commit 52bafc94397795e196aa516df044994692f4705f
Author: Rob Austein <sra at hactrn.net>
AuthorDate: Fri Sep 9 22:28:22 2016 -0400

    Portable fix for ks_find() fencepost error.
    
    Binary search of an array is a notorious example of a simple algorithm
    which is hard to get exactly right.  The variant we're using is nice
    because it automatically computes the correct insertion point when a
    key doesn't exist, but runs into one of the portability corner cases
    of signed integer arithemtic in C.  Rather than leave a landmine
    waiting to explode if somebody builds this code on a platform where
    (-1 >> 1) != -1, we test for the corner case explictly and accept the
    miniscule performance hit (which will be lost in other noise anyway).
---
 ks_index.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/ks_index.c b/ks_index.c
index c093a0a..f506a32 100644
--- a/ks_index.c
+++ b/ks_index.c
@@ -56,8 +56,8 @@ static int ks_find(const hal_ks_index_t * const ksi,
   int hi = ksi->used;
 
   for (;;) {
-    int m = (lo + hi) >> 1;
-    if (m == lo) {
+    int m = (lo + hi) / 2;
+    if (hi == 0 || m == lo) {
       *where = hi;
       return 0;
     }



More information about the Commits mailing list