1 // SPDX-License-Identifier: LGPL-2.1-or-later 1 // SPDX-License-Identifier: LGPL-2.1-or-later
2 /* 2 /*
3 * Provides fixed-point logarithm operations. 3 * Provides fixed-point logarithm operations.
4 * 4 *
5 * Copyright (C) 2006 Christoph Pfister (chris 5 * Copyright (C) 2006 Christoph Pfister (christophpfister@gmail.com)
6 */ 6 */
7 7
8 #include <linux/bitops.h> 8 #include <linux/bitops.h>
9 #include <linux/export.h> 9 #include <linux/export.h>
10 #include <linux/int_log.h> 10 #include <linux/int_log.h>
11 #include <linux/kernel.h> 11 #include <linux/kernel.h>
12 #include <linux/types.h> 12 #include <linux/types.h>
13 13
14 #include <asm/bug.h> 14 #include <asm/bug.h>
15 15
16 static const unsigned short logtable[256] = { 16 static const unsigned short logtable[256] = {
17 0x0000, 0x0171, 0x02e0, 0x044e, 0x05ba 17 0x0000, 0x0171, 0x02e0, 0x044e, 0x05ba, 0x0725, 0x088e, 0x09f7,
18 0x0b5d, 0x0cc3, 0x0e27, 0x0f8a, 0x10eb 18 0x0b5d, 0x0cc3, 0x0e27, 0x0f8a, 0x10eb, 0x124b, 0x13aa, 0x1508,
19 0x1664, 0x17bf, 0x1919, 0x1a71, 0x1bc8 19 0x1664, 0x17bf, 0x1919, 0x1a71, 0x1bc8, 0x1d1e, 0x1e73, 0x1fc6,
20 0x2119, 0x226a, 0x23ba, 0x2508, 0x2656 20 0x2119, 0x226a, 0x23ba, 0x2508, 0x2656, 0x27a2, 0x28ed, 0x2a37,
21 0x2b80, 0x2cc8, 0x2e0f, 0x2f54, 0x3098 21 0x2b80, 0x2cc8, 0x2e0f, 0x2f54, 0x3098, 0x31dc, 0x331e, 0x345f,
22 0x359f, 0x36de, 0x381b, 0x3958, 0x3a94 22 0x359f, 0x36de, 0x381b, 0x3958, 0x3a94, 0x3bce, 0x3d08, 0x3e41,
23 0x3f78, 0x40af, 0x41e4, 0x4319, 0x444c 23 0x3f78, 0x40af, 0x41e4, 0x4319, 0x444c, 0x457f, 0x46b0, 0x47e1,
24 0x4910, 0x4a3f, 0x4b6c, 0x4c99, 0x4dc5 24 0x4910, 0x4a3f, 0x4b6c, 0x4c99, 0x4dc5, 0x4eef, 0x5019, 0x5142,
25 0x526a, 0x5391, 0x54b7, 0x55dc, 0x5700 25 0x526a, 0x5391, 0x54b7, 0x55dc, 0x5700, 0x5824, 0x5946, 0x5a68,
26 0x5b89, 0x5ca8, 0x5dc7, 0x5ee5, 0x6003 26 0x5b89, 0x5ca8, 0x5dc7, 0x5ee5, 0x6003, 0x611f, 0x623a, 0x6355,
27 0x646f, 0x6588, 0x66a0, 0x67b7, 0x68ce 27 0x646f, 0x6588, 0x66a0, 0x67b7, 0x68ce, 0x69e4, 0x6af8, 0x6c0c,
28 0x6d20, 0x6e32, 0x6f44, 0x7055, 0x7165 28 0x6d20, 0x6e32, 0x6f44, 0x7055, 0x7165, 0x7274, 0x7383, 0x7490,
29 0x759d, 0x76aa, 0x77b5, 0x78c0, 0x79ca 29 0x759d, 0x76aa, 0x77b5, 0x78c0, 0x79ca, 0x7ad3, 0x7bdb, 0x7ce3,
30 0x7dea, 0x7ef0, 0x7ff6, 0x80fb, 0x81ff 30 0x7dea, 0x7ef0, 0x7ff6, 0x80fb, 0x81ff, 0x8302, 0x8405, 0x8507,
31 0x8608, 0x8709, 0x8809, 0x8908, 0x8a06 31 0x8608, 0x8709, 0x8809, 0x8908, 0x8a06, 0x8b04, 0x8c01, 0x8cfe,
32 0x8dfa, 0x8ef5, 0x8fef, 0x90e9, 0x91e2 32 0x8dfa, 0x8ef5, 0x8fef, 0x90e9, 0x91e2, 0x92db, 0x93d2, 0x94ca,
33 0x95c0, 0x96b6, 0x97ab, 0x98a0, 0x9994 33 0x95c0, 0x96b6, 0x97ab, 0x98a0, 0x9994, 0x9a87, 0x9b7a, 0x9c6c,
34 0x9d5e, 0x9e4f, 0x9f3f, 0xa02e, 0xa11e 34 0x9d5e, 0x9e4f, 0x9f3f, 0xa02e, 0xa11e, 0xa20c, 0xa2fa, 0xa3e7,
35 0xa4d4, 0xa5c0, 0xa6ab, 0xa796, 0xa881 35 0xa4d4, 0xa5c0, 0xa6ab, 0xa796, 0xa881, 0xa96a, 0xaa53, 0xab3c,
36 0xac24, 0xad0c, 0xadf2, 0xaed9, 0xafbe 36 0xac24, 0xad0c, 0xadf2, 0xaed9, 0xafbe, 0xb0a4, 0xb188, 0xb26c,
37 0xb350, 0xb433, 0xb515, 0xb5f7, 0xb6d9 37 0xb350, 0xb433, 0xb515, 0xb5f7, 0xb6d9, 0xb7ba, 0xb89a, 0xb97a,
38 0xba59, 0xbb38, 0xbc16, 0xbcf4, 0xbdd1 38 0xba59, 0xbb38, 0xbc16, 0xbcf4, 0xbdd1, 0xbead, 0xbf8a, 0xc065,
39 0xc140, 0xc21b, 0xc2f5, 0xc3cf, 0xc4a8 39 0xc140, 0xc21b, 0xc2f5, 0xc3cf, 0xc4a8, 0xc580, 0xc658, 0xc730,
40 0xc807, 0xc8de, 0xc9b4, 0xca8a, 0xcb5f 40 0xc807, 0xc8de, 0xc9b4, 0xca8a, 0xcb5f, 0xcc34, 0xcd08, 0xcddc,
41 0xceaf, 0xcf82, 0xd054, 0xd126, 0xd1f7 41 0xceaf, 0xcf82, 0xd054, 0xd126, 0xd1f7, 0xd2c8, 0xd399, 0xd469,
42 0xd538, 0xd607, 0xd6d6, 0xd7a4, 0xd872 42 0xd538, 0xd607, 0xd6d6, 0xd7a4, 0xd872, 0xd93f, 0xda0c, 0xdad9,
43 0xdba5, 0xdc70, 0xdd3b, 0xde06, 0xded0 43 0xdba5, 0xdc70, 0xdd3b, 0xde06, 0xded0, 0xdf9a, 0xe063, 0xe12c,
44 0xe1f5, 0xe2bd, 0xe385, 0xe44c, 0xe513 44 0xe1f5, 0xe2bd, 0xe385, 0xe44c, 0xe513, 0xe5d9, 0xe69f, 0xe765,
45 0xe82a, 0xe8ef, 0xe9b3, 0xea77, 0xeb3b 45 0xe82a, 0xe8ef, 0xe9b3, 0xea77, 0xeb3b, 0xebfe, 0xecc1, 0xed83,
46 0xee45, 0xef06, 0xefc8, 0xf088, 0xf149 46 0xee45, 0xef06, 0xefc8, 0xf088, 0xf149, 0xf209, 0xf2c8, 0xf387,
47 0xf446, 0xf505, 0xf5c3, 0xf680, 0xf73e 47 0xf446, 0xf505, 0xf5c3, 0xf680, 0xf73e, 0xf7fb, 0xf8b7, 0xf973,
48 0xfa2f, 0xfaea, 0xfba5, 0xfc60, 0xfd1a 48 0xfa2f, 0xfaea, 0xfba5, 0xfc60, 0xfd1a, 0xfdd4, 0xfe8e, 0xff47,
49 }; 49 };
50 50
51 unsigned int intlog2(u32 value) 51 unsigned int intlog2(u32 value)
52 { 52 {
53 /** 53 /**
54 * returns: log2(value) * 2^24 54 * returns: log2(value) * 2^24
55 * wrong result if value = 0 (log 55 * wrong result if value = 0 (log2(0) is undefined)
56 */ 56 */
57 unsigned int msb; 57 unsigned int msb;
58 unsigned int logentry; 58 unsigned int logentry;
59 unsigned int significand; 59 unsigned int significand;
60 unsigned int interpolation; 60 unsigned int interpolation;
61 61
62 if (unlikely(value == 0)) { 62 if (unlikely(value == 0)) {
63 WARN_ON(1); 63 WARN_ON(1);
64 return 0; 64 return 0;
65 } 65 }
66 66
67 /* first detect the msb (count begins 67 /* first detect the msb (count begins at 0) */
68 msb = fls(value) - 1; 68 msb = fls(value) - 1;
69 69
70 /** 70 /**
71 * now we use a logtable after th 71 * now we use a logtable after the following method:
72 * 72 *
73 * log2(2^x * y) * 2^24 = x * 2^2 73 * log2(2^x * y) * 2^24 = x * 2^24 + log2(y) * 2^24
74 * where x = msb and therefore 1 74 * where x = msb and therefore 1 <= y < 2
75 * first y is determined by shift 75 * first y is determined by shifting the value left
76 * so that msb is bit 31 76 * so that msb is bit 31
77 * 0x00231f56 -> 0x8C7D58 77 * 0x00231f56 -> 0x8C7D5800
78 * the result is y * 2^31 -> "sig 78 * the result is y * 2^31 -> "significand"
79 * then the highest 9 bits are us 79 * then the highest 9 bits are used for a table lookup
80 * the highest bit is discarded b 80 * the highest bit is discarded because it's always set
81 * the highest nine bits in our e 81 * the highest nine bits in our example are 100011000
82 * so we would use the entry 0x18 82 * so we would use the entry 0x18
83 */ 83 */
84 significand = value << (31 - msb); 84 significand = value << (31 - msb);
85 logentry = (significand >> 23) % ARRAY 85 logentry = (significand >> 23) % ARRAY_SIZE(logtable);
86 86
87 /** 87 /**
88 * last step we do is interpolati 88 * last step we do is interpolation because of the
89 * limitations of the log table t 89 * limitations of the log table the error is that part of
90 * the significand which isn't us 90 * the significand which isn't used for lookup then we
91 * compute the ratio between the 91 * compute the ratio between the error and the next table entry
92 * and interpolate it between the 92 * and interpolate it between the log table entry used and the
93 * next one the biggest error pos 93 * next one the biggest error possible is 0x7fffff
94 * (in our example it's 0x7D5800) 94 * (in our example it's 0x7D5800)
95 * needed value for next table en 95 * needed value for next table entry is 0x800000
96 * so the interpolation is 96 * so the interpolation is
97 * (error / 0x800000) * (logtable 97 * (error / 0x800000) * (logtable_next - logtable_current)
98 * in the implementation the divi 98 * in the implementation the division is moved to the end for
99 * better accuracy there is also 99 * better accuracy there is also an overflow correction if
100 * logtable_next is 256 100 * logtable_next is 256
101 */ 101 */
102 interpolation = ((significand & 0x7fff 102 interpolation = ((significand & 0x7fffff) *
103 ((logtable[(logentry + 103 ((logtable[(logentry + 1) % ARRAY_SIZE(logtable)] -
104 logtable[logentry]) 104 logtable[logentry]) & 0xffff)) >> 15;
105 105
106 /* now we return the result */ 106 /* now we return the result */
107 return ((msb << 24) + (logtable[logent 107 return ((msb << 24) + (logtable[logentry] << 8) + interpolation);
108 } 108 }
109 EXPORT_SYMBOL(intlog2); 109 EXPORT_SYMBOL(intlog2);
110 110
111 unsigned int intlog10(u32 value) 111 unsigned int intlog10(u32 value)
112 { 112 {
113 /** 113 /**
114 * returns: log10(value) * 2^24 114 * returns: log10(value) * 2^24
115 * wrong result if value = 0 (log 115 * wrong result if value = 0 (log10(0) is undefined)
116 */ 116 */
117 u64 log; 117 u64 log;
118 118
119 if (unlikely(value == 0)) { 119 if (unlikely(value == 0)) {
120 WARN_ON(1); 120 WARN_ON(1);
121 return 0; 121 return 0;
122 } 122 }
123 123
124 log = intlog2(value); 124 log = intlog2(value);
125 125
126 /** 126 /**
127 * we use the following method: 127 * we use the following method:
128 * log10(x) = log2(x) * log10(2) 128 * log10(x) = log2(x) * log10(2)
129 */ 129 */
130 130
131 return (log * 646456993) >> 31; 131 return (log * 646456993) >> 31;
132 } 132 }
133 EXPORT_SYMBOL(intlog10); 133 EXPORT_SYMBOL(intlog10);
134 134
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.