Repository: Kotlin/kotlinx-io
Pull request #338 (2024-06-07 14:10:38)

Simplify evaluation of hex-encoded number's length
While preparing #337, I noticed that the way the length of the number to be encoded into a hexadecimal string could be significantly simplified. As a bonus, the clz-based version also works faster.

Moved the logic into a separate function to cover it with explicit tests.


Patch:
diff --git a/core/common/src/-Util.kt b/core/common/src/-Util.kt
index f7bbca2d..01848f02 100644
--- a/core/common/src/-Util.kt
+++ b/core/common/src/-Util.kt
@@ -171,3 +171,15 @@ internal fun Long.toHexString(): String {
 
     return result.concatToString(i, result.size)
 }
+
+/**
+ * Returns the number of characters required to encode [v]
+ * as a hexadecimal number without leading zeros (with `v == 0L` being the only exception,
+ * `hexNumberLength(0) == 1`).
+ */
+internal inline fun hexNumberLength(v: Long): Int {
+    if (v == 0L) return 1
+    val exactWidth = (Long.SIZE_BITS - v.countLeadingZeroBits())
+    // Round up to the nearest full nibble
+    return ((exactWidth + 3) / 4)
+}
diff --git a/core/common/src/Sinks.kt b/core/common/src/Sinks.kt
index ac3d193f..3bb82ff5 100644
--- a/core/common/src/Sinks.kt
+++ b/core/common/src/Sinks.kt
@@ -149,27 +149,7 @@ public fun Sink.writeHexadecimalUnsignedLong(long: Long) {
         return
     }
 
-    // Mask every bit below the most significant bit to a 1
-    // http://aggregate.org/MAGIC/#Most%20Significant%201%20Bit
-    var x = v
-    x = x or (x ushr 1)
-    x = x or (x ushr 2)
-    x = x or (x ushr 4)
-    x = x or (x ushr 8)
-    x = x or (x ushr 16)
-    x = x or (x ushr 32)
-
-    // Count the number of 1s
-    // http://aggregate.org/MAGIC/#Population%20Count%20(Ones%20Count)
-    x -= x ushr 1 and 0x5555555555555555
-    x = (x ushr 2 and 0x3333333333333333) + (x and 0x3333333333333333)
-    x = (x ushr 4) + x and 0x0f0f0f0f0f0f0f0f
-    x += x ushr 8
-    x += x ushr 16
-    x = (x and 0x3f) + ((x ushr 32) and 0x3f)
-
-    // Round up to the nearest full byte
-    val width = ((x + 3) / 4).toInt()
+    val width = hexNumberLength(v)
 
     writeToInternalBuffer { buffer ->
         val tail = buffer.writableSegment(width)


Test patch:
diff --git a/core/common/test/UtilsTest.kt b/core/common/test/UtilsTest.kt
new file mode 100644
index 00000000..392dc7ba
--- /dev/null
+++ b/core/common/test/UtilsTest.kt
@@ -0,0 +1,42 @@
+/*
+ * Copyright 2010-2024 JetBrains s.r.o. and Kotlin Programming Language contributors.
+ * Use of this source code is governed by the Apache 2.0 license that can be found in the LICENSE.txt file.
+ */
+
+package kotlinx.io
+
+import kotlin.test.Test
+import kotlin.test.assertEquals
+
+class UtilsTest {
+    @Test
+    fun hexNumberLength() {
+        val num2length: Map<Long, Int> = mapOf(
+            0x1L to 1,
+            0x10L to 2,
+            0x100L to 3,
+            0x1000L to 4,
+            0x10000L to 5,
+            0x100000L to 6,
+            0x1000000L to 7,
+            0x10000000L to 8,
+            0x100000000L to 9,
+            0x1000000000L to 10,
+            0x10000000000L to 11,
+            0x100000000000L to 12,
+            0x1000000000000L to 13,
+            0x10000000000000L to 14,
+            0x100000000000000L to 15,
+            0x1000000000000000L to 16,
+            -1L to 16,
+            0x3fL to 2,
+            0x7fL to 2,
+            0xffL to 2,
+            0L to 1
+        )
+
+        num2length.forEach { (num, length) ->
+            assertEquals(length, hexNumberLength(num), "Wrong length for 0x${num.toString(16)}")
+        }
+    }
+}