.. _z1-divider:

===================
Zadanie 1: Dzielnik
===================

Data ogłoszenia: 27.10.2020

Termin oddania: 24.11.2020

Szablon rozwiązania i testy: :download:`divider_template.py`

Napisać moduł dzielący dwie liczby bez znaku przez siebie.

Moduł powinien mieć:

- parametr ``width`` określający szerokość wejść i wyjść w bitach
- wejście ``a``, ``width``-bitowe bez znaku: dzielna
- wejście ``b``, ``width``-bitowe bez znaku: dzielnik
- wejście ``start``, 1-bitowe: sygnał startu.  Gdy to wejście będzie równe 1, dzielnik powinien rozpocząć dzielenie.
- wyjście ``busy``, 1-bitowe: powinno być ustawione na 1 gdy dzielnik jest zajęty, zaczynając od cyklu po ustawieniu ``start``, a kończąc gdy wynik jest gotowy.
- wyjście ``q``, ``width``-bitowe: wynik dzielenia (``a / b``)
- wyjście ``r``, ``width``-bitowe: reszta z dzielenia (``a % b``)
- wyjście ``err``, 1-bitowe: ustawione jeśli wystąpił błąd dzielenia (``b`` jest równe 0); ``q`` i ``r`` mogą mieć w takim wypadku dowolną wartość

Protokół użycia dzielnika jest następujący:

1. Po resecie, dzielnik nic nie robi (``busy`` jest równe 0).
2. Dopóki ``start`` jest równe 0, dzielnik nic nie robi (nie zmienia stanu wyjść, itp).
3. Gdy ``busy`` jest równe 0, użytkownikowi wolno rozpocząć operację dzielenia przez ustawienie wejść ``a`` i ``b`` oraz ustawienie ``start`` na 1.  Dzielnik rozpocznie dzielenie w następnym cyklu zegara.  Od następnego cyklu dzielnik ustawi też ``busy`` na 1 (chyba, że będzie w stanie dać wynik w jednym cyklu zegara).
4. Dopóki dzielnik liczy, ``busy`` jest ustawione na 1, a użytkownikowi nie wolno ustawić ``start`` na 1.  Stan wyjść może się dowolnie zmieniać w tym czasie.
5. Gdy dzielnik policzy wynik, ustawia ``busy`` na 0.  W tym samym cyklu ustawia również ``err``, ``q`` i ``r`` na wyliczony wynik (nie musi ustawiać ``q`` i ``r`` jeśli nastąpił błąd).

Dzielenie jest skomplikowaną operacją — nie należy próbować zrobić dzielnika
działającego w jednym cyklu (z wyjątkiem szczególnych przypadków, jak np.
wykrywanie błędów), gdyż spowoduje to po prostu zbyt długą ścieżkę krytyczną
w realizacji sprzętowej i będzie bardzo ograniczało maksymalną częstotliwość zegara.

Istnieje wiele ciekawych algorytmów dzielenia do realizacji sprzętowej.
Na potrzeby tego zadania wystarczy użyć prostego algorytmu
liczącego jeden bit wyniku na cykl::

    r = a;
    q = 0;
    for (pos = width-1; pos >= 0; pos--) {
        bool bit = (r >= (b << pos));
        if (bit)
            r -= b << pos;
        q = q << 1 | bit;
    }