התחבולה האטומית של הטירה הנאצית

טריק מעניין במיוחד, שהומצא בשנת 1992 כדי למנוע גליצ'ים בתצוגה של המשחק המפורסם Wolfenstein 3D, עשוי להיות רלוונטי למפתחי תוכנות Embedded אפילו כיום.

צילום מסך מ-3d.wolfenstein.com
צילום מסך מ-3d.wolfenstein.com

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

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

הפתרון לבעיה הזו נקרא Double buffering: אם מתכנני המשחק היו מוכנים להתפשר קצת על הרזולוציה או מספר הצבעים, היה מספיק מקום בזיכרון התצוגה לשני מסכים וירטואליים, נקרא להם A ו-B. התוכנה יכולה לצייר את A בזיכרון, וכשהוא מוכן, להפנות את החומרה אל הכתובת שלו. בזמן שהחומרה סורקת את A אל הצג הפיזי, התוכנה יכולה לצייר את B בזיכרון, וכש-B מוכן היא תפנה את החומרה אל הכתובת של B. ככה מחליפים שוב ושוב בין המסכים הווירטואליים, התוכנה מקבלת יותר זמן לצייר כל אחד, וגם אם היא לא מספיקה זה לא נורא – החומרה תמשיך להציג את המסך הקודם והשלם כל עוד התוכנה לא הפנתה אותה אל כתובת הזיכרון של המסך החדש.

ב-Wolfenstein 3D הרחיקו לכת עוד יותר והשתמשו בשלושה מסכים וירטואליים. בכל אחד מהם היו 320×200 פיקסלים, כלומר 64,000, ובגלל המבנה המורכב של זיכרון התצוגה באותם ימים – לא ניכנס לזה כאן – כל כתובת בזיכרון ייצגה למעשה ארבעה פיקסלים, כך שכל מסך תפס 16,000 כתובות. כמו כן, הכתובות האלה היו בנות 16 ביטים (=שני בייטים), כך שהערכים האפשריים נעו בין 0 ל-65,535. אז בואו נמקם את המסכים הווירטואליים שלנו במרחב הכתובות הזה כפי שכל אדם סביר היה עושה:

  • מסך 1: כתובת 0 (בבסיס הקסדצימלי גם 0x0000)
  • מסך 2: כתובת 16,000 (בהקסדצימלי 0x3E80)
  • מסך 3: כתובת 32,000 (בהקסדצימלי 0x7000)

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

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

כתוצאה מכך, בהחלפה מהכתובת 0x0000 ל-0x3E80 נוצר לעתים נדירות מצב שבו הבייט העליון החדש ("3E") כבר נכתב, הפעולה האטומית של כתיבת הבייט התחתון טרם התחילה (הוא נשאר "00" מקודם), ובדיוק באותו רגע החומרה החליטה לרענן את התצוגה. כמו בפסיקות במיקרו-בקרים, היא עצרה את כל הפעילות הרגילה, קראה את הכתובת העדכנית ("0x3E00"!) והציגה את תוכן הזיכרון מהכתובת הזו והלאה. המשתמש ראה את זה בתור פריים קצרצר שכאילו נחתך לכמה חלקים לא שווים וסודר מחדש בצורה שגויה.

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

הפתרון שמצאו ב-id software גאוני בפשטותו. במקום למקם את המסכים הווירטואליים בזיכרון ברצף, הם מיקמו אותם בכתובות 0, 16,640 ו-33,280, כאילו כל מסך הכיל 320×208 פיקסלים. אם תתרגמו את המספרים האלה לבסיס הקסדצימלי תקבלו 0x0000 (כמובן), 0x4100 ו-0x8200… שבכולם הבייט התחתון זהה! ככה אפשר היה לממש את המעבר בין המסכים השונים בפעולת כתיבה אטומית אחת ויחידה, של הבייט העליון בלבד, לא היה יותר מצב של כתובת "חצי-חצי", והפריים הסורר הנדיר נעלם לגמרי.

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

בימינו, כשהמחשבים וגם רבים מהמיקרו-בקרים מבצעים פעולות אטומיות של 32 או 64 ביט, אנחנו נתקלים פחות במקרים ה"קלאסיים" של התנגשות בין פעולות אטומיות ופסיקות. אף על פי כן, בווריאציות שונות זהו עדיין נושא חשוב ביותר במערכות בכל סדרי הגודל. לאורך השנים הומצאו שיטות רבות מסודרות להתמודד איתו, אך כמו שהקוד של Wolfenstein 3D מראה, לפעמים הפתרון האלגנטי ביותר הוא לעקוף את הבעיה מלכתחילה.

את הרעיון והפרטים לפוסט הזה לקחתי מהספר המרתק Game Engine Black Book: Wolfenstein 3D של פביאן סנגלאר, שניתח את קוד המקור של המשחק. הוא מתכנן לכתוב ספרים דומים על משחקים נוספים, ויש לו גם אתר עם פוסטים מעניינים בנושאים קרובים.

להרשמה
הודע לי על
0 Comments
Inline Feedbacks
הראה את כל התגובות