Dodawanie liczb 32-bitowych za pomocą rejestrów 16-bitowych - błąd w pętli

Dodaję liczby 32-bitowe, ale zapisując je i używając do tego liczb tylko 16-bitowych. Mam prostą pętlę w pętli. W pierwszej pętli zwiększam counter 32-bitowy o 1, w drugiej wykonuję proste sumowanie 16 razy:

#include <cstdint>
#include <cstdio>
#include <bitset>
#include<iostream>
#include <string>

uint16_t add_hi(uint16_t a, uint16_t b)
{
    uint16_t sum = a + b;
    return sum > std::max(a, b) ? 0 : 1;
}

int main()
{
    uint32_t s;
    uint32_t weyl = 0;
    uint32_t counter = 1;

    uint16_t s_low;
    uint16_t s_hi;
    uint16_t weyl_low = 0;
    uint16_t weyl_hi = 0;
    uint16_t counter_low = 1;
    uint16_t counter_hi = 0;

    uint32_t wynik;

    for (int i = 0; i < 100; i++)
    {
        counter += 1;
        s = counter;
        weyl = 0;


        counter_hi = add_hi(counter_low, 1) + counter_hi;
        counter_low = counter_low + 1;
        s_low = counter_low;
        s_hi = counter_hi;
        weyl_low = 0;
        weyl_hi = 0;

        for (int i = 0; i < 16; i++)
        {
        weyl += s;

        weyl_hi = add_hi(weyl_low, s_low) + weyl_hi + s_hi;
        weyl_low = weyl_low + s_low;
        }
        
        wynik = (weyl_hi << 16) | weyl_low;
        std::cout << weyl << " " << wynik << "\n";
         
    }

    return 0;

}

Wynik "wynik", czyli złożenie dwóch 16-bitowych liczb w jedną 32-bitową powinien być takim sam jak weyl - czyli rezultat obliczany na normalnych 32-bitowych liczbach. Funkcja add_hi oblicza górne bity będące wynikiem dodawania dwóch 16-bitowych liczb (zawsze będzie to 1 lub 0), w ten sposób możemy obliczyć górne bity będące wynikiem dodawania dwóch 32-bitowych liczb, używając tylko 16-bitowych liczb, czyli weyl_hi. Dolne bity weyl_low liczy się trywialnie.

weyl i wynik powinny być identyczne, a nie są. Z jakichś powodów weyl_hi w drugiej pętli jest ciągle równe 1, pomimo, że powinno być równe 0. Nie mam pojęcia skąd tam do cholery bierze się ta jedynka, skoro przy tak małych pętlach nie otrzymujemy rezultatów większych niż 16-bitowe.

Jak zaimplementować coś tak prostego jak 32-bitowe:

weyl += s;

Ale używając do tego liczb 16-bitowych? Weyl_hi i weyl_low mają się składać w taki sam wynik jak weyl. Ktoś znajduje tu błąd?

PS Już w pierwszym kroku pętli for (int i = 0; i < 16; i++) okazuje się, że weyl_hi jest równe 1, pomimo, że jego składowe powinny być równe zero, bo add_hi(weyl_low, s_low) powinno wynosić zero i weyl_hi + s_hi też powinno wynosić zero. Suma zer to nie zero.

Domyślam się, że robisz sobie eksperymenty w celach edukacyjno-hobbystyczno-rozrywkowych. Oczywiście, masz do tego prawo, ale warto rozważyć różne rozwiązania. Wydaje mi się, że to Ty niedawno zakładałeś podobny temat o mnożeniu liczb 128-bit.

Czy możesz opisać w słowach, co ma robić Twój program? Rozumiem, ze jakieś dodawanie dwóch liczb, ale w pętli? Czy to ma być iterowane, dodawanie, czy inkrementacja o jakąś stałą wartość, czy co? Zanim uruchomisz jakiś algorytm w pętli, proponuję testować pojedyncze dodawania i jeżeli dla dwóch pewnych składników otrzymujesz zły wynik, to albo to spróbować poprawić, albo ewentualnie podać na forum taki przypadek.

Dopiero, jak dodawanie pojedynczych liczb opanujesz, to wtedy próbuj coś z pętlą.

Czy widziałeś mój program w C na mikrokontroler (da się bez większego trudu przerobić na program na komputer), który podlinkowałem w tamtym temacie? Czy jest zrozumiałe, jak on działa?

Ja swego czasu pamiętam, że dość długo siedziałem nad algorytmami działań na liczbach reprezentowanych w postaci tablic o wielkości znanej w chwili kompilacji. W moim programie elementy tablic (odpowiednik tego, co nazywasz rejestrami) dowolnego typu liczbowego i dowolnej długości bitowej (definiowane za pomocą #define preprocesora), jak również w ten sam sposób definiuje się długość tablic.

Jak zaimplementować coś tak prostego jak 32-bitowe:

weyl += s;

Ale używając do tego liczb 16-bitowych? Weyl_hi i weyl_low mają się składać w taki sam wynik jak weyl. Ktoś znajduje tu błąd?

Najlepiej zdefiniować liczby jako unsigned short VarName[2], wtedy do będą tablice składające się z dwóch elementów. Najlepiej ta sama struktura i na wejściu i na wyjściu.

Implementacja może wyglądać mniej więcej tak:

void Add(unsigned short * Num1, unsigned short * Num2, unsigned short * NumRes)
{
   // Num1 - pierwszy składnik
   // Num2 - drugi składnik
   // NumRes - wynik

   // Implementacja dodawania powinna:
   // 1. nie tworzyć nowych obiektów
   // 2. być odporna na podanie tego samego wskaźnika nawet do wszystkich trzech parametrów
}

int main()
{
    unsigned short s[2];
    unsigned short weyl[2];
    
    // jakis kod nadający wartość s i weyl

    // Zwiększenie weyl o s
    Add(weyl, s, weyl);
}

Jak się uprzesz po swojemu, to mniej więcej coś takiego:

void Add(uint16_t &Num1, uint16_t &Num2, uint16_t &NumResHi, uint16_t &NumResLow)
{
   // Num1 - pierwszy składnik
   // Num2 - drugi składnik
   // NumResHi i NumResLow - wynik
}
int main()
{
    Add(weyl_lo, s, weyl_hi, weyl_low);
}

Jednak od razu widać, że raczej powinno się umożliwić obsługę 32-bitowych liczb (czyli po dwie zmienne) zarówno po stronie składników, jak i po stronie wyniku.

return sum > std::max(a, b) ? 0 : 1;

tu jest błąd, powinno być >= bo inaczej źle obsługuje dodawanie zera. Dodawanie ujemnych liczb też tu nie zadziała. Poza tym można to zrobić w jednym kroku - obecnie dwukrotnie dodajesz a do b, raz żeby uzyskać wynik, raz żeby obliczyć carry bit. Możesz skorzystać z raz wyliczonego wyniku

1. Naucz się debugować kod, bez tego za daleko nie zajdziesz
2. Opakuj to sobie w jakąś klasę, przeładuj operatory i będziesz mógł używać dodawania po ludzku. Albo chociaż w jakieś funkcje

andrzejlisek napisał(a):

Domyślam się, że robisz sobie eksperymenty w celach edukacyjno-hobbystyczno-rozrywkowych. Oczywiście, masz do tego prawo, ale warto rozważyć różne rozwiązania. Wydaje mi się, że to Ty niedawno zakładałeś podobny temat o mnożeniu liczb 128-bit.

Czy możesz opisać w słowach, co ma robić Twój program? Rozumiem, ze jakieś dodawanie dwóch liczb, ale w pętli? Czy to ma być iterowane, dodawanie, czy inkrementacja o jakąś stałą wartość, czy co?

To jest generator liczb pseudolosowych, a także funkcja hashująca o niego oparta. Potrzebuje on do działania między innymi czegoś co nazywa się Weyl sequence, sekwencji liczb dodawanych do siebie modulo. Tak, robię to prywatnie, do własnych celów nazwijmy to badawczo-rozwojowych.

Problem polega na tym, że akurat funkcje hahsujące muszą zwracać duże wyniki, aby były bezpieczne, co najmniej 256-bitowe. A ponieważ nie ma 256-bitowych intów, a ten akurat algorytm z konieczności potrzebuje mnożyć i dodawać tak duże liczby (typowe kryptograficzne funkcje hahsujące nie muszą, inaczej omija się ten problem), spróbowałem to zaimplementować używając 128-bitowych intów.

Można użyć biblioteki boost multiprecision, ale ona jest około 400 razy wolniejsza (podobne prędkości jak Python, który może wykonywać działania na dowolnie dużych liczbach), jeśli sobie policzymy np. bajty na sekundę, niż zwykłe działania na intach 64-bitowych. To jest absurdalnie wolno. Dlatego napisałem własne mnożenie i dodawanie, wykorzystując inty 128-bitowe - i jest o wiele szybciej. Nie rozumiem dlaczego ta biblioteka jest tak wolna.

Zanim uruchomisz jakiś algorytm w pętli, proponuję testować pojedyncze dodawania i jeżeli dla dwóch pewnych składników otrzymujesz zły wynik, to albo to spróbować poprawić, albo ewentualnie podać na forum taki przypadek.

Testowałem to dla kilku skrajnych przypadków typu liczba 1, albo 65535, a następnie dla kilku tys. losowych liczb i nie znalazłem błędu. Oczywiście na pewno przetestowałem to niewystarczająco, skoro praktyczny program (ten mój powyżej), czyli test praktyczny jednak zwracał błędne wyniki. @obscurity zauważył w czym problem.

Czy widziałeś mój program w C na mikrokontroler (da się bez większego trudu przerobić na program na komputer), który podlinkowałem w tamtym temacie? Czy jest zrozumiałe, jak on działa?

Nic z tego nie rozumiem (z tego co przejrzałem) i nawet nie wiem od czego zacząć w githubie. Zawsze jest tam milion plików i nie inaczej jest w tym przypadku. Najpierw potrzebowałbym chyba jakiejś instrukcji obsługi do github... ale chyba nie ma sensu tracić czasu w tym przypadku. Bo problem polega na tym, że z moich zgrubnych szacunków wychodzi, że ta moja implementacja z intami 128-bitowymi jest i tak jakieś 10 razy wolniejsza niż mnożenie i dodawanie 64-bitowe. Oczywiście jest to napisane przeze mnie po amatorsku, ale raczej nie da się tego zrobić znacznie szybciej, a 10 razy wolniej dyskwalifikuje zastosowania praktyczne w tym przypadku, więc raczej porzucę ten pomysł. To musiałoby działać mniej więcej tak szybko jak działania na intach 64-bitowych, a to chyba niewykonalne. Już same unsigned __int128 są kilka razy wolniejsze niż uint64_t, a na tych unsigned __int128 jeszcze trzeba zbudować funkcje do obliczeń 256-bitowych. Raczej to niemożliwe, żeby się zbliżyć do prędkości uint64_t.

Rozważałem też mnożenie z ciałach Galois GF(2^128). Mamy w miarę szybkie instrukcje PCLMULQDQ do tego i implementacje algorytmów wykonujące takie mnożenie na zmiennych __m128i (algorytm panów Gueron and Kounavis for 128-bit modular reduction in Galois Counter Mode, based on PCLMULQDQ instructions):

https://www.intel.com/content/dam/develop/external/us/en/documents/clmul-wp-rev-2-02-2014-04-20.pdf

Zaimplementowałem to, ale GF(2^128) to za mało, trzeba by tu użyć GF(2^256). Pewnie można te algorytmy przerobić, by pomnożyły liczby w GF(2^256), ale chyba gra niewarta świeczki. Instrukcje PCLMULQDQ wcale nie są takie szybkie już w przypadku GF(2^128), dla GF(2^256) będzie na pewno gorzej.

Nic z tego nie rozumiem (z tego co przejrzałem) i nawet nie wiem od czego zacząć w githubie. Zawsze jest tam milion plików i nie inaczej jest w tym przypadku. Najpierw potrzebowałbym chyba jakiejś instrukcji obsługi do github... ale chyba nie ma sensu tracić czasu w tym przypadku.

Rozumiem, że mój program był tworzony według innych założeń i chodziło tu o analizę przykładowego programu w C, który liczy na liczbach stałoprzecinkowych o wielkości zdefiniowanej za pomocą definicji. Ten program kompiluje się za pomocą kompilatora SDCC lub podobnego kompilatora C na 8051 lub Z80, a można też skompilować na komputer po odpowiednich zmianach I/O (pobieranie i wypisywanie tekstu). Nie badałem wydajności, chociaż bardziej stawiałem na bezbłędność obliczeń. Podałem tam kilka konkretnych plików, jakbyś napisał, w którym pliku i czego konkretnie nie rozumiesz, to bym wyjaśnił.

Co do obsługi samego githuba, to sprawa jest prosta, można wyświetlić lub zalinkować konkretny plik, więc myślę, ze nie powinieneś mieć problemu.

wątek wygląda znajomo: https://4programmers.net/Forum/C_i_C++/363558-dodawanie_dwoch_liczb_32_bitowych_za_pomoca_rejestrow_tylko_16_bitowych?p=1868020#id1868020

A z czego wynikają takie mocne wymagania wydajnościowe? Bo w mojej opinii, dla liczb 256-bitowych ciężko być szybszym niż wbudowane mnożenie liczb 128-bitowych. Chyba że zastanowisz się czy da się te operacje wektoryzować.

enedil napisał(a):

A z czego wynikają takie mocne wymagania wydajnościowe? Bo w mojej opinii, dla liczb 256-bitowych ciężko być szybszym niż wbudowane mnożenie liczb 128-bitowych. Chyba że zastanowisz się czy da się te operacje wektoryzować.

To ma być funkcja hashująca, nie może być znacznie wolniejsza, niż to co mamy obecnie (a, żeby była bezpieczna musi być przynajmniej 256-bitowa). I to ma wykonywać działania tak jakby liczyło inty 256-bitowe, zastąpienie tego jakimiś rejestrami SSE2, które po prostu będą mnożyć równolegle zwykłe 128-bitowe liczby nie wchodzi w grę - arytmetyka musi być 256-bitowa (inaczej będzie to złamania).

Oczywiście nie udaje mi się wykonywać działań na liczbach 256-bitowych szybciej niż wbudowane 128-bitowe, zwłaszcza, że zaimplementowałem te działania właśnie w oparciu o liczby 128-bitowe.

Wektoryzacja wchodzi w grę, ale niewiele o tym wiem, więc raczej tego nie zwektoryzuję (na razie). Zresztą zaznaczam, że to tylko eksperymenty na zasadzie co jest możliwe, a co nie, co jest jak szybkie. Z tego co mierzyłem to wyszło mi, że mnożenie i dodawanie 256-bitowe za pomocą liczb tylko 128-bitowych (z kilkoma bit shiftami) jest 30 razy wolniejsze (MB na sekundę), niż to samo na intach 64-bitowych. Czyli dramatycznie wolniejsze. A ja, żeby się zbliżyć do praktycznych zastosowań (prędkości, które osiąga SHA-256), musiałbym to robić mniej więcej tak szybko, jak na intach 64-bitowych - czyli 30 razy szybciej, niż robią to funkcje, które napisałem (założyłem też wątek o mnożeniu).

osobliwy nick napisał(a):

To ma być funkcja hashująca, nie może być znacznie wolniejsza, niż to co mamy obecnie (a, żeby była bezpieczna musi być przynajmniej 256-bitowa). I to ma wykonywać działania tak jakby liczyło inty 256-bitowe, zastąpienie tego jakimiś rejestrami SSE2, które po prostu będą mnożyć równolegle zwykłe 128-bitowe liczby nie wchodzi w grę - arytmetyka musi być 256-bitowa (inaczej będzie to złamania).

No to zaimplementuj za pomocą analogicznego algorytmu mnożenie liczb 256-bitowych za pomocą dwóch 128-bitowych, gdzie liczby 128-bitowe parujesz w dwie i dopiero wtedy wykonujesz jedno mnożenie wektorowe...