我摸魚寫的Java代碼意外稱霸StackOverflow十年：有bug

編譯：奇安信代碼衛士團隊

Stack Overflow 上有一個 Java 代碼片段稱霸十年，是 Java 開發人員最愛複製的片段。超過6000個 GitHub Java 項目中複製並內嵌了該代碼，遠超 Stack Overflow 上的其它Java 片段。該片段的作者本尊Andreas Lundblad 剛剛發佈博客文章來修 bug 了……

很久以前，久到離譜……

那還是在2010年，當時我在辦公室摸魚，去Stack Overflow 上精簡精簡代碼，看看自己得到多少小星星。

突然，我看到了一個提問：如何才能把 Java 中的字節數數變成人類可讀的格式呢？通俗地講一下，就是如何把 123,456,789 字節這樣的格式轉化成“123.5MB”？

這裡的隱含規範是，格式化後的字符串的值應該介於1到999.9之間，然後跟一個大小適當的後綴。

當時已經有人給出了一個答案。答案中的代碼基於循環。它的思路很簡單：try 所有大小，從最大（EB=1-18字節）到最小（B=1字節），然後使用小於字節數的第一個數。用偽代碼表示一下就是：

suffixes = [ "EB", "PB", "TB", "GB", "MB", "kB", "B" ]
magnitudes = [ 1018, 1015, 1012, 109, 106, 103, 100 ]
i = 0
while (i < magnitudes.length && magnitudes[i] > byteCount)
 i++
printf("%.1f %s", byteCount / magnitudes[i], suffixes[i])

一般來說，如果已經發布的正確答案的分數為正，那麼別人很難追上。在 Stack Overflow 術語中，這種情況被叫做“西部問題快槍手 (Fastest Gun in the West Problem)”。從本案例來看，因為現有答案確實存在一些缺陷，因此我還有機會反超。至少我還可以大幅度清理下循環代碼。

代數神助攻

靈感來了。kB、MB、GB等等什麼的不就是1000的冪（或者 IEC 標準中的1024）嗎？也就是說我可以使用對數而不是循環來計算正確的後綴是什麼。

基於這個思路，我給出了自己的答案：

public static String humanReadableByteCount(long bytes, boolean si) {
 int unit = si ? 1000 : 1024;
 if (bytes < unit) return bytes + " B";
 int exp = (int) (Math.log(bytes) / Math.log(unit));
 String pre = (si ? "kMGTPE" : "KMGTPE").charAt(exp-1) + (si ? "" : "i");
 return String.format("%.1f %sB", bytes / Math.pow(unit, exp), pre);
}

當然，我寫的代碼可讀性並不高，而且 log/pow 可能使效率遜色於其它解決方案。但它的優點在於沒有循環、幾乎沒有分支，所以我覺得挺整潔的。

解釋下背後的數學知識，其實挺簡單的。字節計數表示為 byteCount = 1000s，其中s 表示比例尺（二進制表示法中，使用基數1024）。求解 s 得出 s = log1000 (byteCount)。API 中沒有現成可用的 log1000，但是我們可以用自然對數表示為 s=log(byteCount)/log(1000)。之後給出s的下限（轉換為整型），因為如果出現的情況是，比如大於1的兆字節 (MB)（但並非完整的千兆字節），則希望使用 MB 作為大小。

此時，如果 s=1，則比例尺為千字節，如果s=2則比例尺為兆字節，以此類推。我們將 byteCount 除以1000，然後在相應的字母前綴上做文章。

提交答案後，我只要靜等大家對它的滿意度就行了。然而，我萬萬沒料到它之後竟然能成為 Stack Overflow 上被複制次數最多的代碼片段。

研究代碼署名問題的論文來了

時間快進到2018年。一位名叫Sebastian Baltes 的博士在《實證性軟件工程》期刊上發表了一篇名為《GitHub 項目對 Stack Overflow 代碼片段的使用和署名問題》的論文，它解決的是這樣一個問題：複製代碼時是否尊重Stack Overflow 的 CC BY-SA 3.0 許可證？也就是說從 Stack Overflow 上覆制代碼時，應該如何分配署名情況？

他們在分析中從Stack Overflow 數據轉出中提取了一些代碼片段，並將其和 GitHub 公開庫中的代碼進行匹配。論文摘要如下：

“我們分析了GitHub (GH) 項目中源自 Stack Overflow 上大量 Java 代碼片段的使用和署名問題，並給出大規模的實證研究結果。”（提前劇透：多數人在使用時候並未給出署名。）

他們在論文中給出如下表格：

排在第一名的id 為3758880的答案碰巧就是我在8年前給出的那個答案。此時答案的瀏覽量已經超過10萬次，收穫的贊也超過1000個。

在GitHub 上搜一下確實能看到數千次有關 humanReadableByteCount 的結果。

你可以在本地發出的倉庫中查看下自己是否用了這段代碼：

$ git grep humanReadableByteCount

插播有趣的相遇故事：我是怎麼了解到這項研究的？Sebastian 從 OpenJDK 倉庫中找到一個匹配結果。其中並沒有署名來源而且 OpenJDK 許可證並不兼容 CC BY-SA 3.0。他於是找到運維郵件列表詢問 Stack Overflow 上的這段代碼是否是從 OpenJDK 複製的，還是有其它情況。

有意思的是，我曾在甲骨文工作，碰巧也是在 OpenJDK 項目組。於是我的前同事也是朋友就回復他說：

你好，

你為啥不直接問Stack Overflow 帖子的作者 (aioobe) 呢？他也是 OpenJDK 的奉獻者而且他在甲骨文工作時把這段代碼寫在了 OpenJDK 源倉庫中。

甲骨文並未掉以輕心。我碰巧知道甲骨文的一些人看到這個答覆時鬆了一口氣，而且在受到“指責”後簡直可以說是喜上眉梢。

Sebastian 之後就直接找我詢問，我答覆他說：我發佈帖子時還未入職甲骨文，而且我並未負責那個補丁。和甲骨文開玩笑啦。之後不久這個問題就被提交給 OpenJDK，代碼也被移除了。

Bug 來了

我猜你肯定在想，這個代碼片段中的 bug 到底是什麼啊？

我們再來看下：

public static String humanReadableByteCount(long bytes, boolean si) {
 int unit = si ? 1000 : 1024;
 if (bytes < unit) return bytes + " B";
 int exp = (int) (Math.log(bytes) / Math.log(unit));
 String pre = (si ? "kMGTPE" : "KMGTPE").charAt(exp-1) + (si ? "" : "i");
 return String.format("%.1f %sB", bytes / Math.pow(unit, exp), pre);
}

1018兆兆字節之後是1021澤字節。有沒有這樣一種可能：輸入一個很大很大的數時，會導致“Kmgtpe”字符串索引超出範圍？並不會。因為最大的 long 值是 263-1≈9.2×1018 ，因此任何 long值都不會超出 EB範圍。

那 SI 和二進制之間會不會混淆？也不會。早期的答案版本有混淆情況但很快就被修復了。

那麼 exp 以0 結尾會不會導致charAt(exp-1) 失敗？也不會。第一個 if 語句涵蓋了這種情況。 exp 的值將始終至少為1。

那麼是不是輸出結果中出現了詭異的舍入錯誤？好吧，我們來看看……

很多個9

這個答案一直都運行正常，直到 1MB時出問題了。當輸入是999,999時，結果（SI 模式）是“1000.0kB”。雖然999,999確實更接近1,000x 10001而不是999.9 x10001 ，但根據標準要求，1,000 的“有效位數”超出了範圍。正確的結果應該是“1.0MB”。

不管咋樣，所有發佈的22個答案，包括使用 Apache Commons 和 Android 庫的答案中在本文成文時都存在這個 bug（或其變體）。

那麼我們如何修復這個問題呢？首先我們注意到，一旦字節數更接近1×1,0002 (1 MB)而非999.9×10001 (999.9 k)，那麼指數 (exp) 就應該儘快從“k”轉變為“M”。這種情況會在 999,950 時發生。同樣，我們應該在超過 999,959,000時，將“M”切換為“G”，以此類推。

為此，我們計算得出這個閾值並且如果 bytes 更大時，則增加exp：

if (bytes >= Math.pow(unit, exp) * (unit - 0.05))
 exp++;

更改後，代碼運行正常，但到了 1EB 又出問題了。

更多的9

如果輸入999,949,999,999,999,999，那麼現在的結果就是1000.0 PB，但正確結果應該是999.9 PB。從數學上來說，這個代碼結果是準確的，但到底出啥問題了？

這時就有必要看看double 的精度侷限性了。

浮點算術101

按照IEEE 754 標準表示的接近0的浮點數值非常密集而大值非常稀疏。實際上超過一半的值都介於-1和1之間，當談論大的 double 時，實際上像Long.MAX_VALUE 這樣的值毫無意義。

double l1 = Double.MAX_VALUE;
double l2 = l1 - Long.MAX_VALUE;
System.err.println(l1 == l2); // prints true

更多深入講解可見：https://programming.guide/bits-of-a-floating-point-value.html。

這裡存在兩個有問題的計算：

• String.format 參數中的除法，以及
• 增加 exp 的閾值

我們可以切換到BigDecimal，但這樣做還有啥樂趣！另外，由於標準 API 中並不存在BigDecimal 日誌函數，因此會搞得一團糟。

縮小中間值

對於第一個問題，我們將字節值縮小到精度更好的範圍，並且對exp 進行相應的調整。最終結果都是四捨五入的，因此我們丟掉最低的有效數字也沒事。

if (exp > 4) {
 bytes /= unit;
 exp--;
}

調整最低有效位

至於第二個問題，我們確實需要注意最低有效位（999,949,99…9 和999,950,00…0應該以不同的指數結尾），因此該問題要求使用其它解決方案。

首先，我們注意到閾值有12種不同的可能值（每種模式為6種），並且其中只有一個會出現問題。我們可以通過以 D0016 結尾的事實來唯一識別這個出問題的值。如果真是這樣，那麼我們只要將其調整為正確的值即可。

long th = (long) (Math.pow(unit, exp) * (unit - 0.05));
if (exp < 6 && bytes >= th - ((th & 0xFFF) == 0xD00 ? 52 : 0))
 exp++;

由於我們依賴浮點結果中的特定位模式，因此我們調整了 strictfp 來確保其不受硬件運行代碼的影響。

負值輸入

目前尚不清楚在什麼情況下會輸入負的字節計數，但既然 Java 中並沒有無符號的 long，那麼我們最好也把這個問題解決了。現在，如果輸入 -10,000，那麼結果是 -10000 B。

我們來看下absBytes：

long absBytes = bytes == Long.MIN_VALUE ? Long.MAX_VALUE : Math.abs(bytes);

這個複雜的表達式是由 -Long.MIN_VALUE == Long.MIN_VALUE 的事實造成的。現在我們使用 absBytes 而非 bytes 來執行和 exp 有關的所有運算。

最終版本

這是該代碼的最終版，本著原始版本的精神進行了精簡：

// From: https://programming.guide/the-worlds-most-copied-so-snippet.html
public static strictfp String humanReadableByteCount(long bytes, boolean si) {
 int unit = si ? 1000 : 1024;
 long absBytes = bytes == Long.MIN_VALUE ? Long.MAX_VALUE : Math.abs(bytes);
 if (absBytes < unit) return bytes + " B";
 int exp = (int) (Math.log(absBytes) / Math.log(unit));
 long th = (long) (Math.pow(unit, exp) * (unit - 0.05));
 if (exp < 6 && absBytes >= th - ((th & 0xfff) == 0xd00 ? 52 : 0)) exp++;
 String pre = (si ? "kMGTPE" : "KMGTPE").charAt(exp - 1) + (si ? "" : "i");
 if (exp > 4) {
 bytes /= unit;
 exp -= 1;
 }
 return String.format("%.1f %sB", bytes / Math.pow(unit, exp), pre);
}

需要注意的是，這個代碼片段的初衷是避免使用循環和過多的分支。經過把所有的情況一一考慮進去後，它的可讀性更差了。我個人並不會把這個代碼片段複製到生產代碼中。

不過我更新了一個可以用於生產代碼的版本，如下：

SI(1 k = 1,000)

public static String humanReadableByteCountSI(long bytes) {
 String s = bytes < 0 ? "-" : "";
 long b = bytes == Long.MIN_VALUE ? Long.MAX_VALUE : Math.abs(bytes);
 return b < 1000L ? bytes + " B"
 : b < 999_950L ? String.format("%s%.1f kB", s, b / 1e3)
 : (b /= 1000) < 999_950L ? String.format("%s%.1f MB", s, b / 1e3)
 : (b /= 1000) < 999_950L ? String.format("%s%.1f GB", s, b / 1e3)
 : (b /= 1000) < 999_950L ? String.format("%s%.1f TB", s, b / 1e3)
 : (b /= 1000) < 999_950L ? String.format("%s%.1f PB", s, b / 1e3)
 : String.format("%s%.1f EB", s, b / 1e6);
}

Binary (1 K =1,024)

public static String humanReadableByteCountBin(long bytes) {
 long b = bytes == Long.MIN_VALUE ? Long.MAX_VALUE : Math.abs(bytes);
 return b < 1024L ? bytes + " B" 

 : b < 0xfffccccccccccccL >> 40 ? String.format("%.1f KiB", bytes / 0x1p10)
 : b < 0xfffccccccccccccL >> 30 ? String.format("%.1f MiB", bytes / 0x1p20)
 : b < 0xfffccccccccccccL >> 20 ? String.format("%.1f GiB", bytes / 0x1p30)
 : b < 0xfffccccccccccccL >> 10 ? String.format("%.1f TiB", bytes / 0x1p40)
 : b < 0xfffccccccccccccL ? String.format("%.1f PiB", (bytes >> 10) / 0x1p40)
 : String.format("%.1f EiB", (bytes >> 20) / 0x1p40);
}

示例

幾個啟發

• Stack Overflow 上的代碼片段可能有 bug，即使獲贊數千的答案也不例外。
• 測試所有邊緣情況，尤其對於代碼是從 Stack Overflow 上覆制的情況。
• 浮點運算很難。
• 複製代碼時請包括適當的歸屬說明。不然可能有人會找你喲。

原文鏈接：https://www.anquanke.com/post/id/194307

閱讀更多 安全客 的文章

關鍵字: 數學 摸魚 Stack