1 // SPDX-License-Identifier: LGPL-2.1-or-later 1
2 /*
3 * Provides fixed-point logarithm operations.
4 *
5 * Copyright (C) 2006 Christoph Pfister (chris
6 */
7
8 #include <linux/bitops.h>
9 #include <linux/export.h>
10 #include <linux/int_log.h>
11 #include <linux/kernel.h>
12 #include <linux/types.h>
13
14 #include <asm/bug.h>
15
16 static const unsigned short logtable[256] = {
17 0x0000, 0x0171, 0x02e0, 0x044e, 0x05ba
18 0x0b5d, 0x0cc3, 0x0e27, 0x0f8a, 0x10eb
19 0x1664, 0x17bf, 0x1919, 0x1a71, 0x1bc8
20 0x2119, 0x226a, 0x23ba, 0x2508, 0x2656
21 0x2b80, 0x2cc8, 0x2e0f, 0x2f54, 0x3098
22 0x359f, 0x36de, 0x381b, 0x3958, 0x3a94
23 0x3f78, 0x40af, 0x41e4, 0x4319, 0x444c
24 0x4910, 0x4a3f, 0x4b6c, 0x4c99, 0x4dc5
25 0x526a, 0x5391, 0x54b7, 0x55dc, 0x5700
26 0x5b89, 0x5ca8, 0x5dc7, 0x5ee5, 0x6003
27 0x646f, 0x6588, 0x66a0, 0x67b7, 0x68ce
28 0x6d20, 0x6e32, 0x6f44, 0x7055, 0x7165
29 0x759d, 0x76aa, 0x77b5, 0x78c0, 0x79ca
30 0x7dea, 0x7ef0, 0x7ff6, 0x80fb, 0x81ff
31 0x8608, 0x8709, 0x8809, 0x8908, 0x8a06
32 0x8dfa, 0x8ef5, 0x8fef, 0x90e9, 0x91e2
33 0x95c0, 0x96b6, 0x97ab, 0x98a0, 0x9994
34 0x9d5e, 0x9e4f, 0x9f3f, 0xa02e, 0xa11e
35 0xa4d4, 0xa5c0, 0xa6ab, 0xa796, 0xa881
36 0xac24, 0xad0c, 0xadf2, 0xaed9, 0xafbe
37 0xb350, 0xb433, 0xb515, 0xb5f7, 0xb6d9
38 0xba59, 0xbb38, 0xbc16, 0xbcf4, 0xbdd1
39 0xc140, 0xc21b, 0xc2f5, 0xc3cf, 0xc4a8
40 0xc807, 0xc8de, 0xc9b4, 0xca8a, 0xcb5f
41 0xceaf, 0xcf82, 0xd054, 0xd126, 0xd1f7
42 0xd538, 0xd607, 0xd6d6, 0xd7a4, 0xd872
43 0xdba5, 0xdc70, 0xdd3b, 0xde06, 0xded0
44 0xe1f5, 0xe2bd, 0xe385, 0xe44c, 0xe513
45 0xe82a, 0xe8ef, 0xe9b3, 0xea77, 0xeb3b
46 0xee45, 0xef06, 0xefc8, 0xf088, 0xf149
47 0xf446, 0xf505, 0xf5c3, 0xf680, 0xf73e
48 0xfa2f, 0xfaea, 0xfba5, 0xfc60, 0xfd1a
49 };
50
51 unsigned int intlog2(u32 value)
52 {
53 /**
54 * returns: log2(value) * 2^24
55 * wrong result if value = 0 (log
56 */
57 unsigned int msb;
58 unsigned int logentry;
59 unsigned int significand;
60 unsigned int interpolation;
61
62 if (unlikely(value == 0)) {
63 WARN_ON(1);
64 return 0;
65 }
66
67 /* first detect the msb (count begins
68 msb = fls(value) - 1;
69
70 /**
71 * now we use a logtable after th
72 *
73 * log2(2^x * y) * 2^24 = x * 2^2
74 * where x = msb and therefore 1
75 * first y is determined by shift
76 * so that msb is bit 31
77 * 0x00231f56 -> 0x8C7D58
78 * the result is y * 2^31 -> "sig
79 * then the highest 9 bits are us
80 * the highest bit is discarded b
81 * the highest nine bits in our e
82 * so we would use the entry 0x18
83 */
84 significand = value << (31 - msb);
85 logentry = (significand >> 23) % ARRAY
86
87 /**
88 * last step we do is interpolati
89 * limitations of the log table t
90 * the significand which isn't us
91 * compute the ratio between the
92 * and interpolate it between the
93 * next one the biggest error pos
94 * (in our example it's 0x7D5800)
95 * needed value for next table en
96 * so the interpolation is
97 * (error / 0x800000) * (logtable
98 * in the implementation the divi
99 * better accuracy there is also
100 * logtable_next is 256
101 */
102 interpolation = ((significand & 0x7fff
103 ((logtable[(logentry +
104 logtable[logentry])
105
106 /* now we return the result */
107 return ((msb << 24) + (logtable[logent
108 }
109 EXPORT_SYMBOL(intlog2);
110
111 unsigned int intlog10(u32 value)
112 {
113 /**
114 * returns: log10(value) * 2^24
115 * wrong result if value = 0 (log
116 */
117 u64 log;
118
119 if (unlikely(value == 0)) {
120 WARN_ON(1);
121 return 0;
122 }
123
124 log = intlog2(value);
125
126 /**
127 * we use the following method:
128 * log10(x) = log2(x) * log10(2)
129 */
130
131 return (log * 646456993) >> 31;
132 }
133 EXPORT_SYMBOL(intlog10);
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.