Долгий путь к рождению Chrome Revenge

PENTRACE

Всё началось в 1994 году, когда я прочитал в Dr. Dobbs Journal несколько интересных статей о FPU (математическом сопроцессоре) нового процессора Pentium. Я пришёл к пониманию того, что численная производительность Pentium очень чувствительна к использованию и порядку команд FPU, и что дополнительными командами FXCH можно значительно увеличить скорость выполнения.

В то время при необходимости трассировки сцены лучами для получения результата требовались часы или даже дни. Я решил написать трассировщик лучей, похожий на POV-Ray или BOB, только на языке ассемблера, чтобы код при этом был сильно оптимизирован под FPU процессора Pentium. Это был «Pentrace», мой дипломный проект в колледже.

CHROME

Существовала очень известная и популярная анимация под названием Chrome, созданная трассировкой лучей. В основном она распространялась среди пользователей Amiga. Я решил, что будет круто показать ту же анимацию зрителям демопати Assembly, но всего в 4 КБ!

Интро Chrome на 4 КБ заняло в 1995 году четвёртое из 44 мест.

CHROME 2

Chrome я заканчивал уже на пати, прямо перед дедлайном, а на следующий год я первым бросил гибкий диск в коробку участников соревнования. Это интро стало первым продуктом с элементами трассировки лучей в реальном времени, только в очень низком разрешении, всего 144x102 пикселя.

Однако я шёл туда за победой! К сожалению, интро не демонстрировали в категории compo, потому что организаторы потеряли мою дискету и его показали только позже, между двумя блоками compo.

В конечном итоге, в 1996 году интро Chrome2 в категории 4kb заняло пятое место, но на следующей неделе мой продукт был первым по скачиваниям с Hornet Archive.

CODER-L

До 2001 года я управлял очень успешным венгерским списком рассылки для кодеров. В этом списке CODER-L было много обсуждений теоретических возможностей трассировки лучей в реальном времени.

Позже на основе этих обсуждений появились такие творения, как Slumpism by Pathos (при выполнении трассировки исходящих из камеры лучей он проводил перед каждой растровой строкой тест пересечения плоскости камеры и объекта) или Heaven Seven by Exceed (использовал для лучей камеры адаптивное субсэмплирование).

Однако тем временем, в конце 90-х, я потерял интерес к демосцене и мотивацию…

COLORFUL

Вернулся я в 2016 году, поучаствовав в qbparty. Меня поразило то, что в демосцене по-прежнему оставалось место для кодинга на ассемблере для DOS, поэтому я начал публиковать 256-байтные интро.

Однако с прежних времён аппаратная среда сильно изменилась, и после тестирования на многих современных компьютерах я понял, что единственным вариантом для трассировщика лучей остаётся видеорежим 640x480 c 32 битным цветом (с банкируемой памятью).

Моим первым 256-байтным интро в режиме HiRes стало Colorful (заняло второе место на Function 2016).

256B SEMINAR

В 2017 году я представил на Function свой движок трассировки лучей с покеболами. В нём использовалось адаптивное субсэмплирование, однако только в горизонтальном направлении из-за ужасного переключения банков в видеопамяти. И да, он был довольно быстрым.

SEASHELL

В этом демо я впервые использовал для лучей камеры ортогональную проекцию. Она выглядела достаточно красивой, была быстрой и занимала малый объём кода.

256-байтное интро Seashell заняло первое место на Riverwash 2017.

TCTRONIC

Мы нарушили правила compo на Function 2017. В нашем интро была музыка PWM PC-Speaker, воспроизводящая хорошо известный байтбит.

256-байтное интро TCTRONIC заняло второе место на демопати Function.

Plasmifier Cover 256b

Первое 256-байтное интро, имеющее музыку с программным синтезатором вместо просто байтбита.

Plasmifier Cover заняло второе место на Chaos Constructions 2018.

Благодарю Provod и Frag за то, что показали мне малозатратную огибающую IMUL xx,xx,-1 на стриме ikubun. И спасибо Gargaj за то, что обратил моё внимание на мастеринг в своей речи на Assembly.

Balls Harmony

HellMood открыл интересную тему о комбинировании записи, которое может ускорить запись в видеопамять. Особенно от этого выигрывали интро в True color.

При комбинировании записи я мог трассировать каждый пиксель экрана в своём интро (однако в эмуляторе это так не работало).

256-байтное интро Balls Harmony заняло второе место на Function 2019.

SSE 4.1

С Kuemmel мы начали код-гольфинг демо разработчика Frigo для Function (Space Fungus). Мы попытались ускорить его с помощью команд SSE. И запись в видеопамять при помощи MOVAPS [ES:DI],XMM7 оказалась даже быстрее, чем комбинирование записи.

Кроме того, Kuemmel из темы на Tiny Intro Toolbox узнал, насколько легко ограничивать значения цветов при помощи команд SSE.

SSE настолько крутое, там можно нормализовать векторы без SQRT и DIV!

Разработка графической части (автор: TomCat)

Технические подробности

HiRes TrueColor

Наименьшее разрешение TrueColor на любом современном PC — это 640 x 480 с 32 битами на пиксель. Можно легко задать его при помощи VESA BIOS.

 MOV BX,112H
 MOV AX,4F02H
 INT 10H

Однако номер видеорежима в разных VGA-картах может различаться. Чаще всего используется номер 112H. Он работает на nVidia, Intel, DosBox и т.п., но не на ATI. В VGA-картах ATI/AMD он устанавливает режим 640x480x24 бит. Поэтому в этом случае нужен номер 121H.

К сожалению, в VESA-драйверах виртуальных машин используются ещё более странные номера: VirtualBox — 142H, VMware — 13FH.

Видеопамять

Под DOS самым быстрым способом записи в видеопамять является команда MOVAPS, если её поддерживает процессор. Она может записывать по 16 байт (4 пикселя) за раз.

 MOVAPS [ES:DI],XMM7

Чтобы использовать её, нужно собрать 4 пикселя в регистры. Нижние 4 байта XMM2 — это новые пиксельные данные для одного пикселя. Повернув XMM7 влево на 4 байта, мы можем вставить новый пиксель.

 SHUFPS XMM7,XMM7,10010011B
 MOVSS XMM7,XMM2

При вычислении цветовых компонентов пикселя мы получаем значения float. Их нужно преобразовать в integer и ограничить интервалом от 0 и 255. Для этого очень пригождаются команды SSE:

 CVTPS2DQ XMM2,XMM2
 PACKSSDW XMM2,XMM2
 PACKUSWB XMM2,XMM2

Видеопамять VESA high-color упорядочена в банки, поэтому после 4096 операций записи мы должны переключиться на следующий банк.

 ADD DI,16
 JNZ .4
 PUSHA
 SUB BX,BX
 MOV AX,4F05H
 INT 10H
 POPA
 INC DX    ; DL: number of memory bank
.4:

Адаптивное субсэмплирование

По сути, мы трассируем каждый четвёртый луч из камеры. Во время трассировки я вычисляю байт метки, то есть уникальное значение, зависящее от того, с чем мы пересеклись.

Если байт метки такой же, как и 4 пикселями ранее, то можно выполнить интерполяцию между цветами. Если нет, то нужно оттрасировать больше лучей камеры между двумя пикселями.

 INSERTPS XMM7,XMM2,00110000B ; XMM7: insert new color on the top
.2:
 SHUFPS XMM7,XMM7,10010011B   ; XMM7: rotate left
 PAVGB XMM2,XMM7              ; XMM2: averaging the colors
 MOVSS XMM7,XMM2              ; XMM7: put interpolated color on the bottom
 CMP [BP+SI],BL               ; is it the same stampbyte?
 LOOPNZ .3                    ; if no, then trace the next pixel
 TEST CL,3                    ; was the fourth pixel?
 JNZ .2                       ; if no, then interpolate the next pixel
.3:
 TEST CL,3                    ; was the fourth pixel?  
 JNZ .4                       ; if no, then skip putpixel
 CALL putpixel
 SHUFPS XMM7,XMM7,11111111B   ; XMM7: fill by the last color
 MOV BL,[BP+SI]               ; store the stampbyte
 ADD CX,8                     ; go to right by 8 pixels
.4:
 CMP CX,RESX/2+4              ; was it the last pixel in the raw?
 JNE nextpixel                ; if no, then go to the next pixel                 

То есть нам нужно трассировать больше, чем каждый четвёртый луч из камеры, но в среднем, как мне кажется, значение меньше, чем каждый третий пиксель.

Ортогональная проекция

Испускание лучей камеры выполняется ортогонально к плоскости X-Y (другими словами, параллельно оси Z). Вектор направления всегда равен [0,0,1] а позиция глаза (камеры) является координатами X, Y экрана плюс любое отрицательное значение Z. Если конкретнее, то после корректировки соотношения сторон P равен [+94..-94,-160..+160,-8260].

 MOV AX,RESY/2
nextline:
 MOV CX,-RESX/2+4
nextpixel:
 PUSHA                      ; -20:DI SI BP SP BX DX CX AX 1 0
 PMOVSXWD XMM6,[BX-8]       ; XMM6: P = x,y,1,0
 CVTDQ2PS XMM6,XMM6
 MOVAPS XMM5,XMM6
 MULPS XMM6,[SI]            ; *Aspect [SI]=[0.5028877,0.39081812,-8260.683]
 SHUFPS XMM5,XMM5,11101111B ; XMM5: D = 0,0,1,0

Векторы

Выполнение вычислений с тремя (или четырьмя) векторными координатами одновременно при помощи команд SSE само по себе является ускорением работы. Вот как я хранил следующие векторы в разных регистрах SSE:

;XMM0: temporary #1
;XMM1: temporary #2
;XMM2: color coordinates
;XMM3: reflection vector
;XMM4: normal vector
;XMM5: direction vector
;XMM6: point
;XMM7: collector for colors of 4 pixels

Нормализация?

Сегодня наиболее затратными командами являются деление и квадратный корень. При нормализации используются обе эти команды, поэтому я попытался избежать нормализации векторов. Именно поэтому мы испускаем лучи с ортогональной проекцией. Лучи камеры являются единичными векторами.

Отражённые лучи также являются единичными векторами из-за свойства отражения; нам не нужно их нормализовать. Единственными векторами, для которых нормализации нельзя избежать, являются лучи теней. К счастью, существует специализированная команда для вычисления величин, обратных квадратным корням.

 MOVAPS XMM0,XMM5         ; XMM5: D = VNORM(D)
 DPPS XMM0,XMM0,01111111B
 RSQRTPS XMM0,XMM0        ; instead of SQRTPS XMM0,XMM0
 MULPS XMM5,XMM0          ; instead of DIVPS XMM5,XMM0

Примечание: RSQRTPS даёт серьёзный прирост производительности. Однако она ОЧЕНЬ приблизительная: она создаёт результаты с относительной погрешностью менее 1.5 * 2^-12. Учитывая то, что машинный эпсилон чисел float с одиночной точностью равен 2^-24, можно сказать, что эта аппроксимация имеет примерно половинную точность. Её нельзя использовать для лучей камеры, но она неплоха для лучей теней.


Когда я попытался нормализовать лучи камеры при помощи RSQRTPS, это привело к множественным артефактам в контуре сферы.

Затенение

Единственный источник света — это слишком скучно, поэтому у нас их два. Один источник имеет координаты (255,255,255), а второй противоположен ему и находится в (-255,-255,-255).

Для затенения я использовал модель Фонга. Компонент рассеянного освещения очень прост: dot(normal,shadow)

 MOVAPS XMM1,XMM4         ; XMM1: N.S
 DPPS XMM1,XMM5,01110001B
 MOVAPS [DI],XMM1
 CMP [DI+3],CH
 JLE @F                   ; Ambient
 FADD DWORD [DI]          ; Ambient+Diffuse
@@:

Компонент зеркального освещения более интересен: dot(reflected,shadow)^2^2^2

 DPPS XMM5,XMM3,01110001B ; XMM5: R.S
 MOVAPS [DI],XMM5
 FLD1
 FADD DWORD [DI]          ; Specular Ambient+Diffuse
@@:
 FMUL ST0,ST0             ; Specular=Specular^2
 INC CX
 JPO @B                   ; loop x3

Рекурсия

Три уровня рекурсии очень заметны в отражениях, но дополнительные уровни будут пустой тратой ресурсов. Для проверки уровня текущей рекурсии я использовал регистр указателя стека.

 CMP SP,-22-2*maxlevel  ; Max recursion level = 3
 LOOPE Tquit            ; JE Tquit + DEC CX
 MOVAPS XMM5,XMM3       ; D = R
 FMUL DWORD [SI]        ; level/2 0
 FILD DWORD [SI]        ; big number for min
 CALL Trace0
Tquit:
RETN

На каждом уровне рекурсии я вдвое уменьшал яркость отражённого цвета.

Сцены

Источником вдохновения для первой сцены стала часть интро Chrome2, выполняемая в реальном времени. Но на этот раз сцена вычисляется в полный экран и с красивыми пересечениями.


В парке аттракционов Walt Disney Studios в основном холле наверху магазина вращается три сферы. Мне это очень понравилось.

Из соображений скорости во второй сцене есть только одна шина, состоящая из сфер, остальные — это отражения.


Я уже пытался воссоздать это гипнотическое движение в своём 256-байтном интро, но результат мне не понравился.

Эта трассируемая лучами сцена намного лучше с сохраняющимися цветами и отражениями.

Создание музыки (автор: ern0)

Написание Sizesong

Характеристики платформы

Традиционные платформы с ограниченной музыкой (например, монофонические рингтоны, Amiga mod, General MIDI и т.п.) имеют «высеченные в камне» ограничения: полифонию или набор тонов, но обычно не имеют значительных ограничений на размер данных. В нашем случае, на платформе динамика PC-DOS, справедливо обратное. Мы можем сгенерировать любую волну, нет ограничений на проигрыватель, однако вычисление каждого тона и функции секвенсора отнимает место у визуальных эффектов.

Мысли о кавере

Во-первых, создание кавера хорошо известной песни для ограниченной платформы — это интересная и сложная задача. Если кавер точный, то при прослушивании в нашей голове звучит и оригинал, что усиливает ощущения. С другой стороны, мы не можем изменять партитуру, чтобы выиграть несколько байтов. Мы можем просто вырезать части целиком (например, пропускать строки), убирать инструменты (например, не использовать бас) или упрощать их (например, применять упрощённые ударные). В крайних случаях, наподобие 549Notes, мы не можем пропускать и изменять ничего.

Структура композиции

Песня «I Remember» Deadmau5 и DJ Kaskade — идеальный кандидат на создание sizecode-музыки.

Её аккордовая последовательность достаточно характерна, чтобы представлять целую композицию, поэтому я могу отказаться от вокала. Кроме того, она имеет длину всего в 8 паттернов и содержит повторения:

 1 2 R R
 3 4 R R 

Так как каждый аккорд состоит из 4 тонов, нам нужно хранить 5x4 = 20 нот.

Есть только одна сложность: смена аккорда происходит на четверть раньше ожидаемого, но только в каждом 2 из 4 случаев:

 [1 1 1 1] [1 1 1 2]
 [2 2 2 2] [2 2 2 R]
 [R R R R] [R R R R]
 [R R R R] [R R R R]

 [3 3 3 3] [3 3 3 4]
 [4 4 4 4] [4 4 4 R]
 [R R R R] [R R R R]
 [R R R R] [R R R R]

К счастью, партия ударных довольно простая и повторяющаяся:

 [BD HT BD+SN HT] [BD HT BD+SN HT]
 [BD HT BD+SN HT] etc. 

Согласно правилам жанра house, композиция начинается только с ударных, но только на половину повтора. Затем идут четыре полных повтора, с проигрыванием в каждом повторе более долгих нот. На четвёртом повторе с самыми длинными нотами дорожка ударных замолкает. Затем композиция продолжается почти с начала, но пропускает интро только с ударными.

  [drums only]
loop point:
  [drums + chords - short]
  [drums + chords - long]
  [drums + chords - longer]
  [no drums, only chords - longest]
    continue at loop point

Альтернативная версия

Мы попытались связаться с авторами, но нам это не удалось, поэтому у нас нет разрешения на публикацию кавера. Возможно, у нас есть на это право, но правила пати строже, поэтому нам пришлось изменить музыку.

Я хотел внести как можно меньше изменений, поэтому изменил только аккорды, оставив всё остальное неизменным, даже структуру аккордов:

 1 2 R R
 3 4 R R

Моя основная задача заключалась в создании композиции, как можно больше отличающейся от оригинала, и мне кажется, я справился. Моя версия ярче, счастливее и светлее, и она звучит как рефрен, а не отдельная песня.

Оригинал мне нравится больше; он очень уникален и имеет необычно хорошо сделанную последовательность аккордов, особенно для современной композиции; он напоминает мне о 80-х, золотой эпохе поп-музыки.

Но я не разочарован своей версией; на самом деле, я начинал писать небольшую счастливую композицию, в которой эта тема будет рефреном.

Создание музыки, часть 2 (автор: TomCat)

Программный синтезатор PC-Speaker

Сэмпл

Чтобы PC speaker работал наподобие устройства PWM, мы переключили канал 2 PIT в нулевой режим работы («прерывание по счётчику терминала»).

 MOV AL,90H
 OUT 43H,AL

Благодаря этому мы можем выводить 6-битный сэмпл. Значение 0 — это тишина, значение 63 — максимальная громкость.

IRQ:
 PUSHA
 MOV AL,2   ; Sample [0...127]
 SHR AL,1   ; scaled to 6-bit
 JZ .1      ; zero means pause (no sound)
 OUT 42H,AL ; out the 6bit sample
.1:
 ...
 POPA
IRET

Темп и ноты

Мы присвоили счётчику таймера значение 68 (позже мы назвали его Divider), потому что хотели получить темп 129 bpm.

 MOV AL,68
 OUT 40H,AL
 MOV AL,0
 OUT 40H,AL

Тогда частота проигрывателя будет 17,5 кГц.

Hz=105000000/88/Divider,

bpm(low)=Hz*60sec/2/2/2/2/2/2/2/2/2/2/2/2/2/2,

bpm(high)=Hz*60sec/2/2/2/2/2/2/2/2/2/2/2/2/2.

Для проигрывания музыкальных нот нужно умножать несущую волну на постоянные значения. Мы можем вычислять эти значения в зависимости от частот, например, нота A4 (ля четвёртой октавы) вычисляется так: A_4=(32*256*44000/Hz+50)/100.

У меня есть файл inlcude для нот: notes.inc

Ударные

Мы хорошо повеселились с ударными программного синтезатора pc-speaker в выпущенном ранее продукте.

И этот очень простой паттерн ударных (bd — ht — sn/bd — ht) использовался и в другом интро, но с другим темпом: qblove.


Басы ударных реализованы простым делением: постоянное значение делится на время (или счётчик таймера).

KICKDRUM:
 MOV AX,16128   ; constant value
 CWD            ; extend the value to 2 words
 MOV CX,8191    ; get some lower bits of
 AND CX,SI      ; the timer counter (SI)
 INC CX         ; avoiding division by zero
 DIV CX         ; get one bit only
 AND AL,64      ; 0 or 64 will be the volume (the sample)

Сравнивая SN (слева) с BD (справа), можно заметить, что малый барабан намного дольше и более случайный, чем басовый.


Хай-хэту тоже требуется случайный шум, поэтому HT и SN начинаются с одного фрагмента кода.

 XCHG AX,DI    ; DI: pointer to video memory, which is quite random here :)
 MUL SI        ; SI: the timer counter
 XCHG AX,DX    ; AX: random number depending on time
 AND AX,32     ; get only one random bit

Аккорды

Один аккорд состоит из четырёх просуммированных нот.

 MOV BP,NOTES
CHORDS:
 SALC            ; AL: zero
 MOV AH,[BP+DI]  ; AX: pitch F#, ...
 MUL SI          ; SI: the timer counter
 AND DX,1FH      ; DX: get a saw wave sample
 ADD BH,DL       ; BH: sample (sum of the notes)
 INC DI          ; next note
 TEST DI,3       ; loop 4x
 JNZ CHORDS

Идея создания кавера популярной песни в среде с ограничениями — это очень увлекательно. Именно поэтому длительность нот отличается от степени двойки.


Аккорды имеют длину 7, 8 и 17. Мне пришлось преобразовать длительности в 8, 8 и 16. Поэтому я сместил начало и в последнюю долю поместил тишину.

 TEST SI,1111000000000000B
 JZ SKIP               ; no chords at the last beat
 ...                   ; chords here
DRUMS:
 SUB SI,1000000000000B ; shifting back the drums by one beat

Но после того, как музыка провалилась на Revision, мы её изменили. Я считаю, что ern0 нашёл гораздо более интересные аккорды. Мне нравится настроение новой композиции.

Паттерн

Хранимые данные музыкальных нот почти всегда можно ужать. «Сырые» данные имеют размер 32 байта:

NOTES:
 DB A_3,B_3,D_4,Fs4
 DB B_3,D_4,E_4,Gs4
 DB Cs4,E_4,Fs4,A_4
 DB Cs4,E_4,Fs4,A_4

 DB B_3,D_4,Fs4,B_4
 DB B_3,Cs4,E_4,Gs4
 DB Cs4,E_4,Fs4,A_4
 DB Cs4,E_4,Fs4,A_4

Вот простой декодер:

 MOV DI,SI
 SHRD DI,BX,2+16-5
 AND DI,7*4

Видите, мы можем сэкономить 12 байт данных…

NOTES:
 DB A_3,B_3,D_4,Fs4
 DB B_3,D_4,E_4,Gs4

 DB B_3,D_4,Fs4,B_4
 DB B_3,Cs4,E_4,Gs4

 DB Cs4,E_4,Fs4,A_4

А на декодере мы потеряли всего 7 байт.

 MOV DI,4*4
 SHR BL,1
 JC .1
 MOV DI,AX
 SHLD DI,SI,3
 AND DI,3*4
.1:

Огибающие

У нас есть две огибающие. Простая ADSR: без атаки, только затухание.

Подготавливаем регистры CL и CH перед циклом аккордов:

 MOV AX,BX       ; BL: pattern
 MOV CX,3
 SHR AL,1
 JC .1
 MOV CH,128
.1:
 DEC AX          ; skipping the drums-only intro
 SHR AL,1
 AND CL,AL

Одна огибающая для тона…

 IMUL AX,SI,-16
 OR AL,111B
 ROR AX,CL
 MUL BX          ; DH: sample

и одна для громкости…

 IMUL AX,SI,-1
 OR AH,CH        ; CH: 128 or 0
 MUL DX          ; DH: sample

Мастеринг

После сложения каждого инструмента, барабана и аккорда я проверяю максимальную громкость. Я всегда храню отладочную информацию в памяти и вывожу её при помощи внешней утилиты.

if maxvol=1
 CMP [FS:8000H],BH
 JAE .1
 MOV [FS:8000H],BH
.1:
end if

На этот раз максимальное значение сэмпла равно 181. Поэтому я ограничу его всего 7 битами.

 MOV AL,180       ; vol 181 -> vol 127
 MUL BH           ; mastering
 XCHG BX,AX
DONE:
 MOV [BP+IRQ.SAMPLE-1],BH

Но на части подавления я убираю это снижение размерности и аккорды становятся ещё громче.

Вот сгенерированная песня целиком:



Готовое интро можно скачать отсюда: https://www.pouet.net/prod.php?which=87078