Попиксельная заливка экрана в Wolfenstein 3D (FizzleFade) — свежий взгляд

После прочтения оригинальной статьи я был несколько как поражён, так и удивлён…

Сразу скажу что сама идея псевдослучайной заливки экрана с наименьшими коллизиями (свести к минимуму попадания пикселей в уже нарисованные пиксели) ну как минимум потрясает, а тот факт, что для заливки таким образом области экрана 320х200 (64000 пикселей), если верить автору оригинальной статьи, ушло 131071 циклов, а они таки уйдут при 17-ти битном полиноме, т.е. более чем в два раза больше чем необходимо — удивляет и настораживает…

Можно оговориться, что для действительно псевдослучайной заливки пикселями такого экрана понадобится циклов ну где-то в 5 раз больше чем 131071…

И мне стало интересно: а почему решили закрасить 64Кб видеопамяти при помощи, как по мне, избыточной 17-ти битной РСЛОС? Хм…

Итак…

Максимальный период 17-ти битной РСЛОС: 2¹⁷–1 = 131071 цикл

Максимальный период 16-ти битной РСЛОС: 2¹⁶–1 = 65535 циклов

Очевидно же, что 16-ти битной РСЛОС для закрашивания экрана в 64000 пикселей хватает с лихвой.

Надо полагать, что разработчики исходили из того, что раз уж экран 320х200, следовательно для координат по оси X, которые в пределах 1…320 (maximum 140 hex) нужно брать целых 9 бит, т.к. значение 320, минимум куда можно всунуть, так это в 9 бит, в отличии от координат по оси Y, в которой их всего 1…200 (maximum C8 hex) что свободно помещается в 8 бит, итого 9+8=17 бит РСЛОС…

А что если, к примеру, экран был бы 253х253=64009, или 254х252=64008, или 255х251=64005… (Ну да, пошутил) А хотя, вы наверное уже поняли куда я клоню… Вот возьмём значения 255 (FF hex) и 251 (FB hex), ведь все эти числа свободно помещаются в восьмибитные регистры и в перемножении дают 64005, что даже больше чем 64000 байт…

Что ж, осталось реализовать 16-ти битную РСЛОС:

Для 16-ти битной РСЛОС существует 2048 полиномов с максимальным периодом вида: Х¹⁶+…+1, в следующем коде я применил, пусть не самый короткий, но он просто первый из них: Х¹⁶+Х⁵+Х³+Х²+1

Ниже я привёл код, в регистре CX которого, у нас вырабатывается некая гамма с периодом 65535, но не суть…

В старшем CH и младшем CL регистрах у нас значения которые можно использовать как координаты для нашего нестандартного экрана: CH*250+CL, т.е. Y * 250 + X.

При максимальных значениях Х=255 и Y=255 у нас получится 255*250+255=64005… А поскольку в нашей гамме не вырабатывается значение равное 0, а нам ведь нужно закрасить и нулевой адрес видеопамяти, мы смещаем всю линию назад на один пиксель командой dec di.

В следствии чего:

• 65535 раз наносим пиксель на псевдослучайный адрес в диапазоне от 0 до 64004;

• 1530 раз попадаем в уже нанесённые пиксели;

• 5 раз вылетаем за пределы диапазона буфера экрана. (при желании фиксится)

Следующий код реализует псевдослучайную попиксельную заливку экрана 320х200 16-ти битной РСЛОС с максимальным периодом 65535 циклов:

        mov     ax, 13h       ; хотим видеорежим 320х200х256         int     10h           ; попросим об этом BIOS         push    0A000h        ; начало видеобуфера где-то здесь         pop     es            ; нацелим на него сегментный регистр ES         xor     cx, cx        ; вычистим место для будущей РСЛОС next:   inc     cx            ; теперь в ней единица         shr     cx, 1         ; продвигаем РСЛОС на 1 бит вправо         jnc     skip          ; проверяем не потерялся ли младший бит         xor     cx, 8016h     ; если бит выпал, выставляем новые с инверсией по маске 1000 0000 0001 0110 skip:   movzx   bx, cl        ; эм... пусть это будет координата для оси X         movzx   ax, ch        ; ну а здесь для оси Y         imul    di, ax, 0FAh  ; определим смещение перемножив Y с 251 (да, 5 пикселей вне экрана)         add     di, bx        ; добавим смещение по X         dec     di            ; все пиксели на шаг назад, дабы хоть один попал в X=0, Y=0         mov     al, 64        ; подкрасим пиксели         stosb                 ; нарисуем пиксель         loop    next          ; проверяем, не равен ли текущий РСЛОС исходному?         ret                   ; дело сделано!

Не знаю зачем был нужен такой хардкор в предыдущем коде, просто наверное хотел создать видимость работы с заливкой по координатам, ну как это делают на языках высокого уровня)

Ниже демонстрирую более простой, быстрый и понятный код, без X и Y, просто заливаем линейную память нашего видеобуфера по закону, определённому нашей 16-ти битной РСЛОС:

        mov     ax, 13h    ; хотим видеорежим 320х200х256         int     10h        ; BIOS нам поможет в этом         push    0A000h     ; начало видеобуфера         pop     ds         ; подгоняем сегментный регистр DS под видеобуфер         mov     cl, 64     ; выбираем цвет для пикселей         mov     dx, ax     ; запоминаем исходное состояние РСЛОС next:   shr     ax, 1      ; продвигаем РСЛОС на 1 бит вправо         jnc     noxor      ; проверяем не выпал ли младший бит         xor     ax, 8016h  ; инвертируем РСЛОС по маске: 1000 0000 0001 0110 noxor:  cmp     ax, 0FA01h ; проверяем не вышел ли адрес за пределы видеобуфера         jae     skip       ; пропустим всё что не попадает в экранную область         mov     bx, ax     ; копируем AX в BX, т.к. AX не указывает на память         mov     [bx-1], cl ; сместим все адреса влево на 1, чтобы попасть в нулевой адрес skip:   cmp     ax, dx     ; сравниваем текущее состояние РСЛОС с исходным         jne     next       ; повторим цикл пока текущий РСЛОС не равен исходному         ret                ; выходим из цикла, т.к. весь экран уже закрашен