botan.utils.bit_ops source code

1 /**
2 * Bit/Word Operations
3 * 
4 * Copyright:
5 * (C) 1999-2008 Jack Lloyd
6 * (C) 2014-2015 Etienne Cimon
7 *
8 * License:
9 * Botan is released under the Simplified BSD License (see LICENSE.md)
10 */
11 module botan.utils.bit_ops;
12 
13 import botan.constants;
14 import botan.utils.get_byte;
15 import botan.utils.types;
16 /**
17 * Power of 2 test. T should be an uinteger type
18 * Params:
19 *  arg = an integer value
20 * Returns: true iff arg is 2^n for some n > 0
21 */
22 bool isPowerOf2(T)(T arg)
23 {
24     return ((arg != 0 && arg != 1) && ((arg & (arg-1)) == 0));
25 }
26 
27 /**
28 * Return the index of the highest set bit
29 * T is an uinteger type
30 * Params:
31 *  n = an integer value
32 * Returns: index of the highest set bit in n
33 */
34 size_t highBit(T)(T n)
35 {
36     for (size_t i = 8*T.sizeof; i > 0; --i)
37         if ((n >> (i - 1)) & 0x01)
38             return i;
39     return 0;
40 }
41 
42 /**
43 * Return the index of the lowest set bit
44 * T is an uinteger type
45 * Params:
46 *  n = an integer value
47 * Returns: index of the lowest set bit in n
48 */
49 size_t lowBit(T)(T n)
50 {
51     for (size_t i = 0; i != 8*T.sizeof; ++i)
52         if ((n >> i) & 0x01)
53             return (i + 1);
54     return 0;
55 }
56 
57 /**
58 * Return the number of significant bytes in n
59 * Params:
60 *  n = an integer value
61 * Returns: number of significant bytes in n
62 */
63 size_t significantBytes(T)(T n)
64 {
65     for (size_t i = 0; i != T.sizeof; ++i)
66         if (get_byte(i, n))
67             return T.sizeof-i;
68     return 0;
69 }
70 
71 /**
72 * Compute Hamming weights
73 * Params:
74 *  n = an integer value
75 * Returns: number of bits in n set to 1
76 */
77 size_t hammingWeight(T)(T n)
78 {
79     __gshared immutable ubyte[] NIBBLE_WEIGHTS = [
80         0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 ];
81 
82     size_t weight = 0;
83     for (size_t i = 0; i != 2*T.sizeof; ++i)
84         weight += NIBBLE_WEIGHTS[(n >> (4*i)) & 0x0F];
85     return weight;
86 }
87 
88 /**
89 * Count the trailing zero bits in n
90 * Params:
91 *  n = an integer value
92 * Returns: maximum x st 2^x divides n
93 */
94 size_t ctz(T)(T n)
95 {
96     for (size_t i = 0; i != 8*T.sizeof; ++i)
97         if ((n >> i) & 0x01)
98             return i;
99     return 8*T.sizeof;
100 }