Заготовка для ассемблера: Извлечение корня
Занялся я алгоритмам возведения числа в квадрат и извлечения квадратного корня для 8-битной ЭВМ. Начал гуглить на эту тему, попалась статья для Z80. Однако, ожидаемого там не нашёл. Просто подготовка таблиц сложением нечётных чисел.
Взялся я в JS отладить собственный вариант. Возведение в квадрат отладил, работает. А вот извлечение корня - даёт сбой. Причём, обе функции практически одинаковы, за исключением противоположных действий. Помню, я долго искал в сети алгоритм нахождения точки пересечения двух отрезков. А когда написал сам, тогда и нашёл готовую. Вот и сейчас, видимо, плохо ищу... Тут используется умножение, Вообще не подходит. Если можете, помогите...
<html>
<script>
function square(n) {
var
m = 1, // Mask
r = 1, // Result
t = n, // Temp
h, // 1/2 of square
q; // 1/4 of square
if(!n)
return 0;
while(t >>= 1)
m <<= 1, r <<= 2;
h = r >> 1, q = h >> 1;
while(m >>= 1) {
if(n & m)
r += h + h + q, h += q;
h >>= 1, q >>= 2;
}
return r;
}
function root(n) {
var
m = 1, // Mask
r = 0, // Result
s = 0; // Shift
++ n;
while(n >> (s + 1))
++ s;
m <<= s & -2;
do {
s = r + m, r >>= 1;
if(s < n)
n -= s, r |= m;
} while(m >>= 2);
return r;
}
function squares(m, n) {
var
i, s, r, d = [];
for(i = m; i <= n; ++ i) {
s = square(i);
r = root(s)
if(i != r)
d.push(i + "<sup>2</sup>=" + s + "<sup><sup>1/2</sup></sup>=" + r);
}
return d;
}
function main() {
document.getElementsByTagName("pre")[0].innerHTML = squares(0,100).join("<br>");
}
</script>
<body onload='main()'>
<pre>
</pre>
</body>
|
Ник :victory:
Описаний алгоритмов в сети как раз куча, если вы знаете ассемблер, то взять алгоритм ассемблера 32-бит, и перевести его на 8-бит, не является проблемой. Более того, есть способ извлечения корня "столбиком" (в сети тоже найдете), это способ переложить на ассемблер не сложно. А еще, если "для изучить" пример, то в среде для конкретного процессора пишем на Си, а полученный в конечном итоге HEX-дамп дизассемблирем. Изучаем ) |
Заготовка для ассемблера: Извлечение корня
Вложений: 1
Цитата:
Данный выше алгоритм я придумал графически, так как с математикой у меня достаточно туго. Я просто вообразил квадрат из шаров и нашёл метод дополнить их недостающими шарами. Т.е. играл воображением, а не вычислениями. Поэтому, возведение в квадрат у меня работает. А извлечение корня - нет. Просто, я не могу найти именно математическую ошибку. Т.к. извлечение корня строил тоже по графическому алгоритму. Вот иллюстрация: |
Цитата:
Math.pow(9, 1/2); // квадратный Math.pow(27, 1/3); // кубический Math.pow(81, 1/4); // ху*ческий :) |
Можно и посмеяться. Только если речь идет о 8-бит процессоре, то каким боком тут JavaScript вам поможет, неужто вы и браузер под нее писать будете? :)
Алгоритм извлечения квадратного корня, ассемблер. Это не для 8-бит, но это дает представление о решениях. Переложить этот ассемблер на 8-бит для того же Z80 можно. На Си - sqrt(double). Z80 это тот же i80, но с интересной особенностью - второй набор регистров, между которыми можно переключаться. Если программировать для 8-бит ЭВМ, к примеру 80С51, значит надо брать ее среду разработки. JS в эту среду ну никак не входит, и какая от него польза в этом контексте не понимаю. ) |
Заготовка для ассемблера: Извлечение корня
Цитата:
Т.е. JS алгоритм расписал так, будто переменные - регистры. И их можно только сдвигать, складывать и маскировать. Причём, сейчас я учусь писать на Verilog, а там и вовсе регистры двигать не надо - только проводники (Wire) смещаешь. Данная тема ещё к тому, что 17 лет назад разрабатывал (в уме, тетради) множитель 32-битных чисел (без тактирования) на ТТЛ-логике. Т.е. тупо, 32 штуки 32-битных сумматоров + 32 мультиплексора. Получилось что-то около 20 миллионов транзисторов (1 бит сумматора ~42 транзистора). Схема работает (в уме) без тактов: Подаёшь операнды X и Y, тут же снимаешь их произведение без стробирования. Тогда я думал, что возвести в квадрат без умножения нельзя. А извлечь квадратный корень - тем более! Т.е. тактировать надо. Если Вы понимаете, то Verilog-схему очень тяжело отлаживать. Легче расписать всё на Си или JS, отладить, отловить баги. А потом перевести на язык ассемблера i8080/Z80 или описать в Verilog. Причём, средства Verilog позволяют какрас сдвиг регистров заменить на сдвиг проводников. Т.е. вместо 32 тактов можно воспроизвести 32 копии одного узла со смещением проводков на 1/2 бита. И схема уже без тактовой частоты выдаст квадратный корень целого числа. Надеюсь, теперь более-менее ясно, зачем я на JS пишу то, что хочу написать на 8-битном процессоре? А потом перевести и в ПЛИС через Verilog. Просто, JS - самый доступный инструмент и я его достаточно знаю. Если бы я сразу бы взялся писать на Z80 - повесился бы. Ведь в JS можно всё собирать в логи. Каждый шаг... Вот... А у меня эта функция извлечения корня хондрит. И не понимаю, почему... P.S.: Алгоритм извлечения квадратного корня, ассемблер помог, Спасибо за ссылку. Правда, я не понимаю, как он работает. Т.е. да, в Visual Studio в отладке всё по шагам вижу, но не понимаю принцип. Свой (на JS выше) я написал сам и представляю, как он действует. А этот, готовый, вроде бы и похож на мой... Сдвиги, сумма и т.д. Короче, надо копаться. |
Нет, на Verilog я не писал, не знаю его, поэтому и недоразумение, и даже не представляю как нужно представить алгоритм на JS, который в последствии нужно будет перенести на Verilog.
Где-то у меня на CD еще хранится все что собирал и под процессоры, и под контроллеры, а среда разработки это Си и Ассемблер, отладчики, программаторы. Не выбросил, есть там и библиотеки различные, а в среде разработки можно было произвести подключения и машинного кода, так что проблем не было. А под Verilog нет библиотек? И не повесился когда писал, первый раз для Z80 (правда к этому времени я хорошо знал i80), все сразу на том что есть, даже непонятное приходилось отлаживать, следя за состоянием аккумулятора, стека и регистров. На Радио-86РК в нашей стране выросло не мало спецов в вычислительной сфере, а нынешнее положение с компьютерами порождает спецов игры в танчики. Случайно попался в руки контроллер от старой РС японской на Z80, выдрал его, оказался цел. На нем собрал MIDI клавиатуру по материалам журнала РАДИО, взята была идея. Но захотелось большего чем там было, регулировать атакой и затуханием звука, контроль силы нажатия клавиш. Стало понятным, что на одном Z80 все не получится. Вот тогда я впервые и столкнулся с однокристальными ЭВМ. И заболел. Далее уже на заказ - охранные устройства, примочки разные для охотников и рыбаков, системы контроля и т.п. Потом опять резкий поворот, и опять по воле случая, и теперь занимаюсь тем, чем занимаюсь, все прошлое на CD и покрывается пылью. ) |
Цитата:
|
в Visual Studio в отладке всё по шагам вижу, но не понимаю принцип.
А что смотрим? Это же ассемблер, значит надо знать команды, а остальное и в уме представить можно - ток медленно перетекает из регистра В в регистр С :) |
Заготовка для ассемблера: Извлечение корня
Цитата:
Цитата:
Цитата:
Цитата:
А на Радио-86РК всё тупо: Нажал СБРОС, набрал директивы D/M монитора, и весь дамп памяти у тебя в руках (без всяких Gens48). Я им пользовался до 1998, пока не сел за "Поиск" с DOS 3.11. Будете смеяться, но программирую на РК до сих пор: вот и вот. Причём, написал свой ассемблер в духе x86-синтаксиса: Код:
mov a,a -> mov al,al |
Будете смеяться, но программирую на РК до сих пор
Даже и улыбки нет. Я ведь тоже на i80 собирал свои ЭВМ, писал свой BIOS, тогда когда BIOS РК де-факто стал стандартным. Какой смех, вычислительная техника увлекательна, начиная от дискретной логики кончая программируемыми контроллерами. Посмотрел по ссылкам, для меня, это "похвально", для тех кто не любит возиться с "железом" может быть и удивительно. И в HEX-дампах есть свое волшебство. Был у меня когда-то товарищ, майор, и тоже болеющий РК-86, но поздно начал, да и логики в мышлении у него, скажем так, желательно бы иметь более для такого занятия. Лично я не занимался РК-86, она меня бы не удовлетворяла, ибо не было в ней нормальной графики. Почему и собирал свой, который имел под цветную графику четыре страницы памяти, который потом подарил тоже военному, его сын увлекался тоже этим, и это уже при наличии дома полноценного компьютера. Это наоборот приветствовать надо. Так вот пришел майор, где-то откопал в архивах об обновлении РК, и что-то связанное с новым знакогенератором, если мне только память не изменяет. В общем помню, что я рассказывал ему о работе знакогенератора. Он мне задает вопрос: - А как ты по этой фиге (дампу) понял, что это так работает? Ну я ему и показал на листочке в клеточку как работает. Он смотрел на меня так, словно я Христос открывший ему глаза на мироздание. :) А контроллерами желания нет заняться? У них ведь на борту сейчас чего только нет, и таймеры, и АЦП, и порт последовательный, и порт I2C, да чего только в них уже не втихивают. С минимальными затратами можно создавать все что угодно. |
Заготовка для ассемблера: Извлечение корня
Цитата:
2. Имею мечту спроектировать свой компьютер; Но: 1. Идея процессора очень сыра и недоработана; 2. Архитектура компьютера туманна и призрачна; 3. Не имею финансовой и физической возможно достигнуть этого опытным путём... (купить Terasic Altera DE0) 4. То же самое и с PIC... |
Из написанного:
Тем самым, это уже не 64кб, а 192кб памяти, без всяких переключений страниц. В любом случае это страницы, ибо процессор не может адресовать более 64КБ, просто представлять страницы можно по разному. В 80С48 ПЗУ программ имеет организацию, которую можно назвать страницами, а обращение к ним определяется командами. В контроллерах постарше можно задействовать разряды какого либо порта, расширив диапазон адресов, но ведь код все равно будет по границе разрядности, нельзя разбить байт на тетрады поместив одну в конец первой страницы, а вторую в начало второй. Да и у страничной организации есть и плюсы. Вот до создания своего процессора я как-то не додумался. :) В Сколково вам надо. PIC это немного иная архитектура МК, минимум портов, ну тоже интересная. Я уже лет 10 как не занимаюсь этим, но с запчастями, от кнопок до процессоров проблем нет, и покупать не надо, а что-то собирать нет времени. Была болезнь, ходили скупали позолоченное, достали, отдавал им. Но память, процессоры, микро ЭВМ, чего только нет, валяется, то ли выбросить, то ли ... |
Заготовка для ассемблера: Извлечение корня
Берём извлечения квадратного корня, ассемблер и переводим на язык JS:
// 1-в-1, как есть в ассемблере переводим в стиль Sphinx C--
// Меняем мнемонику операций в арифметические операторы
function root(x) { // x86
var
eax, ecx, edx, ebx, ebp, edi;
ebp = x + 1;
ecx = 31;
while(ebp >> ecx)
++ ecx;
ebx = 1 << (ecx & -2);
eax = 0;
do {
ecx = eax + ebx;
eax >>= 1;
edx = ecx < ebp ? -1 : 0;
edi = edx;
edx &= ecx;
ebp -= edx;
edi &= ebx;
eax |= edi;
} while(ebx >>= 2);
return eax;
}
Убераем ассемблерные трюки и в итоге получаем:
function root(x) { // JS
var
eax, ecx, edx, ebx, ebp, edi;
ebp = x + 1;
ecx = 31;
while(ebp >> ecx)
++ ecx;
ebx = 1 << (ecx & -2);
eax = 0;
do {
ecx = eax + ebx;
eax >>= 1;
if(ecx < ebp) {
ebp -= ecx;
eax |= ebx;
}
} while(ebx >>= 2);
return eax;
}
Тем самым, с языка ассемблера всё перевели в JavaScript. Обратно, с JavaScript на язык ассемблера (i8080, Z80, 6502, 68000) перевести - дело навыков и практики. (переименовываем переменные в регистры нужного процессора, разбиваем сложные операции на кучи простейщих, заменяем математические операторы мнемониками)
function root(x) { // i8080/Z80
var
a, bc, de, hl, flags, sp = [], tmp;
hl = x + 1; // i8080:inx h
sp.push(hl); // i8080:push h
bc = 32; // i8080:mvi c,16
do {
bc --; // dcr c
flag = !(hl & 0x80000000);
hl += hl &= 0x7FFFFFFF; // dad h
} while(flag); // jnc _do_
bc &= -2; // mov a,c; ani 0feh;
hl = 1; // lxi h,1; jz _xchg_
while(bc --) // dad h
hl += hl; // dcr a; jnz _dad_
de = hl; // xchg
hl = sp.pop(); // pop h
a = 0; // xra a
do {
sp.push(a), sp.push(flags); // push psw
sp.push(hl); // push h
hl = a; // mov h,0; mov l,a
hl += de; // dad d;
tmp = hl; hl = sp.pop(); sp.push(tmp); // xthl
bc = sp.pop(); // pop b
flags = sp.pop(), a = sp.pop(); // pop psw
sp.push(de); // push d
a >>= 1; // or a; rcr
de = a; // mov e,a
a = bc; // mov a,c; cmp l; mov a,b; sbb h
flags = a < hl; // push psw
if(flags) { // jnc _pop_psw_
a = hl; a -= bc; hl = a; // mov a,l; sub c; mov l,a; mov a,h; sbb b; mov h,a
}
a = de; // pop psw; mov a,e
de = sp.pop(); // pop d
if(flags) // jnc _mov_
a |= de; // or e
de >>= 2; // mov c,a; xor a,a; mov a,d; rcr; mov d,a; mov a,e; rcr; mov e,a;
} while(de); // or d; mov a,c; jnz _do_
return a;
}
Вот и готова адаптация под i8080/Z80... |
Нет, я бы такого никогда не стал делать - писать на JS, но с учетом другого языка распиливая код под него, типа писать под CISC процессор, но командами RISC процессора. )
Наверное и слава богу, что в свое время мне не попался этот Verilog. Cи, а критические места Ассемблер, и этого хватает по самые уши, и удобно, и проще, и без посредников. Ну с другой стороны дело вкуса и привычки. ;) |
Ага. Мой друг как-то сказал: Ё-моё! Я иду вверх (изучаю Phyton и т.д.) на уровень абстракции, а ты спускаешься всё ниже (от ассемблера до vhdl/verilog) до уровня вентилей и электрических связей...
Вот тут есть симулятор. Весит очень мало, но вполне годен для симуляции (разрабатываю свой процессор и видео узел на нём)... |
Ваш друг просто не задумывается о том, что без знаний базовой логики не появились бы и процессоры, а появление последних никак не означает смерть первых. Как и без наличия логики в мышлении никакой язык не поможет создать приложение.
Надо будет найти архив всего что у меня накопилось, вспомнить что там есть, можно было бы скинуть что-то полезное из библиотек. Правда только, если, не пропало, многое писалось на CD-R Princo, жутко кошмарная штуковина. Если бы можно было передать компоненты через http/ftp протокол, мог бы подарить и массу различных комплектующих. |
Цитата:
Четыре системных блока стоят: 1. Pentium-90MHz 48Mb-RAM Windows 98 и 2000 - в ходу... 2. Pentium-233MHz MMX - сгорел 10 лет назад... 3. Pentium-IV 2400MHz 512Mb-RAM - сгорел год назад... 4. Core 2 Duo 3GHz 4Gb-RAM - сгорел год назад... Ещё PC-XT есть! (не говоря про ZX-Spectrum, Atari-XE, Радио-86РК, Sega, Dendy, Электронника-МС, принтер-МС - пахал, "Поиск") Семь CRT-мониторов - Flatron, HP-M500, Acer, Relysis, Disonic - пашут лишь 2 и 1 полудохлый. (ещё монитор от Правца - исправен) Дохлый DVR - постоянный ребут, винта нет. Отцовские платы от ЭВМ на транзисторах, матрицы памяти на ферритовых сердечниках, видеоголовки от студийных видеомагнитофонов, гироскопы от самолётов . генераторы, аккумуляторы от АТС, моторы и пресса от шасси самолёта, радиостанция военных лет - пашет, осциллограф 1С, 15 ТВС от телевизоров, ПТК, катушечные магнитофоны / видеомагнитофон Вектор-6Ц (кажется), ламповые видеокамеры, прибор ночного виденья от танка, прожектор от самолёта... Не устали читать? А вот близкие - давно всё выбросить хотят, будь их воля... А сейчас отец носит запчасти оргтехники...:lol: |
Это проблема всех, кто занимается подобным - наличие дома приличной барахолки. :)
Нет, я имел ввиду комплектующие как раз под микроэлектронику - сопротивления, конденсаторы, полупроводники в чип исполнении, светодиоды различные, от миниатюрных, LED и LCD матрицы, кнопки со светодиодной подсветкой, в большей массе это компоненты японского производства. В общем тоже много всякого. Платы различные, процессоры, память, видео карты, HDD и DVD приводы, корпуса, это добро всегда накапливалось, но собиралось в готовый компьютер и продавалось по небольшой цене. Причем это не Pentium-90, а в основном двух-ядерные AMD. Буквально четыре дня назад был собран подобный на МП Gigabyte GA-M56S-S3. Таким вещам я даю вторую жизнь, не всем по карману купить компьютер, тем более в нынешней ситуации. Я хорошо разбираюсь в радиоэлектронике, даже работал когда-то по этой специальности, теперь все забросил, просто некогда. Так для себя, например собрал под 5" отсек УНЧ в компьютер, компактно и удобно, для контроля мне нужного более ничего и не надо. А так, это скорее слесарить приходится, чем паять. У меня AMD FX 8350, и нагружается массой объемных задач. Случайно уронил кулер - гребенки радиатора при этом даже не погнулись, тепловые трубки даже пыль не стряхнули, а вентилятор треснул. Найти новый 120 с двумя подшипниками так и не смог. Поставил что было - на 90. Перегревался проц., включалась защита и комп. выключался, и это еще лето не наступило. Корпус у меня отличный, а не красивый офисный ширпотреб. В нем боксы под HDD съемные, как и привода, на защелках. Прикинул, что если перенести верхний бокс HDD вниз, где есть место, а вместо него сделать бокс под 2.5" устройства (ОС у меня на SSD, плюс еще два HDD 2.5"), то вполне можно поставить вот такого монстра - http://catalog.onliner.by/fan/coolermaster/rrb2puv10gp, и еще свободнее станет. Так и сделал, теперь нужно бокс 2.5" хороший сделать. Загрузка по полной - паковка видео, при открытых редакторах и прочих плюшках нужных, а температура CPU не выше 40 градусов. Вот такая у меня сейчас "электроника" на текущий момент. :) |
Цитата:
|
Ну а что мелочится :)
Сам не понимаю что это за цена, вообще-то средняя цена его 3500. |
| Часовой пояс GMT +3, время: 12:55. |