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 import std.traits : isPointer;
17 /**
18 * Power of 2 test. T should be an uinteger type
19 * Params:
20 *  arg = an integer value
21 * Returns: true iff arg is 2^n for some n > 0
22 */
23 bool isPowerOf2(T)(T arg)
24     if (!isPointer!T)
25 {
26     return ((arg != 0 && arg != 1) && ((arg & (arg-1)) == 0));
27 }
28 
29 /**
30 * Return the index of the highest set bit
31 * T is an uinteger type
32 * Params:
33 *  n = an integer value
34 * Returns: index of the highest set bit in n
35 */
36 size_t highBit(T)(T n)
37     if (!isPointer!T)
38 {
39     for (size_t i = 8*T.sizeof; i > 0; --i)
40         if ((n >> (i - 1)) & 0x01)
41             return i;
42     return 0;
43 }
44 
45 /**
46 * Return the index of the lowest set bit
47 * T is an uinteger type
48 * Params:
49 *  n = an integer value
50 * Returns: index of the lowest set bit in n
51 */
52 size_t lowBit(T)(T n)
53     if (!isPointer!T)
54 {
55     for (size_t i = 0; i != 8*T.sizeof; ++i)
56         if ((n >> i) & 0x01)
57             return (i + 1);
58     return 0;
59 }
60 
61 /**
62 * Return the number of significant bytes in n
63 * Params:
64 *  n = an integer value
65 * Returns: number of significant bytes in n
66 */
67 size_t significantBytes(T)(T n)
68     if (!isPointer!T)
69 {
70     for (size_t i = 0; i != T.sizeof; ++i)
71         if (get_byte(i, n))
72             return T.sizeof-i;
73     return 0;
74 }
75 
76 /**
77 * Compute Hamming weights
78 * Params:
79 *  n = an integer value
80 * Returns: number of bits in n set to 1
81 */
82 size_t hammingWeight(T)(T n)
83     if (!isPointer!T)
84 {
85     __gshared immutable ubyte[] NIBBLE_WEIGHTS = [
86         0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 ];
87 
88     size_t weight = 0;
89     for (size_t i = 0; i != 2*T.sizeof; ++i)
90         weight += NIBBLE_WEIGHTS[(n >> (4*i)) & 0x0F];
91     return weight;
92 }
93 
94 /**
95 * Count the trailing zero bits in n
96 * Params:
97 *  n = an integer value
98 * Returns: maximum x st 2^x divides n
99 */
100 size_t ctz(T)(T n)
101     if (!isPointer!T)
102 {
103     for (size_t i = 0; i != 8*T.sizeof; ++i)
104         if ((n >> i) & 0x01)
105             return i;
106     return 8*T.sizeof;
107 }