_ALGORITHM ALLEY_
by John DeVos
edited by Bruce Schneier


Listing One


/* log2.h  */
/* Prototypes */
long log2K (int);

/* Defines & Macros  */
#define LOG2_ERROR                      666L    /* Impossible result  */
#define BASE_FACTOR                     16384
#define BASE_SHIFT                      14

#define ERR_C1                          242     /* PA * BASE_FACTOR  */
#define ERR_C2                          726     /* 3 * ERR_C1        */

/* log2K -- Returns the log-base-2 of the argument relative to
BASE_FACTOR. If the parameter is not positive, it returns a defined
impossible result. */

long log2K (int x) {
int j, hiBitPos, C1, C2;
long L0;
        if (x <= 0) return LOG2_ERROR;
/* Zero-order estimate  */
        j = 1;
        while (x >> j++);
        hiBitPos = j - 2;
        j = 1 << hiBitPos;                      /* j = 2 ^ hiBitPos(x)  */
        L0 = (long)hiBitPos << BASE_SHIFT;
        if (x == j) return L0;                  /* Catch powers of 2    */

/* First correction */
        C1 = (int)(((((long)x - j) * 3) << BASE_SHIFT) / ((log)x + j));
/* Second correction */
        j >>= 1;                /* j = 2 ^ (hiBit(x) - 1) */
        C2 = (int)(((long)x * ERR_C1) / j) - ERR_C2;
        C2 = ERR_C1 - (int)(((long)C2 * C2) / ERR_C1);
        return (L0 + C1 - C2);
}