Zadanie polega na napisaniu w asemblerze funkcji, którą będzie można wywołać z języka C i która będzie obliczała resztę z dzielenia jednego wielomianu przez drugi. Interesuje nas dzielenie wielomianów modulo 2, to znaczy współczynniki są równe 0 lub 1, a ich dodawanie i mnożenie wykonujemy modulo 2.
Resztą z dzielenia wielomianu x^5 + x^3 + x + 1 przez x^3 + 1 jest x^2 + x.
Należy napisać funkcję o następującej deklaracji:
char *polydiv(const char *p, int pd, const char *q, int qd);
W pd + 1 bajtach począwszy od miejsca wskazywanego przez p znajdują się współczynniki wielomianu P (liczby 0 lub 1). Wyraz wolny to p[0], a współczynnik przy najwyższej potędze to p[pd]. Podobnie jest zapisany wielomian Q. Funkcja powinna zwrócić wskaźnik do zaalokowanego przez siebie funkcją malloc obszaru qd bajtów, w którym będą współczynniki reszty z dzielenia P przez Q. Jeśli nie uda się zaalokować pamięci, funkcja powinna zwrócić 0.
Zakładamy, że:
Funkcja nie może modyfikować wielomianów podanych jako argumenty. Jeśli potrzebuje dodatkowej pamięci, może ją sobie przydzielić, ale powinna ją też zwolnić.
Po wykonaniu instrukcji:
char p[6] = {1, 1, 0, 1, 0, 1};
char q[4] = {1, 0, 0, 1};
char *r = polydiv(p, 5, q, 3);
powinniśmy otrzymać r[0] = 0, r[1] = 1, r[2] = 1.
Funkcja musi być przede wszystkim poprawna. Pod uwagę jednak będzie też brany czas działania na komputerach w laboratorium (tych czarnych, o ile pamiętam, mają one procesor Intel Pentium III 1 GHz). Warto walczyć o każdą milisekundę ;-). Programy mniej efektywne, ale poprawne również otrzymają dodatnią liczbę punktów. Przypominam, że zaliczenie tego laboratorium nie jest na ocenę.
Optymalizując funkcję warto wziąć pod uwagę przypadek, gdy stopień wielomianu Q jest równy co najwyżej 15, a stopień P jest o wiele większy.
Przypominam, że konwencja wołania funkcji z C wymaga m.in. zachowywania wartości pewnych rejestrów.
Funkcja polydiv powinna zostać napisana w asemblerze NASM lub GNU Assembler. Wystarczy przysłać jeden plik źródłowy, który można zasemblować do pliku object. Plik ten powinien udostępniać funkcję polydiv gotową do wykorzystania w programie w języku C.
Rozwiązanie powinno zawierać opis użytego algorytmu i zastosowanych optymalizacji. Może on znajdować się na początku pliku źródłowego w komentarzu.
Program należy przysłać na adres tmal@mimuw.edu.pl do wtorku 10 maja 2005 do godziny 12:00 (w południe). Nadesłanie w późniejszym terminie może spowodować obniżenie oceny, a nawet nieprzyjęcie rozwiązania jeśli opóźnienie przekroczy 2 tygodnie. Trzecie zadanie zaliczeniowe najprawdopodobniej pojawi się przed 10 maja.