<p>laforge has uploaded this change for <strong>review</strong>.</p><p><a href="https://gerrit.osmocom.org/c/libosmocore/+/21562">View Change</a></p><pre style="font-family: monospace,monospace; white-space: pre-wrap;">hash/log2: Add generic implementations of fls() and fls64()<br><br>When importing the hashtable code in I8ef73a62fe9846ce45058eb21cf999dd3eed5741<br>I didn't import actual implementations of the fls() and fls64()<br>implementations, as at least gcc-10 was smart enough to detect<br>we only use it on constant types and hence the computation can happen<br>at build time via const_ilog2()<br><br>However, in our jenkins build verification' this doesn't appear to<br>happen, as we get below errors:<br><br>/build/deps/install/stow/libosmocore/include/osmocom/core/log2.h: In function ‘__ilog2_u32’:<br>/build/deps/install/stow/libosmocore/include/osmocom/core/log2.h:20:9: error: implicit declaration of function ‘fls’ [-Werror=implicit-function-declaration]<br> return fls(n) - 1;<br> ^~~<br>/build/deps/install/stow/libosmocore/include/osmocom/core/log2.h: In function ‘__ilog2_u64’:<br>/build/deps/install/stow/libosmocore/include/osmocom/core/log2.h:28:9: error: implicit declaration of function ‘fls64’ [-Werror=implicit-function-declaration]<br> return fls64(n) - 1;<br> ^~~~~<br><br>Let's provide some generic implementations for this case. If needed<br>one could also introduce architecture-specific assembly implementations<br>like in the Linux kernel, but so far we managed to keep libosmocore free<br>of any assembly tweaks.<br><br>Change-Id: Ifa4898eb66c8d949618edd47961b7a0330ed35b5<br>---<br>M include/osmocom/core/log2.h<br>1 file changed, 59 insertions(+), 0 deletions(-)<br><br></pre><pre style="font-family: monospace,monospace; white-space: pre-wrap;">git pull ssh://gerrit.osmocom.org:29418/libosmocore refs/changes/62/21562/1</pre><pre style="font-family: monospace,monospace; white-space: pre-wrap;"><span>diff --git a/include/osmocom/core/log2.h b/include/osmocom/core/log2.h</span><br><span>index 06b20f8..dfe9d37 100644</span><br><span>--- a/include/osmocom/core/log2.h</span><br><span>+++ b/include/osmocom/core/log2.h</span><br><span>@@ -6,6 +6,65 @@</span><br><span> */</span><br><span> </span><br><span> #pragma once</span><br><span style="color: hsl(120, 100%, 40%);">+#define __always_inline inline __attribute__((always_inline))</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/* from linux/asm-generic/bitops/{fls,fls64}.h - could later be enhanced</span><br><span style="color: hsl(120, 100%, 40%);">+ * with architecture specific optimized versions */</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/**</span><br><span style="color: hsl(120, 100%, 40%);">+ * fls - find last (most-significant) bit set</span><br><span style="color: hsl(120, 100%, 40%);">+ * @x: the word to search</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * This is defined the same way as ffs.</span><br><span style="color: hsl(120, 100%, 40%);">+ * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+static __always_inline int fls(unsigned int x)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ int r = 32;</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+ if (!x)</span><br><span style="color: hsl(120, 100%, 40%);">+ return 0;</span><br><span style="color: hsl(120, 100%, 40%);">+ if (!(x & 0xffff0000u)) {</span><br><span style="color: hsl(120, 100%, 40%);">+ x <<= 16;</span><br><span style="color: hsl(120, 100%, 40%);">+ r -= 16;</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+ if (!(x & 0xff000000u)) {</span><br><span style="color: hsl(120, 100%, 40%);">+ x <<= 8;</span><br><span style="color: hsl(120, 100%, 40%);">+ r -= 8;</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+ if (!(x & 0xf0000000u)) {</span><br><span style="color: hsl(120, 100%, 40%);">+ x <<= 4;</span><br><span style="color: hsl(120, 100%, 40%);">+ r -= 4;</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+ if (!(x & 0xc0000000u)) {</span><br><span style="color: hsl(120, 100%, 40%);">+ x <<= 2;</span><br><span style="color: hsl(120, 100%, 40%);">+ r -= 2;</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+ if (!(x & 0x80000000u)) {</span><br><span style="color: hsl(120, 100%, 40%);">+ x <<= 1;</span><br><span style="color: hsl(120, 100%, 40%);">+ r -= 1;</span><br><span style="color: hsl(120, 100%, 40%);">+ }</span><br><span style="color: hsl(120, 100%, 40%);">+ return r;</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span style="color: hsl(120, 100%, 40%);">+</span><br><span style="color: hsl(120, 100%, 40%);">+/**</span><br><span style="color: hsl(120, 100%, 40%);">+ * fls64 - find last set bit in a 64-bit word</span><br><span style="color: hsl(120, 100%, 40%);">+ * @x: the word to search</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * This is defined in a similar way as the libc and compiler builtin</span><br><span style="color: hsl(120, 100%, 40%);">+ * ffsll, but returns the position of the most significant set bit.</span><br><span style="color: hsl(120, 100%, 40%);">+ *</span><br><span style="color: hsl(120, 100%, 40%);">+ * fls64(value) returns 0 if value is 0 or the position of the last</span><br><span style="color: hsl(120, 100%, 40%);">+ * set bit if value is nonzero. The last (most significant) bit is</span><br><span style="color: hsl(120, 100%, 40%);">+ * at position 64.</span><br><span style="color: hsl(120, 100%, 40%);">+ */</span><br><span style="color: hsl(120, 100%, 40%);">+static __always_inline int fls64(__u64 x)</span><br><span style="color: hsl(120, 100%, 40%);">+{</span><br><span style="color: hsl(120, 100%, 40%);">+ __u32 h = x >> 32;</span><br><span style="color: hsl(120, 100%, 40%);">+ if (h)</span><br><span style="color: hsl(120, 100%, 40%);">+ return fls(h) + 32;</span><br><span style="color: hsl(120, 100%, 40%);">+ return fls(x);</span><br><span style="color: hsl(120, 100%, 40%);">+}</span><br><span> </span><br><span> /*</span><br><span> * non-constant log of base 2 calculators</span><br><span></span><br></pre><p>To view, visit <a href="https://gerrit.osmocom.org/c/libosmocore/+/21562">change 21562</a>. To unsubscribe, or for help writing mail filters, visit <a href="https://gerrit.osmocom.org/settings">settings</a>.</p><div itemscope itemtype="http://schema.org/EmailMessage"><div itemscope itemprop="action" itemtype="http://schema.org/ViewAction"><link itemprop="url" href="https://gerrit.osmocom.org/c/libosmocore/+/21562"/><meta itemprop="name" content="View Change"/></div></div>
<div style="display:none"> Gerrit-Project: libosmocore </div>
<div style="display:none"> Gerrit-Branch: master </div>
<div style="display:none"> Gerrit-Change-Id: Ifa4898eb66c8d949618edd47961b7a0330ed35b5 </div>
<div style="display:none"> Gerrit-Change-Number: 21562 </div>
<div style="display:none"> Gerrit-PatchSet: 1 </div>
<div style="display:none"> Gerrit-Owner: laforge <laforge@osmocom.org> </div>
<div style="display:none"> Gerrit-MessageType: newchange </div>