2026-09-09 — Ladybird 8 月進度全面轉向 Rust、滑板車韌體逆向重寫、Bitap 位元比對演算法拆解

Ladybird 瀏覽器引擎 8 月進度：CSS 解析器全面改寫為 Rust、樣式引擎重構帶動效能跳升

ladybird.org · 2026-08-31

本月重點

Ladybird 核心團隊發布《This Month in Ladybird - August 2026》月報,彙整 2026 年 8 月的開發進度。媒體與排版能力同步補齊:Media Source Extensions 新增 fragmented MP4 下 AVC、HEVC、AV1 與 AAC 支援,讓 Twitch、Plex 得以正常播放;CSS 也補上 scroll-snap-type、scroll-snap-align、scroll-snap-stop,支援滾輪、鍵盤、觸控板與程式化捲動。

LibJS 這個月加入除錯器支援,具備中斷點、逐行執行與監看運算式,並對屬性存取、展開運算子、Promise 組合子等熱路徑做最佳化,使 JSON.stringify 效能與 V8 的差距縮小到 15% 以內。稀疏陣列處理的修正,也讓 Minecraft4k 測試遊戲的畫面更新率從 10.2 FPS 升到 14.5 FPS。

3D transform 新增 transform-style: flat 攤平模式與 backface-visibility,並用 BSP 樹處理相交平面深度排序
overflow-wrap 改為在字素邊界強制換行,避免切斷組合字元
下載功能支援暫停/續傳,單一下載最多 4 條平行連線
Ctrl+Shift+T 觸發的工作階段還原可跨重啟保留完整瀏覽紀錄

技術細節

本月最大的架構調整是樣式引擎重寫:新引擎把每次 DOM 異動視為一串具型別的差異(delta)事件流,只把變動增量式地轉發給真正依賴該節點的選擇器,取代過去整批重新比對 cascade 的做法。CSS 剖析器同時逐步從 C++ 遷移到 Rust,團隊用 A/B 測試讓新舊剖析器並行、比對輸出一致後才刪除舊碼(PR #11318 至 #11360);繪製管線的 display list 與 hit testing 也已 port 到 Rust(#11222)。

其他底層改動包括:JS 數值改採 NaN-boxing 並限制在 GC heap 特定區域、bytecode 儲存區改為唯讀、DOM 節點與其 JS wrapper 拆分以省記憶體,以及新增獨立的 WasmCompiler 服務搭配最小沙箱降低編譯延遲。基準測試大幅躍升:Speedometer 2 從 47 升到 64、Speedometer 3 從 2.5 升到 3.9,StyleBench 子項從 3.5 衝到 83,Canvas fillStyle 剖析則從落後 Chromium 90 倍縮到只差 2 倍。

瀏覽器(M3 MacBook)	StyleBench 分數
Chrome	103.8
Ladybird	116.3
Safari	129.5
Firefox	232.8

影響範圍

Ladybird 是從 SerenityOS 專案獨立出來的瀏覽器引擎,核心排版元件 LibWeb 與 JS 引擎 LibJS 均為自行實作,不依賴 Chromium、Gecko 或 WebKit 程式碼,目前是多程序架構並持續以 Rust 取代 C++ 元件。網站相容性列表持續擴大:Strava 活動地圖載入時間因兩次修正減半、記憶體洩漏從 17.8 GiB 降到 61 MiB;YouTube 影片卡片預覽當機、preload="none" 整頁凍結,以及 ChatGPT.com、VS Code Web 版因 pointer-events hit-testing 錯誤導致的當機也一併修復。

Web Platform Tests 通過子測試數從 2,079,020 增至 2,088,677,單月新增 9,657 項(對照 7 月僅增加 108 項)。專案收到一筆 5,000 美元新贊助,團隊重申 Alpha 版仍規劃於 2026 年內釋出,剩餘工作已從引擎功能轉為當機回報、簽章建置、自動更新等基礎設施項目。

原始來源:This Month in Ladybird - August 2026

拆解一台電動滑板車儀表板:從晶片鑑識到用 Rust 重寫韌體

bensimms.moe · 2026-08-09

原本的問題

開發者 Ben Simms 在部落格文章《Reverse engineering my e-scooter and rewriting the firmware in rust》記錄了他拆解一台 Egret GT 電動滑板車儀表主機板的過程。這台車的電控系統由多顆晶片分工,彼此卻缺乏任何公開文件:主控器是 APM32E103xCxE(Geehy 廠推出的 STM32F103 相容替代晶片),儀表另配一顆 AT32F415,藍牙模組是 CH573,NFC 讀卡用 FM17520,顯示面板控制器為 ST7796,外掛 SPI flash 為 W25Q128FV。

通訊協定同樣雜亂無章:整車跑一條不符標準規範的 CAN bus,訊號卻接在 USB-C 接腳上;藍牙走 UART、鮑率 57500;NFC 另一組 UART 跑 115200;按鍵面板又是獨立一條 9600 的 UART;顯示器與主控晶片間則是佔滿整個 GPIOB 埠的 16 位元並列介面,沒有用任何標準顯示匯流排協定。這種東拼西湊的設計,是逆向工程要面對的第一道障礙。

採用的方法

鑑識流程從硬體訊號分析開始:先用示波器觀察各組訊號腳位,再接上 USB-C breakout 板取出 CAN bus 訊號,並自製一塊以 ESP32-C6 搭配 SN65HVD230 CAN 收發器與 MCP2515 CAN 控制器的側錄裝置,長期紀錄行車時的封包。晶片內部程式碼靠 SWD 除錯埠取出:透過 OpenOCD 把韌體整份 dump 下來丟進 Ghidra 反組譯,並用 SVD loader 外掛比對官方週邊定義檔,讓結果能對應到實際暫存器位址。

拆解記憶體配置後發現,bootloader 位於 0x8000000、更新程式位於 0x8003000、主應用程式從 0x8006200 開始,韌體長度以十進位 ASCII 字串存放在 0x8006000。整個更新流程沒有簽章或加密驗證,只用 CRC-16-CCITT 以 64 bytes 為單位做完整性檢查,代表摸清封包格式後就能塞入未授權的自製韌體。CAN 封包格式也一併還原,例如 0x300 承載駕駛模式、頭燈、步行計數器,0x306 用第二個 byte 高位承載 9 位元節流閥數值並夾帶方向燈與限速旗標,0x201 回報馬達轉速與狀態旗標:

// CAN 訊息 ID 與欄位(簡化示意)
0x201  motor_speed: u16, status_flags: u8
0x300  drive_mode: u8, headlight: bool, walk_counter: u16
0x306  throttle: u9 (跨兩個 byte, MSB 在第二個 byte),
       blinkers: u2, speed_limit: u8

掌握協定與更新機制後,作者用 Rust 重寫顯示器端韌體:HAL 用基於 stm32-rs 分支出來的 at32f4xx-hal,顯示驅動交給 mipidsi crate 處理 ST7796 面板,CAN/UART 封包的位元級解析用 deku 巨集宣告式定義欄位,並用 Embassy 非同步框架搭配 actor 模式把 CAN 監聽、UART 讀取、ADC 取樣與畫面繪製拆成獨立協程,16 位元並列匯流排也自己手刻了一套 GPIOB 批次寫入,取代原廠慢速的逐位元切換。

實際效果

最終成果是一套完全取代原廠的開源顯示器韌體,能正常解析 CAN 匯流排上的行車資訊、處理三條 UART 通道、讀取 ADC 類比訊號,並透過自製並列匯流排驅動硬體加速的自訂 GUI 畫面。作者把成果整理成兩個公開儲存庫:主要韌體專案 scooter-display,以及利用先前逆向出的更新協定另外寫成的燒錄工具 egret-can-flasher,讓其他人不需重覆這整套逆向流程也能刷寫這款車型。

原始來源:Reverse engineering my e-scooter and rewriting the firmware in rust

從暴力比對一路推導到位元運算:Bitap 字串比對演算法拆解

jo3-l.dev · 2026-09-07

背景

部落客 jo3-l 在文章《Bitap: my favorite string matching algorithm》中,以逐步改寫的方式推導出 Bitap(又稱 shift-and 或 shift-or)字串比對演算法,文中同時附上通往 Boyer-Moore、Knuth-Morris-Pratt、Two-Way 等其他經典字串比對演算法說明的連結作為對照。字串比對問題本身很單純:在長度 n 的文字中找出所有等於長度 m 的 pattern 的位置,最直覺的暴力解法要對每個起始位置逐字元比對,最差要花 O(nm)。

Bitap 的位元並行手法其實相當古老:精確比對版本最早由 Bálint Dömölki 於 1964 年提出,1977 年由 R. K. Shyamasundar 加以延伸,直到 1989 年才被 Ricardo Baeza-Yates 與 Gaston Gonnet 重新發現,並在 1992 年發表於 Communications of the ACM,即 shift-or 版本;隔年 Udi Manber 與 Sun Wu 提出效率更好的 shift-and 變形,後來成為 agrep 這款模糊搜尋工具的核心演算法之一。

演算法原理

文章沒有直接端出最終版本,而是先寫一個会追蹤「目前每個候選起始點還剩多少 pattern 尚未匹配」的一次掃描(one-pass)版本,把原本要不斷回頭重比對的暴力解法,改成一次掃過文字、同時維護所有還存活的候選匹配。接著把「剩餘待匹配後綴」壓縮成一個整數索引,代表目前這個候選已經匹配到 pattern 的第幾個字元,而不必真的保留字串切片。

下一步是關鍵的表示法轉換:把所有還存活的候選索引,通通塞進同一個 bitset,例如作者舉例「若存活狀態為 {1, 2, 7},對應的位元表示就是 0b1000_0110」,一個整數就能同時代表所有候選的進度。最終版本 matchBitap() 事先為 pattern 中每個可能出現的字元,計算好一份「合法遮罩」validMask[c]——只要 pattern 第 j 個字元等於 c,就把該遮罩的第 (j+1) 個位元設為 1。掃描文字時每讀入一個字元,只需要兩個位元運算就能同時更新所有候選狀態:

active = 0
for c in text:
    active = ((active << 1) | 1) & validMask[c]
    if active has top bit set:
        # 在目前位置找到完整匹配

由於每個字元只做一次位移(shift)與一次遮罩(and),只要 pattern 長度固定,整體時間複雜度就是線性的 O(n),漸進複雜度其實跟暴力解法一樣,差別在於位元運算的常數因子遠比逐字元比對小得多。但這個技巧仰賴把整個 bitset 塞進一個機器字組(通常是 64 位元)才划算,一旦 pattern 長度超過這個位元寬度,就得改用多個字組拼接的 bitset,效能與空間效率都會隨之下降。

應用場景

因為核心迴圈完全由位移、或(or)、和(and)三種位元運算組成,沒有分支,Bitap 對 CPU 分支預測與快取都非常友善,歷史上被用在 agrep 之類的模糊搜尋工具中作為短 pattern 比對的加速路徑。作者特別註明,能容許 k 個編輯距離的「模糊 Bitap」版本雖然常被歸在同一個名字底下,但不是這篇文章要討論的內容——那個版本原理上仍是同一套位元並行框架,只是要多開 k+1 份平行的 bitset 分別代表容許 0 到 k 個錯誤時的匹配進度,每讀入一個字元時額外用位元或運算讓不同錯誤層級之間傳遞插入、刪除、替換所造成的狀態轉移。

原始來源:Bitap: my favorite string matching algorithm、Bitap algorithm(Wikipedia,演算法歷史參考)

End of article