לולאת מל – הביטים הנעדרים

כשראיתי את האור כמעט הסתנוורתי. (שורה 193)

שורה זו, בסיפור על מל, מובילה לתיאור ההאק של מל, אותו מימוש כמעט פלילי בערמומיותו של לולאה סופית ללא תנאי עצירה. גם אחרי שלושים שנות היכרות עם הסיפור, המלים האלה מעוררות בי לעתים צמרמורת.הן משקפות רגע "אה!" נדיר, שבו ערימה של פרטים מסתדרת לפתע במבנה הגיוני.

מעבר לסיפוק אינטלקטואלי, אני חושד שחלק נכבד מההנאה שלי נבע מתחושת ההשתייכות לקומץ עילי של אנשי תוכנה שבאמת הבינו את הסיפור. כמובן שהסיפור חביב על רבים אחרים שאימצו אותו אל המרחב הדיגיטלי שלהם, אבל אני יכולתי לצלול אל הפרטים מבלי להידרש לקריאה חוזרת. ידעתי על רגיסטר האוגר-מונה, התעלול של שינוי ההוראה וכתיבתה בחזרה לתוך הקוד והופעתה המיסטית של הוראת JUMP במקום הנכון ובזמן הנכון.

רק כשעברתי על הגרסה המוערת של הפרוייקט, התחלתי לחוש אי נוחות סביב אותו דימוי עצמי של איש תוכנה "אמיתי" שיודע לדקלם אודות רגיסטרים, שיטות מיעון וגלישה. התחושה העמומה הזו התפתחה עד מהרה ל"רגע מל" משלי, בגרסה הפוכה לגמרי מהרגע המקורי המתואר בסיפור.

שלא כמו ההתגלות הפתאומית והמספקת לה זכה אד ניית'ר, זו שלי הייתה ממושכת ומטרידה. במקום הבזק אור חטוף, חוויתי עמעום הדרגתי של תמונת ההאק שאצרתי בזכרוני לאורך השנים. במקום להסתנוור, יכולתי לראות, בחסות החשיכה, כמה מרושלת הייתה הקריאה שלי. כה מוקסם הייתי מהסיפור, עד שמעולם לא עלה בדעתי לפקפק בהתכנותו.

הגירסה המקורית

נסקור בקצרה את התיאור של אד ניית'ר ל-overflow ששינה את הקוד בזמן ריצה, יצר הוראת JUMP יש מאין ואיפשר לתכנית לדלג באורח פלא אל מחוץ ללולאה אינסופית.

הרמז החיוני הגיע כאשר שמתי לב שהביט של האוֹגֵר-מונה, הביט שבין הכתובת לבין קוד-הפעולה בהוראה, היה דלוק (שורות 185-189)

למען הפשטות, נדגים את התהליך על דגם מוקטן של הוראה במחשב RPC-4000, שבו לכל רכיב בהוראה מוקצים 3 ביטים, למעט דגל האוגר-מונה אשר שוכן בביט בודד:

• (A) – Data Address
• (X) – Index register
• (C) – Operation code

משהו כמו:

בתרשים הזה חסר רכיב המתואר מוקדם יותר בסיפור:

מִיעוּן הכְּתוֹבוֹת במחשב החדש היה מסוג אחד-ועוד-אחד כך שבכל הוראה למכונה, בנוסף לקוד-הפעולה(operation-code) ולכתובת האוֹפֵּרַנְדּ היתה כתובת נוספת שציינה היכן, על התוף המסתובב, ממוקמת ההוראה הבאה. (שורות 54-60)

עולה שמערך הביטים שלנו צריך רכיב נוסף שבו שמורה כתובת ההוראה הבאה (N). על פי הסיפור, רכיב זה לא משחק תפקיד בהאק. ליתר בטחון, נציב אותו בביטים הנמוכים ביותר:

ידוע לנו שהביטים ברכיב (A) נמצאים "מתחת" לרכיב (V), על סמך תיאור הגלישה שמל הינדס לצרכיו:

תחת זאת, הוא העתיק את ההוראה אל אוֹגֵר אחר במכונה הוסיף 1 לרכיב הכתובת ושמר את התוצאה במקומה המקורי בזכרון. [...] הוא מיקם את המידע שעליו עבד סמוך לראש הזיכרון – בכתובות הגדולות ביותר אליהן יכלה הוראה לפנות כך שלאחר שפריט המידע האחרונה טופל, פעולת חיבור על כתובת ההוראה הייתה גורמת לגלישתה העברת השארית הוסיפה 1 לקוד-הפעולה ושינתה אותו לקוד-הפעולה הבא ברשימת ההוראות: (שורות 175-177, 194-201)

אם הגדלת המספר ברכיב הכתובת גלשה אל תוך רכיב ההוראה, אזי סדר הביטים ביניהם ברור:

אם הביט של האוגר-מונה שוכן, כמתואר, בין שני הרכיבים האלה וערכו 1, אזי גלישה ב- (A) תעבור דרך (X) ותמשיך אל (C) , מגדילה את ערכו ב-1. התוצאה:

הוראת דילוג (`JUMP`) מן הסתם, ההוראה הבאה כבר הייתה בכתובת אפס, והתוכנה המשיכה קדימה באושר בדרכה. (שורות 202-205)

האמת הלא נעימה

כל זה אפשרי להלכה, אבל איננו יודעים עדיין מהיכן לוקחת אותה הוראה JUMP את האופרנד שלה, שערכו על פי הסיפור 0. הגלישה אכן מיקמה את המספר הזה ברכיב (A), אבל בתיאור הארכיטקטורה של ה-RPC-4000 לא מוזכרת אפשרות שהשדה הזה מתפקד גם כאופרנד ישיר. אילו נלקח האופרנד מאחד הרגיסטרים, חזקה על אד ניית'ר שהיה מבין את הרמז ומפענח את התעלול שנרקם בקוד.

הפרט החשוב הזה חמק מעיני במשך 30 שנים, אבל היו עוד מחדלים. איזה תפקיד, אם בכלל, שיחקה שיטת המיעון הייחודית של ה-RPC-4000? האם רכיב ה-(N) הושפע מהגלישה? מה הייתה הזיקה שלו להוראת JUMP? ומה בדבר המיקום של אותו ביט בודד, (X), בין (A) לבין (N)? לא בלתי אפשרי, אבל… מוזר.

אחרי התאוששות הכרחית מהמהלומה שספג האגו התכנותי שלי, נפניתי סוף סוף לפעולה הבסיסית שנדרשת כדי להבין את ההאק של מל: עיון בספרי ההדרכה של RPC-4000. עיון קצר הספיק כדי ליישב את הספקות.

בלשון בני אדם, ההאק – כפי שתואר על ידי אד ניית'ר – לא היה אפשרי על RPC-4000. שדה (C) , שלכאורה הושפע מהגלישה, שכן בביטים הנמוכים ביותר של ההוראה. במודל הפשוט שלנו:

כל גלישה (אשר מתפשטת לכיוון ה-MSB) בביטים שמעל שדה (C) , לא הייתה משפיעה עליו. יתרה מזאת, קוד הפעולה 0 לא היה "הוראת דילוג", אלא פעולה שונה בתכלית שאינה קשורה לתהליך המתואר, כך שגם מערך ביטים שונה לא היה מאפשר את ההאק.

שחזור ההאק

לאחר ששללנו את היתכנות הקוד המתואר בסיפור, אפשר להעלות על הדעת אינספור הסברים לאי הדיוק הזה, כולל האפשרות מדובר במעשיה. עם זאת, מעניין להתמקד בתרחישים דומים לתיאור של ניית'ר אשר תואמים את חומרת ה-RPC-4000. עיון נוסף במשאבים שריכז הפרוייקט העלה שהפער הזה, בין המנגנון שבסיפור לבין יכולות המכונה, לא חמק מעיניהם של חובבי מל אחרים. הניתוח המפורט של דיוויד ניוג'נט נוגע בבעיה, אבל מציע הסבר שנשען על גלישת ה-OPCODE, שאינה אפשרית במכונה. הדיון ב-Hacker News כולל סקירה מעמיקה שכתב Stassa Patsantzis ("YeGoblynQueenne") אודות הפער בין הסיפור לבין המציאות, כולל מתווה כללי למנגנון שנתאר בהמשך.

תרחיש הגלישה

מסתבר שארכיטקטורת ה-RPC-4000 מאפשרת קידוד שיחולל את הפלא בעזרת גלישה. נדגים על ההוראה המפושטת שלנו ונניח שברגע מסויים, היא מחזיקה את הערך:

בתרשים זה, קוד הפעולה אינו משמעותי. בשדה (N) נמצא המספר 111, כך שזו הכתובת שאליה ימשיך המעבד אחרי ביצוע ההוראה הנוכחית. שדה (A) – כתובת האופרנד – מחזיק גם הוא את המספר 111. אין בעיה עקרונית בכך שההוראה והנתון נמצאים באותה כתובת: ייתכן שמדובר בקוד פעולה נטול אופרנד, או שהערך בכתובת הזו הונדס כך שניתן יהיה להשתמש בו בשני ההקשרים, מנהג שלא היה זר למל על פי הסיפור.

במערך הביטים הזה, התכנית תמשיך להוראה בכתובת 111 אחרי ביצוע ההוראה הנוכחית, אלא שאם נוסיף כעת 1 לשדה (A), על ידי חיבור המספר הבינארי 1000 להוראה, ה"גלישה" הפנימית בתוך הרגיסטר תאפס את רכיבי (A) ו-(N) ותניב את ההוראה הזו:

אחרי ביצוע קוד ההוראה CCC, תקפוץ התכנית לכתובת 0, בדיוק כפי שכתב אד ניית'ר. בתרשים המוצע, הביט של האוגר-מונה כבוי לפני הגלישה ודלוק אחריה. השינוי הזה יכול היה להוליד את התמיהה שעלתה אצל ניית'ר כשראה את הביט הזה דלוק ללא סיבה ניכרת.

אפשרות פחות רומנטית

קיים לפחות תרחיש אפשרי אחד נוסף, כזה שתואם אף יותר את הסיפור. מבנה הקוד הזה מוזכר בחטף בפוסט של Stassa Patsantzis ונשען על ההשערה שאד ניית'ר לא הכיר לעומק לפחות שתי תכונות של RPC-4000:

קוד הפעולה 23 (10111) ייצג את הוראת TBC (Transfer on Branch Control) – גירסת ה-RPC-4000 לפעולת JUMPמותנית. הפעולה מעבירה את התוכנית לכתובת שברכיב(A), אם מתג פנימי בשם Branch Control Unit (BCU)דלוק. במקרה שזה האחרון כבוי, התוכנית ממשיכה, כרגיל, להוראה שבכתובת בשדה(N).

על פי התעוד, מתג ה-BCU נדלק (קיבל את הערך 1) בשני מקרים: פעולת השוואה שהצליחה (למשל, בדיקה אם מספר מסויים גדול/שווה למספר אחר), או – רלוונטי יותר לענייננו – גלישה ברגיסטר של המכונה.

לשון אחרת, הסתעפות מותנית מומשה על RPC-4000 באמצעות שני צעדים:

1. בדיקה, כמו השוואת שני מספרים, שלאחריה -
2. הוראת TBC, שמעבירה את התכנית לכתובת ברכיב (A) אם ההשוואה הצליחה.

במקרה של כשלון ההשוואה (למשל, בדיקה אם 13 קטן מ-9), התכנית המשיכה במתווה השכיח, לכתובת שברכיב (N).

סביר להניח שתהליך הכשרת מתכנתים לעבודה עם RPC-4000 כלל רק את המנגנון הראשון מבין השניים, שכן זה אפשר לממש את פעולת התכנות הבסיסית if/else. תחת ההנחה הסבירה לא פחות, שאד ניית'ר הסתפק בהכשרה המקובלת ולא צלל לעמקי המכונה, לא פלא שהוא התפלא למצוא הוראת TBC ללא הבדיקה המקדימה.

במקום לבצע בדיקה כזו, מל חזר והגדיל ב-1 את ערכו של רכיב (A), כמתואר בסיפור. הפעולה הזו הובילה, במרוצת התכנית, לגלישה של הרגיסטר כולו – בתנאי שהביט (X) היה דלוק, בדיוק כפי שזכר אד ניית'ר. נדגים בעזרת המודל הפשוט שלנו, כשרכיב ה-(C) מכיל את הערך השרירותי 101:

         1111111101
    MSB <----------> LSB

    +    0000001000
    ====================
         0000000101
    MSB <----------> LSB

    +     גלישה

הגלישה גרמה להדלקת מתג ה-BCU, מה שגרם להוראת ה-TBC שעד כה לא השפיעה על ריצת התכנית, לדלג לכתובת 0 שהופיעה ברכיב (A). אם אד ניית'ר אכן לא התוודע לקשר בין ההוראה הזו לבין גלישה, אזי מבחינתו הקוד אכן כלל לולאה ללא תנאי יציאה. הוא הכיר רק את השימוש הסטנדרטי בהוראה, כדילוג מותנה (if/else) . כשנתקל בהוראת TBC ללא בדיקה מקדימה, אך טבעי היה להסיק:

אבל בלולאה לא היה תנאי עצירה.

כאמור, התרחיש הזה קרוב יותר למתואר בסיפור המקורי: (סוג של) הוראת JUMP, גלישה ואפילו 1 לא נחוץ, לכאורה, בביט ה-(X). נותרו שני הבדלים משמעותיים:

1. קוד הפעולה (opcode) לא משתנה.
2. האופי הפלאי של ההאק לא מושתת רק על כישוריו של מל, אלא גם – אולי בעיקר – על ההבנה החלקית שהייתה לניית'ר לגבי המכונה. אילו השכיל ניית'ר לקרוא את האותיות הקטנות במדריך למתכנת, לא הייתה לו בעיה לפצח את הקוד במהירות ועל הדרך – למנוע מהדורות הבאים סיפור מופת.

כל חובב או חובבת תכנות יכולים לדמיין בקלות את תגובתו של מל, כאשר למד אודות האפשרות לגרום לדילוג באמצעות גלישה. האתגר היה ברור ומיידי. מן הסתם, אחרי הרצת תכנית בדיקה פשוטה, הוא המשיך לרמה הבאה שבה הדילוג אינו שרירותי, אלא בהקשר טבעי של לולאה שתסתיים כאשר מאגר הנתונים שלה מוצה. המהלך הגאוני הושלם כאשר הוא הצליח לשלב את המבנה המאולץ הזה לתוך תוכנת מחשב מסחרית.

סוף דבר

בכל גירסה שנבחר – בין אם לוליינות הביטים ובין אם התמרון המרהיב עם הוראת TBC – ברור שדיווחו של אד ניית'ר נבע מזכרון לקוי וכנראה גם הבנה לקויה של RPC-4000. הממצא הזה לא גורע מקסמו של הסיפור. רוב מפתחי התוכנה יזדהו בקלות עם החפירה המייגעת בקוד ה"בלתי אפשרי" של מתכנת אחר. ההילה המיוחדת סביב תוכנה שמשכתבת את עצמה אופפת את שתי הגירסאות וההאק – כך או אחרת – מרשים מאד.

אם הניתוח שלנו מטיל צל כלשהו על המיתוס של מל קיי, הרי שזה אינו קשר לאמינות של אד ניית'ר או לכישורי התכנות של מל. הפן הבעייתי קשור לחוסר הנחיצות המובהק של ההאק בתוך התוכנה. לא סביר בעליל שביצועי התוכנה היו מידרדרים באופן ניכר, אילו השתמש מל בטכניקה הסטנדרטית. הלולאה נטולת תנאי היציאה הייתה תוספת גחמנית של סיבוך, בסביבה שגם כך הייתה כמעט מסובכת מדי למפעיליה.

הגישה הזו להנדסת תוכנה רחוקה מלהיות נחלת העבר. גם בימינו, קל לזהות אותה בקרב צוותי פיתוח, אצל אנשי תוכנה שיכולתם לא מוטלת בספק, אבל ההערכה אליהם – דווקא כן. אם בילית כמה שנים בתעשייה או באקדמיית מדעי המחשב, סביר מאד שנתקלת בזן הזה: המפתח שנהנה להחליף לולאות פשוטות בסדרה של auto-resolving promises, שמתכנסות לפונקציית reduce מסתורית. הנאתם מהקוד המורכב שניה רק לסיפוק שהם רווים מהמבטים המבולבלים על פני חבריהם לצוות. כנראה לא האישיות שהייתם בוחרים לאגדת התוכנה שלכם.

אלא שהבדל אחד, בין המתכנתים האלה לבין מל, נוטל את העוקץ מההשוואה הזו. ההאק של מל התבצע בחסות החשיכה. הוא נועד לרוץ בדומיה עד שהמכונה תוציא את ימיה, גלוי רק לקורא הסלילים האלקטרוני. המפגש של אד ניית'ר עם הקוד היה מקרי; הקושי שלו לפצח את הלוגיקה מלמד שמל מעולם לא שיתף את חבריו בתעלול, קל וחומר לא התרברב אודותיו. המאבק של מל עם המכונה לא היה זקוק לקהל. ניצוצות הברק והיופי שניתזו ממנו לא הצריכו תשואות. בהיותו מתכנת אמיתי, מל קיי שאב את כל ההנאה שהיה צריך מהצפיה בקוד שלו רץ ומהתחושה שהוא מאד, מאד חכם.