fec509a05ddbf645268fe2e537314def7d1b67c8gm * CDDL HEADER START
fec509a05ddbf645268fe2e537314def7d1b67c8gm * The contents of this file are subject to the terms of the
fec509a05ddbf645268fe2e537314def7d1b67c8gm * Common Development and Distribution License (the "License").
fec509a05ddbf645268fe2e537314def7d1b67c8gm * You may not use this file except in compliance with the License.
fec509a05ddbf645268fe2e537314def7d1b67c8gm * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
fec509a05ddbf645268fe2e537314def7d1b67c8gm * See the License for the specific language governing permissions
fec509a05ddbf645268fe2e537314def7d1b67c8gm * and limitations under the License.
fec509a05ddbf645268fe2e537314def7d1b67c8gm * When distributing Covered Code, include this CDDL HEADER in each
fec509a05ddbf645268fe2e537314def7d1b67c8gm * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
fec509a05ddbf645268fe2e537314def7d1b67c8gm * If applicable, add the following below this CDDL HEADER, with the
fec509a05ddbf645268fe2e537314def7d1b67c8gm * fields enclosed by brackets "[]" replaced with your own identifying
fec509a05ddbf645268fe2e537314def7d1b67c8gm * information: Portions Copyright [yyyy] [name of copyright owner]
fec509a05ddbf645268fe2e537314def7d1b67c8gm * CDDL HEADER END
fec509a05ddbf645268fe2e537314def7d1b67c8gm * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
fec509a05ddbf645268fe2e537314def7d1b67c8gm * Use is subject to license terms.
fec509a05ddbf645268fe2e537314def7d1b67c8gm#pragma ident "%Z%%M% %I% %E% SMI"
fec509a05ddbf645268fe2e537314def7d1b67c8gm * This whole file is really doing floating point type stuff, and
fec509a05ddbf645268fe2e537314def7d1b67c8gm * would be quite simple in user space. But since we are in the
fec509a05ddbf645268fe2e537314def7d1b67c8gm * kernel, (a) we can't use floating point, and (b) we don't have a
fec509a05ddbf645268fe2e537314def7d1b67c8gm * math library.
fec509a05ddbf645268fe2e537314def7d1b67c8gm/* used inside msb */
fec509a05ddbf645268fe2e537314def7d1b67c8gm * returns the position of the MSB of x. The 1 bit is position 0. An
fec509a05ddbf645268fe2e537314def7d1b67c8gm * all zero arg returns -1.
fec509a05ddbf645268fe2e537314def7d1b67c8gm if (x == 0) {
fec509a05ddbf645268fe2e537314def7d1b67c8gm return (-1);
fec509a05ddbf645268fe2e537314def7d1b67c8gm * lg2 computes 2^(LOG_VAL_SCALE) * log2(x/2^LOG_ARG_SCALE), where ^
fec509a05ddbf645268fe2e537314def7d1b67c8gm * is exponentiation.
fec509a05ddbf645268fe2e537314def7d1b67c8gm * The following conditions must be satisfied: LOG_VAL_SCALE <= 62,
fec509a05ddbf645268fe2e537314def7d1b67c8gm * LOG_VAL_SCALE + log2(maxarg) < 64, LOG_VAL_SCALE >= 0,
fec509a05ddbf645268fe2e537314def7d1b67c8gm * LOG_ARG_SCALE <= 63. Recommended LOG_VAL_SCALE is 57, which is the
fec509a05ddbf645268fe2e537314def7d1b67c8gm * largest value such that overflow is impossible.
fec509a05ddbf645268fe2e537314def7d1b67c8gm * logtable[i-1] == round(2^63 * log2(2^i/(2^i - 1))), where ^
fec509a05ddbf645268fe2e537314def7d1b67c8gm * is exponentiation.
fec509a05ddbf645268fe2e537314def7d1b67c8gm 24785312098ULL, 12392656043ULL, 6196328020ULL, 3098164010ULL,
fec509a05ddbf645268fe2e537314def7d1b67c8gm 96817625ULL, 48408813ULL, 24204406ULL, 12102203ULL, 6051102ULL,
fec509a05ddbf645268fe2e537314def7d1b67c8gm 94548ULL, 47274ULL, 23637ULL, 11819ULL, 5909ULL, 2955ULL,
fec509a05ddbf645268fe2e537314def7d1b67c8gm if (x == 0) {
fec509a05ddbf645268fe2e537314def7d1b67c8gm * Invariant: log2(xx) + logx == log2(x). This is true at the after
fec509a05ddbf645268fe2e537314def7d1b67c8gm * the normalization. At each adjustment step we multiply xx by
fec509a05ddbf645268fe2e537314def7d1b67c8gm * (2^i-1)/2^i, which effectively decreases log2(xx) by
fec509a05ddbf645268fe2e537314def7d1b67c8gm * log2(2^i/(2^i-1)), and a the same time, we add table[i], which
fec509a05ddbf645268fe2e537314def7d1b67c8gm * equals log2(2^i/(2^i-1)), to logx. By induction the invariant is
fec509a05ddbf645268fe2e537314def7d1b67c8gm * true at the end. At the end xx==1, so log2(xx)==0, and thus
fec509a05ddbf645268fe2e537314def7d1b67c8gm * logx=log2(x);
fec509a05ddbf645268fe2e537314def7d1b67c8gm /* Normalize */
fec509a05ddbf645268fe2e537314def7d1b67c8gm if (i - LOG_ARG_SCALE > 0) {
fec509a05ddbf645268fe2e537314def7d1b67c8gm /* 1ULL << (i-1) is rounding */
fec509a05ddbf645268fe2e537314def7d1b67c8gm /* 1ULL << (63 - LOG_VAL_SCALE -1) is rounding */
fec509a05ddbf645268fe2e537314def7d1b67c8gm * The EXCHANGE macro swaps entries j & k if necessary so that
fec509a05ddbf645268fe2e537314def7d1b67c8gm * data[j] <= data[k].
fec509a05ddbf645268fe2e537314def7d1b67c8gm * If OBLIVIOUS is defined, no branches are used. This would allow
fec509a05ddbf645268fe2e537314def7d1b67c8gm * this algorithm to be used by the CPU manufacturing people who run
fec509a05ddbf645268fe2e537314def7d1b67c8gm * on a tester that requires the exact same instruction address stream
fec509a05ddbf645268fe2e537314def7d1b67c8gm * on every test. (It's a bit slower with OBLIVIOUS defined.)
fec509a05ddbf645268fe2e537314def7d1b67c8gm mask = (uint64_t)(((int64_t)(data[k] - data[j])) >> 63); \
fec509a05ddbf645268fe2e537314def7d1b67c8gm * This is a Batcher sort from Knuth v. 3. There is no flow control
fec509a05ddbf645268fe2e537314def7d1b67c8gm * that depends on the values being sorted, except in the EXCHANGE
fec509a05ddbf645268fe2e537314def7d1b67c8gm * step, but that can be made oblivious to the data values, too, by
fec509a05ddbf645268fe2e537314def7d1b67c8gm * setting OBLIVIOUS. So this code could be using in chip testers
fec509a05ddbf645268fe2e537314def7d1b67c8gm * that require fixed flow through a test.
fec509a05ddbf645268fe2e537314def7d1b67c8gm * This is presently hard-coded for sorting uint64_t values.
fec509a05ddbf645268fe2e537314def7d1b67c8gm int p, q, d, r, i;
fec509a05ddbf645268fe2e537314def7d1b67c8gm if ((i & p) == r) {
fec509a05ddbf645268fe2e537314def7d1b67c8gm d = q - p;
fec509a05ddbf645268fe2e537314def7d1b67c8gm * Computes several measures of entropy per word: Renyi H0 (log2 of
fec509a05ddbf645268fe2e537314def7d1b67c8gm * number of distinct symbols), Renyi H1 (Shannon),
fec509a05ddbf645268fe2e537314def7d1b67c8gm * Renyi H2 (-log2 of sum(P_i^2)), and
fec509a05ddbf645268fe2e537314def7d1b67c8gm * Renyi H-infinity (min). The results are coded as H *
fec509a05ddbf645268fe2e537314def7d1b67c8gm * 2^LOG_VAL_SCALE). The samples array is modified by sorting in
fec509a05ddbf645268fe2e537314def7d1b67c8gm * None if this is really valid, since it requres that the block
fec509a05ddbf645268fe2e537314def7d1b67c8gm * length be at least as long as the largest non-approximately-zero
fec509a05ddbf645268fe2e537314def7d1b67c8gm * coefficient in the autocorrelation function, and that the number
fec509a05ddbf645268fe2e537314def7d1b67c8gm * of samples be much larger than 2^longest_block_length_in_bits.
fec509a05ddbf645268fe2e537314def7d1b67c8gm * But we hope that bigger is better, even when it is invalid.
fec509a05ddbf645268fe2e537314def7d1b67c8gmn2rng_renyi_entropy(uint64_t *samples, int lg2samples, n2rng_osc_perf_t *entp)
fec509a05ddbf645268fe2e537314def7d1b67c8gm#endif /* COMPUTE_SHANNON_ENTROPY */
fec509a05ddbf645268fe2e537314def7d1b67c8gm /* process last block */
fec509a05ddbf645268fe2e537314def7d1b67c8gm ((int64_t)(LOG_ARG_SCALE - lg2samples) << LOG_VAL_SCALE))) >>
fec509a05ddbf645268fe2e537314def7d1b67c8gm#endif /* COMPUTE_SHANNON_ENTROPY */
fec509a05ddbf645268fe2e537314def7d1b67c8gm /* H1 is shannon entropy: -sum(p_i * log2(p_i)) */
fec509a05ddbf645268fe2e537314def7d1b67c8gm /* H2 is -log2(sum p_i^2) */
fec509a05ddbf645268fe2e537314def7d1b67c8gm ((int64_t)(LOG_ARG_SCALE - 2 * lg2samples) << LOG_VAL_SCALE)) / 64;
fec509a05ddbf645268fe2e537314def7d1b67c8gm /* Hinf = -log2(highest_probability) */