Einen switch über Zeichenketten dekompilieren: die versteckte Hash-Sprungtabelle, die der Compiler baut

Ein switch über einen int oder ein enum ist eines der saubersten Dinge in ganz IL: Der Compiler gibt eine einzige switch-Instruktion aus, eine echte Sprungtabelle, die einen Integer vom Stack liest und in konstanter Zeit zur N-ten Marke verzweigt. Ein switch über eine Zeichenkette sieht im Quellcode genauso aus — case "build": steht direkt neben case 2: in der Sprache —, kann aber nicht zur selben Instruktion kompilieren, weil es so etwas wie eine durch Text indizierte Sprungtabelle nicht gibt.

Also schreibt der Compiler ihn um. Für zwei oder drei Fälle tut er das Naheliegende und gibt eine kurze Leiter von String.Equals aus. Doch sobald ein Zeichenketten-switch über eine Handvoll Marken hinauswächst, greift Roslyn zu einer anderen Strategie, die die meisten nie gesehen haben: Er hasht die Zeichenkette, verzweigt nach dem Hash, um einen Kandidaten zu finden, bestätigt den Kandidaten mit einer Gleichheitsprüfung und benutzt dann einen echten Ganzzahl-switch über einen kleinen Fallindex, um den Zweig zu erreichen. Der lesbare switch (command), den Sie geschrieben haben, wird zu einer Seite hexadezimaler Konstanten und op_Equality-Aufrufen — und ein Dekompilierer versteht entweder diese Form und gibt Ihnen Ihren switch zurück, oder er reicht Ihnen das Hexadezimale.

Ein switch, der groß genug ist, es auszulösen

Hier ist ein gewöhnlicher Befehls-Dispatcher — ein klassischer Zeichenketten-switch mit acht Fällen:

public static int Dispatch(string command)
{
    switch (command)
    {
        case "init":    return 1;
        case "build":   return 2;
        case "restore": return 3;
        case "run":     return 4;
        case "test":    return 5;
        case "pack":    return 6;
        case "publish": return 7;
        case "clean":   return 8;
        default:        return 0;
    }
}

Acht Marken liegen bequem über der Schwelle (Roslyn wechselt bei etwa sieben zur gehashten Form), also überlebt keine dieser case-Zeichenketten als einfache Vergleichsleiter. Stattdessen injiziert der Compiler zuerst einen Helfer in einen synthetischen Typ namens <PrivateImplementationDetails>:

.method assembly hidebysig static uint32
    '<PrivateImplementationDetails>'::ComputeStringHash(string s) cil managed
{
    // uint num = 2166136261;                 // FNV-1a offset basis (0x811C9DC5)
    // for (int i = 0; i < s.Length; i++)
    //     num = (s[i] ^ num) * 16777619;     // FNV-1a prime   (0x01000193)
    // return num;
}

Das ist ein lehrbuchmäßiger 32-Bit-FNV-1a-Hash und nichts weiter. Er ist schnell, er ist nicht kryptografisch, und er darf ausdrücklich kollidieren — die Kollisionsbehandlung kommt später. Seine Präsenz in <PrivateImplementationDetails>, mit genau diesem Körper, ist das deutlichste Signal, dass eine Methode einen gehashten Zeichenketten-switch enthält.

Der zweistufige Dispatch in IL

Nun der Körper von Dispatch. Die Absenkung benutzt zwei lokale Variablen — nennen wir sie num (der Hash) und num2 (ein dichter Fallindex) — und verteilt in zwei Stufen:

// ---- stage 0: hash the input ----
ldarg.0
call    uint32 '<PrivateImplementationDetails>'::ComputeStringHash(string)
stloc.0                         // num = ComputeStringHash(command)

// ---- stage 1: branch on the hash, confirm with Equals, set the case index ----
ldloc.0
ldc.i4  0x9B8C...               // == ComputeStringHash("init")
beq.s   TRY_INIT
ldloc.0
ldc.i4  0x4F2A...               // == ComputeStringHash("build")
beq.s   TRY_BUILD
// ... one comparison per case ...
br      DEFAULT

TRY_INIT:
ldarg.0
ldstr   "init"
call    bool [System.Runtime]System.String::op_Equality(string, string)
brtrue.s  SET_0
br      DEFAULT
SET_0:  ldc.i4.0
        stloc.1                 // num2 = 0  (the "init" arm index)
        br.s    DISPATCH

TRY_BUILD:
ldarg.0
ldstr   "build"
call    bool [System.Runtime]System.String::op_Equality(string, string)
brtrue.s  SET_1
br      DEFAULT
SET_1:  ldc.i4.1
        stloc.1                 // num2 = 1
        br.s    DISPATCH
// ... and so on ...

// ---- stage 2: a real integer switch over the dense case index ----
DISPATCH:
ldloc.1
switch  (ARM_INIT, ARM_BUILD, ARM_RESTORE, ARM_RUN, ARM_TEST, ARM_PACK, ARM_PUBLISH, ARM_CLEAN)
br      DEFAULT

Lesen Sie, was tatsächlich geschieht. Stufe 0 verwandelt die Zeichenkette in eine 32-Bit-Zahl. Stufe 1 vergleicht diese Zahl mit dem vorberechneten Hash jedes Fall-Literals; ein Treffer springt nicht zum Zweig — er springt zu einer Bestätigung, die die ursprüngliche Zeichenkette lädt, sie mit op_Equality gegen das Literal vergleicht und bei Erfolg einen kleinen zusammenhängenden Index in num2 schreibt. Erst Stufe 2 benutzt die echte switch-Instruktion — und bis dahin verteilt sie über 0..7, einen dichten Ganzzahlbereich, was genau das ist, worin der switch-Opcode gut ist.

Die Hash-Verzweigung in Stufe 1 wird hier als eine Folge von beq-Vergleichen ausgegeben, weil die acht Hashes über den uint-Bereich verstreut sind. Wenn die Hashes sich zufällig häufen, gibt Roslyn auch einen zweiten switch über den Hash aus — ein großer Zeichenketten-switch kann also zu zwei verschachtelten Sprungtabellen dekompilieren, was noch verwirrender ist, wenn Sie das Muster nicht kennen.

Warum die Gleichheitsprüfung der ganze Sinn ist

Die wichtigste Instruktion in diesem Listing ist diejenige, die redundant aussieht: das op_Equality, nachdem der Hash bereits übereinstimmte. Es ist nicht redundant, und es zu entfernen wäre ein Fehler.

ComputeStringHash ist verlustbehaftet — er bildet beliebig viele Zeichenketten auf 2³² Werte ab, also können zwei verschiedene Zeichenketten einen Hash teilen. Die Hash-Verzweigung grenzt die Eingabe nur auf einen Kandidaten ein; das ordinale String.Equals ist das, was beweist, dass die Eingabe wirklich dieser Fall ist, bevor ihr Zweig läuft. Zwei Konsequenzen folgen daraus direkt:

• Eine Hash-Kollision wird behandelt, nicht gefürchtet. Wenn zwei Fall-Literale kollidieren, gibt der Compiler beide op_Equality-Prüfungen unter derselben Hash-Verzweigung aus; die erste, die übereinstimmt, gewinnt, und ein Beinahe-Treffer, der den Hash mit einem echten Fall teilt, scheitert dennoch an seinem op_Equality und fällt zu default durch.
• Ein Zeichenketten-switch ist ordinal und groß-/kleinschreibungssensitiv. op_Equality auf string ist String.Equals — ein Byte-für-Byte-Vergleich, kein kulturbewusster. "Build" stimmt nicht mit case "build": überein und tat es nie; die Absenkung macht den Grund nur sichtbar. Wenn Sie groß-/kleinschreibungsunabhängigen Dispatch brauchen, setzen Sie die Eingabe zuerst in Kleinbuchstaben oder verteilen über etwas anderes, denn der generierte Code hat keinen Begriff von Kultur.

Wie Glass.NET es zurückliest

Ein Dekompilierer, der dieses IL Instruktion für Instruktion durchläuft, ohne Modell des Musters, produziert etwas technisch Korrektes und völlig Unlesbares: eine uint-Variable, zugewiesen aus einem Aufruf an ein mysteriöses ComputeStringHash, einen Baum von if (num == 0x9B8C...)-Vergleichen gegen magische Zahlen, eine Streuung von Zeichenketten-Gleichheitsprüfungen und einen finalen switch über einen Integer, der aus dem Nichts erscheint. Niemand, der das liest, kann sehen, dass es sein Leben als switch (command) begann.

Glass.NET erkennt die Form als Einheit. Das Rezept, das es abgleicht, ist spezifisch genug, um zuverlässig zu sein:

1. Eine lokale Variable, zugewiesen aus einem Aufruf einer Methode namens ComputeStringHash auf <PrivateImplementationDetails>, deren Körper die FNV-1a-Schleife ist.
2. Ein Dispatch über diese Variable — eine Vergleichsleiter oder ein innerer switch — dessen Ziele jeweils ein op_Equality der ursprünglichen Zeichenkette gegen ein ldstr-Literal durchführen.
3. Jede bestätigte Übereinstimmung weist einen dichten Index zu und läuft auf einen finalen switch über diesen Index zusammen, oder verzweigt direkt zu einem Zweigkörper.

Wenn alle drei zusammenpassen, verwirft Glass die Hashes vollständig — sie sind ein Implementierungsdetail des Compilers, keine Information — und rekonstruiert den switch aus den ldstr-Operanden, die die ursprünglichen Fall-Literale sind, wortgetreu in den Metadaten erhalten. Sie bekommen zurück:

switch (command)
{
    case "init":    return 1;
    case "build":   return 2;
    // ...
    default:        return 0;
}

Die Konstanten, die ein naives Werkzeug auf der Seite stranden ließe — 0x9B8C..., 0x4F2A... —, erscheinen nie, weil Glass versteht, dass sie eine Funktion der Literale sind, die es bereits gewonnen hat.

Wo die Rekonstruktion abdriften kann

Weil das Muster regelmäßig ist, geht der häufige Fall sauber hin und zurück, aber einige Formen senken zu IL ab, das sich als äquivalenter, aber abweichender Code zurückliest, und es lohnt sich, sie zu kennen, damit Sie dem Dekompilierer dort vertrauen, wo er treu ist, und dort aufmerksam lesen, wo er paraphrasiert:

• Ein null-Fall wird behandelt, bevor der Hash überhaupt berechnet wird — man kann null nicht hashen —, also erscheint er als ein brfalse zum null-Zweig ganz oben, vor dem Aufruf von ComputeStringHash. Glass faltet ihn zu case null: zurück, aber im rohen IL steht er merkwürdig weit vom Rest des switch entfernt.
• Eine Hash-Kollision zwischen zwei echten Fall-Literalen produziert zwei op_Equality-Prüfungen, verschachtelt unter einer Hash-Verzweigung; ein Dekompilierer kann diesen Eimer als verschachtelte ifs statt zweier flacher case darstellen. Gleiches Verhalten, leicht abweichende Form.
• goto case "x"; kompiliert zu einer Verzweigung zurück in den Dispatch — oft direkt zum Zweig der Stufe 2 oder zur Fallindex-Zuweisung —, die ein Dekompilierer als das goto case rekonstruiert, aber nur, wenn er verfolgt, dass das Verzweigungsziel im selben abgesenkten switch liegt.
• Ein als Ausdruck verwendeter switch (die switch-Ausdrucksform über Zeichenkettenkonstanten) senkt durch dieselbe ComputeStringHash-Maschinerie ab; der Unterschied liegt nur darin, ob die Zweige einen Wert liefern oder Anweisungen ausführen, was ein separater Rekonstruktionsschritt ist.

Das Fazit

Ein switch über eine Zeichenkette ist einer der wenigen Orte, wo sich eine einzige Zeile C# in eine wirklich überraschende Menge IL ausdehnt: ein synthetisierter FNV-1a-Hash-Helfer, eine hashgesteuerte Verzweigung, eine ordinale Gleichheitsbestätigung für jeden Kandidaten und eine dichte Ganzzahl-Sprungtabelle — zwei Dispatches mit einer dazwischengeklemmten Korrektheitsprüfung. Der Hash ist aus Geschwindigkeitsgründen da, das op_Equality ist aus Korrektheitsgründen da, und keines ist Information, die Sie lesen wollen. Die Aufgabe eines Dekompilierers ist, die ganze Maschine zu erkennen, die Hashes wegzuwerfen, die Literale aus den ldstr-Operanden zu gewinnen und Ihnen den switch zurückzugeben, den Sie geschrieben haben. Das ist der Unterschied zwischen dem Lesen von switch (command) { case "build": ... } und dem Blinzeln auf eine Wand aus Hexadezimal.

Siehe auch Mustervergleich und switch-Ausdrücke von C# dekompilieren für den Mustervergleichs-switch, der über Typtests statt Hashes absenkt, und wie .NET-Metadatentabellen funktionieren dafür, wo der Typ <PrivateImplementationDetails> und sein injizierter Helfer tatsächlich leben. Testen Sie Glass.NET kostenlos an einer eigenen Assembly und sehen Sie, wie ein Zeichenketten-switch wieder lesbar wird.