C-Code CRC64 (Erweitertes bish-Kommando 'crc')

[Helmut Schellong]

-----------------------------------------------------------------------
# define CRC64_ECMA182 0x42F0E1EBA9EA3693ull

static uint64_t crc64tbl[256];

static void mkcrc64tbl(void)
{
uint64_t c, crc, i;
int j;
for (i=0; i<256; ++i) {
crc= 0;
c= i<<56;
for (j=0; j<8; ++j) {
if ((crc^c) & 0x8000000000000000ull)
crc= (crc<<1) ^ CRC64_ECMA182;
else crc<<= 1;
c<<= 1;
}
crc64tbl[i]= crc;
}
return;
}

static uint64_t crc64(uint64_t crc, const void *buf, size_t n)
{
const uint8_t *bp= buf; //start-crc= 0
static _Bool T;
if (!T) mkcrc64tbl(), T= 1;
while (n>0) crc= crc64tbl[crc>>56 ^ *bp++] ^ crc<<8, --n;
return crc;
}
-----------------------------------------------------------------------

crc64 ist beträchtlich schneller als sha256.
Ich überlege zur Zeit, CRC64 im Zusammenhang mit Backup
zur pauschalen Überwachung der Datei-Integrität einzusetzen.
Das können immerhin 35000 Dateien sein.

-----------------------------------------------------------------------
crc =32
crc =64
crc [ -vV{32|64} ] [name] [name] [ datei ... ] (-Z-)
crc < datei
kdo | crc
Errechnet CRC32- oder CRC64-Prüfsummen.
CRC64 benutzt das Polynom ECMA182.
Die Optionen müssen als ein Argument angegeben werden.
Die Reihenfolge der Optionszeichen(folgen) ist beliebig.
=32 Wählt dauerhaft CRC32 (Voreinstellung).
=64 Wählt dauerhaft CRC64.
-32 Wählt CRC32; hat Vorrang vor =32 =64.
-64 Wählt CRC64; hat Vorrang vor =32 =64.
-v Der Name einer Shell-Variable wird angegeben, in die
der generierte Wert gespeichert wird.
-V Der Name einer Shell-Variable wird angegeben, aus
deren Inhalt der CRC generiert wird.
Bei Verwendung von Shell-Variable(n) wird nur ein CRC
generiert. Es ist konzeptionell günstiger, wenn der
Umgang mit vielen Quellen und Zielen in einem Skript
vorgenommen wird, u.a. da dieses Kommando intern ist und
somit keinen neuen Prozeß startet.
Das Kommando liest auch von der Standard-Eingabe (fd=0).
Beim Lesen vor der Tastatur werden hierbei anhängende
Zeichen \r und \n entfernt. Beenden durch <Enter>
und ^D bzw. ^Z.
Ohne Option -v erfolgt Ausgabe zur
Standard-Ausgabe: [datei:]crc.
Siehe auch crc(K); Die Beschreibung hier hat Priorität.
-----------------------------------------------------------------------


--
Mit freundlichen Grüßen
Helmut Schellong v...@schellong.biz
http://www.schellong.de/c.htm http://www.schellong.de/c2x.htm http://www.schellong.de/c_padding_bits.htm
http://www.schellong.de/htm/bishmnk.htm http://www.schellong.de/htm/rpar.bish.html http://www.schellong.de/htm/sieger.bish.html
http://www.schellong.de/htm/audio_proj.htm http://www.schellong.de/htm/audio_unsinn.htm http://www.schellong.de/htm/tuner.htm
http://www.schellong.de/htm/string.htm http://www.schellong.de/htm/string.c.html http://www.schellong.de/htm/deutsche_bahn.htm
http://www.schellong.de/htm/schaltungen.htm http://www.schellong.de/htm/rand.htm http://www.schellong.de/htm/dragon.c.html

[Bonita Montero]

Ich habe eine Verfahren entwickelt mit dem man die meisten
nicht-kryptografischen Hash-Algorithmen auf OoO-CPUs massiv
beschleunigen kann. Die ergeben dann andere Ausgabewerte
für den selben Input, aber den gleichen Grad der Gleichver-
teilung.
Wie ich das gemacht habe, das verrate ich nicht, denn ich
überlege mir, das Verfahren in den USA zu patentieren. Die
Idee ist eigentlich recht banal, aber wenn man danach goo-
gelt (eindeutige Schlüsselwörter zu finden ist bei der
"Komplexität" recht einfach) findet man nix. Wundert mich,
dass zuvor noch keiner auf diese Idee gekommen ist.

fnv std 32: : 0.933531 GB/s
fnv my 32: : 3.63284 GB/s 389%
fnv std 64: : 0.93967 GB/s
fnv my 64: : 3.60827 GB/s 384%
crc64: : 0.457939 GB/s
crc64 my: : 1.69729 GB/s 371%
fletcher: : 7.39996 GB/s
fletcher my: : 16.9208 GB/s 229%

CRC64 hat ja eingeschränkte Fähigkeit, Fehler zu korrigeren,
das man dann bei relevanten Eingabemengen-Größen vergessen
kann. Diese Fähigkeit verliert mein Algoritmus durch seine
Optimierung.
Den Fletcher-Algorithmus in seiner Standard-Variante habe ich sehr
elegant in C++20 mit Loop-Unrolling versehen (in C++20 geht das ohne
explizite Compiler-Unsterstützung und ohne, dass man manuell Code
mehrfach hintereinander kopieren muss). Dadurch steigert sich die
Performance von 3,75GB/s auf wie man oben sieht 7,4GB/s. Allerdings
ist der optimale Unrolling-Faktor sehr CPU-spezifisch. Auf der CPU
die ich meistens benutze (TR 3900X) liegt er bei MSVC++ 2022 und
der clang++ Vesion 13 bei fünf.
Unten seh ich mal wieder diesen C-Murks. In C++ ist der CRC64
-Algorithmus als Klasse implementiert die ein statisches Objekt
enthält das vor dem Aufruf von main() von der Runtime initialisiert
wird und das die Tabelle für den CRC64-Algorithmus generiert. Also
muss man sich gar nicht um das Initialisieren der Tabelle kümmern.

[Helmut Schellong]

On 05/23/2022 20:26, Bonita Montero wrote:
> Ich habe eine Verfahren entwickelt mit dem man die meisten
> nicht-kryptografischen Hash-Algorithmen auf OoO-CPUs massiv
> beschleunigen kann. Die ergeben dann andere Ausgabewerte
> für den selben Input, aber den gleichen Grad der Gleichver-
> teilung.
> Wie ich das gemacht habe, das verrate ich nicht, denn ich
> überlege mir, das Verfahren in den USA zu patentieren. Die
> Idee ist eigentlich recht banal, aber wenn man danach goo-
> gelt (eindeutige Schlüsselwörter zu finden ist bei der
> "Komplexität" recht einfach) findet man nix. Wundert mich,
> dass zuvor noch keiner auf diese Idee gekommen ist.
>
> fnv std 32:  : 0.933531 GB/s
> fnv my 32:   : 3.63284 GB/s 389%
> fnv std 64:  : 0.93967 GB/s
> fnv my 64:   : 3.60827 GB/s 384%
> crc64:       : 0.457939 GB/s
> crc64 my:    : 1.69729 GB/s 371%
> fletcher:    : 7.39996 GB/s
> fletcher my: : 16.9208 GB/s 229%

--------------------------------------------------------------------------------------
403] time /u/bsh/a.out -c "crc -64 zodrag"
zodrag:3243959011936764478
0.573u 0.078s 0:00.65 98.4% 1021+876k 0+0io 0pf+0w

405] time /u/bsh/a.out -c "sha256 -3 zodrag"
SHA3-256 (zodrag) = ee2ccaf09d214d6aa2721b7f25405dc77593e2fe51ca28f2b6ac84cd0ec8084a
18.930u 0.062s 0:19.02 99.8% 1001+858k 0+0io 0pf+0w

407] time /u/bsh/a.out -c "sha256 -2 zodrag"
SHA2-256 (zodrag) = 9ee5b9b87f8e54637f99ed7d49050fe2975aef93dc02cba67326bd0e8e2e2d6d
1.922u 0.078s 0:02.00 99.5% 1009+866k 0+0io 0pf+0w
--------------------------------------------------------------------------------------

Mir geht es um den vorstehenden Unterschied zwischen crc64 und sha3-256.
crc64 ist 33-mal schneller als sha3-256 und 3,4-mal schneller als sha2-256.

Und mir geht es nur um die Prüfung von Dateien, ob diese sich geändert haben.

> [...]

> Unten seh ich mal wieder diesen C-Murks. In C++ ist der CRC64
> -Algorithmus als Klasse implementiert die ein statisches Objekt
> enthält das vor dem Aufruf von main() von der Runtime initialisiert
> wird und das die Tabelle für den CRC64-Algorithmus generiert. Also
> muss man sich gar nicht um das Initialisieren der Tabelle kümmern.

Ich kann die Tabelle mit Inhalt im Prozeß auch statisch speichern, wenn ich will.
Dann ist die feststehend stets bereits fertig.

[...]

[Bonita Montero]

Am 23.05.2022 um 21:50 schrieb Helmut Schellong:

> Mir geht es um den vorstehenden Unterschied zwischen crc64 und sha3-256.
> crc64 ist 33-mal schneller als sha3-256 und 3,4-mal schneller als sha2-256.

Was ist denn das für ein doofer Vergleich ?
Seit wann vergleicht man denn kryptografisch Hashes mit nicht-
kryptografischen wo man das eine nicht mit dem anderen ersetzen
kann.

Es gibt i meiner bevorzugten Persönlichkeits-Theorie, der PSI-Theorie
von Julius Kuhl (psi-theorie.com) grundlegende Modulations-Annahme
verschiedener emotionaler Zustände auf Denken und Motivation. Diese
sind eigentlich nix neues, aber die PSI-Theorie fasst die alle in
einer gemeinsamen Logik zusammen.
Ein Modus, der bei sehr schlechter Stimmung aufkommt, ist der Diskrepanz
-sensitive. Da sieht man Unterschiede zwischen einzelnen Gedanken-Inhal-
ten, ist aber nicht in der Lage, dem eine Bedeutung beizumessen weil
man nicht eine Stufe weniger schlecht in den Modus des gedämpft negati-
ven Zustands schalten kann, dass man Zugang zum Extensions-Gedächntis
hat, was einem hilft, diese Details in Zusammenhängen zu bewerten.
Und genau das Problem haben wir hier bei dir: Du siehst diese Kontraste,
merkst aber nicht, wie unsinnig der Vergleich ist. Und das ist ein sehr
durchgängiges Persönlichkeits-Merkmal bei dir.
Du bist halt ein pathologischer Fall des "Nerd-Stils".

> Und mir geht es nur um die Prüfung von Dateien, ob

> Ich kann die Tabelle mit Inhalt im Prozeß auch statisch speichern,
> wenn ich will.

Ist auch Murks.

[Helmut Schellong]

On 05/24/2022 08:50, Bonita Montero wrote:
> Am 23.05.2022 um 21:50 schrieb Helmut Schellong:
>
>> Mir geht es um den vorstehenden Unterschied zwischen crc64 und sha3-256.
>> crc64 ist 33-mal schneller als sha3-256 und 3,4-mal schneller als sha2-256.
>
> Was ist denn das für ein doofer Vergleich ?
> Seit wann vergleicht man denn kryptografisch Hashes mit nicht-
> kryptografischen wo man das eine nicht mit dem anderen ersetzen
> kann.

Du scheinst blind zu sein!
Ich habe nun mindestens zweimal definiert, was ich vorhabe.
Nämlich feststellen, ob sich Dateiinhalte geändert haben (Backup).

Selbstverständlich kann dazu _jede beliebige_ Prüfsumme dienen!
Allerdings mit unterschiedlicher Qualität.
Performance und Qualität müssen gegeneinander abgewogen werden.

> [...]

>
>> Und mir geht es nur um die Prüfung von Dateien, ob
>> Ich kann die Tabelle mit Inhalt im Prozeß auch statisch speichern,
>> wenn ich will.
>
> Ist auch Murks.

Nichts von mir ist Murks, sondern alles ist sinnvoll
und hat sich seit vielen Jahren bewährt.
Das betrifft tatsächlich 100% meiner Software-Einheiten.

Die S-Boxen des Dragon-Algorithmus müssen in statisch initialisierter Form
vorliegen, denn es gibt keinen Algorithmus, der diese errechnen kann.

[Bonita Montero]

> Du scheinst blind zu sein!
> Ich habe nun mindestens zweimal definiert, was ich vorhabe.
> Nämlich feststellen, ob sich Dateiinhalte geändert haben (Backup).

Dazu nimmt man sichere Hashes und nicht CRC.
Das eine ersetzt daa andere nicht und ein Vergleich ist
dämlich.

> Selbstverständlich kann dazu _jede beliebige_ Prüfsumme dienen!

Eben nicht.

> Nichts von mir ist Murks, sondern alles ist sinnvoll
> und hat sich seit vielen Jahren bewährt.
> Das betrifft tatsächlich 100% meiner Software-Einheiten.

In C gibt's ja nichtmal Namespaces, dass man alles in einen
globalen Namensraum packen muss. Grauenhaft.

[Helmut Schellong]

On 05/24/2022 19:14, Bonita Montero wrote:
>> Du scheinst blind zu sein!
>> Ich habe nun mindestens zweimal definiert, was ich vorhabe.
>> Nämlich feststellen, ob sich Dateiinhalte geändert haben (Backup).
>
> Dazu nimmt man sichere Hashes und nicht CRC.
> Das eine ersetzt daa andere nicht und ein Vergleich ist
> dämlich.

Wofür werden CRC verwendet?

>> Selbstverständlich kann dazu _jede beliebige_ Prüfsumme dienen!
>
> Eben nicht.

Warum nicht?

Doch, ich schrieb:

|Selbstverständlich kann dazu _jede beliebige_ Prüfsumme dienen!

|Allerdings mit unterschiedlicher Qualität.
|Performance und Qualität müssen gegeneinander abgewogen werden.

>> Nichts von mir ist Murks, sondern alles ist sinnvoll
>> und hat sich seit vielen Jahren bewährt.
>> Das betrifft tatsächlich 100% meiner Software-Einheiten.
>
> In C gibt's ja nichtmal Namespaces, dass man alles in einen
> globalen Namensraum packen muss. Grauenhaft.

Gibt es sehr wohl, nur keine mit eigenem Schlüsselwort 'namespace'.

[Bonita Montero]

Am 24.05.2022 um 20:11 schrieb Helmut Schellong:
> On 05/24/2022 19:14, Bonita Montero wrote:
>>> Du scheinst blind zu sein!
>>> Ich habe nun mindestens zweimal definiert, was ich vorhabe.
>>> Nämlich feststellen, ob sich Dateiinhalte geändert haben (Backup).
>>
>> Dazu nimmt man sichere Hashes und nicht CRC.
>> Das eine ersetzt daa andere nicht und ein Vergleich ist
>> dämlich.
>
> Wofür werden CRC verwendet?

Bei CRC sind Kollisionen realistisch. Bei sicheren Hashes nicht.
Deswegen nutzt man für Anwendungsfälle wie deinen eben sichere
Hashes.
Ein Performance-Vergleich von sicheren Hashes und nicht sicheren
ist komplett sinnlos weil man das eine nicht mit dem anderen
ersetzen kann.

> |Selbstverständlich kann dazu _jede beliebige_ Prüfsumme dienen!

LOL.

> Gibt es sehr wohl, nur keine mit eigenem Schlüsselwort 'namespace'.

Ja, wie macht man das ?

[Helmut Schellong]

On 05/24/2022 20:32, Bonita Montero wrote:
> Am 24.05.2022 um 20:11 schrieb Helmut Schellong:
>> On 05/24/2022 19:14, Bonita Montero wrote:
>>>> Du scheinst blind zu sein!
>>>> Ich habe nun mindestens zweimal definiert, was ich vorhabe.
>>>> Nämlich feststellen, ob sich Dateiinhalte geändert haben (Backup).
>>>
>>> Dazu nimmt man sichere Hashes und nicht CRC.
>>> Das eine ersetzt daa andere nicht und ein Vergleich ist
>>> dämlich.
>>
>> Wofür werden CRC verwendet?

CRC werden für Daten mit geringem Umfang verwendet.
Beispielsweise für Festplatten-Blöcke.
Es gibt da CRC16 und CRC32 (überwiegend).
Jedoch CRC64 kann für nicht sehr große Dateien benutzt werden.

> Bei CRC sind Kollisionen realistisch. Bei sicheren Hashes nicht.
> Deswegen nutzt man für Anwendungsfälle wie deinen eben sichere
> Hashes.
> Ein Performance-Vergleich von sicheren Hashes und nicht sicheren
> ist komplett sinnlos weil man das eine nicht mit dem anderen
> ersetzen kann.
>
>> |Selbstverständlich kann dazu _jede beliebige_ Prüfsumme dienen!

Wer so darüber denkt wie Du, müßte eigentlich nur SHA3-### statt SHA2-###
verwenden, weil die Keccak-Familie sehr viel sicherer ist als der Vorgänger.
Allerdings ist Keccak 10-fach langsamer.

>> Gibt es sehr wohl, nur keine mit eigenem Schlüsselwort 'namespace'.
>
> Ja, wie macht man das ?
>

Man muß das nicht /machen/, es ist einfach da.

Die äußere Bindung (extern), die innere mit static (Datei), die Funktion(){...},
und der Block { ... } auch verschachtelt.

[Bonita Montero]

Am 24.05.2022 um 21:00 schrieb Helmut Schellong:
> On 05/24/2022 20:32, Bonita Montero wrote:
>> Am 24.05.2022 um 20:11 schrieb Helmut Schellong:
>>> On 05/24/2022 19:14, Bonita Montero wrote:
>>>>> Du scheinst blind zu sein!
>>>>> Ich habe nun mindestens zweimal definiert, was ich vorhabe.
>>>>> Nämlich feststellen, ob sich Dateiinhalte geändert haben (Backup).
>>>>
>>>> Dazu nimmt man sichere Hashes und nicht CRC.
>>>> Das eine ersetzt daa andere nicht und ein Vergleich ist
>>>> dämlich.
>>>
>>> Wofür werden CRC verwendet?
>
> CRC werden für Daten mit geringem Umfang verwendet.
> Beispielsweise für Festplatten-Blöcke.
> Es gibt da CRC16 und CRC32 (überwiegend).
> Jedoch CRC64 kann für nicht sehr große Dateien benutzt werden.

Trotzdem ersetzt das keine sicheren Hashes.

>> Bei CRC sind Kollisionen realistisch. Bei sicheren Hashes nicht.
>> Deswegen nutzt man für Anwendungsfälle wie deinen eben sichere
>> Hashes.
>> Ein Performance-Vergleich von sicheren Hashes und nicht sicheren
>> ist komplett sinnlos weil man das eine nicht mit dem anderen
>> ersetzen kann.
>>
>>> |Selbstverständlich kann dazu _jede beliebige_ Prüfsumme dienen!
>
> Wer so darüber denkt wie Du, müßte eigentlich nur SHA3-### statt SHA2-###
> verwenden, weil die Keccak-Familie sehr viel sicherer ist als der
> Vorgänger.

Das war nicht Punkt der Diskussion.

> Allerdings ist Keccak 10-fach langsamer.
>>> Gibt es sehr wohl, nur keine mit eigenem Schlüsselwort 'namespace'.
>>
>> Ja, wie macht man das ?
>>
>
> Man muß das nicht /machen/, es ist einfach da.
>
> Die äußere Bindung (extern), die innere mit static (Datei), die
> Funktion(){...},
> und der Block { ... } auch verschachtelt.

Das sind keine Namespaces. D.h. Du kannst Namen nicht nach außen
erreichbar machen, aber nur aus dem jeweiligen Namespace.
IQ auf Zimmertemperatur ?

[Helmut Schellong]

On 05/25/2022 07:19, Bonita Montero wrote:
> Am 24.05.2022 um 21:00 schrieb Helmut Schellong:
>> On 05/24/2022 20:32, Bonita Montero wrote:
>>> Am 24.05.2022 um 20:11 schrieb Helmut Schellong:
>>>> On 05/24/2022 19:14, Bonita Montero wrote:
>>>>>> Du scheinst blind zu sein!
>>>>>> Ich habe nun mindestens zweimal definiert, was ich vorhabe.
>>>>>> Nämlich feststellen, ob sich Dateiinhalte geändert haben (Backup).
>>>>>
>>>>> Dazu nimmt man sichere Hashes und nicht CRC.
>>>>> Das eine ersetzt daa andere nicht und ein Vergleich ist
>>>>> dämlich.
>>>>
>>>> Wofür werden CRC verwendet?
>>
>> CRC werden für Daten mit geringem Umfang verwendet.
>> Beispielsweise für Festplatten-Blöcke.
>> Es gibt da CRC16 und CRC32 (überwiegend).
>> Jedoch CRC64 kann für nicht sehr große Dateien benutzt werden.
>
> Trotzdem ersetzt das keine sicheren Hashes.

https://en.wikipedia.org/wiki/Birthday_problem#Probability_table

CRC32 würde ich jedenfalls nicht dafür verwenden.
Mit CRC64 jedoch wird die Lage wesentlich besser:
Es werden etwa 5 Mrd. Hashes gebraucht, um mit einer Wahrscheinlichkeit
von 50% eine Kollision zu erleben.
Mit CRC32 sind das etwa 80000 (statt 5 Mrd).

Es liegt vorstehend ungefähr das Quadrat zwischen einer Verdoppelung der Bits.
256*256 = 65536; 2^8 * 2^8 = 2^(8+8) = 2^16
(7,7*10^4)^2 = 5,9*10^9 = 5,9 Mrd.

>>>> Gibt es sehr wohl, nur keine mit eigenem Schlüsselwort 'namespace'.
>>>
>>> Ja, wie macht man das ?
>>>
>>
>> Man muß das nicht /machen/, es ist einfach da.
>>
>> Die äußere Bindung (extern), die innere mit static (Datei), die Funktion(){...},
>> und der Block { ... } auch verschachtelt.
>
> Das sind keine Namespaces. D.h. Du kannst Namen nicht nach außen
> erreichbar machen, aber nur aus dem jeweiligen Namespace.
> IQ auf Zimmertemperatur ?

Es sind sehr wohl Namensräume, nur eben nicht genau diejenigen Namensräume,
wie sie unter C++ mittels 'namespace' eingerichtet werden können.

Du scheinst _nur_ C++ für Namensräume zu kennen.

https://de.wikipedia.org/wiki/Namensraum

[Helmut Schellong]

Der C-Standard enthält etwa 20-mal die Wörter 'name space'
und erklärt dies und den 'scope' von 'identifier' auf mehreren Seiten.

[Bonita Montero]

Am 25.05.2022 um 11:02 schrieb Helmut Schellong:
> On 05/25/2022 07:19, Bonita Montero wrote:
>> Am 24.05.2022 um 21:00 schrieb Helmut Schellong:
>>> On 05/24/2022 20:32, Bonita Montero wrote:
>>>> Am 24.05.2022 um 20:11 schrieb Helmut Schellong:
>>>>> On 05/24/2022 19:14, Bonita Montero wrote:
>>>>>>> Du scheinst blind zu sein!
>>>>>>> Ich habe nun mindestens zweimal definiert, was ich vorhabe.
>>>>>>> Nämlich feststellen, ob sich Dateiinhalte geändert haben (Backup).
>>>>>>
>>>>>> Dazu nimmt man sichere Hashes und nicht CRC.
>>>>>> Das eine ersetzt daa andere nicht und ein Vergleich ist
>>>>>> dämlich.
>>>>>
>>>>> Wofür werden CRC verwendet?
>>>
>>> CRC werden für Daten mit geringem Umfang verwendet.
>>> Beispielsweise für Festplatten-Blöcke.
>>> Es gibt da CRC16 und CRC32 (überwiegend).
>>> Jedoch CRC64 kann für nicht sehr große Dateien benutzt werden.
>>
>> Trotzdem ersetzt das keine sicheren Hashes.
>
> https://en.wikipedia.org/wiki/Birthday_problem#Probability_table
>
> CRC32 würde ich jedenfalls nicht dafür verwenden.
> Mit CRC64 jedoch wird die Lage wesentlich besser:
> Es werden etwa 5 Mrd. Hashes gebraucht, um mit einer Wahrscheinlichkeit
> von 50% eine Kollision zu erleben.

Das ist egal. Wenn ich was brauche, was keine Kollision ergibt,
dann nehm ich einen sicheren Hash. Der ist über jeden Zweifel
erhaben.

>> Das sind keine Namespaces. D.h. Du kannst Namen nicht nach außen
>> erreichbar machen, aber nur aus dem jeweiligen Namespace.
>> IQ auf Zimmertemperatur ?

> Es sind sehr wohl Namensräume, nur eben nicht genau diejenigen Namensräume,
> wie sie unter C++ mittels 'namespace' eingerichtet werden können.

Nein, gibt es nicht.
Eine statische Funkton hat keinen Namensraum weil sie aus
einer anderen Übersetzungseinheit nicht erreichbar ist.

[Bonita Montero]

> Der C-Standard enthält etwa 20-mal die Wörter 'name space'
> und erklärt dies und den 'scope' von 'identifier' auf mehreren Seiten.

Ja, in dem Fall ist dann auch das Wort scope besser geeignet.
Echte Namespaces hat C nicht.

[Helmut Schellong]

Es gibt keinen sicheren Hash!
Es wird auch niemals einen sicheren Hash geben!

Hast Du die Tabelle nicht gelesen?!
Darin sind doch auch die Kollisions-Wahrscheinlichkeiten
für 512 Bit breite Hash-Werte angegeben.

>
>>> Das sind keine Namespaces. D.h. Du kannst Namen nicht nach außen
>>> erreichbar machen, aber nur aus dem jeweiligen Namespace.
>>> IQ auf Zimmertemperatur ?
>
>> Es sind sehr wohl Namensräume, nur eben nicht genau diejenigen Namensräume,
>> wie sie unter C++ mittels 'namespace' eingerichtet werden können.
>
> Nein, gibt es nicht.
> Eine statische Funkton hat keinen Namensraum weil sie aus
> einer anderen Übersetzungseinheit nicht erreichbar ist.

Deine Definition von Namensraum ist falsch.
Es ist wohl die spezifische Definition von C++.

https://de.wikipedia.org/wiki/Namensraum

Der C-Standard definiert auf mehreren Seiten Namensräume und Bereiche (scope).
Das gilt hier in dieser NG.
Du leugnest es aber wiederholt!

[Helmut Schellong]

On 05/23/2022 20:26, Bonita Montero wrote:

> Ich habe eine Verfahren entwickelt mit dem man die meisten
> nicht-kryptografischen Hash-Algorithmen auf OoO-CPUs massiv
> beschleunigen kann. Die ergeben dann andere Ausgabewerte
> für den selben Input, aber den gleichen Grad der Gleichver-
> teilung.
> Wie ich das gemacht habe, das verrate ich nicht, denn ich
> überlege mir, das Verfahren in den USA zu patentieren. Die
> Idee ist eigentlich recht banal, aber wenn man danach goo-
> gelt (eindeutige Schlüsselwörter zu finden ist bei der
> "Komplexität" recht einfach) findet man nix. Wundert mich,
> dass zuvor noch keiner auf diese Idee gekommen ist.
>
> fnv std 32:  : 0.933531 GB/s
> fnv my 32:   : 3.63284 GB/s 389%
> fnv std 64:  : 0.93967 GB/s
> fnv my 64:   : 3.60827 GB/s 384%
> crc64:       : 0.457939 GB/s
> crc64 my:    : 1.69729 GB/s 371%
>

Software kann nicht patentiert werden.

[Bonita Montero]

Sicher, irgendwelche Aliens werden in der Lage sein, in 2s
eine Kollision aus einem sicheren Hash >= 256 Bit zu errechnen.

> für 512 Bit breite Hash-Werte angegeben.

Bitte berechne mir doch mal eine Kollision für SHA-2 mit 512
Bit wenn das so einfach ist.
Mann, was bist du für ein Idiot.

> Deine Definition von Namensraum ist falsch.
> Es ist wohl die spezifische Definition von C++.

Ich hab halt eine Definition die sich an praktischen Notwendigkeiten
orientiert und keine Luftnummern im Kopf, die in der Praxis nicht das
bieten was man braucht. C ist einfach grauenhaft.

[Bonita Montero]

Am 26.05.2022 um 11:11 schrieb Helmut Schellong:
> On 05/23/2022 20:26, Bonita Montero wrote:
>> Ich habe eine Verfahren entwickelt mit dem man die meisten
>> nicht-kryptografischen Hash-Algorithmen auf OoO-CPUs massiv
>> beschleunigen kann. Die ergeben dann andere Ausgabewerte
>> für den selben Input, aber den gleichen Grad der Gleichver-
>> teilung.
>> Wie ich das gemacht habe, das verrate ich nicht, denn ich
>> überlege mir, das Verfahren in den USA zu patentieren. Die
>> Idee ist eigentlich recht banal, aber wenn man danach goo-
>> gelt (eindeutige Schlüsselwörter zu finden ist bei der
>> "Komplexität" recht einfach) findet man nix. Wundert mich,
>> dass zuvor noch keiner auf diese Idee gekommen ist.
>>
>> fnv std 32:  : 0.933531 GB/s
>> fnv my 32:   : 3.63284 GB/s 389%
>> fnv std 64:  : 0.93967 GB/s
>> fnv my 64:   : 3.60827 GB/s 384%
>> crc64:       : 0.457939 GB/s
>> crc64 my:    : 1.69729 GB/s 371%
>>
> Software kann nicht patentiert werden.

In den USA sind Algorithmen patentierbar.
Seit einem Gerichtsurteil von 2014 kann man nur noch einzelne
Implementationen patentieren und wenn das Patent eine C-Imple-
mentation ist, dann deckt die auch C++ ab, aber wenn das dann
jemand sagen wir mal in Rust implementiert, dann ist der fein
raus.
Ich sach ja: Du bist einfach nur blöd.

[Christian Garbs]

Mahlzeit!

Helmut Schellong <r...@schellong.biz> wrote:

> --------------------------------------------------------------------------------------
> 403] time /u/bsh/a.out -c "crc -64 zodrag"
> zodrag:3243959011936764478
> 0.573u 0.078s 0:00.65 98.4% 1021+876k 0+0io 0pf+0w
>
> 405] time /u/bsh/a.out -c "sha256 -3 zodrag"
> SHA3-256 (zodrag) = ee2ccaf09d214d6aa2721b7f25405dc77593e2fe51ca28f2b6ac84cd0ec8084a
> 18.930u 0.062s 0:19.02 99.8% 1001+858k 0+0io 0pf+0w
>
> 407] time /u/bsh/a.out -c "sha256 -2 zodrag"
> SHA2-256 (zodrag) = 9ee5b9b87f8e54637f99ed7d49050fe2975aef93dc02cba67326bd0e8e2e2d6d
> 1.922u 0.078s 0:02.00 99.5% 1009+866k 0+0io 0pf+0w
> --------------------------------------------------------------------------------------
>
> Mir geht es um den vorstehenden Unterschied zwischen crc64 und sha3-256.
> crc64 ist 33-mal schneller als sha3-256 und 3,4-mal schneller als sha2-256.
>
> Und mir geht es nur um die Prüfung von Dateien, ob diese sich geändert haben.

Wenn es Dir nicht um Kryptographie geht, kannst Du Dir auch xxHash mal
angucken, das soll auch sehr schnell sein:

https://github.com/Cyan4973/xxHash

Ein Vergleich mit CRC64 ist auf der xxHash-Seite nicht zu finden, da
müsstest Du selber messen.

Dort wird auch das SMHasher-Projekt erwähnt, das scheint eine
Testsuite für Hashes zu sein, wie oft sie Kollisionen produzieren etc.
Das wäre dann ggf. ein zweites Kriterium neben der Geschwindigkeit.

Gruß
Christian

PS: Dass eine kryptographische Hashfunktion langsamer ist als eine
nicht-kryptographische, sollte nicht überraschend sein. Mein Auto
kann auch schneller fahren als eine Dampfwalze. Aber halt keine
Straßen planieren ;-)
--
....Christian.Garbs....................................https://www.cgarbs.de
It seemed like a good idea at the time.

[Helmut Schellong]

On 05/28/2022 14:02, Christian Garbs wrote:
> Mahlzeit!
>
> Helmut Schellong <r...@schellong.biz> wrote:
>
>> --------------------------------------------------------------------------------------
>> 403] time /u/bsh/a.out -c "crc -64 zodrag"
>> zodrag:3243959011936764478
>> 0.573u 0.078s 0:00.65 98.4% 1021+876k 0+0io 0pf+0w
>>
>> 405] time /u/bsh/a.out -c "sha256 -3 zodrag"
>> SHA3-256 (zodrag) = ee2ccaf09d214d6aa2721b7f25405dc77593e2fe51ca28f2b6ac84cd0ec8084a
>> 18.930u 0.062s 0:19.02 99.8% 1001+858k 0+0io 0pf+0w
>>
>> 407] time /u/bsh/a.out -c "sha256 -2 zodrag"
>> SHA2-256 (zodrag) = 9ee5b9b87f8e54637f99ed7d49050fe2975aef93dc02cba67326bd0e8e2e2d6d
>> 1.922u 0.078s 0:02.00 99.5% 1009+866k 0+0io 0pf+0w
>> --------------------------------------------------------------------------------------
>>
>> Mir geht es um den vorstehenden Unterschied zwischen crc64 und sha3-256.
>> crc64 ist 33-mal schneller als sha3-256 und 3,4-mal schneller als sha2-256.
>>
>> Und mir geht es nur um die Prüfung von Dateien, ob diese sich geändert haben.
>
> Wenn es Dir nicht um Kryptographie geht, kannst Du Dir auch xxHash mal
> angucken, das soll auch sehr schnell sein:
>
> https://github.com/Cyan4973/xxHash
>
> Ein Vergleich mit CRC64 ist auf der xxHash-Seite nicht zu finden, da
> müsstest Du selber messen.

Ich habe mir das angesehen.
Aber mir mißfällt dort die Präsentation, und eine entsprechende hash-Funktion ist nicht auffindbar.
Alle Quelldateien (xxhash.c ...) sind in Wirklichkeit html-Dateien.
Ich finde dort kein Archiv.

Meine Funktion crc64() hat nur eine Zeile!:

while (n>0) crc= crc64tbl[crc>>56 ^ *bp++] ^ crc<<8, --n;

Signifikant schneller dürfte keine andere Funktion sein.
(Man beachte: 'n' kann 300000000 enthalten!)

> Dort wird auch das SMHasher-Projekt erwähnt, das scheint eine
> Testsuite für Hashes zu sein, wie oft sie Kollisionen produzieren etc.
> Das wäre dann ggf. ein zweites Kriterium neben der Geschwindigkeit.

Dazu hatte ich schon etwas zur Abschätzung gepostet:
https://en.wikipedia.org/wiki/Birthday_problem#Probability_table

> Gruß
> Christian
>
> PS: Dass eine kryptographische Hashfunktion langsamer ist als eine
> nicht-kryptographische, sollte nicht überraschend sein. Mein Auto
> kann auch schneller fahren als eine Dampfwalze. Aber halt keine
> Straßen planieren ;-)
>

Gerade weil ich das seit langem weiß, suchte ich eine schnellere Alternative zu SHA###.
Ich verwende für meine paar großen Dateien Backup zur Cloud zwar SHA3-256.
Jedoch mir fehlt eigentlich noch eine Tabellendatei mit Zeitstempeln, Size und Hashes
für meine etwa 35000 einzelnen Dateien auf Speicherkarte und separater Festplatte.
Und genau dafür will ich nicht SHA256 verwenden.
CRC64 dürfte ausreichen.

[Bonita Montero]

Am 28.05.2022 um 14:02 schrieb Christian Garbs:
> Mahlzeit!
>
> Helmut Schellong <r...@schellong.biz> wrote:
>
>> --------------------------------------------------------------------------------------
>> 403] time /u/bsh/a.out -c "crc -64 zodrag"
>> zodrag:3243959011936764478
>> 0.573u 0.078s 0:00.65 98.4% 1021+876k 0+0io 0pf+0w
>>
>> 405] time /u/bsh/a.out -c "sha256 -3 zodrag"
>> SHA3-256 (zodrag) = ee2ccaf09d214d6aa2721b7f25405dc77593e2fe51ca28f2b6ac84cd0ec8084a
>> 18.930u 0.062s 0:19.02 99.8% 1001+858k 0+0io 0pf+0w
>>
>> 407] time /u/bsh/a.out -c "sha256 -2 zodrag"
>> SHA2-256 (zodrag) = 9ee5b9b87f8e54637f99ed7d49050fe2975aef93dc02cba67326bd0e8e2e2d6d
>> 1.922u 0.078s 0:02.00 99.5% 1009+866k 0+0io 0pf+0w
>> --------------------------------------------------------------------------------------
>>
>> Mir geht es um den vorstehenden Unterschied zwischen crc64 und sha3-256.
>> crc64 ist 33-mal schneller als sha3-256 und 3,4-mal schneller als sha2-256.
>>
>> Und mir geht es nur um die Prüfung von Dateien, ob diese sich geändert haben.
>
> Wenn es Dir nicht um Kryptographie geht, kannst Du Dir auch xxHash mal
> angucken, das soll auch sehr schnell sein:

Der denkt massiv auf der Resourcen-Ebene ohne sich für den
Einzelfall anzuschauen, ob das denn wirklich nötig ist.

[Christian Garbs]

Mahlzeit!

Helmut Schellong <r...@schellong.biz> wrote:
> On 05/28/2022 14:02, Christian Garbs wrote:

>> Wenn es Dir nicht um Kryptographie geht, kannst Du Dir auch xxHash mal
>> angucken, das soll auch sehr schnell sein:
>>
>> https://github.com/Cyan4973/xxHash
>>
>> Ein Vergleich mit CRC64 ist auf der xxHash-Seite nicht zu finden, da
>> müsstest Du selber messen.
>
> Ich habe mir das angesehen.
> Aber mir mißfällt dort die Präsentation, und eine entsprechende hash-Funktion ist nicht auffindbar.
> Alle Quelldateien (xxhash.c ...) sind in Wirklichkeit html-Dateien.

Die sind nicht "in Wirklichkeit html-Dateien", der Source wird nur als
HTML gerendert, wenn man die für die Anzeige im Browser gedachten URLs
benutzt.

xxhash.c ist ziemlich leer, die Funktionalität wird irgendwo in
xxhash.h liegen, ich habe mir das aber nicht genauer angeguckt.

> Ich finde dort kein Archiv.

Du kannst bei GitHub:

- auf die raw-Ansicht umschalten:
https://raw.githubusercontent.com/Cyan4973/xxHash/dev/xxhash.h

- das ganze Git-Repository runterladen:
git clone https://github.com/Cyan4973/xxHash.git

- den aktuellen Stand als ZIP exportieren:
https://github.com/Cyan4973/xxHash/archive/refs/heads/dev.zip

>> Dort wird auch das SMHasher-Projekt erwähnt, das scheint eine
>> Testsuite für Hashes zu sein, wie oft sie Kollisionen produzieren etc.
>> Das wäre dann ggf. ein zweites Kriterium neben der Geschwindigkeit.
>
> Dazu hatte ich schon etwas zur Abschätzung gepostet:
> https://en.wikipedia.org/wiki/Birthday_problem#Probability_table

Aber halt nicht gemessen. Vielleicht ist CRC64 deutlich schlechter,
was Kollisionen angeht.

> Gerade weil ich das seit langem weiß, suchte ich eine schnellere Alternative zu SHA###.
> Ich verwende für meine paar großen Dateien Backup zur Cloud zwar SHA3-256.
> Jedoch mir fehlt eigentlich noch eine Tabellendatei mit Zeitstempeln, Size und Hashes
> für meine etwa 35000 einzelnen Dateien auf Speicherkarte und separater Festplatte.
> Und genau dafür will ich nicht SHA256 verwenden.
> CRC64 dürfte ausreichen.

Die Erstellung einer solchen Tabelle ist, unabhängig vom Algorithmus,
eine Zeile Shellskript, die je nach Langsamkeit halt einmal über Nacht
läuft:

find -type f | while read file; do echo "$(stat -c "%s %X %Y %Z" "$file") $(sha256sum "$file")"; done

(Das kommt nicht mit Zeilenumbrüchen in Dateinamen klar, dafür müsste
man dann mit -print0 usw. arbeiten.)

Mir wäre da der Aufwand, erstmal einen Hash-Algorithmus zu
implementieren, zu hoch.

Zwei kurze Tests mit dem Skript und sha256sum:

- Mein $HOME (~14GB in 256766 Dateien) hat er in 6m39s durchgeackert.
Da sind haufenweise kleine Dateien dabei, die dürften teuer sein.

- Mein Spiele-Ordner hat ~144GB in 257884 Dateien, das hat 19m49s gedauert.

Und das Skript ist noch in keinster Weise optimiert, das könnte ja
z.B. mehrere Dateien gleichzeitig prüfen.


Gruß
Christian
--
....Christian.Garbs....................................https://www.cgarbs.de
Outside of a dog, a book is man's best friend. Inside of a dog, it is
too dark to read. (Groucho Marx)

[Helmut Schellong]

Ich habe wenige Minuten vor.

> (Das kommt nicht mit Zeilenumbrüchen in Dateinamen klar, dafür müsste
> man dann mit -print0 usw. arbeiten.)
>
> Mir wäre da der Aufwand, erstmal einen Hash-Algorithmus zu
> implementieren, zu hoch.

Ich habe in mein Shell-Programm
CRC32, CRC64, SHA2-256, SHA2-512, SHA3-256, SHA3-512,
und die Krypto-StreamCipher Spritz, Rabbit, Dragon
implementiert.

> Zwei kurze Tests mit dem Skript und sha256sum:
>
> - Mein $HOME (~14GB in 256766 Dateien) hat er in 6m39s durchgeackert.
> Da sind haufenweise kleine Dateien dabei, die dürften teuer sein.
>
> - Mein Spiele-Ordner hat ~144GB in 257884 Dateien, das hat 19m49s gedauert.
>
> Und das Skript ist noch in keinster Weise optimiert, das könnte ja
> z.B. mehrere Dateien gleichzeitig prüfen.
>
>
>

Ich will bei festgestellter Änderung von Zeitstempel oder Größe
einen neuen Hash generieren, und allgemein in größeren Abständen
die Hashes prüfen.


Beispiel-Skript:
===========================================================================
set -f
set fn:.500 ft:.300 sz:020

cd die.c
diehard -1 /usr/nist/zodrag

for fn in $( list -fp "/usr/local/bin" )
do
expr "$(- file -b "$fn" )" :: 'ELF.%{1,} executable' || continue
fstat -sv sz "$fn"
let "sz<1000000" && continue
diehard -1 "$fn"
done
===========================================================================