Python 上的 reals 套件 (需要 3.10+ 以上才能裝)

看到「A lightweight python3 library for arithmetic with real numbers.」這個有趣的 Python 延伸套件,可以用他進行高精度的實數運算...

一開始在 Python 3.9 環境裝,結果就跳出需要 3.10+ 的環境,想了一下,開了一個 Docker container 裝 pyenv 來測,測過以後覺得還蠻有趣的,看起來之後把預設環境變成 3.10+ 應該會裝起來用...

這個 reals 的重點在於保證顯示數字的正確性:

It allows you to compute approximations to an arbitrary degree of precision, and, contrary to most other libraries, guarantees that all digits it displays are correct.

目前支援的常數與操作有這些:

Constants: pi, e, phi
Functions related to powers: sqrt, exp, log
Operators: negation, addition, subtraction, multiplication, division, powers
Trigonometric functions: sin, sinh, csc, csch, cos, cosh, sec, sech, tan, tanh, cot, coth

用法的部份,先把 reals 拉進來:

>>> from reals import sqrt

然後用法算直覺:

>>> sqrt2 = sqrt(2)
>>> sqrt2
<reals._real.Real object at 0x10d182560 (approximate value: 1.41421)>
>>> sqrt2.evaluate(10)
'1.4142135624'
>>> '{:.10f}'.format(sqrt2)
'1.4142135624'
>>> sqrt2.to_decimal(10)
Decimal('1.4142135624')

不過作者有提到效能沒有處理到很好,所以應該是拿來快速做一些運算得到結果而已。

JavaScript 上的 fuzzy search library

Hacker News Daily 上看到 Show HN (作者自己或是主要的 contributor 上來發表的作品) 給了一個號稱速度很快,吃資源很少的 fuzzy search library:「Show HN: uFuzzy.js – A tiny, efficient fuzzy search that doesn't suck (github.com/leeoniya)」。

這種已經發展許久,但突然有一天有人說他的東西超好超棒棒的,除非是有新的基礎演算法突破,不然馬上就會想到很經典的「Three circles model」,中間的那些區塊就懶的畫上去了:

依照他的「測試」,可以看到他宣稱完全領先的狀態:

但回過頭來看評論:

Thank you for this!

I am also quite frustrated with the current state of full text search in the javascript world. All libs I've tried miss the most basic examples and their community seems to ignore it. Will give yours a try but it already looks much better from the comparison page.

Edit: Nope, your lib doesn't seem to handle substitution well (THE most common type of typo), so yep, we are back to square one ...

From fuzzy search I expected that entering "super meet boy" or "super maet boy" will return "Super Meat Boy" but unfortunately currently it doesn't work this way and it's quite disappointing.

https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...

看起來這個 library 沒有辦法解決 fuzzy search 最常見的 case (小 typo),依照範例描述的更像是 substring 搜尋加上一些額外的的功能,反而比較像是 auto completion library,或是講的比較廣一點,可以算是 auto suggestion library。

不過我覺得真正的重點 (對我來說的重點) 是下面的比較表格,因為列出了目前市場上的方案,這份清單之後可以拿來參考...

這次 OpenSSL 的兩個 CVE

難得在 Hacker News 首頁上看到 OpenSSLCVE:「OpenSSL Security Advisory [5 July 2022]」,相關的討論在「OpenSSL Security Advisory (openssl.org)」。

第一個 CVE 是 RCE 等級,但觸發條件有點多:

首先是 RSA 2048bits,這個條件應該算容易發生的。

第二個是,因為這個安全問題是因為 OpenSSL 3.0.4 才引入的程式碼,而 OpenSSL 3.0.4 是 2022/06/21 發表的,未必有很多人有升級。

第三個是,因為這次出包的段落是用到了 AVX-512 指令集,一定要 Intel 或是 Centaur 的 CPU,後面這家公司前身就是威盛 (VIA) 的一員,去年賣給了 Intel (然後發現連官網用的 domain 都沒續約...)。

AMD 雖然在 Zen 4 架構上支援 AVX-512,但還沒推出產品,所以直接閃避 XD

另外第三個還有額外的限制,因為這次用到的是 IFMA 指令集,所以也不是所有有支援 AVX-512 的 CPU 都會中獎:

只看 Intel 的部份,第一個支援 IFMA 的是 2018 年推出的 Cannon Lake,這個架構只有一顆行動版的 Intel® Core™ i3-8121U Processor

真正大量支援 IFMA 的是 2019 後的 Intel CPU 了,但到了去年推出的 Alder Lake 因為 E-core 不支援 AVX-512 的關係 (但 P-core 支援),預設又關掉了。

所以如果問這個 bug 嚴不嚴重,當然是很嚴重,但影響範圍就有點微妙了。

接下來講第二個 CVE,是 AES OCB 的實做問題,比較有趣的地方是 Hacker News 上的討論引出了 Mosh 的作者跳出來說明,他居然提到他們在二月的時候試著換到 OpenSSL 的 AES OCB 時有測出這個 bug,被 test case 擋下來了:

Mosh uses AES-OCB (and has since 2011), and we found this bug when we tried to switch over to the OpenSSL implementation (away from our own ocb.cc taken from the original authors) and Launchpad ran it through our CI testsuite as part of the Mosh dev PPA build for i686 Ubuntu. (It wasn't caught by GitHub Actions because it only happens on 32-bit x86.) https://github.com/mobile-shell/mosh/issues/1174 for more.

So I would say (a) OCB is widely used, at least by the ~million Mosh users on various platforms, and (b) this episode somewhat reinforces my (perhaps overweight already) paranoia about depending on other people's code or the blast radius of even well-meaning pull requests. (We really wanted to switch over to the OpenSSL implementation rather than shipping our own, in part because ours was depending on some OpenSSL AES primitives that OpenSSL recently deprecated for external users.)

Maybe one lesson here is that many people believe in the benefits of unit tests for their own code, but we're not as thorough or experienced in writing acceptance tests for our dependencies.

Mosh got lucky this time that we had pretty good tests that exercised the library enough to find this bug, and we run them as part of the package build, but it's not that farfetched to imagine that we might have users on a platform that we don't build a package for (and therefore don't run our testsuite on).

這有點有趣 XDDD

Perl 的 Regular Expression 的強度:NP-complete

這篇稍微偏 CS 理論一些...

以前在學校學 Formal language 的時候會帶出 Grammer、Language、Automaton 三個項目,就像是維基百科上的條列:

裡面可以看到經典的 Regular expression 會被分到 RG/RL/FSM 這三塊。

前幾天看到 gugod 寫的「[Perl] 以正規表示式來定義文法規則」這篇,裡面試著用 Perlregular expression (perlre) 建構「遞歸下降解析器」 (Recursive descent parser)。

Recursive descent parser 可以當作是 CFG 的子集合,而 CFG 對應到的語言是 CFL,另外他對應到的自動機是 PDA

我們已經知道 perlre 因為支援一堆奇怪的東西 (像是 backreference 或是 recursive pattern),所以他能接受的 language 已經超過 RL,但我很好奇他能夠做到什麼程度。

用搜尋引擎翻了翻,查到對 PCRE 的分析 (這是一套與 Perl regular expression 語法相容的 library):「Which languages do Perl-compatible regular expressions recognize?」。

在裡面有人提到「The true power of regular expressions」這篇文章,裡面給了一個在 PTIME 演算法,將 3SAT 轉換到 PCRE 裡解,這證明了 PCRE 是 NP-hard;另外也很容易確認 PCRE 是 NP,所以就達成了 NP-complete 的條件了...

本來一直以為 PCRE 只是 CFG/CFL/PDA 而已,沒想到這麼強,NPC 表示大多數現有的演算法都可以轉成 PCRE 形式放進去跑... XD

Python 裡使用超過 Double Precision 的運算

Hacker News 上爬到的,是一篇 2019 的文章:「When Double Precision Is Not Enough (adambaskerville.github.io)」,原文在「T>T: When Double Precision is Not Enough」。

作者是拿矩陣 (matrix) 的運算當例子,遇到了 double precision 造成的計算誤差問題:

There is no error with the program; this discrepancy is caused by a loss of numerical accuracy in the eigenvalue calculation due to the limitation of hardware double precision (16-digit).

解法是用 mpmath 增加精度,算是一種暴力解,到要注意計算會慢很多:

Note that this library is incredibly slow for large matrices, so is best avoided for most applications.

另外在 Hacker News 的討論串裡面看到個有趣的東西:「Herbie: Automatically Improving Floating Point Accuracy」這個專案,你把公式丟進去,Herbie 會試著提供等價公式來維持精度,像是 \sqrt{x+1} - \sqrt{x} = 1 / ( \sqrt{x+1} + \sqrt{x} ) 這種東西。

半自動化幫你改善...

Libmill:在 C 裡面仿造 Go 的 concurrency 架構

Hacker News 首頁上看到的專案:「Libmill is a library that introduces Go-style concurrency to C.」。

使用上的設計可以看到就是用 Golang 裡面的設計,另外在網頁下方也有提到「libdill: Structured Concurrency for C」,就不是用 Golang 的設計,但是有同樣的功能性...

兩者都是 MIT/X11 license,大多數的專案用起來應該沒什麼問題,底層應該都是用 select() 或是 poll() 來實做就是了?

把 SQLite 的 VFS 掛上 WebTorrent 的 PoC Demo

Hacker News Daily 上看到「Static torrent website with peer-to-peer queries over BitTorrent on 2M records (boredcaveman.xyz)」這個討論,作者試著在網頁上跑 SQLite + VFS + WebTorrent

這好像是這陣子一連串的 combo 技累積出來的東西:

  • 首先當然是把 SQLite 丟到網頁上跑的「sql.js」,這個專案比較久了,2019 年有第一個 release;
  • 然後最近有人透過 HTTP Range (Byte serving) 實做 SQLite VFS 的「sql.js-httpvfs」,這樣就不需要一次下載整包 SQLite;

接下來就是文章作者把 HTTP Range 換掉,改用 BitTorrent 的 pieces 來處理,在網頁端的話就順勢拿 WebTorrent 來用,對於很熱門的網站來說還蠻有趣的設計,但也可以預期網頁的反應速度應該不會太快,偏 PoC...

修正 Curl 的 TLS handshake,避開 bot 偵測機制

利用 TLS handshake 的 pattern 可以當作是某種 fingerprint,就可以知道你是用 Curl,這個方式在蠻多 CDN 都會用在 anti-bot 機制 (像是 Cloudflare),而剛剛看到有人投稿自己的 patch,試著將 Curl 修改成 Firefox 的 pattern:「curl-impersonate」,Hacker News 上的討論在這邊可以看到:「Show HN: Curl modified to impersonate Firefox and mimic its TLS handshake (github.com/lwthiker)」。

作者有提到這次的 patch 偏 hack,不太可能整進上游,但希望未來改的乾淨一點,然後整進上游:

I hope to do so in the future, for now the implementation is extremely hacky so I doubt it can get accepted into curl.

另外有人提出來說應該要用 Firefox ESR 版本的 pattern 而非 stable channel,也有人提出來說用 Google Chrome 的更好,不過我覺得有人開始做就已經很棒了 XD

用 Exodus 打包 Linux ELF 檔案到其他機器上

前幾天在 Hacker News Daily 上看到的工具:「Exodus」,官方的說明是這樣:

Painless relocation of Linux binaries–and all of their dependencies–without containers.

技術上是把 Linux ELF 檔案搬到其他機器上以外,也幫你把對應的 dynamic library 都一起包進去:

  • Finding and bundling all of a binary's dependencies.
  • Launching the binary in such a way that the proper dependencies are used without any potential interaction from system libraries on the destination machine.

而 Linux 的 Kernel 因為有儘量維持 ABI compatibility,應該是不會有太大的問題,除非剛好用到新的 API...

看起來是個除了用 static compile 以外的解法,好像可以來弄弄看 FFmpeg

LLVM 的更換授權進展

Hacker News Daily 上看到「LLVM relicensing update & call for help」這篇,在講 LLVM 計畫從 UIUC licenseMIT license 授權轉成 Apache License 2.0 的進展,在 Hacker News 上的討論「LLVM relicensing update and call for help (llvm.org)」也可以翻一下。

目前的規劃是這樣:

文章開頭還是先花了一些篇幅解釋,這個計畫主要是要處理專利的問題,原先的 developer policy 對於專利的句子太粗糙,會授權過多的權力給 LLVM。這對於一般個人可能影響不大,但對於手上有一卡車專利的公司來說就不太願意了。

另外一個問題是 LLVM 遇到的問題,因為 runtime library 的部份是用 UIUC license + MIT license 授權,但主體是用 UIUC license 授權,這使得主體的程式碼不能隨意搬到 runtime library 裡面:

The run time libraries were dual licensed under the UIUC and MIT license; the rest of the code only under the UIUC license. Therefore, we could not easily move code to run time libraries from other parts. The reason run time libraries were dual licensed was to enable linking to run time library binaries without requiring attribution to LLVM.

因為這些目標,所以新的授權會是 Apache License 2.0 為主,裡面有設計還算合理的專利授權條件,另外大家也算熟悉,再來是針對 object code 以及 GPLv2 設計了例外條款:

As an exception, if, as a result of your compiling your source code, portions of this Software are embedded into an Object form of such source code, you may redistribute such embedded portions in such Object form without complying with the conditions of Sections 4(a), 4(b) and 4(d) of the License.

In addition, if you combine or link compiled forms of this Software with software that is licensed under the GPLv2 ("Combined Software") and if a court of competent jurisdiction determines that the patent provision (Section 3), the indemnity provision (Section 9) or other Section of the License conflicts with the conditions of the GPLv2, you may retroactively and prospectively choose to deem waived or otherwise exclude such Section(s) of the License, but only in their entirety and only with respect to the Combined Software.

在「Long tail of individuals and corporations without a relicensing agreement yet」這邊有目前還沒有同意重新授權的人以及團隊的資料,看起來不會是每個人都願意重新授權,到時候可能還得再挑出來重寫,但有些可以獨立出來的可能可以維持,畢竟 UIUC licesne 與 MIT license 都是 permissive license,只要放到另外一個目錄下,大家知道不是 Apache License 2.0 就還好...