| Die letzten 10 Beiträge |
| Karlito |
Hier der Quelltext (etwas chaoitisch) von einem XML-Parser, den ich mal geschrieben habe um eine Liste aller in Wikipedia vorkommenden Wörter zu erstellen. Der Dump ist ca 12 GB groß und die Indizierung läuft in unter 10 Min. Der Hash (FNV) ist nicht 100%ig optimal. Man kann den Hash auf eine bestimmte Bit-Länge optimieren, was ich hier nicht gemacht hatte.
Es ist quasi eine Hash-Tabelle, welche keine flexible Größe hat. Dabei wird das Modul des FNV-Hashes verwendet, um ein Bucket zu adressieren. In einem Bucket befinden sich dann Einträge (LinkedList von Entries) mit dem selben Hashmodul.
Um einen Hash oder Wort zu Suchen muss man nur noch das Modul des Hashes als Adresse für das Bucket verwenden und bekommt die entsprechenden Einträge.
Ich habe hier außerdem den Stringvergleich selbst implementiert, weil strncmp eine Edit-Distanz liefert. Dazu muss mehr Arbeit getan werden, als einfach nur nach dem ersten Unterschied zu suchen und sollte damit schneller sein. Alternativen habe ich mir noch nicht angeschaut...
Gruß,
Karlito
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
301:
302:
303:
304:
305:
306:
307:
308:
309:
310:
311:
312:
313:
314:
315:
316:
317:
318:
319:
320:
321:
322:
323:
324:
325:
326:
327:
328:
329:
330:
331:
332:
333:
334:
335:
|
#include <stdio.h>
#include <string.h>
#include <wchar.h>
#include <stdint.h>
#include <ctype.h>
#include <libxml/tree.h>
#include <libxml/xmlreader.h>
#include <libxml/parser.h>
#include <libxml/parserInternals.h>
#define CONST_BUCKETS_COUNT (128*1024*1024)
#define CONST_INIT_WORDLIST_SIZE 1024
#define CONST_INIT_CONTENT_BUFFER_SIZE 1024
typedef struct _Entry Entry;
struct _Entry {
uint64_t wordOffset;
uint32_t count;
Entry *next;
};
typedef struct _WordList WordList;
struct _WordList{
char *words;
size_t wordsLength;
uint64_t wordsPos;
Entry *buckets;
int bucketsCount;
};
typedef struct _Content Content;
struct _Content {
char *buffer;
int len;
size_t allocated_size;
};
typedef struct _parserState ParserState;
struct _parserState{
int level;
int state;
Content content[1];
WordList wordList[1];
};
uint64_t fnFNV(const char* word){
uint64_t nHashVal = 0xcbf29ce484222325ULL,
nMagicPrime = 0x00000100000001b3ULL;
while(word[0]){
nHashVal ^= *word++;
nHashVal *= nMagicPrime;
}
return nHashVal;
}
void startDocumentHandler(ParserState *state){
state->level = 0;
state->state = 0;
state->content->buffer = (char *)malloc(CONST_INIT_CONTENT_BUFFER_SIZE);
state->content->len = 0;
state->content->allocated_size = CONST_INIT_CONTENT_BUFFER_SIZE;
state->wordList->words = (char *)malloc(sizeof(char)*CONST_INIT_WORDLIST_SIZE);
state->wordList->wordsLength = sizeof(char)*CONST_INIT_WORDLIST_SIZE;
state->wordList->wordsPos = 0;
state->wordList->buckets = (Entry *)calloc(CONST_BUCKETS_COUNT, sizeof(Entry));
state->wordList->bucketsCount = CONST_BUCKETS_COUNT;
};
void print_wordlist(ParserState *state){
int i, cnt=0;
Entry *bucket;
for(i=0;i<CONST_BUCKETS_COUNT;i++){
if(state->wordList->buckets[i].wordOffset != 0){
cnt++;
printf("%s\n", &state->wordList->words[state->wordList->buckets[i].wordOffset]);
bucket = state->wordList->buckets[i].next;
while(bucket){
printf("%s\n", &state->wordList->words[bucket->wordOffset]);
bucket = bucket->next;
cnt++;
}
}
}
printf("%d\n", cnt);
}
void print_stats(ParserState *state){
int i, used_bucket_count = 0, collissions_count = 0;
Entry *bucket;
uint32_t max = 1;
uint32_t *occurances;
uint32_t *tmp;
occurances = (uint32_t *)calloc(sizeof(uint32_t),max);
for(i=0;i<CONST_BUCKETS_COUNT;i++){
if(state->wordList->buckets[i].wordOffset != 0){
bucket = &state->wordList->buckets[i];
used_bucket_count++;
if(max<bucket->count){
tmp = (uint32_t *)calloc(sizeof(uint32_t),bucket->count);
memcpy(tmp, occurances, sizeof(uint32_t)*max);
max=bucket->count;
free(occurances);
occurances = tmp;
printf("%9d, %s\n", max, &state->wordList->words[bucket->wordOffset]);
}
occurances[bucket->count - 1]++;
bucket = state->wordList->buckets[i].next;
while(bucket){
if(max<bucket->count){
tmp = (uint32_t *)calloc(sizeof(uint32_t),bucket->count);
memcpy(tmp, occurances, sizeof(uint32_t)*max);
max=bucket->count;
free(occurances);
occurances = tmp;
printf("%9d, %s\n", max, &state->wordList->words[bucket->wordOffset]);
}
occurances[bucket->count - 1]++;
bucket = bucket->next;
collissions_count++;
}
}
}
printf("Stats:\n");
printf("%15s %15s %15s %15s\n", "buckets avail", "buckets used", "colls ct", "words ct");
printf("%15d %15d %15d %15d\n", CONST_BUCKETS_COUNT, used_bucket_count, collissions_count, used_bucket_count + collissions_count);
printf("\n");
for(i=0;i<max;i++){
if(occurances[i]){
printf("%9d %d\n", i+1, occurances[i]);
}
}
}
void free_buckets(Entry *bucket){
if(bucket->next){
free_buckets(bucket->next);
}
free(bucket);
}
void save_wordlist(WordList *wordList){
FILE *fptr;
int i;
Entry *bucket;
fptr = fopen("wordList.bin", "w");
if(!fptr){
printf("the wordlist-file could not be opened.\n");
} else {
for(i=0;i<CONST_BUCKETS_COUNT;i++){
if(wordList->buckets[i].wordOffset){
bucket = &wordList->buckets[i];
if(bucket->count>100){
fprintf(fptr, "%s%c", &wordList->words[bucket->wordOffset], '\0');
}
}
}
//fwrite(wordList->words, 1, wordList->wordsPos, fptr);
fclose(fptr);
}
}
void endDocumentHandler(ParserState *state){
int i;
//print_wordlist(state);
print_stats(state);
save_wordlist(state->wordList);
state->level = 0;
state->state = 0;
free(state->content->buffer);
free(state->wordList->words);
for(i=0;i<CONST_BUCKETS_COUNT;i++){
if(state->wordList->buckets[i].next){
free_buckets(state->wordList->buckets[i].next);
}
}
free(state->wordList->buckets);
}
void appendContent(ParserState *state, const xmlChar *buffer, int len){
while(state->content->allocated_size<state->content->len+len+1){
state->content->allocated_size*=2;
state->content->buffer = (char *)realloc(state->content->buffer, state->content->allocated_size);
}
memcpy(&state->content->buffer[state->content->len], buffer, len);
state->content->len+=len;
state->content->buffer[state->content->len] = 0;
}
void appendWordList(WordList *wordList, char *word){
int len;
len = strlen(word);
while(wordList->wordsPos+len+1>=wordList->wordsLength-1){
printf("resize: %lu, %lu\n", wordList->wordsLength*2, wordList->wordsPos);
wordList->words = (char *)realloc(wordList->words, wordList->wordsLength*2);
wordList->wordsLength*=2;
}
memcpy(&wordList->words[wordList->wordsPos], word, len);
wordList->words[wordList->wordsPos+len] = '\0';
wordList->wordsPos+=len+1;
}
int cmpStrings(char *a, char *b){
while(a[0]&&b[0]){
if(a[0]!=b[0]) return 0;
a++;
b++;
}
return (a[0]==b[0]);
}
void insertUniqe(ParserState *state, char *word){
uint64_t hash;
Entry *bucket;
WordList *wordList;
hash = fnFNV(word)%CONST_BUCKETS_COUNT;
bucket = &state->wordList->buckets[hash];
wordList = state->wordList;
if(bucket->wordOffset == 0){
bucket->wordOffset = wordList->wordsPos;
bucket->count = 1;
} else {
if(cmpStrings(&wordList->words[bucket->wordOffset], word)) { bucket->count +=1; return;}
while(bucket->next){
bucket = bucket->next;
if(cmpStrings(&wordList->words[bucket->wordOffset], word)) { bucket->count +=1; return;}
}
bucket->next = (Entry *)calloc(1, sizeof(Entry));
bucket = bucket->next;
bucket->wordOffset = wordList->wordsPos;
bucket->count = 1;
}
appendWordList(state->wordList, word);
}
void to_lower(char *word){
while(word[0]){
word[0] = tolower(word[0]);
word++;
}
}
void createWordList(ParserState *state, char *text){
char *pch;
char *split = " \"\\/\n\t,-_'<>|().:;=[]{}";
pch = strtok(text, split);
while(pch!=NULL){
//to_lower(pch);
insertUniqe(state, pch);
pch = strtok(NULL, split);
}
}
void startElementHandler(ParserState *state, char *name, char **atts){
if(!strcmp("text", name)){
state->state=2;
}
if(!strcmp("title", name)){
state->state=1;
}
state->level++;
}
void endElementHandler(ParserState *state, char *name, char **atts){
static int narf = 0;
state->level--;
if(state->state==2){
narf++;
createWordList(state, state->content->buffer);
if(!(narf%1000)) printf("narf: %d\n", narf);
}
state->content->len=0;
state->state=0;
}
void characterHandler(ParserState *state, const xmlChar *content, int len){
if(state->state==2){
appendContent(state, content, len);
}
}
static xmlSAXHandler SAXParser = {
0, /* internalSubset */
0, /* isStandalone */
0, /* hasInternalSubset */
0, /* hasExternalSubset */
0, /* resolveEntity */
0, /* getEntity */
0, /* entityDecl */
0, /* notationDecl */
0, /* attributeDecl */
0, /* elementDecl */
0, /* unparsedEntityDecl */
0, /* setDocumentLocator */
(startDocumentSAXFunc)startDocumentHandler, /* startDocument */
(endDocumentSAXFunc)endDocumentHandler, /* endDocument */
(startElementSAXFunc)startElementHandler, /* startElement */
(endElementSAXFunc)endElementHandler, /* endElement */
0, /* reference */
(charactersSAXFunc)characterHandler, /* characters */
0, /* ignorableWhitespace */
0, /* processingInstruction */
0, /* comment */
0, /* warning */
0, /* error */
0, /* fatalError */
};
int main(int argc, char **argv){
ParserState state;
xmlParserCtxtPtr ctxt;
if(argc==2){
ctxt = xmlCreateFileParserCtxt(argv[1]);
if(!ctxt) return EXIT_FAILURE;
ctxt->sax = &SAXParser;
ctxt->userData = &state;
xmlParseDocument(ctxt);
} else {
printf("Fehler!\n");
}
}
|
|
|
| Karlito |
Hi,
Sorry für die späte Meldung.
Du solltest einen Teil des Hashes (Präfix, Suffix oder Modul) als index für das Array verwenden, in dem Du die Wörter speicherst. Somit musst Du nicht jedes mal alle Wörter in der bestehenden Liste vergleichen, sondern musst nur in dem entsprechenden Eintrag schauen, ob der Hash nur zufällig gleich ist.
Um dann nach gleichen Hashes zu schauen, müsstest Du nur das gesamte Array durchgehen und in Einträgen mit zwei oder mehr Wörtern schauen, ob der Hash wirklich gleich ist.
Somit müsstest Du auch im Nachhinein nicht alle Wörter mit allen vergleichen, da Du die potentiellen Gleichen Hashes ja schon ermittelt hast. Der Aufwand würde sich so stark minimieren (gegenüber der aktuellen Implementierung).
Gruß,
Karlito |
| deppensido |
ich habe die Aufgabe soweit fertig. Könnt ihr bitte nochmal schauen, ob ich die #pragma Anweisungen richtig gesetzt habe, damit das Programm schneller ausgeführt wird? Die Ausführung der großen Textdatei "Les Miserables.txt" dauert immer noch ca. 15 Minuten bis das Programm terminiert, das kann doch nicht richtig sein oder?
Hier noch der komplette Code, vielen Dank im voraus und schon mal danke für die bisherigen Hilfen.
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
|
// You can use these includes and defines as a hint what functions you might want to use ;)
#define _GNU_SOURCE
#include "md5.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <omp.h>
#include <time.h>
#define HASH_LENGTH 16 //da ein MD5-Hash 16 Byte groß ist
int main (){
//unsigned char target[HASH_LENGTH] = {0xe6, 0x54, 0x93, 0xcc, 0xde, 0xe9, 0xc4, 0x51, 0x4f, 0xe2, 0x0e, 0x04, 0x04, 0xf3, 0xbc, 0xb8}; //"???" - to be used for les_miserables.txt
unsigned char target[HASH_LENGTH] = {0x1c, 0x01, 0x43, 0xc6, 0xac, 0x75, 0x05, 0xc8, 0x86, 0x6d, 0x10, 0x27, 0x0a, 0x48, 0x0d, 0xec}; // "Les Miserables" - to be used for les_miserables_preface.txt
time_t start = time(NULL);
FILE* f;
f = fopen("les_miserables_preface.txt", "r");
if(f == NULL){
return 1;
}
const char* delim = " .,;-:0123456789?!\"*+()|&[]#$/%%' \n \t " "";
unsigned char hash[HASH_LENGTH] = {0};
//Dies ist die Aufgabenstellung
/*
* - find all unique words from the book
* - create the hashes of all two-string combinations
* - try to speed it up
* Usage example (not complete!):
*/
char* words[1000000]; //1 Million Wörter können gespeichert werden
char c; //nächstes Zeichen einlesen
char buffer[1024]; //aktuelles Wort
int letterCount = 0; //Anzahl der Buchstaben im aktuellen Wort
int wordCount = 0; //Anzahl der Wörter
while ((c = fgetc(f)) != EOF) {
char needle[2] = {c};
if (!strstr(delim, needle)) { //es dürfen keine Steuerzeichen etc. eingelesen werden
buffer[letterCount++] = c;
} else {
buffer[letterCount++] = '\0';
if (letterCount > 1) {
char* tmp;
if ((tmp = malloc(letterCount * sizeof(char))) == NULL) return -1;
strncpy(tmp, buffer, letterCount); //aktuelles Wort an Adresse von Pointer tmp kopieren
int i = 0;
int match = 0;
#pragma omp parallel private(i)
while(i < wordCount) {
if(strcmp(tmp, words[i]) == 0) { //prüft, ob das aktuelle Wort bereits eingelesen wurde
match = 1;
i = wordCount;
}
else i++;
}
if(match == 0) {
words[wordCount] = tmp; //eingelesenes Wort wird gespeichert
wordCount++;
}
}
letterCount = 0;
}
}
//nach String-Kombination mit Hilfe von MD5 suchen
MD5_CTX md5_ctx;
int i,j;
int shedule = wordCount; //Arbeitseinheiten werden in Größe shedule an einzelne Threads zugewiesen
#pragma omp parallel for private(i) schedule(dynamic, shedule)
for(i=0;i<wordCount;i++) {
#pragma omp parallel for shared(words) private(j) schedule(dynamic, shedule)
for(j=0;j<wordCount;j++) {
#pragma omp task
MD5_Init(&md5_ctx);
#pragma omp task
MD5_Update(&md5_ctx, words[i], strlen(words[i]));
#pragma omp task
MD5_Update(&md5_ctx," ", strlen(" "));
#pragma omp task
MD5_Update(&md5_ctx, words[j], strlen(words[j]));
#pragma omp task
MD5_Final(hash, &md5_ctx);
if (memcmp(hash, target, HASH_LENGTH) == 0) { //wenn alle Bytes von hash, denen von target entspricht, ist das Wort gefunden
printf("%s %s\n", words[i], words[j]);
printf("\n");
int k;
#pragma omp parallel for private(k)
for(k=0;k<HASH_LENGTH;k++) {
printf("%x",hash[k]); //zugehörigen hash ausgeben
}
printf("\n");
}
}
}
//Der Rest des Codes war vorgegeben
time_t end = time(NULL);
printf("Execution took ~%fs\n", difftime(end, start));
return 0;
}
|
|
|
| deppensido |
es scheint soweit jetzt zu klappen. Aber bei der Ausgabe des Hashwertes werden die Nullen nicht mit ausgegeben.
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
|
MD5_CTX md5_ctx;
int i,j;
for(i=0;i<wordCount;i++) {
for(j=0;j<wordCount;j++) {
MD5_Init(&md5_ctx);
MD5_Update(&md5_ctx, words[i], strlen(words[i]));
MD5_Update(&md5_ctx," ", strlen(" "));
MD5_Update(&md5_ctx, words[j], strlen(words[j]));
MD5_Final(hash, &md5_ctx);
if (memcmp(hash, target, HASH_LENGTH) == 0) {
printf("%s %s\n", words[i], words[j]);
printf("\n");
int k;
for(k=0;k<HASH_LENGTH;k++) {
if(hash[k]==' ')
printf("0");
printf("%x",hash[k]);
}
printf("\n");
}
}
}
|
|
woran liegt das? |
| deppensido |
ich versuch das mal eben.
Ich dachte erst, ich müsste die Wörter so in words einlesen, dass ich in words schon alle zweier String-Kombinationen habe. Ist aber immer ein SIGSEGV Signal gekommen. Versucht hatte ich das mit der Funktion strcat(). Nach Aufgabenblatt versteh ich das aber so, dass in words erstmal nur jedes Wort einzelnd gespeichert werden soll und das mit den 2er Strings dann über MD5 läuft. Welche Variante wäre denn nun die richtige? |
| eulerscheZahl |
Das init musst du innerhalb der Schleife machen, sonst hast du noch den alten Wert drin. |
| deppensido |
ich denke der Hash, der gefunden werden soll, wird nicht richtig richtig generiert |
| deppensido |
hallo,
das funktioniert irgendwie nicht. Also jetzt wird überhaupt nichts mehr gefunden.
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
|
MD5_CTX md5_ctx;
MD5_Init(&md5_ctx);
int i,j;
for(i=0;i<wordCount;i++) {
for(j=0;j<wordCount;j++) {
MD5_Update(&md5_ctx, words[i], strlen(words[i]));
MD5_Update(&md5_ctx, " ", strlen(" "));
MD5_Update(&md5_ctx, words[j], strlen(words[j]));
MD5_Final(hash, &md5_ctx);
if (memcmp(target, hash, HASH_LENGTH) == 0) {
printf("%s %s\n", words[i], words[j]);
}
}
}
|
|
bist du sicher, dass man das so machen muss? |
| as_string |
Das hier ergibt keinen Sinn:
| code: |
1:
2:
3:
4:
5:
6:
|
for(k=0; k < HASH_LENGTH; k++) {
if((target[k] != hash[k]) == 0) {
printf("%s %s %x\n", words[i], words[j], hash[k]);
}
}
|
|
Was Du willst ist doch: Vergleiche jedes Element von target mit dem entsprechenden Element von hash. Wenn es (mindestens) eines gibt, das unterschiedlichen Wert hat, dann ist es kein Treffer, wenn alle übereinstimmen ist es ein Treffer.
Um diese Aussage treffen zu können musst Du doch dann aber logischerweise zuerst über die Arrays gelaufen sein und erst, wenn Du komplett ohne Unterschied durch gekommen bist, kannst Du etwas ausgeben.
Dann die Bedingung: Wenn etwas in C gleich 0 ist, entspricht es false. Dein if((...) == 0) wird also immer genau dann true, wenn das in der der Klammer false ist. Es wirkt also wie ein "not". Da Du in der Klammer auf Ungleichheit prüfst, aber das Ergebnis negierst, hast Du das selbe, wie wenn Du
| code: |
1:
|
if(target[k] == hash[k]) {...} |
|
geschrieben hättest. Das ist aber hier so wie so Quatsch.
Übrigens, als Du die while-Schleife hattest, hast Du nicht die Variablen vorher initialisiert gehabt, so wie ich Dir das sogar geschrieben hatte: Natürlich musst Du die Zählvariable bei einer while()-Schleife vor der Schleife immer wieder auf 0 setzen. Außerdem musst Du die boolsche Variable auf 1 setzen.
Wenn Du aber keine while()-Schleife verwenden willst, geht das äquivalent auch mit einer for()-Schleife, etwa so:
| code: |
1:
2:
3:
4:
5:
6:
7:
|
for (k = 0, match = 1; (k < HASH_LENGTH) && match; k++) {
if (target[k] != hash[k])
match = 0;
}
if (match) { ... }
|
|
Hab das Fragment zwar jetzt nicht ausprobiert, sollte aber tun, was es soll.
Ein MD5-Hash ist immer 16 Byte lang. Wenn man die einzelnen Byte hexadezimal schreibt, bekommt man zwei Zeichen von 0-9 oder a-f für jedes Byte, also insgesamt 32. Ich weiß jetzt nicht, was Du mit 32 Zeichen meintest, allerdings.
So wie Du es geschrieben hattest, gibst Du aber immer nur übereinstimmende Bytes von hash aus, was, sorry..., Quatsch ist! Der ganze Hash muss übereinstimmen, oder er stimmt eben nicht überein. Ob einzelne Byte übereinstimmen wenn nicht all, ist irrelevant.
Um diesen Vergleich zu machen, brauchst Du aber eigentlich diese Schleife gar nicht selbst zu programmieren. Die C-Standardbibliothek hat schon fertige (und stark optimierte) Funktionen für solche Dinge. Z. B. :
| code: |
1:
2:
3:
4:
5:
6:
|
#include <string.h>
...
if (memcmp(target, hash, HASH_LENGTH) == 0) {...}
|
|
Das sollte auch funktionieren (auch völlig ungetestet von mir!). bei memcmp, strcmp und so ist wichtig: Die Funktionen geben -1, 0 oder 1 zurück. Bei Gleichheit eine 0.
Gruß
Marco |
| deppensido |
so nachdem ich die ganze Nacht daran gesessen habe, habe ich nun folgendes:
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
|
// You can use these includes and defines as a hint what functions you might want to use ;)
#define _GNU_SOURCE
#include "md5.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <omp.h>
#include <time.h>
#define HASH_LENGTH 16
int main (){
//Bis zur Aufgabenstellung ist dieser Teil des Codes vorgegeben gewesen
//unsigned char target[HASH_LENGTH] = {0xe6, 0x54, 0x93, 0xcc, 0xde, 0xe9, 0xc4, 0x51, 0x4f, 0xe2, 0x0e, 0x04, 0x04, 0xf3, 0xbc, 0xb8}; //"???" - to be used for les_miserables.txt
unsigned char target[HASH_LENGTH] = {0x1c, 0x01, 0x43, 0xc6, 0xac, 0x75, 0x05, 0xc8, 0x86, 0x6d, 0x10, 0x27, 0x0a, 0x48, 0x0d, 0xec}; // "Les Miserables" - to be used for les_miserables_preface.txt
time_t start = time(NULL);
FILE* f;
f = fopen("les_miserables_preface.txt", "r");
if(f == NULL){
return 1;
}
const char* delim = " .,;-:0123456789?!\"*+()|&[]#$/%%' \n \t";
unsigned char hash[HASH_LENGTH] = {0};
//Dies ist die Aufgabenstellung
/*
* - find all unique words from the book
* - create the hashes of all two-string combinations
* - try to speed it up
* Usage example (not complete!):
*/
char* words[1000000]; //1 Million Wörter können gespeichert werden
char c;
char buffer[1024]; //aktuelles Wort
int letterCount = 0; //Anzahl der Buchstaben im aktuellen Wort
int wordCount = 0; //Anzahl der Wörter
while ((c = fgetc(f)) != EOF) {
char needle[2] = {c};
if (!strstr(delim, needle)) {
buffer[letterCount++] = c;
} else {
buffer[letterCount++] = '\0';
if (letterCount > 1) {
char* tmp;
if ((tmp = malloc(letterCount * sizeof(char))) == NULL) return -1;
strncpy(tmp, buffer, letterCount);
//hier optimieren per OpenMP
int i = 0;
int match = 0;
while(i < wordCount) {
if(strcmp(tmp, words[i]) == 0) {
match = 1;
i = wordCount;
}
else i++;
}
if(match == 0) {
words[wordCount] = tmp;
wordCount++;
}
//bis hier optimieren
}
letterCount = 0;
}
}
//nach String-Kombination mit Hilfe von MD5 suchen
//hier optimieren per OpenMP
MD5_CTX md5_ctx;
MD5_Init(&md5_ctx);
int i,j,k;
for(i=0;i<wordCount;i++) {
for(j=0;j<wordCount;j++) {
MD5_Update(&md5_ctx, words[i], strlen(words[i]));
MD5_Update(&md5_ctx, " ", strlen(" "));
MD5_Update(&md5_ctx, words[j], strlen(words[j]));
MD5_Final(hash, &md5_ctx);
for(k=0; k < HASH_LENGTH; k++) {
if((target[k] != hash[k]) == 0) {
printf("%s %s %x\n", words[i], words[j], hash[k]);
}
}
}
}
//bis hier optimieren
//Der Rest des Codes war vorgegeben
time_t end = time(NULL);
printf("Execution took ~%fs\n", difftime(end, start));
return 0;
}
|
|
die Stellen die ich noch optimieren will, habe ich kommentiert. Aber was immer mir noch nicht klar ist, wie ich nach Aufgabenstellung, Wörter zu einem Hash finden soll. Der Hash zu dem man die zwei Wörter finden soll ist 32 Zeichen lang, bei der Ausgabe, ist der dazugehörige Hash aber nur höchstens 2 Zeichen lang. Hab ich da was falsch, oder passt die Aufgabenstellung nun nicht? Mehr was ich da noch probieren könnte, fällt mir wirklich nicht mehr ein.
Dass die Wörter nur einmal eingelesen werden sollen, hab ich hinbekommen, wenn auch vielleicht etwas ungeschickt. Somit hat sich der Post zuvor erst mal erledigt. |
| Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen. |
|
|
