ריי טרייסר ב-Brainfuck: תוכנית של 23MB שמציירת פיקסל בדקה

מחבר הבלוג epestr.com קיבל כאתגר שורה במדריך של CMake: ray tracer-ים נכתבו אפילו בשפת CMake Language, אם כי זו אינה שיטה מומלצת. הוא כבר כתב ray tracer והסב אותו ל-GPU, ולכן בחר ב-Brainfuck, שלדבריו היא השפה הפשוטה ביותר שהוא מכיר, ויצא לשחזר את התמונה מפרק Metal במדריך Ray Tracing in One Weekend. הקוד פורסם ב-GitHub בשם mTvare6/rayfuck.

שמונה פקודות וסרט אחד

ל-Brainfuck יש שמונה פעולות ומבנה נתונים יחיד: סרט אינסופי של תאים, שכל אחד מהם מחזיק בייט בלתי מסומן. אין אוגר רחב מתא אחד, אין פקודה שנוגעת בשני תאים בבת אחת, וחיבור וכפל אינם פקודות כלל. לכן מספרים ממשיים קודדו ידנית: כל ערך תופס ארבעה תאים בפורמט נקודה קבועה מסומן Q16.16, 16 סיביות לחלק השלם ו-16 לשבר, כלומר רזולוציה של 1/2^16 וטווח של בקירוב [-2^15, 2^15). הפורמט הזול יותר Q8.8 נפסל כצר מדי, מפני שהכדור שמשמש כקרקע חייב רדיוס 1000 כדי להיראות שטוח.

לבנות את האריתמטיקה מאפס

23 מגה-בייט של Brainfuck לא נכתבו ביד: התוכנית מומרת לצורה דמוית SSA ואחר כך מפורקת ל-DSL ביניים קטן עם כשלושים פעולות כמו copy, mul, sqrt, if ו-while. שני פרימיטיבים עושים את רוב העבודה: move ([->+<]) מעביר ערך מתא אחד לשכנו, ו-copy ([->+>+<<]) משאיר אותו בשניים. הכפל הוא חיבור חוזר על פני ארבעת התאים, והחילוק נעשה כמו חילוק ארוך בבסיס 256: המחלק מופחת לכל היותר 255 פעמים לתא.

גם ספריית המתמטיקה נבנתה מאותם אבני בניין. מספרים אקראיים מגיעים מגנרטור זעיר, A = (5*A + 1) % 256, שמחזורו המלא בן 256 הערכים מספיק להחלקת קצוות בדגימה מרובה. לשורש הריבועי שיטת הרון נפסלה בגלל החילוק, וטור טיילור התאים היטב רק מעל 0.305, ולכן נבחר שורש ריבועי בחילוק ארוך.

פיקסל בדקה

התוכנית המוגמרת שוקלת 23MB, יותר מהתמונה שהיא מציירת (כ-0.9MB), ולכן המחבר מציין ש-Brainfuck הוא דרך גרועה לדחיסה. הקצב הוא כ-100 חישובי קרניים בדקה, כלומר פיקסל בדקה, כך שתמונה בגודל 400×225 הייתה אורכת כ-62.5 ימים במחשב הנייד שלו. בזמן הכתיבה הופקו 1229 מתוך כ-90,000 פיקסלים, ורק 10 מהם שונים מתמונת הייחוס ב-C, בעיקר בערך של אחת.

אחרי תגובה בשרשור ב-Reddit שהציעה פרימיטיבים של fork/join, המחבר שיפר במקום זאת את מפרש ה-JIT ודיווח על האצה מסיבית; הרינדור האמיתי, לדבריו, נראה קצת כמו ציור של ואן גוך, כנראה בגלל שגיאות דיוק.